Method and apparatus for scheduling for packet-switched networks

Scheduling method and device for packet switching network

<p>100. . . node</p><p>102. . . Input port</p><p>104. . . processor</p><p>106. . . Packet arrives at the module</p><p>108. . . Queue module with pre-reordering order</p><p>110. . . Packet leaves the module</p><p>122. . . Output port</p><p>114. . . Classification submodule</p><p>115. . . Queue sub-modules by priority</p><p> 112 ₁ ~112 _n . . . Stream queue </p><p> 116 ₁ ~116 _z . . . Priority queue </p><p>118. . . Service submodule</p><p>120. . . Service table</p>

Figure 1 shows a block diagram of the structure of a node. The structure of this node is constructed according to one of the principles of the present invention with a round-robin method of pre-reordered balances.

Figure 2 illustrates a packet scheduling method according to the principles of the present invention.

Figure 3 shows a packet transmission method according to the principles of the present invention.

Figure 4a shows the operation of the conventional balance round robin method, and compares it with the conventional weighted fair queue method.

Figure 4b illustrates the operation of the present invention using the balance round robin method with pre-reordering order, under the same packet input mode and assumptions as in Figure 4a.

Figures 5 to 8 are comparison graphs of various performance simulation results, which are used to compare performance simulation results of the following methods: according to the present invention, the embodiment of the balance round-robin method using the pre-reorganized sequence, the balance round-robin method, and self-provided The fair queue method of the clock.

Figure 9 is a diagram showing the relationship between performance and the number of priority queues according to an embodiment of the present invention. The number of priority queues varies with the specific needs of a communications environment.

The present invention relates to data packet scheduling, and particularly relates to a packet scheduling method and device applied to a packet network.

In order to meet the needs of high-traffic packet transmission, a variety of packet scheduling algorithms have been proposed in recent years to minimize the delay time and take into account the fairness of scheduling. However, most of these algorithms are only applicable to packets of fixed size. What's more, when the number of streams increases, the performance of these algorithms is not good, even those algorithms that are not limited to packets of fixed size.

In the conventional Deficit Round Robin (DRR) method, the packet size is variable. According to the round-robin method, a node has several streams flowing into the node, and the node selects packets from the queues corresponding to these streams in a circular manner, and sends them out of the node. After each cycle, each stream will receive a non-continuously increasing credits, such as a credit with a byte as an incremental unit. This credit can be called a quantum. One disadvantage of the round-robin method is that it requires a very large quantum number, which is usually several times as large as the maximum packet size in a packet of a stream. To illustrate this problem, Table 1 lists the traffic parameters of the four signal streams entering a node and the quantum number corresponding to each stream.

<tables><img file="TW542960B_D0001.tif" /></tables>

The data in Table 1 is obtained under the assumption that 4 signal streams share the same link, where the capacity of this link is 160 megabits per second. As shown in Table 1, the magnitude of the quantum number of a signal stream is quite large, and is related to the maximum packet size of the signal stream. For example, the signal stream D has a quantum number whose size value is 25.6 times (2560/100) of the largest packet size value. Since the balance round-robin method has a disadvantage that it requires a very large quantum number, the performance of this algorithm is compared with other algorithms, such as the self-clocked fair queuing method (Self-Clocked Fair Queuing, SCF0) and weighted fair queuing (Weighted Fair Queuing, WFQ), its performance is low.

In this way, if the size of the quantum number is reduced, it will increase many problems, and it is generally useless. For example, if a node applies the balance round robin method, if during a certain cycle of selecting packets, after all packets of the stream are queued to the corresponding queue, the size of the quantum number is reduced, this The method will cause this node to fail to select the packet that should be forwarded. Moreover, it will seriously delay the scheduling work of this node, and make the performance worse. It can be seen that in a node that uses the round-robin method, simply reducing the value of the quantum number used therein has no effect.

It can be seen from the above-mentioned problems of the conventional technology that the conventional scheduling method cannot effectively process a data stream with a variable packet size, and its performance is not good.

The purpose and summary of the invention

In view of this, the purpose of the present invention is to provide a packet scheduling method and device, which is not limited to packets with a predetermined packet size, and has good performance, and when the number of signal streams is large, Still has good performance.

According to the purpose of the present invention, a packet scheduling method is provided. The packet scheduling method includes the following steps: (a) receiving a packet; (b) identifying a stream of the packet; (c) according to the identified packet The data stream, classify the packet; and (d) buffer and store the packet in one of the multiple queues according to the classification result of the packet.

According to the objective of the present invention, a packet scheduling system is provided. The packet scheduling system includes: an input unit, an arrival module, a classifier, a service module, and an output unit. The input unit is used to receive multiple packets. The arrival module is used to identify a signal flow corresponding to each of these packets. The classifier is used to assign each of these packets to one of a plurality of queues according to the identified traffic. The service module is used to select one of the queues according to the order of a hierarchical system. The output unit is used to output a packet from the queue selected by the service module.

According to the objective of the present invention, a packet scheduling device is provided. The packet scheduling device includes: a receiving device, an identifying device, a classification device, and a buffer storage device. This receiving device is used to receive a packet. The identification device is used to identify a stream to which the packet belongs. The classification device is used to classify the packet according to the identified signal flow. The buffer storage device is used to store the packet in one of a plurality of queues according to the classification result of the packet.

In order to make the above-mentioned objects, features, and advantages of the present invention more obvious and understandable, a preferred embodiment is specifically cited below, and is described in detail as follows in conjunction with the accompanying drawings:

Schematic description

Figure 1 shows a block diagram of the structure of a node. The structure of this node is constructed according to one of the principles of the present invention with a round-robin method of pre-reordered balances.

Figure 2 illustrates a packet scheduling method according to the principles of the present invention.

Figure 3 shows a packet transmission method according to the principles of the present invention.

Figure 4a shows the operation of the conventional balance round robin method, and compares it with the conventional weighted fair queue method.

Figure 4b illustrates the operation of the present invention using the balance round robin method with pre-reordering order, under the same packet input mode and assumptions as in Figure 4a.

