Методы локальной пользовательской маршрутизации, страница 3

Замечание. Алгоритм Дейкстра может быть выполнен децентрализованно. Но при этом должны быть известны стоимости всех каналов связи в каждом узле. Т.к. в реальных сетях эта величина динамически меняется, то более эффективно выполнять расчет централизованным способом. Алгоритм Форда-Фолкирсона не может быть выполнен децентрализованно, т.к. там расчитываются все маршрутные таблицы. Однако именно он послужил основой для полностью децентрализованного алгоритма, использовавшегося в ARPANet, который в настоящее время является основой для Internet.

5.

Децентрализованный алгоритм Форда-Фолкирсона

Впервые был использован в сети ARPANet. В настоящее время являтся технологической основой сети Internet. В каждом узле связихраняться две таблицы. Расширенныя таблица маршрутизации и матрица стоимостей.

Кроме того в текущем узле храняться стоимости каналов со смежными узлами. Обозначим  C_d(v,w) – минимальная стоимость доставки из текущего узла v до получателя d через смежный узел w (смежный с текущим, с v). D_d(v) – минимальная стоимость доставки из текущего узла v до получателя d, т.е. . Величины c, v, w являются содержанием матрицы стоимостей. D_d(v) – третий столбец маршрутной таблицы, l(v,w) – стоимость канала. Все управление алгоритмом и узлами строиться на событиях.

Событие1. В сеть дополнен канал (v,m) между текущим узлом v и смежным с ним узлом m. Его стоимость l(v,m). Возможно, что узел m является новым. Появление узла = появление канала. Такое событие инициируется администратором.

Шаг1. В текущем узле v в матрице стоимостей в строке для получателя с номером m и в столбце для смежного узла с номером m фиксируется значение C_m(v,m) = l(v,m).

Шаг2. Для получателя с номером m пересчитывается минимальная стоимость доставки из узла v, , w – смежный узел. Сравниваем его с имеющимся значением маршрутной таблицы. Если значения различны, то новое значение D_m(v) заносится в таблицу (m, p, D_m(v)), где p – номер узла, на котором достигнут минимум (в матрице стоимостей это номер столбца). Как правило p = m, иначе нет смысла во введении нового канала. Всем смежным узлам посылается сообщение [m, D_m(v)], в котором текущий узел v информирует соседей, что стоимость доставки из узла m до текущего узла v изменилась.