Наконец, время CPU также может быть очень ценным ресурсом. Маршрутизатор тратит его на обработку пакета, а значит, скорость этого процесса ограниченна. Современные маршрутизаторы в основном быстро справляются с этой задачей, но некоторые типы пакетов (в частности, ICMP, о которых мы поговорим в разделе 5.7.4) все же требуют более длительной работы CPU. Уверенность в том, что процессор не перегружен, — залог своевременной обработки пакетов.

Планирование пакетов по принципу 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 еще не началась. При использовании равноправных очередей передача пакета не прерывается. Алгоритм передает пакеты целиком и потому является лишь приближением идеальной схемы побайтовой передачи. Но это достаточно хорошее приближение: в каждый момент времени передается ровно один пакет.