Почему в маршрутизаторах возникают очереди

Обновлено: 21.11.2024

Независимо от того, насколько прост или сложен остальной механизм распределения ресурсов, каждый маршрутизатор должен реализовать некоторую дисциплину организации очередей, которая определяет способ буферизации пакетов в ожидании передачи. Алгоритм постановки в очередь можно рассматривать как распределение полосы пропускания (какие пакеты передаются) и буферного пространства (какие пакеты отбрасываются). Это также напрямую влияет на задержку пакета, определяя, как долго пакет ожидает передачи. В этом разделе представлены два распространенных алгоритма организации очереди — «первым пришел — первым обслужен» (FIFO) и справедливая организация очереди (FQ) — и определены несколько предложенных вариантов.

6.2.1 FIFO¶

Идея организации очереди FIFO, также называемой организацией очереди по принципу "первым пришел - первым обслужен" (FCFS), проста: первый пакет, прибывший на маршрутизатор, должен быть передан первым. Это показано на рис. 156(а), где показан FIFO со «слотами» для хранения до восьми пакетов. Учитывая, что объем буферного пространства на каждом маршрутизаторе конечен, если приходит пакет и очередь (буферное пространство) заполнена, то маршрутизатор отбрасывает этот пакет, как показано на рис. 156(b). Это делается независимо от того, к какому потоку принадлежит пакет или насколько важен пакет. Это иногда называют отбрасыванием хвоста, поскольку пакеты, поступающие в конец FIFO, отбрасываются.

Рис. 156. Организация очереди FIFO (а) и отбрасывание хвоста в очереди FIFO (б).

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

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

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

Проблема с очередью с приоритетом, конечно же, заключается в том, что очередь с высоким приоритетом может истощить все остальные очереди; то есть, пока в очереди с высоким приоритетом есть хотя бы один высокоприоритетный пакет, очереди с более низким приоритетом не обслуживаются. Чтобы это было жизнеспособным, должны быть жесткие ограничения на количество высокоприоритетного трафика, помещаемого в очередь. Сразу должно быть ясно, что мы не можем позволить пользователям бесконтрольно устанавливать высокий приоритет своим собственным пакетам; мы должны либо полностью запретить им это делать, либо предоставить некую форму «возражения» пользователям. Один очевидный способ сделать это — использовать экономику: сеть может взимать больше за доставку пакетов с высоким приоритетом, чем за пакеты с низким приоритетом. Однако при реализации такой схемы в децентрализованной среде, такой как Интернет, возникают серьезные проблемы.

Одна из ситуаций, в которой приоритетная очередь используется в Интернете, — это защита наиболее важных пакетов — как правило, обновлений маршрутизации, необходимых для стабилизации таблиц маршрутизации после изменения топологии. Часто для таких пакетов существует специальная очередь, которую можно идентифицировать по точке кода дифференцированных услуг (ранее поле TOS) в заголовке IP. На самом деле это простой пример идеи «дифференцированных услуг».

6.2.2 Справедливая организация очереди¶

Основная проблема организации очередей FIFO заключается в том, что она не различает разные источники трафика или, говоря языком, представленным в предыдущем разделе, не разделяет пакеты в соответствии с потоком, к которому они принадлежат. Это проблема двух разных уровней. С одной стороны, неясно, сможет ли какой-либо алгоритм управления перегрузкой, полностью реализованный в источнике, адекватно контролировать перегрузку при столь незначительной помощи со стороны маршрутизаторов. Мы отложим суждение по этому вопросу до следующего раздела, когда будем обсуждать управление перегрузкой TCP. На другом уровне, поскольку весь механизм управления перегрузкой реализуется в источниках, а организация очередей FIFO не предоставляет средства контроля того, насколько хорошо источники придерживаются этого механизма, источник (поток) с плохим поведением может захватить сколь угодно большую долю пропускной способности сети. Снова принимая во внимание Интернет, данное приложение, безусловно, может не использовать TCP и, как следствие, обойти его сквозной механизм управления перегрузкой. (Сегодня это делают такие приложения, как интернет-телефония.) Такое приложение может завалить интернет-маршрутизаторы своими собственными пакетами, что приведет к отбрасыванию пакетов других приложений.

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

Рис. 157. Циклическое обслуживание четырех потоков на маршрутизаторе.

Обратите внимание, что FQ не предполагает, что маршрутизатор сообщает источникам трафика что-либо о состоянии маршрутизатора или каким-либо образом ограничивает скорость отправки пакетов данным источником. Другими словами, FQ по-прежнему предназначен для использования в сочетании со сквозным механизмом управления перегрузкой. Он просто разделяет трафик таким образом, чтобы плохо работающие источники трафика не мешали тем, которые добросовестно реализуют сквозной алгоритм. FQ также обеспечивает равноправие в наборе потоков, управляемых надежным алгоритмом управления перегрузкой.

Какой бы простой ни была основная идея, все же есть небольшое количество деталей, которые вам нужно правильно уловить. Основная сложность заключается в том, что пакеты, обрабатываемые маршрутизатором, не обязательно имеют одинаковую длину. Для действительно справедливого распределения пропускной способности исходящего канала необходимо учитывать длину пакета. Например, если маршрутизатор управляет двумя потоками, один с 1000-байтовыми пакетами, а другой с 500-байтовыми пакетами (возможно, из-за фрагментации восходящего потока от этого маршрутизатора), то простое круговое обслуживание пакетов из очереди каждого потока будет предоставьте первому потоку две трети пропускной способности канала, а второму потоку — только одну треть пропускной способности.

Что нам действительно нужно, так это побитовый циклический перебор, когда маршрутизатор передает бит из потока 1, затем бит из потока 2 и так далее. Ясно, что невозможно чередовать биты из разных пакетов. Таким образом, механизм FQ моделирует такое поведение, сначала определяя, когда данный пакет должен закончить передачу, если бы он отправлялся с использованием побитового циклического перебора, а затем используя это время окончания для упорядочивания пакетов для передачи.

Чтобы понять алгоритм аппроксимации побитового циклического перебора, рассмотрим поведение одного потока и представьте себе часы, которые тикают каждый раз, когда один бит передается из всех активных потоков. (Поток активен, когда у него есть данные в очереди.) Для этого потока пусть \(P_i\) обозначает длину пакета i, пусть \(S_i\) обозначает время, когда маршрутизатор начинает передачу пакета i, и пусть \(F_i\) обозначает время, когда маршрутизатор заканчивает передачу пакета i. Если \(P_i\) выражается в терминах того, сколько тактовых импульсов требуется для передачи пакета i (учитывая, что время увеличивается на 1 такт каждый раз, когда этот поток получает обслуживание на 1 бит), то легко видеть, что \(F_i = S_i + P_i\) .

Когда мы начнем передавать пакет i? Ответ на этот вопрос зависит от того, прибыл ли пакет i до или после того, как маршрутизатор завершил передачу пакета i-1 из этого потока. Если это было раньше, то логически первый бит пакета i передается сразу после последнего бита пакета i-1.С другой стороны, возможно, что маршрутизатор закончил передачу пакета i-1 задолго до прибытия i, а это означает, что существовал период времени, в течение которого очередь для этого поток был пуст, поэтому механизм циклического перебора не смог передать пакеты из этого потока. Если мы позволим \(A_i\) обозначить время прибытия пакета i на маршрутизатор, тогда \(S_i = \max(F_, A_i)\) . Таким образом, мы можем вычислить

Теперь мы переходим к ситуации, в которой существует более одного потока, и обнаруживаем, что в определении \(A_i\) есть одна загвоздка. Мы не можем просто прочитать настенные часы, когда приходит пакет. Как отмечалось выше, мы хотим, чтобы время увеличивалось на один тик каждый раз, когда все активные потоки получают один бит обслуживания при побитовом циклическом переборе, поэтому нам нужны часы, которые продвигаются медленнее, когда потоков больше. В частности, часы должны продвигаться на один тик, когда передается n битов, если есть n активных потоков. Эти часы будут использоваться для расчета \(A_i\) .

Теперь для каждого потока мы вычисляем \(F_i\) для каждого приходящего пакета, используя приведенную выше формулу. Затем мы рассматриваем все \(F_i\) как временные метки, и следующим пакетом для передачи всегда является пакет с наименьшей временной меткой — пакет, который, исходя из приведенных выше рассуждений, должен завершить передачу раньше всех остальных.

