Компьютерные сети. 6-е изд.

На илл. 5.29 показана работа алгоритма и примеры значений времени окончания отправки пакетов для трех потоков. Если длина пакета равна L, его отправка завершится через L циклов. Передача пакета начинается либо сразу после отправки предыдущего, либо в момент прибытия этого пакета, если очередь пуста.

Таблица на илл. 5.29 (б) показывает, что первые два пакета в двух верхних очередях прибывают в порядке A, B, D, F. Пакет A приходит на нулевом цикле, а его длина равна 8 байт, поэтому отправка завершается на 8-м цикле. Точно так же отправка пакета B завершается на цикле 11. Пакет D прибывает в момент отправки B. Его передача заканчивается через 9 циклов после окончания

Илл. 5.29. (а) WFQ. (б) Время окончания отправки для пакетов

отправки B; время равно 20. Аналогичным образом время завершения отправки F равно 16. Если новых пакетов нет, порядок окончания отправки пакетов будет таким: A, B, F, D (хотя F прибывает после D). Может случиться так, что в верхний поток поступит небольшой пакет, который будет передан раньше D. Но он обойдет D только в том случае, если отправка D еще не началась. При использовании равноправных очередей передача пакета не прерывается. Алгоритм передает пакеты целиком и потому является лишь приближением идеальной схемы побайтовой передачи. Но это достаточно хорошее приближение: в каждый момент времени передается ровно один пакет.

Взвешенные равноправные очереди

Проблема данного алгоритма в том, что он дает всем хостам одинаковые приоритеты. Как правило, видеосерверам лучше предоставлять большую пропускную способность, чем обычным файл-серверам, чтобы они могли передавать два или несколько байтов за цикл. Такая модификация алгоритма называется взвешенными равноправными очередями (Weighted Fair Queueing, WFQ). Если количество байтов, передаваемое за цикл, считать весом потока W, то формула времени окончания передачи выглядит так:

Fi = max( Ai, Fi–1) + Li/W,

где Ai — время прибытия, Fi — время окончания отправки, а Li — длина i-го пакета. Нижняя очередь (илл. 5.29 (а)) имеет вес 2, поэтому ее пакеты передаются быстрее. Это хорошо видно, если посмотреть на значения времени окончания отправки на илл. 5.29 (б).

Еще один важный фактор — сложность реализации. WFQ помещает пакеты в очередь, сортируя их по времени окончания отправки. Для N потоков это требует по меньшей мере O(log N) операций для каждого пакета, а это трудновыполнимо при большом количестве потоков на высокоскоростных маршрутизаторах. Упрощенная схема дефицитного циклического обслуживания (Deficit Round Robin, DRR) работает гораздо эффективнее: всего за O(1) операций для каждого пакета (Шридхар и Варгезе; Shreedhar and Varghese, 1995). Она широко применяется для алгоритма WFQ.

Существуют другие алгоритмы планирования пакетов, например приоритетный, при котором пакеты обладают каким-либо приоритетом. Высокоприоритетные пакеты передаются раньше, чем низкоприоритетные; последние помещаются в буфер. Пакеты с одинаковым приоритетом отправляются по принципу FIFO. Важным недостатком этого алгоритма является то, что высокоприоритетные пакеты препятствуют отправке низкоприоритетных, которые могут ждать своей очереди бесконечно долго. С этой точки зрения более удачным вариантом является WFQ. Если присвоить высокоприоритетной очереди большой вес (скажем, 3), пакеты в ней будут в основном проходить по быстрой линии (поскольку их сравнительно немного). При этом часть низкоприоритетных пакетов тоже будет передаваться. Фактически бинарная приоритетная система представляет собой две очереди, одна из которых имеет бесконечный вес.

Наконец, существует алгоритм планирования, при котором у каждого пакета есть временной штамп, определяющий порядок отправки. В реализации, которую предложили Кларк и др. (Clark et al., 1992), временной штамп регистрирует информацию о том, насколько пакет, проходя через маршрутизаторы сети, отстает от графика или опережает его. Как правило, пакеты, ожидающие отправки, отстают, а передаваемые в первую очередь — опережают график. Использование временных штампов — эффективный способ ускорить отправку медленных пакетов и замедлить передачу быстрых. При таком подходе все пакеты доставляются с приблизительно равной задержкой, что является очевидным преимуществом.

Собираем все воедино