REPLEX: dynamic traffic engineering based on wardrop routing policies

ABSTRACT

One major challenge in communication networks is the problem of dynamically distributing load in the presence of bursty and hard to predict changes in traffic demands. Current traffic engineering operates on time scales of several hours which is too slow to react to phenomena like flash crowds or BGP reroutes. One possible solution is to use load sensitive routing. Yet, interacting routing decisions at short time scales can lead to oscillations, which has prevented load sensitive routing from being deployed since the early experiences in Arpanet.

However, recent theoretical results have devised a game theoretical re-routing policy that provably avoids such oscillation and in addition can be shown to converge quickly. In this paper we present ReplEx, a distributed dynamic traffic engineering algorithm based on this policy. Exploiting the fact that most underlying routing protocols support multiple equal-cost routes to a destination, it dynamically changes the proportion of traffic that is routed along each path. These proportions are carefully adapted utilising information from periodic measurements and, optionally, information exchanged between the routers about the traffic condition along the path.

We evaluate the algorithm via simulations employing traffic loads that mimic actual Web traffic, i. e., bursty TCP traffic, and whose characteristics are consistent with self-similarity. The simulations quickly converge and do not exhibit significant oscillations on both artificial as well as real topologies, as can be expected from the theoretical results.

REFERENCES

• 1: 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]
• 2: Baruch Awerbuch , Robert D. Kleinberg, Adaptive routing with end-to-end feedback: distributed learning and geometric approaches, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007367]
• 3: Paul Barford , Mark Crovella, Generating representative Web workloads for network and server performance evaluation, Proceedings of the 1998 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.151-160, June 22-26, 1998, Madison, Wisconsin, United States
• 4: M. Beckmann, C. B. McGuire, and C. B. Winsten. Studies in the Economics and Transportation. Yale University Press, 1956.
• 5: Petra Berenbrink , Tom Friedetzky , Leslie Ann Goldberg , Paul Goldberg , Zengjian Hu , Russell Martin, Distributed selfish load balancing, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.354-363, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109597]
• 6: A. Blum, E. Even-Dar, and K. Ligett. Routing without regret, 2005. Manuscript.
• 7: Z. Cao, Z. Wang, and E. W. Zegura. Performance of hashing-based schemes for Internet load balancing. In Proc. IEEE INFOCOM Conference, 2000.
• 8: Holger Dreger , Anja Feldmann , Michael Mai , Vern Paxson , Robin Sommer, Dynamic application-layer protocol analysis for network intrusion detection, Proceedings of the 15th conference on USENIX Security Symposium, p.18-18, July 31-August 04, 2006, Vancouver, B.C., Canada
• 9: A. Elwalid, C. Jin, S. Low, and I. Widjaja. MATE: MPLS adaptive traffic engineering. In Proc. IEEE INFOCOM Conference, 2001.
• 10: Eyal Even-Dar , Yishay Mansour, Fast convergence of selfish rerouting, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 11: Anja Feldmann , Anna C. Gilbert , Polly Huang , Walter Willinger, Dynamics of IP traffic: a study of the role of variability and the impact of control, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.301-313, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 12: A. Feldmann, A. Greenberg, C. Lund, N. Reingold, and J. Rexford. NetScope: Traffic engineering for IP networks. IEEE Network Magazine, 2000.
• 13: Simon Fischer , Harald Räcke , Berthold Vöcking, Fast convergence to Wardrop equilibria by adaptive sampling methods, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132608]
• 14: S. Fischer and B. Vöcking. On the evolution of selfish routing. In S. Albers and T. Radzik, editors, Proc. 12th Ann. European Symp. on Algorithms (ESA), number 3221 in Lecture Notes in Comput. Sci., Bergen, Norway, September 2004. Springer-Verlag.
• 15: Simon Fischer , Berthold Vöcking, Adaptive routing with stale information, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073868]
• 16: B. Fortz, J. Rexford, and M. Thorup. Traffic engineering with traditional IP routing protocols. In IEEE Communication Magazine, 2002.
• 17: B. Fortz and M. Thorup. Internet traffic engineering by optimizing OSPF weights. In Proc. IEEE INFOCOM Conference, 2000.
• 18: B. Fortz and M. Thorup. Optimizing OSPF/IS-IS weights in a changing world. In IEEE Journal on Selected Areas in Communications, Vol. 20, No. 4, 2002.
• 19: W. Hao and R. Ito. Dynamics of load-sensitive adaptive routing. In Proc. IEEE International Conference on Communications (ICC), 2005.
• 20: J.-Y. Jo, Y. Kim, H. J. Chao, and F. Merat. Internet traffic load balancing using dynamic hashing with flow volume. In Proc. SPIE ITCom, 2002.
• 21: Srikanth Kandula , Dina Katabi , Bruce Davie , Anna Charny, Walking the tightrope: responsive yet stable traffic engineering, Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, August 22-26, 2005, Philadelphia, Pennsylvania, USA
• 22: D. Katz , K. Kompella , D. Yeung, Traffic Engineering (TE) Extensions to OSPF Version 2, RFC Editor, 2003
• 23: A. Khanna , J. Zinky, The revised ARPANET routing metric, Symposium proceedings on Communications architectures & protocols, p.45-56, September 25-27, 1989, Austin, Texas, United States
• 24: T. Krämer. IP traffic engineering---OSPF vs. MPLS. Master's thesis, Universität des Saarlandes, 2003.
• 25: B. Krishnamurthy and J. Rexford. Web Protocols and Practice. Addison-Wesley, 2001.
• 26: M. Laor and L. Gendel. The effect of packet reordering in a backbone link on application throughput. IEEE Network, September/October 2002.
• 27: Y. Liu and A. L. N. Reddy. Multihoming route control among a group of multihomed stub networks. Technical Report TAMU-ECE-2006-01, 2006.
• 28: Kihong Park , Walter Willinger, Self-Similar Network Traffic and Performance Evaluation, John Wiley & Sons, Inc., New York, NY, 2000
• 29: C. Pelsser, S. Uhlig, and O. Bonaventure. On the difficulty of establishing interdomain LSPs. In IEEE IPOM, 2004.
• 30: J. Postel et al. RFC 793, September 1981. http://www.ietf.org/rfc/rfc793.txt.
• 31: V. Raghunathan and P. R. Kumar. A Wardrop routing protocol for ad hoc wireless networks. In IEEE CDC, 2004.
• 32: Vivek Raghunathan , P. R. Kumar, Issues in Wardrop Routing in Wireless Networks, Proceedings of the First International Conference on Wireless Internet, p.34-41, July 10-15, 2005 [doi>10.1109/WICON.2005.18]
• 33: Renesys. The SSFNet network simulator. http://www.ssfnet.org/.
• 34: Matthew Roughan , Mikkel Thorup , Yin Zhang, Traffic engineering with estimated traffic matrices, Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, October 27-29, 2003, Miami Beach, FL, USA [doi>10.1145/948205.948237]
• 35: Tim Roughgarden , Éva Tardos, How bad is selfish routing?, Journal of the ACM (JACM), v.49 n.2, p.236-259, March 2002 [doi>10.1145/506147.506153]
• 36: N. Skrypnyuk. Load-sensitive routing. Master's thesis. TU München, 2006.
• 37: Neil Spring , Ratul Mahajan , David Wetherall, Measuring ISP topologies with rocketfuel, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 38: A. Sridharan, R. Guérin, and C. Diot. Achieving near-optimal traffic engineering solutions for current OSPF/IS-IS networks. In Proc. IEEE INFOCOM Conference, 2003.
• 39: Renata Teixeira , Geoffrey M. Voelker, Network sensitivity to intradomain routing changes, University of California at San Diego, La Jolla, CA, 2005
• 40: R. Teixeira, N. Duffield, J. Rexford, and M. Roughan. Traffic matrix reloaded: Impact of routing changes. In Proc. Passive and Active Measurement, 2005.
• 41: TOTEM---TOolbox for Traffic Engineering Methods. http://totem.run.montefiore.ulg.ac.be/.
• 42: C. Vollmert. A Web workload generator for the SSFNet network simulator. Bachelor's thesis, Technische Universität München, 2004.
• 43: J. Wallerich. Design and implementation of a WWW workload generator for the ns-2 network simulator. Master's thesis, Universität des Saarlandes, 2001.
• 44: Jörg Wallerich , Holger Dreger , Anja Feldmann , Balachander Krishnamurthy , Walter Willinger, A methodology for studying persistency aspects of internet flows, ACM SIGCOMM Computer Communication Review, v.35 n.2, April 2005 [doi>10.1145/1064413.1064417]
• 45: Hao Wang , Haiyong Xie , Lili Qiu , Yang Richard Yang , Yin Zhang , Albert Greenberg, COPE: traffic engineering in dynamic networks, Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, September 11-15, 2006, Pisa, Italy
• 46: J. G. Wardrop. Some theoretical aspects of road traffic research. In Proc. of the Institute of Civil Engineers, Pt. II, 1952.
• 47: X. Xiao, A. Hannan, B. Bailey, and L. Ni. Traffic engineering with MPLS in the Internet. In IEEE Network Magazine, March 2000.
• 48: Wen Xu , Jennifer Rexford, MIRO: multi-path interdomain routing, Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, September 11-15, 2006, Pisa, Italy
• 49: Chun Zhanga , Jim Kurosea , Don Towsley , Zihui Ge , Yong Liu, Optimal Routing with Multiple Traffic Matrices Tradeoff between Average andWorst Case Performance, Proceedings of the 13TH IEEE International Conference on Network Protocols, p.215-224, November 06-09, 2005 [doi>10.1109/ICNP.2005.30]
• 50: Yin Zhang , Matthew Roughan , Carsten Lund , David Donoho, An information-theoretic approach to traffic matrix estimation, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863990]

INDEX TERMS

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

General Terms:
Design, Experimentation, Measurement, Performance, Reliability

Keywords:
convergence time, dynamic routing, load balancing, real-time adaptive multipath routing, traffic engineering, wardrop equilibria