Адаптивная маршрутизация в сетях передачи данных с учетом самоподобия трафика
На правах рукописи
КОМИССАРОВ Аркадий Михайлович АДАПТИВНАЯ МАРШРУТИЗАЦИЯ В СЕТЯХ ПЕРЕДАЧИ ДАННЫХ С УЧЕТОМ САМОПОДОБИЯ ТРАФИКА Специальность 05.12.13 – Системы, сети и устройства телекоммуникаций
АВТОРЕФЕРАТ
диссертации на соискание ученой степени кандидата технических наук
Уфа – 2011
Работа выполнена на кафедре телекоммуникационных систем ФГБОУ ВПО «Уфимский государственный авиационный технический университет» д-р техн. наук, проф.
Научный консультант:
Багманов Валерий Хусаинович каф. телекоммуникационных систем Уфим ского государственного авиационного тех нического университета д-р техн. наук, проф.
Официальные оппоненты:
Карташевский Вячеслав Григорьевич каф. мультисервисных сетей и информаци онной безопасности Поволжского государст венного университета телекоммуникаций и информатики, г. Самара канд. техн. наук, Кобляков Андрей Владимирович ООО «ИМАКЛИК», г.Москва Уральский технический институт связи
Ведущая организация:
и информатики (филиал) ФГОБУ ВПО «Сибирский государственный университет телекоммуникаций и информатики», г. Екатеринбург
Защита состоится « 02 » декабря 2011 г. в 10 часов на заседании диссертационного совета Д 212.288. при Уфимском государственном авиационном техническом университете по адресу: 450000, г. Уфа, ул. К. Маркса,
С диссертацией можно ознакомиться в библиотеке университета
Автореферат разослан « 27 » октября 2011 г.
Ученый секретарь диссертационного совета д-р. техн. наук, проф. С.С. Валеев
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы В настоящее время операторы телекоммуникационных сетей расширяют зоны обслуживания, предоставляют новые виды сервисов на базе IP-телефонии, IP-TV, высокоскоростного доступа в Интернет с обеспечением высоких требо ваний к качеству обслуживания – Quality of Service (QoS), что требует увеличе ния пропускной способности сети, использования высококачественного обору дования функционирующего на основе протоколов стека ТСР/IP. Для обеспе чения QoS может использоваться, дифференциальное или интегральное обслу живание, в основе которых лежат разделение трафика на классы приоритетного обслуживания и резервирование пропускной способности каналов. В связи с этим возникает задача более эффективного использования ресурсов сети.
Применяемые в IP-сетях протоколы динамической маршрутизации (OSPF, RIP, BGP) при определении эффективного маршрута следования паке тов учитывают либо пропускную способность каналов связи, либо количество узлов в маршруте, но не учитывают загруженность линий, т.е. при неизменной топологии сети маршруты не меняются. В таких случаях одни линии связи мо гут использоваться более интенсивно, чем другие, т.е. одни ресурсы сети рабо тают с перегрузкой, другие при этом используются не эффективно. Для реше ния этих задач применяются методы трафик инжиниринга, которые позволяют за счет статического распределения маршрутов повысить эффективность рабо ты сети, но при этом необходимо решать задачу оптимального распределения потоков. Другой подход – использование адаптивных алгоритмов маршрутиза ции, которые в процессе функционирования сети самостоятельно определяют маршруты в зависимости от загруженности линий связи.
До недавнего времени теоретическую базу для проектирования и модели рования систем распределения информационных потоков обеспечивала теория телетрафика, которая является одной из ветвей теории массового обслужива ния, получившая свое развитие в работах ряда авторов: А. К. Эрланг, Л. Клейн рок, Г. П. Башарин, А. Д. Харкевич, В. М. Вишневский и др. Наиболее распро страненной моделью потока вызовов в теории телетрафика является стационар ный пуассоновский поток, подходящий для сетей с коммутацией каналов. В ра ботах зарубежных (W. Leland, D. Wilson, I. Noros) и российских исследователей (В. И. Нейман, Б. С. Цыбаков, О. И. Шелухин, В.С. Заборовский, А. Я. Горо децкий) утверждается, что трафик в сетях с коммутацией пакетов обладает так называемым свойством «самоподобия». В результате теоретические расчеты характеристик современных систем распределения информации по классиче ским формулам дают некорректные результаты относительно длин очередей и времени задержек пакетов.
Таким образом, разработка моделей и алгоритмов маршрутизации учиты вающих загруженность линий и самоподобие трафика является актуальной.
Целью исследований является:
Разработка метода адаптивной маршрутизации, позволяющего уменьшить среднюю задержку пакетов в сети на основе прогноза интенсивности трафика.
Для достижения поставленной цели необходимо решить следующие задачи:
1. На базе статистического анализа временных рядов, описывающих ин тенсивности и межкадровые интервалы трафика сетей передачи данных, уста новить наличие свойств стохастического самоподобия трафика сетей уровня распределения и оценить адекватность моделей трафика fbm/D/1 (интенсив ность следования пакетов описывается фрактальным броуновским движением с постоянным временем обслуживания и одним обслуживающим прибором) и M/M/1 (интенсивность следования пакетов описывается пуассоновским пото ком с экспоненциальным распределением времени обслуживания и одним об служивающим прибором).
2. На основе свойства самоподобия временных рядов разработать цифро вой фильтр-предсказатель интенсивности трафика, позволяющего скомпенси ровать временные задержки распространения в сети служебных пакетов.
3. Разработать метод адаптивной двухпутевой маршрутизации, назна чающий разные приоритеты пакетам, передаваемым по разным маршрутам.
4. Разработать методику расчета пороговых значений, для уменьшения средней задержки пакетов на основе предлагаемого метода адаптивной мар шрутизации, с учетом приоритетов передаваемых пакетов.
5. Разработать имитационную модель сети передачи данных, для моде лей трафика fbm/D/1 и M/M/1, позволяющей оценивать влияние временных за держек служебных пакетов на эффективность предлагаемого метода маршрути зации.
На защиту выносятся:
1. Результаты анализа временных рядов, описывающих интенсивности и межкадровые интервалы трафика сетей передачи данных на уровне распреде ления, по статистическим характеристикам и коэффициенту Херста.
2. Фильтр-предсказатель интенсивности трафика, позволяющий компен сировать задержки времени распространения служебных пакетов, в котором используются характеристики и свойства самоподобия предсказываемых рядов.
3. Метод адаптивной маршрутизации, основанный на использовании до полнительного маршрута, где пакеты, передаваемые по второму маршруту, по лучают низкий приоритет по сравнению с пакетами, для которых используемые каналы в маршруте являются основными.
4. Методика расчета пороговых значений для метода адаптивной мар шрутизации с учетом двух приоритетов передаваемых пакетов для моделей трафика М/М/1 и fbm/D/1.
5. Имитационная модель сети передачи данных для моделей трафика fbm/D/1 и M/M/1, позволяющая оценивать эффективность предлагаемого мето да маршрутизации.
Научная новизна работы:
1. Разработан фильтр-предсказатель интенсивности трафика, на основе структурной функции предсказываемого ряда, который в отличие от авторег рессионных фильтров прогнозирует значения интенсивности трафика, исполь зуя свойства самоподобия трафика, что позволяет уменьшить погрешность предсказания при больших интервалах анализа.
2. Предложен метод адаптивной двухпутевой маршрутизации на основе сравнения длин очередей с заданными пороговыми значениями, который в от личие от методов маршрутизации, учитывающих задержки пакетов, меняет приоритет пакетов при передаче по дополнительному маршруту, что позволяет устранить циклическую смену маршрутов.
3. Разработана методика расчета пороговых значений длин очередей, на основе учета приоритетов передаваемых пакетов используемая в предлагаемом методе адаптивной маршрутизации, которая в отличие от традиционных подхо дов к решению задач теории телетрафика, использует модель трафика fbm/D/1, что позволяет уменьшить среднюю задержку пакетов.
4. Разработана имитационная модель сети передачи данных, на основе предложенного метода адаптивной двухпутевой маршрутизации, которая отли чается от известных наличием элементов задержек и фрактальных фильтров предсказателей, что позволяет оценить влияние задержек служебных пакетов.
Методы исследований. В работе использованы методы теории графов, теории случайных процессов, теории очередей. Применены методы математи ческого моделирования, в том числе компьютерного.
Объект исследования. Методы маршрутизации в сетях передачи дан ных, модели трафика.
Предмет исследования. Методы разделения потоков нагрузки по двум путям, с учетом загруженности маршрутов и приоритетов пакетов.
Практическая ценность работы. Разработанная методика расчета за держек пакетов в сети может быть использована при проектировании и на стройке мультисервисных сетей.
Апробация работы. Основные положения и научные результаты работы докладывались и обсуждались на следующих конференциях и семинарах: IV VIII, X, XI Международной научно-технической конференции «Проблемы тех ники и технологии телекоммуникаций» (г. Уфа, г. Самара, 2003-2007, 2009, 2010);
на VII Международном семинаре «Вычислительная техника и информа ционные технологии» CSIT (г. Уфа, 2005).
Публикации. Результаты диссертационной работы отражены в 12 публи кациях, в том числе в 2 научных статьях в периодических изданиях из списка ВАК, в 10 материалах международных конференций.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и списка литературы, изложена на 129 страницах машинопис ного текста. Список литературы включает 50 наименований.
СОДЕРЖАНИЕ РАБОТЫ
Во введении обоснована актуальность темы, сформулирована основная цель работы, изложены основные положения, выносимые на защиту.
В первой главе анализируются механизмы и протоколы управления ин формационными потоками в пакетных телекоммуникационных сетях. Рассмат риваются методы, используемые для обеспечения передачи мультимедийного трафика с заданным качеством обслуживания (QoS), т.е. методы интегрального и дифференциального обслуживания. Приводятся описание и принцип дейст вия основных проколов маршрутизации, наиболее часто используемых в IP сетях. Выполнен анализ протокола OSPF – динамического протокола внутрен ней маршрутизации, который широко используется в настоящее время, прото кола адаптивной маршрутизации который использовался в первых пакетных сетях передачи данных ARPA, а также причин вызвавших отказ от использова ния адаптивных алгоритмов маршрутизации. Описан эксперимент в ходе кото рого выявлены задержки определения маршрутов протоколом OSPF.
Рассматриваются самоподобные случайные процессы, с помощью кото рых предлагается описывать трафик в современных сетях с коммутацией паке тов. Рассматриваются самоподобие, фрактальность, медленно и быстро убы вающие зависимости, коэффициент Херста, распределения с тяжелыми хвоста ми.
На основе анализа протоколов маршрутизации ставится задача разработ ки метода маршрутизации, позволяющего устранить недостатки существующих методов маршрутизации и снизить среднее время задержки пакетов в сетях пе редачи данных.
Во второй главе проводится анализ реализаций сетевого трафика, раз личными методами с целью выявления свойств стохастического самоподобия и определения модели трафика. Описывается процедура агрегирования, приведе ния реализаций сетевого трафика, к виду удобному для анализа. Оцениваются основные статистические характеристики временных рядов, описывающих ин тенсивность трафика и межкадровые интервалы, такие как среднее значение и дисперсия. Приводятся результаты расчетов плотностей распределения вероят ности, автокорреляционных функций, энергетических спектров. Оценивается коэффициент Херста. Полученные характеристики сравниваются с характери стиками тестовых рядов, полученных с помощью функций в математических пакетах Matlab и Mathcad (Гауссовский шум и фрактальное броуновское дви жение) Анализ гистограмм плотностей распределения вероятности позволяет сделать вывод о том, что исследуемые ряды подчиняются некоторому распре делению с «тяжелым хвостом», т.е. обладают высокой пачечностью. Для оцен ки подчинения распределения заданному закону использовался критерий Кол могорова – Смирнова, были предложены гипотезы о подчинении распределе ний законам: Гаусса, Вейбулла, Парето. Как показал выполненный анализ, большая часть исследуемых рядов подчиняется законам распределения либо Вейбулла, либо Парето, ряды с большим шагом агрегирования (3 секунды и более) и тестовые ряды подчиняются распределению Гаусса.
Результаты анализа автокорреляционных функций (АКФ) рядов, описы вающих сетевой трафик, подтверждают присутствие долговременной зависи мости для всех исследуемых случаев.
Анализ графиков спектральной плотности мощности (СПМ) показал, что для исследуемых рядов, вблизи нуля поведение кривых подтверждает присут ствие долговременной зависимости. Графики СПМ рядов межкадровых интер валов и рядов с минимальным шагом агрегирования содержат значительные со ставляющие с высокими частотами, что может свидетельствовать о наличии ан типерсистентности.
Оценка коэффициента Херста Н производилась тремя методами: по гра фику изменения дисперсии, методом R/S-статистики и по графику структурной функции. Для всех исследуемых рядов описывающих сетевой трафик коэффи циент Н 0,5 т. е. полученные реализации трафика можно отнести к классу процессов с длительной памятью.
При анализе распределения длительности кадров выявлено, что в сети чаще всего передаются кадры двух определенных размеров: либо с максималь ным, либо с минимальным размерами. Для описания модели трафика предлага ется длительность обслуживания кадра брать постоянной.
На основе выполненного анализа трафика предложено использовать в ка честве модели обслуживания трафика в узле коммутации систему fbm/D/1.
В третьей главе предлагается метод маршрутизации для выбора основ ного пути в области маршрутизации и дополнительного (если имеется возмож ность) на основе динамических алгоритмов маршрутизации. Часть пакетов по тока отправляют по дополнительному пути, они названы обходными, при этом их приоритет будет меньше, чем приоритет пакетов для которых каналы этого пути являются основными. Определяются параметры и условия работы алго ритма, при которых он позволит более эффективно использовать ресурсы сети.
Для анализа эффективности предлагаемого метода маршрутизации реша ется задача сравнения потокового алгоритма с адаптивным алгоритмом на трех узловой сети, для моделей трафика fbm/D/1 и M/M/1.
Рассматривается полносвязная трехузловая сеть с симметричными вход ными потоками ij = ;
i, j = 1 2, 3 и одинаковыми линиями связи с равными про пускными способностями – С. Предполагается, что входные потоки и длитель ность обслуживания по каждому ребру определяется моделью обслуживания fbm/D/1 или M/M/1.
При решении задачи оптимального распределения потоков среднее время доведения при оптимальном распределении потоков – T= 1/(С–), потоки на грузки пойдут по кратчайшим путям без использования обходных маршрутов.
В предлагаемом алгоритме маршрутизации часть пакетов каждого по тока направляется по обходному маршруту по следующему правилу.
Пусть nij(2) – число пакетов потока ij, стоящих в очереди на передачу в ка нал (линию) (i, j), а mij – число пакетов того же потока, находящихся в очередях обходного пути, т. е. в очередях каналов (i, k) и (k, j) (Далее будет употреб ляться термин «обходные» пакеты). Задаются два натуральных числа D и R – параметры алгоритма и через А обозначается следующее событие: в момент поступления пакета потока ij выполняется: nij(2) D, mij R. Таким образом, еcли в момент поступления пакета потока ij осуществляется событие А, то па кет посылается по обходному маршруту;
в противном случае, т. е. при вы полнении события A, пакет становится в очередь на передачу в канал (i, j).
Предполагается, что пакеты потока ij, находящиеся в очереди в канале (i, j), имеют более высокий приоритет перед пакетами других потоков (рисунок 1).
Приоритет 2 Приоритет поток ij поток ij i D R Приоритет j k i k j Приоритет поток ik поток kj поток ik поток kj Рисунок 1 – Схема работы алгоритма маршрутизации с использованием дополнительного пути с неприоритетным обслуживанием обходных пакетов Пусть Т(2) – среднее время доведения пакетов при использовании описан ного алгоритма маршрутизации, а Т(1) – среднее время доведения пакетов при использовании алгоритма направляющего пакеты по одному кратчайшему пу ти.
Необходимо показать, что для любого R 1 найдется такое D = D(R,, С), что верно неравенство T(2) T(1).
Для этого оценивается величина = T(1) – T(2).
Из формулы полной вероятности имеем:
((T (1) | A) (T ( 2) | A)) P( A) ((T (1) | A ) (T (2 ) | A )) P( A ) (1) P( A) ' P( A ) ' '.
Поскольку в любой момент времени в канале ij выполнено неравенство:
(1) ( 2) nij, то получается следующее неравенство (T(1)| A) P(A) D/C nij Значение (Т(2)| А) есть среднее время прохождения через сеть обходного пакета, которое складывается из двух величин: времени ожидания окончания периода занятости, образованного «прямыми» пакетами, и времени передачи с учетом возможных прерываний тех обходных пакетов, которые находятся в рассматриваемом канале в момент поступления отмеченного обходного пакета, включая и его самого.
Неравенство T(2) T(1) выполняется, если D выбрать следующим образом:
2(1 z ) 2 R D 1.
(2) (1 ) 2 (1 2 ) где – коэффициент загрузки создаваемый потоком (по условию задачи оди наковый), z – отношение низкоприоритетного обходного потока к приоритет ному потоку, для которого каналы составляют основной маршрут. Задавая па раметры регулирования R и D, можно отправлять часть пакетов по обходному пути, более равномерно загружая маршруты в сети, однако необходимо учиты вать вероятность события А, P(A) – вероятность того, что пакеты пойдут по об ходному пути. Для моделей M/М/1 вероятность того, что в системе будет нахо диться не менее чем D пакетов – D, а также вероятность, что в системе менее R пакетов – (1– R). Вероятность совместного наступления событий:
P(A) =(1– ikj Rk)·(1– ikj Rj)·ij D, (3) где Rk+Rj =R – параметр ограничения на число обходных пакетов в узлах k и j;
ikj = ikj·xэкв=z·ij·xэкв коэффициент загрузки неприоритетных пакетов, с учетом приоритетного потока, где длительность обслуживания неприоритетных паке тов xэкв соответствует циклу обслуживания (рисунок 2):
х xэкв, (4) (1 h. p. ) где.h.p. – коэффициент загрузки характеризующий обслуживание высокопри оритетных пакетов. Отсюда:
z ik ikj. (5) (1 ik ) Формула (3) с учетом (5) имеет вид:
Rj z kj Rk z 1 D P ( A) 1 ik ij. (6) 1 1 kj ik 1 p x хэкв p Рисунок 2 – Замена системы из двух очередей с приоритетами, системой без высокоприоритетных требований с заменой времени обслуживания не приоритетных требований эквивалентным временем обслуживания При решении данной задачи, когда потоки разные – ij ik=kj;
в форму лах необходимо рассчитать коэффициент z. Он определяется из решения задачи оптимального распределения потоков (рисунок 3).
f f С1 C2 = С C f i С1+С j f f C2 C3 f1 + f2 = f C1-(C1C2/2)0.5 C1+C Рисунок 3 – Схема задачи распреде- ления потока между Рисунок 4 – Оптимальные двумя путями на потоки f1 и f2, путевые потоки f1 и f Приравнивая производные времени задержек по потокам в путях, получа ем:
dT1 ( f1 ) dT2 ( f 2 ) dT3 ( f 2 ) С1 2C для М/М/1 (с учетом С2=С3).
(C 2 f 2 ) df1 df 2 df 2 (С1 f1 ) Отсюда определяются оптимальные потоки (Рисунок 4):
, C1 C2 2C1C2 C2 2C1 C1C f1 ;
(7) f C1 2C2 C1 2C где С2 определяется по формуле C2=C1(1–ik).
Коэффициент z определяется: z=1(ikj)/2(ik)=f2/2(ik).
Вероятность появления обходного пакета, характеризует эффективность применимости алгоритма (рисунок 5):
Rk Rj R D z (ik ) z ( kj ) ( ik ) D 1 z 2 ij z ( ik ) (8) P ( A) 1 2 C 1 (ik ) 1 ( kj ) ij 1 (ik ) 2 2 ) 2 ij C 2 (1 2 ) ( ik ) ( ik ) (1 2 где z.
( ik ) ( ik ) 1 2(1 2 ) Рисунок 5 – Графики зависимости вероятности появления обходного пакета для модели трафика M/M/1 от коэффициента загрузки создаваемого потоками приоритетных пакетов в обходном пути 2 ( i k ), коэффициента загрузки потока пакетов алгоритма без обходного пути ij/C и параметра R – ограничение на число обходных пакетов Для модели обслуживания трафика fbm/D/1 вероятность того, что в сис теме требований b больше, чем N:
2H 1 (1 H ) b 2 (1 H ) P (b N ) ~ exp, (9) 2a (1 H ) 2 H где Н – показатель Херста [0,5: 1);
a – коэффициент вариации (отношение с.к.о.
к среднему значению интервалов времени между пакетами) a 0.
Формула для среднего числа требований в системе:
1 H 2 (1 H ) (10) 1 H N (1 ) Производя необходимые замены в формулах для задачи с моделью М/М/1получаем выражения для параметров D и R:
(1 z 2 ) 2 H (1 H ) 2 H 2 (1 2 ) 2 H (1 H ) 2 H (1 2 ) exp R exp 3 2 H 2az 2 H 2 H 2a 2 H 2 H 2 (1 H ) 2 D 1 (1 2 ) 1 H Вероятность появления обходного пакета (рисунок 6):
1 ij (1 H ) 2H D 2(1 H ) P( A) ~ exp 2a ij (1 H ) 2 H (11) 2H (1 ikj )(1 H ) R 2 (1 H ) 1 exp.
2a ikj (1 H ) 2 H z ik где ikj ~.
2H 2 H 1 exp (1 ik ) (1 H ) 2a ik H 2 H Н=0,7 а=3 z=0,05 Н=0,6 а=3 z=0, Рисунок 6 – Графики зависимости вероятности появления обходного па кета от – коэффициента использования узлов, параметра R – ограничение на число обходных пакетов в очереди, разные графики зависимости от коэффи циента Херста – H, коэффициента вариации – a, коэффициент z – 0, При решении данной задачи, когда потоки разные – ij ik=kj;
в форму лах необходимо рассчитать коэффициент z. Он определяется из решения задачи оптимального распределения потоков.
Приравнивая производные времени задержек по потокам в путях, получа ем:
2 H 1 2 H f1С1 2(1 H ) 2( f 1 )C 2 2 (1 H ) 1 fC 1 ( f 1 )C 1 1 2 C f. (12) 2 C f H H 1 1 (1 H )(C 2 f 1 ) 1 H 1 H (1 H )(C1 f 1 ) Параметр С2 определяется как эквивалентная пропускная способность, с учетом того, что трафик описывается моделью fbm/D/1:
2H 2 H 1 exp (1 vp ) (1 H ).
С2 С1 (13) 2H 2a vp H Уравнение (12) решалось методом секущих в пакете Mathcad. Решение определяется при значениях коэффициентов загрузок потока подлежащего де лению ij: для Н=0,9 с 0,4 до 0,9;
для Н=0,6 с 0,5 до 0,9;
приоритетного потока 2(ik) с 0,05 до 0,55. Коэффициент вариации существенно меняет z (в 2–3 раза) при значениях 2(ik) больше 0,2.
H=0,7 a=3 R=4 H=0,6 a=3 R= Рисунок 7 – Графики зависимости вероятности появления обходного паке та от коэффициента загрузки создаваемого потоками приоритетных пакетов в обходном пути 2 ( i k ), коэффициента загрузки потока пакетов алгоритма без об ходного пути ij/C, параметра R – ограничение на число обходных пакетов в очереди, коэффициента Херста, коэффициента вариации.
Графики сравнивались при различных значениях коэффициента Херста (0,6;
0,7;
0,8;
0,9) и различных значениях коэффициента вариации (0,5;
3;
10).
При коэффициенте вариации а=3 и а=10, для разных значений коэффициента Херста можно подобрать значения R так, чтобы вероятность появления обход ных пакетов имела более равномерные значения, в таблице 1 представлены значения Р(А) в зависимости от заданного коэффициента Херста и подобран ного параметра R.
Таблица Зависимость вероятности появления обходного пакета Р(А) при подоб ранном параметре R в зависимости от коэффициента Херста и коэффициента вариации а a=10 a= Н R P(A) R P(A) 0,6 10–12 0,2–0,4 1, 2 0,1–0, 0,7 30–40 0,2 – 0,4 2, 3 0,15–0, 0,8 400–500 0,2–0,3 8–16 0,1– 0, 0,9 10 0,1–0,2 500–800 0,1–0, При сравнении полученных результатов по рисункам 5 и 7 видно, что предлагаемый в работе метод маршрутизации для моделей обслуживания в маршрутизаторах fbm/D/1 позволяет более эффективно использовать пропуск ную способность сети, чем при модели обслуживания трафика M/M/1.
В четвертой главе предлагается решение задачи по синтезу фильтра предсказателя интенсивности трафика с учетом свойств самоподобия трафика.
Представлена имитационная модель в пакете Мatlab трехузловой сети, исполь зуемая для оценки эффективности предлагаемого алгоритма маршрутизации Необходимо, чтобы информация о загрузки портов маршрутизаторов до ходила до регулятора потока своевременно, для этого необходимо прогнозиро вать интенсивность трафика. Пусть на отрезке времени [0,t] задано некоторое множество {(i)} значений информационного потока, i – дискретные моменты времени принадлежащие отрезку [0,t]. На основе данной информации требуется определить спрогнозированное значение (t+) информационного потока в бу дущий момент времени t+, где 1.
Известно, что оптимальным в смысле среднеквадратической ошибки предсказания является фильтр Колмогорова – Винера:
t (t ) h(i;
) (t i ), (14) i коэффициенты которого h(i;
) определяются из решения системы уравнений:
t h(i;
) R( i) R( ), 0, t, (15) i где R( ) – корреляционная функция случайного процесса (t).
Cтруктурную функцию процесса (t) можно представить в виде:
( (t ) (t )) 2 a 2 H. (16) Из соотношения (16) следует, что корреляционная функция будет опре делятся соотношением:
a R ( ) 2 2 H, (17) где 2 – дисперсия процесса (t).
При решении данной задачи выражение (14) принимает вид:
t* a 2 H (t ) (t ) 1 h (t ;
) (t )d. (18) 2 Первый член в выражении (18) может быть представлен в виде (t ) R( ), R(0) где R(x) – корреляционная функция процесса (t). Фильтр типа:
R ( ). (19) (t ) (t ) R (0) соответствует решению задачи прогнозирования стационарного случайного процесса по наблюдению этого процесса в момент времени t.
Эффективность работы фильтра предсказателя оценивалась по относи тельной ошибке предсказания:
~ (t ) (t ), (20 ) (t ) ~ где и – предсказанное и текущее значение ряда соответственно.
На рисунке 8 приведена гистограмма характеризующая относительные погрешности предсказания производимые фрактальным фильтром и автокорре ляционным фильтром на исследуемых рядах, для различных шагов предсказа ния =1;
=5;
=10. Каждый столбец представляет собой усредненную величину по интервалу. Погрешность предсказания для фрактального и автокорреляци онного фильтров для шага предсказания =1 и =5 примерно одинаковая и со ставляет от 0,05 до 0,3 для рядов обладающих свойством персистентности. Вы явлено, что фрактальный фильтр имеет меньшую относительную погрешность на достаточных интервалах упреждения (начиная с 40-50).
Рисунок 8 – График средней относительной ошибки предсказания в зави симости от шага предсказания, интервала анализа, используемого фильтра для различных реализаций трафика Для оценки эффективности работы предлагаемого метода маршрутизации в пакете Simulink/Matlab была разработана имитационная модель (рисунок 9) трехузловой сети, схема которой представлена на рисунке 1. Сравнивались сле дующие виды алгоритмов маршрутизации: однопутевой алгоритм без учета свойств трафика (алгоритм применяемый в рабочих сетях);
двухпутевой алго ритм отклоняющий поток на основе текущих длин очередей в маршрутах (при нимается за эталонный алгоритм);
исследуемый двухпутевой адаптивный алго ритм маршрутизации без задержек служебных сообщений;
исследуемый алго ритм с задержками служебных сообщений, исследуемый алгоритм с задержка ми служебных сообщений и фильтрами предсказателями. При моделировании использовались модели трафика М/М/1 и fbm/D/1.
По результатам опытов, проводимых на модели, можно сказать, что ис следуемый алгоритм дает долю отклонения потока, сравнимую с расчетными значениями полученными в главе 3 (рисунок 5, рисунок 7).
Однако результат оказывается хуже чем результат алгоритма, работаю щего по метрике учитывающей текущее значение длин очередей в прямом и обходном маршрутах, и по доле отклоняемого потока и по времени задержки, это можно объяснить тем, что в предлагаемом алгоритме оценка длины очереди и коэффициент загрузки усредняются за заданный интервал времени, для улучшения показателей можно ввести корректировку значения параметра D.
Введение задержек для сообщений о длине очередей коэффициентах загрузок незначительно увеличивают параметры времени задержки в пределах 5–12% (заметно увеличивается максимальное время задержки), что можно объясните наличием персистентности трафика. Применение фильтров предсказателей по зволяет скомпенсировать задержки служебных сообщений и улучшить время задержки на 1–5 %, при этом уменьшается джитер (максимальное время за держки).
Рисунок 9 – Схема имитационной модели трехузловой сети передачи данных Для трафика fbm/D/1 предлагаемый алгоритм маршрутизации в 2–3 раза уменьшает среднее время задержки, по сравнению с однопутевым алгоритмом маршрутизации. Для трафика М/М/1 предлагаемый алгоритм маршрутизации в 1,1–1,4 раза уменьшает среднее время задержки, по сравнению с однопутевым алгоритмом маршрутизации.
ОСНОВНЫЕ ВЫВОДЫ И РЕЗУЛЬТАТЫ 1. Установлено на основе исследования рядов, описывающих интенсивно сти и межкадровые интервалы трафика сетей уровня распределения, по стати стическим характеристикам и коэффициенту Херста, что трафик обладает свой ствами стохастического самоподобия. Исследование рядов показало, что при емлемой моделью трафика, сетей передачи данных уровня распределения явля ется – fbm/D/1, которая в отличие от традиционной для сетей связи модели трафика – M/M/1, позволяет адекватно оценивать задержки в сетях передачи данных.
2. Разработан фильтр-предсказатель интенсивности трафика, который, в отличие от авторегрессионных фильтров, при вычислении использует характе ристики и свойства самоподобия предсказываемого ряда. Это позволяет ком пенсировать задержки времени, возникающие при передаче служебных пакетов переносящих информацию состоянии сети (с относительной погрешностью 0,05 -0,2 для трафика обладающего свойствами стохастического самоподобия).
3. Разработан метод адаптивной двухпутевой маршрутизации на основе сравнения длин очередей в прямом и обходном маршрутах с заданными поро говыми значениями, где пакеты передаваемые по второму маршруту получают низкий приоритет по сравнению с пакетами, для которых используемые каналы в маршруте являются основными. Предложенный метод отличается от адаптив ного метода маршрутизации сети ARPA, пересчитывающего таблицу маршру тизации на основе изменения задержек пакетов имеющих одинаковый приори тет. Это позволяет устранить циклическую смену маршрутов.
4. Разработана методика расчета пороговых значений для предлагаемого метода адаптивной маршрутизации, на основе теории очередей с учетом двух приоритетов передаваемых пакетов для моделей трафика М/М/1 и fbm/D/1, по зволяющая уменьшить среднюю задержку пакетов в сети в 2–5 раз для трафика fbm/D/1.
5. Разработана имитационная модель сети передачи данных в пакете Mat lab, включающая разработанный метод адаптивной двухпутевой маршрутиза ции с использованием фрактального фильтра предсказателя, позволяющая мо делировать работу сети с различными алгоритмами маршрутизации и моделями трафика fbm/D/1, M/M/1. Это позволило оценить эффективность работы пред лагаемого метода маршрутизации, с учетом задержек служебных пакетов про токола маршрутизации и включением фильтров-предсказателей. Средняя за держка пакетов в сети уменьшается 2–3 раз для трафика модели fbm/D/1.
ОСНОВНЫЕ ПУБЛИКАЦИИ В рецензируемых журналах из списка ВАК 1. Модификация алгоритма адаптивной маршрутизации в корпоративных сетях передачи данных на основе вероятностного подхода / Султанов А.Х., Кузнецов И.В., Комиссаров А.М. // Инфокоммуникационные технологии: пе риодич. науч.-техн. и информ.-аналит. журнал. 2005. Том 3, №4. С. 35–38.
2. Прогнозирование телетрафика на основе фрактальных фильтров сети / Султанов А.Х., Багманов В.Х., Комиссаров А.М. // Вестник УГАТУ: научн.
журн. Уфимск. гос. авиац. техн. ун-та. 2007. Т.9, № 6(24). С. 217–221.
В других изданиях 3. Анализ пропускной способности в пакетных сетях с приоритетами / Комиссаров А.М. // Проблемы техники и технологии телекоммуникаций: Сб.
докл. IV Междунар. научн.-техн. конф. – Уфа, УГАТУ, 2003. С. 106–107.
4. Методы оценки пропускной способности в пакетных сетях с различ ными типами нагрузки / Комиссаров А.М. // Проблемы техники и технологии телекоммуникаций: Сб. докл. V Междунар. научн.-техн. конф. – Самара, ПГАТИ, 2004. С. 54–55.
5. Модификация алгоритма адаптивной маршрутизации / Комиссаров А.М. // Принятие решений в условиях неопределенности: Межвузовский сбор ник, часть 2. – Уфа, УГАТУ, 2005. С. 253–256.
6. Подход к расчету размера кадра в пакетных сетях связи для уменьше ния задержки передачи информации / Комиссаров А.М. // Проблемы техники и технологии телекоммуникаций: Сб. докл. VI Междунар. научн.-техн. конф. – Уфа, УГАТУ, 2005. С. 98–101.
7. Модификация алгоритма адаптивной маршрутизации в корпоративных сетях передачи данных / Султанов А.Х., Кузнецов И.В., Комиссаров А.М. // Компьютерные науки и информационные технологии (CSIT’ 2005): матер. VII Междунар. науч. сем. – Уфа, 2005, Т. 2. С. 260–262. (Статья на англ. языке) 8. Моделирование самоподобного трафика пакетных сетей передачи дан ных в среде GPSS / Комиссаров А.М. // Проблемы техники и технологии теле коммуникаций: Сб. докл. VII Междунар. научн.-техн. конф. – Самара, ПГАТИ, 2006. С. 104–105.
9. Постановка задачи для построения квазистатических адаптивных алго ритмов маршрутизации / Комиссаров А.М.// Проблемы техники и технологии телекоммуникаций: Сб. докл. VIII Междунар. научн.-техн. конф. – Уфа, УГАТУ, 2007. С. 116–119.
10. Расчет пропускной способности каналов низкоприоритетного тра фика в сетях с дифференциальным обслуживанием / Комиссаров А.М. // Про блемы техники и технологии телекоммуникаций: Сб. докл. X Междунар.
научн.-техн. конф. – Самара, ПГУТИ, 2009. С. 139–140.
11. Методы повышения эффективности использования пропускной способности каналов связи в пакетных сетях с дифференциальным обслужива нием / Комиссаров А.М. // Электронные устройства и системы: межвузовский научный сборник. – Уфа, УГАТУ, 2010. С. 172–178.
12. Задача сравнения потоковых и адаптивных алгоритмов маршрути зации для модели трафика fbm/D/1 / Комиссаров А.М. // Проблемы техники и технологии телекоммуникаций: Сб. докл. XI Междунар. научн.-техн. конф. – Уфа, УГАТУ, 2010. С. 74–78.
Диссертант Комиссаров А.М.
КОМИССАРОВ Аркадий Михайлович АДАПТИВНАЯ МАРШРУТИЗАЦИЯ В СЕТЯХ ПЕРЕДАЧИ ДАННЫХ С УЧЕТОМ САМОПОДОБИЯ ТРАФИКА Специальность 05.12.13 – Системы, сети и устройства телекоммуникаций АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Подписано в печать 24.10.2011. Формат 6084 1/16.
Бумага офсетная. Печать плоская. Гарнитура Times New Roman.
Усл.печ.л. 1,0. Усл. кр.-отт. 1,0. Уч.-изд.л. 0,9.
Тираж 100 экз. Заказ № ФБГОУ ВПО Уфимский государственный авиационный технический университет Центр оперативной полиграфии 450000, Уфа - центр, ул. К. Маркса,