ТЕНЗОРНАЯ МЕТОДОЛОГИЯ В ИНФОРМАЦИОННЫХ КОММУНИКАЦИЯХ
18 Д. Ю. Пономарев
УДК 519.872.5, 621.391
Д. Ю. ПОНОМАРЕВ
ТЕНЗОРНАЯ МЕТОДОЛОГИЯ В ИНФОРМАЦИОННЫХ КОММУНИКАЦИЯХ
Предложен метод оценки вероятностно-временных характеристик сетей массового обслуживания с использованием математического аппарата тензорного исчисления, позволяющего исследовать указанные сети при их большой размерности.
Ключевые слова: информационно-коммуникационные сети, качество обслуживания, тензорный анализ, среднее время задержки пакета.
Одна из актуальных задач развития современных информационно-коммуникационных сетей — исследование вероятностно-временных характеристик IP-узлов, так как именно данные характеристики позволяют оценить качество обслуживания (QoS — Quality of Service) информационных потоков в этих сетях. Оцениваемыми параметрами при этом являются [1, 2] вероятность потери пакета, среднее время его задержки в системе, дисперсия времени задержки пакета. Однако проектирование рассматриваемых сетей может быть осложнено трудоемкостью расчетов параметров оборудования, позволяющего обеспечить необходимый уровень качества обслуживания, а также топологией сетей и использованием дополнительных протоколов обработки информационных потоков на различных уровнях модели взаимодействия открытых систем (ВОС) [3].
В настоящей статье для оценки вероятностно-временных характеристик (ВВХ) сетей связи предлагается применить математический аппарат преобразования координат (т.е. тензорный анализ сетей), при этом сети рассматриваются как геометрические объекты, проекции которых в различных системах координат различны, но физические свойства самих объектов не изменяются.
Основоположником тензорного анализа сетей является Г. Крон, который впервые использовал тензорный анализ и применительно к теории электрических сетей [4]. Дальнейшее развитие идеи тензорного анализа, в том числе и для информационных систем, получили в работах А. Е. Петрова, А. Е. Арменского, М. Н. Петрова и др. В теории Г. Крона основополагающими являются два постулата, смысл которых заключается в следующем: во-первых, объединение элементов не вносит никаких новых физических явлений, не наблюдаемых в примитивном элементе, а уравнение, описывающее поведение сложной системы, записывается аналогично уравнению состояния примитивного элемента, но в матричном виде; во-вторых, при изменении структуры сложной системы изменяются только элементы матричного уравнения, а переход к описанию новой структуры осуществляется с помощью матрицы перехода C (или A ) [4].
Для использования тензорного подхода в задачах информационных коммуникаций необходимо определить модели процессов и систем исследуемых сетей. В соответствии с работой [3] и общей моделью взаимодействия открытых систем можно определить следующие уровни, на которых необходимо исследовать схемы связи элементов сети: физический, канальный, сетевой. Следовательно, можно выделить несколько различных структур, которые в совокупности будут определять общую модель обработки информационных потоков в исследуемой сети.
Развитие технологий пакетной коммутации привело к тому, что основой для построения современных информационно-коммуникационных сетей является протокол IP, а концепция построения сетей следующего поколения получила название IMS (IP Multimedia Subsystem —
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 5
Тензорная методология в информационных коммуникациях
19
система обработки разнородных информационных потоков с использованием IP) [5]. В сети
IMS основными элементами являются функциональные объекты (ФО) управления соедине-
ниями (CSCF — Call Session Control Function): прокси P-CSCF (Proxy-CSCF), взаимодействия
I-CSCF (Interrogating-CSCF) и обслуживания S-CSCF (Serving-CSCF); различные серверы
(в том числе, HSS — Home Subscriber Server: сервер пользовательской базы данных); ФО рас-
пределения ресурсов среды (MRF — Media Resource Function). Взаимодействие ФО позволяет
определить политику обработки информационных потоков и обеспечить заданное качество
обслуживания.
Рассматривая интерфейсный уровень взаимодействия узлов, любое устройство IP-сети
можно представить в виде сети массового обслуживания, каждая система которой будет моде-
лировать отдельный физический интерфейс устройства передачи информации. Этот интерфейс,
в свою очередь, можно представить в виде одноканальной системы массового обслуживания
(СМО) с условными потерями. Пример модели такого устройства представлен на рис. 1, а.
а) Входные
интерфейсы
Выходные интерфейсы
б)
2
14
7
5
Рис. 1
На следующем уровне можно рассматривать уже не только физические соединения, су-
ществующие между узлами, а учитывать направления передачи информации к узлам сети.
Каждое направление задается СМО, тип которой определяется дисциплиной обслуживания
реальной системы обработки информационных потоков. Кроме того, необходимо отметить,
что основные зависимости исследуемых показателей являются функциями от загрузки систе-
мы: вероятность потерь Pп = f (ρ) и время задержки Tз = ϕ(ρ) , т.е. достаточно знать загруз-
ку системы для определения искомых ВВХ.
На рис. 1, б представлена модель обработки информационных потоков на сетевом уров-
не модели ВОС для сети IMS, где СМО 1 моделирует процесс обслуживания ФО P-CSCF;
СМО 2, 4, 5 — ФО I-CSCF, S-CSCF и MRF соответственно, а СМО 7 — обработку запросов в
сервере HSS.
Значения ВВХ можно использовать для определения показателей качества обслужива-
ния на следующем уровне, так как в реальной сети распределение потоков по узлам подчиня-
ется таблице маршрутизации. В целях расчета ВВХ для каждого маршрута можно записать:
mm
∑ ∑Pп ≈ Pп,i (при малых потерях); Tз = Tз,i , где m определяется числом систем, составi=1 i=1
ляющих данный маршрут передачи информации.
Тензорный анализ ВВХ информационно-коммуникационных систем основан на сле-
дующих предположениях.
1. Поток вызовов с одной и той же интенсивностью ( λ ) поступления определяет при
неизменной интенсивности обслуживания одинаковую загрузку ( ρ ) устройств при изменении
структуры сети; таким образом, можно считать, что будет выполняться соотношение (инва-
риант) [6, 7]:
ρλ = ρ′λ′ ,
(1)
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 5
20 Д. Ю. Пономарев
где переменные ρλ соответствуют одной (исходной) структуре сети, а ρ′λ′ — другой (прими-
тивной). 2. Объединение систем в единую сеть не вызывает никаких изменений процесса обслу-
живания информационного потока, т.е. анализ любой сложной системы (сети) связан с определением простейшего элемента, его свойств и переносом алгоритма анализа на сложную систему (сеть) в целом.
3. Изменение структуры сети не предполагает качественного изменения основных соотношений между физическими величинами, описывающими простейший элемент, а определяет только их численное изменение [4, 6—8].
Исходя из уравнения (1) и применяя соотношение между интенсивностями исходной и
примитивной сетей: λ′ = Cλ , можно записать: ρ′Cλ=ρλ , где С — матрица перехода.* Далее,
находим соотношение между загрузками примитивной и исходной сетей как ρ=CT ρ′ или
( )ρ′= CT −1 ρ . Следовательно, подставив полученное соотношение в выражение ρ = λT , по-
( )лучим CT −1 ρ=T ′Cλ . Таким образом, можно записать ρ=CT T ′Cλ и окончательно
( )CT ρ′ = CT T ′C λ .
(2)
Далее, решая полученное уравнение относительно λ , находим коэффициенты использования устройств в исходной сети. Применительно к сетям связи, исходя из решения уравнения (2), можно найти как вероятность потерь пакетов и время их задержки (и его девиацию), так и оценить пропускную способность сети в целом.
На рис. 2 представлена модель взаимодействия двух коммутаторов (физический уровень), при этом задержки канала связи не учитываются как величины, несоизмеримо малые относительно времени задержки в интерфейсах и в коммутационных элементах. На данном рисунке: СМО 1 и 5 (СМО 7 и 9) обозначают интерфейсы подключения внешних пользователей к исследуемой сети; СМО 3 и 8 являются моделями внутренних коммутационных элементов; СМО 2 и 4 образуют интерфейс подключения к одному коммутатору, а СМО 6 и 10 — к другому, при этом СМО 4 и 6 — входящие интерфейсы, а СМО 2 и 10 — исходящие. Пути передачи информации: 5-3-1 или 5-3-2-6-8-9, 7-8-9 или 7-8-10-4-3-1.
1 3
λb 6
7
2 8
λа 10 9
5 4 λс
Рис. 2
Для применения контурного метода тензорного анализа ВВХ вводятся контурные ин-
тенсивности λa , λb , λc , необходимые для определения связей между СМО в исследуемой сети. В данном случае, задавая направление контурных интенсивностей, определяем матрицу
* Здесь и далее черта над символами означает матрицу.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 5
Тензорная методология в информационных коммуникациях
21
перехода C как соотношение между контурными интенсивностями и интенсивностями в ветвях. Тогда, используя выражение (2), можно записать матричное уравнение, позволяющее определить распределение интенсивностей потоков в сети:
⎛ ρ2 ⎜ ⎜
+
ρ3 ρ1
+ ρ4 − ρ2
+ ρ6 − ρ6
+ ρ8 + ρ7
+
ρ10
⎞ ⎟ ⎟
=
⎛ ⎜ ⎜
Tg −T2 − T6
⎜⎝
−ρ4 + ρ5 + ρ9 − ρ10
⎟⎠
⎜ ⎝
−T4
− T10
−T2 − T6
T1 + T2 + T6 + T7 0
−T4 − T10 0
⎞ ⎟ ⎟
⋅
⎛ ⎜ ⎜
λa λb
⎞ ⎟ ⎟
,
T4
+ T5
+
T9
+
T10
⎟ ⎠
⎜⎝ λc ⎟⎠
где Tg = T2 + T3 + T4 + T6 + T8 + T10 .
Таким образом, определив временные параметры Ti , i = 1…10 , и предварительное распределение загрузок ρi , i = 1…10 , находим одно из возможных распределений интенсивно-
стей в сети как интенсивность ветви: λв = Сλ , где λT = (λa λb λc ) . В данном случае для
размерности множества контурных интенсивностей, равной трем, тензорный подход позволяет получить множество решений, характеризуемых различным распределением загрузки узлов. Далее, используя известные дисциплины обслуживания (M/M/1, M/D/1, M/M/s/N, M/D/1/N и т.д.), можно найти ВВХ отдельной СМО, а следовательно, и вышеуказанных маршрутов передачи информации в целом.
Для решения задачи обеспечения качества обслуживания и управления распределением потоков рассмотрим на примере сети IMS узловой метод тензорного анализа информационно-коммуникационных сетей, основанный на условии λ = µρ (где µ — интенсивность об-
служивания пакетов в СМО). Ранее [6] было показано, что, определяя соответствие между
загрузками исходной ( ρ ) и примитивной ( ρ′ ) сетей через матрицу перехода A как ρ′ = Aρ и
используя выражение (1), можно записать: λ′Aρ = λρ . Далее, находим соотношение между
( )интенсивностями примитивной ( λ′ ) и исходной ( λ ) сетей как λ′ = AT −1 λ . Следовательно,
вектор интенсивностей поступления вызовов в примитивной сети можно определить как
( )AT −1 λ = µ′Aρ . Окончательно уравнение для узлового метода будет иметь вид
( )AT λ′ = AT µ′A ρ .
(3)
Решая полученное уравнение относительно ρ , находим коэффициенты использования
узлов в сети (при загрузке ветвей ρв = Aρ ), что позволяет определить качественные показатели (например, время задержки для маршрута) и распределение интенсивностей потоков по узлам сети как λв = µвρв .
Преобразуем модель, представленную на рис. 1, б, к узловому виду (рис. 3): в местах образования контуров произведем „размыкание“ связей между СМО, но в дальнейшем необходимо учитывать равенство интенсивностей поступления вызовов в соответствующих ветвях, для чего введены мнимые СМО 3 и 6; зададим „узловые загрузки“. Узловые загрузки ρa …ρg ,
представленные на рис. 3, являются элементами вектора ρ , относительно которого решается
уравнение (3). Связь загрузок ρi , i = 1…10 , и узловых загрузок ρa …ρg устанавливается мат-
рицей перехода A . Находя соответствие между загрузками в исходной и примитивной сетях,
определяем матрицу A согласно [9] (ввиду большой размерности здесь не приводится). При этом левая часть уравнения (3) преобразуется к виду (с учетом λ1 = λ2 + λ4 + λ5 , λ7 = λ3 + λ4 + λ6 и λ2 = λ3 , λ5 = λ6 )
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 5
22 Д. Ю. Пономарев
AT λ′ = (0 λ2 −λ2 0 λ5 −λ5 λ7 )T .
Кроме того, так как генератором трафика является СМО 1, то все интенсивности посту-
пления вызовов в остальные СМО могут быть определены через λ1 . С этой целью в уравне-
ние вводятся коэффициенты pi , определяющие долю трафика, поступающего на i СМО. При
этом, исходя из структуры модели сети, необходимо учитывать, что p2 + p4 + p5 = 1. Используя вектор управления, содержащий вероятности разделения нагрузки по узлам
( p2 p4 p5 ) , можно управлять распределением трафика по узлам сети в целях обеспечения
определенного значения среднего времени задержки по заданному маршруту при установ-
ленном значении интенсивности потоков. Например, при заданном λ1 , определенных значе-
ниях интенсивности обслуживания в каждой системе и использовании интерфейса системы
массового обслуживания вида М/М/1 в качестве модели можно, изменяя значения коэффици-
∑ентов
p2 ,
p4 и
p5 ,
определить
общее
среднее
время
задержки
в
сети
как
Tз
=
7 1 µi i=1 1 − ρi
(без
учета мнимых ветвей); ρi определяется как загрузка узлов ρу = Aρ согласно решению урав-
нения (3) относительно ρ . Следует отметить, что зависимость распределения загрузки от λ1
можно получить выбором другого базиса (набора других „узловых загрузок“).
ρc ρg 23 ρb
ρа 4
7
1 ρe
5
6 ρd
ρf
Рис. 3
В качестве преимущества тензорного анализа необходимо также отметить невысокую сложность вычислительного алгоритма. В соответствии с [8] мощность пространства состоя-
ний для однородных замкнутых сетей составляет QNM+−M1 −1 (M — число центров обслужива-
ния, N — количество требований в сети), что естественно приводит к резкому увеличению сложности расчетов показателей работы информационно-коммуникационных сетей, особенно при современном уровне глобализации. Использование вычислительных алгоритмов позволяет снизить сложность определения исследуемых параметров. Например, в работе [8] оценка сложности итерационного алгоритма представлена как 2NM (N + 1) арифметических
операций для определения нормализующей константы, с помощью которой находятся остальные параметры: средняя очередь, среднее время задержки, стационарные вероятности. При определении вероятностно-временных характеристик сети с применением тензорного анализа вычислительная сложность алгоритма обусловливается только количеством узлов и связана с перемножением матриц в соответствии с выражением (2) или (3) в зависимости от метода. Например, при использовании контурного метода количество операций можно оце-
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 5
Тензорная методология в информационных коммуникациях
23
нить как (M − k)(2M 2 + M −1) , где k — количество контуров. Однако в отличие от вычисли-
тельных методов тензорный подход сохраняет возможность аналитического исследования информационно-коммуникационной сети и позволяет использовать полученные результаты для оптимизации сети и управления качеством обслуживания информационных потоков без ограничения на классы потоков и дисциплин обслуживания [9].
В заключение можно сделать следующий вывод: в связи с необходимостью управления большим количеством устройств и обработки множества информационных потоков с заданным качеством обслуживания решение задачи эффективного управления ресурсами сети значительно усложняется. Тензорный анализ сетей — как метод, обладающий возможностями учета взаимодействия процессов и структур и гибкостью применения, — позволяет снизить вычислительные затраты на решение задачи, уменьшить задержки при динамическом управлении информационно-коммуникационными системами и обеспечить хорошую масштабируемость сети как при внедрении новых услуг, так и при изменении структуры и технологий сети. Кроме того, тензорный анализ позволяет достаточно просто формализовать проектные процедуры в целях автоматизации процесса проектирования сетей IMS [10], что обеспечивает повышение качества обслуживания информационных потоков в сетях, работающих на базе стека протоколов TCP/IP, равномерную загрузку устройств сети и снижение времени задержки, обусловленной сетевыми приложениями в транзитных и оконечных узлах сети связи.
Работа выполнена при поддержке Президента Российской Федерации, грант МК2070.2008.9.
СПИСОК ЛИТЕРАТУРЫ
1. Клейнрок Л. Коммуникационные сети. М.: Наука, 1970.
2. Яновский Г. Г. Качество обслуживания в IP сетях // Вестник связи. 2008. № 1. C. 65—74.
3. Braun T., Diaz M., Gabeiras J., Staub T. End-to-End Quality of Service over Heterogeneous Networks. SpringerVerlag Berlin Heidelberg, 2008.
4. Крон Г. Тензорный анализ сетей. М.: Сов. радио, 1978.
5. Гольдштейн А. Б., Гольдштейн Б. С. SOFTSWITCH. СПб: БХВ, 2006.
6. Пономарев Д. Ю. Тензорная методология в телекоммуникациях // Системы управления и информационные технологии. 2006. 1.1(23). С. 161—165.
7. Пономарев Д. Ю. Исследование возможностей тензорного анализа сетей массового обслуживания // Имитационное моделирование. Теория и практика / ИММОД—2007: Сб. докл. Третьей Всерос. науч.-практ. конф. по имитационному моделированию и его применению в науке и промышленности. СПб: ЦНИИТС, 2007. Т. 1. С. 205—209.
8. Вишневский В. М. Теоретические основы проектирования компьютерных сетей. М.: Техносфера, 2003.
9. Пономарев Д. Ю. Исследование возможности использования тензорного анализа сетей к управлению качеством обслуживания в сети IMS // Тр. Третьей Междунар. конф. „Системный анализ и информационные технологии“, САИТ – 2009. М.: ИСА РАН, 2009. С. 722—728.
10. Пономарев Д. Ю. Исследование характеристик пакетных сетей узловым методом тензорного анализа // Программные продукты и системы. 2009. № 4. С. 65—69.
Дмитрий Юрьевич Пономарев
Сведения об авторе — канд. техн. наук, доцент; Институт инженерной физики и радиоэлек-
троники Сибирского федерального университета, кафедра инфокоммуникаций, Красноярск; E-mail: DPonomarev@sfu-kras.ru
Рекомендована кафедрой инфокоммуникаций
Поступила в редакцию 19.03.10 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 5
УДК 519.872.5, 621.391
Д. Ю. ПОНОМАРЕВ
ТЕНЗОРНАЯ МЕТОДОЛОГИЯ В ИНФОРМАЦИОННЫХ КОММУНИКАЦИЯХ
Предложен метод оценки вероятностно-временных характеристик сетей массового обслуживания с использованием математического аппарата тензорного исчисления, позволяющего исследовать указанные сети при их большой размерности.
Ключевые слова: информационно-коммуникационные сети, качество обслуживания, тензорный анализ, среднее время задержки пакета.
Одна из актуальных задач развития современных информационно-коммуникационных сетей — исследование вероятностно-временных характеристик IP-узлов, так как именно данные характеристики позволяют оценить качество обслуживания (QoS — Quality of Service) информационных потоков в этих сетях. Оцениваемыми параметрами при этом являются [1, 2] вероятность потери пакета, среднее время его задержки в системе, дисперсия времени задержки пакета. Однако проектирование рассматриваемых сетей может быть осложнено трудоемкостью расчетов параметров оборудования, позволяющего обеспечить необходимый уровень качества обслуживания, а также топологией сетей и использованием дополнительных протоколов обработки информационных потоков на различных уровнях модели взаимодействия открытых систем (ВОС) [3].
В настоящей статье для оценки вероятностно-временных характеристик (ВВХ) сетей связи предлагается применить математический аппарат преобразования координат (т.е. тензорный анализ сетей), при этом сети рассматриваются как геометрические объекты, проекции которых в различных системах координат различны, но физические свойства самих объектов не изменяются.
Основоположником тензорного анализа сетей является Г. Крон, который впервые использовал тензорный анализ и применительно к теории электрических сетей [4]. Дальнейшее развитие идеи тензорного анализа, в том числе и для информационных систем, получили в работах А. Е. Петрова, А. Е. Арменского, М. Н. Петрова и др. В теории Г. Крона основополагающими являются два постулата, смысл которых заключается в следующем: во-первых, объединение элементов не вносит никаких новых физических явлений, не наблюдаемых в примитивном элементе, а уравнение, описывающее поведение сложной системы, записывается аналогично уравнению состояния примитивного элемента, но в матричном виде; во-вторых, при изменении структуры сложной системы изменяются только элементы матричного уравнения, а переход к описанию новой структуры осуществляется с помощью матрицы перехода C (или A ) [4].
Для использования тензорного подхода в задачах информационных коммуникаций необходимо определить модели процессов и систем исследуемых сетей. В соответствии с работой [3] и общей моделью взаимодействия открытых систем можно определить следующие уровни, на которых необходимо исследовать схемы связи элементов сети: физический, канальный, сетевой. Следовательно, можно выделить несколько различных структур, которые в совокупности будут определять общую модель обработки информационных потоков в исследуемой сети.
Развитие технологий пакетной коммутации привело к тому, что основой для построения современных информационно-коммуникационных сетей является протокол IP, а концепция построения сетей следующего поколения получила название IMS (IP Multimedia Subsystem —
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 5
Тензорная методология в информационных коммуникациях
19
система обработки разнородных информационных потоков с использованием IP) [5]. В сети
IMS основными элементами являются функциональные объекты (ФО) управления соедине-
ниями (CSCF — Call Session Control Function): прокси P-CSCF (Proxy-CSCF), взаимодействия
I-CSCF (Interrogating-CSCF) и обслуживания S-CSCF (Serving-CSCF); различные серверы
(в том числе, HSS — Home Subscriber Server: сервер пользовательской базы данных); ФО рас-
пределения ресурсов среды (MRF — Media Resource Function). Взаимодействие ФО позволяет
определить политику обработки информационных потоков и обеспечить заданное качество
обслуживания.
Рассматривая интерфейсный уровень взаимодействия узлов, любое устройство IP-сети
можно представить в виде сети массового обслуживания, каждая система которой будет моде-
лировать отдельный физический интерфейс устройства передачи информации. Этот интерфейс,
в свою очередь, можно представить в виде одноканальной системы массового обслуживания
(СМО) с условными потерями. Пример модели такого устройства представлен на рис. 1, а.
а) Входные
интерфейсы
Выходные интерфейсы
б)
2
14
7
5
Рис. 1
На следующем уровне можно рассматривать уже не только физические соединения, су-
ществующие между узлами, а учитывать направления передачи информации к узлам сети.
Каждое направление задается СМО, тип которой определяется дисциплиной обслуживания
реальной системы обработки информационных потоков. Кроме того, необходимо отметить,
что основные зависимости исследуемых показателей являются функциями от загрузки систе-
мы: вероятность потерь Pп = f (ρ) и время задержки Tз = ϕ(ρ) , т.е. достаточно знать загруз-
ку системы для определения искомых ВВХ.
На рис. 1, б представлена модель обработки информационных потоков на сетевом уров-
не модели ВОС для сети IMS, где СМО 1 моделирует процесс обслуживания ФО P-CSCF;
СМО 2, 4, 5 — ФО I-CSCF, S-CSCF и MRF соответственно, а СМО 7 — обработку запросов в
сервере HSS.
Значения ВВХ можно использовать для определения показателей качества обслужива-
ния на следующем уровне, так как в реальной сети распределение потоков по узлам подчиня-
ется таблице маршрутизации. В целях расчета ВВХ для каждого маршрута можно записать:
mm
∑ ∑Pп ≈ Pп,i (при малых потерях); Tз = Tз,i , где m определяется числом систем, составi=1 i=1
ляющих данный маршрут передачи информации.
Тензорный анализ ВВХ информационно-коммуникационных систем основан на сле-
дующих предположениях.
1. Поток вызовов с одной и той же интенсивностью ( λ ) поступления определяет при
неизменной интенсивности обслуживания одинаковую загрузку ( ρ ) устройств при изменении
структуры сети; таким образом, можно считать, что будет выполняться соотношение (инва-
риант) [6, 7]:
ρλ = ρ′λ′ ,
(1)
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 5
20 Д. Ю. Пономарев
где переменные ρλ соответствуют одной (исходной) структуре сети, а ρ′λ′ — другой (прими-
тивной). 2. Объединение систем в единую сеть не вызывает никаких изменений процесса обслу-
живания информационного потока, т.е. анализ любой сложной системы (сети) связан с определением простейшего элемента, его свойств и переносом алгоритма анализа на сложную систему (сеть) в целом.
3. Изменение структуры сети не предполагает качественного изменения основных соотношений между физическими величинами, описывающими простейший элемент, а определяет только их численное изменение [4, 6—8].
Исходя из уравнения (1) и применяя соотношение между интенсивностями исходной и
примитивной сетей: λ′ = Cλ , можно записать: ρ′Cλ=ρλ , где С — матрица перехода.* Далее,
находим соотношение между загрузками примитивной и исходной сетей как ρ=CT ρ′ или
( )ρ′= CT −1 ρ . Следовательно, подставив полученное соотношение в выражение ρ = λT , по-
( )лучим CT −1 ρ=T ′Cλ . Таким образом, можно записать ρ=CT T ′Cλ и окончательно
( )CT ρ′ = CT T ′C λ .
(2)
Далее, решая полученное уравнение относительно λ , находим коэффициенты использования устройств в исходной сети. Применительно к сетям связи, исходя из решения уравнения (2), можно найти как вероятность потерь пакетов и время их задержки (и его девиацию), так и оценить пропускную способность сети в целом.
На рис. 2 представлена модель взаимодействия двух коммутаторов (физический уровень), при этом задержки канала связи не учитываются как величины, несоизмеримо малые относительно времени задержки в интерфейсах и в коммутационных элементах. На данном рисунке: СМО 1 и 5 (СМО 7 и 9) обозначают интерфейсы подключения внешних пользователей к исследуемой сети; СМО 3 и 8 являются моделями внутренних коммутационных элементов; СМО 2 и 4 образуют интерфейс подключения к одному коммутатору, а СМО 6 и 10 — к другому, при этом СМО 4 и 6 — входящие интерфейсы, а СМО 2 и 10 — исходящие. Пути передачи информации: 5-3-1 или 5-3-2-6-8-9, 7-8-9 или 7-8-10-4-3-1.
1 3
λb 6
7
2 8
λа 10 9
5 4 λс
Рис. 2
Для применения контурного метода тензорного анализа ВВХ вводятся контурные ин-
тенсивности λa , λb , λc , необходимые для определения связей между СМО в исследуемой сети. В данном случае, задавая направление контурных интенсивностей, определяем матрицу
* Здесь и далее черта над символами означает матрицу.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 5
Тензорная методология в информационных коммуникациях
21
перехода C как соотношение между контурными интенсивностями и интенсивностями в ветвях. Тогда, используя выражение (2), можно записать матричное уравнение, позволяющее определить распределение интенсивностей потоков в сети:
⎛ ρ2 ⎜ ⎜
+
ρ3 ρ1
+ ρ4 − ρ2
+ ρ6 − ρ6
+ ρ8 + ρ7
+
ρ10
⎞ ⎟ ⎟
=
⎛ ⎜ ⎜
Tg −T2 − T6
⎜⎝
−ρ4 + ρ5 + ρ9 − ρ10
⎟⎠
⎜ ⎝
−T4
− T10
−T2 − T6
T1 + T2 + T6 + T7 0
−T4 − T10 0
⎞ ⎟ ⎟
⋅
⎛ ⎜ ⎜
λa λb
⎞ ⎟ ⎟
,
T4
+ T5
+
T9
+
T10
⎟ ⎠
⎜⎝ λc ⎟⎠
где Tg = T2 + T3 + T4 + T6 + T8 + T10 .
Таким образом, определив временные параметры Ti , i = 1…10 , и предварительное распределение загрузок ρi , i = 1…10 , находим одно из возможных распределений интенсивно-
стей в сети как интенсивность ветви: λв = Сλ , где λT = (λa λb λc ) . В данном случае для
размерности множества контурных интенсивностей, равной трем, тензорный подход позволяет получить множество решений, характеризуемых различным распределением загрузки узлов. Далее, используя известные дисциплины обслуживания (M/M/1, M/D/1, M/M/s/N, M/D/1/N и т.д.), можно найти ВВХ отдельной СМО, а следовательно, и вышеуказанных маршрутов передачи информации в целом.
Для решения задачи обеспечения качества обслуживания и управления распределением потоков рассмотрим на примере сети IMS узловой метод тензорного анализа информационно-коммуникационных сетей, основанный на условии λ = µρ (где µ — интенсивность об-
служивания пакетов в СМО). Ранее [6] было показано, что, определяя соответствие между
загрузками исходной ( ρ ) и примитивной ( ρ′ ) сетей через матрицу перехода A как ρ′ = Aρ и
используя выражение (1), можно записать: λ′Aρ = λρ . Далее, находим соотношение между
( )интенсивностями примитивной ( λ′ ) и исходной ( λ ) сетей как λ′ = AT −1 λ . Следовательно,
вектор интенсивностей поступления вызовов в примитивной сети можно определить как
( )AT −1 λ = µ′Aρ . Окончательно уравнение для узлового метода будет иметь вид
( )AT λ′ = AT µ′A ρ .
(3)
Решая полученное уравнение относительно ρ , находим коэффициенты использования
узлов в сети (при загрузке ветвей ρв = Aρ ), что позволяет определить качественные показатели (например, время задержки для маршрута) и распределение интенсивностей потоков по узлам сети как λв = µвρв .
Преобразуем модель, представленную на рис. 1, б, к узловому виду (рис. 3): в местах образования контуров произведем „размыкание“ связей между СМО, но в дальнейшем необходимо учитывать равенство интенсивностей поступления вызовов в соответствующих ветвях, для чего введены мнимые СМО 3 и 6; зададим „узловые загрузки“. Узловые загрузки ρa …ρg ,
представленные на рис. 3, являются элементами вектора ρ , относительно которого решается
уравнение (3). Связь загрузок ρi , i = 1…10 , и узловых загрузок ρa …ρg устанавливается мат-
рицей перехода A . Находя соответствие между загрузками в исходной и примитивной сетях,
определяем матрицу A согласно [9] (ввиду большой размерности здесь не приводится). При этом левая часть уравнения (3) преобразуется к виду (с учетом λ1 = λ2 + λ4 + λ5 , λ7 = λ3 + λ4 + λ6 и λ2 = λ3 , λ5 = λ6 )
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 5
22 Д. Ю. Пономарев
AT λ′ = (0 λ2 −λ2 0 λ5 −λ5 λ7 )T .
Кроме того, так как генератором трафика является СМО 1, то все интенсивности посту-
пления вызовов в остальные СМО могут быть определены через λ1 . С этой целью в уравне-
ние вводятся коэффициенты pi , определяющие долю трафика, поступающего на i СМО. При
этом, исходя из структуры модели сети, необходимо учитывать, что p2 + p4 + p5 = 1. Используя вектор управления, содержащий вероятности разделения нагрузки по узлам
( p2 p4 p5 ) , можно управлять распределением трафика по узлам сети в целях обеспечения
определенного значения среднего времени задержки по заданному маршруту при установ-
ленном значении интенсивности потоков. Например, при заданном λ1 , определенных значе-
ниях интенсивности обслуживания в каждой системе и использовании интерфейса системы
массового обслуживания вида М/М/1 в качестве модели можно, изменяя значения коэффици-
∑ентов
p2 ,
p4 и
p5 ,
определить
общее
среднее
время
задержки
в
сети
как
Tз
=
7 1 µi i=1 1 − ρi
(без
учета мнимых ветвей); ρi определяется как загрузка узлов ρу = Aρ согласно решению урав-
нения (3) относительно ρ . Следует отметить, что зависимость распределения загрузки от λ1
можно получить выбором другого базиса (набора других „узловых загрузок“).
ρc ρg 23 ρb
ρа 4
7
1 ρe
5
6 ρd
ρf
Рис. 3
В качестве преимущества тензорного анализа необходимо также отметить невысокую сложность вычислительного алгоритма. В соответствии с [8] мощность пространства состоя-
ний для однородных замкнутых сетей составляет QNM+−M1 −1 (M — число центров обслужива-
ния, N — количество требований в сети), что естественно приводит к резкому увеличению сложности расчетов показателей работы информационно-коммуникационных сетей, особенно при современном уровне глобализации. Использование вычислительных алгоритмов позволяет снизить сложность определения исследуемых параметров. Например, в работе [8] оценка сложности итерационного алгоритма представлена как 2NM (N + 1) арифметических
операций для определения нормализующей константы, с помощью которой находятся остальные параметры: средняя очередь, среднее время задержки, стационарные вероятности. При определении вероятностно-временных характеристик сети с применением тензорного анализа вычислительная сложность алгоритма обусловливается только количеством узлов и связана с перемножением матриц в соответствии с выражением (2) или (3) в зависимости от метода. Например, при использовании контурного метода количество операций можно оце-
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 5
Тензорная методология в информационных коммуникациях
23
нить как (M − k)(2M 2 + M −1) , где k — количество контуров. Однако в отличие от вычисли-
тельных методов тензорный подход сохраняет возможность аналитического исследования информационно-коммуникационной сети и позволяет использовать полученные результаты для оптимизации сети и управления качеством обслуживания информационных потоков без ограничения на классы потоков и дисциплин обслуживания [9].
В заключение можно сделать следующий вывод: в связи с необходимостью управления большим количеством устройств и обработки множества информационных потоков с заданным качеством обслуживания решение задачи эффективного управления ресурсами сети значительно усложняется. Тензорный анализ сетей — как метод, обладающий возможностями учета взаимодействия процессов и структур и гибкостью применения, — позволяет снизить вычислительные затраты на решение задачи, уменьшить задержки при динамическом управлении информационно-коммуникационными системами и обеспечить хорошую масштабируемость сети как при внедрении новых услуг, так и при изменении структуры и технологий сети. Кроме того, тензорный анализ позволяет достаточно просто формализовать проектные процедуры в целях автоматизации процесса проектирования сетей IMS [10], что обеспечивает повышение качества обслуживания информационных потоков в сетях, работающих на базе стека протоколов TCP/IP, равномерную загрузку устройств сети и снижение времени задержки, обусловленной сетевыми приложениями в транзитных и оконечных узлах сети связи.
Работа выполнена при поддержке Президента Российской Федерации, грант МК2070.2008.9.
СПИСОК ЛИТЕРАТУРЫ
1. Клейнрок Л. Коммуникационные сети. М.: Наука, 1970.
2. Яновский Г. Г. Качество обслуживания в IP сетях // Вестник связи. 2008. № 1. C. 65—74.
3. Braun T., Diaz M., Gabeiras J., Staub T. End-to-End Quality of Service over Heterogeneous Networks. SpringerVerlag Berlin Heidelberg, 2008.
4. Крон Г. Тензорный анализ сетей. М.: Сов. радио, 1978.
5. Гольдштейн А. Б., Гольдштейн Б. С. SOFTSWITCH. СПб: БХВ, 2006.
6. Пономарев Д. Ю. Тензорная методология в телекоммуникациях // Системы управления и информационные технологии. 2006. 1.1(23). С. 161—165.
7. Пономарев Д. Ю. Исследование возможностей тензорного анализа сетей массового обслуживания // Имитационное моделирование. Теория и практика / ИММОД—2007: Сб. докл. Третьей Всерос. науч.-практ. конф. по имитационному моделированию и его применению в науке и промышленности. СПб: ЦНИИТС, 2007. Т. 1. С. 205—209.
8. Вишневский В. М. Теоретические основы проектирования компьютерных сетей. М.: Техносфера, 2003.
9. Пономарев Д. Ю. Исследование возможности использования тензорного анализа сетей к управлению качеством обслуживания в сети IMS // Тр. Третьей Междунар. конф. „Системный анализ и информационные технологии“, САИТ – 2009. М.: ИСА РАН, 2009. С. 722—728.
10. Пономарев Д. Ю. Исследование характеристик пакетных сетей узловым методом тензорного анализа // Программные продукты и системы. 2009. № 4. С. 65—69.
Дмитрий Юрьевич Пономарев
Сведения об авторе — канд. техн. наук, доцент; Институт инженерной физики и радиоэлек-
троники Сибирского федерального университета, кафедра инфокоммуникаций, Красноярск; E-mail: DPonomarev@sfu-kras.ru
Рекомендована кафедрой инфокоммуникаций
Поступила в редакцию 19.03.10 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 5