АЛГОРИТМ МАРШРУТИЗАЦИИ СЕТИ ARPANET

Распределенный адаптивный алгоритм маршрутизации пакетов ARPANET, построенный в соответствии с дейтаграммным принципом, впервые реализован в 1969 г. У первоначальной версии алгоритма бы­ли некоторые недостатки, устраненные в поздних версиях алгорит­ма [I].

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

Длина линии зависит от нагрузки, поступающей в эту линию, и эта длина периодически обновляется. Таким образом, алго­ритм ARPANET является адаптивным, и поскольку в сети используются дейтаграммы, два последовательных пакета одного сообщения мо­гут передаваться по разным маршрутам. Это приводит к двум нежела­тельным эффектам: во-первых, пакеты после прибытия в пункт назна­чения нуждаются в повторном упорядочении, во-вторых, в сети воз­можны колебания загрузки. Причиной колебаний является то, что при выборе маршрута алгоритм ARPANET выбирает слабозагруженные линии и тем самым нагружает их, разгружая при этом остальные линии. В результате следующий маршрут будет отроиться уже с использова­нием других линий сети из какой-либо другой области сети, что, в свою очередь, опять изменяет длины путей и в конечном итоге при­водит к колебаниям. Это является одним из главных недостатков пер­воначальной версии алгоритма ARPANET.

В первоначальной версии алгоритма ARPANET соседние узлы обме­ниваются оценками кратчайших расстояний до любого узла каж­дые 625 мс. Алгоритм обновления кратчайших расстояний от данного узла до каждого узла-адресата основывается на методе Беллмана-Форда. Длина каждой линии равна числу пакетов, находящихся в очереди на передачу по этой линии в момент, когда производится корректи­ровка длин линий. Таким образом, длина линий меняется очень быст­ро, отражая как случайные флуктуации потоков, так и процесс обнов­ления маршрутов. Для ослабления колебаний к длинам линий прибав­ляются большие положительные константы. При этом ухудшается чувст­вительность алгоритма к перегрузкам.

В последней версии алгоритма ARPANET длина каждой линии вы­числяется путем запоминания величины задержки каждого пакета, про­шедшего по этой линии. Длина каждой линии обновляется каждые 10 секунд и выбирается равной средней задержке пакетов, переданных по этой линии в течение предыдущего 10-секундного интервала. Каждый узел следит за длинами всех уходящих от него линий и распростра­няет значения этих длин по сети с использованием волнового алго­ритма не реже одного раза в минуту. В каждом узле пересчитываются кратчайшие пути от этого узла до всех узлов-адресатов с использованием конечно-разностного варианта алгоритма Дийкстра. Эти меры приводят к улучшению свойств устойчивости алгоритма ARPANET.

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