Формальное описание алгоритма

Пусть D (v) равно сумме весов связей для данного пути
и c (i,j)равно весу связи между узлами с номерами i и j.

Последовательность шагов, реализующих алгоритм:

1. Установить множество узлов N = {1}.

2. Для каждого узла v не из множества n установить D (v) = c (1, v).

3. Для каждого шага найти узел w не из множества N, для которого D (w) минимально, и добавить узел w в множество N.

4. Актуализировать D (v) для всех узлов не из множества N
D (v) = min{ D (v), D (v) + c (w, v)}.

5. Повторять шаги 2-4, пока все узлы не окажутся в множестве N.

Топология всех возможных маршрутов для узла А приведена на рис.3, а (в скобках записаны числа, характеризующие метрику отобранного маршрута согласно критерию шага 3).

Топология маршрутов кратчайшего пути для узла А приведена на рис.3.1,б.

 

 EMBED Visio 2000 Drawing EMBED Visio 2000 Drawing

 

а)                                                          б)

 

Рис. 3. Иллюстрация работы алгоритма Дейкстры:

а – схема узлов А - J с метрикой для каждого отрезка пути;

б – топология мршрутов кратчайшего пути ль узла A до J.

 

Табл. 3.1 может иметь различное содержимое в соответствии с приоритетом и типом параметров сети, выбранные пути при этом могут иметь другую топологию. Качество обслуживания может характеризоваться следующими параметрами: пропускной способностью канала; задержкой (время прохождения пакета по сети); числом пакетов, стоящих в очереди для передачи; загрузкой канала; требованиями безопасности; типом трафика; числом шагов до цели (количеством переходов – хопов); возможностями промежуточных связей (например, многовариантность достижения адресата, балансировка нагрузки).

Также см. разд. «Теория» меню программы.

Таблица 3.1

Реализация алгоритма Дейкстры

Шаг

Множество N

Метрика связи узла A с узлами

BCDEFGHIJ0{A}3-9------1{A,B}(3)497-10---2{A,B,C}3(4)66-10---3{A,BC,D}34(6)6-10---4{A,B,C,D,E}346(6)10108--5{A,B,C,D,E,H}34661010(8)9-6{A,B,C,D,E,H,I}346610108(9)147{A,B,C,D,E,H,I,F}3466(10)1089148{A,B,C,D,E,H,I,F,G}346610(10)89149{A,B,C,D,E,H,I,F,G,J}3466101089(14)

Задание

Запустить файл lab.exe. Согласно варианту (табл. 3.2) изобразить исследуемую сеть, указать диапазон параметров сети и заполнить табл. 3.3 для двух типов трафика (приоритетного и неприоритетного).

Оценить влияние параметров сети связи при фиксированных значениях (табл. 3.3), построить графики зависимостей задержки трафика и длины пути (количества промежуточных узлов) от длины очереди, времени обработки пакета в узле, пропускной способности канала.

При выполнении лабораторной работы необходимо:

Сконфигурировать граф в зависимости от варианта согласно табл. 3.2. При этом следите, чтобы не было прямого пути между узлом-отправителем и узлом-получателем.

При выполнении исследовании влияния длины очереди N и времени обработки пакета на узле Т_{обр .} изменяйте значения только в одном узле, расположенном на маршруте (отмечен красным). При заполнении табл. 3.3 необходимо снимать показания времени задержки в узлах (Т2).

При выполнении исследовании влияния пропускной способности C изменяйте значения только на одном из каналов маршрута. В этом случае необходимо снимать показания времени задержки в канале (Т1).

Таблица 3.2

Варианты заданий к лабораторной работе

получателя

время обработки

Авто

Авто

Авто

Авто

Авто

Авто

Авто

Авто

Авто

Авто

Вариант	Номер узла	Отсутствующие связи между узлами	Значения фиксированных параметров сети
	отправителя	длина очереди		полоса пропускания	стоимость	надежность
1	1	4	Данные значения предлагается выбрать самостоятельно. Убирая связи между узлами, оставляйте не менее трех альтернативных путей. Значения исследуемых параметров меняйте плавно в заданном диапазоне (см. пункт меню программы «Помощь»), количество контрольных значений параметров n не менее 5	Авто	Авто
2	5	2		Авто
3	6	3		Авто
4	2	4		Авто
5	6	2		Авто
6	1	5		Авто
7	4	3		Авто
8	1	6		Авто
9	5	3		Авто
10	6	5		Авто
11	3	2		Авто

 

Для корректного выполнения работы можно воспользоваться пунктом «Помощь» программы, в котором приведены основные приемы работы с данным ПО и диапазоны изменения параметров сети.

 

Таблица 3.3

Пример таблицы с результатами эксперимента

Т_зад.

Исследуемый  параметр:	Влияние параметров сети связи с коммутацией пакетов
	длина пути	стоимость	маршрут	надежность
Длина очереди, N -значение 1 … -значение n
Время обработки, Tобр. -значение 1 … -значение n
Пропускная способность, С -значение 1 … -значение n

К защите

Знать функции, область использования и принцип работы протокола маршрутизации OSPF.

Представить отчет, содержащий таблицы исследований и графики Т_зад. (N), Т_зад. (Т_обр), Т_зад. (С) в одной системе координат для приоритетного и неприоритетного типов трафика.

Уметь строить матрицу алгоритма Дейкстры для параметров, исследуемых в лабораторной работе согласно топологии и данным, соответствующим варианту.

Иметь представление о процессах формирования задержек в сетях с коммутацией пакетов и влиянии приоритета трафика на Т_зад.

Объяснить полученные результаты.