PDF de programación - Tema 2. Algoritmos y protocolos de encaminamiento

1908 – Arquitectura de Redes

Tema 2. Algoritmos y protocolos de

encaminamiento

Pedro M. Ruiz

<[email protected]>

Francisco J. Ros
<[email protected]>

3º Grado en Ingeniería Informática – 2011/2012

Organización del tema

 Introducción al encaminamiento en redes
 Algoritmos de encaminamiento
 Protocolos de encaminamiento en Internet

– Introducción y conceptos fundamentales
– Encaminamiento intradominio (RIP,OSPF)
– Encaminamiento entre dominios (BGP)

Arquitectura de Redes - Universidad de Murcia

2

Organización del tema

 Introducción al encaminamiento en redes
 Algoritmos de encaminamiento
 Protocolos de encaminamiento en Internet

– Introducción y conceptos fundamentales
– Encaminamiento intradominio (RIP,OSPF)
– Encaminamiento entre dominios (BGP)

Arquitectura de Redes - Universidad de Murcia

3

¿En qué consiste el
encaminamiento?

¿Por donde debo

ir a w.x.y.z?

Routers

Arquitectura de Redes - Universidad de Murcia

Source: CS244, Steve McKeown, Stanford University

4

Encaminamiento: Definiciones

Objetivo:

Búsqueda de las rutas en una red que, para todo
origen y destino, satisfagan una serie de condiciones.
Por ejemplo, rutas de mínimo coste económico, de
mínimo retardo, de máxima cadencia eficaz o que
satisfagan algún criterio administrativo.

Algoritmo de encaminamiento:
Método mediante el cual se calculan las rutas
en una red.
Decisión de Encaminamiento:
Si la red es no orientada a conexión la
decisión debe tomarse para cada datagrama.
Si es orientada a conexión, únicamente
durante el establecimiento del circuito
virtual.

Arquitectura de Redes - Universidad de Murcia

Source: Curso de redes DIT-UPM

5

Ejemplo de Encaminamiento

Objetivo: Encontrar la ruta de A a B
que minimiza el coste del camino.

A

Ejemplos de coste:

distancia, capacidad, precio,

congestión/retardo, …

R1

1

2

R2

2

1

R4

4

R6

R3

4

R5

2

3

R7

2

3

R8

B

Arquitectura de Redes - Universidad de Murcia

Source: CS244, Steve McKeown, Stanford University

6

Ejemplo de Encaminamiento

En este caso, la solución es simple por inspección

A

R1

1

2

R2

2

1

R4

4

R6

R3

4

R5

2

3

R7

2

3

R8

B

Arquitectura de Redes - Universidad de Murcia

Source: CS244, Steve McKeown, Stanford University

7

¿Qué tal en esta Red...!?

La Internet Pública en 1999

Arquitectura de Redes - Universidad de Murcia

Fuente:
http://www.lumeta.com

8

Organización del tema

 Introducción al encaminamiento en redes
 Algoritmos de encaminamiento
 Protocolos de encaminamiento en Internet

– Introducción y conceptos fundamentales
– Encaminamiento intradominio (RIP,OSPF)
– Encaminamiento entre dominios (BGP)

Arquitectura de Redes - Universidad de Murcia

9

Propiedades deseables

Corrección
Corrección

Robustez
Robustez

Simplicidad
Simplicidad

Optimalidad
Optimalidad

Estabilidad
Estabilidad

Equidad
Equidad

Arquitectura de Redes - Universidad de Murcia

Source: Curso de Redes, DIT-UPM

10

Tipos de Encaminamiento

 Según QUIÉN DECIDE el camino a seguir:

– Fijado en origen
– Salto a salto

 Según su ADAPTABILIDAD:

– Estáticos
– Cuasi-estáticos
– Adaptativos:

Centralizados
Aislados
Distribuidos

Arquitectura de Redes - Universidad de Murcia

11

Esquemas Generales para

Encaminamiento

 Inundación (flooding)
 Patata caliente (hot potato)
 Routing por el camino más corto

Arquitectura de Redes - Universidad de Murcia

12

Inundación

Los encaminadores envían los paquetes por todas

las interfaces excepto la de entrada.

R1

Ventajas:

Simple.
Todo posible destino es alcanzable.

Inconvenientes:

Algunos encaminadores reciben el paquete
múltiples veces.
Podría haber ciclos si no se usan seqnos.
Ineficiente.

Arquitectura de Redes - Universidad de Murcia

13

Inundación con Spanning Trees

Objetivo: Encontrar ruta de menor costo desde

(R1, …, R7) a R8.

R1

1

2

R2

2

R3

4

1

R4

4

R6

3

R7

R5

2

2

3

R8

Arquitectura de Redes - Universidad de Murcia

Source: CS244, Steve McKeown, Stanford University

14

Solución: Spanning Tree

1

R1

2

R3

1

4

R4

3

R5

2

R7

3

R2

2

4

R6

2

R8

La solución es un spanning tree con R8 como raíz del árbol.
Tree: No hay ciclos.
Spanning: Todos los nodos están incluídos.
Número de envíos N-1 (por definición de árbol).
Veremos que los spanning tree también serán útiles para

encaminar por el camino más corto.

Arquitectura de Redes - Universidad de Murcia

Source: CS244, Steve McKeown, Stanford University

15

Patata Caliente (Hot Potato)

 Routers con capacidad de almacenamiento muy limitada.
 El mensaje se enruta lo antes posible por cualquier enlace

que esté desocupado
– preferentemente el de camino más corto

 Si un nodo tiene d enlaces incidentes no necesita más de

2d paquetes de buffer

 Ventaja:

– Requiere poco almacenamiento por nodo

 Inconvenientes:

– Paquetes podrían llegar desordenados
– Las rutas pueden llegar a ser muy largas
– Podrían producirse ciclos

Arquitectura de Redes - Universidad de Murcia

Source: CS244, Steve McKeown, Stanford University

16

Encaminamiento por el camino más

corto: Definiciones

Coste o Distancia:
puede ser dinámico C = f(t)

A

2

D

6

2

B

1

E

2

4

C

2

F

5

1

G

Métrica: magnitud a optimizar (retardo,
cadencia, coste económico, etc)

Tablas de Encaminamiento:

Nodo F
Nodo F

Destino Siguiente Distancia
Destino Siguiente Distancia

A E
A E

8
8

B C 4
B C 4

C C 2
C C 2

D E 6
D E 6

E E 4
E E 4

F F 0
F F 0

G G 1
G G 1

Arquitectura de Redes - Universidad de Murcia

17

Routing por el Camino más Corto

 A cada enlace i se le asocia una longitud li
 La longitud de un camino ∏ se define como:

∑ li, ∀i ∈ ∏

 En general li ≥0 ∀i ∈ ∏, indicando coste tal como

delay, carga de tráfico, etc.
– Si li=1 ∀i ∈ ∏, entonces min-hop routing.
– Si los li varían con el tiempo, la solución mejora pero

pueden aparecer problemas de convergencia.

 Estudiaremos algoritmos para calcular el camino

más corto en un grafo (Dijkstra, Bellman-Ford,
etc.)

Arquitectura de Redes - Universidad de Murcia

18

Routing por el Camino más Corto (II)

1

R1

2

R3

1

4

R4

3

R5

2

R7

3

R2

2

4

R6

2

R8

El camino más corto entre dos nodos, forma parte del spanning

tree del destino (ej: R2-R8).

Inconvenientes:

Throughput limitado (sólo 1 camino entre S y D)
Adaptación limitada a cambios para evitar oscilaciones

Solución: Optimal Routing

Separa tráfico en puntos estratégicos (múltiples caminos)
Basado en teoría de “optimal multi-commodity flows”.

Arquitectura de Redes - Universidad de Murcia

19

Principio de Optimalidad

 Sea G=(V,E) y sea Πi,j = [vi,vi+1,..,vj-1,vj] el camino

óptimo entre dos vértices vi,vj ∈ V. Entonces, el
camino óptimo entre cualquier vk∈ Πi,j y vj también
está incluido en ese camino.

 Demostración por reducción al absurdo

 Consecuencia:

– El grupo de caminos óptimos desde los nodos de la red
hacia un destino dado, forma un spanning tree cuya raíz
es el destino

Arquitectura de Redes - Universidad de Murcia

20

Ejemplo de Principio de Optimalidad

1

R1

2

R3

1

4

R4

3

R5

2

R7

3

R2

2

4

R6

2

R8

Cualquier subcamino de un camino más corto es también

el camino más corto entre ese par de nodos

La solución es un spanning tree con R8 como raíz del árbol.
Tree: No hay ciclos.
Spanning: Todos los nodos están incluídos

Arquitectura de Redes - Universidad de Murcia

Source: CS244, Steve McKeown, Stanford University

21

Encaminamiento por el camino más
corto: Árboles de encaminamiento

AA

2
DD

6

BB

1
EE

2

2

4

CC

2
FF

5

1

GG

Arbol encaminamiento

nodo A

AA

2
DD

6

BB

1
EE

2

2

4

CC

2
FF

5

1

GG

Arbol encaminamiento

AA

2
DD

6

BB

1
EE

2

2

4

CC

2
FF

5

1

nodo F

GG

Arbol encaminamiento

nodo B

Arquitectura de Redes - Universidad de Murcia

22

Algoritmos para Cálculo de Caminos

más Cortos

CENTRALIZADOS
 Bellman-Ford

– Camino más corto de un nodo al resto

 Dijkstra

– Camino más corto de un nodo al resto

 Floyd-Warshall

– Camino más corto de todos a todos

DISTRIBUIDOS
 Vector de distancias
 Estado de enlace

Nos
centraremos
en estos

Arquitectura de Redes - Universidad de Murcia

23

Algoritmo de Bellman-Ford

 Dado G=(V,E,w). Calcular el camino más corto

entre el nodo s y el resto.

function BellmanFord(list vertices, list edges, vertex source)

for each vertex v in vertices:

if v is source then v.distance := 0
else v.distance := infinity
v.predecessor := null

for i=1 to size(vertices): // |V|-1 iteraciones

for each edge uv in edges: // uv es el enlace de u a v

if v.distance > u.distance + uv.weight:
v.distance := u.distance + uv.weight
v.predecessor := u

for each edge uv in edges:

if v.distance > u.distance + uv.weight:

error "Graph contains a negative-weight cycle"

Arquitectura de Redes - Universidad de Murcia

24

Ejemplo Aplicación Bellman-Ford

Iter.

d[A]

d[B]

d[C]

d[D]

d[E]

d[F]

d[G]

A

3

1

4

3

D

4

B

3

1

C

4

E

2

2

F

5

3

G

0

1

2

3

4

5

6

0

0

0

0

0

0

0

∞

∞

∞

3

3

3

3

3

3

1

1

1

1

1

1

3

2

2

2

2

2

∞

∞

5

4

4

4

4

∞

∞

5

4

4

4

4

Si no hay costes negativos, se puede
Si no hay costes negativos, se puede
parar aquí al no haber más cambios
parar aquí al no haber más cambios

Arq