Back to search

Boston University

Graph embeddings for low-stretch greedy routing

Abstract

dc:description.abstract

The simplest greedy geometric routing forwards packets to make most progress in terms of geometric distance within reach. Its notable advantages are low complexity, and the use of local information only. However, two problems of greedy routing are that delivery is not always guaranteed, and that the greedy routes may take more hops than the corresponding shortest paths. Additionally, in dynamic multihop networks, routing elements can join or leave during network operation or exhibit intermittent failures. Even a single link or node removal may invalidate the greedy routing success guarantees. Greedy embedding is a graph embedding that makes the simple greedy packet forwarding successful for every source-destination pair. In this dissertation, we consider the problems of designing greedy graph embeddings that also yield low hop stretch of the greedy paths over the shortest paths and can accommodate network dynamics. In the first part of the dissertation, we consider embedding and routing for arbitrary unweighted network graphs, based on greedy routing and utilizing virtual node coordinates. We propose an algorithm for online greedy graph embedding in the hyperbolic plane that enables incremental embedding of network nodes as they join the network, without disturbing the global embedding. As an alternative to frequent reembedding of temporally dynamic network graphs in order to retain the greedy embedding property, we propose a simple but robust generalization of greedy geometric routing called Gravity--Pressure (GP) routing. Our routing method always succeeds in finding a route to the destination provided that a path exists, even if a significant fraction of links or nodes is removed subsequent to the embedding. GP routing does not require precomputation or maintenance of special spanning subgraphs and is particularly suitable for operation in tandem with our proposed algorithm for online graph embedding. In the second part of the dissertation we study how topological and geometric properties of embedded graphs influence the hop stretch. Based on the obtained insights, we synthesize embedding heuristics that yield minimal hop stretch greedy embeddings. Finally, we verify their effectiveness on models of synthetic graphs as well as instances of several classes of real-world network graphs.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy
Level thesis:degree_level
doctoral
Discipline thesis:degree_discipline
Computer Science
Grantor
Boston University
Year dc:date.issued
2013

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Cvetkovski, Andrej

Subjects

dc:subject × 1

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/2144/14117

Chain of custody

source
Harvested from
Boston University
Base URL
open.bu.edu/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Cvetkovski, Andrej. Graph embeddings for low-stretch greedy routing. doctoral thesis, Boston University, 2013. https://hdl.handle.net/2144/14117