Содержание к диссертации
Введение
1. Анализ совремееных методов и средств расчета и моделирования цифровых сетей передачи данных 9
1.1. Этапы проектирования современных ИТС 10
1.2. Анализ существующих САПР СПД 22
1.3. Модели и методы, используемые при проектировании ИТС 33
1.4. Цели и задачи исследования 42
2. Разработка моделей и алгоритмов расчета и моделирования ИТС 44
2.1. Особенности применения системного подхода к разработке модели СПД 45
2.2. Разработка компонентно-ориентированной модели СПД 53
2.3. Адаптация процедур расчета и анализа СПД к компонентно-ориентированной модели 63
2.4. Выводы второй главы 75
3. Методы и алгоритмы оптимизации СПД 77
3.1. Формирование комплекса методов оптимизации структурысети 78
3.2. Прогнозирование трафика в СПД 87
3.3. Разработка процедур комплексной оценки проектных решений 97
3.4. Выводы третьей главы 111
4. Разработка средства проектирования СПД 112
4.1. Алгоритм оценки эффективности использования САПР СПД 113
4.2. Архитектура разработанной САПД СПД 117
4.3. Пример использования прототипа САПР СПД 133
4.4. Выводы четвертой главы 136
Заключение 137
Список литературы 139
Приложения 150
- Анализ существующих САПР СПД
- Адаптация процедур расчета и анализа СПД к компонентно-ориентированной модели
- Разработка процедур комплексной оценки проектных решений
- Пример использования прототипа САПР СПД
Анализ существующих САПР СПД
Коммутация каналов используется в аналоговых сетях телефонной связи и в узкополосных цифровых сетях интегрального обслуживания (УЦСИО). Режим коммутации каналов в УЦСИО базируется на принципе временного разделения каналов для транспортирования информации от одного узла к другому. Информация передается с определенной частотой, несколько соединений мультиплексируются в одном тракте путем объединения временных интервалов в кадры, которые также повторяются с определенной частотой. Системы передачи с многоскоростной коммутацией каналов используют тот же метод временного разделения, что и системы с обычной коммутацией каналов, однако в каждом соединении может использоваться п (п 1) основных цифровых каналов. Режим быстрой коммутации основан на использовании ресурсов сети только в момент передачи информации. Повышение эффективности использования цифровых трактов связи достигается за счет статистического уплотнения и при идеальной работе системы сигнализации при одной и той же вероятности отказа в обслуживании достигает величины в 180-200 % по сравнению с многоскоростной коммутацией каналов.
Режимы коммутации пакетов используются в технологиях IP и Frame Relay. Режим быстрой коммутации основан на пакетной коммутации с минимумом функций, выполняемых узлами коммутации на уровне звена с целью повышения уровня временной прозрачности сети. Этот режим переноса информации используется в технологиях ATM (Asynchronous Transfer Mode) и MPLS (Multi-Protocol Label Switching). Наиболее перспективными для построения цифровых сетей передачи данных, интегрирующих в себе большое количество различных видов сервисов, являются следующие транспортные технологии:
Frame Relay (FR) представляет собой высокопроизводительную сетевую технологию, которая обеспечивает эффективное разделение ресурсов, поддерживая множество виртуальных каналов над одной высокоскоростной магистралью. Маршрутизация в протоколе FR базируется на простых номерах виртуальных каналов вместо сложных адресов сетевого уровня, используемого маршрутизаторами. Это позволяет сети FR добиваться более высокой производительности по сравнению с сетями маршрутизаторов. Являясь технологией с установлением соединения, FR лучше справляется с потоком данных и перегрузками, чем сети маршрутизаторов. Сеть FR идеальна для ситуации, когда пользовательский узел представляет собой интеллектуальное оборудование типа рабочая станция или ЛВС, а канал связи обеспечивает высокое качество передачи данных. Помимо базовых функций передачи данных протокола Frame Relay, спецификация консорциума Frame Relay включает дополнения LMI, которые делают задачу поддержания крупных межсетей более легкой. Существуют следующие основные дополнения LMI:
1. Сообщения о состоянии виртуальных цепей (общее дополнение). Обеспечивает связь и синхронизацию между сетью и устройством пользователя.
2. Многопунктовая адресация (факультативное). Позволяет отправителю передавать один блок данных, но доставлять его через сеть нескольким получателям. 3. Глобальная адресация (факультативное). Наделяет идентификаторы связи глобальным, а не локальным значением, позволяя их использование для идентификации определенного интерфейса с сетью Frame Relay.
4. Простое управление потоком данных (факультативное). Обеспечивает механизм управления потоком XON/XOFF, который применим ко всему интерфейсу Frame Relay. Он предназначен для тех устройств, высшие уровни которых не могут использовать биты уведомления о перегрузке и которые нуждаются в определенном уровне управления потоком данных.
К достоинствам технологии Frame Relay относятся: наличие эффективных механизмов адаптации к различным видам трафика, обладающим различными вероятностно-временными характеристиками, что позволяет передавать по сетям Frame Relay как данные, так голос/факс и видео; высокая эффективность механизмов статистического уплотнения информации (аналогично ATM), т.е. высокая эффективность при передаче трафика, характеризующегося ярко выраженной неравномерностью во времени трафика локальных сетей; малая протокольная избыточность; гибкость реализуемых на основе FR решений. К недостаткам данной технологии в настоящее время могут быть отнесены: средняя скорость передачи - до 45 Мбит/с. высокое качество каналов связи, необходимое для эффективного функционирования протокола FR.
Функциональная архитектура цифровых сетей с интегральным обслуживанием - это сеть, которая обеспечивает полностью цифровые соединения между оконечными устройствами для поддержания широкого спектра речевых и неречевых услуг, доступных с помощью ограниченного набора стандартизованных многофункциональных интерфейсов. Наибольшее распространение получили первичный вид доступа пользователя к сети (PRI) и базовый вид доступа (BRI). Первичный доступ предоставляет пользователю 30 каналов типа В (универсальных каналов для передачи речи и данных скоростью 64 Кбит/с) и один канал типа D (вспомогательный выделенный канал) по линии со скоростью передачи 2048 Кбит/с или 23 канала типа В и один канал типа D по линии скоростью 1544 Кбит/с. Базовый доступ предоставляет пользователю два канала типа В со скоростью 64 Кбит/с и один канал типа D со скоростью 16 Кбит/с.
Форматы блока данных физического уровня ISDN различаются в зависимости от того, является блок данных отправляемым за пределы терминала (из терминала в сеть) или входящим в пределы терминала (из сети в терминал). Длина блоков данных равна 48 битам, из которых 36 бит представляют информацию. Физически к одной цепи может быть подключено множество устройств пользователей ISDN.
Технология синхронных волоконно-оптических сетей основана на использовании стандарта синхронной цифровой иерархии SDH (Synchronous Digital Hierarchy), принятого ITU и включающего в себя следующие рекомендации:
Адаптация процедур расчета и анализа СПД к компонентно-ориентированной модели
Для проектирования новых ИТС и оптимизации старых в качестве инструмента получения характеристик обычно используются различные средства автоматизированного проектирования СПД, имеющие в своем составе методы расчета характеристик и методы дискретного событийного моделирования сетей передачи данных. Необходимость использования средств САПР для анализа сетей объясняется, в частности, возрастанием числа эксплуатируемых сетей и нарастанием их сложности. Широкое внедрение САПР сетей также является следствием доступности пакетов моделирования, разработанных специально для коммуникационных систем. [103]
В настоящее время существуют три основных вида ПО для моделирования коммуникационных сетей: общецелевые языки имитационного моделирования; коммуникационно-ориентированные языки моделирования; коммуникационно-ориентированные моделяторы.
Общецелевой язык имитационного моделирования - это средство, используемое в основном для построения моделей различных производственных процессов или для моделирования систем. Он может иметь также особые средства для поддержки моделирования коммуникационных систем, таких, как модули для сетей Ethernet или ATM. Примерами подобных языков имитации являются Arena [86], BONeS DESIGNER [89], GPSS/H [98], MODSIM II [106], SES/workbench [113], SIMAN/Cinema V [114],
SIMSCRIPT II.5 [117] и SLAMSYSTEM [118] (только пакеты BONeS DESIGNER и SES/workbench имеют специальные коммуникационные модули). Модель разрабатывается на имитационном языке с помощью написания программы (применяющей синтаксис или графику), используя моделирующие конструкции языка, которые включают динамические объекты (сообщения), атрибуты (типы сообщений или место назначения), ресурсы (узлы или связи) и очереди (буферы). Основным достоинством большинства подобных языков является их способность моделировать почти любые виды коммуникационных сетей независимо от их сложности или уникальности. Возможными недостатками языков по сравнению с имитаторами других типов является необходимость обладания проектировщиком навыками программирования, а также большие издержки, связанные с созданием адекватных моделей.
Коммуникационно-ориентированные языки моделирования - это языки имитации, которые непосредственно ориентированы на коммуникационные сети - OPNET Modeller [108] является именно таким пакетом. По сравнению с общецелевыми языками, OPNET Modeller позволяет сократить время и ресурсы, затрачиваемые на разработку моделей.
Коммуникационно-ориентированные моделяторы в общем виде являются имитационными пакетами, позволяющими моделировать объекты, относящиеся к специфическому классу коммуникационных сетей без программирования в его классическом понимании. Примерами основных имитаторов подобного рода являются BONeS Plan-Net [90], COMNETIII [91], L.NET II.5 [105] и NETWORK II.5 [107]. Интересующие детали моделируемой сети отмечаются для имитации выбором пунктов меню, заполнением соответствующих диалоговых окон (форм) и с использованием графического представления объектов. Типовыми конструкциями для моделирования локальной сети являются типы сетей (Ethernet, Token ring и т.д.), сетевые станции (персональные компьютеры или рабочие станции), устройства межсетевого соединения (мосты и роутеры) и генераторы потоков сообщений. Основным преимуществом подобного имитатора является то, что время разработки «программы» может быть значительно меньше, чем на языке моделирования общего применения. Часто это является очень важным фактором в условиях ограничения времени. Другое преимущество состоит в том, что подобные имитаторы имеют базовые конструкции моделирования, непосредственно отображающие компоненты коммуникационных сетей. Это очень привлекательное свойство для сетевых администраторов. Кроме того, люди без специальной подготовки и те, кто использует имитационное моделирование от случая к случаю, часто предпочитают подобные пакеты из-за легкости использования. Главный недостаток коммуникационно-ориентированных моделяторов состоит в том, что они ограничены моделированием только таких сетевых конфигураций, которые могут быть построены из набора стандартных блоков пакета. Таким образом, если коммуникационная система имеет некоторые уникальные свойства, то они могут быть смоделированы лишь приблизительно в случае использования определенных имитаторов. Существуют, однако, несколько пакетов, которые позволяют модифицировать существующие конструкции или создавать новые. Это значительно повышает гибкость моделирования.
Время, требуемое для того, чтобы построить модель сети, может быть существенно сокращено, если имитационный пакет имеет качественные встроенные модули для определенного аппаратного обеспечения или коммуникационных протоколов. Примерами таких компонентов являются Ethernet, Token ring, FDDI, мосты, роутеры, ТСРЯР, средства спутниковой и пакетной радиосвязи и т.п. Так как все коммуникационные сети обладают в некотором смысле случайностью поведения, пакет симуляции должен содержать хорошие статистические возможности. В первую очередь должен присутствовать надежный, проверенный генератор случайных чисел с множественными потоками случайных величин. Назначая различные потоки разным источникам случайной нагрузки, можно получать намного более статистически точные сравнения альтернативных конфигураций сети.
В общем случае каждый источник системной случайности (времена между отправлениями сообщений, размеры сообщений и др.) необходимо моделировать очень осторожно, выбирая распределение вероятностей, а не фиксированные значения. Если исследователь имеет дело с существующей системой, то следует собрать данные по источникам случайности, а стандартное распределение вероятностей (например, экспоненциальное или Пуассона) должно быть подобрано таким образом, чтобы обеспечить корректное представление данных. Это распределение затем используется как модель для источника случайности при имитации. Если никакое стандартное распределение не может хорошо описать данные, то при имитации вместо него используется эмпирическое распределение, основанное на наблюдаемых данных.
Разработка процедур комплексной оценки проектных решений
Анализ сетей коммутации сообщений с обходными путями является довольно затруднительным, так как для этого необходимо рассчитать вероятности использования обходных путей. Вероятности же использования обходных путей рассчитываются с использованием условных вероятностей того, что время доставки сообщений по обходному пути меньше некоторого времени t в случаях, когда по прямому пути время доставки больше t. Исключение составляют однородные сети, в которых для передачи информации используются к независимых путей одинаковой длины (А = 0). В таких сетях передача информации по обходным путям не приводит к увеличению средней нагрузки на участки сети, и поэтому при расчете вероятностно-временных характеристик отпадает необходимость вычисления вероятности использования обходных путей. Достаточно принять допущение о том, что в сети имеется некоторый идеальный алгоритм маршрутизации, который позволяет для передачи каждого сообщения выбрать из к возможных вариантов путь с минимальным временем доставки. Тогда функция распределения превышения времени передачи Рр( 0 имеет
Анализ сетей с коммутацией пакетов, в которых допускаются многопакетные сообщения, является довольно трудоемким по причине наличия эффекта «перемешивания» пакетов, содержащих разные сообщения, в процессе доставки, а также необходимости учета процедуры ограничения нагрузки. Особенностью сетей коммутации пакетов является также наличие механизмов управления потоками, производящих задержку информации у источников ее возникновения в случаях перегрузки сети, что существенным образом сказывается на времени доставки сообщений. Поэтому скорость передачи через сеть достаточно большого количества информации изменяется в пределах от максимальной скорости передачи информации до нуля в периоды полной перегрузки сети. Наиболее подходящим критерием оценки качества функционирования сети в этом случае является среднее значение скорости поступления информации к получателям.
Предположим, что в исследуемой сети используются только независимые обходные пути передачи информации, длина которых по числу участков равна длине основных путей (Д = 0). Последнее обстоятельство позволяет не учитывать увеличение средней нагрузки на сеть, которое возникало бы в случае использования более длинных обходных путей. Рассмотрим сначала сеть с виртуальными соединениями. Предположим, что все абоненты сети однородны, и в случае получения согласия на установление соединения могут выдавать информацию в сеть с одинаковой максимальной скоростью R . В результате наложения потоков от всех абонентов в сети с помощью механизма адаптивного управления устанавливается некоторое среднее распределение нагрузок у.. между всеми соседними узлами коммутации ij = l,N. Если скорость передачи информации в направлении связи между смежными узлами / и j равна R.., то это направление может одновременно без потерь и уменьшения скорости обслуживать viJ=Ry/R0 заявок. Если число заявок превысит vtj на некоторую величину wiJ9 то возможны, по крайней мере, три алгоритма дальнейшего обслуживания:
С учетом того, что виртуальное соединение проходит по некоторому пути, который может состоять из нескольких участков, результирующее замедление скорости передачи информации по рассматриваемому соединению будет определяться, очевидно, участком, вносящим максимальное замедление. Таким участком будет участок с максимальной на данный МОМеНТ удеЛЬНОЙ ОЧереДЬЮ = Wy/Vy . В реальных условиях функционирования сети из-за флуктуации очередей максимальное значение на рассматриваемом виртуальном соединении, проходящем по некоторому пути л-, можно представить в виде оо = 1-П(і- (64) функция распределения случайной величины Е, на участке у. Другими словами, Fn{H) задает вероятность того, что, по крайней мере, на одном участке случайная величина , ограничивающая результирующую скорость передачи информации, превысит %. Функция распределения максимального значения на виртуальном соединении, проходящем через несколько участков, будет равна
Теперь рассмотрим сеть, в которой каждый пакет доводится до адресата независимо от других, причем в общем случае для каждого пакета определяется кратчайший путь доставки через сеть. Предположим, что между отправителем и получателем массива информации в сети существует к независимых путей передачи. Пусть при обновлении сведений о загрузке сети процедура маршрутизации обеспечивает предоставление пути с минимальной удельной очередью на обслуживание в наиболее узком сечении каждого из имеющихся к путей. Предполагая, как и ранее, статистическую независимость очередей на всех участках сети, можно записать функцию распределения минимального значения среди максимально загруженных участков каждого из к путей в следующем виде:
Для более точного определения характеристик сетей передачи данных целесообразно использовать имитационное моделирование. Для моделирования потока заявок на обслуживание, поступающих от абонентов сети, целесообразно воспользоваться методом Монте-Карло, при котором моделируется такая случайная величина математическое ожидание которой М, равно средней моделируемой величине а. М оценивают как среднее арифметическое N реализаций случайной величины Центральная предельная теорема при весьма широких предположениях относительно % гарантирует асимптотическую нормальность распределения среднего 1 N арифметического я = — и его сходимость по вероятности к величине а. Погрешность оценки 3N не превосходит с заданной вероятностью величины Uj—, где Dq - дисперсия случайной величины д9 a t - константа, определяемая вероятностью ошибки (уровнем достоверности оценки). Иными словами, в методе статистического моделирования моделируют нормально распределенную случайную величину, и задача заключается в вычислении параметров нормального распределения. Важно заметить, что ошибка метода пропорциональна N yi. Эффективность оценки, получаемой в методе статистического моделирования, определяется величиной, обратно пропорциональной произведению дисперсии и трудоемкости оценки [81].
Для моделирования случайных процессов необходимо иметь последовательности чисел, подчиняющихся различным распределениям, например, экспоненциальному, Эрланга, нормальному и другим. Обычно для этого используют равномерно распределенные случайные числа, которые можно получить: программным путем (псевдослучайные числа); при помощи датчика случайных чисел; из заранее составленной таблицы случайных чисел.
Экспериментально доказано, что последовательности псевдослучайных чисел вполне достаточно для моделирования случайных процессов. Псевдослучайные числа, генерируемые компьютером, удовлетворяют закону равномерного распределения.
Пример использования прототипа САПР СПД
С точки зрения системного анализа задачу выбора максимально эффективного проекта можно рассматривать как выбор системы, наиболее близкой цели, причем целью является конкретное ограничение свойств, которое при данных обстоятельствах пользователь считает предпочтительным. Степень удовлетворения системы поставленной цели может быть измерена близостью действительных и желаемых проявлений тех свойств системы, которые предусмотрены целью, и определяется с помощью характеристической функции переход от которой к характеристической функции осуществляется с помощью преобразования, учитывающего зависимость между функциями v(s,s ) и p(s,s ): чем меньше значение p(s,s ), тем больше значение v(s,s ).
С точки зрения близости к достижению цели система sj является более предпочтительной системы S2 тогда и только тогда, когда v(s],s ) v(s2,s ), а величина Vv(sj,S2/s )=v(s],s )-v(s2,s ) характеризует степень целенаправленности Si относительно s2 при заданной цели s . сохраняющая упорядочение, т.е. для любых систем sj и S2 из S sjfs2 тогда и только тогда, когда U(si) U(s2), где символ / обозначает отношение предпочтения между системами sj и s2. Таким образом, цель С, обозначающая собой идеальный проект, должна быть, по меньшей мере измерима, а в случае количественной измеримости цели задача выбора наилучшего проекта сводится к решению оптимизационной задачи вида минимальное значение є, принимаемое во внимание при установлении отношения предпочтения на множестве систем S.
Свойство представительности характеризует адекватность возможного количественного описания данного свойства [4, 41].
Если при анализе проектов во внимание принимаются только критерии, которые могут быть выражены количественно, то задача выбора проектов сводится к задаче многокритериальной оптимизации. Под многокритериальной оптимизацией подразумевается исследование математической модели принятия оптимального решения одновременно по нескольким критериям эффективности. В этом случае критерий качества описывается вектором
Одним из наиболее распространенных методов решения таких задач является сведение их к одной или нескольким задачам математического программирования. При этом один из критериев (наиболее значимый) принимается в качестве целевой функции, а все остальные играют роль ограничений, определяющих допустимую область решения. Недостатком такого подхода является то, что оптимизация производится по одному критерию, а остальные могут принимать любые значения в пределах допустимых областей.
Другим подходом к многокритериальной оптимизации является построение обобщенного критерия. Для построения обобщенного критерия из количественно измеримых критериев часто используют аддитивные или мультипликативные преобразования. В случае аддитивного преобразования обобщенный критерий представляется суммой частных критериев
Эти коэффициенты могут быть положительными для максимизируемых и отрицательными для минимизируемых критериев при условии определения максимального q. Если суммируемые критерии имеют различную размерность, то перед суммированием выполняется нормировка.
Метод мультипликативных преобразований предусматривает наличие обобщенного критерия в виде произведения где показатели степени /lj также определяют важность каждого из частных критериев.
Использование методов аддитивных и мультипликативных преобразований по Парето позволяет получить решения, в которых некоторые из параметров (критериев) улучшаются за счет ухудшения других критериев. Недостатком таких решений является неограниченная возможность взаимной компенсации различных критериев, а следовательно, и наличие множества решений.
Недостаток преобразований по Парето можно частично компенсировать с помощью метода арбитражных решений Нэша. В основе этого метода лежит установление минимальных значений qx с последующим определением вектора х, максимизирующего произведение
Коэффициенты значимости Aj обычно определяются на основе субъективных оценок в результате опроса группы экспертов. Каждый из экспертов определяет в произвольном масштабе набор чисел с у, определяющих значимость z -критерия по мнению у-эксперта. Эти числа масштабируются, в результате чего получают набор коэффициентов
При определении набора оценок Сц эксперты пользуются методом ранжирования. Сначала критериям присваивают номера от 1 до т, а затем ранги. Ранг совпадает с номером, если данному критерию нет равнозначных. Если же на какой-либо позиции имеются равнозначные критерии, то их ранг равен среднеарифметическому значению их номеров. Переход от рангов к оценкам осуществляется с учетом зависимости между рангом и ценностью критерия
Достоверность результатов экспертных оценок определяется степенью согласованности этих оценок по множеству экспертов. Степень согласованности оценок определяется коэффициентом конкордации w, который определяется по формуле представляет собой отклонение суммы рангов критерия от средней их суммы для всех критериев, равной т(п+1)/2. Можно доказать, что коэффициент конкордации находится на отрезке [ОД], причем w=\ при совпадении всех ранжировок, w=0 при полной противоположности мнений экспертов. Достоверность результатов считается хорошей при w=0,7...0,8.
Наряду с методами построения обобщенных критериев иногда используют методы последовательной оптимизации. Одним из наиболее распространенных методов этой группы является метод уступок. Идея этого метода заключается в следующем: определяется пересечение этих множеств, представляющее собой множество оптимальных альтернатив.
Построение обобщенного критерия может быть выполнено на основе оценки расстояния между идеальной и рассматриваемой альтернативами. При этом идеальной считают альтернативу с вектором наиболее оптимальных критериев, которых можно достичь, а мерой
В первую из сумм включают критерии, подлежащие максимизации, а во вторую - подлежащие минимизации. Если частные критерии имеют разную размерность, то суммируют отношения вида наименьшие значения для максимизируемых критериев, и максимальные значения для минимизируемых критериев. При этом обычно вводят дополнительное требование, ограничивающее относительный уровень снижения качества для всех частных решений.
Особенности, присущие слабоструктурированным и неструктурируе-мым задачам, такие, как разнородность информации, неполнота и неопределенность исходных данных и т.д. делают привлекательным использование качественных знаний при моделировании процессов принятия решений в интеллектуальных системах. Инструментом, обеспечивающим формализацию качественной информации, является понятие лингвистической переменной.
Лингвистическая переменная определяется кортежем (а, Т, U, G, М), в котором а - название переменной; Т={Т(} - терм-множество или множество лингвистических значений переменной a; G - синтаксическое правило, порождающее значения 7} переменной ос, a М - семантическое правило, которое ставит в соответствие каждой нечеткой переменной Tt ее смысл M(Tj), то есть нечеткое подмножество M(Tj) универсального множества U. Конкретное значение Tt, порожденное синтаксическим правилом G, называется термом. Терм, состоящий из одного слова или нескольких слов, всегда фигурирующих вместе, называется атомарным термом. Терм, состоящий из одного или более атомарных термов, называется составным термом. Будем говорить, что лингвистическая переменная X структурирована, если ее терм-множество Т(Х) и функцию М, которая ставит в соответствие каждому элементу терм-множества его смысл, можно задать алгоритмически. Из этих соображений синтаксическое и семантическое правила, связанные со структурированной лингвистической переменной, можно рассматривать как алгоритмические процедуры для порождения элементов множества Т(Х) и вычисления смысла каждого терма в Т(Х) соответственно [19, 54].
