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

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

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

Алгоритм маршрутизации должен обладать рядом свойств:

• корректностью

• простотой

• устойчивостью

• стабильностью

• справедливостью

• оптимальностью.

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

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

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

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

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

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

Принцип оптимальности: если маршрутизатор J находится на оптимальном пути между маршрутизаторами I и K, то оптимальный маршрут между J и K принадлежит этому оптимальному пути.

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

Рисунок 5-5. Дерево захода

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

Маршрутизация по наикратчайшему пути.

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

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

Рисунок 5-6. Расчет кратчайшего пути от А к B

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

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

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

Самое интересное возникнет на шаге (d). В соответствии с принципом наикратчайшего пути мы в качестве рабочей выберем вершину G. Теперь, на шаге (е), когда мы начнем искать вершины, смежные Н, то увидим, что путь F до Н короче, чем от G до Н. Поэтому на шаге (е) мы в качестве рабочей возьмем вершину F, а затем Н.

Маршрутизация лавиной.

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

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

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

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

Рассмотрим статический алгоритм маршрутизации на основе потока, который учитывает как топологию, так и загрузку транспортной подсети.

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

Для реализации этой идеи нам нужно о каждой транспортной среде заранее знать следующее:

• топологию

• матрицу трафика F^ij

• матрицу пропускных способностей каналов C^ij

• алгоритм маршрутизации

Рисунок 5-8. (а) Топология ТС с пропускной способностью в Кбит/сек.; (b) Матрица с трафиком в пакетах/сек. и маршрутом

На рисунке 5-8 показан пример: (а) – топология транспортной среды с пропускной способностью каналов в Кбит/сек., (б) – матрица, где для каждой пары узлов (i, j) указан средний размер трафика в пакетах в секунду и маршрут для этого трафика. В таблице 5-9 показан итоговый трафик для некоторых пар соседних вершин. Предполагается здесь, что трафик на каждой линии симметричен, т.е. трафик Х к Y идентичен трафику от Y к Х. В этой таблице также показаны среднее число пакетов в секунду (μC_i), при средней длине пакета 1/μ=800 бит. В последнем столбце указана средняя величина задержки, вычисленная по формуле

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

Таблица 5-9. Итоговый трафик для некоторых пар вершин

53. Сетевой уровень: проблемы построения сетевого уровня (Сервис, внутренняя организация сетевого уровня). Алгоритмы маршрутизации (маршрутизация по вектору расстояния, маршрутизация по состоянию канала, иерархическая маршрутизация, маршрутизация для мобильного узла, маршрутизация при вещании, маршрутизация для группы).

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

Сервис сетевого уровня разрабатывался в следующих целях:

• Сервис должен быть независимым от технологии передачи, используемой в среде передачи данных.

• Транспортный уровень должен быть независим от числа узлов, типа и топологии транспортной подсети.

• Адрес на сетевом уровне, доступный на транспортном уровне, должен иметь унифицированную форму по всей сети.

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

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

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

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

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