# Analytical Model of a Weighted Round Robin Service System

Authors: Vladimir Hottmar; Bohumil Adamec
Journal: Journal of Electrical and Computer Engineering
 (2012)

---

## Abstract

This paper presents a mathematical description of Weighted Round Robin service strategy, on which basis all the perspective QoS tools that serve to manage congestion in converged packet networks work. On the basis of the presented mathematical model, it is possible to suitably configure the operational parameters (maximum queue length, distribution of the available transfer capacity) of these tools according to required values of packet delays. The implementation of the analytical model is demonstrated on a real network segment using advanced network data traffic emulator.


---

## Body

## 1. Introduction

In converged IP networks, it is necessary to provide, apart from the conventional data operation, also the video and voice communication support. Because IP packet architecture was not originally intended for real-time transfers, from the point of view of interactive communication it is necessary to solve the problem of quality guarantee of multimedia services—Quality of Service (QoS). Suitably implemented QoS tools ought to guarantee a certain quality level of processing of time-sensitive interactive applications at the expense of the quality of processing of other applications that do not necessarily require real-time transfers. Without properly implemented QoS tools, the applications that do not require real-time processing might use up the available transfer capacity and in this way make impossible the transfer of time-sensitive interactive applications. The main problem of IP packet network is thus the appropriate support of multimedia communication taking place in real time and the connected suitable management of potentially occurring congestion. The appropriate implementation of QoS tools mainly requires correct setting of the operation parameters of these tools. In order to provide high Quality-of-Service (QoS) in today’s high-speed converged networks, WRR mechanism assigns different priorities to different queues. WRR also ensures fair selection interval among all active queues with minimal delay and jitter [1]. In this scheduling algorithm, a weighting coefficient for each queue determines how many bytes of data the system delivers from the queue before it moves on to the next queue. The WRR mechanism cycles through the queues. For each queue, packets are sent until the number of bytes transmitted exceeds the bandwidth determined by the queue’s weighting coefficient, or the queue is empty [2, 3]. Then the WRR mechanism moves to the next queue. If a queue is empty, WRR mechanism will send packets from the next queue that has packets ready to send. This mechanism guarantees a minimum bandwidth to each queue, and allows the minimum to be exceeded if one or more of the port’s other queues are idle.However, when all the queues are located, each is limited to its maximum bandwidth according to its assigned weight—no queue achieves more than a predetermined portion of transfer capacity when the transmission line is under stress [4]. WRR includes several significant benefits. This scheduling mechanism can be implemented in hardware, so it can be applied to high-speed interfaces in both the core and at the edges of the network. WRR mechanism also ensures that all service classes have access to at least some configured amount of network capacity to avoid bandwidth starvation. WRR queuing provides coarse control over the percentage of output port bandwidth allocated to each service class. Classification of traffic by service class provides more equitable management and more stability for network applications than the use of priorities or preferences. WRR queuing is based on the belief that resource reduction is a better mechanism to control congestion than resource denial [1, 2]. Other information about WRR models and detailed description of the status quo can be found in source [4].


## 2. Analytical Modeling of Weighted Round Robin Service Strategy

In Figure1 we can see the model of a Weighted Round Robin network node with M queues. The offered traffic with λ intensity consists of data flows of individual queues with intensities λ1, λ2 to λM, from which a certain part λ1S, λ2S to λMS is processed by the node and a certain part λ1L, λ2L to λML is discarded by the node. In the ith queue maximally Nimax packets may be stored. The average time needed to service a packet of ith queue is E(Ti). Intensity of the service of the ith queue is μi. The overall transfer capacity BR of output interface is divided according to configuration among individual queues [4].Figure 1
Model of Weighted Round Robin network node.Proposed analytical model describes the specific conditions when the WRR service system is congested. This service mode is analyzed in order to provision a certain parameter reserve for normal noncongested mode. In the case of congestion all the queues work with the predefined portion of time period. Therefore, obtained results include a certain useful reserve for the normal noncongested mode.Processing the traffic by the Weighted Round Robin service strategy means that the service of individual queues is realized only during certain, in general different, time intervalsΔi. The probability that the Weighted Round Robin network node is in the state of service of kth queue is given by the relation [4]:(1)P(i=k)=ΔkΔ1+Δ2+⋯+ΔM=ΔkΔ=BRkBR.
When Wkn is the average waiting time of a packet belonging to the kth queue, having entered the network node during service of the nth queue, then the average waiting time of packet belonging to the kth queue will generally be given by the formula:(2)Wk=Wk1⋅P(i=1)+⋯+WkM⋅P(i=M).
In the case of two queues, the average waiting time of packets in the first queue is given by the relation:(3)W1=W11⋅BR1BR+W12⋅BR2BR.
Figure 2 demonstrates a situation when a packet belonging to the first queue comes in the time of service of the first queue. In the moment of arrival of packet belonging to queue i=1, on average there are N1packets belonging to queue i=1 that  precedes  it.The average number of packets transferred since the moment of arrival of the packet in question to the moment of finishing the interval Δ1 of period Δk is N1(k). Up to the moment of servicing the considered packet the entire interval Δ1 will take place n times on the whole and the entire interval  Δ2(n+1) times altogether. Then the average waiting time of the packet, in question is given by the relation:(4)W11=N1(k)⋅E(T1)+[N1-N1(k)]⋅E(T1)+[n+1]⋅Δ2.
The average waiting time computation comprises of the three-parts residual service time of the packet in service at the arrival,service time of the class-1 packets in queue, and the total intervals assigned to class-2 packets. As shown in Figure 2, residual service time is included in N1(k) variable. In general, this variable assumes the decimal numbers; decimal part of this number represents the residual service time of the packet in service at the moment of arrival.Figure 2
Time conditions at the arrival ofi=1 packet during servicing the i=1 queue.Since the considered packet could come during the intervalΔ1 of period Δk at any moment with the same probability, on average it will come in the moment Δ1/2 and during the period Δk it will spend time Δ1/2, in the queue. During this time on average N1(k) packets will be processed from the arrival time of the given packet to the moment of finishing interval Δ1 of period Δk. It is valid that(5)N1(k)=Δ1[2⋅E(T1)].After the passage of periodΔk, there will be on average N1-N1(k) packets of category i=1 queued before the considered packet. A certain part of these packets will be processed during n whole intervals Δ1 of periods Δk+1 to Δk+n and a certain residual part will be processed during interval Δ1 of periods Δk+n+1 together with the considered packet. Since the moment of finishing period Δk to the moment of transfer of the considered packet, interval Δ1 will take place n+ε times on whole. Variable ε is the mean value of the proportion of the interval Δ1 of period Δk+n+1 that is necessary for processing the residual part of packets. It can be expressed by(6)n+ε=[N1-N1(k)][Δ1/E(T1)]=[N1⋅E(T1)]Δ1-12.
During one interval Δ1 up to Δ1/E(T1) packets of category i=1 are serviced. Thus, during the interval Δ1 of period Δk+n+1, before the considered packet there might be up to [Δ1/E(T1)]-1 packets serviced and on average (1/2)·[Δ1/E(T1)]-1/2 packets are serviced. Since E(T1)/Δ1 is the proportion of interval Δ1 needed to transfer one packet, then for the mean value of the proportion of interval Δ1 of period Δk+n+1, needed to transfer the residual part of packets, following relation is valid:(7)ε=[E(T1)(2⋅Δ1)]⋅[Δ1E(T1)-1]=[1-E(T1)Δ1]⋅12.
It then follows that for the number of whole intervals Δ1 taking place since the arrival moment of a considered packet to the starting moment of its servicing, it is valid that(8)n=[E(T1)Δ1]⋅[N1+12]-1.
After substituting (5) and (8) to (4), the result is(9)W11=N1[1+Δ2Δ1]E(T1)+Δ2E(T1)2Δ1.A situation when a packet belonging to the first queue is coming in the moment of servicing the second queue which can be analyzed in the same way as before. At the arrival moment of packeti=1, on average there are other N1 packets in the i=1 queue before it. The average number of packets processed since the arrival moment of the considered packet to the moment of expiration of period Δk is N2(k). Until the moment of servicing the considered packet, the entire interval Δ1 will take place n times and the entire interval Δ2n times as well. It follows that the average waiting time of the considered packet is given by the relation:(10)W12=N2(k)⋅E(T2)+N1⋅E(T1)+n⋅Δ2.
Using the same method as before we obtain(11)W12=N1[1+Δ2Δ1]E(T1)+Δ2E(T1)2Δ1=W11.
By substituting of (9) and (11) into the expression (3) we obtain(12)W1=N1[1+Δ2Δ1]E(T1)+Δ2E(T1)2Δ1.
The relation between the average number of packets in queue N1, the average waiting time of packets W1, and processed intensity of entry flow λ1S is expressed by Little’s formula:(13)N1=λ1S⋅W1.After substituting Little’s formula (13) into the relation (12), we obtain(14)W1=[Δ2E(T1)/(2⋅Δ1)][1-λ1SE(T1)⋅(1+Δ2/Δ1)].
After substituting the relation between the average time needed to transfer a packet and the intensity of service E(T1)=BR1/(BR·μ1)  to the denominator of the expression (14), introducing the load coefficient of processed traffic ρ1S=λ1S/μ1S and finally after substituting the relation between the average packet size and the average time needed to transfer it E(T1)=E(X1)/BR  to the numerator of (14), the result will be(15)W1=[BR2⋅E(X1)][BR1⋅2(1-ρ1S)⋅BR].
From the expression (15) it is obvious that the average time spent in the queue of packets belonging to the first queue W1 grows linearly with the average size E(X1) of these packets. The bigger the packets are being sent, the longer will be their average waiting time W1. Further, the average waiting time W1 depends on the ratio of sizes of guaranteed proportions BR1, and BR2 from the overall capacity BR. The bigger is the proportion BR1, the smaller will be the average waiting time W1.Figure3 demonstrates the graphic interpretation of the relation (15) for ρ1S=0.93 and BR=256 kbps. Taking Figure 4 into account, it is obvious that the average waiting time W1 grows most rapidly in the direction of the growth of average packet size E(X1) and concurrently to the direction of decrease of the size of portion BR1. The smaller the size of the portion BR1 is, the steeper will be the increase of the average waiting time W1, which depends on the increasing average packet size  E(X1). The bigger the average packet size E(X1) is, the steeper will be the increase of the average waiting time W1 that depends on the decrease of the proportion BR1.Figure 3
Average waiting time ofi=1  packets for ρ1S=0.93 and BR=256 kbps.Figure 4
Time conditions at the arrival ofi=1 packet waiting for period W1max.The relation for the average waiting time can be generalized using mathematical induction. For the average waiting time of packets ofith queue Wi, it is valid that(16)Wi=[(BR-BRi)⋅E(Xi)][BRi⋅2(1-ρiS)⋅BR].The maximum queue lengthN1max can be expressed using the required value of maximum delay of i=1 packets [5].The maximum value of waiting timeW1max reached by packet i=1 will be in the case of entering the system just in the moment when the service of its queue has been finished. Concurrently,  just  N1max-1 packets are located before it, so the considered packet is placed in the last position in the queue. For the maximum waiting time W1max of packet belonging to the first queue according to   Figure 4, it is valid that(17)W1max⁡=(n+1)⋅Δ2+(N1max⁡-1)⋅E(T1).
After deduction for maximum queue length N1max, we get(18)N1max⁡=[W1max⁡+(E(X1)/BR)⋅(1+BR2/(2BR1))](E(X1)/BR)⋅(1+BR2/BR1).The relation for the maximum queue length can be generalized using mathematical induction. For the maximum queue length of packets ofith queue, it is valid that(19)Nimax⁡=[Wimax⁡+(E(Xi)/BR)⋅(1+(BR-BRi)/(2BRi))](E(Xi)/BR)⋅(1+(BR-BRi)/(BRi)).


## 3. Implementation of the Mathematical Model and Experimental Results

The drawn-up mathematical model of a WRR service system was used by configuration of real network architecture emulating a large company network-campus LAN. The created emulating model consists of two segments: LAN 1 (client side segment) and LAN 2 (server side segment). These network parts represent far-flung individual segments of a large company network. The interconnection of individual network segments is created by WAN link emulated by PPP multilink. The data traffic is emulated by multifunctional hardware network emulator. Monitoring of data traffic processing is realized by computers and switches that realize the port mirroring.Undesirable congestions can especially occur by the transfer of data traffic from high-speed LAN link to low-speed WAN link [5]. In order to accomplish a reliable voice or video communication, it is necessary to configure suitable QoS tools in the appropriate network devices that guarantee the required transfer quality of multimedia communication [6].Generated data traffic operations are specified in the emulator event list. Each line in this list presents one required transaction. The emulated users generate load according to event list in the way that progressively require carrying out all events defined in the list. For the needs of emulation, four individual event lists were created. According to the first list the SIP VoIP traffic is generated, according to the second list the RTSP video traffic is generated, according to the third list the SMTP electronic mail traffic is generated, and finally according to the last list the FTP file transfer traffic is generated.The simplest and in most cases default mechanism of traffic processing is FIFO strategy. It is the elementary packet processing technique that was used as first. For the purpose of detailed statistical analysis of transported data traffic, the additional software application was created. It calculates particular statistical parameters such as the empirical probability distribution of delays of transported packets. In Figure5 there are demonstrated FIFO/CBWFQ results for voice and video data traffic. The average delay of VoIP RTP packets W1=652 ms is unsatisfactory, similarly, average delay of video RTP packets W2=579 ms is unsatisfactory. Since processing of interactive packets by FIFO strategy is unsatisfactory from the point of view of quality parameters, it is necessary to implement the more sophisticated mechanism such as CBWFQ. It is needful to create individual operation classes for interactive voice and video packets. Interactive voice RTP packets will belong to the operation class named voice-traffic and video RTP packets will belong to the operation class named video-traffic. For individual operation classes it is necessary to configure the operation parameters that are minimal guaranteed bandwidth and maximal queue length. The setting of these parameters will be realized according to drawn-up mathematical model.Empirical delay probability distribution for  FIFO/CBWFQ  strategy.
(a)(b)(c)(d)By statistically found-out data traffic parameters (average packet sizes:E(X1)=1712 bit,  E(X2)=7808 bit, load coefficients of processed traffic ρ1S=0.93, ρ2S=0.88), we can assume that the required average delay of voice RTP packets should be 100 ms with the peak 700 ms and required average delay of video RTP packet should be 150 ms with the peak 8700 ms.For the size of guaranteed proportion from the total available capacityBR=256 kbps for the first operation class from the relation (16) we get (BR1/BR)·100%≈30% and for the second class we get (BR2/BR)·100%≈45%.For the queue length of the first operation class from the relation (19) we get N1max≈32 packets and for the second class we get N2max≈128 packets.All other packets will be processed without any QoS guarantees as best effort traffic therefore setting operation parameters for this class has no sense [7, 8].In Figure5 there are demonstrated results for FIFO/CBWFQ strategy. The average delay of VoIP RTP packets compared with FIFO strategy decreased from 652 ms to 112 ms and average delay of video RTP packets decreased from 579 ms to 153 ms. The average delays obtained by emulation are approximately in agreement with required values. The deviations are mostly caused by the finite number of analyzed packets. The considerably lower value of peak delay W2max obtained by emulation compared with proposed required value is the result of the fact that the second queue was not even once filled during the emulation. From Figure 5 it is further apparent that approximately 73% of voice RTP packets have acceptable delay in the range from 0 ms to 157 ms, 25% of these packets have limit delay value in the range from 157 ms to 392 ms and only 2% of packets have unsatisfactory delay in the range from 392 ms, and more. Similarly, approximately 73% of video RTP packets have delay in the range from 0 ms to 134 ms, 20% of these packets have delay in the range from 134 ms to 401 ms and only 7% of packets have delay in the range from 401 ms and more.



---

*Source: 374961-2012-04-22.xml*