3. Преобразования структур сетей связи

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

Остановимся на рассмотрении сети с заданными фиксированными N узлами (пунктами), потребность в связи между которыми задана либо нагрузкой Y_st (например, в Эрлангах), либо числом стандартных каналов u_ST. Все ребра сети будем считать ненаправленными и допускать введение дополнительных узлов, когда это дает положительный эффект.

Для обеспечения связности между заданными N узлами число ребер Н в сети может меняться от N-1 (односвязная сеть) до N(N-1)/2 (полно связная сеть). Каждое ребро b_ij будем характеризовать длиной l_ij (в километрах), емкостью _ij (в числе стандартныx каналов ТЧ) и стоимостью ц_ij = ц(l_ij,_ij) (в рублях). Как уже указывалось, стоимость ребра (линии) зависит от многих факторов . В дальнейшем примем две наиболее часто встречающиеся зависимости стоимости от длинны и емкости:

линейную ц_ij = ( + _ij) l_ij

и степенную ц_ij = l_ij

где , ,  и  - параметры, характеризующие аппаратуру и условия строительства, причем 0<<1.

Будем считать, что имеются связи между всеми узлами [т. е. их будет N(N-1)/2] и каждая связь, как правило, проходит только по одному кратчайшему в данной сети пути , причем каждой связи _st соответствует пучок каналов u_st, проходящий по всем ребрам, образующим путь для данной связи. Все пути образуют множество М. Введение коммутации на отдельных узлах для объединения нагрузки позволяет уменьшать общее число каналов на отдельных участках. В некоторых случаях для повышения надежности пучок каналов u_ST будем разбивать и частями пропускать по разным путям.

Структура сетей при разном числе ребер H для заданных расположений узлов (определенных расстояниями l_ij между ними) и тяготений будем оценивать:

а) общей длиной ребер (линий)

L =

где В - множество всех ребер данной сети;

б) общей длиной каналов (например, в канало- километрах)

 =

или «мощностью» сети, Эрл·км или бит·км/с,

C =

где с_ij - - пропускная способность ребра, Эрл или бит/с;

в) общей суммой рангов связей (суммой рангов кратчайших путей)

R =

г) суммой расстояний для всех связей, км,

D =

д) общей стоимостью сети

Ц =  L + , или Ц = 

Полно связная сеть имеет общую минимальную длину каналов тiп, так как в ней все связи идут по кратчайшему пути _с рангом, равным единице. В то же время такая сеть имеет максимальную общую длину ребер Lmax- Общая длина связей, выраженная в рангах, равна числу ребер, т. е. R = N(N-1)/2, а выраженная в километрах - общей длине ребер:

D = L =

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

Односвязная сеть (дерево) имеет N-1 ребро и может иметь много различных структур при значительном разбросе суммарных длин. Из теории графов известно, что связно сетью с минимальной общей длиной ребер является дерево, построенное по определенному алгоритму.

Рис. 3 Возможные варианты построения сети с тремя пунктами

Рассмотрим, как будут изменяться параметры простейшей сети с тремя узлами (рис. 3), тяготения между которыми заданы нагрузками у₁₂, у₂₃ и у₁₃ чему соответствуют пучки каналов и₁₂, и₂₃ и и₁₃. Узлы соединены ребрами а,b и с (рис. 3.а) длиною l_a,l_b и 1_С, причем 1_а+1ь>1_с. Параметры а, ,  и  из зависимостей стоимостей будем считать одинаковыми для всех этих ребер.

Рассмотрим некоторые возможные структуры такой сети. В табл. 1 приведены данные для общей длины ребер L и каналов  некоторых из рассматриваемых структур:

1. В полно связной сети без обходов (рис. 3а) емкость ребер равна требуемому числу каналов между узлами, т. е. _а = и₁₂,, _b = и₂₃ и _c = и₁₃

Таблица 1

Рисунок	Общая длинна ребер L	Общая длинна каналов 
1.	2.	3.
а)
б)
в)
г)
1.	2.	3.
д)
ж)
з)
к)

2. Если исключить из структуры одно ребро, например с (рис. 3б), то емкости ребер будут _a = и₁₂+и₁₃ и _b = u₂₃+ u₁₃, соответственно увеличатся длина пути ₁₃ и общие длины каналов и путей, но общая длина ребер (линий) уменьшится.

3. Введение коммутации (рис. 3в), объединяющей нагрузки предыдущего случая, несколько уменьшит число каналов в ребрах а и b, что можно характеризовать коэффициентом ₁<l.

4. Если объединять не всю нагрузку, а только часть (рис. 3г), то при не значительном увеличении числа каналов по сравнению с предыдущим случаем резко сократится объем коммутационного оборудования. Коэффициент ₂ не много больше ₁, причем ₁<₂<l.

5. Применение многополюсных (многопунктных) каналов, обслуживающих всю нагрузку у₁₂+у₂₃+у₁₃ (рис. 3д) или ее часть (рис. 3е), в некоторых случаях может уменьшить общее число каналов и стоимость сети.

6. Введение дополнительного узла 0, через который пройдут пучки прямых каналов (рис. 3ж), позволит уменьшить общую длину ребер по сравнению с вариантом рис. 3б, что может быть учтено введением коэффициента (0,87<1). Применение в узле 0 коммутации для всех (рис. 3з) или части (рис. 3и) каналов позволит уменьшить и число этих каналов.

7. Во всех рассмотренных вариантах между каждыми двумя узлами имеется только один путь. Повышение надежности достигается использованием обходных путей. Это может быть осуществлено разделением каналов на группы, идущие по разным путям (рис. 3к). По сравнению с вариантом рис. 3а Увеличится общая длина каналов, так как часть из них будет идти по более длинному обходному пути. Если по обходному пути между узлами i и j идет -я часть каналов u_ij то, например, из ребра а потребуется выделить _a=(1 - p)и₁₂ +p(и₂₃ + и₁₃) каналов, может привести к удорожанию сети но обеспечит большую надежность. Применение на всех узлах коммутаций для объединения всей (рис. 3л) или части (рис. 3м) нагрузки приведет к некоторому сокращению числа каналов по сравнению с вариантом рис. 3к.

Рис. 4 Зависимости общей длинны ребер L(a), каналов (б), стоимости Ц и надежности (в) от числа ребер в сети

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

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

Прежде всего, рассмотрим условия, при которых целесообразны с точки зрения стоимости сети исключение одного ребра из трех узловой сети (рис. 3а) со стоимостью ребер Ц_a и переход к сети (рис. 3б) со стоимостью Ц_б. Исключение ребра будет целесообразным, если разность Ц = Ц_а – Цб будет положительной.

Если принять линейную зависимость стоимости ребра, то (см. табл. 1): , откуда условие целесообразности исключения ребра примет вид 0 или //₁₃ , где - Для степенной аппроксимации в соответствии при и₁₂ = и₁₃ = и₂₃ условие целесообразности исключения ребра с примет вид l_с+(l_а + l_b)(1- 2^б)>0, или l_с>(2⁶-1) (l_а +l_b). Если принять  = 0,5, это условие будет l_с>0,42(l_а + l_b).

В реальной сети не всегда может быть применен данный вывод, так как ребро с может включать каналы связей между узлами, не входящими в данный треугольник, а они не обязательно все пойдут по новому пути через узел 2. Исследования сетей с большим числом узлов показали, что при обеспечении связи между любыми двумя узлами по пучку прямых каналов, идущих по кратчайшему пути, общая длина L ребер и  каналов при изменении числа ребер меняется так, как показано на рис. 4 (а и б) (показаны нижняя и верхняя границы вариантов). На рис. 4в показана зависимость стоимости сети (без учета стоимости узлов) от числа ребер, причем для каждого числа ребер выбирался оптимальный по стоимости вариант. Заметим, что таким вариантом не обязательно должна быть структура с минимальной длиной ребер или каналов. Увеличение числа ребер увеличивает живучесть и надежность сети, поскольку увеличивается возможность установления отдельных связей по нескольким путям. На рис. 4в пунктиром показано изменение надежности. Применение в узлах устройств коммутации (как каналов, так и сообщений) приводит к тому, что на отдельных участках (ребрах сети) число каналов может быть уменьшено за счет объединения нагрузок, а также обеспечено установление соединения или передача сообщения по обходному пути, если основное направление перегружено или повреждено. Наличие коммутационных узлов значительно сокращает расходы на сеть при малых пучках каналов для каждой связи.