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

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

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

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

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

Если длина пути µ_ε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}.

В лабораторной работе используется матрица маршрутов, представленная в виде:

В данном случае 1, 2,…, n – номер очередности выбора пути. УК_X ,УК_Y ,…, УК_Z – смежные с i-тым узлом узлы, причем: X=1,2,…,N; Y=1,2,…,N; Z=1,2,…,N; X¹Y¹Z.

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

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

2. Волновой метод получения плана распределения информации.

Этот способ относится к группе разовых детерминированных способов получения плана распределения информации. Он состоит в том, что при поступлении на УК_i заявки (вызова) на установление соединения по сети передаются три “волны” сигналов: поисковая, ответная и заключительная.

Поисковая волна сигналов – такая волна, которая при поступлении заявки на соединение посылается с УК_i и транслируется всеми узлами сети. Она служит для отыскания входящего узла УК_j (узла назначения).

Предполагая единичную задержку в УК , сигналы поисковой волны при установлении соединения от УК₁ к УК₅ (сигналы П_E ) распространяются так, как показано на рис. 2.1. При этом обозначение П_E(t₀) означает начальный момент (пуск) поисковой волны сигналов П_E , а П_E(t_i) – i-й момент прохождения сигналов волны П_E . В запоминающем устройстве (ЗУ) УК фиксируется только тот сигнал волны П_E , который пришел раньше других. При одновременном поступлении сигналов П_E с двух и более направление фиксируется одно из них.

Ответная волна сигналов посылается входящим узлом УК_j после получения поискового сигнала и транслируется всеми узлами сети. Эта волна сигналов служит для маркировки пути между исходящими и входящими УК; при ее прохождении прекращается трансляция поисковых сигналов.

Процесс прохождения сигналов ответной волны (О_E) аналогичен процессу прохождения сигналов волны П_E и показан на рис. 2.2. При этом начальный момент (пуск) ответной волны О_E совпадает с моментом поступления в УК₅ первого сигнала волны П_E . В нашем случае – это момент t₂ .

Заключительная волна сигналов посылается исходящим УК_i после получения им ответного сигнала. Процесс прохождения сигналов заключительной волны (З_E) показан на рис. 2.3. При этом начальный момент (пуск) заключительной волны З_E совпадает с моментом поступления в УК₁ первого сигнала волны О_E . В отличие от сигналов поисковой и ответной волн, сигналы заключительной волны делятся на два типа. Первый тип сигналов волн З_E обеспечивает установление соединения по кратчайшему пути. В нашем случае кратчайших путей два: (УК₁ , УК₂ , УК₅ ); (УК₁ , УК₆ , УК₅ ). При условии, что критерий кратчайшего пути определяется числом транзитных участков, то путь µ₁₅ может быть либо (УК₁,УК₂,УК₅), либо (УК₁ , УК₆ , УК₅). Второй тип сигналов волны З_E распространяется к остальным УК сети и служит для стирания в ЗУ таких УК всей информации, относящейся к поиску входящего УК_j при установлении рассматриваемого соединения.

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

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

3. Игровой метод.

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

Пусть соединения от узла i к узлу j (рис. 3.1.) можно устанавливать через соседние узлы i₁ ,…,i_n . Рассмотрим так называемую матрицу поощрений:

П_i = ß_h ║π_h,r║

в качестве значений элемента которой примем нормированные по столбцу вероятности установления соединения π_h,r т.е.

_n

å π_h,r = 1.

^h=1

При установлении соединения к узлу j по пути, проходящему через ветвь ß_h , значение π_h,r увеличивается в ε раз (0 < ε < 1), а весь столбец нормируется. Такое увеличение значения элемента рассматриваемой матрицы часто называют поощрением.

Наряду с поощрением можно использовать так называемые штрафы, когда значение элемента π_h,r уменьшается в ε раз при не установлении соединения к узлу j по пути, проходящему через ветвь ß_h. В последнем случае, очевидно, столбец также должен нормироваться.

После того как закончится некоторый интервал времени, называемый периодом настройки (или обучения), при наличии стационарных потоков и неизменной ситуации на сети значения элементов матрицы поощрений стабилизируются. Для того чтобы значения элементов были бы более стабильными при неизменных условиях, величина ε должна быть небольшой. Однако при этом период t настройки может оказаться значительным, т.е. при ε→0 получим t→∞. Практически значение ε может быть принято равным ε = 0.01 ÷ 0.3.

От матрицы поощрений легко перейти к матрице маршрутов, если принять, что соединение устанавливается в первую очередь в том направлении, которому соответствует максимальный элемент матрицы поощрений. Например, матрица поощрений имеет вид:

тогда матрица маршрутов:

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

4. Матричный метод.

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

В начале второго этапа составляется модернизированная матрица длин ветвей сети Г, нулевые элементы ветвей имеют значения ∞. По матрице длин ветвей L¹ можно получить модернизированную матрицу длин ветвей Г.

