Учебно-методическии комплекс дисциплины «Компьютерные сети» для специальности 6М011100 — «Информатика» (стр. 55 )

Рис. 11.10 Образование очередей в выходном порту

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

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

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

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

Рис. 11.11 Блокирование головы очереди на входном порту

4. Резюме

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

Протоколы внутренней маршрутизации используются для определения маршрутов внутри автономной системы. Эти протоколы также называют внутренними шлюзовыми протоколами (Interior Gateway Protocol, ЮР)

Протокол RIP работает по дистанционно-векторному алгоритму. В протоколе RIP обмен новыми сведениями между соседними маршрутизаторами происходит приблизительно через каждые 30 с, для чего используются так называемые ответные RIP-сообщения.

Протокол OSPF представляет собой протокол, основанный на учете состоянии линий и использующий метод лавинной рассылки для распространения информации о состоянии линий, а также алгоритм определения пути наименьшей стоимости Дейкстры. Маршрутизатор, работающий по протоколу OSPF, формирует полную топологическую карту (направленный граф) всей автономной системы. Затем маршрутизатор локально запускает алгоритм определения кратчайшего пути Дейкстры, чтобы найти дерево кратчайших путей ко всем сетям автономной системы.

Протокол BGP распознает автономные системы по глобально уникальным номерам автономных систем. В основе протокола BGP лежат объявления о маршрутах. Объявление о маршрутах посыпается одним равноправным BGP-узлом другому равноправному BGP-узлу по соединению «точка-точка».

Маршрутизатор состоит из четырех компонентов: входные порты, выходные порты, коммутационный блок, маршрутный процессор.

5. Вопросы для самоконтроля.

1. В чем разница между внутренними и внешними шлюзовыми протоколами?

2. Какая метрика используется в протоколе RIP?

3. Какие существуют способы ускорения сходимости протокола RIP?

4. Назовите основные этапы построения таблицы маршрутизации по протоколу OSPF.

5. Какие типы метрик поддерживает протокол OSPF? .

6. Для чего сеть маршрутизаторов, поддерживающих протокол OSPF, разбивают на области?

7. Что можно отнести к недостаткам протокола OSPF?

8. Почему протокол EGP больше не применяется в Интернете?

9. За счет какого механизма протокол BGP может работать в сетях, где между автономными системами существуют петли?

10. Какие параметры в объявлении, полученном от какой-либо автономной системы, меняет BGP-маршрутизатор, когда передает его в другую автономную систему?

11. В каких случаях ICMP-сообщение об ошибке не может быть послано при возникновении проблемы с 1Р-пакетом?

12. Кому адресовано ICMP-сообщение? Какой программный модуль обрабатывает его?

13. Каким образом ICMP-сообщение повышает надежность передачи данных по 1Р-сети?

6. Тесты для самоконтроля знаний.

1. Протокол внутренней маршрутизации используется для выбора

a) маршрутов дейтаграмм в пределах одной автономной системы

b) выбора маршрутов дейтаграмм между автономными системами

c) выбора маршрутов сегментов между автономными системами

d) выбора маршрутов кадров между автономными системами

e) выбора маршрутов файлов между автономными системами

2. Протокол внешней маршрутизации используется для выбора

a) маршрутов дейтаграмм в пределах одной автономной системы

b) выбора маршрутов дейта1рамм между автономными системами

c) выбора маршрутов сегментов между автономными системами

d) выбора маршрутов кадров между автономными системами

е) выбора маршрутов файлов между автономными системами

3. Автономная система - это

a) Множество маршрутизаторов, находящихся под общимадминистративным и техническим управлением и использующих разные протоколы маршрутизации

b) Множество маршрутизаторов, находящихся под разнымадминистративным и техническим управлением и использующих один и тот же протокол маршрутизации

c) Множество маршрутизаторов, находящихся под общимадминистративным и техническим управлением и использующих один и тот же протокол маршрутизации

d) Множество коммутаторов, находящихся под общим административным и техническим управлением и использующих один и тот же протокол маршрутизации

e) Множество повторителей, находящихся под общим административным и техническим управлением и использующих один и тот же протокол маршрутизации

4. Протокол RIP (Routing Information Protocol — протокол маршрутной информации) работает по

a) алгоритму, основанный на состоянии линий

b) алгоритму динамической маршрутизации

c) алгоритму адаптивной маршрутизации

d) дистанционно-векторному алгоритму

e) алгоритму скользящего окна

5. В качестве единиц измерения стоимости маршрутов использует

a) количество ретрансляционных мостов

b) количество ретрансляторов

c) количество сетевых тарелок

d) количество компьютеров

e) количество ретрансляционных участков

6. Максимальная стоимость пути т. е. диаметр автономной системы, поддерживаемой протоколом RIP, ограничена значением

a) 2

b) 15

c) 16

d) 32

e) 64

7. Ответное RIP-сообщение, посылаемое маршрутизатором или хостом, содержит

a) список, в котором указаны до 25 сегей-адресагов в пределах автономной системы

b) расстояния до каждой из этих сетей от отправителя

c) список, в котором указаны до 25 сетей-адресатов в пределах автономной системы, расстояния до каждой из этих сетей от отправителя

d) Список ответов

e) Список сообщений

8. Протокол RIP

a) обрабатывает информацию о маршрутах

b) обменивается сообщениями с такими же процессами, работающими на соседних маршрутизаторах

c) управляет таблицами продвижения данных

d) отправлять и получать сообщения через стандартный сокет

e) Это пункты a-d

9. Открытый протокол выбора кратчайшего маршрута OSPF используется

a) для составления списка, в котором указаны до 25 сетей-адресатов в пределах автономной системы