Post on 27-Oct-2014
description
transcript
ENRUTAMIENTO DINAMICO:Bellman-Ford, Dijkstra
dd
iaz@
inic
tel-
un
i.e
du
.pe
INSTITUTO NACIONAL DE INVESTIGACION Y CAPACITACION DE TELECOMUNICACIONES, INICTEL-UNI
Pro
pie
da
d i
nte
lec
tua
l d
e D
an
iel
Día
z @
20
12
Profesor Daniel Díaz Ataucuriddiaz@inictel-uni.edu.pe
http://www.danieldiaza.com
Catedrático Titular a Tiempo Parcial FIEE-UNIDirector de Investigación y Desarrollo
Tecnológico del INICTEL-UNI
Lima, Marzo-Julio de 2012
Palacio Real-España
MaracanáBrasil
ALGORITMOS DE ENRUTAMIENTODINÁMICO
ENRUTAMIENTO DINAMICO:Bellman-Ford, Dijkstra
dd
iaz@
inic
tel-
un
i.e
du
.pe
INSTITUTO NACIONAL DE INVESTIGACION Y CAPACITACION DE TELECOMUNICACIONES, INICTEL-UNI
Pro
pie
da
d i
nte
lec
tua
l d
e D
an
iel
Día
z @
20
12
LABORATORIO 01: NOTA DE EVALUACION
R1R2 R4
R5
R6
30.1.1.0/30 30.1.1.4/30 30.1.1.8/30
30.1.1.12/30
30.1.1.16/30
30.1.1.28/30
.1 .2
.5
.6 .9
.10
.13
.14
.17 .18
.29
.30
200.1.1.0/24
200.2.2.0/24
200.3.3.0/24
.1
.1
.1
.2
.2
.2
R3
R7
Fa0/0
Fa0/1 Fa0/0 Fa0/1
Fa1/0
Fa0/1
Fa0/1Fa0/0
Fa0/0 Fa0/1Fa1/0
Fa0/0 Fa0/1
Fa0/0
30.1
.1.2
0/30
.21
.22
30.1
.1.2
4/30
.25
.26 Fa1
/0F
a1/1
Las interfaces son referenciales,según criterio el alumno puede considerar otras interfaces.
Fa1/
0
Fa1/
0
Simular con tablasde enrutamiento
estático
Acceder via telnetdesde R2, R3, R4 y R5 hacia R1, R6 y R7
ENRUTAMIENTO DINAMICO:Bellman-Ford, Dijkstra
dd
iaz@
inic
tel-
un
i.e
du
.pe
INSTITUTO NACIONAL DE INVESTIGACION Y CAPACITACION DE TELECOMUNICACIONES, INICTEL-UNI
Pro
pie
da
d i
nte
lec
tua
l d
e D
an
iel
Día
z @
20
12
http://neo.lcc.uma.es/evirtual/cdd/tutorial/red/bellman.html
ALGORITMO BELLMAN-FORD
ó Vector Distancia
ALGORITMO BELLMAN-FORD
ó Vector Distancia
ENRUTAMIENTO DINAMICO:Bellman-Ford, Dijkstra
dd
iaz@
inic
tel-
un
i.e
du
.pe
INSTITUTO NACIONAL DE INVESTIGACION Y CAPACITACION DE TELECOMUNICACIONES, INICTEL-UNI
Pro
pie
da
d i
nte
lec
tua
l d
e D
an
iel
Día
z @
20
12
PROTOCOLOS DE ENRUTAMIENTO
IGP: RIP, IGRP, OSPF, EIGRP IGP: RIP, IGRP, OSPF, EIGRP
EGP: BGP
SISTEMA AUTÓNOMO SISTEMA AUTÓNOMO
RFC 4271: “A Border Gateway Protocol 4 (BGP-4)”http://www.ietf.org/rfc/rfc4271.txt
Dos niveles de jerarquía de enrutamiento:► Dentro del dominio y entre dominios (interdomain routing)
ENRUTAMIENTO DINAMICO:Bellman-Ford, Dijkstra
dd
iaz@
inic
tel-
un
i.e
du
.pe
INSTITUTO NACIONAL DE INVESTIGACION Y CAPACITACION DE TELECOMUNICACIONES, INICTEL-UNI
Pro
pie
da
d i
nte
lec
tua
l d
e D
an
iel
Día
z @
20
12
ALGORITMO BELLMAN-FORD (1/8)
Desde A hacia Enlace Costo
A Local 0
Desde B hacia Enlace Costo
B Local 0
Desde C hacia Enlace Costo
C Local 0
Desde D hacia Enlace Costo
D Local 0
Desde E hacia Enlace Costo
E Local 0
Enlace 1 Enlace 2
Enlace 6
Enlace 5
Enl
ace
3A B C
D EE
nlac
e 4
Costo del enlace=1
Costo del enlace=1
Costo del enlace=1
Costo del
enlace=
1
Cos
to d
el
Enl
ace=
1
Cos
to d
el=
enla
ce 1
Envía su vectorA=0
En
vía
su v
ecto
rA
=0
Adiciona elcosto del enlace
Adiciona elcosto del enlace
Nodo A tiene en su tabla un vector de distancia de A=0Nodo B tiene en su tabla un vector de distancia de B=0Nodo C tiene en su tabla un vector de distancia de C=0Nodo D tiene en su tabla un vector de distancia de D=0Nodo E tiene en su tabla un vector de distancia de E=0
(Vector Distancia)
ENRUTAMIENTO DINAMICO:Bellman-Ford, Dijkstra
dd
iaz@
inic
tel-
un
i.e
du
.pe
INSTITUTO NACIONAL DE INVESTIGACION Y CAPACITACION DE TELECOMUNICACIONES, INICTEL-UNI
Pro
pie
da
d i
nte
lec
tua
l d
e D
an
iel
Día
z @
20
12
ALGORITMO BELLMAN-FORD (2/8)
Enlace 1 Enlace 2
Enlace 6
Enlace 5
Enl
ace
3A B C
D EE
nlac
e 4
Costo del enlace=1
Costo del enlace=1
Costo del enlace=1
Costo del
enlace=
1
Cos
to d
el
Enl
ace=
1
Cos
to d
el
Enl
ace=
1
Desde A hacia Enlace Costo
A Local 0
Desde B hacia Enlace Costo
B Local 0
Desde C hacia Enlace Costo
C Local 0
Desde D hacia Enlace Costo
D Local 0
Desde E hacia Enlace Costo
E Local 0
A 1 1
A 3 1
Nodo B tiene en su tabla dos vectores de distancia de B=0 y A=1Nodo D tiene en su tabla dos vectores de distancia de D=0 y A=1
Envía sus vec-tores B=0,A=1
Envía sus vec-tores B=0,A=1
En
vía sus vec-
tores B=
0,A=
1
B 1 1
A 1 2
B 2 1
A 2 2
B 4 1
A 4 2
Envía sus vec-tores D=0,A=1 E
nví
a su
s ve
c-to
res
D=
0,A
=1
D 3 1
A 3 2
D 6 1
A 6 2
ENRUTAMIENTO DINAMICO:Bellman-Ford, Dijkstra
dd
iaz@
inic
tel-
un
i.e
du
.pe
INSTITUTO NACIONAL DE INVESTIGACION Y CAPACITACION DE TELECOMUNICACIONES, INICTEL-UNI
Pro
pie
da
d i
nte
lec
tua
l d
e D
an
iel
Día
z @
20
12
Enlace 1 Enlace 2
Enlace 6
Enlace 5
Enl
ace
3A B C
D EE
nlac
e 4
Costo del enlace=1
Costo del enlace=1
Costo del enlace=1
Costo del
enlace=
1
Cos
to d
el
Enl
ace=
1
Cos
to d
el
Enl
ace=
1
Desde A hacia Enlace Costo
A Local 0
Desde B hacia Enlace Costo
B Local 0
Desde C hacia Enlace Costo
C Local 0
Desde D hacia Enlace Costo
D Local 0
Desde E hacia Enlace Costo
E Local 0
A 1 1
A 3 1
B 1 1 B 2 1
A 2 2
B 4 1
A 4 2
D 3 1
D 6 1
Envía sus vecto-res A=0,B=1,D=1
En
vía
sus
vect
o-re
s A
=0,
B=
1,D
=1
A 3 1
B 3 2
D 3 2
A 1 1
B 1 2
D 1 2
Nodo A tiene en su tabla tres vectores de distancia de A=0, B=1 y D=1Nodo C tiene en su tabla tres vectores de distancia de C=0, B=1 y A=2
Nodo E tiene en su tabla tres vectores de distancia de E=0, B=1, A=2 y D=1
ALGORITMO BELLMAN-FORD (3/8)
ENRUTAMIENTO DINAMICO:Bellman-Ford, Dijkstra
dd
iaz@
inic
tel-
un
i.e
du
.pe
INSTITUTO NACIONAL DE INVESTIGACION Y CAPACITACION DE TELECOMUNICACIONES, INICTEL-UNI
Pro
pie
da
d i
nte
lec
tua
l d
e D
an
iel
Día
z @
20
12
Enlace 1 Enlace 2
Enlace 6
Enlace 5
Enl
ace
3A B C
D EE
nlac
e 4
Costo del enlace=1
Costo del enlace=1
Costo del enlace=1
Costo del
enlace=
1
Cos
to d
el
Enl
ace=
1
Cos
to d
el
Enl
ace=
1
Desde A hacia Enlace Costo
A Local 0
Desde B hacia Enlace Costo
B Local 0
Desde C hacia Enlace Costo
C Local 0
Desde D hacia Enlace Costo
D Local 0
Desde E hacia Enlace Costo
E Local 0
A 1 1
A 3 1
B 1 1 B 2 1
A 2 2
B 4 1
A 4 2
D 3 1
D 6 1
B 3 2
D 1 2
Envía sus v
ecto-
res C
=0,B=1,A=2
Envía sus vecto-res C=0,B=1,A=2
C 5 1
B 5 2
A 5 3
C 2 1
B 2 2
A 2 3
ALGORITMO BELLMAN-FORD (4/8)
ENRUTAMIENTO DINAMICO:Bellman-Ford, Dijkstra
dd
iaz@
inic
tel-
un
i.e
du
.pe
INSTITUTO NACIONAL DE INVESTIGACION Y CAPACITACION DE TELECOMUNICACIONES, INICTEL-UNI
Pro
pie
da
d i
nte
lec
tua
l d
e D
an
iel
Día
z @
20
12
Enlace 1 Enlace 2
Enlace 6
Enlace 5
Enl
ace
3A B C
D EE
nlac
e 4
Costo del enlace=1
Costo del enlace=1
Costo del enlace=1
Costo del
enlace=
1
Cos
to d
el
Enl
ace=
1
Cos
to d
el
Enl
ace=
1
Desde A hacia Enlace Costo
A Local 0
Desde B hacia Enlace Costo
B Local 0
Desde C hacia Enlace Costo
C Local 0
Desde D hacia Enlace Costo
D Local 0
Desde E hacia Enlace Costo
E Local 0
A 1 1
A 3 1
B 1 1 B 2 1
A 2 2
B 4 1
A 4 2
D 3 1
D 6 1
B 3 2
D 1 2
C 5 1
C 2 1
En
vía
sus
vect
ores
Envía sus vectores
Envía sus
vectores
Vectores E=0, B=1A=2, D=1 y C=1
E 6 1
B 6 2
A 6 3
D 6 2
C 6 2
E 5 1
B 5 2
A 5 3
D 5 2
C 5 2
E 4 1
B 4 2
A 4 3
D 4 2
C 4 2
ALGORITMO BELLMAN-FORD (5/8)
ENRUTAMIENTO DINAMICO:Bellman-Ford, Dijkstra
dd
iaz@
inic
tel-
un
i.e
du
.pe
INSTITUTO NACIONAL DE INVESTIGACION Y CAPACITACION DE TELECOMUNICACIONES, INICTEL-UNI
Pro
pie
da
d i
nte
lec
tua
l d
e D
an
iel
Día
z @
20
12
Enlace 1 Enlace 2
Enlace 6
Enlace 5
Enl
ace
3A B C
D EE
nlac
e 4
Costo del enlace=1
Costo del enlace=1
Costo del enlace=1
Costo del
enlace=
1
Cos
to d
el
Enl
ace=
1
Cos
to d
el
Enl
ace=
1
Desde A hacia Enlace Costo
A Local 0
Desde B hacia Enlace Costo
B Local 0
Desde C hacia Enlace Costo
C Local 0
Desde D hacia Enlace Costo
D Local 0
Desde E hacia Enlace Costo
E Local 0
A 1 1
A 3 1
B 1 1 B 2 1
A 2 2
B 4 1
A 4 2
D 3 1
D 6 1
B 3 2
D 1 2
C 5 1
C 2 1
E 6 1
C 6 2
E 5 1
D 5 2E 4 1
ALGORITMO BELLMAN-FORD (6/8)
ENRUTAMIENTO DINAMICO:Bellman-Ford, Dijkstra
dd
iaz@
inic
tel-
un
i.e
du
.pe
INSTITUTO NACIONAL DE INVESTIGACION Y CAPACITACION DE TELECOMUNICACIONES, INICTEL-UNI
Pro
pie
da
d i
nte
lec
tua
l d
e D
an
iel
Día
z @
20
12
Enlace 1 Enlace 2
Enlace 6
Enlace 5
Enl
ace
3A B C
D EE
nlac
e 4
Costo del enlace=1
Costo del enlace=1
Costo del enlace=1
Costo del
enlace=
1
Cos
to d
el
Enl
ace=
1
Cos
to d
el
Enl
ace=
1
Desde A hacia Enlace Costo
A Local 0
Desde B hacia Enlace Costo
B Local 0
Desde C hacia Enlace Costo
C Local 0
Desde D hacia Enlace Costo
D Local 0
Desde E hacia Enlace Costo
E Local 0
A 1 1
A 3 1
B 1 1 B 2 1
A 2 2
B 4 1
A 4 2
D 3 1
D 6 1
B 3 2
D 1 2
C 5 1
C 2 1
E 6 1
C 6 2
E 5 1
D 5 2E 4 1
Envía sus vectores
Envía sus vectores
En
vía
sus
vect
ores
Vectores B=0, A=1D=2, C=1 y E=1
B 1 1
A 1 2
D 1 3
C 1 2
E 1 2
B 4 1
A 4 2
D 4 3
C 4 2
E 4 2
B 2 1
A 2 2
D 2 3
C 2 2
E 2 2
ALGORITMO BELLMAN-FORD (7/8)
ENRUTAMIENTO DINAMICO:Bellman-Ford, Dijkstra
dd
iaz@
inic
tel-
un
i.e
du
.pe
INSTITUTO NACIONAL DE INVESTIGACION Y CAPACITACION DE TELECOMUNICACIONES, INICTEL-UNI
Pro
pie
da
d i
nte
lec
tua
l d
e D
an
iel
Día
z @
20
12
Enlace 1 Enlace 2
Enlace 6
Enlace 5
Enl
ace
3A B C
D EE
nlac
e 4
Costo del enlace=1
Costo del enlace=1
Costo del enlace=1
Costo del
enlace=
1
Cos
to d
el
Enl
ace=
1
Cos
to d
el
Enl
ace=
1
Desde A hacia Enlace Costo
A Local 0
Desde B hacia Enlace Costo
B Local 0
Desde C hacia Enlace Costo
C Local 0
Desde D hacia Enlace Costo
D Local 0
Desde E hacia Enlace Costo
E Local 0
A 1 1
A 3 1
B 1 1 B 2 1
A 2 2
B 4 1
A 4 2
D 3 1
D 6 1
B 3 2
D 1 2
C 5 1
C 2 1
E 6 1
C 6 2
E 5 1
D 5 2E 4 1
C 1 2
E 1 2
Por finconverge elalgoritmo
ALGORITMO BELLMAN-FORD (8/8)
ENRUTAMIENTO DINAMICO:Bellman-Ford, Dijkstra
dd
iaz@
inic
tel-
un
i.e
du
.pe
INSTITUTO NACIONAL DE INVESTIGACION Y CAPACITACION DE TELECOMUNICACIONES, INICTEL-UNI
Pro
pie
da
d i
nte
lec
tua
l d
e D
an
iel
Día
z @
20
12
VECTOR DISTANCIA: enlace cortado (1/7)
Enlace 1 Enlace 2
Enlace 6
Enlace 5
Enl
ace
3A B C
D EE
nlac
e 4
Costo del enlace=1
Costo del enlace=1
Costo del enlace=1
Costo del
enlace=
1
Cos
to d
el
Enl
ace=
1
Cos
to d
el
Enl
ace=
1
Desde A hacia Enlace Costo
A Local 0
Desde B hacia Enlace Costo
B Local 0
Desde C hacia Enlace Costo
C Local 0
Desde D hacia Enlace Costo
D Local 0
Desde E hacia Enlace Costo
E Local 0
A 1 1
A 3 1
B 1 1 B 2 1
A 2 2
B 4 1
A 4 2
D 3 1
D 6 1
B 3 2
D 1 2
C 5 1
C 2 1
E 6 1
C 6 2
E 5 1
D 5 2E 4 1
C 1 2
E 1 2
ENRUTAMIENTO DINAMICO:Bellman-Ford, Dijkstra
dd
iaz@
inic
tel-
un
i.e
du
.pe
INSTITUTO NACIONAL DE INVESTIGACION Y CAPACITACION DE TELECOMUNICACIONES, INICTEL-UNI
Pro
pie
da
d i
nte
lec
tua
l d
e D
an
iel
Día
z @
20
12
VECTOR DISTANCIA: enlace cortado (2/7)
Enlace 1 Enlace 2
Enlace 6
Enlace 5
Enl
ace
3A B C
D EE
nlac
e 4
Costo del enlace=
Costo del enlace=1
Costo del enlace=1
Costo del
enlace=
1
Cos
to d
el
Enl
ace=
1
Cos
to d
el
Enl
ace=
1
Desde A hacia Enlace Costo
A Local 0
Desde B hacia Enlace Costo
B Local 0
Desde C hacia Enlace Costo
C Local 0
Desde D hacia Enlace Costo
D Local 0
Desde E hacia Enlace Costo
E Local 0
A 1
A 3 1
B 1 B 2 1
A 2 2
B 4 1
A 4 2
D 3 1
D 6 1
B 3 2
D 1
C 5 1
C 2 1
E 6 1
C 6 2
E 5 1
D 5 2E 4 1
C 1 E 1
A=
0, B=
,D
=1,
C=
y E
=
A 3 1
B 3 D 3 2
C 3 E 3
B=
0, A=
,D
=
,C
=1 y E
=1
B=0, A= ,D= ,C=1 y E=1
B 4 1
A 4 D 4 C 4 2
E 4 2
B 2 1
A 2 D 2 C 2 2
E 2 2
ENRUTAMIENTO DINAMICO:Bellman-Ford, Dijkstra
dd
iaz@
inic
tel-
un
i.e
du
.pe
INSTITUTO NACIONAL DE INVESTIGACION Y CAPACITACION DE TELECOMUNICACIONES, INICTEL-UNI
Pro
pie
da
d i
nte
lec
tua
l d
e D
an
iel
Día
z @
20
12
VECTOR DISTANCIA: enlace cortado (3/7)
Enlace 1 Enlace 2
Enlace 6
Enlace 5
Enl
ace
3A B C
D EE
nlac
e 4
Costo del enlace=
Costo del enlace=1
Costo del enlace=1
Costo del
enlace=
1
Cos
to d
el
Enl
ace=
1
Cos
to d
el
Enl
ace=
1
Desde A hacia Enlace Costo
A Local 0
Desde B hacia Enlace Costo
B Local 0
Desde C hacia Enlace Costo
C Local 0
Desde D hacia Enlace Costo
D Local 0
Desde E hacia Enlace Costo
E Local 0
A 1
A 3 1
B 1 B 2 1
A 2
B 4 1
A 4
D 3 1
D 6 1
B 3
D 1
C 5 1
C 2 1
E 6 1
C 6 2
E 5 1
D 5 2E 4 1
C 1 E 1
D=
0, A
= 1
,B=
,
E=
1 y
C=
2
D=0, A= 1,B= ,E= 1 y C= 2
D 3 1
A 3 2
B 3 E 3 2
C 3 3
D 6 1
A 6 2
B 6 E 6 2
C 6 3
ENRUTAMIENTO DINAMICO:Bellman-Ford, Dijkstra
dd
iaz@
inic
tel-
un
i.e
du
.pe
INSTITUTO NACIONAL DE INVESTIGACION Y CAPACITACION DE TELECOMUNICACIONES, INICTEL-UNI
Pro
pie
da
d i
nte
lec
tua
l d
e D
an
iel
Día
z @
20
12
VECTOR DISTANCIA: enlace cortado (4/7)
Enlace 1 Enlace 2
Enlace 6
Enlace 5
Enl
ace
3A B C
D EE
nlac
e 4
Costo del enlace=
Costo del enlace=1
Costo del enlace=1
Costo del
enlace=
1
Cos
to d
el
Enl
ace=
1
Cos
to d
el
Enl
ace=
1
Desde A hacia Enlace Costo
A Local 0
Desde B hacia Enlace Costo
B Local 0
Desde C hacia Enlace Costo
C Local 0
Desde D hacia Enlace Costo
D Local 0
Desde E hacia Enlace Costo
E Local 0
A 1
A 3 1
B 1 B 2 1
A 2
B 4 1
A 6 2
D 3 1
D 6 1
B 3
D 1
C 5 1
C 2 1
E 6 1
C 6 2
E 5 1
D 5 2E 4 1
C 3 3
E 3 2C=0, B= 1,A= ,
E= 1 y D= 2
C=0, B= 1,A= ,
E= 1 y D= 2
C 5 1
B 5 2
A 5 E 5 2
D 5 3
C 2 1
B 2 2
A 2 E 2 2
D 2 3
ENRUTAMIENTO DINAMICO:Bellman-Ford, Dijkstra
dd
iaz@
inic
tel-
un
i.e
du
.pe
INSTITUTO NACIONAL DE INVESTIGACION Y CAPACITACION DE TELECOMUNICACIONES, INICTEL-UNI
Pro
pie
da
d i
nte
lec
tua
l d
e D
an
iel
Día
z @
20
12
VECTOR DISTANCIA: enlace cortado (5/7)
Enlace 1 Enlace 2
Enlace 6
Enlace 5
Enl
ace
3A B C
D EE
nlac
e 4
Costo del enlace=
Costo del enlace=1
Costo del enlace=1
Costo del
enlace=
1
Cos
to d
el
Enl
ace=
1
Cos
to d
el
Enl
ace=
1
Desde A hacia Enlace Costo
A Local 0
Desde B hacia Enlace Costo
B Local 0
Desde C hacia Enlace Costo
C Local 0
Desde D hacia Enlace Costo
D Local 0
Desde E hacia Enlace Costo
E Local 0
A 1
A 3 1
B 1 B 2 1
A 2
B 4 1
A 6 2
D 3 1
D 6 1
B 3
D 2 3
C 5 1
C 2 1
E 6 1
C 6 2
E 5 1
D 5 2E 4 1
C 3 3
E 3 2
E=
0, B=
1,A=
2,D
= 1 y C
= 1
E=0, B= 1,A= 2,D= 1 y C= 1
E=0, B= 1,A= 2,
D= 1 y C= 1
E 6 1
B 6 2
A 6 3
D 6 2
C 6 2
E 5 1
B 5 2
A 5 3
D 5 2
C 5 2
E 4 1
B 4 2
A 4 3
D 4 2
C 4 2
ENRUTAMIENTO DINAMICO:Bellman-Ford, Dijkstra
dd
iaz@
inic
tel-
un
i.e
du
.pe
INSTITUTO NACIONAL DE INVESTIGACION Y CAPACITACION DE TELECOMUNICACIONES, INICTEL-UNI
Pro
pie
da
d i
nte
lec
tua
l d
e D
an
iel
Día
z @
20
12
VECTOR DISTANCIA: enlace cortado (6/7)
Enlace 1 Enlace 2
Enlace 6
Enlace 5
Enl
ace
3A B C
D EE
nlac
e 4
Costo del enlace=
Costo del enlace=1
Costo del enlace=1
Costo del
enlace=
1
Cos
to d
el
Enl
ace=
1
Cos
to d
el
Enl
ace=
1
Desde A hacia Enlace Costo
A Local 0
Desde B hacia Enlace Costo
B Local 0
Desde C hacia Enlace Costo
C Local 0
Desde D hacia Enlace Costo
D Local 0
Desde E hacia Enlace Costo
E Local 0
A 4 3
A 3 1
B 1 B 2 1
A 5 3
B 4 1
A 6 2
D 3 1
D 6 1
B 6 2
D 4 2
C 5 1
C 2 1
E 6 1
C 6 2
E 5 1
D 5 2E 4 1
C 3 3
E 3 2D
=0,
A=
1,B
= 2
,E
= 1
y C
= 2
D=0, A= 1,B= 2,E= 1 y C= 2
D 3 1
A 3 2
B 3 3
E 3 2
C 3 3
D 6 1
A 6 2
B 6 3
E 6 2
C 6 3
ENRUTAMIENTO DINAMICO:Bellman-Ford, Dijkstra
dd
iaz@
inic
tel-
un
i.e
du
.pe
INSTITUTO NACIONAL DE INVESTIGACION Y CAPACITACION DE TELECOMUNICACIONES, INICTEL-UNI
Pro
pie
da
d i
nte
lec
tua
l d
e D
an
iel
Día
z @
20
12
VECTOR DISTANCIA: enlace cortado (7/7)
Enlace 1 Enlace 2
Enlace 6
Enlace 5
Enl
ace
3A B C
D EE
nlac
e 4
Costo del enlace=
Costo del enlace=1
Costo del enlace=1
Costo del
enlace=
1
Cos
to d
el
Enl
ace=
1
Cos
to d
el
Enl
ace=
1
Desde A hacia Enlace Costo
A Local 0
Desde B hacia Enlace Costo
B Local 0
Desde C hacia Enlace Costo
C Local 0
Desde D hacia Enlace Costo
D Local 0
Desde E hacia Enlace Costo
E Local 0
A 4 3
A 3 1
B 3 3 B 2 1
A 5 3
B 4 1
A 6 2
D 3 1
D 6 1
B 6 2
D 4 2
C 5 1
C 2 1
E 6 1
C 6 2
E 5 1
D 5 2E 4 1
C 3 3
E 3 2
Por finconverge elalgoritmo
http://www.it.uc3m.es/~prometeo/rsc/apuntes/encamina/encamina.htmlhttp://catarina.udlap.mx/u_dl_a/tales/documentos/lem/bautista_h_e/capitulo2.pdf
ENRUTAMIENTO DINAMICO:Bellman-Ford, Dijkstra
dd
iaz@
inic
tel-
un
i.e
du
.pe
INSTITUTO NACIONAL DE INVESTIGACION Y CAPACITACION DE TELECOMUNICACIONES, INICTEL-UNI
Pro
pie
da
d i
nte
lec
tua
l d
e D
an
iel
Día
z @
20
12
ALGORITMO DIJKSTRA ó
Estado de Enlace
ALGORITMO DIJKSTRA ó
Estado de Enlace
ENRUTAMIENTO DINAMICO:Bellman-Ford, Dijkstra
dd
iaz@
inic
tel-
un
i.e
du
.pe
INSTITUTO NACIONAL DE INVESTIGACION Y CAPACITACION DE TELECOMUNICACIONES, INICTEL-UNI
Pro
pie
da
d i
nte
lec
tua
l d
e D
an
iel
Día
z @
20
12
ALGORITMO DE Dijkstra
2 4
3 5
1
n-2
n-1
n
i
j
c(i,j)
c(2,4)
c(3,5)
c(1,2)
c(1,3)
c(3,4)
c(2,5)
c(i,j) = Costo del enlace desde el nodo i al nodo j Si los nodos no están directamente conectados c(i,j) = ∞
Por ejemplo, c(1,4) = ∞D(v) = Costo del trayecto desde el nodo origen al destino v actual de menor costo.
Por ejemplo; D(4) = c(1,3) + c(3,4) asumiendo que: c(1,3) + c(3,4) < c(1,2) + c(2,4)
p(v) = Nodo previo, vecino a v, a lo largo del actual camino más corto desde el origen a v. Del ejemplo anterior, el nodo previo al nodo 4 es el nodo 3 = p(4)
N = Grupo de nodos que definen el camino más corto desde el origen. Del ejemplo anterior: N = {1, 3, 4}
D(v)
p(v)
ENRUTAMIENTO DINAMICO:Bellman-Ford, Dijkstra
dd
iaz@
inic
tel-
un
i.e
du
.pe
INSTITUTO NACIONAL DE INVESTIGACION Y CAPACITACION DE TELECOMUNICACIONES, INICTEL-UNI
Pro
pie
da
d i
nte
lec
tua
l d
e D
an
iel
Día
z @
20
12
EJEMPLO DEL ALGORITMO DE Dijkstra
5
2
3
1
2 13
1
5
2
A F
B C
D E
Figura 4.4 del libro “Computer Networking”, J Kurose, pag 302
Matriz de distancia = M (i,j) =
0 2 5 1 ∞ ∞2 0 3 2 ∞ ∞5 3 0 3 1 51 2 3 0 1 ∞∞ ∞ 1 1 0 2∞ ∞ 5 ∞ 2 0
A
B
C
D
E
F
A B C D E F
ENRUTAMIENTO DINAMICO:Bellman-Ford, Dijkstra
dd
iaz@
inic
tel-
un
i.e
du
.pe
INSTITUTO NACIONAL DE INVESTIGACION Y CAPACITACION DE TELECOMUNICACIONES, INICTEL-UNI
Pro
pie
da
d i
nte
lec
tua
l d
e D
an
iel
Día
z @
20
12
Algoritmo Dijkstra para el nodo de origen A.
EJEMPLO DEL ALGORITMO DE DijkstraFigura 4.4 del libro “Computer Networking”, J Kurose, pag 302
Paso N D(B), p(B) D(C), p(C) D(D), p(D) D(E), p(E) D(F), p(F)
0 A 2, A 5, A 1, A ∞ ∞
► Inicialización
B C
D
(2,A) (5,A)
(1,A)
A
ENRUTAMIENTO DINAMICO:Bellman-Ford, Dijkstra
dd
iaz@
inic
tel-
un
i.e
du
.pe
INSTITUTO NACIONAL DE INVESTIGACION Y CAPACITACION DE TELECOMUNICACIONES, INICTEL-UNI
Pro
pie
da
d i
nte
lec
tua
l d
e D
an
iel
Día
z @
20
12
EJEMPLO DEL ALGORITMO DE DijkstraFigura 4.4 del libro “Computer Networking”, J Kurose, pag 302
Algoritmo Dijkstra para el nodo de origen A. ► Paso 1
(5,A)
B C
(2,A)
(1,A)
A 32
ED 1
(3,D) (4,D)
(2,D)
ENRUTAMIENTO DINAMICO:Bellman-Ford, Dijkstra
dd
iaz@
inic
tel-
un
i.e
du
.pe
INSTITUTO NACIONAL DE INVESTIGACION Y CAPACITACION DE TELECOMUNICACIONES, INICTEL-UNI
Pro
pie
da
d i
nte
lec
tua
l d
e D
an
iel
Día
z @
20
12
EJEMPLO DEL ALGORITMO DE DijkstraFigura 4.4 del libro “Computer Networking”, J Kurose, pag 302
Algoritmo Dijkstra para el nodo de origen A. ► Paso 1
B C
(2,A) (5,A)
(1,A)
A 32
ED 1
(3,D) (4,D)
(2,D)
Paso N D(B), p(B) D(C), p(C) D(D), p(D) D(E), p(E) D(F), p(F)
0 A 2, A 5, A 1, A ∞ ∞1 AD 2, A 4, D 2,D ∞
ENRUTAMIENTO DINAMICO:Bellman-Ford, Dijkstra
dd
iaz@
inic
tel-
un
i.e
du
.pe
INSTITUTO NACIONAL DE INVESTIGACION Y CAPACITACION DE TELECOMUNICACIONES, INICTEL-UNI
Pro
pie
da
d i
nte
lec
tua
l d
e D
an
iel
Día
z @
20
12
EJEMPLO DEL ALGORITMO DE DijkstraFigura 4.4 del libro “Computer Networking”, J Kurose, pag 302
Algoritmo Dijkstra para el nodo de origen A. ► Paso 2
B C
(2,A) (5,A)
(1,A)
A 32
ED 1
(3,D) (4,D)
(2,D)
(1,A)
A
D
(4,D)
1 F
C
2
(2,D)
E
(3,E)(4,E)
ENRUTAMIENTO DINAMICO:Bellman-Ford, Dijkstra
dd
iaz@
inic
tel-
un
i.e
du
.pe
INSTITUTO NACIONAL DE INVESTIGACION Y CAPACITACION DE TELECOMUNICACIONES, INICTEL-UNI
Pro
pie
da
d i
nte
lec
tua
l d
e D
an
iel
Día
z @
20
12
EJEMPLO DEL ALGORITMO DE DijkstraFigura 4.4 del libro “Computer Networking”, J Kurose, pag 302
Algoritmo Dijkstra para el nodo de origen A. ► Paso 2
(1,A)
A
D
(4,D)
1 F
C
2
(2,D)
E
(3,E)(4,E)
Paso N D(B), p(B) D(C), p(C) D(D), p(D) D(E), p(E) D(F), p(F)
0 A 2, A 5, A 1, A ∞ ∞1 AD 2, A 4, D 2,D ∞
2 ADE 2, A 3, E 4,E
ENRUTAMIENTO DINAMICO:Bellman-Ford, Dijkstra
dd
iaz@
inic
tel-
un
i.e
du
.pe
INSTITUTO NACIONAL DE INVESTIGACION Y CAPACITACION DE TELECOMUNICACIONES, INICTEL-UNI
Pro
pie
da
d i
nte
lec
tua
l d
e D
an
iel
Día
z @
20
12
(1,A)
A
D
(2,A)
B
(2,D)
E
C3
(3,E)
EJEMPLO DEL ALGORITMO DE DijkstraFigura 4.4 del libro “Computer Networking”, J Kurose, pag 302
Algoritmo Dijkstra para el nodo de origen A. ► Paso 3
(1,A)
A
D
(4,D)
1 F
C
2
(2,D)
E
(3,E)(4,E)
(5,B)
ENRUTAMIENTO DINAMICO:Bellman-Ford, Dijkstra
dd
iaz@
inic
tel-
un
i.e
du
.pe
INSTITUTO NACIONAL DE INVESTIGACION Y CAPACITACION DE TELECOMUNICACIONES, INICTEL-UNI
Pro
pie
da
d i
nte
lec
tua
l d
e D
an
iel
Día
z @
20
12
EJEMPLO DEL ALGORITMO DE DijkstraFigura 4.4 del libro “Computer Networking”, J Kurose, pag 302
Algoritmo Dijkstra para el nodo de origen A. ► Paso 3
(1,A)
A
D
(2,A)
B
(2,D)
E
C3
(3,E)
(5,B)
Paso N D(B), p(B) D(C), p(C) D(D), p(D) D(E), p(E) D(F), p(F)
0 A 2, A 5, A 1, A ∞ ∞1 AD 2, A 4, D 2,D ∞
2 ADE 2, A 3, E 4,E3 ADEB 3, E 4,E
ENRUTAMIENTO DINAMICO:Bellman-Ford, Dijkstra
dd
iaz@
inic
tel-
un
i.e
du
.pe
INSTITUTO NACIONAL DE INVESTIGACION Y CAPACITACION DE TELECOMUNICACIONES, INICTEL-UNI
Pro
pie
da
d i
nte
lec
tua
l d
e D
an
iel
Día
z @
20
12
EJEMPLO DEL ALGORITMO DE DijkstraFigura 4.4 del libro “Computer Networking”, J Kurose, pag 302
Algoritmo Dijkstra para el nodo de origen A. ► Paso 4
(1,A)
A
D
(2,A)
B
(2,D)
E
C3
(3,E)
(5,B)
(1,A)
A
D
(2,A)
B
(2,D)
E
C
(3,E)
F
5
(4,E)(8,C)
ENRUTAMIENTO DINAMICO:Bellman-Ford, Dijkstra
dd
iaz@
inic
tel-
un
i.e
du
.pe
INSTITUTO NACIONAL DE INVESTIGACION Y CAPACITACION DE TELECOMUNICACIONES, INICTEL-UNI
Pro
pie
da
d i
nte
lec
tua
l d
e D
an
iel
Día
z @
20
12
EJEMPLO DEL ALGORITMO DE DijkstraFigura 4.4 del libro “Computer Networking”, J Kurose, pag 302
Algoritmo Dijkstra para el nodo de origen A. ► Paso 4
(1,A)
A
D
(2,A)
B
(2,D)
E
C
(3,E)
F
5
(4,E)(8,C)
Paso N D(B), p(B) D(C), p(C) D(D), p(D) D(E), p(E) D(F), p(F)
0 A 2, A 5, A 1, A ∞ ∞1 AD 2, A 4, D 2,D ∞
2 ADE 2, A 3, E 4,E3 ADEB 3, E 4,E4 ADEBC 4,E
ENRUTAMIENTO DINAMICO:Bellman-Ford, Dijkstra
dd
iaz@
inic
tel-
un
i.e
du
.pe
INSTITUTO NACIONAL DE INVESTIGACION Y CAPACITACION DE TELECOMUNICACIONES, INICTEL-UNI
Pro
pie
da
d i
nte
lec
tua
l d
e D
an
iel
Día
z @
20
12
EJEMPLO DEL ALGORITMO DE DijkstraFigura 4.4 del libro “Computer Networking”, J Kurose, pag 302
Algoritmo Dijkstra para el nodo de origen A. ► Paso 5
(1,A)
A
D
(2,A)
B
(2,D)
E
C
(3,E)
F(4,E)
Paso N D(B), p(B) D(C), p(C) D(D), p(D) D(E), p(E) D(F), p(F)
0 A 2, A 5, A 1, A ∞ ∞1 AD 2, A 4, D 2,D ∞
2 ADE 2, A 3, E 4,E3 ADEB 3, E 4,E4 ADEBC 4,E5 ADEBCF 4,E
ENRUTAMIENTO DINAMICO:Bellman-Ford, Dijkstra
dd
iaz@
inic
tel-
un
i.e
du
.pe
INSTITUTO NACIONAL DE INVESTIGACION Y CAPACITACION DE TELECOMUNICACIONES, INICTEL-UNI
Pro
pie
da
d i
nte
lec
tua
l d
e D
an
iel
Día
z @
20
12
EJEMPLO DEL ALGORITMO DE DijkstraFigura 4.4 del libro “Computer Networking”, J Kurose, pag 302
Creación de una árbol invertido desde nodo A.
Paso N D(B), p(B) D(C), p(C) D(D), p(D) D(E), p(E) D(F), p(F)
0 A 2, A 5, A 1, A ∞ ∞1 AD 2, A 4, D 2,D ∞
2 ADE 2, A 3, E 4,E3 ADEB 3, E 4,E4 ADEBC 4,E5 ADEBCF 4,E
B D
A2 1
E
1
C F
1 2
ENRUTAMIENTO DINAMICO:Bellman-Ford, Dijkstra
dd
iaz@
inic
tel-
un
i.e
du
.pe
INSTITUTO NACIONAL DE INVESTIGACION Y CAPACITACION DE TELECOMUNICACIONES, INICTEL-UNI
Pro
pie
da
d i
nte
lec
tua
l d
e D
an
iel
Día
z @
20
12
IMPLEMENTACION DEL ALGORITMODE DIJKSTRA
Los routers deben conocer sus vecinos
► El router A debe conocer la existencia de los routers B, C y D.
► El router A debe enviar protocolo de descubrimiento.
HELLO
HELLO
Cada router forma una base de datos con susrouters vecinos.
ARouter BRouter CRouter D
BRouter ARouter CRouter D
F Router CRouter E
.........
ENRUTAMIENTO DINAMICO:Bellman-Ford, Dijkstra
dd
iaz@
inic
tel-
un
i.e
du
.pe
INSTITUTO NACIONAL DE INVESTIGACION Y CAPACITACION DE TELECOMUNICACIONES, INICTEL-UNI
Pro
pie
da
d i
nte
lec
tua
l d
e D
an
iel
Día
z @
20
12
IMPLEMENTACION DEL ALGORITMODE DIJKSTRA
Cada routers envía sus estados a sus routers vecinos►Costo, máscara de enlace WAN, dirección IP, etc.
5
2
3
1
2 13
1
5
2
A F
B C
D E
Estado A
Estado A Estado C
►Cada router contiene una base de datos con los estados de los demás routers. Esta base de datos es idéntica en toda la red.
ENRUTAMIENTO DINAMICO:Bellman-Ford, Dijkstra
dd
iaz@
inic
tel-
un
i.e
du
.pe
INSTITUTO NACIONAL DE INVESTIGACION Y CAPACITACION DE TELECOMUNICACIONES, INICTEL-UNI
Pro
pie
da
d i
nte
lec
tua
l d
e D
an
iel
Día
z @
20
12
IMPLEMENTACION DEL ALGORITMODE DIJKSTRA
5
2
3
1
2 13
1
5
2
A F
B C
D E
► Es obtiene una topología de árbol invertido por router.
Estadosde todos
los routers
Estadosde todos
los routersEstadosde todos
los routers
Estadosde todos
los routers
Estadosde todos
los routers
Estadosde todos
los routers
En cada router se aplica el algoritmo de Dijkstra.
B D
A2 1
E
1
C F
1 2
ENRUTAMIENTO DINAMICO:Bellman-Ford, Dijkstra
dd
iaz@
inic
tel-
un
i.e
du
.pe
INSTITUTO NACIONAL DE INVESTIGACION Y CAPACITACION DE TELECOMUNICACIONES, INICTEL-UNI
Pro
pie
da
d i
nte
lec
tua
l d
e D
an
iel
Día
z @
20
12
MUCHAS GRACIASMUCHAS GRACIAS