ES2491865T3 - Control de flujo de información en una red de paquetes sobre la base de longitudes de paquetes conceptuales variables - Google Patents

Abstract

Método de control de un flujo de información en un sistema de transmisión de datos, que comprende: recibir una pluralidad de paquetes de datos (116) con una velocidad de muestras recibidas, presentando cada uno de ellos una longitud de paquete físico recibido; caracterizado porque presenta la etapa de: determinar una velocidad de servicio para cada uno de los paquetes; para cada paquete, asignar una longitud de paquete conceptual para el paquete, siendo la longitud de paquete conceptual un tiempo de servicio para el paquete, basándose en la velocidad de servicio determinada para el paquete y en la longitud de paquete físico del paquete; y planificar cada paquete en función de la longitud de paquete conceptual respectiva.

Description

15

25

35

45

55

65 E00964487

12-08-2014

DESCRIPCIÓN

Control de flujo de información en una red de paquetes sobre la base de longitudes de paquetes conceptuales variables.

Referencia cruzada a solicitudes relacionadas

La presente solicitud está relacionada con las solicitudes de patente WO 02/30060, WO 02/30066, WO 02/30062, WO 02/30065, WO 02/30061, WO 02/30063 presentadas simultáneamente a la presente el 3 de octubre de 2000.

Campo de la invención

La presente invención se refiere en general a la transmisión de paquetes digitales en sistemas de telecomunicaciones, y, particularmente, aunque no de manera limitativa, a la gestión de contiendas dentro de y entre flujos continuos de paquetes en redes del tipo almacenamiento y reenvío.

Antecedentes de la invención

Existen muchas técnicas para controlar flujos digitales de información por paquetes. Algunas de estas técnicas conllevan la provisión de una cierta calidad de servicio para diferentes tipos de tráfico. Existen varios requisitos generales asociados a la garantía de niveles de calidad de servicio. Cuando se proporciona diferenciación de la calidad para más de un flujo continuo, es necesario garantizar que se cumplen, de manera individual y en conjunto, diferentes requisitos de calidad para los diversos flujos continuos de paquetes, dentro de la limitación de la calidad finita disponible. Con el fin de proporcionar niveles diferenciales de pérdida y retardo así como de caudal, es necesario restringir la cantidad de datos de entrada y su patrón temporal. La cantidad de datos de entrada servidos, es decir, el caudal de datos, se conoce como gestión a largo plazo. El control del patrón temporal de datos se conoce como gestión a corto plazo. También es necesario que el tráfico en flujos continuos particulares se proteja de los efectos consiguientes del carácter de tipo ráfaga de otros flujos continuos. Por ejemplo, es necesario proteger flujos continuos individuales de tráfico con respecto a los efectos de protocolos tales como el TCP, el cual está diseñado para usar el mayor ancho de banda posible sin tener en cuenta otros flujos continuos, y con respecto a intenciones maliciosas o errores en los dispositivos finales de la red. También es necesario gestionar la intercalación de flujos continuos individuales dentro de las limitaciones de los recursos disponibles.

La gestión de la calidad de servicio resulta particularmente difícil en la periferia o borde de una red, ya que, aquí, los dispositivos no se encuentran bajo el control del administrador central de la red. Por lo tanto, el comportamiento de estos dispositivos no se puede presuponer o predecir. La diversidad siempre creciente de las aplicaciones, el tráfico, y la convergencia también complica la gestión de la calidad de servicio. Un tráfico diferente presenta requisitos diferentes de calidad de servicio, y las consecuencias del retardo y/o la pérdida difiere para un tráfico diferente según la interpretación dada a los mismos por una aplicación.

La posibilidad de duplicar dispositivos de red para permitir la separación física y el procesado independiente de tráfico con requisitos de calidad diferentes es poco práctica, en la medida en la que la implementación de los dispositivos de red es cara. Por este motivo, resulta deseable gestionar la calidad de servicio de un tráfico diferente usando un único dispositivo de red.

En la actualidad existe una tendencia a la formación de patrones de tráfico como patrones de velocidad de bits constante, con la finalidad de incrementar la capacidad de predicción. Este es un control determinista que se centra en mejorar las características de pérdida y la eficiencia de una red. No obstante, dichas técnicas presentan la desventaja de que garantizar la calidad en presencia de “sobrerreserva” (overbooking) requiere un conocimiento global total del comportamiento de las fuentes en la red, tal como sus tiempos de activación/desactivación, su fase relativa, y los efectos de su historial pasado sobre el estado de la red.

La llegada de paquetes de datos desde fuentes diferentes es inherentemente incontrolable. Es imposible conocer su temporización y fase relativa exactas. En ciertas condiciones, dichas propiedades se manifiestan prestando un servicio extremadamente injusto a algunos o la totalidad de los flujos continuos de datos. La solicitud de patente en trámite, WO 02/30060, da a conocer una técnica en la cual la competición por recursos se convierte en un proceso más predecible mediante la introducción de espacios entre paquetes, los cuales desligan los flujos continuos. Al asignar espacios variables entre paquetes y flujos continuos de datos para hacer frente a este problema, debe tenerse cuidado en garantizar que los patrones recurrentes de tamaños de paquetes provoquen una interferencia mutua entre los flujos continuos.

Es por lo tanto un objetivo de la presente invención proporcionar una técnica mejorada para controlar el flujo de información en un sistema de transmisión de datos, que posibilite mejorar el control de los requisitos de calidad de servicio para tipos diferentes de tráfico.

La patente US nº 6.003.089 da a conocer una red de datos por paquetes en la cual el tamaño de los paquetes se

15

25

35

45

55

65 E00964487

12-08-2014

puede hacer variar combinando los paquetes.

La patente US nº 6.064.678 da a conocer un método para asignar longitudes óptimas de paquete en un sistema de comunicación de velocidad variable.

El documento EP 254047 da a conocer un aparato de control para su uso en una red de área local por conmutación de paquetes con el fin de monitorizar un caudal y calcular una longitud de paquete media.

Sumario de la invención

Según la presente invención se proporciona un método de acuerdo con lo reivindicado en la reivindicación 1, de control de un flujo de información en un sistema de transmisión de datos, que comprende: recibir una pluralidad de paquetes de datos con una velocidad de muestras recibidas, presentando cada uno de ellos una longitud de paquete físico recibido; caracterizado por la etapa de: determinar una velocidad de servicio para cada uno de los paquetes; para cada paquete, asignar una longitud de paquete conceptual para el paquete, siendo la longitud de paquete conceptual un tiempo de servicio para el paquete, basándose en la velocidad de servicio determinada, para el paquete, y en la longitud de paquete físico del paquete; y planificar cada paquete en función de la longitud de paquete conceptual respectiva.

La asignación de dicha longitud variable a un paquete físico con el fin de colaborar con el procesado posterior de dichos paquetes hace frente al problema antes mencionado.

La longitud de paquete conceptual puede ser menor o mayor que la longitud del paquete físico recibido.

El método puede comprender además la etapa de generar un flujo de información modificado en el cual la separación entre los paquetes y la velocidad de servicio determinada es variable.

La presente invención proporciona además un controlador, de acuerdo con lo reivindicado en la reivindicación 17, para controlar un flujo de información en un sistema de transmisión de datos, que comprende: unos medios de entrada para recibir una pluralidad de paquetes de datos con una velocidad de muestras recibidas, presentando cada paquete una longitud de paquete físico recibido; caracterizado por: unos medios de asignación para asignar para cada paquete una longitud de paquete conceptual, siendo la longitud de paquete conceptual un tiempo de servicio para el paquete, sobre la base de una velocidad de servicio determinada para el paquete y de la longitud de paquete físico del paquete; y unos medios de salida para dar salida a los paquetes, planificándose cada paquete en función de la longitud de paquete conceptual respectiva.

El controlador puede comprender además unos medios de modificación para generar un flujo de información modificado en el cual los paquetes están separados de manera variable. Los medios de modificación pueden comprender un modulador.

Breve descripción de las figuras

La invención se pondrá más claramente de manifiesto, a título de ejemplo, haciendo referencia a las figuras adjuntas, en las cuales:

la figura 1 ilustra un diagrama de bloques de la arquitectura de un multiplexor de acuerdo con una forma de realización ejemplificativa de la invención;

la figura 2 ilustra el principio de colas de espera de acuerdo con una forma de realización ejemplificativa de la invención;

la figura 3 ilustra el principio de asignación de niveles de prioridad de acuerdo con una forma de realización ejemplificativa de la invención;

la figura 4 ilustra el principio del servicio estocástico de paquetes de acuerdo con una forma de realización ejemplificativa de la invención;

la figura 5 ilustra el principio de la longitud de paquete conceptual de acuerdo con una forma de realización ejemplificativa de la invención.

Las figuras 6(a) y 6(b) ilustran el principio de la disposición en cascada de conformador/reguladores de acuerdo con una forma de realización ejemplificativa de la invención;

la figura 7 ilustra el principio de definir una carga transportada en función de una carga ofrecida en una forma de realización ejemplificativa de la presente invención;

15

25

35

45

55

65 E00964487

12-08-2014

la figura 8 ilustra una forma de realización ejemplificativa de un Regulador/Conformador para implementar la presente invención;

la figura 9 ilustra una forma de realización ejemplificativa de un Multiplexor de Acogida/Urgencia para implementar la presente invención;

la figura 10 ilustra el perfil de carga correspondiente a una implementación ejemplificativa de un Regulador/Conformador.

Descripción de la forma de realización preferida

Haciendo referencia a la figura 1, se muestra un diagrama que ilustra la arquitectura de un multiplexor básico con respecto al cual se describe en este documento el funcionamiento de la presente invención. Debería observarse que la aplicación de la presente invención no se limita a la arquitectura específica mostrada en la figura 1, y que, a partir de la lectura de la siguiente descripción, los expertos en la materia apreciarán la aplicabilidad general de la presente invención. El multiplexor ejemplificativo de la figura 1 multiplexa flujos continuos de datos en una red basada en paquetes tal como se describirá con mayor detalle a continuación en la presente memoria.

El multiplexor ejemplificativo comprende una interfaz de entrada 100, un identificador de flujos continuos 102, una pluralidad de reguladores/conformadores 104, un multiplexor de acogida/urgencia 106, un limitador de velocidad 108, una interfaz de salida 110, una memoria de cola de espera 112, y un gestor de memoria de cola de espera 114.

El multiplexor recibe como entrada sobre las líneas 116 un flujo de información. El flujo de información comprende paquetes que pueden estar asociados a varios tipos diferentes de tráfico de datos. Los paquetes se pueden recibir en paralelo o en serie. La entrada sobre la línea 116 puede recibir flujos de información paralelos. El flujo continuo de datos de entrada 116 puede contener paquetes asociados a varios tipos diferentes de tráfico. A efectos del ejemplo descrito, se supone que el flujo continuo de datos incluye un flujo continuo de voz por IP, un flujo continuo de transferencia de datos en bloques, y un flujo continuo de tráfico telnet.

La interfaz de entrada 100 proporciona la funcionalidad básica necesaria para recibir paquetes de datos transmitidos, desde un sistema o dispositivo externo a través de un medio de transmisión. La interfaz de entrada 100 recibe paquetes desde el flujo continuo de datos de entrada 116 y reenvía los paquetes recibidos, preferentemente en paralelo, sobre las líneas 118 tanto al identificador de flujos continuos 102 como al gestor de memoria de cola de espera 114. La interfaz de entrada debe tener una funcionalidad que resulte apropiada para el sistema o dispositivo externo particular en el cual se originan paquetes sobre el flujo continuo de datos de entrada 116. La interfaz de entrada no es responsable directamente de ningún procesado relacionado con la gestión de la calidad del flujo continuo de datos de acuerdo con la presente invención. La interfaz de entrada puede tener cierta funcionalidad básica para llevar a cabo una comprobación inicial sobre paquetes recibidos en el flujo continuo de datos de entrada. Por ejemplo, si se recibe un paquete alterado, la interfaz de entrada puede descartar el paquete.

La estructura de la interfaz de entrada depende de la implementación. La funcionalidad básica de la interfaz de entrada, necesaria para llevar a cabo cualquiera de las características deseadas, resultará evidente para los expertos en la materia.

El gestor de memoria de cola de espera 114 es responsable de gestionar un conjunto de colas de espera y un área de almacenamiento de paquetes. El gestor de memoria de cola de espera 114 recibe paquetes desde la interfaz de entrada 100. Al producirse la llegada de un paquete, el gestor de memoria de cola de espera asigna un identificador exclusivo al paquete, y envía el identificador, correspondiente al paquete, al identificador de flujos continuos 102 sobre la línea 140. El gestor de memoria de cola de espera almacena adicionalmente el paquete en una memoria intermedia temporal de paquetes. El gestor de memoria de cola de espera asigna también un contador de referencia al paquete, e inicializa a cero el contador de referencia correspondiente a ese paquete. Tal como se describirá de forma adicional posteriormente en la presente, el contador de referencia es usado por el gestor de memoria de cola de espera para determinar si el paquete asociado al contador de referencia está siendo procesado todavía por el multiplexor 100, o si el mismo se debería eliminar de (o no se debería introducir inicialmente en) la memoria de cola de espera 112.

El identificador de paquete es un identificador que identifica de manera exclusiva un paquete. El identificador de paquete identifica de manera exclusiva el paquete con la finalidad de almacenar el identificador de paquete en la memoria de cola de espera 112, tal como se describe de forma adicional posteriormente en la presente, y de diferenciar cada paquete con respecto a otros paquetes en la memoria. En una implementación sencilla, el identificador de paquete es un número, asignándose a cada paquete un identificador de paquete que es el siguiente número de la secuencia. Alternativamente, el identificador de paquete puede estar compuesto por información exclusiva del encabezamiento del paquete. En sistemas en los que el tamaño del paquete es variable, la longitud del paquete se puede incluir en el identificador de paquete.

El identificador de flujos continuos 102 recibe también los paquetes desde la interfaz de entrada sobre las líneas

15

25

35

45

55

65 E00964487

12-08-2014

118, y recibe el identificador de paquete correspondiente a cada paquete sobre la línea 140 desde el gestor de memoria de cola de espera 114. El identificador de flujos continuos 102 es responsable de determinar a qué flujo continuo pertenece cada paquete. Así, por ejemplo, el identificador de flujos continuos determinará si un paquete particular está asociado a un flujo continuo de voz por IP, a un flujo continuo de transferencia de datos en bloques, o a un flujo continuo de tráfico telnet. De acuerdo con el flujo continuo al que pertenezca el identificador de paquete recibido particular, el identificador de flujos continuos reenvía el identificador de paquete correspondiente a ese paquete a uno de los reguladores/conformadores 104 para su posterior procesado.

Tal como se pondrá de manifiesto a partir de la siguiente descripción, el resto del procesado se basa en el identificador de paquete y no en el paquete. El identificador de paquete proporciona de manera ventajosa una representación eficiente del paquete. Tal como se describirá posteriormente en la presente, la memoria de cola de espera y los identificadores de paquetes garantizan que la posición original en secuencia de cada paquete individual no se pierde en la operación de multiplexado.

El regulador/conformadores 104 son una variante operativa de una cola de espera FIFO, en la cual, se produce un procesado auxiliar asociado a la inserción y eliminación de elementos de la cola de espera. Dichas colas de espera FIFO son bien conocidas, y su implementación se incluirá claramente dentro del alcance de un experto en la materia. La configuración del regulador/conformadores depende de la implementación.

En el ejemplo simple mostrado en la figura 1, se supone que se asigna un regulador/conformador a cada uno de los diferentes tipos de flujos continuo de tráfico que se recibe. De este modo, por ejemplo, el regulador/conformador 104a se asigna a tráfico de voz por IP, el regulador/conformador 104b se asigna a tráfico de transferencia de datos en bloques, y el regulador/conformador 104c se asigna a tráfico telnet. El regulador/conformador 104d se muestra en la figura 1 mediante la ilustración de unos medios para gestionar paquetes asociados a flujos continuos diferentes a los procesados por el regulador/conformadores 104a a 104c. De este modo, el identificador de flujos continuos 102 reenvía identificadores de paquete asociados a paquetes de voz por IP sobre la línea 120a al regulador/conformador 104a, reenvía identificadores de paquete asociados a paquetes de transferencia de datos en bloques sobre la línea 120b al regulador/conformador 104b, y reenvía identificadores de paquete asociados a paquetes de tráfico telnet sobre la línea 120c al regulador/conformador 104c.

