Paper Info
Title
Traffic engineering with Equal-Cost-Multipath: An algorithmic perspective.
Abstract
To efficiently exploit the network resources operators, do traffic engineering (TE), i.e., adapt the routing of traffic to the prevailing demands. TE in large IP networks typically relies on configuring static link weights and splitting traffic between the resulting shortest paths via the Equal-Cost-MultiPath (ECMP) mechanism. Yet, despite its vast popularity, crucial operational aspects of TE via ECMP are still little-understood from an algorithmic viewpoint. We embark upon a systematic algorithmic study of TE with ECMP. We consider the standard model of TE with ECMP and prove that, in general, even approximating the optimal link-weight configuration for ECMP within any constant ratio is an intractable feat, settling a long-standing open question. We establish, in contrast, that ECMP can provably achieve optimal traffic flow for the important category of Clos datacenter networks. We last consider a well-documented shortcoming of ECMP: suboptimal routing of large (“elephant”) flows. We present algorithms for scheduling “elephant” flows on top of ECMP (as in, e.g., Hedera) with provable approximation guarantees. Our results complement and shed new light on past experimental and empirical studies of the performance of TE with ECMP.
Year
DOI
Venue
2014
10.1109/INFOCOM.2014.6848095
IEEE/ACM Trans. Netw.
Keywords
Field
DocType
Routing,Approximation algorithms,Network topology,Standards,Optimization,IEEE transactions,IP networks
Multipath propagation,Multipath routing,Internet traffic engineering,Static routing,Computer science,Computer network,Loose Source Routing,IP forwarding,Traffic engineering,Virtual routing and forwarding,Distributed computing
Conference
Volume
Issue
ISSN
25
2
1063-6692
Citations 
PageRank 
References 
15
0.81
24
Authors
3
Name
Order
Citations
PageRank
Marco Chiesa11018.20
Guy Kindler2150.81
Michael Schapira3112279.89