Организация очередей в маршрутизаторе

Маршрутизаторы используют различные входные очереди, чтобы предоставить качество обслуживания для IP-потоков. Использование очередей в маршрутизаторах (и в других устройствах, расположенных на границах локальных и глобальных сетей) позволяет (частично) решить проблемы, возникающие при взрывном росте объема IP-трафика, если непрерывное управление потоком данных невозможно. После того как данные поступают на маршрутизатор, они помещаются в одну из множества очередей. В какую именно, зависит от алгоритма, реализованного на маршрутизаторе. Так или иначе маршрутизатор должен определить выходной порт, куда следует переслать данные. В зависимости от применяемого алгоритма организации очереди (выбираемого при конфигурации маршрутизатора) для этих данных определяется та или иная очередь для передачи.

Самый простой алгоритм организации очереди, используемый маршрутизаторами, – это очередь FIFO. Будучи самой простой для реализации, она создает, тем не менее, серьезные проблемы. При организации очереди в порядке поступления для каждого порта используется только одна выходная очередь, поэтому все потоки трафика оказываются смешаны.

В этой связи возникают две главные проблемы: первоочередной интерактивный трафик может быть легко блокирован объемной передачей данных, а переполнение очереди может вызвать потерю пакетов во всем трафике, а не только в том, который переполнил очередь. Типичным является такой пример – из-за того, что трафик транзакций замедлен происходящей одновременно передачей файла по протоколу FTP, возможен разрыв сеанса связи, что приведет к неработоспособности приложения, отвечающего за транзакции. Это наиболее очевидный недостаток очереди FIFO.

Но и вторая проблема может вызвать не меньше трудностей. Когда происходит переполнение очереди, могут потеряться пакеты от всех смешанных потоков трафика (происходит так называемый «отброс хвоста»). Это заставляет все проходящие потоки протокола TCP (напомним, что так как сегмент TCP инкапсулируется в дейтаграмму IP, можно говорить о потоках TCP) производить повторную передачу, что будет сопровождаться последующими всплесками трафика. В этих условиях алгоритмы протокола TCP «Медленный старт» и «Предотвращение перегрузки» могут не помочь. Такие короткие синхронизированные волны трафика усугубляют переполнение на маршрутизаторах.

Попытки предотвратить переполнение очереди за счет увеличения размера самой очереди вызывают другие проблемы. Большая разница между задержкой при пустой очереди и задержкой при полной очереди увеличивает флуктуации в сети. Повышенная флуктуация требует наличия большего буфера для своего «гашения» на принимающей стороне. По этой причине при использовании больших промежуточных очередей почти невозможно выполнить требования трафика реального времени.

Очередь с приоритетами была разработана для того, чтобы решить первую главную проблему очередей FIFO; она обслуживает отдельные выходные очереди для различных классов трафика на одном и том же выходном порте. Очереди с приоритетами требуют, чтобы первоочередные потоки трафика были специально обозначены, например, с использованием поля «Тип сервиса» в заголовке дейтаграммы IPv4. Кроме того, сетевой администратор может назначить высокий приоритет для трафика, идущего по определенным сетевым адресам или к портам. Пакет из обычной очереди не может быть передан, если есть непустые более приоритетные очереди. Недостаток приоритетной организации очереди состоит в том, что менее приоритетные очереди могут «жаждать» пропускной способности как раз в тот момент, когда сеть перегружена. Тем самым они могут сделать ситуацию с перегрузкой еще тяжелее, пытаясь инициализировать повторные передачи для своих низкоприоритетных потоков трафика.

Очевидное усовершенствование этого метода состоит в том, чтобы всем очередям выделить надлежащую долю полосы пропускания. Такой метод называется справедливой организацией очереди (Fair Queuing, FQ). Справедливая очередь гарантирует, например, что трафик транзакций может проходить через маршрутизаторы своевременно, причем, без полной блокировки канала связи для других пользователей.

Взвешенная справедливая организация очереди (Weighted Fair Queuing, WFQ) является усовершенствованием очереди FQ. Она разбивает потоки на группы и назначает приоритет каждой группе потоков в зависимости от того, какую часть полосы пропускания те используют. Группы потоков со скромными требованиями к ширине полосы пропускания получают более высокий приоритет. При этом время ответа для таких потоков (вероятно, это или интерактивный трафик, или трафик реального времени) значительно улучшается. Кроме того, потокам внутри каждой группы также назначаются приоритеты. Механизм WFQ достаточно эффективен, поэтому во многих случаях использование различных индикаторов приоритета (например, полей «Тип сервиса» в протоколе IP или сетевых адресов или портов) необязательно. Как следствие, от администратора требуется меньше усилий по настройке приоритетов вручную.

Ни один из рассмотренных выше методов не предотвращает полностью буферного переполнения и не решает проблемы «отброса хвоста», которая приводит к частым волнам трафика и усугубляет переполнение. Алгоритм случайного раннего обнаружения (Random Early Detection, RED) снимает вышеназванную проблему. Он контролирует размер выходной очереди и отбрасывает пакет в некоторых потоках трафика до того, как произойдет переполнение очереди. При такой «потере» пакетов срабатывает механизм определения перегрузки протокола TCP, и скорость потока временно уменьшается. Таким образом в жертву приносятся только несколько потоков, которые вынуждены производить повторную передачу и включать алгоритм «Медленный старт». Тем самым удается избежать возникновения глобальных волн синхронизации, когда множество потоков начинают одновременную ретрансляцию, вызванную потерей пакетов при переполнении буфера. Ясно, что работа алгоритма RED зависит от алгоритмов протокола TCP «Медленный старт» и «Предотвращение перегрузки». Использование очередей, к которым вынуждены прибегать маршрутизаторы и граничные устройства, не имеющие возможности непосредственно управлять непрерывными потоками трафика, в свою очередь, порождает некоторые проблемы, которые были разрешены только частично. Есть проблемы, которые не могут быть разрешены любыми методами организации очереди, включая WFQ и другие недавние разработки.

Обработка любой очереди производится каждым сетевым устройством в изоляции от других устройств, и нет никакого метода (отличного от сообщения «Подавление источника» (Source Quench) протокола ICMP) передачи информации между промежуточными сетевыми устройствами, чтобы они могли совместно воздействовать на скорость передачи. Поэтому все, что могут сделать очереди, – это буферизовать пакеты (с неизбежной задержкой), а промежуточным устройствам, не имеющим буферов, остается только вносить ошибки в передачу, надеясь, что это вызовет замедление трафика.

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

Поэтому очереди – это только частичное решение вопроса предоставления QpS в IP-сетях. Кроме того, организацией очередей управлять достаточно сложно, особенно в том случае, если внутри сети существуют участки, находящиеся вне досягаемости прямого управления.