For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Efficient Geometric Routing in Large-Scale Complex Networks with Low-Cost Node Design
Sahel SAHHAF Wouter TAVERNIER Didier COLLE Mario PICKAVET Piet DEMEESTER
IEICE TRANSACTIONS on Communications
Publication Date: 2016/03/01
Online ISSN: 1745-1345
Type of Manuscript: PAPER
geometric routing, greedy forwarding, greedy embedding, spanning tree, large-scale topology, scale-free networks,
Full Text: PDF(1.6MB)>>
The growth of the size of the routing tables limits the scalability of the conventional IP routing. As scalable routing schemes for large-scale networks are highly demanded, this paper proposes and evaluates an efficient geometric routing scheme and related low-cost node design applicable to large-scale networks. The approach guarantees that greedy forwarding on derived coordinates will result in successful packet delivery to every destination in the network by relying on coordinates deduced from a spanning tree of the network. The efficiency of the proposed scheme is measured in terms of routing quality (stretch) and size of the coordinates. The cost of the proposed router is quantified in terms of area complexity of the hardware design and all the evaluations involve comparison with a state-of-the-art approach with virtual coordinates in the hyperbolic plane. Extensive simulations assess the proposal in large topologies consisting of up to 100K nodes. Experiments show that the scheme has stretch properties comparable to geometric routing in the hyperbolic plane, while enabling a more efficient hardware design, and scaling considerably better in terms of storage requirements for coordinate representation. These attractive properties make the scheme promising for routing in large networks.