Skip to main content
SpringerLink
Log in

Sufficient conditions for protection routing in IP networks

  • Original Paper
  • Published:
Optimization Letters Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Atlas, A., Zinin, A.: Basic specification for IP fast reroute: loop-free alternates. RFC 5286 (2008)

  2. Hasunuma T.: Completely independent spanning trees in the underlying graph of a line digraph. Discrete Math. 234(1–3), 149–157 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  3. Hasunuma, T.: Completely independent spanning trees in maximal planar graphs. In: Graph-Theoretic Concepts in Computer Science, pp. 235–245. Springer, Berlin (2002)

  4. Kwong K. W., Gao L., Guerin R., Zhang Z. L.: On the feasibility and efficacy of protection routing in IP networks. IEEE/ACM Trans. Netw. 19(5), 1543–1556 (2011)

    Article  Google Scholar 

  5. Nash-Williams C.: Edge-disjoint spanning trees of finite graphs. J. Lond. Math. Soc. 1(1), 445 (1961)

    Article  MathSciNet  Google Scholar 

  6. Ohara, Y., Imahori, S., Van Meter, R.: Mara: maximum alternative routing algorithm. In: IEEE INFOCOM 2009, pp. 298–306 (2009)

  7. Oliveira C., Pardalos P.: Mathematical Aspects of Network Routing Optimization, vol. 53. Springer, Berlin (2011)

    Book  Google Scholar 

  8. Ray S., Guérin R., Kwong K., Sofia R.: Always acyclic distributed path computation. IEEE/ACM Trans. Netw. (ToN) 18(1), 307–319 (2010)

    Article  Google Scholar 

  9. Reichert, C., Glickmann, Y., Magedanz, T.: Two routing algorithms for failure protection in IP networks. In: IEEE Symposium on Computers and Communications (ISCC), pp. 97–102 (2005)

  10. Resende M., Pardalos P.: Handbook of Optimization in Telecommunications, vol. 10. Springer, Berlin (2006)

    Book  Google Scholar 

  11. Schollmeier, G., Charzinski, J., Kirstädter, A., Reichert, C., Schrodi, K., Glickman, Y., Winkler, C.: Improving the resilience in ip networks. In: Workshop on High Performance Switching and Routing (HPSR), IEEE, pp. 91–96 (2003)

Download references

Author information

Authors and Affiliations

  1. Department of Telecommunications and Media Informatics, Budapest University of Technology and Economics, Budapest, Hungary

    János Tapolcai

Authors
  1. János Tapolcai
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to János Tapolcai.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Tapolcai, J. Sufficient conditions for protection routing in IP networks. Optim Lett 7, 723–730 (2013). https://doi.org/10.1007/s11590-012-0455-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-012-0455-y

Keywords

Search

Navigation