A Computation-Efficient Approach to Reduce Network Congestion for Segment Routing Traffic Engineering

Segment Routing Example: Consider a traffic flow from node i to node j, labels of the intermediate and destination nodes will be attached to the packet headers at node i. Then, node i sends the packet to an intermediate node l. After node l receiving the packet, node l pops out its label and sends the packet to the next node by looking at the next label. After the packet arrives at the destination node j, node j realizes that it is the destination since there is no label follow node j's label. This routing scheme simplifies the control functions of communication networks by explicitly put routing information to the packet headers.


Due to the unprecedented growth of network traffic, network operators are increasingly motivated to manage resource utilization efficiently to avoid network congestion. Traffic engineering is a method to map traffic to network links such that the resource can be managed. Traditionally, network operators leverage shortest path based approaches, which are too vulnerable to network congestion as shortest path routing is very restrictive. Recently, segment routing traffic engineering has been proposed to overcome drawbacks from traditional traffic engineering approaches. However, the trade-off relationship between computation time and link utilization had not been investigated before.

To this end, we formulate an optimization problem to study the trade-off relationship of computation time and link utilization. Due to the hardness of the problem, we proposed a problem decomposition approach that divides the original problem into two sequential sub-problems (e.g., node selection and flow assignment). Then, we leverage stretch bounding with randomized sampling for node selection and linear programming for flow assignment, respectively. In brief, we found that our proposed approach helps balance the trade-off effectively. It is interesting to note that the computation time can be reduced enormously while the link utilization can be kept competitive as compared with several comparison approaches. We believe that our approach can be useful for segment routing traffic engineering, especially when the computation interval is highly limited. In addition, this approach may be capable of applying with other optimization problems regarding paths, flows, and routing in general.

Bibliographic information:
  • Journal title: IEEE Access Publication date: 4 November 2019
  • Paper title: A Computation-Efficient Approach for Segment Routing Traffic Engineering
  • Authors: Tossaphol Settawatcharawanit, Yi-Han Chiang, Vorapong Suppakitpaisarn, Yusheng Ji
  • DOI: 10.1109/ACCESS.2019.2951163
  • URL: https://ieeexplore.ieee.org/document/8890665

Tossaphol Settawatcharawanit, Department of Informatics