Итерационный метод расчета характеристик магистралей транспортных сетей связи

Аннотация

алгебраический транспортный магистраль связь

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

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

Annotation

ITERATIVE METHOD OF CALCULATION OF CHARACTERISTICS OF HIGHWAYS OF TRANSPORT COMMUNICATION NETWORKS

S.L. Gavlievskiy Samara State Technical University

This article refers to constructing the system of the nonlinear algebraic equations describing streams on branches and units of a network in a stationary mode while transferring packages on a transport highway of a communication network. The decision of system allows calculating time delays and probabilities of packages losses between each pair units of a network, and also streams on branches and units of a network, a delay, probability of blocking and levels of loadings of channels.

Keywords: probability-time characteristics, final discrete Marcov circuits, routing, the routing table, a transport network, a matrix of transitive probabilities, system of the nonlinear algebraic equations.

Основная часть

Вводные замечания. В [1-4] рассмотрена математическая модель, предназначенная для расчета вероятностно-временных характеристик сетей с пакетной коммутацией. В этих работах получены соотношения, позволяющие составить систему нелинейных алгебраических уравнений, описывающую потоки на ветвях сети в условиях статического равновесия. Важнейшей составляющей модели является аппарат конечных дискретных цепей Маркова (КДЦМ) [5]. В работах [1-4] рассмотрен общий подход к расчету элементов матриц переходных вероятностей (МПВ), который может быть использован независимо от способа расчета маршрутных таблиц (МТ). В работе [6] для одного из важнейших и наиболее распространенных частных случаев получены выражения, непосредственно связывающие соответствующие элементы матриц переходных вероятностей с элементами МТ и элементами матрицы вероятностей блокировок ветвей.

Математическая модель для расчета показателей качества обслуживания. Характерной особенностью КДЦМ является то, что по известной МПВ для сети, находящейся в стационарном режиме, используя стандартные матричные операции работы с ней и матрицами, полученными путем обработки МПВ, можно получить широкий спектр характеристик процесса передачи одиночного пакета относительно искомого узла .

Взаимосвязь между отдельными переменными, векторами и матрицами показана в виде диаграммы на рис. 1, а все формулы и расчетные соотношения приведены в [1]. Обозначим через пропускную способность канала, соответствующего ветви , через и - задержку при передаче пакета по ветви и вероятность ее блокировки, через - число мест ожидания, через - поток, поступающий на ветвь , через - уровень загрузки канала , через , , , , , - соответствующие матрицы (вершины 1-6), через (вершина 7) - интенсивность обслуживания.

Из теории массового обслуживания (ТМО) известно, что между элементами этих матриц имеют место следующие соотношения: ; ; . Из этих выражений следует, что для расчета задержки и блокировки на ветвях сети необходимо знать потоки, поступившие на соответствующие системы буфер канал (СБК). Соответствующие параметры рассчитываются в вершинах 9, 21, 37.

Рис. 1 Взаимосвязь отдельных переменных, векторов и матриц

Обозначим через:

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

- - множество узлов соседей -го узла, тогда топологию сети можно задать в виде множества (вершина 10). Обозначим через ранг узла. По определению он будет равен мощности множества : ;

- - МТ -го узла. Она представляет собой матрицу, число строк которой равно рангу узла (числу исходящих из узла направлений), а число столбцов - , где - число узлов сети. МТ содержит полную информацию, необходимую для выбора исходящего из узла направления. Если для каждого узла поставлена в соответствие таблица , то говорят, что задан план распределения информации (ПРИ). Запишем его в виде множества МТ: (вершина 11).

При принятии решения о выборе исходящего из узла направления для дальнейшей транспортировки пакета принимаются во внимание два фактора: состояние этих направлений и МТ данного узла. Введем в рассмотрение вектор состояния узла : , содержащий элементов, которые пронумерованы от 1 до . Каждый элемент вектора может принимать одно из двух значений - 0 или 1. Первой компоненте вектора поставим в соответствие состояние ветви , -компоненте - состояние ветви и соответственно -компоненте - состояние ветви . При этом каждому значению вектора однозначно будет соответствовать - десятичный код (номер) состояния:

, (1)

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

. (2)

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

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

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

. (3)

Для важнейших частных случаев получены выражения, непосредственно связывающие соответствующие элементы МПВ с элементами МТ.

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

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

- МПВ, описывающая процесс передачи пакета по сети при поиске узла (вершина 14), состоит из четырех подматриц: . Подматрица (вершина 15) содержит вероятности перехода из невозвратных состояний в поглощающие. Подматрица содержит вероятности перехода из поглощающих состояний в невозвратные. Подматрица содержит вероятности перехода из поглощающих состояний в поглощающие. Подматрица (вершина 15) содержит вероятности перехода из невозвратных состояний в невозвратные.

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

Матрица (вершина 18) содержит вероятности достижения поглощающих состояний. Вероятность успешной доставки пакетов содержится во втором столбце - (вершина 19).

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

Обозначим через (вершина 22) вектор длин между узлами сети и искомым узлом , а через - единичный вектор, столбец той же размерности, что и , тогда вектор будет равен .

