Premium
Optimal segments for forwarding table size minimization in segment‐routed SDNs
Author(s) -
Anbiah Anix,
Sivalingam Krishna M.
Publication year - 2020
Publication title -
international journal of network management
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.373
H-Index - 28
eISSN - 1099-1190
pISSN - 1055-7148
DOI - 10.1002/nem.2142
Subject(s) - computer science , routing table , packet forwarding , network packet , forwarding plane , heuristics , routing (electronic design automation) , minification , source routing , computer network , heuristic , network topology , distributed computing , routing protocol , artificial intelligence , programming language , operating system
Summary Segment routing (SR) is a source routing paradigm where packet forwarding is based on a sequence of instructions known as segments identified using segment IDs (SIDs). An ordered list of SIDs identifies the source route and is carried in the packet headers. Switches in such networks use the SIDs to look up their forwarding tables and forward packets along the segments. Since various flows can share the segments, SR is a mechanism to avoid per‐flow state thereby minimizing the forwarding table size (FTS) of the switches. Software‐defined networks (SDNs) are suitable for SR since the source routing can be accomplished by a centralized controller. Typically, the segment list is limited to a maximum segment list depth (SLD). It can be shown that FTS varies inversely as the SLD. This paper studies the problem of minimizing the FTS given the set of flows and the SLD limitation, which is shown to be NP‐complete. An ILP formulation of the problem is used to solve the problem in relatively small networks. Two different heuristic solutions, BFH and CCH, are presented to solve this problem in large‐scale networks with up to 30,000 nodes and 250,000 flows and for three different network topologies (ring‐of‐rings, fat‐tree, and mesh). The heuristics are shown to perform up to 50% better than an existing FTS minimization technique. Further, CCH is shown to perform better in networks with a high prevalence of equal cost multipaths (ECMPs), while BFH performs better when ECMPs are few in number.