Содержание к диссертации
Введение
1 Методы маршрутизации в компьютерных сетях 11
1.1 Классификация методов маршрутизации 11
1.1.1 Основные принципы маршрутизации 12
1.1.2 Статические алгоритмы 16
1.1.3 Динамические алгоритмы 21
1.2 Глобальная и локальная оптимизация 27
1.2.1 Алгоритмы на основе SPF 28
1.2.2 Локальная оптимизация 31
1.3 Выводы 32
2 Источники ошибок и методы их устранения в системах передачи данных 35
2.1 Виды неопределенностей в системах передачи данных . 35
2.2 Методы устранения неопределенности 37
2.3 Использование локальной оптимизации 41
2.4 Уменьшение сложности системы 45
3 Маршрутизация в условиях неполных данных 48
3.1 Модель динамической компьютерной сети 49
3.1.1 Маршрутизация в сети с постоянной структурой . 49
3.1.2 Маршрутизация в сети с динамической структурой 50
3.1.3 Область эффективной маршрутизации 53
3.1.4. Маршрутные записи 55
3.1.5 Факторы, влияющие на выбор маршрутов 57
3.1.6 Учет загрузки сетевых компонентов 58
3.1.7 Оценка динамики R(vi) 59
3.1.8 Формирование внешних маршрутных записей . 59
3.1.9 Оценка эффективности маршрутизатора 62
3.1.10 Локальный выбор маршрутов 63
3.2 Алгоритмы маршрутизации в условиях неполных данных 65
3.2.1 Функционирование маршрутизаторов 67
3.2.2 Построение К(щ) 68
3.2.3 Проверка состояния R(vi) 70
3.2.4 Обновление при отказе 70
3.2.5 Синхронизация времени 71
3.2.6 Обновление внешних маршрутных данных 73
3.2.7 Подготовка к сбросу 74
3.2.8 Процедура передачи данных 75
3.2.9 Объем служебного трафика 78
3.3 Выводы 80
Качество маршрутов и объем служебного трафика 82
4.1 Задача оценки качества маршрутов 82
4.1.1 Функция качества маршрутов 84
4.1.2 Область значений 86
4.1.3 Выбор параметров 88
4.2 Объем служебного трафика 89
4.2.1 Объем служебного трафика при лавинной адресации 91
4.2.2 Объем служебного трафика при маршрутизации с использованием неполных данных 92
4.2.3 Сравнение объемов служебного трафика при различных методах маршрутизации 94
4.3 Снижение качества путей при отказах 96
4.3.1 Выбор маршрутов 97
4.3.2 Распространение обновлений 98
4.3.3 Область эффективной маршрутизации как передающий элемент 100
4.4 Выводы 101
Моделирование и сравнение алгоритмов 103
5.1 Выбор имитационной модели 104
5.1.1. Структура имитационной модели 106
5.1.2 Выбор оцениваемых параметров 108
5.2 Моделирование алгоритмов маршрутизации 109
5.2.1 Сеть с постоянными характеристиками 111
5.2.2 Динамическая сеть с отказами 113
5.2.3 Объем служебного трафика и размеры ОЭМ . 115
5.2.4 Оценка качества путей 116
5.3 Выводы 120
Литература 128
- Основные принципы маршрутизации
- Маршрутизация в сети с динамической структурой
- Объем служебного трафика при маршрутизации с использованием неполных данных
- Моделирование алгоритмов маршрутизации
Введение к работе
Современные корпоративные вычислительные сети (КВС) вышли на качественно новый уровень своего развития. Для него характерно резкое возрастание количества взаимодействующих узлов, интенсивность обмена данными, активное использование мультимедиа-технологий в производственном процессе, повышенные требования к оперативности доставки информации. Сильная территориальная разобщенность таких сетей с одной стороны, и динамический характер параметров сетевых компонентов и топологии с другой, подразумевает создание и использование качественно новых подходов к управлению передачей данных.
Одной из важнейших проблем, требующих решения, является создание эффективных алгоритмов маршрутизации, обеспечивающих поиск необходимых маршрутов с учетом динамики функционирования КВС. Исторически сложившийся подход к решению данной проблемы основан на алгоритмах, созданных для выбора оптимальных путей в графах с фиксированной структурой, г. е. динамическая топология сети не является исходным положением, а каждый случай ее изменения рассматривается как смена режима функционирования. В настоящее время создано множество алгоритмов в которые изначально заложены механизмы обрабатывающие изменения топологии и нагрузки, однако их эффективность сильно зависит от размеров сетей. Рост числа узлов и связей влечет скачкообразное возрастание времени обработки запросов и увеличение интенсивности служебного трафика, связанные с реконфигурацией параметров.
По заявлениям ведущих аналитиков [59J сложность работы маршрутизатора во многом обусловлена программным обеспечением. Это крайне сложный компонент, и заранее указать на все возможные ошибки нельзя. Кроме этого, успехи в плане надежности современного оборудования тоже не обнадеживают: на основе современной технологии
невозможно создать настолько надежные решения, чтобы можно было гарантировать, что они никогда не выйдут из строя.
Природа маршрутизации в компьютерных сетях такова, что, с одной стороны, маршрутизаторам приходится использовать ненадежные каналы связи для передачи служебной информации, что определяет потенциальную возможность ее искажения или потерю в процессе передачи, а с другой - скорость ее передачи не удовлетворяет требованиям оперативности, что приводит к возникновению неверных маршрутов. Каждый маршрутизатор должен поддерживать адекватность своих таблиц текущей топологии сети. Точность отображения маршрутов является ключевым фактором в его способности осуществлять пересылку полезных пользовательских данных.
Еще одним фактором, определяющим необходимость пересмотра современных методов маршрутизации является, активно обсуждаемая [18,19] проблема чрезмерного возрастания объема маршрутных таблиц протоколов внешних шлюзов, Дж. Хьюстоном (G. Huston) в [18] сделан анализ на основании которого можно сделать вывод об экпонен-циальной зависимости роста числа записей в таблицах BGP от времени. Эта тенденция несколько приостановлена использованием бесклассовой междоменной маршрутизации (CIDR), однако это не является принципиальным решением проблемы - рост маршрутных таблиц протоколов группы EGP будет продолжаться.
Существующие на данный момент реализации алгоритмов маршрутизации, созданные за рубежом, носят коммерческий характер и не предусматривают стороннего участия в их развитии. Это ограничивает их использование и адаптацию к конкретным задачам. В частности, эти ограничения играют роль при построении и эксплуатации различного рода корпоративных сетей военного назначения, к которым предъявляются повышенные требования к устойчивости, защищенности и надежности. В силу указанных причин является актуальным создание и реализация
новых подходов к решению проблемы маршрутизации.
Целью диссертационной работы является повышение эффективности маршрутизации и управление качеством маршрутов в корпоративных вычислительных сетях с динамической структурой.
Задачи исследований. Для достижения сформулированной цели в диссертационной работе поставлены и решены следующие задачи:
Анализ существующих методов маршрутизации и подходов к представлению маршрутной информации в компьютерных сетях. Анализ влияния фактора ошибок различного рода в системах передачи данных на конечный результат и условий его возникновения. Поиск способов уменьшения сложности системы и увеличения точности исходных данных при принятии решений,
Разработка модели компютерной сети с динамической структурой и подхода к представлению маршрутной информации.
Создание алгоритма маршутизации на основе разработанной модели компьютерной сети с динамической структурой, анализ его свойств. Выработка рекомендаций по выбору параметров алгоритма.
Проведение имитационного моделирования для проверки характеристик алгоритма и получения его количественной и качественной оценок.
Основное содержание диссертационной работы, посвященное описанию решения поставленных задач, изложено в пяти главах. По теме диссертации опубликовано 18 печатных работ.
В первой главе сделан обзор основных подходов к маршрутизации в компьютерных сетях различного уровня, рассмотрены современные методы и протоколы. Предложена классификации существующих алгоритмов и проведен их анализ. Основное внимание в первой главе уделено обсуждению возникающих проблем: образованию маршрутных петель, росту
объемов служебной информации, возрастанию вычислительной сложности при увеличении числа элементов сети. Приводятся статистические сведения о функционировании различных сетей, на основании которых делаются выводы о факторах, влияющих на эффективность применяемых в настоящее время алгоритмов маршрутизации, предлагаются направления их дальнейшего развития.
Вторая глава посвящена анализу возникновения фактора ошибок в сложных системах передачи данных. Выявляются основные виды неопределенностей, которые возникают при управлении такими системами. Анализируется влияние различных типов ошибок на конечный результат. Указываются достоинства и недостатки существующих методов их устранения. Рассматривается вопрос о соотношении сложности системы и объема необходимой информации для формализации ее модели; делается предположение о том, что возможно уменьшение сложности системы за счет исключения малозначительных для принятия решения параметров и применения локальной оптимизации.
В третьей главе описана, предлагаемая автором, модель компьютерной сети с динамической структурой на основе выделения областей эффективной маршрутизации; предложен подход к представлению маршрутной информации; введено понятие маршрутизации с использованием неполных данных; предлагается алгоритм маршрутизации на основе предложенной модели. Основное внимание уделено вопросам конкретной реализации предложенных идей. Рассматриваются характерные для маршрутизаторов состояния, излагается общая схема алгоритма; отдельно рассматриваются основные процедуры алгоритма маршрутизации с использованием неполных данных: построение области эффективной маршрутизации, проверка ее состояния, процедуры обновления о внутренних и внешних маршрутах, плановое выбывание маршрутизаторов из распределенной процедуры построения маршрутов; рассматривается алгоритм передачи трафика.
В четвертой главе рассматриваются различные характеристики алгоритма с использованием неполных данных, производится сравнение с оптимальными идеализированными алгоритмами и алгоритмами, использующими лавинную адресацию при передаче обновлений. Основное внимание уделено математической постановке задачи с ограничениями. Вводится и развивается понятие качества маршрутов в сети с маршрутизацией на неполных данных, выводится обобщенный критерий качества. Производится анализ ограничений при различных топологиях графов сети, определяется наихудший представитель, На основе анализа поставленной задачи делаются рекомендации по выбору значения 7 в различных условиях. Анализируются общие объемы служебного трафика и приводится практический пример расчета. В заключение, рассматриваются вопросы распространения информации при использовании предложенного алгоритма маршрутизации с целью обозначения путей для дальнейших исследований. В частности, предлагается подход к анализу функционирования областей эффективной маршрутизации как к передающим элементам с изменяемой пропускной способностью,
В пятой главе описываются численные эксперименты для получения характеристик алгоритма маршрутизации на неполных данных. Обосновывается выбор имитационных моделей и средств для моделирования. Производится сравнение некоторых важных свойств построенного алгоритма с аналогичными свойста алгоритма на основе SPF. Описаны основные задачи и цель моделирования. Описан численный эксперимент-Опытным путем получены параметры функционирования алгоритма на узлах сети. На основе полученных данных сделаны выводы об их согласованности с теоретическими положениями, приведенным в четвертой главе. Определяется область использования разработанного алгоритма.
В процессе работы над диссертацией, автор принимал участие в создании методической базы, для обеспечения учебного процесса по специальности 220400 [40,65» 82,91—93,111]. Разработанные программные
средства и методические материалы внедрены в учебный процесс и используются при проведении лаборторных работ по дисциплинам "Сети и телекоммуникации", ,тСети ЭВМ", "Сетевые технологии" для студентов специальностей 220400 "Программное обеспечение вычислительной техники и автоматизированных систем", 010200 "Прикладная математика" в СПбГЭТУ.
1. МЕТОДЫ МАРШРУТИЗАЦИИ В КОМПЬЮТЕРНЫХ
СЕТЯХ
В данной главе рассматриваются основные принципы маршрутизации, используемые в настоящее время для передачи информации в корпоративных сетях, производится их сравнительный анализ. Выявляются недостатки, используемых методов маршрутизации, а также предлагаются способы устранения этих недостатков.
Основные принципы маршрутизации
Маршрутизацией называют механизм, позволяющий осуществлять передачу пользовательской информации между конечными системами, расположенными в различных сегментах сети. Основными требованиями, предъявляемыми к этому механизму, являются обеспечение связности выбираемого пути между источником сообщения и адресатом, а также удовлетворение некоторому критерию качества, называемому метрикой [95,120]. Впервые, данная проблема в общем виде была сформулирована Беллманом в [41 в 1959 и в последствии развита Кантором (D. G. Cantor) и Гирла (М. Gerla), применительно к компьютерным сетям [8]- В механизмах маршрутизации необходимо уделять внимание следующим основным аспектам: способу представления информации о топологии сети, алгоритму поиска маршрута, оптимизации процесса передачи информации.
Существует множество различных классификаций стратегий маршрутизации. Фульц (Fultz G. F,) и Клейнрок (Kleinrock L.) выделяют стохастическую и детерминированную [15] маршрутизацию. Стохастическая предполагает лавинообразное заполнение сети сообщениями, которые всегда достигают адресата. С точки зрения надежности доставки -это наилучший способ обмена маршрутной информацией, однако использование такого подхода в сетях с большим количеством узлов приводит к значительным расходам на передачу служебного трафика. Методы стохастической маршрутизации изучались Боэмом (Bohem В, W.) и Мобли (МоЫеу R. L) и в настоящее время применяются в небольших сетях, для которых существуют временные ограничения на проведение административных работ [6]. Детерминированная маршрутизация определяется как выбор маршрутов между абонентами на основе фиксированной информации, которая не меняется при любых изменениях условий в вычислительной сети.
Далее, в связи с выработкой нового взгляда на вычисление маршрутов, появление которого было вызвано ростом сложности вычислительных сетей, Мак-Куиллон (McQuillan J. М.) и Рудин (Rudin Н.) вводят классификацию на основе принципа централизации управления. Они выделяют два класса стратегий маршрутизации; с централизованным управлением и с локальным (децентрализованным) [28,34]. Это ознаменовало появление качественно новой категории алгоритмов с распределенной процедурой поиска маршрутов.
Любой подход к управлению потоками информации в составных сетях подразумевает достижение следующих целей: во-первых, поиск непрерывных маршрутов, отвечающих выбранному критерию оптимальности, во-вторых, обеспечение адекватности информации о состоянии компонентов сети, на основе которой осуществляется этот поиск.
Перед тем как проводить анализ различных алгоритмов маршрутизации необходимо рассмотреть принцип оптимальности. В соответствии с этим принципом, если некоторый маршрутизатор В лежит на оптимальном маршруте от маршрутизатора А к С, тогда оптимальный маршрут от В к С совпадает с частью первого маршрута. Подробное доказательство этого принципа приведено в [114]. Прямым следствием из принципа оптимальности является возможность рассматривать множество оптимальных маршрутов от всех источников данных к приемникам в виде дерева, в корне которого располагается приемник. Обычно это дерево называют входным. Цель всех алгоритмов выбора маршрутов заключается в вычислении и использовании входных деревьев для всех маршрутизаторов. Следует отметить, что входное дерево не является уникальным, т. е. может существовать несколько входных деревьев для одной и той же сети. Вопрос о том, как получает маршрутизатор исходную информацию для вычисления входного дерева, является ключевым при анализе и построении алгоритмов маршрутизации.
Многие алгоритмы используют в своей работе концепцию кратчайшего пути в сети, где осуществляется поиск маршрутов. Необходимо отметить, что эта концепция [96,99,114] предполагает более широкую трактовку кратчайшего пути в графе, нежели просто количество транзитных переходов между узлами или физическую длину каналов связи. В наиболее общем случае, параметры дуг графа являются функциями расстояния, пропускной способности, средней загруженности, стоимости связи средней длины очереди, измеренной величины задержки или других факторов. Изменяя весовую функцию, алгоритм может вычислять кратчайший путь с учетом любого количества критериев в различных комбинациях.
В качестве показателя стоимости маршрутизации выступают метрики. Для некоторых методов маршрутизации метрики являются статическими величинами и не могут изменяться. В других случаях они могут назначаться администратором сети, либо вычисляться в процессе работы. Как правило, к метрикам относят следующие величины: длина маршрута в переходах между узлами (количество пересылок, hop), ширина полосы пропускания, задержка, надежность, нагрузка сети, стоимость связи.
Наиболее часто в качестве классифицирующих признаков используются: вид метрики, тип алгоритма, способ обмена служебной информацией. Все методы маршрутизации делятся на два класса - стохастические и детерминированные. В первом классе доставка сообщений осуществляется либо по случайным маршрутам (случайная стохастическая маршрутизация) либо по всем возможным маршрутам (лавинная стохастическая маршрутизация). Во втором классе выделяют статические методы, когда все маршруты жестко зафиксированы, и динамические, когда маршруты вычисляются в процессе работы и зависят от состояния сети в различные моменты времени. Далее, по типу алгоритма, можно выделить три основных группы: алгоритмы вектора дистанции (DV), учитывающие только количество переходов между узлами, алгоритмы состояния канала (LSA), учитывающие загрузку и работоспособность каналов связи и алгоритмы оптимизации потока по всей сети.
Маршрутизация в сети с динамической структурой
Для оптимизации сложных распределенных компьютерных сетей применяются методы многоуровневого управления, основой которых яв ляется идея декомпозиции и координации. В результате декомпозиции сложная сеть разделяется на группу более мелких подсетей с такой вза имосвязью, чтобы глобальная задача маршрутизации преобразовалась в группу локальных задач маршрутизации, т. е. отдельные решения бу дут приниматься по ограниченной информации, без использования всего объема сведений [11], Переход к иерархической структуре управления су жает в общем случае множество допустимых стратегий, ко одновременно снижает и уровень неопределенности, т. е, делает возможным получение ф более качественного решения. Ряд практических примеров доказывает эффективность локальной оптимизации для задач маршрутизации и оп 42 тимизации трафика. В [12] описаны эксперименты, в которых достигнуто значительное повышение эффективности процедуры маршрутизации по сравнению с процедурами глобальной оптимизации. Ряд исследователей 111,12] отмечают неэффективность протокола OSPF, рекомендованного Cisco в качестве базового протокола маршрутизации, в динамических и крупных сетях, использующего глобальную оптимизацию трафика. На основе натурного и имитационного моделирования доказано, что эффективность локального поиска оптимальной стратегии управления трафиком в такого рода сетях на 30-60% превосходит распределенный алгоритм SPF [29]. Предлагаемые в этих работах подходы обладают рядом недостатков. В [І2І, с одной стороны, предлагается специальный алгоритм формирования весовой функции для ребер OSPFs а с другой - отмечается принципиальная неспособность алгоритма SPF к гибкости в больших сетях. В [11] предложен оригинальный подход, который заключается в использовании имитационного моделирования локального поведения подсистемы управления трафиком для выбора весов протокола OSPF. Однако данный подход, как указывают сами авторы, применим только в некоторых случаях и, кроме того, требует наличия специализированного оборудования, что ограничивает его использование па уровне MAN - WAN,
Основной результат данных исследований показывает, что малые затраты на локальную оптимизацию дают значительный вклад в общую эффективность, в то время как небольшой дополнительный прирост этой эффективности требует существенных ресурсных затрат. На основе анализа попыток наделить алгоритм SPF новыми, идеологически нехарактерными для него, свойствами, наряду с доказательством эффективности локальной оптимизации можно сделать вывод о необходимости создания принципиально нового подхода к маршрутизации, который, с одной стороны, обеспечил бы эффективную локальную оптимизацию, а с другой - не требовал существенных затрат на глобальную синхронизацию знаний о состоянии сети. Динамика компьютерной сети существенным образом определяет свойства маршрутов: даже если в момент принятия решения о перенаправлении пользовательского трафика, маршрутизатор имеет точное представление о структуре сети и может получить оптимальный маршрут, то долговечность этого маршрута (время, в течении которого он остается оптимальным) невысока. С другой стороны, оперативно реагируя на изменения в структуре сети, можно снизить их влияние на качество полученного маршрута. Это позволяет говорить о том, что маршруты в динамической компьютерной сети являются динамическими.
Следует отметить, что при управлении реальными техническими системами более эффективным, но в то же время более трудоемким, оказывается управление на основе решения многокритериальной задачи, а не однокритериальной. Как правило, речь идет о нахождении состояния устойчивого равновесия в локальных подмножествах параметров и согласования (координирования) этих локальных решений для подсистем в рамках всей системы. В [37] проводится анализ и обобщение существующих алгоритмов координирования на основании понятия эффективности по Парето, суть которого сводится к необходимости использования небольшого числа наиболее значимых параметров для получения удовлетворительного результата и отбросу тривиальных, не вносящих существенного вклада в качество решения.
Одним из существенных достоинств решения многокритериальной задачи является тот факт, что в результате ее решения мы не получаем решение на границе какого-либо ограничения, т.е. по сути, в ряде случаев удается избежать генерации "узких мест", которые негативно отражаются на значительно снижают другие показатели режима работы системы, такие как надежность, оптимальность и т.д. Многокритериальная постановка задачи отличается большей близостью к реальной задаче и меньшей долей абстракции. Для реальных систем характерна зависимость выбора критерия (или группы критериев) оптимизации от окружающей среды и ряда других факторов т. е. в зависимости от ситуации должен проводиться выбор критерия (или вектора критерия) в процессе принятия решения оптимальным образом, а не вводится в систему жестко или волевым путем. Особо важное значение приобретают вопросы анализа зоны применимости различных критериев и выявления возможности решения одно-критериальных задач в частном случае. Поэтому становится возможным объективно провести выбор критериев по степени их применимости. Следовательно, метод оптимизации должен обладать достаточной гибкостью. Автором предпринималась попытки использовать идею о балансе факторов внешней среды и соответствующего состояния системы [83]. Однако, подход на основе эволюционного программирования [98], с использованием генетических алгоритмов и специального кодирования решения, показал его сложность и неэффективность, а главное - неустойчивость текущего уровня приспособленности популяции решений при наличии топологических изменений в сети.
Объем служебного трафика при маршрутизации с использованием неполных данных
В том случае, когда узел назначения находится вне ОЭМ (например узел Да), запускается распределенная процедура формирования маршрута и соответсвующие его участки формируют узлы-посредники.
Таким образом, каждый маршрутизатор будет осведомлен об изменении. Следует отметить, что скорость распространения маршрутной информации соответствует ее значимости для работоспособности алгоритма маршрутизации на узлах. Так узел Vj получает информацию о нарушении связности внутри R(VJ) немедленно и сразу же выполняет обновление, В отличие от узла Vj узел Vi узнает об изменении параметров маршрутов (которые были вызваны перераспределением нагрузки на каналы связи и узлы внутри R{VJ)) выполняя очередное обновление таблицы М. Адекватность знаний о топологии существенней, чем знания о нагрузке на каналы и узлы. Описанный подход позволяет при передаче данных от источника к получателю прогнозировать эффективность дальнейшей передачи, как бы "заглядывая вперед". С другой стороны, оперативность распространения маршрутной информации согласована с ее значимостью для узлов.
Важным критерием оценки эффективности алгоритмов маршрутизации является время сходимости алгоритма маршрутизации. Как правило под этим понимается время, необходимое для распространения информации о единичном изменении в структуре маршрутизируемой сети среди всех узлов и полной синхронизации маршрутных таблиц.
Для описываемого метода распространения сообщений об изменениях время сходимости внутри ОЭМ каждого узла значительно незначительно и реакция узлов на изменения происходит практически мгновенно (в силу небольших размеров ОЭМ). Этот эффект достигается за счет снижения времени сходимости по всей сети. Как было отмечено в гл. 2, в корпоративных компьютерных сетях более эффективным является достижение динамического равновесия локальных областей.
Объем служебного трафика - один из важнейших критериев оценки алгоритмов маршрутизации. В предлагаемом алгоритме весь служебный трафик можно разделить на две категории: обмен информацией об областях эффективной маршрутизации и обмен информацией об удаленных участках. По сути, точность и оперативность доставки информации второй категории не требуется, так как он используется лишь для определения наиболее выгодного направления дальнейшей передачи. Действительно, при изменении состояния некоторой удаленной подсистемы U(vi), зачастую, большинство маршрутов через R(vi) может быть восстановлено за счет имеющихся ресурсов и общее направление передачи пользовательского трафика не изменится. Если же потерян какой-либо "важный" элемент в рамках всей сети, то это повлечет серию отказов при попытке передать пользовательский трафик через области, неспособные его переработать. Эти отказы повлекут за собой массовые обновления внутренней маршрутной информацией, и если, это возможно, будет восстановлен новый режим передачи по потерянным направлениям, или, если это принципиально недостижимо, данное направление будет исключено из маршрутных таблиц.
Следовательно, при такой схеме реализации обмена маршрутной информацией, необходимо минимизировать внешний служебный трафик, так как он не может быть использован для восстановления работоспособности при отказах, так как не несет информации о связности участков сети. Распространение внешней маршрутной информации выполняется по таймеру, причем инициализирует процесс обмена узел, заинтересованный в получении такой информации. Далее рассмотрим некоторые характеристики внутреннего служебного трафика.
Узел Vit обнаружив изменение состояния Д(г ), вызванное потерей работоспособности некоторого и Є R(vi), рассылает об этом сообщение каждому Vj Є R{vi),i j. Далее, в зависимости от того, находится ли Vя в R(VJ) производится обновление R(VJ) и дальнейшая рассылка сообщения. Рассылка выполняется только для тех сообщений, которые несут информацию об элементах области эффективной маршрутизации того узла, который выполняет его передачу.
Утверждение ЗЛ. Радиус распространения сообщения об изменении при отказе в области К(УІ)_, инициированного узлом vi, не превосходит удвоенного значения R r где Rwa. = imx.Ry (ЗЛО) Пусть vm Є G узел, получивший сообщение. Для vm є R(vi) выполнение условия очевидно, поскольку d[vi,vm) Ri по определению. Пусть vm К{щ)7 тогда сообщение об обновлении поступает3 от некоторого узла Vj, такого что v ,vm Є R(VJ). Следовательно, расстояние d(v Vj) Rj и d(vj7vm) Rj). В свою очередь d(t u ) 7. В силу (3.6) d{vhvm) d{vhVj) +d(vj,vm) или с учетом (ЗЛО) d(vi,vm) 2 - R , Будем называть область, узлы которой задействованы в передаче сообщения при отказе зоной отказа. Радиус зоны отказа ограничен 2 Оценим скорость распространения сообщения об изменении при отказе внутри R(vi), При возникновении сбоя внутри R(vi) узел выполняющий маршрутизация от источника сразу запускает механизм обновления внутренних и внешних маршрутных таблиц, причем сразу после этого оповещает об этом все узлы находящиеся зоне отказа. Как показано выше максимальный радиус распространения не превышает 2 и следовательно время оповещения не превышает величины 2 - шах, где imax - время передачи сообщения по наиболее медленному каналу во всей сети. На этом распространение сообщения внутри зону отказа завершается.
Здлн доставки используется маршрутизация "от источника" Поступление новой информации во внешнюю, по отношению к зоне отказа область, определяется частотой срабатывания таймеров обновлений на узлах не принадлежащих этой области. По этой причине скорость распространения обновлений uf следовательно, объем соответствующего служебного трафика вне зоны отказа не зависят от интенсивности изменений, а определяется только значениями соответствующих таймеров на узлах сети, количеством узлов и размерами ОЭМ.
Предлагаемый подход к представлению маршрутной информации в крупных динамических сетях передачи данных имеет ряд преимуществ по сравнению с представлением в алгоритме SPF. Во-первых, трудоемкость сбора информации о топологии и свойствах сети, которая экспоненциально зависит от количества контролируемых сетевых элементов, может быть значительно снижена за счет управления размерами области эффективной маршрутизации. Во-вторых, качество маршрутной информации, используемой для поиска маршрутов во внутренней области, повышается, что позволяет использовать маршрутизацию от источника с высокой вероятностью успешной доставки, что влечет снижение нагрузки на промежуточные узлы. В-третьих, могут быть использованы независимые распределенные процедуры построения маршрутов внутри всей сети.
При использовании различного представления внешней и внутренней маршрутной информации необходимо определять специфические критерии выбора направления передачи трафика во внешнюю область. Эти критерии должны учитывать расстояние до узла-посредника во внутренней области, состояние и эффективность функционирования узла-посредника, расстояние до внешнего узла от узла-посредника, динамику маршрута от узла-посредника до узла назначения. Задачу выбора маршрута для внешней области можно рассматривать как задачу многокритериального выбора,
В процессе функционирования маршрутизаторы должны поддерживать следующие режимы: построение R(vi)t проверка состояния элементов й(г $), обновление при отказе R(VJ), обновление внешних данных R(vi), подготовка к сбросу R(vi). Для каждого из этих режимов работы предусмотрена соответствующая процедура в алгоритме маршрутизации. Для минимизации расходов на синхронизацию событий в системе необходимо использовать внешние источники точного времени.
Моделирование алгоритмов маршрутизации
Рассмотрим сеть, заданную на графе G(t), с алгоритмом маршрутизации с использованием неполных данных. Пусть в начальный момент времени все выбираемые маршруты являются оптимальными. Отказ может быть обнаружен в двух случаях; 1. При выполнении процедуры HELLO. 2. При транзитной передаче, т. е. выполнении маршрутизации в условиях случая 1 (см. п. 3.2.8).
Следовательно, что обнаружение отказа всегда будет происходить в области эффективной маршрутизации некоторого узла, который инициировал передачу данных по полному маршруту внутри R(vi), Следовательно, имеется полная информация о топологии и состоянии соответствующего участка сети.
Отказ обрабатывается по алгоритму, изложенному в п. 3.2.4, в результате работы которого обновляется информация о топологии во всех узлах, принадлежащих окрестности отказа. Окрестностью отказа Но будем называть подграф исходного графа G, в которую входят все узлы и соединяющие их каналы связи, которые содержали соответствующий отказавший элемент в своей топологической базе (М).
Рассмотрим, как влияет локальная процедура восстановления работоспособности на эффективность маршрутизации. Пусть некоторый узел VQ перестал участвовать в маршрутизации (фактически, исключен из G), тогда с одной стороны, топологически восстанавливаются (если это возможно) все pij, такие что VQ Є pij, а с другой - сбалансированная в начальный момент времени нагрузка па каждый канал перестала удовлетворять условию (3.2). Другими словами, обработка отказа осуще 97 ствляется поэтапно: сначала восстанавливается работоспособность путем обновления маршрутной таблицы MQ, соответствующего гг0, а затем перераспределяются нагрузки на каналы связи до удовлетворения условия (3.2). Очевидно, что выполнение первого этапа не превышает по времени opd? которое является временным интервалом между последовательными рассылками обновлений. Верхняя оценка времени перераспределения нагрузки составляет где RN - максимальный радиус сети; ijjg - максимальное значение таймера обновления среди всех узлов.
В зависимости от структуры G количество путей, эффективность доставки информации по которым снижается, может быть различным. Это снижение эффективности - плата за оперативное восстановление связности путей, содержащих щя Если допустить, что пропускная способность и пользовательский трафик распределен по сети равномерно, а также то, что вышедший из строя элемент не разрушает связность G, то потеря производительности по каждому каналу, в среднем, будет незначительной.
Построение каждого маршрута р,? это выбор альтернативы среди множества маршрутов в исходном графе G соединяющих узлы с идентификаторами г и j. Если бы все альтернативы были представлены точно, то они могли бы быть отсортированы по стоимости передачи информации по ним, что позволило бы осуществлять маршрутизацию от источника Б каждом узле (как это делается в протоколах маршрутизации на основе алгоритма SPF). В случае алгоритма АМНД, все альтернативы могут быть сгруппированы по классам с равным значением ц, (классам качества) и внутри каждого класса упорядочены по стоимости. В п. 3.2.6 было показано, что величина [і может являться функцией принадлежности маршрутной записи множеству достоверных (или надежных), тогда классы качества согласуются с разбиением соответствующего нечеткого множества по «-уровням. Принятие решения о выборе маршрута выполняется в два этапа: 1. Выбор непустого класса с максимальным значением ц. 2. Выбор альтернативы внутри данного класса с минимальным значением стоимости.
Задача оптимального способа формирования маршрутных записей по различным классам качества маршрутной информации - тема отдельного исследования. Однако, можно указать его основные направления. Во-первых, необходимо определить зависимость эффективности принятия решений при использовании маршрутных записей из различных классов. Во-вторых, изучение зависимости соотношения числа элементов каждого типа от параметров сети позволит создать механизм автоматического управления отбором альтернатив. В-третьих, на основе анализа сведений, получаемый с граничных маршрутизаторов об одних и тех же маршрутах, можно уточнять состояние внешней, по отношению к ОЭМ области.
