PDF de programación - Enrutamiento Distance-Vector...

REDES
Área de Ingeniería Telemática

Enrutamiento
Distance-Vector...

Area de Ingeniería Telemática

http://www.tlm.unavarra.es

Redes

4º Ingeniería Informática

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


S
E
D
E
R

e
d



a
e
r
Á

Hoy...

1. Introducción a las redes
2. Tecnologías para redes de área local
3. Conmutación de circuitos
4. Tecnologías para redes de área extensa y última milla
5. Encaminamiento (sesión 2)
• Arquitectura de conmutadores de paquetes
• Control de acceso al medio
• Transporte extremo a extremo

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


S
E
D
E
R

e
d



a
e
r
Á

•



Algoritmo:
Inicializar


Algoritmos para encontrar caminos

Algoritmo de Dijkstra para la distancia mínima
Conocemos: Nodos i Nodo raiz r pesos w(i,j)

•
•
• Mantenemos: d(i) mejor distancia de r al nodo i conocida hasta ahora

T conjunto de nodos a los que ya conocemos la distancia mas corta
d(i) es la distancia menor de r hasta el nodo i pasando solo
por nodos que están en T

d(i)=infinito d(r)=0 si el nodo i es vecino de r [ w(i,r)<infinito ] d(i)=w(i,r)
T={r}


Mientras haya nodos que no pertenezcan a T



elegir el nodo i que no este en T con menor d(i)
añadir el nodo i a T
actualizar d(k) de los nodos vecinos al nodo i que no están en T.



Si d(i)+w(k,i) < d(k) entonces d(k)=d(i)+w(k,i)
[es menor la distancia pasando por i que la que ya tenia]

Dijkstra ejemplo

d(C)

d(D)

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


S
E
D
E
R

e
d



a
e
r
Á

T

{D}

{D,C}

{D,C,F}

{D,C,F,B}

{D,C,F,B,E}

1

B

1

B

1

d(B)

infinito

2

2

2

2

C

3

1

F

1

1

1

1

1

D

2

E

1

4

C

1

3

F

E

4

D

2

0

0

0

0

0

1

B

1

E

1

B

1

d(E)

infinito

4

4

3

3

1

C

3

4

C

3

d(F)

2

2

2

2

2

D

2

F

1

D

2

F

E

4

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



S
E
D
E
R

a
e
r
Á



Algoritmo:
Inicializar


Manteniendo el camino

Usando el algoritmo de Dijkstra para el camino mínimo
Conocemos: Nodos i Nodo raiz r pesos w(i,j)

•
•
• Mantenemos: d(i) mejor distancia de r al nodo i conocida hasta ahora

s(i) siguiente nodo a i en el camino hacia r
T conjunto de nodos a los que ya conocemos la distancia mas corta

d(i)=infinito d(r)=0 si el nodo i es vecino de r [ w(i,r)<infinito ] d(i)=w(i,r)
T={r}
s(i)=desconocido si i es vecino de r [ w(i,r)<infinito ] s(i)=r



Mientras haya nodos que no pertenezcan a T



elegir el nodo i que no este en T con menor d(i)
añadir el nodo i a T
actualizar d(k) de los nodos vecinos al nodo i que no están en T.



Si d(i)+w(k,i) < d(k) entonces d(k)=d(i)+w(k,i)

[si el camino por i es mejor i es el nuevo siguiente salto de k]

y tambien s(k)=i



Dijkstra ejemplo con camino

d(B) / s(B)

d(C) / s(C)

d(D) / s(D)

d(E) / s(E)

d(F) / s(F)

infinito / desc

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


S
E
D
E
R

e
d



a
e
r
Á

T

{D}

{D,C}

{D,C,F}

{D,C,F,B}

{D,C,F,B,E}

infinito / desc

2 / C

2 / C

2 / C

2 / C

1

B

1

B

1

1

C

3

F

E

1

4

C

1

3

F

E

4

1 / D

1 / D

1 / D

1 / D

1 / D

D

2

D

2

0 / soy yo

0 / soy yo

0 / soy yo

0 / soy yo

0 / soy yo

1

B

1

E

1

B

1

4 / C

4 / C

3 / B

3 / B

1

C

3

4

C

3

E

4

2 / D

2 / D

2 / D

2 / D

2 / D

D

2

F

1

D

2

F

Otro algoritmo

Algoritmo de Bellman-Ford
Conocemos: Nodos i Nodo raiz r pesos w(i,j)

•
•
• Mantenemos: dh(i) mejor distancia de r al nodo i conocida hasta ahora

sh(i) siguiente salto del nodo i hacia r (mejor conocido hasta ahora)
h numero de saltos que hemos considerado
dh(i) es la mejor distancia de i al nodo r dando como mucho h saltos

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


S
E
D
E
R

e
d



a
e
r
Á



Algoritmo:
Inicializar


Para h=1,2,3,4 .... hasta cuando?
Para cada uno de los nodos i



d0(i)=infinito d0(r)=0 [en 0 saltos solo desde r se puede llegar a r]
s0(i)=desconocido s0(r)= no hace falta siguiente salto yo soy la raiz

Para cada uno de los nodos k [ vecinos de i ]
dh(i)=min{ dh-1(i)+w(i,k) }
sh(i)= el k con que se obtiene el maximo [ nada si son todos infinito]
[ igual que en el anterior solo que ahora consideramos que puede
haber mejorado el camino de cualquiera de nuestros vecinos]

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á

S
E
D
E
R

Bellman-Ford ejemplo

d(B) / s(B)
infinito / desc
infinito / desc

d(C) / s(C)
infinito / desc

d(D) / s(D)
0 / soy yo

d(E) / s(E)
infinito / desc

d(F) / s(F)
infinito / desc

h
0
1
2
3
4
5 ...

1

C

3

D

2

F

1

B

1

E

4

Para cada nodo por ejemplo para el B

salen todos infinitos

La minima distancia de B a D
dando como mucho un salto es
infinito
no se puede llegar en un salto

d1(B) en la siguiente fila depende de la fila actual y las distancias
d0(B)+w(B,B) d0(C)+w(B,C) d0(D)+w(B,D) d0(E)+w(B,E) d0(F)+w(B,F)
inf + 0 inf + 1 0 + inf inf + 1 inf + inf

•



a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á

S
E
D
E
R

Bellman-Ford ejemplo

d(B) / s(B)
infinito / desc
infinito / desc

d(C) / s(C)
infinito / desc
1 / D

d(D) / s(D)
0 / soy yo

d(E) / s(E)
infinito / desc

d(F) / s(F)
infinito / desc

h
0
1
2
3
4
5 ...

D

2

F

C

3

1

4

1

B

1

E
Para el C

El unico que no sale
infinito es el D con
distancia 1

La minima distancia de C
a D dando como mucho
un salto es 1

d1(C) en la siguiente fila depende de la fila actual
d0(B)+w(C,B) d0(C)+w(C,C) d0(D)+w(C,D) d0(E)+w(C,E) d0(F)+w(C,F)
inf + 1 inf + 0 0 + 1 inf + 3 inf + inf

•



a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


S
E
D
E
R

e
d



a
e
r
Á

Bellman-Ford ejemplo

d(B) / s(B)
infinito / desc
infinito / desc

d(C) / s(C)
infinito / desc
1 / D

d(D) / s(D)
0 / soy yo
0 / soy yo

d(E) / s(E)
infinito / desc
infinito / desc

d(F) / s(F)
infinito / desc
2 / D

h
0
1
2
3
4
5 ...

1

C

3

D

2

F

1

B

1

E

4

•
•

En una iteracion tenemos el arbol de los mejores caminos a D con un salto
En este caso es ya el camino correcto pero no tiene por que ser (si la raiz hubiera
sido C tendriamos que el mejor camino de E a C con un salto es de distancia 3)

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á

S
E
D
E
R

Bellman-Ford ejemplo

d(B) / s(B)
infinito / desc
infinito / desc
2 / C

d(C) / s(C)
infinito / desc
1 / D

d(D) / s(D)
0 / soy yo
0 / soy yo

d(E) / s(E)
infinito / desc
infinito / desc

d(F) / s(F)
infinito / desc
2 / D

h
0
1
2
3
4
5 ...

1

C

3

D

2

F

1

B

1

E

4

Segunda iteración para el B

Ahora a traves de C
tenemos distancia 2

En realidad no hace falta
probar mas que con los
vecinos
En los que no son vecinos
de B siempre dara infinito

d2(B)
d1(B)+w(B,B) d1(C)+w(B,C) d1(D)+w(B,D) d1(E)+w(B,E) d1(F)+w(B,F)
inf + 0 1 + 1 0 + inf inf + 1 2 + inf

Este es B tampoco es vecino

•



a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á

S
E
D
E
R

Bellman-Ford ejemplo

d(B) / s(B)
infinito / desc
infinito / desc
2 / C

d(C) / s(C)
infinito / desc
1 / D
1 / D

d(D) / s(D)
0 / soy yo
0 / soy yo

d(E) / s(E)
infinito / desc
infinito / desc

d(F) / s(F)
infinito / desc
2 / D

h
0
1
2
3
4
5 ...

1

C

3

D

2

F

1

B

1

E

4

Este es C
no es un
candidato

Me vuelve a salir
mejor el camino via D

•



Para cada nodo por ejemplo para el C

d2(C)
d1(B)+w(C,B) d1(C)+w(C,C) d1(D)+w(C,D) d1(E)+w(C,E) d1(F)+w(C,F)
inf + 1 1 + 0 0 + 1 inf + 3 2 + inf

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á

S
E
D
E
R

Bellman-Ford ejemplo

d(B) / s(B)
infinito / desc
infinito / desc
2 / C

d(C) / s(C)
infinito / desc
1 / D
1 / D

d(D) / s(D)
0 / soy yo
0 / soy yo
0 / soy yo

d(E) / s(E)
infinito / desc
infinito / desc
4 / C

d(F) / s(F)
infinito / desc
2 / D

h
0
1
2
3
4
5 ...

E elige entre
ir a traves de C 3+d(C) = 4 <<<< este
ir a traves de F 4+d(F) = 6

1

C

3

D

2

F

1

B

1

E

4

Para cada nodo por ejemplo para el E

d1(B)+w(E,B) d1(C)+w(E,C) d1(D)+w(E,D) d1(E)+w(E,E) d1(F)+w(E,F)
inf + 1 1 + 3 0 + inf inf + 0 2 + 4

B no es un candidato porque el no sabe
como llegar en la iteracion 1

•



a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


S
E
D
E
R

e
d



a
e
r
Á

Bellman-Ford ejemplo

d(B) / s(B)
infinito / desc
infinito / desc
2 / C

d(C) / s(C)
infinito / desc
1 / D
1 / D

d(D) / s(D)
0 / soy yo
0 / soy yo
0 / soy yo

d(E) / s(E)
infinito / desc
infinito / desc
4 / C

d(F) / s(F)
infinito / desc
2 / D
2 / D

h
0
1
2
3
4
5 ...

1

C

3

D

2

F

1

B

1

E

4

•

•
•
•

Al final de la segunda iteración tenemos el arbol de caminos mínimos a D usando
como mucho 2 saltos
Con este ya tenemos un camino desde cada nodo !!!
Aunque esta claro que no son los mejores. Por ejemplo de E llegaríamos antes via B
Cuando acaba el algoritmo???

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


S
E
D
E
R

e
d



a
e
r
Á

Bellman-Ford ejemplo

d(B) / s(B)
infinito / desc
infinito / desc
2 / C

d(C) / s(C)
infinito / desc
1 / D
1 / D

d(D) / s(D)
0 / soy yo
0 / soy yo
0 / soy yo

d(E) / s(E)
infinito / desc
infinito / desc
4 / C

d(F) / s(F)
infinito / desc
2 / D
2 / D

h
0
1
2
3
4
5 ...

•
•

•

•
•
•
•

•

Cuando acaba el algoritmo???
No vale decir cuando tengamos todos los caminos con coste mínimo. Como hacemos
que un programa haga la comprobación?
El objetivo del algoritmo es saber cuales son los caminos de coste minimo, asi que
no podemos usar el conocimiento de cual es el coste minimo para resolverlo
Entonces
El algoritmo calcula cada fila dh en funcion de la fila anterior dh-1
Una vez que una fila se repita... va a seguir repitiendose eternamente...
Esa es la con