This page introduces the queuing mechanisms used by the simulation applet.
FIFO (First In First Out) is probably the simplest and the oldest queuing mechanism available. It will probably stay wildly used in the future for attractions like the Efteling in Kaatsheuvel or at your local supermarket.
Seriously, FIFO is still the most wildly used mechanism in the world. This partially because of its simplicity, partially because there were no means to assign priorities to packets until recently. The operating procedure is simple. There is one linear queue. Arriving packets are put at the rear end of the queue, and at the front of the queue, packets are extracted once they can be serviced (send). This is essentially the same procedure as is used in every place on earth where people stand in line.
There is however one question left to answer to the person implementing a FIFO Queue: Which packet to drop when the queue is full. Should that be the packet just arrived, to avoid having stored a packet for no use? Other possibilities are the packet that’s currently at the front of the queue to decrease the average delay, or the largest packet, to minimize the total number of packets dropped (this does not minimize the number of bytes dropped!)
The FIFO implementation is rather straightforward. All packets are kept in an array. New packets get added at the back, while at the front packets are extracted to receive service. When there is not enough space available, packets at the front will be dropped until there is space enough. Even if this means that a 1500 bytes packet gets dropped to clear the one extra byte necessary to store a 40 byte packet. Perhaps smart heuristics could bring a small improvement in those cases, but that is not investigated by me. The total number of bytes "kept" by all queued packets was counted in a separate variable.
LDoLL is probably the simplest priority scheme around. It was based on the Cell Loss Priority bit in the ATM (cell-) header, which is intended to give cells a storage priority in case they hit congestion. Cells with the CLP bit set are dropped before other cells get dropped. LDoLL extends the meaning of this bit by recognizing two classes of traffic: those primarily in need of a fast, Low Delay service, and those needing a Low Loss rate in the first place.
LDoLL implements these different priorities in the following way. If there is at least one low delay packet in the buffer, this will be serviced first. When there are multiple low delay packets waiting for service, the oldest is served first like in a FIFO queue. When there are no low delay packets waiting for service, the low loss packets are serviced in the same way, the oldest first. When there are too many low delay packets, low loss packets will not receive service.
This can lead to a full buffer, which would result in loss of all incoming traffic, including the low loss traffic. To avoid this problem a threshold mechanism is used. When the number of low loss packets (or bytes) exceeds a certain value, low loss packets receive service until the number of low loss packets is below the threshold value.
There are multiple ways to map the eight IEEE traffic classes to the two LDoLL priorities. The IEEE 802.1D standard uses the following ordering in two classes:
Another possibility is to assign only those traffic types that really need a low delay to low delay, and the rest to Low Loss. That would result in having Voice and perhaps Video in the Low Delay queue, and the rest in Low Loss. Network Control presents a problem. It needs a low loss just as hard as a low delay. Excess Data needs neither. This is general the problem of LDoLL: It gives two extremes, low loss and low delay, but it cannot support the low loss and the low delay demand of network traffic.
The LDoLL queue was implemented using two separate FIFO queues. One was used for Low Delay, one for Low Loss traffic. Because separate counters were kept to count the number of low Loss bytes and he number of Low Delay bytes, decisions about accepting new packets and whether Low Delay or Low Loss deserved service were easy to make. The decision to accept an incoming packet is taken the following way:
When the packet is a Low Loss packet, and its size is smaller than or equal to the total buffer size, it is accepted. Else, it is rejected. When the packet is a low Delay packet, and it is smaller than the total buffer size minus the space used by Low Loss packets it is accepted. Else, it is rejected. This implies that for a Low Loss packet, every other packet can be dropped. For a Low Delay packet, only other Low Delay packets will be dropped. When a packet can not be accepted (because it is too big, or because it requires Low Loss packets to get dropped while the packet is a Low Delay packet) no packets will be dropped by the queue. Of course, the unaccepted packet is dropped.
Minimum Fair Queuing is an attempt to share bandwidth over different traffic types, but still allowing flows to exceed there normal rate and obtain extra bandwidth if available without starving the other traffic, or risking starvation of its own type in the future. It is very similar to the various round robin schemes Cisco’s routers use (Like DRR, MDRR, WRR etc.), it differs in the method used to determine the when each sub queue receives service.
MFQ uses a separate FIFO queue for each type of traffic. Each queue gets a fixed slice of service time, which can be measured in bits (or bytes). The time slice ends prematurely when the queue is empty. When one queue receives more traffic than the other ones it will use its entire time slice while the other ones won’t need their entire slice. This will result in an early return to the first, busy queue. When the other ones do need their entire slice, the first, busy queue will not receive the extra bandwidth, but it will still receive its appointed time slice. In this way, the group in which it is classified determines a packet’s service priority. By assigning a larger time slice to one group, that group can receive a better service.
Regarding the storage priority, there are a few possibilities. The most important factor is whether the different groups share a buffer. When they don’t, it is simple: as the do not share buffer space, the storage priority problem is local to the group, and essentially the same as in a FIFO Queue. However, when they do, one has to decide whether one group may use a larger part of the buffer, and whether packets from one group are allowed to push packets from another group out of the buffer. A possible choice would be to associate each group with a certain storage priority, and let packets with a high storage priority push out packets with a lower (or equal) storage priority. Of course, one can define as many queues as one wish. Therefore, one can create every mapping from any set of class definitions (like IEEE 802.1D) to any set of queues.
Although MFQ isn’t explicitly implemented or simulated as a queuing mechanism, LDoLL Extended as well as Voice First Queuing utilizes it. In both queues, it is implemented in the same way, so I will explain it only once. Also, if it was implemented explicitly, it can be done in this way.
Each queue or group of queues is assigned a time slice. This time slice is measured in bytes. It could just as well be measured in seconds, but if we assume a constant outgoing link speed, which is done in all simulations, the effect is the same. When a packet needs to be elected for service, the mechanism checks whether the remaining time slice of the currently selected queue is positive. If it is, a packet is selected from this queue, and the size of the packet is subtracted from its remaining time slice. If the time slice has already become negative, the next queue is selected and its time slice is increased with the predetermined length of a time slice. If the time slice is still negative after this addition, the mechanism selects the next queue again.
When there are no packets that can be send (the entire queue is empty), all queues keep a remaining time slice of zero. The first packet that arrives will of course be the first packet to send. At that moment, the queue corresponding to that packet will receive a new time slice. If a queue runs out of packets when it has still a part of its time slice remaining, that part will be void to avoid accumulation.
If one queue (traffic class) is allowed to accumulate time slices, it can effectively block all other traffic when one source starts sending traffic of that class. Because the remaining time slice can go negative, time slices can have a length shorter than the maximum packet size. The only effect is that after going negative, a queue has to wait a few turns.
LDoLL Extended is a combination of MFQ and LDoLL. It allows a relatively large number of priorities in a (conceptually) simple system. Like MFQ, each type of traffic gets its own FIFO queue. But unlike MFQ, not every queue gets a private time slice. Instead groups of queues are assigned time slices, and a LDoLL mechanism is used to determine which queue may send from these groups.
The necessary time slices can be defined beforehand or dynamically adapted using (for example) RSVP [XXX]. The LDoLL mechanism used here requires some explanation since LDoLL originally only had two different traffic types, not three or more. Just like plain old LDoLL, thresholds define when a queue gets permission to send. Was there just one threshold in LDoLL, now we use an extra threshold for every extra class there is in a queue. This gives essentially one threshold for every queue there is in a group, except for the last queue. (When there are N queues, there are (N-1) thresholds. When the size of the first queue (that is the queue with the lowest class number, and thus the highest service priority) exceeds its threshold, it is serviced until it is below its threshold again. When it isn’t above its threshold, the next queue is checked in a similar matter. When no queue exceeds its threshold, the last queue is serviced. When the last queue has no packets, the second last queue is serviced, or when this has no packets waiting either, the next. This goes on until the first queue. When no queue has a packet waiting to be serviced, the time slice is ended and the remaining time is void.
However, this only accounts for service priority. When there is no place for a packet in the buffer, some packet(s) need to be dropped. Dropping the recently arrived packet is of course possible, but if this packet needs a very low drop probability this is not desired.
Therefore, we will drop packets based on their (numeric) class code. The lower this number, the lower the loss probability will be. When a packet with a certain priority arrives, packets with the same or higher class code can be dropped, the highest first: Excess traffic will be dropped first, and after all excess traffic is dropped, background traffic will be dropped. If necessary, we continue until all Network Control traffic is dropped. Because we can drop packets with the same priority for a newly arrived packet, packets already buffered can be dropped in favor of newer packets. This is favorable because this lowers the average delay.
We have to assign queues and define groups to use LDoLL Extended; especially we must determine which traffic should share a group with which traffic. First of all, Network control traffic obviously needs the best performance possible. Therefore, it gets the best service and storage priority. Voice and Video traffic are then combined because their requirements are somewhat similar. Voice gets a better service priority as it has a stricter delay requirement. Also, video traffic, especially encoded with MPEG technology, is very sensitive to loss. Controlled load will be well-behaved traffic, but also traffic that has a sort of reservation.
Because of the way MFQ works, this assignment makes it very easy to fulfill this assignment. When differentiation is necessary between two types of Controlled load, there are still 2 other queues available. In the applet these are available as "Less Controlled Load" and "Uncontrolled Load". These queues yield a slightly less reliable service (due to their higher class code the are more likely to suffer loss), which can be used to take advantage of silent periods in the Controlled Load stream. When Controlled load is constant bitrate traffic, no statistical multiplexing is possible and the two extra queues are more or less useless, but when Controlled Load is only defined by a maximum rate, and a reservation is made for that maximum, the other two queues can be used for filling up the bandwidth. Otherwise the other groups would get this bandwidth.
The last group contains the "normal" Internet type traffic. But here some differentiation is also made. First of all, Excellent effort will receive a better storage priority then Best Effort. This allows differentiation between customers, perhaps based on the amount they pay. Background is intended to allow traffic that may not influence network performance, but that may use bandwidth that would go unused otherwise. I have added the excess class. The main difference between excess and background is that it is still possible to adjust threshold levels in LDoLL such that background can receive service in the presence of Best or Excellent Effort. Excess data can only receive service when absolutely no other traffic is available. This is an exception to the normal LDoLL behavior where the background class would have a threshold, and where Excess would receive service if the Background traffic did not exceed its threshold. In the simulations done by me and in the applet, Excess can only receive service with LDoLL Extended when there is neither Excellent Effort, Best Effort nor Background data to service.
The implementation of LDoLL Extended is in fact an extension to the implementation of LDoLL. The same principle is used again, one queue for each type of traffic, and a counter to keep track of the amount of bytes each queue is using. The only difference is scale, where LDoLL implements only 2 different traffic classes, LDoLL Extended implements 10
To decide which packet is serviced, LDoLL Extended uses two mechanisms. The first mechanism decides which group of queues is currently being serviced, using a Minimum Fair Queuing mechanism. This is implemented as explained in the previous paragraph, with the annotation that LDoLL Extended uses MFQ to distinguish between groups of queues, not the separate queues themselves.
To determine the exact queue that receives service, a LDoLL-like mechanism is used. The first candidate for service is the lowest numbered, Low Loss type queue. This will only receive service if it has more bytes waiting to receive service than a predefined threshold. If that condition does not hold, the next queue, with a lower storage but higher service priority is checked. This algorithm loops until it either stops, or reaches the top where the lowest delay queue resides. From there, the algorithm loops again, but now in the opposite direction searching for the first queue that has at least one packet waiting. That will be the one to receive service.
An exception is made for the Excess queue in the triangular ordering. Instead of receiving service when all other queues are below their thresholds, the Excess queue only receives service when all other queues in the same group (i.e. Excellent- and Best Effort, and Background) are empty. This prevents excess data using any other bandwidth than excess bandwidth.
Voice First Queuing is fairly simple. Voice (and perhaps Video) are served first before all others. All others are served by another queuing system, which can (in principle) be anything you like. Cisco for example combines this with Weighted Fair Queuing under the name "Priority Queuing", a name that’s applicable to any queuing system that implements priorities. Most of the details of Cisco’s implementation are unclear to me (for example: Is there some rate controlling or traffic shaping at the input of the priority queue. If not, the priority traffic can easily use all available resources, which is probably not the operators’ intention.)
For simulation purposes, I have combined Voice First Queuing with a Minimum Fair Queuing system. Because Voice First Queuing (and also Minimum Fair Queuing) only implements service priority, some method to determine the order in which packets are dropped has to be defined. I have chosen to drop packets based on their priority code. This means that traffic with the highest code has the highest probability of getting lost. Since it is also possible to assign this traffic the absolute priority, this might not be so bad after all.
One important difference between Voice first queuing and LDoLL Extended is that Voice First Queuing does not group traffic types in single groups. Instead, every traffic type is given its own time slice.