To solve the problems associated with setting a given speed for outgoing traffic, an algorithm was developed in which the traffic bandwidth control 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 network 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 average algorithm (EMA).
The development of modern telecommunications is largely determined by the
widespread 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 [
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
monopolization 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) [
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 [
In this paper, we propose a new queue scheduling algorithm based on direct measurement 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 channel 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
average algorithm (EMA) [
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 behavior 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].
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 received 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 awaiting 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.
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 bandwidth, 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 presence 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 instantaneous 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 markers 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 positions p Start Selection1, ... p Start Selection4), and also returns markers at the position 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.
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 channel counted by the “Scanning” subnet.
The subnet consists of the following nodes: ─ interface positions p Calculated VFrame1, ... p Calculated VFrame4 contain markers 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 corresponding 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 bandwidth to the first stream passing through the ready condition. Another algorithm EMA-TSS (EMA Time Selected Service) is proposed, in which the method for providing 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 average rate values at the end of the frame transmission, also satisfies the condition for the time the frame is in the queue. 4
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 character: 25% of all frames have minimum and maximum length (512 and 12176, respectively), 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 different sets of input data: inconsistent (Table 1) and consistent (Table 2) traffic. The highest average jitter values are shown in bold.
QoS Allocated bandwidth, %
Traffic share DRR DRR-TSS EMA-VF EMA-TSS
QoS Allocated bandwidth, %
Traffic share DRR DRR-TSS EMA-VF EMA-TSS
Analysis of the simulation results shows that with inconsistent traffic, the EMATSS algorithm aligns the average frame latency values in various queues most efficiently in comparison with other algorithms presented in the table. It should be especially 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
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. 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://ciscotelepresence.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), 299307 (2017).