A distributed minimum-distortion routing algorithm with in-network data processing

Ramin Khalili
2008
Article de conférence

Résumé

In many wired and wireless networks, nodes process input traffic to satisfy a network constraint (e.g., a capacity constraint) and to increase the utility of data in the output flows given these constraints. In this paper we focus on the special case in which data processing is applied to satisfy capacity constraints. This occurs when the sum of the rate of the input traffic at a node exceeds the sum of the capacity of its output links, or in a more general case, when the sum of the input rates is larger than any cut capacity in the network. In this case, nodes process data to decrease the output flow rate. This decrease from input rate to output rate distorts the transmitted data, which we characterize by a distortion metric. We show that the distortion cost of distributively processing input traffic in a network can be written as the sum of the distortion at individual nodes.. We present a distributed algorithm for a data-gathering network with many sources and a data sink that routes traffic and performs in-network data processing to minimize the distortion cost. In this algorithm, each node determines its routing table based on gradient information from neighboring nodes.

Official source

https://infoscience.epfl.ch/record/148822?ln=fr

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés

Chargement

Publications associées

Chargement

Network Resource Allocation for Competing Multiple Description Transmissions

Suhas Diggavi

Providing real-time multimedia services over a best-effort network is challenging due to the stringent delay requirements in the presence of complex network dynamics. Multiple description (MD) coding is one approach to transmit the media over diverse (multiple) paths to reduce the detrimental effects caused by path failures or delay. The novelty of this work is to investigate the resource allocation in a network, where there are several competing MD coded streams. This is done by considering a framework that chooses the operating points for asymmetric MD coding to maximize total quality of the users, while these streams are sent over multiple routing paths. We study the joint optimization of multimedia (source) coding and congestion control in wired networks. These ideas are extended to joint source coding and channel coding in wireless networks. In both situations, we propose distributed algorithms for optimal resource allocation. In the presence of path loss and competing users, the service quality to any particular MD stream could be uncertain. In such circumstances it might be tempting to expect that we need greater redundancy in the MD streams to protect against such failures. However, one surprising aspect of our study reveals that for large number of users who compete for the same resources, the overall system could benefit through opportunistic (hierarchical) strategies. In general networks, our studies indicate that the user composition varies from conservative to opportunistic operating points, depending on the number of users and their network vantage points.

2008

Chargement

Hierarchical Routing over Dynamic Wireless Networks

Suhas Diggavi, Matthias Grossglauser, Dominique Florian Tschopp

Dynamic networks are those where the topology changes over time and therefore efficient routes need to be maintained by frequent updates. Such updates could be costly in terms of consuming throughput available for data transmission, which is a precious resource in wireless networks. In this paper, we ask the question whether there exist low-overhead schemes for dynamic wireless networks, that could produce routes that are within a small constant factor (stretch) of the optimal route-length. This is studied by using the underlying geometric properties of the connectivity graph in wireless networks. For a class of models for mobile wireless network that fulfill some mild conditions on the connectivity and on mobility over the time of interest, we can design distributed routing algorithm that maintains the routes over a changing topology. This scheme needs only node identities and therefore integrates location service along with routing, therefore accounting for the complete overhead. We analyze the worst-case (conservative) overhead and route-quality (stretch) performance of this algorithm for the aforementioned class of wireless network connectivity and mobility models. In particular for these models, we show that our algorithm allows constant stretch routing with a network wide control traffic overhead of

O(n\log^2 n)

bits per mobility time step (time-scale of topology change) translating to

O(\log^2 n)

overhead per node (with high probability for wireless networks with such mobility model). Additionally, we can reduce the maximum overhead per node by using a load-balancing technique at the cost of a slightly higher average overhead. We also demonstrate through numerics that these worst-case bounds are quite conservative in terms of the constants derived theoretically.

2007

Chargement

In this thesis, we address two seemingly unrelated problems, namely routing in large wireless ad hoc networks and comparison based search in image databases. However, the underlying problem is in essence similar and we can use the same strategy to attack those two problems. In both cases, the intrinsic complexity of the problem is in some sense low, and we can exploit this fact to design efficient algorithms. A wireless ad hoc network is a communication network consisting of wireless devices such as for instance laptops or cell phones. The network does not have any fixed infrastructure, and hence nodes which cannot communicate directly over the wireless medium must use intermediate nodes as relays. This immediately raises the question of how to select the relay nodes. Ideally, one would like to find a path from the source to the destination which is as short as possible. The length of the found path, also called route, typically depends on how much signaling traffic is generated in order to establish the route. This is the fundamental trade-off that we will investigate in this thesis. As mentioned above, we try and exploit the fact that the communication network is intrinsically low-dimensional, or in other words has low complexity. We show that this is indeed the case for a large class of models and that we can design efficient algorithms for routing that use this property. Low dimensionality implies that we can well embed the network in a low-dimensional space, or build simple hierarchical decompositions of the network. We use both those techniques to design routing algorithms. Comparison based search in image databases is a new problem that can be defined as follows. Given a large database of images, can a human user retrieve an image which he has in mind, or at least an image similar to that image, without going sequentially through all images? More precisely, we ask whether we can search a database of images only by making comparisons between images. As a case in point, we ask whether we can find a query image q only by asking questions of the type "does image q look more like image A or image B"? The analogous to signaling traffic for wireless networks would here be the questions we can ask human users in a learning phase anterior to the search. In other words, we would like to ask as few questions as possible to pre-process and prepare the database, while guaranteeing a certain quality of the results obtained in the search phase. As the underlying image space is not necessarily metric, this raises new questions on how to search spaces for which only rank information can be obtained. The rank of A with respect to B is k, if A is B's kth nearest neighbor. In this setup, low-dimensionality is analogous to the homogeneity of the image space. As we will see, the homogeneity can be captured by properties of the rank relationships. In turn, homogeneous spaces can be well decomposed hierarchically using comparisons. Further, it allows us to design good hash functions. To design efficient algorithms for these two problems, we can apply the same techniques mutatis mutandis. In both cases, we relied on the intuition that the problem has a low intrinsic complexity, and that we can exploit this fact. Our results come in the form of simulation results and asymptotic bounds.

EPFL2010

Chargement

Hierarchical Routing over Dynamic Wireless Networks

Suhas Diggavi, Matthias Grossglauser, Dominique Florian Tschopp

O(n\log^2 n)

bits per mobility time step (time-scale of topology change) translating to

O(\log^2 n)

2007

EPFL2010