CN119603231A

CN119603231A - A method for orderly traffic scheduling based on dynamic priority in data center network

Info

Publication number: CN119603231A
Application number: CN202411769376.9A
Authority: CN
Inventors: 邹绍军; 蒋毅; 曲家成; 杨天若; 刘华中; 张韬
Original assignee: Hainan University
Current assignee: Hainan University
Priority date: 2024-12-04
Filing date: 2024-12-04
Publication date: 2025-03-11

Abstract

The invention provides an ordered flow scheduling method based on dynamic priority in a data center network, which comprises the steps of carrying out priority distribution on each data packet of a sender, collecting flow information in real time by a switch and detecting whether a priority queue is congested, and scheduling forwarding of the data packets according to the priority of the data packets and congestion conditions of the priority queue when the switch receives the data packets. According to the method, data packets of different types of flows are cached by adopting different priority queues, so that the data packets of the urgent flows are not blocked by the data packets of the non-urgent flows, meanwhile, the switch utilizes a non-disordered flow scheduling mechanism based on dynamic priorities, so that the data packets are ensured to arrive at a receiving party in sequence, the flow completion time and the deadline miss rate are reduced to the greatest extent, and the transmission performance of a data center network can be greatly improved.

Description

Ordered flow scheduling method based on dynamic priority in data center network

Technical Field

The invention relates to the technical field of flow scheduling, in particular to an ordered flow scheduling method based on dynamic priority in a data center network.

Background

With the explosive growth of new generation information technologies such as cloud computing, big data, the internet, and artificial intelligence, more and more various applications and services (web search, recommendation systems, online retail, etc.) are migrating to data center Networks (DATA CENTER Networks, DCNs). These applications and services typically generate a large number of mixed traffic (i.e., long and short flows) of different sizes during operation. Many of these flows have deadline requirements, and such flows are referred to as deadline flows. In addition, most of the mixed flows are short flows, and strict requirements are imposed on delay. In short, even small network delays can severely impact the performance of the application and the revenue of the cloud service provider. In order to obtain a good user experience, researchers at home and abroad have successively proposed various traffic scheduling mechanisms to optimize transmission performance with the aim of minimizing the flow completion time (Flow Completion Time, FCT) and deadline miss rate (DEADLINE MISS RATE, DMR).

Hybrid traffic scheduling is one of the most important key issues in modern data centers, which relates to how to efficiently manage and schedule different types of data flows to ensure optimal utilization of network resources and to greatly improve quality of service. The existing mixed flow scheduling method can be mainly divided into two main categories, namely a solution based on a single queue and a solution based on multiple queues. While existing solutions can provide effective scheduling strategies in some cases, each has certain limitations. These limitations limit their potential in achieving the desired transmission performance. The data packets of the urgent flow in the single-queue solution can suffer from larger queuing delay and can not finish data transmission within a set time, and the multi-queue solution has serious data packet rearrangement problem, thereby starting a large amount of unnecessary quick retransmission, reducing the sending rate of the flow and further reducing the network transmission performance.

In summary, the existing traffic scheduling mechanism has the problem that different types of traffic cannot be effectively isolated, or that the data packets arrive at the receiving end in sequence cannot be effectively guaranteed. In other words, existing traffic scheduling schemes have difficulty achieving both low queuing delay and high throughput for urgent flows, especially in networking scenarios where data flows migrate from low priority queues to high priority queues.

Disclosure of Invention

The invention aims to provide an ordered flow scheduling method based on dynamic priority in a data center network, which reasonably sets the priority of a data packet according to different types of flows, dynamically adjusts the priority according to the network state and schedules the forwarding order of the data packet by using an ordered transmission mechanism, so that the data packet of a mixed flow can still arrive at a receiving party in order when the priority is changed.

In order to achieve the above object, the present invention provides a method for scheduling ordered traffic based on dynamic priority in a data center network, the method comprising:

Performing priority allocation for each data packet of the sender;

the exchanger collects flow information in real time and detects whether congestion occurs in the priority queue;

When the exchanger receives the data packet, the exchanger dispatches the forwarding of the data packet according to the priority of the data packet and the congestion condition of the priority queue.

