62184 (588738), страница 5
Текст из файла (страница 5)
На рисунке 5.1 приведена общая классификация методов маршрутизации.
Маршрутизация делится на [2]:
централизованную, когда решающие функции закреплены за одним узлом, который посылает соответствующие команды основным узлам;
децентрализованную, когда каждый узел самостоятельно выбирает маршрут передачи (или ее направление) на основе собственной информации.
В зависимости от способа формирования таблиц маршрутизации алгоритмы маршрутизации делятся на три класса [2]:
алгоритмы фиксированной или статической маршрутизации;
алгоритмы простой маршрутизации;
алгоритмы адаптивной маршрутизации.
В алгоритмах фиксированной маршрутизации все записи в ТМ являются статическими. Все записи о том, какой маршрут выбран для передачи пакетов с теми или иными адресами, заносятся вручную самим администратором сети. если в таблицу требуется внести изменения, например, при отказе в какого-либо маршрутизатора в сети и возложении его функций на другой маршрутизатор, то они делаются вручную. Различают одномаршрутные таблицы, в которых для каждого адресата задан один маршрут, и многомаршрутные таблицы, определяющие несколько альтернативных путей для каждого адресата. В многомаршрутных таблицах должно быть задано правило выбора одного из маршрутов. Как правило, один путь является основным, а остальные резервные. Такой алгоритм маршрутизации применим только в небольших сетях с простой топологией, или для работы на магистральных крупных сетях, так как сама магистраль может иметь простую структуру с очевидными наилучшими путями следования пакетов в подсети, присоединенные к магистрали.
В алгоритмах простой маршрутизации таблицы маршрутизации(ТМ) или не используется, или строится без участия протоколов маршрутизации.
Существует три типа простой маршрутизации:
случайная маршрутизация, когда прибывший пакет посылается в первом попавшемся случайном направлении, кроме исходного;
лавинная маршрутизация, когда пакет широковещательно посылается по всем возможным направлениям, кроме исходного;
маршрутизация по предыдущему опыту, когда выбор маршрута осуществляется по таблице, но таблица строится путем анализа адресных полей пакетов, появляющихся на входных портах.
Самыми широко используемыми являются алгоритмы адаптивной или динамической маршрутизации. Эти алгоритмы обеспечивают автоматическое обновление ТМ после изменения конфигурации сети. Протоколы, построенные на основе этих алгоритмов, позволяют всем маршрутизаторам собирать информацию о топологии связей в сети, оперативно обрабатывая все изменения конфигураций связей.
К адаптивным алгоритмам маршрутизации предъявляется несколько требований:
обеспечение рациональности маршрута;
простота для того, чтобы их реализация не требовала слишком много сетевых ресурсов;
обладание свойством сходимости, то есть достижение однозначного результата за приемлемое время.
Адаптивные протоколы обмена маршрутной информацией делятся на две группы [10]:
дистанционно-векторные алгоритмы (DVA – Distance Vector Algorithms);
алгоритмы состояния связей (LSA – Link State Algorithms).
В алгоритмах дистанционно-векторного типа каждый маршрутизатор периодически и широковещательно рассылает по сети вектор, компонентами которого являются расстояния от данного маршрутизатора до всех известных ему сетей. Возможна и другая метрика, учитывающая не только число промежуточных маршрутизаторов, но и время прохождения пакета по сети между соседними маршрутизаторами. При получении вектора от соседа маршрутизатор наращивает расстояния до указанных в векторе сетей на расстояние до данного соседа. Получив вектор от соседнего маршрутизатора, каждый маршрутизатор добавляет к нему информацию об известных ему других сетях, о которых он узнал непосредственно или из аналогичных объявлений других маршрутизаторов, а затем снова рассылает новое значение вектора по сети. Таким образом каждый маршрутизатор узнает информацию о всех имеющихся в интерсети сетях и о расстоянии до них через соседние маршрутизаторы.
Дистанционно-векторные алгоритмы удобно использовать в небольших сетях. В больших сетях они засоряют линии связи интенсивным широковещательным трафиком, к тому же изменения конфигурации могут обрабатываться по этому алгоритму не всегда корректно, так как маршрутизаторы не имеют точного представления о топологии связей в сети, а располагают только обобщенной информацией – вектором дистанций, полученной через посредников.
Наиболее распространенным протоколом, основанным на DVA, является протокол RIP (Routing Internet Protocol).
Алгоритмы состояния связей обеспечивают каждый маршрутизатор информацией, достаточной для построения точного графа связей сети. все маршрутизаторы работают на основании одинаковых графов, что делает процесс маршрутизации более устойчивым к изменениям конфигурации. Широковещательная рассылка используется только при изменениях состояния связей, что происходит в надежных сетях нечасто. Вершинами графа являются как маршрутизаторы, так и объединяемые ими сети. Распространяемая по сети информация состоит из описания связей различных типов: маршрутизатор-маршрутизатор, маршрутизатор-сеть.
Чтобы понять, в каком состоянии находятся линии связи, маршрутизатор периодически обменивается короткими пакетами HELLO со своими ближайшими соседями. Этот служебный трафик тоже засоряет сеть, но в меньшей степени, чем протокол RIP, так как пакеты HELLO имеют намного меньший объем.
5.2 Формирование плана распределения информации
В общем случае маршрутизация состоит из трех этапов:
Формирование и коррекция плана распределения информации (ПРИ), то есть таблиц маршрутизации для каждого узла коммутации;
Формирование таблиц коммутации, обеспечивающих оптимальное для каждой службы маршруты доставки сообщений пользователей;
Передача информации пользователя.
Совокупность таблиц маршрутизации на сети называется планом распределения информации. Считается, что ПРИ задан, если определены все таблицы маршрутизации для каждого узла коммутации. Таблица маршрутизации представляет собой матрицу Мi, в которой число строк равно N-1, где N – число узлов коммутации сети (строка в матрице Mi для узла i не отводится), а число столбцов равно числу соседних с рассматриваемым узлом коммутации i узлов. Таблицы маршрутизации могут быть составлены по различным критериям: минимальное количество транзитных узлов, минимальная задержка при передаче пакетов, максимальная надежность и так далее.
Формирование плана распределения информации может быть централизованным, распределенным и комбинированным. В первом случае, сбор информации и составление таблиц маршрутизации для всей сети осуществляет один узел, а затем передает эти таблицы в каждый узел коммутации.
При распределенном методе формирования ПРИ каждый узел коммутации самостоятельно составляет таблицу маршрутизации, собирая информацию о состоянии сети и топологии связей. Однако, в случае большой распределенной сети формирование ПРИ таким образом потребует значительных затрат времени и ресурсов сети. Поэтому используют комбинированный способ формирования ПРИ. При этом структуру сети делят на сегменты, в каждом из которых ПРИ формируется либо централизованным, либо распределенным способом.
Кроме того ПРИ может быть статическим и динамическим. Если ПРИ меняется в процессе эксплуатации сети (то есть происходит переформирование ПРИ), то ПРИ называется динамическим, в противном случае – статическим. Динамические методы формирования ПРИ обеспечивают автоматическое обновление таблиц маршрутизации в дискретные моменты времени.
В настоящее время существует три основных способа формирования плана распределения информации: метод рельефов, игровой и логический а также совмещенный метод – логически-игровой.
Метод рельефов.
При использовании метода рельефов для каждого узла коммутации строится свой рельеф, на основе которого составляется таблица маршрутизации. Произвольно выбирается i-ый произвольный узел сети для формирования i рельефа. Из этого узла по всем исходящим трактам передачи сообщения пересылается число 1. Все узлы, в которые поступила 1, увеличивают ее значение на 1 (то есть получаем 2). Теперь уже эта 2 передается во все исходящие тракты. Эта процедура выполняется до тех пор, пока не будет охвачена вся структура сети. Таким образом, получается i рельеф.
Такой рельеф строится для каждого узла. Для выбора оптимального маршрута, по заданным критериям, между i-ым узлом и любым другим нужно выбирать наименьший вес.
Достоинства данного метода в том, что имеется полная информация о состоянии сети на момент формирования рельефа, можно определить исходящие линии связи (ИЛС) не только первого, но и второго, третьего и последующего выбора. Недостатки: большая загруженность сети, особенно при динамическом ПРИ, в случае ввода в эксплуатацию новых УК и в случае загруженности или неисправности сети потребуется переформировать ТМ.
Игровой метод.
Формирование ПРИ происходит по вероятности установления соединения между заданной парой узлов. Перед началом функционирования сети устанавливается начальный набор ТМ. Каждому значению элемента в этой таблице присваивается некоторый весовой коэффициент. При поиске маршрута к i-му УК приходит обращение к i-ым строкам ТМ. В i-ых строках определяется максимальный весовой коэффициент и следовательно выбирается исходящая ЛС. Если в результате маршрут между заданной парой узлов был определен, то весовые коэффициенты данных исходящих ЛС увеличиваются. А если маршрут не был найден, то весовые коэффициенты уменьшаются. После этого строки, в которых были изменены элементы, нормируются.
Достоинства данного метода: нет необходимости передачи служебной информации при формировании ПРИ, оптимизация по критерию – вероятность установления соединения между парой узлов. Отрицательные же стороны – это инерционность, то есть при выходе из строя элементов сети потребуется некоторый период времени для переформирования ТМ на сети, а также необходимость передачи служебной информации о переформировании ТМ при вводе в эксплуатацию новых узлов.
Логический метод.
В каждом УК выполняется процедура, которая позволяет определить исходящую ЛС максимально близкий к геометрическому направлению к узлу получателю. Для этого вся сеть связи помещается в прямоугольную систему координат. Каждому узлу присваиваются свои координаты (x,y). Затем происходит вычисление геометрического направления на заданный узел, путем сравнения своих координат с координатами узла получателя. После этой процедуры выбирается та ЛС, которая имеет наибольшее совпадение с вычисленным геометрическим направлением.
Достоинства: отсутствие служебной информации, простота алгоритма вычислений исходящей ЛС позволяет уменьшить объем оперативной памяти, так как нет необходимости использовать ТМ, упрощается процедура маршрутизации и ввода в эксплуатацию новых узлов. Недостатки: при выходе из строя элемента сети, то это явление не будет отмечено никакой информацией, так как этот метод не является динамическим, не учитываются возможности ранее забракованных из-за загруженности, но более предпочтительные направления.
Логически-игровой метод
Логически-игровой метод – это объединение двух методов: логического и игрового. Данный метод вобрал в себя достоинства обоих методов: отсутствие необходимости передачи служебной информации на сети при формировании (во время ввода в эксплуатацию УК), и переформирования уже в процессе эксплуатации УК таблиц маршрутизации. А так же решение задач глобальной оптимизации сети связи по критерию – формирование ПРИ по накопленной ранее статистике установления соединения между заданной парой УК.
Логически-игровой метод заключается в том, что сеть вводится в прямоугольную систему координат (логический метод), в соответствии, с которой каждому узлу сети присваивается собственный адрес (X,Y), и использует ранее накопленную статистическую информацию о состоявшихся разговорах (игровой метод). Следовательно, логический метод используется при вводе нового УК в эксплуатацию. В каждом УК сети имеется матрица, которая имеет следующий вид (таблица 5.2.1). Данная матрица содержит SN строк. Учитывая возможное увеличение числа УК на сети, SN выбирают таким, чтобы SN>J.
Количество столбцов матрицы PN(j) для УК под номером j равно: (Hj + 3), где Hj –число исходящих ЛС из j- го узла; три столбца отводится для номеров УП, представленных о общепринятой нумерации (№ УП) и прямоугольной системе координат (X,Y).
На момент ввода узла в эксплуатацию матрица содержит только информацию о смежных номерах УК с данными, выраженных в прямоугольной системе координат (т. е. координаты смежных УК). По мере функционирования сети связи матрица заполняется и корректируется.
Определение исходящей ЛС осуществляется логическим методом, а заполнение и корректировка матрицы – игровым методом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
