Содержание к диссертации
Введение
1 Основные принципы построения мультисервисных сетей 15
1.1 Анализ эволюционных и структурных аспектов перехода к ngn... 15
1.2 Технологические подходы к построению мс 20
1.3 Концептуальная модель гмс для услуги «triple play» 27
1.4 Выводы по разделу 1 42
2 Методология исследования гмс 44
2.1 Оценка показателей качества обслуживания в гмс 44
2.2 Концептуальный подход к анализу и моделированию гмс 48
2.3 Аналитические методы исследования гмс 54
2.4 Синтез структуры сети 73
2.5 Выводы по разделу 2 76
3 Модели и характеристики качества обслуживания иерархических подуровней гмс 77
3.1 Исследование подуровня доступа гмс 77
3.2 Исследование подуровня агрегирования доступа гмс 90
3.3 Исследование подуровня агрегирования услуг и ядра гмс 102
3.4 Сопоставление результатов имитационного и аналитического моделирования 114
3.5 Выводы по разделу 3 117
4 Оптимизация гмс 119
4.1 Постановка задачи 119
4.2 Метод оптимизации гмс 122
4.3 Топологическая оптимизация гмс 128
4.3.1 Типы и особенности топологических структур 128
4.3.2 Постановка задачи топологической оптимизации 131
4.4 Пример оптимизации фрагмента гмс 135
4.5 Методика предпроектного анализа гмс 140
4.6 Выводы по разделу 4 142
Заключение 143
Литература 145
- Технологические подходы к построению мс
- Концептуальный подход к анализу и моделированию гмс
- Сопоставление результатов имитационного и аналитического моделирования
- Постановка задачи топологической оптимизации
Введение к работе
Актуальность проблемы. Развитие телекоммуникаций достигло того рубежа, за которым неизбежно должны последовать качественные изменения в подходах к построению телекоммуникационных сетей,
В результате развития информационных технологий появился рынок новых йнфокоммуникационных услуг [1], отражающий процессы формирования информационного общества. Реализация этих услуг связана с использованием принципов распределенной обработки информации, применением широкополосного доступа к высокопроизводительной пакетной телекоммуникационной сети и терминального оборудования мультимедиа.
Еще совсем недавно основной задачей широкого круга связистов была организация перехода от аналоговых сетей на основе электромеханических коммутационных станций и аналоговых систем передачи к цифровым сетям с коммутацией каналов. Теперь же, одним из самых актуальных направлений теоретических и прикладных исследований является переход к мультисервисным сетям нового поколения NGN (Next Generation Networks) [2].
Внедрение мультисервисных сетей (МС) на базе концепции NGN обеспечивает значительное повышение технико-экономической эффективности современных телекоммуникаций, не только за счет внедрения новых услуг, имеющих потребительский спрос, но и за счет формирования «гибкой нижней границы» экономической эффективности при наращивании сети [3].
При переходе от традиционных телекоммуникационных сетей к мультисервисным возникает множество технологических, методологических и других проблем, среди которых центральное место занимает проблема
обеспечения требуемого качества обслуживания для различных видов трафика [4] и, особенно, для речи [5].
Изучением аспектов качества обслуживания в сетях разных классов занимается множество организаций по стандартизации. Основные подходы к анализу показателей качества современных МС, в которых доминирует Internet Protocol (IP), приводятся в Рекомендации сектора стандартизации Телекоммуникаций Международного Союза Электросвязи (МСЭ-Т) Y.1541 [6]. Оценка показателей качества обслуживания различных видов трафика в этих сетях базируется на анализе их вероятностных и вероятностно-временных характеристик (ВХ и ВВХ).
Представляется, что анализ показателей качества обслуживания в наиболее динамично развивающемся сегменте городских мультисервисных сетей (ГМС), и особенно масштабных сетей мегаполисов, может быть выполнен только путем их декомпозиции на иерархические подуровни. Такой подход позволяет выявить и оценить влияние на показатели качества обслуживания основных процессов, протекающих в узлах и каналах на подуровнях доступа, агрегирования и ядра сетей данного класса.
Поскольку ГМС являются протяженными сооружениями, покрывающими большие территории, а следовательно - дорогостоящими объектами, то при их проектировании и предпроектном анализе следует руководствоваться методами оптимизации, ориентированными на минимизацию приведенных затрат. В то же время такие методы должны включать оценку и прогнозирование показателей качества проектируемых сетей, с тем, чтобы чрезмерное снижение затрат на строительство не приводило к построению сетей, не обеспечивающих необходимого качества предоставляемых абонентам услуг.
В данном контексте представляется актуальной разработка соответствующих методик оптимизации структуры ГМС, учитывающих специфику иерархических подуровней.
Объектом исследования диссертационной работы являются городские
мультисервисные сети.
Предметом исследования являются свойства иерархических подуровней городских мультисервисных сетей, связанные с характеристиками качества обслуживания, а также метод оптимизации их структуры.
Целью работы является разработка моделей иерархических подуровней городских мультисервисных сетей для анализа характеристик качества обслуживания, а также разработка метода оптимизации их структуры.
Методы исследования, используемые в работе базируются на аппарате теории вероятностей, теории массового обслуживания, численных методах и методах имитационного моделирования, методах теории оптимизации.
Состояние проблемы и задачи исследования. Аналитическому моделированию телекоммуникационных сетей с пакетной коммутацией посвящены работы Л. Клейнрока [7,8], В. Бакса [9], Г.П. Башарина [10], В,И. Неймана [11], ГЛ. Захарова [12], О.И. Шелухина [13,14], В.М. Вишневского [15],М.О. Колбанева[16] и ряда других авторов-Основы оптимизации пакетных сетей заложены ГЛ. Захаровым, В.В. Лохмотко [17], Г.Ф. Янбыхом, Б.А, Столяровым [18] и другими исследователями.
Однако, в существующих работах не учитываются процессы обслуживания в абонентских ADSL-модемах и групповых модемах DSLAM с профилированием трафика, процессы обслуживания в узлах агрегирования и ядра сети, не учитывается влияние маршрутизации и протяженности линий на задержки распространения в сети, в то время как эти факторы оказывают влияние на показатели качества обслуживания трафика в мультисервисных сетях. Кроме того методы оптимизации сетей строятся без учета деления
исследуемых объектов на иерархические подуровни, а также особенностей прокладки и монтажа оптических кабелей, тогда как стоимость строительства линейных сооружений вносит значительный вклад в формирование капитальных затрат на строительство сети.
При решении задач анализа и синтеза не рассматриваются концептуальные модели ГМС с реализацией услуги 'Triple Play" в то время как именно этот класс сетей воплощает в себе самый современный подход к развитию фиксированных телекоммуникационных сетей.
В соответствии с указанной целью в диссертационной работе поставлены и решены следующие задачи:
Разработана концептуальная модель мультисервисной сети с реализацией услуги "Triple Play", предложена методология исследования ГМС с целью оценки показателей качества обслуживания различных видов трафика.
Разработана аналитическая модель сети доступа на основе многофазной СМО, учитывающая процессы обслуживания в абонентских ADSL-модемах и групповых модемах DSLAM
Разработаны аналитические модели сети агрегирования доступа и ядра ГМС на основе разомкнутых линейных СеМО с тремя относительными приоритетами обслуживания заявок.
Предложена методика оценки времени распространения сигнала в оптических линиях сети агрегирования доступа и ядра сети, учитывающая многовариантность гипотетического пути и маршрутизацию.
Разработана имитационная модель узлов сети агрегирования доступа и ядра мультисервисной сети на основе среды GPSS World.
Разработан метод оптимизации структуры ГМС, учитывающий особенности концептуальной модели сети и включающий метод
топологической оптимизации, учитываюший особенности прокладки и монтажа оптических кабелей.
Научная новизна результатов диссертационной работы заключается в
следующем:
Разработана концептуальная модель ГМС с реализацией услуги "Triple Play".
Разработана аналитическая модель сети доступа в виде многофазной СМО, отличающая от известных тем, что в ней учтены процессы обслуживания заявок в абонентских ADSL-модемах и групповых модемах DSLAM, а также профилирование абонентского трафика.
Разработаны аналитические модели сети афегирования доступа и ядра ГМС в виде разомкнутых линейных СеМО с тремя приоритетами обслуживания заявок, необходимыми для реализации услуги "Triple Play'*, отличающиеся от известных тем, что в них детализированы процессы обслуживания в MPLS-сети, перераспределения заявок между узлами, влияние топологии сети на ее ВВХ;
Предложен метод оценки времени распространения сигнала в линиях сети агрегирования доступа и ядра сети, отличающийся тем, что в нем учтена многовариантность гипотетических маршрутов движения заявок,
Разработан метод оптимизации структуры ГМС, учитывающий особенности концептуальной модели сети, ее деление на иерархические уровни, а также затраты на систему технического обслуживания.
Практическая ценность полученных в работе результатов сводится к следующему:
Разработанные методы расчета обеспечивают адекватность моделей реальным процессам, протекающим в ГМС, за счет учета механизмов обслуживания трафика на различных участках сети.
Получены выражения для определения основных показателей качества, позволяющие проводить прогнозирование этих характеристик в процессе проектирования и предпроектного анализа сети.
Разработана программа для топологической оптимизации кольцевой и звездообразной структур.
Предложена методика предпроектного анализа ГМС операторского класса на основе разработанных методов оценки показателей качества обслуживания и оптимизации сетей данного класса.
Основные теоретические и практические результаты диссертационной работы внедрены в телекоммуникационных операторских структурах, о чем имеются соответствующие документы.
Апробация результатов работы. Основные положения диссертационной работы обсуждались, были одобрены и опубликованы в материалах 8 конференций, в том числе - 5 международных.
Основные результаты диссертационной работы нашли отражения в 5 статьях в научных журналах, в том числе - рецензируемых, одной монографии и одном патенте на полезную модель.
Объем работы. Диссертационная работа содержит 150 страниц машинописного текста (без текста приложений), 37 рисунков, 11 таблиц и состоит из введения, четырех разделов, заключения и приложения,
В первом разделе приводится описание объекта исследования, выявляются эволюционные и структурные аспекты перехода к
телекоммуникационным сетям следующего поколения» Дается описание основных принципов построения мультисервисных сетей связи. Рассмотрена концептуальная модель ГМС с реализацией услуги 'Triple Play", предусматривающая разделение сети на иерархические подуровни.
Во втором разделе раскрывается методология исследования ГМС. Приводятся подходы к оценке показателей качества обслуживания различных видов трафика в ГМС. Дается концептуальный подход к анализу и моделированию ГМС. Описаны методы моделирования ГМС с использованием аппарата СМО и СеМО и другие. Дается общий подход к решению задачи синтеза ГМС,
В третьем разделе приведены результаты моделирования различных иерархических уровней структуры ГМС. Разработана аналитическая модель сети доступа на основе многофазной СМО, учитывающая процессы обслуживания в абонентских модемах ADSL и групповых модемах DSLAM, а также процесс профилирования абонентского трафика. Приводится численное исследование разработанной модели. Выявлено влияние различных параметров и процессов, протекающих в сети доступа на ее ВВХ и показатели качества обслуживания различных видов трафика.
Разработаны аналитические модели сети агрегирования доступа и ядра ГМС в виде разомкнутых линейных СеМО с тремя приоритетами обслуживания заявок, необходимыми для реализации услуги "Triple Play", учитывающие процесс обслуживания в MPLS-сети, перераспределение заявок между узлами, влияние топологии указанных иерархических уровней на их ВВХ. Проведено численное исследование разработанных моделей.
Выявлено влияние параметров структуры указанных иерархических уровней ГМС на их ВВХ и показатели качества обслуживания различных видов трафика.
Разработана имитационная модель узлов сети агрегирования доступа и ядра сети в среде GPSS World. Приводится сопоставление результатов
аналитического и имитационного моделирования при воздействии на разработанные модели потоков заявок, отличных от пуассоновских.
В четвертом разделе рассматривается метод оптимизации структуры ГМС, учитывающий особенности концептуальной модели ГМС, ее деление на иерархические подуровни, а также затраты на систему технического
обслуживания.
Разработан метод топологической оптимизации иерархических подсетей, входящих в состав структуры ГМС, учитывающий трассы прокладки и особенности монтажа оптических кабелей.
Разработана программа топологической оптимизации кольцевой и звездообразной структуры в среде Borland Pascal для ПК.
Предложена методика предпроектного анализа ГМС операторского класса на основе разработанных методов анализа, синтеза, оценки показателей качества обслуживания и оптимизации структуры сетей данного класса.
Положення, выносимые на защиту.
Концептуальная модель и методология исследования ГМС с реализацией услуги 'Triple Play", предусматривающие ее декомпозицию на четыре иерархических подуровня и применение для их исследования математического аппарата СМО и СеМО с неоднородным потоком заявок и тремя классами приоритетов их обслуживания,
Аналитическая модель сети доступа на основе многофазной СМО, учитывающая процессы обслуживания кадров в абонентских ADSL-модемах и групповых модемах DSLAM,
Аналитические модели сети агрегирования доступа и ядра ГМС на основе разомкнутых линейных СеМО с тремя классами приоритетов обслуживания заявок, учитывающие процессы,
протекающие в узлах, процессы обслуживания в MPLS-сети, а также метод оценки времени распространения, учитывающий многовариантность гипотетических маршрутов движения заявок.
4. Метод дискретной оптимизации ГМС, учитывающий иерархическую структуру сети, а также особенности строительства оптических линейных сооружений.
Личный вклад автора.
Результаты исследований получены автором самостоятельно, В работах, которые опубликованы с соавторами, соискателю принадлежит основная роль в постановке и решении задач, а также при обобщении полученных результатов.
Технологические подходы к построению мс
Создание новой телекоммуникационной инфраструктуры, как правило, рассматривается с позиции "техники" и "экономики".
Технический аспект реализации МС основывается на использовании совокупности программно-аппаратных средств, реализующих стандартизированные стеки протоколов передачи данных и сигнализации с применением структурно-сетевых решений, базирующихся на принципах открытой архитектуры, обеспечивающей разделение функций переноса/коммутации и управления вызовом/услугами.
С экономической точки зрения, эффективным является подход, подразумевающий использование минимальных объемов инвестиций и получение максимальной прибыли от коммерческой эксплуатации МС. Степень приближения к точке максимальной эффективности использования инвестиций напрямую зависит от технической составляющей реализации МС.
Еще 5 - 7 лет тому назад Россия, являясь активным участником работ по созданию Единой Европейской Инфраструктуры, координируемой ETSI, была вовлечена в процесс построения сети B-ISDN. Технология ATM была выбрана базовой транспортной платформой, ориентированной на предоставление высокоскоростных мультимедиа услуг с гарантированным кэтествш обсдужинатая, который будут штегриршшны в R-J$DM В іе годы только сетевые решения т базе технологии ATM были ущербны обеспечить эффективный перенос к коммутацию штатного -щЦтт, а, сдадонадільш, рассматривались mm перспективные методы миграции к B-ISDN операторского класса [22].
Кроме того, в условиях повсеместного распространения телефонных (узкополосных) сетей и доминирования телефонного трафика над трафиком ПД, вдревдд к В-І5ВД в значительной мере был направлен щ сохранение имеющихся швестшшії а услуги батозой т&тефоши [23].
Рисунок 1.2 гтасняет стратегию миграции от существующей сети TDM к сети с пакетной коммутацией» а в гшрегшгшм и к ширвкшіодосшй сети с интеграцией сервисов Тр&ш:туиа сжші ,цшй узел ATM выиттяег функции межсетевого В:ШШОДЙСТЙЙЯ и коммутаций между существующей уяюішлосийй телефомоії сетью ШШ регионального оператора й. птратпшю&тй сетью (EHSDN) па базе технологии ATM.
Для N х 64 кбит/с телефонных служб взаимодействие происходит путем преобразования узкополосной системы сигнализации N-ISUP (для России N-ISUP-R) в широкополосную систему сигнализации B-ISUP (для России B-ISUP-R). Выполнение транзитной коммутации телефонии осуществляется в сети ATM. При этом ресурсы сети ATM могут быть использованы для переноса и коммутации не только телефонии, но и любых других типов трафика. Таким образом, обеспечивается создание новой, мультисервисной транзитной сети на базе технологии ATM, которая в перспективе могла стать основой полноценной сети B-ISDN.
Несмотря на то, что выбор пути миграции к B-ISDN осложнялся недостаточной проработанностью структурно-сетевых решений, отсутствием ряда стандартов по сетевой мультисервисной интеграции, сложностью реализации управления параметрами QoS, в 2000-2002 г.г. появилась целая серия зарубежных и отечественных разработок [24], многие из которых были успешно внедрены на российских сетях связи [25].
Когда в восьмидесятые годы прошлого века начали строиться сети ISDN, и появилась стройная система стандартов, специфицирующих сервисы ISDN, возможно, руководствуясь теми же устремлениями, в девяностые годы был выполнен гигантский объем работ в направлении стандартизации и строительства B-ISDN на базе ATM. Однако, с проникновением в нашу жизнь терминального оборудования мультимедиа [26], систем мобильной связи и Internet, многие стандарты стали нуждаться в серьезном пересмотре. Спектр услуг связи, предоставляемых сегодня, варьируется в очень широких пределах - от традиционных услуг базовой телефонии ТфОП до проработанных под различные категории абонентов мультимедиа сервисов сотовых операторов.
Потребность в быстрой реализации заказных или новейших сервисов, которые могут быть стандартизованы позднее, стимулировалась, в основном, бумом Internet и долгое время, с точки зрения многих традиционных операторов тяж являлась вотчиной альтернативных, операторов и поставщиков услуг Internet В настоящее время, тежетммуиикадиошшй рынок РОССИИ характеризуется г среобладашш потребности в быстрой реализации новейших сервисов сшшь Конкурентная борьбу которая р&звдрнул&еъ в борьбе за клиентов между традиционными, альтернативными операторами связи и поставщиками услуг Internet, заглушила голоса сторонников B-ISPN й разрушила все ОПТИМИСТИЧНЫЙ прогнозы развитии М на базе технологий ATM [27]. Новый подход нашедший слое ощжтт в концепции построения МС, яроптжщрутт Multiservice Switching Forum (MSF) [28], отодвигая задачу построения B-1SDN ни Егором пят но не исключал возможности применения технологии ATM тк на уровне транспортного ядра так и на уровне доступа- В соответствии с идеологнш MSF NIC, рассштриваотся тк совокупность пограничных систем коммутации (шлкшш) и систем коммутации три МС (IP/MPLS ИЛИ ATM). В данной структуре (Риеушж КЗ) функции агрегирования уелуг вьшеешы за
Этот агрегированный набор услуг находится под единым управлением, обеспечивающим функционирование граничных устройств как единого "виртуального" узла. Требования к граничным устройствам являются минимальными и в основном сводятся к необходимости реализации стандартных пользовательских и сетевых интерфейсов, а также протоколов переноса данных и сигнализации. Элементы ядра находятся под собственным управлением и действуют независимо от граничного "виртуального" узла.
Очевидно, что при таком подходе достигается очень быстрая реализация практически любого нового вида услуг связи путем установки новых шлюзов и систем управления ими, практически не затрагивая ядро мультисервисной сети.
Концептуальный подход к анализу и моделированию гмс
Из описания структуры ГМС и ее концептуальной модели, рассмотренных в разделе 1.3 настоящей работы следует, что данный объект исследований можно отнести к сложным системам. Структура этого объекта такова, что исследование его характеристик с применением только инженерной эвристики, подкрепленной измерениями, анализом функционирования сетевых элементов, протекающих в них процессов, сетевых механизмов и других факторов, чаще всего не представляется возможным из-за их сложности и очень большого числа.
Ситуация усложняется еще и тем, что в большинстве случаев производители сетевого оборудования не раскрывают детально его структуру, особенности и алгоритмы функционирования в различных режимах.
Поэтому при исследовании системы приходится опираться лишь на анализ стандартных версий протоколов и алгоритмов- В большинстве случаев эти протоколы настолько сложны, что зачастую учет всех нюансов выходит за пределы компетенции проектировщиков сетей. Кроме того, проведение крупномасштабных экспериментальных исследований и натурных испытаний с целью измерений характеристик сети во всем диапазоне воздействий нагрузок характерного трафика требует необоснованных финансовых и временных затрат.
Одной из эффективных мер по преодолению описанных трудностей является применение моделирования объекта исследования [7,12,14,49],
- Объектами моделирования в настоящей работе являются:
- структура сети в целом и ее иерархических подуровней;
-сетевые механизмы, протоколы, алгоритмы, процессы, протекающие в сети в целом, в ее иерархических подуровнях и сетевых элементах, которые оказывают наибольшее влияние на ВВХ сети.
Применение моделирования в совокупности с широким использованием ПК для анализа и имитации свойств моделей на этапе проектирования сети позволяет анализировать варианты предлагаемых проектных решений, определять работоспособность и оценивать надежность системы, выявлять узкие места и мало загруженные ресурсы, принимать решения по рациональному изменению состава и структуры или способа функциональной организации системы, а также получать расчетные соотношения для анализа ВВХ сети, приведенных в разделе 2.1.
Учитывая сложность рассматриваемого объекта исследования, создание для него единой общей математической модели может вызвать значительные затруднения, связанные с решением чрезмерно сложных задач и получением излишне громоздких математических выкладок. В качестве одного из подходов к решению поставленной задачи, для моделирования ГМС может быть применен принцип декомпозиции, суть которого сводится к раздельному моделированию иерархических подуровней рассматриваемой сети: сети доступа, сети агрегирования доступа, ядра (магистрали) сети, сети агрегирования услуг.
В результате такого подхода задача моделирования рассматриваемого объекта распадается на 4 подзадачи умеренной сложности, в результате решения которых могут быть определены перечисленные в разделе 2,1 ВВХ каждого из перечисленных уровней.
После решения этих подзадач для расчета показателей качества сети в целом можно воспользоваться выражениями (2,2), (2.3), (2,4), т.е. рассматривать выделенные уровни в качестве сетевых секций.
Вместе с этнм, применение принципа декомпозиции к рассматриваемому объекту исследования не должно приводить к нарушению целостности и интегративности данного объекта, трактуемого как сложная техническая система [50]. В данном контексте под термином «целостность» будем понимать свойство системы, связанное с объединением взаимодействующих частей (элементов), возможно разнокачественных, но одновременно совместимых.
Термин «интегративность» будем трактовать как свойство системы, определяющее наличие качеств, присущих системе в целом, но не свойственных ни одному из ее элементов в отдельности. Другими словами -интегративность подразумевает, что свойства системы хотя и зависят от свойств ее элементов, но не определяются ими полностью.
Данное условие может быть учтено путем анализа не только структуры узлов сети и связывающих их каналов, но и протокольной базы, применяемой на протяжении всего рассматриваемого гипотетического пути, а также анализа и учета всех связей между перечисленными подсетями (подуровнями ГМС), включая учет задержек распространения в связывающих их линиях.
Перед тем как перейти к описанию применяемых в настоящей работе методов моделирования остановимся на определении основных понятий, связанных с трактовкой объекта исследований как сложной системы- Одним из ключевых понятий в контексте оценки качества функционирования системы является ее эффективность»
Эффективность - степень соответствия системы своему назначению. Оценка эффективности системы - одна из задач исследования систем, решаемых в процессе ее моделирования.
Сопоставление результатов имитационного и аналитического моделирования
Основным допущением, которое использовалось в предыдущих разделах настоящей работы, было предположение о пуассоновском характере входящих потоков всех рассматриваемых СМО и СеМО.
Пуассоновский поток занимает центральное место в инженерной теории массового обслуживания [15] не только потому, что он приводит к простым формам выражений для определения характеристик СМО и СеМО, приведенным в разделе 2.3, и широко используемых в других разделах настоящей работы, но и потому, что доказанным является тот факт, что при наложении потоков с другими распределениями интервалов между поступлением заявок, отличающимися от пуассоновского, результирующий поток стремится к пуассоновскому [12].
Это обстоятельство дает основание полагать, что моделирование потоков на основе пуассоновского распределения, по крайней мере, на выходах узлов коммутации, где происходит наложение большого числа входных потоков и их агрегирование в высокоскоростные выходные потоки, во многих случаях является вполне адекватным.
Вместе с тем, в ряде работ по исследованию ТР-сетей отмечается, что описание входных потоков пуассоновской моделью, а также марковские модели СМО и СеМО дают излишне оптимистичные (заниженные) результаты при анализе показателей качества обслуживания в различных сетевых фрагментах. [13,15,52]. В частности утверждается, что потоки заявок в IP- сетях имеют значительное последействие, аппроксимируются распределениями с «тяжелыми хвостами», а в ряде случаев обладают свойствами самоподобия [13].
В работах одного из известных отечественных исследователей телекоммуникационных сетей В.И. Неймана утверждается, что «три источника и три составные части самоподобных процессов» выражены в медленном убывании дисперсии, долгосрочной зависимости и флуктуационном характере спектра мощности таких процессов [11,52].
Использование СМО типа G/G/1 для построения аналитических моделей приводит не только к громоздким математическим выкладкам, но и к значительным методическим ошибкам, поскольку для данного типа СМО не известно точных решений, а используются лишь приближенные соотношения.
Известно [62], что одним из наиболее точных (при большом числе испытаний) методом моделирования СМО общего вида является метод имитационного моделирования, основанный на программном генерировании потоков входных требований и процессов обслуживания практически любого вида. Для создания таких моделей широко используется специализированный язык программирования GPSS. В настоящее время наибольшее применение получили модели на основе специализированной интегральной среды программирования GPSS World для ПК[63].
С учетом изложенного, для оценки возможных отклонений результатов аналитического моделирования с использованием пуассоновского входного потока и при воздействии на исследуемую сеть потоков, отличных от пуассоновских, была разработана имитационная модель узла ГМС (Рисунок 3.11) с неоднородным потоком заявок и приоритетным обслуживанием в среде GPSS World.
В разработанной программной модели была заложена возможность выбора распределений интервалов между поступлением заявок входного потока - пуассоновского, Эрланга порядка 2 и гиперэкспоненциального. Эти же распределения были использованы в качестве вариантов для выбора характера распределения интервалов обслуживания заявок во всех фазах модели узла ГМС (Рисунок 3.11).
Рисунок 3.21 показывает зависимости средней задержки от интенсивности входного потока для узла сети агрегирования доступа. Три заштриховашшс области ДЛИ трта видов трзфика с различными приорнтетамм обслуживший заявок в СМО у$т иллюстрируют сттстшя&жт результатов аналитического ш имитационного моделирования.
Нижние границы заштрихонашшх областей соответствуют результатам аналитического модеишров&ния с пуассоновской моделью входного потока М/О/1 (Ли). В этом режиме результаты анадитаческого и имитационного моделирования почти не отличаются. Верхние границы этих областей шот встетвуют результатам имитационного моделировашш при тиопь зотнт ншбшюе тяжелого режима - гиперзксцонеяциапыюго распределения интервалов во входном потоке и гшхерэкгаокшци&пьшт распределения интервалов обслуживания Н/НУІ (Им).
Гшерэксшненциальное распределение с коэффициентом вариации 3 выбрана для данного иллюстративного примера в связи с тем, что оно имеет довольно медленно убывающую дисперсию, а следовательно - со значительной степенью адекватности отражает характер входного потока и распределение интервалов обслуживания, возникающих в раде случаев в IP-сетях.
На основании оценки полученных результатов можно сделать вывод о том, что наименьшие расхождения результатов двух исследуемых моделей наблюдаются в областях малых нагрузок для классов заявок с повышенными приоритетами обслуживания (трафик, чувствительный к задержкам). В области больших нагрузок для этих видов трафика расхождения увеличиваются и составляют 1,6 - 1,8 раз. Учитывая, что данное моделирование предназначено для грубых оценочных расчетов, такие расхождения не являются катастрофическими. Для эластичного (малочувствительного к задержкам) трафика данных с наименьшим приоритетом обслуживания расхождения могут составлять 2-8 раз в зависимости от уровня загрузки, что также не столь критично для этого типа трафика.
Постановка задачи топологической оптимизации
1. Матрицы расстояний (4.1)-(4.2) составленные с учетом ограничений на пути прокладки линейных сооружений (трассы).
2. Допустимые виды топологических структур - звездообразная и кольцевая, (ADSL-сеть доступа, оптическая сеть агрегирования доступа).
-132 Требуется определить:
1. Номер вершины из заданного множества JV вершин графа, на которой должен быть размещен центр звездообразной структуры (расположен модем DSLAM), При этом структуры задаются матрицей расстояний (4.1), и ведется поиск топологии оптимальной с точки зрения выполнения условия: где /зв - сумма длин линий в звезде; f{xpcj) - длина линии от центра до вершины / (длина луча);
2. Сумму длин линий в звездообразной структуре, заданной матрицей расстояний (4.1) и удовлетворяющую(или не удовлетворяющую) условию (4.7).
3. Максимальную длину линии в найденной (или заданной) звездообразной структуре /, в, значение которой необходимо для проверки ограничения на максимальную длину абонентской линии ADSL.
4. Стоимость линейных сооружений для звездообразной топологической структуры удовлетворяющей (или не удовлетворяющей) условию (3-7), Стоимость линейных сооружений может быть определена из выражения: Ъш=Шк+СПк)+СМк (4.9) где Ц к стоимость единиц длины кабеля абонентской ADSL - проводки для звездообразной структуры или оптических кабелей при объединении SLAM; СПк - стоимость прокладки единицы длины ADSL; СМк -стоимость монтажа линейных сооружений;
5. Последовательность соединения N узлов, привязанных к территории охватываемого сетью района, в кольцевой топологической структуре {сеть агрегирования доступа или кольцевое включение DSLAM), задаваемой матрицей расстояний (4.2) и оптимальной с точки зрения выполнения условия: 1тл =Х/(г, ,)-ипш , (4.10)
где /К1 л - сумма длин линий в кольцевой структуре; f (х ) - длины линий между вершинами графа / и j в данной структуре;
6. Сумму длин линий в кольцевой структуре, удовлетворяющей условию (4.10): =2/( , ,) , (4.11) 1, Стоимость линейных сооружений для кольцевой топологической структуры (сети агрегирования доступа), удовлетворяющей условию (ЗЛО), которая может быть определена из выражения: лскол = кол (Цсж+СП0К) + СМок , (4.12) где Цок - стоимость единицы длины оптического кабеля; СП0К -стоимость прокладки единицы длины оптического кабеля.
Решение задачи оптимизации звездообразной структуры на основании условия (4,7) может быть осуществлено, например, в соответствии со следующим формально-звристическим алгоритмом:
1. В матрице j[C (4.1) знаки со заменяются на 0. Полученную таким образом матрицу обозначим С ,
2. Строится матрица - строка, каждый член которой определяется как сумма членов каждого столбца матрицы ]С , и может быть определен так: c tc: (4.13) где Сю - член искомой матрицы строки; С;- член столбца матрицы С.
3. Отыскивается минимальный член полученной матрицы - строки. Номер этого члена и соответствует номеру узла, на котором оптимально с точки зрения выполнения условия (4.7) следует разместить DSLAM. Численное значение найденного члена есть не что иное, как параметр /, вычисленный в соответствии с (4.7), а максимальный член столбца матрицы С с номером, соответствующим номеру найденного члена соответствует максимальной длине линии в звездообразной структуре. Конец алгоритма. В случае, если по условиям или исходньш данным проекта априорно задается расположение DSLAM в одном из узлов, то оптимизация топологической структуры не производится, а параметр / определяется как сумма членов столбца матрицы С соответствующего номеру вершины в которой расположен модем DSLAM,
Задача поиска кольцевой структуры, удовлетворяющей условию (4.10) сводится к широко известной [72, 73] задаче о коммивояжере (ЗК), и часто трактуется в постановке, схожей с рассматриваемой в данном подразделе, ЗК относится к типичным комбинаторным экстремальным задачам, в которых экстремум функционала отыскивается на множестве всех циклических перестановок [72]. Для получения решения ЗК методом перебора необходимо перебрать (N-1)! комбинаций в асимметричной ЗК (/ / ) и (N-1J/2! комбинаций в симметричной ЗК (/шгЛрд- Очевидно, что для достаточно больших N такой подход может привести к слишком большому времени вычисления [72] и поэтому следует искать действительно эффективные алгоритмы решения ЗК. В [72] приводится обзор существующих методов решения ЗК, как точных, так и приближенных. Все эти методы подразделяются на методы улучшения цикла и методы последовательного построения цикла. Одним из эффективных методов, относящихся к первой группе, причисляется метод ветвей и границ [74], однако, к основным трудностям этого метода относят необходимость разработки специальных реализаций применительно к каждой решаемой задаче, что приводит к значительным неудобствам. Для N 50 точные методы решения ЗК достаточно трудоемки в вычислительном плане, в то время, как в [74] указывается на перспективность и относительно низкую вычислительную сложность эвристических методов решения ЗК [75, 76], которые дают точность не хуже 10%, что может считаться вполне допустимым. Один из наиболее простых методов этого класса, основанный на достроении тура, [75] сводится к алгоритму: "начиная с вершины 1 идти в ближайшую еще не пройденную вершину".
Применение этого метода дает несложную программную реализацию или, при небольшой размерности задач, позволяет решить их вручную. Данный метод можно с успехом использовать для решения поставленной задачи.
Для решения задачи топологической оптимизации звездообразной и кольцевой структур СД и СА, а также для выбора оптимальной структуры на базе изложенных методов и алгоритмов разработана специальная программа на языке Borland Pascal
