INTRODUCTION
In highspeed 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: Timestamp based scheduling
and roundrobin based scheduling. Timestamp based algorithms such as WF^{2}Q
(Worstcase Fair Weighted Fair Queuing) (Bennett and Zhang,
1996) and SCFQ (Selfclocked fair Queuing) (Golestani,
1994) maintain two timestamps for every packet to indicate its startserving
time and endserving time, respectively then sort their time and send out the
packet with the least endserving time. This kind of algorithms is to approximately
emulate the most ideal packet scheduling algorithmGPS (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 packet’s time. They are not suitable for using in highspeed
networks, thus roundrobin based packet scheduling algorithms with lower complexity
are at a premium. In roundrobin based scheduling algorithms such as RR (RoundRobin),
WRR (Weighted RoundRobin) (Chaskar and Madhow, 2003)
and DRR (Deficit RoundRobin) (Shreedhar and Varghese,
1996) etc., the scheduler simply serves all nonempty queues in a roundrobin
manner. These algorithms neither maintain a timestamp 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 variablelength packet environment,
roundrobin 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 variablelength 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 variablelength 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 abovementioned
shortages, many literatures put forward improvement to DRR. Kanher
and Sethu (2001) proposed nestedDRR 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 variablelength
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. IMDRR (Kumar
and Priyameenal, 2011) is proposed for broadband wireless access and it
can support QoS requirements of realtime services as well as provide higher
throughput. The slicing domain scheduling viewpoint is proposed (Bo
et al., 2012), which adopts Smoothed Deficit RoundRobin (SDRR) scheduling
algorithm in carrying group and Longest Queue First (LQF) scheduling algorithm
in scheduling domain; Scheduling complexity and delay are decreased. MDRR (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 variablelength packet scheduling
algorithm different from DRR is presented, which is called Resilient Quantum
RoundRobin (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 ROUNDROBIN
A pseudocode 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.

Fig. 1: 
Pseudocode for RQRR (Resilient Quantum RoundRobin) 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
called “ActiveFlowList”.
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
of ActiveFlowList.
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 roundrobin iteration starting at time T1 and consisting
of visits to all the flows that were in the ActiveFlowList at time T1. Assume
that flow1, flow2 and flow3 are the only flows active at the beginning of
round 1. The visits of the scheduler to the flow1, flow2 and flow3, comprise
round 1. Let flow4 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 flow4 in round 1 since flow4 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 flows1, flow2 and
flow3 are still active at timeT2 and round 2 consists of visits to flow1,
flow2, flow3 and flow4. Therefore, the sequence number of rounds is relative
to one flow, i.e., round 2 is the second round for flow1, flow2, flow3,
but the first round for flow4.
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 pvalue for the flow
during that round. Suppose there are n (n is a natural number and n>0) flows
sharing one output link. The pvalue 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 P_{i}
(r). pvalue is not fixed and is recomputed in the following rounds except its
initial value is 0. The computing method is: For one flow, pvalue of the next
round = pvalue of the current round+the Average Count (AC) of bytes sent by
other flows in current roundthe number of bytes sent by the flow in current
round.
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 flowi, AC expresses that, starting from the rth (r≥2)
round, the average number of bytes sent by all the other flows in the previous
round, denoted by AC_{i} (r1). If there are n flows in the round
r1, then:
If it is not divided exactly, the result equals the integer part of quotient+1.
Whereupon, computing the pvalue of a flow as: when:
r = 1, P_{i} (1) = 0
when,
r>1, P_{i} (r) = P_{i}
(r1)+AC_{i} (r1)Send_{i} (r1) 
(2) 
Hereinto i is a natural number and 1≤i≤n. The meaning of pvalue is:
The quantity of data that a flow is permitted to send out in a round not only
relates to its own pvalue, but also depends on the quantity sent by other active
flows.
Figure 2 illustrates the first four rounds in an execution
of the RQRR algorithm.

Fig. 2: 
An illustration of 4 rounds in a RQRR (Resilient Quantum RoundRobin)
execution 
In this figure, there are three flows: Flow1, flow2 and flow3. The sizes
of the packets actually sent by the flow during this round are shown by the
horizontal bars and the new pvalues for the next round are again computed using
(1) and (2). One packet is sent at least when pvalue = 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, flow3 only sent a threebyte packet in round 2, whereas, it sent
three packets in round 3 and the total length comes to twenty bytes.
ANALYTICAL RESULTS
In this section, analyzing the implementation complexity of RQRR, and also
the fairness using a measure based on a popular metric proposed (Golestani,
1994).
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, Send_{i} and pvalue. 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
is proved.
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 Send_{i} (t_{1}, t_{2}) be
the number of bytes transmitted by flowi during the time interval between t_{1}
and t_{2}. Given a time interval (t_{1}, t_{2}), the
Fairness Measure, FM (t_{1}, t_{2}) for the interval is defined
as the maximum value of the difference between the number of bytes transmitted
by any two flows, flowi and flowj. Namely:
FM (t_{1}, t_{2}) = max (Send_{i} (t_{1},
t_{2})Send_{j} (t_{1}, t_{2})), 1≤i, j≤n
Define FM as the maximum of FM (t_{1}, t_{2}) for all possible
time intervals (t_{1}, t_{2}). 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 packetbypacket
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 (t_{1}, t_{2}) 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 AC_{i} (1≤i≤n),
for any round r (r≥1), the sum of pvalue of n flows is zero.
Proof: When r = 1, since P_{i} (1) = 0, so the sum of
pvalue of n flows is zero. When, r≥2, since:
P_{i} (r) = P_{i} (r1) +AC_{i} (r1)Send_{i}
(r1)
so the sum is:
Since:
then:
Since, P_{i} (1) = 0, therefore:
The statement of the lemma is proved.
Lemma 2: For any flowi (1≤i≤n) and round r (r≥1), P_{i}
(r) <2Max.
Proof: When r = 1, P_{i} (1) = 0. The statement is correct.
When:
r ≥2, P_{i} (r) = P_{i} (r1)+AC_{i}
(r1)Send_{i} (r1)
Since:
Send_{i} (r1)≥P_{i} (r1), have P_{i}
(r)≤AC_{i} (r1)
According to Lemma 1, if the pvalues of flows are not all zero, then they
cannot all be positive number. The sum of positive pvalue and the sum of negative
pvalue have the equal numerical value. When the pvalue 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 pvalue of flow1 is negative at round r1,
the largest length of data that flow1 can send at this round is Max. Again,
assume that flow2 is the flow with the largest pvalue which is more than Max
and attains to 2Max1. The total length of packets that flow1 and flow2 can
send at the most is: Max+2Max2+Max = 4Max2; the average value is 2Max1 and
less than 2Max. If need AC_{i} (r1)≥2Max, then the average value
of P_{j} (r1) of the other flows (j≠i) must be more than Max, that
is to say, AC_{j } (r2)>Max. By parity of reasoning, it requires
AC_{j} (1)>Max. However, the maximum value of AC_{j} (1)
is Max, and then AC_{i} (r1)<2Max; therefore, P_{i} (r)<2Max.
The statement of the lemma is proved.
Theorem 2: Given m consecutive rounds starting from round k (k≥1)
during which flowi (1≤i≤n) is active, the total number of bytes transmitted
by flowi is denoted as Sumi. For any round r (k≤r≤k+m1), if
P_{i} (r)≥0, then:
Proof: When r≥2, P_{i} (r) = P_{i} (r1)+AC_{i}
(r1)Send_{i} (r1), therefore, Send_{i} (r1) = P_{i}
(r1)P_{i} (r)+AC_{i} (r1), then:
Since, P_{i} (r)<0 and P_{i} (r) = 0 allow flowi to send
one packet, when P_{i} (r)<0, take P_{i} (r) = 0, then have
P_{i} (r)≥0. Also, P_{i} (r)<2Max from Lemma 2, therefore,
2Max<P_{i} (k)P_{i} (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 P_{i} (r)<0,
take P_{i} (r) = 0 (1≤i≤n), Then, for any time interval (t_{1},
t_{2}), FM (t_{1}, t_{2})<7Max1.
Proof: Consider two active flows i and j in time interval (t_{1},
t_{2}). Since, RQRR is a roundrobin algorithm, flowj must have an
opportunity between any two opportunities given to flowi. Let m_{i}
be the number of opportunities given to flowi in time interval (t_{1},
t_{2}) and let m_{j} be the number of opportunities given to
flowj in the same interval, then m_{i}m_{j}≤1.
Without loss of generality, assume that in the interval (t_{1}, t_{2}),
flowi starts receiving service before flowj. Thus, m_{j} = m_{i}
or m_{j} = m_{i}1. From Theorem 2, have:
Thus:
When m_{j} = m_{i}:
So, from Eq. 5 have:
namely:
then, get:
When m_{j} = m_{i}1:
namely:
then, get:
Since, Send_{u} (k+m_{j})≤P_{u} (k+m_{j})1+Max<2Max1+Max
= 3Max1 hence:
Combining Eq. 6 and 7, get FM (t_{1},
t_{2})<7Max1. The statement of the theorem is proved.
RQRR SUPPORTS MULTILINK TRANSMISSION
Many mediumsmall 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 subscriber’s 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 loadbalance between links. In this respect, MLPPP only mentioned two
simple roundrobin 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 loadbalance commendably
in multilink transmission. When there are two or more links between sending
end and receiving end, RQRR can realize loadbalance 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
for them.
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 pvalue of each link
is also set initial value 0.

Fig. 3: 
RQRR (Resilient Quantum RoundRobin) operating procedure at
sending end 

Fig. 4: 
RQRR (Resilient Quantum RoundRobin) operating procedure at
receiving end 

Fig. 5: 
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. Loadbalance 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
end; “VisitLinkCount”
is set initial value 0; the pvalue 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 link1, link2 and link3, respectively.
At sending end, loadbalance module executes RQRR algorithm to distribute seventeen
packets into three links after four rounds (hereinto SP denotes pvalue at sending
end) illustrated in Fig. 6. At receiving end, there are four
packets a, d, h, g entering into the queue of link1; seven packets b, e, f,
j, k, s, t entering into the queue of link2; six packets c, g, l, m, p, u entering
into the queue of link3 and the status is revealed in Fig. 7.
Moreover, the loadbalance situation between links can be seen from Fig.
7.
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.

Fig. 6: 
An illustration of 4 rounds in a RQRR (Resilient Quantum RoundRobin)
execution at sending end. There are three links between sending end and
receiving end and SP denotes the pvalue at sending end 

Fig. 7: 
At receiving end, packets a, d, h and q enter into the queue
of Link1, packets b, e, f, j, k, s and t enter into the queue of Link2,
packets c, g, l, m, p and u enter into the queue of Link3 

Fig. 8: 
An illustration of RQRR (Resilient Quantum RoundRobin) supporting
multilink transmission. Loadbalance 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 loadbalance
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
loadbalance 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.
CONCLUSION
This study presented a novel scheduling discipline called Resilient Quantum
RoundRobin (RQRR), which is fair, efficient and supports variablelength packet
scheduling. The implementation complexity of RQRR is O (1) and therefore, can
be easily implemented in highspeed 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 7Max1, 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 loadbalance
as well as guarantee the consistent packet sequence between receiving end and
sending end.
ACKNOWLEDGMENTS
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).