Boston University Libraries OpenBU
    JavaScript is disabled for your browser. Some features of this site may not work without it.
    View Item 
    •   OpenBU
    • Theses & Dissertations
    • Boston University Theses & Dissertations
    • View Item
    •   OpenBU
    • Theses & Dissertations
    • Boston University Theses & Dissertations
    • View Item

    Graph embeddings for low-stretch greedy routing

    Thumbnail
    Date Issued
    2013
    Author(s)
    Cvetkovski, Andrej
    Share to FacebookShare to TwitterShare by Email
    Export Citation
    Download to BibTex
    Download to EndNote/RefMan (RIS)
    Metadata
    Show full item record
    Permanent Link
    https://hdl.handle.net/2144/14117
    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.
    Collections
    • Boston University Theses & Dissertations [6915]


    Boston University
    Contact Us | Send Feedback | Help
     

     

    Browse

    All of OpenBUCommunities & CollectionsIssue DateAuthorsTitlesSubjectsThis CollectionIssue DateAuthorsTitlesSubjects

    Deposit Materials

    LoginNon-BU Registration

    Statistics

    Most Popular ItemsStatistics by CountryMost Popular Authors

    Boston University
    Contact Us | Send Feedback | Help