Алгоритмы распределения ресурсов маршрутизатора между пакетами потока и конкурирующими потоками называются алгоритмами диспетчеризации пакетов (packet scheduling algorithm). Резервироваться могут три типа ресурсов:
1. Пропускная способность.
2. Буферное пространство.
3. Время центрального процессора.
Наиболее очевидно резервирование пропускной способности. Если потоку необходима скорость в 1 Мбит/с, а исходящая линия может работать со скоростью 2 Мбит/с, то направить три потока с такими параметрами по этой линии не удастся. То есть резервирование пропускной способности означает предотвращение предоставления канала большему числу абонентов, чем канал может обработать.
Вторым дефицитным ресурсом является буферное пространство. Когда прибывает пакет, он хранится в буфере маршрутизатора до тех пор, пока он не будет передан по выбранной исходящей линии. Буфер нужен для того, чтобы хранить небольшие пачки трафика, пока потоки сражаются друг с другом. Если буферное пространство недоступно, входящий пакет приходится игнорировать, поскольку его просто негде сохранить. Для обеспечения хорошего качества обслуживания можно резервировать некоторую часть буферной памяти под конкретный поток, чтобы ему не пришлось бороться за буфер с другими потоками. И тогда при передаче потока ему всегда будет предоставляться выделенная часть буфера, вплоть до некоторого максимума.
Наконец, время центрального процесса также может быть очень ценным ресурсом. На что расходуется время работы процессора в маршрутизаторе? На обработку пакетов. Поэтому существует предельная скорость, с которой маршрутизатор может обрабатывать пакеты. Хотя большинство пакетов современные маршрутизаторы могут обрабатывать очень быстро, определенные типы пакетов (в частности, ICMP, о которых мы поговорим в разделе 5.6) все же требуют более длительной работы центрального процессора. Необходимо быть уверенным в том, что процессор не перегружен, — это залог своевременной обработки каждого пакета.
Алгоритмы диспетчеризации пакетов распределяют пропускную способность и другие ресурсы маршрутизатора, определяя, какие пакеты из буфера необходимо отправить по исходящей линии следующими. Простейший вариант диспетчера мы уже обсуждали, когда говорили о принципе работы маршрутизатора. Каждый маршрутизатор помещает пакеты в очередь (отдельную для каждой исходящей линии), где пакеты ждут отправки. При этом отправка пакетов происходит в том же порядке, в котором они пришли. Этот принцип называется FIFO (First-In First-Out, первым пришел — первым ушел), или FCFS (First-Come First-Serve, первым пришел — первым обслуживается).
Маршрутизаторы, работающие по принципу FIFO, при переполнении очереди обычно удаляют последние прибывшие пакеты. Поскольку только что прибывшие пакеты помещаются в конец очереди, такое поведение называется «обрубанием хвоста» (tail drop). Это настолько простой и привычный вариант, что альтернативный метод не так-то просто себе представить. Тем не менее алгоритм случайного раннего обнаружения (RED), о котором мы говорили в разделе 5.3.5, удалял новые пакеты случайным образом, когда длина очередь начинала расти. Другие алгоритмы диспетчеризации, о которых мы здесь поговорим, используют для выбора удаляемых пакетов самые разные возможности.
Диспетчеризацию по принципу FIFO очень легко реализовать, однако она не позволяет обеспечить высокое качество обслуживания: если потоков несколько, один из них может влиять на производительность других. Если первый поток будет вести себя агрессивно и отправлять большие объемы трафика, его пакеты будут помещаться в очередь. Если пакеты обрабатываются в порядке поступления, агрессивный отправитель захватит большую часть мощности маршрутизаторов, отбирая ее у других потоков и тем самым уменьшая их качество обслуживания. Ситуация усугубится тем, что пакеты других потоков, прошедшие через маршрутизатор, скорее всего, придут с опозданием, поскольку им пришлось задержаться в очереди, ожидая отправки пакетов агрессивного потока.
Чтобы обеспечить изоляцию потоков и предотвратить их конфликты, было разработано множество различных алгоритмов диспетчеризации пакетов (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, то формула вычисления времени окончания передачи будет выглядеть так:
