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 [email protected]

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


dd

iaz@

inic

tel-

un

i.e

du

.pe


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


dd

iaz@

inic

tel-

un

i.e

du

.pe


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


dd

iaz@

inic

tel-

un

i.e

du

.pe


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)


dd

iaz@

inic

tel-

un

i.e

du

.pe


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)


dd

iaz@

inic

tel-

un

i.e

du

.pe


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


A Local 0


B Local 0


C Local 0


D Local 0


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


dd

iaz@

inic

tel-

un

i.e

du

.pe


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


A Local 0


B Local 0


C Local 0


D Local 0


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



dd

iaz@

inic

tel-

un

i.e

du

.pe


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


A Local 0


B Local 0


C Local 0


D Local 0


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



dd

iaz@

inic

tel-

un

i.e

du

.pe


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


A Local 0


B Local 0


C Local 0


D Local 0


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



dd

iaz@

inic

tel-

un

i.e

du

.pe


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


A Local 0


B Local 0


C Local 0


D Local 0


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



dd

iaz@

inic

tel-

un

i.e

du

.pe


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


A Local 0


B Local 0


C Local 0


D Local 0


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



dd

iaz@

inic

tel-

un

i.e

du

.pe


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


A Local 0


B Local 0


C Local 0


D Local 0


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



dd

iaz@

inic

tel-

un

i.e

du

.pe


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


A Local 0


B Local 0


C Local 0


D Local 0


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


dd

iaz@

inic

tel-

un

i.e

du

.pe


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=

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


A Local 0


B Local 0


C Local 0


D Local 0


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


dd

iaz@

inic

tel-

un

i.e

du

.pe


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=

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


A Local 0


B Local 0


C Local 0


D Local 0


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


dd

iaz@

inic

tel-

un

i.e

du

.pe


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=

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


A Local 0


B Local 0


C Local 0


D Local 0


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


dd

iaz@

inic

tel-

un

i.e

du

.pe


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=

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


A Local 0


B Local 0


C Local 0


D Local 0


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


dd

iaz@

inic

tel-

un

i.e

du

.pe


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=

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


A Local 0


B Local 0


C Local 0


D Local 0


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


dd

iaz@

inic

tel-

un

i.e

du

.pe


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=

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


A Local 0


B Local 0


C Local 0


D Local 0


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


dd

iaz@

inic

tel-

un

i.e

du

.pe


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


dd

iaz@

inic

tel-

un

i.e

du

.pe


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)


dd

iaz@

inic

tel-

un

i.e

du

.pe


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


dd

iaz@

inic

tel-

un

i.e

du

.pe


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


dd

iaz@

inic

tel-

un

i.e

du

.pe


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. ► Paso 1

(5,A)

B C

(2,A)

(1,A)

A 32

ED 1

(3,D) (4,D)

(2,D)


dd

iaz@

inic

tel-

un

i.e

du

.pe


Pro

pie

da

d i

nte

lec

tua

l d

e D

an

iel

Día

z @

20

12



B C

(2,A) (5,A)

(1,A)

A 32

ED 1

(3,D) (4,D)

(2,D)


0 A 2, A 5, A 1, A ∞ ∞1 AD 2, A 4, D 2,D ∞


dd

iaz@

inic

tel-

un

i.e

du

.pe


Pro

pie

da

d i

nte

lec

tua

l d

e D

an

iel

Día

z @

20

12



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)


dd

iaz@

inic

tel-

un

i.e

du

.pe


Pro

pie

da

d i

nte

lec

tua

l d

e D

an

iel

Día

z @

20

12



(1,A)

A

D

(4,D)

1 F

C

2

(2,D)

E

(3,E)(4,E)


0 A 2, A 5, A 1, A ∞ ∞1 AD 2, A 4, D 2,D ∞

2 ADE 2, A 3, E 4,E


dd

iaz@

inic

tel-

un

i.e

du

.pe


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)



(1,A)

A

D

(4,D)

1 F

C

2

(2,D)

E

(3,E)(4,E)

(5,B)


dd

iaz@

inic

tel-

un

i.e

du

.pe


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)

(5,B)


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


dd

iaz@

inic

tel-

un

i.e

du

.pe


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)

(5,B)

(1,A)

A

D

(2,A)

B

(2,D)

E

C

(3,E)

F

5

(4,E)(8,C)


dd

iaz@

inic

tel-

un

i.e

du

.pe


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

C

(3,E)

F

5

(4,E)(8,C)


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


dd

iaz@

inic

tel-

un

i.e

du

.pe


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

C

(3,E)

F(4,E)


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


dd

iaz@

inic

tel-

un

i.e

du

.pe


Pro

pie

da

d i

nte

lec

tua

l d

e D

an

iel

Día

z @

20

12


Creación de una árbol invertido desde nodo A.


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


dd

iaz@

inic

tel-

un

i.e

du

.pe


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

.........


dd

iaz@

inic

tel-

un

i.e

du

.pe


Pro

pie

da

d i

nte

lec

tua

l d

e D

an

iel

Día

z @

20

12


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.


dd

iaz@

inic

tel-

un

i.e

du

.pe


Pro

pie

da

d i

nte

lec

tua

l d

e D

an

iel

Día

z @

20

12


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


dd

iaz@

inic

tel-

un

i.e

du

.pe


Pro

pie

da

d i

nte

lec

tua

l d

e D

an

iel

Día

z @

20

12

MUCHAS GRACIASMUCHAS GRACIAS

cap 01 enrutamiento dinamico-algoritmos

Documents