Лекции 2010-го года (1130544), страница 59
Текст из файла (страница 59)
Возможны сервис с соединением вдейтаграммных транспортных средах, когда надо обеспечить очень надежный сервис;сервис без соединения над виртуальными каналами - TCP/IP над АТМ. Примеры всехчетырех случаев представлены на рисунке 5-3.Рисунок 5-3. Комбинации типов сервиса и организаций транспортных средРаздел 5.2. Алгоритмы маршрутизацииОсновной задачей сетевого уровня является маршрутизация пакетов. Пакетымаршрутизируются всегда, независимо от того, какую внутреннюю организацию имееттранспортная среда - с виртуальными каналами или дейтаграммную. Разница лишь в том,что в первом случае этот маршрут устанавливается один раз для всех пакетов, а во втором- для каждого пакета.
В первом случае говорят иногда о маршрутизации сессии, потомучто маршрут устанавливается на все время передачи данных пользователя, т.е. сессии.Алгоритм маршрутизации - часть программного обеспечения сетевого уровня. Онотвечает за определение, по какой линии отправлять пакет дальше. Вне зависимости оттого, выбирается маршрут для сессии или для каждого пакета в отдельности, алгоритммаршрутизации должен обладать рядом свойств: корректностью, простотой,устойчивостью, стабильностью, справедливостью и оптимальностью.
Если корректность ипростота комментариев не требуют, то остальные свойства надо разъяснить.Алгоритм маршрутизации должен быть устойчивым, т.е. сохранять работоспособностьнезависимо ни от каких сбоев или отказов в сети, изменений в ее топологии (отключениехостов, машин транспортной подсети, разрушения каналов и т.п). Алгоритммаршрутизации должен адаптироваться ко всем таким изменениям, не требуяперезагрузки сети или остановки абонентских машин.Стабильность алгоритма - также весьма важный фактор. Существуют алгоритмымаршрутизации, которые никогда не сходятся к какому-либо равновесному состоянию,как бы долго они ни работали.
Это означает, что адаптация алгоритма к изменениям вконфигурации транспортной среды может оказаться весьма продолжительной. Более того,она может оказаться сколь угодно долгой.8Справедливость значит, что все пакеты, вне зависимости от того, из какого канала онипоступили, будут обслуживаться равномерно, никакому направлению не будет отдаватьсяпредпочтение, для всех абонентов будет всегда выбираться оптимальный маршрут.
Надоотметить, что справедливость и оптимальность часто могут вступать в противоречие другс другом. На рисунке 5-4 приведен пример такого противоречия. Трафики между А-А', ВВ', С-С' могут уже забить канал между Х-Х'. Поэтому вместо кратчайшего маршрутамежду Х и Х” надо будет выбирать какой-то другой маршрут.Рисунок 5-4. Конфликт между справедливостью и оптимальностьюПрежде чем искать компромисс между оптимальностью и справедливостью, мы должнырешить, что является критерием оптимизации. Один из возможных критериев минимизация средней задержки пакета.
Другой - максимизация пропускной способностисети. Однако эти критерии конфликтуют. Согласно теории массового обслуживания, еслисистема с очередями функционирует близко к своему насыщению, то задержка в очередиувеличивается. Как компромисс, во многих сетях минимизируется число переходов междумаршрутизаторами - один такой переход мы будем называть скачком (hop). Уменьшениечисла скачков сокращает маршрут, а следовательно, сокращает задержку, а такжеминимизирует потребляемую пропускную способность при передаче пакета.Алгоритмы маршрутизации можно разбить на два больших класса: адаптивные инеадаптивные. Неадаптивные алгоритмы не принимают в расчет текущую загрузку сети исостояние топологии. Все возможные маршруты вычисляются заранее и загружаются вмаршрутизаторы при загрузке сети.
Такая маршрутизация называется статическоймаршрутизацией.Адаптивные алгоритмы, наоборот, определяют маршрут, исходя из текущей загрузки сетии топологии. Адаптивные алгоритмы различаются тем, где и как они получаютинформацию (локально от соседних маршрутизаторов или глобально от всех), когда онименяют маршрут (каждые Т секунд, когда меняется нагрузка, когда меняется топология),какая метрика используется при оптимизации (расстояние, число скачков, ожидаемоевремя передачи).5.2.1.
Принцип оптимальностиПрежде чем мы приступим к рассмотрению конкретных алгоритмов маршрутизации,сформулируем принцип оптимальности. Этот принцип утверждает, что еслимаршрутизатор J находится на оптимальном пути между маршрутизаторами I и K, тооптимальный маршрут между J и K принадлежит этому оптимальному пути. Это так,поскольку существование между J и K оптимального маршрута, отличного от частимаршрута между I и K, противоречил бы утверждению об оптимальности маршрута9между 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. Расчет кратчайшего пути от А к B10В общем случае веса на дугах могут быть функциями от расстояния, пропускнойспособности канала, среднего трафика, стоимости передачи, средней длины очереди вбуфере маршрутизатора к данному каналу и других факторов. Изменяя весовую функцию,алгоритм будет вычислять наикратчайший путь в смысле заданной метрики.Известно несколько алгоритмов вычисления наикратчайшего пути в графе. Один из нихпредложил голландский математик Эдсгер Дейкстра.
Идею этого алгоритма можноописать так. Все вершины в графе, смежные исходной вершине, помечают расстоянием(оно указано в скобках) до исходной вершины. Изначально никаких путей не известно ивсе вершины помечены бесконечностью. По мере работы алгоритма и нахождения путей,метки могут меняться.
Метки могут быть двух видов: либо пробными, либо постоянными.Изначально все метки пробные. Когда обнаруживается, что метка представляетнаикратчайший путь до исходной вершины, она превращается в постоянную метку иникогда более не меняется.На рисунке 5-6 показан процесс построения маршрута из А в D. Помечаем вершину А какпостоянную (вершина, закрашенная черным цветом). Все вершины, смежные А, помечаемкак временные (эти вершины не закрашены), а также указываем в метке их вершину, изкоторой мы апробировали данную вершину. Это позволит нам впоследствии изменитьмаршрут, если надо. Кроме этого, все вершины, смежные А, помечаем расстоянием от Адо этой вершины.
Из всех смежных вершин мы выберем ту, расстояние до которой самоекороткое, и ее объявляем рабочей. Таким образом, мы выберем на первом шаге вершинуВ, а затем Е.Самое интересное возникнет на шаге (d). В соответствии с принципом наикратчайшегопути мы в качестве рабочей выберем вершину G. Теперь, на шаге (е), когда мы начнемискать вершины, смежные Н, то увидим, что путь F до Н короче, чем от G до Н. Поэтомуна шаге (е) мы в качестве рабочей возьмем вершину F, а затем Н.
На рисунке 5-7 даноописание алгоритма Дейкстры. Надо сделать оговорку, что этот алгоритм строитнаикратчайший путь, начиная от точки доставки, а не от точки отправления. Посколькуграф не ориентированный, то это никакого влияния на построение пути не оказывает.Рисунок 5-7. Алгоритм Дейкстры115.2.3. Маршрутизация лавинойДругим примером статического алгоритма может служить следующий алгоритм: каждыйпоступающий пакет отправляют по всем имеющимся линиям, за исключением той, покоторой он поступил. Ясно, что если ничем не ограничить число повторно генерируемыхпакетов, то их число может расти неограниченно.
Время жизни пакета ограничиваютобластью его распространения. Для этого в заголовке каждого изначально генерируемогопакета устанавливается счетчик переходов. При каждой пересылке этот счетчикуменьшается на единицу. Когда он достигает нуля, пакет сбрасывается и далее непосылается. В качестве начального значения счетчика выбирают наихудший случай,например, диаметр транспортной подсети.Другим приемом, ограничивающим рост числа дублируемых пакетов, являетсяотслеживание на каждом маршрутизаторе тех пакетов, которые через него однажды ужепроходили. Такие пакеты сбрасываются и больше не пересылаются.
Для этого каждыймаршрутизатор, получая пакет непосредственно от абонентской машины, помечает егонадлежащим числом. В свою очередь, каждый маршрутизатор ведет список номеров,сгенерированных другим маршрутизатором. Если поступивший пакет уже есть в списке,то этот пакет сбрасывается. Для предотвращения безграничного роста списка вводятограничительную константу k. Считается, что все номера, начиная с k и далее, ужевстречались.12Несмотря на кажущуюся неуклюжесть, этот алгоритм применяется, например, враспределенных базах данных, когда надо параллельно обновить данные во всех базаходновременно. Этот алгоритм всегда находит наикратчайший маршрут за самое короткоевремя, поскольку все возможные пути просматриваются параллельно.5.2.4. Маршрутизация на основе потокаАлгоритмы, которые мы рассматривали до сих пор, принимали в расчет только топологиютранспортной среды и никак не учитывали ее загрузку.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