En el caso de la multidifusión u otros servicios que requieran duplicación (por ejemplo, la monitorización), el identificador de flujos continuos 102 puede reenviar identificadores de paquetes a más de un regulador/conformador

104.

Debería observarse que el identificador de flujos continuos 102 no reenvía paquetes para un procesado posterior dentro del multiplexor 100. En su lugar, el identificador de flujos continuos reenvía los identificadores de paquetes asignados a paquetes para su procesado posterior en el multiplexor 100.

El regulador/conformadores 104 son responsables de la asignación de clasificaciones de calidad a los paquetes dentro de un flujo continuo, y son responsables del control de calidad del flujo continuo tanto a corto plazo como a largo plazo mediante el descarte selectivo de identificadores de paquetes en el flujo continuo y el desplazamiento selectivo en el tiempo de paquetes en el flujo continuo.

Una de las funciones del regulador/conformadores es servir paquetes, usando los identificadores de paquete correspondientes, con una velocidad de servicio variable. Como consecuencia, los identificadores de paquete que salen de un regulador/conformador están separados de manera variable, preferentemente con una separación aleatoria o seudoaleatoria. La separación aleatoria de los paquetes garantiza que al tráfico menos urgente le presta servicio finalmente el multiplexor de acogida/urgencia 106. La separación variable de los paquetes en la salida del regulador/conformadores 104 reduce la coherencia entre flujos continuos de fuentes independientes. La creación de patrones temporales independientes entre flujos continuos hace que aumente la ecuanimidad de los procesos de decisión del multiplexor de acogida/urgencia. Las clasificaciones de acogida/urgencia asignadas a los identificadores de paquetes en el regulador/conformadores no garantizan por sí solas la ecuanimidad de forma incondicional.

Por ejemplo, el retardo experimentado por un paquete con un nivel de urgencia asociado bajo, depende del patrón temporal de los flujos continuos de tráfico más urgentes. Si dos flujos continuos con diferentes niveles de acogida/urgencia son temporalmente coherentes, puede que los paquetes con mayor grado de acogida “ganen” siempre la carrera para entrar en el multiplexor de acogida/urgencia 106 y/o puede que los datos más urgentes se transmitan siempre en primer lugar. Esto resulta estadísticamente menos probable si los flujos continuos tienen paquetes separados de forma variable.

Haciendo referencia a la figura 4, se ilustran dos de los reguladores/conformadores 104a y 104b de la figura 1, con ejemplos de flujos continuos de paquetes de datos en sus entradas y salidas. El regulador/conformador 104a recibe paquetes 200 con una separación constante t sobre su línea de entrada 120a. El regulador/conformador 104b recibe identificadores de paquetes 202 con una separación constante t sobre su línea de entrada 120b. El regulador/conformador 104a sirve los identificadores de paquetes en su cola de espera de tal manera que los paquetes 200a, 200b y 200c se generan en su línea de salida 122a con una separación variable entre ellos. De

15

25

35

45

55

65 E00964487

12-08-2014

manera similar, el servicio de identificadores de paquetes por parte del regulador/conformador 104b da como resultado identificadores de paquetes 202a, 202b y 202c sobre su línea de salida 122b que tienen una separación variable.

Una segunda función del regulador/conformadores es limitar el volumen de tráfico en un flujo continuo, logrado por el descarte selectivo de paquetes. La naturaleza de la política reguladora se especifica en términos de un perfil de carga, el cual es una función de (por lo menos) la carga ofrecida (es decir, la velocidad de llegada de paquetes en un flujo continuo). Por lo tanto, y de manera ventajosa, puede haber características diferentes definidas para varios niveles de carga. Es decir, la calidad se puede mejorar o reducir a medida que aumenta la velocidad de llegada. Por lo tanto, las características de transporte se pueden configurar de manera que se correspondan mejor con los requisitos de aplicación y de manera que se eviten los efectos de una carga ofrecida anormal, por ejemplo, ataques de denegación de servicio. Haciendo referencia a la figura 7, se ilustra el principio de definición de características de transporte en términos de carga ofrecida.

En la figura 7, el eje X ilustra la carga ofrecida y el eje Y ilustra la carga que se transporta realmente. Tal como puede observarse en la figura 7, existen dos niveles de umbral: un nivel de umbral inferior 250; y un nivel de umbral superior 252. Si la carga ofrecida no supera el nivel de umbral 252, entonces la carga ofrecida se puede transportar dentro de garantías configuradas. Si la carga ofrecida supera el nivel de umbral 252, entonces no se puede garantizar la transmisión de la carga ofrecida. El nivel de umbral inferior 250 representa la carga transportada mínima con independencia de lo alta que llegue a ser la carga ofrecida.

Así, haciendo referencia una vez más a la figura 7, una vez que la carga ofrecida alcanza el nivel de umbral superior 252 y el punto 254, la carga transportada se ajusta de tal modo que se reduce. Cuando la carga ofrecida aumenta, la carga transportada continúa reduciéndose hasta el punto en el que se estabiliza y tiende hacia el nivel de umbral inferior 250.

Así, la velocidad de descarte de paquetes queda determinada por la carga ofrecida. El nivel de umbral superior define un nivel en el cual se activa el descarte selectivo de paquetes. Los paquetes se descartan preferentemente basándose en una aproximación instantánea de la carga ofrecida. Los paquetes se pueden descartar en términos probabilísticos basándose en una aproximación instantánea de la carga ofrecida. Si la carga ofrecida da como resultado una carga transportada que supera el nivel de umbral superior, la carga transportada se reduce por debajo del nivel de umbral superior mediante el descarte selectivo de paquetes. Cuando se reduce, la carga transportada se reduce preferentemente a un nivel por encima del nivel de umbral inferior. La reducción de la carga transportada es mayor cuanto más grande sea la carga ofrecida. La carga transportada se reduce además como respuesta a un aumento de la carga ofrecida.

Un Regulador/Conformador logra un perfil de carga deseado mediante el descarte selectivo de paquetes. Los paquetes se descartan preferentemente basándose en una aproximación instantánea de la carga ofrecida. Haciendo referencia a la figura 10, se ilustra un perfil de carga para una implementación ejemplificativa de un Regulador/Conformador. La figura 10 ilustra un perfil de carga para un regulador/conformador ejemplificativo implementado en forma de una cola de espera con 10 memorias intermedias y tiempos de servicios estocásticos muestreados a partir de una distribución exponencial, con parámetros de velocidad µ1= µ2=...= µ9=1,3234, µ10=0,5. La gráfica presenta un perfil de carga para un Regulador/Conformador implementado como una cola de espera con 10 memorias intermedias que tienen tiempos de servicio muestreados a partir de una distribución exponencial cuyo parámetro de velocidad depende del número de paquetes en la cola de espera. Se proporciona una descripción de una implementación de este tipo en un ejemplo a continuación. Los parámetros de velocidad de servicio son µ1= µ2=...= µ9=1,3234, µ10=0,5, escalándose los valores numéricos para las velocidades de servicio y la carga ofrecida y transportada de manera que el nivel de umbral superior adopta el valor 1. El perfil de carga ilustrado en la figura 10 representa la carga transportada media cuando el tráfico de llegada presenta un patrón de Poisson. La aplicación de resultados de la teoría convencional de colas de espera permite la determinación de la tasa de pérdidas esperada.

Una tercera función del regulador/conformadores 104 consiste en asignar clasificaciones de acogida y urgencia a los identificadores de paquetes incluidos en sus colas de espera. Mediante la asignación de dichas clasificaciones a los identificadores de paquetes, a los propios paquetes se les asigna inherentemente la misma clasificación. El principio de niveles de acogida y urgencia se describe en la solicitud de patente internacional PCT/GB00/01569 (PWF Ref. 101926). Un nivel de acogida indica una clase o nivel de pérdida para un paquete. La clase de pérdida indica la tendencia del paquete a ser descartado. Un nivel de urgencia indica el nivel de urgencia con el cual se debería procesar un paquete. Los niveles de urgencia y de acogida se pueden considerar, combinados, de manera que constituyen un nivel de prioridad para un paquete. Así, en este contexto un nivel de prioridad tiene dos componentes.

Tal como se ha descrito anteriormente en la presente memoria, en este regulador/conformador ejemplificativo, se determinan características de transporte para un flujo continuo, incluyendo la asignación de niveles de acogida y urgencia, basándose en la carga ofrecida. Las clasificaciones de acogida y urgencia se asignan de manera ventajosa simultáneamente a identificadores de paquetes sobre la base de una función del estado actual de la cola de espera cuando se está calculando la clasificación. La probabilidad de encontrarse en un estado particular es una

15

25

35

45

55

65 E00964487

12-08-2014

función de la carga ofrecida. Esta función de clasificación es configurable, y se puede seleccionar sin limitación. Por ejemplo, un regulador/conformador dado se puede configurar para asignar una de dos clasificaciones a paquetes basándose en una elección probabilística. La probabilidad de clasificación usada se puede relacionar con la longitud de la cola de espera. Es decir, una configuración de este tipo se puede diseñar para asignar clasificaciones más altas a paquetes con una mayor probabilidad cuando la carga ofrecida es baja.

La clasificación de un paquete determina la pérdida y el retardo máximos que experimentará con mayor probabilidad cuando se multiplexe con otros flujos continuos en la salida del regulador/conformadores, tal como se describirá más detalladamente en la presente más adelante. Este es un concepto independiente con respecto al de la pérdida y el retardo que puede experimentar el paquete dentro del propio regulador/conformador. La pérdida experimentada por un paquete en el regulador/conformador depende de la velocidad de llegada reciente del flujo continuo y de la longitud de la cola de espera. El retardo se determina por las velocidades de servicio configuradas y la longitud de la cola de espera.

Cada uno del regulador/conformadores 104 se materializa preferentemente usando una cola de espera con una velocidad de servicio variable. Cuando un regulador/conformador 104 recibe un identificador de paquete, determina si el identificador de paquete se debería almacenar en su cola de espera interna o se debería descartar. El control de la admisión de un identificador de paquete en una cola de espera de un regulador/conformador se describe de forma adicional posteriormente en la presente.

A continuación se describe en primer lugar la operación por la cual los paquetes se admiten en o se descartan del regulador/los conformadores 104. En el contexto de la presente descripción, se toma un ejemplo de un regulador/conformador que utiliza un sistema de colas de espera que tiene una longitud de cola de espera de cuatro tal como se ilustra en la figura 2. Cada estado de la figura 2 se etiqueta con la longitud de la cola de espera en ese estado. Los tiempos de servicio en cada estado se obtienen muestreando una distribución exponencial con el parámetro de velocidad µ. Los tiempos de servicio determinan la velocidad conceptual de servicio para el paquete. En el ejemplo mostrado en la figura 2 se usan dos velocidades de servicio diferentes. Si la cola de espera está en el estado 1 (es decir, la cola de espera tiene solamente un paquete), entonces µ1 determina la velocidad de servicio para el paquete en la cabeza de la cola de espera. Si la cola de espera es mayor, por ejemplo en el estado 3, se usaría la velocidad de servicio µ2. Esta forma de realización de ejemplo del regulador/conformador tiene también probabilidades de descarte arbitrarias asociadas a cada estado. Es decir, al producirse la llegada, existe una probabilidad de que el identificador del paquete se descarte de manera arbitraria. En este ejemplo, la probabilidad de este evento depende del estado de la cola de espera cuando llega el identificador del paquete. A continuación se describe el funcionamiento de un regulador/conformador en términos del estado de la cola de espera al producirse la llegada del identificador del paquete.

En un primer caso, se supone que la cola de espera está completa en el momento en el que llega el identificador de paquete. En tal caso, la probabilidad de que el identificador del paquete esté entrando en la cola de espera es cero. Esto no significa necesariamente que el paquete se descarte de manera automática, ya que el paquete se puede haber enviado a más de uno del regulador/conformadores disponibles. En tal caso, el regulador/conformador 104 reenvía una orden sobre su línea respectiva 138 para decrementar el recuento de referencia para el paquete asociado a un identificador particular. A continuación, el gestor de memoria de cola de espera descartará el paquete al que remite el identificador de paquete si su recuento de referencia es 0 o menor.

En un segundo caso, en el momento de la llegada de un identificador de paquete al regulador/conformador 104, la cola de espera está prácticamente completa. Por ejemplo, supóngase que la cola de espera está en el estado 3. En el estado 3, existe una probabilidad del 30% de que el identificador del paquete no entre en la cola de espera. Si el identificador del paquete se admite, entonces el mismo se almacena en la cola de espera del regulador/conformador y la cola de espera se mueve al estado 4. La cola de espera está entonces llena, y no se admitirá ningún identificador de paquete que llegue antes de que salga otro identificador de paquete de la cola de espera.

Si el identificador de paquete se introduce en la cola de espera del regulador/conformador 104, el regulador/conformador 104 envía una señal apropiada sobre su línea respectiva 138 al gestor de memoria de cola de espera indicando que el paquete asociado al identificador de paquete se debe admitir en la memoria de cola de espera 112 y almacenar en una cola de espera específica asignada para paquetes pertenecientes a este flujo continuo.

Cuando se planifica una salida, se sirve el identificador de paquete de la cabeza de la cola de espera. La velocidad muestreada que se usa para servir este identificador de paquete depende del estado de la cola de espera. Basándose en que la cola de espera se encuentre en el estado 4, la velocidad de servicio de muestras usada para servir este identificador de paquete se determina mediante una variable aleatoria de distribución exponencial con media µ2. El tiempo de servicio calculado de este paquete se basa en la velocidad de servicio de muestras y la longitud del paquete.

En un tercer caso, un identificador de paquete llega en un momento en el que la cola de espera está casi vacía. El procesado del identificador de paquete en este caso es muy similar al caso en el que la cola de espera está casi

15

25

35

45

55

65 E00964487

12-08-2014

llena. Supóngase que un identificador de paquete llega cuando la cola de espera se encuentra en el estado 1. No existe ninguna probabilidad de que el paquete se descarte de manera arbitraria, puesto que la probabilidad de este evento se ha configurado para que sea cero. Por lo tanto, el identificador de paquete se almacena en la cola de espera, y la cola de espera se mueve al estado 2. Si se planifica un evento de salida antes de que se produzca otra llegada, se sirve el identificador de paquete de la cabeza de la cola de espera basándose en la velocidad de servicio correspondiente al estado 2, que es µ1.

En un cuarto caso, el identificador de paquete llega en un momento en el que la cola de espera está vacía. En este caso, tal como en el tercer caso, el identificador de paquete se admitirá en la cola de espera.

La descripción contenida en la presente anteriormente ha supuesto que el regulador/conformador no está configurado para enviar ningún paquete sin retardo. En otras palabras, el regulador/conformador no tiene preferentemente ninguna transparencia de carga baja, retardándose todos los paquetes.

En su forma más sencilla, una transparencia de carga baja permite que el primer paquete que llega a una cola de espera vacía sea reenviado inmediatamente. Con independencia de esta acción, la cola de espera se mueve al estado 1. Los paquetes posteriores que llegan se procesan como si este paquete estuviera presente, excepto que este paquete, cuando normalmente se habría reenviado al producirse la expiración de su temporizador, no se envía. En la cola de espera se registra si un identificador de paquete se ha reenviado inmediatamente o no al producirse la llegada. Este concepto se puede ampliar de manera similar a múltiples paquetes.

Antes de que un identificador de paquete abandone un regulador/conformador, el regulador/conformador determina una clasificación de calidad para ese identificador de paquete. El regulador/los conformadores clasifican los identificadores de paquetes, según se ha descrito anteriormente en la presente, con clasificaciones de acogida y urgencia. Cada identificador de paquete se debe clasificar con una clasificación de acogida y urgencia antes de que sea reenviado al multiplexor de acogida/urgencia 106. La clasificación asignada a un identificador de paquete es una función del estado actual de la cola de espera.

Supóngase nuevamente un regulador/conformador que tiene una cola de espera de longitud 4. Tal como se muestra en la figura 2, se supone que la cola de espera del regulador/conformador está configurada de tal modo que las velocidades de servicio para los estados 1 y 2 se definen como µ1, y la posibilidad de pérdida arbitraria para los estados 1 y 2 es cero. Los estados 3 y 4 tienen una velocidad de servicio definida de µ2, y tienen una probabilidad de pérdida arbitraria de 0,3 (es decir el 30%).

En una forma de realización preferida, cada regulador/conformador está configurado con una clasificación principal y secundaria de acogida/urgencia, y a un identificador de paquete se le asigna una de las clasificaciones al producirse su llegada. Cada estado tiene una probabilidad asociada de que un paquete se clasifique con la clasificación principal. La probabilidad de clasificar un paquete con la clasificación principal en cada estado está configurada, en este ejemplo, de manera que es: para el estado 1, el 100%; para el estado 2, el 80%; para el estado 3, el 60%; y para el estado 4, el 40%. En la figura 3 se ilustran estas probabilidades.

Por ejemplo, la clasificación principal puede ser una clasificación más deseable que la clasificación secundaria. Si la carga ofrecida en el flujo continuo es baja, los paquetes tienen una mayor probabilidad de que se les asigne la clasificación principal más deseable, en la medida en la que la cola de espera estará con la mayor frecuencia en el estado 1 o 2. A medida que aumenta la carga ofrecida, se produce una probabilidad mayor de que a un identificador de paquete se le asigne la clasificación secundaria, que resulta menos deseable, ya que esto podría significar que el identificador de paquete experimentase un retardo y/o una pérdida mayores en el multiplexor de acogida/urgencia.

Haciendo referencia a la anterior descripción, en la presente memoria, de los criterios para admitir un identificador de paquete en la cola de espera, cuando se admite un identificador de paquete en la cola de espera en el caso 2 (es decir, en el ejemplo en el que la cola de espera está en el estado 3 y se admite el identificador de paquete, moviendo la cola de espera al estado 4), la probabilidad de clasificar el identificador de paquete con la clasificación principal es del 40% ya que la cola de espera está entonces en el estado 4. Por lo tanto, existe una probabilidad del 40% de que al identificador de paquete se le asigne la clasificación principal, y una probabilidad del 60% de que se le asigne la clasificación secundaria. Esta clasificación del identificador de paquete se basa en una simple elección probabilística.

A continuación, se emite un identificador de paquete desde la cola de espera del regulador/conformador al final del tiempo de servicio calculado, y la cola de espera se mueve al estado 3. A continuación, un nuevo tiempo de servicio calculado basado en los parámetros definidos del estado 3 determina cuándo se lleva a cabo la siguiente salida. Si se produce una llegada antes de que se acabe este periodo de tiempo, entonces la cola de espera se puede mover nuevamente al estado 4, basándose en si la llegada se descarta o no arbitrariamente.

Haciendo referencia al anterior caso 3, en el caso en el que un identificador de paquete llegue cuando la cola de espera está casi vacía, el identificador de paquete se clasifica usando la probabilidad asociada al estado 2. En este caso, existe una probabilidad del 80% de que el identificador de paquete se envíe al multiplexor de acogida/urgencia

15

25

35

45

55

65 E00964487

12-08-2014

106 con la clasificación principal.

El descarte arbitrario de paquetes al producirse su llegada a un regulador/conformador no solamente reduce la velocidad de llegada del flujo continuo, sino que también ayuda a evitar la pérdida en ráfagas. Por ejemplo, si una ráfaga de seis paquetes llegase al sistema de colas de espera de la figura 2, los últimos dos paquetes se perderían si los paquetes no se descartasen de manera arbitraria. Por otro lado, si la probabilidad del descarte arbitrario aumenta con la longitud de la cola de espera, puede darse el caso de que, por ejemplo, el cuarto o tercer paquete se descarte en la llegada, distribuyéndose así la pérdida de la ráfaga de manera más ecuánime.

Otra de las funciones del regulador/conformador según se ha descrito anteriormente en la presente, es mantener el paquete asociado al identificador de paquete que se está procesando en la memoria de cola de espera 112 mediante interacción con el gestor de memoria de cola de espera 114. El almacenamiento de paquetes en colas de espera es necesario para garantizar que los paquetes de un flujo continuo no son reordenados por el proceso de servicio del multiplexor de acogida/urgencia 106. Dependiendo de la función escogida para asignar niveles de acogida/urgencia a paquetes, existe la posibilidad de que los paquetes se pudieran reordenar durante el multiplexado sobre la línea 124, tal como se describe adicionalmente más adelante en la presente.

Como ejemplo, considérese la función simple de clasificación probabilística descrita anteriormente. Supóngase que al regulador/conformador llega una ráfaga de cuatro identificadores de paquetes y todos los paquetes se almacenan en la cola de espera. Además, supóngase que no se produce ninguna llegada más durante el primer periodo en cuestión. Nuevamente además, supóngase que el multiplexor de acogida/urgencia no está vacío, originándose paquetes en otro regulador/conformadores. Finalmente, supóngase que la clasificación principal de acogida/urgencia tiene un nivel de urgencia alto deseable, mientras que la segunda clasificación tiene un nivel de urgencia bajo. Dadas estas condiciones, el identificador de paquete del inicio de la ráfaga, al que se hace referencia como “identificador de paquete 1”, tiene una probabilidad mayor de que se le asigne la clasificación secundaria de acogida/urgencia que un paquete próximo al final de la ráfaga, denominado “identificador de paquete 4”. Si al identificador de paquete 1 se le asigna la clasificación secundaria, mientras que al identificador de paquete 4 se le asigna la clasificación primaria, la diferencia de los niveles de urgencia puede provocar que el identificador de paquete 4 se sirva antes que el identificador de paquete 1 en el multiplexor de acogida/urgencia 106.

Para evitar esto, el regulador/los conformadores dan instrucciones al gestor de memoria de cola de espera 114 para situar en cola de espera los paquetes en la memoria de cola de espera 112 de acuerdo con el orden en el cual los identificadores de paquetes correspondientes se reciben en el regulador/conformador. Es decir, al producirse la llegada al regulador/conformador, si un identificador de paquete no se descarta, se dan instrucciones a la memoria de cola de espera para que sitúe en cola el paquete en la cola de espera del flujo continuo pertinente en el orden en el que llegó.

La figura 8 muestra una implementación de ejemplo de un regulador/conformador 104. El Regulador/Conformador ejemplificativo incluye el bloque de proceso de llegada al Regulador/Conformador 701, un bloque de cola de espera de identificadores de paquete 702, un bloque de proceso de salida del Regulador/Conformador 704, un temporizador 703, un generador de probabilidades de descarte 706, y un generador de tiempos de servicio 707.

Los identificadores de paquetes llegan por medio de la línea 708 al bloque de proceso de llegada al Regulador/Conformador 701. El bloque de proceso de llegada al Regulador/Conformador 701 notifica al bloque de gestión de configuración del Regulador/Conformador 705, por medio de la línea 720, que ha llegado un identificador de paquete. El bloque de gestión de configuración del Regulador/Conformador interroga al bloque de cola de espera de identificadores de paquete 702, por medio de la línea 724, para obtener la longitud actual de la cola de espera dentro del Regulador/Conformador. Basándose en la respuesta del bloque de cola de espera de identificadores de paquetes por medio de la línea 726, el bloque de gestión de configuración del Regulador/Conformador determina si la cola de espera está o no completa. Si hay capacidad disponible en la cola de espera, el bloque de gestión de configuración del Regulador/Conformador 705 determina a continuación si el identificador de paquete se debería descartar o no arbitrariamente, usando una entrada proveniente del generador de probabilidades de descarte 706 sobre la línea 732.

Si el identificador de paquete se va a admitir en la cola de espera, el bloque de gestión de configuración del Regulador/Conformador 705 alerta al bloque de proceso de llegada al Regulador/Conformador 701, por medio de la línea 722, para que admita el identificador de paquete. Al producirse la recepción de esta respuesta, el bloque de proceso de llegada al Regulador/Conformador 701 envía una solicitud, por medio de la línea 736 (equivalente a una de las líneas 138), al gestor de memoria de cola de espera 114 para situar en cola de espera el paquete en la cola de espera de la memoria de cola de espera que está asignada para este flujo continuo. A continuación, el proceso de llegada al Regulador/Conformador reenvía el identificador de paquete al bloque de cola de espera de identificadores de paquete 702 por medio de la línea 710. El bloque de gestión de configuración del Regulador/Conformador 705 calcula un nuevo tiempo de servicio, basándose en la entrada proveniente del generador de tiempos de servicio 707 sobre la línea 734 y la longitud del paquete, y envía este tiempo de servicio al bloque de proceso de salida del Regulador/Conformador 704 por medio de la línea 728. El proceso de salida del Regulador/Conformador reenvía el tiempo de servicio nuevo al temporizador 703 por medio de la línea 716. El

15

25

35

45

55

65 E00964487

12-08-2014

temporizador 703 se reinicializa para reactivarse al final del tiempo de servicio nuevo.

Si el bloque de gestión de configuración del Regulador/Conformador 705 determina que la cola de espera está llena, da instrucciones al bloque de proceso de llegada al Regulador/Conformador 701, por medio de la línea 722, para que descarte el identificador de paquete. En este caso, el bloque de proceso de llegada al Regulador/Conformador 701 envía una instrucción de descarte al gestor de memoria de cola de espera 114 por medio de la línea 736. A continuación, el bloque de proceso de llegada al regulador/conformador descarta al identificador de paquete.

Cuando el temporizador 703 se reactiva, envía una solicitud, por medio de la línea 718, al bloque de proceso de salida del Regulador/Conformador 704 para que emita un identificador de paquete. El bloque de proceso de salida del Regulador/Conformador envía una solicitud al bloque de gestión de configuración del Regulador/Conformador 705, por medio de la línea 730, para una clasificación y un tiempo de servicio nuevo. El bloque de gestión de configuración 705 interroga al bloque de cola de espera de identificadores de paquete 702, por medio de las líneas 724 y 726, para obtener la longitud actual de la cola de espera. El bloque de gestión de configuración usa la longitud actual de la cola de espera para determinar la clasificación correspondiente al identificador de paquete que está a punto a emitirse. La clasificación se envía al bloque de proceso de salida del Regulador/Conformador por medio de la línea 728. El proceso de salida del Regulador/Conformador 704 concatena un identificador de cola de espera, especificando qué cola de espera de la memoria de cola de espera 112 se usa para almacenar paquetes de este flujo continuo, y la clasificación con el identificador de paquete, y reenvía esta tupla de datos sobre la línea 738.

Debería observarse que, en esta implementación de ejemplo, la clasificación de los identificadores de paquete se lleva a cabo a medida que los paquetes abandonan la cola de espera. No obstante, el momento en el que los paquetes se clasifican dentro del Regulador/Conformadores depende de la implementación, y no se limita al ejemplo ofrecido en la presente. Tal como se ha descrito anteriormente en la presente memoria, los identificadores de paquete se pueden clasificar al producirse su llegada en lugar de su salida.

Si la cola de espera identificada en el bloque de cola de espera de identificadores de paquetes 702 no está vacía, el bloque de gestión de configuración del Regulador/Conformador 705 envía también un tiempo de servicio nuevo al bloque de proceso de salida del Regulador/Conformador 704 por medio de la línea 728. Este tiempo de servicio se reenvía al temporizador 703 por medio de la línea 716, y el temporizador se ajusta a sí mismo para reactivarse después de este tiempo. Si la cola de espera está vacía, no se lleva a cabo ninguna acción.

Haciendo referencia a la figura 6 se ilustran otras modificaciones posibles del regulador/conformadores 104 mostrados en la figura 1. Tal como se muestra en la figura 6, el regulador/conformadores se pueden disponer en cascada de diversas maneras.

Haciendo referencia a la figura 6(a), se ilustra una disposición ventajosa en la cual la salida de un regulador/conformador 210 proporciona una entrada a dos reguladores/conformadores paralelos 212 y 214. El regulador/conformador 210 recibe identificadores de paquete sobre la línea 222 a partir del identificador de flujo continuo 102. De acuerdo con el funcionamiento convencional del regulador/conformador, el regulador/conformador 210 descarta selectivamente identificadores de paquete y desplaza en el tiempo identificadores de paquete para proporcionar un flujo modificado de identificadores de paquete en su salida. En una primera forma de realización, el flujo, así modificado, de identificadores de paquete se difunde de forma general sobre las líneas 234 y 236 a cada uno de los reguladores/conformadores paralelos 212 y 214. A continuación, los reguladores/conformadores respectivos 212 y 214 descartan selectivamente identificadores de paquete y desplazan en el tiempo identificadores de paquete para generar otros dos flujos modificados de identificadores de paquete en sus salidas 224 y 226. En una segunda forma de realización, la salida del regulador/conformador 210 se proporciona selectivamente o bien a uno o bien al otro de los reguladores/conformadores 212 y 214. El regulador/conformador apropiado de entre el 212 y 214 descarta selectivamente a continuación identificadores de paquete y desplaza en el tiempo identificadores de paquete en su salida respectiva.

Haciendo referencia a la figura 6(b), se ilustra otra disposición en la cual dos reguladores/conformadores paralelos 216 y 218 reciben entradas que comprenden identificadores de paquete sobre flujos en las líneas 228 y 230. La salida de los dos reguladores/conformadores 216 y 218 en sus salidas respectivas 238 y 240 forma una entrada a otro regulador/conformador 220. El regulador/conformador 220 da salida a identificadores de paquete sobre la línea

232.

Resultará evidente para los expertos en la materia cómo se pueden disponer en cascada reguladores/conformadores en diversas combinaciones de las disposiciones mostradas en la figura 6. Por ejemplo, las disposiciones de las figuras 6(a) y 6(b) se pueden situar en cascada. Adicionalmente, uno cualquiera de los reguladores/conformadores también puede recibir entradas de otras fuentes. Por ejemplo, el regulador/conformador 212 de la figura 6(a) puede recibir una entrada adicional que no se obtenga a partir de otro regulador/conformador. Los expertos en la materia apreciarán cómo se pueden implementar varias disposiciones en cascada. La única limitación es que los reguladores/conformadores en cascada se deben conectar en un gráfico acíclico.

Al producirse la salida, el regulador/conformador envía tanto el identificador de paquete como su identificador de

10

15

20

25

30

35

40

45

50

55

60

65 E00964487

12-08-2014

cola de espera y clasificación asociados, al multiplexor de acogida/urgencia 106 por medio de una línea de salida respectiva 122. El multiplexor de acogida/urgencia requiere el identificador de paquete, además del identificador de cola de espera, en caso de que deba emitir una instrucción de descarte al gestor de memoria de cola de espera 114, tal como se describirá con mayor detalle a continuación en la presente memoria.

El multiplexor de acogida/urgencia 106 gestiona la contienda por los recursos de la red entre dos o más flujos continuos. El multiplexor de acogida/urgencia 106 recibe identificadores de paquete desde los diversos reguladores/conformadores 104, etiquetándose cada identificador de paquete con una clasificación de acogida/urgencia.

La clasificación de un identificador de paquete define un nivel de acogida y un nivel de urgencia para el paquete al cual está asociado. El multiplexor de acogida/urgencia gestiona la contienda entre dos o más flujos continuos sirviendo paquetes (por medio de sus identificadores de paquete) en función de su nivel de urgencia y, cuando sea necesario, descartando paquetes en función de su nivel de acogida. El nivel de acogida determina qué paquetes entran en el multiplexor de acogida/urgencia. El nivel de urgencia determina el orden en el cual se toman los paquetes del multiplexor de acogida/urgencia. La clasificación de paquetes usando niveles de acogida y de urgencia se describe en la solicitud de patente internacional PCT/GB00/01569 (PWF ref 101926). De este modo, el multiplexor de acogida/urgencia 106 gestiona la contienda entre los tres flujos continuos 122a, 122b y 122c en las salidas de los reguladores/conformadores 104a, 104b y 104c.

Cuando llega un identificador de paquete con su clasificación asociada de acogida/urgencia, el multiplexor de acogida/urgencia 106 determina si el identificador de paquete se debería almacenar o descartar. Esto se determina por la capacidad de almacenamiento disponible en el multiplexor de acogida/urgencia y el nivel de acogida asociado al identificador.

En un método conocido de implementación de la acogida, el acceso a una memoria intermedia en el multiplexor de acogida/urgencia se determina asociando un nivel de acogida a un área particular de la memoria intermedia. Es decir, supóngase que un paquete se puede clasificar como uno cualquiera de N. A continuación, considérese que hay en total KN memorias intermedias. El tráfico de nivel de acogida 1 puede entrar en cualquiera de las KN memorias intermedias, mientras que el tráfico de nivel de acogida i puede entrar únicamente en las primeras KN-i+1 memorias intermedias, donde K0 = 0 <K1< ...<KN. Por lo tanto, los paquetes de nivel de acogida 1 tendrán una probabilidad mayor de hallar recursos disponibles de memoria intermedia que los paquetes de nivel de acogida i, donde i > 1.

También es necesario un esquema para determinar qué identificador de paquete reenviar, es decir, cómo deberían usarse los niveles de urgencia para determinar el orden en el que se sirven paquetes. Un planteamiento consiste en reenviar el identificador en la cabeza de la cola de espera con el nivel de urgencia más alto, aunque son posibles otros planteamientos.

La tasa de pérdidas para identificadores de paquete en un flujo continuo dado viene determinada tanto por el nivel de acogida asignado a los paquetes como por la velocidad de llegada máxima para la totalidad del resto de flujos continuos que tienen un nivel de acogida de igual o mayor valor. El orden en el que se sirven paquetes en el multiplexor de acogida/urgencia depende de sus niveles de urgencia y las velocidades de llegada y patrones de tráfico más urgente. Esto determina el retardo experimentado por el identificador de paquete en el multiplexor de acogida/urgencia.

Si el multiplexor de acogida/urgencia 106 descarta un identificador de paquete, da instrucciones al gestor de memoria de cola de espera, por medio de la línea 136, para decrementar el recuento de referencia correspondiente al paquete apropiado de la memoria de cola de espera 112.

El multiplexor de acogida/urgencia registra estadísticas sobre los flujos de tráfico, incluyendo aunque sin carácter limitativo, el número de los bytes y/o el número de paquetes tanto aceptados como rechazados para cada nivel de urgencia y cada nivel de acogida.

El multiplexor de acogida/urgencia reenvía uno de los identificadores de paquete almacenados junto con su identificador de cola de espera asociado desde sus memorias intermedias internas, al limitador de velocidad 108 sobre la línea 124 como respuesta a una solicitud del limitador de velocidad en la línea 126. La elección del par de identificadores que se reenvía al limitador de velocidad en respuesta a una solicitud del mismo viene determinada por el nivel de urgencia del identificador de paquete y el mecanismo de selección del multiplexor de acogida/urgencia.

En la figura 9 se ilustra una implementación de ejemplo de un multiplexor de acogida/urgencia 106. El multiplexor de acogida/urgencia incluye un bloque de proceso de llegada de acogida/urgencia 801, un conjunto de colas de espera de urgencia 814 que comprenden las colas de espera 802, 805, un bloque de proceso de salida de acogida/urgencia 816, y un bloque de gestión de configuración de acogida/urgencia 807.

10

15

20

25

30

35

40

45

50

55

60

65 E00964487

12-08-2014

Los identificadores de paquete llegan, por medio de la línea 810, al bloque de proceso de llegada de Acogida/Urgencia 801. El bloque de proceso de llegada de Acogida/Urgencia notifica al bloque de gestión de configuración de Acogida/Urgencia 807 que ha llegado un identificador de paquete y reenvía su nivel de acogida por medio de la línea 822. El bloque de gestión de configuración de Acogida/Urgencia 807 solicita la longitud de cada una de las colas de espera de urgencia 802 a 805 por medio de la línea 826. Sobre la base del número total actual de identificadores de paquetes que están en cola de espera en el multiplexor de acogida/urgencia 106 y el nivel de acogida del identificador de paquete, el bloque de gestión de configuración de Acogida/Urgencia determina si descartar o no el paquete.

Si el identificador de paquete se va a descartar, el bloque de gestión de configuración de Acogida/Urgencia 807 notifica de forma correspondiente al proceso de llegada de Acogida/Urgencia 801 por medio de la línea 824. En este caso, el proceso de llegada de Acogida/Urgencia envía una instrucción para descartar el paquete a la memoria de cola de espera por medio de la línea 812, identificando el paquete a descartar por medio de su identificador de paquete y su identificador de cola de espera. A continuación, estos identificadores son descartados por el bloque de proceso de llegada de Acogida/Urgencia 801.

En cualquier otro caso, el bloque de gestión de configuración de Acogida/Urgencia 807 notifica al proceso de llegada de Acogida/Urgencia 801, por medio de la línea 722, que reenvíe el identificador de paquete a una de las colas de espera de urgencia 802 a 805. Existe una cola de espera de urgencia para cada nivel de urgencia. Esta implementación de ejemplo ilustra un multiplexor de acogida/urgencia configurado para cuatro posibles niveles de urgencia. El proceso de llegada de Acogida/Urgencia obtiene el nivel de urgencia para el identificador de paquete y reenvía el identificador de paquete y su identificador de cola de espera asociado, por medio de una de las líneas 830, a la cola de espera de urgencia apropiada.

El bloque de proceso de salida de Acogida/Urgencia 806 recibe, por medio de la línea 818, solicitudes de paquetes provenientes del limitador de velocidad. Cuando llega una solicitud de paquete, el proceso de salida de Acogida/Urgencia solicita el elemento de cabeza de una de las colas de espera de urgencia 802 a 805 por medio de una de las líneas 834. En la forma de realización preferida se solicitarán los identificadores que están en la cabeza de la cola de espera más urgente. El par de identificador de paquete e identificador de cola de espera en la cabeza de la cola de espera que ha recibido la solicitud se reenvía al bloque de proceso de salida de Acogida/Urgencia 806 por medio de una de las líneas 832. El bloque de proceso de salida de Acogida/Urgencia 806 reenvía el par de identificadores inmediatamente al limitador de velocidad por medio de la línea 124.

El limitador de velocidad 108 traslada la contienda desde un punto aguas abajo en la red a dentro del multiplexor limitando la velocidad de servicio a una para la cual la red dispone de recursos suficientes. El limitador de velocidad garantiza que no se supere la velocidad de servicio máxima a largo plazo garantizando que se mantengan espacios apropiados entre paquetes transmitidos.

El limitador de velocidad 108 solicita identificadores de paquete del multiplexor de acogida/urgencia sobre una línea de solicitud 126, y recibe identificadores de paquete junto con sus identificadores de cola de espera asociados sobre la línea 124. Al producirse la recepción del par de identificadores sobre la línea 124, el limitador de velocidad proporciona el identificador de cola de espera sobre la línea 134 al gestor de memoria de cola de espera 114. Como respuesta a ello, el gestor de memoria de cola de espera 114 proporciona el paquete de la cabeza de la cola de espera identificada desde la memoria de cola de espera al limitador de velocidad sobre la línea 132. A continuación el limitador de velocidad reenvía paquetes para su transmisión a la interfaz de salida sobre la línea 128. Al producirse el reenvío de un paquete a la interfaz de salida, el limitador de velocidad ajusta un temporizador para representar el tiempo de servicio del paquete particular con la velocidad configurada. Al final del periodo de temporización asignado al servicio del paquete particular, el limitador de velocidad solicita otro paquete sobre la línea 126, del multiplexor de acogida/urgencia 106.

Si no se ha producido ninguna reordenación en el multiplexor de acogida/urgencia, el paquete enviado desde el gestor de memoria de cola de espera será el mismo paquete identificado por el identificador de paquete. En caso contrario, el identificador de paquete recibido por el limitador de velocidad hará referencia a un paquete que está todavía esperando en la cola de espera de la memoria de cola de espera.

El limitador de velocidad puede servir paquetes de forma estocástica o determinista. Así, el limitador de velocidad puede servir paquetes de tal modo que tengan una separación variable, según se ha descrito anteriormente en la presente en referencia a los reguladores/conformadores.

Una unidad se puede realizar a partir de la combinación de un multiplexor de acogida/urgencia 106 y un limitador de velocidad 108, preferentemente uno que sirva paquetes de forma estocástica. Dichas unidades se pueden disponer en cascada con una pluralidad de reguladores/conformadores y otras unidades de este tipo de limitador de velocidad y de multiplexor de acogida/urgencia, y pueden recibir entradas adicionales de otras fuentes. Los expertos en la materia apreciarán cómo se pueden implementar varias disposiciones en cascada. La única limitación es que la combinación en cascada de estas unidades se debe conectar en un gráfico acíclico.

10

15

20

25

30

35

40

45

E00964487

12-08-2014

