Математическая модель анализа многоадресной маршрутизации в мультисервисной сети связи

УДК 004.725.7

В.О. Жарикова, С.Н. Новиков

Математическая модель анализа многоадресной маршрутизации в мультисервисной сети связи

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

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

Известно, что протоколы сетевого уровня значительно влияют на функционирование сети связи и параметры качества обслуживания (QoS) приложений [1]. Проведение экспериментальных исследований на действующих МСС с использованием различных методов маршрутизации связано с техническими, организационными и финансовыми трудностями. Одним из решений данной проблемы является разработка математической модели функционирования МСС. В настоящее время анализу функционирования протоколов сетевого уровня посвящено множество работ [1-5, 9]. Предложены математические модели функционирования МСС, учитывающие в том числе самоподобный трафик при одноадресной маршрутизации [2]. Однако вопросы анализа функционирования МСС с учетом протоколов многоадресной маршрутизации рассмотрены недостаточно. В связи с этим возникает необходимость разработки подобных моделей.

1. Определение исходных данных, ограничений математической модели и критериев анализа функционирования МСС

Исходные данные.

1. Представим структуру сети связи в виде неориентированного графа G(As Ls s), где As -

множество вершин графа, As = (oq,..,щ,..,as); S- количество узлов коммутации (УК); Ls s - множество ребер графа, отражающих линии связи (ЛС); Ls s = {lj}, i, j = 1,S;i Ф j, причем lj = (0,1). В каждой ЛС lj имеется kj каналов связи (КС), i, j = 1,S;i Ф j; K = ||kj|| - матрица КС в ЛС.

2. Тяготение узлов-источников (УИ) ai и групп узлов-получателей (УП) aj при поступлении потока данных r-го приложения в МСС, зададим матрицей тяготений Пмк:

Пr =||nri/||s s ; 0 —nrij —1 ; Cnrij = 1 . i,j

3. Поступающий в сеть связи поток данных r-го приложения считается самоподобным:

x

, X > 0,

f (х) =

1 xk-1e 0 , X >(

0k Г

0, x < 0,

да

где Г (к) =| хк 1е xdx, с параметрами кг - количество сообщений, поступающих на обслуживание;

0

0 - параметр гамма-распределения.

4. Закон распределения длительности обслуживания заявки в каждом УК подчиняется экспоненциальному закону:

М-об (^дл ) = Мдл.ге Мдлг дл с параметром: |Мдл г - интенсивность обслуживания сообщения г-го приложения.

5. Метод маршрутизации [2] Ы{.

Ы\ - лавинный, формирование дерева с корнем в УИ при последовательном выборе исходящих трактов передачи сообщений (ИТПС);

М2 - игровой, формирование дерева с корнем в УИ при параллельном выборе ИТПС;

М3 - лавинный, формирование остового дерева при последовательном выборе ИТПС;

М4 - игровой, формирование остового дерева при параллельном выборе ИТПС представим в

виде таблиц маршрутизации (ТМ) Р^^) =

рмк(Г) Гг у

; г,у = 1,5, где Ргмк(Г)гу - вероятность перехо-

5,5

да из узла г в узелу при поиске ?-го узла группы получателей для г-го приложения.

Ограничения математической модели

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

2. Элементы сети (УК, ЛС) абсолютно надежны.

3. Пакеты, поступающие в сеть постоянной длины.

Определение критериев анализа функционирования МСС

В качестве критериев оценки функционирования МСС примем:

1) дифференциальную оценку качества обслуживания пользователей для г-го приложения,

Рг = 11^| ; Ру ;г,у = 1,5;г Ф у - вероятность блокировки г-го приложения между г-м иу-м УК;

2) интегральную оценку качества обслуживания пользователей; Ро г - вероятность блокировки г-го приложения в целом по МСС.

Таким образом, будем оценивать функционал {Рг ;Р0,г} = Е{О(Л3,К3,5);Пг,Х,ц,Мг} .

2. Математическая модель входящих информационных потоков

Чтобы случайный процесс являлся самоподобным, должны выполняться следующие условия:

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

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

Воспользуемся следующими свойствами гамма-распределения:

1) если Х1,X2Хп - независимые случайные величины, такие что Xг- ~Г(кг-,0), то

