Автоматика и телемеханика, Л- 7, 2007
Автоматизация проектирования и
программирования
PACS 02.10.0x
© 2007 г. H.A. КУЗНЕЦОВ, д-р техн. наук, В.Н. ФЕТИСОВ, д-р техн. наук (Институт проблем передачи информации им. A.A. Харкевича РАН, Москва)
УПРАВЛЕНИЕ МАРШРУТИЗАЦИЕЙ В 1Р-СЕТЯХ С ПЕРЕМЕННЫМ КРИТЕРИЕМ КАЧЕСТВА
Для управления маршрутизацией в магистральных IP-сетях предложено разбивать временной интервал управления па два участка, па которых использовать различные критерии качества управления. Предполагается, что распределение потоков па первом этапе реализуется с помощью алгоритма Дейкстры. который включен в протокол маршрутизации OSPF и используется в маршрутизаторах фирмы Siseo. На втором этапе управления предложен минимаксный критерий, который реализуется в робастпом алгоритме коррекции распределения входящих потоков информации. Цель алгоритма коррекции предотвратить или снизить вероятность перегрузки информационных каналов. Изучаются свойства предлагаемого алгоритма. С помощью метода Мопте-Карло показана эффективность использования алгоритма коррекции для управления крупными магистральными сетями. Сравниваются скоростные характеристики предлагаемого алгоритма с некоторыми оптимальными алгоритмами.
1. Введение
На протяжении последних двух десятилетий интенсивно изучается проблема управления маршрутизацией в 1Р-сетях. Благодаря быстрому росту значения Интернета в жизни общества увеличиваются требования к качеству функционирования глобальной информационной сети [1].
Одна из проблем функционирования сетей проблема перегрузок информационных каналов в магистральных сетях. Для решения данной проблемы привлекаются как организационные меры, так и научные. В качестве научных методов чаще всего используются методы оптимального распределения входных информационных потоков.
В данной работе предлагается разбить управление распределением входных информационных потоков на два временных этапа, которые отличаются использованием различных критериев качества управления.
Идея использования двойного критерия оптимальности существует уже давно. В [2] такой критерий оптимальности был использован в динамических системах управления. В [3] показана эффективность практического использования двойного критерия качества. В [4] для уменьшения вероятности перегрузок предлагается
многостадийная оптимизация с измененном весовых параметров критерия качества в методе линейного программирования на каждом сеансе оптимизации. В результате удалось снизить вероятность перегрузки, но расчетное время оказалось неприемлемым. Заметим, что изменение значений весовых параметров вовсе но означает переход к новому критерию качества. В данной работе на втором этапе управления используется критерий, структура которого и назначение принципиально отличны от структуры и назначения критерия качества, используемого на первом этапе.
Метод линейного программирования довольно часто предлагается для предотвращения перегрузок [4 9]. но по ряду причин этот метод трудно реализуем на практике. Укажем на главнейшие из этих причин.
• Проблема определения весов в критерии качества.
усложняет взаимодействие глобального алгоритма управления с протоколами маршрутизации. используемыми в узлах сети.
Указанные особенности задачи линейного программирования привели к поиску более практичных подходов. В [10] предлагается субоптимальный подход к управлению маршрутизацией, который существенно снижает трудности реализации оптимального подхода. Но ряд проблем остается. Например, проблема продолжительности вычислений, хотя по сравнению с оптимальным подходом объем вычислений стал меньше. Заметим также, что в ряде случаев трудно понять, насколько субоптимальный подход близок к оптимальному. Субоптимальный подход никак не гарантирует отсутствие перегрузок в сети, а проблема перегрузок является очень важной, поскольку перегрузки каналов приводят к существенным задержкам передачи данных н существенно ухудшают качество передачи мультимедийных потоков.
В [11] предложен новый подход к управлению маршрутизацией, который нельзя отнести к оптимальному или субоптимальному подходам. Новый алгоритм предназначен для устранения перегрузок каналов в магистральных 1Р-сотях путем рационального выбора обходных путей передачи информации. При этом не нарушается инфраструктура информационной сети. Алгоритм является надстройкой над существующими способами распределения нагрузки в информационных каналах. Благодаря предложенному в [11] способу хранения и обработки данных (факторизации матрицы нагрузок) существенно упрощается обмен данными между новым алгоритмом н локальными алгоритмами распределения нагрузок. Алгоритм вступает в работу лишь в случае появления перегрузки или высокой вероятности ее возникновения.
Данная работа преследует несколько целей: терпев качества управления и показать, в чем эффективность такого подхода, ны н гарантировать отсутствие потерн данных при функционировании алгоритма.
ции с некоторыми другими алгоритмами распределения нагрузки в магистральных 1Р-СОТЯХ.
Во втором разделе статьи изучаются особенности метрики, используемой в протоколе ОЭРБ [12. 13] и указывается на необходимость использования двойного критерия качества: на первом этапе распределение задания по каналам информационной сети с помощью алгоритма Дойкстры [14]. на втором этапе коррекция первоначального распределения с помощью алгоритма с минимаксным критерием. В третьем разделе описывается обобщенный алгоритм коррекции и изучаются его
свойства. В четвертом разделе предлагается способ выбора параметров алгоритма коррекции. В пятом разделе изучается быстродействие алгоритма. В шестом разделе приводятся примеры моделирования ряда информационных сетей и делается сравнение времени реализации алгоритма коррекции с временем реализации оптимального алгоритма.
В IP-сетях присутствует специальный алгоритм управления скоростью передачи, который реализован в транспортном протоколе TCP [15]. Этот алгоритм частично препятствует возникновению перегрузок. Но скорость нельзя снизить ниже некоторой величины для мультимедийного типа информации, так как в общем случае снижение скорости может привести к существенной задержке передачи данных или даже к их потере. Транспортный протокол UDP [15]. с помощью которого часто передаются потоки мультимедийных данных, вообще не управляет скоростью передачи данных. Поэтому для снижения вероятности перегрузки необходимо принимать дополнительные меры. Прежде всего, снизить эту вероятность можно путем выбора подходящего алгоритма распределения нагрузок каналов.
Пусть определен ориентированный или неориентированный граф G = (V,E). Ребра графа будем определять как однозвонныо каналы информационной сети, а вершины определим как маршрутизаторы. В протоколе OSPF для распределения нагрузки используется алгоритм Дойкстры [14] с метрикой, определяемой формулой
(г, ]) - однозвенный капал, суммирование производится по некоторому пути из узла д в узел р графа О. Величина е^ обозначает пропускную способность канала (г,]) € Е в бит/с.
В изучаемом далее алгоритме коррекции используется метрика, определяемая максимальным по всем (г,]) € Е отношением нагрузки канала к его пропускной способности.
Обе упомянутые выше метрики имеют своп преимущества и недостатки. Поясним это на простом примере.
На рис. 1 показан фрагмент информационной сети, где кружками обозначены маршрутизаторы, а цифры над каналами определяют их пропускную способность.
Для передачи информационных данных из узла 1 в узел 3 согласно метрике 1чр и алгоритму Дойкстры предпочтителен путь (1.2). (2.3). хотя в случае большой вероятности перегрузки канал (2.3) может оказаться «узким местом».
2. Выбор метрики
[12, 13]:
10000 0000
(i,j)eE
Рис. 1. Фрагмент .Vs 1.
Рис. 2. Фрагмент Л"'2.
Теперь рассмотрим фрагмент информационной сети, изображенной на рис. 2. Если для выбора пути использовать минимаксную метрику при передаче информации из узла 1 в узел 3. то канал (1.3) может оказаться вообще незадействованным. что противоречит здравому смыслу.
Возникшая дилемма может быть решена применением комбинированного подхода. На первом шаге используется алгоритм Дейкстры. который входит в протокол маршрутизации. На втором шаге используется метод коррекции, назначение которого избавиться от перегрузки (или снизить ее вероятность). В случае отсутствия высокой вероятности перегрузки второй шаг не реализуется.
Подход к распределению нагрузки с использованием двойного критерия оптимальности дает хороший результат, что будет показано далее на примере.
Необходимость глобальной оптимизации в магистральных сетях аргументируется в ряде работ (см.. например. [4 10]). Но каждый раз авторы этих работ встречаются с проблемой дефицита времени реализации алгоритма оптимизации при работе в реальном масштабе времени. Здесь эта проблема успешно решается. Предлагаемый алгоритм имеет существенно большее быстродействие, что будет показано далее.
3. Алгоритм коррекции
Определение 1. Обозначим через N(2) информационную сеть в момент Ь, которая определяется матрицей нагрузок каналов X(Ь) размерности (п х п) на графе О = (V, Е) с числом вер шин п = V (О), числом ре бер т = Е(О) и матрицей пропускных способностей СЕ = С(Е). Каждая вершина графа О является маршрутизатором.
Обозначим через ДЬ временной интервал между двумя моментами расчета алго-Е
что в каждый расчетный момент времени на каждый г-й маршрутизатор поступает (из локальных сетей) суммарный поток информации, предназначенный для маршрутизатора ]. Эти потоки определяют матрицу <(Ь) размерности п х п с нулевой главной диагональю. Матрица <(Ь) определяет многоадресный поток данных и имеет представление
<(ь) = £ (г), к е К, к
где К обозначает множество потоков информации, 1Р адреса которых соответствуют префиксам (1Р-адресам сетей) в таблицах маршрутизации [4].
Матрицу X(Ь), которая определяет нагрузку информационной сети после распределения задания алгоритмом, входящим в маршрутизатор, представим в виде суммы матриц [11]
(1) X (Ь) = ь(г) + и (Ь),
п т ¿=1 3 = 1
где матрицы Ь(€)гз определяют сумму инфор
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.