Optimal segments for forwarding table size minimization in segment-routed SDNs

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.

Automated summary

Segment routing (SR) is a source routing paradigm that uses segment IDs (SIDs) to forward packets based on a sequence of instructions. By carrying a list of SIDs in packet headers, switches can reduce forwarding table size and avoid per-flow state. The problem of minimizing the forwarding table size given a set of flows and limitations is shown to be NP-complete, with two heuristic solutions presented for solving this issue.