CN104836750B - A kind of data center network stream scheduling method based on round-robin - Google Patents

Abstract

The invention discloses a data center network flow scheduling method based on time slice rotation, belonging to the field of data center networks. This method utilizes SDN technology, in the data center network with redundant links, comprehensively considers the distribution of long flows and short flows, dynamically controls the flow forwarding in the network, and can dynamically adjust the flow in the SDN network according to the size of the flows in the network. Queuing in the switch. The invention can realize the load balance of the data flow in the data center network, and reduce the delay of the short flow in the Internet network.

Description

A data center network flow scheduling method based on time slice rotation

technical field

The invention relates to a data center network flow scheduling method based on time slice rotation, belonging to the field of data center networks.

Background technique

As the key infrastructure of high-yield online services (web search, social network, advertising system, and recommender system), the network performance of data center has attracted more and more attention. These applications place low latency requirements on data center networks. User experience is greatly affected by application response speed, and even a delay of a few hundred milliseconds can significantly degrade user experience. Amazon, for example, found that every 100ms increase in latency resulted in a 1 percent drop in revenue.

The web search application is a typical application in the data center, and it follows the partition-aggregate working mode. In this working mode, different devices have different roles. They are top-level aggregators (TLAs), mid-level aggregators (MLAs) and worker nodes. The TLAs receive the request and divide the calculations required to fulfill the request to the individual MLAs. MLA continues to divide the calculations into appropriate sizes and hand them over to each worker node. Each working node executes specific calculations in parallel and returns the results to the MLA, and each MLA combines the received results and forwards them to the corresponding TLA. This mode of operation results in simultaneous short and long data flows in the data center network. This short data flow is mainly generated by aggregators at different levels, or by the interaction of MLAs with worker nodes. Long data streams are mainly caused by worker nodes performing large-scale background parallel computations. For interactive applications, reducing the completion time of short data streams can significantly improve the response time of such interactive applications, but this does not mean that long data streams generated by background calculations can be completely ignored. In other words, this kind of long data flow generated by background calculation only needs to obtain certain resources to transfer all the data. It is a throughput-sensitive flow, while this short data flow is sensitive to delay. . When delay-insensitive long data flows and delay-sensitive short data flows share the same queue, short data flows experience longer delays due to the accumulation of long data flows in the queue. At the same time, the typical stream scheduling algorithm ECMP does not solve the network congestion problem well. Once the link is congested, it will further increase the delay of the network, resulting in delays in the completion of short data streams. In order to improve network performance, an efficient scheduling algorithm needs to guarantee the delay requirements of short data streams without significantly degrading the transmission performance of long data streams.

Contents of the invention

In order to achieve this purpose, the present invention provides a network flow scheduling method based on SDN and considering both long data flow and short data flow. First of all, in order to make full use of the redundant lines in the network, the data flow in the network is evenly distributed through the method of dynamic routing, so as to avoid congestion. Secondly, in order to reduce the transmission delay of short data flows, two FIFO queues with different priorities are configured at the egress port of the switching device. The packets of short data flows are stored in the high-priority queues, and the packets of short data flows are stored in the low-priority queues. The data packets of the long data stream are stored, so that the short data stream is sent in priority to the long data stream, thereby reducing the delay of the short data stream.

The technical scheme that the present invention takes is as follows:

(1) Use SDN switches that support the OpenFlow protocol to build the Internet.

(2) Using the OpenFlow protocol to obtain the link usage between the switches, the controller sends the ofp_port_stats_request message to the SDN switch supporting the OpenFlow protocol to obtain the link information between the switches. Specific steps are as follows:

a. Every certain time interval T ₁ , the controller sends an ofp_port_stats_request message to all SDN switches in the network, and waits for the SDN switch to respond;

b. The controller triggers the PortStatsReceived event after receiving the response message of ofp_port_stats, and obtains the total number of bytes transmitted by the port so far by calling the event processing function;

c. Calculate the difference between the current total number of transmitted bytes and the last collected total number of transmitted bytes and divide it by the time interval T ₁ . This value can be approximately regarded as the current bandwidth occupied by the port.

d. Store the calculated bandwidth value in the structure {dpid, port, bandwidth}, where bandwidth is the transmission bandwidth of the port.

(3) Dynamic routing strategy

Use redundant paths in the network to reduce the possibility of network congestion. The specific steps are as follows:

a. After the controller receives the packet-in message sent by the openflow switch, it triggers the PACKETIN event, and by calling the event processing function, the controller parses out the flow identifier <srcip, dstip, srcport, dstport, proto> and records it;

