Подсистема управления маршрутизацией

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

• Общие положения
• Классификация методов маршрутизации
• Метод рельефов
1

2. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ

Маршрут (route) – список элементов сети (АП, УК, ЛС,
ТПС, КС), входящих в путь между двумя АП
пользователей либо узлами сети.
Маршрутизация (routing) – набор процедур,
позволяющих определить оптимальный, по заданным
параметрам, маршрут на сети связи между АП
пользователей либо узлами коммутации.
В качестве параметров выбора маршрута могут
использоваться:
количество транзитных участков (ранг пути);
время задержки в элементах сети при передаче
информации между пользователями;
надежность элементов;
пропускная способность элементов сети и т.д.

3. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ

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

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

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

5. Пример

Сформируем матрицу маршрутизации для первой вершины графа сети, представленного на рис.:

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

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

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

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

8. КЛАССИФИКАЦИЯ МЕТОДОВ МАРШРУТИЗАЦИИ

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

Метод рельефов – динамический метод управления трафиком в сети, детерминированный,
групповой, без ограничения нагрузки.
Алгоритм реализации метода рельефов
включает следующие процедуры:
Построение i–рельефа для каждого узла сети.
Формирование матрицы рельефов Ri для
каждого узла сети на основании ранее построенных рельефов.
Формирование матрицы маршрутов Mi для
каждого узла сети на основании матриц рельефов.

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

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

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

6.Определяем новый вес ребра b kj , по формуле:
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 определили веса кратчайших путей при
использовании соответствующих ребер.

12. Пример

Сформируем i –рельефы, матрицы рельефов Ri и
матрицы маршрутов Mi для всех вершин графа сети,
представленного на рисунке (i =
). В качестве
критерия длины пути будем использовать ранг пути.
2
1
3
4

13. Сформируем рельеф для 1 –ой вершины

14. Цикл 2

15. Рельефы для всех вершин графа

16. Матрицы рельефов и маршрутизации для 1- ой и 2 - ой вершины

17. Матрицы рельефов

18. Матрицы маршрутизации

19. КОНЕЦ