ES2536329T3

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

Info

Publication number: ES2536329T3
Application number: ES12737733.1T
Authority: ES
Inventors: Dacfey Dzung
Original assignee: ABB Research Ltd Switzerland
Current assignee: ABB Research Ltd Switzerland
Priority date: 2011-06-30
Filing date: 2012-07-02
Publication date: 2015-05-22
Anticipated expiration: 2032-07-02
Also published as: EP2541849A1; WO2013001090A1; EP2727296A1; EP2727296B1

Abstract

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.

Description

E12737733

06-05-2015

DESCRIPCIÓN

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

5 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

15 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

25 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

35 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.

E12737733

06-05-2015

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.

5 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

15 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

25 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.

35 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 cada caso una proporción de entrega de paquetes, y seleccionar la ruta preferida con la proporción de entrega de paquetes más alta.

45 En aún otra realización, las clases de los paquetes pertenecen a las comunicaciones en el campo del medio y/o la distribución eléctrica de baja tensión comúnmente denominada como comunicaciones de red inteligente. Específicamente, los datos incluyen datos muestreados de estado o cíclicos que requieren un cuantil bajo d, así como datos de medición que tolerar un alto d, pero que necesitan una baja probabilidad de pérdida de paquetes pruta.

Además del método de enrutamiento y el dispositivo de enrutamiento para una red de comunicaciones orientada a paquetes, la presente invención se refiere también a un producto de programa de ordenador que comprende un código de programa de ordenador para controlar uno o más procesadores del dispositivo de enrutamiento para realizar el método de enrutamiento, preferentemente un producto de programa de ordenador que comprende un

55 medio legible por ordenador que tiene almacenado el código de programa de ordenador en el mismo.

Por lo tanto, se presenta una nueva clase de métricas de enlace que se define como la distribución de probabilidad completa del retardo de transmisión a lo largo del enlace. La distribución de probabilidad del retardo de un enlace i se describe por su función de densidad de probabilidad pdfi y la probabilidad de pérdida de paquetes pi. Formalmente, la probabilidad de pérdida de paquetes pi es la probabilidad de que el retardo de transmisión sea infinito, de manera que pi podría subsumirse en pdfi. En la práctica es más conveniente mantener la pi separada, lo que implica a su vez que la integral de pdfi a lo largo de los retardos finitos debe ser igual a 1-pi. La nueva métrica de enlace tiene las siguientes ventajas:

65  El retardo de transmisión se representa completo en general, incluyendo su variación estadística y la

E12737733

06-05-2015

probabilidad de pérdida de paquetes. Esta información de métrica de enlace se adquiere y se mantiene en el sistema de enrutamiento.  Entonces, la decisión de enrutamiento actual puede hacerse de manera separada en base a esta información de métrica de enlace, por ejemplo, usando un retardo medio (ETT), un retardo medio y la varianza (mETX), o una 5 tasa de pérdida de paquetes de la ruta (pruta).

 Puede usarse un nuevo criterio de enrutamiento relevante para muchas aplicaciones con esta información de métrica de enlace, concretamente, el cuantil d del retardo total en la ruta, es decir, el d de manera que Pr [retardo ≤ d] = , en la que  es un gran número cercano a 1, por ejemplo,  = 90 %. Tal criterio es especialmente relevante para las aplicaciones sensibles al retardo.

10

Breve descripción de los dibujos

La presente invención se explicará en más detalle, a modo de ejemplo, con referencia a los dibujos en los que:

15 La figura 1: muestra un diagrama de bloques que ilustra de manera esquemática una red de comunicaciones orientada a paquetes que comprende una pluralidad de nodos interconectados por enlaces (saltos). La figura 2: muestra un diagrama de bloques que ilustra de manera esquemática un dispositivo de enrutamiento de una red de comunicaciones orientada a paquetes. La figura 3: muestra tres gráficas que ilustran en cada caso para una ruta las distribuciones de probabilidad de 20 retardo de transmisión de sus enlaces individuales. La figura 4: muestra unas gráficas que ilustran para las tres rutas diferentes sus distribuciones de probabilidad de retardo de transmisión totales. La figura 5: muestra un diagrama de flujo que ilustra una secuencia ejemplar de las etapas de un método de enrutamiento para una red de comunicaciones orientada a paquetes. 25

Descripción detallada de las realizaciones preferidas

En la figura 1, la referencia numérica 1 se refiere a una red de comunicaciones (red de conmutación de paquetes) orientada a paquetes, específicamente una red de malla que comprende una pluralidad de nodos A, B, C, D, E, F, G, 30 H, I, L interconectados por enlaces. Específicamente, la red de comunicaciones 1 comprende enlaces con pérdidas, por ejemplo, enlaces inalámbricos o enlaces de línea eléctrica (PLC). En la figura 1, los números dentro de círculos indican para un enlace en cada caso un ejemplo de un retardo de transmisión media en alguna unidad de tiempo definida, por ejemplo, 1 segundo. Los paquetes de datos se enrutan desde un nodo de origen a un nodo de destino a través de una de un número de rutas posibles. Por ejemplo, en la figura 1, un paquete de datos desde el nodo B al

35 nodo de destino L puede enrutarse a lo largo de la ruta P1, que lo conduce a través de los enlaces 11 y 12 por el nodo A; o a través de la ruta P2, que tiene un enlace directo 20 al nodo destino L; o a lo largo de la ruta P3, que lo conduce a través de los enlaces 31 y 32 por el nodo C.

En la figura 2, el número de referencia 2 se refiere a un dispositivo de enrutamiento que comprende uno o más

40 ordenadores que funcionan con uno o más procesadores. El dispositivo de enrutamiento 2 incluye diferentes módulos funcionales, incluyendo un sistema de medición 21, un módulo de enrutamiento 22, y un módulo de configuración 23. Preferentemente, los módulos funcionales se implementan por medio de unos módulos de software programados que comprenden un código de programa de ordenador para controlar el procesador(s) del dispositivo de enrutamiento 2. El código de programa se almacena en un producto de programa de ordenador,

45 específicamente en un medio de almacenamiento legible por ordenador que está conectado de manera fija o extraíble con el procesador(s) del dispositivo de enrutamiento 2. Un experto en la materia entenderá, sin embargo, que, en realizaciones alternativas, los módulos funcionales pueden implementarse total o parcialmente por medio de componentes de hardware.

50 En los párrafos siguientes, se describen con referencia a la figura 5 posibles secuencias de etapas realizadas por los módulos funcionales para enrutar los paquetes de datos en la red de comunicaciones 1; específicamente, para seleccionar una ruta (óptima) preferida de diferentes rutas posibles P1, P2, P3 desde un nodo de origen B a un nodo de destino L.

55 En la figura 5, el número de referencia S1 se refiere a una etapa de configuración para seleccionar y asignar diferentes criterios de selección a diferentes clases o tipos de paquetes de datos. Específicamente, en la etapa S1, el módulo de configuración 23 define diferentes calidades de servicio (QoS) para los diferentes tipos de datos almacenando, por ejemplo, en una tabla de calidad de servicio, diferentes criterios de selección asignados a diferentes clases o tipos de datos.

60 El número de referencia S2 se refiere a un bloque de etapas para determinar unas métricas de enlace y de ruta para las rutas P1, P2, P3 y los enlaces asociados 11, 12, 20, 31, 32 de la red de comunicaciones 1. Como se indica de manera esquemática en la figura 5, el sistema de medición 22 realiza continuamente el bloque de las etapas S2 para determinar y actualizar de manera dinámica las métricas de enlace y de ruta.

65

E12737733

06-05-2015

En la etapa S21, el sistema de medición 21 determina las métricas de enlace determinando las distribuciones de probabilidad de los retardos de transmisión en los enlaces individuales 11, 12, 20, 31, 32 de las diversas rutas P1, P2, P3 en la red de comunicaciones 1. Específicamente, las distribuciones de probabilidad de retardo de transmisión para los enlaces individuales 11, 12, 20, 31, 32 están definidas por las funciones de densidad de probabilidad

5 respectivas.

Como todo con todas las métricas de enlace dinámico, la nueva métrica está midiendo y actualizándose de manera continua, midiendo retardos (de acuses de recibo) de paquetes de datos enviados, o usando paquetes de prueba especiales enviados a los vecinos de un enlace. En contraste a las métricas del estado del estado del arte, las medidas de retardo no se promedian, pero el histograma completo pdfi de las medidas de retardo se mantiene y se normaliza tal como se ha descrito anteriormente, junto con el recuento de pérdida de paquetes promediado pi (la integral de pdfi a lo largo de los retardos finitos debe ser igual a 1-pi). Como es bien conocido, la actualización y el uso de tal información de métrica de enlace dinámico deben estar suficientemente pulidos en el tiempo con el fin de evitar las oscilaciones e inestabilidades del enrutamiento. El histograma medido es normalmente una lista de

15 probabilidades (fracciones) como una función de los valores de retardo redondeados (cuantificados), en lugar de una función de densidad de probabilidad continua pdfi. Tal representación discretizada debe tratarse adecuadamente en el cálculo de la convolución.

Para el ejemplo de la figura 1, la primera subtrama (superior) de la figura 3 muestra las distribuciones de retardo de los enlaces 11 y 12 de la ruta P1, con lo que los retardos medios, dado que el paquete no está perdido, son 1 unidad (mostrado en la figura 1), y el enlace 11 tiene una probabilidad de pérdida de paquetes de p11 = 0,1. La distribución de retardo (histograma) del enlace directo 20 de la ruta P2 se muestra en la segunda subtrama (media) de la figura 3; el retardo medio es de 3 unidades. En cuanto a la ruta P3, el enlace 31 tiene un retardo fijo de 1, mientras que enlace 32 tiene una distribución de retardo uniforme, representado solo por el límite inferior y superior de la tercera

25 subtrama (inferior) de la figura 3, y la probabilidad de pérdida de paquetes p32 = 0,05.

Cuando la función de densidad de probabilidad exacta pdfi se considera innecesariamente detallada, puede aplicarse alguna representación más ordinaria, por ejemplo, por aproximación lineal por tramos, con el fin de reducir el almacenamiento y la complejidad del cálculo. En otras realizaciones, las mediciones de retardo pueden ajustarse para las longitudes de paquetes, similar a la métrica ETT mencionada anteriormente.

En la etapa S22, el sistema de medición 21 determina la métrica de ruta a partir de las métricas de enlace calculando las distribuciones de probabilidad de retardo de transmisión totales para las diversas rutas P1, P2, P3 a partir de las distribuciones de probabilidad de retardo de transmisión de sus respectivos enlaces 11, 12, 20, 31, 32.

35 Específicamente, la distribución de probabilidad de retardo de transmisión total se determina 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, A/L, B/L, B/C, C/L de la ruta respectiva P1, P2, P3.

La agregación de la métrica de enlace por convolución () de las funciones de densidad de probabilidad pdfi se realiza conforme al supuesto realista de enlaces independientes, cuyos retardos son aditivos. La convolución se necesita para el caso general de distribuciones de probabilidad. Específicamente, los cuantiles de sumas de variables aleatorias no son aditivos, excepto si las variables aleatorias son “co-monótonas” (derivadas de manera monótona a partir de una variable aleatoria subyacente común). Por lo tanto, el cuantil d de la ruta total no puede calcularse como la suma de los cuantiles d de los enlaces individuales, pero debe calcularse a través de las

45 convoluciones de todas las pdfi de la ruta. A continuación, se muestra el pseudo-código para la agregación de las pdfi de los enlaces (nsaltos) en la ruta pdfruta, incluyendo los cálculos de la probabilidad de pérdida pruta de una ruta a partir de pi (= 1 -Di) para pruta:

pdfruta = delta pruta = 0 for i = 1 to nsaltos pdfruta, = pdfruta ⊗pdfi

pruta = pruta + pi -pruta · pi end

55 Es evidente que esta métrica enlace/ruta es más compleja, ya que requiere el mantenimiento de una matriz que contenga la pdfi y el pi (en lugar de un único escalar en las métricas del estado del arte), y un procesamiento más complejo (la convolución, en lugar de simples sumas o multiplicaciones de escalares). Sin embargo, esta complejidad se encuentra dentro de la capacidad de los modernos procesadores integrados. El almacenamiento y el procesamiento de las métricas de enlace es normalmente solo una pequeña parte del software de enrutamiento global, de manera que la complejidad adicional es aceptable teniendo en cuenta las ventajas de la nueva métrica de enlace propuesta.

Los resultados de la convolución para cada una de las tres rutas P1, P2, P3 de la figura 1 se muestran en la parte

65 superior de la figura 4 (obsérvese que la distribución de retardo de la ruta P1 se desvía del triángulo (= la convolución de las distribuciones de retardo uniformes de los enlaces 11 y 12), debido a la cuantificación diferente

E12737733

06-05-2015

de los valores de retardo para los enlaces 11 y 12, mostrado en la primera (superior) subtrama de la figura 3.

Finalmente, la parte inferior de la figura 4 muestra las distribuciones de probabilidad acumuladas de las tres rutas P1, P2, P3, obtenidas acumulando las probabilidades de retardo en la parte superior de la figura 4. Una posible 5 brecha entre el punto final derecho de la distribución acumulativa y 1 es igual a la probabilidad de pérdida de paquetes pruta de la ruta.

En la etapa S3, el módulo de enrutamiento 22 selecciona, a partir de entre las posibles rutas P1, P2, P3 que conducen desde el nodo de origen B al nodo de destino L, la ruta preferida en base a las métricas de ruta actuales y 10 de acuerdo con un criterio de selección pertinente para el paquete de datos a transmitir.

En la etapa S31, el módulo de enrutamiento 22 determina la clase o tipo del paquete de datos a transmitir.

En la etapa S32, el módulo de enrutamiento 22 determina para la clase o tipo de paquete de datos, por ejemplo, a 15 partir de la tabla de calidad de servicio, el criterio de selección a aplicarse para seleccionar la ruta preferida.

Por ejemplo, los diversos criterios de enrutamiento, que pueden derivarse a partir de las distribuciones de probabilidad acumuladas, incluyen:

20  seleccionar la ruta con la más alta probabilidad de cumplir este límite superior, dado un retardo de ruta máximo,

 seleccionar la ruta con el más bajo cuantil d, dada una probabilidad  cercana a 1, y

 seleccionar la ruta con la más alta proporción de entrega de paquetes D (= 1 -pruta).

25 En la etapa S33, el módulo de enrutamiento 22 aplica el criterio de selección para las métricas de ruta de las posibles rutas P1, P2, P3 desde el nodo de origen B al nodo de destino L. Específicamente, el módulo de enrutamiento 22 aplica el criterio de selección a las distribuciones de probabilidad de retardo de transmisión totales de las posibles rutas P1, P2, P3.

30 En la etapa S34, el módulo de enrutamiento 22 determina la ruta (óptima) preferida en base a los resultados de la etapa S33.

Por lo tanto, en función de los criterios y sus parámetros, correspondientes a diferentes requisitos de QoS para los 35 paquetes del mismo par de origen/destino, pueden seleccionarse las diferentes rutas, todas en base a la misma nueva métrica de enlace que incorpora la distribución de retardo de enlace.

Debería tenerse en cuenta que, en la descripción, el código de programa de ordenador se ha asociado con los módulos funcionales específicos y la secuencia de las etapas se ha presentado en un orden específico, un experto

40 en la materia entenderá, sin embargo, que el código de programa de ordenador puede estar estructurado de manera diferente y que puede alterarse el orden de al menos algunas de las etapas, sin desviarse del alcance de la invención.

Claims

REIVINDICACIONES

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

5 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

15 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.

25 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

35 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.

5
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

10 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

15 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

20 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

25 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.

8