12/05/2010

1

Session 4

Capa 3 - Protocolos de pEnrutamiento

Ruteador• Un ruteador es un dispositivo de

i id d dconectividad que transporta paquetes de datos entre redes, basandose en direcciones lógicas (capa 3).

• Un ruteador tiene la capacidad de tomar decisiones inteligentes con respecto a ladecisiones inteligentes con respecto a la mejor ruta para la entrega de datos en la red.

• El ruteo puede ser dinámico o estático.

12/05/2010

2

Ruteador

Proceso de ruteo

E0 S0

S1

IP 148.204.211.254MAC 00-40-33-2B-35-77

IP 148.204.20.254MAC 67-40-1A-2C-35-77

IP 148.204.45.254MAC 08-40-3A-DD-35-7F

DATOS

Extraer encabezado capa 2IP 148.204.45.32

MAC AD-08-3A-21-DC-11

08-40 3A-DD 35-7F AD-08-3A-21-DC-11 148.204.20.124 148.204.45.32 DATOS

IP 148.204.20.124

MAC 08-A2-FF-43-1D-10

12/05/2010

3

Proceso de ruteo

E0 S0

S1

IP 148.204.211.254MAC 00-40-33-2B-35-77

IP 148.204.20.254MAC 67-40-1A-2C-35-77

IP 148.204.45.254MAC 08-40-3A-DD-35-7F

DATOS

Extraer encabezado capa 2IP 148.204.45.32

MAC AD-08-3A-21-DC-11

148.204.20.124 148.204.45.32 DATOS

IP 148.204.20.124

MAC 08-A2-FF-43-1D-10

Proceso de ruteo

E0 S0

S1

IP 148.204.211.254MAC 00-40-33-2B-35-77

IP 148.204.20.254MAC 67-40-1A-2C-35-77

IP 148.204.45.254MAC 08-40-3A-DD-35-7F

Examinar destino IP

DATOSIP 148.204.45.32

MAC AD-08-3A-21-DC-11

148.204.20.124

IP 148.204.20.124

MAC 08-A2-FF-43-1D-10

12/05/2010

4

Proceso de ruteo

E0 S0

S1

IP 148.204.211.254MAC 00-40-33-2B-35-77

IP 148.204.20.254MAC 67-40-1A-2C-35-77

IP 148.204.45.254MAC 08-40-3A-DD-35-7F

Consultar las tablas de ruteo

DATOSIP 148.204.45.32

MAC AD-08-3A-21-DC-11

148.204.20.124

148.204.45.0

148.204.211.0

148.204.20.0

E0

RED INTERFAZ

S0

S1

Tabla de ruteo

IP 148.204.20.124

MAC 08-A2-FF-43-1D-10

Proceso de ruteo

E0 S0

S1

IP 148.204.211.254MAC 00-40-33-2B-35-77

IP 148.204.20.254MAC 67-40-1A-2C-35-77

IP 148.204.45.254MAC 08-40-3A-DD-35-7F

Enviar datos por S1IP 148.204.45.32

MAC AD-08-3A-21-DC-11

08-A2-FF-43-1D-10 67-40-1A-2C-35-77 148.204.20.124 148.204.45.32 DATOS

DATOS IP 148.204.20.124

MAC 08-A2-FF-43-1D-10

12/05/2010

5

Direccionamiento IP

EstáticoEstático.• Direccionamiento local.• Riguroso control de las direcciones.

DinámicoDinámico• Direccionamiento remoto.• Configuración automática de los parámetros de

red.

Direccionamiento dinámico

• Protocolo de resolución de direcciones inversa (RARP).

• Protocolo BOOTstrap (BOOTP).• Protocolo de configuración dinámica del f g

host (DHCP).

12/05/2010

6

Servicios de red• Orientados a conexión

– Se establece una conexión entre el emisor y el receptor antes de enviar datos.

– Conmutación de circuitos.

• No orientados a conexión• No orientados a conexión– No se establece una conexión previa entre el

emisor y receptor.– Conmutación de paquetes.

Protocolos no enrutables

• Protocolos de capa 2 que no brindan• Protocolos de capa 2 que no brindan capacidades para asignar números de red y números de host.

• Ej. NetBEUI (windows).

12/05/2010

7

Protocolos enrutables

• Protocolos que suministran soporte para la• Protocolos que suministran soporte para la capa de red y cuentan con capacidad de direccionamiento de host y red.

• Ej. IP, IPX/SPX y AppleTalk.

Protocolos de enrutamiento

Protocolos que determinan las rutas queProtocolos que determinan las rutas que siguen los paquetes enrutables (IP, IPX/SPX, AppleTalk) hacia los destinos.

• Protocolo de Información de Enrutamiento (RIP).• Protocolo de Enrutamiento de Compuerta Interior

(IGRP).• Protocolo de Enrutamiento de Compuerta Interior

Mejorado (EIGRP).• Primero la Ruta Libre mas Corta (OSPF).

12/05/2010

8

Enrutamiento multiprotocolo

Algoritmos de Enrutamiento (ruteo, encaminamiento)

• Son la parte del software de la capa de red encargados de decidir la línea de salida (interface) por la que se transmitirá cada paquete que llegue al ruteador.

• En una red de paquetes conmutados la decisión de enrutamiento es por cada paquetedecisión de enrutamiento es por cada paquete.

• En una red de circuitos (vituales) conmutados la decisión de enrutamiento es al momento de negociar/establecer la conexión.

12/05/2010

9

Función de los algoritmos de ruteo• Optimo. • Simplicidad y poco encabezado. • Robustez y estabilidad. • Rápida Convergencia. • Flexibilidad.

¿Cómo seleccionar la mejor ruta?

• En el caso de los algoritmos de ruteo, la mejor ruta depende de la función objetivo que el operador de la red quiera optimizar.

E l l it d t d b• En general, un algoritmo de ruteo debe buscar uno o mas de los siguientes objetivos:

12/05/2010

10

Objetivos de los Algoritmo de Ruteo

• Envío rápido y certero de paquetes.• Adaptabilidad a cambios en la topología de la

red.• Adaptabilidad a cambios en el trafico fuente-

destino.• Capacidad de enrutar paquetes evitando enlaces

congestionados.• Capacidad de determinar la conectividad de laCapacidad de determinar la conectividad de la

red (topología)• Capacidad de evitar loops de enrutamiento.• Baja señalización (overhead)

Clasificación de Algoritmos de Ruteo

• Los algoritmos de ruteo se pueden agrupar• Los algoritmos de ruteo se pueden agrupar en dos grandes categorías:

– Algoritmos No Adaptivos (ruteo estático)

– Algoritmos Adaptivos (ruteo dinámico)

12/05/2010

11

Clasificación de Algoritmos de Ruteo• Los algoritmos de ruteo también se pueden

agrupar en dos grandes categorías:

– Algoritmos Centralizados (ruteo centralizado)– Un centro de control de la red calcula todas

las rutas y las carga en nodos de la red.

– Algoritmos Distribuidos (ruteo distribuido)– Los nodos cooperan independientemente

intercambiando mensajes para hacer sus propios cálculos de rutas.

Algoritmos No Adaptivos (estáticos)

• No basan sus decisiones de enrutamiento en• No basan sus decisiones de enrutamiento en mediciones o estimaciones del trafico y/o topología actuales de la red.

• Es decir, la decisión de ruta para llegar del punto A al punto B se tomará por adelantado o “offline” y se carga en memoria de los ruteadores al momento de iniciar.

12/05/2010

12

Algoritmos Adaptivos (dinámicos)

• Cambian sus decisiones de enrutamiento• Cambian sus decisiones de enrutamiento para reflejar los cambios de topología de la red y por lo general también del trafico.

• Los tipos de algoritmos adaptivos difieren entre si en cuanto al lugar y la frecuencia de cuando/donde obtienen su información, el momento de cambio de sus rutas y la métrica de decisión.

Enrutamiento por la ruta más corta• Se construye un grafo que represente a la

red, cada nodo representa un enrutador y d d l f lí dcada arco del grafo una línea de

comunicación (enlace).

12/05/2010

13

Enrutamiento por la ruta más corta• La manera de medir la longitud de una ruta

es por la cantidad de saltos o la distancia geográfica. También se puede crear una g g pmezcla de métricas para asignar a cada enlace (retardo, ancho de banda, costo, etc.)

Enrutamiento por la ruta más corta• Cada enlace (arco) en la red (grafo) tiene un

“valor” asociado a el que representa el “costo” (o métrica) por usar dicho enlace.( ) p

• Diferentes métricas se pueden asignar a un enlace dependiendo de la función objetivo a optimizar:• Costo ~ 1/ capacidad• Costo ~ retardo de paquetes (tiempo)• Costo ~ carga de trafico• Costo++ ~ (ω11/capacidad) + (ω2retardo) +

(ω3carga)

12/05/2010

14

Enrutamiento por la ruta más corta• Una vez que se define la métrica existen

varios algoritmos para el cálculo de la ruta mas corta entre dos nodos de un grafomas corta entre dos nodos de un grafo.

• Uno de los mas utilizados es el algoritmo de búsqueda de rutas propuesto por E. Dijkstra en 1959.

• Ver animación en:http://en.wikipedia.org/wiki/Dijkstra's_algorithm

Enrutamiento por inundación• Otro algoritmo de enrutamiento estático es

el de la inundación.• Cada paquete de entrada se envía por cadaCada paquete de entrada se envía por cada

una de las líneas de salida, excepto aquella por la que llegó.

• Este algoritmo genera grandes cantidades de paquetes duplicados. Una manera para

i l d devitar saturar la red es poner contadores (TTL) y disminuirlos por cada salto o por medio de etiquetas para evitar enviarlos por segunda vez.

12/05/2010

15

Enrutamiento por inundación• Una versión del algoritmo, un poco más

práctica, es la inundación selectiva donde los enrutadores no envían cada paquete a p qtodas las salidas sino únicamente a aquellas que van aproximándose al destino correcto.

• El algoritmo de inundación siempre escoge la ruta mas corta y es capaz de producir el retardo mas corto (el problema es laretardo mas corto (el problema es la sobrecarga de trafico en la red.

• Ver animación en:http://en.wikipedia.org/wiki/Flooding_algorithm

Enrutamiento Dinámico

• Actualmente las redes de datos l ili l i dgeneralmente utilizan algoritmos de

enrutamiento dinámico.• En particular, dos son los algoritmos de

enrutamiento dinámicos mas importantes:– Enrutamiento por Vector DistanciaEnrutamiento por Vector Distancia– Enrutamiento por Estado Enlace

12/05/2010

16

Enrutamiento por Vector Distancia

• Operan haciendo que cada router (enrutador) mantenga una tabla (vector) que da la mejor di i id d d i l lídistancia conocida a cada destino y la línea (enlace) que puede llegar ahí.

• Estas tablas se actualizan intercambiando información con los routers vecinos.

• Este algoritmo también recibe otros• Este algoritmo también recibe otros nombres:– Algoritmo de Enrutamiento Bellman-Ford (1957)– Algoritmo Ford- Fulkerson (1962)

Enrutamiento por Vector Distancia

• Este algoritmo fue el original algoritmo de enrutamiento utilizado en ARPANET y

bié l b dtambién uso el nombre de RIP.• Las métrica utilizada puede ser la cantidad

de saltos, el retardo de tiempo, el número total de paquetes en los buffers de los routers a lo largo de la ruta, etc.a lo largo de la ruta, etc.

• Ver animación en:http://en.wikipedia.org/wiki/Bellman-Ford_algorithm

12/05/2010

17

Enrutamiento por Vector Distancia

• Algunos protocolos de enrutamiento que utilizan enrutamiento por vector distancia tenemos:

– RIP (Routing Information Protocol)– IGRP (Interior Gateway Protocol)– EIGRP (Enhanced Interior Gateway Protocol)

Enrutamiento por Vector Distancia• El protocolo de enrutamiento EIGRP

desarrollado por CISCO es uno de los mas utilizados actualmente dentro de los sistemasutilizados actualmente dentro de los sistemas autónomos (SA).

• EIGRP utiliza una métrica combinada para calcular los pesos de los enlaces que incluye:– Retardo Total (milisegs)– Ancho de Banda Mínimo (Kbps)– Confiabilidad (rango de 1 a 255)– Carga de Trafico (rango de 1 a 255)

12/05/2010

18

Enrutamiento por Estado Enlace

• Enrutamiento por vector distancia fue utilizado en ARPANET hasta 1979, cuando f l d i dfue reemplazado por enrutamiento estado enlace.

• Principalmente para resolver dos problemas del enrutamiento por vector distancia:– Consideración del Ancho de Banda comoConsideración del Ancho de Banda como

métrica no muy importante (enlaces de 56Kbps).– La tardanza en converger para el calculo de rutas

(problema de la cuenta hasta infinito).

Enrutamiento por Estado Enlace

• La operación de los algoritmos de enrutamiento de estado enlace se puede agrupar en 5 pasos:

• 1) Descubrir a sus vecinos y sus direcciones de red.• 2) Medir el retardo o costo para cada de sus vecinos.• 3) Construir un paquete que indique todo lo anterior.• 4) Enviar dicho paquete a todos los demás enrutadores.• 5) Calcular la ruta mas corta a todos los demás enrutadores.

12/05/2010

19

Enrutamiento por Estado Enlace

• 1) Para descubrir a sus vecinos los routers intercambian paquetes HELLO en cada línea punto a punto.

• 2) Para las mediciones de retardo o costo de los enlaces, los ruters requieren intercambiar paquetes ECHO en cada línea punto a puntopaquetes ECHO en cada línea punto a punto. Se mide el tiempo de ida y vuelta (por ejemplo los ping).

Enrutamiento por Estado Enlace

• 3) La construcción del paquete con la información anterior es fácil. Lo difícil es d idi d d b i idecidir cuando se deben construir y enviar. En general, esto ocurre a intervalos regulares o únicamente cuando ocurra un evento significativo como la caída o reactivación de un enlace y/o un cambio considerable en sus ypropiedades (retardo, ancho de banda, etc.)

12/05/2010

20

Enrutamiento por Estado Enlace

• 4) Para la distribución de los paquetes con información generalmente se utiliza un tipo d i d ió l dde inundación controlada.

• 5) Para la actualización de las rutas con la información nueva, el router puede ejecutar localmente el algoritmo de Dijkstralocalmente el algoritmo de Dijkstra.

Enrutamiento por Estado Enlace

• Algunos protocolos de enrutamiento que utilizan enrutamiento por estado enlace tenemos:

– OSPF (Open Shortest Path First)– IS-IS (Intermediate System to Intermediate System)

12/05/2010

21

• El protocolo de enrutamiento OSPFdesarrollado por IETF es uno de los mas

Enrutamiento por Estado Enlace

putilizados actualmente dentro de los sistemas autónomos (SA).

• Entro en operación en Internet desde 1990.• 1989 propuesto como estándar.• 1998 definido como OSPF v2 para IPv4.• 2008 actualizado como OSPF v3 para IPv6.

Algoritmo vector-distancia

• Visualiza la topología de la red desde la• Visualiza la topología de la red desde la perspectiva del vecino.

• Agrega vectores de distancia de un router a otro.

• Actualizaciones frecuentes y periódicas; f y p ;convergencia lenta.

• Envía copias de la tabla de enrutamiento a los routers vecinos.

12/05/2010

22

Algoritmo estado de enlace

• Obtiene una visión común de toda la• Obtiene una visión común de toda la topología de la red.

• Calcula la ruta mas corta hacia otros routers.

• Actualizaciones disparadas por eventos; p p ;convergencia rápida.

• Envía actualizaciones del enrutamiento por estado de enlace a los otros routers.

Metricas de ruteo

• Ancho de banda• Ancho de banda.• Retardo.• Carga.• Confiabilidad.• Número de saltos.• Costo.

12/05/2010

23

Protocolo RIP• Es un protocolo de enrutamiento vector-

distancia• Utiliza el número de saltos como métrica

para la selección de rutas.• El número de saltos máximo permitido es

15.• Por defecto, envía broadcasts con

actualizaciones de enrutamiento cada 30segundos.

Métrica en RIP

El número de saltos determina la mejor ruta

12/05/2010

24

Protocolo IGRPCaracteristicas Métrica

h d b d• versatilidad que permite manejar automáticamente topologías indefinidas y complejas

• flexibilidad para segmentos con distintas características de ancho de banda y de retardo

• ancho de banda • retardo • carga • confiabilidad • MTU de banda y de retardo

• escalabilidad para operar en redesde gran envergadura

Métrica en IGRP

• La métrica compuesta selecciona la ruta.• La velocidad del enlace es el primer criterio de

adelanto.