Oblivious routing of highly variable traffic in service overlays and IP backbones

ABSTRACT

The emergence of new applications on the Internet like voice-over-IP, peer-to-peer, and video-on-demand has created highly dynamic and changing traffic patterns. In order to route such traffic with quality-of-service (QoS) guarantees without requiring detection of traffic changes in real-time or reconfiguring the network in response to it, a routing and bandwidth allocation scheme has been recently proposed that allows preconfiguration of the network such that all traffic patterns permissible within the network's natural ingress-egress capacity constraints can be handled in a capacity efficient manner. The scheme routes traffic in two phases. In the first phase, incoming traffic is sent from the source to a set of intermediate nodes and then, in the second phase, from the intermediate nodes to the final destination. The traffic in the first phase is distributed to the intermediate nodes in predetermined proportions that depend on the intermediate nodes. In this paper, we develop linear programming formulations and a fast combinatorial algorithm for routing under the scheme so as to maximize throughput (or, minimize maximum link utilization). We compare the throughput performance of the scheme with that of the optimal scheme among the class of all schemes that are allowed to even make the routing dependent on the traffic matrix. For our evaluations, we use actual Internet Service Provider topologies collected for the Rocketfuel project. We also bring out the versatility of the scheme in not only handling widely fluctuating traffic but also accommodating applicability to several widely differing networking scenarios, including i) economical Virtual Private Networks (VPNs); ii) supporting indirection in specialized service overlay models like Internet Indirection Infrastructure (i3); iii) adding QoS guarantees to services that require routing through a network-based middlebox; and iv) reducing IP layer transit traffic and handling extreme traffic variability in IP-over-optical networks without dynamic reconfiguration of the optical layer. The two desirable properties of supporting indirection in specialized service overlay models and static optical layer provisioning in IP-over-optical networks are not present in other approaches for routing variable traffic, such as direct source-destination routing along fixed paths.

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: Yossi Azar , Edith Cohen , Amos Fiat , Haim Kaplan , Harald Racke, Optimal oblivious routing in polynomial time, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780599]
• 3: Walid Ben-Ameur , Hervé Kerivin, Networks new economical virtual private, Communications of the ACM, v.46 n.6, p.69-73, June 2003 [doi>10.1145/777313.777314]
• 4: Configuring OSPF. Cisco Systems Product Documentation. [Online]. Available: http://www.cisco.com/univercd/home/home.htm
• 5: ILOG CPLEX. [Online]. Available: http://www.ilog.com
• 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: M. Kodialam, T. V. Lakshman, and S. Sengupta, "Efficient and robust routing of highly variable traffic," in Proc. 3rd Workshop on Hot Topics in Networks (HotNets-III), San Diego, CA, Nov. 2004, 6 pp.
• 10: M. Kodialam, T. V. Lakshman, J. B. Orlin, 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, 12 pp.
• 11: 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, Jun. 2007.
• 12: M. Kodialam, T. V. Lakshman, and S. Sengupta, "Maximum throughput routing of traffic in the hose model," in Proc. IEEE INFOCOM 2006, Barcelona, Spain, Apr. 2006, 11 pp.
• 13: M. Kodialam , T. Lakshman , Sudipta Sengupta, Throughput Guaranteed Restorable Routing Without Traffic Prediction, Proceedings of the Proceedings of the 2006 IEEE International Conference on Network Protocols, p.137-146, November 12-15, 2006 [doi>10.1109/ICNP.2006.320207]
• 14: 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
• 15: Craig Labovitz , Abha Ahuja , Farnam Jahanian, Experimental Study of Internet Stability and Backbone Failures, Proceedings of the Twenty-Ninth Annual International Symposium on Fault-Tolerant Computing, p.278, June 15-18, 1999
• 16: 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
• 17: E. Rosen , A. Viswanathan , R. Callon, Multiprotocol Label Switching Architecture, RFC Editor, 2001
• 18: Sundipta Sengupta, Efficient and robust routing of highly variable traffic, Massachusetts Institute of Technology, Cambridge, MA, 2006
• 19: S. Sengupta, D. Saha, and V. P. Kumar, "Switched optical backbone for cost-effective scalable core IP networks," IEEE Commun. Mag., vol. 41, no. 6, pp. 60-70, Jun. 2003.
• 20: Farhad Shahrokhi , D. W. Matula, The maximum concurrent flow problem, Journal of the ACM (JACM), v.37 n.2, p.318-334, April 1990 [doi>10.1145/77600.77620]
• 21: 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]
• 22: 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
• 23: D. Thaler and C. Hopps, "Multipath issues in unicast and multicast next-hop selection," RFC 2919.
• 24: L. G. Valiant, "A scheme for fast parallel communication," SIAM J. Comput., vol. 11, no. 7, pp. 350-361, 1982.
• 25: R. Zhang-Shen and N. McKeown, "Designing a predictable internet backbone network," in Proc. 3rd Workshop on Hot Topics in Networks (HotNets-III), San Diego, CA, Nov. 2004, 6 pp.
• 26: R. Zhang-Shen and N. McKeown, "Designing a predictable internet backbone with valiant load-balancing," in Proc. Int. Workshop on Quality of Service (IWQoS) 2005, Passau, Germany, Jun. 2005, pp. 178-192.

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.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

          Nouns: IP
      C.2.3 Network Operations
          Subjects: Network management
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

General Terms:
Algorithms, Design, Management, Performance

Keywords:
IP-over-optical, IP/MPLS, hose traffic model, oblivious routing, service overlays, two-phase routing, valiant load balancing, variable traffic