Читайте также: |
|
В этом случае сеть представляется в виде графа. Способ измерения длины дуг может выбираться исходя из физической длины линии между маршрутизаторами, временем задержки при передаче пакетов, длиной очереди и т.д. Имеется несколько алгоритмов вычисления кратчайшего пути. Наиболее известный алгоритм Дейкстры. Работу алгоритма рассмотрим на примере.
Пример:
Кратчайший путь от А к D.
Алгоритм маршрутизации «Заливка»
Идея: каждый приходящий пакет посылается на все исходящие линии кроме той, откуда он пришел. Недостаток: порождается большое количество дублированных пакетов которые гуляют по сети. С целью их упорядочивания в заголовок пакета помещается счетчик преодоления транзитных участков уменьшаемый на 1 после прохождения каждого маршрутизатора. В идеальном случае первоначальное значение счетчика устанавливается в максимальную длину в пути без петлей. Когда, двигаясь по пути пакета, значение счетчика становится равным нулю, он удаляется, либо другим способом является учет прохождения маршрутизаторов. В этом случае все маршрутизаторы ведут список маршрутизаторов – источников. В списке сохраняются порядковые номера пакетов. Если пакет от данного маршрутизатора с таким номером уже приходил он удаляется. Если нет – распространяется дальше.
При «выборочной заливке» пакеты направляются не по всем линиям, а только по тем, которые «приблизительно» идут по выбранному адресатом направлению.
Алгоритм заливки и выборочной заливки используется в сетях, где выход маршрутизатора из строя или его выключение имеет высокую вероятность. Достоинством заливки является то, что находятся все пути до адресата и пакет обязательно дойдет.
Дата добавления: 2015-07-11; просмотров: 254 | Нарушение авторских прав
<== предыдущая страница | | | следующая страница ==> |
Коммутация на уровне передачи даных. Мосты. | | | Адаптивные (динамические) алгоритмы маршрутизации по вектору расстояния |