Р.Л. Смелянский - Компьютерные сети. Том 2. Сети в ЭВМ, страница 10

2. Измерить задержку или оценить затраты на передачу до каждого соседа. 3. Сформировать пакет, где указаны все данные, полученные на шаге 2. 4. Послать этот пакет всем другим маршрутизаторам. 5. Вычислить наикратчайший маршрут до каждого маршрутизатора. Как видно из приведенного описания, топология транспортной среды и все задержки в СПД оцениваются всеми узлами экспериментально.

После этого можно использовать, например, алгоритм Дейкстры для вычисления наикратчайшего маршрута. Теперь рассмотрим подробнее эти пять шагов. Определение соседей При загрузке маршрутизатор, прежде всего, определяет, кто его непосредственные соседи. Для этого он рассылает по всем подсоединенным к нему каналам специальный пакет НЕ1.1.0, и все маршрутизаторы отвечают, указывая свое уникальное имя. Имя маршрутизатора должно быть уникальным в сети, чтобы избежать неоднозначностей. Если же два и более маршрутизаторов соединены каналом с множественным доступом, как на рис.

2.8 а, то этот канал в графе связей представляют отдельным искусственным узлом (рис. 2.8, б). Оценка затрат Оценка затрат до каждого соседа происходит с помошью другого специального пакета ЕСНО, который рассылается всем соседям, при этом замеряется задержка от момента отправки этого пакета до мо- лвс Рис. 2,8. Пример определения соседей: а — топология ТС; б — граф связей 42 -::: Рис. 2.9. Пример учета загрузки канала при маршрутизации по состоянию ',- мента его возвращения.

Все маршрутизаторы, которые получают такой пакет, обязаны отвечать незамедлительно, отправляя пакет об,,;' ратно. Такие замеры делают несколько раз и вычисляют их среднее значение. Таким образом, длина очереди к каналу не учитывается Здесь необходимо понять: следует учитывать загрузку канала или ;,. нет? Если учитывать, то задержку надо замерять от момента посту;:й: '*.

пления пакета в очередь к каналу, а если не учитывать, то — от мо'мента, когда пакет достиг головы очереди. Есть доводы и за учет за'-:- грузки, и против ее учета. При учете загрузки можно выбирать ,,", между двумя и более каналами с одинаковой пропускной способно"' стью, обеспечивая лучшую производительность Однако можно привести примеры, когда учет загрузки вызывает '., проблемы.

Например, рассмотрим рис. 2.9, где два одинаковых по производительности канала СГи Е1 соединяют две транспортные '"';-:, среды. Когда загрузка одного из этих каналов меньше, то он предло.',:,-:;; .,'гтительнее другого, что через некоторое время приводит к его перегрузке, и предпочтительнее становится другой канал. Если загрузка не учитывается, то такой проблемы не возникает Формирование пакетов состояний каналов После выполнения всех указанных измерений можно формировать пакеты состояний каналов На рис.

2ЛО, б показаны пакеты состояний каналов для примера транспортной среды, приведенной на рис. 220, и В пакетах состояний указываются: отправитель, последовательное : " '.,число, возраст (назначение этих полей станет ясно позднее), список ': ':соседей и задержки до них. Формирование таких пакетов не вызывает :: ";ззроблем. Основной вопрос здесь, когда их формировать; периодически Рис. 2.10. Пример топологии зранспортвой среды (а) и таблица состояний каналов (б) с каким-то интервалом или по особому событию, т.с. когда в транс- портной среде произошли какие-то сушественные изменения? Распространение пакетов состояний каналов Наиболее хитрая часть этого алгоритма — надежное распространение пакетов состояний каналов (далее СК-пакетов). Как только СК-пакет получен и включен в работу, маршрутизатор начинает использовать его при определении маршрута.

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

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

Первая проблема — размер поля последовательных номеров пакетов. Если это поле будет недостаточно велико, то его переполнение приведет к повтору номеров, а следовательно, к некорректной работе всего алгоритма. Решением здесь является использование достаточно большого поля, например 32-разрядного. В этом случае если обмен СК-пакетами происходит раз в секунду, потребуется 137 лет, чтобы возникло переполнение.

44 '.;:: Вторая проблема — если маршрутизатор «упал» по какой-либо причине и потерял уже использованные последовательные номера, то неясно, как их восстановить. Третья проблема — если в результате передачи возникнет ошибка в одном бите, например вместо пакета с номером 4 получим пакет с номером 65540, то все пакеты с 5-го номера по 65 540-й будут сбрасываться как устаревшие, поскольку текущий номер — 65 540.

Для решения этих проблем используется поле еВозраст» СК-пакета, .в котором устанавливается некоторое значение, уменьшающееся на ' ' единицу при каждом скачке, и, когда это значение достигнет нуля, пакет сбрасывается. В пелях сокрашения числа рассылаемых СК-пакетов их рассыла- ';" ют не сразу. Сначала полученный СК-пакет помещают в специальную - „,' область задержки, где он находится некоторое время.

Если за это .:; время придет другой пакет от того же источника, то эти пакеты срав;, 'ииваются, и если они одинаковые, то вновь пришедший пакет сбра';.:, сывается, если же они различаются, то последний пришелший пакет ;:.."дублируется и отправляется другим маршрутизаторам, а первый пакет . ': -,'сбрасывается, Все СК-пакеты передаются с уведомлением. Структура данных, используемая маршрутизатором В из примера, :.

"приведенного на рис. 2.10, а, показана на рис. 2.11 [191. Здесь каждая ;..' .строка таблицы соответствует последнему поступившему, но не до ;:.:,';конца обработанному СК-пакету. При этом лля каждого канала .:;;:маршрутизатора В указано с помощью флага, был ли соответству;:., ющий СК-пакет отправлен и подтвержден. Флаг отправления озна:,:::, . чает, что соответствующий СК-пакет должен быть послан по указан;:;;,"ному каналу.

Флаг уведомления указывает, что по соответствующей '-':.: ':линии должно прийти подтверждение. На рис. 2.11 СК-пакет от маршрутизатора А прибыл и он должен ,.;; ' быть переслан в С и в Г и подтвержден для А. Аналогичны ситуация ,з:с СК-пакетом, поступившим от Г. Существенно отличается ситуация .: .:с маршрутизатором Е, от которого поступило два СК-пакета: один Флаги Флаги отпряв- уведомления ленив Источник Номер Данные Возраст А С Р А С т Рис, 2.11.

Буфер пакетов для маршрутизатора В из зтримера, приведенного на рис. 2.10, и по маршруту ЕАВ, а лругой по маршруту ЕГВ. Следовательно, СК- пакет должен быть послан только в С, а вот уведомления должны быть посланы и в А, и в Г. Наличие дубликатов СК-пакетов легко распознать по состоянию флагов отправки. Вычисление нового пути Когда маршрутизатор получил полный комплект СК-пакетов, он может построить топологию транспортной среды и, например, локально запустить алгоритм Дейкстры для вычисления наикратчайшего пути. В системе, где есть п маршрутизаторов, имеющих по 1с линий, у каждого из этих маршрутизаторов должно быть достаточно памяти для хранения необходимой информации о сети.

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