Encaminamiento

Encaminamiento

El encaminamiento, enrutamiento o 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 y en consecuencia cuál es la métrica que se debe utilizar para medirla

La red debe encontrar una ruta mediante:

  • Eficiencia
  • Flexibilidad

Los conmutadores de la red se organizan en una estructura en árbol

El encaminamiento estático utiliza la misma aproximación todo el tiempo

El encaminamiento dinámico permite los cambios en el encaminamiento dependiendo del tráfico

Utiliza una estructura de relación de igual a igual para los nodos

Criterios de encaminamiento

Encaminamiento alternativo

Las posibles rutas entre dos centrales finales se encuentran predefinidas

Es responsabilidad del conmutador origen seleccionar el camino adecuado para cada llamada

Cada conmutador dispone de un conjunto de rutas prefijadas, en orden de preferencia

Un conjunto diferente de rutas preplanificadas en instantes distintos de tiempo

Dos tipos:

  • Alternativo fijo
    Sólo una secuencia de encaminamiento para cada pareja origen-destino
  • Alternativo dinámico
    Conjunto diferente de rutas preplanificadas en instantes distintos de tiempo

Encaminamiento en redes de conmutación de paquetes

Uno de los aspectos más complejos y cruciales del diseño de redes de conmutación de paquetes es el relativo al encaminamiento

Características necesarias:

  • Exactitud
  • Simplicidad
  • Robustez
  • Estabilidad
  • Imparcialidad
  • Optimización
  • Eficiencia

Criterios de rendimiento

Se utiliza para la elección de una ruta

Dos técnicas fundamentales:

  • Elegir el camino con menor número de saltos: minimiza el consumo de recursos de la red
  • Una generalización del anterior es el criterio del mínimo coste
    • En caso de distintos costos por enlaces, se tomará aquel camino que sea el del mínimo coste
    • Si cada nodo tiene igual coste se puede generalizar este criterio buscando el camino de menor número de saltos

Instante y lugar de decisión

  • Instante
    • Paquete o datagrama
      Si cambian los costos, el paquete siguiente puede seguir una ruta diferente, de nuevo determinada por cada nodo a lo largo del camino
    • Circuito virtual
      Cada nodo recuerda la decisión de encaminamiento tomada cuando se estableció el circuito virtual, de modo que se limita a transmitir los paquetes sin tomar decisiones nuevas
  • Lugar
    • Encaminamiento distribuido
      • Se lleva a cabo por cada nodo
      • Es el más robusto
    • Encaminamiento centralizado
    • Encaminamiento desde el origen

Fuente de información de la red y tiempo de actualización

Las decisiones de encaminamiento se suelen tomar en base al conocimiento de la red, la carga y el coste de los enlaces (pero no siempre como por ejemplo con inundaciones y encaminamiento aleatorio)

  • Encaminamiento distribuido
    • Los nodos hacen uso de información local (coste asociado a cada enlace de salida)
    • Pueden utilizar información de los nodos adyacentes (congestión entre ellos)
    • Pueden obtener información de todos los nodos de una potencial ruta de interés
  • Encaminamiento central
    • Recopilar información de todos los nodos
  • Tiempo de actualización
    • Cuando los nodos tienen información actualizada de la red
    • Para una estrategia de encaminamiento estático, la información no se actualiza nunca
    • Para una técnica adaptable, la actualización se lleva a cabo periódicamente

Estrategias de encaminamiento ARPANET

Primera generación: 1969

  • Algoritmo adaptable distribuido
  • Estimación de los retardos como criterio de funcionamiento
  • Algoritmo de Bellman-Ford
  • Cada nodo intercambia su vector de retardo con todos sus vecinos
  • Tabla de encaminamiento actualizada basándose en la información de entrada
  • No tiene en cuenta la velocidad de la línea, sino la longitud de la cola
  • La longitud de la cola no es una buena medida del retardo
  • Responde lentamente a la congestión

Segunda generación: 1979

  • Se hace uso del retardo como criterio de rendimiento
  • El retardo se mide directamente
  • Algoritmo de Dijkstra
  • Es bueno ante cargas bajas o moderadas
  • Ante cargas altas, existe poca correlación entre los retardos indicados y los experimentados

Tercera generación: 1987

  • Cambian las estimaciones del coste del enlace
  • Medida del retardo medio en los últimos 10 segundos
  • Se normaliza en base al valor actual y a los resultados previos

Estrategias de encaminamiento

Encaminamiento estático

Una única ruta permanente para cada par de nodos origen-destino en la red

Se determinar las rutas utilizando cualquiera de los algoritmos de encaminamiento de mínimo coste

Las rutas son fijas, al menos mientras lo sea la topología de la red

Ejemplo de encaminamiento estático

Matriz de encaminamiento central

{\tiny\text{Nodo destino}}\overset{\text{Nodo origen}}{\begin{pmatrix}& 1& 2& 3& 4& 5& 6 \\ 1& & 1& 5& 2& 4& 5 \\ 2& 2& & 5& 2& 4& 5 \\ 3& 4& 3& & 5& 3& 5 \\ 4& 4& 4& 5& & 4& 5 \\ 5& 4& 4& 5& 5& & 5 \\ 6& 4& 4& 5& 5& 6 \\ \end{pmatrix}}

Tabla del nodo 1
Destino Nodo siguiente
2 2
3 4
4 4
5 4
6 4
Tabla del nodo 2
Destino Nodo siguiente
1 1
3 3
4 4
5 4
6 4
Tabla del nodo 3
Destino Nodo siguiente
1 5
2 5
4 5
5 5
6 5
Tabla del nodo 4
Destino Nodo siguiente
1 2
2 2
3 5
5 5
6 5
Tabla del nodo 5
Destino Nodo siguiente
1 4
2 2
3 3
4 4
6 6
Tabla del nodo 6
Destino Nodo siguiente
1 5
2 5
3 5
4 5
5 5

Inundaciones

No precisa de ninguna información sobre la red. Un nodo origen envía un paquete a todos sus nodos vecinos. Los nodos vecinos, a su vez, lo transmiten sobre todos los enlaces de salida excepto por el que llegó. Finalmente, llegará un número de copias al destino

Cada paquete contiene un identificador único, por lo que se pueden descartar los duplicados. De esta forma, una técnica sería que los nodos puedan recordar la identidad de los paquetes que han retransmitido con anterioridad, de manera que se evitan las cargas de la red

Otra técnica más sencilla es que se pueda incluir un campo de cuenta de saltos en cada paquete, un tiempo de vida donde cada vez que un nodo transmite un paquete, decrementa la cuenta en 1, de modo que cuando el contador alcanza el valor cero de elimina el paquete de la red

Propiedades

  • Se prueban todos los posibles caminos entre los nodos origen y destino. Lo que nos ofrece robustez
    Ejemplo: el envío de un mensaje de alta prioridad para garantizar la recepción del paquete
  • Al menos una copia del paquete a recibir en el destino habrá usado una ruta de menor número de saltos. Podría emplearse inicialmente para establecer la ruta para un circuito virtual
  • Se visitan todos los nodos. Puede resultar útil para llevar a cabo la propagación de información relevante para todos los nodos (por ejemplo, una tabla de encaminamiento central)

Ejemplo de inundación

Inundación

Encaminamiento aleatorio

Un nodo selecciona un único camino de salida para retransmitir un paquete entrante. La selección se puede hacer de forma aleatoria o alternada

Una mejoría es que se pueda seleccionar la ruta de salida de acuerdo con el cálculo de probabilidades

No necesita el uso de información sobre la red. La ruta no corresponderá en general con la de mínimo coste ni con la de menor número de saltos. Tiene menos tráfico que la de inundaciones pero es igualmente sencilla y robusta.Un nodo selecciona un único camino de salida para retransmitir un paquete entrante. La selección se puede hacer de forma aleatoria o alternada

Una mejoría es que se pueda seleccionar la ruta de salida de acuerdo con el cálculo de probabilidades

No necesita el uso de información sobre la red. La ruta no corresponderá en general con la de mínimo coste ni con la de menor número de saltos. Tiene menos tráfico que la de inundaciones pero es igualmente sencilla y robusta

Encaminamiento adaptable

Prácticamente en todas las redes de conmutación de paquetes se utiliza algún tipo de técnica de encaminamiento adaptable

Las decisiones de encaminamiento cambian en la medida que lo hacen las condiciones de la red:

  • Fallos
  • Congestión

Requiere información acerca del estado de la red presentando desventajas:

  • Las decisiones son más complejas: mayor coste de procesamiento en los nodos de la red
  • Es necesario que los nodos intercambien información acerca del estado y del tráfico de la red: mayor tráfico y degradación de las prestaciones de la red
  • La reacción demasiado rápida puede provocar oscilación o ser demasiado lenta para ser relevante

Ventajas del encaminamiento adaptable

    • Mejora de las prestaciones
    • Resulta de ayuda en el control de la congestión
    • Sistema complejo: Puede que no se cumplan los beneficios teóricos

Clasificación

Clasificación realizada de acuerdo con la fuente de información

      • Local (aislada)
        • Encaminar el paquete hasta el enlace de salida con la cola más corta
        • Puede incluir un peso para cada destino. Se utilizan raramente, puesto que no explotan con facilidad la información disponible
      • Nodos adyacentes
      • Todos los nodos

Ejemplo de encaminamiento adaptable aislado

Ejemplo encaminamiento adaptable aislado