Further, the priority allocation is performed for each data packet of the sender, which specifically includes the following operations:

Judging the flow type in the data center network to obtain flow type information;

Calculating the priority of the data packet according to the flow type information;

The priority of the data packet is written into the header of the data packet.

Further, traffic types include flows with deadlines, flows without deadlines but of known size, flows without deadlines, or flows of unknown size.

Further, the method further comprises:

Each switch is configured to maintain a flow table configured to record information for each active flow and a port queue table configured to record status information for all output ports.

Further, the switch receives the flow information in real time and detects whether congestion occurs in the priority queue, which specifically includes:

when the exchanger receives a first data packet of any new stream, five-tuple information according to the head of the first data packet is used as an input parameter of a hash function;

creating an entry in a flow table for the corresponding new flow according to the output result of the hash function;

Recording a stream identification ID, the number of arriving data packets, the priority of the last data packet and the queue position thereof, and the priority queue of the last data packet in the created entry;

and when the switch receives one data packet, updating relevant parameters of corresponding entries in the flow table in real time.

The exchanger updates the parameters of the items in the port queue list every other round trip time RTT, and each item records the port ID, the queue length, the average arrival rate of the flow and the slope of the burst flow evolution;

When the switch receives the data packet with the lifting priority, the information such as the current queue length, the average arrival rate of the flow, the gradient of the flow evolution and the like is comprehensively considered, and whether congestion occurs in the high-priority queue or not is predicted when the data flow with the lifting priority is migrated from the low-priority queue to the high-priority queue.

Further, when the switch receives the data packet, the switch schedules forwarding of the data packet according to the priority of the data packet and congestion condition of the priority queue, and specifically includes:

When the exchanger receives a data packet, the priority of the head of the data packet is extracted and compared with the priority recorded in the flow table;

If the priority of the received data packet is equal to or lower than the priority in the flow table, the switch allows the data packet to enter a corresponding priority queue according to the priority information recorded by the head of the data packet;

if a packet of elevated priority is received, the switch performs a out-of-order traffic scheduling mechanism (DFS) to process the packet.

Further, the switch executes an unordered traffic scheduling mechanism to process the data packet, and specifically includes:

the switch finds out a corresponding priority queue according to the priority of the data packet and detects whether congestion occurs in the priority queue;

judging whether the preset condition is met, if the preset condition is not met, setting the priority of the data packet as the priority recorded in the flow table, and enabling the data packet to enter a corresponding priority queue;

If the preset condition is met, the switch queries the flow table, obtains the priority queue of the corresponding flow and the position of the last data packet of the flow in the priority queue, gives the highest priority to the corresponding priority queue in a limited time, forwards the data packet in the priority queue preferentially until the last data packet of the flow in the priority queue is forwarded, and restores all the priority queues to the default priority.

Further, the preset conditions include the following three conditions:

The priority of the data packet is raised;

the high priority queue into which the data packet is to enter is free from congestion;

all the flight data packets which are in the same flow as the data packets to be processed by the switch are cached in the same priority queue of the output port of the switch, and the flight data packets are data packets which are sent by a sender but not received confirmation;

the switch allows flow to migrate from the low priority queue to the high priority queue only if the three conditions are met simultaneously.

Compared with the prior art, the invention has the beneficial effects that:

The ordered flow scheduling method based on dynamic priority in the data center network provided by the invention adopts different priority queues to buffer data packets of different types of flows, ensures that the data packets of the urgent flows are not blocked by the data packets of the non-urgent flows, and in addition, the switch utilizes a non-disordered flow scheduling mechanism based on dynamic priority to schedule the forwarding of the data packets, ensures that the data packets arrive at a receiving party in sequence, reduces the flow completion time and deadline error rate to the greatest extent, and can greatly improve the transmission performance of the data center network.

Drawings

In order to more clearly illustrate the technical solutions of the embodiments of the present invention, the drawings required for the description of the embodiments will be briefly described below, and it is apparent that the drawings in the following description are only preferred embodiments of the present invention, and other drawings may be obtained according to these drawings without inventive effort for a person skilled in the art.

Fig. 1 is a schematic diagram of a prior art single queue and multiple queue solution.

Fig. 2 is a schematic diagram of experimental test results for a prior art single queue solution.

Fig. 3 is a schematic diagram of experimental test results of a prior art multiple queue solution.

Fig. 4 is a schematic diagram of an overall framework of an ordered transmission traffic scheduling algorithm based on dynamic priority according to an embodiment of the present invention.

Fig. 5 is a schematic diagram of an out-of-order traffic scheduling mechanism according to an embodiment of the present invention.

Fig. 6 is a schematic diagram of average flow completion times for different flow scheduling schemes provided by an embodiment of the present invention.

FIG. 7 is a schematic diagram of the performance of a method provided by an embodiment of the present invention under network search workload.

FIG. 8 is a schematic diagram of the performance of a method provided by an embodiment of the present invention under a data mining workload.

Fig. 9 is a schematic overall flow chart of an ordered flow scheduling method based on dynamic priority in a data center network according to an embodiment of the present invention.

Detailed Description

The principles and features of the present invention are described below with reference to the drawings, the illustrated embodiments are provided for the purpose of illustrating the invention and are not to be construed as limiting the scope of the invention.

Existing traffic scheduling mechanisms can be broadly divided into two categories, single queue based traffic scheduling mechanisms and multi-queue based traffic scheduling mechanisms. The method comprises the following steps:

(1) The core idea of the single queue scheme is that each switch caches all data packets forwarded by the same output port in a single queue, and a sender adjusts the sending rate of a mixed flow according to an optimization target and configures the priority of each data packet so as to meet the differentiated requirements of different types of traffic as far as possible. Typical representative works include D ² TCP, DA & FD and AIFO. Specifically, D ² TCP adjusts the transmission rate in combination with the congestion degree on the transmission path and the deadline of the data flow, prevents the urgent flow from performing an aggressive congestion avoidance operation when the network is congested, and minimizes the deadline miss rate. In addition, the DA & FD comprehensively considers the deadline and the duration of the data stream, and optimizes the transmission performance by using a dual evaluation mechanism. However, a common problem with these single queue based solutions is that when the urgent and non-urgent flows compete for bandwidth resources on the same transmission path, the packets of the urgent flow are inevitably blocked by the packets of the non-urgent flow, severely degrading its network performance.

As shown in fig. 1 (a), the switch buffers all packets forwarded to the same egress port in the same queue, whether or not the data flow is urgent. Obviously, when the urgent and the non-urgent flows compete for bandwidth resources on the same transmission path, the packets of the urgent flow are inevitably blocked by the packets of the non-urgent flow. At this time, packets of the urgent flow may suffer from a large queuing delay. Worse still, the urgent flow may not complete the data transmission within a prescribed time, resulting in a higher deadline loss rate. Similarly, packets of short flows may be blocked by packets of long flows, failing to achieve a lower average flow completion time. In a network scenario with higher network load, the problem that the urgent flow (short flow) is blocked by the non-urgent flow (long flow) is more prominent, and the network transmission performance is seriously reduced.

In order to intuitively illustrate the limitations of the existing single-queue traffic scheduling scheme, the invention adopts a network simulation simulator (Network Simulator version, NS2) to carry out experimental tests under different network scenes. In testing, the present invention uses a typical many-to-one topology in a data center network (i.e., multiple senders and one receiver are connected to the same switch), and the round trip propagation delay, packet size, and link capacity of the transmission path are set to 100 μs, 1500B, and 10Gbps, respectively. A total of 100 streams share a bottleneck link in this test, including short and long streams with or without deadlines and their arrival times follow poisson distribution. The invention measures the deadline miss rate, slowdown, the average stream completion time of the short stream and the 99 minutes bit stream completion time by adjusting the quantity of the last-period current limit.

As shown in fig. 2 (a), as the number of deadline streams increases, the deadline miss rate and Slowdown also increase. Similarly, fig. 2 (b) shows that the average stream completion time and the 99-minute bitstream completion time of the short stream both increase with the increase in the number of cut-off time streams. The root cause is that when some flows near the expiration date increase their sending rate, congestion on the bottleneck link is exacerbated by their sharing of queues with other non-urgent flows, ultimately resulting in urgent flows suffering a greater deadline miss rate and flow completion time.

