Given that neither the network capacity nor the queues capacity is infinite, it is possible to overload the network or the queues with packets. To prevent that, packet policing is used to discard input packets and packet scheduling is used to time output packets.
The stochastic fair queuing algorithm is used when many flows need to compete for bandwidth. The algorithm approximates having a queue for each flow and sending data from the queues in a round robin fashion. Rather than having as many queues as flows, however, the algorithm hashes a potentially large number of flows to a relatively small number of queues. To compensate for the possibility of a collision that would make multiple flows share one queue, the algorithm changes the hash function periodically.
The token bucket algorithm is used when single flow needs to observe bandwidth. The flow is assigned a bucket for tokens with a defined maximum capacity. Tokens are added regularly and removed when data is sent, no tokens are added to a full bucket, no data can be sent when no tokens are available. The speed of adding tokens determines bandwidth limit. The capacity of token bucket determines fluctuation limit.
The class based queuing algorithm is used when multiple flows need to share bandwidth. The flows are separated into hierarchical classes that specify their bandwidth requirements and can borrow unused bandwidth from each other.
A class has a level. The level of a leaf class is 1, the level of a parent class is one higher than the maximum level of its children.
A class is under limit if it transmits below the allocated capacity. A class is over limit if it transmits above the allocated capacity. A class is on limit otherwise.
A class is unsatisfied if it is under limit and it or its siblings have data to transmit. A class is satisfied otherwise.
A class is regulated if the class based queuing algorithm prevents it from sending data. A class is unregulated otherwise.
V klasické Formal Sharing implementaci může třída zůstat unregulated pokud není over limit, nebo pokud má předka na úrovni i, který není over limit a ve stromu nejsou žádné unsatisfied třídy úrovně nižší než i.
Drobný nedostatek algoritmu je příliš složitá podmínka regulace. Proto se definuje Ancestor Only Sharing, ve kterém třída zůstává unregulated pokud není over limit, nebo pokud má předka, který je under limit. Nevýhodou tohoto přístupu pochopitelně je, že bude omezovat over limit třídy i tehdy, pokud tyto momentálně nikomu nevadí.
Další variantou je Top Level Sharing, které definuje maximální úroveň, ze které si ještě třídy smí půjčovat přenosové pásmo. Třída pak smí zůstat unregulated pokud není over limit nebo pokud má předka do dané úrovně, který je under limit. Úpravou maximální úrovně se pak dá tento algoritmus regulovat, pro nekonečnou úroveň je stejný jako Ancestor Only Sharing, pro stejnou úroveň jako je nejmenší úroveň unsatisfied třídy je téměř stejný jako Formal Sharing, pro úroveň 1 algoritmus reguluje všechny over limit třídy a tím vyprazdňuje fronty.
Pro nastavování maximální úrovně pro Top Level Sharing se zpravidla používá heuristika. Jedna z možných funguje následujícím způsobem:
Kdykoliv přijde paket třídy, která není over limit, maximum je 1 (tj. heuristika se snaží zaručit třídám jejich přenosové pásmo).
Kdykoliv přijde paket třídy, která je over limit, ale má under limit předka třídy nižší než je aktuální maximum, maximum je tato třída (tj. na rostoucí zatížení reaguje snižováním možnosti půjčovat si přenosové pásmo).
Kdykoliv třída odešle paket a má buď prázdnou frontu nebo se stane regulovanou, maximum je nekonečno (tj. heuristika uvolňuje omezení když se mění podmínky).
References.
Floyd S., Jacobson V.: Link-Sharing and Resource Management Models for Packet Networks, IEEE/ACM Transactions on Networking 3(4), August 1995
The goal of the random early detection queuing algorithm is to avoid anomalies associated with algorithms that fill a queue first and drop a queue tail when the queue is filled. A weighted average of the queue length is kept and within a range of minimum and maximum queue lengths, packets are marked or dropped with a probability proportional to the current weighted average of the queue length. This gives the flow control algorithms of the transport protocols an early warning before the queue is filled.
References.
Floyd S., Jacobson V.: Random Early Detection Gateways for Congestion Avoidance