Encaminamiento

SC: Encaminamiento Transp. 1

ENCAMINAMIENTO EN REDES DE CONMUTACIÓN DE PAQUETES El problema del encaminamiento
Consiste en cómo establecer una ruta óptima para una instancia de comunicación desde una fuente a un destino. La ruta elegida debe optimizar en lo posible algún parámetro o conjunto de parámetros, como el retardo de tránsito, el número de saltos, el tamaño de las colas, el caudal desalida. . . En general, las decisiones de encaminamiento son incrementales. Cada nodo de conmutación sólo debe decidir a qué nodo adyacente debe transmitir los datos, quedando así establecida la parte correspondiente de la ruta. Para calcular las rutas se usa un algoritmo de encaminamiento, que dado un destino decide la línea de salida adecuada. Es necesario además una estructura de informacióndonde almacenar localmente los pares (destinolínea de salida) resultantes, que recibe el nombre de tabla de encaminamiento. Asímismo, los nodos deben coordinar el cálculo de las rutas e informarse entre sí de los cambios que se produzcan por ejemplo en la topología de la red, tarea que es llevada a cabo por un protocolo de encaminamiento. Propiedades exigibles a los algoritmos de encaminamiento:Deben ser robustos, capaces de adaptarse a los posibles cambios de topología (fallos, bajas o altas en enlaces y nodos) sin necesidad de abortar y reinicializar toda la red. Deben ser estables, en el sentido de converger a un resultado de la forma más rápida posible. No deben generar bucles en el encaminamiento. Si no hay ningún motivo no deben favorecer a algunos usuarios frente a otros.

SC:Encaminamiento Transp. 2

Clasificación de los algoritmos de encaminamiento
Estáticos o no adaptativos: Las rutas son calculadas de antemano y cargadas en los nodos durante su inicialización y permanecen invariantes durante largos períodos de tiempo. Dinámicos o adaptativos: Cambian sus decisiones de encaminamiento para reflejar cambios en la topología y/o en el tráfico. Pueden diferir en losinstantes de adaptación (de manera periódica o cuando cambie de manera significativa la topología o el tráfico) y en la forma de obtener la información y tomar las decisiones: • Aislados: Los nodos basan sus decisiones en información obtenida localmente. • Centralizados: Un nodo de control utiliza la información obtenida de todos los nodos de la red y toma las decisiones de encaminamiento, quetransmite posteriormente al resto de los nodos de la red. • Distribuidos: Las decisiones de encaminamiento se toman localmente en los nodos y se basan en información que obtienen de parte (sólo adyacentes) o de la totalidad del resto de nodos. En las redes actuales el encaminamiento es dinámico y distribuido.

SC: Encaminamiento Transp. 3

Principio de optimización
Si modelamos la red como ungrafo etiquetado, esto es, como una colección de nodos y enlaces punto a punto y a cada enlace le asignamos un valor que representa el coste de enviar un paquete por dicho enlace, que será función de uno o más parámetros según lo que interese optimizar, el coste de una ruta se obtiene a partir de la suma del coste de cada uno de sus enlaces. Principio de optimización: Cualquier subcamino dentro deun camino óptimo es, a su vez, óptimo. Como consecuencia del principio de optimización: El conjunto de rutas óptimas a un destino dado desde cualquier nodo forma un árbol, que puede no ser único, cuya raíz es el nodo destino, y que se conoce como árbol sumidero (sink tree). Las decisiones de encaminamiento se pueden tomar localmente. El cálculo de los caminos óptimos puede llevarse a cabo demanera distribuida. Los algoritmos de encaminamiento intentarán obtener rutas lo más aproximadas a las del árbol sumidero. A continuación se muestra una red de ejemplo y el árbol sumidero para el nodo B, tomando como métrica el número de saltos.

SC: Encaminamiento Transp. 4

B C E F G D J

A

I H N L K

M

O

B C E F G D J

A

I H N L K

M

O

SC: Encaminamiento Transp. 5...