[Nrg-l] NRG Presentation: March/23/2009

Jorge Londoño jmlon at cs.bu.edu
Fri Mar 20 08:35:25 EDT 2009

*Speaker:* Andrej Cvetkovski

Hyperbolic Embedding and Routing for Dynamic Graphs
Andrej Cvetkovski and Mark Crovella

We propose an embedding and routing scheme for arbitrary network 
connectivity graphs, based on greedy routing and utilizing virtual node 
coordinates. In dynamic multihop packet-switching communication 
networks, routing elements can join or leave during network operation or 
exhibit intermittent failures. We present 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. Even a single link or node removal may invalidate 
the greedy routing success guarantees in network embeddings based on an 
embedded spanning tree sub- graph. 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 
rout- ing 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 

*Time and Place:*
4:00pm - Grad lounge

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://cs-mailman.bu.edu/pipermail/nrg-l/attachments/20090320/c75d5bdb/attachment.html 

More information about the Nrg-l mailing list