Modelado y Análisis Transitorio de un Sistema de Distribución de Vídeo bajo Demanda Isabel Martín1, 2, Juan José Alins1, Mónica Aguilar1, Reinaldo Vallejos2, Luis J. De la Cruz1, Jorge Mata1 2 Departamento de Electrónica. Universidad Técnica Federico Santa María. Avenida España 1680, Valparaíso, Chile. E-mail:
[email protected] 1 Departamento de Ingeniería Telemática. Universitat Politècnica de Catalunya C/ Jordi Girona 1-3, Mód. C3, Campus Nord, 08034 Barcelona. E-mail: {isabelm, juanjo, maguilar, ljcruz, jmata}@mat.upc.es Abstract. The dramatic growth of Internet and the need of certain Quality of Service (QoS) guarantees of the video-streaming applications make necessary to ensure end-to-end QoS. This paper presents a tool to evaluate the performance of a video-streaming system. This tool provides an estimated QoS given to the user in the connection moment, thus the user can decide to accept or to reject its service demand. Moreover, the system could charge the clients for a tightly service, meanwhile making efficient use of the available bandwidth. In this paper, the analyzed video-streaming architecture is composed of three elements: the MPEG video encoder, the traffic shaper and the supervisor and controller subsystem. It supplies smoothing and control functions to provide a guaranteed QoS over an open broadband network like Internet.
1 Introducción El fuerte crecimiento que ha experimentado Internet en los últimos años ha llevado al desarrollo de nuevas aplicaciones con requisitos de Calidad de Servicio (QoS) de diversos grados, según el tipo de aplicación desarrollada y el servicio ofrecido. La actual Internet sólo ofrece un servicio best-effort, insatisfactorio como infraestructura comercial en la que se está transformando. Como ejemplo, cada vez son más los usuarios dispuestos a pagar por obtener servicios multimedia bajo demanda y casi bajo demanda, con requisitos de tiempo real y con cierto grado de QoS. Para poder distribuir eficientemente estos flujos multimedia y proveer QoS, durante los últimos años se han desarrollado muchos protocolos, en especial los que proporcionan soporte a los requisitos de tiempo real de las aplicaciones. Una de las aplicaciones que se han desarrollado con más énfasis, debido a la demanda y buena aceptación entre el conjunto general de usuarios, son las aplicaciones para la transmisión y distribución de flujos multimedia (video y audio) bajo demanda para su reproducción en tiempo real (video-streaming). Decodificador Q . . .
Control Codificador
Codificador
Control de Tasa
cliente 1 . . .
RED Decodificador
Servidor de video cliente 2
Figura 1. Sistema de distribución de video para su reproducción en tiempo real (video streaming).
En la Fig. 1 se presenta el esquema de un sistema video streaming. El servidor de video dispone de un conjunto de películas, que pueden ser solicitadas por cualquiera de los clientes. Si la solicitud de conexión
es aceptada, se da origen a un flujo de información a través de la red, desde el servidor de video hasta el cliente. Cada fuente de video (película que está siendo transmitida por el servidor de video) genera una gran cantidad de información, lo que hace necesario usar técnicas de compresión, como se representa con el bloque “Codificador” de la Fig. 1. El estándar MPEG-2 es ampliamente reconocido para la codificación de flujos que se transmiten sobre redes de comunicación. Este tipo de flujo presenta una gran variabilidad, producida por factores como el algoritmo de codificación utilizado y por la propia complejidad de las secuencias a codificar. Si la codificación se realiza en modo tasa variable (Variable Bit Rate, VBR) se dificulta la gestión de la red, dada la característica de gran variabilidad en la tasa de transmisión del tráfico VBR. En general, una forma de asegurar un cierto grado de calidad de servicio, durante todo el tiempo de conexión, es asignar los recursos necesarios para la transmisión de los instantes de máxima exigencia del tráfico, en el momento de conexión. Para el tráfico VBR esta opción no es eficiente desde el punto de vista de la red, debido a que durante gran parte del tiempo de transmisión la conexión no estará en la condición de máxima exigencia y, por lo tanto, esos recursos estarán siendo subutilizados. Dada la alta exigencia de recursos de los flujos de video, el número de conexiones compartiendo los recursos es pequeño, por lo que la multiplexación estadística pierde su beneficio. Por este motivo, surgen propuestas para controlar la tasa de codificación, y asignar los recursos de red en forma dinámica. Tienen especial interés aquellas aplicaciones capaces de adaptar su tasa de transmisión en función del estado de la red, reduciendo la calidad del flujo emitido en caso de congestión (bloque “Control Codificador” de la Fig. 1).
En la literatura se pueden encontrar diversas propuestas para modelar y evaluar el rendimiento de este tipo de sistemas, tanto en régimen transitorio como estacionario. El objetivo principal es poder predecir la influencia que tiene el tráfico generado por las aplicaciones, en los recursos de la red y la calidad de servicio que se le entrega al usuario. Dos propuestas de especial interés para el desarrollo del presente trabajo, son [1] y [2]. En la primera, se propone un modelo de Proceso de Fluido Modulado por Markov (Markov Modulated Fluid Process, MMFP) bidimensional para modelar el tráfico MPEG-VBR. Este modelo es el proceso agregado de dos tipos de minifuentes ON-OFF, que permiten capturar la característica de dependencia a corto y largo plazo del tráfico de video. Y en la segunda, en base a este modelo, se propone un método de asignación dinámica de recursos de la red. Para evaluar las prestaciones del sistema de distribución de video, se propone utilizar herramientas que provienen del área de investigación denominada Prestabilidad (Performability), concepto que integra los aspectos de Prestaciones y Disponibilidad (Performance y Dependability) [4]. En particular, se propone utilizar un modelo de Cadenas de Markov con Recompensas (CMR) y la técnica de Uniformización (o randomización). Esta metodología se utiliza ampliamente en el área de Prestabilidad; por ejemplo, en [3, 8] se aplica a modelado de tráfico, y en [6] para evaluar un algoritmo de control de admisión de conexión. Una de las medidas que permite obtener esta metodología es una estimación de la QoS que el usuario percibe durante el tiempo en que se le está ofreciendo el servicio. Una utilidad de esta medida es entregar al usuario una estimación de la QoS que le puede ofrecer el sistema desde ese momento hasta que finalice la transmisión de la película solicitada. Este servicio puede ser muy atractivo para el usuario, dado que puede aceptar o rechazar la conexión según sea la QoS que se le ofrece. Por otro lado, desde el punto de vista del proveedor, ésta medida puede permitir un servicio de tarificación variable al usuario y por tanto ajustada al servicio ofrecido. Para los sistemas en que está implementado algún método de reserva de recursos, la aceptación de una conexión supone el compromiso, por parte de la red, de mantener una cierta calidad al usuario acotando el valor de algunos parámetros de QoS, es decir de unas medidas objetivas (retardo, pérdidas, etc) que no reflejan todas las métricas de calidad de video (VQM, Video Quality Metrics) del flujo transmitido. Debido al mecanismo de renegociación de recursos implementado en el sistema evaluado, en este trabajo es relevante obtener una medida de la calidad de codificación del flujo entregado, dado que el sistema emite flujos de diferentes calidades a lo largo de la transmisión. La valoración final de QoS puede corresponder a una función que relacione diferentes medidas objetivas de VQM con la percepción subjetiva que tiene el usuario (VQM subjetivas).
El resto de este trabajo está organizado de la siguiente manera: La sección 2 presenta el modelo que describe el funcionamiento del sistema a evaluar. En la sección 3 se resuelve el modelo mediante herramientas de evaluación de prestabilidad. A continuación, en la sección 4 se presentan algunos resultados numéricos contrastados con mediciones experimentales, obtenidas en la plataforma del proyecto SSADE [7] implementado por el grupo de investigación Servicios Telemáticos de la Universidad Politécnica de Cataluña. Finalmente, en la sección 5 se presentan las conclusiones.
2 Modelo del sistema. El sistema que se modela y analiza en este trabajo, considera las características del sistema de distribución de vídeo bajo demanda SSADE [7]. El flujo de información se codifica con el algoritmo MPEG-2 en modo VBR (Variable Bit Rate). Para reducir la dificultad de la red en transmitir este tipo de tráfico de forma eficiente, se agrega al sistema un mecanismo de suavizado del flujo y un mecanismo de asignación dinámica de recursos de la red. Se dispone de más de un flujo de video, codificado con diferente valor del parámetro de cuantización (Q) y, por tanto, con diferente calidad. Ello permite variar la tasa de transmisión según los recursos disponibles en la red. Se supone que todos los flujos multimedia están almacenados en el servidor de video, por lo que se tiene un completo conocimiento estadístico de su comportamiento. Esto permite obtener los valores empíricos que se requieren para definir los parámetros del modelo de tráfico de cada flujo. Así mismo, permite obtener una métrica de la calidad del flujo, que en el modelo propuesto se considera constante para cada secuencia VBR. En esta sección se describen los modelos de tráfico y de asignación dinámica de recursos de red utilizados para representar el funcionamiento del sistema global que se ha evaluado.
2.1 Modelo de Tráfico El modelo de tráfico de una fuente MPEG VBR que se ha considerado en este trabajo es un modelo de fluidos modulado por un proceso de Markov (Markov Modulated Fluid Process, MMFP) bidimensional, tal como se propone y analiza en [1]. Este modelo se compone de la agregación de dos tipos de fuentes simples ON-OFF. tasa3,1
tasa3 2
tasa3,3
tasa3,4
tasa3,5
tasa3,6
tasa2,3
tasa2,4
tasa2 5
tasa2,6
S2d=2d
c
tasa2,1 S2c=2c
tasa2 2 d S1a=5a
tasa 1,1
4a
b
3a tasa1,3
tasa1,2 2b
2a tasa1,4
3b
a tasa1,5
4b
Figura 2a. Modelo de tráfico.
tasa1,6 S1b=5b
2.2 Asignación Dinámica de Recursos de la Red
Actividad Alta
2d
c
Actividad Media
d
2c Actividad Baja
Figura 2b. Modelo del nivel de actividad.
En la Fig. 2a se muestra el diagrama de este modelo, donde cada estado corresponde a un valor de la tasa de transmisión de la secuencia de video. Las transiciones entre estados ocurren cuando se activa o desactiva alguna de las minifuentes ON-OFF. El tiempo entre transiciones de cada minifuente está distribuido exponencialmente. S1 y S2 son la cantidad de minifuentes de cada tipo y, como se demuestra en [1], en general se obtiene un buen ajuste de cualquier secuencia de video MPEG VBR con S1 igual a 5 (o 6) y S2 igual a 2. En la Fig. 2b se muestran tres niveles de actividad (Alto, Medio, Bajo) para el tráfico de video MPEG VBR (determinados por el estado de las dos minifuentes de tipo 2, S2). El tiempo de permanencia en estos tres niveles de actividad captura la relación temporal a largo plazo de la generación de tráfico y viene condicionado por las tasas de transición de las minifuentes de tipo 2 [2]. La transición entre estos niveles de actividad modela los posibles cambios significativos de actividad que se producen en una secuencia de video. Uno de los parámetros de codificación que más influye en la tasa media del flujo, es el parámetro de nivel de cuantización, Q. En [5] se comprueba empíricamente que al comparar las características de una secuencia de video codificada con distintos Q, la forma de los flujos resultantes (subidas y bajadas del nivel de actividad) se mantiene muy semejante entre un flujo y otro, siendo la tasa media del flujo mayor cuanto menor es el valor del parámetro Q. Esto quiere decir que en el modelo MMFP bidimensional de una secuencia de video, el valor de la tasa de transmisión de cada uno de los flujos obtenidos de codificar esa secuencia con distinto Q, sólo se verá modificado por un factor proporcional y las tasas de transición entre estados se considera que son las mismas. Para garantizar un determinado nivel de QoS en la transmisión de un flujo completo, con una asignación estática de recursos de la red, el sistema debe asignar los recursos que necesite el nivel Alto de actividad de dicho flujo. La mayor parte del tiempo el flujo estará en el nivel Bajo de actividad, eventualmente saltará al nivel Medio y en pocas ocasiones saltará al nivel Alto de actividad. Por lo tanto, la identificación de los intervalos de tiempo durante los cuales el flujo está en cada uno de esos tres niveles de actividad, permite llevar a cabo un mecanismo de asignación más eficiente de los recursos de red. Esta asignación es dinámica, según el mecanismo de renegociación de recursos de red propuesto en [2], que se describe a continuación.
Con el objetivo de asegurar un determinado nivel de calidad en la transmisión de un flujo de información por la red, se implementan mecanismos o protocolos que permiten hacer una reserva de recursos de la red. Cada aplicación determina cuándo y qué parámetros enviará al protocolo de reserva de recursos para solicitar recursos de red. El sistema reserva los recursos necesarios para limitar las pérdidas y el retardo sufridos en la transmisión. Debido a la exigencia de mínimo retardo que requieren los servicios de distribución de video en tiempo real (longitudes de memorias pequeñas y fijas) en este estudio se considera que los recursos necesarios de red sólo están condicionados por el ancho de banda (BW) que el servicio de video reserva para la conexión del usuario. Para aceptar un nuevo usuario, se necesita determinar la cantidad de recursos (BW) requeridos para la nueva conexión y si el sistema es capaz de proporcionárselos. Este BW está limitado por la tasa de la red de acceso a la que está conectado el terminal del usuario y por el BW que facilita la red al sistema de distribución de video. El primero es un dato propio del usuario, que debe comunicar al sistema en el momento en que solicita la conexión. El sistema rechaza la conexión del nuevo usuario si su tasa de conexión es inferior al mínimo BW requerido por la conexión. Si el usuario dispone de suficiente BW en la red de acceso para recibir el servicio de video y tiene contratada reserva de recursos, el sistema invocará al protocolo de reserva de recursos. El bloque “Control de Codificación” de la Fig. 1 controla la petición de recursos de la red y el valor de los parámetros de codificación. El sistema formulará nuevas peticiones a la red para incrementar gradualmente la calidad del flujo transmitido. Para transmitir una película con reserva de recursos, el sistema acepta la conexión del nuevo usuario si puede asignarle suficiente BW para asegurar la transmisión del flujo menos exigente de la película solicitada. Este mínimo BW requerido es igual a la tasa del nivel más alto de actividad del flujo de menor tasa media de la película solicitada (el flujo de menor calidad de codificación). El mecanismo de reserva de recursos implementado es el propuesto en [2], que en líneas generales sigue las siguientes pautas de funcionamiento: -
-
El sistema acepta la conexión de un usuario si puede hacer la reserva de recursos requerida para asegurar la transmisión del flujo de video menos exigente (menor tasa media, menor calidad de codificación) disponible de la película solicitada. Durante la transmisión, el sistema siempre intenta mejorar la calidad del flujo a transmitir (mayor tasa media, menor Q de codificación). Para esto, realiza una renegociación de reserva
-
-
cada cierto intervalo de tiempo (la longitud adecuada de este intervalo depende de las características del flujo) solicitando los recursos necesarios para transmitir el flujo de la siguiente mejor calidad disponible (en el mismo nivel de actividad en que se encuentra). Si el flujo de la película en curso cambia a un nivel de actividad más alto, el sistema procede a enviar un flujo de calidad igual o inferior, bajará la calidad hasta que los recursos que tiene asignado en la reserva actual sean suficientes. Si el flujo de la película en curso cambia a un nivel de actividad más bajo, puede seguir enviando el flujo con la misma calidad, ya que requiere menos recursos que los asignados actualmente. En caso de que estos recursos asignados también sean suficientes para transmitir el flujo de la siguiente mejor calidad, puede aumentar de calidad. En cualquiera de los dos casos, los recursos excedentes se liberan inmediatamente.
Nótese que este sistema reserva recursos a cada conexión en la medida en que están disponibles, siempre intentando mejorar el servicio, pero también liberando los recursos que el usuario no está utilizando.
2.3 Modelo para una conexión En esta sección se presenta el modelo analítico para el funcionamiento del sistema de distribución de video descrito, que permite obtener medidas de su rendimiento. e1A
e2A
e3A
N i v e l a c t i v i d a d
conexión (en el momento de la renegociación) recursos suficientes para estar en el estado e. Sea PRS' (e af , e af '' ) un factor que indica si los recursos ya asignados a la conexión (en el estado e af ) son suficientes para que la conexión transite al estado eaf '' . Por lo tanto, PRS' (e af , e af '' ) = 1 si los recursos requeridos para que la conexión transmita el flujo de calidad f y nivel de actividad a son mayores o iguales a los requeridos para que la conexión transmita el flujo de calidad f’ y nivel de actividad a’; y PRS' (e af , e af '' ) = 0 en caso contrario. En el sistema, el tiempo entre renegociaciones está distribuido exponencialmente con una tasa λR . Las tasas de activación y desactivación de las minifuentes ON-OFF que modelan el tráfico, son c y d respectivamente. Sea λ (e1 , e2 ) la tasa de transición desde el estado e1 al estado e2 . A continuación se definen las tasas de transición λ (e1 , e2 ) de la Fig. 3, para PRS (e1 ) = 1 . Las transiciones ocurridas en los instantes de renegociación son:
λ (e af , e af +1 ) = λR ·PRS (e af +1 ) , para a = A, M, B y f = 1,2. Las transiciones ocurridas por una disminución en el nivel de actividad del flujo son:
λ (e Af , e Mf +1 ) = 2·d ·PRS' (e Af , e Mf +1 ) y
λ (e Af , e Mf ) = 2·d ·PRS' (e Af , e Mf +1 ) , para f = 1, 2. λ (e Mf , e Bf +1 ) = d ·PRS' (e Mf , e Bf +1 ) y
λ (e Mf , e Bf ) = d ·PRS' (e Mf , e Bf +1 ) , para f = 1, 2. e1M
e2M
e3M
λ (e3A , e3M ) = 2·d y λ (e3M , e3B ) = d . Las transiciones ocurridas por un aumento en el nivel de actividad del flujo son:
e1B
e2B
e3B
calidad flujo
Figura 3. Modelo comportamiento 1 conexión en el sistema.
En la Fig. 3 se presenta el diagrama de estados que modela el comportamiento de una conexión (flujo de video) aceptada en el sistema, y se muestran las transiciones debidas al comportamiento de una determinada conexión. Se considera que en cada conexión se puede estar transmitiendo un flujo entre 3 posibles calidades de codificación, cada una con 3 posibles niveles de actividad. Sea e af un estado del sistema, que representa la situación en la cual la conexión en observación está transmitiendo un flujo de calidad f (1: baja, 2: media, 3: alta) y en nivel de actividad a (B: bajo, M: medio, A: alto). Sea PRS (e) un factor que indica la posibilidad de que el sistema asigne a la
λ (e1B , e1M ) = 2·c , λ (e1M , e1A ) = c , B M ' λ (e2 , e2 ) = 2·c·PRS (e2B , e2M ) ,
λ (e2M , e1A ) = c ,
λ (e2B , e1M ) = 2·c·PRS' (e2B , e2M ) , λ (e3B , e3M ) = 2·c·PRS' (e3B , e3M ) , λ (e3B , e2M ) = 2·c·PRS' (e3B , e3M )·PRS' (e3B , e2M ) , λ (e3B , e1M ) = 2·c·PRS' (e3B , e3M )·PRS' (e3B , e2M ) ,
λ (e3M , e2A ) = c·PRS' (e3M , e2A ) , λ (e3M , e1A ) = c·PRS' (e3M , e2A ) . Nótese que tanto PRS (e) como PRS' (e1 , e2 ) no son probabilidades, sino factores que permiten expresar en forma general el modelo, y que dependen de los recursos totales del sistema y las características particulares de los flujos, respectivamente. Los factores PRS (e) , indican la existencia o no del estado e en el sistema; es decir, PRS (e) = 0 significa que el sistema no puede estar en el estado e porque nunca
existen los recursos suficientes y PRS (e) = 1 significa que el sistema puede transitar al estado e (cuando sucede una renegociación) porque existen los recursos suficientes para aceptar la reserva de recursos. Asimismo, en los casos en que una transición ocurre hacia un nivel más bajo de actividad los factores PRS' (e1 , e2 ) indican el hecho de que los recursos actualmente asignados son suficientes para transmitir un flujo de mayor calidad y en un nivel de actividad más bajo. Esta situación se puede presentar por dos motivos: Por un lado, los recursos requeridos para transmitir cierto nivel de actividad pueden ser numéricamente mayor o igual a los requeridos para transmitir un nivel más bajo de actividad del flujo en una calidad superior (indicados en la Fig. 3 con líneas segmentadas descendientes); y por otro lado, el sistema reserva (como mínimo) los recursos requeridos para transmitir el flujo de menor calidad en el nivel de máxima actividad. Este último motivo también da lugar a las posibles transiciones hacia niveles más altos de actividad en la misma calidad de flujo. Por último, cuando hay un aumento en el nivel de actividad de un flujo, se pasa a transmitir el flujo de la mejor calidad posible que permitan los recursos asignados actualmente.
2.4 Modelo para N Conexiones El modelo de la sección anterior (Fig. 3) permite entender el comportamiento del flujo de una sola conexión en el sistema. Ahora, se propone el modelo del sistema para las N conexiones aceptadas en el sistema. Sea S = { ( n1B , n1M , n1A ) , ( n2B , n2M , n2A ) , ( n3B , n3M , n3A ) } el estado del sistema donde cada componente ( naf ) es la cantidad de conexiones transmitiendo un flujo de calidad f y en nivel de actividad a. Por lo tanto, si hay N conexiones aceptadas dentro del sistema se tiene que: ∑ ∑ n af = N . Sea S+(f,a)-(f’,a’) un estado del ∀a
∀f
S + (2,a )− (1,a )
S + (2, M ) −(1, A)
S + (1, A) −(2,M )
S + (1, M ) − (1, A)
S + (1, A) − (1, M ) S + (2, A) − (3,M )
S + (3,M ) −(2, A)
de diferentes calidades de flujo. Dada la complejidad de dibujar el espacio de estados completo del sistema, en la Fig. 4 se representan las transiciones desde y hacia un estado S cualquiera del sistema. Los dos estados de salida de S ubicados en la zona superior de la Fig. 4, S+(2,a)-(1,a) y S+(3,a)-(2,a) (a = B, M, A), representan los estados a los que transitaría el sistema cuando se acepta una renegociación de reserva de recursos. Los estados ubicados en la zona derecha de la Fig. 4 corresponden a los cambios de estado debido a que alguna de las conexiones ha subido de actividad. Y los estados en la zona izquierda, corresponden a los cambios de estado debido a que el tráfico de alguna de las conexiones ha bajado de nivel de actividad. En las tasas de transición del modelo, que se propone a continuación, se ha considerado que todas las conexiones están transmitiendo tráfico que tiene las mismas tasas de transición de las minifuentes ONOFF que lo modelan (c, d: tasas de activación y desactivación de una minifuente, respectivamente). Entonces, las tasas de transición desde el estado S (con PRS ( S ) = 1 ) a los estados S+(f1,a1)-(f2,a2), λ(S, S+(f1,a1)-(f2,a2)), son las siguientes. Tasas de transición del estado S a los estados posteriores a una renegociación aceptada:
λ ( S , S + (3,a )−(2,a ) ) = n2a ·λR ·PRS ( S+ (3,a )−(2,a ) ) , a = A, M, B . Tasas de transición del estado S a los estados en que una de las conexiones ha disminuido la actividad del flujo:
S + (1, A) − (3, M )
λ ( S , S + (2, M ) − (1, A) ) = n1A ·2·d ·PRS' (e1A , e2M ) ,
S + (1,M ) −(3, B )
λ ( S , S + (1, M ) − (1, A) ) = n1A ·2·d ·PRS' (e1A , e2M ) ,
S
S + (3,M ) −(3, A)
Si los recursos totales del sistema son suficientes para que las N conexiones estén transmitiendo la máxima calidad en el nivel de actividad máximo, esto es el estado S = {(0,0,0), (0,0,0), (0,0,N)}, el espacio de estados del sistema es de ( N + 8)!/( N !8!) . En general, la máxima cantidad de estados del sistema es ( N + 3mf −1)!/( N !(3mf −1)!) , donde mf es la cantidad
λ ( S , S+ (2,a )−(1,a ) ) = n1a ·λR ·PRS ( S+ (2,a )−(1,a ) ) ,
S + (3,a ) −(2,a )
S + (2, M ) −(2, A)
sistema en que se tiene una conexión más respecto del estado S, trasmitiendo un flujo de calidad f en nivel de actividad a; y una conexión menos, trasmitiendo un flujo de calidad f’ en nivel de actividad a’.
λ ( S , S + (3, M ) − (2, A) ) = n2A ·2·d ·PRS' (e2A , e3M ) ,
S + (2, B ) −(1,M )
S + (1, M ) −(2, B )
S + (1, B ) −(1, M )
S + (1, M ) −(1, B )
S + (3, B ) −(2,M )
S + (2, M ) − (3, B )
λ ( S , S + (2, B ) − (1, M ) ) = n1M ·d ·PRS' (e1M , e2B ) ,
S + (2, B ) −(2, M )
S + (2,M ) −(2, B )
λ ( S , S + (1, B ) − (1, M ) ) = n1M ·d ·PRS' (e1M , e2B ) ,
S + (3, B ) −(3, M )
S + (3,M ) −(3, B )
Figura 4. Modelo comportamiento N conexiones en el sistema.
λ ( S , S + (2, M ) − (2, A) ) = n2A ·2·d ·PRS' (e2A , e3M ) , λ ( S , S + (3, M ) − (3, A) ) = n3A ·2·d ,
λ ( S , S + (3, B ) − (2, M ) ) = n2M ·d ·PRS' (e2M , e3B ) ,
λ ( S , S + (2, B ) − (2, M ) ) = n2M ·d ·PRS' (e2M , e3B ) ,
λ ( S , S + (3, B ) − (3, M ) ) = n3M ·d . Análogamente, tasas de transición del estado S a los estados en que una de las conexiones ha aumentado la actividad del flujo:
λ ( S , S + (1, A) −(1, M ) ) = n1M ·c ,
λ ( S , S + (1, A ) − ( 2, M ) ) = n2M ·c ,
λ ( S , S + (2, A) −(3, M ) ) = n ·c·P (e , e ) , M 3
' RS
M 3
A 2
λ ( S , S + (1, A ) − (3, M ) ) = n3M ·c·PRS' (e3M , e2A ) , λ ( S , S + (1, M ) − (3, B ) ) = n3M ·2·c·PRS' (e3B , e3M ) PRS' (e3B , e2M ) λ ( S , S + (1, M ) − (2, B ) ) = n2B ·2·c·PRS' (e2B , e2M ) , λ ( S , S + (1, M ) − (1, B ) ) = n1B ·2·c ,
λ ( S , S + (2, M ) − (3, B ) ) = n3B ·2·c·PRS' (e3B , e3M ) PRS' (e3B , e2M ) λ ( S , S + (2, M ) − (2, B ) ) = n2B ·2·c·PRS' (e2B , e2M ) , λ ( S , S + (3, M ) − (3, B ) ) = n3B ·2·c·PRS' (e3B , e3M ) . Los factores
PRS (e) y PRS' (e1 , e2 ) expresados de la siguiente forma:
pueden ser
1 , si ∑∑ n af ·RS af < RStotal PRS ( S ) = ∀f ∀ a 0 , en otro caso.
(1)
1 , si RS af ≥ RS af '' PRS' (e af , e af '' ) = 0 , en otro caso.
(2)
Donde RS af representa la cantidad de recursos de la red que el sistema reserva a una conexión para transmitir un flujo de calidad f a un nivel de actividad a; y RStotal es la cantidad total de recursos de la red que el servicio dispone para todas las conexiones. El punto restrictivo de estos recursos se encuentra en el nodo de acceso a la red. Si se desprecia el requerimiento de memoria, RS total es igual a la capacidad total de BW del servicio en el nodo de acceso. Debido al requerimiento de asegurar la transmisión del flujo de mínima calidad, a RS af = max { RS1A , rs af } donde rs f es la mínima cantidad de recursos de red que una conexión requiere para transmitir un flujo de calidad f a un nivel de actividad a.
3 Solución del Modelo. En la sección 2.4 se ha establecido un modelo estocástico del sistema, específicamente una Cadena de Markov de Tiempo Continuo (CMTC), dado que el tiempo de permanencia en cada estado del sistema tiene distribución exponencial. En esta sección se presenta un método de solución de este modelo con el objetivo de obtener medidas de rendimiento del sistema. Obtener una solución de esta CMTC mediante un conjunto de ecuaciones diferenciales, es una tarea extremadamente ardua, además del elevado costo en cálculo numérico. Como alternativa, se propone una metodología ampliamente utilizada en el área de
investigación de Prestabilidad. Esto es, utilizar un modelo de Cadenas de Markov con Recompensas (CMR) y la técnica de Uniformización. En [4] se encuentra la descripción de esta metodología, que se resume a continuación. Para modelar el sistema mediante CMR, a cada estado del sistema se le asocia una recompensa. En el caso de una CMTC, esta recompensa es la ganancia de la medida objeto de la evaluación mientras permanece en un cierto estado del sistema. Así, el valor de recompensa asociado a un estado corresponde a la medida de prestación (performance) del sistema por cada unidad de tiempo en que el sistema se encuentre en dicho estado. Por lo tanto, la definición de estado debe ser tal que para cada uno de estos estados se pueda asociar un único valor de tasa de recompensa. Para resolver este modelo de CMR, una técnica frecuentemente utilizada es la uniformización, que consiste en una transformación de un problema presentado en términos de una cadena de Markov en tiempo continuo a una solución en tiempo discreto. Esta transformación facilita los cálculos numéricos para obtener soluciones transitorias. La uniformización se describe formalmente como sigue. Considere una CMTC X ={X(t): t ≥ 0} con espacio de estados finito S y generador infinitesimal Q = [qij]. Sea Z ={Zn, n = 0, 1, …}una CM de tiempo discreto (CMTD) con espacio de estados finito S y matriz de probabilidad de transición P = I + Q/Λ, donde Λ ≥ maxi{|qii|}, y sea N = {N(t): t ≥ 0} un proceso de Poisson de parámetro Λt el cual es independiente de Z. Entonces, se puede interpretar que X(t) = ZN(t) para t ≥ 0. Sea p(t) un vector cuya i-ésima entrada es la probabilidad de que la CMTC X esté en el estado i en el tiempo t dada una distribución inicial. Sea v(n) = v(0)Pn un vector cuya j-ésima entrada es la probabilidad de que la CMTD Z esté en el estado j después de n transiciones, donde v(0) es el vector de probabilidad inicial. Entonces, la ecuación básica del método de uniformización es: ∞
p (t ) = ∑ e −Λt n =0
( Λt ) n v ( n) n!
(3)
Para calcular (3), es necesario truncar el sumatorio infinito en un cierto número N de términos. Donde, para cualquier componente de p(t), el error está dado n N por ε ( N ) ≤ 1 − e −Λt (Λt ) .
∑
n!
n =0
Sea r = [r1, r2, …,rM] el vector de tasas de recompensas asociadas al espacio de estados S, y sea ER(t) la recompensa esperada en el tiempo t. Utilizando la ecuación (3) (en [4], ec. (3.8)), ER(t) se expresa como: ∞
ER(t ) = ∑ e−Λt n =0
( Λt ) n {r · v(n)} n!
(4)
Donde r · v (n) = ∑ M ri ·vi (n) . Sean M(t) la recompensa i =1 acumulada en el intervalo (0, t) y EM(t) el valor esperado de M(t). A partir de (4) y simples argumentos probabilísticos se puede demostrar que EM(t) es (en [4], ec. (3.10)): ∞
EM (t ) = t ∑ e n=0
−Λt
n (Λt ) n ∑ j =0 {r · v (n)} (5) n! n +1
∑ {r · v(n)} , f ( n) = n
Donde
j =0
puede ser calculado
n +1 {r · v(n)} . n como f (n) = f (n − 1) + n +1 n +1
Otra medida de interés es la función de distribución (FDP) de M(t), Pr{M(t) ≤ m}, que en la literatura es la más conocida como medida de performability. El cálculo eficiente de esta ecuación no es tan simple como el de (5). En [9] se presenta la solución general que actualmente mejor realiza este cálculo en forma eficiente y numéricamente estable. En resumen, modelando el sistema con CMR y utilizando la técnica de uniformización, se obtiene un método simple para obtener más de una medida de rendimiento del sistema, simplemente definiendo adecuadamente la estructura de recompensas del sistema. Por ejemplo, a continuación se presenta una de las medidas de interés en el sistema de nuestro análisis, esto es la QoS definida por la calidad de codificación del flujo que se está transmitiendo al usuario.
3.1 Medida de QoS de un usuario en el sistema No es objetivo de este trabajo definir una función de relación entre medidas objetivas y subjetivas de VQM. Sin embargo, algunos parámetros cuya influencia en la calidad del video que percibe el usuario es conocida, son la pérdida de paquetes y el retardo de los mismos, que en el caso de reserva de recursos son parámetros acotados. El parámetro que principalmente influirá en la degradación producida por la codificación del video, es el parámetro de cuantización Q (el cual influye directamente en la relación señal-ruido, PSNR [5]). Por lo tanto, una buena aproximación de esta QoS es la determinada por la PSNR (o el parámetro de cuantización (Q)) del flujo codificado, o bien una función que relacione más de una VQM objetiva en un valor de VQM subjetiva. Antes de definir la estructura de recompensas que nos permitirá obtener esta medida de QoS con un modelo de CMR, se hará una integración de los modelos presentados en las secciones 2.3 y 2.4. Sea S%= { u af , a f
S}, donde u describe el estado de la conexión de un usuario en observación, esto es, la conexión está transmitiendo un flujo de calidad f en un nivel de actividad a, y S describe el estado del resto de las
conexiones en el sistema (ver definición de S en la sección 2.4). Las tasas de transición de un estado { u af , S } a un estado { u af , S’} son las definidas en la sección 2.4, y las tasas de transición de un estado { u af , S } a un estado { u af '' , S } son las definidas en la sección 2.3. Esta definición permite asociar un único valor de recompensa a cada estado para la medida en particular de QoS de un usuario dado. Así, a cada estado S% = { u af , S} se le asocia una recompensa r(S%) igual a la valoración de la calidad de codificación del flujo de calidad f, Qf . Sea QoSi(T) la QoS entregada al usuario, acumulada durante el intervalo T (tiempo duración de película) de duración de la conexión, dado que el sistema le puede asignar los recursos mínimos necesarios y al inicio de su conexión el estado del sistema es i. Entonces se estima el valor medio de QoS que el sistema podría ofrecerle durante el siguiente intervalo de tiempo T, esto es el cálculo del valor esperado de QoSi(T)/T. Se considera que el número de usuarios total dentro del sistema se mantiene constante durante T. Finalmente, se interpreta el valor numérico de E{QoSi(T)/T} con una calificación cualitativa (por ejemplo: Platino, Oro, Plata o Bronce) para informar al usuario.
4 Resultados numéricos En los ejemplos numéricos que se presentan a continuación, se ha evaluado el sistema con 4 calidades de flujo (Q = 17, 10, 6 y 4) de la secuencia completa de la película Matrix. Los valores de los parámetros del modelo de tráfico de cada uno de estos flujos han sido obtenidos empíricamente y a priori ya que son propios de la secuencia. Así mismo, a cada flujo se le ha asociado como valor de QoS (recompensa en el modelo CMR) el valor medio de PSNR medido a lo largo de la secuencia. La Fig. 5 muestra la traza de los 4 flujos en un intervalo de la secuencia. La traza resaltada en negrilla es el flujo efectivamente transmitido por el sistema, que se
segundos
Figura 5. Traza real de película Matrix codificada en MPEG2.
corresponde con una u otra calidad de flujo durante distintos intervalos. La Fig. 6 representa la QoS obtenida en función de la cantidad de recursos disponibles. La λR considerada
es igual a 1 renegociación/seg.. El mínimo BW necesario para aceptar la conexión es de 1’732 Mbps. (igual a la tasa máxima del flujo de peor calidad). El máximo BW representado corresponde a la tasa máxima del flujo de mejor calidad. El valor de QoS representado está normalizando respecto de los valores de PSNR máximo y mínimo que ofrece el sistema. Se aprecia como la QoS estimada aumenta a medida que se incrementan los recursos disponibles. Las discontinuidades se producen en aquellos valores de recursos de red que pasan a ser suficientes para un cambio a un flujo de mejor calidad. En concreto, cerca de un valor de 2’5 Mbps de BW disponible hay un cambio significativo en la QoS ofrecida (alcanza el nivel de actividad bajo –donde la secuencia permanece habitualmente- de un flujo de calidad superior). Qo S 1
Qo S en funció n del B W
en función del parámetro Q. Para obtener medidas de rendimiento del sistema, se ha propuesto un modelo analítico basado en CMR. La solución propuesta ha sido programada en ordenador. En particular se ha obtenido la QoS definida por la calidad de codificación del flujo que se está transmitiendo al usuario. Se ha validado el modelo propuesto contrastando con los valores obtenidos en la plataforma SSADE, obteniéndose valores muy semejantes. Cabe señalar que se encuentra en desarrollo la extensión del modelo para ser incorporada la variación de N durante el tiempo de transmisión (llegada y salida de usuarios del sistema).
Agradecimientos Este trabajo ha sido financiado por los proyectos de investigación DISQET (CICYT TIC2002-00818), CREDO (CICYT TIC2002-00249), y proyecto FONDECYT (1000055/2000-CONICYT).
Referencias
0,8
[1] L. J. De la Cruz, M. Fernández, J. Alins, J. Mata “Bidimensional Fluid Model for VBR MPEG Video Traffic”. Broadband Communications: The future of telecommunications, IFIP 1997.
0,6 0,4 0,2 B W(Kbps)
0 1732
2799
3866
4933
6000
Figura 6. QoS estimada a 1 conexión en función del BW disponible en el servidor de video.
La Fig. 7 representa la QoS obtenida en función de la tasa media de renegociación del algoritmo de asignación dinámica de recursos. El BW total considerado es igual a 3Mbps. Se observa que a partir de un valor de λR=0’048 renegociaciones/seg. se consigue una QoS cercana al 90%. QoS 1
Qo S en funció n de la tasa renego ciació n
[2] L. J. De la Cruz, J. Mata, “Performanace of Dynamic Resource Allocation with QoS Guarantees for MPEG VBR Video Traffic Transmission over ATM Networks”. Proc. Of IEEE GLOBECOM99, Brasil, 1999. [3] E. de Souza e Silva, R. M. M. Leao, M. Diniz. “Transient Analysis Applied to Traffic Modeling”. ACM SIGMETRICS Performance Evaluation Review, Vol. 28, I. 4, Marzo 2001. [4] B. R. Haverkort, R. Marie, G. Rubino, K. Trivedi (editores), “Performability Modelling. Techniques and Tools“, John Wiley & Sons, ISBN: 047149195-0, 2001. [5] J. Mata. “Contribución a la Gestión Dinámica de Recursos Aplicada al Control de Fuentes de Video de Velocidad Variable en la Red Digital de Servicios Integrados de Banda Ancha”. Tesis Ph.D, U. Politécnica de Cataluña, 1996.
0,8 0,6 0,4 0,2 0 0
0,12
0,24
0,36
0,48
0,6
tasa renegociación (1/seg.)
Figura 7. QoS estimada a una conexión en función de la Tasa de Renegociación en el servidor de video.
5 Conclusiones En este trabajo se ha propuesto un mecanismo de evaluación de las prestaciones de un sistema videostreaming que tiene implementado un mecanismo de asignación dinámica de recursos de red. La QoS ofrecida al usuario depende principalmente de la calidad del flujo transmitido (medida por la PSNR de la imagen), degradada por el proceso de codificación
[6] J. F. Meyer, “Performability of an Algorithm for Connection Admission Control”, IEEE Transac. on Computers, Vol.50 Nº 7: 724-733, 2001. [7] SSADE, Sistema Seguro de Acceso y Distribución Eficiente de Servicios Multimedia, CYCIT TEL 99-0322, http://ssade.upc.es. [8] B. Sericola. “Transient Analysis of Stochastic Fluid Models”. Publication interne nº 1099, INRIA, Campus de Beaulieu, 35042 Rennes Cédex, France, Avril 1997. [9] H.Nabli and B. Sericola. “Performability Analysis: A New Algorithm”. IEEE Transaction on Computers, vol. 45, Nº 4, April 1996.
