Control de admisión y planificación de tráfico de datos por paquetes.

Método para procesar, en un sistema de comunicaciones, un flujo continuo de paquetes de datos que transporta tráfico de datos en tiempo real,

con las etapas de

- recibir un primer paquete de control de sincronización (SCP) insertado en el flujo continuo de paquetes de datos, en donde el primer paquete de control de sincronización (SCP) incluye un número de p parámetros de control de sincronización, con p ≥ 1, 2, 3,...,

- leer por lo menos un parámetro de control de sincronización a partir del paquete de control de sincronización (SCP), - recibir por lo menos un paquete de datos de carga útil del flujo continuo de paquetes de datos,- determinar para cada paquete de datos de carga útil un plazo límite de entrega usando por lo menos un parámetro de control de sincronización, y

- ordenar el por lo menos un paquete de datos de carga útil de acuerdo con su plazo límite de entrega determinado, en una primera cola (EDF) y fijar una indicación de tiempo para el por lo menos un paquete de datos de carga útil en la primera cola (EDF) al plazo límite de entrega determinado.

Control de admisión y planificación de tráfico de datos por paquetes.

Campo de la Invención La presente invención se refiere en general al procesamiento de tráfico de datos por paquetes en un sistema de comunicaciones, y en particular a la planificación de paquetes de datos y al control de admisión.

Antecedentes de la Invención A partir de la técnica anterior, se conocen dos conceptos para la provisión de calidad de servicio en una red de comunicaciones orientada a paquetes.

Un concepto es el denominado Concepto de Servicios Integrados, que se basa en la reserva de recursos para flujos continuos dedicados de paquetes de datos. Para la reserva de recursos, es necesaria una señalización de requisitos entre entidades pares antes de una transmisión de datos de carga útil. A todos los nodos de red a lo largo de un trayecto de transmisión se les solicita reservar recursos correspondientes. El Concepto de Servicios Integrados se describe en: D. Clark et al., Supporting Real-time Applications in an Integrated Services Packet Network: Architecture and Mechanisms, Proceedings SIGCOMM 92, agosto de 1992.

Un protocolo de señalización conocido es el denominado Protocolo de Reserva de Recursos RSVP, que se describe en: L. Zhang et al., RSVP: A New Resource Reservation Protocol, IEEE Network Magazine, septiembre de 1993. El RSVP es un protocolo símplex orientado a receptores, que reserva recursos en una dirección a lo largo de un trayecto de comunicaciones. El receptor del flujo de datos es responsable del inicio de la reserva de recursos.

El esquema denominado TENET es similar al Concepto de Servicios Integrados (véase, D. Ferrari et al., A Scheme for Real-Time Channel Establishment in Wide Area Networks, IEEE Journal on Selected Areas of Communications, vol. 8, págs. 368 a 379, 1990) . Proporciona retardos garantizados para servicios de tiempo real en una red de área extensa por conmutación de paquetes y permite la asignación de ancho de banda por flujo de paquetes. En este esquema, los clientes declaran sus características de tráfico y requisitos de rendimiento en el momento del establecimiento del canal de comunicaciones. Después de que se haya establecido un canal, se planifican paquetes de datos basándose en plazos límite en los anfitriones y en los nodos de red. Para realizar esto, un planificador mantiene por lo menos tres colas: una para paquetes deterministas, una para paquetes estadísticos, y la tercera para la totalidad del resto de tipos de paquetes y todas las tareas locales.

Otro concepto para la provisión de calidad de servicio es el denominado Concepto de Servicios Diferenciados, que pretende simplificar la clasificación y planificación de paquetes con requisitos de calidad de servicio mediante el uso de bits de prioridad en un encabezamiento del protocolo. Todos los paquetes pertenecientes a una clase de calidad de servicio específica se marcarán con una combinación correspondiente de bits de prioridad en el encabezamiento del Protocolo de Internet. Los flujos de paquetes se marcan con los bits de prioridad y se supervisan en concordancia con un Acuerdo a Nivel de Servicio en el borde de la red. En el interior de la red, los paquetes se planifican basándose en los bits de prioridad. Para el Concepto de Servicios Diferenciados, se proporciona la referencia S. Blake et al., An Architecture for Differentiated Services, IETF RFC 2475, diciembre de 1998.

