Алгоритм маршрутизации сети ARPANET

Директория статьи: ГлавнаяHi-TechИнтернет

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

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

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

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

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

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

Статья №121 | Просмотров: 416 | Добавлено: 15 ноября 2012 г.

Почему Вы еще не прокомментировали? Оставьте свой комментарий! Весь Интернет заждался уже!

Ваше Имя Муж. Жен. Как нам Вас величать?
Антиспам защита

– Напишите название этого сайта по-русски
(если Вы не в курсе, сайт называется "ВикиАтлас")

Текст комментария
   
Статистика статьи
Слов в статье:
578
Символов в статье:
4098
Просмотров статьи:
449
Уникальные просмотры:
416

Воздушные шары

ТОП5 самых посещаемых статей раздела
ТОП3 самых новых статей раздела