Содержание к диссертации
Введение
ГЛАВА 1. Анализ задач построения систем сетецентрического типа специального назначения
1.1. Особенности архитектуры сетецентрической системы специального назначения
1.2. Принципы построения инфокоммуникационной среды
1.3. Обоснование выбора показателей качества функционирования системы
1.4. Постановка задачи исследований 40
ГЛАВА 2. Разработка формальной модели сетевой инфраструктуры сетецентрической системы
2.1. Графовая модель и задача размещения центров обработки данных
2.2. Алгоритм размещения центров обработки данных
2.3. Постановка задачи оптимизации обслуженной нагрузки абонентов
2.4. Выводы по главе 2 66
ГЛАВА 3. Методы анализа показателей качества сетецентрической системы
3.1. Вероятностная модель обслуживания трафика 68
3.2. Анализ модели отдельного звена сети
3 3.3. Обоснование метода расчета вероятностей блокировок и величины обслуженной нагрузки
3.4. Выводы по главе 3 83
ГЛАВА 4. Методика практического использования методов и средств расчёта сетецентрических систем
4.1. Инструментальные программные средства 85
4.2. Методика сбора данных для вычислительного эксперимента
4.3. Численный анализ параметров качества сетецентрической системы
4.4. Выводы по главе 4 126
Заключение 127
Список литературы 129
Приложение
- Принципы построения инфокоммуникационной среды
- Постановка задачи исследований
- Постановка задачи оптимизации обслуженной нагрузки абонентов
- Методика сбора данных для вычислительного эксперимента
Введение к работе
Актуальность проблемы
Современная концепция ведения военных действий базируется на новых технологиях, в первую очередь - на информационно-телекоммуникационных технологиях, которые позволяют обеспечить максимально высокие показатели управления такие, как оперативность принятия решений и эффективность взаимодействия участвующих в военных действиях формирований. В рамках осуществления концепции «сетецентрической войны», развивается и соответствующая концепция построения центров обработки данных (ЦОД), как составной части АСУ специального назначения. По сути, данная концепция состоит в информационной интеграции всех участвующих в военных действиях подсистем (единые базы данных разведывательной информации, единые системы и инструментарии планирования операций и др.) на базе единой сети передачи данных.
Сетецентрическая концепция требует объединения всех современных разработок и методологий построения и проектирования распределённых систем, начиная от парадигм проектирования распределённого программного обеспечения (например, GRID, SOA) и заканчивая использованием перспективных средств, отвечающих за передачу данных (например, технология MPLS). Существенно, что применение новой концепции порождает большой объем передаваемой информации, но при этом нерешенным остается вопрос с ограниченной пропускной способностью каналов передачи данных систем специального назначения, что существенно влияет на показатели качества функционирования системы в целом. Из опыта военных операций «Буря в пустыне» и «Свобода Ираку» известно, что из-за ограниченной пропускной способности сетевой инфраструктуры, МО США собственными средствами осуществляло передачу до 20% информации (обслуженная нагрузка), а остальные 80% информации (избыточная нагрузка) передавались через системы связи общего пользования (альтернативные сети), в которых также наблюдались сбои из-за перегрузок.
В диссертационной работе исследуются и разрабатываются методы и средства обоснования архитектуры информационных систем сетецентрического типа специального назначения. Решаются задачи размещения ЦОД в сетецентрической системе (СС) специального назначения и оценки качества функционирования системы в условиях ограниченной пропускной способности каналов передачи данных.
На данный момент существуют два класса моделей и методов для исследования проблемы построения СС. Один класс относится к решению задач дискретной оптимизации размещения центров и покрытия множеств и имеет многочисленные приложения. Другой класс описывает вероятностные модели телекоммуникационных сетей, которые в современной терминологии принято называть мультисервисными моделями. Специфика построения СС требует применения моделей обоих типов, что влечет необходимость проведения комплексных исследований для обеспечения большей адекватности
и достоверности планируемых результатов. Значительный вклад в развитие соответствующих методов сделали следующие отечественные и зарубежные ученые и специалисты: Башарин Г.П., Вишневский В.М., Емеличев В.А., Журавлев Ю.И., Самуилов К.Е., Соколов И.А., Шоргин С.Я., Joshi D, Kelly F., Kleinrock L., Ross K., Spohn M. другие. Все вышеизложенное обосновывает актуальность темы диссертационной работы.
Объектом исследований диссертационной работы является архитектура информационных систем сетецентрического типа специального назначения, построенная на базе ЦОД в составе оборудования телекоммуникационной сети с ограниченной пропускной способностью каналов передачи данных (звеньев сети).
Предметом исследований работы являются методы и средства обоснования и построения архитектуры СС в условиях ограниченных пропускных способностей каналов передачи данных, а также методы анализа показателей качества функционирования СС.
Цель диссертационной работы и задачи исследования. Целью диссертационной работы является разработка моделей и методов, предназначенных для решения задачи размещения ЦОД на телекоммуникационной сети с ограниченной пропускной способностью. Для достижения поставленной цели в работе сформулированы и решены перечисленные ниже основные задачи.
Разработка формальной модели размещения ЦОД на графе сети СС и модели обслуживания трафика абонентов в условиях ограниченной пропускной способности звеньев сети.
Разработка методов для анализа показателей качества функционирования СС, включая построение и анализ вероятностной модели отдельного звена сети и метод расчета величины обслуженной системой нагрузки.
Разработка алгоритмов и инструментальных программных средств для расчета структурных и нагрузочных параметров сетецентрической системы.
Разработка методики сбора исходных данных, расчета параметров сетевой инфраструктуры СС и показателей качества ее функционирования.
Организация и проведение вычислительного эксперимента для анализа структурных и нагрузочных параметров сетевой инфраструктуры СС. Методы исследования. В работе использованы методы теории графов,
теории оптимизации, теории алгоритмов, теории вероятностей и теории телетрафика, методы математического моделирования.
Достоверность полученных теоретических результатов подтверждена вычислительным экспериментом и практической реализацией разработанных методов на телекоммуникационной сети специального назначения.
Научная новизна работы состоит в следующем: 1. Разработана модель СС в виде графа сети и сформулирована задача размещения центров обработки данных.
Исследован и модифицирован метод решения задачи размещения центров на графе сети СС в условиях ограничений на пропускные способности звеньев сети.
Построена вероятностная модель и разработаны методы анализа основных вероятностных характеристик сетецентрической системы - вероятности блокировки запросов абонентов и величины обслуженной сетью нагрузки.
Разработаны алгоритмы, инструментальные программные средства и методика для сбора данных, расчета структурных и нагрузочных параметров СС.
Результаты, выносимые на защиту:
Графовая модель СС и формализованная задача размещения ЦОД. Модель обслуживания трафика, с учетом случайного характера потока запросов абонентов и объема передаваемых блоков данных.
Метод решения задачи размещения центров на графе сети СС в условиях ограничений на пропускные способности звеньев сети.
Вероятностная модель функционирования СС, метод и алгоритм расчета ее основных вероятностных характеристик - вероятности блокировки запросов абонентов и величины обслуженной сетью нагрузки.
Алгоритмы и инструментальные программные средства для численного решения задачи размещения ЦОД и расчета показателей качества СС.
Инженерная методика для поддержки процесса проектирования СС в части расчета и анализа ее структурных и нагрузочных параметров. Результаты вычислительного эксперимента, подтверждающие, что в зависимости от величины предложенной нагрузки абонентов, часть нагрузки не может быть пропущена из-за ограниченной пропускной способности сети. Практическая ценность работы. Математические модели, методы,
вычислительные алгоритмы и программное обеспечение, разработанные в диссертационной работе, предназначены для расчета и анализа структурных и нагрузочных параметров сетецентрической системы при решении задачи размещения узлов АСУ специального назначения на сети с каналами с ограниченной пропускной способностью. Результаты работы могут быть использованы при проектировании СС специального назначения для обоснованного выбора структурных параметров и прогнозной оценки качества функционирования.
Реализация результатов работы. Работа проводилась в рамках ОКР «Акация-М» и ОКР «Наработка», выполняемых в соответствии с планами ФГУП «Концерн «СИСТЕМПРОМ». Реализация результатов работы подтверждена актом о внедрении.
Апробация работы. Основные результаты, изложенные в диссертации, докладывались на:
научной сессии МИФИ «Информатика и процессы управления. Компьютерные системы и технологии» (Москва, 2006, 2007, 2008 г.г.);
VIII всероссийской научно-технической конференции «Повышение эффективности средств обработки информации на базе математического моделирования» (Тамбов, 2006 г.);
IX Международной конференции «Интеллектуальные системы и компьютерные науки» механико-математического факультета МГУ им. М.В. Ломоносова (Москва, 2006 г.);
V Всероссийской научной конференции «Проблемы развития системы специальной связи и специального информационного обеспечения государственного управления России» (Орёл, 2007 г.);
XXXVIII военно-научной конференции «Проблемы развития информационных технологий в системе ВКО РФ» (Тверь, 2009 г.). Публикации. По теме диссертации опубликовано 9 работ, из них 7 - в
трудах всероссийских и международных конференций и 2 статьи - в изданиях, рекомендованных ВАК для опубликования научных положений диссертационных работ.
Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав, заключения, библиографии из 115 наименований, 2-х приложений. Основной текст диссертации содержит 140 страниц текста, 41 рисунка (из них 16 графиков), 24 таблицы.
Принципы построения инфокоммуникационной среды
Из литературы [20,28,29,47,111,79] известно, что задача размещения, записанная в виде целевой функции (2.1) и ограничений (2.2), является обобщенной задачей размещения или задачей (А:,г)-размещения. Так как данная задача является NP-полной [23,24,28], то целесообразным представляется искать приближенное решение задачи размещения. Известно [3,28,32,35,37,67,68,85], что подобную задачу можно решать с помощью набора приближенных алгоритмов: жадного, генетического, лагранжевой релаксации и некоторых других. В диссертационной работе разработан алгоритм решения задачи (А:,г)-размещения центров обработки данных в сетецентрической, основанный на модификации алгоритма М. Спона [104, 105] и применении жадной эвристики В. Хватала [73,95,85].
Жадные алгоритмы часто применяются для решения различных оптимизационных задач [28,32,33,39,48,51,80,84,95]. Основная идея жадного алгоритма состоит в разделении задачи оптимизации на подзадачи и предположении, что последовательность локально оптимальных решений для каждой из подзадач ведет к глобальному решению. Основными понятиями жадных алгоритмов являются [33,42] подзадача, подструктура и жадная эвристика.
На основе перечисленных понятий жадных алгоритмов можно записать этапы решения оптимизационной задачи на основе жадной стратегии [33]: 1. Разработать правило формирования подзадач и эвристическую функцию оценки выбора решения подзадачи. 2. Сформировать оптимальную подструктуру решения подзадачи, используя жадную эвристику. 3. Сформировать алгоритм решения задач путем многократного решения подзадач, используя жадную эвристику. Каждая новая подзадача должна быть меньшей размерности, чем предыдущая. 4. Составить оптимальную структуру решения из оптимальных подструктур. Очевидно, что не для всех задач можно использовать жадный алгоритм при поиске точного решения. Для того чтобы применение жадной эвристики давало глобальный оптимум, можно выделить 2 правила [33,94]: — Свойство жадного выбора: глобальное оптимальное решение можно получить, делая локальный оптимальный (жадный) выбор. Другими словами, при выборе очередного решения текущей подзадачи мы не рассматриваем возникающие подзадачи. — Оптимальная подструктура проявляется в задаче, если в ее оптимальном решении содержатся оптимальные решения подзадач.
Это свойство является основным признаком применимости, как динамического программирования, так и жадных алгоритмов. Так как идеи жадного алгоритма в целом схожи с идеями, лежащими в методе динамического программирования, то доказательство оптимальности жадного алгоритма и методику построения жадного алгоритма можно определить, исходя из структуры решения динамического программирования. Естественно тогда придется искать структуру подзадач динамического программирования. Так в литературе [33] описан следующий подход к построению алгоритма, на основе оптимальный подструктур динамического программирования:
Доказательство оптимальности решения, даваемого жадным алгоритмом для конкретной задачи, также можно проводить на основе использования аппарата матроидов [3,28,96]. Тогда многие задачи, для которых жадный подход позволяет получить оптимальное решение, можно сформулировать в терминах поиска независимого подмножества с максимальным весом во взвешенном матроиде. Подробное описание аппарата матроидов можно найти в работах [3,93,95], а применение матроидов к анализу жадных алгоритмов дано в работах [94,95,96].
Для выбора размещения базовых станций в мобильной сети М. Споном был предложен и описан [105] алгоритм решения задачи (А:,г)-размещения. В диссертационной работе [104] дано описание применения данного алгоритма на практике. Перед описанием алгоритма введем, используемую только в этом подразделе диссертационной работы необходимую систему обозначений, применяемую М. Споном в его статьях.
Приведем пример работы алгоритма Спона, иллюстрация примера приведена на рис. 2.3. Здесь (рис. 2.3А) процедура расчета начинается с выбранной вершины В, причем все значения Domin равны 2, поэтому можно выбрать любую вершину в качестве начальной. Стрелками исходящими из вершины В показан этап построения множества SP, которое для вершины В оказывается равным {F,M]. Так как все вершины в 3 окрестности вокруг вершины В покрываемы, то в качестве покрывающих выбираем вершины из SP (рис. 2.3В) и в 3-окрестности от выбранных вершин меняем значения требуемых коэффициентов покрытия. Замечаем, что у части вершин требуемые коэффициенты покрытия становятся равными 0, а следовательно перемещаем их в множество $ . Далее выбираем вершину из множества 3, с наибольшим значением коэффициента покрытия — это вершина А (рис. 2.1С). Очевидно, что она не являются покрываемой (мощность множества У равна 1, а само множество равно { }), поэтому переводим вершину в множество 3 и корректируем значения коэффициентов покрытия в соседних вершинах в пределах 3-окрестности. Далее снова выбираем вершину с наибольшим значением коэффициента. Из вершин с одинаковым значением коэффициента выбираем вершину G (рис. 2.3D). Для этой вершины все соседи покрываемы (также как и сама вершина), а, следовательно, покрывающей вершиной выбирается Н. После корректировки значений коэффициента покрытия, во множестве 3 остается только вершина N, которая переносится в множество 3) (см. рис. 2.3Е). Таким образом, в результате работы алгоритма получаем множество 9 = {F,M,A,H,N] (см. рис. 2.3F).
Постановка задачи исследований
Предположим, что в модели сети СС (например, показанной на рис. 3.1), все звенья сети, кроме некоторого звена е , имеют неограниченные ресурсы для обслуживания запросов абонентов, т.е. Се = для еФе . Задача анализа блокировок в такой системе сводится к анализу сети, состоящей из одного звена е , с одним ЦОД f, который передает блоки данных различных типов из множества Л = {!,...,N]. Отметим, что в литературе эту задачу называют задачей анализа отдельного звена сети (stand alone link) [88,100]. Для удобства записи далее во всех обозначениях индексы е и t опускаются.
Итак, рассмотрим модель звена сети емкости С условных единиц, схематично изображенную на рис. 3.3. По звену передаются блоки данных N типов, запросы на передачу л-блока образуют пуассоновский поток интенсивности Яп, размер блока является случайной величиной, распределенной экспоненциально со средним вп, а величина предложенной п -блоками нагрузки вычисляется по формуле ап — Япвп. Блоки любого типа характеризуются минимальным требованием Ъ к емкости звена, а их обслуживание производится по дисциплине разделения процессора (англ. PS - Processor Sharing). С вероятностью Вп л-блок может получить отказ в обслуживании, если в момент его поступления свободны менее Ъ из С единиц емкости звена. Заметим, что использование дисциплины обслуживания PS является стандартным приемом при моделировании процесса передачи эластичного трафика. ах=\вх
Пусть Xn{t) - число передаваемых в момент t л-блоков, тогда составной случайный процесс (СП) lx(t) = (X](t),...,XN(t) ) t 6\ описывает функционирование модели над пространством состояний
Иллюстративно, режим обслуживания в рассматриваемой модели показан на рис. 3.4. В сделанных выше предположениях СП Х(/) является Марковским процессом и, нетрудно убедиться, что равновесное распределение вероятностей его состояний лг(х) определяется из системы уравнений локального баланса (х) «( уГ=;г(х "е И хє5Г х« 0 пєЛ (3-5) где еп - вектор, «-я компонента которого равна 1, а остальные - 0. Заметим, что в (3.5) величина ( . ,-) Схп/вп соответствует интенсивности обслуживания л-блока в состоянии хє.9Г, поскольку обслуживание производится по дисциплине разделения процессора (PS).
Используя известное [16,21,91] для систем массового обслуживания с дисциплиной PS решение, получаем стационарное распределение состояний СП Х(ґ) в мультипликативном виде: (3.6) где G(9L) = 7T (О) - нормировочная константа. Ниже в данном разделе получено аналитическое выражение для вычисления вероятностей Вп, пє JV. В общем виде вероятность блокировки запроса на передачу «-блока определяется по следующей формуле Вп:=?{хє.%), (3.7) где множество состояний системы, в которых происходят блокировки, имеет вид Гп:=\хєЖ: /][ ,+l\ СІ. (3.8) Представим пространство состояний модели Ж в виде -77 Ж:=1)ж{с), (3.9) с=0 (3.10) (3.11) где Cb:=[C/bj 5Г(с):=хє5Г: Хх«=с] I пел J и обозначим 7(с):=Р(хє5Г(с)), c = 0,...,Q. (3.12) Заметим, что по определению величина #(с) является вероятностью того, что в системе заняты с условных единиц общей емкости звена. Используя уравнения локального баланса (3.5), и приняв х- 0 для некоторого j є JV , получаем, что Заметим, что вероятность блокировки блока данных Вп не зависит от его длины (см. формулу (3.18)), что объясняется одинаковым для блоков любого типа требованием b к емкости звена. В этих условиях формулу (3.18) можно также получить, проведя анализ системы массового обслуживания типа М G 1 PS с нагрузочным параметром а, емкостью прибора С и максимальным числом находящихся на обслуживании заявок Сь. Распределение вероятностей состояний такой системы имеет вид (3.15)-(3.16).
Обзор литературы показывает, что предположение о независимости блокировок на звеньях сети, значительно облегчающее исследование, лежит в основе приближенного расчета вероятностей блокировок в сети - метода просеянной нагрузки (Reduced load approximation). Этот метод впервые был предложен в 1960-х гг., а в середине 1980-х гг. появились фундаментальные работы на эту тему [88,89,111]. В них В. Уитт и Ф. Келли в исследовали метод просеянной нагрузки в сетях с одноадресными одноканальными соединениями (передача речи), где соединение занимает на звеньях маршрута одну единицу ШПП. Кроме того, Ф. Келли сделал попытку обобщить полученные результаты на сети с многоканальными соединениями — сети, в которых требования классов соединений к ширине полосы пропускания звеньев различны. Применению метода просеянной нагрузки в сетях с многоканальными соединениями посвящена работа [100], автор (К. Росс), которой предложил еще две модификации метода просеянной нагрузки, дающие более точные результаты в случае многоканальных соединений, чем метод, предложенный Ф. Келли. Основное различие трех подходов состоит в выборе модели для расчета вероятности блокировки на отдельном звене сети. В работах Ф. Келли используется обобщенная модель Эрланга, а в работах К. Росса предлагается более адекватная модель стохастического ранца. Далее кратко излагаются основные положения этой теории, которые и положены в основу метода расчета величины обслуженной нагрузки в СС.
Рассмотрим сеть произвольной топологии с множеством звеньев J# = {l,...,Z,] , где /-звено имеет емкость С,. Сеть поддерживает Ж ={\,...,К] классов одноадресных соединений, а А:-класс характеризуется маршрутом З сіЗ?, т.е. множеством звеньев сети, через которые устанавливается соединение, и требованием dk к емкости звеньев маршрута. Запросы на установление соединения А:-класса образуют пуассоновский поток интенсивности vk с интенсивностью предложенной нагрузки ak, к є Ж.
Постановка задачи оптимизации обслуженной нагрузки абонентов
Однако, наравне с достоинствами, выделяют и ряд недостатков объектно-ориентированного программирования. Это - трудоемкость разработки структуры и интерфейса класса, отсутствие реальных видимых преимуществ по сравнению с другими парадигмами программирования, низкая производительность объектно-ориентированных программ, связанных с особенностями объектно-ориентированного программирования (в первую очередь полиморфизмом), излишняя функциональная насыщенность получаемых программ.
Однако, несмотря на недостатки, объектно-ориентированное программирование принято к использованию при реализации программно-аппаратного комплекса, что связано с относительной сложностью разрабатываемой программы и наличии ярко выраженных сущностей предметной области, которые можно выделить в классы (графы с операциями на них, вершины и ребра с данными и свойствами и т.д.).
В качестве языка программирования в диссертационной работе выбран язык C++, как язык полностью реализующий парадигму объектно-ориентированного программирования и способный покрыть требования, предъявляемые к программно-инструментальному комплексу.
Для разработки кроссплатформенных приложений необходимо использовать специальные кроссплатформенные библиотеки. Одной из наиболее распространенных библиотек для кроссплатформенной разработки приложений для сред ОС Windows и ОС Linux является библиотека QT.
Библиотека QT является кросс-платформенным инструментарием разработки ПО на языке программирования C++ и включает в себя классы для разработки графических интерфейсов, классы работы с сетью, базами данных, XML и многими другими. Разработка пользовательского интерфейса Интерфейс пользователя должен соответствовать решаемым инструментальными программными средствами задачам: 1. задание и отображение структуры и параметров исследуемой СС; 2. сохранение созданных и загрузка сохраненных структур СС; 3. учет экспертного мнения по размещению ЦОД; 4. расчет задачи размещения ЦОД и анализ качества полученного решения; 5. отображение результатов решения задачи размещения ЦОД и анализа качества решений. На рис. 4.1 показано главное окно интерфейса пользователя инструментального программного средства для расчета СС. Главное окно состоит из нескольких областей:
Окно отображения и рисования элементов исследуемых систем. Элементами системы являются: - абонентские узлы - отрисовываются в программе в виде окружностей зеленого цвета; -транзитные узлы - отрисовываются в программе в виде окружностей серого цвета; -узлы кандидаты в ЦОД - отрисовываются в программе в виде окружностей синего цвета; - звенья сети — показываются в программе в виде линий, соединяющих узловые элементы. X ї" ! Программа распределения серверов обработки - test_!66(Mjrh iBhad Файл Добавить Изменить Счёт Результаты а -/ма F=25 iL Текущая конфигурация сети. testJ666grti Текущий кэртоФон Не загружено Вид целевой функции: mn серверов Временное ограничение на доставку: 0 Квант распределения: 0 Коэффициент распределения J—fc Рис. 4.1. Вид главного окна инструментального программного средства для расчета сетецентрической системы
У каждого узла системы есть символьное имя, отображаемое под соответствующим элементом. Для абонентских узлов отображаются величины информационных потоков. На звеньях сети отображаются их пропускные способности и величины текущего потока (после решения задачи распределения потока). Панель меню с выбором действий, применяемых в инструментальных программных средствах.
Тулбар с вынесенными для удобства и быстроты использования действиями по рисованию структуры исследуемой системы, сохранению созданной структуры и загрузки. Информационная панель, на которую для удобства оператора вынесена информация об основных параметрах загруженной/созданной системы На рис. 4.2(a) показаны окна интерфейса для задания параметров абонентского узла - имя и интенсивность потока данных, а на рис. 4.2(6) окно изменения параметров звена сети - его пропускная способность.
На рис. 4.3(a) представлено окно интерфейса изменения параметров узла кандидата в ЦОД. Здесь присутствует возможность директивного (экспертного) выбора ЦОД. Так эксперт может запретить размещение алгоритмом ЦОД в указанном узле либо наоборот указать узел, где он должен быть обязательно размещен. Запрещенные кандидатские узлы обрамляются желтой рамкой, размещенные - красной (см. рис. 4.3(6)).
Методика сбора данных для вычислительного эксперимента
В данном разделе диссертационной работы проводится численный анализ вероятностных характеристик СС для исходных данных, разработанных в разделе 4.2. Рассматриваются задачи (1, 0.001)- и (2, 0.001)-размещения центров из раздела 2.2, граф системы показан на рис. 2.5. В разделе 4.2 рассчитаны все необходимые данные для решения задачи численного анализа величины обслуженной нагрузки. Расчеты проводились средствами программного продукта MAPL.
Предполагается, что один из абонентов системы (хи) увеличивает интенсивность потока запросов к центрам обработки данных от значения 1.3 кбит/с до максимального значения 2.4 кбит/с пропускной способности звена, посредством которого он присоединен к сети. Ясно, что такое поведение одного из абонентов влияет на маршрутизацию потоков в сети и на значения исследуемых вероятностных характеристик. Маршруты и значения распределенной по ним предложенной нагрузки приведены в приложении 2. Исследуются четыре задачи размещения центров (1, 0.001)-, (2, 0.001)-, (1, 0.002)- и (2, 0.002). Если в первом и во втором случае требуется 1 и 2 ЦОД соответственно, то в последних - за счет увеличения директивного времени передачи данных в 2 раза — число ЦОД возрастает до 3. Графики зависимости вероятностей блокировок и величин обслуженной и избыточной нагрузки, рассчитанных с помощью методов, разработанных в главе 3 диссертационной работы, показаны на рис.4.9 - 4.23. Численный анализ обслуженной нагрузки и вероятностей блокировок для задачи (1, 0.001) -размещения центров В табличном виде результаты вычислений показаны в табл. 4.3 - 4.5 соответственно, а графики приведены на рис. 4.9 - 4.11.
Поведение графиков объясняется следующим образом. С увеличением потока запросов от абонента хи , занимаемая доля пропускной способности на звеньях сети потоками от других абонентов сокращается, приводя к уменьшению обслуженной нагрузки этих абонентов (рис. 4.9). Если бы маршруты движения данных были статичными, то и обслуженная нагрузка абонента х13 соответственно возрастала. Как видно из таблицы П.1 приложения 1, маршруты в условиях а(х12) = 1.3, а(х13) = 1.6 и а(х13) = 1.9,2.2,2.4 различны. При значении а(л;13) = 1.3 множество маршрутов от абонента х12 состоит из маршрутов (xn,xn,x7,x3,xlg) и (х12,хп,х4,хг,хп), а при значении а(х13) = 1.6 — только из одного маршрута [xl2,xn,x1,x3,xls). Различие таблиц маршрутизации для сети с а(х13) = 1.6 и а(х13) = 1.9 также относится к одному абоненту — х13: при а[х13) = 1.6 %(s,t) = (xx3,xn,xA,x3,xl%), при а(х13) = 1.9 $(s,t)={(xn,xn,x4,x3,x]%),(xl3,xn,x1,x3,xK)}. Именно поэтому происходят скачки как в поведении графиков обслуженной нагрузки (рис. 4.9), избыточной нагрузки (рис. 4.10), так и вероятности блокировки (рис. 4.10).
Численный анализ обслуженной нагрузки и вероятностей блокировок для задачи (2, 0.001) -размещения центров
В табличном виде результаты вычислений показаны в табл. 4.6 — 4.8 соответственно, а графики приведены на рис. 4.12 - 4.14. В отличие от предыдущей задачи, пучки маршрутов для всех значений предложенной нагрузки а(х13) совпадают, поэтому с ее увеличением обслуженная нагрузка всех абонентов - кроме х13 - уменьшается (рис. 4.12), а избыточная нагрузка
В табличном виде результаты вычислений показаны в табл. 4.9 - 4.11 соответственно, а графики приведены на рис. 4.15 - 4.17. Аналогичными рассуждениями, проведенными для задач со значением расстояния г = 0.001, можно объяснить поведение графиков зависимости обслуженной нагрузки (рис. 4.15), избыточной нагрузки (рис. 4.16) и вероятности блокировок (рис. 4.17) от интенсивности а(х13). Численный анализ обслуженной нагрузки и вероятностей блокировок для задачи (2, 0.002) -размещения центров
В табличном виде результаты вычислений показаны в табл. 4.12 - 4.14 соответственно, а графики приведены на рис. 4.18 — 4.20. Как и предыдущих задачах, они объясняются аналогичным образом. Очевидно, что наибольший интерес представляет сравнение исследуемых характеристик при одних значениях расстояния г, но разных к, а также качественное сравнение результатов всех 4 задач. Ниже в данном разделе проведен такой анализ на примере одной из важнейших характеристик рассматриваемой системы — суммарной обслуженной нагрузки.
В табличном виде результаты вычислений показаны в табл. 4.15 и табл. 4.16, а графики приведены на рис. 4.21 — 4.23. Из графика на рис. 4.21 (г = 0.001) видно, что для всех значений потока от абонента х13 суммарная обслуженная нагрузка а при k = 2 больше, чем при к = 1. Связано это с тем, что для случая (1, 0.001) -размещения был получен один ЦОД в вершине х18, а для (2, 0.001)-размещения было рассчитано положение двух ЦОД в вершинах х18 и х19. Размещение еще одного центра способствовало разгрузке некоторых звеньев сети, приводя к уменьшению потерь на них и увеличению обслуженной нагрузки. Подобное изменение минимального числа центров с к = \ на к — 2 не приводит к стабильному увеличению суммарной обслуженной нагрузки для случая г = 0.002 (рис. 4.22). Для обоих значений к рассчитанное число ЦОД одинаково и равно 3 (вершины х17, х18, х20), а различны маршруты и доли нагрузки, поступающей на каждый из маршрутов соответствующего множества маршрутов. Наконец, из рис. 4.23 видно, что с ростом числа размещенных центров, а также увеличением директивного времени передачи данных значение суммарной обслуженной нагрузки растет.
