Greedy Routing on Virtual Raw Anchor Coordinate (VRAC) System

Geographic routing is an appealing routing strategythat uses the location information of the nodes to route the data. This technique uses only local information of the communicationgraph topology and does not require computational effort tobuild routing table or equivalent data structures. A particularlyefficient implementation of this paradigm is greedy routing, where along the data path the nodes forward the data to aneighboring node that is closer to the destination. The decreasingdistance to the destination implies the success of the routingscheme. A related problem is to consider an abstract graphand decide whether there exists an embedding of the graph ina metric space, called a greedy embedding, such that greedyrouting guarantees the delivery of the data. A common approachto assign geographic coordinates is to measure distances (forinstance the distances between neighboring nodes) and compute(virtual) coordinates. The rationale of the Virtual raw Anchor Coordinate System(VRAC) is to use the (raw) measured distances as coordinates inorder to avoid further computations. More precisely, each nodeneeds to measure three distances. In this paper, we investigatethe existence of greedy routing in the VRAC coordinate systemusing a metric free characterization of greedy paths that is moregeneral than in previous works. We show that if the graph issaturated (see definition in the text) then the greedy algorithmguarantees delivery. Interestingly, the approach of greedinesshere applies to Schnyder drawings of planar triangulations. Indeed, by choosing the measured distances appropriately Schnyderdrawings of planar triangulations are always saturated and henceour greedy routing algorithm succeeds. The VRAC coordinates have conditions to satisfy to makegreedy routing successful. These conditions can be inferred fromgeometric considerations. However, we formulate these conditionsin an abstract way in order to avoid geometric considerationsand in order to make possible further derivation of virtualVRAC coordinate systems, i.e. using only the abstract graphdescription. In particular using only local information would leadto distributed algorithm.