Введение
Алгоритм планирования задач или потоков данных. Взвешенный круглый робин (WRR) — это сетевой планировщик потоков данных, который также используется для планирования процессов. Взвешенный круглый робин является обобщением алгоритма круглого робина. Он обслуживает набор очередей или задач. В то время как круглый робин последовательно перебирает очереди или задачи, предоставляя одну возможность обслуживания за цикл, взвешенный круглый робин предоставляет каждой очереди или задаче фиксированное количество возможностей, определяемое заданным весом, который влияет на долю ресурсов, выделяемых каждой очереди или задаче. В компьютерных сетях возможность обслуживания представляет собой отправку одного пакета, если выбранная очередь не пуста. Если все пакеты имеют одинаковый размер, WRR является простейшим приближением к обобщенному разделению ресурсов процессора (GPS). Существует несколько вариантов WRR, основными из которых являются классический WRR и переплетенный WRR.
Weighted round robin (WRR) is a network scheduler for data flows, but also used to schedule processes. Weighted round robin is a generalisation of round robin scheduling. It serves a set of queues or tasks. Whereas round robin cycles over the queues or tasks and gives one service opportunity per cycle, weighted round robin offers to each a fixed number of opportunities, as specified by the configured weight which serves to influence the portion of capacity received by each queue or task. In computer networks, a service opportunity is the emission of one packet, if the selected queue is non empty. If all packets have the same size, WRR is the simplest approximation of generalized processor sharing (GPS). Several variations of WRR exist. The main ones are the classical WRR, and the interleaved WRR.
Принципы
WRR в дальнейшем рассматривается как сетевой планировщик. Его также можно использовать для планирования задач аналогичным образом. Взвешенный сетевой планировщик типа "round robin" имеет входные очереди. Каждой очереди сопоставлен положительный целый вес. Планировщик WRR имеет циклическое поведение. В каждом цикле каждая очередь получает возможности для передачи. Различные алгоритмы WRR различаются способом распределения этих возможностей в цикле.
Пример
Рассмотрим систему с тремя очередями и соответствующими весами. Рассмотрим ситуацию, когда в первой очереди 7 пакетов, А, В, С, D, Е, F, G, в второй очереди 3 пакета, U, V, W, и в третьей очереди 2 пакета, X, Y. Предположим, что новых пакетов больше не поступает. При классическом WRR в первом цикле планировщик сначала выбирает и передает пять пакетов из начала первой очереди, A, B, C, D, E, затем выбирает вторую очередь и передает два пакета из начала очереди, U, V, и, наконец, выбирает третью очередь, которая имеет вес, равный 3, но содержит только два пакета, поэтому передает X, Y. Сразу после окончания передачи Y начинается второй цикл, и передаются F, G из первой очереди, за которыми следует W из второй очереди.
With interleaved WRR, the first cycle is split into 5 rounds (since ). In the first one (r=1), one packet from each queue is sent (A,U,X), in the second round (r=2), another packet from each queue is also sent (B,V,Y), in the third round (r=3), only queues are allowed to send a packet (, and ), but since is empty, only C from is sent, and in the fourth and fifth rounds, only D,E from are sent. Then starts the second cycle, where F,W,G are sent.
При interleaved WRR первый цикл разделен на 5 раундов. В первом раунде (r=1) отправляется по одному пакету из каждой очереди (A, U, X), во втором раунде (r=2) отправляется еще по одному пакету из каждой очереди (B, V, Y), в третьем раунде (r=3) только первой и второй очередям разрешено отправлять пакеты, но поскольку вторая очередь пуста, отправляется только C из первой очереди, а в четвертом и пятом раундах отправляются только D, E из первой очереди. Затем начинается второй цикл, в котором отправляются F, W, G.
With interleaved WRR, the first cycle is split into 5 rounds (since ). In the first one (r=1), one packet from each queue is sent (A,U,X), in the second round (r=2), another packet from each queue is also sent (B,V,Y), in the third round (r=3), only queues are allowed to send a packet (, and ), but since is empty, only C from is sent, and in the fourth and fifth rounds, only D,E from are sent. Then starts the second cycle, where F,W,G are sent.
Свойства
Как и в случае с методом "каждый с каждым", планирование с взвешенным методом "каждый с каждым" простое, легко реализуемое, эффективно использует ресурсы и исключает "голодание". При планировании пакетов, если все пакеты имеют одинаковый размер, то WRR и IWRR являются приближением к обобщенному разделению ресурсов процессора: очередь будет получать долгосрочную долю полосы пропускания, равную (если все очереди активны), в то время как GPS обслуживает бесконечно малые объемы данных из каждой непустой очереди и предоставляет эту долю на любом интервале времени. Если очереди содержат пакеты переменной длины, доля полосы пропускания, получаемая каждой очередью, зависит не только от весов, но и от размеров пакетов. Если известен средний размер пакетов для каждой очереди, то каждая очередь получит долгосрочную долю полосы пропускания, равную. Если целью является предоставление каждой очереди определенной доли пропускной способности канала (где ), можно установить. Поскольку IWRR имеет меньшие всплески трафика на класс, чем WRR, это подразумевает меньшие максимальные задержки.
Since IWRR has smaller per class bursts than WRR, it implies smaller worst case delays.
Ограничения и улучшения
WRR для планирования сетевых пакетов был впервые предложен Кетевенисом, Сидиропулосом и Куркубетисом в 1991 году, специально для планирования в сетях ATM, использующих пакеты фиксированного размера (ячейки). Основное ограничение взвешенного циклического обслуживания заключается в том, что оно обеспечивает корректную долю полосы пропускания для каждого класса обслуживания только в том случае, если все пакеты во всех очередях имеют одинаковый размер или когда средний размер пакета известен заранее. В более общем случае IP-сетей с пакетами переменного размера, для приближения к GPS весовые коэффициенты необходимо корректировать в зависимости от размера пакета. Это требует оценки среднего размера пакета, что затрудняет достижение хорошего приближения к GPS на практике при использовании WRR. Дефицитный циклический алгоритм – более поздняя модификация WRR, которая обеспечивает лучшее приближение к GPS без предварительного знания среднего размера пакета для каждого соединения. Также были разработаны более эффективные алгоритмы планирования, которые решают вышеупомянутые ограничения (например, взвешенная справедливая очередь).