ПОДСИСТЕМА УПРАВЛЕНИЯ МАРШРУТИЗАЦИЕЙ

УК, ЛС, ТПС, КС), входящих в путь между двумя АП

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

В качестве параметров выбора маршрута могут использоваться:
количество транзитных участков (ранг пути);
время задержки в элементах сети при передаче информации между пользователями;
надежность элементов;
пропускная способность элементов сети и т.д.

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

Совокупность

таблиц маршрутизации для всех
УК сети называется планом распределения
информации (ПРИ) на сети связи.

узла j к любому узлу сети. Матрица Mj сдержит n

─ 1 строк и k столбцов, где n – число узлов сети, а k – число узлов смежных с узлом j. Из нее исключается строка, соответствующая вершине j. Номер столбца определяет порядок выбора путей от вершины j через смежные ей вершины к n ─ 1 узлам сети.
Вхождение матрицы Mj представляет номер соответ-ствующей смежной вершины с вершиной j. Самый корот-кий путь является путем первого выбора, а самый длин-ный – путем k-ого выбора. При равенстве ранга путей, вводится дополнительные условия определения порядка выбора путей. Например, преимущество имеют пути через смежную вершину с меньшим номером.

Матрица маршрутизации

рис.:


Пример

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

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

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

ТРЕБОВАНИЯ К ПОДСИСТЕМЕ УПРАВЛЕНИЯ МАРШРУТИЗАЦИЕЙ

временному графику.
СУ должна устранять избыточность информации путем использования объектов, которые

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

ТРЕБОВАНИЯ К ПОДСИСТЕМЕ УПРАВЛЕНИЯ МАРШРУТИЗАЦИЕЙ (продолжение)

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

процедуры:
Построение i–рельефа для каждого узла сети.
Формирование матрицы рельефов Ri для каждого узла сети на основании ранее построен-ных рельефов.
Формирование матрицы маршрутов Mi для каждого узла сети на основании матриц рель-ефов.

МЕТОД РЕЛЬЕФОВ

пути будем использовать ранг пути – r.
2. В качестве модели

сети возьмем простой граф.
3. Определим узел i, для которого построим рельеф .
4. Каждому ребру графа сети поставим в соответ-ствие исходящую стрелку и вес равный ∞. Ребрам узла i поставим вес 0.
5. Выбираем любой узел графа, кроме i, например k, и любое из ребер инцидентное
этому узлу, например, b kj.

АЛГОРИТМ ПОСТРОЕНИЯ i -РЕЛЬЕФА

U b kjнов = 1+ min {U b jm

},
где 1- ранг ребра, связывающего узел k со смежным узлом j;
U jm - минимальный вес ребра, исходящего из узла j.
7. Сравниваем новый вес ребра b kj со старым весом.
Если U b kjнов ≥ U b kjстар, то старый вес ребра остается прежним.
В противном случае старый вес ребра меняется на новый вес U b kjнов .
Переходим к шагу 5.
Шаги 5-7 повторяются до тех пор, пока веса всех ребер графа не будут меняться, т.е. от любого узла сети до узла i определили веса кратчайших путей при использовании соответствующих ребер.

АЛГОРИТМ ПОСТРОЕНИЯ i – РЕЛЬЕФА (продолжение)

для всех вершин графа сети, представленного на рисунке (i =

). В качестве критерия длины пути будем использовать ранг пути.