cap 01 enrutamiento dinamico-algoritmos

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