Un procedimiento para controlar la admisión de un flujo a una red y una red.

Un procedimiento para controlar la admisión de un flujo a una red,

particularmente una red WiMAX, Interoperabilidad mundial para acceso por microondas, en el que se llevará a cabo una estimación de capacidad máxima requerida dentro de un enlace de la red y/o dentro de la red para examinar, si se puede admitir el flujo que pide entrar en la red con al menos una reserva de recursos de QoS, Calidad de servicio, hallando conjuntos de intersecciones entre todos los pares de reservas de QoS, es decir las reservas de QoS ya aceptadas dentro del enlace y/o dentro de la red y la al menos una reserva de QoS requerida por el flujo, mediante el algoritmo Diofántico para proporcionar conjuntos de intersecciones hallados,

caracterizado por estructurar los conjuntos de intersecciones hallados construyendo una matriz de intersecciones de reservas de QoS, en el que la construcción de la matriz se llevará a cabo cruzando para cada par de reservas el conjunto de intersecciones hallado, y

- en base a dicha matriz - deducir el resto de los conjuntos de intersecciones entre las intersecciones halladas, en base a la información obtenida con respecto a las reservas de QoS implicadas en cada intersección, en el que el resto de los conjuntos de intersecciones se deducirán cruzando para cada reserva la matriz de intersecciones y descartando soluciones no posibles aplicando las siguientes Condiciones 1 y 2:

Condición 1: Para cualquier par de conjuntos de intersecciones hallados, se cruzarán entre ellos si ambas soluciones tienen una reserva en común y las otras dos reservas se cruzan entre sí, y

Condición 2: Para cualquier conjunto de intersecciones hallado, se cruzará con otro conjunto de intersecciones si y sólo si todas las reservas implicadas en ambos conjuntos de intersecciones se cruzan las unas con las otras.

Un procedimiento para controlar la admisión de un flujo a una red y una red.

Las investigaciones que llevan a los resultados dados a conocer en la presente solicitud han recibido fondos del Séptimo programa marco de la Unión Europea (FP7f2007-2013) bajo el contrato de subvención nO 214994

La presente invención se refiere a un procedimiento para controlar la admisión de un flujo a una red de acuerdo con el preámbulo de la reivindicación 1

Asimismo, la presente invención se refiere a una red de acuerdo con el preámbulo de la reivindicación 14.

Tal procedimiento y red se conocen por el documento US-2009f0116384-A1 .

Se conocen procedimientos adicionales para controlar la admisión de un flujo a una red y redes correspondientes. Particularmente las redes WiMAX están proporcionando una importante futura tecnología inalámbrica de banda ancha que se explica en el Grupo de trabajo IEEE 802.16, "IEEE Standard for Local and Metropolitan Area Nelworks. Part 16: Air Interface for Broadband Wireless Access Systems", Norma IEEE 802.16-2009, mayo de 2009. En base al concepto de OFDMA (Acceso múltiple por división de frecuencia ortogonal) , permite que los proveedores de servicios soporten una variedad de aplicaciones en tiempo no real y en tiempo real en diversos entornos móviles y fijos. En WiMAX, se pueden asignar aplicaciones a cualquiera de los diversos servicios de programación que proporcionan diferentes garantías de QoS. Por ejemplo, servicios como UGS (Servicio no solicitado de concesión) proporcionan firmes garantías de CoS mientras que otros como rtPS y nrtPS (Servicios de sondeo en tiempo real y en tiempo no real) proporcionan unos niveles de CoS menos estrictos; finalmente, BE (Mejor esfuerzo) no ofrece ninguna garantía. Cumplir con los requisitos de CoS de las demandas de servicios concedidos es obligatorio para los proveedores de servicios lo cual requiere estimar con exactitud la capacidad del sistema. Las técnicas de estimación de capacidad precisa permiten el diseño de algoritmos o procedimientos de control de admisión eficientes La literatura actual acerca del control de admisión para WiMAX propone una amplia variedad de opciones que consiguen niveles muy diferentes de exactitud así como carga computacional. De H. Wang, W. Lí, y O.P. Agrawal, "Dynamic Admission Control and CoS tor 802.16 Wireless MAN", en Proceeding of Wireless Telecommunications Symposium (WTS) , Pomona, EEUU, abril de 2005 es obtenible un planteamiento simple que se basa principalmente en la tasa media de datos que una aplicación especifica como demanda. Con tal conocimiento, se pueden admitir

