к.т.н. Бельков Д.В.

Донецкий национальный технический университет, Украина

ЗАДАЧА МАРШРУТИЗАЦИИ В ГЛОБАЛЬНЫХ КОМПЬЮТЕРНЫХ СЕТЯХ

Маршрутизация - процесс определения в сети пути, по которому пакет может достигнуть адресата. Наибольшее распространение в компьютерных сетях получили адаптивные (динамические) алгоритмы маршрутизации, которые можно разделить на две группы: алгоритмы по вектору расстояния и алгоритмы состояния связей. В алгоритмах по вектору расстояния (DVA) каждый маршрутизатор периодически и широковещательно рассылает по сети вектор, компонентами которого являются расстояния от данного маршрутизатора до всех известных ему сетей. Под расстоянием обычно понимается число промежуточных маршрутизаторов, но может также учитываться время прохождения пакетов по сети между соседними маршрутизаторами. Получив информацию о состоянии сети и расстоянии ко всем имеющимся в интерсети сетям, маршрутизатор выбирает из нескольких альтернативных маршрутов к каждой сети тот, который обладает наименьшей метрикой. Алгоритмы по вектору расстояния хорошо работают только в небольших сетях. В больших сетях они засоряют линии связи интенсивным служебным трафиком, к тому же изменения конфигурации могуг отрабатываться по этому алгоритму не всегда корректно, так как маршрутизаторы не имеют точного представления о топологии связей сети, а располагают только обобщённой информацией - вектором дистанций, к тому же полученной от посредников [1].

Алгоритмы состояния связей (LSA) обеспечивают каждый маршрутизатор информацией достаточной для построения точного графа связей сети. Все маршрутизаторы работают на основании одинаковых графов, что делает процесс маршрутизации более устойчивым к изменениям конфигурации. Широковещательная рассылка имеет место только при изменениях состояния связей, что редко происходит в надёжных сетях. Вершинами графа являются как маршрутизаторы, так и объединяемые ими сети. Чтобы понять, в каком состоянии находятся линии связи, подключённые к его портам, маршрутизатор периодически обменивается короткими сообщениями HELLO со своими ближайшими соседями. Объявление о состоянии связей не повторяется периодически, как в алгоритме DVA, а передаются только в том случае, когда с помощью сообщения HELLO было установлено изменение состояния какой-либо связи. В результате служебный трафик, создаваемый алгоритмом LSA менее интенсивный, чем у DVA [2].

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

Обозначим: - время передачи сообщения, - вероятность изменения состояния связей. Если во время передачи произойдет изменение топологии сети, то процесс передачи прекращается, сообщение будет потеряно. Передача возобновится только после получения маршрутизатором уточненной информации о связях между узлами сети. Поэтому величина есть вероятность потери сообщения (вероятность события). Пусть поток событий является потоком Эрланга k - го порядка с параметром и t – время, прошедшее после очередного события. В этом случае значение можно определить по формулам [3]:

, ,

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

Целевая функция:

(1)

Ограничения:

,, i=1...n (2)

, j=1...n (3)

Необходимо найти матрицу X, обеспечивающую максимум целевой функции (1) при ограничениях (2),(3). В задаче минимизируется вероятность потери сообщений.

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

На первом шаге определяется маршрут с наименьшим значением , j=1,…n. На втором шаге сообщение i будет направлено по j–му маршруту, если условие (3) выполняется. Иначе передача этого сообщения по j–му маршруту запрещается, и процедура повторяется с первого шага.

Необходимо отметить, что задача (1)-(3) представляет собой задачу о назначениях, методов решения которой известно много. Перспективным направлением исследований является маршрутизация на основе идей „природных вычислений” (генетических, нейросетевых, муравьиных и других алгоритмов).

Литература

1. Олифер В.Г., Олифер Н.А. Сетевые операционные системы. СПб: Питер,

2002.- 538 с.

2. Голубова О.М., Вороной С.М. Исследование алгоритмов маршрутизации

в глобальных компьютерных сетях. Материалы первой международной

научно-технической конференции “Моделирование и компьютерная

графика”. Донецк: ДонНТУ, 2005, С. 276-277.

3. Вентцель Е.С., Овчаров Л.А. Теория случайных процессов и ее

инженерные приложения. Москва: Финансы и статистика, 1991.- 381с.