Joint Routing And Flow Allocation Algorithm In Software-Defined Networking

As an emerging technology,software defined networking(SDN)is characterized by the distinguished features,including logical centralized control,decoupling the control plane from the data plane and providing programmability for network applications.It allows flexible control of network devices and supports user applications with guaranteed quality of service(QoS).To achieve flow transmission between two non-adjacent switches in SDN,efficient routing algorithm should be designed.While considering the resource competition problem of multiple user flows,the flow allocation algorithm should also be designed.In this thesis,we jointly study the route selection and flow allocation problem,and the following issues are mainly discussed.Firstly,the concept,the structure and the key technologies of SDN are introduced.The current research works on routing algorithms and flow allocation algorithms for SDN are summarized.Moreover,the difficulties and challenges of SDN routing and flow allocation are analyzed.Secondly,under the assumption that user flows can be split into multiple sub-flows which may transmit from the source to the destination via different paths,we study the joint route selection and flow allocation problem over SDN.To stress the service sensitivity on delay,we design an optimization algorithm which minimizes the total delay subject to data transmission and service requirement constraints of user flow.Since the formulated optimization problem is an NP-complete problem,traditional method can not get the optimal result.For the case of single user flow,we propose a modified minimum cost flow algorithm.And for the case of multiple-user flows,we use the modified minimum cost flow algorithm and Lagrange dual decomposition method to deal the route selection and flow allocation problem.By selecting the minimum cost path in an auxiliary network iteratively,the optimal joint routing and flow allocation strategy can be obtained.Finally,we study the route selection and resource allocation problem of multiple user flows in SDN.Considering the end-to-end delay and the network load metrics,we design a utility function that characterize the joint network performance as the weighted sum of end-to-end delay and network load.Under the constraints of the QoS requirement of user flows,network performance,routing,and resource allocation,we study the joint route selection and resource allocation optimization problem which minimizes the utility function.Based on the Dijkstra algorithm and Lagrange dual decomposition method,we propose a joint route selection and resource allocation algorithm.