Студопедия — АЛГОРИТМ МАРШРУТИЗАЦИИ СЕТИ ARPANET
Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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






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

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

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

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

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

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

 







Дата добавления: 2015-03-11; просмотров: 550. Нарушение авторских прав; Мы поможем в написании вашей работы!



Шрифт зодчего Шрифт зодчего состоит из прописных (заглавных), строчных букв и цифр...

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

Практические расчеты на срез и смятие При изучении темы обратите внимание на основные расчетные предпосылки и условности расчета...

Функция спроса населения на данный товар Функция спроса населения на данный товар: Qd=7-Р. Функция предложения: Qs= -5+2Р,где...

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

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

Случайной величины Плотностью распределения вероятностей непрерывной случайной величины Х называют функцию f(x) – первую производную от функции распределения F(x): Понятие плотность распределения вероятностей случайной величины Х для дискретной величины неприменима...

Виды и жанры театрализованных представлений   Проживание бронируется и оплачивается слушателями самостоятельно...

Что происходит при встрече с близнецовым пламенем   Если встреча с родственной душой может произойти достаточно спокойно – то встреча с близнецовым пламенем всегда подобна вспышке...

Реостаты и резисторы силовой цепи. Реостаты и резисторы силовой цепи. Резисторы и реостаты предназначены для ограничения тока в электрических цепях. В зависимости от назначения различают пусковые...

Studopedia.info - Студопедия - 2014-2024 год . (0.014 сек.) русская версия | украинская версия