Locally restorable routing of highly variable traffic

ABSTRACT

Two-phase routing, where traffic is first distributed to intermediate nodes before being routed to the final destination, has been recently proposed for handling widely fluctuating traffic without the need to adapt network routing to changing traffic. Preconfiguring the network in a traffic independent manner using two-phase routing simplifies network operation considerably.

In this paper, we extend this routing scheme by providing resiliency against link failures through fast restoration along link backup detours. We view this as important progress towards adding carrier-class reliability to the robustness of the scheme so as to facilitate its future deployment in Internet Service Provider (ISP) networks. On the theoretical side, the main contribution of the paper is the development of linear programming based and fast combinatorial algorithms for two-phase routing with link restoration so as to minimize the maximum utilization of any link in the network, or equivalently, maximize the throughput. The algorithms developed are Fully Polynomial Time Approximation Schemes (FPTAS)--for any given Ɛ > 0, an FPTAS guarantees a solution that is within a (1 + Ɛ)-factor of the optimum and runs in time polynomial in the input size and 1/Ɛ. To the best of our knowledge, this is the first work in the literature that considers making the scheme resilient to link failures through preprovisioned fast restoration mechanisms. We evaluate the performance of link restoration (in terms of throughput) and compare it with that of unprotected routing. For our experiments, we use actual ISP network topologies collected for the Rocketfuel project and three research network topologies.

REFERENCES

• 1: Ravindra K. Ahuja , Thomas L. Magnanti , James B. Orlin, Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 2: David Applegate , Lee Breslau , Edith Cohen, Coping with network failures: routing strategies for optimal demand oblivious restoration, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 3: David Applegate , Edith Cohen, Making intra-domain routing robust to changing and uncertain traffic demands: understanding fundamental tradeoffs, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863991]
• 4: Ramesh Bhandari, Survivable Networks: Algorithms for Diverse Routing, Kluwer Academic Publishers, Norwell, MA, 1998
• 5: Configuring OSPF. Cisco Systems Product Documentation. [Online]. Available: http://www.cisco.com/univercd/home/home.htm
• 6: N. G. Duffield , Pawan Goyal , Albert Greenberg , Partho Mishra , K. K. Ramakrishnan , Jacobus E. van der Merive, A flexible model for resource management in virtual private networks, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.95-108, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 7: J. Andrew Fingerhut , Subhash Suri , Jonathan S. Turner, Designing least-cost nonblocking broadband networks, Journal of Algorithms, v.24 n.2, p.287-309, Aug. 1997 [doi>10.1006/jagm.1997.0866]
• 8: Naveen Garg , Jochen Koenemann, Faster and Simpler Algorithms for Multicommodity Flow and other Fractional Packing Problems., Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.300, November 08-11, 1998
• 9: Amit Kumar , Rajeev Rastogi , Avi Silberschatz , Bulent Yener, Algorithms for provisioning virtual private networks in the hose model, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.135-146, August 2001, San Diego, California, United States
• 10: M. Kodialam, T. V. Lakshman, and S. Sengupta, "Efficient and robust routing of highly variable traffic," presented at the 3rd Workshop on Hot Topics in Networks (HotNets-III), San Diego, CA, Nov. 2004.
• 11: M. Kodialam, T. V. Lakshman, and S. Sengupta, "A versatile scheme for routing highly variable traffic in service overlays and IP backbones," in Proc. IEEE INFOCOM 2006, Barcelona, Spain, Apr. 2006, online.
• 12: M. Kodialam, T. V. Lakshman, J. B. Orlin, and S. Sengupta, "Preconfiguring IP-over-optical networks to handle router failures and unpredictable traffic," IEEE J. Sel. Areas Commun., Special Issue on Traffic Engineering for Multi-Layer Networks, vol. 25, no. 5, pp. 934-948, Jun. 2007.
• 13: Neil Spring , Ratul Mahajan , David Wetherall , Thomas Anderson, Measuring ISP topologies with rocketfuel, IEEE/ACM Transactions on Networking (TON), v.12 n.1, p.2-16, February 2004 [doi>10.1109/TNET.2003.822655]
• 14: A. Medina , N. Taft , K. Salamatian , S. Bhattacharyya , C. Diot, Traffic matrix estimation: existing techniques and new directions, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 15: S. Sengupta and R. Ramamurthy, "From network design to dynamic provisioning and restoration in optical cross-connect mesh networks: An architectural and algorithmic overview," IEEE Network, vol. 15, no. 4, pp. 46-54, Jul./Aug. 2001.
• 16: Ion Stoica , Daniel Adkins , Shelley Zhuang , Scott Shenker , Sonesh Surana, Internet indirection infrastructure, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 17: L. G. Valiant, "A scheme for fast parallel communication," SIAM J. Comput., vol. 11, no. 7, pp. 350-361, 1982.
• 18: R. Zhang-Shen and N. McKeown, "Designing a predictable internet backbone network," presented at the 3rd Workshop on Hot Topics in Networks (HotNets-III), San Diego, CA, Nov. 2004.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Spline and piecewise polynomial approximation
      G.1.6 Optimization
          Subjects: Linear programming

General Terms:
Algorithms, Design, Performance

Keywords:
fast restoration, hose traffic model, link restoration, oblivious routing, two-phase routing, valiant load balancing, variable traffic