Исследование алгоритма Дейкстры для маршрутизации пакетов в компьютерной сети

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

маршрутизация пакет данные компьютерная сеть

ВВЕДЕНИЕ

Каждый маршрутизатор действует по алгоритму кратчайшего пути Дейкстры. Для реализации алгоритма он нуждается в плане сети с обозначенными длинами каналов. Каждый маршрутизатор знает собственный адрес, который был введен в него при его установке, и обращается к соседям при поиске их сетевых адресов. В работающей сети маршрутизатор может рассчитать метрику каждого исходящего канала. В простейшем случае метрика равна 1 для работоспособного канала и бесконечно велика в противном случае. Более точная метрика учитывает пропускную способность канала и среднюю задержку при прохождении через его буфер. Метрика выбирается администратором сети, и все маршрутизаторы используют одну метрику.

Маршрутизаторы могут также выполнять алгоритм Дейкстры с несколькими различными наборами метрик. Например, метрики могут учитывать порознь надежность, пропускную способность и задержку. В результате выполнения алгоритма Дейкстры для каждого из трех наборов метрик, все маршрутизаторы сети знают самый надежный путь, путь с наибольшей пропускной способностью и путь с минимальной задержкой до любого другого маршрутизатора. В пакете может быть указано, по какому критерию маршрутизаторам следует выбирать путь.

Таким образом, задачи данной работы можно сформулировать следующим образом:

Ознакомиться с управлением процессами маршрутизации пакетов, передаваемых через сеть.

Изучить теорию выбора кратчайших путей и ее методов.

Написать программу в соответствии с заданной сетью, ввести программу, отладить и решить ее на ЭВМ.

Получить таблицу кратчайших путей и маршрутов методом Дейкстры

1. Краткая теория

Есть простой способ объяснения, как действует алгоритм. Представьте себе набор из N шаров, соединенных между собой нитями. Нити имеют различную длину. Мы выбираем какой-то один шар, и называем его «шар 1». Нашей целью является нахождение кратчайшего пути от «шара 1» к каждому из оставшихся шаров. Для нахождения этих путей мы кладем все шары на поверхность и начинаем медленно поднимать "«шар 1"» следующий поднятый шар мы называем «шар 2». Когда «шар 2» поднялся с поверхности, мы видим, что кратчайший путь между шарами 1 и 2 - это нить, соединяющая эти шары. По мере того, как мы продолжаем поднимать «шар 1» другой - « шар 3» поднимается с поверхности. Кратчайший путь между шарами 1 и 3 - это или нить между шарами 1 и 3, либо составной путь между шарами 1, 2 и 2, 3. Продолжая подобным образом, мы поднимаем все шары с поверхности. Когда поднимается очередной, «шар n+1», мы находим кратчайший путь между шарами 1 и n+1. Шаг за шагом мы найдем все кратчайшие пути между шаром 1 и остальными шарами.

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

Переходим к описанию алгоритма Дейкстры. Рассмотрим сеть на рис.1

Рисунок 4. Пример сети

Числа, проставленные у каждой линии, указывают ее стоимость (ради простоты стоимость в обоих направлениях предполагается одинаковой; однако в более общем случае стоимость передачи в разных направлениях может и различаться). Алгоритм Дейкстры позволяет найти кратчайшие пути от источника ко всем другим узлам. Для этого требуется знание глобальной структуры, т.е. списка всех узлов сети и их взаимосвязей, а также стоимости каждой линии.

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

В примере на рис.1 целью является нахождение кратчайшего пути от узла 1, являющегося источником, ко всем остальным узлам сети. Алгоритм решает эту задачу поэтапно, строя дерево кратчайших путей с корнем в узле-источнике (в данном примере в узле 1), пока будет охвачен самый удаленный узел. На k-м шаге вычисляются кратчайшие пути к k-узлам, ближайшим к источнику. Они определяются как находящиеся внутри множества N. Опишем алгоритм неформально.

Обозначим через D(v) расстояние (сумму весов каналов вдоль данного пути) от источника 1 до узла v. Пусть l(i,j) - заданная стоимость пути между узлами i и j. Алгоритм состоит из двух частей: начального шага и итераций, повторяющихся до завершения алгоритма.

1. Начальный шаг. Устанавливаем N={1}. Для каждого узла v, не принадлежащего множеству N, устанавливаем D(v)=l(1,v). (Расстояние до узлов, не соединенных с узлом 1, принимаем равным Ґ; практически можно принять любое число, большее максимальной стоимости или расстояния.)

2. Каждый последующий шаг. Находим не принадлежащий множеству N узел w, для которого D(w) минимально и включаем w в множество N. Затем обновляем значения D(v) для всех остальных узлов, не принадлежащих N путем вычисления

Шаг 2 повторяется, пока в множество N не войдут все узлы.

Применение алгоритма Дейкстры к сети на рис.1 иллюстрируется последовательными шагами, указанными в таблице 1.1. Полужирным курсивом в столбцах обозначены минимальные значения D(w) на каждом шаге (при равных расстояниях выбор производится случайным образом). После каждого шага соответствующий узел w добавляется к N. Затем величины D(v) обновляются. Например, после начального шага во время шага 1 к множеству N добавляется узел 4, имеющий минимальное значение D(4)=1. На шаге 2 в N включается узел 5 при D(5)=2, и т.д. После шага 5 все узлы оказываются включенными в множество N, и алгоритм завершается.

По мере работы алгоритма, приводящей к результатам, показанным в табл.1.1, в то же самое время строится дерево кратчайших путей с корнем в узле 1: при включении узла во множество N он соединяется с соответствующим узлом, уже принадлежащим N. Результирующее дерево для сети на рис.1 показано на рис.2а.

а

Рис.5 Применение алгоритма Дейкстры к рис.1; источник-узел 1: (а) построение дерева кратчайших путей, (б) таблицы маршрутов, узел 1.

Цифры в скобках у каждого узла указывают шаг, на котором этот узел был включен в дерево. С помощью дерева кратчайших путей для узла 1 можно получить таблицу маршрутов для узла 1, показывающую исходящий путь. По которому нужно направлять пакеты к узлу назначения. Подобная таблица маршрутов может быть составлена для каждого узла, являющегося источником сообщений. В случае централизованных вычислений каждая таблица маршрутов затем может быть направлена в соответствующий узел. В случае же децентрализованного, или распределенного выбора маршрутов, как в обсуждаемом ниже алгоритме сети ARPA, каждый узел выполняет свои вычисления, используя ту же самую глобальную информацию и генерируя собственное дерево и соответствующую таблицу маршрутов.

2. Описание процедур и функций, используемых в программе

ДЛЯ СЕТИ № 1

Начальная вершина: 1

Конечная вершина: 1

Конечная вершина: 2<-1

Конечная вершина: 3<-5<-1

Конечная вершина: 4<-1

Конечная вершина: 5<-1

Конечная вершина: 6<-5<-1

Начальная вершина: 2

Конечная вершина: 1<-2

Конечная вершина: 2

Конечная вершина: 3<-2

Конечная вершина: 4<-2

Конечная вершина: 5<-3<-2

Конечная вершина: 6<-2

Начальная вершина: 3

Конечная вершина: 1<-5<-3

Конечная вершина: 2<-3

Конечная вершина: 3

Конечная вершина: 4<-5<-3

Конечная вершина: 5<-3

Конечная вершина: 6<-3

Начальная вершина: 4

Конечная вершина: 1<-4

Конечная вершина: 2<-4

Конечная вершина: 3<-5<-4

Конечная вершина: 4

Конечная вершина: 5<-4

Конечная вершина: 6<-5<-4

Начальная вершина: 5

Конечная вершина: 1<-5

Конечная вершина: 2<-3<-5

Конечная вершина: 3<-5

Конечная вершина: 4<-5

Конечная вершина: 5

Конечная вершина: 6<-5

Начальная вершина: 6

Конечная вершина: 1<-5<-6

Конечная вершина: 2<-6

Конечная вершина: 3<-6

Конечная вершина: 4<-5<-6

Конечная вершина: 5<-6

Конечная вершина: 6

ДЛЯ СЕТИ № 2

Начальная вершина: 1

Конечная вершина: 1

Конечная вершина: 2<-1

Конечная вершина: 3<-1

