Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Traffic engineering with Equal-Cost-Multipath: An algorithmic perspective
Roma Tre University, Italy.ORCID iD: 0000-0002-9675-9729
2014 (English)In: INFOCOM, 2014 Proceedings IEEE, Institute of Electrical and Electronics Engineers (IEEE), 2014, p. 1590-1598, article id 6848095Conference paper, Published paper (Refereed)
Abstract [en]

To efficiently exploit 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 [1]) with provable approximation guarantees. Our results complement and shed new light on past experimental and empirical studies of the performance of TE with ECMP.

Place, publisher, year, edition, pages
Institute of Electrical and Electronics Engineers (IEEE), 2014. p. 1590-1598, article id 6848095
Series
Proceedings - IEEE INFOCOM, ISSN 0743-166X
National Category
Communication Systems Computer Sciences
Identifiers
URN: urn:nbn:se:kth:diva-222331DOI: 10.1109/INFOCOM.2014.6848095ISI: 000361544200178Scopus ID: 2-s2.0-84904430604ISBN: 9781479933600 (print)OAI: oai:DiVA.org:kth-222331DiVA, id: diva2:1180761
Conference
33rd IEEE Conference on Computer Communications, IEEE INFOCOM 2014, Toronto, ON, Canada, 27 April 2014 through 2 May 2014
Note

QC 20180207

Available from: 2018-02-06 Created: 2018-02-06 Last updated: 2018-02-07Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Chiesa, Marco
Communication SystemsComputer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 9 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf