# A Traffic Scheduling Method Based on SDN

Authors: Li Wang
Journal: Mathematical Problems in Engineering
 (2022)

---

## Abstract

The rise of big data has brought severe challenges to data storage, which also means that computing resources and storage resources have become centralized. In the past, business data could end up after being processed locally or at the secondary node. Now, all data must be uploaded to each data center for unified processing. Data collection also requires users to access data center services and then send them back, which undoubtedly increases the pressure on the backbone network. This also means that the annual private line cost of the enterprise will increase with the growth of network traffic. Large enterprises often use multiple lines between network nodes to improve link utilization and network reliability. However, in most cases, the line utilization of the backup line is usually low, because the traditional routing algorithm forwards according to the optimal path. Load sharing or traffic scheduling is achieved by adjusting interface cost values ​​or BGP parameters. In large networks, it often affects the entire body. Each adjustment requires detailed planning and validation. At the same time, due to the diversity of applications, different applications have different business characteristics. If the network can distinguish different applications, sense network conditions, and adjust the QoS and traffic paths of applications as needed, the link utilization of leased lines and the network quality of applications will be significantly improved. SDN separates the control plane from the data plane and intelligently controls the network forwarding policy through the global controller, which improves the flexibility and security of the network. Based on the traditional large-scale enterprise WAN architecture, this paper proposes a complete traffic scheduling solution based on SDN to achieve secure, controllable, and flexible scheduling of enterprise WAN network resources.


---

## Body

## 1. Introduction

With the rapid development of cloud computing, big data, mobile applications, and the Internet of things, the traffic on the WAN will also increase explosively, and the expenditure of enterprises on dedicated line fees will also rise sharply. However, the enterprise’s dedicated line links often have low average utilization but high peak utilization, and the enterprise’s redundant links cannot be effectively utilized. According to the prediction of authoritative institutions, the future traffic will continue to grow at a faster rate than expected. In order to cope with such growth, it is very expensive for enterprises to upgrade the bandwidth of leased lines and build and use free optical cables. Enterprises also hope to effectively control the bandwidth cost caused by the increase in bandwidth demand.With the rapid growth of network traffic, some problems in the enterprise network are gradually exposed: at present, many enterprise networks are often unable to achieve comprehensive visualization, making the network business slow and unable to locate quickly; enterprises spend a lot of money on the improvement of dedicated line bandwidth, but in many cases, the service quality is still not improved. Therefore, enterprises urgently need to solve the problems in the existing network through the transformation of the network and technological innovation.In terms of network visualization, the traditional network monitoring scheme is often realized through SNMP [1], which has complex configuration, low sampling frequency, and few monitoring indicators. The collected monitoring data are often only an auxiliary means to troubleshoot and solve problems and cannot be used as the basis for network optimization. Therefore, enterprises need to use some new monitoring technologies, such as bgp-ls to realize the automatic drawing of network topology [2], telemetry to realize the second push of equipment performance indicators, and network probe to realize the accurate analysis of traffic [3]. Through a large number of monitoring data and analyzing the performance indicators of each service, the intelligent scheduling of network traffic is realized.In terms of network traffic scheduling, traditional network engineers often realize service traffic scheduling by manually configuring MPLS-TE [4]. Its configuration is complex and error-prone. With the increase of enterprise network scale, its configuration often leads the whole body, which has high requirements for network engineers. Google’s B4 pioneered the use of SDN to realize the service traffic scheduling between global data centers, which greatly improved the bandwidth utilization of its submarine optical cable and reduced the annual cost of the link cost [5]. At present, large enterprises are also facing this situation. If enterprises can use SDN technology to centrally control network business traffic, ensure important business operation, and improve bandwidth utilization, it will greatly reduce the leased line rental cost of enterprises.This paper is divided into four parts. Section1 introduces the overall scheme of SDN traffic scheduling. Section 2 introduces the design and implementation of the scheduling algorithm. Section 3 tests and verifies the scheduling algorithm. Section 4 is the summary and prospect.The overall solution is mainly divided into three parts, including network visualization, traffic scheduling, and configuration distribution. The purpose of network visualization is to obtain the data and indicators of the whole network and provide a basic data source for the calculation of traffic scheduling. Traffic scheduling refers to the algorithms used in Google B4 [6] network (KSP algorithm, greedy algorithm, maximum, and minimum fair value algorithm [7]). According to the collected network indicators, application priority, network topology, and other information, each application is allocated its bandwidth, path, and priority globally and fairly [6]. The configuration distribution module generates the corresponding configuration according to the final traffic scheduling result and distributes it to the network device.Network visualization mainly includes two parts: network topology visualization and network traffic visualization. Network topology visualization solves the problem of constructing the adjacency relationship between network nodes and links, and network traffic visualization solves the problem of network traffic data collection, analysis, and visualization.At present, the most mainstream solution for network topology visualization is to obtain network topology information through BGP-LS (border gateway protocol link state). By extending the two attributes of address family and routing of BGP protocol, it carries the information of topology nodes, link information, and routing information of each node in the network through three attributes: node, link, and routing prefix [8]. At the same time, it also supports cross-domain network topology generation. The controller only needs to establish a BGP-LS session with one device in each domain to draw the network topology information of the whole network.There are traditional NetFlow schemes for network traffic visualization, port images combined with network probe schemes, and some technical schemes produced by various manufacturers to cooperate with their own controllers, such as IFIT. Because NetFlow appeared earlier, most network devices support this function. It can realize the monitoring based on the network quintuple. Because NetFlow relies on the device for network traffic analysis, when the traffic flow in the network is large, it has a high-performance loss to the device. Therefore, in many cases, it will reduce the loss of equipment performance by reducing its sampling rate, which leads to the inaccurate traffic data obtained by using NetFlow [9]. The solution provided by the manufacturer is like IFIT. Its essence is to sample and analyze network traffic data similar to NetFlow. Compared with NetFlow, it has the advantage that end-to-end traffic analysis can be realized through whole network deployment. The advantage of port mirroring combined with network probe is that it has little impact on the performance of network equipment and because it is full traffic collection and analysis, the collected traffic data are more accurate [10].Traffic scheduling is mainly divided into two parts, including path calculation and path and bandwidth allocation. The purpose of path calculation is to create a traffic path in advance for the scheduling algorithm. Path and QoS allocation is to allocate the path and bandwidth for each application flow according to the maximum and minimum fair value algorithm according to the network path, link bandwidth, application priority, and required bandwidth, so as to achieve the global optimal effect.The algorithm can calculate the K optimal paths without loops from a starting point to an end point. Generally speaking, the bandwidth of the enterprise’s dedicated line link is much smaller than that used by the intranet line. Therefore, when using this algorithm, we only need to reduce the cost value of the high bandwidth link and increase the cost value of the low bandwidth link, plus the appropriate number of paths, we can generate a path covering all low bandwidth links.Assuming that the number of nodes in the network topology isn and the node has m deviation points, in the kth iteration, we need 1/2∑i=1mN−i2=1/6qN3 insert operation and ∑k=1mN−k2=1/3qN3 comparison operation, where 0<q≤1。. Hence, the insertion operation to be performed by the whole algorithm is 1/6qKN3, the comparison operation is 1/3qKN3, and the additional space required is N2+KN.Application path and bandwidth allocation: this paper uses the minimum and maximum fair value algorithm [11] to calculate the application path and bandwidth allocation. The implementation of specific scheduling and fair allocation algorithm is introduced in detail in Section 2.The configuration distribution module mainly completes two things, including determining the content of configuration distribution and determining the protocol of configuration distribution. The content of configuration distribution needs to be determined according to the actual situation of the current network. In networks that only support MPLS, path switching can be realized by MPLS-TE combined with PBR or CBTs. In networks supporting segment routing [12], application flow scheduling can be realized through SR-TE, SR policy combined with CBTs or PBTS. At present, only NETCONF [13] and CLI can be used to configure distribution. Compared with CLI, NETCONF has great advantages in distribution efficiency, configuration consistency, and development efficiency, but not all devices can support NETCONF protocol, and its device versatility is poor. Table 1 compares the CLI and NETCONF distribution efficiency. If the enterprise’s ingress node cannot support the NETCONF protocol, the upper SDN controller needs to design a perfect distribution process when developing relevant modules to ensure the success of distribution and the rollback after distribution failure. Time required for CLI script and NETCONF to complete a certain number of configurations is shown in Table 1.Table 1
Time required for CLI script and NETCONF to complete a certain number of configurations.
CLI (s)NETCONF (s)1005.3890.63620011.3260.73850027.6541.356100056.2762.153


## 2. Design and Implementation of the Scheduling Algorithm

