Положения, лежащие в основе выбора кратчайших путей

Назначение путевых процедур и классификация методов маршрутизации.

Тема 5. МЕТОДЫ МАРШРУТИЗАЦИИ СООБЩЕНИЙ В СЕТЯХ ПЕРЕДАЧИ ДАННЫХ.

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

К алгоритмам маршрутизации предъявляются следующие требования: 1. Обеспечение заданных временных характеристик передачи сообщений от абонента-отправителя до абонента-получателя.

2. Управление маршрутизацией должно быть по возможности децентрализованным, распределенным, с автономным управлением на каждом центре коммутации.

3. Издержки на реализацию не должны снижать эффективности ис­пользования каналов связи и памяти центра коммутации.

4. Иметь простую реализацию.

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

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

Методы маршрутизации, учитывающие эти факторы, называют адаптивными.

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

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

Как уже было отмечено неадаптивные методы маршрутизации не учиты­вают перечисленные выше факторы. К неадаптивным методам маршрутизации отнесем:

- фиксированную маршрутизацию,

- случайную маршрутизацию,

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

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

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

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

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

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

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

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

При централизованной маршрутизации центры коммутации передают локальную служебную информацию центральному управляющему центру коммутации, который рассылает маршрутные директивы всем центрам коммута­ции сети.

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

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

Выбор крат­чайших путей основывается на следующих положениях:

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

2.Если имеется три уза , связанные путями , , , то кратчайший путь от узла до узла определяется на осно­ве тернарной операции

В настоящее время известно большое число способов, позволяющих упорядо­чить определение кратчайшего пути. Все известные способы определения кратчайшего пути могут быть объединены в две группы: способы нумерации узлов ветвей и матричные способы. В основе способов нумерации узлов и ветвей лежат следующие положения. Известна структурная матрица сети или мат­рица связности. Узел М, по отношению к которому отыскиваются крат­чайшие пути, принимается за центральный и ему приписывается нулевой вес . Все остальные узлы или исходящие из них ветви получают веса в соответствии с их минимальным расстоянием от центрального узла. Эти веса выражаются через суммарное значение элементов исходных матриц, характеризующих кратчайший путь. Повторив эту процедуру для каждого узла сети, можно определить кратчайшие пути между каждой парой узлов и их количественные оценки.

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

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

,

где - значение очереди для данного канала,

S - характеристика структуры сети,

T - характеристика нагрузки,

- масштабные множители.

Для сбалансированной по нагрузке сети формула маршрутизации должна обеспечить фиксированную маршрутизацию, а при динамическом изменении нагрузки – адаптивную.

Для локальной адаптивной маршрутизации формула маршрутизации упрощается

.

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

С ростом нагрузки в сети следует ожидать увеличения очередей в центрах коммутации. Поэтому некоторое усложнение формулы маршрутизации

где ,

позволяет приблизить по эффективности локальную адаптивную маршрутиза­цию к распределенной адаптивной. Эта формула дает хороший эффект при нагрузке на сеть, не превышающей 70% ее максимальной пропускной способности. При большей нагрузке предпочтительнее фиксированная маршрутиза­ция.

Основной задачей создания и адаптивного изменения плана распределения потоков информации является формирование матриц (таблиц) по на­правлениям передачи. В маршрутной матрице (ММ) каждому направлению передачи поставлено в соответствие один или несколько путей (маршру­тов). Формирование и применение ММ осуществляется по определенному ал­горитму человеком-оператором на основе визуального анализа струк­туры сети связи или автоматически с использованием аналитических или машинных методов формализованного решения маршрутных задач.

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

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

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

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

Поэтому в ММ записывается один или несколько маршрутов передачи

сообщений.

Применение матрицы (таблиц) маршрутов в общем случае осуществля­ется следующим образом. После получения заявки на передачу сообщения по заданному адресу определяется номер центра коммутации - получателя сообщения и соответствующий ему номер строки (столбца) в ММ.

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

Дата добавления: 2014-01-07