Содержание к диссертации
Введение
ГЛАВА 1. Показатели качества обслуживания ОКС 7 и сигнальная нагрузка 51
1.1. Общие положения 51
1.2. Интегральные показатели качества 55
1.3. Требования к показателям качества подсистем 64 ОКС 7
1.4. Сигнальная нагрузка 77
1.5. Выводы 94
ГЛАВА 2. Методы анализа задержек сигнальных сообщений в сети ОКС 7 96
2.1. Предварительные замечания 96
2.2. Методы расчета задержек в звене сигнализации 97
2.3. Метод оценки среднего значения маршрутной задержки 112
2.4. Особенности вычислений характеристик задержек сигнальных сообщений 115
2.5. Выводы 132
ГЛАВА 3. Метод построения плана маршрутизации сигнальных сообщений 134
3.1. Постановка задачи 134
3.2. Метод построения плана маршрутизации по коду пункта назначения 140
3.3. Метод расчета емкости пучков звеньев сигнализации 148
3.4. Метод расчета значений кодов селекции звена сигнализации 158
3.5. Выводы 169
ГЛАВА 4. Рекомендации по особенностям расчета сети ОКС 7 171
4.1. Типовая структура сети сигнализации 171
4.2. Расчет планов маршрутизации по кодам пунктов назначения 174
4.3. Расчет емкости пучков звеньев сигнализации 176
4.4. Разделение сигнальной нагрузки 184
4.5. Замечания к решению задачи о максимальном потоке на графе сети сигнализации 199
4.6. Программные средства для расчета сетей ОКС 7 212
4.7. Выводы 221
ГЛАВА 5. Методы анализа моделей мультисервисных сетей связи 223
5.1. Мультисервисная сеть с одноадресными соединениями 223
5.2. Модели и методы анализа сетей с многоадресными соединениями 232
5.3. Точный метод расчета вероятностных характеристик сети с многоадресными соединениями древовидной структуры 253
5.4. Постановка задачи анализа сети с двумя типами соединений 263
5.5. Выводы 267
ГЛАВА 6. Анализ мультисервиснои сети с одноадресными и многоадресными соединениями 269
6.1. Модель отдельного звена сети с одноадресными и многоадресными соединениям 269
6.2. Метод расчета вероятностных характеристик отдельного звена сети 277
6.3. Метод просеянной нагрузки 282
6.4. Анализ показателей качества обслуживания мультисервисных сетей с двумя типами соединений 285
6.5. Выводы 301
Заключение 303
Список источников
- Интегральные показатели качества
- Метод оценки среднего значения маршрутной задержки
- Метод построения плана маршрутизации по коду пункта назначения
- Замечания к решению задачи о максимальном потоке на графе сети сигнализации
Введение к работе
Тенденции развития современных телекоммуникаций определяются целым рядом факторов, среди которых решающую роль следует отвести быстрому прогрессу технологий производства электроники, компьютерных средств, волоконной оптики и коммутационного оборудования. Это обеспечивает надежные, дешевые и высокопроизводительные средства для передачи стремительно растущих информационных потоков, порождаемых в результате небывалого спроса потребителей на услуги связи. Уже ни у кого не вызывает сомнения, что на рубеже XX-XXI веков началась и продолжается конвергенция телекоммуникационных, компьютерных и информационных технологий, а развитие телекоммуникационных сетей идет в направлении создания единой мультисервисной сети [2, 4, 30, 43, 63, 65, 66, 69, 137, 205, 248, 278], закладывающей основу для возникновения на нашей планете глобального информационного сообщества.
Существенные изменения в области технологий и потребительского спроса предъявляют новые требования к производительности и пропускной способности всех видов сетей, а также к постоянному наращиванию их «интеллекта», позволяющего в кратчайшие сроки разрабатывать и расширять спектр новых услуг [3, 6, 26, 36, 63, 70, 87, 98, 122, 123, 200, 270]. Следует отметить, что наряду с появлением новых услуг продолжается процесс насыщения рынка традиционными услугами связи, хотя от момента начала их коммерческой эксплуатации прошло не так уж и мало времени. Прежде всего, это касается услуг. предоставляемых на базе цифровых сетей связи - цифровой сети с интеграцией служб (ЦСИС) [4, 48, 252, 260], интеллектуальной сети связи (ИСС) [6, 26, 36, 87, 122, 278] и сети сотовой подвижной связи (СПС) [10, 65, 154, 236]. Во всем мире в создание цифровых сетей связи за последние три десятилетия были инвестированы колоссальные средства, этот процесс еще далек от завершения, а их конвергенция с IP сетями позволяет телекоммуникационным операторам и поставщикам услуг получать новые дополнительные доходы.
На Единой сети электросвязи Российской Федерации (ЕСЭ РФ) процесс построения цифровых сетей был активизирован примерно с начала 1990-х годов, а в настоящее время наблюдается стабильной рост клиентской базы и развитие сетевой инфраструктуры. До настоящего времени ядром конвергирующих сетей является телефонная сеть общего пользования (ТфОП), имеющая наиболее развитую инфраструктуру и обеспечивающая взаимодействие ЦСИС, ИСС и СПС на базе системы общеканальной сигнализации № 7 (ОКС 7) [3-5, 35, 47, 86-87, 91, 111. 170-200, 228, 234, 252]. Существенную роль ТфОП играет и в предоставлении услуг пакетной передачи данных путем создания точек присутствия Интернет. Наиболее быстрыми темпами растут сети операторов подвижной связи, число абонентов которых на конец 2004 года превысило 60 миллионов, то есть общий уровень проникновения составил примерно 1/3. Построение сетей подвижной связи в России еще далеко до завершения, как в части покрытия территории обслуживания базовыми станциями, так и в части внедрения новых коммутационных станций. Следует отметить, что крупнейшие отечественные операторы СПС, накопили значительный опыт в планировании и эксплуатации своих сетей и параллельно с их экстенсивным развитием все большее внимание обращают на оптимизацию уже существующих сетевых ресурсов. Этот процесс во многом определяется жесткой конкуренцией на рынке услуг подвижной связи, которая естественным путем приводит участников рынка к необходимости повышения качества обслуживания абонентов, что в свою очередь предопределяет необходимость приведения показателей качества функционирования сетей в соответствие с требованиями международных стандартов и национальных нормативных документов. В сетях подвижной связи помимо проблем покрытия территории, наибольшее внимание уделяется оптимизации функционирования сети ОКС 7, которая кроме традиционных процедур установления соединения на вторичной сети, обеспечивает передачу больших объемов данных без установления соединения, например, данные роуминга, короткие и мультимедийные сообщения [4, 10, 154, 236].
Быстрыми темпами развиваются сети стационарной связи, где все большую роль в предоставлении новых услуг играют стандартизованные платформы ИСС. Как справедливо отмечено в предисловии к книге [5], по ряду объективных и субъективных причин развитие ИСС в России несколько задержалось, а до сих пор операторы находили выход из положения за счет «легковесных» интеллектуальных платформ, опыт применения которых за рубежом хорошо известен. Такого рода решения дают быструю отдачу при внедрении отдельно взятых услуг, например, таких, как услуга предоплаты по кредитной карте. Однако зарубежный опыт и накопленный в России потенциал показывают, что создание ИСС в национальном масштабе невозможно без широкого внедрения интеллектуальных платформ, отвечающих требованиям международных стандартов и национальных технических спецификаций. В настоящее время ведущие Российские операторы стационарных сетей, в том числе, крупнейшие операторы транзитных сетей ОАО «Ростелеком» и ОАО «Межрегиональный ТранзитТелеком» вплотную подошли к масштабной реализации платформ ИСС на своих сетях. Значительная часть операторов, входящих в холдинг «Связьинвест», предоставляет не менее одной из известных услуг ИСС.
Известно [5, 7, 36, 47, 86], что необходимым условием внедрения ИСС является наличие развитой сети ОКС 7 способной обслуживать значительные объемы сигнального трафика, который, как и в случае СПС. возникает как от услуг, ориентированных на установление соединение пользователей, так и от услуг, не ориентированных на установление соединения, обеспечивая взаимодействие коммутационных платформ с сетевыми базами данных, например, узлами управления услугами ИСС.
Резюмируя вышесказанное, следует особо подчеркнуть, что предоставление новых высококачественных услуг сетей ЦСИС, ИСС и СПС практически невозможно без высокоразвитой и надежно функционирующей сети ОКС 7, что предопределяет на ближайшую и долгосрочную перспективу комплекс масштабных научно-технических задач по анализу и расчету показателей качества функционирования сетей сигнализации [4, 5, 18, 37, 82, 88, 111, 114, 130, 134, 153, 160, 196, 197, 247,251,269,279].
Информационные потоки, определяемые все более интенсивным характером предоставления традиционных услуг и порождаемые в результате внедрения новых услуг, сильно различаются по своему составу и объему требуемых ими сетевых ресурсов. Применение цифровых технологий передачи информации отнюдь не означает решение проблем наличия достаточного объема ресурсов для обслуживания трафика в современных мультисервисных сетях. Здесь имеются в виду, прежде всего ресурсы цифровых линий, по которым осуществляется передача информационных потоков, например, передача изображений с высокой разрешающей способностью или видео фильмов по запросу пользователей [43, 63, 66, 69, 92, 132, 133, 141, 144, 205, 227, 237, 248, 258, 259]. Следует подчеркнуть, что информационные потоки, порожденные новыми услугами, требуют для своей передачи существенно больший ресурс, чем в случае традиционных услуг передачи речи. Уже сейчас доля трафика, передаваемого традиционным способом по технологии коммутации каналов в наиболее развитых странах мира, составляет менее половины всего объема информационной нагрузки.
Проблема нехватки ресурсов в мультисервисных сетях решается несколькими способами. Самый простой из них, который на этапе экстенсивного развития цифровых сетей используют большинство операторов, заключается в создании новых линий связи или во внедрении новых технологий передачи, например, по оптоволокну. Фактически данный способ решает проблему исключительно с точки зрения повышения скорости передачи. Заметим, что в настоящее время такой подход начал применяться и для повышения качества обслуживания в сетях ОКС 7, где теперь стала доступна технология передачи данных со скоростью 2 Мбит/с, вместо традиционной скорости работы звена данных сигнализации - 64 кбит/с.
Одним из наиболее известных и на сегодняшний день исследованных способов повышения эффективности использования цифровых линий связи в мультисервисных сетях является применение различного рода схем преимущественного предоставления ресурсов для той части информационных потоков, которые для данной конкретной сети и в данной конкретной ситуации представляют наибольшую ценность с точки зрения оператора и его клиентов. В отличие от первого способа, преимущественное предоставление ресурсов может быть решено оперативными средствами, то есть не требует существенных инвестиций в создание новых линий связи и во внедрение дополнительного коммутационного оборудования. Однако это не означает, что решение проблемы нехватки ресурсов таким способом не потребует каких-либо средств вообще. Известно, что улучшение качества обслуживания без увеличения скорости передачи, а именно об этом и идет речь в данном случае, является весьма непростой задачей, переводящей решение проблемы в плоскость управления сетевыми ресурсами, а в некоторых случаях и сетью в целом [68, 69, 70]. Аналогом масштаба решаемой задачи может служить, например, внедрение динамической маршрутизации вызовов на сетях с коммутацией каналов [29, 213-215]
В контексте обсуждаемой выше проблемы, существует ряд других подходов и технологий эффективного использования ресурсов цифровых сетей, среди которых наиболее актуальным для мультисервисных сетей является применение технологий многоадресной передачи информационных потоков (принцип «точка - много точек») наряду с традиционной одноадресной передачей (принцип «точка - точка»). Известен целый ряд протоколов многоадресной передачи, которые также
-21 называют протоколами мультивещания от английского термина multicasting protocols, а мультисервисные сети, построенные на базе таких протоколов, называют сетями мультивещания (multicasting networks) [131-133, 135, 141, 142, 144, 155, 158, 163, 201, 233, 242, 245, 262, 263, 268, 272].
Появление механизмов многоадресной передачи информации является существенным шагом на пути решения проблемы эффективного использования сетевых ресурсов. Существует мнение, что внедрение многоадресной передачи данных в ІР-сетях - такая же революция в области информационных технологий, как в свое время появление технологии World Wide Web. Такая оценка вовсе не случайна, спрос на мультивещание неуклонно растет как со стороны пользователей Интернет, так и со стороны предприятий, желающих рационально использовать ресурсы своих внутренних информационных сетей. Чем же так привлекательно мультивещание? Традиционно передача данных в сети происходит по принципу «точка-точка», то есть сервер передает каждому из клиентов копию запрашиваемой последним информации. Однако в случае, если нескольким клиентам требуются одновременно идентичные данные, этот способ оказывается нерациональным, поскольку приводит к дублированию информации на некоторых звеньях сети, и, следовательно, к фактическому снижению пропускной способности сети. Ситуация становится критической, когда необходимо передавать большие объемы данных, например аудио- или видеопотоки. Суть основного принципа мультивещания, сформулированного в базовых международных рекомендациях [142, 201, 245, 272], заключается в том, что источник информации, например, сервер услуг отправляет в сеть один экземпляр данных, а задача ее доставки нескольким распределенным по сети пользователям решается так, чтобы копирование происходило лишь на тех участках сети, где это действительно необходимо.
Первые спецификации многоадресной передачи (RFС 966. RFC 1054, RFC 1075) были разработаны IETF в середине 1980-х годов, однако эта технология стала востребована только в последние годы с появлением видеоконференций, а также теле- и радиовещания на базе компьютерных сетей. Следует отметить, что телевещание через Интернет стало возможным только благодаря технологии многоадресной передачи данных, так как при традиционной передаче одновременно телевизионные каналы с приемлемым качеством могут смотреть всего лишь сотни пользователей, чего явно недостаточно при современных масштабах Интернет.
Таким образом, в современных мультисервисных сетях наряду с традиционными одноадресными соединениями для обслуживания запросов пользователей должны применяться многоадресные соединения. которые позволяют снизить остроту нехватки ресурсов цифровых линий связи. Тем не менее, как и ранее, основным показателем качества обслуживания в мультисервисных сетях является вероятность блокировки запроса пользователя, которая возникает по целому ряду причин, в том числе и по причине отсутствия достаточного числа свободных единиц ширины полосы пропускания на тех звеньях сети, по которым проходит маршрут передачи информационного потока от источника к пользователю [11, 21, 29, 43, 56, 56, 62, 69, 127, 131, 132, 140, 209-215, 241, 248, 254. 255]. Поэтому в современных условиях особенно актуальной становится проблема обеспечения требований к показателям качества обслуживания в цифровых сетях с двумя типами соединений - одноадресными и многоадресными. Данная проблема порождает новый класс задач. связанных с разработкой и анализом моделей, позволяющих осуществлять анализ и эффективные вычисления одного из основных показателей качества обслуживания мультисервисных сетей -вероятности блокировки запросов пользователей из-за отсутствия достаточного числа ресурсов цифровых линий связи в условиях установления как одноадресных, так и многоадресных соединений.
На современном этапе развития телекоммуникаций, все вышесказанное определяет актуальность задач анализа и расчета показателей качества обслуживания в цифровых сетях связи, которые лежат как в плоскости базовой сети, обеспечивающей передачу информационных потоков, так и в плоскости сети сигнализации, которая управляет соединениями базовой сети и помимо этого обеспечивает передачу данных пользователей без установления речевого соединения. Поэтому целью диссертационной работы является решение фундаментальной научной проблемы - разработка новых моделей и методов, предназначенных для анализа и расчета показателей качества обслуживания в современных сетях связи, а также применение полученных методов для решения практических задач, имеющих важное народно-хозяйственное значение для отрасли связи:
- исследования и разработка методов планирования сетей сигнализации, создание моделей и методов для расчета маршрутных характеристик сигнальных сообщений, включая развитие методов анализа показателей качества обслуживания;
- разработка модели функционирования мультисервисной сети с одноадресными и многоадресными соединениями, разработка точных и приближенных методов для анализа и расчета вероятностных характеристик, включая вероятности блокировок соединений пользователей.
Достижение сформулированной цели осуществляется путем решения перечисленных ниже задач.
1. Анализ показателей качества обслуживания, актуальных для процесса планирования сетей ОКС 7 с учетом специфики сигнального трафика в СПС и ИСС. Развитие методов оценки величины сигнальной нагрузки и методов анализа задержек сигнальных сообщений. Результаты решения данной задачи применяются при расчете маршрутизации сигнальных сообщений в сети ОКС 7.
2. Разработка унифицированного процесса расчета сети ОКС 7. включающего расчет планов маршрутизации по коду пункта
-24 назначения, расчет приоритетов выбора направления передачи. расчет емкости пучков звеньев сигнализации, разделение сигнальной нагрузки и расчет значений кодов селекции звена сигнализации (СЗС).
3. Разработка в терминах теории графов модели маршрутизации сигнальных сообщений. Формулировка ограничений на построение графа маршрутов сети сигнализации с учетом числа транзитных пунктов на маршруте, требования к отсутствию на маршруте циклов и петель, выбора приоритетов направления передачи в пунктах сигнализации, равномерного разделения потоков сигнальной информации между звеньями и пучками звеньев сигнализации.
4. Разработка методов расчета орграфов маршрутизации по кодам пунктов назначения, методов расчета взвешенных орграфов для выбора направления передачи и равномерного разделения потоков сигнального трафика, методов раскраски мультиграфа сети сигнализации для расчета значений кодов СЗС.
5. Разработка рекомендаций по применению разработанных методов к анализу и расчету сетей ОКС 7 с типовой структурой. Анализ потоков на графе сети сигнализации. Создание эффективных программных средств для поддержки процесса планирования сетей ОКС 7.
6. Построение модели мультисервиснои сети с одноадресными и многоадресными соединениями и несколькими источниками информации. Разработка и анализ модели функционирования отдельного звена сети с двумя типами соединений и разработка эффективных вычислительных алгоритмов свертки для расчета вероятностных характеристик модели.
7. Разработка точных методов анализа вероятностных характеристик сети мультивещания, включая точные методы для расчета вероятности блокировок соединений пользователей на отдельном звене сети и в сети древовидной структуры с одним источником информации. 8. Развитие приближенного метода для расчета вероятностей блокировок соединений в мультисервисной сети с одноадресными и многоадресными соединениями, численный анализ вероятностных характеристик функционирования сети и оценка точности приближенного метода. Из сформулированных выше целей и задач вытекает структура диссертационной работы, основной текст которой состоит из шести глав. Главы с первой по четвертую посвящены созданию новых методов анализа и расчета сетей ОКС 7. В последних двух главах диссертационной работы (пятая и шестая главы) решается проблема создания новых моделей и методов анализа мультисервисных сетей с одноадресными и многоадресными соединениями.
Прежде чем переходить к общему описанию диссертационной работы, следует определиться с методами исследований, положенными в ее основу, а также обосновать научную новизну и значимость решаемых в ней проблем.
Проблема, соответствующая первой цели данной диссертационной работы, на первый взгляд формулируется достаточно просто: для сети ОКС 7 с заданной структурой требуется рассчитать показатели качества ее функционирования и маршрутные таблицы для пунктов сигнализации сети с учетом ограничений на структурные и нагрузочные параметры. Данные ограничения вытекают из требований международных стандартов [170-200], нормативных документов отрасли связи и специфики построения национальных сетей ОКС 7 [4, 5, 9, 35, 37, 44, 47, 81, 82, 88. 111, 112, 118-121, 126]. Ясно, что в такой постановке задача имеет несколько возможных сценариев решения. На практике эта задача решается проектными организациями и операторами сетей всякий раз на этапе планирования конкретной сети ОКС 7. Если сеть имеет небольшую размерность и функционирует в основном в связанном режиме сигнализации, то процесс расчета может осуществляться «вручную», т.е. без применения специальных методов и программных средств. Решение задачи в случае сети большой размерности, функционирующей в смешанном режиме сигнализации (связанном и квазисвязанном режимах), практически невозможно в отсутствие адекватных математических моделей и методов, эффективных вычислительных алгоритмов и развитых специализированных программных средств. Автор берет на себя смелость утверждать, что до сих пор в России и за рубежом нет публикаций, где сформулированная в таком виде проблема решена полностью в одной из ее возможных постановок, ее решение строго обосновано математически, а математические методы доведены до вычислительных алгоритмов. Сразу оговоримся, что в данной диссертационной работе не ставится задача оптимизации сети ОКС 7 по некоторому критерию, например, надежностному или стоимостному. Решение задачи в целом с учетом оптимизации автору не известно, а известны лишь подходы и методы решения некоторых частных случаев (см. например, [129, 162, 206]), которые не являются предметом исследований данной диссертационной работы.
Для решения этой важной и сложной научно-технической проблемы необходимо обладать опытом в планировании реальных сетей и большим объемом информации об ОКС 7, во-первых, как об открытой системе протоколов (архитектура ОКС 7), во-вторых, о принципах построения и функционирования сети сигнализации (сетевой аспект ОКС 7), и, в-третьих, глубоко понимать проблемы качества функционирования ОКС 7 и обслуживания сигнального трафика (показатели качества ОКС 7 и сигнальная нагрузка). Следует особо подчеркнуть, что исследования в такой многогранной проблемной области практически немыслимы в отсутствие опоры на фундаментальные теоретические методы и масштабные инженерные решения. Не принижая вклад зарубежных исследователей и инженеров в проблематику систем сигнализации по общему каналу, несомненно, следует считать давно сложившейся школу отечественных специалистов, благодаря усилиям которых были созданы и эксплуатируются современные сети ОКС 7 российских операторов [2-7. 12, 17, 18,27,35-37,45-49, 54,55, 88,99, 102-105, 111, 112, 114, 118-121, 130, 146, 149, 156, 225, 253]. В эту крупную область научно-технических исследований и разработок за последние 30 лет сделан огромный вклад известными российскими учеными и инженерами-связистами, со многими из которых автор диссертационной работы обсуждал или вместе решал задачи и проблемы создания отечественных методов и средств анализа и расчета сетей ОКС 7. В числе этих исследователей и практиков, фамилии которых перечислены ниже в алфавитном порядке без указания их ученых степеней, званий и должностей, следует назвать: А.С. Аджемова. Г.П. Башарина, А.И. Васильченко, Б.С. Гольдштейна, В.Г. Дедоборща. М.А. Жаркова, А.Е. Кучерявого, В.А. Наумова, В.П. Полищука. Н.А. Соколова, СП. Соловьева, Ю.И. Филюшина, М.А. Шнепс-Шнеппе, П.А. Юнакова, Г.Г. Яновского и некоторых других.
Теоретические и прикладные основы отечественных исследований ОКС 7 также базируются в основном на результатах российских ученых в области дискретной математики [1, 41, 42, 53, 71, 77], теории вероятностей и теории массового обслуживания [13, 20, 29, 32-34, 58, 83, 139], теории телетрафика [11, 15, 19, 21, 23, 62, 69, 70, 75, 76, 127, 237]. Фундаментальный вклад в эти области внесли A.M. Александров, Г.П. Башарин, П.П. Бочаров, В.М. Вишневский, Б.В. Гнеденко, В.А. Ершов. В.А. Жожикашвили, Г.П. Климов, В.Г. Лазарев, В.А. Наумов, В.И. Нейман, А.П. Пшеничников, Б.А. Севастьянов, С.Н. Степанов, А.Д. Харкевич, М.А. Шнепс-Шнеппе и др.
Начало отечественных исследований и разработок в области систем сигнализации по общему каналу следует отнести к середине 1970-х годов. Основные работы были сконцентрированы в двух крупнейших отраслевых научно-исследовательских центрах - ЦНИИС и ЛОНИИС, а с начала 1990-х годов в этот список, несомненно, следует включить НТЦ «Комсет» и ОАО «Гипросвязь». В Российской высшей школе
-28 исследования и разработки велись и продолжают вестись в МТУСИ, СПбГУТ им. М.А. Бонч-Бруевича и в Российском университете дружбы народов (РУДН), а в Российской академии наук это процесс поддерживают ИППИ РАН и ИПИ РАН. Следует также отметить, что в последние десять лет существенный вклад в постановку прикладных аспектов решаемых задач сделали крупнейшие Российские операторы сетей связи - ОАО «Ростелеком», ЗАО «Межрегиональный ТранзитТелеком», ОАО «Уралсвязьинформ», ОАО «Центртелеком», ОАО «МГТС» и некоторые другие.
Зарубежные, в основном Европейские и Северо-Американские, разработки в области анализа и расчета сетей ОКС 7 по понятным причинам всегда опережали отечественные исследования. Наибольшее число зарубежных публикаций приходится на 1980-е и самое начало 1990-х годов, среди которых в первую очередь следует отметить работы [134, 138, 165-167, 204, 206, 217-219, 221, 239, 243, 239, 246, 247, 251, 253. 257, 265, 267, 269, 270, 277]. Наиболее значимыми авторами результатов в этой области являются Р. Адаме, М. Бафутто, Й. Ватанабе, Г. Вилманн, Б. Джабарри, Й. Икеда, В. Клейн, Л. Краусс, П. Кюн, А. Модаресси, В. Рамасвами, Т. Рассел, Г. Руфа, Р. Скуг и некоторые другие.
Анализ публикаций, посвященных планированию и расчету сетей сигнализации по общему каналу, показывает, что зарубежные исследования в этой области к началу 1990-х годов практически прекратились, и, наоборот, в России этим исследованиям стали придавать все большее и большее значение. Этот факт объясняется естественным образом, поскольку на этот момент практически все технологически развитые страны построили сети ОКС 7, а в России этот процесс только начался. Следует отметить, что отнюдь не все результаты зарубежных исследований и разработок можно было применить либо, по крайней мере, адаптировать к специфике отечественных сетей. В первую очередь это объясняется размерностью сетей сигнализации и спецификой построения Российских сетей связи в целом. В главе 1 диссертационной работы показано, что с точки зрения международных стандартов сети ОКС 7 на ЕСЭ РФ в целом относятся к сетям большой размерности. Это означает, что опыт Европейских стран не может быть напрямую использован в отечественной практике, хотя целый ряд результатов оказывается весьма полезным в процессе анализа основных показателей качества обслуживания ОКС 7. Сети сигнализации США и Канады сравнимы по масштабу с Российским сетями, но их принципы построения определяются Северо-американскими стандартами, которые имеют ряд существенных отличий от международных и Европейских стандартов [4. 5, 9, 47, 81, 82, 88, 118-121]. В первую очередь это касается правил маршрутизации сигнальных сообщений и разделения сигнальной нагрузки между звеньями сигнализации для равномерной загрузки сетевых элементов. Суть различия состоит в том, что стандарты ANSI (Американский национальный институт стандартов) позволяют в адресной части сигнальной единицы (в этикетке маршрутизации) использовать поля большей длины, чем в случае международных и европейских стандартов. Именно это различие является определяющим при построении сетей сигнализации большой размерности. Автор данной диссертационной работы принимал участие в работе международной группы, которая в начале 1990-х годов разрабатывала Российские национальные технические спецификации ОКС 7. Именно тогда было принято решение, которое не позволило в дальнейшем адаптировать стандарты ANSI к специфике Российских сетей связи. По мнению некоторых специалистов, это решение негативно повлияло на принципы построения Российских сетей ОКС 7, особенно в части нумерации пунктов сигнализации и пропускной способности сети в целом. Заметим, что в Китае было принято гибкое решение, позволяющее на национальном уровне использовать расширенный формат адресной части сигнальных сообщений.
Резюмируя мысль предыдущего абзаца, приходим к выводу, что на момент начала активного создания в России цифровых сетей отсутствовали зарубежные и отечественные методы, которые позволяли бы решать задачи расчета сетей ОКС 7 в целом, начиная от построения теоретико-графовых и вероятностных моделей, и, заканчивая созданием адекватных программных средств, позволяющих проводить эффективные вычисления в процессе планирования сети сигнализации. Таким образом, сформулированные выше задачи, посвященные ОКС 7, являются весьма актуальными, а для их решения требуется разработка новых моделей и методов для анализа и расчета соответствующих характеристик. Решению этих задач посвящены первые четыре главы диссертационной работы. Все, что изложено в этих главах, основано на личном, более чем 20-летнем, опыте автора, полученном в процессе участия в российских и зарубежных проектах, посвященных решению конкретных научно-технических задач в области планирования и расчета сетей ОКС 7 [2. 4. 16-18, 44-46, 48, 54, 55, 85, 88, 90, 94-97, 99, ,100, 105-106, 112, 114, 146. 149, 156, 228, 253, 255, 273-276], в работе по подготовке вкладов в труды МСЭ-Т [150, 169], в создании программного обеспечения протоколов ОКС 7 [223 - 226] и разработке инструментальных программных средств, предназначенных для моделирования и расчета систем и сетей телекоммуникаций [49, 50, 146, 229 - 232, 238].
Перейдем теперь к обоснованию актуальности и новизны проблемы анализа и расчета мультисервисных сетей с одноадресными и многоадресными соединениями, возникновения которой, судя по публикациям, следует отнести к середине 1990-х годов. К этому моменту исследования мультисервисных сетей с одноадресными соединениями были в основном завершены. Существенный вклад в эту проблематику сделали как зарубежные (В. Иверсен, Д. Кауфман, Ф. Келли, Л. Клейнрок. К.Росс и др.), так и отечественные исследователи (Г.П. Башарин, В.А. Лагутин, В.А. Наумов, С.С. Степанов и др.). Первые работы, посвященные анализу мультисервисных сетей с многоадресными соединениями, появились примерно в то время, когда уже сложились все предпосылки для масштабного внедрения протоколов мультивешания. В этой области наиболее значимые исследования проводились практически одновременно в Технологическом университете г. Хельсинки, Финляндия [208-210, 241] и на кафедре систем телекоммуникаций РУДН [21, 84, 89, 92, 93, 105, 108, 109, 157, 250, 255]. Разработанные в этих исследовательских коллективах модели имеют ряд отличий, а основным их сходством является представление модели функционирования сети в виде обратимого марковского процесса (ОМП) с мультипликативным стационарным распределением вероятностей состояний [11, 19, 20, 21, 56, 57, 69, 202-203, 212-215, 248, 249].
Одна из первых работ, посвященных анализу разделения ресурсов широкополосной цифровой сети в условиях предоставления услуг с двумя типами соединений (одноадресными и многоадресными), была опубликована К. Боуссета и А-Л Бейлотом в 1999 году [140]. Однако, эта модель, хотя и позволяет использовать для расчетов известный подход Д. Кауфмана [14, 211, 213, 248], но не учитывает основной особенности мультивещания в цифровых сетях - совместного использования одних и тех же ресурсов при обслуживании многоадресных соединений от одного и того же источника информационного потока. Несколько позднее Й. Виртамо с соавторами в рамках разрабатываемой ими модели показывают, что при анализе разделения ресурсов цифровых линий в мультисервисных сетях необходимо учитывать нагрузку, создаваемую как многоадресными, так и многоадресными соединениями [208, 241]. В этих исследованиях на каждом звене сети трафик одноадресных соединений (unicast connections) считается фоновым (background traffic) по отношению к трафику многоадресных соединений. Это несколько упрощает картину, хотя и облегчает анализ ввиду некоторых предположений. Кроме того, данные исследования были далеки от завершения ввиду отсутствия эффективных методов, предназначенных для масштабного вычислительного эксперимента.
Таким образом, проблема анализа и расчета показателей качества мультисервисных сетей с одноадресными и многоадресными соединениями является актуальной ввиду современного состояния и перспектив развития сетей мультивещания, и новой в теоретическом и практическом плане, поскольку исследования во всем мире только начаты и еще рано говорить об их завершении в целом. Решению именно этой, новой, с точки зрения современного состояния теории телетрафика, проблеме посвящены две последние главы данной диссертационной работы.
Говоря о диссертационной работе в целом, ее научная новизна состоит в создании теоретических основ, методов анализа и расчета показателей качества обслуживания в сетях ОКС 7, а также в создании нового направления в области разработки моделей и методов анализа вероятностных характеристик мультисервисных сетей с одноадресными многоадресными соединениями. Из изложенного выше вытекают основные положения, определяющие научную новизну и значимость диссертационной работы.
1. Разработан метод анализа показателей качества обслуживания сетей ОКС 7 и формализован процесс расчета сети сигнализации, включая расчет плана маршрутизации сигнальных сообщений, расчет приоритетов выбора направления передачи, расчет емкости пучков звеньев сигнализации и разделения сигнальной нагрузки между звеньями и пучками звеньев сигнализации.
2. Впервые сформулирована в терминах теории графов задача маршрутизации сигнальных сообщений в сети ОКС 7. Получены ограничения на построение графов и мультиграфов маршрутов, которые адекватно отражают принципы маршрутизации сигнальных сообщений в соответствии с требованиями международных рекомендаций.
3. Разработаны алгоритмы для расчета корректного и масштабируемого плана маршрутизации сигнальных сообщений с заданным числом транзитных пунктов на маршруте, отсутствием на них циклов и петель, с назначением заданного числа приоритетов для выбора направлений передачи, с равномерным разделением сигнальной нагрузки между звеньями и пучками звеньев сигнализации.
4. Разработана модель и метод анализа вероятностных характеристик сети многоадресной передачи. Сформулированы предположения, позволяющие описать функционирование сети в виде обратимого марковского процесса с мультипликативным представлением стационарного распределения вероятностей состояний модели. Для отдельного звена сети и сети многоадресной передачи древовидной структуры разработаны точные методы для расчета вероятностных характеристик.
5. Впервые разработана модель мультисервисной сети с одноадресными и многоадресными соединениями. Предложен точный метод для расчета вероятностных характеристик отдельного звена сети. Для приближенного расчета вероятностей блокировок соединений пользователей в сети с двумя типами соединений реализовано развитие метода просеянной нагрузки. Проведен вычислительный эксперимент и дана оценка погрешности приближенного метода.
Практическая ценность результатов диссертационной работы заключается в том, что выполненные в ней исследования и разработанные методы позволяют осуществлять мероприятия, выполняемые при планировании цифровых сетей связи на основе адекватных математических моделей и эффективных алгоритмов расчета характеристик маршрутизации и показателей качества обслуживания. С целью широкого применения полученных результатов в научно-исследовательских, проектных организациях и в компаниях операторов сетей связи на основании теоретических исследований разработаны алгоритмы и программные " средства для поддержки процесса планирования сетей сигнализации в части маршрутных таблиц и показателей качества обслуживания. Программные средства применены для расчета сетей сигнализации в условиях реальных структур сети, значений нагрузочных параметров, возможностей организации основных и альтернативных маршрутов, а также внедрения на сети выделенных транзитных пунктов сигнализации. Высокая производительность программных средств позволяет проектировщику выполнять многовариантные вычисления и на их основе принимать наиболее эффективные технические решения.
Результаты диссертационной работы легли в основу лекционных курсов, постановок задач для выпускных работ бакалавров по направлению 510200 «Прикладная математика и информатика», магистерских диссертаций по специализации 510210 «Программное обеспечение вычислительных сетей» и кандидатских диссертаций по специальности 05.13.17 «Теоретические основы информатики» на кафедре систем телекоммуникаций факультета физико-математических и естественных наук РУДН.
В приложении к диссертационной работе содержатся документы, подтверждающие внедрение полученных автором научных результатов.
Перейдем теперь к краткой характеристике содержания диссертационной работы.
Интегральные показатели качества
В рекомендациях МСЭ-Т различают два способа установления соединений сигнализации: установление соединения сигнализации «от-звена-к-звену» (link-by-link signaling) и установление соединения сигнализации «из-конца-в-конец» (endo-end signaling). Для краткости также говорят о сигнализации «от-звена-к-звену» и о сигнализации «из-конца-в-конец». Мы будем использовать такую терминологию в тех случаях, когда это не вызывает двусмысленного толкования.
При сигнализации «от-звена-к-звену» сигнальные сообщения обрабатываются подсистемами пользователей ОКС 7 в оконечных пунктах (SEP) и во всех промежуточных пунктах сигнализации (SP) гипотетического соединения, т.е. в пунктах сигнализации всех станций базовой сети связи (оконечных и транзитных), где осуществляется коммутация информационных каналов. При сигнализации «из-конца-в-конец» обработка сигнальных сообщений подсистемами пользователей осуществляется только в оконечных пунктах (SEP). Промежуточными пунктами в гипотетических соединениях при сигнализации «из-конца-в-конец» являются только пункты с функциями STP и SPR.
Показатели качества функционирования гипотетических соединений нормируются МСЭ-Т в зависимости от размерности сетей ОКС 7 тех стран, через которые проходят пути этих соединений. Сеть ОКС 7 некоторой страны считается сетью большой размерности, если соответствующая национальная базовая сеть связи обслуживает десятки миллионов абонентов ( л-107). Поэтому сеть ОКС 7 России в целом следует считать сетью большой размерности. В рекомендации Q.709 [177] рассматриваются только те гипотетические сигнальные соединения, которые соответствуют международной связи. Вопрос анализа показателей качества гипотетических соединений национального уровня остается на сегодняшний день открытым и относится к компетенции региональных и национальных органов стандартизации. В данном разделе диссертационной работы числовые значения всех параметров приводятся для сетей ОКС 7 большой размерности, что, с точки зрения автора, наиболее интересно для российских исследователей и специалистов.
Пример гипотетического сигнального соединения при сигнализации «от-звена-к-звену» для междугородной связи на ЕСЭ России приведен на рис. 1.1. Рассматриваемое соединение обслуживает вызовы абонентов двух автоматических телефонных станций (АТС), например, абонентов городской телефонной сети (ГТС) с узлообразованием. Поэтому возможный (гипотетический) путь установления соединения по базовой сети проходит от АТС на узел исходящей и входящей связи (УИВС) и далее на АМТС соответствующей зоны нумерации. На междугороднем участке соединение может быть установлено через два УАК и далее в порядке, обратном вышеизложенному способу, то есть от АМТС зоны к УИВС и к АТС вызываемого абонента.
На рис. 1.1 показан путь установления соединения по базовой сети, а также все сигнальные отношения (signaling relation) и структурные элементы гипотетического соединения сигнализации. Число STP на каждом сигнальном маршруте выбрано «наихудшим» с точки зрения возможности маршрутизации сигнальных сообщений сетей ОКС 7 каждого уровня иерархии (одна сеть ОКС 7 федерального уровня иерархии и две сети ОКС 7 регионального уровня иерархии), поскольку МСЭ-Т рекомендует строить гипотетические соединения наибольшей «длины» для путей последнего выбора вторичной сети. В данном примере выбраны данные, характерные для ЕСЭ России, т.е. число SP (Nsp) на гипотетическом соединении равно 10, а число STP (NSTP) равно 8. Числовые значения параметров NSP 0 и NSTP 0 в данном случае являются., показателями качества функционирования национальной сети ОКС 7 России и подлежат стандартизации в руководящих документах отрасли. Вопрос анализа показателей качества гипотетических соединений сигнализации на ЕСЭ России подлежит дальнейшему исследованию, а разработку соответствующих нормативных документов следует отнести к важнейшим вопросам построения национальной сети ОКС 7. (АТС) (УИВС) (АМТС) (УАК) (УАК) (АМТС) (УИВС) (АТС) значениям, специфицированных для данного случая в рекомендациях Е.721 и Е.723 [198, 199], т.е. в случае соединений при междугородной связи (таблица 1.1). В этих рекомендациях указано на то, что требования к соединениям на национальных сетях связи подлежат дальнейшим исследованиям, т.е. требования МСЭ-Т в этом случае не являются чрезмерно жесткими. Тем не менее, следует, по крайней мере, принимать во внимание эти требования и исследовать вопросы, связанные с особенностями построения национальной сети. Например, как говорилось выше, особенностью сети ОКС 7 России является наличие шлюза на АМТС зоны между сетями сигнализации федерального (NI=10bin) и регионального уровней иерархии (N1=1 ІЬІП)- ДЛЯ соединений со шлюзовыми пунктами сигнализации такого типа в рекомендациях МСЭ-Т по ОКС 7 какие-либо требования отсутствуют.
На рис. 1.2 показан пример гипотетического соединения при сигнализации «из-конца-в-конец» между двумя оконечными пунктами сигнализации. В этом примере соединение устанавливается для осуществления запроса по сети ОКС 7 из оконечного пункта SEP! в базу данных оконечного пункта SEP2. Запрос осуществляется с использованием транзакционных возможностей ОКС 7 для получения дополнительной информации о маршрутизации вызова. Поскольку SEP і и SEP2 могут находиться в разных сетях ОКС 7 (например, в сетях ОКС 7 разных операторов и разных уровней иерархии), то в установлении такого соединения могут быть задействованы несколько пунктов сигнализации с обработкой сигнальных сообщений в подсистеме SCCP (пункты SPR). Напомним, что на рис. 1.2 пункты SPR изображены перечеркнутыми квадратами. Сигнальные маршруты между оконечными пунктами и пунктами SPR используют транзитные пункты STP.
Метод оценки среднего значения маршрутной задержки
Характеристики задержек сигнальных сообщений на маршрутах сети ОКС 7 относятся к интегральным показателям качества подсистемы МТР. Далее для краткости изложения будем также использовать термин маршрутная задержка, понимая под ним СВ Т0, определенную в разделе 1.3 диссертационной работы (см. рис. 1.5). В настоящее время отсутствуют методы анализа маршрутных задержек, которые дают возможность получить их характеристики в аналитическом виде или, по крайней мере, рассчитать эти характеристики с помощью эффективных вычислительных алгоритмов. В отсутствие аналитических и численных методов может быть использован метод имитационного моделирования. который автор не стал бы рекомендовать для применения при планировании сети ОКС 7 ввиду больших временных затрат и размерности решаемой задачи. В данном разделе диссертационной работы предлагается простой инженерный способ оценки среднего значения СВ Т0, с помощью которого проектировщик может осуществить анализ маршрутных задержек, не прибегая к сложным имитационным и аналитическим методам. Рассматриваемый ниже метод основан на результатах работ [17, 48, 88, 100, 150, 273], где решалась задача оценки среднего времени установления соединения в ЦСИС и в ИСС. В [100] полученные результаты численного анализа сравнивались с результатами работы [138], где та же характеристика была получена с помощью специально разработанных методов и средств имитационного моделирования. Сравнение двух методов дало положительный в целом результат, и поэтому метод был рекомендован для применения в упрощенных инженерных расчетах. В данном разделе метод оценки маршрутных задержек уточняется, приводится к принятым в рекомендациях МСЭ-Т обозначениям и позволяет с единых позиций использовать результаты предыдущих разделов данной главы.
Заметим, что в формуле (2.38) величина 7 Д/) может быть рассчитана для /-го ЗС рассматриваемого маршрута с помощью алгоритма, полученного в следующем разделе данной главы. Значение величины Тр (і) определяется в зависимости от типа физической среды, расстояния передачи и других характеристик уровня МТР1 в соответствии с методом раздела 2.3 рекомендации Q.706. Остается определить способ для оценки значений величин Г;" и Т$. Для этого можно воспользоваться данными таблиц 1.10 и 1.17 из предыдущей главы диссертационной работы. Отметим, что этими данными можно пользоваться в случае, если сеть ОКС 7 построена в соответствии с требованиями рекомендаций МСЭ-Т.
При вычислении оценки среднего значения маршрутной задержки по формуле (2.38) некоторые сложности могут возникнуть только при расчетах характеристик СВ Tod. Поэтому в следующем разделе приведены исчерпывающие примеры численного анализа этой характеристики, а примеры расчетов характеристик маршрутных задержек оставляем заинтересованному читателю.
В современных условиях ЗС обслуживает сигнальный трафик. который представляет собой случайный поток ЗнСЕ различной длины от 10 до 279 байт. Поэтому длина L (байт) ЗнСЕ, поступающей на передачу в канал, является случайной величиной, распределение которой зависит от многих факторов и фактически не поддается точному аналитическому описанию. Если распределение дискретной СВ L известно (см. раздел 1.4 диссертационной работы), то для расчетов применимы точные методы, полученные в [27, 88, 169]. В противном случае (распределение СВ L не известно) МСЭ-Т рекомендует рассматривать три основные модели сигнального трафика, для которых достаточно знать лишь среднее значение П1 данной случайной величины.
Модель 1. Поток ЗнСЕ, время передачи которых имеет детерминированное распределение. Модель 2. Поток ЗнСЕ, время передачи которых имеет экспоненциальное распределение. Модель 3. Суперпозиция потока ЗнСЕ с детерминированным временем передачи и потока ЗнСЕ с экспоненциальным временем передачи.
Модель 1 применяется при расчете задержек, когда средняя длина ЗнСЕ близка к максимально допустимой (Z) 279 байт). Модель 2 применяется, когда средняя длина ЗнСЕ относительно невелика (D 50 байт). Модель 3 используется, когда сигнальный трафик включает как «длинные», так и «короткие» ЗнСЕ (L(l) « 140 байт).
Метод построения плана маршрутизации по коду пункта назначения
Будем считать, что в качестве исходных данных для расчета ПМ имеем структуру сети ОКС 7 и значения нагрузок на сигнальные отношения. Структура сети ОКС 7 включает в себя пункты сигнализации (SP), транзитные пункты сигнализации (STP) и пучки ЗС, которые связывают между собой узлы сети в соответствии с заданной топологией. Пример структуры сети ОКС 7, который будет использоваться в данной главе, приведен на рис. 3.3. В этой и следующей главах будем рассматривать общую нагрузку на сигнальное отношение между двумя SP. То есть для каждой пары SPj и SPj будем считать заданной сигнальную нагрузку подсистем ISUP и SCCP, подлежащую передаче по сети ОКС 7 как в прямом (от SPj в SPj), так и в обратном (от SPj в SPj) направлении.
Пример структуры сети ОКС 7 Обозначим G = (V,%} неориентированный граф сети ОКС 7. множество V вершин которого соответствует множеству пунктов сигнализации всех типов, а множество $ его дуг - множеству пучков звеньев сигнализации сети ОКС 7. Напомним, что рассматривается сеть ОКС 7 с двумя типами пунктов сигнализации - оконечных пунктов сигнализации (SP-источники и SP-адресаты) и транзитных пунктов сигнализации (STP). Тогда множество Y представимо в виде Т=У{{}Уг, где Т} - множество вершин, соответствующих узлам типа SP, а Жг - множество вершин, соответствующих узлам типа STP.
Для рассматриваемой в примере этой главы сети ОКС 7 (см. рис. 3.3) неориентированный граф G = (Y, e) имеет вид, показанный на рис. 3.4. В этом случае / = {v,,v2,v3,v4} и У2 ={v5,v6,v7,v8}. Маршрутизация в сети ОКС 7 осуществляется только между узлами. находящимися в сигнальном отношении, причем это отношение является обязательно двусторонним и может иметь место только для оконечных пунктов сигнализации (SP). Это означает, что для любой пары SP (например, SP и SP4, показанных на рис. 3.3) в сети ОКС 7 должны быть созданы два пучка сигнальных маршрутов - в прямом (от S?\ к SP4) и обратном (от SP4 к SPi) направлениях.
Введем множество 91 сигнальных отношений сети ОКС 7 такое, что 9l zVxxV{, а в рассматриваемом примере будем считать, что & = \\yl,vjy.vi,Vj eY i j\. В силу того, что любые сигнальные отношения являются двусторонними, из условия (u,v)e9l следует, что {у,и)е91. Обозначим l(u,v) = {u,xv...,x,,v} маршрут из вершины и в вершину v и L(u,v) = t число промежуточных вершин маршрута. Введем i(w,v) множество всех маршрутов (пучок маршрутов), которые начинаются в вершине и и заканчиваются в вершине v графа G. Заметим, что для любой пары вершин (И,У)Є#? граф G должен содержать два пучка маршрутов $(u,v) и &(v,u). Определим множество $.= U #(M,V), (3.1) (И,У)Є5? соответствующее множеству всех маршрутов в рассматриваемой сети, которые требуется построить, исходя из правил маршрутизации, сформулированных в разделе 3.1. Из этих правил вытекают ограничения на построение маршрутов на графе G, и, исходя из этих ограничений, строятся ориентированные графы, содержащие пучки маршрутов между парами вершин из множества 91.
Для каждой пары вершин (М,У)Є,5? на графе G должны быть построены маршруты, такие, что: (і) число промежуточных вершин любого маршрута ограничено, причем 0 L(u,v) Т; (ii) любой маршрут является простой цепью графа G, причем его промежуточные вершины, если такие найдутся, лежат в множестве л(/\.
Заметим, что требования стандартов [174] допускают наличие циклов единичной длины в плане маршрутизации сети ОКС 7. Поэтому ограничение (ii) может быть ослаблено. Введем множества («.VJG V,] (3.2) и (v,)=U (" 0. (3.3) Множество Ух содержит вершины графа G, соответствующие тем узлам сети, которые находятся в сигнальном отношении с узлом. соответствующим вершине v(. Тогда &{у,) является множеством всех маршрутов графа G с окончанием в вершине v,, и поскольку множество с представимо в виде #=U (vi). (3-4) то справедлива следующая лемма. Лемма 3.1. Если все маршруты множеств #(v,) удовлетворяют ограничениям (і) и (ii) для всех v,- є Yx , тогда все маршруты множества ( удовлетворяют ограничениям (і) и (ii). Из последнего утверждения и формулы (3.4) вытекает важное следствие.
Замечания к решению задачи о максимальном потоке на графе сети сигнализации
Исследование сети сигнализации с точки зрения теории графов естественным путем приводит к задаче о максимальном потоке известной задаче оптимизации [161]. Однако принципы планирования и функционирования сети сигнализации вынуждают несколько изменить классическую формулировку задачи [64]. Прежде всего, необходимо уточнить понятие потока. Под потоком будем понимать суммарную сигнальную нагрузку между всеми парами оконечных узлов сети. находящихся в сигнальном отношении. Увеличение потока ограничено пропускными способностями пучков звеньев сети. Кроме того, при вычислении доли потока, передаваемого по пучкам звеньев, необходимо учитывать заранее определенную (статическую) маршрутизацию, а также принцип равномерного разделения нагрузки между пучками звеньев. исходящими из одного узла.
Таким образом, задача состоит в нахождении максимального потока в сети и в определении значений сигнальных нагрузок, при которых этот поток достигается, с соблюдением перечисленных ограничений. Далее в данном разделе диссертационной работы задача сформулирована в терминах теории графов для случая нормального функционирования сети, т.е. учитываются только маршруты первого приоритета - основные маршруты. Для ее решения используется симплекс-метод [60]. Решение задачи состоит из трех этапов. На первом этапе для каждого пункта назначения строится орграф, содержащий все пучки маршрутов из пунктов сигнализации, которые находятся в сигнальном отношении с данным узлом-адресатом, а затем строится его подграф, содержащий только основные маршруты (см. раздел 3.2 диссертационной работы). На втором этапе для каждого пучка ЗС рассчитывается величина передаваемой по нему сигнальной нагрузки (см. раздел 3.3 данной диссертационной работы). На третьем этапе формулируется и решается соответствующая задача оптимизации. Ниже предложен метод решения поставленной задачи и показано применение полученных результатов к анализу потоков в сети сигнализации.
Построим взвешенный граф S = (G,w), где действительная положительная функция w(-,-), определенная на множестве ребер графа G сети сигнализации, соответствует пропускной способности пучков ЗС этой сети. Определим величину F= f(u,v) и сформулируем задачу (u,v)e# о максимальном потоке на графе сети сигнализации в следующем виде {0«t (x,y) w(x,y), (х,у)є%, [F- max.
Будем считать, что для всех пар (u,v)e$l заданы начальные потоки f0(u,v), т.е. для соответствующих пар оконечных узлов сети определена начальная нагрузка на сигнальное отношение между ними. Тогда величины Ф0(х,у), вычисленные по формулам (3.16) - (3.18), являются начальными потоками по ребрам (х,у) є $ . Определим приращения потоков Af(u,v) и АФ(х,у) такие, что 0 Af(u,v) = f(u,V)-f0{u,v), (w,v)e&, 0 АФ(х,у) = Ф(х,у)-Ф0(х,у), (х,у)є%. Введем величину приращения потока AF = Af{u,v) и тогда задача (U,V)SJ? (4.1) может быть сформулирована в виде \Ъ АФ{х,у) ч,(х,у)-Фй{х,у\ (х,у)е%, (4.2) [AF- max.
Решение задачи (4.2) даёт приращения потоков f(u,v), причем увеличение начальных потоков /0(w,v) на найденные значения Af(u,v) сохраняет допустимость этих потоков, и их дальнейшее увеличение невозможно. Заметим, что задача (4.2) может быть записана в виде 0 k{u,v,x,yW(u,v) w(x,y)-0o(x,y),(x,y)e%, (u,v)e3! (4.3) AF —» max, где 0 k(u,v,x,y) \ - Для приращения потока Af(u,v), текущего по ребру (х,у).
Задача (4.3) является общей задачей линейного программирования и может быть решена симплекс-методом. Количество переменных в задаче (4.3) равно мощности множества 01, а количество неравенств -мощности множества Ш дуг графа сети сигнализации. Для реальных сетей имеет место соотношение Ш , и поэтому задача в общем случае имеет множество решений. На практике из этого множества могут быть выбрано одно или несколько решений, которые представляют определенную ценность на этапе планирования сети и позволяют проектировщику сделать оценку производительности устанавливаемого на сеть оборудования.
В некоторых случаях дополнительные ограничения на потоки в сети, обоснованные с точки зрения практики, позволяют найти единственное решение задачи. Например, будем считать, что потоки в сети увеличиваются пропорционально начальным потокам с одним и тем же коэффициентом пропорциональности а 0, который определяется по формуле а= w( ) (4 4) {u,v)etf
Нетрудно убедиться, что в этом случае максимальный поток и значения потоков f(u,v) вычисляются по формулам F = a X f0(u,v), (4.5) (u,v)e- ? f(u,v) = af0(u,v), (u,v)e& . (4.6)
Значение максимального потока, найденного по формуле (4.5), вообще говоря, меньше значения максимального потока, найденного в результате решения системы (4.1) без дополнительных ограничений. Преимущество подхода с использованием формулы (4.4) состоит в единственности решения задачи и простоте качественного анализа реальных сетей.
