Priority-based online flow scheduling for network throughput maximization in software defined networking

摘要

Data transmission in current networks is usually associated with strict priority enforcement for the purpose of quality of service (QoS). Under the case that priority flow requests are injected into the network sequentially without the information of future flow request arrivals, it is a challenging to achieve network throughput maximization for on-line flow requests under the joint constraints of the flow's priority, bandwidth demand, and resource capacity. Software Defined Networking (SDN) can effectively solve the flow scheduling equilibrium problem between the priority of dynamic flow requests and the maximization of network throughput. Therefore, in this paper, we study on-line flow request admission in SDN, the goal of which is to maximize the network throughput under the constraints of critical network bandwidth resources, flow priority, and bandwidth demands. First, we present the concept of flow routing cost and profit and a model to characterize the cost of using link resources and routing paths. Then, we propose an efficient on-line priority flow scheduling algorithm (OPFSA) to solve priority flow request scheduling problem and analyze the competitive ratio of OPFSA. Our on-line algorithm can reach throughput within O(1logn) of the highest possible throughput that can be achieved by an off-line algorithm, where n is the number of node in the network. Finally, experimental results demonstrate that compared with SHORTEST-SC, our proposed algorithm can enhance the cumulative bandwidth about 9% and 40% when general network size is 30 and 170 nodes, respectively, and improve the throughput about 25% in Fat-tree network when pod size is 4.