Контрольные вопросы

1. Дайте определение способа организации связи с использованием обходных направлений.

2. Расскажите об иерархическом принципе организации обходных направлений. Каковы его достоинства и недостатки?

3. Расскажите о распределенном принципе организации обходных направлений. Каковы его достоинства и недостатки?

4. Опишите план распределения потоков вызовов.

5. Расскажите об итерационном методе расчета сетей с обходными направлениями, его основных положениях.

6. Опишите процесс построения «дерева» путей.

7. Как определяются доли суммарной нагрузки на каждое -е направление связи при распределении нагрузки ?

8. Как определяются потери между любой парой узлов коммутации?

9. Как определяется максимальное отклонение между потерями для каждой пары узлов коммутации?

10. Когда заканчивается процесс расчета по методу итераций?

Литература

1. Лазарев Ю.В. Анализ сетей электросвязи с обходными направлениями / Методические указания для студентов факультета АЭС. – М.: МЭИС, 1984. – 22 с.

2. Семейкин В.Д. Анализ сетей связи с обходными направлениями / Методические указания и контрольные задания по дисциплине «Сети связи» для студентов специальности 200900. – Астрахань: АГТУ, 2001. – 32 с.

3. Лазарев В.Г., Лазарев Ю.В. Динамическое управление потоками информации в сетях связи. – М.: Радио и связь, 1983. – 216 с.

4. Максимов Г.З., Пшеничников А.П. Телефонная нагрузка местных сетей связи. – М.: Связь, 1969. – 151 с.

5. Башарин Г.П. Таблицы вероятностных характеристик и средних квадратичных отклонений потерь на полнодоступном пучке линий. – М.: Изд. АН СССР, 1962. – 128 с.

Работа № 7. Изучение методов маршрутизации на сетях связи

Цель работы: Изучение последовательных методов маршрутизации и оценка сетевых характеристик.

1. Метод оценки сетевых характеристик

1.1. Расчетные формулы и соотношения

Рассмотрим процесс прохождения одиночного пакета по сети.

Процесс прохождения пакета по сети от УК-источника к УК-получателю является всегда случайным, даже в случае фиксированного выбора направления в каждом из промежуточных УК по пути от УК-источника к УК-получателю. Это обусловлено тем, что случайность присутствует в самой среде, состоящей из УК и линий связи (ЛС), вследствие возможного выхода из строя УК и ЛС под действием внутренних и внешних факторов, а также блокировки отдельных направлений. Процесс прохождения пакета по сети при этом является типично дискретным марковским процессом [1].

Если для каждого УК1, который может быть искомым, поставлена в соответствие матрица переходных вероятностей (МПВ) Р⁽¹⁾, то можно получить ряд основных характеристик процесса прохождения пакета по сети посредством решения систем линейных алгебраических уравнений (СЛАУ) [1, 2].

Будем считать, что пакет покидает сеть в двух случаях [3]:

1) пакет достигает искомого УК;

2) пакет «теряется», т.е. не достигает искомого УК вследствие:

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

– засылки сообщения по неправильному адресу из-за искажения адресной части;

– блокировки отдельных направлений.

Для учета потери пакета целесообразно ввести некоторый фиктивный УК₀, которому соответствует дополнительное нулевое состояние МПВ.

Общее число состояний МПВ будет равно N_и+1, где N_и – число УК сети (из них два поглощающих состояния).

Число невозвратных состояний – N_и –1.

Матрица переходных вероятностей Р⁽¹⁾ в каноническом виде выглядит следующим образом [3]:

(7.1)

Матрица P⁽¹⁾ состоит из четырех подматриц: I⁽¹⁾, 0⁽¹⁾, R⁽¹⁾, Q⁽¹⁾.

Первая из них характеризует вероятность перехода из невозвратных состояний в поглощающие.

I⁽¹⁾ представляет собой единичную матрицу. Подматрицы R⁽¹⁾ и Q⁽¹⁾ содержат соответственно вероятности перехода из невозвратных состояний в поглощающие и из невозвратных в невозвратные.

Матрица N⁽¹⁾ = (I – Q⁽¹⁾) ^–1 называется фундаментальной матрицей поглощающей цепи Маркова. Используя N⁽¹⁾, можно получить ряд сетевых характеристик при поиске УК1.

Вероятность потерь пакета и успешного достижения пакета конечного УК1 (доставка пакета по заданному адресу) будут соответственно содержаться в первом и втором столбцах матрицы В⁽¹⁾ :

B⁽¹⁾ = N⁽¹⁾ * R⁽¹⁾. (7.2)