Обратите внимание, что это означает, что пакет может прибыть в поток, и, поскольку он короче, чем пакет из какого-либо другого потока, который уже находится в очереди, ожидающей передачи, его можно вставить в очередь перед этот более длинный пакет. Однако это не означает, что вновь прибывший пакет может вытеснить пакет, который передается в данный момент. Именно это отсутствие вытеснения не позволяет только что описанной реализации FQ точно имитировать побитовую циклическую схему, которую мы пытаемся аппроксимировать.

Рисунок 158. Пример справедливой постановки в очередь в действии: (a) пакеты с более ранним временем окончания отправляются первыми; (b) отправка уже выполнявшегося пакета завершена.

Чтобы лучше понять, как работает эта реализация справедливой организации очередей, рассмотрим пример, приведенный на рис. 158. Часть (а) показывает очереди для двух потоков; алгоритм выбирает оба пакета из потока 1 для передачи перед пакетом в очереди потока 2 из-за их более раннего времени завершения. В (b) маршрутизатор уже начал отправлять пакет из потока 2, когда приходит пакет из потока 1. Хотя пакет, поступающий в поток 1, завершился бы до потока 2, если бы мы использовали идеальную побитовую справедливую организацию очереди, реализация не вытесняет пакет потока 2.

Есть два момента, на которые следует обратить внимание при организации справедливой очереди. Во-первых, канал никогда не простаивает, пока в очереди есть хотя бы один пакет. Любая схема организации очередей с такой характеристикой называется сохраняющей работу. Одним из последствий экономии труда является то, что если я делюсь ссылкой с большим количеством потоков, которые не отправляют никаких данных, то; Я могу использовать полную пропускную способность канала для своего потока. Однако, как только другие потоки начнут отправлять, они начнут использовать свою долю, и пропускная способность, доступная моему потоку, упадет.

Второе, на что следует обратить внимание, это то, что если ссылка полностью загружена и существует n потоков, отправляющих данные, я не могу использовать более 1/n пропускной способности ссылки. Если я попытаюсь отправить больше, моим пакетам будут назначаться все более крупные временные метки, из-за чего они дольше будут находиться в очереди в ожидании передачи. В конце концов, очередь переполнится — хотя отбрасываются ли мои пакеты или чьи-то еще — это решение, которое не определяется тем фактом, что мы используем справедливую организацию очереди. Это определяется политикой отбрасывания; FQ — это алгоритм планирования, который, как и FIFO, можно комбинировать с различными политиками отбрасывания.

Поскольку FQ экономит работу, любая полоса пропускания, не используемая одним потоком, автоматически становится доступной для других потоков. Например, если у нас есть четыре потока, проходящих через маршрутизатор, и все они отправляют пакеты, то каждый из них получит четверть пропускной способности. Но если один из них бездействует достаточно долго, чтобы все его пакеты вылетели из очереди маршрутизатора, то доступная пропускная способность будет разделена между оставшимися тремя потоками, каждый из которых теперь будет получать по одной трети пропускной способности. Таким образом, мы можем думать о FQ как о предоставлении гарантированной минимальной доли полосы пропускания каждому потоку с возможностью того, что он может получить больше, чем гарантировано, если другие потоки не используют свои доли.

Можно реализовать разновидность FQ, называемую взвешенной справедливой организацией очереди (WFQ), которая позволяет назначать вес каждому потоку (очереди).Этот вес логически определяет, сколько битов будет передаваться каждый раз, когда маршрутизатор обслуживает эту очередь, что эффективно контролирует процент пропускной способности канала, который получит поток. Simple FQ присваивает каждой очереди вес, равный 1, что означает, что логически каждый раз из каждой очереди передается только 1 бит. Это приводит к тому, что каждый поток получает \(1/n^\) полосы пропускания при наличии n потоков. Однако с WFQ одна очередь может иметь вес 2, вторая очередь может иметь вес 1, а третья очередь может иметь вес 3. Предполагая, что каждая очередь всегда содержит пакет, ожидающий передачи, первая поток получит одну треть доступной пропускной способности, второй — одну шестую доступной пропускной способности, а третий — половину доступной пропускной способности.

Хотя мы описали WFQ с точки зрения потоков, обратите внимание, что его можно реализовать на классах трафика, где классы определяются другим способом, отличным от простых потоков, представленных в начале этой главы. . Например, мы могли бы использовать некоторые биты в заголовке IP для идентификации классов и выделения очереди и веса каждому классу. Это именно то, что предлагается как часть архитектуры дифференцированных услуг, описанной в следующем разделе.

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

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