(2) Multiple queue based traffic scheduling mechanism to overcome the deficiencies of single queue solutions, researchers have proposed various multiple queue traffic scheduling solutions, typical representative efforts include Karuna, PIAS, aemon, HPSTOS and HybridPass. The core idea of these solutions is to place data packets of different traffic types in different priority queues, which can effectively prevent urgent (short flows) from being blocked by non-urgent (long flows). For example Karuna employs a minimum-impact transport mechanism to meet deadline flow-limiting while minimizing impact on flow completion times of non-deadline flow-limiting. Similarly Aemon is a mixed stream transport with no information. The basic idea is that the sender dynamically adjusts the sending window according to the urgency of the flow, and the switch adopts a two-stage priority mechanism to schedule the mixed flow. However, when non-urgent flows migrate from low priority queues to high priority queues, existing multi-queue based solutions raise the problem of large amounts of data packets out of order, thereby causing the sender to trigger unnecessary fast retransmissions and failing to achieve the expected transmission performance.

As shown in fig. 1 (b), at time t=0, packets of different traffic types enter queues of different priorities, effectively solving the problem of urgent (short stream) blocking by non-urgent (long stream). However, existing multi-queue traffic scheduling has serious packet reordering problems. For example, at time t=1, flow f3 near the deadline increases priority and the switch places the next packet (from packet 2) of flow f3 into the high priority queue. Obviously, if the switch forwards the packets with strict priority, it will necessarily result in a large number of packets going out of order to the receiver. However, serious packet reordering can cause the sender to trigger a large number of unnecessary fast retransmissions, reducing the sending rate of the stream, and thus reducing the network transmission performance.

The invention intuitively displays the performance problems of multi-queue flow scheduling through experimental tests. In this test, there are two queues (i.e., one high priority queue and one low priority queue) per port of the switch. In addition, the present invention counts the number of out-of-order packets, slowdown, the average stream completion time of the short stream, and the 99 minutes bit stream completion time by varying the number of competing streams.

Fig. 3 shows that as the number of competing streams increases from 10 to 60, all measured performance metrics become larger, meaning that network performance becomes worse. The main reason is that existing multi-queue solutions result in a large number of packets arriving out of order at the receiver and generating corresponding duplicate ACK feedback to the sender when the data flow is migrated from low priority to high priority queues, ultimately resulting in the sender triggering a large number of unnecessary fast retransmissions, thus increasing the flow completion time.

The invention performs deep exploration and analysis aiming at the mixed flow scheduling algorithm, and discovers that the existing solution can not effectively isolate different types of flows, ensure that the data packets arrive at the receiver in sequence, and seriously reduce the network transmission performance. To this end, the present invention proposes a Dynamic Priority-based traffic scheduling mechanism (DPOT) to solve the above-mentioned problems, aiming at minimizing the flow completion time and deadline loss rate. In one aspect, the switch employs different priority queues to buffer packets of different types of flows, ensuring that packets of an urgent flow are not blocked by packets of a non-urgent flow. On the other hand, when a certain flow is migrated from a low priority queue to a high priority queue, the switch utilizes an ordered transmission mechanism based on dynamic priority to schedule data packet forwarding, so that the data packets are ensured to arrive at a receiving party in sequence, and the flow completion time and the deadline miss rate are reduced to the greatest extent.

Fig. 4 shows an overall framework of an ordered transmission traffic scheduling algorithm based on dynamic priority. The algorithm reasonably sets the priority of the data packet according to different types of traffic, dynamically adjusts the priority according to the network state and utilizes an ordered transmission mechanism to schedule the forwarding order of the data packet, so that the data packet of the mixed flow can still arrive at a receiving party in order when the priority of the mixed flow changes. The algorithm mainly comprises three modules, namely a priority distribution module of a sender, a congestion detection module of a switch and a disorder-free flow scheduling module.

Specifically, an embodiment of the present invention provides a method for scheduling ordered traffic based on dynamic priority in a data center network, where the method includes the following operations:

s101, carrying out priority allocation for each data packet of a sender.

This step is implemented by the sender's priority assignment module. The module is deployed between the transport layer and the network layer and is responsible for assigning a priority to each data packet, the basic idea of which is that the sender calculates the priority of each data packet and writes it in the packet header when the data packet passes from the transport layer to the network layer. The priority of the data packet can be flexibly allocated according to the traffic scheduling target. For example, to minimize the deadline loss rate, the sender should calculate packet priority in combination with the remaining stream size and deadline, and more urgent streams should be assigned higher priority.

S102, the switch collects flow information in real time and detects whether congestion occurs in the priority queue.

This step is implemented by a congestion detection module of the switch, which is responsible for collecting flow information in real time and detecting if congestion occurs in the priority queues. The core idea is that the switch counts important information of active flows, including the number of data packets, priority and the like. Once the exchanger receives the data packet with the improved priority, the congestion detection module immediately combines the collected flow information and the state of the priority queue, predicts whether the high priority queue is congested, and accurately judges whether the priority of the data flow can be improved without causing the data packet rearrangement of the receiver.

And S103, when the switch receives the data packet, scheduling forwarding of the data packet according to the priority of the data packet and the congestion condition of the priority queue.

The step is realized by a non-out-of-order traffic scheduling module. When a packet arrives at the switch, the packet enters a priority queue corresponding to the egress port according to the priority carried by the packet header. In addition, the packets in the queues with different priorities follow strict priority scheduling, and the packets in the same queue are forwarded according to a First-in-First-out (FIFO) strategy.

As an alternative implementation manner, the priority allocation is performed for each data packet of the sender, which specifically includes the following operations:

s201, judging the flow type in the data center network, and obtaining flow type information.

S202, calculating the priority of the data packet according to the flow type information.

S203, writing the priority of the data packet into the head of the data packet.

In this embodiment, traffic types are classified into three types, a stream with a deadline, a stream without a deadline but of known size, a stream without a deadline, or a stream of unknown size.

A stream with deadlines its main performance indicator is the deadline miss rate. Since the size of some deadline constraints may not be known, the priority of the packets cannot be calculated based on the remaining stream size and the remaining time. For this purpose, the sender calculates its urgency using the elapsed time T _e and deadline T _d of the deadline current limit

Wherein T _e can be calculated by subtracting the start time of the deadline current limit from the current time.

Obviously, the higher the urgency of deadline throttling, the higher the priority of its packets should be. Therefore, in this embodiment, the priority of the packets of the flow close to the deadline is dynamically adjusted according to the urgency of the deadline flow limitation, so that the packets of the flow close to the deadline are preferentially forwarded, and the deadline miss rate is reduced to the greatest extent.

Streams of known size without deadlines-such streams do not have stringent delay requirements, but smaller stream completion times are generally desirable. Since the size of these flows is generally known prior to transmission, the flows can be directly assigned to different priority queues using SJF scheduling policies, thereby minimizing flow completion time.

This embodiment leverages the switch's multi-priority queues to model SJF scheduling policies for flows without deadlines or of unknown size, with the aim of minimizing flow completion times. In particular, packets of about 80% of the flows in a data center network are initially assigned a higher priority, considering that these flows are short flows. As these flows send an increasing number of bytes, their subsequent packets are gradually demoted from the high priority queue to the low priority queue, which can effectively reduce the flow completion time for non-deadlines or previously unknown sized traffic.

In this embodiment, each switch is configured to maintain a flow table configured to record information for each active flow and a port queue table configured to record status information about all output ports.

On this basis, the specific process of congestion detection is as follows:

When the switch receives the first data packet of any new stream, it uses the five-tuple information of the data packet header as the input parameter of the function, and then creates an entry for the new stream in the stream table according to the output result of the hash function. For each entry, it records the flow identification ID, the number of arriving packets, the priority of the last packet and its queue position (i.e. queue length), the priority queue in which the last packet is located. And updating relevant parameters in corresponding entries in the flow table in real time when the switch receives one data packet.

In addition, each entry of the port queue table records the port ID, queue length, average arrival rate of traffic, and slope of bursty traffic evolution. To limit computation and memory overhead, the switch periodically updates the relevant parameters in the port queue table every other RTT. When the switch receives the data packet with the lifting priority, the information such as the current queue length, the average arrival rate of the flow, the gradient of the flow evolution and the like is comprehensively considered, and whether congestion occurs in the high-priority queue or not is predicted when the data flow with the lifting priority is migrated from the low-priority queue to the high-priority queue. In this embodiment, if the length of the priority queue reaches a predetermined threshold (e.g., ECN mark threshold) within a specified duration, the priority queue is determined to be a congestion queue, otherwise the queue is considered to be congestion free.

As an optional implementation manner, when the switch receives a data packet, the switch schedules forwarding of the data packet according to the priority of the data packet and the congestion condition of the priority queue, and specifically includes:

s301, when the switch receives a data packet, the priority of the head of the data packet is extracted and compared with the priority recorded in the flow table.

S302, if the priority of the received data packet is equal to or lower than the priority in the flow table, the switch allows the data packet to enter a corresponding priority queue according to the priority information recorded by the head of the data packet.

S303, if a data packet with a higher priority is received, the switch executes a Disorder traffic scheduling mechanism (DFS) to process the data packet.

The packet priority of any one stream may remain unchanged, decrease or increase during the data transmission. Packets may arrive at the receiver in sequence when the priority of the data stream is unchanged or decreases. However, for streams near the deadline, the sender may gradually increase the priority of its packets. Once these packets with elevated priorities reach the switch, and simply from the lowest priority to a higher priority according to their priorities, there is a potential for a large number of packets to arrive at the receiver out of order, causing the sender to trigger unnecessary fast retransmissions and thus compromising network transmission performance. For this reason, this embodiment designs an out-of-order traffic scheduling mechanism (DFS) to solve the above problem.

Specifically, the switch executes an unordered traffic scheduling mechanism to process data packets, including the following operations:

S401, the switch finds a corresponding priority queue according to the priority of the data packet, and detects whether congestion occurs in the priority queue.

S402, judging whether preset conditions are met:

If the preset condition is not met, setting the priority of the data packet as the priority recorded in the flow table, and allowing the data packet to enter a corresponding priority queue;

The preset conditions include the following three conditions:

(a) The priority of the data packet is raised;

(b) The high priority queue into which the data packet is to enter is free from congestion;

(c) All the flight data packets of the same flow as the data packets to be processed by the switch are cached in the same priority queue of the output port of the switch, and the flight data packets are data packets which are sent by a sender but not confirmed.

To eliminate the negative effects of packet misordering, the switch allows flow to migrate from the low priority queue to the high priority queue only if the three conditions are met simultaneously.

Wherein condition (a) is intended to ensure that an upgrade priority level of the flow is necessary, condition (b) indicates that a non-congested high priority queue is available, and condition (c) ensures that the flight packets in any one flow are located in at most two different priority queues at any time.

In this embodiment, when a packet arrives, the switch extracts the priority of the packet header and compares it with the priorities recorded in the flow table. On the one hand, if the priority of the arriving data packet is equal to or lower than the priority in the flow table, the switch makes the arriving data packet enter the corresponding queue according to the priority carried by the data packet head. On the other hand, as shown in fig. 5, when a packet of elevated priority arrives, the switch may implement a DFS mechanism to process the packet. Specifically, the switch finds a corresponding priority queue according to the priority of the data packet, and detects whether the queue is congested. If any one of the three conditions cannot be met, the switch sets the priority of the data packet as the priority recorded in the flow table and makes the data packet enter the corresponding priority queue. Otherwise, the switch immediately looks up the flow table to obtain the priority queue in which the flow is located and the position of the last packet of the flow in the queue. The switch then temporarily assigns the highest priority to the queue and forwards the packets in the queue preferentially until the last packet in the queue for the flow is forwarded. At this time, all queues recover the default priority and continue forwarding the data packets in the high priority queues. It should be noted that, during the execution of the DFS mechanism, the packets of other flows still enter the corresponding priority queues according to the priority information of the header thereof.

