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

Лекция 10

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

Алгоритм Дейкстры

Эти методы обеспечивают оптимальный маршрут прохождения пакета между отдельной парой абонентов. Введем обозначения: D(v) – суммарная стоимость минимального пути от источника (узел с номером 1) до получателя (узел с номером v), l(i,j) – стоимость канала от узла i до узла j. Определена только для смежных узлов. Для несмежных равна ¥. Это подход является алгоритмом Дейкстры для сетевой маршрутизации.

Шаг0. Строится множество N, содержащее номер одного узла (первого). Строится таблица: строки таблицы – итерации, столбцы – номер операции, множество N, номера узлов (начиная со второго). В строке для нулевой итерации, в столбце для узла v фиксируется значение D₁(v) = l(1,v). Нижний индекс показывает номер узла, через который достигается текущее оптимальное значение. Строиться корень дерева с узлом 1.

Шаг k (k = 1,2,3,…). В текущей строке выбираем узел v такой, что он не из множества N, но является смежным с каким-либо из узлов множества N и такой, что значение D_p(v) минимально. Узел v включается во множество N. В дереве добавляется узел с номером v в качестве потомка узла с номером p. Далее формируется новая строка таблицы, делается пересчет. Для всех узлов wÏN проверяем, изменилось ли стоимость маршрута по следующему правилу: , w* – любое, , если было оставлено старое значение,  иначе.

Алгоритм заканчивает работу, исчерпав все множество вершин.

Пример: