User menu

Accès à distance ? S'identifier sur le proxy UCLouvain

Lying Your Way to Better Traffic Engineering

Primary tabs

Chiesa, Marco [UCL] Rétvári, Gábor Schapira, Michael

To optimize the flow of traffic in IP networks, operators do traffic engineering (TE), i.e., tune routing-protocol parameters in response to traffic demands. TE in IP networks typically involves configuring static link weights and splitting traffic between the resulting shortest-paths via the Equal-Cost-MultiPath (ECMP) mechanism. Unfortunately, ECMP is a notoriously cumbersome and indirect means for optimizing traffic flow, often leading to poor network performance. Also, obtaining accurate knowledge of traffic demands as the input to TE is elusive, and traffic conditions can be highly variable, further complicating TE. We leverage recently proposed schemes for increasing ECMP's expressiveness via carefully disseminated bogus information ("lies") to design COYOTE, a readily deployable TE scheme for robust and efficient network utilization. COYOTE leverages new algorithmic ideas to configure (static) traffic splitting ratios that are optimized with respect to all (even adversarially chosen) traffic scenarios within the operator's "uncertainty bounds". Our experimental analyses show that COYOTE significantly outperforms today's prevalent TE schemes in a manner that is robust to traffic uncertainty and variation. We discuss experiments with a prototype implementation of COYOTE.

Document type Communication à un colloque (Conference Paper) – Présentation orale avec comité de sélection
Access type Accès restreint
Publication date 2016
Language Anglais
Conference "CoNEXT", Irvine, California, USA
Peer reviewed yes
Host document "Conference on emerging Networking EXperiments and Technologies" (ISBN : 978-1-4503-4292-6)
Publication status Publié
Affiliation UCL - SST/ICTM/INGI - Pôle en ingénierie informatique
Links
  1. OCEAN. http://ocean.cs.illinois.edu/, 2016.
  2. Internet2 NOC. http://noc.net.internet2.edu/, 2016.
  3. Bertsekas D., Dynamic behavior of shortest path routing algorithms for communication networks, 10.1109/tac.1982.1102884
  4. Junlan Zhou, Malveeka Tewari, Min Zhu, Abdul Kabbani, Leon Poutievski, Arjun Singh, and Amin Vahdat. WCMP: weighted cost multipathing for improved fairness in data centers. In EuroSys 2014.
  5. Ericsson M., Resende M.G.C., Pardalos P.M., 10.1023/a:1014852026591
  6. Fortz B., Thorup M., Optimizing OSPF/IS-IS weights in a changing world, 10.1109/jsac.2002.1003042
  7. Ashwin Sridharan, R. Guerin, and C. Diot. Achieving near-optimal traffic engineering solutions for current OSPF/IS-IS networks. Networking, IEEE/ACM Transactions on, 13(2):234--247, 2005.
  8. Yufei Wang, Zheng Wang, and Leah Zhang. Internet traffic engineering without full mesh overlaying. In INFOCOM'01, volume 1, pages 565--571, 2001.
  9. Fortz B., Thorup M., Internet traffic engineering by optimizing OSPF weights, 10.1109/infcom.2000.832225
  10. Brandon Heller, Nikhil Handigol, Vimalkumar Jeyakumar, Bob Lantz, and Nick McKeown. Reproducible network experiments using container based emulation. In CoNEXT, 2012.
  11. Cantor D.G., Gerla M., Optimal Routing in a Packet-Switched Computer Network, 10.1109/t-c.1974.223806
  12. Medina A., Taft N., Salamatian K., Bhattacharyya S., Diot C., Traffic matrix estimation : existing techniques and new directions, 10.1145/964725.633041
  13. Roughan Matthew, Greenberg Albert, Kalmanek Charles, Rumsewicz Michael, Yates Jennifer, Zhang Yin, Experience in measuring backbone traffic variability : models, metrics, measurements and meaning, 10.1145/637201.637213
  14. Mosek ApS. www.mosek.com, 2015.
  15. R. Fourer, D. M. Gay, and B. W. Kernighan. AMPL: A Modeling Language for Mathematical Programming. Duxbury-Thomson, 2003.
  16. Configuring OSPF Cisco. http://www.cisco.com/c/en/us/support/docs/ip/open-shortest-path-first-ospf/7039--1.html, 2005.
  17. Internet Topology Zoo. www.topology-zoo.org, 2010.
  18. K. Németh, A. Körösi, and G. Rétvári. Optimal OSPF traffic engineering using legacy Equal Cost Multipath load balancing. In IFIP Networking Conference 2013.
  19. Boyd Stephen, Kim Seung-Jean, Vandenberghe Lieven, Hassibi Arash, A tutorial on geometric programming, 10.1007/s11081-007-9001-7
  20. Marco Chiesa, Gábor Rétvári, and Michael Schapira. Lying Your Way to Better Traffic Engineering. CoRR, abs/1610.02728, 2016.
  21. McKeown Nick, Anderson Tom, Balakrishnan Hari, Parulkar Guru, Peterson Larry, Rexford Jennifer, Shenker Scott, Turner Jonathan, OpenFlow : enabling innovation in campus networks, 10.1145/1355734.1355746
  22. David Applegate and Mikkel Thorup. Load optimal MPLS routing with N+M labels. In Proceedings IEEE INFOCOM 2003.
  23. Praveen Kumar, Yang Yuan, Chris Yu, Nate Foster, Robert D. Kleinberg, and Robert Soulé. Kulfi: Robust traffic engineering using semi-oblivious routing. CoRR, abs/1603.01203, 2016.
  24. Ayşegül Altin, B. Fortz, and Hakan Ümit. Oblivious OSPF Routing with Weight Optimization Under Polyhedral Demand Uncertainty. Netw., 60(2):132--139, 2012.
  25. D. Applegate and E. Cohen. Making Routing Robust to Changing Traffic Demands: Algorithms and Evaluation. Networking, IEEE/ACM Transactions on, 14(6):1193--1206, 2006.
  26. Räcke Harald, Optimal hierarchical decompositions for congestion minimization in networks, 10.1145/1374376.1374415
  27. Vissicchio Stefano, Tilmans Olivier, Vanbever Laurent, Rexford Jennifer, Central Control Over Distributed Routing, 10.1145/2785956.2787497
  28. Stefano Vissicchio, Laurent Vanbever, and Jennifer Rexford. Sweet little lies: Fake topologies for flexible routing. In HotNets-XIII, pages 1--7, 2014.
  29. Marco Chiesa, Guy Kindler, and Michael Schapira. Traffic Engineering with Equal-Cost-MultiPath: An Algorithmic Perspective. In INFOCOM'14, pages 1590--1598, 2014.
  30. Fortz Bernard, Thorup Mikkel, Increasing Internet Capacity Using Local Search, 10.1023/b:coap.0000039487.35027.02
  31. C. Hopps. Analysis of an ECMP Algorithm. RFC 2992, 2000. www.ietf.org/rfc/rfc2992.txt.
  32. John Moy. OSPF version 2. RFC 2328, 1998.
  33. Andrew R. Curtis, Jeffrey C. Mogul, Jean Tourrilhes, Praveen Yalagandula, Puneet Sharma, and Sujata Banerjee. DevoFlow: Scaling Flow Management for High-performance Networks. In SIGCOMM 2011.
  34. Wang Ning, Ho Kin, Pavlou George, Howarth Michael, An overview of routing optimization for internet traffic engineering, 10.1109/comst.2008.4483669
  35. Fortz B., Rexford J., Thorup M., Traffic engineering with traditional IP routing protocols, 10.1109/mcom.2002.1039866
Bibliographic reference Chiesa, Marco ; Rétvári, Gábor ; Schapira, Michael. Lying Your Way to Better Traffic Engineering.CoNEXT (Irvine, California, USA). In: Conference on emerging Networking EXperiments and Technologies, 2016
Permanent URL http://hdl.handle.net/2078.1/182799