Конечная вершина: 4<-1

Конечная вершина: 5<-2<-1

Конечная вершина: 6<-5<-2<-1

Начальная вершина: 2

Конечная вершина: 1<-2

Конечная вершина: 2

Конечная вершина: 3<-1<-2

Конечная вершина: 4<-1<-2

Конечная вершина: 5<-2

Конечная вершина: 6<-5<-2

Начальная вершина: 3

Конечная вершина: 1<-3

Конечная вершина: 2<-1<-3

Конечная вершина: 3

Конечная вершина: 4<-3

Конечная вершина: 5<-6<-3

Конечная вершина: 6<-3

Начальная вершина: 4

Конечная вершина: 1<-4

Конечная вершина: 2<-1<-4

Конечная вершина: 3<-4

Конечная вершина: 4

Конечная вершина: 5<-6<-4

Конечная вершина: 6<-4

Начальная вершина: 5

Конечная вершина: 1<-2<-5

Конечная вершина: 2<-5

Конечная вершина: 3<-6<-5

Конечная вершина: 4<-6<-5

Конечная вершина: 5

Конечная вершина: 6<-5

Начальная вершина: 6

Конечная вершина: 1<-2<-5<-6

Конечная вершина: 2<-5<-6

Конечная вершина: 3<-6

Конечная вершина: 4<-6

Конечная вершина: 5<-6

Конечная вершина: 6

ДЛЯ СЕТИ № 3

Начальная вершина: 1

Конечная вершина: 1

Конечная вершина: 2<-1

Конечная вершина: 3<-1

Конечная вершина: 4<-1

Конечная вершина: 5<-2<-1

Конечная вершина: 6<-5<-2<-1

Начальная вершина: 2

Конечная вершина: 1<-2

Конечная вершина: 2

Конечная вершина: 3<-4<-2

Конечная вершина: 4<-2

Конечная вершина: 5<-2

Конечная вершина: 6<-5<-2

Начальная вершина: 3

Конечная вершина: 1<-3

Конечная вершина: 2<-5<-3

Конечная вершина: 3

Конечная вершина: 4<-3

Конечная вершина: 5<-3

Конечная вершина: 6<-3

Начальная вершина: 4

Конечная вершина: 1<-4

Конечная вершина: 2<-4

Конечная вершина: 3<-4

Конечная вершина: 4

Конечная вершина: 5<-2<-4

Конечная вершина: 6<-4

Начальная вершина: 5

Конечная вершина: 1<-2<-5

Конечная вершина: 2<-5

Конечная вершина: 3<-5

Конечная вершина: 4<-2<-5

Конечная вершина: 5

Конечная вершина: 6<-5

Начальная вершина: 6

Конечная вершина: 1<-2<-5<-6

Конечная вершина: 2<-5<-6

Конечная вершина: 3<-6

Конечная вершина: 4<-6

Конечная вершина: 5<-6

Конечная вершина: 6

ЗАКЛЮЧЕНИЕ

В результате выполненной курсовой работы были выполнены поставленные цели и задачи, а именно я ознакомился с управлением процессами маршрутизации пакетов, передаваемых через сеть, изучил теорию выбора кратчайших путей и ее методов. Кроме того, была написана программа в соответствии с заданными сетями.

В результате была получена таблица кратчайших путей и маршрутов методом Дейкстры.

Программы готовы к эксплуатации и могут с успехом использоваться как в вычислительных процессах, так и как один из примеров демонстрации работы с алгоритмом Дейкстры.

Также были получены практические навыки в программировании на алгоритмическом языке высокого уровня Turbo Pascal 7.0.

Список использованных источников

Листинг программы

program Deikstr;

Uses Crt,Graph;

type

