Paper Info
Title
Sufficient conditions for protection routing in IP networks.
Abstract
Providing fully distributed, fault tolerant, hop-by-hop routing is one of the key challenges for intra-domain IP networks. This can be achieved by storing two next-hops for each destination node in the forwarding table of the routers, and the packets are forwarded to primary next-hop (PNH), unless PNH is unreachable and secondary next-hop (SNH) is used instead. We follow the architecture by Kwong et al. in On the feasibility and efficacy of protection routing in IP networks, University of Pennsylvania (2010), where the routing tables are configured in a centralized way, while the forwarding and failure recovery is in a fully distributed way without relying on any encapsulation and signaling mechanisms for failure notification, to meet the standard IP forwarding paradigm. A network is protected if no single link of node failure results in forwarding loops. Kwong et al. (On the feasibility and efficacy of protection routing in IP networks, University of Pennsylvania 2010) conjectured that network node connectivity is not sufficient for a network to be protectable. In this paper we show that this conjecture is in contradiction with a conjuncture by Hasunuma (Discrete Math 234(1–3):149–157, 2001; in Graph-Theoretic Concepts in Computer Science, Springer, Berlin, pp. 235–245, 2002), and show that every four connected maximal planar graph and every underlying graph of a 2-connected line digraph has feasible protection routing.
Year
DOI
Venue
2013
10.1007/s11590-012-0455-y
Optimization Letters
Keywords
Field
DocType
IP Fast ReRoute (IPFRR), Node-connectivity
Dynamic Source Routing,Triangular routing,Static routing,Computer science,Computer network,Loose Source Routing,Routing table,IP forwarding,Virtual routing and forwarding,Routing protocol,Distributed computing
Journal
Volume
Issue
ISSN
7
4
1862-4480
Citations 
PageRank 
References 
2
0.36
5
Authors
1
Name
Order
Citations
PageRank
János Tapolcai136441.42