Содержание к диссертации
Введение
Глава 1. Проблемы разработки алгоритмического обеспечения для маршрутизации беспроводных вычислительных сетей 12
1.1. Беспроводные вычислительные сети. Типы беспроводных локальных вычислительных сетей 12
1.2. Недостатки традиционных и актуальность разработки новых алгоритмов маршрутизации БЛВС 16
1.3. Анализ специализированных алгоритмов маршрутизации мэблвс 19
1.3.1. Проактивная или табличная маршрутизация 23
1.3.2. Иерархическая маршрутизация 26
1.3.3. Реактивная маршрутизация или маршрутизация по требованию 30
1.4. Актуальность проблемы обеспечения качества обслуживания данных в сетях мэблвс 36
1.5. Программные средства для моделирования беспроводных вычислительных сетей 38
1.6. Цель и задачи исследования 42
1.7. Основные результаты и выводы по главе 43
Глава 2. Задачи многокритериальной маршрутизации в сетях Мэ БЛВС 45
2.1. Построение графовой модели сети 45
2.2. Задача поиска маршрута с множественными ограничениями 50
2.3. Алгоритм поиска маршрута с двумя ограничениями 53
2.4. Алгоритм поиска маршрута с тремя ограничениями 56
2.5. Алгоритм поиска маршрута с множественными ограничениями при изменяющемся состоянии сети 62
2.6. Анализ эффективности разработанных алгоритмов 67
2.6.1. Анализ алгоритмов маршрутизации при использовании возможности поиска альтернативного маршрута 73
2.7. Основные результаты и выводы по главе 75
Глава 3. Реализация алгоритмов маршрутизации с поддержкой качества обслуживания в сетях МЭБЛВС 77
3.1. Приближенная сетевая модель МЭБЛВС 78
3.2. Алгоритм ко-маршрутизации от источника 81
3.3. Алгоритм ко-маршрутизации от адресата 86
3.4. Адаптация алгоритмов к изменяющейся топологии сети МЭБЛВС 91
3.4.1. Обнаружение нарушенных маршрутов 93
3.4.2. Поиск альтернативного маршрута 94
3.4.3. Восстановление нарушенного маршрута 96
3.5. Модификация предложенных алгоритмов 97
3.5.1. Локальная рассылка сообщений маршрутизации 99
3.5.2. Сбор информации о расстояниях 101
3.6. Анализ разработанных алгоритмов 103
3.7. Основные результаты и выводы по главе 107
Глава 4. Программное обеспечение для исследования моделей сетей МЭБЛВС 109
4.1. Подсистема редактирования модели 110
4.2. Подсистема прогона модели 112
4.3. Подсистема обработки результатов 116
4.4. Апробация разработанного программного пакета 118
4.5. Основные результаты и выводы по главе 119
Заключение 120
Список использованных источников 125
Приложение 1 137
Приложение 2 138
Приложение 3 139
- Недостатки традиционных и актуальность разработки новых алгоритмов маршрутизации БЛВС
- Алгоритм поиска маршрута с множественными ограничениями при изменяющемся состоянии сети
- Адаптация алгоритмов к изменяющейся топологии сети МЭБЛВС
- Локальная рассылка сообщений маршрутизации
Введение к работе
В настоящее время резко возрос интерес к беспроводным вычислительным сетям, в которых в качестве среды передачи используются радио или инфракрасные каналы. Во многих отраслях народного хозяйства наблюдается увеличение спроса на полностью мобильные портативные компьютеры, которые позволяли бы без наличия проводных соединений обмениваться информацией друг с другом и получать доступ к глобальной сети Internet. Так по данным агентства Gartner Dataquest [71] только для Европы прогнозируемый рост общего числа регулярных пользователей беспроводных вычислительных сетей вырастет к 2007г. до 10950000 человек.
Одним из наиболее актуальных и динамично развивающихся сегодня направлений в беспроводных вычислительных сетях является создание мобильных эпизодических беспроводных локальных вычислительных сетей (МЭБЛВС). Повышенный интерес к ним вызван, прежде всего, такими свойствами сетей МЭБЛВС, как простота организации и возможность свободного перемещения беспроводных узлов. Сеть МЭБЛВС может быть создана в считанные минуты, и включать в себя десятки, а то и сотни беспроводных узлов. Мобильные эпизодические беспроводные сети могут использоваться при проведении встреч или конференций, операций поиска и спасения людей, обмена информацией в критических условиях, например при стихийных бедствиях или при проведении военных операций [57,80,86,106].
Сети МЭБЛВС характеризуются отсутствием централизованного управления и, следовательно, каждый беспроводной узел в этой сети должен самостоятельно находить наилучший маршрут для передачи данных другим узлам. Возникает необходимость в использовании узлами соответствующих алгоритмов, называемых алгоритмами маршрутизации.
В процессе функционирования современных приложений, на алгоритмы маршрутизации ложится задача поиска таких маршрутов, которые удовлетворяют требуемым приложениями величинам пропускной способности, задержки и по-
терь пакетов. Данная задача в литературе описывается как задача качества об-
« служивания данных (QoS) [17,20,22,25].
Несмотря на достаточно большое количество существующих протоколов маршрутизации для МЭБЛВС, описанных в литературе [62,82,83,98,104,115,118], необходимо отметить, что нахождение маршрута в них сводится лишь к отысканию кратчайшего пути с обеспечением доставки данных только «по возможности». При этом передача данных приложений, чувствительных к величинам пропускной способности, задержки и потерь пакетов, становится практически невоз-можной. Применение же в сети МЭБЛВС традиционных протоколов маршрутизации, разработанных для проводных сетей [20,89,90], не эффективно, поскольку данный класс протоколов не предназначен для работы с изменяющейся топологией сети.
Все вышеперечисленное говорит об актуальности проблемы создания алгоритмического обеспечения для маршрутизации с поддержкой качества обслуживания данных в сетях МЭБЛВС. Специфические особенности, которыми обладают сети МЭБЛВС, обуславливают необходимость разработки алгоритмов маршрутизации, функционирующих при изменяющихся характеристиках и топологии сети.
Цель работы и задачи диссертации. Целью диссертационной работы является построение моделей сети МЭБЛВС с учетом особенностей данного вида сетей, создание алгоритмов маршрутизации с поддержкой качества обслуживания данных в сетях МЭБЛВС, разработка программного пакета имитационного моде-лирования сетей МЭБЛВС для оценки эффективности разработанных алгоритмов и последующая апробация полученных результатов в функционирующих сетях МЭБЛВС.
Для реализации поставленной цели необходимо последовательное решение следующих задач:
1. Создание и формализованное описание модели сети МЭБЛВС с обеспечением качества обслуживания и модели сети МЭБЛВС с учетом изме-няющихся характеристик и топологии.
Решение задач маршрутизации с множественными ограничениями на искомый маршрут.
Разработка алгоритмического обеспечения для маршрутизации с поддержкой качества обслуживания сетей МЭБЛВС.
Разработка программного пакета для исследования моделей сетей МЭБЛВС, позволяющего с помощью имитационного моделирования оценивать эффективность новых и существующих алгоритмов маршрутизации сетей МЭБЛВС.
Апробация разработанных алгоритмов в функционирующих сетях МЭБЛВС.
Методы исследований. В работе использованы методы теории множеств, теории алгоритмов, теории графов и комбинаторики и теории моделирования.
Апробация работы. Основные результаты работы докладывались и обсуждались на следующих конференциях: Всероссийская научно-практическая конференция «Российская школа и интернет» (Санкт-Петербург, 2001), Вторая Международная научно-практическая конференция «Моделирование. Теория, методы и средства» (Новочеркасск, 2002), Третья научно-практическая конференция "Современные средства и системы автоматизации" (Томск, 2002), Четвертая научно-практическая конференция "Современные средства и системы автоматизации" в рамках Всероссийского конгресса "Системы и средства автоматизации управления" (Томск, 2003), The IEEE-Siberian conference on control and communications «SIBCON-2003» (Томск, 2003).
По результатам работы имеется 10 публикаций, в том числе 7 статей.
Кратко изложим основное содержание работы.
В первой главе описываются типы беспроводных вычислительных сетей и особенности их функционирования. Формулируются проблемы разработки алгоритмического обеспечения маршрутизации сетей МЭБЛВС. Обосновывается неэффективность применения традиционных протоколов маршрутизации в сетях МЭБЛВС.
Приводится классификация существующих протоколов маршрутизации сетей МЭБЛВС и проводится анализ протоколов на предмет наличия в них слабых мест. Выявленные недостатки протоколов обобщаются, и показывается, что на сегодняшний день с помощью существующего алгоритмического обеспечения не решается задача обеспечения качества обслуживания данных. Приводится обоснование актуальности использования механизмов обеспечения качества обслуживания данных в сетях МЭБЛВС, и делаются выводы о необходимости разработки алгоритмов маршрутизации, позволяющих находить маршрут, отвечающий требованиям качества обслуживания.
Приводится обзор методов исследования сетей МЭБЛВС и программных пакетов, позволяющих осуществлять имитационное моделирование данного вида сетей. Делается вывод о том, что существующее программное обеспечение не является оптимальным для решения поставленных задач исследования сетей МЭБЛВС.
На основе результатов проведенного анализа существующего алгоритмического обеспечения для маршрутизации сетей МЭБЛВС, а также программного обеспечения для исследования моделей сетей МЭБЛВС, формулируются цель и задачи диссертационной работы.
Во второй главе рассматриваются задачи маршрутизации с множественными ограничениями. Предлагается графовая модель сети МЭБЛВС, допускающая применение схем обеспечения качества обслуживания. Описываются требования к метрикам, используемым при маршрутизации, а также типы приложений, чувствительных к данным метрикам.
Рассматривается задача маршрутизации с множественными ограничениями, и приводятся правила для композиции различного вида метрик, используемых этой задачей. Описывается разработанный алгоритм решения задачи маршрутизации для двух ограничений на искомый маршрут.
Приводятся типы приложений, чувствительных одновременно к трем метрикам, и описывается задача маршрутизации с тремя ограничениями на искомый маршрут. Вводится понятие смешанной метрики и предлагается способ для ее
расчета. Рассматривается разработанный алгоритм для решения задачи маршрутизации с тремя ограничениями и использованием смешанной метрики.
Рассматривается задача маршрутизации с учетом изменяющегося состояния сети и описывается разработанный алгоритм для поиска маршрута с двумя ограничениями при изменяющемся состоянии сети.
Приводится анализ эффективности алгоритма поиска маршрута с тремя ограничениями, на основе сравнения разработанного алгоритма с существующим алгоритмом, используемыми в современных сетях МЭБЛВС. Делаются выводы о зависимости степени эффективности алгоритмов от размеров сети. Приводится анализ эффективности алгоритмов с возможностью поиска альтернативного маршрута.
В третьей главе рассматривается реализация алгоритмов маршрутизации в сети МЭБЛВС. Предлагается приближенная сетевая модель МЭБЛВС, описываются основные предположения, относимые к модели и маршрутная архитектура модели.
Рассматриваются разработанные алгоритмы маршрутизации с поддержкой качества обслуживания, инициализируемые соответственно узлом-источником и узлом- адресатом.
Предлагаются способы адаптации разработанных алгоритмов к изменяющейся топологии сети МЭБЛВС. Описываются механизмы обнаружения и поиска альтернативных маршрутов при нарушении основного. Приводится разработанный алгоритм восстановления нарушенных маршрутов без полного перестроения уже существующих.
Предлагаются способы модификации разработанных алгоритмов с целью уменьшения количества служебных сообщений, генерируемых алгоритмами.
Приводится анализ разработанных алгоритмов и сравнение разработанных алгоритмов с учетом внесенных изменений.
В четвертой главе рассматривается создание программных средств для исследования моделей сетей МЭБЛВС.
Описывается структура разработанного программного пакета для исследования моделей сетей МЭБЛВС. Приводится описание разработанных подсистем редактирования модели, прогона модели и подсистемы работы с результатами прогона. Описывается апробация разработанного программного пакета, и приводятся примеры его применения.
Указывается, что алгоритмические и программные средства внедрены в ООО «Стек» и ООО «Томская транковая компания».
Научную новизну полученных в работе результатов определяют:
Приближенная сетевая модель, позволяющая учитывать особенности сетей МЭБЛВС и в том числе, динамически изменяющуюся топологию и характеристики сети.
Разработанные алгоритмы многокритериальной маршрутизации, находящие маршруты с накладываемыми двумя и тремя ограничениями на искомый маршрут. Разработанный алгоритм, позволяющий находить маршрут с двумя ограничениями при изменяющемся состоянии сети.
Разработанные алгоритмы маршрутизации сети МЭБЛВС, инициализируемые либо источником, либо адресатом, с учетом их последующих модификаций и адаптации.
Результаты анализа алгоритмов маршрутизации с помощью исследования на моделях сетей МЭБЛВС в разработанном программном пакете, позволяющие делать выводы об эффективности применения разработанных алгоритмов для маршрутизации сетей МЭБЛВС.
Практическая ценность и реализация результатов работы. Практически значимыми являются созданные модели, методы, алгоритмы и программные средства, позволяющие исследовать модели сетей МЭБЛВС. Программные средства функционируют на компьютерах типа IBM PC под управлением операционной системы Windows 2000. Объем исходного кода системы составляет более 8000 строк кода на языке Object Pascal.
Предложенные алгоритмы были внедрены в программное обеспечение для беспроводных систем, разрабатываемое в «Darim Vision Co. Ltd», что подтверждается соответствующим актом о внедрении.
Созданные программные средства и алгоритмическое обеспечение используются в работе сетевых департаментов ООО «Стек» и ООО «Томская транковая компания». Внедрение подтверждено соответствующими документами.
Личный вклад:
Постановка задач исследования и разработка графовой модели сети МЭБЛВС выполнена автором совместно с В.К. Погребным.
Формальное описание постановки задач маршрутизации с множественными ограничениями и описание алгоритмов для их решения с различными условиями выполнено лично автором.
Приближенная сетевая модель и алгоритмы} для маршрутизации сети МЭБЛВС разработаны лично автором. Постановка задач исследования эффективности предложенных алгоритмов и результаты исследования получены автором.
Разработка программного пакета для исследования моделей сетей МЭБЛВС выполнена лично автором.
Основные положения, выносимые на защиту:
Разработанные алгоритмы решения задач маршрутизации с множественными ограничениями позволяют находить маршрут с обеспечением качества обслуживания данных быстрее, чем алгоритмы, использующие последовательный поиск по каждому ограничению на маршрут (алгоритм ЗМ).
Созданная приближенная сетевая модель позволяет адекватно описывать процессы изменения топологии, происходящие в сетях МЭБЛВС.
Разработанные алгоритмы маршрутизации адаптированы к применению в сетях МЭБЛВС и позволяют находить маршрут с поддержкой качества обслуживания без дополнительных трат сетевых ресурсов.
11 4. Программный пакет для исследования моделей сетей МЭБЛВС позволяет
'# легко создавать модели при помощи визуальных компонентов и изучать работу
сети с помощью имитационного моделирования.
Автор выражает глубокую благодарность научному руководителю доктору технических наук, профессору В.К. Погребному за помощь в подготовке диссертационной работы, ценные замечания и советы. Автор также благодарит за плодотворные дискуссии доцентов Томского политехнического университета, кандидатов технических наук А.В. Кудинова, А.Ю. Демина и И.А. Ботыгина.
*
»
Недостатки традиционных и актуальность разработки новых алгоритмов маршрутизации БЛВС
Если при эксплуатации инфраструктурной БЛВС, все задачи по централизации и обслуживанию сети на себя берут точки доступа, то в случае использования эпизодических БЛВС возникает немало вопросов. На первом месте стоит необходимость поддержки мобильности узлов сети. Проблемной группой проектирования Интернет (IETF) была создана специальная рабочая подгруппа для изучения проблем мобильных эпизодических БЛВС — Mobile Ad hoc NETworks MANET [73]. В рамках работы группы MANET изучаются и стандартизируются предлагаемые исследователями решения задач, возникающих при эксплуатации МЭБЛВС.
Изначально предполагается, что сеть МЭБЛВС является одноранговой и канал связи может быть установлен напрямую между узлом-источником и узлом-адресатом при нахождении их в радиусе связи друг с другом. Однако в случае отсутствия прямой видимости узла-источника и узла-адресата используется многоступенчатая доставка информации через промежуточные узлы. Таким образом, возникает необходимость в маршрутизации передаваемых данных, т.е. нахождении пути от узла-источника к узлу-адресату и корректной доставки пакетов узлу-адресату. Для обеспечения доставки пакета адресату используется соответствующий алгоритм, называемый алгоритмом маршрутизации.
Определение 1.6. Согласно [13] алгоритмом маршрутизации мы будем называть правило, в соответствии с которым в каждом узле сети передачи данных осуществляется выбор линии связи для передачи данных. Под протоколом маршрутизации подразумевается стандартизированный для какого-либо вида сетей алгоритм маршрутизации или набор алгоритмов.
Под фиксированной (неразветвленной, однопутевой) маршрутизацией будем понимать такую процедуру выбора маршрутов, при которой для передачи данных от узла-источника узлу-адресату используется единственный маршрут[18]. Если в процедуре выбора маршрутов разрешается использовать более одного пути, то она называется альтернативной (разветвленной, многопутевой).
Существует достаточно большое количество алгоритмов маршрутизации, разработанных ранее для проводных сетей, основные из которых можно разделить на две группы: дистанционно-векторные алгоритмы (Di stance Vector Algorithms, DVA)[90] алгоритмы состояния связи (Link State Algorithms, LSA) [93] В алгоритмах дистанционно-векторного типа каждый маршрутизатор периодически широковещательно рассылает по сети вектор расстояний от себя до всех известных ему сетей. Под расстоянием обычно понимается число промежуточных маршрутизаторов, через которые пакет должен пройти прежде, чем попадет в соответствующую сеть. Может использоваться и другая метрика, учитывающая не только число промежуточных пунктов, но и время прохождения пакетов. Получив вектор от соседнего маршрутизатора, каждый маршрутизатор добавляет к нему информацию об известных ему других сетях, о которых он узнал непосредственно или из аналогичных объявлений других маршрутизаторов, а затем снова рассылает новое значение вектора по сети. В конце концов, каждый маршрутизатор узнает информацию об имеющихся сетях и о расстоянии до них через соседние маршрутизаторы. Наиболее распространенным примером, основанным на дистанционно-векторном алгоритме, является протокол RIP [89].
Алгоритмы состояния связей обеспечивают каждый маршрутизатор информацией, достаточной для построения точного графа связей сети. Все маршрутизаторы работают на основании одинаковых графов, что делает процесс маршрутизации более устойчивым к изменениям конфигурации. Широковещательная рассылка используется здесь только при изменениях состояния связей, что происходит в надежных сетях не так часто. Маршрутизатор периодически обменивается короткими пакетами только со своими ближайшими соседями, что не перегружает каналы связи служебными сообщениями. Пример использования алгоритмов состояния связей - протокол OSPF [93]. Однако, вышеперечисленные алгоритмы, хорошо зарекомендовавшие себя в проводных сетях, не пригодны для использования в МЭБЛВС. Вызвано это несколькими причинами.
Во-первых, динамически изменяющаяся топология сети. Поскольку узлы эпизодической сети могут постоянно перемещаться, алгоритм должен все время поддерживать адекватную информацию о местоположении и достижимости этих узлов. В эпизодической сети каналы связи возникают и уничтожаются непредсказуемо и хаотически. В традиционных алгоритмах маршрутизации подобные изменения спровоцируют поток служебных сообщений для составления нового графа связей сети. Конечно, в итоге, адекватная информация о сети будет собрана, но узлы же не стоят на месте, и поток служебных сообщений будет инициирован заново. Так может продолжаться бесконечно, пока хотя бы один из узлов находится в движении. Подобной ситуации не возникло бы, если бы при разработке данных алгоритмов учитывалась возможная мобильность узлов и динамическая топология.
Во-вторых, ограниченная пропускная способность беспроводной сети. Хотя максимальные скорости, заявленные для беспроводных сетей, составляют ИМбит/с для стандарта IEEE 802.11b [76] и 54мбит/с для IEEE 802.11а [74], это отнюдь не означает, что реальная пропускная способность всегда будет на максимальном уровне. Пропускная способность БЛВС зависит от таких факторов, как дальность связи, наличие помех в транслируемом диапазоне и препятствий на пути радиоволн. Также на пропускную способность влияет явление интерференции или наложения волн. Спецификациями предусмотрены более низкие скорости функционирования БЛВС, на которые устройства автоматически переходят при невозможности работы на более высоких скоростях.
Большой объем передаваемых служебных сообщений о структуре сети чреват снижением доли пользовательских данных в передаваемой информации, а то и вовсе передачей одной только служебной информации. В-третьих следует учесть тот факт, что некоторая часть беспроводных узлов являются портативными или переносными, следовательно, вычислительная мощность узла достаточно скромна, а источником питания служат аккумуляторные батареи. Стандартом ТЕЕЕ 802,11 [58,75] для экономии батарей предусмотрено нахождение сетевых устройств узлов в «спящем» состоянии, если нет необходимости передавать или получать данные. Однако, при перемещении узлов, не находящихся в режиме энергосбережения, генерируемая маршрутная информация заставит все узлы активно участвовать в процессе обмена сообщениями. В итоге, может возникнуть ситуация, когда пользовательское устройство не передав и не получив из сети никакой интересующей пользователя информации просто выключится от истощения заряда источника питания. Или же маломощное ЦПУ узла будет большую часть времени загружено обработкой служебных пакетов. В-четвертых, в БЛВС необязательно все каналы являются симметричными или двунаправленными. В традиционных протоколах маршрутизации проводных сетей для маршрутизации используется предположение, что если существует маршрут от узла А к узлу В, то обратный маршрут от В к А идентичен маршруту от А к В. В случае БЛВС, один из обменивающихся информацией узлов может находиться в более выгодных условиях, нежели другой, и, следовательно, направление канала связи будет однонаправленным. Различными исследователями было предложено множество алгоритмов, ориентированных на использование в беспроводных сетях [62,80-83, 98,104,115,118]. Рассмотрим более подробно основные и наиболее важные способы решения задач маршрутизации в сетях МЭБЛВС.
Алгоритм поиска маршрута с множественными ограничениями при изменяющемся состоянии сети
Таким образом, некоторые две вершины п и nv графа ГМСМ соединены дугой, т.е. (пц,Пу) = 1/ L, если представленный с их помощью канал связи является функциониругощим, пропускная способность канала связи отлична от нуля, а величина задержки не равна бесконечности.
Требования качества обслуживания будем рассматривать как набор ограничений, которые могут быть ограничениями канала связи или же ограничениями маршрута. Используемое для количественной оценки ограничения канала связи число, будем называть метрикой канала связи или ребра графа. Требования качества обслуживания для определенного маршрута, будут состоять из требований к каждому каналу связи, входящему в этот маршрут.
Используемые при нахождении маршрута метрики зависят, прежде всего, от характера применяемых пользователем приложений. Обычно это пропускная способность (мгновенная или средняя), задержка, вариация (дрожание) задержки, вероятность потери пакетов и т.п. Каждый класс приложений, отличается чувствительностью к определенной метрике или совокупности метрик. Например, приложения можно классифицировать по уровню чувствительности к величине задержки. В литературе [17,20,47], можно встретить классификацию основных типов приложений в порядке повышения чувствительности к задержкам пакетов.
Выделим пять видов приложений согласно чувствительности к задержкам: асинхронные - не чувствительные к задержкам, например, электронная почта; синхронные, чувствительные к задержкам, но допускающие их. Как пример можно привести передачу аудиоданных, требующих высокого качества воспроизведения; интерактивные, когда задержки будут заметны, но не отразятся негативно на процессе обмена информацией. Под этот вид приложений подпадают видеоконференции; изохронные приложения, обладающие порогом чувствительности, при превышении которого резко снижается функциональность приложения, например, голосовые данные; сверхчувствительные к задержкам приложения. К данному типу можно отнести приложения, управляющие каким-либо объектом в режиме реального времени или сетевые компьютерные игры. Приблизительная чувствительность к таким весовым функциям, как пропускная способность и задержка, на примере некоторых видов приложений показана на рис.2 Л.
При выборе используемых для маршрутизации метрик с множественными ограничениями, будем руководствоваться следующими правилами. Во-первых, для любой выбранной метрики, должны существовать эффективные и масштабируемые алгоритмы маршрутизации. Сложность используемого алгоритма маршрутизации не должна расти пропорционально размерам сети. Во-вторых, метрика должна отражать основные характеристики сети. Информация, которую содержит метрика, должна позволять обеспечивать основные требования качества обслуживания. Обратим внимание, что любые требования качества обслуживания должны быть отображены как выраженные в метриках ограничения на маршрут. Следовательно, используемые при маршрутизации метрики определяют те типы качества обслуживания, которые сеть может поддерживать. Например, если мы будем использовать в качестве метрик пропускную способность и задержку, все остальные требования качества обслуживания должны быть приведены к этим двум метрикам.
Допустимый маршрут - такой маршрут, который удовлетворяет накладываемым на него требованиям качества обслуживания. Основной функцией КО-маршрутизации является нахождение именно такого маршрута. Схему обеспечения условий качества обслуживания из конца в конец можно описать следующим образом. Когда вершина s хочет отправить данные с некоторым требованием качества обслуживания для маршрута к другой вершине t9 генерируется запрос на соответствующее соединение. Сначала система идентифицирует путь от s до /, который может удовлетворить требованиям качества обслуживания, и затем резервирует ресурсы по маршруту для установления соединения. Процесс идентификации маршрута отнесем к обязанностям КО-маршрутизации, а процесс резервирования - к механизмам сигнализации и резервирования ресурсов [54,84,86]. После того, как подключение будет установлено, узел s пошлет данные по новому маршруту к узлу t. Качество обслуживания данных будет гарантироваться найденными и зарезервированными ресурсами по всей длине маршрута.
Термин «состояние канала связи» будет использоваться для обозначения совокупности применяемых при маршрутизации характеристик канала связи.
Рассмотрим пример описания каналов связи с помощью определенных метрик качества обслуживания (КО-метрик). Например, на рис.2.2,, состояние канала связи описывается тройкой переменных, состоящей из пропускной способности, задержки и вероятности потерь пакетов.
Адаптация алгоритмов к изменяющейся топологии сети МЭБЛВС
Когда узел-адресат / получает сообщение маршрутизации, будем считать, что допустимый маршрут найден, и этот маршрут является тем, который уже пройден сообщением маршрутизации- Запись о пройденных узлах можно делать непосредственно в сообщении маршрутизации, В нашем случае, узел-адресат восстанавливает маршрут согласно списку узлов содержащихся в полученном сообщении.
Сообщение маршрутизации также накапливает суммарные метрики маршрута, который оно проходит. Если адресат получает несколько сообщений, то он выбирает маршрут с наименьшим показателем метрики, как, например, суммарной задержки. После выбора сообщения с наилучшими показателями, узел-адресат отправляет узлу-источнику сообщение подтверждения, резервирующее ресурсы по маршруту.
Но поскольку топология сети и доступность ресурсов постоянно изменяются, маршрут может быть нарушен или же промежуточный узел не будет обладать достаточными ресурсами в момент, когда получит сообщение подтверждения. В таком случае, сообщение будет возвращено обратно адресату и, в качестве маршрута, будет выбран маршрут из другого полученного сообщения маршрутизации. И источник и адресат используют время ожидания, для предотвращения бесконечного ожидания в случае потери сообщения маршрутизации. Но даже после того, как соединение установлено, и ресурсы зарезервированы, может произойти сбой маршрута в результате перемещения промежуточных узлов или их отключения. Рассмотрим возможные варианты решения данной проблемы.
Предположим, что каждый узел в сети поддерживает таблицу подключений, которая содержит запись для каждого подключения, проходящего через данный узел. Запись содержит входящий и исходящий канал связи, используемый проходящим подключением, Для определения того, по какому исходящему каналу послать входящий пакет, требуется произвести поиск в таблице подключений. Кроме того, в записях таблицы подключений хранится информация об узле-источнике, узле-адресате, зарезервированных ресурсах и другая полезная информация относительно подключения. Встречаемое в литературе [120] описание подобной таблицы подключений, использует для каждой записи термин «мягкий переход»- Если в течение некоторого периода времени информация о мягком переходе не обновляется, запись о нем удаляется из таблицы. В сетях МЭБЛВС данное действие актуально по следующим причинам. Поскольку топология сети изменяется динамически, маршруты могут быть разбиты на части, что делает информацию, хранящуюся в узлах устаревшей. Использование мягких переходов позволяет удалять устаревшую информацию и автоматически освобождать неиспользуемые сетевые ресурсы.
Сообщения обновления периодически посылаются по маршруту от узла-адресата к узлу-источнику [102]. Когда промежуточный узел получает сообщение обновления, он сбрасывает таймер соответствующего мягкого перехода и пересылает сообщение обновления дальше по направлению к узлу-источнику. При изменении топологии сети МЭБЛВС, установленные маршруты также могут быть нарушены. Возникает задача обнаружения и восстановления нарушенных маршрутов, Пусть s, /и Р, будут соответственно источником, адресатом и установленным маршрутом. Каждый узел і на маршруте Р, кроме узла s, имеет узла-предшественника. Точно так же каждый узел / на Р кроме t имеет узла-последователя. В сети МЭБЛВС, маршрут Р может быть нарушен по одной из следующих причин: 1, узел-источник s перемещается настолько далеко от узла-последователя, что канал связи между ними нарушается; 2, промежуточный узел і перемещается настолько далеко от узла-предшественника или узла-последователя, что связь между узлом / и узлом-предшественником или последователем нарушается. Заметим, что узел / имеет некоторый эффективный диапазон передачи. Если расстояние между узлом / и соседним с ним узлом становится больше данного диапазона, связь между этими узлами нарушается, поскольку соседний узел не получает больше сообщений от узла / ; 3. узел-адресат / перемещается настолько далеко от узла предшественни ка, что связь между ними нарушается; 4. любой из узлов составляющих маршрут Р покидает сеть МЭБЛВС. Для всех вышеперечисленных случаев будет предложено единственное ре шение, заключающееся в следующем. Если узел / не равный узлу-адресату t, с помощью протокола, находящего соседние узлы, обнаруживает, что его узел последователь долгое время не отвечает, і делает вывод, что маршрут Р нарушен на участке от него до его последователя. Наше решение строится на предположе нии, что каждый узел і поддерживает таблицу подключений описанную выше. Когда узел / обнаруживает, что соседний узел j больше не существует, следовательно, канал (ij) нарушен, узел помечает в таблице, что все подключения использующие канал также нарушены. Возникает задача нахождения альтернативного маршрута для передачи данных. При обрыве или нарушении существующего маршрута, необходимо найти способ передачи данных, либо обеспечив нахождение другого, альтернативного маршрута, либо восстановив существующий маршрут. Предположим, что сначала перед алгоритмом стоит задача нахождения маршрута, являющегося альтернативой нарушенному- Опишем данную задачу и ее решение применительно к разработанным алгоритмам.
Локальная рассылка сообщений маршрутизации
Первым шагом, для уменьшения избыточности сообщений маршрутизации, удалим ненужные сообщения, посылаемые обратно отправителю. Например, после получения узлому первого сообщения маршрутизации от /, узел/ не должен пересылать сообщение маршрутизации обратно к /, поскольку узел / в любом случае отбросит это сообщение маршрутизации.
Далее используем конкретизацию получателей сообщений маршрутизации. Локальная групповая рассылка, позволяет определить как получателей подмножество соседних узлов. В реализации беспроводного оборудования не существует аппаратной поддержки локальной групповой рассылки, следовательно, в дальнейшем мы будем упоминать подобный механизм рассылки в контексте его программной реализации. Рассмотрим узел /. Пусть набор получателей будет выражен как Rsi = {j J bandwidth(i,j) B,j соседи узла /}. Вместо того, чтобы посылать однонаправленное сообщение маршрутизации каждому узлу в Rst, і создает локальное широковещательное сообщение маршрутизации, обладающее дополнительное полем для хранения Rst.
Широковещательное сообщение рассылается по всем соседним узлам. Каждый соседний узел обрабатывает полученное сообщение и затем проверяет его на принадлежность к RsrB случае принадлежности к Rsi, получивший сообщение маршрутизации узел является предназначенным получателем, иначе, узел отказывается от дальнейшей рассылки сообщения маршрутизации. В результате, подобный подход должен экономить пропускную способность беспроводной сети, особенно учитывая то, что пропускная способность является, пожалуй, одним из самых серьезных факторов ограничивающих производительность всей системы в целом [79].
Оглядываясь на вышесказанное, следует учесть, что уменьшение количества рассылаемых сообщений не пропорционально изменению суммарного объема служебного трафика. Объясняется это следующей причиной: - при использовании локальной групповой рассылки, увеличивается размер каждого сообщения маршрутизации. Увеличение размера сообщения напрямую зависит от количества узлов в наборе Rsi. Кроме того, каждый соседний узел вынужден обработать увеличенные в размере сообщения и осуществить поиск для определения того находится ли он в наборе Rsf. Как следствие, затрачиваемое на обработку процессорное время также увеличивается.
Когда сообщения маршрутизации рассылаются от узла-источника до узла-адресата, можно их использовать для сбора полезной информации. Каждое сообщение маршрутизации дополнительно обладает полем, сохраняющим число узлов пройденных сообщением. Каждый узел і поддерживает кэш расстояний, состоящий из пар \j,dtJ\ где di} - аппроксимация расстояния между узлами і и j.
Предположим, что у узел-источник. При получении узлом і сообщения маршрутизации, возраст которого равен т, узел / узнает, что расстояние от него до узла-источника/ не более т. Если в кэше не существует пара w\rfiyV узел / помещает пару (j,m) в свой кэш. Если в кэше уже существует (j,d\ узел і сравнивает dtJnm. Если m меньше, чем d( J, пара lj\di}) меняется на [j\m). После прошествия определенного интервала времени, пара в кэше считается устаревшей и удаляется. При поступлении в узел-источник s запроса на подключение к узлу-адресату t, узел s ищет в кэше расстояний пару \t,dst). При существовании такой пары, узел s определяет значение поля TTL (Time То Live - время жизни) в сообщениях маршрутизации. Начальное значение для поля TTL равно dsi плюс небольшое целое число. Поле TTL определяет максимальный размер переходов между узлами, которые разрешается сделать сообщению. При получении узлом сообщения, он уменьшает поле TTL на одну единицу. Сообщение отбрасывается, если значение TTL становится нулевым. Следовательно, максимальный размер рассылки сообщений маршрутизации ограничивается полем TTL, позволяющим решить проблему с неограниченной рассылкой сообщений маршрутизации по сети. Иллюстрация показана на рис. 3,6, Предположим существование пары (/,3)в кэше расстояния узла s. Зададим полю TTL значение 3. Только 10 узлов, обозначенные закрашенными кружками на рисунке, перешлют полученные сообщения маршрутизации. Узел-адресат получит только одно сообщение маршрутизации.