El control de admisión de flujos continuos de paquetes de datos y la planificación del orden de transmisión de paquetes de datos con el fin de minimizar violaciones de plazos límite de aplicaciones multimedia de tiempo real o tiempo casi real son tareas importantes en las redes de comunicaciones que contienen cuellos de botella. En lo sucesivo, la expresión “tiempo real” debería entenderse también como “tiempo casi real” o, en general, como “sensible al tiempo”. En redes heterogéneas, los cuellos de botella aparecen en límites de redes en los que el tráfico de una red se hace pasar a otra.

Habitualmente, ciertos plazos límite de tiempo real no se hacen pasar en caso de que se retarde únicamente un paquete de datos. En cambio, habitualmente un conjunto de paquetes de datos abarca una entidad de sincronización que debe llegar al destino, por ejemplo, para visualizar una parte de una salida multimedia a tiempo.

Los nodos de aplicación e intermedios se vuelven cada vez más inteligentes y permiten la adaptación multimedia. Esto significa que la cantidad de ancho de banda de datos necesaria para la transmisión de un cierto objeto multimedia o presentación no es fija. El proceso de adaptación se puede realizar por varios medios como la omisión de paquetes de prioridad inferior, codificación multimedia jerárquica, aplicación adaptativa, pasarelas de adaptación de ancho de banda o incluso redes activas que despliegan elementos de procesamiento dentro de nodos de red. Así, en caso de congestión, el ancho de banda puede variar dentro de un cierto intervalo. Las aplicaciones o la propia red pueden cumplir la tarea de adaptación necesaria para variar la velocidad de transmisión real con el fin de evitar violaciones de plazos límite.

Los esquemas existentes de control de admisión y de planificación permiten únicamente una baja utilización del ancho de banda por medio de asignaciones de velocidades de pico y garantías de retardo que se proporcionan para fuentes de paquetes en ráfagas. Los esquemas mejorados están alcanzando una mayor utilización del ancho de banda mediante la aplicación de algoritmos de medición que predicen el ancho de banda disponible real midiendo el uso pasado del ancho de banda. No obstante, los algoritmos basados en mediciones proporcionan únicamente garantías débiles y solamente funcionan eficazmente con una alta cantidad de multiplexado estadístico. En especial, las redes inalámbricas están limitadas habitualmente en cuanto a capacidad de ancho de banda y, por lo tanto, los esquemas de control de admisión basados en mediciones y deterministas presentan rendimientos deficientes. Una de las razones es que los esquemas existentes para la planificación de paquetes tratan cada paquete de la misma manera. No pueden detectar plazos límite pasados que son relevantes para las aplicaciones de recepción y, por lo tanto, no pueden activar procesos que convierten el sistema actual a un estado exento de errores.

Los esquemas tradicionales clasifican cada flujo continuo de paquetes en una clase de prioridad. En el Concepto de Servicios Integrados, esta clase de prioridad pertenece a un retardo promedio que experimentarán los paquetes de un flujo continuo particular. En el planteamiento de los Servicios Diferenciados, esta clase de prioridad pertenece a un tipo de tráfico que debería presentar un retardo menor que otros. La clase de prioridad está vinculada habitualmente a un retardo promedio que se espera que experimente el paquete cuando es admitido en esa clase de prioridad. Cuando se consideran flujos continuos multimedia con velocidades de bits variables (como flujos continuos de vídeo) , los paquetes de un flujo continuo individual no presentarán los mismos requisitos de retardo con el paso del tiempo. En cambio, una planificación mediante la determinación de un plazo límite de entrega para cada paquete individual, según propone la presente invención, proporciona un rendimiento mejor que una planificación basada en prioridades.

