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

Вторым дефицитным ресурсом является буферное пространство. Когда прибывает пакет, он хранится в буфере маршрутизатора до тех пор, пока он не будет передан по выбранной исходящей линии. Буфер нужен для того, чтобы хранить небольшие пачки трафика, пока потоки сражаются друг с другом. Если буферное пространство недоступно, входящий пакет приходится игнорировать, поскольку его просто негде сохранить. Для обеспечения хорошего качества обслуживания можно резервировать некоторую часть буферной памяти под конкретный поток, чтобы ему не пришлось бороться за буфер с другими потоками. И тогда при передаче потока ему всегда будет предоставляться выделенная часть буфера, вплоть до некоторого максимума.

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