B. Utilize the bandwidth usage of different links obtained in (2), select that link with the lowest bandwidth utilization rate as the forwarding path of the data flow;

c. Add the selected path to the flow table of the corresponding SDN switch, and notify the switch to forward the flow.

(4) Using the OpenFlow protocol to obtain the number of transmitted bytes of each flow, the controller sends the ofp_flow_stats_request message to the SDN switch supporting the OpenFlow protocol to obtain the number of transmitted bytes of each flow. Specific steps are as follows:

a. Every certain time interval T ₂ , the controller sends an ofp_flow_stats_request message to all SDN switches in the network, and waits for the SDN switch to respond;

b. The controller triggers the FlowStatsReceived event after receiving the response message of ofp_flow_stats, and obtains the total number of bytes transmitted by the flow by calling the event processing function;

c. Store the total number of transmitted bytes of the stream in the structure <srcip,dstip,srcport,dstport,proto,transmitted>, where transmitted is the total number of transmitted bytes.

(5) Queue scheduling strategy

Significantly reduce the transmission delay of high-priority data streams without significantly reducing the output performance of low-priority data streams. Specific steps are as follows:

a. two queues with different priorities are set at the output port of the switching device, and the switching device schedules and outputs the data in these _two queues according to the time slice T3;

b. The switching device dequeues the data in the high-priority queue first;

c. If the high-priority queue is empty at a certain moment in a time slice, transfer to the scheduling low-priority queue, and mark that the time slice has been dispatched to the low-priority queue until the time slice is used up;

d. If the high-priority queue is not empty within a time slice, the low-priority queue will not be scheduled until the time slice is used up;

e. When a certain time slice is used up, check whether the low-priority queue has not been scheduled for two consecutive time slices. If so, the next time slice will be transferred to the low-priority queue, and the low-priority queue will be marked as scheduled. step b;

f. If not, go to step b.

(6) Network data packet enqueue strategy, the specific steps are as follows:

a. Initially, all streams are queued in the high-priority queue for output;

b. When it is found in (4) that the number of transmitted bytes of a stream reaches a certain threshold, the stream will be regarded as a long data stream;

c. The controller sends the ofp_flow_mod message to the switch, and adds a flow entry in the flow table of the switch, match is the identifier of the flow, and action is an enqueue action, instructing the switch to queue long data flows into a low priority queue ;

d. When the switch receives the matching data flow, it arranges the data flow in the low priority queue;

e. The switch schedules the two queues at the output port according to the method in (5).

The data center network flow scheduling method of the present invention takes into account the scheduling of long data flows and short data flows in the network at the same time, and dynamically schedules network flows to balance the workload of each link. streams to reduce queuing delays for short streams without significantly "penalizing" long streams.

Description of drawings

FIG. 1 is a schematic diagram of the test network topology of the present invention.

Fig. 2 is a system architecture diagram of the present invention.

Fig. 3 is a flowchart of data stream scheduling in the present invention.

Fig. 4 is a flowchart of queue scheduling in the present invention.

detailed description

The specific implementation manners of the present invention will be further described below in conjunction with the accompanying drawings and technical solutions.

As shown in Figure 1, a test network is composed of SDN switches supporting the OpenFlow protocol. The bandwidth of each link in the network is 100 Mbps, and two queues with different priorities are configured for each port of the SDN switch. By default, streams are queued for delivery in the high priority queue.

As shown in Figure 2, use POX as the controller, install the scheduling module, and run two scheduled tasks to collect statistics of all links in the network and statistics of all existing data flows.

As shown in Figure 3, when the host H1 in Figure 1 sends a data flow f1 to the host H2, if the switch in the network cannot forward the flow, it will report to the POX controller and request to forward the flow. After receiving the request, POX starts to calculate the forwarding path for f1.

According to the topology information of the network, it can be seen that there are four equal-cost paths between H1 and H2. Based _on the link usage information collected by the scheduled task T1, find the path with the most idle current link and assign it to flow f1, assuming it is H1-E1-A1 -C1-A3-E2-H2. Send the flow table to switches E1, A1, C1, A3, and E2, and control E1 to forward the flow.

Timed task T ₂ collects the number of bytes sent by the stream every T ₂ time. When the number of sent bytes of a flow exceeds a certain threshold, the POX controller judges that the data flow is a large data flow. The POX controller sends the ofp_flow_mod message to the switch, and adds a flow entry in the flow table of the switch, match is the identifier of the flow, and action is an enqueue action, instructing the switch to queue long data flows into a low-priority queue. When the switch receives the subsequent matching data flow, it arranges the data flow in the low priority queue and waits for the switch to dispatch the output.

As shown in Figure ₄ , the switch schedules the data in the output port queue with T3 time as a cycle, and we call a cycle a time slice. Initially, the flag Flag is set to ₁ , and the T3 timer is started. The timer task is mainly divided into three parts:

1. When the high-priority queue is not empty, loop out the data in the high-priority queue.

2. In the process of scheduling the high-priority queue, if the high-priority queue is found to be empty, it will switch to scheduling the low-priority queue until the timer expires.

3. When the low-priority queue is not scheduled for two consecutive time slices, the next time slice is allocated to the low-priority queue.

Claims (1)

1. A data center network flow scheduling method based on time slice rotation, characterized in that: (1) Use SDN switches supporting the OpenFlow protocol to build the Internet; (2) Utilize the OpenFlow protocol to obtain the link usage between the SDN switches, and the controller obtains the link information between the SDN switches by sending the ofp_port_stats_request message to the SDN switch supporting the OpenFlow protocol; the specific steps are as follows: a. Every certain time interval T1, the controller sends an ofp_port_stats_request message to all SDN switches in the network, and waits for the SDN switch to respond; b. The controller triggers the PortStatsReceived event after receiving the response message of ofp_port_stats, and obtains the total number of bytes transmitted by the port so far by calling the event processing function; c. Calculate the difference between the total number of bytes transmitted currently and the total number of bytes transmitted last time and divide it by the time interval T1. This value is regarded as the current bandwidth occupied by the port; d. Store the calculated bandwidth value in the structure {dpid, port, bandwidth}, where bandwidth is the transmission bandwidth of the port; (3) Dynamic routing strategy a. When the controller receives the packet-in message sent by the SDN switch supporting the openflow protocol, it triggers the PACKETIN event, and by calling the event processing function, the controller parses out the flow identifier <srcip,dstip,srcport,dstport,proto> , and record it; B. Utilize the bandwidth usage of different links obtained in (2), select that link with the lowest bandwidth utilization rate as the forwarding path of the data flow; c. Add the selected path to the flow table of the corresponding SDN switch, and notify the SDN switch to forward the flow; (4) Utilize the OpenFlow protocol to obtain the transmitted bytes of each flow, and the controller obtains the transmitted bytes of each flow by sending the ofp_flow_stats_request message to the SDN switch supporting the OpenFlow protocol; the specific steps are as follows: a. Every certain time interval T2, the controller sends an ofp_flow_stats_request message to all SDN switches in the network, and waits for the SDN switch to respond; b. The controller triggers the FlowStatsReceived event after receiving the response message of ofp_flow_stats, and obtains the total number of bytes transmitted by the flow by calling the event processing function; c. Store the total number of transmitted bytes of the stream in the structure <srcip, dstip, srcport, dstport, proto, transmitted>, where transmitted is the total number of transmitted bytes; (5) Queue scheduling strategy Significantly reduce the transmission delay of high-priority data streams without significantly reducing the output performance of low-priority data streams; the specific steps are as follows: a. Two queues with different priorities are set at the output port of the SDN switch, and the SDN switch schedules and outputs the data in these two queues according to the time slice T3; b. The SDN switch prioritizes the output of the data in the high priority queue; c. If the high-priority queue is empty at a certain moment in a time slice, transfer to the scheduling low-priority queue, and mark that the time slice has been dispatched to the low-priority queue until the time slice is used up; d. If the high-priority queue is not empty within a time slice, the low-priority queue will not be scheduled until the time slice is used up; e. When a certain time slice is used up, check whether the low-priority queue has not been scheduled for two consecutive time slices. If so, the next time slice will be transferred to the low-priority queue, and the low-priority queue will be marked as scheduled. step b; f. If it is detected that the low priority queue is not scheduled for two consecutive time slices, then go to step b; (6) Network data packet enqueue strategy a. Initially, all streams are queued in the high-priority queue for output; b. When it is found in (4) that the number of transmitted bytes of a stream reaches a certain threshold, the stream will be regarded as a long data stream; c. The controller sends the ofp_flow_mod message to the SDN switch, and adds a flow entry in the flow table of the SDN switch, match is the identifier of the flow, and action is an enqueue action, instructing the SDN switch to queue long data flows to low priority in the class queue; d. When the SDN switch receives the matching data flow, it arranges the data flow in the low priority queue; e. The SDN switch schedules the two queues at the output port according to the method in (5).