Э. Таненбаум - Компьютерные сети. (4-е издание) (DJVU) (1130092), страница 112

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 112)

К счастью, С говорит: «Не волнуйся. У меня есть путь к А длиной 2». В не знает, что путь от С к А проходит через В. В может только предполагать, что у С около 10 выходных линий с независимыми путями к А, кратчайшая из которых имеет длину 2. Поэтому теперь В думает, что может связаться с А через С по пути длиной 3. При этом первом обмене маршрутизаторы Р и Е не обновляют свою информацию об А. Алгоритмы маршрутизации 417 При втором обмене векторами С замечает, что у всех его соседей есть путь к А ддиной 3. Он выбирает один из них случайным образом и устанавливает свое расстояние до А равным 4, как показано в третьей строке на рис.

5.8, 6. Результаты последующих обменов векторами также показаны на этом рисунке. Теперь должно быть понятно, почему плохие новости медленно распространяются — ни один маршрутизатор не может установить значение расстояния, более чем на единицу превышающее минимальное значение этого расстояния, хранящееся у его соседей. Таким образом, все маршрутизаторы будут до бесконечности увеличивать значение расстояния до выключенного маршрутизатора. Количество необходимых для завершения этого процесса обменов векторами можно ограничить, если установить значение этой «бесконечности» равным длине самого длинного пути плюс 1. Если расстояния в подсети измеряются во временных задержках, такую верхнюю границу выбрать сложнее.

Следует выбирать достаточно большое ограничивающее значение, чтобы линия с большой задержкой не была сочтена совсем не работающей. Неудивительно, что эта проблема называется счетом до бесконечности. Было сделано несколько попыток решить ее (например, алгоритм расколотого горизонта, весьма бесполезный во многих случаях, но внесенный в КРС 1058), но все они оказались безуспешными.

Суть проблемы заключается в том, что когда Х сообщает У о том, что у него есть какой-то путь, у У нет никакой возможности узнать, входит ли он сам в этот путь. Маршрутизация с учетом состояния линий Маршрутизация на основе векторов расстояний использовалась в сети АКРАХЕТ вплоть до 1979 года, когда ее сменил алгоритм маршрутизации с учетом состояния линий. Отказаться от прежнего алгоритма пришлось по двум причинам. Вопервых, старый алгоритм при выборе пути не учитывал пропускную способность линий.

Пока все линии имели пропускную способность 56 Кбит/с, в учете пропускной способности не было необходимости. Однако стали появляться линии со скоростью 230 Кбит/с, а затем и 1,544 Мбит/с, и не принимать во внимание пропускную способность стало невозможно. Конечно, можно было ввести пропускную способность в качестве множителя для единицы измерения, но имелась еще н другая проблема, заключавшаяся в том, что алгоритм слишком долго приходил " устойчивому состоянию (проблема счета до бесконечности). Поэтому он был заменен полностью новым алгоритмом, который сейчас называется маршрутизацией с учетом состояния линий.

Варианты этого алгоритма широко применяются в наши дни. В основе алгоритма лежит простая идея, ее можно изложить в нлти глребованвях к маршрутизатору. Каждый маршрутизатор должен: 1. Обнаруживать своих соседей и узнавать их сетевые адреса.

Измерять задержку или стоимость связи с каждым из своих соседей, 3 Создавать пакет, содержащий всю собранную информацию. 4. Посылать этот пакет всем маршрутизаторам. Вычислять кратчайший путь ко всем маршрутизаторам. 418 Глава Ь. Сетевой уровень В результате каждому маршрутизатору высылаются полная топология и все измеренные значения задержек. После этого для обнаружения кратчайшего пути к каждому маршрутизатору может применяться алгоритм Дейкстры. Далее мы рассмотрим каждый из этих пяти этапов более подробно. Знакомство с соседями Когда маршрутизатор загружается, его первая задача состоит в получении информации о своих соседях Он достигает этой цели, посылая специальный пакет НВ.).0 по всем двухточечным линиям.

При этом маршрутизатор на другом конце линии должен послать ответ, сообшая информацию о себе, Имена маршрутизато. ров должны быть совершенно уникальными, поскольку, если удаленный маршрутизатор слышит, что три маршрутизатора являются соседями маршрутизатора Г, не должно возникать разночтений по поводу того, один и тот же маршрутизатор Р имеется в виду или нет. Когда два или более маршрутизаторов объединены в локальную сеть, ситуация несколько усложняется. На рис, 5.9, а изображена ЛВС, к которой напрямую подключены три маршрутизатора — А, С и Е Каждый из них, как показано на рисунке, соединен также с одним или несколькими дополнительными маршрутизаторами.

Маршрутизатор локальная сеть е б рис. в.в. Аееять маршрутизаторов и локальная сеть (е); грефоеея модель той же системы (б) Один из способов моделирования локальной сети состоит в том, что ЛВС рассматривается в виде узла графа, как и маршрутизаторы, Это показано на рис.

5.9, б На рисунке сеть изображена в виде искусственного узла М, с которым соединены маршрутизаторы А, С и Е Возможность передачи пакетов от А к С по локальной сети отражается здесь наличием пути АХС, Измерение стоимости линии Алгоритм маршрутизации с учетом состояния линии требует от каждого маршрутизатора знания или хотя бы обоснованной оценки задержки для всех линий связи со своими соседями. Наиболее прямой способ определить эту зздержку заключается в посылке по линии специального пакета ЯСНО, на который другая сто- Алгоритмы маршрутизации 419 рона обязана немедленно ответить.

Измерив время двойного оборота этого пакета и разделив его на два, отправитель получает приемлемую оценку задержки. Чтобы получить более точный результат, это действие можно повторить несколько раз, после чего вычислить среднее арифметическое. Конечно, такой метод предполагает, что задержки являтотся симметричными, что не всегда так. Возникает интересный вопрос: надо ли учитывать нагрузку на линию во время измерения задержкиг Чтобы учесть загруженность линии, таймер должен включаться при отправке пакета ГОНО. Чтобы игнорировать загрузку, таймер следует включать, когда пакет ГОНО достигает начала очереди. Оба способа могут быть аргументированы.

Учет трафика в линии при измерении задержки означает, что когда у маршрутизатора есть выбор между двумя линиями с одинаковой пропускной способностью, маршрут по менее загруженной линии рассматривается как более короткий, Такой выбор приведет к более сбалансированному использованию линий связи н, следовательно, к более эффективной работе системы, К сожалению, можно привести аргумент и против учета загруженности линии при расчете задержек. Рассмотрим подсеть, показанную на рис. 5.10.

Она разделена на две части — восточную и западную, которые соединены двумя линиями, СЕи ЕЕ Рис. 6.10. Подсеть, в которой восточная и западная части соединены двумя линиями Прелположим, что основная часть потока данных между востоком и западом использует линию СЕ В результате эта линия оказывается сильно загруженной и с большими задержками. учет времени стояния пакета в очередях прн подсчете кратчайшего пути сделает линию Е! более привлекательной. После установки новых таблиц маршрутизации большая часть потока данных между востоком и западом переместится на линию Е1, и ситуация повторится с точностью до смены одной линии на другую.

Аналогично, после еще одного обновления уже линия СГ окажется более привлекательной, В результате таблицы маршрутизации ' будут страдать от незатухающих колебаний, что сильно снизит эффективность 420 Глава б, Сетевой уровень работы системы. Если же нагрузку не учитывать, то зта проблема не возникнет, Можно поступать по-другому: распределять нагрузку между двумя линиями. Однако такое решение приведет к неполному использованию наилучшего пути. тем не менее, во избежание колебаний системы при выборе оптимального пути, по-видимому, лучше всего распределять нагрузку между несколькими линиями, пуская определенные части графика по каждой из них, Соаданив паквтоа состояния линий После того как информация, необходимая для обмена, собрана, следующий шаг, выполняемый каждым маршрутизатором, заключается в создании пакета, содержащего все вти данные.

Пакет начинается с идентификатора отправителя, за которым следует порядковый номер и возраст (описываемый далее), а также список соседей. Для каждого соседа указывается соответствующая ему задержка Пример подсети приведен на рис. 5.11, а, на котором показаны задержки для каждой линии. Соответствующие пакеты состояния линий для всех шести маршрутизаторов показаны на рис. 5.11, б. В 2 С Е 8 Пакеты состояния линий б Рис.

5.11. Подсеть (еп пакеты состояния линий для етой подсети (б) Создаются пакеты состояния линий несложно. Самое трудное заключается в выборе момента времени для их создания. Их можно создавать периодически через равные интервалы времени. другой вариант состоит в создании пакетов, когда происходит какое-нибудь значительное событие — например, линия или сосед выходит из строя или, наоборот, снова появляется в сети либо существен- но изменяет свои свойства. Алгоритмы маршрутизации 421 распространение пакетов состояния линий Сзмая сложная часть алгоритма заключается в распространении пакетов состояния линий.

Характеристики

Список файлов книги