In short, DFS mechanisms are a traffic scheduling strategy with dynamically adjusted queue priorities to ensure that packets arrive at the receiver in order, thus avoiding unnecessary fast retransmissions.

The present invention will verify the flow completion time of the prior art single queue solutions, multiple queue solutions and the methods provided by embodiments of the present invention by means of a model.

For ease of analysis, let K, m, t _d、RTT_min denote ECN marking threshold, number of switches on the transmission path, transmission delay of a single packet, and round trip propagation delay of the transmission path, respectively, assuming that there are n ₁ urgent flows and n ₂ non-urgent flows competing for bandwidth resources on the bottleneck link.

(1) Single queue traffic scheduling model

Since the transport protocol of a data center network typically uses ECN as the congestion signal, the queue length of each egress port on the bottleneck link is typically maintained around the ECN marking threshold K. To simplify the analysis, assuming that flows in the same queue fairly share bandwidth resources, the maximum congestion window for each flowThe method comprises the following steps:

Thus, queuing delay of data packets Real-time round trip propagation time Let S _i denote the size of the ith stream, its stream completion time is:

based on the above analysis, the average flow completion time for the single queue solution is calculated as follows:

(2) Multi-queue traffic scheduling model

For a multi-queue traffic scheduling scheme, it is assumed that initially all flows compete for bandwidth resources in the low priority queue, and then n ₁ urgent flows switch from the low priority queue to the high priority queue. Obviously, n ₁ urgent flows compete in the high priority queue for the maximum window that can be reachedIs thatHowever, these urgent flows inevitably undergo packet reordering, which tends to cause unnecessary fast retransmission, reducing the transmission rate thereof. Assuming that the probability of triggering fast retransmissions is p, the average congestion window per urgent flow is:

thus, the queuing delay of the urgent flow data packet is Stream completion time of ith urgent streamIt can be calculated as:

for each non-urgent flow, its maximum window is Queue delay isBecause the priority of the urgent flow is higher than that of the non-urgent flow, the switch forwards the data packet of the urgent flow before starting to forward the non-urgent flow. In the forced flow, the wake completion time is(1.Ltoreq.i.ltoreq.n ₁). Thus, the flow completion time of the jth non-urgent flowIt can be calculated as:

according to equations (5) and (6), the average flow completion time for all flows is:

(3) Unordered multi-queue traffic scheduling model

For the unordered multi-queue flow scheduling mechanism, the method can effectively avoid unnecessary quick retransmission, and the maximum window of each urgent flow isThus, the queuing delay for an urgent flow is Q _d＝K×t_d, and the flow completion time for the ith urgent flow can be calculated as:

Similar to equation (6), the flow completion time of the j-th non-urgent flow It can be calculated as:

wherein, Wake completion time for the urgent flow, which is a value ofAccording to equations (8) and (9), the average flow completion time for all flows is:

As shown in fig. 6, the present invention plots the urgent flow and the average flow completion time for all flows according to the model analysis described above. Wherein, K, m, RTT _min、p、t_d are set to 65, 3, 10 μs, 0.8 and 0.3 μs, respectively. In fig. 6 (a), there are 30 streams competing for bandwidth resources on the same transmission path, where the number of urgent streams is 20. Further, the size of the urgent stream is gradually increased from 10 packets to 40 packets, and the average stream completion time is calculated, respectively. In fig. 6 (b), we record the average flow completion time for all flows at different urgent flow percentages. Wherein the total number of urgent and non-urgent flows is still 30, and the sizes of the urgent and non-urgent flows are 40 and 200 data packets, respectively. As expected, the single queue solution achieves the maximum flow completion time in all scenarios, while the present solution achieves the minimum flow completion time.

We comprehensively evaluate the transmission performance of the present invention using two typical workloads in a data center network (i.e., network search and data mining workloads). In this test, a typical Leaf-Spine network topology was used, which comprised 9 Leaf switches, 4 Spine switches and 144 servers. Wherein each Leaf switch is interconnected with 16 servers, with link capacities and link delays of 40Gbps and 10 μs, respectively. In addition, the total buffer size of each switch output port is 320KB, the number of queues of each output port in the multi-queue scheme is 4, and the ecn marking threshold is 20 data packets. In this test, the DPOT of the present invention was compared with representative, up-to-date correlation jobs D ² TCP, DA & FD, aecon, and Karuna, and the deadline miss rates and average flow completion times for all flows, short flows (.ltoreq.100 KB), and long flows (> 100 KB) were measured. The experimental results are shown in fig. 7 and 8.

