Encaminamiento dinámico multicamino con tolerancia diferenciada por planos de red,

en el que el valor de tolerancia en cada interfaz se calcula en función de la carga de tráfico, por lo que mejora la distribución del tráfico en la red. Esta mejora en la distribución del tráfico en la red se hace preservando la compatibilidad con el funcionamiento convencional de las redes IP, de manera que no es necesario hacer ningún cambio en el funcionamiento de los nodos que trabajen alrededor de los nodos con EDMT-DPR

Encaminamiento dinámico multicamino con tolerancia diferenciada por planos de red.

Sector de la técnica

La presente invención está relacionada, dentro del área de las telecomunicaciones, con el campo de las redes IP y, en particular, con las estrategias de encaminamiento y distribución de tráfico diferenciado.

Estado de la técnica

La figura 2 muestra la estructura de una red simple del estado del arte previo. Esta red comprende dos componentes básicos: "nodos" (también llamados routers) y "enlaces". Los nodos pueden enviar información (también llamada "datos"), dividida en fragmentos llamados "paquetes", a un nodo de destino a través de los enlaces de la red, o tan solo limitarse a enviar la información hacia el nodo de destino. Las decisiones sobre el enrutamiento se toman salto a salto de forma descentralizada, es decir, cada nodo sólo decide el próximo nodo hacia el que enviar el paquete, de forma que los paquetes se acercan más al destino final salto a salto. Por otro lado, cada enlace conecta dos nodos, que lo usan para enviar información entre ellos. La estructura de los nodos que envía paquetes a través de un enlace se llama "interfaz de salida", y hay tantas interfaces de salida en un nodo como enlaces hay en el mismo conectándolo a otros nodos. El número de paquetes por segundo (tasa de paquetes) que un enlace puede transportar es determinado por el ancho de banda del enlace. La parte del ancho de banda que es usado en un determinado momento para transportar información se llama "carga" o "ancho de banda usado", y el ancho de banda restante es llamado "ancho de banda disponible". El conjunto de enlaces que un paquete de datos sigue desde el nodo de origen hasta el nodo de destino se llama "camino", y normalmente hay más de un posible camino para enviar información desde un nodo de origen a uno de destino.

En el enrutamiento de red, los enlaces se caracterizan por un número llamado "coste", que permite comparar los distintos enlaces. Hay muchas maneras de calcular el coste de un enlace, pero la idea general es que cuanto menor sea el coste de un enlace, más apropiado (es decir, más rápido o con menos retraso) es éste. Los caminos también se caracterizan por un coste que permite comparar los distintos caminos uniendo un mismo par de nodos origen-destino. De nuevo, hay diferentes métodos para calcular el coste de un camino y el concepto es el mismo: cuanto menos coste tenga un camino más apropiado es este. Todos estos métodos calculan el coste de un camino a partir del coste de sus enlaces y la idea principal es que el camino con un menor coste está formado por los enlaces con los menores costes.

Hay típicamente tres alternativas para asignar costes a los enlaces en una red IP y difundirlos entre los nodos a través de los protocolos correspondientes (a los que se denomina "protocolos IGP" o Interior Gateway Protocols): número de saltos, retardo o ancho de banda. La métrica basada en el número de saltos es la más sencilla (cada enlace tiene el mismo coste), pero no tiene en cuenta la topología ni las características de los enlaces. La métrica basada en el retardo de los enlaces ayuda a evitar enlaces con un gran retardo de propagación (enlaces transatlánticos o vía satélite), aunque no tienen en cuenta el retardo en las colas causado por los estados de congestión en la red, lo que en la práctica podría ser más significativo. Finalmente, las métricas de ancho de banda asignan costes a los enlaces en relación inversa a su capacidad nominal. Con esta métrica, el tráfico tiende a ser transportado por los enlaces con mayor ancho de banda nominal, lo que reduce la probabilidad de congestión.

Con respecto al cálculo del coste de un camino, normalmente se calcula como la suma de los costes de sus enlaces, independientemente de la métrica de enlace considerada (número de saltos, retardo o ancho de banda). Sin embargo, en el caso de la métrica basada en ancho de banda, sería más apropiado una medida relativa al enlace con peor métrica (es decir, el enlace con menor ancho de banda nominal o "cuello de botella"), puesto que el caudal extremo a extremo viene determinado principalmente por este peor enlace. Esta métrica basada en cuello de botella es más estable que aquellas basadas en la suma de costes de los enlaces, puesto que cada router ve un coste extremo a extremo distinto del de sus vecinos (aunque depende de la topología). Además, su uso con un protocolo dinámico debería provocar menos oscilaciones, puesto que sólo el ancho de banda del enlace cuello de botella influye en la distribución del tráfico. Por el contrario, con una métrica de suma de costes, la estimación de la conveniencia de un camino cambiaría en función de los enlaces del camino.

Cada nodo debe decidir dónde enviar cada paquete, es decir, qué interfaz de salida utilizar. Por un procedimiento el estado del enlace, los nodos pueden aprender la estructura de la red y todos los caminos hacia un determinado nodo de destino con sus costes asociados para poder decidir la interfaz de salida más apropiada para cada paquete. En este sentido, un nodo mantiene una tabla de rutas con todas las posibles interfaces de salida para enviar paquetes hacia un nodo de destino y los costes asociados. De este modo, en la figura 2, el nodo a tiene dos posibilidades (nodos b o c) para transmitir los paquetes hacia el nodo d y el coste del camino es diferente para cada uno. A partir de estas tablas de enrutamiento, los nodos del estado del arte previo usan distintos métodos para decidir el interfaz de salida más conveniente para un determinado paquete de datos.

En el enrutamiento monocamino, que es el modo convencional de operación con protocolos de encaminamiento interiores -tales como Open Shortest Path First (OSPF) o Intermedíate System to INtermediate System (IS-IS)- sólo el camino óptimo (el que tiene mínimo coste) puede usarse para enviar el tráfico. Este mecanismo es normalmente incapaz de hacer una distribución de tráfico uniforme porque sólo uno de los caminos es usado para enviar la información, y por lo tanto, existe el riesgo de que los enlaces con bajo coste concentren el tráfico. Por consiguiente, no habría suficiente ancho de banda para transportar toda la información a través de este enlace, incluso con cargas globales ligeras. Para la red de la figura 2, el nodo a tiene que enrutar paquetes hacia d. Trabajando con el principio de que el nodo a conoce la estructura completa de la red, éste decidiría enviar todos los paquetes a través de b porque el coste es menor. Si se toma siempre esta decisión, el ancho de banda disponible en el camino a-b-d se puede reducir a cero, y entonces habrá paquetes que puedan ser descartados, incluso cuando la otra interfaz de salida (a-c) tiene ancho de banda disponible. En ingeniería del tráfico, es deseable el uso de todos los recursos de la red (p.e. ancho de banda del enlace) para minimizar el descarte de paquetes, de forma que todos los enlaces deberían ser capaces de trasportar información en caso necesario y no sólo aquellos que forman parte de los caminos con mínimo coste. El enrutamiento multicamino y el enrutamiento dinámico tratan de resolver este problema.

El enrutamiento multicamino consiste en el uso simultaneo de de más de un interfaz de salida para un destino dado. En la actualidad existen dos aproximaciones básicas: ECMP, que envía paquetes a través de todos los caminos con coste óptimo, por lo que la carga se distribuye entre ellos y la probabilidad de congestión se reduce; y el "multicamino con tolerancia", que permite que el tráfico sea transportado por otros caminos además de por aquellos con el mínimo coste. Aunque ECMP puede mejorar las prestaciones, no es suficientemente efectivo puesto que la distribución de tráfico se realiza sólo entre caminos con exactamente el mismo coste, y todos los nodos tienen la misma visión de la red, con lo que los enlaces con bajo coste se mantendrán concentrando el tráfico como en el caso de enrutamiento monocamino. En el multicamino con tolerancia, por el contrario, caminos que tienen costes ligeramente peores que los óptimos son válidos para su uso. El grado de parecido necesario para que un camino transporte tráfico se determina comparando su coste a un umbral de la siguiente manera:

M ≤q Mmin • V

donde M es el coste del camino, Mmin es el coste del camino óptimo, y V es el parámetro de la tolerancia. El tráfico es distribuido entre todos los caminos satisfaciendo esta condición de acuerdo a los costes de los caminos, de manera que los caminos con un coste menor pueden...

1. Método de encaminamiento dinámico multicamino para el reparto dinámico de la carga de tráfico en una red, caracterizado porque comprende los siguientes pasos:

a) para enviar un paquete a un determinado destino cada nodo de la red decide que interfaz de salida utilizar para enviar dicho paquete

b) cada interfaz de salida de cada nodo de la red tiene asociado, por cada plano de red, un parámetro denominado "tolerancia", cuyo valor cambia dinámicamente en función de la carga que se ha medido en esa interfaz para el tráfico de ese plano de red, PR.

c) el nodo considera como utilizable para enviar dicho paquete a ese destino cada una de las posibles interfaces de salida de un nodo,, si el coste del camino extremo a extremo que utiliza ese interfaz de salida es menor que el valor de la expresión

Mmin • V

donde Mmin es el coste del camino óptimo hacia ese destino, es decir, el mínimo coste de todos los posibles caminos hacia ese destino partiendo de ese nodo y V es el valor de la tolerancia de la interfaz de salida del camino óptimo, y cuyo valor depende de la carga monitorizada.

2. Método de encaminamiento dinámico multicamino para el reparto dinámico de la carga de tráfico en una red, según la reivindicación 1, caracterizado porque la correspondencia entre la carga asociada al tráfico de un PR dentro una interfaz de salida y el valor de la tolerancia correspondiente asociado a ese plano de red PR en esa interfaz se controla por un ciclo de histéresis, de manera que: