Graph Embeddings for Low-Stretch Greedy Routing: Andrej Cvetkovski, PhD Proposal

Starts:
9:30 am on Wednesday, December 12, 2012
Ends:
11:00 am on Wednesday, December 12, 2012
Location:
MCS 148
Abstract Notable advantages of the simplest greedy routing scheme are its low complexity, and the use of local information only. However, two problems of greedy routing are that (1) it is not guaranteed to succeed for every source-destination pair, and (2) the routes it finds may take more hops than the corresponding shortest paths. Additionally, in dynamic multihop packet-switching communication 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 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 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 distance 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, as demonstrated by our numerical evaluation, 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. Examination Committee Prof. Azer Bestavros Prof. John Byers Prof. Mark Crovella (major advisor)