Faculté informatique et communications IC, Section des systèmes de communication, Institut de systèmes de communication ISC (Laboratoire de communications audiovisuelles 1 LCAV1)

Anypath routing

Dubois-Ferriere, Henri ; Vetterli, Martin (Dir.) ; Grossglausser, Matthias (Dir.)

Thèse sciences Ecole polytechnique fédérale de Lausanne EPFL : 2006 ; no 3636.

Ajouter à la liste personnelle
    Summary
    In many networks, it is less costly to transmit a packet to any node in a set of neighbors than to one specific neighbor. A well-known instance is with unreliable wireless links, where the probability that at least one node out ofnreceives a packet increases with n. This observation was previously exploited, by modifying single-path routing to assign to each node group of candidate next-hops for a particular destination. However, single-path metrics not do reflect the cost of forwarding when a sender has multiple candidate relays, and they result in routing decisions that are in many cases suboptimal. This dissertation addresses the shortest anypath routing problem: how to assign a set of candidate relays at each node for a given destination, such that the cost of forwarding a packet to the destination is minimized. The key is the following tradeoff: on the one hand, increasing the number of candidate relays decreases the forwarding cost, but on the other, this increases the likelihood of "veering" away from the most direct trajectory. Solving the shortest anypath problem requires us first to formalize the notions of anycast link cost and remaining path cost, that generalize the link cost and path cost of single-path routing. Unlike with single-path routing, a packet can travel across an anypath route in many different ways; the cost of this route is naturally defined as the expected cost of all possible traversals. We introduce an algorithm that provably computes the shortest anypath route between each node and a destination. It is based on the Bellman-Ford algorithm and so is amenable to implementation in a distributed setting. This algorithm works for all physical cost metrics; we show that there exist certain "non-physical" cost metrics under which the shortest anypath route may contain cycles. We also explore the interaction between the relay selection policy, that is, the way in which the effective relay is chosen among many receivers, and the cost of optimal routes. We also explore the robustness of anypath routes, and find that they are significantly more stable in the face of topology changes and imperfect information than are single-path and multipath routes. The principles of anypath routing are general and can be applied in many settings. Our application focus in this dissertation is on low-power, low-rate wireless communication in embedded wireless networks. We introduce novel ways in which low-power link-layers can take advantage of anycast forwarding to reduce transmission energy or latency. We describe the design and implementation of a complete anypath routing protocol; evaluation on a 50-node wireless testbed demonstrates that anypath routing is robust, stable, and increases energy efficiency of low-power nodes by a significant factor over the equivalent system using single-path routing. Finally, we describe a novel error-correctionmechanism for multi-hop wireless communication based on packet combining. Packet combining allows to exploit corrupt packets received at different nodes by jointly decoding independent, noisy versions of an original packet.
    Résumé
    Dans un réseau de communication, il est souvent moins coûteux de transmettre un paquet à n'importe quel noeud parmi un ensemble de voisins qu'à un voisin spécifique. Un exemple bien connu survient avec des liens non fiables, ou la probabilité qu'un noeud parmi n reçoive le paquet augmente avec n. Cette observation fut précédemment exploitée, en modifiant le routage à chemin unique afin d'assigner à chaque noeud un ensemble de relais candidats pour une destination donnée. Cependant, le coût d'un chemin unique ne reflète pas le coût de transmission avec plusieurs candidats, et par conséquent le choix de routes résultant n'est souvent pas optimal. Cette thèse a pour sujet le problème du plus court routage anypath. Il s'agit de désigner les relais candidats à chaque noeud de manière à ce que le coût total de transmission d'un paquet jusqu'à sa destination soit minimisé. La clef est d'équilibrer au mieux la tension suivante: d'un côté, le coût de transmission décroît lorsque l'on augmente le nombre de relais candidat; de l'autre la probabilité de s'écarter de la trajectoire directe est accrue. La résolution de ce problème nécessite en premier lieu de formaliser la notion de coût de transmission anycast, et de coût de chemin restant. Contrairement aux routes à chemin unique, les routes anypath peuvent acheminer un paquet par plusieurs chemins différents; le coût d'une route anypath est donc naturellement défini comme le coût moyen de tous ses chemins. Nous introduisons un algorithme qui calcule les routes anypath les plus courtes entre chaque source et une destination. L'algorithme est basé sur celui de Bellman-Ford et peut aisément être implémenté dans un contexte distribué. Il fonctionne pour tout modèle de coût physique; nous montrons qu'il existe certains modèles de coûts non-physiques avec lesquels la plus courte route anypath peut contenir des cycles. Nous explorons aussi la robustesse des routes anypath, et nous trouvons qu'elles sont plus stables face aux changements de topologie que ne le sont les routes à chemin unique. Les principes du routage anypath sont généraux et peuvent s'appliquer à de nombreux contextes. Cette thèse a pour domaine d'application principal la communication à basse consommation et à faibles débits dans les réseaux sans-fil embarqués. Nous introduisons de nouveaux mécanismes de transmission anycast afin de réduire soit le délai, soit le coût énergétique de transmission. Nous décrivons le design et l'implémentation d'un protocole de routage anypath complet; une évaluation sur un lit de test montre que le routage anypath est robuste, stable, et diminue la consommation énergétique de noeuds à basse puissance d'un facteur significatif. Enfin, nous décrivons un nouveau mécanisme de correction d'erreurs pour la communication sans fil à sauts multiples, basé sur la combinaison de paquets. Ce mécanisme permet de tirer avantage de paquets corrompus reçus par différents noeuds en décodant conjointement plusieurs copies indépendamment bruitées d'un paquet.