progresivamente conexiones de diferentes servicios en el sistema WiMAX siguiendo un orden de prioridad predeterminado. Tal planteamiento requiere pocos recursos computacionales; sin embargo, no tiene en consideración la naturaleza variable en el tiempo de las aplicaciones típicas como video o voz con detección de actividad ni el periodo de tiempo en el que estos recursos son requeridos. De ese modo, los recursos reales disponibles podrían no usarse. Esta solución se puede ver como el peor de los casos.

Un planteamiento diferente se propone en A. Teh y P. Pudney, "Efficient Admission Control Based on Predicted Traffic Characteristics", en Proceeding of Personallndoor Mobile Radio Communications (PIMRC) , Atenas, Grecia, septiembre de 2007 donde la varianza de los requisitos de ancho de banda de un flujo se propone como una estadística que mejor describe los requisitos de las aplicaciones. Sin embargo, no hay ninguna prueba de que la 45 varianza sea un buen descriptor para todos los tipos de tráfico. Los autores extienden aún más este procedimiento en A. Teh, A. Jayasuriya, y P. Pudney, "Admission Control in Wireless Infrastructure Nelworks Based on the Predicted Percentage of Delayed Packets", en Proceeding of Asia-Pacific Conference on Communications (APCC) , Tokio, Japón, octubre de 2008 donde tienen en cuenta la fracción predicha de paquetes retardados por encima de un umbral. Tal conocimiento se puede usar entonces para evaluar si se puede cumplir con los requisitos de CoS

para un flujo particular.

De S. Ghazal, Y.H. Aoul, J.B. Othman, y F. Nait-Abdesselam, "Applying a Self-Configuring Admission Control Algorithm in a New CoS Architecture for IEEE 802.16 Nelworks", en Proceedings of IEEE Symposium on Computers and Communications (ISCC) , Marrakech, Marruecos, julio de 2008 es obtenible un controlador basado en la lógica 55 difusa para predecir la probabilidad de bloqueo de un flujo particular. Se explica que la naturaleza variable de las aplicaciones en tiempo real se puede tomar en consideración mediante un controlador 'basado en reglas' Sin embargo, se asume que aún se requiere la validación extendida de tal controlador frente a diversos tipos de tráfico Finalmente, de O. Yang y J. Lu, "Call Admission Control and Scheduling Schemes with QoS support for Real-time Video Applications in IEEE 802.16 Nelworks", en IEEE Journal of Multimedia, mayo de 2006 es obtenible un algoritmo de control de admisión exacto para flujos de vídeo que tiene en cuenta los requisitos tanto de producción como de retardo. Sin embargo, este planteamiento no se puede usar en la práctica debido a su carga computacional y por lo tanto, se necesita una alternativa.

Las redes WiMAX soportan la reserva de recursos de QoS permitiendo que un nuevo flujo solicite la admisión en el sistema a través de un mensaje de petición de Adición de servicio dinámica (DSA-REQ) . Tales peticiones contienen un conjunto de parámetros de QoS que incluye diferente información obligatoria dependiendo del servicio pedido. En base a estos parámetros, para cada reserva i un conjunto mínimo de requisitos de QoS se puede deducir para un servicio como: dado un tiempo de inicio ti, una cierta cantidad de capacidad B¡ (bits) se debería reservar

periódicamente para transmitir datos i del flujo dentro de un intervalo de tiempo Ti.

Considerando una nueva reserva i que pide aceptación en el sistema, un algoritmo o procedimiento de control de admisión tiene que evaluar si hay capacidad suficiente disponible en la red para cumplir con el requisito de nueva reserva mientras aún se cumplen los acuerdos de QoS de las reservas ya aceptadas. Tal petición se puede modelar

como una secuencia discreta periódica de deltas de kronecker con amplitud B i del siguiente modo si t=t¡+n· 7; , donde n E Z de lo contrario (1 )

Asumiendo un sistema WiMAX con una capacidad disponible para datos con requisitos de QoS Cav y N reservas ya 20 aceptadas, se puede aceptar una nueva reserva i en la red si se cumple la siguiente condición (2)

donde A (t) corresponde a la amplitud de la envolvente de la señal formada por la combinación de las reservas de los N flujos admitidos en el sistema más el que pide la admisión.

