Эндрю Уэзеролл - Компьютерные сети. 5-е издание

Чтобы обеспечить изоляцию потоков и предотвратить их конфликты, было разработано множество различных алгоритмов диспетчеризации пакетов (Bhatti

и Crowcroft, 2000). Одним из первых был алгоритм справедливого обслуживания( fair queueing) (Nagle, 1987). Суть его состоит в том, что маршрутизаторы организуют отдельные очереди для каждой исходящей линии, по одной для каждого потока. Как только линия освобождается, маршрутизатор начинает циклически сканировать очереди (рис. 5.27), выбирая первый пакет следующей очереди. Таким образом, если за данную исходящую линию борются n хостов, то каждый из них имеет возможность отправить свой пакет, пропустив n—1 чужих пакетов. Получается, что все потоки передают пакеты с одинаковой скоростью. Агрессивному хосту не поможет то, что в его очереди стоит больше пакетов, чем у остальных.

Рис. 5.27. Циклическое справедливое обслуживание

Однако и с этим алгоритмом связана одна проблема: предоставляемая им пропускная способность напрямую зависит от размера пакета используемого хостом: большая часть предоставляется хостам с большими пакетами и меньшая — хостам с небольшими пакетами. В книге (Demers и др., 1990) предлагается улучшенная версия, в которой циклический опрос производится с целью выхватывания не пакета, а байта. Идея заключается в вычислении виртуального времени, то есть номера цикла, после которого отправка пакета завершится. Каждый цикл выхватывает один байт из каждой очереди, содержащей пакеты для отправки. После этого пакеты отправляются в том порядке, в котором они заканчивались при опросе очередей.

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

Рис. 5.28. Работа алгоритма: а — взвешенное справедливое обслуживание; б — время окончания отправки для пакетов

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

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

где — время прибытия, — время окончания отправки, а — длина пакета. Нижняя очередь (рис. 5.28, а) имеет вес 2, поэтому ее пакеты передаются быстрее. Это хорошо видно, если посмотреть на значения времени окончания отправки (см. рис. 5.28, б ). Еще один фактор, который необходимо учитывать, — это сложность реализации. Метод взвешенного справедливого обслуживания помещает пакеты в очередь, сортируя их по времени окончания отправки. Для N потоков это требует по меньшей мере операций для каждого пакета, что является трудновыпол

нимым при большом количестве потоков на высокоскоростных маршрутизаторах. Существует упрощенная схема DRR (deficit round robin), работающая гораздо эффективнее — всего за 0(1) операций для каждого пакета (Shreedhar и Varghese, 1995). Она широко применяется для алгоритма взвешенного справедливого обслуживания.

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

Фактически бинарная приоритетная система представляет собой две очереди, одна из которых имеет бесконечный вес.

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