Частотное планирование с двумя частотами, двумя частотными выходами и учетом загрузки в mesh-сетях Трушина Оксана Вячеславовна Научный руководитель: Вишневский В.М. (научно-производственная фирма ИНСЕТ) Москва 2010

2 Содержание Введение Введение Недостатки Недостатки Постановка задачи Постановка задачи Разработанный алгоритм Разработанный алгоритм Метрики Метрики Экспериментальные результаты Экспериментальные результаты Выводы Выводы

3 Введение Mesh - сеть: Mesh - сеть: Сценарий использования – транспортная сетьСценарий использования – транспортная сеть -Статичность -Потоковая передача -Плавное изменение интегральных характеристик трафика Доступ к среде - STDMAДоступ к среде - STDMA Полный дуплекс, 2 частотыПолный дуплекс, 2 частоты Распределение ресурсов – централизованный механизмРаспределение ресурсов – централизованный механизм

4 Недостатки Задержки при передаче данных низкий уровень качества обслуживания Задержки при передаче данных низкий уровень качества обслуживания Неравномерная загрузка сети угроза отказа узла Неравномерная загрузка сети угроза отказа узла Постановка задачи Разработать алгоритм частотного планирования: Разработать алгоритм частотного планирования: Выделение дополнительных ресурсов дискриминированному потокуВыделение дополнительных ресурсов дискриминированному потоку Балансировка нагрузки по узламБалансировка нагрузки по узлам

5 Терминология Mesh- сеть : Mesh- сеть : G=(V, E) и α: V {0,1}, - (u,v) != (v,u), - (u,v) \in E α(u) != α(v) Поток f sd = ( s, d, r, g ), s – узел-источник, Поток f sd = ( s, d, r, g ), s – узел-источник, d – узел-приемник, r – кол-во запрашиваемых ресурсов, g – кол-во выделенных ресурсов Коэффициент насыщения потока q: F R, q = g / r Коэффициент насыщения потока q: F R, q = g / r Дискриминированный поток f sd = f c min F ( q )Дискриминированный поток f sd = f c min F ( q ) Виртуальный путь – последовательность Виртуальный путь – последовательность { v 1, v 2 …v m }: существует k α(v k ) = α(v k+1 )

6 Структура алгоритма G 1 (V,E 1 ) f sd Нахождение U sd Для каждого элемента U sd Изменения цвета одной вершины Вычисление метрик Выбор оптимальной топологии G 2 (V, E 2 ) Трансформация G 1 (V,E 1 ) к G 2 (V, E 2 ) Обновление внутреннего хранилища данных

7 Метрики Уменьшение максимальной задержки Уменьшение максимальной задержки Параметры:Параметры: min F (q ) Балансировка загрузки сети Параметры: загрузка узла u(v i )=Σ j u j ; интерференция узла I(v i )=Σ j I j ; коэффициент связности conF(v i ) = количество связей узла/количество соседей Метрика μ(v i ) = u(v i ) + I(v i ) + 10*conF(v i ) - - μ(v) < μ(u) μ( v) лучше μ(u) Метрика m=avrg(μ(v i )) + maxDisp(μ(v i )) + 100*(1- min F (q )) m 1 < m 2 m 1лучше m 2

8 Экспериментальные результаты

9 Выводы В рамках работы над дипломным проектом был разработан и реализован алгоритм частотного планирования, который: В рамках работы над дипломным проектом был разработан и реализован алгоритм частотного планирования, который: Учитывает реальную загрузку сетиУчитывает реальную загрузку сети Не подвержен волновому эффектуНе подвержен волновому эффекту Позволяет использовать компромисс между временем работы и качеством, получаемых результатовПозволяет использовать компромисс между временем работы и качеством, получаемых результатов Реализованный алгоритм успешно интегрирован с алгоритмами, разработанными НПО «Информационные и сетевые технологии» для реализации протоколов, использующихся в высокоскоростных mesh-сетях Реализованный алгоритм успешно интегрирован с алгоритмами, разработанными НПО «Информационные и сетевые технологии» для реализации протоколов, использующихся в высокоскоростных mesh-сетях