Deficit každý s každým - Deficit round robin
Deficit Round Robin (DRR), taky Deficit vážený kulatý Robin (DWRR), je plánovací algoritmus pro plánovač sítě. DRR je jako vážené spravedlivé řazení do fronty (WFQ), paketová implementace ideálu Obecné sdílení procesoru (GPS). Navrhli to M. Shreedhar a G. Varghese v roce 1995 jako efektivní (s O (1) složitost) a spravedlivý algoritmus.[1]
Detaily
V DRR plyne plánovač zpracovávající N[A] je nakonfigurován s jedním kvantem pro každý tok. Tato globální myšlenka spočívá v tom, že v každém kole jde o tok lze odeslat maximálně bajtů a zbývající, pokud existují, jsou hlášeny do dalšího kola. Tímto způsobem tok čísel i dosáhne minimální dlouhodobé datové rychlosti , kde je rychlost odkazu.
Algoritmus
DRR prohledává postupně všechny neprázdné fronty. Když neprázdná fronta je vybráno, jeho počitadlo deficitu je zvýšeno o jeho kvantovou hodnotu. Hodnota čítače deficitu je pak maximální počet bajtů, které lze v tomto tahu odeslat: pokud je čítač deficitu větší než velikost paketu v čele fronty (HoQ), lze tento paket odeslat a hodnotu počitadla se sníží o velikost paketu. Poté je velikost dalšího paketu porovnána s hodnotou čítače atd. Jakmile je fronta prázdná nebo je hodnota čítače nedostatečná, plánovač přeskočí na další frontu. Pokud je fronta prázdná, hodnota čítače deficitů se vynuluje.
Proměnné a konstanty const integer N // Nb front fronta const integer Q [1..N] // Na frontu kvantové celé číslo DC [1..N] // Na frontu deficit počítadlo fronta fronta [1..N] // Fronty
Plánování smyčkyzatímco skutečný dělat pro i v 1..N dělat -li není fronta [i]. prázdné () pak DC [i]: = DC [i] + Q [i] zatímco(ne fronta [i] .empty () a DC [i] ≥ fronta [i] .head (). Size ()) dělat DC [i]: = DC [i] - fronta [i] .head (). Size () send (fronta [i] .head ()) fronta [i] .dequeue () skončit chvíli -li fronta [i] .empty () pak DC [i]: = 0 skončit, pokud skončit, pokud konec proskončit chvíli
Výkony: spravedlnost, složitost
Stejně jako ostatní plánovací algoritmy podobné GPS je volba vah ponechána na správci sítě.
Stejně jako WFQ nabízí DRR minimální rychlost pro každý tok bez ohledu na velikost paketů. Při plánování váženého opakování závisí zlomek použité šířky pásma na velikostech paketu.
Ve srovnání s plánovačem WFQ, který má složitost O (log (n)) (n je počet aktivních toky / fronty ), složitost DRR je O (1), pokud kvantové je větší než maximální velikost paketu tohoto toku. Tato účinnost má nicméně své náklady: latence, tj. vzdálenost k ideálnímu GPS je větší v DRR než v WFQ. [2]
Implementace
Implementaci algoritmu schodku každý s každým napsal Patrick McHardy pro Linuxové jádro[3] a zveřejněna pod GNU General Public License.
Ve směrovačích Cisco a Juniper jsou implementovány upravené verze DRR: protože latence DRR může být pro určitou třídu provozu větší, tyto upravené verze dávají vyšší prioritu některým frontám, zatímco ostatní jsou obsluhovány standardním algoritmem DRR.[4][5]
Viz také
- Algoritmus plánování
- Fair Queuing
- Zobecněné sdílení procesoru
- Vážený veletrh
- Vážený každý s každým
- Míra spravedlnosti
Poznámky
- ^ Toky lze také nazývat fronty, třídy nebo relace
Reference
- ^ Shreedhar, M .; Varghese, G. (Říjen 1995). „Efektivní spravedlivé řazení do fronty s využitím každého kola deficitu“. Recenze počítačové komunikace ACM SIGCOMM. 25 (4): 231. doi:10.1145/217391.217453. ISSN 0146-4833.
- ^ Lenzini, L .; Mingozzi, E .; Stea, G. (2002). „Aliquem: Nová implementace DRR k dosažení lepší latence a spravedlnosti při složitosti O (1)“. IEEE 2002 Desátý mezinárodní seminář IEEE o kvalitě služeb (kat. Č. 02EX564). str. 77. doi:10.1109 / IWQoS.2002.1006576. ISBN 978-0-7803-7426-3.
- ^ „DRR Linux kernel network scheduler module“. kernel.org. Citováno 2013-09-07.
- ^ Lenzini, Luciano; Mingozzi, Enzo; Stea, Giovanni (2007). „Analýza výkonu modifikovaných plánovačů Round Robin Schedulers“. IOS Journal of High Speed Networks.
- ^ Lenzini, Luciano; Mingozzi, Enzo; Stea, Giovanni (2006). Analýza výkonu modifikovaných plánovačů Round Robin Schedulers (Technická zpráva). Dipartimento di Ingegneria della Informazione, Univerzita v Pise.