Liebeherr et al. describen en “Work conserving vs, non-work conserving packet scheduling: An issue revisited”, 1999 7th International Workshop on Quality of Service, Londres, RU, 31 de mayo a 4 de junio de 1999, ISBN: 0-78035671-3, un planificador que usa un mecanismo sintonizable de control de velocidad. El planificador se basa en la prontitud, en donde a cada paquete se le marca una indicación de tiempo con un plazo límite que se fija igual a una suma de su tiempo de llegada y un retardo vinculado.

Por lo tanto, es un objetivo de la presente invención proporcionar un planteamiento mejorado para sistemas de comunicaciones orientados a paquetes, que supere estos y otros problemas, en particular permitir una planificación, orientada a tiempos límite, de paquetes de datos que transporten tráfico de datos en tiempo real.

Este objetivo se logra mediante las enseñanzas de las reivindicaciones independientes. En las reivindicaciones dependientes se ofrecen otras realizaciones preferidas.

La solución descrita en la invención resulta ventajosa gracias a las asignaciones de plazos límite de entrega individuales para paquetes de datos de carga útil que están sujetos a un procesamiento en tiempo real. Esto es especialmente útil para paquetes de datos de un flujo continuo multimedia... [Seguir leyendo]

1. Método para procesar, en un sistema de comunicaciones, un flujo continuo de paquetes de datos que transporta tráfico de datos en tiempo real, con las etapas de

- recibir un primer paquete de control de sincronización (SCP) insertado en el flujo continuo de paquetes de datos, en donde el primer paquete de control de sincronización (SCP) incluye un número de p parámetros de control de sincronización, con p = 1, 2, 3, ...,

- leer por lo menos un parámetro de control de sincronización a partir del paquete de control de sincronización (SCP) ,

- recibir por lo menos un paquete de datos de carga útil del flujo continuo de paquetes de datos,

- determinar para cada paquete de datos de carga útil un plazo límite de entrega usando por lo menos un parámetro de control de sincronización, y - ordenar el por lo menos un paquete de datos de carga útil de acuerdo con su plazo límite de entrega determinado, en una primera cola (EDF) y fijar una indicación de tiempo para el por lo menos un paquete de datos de carga útil en la primera cola (EDF) al plazo límite de entrega determinado.

2. Método según la reivindicación 1, en el que la etapa de leer por lo menos un parámetro de control de sincronización comprende la lectura de

- un número de paquetes (N) en una entidad de sincronización, que comprende paquetes de datos de carga útil

- un tiempo de transmisión máximo (I) , permitido para una transmisión en tiempo real de la entidad de sincronización

- un tamaño de bytes (S) para cada paquete de carga útil,

y en donde la determinación del plazo límite de entrega para cada paquete de datos de carga útil comprende las etapas de

- determinar una tasa de errores de paquete (Pj) de un canal (j) usado para transmitir la entidad de sincronización,

- determinar una velocidad de bits (Rj) de dicho canal (j) ,

- determinar un valor de tiempo (t) que indica un tiempo de llegada actual de paquetes de datos de carga útil, y

- calcular el plazo límite de entrega a partir de los mismos.

3. Método según la reivindicación 2, en el que el plazo límite de entrega para un paquete de datos de carga útil actual i se calcula de la manera siguiente:

∃N & i ∋1%) S

plazo límite ( t ∋ I & , i #!1..N∀.

iN ) (1- Pj) ) Rj

4. Método según la reivindicación 1, 2 ó 3 con las etapas adicionales de

- recibir un primer paquete de control de admisión (ACP) que incluye un número de q parámetros de control de admisión, con q =1, 2, 3, ...,

