Исследования процесса маршрутизации в вычислительных сетях с использованием гибридной сети

В настоящее время широко используются сети с коммутацией пакетов, в которых применяются маршрутизаторы для определения маршрута передачи данных. Известные алгоритмы маршрутизации не всегда обеспечивают желаемые показатели: задержка пакетов, скорость передачи, стоимость, надежность.

В нашей работе проведены исследования по улучшению алгоритмов маршрутизации с использованием гибридных сетей, в которых совместно применены методы нечеткой логики и нейросетей.

Выбор маршрута, в свою очередь, включает в себя две задачи: определение маршрута и оповещение сети о выбранном маршруте.

Процедура маршрутизации сообщений включает правила выбора набора узлов, через которые сообщение пройдет по сети к получателю. Процедура выбора маршрута определяется алгоритмом, в котором используются следующие параметры: место возникновения и назначение сообщения, приоритет сообщений, возможность использования определенных каналов, их перегрузка или отказ от них. Возможны четыре стратегии маршрутизации:

• -    выбор единственного пути по критерию минимальной оценки пути;

• -    использование одного или нескольких маршрутов с одинаковыми оценками, которые являются минимальными для заданной сети;

• -    распределение пакетов по возможным маршрутам между заданной парой узлов с вероятностью, обратно пропорциональной длине выбранного маршрута;

• -    распределение пакетов данных по кратчайшим маршрутам с вероятностью, обратно пропорциональной длине данного маршрута.

Будем сравнивать гибридную сеть с традиционной по критерию загруженности сети. Для количественной оценки предлагаемых алгоритмов необходимо смоделировать две сети: традиционную и гибридную. Начнем с традиционного варианта.

В модель сети включаем узлы сети (коммутаторы и маршрутизаторы, для которых определены протоколы), компьютеры, соединения между узлами. В нашем случае применим протокол Ethernet со скоростью прохождения 10 Мбит/С и 100 Мбит/С согласно рис. 1.

Рис. 1. Смоделированная сеть

В настоящее время Ethernet – самая распространенная технология локальных сетей на сегодняшний день. В широком смысле это семейство технологий, в которое входит фирменный стандарт Ethernet DIX, IEEE 802.3 Ethernet 10 Мбит/С, Fast Ethernet, Gigabit Ethernet и 10G Ethernet [4].

В технологии Ethernet используется дейтаграммная коммутация пакетов. Кадр имеет фиксированный формат и наряду с полем данных содержит различную служебную информацию. Адрес Ethernet является плоским числовым адресом, иерархия не используется. Адаптеры Ethernet работают с тактовой частотой 20 МГц, передавая в среду прямоугольные импульсы, соответству- ющие нулям и единицам данного компьютера. Передача кадров идет с постоянной скоростью 10 Мбит/С, она и определяет пропускную способность Ethernet. Для повышения надежности передачи данных Ethernet использует подсчет контрольной суммы и передает ее в конце кадра [3]

Рассмотрим пять маршрутизаторов, расположенных по графам вершин, и серверы на одном и другом конце сети (см. рис. 1). Маршрутизаторы и серверы используем по умолчанию настройками. Для исследования традиционной сети применим программу OPNET [5].

На выбранный критерий оптимизации сети влияет большое количество параметров различных типов. В наибольшей степени на загруженность сети влияют:

• -    используемые коммуникационные протоколы и их параметры;

• -    доля и характер широковещательного трафика, создаваемого различными протоколами;

• -    топология сети и используемое коммуникационное оборудование;

• -    интенсивность возникновения и характер ошибочных ситуаций;

• -    конфигурация программного и аппаратного обеспечения конечных узлов.

При номинальной пропускной способности протокола Ethernet 10 Мбит/С биты внутри кадра передаются с интервалом в 0,1 мкС; время передачи одного кадра минимальной длины составляет 57,6 мкС. Эффективная пропускная способность протокола Ethernet при использовании кадров минимальной длины составляет 46-8/67,2 = 5,48 Мбит/C [3]. При моделировании через сеть пропускается 100 или 300 пакетов с усредненной длиной пакета 763 байта. При 100 пакетах количество бит информации, которое пройдет по сети, вычисляется как 100-763-8=610400 бит [5]. Результат моделирования в OPNET демонстрирует рис. 2.

Рис. 2. Сеть с нагрузкой 100 пакетов

Проанализировав работу сети со 100 пакетами, мы видим, что ее загруженность по всем направлениям достаточно мала: на всех участках она практически одинакова в пределах от 3,3% до 13,4% (расхождения по загрузке происходят ввиду разной скорости прохождения по сети). Можно сделать вывод, что при малой или средней нагрузке маршрутизатор работает стабильно, то есть успевает распределять пакеты по сети согласно таблице маршрутизации без коллизий. Протокол Ethernet в этом случае работает эффективно (см. рис. 3). Критических участков не наблюдается.

Рис. 3. Сеть с загруженностью участков

Программа OPNET позволяет продемонстрировать производительность сети и передачу информации графически (см. рис. 4): как мы видим, загруженность сети в данном случае составляет максимально 20% при скорости передачи 2 Мбит/С.

Рис. 4. Загруженность сети и ее пропускной способности

Увеличим количество информации, проходящей через сеть, до 300 пакетов. Используем формулу 300-763-8=1831200 бит.

Рис. 5. Сеть с нагрузкой 300 пакетов

Как видно из рис. 5, при изменении нагрузки на сеть до 300 пакетов нагрузка на участки сети становится неравномерной. Появляются критические участки, в нашем случае это участок между узлами 2_node и 3_node, где нагрузка на сеть доходит до 95 %. На участке между 0_node и router загрузка не превышает 40%, а между сервером и router 12%.

Рис. 6. Загруженность сети на участках router – 1_node и 2_node – 3_node

На участке 2_node – 3_node скорость передачи информации максимальна (см. рис. 7). По результатам моделирования видно, что сеть работает нестабильно. Пакеты начинают скапливаться на участке 2_node – 3_node. Хотя на всех остальных участках сети работа стабильна. Следует разгрузить этот участок. Маршрутизатор направляет пакеты согласно данным таблицы маршрутизации, и поэтому даже в такой маленькой сети при максимальной нагрузке происходит дестабилизация.

Рис. 7. График скорости передачи информации на участке 2_node – 3_node

Результаты исследования показывают, что таблица маршрутизации не всегда работает эффективно, сеть загружена неравномерно. Распределение пакетов по сети не всегда предсказуемо и может быть просчитано. После исследования стандартной сети при минимальной и максимальной загруженности можно сделать выводы: во-первых, при максимальной загруженности один участок начинает работать нестабильно, хотя все остальные участки загружены на 30… 40 %; во-вторых, при передаче информации не учитывается ее важность. Поэтому необходим алгоритм маршрутизации пакетов, учитывающий следующие параметры: приоритет сообщений, возможность использования определенных каналов, перегрузку сети, время прохождения пакета. Для этого нужно разработать алгоритм, использующий гибридную сеть.

Реализуем модель, ориентированную на решение задачи «проникновения» из пункта отправления в пункт назначения кратчайшим или менее загруженным доступным путем, то есть за минимально возможное время. Структуру возьмем такую же, как и у модели традиционной сети (см. рис. 1).

Определим правила, которые задают связь входных переменных с выходными. Для исследования алгоритма маршрутизации необходимо выделить наиболее значимые этапы работы сети. Входными переменными будем считать количество переходов (k), пропускную способность сети (t), выходной переменной функцию время прохождения пакетов (g).

При описании объектов и явлений с помощью нечетких множеств используется понятие нечеткой и лингвистической переменных [2].

Нечеткая переменная характеризуется тройкой , где α – имя переменной; X – универсальное множество (область определения α); A – нечеткое множество на X, описывающее ограничение (то есть μ A(x)) на значение нечеткой переменной α.

Лингвистической переменной называется набор <β ,T,X,G,M>, где β – имя лингвистической переменной; Т – множество его значений (тер-ммножество), представляющее имена нечетких переменных, областью определения которых является множество X, множество T называется базовым терм-множеством лингвистической переменной; G – синтаксическая процедура, позволяющая оперировать элементами терм-множества T, в частности, генерировать новые термы (значения), множество T G(T), где G(T) – множество сгенерированных термов называется расширен- ным терм-множеством лингвистической переменной; М – семантическая процедура, позволяющая преобразовать новое значение лингвистической переменной, образованной процедурой G, в нечеткую переменную, то есть сформировать соответствующее нечеткое множество.

Исходя из вышесказанного определим входные переменные х1 и х2 и выходную переменную у:

х1 – как терм-множество, состоящее из трех лингвистических переменных – максимального числа переходов (K = 4), среднего числа переходов (КС); минимального числа переходов (МК = 1);

х2 – как терм-множество, состоящее из трех лингвистических переменных – скорости передачи информации по сети: максимальной (Т = 100 Мбит/С), средней (ТС), минимальной (МТ = 10 Мбит/С)

у – как терм-множество, состоящее из трех лингвистических переменных максимального времени прохождения пакета (G = 30 С), среднего времени прохождения пакета (GС), минимального времени прохождения пакета (MG = 10 С).

Таблица 1. Комбинация термов

Номер	xl	х2	У
1	К	МТ	G
2	КС	т	MG
3	КС	тс	GC
4	МК	т	MG

Применим систему типа Сугэно. Если значение выходной переменной в правиле задано нечетким множеством, тогда правило может быть представлено нечетким отношением. Для нечеткого правила, если значение выходной переменной в правиле задано нечетким множеством, тогда правило может быть представлено нечетким отношением. Для нечеткого правила «Если x есть А , то y есть В нечеткое отношение R задается на декартовом произведении Ux xU , где Ux(u) – универсальное множество входной (выходной) переменной» [3]. Для расчета нечеткого отношения можно применять нечеткую импликацию и t-норму. При использовании в качестве t-нормы операции нахождения минимума расчет нечеткого отношения R осуществляется так [6]:

А_й lx, v) = min^ (4 А_ё W) (x, y) e U_x x U_y .

Согласно этому утверждению разработаем правила, которые будут применяться на основ- ных этапах проектирования систем типа Сугэно на примере создания системы нечеткого логического вывода, моделирующей зависимость:

если xl = К и x2 = MT, то у = 30;

если xl = КС и x2 = ТС, то у = 20;

если xl = КС и х2 = ТС, то у = 15;

если xl = МК и х2 = Т, то у = 10.

Введем входные и выходные переменные. Введем правила для создания графиков кодирования. Для этого необходимо выбрать соответствующую комбинацию термов.

Рис.8. Правила для создания структуры сети

В окне видно число строк, соответствующих числу правил нечеткого вывода, а число столбцов – числу входных и выходных переменных. Дополнительное графическое окно служит для отображения результата нечеткого вывода. Входной вектор в каждом из этих вариантов определения исходных данных задается набором красных вертикальных линий.

Построенная модель прохождение пакетов позволяет сделать выбор алгоритма маршрутизации, учитывая необходимую стратегию маршрутизации (см. рис. 9). Можно учесть и время задержки пакетов при любом маршруте. По этим данным смоделируем гибридную сеть, которая будет внедрена в маршурутизаторы.

Структура данной сети (см. рис. 10) может быть описана следующим образом. Слой 1 (inputmf) представлен радиальными базисными нейронами и моделирует функции принадлежности. Выходы узлов этого слоя представляют собой значения функции принадлежности при конкретных значения входов (х1, х2), терм множества (x1 →К, КС, МК; x2 →Т,ТС,МТ).

Рис. 9. Отображение результата нечеткого вывода

РХУХ =PXG 1 <ах); р^у^ = p^MG 1 («2);

Р3у3 = Р3СС"Ча3У, Р4у4 = Р4МС-ЧссдУ

Слой 4 (output) – единственный нейрон этого слоя вычисляет выход сети, тем самым выполняет дефазификацию:

У = Р_ху_х + ^₂у₂ + Р3У3 + РдУд, ■

Результаты загрузки и тестирования сети отражает рис. 11. По результатам тестирования видно, что ее необходимо обучить, так как сеть работает не по заданным условиям.

Рис. 10. Структура гибридной сети

Рис. 11. Результат тестирования сети

Слой 2 (rule) моделирует логическую связку. Выходами нейронов этого слоя являются степени истинности предпосылок каждого правила базы знаний системы, вычисляемые по формулам:

^ = ^(х^ л Ш\х^ л G^x^;

«₂ = КС(х^ ) л ТС(х₂ ) л MGt^);

аз= КС^лТС^ лСС(хзУ,

«4 = МК (х ) л Т (х) л МС^_з).

Все нейроны этого слоя могут реализовывать

Рис. 12. Отображение правил работы гибридной сети

произвольную Т-норму для моделирования опе- рации «И». На этом этапе также рассчитывается и нормированная сила правила (βi):

"А

а, +          +... + а

Слой 3 (outputmf) формирует значения выходной переменной у . Нейроны этого слоя выполняют следующие операции:

После обучения сети правила ее функционирования изменяются (см. рис. 12) за счет добавления условий, которые обеспечивают корректную работу.

Изложенное позволяет сделать вывод о том, что применение гибридной сети упрощает задачу маршрутизации. Выбор маршрута производится автоматически и учитывает кон- фигурацию сети и ее загруженность. Для формулировки основных идей управления гибридной сетью разработан нечеткий алгоритм, с помощью которого можно получить структуру сети, в которой возможен переход от булевых переменных к действительным значениям.

Рис. 13. Поверхность «входы» и «выходы» для системы Сугэно после обучения сети, определяющие передачу данных в зависимости от входных параметров