Лекции 2010-го года (1130544), страница 61
Текст из файла (страница 61)
Определение соседейПри загрузке маршрутизатор прежде всего определяет, кто его соседи. Для этого онрассылает по всем своим линиям точка-точка специальный пакет HELLO. В ответ всемаршрутизаторы отвечают, указывая свое уникальное имя. Имя маршрутизатора должнобыть уникальным в сети, чтобы избежать неоднозначностей. Если же два и болеемаршрутизатора соединены одним каналом, как на рисунке 5-13 (а), то этот канал в графесвязей представляют отдельным, искусственным узлом (рисунок 5-13 (b)).Рисунок 5-13.
Определение соседей175.2.6.2. Оценка затратОценка затрат до каждого соседа происходит с помощью другого специального пакетаEСHO. Это пакет рассылается всем соседям, при этом замеряется задержка от моментаотправки этого пакета до момента его возвращения. Все, кто получает такой пакет,обязаны отвечать незамедлительно. Такие замеры делают несколько раз и вычисляютсреднее значение. Таким образом, длина очереди к каналу не учитывается.Здесь есть одна тонкость: учитывать загрузку в канале или нет? Если учитывать, тозадержку надо замерять от момента поступления пакета в очередь к каналу. Если неучитывать, то от момента, когда пакет достиг головы очереди. Есть доводы, как в пользуучета нагрузки, так и против такого учета.
Учитывая нагрузку, мы можем выбирать междудвумя и более каналами с одинаковой пропускной способностью, получая лучшуюпроизводительность. Однако можно привести примеры, когда ее учет вызывает проблемы.Например, рассмотрим рисунок 5-13 (с). Здесь два одинаковых по производительностиканала CF и EI соединяют две сети. Если на одном из них нагрузка меньше, топредпочтительнее будет другой, что через некоторое время приведет к его перегрузке ипредпочтительнее должен стать первый. Если нагрузка не учитывается, то этой проблемыне возникает.Рисунок 5-13 (с).
Определение затрат5.2.6.3. Формирование пакета состояния каналаПосле того как измерения выполнены, можно сформировать пакет о состоянии каналов.На рисунке 5-14 показаны пакеты для примера сети. В пакете указаны: отправитель,последовательное число, возраст (назначение этих полей станет ясно позднее), списоксоседей и задержки до них.
Формирование таких пакетов не вызывает проблем. Основнойвопрос - когда их формировать? Периодически, с каким-то интервалом, или по особомусобытию, когда в транспортной подсети произошли какие-то существенные изменения?Рисунок 5-14. Формирование пакетов состояния канала185.2.6.4. Распространение пакетов состояния каналовНаиболее хитрая часть этого алгоритма – как надежно распространить пакеты о состоянииканалов (СК-пакеты)? Как только СК-пакет получен и включен в работу, маршрутизаторбудет его использовать при определении маршрута. При неудачном распространении СКпакетов разные маршрутизаторы могут получить разное представление о топологиитранспортной среды, что может приводить к возникновению циклов, недостижимыхмашин и другим проблемам.Сначала рассмотрим базовый алгоритм, потом некоторые его усовершенствования.
СКпакеты распространяются методом лавины, т.е. СК-пакет рассылается всем соседям, те, всвою очередь, своим соседям, и т.д. Однако, чтобы не потерять контроль и не вызватьнеограниченное дублирование СК-пакетов, каждый маршрутизатор ведет счетчикпоследовательных номеров СК-пакетов, которые он сгенерировал. Все маршрутизаторызапоминают пары «маршрутизатор, последовательное число», которые они уже встречалисреди полученных СК-пакетов. Если поступивший СК-пакет содержит пару, которая ещене встречалась маршрутизатору, то он отправляет этот СК-пакет всем своим соседям, заисключением того, от которого он его получил.
Если он уже встречал такой пакет, топакет сбрасывается и никуда не дублируется.У этого алгоритма есть несколько проблем, но все они разрешимые. Первая: размер поляпоследовательных номеров пакетов. Если оно будет недостаточно длинное, то егопереполнение приведет к повтору номеров, что, в свою очередь, приведет к некорректнойработе всего алгоритма. Решением является достаточно большое поле, например, 32разрядное. При таком поле, если обмен СК-пакетами происходит раз в секунду, топотребуется 137 лет, чтобы возникло переполнение.Вторая проблема: если маршрутизатор «упал» по какой-либо причине и потерялпоследовательность использованных последовательных номеров, то неясно, как еевосстановить.Третья – если в результате передачи возникнет ошибка в одном бите, например, вместо 4получим пакет с номером 65540, то все пакеты с 5 по 65540 будут сбрасываться какустаревшие, поскольку текущий номер - 65540.Для решения этих проблем используется поле «возраст» СК-пакета.
Там устанавливаетсянекоторая величина, которая уменьшается периодически на единицу каждую секунду.Когда она достигнет нуля, пакет сбрасывается.В целях сокращения числа рассылаемых СК-пакетов, когда такой пакет поступает, его несразу дублируют и отправляют. Сначала его помещают в специальную область задержки.Там он находится некоторое время. Если за это время придет другой пакет от того жеисточника, то пакеты сравниваются. Если нет различий между ними, то вновь пришедший19сбрасывается, если есть, то последний пришедший дублируется и отправляется другим, апервый сбрасывается. Все СК-пакеты передаются с уведомлением.Структура данных, используемая маршрутизатором В из примера на рисунке 5-14 (a),показана на рисунке 5-15.
Каждая строка в этой таблице соответствует последнемупоступившему, но не до конца обработанному СК-пакету. В этой таблице для каждойлинии маршрутизатора В указано в виде флага, был ли соответствующий СК-пакетотправлен и подтвержден. Флаг отправления означает, что соответствующий СК-пакетдолжен быть послан по указанной линии. Флаг уведомления указывает на то, что посоответствующей линии должно прийти подтверждение.Рисунок 5-15.
Буфер пакетов для маршрутизатора В из рисунка 5-14На рисунке 5-15 СК-пакет от А прибыл и должен быть переслан в С и F и подтвержден поА. Аналогичная ситуация с СК-пакетом от F. Существенно отличная ситуация с СКпакетом от Е. От Е поступило два пакета. Один - по маршруту ЕАВ, другой – по маршрутуEFB.
Следовательно, СК-пакет должен быт послан только к С, а вот уведомления должныбыть посланы и А, и F. Наличие дубликатов СК-пакетов легко распознать по состояниюфлагов отправки.5.2.6.5. Вычисление нового путиКогда маршрутизатор получил полный комплект СК-пакетов, он может построитьтопологию транспортной среды и, например, локально запустить алгоритм Дейкстры длявычисления наикратчайшего пути.В системе, где есть n маршрутизаторов с k линий у каждого, каждый маршрутизатордолжен иметь достаточно памяти, чтобы хранить необходимую информацию о сети. Прибольших n эта величина может стать существенной.
Кроме этого, в сетях, где числомаршрутизаторов достигает десятков или сотен тысяч, проблемы, вызванные сбоемодного из них, могут оказаться весьма серьезными. Например, если из-за сбоя вмаршрутизаторе послан неправильный СК-пакет или неправильно оценено состояниеканала, то в дальнейшем это может привести к проблемам.Маршрутизация по состоянию каналов широко используется в реальных сетях. Например,в протоколе OSPF, который мы будем подробно рассматривать позже.Другим важным примером может служить протокол IS-IS, который был изначальнопредложен фирмой DEC, а позже адаптирован ISO.
IS-IS широко используется вИнтернете. Поскольку OSPF появился позже IS-IS, он вобрал в себя всеусовершенствования, сделанные для IS-IS. Основное различие между ними в том, что IS20IS может работать с разными протоколами сетевого уровня, что делает его весьмапривлекательным при маршрутизации между разнотипными сетями, чего не может делатьOSPF.5.2.7. Иерархическая маршрутизацияПо мере роста транспортной среды размер таблиц, т.е.
затраты памяти, время процессорана обработку этих таблиц, пропускная способность каналов, затрачиваемая на передачуслужебной информации, может превысить разумные пределы. Таким образом,дальнейший рост сети, когда каждый маршрутизатор знает все о каждом другоммаршрутизаторе, будет невозможен. Решение этой проблемы – иерархия сетей, подобноиерархии коммутаторов в телефонной сети.На рисунке 5-16 (а) приведен пример сети с двухуровневой иерархией из пяти регионов.Здесь каждый из регионов соединен с двумя другими.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
