Содержание к диссертации
Введение
1. Архитектура, характеристики и методы анализа мультисервисных сетей широкополосного доступа
1.1. Эволюция телекоммуникационных сетей региональных операторов и провайдеров 27
1.2. Архитектуры мультисервисной сети широкополосного доступа
1.2.1. Общие требования к системам телекоммуникаций 33
1.2.2. Основные компоненты архитектуры 34
1.2.3. Особенности оказания услуг для квартирного сектора 38
1.2.4. Особенности оказания услуг для корпоративных клиентов 41
1.3. Выбор технологий для построения мультисервисной сети 46
1.3.1. Подключение конечных пользователей 46
1.3.2. Транспортная сеть 57
1.4. Планирование развития мультисервисной сети. 64
1.4.1. Задача планирования 64
1.4.2. Выбор бизнес - стратегии 69
1.4.3. Моделирование и системный анализ сетей
1.5. Методы анализа распределенных информационно-вычислительных, компьютерных и телекоммуникационных систем и сетей 78
1.6. Выводы 87
2. Описание компонентов мультисервисной сети в терминах теорий массового обслуживания и множеств 90
2.1. Формирование потоков в мультисервисных сетях 90
2.2. Описание узлов сети как систем массового обслуживания
2.2.1. Узел с одним классом обслуживания 94
2.2.2. Узел с несколькими классами обслуживания з
2.3. Примеры описания фрагментов телекоммуникационных сетей как сетей массового обслуживания 99
2.4. Описание типовых топологий транспортных магистралей в терминах теории множеств 105
2.5. Выводы 119
3. Метод анализа сетей с пакетной коммутацией при использовании адресной рассылки пакетов, основанный на использовании аппарата конечных дискретных цепей маркова 120
3.1. Вводные замечания 120
3.2. Общий подход к расчету элементов матрицы переходных вероятностей
3.2.1. План распределения информации 122
3.2.2. Вектор и таблица вероятностей состояний узла 128
3.2.3. Таблица условных вероятностей выбора направлений, получение полных вероятностей выбора направлений 131
3.2.4. Примеры расчета элементов МПВ
3.3. Вывод соотношений для расчета элементов матриц переходных вероятностей при использовании стохастических маршрутных таблиц138
3.4. Вывод соотношений для расчета элементов матриц переходных вероятностей при использовании простых маршрутных таблиц
3.4.1. Простые маршрутные таблицы 141
3.4.2. Заполнение таблицы условных вероятностей 142
3.5. Описание процесса передачи одиночного пакета по сети,
находящейся в стационарном режиме при помощи аппарата КДЦМ... 146
3.5.1. Матрица переходных вероятностей и ее представление в каноническом виде 146
3.5.2. Фундаментальная матрица 151
3.5.3. Определение вероятности успешной доставки пакетов 152
3.5.4. Модифицированная фундаментальная матрица 153
3.5.5. Определение вероятности возвращения пакета в исходный узел
3.6. Соотношения для определения времени доставки пакетов 155
3.7. Особенности расчета показателей качества обслуживания между каждой парой узлов и среднесетевых характеристик 157
3.8. Математическая модель для расчета показателей качества обслуживания при использовании одного класса обслуживания 160
3.8.1. Потоки на ветвях и узлах сети 160
3.8.2. Оценка требований к производительности узлов коммутации 162
3.8.3. Система уравнений для определения потоков на ветвях в стационарном режиме 164
3.8.4. Пример составления системы 171
3.8.5. Алгоритмы решения системы и расчета вероятностно-временных характеристик сетей 1 3.9. Математическая модель для расчета показателей качества обслуживания при использовании нескольких классов обслуживания 181
3.10. Выводы 190
4. Метод расчета характеристик сетей с пакетной коммутацией при использовании широковещательного режима рассылки пакетов 191
4.1. Вводные замечания 191
4.2. Широковещательная рассылка пакетов на сетях с кольцевой топологией
4.2.1. Соотношения для расчета характеристик сети при адресной пересылке пакета 192
4.2.2. Соотношения для расчета задержек и вероятностей доставки пакетов в широковещательном режиме 196
4.2.3. Соотношения для расчета нагрузки на ветви сети 200
4.2.4. Алгоритм расчета характеристик при передаче пакетов в широковещательном режиме относительно заданного узла 204
4.2.5. Система уравнений для расчета характеристик сети при использовании широковещательной рассылки 207
4.2.6. Алгоритм расчета решения системы и расчета характеристик между каждой парой узлов 209
4.3. Широковещательная рассылка пакетов на сетях с
топологиями, не содержащих петель 211
4.3.1. Некоторые особенности построения сетей на базе коммутаторов Ethernet второго уровня 211
4.3.2. Описание процесса рассылки пакетов в широковещательном режиме в терминах теории множеств 213
4.3.3. Алгоритм расчета характеристик относительно исходного узла при передаче пакетов в широковещательном режиме 217
4.3.4. Система уравнений для расчета характеристик сети при широковещательной рассылке пакетов 219
4.4. Выводы 221
5. Метод расчета характеристик сетей при использовании для рассылки пакетов направленнойволны 222
5.1. Использование направленной волны для рассылки пакетов 222
5.2. Соотношения для определения вероятности успешной передачи пакетов между заданной парой узлов 228
5.3. Соотношения для расчета времени доставки пакетов между заданной парой узлов 231
5.4. Расчет потоков на ветвях и узлах сети 233
5.5. Описание процесса пересылки пакета по сети при помощи направленной волны в терминах теории множеств 234
5.6. Алгоритм расчета характеристик относительно исходного узла при передаче пакетов методом направленной волны 238
5.7. Система уравнений для расчета характеристик сети 240
5.8. Выводы 243
6. Расчет характеристик и исследование свойств магистралей транспортных сетей при использовании нескольких классов обслуживания 244
6.1. Вводные замечания 244
6.2. Входные данные и результаты расчета 244
6.3. Топология магистрали - кольцевая 246
6.3.1. Передача по кольцевой магистрали ассиметричного
трафика 246
6.3.2. Накопление задержек при передаче пакета по магистрали сети с кольцевой топологией 256
6.3.3. Исследование влияния места отказа каналов 261
6.3.4. Исследование влияния изменения нагрузки и пропускных способностей каналов 269
6.4. Топология магистрали — квадратная ячейка 281
6.4.1. Исследование влияния изменения нагрузки и увеличения пропускных способностей наиболее загруженных ветвей 281
6.4.2. Исследование влияния отказа наиболее загруженной ветви... 298
6.5. Топология — логическая звезда на базе системы спектрального уплотнения 305
6.6. Выводы 313
Заключение 315
Литература 317
- Основные компоненты архитектуры
- Примеры описания фрагментов телекоммуникационных сетей как сетей массового обслуживания
- Таблица условных вероятностей выбора направлений, получение полных вероятностей выбора направлений
- Соотношения для расчета задержек и вероятностей доставки пакетов в широковещательном режиме
Введение к работе
Актуальность темы исследования. Задача построения современного информационного общества немыслима без развертывания мощных высокопроизводительных мультисервисных сетей. Именно поэтому все Операторы, входящие в ОАО «Связьинвест», а также Операторы корпоративных и ведомственных сетей поставили в качестве приоритетной задачу построения и реконструкции мультисервисных сетей на базе пакетной коммутации с использованием ІР-протокола.
При проектировании такого рода сетей проектировщики столкнулись с очень серьезной проблемой. Если для расчета сетей с коммутацией каналов имеется удобный и проверенный временем математический аппарат, реализованный в виде компьютерных программ на автоматизированном рабочем месте (АРМ) проектировщика, то для сетей с коммутацией пакетов дело обстоит гораздо сложнее. Автоматические телефонные станции (АТС) появились много десятилетий тому назад и их модели хорошо описаны в технической литературе, в то время же такие телекоммуникационные устройства сетей с пакетной коммутацией как маршрутизаторы, серверы, шлюзы и некоторые другие стали широко использоваться относительно недавно. Поэтому модели сетей на их основе недостаточно проработаны, а методы расчета не доведены до практической реализации.
Значительный вклад в решение вопросов, связанных с созданием теоретического и практического задела построения современных мультисервисных сетей, внесли работы отечественных ученых Г.П. Башарина, В.М. Вишневского, B.C. Гладкого, Б.С. Гольдштейна, В.А. Ершова, Г.П. Захарова, В.А. Ивницкого, В.В. Крылова, Н.А. Кузнецова, А.Е. Кучерявого, В.Г. Лазарева, А.Н. Назарова, А.П. Пшеничникова, СИ. Самойленко, К.Е. Самуйлова, Ю.А. Семенова, Н.А. Соколова, С.Н. Степанова, Э.И. Якубайтиса, Г.Г. Яновского и зарубежных специалистов Д. Барбера, Д. Девиса, Л. Клейн-рока, Дж. Мартина, Р. Мобли, М.А. Шнепс-Шнеппе, М. Шварца, Фриша и других.
Актуальность темы нашла подтверждение в таких руководящих материалах как:
Концептуальные положения по построению мультисервисных сетей на ВСС России. Утверждены Минсвязью РФ 25 января 2002 г;
Принципы построения мультисервисных местных сетей электросвязи. Руководящий технический материал. 2005 год;
Стратегия развития информационного общества в Российской Федерации. Утверждена Президентом Российской Федерации В.Путиным 7 февраля 2008 г., № Пр-212.
Цель и задачи исследования. Цель и задачи работы заключаются в разработке методов расчета вероятностно-временных характеристик (ВВХ) мультисервисных сетей. Для достижения поставленной цели необходимо решить следующие основные задачи:
Осуществить рассмотрение сценариев эволюции существующих одно-сервисных сетей и их миграции к мультисервисным с целью формулирования требований к методам анализа современных сетей.
Провести анализ архитектур сетей переходного периода, а также сетей связи следующего поколения - Next Generation Network (NGN) и описание их компонентов в терминах теории массового обслуживания (ТМО).
Сформулировать системный подход к построению моделей и разработке методов расчета характеристик мультисервисных сетей.
Описать потоки на узлах и ветвях сети в условиях статистического равновесия.
Описать типовые топологии мультисервисных сетей в терминах теории множеств.
Разработать методы расчета характеристик сетей с несколькими классами обслуживания.
7. Выполнить с использованием разработанных программных средств
расчеты характеристик сетей и провести системный анализ.
Объектом исследования являются мультисервисные сети с несколь
кими классами обслуживания.
Предметом исследования являются модели и методы, предназначенные для расчета характеристик качества обслуживания и последующего системного анализа мультисервисных сетей.
Методология исследования. Для решения поставленной задачи используются элементы теории сложных систем, аппарат конечных дискретных цепей Маркова (КДЦМ), теория телетрафика, ТМО, теория графов, элементы теории множеств, матричный аппарат, элементы вычислительной математики.
Научные результаты, выносимые на защиту
Процедура расчета элементов матрицы переходных вероятностей (МПВ), описывающей процесс передачи одиночного пакета по сети в виде дискретной марковской цепи с поглощающими состояниями.
Соотношения, связывающие для важнейших частных случаев элементы таблиц распределения информации (таблиц коммутации по меткам, маршрутных таблиц, таблиц коммутации) с элементами МПВ.
Соотношения, описывающие типовые топологии сетей в терминах теории множеств.
Системы нелинейных алгебраических уравнений (СНАУ), описывающие потоки на ветвях и узлах сети в стационарном режиме и позволяющие рассчитать для каждой категории обслуживания время задержки и вероятности потерь пакетов между каждой парой узлов сети, а также потоки на ветвях и узлах сети, задержки, вероятности блокировок и уровни загрузок каналов.
Методы, основанные на решении СНАУ, позволяющие рассчитывать характеристики сети в условиях совместного воздействия различных факторов, в том числе при изменениях:
нагрузки;
структуры тяготения;
пропускной способности каналов;
при отказе оборудования и обрывах каналов;
числа классов обслуживания.
6. Результаты расчетов, позволяющие определить наиболее критические места на сети в условиях совместного воздействия различных факторов, оценить эффект от разделения пакетов на классы обслуживания. Научная новизна результатов исследования.
Разработана процедура расчета элементов МПВ, описывающей процесс передачи пакетов по сети в виде дискретной марковской цепи с поглощающими состояниями.
Для важнейших частных случаев получены соотношения, связывающие элементы таблиц распределения информации (таблиц коммутации по меткам, маршрутных таблиц, таблиц коммутации) с элементами МПВ.
Разработаны математические модели в форме СНАУ, описывающих потоки на ветвях и узлах сети в стационарном режиме как при использовании одного, так и нескольких классов обслуживания.
Разработаны алгоритмы и методы расчета характеристик сетей, основанные на решении СНАУ.
Получены соотношения, позволяющие описывать типовые топологии сетей в терминах теории множеств.
Получены результаты, позволяющие оценить эффект от разделения пакетов на классы обслуживания, определить каналы сети, склонные к перегрузкам, дать рекомендации по разгрузке наиболее перегруженных каналов, изучить влияние места обрыва канала на характеристики качества обслуживания.
Обоснованность и достоверность основных результатов работы обеспечивается строгим характером использованных методов, адекватностью и корректностью примененного математического аппарата, сопоставлением с аналогичными результатами, полученными другими исследователями. Достоверность положений и выводов работы подтверждается результатами моделирования, практической реализацией и внедрением разработок.
Личный вклад. Все результаты, составляющие содержание данной работы, получены автором самостоятельно, соответствуют пунктам 1и 2 паспорта специальности 05.12.13. В главе 6 использована программа, разработанная автором лично.
Практическая значимость работы
Использование разработанных методов позволит рассчитать характеристики сети при различном наборе исходных данных, увеличить возможное количество рассматриваемых вариантов и выбрать из них оптимальный на основе строгого научного анализа, улучшить качество проектов за счет комплексного решения, возникающих при проектировании задач, сократить
сроки проектирования за счет его компьютеризации, сократить затраты на проектирование, прежде всего, за счет использования возможностей, предоставляемых вычислительной техникой.
Реализация результатов работы. Результаты диссертационных исследований по разработке методов расчета характеристик сетей использовали следующие предприятия:
1. ОАО «Гипросвязь» г. Самара - при выполнении ряда проектов по
построению мультисервисных сетей;
ЗАО «Энвижн Групп» Энвижн-Волга - при принятии проектных решений по заказу «Организация "последних миль" на объектах Приволжского филиала ОАО «Ростелеком»;
ООО «ТехноСерв А/С» - при выполнении заказа « Проектирование технической архитектуры Единой системы управления предприятием (ERP) ОАО «ВолгаТелеком» на основе программного продукта Oracle e-Business SuiTe. Телекоммуникационная подсистема»;
4. Самарский филиал «Ростелеком - Волга» - для расчета характери
стик и системного анализа сети передачи данных IP/MPLS;
5. ФГОБУ ВПО ПГУТИ - при внедрении в учебный процесс на ка
федре МСИБ
Апробация работы. Основные положения диссертационной работы были представлены и обсуждены на школе-семинаре «Проблемы и перспективы внедрения мультисервисных сетей на основе современных телекоммуникационных технологий» (Самара, 2002), на школе-семинаре «Развитие мультисервисных сетей в МРК ОАО «Связьинвест» (Самара 2004), на школе-семинаре «Особенности построения сетей электросвязи на основе технологии IP-MPLS» (Самара 2005), на школе-семинаре «Управление и контроль качества услуг в сетях нового поколения» (Самара 2005), на семинаре-совещании «Развитие широкополосного доступа на сетях электросвязи России», на юбилейной научно-практической конференции «35 лет ФАИТ и 90 лет со дня рождения основателя факультета профессора Л.Ф. Куликовского» (Самара 1995), на Всероссийской межвузовской научно-практической конференции «Компьютерные технологии в науке, практике и образовании» (Самара, 2002, 2003, 2004, 2005, 2007, 2008, 2009, 2010, 2011), российских НТК профессорско-преподавательского состава ПГАТИ (Самара 1999, 2000, 2001, 2005), на десятой международной научно-технической конференции «Проблемы техники и технологий телекоммуникаций» ПТ и ТТ-2009.
Публикации. По теме диссертации опубликовано 65 печатных работ, в том числе 22 статьи, из них 16 - в журналах, входящих в перечень ВАК, кроме того, 1 статья из перечня ВАК будет опубликована в первом квартале 2012 года.
Структура и объем работы. Диссертация состоит из введения, 6 глав, заключения, списка литературы и приложения. Основной текст диссертации составляет 353 страницы, в том числе 98 рисунков, 32 таблицы, список литературы из 310 наименований.
Основные компоненты архитектуры
Важнейшая роль отводится системам телекоммуникаций при реализации национальных проектов [48-52], информатизации регионов [53-55], созданию электронного правительства [56] и информационного общества [6]. Теоретический задел для решения этих задач был создан в работах [8], [57-62]. Серьезным этапом в информатизации страны стало подключение в 2008 году 100% школ и учебных заведений к всемирной сети Интернет [63], а еще ранее - подключение к всемирной паутине важнейших научных центров страны [64].
Одной из самых главных задач, которые ставят перед собой Операторы связи, является переход к новой структуре сети, ориентированной на передачу разнородного трафика (данных, видео, голоса) с обеспечением необходимого качества обслуживания абонентов, набора современных услуг, безопасности и надежности. При выборе проектных решений необходимо исходить из того, что проектируемая сеть должна удовлетворять следующим требованиям [3,4, 26-28,65-69]: использовать новейшие принципы построения, в основе которых должны лежать протоколы и технологии, одобренные соответствую щими комитетами по стандартизации в области связи; ориентироваться на широкое применение оптоволокна как при построении сетей доступа, так и магистрального сегмента [70-78]; обладать высокой структурной надежностью и обеспечивать связность сети при обрыве каналов связи и отказе оборудования; использовать оборудование операторского класса, обеспечивающего высокую надежность и возможность восстановления соединений в реальном времени при аварийных ситуациях; обеспечивать конфиденциальность и защиту данных; предусматривать механизмы защиты от подмены адресов с целью предотвращения неавторизованного доступа к услугам; обеспечивать преемственность старых услуг на новой архитектуре; поддерживать механизмы обеспечения качества обслуживания QoS, что является обязательным условием при передаче чувствительного к параметрам задержек трафика, такого как речь и видео; обеспечивать масштабируемость сети, под которой будем понимать возможность многократного увеличения портовой мощности сети, пропускной способности магистрали, возможности расширения списка оказываемых услуг; гарантировать выполнение соглашений об уровне обслуживания для заданных групп абонентов, а в идеале - для каждого клиента; использовать управление сетью по стандарту TMN [79].
Выше отмечалось, что многие Операторы уже приступили к строительству мультисервисных сетей, ориентируясь на предоставление комплексной услуги Triple Play [80]. Конечный пользователь при этом получает доступ одновременно к трем услугам: телефонии, скоростному Интернет и IP 35 телевидению. Обратим внимание на то, что Оператор мультисервисной сети не просто обеспечивает предоставление старых услуг на новой технологической базе, но и дополняет этот список услуг новыми, которые отсутствуют в традиционных односервисных сетях. В целом, Triple Play - это маркетинговый термин, подразумевающий предоставление трех основных услуг, а также услуг, производных от базовых, на мультисервисных ІР-сетях операторского класса.
Поскольку Оператор вместо одной услуги предоставляет сразу три, то это должно способствовать снижению издержек, получению дополнительного дохода и, как следствие этого, повышению конкурентоспособности на рынке предоставления телекоммуникационных услуг.
Архитектура мультисервисной сети при использовании централизованной схемы оказания услуг содержит следующие элементы [80-87]:
Домашняя (офисная) сеть может содержать различное оборудование, например, компьютеры, телевизоры, IP и обычные телефонные аппараты, прочую бытовую технику. В качестве пограничного устройства домашней сети рекомендовано использовать специальное устройство - домашний шлюз.
Узел доступа. Главной функцией узла доступа является обеспечение подключения пограничных устройств Customer Premises Equipment (CPE), расположенных у пользователя, с сетью Оператора. Узел доступа является многопортовым и обеспечивает подключение к сети от нескольких единиц до нескольких сотен CPE. Он объединяет трафик данных, голоса и видео от различных пользователей. Для предоставления скоростного доступа в Интернет на узлах доступа сетей операторского класса широкое распространение получило применение Digital Subscriber Line Multiplexer (DSLAM) - мультиплексоров доступа no DSL, позволяющих подключить конечных пользователей по обычным телефонным линиям при помощи технологии xDSL. В последние годы наметилась тенденция использования в качестве узлов доступа устройств Multi Service Access Node (MSAN) - мультисервисных узлов абонентского доступа, особенностями которых являются наличие большого числа популярных интерфейсов, поддержка QoS.
Узел агрегирования. Объединяет трафик от одного или нескольких узлов доступа и направляет его через транспортную сеть в сторону граничного устройства предоставления услуг, а также передает трафик в обратную сторону — от граничного устройства в сторону узла доступа.
Транспортная сеть может иметь различные топологии: кольцевую, линейную, звездообразную и другие. В качестве технологии построения транспортных сетей широкое распространения получила технология Ethernet, при этом сами коммутаторы обычно соединяются друг с другом либо по кольцевой топологии, либо по звездообразной с использованием оборудования спектрального уплотнения.
Пограничное устройство предоставления услуг представляет собой узел, расположенный между транспортной и опорной сетями. Это первый узел сети, на котором терминируется ІР-сеанс пользователя. Он представляет собой центральный пункт широкополосной сети, через который конечные пользователи получают доступ к различным ее услугам.
В качестве пограничного устройства на сетях операторского класса обычно используют Broadband Remote Access Server (BRAS) - сервер удаленного ШПД. Более подробно о функциях этого устройства будет сказано ниже.
Примеры описания фрагментов телекоммуникационных сетей как сетей массового обслуживания
Рассмотрим СПД с одним классом обслуживания, приведенную на рис. 2.3а. Она содержит магистраль, состоящую из 4 маршрутизаторов, соединенных между собой высокоскоростными цифровыми каналами и образующих сеть с кольцевой топологией. Серверы, ПК конечных пользователей подключены к коммутаторам для рабочих групп, которые, в свою очередь, соединены с портами соответствующих маршрутизаторов.
На рис. 2.36 приведена модель узла коммутации как СМО. Рассмотрим процесс обработки пакета в машрутизаторе. Сам алгоритм обработки приведен, например, в [104]. Если опустить некоторые детали, связанные со спецификой работы протокола сетевого уровня (пересчет полей заголовка принятого пакета, удаление копий ранее принятых пакетов, удаление пакетов с просроченным временем жизни и т.п.), то алгоритм обработки принятого пакета заключается в следующем. У поступившего пакета считывается заголовок и определяется исходящее из узла направление, по которому следует передать пакет дальше по сети. Если очередь пакетов для передачи по данному направлению отсутствует, то пакет практически сразу начинает передаваться по каналу. В случае занятости канала делается попытка поставить пакет в очередь на обслуживание. Если в очереди имеются свободные места ожидания, то пакет ставится в очередь на обслуживание, в противном случае он отбрасывается.
После освобождения канала из очереди извлекается следующий пакет, который ставится на обслуживание. Одновременно осуществляется продвижение пакетов в очереди. Если обслуживание происходит в строгой очередности по мере поступления, то такой механизм обслуживания называют First In - First Out (FIFO), что означает - первым поступил, первым обслужен. Назовем участок сети, содержащий выходной буфер узла и обслуживающий его канал связи, системой буфер-канал (СБК). Нетрудно видеть, что вся сеть представляет собой совокупность СБК. А раз это так, то можно использовать аппарат ТМО для построения модели сети в целом. Модель такой СБК представлена на рис. 2.4.
Учитывая то, что в разных источниках используются различные обозначения, с целью избегания путаницы приведем соотношения из ТМО и теории телетрафика, которые потребуются в дальнейшем для построения моделей сетей. Представим основные соотношения, позволяющие рассчитывать ее характеристики для случая, когда параметры описываются системой М/М/1.
Модель процесса передачи пакета между парой соседних узлов Обозначим через су пропускную способность канала, соответствующего ветви (if), через г у и п 1} - задержку при передаче пакета по ветви (/) ) и вероятность ее блокировки, через оц и сод - очередь и число мест ожидания, через Лц - поток, поступающий на ветвь (if), на соответствующую СБК, через ju - величину обратную длине пакета.
Приведем соотношения для СМО типа M/M/I/N (процесс поступления пакетов пуассоновский, распределение времени обслуживания - экспоненциальное, число мест ожидания равно N). Для этого класса систем при условии, что ри 1 справедливы следующие соотношения [179]:
При неограниченной очереди нет смысла говорить о блокировке направления. Когда же число мест ожидания в буфере ограничено, то вероятность его блокировки будет равна: -Р„УР7 л„ = 1-А? Обозначим через р0 вероятность того, что в системе отсутствуют заявки на обслуживания. Она будет равна: Ро„=1-Р,г В монографии [226] показано, что для системы M/D/1/N с учетом введенных ранее обозначений будут иметь место следующие соотношения: ( " oXp . rt-V-1 -Z 5 2 e"-(-x-p„r «=0 ,-0 (П-Х) Л-1 pxp4 (tf-x-1)! to (%-x + l)! уп(у1± іії1_уе1р:л-х-р х л S (я-х-1)! J_. w„-x+\ Іо [it (n-x)\ V2 о 0,,-x + l)! У „ SP J w„-x+l = 1 to (УУ„-ХУ h K-x+1)! to (wy-x + l)l P,j=fP( j c,j H); ои=/0(Ли,сд,/і); T9=ft{\,c9,n); яу = f, (4, S %»/0 Ї Poj, = /д, (Л c / / ) В дальнейшем эти соотношения будут использованы при разработке методов для расчета характеристик сетей.
Характеристики качества обслуживания во многом определяются пропускной способностью канала. Именно поэтому при строительстве и модернизации сетей обычно в первую очередь усилия направляются на увеличение пропускной способности магистралей, чему способствует повсеместное использование оптического волокна, а также массовое производство высокопроизводительного телекоммуникационного оборудования. Однако возможности по повышению пропускной способности каналов не безграничны. Понятно также, что не все виды трафика нуждаются в одинаковом качестве обслуживания, например, в минимальных задержках. Для приложений, таких как электронная почта, задержки в несколько секунд не являются значительными. При передаче голосового и видеотрафика реального времени задержки в десятки миллисекунд могут существенно ухудшить параметры качества обслуживания. Поэтому практически все современные телекоммуникационные устройства используют механизм очередей для более рационального использования ресурсов сетей при передаче различных типов трафика. Одним из наиболее эффективных и перспективных методов организации и планирования очередей (Queuing and scheduling) является обслуживание в соответствии с классом сервиса (Class-based queuing). При этом пакеты разделяются на отдельные очереди в соответствии с назначенным классом обслуживания и для каждой очереди отводится определенный ресурс пропускной способности канала. Модель узла при использовании этой схемы обработки пакетов приведена на рис. 2.5. Данная модель является обобщенной и справедлива как для маршрутизаторов, так и для коммутаторов и даже шлюзов.
Не акцентируя внимание на особенностях обработки, связанных с типом телекоммуникационного устройства, отметим следующее. На первом шаге обработки пакета необходимо, используя таблицу распределения информации, определить направление, ведущее в сторону искомого узла, а также очередь, соответствующую приоритету передаваемого пакета. На втором шаге обработки пакета, используя тот или иной механизм обработки очередей, осуществляется передача пакета по каналу связи.
Таблица условных вероятностей выбора направлений, получение полных вероятностей выбора направлений
Как было отмечено в первой главе, характерной особенностью сетей региональных операторов, особенно в переходный период, является совместное использование различных технологий, особенно на канальном и физическом уровне. В рассмотренном выше примере порты маршрутизаторов, образующих магистраль, соединены между собой при помощи оптоволокна. При построении систем широко используются системы передачи, такие как, например SDH, xWDM и т.п. Рассмотрим, как учесть наличие в схеме организации связи такого рода оборудования при описании их в виде СеМО. Отличие СПД, представленной на рис. 2.7а, от СПД, изображенной на (см. рис. 2.3а), заключается в том, что маршрутизаторы соединены между собой через тракты, образованные системой SDH. Напомним, что SDH позволяет организовывать прозрачные тракты между любой парой портов SDH мультиплексора. Учитывая этот факт, схема СПД, используемая для дальнейшего анализа, может быть упрощена и представлена эквивалентной схемой, приведенной на рис. 2.76. Обратим внимание на то, что в результате такого упрощения изменилась топология магистрали СПД. Если первоначально она была кольцевой, что подразумевало наличие запасного маршрута в случае обрыва кольца, то после преобразования топология магистрали стала звездообразной. Заметим, что это никоим образом не сказывается на надежности СПД, поскольку одна из особенностей SDH [35] сетей заключается в том, что они проектируются со 100% резервом по пропускной способности и в случае обрыва кольца в одном месте все полупостоянные соединения автоматически в течение 50 мс переключаются на резервные маршруты. Упрощенная схема при этом остается прежней. Модель СПД в виде СеМО с одним классом обслуживания, построенной на маршрутизаторах, соединенных между собой трактами SDH, изображена на рис. 2.8 [255].
В главе 1 отмечалось, что при построении транспортных сетей широко используется технология спектрального уплотнения xWDM, которая многократно повышает пропускную способность магистрали транспортной сети. На рис. 2.9а приведен фрагмент магистрали мультисервисной сети с несколькими классами обслуживания, образованный многоуровневыми коммутаторами и системой спектрального уплотнения, а на рис. 2.10 приведена модель этой магистрали в виде СеМО. Первым шагом к построению такой модели является замена реально физически существующей системы спектрального уплотнения эквивалентными прозрачными каналами (рис. 2.96). Заметим, что в результате такого преобразования изменилась топология сети - кольцевая трансформировалась в звездообразную. Также как и в предыдущем случае с магистралью с использованием SDH, такая трансформация не приводит к снижению надежности, поскольку сети спектрального уплотнения проектируются таким образом, что при обрыве кольца в одном месте происходит переключение нарушенных связей на резервный маршрут. Используя приведенную модель узла (см. рис. 2.5), при использовании нескольких классов обслуживания пакетов переходим от схемы, приведенной на рис. 2.96, к модели сети в виде СеМО, изображенной на рис. 2.10 [255].
Современные сети содержат от одного до нескольких десятков или даже сотен узлов. Перед исследователями и проектировщиками сетей часто стоит задача оценки эффективности работы тех или иных алгоритмов маршрутизации и методов управления потоками при работе на сетях различных топологий и размерностей. Учитывая темпы роста сетей, на повестке дня стоит задача исследования сетей, содержащих несколько десятков и сотен узлов. Ясно, что для ее решения необходимо разработать специальные процедуры генерации стандартных топологий сетей большой размерности [255,257]. к BRAS
Нетрудно видеть, что матрица смежности является редкозаполненной матрицей, поскольку количество ненулевых элементов в z -строке равно рангу этого узла. Например, если сеть содержит 100 узлов, а максимальное число соседей равно 4, то только 4 элемента из 100 в строке будут равны 1, а остальные 96 будут равны 0. Более удобно хранить и обрабатывать информацию о топологии сети в плотном виде. В этом случае топология представляется в виде совокупности множеств узлов соседей: Г = {Г,,.., Г,,.., ГЯц}.
Связь между элементами матрицы смежности /? = [Д;У] и множеством соседей Г, достаточна проста: в =і0,у/ег Р- [i,Y/Sr, Обозначим через nv число ветвей сети. В случае, если каналы являются дуплексными или двунаправленными, то общее число каналов сети может быть получено суммированием элементов матрицы смежности и делением полученного числа пополам: 1 ПЧ П11 Число ветвей можно получить и используя множества соседей: Ниже рассмотрен подход, позволяющий автоматически заполнять эти множества для типовых топологий сетей. В основе разбиения множества узлов на отдельные подмножества лежат следующие принципы: - в рамках одного и того же подмножества номера соседних узлов должны рассчитываться при помощи одних и тех же соотношений; - подмножества должны охватывать все узлы сети; - подмножества не должны пересекаться. Математически вышесказанное может быть записано следующим образом:
Соотношения для расчета задержек и вероятностей доставки пакетов в широковещательном режиме
При построении MT для определенности было принято допущение о том, что, если в сторону искомого узла ведут несколько направлений, имеющих одинаковый вес, то более высоким приоритетом будет обладать то направление, которое соединяет рассматриваемый узел с узлом, имеющим минимальный номер. Разумеется, для определения более приоритетного направления при равных весах можно использовать случайный выбор, однако для рассматриваемого примера это не принципиально.
Рассмотрим, каким образом при помощи сформированных МТ осуществляется передача от исходного узла к искомому на сети, на которой отдельные направления оказались временно перегруженными. Итак, пакет введен в узле / = 1. Обращаясь к т7 видим, что ветвью первого выбора будет ветвь (7,4). Поскольку она заблокирована, то пакет выводится по ветви (7,8) и попадает в узел 8. В узле 8 ветвью первого выбора при поиске узла / = 1 является ветвь (8,5). Поскольку она является не заблокированной, направляем пакет по этому направлению, после чего пакет оказывается в узле 5. В узле 5 предстоит опять делать выбор. И ветвь первого выбора (5,2), и ветвь второго выбора (5,4) оказываются заблокированными. Выводим пакет из узла по ветви третьего выбора (5,6). Пакет поступает в узел 6 и так далее. Окончательный путь, по которому будет передан пакет, выглядит следующим образом: [7]-кі) ={7,8,5,6,3,2,1}. Вес пути при этом равен 6 переприемам (хопам), хотя минимальное расстояние между узлами составляет 2 переприема.
Обратим внимание на то, что использование рассмотренного механизма маршрутизации хотя и позволяет обходить перегруженные участки сети, но и таит в себе опасность зацикливания пакетов. Именно поэтому в протоколах сетевого уровня предусмотрен механизм уничтожения пакетов, время пребывания для которых в сети превысило предельно допустимое значение Заметим, если отмеченные крестиком ветви нельзя использовать не из-за временной перегрузки, а из-за отказа каналов, то ТМВ и МТ необходимо пересчитать. Для рассматриваемого примера они будут равны:
Нетрудно видеть, что пересчитанные МТ значительно отличаются от первоначальных, в частности, появились направления, которые использовать запрещено. Существенно изменились веса маршрутов, что объясняется изменением топологии сети. Обратим внимание на то, что после пересчета МТ сам путь передачи пакета остался прежним, однако сам маршрут был построен при помощи выбора на каждом узле ветвей первого выбора.
Как видно из приведенного выше примера, при принятии решения о выборе исходящего из узла направления для дальнейшей транспортировки пакета принимаются во внимание два фактора: МТ данного узла и состояние направлений, исходящих из этого узла. Запись МТ в виде матрицы рассмотрена выше. Рассмотрим теперь, каким образом, формально может быть описано состояние узлов сети [255,275-277].
Пусть / некоторый узел, в котором может оказаться пакет, адресованный узлу /, а его соседи образуют множество Г, ={j\,..,jv,..,jr}. При этом каждая ветвь (ijv) может находиться в одном из двух состояний: разблокированном (рабочем) и заблокированном. Применительно к сетям с пакетной коммутацией блокировка ветви означает, что число пакетов, находящихся в очереди для передачи по ветви (ijv), совпадает с числом закрепленных за этим направлением буферов.
Состояние отдельных ветвей представим в виде матрицы блокировок п = \п\ , которая представляет собой квадратную матрицу размерности пихпи, элементы которой могут принимать значения в диапазоне от 0 до 1, если узлы / и j имеют непосредственную связь и всегда равны 1, если такая связь отсутствует: л,=\ . (3.9) Введем в рассмотрение вектор состояния узла а: a = [ar,..,av,..,al], (ЗЛО) содержащий г, элементов, которые пронумерованы от 1 до г,. Каждый элемент вектора может принимать одно из двух значений: 0 или 1. Первой компоненте вектора поставим в соответствие состояние ветви (// ,), v- компоненте - состояние ветви (ijv) и, соответственно, rt компоненте - состояние ветви (ijr). Тогда состояние узла может быть формально выражено при помощи значений этого вектора. Заблокированному состоянию ветви (ijv) будет соответствовать av = 0, рабочему состоянию - av = 1. Закодируем значения, принимаемые вектором а, при помощи двоичного кода. Тогда состоянию узла /, при котором все ветви заблокированы, соответствует код 00..О, а состоянию, когда все ветви находятся в рабочем состоянии - код 11..1.
