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