Полный курс лекций 2009-го года (1130357), страница 61
Текст из файла (страница 61)
Однако можно привести примеры, когда ее учетвызывает проблемы. Например, рассмотрим рисунок 5-13 (с). Здесь два одинаковых попроизводительности канала CF и EI соединяют две сети. Если на одном из них нагрузка меньше, топредпочтительнее будет другой, что через некоторое время приведет к его перегрузке и предпочтительнеедолжен стать первый. Если нагрузка не учитывается, то этой проблемы не возникает.Рисунок 5-13 (с). Определение затрат5.2.6.3. Формирование пакета состояния каналаПосле того как измерения выполнены, можно сформировать пакет о состоянии каналов.
Нарисунке 5-14 показаны пакеты для примера сети. В пакете указаны: отправитель, последовательноечисло, возраст (назначение этих полей станет ясно позднее), список соседей и задержки до них.Формирование таких пакетов не вызывает проблем. Основной вопрос - когда их формировать?Периодически, с каким-то интервалом, или по особому событию, когда в транспортной подсети произошликакие-то существенные изменения?Рисунок 5-14. Формирование пакетов состояния канала5.2.6.4. Распространение пакетов состояния каналовНаиболее хитрая часть этого алгоритма – как надежно распространить пакеты о состоянии каналов(СК-пакеты)? Как только СК-пакет получен и включен в работу, маршрутизатор будет его использоватьпри определении маршрута. При неудачном распространении СК-пакетов разные маршрутизаторы могутполучить разное представление о топологии транспортной среды, что может приводить к возникновениюциклов, недостижимых машин и другим проблемам.Сначала рассмотрим базовый алгоритм, потом некоторые его усовершенствования.
СК-пакетыраспространяются методом лавины, т.е. СК-пакет рассылается всем соседям, те, в свою очередь, своимсоседям, и т.д. Однако, чтобы не потерять контроль и не вызвать неограниченное дублирование СКпакетов, каждый маршрутизатор ведет счетчик последовательных номеров СК-пакетов, которые онсгенерировал. Все маршрутизаторы запоминают пары «маршрутизатор, последовательное число», которыеони уже встречали среди полученных СК-пакетов. Если поступивший СК-пакет содержит пару, котораяеще не встречалась маршрутизатору, то он отправляет этот СК-пакет всем своим соседям, за исключениемтого, от которого он его получил. Если он уже встречал такой пакет, то пакет сбрасывается и никуда недублируется.У этого алгоритма есть несколько проблем, но все они разрешимые. Первая: размер поляпоследовательных номеров пакетов.
Если оно будет недостаточно длинное, то его переполнение приведетк повтору номеров, что, в свою очередь, приведет к некорректной работе всего алгоритма. Решениемявляется достаточно большое поле, например, 32-разрядное. При таком поле, если обмен СК-пакетамипроисходит раз в секунду, то потребуется 137 лет, чтобы возникло переполнение.Вторая проблема: если маршрутизатор «упал» по какой-либо причине и потерял последовательностьиспользованных последовательных номеров, то неясно, как ее восстановить.Третья – если в результате передачи возникнет ошибка в одном бите, например, вместо 4 получимпакет с номером 65540, то все пакеты с 5 по 65540 будут сбрасываться как устаревшие, посколькутекущий номер - 65540.Для решения этих проблем используется поле «возраст» СК-пакета. Там устанавливается некотораявеличина, которая уменьшается периодически на единицу каждую секунду.
Когда она достигнет нуля,пакет сбрасывается.В целях сокращения числа рассылаемых СК-пакетов, когда такой пакет поступает, его не сразудублируют и отправляют. Сначала его помещают в специальную область задержки. Там он находитсянекоторое время. Если за это время придет другой пакет от того же источника, то пакеты сравниваются.Если нет различий между ними, то вновь пришедший сбрасывается, если есть, то последний пришедшийдублируется и отправляется другим, а первый сбрасывается.
Все СК-пакеты передаются с уведомлением.Структура данных, используемая маршрутизатором В из примера на рисунке 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. Основное различие междуними в том, что IS-IS может работать с разными протоколами сетевого уровня, что делает его весьмапривлекательным при маршрутизации между разнотипными сетями, чего не может делать OSPF.5.2.7. Иерархическая маршрутизацияПо мере роста транспортной среды размер таблиц, т.е.
затраты памяти, время процессора наобработку этих таблиц, пропускная способность каналов, затрачиваемая на передачу служебнойинформации, может превысить разумные пределы. Таким образом, дальнейший рост сети, когда каждыймаршрутизатор знает все о каждом другом маршрутизаторе, будет невозможен. Решение этой проблемы –иерархия сетей, подобно иерархии коммутаторов в телефонной сети.На рисунке 5-16 (а) приведен пример сети с двухуровневой иерархией из пяти регионов. Здеськаждый из регионов соединен с двумя другими. На рисунке 5-16 (b) показана полная таблицамаршрутизации для маршрутизатора 1А без иерархии.
На рисунке 5-16 (с) – та же таблица придвухуровневой иерархии. Нетрудно видеть, что таблица маршрутизации во втором случае резкосократилась.Рисунок 5-16. Иерархическая маршрутизацияОднако за эту экономию приходится платить эффективностью маршрутизации. Например, наилучшиймаршрут от 1А к 5С проходит через регион 2, однако в данном случае он пройдет через регион 3,поскольку большинство машин в регионе 5 действительно эффективнее достигнуть через регион 3.При построении иерархии возникает сразу несколько вопросов.
Один из них: сколько уровнейдолжно быть в иерархии при заданном размере сети? Например, если наша транспортная среда содержит920 маршрутизаторов, то без иерархии таблица каждого будет иметь 920 строк. Если транспортную средуразбить на 40 регионов, то размер таблиц будет равен 23 строки для маршрутизации внутри региона плюс40 для маршрутизации между регионами. Если использовать трехуровневую иерархию и объединитьрегионы в кластеры, то при 5 кластерах, по 8 регионов с 23 маршрутизаторами в каждом у таблицы будет23 входа для внутрикластерной маршрутизации, плюс 7 входов для межкластерной, плюс 5 входов длямежрегиональной маршрутизации.
Итого 35 входов.Клейнрок и Камоун показали, что оптимальное число уровней иерархии в транспортной среде при Nузлах будет равняться lnN, при e*lnN строках в таблице маршрутизатора.5.2.8. Маршрутизация для мобильного узлаМиллионы людей в наши дни путешествуют, находятся в командировках. Многим из них простонеобходимо иметь доступ к своей электронной почте, файловой системе. Так мы приходим к проблемемобильного узла, которую мы уже отмечали. Это относительно новая проблема, но, несмотря на это, онастоит довольно остро.На рисунке 5-17 показана модель WAN с мобильным узлом. Всех пользователей мы можемразделить на две большие группы.
Стационарные - это большая группа, их компьютеры подключены ксети стационарными средствами (проводами, кабелями) и редко меняют свое место положение. Другаягруппа постоянно меняет свое местоположение и стремится поддерживать связь с сетью. Этихпользователей мы будем называть мобильными.Рисунок 5-17. Модель WAN с мобильным узломПредполагается, что в сети каждый пользователь имеет постоянное домашнее местоположение,которое никогда не меняется.
Проблема маршрутизации в этих условиях заключается в том, чтобыпосылать пакеты мобильному пользователю через его домашнее местоположение. При этом то, гденаходится сам пользователь, не имеет значения. Вся WAN на рисунке 5-17 разбивается на области. Вкаждой области есть агент визитеров, который знает о всех мобильных пользователях в своей области. Всвою очередь, в каждой области есть домашний агент, который знает обо всех стационарныхпользователях в своей области, которые в настоящий момент путешествуют.Как только мобильный узел подключается к местной, локальной сети, он регистрируется у агентавизитеров. Эта процедура примерно выглядит так:1.Периодически агент визитеров рассылает по своей области пакет, где указано местоположение этогоагента и его адрес. Если мобильный узел, подключившись к сети, долго не видит такого пакета, онрассылает свой пакет с просьбой агенту визитеров объявить свои координаты.2.Мобильный узел регистрируется у агента визитеров, указывая свое текущее местоположение, домашнееместоположение и определенную информацию, связанную с безопасностью передаваемых данных.3.Агент визитеров обращается через сеть к домашнему агенту домашнего местоположения визитера,указывая, что один из его пользователей сейчас находится в его области, передавая конфиденциальнуюинформацию, которая должна убедить домашнего агента, что это действительно его пользовательпытается соединиться с ним.4.Домашний агент изучает конфиденциальные данные, время связи.
Если эти данные соответствуют тойинформации, что есть у домашнего агента об этом пользователе, он дает добро на связь.5.Агент визитеров, получив подтверждение от домашнего агента, заносит данные о мобильном узле в своитаблицы и регистрирует его.В идеале пользователь, покидая область визита, должен закрыть свою временную регистрацию.Однако, как правило, закончив сеанс связи, пользователь просто выключает свой компьютер и все.Поэтому, если по прошествии некоторого времени пользователь не объявился вновь, агент визитеровсчитает его покинувшим область.Рассмотрим теперь, что происходит, когда кто-то посылает сообщения мобильному узлу (рисунок 518). Пакет поступает на адрес домашнего местоположения пользователя, где его перехватывает домашнийагент.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
