Premium
Optimizing robustness in geometric routing via embedding redundancy and regeneration
Author(s) -
Houthooft Rein,
Sahhaf Sahel,
Tavernier Wouter,
De Turck Filip,
Colle Didier,
Pickavet Mario
Publication year - 2015
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21630
Subject(s) - computer science , robustness (evolution) , multipath routing , embedding , static routing , redundancy (engineering) , equal cost multi path routing , network topology , spanning tree , topology (electrical circuits) , distributed computing , routing (electronic design automation) , mathematical optimization , routing protocol , computer network , mathematics , artificial intelligence , biochemistry , combinatorics , chemistry , gene , operating system
Geometric routing is an alternative to traditional routing algorithms in which traffic is no longer forwarded using lookup tables, but using coordinates in an embedding of the underlying network. A major downside of current geometric routing algorithms is their inability to handle network failures in a graceful manner. Moreover, they cannot deal with dynamic graph topologies. This article presents a geometric routing scheme that uses an embedding based on a spanning forest. Allowing nodes to select the optimal spanning tree leads to both shorter paths and natural traffic redirection in case of network failures. By constructing the forest in such a way that its disconnected components have low redundancy, their coverage is maximized. Results show that this system is able to operate gracefully in severe failure scenarios, without any form of path protection or restoration. By means of an embedding regeneration procedure, the routing scheme is able to continuously adapt to an altering network topology. This geometric routing algorithm effectively combines two key objectives, namely low path stretch and high robustness. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 66(4), 320–334 2015