Paper Info
Title
Succinct and practical greedy embedding for geometric routing.
Abstract
The scalability challenge of geometric routing is to construct succinct coordinates for all nodes in the network. This paper presents SPrefix-B, a practical greedy embedding scheme with succinct coordinates, low path stretches and 100% routing success. In comparison to theoretical schemes with near-optimal succinctness, SPrefix-B is simple and easy to implement without requiring the whole topology and works well in both weighted and unweighted graphs. In contrast to practical schemes, SPrefix-B is more succinct and universal. It provides O(log2(n))-bit coordinates for arbitrary graphs. This paper first proposes Prefix-B which adopts a bit-string prefix tree as a metric space and provides succinct embedding for some power law graphs. Furthermore, to extend the succinctness to arbitrary graphs, SPrefix-B is proposed by applying two optimizations, the compressed path decomposition and the compressed embedding, to Prefix-B. The theoretical analyses and experimental results show that SPrefix-B not only guarantees greediness, but also provides succinctness and low path stretches.
Year
DOI
Venue
2017
10.1016/j.comcom.2017.10.014
Computer Communications
Keywords
Field
DocType
Scalable routing,Geometric routing,Embedding,Succinctness,Greediness
Embedding,Succinctness,Computer science,Theoretical computer science,Prefix,Wavelet Tree,Metric space,Trie,Scalability,Greedy embedding
Journal
Volume
Issue
ISSN
114
C
0140-3664
Citations 
PageRank 
References 
0
0.34
22
Authors
4
Name
Order
Citations
PageRank
sun yanbin121.38
Yu Zhang218831.14
Binxing Fang338088.26
Hongli Zhang4126.32