Главными показателями функционирования сети связи с КП являются: вероятность доставки пакета по заданному адресу Р_дост и время задержки при доставке пакета между УК сети. Обозначил через t‾ ⁽¹⁾ – вектор задержек пакета между каждым УК и искомым УК1, а через τ ⁽¹⁾ – вектор задержек пакета на УК сети при поиске УК1.

Тогда вектор t ⁽¹⁾ будет определяться следующим образом [3]:

, (7.3)

где , (7.4)

, (7.5)

. (7.6)

Векторы r₂⁽¹⁾ и b₂⁽¹⁾ – вторые векторы-столбцы, соответственно подматриц R⁽¹⁾ и В⁽¹⁾.

Вектор

, (7.7)

где n_s – максимальный ранг УК сети.

Для определения τ_и⁽¹⁾ кратко рассмотрим работу УК сети связи.

На вход блока управления УК поступают потоки пакетов со всех входящих направлений. С выхода блока управления пакеты поступают в выходные буферы по исходящим направлениям. Оповестительные сигналы об уровнях загрузки выходных буферов направляются также на блок управления (БУ).

Анализируя пакет, БУ может либо вывести его из сети, либо поставить его в одну из очередей. Если пакет адресуется УК_i, то он отправляется к своему абоненту. Если использование направления для передачи невозможно, то пакет выводится из сети и с УК-источника (при получении отрицательной квитанции) происходит повторная передача пакета.

Пусть заданы задержки на буферах, равные соответственно τ(i, j₁),...,τ(i, j_ν),...,τ(i, j_ns) и пусть известны вероятности, с которыми БУ направляет пакеты, адресованные УК1 в тот или иной буфер, равные соответственно:

, (7.8)

тогда задержка пакета, адресованного УК1, на УК_i будет равна:

, , (7.9)

где N_u – число УК сети.

Для построения матрицы воспользуемся идеализированной МПВ – [3].

Идеализированная цепь Маркова содержит только одно поглощающее состояние, соответствующее достижению пакета искомого УК1 . Идеализированная МПВ строится при этом путем трансформации элементов исходной МПВ Р⁽¹⁾ следующим образом:

, (7.10)

где подматрица формируется на базе подматрицы МПВ Q⁽¹⁾ и вектора . Подматрица представляет собой квадратную матрицу размерностью п_S x п_S.

Номера строк и столбцов матрицы соответствуют номерам УК сети.

В 1-й столбец заносятся элементы вектора , причем диагональный (1,1)-й элемент равен единице. Остальные столбцы матрицы получаются из подматрицы исходной МПВ Q⁽¹⁾. Первая строка матрицы единичная. Нужная для расчетов матрица получается в конечном счете из матрицы (10) путем трансформации последней в прямоугольную матрицу размерностью N_u x n_s. Данная трансформация производится в соответствии со структурой сети (берутся только ненулевые элементы).

1.2. Построение матрицы переходных вероятностей

Для построения МПВ используются: план распределения информации на сети и ситуационная таблица (СТ), в которой разыграны все возможные состояния ребер сети (для УК) с учетом всевозможных факторов [3]. Построение плана распределения информации осуществляется в три этапа по следующей схеме: МИВ—>ТВКП—>ТМВ—>ТМ, где МИВ – матрица инцидентных весов, ТВКП – таблица весов кратчайших путей, ТМВ – таблица маршрутных весов, ТМ – таблица маршрутизации [4].

Необходимо отметить, что большое влияние на характеристики функционирования сетей с КП оказывают блуждающие в сети по замкнутым кольцевым маршрутам пакеты. Можно добиться при формировании ТМВ полного или частичного устранения этого явления [3]. Частичное устранение петель осуществляется путем преобразования МИВ в матрицу, в которой для УК-источника не учитываются при составлении ТМВ все входящие в него ребра. Полное устранение петель достигается путем алгоритмического поиска и запрещения всех маршрутов, при движении по которым существует вероятность возращения в уже пройденный УК.

Перейдем к построению ситуационной таблицы СТ.

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

N_max = Kn_s , (7.11)

где К – число укрупненных состояний ребер УК, которые определяются множеством параметров и учитывают вероятности блокировок и ненадежности ребер, живучесть, помехоустойчивость и др. [3].

При построении СТ берутся в расчет вероятности блокировок пакетов и коэффициент готовности К_Г ребер сети. Для данной ситуации (при учете ненадежности ребер сети) можно получить три укрупненных состояния:

1) ребро УК свободно и работоспособно;

2) ребро УК работоспособно, но заблокировано;

3) ребро УК неработоспособно.

В таблицу состояний ребер УК сети связи заносятся номера укрупненных состояний, т.е. в нашем случае это числа 1, 2 и 3. Цифра 1 соответствует 1-му укрупненному состоянию, когда ребро УК свободно и работоспособно. Цифра 2 соответствует 2-му укрупненному состоянию, когда ребро УК работоспособно, но заблокировано. Цифра 3 соответствует 3-му укрупненному состоянию, когда ребро УК неработоспособно. Процедура формирования таблицы состояний ребер УК позволяет получить набор всех возможных состояний ребер для УК сети путем циклического сдвига элементов таблицы. Число таких ситуаций равно N_max. Произведем оценку вычислительной сложности процедуры. Число операций деления пропорционально n_s , а число сложений – n_{s *} N_max.

Переходим непосредственно к описанию СТ.

Для каждого УКi существует (N_s – 1) CТi¹ (при поиске УК⁽¹⁾). Индекс i означает номер УК-источника. В общем случае СТ содержит в полном объеме предписания на случай любой из возможных на УKi ситуаций, возникающих к моменту принятия решения о выборе исходящего направления передачи пакета. Решения о выборе исходящего направления принимается с учетом сведений о ТМ и состояния рассматриваемого УК (исходящих направлений), т.е. СТ является формальной записью алгоритма маршрутизации для конкретной сети в заданных условиях эксплуатации.

Общее число состояний работоспособного УКi равно Кⁿ (n – число исходящих ребер УКi).

Число строк CTi⁽¹⁾ равно Кⁿ. Число столбцов равно числу исходящих ребер (направлений) плюс 4. В первом столбце пронумерованы просматриваемые ситуации. Во второй столбец занесен код ситуации (формализованная запись), показывающий в каком состоянии находится каждое из исходящих направлений. Код ситуации выбирается из таблицы состояний ребер УК, при этом просматриваются первые Кⁿ строк и первые n столбцов таблицы (Kⁿ ≤ N_max, n ≤ n_s).

В третьем столбце указана вероятность возникновения этих ситуаций:

(ξ_m⁽¹⁾ (i, j₁),…, ξ_m⁽¹⁾ (i, j_ν),…, ξ_m⁽¹⁾ (i, j_n). (7.12)

В следующие n столбцов заносятся вероятности выбора каждого из направлений при поиске УК1.

Для учета потерь введен фиктивный узел УК₀. Вероятности потерь заносятся в столбец ξ_m⁽¹⁾(i, j₀).

Столбцы заполняются по ТМ УКi, а столбец Ω(m) заполняется на основании матрицы вероятностей блокировок буферов (из-за переполнения) коэффициентов ребер сети.

Рассмотрим подробнее СТ, построенную для УК1, имеющего три исходящих направления. Анализируется ситуация на сети, когда приходится учитывать надежности элементов сети. Передача пакета будет происходить по ребру (направлению) в том случае, если оно работоспособно и свободно.

Общее число состояний на УК равно Kⁿ = 3 ³ = 27.

Первые восемь состояний характеризуют ситуации, в результате возникновения которых пакет не будет передан из УКi, так как ни одно из направлений не может служить для передачи пакета. Это подмножество характеризует ситуацию, когда пакет теряется на УKi. Во всем множестве Кⁿ состояний можно выделить А подмножеств, которые характеризуют возможность передачи пакета из УКi:

, (7.13)

где i – количество исходящих направлений, по которым не может осуществляться передача пакета. В рассматриваемом примере возможно следующее значение А (при n = 3):

А = С₃³ + С₃² + С₃¹ + С₃⁰ = 1 + 3 + 3 + 1 = 8.

Количество слагаемых в формуле (13) показывает количество возможных реализаций событий (пакет передан на УKi). В рассматриваемом примере их четыре: первое слагаемое – передача пакета не может осуществляться ни по одному из исходящих направлений (количество реализаций равно 1); второе слагаемое – передача пакета может осуществляться по единственному направлению (количество реализаций равно 3); третье слагаемое – передача пакета может осуществляться по одному из двух возможных направлений (количество реализаций равно 3); четвертое слагаемое – передача пакета может осуществляться по любому из исходящих направлений (единственная реализация).

Для CTi⁽¹⁾ должны выполняться условия нормировки [3]:

для , (7.14)

. (7.15)

Условие (14) говорит о том, что пакет, попав в УКi , или выйдет из него по одному из исходящих направлений, или потеряется в нем, а условие (15) показывает, что в момент принятия решения, УКi должен находиться в одном из возможных состояний.

Пользуясь ситуационной таблицей СТ, можно рассчитать по формуле полной вероятности элементы строки МПВ, соответствующей УКi при поиске УК1 [3]:

. (7.16)