Space Lower Bounds for Low-Stretch Greedy Embeddings

Ioannis Caragiannis, Christos Kalaitzis

Abstract

Greedy (geometric) routing is an important paradigm for routing in communication networks. It uses an embedding of the nodes of the network into points of a metric space (e.g., ) equipped with a distance function (e.g., the Euclidean distance ℓ2) and uses as address of each node the coordinates of the corresponding point. The embedding has particular properties so that the routing decision for a packet is taken greedily based only on the addresses of the current node, its neighbors, and the destination node and the distances of the corresponding points. In this way, there is no need to keep routing tables at the nodes. Embeddings that allow for this functionality are called greedy embeddings. Even though greedy embeddings do exist for several metric spaces and distance functions, they usually result in paths of high stretch, i.e., significantly longer than the corresponding shortest paths.
BibTeX
@inproceedings{caragiannis2012space,
  author = {Ioannis Caragiannis and Christos Kalaitzis},
  title = {{Space Lower Bounds for Low-Stretch Greedy Embeddings}},
  booktitle = {SIROCCO},
  year = {2012},
  doi = {10.1007/978-3-642-31104-8\_1},
}

Loading related content...

Figure