Evaluación de un Servicio Video-Streaming Utilizando Modelos Markovianos con Recompensas Isabel V. Martín Faus Dpto. Ingeniería Telemática Univ. Politèc. de Catalunya
Juan José Alins Delgado Dpto. Ingeniería Telemática Univ. Politèc. de Catalunya
Mónica Aguilar Igartua Dpto. Ingeniería Telemática Univ. Politèc. de Catalunya
Jorge Mata Díaz Dpto. Ingeniería Telemática Univ. Politèc. de Catalunya
[email protected]
[email protected]
[email protected]
[email protected]
Abstract- In this work we propose a methodology to obtain analytical models for the traffic generated from a Video on Demand service (VoD) system that adapts their transmission rate to the network conditions. The model has a direct relation with the design and operation of the VoD system, which implies to easily incorporate system modifications. It is a simple analytic model, computationally evaluated that allows obtaining a priori measures of the system performance, as the PSNR, effective bandwidth and reserved bandwidth. To allow this, we have used well-known methods used in Performability analysis [1]: we have modelled the VoD system with a Markov-Rewards Chain; and to solve it, we have used the randomization technique (or uniformization). The model is flexible enough to compute a wide range of Service Level Agreements parameters. The numerical results have been compared with the ones obtained from the testbed of the laboratory platform SSADE http://ssade.upc.es /, showing a good adjustment for the mean value evaluations of diverse performance evaluation measures of the VoD systems. I.
INTRODUCCIÓN
En los últimos años las aplicaciones para la transmisión y distribución de video bajo demanda (VoD) han experimentado un creciente desarrollo y aceptación por parte de los usuarios. En particular, los sistemas de distribución de video para su reproducción en tiempo real, video-streaming [2]. En 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 de comunicación, desde el servidor de video hasta el cliente. Para disminuir la elevada cantidad de información que genera una fuente de video (película que está siendo transmitida por el servidor de video), se utilizan técnicas de compresión como el estándar MPEG-II, a costa de una degradación en la calidad de video. La calidad de servicio (QoS) que se ofrece al usuario depende de la relación entre los recursos de red disponibles y los requeridos para transmitir el flujo. Esta relación afecta a medidas del sistema como pérdida y retardo de paquetes. El flujo MPEG-II VBR presenta gran variabilidad en la tasa de transmisión, producida por factores como el algorit mo de codificación utilizado y la propia complejidad de las secuencias de video (películas) a codificar. En este escenario, crece la importancia de diseñar fuentes de video capaces de adaptarse a las condiciones de la red durante la
transmisión. Algunas propuestas de diseño y evaluación de sistemas VoD adaptativos son [3, 4, 5, 6, 7]. Sin embargo, en la mayoría de éstas, la evaluación de medidas de rendimiento del sistema propuesto se realiza con modelos de simulación, plataformas reales o no modelan la interacción entre las diversas fuentes de video multiplexadas (compartiendo los recursos de red). Tampoco las diversas propuestas para caracterizar y modelar flujos de video como [8, 9, 10] son suficientes por sí mismas, para modelar un sistema videostreaming adaptativo donde, para cada conexión aceptada se transmiten diferentes flujos (con diferentes calidades de la secuencia solicitada) a lo largo del tiempo. Así, actualmente existe una carencia de métodos o herramientas analíticas, evaluables computacionalmente y flexibles, que permitan estudiar el diseño y dimensionado de estos VoD de manera global. Tanto los proveedores de servicios como sus usuarios están interesados en disponer de estas herramientas y medidas que permitan cuantificar el rendimiento del sistema desde diversos puntos de vista. Entre otros objetivos, se requiere: maximizar la utilización de recursos de red, maximizar la QoS que se ofrece a los usuarios, definir métricas de tarificación. Además, estos son necesarios para definir, gestionar y controlar el cumplimiento de contratos a nivel de servicio (Service Level Agreement, SLA). SLA es un tema actual en la investigación de servicios multimedia y de gran interés comercial. Existen diversas propuestas recientes sobre SLA [11, 12], aunque ninguna especifica cómo evaluar numéricamente los parámetros SLA que proponen. Uno de los principales objetivos de este trabajo, es evaluar a priori la QoS ofrecida al usuario (PSNR, recursos reservados, recursos efectivamente utilizados, entre otros parámetros) de una aplicación video-streaming que adapte la tasa de transmisión según la caracterización de la secuencia y los recursos de red disponibles durante la transmisión. Este trabajo se destaca, respecto a otras propuestas publicadas, por obtener un modelo que tiene una directa interpretación con el diseño y funcionamiento global del servicio VoD, esto permite en forma fácil incorporar modificaciones en el sistema. Además, el modelo considera la interacción entre las diversas conexiones multiplexadas (compartiendo los recursos).
II. DESCRIPCIÓN DEL SISTEMA El sistema VoD analizado en este trabajo se muestra en la Fig. 1. El servidor almacena un conjunto de flujos de video para cada secuencia, previamente codificada utilizando MPEG-II VBR con diferentes calidades (p. ej., diferentes valores del parámetro paso de cuantización Q). La transmisión de una secuencia requiere diferentes recursos de red a lo largo de toda la sesión según la complejidad de la secuencia Este trabajo ha sido financiado por el proyecto DISQET (CICYT codificada. Esos requerimientos son asociados con las escenas TIC2002-00818, España), CREDO (CICYT TIC2002-00249, de la película. El sistema utiliza el protocolo RSVP para la
España)
señalización y administración de reserva de recursos. Para cada conexión aceptada por el servidor, se transmiten diferentes flujos (con diferentes calidades y tasas de transmisión) en los distintos intervalos de tiempo. El flujo que se transmite se elige adaptándose al nivel de QoS que se desea entregar al usuario y a las respuestas obtenidas de las peticiones de recursos de red. Los recursos disponibles en la red cambian debido a la interacción entre las conexiones de video multiplexadas. El bloque Planificador Estadístico de la Fig. 1, almacena previamente los parámetros de especificación de tráfico (Tspec) de cada escena y los momentos de renegociación. El bloque Regulador/Negociador, decide qué calidad del flujo (Q) se va a transmitir, en los instantes de cambio de escena o cambio de disponibilidad de recursos. Para garantizar una calidad mínima, las peticiones de recursos deben asegurar siempre una reserva mínima. El bloque Suavizador transmite a una tasa constante, rGoP , durante cada GoP (Group of Picture), realizando así un suavizado del tráfico. Las características de los mecanismos implementados en el servidor de video (en particular, los valores obtenidos de la segmentación y la renegociación), el conjunto de calidades de flujos disponibles y el perfil de cada cliente (conexión), determinan la forma de los streams enviados y, por ende la eficiencia del sistema y la QoS que será entregada a los clientes de video.
Figura 1. Modelo del sistema evaluado. III. PRELIMINARES DEL MODELO
Como punto de partida para la confección del modelo analítico propuesto en este trabajo, se parte de la caracterización de las escenas de un flujo de video a través de un modelo markoviano simple derivado de [9]. Este modelo se compone de tres estados que definen la actividad de la tasa binaria en función de la complejidad de las escenas de un flujo de video con una calidad de imagen prefijada. Por lo tanto, las transiciones entre estos estados caracterizan los posibles cambios significativos de actividad en la tasa binaria de las escenas . En adelante, denominaremos a estos estados como niveles de actividad. IV. MODELO ANALÍTICO
En esta sección resumimos la propuesta para construir un modelo analítico que represente el comportamiento del tráfico generado por las conexiones aceptadas en un sistema VoD, como el descrito en la sección II. Los detalles de cada paso de construcción se pueden encontrar en [13]. La metodología genérica de construcción consiste en los siguientes pasos: 1) Establecimiento de un modelo markoviano que caracterice los recursos requeridos por cada flujo disponible. 2) Integración de los modelos establecidos en 1), agregando las transiciones entre flujos que reflejan las decisiones (elecciones de calidades de flujos) del
mecanismo de renegociación. Así se obtiene el modelo para una conexión. 3) Agregación de estados para el caso de N conexiones en el sistema. Esto es, el estado del sistema es definido por cuántas conexiones están en cada uno de los estados ya definidos en el modelo de una conexión (establecido en 2)). Así se obtiene el modelo del tráfico agregado generado por N conexiones aceptadas en el VoD. Este modelo permite obtener medidas globales de funcionamiento del VoD, considerando la interacción entre las conexiones. 4) Evaluación de medidas de un usuario particular en interacción con otras N conexiones. Para ello se propone la integración del modelo de 1) y el modelo de 2). Así 1) representa el estado de la conexión de interés y 2) el estado de las otras N conexiones. El resultado de estos pasos es la obtención de una cadena de Markov de tiempo continuo (CMTC). Luego, para obtener medidas de QoS en el VoD a partir de esta CMTC, de forma computacionalmente evaluable, se propone utilizar metodologías clásicas en el área de Prestabilidad (Performability). Primero, se asigna a cada estado de la CMTC el valor de eficiencia (Performance) asociada al sistema mientras permanece en dicho estado (tasa de recompensa), obteniéndose una cadena de Markov con recompensas (Markov-Reward Chain, MRC). Luego, se aplica la técnica de randomización (también llamada uniformización) que consiste en la transformación de un proceso continuo en uno discreto. Una extensa descripción de esta metodología se encuentra en [1]. Utilizando esta metodología genérica de construcción y solución del modelo y eligiendo otras opciones de diseño (diferentes a las elegidas en este trabajo) se puede modelar diferentes sistemas VoD y obtener diversas medidas de interés del sistema. Algunos ejemplos de estas medidas son: • Esperanza del valor acumulado, EM(t). Es la esperanza de una medida acumulada M(t). Nos permite, por ejemplo, obtener la esperanza de la cantidad total de bits transmitidos a un usuario durante su tiempo conexión. La recompensa es la tasa de bits asociada a cada estado y t es el tiempo de conexión. (La ecuación 3.10 en [1] permite la evaluación numérica de EM(t)). • Tiempo en fallo. Un fallo en nuestro sistema se define como el incumplimiento de algún parámetro de la QoS contratada. Entonces las medidas relacionadas con el tiempo de fallo se obtienen asignando una estructura de recompensas tal que: si el estado del sistema está en fallo (la medida del sistema en tal estado es inferior a la deseada o contratada) se le asigna una recompensa igual a 1; en caso contrario, la recompensa asignada es 0. La esperanza del tiempo en fallo se calcula con la ecuación de EM(t) aplicando esta estructura de recompensas. • Función de distribución de probabilidad (FDP) del tiempo de fallo. Esta medida puede ser interpretada como la probabilidad de cumplimiento del contrato del servicio. Sea P {M (t ) < u} la probabilidad de que el tiempo total (acumulado durante un intervalo de tiempo de servicio t ) en que el sistema no cumple la QoS contratada por el usuario, no supere un umbral u. Entonces , debemos aplicar la misma estructura de recompensas presentada para el tiempo de fallo. Una solución eficiente de para evaluar numéricamente P {M (t ) < u} se encuentra en [14].
A. Ejemplo de Modelo En el paso 1), el modelo más simple es definir un estado para cada nivel de actividad del modelo de segmentación. Como ejemplo, en la Fig. 2 se representa el modelo de flujo para la secuencia “The Graduate” codificado con Q igual a 4. En esta figura, el valor asociado a cada estado i corresponde a la cantidad de recursos requeridos para estar en el nivel de actividad i, se calcula como el promedio del parámetro Peak Rate de todos los GoPs considerados en tal nivel; su unidad es (bits/GoP). Sea λi, j la tasa de transición desde el estado i al estado j de la secuencia de video, cuyo valor es la inversa del tiempo de permanencia en el estado i, multiplicado por la probabilidad del evento j dado que está en i.
Figura 2. Modelo de tráfico de “ The Graduate” codificada con Q=4.
El análisis estadístico de los flujos a partir de la información de cada GoP de los parámetros Tspec, la tasa de transmisión y el PSNR, entre otros, permite determinar los valores de las tasas de transición, recursos requeridos y cualquier otra medida de performance (eficiencia) asociada a cada estado (o nivel de actividad) para cada flujo. Se observa que en cada instante de tiempo de una misma secuencia, las diferentes calidades de flujo están aproximadamente en el mismo nivel de actividad (0, 1 o 2). Para el paso 2) se observa que en una conexión, a lo largo del tiempo, el stream transmitido se corresponde con uno de los F flujos situado en uno de sus tres estados. Así, el estado de una conexión, eaf , corresponde a la transmisión de un flujo de calidad f (1: menor, …, F: mayor) en el nivel de actividad a (0: regular, 1: medio, 2: alto). Como ejemplo, la CMTC mostrada en la Fig. 3 modela el comportamiento de una conexión en el sistema, donde por claridad del dibujo se muestran sólo 3 calidades de flujo.
Figura 3. Modelo genérico para una conexión aceptada.
Cada columna de la Fig. 3 corresponde al modelo de cada flujo disponible de una secuencia de video, obtenidos en el paso 1). Entonces, el eje vertical de la Fig. 3 corresponde a los niveles de actividad. Las transiciones de la Fig. 3 reflejan el comportamiento de la secuencia y las decisiones de renegociación implementadas en el VoD. En este ejemplo, cuando se produce un cambio de actividad de la secuencia, el sistema elige el mejor flujo que le permitan los recursos disponibles limitado a que: si es aumento de actividad, el sistema mantiene o disminuye la calidad de flujo; si es
disminución de actividad, mantiene o aumenta a la siguiente calidad de flujo. Además, mientras no cambia de actividad, periódicamente solicita más recursos para cambiar a la siguiente mejor calidad (esto lo denominaremos polling de renegociación). En la Fig. 3 están dibujadas todas las potenciales transiciones permitidas por el sistema, pero la existencia de cada una de estas transiciones dependerá de los recursos requeridos y de los disponibles. V. RESULTADOS NUMÉRICOS
Se han realizado numerosas evaluaciones con el propósito de validar el modelo y su implementación. Se han obtenido valores de la esperanza del valor medio (es decir, EM(t )/t) de PSNR, BW transmitido y BW reservado. Estos resultados han sido contrastados con resultados experimentales de la plataforma real (testbed) del sistema de distribución de video bajo demanda SSADE (http://ssade.upc.es). A continuación se presentan algunos ejemplos numéricos de la esperanza del valor medio de la QoS ofrecida a un usuario del VoD. Los valores de configuración del sistema VoD en estos ejemplos son: Todos los usuarios del Vo D tienen el mismo perfil de QoS. Pueden reservar todo el BW que esté disponible y deben liberar el BW que no necesiten. La película solicitada al VoD por todos los clientes es “The Graduate”. De esta secuencia, el VoD tiene disponibles para transmitir los flujos codificados con Q igual a 4, 8 y 16. La codificación es MPEG-VBR, con M= 2, N= 6, de video PAL con formato CIF. En la tabla 1 se resumen los valores para el modelo de tres estados (niveles de actividad) de estos flujos. Estos valores se obtienen de la forma que es descrito en la sección IV.A. En la tabla 1a se muestran las tasas de transición entre niveles de actividad. En la tabla 1b, los recursos requeridos que se consideran son los Peak Rate del Tspec para cada flujo. Para simplificar el cálculo de esos parámetros, el tamaño de bucket se limita a que sea menor a 10 Bytes. Así, el Mean Rate es casi igual al Peak Rate, porque el tamaño del bucket no es un parámetro de recurso crítico. La longitud total de esta secuencia es 25325 GoPs, que es el tiempo de observación o medición. La tasa del polling de renegociación es 0.04 renegociaciones por GoP. La eficiencia (tasa de recompensa) asociada a cada estado es el PSNR, el BW efectivamente transmitido (bits/GoP) o BW reservado (bits/GoP). En la Fig 4 se presenta la esperanza de la utilización media del enlace. Esta medida es de gran interés a los proveedores y ha sido calculada como la razón entre el BW utilizado por todas las conexiones y los asignados al servicio de video. Los valores de trazo oscuro han sido calculados usando la ecuación de 3.10 de [1] (donde la recompensa asociada utilizada son los respectivos valores presentados en las tablas 1b y 1d) y los valores de trazo gris han sido calculados a partir de las trazas reales obtenidas de transmisiones en el testbed. La Fig 5 representa la QoS (medida como PSNR del video transmitido) ofrecida a un usuario en función de la cantidad de recursos compartidos en el enlace y el número de conexiones aceptadas en el VoD. Para un determinado BW asignado al servicio de video, a medida que aumenta el número de conexiones disminuye la QoS. En los valores de N en que no aparece la barra de una serie (un valor de BW total) el VoD no admite tal cantidad de usuarios. Las discontinuidades en las curvas analíticas se producen debido a la definición de un único estado en cada nivel de actividad y, por tanto, se ha asociado a cada uno de esos
estados un promedio de las medidas (eficiencia ) de las medida a priori para ser utilizada en la gestión de la QoS en escenas agrupadas en el respectivo nivel de actividad. El servicios de VoD, lo que valida nuestro modelo para dichos ajuste entre la aproximación propuesta y los resultados reales fines. para las estimaciones del valor medio, es suficiente como
Figura 4. Esperanza de la utilización media del enlace. BW efectivamente transmitido a los N usuarios dividido por el BW total compartido.
con una MRC y para resolverla se ha utilizado la técnica de randomización. La comparación de evaluaciones (en las medidas de PSNR, BW utilizado y BW reservado) de un sistema real (testbed) con los obtenidos por la evaluación del modelo, verifica su validez. Se encuentra actualmente en desarrollo le modelo para evaluar la Función de Distribución de Probabilidad, donde se contempla la posibilidad de que se requiera un modelo que considere más de un estado para cada Figura 5. Esperanza del PSNR medio estimado con el modelo propuesto. nivel de actividad. λ 0,1 λ 1,2 λ 2,1 λ 1,0
Vbr16 0.0031403747 0.003301801 0.04303278688 0,009433718
Vbr8 0.0030811008 0.003172488 0.0338409475 0.00935884
Vbr4 0.0025111464 0.002547517 0.0398009950 0.007801771
a). Tasas de transición para modelo de tres niveles de actividad. Unidad: [1/GoP].
Vbr16 Vbr8 Vbr4
Nivel 0 364476.06 366587.066639 553046.680253
Nivel 1 364476.06 392237.9456713 717029.0952097
Nivel 2 364476.06 501597.4111675 1033529.925223
b). Recursos medio reservados para la transmisión de una conexión en cada nivel de a ctividad. Unidad: [bits/GoP].
Vbr16 Vbr8 Vbr4
Nivel 0 0.00032386851 0.00013828712 5.56828935E-5
Nivel 1 0.00049464229 0.00021552240 8.461717324E-5
Nivel 2 0.00045332403 0.00022287058 9.752284877E-5
c). PSNR medio entregado a una conexión en cada nivel de actividad. Unidad: [lineal] .
Vbr16 Vbr8 Vbr4
Nivel 0 76536.002774 119331.87367 227509.09722
Nivel 1 114251.89567 202084.27605 393274.79948
Nivel 2 161180.08402 275269.41624 615892.17413
d). Tasa media efectivamente transmitida a una conexión en cada nivel de actividad. Unidad: [bits/GoP]. Tabla 1. Parámetros del modelo analítico para los flujos de la secuencia “El graduado” codificada con Q = 4, 8 y 16. Estos valores son obtenidos del análisis estadístico de cada flujo.
VI. CONCLUSIONES
En este trabajo se ha propuesto un modelo general del tráfico generado por un sistema de Video bajo Demanda (VoD) que adapta su tasa de transmisión a las condiciones de la red. El modelo tiene una directa interpretación con el diseño y funcionamiento global del VoD, lo que permite en forma fácil incorporar posibles modificaciones en el sistema y evaluar la influencia de tales modificaciones en la eficiencia del sistema en la QoS entregada a un determinado usuario. Además, el modelo que proponemos es simp le, evaluable computacionalmente y flexible para obtener a priori distintas medidas de rendimiento del sistema. Para conseguir estas características, hemos modelado el sistema
REFERENCES [1]
B. R. Haverkort, R. Marie, G. Rubino, K. Trivedi, “Performability Modelling. Techniques and Tools“, John Wiley & Sons, ISBN: 047149195-0 (2001). [2] D. Wu, Y. T. Hou, W. Zhu, Y-Q. Zhang, J. M. Peha, “Streaming Video over Internet: Approaches and Directions”, IEEE Trans. On Circuits and Systems for Video Technology, Vol. 11, Nº3: 282-300, 2001. [3] G.-M. Muntean, L. Murphy, “A New Adapatative Multimedia Streaming System for All-IP Multi- Service Networks”, IEEE Transactions on Broadcasting, Vol. 50. Nº1: 1-10, 2004. [4] A. Lombardo, G. Schembra, “Performance Evaluation of an AdaptativeRate MPEG Encoder Matching IntServ Traffic Constraints”, IEEE/ACM Transactions on Networking, Vol. 11 Nº1:47-65, 2003. [5] C. Luna, L. Kondi, A. Katsaggelos. “Maximizing User Utility in Video Streaming Applications”. IEEE Transactions on Circuits and Systems for Video Technology. 13 (2) (2003). [6] L. J. De la Cruz, J. Mata, “Performance of Dynamic Resource Allocation with QoS Guarantees for MPEG VBR Video Traffic Transmission over ATM Networks”. Proceeding of the IEEE GLOBECOM’99, IEEE Communications Society, 1999. [7] R. S. Ramanujan, J. A. Newhouse, M.N. Kaddoura, A. Ahamad, E.R. Chartier, K.J. Thurber, “Adaptive streaming of MPEG video over IP networks”, Proceedings 22nd Annual Conference on Local Computer Networks, IEEE, 398-409, 1997. [8] A. Adas, “Traffic Models in Broadband Networks”, IEEE Communications Magazine, 82-89, July 1997. [9] L. J. De la Cruz, M. Fernández, J. Alins, J. Mata “Bidimensional Fluid Model for VBR MPEG Video Traffic”. Fourth International Conference on Broadband Communications, IFIP, TC6/WG6.2, 538-549 (1998). [10] P. Manzoni, P. Cremonesi, G. Serazzi, “Workload Models of VBR Traffic and Their Use in Resource Allocation Policies”, IEEE/ACM Transactions on Networking, Vol.7, Nº3: 387-397, 1999. [11] J. Schnizlein, et al., “Terminology for Policy-Based Management”. Request for Comments RFC-3198, Internet Engineering Task Forc, (2001). [12] TAPAS IST Project (Trusted and QoS-Aware Provision of Application Services) http://www.newcastle.research.ec.org/tapas/ [13] I. V. Martin, et al., “Modelado y Análisis Transitorio de un Sistema de Distribución de Vídeo bajo Demanda”, JITEL03, Gran Canaria, 2003 [14] R. Vallejos, J. Martinez, "A Simple Method for Evaluating the Probability Distribution Function of Cumulative Operational Time in Repairable Systems", Fifth International Workshop on Performability Modeling of Computer and Communication Systems (PMCCS 5), pags. 61-66 Erlangen, Germany , September , 2001.
