Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Министерство образования и науки Российской Федерации
Федеральное агентство по образованию
Марийский государственный технический университет
Кафедра ИВС
Отчет по лабораторной работе № 6
Функционирование маршрутизаторов на основе
протокола сетевого уровня OSPF
стека протоколов TCP/IP
по дисциплине
«Сети ЭВМ и телекоммуникации»
Вариант 15
Выполнила : ст. гр. ВМ-41
Кукина Н.В.
Проверил: Смирнов А.В.
Йошкар – Ола
2008
Цель работы
Изучение основных принципов работы, построения, алгоритмов функционирования маршрутизаторов в сетях ЭВМ на основе протокола OSPF.
Исходные данные
Граф сети, в узлах которого расположены маршрутизаторы:
|
№ варианта |
Расстояние между соседними узлами графа - l(i,j) |
№ графа |
№ узла |
|||||||||||||||
|
1,2 |
1,3 |
1,4 |
1,5 |
2,3 |
2,4 |
3,5 |
3,6 |
3,7 |
4,5 |
5,6 |
6,7 |
1,6 |
2,6 |
3,4 |
5,7 |
|||
|
15 |
3 |
- |
- |
- |
3 |
2 |
1 |
- |
3 |
4 |
8 |
6 |
5 |
4 |
2 |
1 |
2 |
2 |
Выполнение работы
Граф сети:
Вычисление кратчайших путей по алгоритму Э.Дейкстры
|
Шаг |
N |
D(1) |
D(3) |
D(4) |
D(5) |
D(6) |
D(7) |
|
Нач. |
{2} |
3 |
3 |
2 |
∞ |
4 |
∞ |
|
1 |
{2,4} |
min[D(1), D(4)+l(4,1)]= min[3, 2+∞]=3 |
min[D(3), D(4)+l(4,3)]= min[3, 2+2]=3 |
2 |
min[D(5), D(4)+l(4,5)]= min[∞, 2+4]=6 |
min[D(6), D(4)+l(4,6)]= min[4, 2+∞]=4 |
min[D(7), D(4)+l(4,7)]= min[∞, 2+∞]=∞ |
|
2 |
{2,4,1} |
3 |
min[D(3), D(1)+l(1,3)]= min[3, 3+∞]=3 |
2 |
min[D(5), D(1)+l(1,5)]= min[6, 3+∞]=6 |
min[D(6), D(1)+l(1,6)]= min[4, 3+5]=4 |
min[D(7), D(1)+l(1,7)]= min[∞, 3+∞]=∞ |
|
3 |
{2,4,1,3} |
3 |
3 |
2 |
min[D(5), D(3)+l(3,5)]= min[6, 3+1]=4 |
min[D(6), D(3)+l(3,6)]= min[4, 3+∞]=4 |
min[D(7), D(3)+l(3,7)]= min[∞, 3+3]=6 |
|
4 |
{2,4,1,3,5} |
3 |
3 |
2 |
4 |
min[D(6), D(5)+l(5,6)]= min[4, 4+8]=4 |
min[D(7), D(5)+l(5,7)]= min[6, 4+1]=5 |
|
5 |
{2,4,1,3,5,6} |
3 |
3 |
2 |
4 |
4 |
min[D(7), D(6)+l(6,7)]= min[5, 4+6]=5 |
|
6 |
{2,4,1,3,5,6,7} |
3 |
3 |
2 |
4 |
4 |
5 |
Вычисление кратчайших путей по алгоритму Флойда
|
Шаг |
Узел |
|||||
|
1 |
3 |
4 |
5 |
6 |
7 |
|
|
Нач. |
(•;∞) |
(•;∞) |
(•;∞) |
(•;∞) |
(•;∞) |
(•;∞) |
|
1 |
min[D(2)+l(2,1), D(6)+l(6,1)]= min[0+3, ∞+5]=3 (2;3) |
min[D(2)+l(2,3), D(4)+l(4,3), D(5)+l(5,3), D(7)+l(7,3)]= min[0+3, ∞+2, ∞+1, ∞+3]=3 (2;3) |
min[D(2)+l(2,4), D(3)+l(3,4), D(5)+l(5,4)]= min[0+2, ∞+2, ∞+4]=2 (2;2) |
min[D(3)+l(3,5), D(4)+l(4,5), D(6)+l(6,5), D(7)+l(7,5)]= min[∞+1, ∞+4, ∞+8, ∞+1]=∞ (•;∞) |
min[D(1)+l(1,6), D(2)+l(2,6), D(5)+l(5,6), D(7)+l(7,6)]= min[∞+5, 0+4, ∞+8, ∞+6]=4 (2;4) |
min[D(3)+l(3,7), D(5)+l(5,7), D(6)+l(6,7)]= min[∞+3, ∞+1, ∞+6]=∞ (•;∞) |
|
2 |
min[D(2)+l(2,1), D(6)+l(6,1)]= min[0+3, 4+5]=3 (2;3) |
min[D(2)+l(2,3), D(4)+l(4,3), D(5)+l(5,3), D(7)+l(7,3)]= min[0+3, 2+2, ∞+1, ∞+3]=3 (2;3) |
min[D(2)+l(2,4), D(3)+l(3,4), D(5)+l(5,4)]= min[0+2, 3+2, ∞+4]=2 (2;2) |
min[D(3)+l(3,5), D(4)+l(4,5), D(6)+l(6,5), D(7)+l(7,5)]= min[3+1, 2+4, 4+8, ∞+1]=4 (3;4) |
min[D(1)+l(1,6), D(2)+l(2,6), D(5)+l(5,6), D(7)+l(7,6)]= min[3+5, 0+4, ∞+8, ∞+6]=4 (2;4) |
min[D(3)+l(3,7), D(5)+l(5,7), D(6)+l(6,7)]= min[3+3, ∞+1, 4+6]=6 (3;6) |
|
3 |
min[D(2)+l(2,1), D(6)+l(6,1)]= min[0+3, 4+5]=3 (2;3) |
min[D(2)+l(2,3), D(4)+l(4,3), D(5)+l(5,3), D(7)+l(7,3)]= min[0+3, 2+2, 4+1, 6+3]=3 (2;3) |
min[D(2)+l(2,4), D(3)+l(3,4), D(5)+l(5,4)]= min[0+2, 3+2, 4+4]=2 (2;2) |
min[D(3)+l(3,5), D(4)+l(4,5), D(6)+l(6,5), D(7)+l(7,5)]= min[3+1, 2+4, 4+8, 6+1]=4 (3;4) |
min[D(1)+l(1,6), D(2)+l(2,6), D(5)+l(5,6), D(7)+l(7,6)]= min[3+5, 0+4, 4+8, 6+6]=4 (2;4) |
min[D(3)+l(3,7), D(5)+l(5,7), D(6)+l(6,7)]= min[3+3, 4+1, 4+6]=5 (5;5) |
|
4 |
min[D(2)+l(2,1), D(6)+l(6,1)]= min[0+3, 4+5]=3 (2;3) |
min[D(2)+l(2,3), D(4)+l(4,3), D(5)+l(5,3), D(7)+l(7,3)]= min[0+3, 2+2, 4+1, 5+3]=3 (2;3) |
min[D(2)+l(2,4), D(3)+l(3,4), D(5)+l(5,4)]= min[0+2, 3+2, 4+4]=2 (2;2) |
min[D(3)+l(3,5), D(4)+l(4,5), D(6)+l(6,5), D(7)+l(7,5)]= min[3+1, 2+4, 4+8, 5+1]=4 (3;4) |
min[D(1)+l(1,6), D(2)+l(2,6), D(5)+l(5,6), D(7)+l(7,6)]= min[3+5, 0+4, 4+8, 5+6]=4 (2;4) |
min[D(3)+l(3,7), D(5)+l(5,7), D(6)+l(6,7)]= min[3+3, 4+1, 4+6]=5 (5;5) |
Алгоритм вычисления кратчайших путей Э.Дейкстры (рис. 1)
Список узлов = {w1, w2, …, wn}
Корень wk
N = {wk}
= {w1, w2, …, wn} \ wk
Для wi D(wi)=l(wi,wk)
N = N U wm : D(wm) = min(D(wi)) wi
= \ wm
Для wi D(wi)=min(D(wi), D(wm)+l(wm,wi))
Алгоритм вычисления кратчайших путей Флойда (рис. 2)
Список узлов N = {w1, w2, …, wn}
Корень wk
N = N \ wk
D(wk)=0
Для wiN D(wi)=∞, n(wi)=0
wi D(wi) =D1(wi), n(wi) =n1(wi)
Для wiN D(wi)= min(D(wj)+l(wj,wi)), n(wi)=j
wj ≠ wi(N U wk)
Обобщенная граф-схема алгоритма функционирования маршрутизатора, согласно протоколу OSPF, представлена на рисунке 3.
Вывод
Дерево крачтайших путей и таблица маршрутов, вычисленные с помощью двух алгоритмов, совпадают.
Полученное дерево кратчайших путей: Таблица маршрутов:
|
Узел- получатель |
Направление передачи (узел) |
|
1 |
1 |
|
3 |
3 |
|
4 |
4 |
|
5 |
3 |
|
6 |
6 |
|
7 |
3 |
Рис. 1. Рис. 2
Рис. 3.