Методические указания к задаче 5

Методы управления потоками вызовов на сетях связи.

Общие понятия и определения.

Распределение информации на сети связи производится с учетом оптимальности путей. При этом, очевидно, информацию целесообразно передавать в первую очередь по наиболее “коротким” путям, или, как говорят, по кратчайшим путям.

Для оценки “длины” пути могут быть использованы различные критерии: число транзитных узлов в пути, протяженность пути (например, в км.), качество тракта, вероятность передачи информации (или вероятность установления соединения), вероятность перерыва связи, величина затухания и т.п. Значения многих из этих критериев не являются независимыми, поэтому рассматриваются лишь некоторые из них. Так, в однородной сети связи качество тракта зависит от затухания, которое, в свою очередь, определяется числом транзитных узлов и протяженностью пути. Если протяженность ветвей сети примерно одинаковая; то качество тракта непосредственно определяется числом транзитных узлов в пути. Число транзитных узлов в значительной степени определяет вероятность прерывания связи, вероятность установления всего соединения и т.п. В связи с этим основным критерием длины пути в настоящее время часто принимают число в нем транзитных узлов или ветвей в этом пути. В ряде случаев в качестве дополнительного критерия рассматривается протяженность пути.

Кратчайшим путем передачи информации называется путь, для которого длина пути имеет наименьшее значение по сравнению с его значениями для других возможных путей. Все способы выбора кратчайших путей основаны на достаточно очевидном утверждении о том, что, если кратчайший путь µ_iN от произвольного узла Уз_i к узлу Уз_N проходит через промежуточные узлы Уз_ε , …, Уз_k , то кратчайшие пути µ_{ε N}, …, µ_kN от узлов Уз_ε , …, Уз_k , к узлу Уз_N соответственно являются частями кратчайшего пути µ_iN от Уз_i к Уз_N.

 

Рис.28 Структура кратчайшего пути.

 

Если длина пути µ_{ε N} равна L_{ε N}, то L_iN = l_iε + L_{ε N}.

Так как путь µ_iN является кратчайшим путем, то L_iN = min( l_ij + L_jN ), где j = 1, …, n; n – число узлов сети.

Таким образом, чтобы найти кратчайший путь от узла i к узлу N, необходимо просмотреть все возможные пути и выбрать из них путь с наименьшей длиной.

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

Выбор плана распределения информации для коммутируемой сети рассмотрим применительно к сети коммутации каналов. Порядок выбора исходящих направлений (ветвей) из УК_i ко всем остальным узлам сети, т.е. план распределения информации для узла УК_i , можно представить матрицей маршрутов М_i для УК_i:

В матрице маршрутов число строк равно (N-1), где N – число узлов на сети (строка в матрице М_i для узла i не отводится), а число столбцов равно числу n соседних с рассматриваемым УК_i узлов. Элемент m_jr матрицы М_i указывает номер очередности выбора ветви ß _j при установлении соединения к узлу УК_r , т.е. m_jr Î {1, 2, …, n}.

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

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

 

Метод рельефов

Метод рельефов – метод динамического управления трафиком в сети. Является детерминированным без ограничения нагрузки групповым. Алгоритм реализации данного метода включает три этапа:

a. Построение рельефа для каждого узла сети (i- рельефа).

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

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

 

 

а. Алгоритм построения i- рельефа включает следующие шаги:

1. Определение критерия длины используемого для связи пути. В качестве длины пути при решении задачи будем использовать ранг пути r, определяемого числом ребер графа модели сети.

2. В качестве модели сети возьмем простой неориентированный граф.

3. Выбираем i – вершину (узел) графа сети, для которой строится i - рельеф.

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

5. Выбираем любую вершину k графа сети, кроме ранее выбранной вершины i, и любое ребро инцидентное вершине k. Например, ребро bkj.

6. Определяем новый вес ребра bkj по формуле:

Ukj нов = 1+ Ujm,

где 1 соответствует длине ребра bkj по рангу;

Ujm – минимальный вес ребра из множества ребер инцидентных вершине j.

7. Сравниваем старый вес ребра bkj с новым весом данного ребра.

Если Ukj нов < Ukj, то старый вес ребра меняется на новый вес Ukj нов.

В противном случае вес ребра bkj не меняется и остается прежним.

8. Переходим к следующему ребру вершины k и далее к шагу 6 алгоритма. Просмотрев все ребра, принадлежащие вершине k, переходим к шагу 6. с учетом

изменения номера вершины графа.

Шаги 5- 8 повторяются до тех пор, пока веса ребер графа не будут меняться.

Построенный таким образом взвешенный граф, является i – рельефом и харак-

теризует веса путей минимальной длины по рангу от любой вершины графа до вершины i при использовании любого ребра от рассматриваемой вершины графа.

в. Формирование матриц рельефов Rj.

Матрица рельефов Rj строится на основании i – рельефов графа сети. Матрица рельефов имеет число строк равное числу вершин смежных с вершиной j, а число столбцов равное числу узлов в графе сети. Вершина j смежна с вершинами j 1, j 2, …. jk. Вхождение матрицы Rj равно весу кратчайшего пути между вершиной j графа сети и любой вершиной графа при использовании соответствуюшей смежной вершины ji. Следовательно, все вхождения для j -ого столбца равны 0. В нашем случае вхождение матрицы Rj равно рангу соответствующего пути.

⇐ Предыдущая45678910111213Следующая ⇒

Поделиться: