Método de enrutamiento y dispositivo de enrutamiento para una red de comunicaciones orientada a paquetes.

Un método de enrutamiento para una red de comunicaciones orientada a paquetes (1),

comprendiendo el método:

determinar (S21) una función de densidad de probabilidad indicativa de una distribución de probabilidad de retardo de transmisión para cualquier enlace (11, 12, 20, 31, 32) entre nodos adyacentes (A, B, C, L) de una ruta (P1, P2, P3) desde un nodo de origen (B) a un nodo de destino (L);

determinar (S22) para diferentes rutas posibles (P1, P2, P3) desde el nodo de origen (B) al nodo de destino (L) en cada caso una distribución de probabilidad de retardo de transmisión total a través de la convolución de las funciones de densidad de probabilidad de los enlaces (11, 12, 20, 31, 32) entre los nodos adyacentes (A, B, C, L) de la ruta respectiva (P1, P2, P3);

seleccionar (S32) un primer criterio de selección para una primera clase de paquetes;

caracterizado por

seleccionar (S32) un segundo criterio de selección para una segunda clase de paquetes; y seleccionar la ruta preferida (P1, P2, P3) para la primera clase de paquetes y la segunda clase de paquetes aplicando a las distribuciones de probabilidad de retardo de transmisión totales determinadas para las diferentes rutas posibles (P1, P2, P3) el primer criterio de selección o el segundo criterio de selección, respectivamente, donde el primer y el segundo criterio de selección son diferentes y se seleccionan de un grupo de criterios que incluye

- seleccionar la ruta con un cuantil más bajo dα, donde un cuantil dα se define de tal manera que Pr [retardo ≤ da], en la que αes un gran número cercano a 1,

- seleccionar la ruta con una más alta probabilidad de satisfacer un retardo de ruta máximo,

- seleccionar la ruta con una más alta proporción de entrega de paquetes.

Método de enrutamiento y dispositivo de enrutamiento para una red de comunicaciones orientada a paquetes

Campo de la invención

La presente invención se refiere a un método de enrutamiento y a un dispositivo de enrutamiento para una red de comunicaciones orientada a paquetes. Específicamente, la presente invención se refiere a un método de enrutamiento y a un dispositivo de enrutamiento para seleccionar, en una red de comunicaciones orientada a paquetes, una ruta preferida a partir de diferentes rutas posibles desde un nodo de origen a un nodo de destino.

Antecedentes de la invención En las redes de comunicaciones orientadas a paquetes, un paquete de datos se enruta desde un origen a un destino a lo largo de una cierta ruta que consiste en un número de saltos (enlaces entre los routers vecinos) . Las rutas están establecidas y mantenidas por un protocolo de enrutamiento en base a métricas de enlace. En los protocolos de enrutamiento de Internet tradicionales, tal como RIP (RFC2453) , la longitud de las rutas se mide con una "cuenta de saltos", como la métrica de enlace. Los algoritmos de enrutamiento determinan las rutas más cortas entre pares de nodos de origen y de destino con respecto al número de saltos (nodos de enrutamiento) atravesados. La métrica de enlace es, por lo tanto, solo binaria (1 para los enlaces activos, infinito para los enlaces no existentes o rotos) . Esta métrica es fácil de medir y simple de procesar, y es suficiente para los enlaces de banda ancha cableados estáticos normales. Sin embargo, los enlaces con pérdidas, tales como los enlaces inalámbricos o de línea eléctrica, exhiben normalmente un comportamiento variable de manera dinámica, que debería medirse por una métrica de calidad del enlace de grano más fino, con el fin de optimizar el enrutamiento. Además de la fiabilidad de la transmisión (tasa de pérdida de paquetes) , el retardo de transmisión es a menudo el principal criterio para las decisiones de enrutamiento. Los retardos en la transmisión se provocan por diversos mecanismos, tales como los errores de bits aleatorios y las consiguientes retransmisiones de paquetes, el retroceso aleatorio en la contención en base a esquemas de acceso al medio, los retardos de encolamiento en los routers, etc.

Los protocolos de enrutamiento próximo para redes de baja energía y con pérdidas (RPL) proporcionan la capacidad de seleccionar una de una serie de métricas de enlace predefinidas para usarse en una red de malla determinada.

Tal como se describe en M. Campista et al., "Routing Metrics and Protocols for Wireless Mesh Networks", Red IEEE, enero/febrero de 2008, pp. 6-12, se han propuesto específicamente muchas métricas conscientes de calidad de enlace para las redes de malla inalámbricas:

Dada una proporción de entrega de paquetes medida Di en un enlace i, la cuenta de transmisión esperada ETX que usa ese enlace es ETXi = 1/Di, o ETXi = 1/ (DfI Dri) , si están incluidos el envío de datos DfI y las proporciones de entrega de acuse de recibo de retorno Dri. ETX es una métrica aditiva, y se selecciona la ruta con la suma más baja del enlace ETXi. La métrica de tiempo de transmisión esperada (ETT) ajusta el ETX para explicar el tamaño del paquete de datos y la tasa de datos Ri del enlace, ETTI = ETXi x tamaño de paquete l Ri.

La pérdida mínima ML mide la proporción de entrega de paquetes de extremo a extremo, por lo tanto la proporción de entrega de ruta es el producto Druta de todos los Di a lo largo de la ruta. 45 Si el enlace de cuello de botella a lo largo de una ruta es crítico, entonces, una métrica de ruta relevante es el mínimo de las tasas de datos Ri de los enlaces a lo largo de la ruta.

Más modificaciones propuestas de las métricas de enlace incluyen, además de la media, también la desviación convencional, por ejemplo, de la tasa de error de paquetes, con el fin de modelar la variabilidad de la calidad del enlace (número de transmisiones efectivas mETX modificadas, métricas conscientes SNR y la interferencia) .

Las métricas conscientes de carga incluyen los efectos de interferencia de interflujo en cada enlace: la tasa de datos Ri puede ser la tasa de datos residuales en el enlace, excluyendo otro tráfico compartido en el enlace. Se 55 proporciona una medida adicional de la carga dinámica por la longitud de cola de búfer instantánea en el nodo.

Como se ha descrito por M. Campista et al., las métricas de enlace se usan tanto como un criterio de optimización de ruta como de limitación de enrutamiento. Las métricas de enlace pueden grabarse (adquiridas y almacenadas por separado para cada enlace a lo largo de la ruta) o agregarse (acumuladas en un número a lo largo de la ruta) . La agregación métrica es aditiva, multiplicativa, máxima o mínima.

El documento "A Laplace transform-based method of stochastic path finding, Suleymann Uludag et al." describe un método de transformación de las distribuciones de probabilidad en el dominio de Laplace, encontrar la transformada de Laplace de sus circunvoluciones y la inversa numéricamente para encontrar la función de distribución en el 65 dominio del tiempo. El método iterativo de Picard de aproximaciones sucesivas se usa para encontrar la solución.

Las simulaciones muestran que el enfoque estocástico propuesto selecciona rutas correctas con más frecuencia, incurre en menos sobrecarga con respecto a la difusión y al procesamiento de información de estado, y reduce la rotación seleccionando rutas más estables.

Sumario de la invención

Es un objeto de esta invención proporcionar un método de enrutamiento y un dispositivo de enrutamiento para una red de comunicaciones orientada a paquetes, cuyo método y dispositivo no tenga al menos algunas de las desventajas de la técnica anterior. En particular, es un objeto de la presente invención proporcionar un método de enrutamiento y un dispositivo de enrutamiento adecuado para la transmisión de datos sensible al retardo en una red de comunicaciones orientada a paquetes.

De acuerdo con la presente invención, estos objetos se logran a través de las características de las reivindicaciones independientes. Además, se deducen unas realizaciones ventajosas adicionales de las reivindicaciones dependientes y de la descripción.

De acuerdo con la presente invención, los objetos mencionados anteriormente se logran específicamente en que para enrutar un paquete de datos en una red de comunicaciones orientada a paquetes, se determina una distribución de probabilidad de retardo de transmisión para cualquier enlace entre los nodos adyacentes de una ruta desde un nodo de origen a un nodo de destino. La distribución de probabilidad de retardo de transmisión de un enlace se define por una función de densidad de probabilidad para el enlace. Para las diferentes rutas posibles, se determina en cada caso una distribución de probabilidad de retardo de transmisión total a través de una convolución de las funciones de densidad de probabilidad de los enlaces entre los nodos adyacentes de la ruta respectiva. Posteriormente, se selecciona una ruta preferida en base a las distribuciones de probabilidad de retardo de transmisión totales determinadas para las diferentes rutas posibles y en base a un criterio de selección u óptimo. En base a las distribuciones de probabilidad de retardo de transmisión totales mencionadas anteriormente como una información métrica de enlace única y exhaustiva, se realiza un enrutamiento diferenciado para las clases de paquetes del mismo par origen / destino en la misma red. El criterio de selección u óptimo puede seguir un requerimiento de calidad de servicio (QoS) de la clase de paquetes.

En una realización, seleccionar la ruta preferida incluye determinar a partir de las distribuciones de probabilidad de retardo de transmisión totales para las diferentes rutas posibles en cada caso un cuantil d, de tal manera que la probabilidad de que el retardo de transmisión total de una ruta sea menor o igual al cuantil d es igual a un nivel de probabilidad determinado, Pr [retardo da] = , y seleccionar la ruta preferida con el cuantil más bajo da.

En una realización adicional, seleccionar la ruta preferida incluye determinar a partir de las distribuciones de probabilidad de retardo de transmisión totales para las diferentes rutas posibles en cada caso una probabilidad de no superar un retardo de transmisión máximo determinado, y seleccionar la ruta preferida con la más alta probabilidad de no superar el retardo de transmisión máximo.

En otra realización, seleccionar la ruta preferida incluye determinar a partir de las distribuciones de probabilidad de retardo de transmisión totales para las diferentes rutas posibles en... [Seguir leyendo]

1. Un método de enrutamiento para una red de comunicaciones orientada a paquetes (1) , comprendiendo el método:

determinar (S21) una función de densidad de probabilidad indicativa de una distribución de probabilidad de retardo de transmisión para cualquier enlace (11, 12, 20, 31, 32) entre nodos adyacentes (A, B, C, L) de una ruta (P1, P2, P3) desde un nodo de origen (B) a un nodo de destino (L) ; determinar (S22) para diferentes rutas posibles (P1, P2, P3) desde el nodo de origen (B) al nodo de destino (L) en cada caso una distribución de probabilidad de retardo de transmisión total a través de la convolución de las funciones de densidad de probabilidad de los enlaces (11, 12, 20, 31, 32) entre los nodos adyacentes (A, B, C, L) de la ruta respectiva (P1, P2, P3) ; seleccionar (S32) un primer criterio de selección para una primera clase de paquetes;

caracterizado por seleccionar (S32) un segundo criterio de selección para una segunda clase de paquetes; y seleccionar la ruta preferida (P1, P2, P3) para la primera clase de paquetes y la segunda clase de paquetes aplicando a las distribuciones de probabilidad de retardo de transmisión totales determinadas para las diferentes rutas posibles (P1, P2, P3) el primer criterio de selección o el segundo criterio de selección, respectivamente, donde el primer y el segundo criterio de selección son diferentes y se seleccionan de un grupo de criterios que incluye -seleccionar la ruta con un cuantil más bajo d, donde un cuantil d se define de tal manera que Pr [retardo da], en la que es un gran número cercano a 1, -seleccionar la ruta con una más alta probabilidad de satisfacer un retardo de ruta máximo, -seleccionar la ruta con una más alta proporción de entrega de paquetes.

2. El método de enrutamiento de la reivindicación 1, donde seleccionar (S3) la ruta preferida (P1, P2, P3) incluye determinar a partir de las distribuciones de probabilidad de retardo de transmisión totales para las diferentes rutas posibles (P1, P2, P3) en cada caso un cuantil d, de tal manera que la probabilidad de que el retardo de transmisión total de una ruta sea menor o igual al cuantil d es igual a un nivel de probabilidad determinado, Pr [retardo da] = , y seleccionar la ruta preferida (P1, P2, P3) con el cuantil más bajo da.

3. El método de enrutamiento de la reivindicación 1, donde seleccionar (S3) la ruta preferida (P1, P2, P3) incluye determinar a partir de las distribuciones de probabilidad de retardo de transmisión totales para las diferentes rutas posibles (P1, P2, P3) en cada caso una probabilidad de no superar un retardo de transmisión máximo determinado, y seleccionar la ruta preferida (P1, P2, P3) con la más alta probabilidad de no superar el retardo de transmisión máximo.

4. El método de enrutamiento de la reivindicación 1, donde seleccionar (S3) la ruta preferida (P1, P2, P3) incluye determinar a partir de las distribuciones de probabilidad de retardo de transmisión totales para las diferentes rutas posibles (P1, P2, P3) en cada caso una proporción de entrega de paquetes o un retardo medio, y seleccionar la ruta preferida (P1, P2, P3) con la más alta proporción de entrega de paquetes o con el retardo medio más bajo, respectivamente.

5. El método de enrutamiento de una de las reivindicaciones 1 a 4, donde la primera clase de paquetes incluye datos

de medición y la segunda clase de paquetes incluye datos muestreados de estado o cíclicos, surgiendo los datos de 45 un medio o de una red de distribución eléctrica de baja tensión.

6. Un dispositivo de enrutamiento (2) para una red de comunicaciones orientada a paquetes (1) , comprendiendo el dispositivo (2) :

un sistema de medición (21) configurado para determinar una función de densidad de probabilidad indicativa de una distribución de probabilidad de retardo de transmisión de cualquier enlace (11, 12, 20, 31, 32) entre los nodos adyacentes (A, B, C, L) de una ruta (P1, P2, P3) desde un nodo de origen (B) a un nodo de destino (L) ; y configurado para determinar por las diferentes rutas posibles (P1, P2, P3) desde el nodo de origen (B) al nodo de destino (L) en cada caso una distribución de probabilidad de retardo de transmisión total a través de la 55 convolución de las funciones de densidad de probabilidad de los enlaces (11, 12, 20, 31, 32) entre los nodos adyacentes (A, B, C, L) de la ruta respectiva (P1, P2, P3) ; un módulo de configuración (23) configurado para seleccionar un primer criterio de selección para una primera clase de paquetes; caracterizado por que el módulo de configuración está configurado además para seleccionar un segundo criterio de selección para una segunda clase de paquetes, donde el primer criterio de selección y el segundo criterio de selección son diferentes y se seleccionan de un grupo de criterios que incluye -seleccionar la ruta con un cuantil más bajo d, donde un cuantil d se define de tal manera que Pr [retardo d], en la que es un gran número cercano a 1, -seleccionar la ruta con una más alta probabilidad de satisfacer un retardo de ruta máximo, 65 -seleccionar la ruta con una más alta proporción de entrega de paquetes; y 7

un módulo de enrutamiento (22) configurado para seleccionar la ruta preferida (P1, P2, P3) para la primera clase de paquetes y la segunda clase de paquetes aplicando a las distribuciones de probabilidad de retardo de transmisión totales determinadas para las diferentes rutas posibles (P1, P2, P3) el primer criterio de selección o el segundo criterio de selección, respectivamente.

7. El dispositivo de enrutamiento (2) de la reivindicación 6, donde el módulo de enrutamiento (22) está configurado además para determinar a partir de las distribuciones de probabilidad de retardo de transmisión totales para las diferentes rutas posibles (P1, P2, P3) en cada caso un cuantil d, de tal manera que la probabilidad de que el retardo de transmisión total de una ruta (P1, P2, P3) sea menor o igual al cuantil d es igual a un nivel de probabilidad determinado, Pr [retardo d] = , y seleccionar la ruta preferida (P1, P2, P3) con el cuantil más bajo d.

8. El método de enrutamiento de la reivindicación 6, donde el módulo de enrutamiento (22) está configurado además para determinar a partir de las distribuciones de probabilidad de retardo de transmisión totales para las diferentes rutas posibles (P1, P2, P3) en cada caso una probabilidad de no superar un retardo de transmisión máximo determinado, y para seleccionar la ruta preferida (P1, P2, P3) con la más alta probabilidad de no superar el retardo de transmisión máximo.

9. El dispositivo de enrutamiento (2) de la reivindicación 6, donde el módulo de enrutamiento (22) está configurado además para determinar a partir de las distribuciones de probabilidad de retardo de transmisión totales para las diferentes rutas posibles (P1, P2, P3) en cada caso una proporción de entrega de paquetes o un retardo medio, y para seleccionar la ruta preferida (P1, P2, P3) con la proporción de entrega de paquetes más alta o con el retardo medio más bajo, respectivamente.

10. Un producto de programa de ordenador que comprende un medio legible por ordenador que tiene almacenado en el mismo un código de programa de ordenador para controlar uno o más procesadores de un dispositivo de enrutamiento (2) de una red de comunicaciones orientada a paquetes (1) de tal manera que el dispositivo de enrutamiento (2) realiza el método de enrutamiento de una de las reivindicaciones 1 a 5.