Research Of Load Balancing Problem On Segment Routing Architecture

There are problems such as high consumption of flow entry resources and overlo-ads of the controller in software-defined networking(SDN).Those drawbacks can lead to a significant degeneration in network traffic forwarding capability and network sca-lability.Through inserts part of the routing information(labels)into packet header,seg-ment routing can forward packets based on those labels,so that only a small amount of flow entry resources is required.However,during the forwarding process of segment routing,insertion of too many labels involves complex copy processes,which affects the forwarding efficiency.In addition,current load balancing solutions based on the segment routing architecture mainly solved by integer linear programming and constraint programming,which re-quire a long computational time and cannot respond to sudden changes in network traf-fic or topology.By studying the forwarding architecture of the segment routing and real-time processing capability,while providing a better load balancing capability,this dissertation seeks a better solution to enhance the ability to responding sudden changes in network changes,and reduces the consumption of flow entry resources and segment routing labels.The main research contents and contributions of this dissertation are listed as follows:1.Targeting the problems of insufficient resources of flow entry in software-defined network architecture and excessive segment routing label to be inserted during the forwarding,we have proposed a new segment routing architecture,called kLink ar-chitecture.The kLink architecture we proposed reduces the number of labels by sharing labels in multiple nodes,and also greatly decreases the consumption of flow table en-try resources.Compared with the standard segment routing protocol,experiments have shown that the kLink architecture can effectively reduce the number of labels by 50%,in terms of flow entry resources consumption,it is less than 1/3 of the traditional solution.2.Aiming at the two shortcomings that the algorithm is time-consuming and can not respond to sudden changes in traffic or topology in related load balancing solutions,we have proposed a random link optimization algorithm based on local search.The algorithm reduces the maximum load of the link by randomly adjusting the traffic on the high-load link to the nearby links with relatively low loads.And the algorithm can obtain a feasible solution in any given time,and can quickly respond to changes in network topology or traffic matrix.Comparing the experimental results with related algorithms,in terms of traffic load,our algorithm can reduce 30%of maximum link load in commonly used network architecture by data center;in terms of time efficiency,our algorithm can reduce the running time by 4 to 5 times,and get solutions within 1 second.3.Targeting the shortage of ternary content addressable memory(TCAM)resour-ces that used in the flow table matching procedure,we have proposed a hybrid network architecture.This hybrid architecture uses segment routing to reduce the consumption of flow table entry resources,and uses flow entry to guide the traffic at key nodes to reduce the use of labels.Then by adding link capacity constraints and flow entry re-source constraints,the load balancing problem of the hybrid network architecture is provided and its NP-hardness is proved.An approximation algorithm is proposed to solve this problem,and we performed an approximate analysis of the algorithm.We proved that the algorithm can achieve the approximation factor of 4logn/? 4 for link capacity constraint and the approximation factor of 3logn/? + 3 for flow table entry con-straint.Experiments have shown that,compared with the stat-of-the-art architecture,our algorithm can achieve similar load balancing effect in the load balancing capability parameter,and reduce 12%in the consumption of flow table entry resources parameter.