PROCEDIMIENTO, SISTEMA Y ENCAMINADOR PARA PROPORCIONAR UNA GESTIÓN DE COLA ACTIVA EN SISTEMAS DE TRANSMISIÓN DE PAQUETES.

Un procedimiento de gestión de cola activa para controlar tráfico priorizado en un sistema de transmisión de paquetes,

adaptado para proporcionar diferenciación entre el tráfico que se origina en aplicaciones de velocidad adaptable sensibles a la pérdida de paquetes, en donde al tráfico se le asigna un nivel de precedencia de descarte de entre al menos un primer y un segundo nivel de precedencia de descarte, concretamente dentro de perfil y fuera de perfil, caracterizado por: - calcular una longitud media de cola, avg_ql; - asignar umbrales mínimos, min_th_in y min_th_out, para paquetes dentro de perfil y para paquetes fuera de perfil, respectivamente, y un umbral máximo para la longitud media de cola para paquetes fuera de perfil, max_th_out, y un umbral máximo para paquetes dentro de perfil, max_th_in, donde max_th_out > max_th_in para evitar la inanición, siendo dichos umbrales valores límite del intervalo de longitud media de cola en donde la probabilidad de descarte para paquetes marcados como dentro de perfil, Pin, y la probabilidad de descarte para paquetes marcados como fuera de perfil, Pout, respectivamente, aumentan linealmente con la longitud de cola; - descartar un paquete si avg_ql, cuando llega el paquete, es > max_th; - para un paquete etiquetado como dentro de perfil, calcular avg_ql_in, y, si avg_ql_in > th_in y min_th_in < avg_ql, calcular Pin y descartar, o retener, dicho paquete según el valor de Pin; - para un paquete marcado como fuera de perfil, si min_th_out < avg_ql, calcular Pout y descartar, o retener, dicho paquete según el valor de Pout; - retener todos los paquetes con sus niveles de precedencia de descarte inicialmente asignados cuando la longitud media de cola sea inferior, o igual, a un umbral th_in; - asignar una probabilidad de descarte a cada paquete, determinada a partir de la longitud media de cola; - retener todos los paquetes cuando avg_ql sea inferior a th_in; y - descartar paquetes según su probabilidad de descarte asignada; y siendo max_p_out mayor que max_p_in, donde max_p_out es la probabilidad de descarte máxima de paquetes marcados como fuera de perfil y max_p_in es la probabilidad de descarte máxima para paquetes marcados como dentro de perfil

La presente invención se refiere a procedimientos de gestión de cola activa en sistemas de transmisión de paquetes, especialmente sistemas de Internet, a sistemas de telecomunicaciones que emplean tales procedimientos y a encaminadores (routers) que emplean tales procedimientos.

La arquitectura de Internet actual ofrece solamente un servicio, concretamente el servicio de mejor esfuerzo. La comunidad de Internet ha reconocido la importancia de simplificar los mecanismos de retransmisión, pero también ha reconocido que este único servicio puede no ser suficiente para soportar la gran variedad de aplicaciones en Internet. Por lo tanto, el grupo de trabajo de ingeniería de Internet (IETF) está diseñando extensiones de arquitectura para permitir la diferenciación de servicios en Internet. La arquitectura de servicios diferenciados (DiffServ), véase:

incluye mecanismos para una retransmisión diferenciada.

Un mecanismo propuesto para DiffServ es asignar niveles de precedencia de descarte a paquetes IP. Este mecanismo está incluido en el grupo de comportamiento por salto (PHB) de retransmisión asegurada (AF), véase: -Assured Forwarding PHB Group, de Hainanen J. et. al. (1998), IETF DRAFT, noviembre

de 1998.

AF puede utilizarse para ofrecer una diferenciación entre aplicaciones de velocidad adaptable que responden a la pérdida de paquetes, por ejemplo aplicaciones que utilizan TCP. El tráfico de cada usuario se etiqueta como estando dentro o fuera de sus perfiles de servicio. Los paquetes etiquetados como dentro de perfil tienen asignados una precedencia de descarte inferior que los etiquetados como fuera de perfil. Además, un paquete dentro de un perfil de usuario puede etiquetarse con uno de entre varios niveles de precedencia de descarte. Por el momento hay tres niveles de precedencia de descarte para el grupo PHB AF.

Pueden crearse múltiples niveles de precedencia de descarte con un mecanismo de gestión de cola activa (AQM) aplicado a una cola FIFO. Una propiedad ventajosa de las colas FIFO es que los paquetes se retransmiten en el mismo orden en que llegan. Por lo tanto se evita una reordenación de los paquetes, lo que puede reducir el rendimiento de una conexión TCP.

Además, las colas FIFO son adecuadas para enlaces de alta velocidad ya que pueden implementarse de una manera eficaz. Dos mecanismos AQM conocidos son RIO, véase: -Explicit Allocation of Best Effort Delivery Service, 1997, de Clark D. y Fang W. (1997), URL: http://www.diffserv.lcs.mit.edu/Papers/exp-alloc-ddc-wf.pdf, y WRED, véase:

- Distributed Weighted Random Early Detection, 1998, de la especificación técnica de Cisco

(1998), URL:http://www.cisco.comlunivercd/cc/td/doc/productl/oftware/ios/111/

cc111/wred.pdf.

Normalmente, el tráfico priorizado que entra en una red se controla para evitar sobrecargas. Cuando tal tráfico está controlado de manera apropiada, se ha observado que RIO y WRED ofrecen una diferenciación absoluta cuantificable. Sin embargo, estos mecanismos puede provocar la inanición del tráfico de menor prioridad si este control falla. Es decir, el tráfico etiquetado con cualquier cosa menos con el mayor nivel de prioridad de precedencia de descarte puede sufrir de inanición.

En el control del tráfico se producen fallos debido a imprecisiones en el control de admisión y a cambios de topología. Por ejemplo, el control de admisión basado en mediciones puede aceptar accidentalmente tráfico que provoque una sobrecarga temporal hasta que se detecte esta situación. Además, el sistema de control, o el protocolo de señalización, puede no adaptarse lo suficientemente rápido a los cambios de la topología de encaminamiento de red. Por lo tanto, los acondicionadores de tráfico pueden no estar reconfigurados antes de que se produzca una sobrecarga. Así pues, es preferible que el mecanismo AQM utilizado pueda impedir la inanición a cualquier carga.

RIO puede configurarse para evitar la inanición pero no puede garantizarse una jerarquía estricta entre niveles de precedencia durante periodos de sobrecarga. Es decir, el tráfico etiquetado con el mayor nivel de prioridad de precedencia de descarte puede experimentar una mayor tasa de descarte que el tráfico etiquetado con un nivel de prioridad inferior. Por lo tanto, esta configuración de RIO no es aconsejable. Un mecanismo de puesta en cola no solo debe impedir la inanición, sino que también debe mantener una jerarquía estricta entre niveles de precedencia a cualquier carga.

Un mecanismo de puesta en cola que cree múltiples niveles de precedencia de descarte puede considerarse como tolerante a las cargas si puede cumplir los dos requisitos siguientes a cualquier carga:

- impedir la inanición del tráfico de baja prioridad, es decir, el tráfico de baja prioridad

siempre debe obtener una parte útil del ancho de banda disponible; y

- mantener una jerarquía estricta entre niveles de precedencia, es decir, el tráfico que

utilice un determinado nivel de precedencia siempre debe experimentar una menor

probabilidad de pérdida que el tráfico que utilice un nivel de prioridad inferior de

precedencia de descarte.

WRED puede cumplir estos requisitos de tolerancia a las cargas cuando está configurada para ofrecer una diferenciación relativa. Una diferenciación relativa significa, por ejemplo, que un flujo TCP tiene un rendimiento dos veces mayor que otro flujo TCP, de menor prioridad, con el mismo RTT. Es decir, se establecen garantías solamente para un flujo con respecto a otro. Por otro lado, una diferenciación absoluta ofrece límites cuantificables con respecto al rendimiento, la pérdida y/o la fluctuación de retardo. Este tipo de diferenciación puede proporcionar a un flujo TCP un rendimiento absoluto cuantificado independiente del rendimiento que experimenten otros flujos TCP.

Puede suponerse que los servicios absolutos diferenciables son más deseables para muchos usuarios que los servicios relativos ya que son más predecibles. Con un servicio absoluto se conoce de antemano la calidad de una determinada sesión de comunicaciones. Este conocimiento previo es valioso, por ejemplo, cuando se elige el nivel óptimo de codificación de redundancia. Con un servicio relativo, el nivel de codificación tiene que elegirse en función de mediciones heurísticas o en tiempo real.

Ni RIO ni WRED pueden cumplir con los requisitos de tolerancia a las cargas, enunciados anteriormente, proporcionando al mismo tiempo una diferenciación absoluta. Sin embargo, la presente invención proporciona un nuevo mecanismo de puesta en cola, WRED con umbrales (WRT). El beneficio de la presente invención, es decir, WRT, es que, sin reconfiguración, proporciona una diferenciación absoluta, si el tráfico priorizado está controlado apropiadamente, y una diferenciación relativa en otros casos. Por lo tanto, WRT puede considerarse como tolerante a las cargas según la definición indicada anteriormente.

