Permutation Routing for Increased Robustness in IP Networks

详细信息    查看全文

• 作者：Hung Quoc Vo (1) vqhung@simula.no
  Olav Lysne (1) olav.lysne@simula.no
  Amund Kvalbein (1) amundk@simula.no
• 关键词：IP networks – ; Multipath Routing – ; Resilience – ; Fault ; tolerant
• 刊名：Lecture Notes in Computer Science
• 出版年：2012
• 出版时间：2012
• 年：2012
• 卷：7289
• 期：1
• 页码：217-231
• 全文大小：1,011.9 KB
• 参考文献：1. Garcia-Lunes-Aceves, J.J.: Loop-free routing using diffusing computations. IEEE Trans. on Networking 1(1), 130–141 (1993)
  2. Vutukury, S., Garcia-Luna-Aceves, J.J.: MDVA: A Distance-Vector Multipath Routing Protocol. In: IEEE INFOCOM, pp. 557–564 (2001)
  3. Nelakuditi, S., Lee, S., Yu, Y., Zhang, Z.-L., Chuah, C.-N.: Fast local rerouting for handling transient link failures. IEEE Trans. on Networking 15, 359–372 (2007)
  4. Atlas, A., Zinin, A.: RFC5286: Basic Specification for IP Fast Reroute: Loop-Free Alternates (September 2008)
  5. Shand, M., Bryant, S., Previdi, S.: IP Fast Reroute Using Not-via Addresses. Internet-Draft (work in progress, expired in June 2012)
  6. Kvalbein, A., Hansen, A.F., Čičic, T., Gjessing, S., Lysne, O.: Multiple routing configurations for fast IP network recovery. IEEE Trans. on Networking 17(2) (2009)
  7. Elhourani, T., Ramasubramanian, S., Kvalbein, A.: Enhancing Shortest Path Routing for Resilience and Load Balancing. In: ICC, pp. 1–6 (2011)
  8. Francois, P., Bryant, S., Decraene, B., Horneffer, M.: LFA applicability in SP networks. Internet-Draft (work in progress, expired in July 2012)
  9. Nakano, K., Olariu, S., Zomaya, A.Y.: Energy-efficient permutation routing in radio networks. IEEE Trans. on Parallel and Distributed Systems 12(6) (2001)
  10. Liang, X., Shen, X.: Permutation Routing in All-Optical Product Networks. IEEE Trans. on Circuits and Systems 49(4), 533–538 (2002)
  11. Xu, D., Chiang, M., Rexford, J.: DEFT: Distributed Exponentially-Weighted Flow Splitting. In: IEEE INFOCOM, pp. 71–79 (2007)
  12. Kvalbein, A., Dovrolis, C., Muthu, C.: Multipath load-adaptive routing: putting the emphasis on robustness and simplicity. In: IEEE ICNP, pp. 203–212 (2009)
  13. Cormen, T. H., et al.: Introduction to Algorithms. MIT Press, ISBN 0-262-03293-7
  14. Kwong, K.-W., Gao, L., Gurin, R., Zhang, Z.-L.: On the feasibility and efficacy of protection routing in IP networks. In: IEEE INFOCOM, pp. 1543–1556 (2010)
  15. Fortz, B., Thorup, M.: Internet traffic engineering by optimizing OSPF weights. In: IEEE INFOCOM, pp. 519–528 (2000)
  16. Schollmeier, G., Charzinski, J., Kirstadter, A.: Improving the resilience in IP networks. In: HPSR Workshop, pp. 91–96 (2003)
  17. Ohara, Y., Imahori, S., Meter, R.V.: MARA: Maximum Alternative Routing Algorithm. In: IEEE INFOCOM, pp. 298–306 (2009)
  18. Nccui, A., Bhattacharyya, S., Taft, N., Diot, C.: IGP link weight assignment for operational Tier-1 backbones. IEEE Trans. on Networking 15, 789–802 (2007)
  19. Rocketfuel topology mapping. WWW, http://www.cs.washington.edu
• 作者单位：1. Simula Research Laboratory, Norway
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

We present Permutation Routing as a method for increased robustness in IP networks with traditional hop-by-hop forwarding. Permutation Routing treats routers involved in traffic forwarding as a sequence of resources, and creates permutations of these resources that give several forwarding options. We introduce Permutation Routing as a concept, and use it to create routings where we seek to maximize single link fault coverage. Analogous to the IETF standardized Loop-Free Alternate (LFA), Permutation Routing can easily be implemented for OSPF or IS-IS networks to augment existing ECMP forwarding with additional loop-free forwarding entries for improved load balancing or fault tolerance. Our evaluations show that Permutation Routing can increase single link fault coverage by up to 28% compared to LFA in inferred network topologies.