fr
Rapport technique
Accès libre
Anglais

Succint greedy routing without metric on planar triangulations

Contributeurs/tricesLeone, Pierre; Samarasinghe, Kasun
Date de publication2015
Résumé

Geographic routing is an appealing routing strategy that uses the location information of the nodes to route the data. This technique uses only local information of the communication graph topology and does not require computational effort to build routing table or equivalent data structures. A particularly efficient implementation of this paradigm is greedy routing, where along the data path the nodes forward the data to a neighboring node that is closer to the destination. The decreasing distance to the destination implies the success of the routing scheme. A related problem is to consider an abstract graph and decide whether there exists an embedding of the graph in a metric space, called a greedy embedding, such that greedy routing guarantees the delivery of the data. In the present paper, we use a metric-free definition of greedy path and we show that greedy routing is successful on planar triangulations without considering the existence of greedy embedding. Our algorithm rely entirely on the combinatorial description of the graph structure and the coordinate system requires O(log(n)) bits where n is the number of nodes in the graph. Previous works on greedy routing make use of the embedding to route the data. In particular, in our framework, it is known that there exists an embedding of planar triangulations such that greedy routing guarantees the delivery of data. The result presented in this article leads to the question whether the success of (any) greedy routing strategy is always coupled with the existence of a greedy embedding?

Mots-clés
  • Greedy routing
  • Greedy embedding
  • Geographic routing
Citation (format ISO)
LEONE, Pierre, SAMARASINGHE, Kasun. Succint greedy routing without metric on planar triangulations. 2015
Fichiers principaux (1)
Report
accessLevelPublic
Identifiants
  • PID : unige:55819
612vues
69téléchargements

Informations techniques

Création23/04/2015 10:11:00
Première validation23/04/2015 10:11:00
Heure de mise à jour14/03/2023 23:13:49
Changement de statut14/03/2023 23:13:48
Dernière indexation16/01/2024 17:51:48
All rights reserved by Archive ouverte UNIGE and the University of GenevaunigeBlack