Rip(Метод рельефов)

Рельеф – это оценка кратчайшего пути от узла Aдо узлаB. Оценка (расстояние) может выражаться временем доставки, надёжностью доставки или числом узлов коммутации на данном маршруте.

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

Например, для узла а строка для dвыглядит так (зная, что из узла а можно попасть в узелdчерез узлыjиk):

• пункт назначения – d;

• длина кратчайшего пути Ra(d);

• номер ближайшего узла N(d)=j;

• список рельефов: Raj(d),Rak(d).

Пусть изменилась задержка Rak(d) так, что она стала меньше, чемRaj(d). Тогда в строкеdтаблицы маршрутизации узлаaкорректируетсяRa(d),N(d) изменяется наk, и кроме того всем соседям узла а посылается сообщение об изменённомRa(d). Например, в некотором соседнем узлеlпри этом будет изменено значениеRla(d)=Ra(d)+Rl(a). Мы видим, что возникает итерационный процесс корректировки маршрута информации в узлах коммутации.

Хотя данный алгоритм сходится медленно, для относительно небольших сетей он вполне приемлем.

Возможен упрощенный вариант формирования рельефов. Он заключается в следующем: пусть i– это произвольный узел коммутации сети связи.i-рельефом называется процедура присвоения значений числовой функции каждой линии связи. Он строится следующим образом: изi-ого узла коммутации по всем исходящим линиям связи передается число «1». Все узлы коммутации, в которые поступило число 1, передают по всем исходящим линиям связи, кроме тех, по которым поступила 1, число 2. Далее узлы коммутации, по которым поступило число 2, передают 3, и т.д. до тех пор, пока все линии связи не будут пронумерованы. Говорят, что линия связи имеетnвысоту, если она обозначена числомnвi-рельефе.

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

Пример формирования 4-рельефа:

Чтобы найти кратчайший маршрут коммутации к узлу A, достаточно в каждом узле коммутации выбирать линию связи с меньшим весом. Например, кратчайший маршрут отNдоAбудет следующий: