Se proporciona un método y un programa para estimar los parámetros de un elemento de control del tipo token-bucket para el control o regulación de la transmisión de paquetes de datos (QoS) en redes de comunicación.

Este método permite estimar de forma no intrusiva aquellos parámetros para cada servicio controlado por un regulador token-bucket. Además este método es capaz de discriminar las interferencias a través de dicho servicio y permitiendo ser ejecutado en presencia de procesos en aquellos sistemas con recursos compartidos. Mediante este método se permite la obtención de los parámetros de un elemento de control del tipo token-bucket, de tal forma que permite verificar acuerdos de nivel de servicio (SLA) entre una empresa y un operador de telecomunicaciones. Junto con lo anterior se proporciona un programa de ordenador capaz de ejecutar este método.

Método para estimar los parámetros de un elemento de control del tipo token-bucket.

Campo técnico de la invención

La invención se sitúa en el ámbito de las tecnologías de Calidad de Servicio (Quality of Service, QoS) parael control o regulación de la transmisión de paquetes de datos en redes de comunicación. Más en concreto se refiere a un método no intrusivo que permite estimar aquellos parámetros para cada servicio controlado por un regulador tokenbucket. Además, este método es capaz de discriminar las interferencias a través de dicho servicio permitiendo ser ejecutado en presencia de procesos en aquellos sistemas con recursos compartidos. Mediante este método se permite la obtención de los parámetros de un elemento de control del tipo token-bucket, de tal forma que permite verificar acuerdos de nivel de servicio (SLA) entre una empresa y un operador de telecomunicaciones.

Estado de la técnica

Las tecnologías QoS son especialmente importantes para ciertas aplicaciones -tales como la transmisión de vídeo

o voz-dado que intentan garantizar la transmisión de cierta cantidad de datos en un tiempo dado. Dentro de las tecnologías se encuentra el algoritmo token-bucket que es un sistema de control de admisión de una red. Esto es, un algoritmo cuyo objetivo es limitar la tasa de transmisión a la cual un tipo de servicio o un usuario inyectan tráfico en una red.

El funcionamiento de un algoritmo token-bucket se puede encontrar en el estado de la técnica. En particular el algoritmo admite la entrada de paquetes de información y genera tokens, instancias particulares asociadas a los paquetes de información, a una a tasa constante de generación de tokens (CIR) . Estos tokens son capaces de transportar los paquetes de información desde la entrada. Estos tokens se acumulan en un “cubo” de tamaño Br. En este algoritmo se retira un token cuando se transmite un paquete de datos. El sistema puede consumir todos los tokens acumulados en el cubo si se llega a un volumen de datos suficiente de forma que es posible mandar ráfagas de datos (bursts) a una velocidad máxima de transmisión (PIR) cuando hay tokens disponibles a diferencia de otros algoritmos como el leaky bucket.

De este modo, ante la entrada de un flujo variable de datos, si existen tokens acumulados, éstos son empleados en transmitir paquetes a la máxima velocidad de transmisión; y, si han sido consumidos, los paquetes sólo pueden ser transmitidos conforme se generan tokens, esto es, a la tasa máxima de generación de tokens.

Este mismo algoritmo token-bucket también puede ser aplicado para limitar a distintas velocidades dependiendo del tipo de servicio. Por ejemplo, dar una velocidad para las aplicaciones en tiempo real (teleconferencia, vídeo bajo demanda, etc.) y otra distinta para las transferencias de ficheros. Esto se realiza añadiendo una cola y un cubo para cada tipo de servicio, pudiendo así darle una tasa de transmisión distinta a cada servicio.

Se plantea como problema técnico la determinación de los parámetros CIR, PIR y tamaño del cubo, ya que ésta no se puede realizar mediante herramientas genéricas de medida de ancho de banda, como SpeedTest (www.speedtest.net) . Estas herramientas no son capaces de medir un enlace limitado por el algoritmo token-bucket porque obtienen como resultado un ancho de banda que refleja un promedio del CIR yel PIR, ponderado según el tamaño del cubo. Por tanto, no ofrecerían un resultado fiable a la hora de la verificación de un contrato SLA, y, en ningún caso, serían capaces de extraer los parámetros CIR, PIR y Br que limitan el enlace, ni para el caso de una única cola, ni, mucho menos, para el caso de varias colas según tipo de servicio.

Otros métodos como los descritos por Rosario G. Garroppo, Stefano Giordano, Michele Pagano, “Estimation of token-bucket parameters for aggregated VoIP sources” International Journal of Communication Systems Vol. 15 n. 10 pp 851-866 (2002) , plantean un método analítico para la estimación de los parámetros CIR y Br de un filtro tokenbucket. No obstante, el principal problema del método propuesto es la necesidad de conocer el modelo estocástico del tráfico multiplexado de la entrada, lo cual no es viable en un entorno real, donde la distribución del tráfico no es conocida y es muy dependiente del contexto de la red concreta.

Es decir, no se conocen métodos para estimar estos parámetros del token-bucket de forma no intrusiva, siendo además necesario estimar los parámetros CIR, PIR, Br en presencia de tráfico interferente. El tráfico interferente está presente en muchos entornos donde la medida es de máximo interés industrial. La presencia de un tráfico interferente puede distorsionar la medida siendo un obstáculo para medir un enlace en uso, no vacío, que resulta el entorno de mayor interés en muchas ocasiones.

Además, cuando la estimación de estos parámetros se lleva a cabo mediante un dispositivo dedicado o compartido,

(i.e. en el que se ejecutan procesos a la misma vez que el proceso de medida) , ocurre que la estimación puede estar contaminada debido a procesos contaminantes en el mismo hilo de ejecución (thread) y por tanto no ser representativa para un control correcto del tráfico. Es necesario por tanto dotar de un método capaz de estimar aquellos parámetros clave y seleccionar aquellas estimaciones representativas de la medida desechando el resto.

El solicitante no conoce soluciones que permitan la medición o estimación de los parámetros del algoritmo tokenbucket de un router comercial tal y como lo hace el método que se presenta, tanto para el caso de una única cola, como para el caso de varias colas según tipo de servicio.

Descripción de la invención

El objeto de la invención es proporcionar un método para estimar los parámetros de un elemento de control del tipo token-bucket, comprendido en una red de comunicaciones. Este método permite estimar los parámetros del tokenbucket con la exactitud y precisión requeridas para verificar acuerdos de nivel de servicio (SLA) . Dicho método se encuentra definido por la reivindicación 1 independiente. En un segundo aspecto inventivo se proporciona un programa para implementar este método según la reivindicación 15 independiente.

Un primer aspecto inventivo comprende un método para estimar los parámetros del token-bucket donde entre otras etapas se detecta un cambio entre una primera velocidad de transmisión (máxima) y una segunda velocidad, y permite determinar los parámetros CIR, PIR y el tamaño del cubo en modo operativo. Este método comprende los siguientes pasos:

- se genera un tren de N paquetes sonda marcados para su identificación y se inyectan en la línea de entrada por medio de los medios de emisión.

En un primer paso se genera un tren de N paquetes que denominaremos “paquetes sonda”. Estos paquetes sonda son marcados para su identificación con un identificador de paquete. Así, la lectura del paquete posterior de estos paquetes permite identificar a un paquete leído como un paquete perteneciente al tren de paquetes sonda. Los paquetes sonda se inyectan en la línea de entrada, que puede tener o no paquetes interferentes, utilizando preferentemente un servicio, utilizando unos medios de emisión. En un ejemplo de realización estos paquetes tienen un tamaño similar B.

Cuando los medios de emisión suministran los paquetes sonda a la línea de entrada, estos paquetes se insertan en el flujo de datos regulado por el token-bucket. El elemento de control token-bucket recibe los paquetes y los transmite por la línea de salida junto con otros dos paquetes.

- se leen los instantes de tiempo de paso de cada uno de los paquetes sonda a través de los medios de sonda de la línea de salida.

En un segundo paso unos medios de sonda permiten leer los instantes de tiempo de paso t1, ... tN. Estos instantes reflejan el tiempo que cada paquete sonda alcanza los medios de sonda en la línea de salida.

- a partir de los instantes de tiempo de paso de los paquetes sonda se determina su velocidad de transmisión.

En un tercer paso, a partir de los diferentes tiempos t1, ... tN, se determina la velocidad de transmisión de datos por los paquetes sonda, y, para un tren de varios paquetes sonda, se puede estimar una velocidad de transmisión... [Seguir leyendo]

1. Método para estimar los parámetros de un elemento de control del tipo token-bucket (3) que comprende: -un elemento de control tipo token-bucket (3) ; -una línea de salida; -al menos una línea (2) de entrada; -unos medios (4) de emisión para la inyección de datos en la línea (2) de entrada; y, -unos medios de sonda para la lectura de datos en la línea de salida;

en donde el elemento de control tipo token-bucket (3) está caracterizado por: -una tasa de generación de tokens (CIR) ; -una velocidad máxima de transmisión de la salida (PIR) ; y, -un tamaño de cubo (Br) ,

donde el método comprende las siguientes etapas: -se genera un tren (1) de N paquetes sonda marcados para su identificación y se inyectan en la línea (2) de entrada por medio de los medios (4) de emisión, -se leen los instantes de tiempo de paso de cada uno de los paquetes (1.1-1.N) sonda a través de los medios de sonda de la línea de salida, -a partir de los instantes de tiempo de paso de los paquetes (1.1-1.N) sonda se determina su velocidad de transmisión, -a partir de la velocidad de transmisión de los paquetes (1.1-1.N) sonda se establece si hay un cambio de velocidad entre los paquetes (1.1-1.r-1) sonda del principio y los paquetes (1.r-1.N) sonda del final del tren

