Technical report
OA Policy
English

Succint greedy routing without metric on planar triangulations

Publication date

2015

Abstract

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?

Keywords

  • Greedy routing
  • Greedy embedding
  • Geographic routing

UNIGE research groups

Citation (ISO format)

LEONE, Pierre, SAMARASINGHE, Kasun. Succint greedy routing without metric on planar triangulations. 2015

Main files (1)

Report

Identifiers

  • PID : unige:55819
703views
305downloads

Technical informations

Creation

23/04/2015 10:11:00

First validation

23/04/2015 10:11:00

Update

14/03/2023 23:13:49

Status update

14/03/2023 23:13:48

Last indexation

31/10/2024 00:03:45
All rights reserved by Archive ouverte UNIGE and the University of Geneva
OpenAIRE Indexed & Validated