п ( п Л

I = ХXi ~ Г X кг ,0

г=1

М=1

2) если X ~ Г(к,0), и а > 0 - произвольная константа, то аХ ~ Г(к,а0) .

Пусть на вход сетевого элемента поступают пакеты данных от различных УИ. Поступающие потоки образуют гамма-распределение с параметрами к, 0 . Тогда суммарный поток на входе сетевого элемента также образует гамма-распределение:

Л = ХХг- ~г[£кг-,0^ = Г(К,0).

г=1 V. г =1 у

Математическое ожидание и дисперсия суммарного потока равны соответственно

п п

М[X] = 0^кг =0-К ; ЩХ] = 02 Xк =02 • К.

г=1 г=1

3. Математическая модель маршрутизации на сети связи

Таблица маршрутизации строится в результате работы имитационных алгоритмов маршрутизации, представленных в [8].

Пусть Лж - общая интенсивность потока информации многоадресного трафика. Следовательно, выражение

Л^г =П^ Лмк,

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

Тогда объединенный во входной части сетевого элемента поток для Е -дерева распределяется в

соответствии с таблицами маршрутизации на выходные потоки Х1 = Л^,гР, Х2 = Л^,гР2,

94 МАТЕМАТИЧЕСКОЕ ОБОСНОВАНИЕ И ТЕОРЕТИЧЕСКИЕ АСПЕКТЫ ИНФОРМАЦИОННОЙ БЕЗОПАСНОСТИ ..., Хп =Л^,гРг. В соответствии со свойством (1) гамма-распределения выходные потоки Х^ будут также иметь гамма-распределение:

Н=Ч,грі ~ г(к-р ,0)=Г

С п ^

Рі I к у ,0 , І=1 .

Математическое ожидание и дисперсия в этом случае

М[X] = р-0-К = р .01*,- , Щ[Х] = 02КРі =02Рі- .

у=і у=і

В результате, согласно особенности многоадресной маршрутизации, которая заключается в передаче одной и той же информации от УИ к группе получателей, распределение интенсивности потока Х^ г по одному из деревьев оптимальных маршрутов будет таким, как показано на рис. 1.

Рис. 1. Пример распределения интенсивности потока информации по дереву оптимальных маршрутов

В результате формируется взвешенный граф сети связи, ребрам которого присвоены интенсивности проходящих потоков данных:

хмкЕ,г=ЛЕ,лмк;к’1=15.

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

- нагрузка, создаваемая в процессе формирования ТМ информации на сети связи;

- нагрузка, создаваемая в процессе построения дерева многоадресных маршрутов;

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

Соотношения для поиска величины нагрузки при различных методах маршрутизации приведены в [8].

4. Математическая модель сетевых элементов

Представим маршрутизатор в терминах системы массового обслуживания - О/М/1Ш, с абсолютным приоритетом обслуживания. На рис. 2 приведена модель маршрутизатора, где Хвх - интенсивности пакетов данных, поступающих на г-й вход сетевого элемента; ц - производительность обслуживающей линии маршрутизатора; Ру - вероятность выбора у-го исходящего тракта передачи

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

5. Вероятность блокировки СМО с ограниченным буфером при входящем гамма-потоке Известно [6], что вероятность блокировки в системе массового обслуживания О/М/1/Ы вычисляется по формуле

1-ст N

Рм = !1^+гст ’

где ст - единственное решение уравнения

к

здесь к - преобразование Лапласа-Стильтьеса.

РіН

Накопитель

Рис. 2. Математическая модель маршрутизатора

В

ы

х

о

д

ы

В [7] приведено решение уравнения (3) для случаев гамма-распределения различного порядка. В общем случае решение уравнения (3) сводится к решению уравнений вида

1

(кр)к -ст(1-ст + кр)к = 0, кр-стк (1-ст + кр) = 0,

где р = Х/ц, Х - интенсивность поступления заявок на входе СМО; ц - производительность обслуживающей линии СМО.

Для исследования сетей с самоподобным трафиком коэффициент к должен удовлетворять условию: 0 < к < 1. В этом случае гамма-распределение будет тяжеловесным, т.е. будет выполняться необходимое условие самоподобности трафика.

Для практических исследований подойдет значение коэффициента к = 0,5. При к = 0,5 [7] имеем следующее решение:

1

кр-ак (1 -а+кр) = 0.

Р-а2 [і_ст+Р|=0

, §Н)

