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

Алгоритм маршрутизации по выбору кратчайшего пути

Читайте также:
  1. II. Алгоритмы манипуляций и инфекционная безопасность
  2. Адаптивные (динамические) алгоритмы маршрутизации по вектору расстояния
  3. Алгоритм
  4. Алгоритм
  5. Алгоритм
  6. Алгоритм 4. Устранение цепных правил
  7. Алгоритм 5. Преобразование грамматики к БНФ (Хомского).

В этом случае сеть представляется в виде графа. Способ измерения длины дуг может выбираться исходя из физической длины линии между маршрутизаторами, временем задержки при передаче пакетов, длиной очереди и т.д. Имеется несколько алгоритмов вычисления кратчайшего пути. Наиболее известный алгоритм Дейкстры. Работу алгоритма рассмотрим на примере.

Пример:

Кратчайший путь от А к D.

Алгоритм маршрутизации «Заливка»

Идея: каждый приходящий пакет посылается на все исходящие линии кроме той, откуда он пришел. Недостаток: порождается большое количество дублированных пакетов которые гуляют по сети. С целью их упорядочивания в заголовок пакета помещается счетчик преодоления транзитных участков уменьшаемый на 1 после прохождения каждого маршрутизатора. В идеальном случае первоначальное значение счетчика устанавливается в максимальную длину в пути без петлей. Когда, двигаясь по пути пакета, значение счетчика становится равным нулю, он удаляется, либо другим способом является учет прохождения маршрутизаторов. В этом случае все маршрутизаторы ведут список маршрутизаторов – источников. В списке сохраняются порядковые номера пакетов. Если пакет от данного маршрутизатора с таким номером уже приходил он удаляется. Если нет – распространяется дальше.

При «выборочной заливке» пакеты направляются не по всем линиям, а только по тем, которые «приблизительно» идут по выбранному адресатом направлению.

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


Дата добавления: 2015-07-11; просмотров: 254 | Нарушение авторских прав


Читайте в этой же книге: Формирование кадра | Обнаружение и исправление ошибок | Построение кодирования | Двунаправленные протоколы, скользящее окно | Примеры протоколов канального уровня | Протокол PPP | Протоколы канального уровня широковещательных сетей. | Протоколы беспроводных локальных сетей | Формат информационного кадра | Протоколы канального уровня ЛВС типа Ethernet |
<== предыдущая страница | следующая страница ==>
Коммутация на уровне передачи даных. Мосты.| Адаптивные (динамические) алгоритмы маршрутизации по вектору расстояния

mybiblioteka.su - 2015-2024 год. (0.011 сек.)