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

Рис. 9.10. Обратная коррекция.

На рис. 9.10 показано, как метод обратной коррекции решает проблему маршрутных петель, с которой мы столкнулись на рис. 9.9. В результате обратной коррекции в таблице расстояний узла Y в записи стоимости пути до узла X через узел Z указана бесконечность (так как узел Z сообщил узлу Y, что расстояние от узла Z до узла X равно бесконечности). Когда в момент времени t0 стоимость линии XY увеличивается с 4 до 60, узел У обновляет свою таблицу, но продолжает направлять пакеты узлу X напрямую, несмотря на увеличившуюся стоимость маршрута, а также информирует узел Z об изменении стоимости. Получив это извещение в момент времени tu узел Z немедленно изменяет свой маршрут к узлу X на прямую линию ZX стоимости 50. Поскольку маршрут к узлу X изменился, и этот новый маршрут более не проходит через узел F, узел Z сообщает узлу Y о своем новом маршруте в момент времени t2. Получив эту информацию, узел Y обновляет свою таблицу расстояний, изменяя свой маршрут к узлу X. Теперь этот маршрут стоимости 51 проходит через узел Z. Кроме того, поскольку через узел Z теперь проходит путь наименьшей стоимости от узла Fk узлу X, узел Y «отравляет» обратный путь от узла Z до узла X, сообщая в момент времени t3 узлу Z, что стоимость пути от узла 7до узла X равна бесконечности. Этот алгоритм успокаивается в момент времени Ј4, со значениями таблицы расстояний для адресата Х1 показанными в правом столбце.

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

7. Сравнение алгоритмов маршрутизации

Перед рассмотрением других алгоритмов маршрутизации дадим краткое сравнение некоторых характеристик алгоритма, основанного на состоянии линий, и дистанционно-векторного алгоритма.

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

□ Скорость схождения. Как мы видели, количество вычислений в нашей реализации алгоритма, основанного на состоянии линий, растет пропорционально квадрату узлов сети, требуя передачи 0(пЕ) сообщений. Дистанционно-векторный алгоритм может сходиться медленно (в зависимости от относительной стоимости путей, как было показано в примере на рис. 4.10), и во время схождения могут образовываться маршрутные петли. Кроме того, дистанционно-векторный алгоритм страдает от «приступов» счета до бесконечности.

□ Живучесть. Что может случиться, если маршрутизатор выйдет из строя, «сойдет с ума» или объявит забастовку? В алгоритме маршрутизации, основанном на состоянии линий, маршрутизатор может передать всем остальным маршрутизаторам неверные сведения о стоимости одной из присоединенных к нему линий. Узел может также повредить или потерять один из широковещательных пакетов LS-алгоритма, который он получил. Но узел рассчитывает только собственную таблицу продвижения данных. Остальные узлы сами вычисляют свои таблицы. Это означает, что в алгоритме, основанном на состоянии линий, расчеты маршрутов выполняются в значительной степени раздельно, что предоставляет определенную степень живучести. В случае дистанционно-векторного алгоритма узел может передать другим узлам неверно сосчитанные им значения минимальной стоимости путей. (Такие ситуации встречаются на практике. В 1997 году неисправный маршрутизатор, принадлежащий небольшой компании, занимающейся предоставлением доступа в Интернет, снабжал маршрутизаторы национальной магистрали ошибочной информацией о маршрутах. Это привело к тому, что другие маршрутизаторы завалили трафиком неисправный маршрутизатор, в результате большие фрагменты Интернета в течение нескольких часов были отрезаны.) Обратите внимание, что в дистанционно-векторном алгоритме на каждой итерации результаты вычислений узла непосредственно передаются соседнему узлу, а затем на следующей итерации они попадают к соседу соседа и т. д. Таким образом, в дистанционно-векторном алгоритме некорректно вычисленные данные могут распространиться по всей сети.

В заключение скажем, что ни один алгоритм нельзя считать «победителем». Как мы увидим в разделе «Маршрутизация в Интернете», в Интернете применяются оба эти алгоритма.

Иерархическая маршрутизация

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

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

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

Обе эти задачи могут быть решены путем объединения маршрутизаторов в отдельные области, называемые автономными системами (Autonomous System, AS). Маршрутизаторы в пределах одной автономной системы используют один и тот же алгоритм маршрутизации (например, дистанционно-векторный алгоритм или алгоритм, основанный на состоянии линий) и обладают информацией обо всех маршрутизаторах своей автономной системы, как это было в рассмотренном ранее идеальном случае. Алгоритм маршрутизации, используемый внутри автономной системы, называется протоколом внутренней маршрутизации. Разумеется, необходимо соединить автономные системы друг с другом, и поэтому один или несколько маршрутизаторов в автономной системе будет отвечать за пересылку пакетов за пределы автономной системы. Эти маршрутизаторы называются шлюзовыми маршрутизаторами, или просто шлюзами. Чтобы шлюзовые маршрутизаторы могли направлять пакеты из одной автономной системы в другую (возможно, пересекая множество других автономных систем), шлюзы должны знать, как определить маршруты друг к другу. Алгоритм маршрутизации, в котором для определения маршрутов между различными автономными системами применяют шлюзы, называется протоколом внешней маршрутизации.

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

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

Данный сценарий иллюстрирует рис. 9.11. Здесь изображены три автономные системы, А, В и С. В автономной системе А имеется четыре маршрутизатора, А. а, А. Ь, А. с и A. d, на которых работает протокол внутренней маршрутизации, используемый в пределах автономной системы А. Эти четыре маршрутизатора обладают полной информацией о маршрутах внутри автономной системы А. Аналогично в автономных системах В и С есть три и два маршрутизатора соответственно. Обратите внимание, что протоколы внутренней маршрутизации, применяемые в автономных системах А, В и С, могут быть разными. Шлюзовыми маршрутизаторами являются А. а, А. с, В. а и протоколов внутренней маршрутизации на этих четырех маршрутизаторах работает протокол внешней маршрутизации.

Рис. 9.11 Внутренняя и внешняя маршрутизация

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