Se conocen los siguientes procedimientos para la estimación de la capacidad máxima requerida dentro de un enlace de la red y/o dentro de la red '

A. Peor caso Con el fin de determinar max (A (t) ) se pueden considerar diferentes planteamientos La aproximación más fácil pero más pesimista, denominada en lo sucesivo Peor caso, sería asumir que todas las reservas admitidas necesitan servirse simultáneamente, es decir, sin tener en cuenta el tiempo en el que los flujos realmente necesitan servirse.

N I]

A_ _= (t) =B¡

j =l

(3)

Tal planteamiento es similar al descrito en H. Wang, W. Lí, y D.P Agrawal, "Dynamic Admission Control and QoS for

802.16 Wireless MAN", en Proceeding ofWireless Telecommunications Symposium (WTS) , Pomona, EEUU, abril de 2005. Este planteamiento podría dar como resultado que una gran porción de capacidad disponible se infrautilizara.

B. Heurístico 45 Una solución exacta para A (t) se puede obtener computando todos los valores de A (t) dentro de su periodo, véase la Ecuación 4. Obsérvese que ya que A (t) está compuesta de N+1 reservas periódicas, su periodo corresponde al Mínimo común múltiplo (MCM) de los periodos de las reservas. Este planteamiento se denominará en el resto de este documento Heurístico N+] MCM

A".../mro (t) =L: L: Bj o (t)

j d 1=0

(4)

El planteamiento Heurístico tiene una dependencia con el MCM de las reservas en el sistema que, dependiendo de 5 la granularidad permitida para tales periodos, podría aumentar exponencialmente con el número de reservas y por lo tanto pasar a ser muy caro en términos computacionales _Por lo tanto, tal solución podria no ser viable en la práctica C. Diofántico Con el fin de eliminar la dependencia del MCM con el planteamiento Heurístico, se considera otra solución en base a la teoría Diofántica que, en general, maneja... [Seguir leyendo]

1. Un procedimiento para controlar la admisión de un flujo a una red, particularmente una red WiMAX, Interoperabilidad mundial para acceso por microondas, en el que se llevará a cabo una estimación de capacidad máxima requerida dentro de un enlace de la red y/o dentro de la red para examinar, si se puede admitir el flujo que pide entrar en la red con al menos una reserva de recursos de 00$, Calidad de servicio, hallando conjuntos de intersecciones entre todos los pares de reservas de 00$, es decir las reservas de OoS ya aceptadas dentro del enlace y/o dentro de la red y la al menos una reserva de 00$ requerida por el flujo, mediante el algoritmo Diofántico para proporcionar conjuntos de intersecciones hallados,

caracterizado por estructurar los conjuntos de intersecciones hallados construyendo una matriz de intersecciones de reservas de 00$, en el que la construcción de la matriz se llevará a cabo cruzando para cada par de reservas el conjunto de intersecciones hallado, y

-en base a dicha matriz -deducir el resto de los conjuntos de intersecciones entre las intersecciones halladas, en base a la información obtenida con respecto a las reservas de 00$ implicadas en cada intersección, en el que el resto de los conjuntos de intersecciones se deducirán cruzando para cada reserva la matriz de intersecciones y descartando soluciones no posibles aplicando las siguientes Condiciones 1 y 2:

Condición 1: Para cualquier par de conjuntos de intersecciones hallados, se cruzarán entre ellos si ambas soluciones tienen una reserva en común y las otras dos reservas se cruzan entre si, y

Condición 2: Para cualquier conjunto de intersecciones hallado, se cruzará con otro conjunto de intersecciones si y sólo si todas las reservas implicadas en ambos conjuntos de intersecciones se cruzan las unas con las otras.

2. Un procedimiento de acuerdo con la reivindicación 1, en el que la capacidad requerida hace referencia a requisitos de ancho de banda.

3. Un procedimiento de acuerdo con las reivindicaciones 1 ó 2, en el que la construcción de la matriz se llevará a cabo bajo el uso de la teoria de las ecuaciones diofánticas lineales.

4. Un procedimiento de acuerdo con una de las reivindicaciones 1 a 3, en el que la deducción del resto de los conjuntos de intersecciones producirá un árbol de soluciones que tiene ramificaciones de soluciones.

5. Un procedimiento de acuerdo con la reivindicación 4, en el que las ramificaciones de soluciones se ordenarán en orden descendente de acuerdo con su valor máximo potencial y se finalizará una exploración de las ramificaciones cuando se halle una solución sin requerirse una exploración total de las ramificaciones o

en el que las ramificaciones de soluciones se explorarán sólo parcialmente de acuerdo con una politica específica para el equilibro entre la exactitud y el tiempo computacional, por ejemplo la exploración sólo de un porcentaje definible del número total de ramificaciones con la mayor probabilidad de contener la capacidad máxima.

6. Un procedimiento de acuerdo con una de las reivindicaciones 1 a S, en el que los requisitos de ancho de banda Bi se modelan como múltiplos de un requisito de ancho de banda predefinible B re! Yuna reserva mayor de Brel se modelará como las reservas de B/ Brel.

7. Un procedimiento de acuerdo con una de las reivindicaciones 1 a 6, en el que dentro de un caso de repetidores de múltiples saltos un flujo entrante de una MR-B$ (Estación base de repetidores de múltiples saltos) o RS (Estación repetidora) a una siguiente RS podría ser considerado como un flujo que pide entrar en la red con al menos una reserva de recursos de OoS.

8. Un proced imiento de acuerdo con la reivindicación 7, en el que -cuando un flujo pide entrar en la redel procedimiento comprende el paso de determinar si un destino, en el caso de una petición de enlace descendente,

o una fuente, en el caso de una petición de enlace ascendente, se asocian a una RS, yen tal caso el procedimiento comprende además el paso de considerar el flujo para la estimación de la capacidad máxima.

9. Un procedimiento de acuerdo con la reivindicación 7 u 8, en el que, si una R$ está implicada, una estimación de la capacidad máxima requerida se llevará a cabo para todas las BSs y RSs implicadas en una trayectoria de flujo desde una fuente hasta su destino.

10. Un procedimiento de acuerdo con la reivindicación 9, en el que la estimación de la capacidad máxima requerida se llevará a cabo secuencialmente paso a paso.

11. Un procedimiento de acuerdo con la reivindicación 10, en el que la petición será rechazada, si en algún paso la capacidad máxima requerida está por encima de un valor de una capacidad máxima disponible.

12. Un procedimiento de acuerdo con una de las reivindicaciones 7 a 11, en el que en cada paso o salto adicional un tiempo de inicio de reserva se incrementará un número entero de duración de las tramas WiMAX o cualquier otro número arbitrario de acuerdo con las capacidades de procesamiento de las MR-BS y/o RSs.

13. Un procedimiento de acuerdo con una de las reivindicaciones 1 a 12, en el que un valor de una capacidad máxima disponible en un enlace y/o en la red se definirá por un operador o en base a la política de un operador.

14. Una red, particularmente una red WiMAX, Interoperabilidad mundial para acceso por microondas, en el que se llevará a cabo una estimación de capacidad máxima requerida dentro de un enlace de la red y/o dentro de la red para examinar, si se puede admitir el flujo que pide entrar en la red con al menos una reserva de recursos de OoS, Calidad de servicio, hallando conjuntos de intersecciones entre todos los pares de reservas de OoS, es decir las reservas de QoS ya aceptadas dentro del enlace y/o dentro de la red y la al menos una reserva de QoS requerida por el flujo, mediante el algoritmo Diofántico para proporcionar conjuntos de intersecciones hallados,

caracterizado porque la red comprende medios para estructurar los conjuntos de intersecciones hallados adaptados para construir una matriz de intersecciones de reservas de OoS, en el que la construcción de la matriz se llevará a cabo cruzando para cada par de reservas el conjunto de intersecciones hallado, y

medios para -en base a dicha matriz -deducir el resto de los conjuntos de intersecciones entre las intersecciones halladas, en base a la información obtenida con respecto a las reservas de OOS implicadas en cada intersección, en el Que el resto de los conjuntos de intersecciones se deducirán cruzando para cada reserva la matriz de intersecciones y descartando soluciones no posibles aplicando las siguientes Condiciones 1 y 2:

Condición 1: Para cualquier par de conjuntos de intersecciones hallados, se cruzarán entre ellos si ambas soluciones tienen una reserva en común y las otras dos reservas se cruzan entre si, y

Condición 2: Para cualquier conjunto de intersecciones hallado, se cruzará con otro conjunto de intersecciones si y sólo si todas las reservas implicadas en ambos conjuntos de intersecciones se cruzan las unas con las otras.