Procedimiento y dispositivo de ordenación de paquetes para su enrutamiento en una red con determinación implícita de los paquetes que procesar con prioridad.

Procedimiento de ordenación de paquetes pertenecientes a distintos flujos (1),

una fila de espera no prioritaria denominada Queue_i y un contador de déficit denominado DC_i asociados a cada flujo i, así como una fila prioritaria denominada PQ, incluyendo este procedimiento, tras la recepción de un paquete:

* la determinación del número de flujo i al que pertenece el paquete;

* una etapa (E40, E54) de determinación de la prioridad de dicho paquete, denominado p, siendo un paquete prioritario por una parte:

- el primer paquete de un flujo no presente en una lista denominada ActiveList de flujos activos, insertándose el índice de este flujo al final de dicha ActiveList; y por otra parte

- los siguientes paquetes de este flujo recibidos durante un ciclo, mientras el número de bits denominado ByteCount_i de este flujo recibidos en dicho ciclo es inferior a una cuota denominada Q_i asociada al flujo para dicho ciclo; y

* si dicho paquete se determina no prioritario, una etapa (E58) de colocación en fila de dicho paquete en la fila de espera no prioritaria denominada Queue_i asociada al flujo de dicho p;

* si dicho paquete se determina prioritario, una etapa (E48, E56) de colocación en fila de dicho p al final de dicha fila PQ;

con dichas filas Queue_i respectivamente asociadas a los flujos de dicha lista ActiveList procesadas cíclicamente según su orden en dicha ActiveList, con la fila PQ procesada con prioridad respecto de cada una de las filas Queue_i en dicho ciclo;

consistiendo el procesamiento de dicha fila PQ en emitir (F24) todos los paquetes contenidos en dicha PQ y en disminuir (F26), para cada uno de dichos paquetes emitidos, dicho DC_i asociado al flujo i de dicho paquete del tamaño de dicho paquete;

consistiendo el procesamiento de una fila Queue_i en:

- aumentar (F50) dicho DC_i asociado a dicha fila Queue_i de dicha cuota; y

- emitir (F64) paquetes contenidos en dicha fila Queue_i, mientras dicho DC_i asociado a dicha fila Queue_i es estrictamente positivo (F60), emitiéndose un paquete si su tamaño es inferior a dicho DC_i (F62), disminuyéndose dicho DC_i (F66) del tamaño de dicho paquete emitido;

- retirar el índice de dicho flujo asociado a esta fila Queue_i de dicha lista ActiveList y reiniciar dicho DC_i si dicha fila Queue_i está vacía tras dicho procesamiento (F82); y

- desplazar el índice de dicho flujo al final de dicha lista ActiveList en el caso contrario.

Procedimiento y dispositivo de ordenación de paquetes para su enrutamiento en una red con determinación implícita de los paquetes que procesar con prioridad

Antecedentes de la invención

La invención se refiere al ámbito de la arquitectura de redes de telecomunicaciones.

La invención apunta más concretamente a un procedimiento, un dispositivo de ordenación y un enrutador de paquetes de datos de multiservicio para mejorar la calidad del servicio de enrutamiento de paquetes de datos de multiservicio incluidos en distintos flujos de esta red, de escasa complejidad.

Se aplica en particular a la red de Internet.

El concepto de "flujo" utilizado en este documento es por ejemplo el de la arquitectura "flow-aware" expuesta en el artículo de Bonald et al. "IP traffic and QoS control: the need for a flow-aware architecture", World Telecom Conference, París, 22.

Internet tiene vocación de multiservicio y está llamado a proporcionar el soporte para una gran gama de servicios y aplicaciones. Se distinguen dos grandes clases de tráfico en esta red, el tráfico en tiempo real (o tráfico "streaming") producido en general por las aplicaciones de audio o vídeo, y el tráfico de datos (o tráfico elástico) correspondiente a la transferencia de documentos digitales. El tráfico en tiempo real posee exigencias de calidad de servicio correspondientes a la necesidad de conservación de la señal - las variaciones de velocidad que caracterizan la señal producida por la fuente deben preservarse cuando la señal cruza la red. La calidad de servicio del tráfico de datos se mide por el tiempo de transferencia de los documentos. Este tiempo o, de manera equivalente, la velocidad media alcanzada durante la transferencia, depende de toda la cadena de comunicación, desde la fuente hasta el destino. Un objetivo de calidad de servicio para una red de Internet podría ser parecer transparente al tráfico de datos sin introduciruna reducción de velocidad adicional respecto de las limitaciones introducidas en otras partes (servidor, redes de acceso, equipo del usuario); en este sentido la red garantiza el mantenimiento de la velocidad de los flujos de datos.

La red de Internet pública ofrece un servicio de transporte a clientes usuarios en un contexto comercial. La cuestión de la tarificación es, por lo tanto, importante. La arquitectura de red debe permitir una rentabilidad respecto de la inversión para el operador con precios competitivos para los servicios de calidad solicitados por los usuarios.

Se conoce un procedimiento de ordenación de escasa complejidad (de orden (1), es decir independiente del número de flujos) denominado DRR (para "Déficit Round Robín"), y descrito por M. SHREEDHAR y G. VARGHESE: "Efficient fair queulng using Déficit round robin", IEEE/ACMT Transactions on Networking, Volumen 4, 3a publicación, Junio de 1996, páginas 375-385.

El procedimiento DRR es un procedimiento de ordenación basado en el procesamiento de los flujos de manera cíclica, según el principio "round robin". Este procedimiento asocia una fila de espera a cada flujo, con cada una de estas filas de espera tratada cíclicamente, autorizada a emitir, por ciclo, paquetes hasta alcanzar una cuota (cantidad de datos, por ejemplo medida en bits).

Este procedimiento DRR permite tener un grado de equidad razonable gracias al mantenimiento de un contador de déficit que permite compensar la posible diferencia de tamaño de los paquetes de los distintos flujos.

El artículo TSAO et al: "Pre-order Déficit Round Robin: a new scheduling algorithm for packet-switched network" de 3 de febrero de 21, publicado en el documento COMPUTER NETWORKS ELSEVIER SCIENCE PUBLISHERS B.V. AMSTERDAM, NL, vol. 35, n2 2-3, describe un procedimiento de ordenación de paquetes pertenecientes a distintos flujos, apuntando este procedimiento a la adaptación del algoritmo DRR para mejorar la equidad de reparto de un ancho de banda entre los distintos flujos.

Unas variantes del procedimiento DRR han permitido asociar un procesamiento prioritario a los paquetes de ciertos flujos.

Especialmente, el procedimiento DRR+, descrito en el artículo de SHREEDHAR y VARGHESE mencionado anteriormente, permite procesar con prioridad los flujos sensibles al plazo, en detrimento de los flujos "best effort". En este procedimiento, los flujos prioritarios deben cumplir un contrato, es decir, no emitir más de cierto volumen de datos durante un periodo de tiempo predeterminado.

El documento FR2854296 del solicitante propone un procedimiento de ordenación con diferenciación implícita de los paquetes que procesar con prioridad, que permite, en consecuencia, librarse ventajosamente de este tipo de contrato. Pero el procedimiento de ordenación descrito en este documento, del tipo "self-clock fair queuing" es del

orden (log n), siendo n el número de flujos que tomar en cuenta, lo que puede aparecer como una limitación para su aplicación en ciertos tipos de enrutadores.

La invención pretende resolver los inconvenientes anteriores.

Objeto y sumario de la invención

A tal efecto, y según un primer aspecto, la invención se refiere a un procedimiento y un dispositivo de ordenación conformes al objeto de las reivindicaciones.

Por lo tanto, la ordenación según la invención se distingue de las del estado de la técnica conocido hasta hoy, porque realiza una distinción de la prioridad de los flujos en función de sus características intrínsecas de velocidad, no en función de un contrato o de una asignación externa de un nivel de prioridad asociado a los paquetes o a los flujos, manteniendo al mismo tiempo una complejidad independiente del número de flujos.

El dispositivo y el procedimiento de ordenación ordenan los paquetes en una fila de espera, según un algoritmo de reparto equitativo con prioridad.

Una ordenación del tipo "reparto equitativo con prioridad" permite dar prioridad a los paquetes de flujos cuya velocidad es inferior a un umbral dinámico. Este umbral corresponde a la velocidad que alcanzaría un flujo que tuviese siempre paquetes que emitir.

Ventajosamente, este procedimiento y este dispositivo de ordenación se basan en el procedimiento de ordenación DRR mencionado anteriormente.

En un modo particular de realización, el procedimiento de ordenación según la invención incluye, además, una etapa de medición de un contador de congestión que memoriza el volumen de los paquetes emitidos a partir de la fila prioritaria, con este contador destinado a ser procesado para el cálculo de estimadores de congestión utilizados para un control de admisión.

Estos estimadores de congestión pueden servir especialmente para un control de admisión en el núcleo de la red.

