Succinct and practical greedy embedding for geometric routing

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.