Содержание к диссертации
Введение
ГЛАВА 1. Анализ проблем и принципов построения сетей доступа 14
1.1. Глобальная информационная инфраструктура (Gil). Место сети доступа в GII 14
1.2. Эволюция сетей доступа 18
1.2.1. Сети доступа ТфОП 18
1.2.2. Сети доступа КТВ 24
1.3. Специфика перспективных сетей доступа в NGN 27
1.4. Технологии, используемые в сетях доступа NGN 32
1.5. Задачи диссертационной работы 37
Выводы по главе 1 39
Глава 2. Определение критериев выбора оптимальной структуры ТСД 41
2.1. Формализованное описание структуры ТСД. Характеристики и параметры компонентов сети 41
2.2. Критерии оптимальности и задача выбора структуры ТСД 47
2.3. Выбор базовой топологии ТСД 60
Выводы по главе 2 75
Глава 3. Синтез структур ТСД при заданной базовой топологии 77
3.1. Синтез односвязной структуры ТСД 77
3.2. Определение оптимального числа колец в ТСД 80
3.3. Синтез однокольцевой структуры ТСД 86
Выводы по главе 3 103
Глава 4. Разработка моделей и методов расчета ВВХ линий СД при обслуживании мультисервисного трафика 106
4.1. Разработка модели цифровой линии ТСД при передаче мультисервисного трафика 106
4.2. Модель с бесприоритетным обслуживанием мультисервисного трафика 112
4.3. Модель обслуживания мультисервисного трафика с приоритетом 126
Выводы по главе 4 132
Заключение 133
Библиографический список использованной литературы 136
Приложение 1. Листинг программ 140
Приложение 2. Акты о внедрении результатов 155
- Специфика перспективных сетей доступа в NGN
- Критерии оптимальности и задача выбора структуры ТСД
- Определение оптимального числа колец в ТСД
- Модель обслуживания мультисервисного трафика с приоритетом
Введение к работе
Актуальность исследований. Эксплуатируемые в настоящее время сети доступа (СД) создавались Операторами местных телефонных сетей как совокупности абонентских линий (АЛ), соединяющих абонентские терминалы (в основном телефонные аппараты) с кроссом автоматической телефонной станции (АТС). Эти абонентские СД предназначались преимущественно для передачи речевой информации в полосе 0.3-3.4 кГц и мало изменялись в течение 100 лет своего существования, являясь наиболее консервативной частью телефонной сети общего пользования (ТфОП).
Происходящая в настоящее время модернизация местных телекоммуникационных сетей в направлении конвергенции сетей и услуг (речь, данные, видеоинформация) и переход к сетям связи следующего поколения (Next Generation Network - NGN), радикально изменяет подходы к построению СД. От СД по-прежнему требуются высокая надежность и низкая стоимость, но уже при более широкой пропускной способности и более высоком качестве передачи сигналов. Эти требования предъявляются и к технологически новым средам распространения сигналов (оптическое волокно (ОВ) и радиоканал (WLL - Wireless Local Loop)). Это радикально изменяет принципы построения СД. С учетом того, что технологические решения, используемые в СД, активно вытесняют традиционную медную АЛ, то СД должны модернизироваться и строиться так, чтобы отвечать будущим требованиям инфокоммуникаций в течение еще нескольких циклов смены технологий в системах передачи и коммутации. Таким образом, СД должны строиться с учетом не только завтрашних, но и послезавтрашних требований.
Революционные изменения в технологиях СД сопровождаются появлением новых телекоммуникационных услуг. Распространение этих услуг меняет характер нагрузки, передаваемой по линиям СД, а применение выносных модулей (ВМ) (Remote Units) [64], новых технологий и новых сред распространения сигналов существенно влияет на выбор топологии и
параметров СД. В частности, может оказаться целесообразным расширение границ СД, переход к новым структурам и изменение качества обслуживания различных видов информации. Естественно, что при этом должна меняться количественная и качественная основа исследований СД, совокупность математических моделей и методов оценки эффективности, планирования и оптимизации СД. В связи с этим, тема диссертационной работы является, безусловно, актуальной.
Состояние исследований. Вопросы, в той или иной мере касающиеся СД рассматриваются во многих работах. В частности, в [1] рассмотрены основные вопросы планирования и проектирования местных телефонных сетей, в том числе абонентских. Представлены методы, позволяющие эффективно проектировать сети связи, а также осуществлять их оптимизацию. Работы [3], [17] посвящены методикам проектирования линейных сооружений связи. Основам технико-экономического проектирования городских телефонных сетей посвящена работа [4], в [2] исследуются вопросы выбора длины АЛ. Но все эти работы касаются, в основном, исследования СД как части традиционной ТФОП с коммутацией каналов для обслуживания речевого трафика. В работах [24], [25] исследуются принципы модернизации сетей кабельного телевидения (КХВ). В работе [8] рассмотрены принципы построения и модернизации СД для ТфОП. В работе [10] описаны новые технологии, но не рассматриваются сетевые аспекты.
Наиболее близкими к данной диссертационной работе являются работы [19], [22] и [42], посвященные методам планирования современных С Д. Данная диссертационная работа является, по сути, их продолжением, обобщением и дальнейшим развитием.
Цель и задачи исследования. Цель работы состоит в исследовании и разработке методов выбора структур СД, моделей и методов оценки ВВХ при передаче по СД разнородной нагрузки для определения необходимого
ресурса цифровых линий в условиях перехода к NGN. Поставленная цель
обусловила необходимость решения следующих основных задач:
' - анализ проблем и путей модернизации существующих СД;
определение круга задач планирования, которые требуют своего решения при построении мультисервисных СД;
развитие методов формального описания структуры сети, определение параметров, метрик и критериев оценки для сравнения между собой альтернативных вариантов компонентов и структуры СД в условиях NGN;
разработка методов и алгоритмов выбора компонентов и структуры СД;
разработка методов определения рациональной топологии СД;
разработка методов, алгоритмов и программных средств синтеза структур СД при различных сетевых топологиях по критерию минимальной стоимости;
разработка моделей и методов расчета ВВХ обслуживания нагрузки цифровых линий СД.
Методы исследования. Для достижения поставленных целей в
качестве аппарата исследования использованы методы теории графов, целочисленного линейного программирования, теории телетрафика, теории массового обслуживания, теории исследования операций и теории надежности.
Научная новизна диссертационной работы заключается в предложенных оригинальных методах и моделях, позволяющих эффективно вырабатывать предложения по модернизации или строительству новых СД, с учетом современных требований при переходе сетей связи к NGN. В процессе проведенных исследований были разработаны следующие объекты, характеризующиеся научной новизной:
- метод определения структуры СД, основанный на последовательном
решении задач выбора топологии и синтеза структуры в рамках
щ выбранной топологии;
метод определения базовой топологии построения СД, учитывающий как надежностные, так и затратные критерии;
метод минимизации затрат на линейно-кабельную инфраструктуру при построении СД на базе кольцевых топологий;
алгоритм и программа синтеза однокольцевых структур СД;
модель цифровой линии СД и метод определения ВВХ при передаче по ней мультисервисного трафика.
Практическая ценность результатов работы. Теоретические исследования, выполненные в работе, доведены до инженерных решений. Основные результаты работы внедрены ОАО «Связьинвест» и ГК «Экран» при построении мультисервисной сети абонентского доступа BroadAccess в системном проекте сети следующего поколения NGN для ОАО «Межрегиональный ТранзитТелеком» и в ряде других НИР и ОКР, выполненных при участии автора.
Представленные принципы и методы эффективного проектирования сетей доступа служат основой для создания программного обеспечения, автоматизирующего процесс проектирования. В рамках диссертации созданы программы, тексты которых содержатся в приложениях.
Апробация работы. Основные результаты докладывались на 59-й Научной сессии, посвященной Дню радио, Москва, 2004 г., а также на научно-технических конференциях профессорско-преподавательского состава, научных работников и аспирантов ГУТ им. проф. М.А. Бонч-Бруевича и опубликованы в "Трудах учебных заведений связи".
Публикации. По материалам данной диссертационной работы в научно-технических журналах и в трудах международных и всероссийских научных конференций опубликовано 9 печатных работ.
Объем и структура работы. Диссертационная работа состоит из введения, четырех глав, заключения, двух приложений и списка литературы. Объем пояснительной записки 140 страниц, 44 иллюстраций, список литературы насчитывает 80 наименований. В приложениях приведены
листинги программ, акты о внедрении результатов диссертационной работы и свидетельства о регистрации программ, разработанных автором в рамках диссертации.
Основные положения, выносимые на защиту:
двухкомпонентный критерий эффективности, включающий стоимость компонента сети при нормальных периодах функционирования и стоимость штрафа за периоды его простоя;
подход к оптимизации структуры СД, позволяющий свести многокритериальное решение к двухэтапному однокритериальному решению данной задачи;
метод выбора базовой топологии сетей доступа по усредненным или предельным значениям характеристик компонентов сети;
алгоритмы и программы синтеза сетевых структур по критерию минимальной стоимости в классе односвязных и кольцевых топологий;
обоснование оптимальности однокольцевых структур СД и порядок рационального перехода к многокольцевым структурам;
математическая модель цифровой линии мультисервисной сети доступа, представленная в виде СМО с комбинированной дисциплиной обслуживания с наличием и отсутствием приоритетов и методы получения ее ВВХ.
Содержание пояснительной записки. В первой главе кратко рассматриваются принципы построения существующих СД, их структурные характеристики, достоинства и недостатки этих сетей. В данной главе рассмотрена эволюция проблематики существующих СД, оценки возможности использования современных технологий для увеличения скорости передачи по абонентским линиям, изложены основные требования к СД в составе глобальной информационной инфраструктуры (GII). Проанализированы процессы конвергенции и перехода к NGN. Показана актуальность исследований в этом направлении. В соответствии с уже проведенными исследованиями сформулированы цель и задачи работы.
Вторая глава посвящена вопросам выбора компонентов и определению рациональной топологии транспортной сети доступа. Детально излагается способ формального описания структур сетей при помощи методов теории графов, являющихся одними из наиболее эффективных для анализа сетей связи. Использование формального описания позволяет выработать рекомендации по выбору той или иной структуры ТСД. Важным при этом является выявление критериев эффективности для сравнения между собой альтернативных вариантов компонентов сети и ее структуры и выбора наилучших из них. Стремление учесть несколько компонентов затратного критерия или одновременно затратный и надежностный критерии приводит к многокритериальным оптимизационным задачам. Обсуждается возможный подход к решению одной из таких задач, когда учитываются стоимости и надежности входящих в СД компонентов. В отличие от обычно используемого метода свертки, когда скаляризация вектора критериев достигается использованием их взвешенной суммы, причем веса критериев являются экспертными оценками, в работе формируется двухкомпонентный критерий, куда с весами в виде вероятностей соответствующих состояний входят стоимость линии при ее нормальном функционировании и стоимость штрафа за ее простой. Критерий в таком виде имеет ясную физическую трактовку и представляет собой, по существу, математическое ожидание затрат на линию, у которой периоды исправной работы (с вероятностью кт -коэффициента готовности) чередуются с периодами простоя из-за выхода линии из строя (с вероятностью Кп=1- кг). Задача оптимизации разбивается на два этапа: на первом выбирается базовая топология, на втором - вариант структуры в рамках этой топологии. Проведенный анализ показал, что в качестве базовых рекомендуются односвязные и кольцевые топологии.
Третья глава посвящена рассмотрению новых методов и алгоритмов, являющихся следующим этапом на пути оптимизации структуры СД. При этом основной задачей данного этапа является географическая трассировка каналов (ребер) сети, которая ставится как задача структурного синтеза по
минимуму двухкомпонентного затратно-надежностного критерия в классе односвязных и кольцевых структур.
Предложен метод и алгоритм синтеза оптимальных односвязных топологий и на его основе написана программа, текст которой приводится в Приложении.
Используя кольцевые топологии можно строить СД с высокой степенью надежности. Однако у проектировщика может возникнуть вопрос, о целесообразном числе колец на проектируемой С Д. Показано, что однокольцевая структура обеспечивает минимум двухкомпонентного затратно-надежностного критерия. Синтез однокольцевой структуры ТСД в такой постановке является аналогом знаменитой задачи коммивояжера (ЗК) из теории исследования операций. Были детально проанализированы известные методы решения ЗК, и предложен собственный алгоритм получения решения - метод последовательного расширения кольца.
В работе также учтено и то, что повышенные требования к показателям надежности или технические ограничения систем передач могут сделать невозможным или нецелесообразным построение СД в виде одного кольца. Предложен иной метод построения многокольцевой структуры, применение которого позволит существенно сократить затраты на реализацию СД.
В четвертой главе вводится базовая модель цифровой линии, в которой учитываются закономерности процессов поступления и обслуживания разнородных видов трафика в транспортную сеть доступа. Реализация модели разных видов трафика позволяют получить явные аналитические выражения для расчета ВВХ, отражающих качество предоставления услуг мультисервисной сетью доступа. Сравнение этих моделей позволит проектировщику оперативно реагировать на изменение трафика в этих сетях путем предоставления различных приоритетов, а также эффективно спланировать необходимую пропускную способность СД.
Специфика перспективных сетей доступа в NGN
Представлены три основные варианта подключения абонентского терминала в местную КС.
Верхняя ветвь - перспективный вариант подключения ТА без использования промежуточного кроссового оборудования. Кабель доходит от кросса до РК, где - посредством абонентской проводки - осуществляется подключение ТА.
Средняя ветвь - вариант подключения ТА по шкафной системе, когда между кроссом и РК размещается промежуточное оборудование. В данном случае - это ШР. Нижняя ветвь - организация АЛ с использованием воздушных линий связи (ВЛС). В такой ситуации на столбе устанавливается кабельный ящик (КЯ) и - обязательно - вводно-выводные изоляторы. В месте размещения РК монтируется - абонентское защитное устройство (АЗУ), предотвращающее возможное влияние опасных токов, и напряжений на ТА. Следует отметить, что организация АЛ или ее отдельных участков за счет строительства ВЛС не рекомендуется; но в ряде случаев - это единственный вариант организации абонентского доступа. Использование цифровых КС почти не изменило принципы построения СД. Это положение, как правило, связано с двумя основными причинами. Во-первых, при замене старого аналогового оборудования на цифровую КС часто не ставилась задача модернизации СД. По крайней мере, не изменялись границы пристанционного участка. Во-вторых, финансовые возможности Оператора не позволяли существенно модернизировать СД даже в тех случаях, когда необходимость такого решения была очевидна. Ориентация большинства Операторов ТфОП на поддержку традиционных услуг телефонной связи не стимулировала каких-либо существенных изменений в СД. Тем не менее, использование ресурсов ТфОП для передачи данных (ПД) через модемы выявило ряд проблем, свойственных СД. Эти проблемы касаются, в основном, структурных характеристик существующих СД для ТфОП, под которыми понимаются средние значения длин АЛ и емкости абонентских кабелей. Очевидно, что распределение длин АЛ и емкости абонентского кабеля определялось множеством факторов, из которых следует выделить: - емкость КС, для которой создавалась СД; - градостроительные принципы застройки и планировки городской или сельской местности, где устанавливалась КС; - участок абонентской сети (магистральный или распределительный), для которого оценивались данные характеристики. Представляют интерес значения структурных характеристик, полученных в [20] в результате обработки данных по реальным сетям доступа для различных регионов России: - среднее значение длины АЛ в российских городских телефонных сетей (ГТС) составляет 1280 м; - коэффициент вариации (рассеивание от среднего значения) этой величины - 0,59; - распределение длин различных участков АЛ имеет следующий характер: магистральный участок - 74,7%, распределительный участок - 20,2%, абонентская проводка - 5.1%. Эти данные хорошо корреспондируются с теми оценками, которые излагаются в работе [17]; - среднее значение емкости магистрального кабеля составило 761 пару; - коэффициент вариации этой величины равен 0,42.
Имеется много других работ, касающихся анализа характеристик эксплуатируемых абонентских сетей ТфОП. Но все эти исследования ориентировались на одну технологию - передачу речи в полосе 0.3-3.4 кГц. Конвергенция сетей связи и планы перехода к NGN изменили ситуацию.
Формальный анализ структурных характеристик СД для ТфОП в России позволяет сделать следующий вывод: более короткие АЛ позволяют сравнительно просто применять оборудование типа xDSL, равно как и другие современные технические средства. На практике дело обстоит иначе. Условия эксплуатации большинства абонентских кабелей не позволили сохранить в заданных нормах те характеристики, которые существенны с точки зрения передачи сигналов, требующих более широкой полосы пропускания по сравнению с той, что обеспечивается каналом тональной частоты. Кроме того, устройства кроссировки кабельных жил в ШР и РК вносят искажения в передаваемые сигналы, которые особо заметны за пределами полосы пропускания канала 0,3-3,4 кГц.
Непредвиденные сложности возникли у Операторов связи из-за резкого всплеска актов вандализма и хищения воздушных линий и кабелей связи.
Также сложной проблемой стал несанкционированный доступ к АЛ для проведения за счет другого абонента междугородных или международных переговоров, получения различного рода платной информации. Все эти требования и обстоятельства, инициировали поиск новых принципов построения, как АЛ, так и СД в целом, и, следовательно, подтверждают необходимость и целесообразность решения задач, поставленных в диссертационной работе.
Первые сети КТВ формировались по принципу коллективного приема сначала в метровом диапазоне волн (47...240 МГц), а затем и в дециметровом (550...862 МГц в Европе и 600...750 МГц в США). Они имели сравнительно простую схему: коллективная антенна, головная станция (ГС) и коаксиальный тракт с необходимым числом ответвителей и усилителей (магистральных и домовых). Телевизионные спутниковые и эфирные каналы, а также каналы местной студии КТВ поступают на ГС, которая выполняет их частотное мультиплексирование и направляет комбинированный широкополосный сигнал по магистральному коаксиальному кабелю к абонентам. Архитектура традиционной сети абонентского доступа для КТВ показана на рис. 1.6.
Критерии оптимальности и задача выбора структуры ТСД
Эта оценка, вероятно, сильно завышена. При весьма скромном значении iV=10 величина R равна астрономическому значению 6,7-1026.
Структуры ТСД можно классифицировать по различным признакам. Если, в частности, в качестве параметра классификации выбрать связность, то множество структур будет заключено между двумя предельными топологиями - односвязной и полносвязной.
Полносвязная сеть (h=N-l) имеет общую минимальную длину каналов Л, так как в ней все связи идут по кратчайшему пути с рангом, равным единице. В то же время такая сеть имеет максимальную общую длину ребер L, так как все узлы сети соединены между собой отдельными ребрами. При этом общая длина связей, выраженная в рангах, равна числу ребер, т.е. R=N(N-l)/2, а выраженная в километрах - общей длине ребер.
Односвязная сеть (/г=1) имеет N-1 ребро и может иметь много различных структур при значительном разбросе суммарных длин ребер. Данная топология обеспечивает наименьшую общую длину линий L, и наибольшую общую длину каналов А и рангов связей R.
В общем случае исключение какого-либо ребра из сети приводит к уменьшению общей длины ребер, увеличивает сумму рангов связей и может увеличить сумму расстояний для всех связей и общую длину каналов. Кроме того, от числа ребер на сети зависят ее стоимость и надежность. Обычно минимальная стоимость сети достигается не при h=l или h=N-l, а в случае, когда l h N-l. Во всех случаях увеличение числа ребер на сети приводит к росту ее связности и надежности. Одновременно, правда, возрастает стоимость сети.
Одним из основных вопросов, решаемых на этапе планирования СД [19], является выбор структуры и расчет необходимой для нужд различных коммутируемых сетей пропускной способности данной ТСД. Структура ТСД, определяемая числом, местоположением различных ее узлов, а также характером их взаимосвязей, определяет надежность, необходимые затраты для создания и возможности этой сети по доставке заданных объемов информации между отдельными парами узлов. Выбор оптимальной структуры ТСД можно осуществить на базе различных показателей (критериев) с учетом или без учета различных ограничивающих факторов. Используемый показатель оптимальности, число и тип ограничений определяют уровень сложности решения задач по синтезу структуры ТСД.
Проблема выбора оптимальной структуры ТСД представляет собой многокритериальную задачу. Сложность решения этой задачи обусловлена наличием таких, как правило, противоречивых требований к ТСД, как низкая стоимость, высокая надежность, возможности использования существующих и перспективных систем передачи, модернизации и дальнейшего развития сети и др. Практически из множества показателей можно выделить два критерия: затратный и надежностный. Принципиально это не меняет характера задачи - она остается многокритериальной и должна решаться методами векторной оптимизации [60]. Однако, для двухкритериальных задач существенно упрощается построение множества эффективных решений, т.е. множества Парето [61]. Выбор одного из парето-оптимальных решений из этого множества должен осуществляться на основе использования того или иного принципа компромисса.
Необходимо отметить, что случаев практического применения Парето-подхода при проектировании систем связи крайне мало. Обычно при проектировании выбирают один из критериев, который представляется проектировщику наиболее важным при оптимизации, а остальные критерии переводятся в разряд ограничений. Чаще всего при проектировании ТСД производится оптимизация по затратному критерию, а показатели надежности используются в качестве ограничений. Для синтеза оптимальной структуры ТСД должны быть заданы: множество узлов A={ai], i=l,2,...N. Размещение узлов на сети задается указанием их координат или матрицей расстояний L=/y, zj=l,2,...iV; допустимые трассы строительства линий между узлами ТСД в виде матрицы допустимых ребер 2?=&у, i,j=l,2,...N; Щ=1, если по данной трассе допускается строительство линии и Ьу=0 - в противном случае; матрица весовых коэффициентов ребер 3=/?у. Величина общесетевых затрат на построение ТСД может определяться из выражения [2], [67]: ще 3А и 3L - суммарные затраты на создание соответственно узлов и линий сети абонентского доступа; pi, ру - весовые коэффициенты, характеризующие соответственно затраты на создание узла at и ребра Ьу; В єВ - множества ребер из матрицы Z?=&y[, которые могут быть включены в сеть в процессе синтеза ее структуры. Если считать, что при заданном числе узлов N суммарные затраты на создание узлов 3А не зависят от элементов матрицы В, то минимизация суммарных затрат на построение линии 3L обеспечивает минимум общесетевых затрат 3, т.е. 3L является целевой функцией при экономически оптимальном синтезе структуры сети абонентского доступа. Поэтому синтез оптимальной структуры ТСД сводится к выбору такого подмножества (В ) из множества допустимых ребер (В), включение которых в сеть требует наименьших затрат на построение и обеспечивает надежность сети не менее заданной, т.е. в этом случае затраты являются показателем оптимальности, а надежность сети ограничивающим фактором. Может применяться подход, когда в качестве показателя оптимальности используется надежность сети, а в качестве ограничивающего фактора - затраты на создание сети, т.е. синтезируется структура ТСД, обеспечивающая максимальную надежность сети при заданной величине затрат. Используя в качестве весового коэффициента рц такой параметр ребра, как его длину (/у), в результате можно получить сеть с наименьшей общей длиной ребер между узлами ТСД. Эти величины могут быть известны априорно или же могут быть вычислены по известному расположению щ (координатам) узлов. Нужно также отметить, что реальные (фактические) расстояния между узлами ТСД в некоторых случаях могут отличаться (как правило, в большую сторону) от расстояний, измеренных по прямой. Данный факт можно учесть введением коэффициента удлинения (зависящего от градостроительных принципов и типа планировки улиц), что предложено в работах [1], [19].
Определение оптимального числа колец в ТСД
Основой выработки рекомендаций по выбору той или иной структуры ТСД является формальное описание сети. Целесообразно использовать для этого методы теории графов, являющиеся одними из наиболее эффективных для анализа сетей связи. Важным при этом является выявление критериев оценки для сравнения между собой альтернативных вариантов компонентов сети доступа и ее структуры и выбора наилучших из них.
Основными являются затратный и надежностный критерии, а также их компоненты. Стремление учесть несколько компонентов затратного критерия или одновременно затратный и надежностный критерии приводит к многокритериальным оптимизационным задачам. В отличие от обычно используемого метода свертки, когда скаляризация вектора критериев достигается использованием их взвешенной суммы, причем веса критериев являются экспертными оценками, в работе формируется двухкомпонентный критерий, куда с весами в виде вероятностей соответствующих состояний входят стоимость компонента при его нормальном функционировании и стоимость штрафа за его простой. Критерий в таком виде имеет ясную физическую трактовку и представляет собой, по существу, математическое ожидание затрат на компонент, у которого периоды исправной работы (с вероятностью кТ - коэффициента готовности) чередуются с периодами простоя из-за выхода компонента из строя (с вероятностью кп =1-кг).
Введенный критерий ("стоимость-надежность") является аддитивным и может быть использован, вследствие этого, для сравнения между собой не только компонентов, но и различных структур сети в целом. В то же время для отдельных компонентов критерий является недостаточно эффективным, не обеспечивает должной уверенности в результате, поскольку математические ожидания реализуются с недостаточно высокими вероятностями. В связи с этим предлагается и (на основании строгого вероятностного подхода) выводится выражение для гарантированной (с вероятностью, не меньшей 0,98) "стоимости-надежности" компонента. Этот критерий не является аддитивным, поэтому его рекомендуется использовать только для локальных исследований сети.
Задачу оптимизации сети ввиду ее существенной сложности целесообразно декомпозировать на два этапа: на первом по усредненным или предельным значениям характеристик компонентов выбирается базовая топология, на втором - вариант структуры в рамах этой топологии с использованием конкретных значений параметров компонентов.
Задачу выбора базовой топологии также целесообразно решать в два этапа. На первом минимизируется связность сети при выполнении заданного ограничения на надежность; на втором - минимизируется стоимостной показатель, вычисляемый с учетом надежности сети. При конструировании показателя использован тот же подход, что и при выводе выражения для критерия "стоимость-надежность". Синтез решений двух этапов и позволяет выработать рекомендации по целесообразной базовой топологии. Как оказалось, предпочтительными являются односвязная и кольцевая базовые топологии.
Односвязная топология наиболее часто используется для построения отдельных участков сети абонентского доступа. Использование данной топологии требует наименьшего числа ребер. Поэтому реализация односвязной топологии требует минимальных затрат среди всех возможных топологий. В то же время, как известно, односвязная топология является не избыточной, т.е. выход из строя хотя бы одного ребра этой сети приводит к нарушению связности сети. Поэтому потенциальная надежность и живучесть односвязной топологии является наименьшей среди всех других топологий построения сети. И, тем не менее, вследствие низкой стоимости и простоты реализации односвязная топология является одной из базовых топологий построения ТСД. В рамках односвязной топологии реализуются различные структуры сетей доступа, такие как "линейная", "звездообразная", "узловая", "древовидная" и т.д. Примером реализации односвязной топологии построения ТСД могут являться пассивные оптические сети (PON). Кроме того, данная топология является единственной для построения распределительного участка сети доступа.
Модель обслуживания мультисервисного трафика с приоритетом
В математической постановке говорится о произвольной матрице. Сделано это потому, что имеется много прикладных задач, которые описываются основной моделью, но всем условиям (3.13)-(3.15) не удовлетворяют. Особенно часто нарушается условие (3.13) (например, если Су - не расстояние, а плата за проезд: часто в одном направлении стоимость билета одна, а в обратном - другая). Поэтому уместно различать два варианта ЗК: симметричную задачу, когда условие (3.14) выполнено, и несимметричную в противном случае. Условия (3.13) и (3.15) по умолчанию будем считать выполненными.
Второе замечание касается числа всех возможных туров. В несимметричной ЗК все туры t=(jbJ2,...,JNJi) и t =(jbJN,..-,J2,ji) имеют разную длину и должны учитываться оба. Разных туров очевидно (iV-1)!.
Зафиксируем на первом и последнем месте в циклической перестановке номер jb а оставшиеся iV-І номеров переставим всеми (iV—1)! возможными способами. В результате получим все несимметричные туры. Симметричных туров имеется в два раза меньше, поскольку t и V по длине эквивалентны в силу симметрии.
В дальнейшем, в диссертационной работе при синтезе однокольцевой структуры ТСД нас будут устраивать методы решения симметричной ЗК.
Для решения ЗК могут использоваться точные или приближенные методы дискретной оптимизации. Наиболее тривиальным точным методом является метод полного перебора всех возможных вариантов.
Чтобы проводить полный перебор в ЗК, нужно генерировать (разумеется, без повторений) все перестановки заданного числа N элементов. Это можно сделать несколькими способами, но самый распространенный (т.е. приложимый для переборных алгоритмов решения) - это перебор в лексикографическом порядке.
Пусть имеется некоторый алфавит и наборы символов алфавита (букв), называемые словами. Буквы в алфавите упорядочены: например, в русском алфавите порядок букв а х=б :я (символ с читается "предшествует)". Если задан порядок букв, можно упорядочить и слова. Скажем, дано слово u=(ubu2v.,Um) - состоящее из букв ui,u2,..,um - и слово v =(vi,V2,.-,Vb). Тогда если Uicvi, то и ucv, если же Ui=Vi, то сравнивают вторые буквы и т.д. Этот порядок слов и называется лексикографическим.
Рассмотрим, например, перестановки из пяти элементов, обозначенных цифрами 1,5. Лексикографически первой перестановкой является 1-2-3-4-5, второй - 1-2-3-5-4, ..., последней - 5-4-3-2-1. Правило следующее. Пусть дана перестановка 1-3-5-4-2. Нужно двигаться по перестановке справа налево, пока впервые не увидим число, меньшее, чем предыдущее (в примере это 3 после 5). Это число, Pj.i надо увеличить, поставив вместо него какое-то число из расположенных правее, от Pi до PN. Число большее, чем Pj_i, несомненно, найдется, так как РН РІ. Если есть несколько больших чисел, то, очевидно, надо ставить меньшее из них. Пусть это будет Pj,j i-1. Затем число Pi-i и все числа от РІ до PN, не считая Pj нужно упорядочить по возрастанию. В результате получится непосредственно следующая перестановка, в примере - 1-4-2-3-5. Потом получится 1-4-2-5-3 (тот же алгоритм, но упрощенный случай) и т.д.
Нужно понимать, что в сети с N узлами не нужны все перестановки из N элементов. Потому что перестановки, скажем, 1-3-5-4-2 и 3-5-4-2-1 " (последний элемент соединен с первым) задают один и тот же тур, считанный сперва с города 1, а потом с города 3. Поэтому нужно зафиксировать начальный город 1 и присоединять к нему все перестановки из остальных элементов. -Этот перебор даст (N-1)! разных туров, т.е. полный перебор в несимметричной ЗК (мы по-прежнему будем различать туры 1-3-5-4-2 и 1-2-4-5-3). Понятно, что полный перебор практически применим только в задачах малого размера. Отметим, что симметричная ЗК с N городами требует при полном переборе рассмотрения (N-l)!/2 туров, а факториал, как известно, растет очень быстро: Поэтому для решения ЗК при большем значении N желательно усовершенствовать перебор, введя в него интеллект. В связи с этим опишем метод ветвей и границ, применительно к оптимизации сети связи, который л реализует простую, но широко применимую и очень полезную идею. В сущности, это полный перебор решений, который оптимизируется за счет того, что при переборе вариантов по определенным признакам отсекаются неоптимальные множества перебора. Так как количество вершин от уровня к уровню возрастает в факториальной прогрессии, то отсечение вершин верхних уровней значительно сокращает общее число перебираемых вариантов. Сущность метода ветвей и границ состоит в следующем: l.Bce множество разбивается на п-1 подмножеств, каждое из которых оценивается верхней и нижней оценками. 2.Производится отсев неоптимальных множеств по следующему критерию: если нижняя оценка (решение релаксированной задачи) больше минимальной из верхних оценок (решений нерелаксированной задачи), то множество, очевидно, считается неоптимальным и отсекается, иначе остается до следующей итерации. 3.Находится множество с лучшей нижней оценкой (прогнозом) и дробится на количество равное размерности исходной матрицы минус количество уже выбранных (фиксированных для данного множества) узлов. 4.Находятся минимальная верхняя и нижняя оценка. Если они равны и достигнуты на одном и том же множестве, то это значит, что получено оптимальное решение и алгоритм заканчивает работу, иначе возврат к шагу Итак, общая идея тривиальна: нужно разделить огромное число перебираемых вариантов на классы и получить оценки (снизу - в задаче минимизации, сверху - в задаче максимизации) для этих классов, чтобы иметь возможность отбрасывать варианты не по одному, а целыми классами. Трудность состоит в том, чтобы найти такое разделение на классы (ветви) и такие оценки (границы), чтобы процедура была эффективной.
