1

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

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

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

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

Кратчайшим путем передачи информации называется путь, для которого длина пути имеет наименьшее значение по сравнению с его значениями для других возможных путей. Все способы выбора кратчайших путей основаны на достаточно очевидном утверждении о том, что, если кратчайший путь µiN от произвольного узла Узi к узлу УзN проходит через промежуточные узлы Узε , …, Узk , то кратчайшие пути µεN , …, µkN от узлов Узε , …, Узk , к узлу УзN соответственно являются частями кратчайшего пути µiN от Узi к УзN .

Если длина пути µεN равна LεN , то LiN = liε + LεN .

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

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

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

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

В матрице маршрутов число строк равно (N-1), где N – число узлов на сети (строка в матрице Мi для узла i не отводится), а число столбцов равно числу n соседних с рассматриваемым УКi узлов. Элемент mjr матрицы Мi указывает номер очередности выбора ветви ßj при установлении соединения к узлу УКr , т.е. mjr Î {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 (узла назначения).

Предполагая единичную задержку в УК , сигналы поисковой волны при установлении соединения от УК1 к УК5 (сигналы ПE ) распространяются так, как показано на рис. 2.1. При этом обозначение ПE(t0) означает начальный момент (пуск) поисковой волны сигналов ПE , а ПE(ti) – i-й момент прохождения сигналов волны ПE . В запоминающем устройстве (ЗУ) УК фиксируется только тот сигнал волны ПE , который пришел раньше других. При одновременном поступлении сигналов ПE с двух и более направление фиксируется одно из них.

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

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

Заключительная волна сигналов посылается исходящим УКi после получения им ответного сигнала. Процесс прохождения сигналов заключительной волны (ЗE) показан на рис. 2.3. При этом начальный момент (пуск) заключительной волны ЗE совпадает с моментом поступления в УК1 первого сигнала волны ОE . В отличие от сигналов поисковой и ответной волн, сигналы заключительной волны делятся на два типа. Первый тип сигналов волн ЗE обеспечивает установление соединения по кратчайшему пути. В нашем случае кратчайших путей два: (УК1 , УК2 , УК5 ); (УК1 , УК6 , УК5 ). При условии, что критерий кратчайшего пути определяется числом транзитных участков, то путь µ15 может быть либо (УК1,УК2,УК5), либо (УК1 , УК6 , УК5). Второй тип сигналов волны ЗE распространяется к остальным УК сети и служит для стирания в ЗУ таких УК всей информации, относящейся к поиску входящего УКj при установлении рассматриваемого соединения.

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

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

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

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

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

П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. Матричный метод.

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

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

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

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

dij = mink [(gi,1 + d1,j );(gi,2 + d2,j );…;(gi,i + di,j );…;(gi,N + dN,j )]

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

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

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

d1ij = min1 [(gi,1 + d1,j );…;(gi,N + dN,j )]= (gi,e + de,j ),

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

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

d2ij = min2 [(gi,1 + d1,j );…;(gi,N + dN,j )]

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

## При наличии n соседних узлов можно получить n дистанционных матриц D1, D2,…, Dn.

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

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

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

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

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

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

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

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

Затем строки исходных таблиц рельефов заменяются соответствующими им по номеру минимальными строками, каждый элемент которых предварительно увеличен на длину ветви, связывающей рассматриваемые соседние узлы, и получаются таблицы рельефов Ri’. Например, строка 1 таблицы R1 заменяется минимальной строкой Min.2, каждый элемент которой увеличен на величину l12 =1 , а строка 2 таблицы R1 заменяется минимальной строкой Min.5, с добавлением к каждому элементу величины l15 =1. Значения элементов первого столбца таблицы R1 при этом сохраняются равными 0:

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

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

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

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

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

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