Рис. 1. Изображение входящего и исходящего трафика маршрутизатора

Перегруженность очереди и правила организации очереди

Очереди маршрутизатора подвержены перегрузке из-за ограниченного объема доступной им буферной памяти. Когда скорость входящего трафика становится больше, чем количество, которое может быть перенаправлено на выходной интерфейс, наблюдается перегрузка. Потенциальные причины такой ситуации в основном включают:

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

Чтобы управлять выделением памяти маршрутизатора для пакетов в таких ситуациях перегрузки, маршрутизаторы могут следовать различным дисциплинам, чтобы определить, какие пакеты оставить, а какие отбросить. Соответственно, у нас есть следующие важные дисциплины очередей в маршрутизаторах:

Очередь в порядке очереди (FIFO)

Схема организации очереди по умолчанию, используемая большинством маршрутизаторов, — FIFO. Как правило, это требует небольшой настройки на сервере. Все пакеты в FIFO обслуживаются в том же порядке, в котором они поступают на маршрутизатор. При достижении насыщения в памяти новые пакеты, пытающиеся войти в маршрутизатор, отбрасываются (tail drop). Однако такая схема не подходит для приложений реального времени, особенно во время перегрузки. Приложение реального времени, такое как VoIP, которое постоянно отправляет пакеты, может не работать во время перегрузки, и все его пакеты будут отброшены.

Приоритетная очередь (PQ)

При приоритетной очереди вместо использования одной очереди маршрутизатор разбивает память на несколько очередей на основе определенного показателя приоритета. После этого каждая очередь обрабатывается в порядке FIFO, циклически перебирая очереди одну за другой. Очереди помечаются как High, Medium или Low в зависимости от приоритета. Пакеты из очереди High всегда обрабатываются раньше пакетов из очереди Medium. Аналогично, пакеты из средней очереди всегда обрабатываются раньше пакетов из обычной очереди и т. д.Пока некоторые пакеты находятся в очереди с высоким приоритетом, никакие пакеты из другой очереди не обрабатываются. Таким образом, пакеты с высоким приоритетом переходят в начало очереди и обслуживаются первыми. Как только очередь с более высоким приоритетом очищается, только тогда обслуживается очередь с более низким приоритетом.

Рис. 2. Несколько подочередей, используемых в схеме приоритетной очереди

Очевидным преимуществом PQ является то, что трафик с более высоким приоритетом всегда обрабатывается первым. Однако существенным недостатком схемы PQ является то, что очереди с более низким приоритетом часто могут
не получать вообще никакого обслуживания из-за голодания. Постоянный поток трафика с высоким приоритетом может привести к истощению очередей с более низким приоритетом

Взвешенная справедливая организация очереди (WFQ)

Weighted Fair Queuing (WFQ) динамически создает очереди на основе потоков трафика и назначает полосу пропускания для этих потоков в зависимости от приоритета. Подочередям назначается пропускная способность динамически. Предположим, что существуют 3 очереди с пропускной способностью в процентах 20%, 30% и 50%, когда все они активны. Затем, если 20-процентная очередь простаивает, освободившаяся полоса пропускания распределяется между оставшимися очередями с сохранением исходных коэффициентов пропускной способности. Таким образом, очереди 30 % теперь выделяется (75/2) %, а очереди 50 % теперь выделяется пропускная способность (125/2) %.

Исходный и целевой IP-адреса
Исходный и целевой порты TCP (или UDP)
Номер IP-протокола
Значение типа службы (IP-приоритет или DSCP)

Рис. 3. Динамически выделяемая пропускная способность для подочередей в WFQ

Таким образом, пакеты распределяются по отдельным очередям в зависимости от соответствующего им потока трафика. После идентификации пакеты, принадлежащие одному и тому же потоку трафика, вставляются в очередь, созданную специально для такого трафика. По умолчанию внутри маршрутизатора может быть установлено максимум 256 очередей, однако это число может быть увеличено до 4096 очередей. В отличие от схем PQ, очередям WFQ выделяется разная пропускная способность в зависимости от их приоритетов очереди. Пакеты с более высоким приоритетом планируются раньше, чем пакеты с более низким приоритетом, поступающие в то же время.

Влияние дисциплин очередей на сеть

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

