[email protected] INSTITUTO NACIONAL DE INVESTIGACION Y CAPACITACION DE TELECOMUNICACIONES,...

dd

iaz@

inic

tel-

un

i.ed

u.p

e

INSTITUTO NACIONAL DE INVESTIGACION Y CAPACITACION DE TELECOMUNICACIONES, INICTEL-UNI

Pro

pie

dad

in

tele

ctu

al d

e D

anie

l D

íaz

@ 2

012ALGORITMO DE ENRUTAMIENTO:

BELLMAN-FORD Y DIJKSTRA

Palacio Real-España

FACULTAD DE INGENIERIA ELECTRICA Y ELECTRONICA

Profesor Daniel Díaz [email protected]

http://www.danieldiaza.com

Catedrático Titular a Tiempo Parcial FIEE-UNI / UNMSMDirector de Investigación y Desarrollo

Tecnológico del INICTEL-UNI

Lima, Agosto-Diciembre de 2012

ALGORITMOS DE ENRUTAMIENTO:BELLMAN-FORD, DIJKSTRA

dd

iaz@

inic

tel-

un

i.ed

u.p

e


Pro

pie

dad

in

tele

ctu

al d

e D

anie

l D

íaz

@ 2



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.ed

u.p

e


Pro

pie

dad

in

tele

ctu

al d

e D

anie

l D

íaz

@ 2



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.ed

u.p

e


Pro

pie

dad

in

tele

ctu

al d

e D

anie

l D

íaz

@ 2



5

2

3

1

2 13

1

5

2

1 6

2 3

4 5

ALGORITMO DE Bellman-Ford:Vector Distancia

d(2,3)=3

d(1,2)=2d(1,

1)=0D3

(1)= 5

d(1,5)= ∞s = nodo fuente

d(i,j) = costo del enlace de i hacia j

h = número máximo de enlace

Dn = costo del camino de menor costo desde el nodo s al nodo n

(h)

Dn = ∞, para todo n ≠ s(0)

Ds = 0, para todo h(h)

INICIO

Dn = Min [ ] (h+1)

Dj + djn

(h)

Para cada sucesivo h≥0

dd

iaz@

inic

tel-

un

i.ed

u.p

e


Pro

pie

dad

in

tele

ctu

al d

e D

anie

l D

íaz

@ 2



h = 1

D2 = 2(1)

D3 = 5(1)

D4 = 1(1)

2 3

4

1

2

5

1

D2 = 2(1)

D3 = 5(1)

D4 = 1(1)

2 3

4

1

2

5

1

3

2

D4 = 4(2)

D3 = 5(2)

D2 = 2(1)

D3 = 5(1)

D4 = 1(1)

2 3

4

1

2

5

1

2 3

51

D3 = 4(2)

D5 = 2(2)

D2 = 3(2)


dd

iaz@

inic

tel-

un

i.ed

u.p

e


Pro

pie

dad

in

tele

ctu

al d

e D

anie

l D

íaz

@ 2



D2 = 2(1)

D3 = 5(1)

D4 = 1(1)

2 3

4

1

2

5

15

16

5D6 = 10

(2)

D5 = 6(2)

D2 = 2(1)

D3 = 5(1)

D4 = 1(1)

2 3

4

1

2

5

1

h = 1

D2 = 2(2)

D3 = 4(2)

D4 = 1(2)

2 3

4

1

2

3

1

6

5D6 = 10

(2)

51

D5 = 2(2)

h = 2


dd

iaz@

inic

tel-

un

i.ed

u.p

e


Pro

pie

dad

in

tele

ctu

al d

e D

anie

l D

íaz

@ 2



D2 = 2(1)

D3 = 5(1)

D4 = 1(1)

2 3

4

1

2

5

1

h = 1

D6 = 10

(2) (2)D2 = 2 D3 = 4

D4 = 1(2)

2 3

4

1

2

3

1

6

5 (2)

51

D5 = 2(2)

1

2

D3 = 3(3)

D6 = 4(3)

D6 = 4

(3) (3)D2 = 2 D3 = 3

D4 = 1(3)

2 3

4

1

2

1

6

3)

51

D5 = 2(3)

1

2

h = 3


dd

iaz@

inic

tel-

un

i.ed

u.p

e


Pro

pie

dad

in

tele

ctu

al d

e D

anie

l D

íaz

@ 2



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.ed

u.p

e


Pro

pie

dad

in

tele

ctu

al d

e D

anie

l D

íaz

@ 2




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.ed

u.p

e


Pro

pie

dad

in

tele

ctu

al d

e D

anie

l D

íaz

@ 2



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.ed

u.p

e


Pro

pie

dad

in

tele

ctu

al d

e D

anie

l D

íaz

@ 2



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.ed

u.p

e


Pro

pie

dad

in

tele

ctu

al d

e D

anie

l D

íaz

@ 2



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.ed

u.p

e


Pro

pie

dad

in

tele

ctu

al d

e D

anie

l D

íaz

@ 2



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.ed

u.p

e


Pro

pie

dad

in

tele

ctu

al d

e D

anie

l D

íaz

@ 2



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.ed

u.p

e


Pro

pie

dad

in

tele

ctu

al d

e D

anie

l D

íaz

@ 2



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.ed

u.p

e


Pro

pie

dad

in

tele

ctu

al d

e D

anie

l D

íaz

@ 2



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.ed

u.p

e


Pro

pie

dad

in

tele

ctu

al d

e D

anie

l D

íaz

@ 2




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.ed

u.p

e


Pro

pie

dad

in

tele

ctu

al d

e D

anie

l D

íaz

@ 2




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.ed

u.p

e


Pro

pie

dad

in

tele

ctu

al d

e D

anie

l D

íaz

@ 2




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.ed

u.p

e


Pro

pie

dad

in

tele

ctu

al d

e D

anie

l D

íaz

@ 2




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.ed

u.p

e


Pro

pie

dad

in

tele

ctu

al d

e D

anie

l D

íaz

@ 2




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.ed

u.p

e


Pro

pie

dad

in

tele

ctu

al d

e D

anie

l D

íaz

@ 2




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.ed

u.p

e


Pro

pie

dad

in

tele

ctu

al d

e D

anie

l D

íaz

@ 2



ALGORITMO DIJKSTRA ó

Estado de Enlace

ALGORITMO DIJKSTRA ó

Estado de Enlace

dd

iaz@

inic

tel-

un

i.ed

u.p

e


Pro

pie

dad

in

tele

ctu

al d

e D

anie

l D

íaz

@ 2



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.ed

u.p

e


Pro

pie

dad

in

tele

ctu

al d

e D

anie

l D

íaz

@ 2



ALGORITMO DE Dijkstra

Para el nodo de origen A:Inicialización:

N = {A}Para todos los nodos v

Si v es adyacente a A Entonces D(v) = c (A,v)Caso contrario D(v) = ∞

Lazo:Encontrar w que no pertenece a N tal que D(w) sea un mínimoAdicionar w a NActualizar D(v) para todo v adyacente a w y no pertenece a N

D(v) = min ( D(v) , D(w) + c(w,v) )/*El nuevo costo a v es ó bien el antiguo costo a v ó el costo del camino más corto a w más el costo de w a v. */Repetir hasta terminar con todos los nodos en N

dd

iaz@

inic

tel-

un

i.ed

u.p

e


Pro

pie

dad

in

tele

ctu

al d

e D

anie

l D

íaz

@ 2



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.ed

u.p

e


Pro

pie

dad

in

tele

ctu

al d

e D

anie

l D

íaz

@ 2



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.ed

u.p

e


Pro

pie

dad

in

tele

ctu

al d

e D

anie

l D

íaz

@ 2




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.ed

u.p

e


Pro

pie

dad

in

tele

ctu

al d

e D

anie

l D

íaz

@ 2





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.ed

u.p

e


Pro

pie

dad

in

tele

ctu

al d

e D

anie

l D

íaz

@ 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)

dd

iaz@

inic

tel-

un

i.ed

u.p

e


Pro

pie

dad

in

tele

ctu

al d

e D

anie

l D

íaz

@ 2





(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.ed

u.p

e


Pro

pie

dad

in

tele

ctu

al d

e D

anie

l D

íaz

@ 2



(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.ed

u.p

e


Pro

pie

dad

in

tele

ctu

al d

e D

anie

l D

íaz

@ 2





(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.ed

u.p

e


Pro

pie

dad

in

tele

ctu

al d

e D

anie

l D

íaz

@ 2





(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.ed

u.p

e


Pro

pie

dad

in

tele

ctu

al d

e D

anie

l D

íaz

@ 2





(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.ed

u.p

e


Pro

pie

dad

in

tele

ctu

al d

e D

anie

l D

íaz

@ 2





(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.ed

u.p

e


Pro

pie

dad

in

tele

ctu

al d

e D

anie

l D

íaz

@ 2




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.ed

u.p

e


Pro

pie

dad

in

tele

ctu

al d

e D

anie

l D

íaz

@ 2



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.ed

u.p

e


Pro

pie

dad

in

tele

ctu

al d

e D

anie

l D

íaz

@ 2




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.ed

u.p

e


Pro

pie

dad

in

tele

ctu

al d

e D

anie

l D

íaz

@ 2




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.ed

u.p

e


Pro

pie

dad

in

tele

ctu

al d

e D

anie

l D

íaz

@ 2



MUCHAS GRACIASMUCHAS GRACIAS

Date post:	31-Dec-2014
Category:	Documents
Upload:	sarita-cerezo
View:	5 times
Download:	0 times

[email protected] INSTITUTO NACIONAL DE INVESTIGACION Y CAPACITACION DE TELECOMUNICACIONES,...

Documents