Очереди

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

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

Даже в худшем случае, когда по всем п входных линиям будут поступать пакеты, коммутатор сможет переправлять все п пакетов из входных портов в выходные порты за время, необходимое для того, чтобы каждый из п входных портов одновременно принял по одному пакету. Но что происходит на выходных портах? Будем продолжать предполагать, что пропускная способность коммутационного блока, по меньшей мере, в п раз превосходит скорость передачи данных в линии. В худшем случае все пакеты, принятые на п входных портах, направляются в один и тот же выходной порт. В этом случае за время приема/передачи одного пакета на этот выходной порт поступят сразу п пакетов. Поскольку за этот интервал времени выходной порт может передать только один пакет, из оставшихся п — 1 пакетов образуется очередь. За следующий интервал времени на выходной порт могут поступить еще п пакетов, которые добавятся к уже имеющейся очереди, и т. д. Наконец, число пакетов в очереди может вырасти настолько, что у маршрутизатора закончится свободная память для их размещения, после чего ему придется отбрасывать некоторые пакеты.

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

437.png

В результате планировщик пакетов выходного порта должен выбрать из стоящих в очереди пакетов один для передачи в линию. Этот выбор может осуществляться на основе простой дисциплины очередей, например, алгоритма FCFS (First Соте, First Served — первым пришел, первым обслужен), или на основе более сложной дисциплины планирования, например, алгоритма WFQ (Weighted Fair Queuing — взвешенная справедливая организация очередей). Планирование пакетов играет ключевую роль в предоставлении гарантий качества обслуживания. Этот вопрос мы подробно рассмотрим в главе 6.

Аналогично, если не хватает памяти для буферизации входящего пакета, необходимо принять решение о том, отбросить ли новый пакет (такая политика иногда называется «обрубанием хвостов») или удалить из буфера один или несколько уже стоящих в очереди пакетов, чтобы освободить место для нового пакета. В некоторых случаях может быть выгодно отбросить пакет (или пометить заголовок пакета), прежде чем буфер заполнится, чтобы тем самым послать сигнал отправителю. Было предложено и проанализировано множество алгоритмов отбрасывания и пометки пакетов, которые совместно получили название алгоритмов активного управления очередями (Active Queuing Management, AQM). Одним из наиболее глубоко изученных и распространенных алгоритмов AQM является алгоритм RED (Random Early Detection — случайное раннее обнаружение). В алгоритме RED для длины выходной очереди вычисляется взвешенное среднее значение. Если при поступлении пакета средняя длина очереди оказывается меньше минимальной границы min(th), пакет ставится в очередь. Если, напротив, в момент прибытия пакета очередь полна или средняя длина очереди оказывается больше максимальной границы mах(th), пакет маркируется или отбрасывается. Наконец, если при поступлении пакета средняя длина очереди находится в интервале [min(th), mах(th)], пакет маркируется или отбрасывается с вероятностью, представляющей собой функцию средней длины и параметров min(th) и mах(th). Было предложено несколько вероятностных функций и реализовано несколько версий алгоритма RED.

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

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

438.png

Данная статья "Очереди" размещена на сайте Компьютерные сети и многоуровневая архитектура интернета (conlex.kz) в ознакомительных целях.

Уточнения, корректировки и обсуждения статьи "Очереди" - под данным текстом, в комментариях.

Ответственность, за все изменения, внесённые в систему по советам данной статьи, Вы берёте на себя.

Копирование статьи "Очереди", без указания ссылки на сайт первоисточника Компьютерные сети и многоуровневая архитектура интернета (conlex.kz), строго запрещено.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *