ES2349159T3 - Procedimiento, sistema y encaminador para proporcionar una gestión de cola activa en sistemas de transmisión de paquetes. - Google Patents

Procedimiento, sistema y encaminador para proporcionar una gestión de cola activa en sistemas de transmisión de paquetes. Download PDF

Info

Publication number
ES2349159T3
ES2349159T3 ES00919246T ES00919246T ES2349159T3 ES 2349159 T3 ES2349159 T3 ES 2349159T3 ES 00919246 T ES00919246 T ES 00919246T ES 00919246 T ES00919246 T ES 00919246T ES 2349159 T3 ES2349159 T3 ES 2349159T3
Authority
ES
Spain
Prior art keywords
discard
profile
max
packages
precedence
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Expired - Lifetime
Application number
ES00919246T
Other languages
English (en)
Inventor
Ulf Bodin
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Telia Co AB
Original Assignee
TeliaSonera AB
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by TeliaSonera AB filed Critical TeliaSonera AB
Application granted granted Critical
Publication of ES2349159T3 publication Critical patent/ES2349159T3/es
Anticipated expiration legal-status Critical
Expired - Lifetime legal-status Critical Current

Links

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04Q—SELECTING
    • H04Q11/00—Selecting arrangements for multiplex systems
    • H04Q11/04—Selecting arrangements for multiplex systems for time-division multiplexing
    • H04Q11/0421—Circuit arrangements therefor
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic control in data switching networks
    • H04L47/10—Flow control; Congestion control
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic control in data switching networks
    • H04L47/10—Flow control; Congestion control
    • H04L47/24—Traffic characterised by specific attributes, e.g. priority or QoS
    • H04L47/2408—Traffic characterised by specific attributes, e.g. priority or QoS for supporting different services, e.g. a differentiated services [DiffServ] type of service
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic control in data switching networks
    • H04L47/10—Flow control; Congestion control
    • H04L47/29—Flow control; Congestion control using a combination of thresholds
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic control in data switching networks
    • H04L47/10—Flow control; Congestion control
    • H04L47/30—Flow control; Congestion control in combination with information about buffer occupancy at either end or at transit nodes
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic control in data switching networks
    • H04L47/10—Flow control; Congestion control
    • H04L47/32—Flow control; Congestion control by discarding or delaying data units, e.g. packets or frames
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04Q—SELECTING
    • H04Q2213/00—Indexing scheme relating to selecting arrangements in general and for multiplex systems
    • H04Q2213/13103—Memory
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04Q—SELECTING
    • H04Q2213/00—Indexing scheme relating to selecting arrangements in general and for multiplex systems
    • H04Q2213/13164—Traffic (registration, measurement,...)
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04Q—SELECTING
    • H04Q2213/00—Indexing scheme relating to selecting arrangements in general and for multiplex systems
    • H04Q2213/13166—Fault prevention
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04Q—SELECTING
    • H04Q2213/00—Indexing scheme relating to selecting arrangements in general and for multiplex systems
    • H04Q2213/13174—Data transmission, file transfer
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04Q—SELECTING
    • H04Q2213/00—Indexing scheme relating to selecting arrangements in general and for multiplex systems
    • H04Q2213/13196—Connection circuit/link/trunk/junction, bridge, router, gateway
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04Q—SELECTING
    • H04Q2213/00—Indexing scheme relating to selecting arrangements in general and for multiplex systems
    • H04Q2213/13389—LAN, internet

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)
  • Telephonic Communication Services (AREA)
  • Mobile Radio Communication Systems (AREA)
  • Hardware Redundancy (AREA)

Abstract

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.

Description

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:
-
An Architecture for Differentiated Services, de Black D. et. al. (1998), IETF RFC 2475,
diciembre de 1998;
-
A Framework for Differentiated Services, de Bernet Y. et. al. (1998), IETF DRAFT, octubre
de 1998; y
-
Definition of the Differentiated Services Field (DS Field) en los encabezamientos IPv4 y
1Fv6, de Nichols K. et. al. (1998), IETF RFC 2474, diciembre de 1998;
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 es proporcionar un mecanismo de puesta en cola que cree múltiples niveles de precedencia de descarte que puedan 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.
Estos objetos se obtienen según la invención mediante un procedimiento según la reivindicación 1.
Por lo tanto, según la invención se proporciona un procedimiento de gestión de cola activa para controlar el 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 que responden 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.
El procedimiento incluye las etapas de:
-
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, max_th;
-
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.
Dicho procedimiento también incluye las etapas de: -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 descargar, 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.
Dicho procedimiento puede aplicarse a una cola FIFO.
Pueden emplearse más de dos niveles de precedencia de descarte y puede obtenerse una longitud media de cola para cada nivel de precedencia de descarte.
Dicho max_th para cada nivel de precedencia de descarte puede fijarse al mismo valor.
Pueden proporcionarse tres niveles de precedencia de descarte y puede calcularse una longitud media de cola para cada nivel de precedencia de descarte en función de paquetes etiquetados con ese nivel y paquetes etiquetados con un nivel superior de precedencia de descarte.
Puede asignarse un único umbral a cada uno de los dos niveles de precedencia de mayor prioridad, utilizándose dichos umbrales únicos para determinar cuándo un paquete va a etiquetarse con un nivel de precedencia inferior, y puede proporcionarse una diferenciación relativa entre dichos tres niveles cuando las longitudes medias de cola para los dos niveles de precedencia más altos superen ambos umbrales.
Pueden proporcionarse más de tres niveles de precedencia de descarte y puede emplearse un parámetro de longitud media de cola para cada nivel de precedencia de descarte con umbrales asociados min_th#s y max_p#s.
Pueden proporcionarse ocho niveles de precedencia de descarte.
Puede proporcionarse 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.
Según la presente invención, también se proporciona 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 expuesto en algún párrafo anterior.
Dicho sistema de telecomunicaciones puede ser de tipo Internet.
Según otro aspecto de la presente invención, se proporciona un encaminador para utilizarse con un sistema de telecomunicaciones como el expuesto en algún párrafo anterior, caracterizado porque dicho encaminador emplea un procedimiento de gestión de cola activa como el expuesto en algún párrafo anterior.
A continuación se describirán realizaciones de la invención, a modo de ejemplo, con referencia a los dibujos adjuntos, en los que:
La Figura 1 ilustra el mecanismo RED.
La Figura 2 ilustra el mecanismo WRED.
La Figura 3 ilustra el mecanismo RIO.
La Figura 4 ilustra WRED configurada para ofrecer una diferenciación absoluta.
La Figura 5 ilustra WRED configurada para ofrecer una diferenciación relativa.
La Figura 6 ilustra el mecanismo WRT de la presente invención.
La Figura 7 muestra un seudocódigo para WRT.
La Figura 8 ilustra una disposición de simulación.
La Figura 9 es una tabla que muestra los límites de asignación de ancho de banda con
ItRIO.
La Figura 10 muestra las características de RIO y de ItRIO.
La Figura 11 muestra las características de WRED y de WRT.
La Figura 12 muestra ItRIO bajo una sobrecarga severa.
La Figura 13 muestra ItRIO bajo una sobrecarga limitada.
La Figura 14 muestra RIO bajo una sobrecarga limitada.
La Figura 15 muestra la tolerancia a cargas de RIO, ItRIO y WRT.
A continuación se muestra un glosario de las abreviaturas utilizadas en esta memoria
descriptiva de patente para facilitar el entendimiento de la presente invención:
AF:
retransmisión asegurada
AQM:
gestión de cola activa
CS:
sector de clase
DiffServ:
servicios diferenciados
EF:
retransmisión acelerada
FIFO:
primero en entrar primero en salir
IETF:
grupo de trabajo de ingeniería de Internet
IP:
protocolo de Internet
ISP:
proveedor de servicios de Internet
ItRIO:
RIO tolerante a cargas
PHB:
comportamiento por salto
RED:
detección temprana aleatoria
RIO:
RED dentro y fuera
RTT:
tiempo de ida y vuelta
TCP:
protocolo de control de transmisión
TSW:
ventana deslizante de tiempo
UDP:
protocolo de datagramas de usuario
WRED:
RED ponderada
WRT:
WRED con umbrales
El objetivo principal de los mecanismos AQM es reducir la longitud media de cola en los encaminadores. Esto proporciona menos retardo, evita que los flujos queden bloqueados y, de manera óptima, reduce el número de paquetes descartados en encaminadores congestionados. Además, la AQM puede utilizarse para implementar la diferenciación de servicios entre diferentes flujos, por ejemplo, flujos TCP. Una ventaja con AQM es que puede utilizarse una sola cola FIFO para todo el tráfico que pertenezca a estos flujos. Esto es ventajoso si va a evitarse la reordenación de paquetes dentro de los flujos. Debe observarse que en las colas FIFO, los paquetes se retransmiten en el mismo orden en que llegan.
WRED y RIO son dos ejemplos de la utilización de AQM para conseguir la diferenciación de servicios. Tanto WRED como RIO son extensiones de RED, la cual se describe brevemente a continuación.
RED se propuso originalmente en 1993 por Floyd y Jacobson, véase: -Random Early Detection Gateways for Congestion Avoidance, de Floyd S. y Jacobson V. (1993), IEEE/ACM Transactions on Networking, agosto de 1993; y actualmente se recomienda su desarrollo en Internet, véase:
-Recommendations on Queue Management and Congestion Avoidance in the Internet, de
Braden B. et al (1998), IETF RFC 2309, abril de 1998.
RED permite a un encaminador descartar paquetes antes de que alguna cola se sature. Después se retiran los flujos responsables, en el momento oportuno, dando como resultado menores tamaños medios de cola. Esto es deseable por varios motivos. El retardo de puesta en cola se reducirá, lo que es bueno para aplicaciones tales como juegos interactivos. Otra propiedad ventajosa de RED es que los descartes de paquete no se producen en ráfagas. Esto reduce la probabilidad de que los flujos TCP pasen por una fase de inicio lenta debido a múltiples paquetes perdidos consecutivos. RED consigue esto descartando paquetes con una determinada probabilidad dependiendo de la longitud media de cola (avg_ql), véase la Figura 1.
Desafortunadamente, la configuración óptima para RED depende de patrones y características de tráfico. Por ejemplo, si hay un elevado número de flujos TCP presentes en una cola, RED necesita ser agresiva para conseguir su objetivo, es decir, max_p debe tener un valor elevado. En caso contrario, es probable que la cola crezca hacia su límite comportándose finalmente como una cola normal de descarte de últimos elementos. Por otro lado, si en una cola sólo hay un pequeño número de flujos, una RED demasiado agresiva puede reducir la utilización del enlace en cuestión. Una RED adaptativa, véase:
-Techniques for Eliminating Packet Loss in Congested TCP/IP Networks, de Feng W.,
Kandlur D., Saha D. y Shin K. (1997), Technical Report, Universidad de Michigan,
noviembre de 1997, URL: http://www.eecs.umich.edu/~wuchang/work/CSE-TR-349
97.ps.Z, es un intento de solucionar este problema de configuración. Sin embargo, este mecanismo no soluciona el problema si se origina una gran cantidad de tráfico a partir de aplicaciones no sensibles a la congestión de red, por ejemplo, aplicaciones en tiempo real que utilicen UDP o transferencias http de corta duración que utilicen TCP.
WRED, definida e implementada por Cisco, y RIO, propuesta y evaluada con simulaciones por Clark y Fang, son dos mecanismos AQM definidos para la diferenciación de servicios en redes IP. Ambos están basados en RED y ofrecen diferenciación gestionando la precedencia de descarte.
Con WRED pueden configurarse ocho niveles distintos de precedencia de descarte. Cada uno de estos niveles está configurado con un conjunto diferente de parámetros RED, véase la Figura 2. Por otro lado, RIO solo tiene dos conjuntos de parámetros RED. Por lo tanto, en su versión básica, pueden crearse dos niveles de preferencia de descarte, es decir, un nivel para paquetes etiquetados como dentro de perfil y otro nivel para paquetes etiquetados como fuera de perfil.
La diferencia principal entre RIO y WRED es que RIO utiliza dos longitudes medias de cola para calcular probabilidades de descarte, mientras que WRED solo utiliza una. WRED calcula su longitud media de cola (avg_ql) en función de todos los paquetes presentes en la cola. RIO también hace esto pero, además, calcula una longitud media de cola distinta para los paquetes de la cola etiquetada como dentro de perfil (av_ql_in), véase la Figura 3.
Hay una clara distinción entre diferenciación absoluta y diferenciación relativa entre niveles de precedencia de descarte. En este contexto, diferenciación absoluta implica que un determinado nivel de precedencia ofrece un límite cuantificable de pérdida. Es decir, el tráfico que utilice ese nivel particular tiene garantizado una tasa de pérdida máxima. Por tanto, un flujo TCP puede tener un rendimiento absoluto cuantificado independiente del rendimiento experimentado por otros flujos TCP.
Un límite máximo de pérdida solo puede ofrecerse a tráfico que esté controlado apropiadamente. Es decir, la tasa a la que llegan paquetes priorizados a la red debe limitarse para garantizar que la tasa de descarte nunca supere el límite. Por consiguiente, el control de tráfico es necesario para crear una diferenciación absoluta de servicios.
Una diferenciación relativa no ofrece ningún límite cuantificable de pérdida. En cambio, la tasa de descarte para cada nivel de precedencia se define con relación a algún otro nivel. Por ejemplo, un nivel de precedencia puede ofrecer la mitad de la tasa de descarte de otro nivel. A partir de estas tasas de descarte, definidas una en función de la otra, puede conseguirse una diferenciación de rendimiento entre los flujos TCP.
Cuando se soporta una diferenciación absoluta para el tráfico que utiliza un nivel particular de precedencia de descarte, el tráfico que utilice otros niveles de precedencia puede sufrir inanición. Este problema puede producirse si el tráfico que utiliza el nivel absoluto no está suficientemente controlado. Es decir, la tasa de llegada del tráfico al que se le va a proporcionar un límite absoluto de pérdida supera la tasa en la que la red puede soportar ese límite.
WRED y RIO pueden configurarse para soportar una diferenciación absoluta. Para crear tal diferenciación, estos ajustes requieren un control apropiado del tráfico que utilice solamente el nivel de precedencia que soporta diferenciación absoluta. Es decir, no es necesario controlar tráfico que utilice otros niveles de precedencia.
Con WRED puede soportarse diferenciación absoluta fijando max_th# a distintos valores. Además, max_p#s y min_th#s deben fijarse para garantizar que paquetes de prioridad superior experimenten siempre una menor probabilidad de pérdida que paquetes de prioridad inferior. Un ejemplo de esta configuración con dos niveles de precedencia de descarte se muestra en la Figura 4.
Con este tipo de configuración se proporciona un límite máximo de pérdida si av_ql nunca supera a max_th1, véase:
-Resource Reservation Protocol (RSVP) -Version 1 Functional Specification, de Braden R.
et. al. (1997), IETF RFC 2205, septiembre de 1998.
Sin embargo, para evitar la inanición del tráfico etiquetado con nivel de precedencia cero, av_ql no debe superar a max_th0. Por lo tanto, se necesita un control de tráfico adecuado para ofrecer una diferenciación absoluta de servicios con WRED.
Cuando se utiliza RIO para crear una diferenciación absoluta, max_th_in debe fijarse igual, o superior, a max_th_out. En caso contrario, el tráfico etiquetado como dentro de perfil puede experimentar una mayor tasa de descarte que el tráfico etiquetado como fuera de perfil. Esto quebrantaría la estricta jerarquía entre niveles de precedencia de descarte. Por tanto, una configuración de este tipo no es aconsejable.
La configuración de RIO mostrada en la Figura 3 puede utilizarse para ofrecer una diferenciación absoluta. Por ejemplo, se ofrece un límite máximo de pérdida si avg_ql_in nunca supera a max_th_in. Sin embargo, al igual que con WRED, puede producirse la inanición de tráfico de prioridad inferior, es decir, tráfico etiquetado como fuera de perfil, si no se controla apropiadamente tráfico de prioridad superior. Con RIO, este control debe garantizar que avg_ql nunca supere a max_th_out.
Ni RED ni RIO pueden cumplir con los requisitos de tolerancia a cargas cuando están configuradas para soportar diferenciación absoluta. El tráfico priorizado debe controlarse apropiadamente para evitar la inanición de tráfico de baja prioridad y para garantizar que se mantenga una jerarquía estricta entre niveles de precedencia de descarte. Sin embargo, WRED puede cumplir con estos requisitos cuando está configurada para ofrecer una diferenciación relativa entre niveles de precedencia.
Puede crearse una diferenciación relativa con WRED si todos los max_th#s se fijan al mismo valor. La diferenciación ofrecida depende de los ajustes de los min_th#s y los max_p#s. Estos parámetros deben fijarse para garantizar una jerarquía estricta entre los niveles de precedencia de descarte.
Con el ajuste de WRED, mostrado en la Figura 5, el tráfico que utilice el nivel de precedencia uno experimentará la mitad de la tasa de descarte del tráfico que utilice el nivel de precedencia cero. Sin embargo, esa relación solo puede mantenerse durante una sobrecarga moderada. Es decir, solo una pequeña parte del tráfico proviene de aplicaciones no sensibles a la congestión de red, por ejemplo aplicaciones en tiempo real que utilicen UDP o transferencias http de corta duración que utilicen TCP.
Cuando aumenta la parte de tráfico que proviene de aplicaciones no sensibles a la congestión de red, la sobrecarga se vuelve más severa. Si la sobrecarga se vuelve lo bastante severa, la cola se comportará finalmente como una cola de descarte de últimos elementos. La diferenciación relativa exacta proporcionada depende de las características de tráfico así como de la configuración de WRED.
RIO no puede configurarse para ofrecer una diferenciación relativa. Esto se debe a que RIO utiliza una variable aparte (av_ql_in) para calcular la probabilidad, Pin, de descartar un paquete marcado como dentro de perfil que llegue a la cola. Esta otra variable no contiene ninguna información relacionada con el número de paquetes, en la cola, marcados como fuera de perfil. Por lo tanto, el cálculo de Pin no puede no relacionado con la probabilidad Pout de descartar el paquete si se ha marcado como fuera de perfil.
La presente invención comprende un nuevo mecanismo de puesta en cola que, sin reconfiguración, proporciona una diferenciación absoluta si el tráfico priorizado se controla apropiadamente y una diferenciación relativa en otros casos. Este mecanismo, RED ponderada con umbrales (WRT), se implementa combinando RIO con WRED.
La presente invención adopta, de RIO, la idea de calcular dos longitudes medias de cola distintas. Sin embargo, en lugar de descartar paquetes marcados como dentro de perfil cuando avg_ql_in supera a max_th_in, véase la Figura 3, estos paquetes se tratan como si estuvieran marcados como fuera de perfil. Esto significa que max_th_in puede, y debe, fijarse a un valor inferior a max_th_out para evitar la inanición. Con este cambio, el mecanismo puede soportar una diferenciación absoluta siempre que av_ql_in no supere a max_th_in. Este mecanismo soporta una diferenciación igual a la soportada por RIO. Si avg_ql_in no supera a max_th_in, no habrá diferenciación. El mecanismo de puesta en cola se comportará entonces como RED. Por motivos de comodidad, este mecanismo se denominará como RIO tolerante a cargas (ItRIO).
El número de parámetros presentes en ItRIO puede reducirse utilizando un umbral en lugar de un conjunto de parámetros RED, concretamente max_th_in, min_th_in y max_p_in, para decidir cuándo los paquetes dentro de perfil van a tratarse como si estuvieran etiquetados como fuera de perfil. No se espera que esta simplificación tenga un efecto notable en el comportamiento de ltRIO. Esto se debe a que la señalización de congestión temprana aleatoria se llevará a cabo en función de los parámetros RED asociados con av_ql para paquetes etiquetados como dentro de perfil y fuera de perfil. Con RIO, esta señalización está basada en parámetros RED asociados con av_ql para paquetes etiquetados como fuera de perfil y en parámetros Red asociados con av_ql_in para paquetes etiquetados como dentro de perfil.
Para conseguir una diferenciación relativa cuando avg_ql_in supere a max_th_in se necesita un mecanismo para aplicar diferentes probabilidades de descarte a cada nivel de precedencia. Tal y como se ha tratado anteriormente, WRED proporciona esto cuando todos los max_th#s están fijados al mismo valor. Por lo tanto, combinando ltRIO con WRED se obtiene esta propiedad en el mecanismo de puesta en cola de la presente invención. Para el mecanismo de puesta en cola de la presente invención, no se permite que los max_th#s se fijen de manera independiente entre sí. Esto se debe a que tal fijación puede provocar la inanición del tráfico que utilice niveles de precedencia de baja prioridad.
El esquema combinado, WRT, puede utilizarse para crear una diferenciación relativa entre ocho niveles de precedencia cuando av_ql_in supera a th_in. Sin embargo, para los fines de esta descripción, sólo se utilizan dos de estos niveles que, por simplicidad, se denominan como el nivel dentro y el nivel fuera, respectivamente. WRT se muestra en la Figura 6.
La Figura 7 muestra cómo puede implementarse WRT con dos niveles de precedencia de descarte. La implementación tiene básicamente la misma complejidad que una implementación de RIO.
Para el grupo PHB AF se especifican tres niveles de presencia de descarte. Para crear estos tres niveles, WRT debe extenderse con soporte para un nivel adicional de precedencia de descarte. Esto implica que WRT debe extenderse con un umbral más asociado con una longitud media de cola adicional. Por lo tanto, para cada uno de los tres niveles de precedencia de descarte se calcula una longitud media de cola distinta en función de los paquetes etiquetados con ese nivel y del resto de paquetes etiquetados con cualquier nivel de prioridad superior.
Un único umbral se asigna para cada uno de los dos niveles de precedencia de mayor prioridad. Estos umbrales se utilizan para decidir cuándo los paquetes deben tratarse como si estuvieran marcados con un nivel de precedencia de prioridad inferior. El umbral para el nivel más alto debe fijarse a un valor inferior al del umbral para el segundo nivel más alto (el orden en que se fijan los umbrales define el orden de prioridad entre los niveles de precedencia).
Cuando las longitudes medias de cola para los dos niveles de mayor prioridad superan ambos umbrales, se proporciona una diferenciación relativa entre los tres niveles de precedencia de descarte. La diferenciación relativa depende de cómo estén configurados el min_th# y el max_p# para cada uno de estos niveles y de la carga actual de tráfico irresponsable.
Siempre que sea necesario, WRT puede extenderse para soportar más niveles de precedencia de descarte añadiendo variables adicionales de longitud media de cola con umbrales asociados, min_th#s y max_p#s.
La tolerancia a cargas de ItRIO y de WRT puede evaluarse utilizando simulaciones. Las simulaciones pueden llevarse a cabo con un simulador de red (ns), véase:
-UCB/LBNL/VINT Network Simulator -ns (version 2) (1998), URL: http://www-
mash.CS.Barkeley.EDU/ns/.
Esto permite mostrar que ltRIO puede ofrecer la misma diferenciación que la ofrecida por RIO y que WRT puede ofrecer la misma diferenciación que WRED.
Las simulaciones presentadas posteriormente permiten examinar el comportamiento cualitativo de WRT bajo diferentes grados de sobrecarga. Además, comparando WRT con RIO y WRED, puede demostrarse que WRT puede ofrecer la misma diferenciación que estos mecanismos.
Para llevar a cabo la evaluación, se utiliza una configuración de simulación sencilla. Se utiliza una topología de diez ordenadores centrales (S0,…, S9) conectados a sus respectivos destinos (R0,…, R9) a través de un enlace común. Este enlace, P1-P2, es un cuello de botella de 30 Mbps con un retardo de 20 ms; véase la Figura 8.
Los mecanismos AQM evaluados se aplican a la cola acoplada al enlace de cuello de botella. Cada ordenador central presenta diez conexiones Reno TCP con sus respectivos destinos. El rendimiento de cada uno de estos flujos TCP se mide durante 16 segundos simulados. Sin embargo, cada simulación pasa por una fase de inicio de tres a cuatro segundos simulados antes de que estas mediciones se inicien. Esto es para dejar que la cola se estabilice antes de observar el comportamiento de los mecanismos AQM que van a evaluarse. Las conexiones TCP se inician de manera aleatoria en el primer segundo simulado. Todas estas conexiones tienen el mismo RTT (40 ms).
Un estimador de velocidad de ventana deslizante de tiempo (TSW) se utiliza para cada uno de los diez ordenadores centrales para etiquetar paquetes como dentro de perfil hasta una velocidad determinada. Por lo tanto, un perfil de servicio se aplica para las diez conexiones TCP de cada ordenador central. Hay dos enfoques diferentes para el etiquetado de paquetes, los cuales se basan en la velocidad estimada con la TSW. El primer enfoque es más general y puede aplicarse a tráfico TCP agregado así como a conexiones TCP individuales. El segundo enfoque solo debe aplicarse a conexiones individuales pero es más eficaz si el estimador está situado cerca del ordenador central de envío. Puesto que el estimador se aplica a un agregado de diez conexiones TCP, el primer enfoque es más apropiado para las simulaciones descritas en este documento.
Con el primer enfoque, el tamaño de ventana debe fijarse a un valor elevado, es decir, del orden de un diente de sierra de TCP comprendido entre el 66% y el 133% de la velocidad especificada en el perfil de servicio. Una ventana muy pequeña puede hacer que el rendimiento del agregado sea inferior al especificado en el perfil. Por otro lado, con una ventana demasiado grande, el tráfico marcado como dentro de perfil puede aumentar su número de ráfagas. Por lo tanto, el tamaño de la ventana puede afectar al rendimiento experimentado por los flujos TCP individuales y a la variación de velocidad de los paquetes marcados como dentro de perfil que lleguen a los encaminadores centrales. Desafortunadamente, esto implica que hay una dependencia circular entre la longitud de tiempo de un diente de sierra y el tamaño de la ventana. Además, la longitud de un diente de sierra variará ya que los paquetes pueden descartarse aleatoriamente en la red. Por lo tanto, resulta complicado elegir un tamaño de ventana apropiado para una determinada conexión TCP basándose solamente en los parámetros conocidos. Por lo tanto, puede ser necesario adaptar el tamaño de la ventana en función de la medición en tiempo real de cada flujo TCP individual.
Para todas las simulaciones, el tamaño de ventana está fijado a 300 ms. Este valor se elige en función del siguiente argumento. Supóngase que la velocidad objetivo de una determinada conexión TCP está fijada a 500 kbps. En las simulaciones, el RTT es de 80 ms, incluyendo el retardo medio de puesta en cola, y el tamaño medio de paquete está fijado a 8000 bits. Entonces, esta conexión TCP tendrá cinco paquetes en curso, de media, y una ventana de congestión del tamaño de cinco paquetes de datos, de media. De manera óptima, el número de paquetes en curso y el tamaño de la ventana de congestión variarán entonces entre 1,33*5 y 0,66*5. La variación es por tanto de 0,67*5 = 3,35 paquetes. Puesto que TCP aumenta su ventana de congestión con un segmento de datos, equivalente a la carga útil de un paquete, en su mayor parte para cada RTT, la longitud de tiempo de un diente de sierra de TCP es de 3,35*0,08 = 0,268s.
Para llevar a cabo una evaluación de las propiedades de ItRIO y de WRT en comparación con RIO y WRED, se observa el rendimiento medio experimentado por las fuentes TCP que envían todos sus paquetes aguas abajo marcados como dentro de perfil, es decir, estas fuentes tiene perfiles de velocidad ilimitada. Esto se compara con el rendimiento medio experimentado por otras fuentes TCP que envían todos sus paquetes marcados como fuera de perfil, es decir, fuentes con perfiles de velocidad cero. El número de fuentes TCP con perfiles de velocidad ilimitada varía entre el 10% y el 90% en saltos de 10. Los resultados están representados en gráficas con el rendimiento medio como el eje y, y con el porcentaje de fuentes con perfil de velocidad ilimitada con el eje x. La Figura 11 muestra los resultados para RIO e ItRIO.
En esta simulación, RIO está configurada con max_th_in y min_th_in fijados a 100 paquetes, max_th_out a 200 paquetes y min_th_out a 100 paquetes. Por lo tanto, el valor de max_p_in no es relevante (ya que max_th_in y min_th_in son iguales). El parámetro max_p_out está fijado al 5%. ItRIO tiene la misma configuración, es decir, los parámetros presentes en estos dos mecanismos están fijados a los mismos valores. El parámetro th_in en ItRIO está fijado a 100 paquetes.
En la Figura 10 puede observarse que ItRIO ofrece la misma diferenciación que RIO cuando el número de flujos con perfiles de velocidad ilimitada es inferior al 57%. Por encima de esa carga, ItRIO se comporta como RED mientras que RIO ya no mantiene el orden estricto de prioridad entre los niveles de precedencia dentro y fuera. Por lo tanto, ItRIO puede soportar diferenciación absoluta sin el riesgo de proporcionar una calidad de servicio inferior al tráfico marcado como dentro de perfil que la que se proporciona a un tráfico con una prioridad inferior.
La Figura 11 muestra los resultados para WRED y WRT. En esta simulación, WRED está configurada con max_th0 y max_th1 fijados a 200 paquetes, min_th0 y min_th1 a 100 paquetes, max_p0 al 5% y max_p1 al 2,5%. Los parámetros para los otros seis niveles de precedencia no son relevantes ya que solo se utilizan el nivel cero y el nivel uno (el nivel uno se aplica a tráfico marcado como dentro de perfil y el nivel cero a tráfico marcado como fuera de perfil). Los parámetros presentes en ambos mecanismos están fijados al mismo valor. El parámetro max_th en WRT está fijado a 100 paquetes.
En la Figura 11 puede observarse que WRT ofrece una diferenciación relativa cuando el número de flujos con perfiles de velocidad ilimitada supera el 50%. Esta diferenciación es la misma que la ofrecida con WRED. Cuando el número de flujos con perfiles de velocidad ilimitada es inferior al 50%, WRT ofrece la misma diferenciación que RIO y que ItRIO.
Por lo tanto, con esta configuración particular, WRT se comporta como RIO y como ItRIO si el número de flujos con perfiles de velocidad ilimitada es inferior al 50% y, en caso contrario, como WRED. Esto significa que WRT mantiene la estricta jerarquía entre niveles de precedencia de descarte independientes de la carga. En función de estas observaciones puede concluirse que WRT puede utilizarse para crear una diferenciación absoluta, si el tráfico priorizado está controlado apropiadamente, y una diferenciación relativa en caso contrario.
Permitir que las fuentes tengan perfiles de velocidad ilimitada representa una situación extrema de sobrecarga ya que el único control de admisión presente está basado en el número de flujos. Esto puede considerarse como el peor caso de escenario cuando el control del tráfico agregado marcado como dentro de perfil ha fallado completamente. Las simulaciones con este tipo de sobrecarga proporcionan una indicación del grado de sensibilidad de la diferenciación con respecto a diferentes números de fuentes TCP que utilizan perfiles de velocidad ilimitada.
Para investigar la sensibilidad de la diferenciación, se aplica un perfil común de 5 Mbps al 10% de todos los flujos TCP, es decir, todos los flujos del ordenador central S9. Las fuentes con perfiles de velocidad ilimitada varían entre el 0% y el 80%. Por tanto, este gráfico está comprendido entre el 0% y el 90% de los flujos con perfiles de velocidad distinta de cero, en lugar de entre el 10% y el 90% como en los gráficos anteriores. Esto es para mostrar el rendimiento que tendrían los flujos de S9 si no hubiera sobrecarga, es decir, no hay ninguna fuente TCP con perfiles de velocidad ilimitada. ItRIO se utiliza con la misma configuración que en la simulación presentada en la Figura 10.
La Figura 12 muestra cómo el rendimiento medio experimentado por las diez fuentes TCP controladas se degrada con un número creciente de flujos que utilizan perfiles de velocidad ilimitada. Las fuentes TCP controladas son aquellas con un perfil de velocidad común de 5 Mbps. Puede observarse que algunas fuentes TCP no controladas no provocan ninguna degradación severa en el rendimiento experimentado por las fuentes TCP que comparten el perfil de 5 Mbps. Sin embargo, esto supone que los flujos con perfiles de velocidad ilimitada son sensibles a la señalización de congestión de red, es decir, a los descartes de paquete. Las aplicaciones irresponsables hacen que esta degradación sea mucho más drástica.
Tal y como se ha mencionado anteriormente, ItRIO y WRT ofrecen la misma diferenciación que RIO si avg_ql_in nunca supera a th_in. La cuestión es por tanto a qué carga sucederá esto para una distribución de tráfico específica y una configuración de estos mecanismos. Esta cuestión puede estudiarse llevando a cabo un conjunto de simulaciones iterativas. A través de estas simulaciones puede determinarse la cantidad máxima de ancho de banda que puede asignarse sin provocar que av_ql_in supere a th_in.
Además de variar la velocidad objetivo de la velocidad TSW, se utiliza la misma configuración que en la simulación de ItRIO mostrada en la Figura 10. La tabla expuesta en la Figura 9 presenta las velocidades máximas para dos ajustes diferentes de th_in, es decir 1/2 y 3/4 de max_th (el parámetro max_th está fijado a 200 paquetes). Para cada uno de estos ajustes se simulan tres escenarios, presentando el 30%, el 40% y el 50% de todos los flujos perfiles de velocidad distinta de cero.
La tabla expuesta en la Figura 9 muestra cómo el límite de asignación de ancho de banda depende del ajuste de th_in con respecto a max_th. Para estas simulaciones, fijar th_in a 1/2 y a 3/4 de max_th_out da como resultado un límite de asignación de ancho de banda próximo a 1/2 y 3/4 de la velocidad de enlace, respectivamente. Sin embargo, no puede esperarse que esta relación soporte cualquier configuración de ItRIO y cualquier posible carga de tráfico. Esto se debe a que el límite de asignación de ancho de banda depende de la variación de av_ql_in. Cuanto mayor sea esta variación, menor ancho de banda podrá asignarse sin el riesgo de que avg_ql_in supere a th_in. Consideraciones tales como el tamaño de ventana del estimador de velocidad TSW y la configuración del estimador de longitud media de cola del mecanismo de puesta en cola (RIO, ltRIO o WRT), influyen en la variación de av_ql_in. Por lo tanto, el límite exacto solo puede obtenerse con mediciones en tiempo real. Sin embargo, puede realizarse una estimación aproximada del límite de asignación de ancho de banda para un enlace determinado teniendo en cuenta solamente la configuración de ItRIO.
La diferenciación ofrecida cuando la cantidad de ancho de banda asignado varía, en lugar del número de fuentes TCP que utilizan perfiles de velocidad ilimitada, puede estudiarse examinando el rendimiento medio experimentado por 10 fuentes TCP que compartan un perfil de velocidad de 5 Mbps. La cantidad total de ancho de banda asignado varía entre 5 Mbps y 30 Mbps. Además, el número total de fuentes TCP que utilizan un perfil de velocidad distinta de cero varía entre el 30%, el 50% y el 70%. ItRIO está configurada de la misma manera que en la simulación presentada en la Figura 10.
En la Figura 13 puede observarse que las diez fuentes TCP que utilizan el perfil de velocidad común de cinco Mbps consiguen un rendimiento mayor a 500 Kbps, de media, si la cantidad total de ancho de bando asignado es inferior a 15 Mbps, es decir, 1/2 de la velocidad del enlace. Cuando se asigna más ancho de banda, la diferenciación depende del número de fuentes TCP que tengan perfiles de velocidad distinta de cero. Con esta configuración, ItRIO mantiene la estricta jerarquía entre los niveles de precedencia dentro y fuera si este número es inferior al 50%. Si más del 50% de las fuentes TCP tienen perfiles de velocidad distinta de cero, ItRIO se comporta, de la manera esperada, como RED. Para la comparación, RIO se simula con las mismas cargas, véase la Figura 14. RIO está configurada de la misma manera que la simulación presentada en la Figura 10.
Comparando las Figuras 13 y 14 puede observarse que RIO ofrece una diferenciación similar a ItRIO si la cantidad total de ancho de banda asignado es inferior a 15 Mbps. Además, estos dos mecanismos ofrecen una diferenciación similar si el número de fuentes TCP que tienen perfiles de velocidad distinta de cero es del 50% o menos. Sin embargo, cuando el número de fuentes TCP con perfiles de velocidad distinta de cero es del 70% y se utiliza RIO, las fuentes TCP con perfiles de velocidad cero experimentan un mayor rendimiento, de media, que las diez conexiones que comparten un perfil de velocidad de 5 Mbps. Este comportamiento también puede observarse en la Figura 10.
Para estudiar la diferencia entre RIO, ItRIO y WRT cuando el número de conexiones TCP que tienen perfiles de velocidad distinta de cero supera el 50%, WRT se simula con el 70% de las conexiones que utilizan perfiles de velocidad distinta de cero. Los resultados de esta simulación se muestran en la Figura 15.
Tal y como se espera a partir de las Figuras 10 y 11, solamente WRT mantiene la estricta jerarquía entre los niveles de precedencia de descarte. RIO falla completamente a la hora de mantener esta jerarquía e ItRIO se comporta como RED cuando el ancho de banda asignado supera los 20 Mbps. Por lo tanto, WRT es el único mecanismo de cola, de estos tres, que puede cumplir con los requisitos de tolerancia a las cargas.
Las simulaciones, descritas anteriormente, muestran que WRT, sin reconfiguración, proporciona una diferenciación absoluta, si el tráfico priorizado está controlado apropiadamente, y una diferenciación relativa en caso contrario. Ni RIO ni WRED pueden proporcionar esto con una sola configuración. Se observa que la diferenciación absoluta que ofrece la WRT es la misma que para RIO cuando la cantidad de tráfico priorizado se controla por debajo de un límite determinado y se observa que la diferenciación relativa es la misma que para WRED. El límite de asignación de ancho de banda cuando la diferenciación pasa de ser absoluta a relativa puede estimarse de manera aproximada en función de la configuración de WRT. Sin embargo, el ancho de banda real que puede asignarse será inferior que el estimado si avg_ql_in presenta una variación no despreciable.
Debe observarse que estos resultados suponen que en la cola gestionada por WRT solo hay tráfico TCP de larga duración. Un tráfico UDP voraz y/o un tráfico TCP de corta duración pueden afectar al comportamiento de WRT. Puede esperarse que cualquier efecto negativo de tales tráficos tenga un efecto similar en RIO y en WRED.
Durante la generación de la diferenciación de extremo a extremo absoluta cuantificable de servicios basados en niveles de precedencia de descarte, el control de tráfico debe ser preciso para garantizar que esta diferenciación se proporcione en todo momento. Además, puede ser necesario mantener la parte del tráfico que utiliza un pequeño servicio absoluto para ofrecer tal garantía. Claramente, si solo puede proporcionarse un servicio como éste a un tráfico muy pequeño, el beneficio global de los servicios absolutos es limitado.
5
10
15
20
25
30
35
18
Sin embargo, la tolerancia a cargas de WRT hace que los servicios absolutos basados en precedencias de descarte sean más robustos. La inanición no puede producirse a cualquier carga. Por lo tanto, la red es más robusta contra los fallos en el control de tráfico. Debido a la robustez de WRT, es probable que el tiempo de implantación de los servicios absolutos basados en precedencias de descarte sea más corto. Además, en la red puede permitirse más tráfico que utilice tales servicios absolutos sin riesgo de inanición.
Otro efecto positivo de la tolerancia a cargas de WRT es que no es necesario que el control de tráfico sea tan preciso como en otros mecanismos AQM, por ejemplo WRED o RIO. Un mecanismo de control menos preciso, quizá basado en mediciones, puede garantizar que se ofrezca una diferenciación absoluta gran parte del tiempo. Si este control falla se garantiza, como mínimo, una diferenciación relativa si se utiliza WRT.
RIO y WRED soportan una diferenciación absoluta cuantificable entre niveles de precedencia de descarte cuando el tráfico priorizado está controlado apropiadamente. Sin embargo, si este control falla, estos mecanismos pueden provocar la inanición de tráfico de baja prioridad. Tales fallos se producen debido a imprecisiones en el control de admisión y a cambios de topología.
La inanición puede evitarse con WRED si está configurada para ofrecer una diferenciación relativa. Sin embargo, la diferenciación absoluta de servicios es todavía necesaria.
Para ofrecer una diferenciación absoluta entre niveles de precedencia sin el riesgo de inanición, la presente invención proporciona un nuevo mecanismo de cola, WRT. Las simulaciones han mostrado que WRT, sin reconfiguración, proporciona una diferenciación absoluta, si el tráfico priorizado está controlado apropiadamente, y una diferenciación relativa en caso contrario.
Se observa que la diferenciación absoluta que la WRT ofrece es la misma que para RIO cuando la cantidad de tráfico priorizado se controla por debajo de un determinado límite y se observa que la diferenciación relativa es la misma que para WRED. Por lo tanto, WRT puede proporcionar cualquier diferenciación que RIO y WRED puedan ofrecer. Además, los servicios de extremo a extremo que prometen una diferenciación absoluta la mayor parte del tiempo y, como mínimo, una diferenciación relativa, pueden implementarse con WRT. RIO y WRED no bastan para crear tales servicios.

Claims (12)

  1. REIVINDICACIONES
    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:
    -
    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.
  2. 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. 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. 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. 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. 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. 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. 8.-Un procedimiento según la reivindicación 7, caracterizado por ocho niveles de precedencia de descarte.
  9. 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. 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. 11.-Un sistema de telecomunicaciones según la reivindicación 10, caracterizado porque dicho sistema de telecomunicaciones es Internet.
  12. 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.
ES00919246T 1999-04-07 2000-04-07 Procedimiento, sistema y encaminador para proporcionar una gestión de cola activa en sistemas de transmisión de paquetes. Expired - Lifetime ES2349159T3 (es)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
SE9901236A SE514313C2 (sv) 1999-04-07 1999-04-07 Förbättringar av, eller med avseende på, datapaketförmedling
SE9901236 1999-04-07

Publications (1)

Publication Number Publication Date
ES2349159T3 true ES2349159T3 (es) 2010-12-28

Family

ID=20415132

Family Applications (1)

Application Number Title Priority Date Filing Date
ES00919246T Expired - Lifetime ES2349159T3 (es) 1999-04-07 2000-04-07 Procedimiento, sistema y encaminador para proporcionar una gestión de cola activa en sistemas de transmisión de paquetes.

Country Status (10)

Country Link
US (1) US7139281B1 (es)
EP (1) EP1171977B1 (es)
AT (1) ATE477645T1 (es)
DE (1) DE60044805D1 (es)
DK (1) DK1171977T3 (es)
EE (1) EE04980B1 (es)
ES (1) ES2349159T3 (es)
NO (1) NO332566B1 (es)
SE (1) SE514313C2 (es)
WO (1) WO2000060817A1 (es)

Families Citing this family (34)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7688727B1 (en) * 2000-04-17 2010-03-30 Juniper Networks, Inc. Filtering and route lookup in a switching device
US7215637B1 (en) 2000-04-17 2007-05-08 Juniper Networks, Inc. Systems and methods for processing packets
EP1220493A1 (en) 2000-12-28 2002-07-03 Alcatel Marker device and related method
US6831891B2 (en) * 2001-03-06 2004-12-14 Pluris, Inc. System for fabric packet control
EP1249972A1 (en) * 2001-04-09 2002-10-16 Telefonaktiebolaget L M Ericsson (Publ) Method of controlling a queue buffer
GB2372172B (en) 2001-05-31 2002-12-24 Ericsson Telefon Ab L M Congestion handling in a packet data network
US7349336B2 (en) * 2002-06-04 2008-03-25 Lucent Technologies Inc. Random early drop with per hop behavior biasing
AU2002314419A1 (en) * 2002-06-27 2004-01-19 Nokia Corporation Self-adaptive scheduling method and network element
GB2395856A (en) * 2002-11-26 2004-06-02 King S College London Method for reducing packet congestion at a network node
JP4080911B2 (ja) * 2003-02-21 2008-04-23 株式会社日立製作所 帯域監視装置
US7372814B1 (en) * 2003-02-27 2008-05-13 Alcatel-Lucent Network system with color-aware upstream switch transmission rate control in response to downstream switch traffic buffering
ES2229917B1 (es) * 2003-07-15 2006-07-01 Diseño De Sistemas En Silicio, S.A. Procedimiento de gestion dinamica de recursos de sitemas de telecomunicaciones en funcion de la calidad de servicio y del tipo de servicio.
US7391722B2 (en) 2004-02-17 2008-06-24 Alcatel Lucent Method and system for determining link congestion
US7567508B2 (en) * 2005-05-23 2009-07-28 Cisco Technology, Inc. Method and system for providing delay bound and priortized packet dropping
US8649277B2 (en) * 2006-06-29 2014-02-11 Nec Corporation Communication apparatus and method
JP4878391B2 (ja) * 2006-12-18 2012-02-15 テレフオンアクチーボラゲット エル エム エリクソン（パブル） 適応的なキュー待ち時間を伴うスケジューリング及びキューマネージメント
US7697532B2 (en) * 2007-02-08 2010-04-13 Corrigent Systems Ltd. Frame concatenation with drop precedence assignment
KR101075724B1 (ko) * 2007-07-06 2011-10-21 삼성전자주식회사 통신 시스템에서 패킷 전송 속도 제한 장치 및 방법
WO2009016692A1 (ja) * 2007-07-27 2009-02-05 Fujitsu Limited パケット処理装置
US7756044B2 (en) * 2008-07-31 2010-07-13 Microsoft Corporation Inverse multiplexing heterogeneous wireless links for high-performance vehicular connectivity
US20100027563A1 (en) * 2008-07-31 2010-02-04 Microsoft Corporation Evolution codes (opportunistic erasure coding) platform
US20100064072A1 (en) * 2008-09-09 2010-03-11 Emulex Design & Manufacturing Corporation Dynamically Adjustable Arbitration Scheme
GB2478277B (en) * 2010-02-25 2012-07-25 Skype Ltd Controlling packet transmission
CN102469510A (zh) * 2010-11-11 2012-05-23 中兴通讯股份有限公司 用于3g网络视频传输的内容感知主动队列管理方法
US8593972B2 (en) * 2011-09-29 2013-11-26 Cisco Technology, Inc. Method to verify a drop probability curve
US8824328B2 (en) * 2012-02-29 2014-09-02 Infosys Limited Systems and methods for optimizing the performance of an application communicating over a network
EP2823610B1 (en) 2012-03-09 2019-01-02 British Telecommunications public limited company Signalling congestion
US9473974B2 (en) 2012-05-30 2016-10-18 The University Of Hong Kong Enhancing AQM to combat wireless losses
US9680760B2 (en) * 2013-07-16 2017-06-13 Cisco Technology, Inc. Adaptive marking for WRED with intra-flow packet priorities in network queues
US9948561B2 (en) * 2015-04-14 2018-04-17 Cisco Technology, Inc. Setting delay precedence on queues before a bottleneck link based on flow characteristics
CN105425590B (zh) * 2015-12-31 2018-01-09 河南科技大学 一种基于改进免疫算法的pid主动队列管理方法
CN109787922B (zh) * 2017-11-13 2020-08-21 中国移动通信集团公司 一种获取队列长度的方法、设备及计算机可读存储介质
CN114531399B (zh) * 2020-11-05 2023-09-19 中移(苏州)软件技术有限公司 一种内存阻塞平衡方法、装置、电子设备和存储介质
CN113590030B (zh) * 2021-06-30 2023-12-26 济南浪潮数据技术有限公司 一种队列调度方法、系统、设备以及介质

Family Cites Families (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
DE4323405A1 (de) 1993-07-13 1995-01-19 Sel Alcatel Ag Zugangskontrollverfahren für einen Pufferspeicher sowie Vorrichtung zum Zwischenspeichern von Datenpaketen und Vermittlungsstelle mit einer solchen Vorrichtung
FI951278A0 (fi) 1995-03-17 1995-03-17 Finland Telecom Oy Foerfarande och arrangemang foer att behaerska en buffert i ett ATM-naet
US6092115A (en) 1997-02-07 2000-07-18 Lucent Technologies Inc. Method for supporting per-connection queuing for feedback-controlled traffic
US6252848B1 (en) * 1999-03-22 2001-06-26 Pluris, Inc. System performance in a data network through queue management based on ingress rate monitoring

Also Published As

Publication number Publication date
DE60044805D1 (de) 2010-09-23
EP1171977A1 (en) 2002-01-16
EP1171977B1 (en) 2010-08-11
US7139281B1 (en) 2006-11-21
NO332566B1 (no) 2012-10-29
NO20014498D0 (no) 2001-09-17
WO2000060817A1 (en) 2000-10-12
NO20014498L (no) 2001-12-06
EE04980B1 (et) 2008-02-15
EE200100523A (et) 2002-12-16
ATE477645T1 (de) 2010-08-15
SE9901236D0 (sv) 1999-04-07
SE9901236L (sv) 2000-10-08
SE514313C2 (sv) 2001-02-12
DK1171977T3 (da) 2010-12-06

Similar Documents

Publication Publication Date Title
ES2349159T3 (es) Procedimiento, sistema y encaminador para proporcionar una gestión de cola activa en sistemas de transmisión de paquetes.
Nandy et al. Intelligent traffic conditioners for assured forwarding based differentiated services networks
US6839321B1 (en) Domain based congestion management
Mao et al. PQWRR scheduling algorithm in supporting of DiffServ
Raghuvanshi et al. On the effectiveness of CoDel for active queue management
de Rezende Assured service evaluation
Seddigh et al. Experimental study of assured services in a diffserv IP QoS network
US8264957B1 (en) Control of preemption-based beat-down effect
Bowen et al. Bandwidth allocation for non-responsive flows with active queue management
ES2341521B1 (es) Procedimiento de gestion de ancho de banda en redes de paquetes.
Herrerı́a-Alonso et al. Improving aggregate flow control in differentiated services networks
ES2969600T3 (es) Procedimiento de enrutamiento de un flujo elástico en una red de transporte
Li et al. Class-based fair intelligent admission control over an enhanced differentiated service network
Joo et al. Assuring drop probability for delay-insensitive traffic in a differentiated service network
Fgee et al. MRED: An Algorithm to Insure High QoS in IP Networks.
Kure et al. Architecture for TDM circuit emulation over IP in tactical networks
Phan et al. FICC-DiffServ: A new QoS architecture supporting resources discovery, admission and congestion controls
Habib et al. Unresponsive flow detection and control using the differentiated services framework
US20090141624A1 (en) Method and System for A Novel Flow Admission Control Framework
Kim A modified RIO for Improving Assured Service Performance
Culverhouse et al. Optimising Quality of Service through the controlled aggregation of traffic
Yan et al. A stateless active queue management scheme for approximating fair bandwidth allocation and stabilized buffer occupation
Bali Plánovač síťového provozu pro diferencované služby
Yi et al. Gateway algorithm for fair bandwidth sharing
Adegboyega An enhanced algorithm for fair traffic conditioning in IP differentiated services