Планирование пакетов по принципу FIFO
Алгоритмы планирования пакетов распределяют пропускную способность и другие ресурсы маршрутизатора, решая, какой пакет из буфера отправить по исходящей линии следующим. Простейший вариант планировщика мы уже обсуждали, когда говорили о принципе работы маршрутизатора. Каждый маршрутизатор помещает пакеты в очередь (отдельную для каждой исходящей линии), где они ждут отправки. Дальнейшая передача пакетов происходит в том же порядке, в каком они пришли. Этот принцип называется FIFO (First-In First-Out, первым пришел — первым ушел) или FCFS (First-Come First-Serve, первым пришел — первым обслуживается).
Маршрутизаторы, работающие по принципу FIFO, при переполнении очереди обычно удаляют пакеты, которые пришли последними. Новые пакеты помещаются в конец очереди, поэтому такой принцип работы называется «обрубанием хвоста» (tail drop). Трудно представить альтернативу настолько простому и привычному методу. Однако алгоритм RED (см. раздел 5.3.2) при росте очереди отбрасывает прибывающие пакеты случайным образом. Другие алгоритмы планирования, которые мы обсудим, применяют самые разные принципы выбора пакетов для удаления.
Справедливое обслуживание
Планирование по принципу FIFO легко реализовать, но оно не обеспечивает высокий уровень QoS: если потоков несколько, один из них может влиять на производительность других. Если поток ведет себя агрессивно и отправляет большие объемы трафика, его пакеты попадают в очередь. При обработке в порядке поступления этот отправитель захватывает большую часть мощности маршрутизаторов, отбирая ее у других потоков и тем самым уменьшая их уровень QoS. Ситуация усугубляется тем, что пакеты других потоков, прошедшие через маршрутизатор, скорее всего, придут с опозданием, поскольку они задержались в очереди, ожидая отправки пакетов агрессивного потока.
Чтобы обеспечить изоляцию потоков и предотвратить их конфликты, было разработано множество различных алгоритмов планирования пакетов (Бхатти и Кроукрофт; Bhatti and Crowcroft, 2000). Одним из первых был алгоритм равноправных очередей (fair queueing) (Нейгл; Nagle, 1987). Маршрутизаторы организуют отдельные очереди для каждой исходящей линии, по одной для каждого потока. Как только линия освобождается, маршрутизатор циклически сканирует очереди (илл. 5.28) и выбирает первый пакет следующей очереди. Таким образом, если за данную исходящую линию конкурируют n хостов, то каждый из них отправляет один пакет из каждых n пакетов. Получается, что все потоки передают пакеты с одинаковой скоростью и агрессивному хосту не поможет отправка большего числа пакетов.
Илл. 5.28. Циклическая обработка равноправных очередей
Однако у этого метода есть один недостаток. Предоставляемая им пропускная способность напрямую зависит от размера пакетов, отправляемых хостом: чем они крупнее, тем больше ресурса ему выделяется. В книге Демерса и др. (Demers et al., 1990) предлагается улучшенная версия алгоритма, в которой циклический опрос производится с целью выхватывания байта, а не пакета. Идея заключается в вычислении виртуального времени, то есть номера цикла, на котором отправка пакета завершится. Каждый цикл выхватывает один байт из всех очередей, содержащих пакеты для передачи. Затем пакеты сортируются согласно времени завершения отправки и передаются в этой последовательности.
На илл. 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), временной штамп регистрирует информацию о том, насколько пакет, проходя через маршрутизаторы сети, отстает от графика или опережает его. Как правило, пакеты, ожидающие отправки, отстают, а передаваемые в первую очередь — опережают график. Использование временных штампов — эффективный способ ускорить отправку медленных пакетов и замедлить передачу быстрых. При таком подходе все пакеты доставляются с приблизительно равной задержкой, что является очевидным преимуществом.
Собираем все воедино
Теперь, когда мы познакомились с основными компонентами QoS, самое время объединить их, чтобы реально его обеспечить. Гарантии QoS предоставляются через управление допуском. Мы рассматривали его как средство борьбы с перегрузкой, что является гарантией производительности, пусть даже не очень эффективной. Здесь мы предъявляем к гарантиям более серьезные требования, но модель остается той же. Пользователь передает в сеть поток, предъявляя определенные требования QoS. Сеть принимает или отвергает этот поток в зависимости от своих возможностей и обязательств перед другими клиентами. Если поток принимается, сеть должна заранее зарезервировать ресурсы, чтобы при передаче по нему трафика клиент получил необходимый уровень QoS.
Необходимо зарезервировать ресурсы на всех маршрутизаторах, расположенных в узлах пути, по которому следуют пакеты. Иначе может возникнуть коллапс, и гарантии QoS не будут выполнены. Многие алгоритмы маршрутизации выбирают наилучший путь от отправителя до получателя и направляют по нему весь трафик. Однако некоторые потоки могут быть отвергнуты из-за недостатка ресурсов в узлах наилучшего маршрута. Тогда, чтобы выполнить свои обязательства, сеть выберет другой путь для отправки крупного потока. Этот подход называется QoS-маршрутизацией (QoS routing); см. работу Чэня и Нарштедт (Chen and Nahrstedt, 1998). Также можно разделить трафик для одного адресата по нескольким маршрутам, чтобы было проще найти дополнительные ресурсы. Маршрутизаторы могут выбирать пути с одинаковой стоимостью и использовать маршрутизацию, пропорциональную или эквивалентную емкостям исходящих связей. Однако существуют и более сложные алгоритмы (Нелакудити и Чжан; Nelakuditi и Zhang, 2002).
С учетом выбранного пути решение о принятии или отклонении потока не сводится к сравнению запрашиваемых ресурсов (пропускной способности, буферной памяти, времени CPU) с возможностями маршрутизатора. Во-первых, несмотря на то что многие приложения знают свои требования по пропускной способности, два других параметра им неизвестны. Следовательно, как минимум необходим иной способ описания потоков и определения ресурсов, выделяемых маршрутизатором. Вскоре мы это обсудим.
Также отметим, что приложения значительно различаются по толерантности в отношении пропущенного предельного срока обработки. Поэтому приложение должно выбрать один из типов гарантий, предлагаемых сетью: от строгих до максимально лояльных. При прочих равных условиях наиболее популярными были бы строгие гарантии. Но проблема в том, что они затратные, так как ограничивают поведение сети в наихудшем случае. Для приложения обычно достаточно тех же гарантий, что и для большинства пакетов; кроме того, они позволяют добавить дополнительный поток при фиксированной емкости.