La invención propone asimismo un procedimiento de control de admisión que utiliza un estimador (o parámetro) de congestión constituido por un valor de carga prioritaria, correspondiente a un volumen de los paquetes prioritarios, transmitido durante un intervalo de tiempo, dividido por la duración de este intervalo, obteniéndose este volumen mediante un procedimiento de ordenación como el mencionado anteriormente.

En un modo particular de realización, la ordenación según la invención está asociada a un control de admisión por flujo del tipo "fair queuing".

De este modo, y según un segundo aspecto, la invención se refiere asimismo a un enrutador de paquetes como el reivindicado.

En un modo particular de realización, el módulo de admisión está, además, adaptado para enrutar directamente los paquetes pertenecientes a flujos denominados protegidos, es decir los flujos para los que al menos un paquete ha sido recibido por dicho módulo de admisión desde un intervalo de tiempo predeterminado.

Dicho dispositivo o procedimiento puede funcionar, sin medios de control de admisión, especialmente en el marco de una red de acceso en la que el riesgo de congestión es más controlable que en el núcleo de la red.

En un modo particular de realización, las etapas del procedimiento de ordenación se ejecutan en un ordenador bajo el control de instrucciones de un programa informático. Por consiguiente, la invención se refiere asimismo a un programa de ordenador almacenado en un soporte de información, incluyendo este programa instrucciones que permiten la aplicación de un procedimiento de ordenación como el mencionado anteriormente, cuando este programa se carga y ejecuta en un sistema informático.

La invención se refiere asimismo a un soporte de información legible por un sistema informático, eventualmente amovible en todo o parte, especialmente CD-ROM o soporte magnético, como un disco duro o un disquete, o soporte transmisible, como una señal eléctrica... [Seguir leyendo]

1.- Procedimiento de ordenación de paquetes pertenecientes a distintos flujos (1), una fila de espera no prioritaria denominada QueueJ y un contador de déficit denominado DC_i asociados a cada flujo i, así como una fila prioritaria denominada PQ, incluyendo este procedimiento, tras la recepción de un paquete:

la determinación del número de flujo i al que pertenece el paquete;

una etapa (E4, E54) de determinación de la prioridad de dicho paquete, denominado p, siendo un paquete prioritario por una parte:

- el primer paquete de un flujo no presente en una lista denominada ActiveList de flujos activos, insertándose el índice de este flujo al final de dicha ActiveList; y por otra parte

- los siguientes paquetes de este flujo recibidos durante un ciclo, mientras el número de bits denominado ByteCountJ de este flujo recibidos en dicho ciclo es inferior a una cuota denominada Q_i asociada al flujo para dicho

ciclo; y

si dicho paquete se determina no prioritario, una etapa (E58) de colocación en fila de dicho paquete en la fila de espera no prioritaria denominada QueueJ asociada al flujo de dicho p;

si dicho paquete se determina prioritario, una etapa (E48, E56) de colocación en fila de dicho p al final de dicha fila

PQ;

con dichas filas QueueJ respectivamente asociadas a los flujos de dicha lista ActiveList procesadas cíclicamente según su orden en dicha ActiveList, con la fila PQ procesada con prioridad respecto de cada una de las filas

QueueJ en dicho ciclo;

consistiendo el procesamiento de dicha fila PQ en emitir (F24) todos los paquetes contenidos en dicha PQ y en disminuir (F26), para cada uno de dichos paquetes emitidos, dicho DCJ asociado al flujo i de dicho paquete del

tamaño de dicho paquete;

consistiendo el procesamiento de una fila QueueJ en:

- aumentar (F5) dicho DCJ asociado a dicha fila QueueJ de dicha cuota; y

- emitir (F64) paquetes contenidos en dicha fila QueueJ, mientras dicho DCJ asociado a dicha fila QueueJ es estrictamente positivo (F6), emitiéndose un paquete si su tamaño es inferior a dicho DCJ (F62), disminuyéndose dicho DCJ (F66) del tamaño de dicho paquete emitido;

- retirar el índice de dicho flujo asociado a esta fila QueueJ de dicha lista ActiveList y reiniciar dicho DCJ si dicha fila QueueJ está vacía tras dicho procesamiento (F82); y

- desplazar el índice de dicho flujo al final de dicha lista ActiveList en el caso contrario.

2.- Procedimiento de ordenación según la reivindicación 1, caracterizado porque incluye además, una etapa (F28, F42) de medición de un contador (PB) de congestión que memoriza el volumen de los paquetes emitidos a partir de dicha fila PQ, destinado a ser procesado para el cálculo de un estimador (CP) de congestión utilizado para un control de admisión.