При движении пакета по сети возможно образование циклов, т. е. ситуаций, когда он, прежде чем достигнет искомый , побывает в некоторых узлах неоднократно. Вероятность образования циклов для пакетов, адресованных узлу , содержится в матрице (вершина 23); - элемент, который показывает вероятность попадания в узел для пакета, передаваемого по сети и из узла в узел . Элемент матрицы равен вероятности возвращения пакета в исходный узел . Рассмотрим вектор (вершина 24), -тый элемент которого , тогда элементы этого вектора будут показывать вероятность возвращения в исходное состояние для каждого узла сети при пересылке пакета в узел . В вершине 25 рассчитывается - вектор условных задержек (размерностью ) в узлах сети при условии, что пакет не «застрял» в транзитных узлах, а в вершине 26 - вектор задержек доставки пакетов между каждым узлом и искомым .

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

В вершинах (33)-(36) рассчитываются потоки, поступившие и пропущенные по ветвям сети. Для этого в вершине (33) определяется - вектор суммарных потоков, втекающих в узлы сети и адресованных узлу , в вершинах (34)-(35) рассчитываются и - матрицы интенсивностей соответственно пропущенных и поступивших потоков по ветвям сети, адресованных узлу , а в вершине (36) вычисляется - матрица суммарных интенсивностей, поступивших на ветви сети и адресованных всем узлам сети.

Одной из характерных особенностей аппарата КДЦМ является то, что в результате обработки МПВ рассчитываются параметры качества обслуживания относительно узла сразу для всех узлов сети. При этом сами параметры содержатся в векторах размерности . Очевидно, что для расчета характеристик качества обслуживания между каждой парой узлов необходимо перебрать все узлы, которые могут быть искомыми, и для рассчитать вектора ,,,.

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

Обозначим через (вершины 31-34) среднесетевые характеристики, а именно вероятности успешной доставки пакетов, задержки, число переприемов и вероятности зацикливания пакетов, через (вершина 35) - среднесетевую загрузку сети.

На рис. 2 выделены вершины, непосредственно используемые для расчета потоков. Это позволит более четко увидеть взаимосвязь между матрицами и векторами, используемыми для расчета потоков в стационарном режиме.

Рис. 2 Взаимосвязь между отдельными векторами и матрицами, влияющими на расчет потоков в стационарном режиме

В компактном виде СНАУ, описывающая потоки на ветвях сети, будет выглядеть следующим образом:

. (4)

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

Число различных типов переменных в системе

Из этой таблицы видно, что число приведенных уравнений системы (4) совпадает с числом неизвестных и равно . Это означает, что выполняется одно из необходимых условий существования единственного решения системы. В [1] приведен алгоритм решения этой СНАУ и алгоритм расчета показателей качества обслуживания.

Заключение

Для решения СНАУ (4) использован итерационный метод. Схема итерационного процесса следующая. Задаются начальные условия - потоки на ветвях сети. Перед началом первой итерации они могут быть нулевыми. Затем, перебирая все узлы, которые могут быть искомыми, и используя взаимосвязь, приведенную на рис. 3, вычисляют новые потоки. Полученные после первой итерации потоки используются для второй итерации. Итерационный процесс следует продолжать до тех пор, пока расхождения, достигнутые при расчете потоков на текущей и предыдущей итерациях, не будут меньше наперед заданной величины. При этом делается вывод о том, что решение СНАУ найдено. Обычно число требуемых итераций не превышает 3-5. Заметим, что при некоторых исходных данных решение СНАУ может отсутствовать. Это может иметь место тогда, когда сеть работает в экстремальных условиях. Например, когда нагрузка, поступающая на сеть, такова, что уровни загрузки отдельных ветвей приближаются к некоторому критическому порогу, при достижении которого незначительные колебания нагрузки приводят к резким изменениям потерь, длин очередей, задержкам. Заметим, что нас будет интересовать в основном работа сети в нормальных условиях, не предполагающих резкую перегрузку отдельных каналов.

Библиографический список

Гавлиевский С.Л. Методы анализа мультисервисных сетей связи с несколькими классами обслуживания. М.: ИРИАС, 2010. 365 с.

Гавлиевский С.Л. Математическая модель для анализа сетей с пакетной коммутацией: Вестник Самарского гос. техн. ун-та. Сер. Технические науки, №8. Самара, 2000. С. 63-77.

Гавлиевский С.Л. Итерационный метод расчета характеристик сетей с коммутацией сообщений // Сетеметрия, анализ и моделирование информационно-вычислительных сетей: Межвуз. сб. ст. Куйбышев, 1988. С. 21-27.

Гавлиевский С.Л. Модели для расчета характеристик сетей с коммутацией пакетов. Автоматизация научных исследований: Межвуз. сб. научн. тр. Куйбышев, 1989. С. 58-63.

Кемени Д., Снелл Д. Конечные цепи Маркова. М.: Наука, 1970. 272 с.

Гавлиевский С.Л. Соотношения для расчета элементов матриц переходных вероятностей при использовании простых маршрутных таблиц для сетей с пакетной коммутацией / С.Л. Гавлиевский // Вестн. Самарского гос. техн. ун-та. Сер. Технические науки, №39. Самара, 2005. С. 31-36.

Размещено на Allbest.ru