Оценка пропускных способностей каналов связи в распределенных сетях передачи данных

Тип работы:
Реферат
Предмет:
ТЕХНИЧЕСКИЕ НАУКИ


Узнать стоимость

Детальная информация о работе

Выдержка из работы

3
ИНФОРМАЦИОННЫЕ СИСТЕМЫ
И ТЕХНОЛОГИИ
ОЦЕНКА ПРОПУСКНЫХ СПОСОБНОСТЕЙ КАНАЛОВ СВЯЗИ В РАСПРЕДЕЛЕННЫХ СЕТЯХ ПЕРЕДАЧИ ДАННЫХ
Нгуен Дык Тай Научный руководитель — д.т.н., профессор Т.И. Алиев
Предлагается решение задачи оценки пропускных способностей каналов связи в распределенных СПД при ограничениях на время доставки пакетов или на стоимость сети. Разработанный метод ориентирован на сети произвольной топологии и позволяет учесть алгоритм маршрутизации, вариант размещения прикладных программ и наборов данных по узлам сети, способ взаимодействия пользователей сети. Разработанные методы положены в основу программного комплекса, позволяющего проводить исследование СПД с учетом особенностей реальных сетей.
Введение
Исследование сетей передачи данных (СПД) предполагает построение математических моделей, позволяющих получить зависимости характеристик исследуемой СПД от структурно-функциональных и нагрузочных параметров. В качестве моделей СПД широко используются модели в виде сетей массового обслуживания (СеМО), в которых узлы, представляющие собой системы массового обслуживания (СМО), отображают задержки при передаче пакетов по каналам связи [1−4]. При этом точные аналитические результаты могут быть получены в том случае, если СеМО является экспоненциальной, т. е. узлы представляют собой СМО типа М/М/1 в символике Кендалла [2]. Задача оценки пропускных способностей каналов связи в СПД с использованием модели в виде разомкнутой экспоненциальной СеМО (РЭСеМО) с однородным потоком заявок была решена методом множителей Лагранжа в [2]. При этом задача решалась как математическая оптимизационная задача, и абсолютно никак не учитывались специфические особенности, присущие реальным распределеным СПД. К числу таких особенностей, в первую очередь, относятся неоднородность трафика, многообразие топологий и алгоритмов маршрутизации и т. д. Учет этих особенностей выполняется на этапе параметризации модели СПД, результаты которого оказывают существенное влияние на адекватность разрабатываемой модели.
В данной работе предлагается решение задачи оценки пропускных способностей каналов связи в распределенных СПД с неоднородным трафиком с учетом топологии сети, алгоритма маршрутизации, варианта размещения прикладных программ и наборов данных по узлам сети, способа взаимодействия пользователей сети. Разработанные методы реализованы в виде программного комплекса, обладающего наглядным графическим интерфейсом и позволяющего проводить исследование СПД с учетом особенностей реальных сетей.
Постановка задачи
Для описания исследуемой СПД используются: 1) структурные параметры, определяющие:
• топологию СПД-
• количество узлов п и каналов связи в СПД-
• тип каналов связи (дуплексный, полудуплексный) —
• стоимостные коэффициенты каналов связи-
• длины каналов связи-
2) функциональные параметры, задающие:
• способ взаимодействия пользователей сети-
• способ маршрутизации для каждого узла СПД в виде маршрутной таблицы, содержащей основной и альтернативный маршруты-
3) нагрузочные параметры:
а) интенсивности Л1 ] потоков сообщений разных типов от пользователей, подключен-
ных к узлам СПД- предполагается, что в сети циркулируют сообщения следующих типов:
• запросы к прикладным программам и наборам данных, размещенных в узлах сети-
• прикладные программы и наборы данных, передаваемые по запросу пользователям-
• результаты выполнения прикладных программ и обработки данных в виде сообщений-ответов-
• текстовые сообщения, которыми обмениваются пользователи-
б) длины сообщений разных типов:
• прикладных программ Ьр и наборов данных Ь0-
13
• запросов к прикладным программам 1р и наборам данных ° -
• результатов выполнения прикладных программ 1р и обработки наборов данных 1о •
• текстовых сообщений 1 Т —
в) средняя длина одного пакета 1П и длина обрамления 1О.
Эти параметры используются для решения задачи параметризации модели СПД, представляемой в виде РЭСеМО, в результате которой задача оценки пропускных способностей каналов связи может быть сведена к задаче оптимизации РЭСеМО методом неопределенных множителей Лагранжа. Задача параметризации модели СПД заключается в пересчете параметров СПД, связанных с неоднородностью потоков, циркулирующих в сети. Кроме того, чтобы решить задачу оценки пропускных способностей каналов связи, необходимо рассчитать потоки пакетов в каналах. При этом расчет потоков реализуется программно на основе заданных внешних интенсивностей потоков сообщений, формируемых пользователями сети, известной топологии и маршрутизации, способов взаимодействия пользователей, а также нагрузочных параметров.
Оптимизация пропускных способностей каналов связи
В качестве модели распределенной СПД будем использовать разомкнутую СеМО, состоящую из т СМО, каждая из которых соответствует определенному каналу связи СПД. Принимается традиционное допущение, что поток пакетов, поступающих в каналы СПД, простейший, и время передачи пакетов в каждом из каналов, определяемое как отношение длины передаваемого пакета 1 п к пропускной способности канала С, распределено по экспоненциальному закону.
Метод расчета характеристик РЭСеМО можно найти в [2]. При этом среднее время доставки пакетов в сети, состоящей из т каналов связи, определяется следующим образом:
п п п 1
Т _ ^^ (к, 1) П
ср ?-I ?-I
Ср к1 11 С (к, 1) Х (к, 1 }п где С (к1) — пропускная способность канала связи (к, 1) — а к1) — среднее число «обращений» к каналу связи (к, I) в процессе передачи пакетов- X (к1) — интенсивность пакетов в канале связи (к, 1). Стоимость? СПД определяется как
п п
? _ ^^ Р (к, 1) С (к, 1) Ц (к, 1), к _1 1 _1
где Р (к1) — стоимостной коэффициент пропорциональности, отражающий стоимость
единицы пропускной способности канала связи (к, 1) — Ц (к1) — длина канала связи.
Задача оптимизации пропускных способностей каналов связи с использованием модели РЭСеМО может решаться в одной из двух постановок.
1. Минимизировать среднее время задержки пакетов в сети Тср при ограничении
на стоимость сети? & lt-? *. В этом случае, с учетом введенных обозначений, пропускная способность канала связи (к, 1) вычисляется следующим образом (к _ 1, п- 1 _ 1, п- к Ф 1):
? '-^^Р (к, 1) Х (к, 1)1ПЦ (к, 1) Р. к1 Ы__УР& lt-
Р (к, 1) Ц
'-(к, Г) к, г/п Ц (к, 1)
С __к1 11__V'- у-*'- & quot-, у 1 /1
Чм) _ в Ц п п + к, 1)1 П • (1)
(к, 1) Ц (к, 1) УУ? в X 1 Ц
/ У г (к, 1/ (к, 1) п^к 1,
) П (к, 1)
к1 11
2. Минимизировать стоимость СПД Б при ограничении на среднее время задержки пакетов в сети Т & lt- Тср. В этом случае пропускная способность канала связи
(к, 1) вычисляется по формуле (к _ 1, п- 1 _ 1, п- к Ф 1):
1 п п _ I, а 1
1 ^^ гг. г^: I 1Л (к, 1)'- п
С (к, 1) _ Т* ^^ в (к 1) а (к,)ПЦ (к, 1) л в Ц + Х (к, 1 /п. (2)
Тср к1 1=1 У Р (к, 1) Ц (к, 1)
Расчет потоков в каналах связи
Чтобы решить задачу определения пропускных способностей каналов связи с использованием формул (1) и (2), необходимо рассчитать интенсивности X (к1) потоков
пакетов в каналах связи на основе заданных внешних интенсивностей потоков сообщений и известного алгоритма маршрутизации в СПД. Кроме того, расчет интенсивностей проводится с учетом выбранного варианта размещения прикладных программ и наборов данных по узлам СПД и заданного способа взаимодействия пользователей сети. Расчет потоков пакетов в каналах СПД состоит из трех этапов.
На первом этапе выполняется расчет интенсивностей Xч пакетов в СПД путем
умножения внешних интенсивностей Л1 ] сообщений от пользователей на число пакетов в одном сообщении:
х] _ кК] & lt-л ] _1, п- * Ф Л
где к _ 1,2,… — количество пакетов в сообщении.
На втором этапе расчет интенсивностей пакетов в каналах связи выполняется на основе вычисленных на первом этапе внешних интенсивностей потоков пакетов, заданных таблиц маршрутизации и вероятности передачи по основному пути. Интенсивности пакетов в каждом из каналов связи рассчитываются по формуле
n n
) (k, 1 = 1, n- к * l), (3)
i=1 j=1
где у — интенсивность пакетов из узла г в узел у- Хи) — доля пакетов (0 & lt- Хи) — 1), проходящих по линии (к, 1), причем должно выполняться условие сохранения потока в
сети:
VX'-j'--V x ('---j'-)
k, l) AJl, k) k=l k=l