As can be seen from fig. 7 and fig. 8, compared with other traffic scheduling methods, the method (DPOT) according to the embodiment of the present invention achieves the best performance on all measurement indexes under different network loads. As shown in fig. 8 (b), the average flow completion time of all flows obtained by DPOT was reduced by 45%, 30% and 40% compared to D ² TCP, DA & FD, aecon and Karuna, respectively. The main reason is that the present invention buffers data packets of different traffic types by using different priority queues and employs a non-out-of-order traffic scheduling mechanism to schedule data packet forwarding. Thus, the blocking of the cut-off time/short stream by the non-cut-off time/long stream can be effectively prevented, and the unordered arrival of the data packet at the receiving party can be ensured. Finally, the method provided by the embodiment of the invention obtains the minimum deadline miss rate and the stream completion time, thereby greatly improving the network transmission performance.

Referring to fig. 9, in some implementations, the method provided by the embodiments of the present invention may be implemented by:

Step 1, a sender calculates the priority of each data packet according to information such as traffic types and the like;

step 2, writing the calculated priority into the head of the data packet;

Step 3, the exchanger detects the network state and the information related to the active flow in real time;

Step 4, the exchanger receives the data packet;

step 5, extracting priority information of the packet head of the data packet;

step 6, judging whether the priority of the data packet is improved;

step 7, if the priority of the data packet is improved, further judging whether congestion occurs in a high priority queue into which the data is to enter;

Step 8, if the high priority queue is not congested, the data packet enters the corresponding high priority queue;

Step 9, if the high priority queue is congested, the flow table is searched to acquire the priority of the previous data packet of the flow and the acquired priority is updated to the data packet;

step 10, the data packet enters a corresponding priority queue;

step 11, updating a flow table and a port queue table;

Step 12, the exchanger forwards the data packet;

step 13, judging whether the data packet is forwarded completely or not;

Step 14, if the data packet is not forwarded, jumping to step 12, otherwise, ending.

The foregoing description of the preferred embodiments of the invention is not intended to limit the invention to the precise form disclosed, and any such modifications, equivalents, and alternatives falling within the spirit and scope of the invention are intended to be included within the scope of the invention.

Claims

1. A method for ordered traffic scheduling based on dynamic priorities in a data center network, the method comprising:

Performing priority allocation for each data packet of the sender;

2. The method for ordered traffic scheduling based on dynamic priorities in a data center network according to claim 1, wherein the priority allocation is performed for each packet of the sender, specifically comprising the following operations:

The priority of the data packet is written into the header of the data packet.

3. A method of ordered traffic scheduling based on dynamic priorities in a data center network according to claim 2, wherein the traffic types include deadlines, non-deadlines but of known size, non-deadlines or non-known size.

4. The method for dynamic priority based ordered traffic scheduling in a data center network of claim 1, further comprising:

5. The method for ordered traffic scheduling based on dynamic priorities in a data center network according to claim 4, wherein the switch collects flow information in real time and detects whether congestion occurs in the priority queue, specifically comprising:

6. The method for ordered traffic scheduling based on dynamic priorities in a data center network according to claim 5, wherein the switch collects flow information in real time and detects whether congestion occurs in a priority queue, specifically comprising:

7. The method for scheduling ordered traffic based on dynamic priority in a data center network according to claim 4, wherein when the switch receives a data packet, the switch schedules forwarding of the data packet according to the priority of the data packet and congestion of a priority queue, and specifically comprises:

8. The method for ordered traffic scheduling based on dynamic priority in a data center network according to claim 7, wherein the switch performs an unordered traffic scheduling mechanism to process the data packets, specifically comprising:

9. The method for ordered traffic scheduling based on dynamic priorities in a data center network according to claim 1, wherein the preset conditions include the following three conditions:

The priority of the data packet is raised;