Содержание к диссертации
Введение
1. Анализ существующих технологий повышения производительности сетей передачи данных 10
1.1. Особенности построения сетей передачи данных, подходы к обеспечению качества обслуживания и повышению производительности сетей 11
1.2. Особенности работы протокола маршрутизации OSPF 16
1.3. Анализ особенностей самоподобного трафика 23
1.4. Постановка задачи исследований 30
Выводы по главе 31
2. Статистический анализ реализаций трафика на самоподобие 33
2.1. Описание реализаций трафика 33
2.1.1. Реализация трафика УГАТУ 33
2.1.2. Реализация трафика сети провайдера Уфанет 34
2.1.3. Реализация трафика Уфимского государственного колледжа радиоэлектроники. 35
2.1.4. Трафик беспроводного Интернет-провайдера 38
2.1.5. Тестовые реализации. 41
2.2. Расчет показателей Херста исследуемых реализаций 42
2.2.1. График Я/З-статистики 42
2.2.2. График изменения дисперсии 45
2.2.3. График структурной функции 46
2.3. Анализ статистических показателей исследуемых рядов 48
2.3.1. Плотность распределения вероятностей исследуемых рядов 48
2.3.2. Автокорреляционные функции исследуемых рядов 54
2.3.3. Энергетические спектры исследуемых рядов 56
Выводы по главе 58
3. Математическая модель процесса маршрутизации в пакетных сетях с учетом приоритета пакетов 59
3.1. Анализ современных подходов к задаче маршрутизации в сетях с коммутацией пакетов 59
3.1.1. Постановка задачи оптимального распределения потоков 62
3.1.2. Задача о динамической маршрутизации пакетов 65
3.2. Задача сравнения алгоритма распределения потоков с адаптивным алгоритмом маршрутизации для модели обслуживания трафика М/М/1 67
3.2.1. Решение задачи при одинаковых потоках в сети 67
3.2.2. Решение задачи при разных потоках в сети 74
3.3. Задача сравнения алгоритма распределения потоков с адаптивным алгоритмом маршрутизации для модели обслуживания трафика fbm/D/1 77
3.3.1. Решение задачи при одинаковых потоках в сети 78
3.3.2. Решение задачи при разных потоках в сети 83
Выводы по главе х 89
4. Моделирование работы адаптивного протокола маршрутизации с использованием фрактального фильтра предсказателя 90
4.1. Разработка фильтра предсказателя, учитывающего коэффициент самоподобия трафика 91
4.1.1. Постановка задачи прогнозирования интенсивности трафика в сетях передачи данных 91
4.1.2. Синтез оптимального фильтра 92
4.1.3. Имитационная модель фрактального фильтра 96
4.1.4. Оценка эффективности фильтра предсказателя 97
4.2. Моделирование процессов маршрутизации и передачи пакетов в сети 101
4.2.1. Моделирование работы сети с трафиком М/М/1 106
4.2.2. Моделирование работы сети с трафиком fbm/D/1 110
Выводы по главе 117
Заключение 119
Список использованных источников 121
Приложения 125
- Особенности работы протокола маршрутизации OSPF
- Плотность распределения вероятностей исследуемых рядов
- Задача сравнения алгоритма распределения потоков с адаптивным алгоритмом маршрутизации для модели обслуживания трафика fbm/D/1
- Моделирование процессов маршрутизации и передачи пакетов в сети
Введение к работе
Актуальность темы
В настоящее время операторы телекоммуникационных сетей расширяют зоны обслуживания, предоставляют новые виды сервисов на базе 1Р-телефонии, IP-TV, высокоскоростного доступа в Интернет с обеспечением высоких требований к качеству обслуживания - Quality of Service (QoS), что требует увеличения пропускной способности сети, использования высококачественного оборудования функционирующего на основе протоколов стека TCP/IP. Для обеспечения QoS может использоваться, дифференциальное или интегральное обслуживание, в основе которых лежат разделение трафика на классы приоритетного обслуживания и резервирование пропускной способности каналов. В связи с этим возникает задача более эффективного использования ресурсов сети.
Применяемые в IP-сетях протоколы динамической маршрутизации (OSPF, RIP, BGP) при определении эффективного маршрута следования пакетов учитывают либо пропускную способность каналов связи, либо количество узлов в маршруте, но не учитывают загруженность линий, т.е. при неизменной топологии сети маршруты не меняются. В таких случаях одни линии связи могут использоваться более интенсивно, чем другие, т.е. одни ресурсы сети работают с перегрузкой, другие при этом используются не эффективно. Для решения этих задач применяются методы трафик инжиниринга, которые позволяют за счет статического распределения маршрутов повысить эффективность работы сети, но при этом необходимо решать задачу оптимального распределения потоков. Другой подход - использование адаптивных алгоритмов маршрутизации, которые в процессе функционирования сети самостоятельно определяют маршруты в зависимости от загруженности линий связи.
До недавнего времени теоретическую базу для проектирования и моделирования систем распределения информационных потоков обеспечивала теория телетрафика, которая является одной из ветвей теории массового обслуживания, получившая свое развитие в работах ряда авторов: А. К. Эрланг, Л. Клейн-рок, Г. П. Башарин, А. Д. Харкевич, В. М. Вишневский и др. Наиболее распространенной моделью потока вызовов в теории телетрафика является стационарный пуассоновский поток, подходящий для сетей с коммутацией каналов. В работах зарубежных (W. Leland, D. Wilson, I. Noros) и российских исследователей (В. И. Нейман, Б. С. Цыбаков, О. И. Шелухин, B.C. Заборовский, А. Я. Городецкий) утверждается, что трафик в сетях с коммутацией пакетов обладает так называемым свойством «самоподобия». В результате теоретические расчеты характеристик современных систем распределения информации по классическим формулам дают некорректные результаты относительно длин очередей и времени задержек пакетов.
Таким образом, разработка моделей и алгоритмов маршрутизации учитывающих загруженность линий и самоподобие трафика является актуальной.
Целью исследований является:
Разработка метода адаптивной маршрутизации, позволяющего уменьшить среднюю задержку пакетов в сети на основе прогноза интенсивности трафика.
Для достижения поставленной цели необходимо решить следующие задачи:
На базе статистического анализа временных рядов, описывающих интенсивности и межкадровые интервалы трафика сетей передачи данных, установить наличие свойств стохастического самоподобия трафика сетей уровня распределения и оценить адекватность моделей трафика fbm/D/1 (интенсивность следования пакетов описывается фрактальным броуновским движением с постоянным временем обслуживания и одним обслуживающим прибором) и М/М/1 (интенсивность следования пакетов описывается пуассоновским потоком с экспоненциальным распределением времени обслуживания и одним обслуживающим прибором).
На основе свойства самоподобия временных рядов разработать цифровой фильтр-предсказатель интенсивности трафика, позволяющего скомпенсировать временные задержки распространения в сети служебных пакетов.
Разработать метод адаптивной двухпутевой маршрутизации, назначающий разные приоритеты пакетам, передаваемым по разным маршрутам.
Разработать методику расчета пороговых значений, для уменьшения средней задержки пакетов на основе предлагаемого метода адаптивной маршрутизации, с учетом приоритетов передаваемых пакетов.
Разработать имитационную модель сети передачи данных, для моделей трафика fbm/D/1 и М/М/1, позволяющей оценивать влияние временных задержек служебных пакетов на эффективность предлагаемого метода маршрутизации.
На защиту выносятся:
Результаты анализа временных рядов, описывающих интенсивности и межкадровые интервалы трафика сетей передачи данных на уровне распределения, по статистическим характеристикам и коэффициенту Херста.
Фильтр-предсказатель интенсивности трафика, позволяющий компенсировать задержки времени распространения служебных пакетов, в котором используются характеристики и свойства самоподобия предсказываемых рядов.
Метод адаптивной маршрутизации, основанный на использовании дополнительного маршрута, где пакеты, передаваемые по второму маршруту, получают низкий приоритет по сравнению с пакетами, для которых используемые каналы в маршруте являются основными.
Методика расчета пороговых значений для метода адаптивной маршрутизации с учетом двух приоритетов передаваемых пакетов для моделей
трафика М/М/1 и fbm/D/1.
5. Имитационная модель сети передачи данных для моделей трафика fbm/D/1 и М/М/1, позволяющая оценивать эффективность предлагаемого метода маршрутизации.
Научная новизна работы:
Разработан фильтр-предсказатель интенсивности трафика, на основе структурной функции предсказываемого ряда, который в отличие от авторегрессионных фильтров прогнозирует значения интенсивности трафика, используя свойства самоподобия трафика, что позволяет уменьшить погрешность предсказания при больших интервалах анализа.
Предложен метод адаптивной двухпутевой маршрутизации на основе сравнения длин очередей с заданными пороговыми значениями, который в отличие от методов маршрутизации, учитывающих задержки пакетов, меняет приоритет пакетов при передаче по дополнительному маршруту, что позволяет устранить циклическую смену маршрутов.
Разработана методика расчета пороговых значений длин очередей, на основе учета приоритетов передаваемых пакетов используемая в предлагаемом методе адаптивной маршрутизации, которая в отличие от традиционных подходов к решению задач теории телетрафика, использует модель трафика fbm/D/1, что позволяет уменьшить среднюю задержку пакетов.
Разработана имитационная модель сети передачи данных, на основе предложенного метода адаптивной двухпутевой маршрутизации, которая отличается от известных наличием элементов задержек и фрактальных фильтров-предсказателей, что позволяет оценить влияние задержек служебных пакетов.
Методы исследований. В работе использованы методы теории графов, теории случайных процессов, теории очередей. Применены методы математического моделирования, в том числе компьютерного.
Объект исследования. Методы маршрутизации в сетях передачи данных, модели трафика.
Предмет исследования. Методы разделения потоков нагрузки по двум путям, с учетом загруженности маршрутов и приоритетов пакетов.
Практическая ценность работы. Разработанная методика расчета задержек пакетов в сети может быть использована при проектировании и настройке мультисервисных сетей.
Апробация работы. Основные положения и научные результаты работы докладывались и обсуждались на следующих конференциях и семинарах: IV-VIII, X, XI Международной научно-технической конференции «Проблемы техники и технологии телекоммуникаций» (г. Уфа, г. Самара, 2003-2007, 2009, 2010); на VII Международном семинаре «Вычислительная техника и информационные технологии» CSIT (г. Уфа, 2005).
Публикации. Результаты диссертационной работы отражены в 12 публикациях, в том числе в 2 научных статьях в периодических изданиях из списка ВАК, в 10 материалах международных конференций.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и списка литературы, изложена на 129 страницах машинописного текста. Список литературы включает 50 наименований.
Особенности работы протокола маршрутизации OSPF
Сети, построенные на основе стека протоколов TCP/IP (сеть Интернет), делятся на автономные системы с целью обеспечения многоуровнего подхода к маршрутизации. Автономные системы соединяются внешними шлюзами или маршрутизаторами с внешним шлюзовым протоколом маршрутизации. В настоящее время таким протоколом является BGP (рисунок 1.3). Внешне шлюзовой протокол отвечает за выбор маршрута между автономными системами. Внутренние шлюзовые протоколы (внутридоменные) отвечают за маршруты внутри автономной системы [1, 3, 4].
Одним из распространенных протоколов внутридоменной маршрутизации является протокол OSPF (выбор кратчайшего пути первым) реализующий алгоритм состояния связей.
Для упрощения вычисления маршрутов и уменьшения размера базы данных состояния связей OSPF-система может быть разбита на отдельные независимые области (areas), объединяемые в единую систему особой областью, называемой магистралью (backbone). Области, не являющиеся магистралью, называются периферийными (рисунок 1.4). Маршруты внутри каждой области вычисляются как в отдельной системе: база данных состояния связей содержит записи только о связях маршрутизаторов внутри области, действие протокола затопления не распространяется за пределы области. Некоторые маршрутизаторы принадлежат магистрали и одной или нескольким периферийным областям. Такие маршрутизаторы называются областными пограничными маршрутизаторами (area border router, ABR). Каждая область должна иметь как минимум один ABR, иначе она будет полностью изолирована от остальной части системы. Областные пограничные маршрутизаторы поддерживают отдельные базы данных состояния связей для всех областей, к которым они подключены. На основании этих данных они обобщают информацию о достижимости сетей внутри отдельных областей и сообщают результат в смежную область. Также ABR обрабатывают подобные сообщения от других ABR (граничащих с другими областями) и ретранслируют информацию о внешних маршрутах, исходящую от пограничных маршрутизаторов (автономной) системы (ASBR). Тем самым обеспечивается передача маршрутной информации и коннективность между областями. При этом за пределы области передается не полная база данных состояния связей, а просто список сетей этой области, достижимых извне области через данный ABR, вместе с метриками расстояния до этих сетей. Если возможно, адреса сетей агрегируются в общий адрес с более короткой маской. Подобную же информацию, но только о сетях, лежащих за пределами OSPF-системы, распространяют ASBR.
После инициализации модуля OSPF через все интерфейсы, включенные в OSPF-систему, начинают рассылаться Hello-сообщения. Задача Hello-протокола - обнаружение соседей и установление с ними отношений смежности.
Соседями называются OSPF-маршрутизаторы, подключенные к одной сети (к одной линии связи) и обменивающиеся Hello-сообщениями.
Смежными называются соседние OSPF маршрутизаторы, которые приняли решение обмениваться друг с другом информацией, необходимой для синхронизации базы данных состояния связей и построения маршрутов. Другая задача протокола Hello - выбор выделенного маршрутизатора в сети с множественным доступом, к которой подключено несколько маршрутизаторов.
Hello-пакеты продолжают периодически рассылаться и после того, как соседи были обнаружены. Таким образом маршрутизатор контролирует состояниє своих связей с соседями и может своевременно обнаружить изменение этого состояния (например, обрыв связи или отключение одного из соседей). Обрыв связи может быть также обнаружен и с помощью протокола канального уровня, который просигнализирует о недоступности канала.
После установления отношений смежности для каждой пары смежных маршрутизаторов происходит синхронизация их баз данных. Эта же операция происходит при восстановлении ранее разорванного соединения, поскольку в образовавшихся после аварии двух изолированных подсистемах базы данных развивались независимо друг от друга. Синхронизация баз данных происходит с помощью протокола обмена (Exchange protocol).
Сначала маршрутизаторы обмениваются только описаниями своих баз данных (Database Description), содержащими идентификаторы записей и номера их версий, это позволяет избежать пересылки всего содержимого базы данных, если требуется синхронизировать только несколько записей.
Во время этого обмена каждый маршрутизатор формирует список записей, содержимое которых он должен запросить (то есть эти записи в его базе данных устарели либо отсутствуют), и соответственно отправляет пакеты запросов о состоянии связей (Link State Request). В ответ он получает содержимое последних версий нужных ему записей в пакетах типа «Обновление состояния связей (Link State Update)».
После синхронизации баз данных производится построение маршрутов, как описано в предыдущем разделе.
Каждый маршрутизатор отвечает за те и только те записи в базе данных состояния связей, которые описывают связи, исходящие от данного маршрутизатора. Это значит, что при образовании новой связи, изменении в состоянии связи или ее исчезновении (обрыве), маршрутизатор, ответственный за эту связь, должен соответственно изменить свою копию базы данных и немедленно известить все остальные маршрутизаторы OSPF-системы о произошедших изменениях, чтобы они также внесли исправления в свои копии базы данных.
Плотность распределения вероятностей исследуемых рядов
Стремительное развитие цифровых сетей, распространение оптоволоконных и беспроводных средств связи сопровождаются непрерывной сменой сетевых технологий. Однако, несмотря на достигнутый прогресс в теории проектирования телекоммуникационных систем, эта область в настоящее время оставляет широкий простор для разработки аналитических методов и подведения строгой теоретической базы для приближённых методик, реально используемых операторами и разработчиками. Такие методики во многом ещё являются эвристическими и опираются главным образом на интуицию и эмпирические исследования. Обладая определёнными преимуществами, эвристические методики и алгоритмы в большинстве случаев не позволяют оценить погрешности получаемых решений, обеспечить их общность (гарантировать отсутствие пропущенных решений), а также находить эффективные решения нестандартных задач. С этой точки зрения развитие аналитических подходов к моделированию сетевых процессов обладает значительной актуальностью, а полученные результаты - высокой значимостью.
В подавляющем большинстве случаев, согласно огромному количеству публикаций на данную тему, при аналитическом моделировании процесса передачи сигналов по сети производится переход из одной теоретической области (моделирование объекта) в другую (моделирование работы сети с этим объектом), что почти всегда лежит в сфере теории массового обслуживания. Причём зачастую с практической точки зрения исследования носят незаконченный характер — отсутствует обсуждение результатов по части их применения в сетевой практике. Безусловно, математические методы теории массового обслуживания являются весьма весомыми при разработке общей модели сетевых процессов, тем не менее результаты подобного моделирования должны применяться для поиска решений по построению, модернизации и оптимизации программно-аппаратных средств телекоммуникаций. Под последними следует понимать выбор (определение) физической архитектуры и логических топологических схем, типа маршрутизации, способов резервирования (в том числе буферизации) в случае имеющих место нарушений, и поиск решений других сетевых подзадач.
В соответствии с тематикой настоящей работы, посвященной изучению процессов в уже разработанных (уже эксплуатирующихся) сетях, к значимым сетевым подзадачам следует отнести задачу маршрутизации. Следует заметить, что вопросы резервирования, управления информационными потоками и им подобные, в той или иной мере связаны с проблемами маршрутизации. С представленной точки зрения разработка аналитических подходов к моделированию процессов маршрутизации является актуальной технической задачей.
Термин «маршрутизация» (Routing) в настоящее время имеет неоднозначное толкование. Согласно [1, 2, 4], под термином понимают: «Подсистему маршрутизации», «Протокол(ы) маршрутизации» и «Вычисление маршрута», т.е. способ поиска путиущя заданного пакета.
В функции подсистемы маршрутизации входит определение значений QoS-параметров, параметров трафика устанавливаемого виртуального соединения (в зависимости от типа режима продвижения пакетов: передача с виртуальным каналом или дейтаграмная передача), согласование и корректировка поступающего сигнала между его инициатором и администратором сети. Протокол маршрутизации предназначен для обмена информацией, необходимой для вычисления маршрутов [2, 3, 33]. Вычисление маршрута - это как раз и есть задача по определению пути, необходимому для передачи сигнала от источника к адресату. Так, под термином «маршрутизация» с точки зрения аналитического описания сетей следует понимать поиск пути для какого-либо заданного сигнала с выполнением топологических ограничений сети, требований трафика, QoS-параметров при удовлетворении критериев оптимальности (прежде всего, по эффективности сети).
Процедуры маршрутизации можно классифицировать на статические и динамические, последние могут быть адаптивными. В статических процедурах маршрут каждого пакета известен заранее до его входа в сеть, маршруты определяются и задаются администратором. Существуют: фиксированная (однопу-тевая), А:-путевая и альтернативная виды маршрутизации. В случае фиксированной маршрутизации от узла-источника к узлу-адресату используется единственный маршрут для передачи всего предназначающегося трафика, и задача сводится к выбору оптимального пути из всех возможных путей. При альтернативной (разветвлённой, многопутевой) маршрутизации предполагается возможность разделения передаваемого трафика на части с последующей передачей этих частей по различным каналам, что в более полной мере использует ресурсы сети. При Аг-путевой маршрутизации трафик передается по к путям [1,3, 13].
В динамических же процедурах маршрут заранее не известен, а на каждом узле направление дальнейшей передачи выбирается исходя из текущей информации, если эта информация о топологии сети (о наличии работоспособной линий связи), о пропускных способностях линий связи, о количестве узлов маршрутизации, то это динамическая процедура маршрутизации. Если при выборе маршрута используется информация о текущей загруженности линий связи, задержках, то это адаптивные процедуры маршрутизации [1,3].
К сожалению, в настоящее время отсутствует единая теория маршрутизации. Выбор маршрута в динамических процедурах осуществляется с использованием алгоритмов поиска кратчайшего пути графа, трафик сети при этом не учитывается. В статических процедурах маршрутизации необходимо решать задачу оптимального распределения потоков (алгоритм девиации потока). Для адаптивных алгоритмов анализ модели оказывается весьма затруднительным. Причина этих сложностей заключается в том, что в адаптивных алгоритмах процессы, описывающие поведение отдельных элементов сети, зависят от принимаемых в алгоритме решений по выбору направлений передачи, а решения эти принимаются с учетом текущего состояния элементов сети. Разомкнуть эту связь аналитическими методами оказывается крайне сложно [3, 34].
В силу этих причин для анализа алгоритмов маршрутизации задачу нахождения оптимального алгоритма чаще всего сводят к задаче оптимального распределения потоков. Однако заданному распределению потоков может соответствовать большое число алгоритмов маршрутизации [3].
Постановка общей задачи об оптимальном распределении потоков, согласно [13], может быть представлена следующим образом. Сеть передачи данных состоит из G узлов коммутации и В линий связи. Предполагается: 1) все линии абсолютно надежны и помехоустойчивы; 2) узлы коммутации имеют бесконечную память; 3) время обработки в узлах коммутации отсутствует; 4) длины всех сообщений независимы и распределены по показательному закону со средним 1/(0,; 5) трафик, поступающий в сеть, состоит из сообщений, имеющих одинаковый приоритет, и образует пуассоновский поток со средним значением у у [пакет/сек] для сообщений, возникающих в узле / и предназначенных узлу j, полный внешний трафик:
Задача сравнения алгоритма распределения потоков с адаптивным алгоритмом маршрутизации для модели обслуживания трафика fbm/D/1
На некоторых графиках можно наблюдать, особенно для а=\0, что вероятность появления обходного пакета уменьшается при увеличении у у/С и может уменьшаться при уменьшении Pi , это связано с расчетами коэффициента z, в основе которых решение задачи оптимального распределения потоков. Исходя из решения задачи, получаем, что при увеличении уу/С увеличивается доля отклоняемого потока, тем самым увеличивается вероятность превышения порога R. При значениях 0,5 - 0,7 коэффициента загрузки ууІС потока, подлежащего делению и увеличении Рг , доля отклоняемого потока уменьшается, при этом вероятность превышения порога D увеличивается быстрее, чем вероятность превышения порога R.
При сравнении полученных результатов по рисункам видно, что предла-гаемый в работе метод маршрутизации для моделей обслуживания в маршрутизаторах fbm/D/1 позволяет более эффективно использовать пропускную способность сети, чем при модели обслуживания М/М/1.
В результате анализа подходов к формализации процесса маршрутизации в пакетных сетях связи выявлено, что для нахождения оптимальных потоковых долей в статических алгоритмах маршрутизации и в задачах трафик-инжиниринга, а также для анализа динамических алгоритмов маршрутизции используется оптимальное распределение потоков при заданной входной нагрузке. Однако заданному распределению потоков может соответствовать некоторое число различных алгоритмов маршрутизации. Решение известной задачи оптимального распределения потоков приводится для модели трафика М/М/1.
При сравнении многопутевой, однопутевой и двухпутевой маршрутизации выявлено, что преимуществом обладает последняя. На этом основании и в результате анализа недостатков адаптивных алгоритмов маршрутизации предложен алгоритм маршрутизации, использующий два пути, определяемые алгоритмом кратчайшего пути в графе, при выполнении условий алгоритма пакеты идут по второму (обходному) с меньшим приоритетом.
На основе задачи сравнения потокового алгоритма и предложенного алгоритма маршрутизации, при моделях обслуживания трафика - М/М/1 и fbm/D/1, для полносвязной трехузловой сети выведено выражение для расчета параметров работы алгоритма, позволяющего уменьшать среднее время задержки пакетов. Определение условий, при которых алгоритм работает оптимально, в случаях, когда потоки трафика в сети одинаковые и когда разные.
В случае, когда потоки в сети одинаковые (обходной маршрут не используется по задаче оптимального распределения потоков), и модель обслуживания трафика - М/М/1 предложенный алгоритм позволяет проводить по обходному маршруту 0,01 часть потока при коэффициенте загрузки 0,25-0,55, при модели трафика fbm/D/1 на обходной путь может отклоняться от 0,1 до 0,5, при изменении коэффициента Херста от 0,6 до 0,9, при значениях коэффициента вариации 3 и 10. В случае, когда потоки нагрузки разные, модель трафика -М/М/1, вероятность появления обходных потоков составляет 0,1 (в случае максимального различия потоков). При модели трафика fbm/D/І вероятность появления обходных потоков может составлять 0,2 - 0,3 в зависимости от коэффициента Херста и коэффициента вариации.
Цель данной главы - апробация метода адаптивной маршрутизации, описанного в главе 3. Эффективность работы адаптивного алгоритма будет оцениваться сравнением с работой сети без адаптивной маршрутизации (без отклонения части потока по обходному маршруту) и с работой сети по алгоритму, отклоняющему пакеты по информации о текущей длине очередей в прямом и обходном маршрутах, позволяющему наиболее максимально использовать пропускную способность сетей [35]. Коэффициент использования пропускной способности сети можно оценивать по следующим параметрам: среднее время задержки, время задержки, доля отклоняемого потока, джитер - отклонение времени задержки от среднего.
Необходимо учесть, что при работе реальной сети алгоритм маршрутизации не может мгновенно адаптироваться под изменение ситуации в сети, возникает задержка вследствиевремени обмена служебными пакетами между маршрутизаторами. Предлагается скомпенсировать задержку за счет фильтра предсказателя,использующего свойства стохастического самоподобия трафика [3]. В данной главе предлагается решение задачи синтеза фрактального фильтра и оценка его работы. В архитектуру маршрутизатора необходимо включить фрактальный фильтр, который будет использоваться при работе предлагаемого адаптивного алгоритма маршрутизации (рисунок 4.1).
Актуальность постановки задачи прогнозирования и ее решение заключается в том, что данные прогноза о пропускной способности позволяют получить дополнительные сведения для решения задач управления, а имен-но: формирования алгоритмов предотвращения перегрузок, минимизации времени задержки прохождения пакетов и повышения эффективности использования пропускной способности сети. Решение указанной задачи сводится к определению алгоритма с механизмом перенастройки отдельных сетевых компонент. При прогнозе оценка процесса формируется на некотором интервале упреждения.
Пусть на отрезке времени [0,t] задано некоторое множество { i)} значений информационного потока, / - дискретные моменты времени, принадлежащие отрезку [0,t]. На основе данной информации требуется определить прогнозное значение jt+Я) информационного потока в будущий момент времени t+Я, где Я 1 (рисунок 4.2).
Моделирование процессов маршрутизации и передачи пакетов в сети
В данном опыте оптимальный алгоритм (метрика по длине очереди) отклоняет 5 % пакетов, уменьшает среднее и максимальное время задержки на 45 %. Исследуемый алгоритм отклоняет 4 % пакетов, уменьшает среднее время задержки на 25 %, максимальное время задержки меняется несущественно, введение в модель блоков задержки для сигналов управления и фильтров-предсказателей не меняет показателей среднего и максимального времени задержки (табіица 4.5).
Адаптивный алгоритм, дающий наибольший эффект, в данном опыте отклоняет 18 % пакетов потока ij , на 90 % уменьшает среднее время задерж-ки и на 70 % максимальное время задержки. Предлагаемый в работе алгоритм без фильтров-предсказателей отклоняет 14 % пакетов потока ij, на 84 % уменьшает среднее время задержки и на 65 % максимальное время задержки. Введение задержек для сигналов управления увеличивает среднее время задержки на 1 максимальное время задержки на 25 %. Включение фильтров предсказателей позволяет скомпенсировать задержки сигналов управления, число обходных пакетов такое же, как без блоков задержки, среднее время задержки не поменялось, улучшилось максимальное время на 8 % (таблица 4.6).
Опыт 4. Поток ij сформирован с использованием ряда - инт_укр2000, поток к/ - Ы, поток ik - al. Время моделирования - 450 единиц. Всего прошло пакетов потока ij - 535.
Адаптивный алгоритм, дающий наибольший эффект, в данном опыте отклоняет 9 % пакетов потока ij , на 73 % уменьшает среднее время задержки и на 40 % максимальное время задержки. Предлагаемый в работе алгоритм без фильтров-предсказателей отклоняет 5 % пакетов потока ij, на 50 % уменьшает среднее и максимальное время задержки. При введение задержек для сигналов управления среднее время задержки не меняется, максимальное время задержки увеличивается на 40 %. Включение фильтров предсказателей позволяет немного уменьшить максимальное время задержки.
По результатам опытов можно сказать, что исследуемый алгоритм дает долю отклонения потока, сравнимую с расчетными значениями полученными в главе 3 (см. рисунок 3.15). Однако результат оказывается хуже, чем результат алгоритма, работающего по метрике, учитывающей текущее значение длин очередей в прямом и обходном маршрутах, и по доле отклоняемого потока и по времени задержки, это можно объяснить тем, что в предлагаемом алгоритме оценка длины очереди и коэффициент загрузки усредняются за заданный интервал времени (10), для улучшения показателей можно ввести корректировку значения параметра D. Введение задержек для сообщений о длине очередей и коэффициентов загрузок незначительно увеличивают параметры времени задержки в пределах 5 - 12% (заметно увеличивается максимальное время задержки), что можно объяснить наличием персистентности в трафике. Применение фильтров-предсказателей позволяет скомпенсировать задержки служебных сообщений и улучшить время задержки на 1 - 5 %, при этом уменьшается джитер (по максимальному времени задержки). 1. Разработана модель фильтра-предсказателя, получено выражение импульсной характеристики, учитывающей свойства стахостического само подобия трафика, сетей передачи данных уровня распределения, позволяю щего вычислять прогнозируемое значение ряда на основе параметров этого ряда (дисперсия, коэффициент Херста), полученных на интервале упрежде ния. 2. Анализ моделирования работы фильтра, на основе сравнения относи тельной погрешности предсказания для исследуемых реализаций трафика, получаемых с помощью фрактального и автокорреляционного фильтров по казал, что погрешность предсказания, как для фрактального, так и для авто корреляционного фильтров на шаге предсказания 1-5 примерно одинаковая и составляет от 0,05 до 0,3 для рядов, обладающих свойством персистентности. Фрактальный фильтр имеет меньшую относительную погрешность, чем ав токорреляционный фильтр на достаточных интервалах упреждения (начиная с 40 - 50) и шаге прогнозирования 5-10. 3. Предложена структура и модель маршрутизатора, работающего с адаптивным алгоритмом маршрутизации, предлагаемого в данной работе, с использованием фрактальных фильтров-предсказателей, компенсирующих задержку служебных сообщений, позволяющего уменьшить среднее время задержки. 4. Проведен анализ эффективности работы разработанного адаптивного алгоритма маршрутизации, на основе сравнения результатов моделирования работы трехузловой сети с разными алгоритмами маршрутизации: однопуте-вой алгоритм без учета свойств трафика; двухпутевой алгоритм отклоняющий поток на основе текущих длин очередей в маршрутах; исследуемый двухпутевой адаптивный алгоритм маршрутизации без задержек служебных сообщений; с задержками служебных сообщений; с задержками служебных сообщений и фильтрами-предсказателями. При моделировании использовались модели трафика М/М/1 и fbm/D/1. Исследуемый двухпутевой адаптивный алгоритм маршрутизации с задержками служебных сообщений и фильтрами предсказателями отклоняет на 5 - 7 % пакетов меньше от расчетных значений полученых в главе 3, в 2 - 3 раза уменьшает среднее время задержки.