Figures 5 to 8 are comparison graphs of various performance simulation results, which are used to compare performance simulation results of the following methods: according to the present invention, the embodiment of the balance round-robin method using the pre-reorganized sequence, the balance round-robin method, and self-provided The fair queue method of the clock.

Figure 9 is a diagram showing the relationship between performance and the number of priority queues according to an embodiment of the present invention. The number of priority queues varies with the specific needs of a communications environment.

Symbol description of main components

100. . . node

102. . . Input port

104. . . processor

106. . . Packet arrives at the module

108. . . Queue module with pre-reordering order

110. . . Packet leaves the module

122. . . Output port

114. . . Classification submodule

115. . . Queue sub-modules by priority

112 ₁ ~112 _n . . . Stream queue

116 ₁ ~116 _z . . . Priority queue

118. . . Service submodule

120. . . Service table

Preferred embodiment

The following embodiments will provide a pre-ooder deficit round robin (PDRR) architecture in accordance with the spirit of the present invention, which is applied to a packet switching network. This architecture is used to implement a scheduling method that minimizes the delay time and maintains fairness. In most cases, that is, when the number of streams increases, the embodiment of the present invention has a time complexity of 0(1) per packet (0(1) per-packet time complexity), and It can be applied to the occasions of packets of variable size.

In addition, the embodiments of the present invention will be tested to obtain analysis results. These tests will be conducted on three measurement criteria: latency, fairness, and time complexity of each packet. These analysis results will serve as evidence to illustrate that the embodiment of the present invention achieves better performance, in terms of latency, fairness, and lower time complexity.

Please refer to the first figure, which shows a block diagram of the structure of a node 100. The structure of this node is constructed according to the principle of the present invention with a round-robin method of pre-reordering the order. The node 100 includes an input port 102, a processor 104, a packet arrival module 106, a pre-reordered queuing module 108, a packet departure module 110, and an output port 122.

The input port 102 is used as an interface between the node 100 and a link to connect to other destinations, such as other nodes (not shown), and is used to receive packets entering the node; in addition, the input port 102 can also be used as the node 100 and Interface. For illustrative purposes, in this embodiment, the node 100 has only one input port, that is, the input port 102; however, the node 100 can be implemented as having multiple input ports for receiving packets entering the node.

The processor 104 is used to perform various operations for receiving, scheduling, and transmitting packets. The implementation of the processor 104 can be achieved by using logical actions of the hardware, combined with a software program and an operating system. Examples of operating systems and software programs are the use of UNIX or LINUX operating systems to execute code written in C or C++ programming languages.

The packet arrival module 106 is used to receive packets from the input port 102, identify which stream each packet comes from, and put each packet into the flow queue corresponding to the stream to which the packet belongs. middle. The packet arrival module 106 obtains the data of the packet leaving the module 110 through the path 124, and based on this data, determines the number of stream queues n and determines the pair of stream queues 112 _l To 112 _n Perform recognition actions. When there is a new flow that needs the service of node 100, and a packet arrives at the packet arrival module 106 from this flow, the packet arrival module 106 can send a notification message, for example, through the processor 104 to send a notification message to the packet to leave Module 110. Furthermore, the packet arrival module 106 can be used to notify the queuing module 108 that reorders the sequence in advance when a certain situation occurs, for example, when there are no other packets in a certain stream. As shown in the first figure, the packet arrival module 106 includes a set of stream queue 112 _l ~112 _n , Where n is the number of traffic currently served by the node 100. The packet arrival module 106 can be implemented by any logic operation combined with hardware and software. The packet arrival module 106 can use the processing function of the processor 104 to execute instructions in the software. For example, the following is a pseudo-code (pseudo-code) named "PKT _＿ Arrival" module; the packet arrival module 106 can use this module to place each packet in its corresponding flow queue Fq, which is the flow queue 112 _l ~112 _n one of them.

PKT_Arrival modulei&lt;-E×tractFlow(p) //Get the number of the flow that the packet p belongs to Enqueue(p,Fqi)lf Numltem(Fqi)=1then //The establishment of this condition means that no Fq is placed in the packet p _l Before, it was empty, sendMsg(PKT_Pass,i) // and the PACKET_Pass module should be notified to process the stream i

The output port 112 is used to output the packet transmitted by the node 100 to a link to reach the destination, such as another node. For illustrative purposes, in this embodiment, the node 100 has only one output port, that is, the output port 122; however, the node 100 can be implemented as having multiple output ports. In addition, the node 100 can be implemented as a port with dual functions, such as a port with input and output port functions.

The pre-reordered queuing module 108 is used to queue the non-empty traffic 112 _l ~112 _n The packets of are placed in the queue of the second group. The pre-reordered queuing module 108 can process packets of any size. The pre-reordered queuing module 108 includes a classification sub-module 114 and a priority-based queuing sub-module 115.

The classification sub-module 114 is used to arrive at the non-empty data stream queue in the module 106 from the packet, that is, the data stream queue 112 _l ~l12 _n Among them, the packets are captured, the priority of each captured packet is determined, and each packet that has been given priority is placed into an appropriate priority queue in the priority-based queuing submodule 115 Among them, the priority queue 116 _l ~116 _z One of them. Moreover, the classification sub-module 114 can set a packet as a function that can be considered for immediate transmission. Such a packet is, for example, a packet in a high-priority stream. According to the priority queuing submodule 115 maintains some priority queues 116 _l ~116 _z , Where Z is the number of priority levels used by the classification sub-module 114.

The queuing module 108 that has been reordered in advance can be implemented in various ways to achieve the functions of the classification sub-module 114 and the priority-based queuing sub-module 115. For example, the pre-reordering queuing module 108 can be implemented through the processing function of the processor 104 and the instructions of executing software. For example, the following is a virtual code named "PKT_Pass" module, which can be used by the queuing module 108 that reorganizes the sequence in advance. The PKT_Pass module is used to determine which category j the packet belongs to, and to remove the packet from the stream queue Fq where it is located (ie, stream queue 112 _l ~112 _n ) Put it into the priority queue Pq corresponding to this packet _j (I.e. priority queue 116 _l ~116 _z ).

