Полный курс лекций 2009-го года (1130357), страница 59

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

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

Более того, она может оказаться сколь угодно долгой.Справедливость значит, что все пакеты, вне зависимости от того, из какого канала они поступили,будут обслуживаться равномерно, никакому направлению не будет отдаваться предпочтение, для всехабонентов будет всегда выбираться оптимальный маршрут. Надо отметить, что справедливость иоптимальность часто могут вступать в противоречие друг с другом. На рисунке 5-4 приведен примертакого противоречия.

Трафики между А-А', В-В', С-С' могут уже забить канал между Х-Х'. Поэтому вместократчайшего маршрута между Х и Х” надо будет выбирать какой-то другой маршрут.Рисунок 5-4. Конфликт между справедливостью и оптимальностьюПрежде чем искать компромисс между оптимальностью и справедливостью, мы должны решить, чтоявляется критерием оптимизации. Один из возможных критериев - минимизация средней задержки пакета.Другой - максимизация пропускной способности сети.

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

Уменьшение числаскачков сокращает маршрут, а следовательно, сокращает задержку, а также минимизирует потребляемуюпропускную способность при передаче пакета.Алгоритмы маршрутизации можно разбить на два больших класса: адаптивные и неадаптивные.Неадаптивные алгоритмы не принимают в расчет текущую загрузку сети и состояние топологии. Всевозможные маршруты вычисляются заранее и загружаются в маршрутизаторы при загрузке сети. Такаямаршрутизация называется статической маршрутизацией.Адаптивные алгоритмы, наоборот, определяют маршрут, исходя из текущей загрузки сети итопологии. Адаптивные алгоритмы различаются тем, где и как они получают информацию (локально отсоседних маршрутизаторов или глобально от всех), когда они меняют маршрут (каждые Т секунд, когдаменяется нагрузка, когда меняется топология), какая метрика используется при оптимизации (расстояние,число скачков, ожидаемое время передачи).5.2.1.

Принцип оптимальностиПрежде чем мы приступим к рассмотрению конкретных алгоритмов маршрутизации, сформулируемпринцип оптимальности. Этот принцип утверждает, что если маршрутизатор J находится на оптимальномпути между маршрутизаторами I и K, то оптимальный маршрут между J и K принадлежит этомуоптимальному пути.

Это так, поскольку существование между J и K оптимального маршрута, отличного отчасти маршрута между I и K, противоречил бы утверждению об оптимальности маршрута между I и K.Дело в том, что если рассмотреть маршрут от I до К, как от I до J (назовем его S1) и от J до К (назовем егоS2), то если между J и К есть маршрут лучше, чем S2, например S3, то маршрут S1S2 не может бытьлучшим. Взяв конкатенацию маршрутов S1S3, мы получим лучший маршрут, чем маршрут S1S2.Следствием из принципа оптимальности является утверждение, что все маршруты к заданной точкесети образуют дерево с корнем в этой точке.

Это дерево называется деревом захода, онопроиллюстрировано на рисунке 5-5.Рисунок 5-5. Дерево заходаПоскольку дерево захода - это дерево, то там нет циклов, поэтому каждый пакет будет доставлен законечное число шагов. На практике все может оказаться сложнее. Маршрутизаторы могут выходить изстроя, и, наоборот, появляться новые, каналы могут выходить из строя, разные маршрутизаторы могутузнавать об этих изменениях в разное время и т.д. и т.п.5.2.2. Маршрутизация по наикратчайшему путиНаше изучение алгоритмов маршрутизации мы начнем со статического алгоритма, широкоиспользуемого на практике в силу его простоты.

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

В графе с такой разметкой наикратчайший путь - наибыстрейший путь, хотя онне обязательно имеет минимальное число переходов или километров.Рисунок 5-6. Расчет кратчайшего пути от А к BВ общем случае веса на дугах могут быть функциями от расстояния, пропускной способности канала,среднего трафика, стоимости передачи, средней длины очереди в буфере маршрутизатора к данномуканалу и других факторов. Изменяя весовую функцию, алгоритм будет вычислять наикратчайший путь всмысле заданной метрики.Известно несколько алгоритмов вычисления наикратчайшего пути в графе. Один из них предложилголландский математик Эдсгер Дейкстра. Идею этого алгоритма можно описать так.

Все вершины в графе,смежные исходной вершине, помечают расстоянием (оно указано в скобках) до исходной вершины.Изначально никаких путей не известно и все вершины помечены бесконечностью. По мере работыалгоритма и нахождения путей, метки могут меняться. Метки могут быть двух видов: либо пробными, либопостоянными. Изначально все метки пробные.

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

Это позволит нам впоследствии изменить маршрут, если надо. Кроме этого, все вершины,смежные А, помечаем расстоянием от А до этой вершины. Из всех смежных вершин мы выберем ту,расстояние до которой самое короткое, и ее объявляем рабочей. Таким образом, мы выберем на первомшаге вершину В, а затем Е.Самое интересное возникнет на шаге (d). В соответствии с принципом наикратчайшего пути мы вкачестве рабочей выберем вершину G. Теперь, на шаге (е), когда мы начнем искать вершины, смежные Н,то увидим, что путь F до Н короче, чем от G до Н.

Поэтому на шаге (е) мы в качестве рабочей возьмемвершину F, а затем Н. На рисунке 5-7 дано описание алгоритма Дейкстры. Надо сделать оговорку, чтоэтот алгоритм строит наикратчайший путь, начиная от точки доставки, а не от точки отправления.Поскольку граф не ориентированный, то это никакого влияния на построение пути не оказывает.Рисунок 5-7. Алгоритм Дейкстры5.2.3. Маршрутизация лавинойДругим примером статического алгоритма может служить следующий алгоритм: каждый поступающийпакет отправляют по всем имеющимся линиям, за исключением той, по которой он поступил.

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

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

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

Тогда нетруднопостроить алгоритм, вычисляющий путь с минимальной задержкой пакета между двумя узлами.Для реализации этой идеи нам нужно о каждой транспортной среде заранее знать следующее:§топологию§матрицу трафика Fij§матрицу пропускных способностей каналов Cij§алгоритм маршрутизацииРисунок 5-8.

(а) Топология ТС с пропускной способностью в Кбит/сек.; (b)Матрица с трафиком в пакетах/сек. и маршрутомНа рисунке 5-8 показан пример: (а) – топология транспортной среды с пропускной способностьюканалов в Кбит/сек., (б) – матрица, где для каждой пары узлов (i, j) указан средний размер трафика впакетах в секунду и маршрут для этого трафика.

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

Список файлов лекций