La tolerancia a cargas de WRT puede examinarse mediante simulaciones. Las simulaciones se centran en el comportamiento cualitativo de WRT bajo diferentes grados de sobrecarga, en lugar de en su comportamiento cuantitativo a una carga específica. Las simulaciones que comparan WRT con RIO y WRED muestran que WRT ofrece la misma diferenciación que estos mecanismos. Por lo tanto, es probable que otros estudios de simulación de RIO y WRED, que proporcionen resultados cuantitativos, puedan aplicarse a WRT.

Para generar servicios de extremo a extremo, la tolerancia a las cargas es ventajosa por varios motivos. En primer lugar, el control del tráfico no necesita ser muy preciso y/o en una red puede permitirse una mayor parte de tráfico priorizado. Además, los fallos en el control de este tráfico priorizado no pueden provocar inanición.

Un objeto de la presente invención es proporcionar un mecanismo de puesta en cola que cree múltiples niveles de precedencia de descarte que puedan impedir la inanición de tráfico de baja prioridad.

Un objeto adicional de la presente invención...

1. Un procedimiento de gestión de cola activa para controlar tráfico priorizado en un sistema de transmisión de paquetes, adaptado para proporcionar diferenciación entre el tráfico que se origina en aplicaciones de velocidad adaptable sensibles a la pérdida de paquetes, en donde al tráfico se le asigna un nivel de precedencia de descarte de entre al menos un primer y un segundo nivel de precedencia de descarte, concretamente dentro de perfil y fuera de perfil, caracterizado por:

- para un paquete etiquetado como dentro de perfil, calcular avg_ql_in, y, si avg_ql_in > th_in y min_th_in < avg_ql, calcular Pin y descartar, o retener, dicho paquete según el valor de Pin;

- para un paquete marcado como fuera de perfil, si min_th_out < avg_ql, calcular Pout y descartar, o retener, dicho paquete según el valor de Pout; -retener todos los paquetes con sus niveles de precedencia de descarte inicialmente asignados cuando la longitud media de cola sea inferior, o igual, a un umbral th_in; -asignar una probabilidad de descarte a cada paquete, determinada a partir de la longitud

media de cola; -retener todos los paquetes cuando avg_ql sea inferior a th_in; y -descartar paquetes según su probabilidad de descarte asignada;

y siendo max_p_out mayor que max_p_in, donde max_p_out es la probabilidad de descarte máxima de paquetes marcados como fuera de perfil y max_p_in es la probabilidad de descarte máxima para paquetes marcados como dentro de perfil.

2. Un procedimiento según la reivindicación 1, caracterizado por aplicar dicho procedimiento a una cola FIFO (primero en entrar primero en salir).

3. Un procedimiento según las reivindicaciones 1 ó 2, caracterizado por emplear más dos niveles de precedencia de descarte y por obtener una longitud media de cola para cada nivel de precedencia de descarte.

4. Un procedimiento según la reivindicación 1 ó 3, caracterizado por fijar max_th para cada nivel de precedencia de descarte al mismo valor.

5. Un procedimiento según la reivindicación 3 ó 4, caracterizado por tres niveles de precedencia de descarte y por calcular una longitud media de cola para cada nivel de precedencia de descarte en función de paquetes etiquetados con ese nivel y de paquetes etiquetados con un nivel superior de precedencia de descarte.

6. Un procedimiento según la reivindicación 5, caracterizado por asignar un único umbral a cada uno de los dos niveles de precedencia de mayor prioridad, utilizándose dicho único umbral para determinar cuándo un paquete va a etiquetarse con un nivel de precedencia inferior, y por proporcionar una diferenciación relativa entre dichos tres niveles cuando las longitudes medias de cola para los dos niveles de precedencia más altos superan ambos umbrales.

7. Un procedimiento según la reivindicación 6, caracterizado por proporcionar más de tres niveles de precedencia de descarte y por emplear un parámetro de longitud media de cola para cada nivel de precedencia de descarte con umbrales min_th#s y max_p#s asociados.

8. Un procedimiento según la reivindicación 7, caracterizado por ocho niveles de precedencia de descarte.

9. Un procedimiento según la reivindicación 7 u 8, caracterizado por un único umbral mínimo, th_in, para todos los niveles de precedencia de manera que ningún paquete se descarta si la longitud media de cola es inferior a th_in.

10. Un sistema de telecomunicaciones para la transmisión de datos por paquetes, caracterizado porque dicho sistema de telecomunicaciones emplea un procedimiento de gestión de cola activa como el reivindicado en cualquiera de las reivindicaciones 1 a 9.

11. Un sistema de telecomunicaciones según la reivindicación 10, caracterizado porque dicho sistema de telecomunicaciones es Internet.

12. Un encaminador para su uso en un sistema de telecomunicaciones como el reivindicado en la reivindicación 10 u 11, caracterizado porque dicho encaminador emplea un procedimiento de gestión de cola activa como el reivindicado en cualquiera de las reivindicaciones 1 a 9.