• Mas=array[1..6,1..6] of integer;
• Const
• Infinity=1000;
• N=6;
• mattr:mas = (( 0, 3, 1000, 1, 3, 1000),
• ( 3, 0, 3, 2, 1000, 4),
• (1000, 3, 0, 1000, 1, 3),
• ( 1, 2, 1000, 0, 3, 1000),
• ( 3, 1000, 1, 3, 0, 2),
• (1000, 4, 3, 1000, 2, 0));
• mattr1:mas = (( 0, 1, 5, 2, 1000, 1000),
• ( 1, 0, 1000, 1000, 3, 1000),
• ( 5, 1000, 0, 4, 1000, 3),
• ( 2, 1000, 4, 0, 1000, 4),
• (1000, 3, 1000, 1000, 0, 1),
• (1000, 1000, 3, 4, 1, 0));
• mattr2: mas = (( 0, 1, 5, 2, 1000, 1000),
• ( 1, 0, 1000, 1, 3, 1000),
• ( 5, 1000, 0, 4, 2, 3),
• ( 2, 1, 4, 0, 1000, 4),
• (1000, 3, 2, 1000, 0, 1),
• (1000, 1000, 3, 4, 1, 0));
• Var
• Visited: array [1..N] of boolean;
• Len,Path: array [1..N] of integer;
• gr,MN,l,t,Start, Finish, k, i,j: integer;
• ch:char;
• function menu:byte;
• var
• t,n:integer;
• c:char;
• const
• mdat:array [1..3] of string=(
• ' ПРОСМОТРЕТЬ СЕТИ ',
• ' АЛГОРИТМ ДЕЙКСТРЫ ',
• ' ВЫХОД ');
• begin
• t:=1;
• repeat
• for n:=1 to 3 do begin
• if n=t then begin
• textcolor(15);
• textbackground(2);
• end else begin
• textcolor(7);
• textbackground(1);
• end;
• gotoxy(30,10+n);
• write(mdat[n]);
• end;
• c:=readkey;
• if c=#0 then c:=readkey;
• if (c=#72)and(t>1) then t:=t-1;
• if (c=#80)and(t<4) then t:=t+1;
• until c=#13;
• textcolor(7);
• textbackground(0);
• menu:=t;
• end;
• Procedure Draw;
• begin
• OutTextXY(10,10,#49+#50+#51' - take');
• OutTextXY(10,25,'Esc - exit');
• circle(200,100,20);
• outtextxy(200,100,'2');
• circle(150,200,20);
• outtextxy(150,200,'1');
• circle(200,300,20);
• outtextxy(200,300,'4');
• circle(450,100,20);
• outtextxy(450,100,'3');
• circle(500,200,20);
• outtextxy(500,200,'6');
• circle(450,300,20);
• outtextxy(450,300,'5');
• end;
• Procedure Draw1;
• begin
• OutTextXY(170,140,'3');
• line(200,100+20,150,200-20);
• OutTextXY(170,252,'1');
• line(150,200+20,200,300-20);
• OutTextXY(325,310,'3');
• line(200+20,300,450-20,300);
• OutTextXY(325,110,'3');
• line(200,100+20,200,300-20);
• OutTextXY(210,200,'2');
• line(200+20,100,450-20,100);
• OutTextXY(480,140,'3');
• line(450,100+20,500,200-20);
• OutTextXY(440,200,'1');
• line(450,100+20,450,300-20);
• OutTextXY(480,250,'2');
• line(450,300-20,500,200+20);
• OutTextXY(350,170,'4');
• line(200,100+20,500-20,200);
• OutTextXY(350,260,'3');
• line(150+20,200,450,300-20);
• end;
• Procedure Draw2;
• begin
• line(150,200+20,200,300-20);
• OutTextXY(170,260,'2');
• line(200,100+20,150,200-20);
• OutTextXY(170,140,'1');
• line(450,300-20,500,200+20);
• OutTextXY(475,260,'1');
• line(200,100+20,450,300-20);
• OutTextXY(300,140,'5');
• line(150+20,200,450-20,100);
• OutTextXY(300,170,'3');
• line(200,300-20,450,100+20);
• OutTextXY(300,220,'4');
• line(200+20,300,500-20,200);
• OutTextXY(350,260,'4');
• line(450,100+20,500,200-20);
• OutTextXY(470,130,'3');
• end;
• Procedure Draw3;
• begin
• OutTextXY(170,260,'2');
• OutTextXY(170,140,'1');
• OutTextXY(300,140,'5');
• OutTextXY(475,260,'1');
• OutTextXY(300,170,'3');
• OutTextXY(300,220,'4');
• OutTextXY(350,260,'4');
• OutTextXY(470,130,'3');
• OutTextXY(440,170,'2');
• OutTextXY(190,170,'1');
• line(150,200+20,200,300-20);
• line(200,100+20,150,200-20);
• line(450,300-20,500,200+20);
• line(200,100+20,450,300-20);
• line(150+20,200,450-20,100);
• line(200,300-20,450,100+20);
• line(200+20,300,500-20,200);
• line(450,100+20,500,200-20);
• line(200,100+20,200,300-20);
• line(450,100+20,450,300-20);
• end;
• Function Possible: Boolean;
• Var i: integer;
• Begin
• Possible:=True;
• For i:=1 to n do
• If not Visited[i] then Exit;
• Possible:=False
• End;
• Function Min: Integer;
• Var i, minvalue, currentmin: integer;
• Begin
• Minvalue:=Infinity;
• For i:=1 to n do
• If not Visited[i] then
• If Len[i]<minvalue then
• Begin
• currentmin:=i;
• minvalue:=Len[i]
• End;
• min:=currentmin
• EnD;
• Procedure algor(M:mas);
• begin
• for START:=1 to n do begin
• Writeln('Начальная вершина: ',start);
• writeln;
• For i:=1 to n do
• Begin
• Visited[i]:=False;
• Len[i]:=M[Start, i];
• Path[i]:=Start
• End;
• Path[Start]:=0;
• Visited[Start]:=True;
• for t:=1 to n do begin
• While Possible do
• Begin
• k:=min;
• Visited[k]:=True;
• For i:=1 to n do
• If Len[i]>Len[k]+M[i, k] then
• Begin
• Len[i]:=Len[k]+M[i, k];
• Path[i]:=k
• End
• End;
• finish:=t;
• Write('Конечная вершина: ',Finish);
• Finish:=Path[Finish];
• While Finish<>0 do
• Begin
• Write('<-', Finish);
• Finish:=Path[Finish];
• End;
• if t=n then readln;
• writeln;
• end;
• end;
• ReadKey
• end;
• Begin
• ClrScr;
• while true do
• begin
• mn:=menu;
• case mn of
• 1:BEGIN
• gr:= Detect;
• InitGraph(gr, mn,'c:\bp\units');
• setbkcolor(blue);
• repeat
• OutTextXY(210,40, 'НАЖМИТЕ 1 , 2 ИЛИ 3:');
• Ch:=ReadKey;
• case Ch of
• #49: begin
• cleardevice;
• OutTextXY(10,50,' СХЕМА СЕТИ: №1');
• Draw;
• Draw1;
• end;
• #50: begin
• cleardevice;
• OutTextXY(10,50,'СХЕМА СЕТИ: №2');
• Draw;
• Draw2;
• end;
• #51: begin
• cleardevice;
• OutTextXY(10,50,'СХЕМА СЕТИ: №3');
• Draw;
• Draw3;
• end;
• end;
• until Ch=#27;
• closegraph;
• end;
• 2:BEGIN
• repeat
• clrscr;
• writeln('ДЛЯ ПРОСМОТРА РЕЗУЛЬТОВ АЛГОРИТМА ВЫБЕРЕТЕ № СХЕМЫ');
• WRITEln(' ДЛЯ КОТОРОЙ БУДЕТ ПРОИЗВОДИТЬСЯ РАСЧЕТ' (1 , 2 , 3)');
• WriteLn(' ИЛИ ESC ДЛЯ ВЫХОДА:');
• Ch:=ReadKey;
• case Ch of
• #49:begin
• writeln;
• TEXTCOLOR(red);
• writeln('„‹џ `…'€ ь 1');
• TextColor(lightgray);
• algor(mattr);
• end;
• #50: begin
• writeln;
• TEXTCOLOR(red);
• writeln('„‹џ `…'€ ь 2');
• TextColor(lightgray);
• algor(mattr1);
• end;
• #51: begin
• writeln;
• TEXTCOLOR(red);
• writeln('„‹џ `…'€ ь 3');
• TextColor(lightgray);
• algor(mattr2);
• end;
• end;
• until ch=#27;
• clrscr
• end;
• 3:halt;
• END;
• END;
• End.
• Размещено на Allbest.ru