Ddiaz@inictel-uni.edu.pe INSTITUTO NACIONAL DE INVESTIGACION Y CAPACITACION DE TELECOMUNICACIONES,...

transcript

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

012ALGORITMO DE ENRUTAMIENTO:

BELLMAN-FORD Y DIJKSTRA

Palacio Real-España

FACULTAD DE INGENIERIA ELECTRICA Y ELECTRONICA

Profesor Daniel Díaz Ataucuriddiaz@inictel-uni.edu.pe

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

http://neo.lcc.uma.es/evirtual/cdd/tutorial/red/bellman.html

ALGORITMO BELLMAN-FORD

ó Vector Distancia

ALGORITMO BELLMAN-FORD

ó Vector Distancia

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)

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

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

Ds = 0, para todo h(h)

INICIO

Dn = Min [ ] (h+1)

Dj + djn

Para cada sucesivo h≥0

D2 = 2(1)

D3 = 5(1)

D4 = 1(1)

D2 = 2(1)

D3 = 5(1)

D4 = 1(1)

D4 = 4(2)

D3 = 5(2)

D2 = 2(1)

D3 = 5(1)

D4 = 1(1)

D3 = 4(2)

D5 = 2(2)

D2 = 3(2)

D2 = 2(1)

D3 = 5(1)

D4 = 1(1)

5D6 = 10

D5 = 6(2)

D2 = 2(1)

D3 = 5(1)

D4 = 1(1)

D2 = 2(2)

D3 = 4(2)

D4 = 1(2)

5D6 = 10

D5 = 2(2)

D2 = 2(1)

D3 = 5(1)

D4 = 1(1)

D6 = 10

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

D4 = 1(2)

D5 = 2(2)

D3 = 3(3)

D6 = 4(3)

D6 = 4

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

D4 = 1(3)

D5 = 2(3)

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

3A B C

Costo del enlace=1

Costo del

enlace=

Envía su vectorA=0

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)

Enlace 1 Enlace 2

Enlace 6

Enlace 5

3A B C

Costo del enlace=1

Costo del

enlace=

A Local 0

B Local 0

C Local 0

D Local 0

E Local 0

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

vía sus vec-

tores B=

Envía sus vec-tores D=0,A=1 E

Enlace 1 Enlace 2

Enlace 6

Enlace 5

3A B C

Costo del enlace=1

Costo del

enlace=

A Local 0

B Local 0

C Local 0

D Local 0

E Local 0

B 1 1 B 2 1

Envía sus vecto-res A=0,B=1,D=1

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

Enlace 1 Enlace 2

Enlace 6

Enlace 5

3A B C

Costo del enlace=1

Costo del

enlace=

A Local 0

B Local 0

C Local 0

D Local 0

E Local 0

B 1 1 B 2 1

Envía sus v

=0,B=1,A=2

Envía sus vecto-res C=0,B=1,A=2

Enlace 1 Enlace 2

Enlace 6

Enlace 5

3A B C

Costo del enlace=1

Costo del

enlace=

A Local 0

B Local 0

C Local 0

D Local 0

E Local 0

B 1 1 B 2 1

Envía sus vectores

Envía sus

vectores

Vectores E=0, B=1A=2, D=1 y C=1

Enlace 1 Enlace 2

Enlace 6

Enlace 5

3A B C

Costo del enlace=1

Costo del

enlace=

A Local 0

B Local 0

C Local 0

D Local 0

E Local 0

B 1 1 B 2 1

D 5 2E 4 1

Enlace 1 Enlace 2

Enlace 6

Enlace 5

3A B C

Costo del enlace=1

Costo del

enlace=

A Local 0

B Local 0

C Local 0

D Local 0

E Local 0

B 1 1 B 2 1

D 5 2E 4 1

Envía sus vectores

Vectores B=0, A=1D=2, C=1 y E=1

Enlace 1 Enlace 2

Enlace 6

Enlace 5

3A B C

Costo del enlace=1

Costo del

enlace=

A Local 0

B Local 0

C Local 0

D Local 0

E Local 0

B 1 1 B 2 1

D 5 2E 4 1

Por finconverge elalgoritmo

VECTOR DISTANCIA: enlace cortado (1/7)

Enlace 1 Enlace 2

Enlace 6

Enlace 5

3A B C

Costo del enlace=1

Costo del

enlace=

A Local 0

B Local 0

C Local 0

D Local 0

E Local 0

B 1 1 B 2 1

D 5 2E 4 1

Enlace 1 Enlace 2

Enlace 6

Enlace 5

3A B C

Costo del enlace=

Costo del enlace=1

Costo del

enlace=

A Local 0

B Local 0

C Local 0

D Local 0

E Local 0

B 1 B 2 1

D 5 2E 4 1

C 1 E 1

B 3 D 3 2

C 3 E 3

=1 y E

B=0, A= ,D= ,C=1 y E=1

A 4 D 4 C 4 2

A 2 D 2 C 2 2

Enlace 1 Enlace 2

Enlace 6

Enlace 5

3A B C

Costo del enlace=

Costo del enlace=1

Costo del

enlace=

A Local 0

B Local 0

C Local 0

D Local 0

E Local 0

B 1 B 2 1

D 5 2E 4 1

C 1 E 1

D=0, A= 1,B= ,E= 1 y C= 2

B 3 E 3 2

B 6 E 6 2

Enlace 1 Enlace 2

Enlace 6

Enlace 5

3A B C

Costo del enlace=

Costo del enlace=1

Costo del

enlace=

A Local 0

B Local 0

C Local 0

D Local 0

E Local 0

B 1 B 2 1

D 5 2E 4 1

E 3 2C=0, B= 1,A= ,

E= 1 y D= 2

C=0, B= 1,A= ,

E= 1 y D= 2

A 5 E 5 2

A 2 E 2 2

Enlace 1 Enlace 2

Enlace 6

Enlace 5

3A B C

Costo del enlace=

Costo del enlace=1

Costo del

enlace=

A Local 0

B Local 0

C Local 0

D Local 0

E Local 0

B 1 B 2 1

D 5 2E 4 1

= 1 y C

E=0, B= 1,A= 2,D= 1 y C= 1

E=0, B= 1,A= 2,

D= 1 y C= 1

Enlace 1 Enlace 2

Enlace 6

Enlace 5

3A B C

Costo del enlace=

Costo del enlace=1

Costo del

enlace=

A Local 0

B Local 0

C Local 0

D Local 0

E Local 0

B 1 B 2 1

D 5 2E 4 1

E 3 2D

D=0, A= 1,B= 2,E= 1 y C= 2

Enlace 1 Enlace 2

Enlace 6

Enlace 5

3A B C

Costo del enlace=

Costo del enlace=1

Costo del

enlace=

A Local 0

B Local 0

C Local 0

D Local 0

E Local 0

B 3 3 B 2 1

D 5 2E 4 1

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

ALGORITMO DIJKSTRA ó

Estado de Enlace

ALGORITMO DIJKSTRA ó

Estado de Enlace

ALGORITMO DE Dijkstra

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}

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

EJEMPLO DEL ALGORITMO DE Dijkstra

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

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

(2,A) (5,A)

Algoritmo Dijkstra para el nodo de origen A. ► Paso 1

(3,D) (4,D)

(2,A) (5,A)

(3,D) (4,D)