PDF de programación - Tema 4.2. Encaminamiento

Redes y Servicios de Telecomunicaciones

Tema 4.2. Encaminamiento

Peterson - Davie:
3.3, 3.3.1, 3.3.2, 3.3.3
Tanenbaum 5ªed:
5.2.1, 5.2.2, 5.2.3, 5.2.4, 5.2.5
Portal Moodle

Copyright © 2010, Elsevier Inc. All rights Reserved



1

Contenido

• Grafos de red.
• Principio del camino óptimo.
• Encaminamiento óptimo.

Inundación.

•

• Vector de distancias.
• Estado de los enlaces.
• Grafos en las inter-redes

2

Grafo de encaminamiento

Nodos, enlaces y costes

3

Encaminamiento:

Objetivos y propiedades

 Dados “i”, “j” obtener una ruta (nodo, enlace, nodo, enlace,....) de

coste (global) mínimo

 Algoritmo de “routing” vs “Forwarding”
 Encaminamiento de paquete vs de sesión
 Propiedades del encaminamiento: Correcto, simple, robusto,

estable, justo y óptimo, adaptable (o no) a cambios
topológicos/tráfico

Conflicto: encaminamiento justo y óptimo (¿retardo, caudal?) -> “métrica”
4

Principio del camino óptimo

(a) Una subred
(b) El árbol de rutas para el “router” B

5

Algoritmo del camino más corto (Dijkstra)

Los primeros 5 pasos en el cálculo del camino más corto de “A” a “D”

6

Inundación

• Operación:

• Réplica en cada router

• Características:

• Camino óptimo
• Robustez (si hay camino lo encuentra)
• Baja eficiencia (copias)
• Control de bucles

• Por diámetro de la red (cuenta a cero)
• Control de repeticiones (numeración de paquetes

por “router” origen)

• Uso: militar, señalización, LANs, sistemas

distribuidos (DB)

7

Vector de distancias

(a) Una subred.
(b) Entradas desde “A”, “I”, “H”, “K”, y la nueva tabla para “J”

8

Vector de distancias.

Problema de convergencia

(a) problema de convergencia al aparecer el “router” “A”
(b) problema de “count-to-infinity” al desaparecer el “router” “A”
9

Estado de los enlaces: Fases

Cada “router” debe hacer lo siguiente:
 Descubrir a sus vecinos y aprender sus
direcciones
 Medir la distancia a cada vecino
 Construir un paquete con la información
aprendida
 Enviar ese paquete a todos los demás “routers”
 Calcular el camino más corto a cada uno de los
demás “routers”

10

Estado de los enlaces.

Aprendiendo

(a) 9 routers en una red
(b) Grafo de (a).

11

Estado de los enlaces:
Medida de distancias

Una subred con partes interconectadas por dos enlaces.

12

Estado de los enlaces:
Paquetes de estado

(a) Una subred.
(b) Paquetes de estado de los enlaces en (a)

13

Estado de los enlaces: Distribución

El almacén de paquetes del “router” “B” en la red anterior

14

Grafos en encaminamiento Inter-red
Una Inter-red Su grafo de encaminamiento

• Routers Inter-red => nodos en el grafo
• Troncales entre Routers Inter-red => Enlaces en el grafo
• Subredes con CVs => Un enlace del grafo por CV
• Subredes Difusivas => Nodos virtuales en el grafo.
• Costes a definir: ¿Número de saltos? ¿Retardos? en la Inter-red

15

Resumen

Se ha visto:
• El concepto de grafo de red y los objetivos y

propiedades del encaminamiento.

• El principio del camino óptimo y dos métodos para

obtener el camino más corto: el algoritmo de
Dijkstra y el protocolo de inundación.

• El encaminamiento por vector distancia.
• El encaminamiento por estado de los enlaces
• Los grafos en las inter-redes

16