Forwarding of packets at the data plane of networks has gone through
several changes to optimize various metrics. In a conventional IP
network, it is based on packet header fields such as the destination
address. Path computation towards the destination is performed at
each hop in such networks. Source routing is added as a technique to
avoid path computation at each hop by including the route in the
packet itself. However, encoding the entire path of each packet in
its header has the disadvantage of an increased packet size resulting
in overhead. Multi-protocol Label Switching (MPLS) was introduced to
tag the packets using small fixed size labels, thereby simplifying
the forwarding process. The labels are used to look up a forwarding
table typically implemented using fast but expensive TCAM (Ternary
Content-Addressable Memory). However, each data flow through the
network requires a separate label, resulting in per-flow state in the
network switches, especially when traffic engineering requires each
flow to be handled differently by the switches. This results in
increased Forwarding Table Size (FTS) and therefore increased TCAM
requirement.

Segment Routing (SR) is a source routing paradigm with a flexible
architecture that addresses this problem of per-flow state in the
switches. Packet forwarding using SR is based on a sequence of
instructions known as segments identified using Segment IDs (SIDs).
An ordered list of SIDs known as the segment list 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 avoids per-flow state thereby minimizing the FTS of
the switches.

Software-defined Networks (SDNs) are suitable for SR since the source
routing (i.e., the computation of the segment list) 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
requirements of the network switches vary inversely as the SLD. In this
presentation, we discuss the problem of minimizing the FTS given the
set of flows and the SLD limitation. This problem is shown to be
NP-complete by reduction from the Set Cover problem. An ILP formulation
of the problem is discussed, which can be 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 multi-paths (ECMPs), while BFH performs better
when ECMPs are few in number.