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

↑

▷ Содержание

⇐ ПредыдущаяСтр 4 из 7Следующая ⇒

Пусть 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

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

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

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

получателя

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

Авто

Авто

Авто

Авто

Авто

Авто

Авто

Авто

Авто

Авто

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

Таблица 3.3

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

Т_зад.

К защите

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

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

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

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

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

Познавательные статьи:



Коммуникативные барьеры и пути их преодоления

Рынок недвижимости. Сущность недвижимости

Решение задач с использованием генеалогического метода

История происхождения и развития детской игры