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

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)

Задание

Для выполнения работы № 7 необходимы следующие исходные данные:

1. Число узлов коммутации (УК) сети – N_u.

2. Максимальный ранг УК сети – N_s.

3. Структура сети – S (N_u, N_s).

4. Метод маршрутизации.

5. Матрица тяготений – L_т (N_u, N_u).

6. Массив интенсивностей потоков в УК сети – λ(N_u).

7. Матрица пропускных способностей каналов – C(N_u, N_u).

8. Матрица коэффициентов готовности ребер сети – K_г(N_u, N_s).

9. Длина пакета – 1/µ.

На основании этих исходных данных формируется план распределения информации (ПРИ). Далее производится оценка сетевых характеристик для меняющегося трафика. На основании полученных результатов необходимо построить графики зависимости времени задержки пакетов Т_ср и вероятности потерь пакетов σ_ср от интенсивности входных потоков λ для градиентных методов маршрутизации и график зависимости вероятности циклообразования Н_ср от λ для градиентно-диффузного или диффузного методов маршрутизации.

Таблица 7.1

Варианты заданий

№ варианта

Число УК сети, Nu

Максимальный ранг УК сети, Ns

Метод маршрутизации

Градиентный равновероятный (Г-РВ)

Градиентный с макс-ным числом кратчайших маршрутов (Г-МЧКМ)

Градиентный пропорциональный числу кратчайших маршрутов (Г-ПЧКМ)

Пропускная способность канала, С (Кбит/c)

№ варианта
Число УК сети, Nu
Максимальный ранг УК сети, Ns
Метод маршрутизации	Градиентно-диффузный (Гр-Д)	Диффузный (Д)
Пропускная способность канала, С (Кбит/c)

Длина пакета – 1/µ = 1280 Бит/с.

Коэффициент готовности канала – K_Г(i, j) = 0,99.

Тяготения на сети – равномерные.

Интенсивности входных потоков пакетов одинаковые для всех УК сети и равны:

λ ( i ) = 1 ÷ 15 пак./c.

На рис. 7.1 показаны структуры сетей (3 варианта).

Рис. 7.1. Структуры сетей связи

Содержание отчета

1. Структура сети и исходные данные.

2. Графики зависимости сетевых характеристик от нагрузки.

3. Анализ полученных результатов.

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

1. Дайте определение маршрутизации и назовите три класса методов маршрутизации.

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

3. По каким признакам классифицируют все методы маршрутизации?

4. Какие методы маршрутизации различают по принципу управления сетью?

5. Как разделяются методы маршрутизации по характеру процесса поиска на сети?

6. Как делятся методы маршрутизации по способу выбора исходящего направления передачи?

7. Как делятся таблицы маршрутизации по виду?

8. Опишите процедуру построения таблиц маршрутизации.

9. Что представляет собой план распределения информации?

10. Что называется марковской цепью? Чем она характеризуется?

11. Что представляет собой марковский процесс? Какими свойствами он обладает?

12. Какие показатели функционирования сети связи с коммутацией пакетов являются главными?

13. Опишите процесс прохождения пакета по сети.

14. Опишите работу узла коммутации сети связи с КП.

15. Как строится матрица переходных вероятностей?

16. Опишите процесс построения ситуационной таблицы.

Литература

1. Райншке К., Ушаков И.А. Оценка надежности систем с использованием графов/ Под ред. И.А.Ушакова. – М.: Радио и связь, 1988. – 208 с.

2. Гладкий В.С., Гавлиевский С.Л. Численные методы анализа процессов маршрутизации на сетях ЭВМ// Программирование, №3. – М.: Наука, 1986. – с. 78 – 87.

3. Данилов А.Н. Сборник лабораторных работ по анализу сетей связи с использованием ПЭВМ. – М.: МТУСИ, 1997. – 58 с.

4. Семейкин В.Д. Маршрутизация на сетях связи. Учебное пособие по дисциплинам: «Сети связи» и «Цифровые сети интегрального обслуживания». – Астрахань: АГТУ, 2003. – 44 с.

5. Филипс Д., Гарсиа-Диас А. Методы анализа сетей. М.: Мир, 1984. – 496 с.