Желілік жүктемелерді жоспарлау алгоритмі: Токен шөкісі
Token bucket
Желілік жүктемелерді басқару үшін қолданылатын "токен шелек" алгоритмі туралы мақала. Өріс ені мен жүктемелерді тексеру, уақытты жоспарлау мүмкіндіктері.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Желілік берілістерді жоспарлау алгоритмі
Scheduling algorithm for network transmissions
Токендік бөшке – пакеттік коммутациялық және телекоммуникациялық желілерде қолданылатын алгоритм. Ол деректерді пакеттер түрінде берудің жолақтығы мен импульстілігінің (трафик ағынының тепе-теңдігі немесе өзгергіштігінің өлшемі) белгіленген шектеріне сәйкес келетінін тексеру үшін пайдаланылуы мүмкін. Сондай-ақ, ол жолақтығы мен импульстілігі үшін белгіленген шектерге сәйкес келетін берілімдердің уақытын анықтау үшін жоспарлау алгоритмі ретінде де қолданылуы мүмкін: желілік жоспарлаушыға қараңыз.
The token bucket is an algorithm used in packet switched and telecommunications networks. It can be used to check that data transmissions, in the form of packets, conform to defined limits on bandwidth and burstiness (a measure of the unevenness or variations in the traffic flow). It can also be used as a scheduling algorithm to determine the timing of transmissions that will comply with the limits set for the bandwidth and burstiness: see network scheduler.
Шолу
Токендік бөшке алгоритмі тұрақты сыйымдылыққа ие бөшке аналогиясына негізделген, оған әдетте байттар бірлігін немесе алдын ала белгіленген мөлшердегі бір пакетті білдіретін токендер белгіленген жылдамдықпен салынады. Пакеттің анықталған шектерге сәйкестігін тексеру қажет болғанда, бөшке сол уақытта жеткілікті токендер бар-жоғы тексеріледі. Егер жеткілікті болса, тиісті мөлшердегі токендер, мысалы, пакет ұзындығына тең байттар алынып ("жұмсалады") және пакет, мысалы, жіберу үшін жіберіледі. Егер бөшкеде жеткіліксіз токендер болса, пакет сәйкес келмейді және бөшкенің мазмұны өзгертілмейді. Сәйкес келмейтін пакеттерге әртүрлі жолдармен қарауға болады:
The token bucket algorithm is based on an analogy of a fixed capacity bucket into which tokens, normally representing a unit of bytes or a single packet of predetermined size, are added at a fixed rate. When a packet is to be checked for conformance to the defined limits, the bucket is inspected to see if it contains sufficient tokens at that time. If so, the appropriate number of tokens, e. g. equivalent to the length of the packet in bytes, are removed ("cashed in"), and the packet is passed, e. g., for transmission. The packet does not conform if there are insufficient tokens in the bucket, and the contents of the bucket are not changed. Non conformant packets can be treated in various ways:
Оларды тастап жіберуге болады. Жеткілікті токендер жиналғанда, оларды кейінірек жіберу үшін кезекке қоюға болады. Оларды жіберуге болады, бірақ сәйкес келмейтін деп белгіленеді, егер желі жүктемелі болса, кейіннен жойылуы мүмкін. Осылайша, сәйкес ағынның трафигі токендер бөшкеге қосылатын жылдамдыққа дейінгі орташа жылдамдыққа ие болуы мүмкін, ал бөшкенің тереңдігімен анықталатын импульстік сипаттамасы болуы мүмкін. Бұл импульстік сипаттаманы джиттерге төзімділік, яғни пакеттің орташа жылдамдық шегінен қаншалықты ертерек сәйкес келуі (мысалы, келу немесе берілуі) немесе импульстік төзімділік немесе максималды импульстік мөлшері, яғни қандай да бір уақыт аралығында трафиктің орташа деңгейінен қаншалықты көп сәйкес келуі арқылы көрсетуге болады.
They may be dropped. They may be enqueued for subsequent transmission when sufficient tokens have accumulated in the bucket. They may be transmitted, but marked as being non conformant, possibly to be dropped subsequently if the network is overloaded. A conforming flow can thus contain traffic with an average rate up to the rate at which tokens are added to the bucket, and have a burstiness determined by the depth of the bucket. This burstiness may be expressed in terms of either a jitter tolerance, i. e. how much sooner a packet might conform (e. g. arrive or be transmitted) than would be expected from the limit on the average rate, or a burst tolerance or maximum burst size, i. e. how much more than the average level of traffic might conform in some finite period.
Вариациялар
Бұл алгоритмді сағаттың жеткілікті ажыратымдылығы жоқ платформаларда іске асырушылар әр секунд сайын себетке бір белгі қосу үшін баламалы формуланы қарастыруы керек. Егер токендер қапшығын әр S миллисекунд сайын жаңарту мүмкіндігі болса, онда әр S миллисекунд сайын қосылатын токендер саны = .
Implementers of this algorithm on platforms lacking the clock resolution necessary to add a single token to the bucket every seconds may want to consider an alternative formulation. Given the ability to update the token bucket every S milliseconds, the number of tokens to add every S milliseconds = .
Орташа мөлшерлеме
Ұзақ мерзімде сәйкес пакеттердің шығысы токен жылдамдығымен шектеледі.
Over the long run the output of conformant packets is limited by the token rate, .
Қолданылуы
Токендік бөтелке трафикті қалыптастыруда немесе трафикті бақылауда қолданылуы мүмкін. Трафикті бақылауда сәйкес келмейтін пакеттер жойылуы (түсірілуі) мүмкін, немесе олардың басымдылығы төмендетілуі мүмкін (желіде тығын болған жағдайда, ағынмен басқару функциялары оларды жоюы мүмкін). Трафикті қалыптастыруда пакеттер сәйкес болатынша кешіктіріледі. Трафикті бақылау және трафикті қалыптастыру желіні артық немесе күрт өзгеретін трафиктен қорғау үшін кеңінен қолданылады, кеңдік бандын басқару және тығыннан сақтану қараңыз. Трафикті қалыптастыру көбінесе хосттардағы желілік интерфейстерде қолданылады, бұл желідегі трафикті басқару функциялары берілімдерді жоюын болдырмайды. Токендік бөтелке алгоритмі дерекқорының IO ағынын басқару үшін де қолданылады.
The token bucket can be used in either traffic shaping or traffic policing. In traffic policing, nonconforming packets may be discarded (dropped) or may be reduced in priority (for downstream traffic management functions to drop if there is congestion). In traffic shaping, packets are delayed until they conform. Traffic policing and traffic shaping are commonly used to protect the network against excess or excessively bursty traffic, see bandwidth management and congestion avoidance. Traffic shaping is commonly used in the network interfaces in hosts to prevent transmissions being discarded by traffic management functions in the network. The token bucket algorithm is also used in controlling database IO flow.