BOUQUET — Aggregating network paths in trees to reduce data-plane forwarding state

Research output: Contribution to journalArticle

Abstract

Flexible network management requires explicit control of the exact paths taken by different network flows. Whatever the way this endeavour is achieved (e.g. Multiprotocol Label Switching, Virtual Local Area Networks and OpenFlow), this need may lead to an explosion of entries in the forwarding tables of network equipment. In this article, we present an algorithm that aggregates many network paths in a reduced number of trees, thus allowing shrinking the forwarding state in switching devices. Path aggregation algorithms are often deployed to reduce data-plane state with different routing approaches and the presented algorithm achieves better results than existent algorithms with similar goals. Additionally, we show that most types of popular routing and switching equipment, even using off-the-shelf routing software, may be used to implement multi-path routing with trees. This highlights the applicability of the proposed algorithm and its significance in light of the current trend of separating the data- and the control-planes in modern networks.

Original languageEnglish
Pages (from-to)1512-1522
Number of pages11
JournalComputer Journal
Volume61
Issue number10
DOIs
Publication statusPublished - 1 Jan 2018

Keywords

  • Control path algorithms
  • Data path algorithms
  • Graph algorithms
  • Network protocols design
  • NP-hard problems

Fingerprint Dive into the research topics of 'BOUQUET — Aggregating network paths in trees to reduce data-plane forwarding state'. Together they form a unique fingerprint.

  • Cite this