Замена элемента l_ii с нуля на ∞ означает, что длина пути в УК принимается бесконечно большой. Это дает возможность не рассматривать все пути, проходящие через исходящий узел, т.е. позволяет исключить путь (b_ii ,b_ij). Полученная указанным способом модернизированная матрица длин Г =║g_ij║ умножается на дисперсионную матрицу D. При умножении матрицы Г на матрицу D образуется матрица D = Г × D, элементы которой используются для получения дистанционных матриц (т.е. матриц величин второго и т.д. кратчайших путей) и матриц маршрутов.

Каждый элемент d_ij матрицы D =║d_ij ║ имеет вид

d_ij = min_k [(g_i,1 + d_1,j );(g_i,2 + d_2,j );…;(g_i,i + d_i,j );…;(g_i,N + d_N,j )]

Каждый из членов (g_i,e + d_e,j ) определяет длину пути от узла i к узлу j , если первым транзитным узлом после узла i на пути к узлу j будет узел e,eÎ {1,…,N}. Если узел e не является соседним узлу i , то член (g_i,e + d_e,j ) равен ¥.

В связи с тем, что g_i,i = ¥, член (g_i,i + d_j,j ) всегда имеет значение ¥ (элемент (g_i,j + d_j,j ) необязательно равен ¥). Таким образом, число членов, не равных ¥, равно числу n соседних УК, т.е. числу исходящих из УК_i направлений (ветвей).

Величина минимального члена, определяющая длину кратчайшего пути от узла i к узлу j через узел e :

d¹_ij = min₁ [(g_i,1 + d_1,j );…;(g_i,N + d_N,j )]= (g_i,e + d_e,j ),

заносится в качестве элементов d¹_ij в дистанционную матрицу 1-го выбора D¹ =║d¹_ij ║.

Величина второго по значению члена, определяющая длину второго по протяженности пути после кратчайшего пути от узла i к узлу j:

d²_ij = min₂ [(g_i,1 + d_1,j );…;(g_i,N + d_N,j )]

заносится в качестве элементов d²_ij в дистанционную матрицу 2-го выбора D² =║d²_ij ║.

При наличии n соседних узлов можно получить n дистанционных матриц D¹, D²,…, Dⁿ.

От матрицы D легко перейти к матрицам маршрутов для каждого узла.

Для того чтобы получить матрицу маршрутов для УК_i , необходимо найти минимальный член при k = e,e = 1,2,…,N. Пусть минимальным членом будет член (g_i,e + d_e,j ). Тогда это означает, что k-м по длине путем от УК_i к УК_j будет путь, проходящий через УК_e , а ветвь b_ie , соединяющая узлы УК_i к УК_e входит в путь k-го выбора. Следовательно, элемент m матрицы маршрутов для УК_i равен значению индекса k , т.е.

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

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

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

К методам, использующим для определения кратчайших путей нумерацию ветвей, относится метод рельефов. В указанном методе “N-рельефом” называется набор весов всех ветвей, определенных для фиксированного конечного узла N. Рельефы сети записываются в специальные таблицы рельефов. На каждом узле формируется своя таблица рельефов. Процесс формирования матриц рельефов похож на процесс построения дистанционной таблицы и будет рассмотрен на примере сети рис. 5.1. В рассматриваемом примере длина пути выражается числом транзитных участков.

На каждом узле сети составляется исходная таблица рельефов R_i . Число столбцов таблицы определяется числом конечных узлов в путях передачи информации (числом возможных адресов сообщений). В общем случае число столбцов каждой таблицы рельефов равно числу узлов сети. Число строк таблицы рельефов равно числу ветвей, исходящих из узла, для которого эта таблица составлена. Столбцам присваиваются номера узлов, а строкам – номера конечных узлов ветвей, соответствующих этим строкам. В исходной таблице рельефов на произвольном узле i все элементы, кроме элементов i–го столбца, принимаются равными ¥ (практически эти элементы таблицы могут иметь любое значение, превышающее максимально допустимую длину пути). Элементы i–го столбца принимаются равными нулю и в процессе преобразования таблицы не изменяются.

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

Затем строки исходных таблиц рельефов заменяются соответствующими им по номеру минимальными строками, каждый элемент которых предварительно увеличен на длину ветви, связывающей рассматриваемые соседние узлы, и получаются таблицы рельефов R_i^’. Например, строка 1 таблицы R₁ заменяется минимальной строкой Min.2, каждый элемент которой увеличен на величину l₁₂ =1 , а строка 2 таблицы R₁ заменяется минимальной строкой Min.5, с добавлением к каждому элементу величины l₁₅ =1. Значения элементов первого столбца таблицы R₁ при этом сохраняются равными 0:

После того, как указанным способом будут заменены строки во всех таблицах, вновь формируются минимальные строки и вновь производится замена строк и формируются таблицы R_i^”:

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

Так как в рассматриваемом примере две последние замены в R_i^” и R_i^”’ не изменили значений ни одного элемента минимальных строк, процесс завершается. Сформированные указанным способом таблицы рельефов идентичны дистанционным таблицам, полученным матричным методом, и могут быть использованы для распределения потоков информации по сети.

В соответствии с полученными матрицами рельефа строим матрицы маршрутов:

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

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