Р.Л. Смелянский - Компьютерные сети. Том 2. Сети в ЭВМ (1130083), страница 8

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

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

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

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

2.2.2. Свойство оптимвльиого пути Обоснуем одно важное предположение о свойстве оптимального маршрута, которое будет использоваться в дальнейших рассуждениях 119]. Это свойство состоит в том, что если маршрутизатор / находится на оптимальном пути между маршрутизаторами 1 н К (рис. 2.2, а). то оптимальный маршрут между 1 и К принадлежит этому оптимальному пути. Это так„поскольку существование между з" и К оптимального маршрута, отличного от части маршрута между 2 и К, 32 Рис. 2.2.Топология транспортной среды (а) и дерево захода(б) :.,:,'противоречило бы утверждению об оптимальности маршрута между :; -;.Хи К. Дело в том, что если представить маршрут от 1до К, как от 1 ; ' до У (назовем его 5) и от Удо К(назовем его 5) и если между / и К :::„-имеется маршрут лучше, чем Я„например 5;, то маршрут Х,5, не .'.

':-может быть лучшим. Взяв конкатенацию маршрутов 5,5и мы получим -'...;:лучший маршрут, чем маршрут Х,5,. Следствием из этого свойства ; ' .является утверждение, что все маршруты к заданной точке транс,': "портной среды образуют дерево с корнем в этой точке. Это дерево, :=..',-называемое деревом захода, показано на рис. 2.2, 6.

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

Маршрутизация по наикратчайшему пути Изучение алгоритмов маршрутизации начнем со статического : - алгоритма, широко используемого на практике вследствие его про. стоты, Идея этого алгоритма состоит в построении графа транспорт, ной среды (где вершины — маршрутизаторы, а дуги — каналы связи) :" И нахождении наикратчайшего пути в этом графе. На рис. 2.3 И9) показана работа алгоритма нахождения наикратчайшего пути от А к 2) (стрелками обозначены задействованные узлы).

„: .На дугах этого графа цифрами указаны веса, которые представляют собой расстояния между узлами. Это расстояние можно измерять в переходах, а можно в километрах. Возможны также и другие меры: например, средняя задержка пакетов в соответствующем канале. В ... графе с такой разметкой наикратчайший путь — это путь с наимень.шим весом, хотя ему необязательно способствует минимальное число переходов или километров. 33 2 ему~и ссик 2 В общем случае веса на дугах могут представлять собой функции расстояния, пропускной способности канала, среднего графика, стоимости передачи, средней длины очереди в буфере маршрутизатора к данному каналу и других факторов. При изменении весовой функции алгоритм будет вычислять наикратчайший путь в соответствии с заданной метрикой. Известно несколько алгоритмов вычисления наикратчайшего пути в графе. Один из них предложил голландский программист Э.

Дейкстра. Идея этого алгоритма следующая. Все вершины в графе, смежные исходной вершине, помечают расстоянием до исходной вершины (указано на рис. 2.3 в скобках). Изначально никаких путей не выделено, и все вершины помечены бесконечностью. По мере работы алгоритма и нахождения путей метки вершины могут изменяться. При этом мет- )з(~ю 1) )г (~, — ) Рис. 2.3. Иллюсзрация шагов (а...е) алгоритма поиска наикратчайшего пути от А к 2) 34 ,ки могут быть трех видов: временными, рабочими и постоянными.

Изначально все метки временные. Когда обнаруживается, что метка Принадлежит наикратчайшему пути до исходной вершины, она превращается в постоянную метку и никогда более не изменяется. На рис. 2.3, а...е показаны шаги процесса построения маршрута изА в Л. Помстим вершину А как постоянную (зачерненной точкой), Все вершины, смежные с вершиной А, пометим как временные (незачерненными точками) и укажем в этих метках вершину, из которой они достижимы и за какое расстояние. Это позволит нам впослед,ствии при необходимости изменить маршрут. Кроме того, все вер- ' шины, смежные с вершиной А, пометим расстоянием от А до этой вершины. Из всех смежных вершин выберем ту, расстояние до кото:- ;рой самое короткое, и объявим ее рабочей.

Таким образом, на первом шаге процесса выберем вершину В, а затем Е. При этом самое интересное происходит на шаге г: в соответствии ' ': с, принципом кратчайшего пути в качестве рабочей вершины выби' . раем вершину С. Теперь на шаге д, когда начнем искать вершины, -,,смежные Н, увидим, что путь от Гдо Н короче, чем от С до Н, поэто' ' му в качестве рабочей возьмем здесь вершину Г, а С пометим как .;временную. Затем пометим Н как рабочую, после чего останется : ".только преобразовать рабочие вершины в постоянные, 2.2.4.

Маршрутизация лавиной Примером статического алгоритма маршрутизации может также '.;:,::служить следуюший алгоритм. Каждый поступающий пакет отправ-':. ляют по всем имеющимся линиям за исключением той, по которой ;:ч он поступил. Ясно, что если ничем не ограничить число повторно '..., генерируемых пакетов, это число может расти неограниченно. Поэто!"., му, чтобы ограничить область распространения, время жизни таких ;:;;:.пакетов ограничивают.

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

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

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

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

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

Список файлов книги