In high-speed packet networks, all the switching or routing points want to
output the arrived packets by utilizing packet scheduling algorithms. These
algorithms can be categorized into two main classes: Time-stamp based scheduling
and round-robin based scheduling. Time-stamp based algorithms such as WF2Q
(Worst-case Fair Weighted Fair Queuing) (Bennett and Zhang,
1996) and SCFQ (Self-clocked fair Queuing) (Golestani,
1994) maintain two time-stamps for every packet to indicate its start-serving
time and end-serving time, respectively then sort their time and send out the
packet with the least end-serving time. This kind of algorithms is to approximately
emulate the most ideal packet scheduling algorithm-GPS (Generalized Processor
Sharing) (Parekh and Gallager, 1993) by maintaining virtual
clocks and achieves good fairness and low latency. However, their time complexity
is at least O (logN) (N is the number of active flows) due to computing and
sorting each packets time. They are not suitable for using in high-speed
networks, thus round-robin based packet scheduling algorithms with lower complexity
are at a premium. In round-robin based scheduling algorithms such as RR (Round-Robin),
WRR (Weighted Round-Robin) (Chaskar and Madhow, 2003)
and DRR (Deficit Round-Robin) (Shreedhar and Varghese,
1996) etc., the scheduler simply serves all non-empty queues in a round-robin
manner. These algorithms neither maintain a time-stamp for every service flow,
nor perform sorting among the packets. Most of them have O (1) complexity with
respect to the number of flows. But in a variable-length packet environment,
round-robin based scheduling algorithms must consider packet length to guarantee
scheduling fairness. All in all, a good scheduling algorithm should have the
characteristics of fairness, efficiency and low complexity.
DRR can support variable-length packet scheduling with O (1) time complexity
and it gains widespread attention (Sivakumar and Ramprasad,
2012; Ayaz et al., 2011; Sleem
et al., 2011; Mansy et al., 2011).
DRR assigns a quantum for each flow to indicate the number of bytes that the
flow can transmit in a round. At the same time, a Deficit Counter (DC) is also
set for each flow to store the residual quantum that the flow does not use up
in a service opportunity, and through which the flow can bring the residual
quantum into the next service. In this way during a relatively long time, the
service that a flow receives is directly proportional to its quantum on the
whole. It means that DRR is fair and suited to be used in variable-length packet
networks. However, DRR also has some shortages: Firstly, it just provides long
time scale fairness and it may induce big output burst from short time scale;
furthermore, its fairness is related to the minimum quantum and the minimum
quantum must be equal or greater than Max in order to assure DRR has O (1) complexity.
Secondly, its characteristic of latency is not good and probably some queues
cannot receive service for a long time. In addition, DRR wants to know the length
of packets before sending them and overhead is increased. Aiming at the above-mentioned
shortages, many literatures put forward improvement to DRR. Kanher
and Sethu (2001) proposed nested-DRR to adopt fine grain scheduling policy
and minish the upper bound of packet latency. LL_DRR (Xiaodong
and Lemin, 2002) presented a new algorithm suitable for variable-length
packet scheduling based on DRR and had prominent improvement in latency performance.
Jian et al. (2005) put forward a new scheduling
discipline named Prioritized Nested DRR (PNDRR), which introduced a token bucket
with virtual allocated token quantum and delay of packet in latency critical
queue is effectively diminished. Fei et al. (2011)
overcome the limitation that DRR cannot output smoothly by adding traffic shaper
on the basis of network calculus in nodes and improved network QoS. I-MDRR (Kumar
and Priyameenal, 2011) is proposed for broadband wireless access and it
can support QoS requirements of real-time services as well as provide higher
throughput. The slicing domain scheduling viewpoint is proposed (Bo
et al., 2012), which adopts Smoothed Deficit Round-Robin (SDRR) scheduling
algorithm in carrying group and Longest Queue First (LQF) scheduling algorithm
in scheduling domain; Scheduling complexity and delay are decreased. M-DRR (Shuqing
and Jinye, 2012) schedules wireless packets by taking advantage of channel
conditions and HARQ technology; it improves the throughput and QoS guarantee
in IEEE 802.16e system. Aiming at redundant transmission and handling burst
flows in avionic networks, D2DRR (Hua and Liu, 2012)
properly distributes traffic between switches and end systems, and unifies the
representation of heterogeneous flows; it implements fast deduplication and
the network load is reduced. In these mentioned algorithms, improvements to
DRR made up its some shortages, but their basis is still DRR and fixed quantum
is assigned for data flows. In this study, a new variable-length packet scheduling
algorithm different from DRR is presented, which is called Resilient Quantum
Round-Robin (RQRR). The distinct characteristic is that the quantum of each
queue changes dynamically and the permission given to each of the flows in a
given round is not fixed and is computed depending on the behavior of the flows
in the previous round. During the course of its execution, flows which receive
very little service in a round are given an opportunity to receive proportionately
more service in the next round. Thereupon, good scheduling fairness among flows
can be guaranteed. Besides, as an important application of RQRR, it can support
multilink transmission efficiently.
RESILIENT QUANTUM ROUND-ROBIN
A pseudo-code implementation of the RQRR scheduling algorithm is shown in Fig.
1, consisting of Initialization, Enqueuing module and Dequeuing module.
The Initialization is to initialize packet scheduling module when network node
has demand on scheduling packets.
||Pseudo-code for RQRR (Resilient Quantum Round-Robin) scheduling
Enqueuing module is called whenever a new packet arrives at a flow. The packet
will enter into the correlative queue and wait for being sent. Dequeuing module
is the heart of the algorithm which schedules packets from the queues corresponding
to different flows.
A data flow is defined as active if its queue is not empty or its packets are
being scheduling. All the active flows are put into a list and this list is
When a flow changes from active to inactive, it will be removed from ActiveFlowList.
When a flow changes from inactive to active, it will be appended at the end
A round is defined as the process during which the data flows, included in
ActiveFlowList at a time instant T1 (T1>0), are accessed by packet scheduling
module. The newcome flows or those become active once again can be appended
at the end of ActiveFlowList, but they will be accessed in the next round. For
example, consider the instant of time, T1, when the scheduler is first initialized.
Suppose round 1 is one round-robin iteration starting at time T1 and consisting
of visits to all the flows that were in the ActiveFlowList at time T1. Assume
that flow-1, flow-2 and flow-3 are the only flows active at the beginning of
round 1. The visits of the scheduler to the flow-1, flow-2 and flow-3, comprise
round 1. Let flow-4 become active after the time instant T1, but before the
completion of round 1. Let the time instant T2 mark the completion of round
1. The scheduler does not visit flow-4 in round 1 since flow-4 was not in the
ActiveFlowList at the start of round 1. Round 2 will visit all of the flows
that are in the ActiveFlowList at time T2. Assuming that flows-1, flow-2 and
flow-3 are still active at timeT2 and round 2 consists of visits to flow-1,
flow-2, flow-3 and flow-4. Therefore, the sequence number of rounds is relative
to one flow, i.e., round 2 is the second round for flow-1, flow-2, flow-3,
but the first round for flow-4.
In order to express the number of data flows wanted to be accessed in a round,
RQRR introduces a counter, which is called VisitFlowCount,
to record the number of flows. At the beginning of a round, VisitFlowCount equals
the number of flows in ActiveFlowList. When packet scheduling module finishes
accessing a flow, the value of VisitFlowCount will be minus 1. At last, when
VisitFlowCount equals 0, it means that the current round is over.
In each round, the scheduling algorithm determines the number of bytes that
a flow is permitted to send and calls this quantity the p-value for the flow
during that round. Suppose there are n (n is a natural number and n>0) flows
sharing one output link. The p-value assigned to flow i (i is a natural number,
1≤i≤n) during round r (r is a natural number, r>0) is denoted by Pi
(r). p-value is not fixed and is recomputed in the following rounds except its
initial value is 0. The computing method is: For one flow, p-value of the next
round = p-value of the current round+the Average Count (AC) of bytes sent by
other flows in current round-the number of bytes sent by the flow in current
Another counter is used to record the number of bytes, called ByteNumberCount.
Let Send i (r) be the number of bytes that are transmitted from the queue of
flow i in round r. Its initial value is 0 before a round starts and the number
of bytes of sent packets will be accumulated to it once a packet is sent.
Average count (AC): For flow-i, AC expresses that, starting from the r-th (r≥2)
round, the average number of bytes sent by all the other flows in the previous
round, denoted by ACi (r-1). If there are n flows in the round
If it is not divided exactly, the result equals the integer part of quotient+1.
Whereupon, computing the p-value of a flow as: when:
r = 1, Pi (1) = 0
r>1, Pi (r) = Pi
(r-1)+ACi (r-1)-Sendi (r-1)
Hereinto i is a natural number and 1≤i≤n. The meaning of p-value is:
The quantity of data that a flow is permitted to send out in a round not only
relates to its own p-value, but also depends on the quantity sent by other active
Figure 2 illustrates the first four rounds in an execution
of the RQRR algorithm.
||An illustration of 4 rounds in a RQRR (Resilient Quantum Round-Robin)
In this figure, there are three flows: Flow-1, flow-2 and flow-3. The sizes
of the packets actually sent by the flow during this round are shown by the
horizontal bars and the new p-values for the next round are again computed using
(1) and (2). One packet is sent at least when p-value = 0 in a round. Although
only four rounds are listed, there is no limitation in the quantity of flows
and the number of rounds for RQRR, which will continue scheduling packets once
data flows become active. Also, it is observed from Fig. 2
that, in general, flows which receive very little service in one round will
be given more opportunity to receive proportionate service in the next round.
For instance, flow-3 only sent a three-byte packet in round 2, whereas, it sent
three packets in round 3 and the total length comes to twenty bytes.
In this section, analyzing the implementation complexity of RQRR, and also
the fairness using a measure based on a popular metric proposed (Golestani,
Implementation complexity: Consider an execution of the RQRR scheduling
algorithm over n flows. Define the implementation complexity of the RQRR scheduler
as the order of the time complexity, with respect to n, of enqueuing and then
dequeuing a packet for transmission:
Theorem 1: The implementation complexity of a RRQR scheduler is O (1).
Proof: prove the theorem by demonstrating that enqueuing and dequeuing
a packet are each of O (1) time complexity.
The time complexity of enqueuing a packet is the same as the time complexity
of the Enqueuing module in Fig. 1, which is executed whenever
a new packet arrives at a flow. Determining the flow at which the packet arrives
is an O (1) operation. The flow at which the new packet arrives is added to
the ActiveFlowList, if it is not already in the list. This addition of an item
to the tail of a linked list data structure is also an O (1) operation.
Next, considering the time complexity of dequeuing a packet. During each service
opportunity, the RQRR scheduler transmits at least one packet. Thus, the time
complexity of dequeuing a packet is equal to or less than the time complexity
of all the operations performed during each service opportunity. Each execution
of the set of operations inside the while loop of the Dequeuing module in Fig.
1, represents all operations performed during each service opportunity given
to a flow. These operations include determining the next flow to be served,
removing this flow from the head of the ActiveFlowList and possibly adding it
back at the tail. All of these operations on a linked list data structure can
be executed in O (1) time. Additionally, each service opportunity includes updating
the values of VisitFlowCount, Sendi and p-value. All of these can
be done in constant time, as represented by the constant number of operations
in the Dequeuing module in Fig. 1. The statement of the theorem
Fairness: GPS (General Processor Sharing) scheduling algorithm has good
fairness. Absolute fairness bound of a scheduler, a method of fairness measurement,
is defined as the upper bound on the difference between services received by
a flow under the scheduler and that under GPS scheduling over all possible time
intervals. Since this upper bound is difficult to obtain analytically, Relative
fairness bound, proposed by Golestani (1994), is more
commonly employed. This quantity is defined as the maximum difference in the
services received by any two flows over all possible time intervals:
Definition 1: Let Sendi (t1, t2) be
the number of bytes transmitted by flow-i during the time interval between t1
and t2. Given a time interval (t1, t2), the
Fairness Measure, FM (t1, t2) for the interval is defined
as the maximum value of the difference between the number of bytes transmitted
by any two flows, flow-i and flow-j. Namely:
FM (t1, t2) = max (|Sendi (t1,
t2)-Sendj (t1, t2)|), 1≤i, j≤n
Define FM as the maximum of FM (t1, t2) for all possible
time intervals (t1, t2). A scheduler is more perfectly
fair if FM approaches zero more closely. GPS (General Processor Sharing) is
proven to have FM = 0, but this condition cannot be met by any packet-by-packet
algorithm since packets must be served exclusively. Therewithal, a scheduling
algorithm can be considered close to fair if its FM is bounded by a constant.
Especially, FM (t1, t2) should be independent of the length
of time interval.
Definition 2: Define Max as the size in bytes of the largest packet,
namely the largest length of packets:
Lemma 1: In the case of no rounding in computing ACi (1≤i≤n),
for any round r (r≥1), the sum of p-value of n flows is zero.
Proof: When r = 1, since Pi (1) = 0, so the sum of
p-value of n flows is zero. When, r≥2, since:
Pi (r) = Pi (r-1) +ACi (r-1)-Sendi
so the sum is:
Since, Pi (1) = 0, therefore:
The statement of the lemma is proved.
Lemma 2: For any flow-i (1≤i≤n) and round r (r≥1), Pi
Proof: When r = 1, Pi (1) = 0. The statement is correct.
r ≥2, Pi (r) = Pi (r-1)+ACi
Sendi (r-1)≥Pi (r-1), have Pi
According to Lemma 1, if the p-values of flows are not all zero, then they
cannot all be positive number. The sum of positive p-value and the sum of negative
p-value have the equal numerical value. When the p-value of a flow is negative,
this flow is permitted to send one packet and its largest length is Max. Without
loss of generality, assume that the p-value of flow-1 is negative at round r-1,
the largest length of data that flow-1 can send at this round is Max. Again,
assume that flow-2 is the flow with the largest p-value which is more than Max
and attains to 2Max-1. The total length of packets that flow-1 and flow-2 can
send at the most is: Max+2Max-2+Max = 4Max-2; the average value is 2Max-1 and
less than 2Max. If need ACi (r-1)≥2Max, then the average value
of Pj (r-1) of the other flows (j≠i) must be more than Max, that
is to say, ACj (r-2)>Max. By parity of reasoning, it requires
ACj (1)>Max. However, the maximum value of ACj (1)
is Max, and then ACi (r-1)<2Max; therefore, Pi (r)<2Max.
The statement of the lemma is proved.
Theorem 2: Given m consecutive rounds starting from round k (k≥1)
during which flow-i (1≤i≤n) is active, the total number of bytes transmitted
by flow-i is denoted as Sum-i. For any round r (k≤r≤k+m-1), if
Pi (r)≥0, then:
Proof: When r≥2, Pi (r) = Pi (r-1)+ACi
(r-1)-Sendi (r-1), therefore, Sendi (r-1) = Pi
(r-1)-Pi (r)+ACi (r-1), then:
Since, Pi (r)<0 and Pi (r) = 0 allow flow-i to send
one packet, when Pi (r)<0, take Pi (r) = 0, then have
Pi (r)≥0. Also, Pi (r)<2Max from Lemma 2, therefore,
-2Max<Pi (k)-Pi (k+m) <2Max. The statement of the
theorem is proved.
The following theorem establishes the fact that the fairness measure of RQRR
is bounded by a constant, which is independent of the length of time interval.
Theorem 3: In any execution of RQRR algorithm, when Pi (r)<0,
take Pi (r) = 0 (1≤i≤n), Then, for any time interval (t1,
t2), FM (t1, t2)<7Max-1.
Proof: Consider two active flows i and j in time interval (t1,
t2). Since, RQRR is a round-robin algorithm, flow-j must have an
opportunity between any two opportunities given to flow-i. Let mi
be the number of opportunities given to flow-i in time interval (t1,
t2) and let mj be the number of opportunities given to
flow-j in the same interval, then |mi-mj|≤1.
Without loss of generality, assume that in the interval (t1, t2),
flow-i starts receiving service before flow-j. Thus, mj = mi
or mj = mi-1. From Theorem 2, have:
When mj = mi:
So, from Eq. 5 have:
When mj = mi-1:
Since, Sendu (k+mj)≤Pu (k+mj)-1+Max<2Max-1+Max
= 3Max-1 hence:
Combining Eq. 6 and 7, get FM (t1,
t2)<7Max-1. The statement of the theorem is proved.
RQRR SUPPORTS MULTILINK TRANSMISSION
Many medium-small enterprises access Internet through an E1 leased line firstly.
When business increments want higher bandwidth than E1, telecommunications operators
have no good method to solve this problem because the higher bandwidth standard
is E3 line. The bandwidth of E3 is 34 Mbps and this kind of line not only has
expensive rent charge, but also subscribers do not need such high bandwidth.
In this case, multilink transmission is an efficient way to solve the problem;
that is, satisfying the subscribers demand on bandwidth by increasing
links based on the former lines. The PPP Multilink Protocol (MLPPP) (Sklower
et al., 1996) is the typical representative among them. The distribution
mechanism of multilink will divide a large packet into many small packets and
transmit them through multilink simultaneously. However, if just assign packets
to multi channels and transmit them simply, the receiver cannot reassemble the
packets correctly because of the improper arriving sequence. Therefore, MLPPP
appends 4 bytes sorting identifier in a packet header to control the sequence
and adopts simple synchronous principle so that it can transmit packets on parallel
channels and reassemble them with correct order at the destination. The other
problem which multilink transmission needs solve is the fairness of link utilization,
namely load-balance between links. In this respect, MLPPP only mentioned two
simple round-robin methods and they cannot guarantee fairness as well as adequately
take advantage of the bandwidth provided by multilink.
RQRR algorithm can settle datagram reassembly and load-balance commendably
in multilink transmission. When there are two or more links between sending
end and receiving end, RQRR can realize load-balance at the sending end. At
the receiving end, RQRR carries out queue scheduling and the receiving packet
sequence is entirely consistent with the sending sequence. Next, specifying
the process of multilink transmission supported by RQRR algorithm. Notice that:
Some concepts such as ActiveLinkList, VisitLinkCount etc., can be understood
easily based on the above algorithm description, so there is no specific explanation
RQRR operating at sending end: There are one input link and multi output
links at sending end. RQRR will initialize sending end after all output links
are ready, including: initializing ActiveLinkList of sending end;
VisitLinkCount is set initial value 0; the p-value of each link
is also set initial value 0.
||RQRR (Resilient Quantum Round-Robin) operating procedure at
||RQRR (Resilient Quantum Round-Robin) operating procedure at
||A flow consisting of seventeen packets arrives at sending
end and each packet is denoted with a letter and its length (bytes). Hereinto,
packet a arrives firstly and u is the last one
When a packet arrives at sending end, it enters into DataRequestSendQueue
firstly and waits for being sent. Load-balance module executes RQRR algorithm
and selects one link from multi output links through which packets in DataRequestSendQueue
are sent out. The operating procedure is shown as Fig. 3.
RQRR operating at receiving end: There are multi input links and one
output link at receiving end. The initializing process involves: Initializing
ActiveLinkList of receiving
is set initial value 0; the p-value of each link is set initial value 0; The
ByteNumberCount of each
link in ActiveLinkList
is set initial value 0 as well. Notice that, receiving end has some same components
as sending end, but their operation is independent. When a packet sent from
sending end arrives at receiving end, it will enter into the queue belonging
to the relevant link. Queue scheduling module of receiving end executes RQRR
algorithm to pick up packets from relative queue and send them out through the
output link. The operating procedure is illustrated in Fig. 4.
An example: Assume that a flow, arriving at sending end, consists of
seventeen packets expressed successively by a, b, c, d, e, f, g, h, j, k, l,
m, p, q, s, t and u shown as in Fig. 5. The numbers behind
letters denote the length of packets with unit byte. There are three links between
sending end and receiving end, expressed as link-1, link-2 and link-3, respectively.
At sending end, load-balance module executes RQRR algorithm to distribute seventeen
packets into three links after four rounds (hereinto SP denotes p-value at sending
end) illustrated in Fig. 6. At receiving end, there are four
packets a, d, h, g entering into the queue of link-1; seven packets b, e, f,
j, k, s, t entering into the queue of link-2; six packets c, g, l, m, p, u entering
into the queue of link-3 and the status is revealed in Fig. 7.
Moreover, the load-balance situation between links can be seen from Fig.
Queue scheduling process at receiving end is similar to the scheduling process
in section 2. After four rounds queue scheduling, obtaining the following packet
sequence on the output link at receiving end: a, b, c, d, e, f, g, h, j, k,
l, m, p, q, s, t and u. Hereinto, a is the first packet sent out through the
output link and u is the last one.
||An illustration of 4 rounds in a RQRR (Resilient Quantum Round-Robin)
execution at sending end. There are three links between sending end and
receiving end and SP denotes the p-value at sending end
||At receiving end, packets a, d, h and q enter into the queue
of Link-1, packets b, e, f, j, k, s and t enter into the queue of Link-2,
packets c, g, l, m, p and u enter into the queue of Link-3
||An illustration of RQRR (Resilient Quantum Round-Robin) supporting
multilink transmission. Load-balance operation at sending end distributes
seventeen packets to be transmitted through three links. After executing
queue scheduling at receiving end, packet sequence through the output link
is the same as packets arrived at sending end
Thus, it can be seen, the packet sequence sent out through the output link
at receiving end is consistent with the packet sequence arriving at sending
end. The whole process is presented in Fig. 8.
Therefore, realizing multilink data transmission by RQRR algorithm, it not
only allocates the bandwidth resource of multilink fairly to keep load-balance
amongst links, but also guarantees accordant packet sequence between sending
end and receiving end without increasing additional overhead. So, it has low
complexity and hardware implementation is simple as well. In order to realize
load-balance and accordant packet sequence, sending end and receiving end must
satisfy the following conditions: (1) Sending end and receiving end should be
synchronous and have same ActiveLinkList, (2) There is no packet loss during
the transmission, or accordant packet sequence cannot be guaranteed.
This study presented a novel scheduling discipline called Resilient Quantum
Round-Robin (RQRR), which is fair, efficient and supports variable-length packet
scheduling. The implementation complexity of RQRR is O (1) and therefore, can
be easily implemented in high-speed networks with large numbers of flows. The
relative fairness measure of RQRR is independent of the length of time interval
and has an affirmatory upper bound of 7Max-1, where Max is the largest size
of the packets. In comparison to DRR of similar efficiency, complexity and fairness
of RQRR are not related to quantum; each flow sends out one packet at least
in a round and RQRR has better characteristic of latency; on the other hand,
RQRR does not want to know the length of a packet before scheduling it because
it gets hold of the length information from the already sent packets. Finally,
in supporting multilink transmission, RQRR can efficiently implement load-balance
as well as guarantee the consistent packet sequence between receiving end and
This study is partially sponsored by the S and T Plan Projects of Hunan Province
(No. 2010GK3045) and Scientific Research Fund of Hunan Provincial Education
Department (No. 10C0687).