(1) de paquetes sonda, -caso de haber un cambio de velocidad:

• la velocidad de los primeros paquetes (1.1-1.r-1) sonda determina la velocidad máxima de transmisión a la salida (PIR) ,

• la velocidad de los segundos paquetes (1.r-1.N) sonda determina la tasa de generación de tokens (CIR) ; y,

• el volumen de datos que corresponde a los paquetes con la velocidad máxima de transmisión determina el tamaño del cubo en modo operativo (Br) ;

y caso de no haber cambio de velocidad se considera la medida no válida.

2. Método según la reivindicación 1 caracterizado porque en la inyección en la línea (2) de entrada de los N paquetes (1.1-1.N) sonda se estima o determina si todos los huecos entre paquetes (1.1-1.N) sonda tienen al menos un paquete (7) interferente, en cuyo caso se considera la medida no válida.

3. Método según la reivindicación 2 caracterizado porque se estima si no existen parejas de paquetes (1.k, 1.k+1) sonda contiguos de la siguiente forma:

• se determina la probabilidad P de que todos los huecos entre paquetes (1.1-1.N) sonda tienen al menos un paquete (7.1) interferente,

• se determina un valor T umbral de aceptación de la media, si la probabilidad P es mayor que T entonces la medida se considera no válida.

4. Método según la reivindicación 3 caracterizado porque la probabilidad P de que todos los N-1 huecos entre paquetes (1.1-1.N) sonda tienen al menos un paquete (7.1) interferente se establece del siguiente modo:

• en la inyección en la línea (2) de entrada de los N paquetes (1.1-1.N) sonda se determina el número de paquetes (7) interferentes m inyectados a través de los mismos medios (4) de emisión y que resultan intercalados entre los paquetes (1.1-1.N) sonda,

• dados los N-1 huecos, el hueco i-ésimo puede estar ocupado por ni paquetes (7) interferentes con i = 1, ...,

N−1

N-1, donde m = ni de modo que se considera que cada uno de los paquetes (7) interferentes tiene la

i=1

misma probabilidad de caer en cualquiera de los huecos entre paquetes (1.1-1.N) sonda,

• se considera que cada uno de los paquetes (7) interferentes pueden caer en un hueco determinado independientemente de si lo ha hecho otro paquete interferente,

• se determina la función densidad de probabilidad multinomial Pmul (n1, n2, ... nN−1) y a partir de ésta se determina la probabilidad P = Pmul (mini=1, ..., N−1 n1 ≥ 1) .

5. Método según la reivindicación 2 caracterizado porque en la inyección en la línea (2) de entrada de los N paquetes (1.1-1.N) sonda se determina:

• el número m de paquetes (7) interferentes inyectados a través de los mismos medios (4) de emisión y que resultan intercalados entre los paquetes (1.1-1.N) sonda,

• un valor M umbral de rechazo,

la estimación de que todos los huecos entre paquetes (1.1-1.N) sonda tienen al menos un paquete (7.1) interferente se establece cuando N+m es mayor que M.

6. Método según la reivindicación 1 caracterizado porque los medios (4) de emisión están implementados en un ordenador que contiene unos medios de almacenamiento y una unidad de procesamiento de datos.

7. Método según la reivindicación 6 caracterizado porque si el nivel de carga de la unidad de procesamiento de datos supera un valor umbral CPUload entonces la medida es rechazada.

8. Método según la reivindicación 6 caracterizado porque si el nivel de carga de los medios de almacenamiento supera un valor umbral MEMload entonces la medida es rechazada.

9. Método según la reivindicación 1 en dónde el cambio de velocidad se establece cuando el tiempo entre dos paquetes (1.k, 1.k+1) consecutivos es superior a TNom.

10. Método según la reivindicación 1 en donde el parámetro PIR se estima como el mínimo de la velocidad entre paquetes (1.1-1.r-1) sonda antes del cambio de velocidad.

11. Método según la reivindicación 1 en donde el parámetro CIR se estima como el mínimo de la velocidad entre paquetes (1.r-1.N) sonda después del cambio de velocidad.

12. Método según la reivindicación 1 en donde el tamaño del cubo en modo operativo Br se estima como el producto

entre el factor

y el volumen de datos transmitido antes del cambio de velocidad.

13. Método según la reivindicación 1 donde el tamaño del paquete (1.1-1.N) sonda es sustancialmente unidad máxima de trasmisión de la red (MTU) .

14. Método según la reivindicación 1 donde el número de paquetes sonda (1.1-1.N) en el tren (1) de paquetes sonda es 100.

15. Programa de ordenador para realizar la estimación de los parámetros de un elemento de control del tipo tokenbucket (3) en un ordenador según un conjunto de instrucciones que implementan en un ordenador un método según la reivindicación 1.