- leer a partir de dicho primer paquete de control de admisión (ACP) por lo menos un parámetro de control de admisión que indica un caudal (R1) requerido para un procesamiento en tiempo real de un subflujo continuo de paquetes de datos, el cual se recibe después del primer paquete de control de admisión y antes de un segundo paquete de control de admisión,

- determinar un caudal disponible actualmente (V) ,

- comparar el caudal disponible (V) con el caudal requerido (R1) ,

- admitir el procesamiento en tiempo real del subflujo continuo, si el caudal disponible (V) es mayor que o igual al caudal requerido (R1) , y enviar dicho subflujo continuo a un planificador de paquetes.

5. Método según la reivindicación 4, en el que

- la etapa de leer el por lo menos un parámetro de control de admisión comprende la lectura de un caudal máximo (Rh) ,

con la etapa adicional de

- escoger para un subflujo continuo un caudal entre el caudal requerido mínimo (R1) y un mínimo del caudal máximo (Rh) y el caudal disponible (V) .

6. Método según la reivindicación 4 ó 5, con la etapa adicional de

- rechazar el procesamiento en tiempo real del subflujo continuo, si dicho subflujo continuo no se admite para un procesamiento en tiempo real, y enviar dicho subflujo continuo al planificador de paquetes.

7. Método según la reivindicación 6, con la etapa adicional, en el caso de rechazo del subflujo continuo para un procesamiento en tiempo real, de

- ordenar en el planificador de paquetes los paquetes de datos en su orden de aparición en una segunda cola (FIFO) .

8. Método según la reivindicación 7, con las etapas adicionales de

- procesar adicionalmente los paquetes de datos de la primera cola (EDF) de acuerdo con sus plazos límite de entrega, y

- procesar adicionalmente los paquetes de datos de la segunda cola de acuerdo con una estrategia del primero en entrar -primero en salir.

9. Método según la reivindicación 6, 7 u 8, con la etapa adicional de

- priorizar, por medio de una interfaz de salida para el procesamiento adicional, paquetes de datos contenidos en la primera cola (EDF) y paquetes de datos contenidos en la segunda cola (FIFO) .

10. Método según cualquiera de las reivindicaciones 4 a 9, con la etapa adicional de

- generar y devolver, desde un controlador de admisiones (AC) a lo largo del trayecto de transmisión del subflujo continuo, un paquete de control de admisión modificado que comprende parámetros de capacidad de caudal de dicho controlador de admisiones (AC) .

11. Método según cualquiera de las reivindicaciones 1 a 10, con la etapa adicional de

- recibir los parámetros de control de sincronización a partir de un encabezamiento de un protocolo de red subyacente.

12. Método según cualquiera de las reivindicaciones 1 a 11, con la etapa adicional de

- detectar una violación de plazo límite comparando repetidamente, para paquetes de carga útil ordenados en la primera cola (EDF) , su tiempo real pasado en dicha primera cola con sus plazos límites de acuerdo con sus indicaciones de tiempo.

13. Método según la reivindicación 12, con la etapa adicional de

- realizar, después de detectar la violación del plazo límite, una adaptación de por lo menos un paquete de datos de carga útil de la primera cola (EDF) .

14. Método según cualquiera de las reivindicaciones 1 a 13, con la etapa adicional de

- recibir los parámetros de control de admisión a partir de un encabezamiento de un protocolo de red subyacente.

15. Nodo de red, en un sistema de comunicaciones, para procesar un flujo continuo de paquetes de datos que transporta tráfico de paquetes de datos en tiempo real, que comprende

- una unidad de determinación de tasas de errores de paquete para determinar una tasa de errores de paquete (Pj) de un canal de comunicaciones (j) ,

- una unidad de determinación de velocidades de bits para determinar una velocidad de bits (Rj) de dicho canal de comunicaciones (j) , -un temporizador para determinar, para por lo menos un paquete de datos de carga útil del flujo continuo de paquetes de datos, recibiéndose el paquete de datos de carga útil en el nodo de red, un valor de tiempo actual (t) , indicando el valor de tiempo actual (t) un tiempo de llegada del paquete de datos de carga útil al nodo de red,

- unos medios de lectura para leer parámetros de control de sincronización proporcionados por al menos un paquete de control de sincronización (ACP, SCP) insertado en el flujo continuo de paquetes de datos,

- una unidad de cálculo para cálculos de plazos límite de entrega para paquetes de datos de carga útil usando por lo menos un parámetro de control de sincronización, y

- una primera cola (EDF) para ordenar el por lo menos un paquete de datos de carga útil de acuerdo con una indicación de tiempo fijada, para el por lo menos un paquete de datos de carga útil, a su plazo límite de entrega calculado.

16. Nodo de red según la reivindicación 15, en el que la primera cola (EDF) incluye una unidad de ordenación para ordenar paquetes de datos de acuerdo con sus plazos límite en la primera cola (EDF) , siguiendo dicha unidad de ordenación una estrategia del tipo en primer lugar el plazo límite más cercano, y en donde dicha unidad de ordenación fija indicaciones de tiempo de la primera cola (EDF) de acuerdo con plazos límite calculados.

17. Nodo de red según la reivindicación 15 ó 16, que comprende adicionalmente

- una unidad de determinación para determinar un caudal disponible actualmente (V) del nodo de red, y

- unos medios de decisión para decidir si un flujo de tráfico de paquetes de datos entrante se puede procesar en el nodo de red de acuerdo con requisitos de tiempo real proporcionados por parámetros de control de admisión.

18. Nodo de red según cualquiera de las reivindicaciones 15 a 17, que comprende además

- una segunda cola (FIFO) para paquetes de datos que no se admiten para un procesamiento en tiempo real,

- una unidad de transferencia para reenviar un flujo de tráfico de paquetes de datos después de una decisión positiva por parte de los medios de decisión hacia la primera cola (EDF) o después de una decisión negativa hacia la segunda cola (FIFO) , y

- una interfaz de salida (OI) que prioriza todas las colas y que lee paquetes de datos de todas las colas.

19. Nodo de red según cualquiera de las reivindicaciones 15 a 18, que comprende además

- un gestor de violaciones de plazos límite para monitorizar plazos límite de paquetes de datos, para una detección de por lo menos una violación de plazo límite, y para un inicio de una adaptación de por lo menos un paquete de datos, y

- una unidad de adaptación para la adaptación de por lo menos un paquete de datos.

20. Nodo de red según cualquiera de las reivindicaciones 15 a 19, que incluye además una estación base de radiocomunicaciones para recibir y transmitir dicho tráfico de paquetes de datos en tiempo real.

21. Programa de ordenador, cargable en una memoria de un ordenador digital, que comprende partes de código de software para realizar las etapas de

- detectar en un flujo continuo de paquetes de datos, que transporta tráfico de datos en tiempo real, y que se recibe en un planificador de paquetes, por lo menos un paquete de control de sincronización (SCP) , al cual le sucede una entidad de sincronización que comprende por lo menos un paquete de datos de carga útil, comprendiendo dicho paquete de control de sincronización parámetros de control de sincronización,

- leer, a partir del paquete de control de sincronización, un número de paquetes de datos de carga útil en la entidad de sincronización (N) , un tiempo de transmisión máximo (I) permitido para una transmisión en tiempo real de la entidad de sincronización y un tamaño de bytes (S) de la entidad de sincronización,

- determinar una tasa de errores de paquete (Pj) de un canal (j) que se usa para transmitir la entidad de sincronización (N) ,

- determinar una velocidad de bits (Rj) de dicho canal (j) ,

- determinar un valor de tiempo (t) que indica un tiempo de llegada actual de paquetes de datos de carga útil, y

- calcular para cada paquete de datos de carga útil un plazo límite de entrega usando por lo menos uno de los parámetros de sincronización, - ordenar cada paquete de datos de carga útil de acuerdo con su plazo límite en una primera cola (EDF) basada en indicaciones de tiempo, y fijar una indicación de tiempo para cada paquete de datos de carga útil de la primera cola (EDF) al plazo límite calculado, cuando dicho programa de ordenador se ejecuta en un ordenador.

22. Programa de ordenador según la reivindicación 21, en el que el plazo límite de entrega para un paquete de datos de carga útil actual (i) se calcula de la manera siguiente:

∃N & i ∋1%) S

plazo límite ( t ∋ I & , i #!1..N∀.

iN ) (1- Pj) ) Rj

23. Programa de ordenador según la reivindicación 21 ó 22, que comprende además partes de código de software para realizar las etapas de - detectar en el flujo continuo de paquetes de datos, que transporta tráfico de datos en tiempo real, y que se recibe en un controlador de admisiones (AC) , un primer paquete de control de admisión (ACP) que comprende parámetros de control de admisión,

- leer por lo menos dos parámetros de control de admisión (R1, Rh) a partir de dicho primer paquete de control de admisión,

- calcular un caudal (V) como una diferencia de un caudal total (Vmax) disponible en dicho controlador de admisiones (AC) y un caudal ocupado actualmente (Vc) ,

- comparar el caudal (V) con el caudal requerido (R1) , y

- si el caudal disponible (V) es menor que el caudal requerido más bajo (R1) , entonces rechazar un procesamiento en tiempo real de un subflujo continuo de paquetes de datos que viene a continuación entre dicho primer paquete de control de admisión y un segundo paquete de control de admisión, o si no, escoger un valor de caudal de entre un intervalo de valores de caudal, incluyendo dicho intervalo, como límites, el caudal requerido más bajo (R1) y un segundo valor de caudal (Rh, M) y admitir un procesamiento en tiempo real de dicho subflujo continuo.

24. Programa de ordenador según la reivindicación 23, que comprende además partes de código de software para realizar la etapa de - generar y enviar de vuelta desde el controlador de admisiones (AC) , a lo largo del trayecto de transmisión del subflujo continuo, un paquete de control de admisión modificado que comprende parámetros de capacidad de caudal de dicho controlador de admisiones (AC) .

25. Programa de ordenador según la reivindicación 23 ó 24, que comprende además partes de código de software 25 para realizar la etapa de

- ordenar los paquetes de datos de un subflujo continuo que es rechazado para un procesamiento en tiempo real, en su orden de aparición en una segunda cola (FIFO) .

26. Programa de ordenador según la reivindicación 25, que comprende además partes de código de software para realizar la etapa de

- priorizar para la lectura paquetes de datos contenidos en la primera cola (EDF) y paquetes de datos contenidos en la segunda cola (FIFO) .

27. Programa de ordenador según cualquiera de las reivindicaciones 21 a 26, que comprende además partes de código de software para realizar la etapa de

- detectar una violación de plazo límite de entrega comparando repetidamente, para paquetes de datos

ordenados en la primera cola (EDF) , un valor de tiempo real con sus plazos límite según sus indicaciones de tiempo.

28. Programa de ordenador según la reivindicación 27, que comprende además partes de código de software para realizar las etapas de

- realizar, después de detectar la violación de retardo, una adaptación de por lo menos un paquete de datos de la primera cola (EDF) .

29. Programa de ordenador según cualquiera de las reivindicaciones 23 a 28, que comprende además partes de 50 código de software para realizar la etapa de

- leer los parámetros de control de admisión a partir de un encabezamiento de un protocolo de red subyacente.

30. Programa de ordenador según cualquiera de las reivindicaciones 21 a 29, que comprende además partes de código de software para realizar la etapa de

- leer los parámetros de control de sincronización a partir de un encabezamiento de un protocolo de red subyacente.