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

Наиболее очевидным является резервирование пропускной способности. Если потоку необходима скорость в 1 Мбит/с, а исходящая линия может работать со скоростью 2 Мбит/с, то направить по ней три потока с такими параметрами не удастся. Таким образом, резервирование пропускной способности предотвращает предоставление канала слишком большему числу абонентов.

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

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