BOUQUET—Aggregating Network Paths in Trees to Reduce Data-Plane Forwarding State. (21st February 2018)

• Record Type: Journal Article
• Authors: Mamede, Margarida; Martins, José Legatheaux; Horta, João
• Editors: Parr, Gerard
• Is Part Of: Computer journal. Volume 61:Number 10(2018)
• Page Start: 1512
• Page End: 1522
• Publication Date: 2018-02-21
• Subjects: network protocols design -- data path algorithms -- control path algorithms -- graph algorithms -- NP-hard problems; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxy015
• Languages: English
• ISSNs: 0010-4620

Abstract

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.