2. Оценки ребер и путей в сети

Для получения количественных оценок ребер, путей и связей? каждому ребру или узлу сети приписывается «вес» - число, характеризующее соответствующее свойство ребра или узла, с указанием размерности. Для каждой характеристики может быть, составлена матрица, вхождения которой относятся либо к ребрам b_ij, либо к узлам а_i (на главной диагонали). Прежде всего введем матрицы, характеризующие ребра:

1. Матрица смежности R (см. Лекцию 2).

2. Матрица длин ребер (линий)

L =

где l_ii = 0; l_ij - длина линии от пункта а_i,- до пункта a_j: l_ij = , если между a_i и а_j нет ребра.

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

C =

Пропускную способность ОП будем считать равной нулю, а узлов - неограниченной, т. е. в сетевых узлах возможно кроссирование любого числа любых каналов, а в коммутационных - установление любого числа соединений (при коммутации каналов) или передача сообщений (при коммутации пакетов или сообщений) между входящими и исходящими каналами любых направлений. В дальнейшем вместо показателя пропускной способности для оценки того или иного ребра сети будем пользоваться числом стандартных каналов (обычно каналов ТЧ). Этот показатель назовем емкостью ребра (линии) и будем записывать матрицей емкостей вхождения которой _ij - число каналов от a_i к a_j;- (при отсутствии между пунктами ребра _ii = 0; _ij = 0).

V =

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

4. Матрица прямых каналов

U =

где и_ij - число каналов, начинающихся в узле a_i; и кончающихся в узле a_j независимо от того, через какие еще транзитные или сетевые узлы они проходят. Такая матрица уже характеризует возможность сети по установлению связи, если считать, что все узлы являются коммутационными.

5. Матрица надежности

P =

где р_ij = q_ij - вероятность нахождения данного ребра в работоспособном состоянии, а q_ij - вероятность выхода его из строя.

6. Матрица стоимостей

Ц =

где ц_ij - стоимость ребра между пунктами а_i и а_j , a ц_ii = ц_i - стоимость узла a_i. В стоимость ребра может быть включена стоимость каналообразующей, а иногда и части коммутационной аппаратуры узлов а_i и a_j.

Из матриц L и С или V могут быть построены матрицы, отражающие возможности ребра по доставке информации, выраженной в канало-километрах (матрица  = ), бито- километрах или Эрланго - километрах (матрица CL = )

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

Для пути зависимости от поставленной задачи могут быть использованы матрицы либо емкостей V, либо прямых каналов U.

1. Ранг пути - число входящих в него ребер; если используется матрица прямых каналов, то ранг пути будет характеризовать число входящих в путь прямых каналов.

2. Длина пути - сумма длин всех ребер, образующих этот путь:

3. Пропускная способность пути определяется наиболее узким местом - минимальной пропускной способностью ребер, образующих путь:

4. Емкость пути - максимальное число каналов, которое может быть получено в данном пути. Емкость пути определяется минимальной емкостью ребер, входящих в путь:

Длину кратчайшего пути между пунктами a_s и a_t примем за расстояние d_st между этими пунктами в сети (это расстояние может отличаться от географического расстояния), т. е.

Соответственно сеть может характеризоваться матрицей расстояний (длин кратчайших путей)

D =

Аналогичные показатели могут быть определены и для отдельных сечений (или квазисечений). Так, пропускная способность и емкость сечения (или квазисечения) ^l_st определяются как сумма пропускных способностей или емкостей ребер, входящих в данное сечение (квазисечение):

Одной из важнейших характеристик сети является пропускная способность связей _st между отдельными пунктами сети - пропускная способность c*_st или емкость v*_st множества m*_st всех или выбранных путей, образующих данную связь, которые определяются как пропускная способность (емкость) сечения (квазисечения) данного множества путей, имеющего минимальную пропускную способность или емкость:

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