Nets2010 (1131259), страница 39

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 39)

Каждые Т секунд маршрутизатор шлет своим соседям свой вектор задержек до всех маршрутизаторов в подсети. В свою очередь, он получает такие же вектора от своих соседей. Кроме этого, он постоянно замеряет задержки до своих соседей. Поэтому, имея вектора расстояний от соседей и зная расстояние до них, маршрутизатор всегда может вычислить кратчайший маршрут до определенного места в транспортной среде.

Рассмотрим пример на рисунке 5-10. На рисунке 5-10 (а) показана подсеть. На рисунке 5-10 (b) показаны вектора, которые маршрутизатор J получил от своих соседей, и его замеры задержек до них. Там же показана итоговая таблица маршрутизации, которую J вычислит на основании этой информации.

Рассмотрим, как маршрутизатор J с помощью этой таблицы вычислит маршрут до G. J знает, что он может достичь А за 8 мсек., А объявляет, что от него до G 18 мсек. Таким образом, J может достичь G за 26 мсек. через A. Аналогично можно подсчитать, что достичь G через I, H и K можно за 41 (31+10), 18 (6+12) и 37 (31+6) мсек. соответственно. Наилучшее значение – 18, поэтому это и есть наилучший маршрут.

Рисунок 5-10. Маршрутизация по вектору расстояния

Алгоритм маршрутизации по вектору расстояния теоретически работает хорошо, но у него есть один недостаток: он очень медленно реагирует на разрушения каналов в транспортной среде. Информация о появлении хорошего маршрута в подсети распространяется более или менее быстро, а вот данные о потере, разрушении какого-то маршрута распространяются не столь быстро.

Одним из решений этой проблемы является следующий прием. Алгоритм работает так, как было описано, но при передаче вектора по линии, по которой направляются пакеты для маршрутизатора Х, т.е. по которой достижим маршрутизатор Х, расстояние до Х указывается как бесконечность.

Однако и в алгоритме разделения направлений есть «дыры». Рассмотрим подсеть на рисунке 5-12. Если линия между С и D будет разрушена, то С сообщит об этом А и В. Однако А знает, что у В есть маршрут до D, а В знает, что такой маршрут есть и у А. И опять мы «сваливаемся» в проблему бесконечного счетчика.

Рисунок 5-12. Случай, при котором разделение направлений не помогает

Маршрутизация по состоянию канала.

Алгоритм маршрутизации по вектору расстояний использовался в сети ARPANET до 1979 года, после чего он был заменен. Тому было две основных причины. Первая - пропускная способность канала никак не учитывалась, поскольку основной мерой задержки была длина очереди. Вторая проблема – медленная сходимость алгоритма при изменениях. По этим причинам был создан новый алгоритм маршрутизации по состоянию канала.

Основная идея построения этого алгоритма проста и состоит из пяти основных шагов:

1. Определить своих соседей и их сетевые адреса.

2. Измерить задержку или оценить затраты на передачу до каждого соседа.

3. Сформировать пакет, где указаны все данные, полученные на шаге 2.

4. Послать этот пакет всем другим маршрутизаторам.

5. Вычислить наикратчайший маршрут до каждого маршрутизатора.

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

При загрузке маршрутизатор прежде всего определяет, кто его соседи. Для этого он рассылает по всем своим линиям точка-точка специальный пакет HELLO. В ответ все маршрутизаторы отвечают, указывая свое уникальное имя. Имя маршрутизатора должно быть уникальным в сети, чтобы избежать неоднозначностей. Если же два и более маршрутизатора соединены одним каналом, как на рисунке 5-13 (а), то этот канал в графе связей представляют отдельным, искусственным узлом (рисунок 5-13 (b)).

Рисунок 5-13. Определение соседей

Оценка затрат до каждого соседа происходит с помощью другого специального пакета EСHO. Это пакет рассылается всем соседям, при этом замеряется задержка от момента отправки этого пакета до момента его возвращения. Все, кто получает такой пакет, обязаны отвечать незамедлительно. Такие замеры делают несколько раз и вычисляют среднее значение. Таким образом, длина очереди к каналу не учитывается.

Здесь есть одна тонкость: учитывать загрузку в канале или нет? Если учитывать, то задержку надо замерять от момента поступления пакета в очередь к каналу. Если не учитывать, то от момента, когда пакет достиг головы очереди. Есть доводы, как в пользу учета нагрузки, так и против такого учета.

После того как измерения выполнены, можно сформировать пакет о состоянии каналов. На рисунке 5-14 показаны пакеты для примера сети. В пакете указаны: отправитель, последовательное число, возраст (назначение этих полей станет ясно позднее), список соседей и задержки до них. Формирование таких пакетов не вызывает проблем. Основной вопрос - когда их формировать? Периодически, с каким-то интервалом, или по особому событию, когда в транспортной подсети произошли какие-то существенные изменения?

Рисунок 5-14. Формирование пакетов состояния канала

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

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

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

Вторая проблема: если маршрутизатор «упал» по какой-либо причине и потерял последовательность использованных последовательных номеров, то неясно, как ее восстановить.

Третья – если в результате передачи возникнет ошибка в одном бите, например, вместо 4 получим пакет с номером 65540, то все пакеты с 5 по 65540 будут сбрасываться как устаревшие, поскольку текущий номер - 65540.

Для решения этих проблем используется поле «возраст» СК-пакета. Там устанавливается некоторая величина, которая уменьшается периодически на единицу каждую секунду. Когда она достигнет нуля, пакет сбрасывается.

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

Структура данных, используемая маршрутизатором В из примера на рисунке 5-14 (a), показана на рисунке 5-15. Каждая строка в этой таблице соответствует последнему поступившему, но не до конца обработанному СК-пакету. В этой таблице для каждой линии маршрутизатора В указано в виде флага, был ли соответствующий СК-пакет отправлен и подтвержден. Флаг отправления означает, что соответствующий СК-пакет должен быть послан по указанной линии. Флаг уведомления указывает на то, что по соответствующей линии должно прийти подтверждение.

Рисунок 5-15. Буфер пакетов для маршрутизатора В из рисунка 5-14

На рисунке 5-15 СК-пакет от А прибыл и должен быть переслан в С и F и подтвержден по А. Аналогичная ситуация с СК-пакетом от F. Существенно отличная ситуация с СК-пакетом от Е. От Е поступило два пакета. Один - по маршруту ЕАВ, другой – по маршруту EFB. Следовательно, СК-пакет должен быт послан только к С, а вот уведомления должны быть посланы и А, и F. Наличие дубликатов СК-пакетов легко распознать по состоянию флагов отправки.

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

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

Маршрутизация по состоянию каналов широко используется в реальных сетях.

Иерархическая маршрутизация.

По мере роста транспортной среды размер таблиц, т.е. затраты памяти, время процессора на обработку этих таблиц, пропускная способность каналов, затрачиваемая на передачу служебной информации, может превысить разумные пределы. Таким образом, дальнейший рост сети, когда каждый маршрутизатор знает все о каждом другом маршрутизаторе, будет невозможен. Решение этой проблемы – иерархия сетей, подобно иерархии коммутаторов в телефонной сети.

На рисунке 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-17 показана модель WAN с мобильным узлом. Всех пользователей мы можем разделить на две большие группы. Стационарные - это большая группа, их компьютеры подключены к сети стационарными средствами (проводами, кабелями) и редко меняют свое место положение. Другая группа постоянно меняет свое местоположение и стремится поддерживать связь с сетью. Этих пользователей мы будем называть мобильными.

Рисунок 5-17. Модель WAN с мобильным узлом

Характеристики

Список файлов ответов (шпаргалок)