3.- Procedimiento de control de admisión que utiliza un estimador de congestión constituido por:

- un valor (CP) de carga prioritaria, correspondiente a un volumen (PB) de paquetes prioritarios, transmitidos durante un intervalo de tiempo, dividido por la duración de este intervalo, obteniéndose dicho volumen (PB) mediante un procedimiento de ordenación según la reivindicación 2.

4.- Dispositivo de ordenación de paquetes p pertenecientes a distintos flujos, una fila de espera no prioritaria denominada QueueJ y un contador de déficit denominado DCJ asociados a cada flujo i, así como una fila prioritaria denominada PQ, incluyendo este dispositivo, al recibir un paquete:

medios para determinar el número de flujo i al que pertenece el paquete;

medios de determinación de la prioridad de dicho paquete, denominado p, siendo un paquete prioritario por una parte:

- el primer paquete de un flujo no presente en una lista denominada ActiveList de flujos activos, con el índice de este flujo insertado al final de dicha ActiveList; y por otra parte

- los siguientes paquetes de este flujo recibidos durante un ciclo mientras el número de bits denominado BytesCountJ de este flujo recibidos en dicho ciclo es inferior a una cuota denominada Qi asociada al flujo para dicho ciclo; y

si dicho paquete se determina no prioritario, medios de colocación en fila de dicho paquete en la fila denominada QueueJ asociada al flujo de dicho p; y

si dicho paquete se determina prioritario, medios de colocación en fila de dicho p al final de dicha fila PQ;

medios para tratar cíclicamente dichas filas QueueJ respectivamente asociadas a los flujos de dicha ActiveList según su orden en dicha ActiveList, siendo la fila PQ procesada con prioridad respecto de cada una de las filas QueueJ en dicho ciclo, incluyendo dichos medios de procesamiento:

- medios de emisión de todos los paquetes en dicha fila PQ, con dicho DCJ asociado al flujo i de cada uno de dichos paquetes emitidos disminuido del tamaño de dicho paquete;

- medios de emisión de los paquetes contenidos en dicha fila QueueJ, mientras dicho DCJ asociado a dicha fila QueueJ es estrictamente positivo, con dicho contador DCJ aumentado de la cuota QJ asociada a dicha fila Queue i, emitiéndose un paquete si su tamaño es inferior a dicho DCJ, disminuyéndose dicho contador de déficit del tamaño de dicho paquete emitido, siendo dichos medios:

- capaces de retirar el índice de dicho flujo asociado a esta fila Queue i de dicha ActiveList y de reiniciar dicho DCJ si dicha fila QueueJ está vacía tras dicho procesamiento; o

- medios para desplazar el índice de dicho flujo al final de dicha ActiveList en el caso contrario.

5.- Dispositivo de ordenación según la reivindicación 4, caracterizado porque incluye, además, medios de medición de un contador (PB) de congestión que memoriza el volumen de los paquetes emitidos a partir de dicha fila PQ, destinado a ser procesado para el cálculo de un estimador de congestión utilizado para un control de admisión.

6.- Enrutador de paquetes caracterizado porque incluye un dispositivo de ordenación (1) según la reivindicación 5, y un módulo (24) de control de admisión que utiliza un estimador de congestión constituido por un valor (CP) de carga prioritaria, correspondiente a un volumen (PB) de paquetes prioritarios, transmitidos durante un intervalo de tiempo, dividido por la duración de este intervalo, obteniéndose este volumen (PB) con la ayuda de los medios de medición de un contador de congestión del dispositivo de ordenación.

7.- Enrutador según la reivindicación 6, caracterizado porque dicho módulo de admisión está, además, adaptado para enrutar directamente los paquetes pertenecientes a flujos denominados protegidos, es decir los flujos para los que se ha recibido al menos un paquete por parte de dicho módulo de admisión desde un intervalo de tiempo predeterminado.

8.- Programa de ordenador almacenado en un soporte de información, incluyendo dicho programa instrucciones que permiten la aplicación de un procedimiento de ordenación según una cualquiera de las reivindicaciones 1 a 2, cuando este programa se carga y ejecuta en un sistema informático.

9.- Soporte de información legible por un sistema informático, eventualmente amovible en todo o parte, especialmente CD-ROM o soporte magnético, como un disco duro o un disquete, o soporte transmisible, como una señal eléctrica u óptica, caracterizado porque incluye instrucciones de un programa de ordenador que permite la aplicación de un procedimiento de ordenación según una cualquiera de las reivindicaciones 1 a 2, cuando este programa se carga y ejecuta en un sistema informático.