Network design and optimization based on segment routing

Abstract

Segment routing (SR) is an emerging networking technology that combines the advantages of both IP routing and source routing. In SR, a packet can be forwarded along any arbitrary path identified by a segment list. The segment list consists of segment identifiers (SIDs) and each SID identifies a sub-path called segment. Specifically, a node-SID identifies a shortest-path segment and an adjacency-SID identifies a link segment. In this thesis, three important network design and optimization problems based on SR are investigated: traffic engineering, network monitoring and fast reroute.

Traffic engineering aims at finding a set of K-segment paths, or paths that can be identified by a segment list with no more than K SIDs, to carry all the flows in a given traffic matrix such that the maximum link utilization in the network is minimized. Existing approaches ignored adjacency-SIDs due to the complexity involved. As a result, not all paths in the network can be utilized to carry traffic and the solutions found are not optimal. In this thesis, we formulate the first mixed integer linear programming (MILP) for optimal solutions. A simplified but close-to-optimal formulation is also designed. It is further extended to prevent excessive flow splitting and long paths. For large-sized networks, an efficient heuristic algorithm is also proposed.

In SR, network monitoring can be conducted from a single vantage point in the network, where a monitor periodically sends probe packets along a set of cycles that traverse every link. A link failure is detected if packets fail to return. Aiming at minimizing network bandwidth consumption, the problem of finding a set of cycles to cover every link in the network such that their total length is minimized and each cycle is a K-segment path, or minimum cycle cover problem, is to be solved. In this thesis, the first ILP is formulated for its optimal solution. A new voltage-based approach for cycle construction is then designed to reduce the ILP complexity. For large-sized networks, a set of efficient heuristic algorithms are also proposed. We then generalize the minimum cycle cover problem to support multiple monitors and monitoring trails, or k-monitor cover problem. We first prove that the k-monitor cover problem is NP-hard. Then the first ILP is formulated to solve it, and an efficient heuristic algorithm is also proposed.

Finally, we consider a hybrid network consisting of both IP routers and SR routers. We focus on exploiting the source routing capability of SR to enhance the IP fast reroute performance. In order to maximize the percentage of links that can be protected by fast reroute, two ILP formulations are proposed. The first one aims at minimizing the repair path length and the second one focuses on balancing the traffic load in the network.