2 V 2 У 2

Решение уравнения (4) дает три корня - ст= 1 и два корня уравнения:

-а2

ст2 -£а-Р=0.

Корни уравнения

а Р± Р +Р

а12 = _--------------1—

1,2 4 V16 2

Для определения возможности использования корней уравнения используется условие

0 <ст<1.

Данному условию удовлетворяет лишь один корень уравнения (5):

ст=Р+Я^.

4 V16 2

Подставляя значение решения уравнения (3) в (2), получаем вероятность блокировки системы массового обслуживания Г0,5/М/1/#:

1-а N Рп =-------~а =-

1 Р /£!+£

Р2 16 2

NN

1-а

N +1

NN +1

1-

£^- + £ 4 V16 2

£+Л-+£

4 V16 2

6. Оценка дифференциального критерия качества обслуживания пользователей МСС

Для оценки параметров Рг и Р0 г воспользуемся методами [9], которые сводятся к определению вероятности связности:

1) анализируемого графа - Р0,г ;

2) отдельных вершин графа - Рг .

Выводы

1. Разработана математическая модель функционирования МСС с учетом самоподобного трафика при многоадресной маршрутизации.

2. Математическая модель позволяет проводить целенаправленный анализ параметров качества обслуживания пользователей в МСС при многоадресной маршрутизации.

Литература

1. Вишневский В.М. Теоретические основы проектирования компьютерных сетей. - М.: Техносфера, 2003. - 512 с.

2. Новиков С.Н. Методы маршрутизации на цифровых широкополосных сетях связи: учеб. пособие. - Ч. 1. - Новосибирск: СибГУТИ, 2000. - Ч. 1 - 84 с.

3. Буров А. А. Анализ методов маршрутизации в широкополосных цифровых сетях интегрального обслуживания (Ш-ЦСИО) / А.А. Буров, С.Н. Новиков // Компьютерные учебные программы и инновации. - 2004. - № 6. - 13 с.

4. Математические модели исследования маршрутизации в сетях передачи данных / М.П. Березко, В.М. Вишневский, Е.В. Левнер, Е.В. Федотов // Информационные процессы. - 2001. -Т. 1, № 2. - С. 103-125.

5. Wittmann R. Multicast Communication: protocols and applications / R. Wittmann, M. Zitterbart. -Academic press, 2001. - 369 p.

6. Пономарев Д.Ю. Исследование моделей телекоммуникационных систем с непуассоновски-ми входными потоками // Проблемы информатизации региона. ПИР-2001: сб. науч. тр. - Красноярск: ИПЦ КГТУ, 2002. - С. 145-152.

7. Пономарев Д.Ю. Об обслуживании в системе с входным гамма-потоком [Электронный реcурс]. - Режим доступа: http://www.sbras.ru/ws/YM2004/8510/, свободный (дата обращения: 24.04.2012).

8. Жарикова В.О. Введение в курс «Моделирование систем» методики анализа функционирования методов многоадресной маршрутизации на сети связи // Матер. 53-й (LIII) науч.-метод. конф. «Дидактические особенности образовательного процесса в условиях перехода на новые образовательные стандарты». - Новосибирск: СибГУТИ, 2012. - 110 c.

9. Новиков С. Н. Методы оценки структурной надежности телекоммуникационных систем: учеб. пособие / С.Н. Новиков, Е.В. Сафонов (Методический комплекс). - Новосибирск, 2003. - 44 с.

Жарикова Виктория Олеговна

Ст. преподаватель каф. безопасности и управления в телекоммуникациях (БиУТ) Сибирского государственного университета телекоммуникаций и информатики (СибГУТИ), г. Новосибирск Тел.: (383) 269-82-45, 913-741-73-93 Эл. почта: zharikova_viktoria@mail.ru

Новиков Сергей Николаевич

Канд. техн. наук, доцент, зав. каф. БиУТ, проф. ФГОУ ВПО «СибГУТИ»

Тел.: (383) 269-82-45, 913-923-7234 Эл. почта: snovikov@mbit.ru

Zharikova У.О., Novikov S.N.

A mathematical model analysis of multicast routing in multi-service network

The paper presents a mathematical model of the multi-service network for multicast routing, comprising: a model of incoming information flow, routing model, model of network elements (routers).

Keywords: multicast routing, mathematical model, multi-service network.