1 Лекция 17 План распределения нагрузки

2 Вопросы лекции 1. Формы представления ПРН 2. Методы формирования ПРН

3 Формы представления ПРН Формирование плана распределения нагрузки ( ПРН) – одна из важнейших функций СУС По- сути, ПРН представляет собой совокупность путей установления соединений в каждом направлении связи и порядок из занятия. ПРН может быть сформирован на основе анализа структуры сети. Аналитическими методами оценки параметров ветвей и расчетом показателей путей установления соединений Визуальной оценкой путей установления соединений Выбор пути установления соединения осуществляется на основе заданного критерия его оценки. Наиболее общим показателем при оценке является длина пути

4 Формы представления ПРН Оценка длины пути может определяться Протяженностью составляющих его каналов ( в км) Количеством транзитных КЦ или ветвей, участвующих в установлении соединения по установленному пути Показателями качества обслуживания заявок Средней стоимостью оборудования пути в пересчете на одно соединений Обычно, выбор пути осуществляется по критерию минимального пути. Для телефонных сетей связи чаще всего длину пути определяют количеством входящих в путь ветвей, числом КЦ или числом транзитов. Формирование ПРН, как правило, производится в два этапа: 1 этап. Определение совокупности возможных путей установления соединений в направлении связи 2 этап. Задание очередности выбора и занятия этих путей.

5 Методы формирования ПРН Матричный метод формирования ПРН в централизованных СУС Определение совокупности всех независимых путей в направлениях связи осуществляется на основе матрицы ||M|| параметров ветвей {m ij }. Значения {m ij }. m ij =, если отсутствует ветвь m ii = 0, для элементов диагонали матрицы Исходная матрица показывает непосредственные связи между КЦ сети. Определение путей производится путем преобразования матрицы ветвей

6 Методы формирования ПРН Пример. Определение путей в направлении связи 2 – 4 Поэлементное сложение 2-й строки и 4- го столбца матрицы Направление 2-4 содержит два пути. Очередность выбора определяет по заданному признаку ( больший номер транзитного КЦ – первый выбор)

7 Методы формирования ПРН Выполнение преобразование матрицы параметров ветвей для каждого направления связи в сети позволяет определить все возможные пути для каждого направления. Количество операций по сложению строк и столбцов равно числу направлений связи I= N*(N-1)/2 Матричный метод построения ПРН применяется в централизованных СУСС ( системах управления сетью связи). Информация о сети собирается в СУСС ( о связности и весовых коэффициентах ветвей), осуществляется математическая (программная) обработка и передача таблиц ПРН (путей установления соединений) на каждый КЦ по всем направлениям связи от данного КЦ. Для обмена служебной информацией между КУ и СУСС используются, как правило, те же рабочие каналы, что и для передачи информационных сообщений

8 Методы формирования ПРН Формирование ПРН методом «рельефов» Метод «Входящих рельефов» Входящим рельефом сети по отношению к какому-либо КЦ называется совокупность коэффициентов, приписываемых каждой ветви сети, определяющих минимальную длину пути к этому КЦ от других КЦ сети. Разметка осуществляется следующим образом: По всем ветвям, входящим в данный КЦ приписывается высота 1 По всем ветвям, смежных КЦ приписывается высота 2 Далее по ветвям, смежных КЦ приписывается высота на 1 больше предыдущей Совокупность «входящих рельефов» по всем КЦ образует полных рельеф сети.

9 Методы формирования ПРН Пример входящего рельефа для КЦ 4 По-сути, значения высоты, приписанные ветвям показывают число ветвей в кратчайшем пути от КЦ сети к КЦ4. Путь КЦ 2 – КЦ 4 содержит 2 ветви Выход из строя одной ветви ( например, m 45 ) меняет рельеф сети

10 Методы формирования ПРН Метод «исходящих рельефов» Исходящим рельефом КЦ называется совокупность коэффициентов, которые приписываются каждой ветви, исходящей от КЦ и определяющую минимальную длину пути от данного КЦ до всех остальных КЦ сети. Пример исходящего рельефа для КЦ 4

11 Методы формирования ПРН Представляется исходящий рельеф для КЦ в форме таблицы. Пример, построения исходящего рельефа для КЦ4 Рельеф отображает длину пути от КЦ ко всем остальным КЦ по всем исходящим ветвям из КЦ

12 Методы формирования ПРН Отличие методов «входящих» и «исходящих» рельефов. Входящий рельеф КЦ4 ( на сеть из КЦ 4) Исходящий рельеф КЦ4 (на исходящие ветви из КЦ 4)

13 Методы формирования ПРН Метод рельефов используется в децентрализованных СУСС Исходные данные (общей информацией для всех КЦ) количество КЦ в сети номера смежных КЦ весовой коэффициент ветви ( например, 1 – при непосредственной связи КЦ i – КЦ j, 0 – при ее отсутствии) Количество смежных КЦ равно числу исходящих ветвей и числу путей установления соединений в любом направлении связи сети Построение рельефа реализуется путем обмена таблицами между соседними КЦ. Обмен таблицами производиться до получения уже известных данных. В полученной таблице имеется информация о значениях весовых коэффициентов путей до всех КЦ сети через все исходящие ветви от КЦ. Метод «исходящих рельефов» нашел широкое применение в компьютерной сети Интернет

14 Методы формирования ПРН Метод рельефов широко используется в адаптивных протоколах маршрутизации - RIP (Routing Information Protocol) и OSPF (Open Shortest Path First). RIP используется преимущественно на нижних уровнях иерархии сети. В сетях, работающих в соответствии с методом OSPF, информация о любом изменении в сети рассылается лавинообразно. В основе метода рельефов ( метода RIP ) лежит алгоритм Беллмана-Форда Алгоритм Беллмана-Форда относится к алгоритмам DVA (Distance Vector Algorithms). В DVA рельеф Ra(d) - это оценка кратчайшего пути от узла a к узлу d. Оценка (условно назовем ее расстоянием) может выражаться временем доставки, надежностью доставки или числом узлов коммутации (измерение в хопах) на данном маршруте. Метод рельефов очень хорошо используется при изменении структуры сети.

15 Методы формирования ПРН Отображение на рельефе КЦ4 изменения структуры сети при удалении двух ветвей рельеф имеет вид

16 Методы формирования ПРН Первоначально принципы построения и функционирования систем адаптивного (динамического) распределения информационных потоков были сформулированы в 1964 г. советским ученым - В. Г. Лазаревым. Позднее на их основе был разработан метод распределенного управления выбором путей передачи информации, получивший название метода рельефов. Практическая реализация идей адаптивного распределения была осуществлена в США в сети ARPA (Adranced Research Projects Agency) Управления перспективных научных исследований (DARPA) США в 1968 г., на основе которой была построена глобальная сеть Internet. В сети Internet на основе метода рельефов реализованы два типа маршрутизации пакетов: Виртуальных каналов Дейтаграммный ( применяется в сетях IP/MPLS)

17 Методы формирования ПРН Достоинства метода рельефов Высокая оперативность построения ПРН Высокая эффективность при структурных изменениях Относительная простота реализации органов управления Недостатки Не эффективное использование для оптимизирования ПРН при возникновении перегрузок, т.к. в качестве критерия рациональности сформированного ПРН используется минимум количества ветвей в пути установления соединения, а не загрузка этих ветвей. Большой объем управляющей информации, которым обмениваются между собой КЦ

18 Методы формирования ПРН Игровой метод формирования ПРН Матрица ПРН содержит значения «высот» для путей установления соединений в виде вероятностей установления соединений в направлениях связи. ПРН для КЦ представляется в виде стохастической матрицы ||k*n-1||, где к – число исходящих из КЦ ветвей, n – число КЦ в сети Очевидно, что для всех исходящих ветвей из КЦ

19 Методы формирования ПРН Механизм расчета вероятностных коэффициентов Если вызов получил обслуживание на i-ой ветви, ее вероятностный показатель увеличивается на коэффициент β>1 Если вызов не получил обслуживание на i-ой ветви, ее вероятностный показатель уменьшается на коэффициент 0

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

21 Методы формирования ПРН Волновой метод установления соединений Данный метод нашел широкое применение в некоторых военных радио сетях Франции и Италии При волновом методе установление соединений осуществляется по всем возможным путям одновременно. Поэтому ПРН не создается вообще. Каждому абоненту сети присваиваться уникальный номер (адрес). При перемещении абонентов по сети это номер сохраняется и не изменяется. КЦ хранят номера всех абонентов, которые включены в данный КЦ (попадают в зону их обслуживания) и обновляют их в соответствии с реальным местоположением абонента.

22 Методы формирования ПРН Процесс утановления соединения осуществляется в три этапа. Поиск. Заявка от абонента на установление соединения фиксируется в обслуживающем КЦ, сравнивает с записанными и если нет соответствия, всем смежным КЦ отсылается «сигнал поиска». Если по полученному сигналу поиска не найден абонент в памяти КЦ, это сигнал рассылается дальше. Сигнал волнообразно проходит через все КЦ сети Ответ абонента. Если на КЦ абонент найден, данный КЦ посылает обратно сигнал «абонент найден». При получении этого ответного сигнала КЦ источником, фиксируется путь ответа в качестве пути установления соединения. Прекращение поиска. КЦ источника посылает по всем исходящим ветвям сигал «прекращения поиска»

23 Методы формирования ПРН Пример. Установление соединения для абонента КЦ1 с абонентом КЦ6 Абонент найден во 2-ом цикле поиска, но сигнал поиска проходит через все КЦ

24 Методы формирования ПРН Достоинства волнового метода Высокая скорость установления соединений Возможность свободно передвигаться в пределах сети без изменения их номера. Недостатки Относительная неэффективность загрузки ветвей ( каналов) сигналами поиска абонентов. Сигнал поиска по каждому запросу абонента проходит по всем КЦ сети. Сигнал от исходящего КЦ о прекращении поиска не может «догнать» сам сигнал поиска, т.к. передается с той же скоростью. Необходимость использования высокоскоростных управляющих устройств на КЦ Волновой метод установления соединений нашел применение как на сетях с коммутацией каналов так и на сетях с коммутацией пакетов

25 Литература Романов А. И. Телекоммуникационные сети и управление: Учебное пособие –К. ИПЦ « Киевский университет», 2003, -247с. Лазарев В.Г., Лазарев Ю.В. Динамическое управление потоками информации в сетях связи. – М.: Радио и связь, – 216 Сети ЭВМ. Под редакцией В.М. Глушкова – М.: Связь, 1977 Бусленко Н. П. Моделирование сложных систем – М. : Наука, 1978 Рыбкин Л.В. и др. Автоматизация проектирования систем управления сетями связи. – М.: Радио и связь, Клейнрок Л. Коммутационные сети – М.: Наука, 1970 Шварц М. Сети ЭВМ. Анализ и проектирование - М.: Радио и связь, 1981 Советов Б.Я. и др. Построение сетей интегрального обслуживания – Л.: Машиностроение, Лен отд-е, 1990 Клейнрок Л. Вычислительные сети с очередями – М.: Мир, 1979

26 Спасибо за внимание!