Желілік кестеге арналған тапсыру алгоритмі: Deficit Round Robin
Deficit round robin
Желілік жоспарлаушы үшін Deficit Round Robin (DRR) алгоритмі. Ол пакеттік жүктемеде әділдік пен тиімділікті қамтамасыз етеді (O(1) күрделілік). DRR, WFQ сияқты, GPS саясатын іске асырады.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Желілік жоспарлаушы үшін жоспарлау алгоритмі
Scheduling algorithm for the network scheduler
Дефицит Round Robin (DRR), сондай-ақ Дефицит салмақталған дөңгелек Робин (DWRR) – желілік жоспарлаушы үшін қолданылатын жоспарлау алгоритмі. DRR, салмақталған әділ кезекке тұру (WFQ) сияқты, идеалды Жалпы процессорды бөлісу (GPS) саясатының пакеттік іске асырылуы болып табылады. Ол 1995 жылы М. Шредхар және Г. Варгезе еңбектерінде тиімді (O(1) күрделілігімен) және әділ алгоритм ретінде ұсынылған.
Deficit Round Robin (DRR), also Deficit Weighted Round Robin (DWRR), is a scheduling algorithm for the network scheduler. DRR is, like weighted fair queuing (WFQ), a packet based implementation of the ideal Generalized Processor Sharing (GPS) policy. It was proposed by M. Shreedhar and G. Varghese in 1995 as an efficient (with O(1) complexity) and fair algorithm.
Егжей-тегжейлер
DRR-де N ағынды басқаратын жоспарлаушы әр ағын үшін бір квантпен конфигурацияланады. Басты идея – әрбір раундта ағын ең көп байт жібере алады, ал қалған бөлігі, болған жағдайда, келесі раундқа ауыстырылады. Осылайша, ұзақ мерзімде ағынның ең төменгі жылдамдығы ; мұнда – байланыс жылдамдығы.
In DRR, a scheduler handling N flows is configured with one quantum for each flow. This global idea is that, at each round, the flow can send at most bytes, and the remaining, if any, is reported to the next round. In this way, the minimum rate that flow will achieve over a long term is ; where is the link rate.
Орындау: әділдік, күрделілік және кідіріс
Басқа GPS сияқты кестелеу алгоритмі сияқты, салмақтарды таңдау желі әкімшісіне жүктеледі. WFQ сияқты, DRR пакеттердің мөлшеріне қарамастан, әрбір ағымға ең төменгі жылдамдық мөлшерін ұсынады. Салмақты дөңгелек тізбегімен кестелеуде, пайдаланылған өткізу қабілетінің үлесі пакеттердің мөлшеріне байланысты. WFQ кестелеушісінің күрделілігі O(log(n)) (n – белсенді ағындар/кезектер саны) болса, DRR-дің күрделілігі O(1) болады, егер квант осы ағынның ең үлкен пакет мөлшерінен артық болса. Дегенмен, бұл тиімділіктің құны бар: DRR-дегі кідіріс, яғни идеалды GPS-ке дейінгі арақашықтық, WFQ-ге қарағанда үлкен. Ең нашар жағдайдағы кідіріс туралы толық ақпаратты мына жерден табуға болады.
Like other GPS like scheduling algorithm, the choice of the weights is left to the network administrator. Like WFQ, DRR offers a minimal rate to each flow whatever the size of the packets is. In weighted round robin scheduling, the fraction of bandwidth used depend on the packet's sizes. Compared with WFQ scheduler that has complexity of O(log(n)) (n is the number of active flows/queues), the complexity of DRR is O(1), if the quantum is larger than the maximum packet size of this flow. Nevertheless, this efficiency has a cost: the latency, i. e., the distance to the ideal GPS, is larger in DRR than in WFQ. More on the worst case latencies can be found here.
Қолданылу
Дефициттік дөңгелек робин алгоритмінің іске асырылуын Патрик МакХарди Linux ядросы үшін жазды және оны GNU General Public License лицензиясы бойынша жариялады. Cisco және Juniper маршрутизаторларында DRR-дің өзгертілген нұсқалары қолданылады: DRR-дің кейбір трафик түрлері үшін жауап уақыты ұзақ болуы мүмкін болғандықтан, бұл өзгертілген нұсқалар кейбір кезектерге жоғары басымдық қойып, қалғандарын стандартты DRR алгоритмімен қамтамасыз етеді.
An implementation of the deficit round robin algorithm was written by Patrick McHardy for the Linux kernel and published under the GNU General Public License. In Cisco and Juniper routers, modified versions of DRR are implemented: since the latency of DRR can be larger for some class of traffic, these modified versions give higher priority to some queues, whereas the others are served with the standard DRR algorithm.