# An Optimization Routing Algorithm Based on Segment Routing in Software-Defined Networks
## 2 Related work  
### Segment Routing Based on SDN  
SR [4] is a recently proposed routing architecture to solve the complex problem of a large number of forwarding rules in the information forwarding process. A segment [17] represents an instruction that can be used to define the path in a weighted graph. A node segment contains the unique label of the next switch to reach. The intermediate switch only needs to know how to forward to the next intermediate node with the shortest path. They no longer need to maintain the status of a large amount of network information. In the current draft defined by the IETF, two segments are defined: the Nodal Segment and Adjacency Segment. The Nodal Segment is a global label. Each node is assigned by a globally unique Nodal Segment. The Adjacency Segment is a local label that is locally valid and used to represent a particular segment routing node. In Figure 1, we use a simple network topology to clarify the overview of SR based SDN. The SDN controller calculates the explicit route through the routing module and configures the forwarding table of the ingress switch with a segment list. The node only processes the top label of the stack to forward the packets along the shortest path to reach the specified destination. For example, the target path for an incoming traffic flow is from A to F, and the path is an encoded SID list E, 101, F in the packet header. E and F are the Nodal Segment. 101 is the Adjacency Segment. The switch A processes the top label of the stack and forwards the packet to the switch E along the shortest path. Then, switch E pops the top label to forward the packet to F along the shortest path from output port 101. After arriving at switch C, the packet is forwarded to F along the shortest path. SR maintains per-flow path information only at the ingress node, where the label stack is initialized by the SDN controller. In this way, the operation of the control plane and the provisioning procedure of time consumption is remarkably simplified. Some works have been done on this issue. The authors in [4] present the concept of SR and its implementation. SR uses the source routing method. The idea of SR is to divide an end-to-end path into multiple segments, each of which is identified by a segment identifier. The forwarding steps are designated in the segment, so the routers do not have to maintain routing table information. The header of the packets carries the segment. The node forwards the packet to the destination via the shortest path. The authors note that SR has a unique advantage in implementing network load balance and traffic engineering. As we know, SDN has a global view of the network and has the ability to control the segments. The combination of SR and SDN is a good way to meet these differentiated business needs and can quickly realize the deployment and implementation of business needs. However, our work mainly considers the routing algorithm about SR in SDN. The authors in [18] aim at solving the problem of restoration optimization in SR. The main problem is to centralize connection to the primary path in order to achieve optimal sharing of recovery bandwidth in non-synchronous network failures. The authors propose linear programming problem and random rounding scheme in this paper. The primal-dual algorithm solves the linear programming problem, and it has a good running time even on large networks. The simple random rounding scheme aims at other restrictions on segment routing. However, our research aims at evaluation and selection of paths for SR in SDN. The authors in [19] concentrate on two related situations: dynamic traffic recovery and multi-domain traffic engineering. This paper defines the appropriate procedure to minimize the depth of the segment  
Figure 1: Segment routing based on SDN. list. With regard to traffic recovery, an SR-FAILOVER scheme is proposed to dynamically recover traffic flow interrupted by link or node failures to minimize the depth of the required segment list.