=Paper=
{{Paper
|id=Vol-2922/paper006
|storemode=property
|title=Modeling a queue scheduling algorithm in network switches using bitrate measurement
|pdfUrl=https://ceur-ws.org/Vol-2922/paper006.pdf
|volume=Vol-2922
|authors=Nikolay Konnov,Maxim Mitrokhin,Dmitry Patunin
}}
==Modeling a queue scheduling algorithm in network switches using bitrate measurement==
https://ceur-ws.org/Vol-2922/paper006.pdf
Modeling a queue scheduling algorithm in network
switches using bitrate measurement
Nikolay Konnov[0000-0002-8656-838X], Maxim Mitrokhin[0000-0001-6719-4610]
and Dmitry Patunin[0000-0001-9438-7004]
Penza State University, 40, Krasnaya Street, Penza, 440026, Russian Federation
knnpnz@mail.ru
Abstract. To solve the problems associated with setting a given speed for out-
going traffic, an algorithm was developed in which the traffic bandwidth con-
trol algorithm works inside the queue scheduling block in conjunction with the
shaping procedure. The article discusses the results of simulation modeling in
the CPN Tools package of the proposed queue scheduling algorithms in a net-
work switch with quailty of service (QoS) support, based on the measurement
of the bit rate by the method of exponential smoothing. The simulation results
show the efficiency of bandwidth management with real-time measurement of
the current bit rate of data streams in switches using the exponential moving av-
erage algorithm (EMA).
Keywords: Switch, ethernet, quality of service, shaping, bandwidth control,
scheduling Aalgorithm, delay, jitter, petri nets.
1 Introduction
The development of modern telecommunications is largely determined by the wide-
spread implementation of quality of service (QoS) methods, which means the ability
of the network to provide a given service to the traffic of each application: throughput
(bandwidth), packet transmission delay and its variation (jitter), the share of lost
packets. Among the many QoS mechanisms used in network switches and routers,
queue scheduling algorithms are of great importance, which refers to the rules for
selecting queues for service and allocating bandwidth to certain traffic, implemented
as management of continuous service of selected queues. It is the scheduling that
determines the frame transmission delay and jitter, the values of which are important
when transmitting real-time traffic through packet-switched networks [1-2].
In network switches, such scheduling algorithms as weighted round-robin (WRR)
and deficit round-robin (DRR) are widely used. A feature of these algorithms is the
use of cyclic priority when choosing a queue for service, which excludes monopoliza-
tion of the channel by any traffic, and the duration of continuous queue service is
determined by a credit proportional to the bandwidth of the output channel allocated
for a given traffic class. The DRR algorithm, in contrast to WRR, provides a high
accuracy of setting the bandwidth, since the credit is set in bytes (bits) [3]. Both algo-
rithms have a common drawback — uncontrolled jitter of switched frames due to the
difference in the waiting time of frames in different queues, which is caused by the
deterministic order of service. In addition, the frame delay of a given QoS class, as
well as the corresponding queue sizes, is dependent on the allocated bandwidth for the
particular class. This leads to an increase in frame latency and congestion of queues in
channels with a small assigned bandwidth with a pulsating nature of traffic due to its
self-similarity. In addition, the transfer of large portions of traffic data of the same
class leads to a burst of traffic, which in turn increases the load on the buffers of sub-
sequent telecommunication devices.
In order to ensure fair distribution of free channel bandwidth, a deficit weighted
scheduling algorithm was proposed with limiting the duration of the queuing session
and selection of the waiting time for buffered frames (DRR-TSS), which provide a
smaller spread of jitter values when moving traffic of different QoS classes, as well as
more comfortable conditions for traffic transmission in case of imbalance in the
bandwidth allocated to them [4]. However, this scheduling algorithm also has disad-
vantages in that it is impossible to fully compensate for traffic pulsations and it is
impossible to provide the most efficient allocation of free traffic bandwidth due to the
applied weighted bandwidth control according to a predetermined value.
2 Materials and methods
In this paper, we propose a new queue scheduling algorithm based on direct meas-
urement in the output channel of the switch of the instantaneous bit rate of data
streams of different QoS classes and regulation of this rate taking into account the
declared bandwidth value for this traffic and the share of free bandwidth in the chan-
nel at a given time. In this case, the order of selection of queues for service should be
determined by their current state (the size of the queue or the buffering time of the
frames stored in them).
To measure the data flow rate, it is proposed to use the exponential moving aver-
age algorithm (EMA) [5] because of its simplest hardware and software implementa-
tion. The peculiarity of using EMA for the purpose of assessing the current bit rate of
the data stream in the channel is not in the periodic calculation of the EMA, but at the
moments of the beginning of the transmission and the end of the transmission of the
frame. Due to the constancy of the bit rate of the frame, the estimation of the values of
the current bit rate is carried out by processing the values of the frame length and the
duration of interframe pauses [6].
The choice of the most effective methods of quality of service management, the
development of new QoS mechanisms is a difficult task that can be solved by means
of simulation modeling. An effective tool for modeling various aspects of the behav-
ior of complex telecommunication systems, not tied to specific equipment, is the CPN
Tools, based on the mathematical apparatus of hierarchical timed colored Petri nets
[7-10].
3 Results
The Ethernet switch model with IEEE 802.1 Q / P [11] support consists of several
functional modules. The Buffer subnet simulates the activity of the output port buffer
of a switch; its general structure is shown in Figure 1. The Buffer subnet consists of
the following components:
─ contact positions Buffer In and Buffer Out, through which traffic tokens are re-
ceived and issued, respectively;
─ the subnet of the frame classifier Classifier, which analyzes the type of incoming
traffic and routes it to one of four queues in accordance with the value of the QoS
class;
─ subnets of queues Queue1, ... Queue4, which represent traffic queues of QoS
classes 6-7, 4-5, 2-3, 0-1, respectively. The queues contain tokens of frames await-
ing scheduling;
─ the queue scanning algorithm subnet Scan, which directly selects the next queue
according to a specific scheduling algorithm;
─ subnets of bandwidth control nodes Bend1, ... Bend4, which control the bandwidth
allocated to each type of traffic.
Fig. 1. Switch output buffer subnet.
The queue scheduling algorithm based on measuring the instantaneous bit rate of
streams was presented in the form of two subnets: Scanning and Queue Scanning. The
queue scheduling algorithm includes the following sequence of actions:
1. Calculation of the values of the instantaneous bit rate at the moment of the start
of frame transmission in all channels;
2. Based on the obtained values, the predicted values of the instantaneous bit rate at
the moment of the end of the frame transmission, as well as the remaining free band-
width, are calculated;
3. Round-robin queuing, which makes a service decision based on the calculated
values of the predicted rates of each channel;
4. Storing the predicted rate value of the ready-to-serve channel for calculating the
next bit rate value at the moment of the frame transmission start.
The first subnet (Figure 2) simulates the operation of a node, the results of which
allow you to control the bandwidth. The subnet consists of the following nodes:
─ interface positions p Indicator 1, ... p Indicator 4 contain markers of the
FRAME_SIZExINPUT_TIME composite type, signal the presence of a pending
frame fetch from the queue;
─ interface position p Outport Free contains markers of the INTT type, signals that
the output port is not occupied;
─ the transition t Calculate VPause, which counts when the instantaneous bit rate is
triggered at the end of frame transmission in all channels, in addition to the pres-
ence of markers in incoming positions, has a trigger guard condition:
─ [(frame_size1>0 andalso input_time1>0)
─ orelse (frame_size2>0 andalso input_time2>0)
─ orelse (frame_size3>0 andalso input_time3>0)
─ orelse (frame_size4>0 andalso input_time4>0)];
─ the position p Calculated VPause contains markers of the DATA_PACK composite
type, which contain the values calculated in the t Calculate VPause transition, as
well as the values necessary for further calculation of the predicted instantaneous
bit rate at the moment of the end of frame transmission in the next hop;
─ transition t Calculate VFrame, which, when triggered, counts the value of the in-
stantaneous bit rate at the end of frame transmission in all channels, as well as the
remaining free bandwidth;
─ position p Calculated VFrame, stores markers of the composite type
VFRAME_PACK with all values of the predicted rates for transmitting the frame
rate value from the served channel in position p Prev vf1, ... p Prev vf4;
─ interface positions p Calculated VFrame1, ... p Calculated VFrame4 contain mark-
ers of the BOOL type, according to the conditions on the arcs going to them from
the transition t Calculate VFrame, a channel ready for service is determined;
─ transition t Finish Scanning, when triggered, sends a marker about the beginning of
the selection from the ready frame queue (transfers the marker to one of the posi-
tions p Start Selection1, ... p Start Selection4), and also returns markers at the posi-
tion p Prev vf1, ... p Prev vf4;
─ interface positions p QS Out 1, ... p QS Out 4 contain tokens of the BOOL type,
which are the result of the operation of the round-robin queuing mechanism;
─ the positions p Prev vf1, ... p Prev vf4 contain markers of the
PREV_VFxOUTPUT_TIME type.
Fig. 2. Bandwidth control subnet.
The “Queue Scanning” subnet (Figure 3) simulates the activity of a round robin
queuing mechanism that makes a service decision based on the bit rates of each chan-
nel counted by the “Scanning” subnet.
Fig. 3. Queuing subnet.
The subnet consists of the following nodes:
─ interface positions p Calculated VFrame1, ... p Calculated VFrame4 contain mark-
ers of the BOOL type, according to the conditions on the arcs going to them from
the transition t Calculate VFrame, a channel ready for service is determined;
─ the transition t Queue Scanning, when triggered, transmits along the output arcs for
which the conditions were set, in the position p QS Out 1, ... p QS Out 4 markers,
the true value of one of which indicates the readiness to fetch a frame from the cor-
responding queue;
─ position p Queue Number contains a marker of type INT and serves as a queue
counter from 1 to 4;
─ interface positions p QS Out 1, ... p QS Out 4 contain tokens of the BOOL type,
which are the result of the operation of the round-robin queuing mechanism.
The simulation results of the scheduling algorithm based on the measurement of
the instantaneous bit rate show that this algorithm loses to other algorithms in terms
of QoS characteristics such as jitter. One of the reasons for these results is the chosen
method of providing the remaining free bandwidth to the stream. In the EMA-VF
(EMA Velocity Frame) algorithm, it was proposed to assign the rest of the free band-
width to the first stream passing through the ready condition. Another algorithm
EMA-TSS (EMA Time Selected Service) is proposed, in which the method for pro-
viding the remaining bandwidth is based on predicting based on the waiting time of
frames in queues. Now the unoccupied part of the free bandwidth is assigned to that
stream, which, in addition to passing the readiness conditions according to the aver-
age rate values at the end of the frame transmission, also satisfies the condition for the
time the frame is in the queue.
4 Discussion
To assess the effectiveness of the proposed algorithms in comparison with the
known algorithms, they were modeled. The input traffic was modeled using a special
Petri net [12] and is a combination of two components, the merging of which forms a
stream of frames with pronounced bursts:
─ regular, representing a sequence of 100 two-frame bursts with a maximum length
of 12176TI;
─ random, with frames whose length distribution has a pronounced bimodal charac-
ter: 25% of all frames have minimum and maximum length (512 and 12176, re-
spectively), the length of the rest is evenly distributed in the remaining range.
The channel load factor, calculated from the input implementation, is 0.798. The
model time is expressed in TI clock intervals (one clock corresponds to 100 ns
Ethernet or 10 ns for Fast Ethernet). As an efficiency criterion, the maximum average
value and variations in the average values of traffic jitter of various QoS classes are
considered. The tables show the average values of frame jitter for queues on two dif-
ferent sets of input data: inconsistent (Table 1) and consistent (Table 2) traffic. The
highest average jitter values are shown in bold.
Table 1. Average frame jitter (inconsistent traffic).
QoS 6-7 4-5 2-3 0-1
Allocated bandwidth, % 40 30 20 10 Variation
Traffic share 0.25 0.25 0.25 0.25
DRR 18972 18954 23461 38520 19566
DRR-TSS 21341 23035 25817 28483 7142
EMA-VF 9392 11119 17686 45975 36583
EMA-TSS 22351 21677 21603 22331 747
Table 2. Average frame jitter (consistent traffic)
QoS 6-7 4-5 2-3 0-1
Allocated bandwidth, % 40 30 20 10 Variation
Traffic share 0.4 0.3 0.2 0.1
DRR 23291 22478 29119 28998 6641
DRR-TSS 23071 24630 25029 29929 6858
EMA-VF 16142 15741 27806 17954 12064
EMA-TSS 23488 19116 15313 12648 10840
Analysis of the simulation results shows that with inconsistent traffic, the EMA-
TSS algorithm aligns the average frame latency values in various queues most effi-
ciently in comparison with other algorithms presented in the table. It should be espe-
cially noted that the EMA-TSS algorithm reduces the largest value of the average
jitter compared to both the classic deficit round-robin and its modernization..
5 Conclusion
The proposed queue scheduling model based on measuring the instantaneous bit rate
of streams is efficient and shows its certain advantages over the known ones. It should
be noted that the given implementation of the queue scheduling algorithm based on
direct measurement of the bit rate of data streams is preliminary. This algorithm has
great potential for further development by improving the methods of providing free
bandwidth to data traffic with different QoS, based on prediction, modifying static
thresholds into adaptable ones.
References
1. Olifer, N., Olifer, V.: Computer Networks: Principles, Technologies and Protocols for
Network Design, Wiley (2005).
2. Barreiros, M., Lundqvist, P.: QOS-Enabled Networks: Tools and Foundations, Wiley
(2015).
3. Vegesna, S., R.: IP Quality of Service, Cisco Press (2001).
4. Konnov, N., Semenov, A., Patunin, D.: Analysis of Dynamical Queue Scheduling Algo-
rithm with Service Loop Duration Restriction for Network Services. In: 2020 Moscow
Workshop on Electronic and Networking Technologies (MWENT), 1–5, IEEE (2020).
5. Droke, C.: Moving Averages Simplified, Marketplace Books, Columbia (2001)
6. Domnin A., Konnov N., Mekhanov V.: Modeling EMA and MA Algorithms to Estimate
the Bitrate of Data Streams in Packet Switched Networks. Dudin A., Nazarov A., Yakupov
R., Gortsev A. (eds) Information Technologies and Mathematical Modelling. ITMM 2014.
Communications in Computer and Information Science, 487. Springer, Cham (2014).
7. Jensen, K., Kristensen, L.: Coloured Petri Nets: modelling and validation of con-current
systems, Springer, Verlag (2009).
8. Zaitsev, D.: Switched LAN simulation by colored Petri nets. Mathematics and Computers
in Simulation, 3(65), 245-249 (2004).
9. Brahimi, B., Aubrun, C., Rondeau, E.: Modelling and Simulation of Scheduling Policies
Implemented in Ethernet Switch by Using Coloured Petri Nets. In: 11 IEEE Conference on
Emerging Technologies and Factory Automation, 667-674, IEEE, Prague, Czech Republic
(2006).
10. Mekhanov, V.: The traffic passage quality estimation for algorithms of the weighed fair
service of queues. Informatization of education and science, 1(13), 59-67 (2012).
11. IEEE 802.1p/Q: VLAN Tagging and CoS, https://cisco-
telepresence.blogspot.com/2012/05/ieee-8021pq-vlan-tagging-and-cos.html.
12. Konnov, N., Nikishin, K.: The traffic generator of switch Ethernet using colored Petri
nets”. Models systems networks in economics technology nature and society, 1(17), 299-
307 (2017).