l, l = Г- 0, l * i-
(4)
in l=j.
Формула (3) получена из условия, что интенсивность пакетов в канале связи (k, l) должна равняться сумме интенсивностей пакетов по всем путям, которые проходят через этот канал. Для того чтобы найти программно доли пакетов X^ и, следовательно,
интенсивности пакетов в каналах связи, используется обратная рекурсивная процедура, определяющая распределение интенсивностей потоков на паре (i — узел-источник, j -узел-назначение) и суммирующая их при рассмотрении всех пар узлов. Эта процедура реализуется следуюшим образом.
Сканируются все узлы, через которые пакеты могут пройти от узла-источника к узлу-назначению с учетом таблиц маршрутизации, и строится двоичное дерево, причем для каждого узла рассматриваются два пути передачи пакета: основной и альтернативный. СПД отличается от двоичного дерева тем, что ее топология произвольная. Чтобы устранить ситуацию, когда пакеты могут циркулировать в сети бесконечно, используется маскирование узлов, которые уже сканировались: Ма8к[узел]: =Га1ве.
На первом шаге обнуляются все доли Xk'-j) пакетов во всех каналах связи и
маскируется узел-источник i как просканированный узел: Mask[i]:= false.
При вызове рекурсивной процедуры доля пакетов в каждом из каналов связи рассчитается по правилу:
• если следующий рассматриваемый узел является основным и он не маскирован, то доля пакетов в этом канале увеличивается на величину, равную произведению вероятности передачи пакетов по основному пути на долю пакетов предыдущего канала связи-
• если следующий рассматриваемый узел является альтернативным и он не маскирован, то доля пакетов в этом канале увеличивается на величину, равную произведению вероятности передачи по альтернативному пути на долю пакетов предыдущего канала связи.
Рекурсивная процедура вызывается только тогда, когда следующий рассматриваемый узел в процессе сканирования не маскрован и не совпадает с узлом-назначения. Обратный механизм в рекурсивном алгоритме реализуется с помощью массива маскирования Mask[] - после вызова рекурсивной процедуры какой-то пары (узел-источник, узел-назначение), нужно отметить узел-источник как немаскированный: Mask[узел-источник]: =true.
Если основной путь рассматриваемого узла совпадает с узлом-назначения и альтернативный путь этого узла является маскированным узлом, то к доле пакетов основного канала связи добавляется доля пакетов альтернативного, равная произведению вероятности передачи пакета по альтернативному пути на долю пакетов предыдущего канала связи, так как пакеты не могут повторно попадать в один и тот же узел СПД. При этом обеспечивается условие (4).
На рис. 1 показан пример распределения по каналам связи долей пакетов, передаваемых в СПД с интенсивностью от пользователей, подключенных к узлу 1, к пользователям, подключенным к узлу 4. Рекурсивная процедура обозначается как Кь (к,/), где к — узел-источник, / - узел-назначение, И — порядковый номер вызова рекурсивной процедуры.
Рис. 1. Пример распределения долей пакетов Л14
Распределение долей пакетов Х14 в каналах связи для пары (1,4) реализовано с помощью рекурсивной процедуры Я1(1,4) следующим образом. Процедура Я1(1,4) определяет по таблице маршрутизации узла 1 следующие узлы основного пути (узел 3) и альтернативного пути (узел 6), по которым пакет должен пройти от узла 1 к узлу назначения 4. Затем выбирается основной путь (узел 3) и вызывается рекурсивная процедура
Я2(3,4). При этом доля Х14 пакетов в канале (1,3), соединяющем узел 1 и основной
узел 3, будет вычисляться как произведение доли пакетов предыдующего канала (в этом случае она равна 1) и вероятности q передачи пакета по основному пути, т. е. Х ($ = q. В свою очередь, процедура Я2(3,4) снова определяет по таблице маршрутизации узла 3 основной и альтернативный пути, по которым пакет должен пройти от этого узла к узлу назначения. Пусть основным путем является узел назначения 4, а альтернативным — узел 2. Доля Х^^ пакетов в канале (3,4), соединяющем узел 3 и основной
узел 4, будет вычисляться как произведение доли пакетов предыдующего канала (в этом случае она равна q) и вероятности q передачи пакета по основному пути, т. е. X™ = q2. Поскольку узел 4 представляет собой узел назначения, то Я2(3,4) выбирает альтернативный путь от узла 3 к узлу 4 путем вызова процедуры Я3(2,4). При этом, доля Xпакетов равна произведению доли пакетов q предыдующего канала на вероятность (1^) передачи пакетов по альтернативному пути, т. е. Х4 = q (1 — q). Таким образом, рекурсивная процедура сканирует все узлы, по которым пакет пройдет от узла-источника к узлу назначения, рассчитывая доли пакетов в каналах связи. Эта процедура позволяет вычислить интенсивности пакетов в каналах связи, через которые пакеты проходят при передаче от узла-источника до узла назначения, т. е. между одной парой взаимодействующих узлов. Для того чтобы получить интенсивности пакетов разных типов в СПД между всеми узлами, нужно просуммировать интенсивности всех возможных передач для прикладных программ, наборов данных и текстовых сообщений.
На третьем этапе выполняется расчет коэффициентов передач для каждого канала связи (k, l) как отношение интенсивности пакетов в этом канале к суммарной (внешней) интенсивности поступления пакетов в СПД: а (k, i) = Х (k, l) /Х вн., где
n n
Xвн = ^ i j — суммарная (внешняя) интенсивность поступления пакетов в СПД.
i=1 j=1
Расчет потоков пакетов в каналах связи выполняется с учетом способов взаимодействия пользователей сети, которые существенно влияют на результаты расчетов потоков и, следовательно, пропускные способности каналов связи. В работе рассматриваются следующие способы взаимодействия пользователей:
a) RDA (Remote Data Access) — по запросу пользователя прикладная программа или набор данных пересылаются в узел пользователя и обрабатываются в нем-
b) DBS (DataBase Server) — по запросу пользователя прикладная программа и набор данных обрабатываются в узле-сервере, в котором они находятся, и пользователю пересылаются только результаты обработки-
c) AS (Application Server) — прикладные программы в процессе реализации в узле-сервере могут обращаться к наборам данных, расположенным в других узлах сети.
Программный комплекс
Рассмотренный метод оценки пропускных способностей каналов связи СПД реализован в виде программного комплекса, написанного на языке Visual C++ с использованием библиотеки базовых классов MFC с архитектурой Doc/View для удобства разработки и реализации приложений под Windows. Программа работает под ОС Windows 2000/XP с требованием памяти не более 64 Мбайт. Программа имеет наглядный графический интерфейс, позволяющий достаточно просто задавать структурно-функциональные и нагрузочные параметры исследуемой СПД. Программа обладает следующими возможностями:
1) задание топологии исследуемой СПД одним из следующих способов (рис. 2):
• графически путем указания мышкой на экране компьютера местоположения узлов и соответствующих каналов связи-
• автоматически путем выбора из перечня типовых топологий, а именно: «звезда», «кольцо», «дерево», «полносвязная" —
• аналитически путем указания декартовых координат узлов СПД или расстояний между ними (рис. 3) —
2) построение и изменение произвольной топологии с использованием соответствующей матрицы связей (рис. 2) —
3) выбор вариантов распределения прикладных программ и наборов данных по узлам СПД-
4) автоматическое создание всех таблиц маршрутизации в узлах по критерию «количество хостов» или «взвешенного графа» с возможностью изменения таблиц маршрутизации и вероятности передачи пакетов по основному пути-
5) расчет потоков пакетов в каналах связи и параметризация модели СПД-
6) расчет вероятностей передачи пакетов:
• от пользователей к каналам связи-
• между соседними каналами-
• от каналов к пользователям сети-
7) расчет пропускных способностей каналов связи методом множителей Лагранжа-
8) исследование характеристик СПД путем варьирования структурно-функциональных и нагрузочных параметров.
зшм
Рис. 2. Построение и изменение произвольной топологии
Рис. 3. Аналитическое задание топологии
На рис. 4 показан интерфейс для ввода исходных параметров СПД. В этой закладке можно выбрать одну из двух постановок задачи оптимизации: минимизировать стоимость СПД при ограничении на среднее время задержки пакетов в сети или минимизировать среднее время задержки пакетов в сети при ограничении на стоимость сети. Кроме того, интерфейс позволяет задавать такие параметры, как модель взаимодействия, тип каналов связи, длина пакета, длина запросов и ответов разных типов по прикладным программам, наборам данных и текстовым сообщениям.
Рис. 4. Интерфейс для ввода исходных параметров СПД
Рис. 5. Пример результатов оптимизации и расчета характеристик СПД
В закладке «Маршрутизация» отображаются созданные автоматически таблицы маршрутизации для каждого узла по критерию «количество хостов» или «взвешенного графа». Здесь же предусмотрена возможность изменения маршрутов и вероятности, в соответствии с которой пакет (или сообщение) пойдет по основному пути. В закладке «Распределение программ и данных» предоставляется возможность ввода варианта распределения прикладных программ и наборов данных по узлам СПД. В закладке «Интенсивности» задаются значения интенсивностей запросов к прикладным программам и наборам данных и текстовых сообщений.
На рис. 5 представлен пример результатов оптимизации и расчета характеристик СПД. Для заданного времени задержки пакетов в сети программа позволяет рассчитать оптимальные пропускные способности каналов связи, обеспечивающие минимальную стоимость СПД, а также время передачи данных по каждому каналу и загрузку всех каналов связи. Здесь же предусмотрено варьирование пропускных способностей и значения времени передачи пакетов в каналах связи.
Работа пользователя с программой реализуется по следующей схеме:
Заключение
Задача параметризации модели и оценки пропускных способностей каналов связи распределенной СПД, в которой расчет потоков пакетов в сети представляет собой основную часть, реализована в виде программного комплекса, позволяющего исследовать и проектировать реальные СПД с использованием модели в виде разомкнутой экспоненциальной СеМО с учетом специфических особенностей реальных СПД, таких как неоднородность потока поступающих в сеть сообщений, многообразие топологий СПД, способов распределения прикладных программ и наборов данных по узлам сети, способов взаимодействия сети, вариантов маршрутизации.
Литература
1. Клейнрок Л. Теория массового обслуживания. М.: Машиностроение, 1979. 432 с.
2. Клейнрок Л. Вычислительные системы с очередями. М.: Мир, 1979. 598 с.
3. Столлингс В. Современные компьютерные сети. 2-е изд. СПб: Питер, 2003. 783 с.
4. Вишневский В. М. Теоретические основы проектирования компьютерных сетей. М.: Техносфера, 2003. 512 с.

ПоказатьСвернуть
Заполнить форму текущей работой