With the expansion of enterprise scale, there are many kinds of applications in the network, and the application characteristics of each application are also very different. Some applications are sensitive to delay and packet loss but do not require high bandwidth; some applications are sensitive to delay and packet loss but require high bandwidth; some applications have high requirements for delay, packet loss, and bandwidth. Therefore, if each application is divided into a policy, the number is very large, and it is difficult for network devices to schedule each application. In IP packet designing, the first three bits of the TOS field are used as IP priority. The larger the number from 0 to 7, the higher the importance of the service. Later, in order to identify more service types, a new definition of TOS was made in RFC 2474 [14], taking the first six bits as DSCP and reserving the last two bits, so that 0 ∼ 63 service types can be represented. Since the priority field in the MPLS tag only contains 3 bits, it is consistent with the TOS field, and generally, 6 and 7 in the TOS are reserved for basic protocols such as routing protocols. Therefore, this paper implements scheduling according to six types of applications from 0 to 5.Path calculation: in this paper, Yen algorithm [11] is used to calculate the path. The detailed algorithm flow is shown in Figure 1.Figure 1
Implementation flow chart of Yen algorithm.Time required for CLI script and NETCONF to complete a certain number of configurations is shown in Table1.Different enterprise nodes access various applications to form hundreds of application flow groups (FGs). Each FG contains source address, destination address, priority, path, bandwidth, and other QoS information. At the same time, there are multiple paths from one site to another. These paths are divided into a tunnel group (TG). Different application classes have different priority and bandwidth requirements. The fair value fs (fair share) is obtained by priority according to the required bandwidth. The bandwidth function of each application can be obtained by taking the fair values as the horizontal axis and the bandwidth B as the vertical axis BS=W×S,0≤S≤Bmax/WBmax,S>Bmax/W, as shown in Figure 2(a) The slope shown by each line is the weight W applied. For an application stream group FG, which contains several application streams, its bandwidth function is BsumS=∑k=1nBkS; we can use the linear superposition of each application stream bandwidth function to represent B. K(s) represents the bandwidth function of the kth application stream. As shown in Figure 2(b), the bandwidth function diagram of the final FG is composed of a group of broken lines.Figure 2
Bandwidth allocation function of the application stream group FG: (a) per-application and (b) FG-level composition.
(a)(b)If the bandwidth and path allocated by each FG are calculated by linear programming, it takes a long time and has no good scalability. Therefore, this paper calculates the final result by greedy algorithm combined with dichotomy.The fair algorithm process and pseudocode are as follows:(1)
Since the number of application streams covered at the branch node is small, bandwidth allocation for the bottle-neck link is given priority at the branch node. During allocation, all cases are enumerated by permutation and combination. The initial value of minfs is 0 and maxfs is the maximum fair value in the application flow group FG. Curfs represent the currently allocated fair value, which is initially set to maxfs. The pseudocode is as follows:(2)
The bandwidth of the bottleneck link at the core/convergence is allocated. The calculation results in the first step are sorted according to the allocated bandwidth from large to small and then allocated to the links with large remaining bandwidth in all bottleneck lines. The exhaustive algorithm in the first step is not used here, mainly because the number of application streams at the core/aggregation link is relatively correct and the complexity of the exhaustive algorithm is high. Although the greedy algorithm used here is not the global optimal solution, its algorithm complexity is low and its error will decrease with the increase in the number of application streams. The maximum fair value maxfs is the maximum current fair value in all application streams (calculated in step 1), the minimum fair value minfs is 0, the current fair value curfs, flow_size is the number of all application streams, curbw [i] is the current bandwidth of the ith application stream, and priority [i] is the priority of application stream I. The pseudocode is as follows:(3)
The final path of the application flow is the path containing the bottleneck lines stored in steps 1 and 2.


## 3. Test and Result Analysis

This paper constructs a network topology, as shown in Figure3: node E and node f are branch 1, nodes g and H are branch 2, and nodes I and j are branch 3. The link bandwidth is shown in the figure. Application flows are classified into five application classes. The path of flow1 is fixed as the optimal path, and flow5 is other nonimportant services. Its required bandwidth is the maximum bottleneck bandwidth value; that is, when meeting the bandwidth requirements of other important services, the remaining bandwidth can be allocated to this kind of applications.Figure 3
Example of network topology.The path from node a to each branch node is shown in Table2. It can be seen that the path completely covers the bottleneck line.Table 2
All paths from node a to branch node.
Path namePath detailETP1-path1A- > c- > eETP1-path2A- > c- > d- > f- > eETP1-path3A- > b- > d- > c- > eETP1-path4A- > b- > d- > f- > eETP2-path1A- > c- > gETP2-path2A- > c- > d- > h- > gETP2-path3A- > b- > d- > c- > gETP2-path4A- > b- > d- > h- > gETP3-path1A- > c- > iETP3-path2A- > c- > d- > j- > iETP3-path3A- > b- > d- > c- > iETP3-path4A- > b- > d- > j- > iBy adjusting the required bandwidth in different scenarios, check whether the bandwidth is consistent with the expected bandwidth.It can be seen from Table3 that when the link bandwidth is greater than the required bandwidth of all application streams, when the link bandwidth is sufficient, the required bandwidth of each application stream will be met as much as possible.Table 3
Algorithm results when bandwidth demand is lower than link bandwidth.
Flow nameCalculated bandwidth (kbps)Demand bandwidth (kbps)Calculated pathPriorityETP1_Flow140004000ETP1-path16ETP1_Flow280008000ETP1-path45ETP1_Flow380008000ETP1-path34ETP1_Flow420002000ETP1-path33ETP1_Flow52000030000ETP1-path21ETP2_Flow140004000ETP2-path16ETP2_Flow240004000ETP2-path45ETP2_Flow380008000ETP2-path44ETP2_Flow420002000ETP2-path33ETP2_Flow52000030000ETP2-path11ETP3_Flow140004000ETP3-path16ETP3_Flow240004000ETP3-path15ETP3_Flow320002000ETP3-path14ETP3_Flow420002000ETP3-path43ETP3_Flow5800030000ETP3-path41Table4 shows the results calculated by a fair algorithm when the link bandwidth is insufficient after adjusting the required bandwidth of high priority applications. It can be seen that the bandwidth requirements of high priority applications are guaranteed first, while the bandwidth of low priority applications can be allocated better when the link bandwidth is sufficient, and the bandwidth of bottleneck links can be fully used to improve the overall link utilization.Table 4
Algorithm calculation results after increasing the bandwidth required by high priority applications.
Flow nameCalculated bandwidth (kbps)Demand bandwidth (kbps)Calculated pathPriorityETP1_Flow140004000ETP1-path16ETP1_Flow21000010000ETP1-path25ETP1_Flow31000010000ETP1-path44ETP1_Flow41000010000ETP1-path33ETP1_Flow5575030000ETP1-path21ETP2_Flow140004000ETP2-path16ETP2_Flow21000010000ETP2-path25ETP2_Flow31000010000ETP2-path34ETP2_Flow41000010000ETP2-path43ETP2_Flow5575030000ETP2-path11ETP3_Flow140004000ETP3-path16ETP3_Flow2600010000ETP3-path15ETP3_Flow3500010000ETP3-path24ETP3_Flow4375010000ETP3-path43ETP3_Flow5125030000ETP3-path21Table5 increases the required bandwidth of enterprise 2 application stream 2 compared with Table 4. From the calculation results, it can be seen that the allocated bandwidth of application flow under the same conditions of enterprise 1 and enterprise 2 is consistent, which shows the global fairness of the algorithm.Table 5
The result of the etp2_ calculation of the boosting algorithm.
Flow nameCalculated bandwidth (kbps)Demand bandwidth (kbps)Calculated pathPriorityETP1_Flow140004000ETP1-path16ETP1_Flow21000010000ETP1-path15ETP1_Flow31000010000ETP1-path44ETP1_Flow4966610000ETP1-path43ETP1_Flow5322230000ETP1-path11ETP2_Flow140004000ETP2-path16ETP2_Flow21611120000ETP2-path25ETP2_Flow31000010000ETP2-path34ETP2_Flow4966610000ETP2-path33ETP2_Flow5322230000ETP2-path21ETP3_Flow140004000ETP3-path16ETP3_Flow2600010000ETP3-path35ETP3_Flow3500010000ETP3-path24ETP3_Flow4375010000ETP3-path43ETP3_Flow5125030000ETP3-path41


## 4. Conclusions and Outlook

Based on the actual network situation of the current enterprise network, this paper introduces a complete solution for SDN service traffic scheduling, including network visualization, traffic scheduling, and configuration distribution. The rationality and correctness of the scheduling algorithm are verified by tests. The research content of this paper is more based on the status quo of the enterprise network to achieve business traffic scheduling. However, with the emergence of new technologies and the upgrading of enterprise equipment, enterprises can also achieve intelligent scheduling of business traffic in a more convenient and intelligent way, improve the bandwidth utilization of private lines, reduce private line costs, and improve operational efficiency. The method to improve the accuracy of network indicators, the ubiquity of scheduling algorithms, and the efficiency of configuration distribution are also the key directions of future research and practice and ultimately realize the complete integration of services and networks. The dynamic scheduling and universality of future data in the research of this paper are one of the key tasks of future research.



---

*Source: 1819202-2022-04-30.xml*