Si se usan velocidades de servicio estocásticas, existe el potencial de que la velocidad de servicio muestreada pueda ser mucho mayor que la velocidad con la cual la interfaz de salida puede transmitir físicamente el paquete. En este caso, el tamaño de recurso calculado del paquete será menor que el tamaño real del paquete tal como se ilustra en la figura 5. Haciendo referencia a la figura 5a, en la misma se ilustra en tamaño real del paquete, de acuerdo con la velocidad de transmisión física del medio de transmisión al cual se reenviará el mismo. La figura 5b ilustra el tamaño del paquete en el que la velocidad de servicio escogida para el paquete es mayor que la velocidad con la cual se transmitirá realmente el paquete sobre el medio físico. La figura 5c ilustra el tamaño del paquete en el caso en el que la velocidad de servicio escogida para el paquete sea menor que la velocidad con la cual la interfaz de salida 110 transmitirá realmente el paquete.

Tal como puede observarse a partir de la figura 5, si el tamaño de recurso calculado es realmente menor que el tamaño de recurso real del paquete, los dos paquetes se pueden solapar. En un sistema práctico dos paquetes no se pueden solapar durante la transmisión. Se observará, en cambio, una ráfaga de dos o más paquetes. Por lo tanto, cuando los identificadores de paquete se sirven de manera estocástica, existe una probabilidad finita de que dos o más paquetes se envíen adosados.

La interfaz de salida 110 proporciona una realimentación de control de flujo sobre la línea 130 al limitador de velocidad 108. Si la interfaz de salida indica al limitador de velocidad que se ha suspendido la transmisión, el mecanismo de temporización interno del limitador de velocidad se ve afectado. En este caso, el limitador de velocidad puede llevar a cabo una de varias acciones. Por ejemplo, el limitador de velocidad se puede configurar para descartar cualquier paquete que se haya planificado servir durante el periodo de suspensión. Dicho descarte de paquetes por el limitador de velocidad requiere que el limitador de velocidad genere una señal de alarma.

El limitador de velocidad 108 también se puede optimizar para maximizar el recurso del sistema externo con una carga baja. Es decir, con cargas bajas, la velocidad de servicio se puede escoger de manera que sea mayor que la velocidad configurada. A medida que aumenta la carga sobre el sistema, la velocidad de servicio se reducirá hasta que la misma esté próxima a la velocidad configurada o sea esta última.

La interfaz de salida 110 proporciona la funcionalidad básica necesaria para la transmisión hacia delante de paquetes de datos. La interfaz de salida 110 proporciona una realimentación de control de flujo sobre las líneas 130 al limitador de velocidad 108 cuando se produce cierta resistencia externa (por ejemplo, desde el medio de transmisión). De este modo, la interfaz de salida transmite paquetes sobre la línea 142, y recibe señales de control de flujo sobre la línea 144 desde el sistema operativo o el controlador de dispositivo.

La interfaz de salida no es responsable de ningún procesado directo en relación con la gestión de calidad del flujo continuo de datos. Si la interfaz de salida recibe un paquete y el sistema o dispositivo externo indica que tiene recursos disponibles para la transmisión, entonces el paquete es transmitido por la interfaz de salida sin ningún retardo. Si el limitador de velocidad está funcionando en modo determinista y no se ha ejercido ningún control de flujo, en un momento dado no habrá nunca más de un paquete en la memoria intermedia de la interfaz de salida.

De este modo, se ha descrito una invención que se puede utilizar ventajosamente en un multiplexor para garantizar una calidad de servicio predeterminada. Aunque la invención se ha descrito en la presente memoria haciendo referencia a una forma de realización ejemplificativa particular, los expertos en la materia apreciarán que la invención no resulta limitada por ello en cuanto a su aplicabilidad, y se puede aplicar de forma más general.

Claims (16)

1. E00964487

   12-08-2014

   REIVINDICACIONES

   1. Método de control de un flujo de información en un sistema de transmisión de datos, que comprende: recibir una

   pluralidad de paquetes de datos (116) con una velocidad de muestras recibidas, presentando cada uno de ellos una 5 longitud de paquete físico recibido; caracterizado porque presenta la etapa de:

   determinar una velocidad de servicio para cada uno de los paquetes;

   para cada paquete, asignar una longitud de paquete conceptual para el paquete, siendo la longitud de paquete

   10 conceptual un tiempo de servicio para el paquete, basándose en la velocidad de servicio determinada para el paquete y en la longitud de paquete físico del paquete; y

   planificar cada paquete en función de la longitud de paquete conceptual respectiva.

   15 2. Método según la reivindicación 1, en el que la longitud de paquete conceptual es menor que la longitud de paquete físico recibido.
2. 3. Método según la reivindicación 1, en el que la longitud de paquete conceptual es mayor que la longitud de

   paquete físico recibido. 20

3. 4.

   Método según cualquiera de las reivindicaciones 1 a 3, que comprende además la etapa de generar un flujo de información modificado en el que la separación entre paquetes es variable.

4. 5.

   Método de control de una pluralidad de flujos de información paralelos según cualquiera de las reivindicaciones 1

   25 a 4, en el que se genera una pluralidad de flujos de información modificados, presentando cada uno de ellos una velocidad de servicio determinada para cada paquete.
5. 6. Método según la reivindicación 5, que comprende además la etapa de multiplexar la pluralidad de flujos de

   información modificados. 30
6. 7. Método según cualquiera de las reivindicaciones 1 a 6, en el que los paquetes recibidos en un flujo de información se admiten en una cola de espera, dependiendo la probabilidad de que un paquete entre en la cola de espera de la longitud de la cola de espera.

   35 8. Método según la reivindicación 7, en el que la probabilidad de que un paquete sea admitido en la cola de espera depende de la longitud de la cola de espera.
7. 9. Método según la reivindicación 7, en el que la probabilidad de que un paquete ya presente en la cola de espera

   sea descartado para permitir la admisión del paquete recibido depende de la longitud de la cola de espera. 40
8. 10. Método según cualquiera de las reivindicaciones 7 a 9, en el que un nivel de servicio se asocia a cada paquete en la cola de espera, determinándose el nivel de servicio por la longitud de la cola de espera.
9. 11. Método según la reivindicación 10, en el que el nivel de servicio se controla controlando las admisiones de 45 paquetes en la cola de espera.
10. 12. Método según cualquiera de las reivindicaciones 1 a 11, que comprende además asignar un nivel de prioridad a cada paquete.

    50 13. Método según la reivindicación 12, en el que se sirven paquetes dependiendo del nivel de prioridad asignado.
11. 14. Método según la reivindicación 12 o 13, en el que el nivel de prioridad incluye una indicación de una urgencia asociada al paquete y un nivel de pérdida que se puede tolerar para el paquete.

    55 15. Método según cualquiera de las reivindicaciones 12 a 14, cuando están subordinadas a cualquiera de las reivindicaciones 7 a 9, en el que el nivel de prioridad se asigna a un paquete sobre la base de una función del estado de la cola de espera.
12. 16. Método según cualquiera de las reivindicaciones 6 a 15, en el que, si la longitud de paquete conceptual de un

    60 paquete es tal que se asigna una separación negativa entre dos paquetes, los dos paquetes se multiplexan de manera adyacente.
13. 17. Controlador para controlar un flujo de información en un sistema de transmisión de datos, que comprende: unos

    medios de entrada (100) para recibir una pluralidad de paquetes de datos con una velocidad de muestras recibidas, 65 presentando cada paquete una longitud de paquete físico recibido; caracterizado porque presenta:

    14 E00964487

    12-08-2014

    unos medios de asignación (108) para asignar para cada paquete una longitud de paquete conceptual, siendo la longitud de paquete conceptual un tiempo de servicio para el paquete, sobre la base de una velocidad de servicio determinada para el paquete y de la longitud de paquete físico del paquete; y

    5 unos medios de salida (110) para dar salida a los paquetes, planificándose cada paquete dependiendo de la longitud de paquete conceptual respectiva.
14. 18. Controlador según la reivindicación 17, que incluye además unos medios de modificación para generar un flujo

    de información modificado en el que los paquetes están separados de manera variable. 10

15. 19.

    Controlador según la reivindicación 18, en el que los medios de modificación comprenden un modulador.

16. 20.

    Controlador según cualquiera de las reivindicaciones 17 a 19, que incluye además un multiplexor para

    multiplexar una pluralidad de flujos de información que presentan paquetes con una velocidad de servicio. 15

    15