Encaminamiento


Encaminamiento

Encaminamiento

Cálculo de una ruta óptima para vehículos entre un punto de origen (en verde) y un punto de destino (en rojo) a partir de cartografía del proyecto OpenStreetMap.

Encaminamiento (o enrutamiento, ruteo) es la función de buscar un camino entre todos los posibles en una red de paquetes cuyas topologías poseen una gran conectividad. Dado que se trata de encontrar la mejor ruta posible, lo primero será definir qué se entiende por mejor ruta y en consecuencia cuál es la métrica que se debe utilizar para medirla.

Contenido

Parámetros

Métrica de la red

Puede ser por ejemplo el número de saltos necesarios para ir de un nodo a otro. Aunque ésta no se trata de una métrica óptima ya que supone “1” para todos los enlaces, es sencilla y suele ofrecer buenos resultados.

Otro tipo es la medición del retardo de tránsito entre nodos vecinos, en la que la métrica se expresa en unidades de tiempo y sus valores no son constantes sino que dependen del tráfico de la red .

Mejor Ruta

Entendemos por mejor ruta aquella que cumple las siguientes condiciones:

  • Presenta el menor retardo medio de tránsito.
  • Consigue mantener acotado el retardo entre pares de nodos de la red.
  • Consigue ofrecer altas cadencias efectivas independientemente del retardo medio de tránsito
  • Permite ofrecer el menor costo.

El criterio más sencillo es elegir el camino más corto, es decir la ruta que pasa por el menor número de nodos. Una generalización de este criterio es el de “coste mínimo”. En general, el concepto de distancia o coste de un canal es una medida de la calidad del enlace basado en la métrica que se haya definido. En la práctica se utilizan varias métricas simultáneamente.

Encaminamiento en redes de circuitos virtuales y de datagramas

Cuando la red de conmutación de paquetes funciona en modo circuito virtual, generalmente la función de encaminamiento establece una ruta que no cambia durante el tiempo de vida de ese circuito virtual. En este caso el encaminamiento se decide por sesión.

Una red que funciona en modo datagrama no tiene el compromiso de garantizar la entrega ordenada de los paquetes, por lo que los nodos pueden cambiar el criterio de encaminamiento para cada paquete que ha de mandar. Cualquier cambio en la topología de la red tiene fácil solución en cuanto a encaminamiento se refiere, una vez que el algoritmo correspondiente haya descubierto el nuevo “camino óptimo”.

Clasificación de los métodos de encaminamiento

Los algoritmos de encaminamiento pueden agruparse en:

Determinísticos o estáticos

No tienen en cuenta el estado de la subred al tomar las decisiones de encaminamiento. Las tablas de encaminamiento de los nodos se configuran de forma manual y permanecen inalterables hasta que no se vuelve a actuar sobre ellas. Por tanto, la adaptación en tiempo real a los cambios de las condiciones de la red es nula.

El cálculo de la ruta óptima es también off-line por lo que no importa ni la complejidad del algoritmo ni el tiempo requerido para su convergencia. Ej: algoritmo de Dijkstra.

Estos algoritmos son rígidos, rápidos y de diseño simple, sin embargo son los que peores decisiones toman en general.

Adaptativos o dinámicos

Pueden hacer más tolerantes a cambios en la subred tales como variaciones en el tráfico, incremento del retardo o fallas en la topología. El encaminamiento dinámico o adaptativo se puede clasificar a su vez en tres categorías, dependiendo de donde se tomen las decisiones y del origen de la información intercambiada:

  • Adaptativo centralizado. Todos los nodos de la red son iguales excepto un nodo central que es quien recoge la información de control y los datos de los demás nodos para calcular con ellos la tabla de encaminamiento. Este método tiene el inconveniente de que consume abundantes recursos de la propia red.
  • Adaptativo distribuido. Este tipo de encaminamiento se caracteriza porque el algoritmo correspondiente se ejecuta por igual en todos los nodos de la subred. Cada nodo recalcula continuamente la tabla de encaminamiento a partir de dicha información y de la que contiene en su propia base de datos. A este tipo pertenecen dos de los más utilizados en Internet que son los algoritmos por vector de distancias y los de estado de enlace.
  • Adaptativo aislado. Se caracterizan por la sencillez del método que utilizan para adaptarse al estado cambiante de la red. Su respuesta a los cambios de tráfico o de topología se obtiene a partir de la información propia y local de cada nodo. Un caso típico es el encaminamiento “por inundación” cuyo mecanismo consiste en reenviar cada paquete recibido con destino a otros nodos, por todos los enlaces excepto por el que llegó.


Tipos de

Encaminamiento

Información

de control

Decisión

de encaminamiento

Adaptación

a los cambios

Determinísticos

ESTÁTICOS

CUASIESTÁTICOS


NO

NO


OFF-LINE

OFF-LINE


NO

REDUCIDA

Adaptativos

CENTRALIZADO

DISTRIBUIDO

AISLADO


NODO CENTRAL

ENTRE NODOS

NO


NODO CENTRAL

CADA NODO

CADA NODO


SI

SI

SI

Encaminamiento adaptativo con algoritmos distribuidos

El encaminamiento mediante algoritmos distribuidos constituye el prototipo de modelo de encaminamiento adaptativo. Los algoritmos se ejecutan en los nodos de la red con los últimos datos que han recibido sobre su estado y convergen rápidamente optimizando sus nuevas rutas.

El resultado es que las tablas de encaminamiento se adaptan automáticamente a los cambios de la red y a las sobrecargas de tráfico. A cambio, los algoritmos tienen una mayor complejidad. Existen dos tipos principales de algoritmos de encaminamiento adaptativo distribuido.

Algoritmos por “vector de distancias”

“Artículo principal: Vector de distancias

Estos métodos utilizan el algoritmo de Bellman-Ford. Busca la ruta de menor coste por el método de búsqueda indirecta El vector de distancias asociado al nodo de una red, es un paquete de control que contiene la distancia a los nodos de la red conocidos hasta el momento.

Cada nodo envía a sus vecinos las distancias que conoce a través de este paquete. Los nodos vecinos examinan esta información y la comparan con la que ya tienen, actualizando su tabla de encaminamiento.

Ejemplos de protocolos por vector de distancias: RIP (versión 1 y 2), IGRP.

Algoritmos de “estado de enlace”

“Artículo principal: Estado de enlace

Este tipo de encaminamiento se basa en que cada nodo llegue a conocer la topología de la red y los costes (retardos) asociados a los enlaces, para que a partir de estos datos, pueda obtener el árbol y la tabla de encaminamiento tras aplicar el algoritmo de coste mínimo (algoritmo de Dijkstra) al grafo de la red

Los protocolos estado de enlace incluyen OSPF e IS-IS.

Protocolos de encaminamiento y sistemas autónomos

En Internet, un sistema autónomo o AS se trata de un conjunto de redes IP y routers que se encuentran bajo el control de una misma entidad (en ocasiones varias) y que poseen una política de encaminamiento similar a Internet. Dependiendo de la relación de un router con un sistema autónomo (AS), encontramos diferentes clasificaciones de protocolos:

1. Protocolos de encaminamiento Ad hoc. Se encuentran en aquellas redes que tienen poca o ninguna infraestructura.

2. IGPs (Interior Gateway Protocols). Intercambian información de encaminamiento dentro de un único sistema autónomo. Los ejemplos más comunes son:

  • IGRP (Interior Gateway Routing Protocol). La diferencia con la RIP es la metrica de enrutamiento
  • EIGRP (Enhanced Interior Gateway Routing Protocol). Es un protocolo de enrutamiento vector-distancia y estado de enlace
  • OSPF (Open Shortest Path First). Enrutamiento jerárquico de pasarela interior
  • RIP (Routing Information Protocol). No soporta conceptos de sistemas autonomos
  • IS-IS (Intermediate System to Intermediate System). Protocolo de intercambio enrutador de sistema intermedio a sistema intermedio

3. EGPs (Exterior Gateway Protocol). Intercambian rutas entre diferentes sistemas autónomos. Encontramos:

  • EGP. Utilizado para conectar la red de backbones de la Antigua Internet.
  • BGP (Border Gateway Protocol). La actual versión, BGPv4 data de 1995.

Véase también

Obtenido de "Encaminamiento"

Wikimedia foundation. 2010.

Mira otros diccionarios:

  • encaminamiento — m. Acción y efecto de encaminar …   Diccionario de la lengua española

  • Encaminamiento — ► sustantivo masculino Acción y resultado de encaminar o encaminarse. SINÓNIMO [encaminadura] * * * encaminamiento. m. Acción y efecto de encaminar. * * * En comunicaciones, el encaminamiento (a veces conocido por el anglicismo ruteo) es el… …   Enciclopedia Universal

  • Encaminamiento jerárquico — Saltar a navegación, búsqueda Encaminamiento jerárquico: Encaminamiento basado en el direccionamiento jerarquizado. Nota: La mayor parte del encaminamiento en TCP/IP se basa ena jerarquía de encaminamientos de dos niveles, según la cual una… …   Wikipedia Español

  • Protocolos de encaminamiento — En una Internet estática y pequeña, las tablas de encaminamiento se pueden crear y mantener manualmente. En Internet mayores los encaminadores mantienen sus propias tablas actualizadas intercambiando información unos con otros. Los encaminadores… …   Enciclopedia Universal

  • Protocolos de encaminamiento — Saltar a navegación, búsqueda Usar archivos por lotesCon los archivos por lotes, que se denominan también programas de proceso por lotes o secuencias de comandos, puede simplificar tareas rutinarias o repetitivas. Un archivo por lotes es un… …   Wikipedia Español

  • EIGRP — Saltar a navegación, búsqueda EIGRP es un protocolo de encaminamiento híbrido, propiedad de Cisco Systems, que ofrece lo mejor de los algoritmos de vector de distancias y del estado de enlace. Se considera un protocolo avanzado que se basa en las …   Wikipedia Español

  • IS-IS — El protocolo IS IS es un protocolo de estado enlace,o SPF (shortest path first), por lo cual, básicamente maneja una especie de mapa con el que se fabrica a medida que converge la red. Es también un protocolo de Gateway interior (IGP). Este… …   Wikipedia Español

  • José Francisco Duato Marín — (Alberique, Valencia, 1958) es un profesor e investigador español galardonado con el Premio Nacional de Investigación Julio Rey Pastor en el año 2009, así como el Premio Rey Jaime I a las nuevas tecnologías en el 2006. Su línea de investigación… …   Wikipedia Español

  • CIDR — Saltar a navegación, búsqueda Classless Inter Domain Routing (CIDR Encaminamiento Inter Dominios sin Clases) se introdujo en 1993 y representa la última mejora en el modo como se interpretan las direcciones IP. Su introducción permitió una mayor… …   Wikipedia Español

  • Certificación Cisco — La Certificación Cisco es un plan de capacitación en tecnología de redes que la empresa Cisco ofrece.[1] Se divide en tres niveles, de menor a mayor complejidad: Cisco Certified Network Associate,Cisco Certified Network Professional y Certificado …   Wikipedia Español