Pasos SPF

Pasos Algoritmo Dijkstra
1.- PASO 0 (INICIACIÓN):

2.- PASO 1:
Encontramos
Puede existir un empate, en tal caso se elige
uno arbitrariamente o de acuerdo a un
criterio marcado
Si P contiene a todos los nodos se para, si no
continuamos con el paso 3.

3.- PASO 2
(ACTUALIZACIÓN):

- Redes y Servicios de Comunicaciones 1

Algoritmos de encaminamiento

EJEMPLO DIJKSTRA
1

2

13

1

3

2

6

1

4

4

4

1

P = {_, _} T = {_, _, _, _}
D1K = {_, _, _, _, _, _}

Tenc = {_, _, _, _, _, _ }

P = {1} T = {2,3,4,5,6}
D1K = {0,1, −,4,−,−}

Tenc = {1,2,−,4,−, −}

5
P = {_, _, _ } T = {_, _, _}
D1K = {_, _, _, _, _, _}

Tenc = {_, _, _, _, _, _ }

P = {_, _, _, _, _} T = {_}
D1K = {_, _, _, _, _, _}

Tenc = {_, _, _, _, _, _ }

P = {_,_, _, _ } T = {_, _}
D1K = {_, _, _, _, _, _}

Tenc = {_, _, _, _, _, _ }

P = {_, _, _, _, _, _} T = {
D1K = {_, _, _, _, _, _ }

}

Tenc = {_, _, _, _, _, _}

- Redes y Servicios de Comunicaciones 2

1

Algoritmos de encaminamiento

EJEMPLO DIJKSTRA
1

2

1

3

1

3

2

6

1

4

4

4

1

P = {1, 2} T = {3,4 ,5,6}
D1K = {0,1,4 ,4, 2, −}

Tenc = {1,2, 2,4, 2, −}

P = {1} T = {2,3,4,5,6}
D1K = {0,1, −,4,−,−}

Tenc = {1,2,−,4,−, −}

5
P = {1, 2,5} T = {3, 4,6}
D1K = {0,1,3,3,2, 6}

Tenc = {1, 2, 2.5, 2.5, 2, 2.5}

P = {1, 2,5,4 ,3} T = {6}
D1K = {0 ,1,3,3,2,5}

Tenc = {1, 2,2 .5,2 .5, 2,2 .5. 3}

P = {1, 2,5, 4} T = {3,6}
D1K = {0,1,3,3,2, 6}

Tenc = {1, 2, 2.5, 2.5, 2, 2.5}

P = {1, 2,5, 4,3,6} T = {
D1K = {0,1,3,3,2,5}

}

Tenc = {1, 2, 2.5, 2. 5,2, 2.5 .3}
- Redes y Servicios de Comunicaciones 3

Pasos Algoritmo Floyd-Warshall
1.- PASO 0 (INICIACIÓN):

Nota:

2.- PASO 1: (ITERACIÓN)

Es el camino del nodo “i” al nodo “j” pasando por n nodos
intermedios

- Redes y Servicios de Comunicaciones 4

2

Algoritmos de encaminamiento

EJEMPLO FLOYD-WARSHALL
2

1

1

3

4

3

22

1

5 1

4

0
2. Inter. 1 y 2 
≡ Inter. 1,2 y 3  1
5

3
2


1. Inicialización  0
≡ Intermedio 1  1
−

−

2

1 5 3 2
0
 3. Inter. 1,2,3 y 4 
0 4 2 3  ≡ Inter. 1,2,3,4 y 5  1
4
4 0 1 7


2 1 0 1
3

2
3 7 1 0


1 − −
0 4

2

4 0

1

2 1
3 −

0
1

2

3
−

1

0

1 4 3 2

0 3 2 3
3 0 1 2
2 1 0 1
3 2 1 0 

- Redes y Servicios de Comunicaciones 5

Pasos Algoritmo BellMan-Ford
1.- PASO 0 (INICIACIÓN):

2.- PASO 1: (ITERACIÓN)

Nota: “n” es el número de saltos
d i,j es la distancia entre nodos contiguos
Di,j es la distancia entre dos nodos no contiguos

- Redes y Servicios de Comunicaciones 6

3

Algoritmos de encaminamiento

EJEMPLO BELLMAN-FORD
1

1

28

2 1

4
2

2
1

4

4

3
2

2

4

1

3

5
2

4

1
3

5

2

4

3

5

1
3

5

- Redes y Servicios de Comunicaciones 7

Pasos Algoritmo BellMan-Ford Distribuido
1.- PASO 0 (INICIACIÓN):

2.- PASO 1: (ACTUALIZACIÓN)
cada cierto tiempo, el nodo 'i' envía a sus vecinos D(i,j),
recibiendo a su vez de todos sus vecinos 'j' los D(j,k).
Entonces,el nodo 'i' calcula la distancia de 'i' a 'k' pasando
por 'j':

y realiza la siguiente actualización de su tabla de
encaminamiento:

Nota:

- Redes y Servicios de Comunicaciones 8

4

Algoritmos de encaminamiento

EJEMPLO BELLMAN-FORD DISTRIBUIDO
B

A

C

1

B

VDA=(0A)
VDB=(0B)
VDC=(0C)
VDD=(0D)

1
1

D

1

Inicialización

VDA=(0A, 1B, 1C)

C
AVDB=(1A, 0B, 1C)

C

A

VDC=(1A, 1B, 0C , 1D)

B
D

VDD=(1B, 0D)

C

Arranque

∞
dA-C+dC-D=2C

A

VDA =(0A , 1B, 1C, 2C)
VDB =(1A , 0B, 1C , 2C)
VDC =(1A , 1B, 0C , 1D )
VDD =(2C, 2C , 1C , 0D )

VDA =(0A , 1B, 1C, 2C)
1B
dA-B+dB-B=1B
dA-C+dC-B=2C

1C
1C= dA-C+dC-C
2B= dA-B+dB-C
- Redes y Servicios de Comunicaciones 9

N12

Ejemplo de OSPF

N1

3

RT1 1...