tanenbaum_seti_all.pages (525408), страница 111
Текст из файла (страница 111)
Самой большой популярностью пользуются два метода: маршрутизация по вектору расстояний и маршрутизация с учетом состояния каналов. В этом разделе мы изучим первый, в следующем — второй метод. 414 Глава 5, Сетевой уровень Алгоритмы маршрутизации по вектору расстояний работают, опираясь на таблицы (то есть векторы), поддерживаемые всеми маршрутизаторами и содержащие наилучшие известные пути к каждому из возможных адресатов. Для обновления данных этих таблиц производится обмен информацией с соседними маршрутизаторами. Алгоритм маршрутизации по вектору расстояний иногда называют по именам его создателей распределенным алгоритмом Беллмана-Форда (ВеПглап — Рогб) и алгоритмом Форда-Фулкерсона (Рогд-РцПсегзоп), (Вейшап, 1957; Рогд апб Рйкегзоп, 1962).
Этот алгоритм изначально применялся в сети АЕРАХЕТ и в Интернете был известен под названием Е1Р. При маршрутизации по вектору расстояний таблицы, с которыми работают и которые обновляют маршрутизаторы, содержат записи о каждом маршрутизаторе подсети. Каждая запись состоит из двух частей: предпочитаемого номера линии для данного получателя и предполагаемого расстояния или времени прохождения пакета до этого получателя.
В качестве единиц измерения может использоваться число транзитных участков, миллисекунды, число пакетов, ожидающих в очереди в данном направлении, или еще что-нибудь подобное. Предполагается, что маршрутизаторам известно расстояние до каждого из соседей. Если в качестве единицы измерения используется число транзитных участков, то расстояние равно одному транзитному участку. Если же дистанция измеряется временем задержки, то маршрутизатор может измерить его с помощью специального пакета ЕНО (эхо), в который получатель помещает время получения и который отправляет обратно как можно быстрее. Предположим, что в качестве единицы измерения используется время задержки, и этот параметр относительно каждого из соседей известен маршрутизатору.
Через каждые Т миллисекунды все маршрутизаторы посылают своим соседям список с приблизительными задержками для каждого получателя. Они, разумеется, также получают подобный список от всех своих соседей. Допустим, одна из таких таблиц пришла от соседа Х, и в ней указывается, что время распространения от маршрутизатора Х до маршрутизатора 1 равно Хг Если маршрутизатор знает, что время пересылки до маршрутизатора Х равно т, тогда задержка при передаче пакета маршрутизатору 1 через маршрутизатор Х составит Х,, + ш. Выполнив такие расчеты для всех своих соседей, маршрутизатор может выбрать наилучшие пути и поместить соответствующие записи в новую таблицу.
Обратите внимание на то, что старая таблица в расчетах не используется. Процесс обновления таблицы проиллюстрирован на рис. 5.7. Слева показана подсеть (рис. 5.7, а). Первые четыре столбца на рис. 5.7, б показывают векторы задержек, полученные маршрутизатором / от своих соседей. Маршрутизатор А считает, что время пересылки от него до маршрутизатора В равно 12 мс, 25 мс— до маршрутизатора С, 40 мс — до Р и т. д.
Предположим, что маршрутизатор/ измерил или оценил задержки до своих соседей А, Т, Н и К как 8, 10, 12 и 6 мс соответственно. Теперь рассмотрим, как/ рассчитывает свой новый маршрут к маршрутизатору С. Он знает, что задержка до А составляет 8 мс, а А думает, что от него до С Алгоритмы маршрутизации 415 Новая расчетная задержка для,/ Маршрутизатор в зас в К т Линия к я Я в с 0 Е 8 Н ! К Задержка Задержка Задержка Задержка ,тя ш ~н ж равна З равна 10 равна 12 равна б Новая таблица маршрутов для ц Векторы, полученные от четырех соседей,/ Рис.
В.т. Подсеть (а); полученные от Я, А Н и К векторы и новая таблица маршрутов для,/(б) Проблема счета до бесконечности Алгоритм маршрутизации по вектору расстояний работает в теории, но обладает серьезным недостатком на практике: хотя правильный ответ в конце концов и находится, процесс его поиска может занять довольно много времени.
В частности, такой алгоритм быстро реагирует на хорошие новости и очень лениво — на плохие. Рассмотрим маршрутизатор, у которого задержка до маршрутизатора Х велика. Если при очередном обмене векторами его сосед сообщит ему, что от него до маршрутизатора Х совсем недалеко, наш маршрутизатор просто переключится для передач маршрутизатору Х на линию, проходящую через этого соседа. Таким образом, хорошая новость распространилась всего за один обмен информацией.
данные дойдут за 18 мс. Таким образом,,7 знает, что если он станет отправлять пакеты для С через А, то задержка составит 26 мс. Аналогично он вычисляет значения задержек для маршрутов от него до С, проходяшнх через остальных его соседей (й Н и 7(), и получает соответственно 41 (31+ 10), 18 (6+ 12) и 37 (31+ 6), Дучшим значением является 18, поэтому именно оно помещается в таблицу в запись для получателя С.
Вместе с числом 18 туда же помещается обозначение линии, по которой проходит самый короткий маршрут до С, то есть Н. Данный мбтод повторяется для всех остальных адресатов, и при этом получается новая таблица, показанная в виде правого столбца на рисунке. 416 Глава 5.
Сетевой уровень Чтобы увидеть, как быстро распространяются хорошие известия, рассмотрим линейную подсеть из пяти узлов, показанную на рис. 5.8, в которой мерой расстояния служит количество транзитных участков. Предположим, что вначале маршрутизатор А выключен и все остальные маршрутизаторы об этом знают. То есть они считают, что расстояние до А равно бесконечности. А В С 0 Е А В С 0 Е 4 Вначале 4 Послв1обмвнв 4 Посла 2 обманов 4 После 3 обменов 6 Посла 4 обменов 8 После б обменов 8 Послв 6 обменов ° Вначале ° Посла 1 обмена ° После 2 обменов ° Паслв 3 обменов 4 Послв 4 обменов 1 2 3 3 2 3 3 4 3 б 4 6 6 6 6 7 6 7 7 8 7 ° ° ° 1 1 2 1 2 3 1 2 3 ° ° ° ° Рис.
6.8. Проблема счета до бесконечности Когда в сети появляется А, остальные маршрутизаторы узнают об этом с помощью обмена векторами. Для простоты будем предполагать, что где-то в сети имеется гигантский гонг, в который периодически ударяют, чтобы инициировать одновременный обмен векторами. После первого обмена В узнает, что у его соседа слева нулевая задержка при связи с А, а В помечает в своей таблице маршрутов, что А находится слева ца расстоянии одного транзитного участка. Все остальные маршрутизаторы в этот момент еще полагают, что А выключен. Значения задержек для А в таблицах на этот момент показаны во второй строке на рис. 5.8, а. При следующем обмене информацией С узнает, что у В есть путь к А длиной 1, поэтому он обновляет свою таблицу, указывая длину пути до А, равную 2, по Р и Е об этом еще не знают.
Таким образом, хорошие вести распространяются со скоростью один транзитный участок за один обмен векторами. Если самый длинный путь в подсети состоит из Х транзитных участков, то через ту обменов все маршрутизаторы подсети будут знать о включенных маршрутизаторах и заработавших линиях. Теперь рассмотрим ситуацию на рис.
5.8, б, в которой все линии и маршрутизаторы изначально находятся во включенном состоянии. МаршрутизатоРы В, С, Р и Е находятся от А на расстоянии 1, 2, 3 и 4 соответственно. Внезапно А отключается или, возможно, происходит обрыв линии между А и В, что с точки зрения В одно и то же.
При первом обмене пакетами В не слышит ответа от А. К счастью, С говорит: чНе волнуйся. У меня есть путь к А длиной 2». В не знает, что путь от С к А проходит через В. В может только предполагать, что у С около 10 выходных линий с независимыми путями к А, кратчайшая из которых имеет длину 2. Поэтому теперь В думает, что может связаться с А через С по пути длиной 3. При этом первом обмене маршрутизаторы Р и Е не обновляют свою информацию об А. Алгоритмы маршрутизации 417 При втором обмене векторами С замечает, что у всех его соседей есть путь к А длиной 3. Он выбирает один из них случайным образом и устанавливает свое расстояние до 4 равным 4, как показано в третьей строке на рис.
5.8, б. Результаты последующих обменов векторами также показаны на этом рисунке. Теперь должно быть понятно, почему плохие новости медленно распространяются — ни один маршрутизатор не может установить значение расстояния, более чем на единицу превышающее минимальное значение этого расстояния, хранящееся у его соседей. Таким образом, все маршрутизаторы будут до бесконечности увеличивать значение расстояния до выключенного маршрутизатора. Количество необходимых для завершения этого процесса обменов векторами можно ограничить, если установить значение этой «бесконечности» равным длине самого длинного пути плюс 1.
Если расстояния в подсети измеряются во временных задержках, такую верхнюю границу выбрать сложнее. Следует выбирать достаточно большое ограничивающее значение, чтобы линия с большой задержкой ие была сочтена совсем не работающей. Неудивительно, что зта проблема называется счетом до бесконечности. Было сделано несколько попыток решить ее (например, алгоритм расколотого горизонта, весьма бесполезный во многих случаях, но внесенный в ВЕС 1058), но все они оказались безуспешными.
Суть проблемы заключается в том, что когда Х сообщает У о том, что у него есть какой-то нуть, у У нет никакой возможности узнать, входит ли он сам в этот путь. Маршрутизация с учетом состояния линий Маршрутизация на основе векторов расстояний использовалась в сети АВРАХЕТ вплоть до 1979 года, когда ее сменил алгоритм маршрутизации с учетом состояния линий. Отказаться от прежнего алгоритма пришлось по двум причинам. Вопервых, старый алгоритм при выборе пути не учитывал пропускную способность линий.
Пока все линии имели пропускную способность 56 Кбит/с, з учете пропускной способности не было необходимости, Однако стали появляться линии со скоростью 230 Кбит/с, а затем и 1,544 Мбит/с, и не принимать во внимание пропускную способность стало невозможно. Конечно, можно было ввести пропускную способность в качестве множителя для единицы измерения, но имелась еще и другая проблема, заключавшаяся в том, что алгоритм слишком долго приходил к устойчивому состоянию (проблема счета до бесконечности), Поэтому он был заменен полностью новым алгоритмом, который сейчас называется маршрутизацией с учетом состояния линий. Варианты этого алгоритма широко применяются в наши дни. В основе алгоритма лежит простая идея, ее можно изложить в пяти требованиях к маршрутизаглору. Каждый маршрутизатор должен: 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