Рис. 4. Количество отброшенных пакетов в зависимости от времени для различных дисциплин очередей (моделирование в Riverbed Modeler)

Главная страница сайта
(новости и уведомления)

Получать оповещения при обновлении Linktionary

Обновления и дополнения к книгам

Загрузить электронную версию Энциклопедии сетей, 2-е издание (1996 г.). Это бесплатно!

Примечание. Многие темы на этом сайте являются сокращенными версиями текста в "Энциклопедии сетей и телекоммуникаций". Результаты поиска не будут такими обширными, как поиск на компакт-диске с книгой.

Вы знакомы с очередями как с очередью людей, ожидающих купить билеты или поговорить с представителем службы поддержки по телефону. Очередь также представляет собой набор объектов, ожидающих обработки по одному за раз. В сетевой среде пакеты ставятся в очередь в буферах памяти сетевых устройств, таких как маршрутизаторы и коммутаторы. Пакеты в очереди обычно располагаются в порядке «первым пришел — первым обслужен», но могут использоваться различные методы для определения приоритетов пакетов или обеспечения справедливой обработки всех пакетов вместо того, чтобы позволить одному источнику захватить больше, чем его доля ресурсов.< /p>

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

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

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

Сети множественного доступа, такие как интранет и Интернет, называются "сетями очередей". В канале «точка-точка» получатель отслеживает свои собственные очереди и сигнализирует отправителю, когда он отправляет слишком быстро. В сетях с коммутацией пакетов, где множество отправителей передают в любой момент времени, невозможно предсказать уровни трафика. Некоторые части сети могут стать более перегруженными, чем другие. Решение состоит в том, чтобы размещать очереди по всей сети, чтобы принимать пакеты от одного или нескольких отправителей.

В этом разделе объясняются основные приемы работы с очередями. При попытке понять, как работает конкретная система, можно задать следующие вопросы об очередях:

<УЛ>

Как входящие пакеты помещаются в очереди?

В каком порядке и/или каким методом сетевое устройство обслуживает свои очереди?

Каковы стратегии борьбы с резкими скачками трафика и переполнением очередей?

Существует несколько методов организации очереди, в том числе FIFO (первым пришел - первым обслужен), приоритетная очередь и справедливая очередь. FIFO используется во всех схемах организации очередей, поскольку описывает основной метод прохождения пакетов через очереди. Вы можете представить очереди как кассы супермаркетов. Каждая полоса использует очередь FIFO, но кассиры могут изменить порядок, чтобы уменьшить заторы (например, перетащить покупателей из загруженных полос в менее загруженные полосы). Покупатели с членскими картами, наличными или небольшим количеством товаров могут попасть в экспресс-полосу (расстановка приоритетов).

<УЛ>

Очередь FIFO Это базовый метод организации очереди по принципу «первым поступил – первым обслужен», при котором первый пакет в очереди является первым обрабатываемым пакетом. Когда очереди переполняются, возникает перегрузка и входящие пакеты отбрасываются. FIFO полагается на конечные системы для контроля перегрузки с помощью механизмов управления перегрузкой.

Очередь с приоритетом В этом методе используется несколько очередей, но очереди обслуживаются с разными уровнями приоритета, при этом очереди с наивысшим приоритетом обслуживаются в первую очередь. Рисунок Q-2 иллюстрирует схему приоритетной очереди Cisco. При перегрузке пакеты удаляются из очередей с более низким приоритетом. Единственная проблема с этим методом заключается в том, что очереди с более низким приоритетом могут вообще не обслуживаться, если трафик с высоким приоритетом является чрезмерным. Пакеты классифицируются и помещаются в очереди в соответствии с информацией в пакетах. Например, маршрутизаторы Cisco можно запрограммировать таким образом, чтобы трафик для определенного порта распределялся по очередям с высоким, средним или низким приоритетом. Пользователи или приложения могут злоупотреблять схемами приоритетов, которые помечают пакеты недопустимыми приоритетами. Функции контроля доступа могут контролировать это. См. «Контроль доступа».

Справедливая постановка в очередь Этот метод помогает решить проблему, когда некоторые очереди могут не обслуживаться из-за того, что обслуживаются очереди с высоким приоритетом. Циклический подход используется для справедливого обслуживания всех очередей. Это предотвращает чрезмерное использование каким-либо одним источником своей доли пропускной способности сети. Проблемы могут возникнуть, когда пакеты имеют разную длину и каждой очереди разрешено выпускать по одному пакету за раз. Некоторые очереди занимают больше времени. Для выравнивания очередей может использоваться байт-ориентированная схема. Кроме того, некоторые очереди могут быть более заполнены, чем другие, и, естественно, нуждаются в большем обслуживании, но строгая и справедливая схема организации очередей будет обслуживать каждую очередь в равной степени.

WFQ (взвешенная равноправная организация очереди) Это можно рассматривать как комбинацию приоритетной организации очереди и справедливой организации очереди. Все очереди обслуживаются так, что ни одна из них не голодает, но некоторые очереди обслуживаются больше, чем другие. К очередям применяется вес, чтобы дать некоторым очередям более высокий приоритет. Например, одна очередь может получить половину доступной пропускной способности, а другие очереди получат выделение оставшейся пропускной способности. Трафик может иметь приоритет в соответствии с маркировкой пакетов, полями IP-адреса источника и получателя, номерами портов и информацией в поле ToS. WFQ взвешивает трафик, чтобы трафик с низкой пропускной способностью получал справедливый уровень приоритета. Если очереди с высоким приоритетом не используются, трафик с более низким приоритетом использует свои очереди. Это не позволяет трафику с высокой пропускной способностью захватывать несправедливую долю ресурсов. WFQ — это «основной метод организации очередей» Cisco, согласно документу Cisco QoS, указанному на странице соответствующих записей. Уникальной особенностью является то, что он перемещает интерактивный трафик в реальном времени в начало очередей и справедливо распределяет оставшуюся полосу пропускания между другими потоками.

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

<УЛ>

Буферизация предназначена для поглощения пакетов данных и их передачи в течение последующего медленного периода (при условии, что это произойдет).

"Блокировка" очереди происходит, когда отправителю разрешено монополизировать пространство в очереди и не позволяет другим соединениям получить место в очереди. Отправитель может разрываться или отправлять большие пакеты.

Переменная длина пакетов в IP-сетях (до 1500 байт) затрудняет управление очередями и, следовательно, качество обслуживания. Невозможно точно оценить задержку с переменными размерами пакетов.

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

Должны быть разрешены временные всплески. Действия по уменьшению временных всплесков путем отбрасывания пакетов могут быть ненужной тратой полосы пропускания.

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

Вместо отбрасывания хвоста можно использовать две дисциплины очереди. «Случайное отбрасывание при заполнении» отбрасывает случайно выбранные пакеты. «Drop front on full» отбрасывает пакеты в начале очереди. Отбрасывание на передний план используется для более быстрого уведомления отправителя о перегрузке. Рассмотрим случай, когда отправитель заполнил очередь и происходит отбрасывание хвоста. Получатель будет продолжать получать пакеты и не будет знать о перегрузке, пока не заметит отброшенный пакет. Отбрасывание впереди сообщает приемнику о перегрузке (отсутствием подтверждения).

Активное управление очередями — это процесс отбрасывания пакетов до переполнения буфера. Механизм под названием RED (случайное раннее обнаружение) определяет, когда очередь вот-вот переполнится, отслеживая несколько пороговых уровней. Когда уровень превышен, пакеты отбрасываются «вероятностно» в попытке сократить отправителя. RED и некоторые варианты RED обсуждаются в разделе «Механизмы управления перегрузкой».

Пакеты пакетов неизбежны. Отбрасывание пакетов из временных пакетов бесполезно, поскольку это приведет к замедлению отправителя, когда в этом может не быть необходимости. Небольшой средний размер очереди помогает активному управлению очередями обеспечивать большую емкость для поглощения естественных всплесков без потери пакетов.

Небольшие очереди сокращают задержки, что очень важно для трафика в реальном времени.

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

Поскольку базовое управление очередями не обеспечивает состояние каждого потока (отслеживание потоков пакетов с одним и тем же IP-адресом источника/получателя и портом), для объективного распределять пропускную способность между потоками. Алгоритмы планирования и управление очередями следует рассматривать как дополняющие, а не заменяющие друг друга.

Алгоритмы формирования трафика управляют очередями таким образом, чтобы сгладить поток пакетов в сети между узлами или маршрутизаторами. Например, хост может использовать на сетевом интерфейсе так называемое дырявое ведро. Ведро — это, по сути, регулируемая очередь. Приложение может создавать неравномерный поток пакетов, которые вырываются или просачиваются в ведро, но ведро имеет воображаемую дыру в дне, через которую непрерывным потоком может выйти только определенное количество пакетов. Token Bucket развивает эту концепцию дальше, позволяя очереди сохранять разрешение на отправку пакетов пакетов в более позднее время. Типичный алгоритм заключается в том, что каждую секунду времени сохраняется токен. Если пакет отправляется, один из этих маркеров уничтожается. Если пакеты не отправляются, начинают накапливаться маркеры, которые можно использовать позже для пакетной передачи пакетов.

UDP может использоваться приложениями, которым не нужны гарантированные службы TCP. UDP не подтверждает получение пакетов отправителю; поэтому он не поддерживает управление перегрузкой на основе отбрасывания пакетов. Когда очереди заполнятся, UDP продолжит отправку. Контроллеры скорости могут помочь, как описано в разделе «Механизмы управления перегрузкой».

Как уже упоминалось, механизмы управления перегрузкой TCP и схемы управления активными очередями, такие как RED, обсуждаются в разделе «Механизмы управления перегрузкой». Помимо механизмов управления перегрузкой, существуют методы QoS, такие как Int-Serv (интегрированные службы) и RSVP (протокол резервирования ресурсов). Обзор и ссылки на соответствующие разделы см. в разделе "QoS (качество обслуживания)".

Как маршрутизатор/коммутатор/мультиплексор узнает, в какую очередь в какую очередь поместить пакет, при организации взвешенной справедливой очереди? Например, читает ли он заголовки каждого пакета, чтобы узнать отправителя и предполагаемое приложение?

Например, как работает функция "классифицировать прибытия"?

Я позволил себе отредактировать вопрос, сделав его менее широким; мы не можем брать вопросы, которые ведут к ответам размером со статью в википедии. Если мы не ограничим это одной функцией qos, вопрос будет слишком широким

Помог ли вам какой-либо ответ? если это так, вы должны принять ответ, чтобы вопрос не появлялся вечно в поисках ответа. Кроме того, вы можете опубликовать и принять свой собственный ответ.

2 ответа 2

Сетевое устройство обычно имеет 3–4 очереди для обработки трафика. WFQ, строго говоря, не является алгоритмом организации очереди, это алгоритм планирования исходящего трафика. Он определяет, как трафик, помещенный в разные очереди, отправляется из устройства. Работа честной очереди заключается в том, что трафик, размещенный в разных очередях, обслуживается по порядку, например, в случае трех очередей они будут обслуживаться 1-2-3-1-2-3 и так далее. Мы можем дать двойной вес очереди 1, и в этом случае очереди будут обслуживаться 1-1-2-3-1-1-2-3.

"Классификация поступивших" относится к тому, как входящие пакеты обрабатываются внутри самого устройства. Обычно сетевые устройства поддерживают существующий приоритет трафика, помещая входящие пакеты в соответствующую исходящую очередь в зависимости от того, какой у них приоритет. Однако в любом случае устройство фактически просматривает сам кадр, заголовок L2 или L3.

Приоритет входящих фреймов можно задать несколькими способами. Мы можем использовать входной интерфейс или определить его по информации кадра уровня 2, такой как приоритет 802.1p/Q (класс обслуживания, CoS), MAC-адрес L2 или идентификатор VLAN. Вот как работает устройство L2, такое как коммутатор. Например, пакет может прибыть в конкретную «голосовую» сеть VLAN (используемую для VOIP-трафика), и в этом случае он будет помещен в исходящую очередь с высоким приоритетом. Или тег VLAN 802.1Q заголовка кадра может содержать 3-битное поле PCP (Priority Code Point), которое определяет, в какую очередь помещен пакет.

PHB по умолчанию — обычно трафик с максимальной эффективностью, используемый для обычного трафика данных ПК.
Ускоренная переадресация (EF PHB) — используется для трафика с малыми потерями и задержкой, например VOIP.
Гарантированная переадресация (AF PHB) — гарантирует доставку при определенных заранее определенных условиях.
Селектор класса PHB — поддерживает обратную совместимость с ранее использовавшимся полем ToS (тип службы) в заголовке IPv4.

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

Читайте также: