Подход к установлению многомагистральности

МНОГОМАГИСТРАЛЬНАЯ МОДЕЛЬ РЕГУЛЯРИЗАЦИИ ВЫСОКОУРОВНЕВОЙ МАРШРУТИЗАЦИИ В ИНТЕРНЕТ

Дзегеленок И.И., Калинин Н.В.

(Москва, Московский Энергетический Институт (ТУ), Российская Федерация)

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

4 уровень – простые пользователи, не имеющие постоянного IP адреса;
3 уровень – вторичные провайдеры;
2 уровень – первичные провайдеры;
1 уровень – Автономные Системы (АС) [1, стр. 417].

Каждое звено последующего уровня является шлюзом для предыдущего, и если маршрутизация нижних трех уровней проста (если адрес получателя в той же подсети, то пакеты сразу отправляются ему, если нет, то передаются выше), то маршрутизация между АС является нетривиальной задачей. Однако не существует жестко установленных правил регулирования взаимоотношений между АС. Помимо того, что они доставляют интернет-трафик внутренним пользователям, они, как правило, обязаны прокачивать по своим каналам потоки чужих пакетов, идущих между АС, с которыми они граничат.

Каждая такая АС обслуживается одним или несколькими внешними маршрутизаторами (роутерами). Протоколы внешних роутеров предназначены для маршрутизации между доменами маршрутизации. Организации, управляющие АС, относительно свободны в том, как устанавливать соединения и договариваться о маршрутизации. Однако все они находятся на строгом международном учете. Регистрацией AC в Европе занимается RIPE: (Riseaux IP Europiens), а в России эта функция возложена на РосНИИРОС. При регистрации они обязываются поддерживать связность со всеми технически корректными АС Интернета, обслуживать транзитный трафик, следить за грамотным осуществлением маршрутизации, а в случае возникновения сбоев в других системах временно предоставлять свои ресурсы для обхода проблемных узлов и систем.

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

Справедливо следующее утверждение: в глобальной сети существует множество равноправных (по достижимости) маршрутов между двумя точками. Более предпочтительными являются маршруты с меньшей длиной, т.е. маршруты проходящие через меньшее количество АС, однако, в зависимости от загруженности, более короткий маршрут не всегда является самым быстрым.

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

Если предоставить возможность администраторам АС осуществлять плановое "расщепление" транзитного потока данных, то у них появится инструмент для более тонкой настройки маршрутизации и, стало быть, для более эффективного использования каналов, связующих АС.

Для формализации поставленной задачи введем в рассмотрение принцип событийного тактирования. Его суть состоит в том, что для определенных временных интервалов или характерных событий по имеющимся каналам разрешается (но не предписывается) осуществление сразу несколько параллельных передач данных по известным адресам. Воплощением этого принципа является следующий метод синтеза магистральных структур [2, стр. 52]. Он сводится к построению коммуникационной матрицы (КМ) со структурными переменными, определяющими полное множество магистральных структур.

Основой для построения КМ является потактное описание параллельных информационных передач. Формирование КМ начинается с внесения "1" (указывающих на наличие передачи), которые фиксируют связь между соответствующими портами "выход–вход". Одновременно в каждом такте запрещаются перекрестные передачи между смежными портами данного такта, что отражается внесением "0"-ля в КМ.

На оставшиеся пустые места вносятся структурные переменные Х_i. Структурная переменная может принимать значение "1" только для допустимых "1"-чных значений других переменных, если их совместная комбинация не приводит к образованию запрещенных фигур на КМ. Структурным переменным, значения которых всегда изменяется одновременно, согласно правилу плотного заполнения, присваиваются одинаковые индексы, что облегчает поиск допустимых структур. В результате получается КМ, которая может служить "экспертом", оценивающим допустимость возможных комбинаций структурных переменных.

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

Поясним действие предлагаемого метода на простом примере (рис.1).

Дано шесть АС. Имена АС и соответствующие им порты обозначены латинскими буквами. Обозначены. Для АС d и c потоки могут расщепляться.

Положим, что по результатам статистического анализа трафика построено следующее потактное описание информационных передач "вых. r–вх.q" для портов соответствующих АС с именами r и q:.

Такты	1	2	3	4
Передача 1	a––>b	b––->d	D––->f	C––->h
Передача 2	a––>c	c––->e	D––->e

Получаемая КМ имеет вид:

Вых.\Вх.	b	c	D	E	F	h
A	1	1	X₁	X₂	X₂	X₂
B	X₁	X₁	1	0	0	0
C	X₂	X₂	0	1	1	1
D	X₂	X₂	0	1	1	1

Одна из двух допустимых магистральных структур для найденных значений структурных переменных Х₁, Х₂ представлена на рис.2.

Окончательный выбор магистральной структуры среди получаемых допустимых структур может быть осуществлен путем оценки топологической плотности выявленных магистралей. С этой целью введем вспомогательную булеву переменную: x_rmt = 1 если r-я передача закрепляется за m-ой магистралью в такте t и x_rmt = 0 в противном случае. Тогда загрузка m-ой магистрали определяется величиной:

Исходя из того, что скорость магистрали пропорциональна величине топологической загрузки: V_m=c z(m), где с – коэффициент пропорциональности, легко оценить необходимое время для передачи потока емкостью flow: . Отсюда получаем критерий выбора магистральной структуры: .

В заключение укажем на необходимость реализации синхронизации АС в "большом". На первый взгляд можно применить барьерную синхронизацию. Но процессы передачи данных в глобальной сети Интернет полностью асинхронны. Поэтому невозможно контролировать передачу потока вне родительской АС. Зато можно получать подтверждение о доставке или недоставке пакетов. Тем самым синхронизация возможна посредством объединения параллельных потоков в конечной точке маршрута. Конкретно, предлагается ввести нумерацию передаваемых блоков и управляющий сигнал завершения передач. Заметим, что протокол маршрутизации BGP позволяет отправлять и такие сигналы [3].

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

ЛИТЕРАТУРА

1. Компьютерные сети. Принципы, технологии, протоколы/ Олифир В.Г., Олифир Н.А.–СПб.: Питер, 2001.–672 с.

2. Дзегеленок И.И. Мультиконвейерные вычислительные системы на базе микро-ЭВМ.–М.: Моск. энерг. ин-т, 1985.-60 с.

3. Руководство по конфигурированию GateD – BGP. http://www.riss-telecom.ru/doc/gated-rus