Содержание к диссертации
Введение
Глава 1. Проблемы реализации услуг виртуальных частных сетей 19
1.1. Перспективность услуг VPN 19
1.2. Классификация технологий реализации VPN 26
1.3. Проблемы оптимального распределения ресурсов сетей общего пользования для реализации VPN 29
1.4. Общая архитектура системы эксплуатационной поддержки VPN 40
1.5. Канальная модель VPN 47
1.6. Потоковая модель VPN 49
1.6.1. Базовые принципы потоковой модели 49
1.6.2. Особенности резервирования сетевых ресурсов в потоковой модели VPN 57
1.6.3. Комбинированная модель VPN 62
1.6.4. Классификация потоковых моделей VPN 65
1.6.5. Условные обозначения потоковых моделей VPN 67
1.7. Анализ работ в области исследования VPN 69
1.8. Постановка задачи исследования 78
1.9. Выводы по главе 1 82
Глава 2. Исследование и разработка метода анализа канальной модели VPN 86
2.1. Постановка задачи исследования канальной модели VPN 86
2.2. Оптимальное распределение сетевых ресурсов для отдельных VPN 92
2.3. Разработка метода распределения сетевых ресурсов для всех реализованных VPN 98
2.4. Исследование канальной модели VPN 104
2.5. Выводы по главе 2 109
Глава 3. Исследование и разработка алгоритмов анализа потоковых моделей VPN при отсутствии ограничений на сетевые ресурсы 111
3.1. Потоковые модели VPN с древовидной топологией 111
3.1.1. Особенности потоковых моделей VPN с древовидной топологией 111
3.1.2. Потоковая модель VPN с древовидной топологией и симметричным трафиком конечных точек 117
3.1.3. Потоковая модель VPN с древовидной топологией и суммарно-симметричным трафиком конечных точек 123
3.1.4. Потоковая модель VPN с древовидной топологией и асимметричным трафиком конечных точек 128
3.1.5. Разработка двухшагового алгоритма покрывающего дерева 138
3.2. Комбинированная модель VPN 150
3.3. Потоковая модель VPN с многопутевым маршрутированием трафика 159
3.4. Потоковая модель VPN с однопутевым маршрутированием трафика 169
3.5. Выводы по главе 3 170
Глава 4. Исследование и разработка алгоритмов анализа потоковых моделей VPN при наличии ограничений на сетевые ресурсы 173
4.1. Влияние ограничений сетевых ресурсов на реализацию VPN 173
4.2. Разработка алгоритма анализа потоковой модель VPN с древовидной топологией и симметричным трафиком 180
4.3. Разработка модифицированного алгоритма для потоковой модели VPN 184
4.4. Потоковая модель VPN с однопутевым маршрутированием трафика 192
4.5. Потоковая модель VPN с многопутевым маршрутированием трафика 200
4.6. Оценка характеристик различных моделей VPN при наличии ограничений на сетевые ресурсы 205
4.7. Выводы по главе 4 209
Глава 5 . Экспериментальное исследование моделей VPN 211
5.1. Программный пакет исследования моделей VPN 211
5.2. Сравнение характеристик канальной и потоковой моделей VPN 217
5.3. Сравнение характеристик различных потоковых моделей VPN 229
5.4. Сравнение характеристик алгоритмов синтеза потоковой модели VPN 235
5.5. Исследование комбинированной потоковой модели VPN 239
5.6. Исследование различных моделей VPN при наличии ограничений на сетевые ресурсы 245
5.7. Выводы по главе 5 253
Глава 6. Разработка экспертных моделей внедрения услуг VPN 255
6.1. Разработка экспертной модели оценки потребностей корпоративных пользователей в услугах VPN 255
6.1.1. Принципы формирования оценки потребностей в услугах VPN 255
6.1.2. Разработка критериев оценки потребностей корпоративных пользователей в услугах VPN 256
6.1.3. Оценка относительной важности критериев 259
6.1.4. Формирование балльной оценки экспертов 270
6.1.5. Оценка результатов экспертизы и формирования решения 276
6.2. Разработка экспертной модели принятия решения по выбору технологий реализации VPN 281
6.2.1. Определение локальных целей 281
6.2.2. Взвешивание локальных целей 285
6.2.3. Минимизация числа локальных целей 288
6.2.4. Определение уровня достижимости целей 291
6.3. Выводы по главе 6 295
Заключение 297
Список литературы 302
Приложения 331
Акты о внедрении 346
- Общая архитектура системы эксплуатационной поддержки VPN
- Потоковая модель VPN с древовидной топологией и асимметричным трафиком конечных точек
- Программный пакет исследования моделей VPN
- Формирование балльной оценки экспертов
Введение к работе
Актуальность проблемы. Крупные компании и организации для создания единого информационного пространства используют терри-ториально-распределенные корпоративные сети для соединения отдельных сетей филиалов и удаленных сотрудников с сетью центрального офиса. Традиционный способ построения таких сетей - использование выделенных (чаще всего арендованных у телекоммуникационных операторов) каналов для организации связей «локальная сеть -локальная сеть» и телефонных сетей общего пользования для связи с удаленными сотрудниками. Бурное развитие в конце XX века сетей с пакетной коммутацией (и, прежде всего, Интернет) породило новую тенденцию - использование для построения глобальных корпоративных связей более дешевого и более доступного (по сравнению с выделенными каналами) транспортного ресурса пакетных сетей.
Однако такое заманчивое и дешевое решение - передача корпоративных данных через публичную пакетную сеть - представляет собой очевидную угрозу для безопасности сети любого предприятия, не говоря уж об органах государственной власти и управления. Кроме этого, отказавшись от выделенных каналов с гарантированной пропускной способностью, компания вынуждена мириться с непредсказуемым характером производительности пакетных каналов связи, особенно в Интернет.
Для решения этих проблем может быть использована услуга виртуальных частных сетей VPN (Virtual Private Network). Виртуальная частная сеть строится на основе логических соединений между определенными корпоративными пользователями через сеть общего пользования с пакетной коммутацией, изолированных на логическом уровне от других пользователей той же сети. VPN обеспечивает безопасность и секретность, как в традиционной частной сети, при сохранении стоимости передачи информации, как в сети общего пользования. Следовательно, такая услуга востребована многими корпоративными пользователями, не имеющих собственных сетевых ресурсов, в том числе органами государственной власти и другими бюджетными организациями, ввиду ее экономичности и доступности.
Хотя услуги виртуальных частных сетей операторы предоставляют уже достаточно длительный период (начиная с пакетных сетей Frame Relay и ATM), тем не менее, только в связи с активным развитием сетей на базе протокола IP (Internet Protocol) в последнее время наблюдается рост научных исследований технологии VPN. Несмотря на зна-
чительную популярность тематики исследования VPN приходится констатировать, что до сих пор остается множество вопросов и нерешенных задач. Перечислим основные из них:
фактически отсутствует единая теоретическая база, которая бы служила методологической основой решения всего комплекса задач поддержки услуг VPN - планирования, реализации и эксплуатации виртуальных сетей;
имеющиеся теоретические подходы к оптимальному распределению полосы пропускания сетей общего пользования для реализации VPN не учитывают многих особенностей функционирования современных виртуальных сетей;
отсутствуют эффективные алгоритмы и программные системы, которые позволяют сократить эксплуатационные расходы провайдеров услуг VPN и тем самым снизить на них тарифы.
Решение указанных проблем позволит повысить эффективность использования сетевой инфраструктуры в целом, что выгодно как потребителям, так и поставщикам услуг VPN. Таким образом, актуальность темы диссертационной работы определяется необходимостью разработки теории планирования VPN, под которой понимается совокупность математических моделей и методов исследования, предназначенных для использования провайдерами услуг VPN при решении задач оптимального распределения имеющихся сетевых ресурсов на различных этапах эксплуатации виртуальных сетей.
Актуальность изучения и исследования VPN обусловлена еще и тем, что данная технология является базовой для построения в России телекоммуникационной сети для государственных нужд в рамках реализации национальной концепции «электронного правительства», сформулированной в виде Федеральной целевой программы «Электронная Россия (2002-2010 годы)». Одним из практических примеров такого подхода является создаваемая в настоящее время крупнейшая в России VPN «Образование» в рамках реализации одноименного национального проекта.
Объектом исследования являются виртуальные частные сети.
Предметом исследования являются модели и методы оптимального распределения полосы пропускания сети общего пользования для реализации виртуальных частных сетей в соответствии с требованиями пользователей услуг и возможностями провайдера услуг VPN.
Цель работы и задачи исследования. Цель диссертации состоит в разработке элементов теории планирования VPN на базе новых моде-
лей и методов анализа и реализации полученных результатов в виде алгоритмов и программных пакетов. Данные модели, методы и алгоритмы должны обеспечить повышение эффективности использования ресурсов сетей общего пользования, что выгодно как пользователям, так и провайдерам услуг VPN.
Для реализации поставленной цели необходимо решить следующие задачи:
провести анализ характерных особенностей практической реализации виртуальных частных сетей, которые необходимо учитывать при разработке теоретической основы планирования VPN;
обосновать базовые принципы построения автоматизированной системы эксплуатационной поддержки OSS (Operations Support System) деятельности провайдера услуг VPN;
сформировать системный подход к построению моделей и разработке методов оптимизации виртуальных частных сетей с учетом интересов, как потребителей, так и поставщиков услуг VPN;
разработать методы анализа и синтеза топологии VPN на основе теории графов с учетом различных аспектов практической реализации частной сети (характера трафика, способов маршрутирования трафика в VPN, ограничений на доступную полосу пропускания и др.);
провести экспериментальные исследования моделей и методов планирования VPN с использованием разработанных программных средств и оценить их эффективность;
- разработать методики количественной оценки управленческих
решений при предоставлении услуг VPN.
Методы исследования. Для решения перечисленных задач в работе использовались методы теории графов, теории оптимизации, теории телетрафика, теории вероятностей и математической статистики, численные методы расчета и анализа, методы экспертных оценок.
Достоверность основных результатов работы обеспечивается строгим характером использованных методов, адекватностью и корректностью примененного математического аппарата, сопоставлением с аналогичными результатами, полученными другим исследователями. Достоверность положений и выводов работы подтверждается результатами моделирования, практической реализации и внедрения разработок.
Научная новизна.
1. Разработан методологический подход к планированию виртуальных частных сетей, учитывающий в совокупности интересы потре-
бителей и поставщиков услуг VPN и позволяющий получить законченное системно-техническое решение - от анализа потребностей в услугах VPN до планирования, создания и последующего обслуживания корпоративных сетей связи.
-
Разработаны элементы теории планирования VPN с использованием аппарата теории графов в виде комплекса моделей и методов анализа и синтеза топологии виртуальной сети с учетом полноты информации о трафике конечных точек VPN и его характере, способов его маршрутирования, ограничений на доступные сетевые ресурсы.
-
Предложено развитие метода оценки сетевых доходов при реализации нескольких VPN на базе канальной модели с учетом ограниченности ресурсов отдельных участков сети общего пользования.
-
Разработаны эффективные алгоритмы анализа и синтеза топологии VPN для различных потоковых моделей, обеспечивающие поддержку автоматизированного проектирования и реализации виртуальных сетей на практике при больших размерах сетей.
-
Предложена комбинированная модель VPN, основанная на использовании более полной информации о распределении трафика, которая дает существенный выигрыш в требуемой полосе пропускания сети общего пользования по сравнению с потоковой моделью.
-
Разработаны экспертные модели, позволяющие формализовать и унифицировать процедуры оценки потребностей корпоративных пользователей в услугах виртуальных сетей и принятия решения по выбору технологии реализации VPN.
Личный вклад. Все результаты, составляющие содержание данной работы, получены автором самостоятельно. В гл. 5 использованы программные средства, разработанные при непосредственном участии автора и под его научным руководством.
Практическая ценность работы заключается в том, что разработанные модели, методы и алгоритмы анализа и синтеза топологии виртуальных сетей реализованы в виде пакета прикладных программ, использование которого позволило провайдерам услуг VPN повысить эффективность планирования, администрирования и функционирования виртуальных сетей, автоматизировать процессы эксплуатационной поддержки деятельности провайдера услуг VPN, снизить тарифы на предоставляемые услуги, обеспечить поддержку соглашений о заданном качестве обслуживания пользователей SLA (Service Level Agreement).
Разработанные экспертные модели позволили получить количест-
венные оценки потребностей корпоративных пользователей в услугах VPN и принятия решения по выбору технологии реализации VPN в компаниях, имеющих разветвленную (многофилиальную) территориально разнесенную структуру, что повысило лояльность корпоративных клиентов.
Реализация результатов работы. Результаты диссертационных исследований по разработке моделей и методов анализа виртуальных частных сетей использованы в организациях:
-
ОАО «Связьинвест» - при выполнении ряда НИР, целью которых являлась разработка типовых технических решений и методических рекомендаций по реализации услуг VPN;
-
Тульский филиал ОАО «Центр Те леком» - при построении современных сетей корпоративных клиентов на базе высокоскоростной информационной транспортной сети;
-
Самарский филиал ОАО «ВолгаТелеком» - при реализации филиалом Политики в области качества услуг виртуальных частных сетей в рамках системы менеджмента качества в соответствии с требованиями ГОСТ Р ИСО 9001-2001;
-
Иркутский филиал ОАО «СибирьТелеком» - для повышения эффективности распределения ресурсов мультисервисной сети при предоставлении услуг VPN корпоративным пользователям;
-
ГОУ ВПО «Поволжская государственная академия телекоммуникаций и информатики» (ПГАТИ) - при внедрении в учебный процесс по специальности 210406 «Сети связи и системы коммутации» на кафедре автоматической электросвязи;
-
Самарский региональный телекоммуникационный трейнинг центр - при проведении курсов переподготовки и повышения квалификации специалистов телекоммуникационных предприятий.
Использование результатов работы подтверждено соответствующими документами, приведенными в приложениях.
Апробация работы. Основные положения диссертационной работы были представлены и обсуждались на: школе-семинаре «Проблемы и перспективы внедрения мультисервисных сетей на основе современных телекоммуникационных технологий» (Самара, 2002), Международном семинаре «Перспективы развития современных средств и систем телекоммуникаций» (Новосибирск, 2002), 4 международной научно-технической конференции (НТК) «Проблемы техники и технологии телекоммуникаций» (Уфа, 2003), 6 и 7 Международных конференциях «Цифровая обработка сигналов и ее применение» (DSPA-
2004, DSPA-2005) (Москва, 2004), X международной НТК «Радиолокация, навигация, связь» (RLNC-2004) (Воронеж, 2004), LIX, LX и LXI научных сессиях, посвященных Дню радио (Москва, 2004, 2005, 2006), школе-семинаре «Развитие мультисервисных сетей в МРК ОАО «Связьинвест» (Самара, 2004), 5 Международной конференции «Проблемы техники и технологий телекоммуникаций» (Самара, 2004), XIV Международном симпозиуме «Современное состояние и перспективы развития инфокоммуникаций» (Самара, 2005), 6 международной выставке - форуме «Инфокоммуникаций России - XXI» (Самара, 2006), 7 Международной НТК «Проблемы техники и технологий телекоммуникаций» (Самара, 2006), 8 Международной НТК «Проблемы техники и технологий телекоммуникаций» (Уфа, 2007), семинаре «Услуги электросвязи. Инновационные решения, тенденции и проблемы» (Москва, 2008), российских НТК профессорско-преподавательского состава ПГАТИ (Самара, 2002-2008).
Публикации. По теме диссертации опубликовано 59 печатных работ: 2 монографии, 28 статей в журналах и сборниках трудов (12 из которых опубликованы в журналах, входящих в перечень ВАК), 29 тезисов и текстов докладов на международных и всероссийских конференциях.
Основные положения, выносимые на защиту.
1. Формализованная в терминах теории графов задача планирова
ния виртуальных частных сетей, позволяющая экономить ресурсы се
тей общего пользования.
-
Система классификации и условных обозначений моделей VPN, позволяющие систематизировать модели и методы исследования виртуальных частных сетей.
-
Модели и методы расчета характеристик виртуальных частных сетей, учитывающие особенности их практической реализации, в том числе:
метод решения задачи оптимального распределения сетевых ресурсов при использовании канальной модели VPN,
методы решения задач анализа и синтеза VPN при использовании потоковых моделей,
комбинированная модель VPN.
4. Алгоритмические и программные средства анализа и синтеза
топологии VPN и расчета необходимой полосы пропускания на от
дельных участках сети общего пользования, позволяющие реализо
вать систему OSS провайдера услуг VPN.
5. Результаты исследования комбинированной модели VPN, пока
зывающие существенную экономию ресурсов сетей общего пользова
ния по сравнению с канальной и потоковой моделями.
6. Методы получения количественной оценки потребностей кор
поративных пользователей в услугах виртуальных сетей и принятия
обоснованного решения по выбору технологии реализации VPN.
Структура и объем работы. Диссертация состоит из введения, 6 глав, заключения, списка литературы и приложений. Основной текст диссертации включает 330 страниц, в том числе 100 рисунков, 32 таблицы, список литературы из 290 наименований.
Общая архитектура системы эксплуатационной поддержки VPN
В процессе жизненного цикла услуг VPN провайдер должен иметь возможность реализовывать следующие функции (рис. 1.12):
1. Ввод данных об услуге VPN - получение исходной информации о требуемой услуге от заказчика и ввод ее в систему автоматизированной поддержки услуг VPN. Здесь возможны различные варианты реализации данной функции - ввод информации через автоматизированное рабочее место системы, посредством импорта данных или через интерфейс OSS для автоматизированного обмена информацией с приложениями пользователя.
2. Модификация VPN - возможность добавления новых географических точек, устройств и функций в виртуальной сети, сохраняя при этом всю существующую функциональность VPN.
3. Планировка VPN - распределение доступных сетевых ресурсов на стадии создания VPN для выполнения специфических требований, при этом созданные ранее VPN не затрагиваются и непрерывно функционируют в прежнем режиме.
4. Аудит VPN - проверка доступности всех необходимых сетевых ресурсов и возможности функционирования виртуальной сети в заданной конфигурации.
5. Активация VPN - передача конфигурационной информации в сетевые устройства для реализации планируемой VPN.
6. Мониторинг VPN - после настройки оборудования и запуска услуги осуществляется контроль функционирования сетевых устройств с целью обеспечения полной работоспособности виртуальной сети.
7. Отчетность по VPN - формируется оперативная и статистическая отчетность обо всех аспектах функционирования VPN, что позволяет обеспечить высокую доступность и качество предоставления услуги. Возможно также взаимодействие с различными автоматизированными системами провайдера (биллинговыми, CRM, BSS и др.) через прикладной программный интерфейс API.
Для автоматизации процессов администрирования и настройки сетей общего пользования с целью эффективного предоставления корпоративным клиентам услуг виртуальных частных сетей предлагается использовать специальную систему поддержки эксплуатационной деятельности провайдеров услуг VPN - VPN-OSS (Operations Support System) [207].
Система VPN-OSS должна поддерживать реализацию следующих функций:
- хранение данных технического учета и топологии пакетной сети общего пользования и реализованных VPN;
- мониторинг занятой и доступной полосы пропускания и характеристик отдельных звеньев пакетной сети общего пользования задержек (задержки пакетов, джиттер, процент потерь пакетов, коэффициент готовности и др.);
- хранение, анализ и выдача данных о характеристиках трафика пакетной сети общего пользования и реализованных VPN;
- балансировка загрузки пакетной сети общего пользования с помощью соответствующего конфигурирования сетевых устройств;
- автоматизация и упрощение задач оптимального планирования и конфигурирования VPN.
Система VPN-OSS состоит их следующих функциональных подсистем (рис. 1.13) [207]:
1) подсистема измерений пропускной способности и задержек в сети общего пользования;
2) подсистема данных о сети общего пользования;
3) подсистема сетевой топологии;
4) подсистема планирования VPN;
5) подсистема конфигурирования VPN;
6) подсистема принятия заказов.
Подсистема измерений сети обеспечивает мониторинг ІР-сети и включает следующие измерения:
- имеющейся полосы пропускания каналов сети общего пользования;
- использованной полосы пропускания потока VPN (каждый поток идентифицируется парой адресов узлов источника/получателя);
- величины задержки из конца в конец между узлами сети.
В подсистеме измерений для сбора информации в сети могут быть использованы следующие основные механизмы и протоколы:
- для измерения имеющейся полосы пропускания (пропускной способности) звена (канала) сети - простой протокол управления сетью SNMP (Simple Network Management Protocol) [92];
- для измерения задействованной полосы пропускания потока -технология удаленного мониторинга сети RMON (Remote Network MONitoring) [93], технология NetFlow (фирмы Cisco) [94];
- для измерения задержек - пробные пакеты (маршрутизируются с использованием источника трафика).
При проведении измерений в сети IP необходимо учитывать тот факт, что использование сообщений SNMP и NetFlow может сильно повлиять на производительность маршрутизаторов (уменьшение ее до 20%), так как передаваемый служебный трафик создает дополнительную нагрузку на сеть.
В подсистеме данных сети хранятся следующие данные, собираемые в сети:
- пропускная способность звеньев (каналов) сети;
- задействованная полоса пропускания потоков;
- задержка из конца в конец.
Подсистема сетевой топологии предназначена для:
- автоматического отслеживания состояния текущих активных сетевых узлов и их интерфейсов;
- автоматического отслеживания состояния соединений сетевых узлов на 2-м уровне модели OSI;
- поддержки сетевой базы данных, содержащей архивные и текущие данные об элементах сети и их соединениях;
- поиска и выдачи информации об изменениях топологии сети общего пользования.
Знание сетевой топологии необходимо для решения многих задач технической эксплуатации, и, прежде всего для инжиниринга трафика, определения корреляций событий в сети, анализа первопричин событий, управления сетевой конфигурацией.
Необходимость автоматизации процессов отслеживания состояния сетевой топологии обусловлена следующими причинами:
- сеть связи является динамической системой, состояние которой меняется достаточно часто;
- крупные сети общего пользования включают сотни узлов и тысячи звеньев;
- ручное отслеживание состояния сетевой топологии является крайне трудоемкой и приводит к частым ошибкам.
Основные подходы, которые должны использоваться в подсистеме сетевой топологии:
1. Хранение данных обо всех узлах и интерфейсах данного сетевого сегмента.
2. Использование информационной базы данных МІВ (Management Information Base) для получения списков узлов, в которых указаны все порты каждого узла.
3. Для каждого порта каждого узла генерация списка узлов, с которыми связан этот порт.
4. Использование алгоритмов генерации топологии, позволяющих получать карту сети данного сетевого сегмента.
Подсистема планирования виртуальных частных сетей предназначена для оптимизации использования ресурсов сети общего пользования с минимизацией резервируемой полосы пропускания для каждой реализуемой VPN с учетом ранее реализованных виртуальных сетей. В данной подсистеме в зависимости от выставленных требований заказчика могут использоваться различные модели и методы реализации VPN.
Потоковая модель VPN с древовидной топологией и асимметричным трафиком конечных точек
Для случая асимметричного трафика задача определения древовидной топологии VPN с минимальной резервируемой полосой пропускания по сложности не сложнее расчета дерева Штейнера. Однако известно, что сложность расчета дерева Штейнера NP-сложная (NP-hard) [11, 121]. NP-сложность (nondeterminictic polinomial hard) имеют задачи, решение которых на недетерминированной машине Тьюринга возможно за время, полиномиально зависящее от числа параметров (далее используется термин «полиномиальное время»). К таким задачам относятся задачи подсчета путей на графе, поиска кратчайшего пути (задача о коммивояжере) и другие. Следовательно, и проблема расчета оптимального дерева при асимметричной нагрузке также NP-сложная. Поэтому решение данной задачи возможно только аппроксимационными методами.
Задача нахождения оптимальной древовидной топологии VPN в случае асимметричного трафика конечных точек может быть сформулирована как задача целочисленного программирования. Определим свойства графа с древовидной топологией, соединяющего конечные точки с асимметричной полосой пропускания.
Очевидно, что использование в дереве Т только равновесных ребер позволяет образовать связанный компонент. Отсюда следует, что корневые вершины образуют дерево, состоящее только из равновесных ребер. Таким образом, если удалить равновесные ребра из дерева Т, то в каждом из получающихся связанных компонент останется только одна корневая вершина. Обозначим через Ри компонент, включающий корневую вершину
Однако если дерево Т не содержит равновесных ребер, то будет только один компонент. При смещении всех ребер в компоненте можно показать, что существует уникальная вершина v такая, что каждое ребро, инцидентное с вершиной v, смещается от нее. При этом данная вершина v является корневой для компонента.
Таким образом, дерево Т состоит из совокупности корневых вершин, связанных равновесными ребрами, и связанных компонент Ри для каждой корневой вершины, включающих только смещенные ребра. Обозначим через S(T) совокупность корневых вершин в дереве Т и через Н(Т) - совокупность равновесных ребер в дереве Т. Чтобы построить дерево T(S) для совокупности вершин S таких, что CT(S)-CS во-первых соединим вершины совокупности S деревом
Штейнера и добавим все ребра дерева Штейнера к дереву T(S). Затем объединим все вершины в совокупности iS в одну супервершину и построим дерево с поиском в ширину, подключенное к супервершине и соединяющее все конечные точки VPN в совокупности Р. Добавим ребра полученного дерева к дереву T(S). Тогда задача определения оптимальной VPN с древовидной топологией эквивалентна определению совокупности вершин S, для которых резервируемая полоса пропускания С$- минимальна.
Справедливо и обратное, если Topt - оптимальное дерево, то для него полоса пропускания минимальна, т.е. всегда Cg Cj Следовательно, определив совокупность корневых вершин S, всегда можно построить оптимальное дерево T(S). Таким образом, при асимметричном трафике для определения оптимального дерева VPN необходимо найти совокупность вершина S, для которых резервируемая полоса пропускания в соединяющих их ребрах минимальна.
Задача расчета совокупности вершин S с минимальной резервируемой полосой пропускания может быть сформулирована как задача целочисленного программирования, если известна одна из вершин в совокупности S. Первые два ограничения определяют, что каждая конечная точка j VPN должна быть назначена как минимум одной вершине из совокупности S. Третье ограничение гарантирует, что вершины в совокупности S соединяются деревом Штейнера. Это достигается требованием того, что если конечная точка j VPN сопоставляется вершине і (данная вершина і принадлежит совокупности S), то вершина і соединяется с вершиной v ребрами дерева Штейнера. Соответственно, функция, которую необходимо минимизировать, и есть резервируемая полоса пропускания совокупности вершин S. Таким образом, зная, что совокупность S должна содержать вершину из совокупности V, можно определить оптимальное дерево, выполняя следующие шаги:
1. Для каждой вершины v =V выполняется алгоритм целочисленного программирования для расчета оптимальной совокупности вершин Sv, содержащей вершину v (Sv состоит из вершин і, для которых Уі= в решении задачи целочисленного программирования).
2. Определяется дерево T(SV), у которого резервируемая полоса пропускания минимальна.
Отметим, что хотя задача определения совокупности вершин с минимальной резервируемой полосой пропускания имеет несколько сходств с хорошо известной задачей размещения ресурсов [153], однако есть одно существенное отличие. Если мы будем рассматривать отдельные вершины в совокупности V как ресурсы, то в рассматриваемом случае полоса пропускания для каждого индивидуального ресурса (вершины) равна 0. Однако выбранные ресурсы как единое целое имеют суммарную величину полосы пропускания, т.к. они объединяются деревом Штейнера с соответствующими величинами пропускных способностей ребер Се. Таким образом, полоса пропускания каждого отдельного ресурса (вершины) определяется полосой пропускания в дереве Штейнера, объединяющего эти выбранные ресурсы (вершины).
Задача целочисленного программирования (3.13) отличается от задачи линейного программирования (ЛП) дополнительным требованием целочисленности переменных. В отличие от задачи ЛП задача ЦП является NP-трудной (NP-hard) и поэтому не может быть решена за полиномиальное время. Для приближенного решения задачи ЦП могут быть применены различные методы, например отсечений, ветвей и границ, алгоритмы динамического программирования, методы локального поиска, аппроксимационные алгоритмы [53, 114].
Для решения задачи ЦП в [36] предлагается алгоритм аппроксимации, основанный на решении линейного упрощения задачи целочисленного программирования и дальнейшего округления дробного (нецелочисленного) решения до целочисленного. Дробное решение дает увеличение требуемой полосы пропускания на небольшую величину по сравнению с целочисленным решением. Алгоритм округления состоит из следующих двух фаз: во-первых, используется методика отсеивания и округления, предложенная в [150], чтобы получить новое приближенное (нецелочисленное) решение, имеющее следующее свойство: для любой конечной точки VPNy, приближенно совпадающей с вершиной, длина пути DQ(I,J) есть величина не очень большая. Далее полученное дробное решение с близкими характеристиками может быть округлено для получения почти оптимального целочисленного решения.
Упрощение задачи ЦП приводит к следующей постановке задачи ЛП: минимизировать величину
Таким образом, оптимальную резервируемую полосу пропускания дерева VPN с несимметричным трафиком конечных точек можно определить с помощью аппроксимационного метода, основанного на приближенном решении задачи ЛП как задачи целочисленного линейного программирования (ЦЛП). Хотя рассматриваемая задача и имеет небольшое число переменных, но экспоненциально возрастающее число ограничений. В принципе для решения задачи ЛП за полиномиальное время может быть использован метод эллипсоидов [151, 152], но он является неэффективным и на практике не используется.
В [36] предложен алгоритм, использующий прямодвойственный метод (одновременного решения прямой и двойственной задач) [154] для нахождения возможного решения задачи ЦЛП (3.13)
Программный пакет исследования моделей VPN
Для исследования разработанных моделей и оценки практической эффективности применения предлагаемых алгоритмов планирования VPN был разработан программный пакет «Конструктор VPN» [158-162]. Данный пакет представляет собой программное инструментальное средство, предназначенное для создания и редактирования моделей виртуальных частных сетей и исследования их характеристик. Целью разработки являлось получение удобного и мощного инструмента для планирования виртуальных частных сетей, позволяющего решать целый спектр возникающих при этом задач. Пакет располагает современным графическим интерфейсом и обладает широкими функциональными возможностями. Общая структура пакета «Конструктор VPN» представлена на рис. 5.1.
Основными требованиями к разработке пакета были:
- удобный для специалистов различного уровня интерфейс;
- возможность интерактивного ввода данных;
- поддержка сохранения и загрузки созданных моделей сетей;
- решение задач планирования VPN при различных моделях;
- интерактивный просмотр результатов решения задач;
- невысокие системные требования;
- высокие емкостные характеристики пакета;
- возможность стыковки с внешним программным генератором топологий графа, например пакетом BRITE [157], широко используемым при исследовании графовых моделей.
Спектр задач, решаемых разработанным программным продуктом, включает в себя задачи анализа и синтеза оптимальной топологии VPN с симметричным и ассиметричным трафиком конечных точек, с различной топологией получаемых результатов: дерево, набор деревьев или подграф, с учетом стоимости использования полосы пропускания каналов или без него, с ограниченным максимальным трафиком через канал или без учета и др. В основной своей массе это задачи синтеза оптимальной топологии, построенной на канальной и потоковой моделях VPN. В число этих задач входят:
- синтез оптимальной топологии VPN с учетом минимизации стоимости или полосы пропускания при симметричном трафике конечных точек без учета ограничений на пропускную способность каналов сети общего пользования;
- анализ возможности построения заданной топологии VPN при симметричном трафике с учетом ограничений на пропускную способность каналов сети общего пользования;
- синтез оптимальной топологии VPN с учетом минимизации стоимости или полосы пропускания при асимметричном трафике конечных точек без учета ограничений на пропускную способность каналов сети общего пользования;
- синтез оптимальной топологии VPN с учетом минимизации стоимости или полосы пропускания при симметричном трафике конечных точек с учетом ограничений на пропускную способность каналов сети общего пользования;
- синтез оптимальной топологии VPN с учетом минимизации стоимости или полосы пропускания при асимметричном трафике конечных точек с учетом ограничений на пропускную способность каналов сети общего пользования;
- синтез оптимальной топологии VPN с учетом минимизации стоимости или полосы пропускания при однопутевом маршрутировании симметричного трафика конечных точек без учета ограничений на пропускную способность каналов сети общего пользования
- синтез оптимальной топологии VPN с учетом минимизации стоимости или полосы пропускания при многопутевом маршрутировании симметричного трафика конечных точек без учета ограничений на пропускную способность каналов сети общего пользования
- синтез топологии канальной модели VPN.
- синтез оптимальных древовидных топологий отказоустойчивой VPN с симметричным и асимметричным трафиком конечных точек при одиночных отказах ребер дерева VPN для стратегий защиты звена и защиты пути.
Программное обеспечение разработано в среде Borland Delphi 7.0 с использованием формата XML для хранения данных в файлах. Система «Конструктор VPN» предназначена для функционирования в среде операционной системы MS Windows-2000 и более старших версий и обеспечивает работу приложения в следующих основных режимах:
1. Создание новых и редактирование уже существующих моделей VPN.
2. Выполнение экспериментов с моделями VPN.
Разработанная система выполнена в виде приложения с многодокументным графическим интерфейсом и позволяет одновременно работать с несколькими моделями, каждая из которых представлена в своем собственном окне. Модель VPN представляется пользователю в виде отображающего ее графа. Система способна «распознавать» все изменения в графе и автоматически вносить соответствующие изменения в саму модель. Отличие внутреннего представления модели VPN от отображающего ее графа заключается только в отсутствии в ней информации, необходимой для визуального изображения графа. Система позволяет пользователю работать с моделью и через ее отображение в виде матрицы. Управление взаимодействием модели с различными формами ее графического отображения осуществляется редактором модели. Кроме этого, редактор обеспечивает взаимодействие с базой данных и осуществляет оперативный контроль и отвечает за обновление модели в процессе редактирования ее визуального отображения в виде графа. Для проектирования алгоритмов выбрана следующая интуитивно понятная модель сети общего пользования и модель VPN:
1. Сеть общего пользования - граф, где вершины соответствуют узлам сети, а ребра соответствуют каналам между узлами. Граф ориентированный, взвешенный, вес ребра означает стоимость использования канала, могут вводиться ограничения на пропускную способность ребра.
2. Конечные точки VPN задаются дополнительными вершинами графа, имеющими одно исходящее и одно входящее нагруженное ребро в одну и ту же вершину графа сети общего пользования. Нагрузкой данного ребра является трафик конечной точки VPN
На основании данной графовой модели разработаны алгоритмы, которые реализованы с применением объектно-ориентированного программирования (ООП) на классовой модели, позволяющей с одинаковым удобством реализовывать и алгоритмы на графах, и визуализацию.
Пакет имеет простой и удобный в использовании пользовательский интерфейс (рис. 5.2). При его разработке особое внимание было уделено выполнению двух основных требований. Первое из них заключалось в необходимости предоставления пользователю как можно более широких возможностей, позволяющих простыми средствами создавать и редактировать сетевые модели путем их вырисовывания в виде соответствующих графов и последующей манипуляции их фрагментами.
Второе требование касалось необходимости максимальной автоматизации многочисленных рутинных функций, таких как манипуляции с графическим отображением модели через буфер (копирование, вставка и удаление различных фрагментов графа), организации взаимодействия с файловой системой и базами данных, формирование сетки, масштабирование изображений и т.д.
Формирование балльной оценки экспертов
Согласно выбранному методу в рамках разрабатываемой модели оценки потребностей корпоративных пользователей в услугах VPN предполагается, что эксперты после ознакомления с представленной документацией и проведения (при необходимости) информационного обследования компании выполнят балльную оценку полученной информации. Балльная оценка позволит в формализованном виде оценить степень соответствия собранной информации сформированным критериям, описанным в подразделе 6.2.2. При формировании балльной оценки необходимо принять во внимание веса критериев и подкритериев, рассчитываемые по формулам (6.21) - (6.24) для метода МАИ или (6.27) -(6.30) для метода долевых коэффициентов.
Для формирования корректной балльной оценки от экспертов, прежде всего, потребуется определить базу балльных оценок проекта - общую максимальную сумму баллов по всем критериям. Математически это должно быть положительное целое число. В рамках рассмотренного примера в приложении 1 в качестве базы выбрано число 1000, соответствующее 1000 баллам.
После формирования базы проекта рассчитывается максимальная сумма баллов по отдельным критериям - база по критериям. База по критериям рассчитывается по формуле [284, 285].
В дальнейшем эксперты по каждой составляющей критерия или по каждой составляющей подкритерия выставляют относительные оценки от 0,01 до 0,99, которые характеризуют степень удовлетворения требованиям критерия представленных документов и фактических данных. В итоге, назначенная экспертами база балльных оценок БП распределяется по отдельным критериям и подкритериям согласно их значимости, зафиксированной в векторе приоритетов или долевых коэффициентах.
В рамках разработанной модели оценки потребностей корпоративных пользователей в услугах VPN предлагается следующая последовательность действий для формирования балльных оценок экспертов [281 - 283]:
Шаг 1. Эмпирически определить базу балльных оценок проекта -общую сумму баллов по всем критериям, БП.
Шаг 2. Рассчитать базу по каждому к-щ критерию БКк по формуле (6.31).
Шаг 3. Рассчитать базу по каждой т-й составляющей БСКт по формуле (6.32).
Шаг 4. Рассчитать базу по каждому подкритерию БПКт по формуле (6.33).
Шаг 5. Рассчитать базу по каждой т-й составляющей БСПКт по формуле (6.34).
Шаг 6. Рассчитать оценку экспертов ОЭт по каждой га-й составляющей критерия согласно (6.35).
Шаг 7. Рассчитать оценку экспертов ОЭ„ по каждой п-й составляющей подкритерия согласно (6.36).
Шаг 8. Рассчитать суммарную балльную оценку экспертов по всем подкритериям согласно (6.38).
Шаг 9. Рассчитать суммарную балльную оценку экспертов по всем критериям согласно (6.37) и (6.39).
Шаг 10. Рассчитать суммарную бальную оценку по всему проекту согласно (6.40).
Результаты численных расчетов для частного случая экспертных оценок, полученные при использовании шагов 1-10, представлены в приложении 1. Следует отметить, что шкала оценок в таблице 6.4 является ориентировочной и может быть изменена в рамках предлагаемого метода. Однако при использовании предлагаемой модели для нескольких объектов (филиалов одной компании) рекомендуется использовать одни и те же значения в таблицах (во всех таблицах 6.1 - 6.4) для обеспечения сопоставимости результатов использования модели оценок потребностей корпоративных пользователей в услугах VPN.