PKT_Pass moduleWhile(TRUE){i<-WaitMsg() //Wait until a packet is put into this empty Fqlf Round=Roundsys //The establishment of an unequal condition means that a new cycle has started {Round<-RoundsysDC<-Ma ×(DCl,Quantum))While DC _i >0 and //Classify the appropriate packet and put it into PQNonEmpty(Fql){PktSize<-Size(Head(Fq _l )) // Best Fq _l The front-end packet size lf(PktSize DC _l )Then// If the data flow/ quota reaches to be able to transmit packets {DC _l <-DC-Pktsize // deduct the used amount j<-z-(DC _l /Pqg _l ) //Calculate jEnqueue(Dequeue(Fq _i ),Pqj) //Mobile Fq _l The front end packet to the appropriate Pqjlf Numltem(Pqj)=1 // means Pqj is empty, and the last packet is placed before j is Then // does not exist in the smallest stacking heap MH_lnsert(j) // join j in the smallest stack))lf NonEmpty(Fq _l )Then // indicates that the remaining amount is insufficient Enqueue(l,AckList){lf Numltem(AckList)=1Then setEVent(EV _actlist )}}}

The packet leaving module 110 is used to get from the non-empty priority queue in the priority-based queuing submodule 115, that is, the priority queue 116 _l ~116 _z Among them, the packet is captured, and the packet is output to the output port 122. The packet leaving module 110 includes a service sub-module 118 and a service table 120.

The service sub-module 118 is to serve the priority queue 116 in a round-robin manner. _l ~116 _z Each non-empty priority queue in. The service sub-module 118 refers to the service table 120 to determine these non-empty priority queues. Here is an example to illustrate. In this example, the service submodule 118 announces a new round of service work, and then the service is in the priority queue 116 _l ~116 _z In the non-empty priority queue in, the service sub-module 118 uses an algorithm, for example, an algorithm similar to the balance round-robin method. The service sub-module 118 and the service table 120 can use a quantum number corresponding to each stream and

A calculated value of a balance (deficit counter) determines how to serve a particular priority queue. The quantum number of a signal stream represents the bandwidth that can be allocated to the signal stream during a round, that is, a part of the available bandwidth, for example, the bandwidth in bytes. For a stream i, its quantum number Quantum _i It can be expressed as:

<maths><img file="TW542960B_D0002.tif" /></maths>

Where r _i Is the rate allocated to stream i, C is the link service rate (linkService rate), F is the size of the frame, and F represents the sum of the quantum numbers of all streams.

During one round, a stream of information accumulates the bandwidth that it can allocate, which means that it is the accumulation of quantum number increments. For example, in the j-1th round, the balance calculation value accumulates the remaining quantum number of the flow i, which can be expressed as DeficitCounter _i^jl . When the next node serves stream i, additional DeficitCounter _i^jl Bytes of data (that is, the quantum number Quantum is added _i Data) can be sent out in the jth round. The service sub-module 118 is used to verify the size of the front-end packet (or "front-end packet") of the priority queue being served. In addition, we will cooperate with Figure 3 to illustrate that the service sub-module 118 also determines when to send a specific packet, for example, through the output port 122.

The service sub-module 118 is also responsible for maintaining the service table 120. It was mentioned above that the service table 120 records information about all the traffic currently served by the node 100. These data include a stream identification code corresponding to each stream, a calculated balance value, and a quantum number. If a stream, such as stream queue 112 _l ~112 _n If there is no packet in the flow, the service sub-module 118 can delete the flow identification code of the flow from the service table 120. The other hand, when there is an inquiry from the packet stream arriving new node, the service submodule 118 may be increased in the service table l20 identification code representative of a new information stream.

In one embodiment, the service sub-module 118 updates the balance calculation value in the service table 120 (DeficitCounter _i^jl ), this equation is defined as: DeficitCounter _i^j =DeficitCounter _i^j-1 +Quantum _i 。

As mentioned above, the increment of the bandwidth that can be allocated to a certain signal flow is accumulated to become the quantum number of the signal flow. The service sub-module 118 calculates this quantum number so that the time complexity of processing a packet is O(1). For a stream, the quantum number can be greater than the largest packet size in the stream, so that every stream with a packet backlog can have at least one packet available for service in a round-robin cycle. In addition, the quantum numbers of any two streams, such as the quantum numbers of stream i and stream j, can be defined as:

<maths><img file="TW542960B_D0003.tif" /></maths>

With the principle of the present invention, the service sub-module 118 can exhibit good performance. Even if it is assumed that all the signal streams after time t begin to show a serious packet backlog phenomenon, the performance can be maintained. This means that the service sub-module 118 can send out the packet with the smallest value of the virtual finishing timestamp (that is, the earliest time stamp) among the front-end packets of all the information streams. Under the assumption of the serious packet backlog phenomenon mentioned above, the virtual completion time stamp of a packet can be calculated according to the following formula:

<maths><img file="TW542960B_D0004.tif" /></maths>

Among them, TS _i^m Represents the time stamp value of the m-th packet of stream i after time t, and for all i values, TS _i⁰ Are set to 0 at time t, r _i Is the rate that can be configured to flow i, and L _i^m It represents the packet size of the m-th packet of the stream i after time t. In addition, for equation (3), use Acc _i^ri Substitute in TS _i^m . r _i After that, equation (3) is equivalent to:

<maths><img file="TW542960B_D0005.tif" /></maths>

Where Acc _i^m It means the cumulative amount of data sent by the stream I after the m-th packet is sent after time t, and its size does not exceed one byte. In addition, it is assumed that all m packets can be transmitted in the kth round. We use DeficitCounter _i⁰ -DeficitCounter _i^m Instead of Acc in the method (4) _i^m , Equation (4) is equivalent to:

<maths><img file="TW542960B_D0006.tif" /></maths>

Where DeficitCounter _i^m It represents the remaining quantum number of the stream i after the m-th packet of the stream i is sent to the pre-order queuing process (Pre-order Queuing) in this round robin. In order to further illustrate this equivalent relationship, we make the following definition.

Definition 1: Quantum Availability. Packet P _i^m QA _i^m DeficitCounter defined for this packet _i^m With Quantum _i Ratio of

<maths><img file="TW542960B_D0007.tif" /></maths>

Auxiliary Theorem 1: For any package P _i^m , Its quantum number availability QA _i^m Meet the following conditions: 0 <img file="TW542960B_D0008.tif" /> QA _i^m &lt;1。

Auxiliary Theorem 2: In a round-robin, the packet with the smallest time stamp has the largest QA value.

Therefore, the service sub-module 118 selects the packet with the largest QA value in one round and transmits the packet. In order to avoid the need to find the packet with the largest QA value from all possible packets that may be sent in each round robin, the classification sub-module 114 in this embodiment classifies these packets according to the QA value of the packet. Packets are divided into several categories and placed in the corresponding priority queue, that is, into the priority queue 116 _l ~116 _z Among.

Since there are Z priority queues, Z categories are defined. In this round robin, the m-th packet of flow I can be sent, and the packet type is n _i^m It can be derived from the following equation:

<maths><img file="TW542960B_D0009.tif" /></maths>

Where DeficitCounter _i^m Yes means that in the kth round, when the mth packet is put into a priority queue, the remaining quota of stream i, the remaining quota is in bytes, and Pqgi means the message The granularity of the priority queue of stream i, Pqgi can be obtained by the following formula:

<maths><img file="TW542960B_D0010.tif" /></maths>

The following is an example of a virtual code, named "PKT_Departure" module, which can be used by the packet departure module 110.

PKT _＿ Departure moduleWhile(TRUE){lf MH_Empty()Then //It means that no packet can be put into PQ{Round _sys Round _sys +1 // Declare the start of a new round of round-robin action ECWaitEvents(EV _minheaP, //Wait until a packet is put into PQ or any FqEV _actlist )lf(EC=EV _actlist ) Then // means that some packets were not sent during the last round robin action {NumAckList // In the last round robin action, there was NumAckListNumltem(AckList) // a non-empty FqWhile(NumAckList >0)//For the non-empty Fq in the last round-robin action, iDequeue(AckList){DC _i DC _i +Quantumi // accumulate their remaining quota to apply to this // round-robin action sendMsg(PKT_Pass,i) // notify PKT_Pass to send the Fqi packet to PQNumAckListNumAckList-1}WaitEvent(EV _minheap ) // If there is no packet in PQ, the action will be suspended}lFEC=EV _actlist } //LFMH_EMPTYwaitEvent(Serverldle)//If the service module is sending out the packet, then MH_Lock() will be suspended //Set the lock to avoid MH _＿ When Delete() is executed, the value of MinHeapRoot is changed. lf Empty(Pq _MinHea p _Root )ThenMH-Delete()MH-Unlock()send(Dequeue(Pq _MinHeapRoot )) //Transmit this packet in Pqj, where the value of j // is a non-empty Pq _j The smallest value

In addition, the following Table 2 and Table 3 provide some definitions used by the above-mentioned virtual code module.

Used in PKT_ARRIVAL, PKT_DEPARTURE and PKT_PASS modules to change the table

<tables><img file="TW542960B_D0011.tif" /></tables>

PKT_ARRlVAL, PKT_DEPARTURE, and the operation function definitions used in the PKT_PASS module

<tables><img file="TW542960B_D0012.tif" /></tables>

Please refer to Figure 2, which shows a flowchart of a packet scheduling method according to the present invention. In step 200, the input port 102 receives a packet and transmits the packet to the packet arrival module 106. In step 202, the packet arrival module 106 identifies which stream the packet belongs to. In step 204, the packet arrival module 106 determines whether the stream to which the packet belongs is a new stream or a known stream. For example, the packet arrival module 106 can use the processor 104 to check the records of the service table 120 to make a decision. If after searching the service table 120, there is no corresponding record of the stream to which the packet belongs, then the packet scheduling method executes step 206; and the action of searching the service table 120 can be performed by, for example, the processor 104. In step 206, the packet arrival module 106 sends a message to the packet departure module 110 and requests the new signal flow to be recorded in the service table 120. Then, the packet arrival module 106 can queue 112 in these streams _l ~112 _n Add a stream queue to process the packets of the new stream. Then, the scheduling method proceeds to step 208.

In step 204, if the stream record to which the packet belongs can be found in the service table 120, the flow of the scheduling method also proceeds to step 208. In step 208, the packet arrival module 106 puts the packet into its corresponding stream queue, that is, the stream queue 112 _l ~112 _n One of them, and sends a message to the queuing module 108 that reorganizes the sequence in advance.

In step 210, when the pre-reordered queuing module 108 receives the above-mentioned message, it will notify the classification sub-module 114 of the occurrence of this event and make it queue 112 from the stream _l ~112 _n Take out this packet, and classify this packet. The classification sub-module 114 can perform classification actions on this packet (and the stream to which it belongs) in a variety of ways. For example, the classification sub-module 114 can be based on a source address, a destination address, or other information such as a service category (such as a constant bit rate, CBR). ) Or transport control protocol port (transport control protocol port), etc. In addition, the classification sub-module 114 can also use other information to classify packets.

In step 212, the classification sub-module 114 puts the packet into the priority queue 116 in the priority-based queuing sub-module 115 according to the result of the classification of the packet. _l ~116 _z Among. When the packet is put into the priority queue 116 _l ~116 _z After that, the queuing module 108, which reorganizes the sequence in advance, sends a message to the packet leaving module 110. This message can be used to inform the packet leaving module 110 of the packet size of the packet and which priority queue the packet is put into. After that, the flow of the scheduling method returns to step 200, and the same steps are repeated to continue processing other packets.

Figure 3 shows a packet transmission method according to the present invention. In step 300, the service sub-module 118 specifically sends a message to announce a new round of round robin action; this message can be sent to, for example, the processor 104 to the queuing module 108 that reorders the sequence in advance. The pre-reordered queuing module 108 can announce a new round of round-robin actions at various times, for example, when the packet leaving module 110 receives a message about the existence of a packet in the priority-based queuing sub-module 115, or It is an announcement action at a predetermined interval.

In step 302, the service sub-module 118 decides to be in the priority queue 116 _l ~116 _z Among them, which ones are non-empty, that is, which priority queues contain packets. The service sub-module 118 can search the service table 120 to determine these non-empty priority queues.

Next, in step 304, the service sub-module 118 confirms whether there is a non-empty priority queue. If all priority queues are 116 _l ~116 _z If the line is empty, the method flow goes to step 306; otherwise, it goes to step 308. In step 306, the service sub-module 118 waits and prepares to announce a new round of round robin action. In addition, the service sub-module 118 can also wait to receive a message from the pre-reordered queuing module 108, or wait for a predetermined period of time. In short, whether it is setting various types of waiting action time or adopting any initial action method in a new round of round robin, it is included in the scope of the principle of the invention.

In step 308, the service sub-module 118 determines whether the current round-robin action is completed. For example, when the service sub-module 118 finishes serving all non-empty priority queues, it is the time when a round-robin action is completed. If the round-robin action this time has been completed, the flow of this method returns to step 300 to continue to declare another round round-robin action.

If the round-robin action this time has not been completed, the flow of this method proceeds to step 310. In step 310, the service sub-module 118 determines the priority queue for the next service. The service sub-module 118 allows it to determine the next priority queue to be served, so that the priority queue 116 _l ~116 _z Among them, the priority queue with the highest priority is served first, and the priority queue with a lower priority is served later. In addition, the service sub-module 118 can also serve the priority queue 116 in a circular manner. _l ~116 _z 。

In one embodiment, a complete binary tree (called min_heap in the above virtual code, which means minimum stacking) can be used to enable the service submodule 118 to effectively determine the priority queue 116 _l ~116 _z Among them, which non-empty priority queues have the highest priority. Here is an example, please refer to the above PKT_DEPARTURE and the virtual code of the PKT_PASS module at the same time. When the packet is put into the priority queue sub-module 115 (such as through the PKT_PASS module), the status of this event is EV _minheap It will be sent out to notify the packet leaving module 110 (for example, the PKT_DEPARTURE module). After receiving this notification, the packet leaving module 110 will send a packet. After sending this packet, ServerIdle will be sent out, and the PKT_DEPARTURE module will repeat the last action until Pq _MinHeapRoot There are no packets. At this time, the function MH_Delete can delete the root node of the binary tree (ie, the minimum stack min_heap) and set the value of MinHeapRoot to the smallest value of j of the remaining nodes. When min_heap is empty, that is, all Pqj are empty. The PKT_DEPARTURE module can use Round _syS The value of plus one announces the start of a new round of round robin action. For all non-empty Fq, that is, after the last round-robin, there are remaining packets in the stream, the PKT_DEPARTURE module can update DeficitCounters according to the order in the service table (such as AckList), and make a request. The PKT_PASS module classifies these suitable packets and puts them into the priority-based queuing sub-module 115.

In step 312, the service sub-module 118 calculates the quantum number (that is, the value represented by DeficitCounter) accumulated in the packet. Then, in step 314, the service sub-module 118 determines whether to send the packet in the current round-robin operation. For example, if the packet size of this packet is smaller than DeficitCounter _i^j , The service sub-module 118 will set DeficitCounter _i^j The value of reduces the packet size value of the packet, and causes the flow of the method of transmitting the packet to enter step 316. In step 316, the service sub-module 118 sends the packet, for example, the packet is sent through the output port 122. Another example is that the service sub-module 118 can set DeficitCounter _i^j The value of is set to zero, that is, in order to avoid delays in services to other priority queues, the remaining quantum numbers (residualquantum) remaining after the last round-robin action cannot be transferred anymore. In addition, during a certain round-robin action, if a packet is sent to a priority queue, and the priority level of this priority queue is higher than the priority of the priority queue currently being served In this round-robin operation, the service sub-module 118 may violate the order of the priority queue with a higher priority, and may not send other priority queues with a lower priority. It is possible to send this packet before the packet in the right queue.

If the packet size of this packet is larger than DeficitCounter _i^j , The method flow goes to step 318. The service sub-module 118 can retain the packet in step 318 until a subsequent round-robin action. The service sub-module 118 can keep the packet again and again until the packet size of the front-end packet is greater than DeficitCounter _i^j In other words, the remaining quantum number is not enough to serve a later packet, or there are no remaining packets in this priority queue. In the process of a subsequent round-robin action, when it is the next turn to the priority queue, the service sub-module 118 can send out additional DeficitCounter in addition to Quantumi bytes of data. _i^j Bytes.

Please refer to Figure 4a, which illustrates how the Balance Round Robin (DRR) works and compares it with the weighted Fair Queuing (WFQ) operation. As shown in Figure 4a, there are 4 streams that require the same amount of bandwidth, and the packets transmitted by each stream have heterogeneous packets of various predetermined sizes. All the data streams are assigned to the same quantum number. According to the conventional DRR algorithm, this quantum number should be equal to the largest packet size in all the data streams. Observing each tributary stream, we can see that packets 1, 4, 6 and B arrive at each tributary stream at the same time, and all packets originate from a source that needs to be serviced, that is, all streams There is a serious backlog of packets. In the lower two columns of Figure 4a, each shows the output form using DRR and WFQ. By comparing these two output forms, three problems can be observed. The first problem is that according to DRR, packets 1, 4, and 6 are transmitted discontinuously (compared to the transmission order 6, 1, and 4 obtained by WFQ); this is because DRR only considers whether a packet can be transmitted in one transmission. It is sent out in a loop without considering whether the transmission sequence of the packet is appropriate. The second problem is that according to DRR, packets 6, 7, 8 and 9 are transmitted in the same batch. Considering the delay and fairness, such a transmission method is not regarded as a packet switching network. Good transmission behavior. The third problem is as follows. The transmission time of packet B is delayed until the next round-robin action, that is, after all the packets of other streams are transmitted in the second round-robin action, packet B It is sent out. As a result, the delay time of packet B is too long; the size of packet B is slightly larger than the remaining quota value during the first round-robin action. According to DRR, the delay time of a packet increases with the size of the frame, and a larger quantum number will produce a larger frame size.

Fig. 4b is an embodiment according to the present invention, which utilizes the balance round-robin method of pre-reorganization sequence and operates under the same input form and assumptions as in Fig. 4a. In this example, the packets are divided into 4 types, so Z=4. Assuming that the quantum number of each tributary stream is equal to 400, and the size of packet B is 500, then packet B cannot be sent in the first round-robin action. However, in the second round, DeficitCount ^B Will be equal to 300, that is, 400+400-500=300. According to the present invention, packet B will be classified as the first level, that is 4-[300/(400/4)]=1, and packet B can be transmitted at the beginning of the next round-robin action. As for other packets, they are put into the priority queuing sub-module 115 according to the same rule. Therefore, as shown in Figure 4b, even when all the traffic streams have a serious accumulation of packets and have sufficient priority queues, according to the embodiment of the present invention, compared with a typical DRR In other words, they can show good performance.

The following is an analysis of the effectiveness of the pre-reordered balance round robin (PDRR) by delay bound and throughput fairness. From the following analysis, it can be seen that in most cases, PDRR has the performance of O(1) time complexity of each packet. In the following, a queuing system plus a single server (server) will be specifically considered, where the rate of the server is C.

Definition 2: The packet backlogged period of stream i is defined as a period of time during which the packet backlog phenomenon continues to occur in the signal stream in the system. Suppose time t _q Is the starting point of a packet backlog period of flow i, and set t _k Represents the completion time of the k-th round-robin action in the PDRR method. W _t ( <img file="TW542960B_D0013.tif" /> ,t _k ) Is used to indicate the time period ( <img file="TW542960B_D0014.tif" /> ,t _k ] Services provided to Newsstream i. L _i It is the maximum packet size in stream i. Auxiliary Theorem 3: In the PDRR method, if the signal flow i is in the time period (t _o ,t _k ] Continuously has a backlog of packets, then at the end of the k-th round-robin action,

<maths><img file="TW542960B_D0015.tif" /></maths>

Where D _i^k Is DeficitCounter _i The value at the end of the k-th round of action, Φ _i Is Quantum _i 。

Auxiliary Theorem 4: Let t _o Is the starting point of the packet backlog period in the PDRR method for stream i. At any time t in this packet backlog period, the following relationship holds:

<maths><img file="TW542960B_D0016.tif" /></maths>

Where F is equal to # <img file="TW542960B_D0017.tif" /> , Z is the number of priority queues, and r _i Is the rate allocated to the stream i.

Theorem 1: This PDRR server belongs to LR, and LR has delay θ ^PDRR less than or equal to:

<maths><img file="TW542960B_D0018.tif" /></maths>

According to equation (1), and in unequal equation (11) with ψ _i C/r _i Substituting F, we get:

<maths><img file="TW542960B_D0019.tif" /></maths>

Since the delay of the DRR method is (3F-2ψ _i )/C, so inequality (11) proves that the PDRR method has better delay. In addition, even in the worst case, if you put θ ^SCFQ Is converted to θ ^PDRR The delay performance of PDRR method is proved to be similar to that of SCFQ, which is (2F-ψ _i )/C. Inequality (12) shows that the delay of the PDRR method has an inverse relationship with the configured bandwidth, and has nothing to do with the number of signal streams currently in use.

Theorem 2: The scheduling algorithm used by the server is the PDRR method and the traffic of the traffic I conforms to a traffic with a parameter of (O _i ,ρ _i ) In the leakybucket mode, where a _i Is the burstiness, ρ _i This is the average rate of the stream. The rate assigned to this stream i is assumed to be equal to ρ _i . If the delay time (delay) of any stream i is Delay _i ,but:

<maths><img file="TW542960B_D0020.tif" /></maths>

Theorem 3: For a PDRR scheduler, its fairness is:

<maths><img file="TW542960B_D0021.tif" /></maths>

Where Fairness ^PDRR Represents the fairness of this PDRR server. Therefore, Fairness ^PDRR Fairness ^DRR To come small, where Fairness ^DRR It is 3F/C.

As mentioned in the above analysis, for each packet, the PKT_Arrival module will put the packet into the corresponding Fq, and the PKT_Pass module will take the packet from the Fq and place it in Pqj, where the value of j is Obtained by a certain number of operations in the picture. PKT_Departure repeatedly started from Pq _MinHeapRoot Select a package in the Pq _MinHeapRoot The value of MinHeapRoot is the small value of j in the non-empty Pqj. Assuming that each accessed Pq is non-empty, since there is no min heap operation, the time complexity of all the above operations is O(1). If Pq _MinHeapRoot If it is empty, the PKT_Departure module will call the delete operation of the minimum stack to obtain a new MinHeapRoot. The time complexity of the reheapification loop of the stack is O(logZ), where Z is the maximum number of keys that appear in the minimum stack, that is, the number of non-empty Pqs at the time. When the PKT_Arrival module must insert a new j value into this minimum stack, a similar situation will occur. Table 4 below briefly summarizes the time complexity of the three modules PKT_Arrival, PKT_Pass, and PKT_Departure when a non-empty priority queue or an empty priority queue is accessed.

<tables><img file="TW542960B_D0022.tif" /></tables>

Although the time complexity of the reheapification loop of the stacking operation involving the minimum stacking operation is O(logZ), according to the embodiment of the present invention, the packets can be sent out individually through the minimum stacking operation operation and The probability of a packet being processed delayed is low. First, when the accessed Pq is empty, the minimum stacking operation may be involved. In contrast, among the sorted priority algorithms, for example, in the methods of SCFQ and WFQ, in the process of sending a packet out, insert (inSert) and delete (delete), these two operations The action needs to be used repeatedly. The second point is that, according to the embodiment of the present invention, the scalar of the minimum stack can be made a small value, so that the maximum number of key values can be equal to the number of Pqs instead of the number of streams. Furthermore, according to the embodiment of the present invention, the actions of inserting and deleting the stack can be simultaneously performed. According to the principle of the present invention, the PKT_Departure module directly compares the two leaf keys of the two leaf keys of the root node by a comparison action to obtain the next smallest j value. After that, the module The group can start sending out Pq at the same time during the cycle of the stacking sorting process _j Packets in. Therefore, according to the present invention, the time complexity of the PDRR method is O(1) in most cases, and O(logZ) in some special cases. Through the above discussion, it can be seen that the embodiment of the present invention uses an algorithm with low time complexity. Compared with other algorithms such as SCFQ, it requires O(lOgN) operation, and N is the number of signal streams. .

Please refer to Figures 5 to 8, which show various simulation results to compare the performance of the embodiment according to the present invention when using PDRR, DRR, and SCFQ. In this simulation, the bandwidth of the link, that is, the server capacity, is assumed to be 80 Mbps, but there are 20 streams of the bandwidth allocated. The 20 streams are divided into two groups, GA and GB. The following experiment was performed, which pointed out the problem of bursty transmission in DRR and the improvement brought by the use of PDRR. In this experiment, all traffic sources are assumed to be CBR and their packet size is fixed. Please refer to Table 5, which lists the traffic parameters of the above two sets of signal streams GA and GB.

The traffic number and quantum number of the two groups

<tables><img file="TW542960B_D0023.tif" /></tables>

Furthermore, the bit rates of the two streams GA and GB are set to be equal. In the two streams, the largest packet size is 500 bytes, and the two streams are each assigned the same quantum number. The size is 500 bytes. The packet arrival rate of the GA group stream is 10 times the packet arrival rate of the GB group stream. In this experiment, 10 priority levels are used. In addition, under the conditions of DRR, PDRR and SCFQ, this experiment also measured the delay time of a signal stream in the GA group.

As shown in Figure 5, in DRR, when a stream is served, the packets of this stream are sent out in batches. In PDRR, the signal stream can use its quantum number in several times, so its packets can be sent out evenly. Another observed phenomenon is that in SCFQ, packets suffer from high delay jitter. This situation is due to the packet arrival rate of the GA group stream is that of the GB group stream. Caused by 10 times the arrival rate. Furthermore, when the server is serving a large packet of the GB group, and some packets of the GA group arrive at the server at the same time, the virtual arrival times of these packets will be set to the same, which will cause The server cannot send these packets according to their actual arrival order.

As shown in Figure 6, in DRR, the average delay time of the GA group's signal flow is greater than in PDRR. In this experiment, the bit rate of the message source is 4MbpS, and it is assumed that the message source is adjusted by a leaky bucket algorithm. The opening and closing rates of the leaky bucket algorithm are each 1000 times/μsec. The size of the packet allocated to the GA group stream is larger than the size of the packet allocated to the GB group stream, but all the streams require the same bandwidth. Although the packet size of the GA group has increased compared to the size of the GB group, the PDRR curve in Figure 6 shows that PDRR has better performance, especially when there are heterogeneous sources. The advantages are even more obvious.

As shown in Figure 7, when the ratio of the size of the packet in the GA group to the size of the packet in the GB group increases, in PDRR, a smaller packet will have better performance than a larger packet. This result is just as good as The situation with DRR is different. The difference between PDRR and DRR is that PDRR considers the information provided by the quantum number consumed by a packet, and rearranges the packet transmission order in a round-robin action. According to DRR, a node only considers whether a packet can be sent, and ignores the packet transmission sequence in a round-robin action. If the traffic environment (traffic environment) is a high-volume environment with a variety of bandwidth requirements of different nature, according to the embodiment of the present invention, and using PDRR, its performance will be better than the performance obtained by using DRR. Preferably, this is because the pre-reordered queuing module 108 can evenly transmit packets in one round-robin action. In addition, Figure 8 further points out that in PDRR, the average delay time of the GA group of signals is lower than the average delay time of the GA group of signals in DRR.

Figure 9 shows a performance graph according to an embodiment of the present invention. The performance change shown in this figure is obtained when the number of priority queues in the embodiment is changed for a specific traffic environment. . As described above, according to the embodiments of the present invention, the quantum number of the signal stream can be uniformly used in a round motion, especially when the quantum number of the signal stream is several times the size of the packet. For example, for stream i, use the pre-reordered queuing method and (Quantumi/L _i ) A priority queue can achieve the above goals. Therefore, for a specific traffic environment, Z priority queues are sufficient, where Z is the largest (Quantumi/Li) value for all traffic, that is, m <img file="TW542960B_D0024.tif" /> x(Quantum _i /L _i ). Therefore, the experimental data shown in Figure 9 is used to illustrate Z and m <img file="TW542960B_D0025.tif" /> x(Quantum _i /L _i ), in which all the traffic sources are set to the CBR type with the specified packet size. Figure 9 shows the average delay time of the signal flow, where the (Quantum _i /Li) value is equal to m <img file="TW542960B_D0026.tif" /> x(Quantum _i L _i ). In Figure 9, each curve represents when Z= <img file="TW542960B_D0027.tif" /> ax(Quantum _i L _i ) When the signal flow obtains the smallest average delay time; this also confirms the advantages that can be achieved through the implementation of this invention.

The present invention can also be applied to multiple signal streams that are allocated different bandwidths but have the same packet size distribution. In addition, in accordance with the principles of the present invention, various types of traffic, such as positioning element rate (CBR) and Markov Modulated Poisson Process (Markov Modulated Poisson Process, MMPP) these two traffic types, as well as other traffic types include Within the scope of application of the present invention.

In summary, although the present invention has been disclosed in a preferred embodiment as above, it is not intended to limit the present invention. Anyone familiar with the art can make various changes without departing from the spirit and scope of the present invention. Therefore, the scope of protection of the present invention shall be subject to the scope of the attached patent application.

Appendix: Proof of the main results

Proof of Auxiliary Theorem 1: The proof of Auxiliary Theorem 1 can be obtained by proving this proposition: For any package P _i^m , Its DeficitCounter _i^m Must be positive and less than Quantum _i . The value in DeficitCounter cannot be negative and can only increase Quantum in the UpdateOneFlow function _i . Suppose the quota is not enough to send this packet P _i^m , Which is this DeficitCounter _i^m-1 Department is less than L _i^m (Packet P _i^m the size of). In the update action and sending this packet P _i^m After that, DeficitCounter _i^m =DeficitCounter _i^m-l +Quantum _i -L _i^m . When DeficitCounter _i^m-1 &lt;L _i^m ,DeficitCounter _i^m Must be less than Quantum _i . Therefore, auxiliary theorem 1 is proved to be true.

Proof of auxiliary theorem 2: According to equation (6), equation (5) is equivalent to:

<maths><img file="TW542960B_D0028.tif" /></maths>

Since L _i^m >0,Quantum _i >0 and r _i , From equation (3) and equation (A.1), for any value of m, TS can be obtained _i^m >TSi ^mI And QA _i^ml >qA _i^m 。

In the same round-robin action, for the packet P with the smallest time stamp _i^m , Its m value is the smallest value among all packets, and the QAi of this packet ^m The m value in is also the minimum value among all packets.

Proof of auxiliary theorem 3: PDRR only adjusts the service order of packets in a DRR round-robin action. Therefore, in DRR, during the packet backlog period, those packets that can be transmitted in one round-robin action can still be transmitted in the same PDRR round-robin action.

Proof of Auxiliary Theorem 4: For each period (t _kl ,t _k ],

<maths><img file="TW542960B_D0029.tif" /></maths>

By changing the formula (A.2) from k=1,2, _… When the k-1 formulas are added up, we can get:

<maths><img file="TW542960B_D0030.tif" /></maths>

Assuming in Fq _i In, there are two packets P _i^A And P _i^B , Their packet sizes are Li ^A And LiB, (LiB=ψi), and there is only P in the (kl)th round of actions _i^A Can be sent out. All other streams have exhausted their DeficitCounter. Therefore, D ^ik-l =ψ _i -, where 0&lt;A <img file="TW542960B_D0031.tif" /> ψ _i , If ji then Di ^kl =0, and:

<maths><img file="TW542960B_D0032.tif" /></maths>

Under this assumption, in the k-th blow-round action, the packet P _i^B Will be put into Pq _n Among them:

<maths><img file="TW542960B_D0033.tif" /></maths>

And in packet P _i^B Previously, the maximum amount of material that could be served was ((n/Z)F-ψ _i ). Therefore, in the round-robin action from the beginning to the k-th blow, in the packet P _i^B At any time t before receiving service, there are:

<maths><img file="TW542960B_D0034.tif" /></maths>

(A.6) is equivalent to:

<maths><img file="TW542960B_D0035.tif" /></maths>

In addition, in equation (9), replace k with kl, and define the retention rate ri of the signal flow i as (ΦiC/F), then:

<maths><img file="TW542960B_D0036.tif" /></maths>

Then, replace D with Φi- _i^kl , And for any delta value, <img file="TW542960B_D0037.tif" /> － <img file="TW542960B_D0038.tif" /> = <img file="TW542960B_D0039.tif" /><img file="TW542960B_D0040.tif" /> Z- <img file="TW542960B_D0041.tif" /><img file="TW542960B_D0042.tif" /><img file="TW542960B_D0043.tif" /><img file="TW542960B_D0044.tif" /> ,but:

<maths><img file="TW542960B_D0045.tif" /></maths>

In the worst case, the stream i is updated last in the k-th round-robin action, and its packet L _i Is inserted into Pq _n The end. Now consider two cases: Case 1: In the k-th round-robin action, at the time t before the traffic i is served, that is: t _kl &lt;t <img file="TW542960B_D0046.tif" /> t _kl + <img file="TW542960B_D0047.tif" /> F-ψi, so we can get:

W _i (t ₀ ,t)=Wi(t ₀ ,t _k-1 ). (A.l0) Case 2: In the k-th round-robin action, at the time t after the traffic i starts to receive service, that is: t _kl + <img file="TW542960B_D0048.tif" /> F-Φ _i &lt;t <img file="TW542960B_D0049.tif" /> t _k , So available: W _i (t ₀ ,t)=W _i (t _o ,t _kl )+W _i (t _kl ,t) <img file="TW542960B_D0050.tif" /> W _i (t _o ,t _k-l ). (A.11) Therefore, for any time t,

<maths><img file="TW542960B_D0051.tif" /></maths>

Proof of Theorem 3: Assume that at the beginning of the k-th round-robin action, at Fq _i In, there are two packets P _i^A And P _i^B , Their packet size is L respectively _i^A And L _i^B ,(L _i^B =Φ _i ), and there is only P in the k-th round-robin action _i^A Can be sent out. Packet P _i^B The category is n, which also means that this packet will enter the nth priority queue. In the (k+1)th round-robin action, because the server always selects packets from the non-empty Pqj with the smallest j value, for another stream j with a category greater than n, all its packets are only in Packet P _i^B It may be sent after the time t when it is sent. Therefore, before time t, for the stream j,

<maths><img file="TW542960B_D0052.tif" /></maths>

Moreover, when t _k &lt;t&lt;t _k+l , For the signal flow i, from equation (9), we can get

<maths><img file="TW542960B_D0053.tif" /></maths>

From equations (A.5), (A.13) and (A.14), the following results can be obtained:

<maths><img file="TW542960B_D0054.tif" /></maths>

This boundary (bound) applies from t ₀ The beginning period. And for any period:

<maths><img file="TW542960B_D0055.tif" /></maths>

Therefore, for any two streams i and j,

<maths><img file="TW542960B_D0056.tif" /></maths>