Введение к работе
Актуальность работы. Необходимость ускорения научно-технического прогресса в области телекоммуникаций, возрастающая роль и глобальный характер процессов информатизации общества обуславливают опережающее развитие теории и инструментальных средств планирования, проектирования и управления структурой телекоммуникационных сетей (ТС), представляемой территориально разнесенным набором средств доступа, мультиплексирования, концентрации, коммутации, шлюзования, управления, а также каналов связи.
Непрерывное совершенствование сетевых технологий, стадийность жизненного цикла ТС, многообразие вариантов построения структуры, необходимость согласования противоречивых интересов администраций ТС и ее пользователей порождают многобразие структурно-сетевых задач (ССЗ), связанных с выбором физической и протокольной структур ТС, управлением ресурсами ТС и ее конфигурацией, обоснованием этапности развития и оптимальных перидов замени оборудования, формированием требований по производительности, надежности и стоимости к перспективной технике связи.
Базовое ядро ССЗ в предметной области ТС составляет задача ; оптимизации структуры (ЗОС) ТС, включающая частные задачи синтеза топологической структуры (СТС) сети, дискретного выбора пропускных способностей (ВПС) оборудования, распределения потоков (РП) нагрузки, оценки стоимостных показателей ТС и вероятностно-временных характеристик (ВВХ) процесса доставки информации.
Применение накопленного арсенала эвристических, субоптимальных и динамических методов оптимизации структуры сетей связи, в создание которых значительный вклад внесли В.А.Богатырев, Ю.ПЗайченко, М. Герла, Л. Клейнрок, Н.А. Князева, В.Г. Лазарев, К.Мараяма, В.К. Попков, СИ. Самойленко, Г.Ф. Янбых и др., для решения прикладных ССЗ ограничивается из-за узкой специализации этих методов в части протокольных и топологических структур, а также известного предела Nmax размерности ЗОС, который в общем случае для графо-матричных моделей не превышает нескольких десятков вершин.
Практика планирования, проектирования, управления (элементами, службами, сетью и бизнесом), а также сопровождения работ по инсталляции аппаратного и сетевого программного обеспечения ТС остро нуждается в методах решения ССЗ, не ограниченных масштабами сетей, рассматривающих структуру ТС во взаимосвязи с процессами функционирования, администрирования и обслуживания, учитывающих устойчивую тенденцию сетей связи на интеграцию, легко адаптируемых
под различные проектные и управленческие ситуации и пригодных как для детальной проработки проекта ТС, так и получения "экспресс-оценок".
Однако этому препятствуют нерешенные проблемы методологического, модельного и вычислительного характера, в частности малоизученность ТС с мультисервисным пакетизированным трафиком, сводимость NP-полной по своей природе ЗОС ТС к задаче с полиномиальной трудоемкостью, сложность выбора стартовой точки оптимизации и т.д. Положение дел усугубляется неопределенностью предпроектной ситуации, трудоемкостью подготовки больших массивов данных для графо-матричных моделей, дефицитом информации о программных реализациях известных методов решения ЗОС, их значительным недоиспользованием и большими затратами по перенастройке под новые применения, что отрицательно сказывается на стоимости, качестве и продолжительности разработки проектов ТС и принятии структурно-сетевых решений.
Ресурсосберегающий, создающий источник дополнительных инвестиций характер ЗОС, потенциально широкая, охватывающая системы планирования, проектирования и сетевого менеджмента область применения моделей и методов оптимизации структуры ТС подчеркивают необходимость обобщения и развития имеющихся результатов в области теории оптимизации структуры ТС и важность выделенных проблем в плане развития экономики страны.
Цель и задачи работы. Целью диссертации является развитие научных основ и разработка конструктивного метода оптимизации структуры ТС с асинхронным режимом с очередями, предназначенного для решения с системных позиций широкого класса прикладных структурно-сетевых задач, различающихся числом учитываемых факторов и размерностью, составом системы ограничений и критериями. Цель работы определила необходимость решения следующих задач:
систематизация основных прикладных ССЗ для обеспечения применимости информационно-математического обеспечения систем планирования, проектирования и управления ТС в различных проектных и управленческих ситуациях;
освоение комплексных подходов, рассматривающих ТС во взаимосвязи процессов функционирования, администрирования и технического обслуживания, структуру сети с учетом подсети абонентского доступа, показатели качества обслуживания пользователей ТС, как функции структурных параметров, вероятностно-временных характеристик и технико-экономических показателей;
разработка эффективно разрешимых в условиях большой размерности математических моделей физической и протокольной структур ТС, базирующихся на новых сетевых пакетных технологиях совместной передачи разнородного трафика;
изыскание путей снижения вычислительной сложности ЗОС и разработка методов решения ССЗ, различающихся степенью детализации проекта, числом учитываемых факторов и размерностью моделей, составом системы ограничений и критериями;
разработка эффективных способов задания стартовой точки оптимизации (допустимого начального плана распределения потоков, начальной структуры и т.п.), существенно снижающих трудозатраты по поиску оптимума и суммарную стоимость проектирования.
Объектом исследования является физическая структура телекоммуникационных сетей с асшгхронным режимом с очередями. Типы рассматриваемых ТС - территориальные, региональные и локальные, топологических структур - распределенные и многоуровневые. Основным протокольным объектом исследования является сетевой уровень ЭМ ВОС со свойственными ему подуровнями и функциями.
Предметом исследования являются теоретические и практические вопросы создания аналитико-алгоритмических моделей структуры ТС, разработка численных методов оптимизации структуры ТС и применение разработанных моделей и методов для решения различных структурно-сетевых задач.
Методы исследования. В процессе исследований использованы методы общей теории систем и исследования операций, теории массового обслуживания, теории телетрафика, теории графов, теории математического программирования и т.д.
Научная новизна диссертации состоит в решении научной проблемы, имеющей важное народнохозяйственное значение в области сетевого менеджмента, планирования сетевых ресурсов, сопровождения работ по инсталляции телекоммуникационных средств и заключающейся в развитии теории оптимального проектирования ТС и разработке конструктивного метода оптимизации структуры телекоммуникационных сетей с асинхронным режимом с очередями на основе:
постановки семейства структурно-сетевых задач, обобщающего отдельные модификации "классической" ЗОС и обеспечивающего многоплановость практического применения методов ее решения;
двухэтапной оптимизации, для которой традиционные проблемы "декомпозируемости", "размерности" и выбора начальных приближений по числу вершин графо-матричной модели решаются введением компактной, многофакторной, аналитической модели 1-го этапа (макро-
модели физической структуры ТС), охватывающей все, включая абонентский и магистральный, уровни топологической структуры, а также три (канальный, сетевой и транспортный) уровня протокольной структуры ТС;
инвариантного к числу оконечных пунктов, типам топологической и протокольной структур ТС метода решения ССЗ на макромодели, предполагающего использование критерия прибыли в качестве одного из альтернативных вариантов и основанного на исключении ограничений по методу штрафных функций, упрощающих оптимизацию в недопустимой области и снимающих проблему поиска начального реализуемого потока и стартовой структуры;
комбинированных, учитывающих многомерные входящие потоки и специфику совместной передачи разнородного трафика моделей протокольной структуры коммуникационной (транспортной) подсистемы ТС, обобщающих модели отдельных неинтегрированных сетей связи в направлении ISDN и использующих аналитические соотношения для расчета ВВХ отдельных виртуальных каналов, а основанные на непрерывных аппроксимациях ВВХ алгоритмы совместной оптимизации маршрутизации и ограничения нагрузки - для оптимизации канальных потоков и сетевых ВВХ.
Основные новые результаты, полученные в работе и выносимые на защиту.
-
Макромодель телекоммуникационных сетей с асинхронным режимом с очередями, представляющая собой взаимоувязанный комплекс частных моделей топологии и географии сети, информационного тяготения, процессов доставки информации и технического обслуживания, распределения смешанных и приоритетных потоков.
-
Метод решения структурно-сетевых задач (оптимизация физической структуры, декомпозиция сетевых требований, обоснование периодов замены оборудования и т.д.) на макромодели, основанный на применении некритичных к выбору начальной точки штрафных функций и позволяющий без предварительного разбиения ТС на подсети выполнять в едином оптимизационном цикле ВПС, СТС, РП, оценку стоимостных показателей и ВВХ.
-
Семейство протокольных моделей ТС, предназначенных для расчета вероятностно-временных характеристик (среднего времени и вероятности своевременной доставки информации) звена, тракта и ТС с асинхронным режимом с очередями с учетом достоверности и качества доставки, кратковременных и системных отказов, ошибок в дискретном канале, времени декодирования и распространения сигнала,
географической протяженности и различных дисциплин обслуживания смешанного трафика.
-
Семейство алгоритмов распределения потоков и ограничения нагрузки, использующих непрерывные аппроксимации функций ВВХ и предназначенных для совместной и раздельной оптимизации на графо-матричной модели ТС статического плана РП, расчета допустимых порогов по внешнему трафику, сетевых ВВХ, канального и узлового трафика.
-
Двухэтапный метод оптимизации структуры ТС, основанный на предварительном применении макромодели и последующем уточнении решения на графо-матричной модели с помощью эвристического алгоритма замены ребер.
Практическая ценность и реализация результатов работы состоят в том, что они явились составной частью НИР по созданию САПР сетей связи, проводимых ЛНПО "Красная заря" с участием ведущих институтов Академии наук и ВУЗов, а также использовались при системном сопровождении основных НИОКР ЛНПО "Красная заря" (с 1973-го по 1991-ый год) и ГП НИИ "Масштаб" (с 1991-го года по настоящее время) в части проектирования сетей связи, планирования их развития, технико-экономического обоснования выбора принципов структурной и архитектурной организации ТС и подсистем сетевого менеджмента, подготовки технико-коммерческих предложений.
Результаты диссертационнных исследований использовались при подготовке инвестиционных проектов для Информационного банка UNIDO, бизнес-плана по программе TACIS ЕС, международного тендера, меморандума и контракта с фирмами "Eurodata GmbH", "Dornier GmbH" и др.
Разработанные в диссертации модели и методы оптимизации структуры ТС использовались в учебных процессах ЛЭИС им. проф. М.А. Бонч-Бруевича и ЛФ института повышения квалификации руководящих работников и специалистов Минпромсвязи СССР, а в настоящее время включены в учебные программы и учебно-тематические планы обучения ГУТ им. проф. М.А. Бонч-Бруевича.
Пакеты прикладных программ оптимизации структуры сетей связи удостаивались дипломов и премий на конкурсах ЛОП НТО РЭС им. А.С. Попова "На лучшие разработки и усовершенствования технических средств связи для использования в народном хозяйстве" (1980, 1984-1988), включены в информационно-математическую базу САПР сетей связи предприятий ЛНПО "Красная заря", переданы ряду оргаїшзаций (АСУЖД МПС, Черкасский КБ "Аккорд", Белгосуниверситет, ИТК АН Белоруссии и др.), зарегистрированы в РосАПО.
Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на 1 Всесоюзном научно-техническом совещании "Проблемы передачи данных в АСУ" (Киев, 1974), ХП, ХШ, XIV, XV, XVn, XVIII, XIX отраслевых и межотраслевых НТК, проводимых на базе ЛНПО "Красная заря", Ш Всесоюзном научно-техническом совещании "Развитие систем и средств передачи данных для совершенствования технической базы ОГАС" (Калуга, 1980), IV Всесоюзном симпозиуме по проблемам управления на сетях и узлах связи (Переславль-Залесский, 1980), межотраслевой НТК "Прикладные проблемы моделирования систем связи" (Ташкент, 1980), VI и IX Всесоюзных школах-семинарах по теории телетрафика (Минск, 1980; Тарту, 1986), V, VI, X, XI, ХП и ХШ Всесоюзных школах-семинарах по вычислительным сетям (Владивосток, 1980; Винница, 1981; Тбилиси, 1985; Рига, 1986; Одесса, 1987; Алма-Ата, 1988), XXXYIII Всесоюзной научной сессии, посвященной Дню Радио (Москва, 1983), Ш, IV, V, VI Всесоюзных конференциях "Вычислительные сети коммутации пакетов" (Рига,1983,1985,1987,1989), Ш Всесоюзном совещании по оптимизации на графах и сетях (Новосибирск, 1984), Всесоюзной НТК "Методы и средства решения задач в интегрированных АСУ" (Ташкент, 1984), Всесоюзной школе-семинаре по распределенным автоматизированным СМО (Кутаиси, 1987), Белорусских школах-семинарах по теории массового обслуживания (Гомель, 1986, Минск 1985, 1988, 1989, 1992, 1994), Школе-семинаре по проблемам управления на сетях и узлах связи (Чимган, 1989), Втором двустороннем советско-болгарском семинаре по проблемам передачи информации (Суздаль, 1988), НТК "Автоматизированные системы проектирования и разработки аппаратно-программных средств ИВС" (Киев, 1990), НТК молодых ученых и специалистов ЛНПО "Красная заря" (1987, 1989, 1991), конференциях МАИ (1993, 1995, 1996), Постоянно действующем семинаре по оптимизации структур сетей связи при ГУТ им. проф. М.А.Бонч-Бруевича, Постоянно действующем семинаре по системотехнике при Доме Ученых РАН и т.д.
Публикации. Результаты диссертационной работы опубликованы в 93 работах и 4 книгах, в том числе одной монографии.
Структура и объем работы. Диссертация состоит из введения, пяти разделов, заключения, списка литературы и 5 приложений. Объем диссертации 300 страниц текста, в том числе 10 стр. рисунков и таблиц, 49 стр. приложений и список литературы из 286 наименований на 30 стр.
