DocsTec-6503

Vista previa del material en texto

Instituto Tecnológico y de Estudios
Superiores de Monterrey
Campus Monterrey
División de Electrónica, Computación, Información y Comunicaciones
Programa de Graduados en Electrónica, Computación, Información y
Comunicaciones
Análisis Comparativo de Políticas de Disk Scheduling con MPEG-2
TESIS
Presentada como requisito parcial para obtener el grado de
Maestro en Ciencias en Ingeniería Electrónica con
especialidad en Telecomunicaciones
Samuel Meza Goiz
Noviembre 2001
Instituto Tecnológico y de Estudios Superiores de
Monterrey
Campus Monterrey
División de Electrónica Computación,
Información y Comunicaciones
Programa de Graduados en Electrónica,
Computación, Información y Comunicaciones
Los miembros del comité de tesis recomendamos que la presente tesis del Ing. Samuel
Meza Goiz sea aceptada como requisito parcial para obtener el grado académico de
Maestro en Ciencias en Ingeniería Electrónica con especialidad en:
Telecomunicaciones
Comité de Tesis
Ramón M. Rodríguez Dagnino, Ph.D.
Asesor
Aprobado
M.C. Julio Armando Morales Fernández
Sinodal
Agradecimientos
Al Instituto Tecnológico y de Estudios Superiores de Monterrey por brindarme la
oportunidad de llevar a cabo mis estudios.
Mi agradecimiento al Ph.D. Ramón Martín Rodríguez Dagnino por su valiosa colaboración
y paciencia para la realización de esta tesis.
Mi agradecimiento al M.C. Raúl Ramírez Velarde y al M.C. Julio Armando Morales
Fernández por su colaboración y sus valiosos comentarios y observaciones en este trabajo.
A mi madre, mi padre, y mi hermano por su apoyo, consejos y paciencia
A Alejandra y su familia por haberme brindado su apoyo durante la realización de esta tesis
y por todo.
A mis amigos del Centro de Electrónica y Telecomunicaciones por el apoyo y los buenos
ratos. De manera muy especial a Anabel, Arturo, Calix y Francisco. A todas las personas
que formaron parte de mi vida durante este tiempo.
A mis amigos Alejandro, Dori, Hugo, Jesús y Rafael por haberme impulsado en una de las
etapas más importantes de mi vida.
Y a todas las personas que de una u otra forma influyeron para llevar a cabo esta empresa.
/ never saw a wild thing feel
sorry for itself.
A small bird will drop frozen dead from a bough
without ever having felt sorry for itself.
D. H. Lawrence
A mi Padre
A mi Madre
A mi hermano
A Alejandra
Resumen
Los avances tecnológicos en áreas de la Ingeniería como las telecomunicaciones, el video
digital, y los medios de almacenamiento han hecho posible y costeable la introducción de
servicios interactivos de video en lugares como escuelas, empresas y en el hogar. Dado que
esta tecnología es de reciente aparición, aún existen retos que superar para poder brindar un
servicio de excelente calidad al usuario final. Un sistema de video a la demanda está
compuesto en su forma más simple por un servidor de video, una infraestructura de
telecomunicaciones y equipo para el usuario. A lo largo del trayecto que sigue un flujo de
video para llegar al cliente, se encuentran cuellos de botella que ocasionan retardos en la
entrega de dicho flujo. El proceso de recuperación del video digital del disco en el servidor
de video ocasiona un retardo que, si se considera que se atiende a varios clientes, se puede
volver importante.
Existen algoritmos de recuperación de información de un disco duro que permiten un uso
más eficiente del mismo. En este trabajo se efectúa una comparación entre tres de estos
algoritmos con el objetivo de evaluar su desempeño considerando que la información de
video digital que se recupera es en formato MPEG-2. Dicho formato de video es un
formato de compresión que consiste de patrones de cuadros I,B y P. En esta tesis el tamaño
de cada cuadro fue obtenido a partir de distribuciones Gamma ya que en la literatura se ha
publicado que dicha distribución es la más adecuada para modelar el tamaño de los cuadros
arriba mencionados.
Los resultados de este trabajo muestran parámetros de desempeño como tiempo de servicio,
tiempo de espera y número de clientes en cola comparando los tres algoritmos (LOOK,
CLOOK y FCFS).
De este trabajo se desprende el hecho que el algoritmo LOOK es el que tiene un desempeño
más adecuado cuando se trabaja con información del tipo MPEG-2. La continuación de
este trabajo consistiría en llevar a cabo simulaciones empleando trazas de video real
codificadas en MPEG-2 y aún más, en verificar los resultados obtenidos mediante el
empleo de hardware.
índice
Capítulo I Introducción 1
Objetivo 1
Justificación 2
Aportación 2
Capítulo 2 Video a la Demanda 3
Video Digital [9] 4
Fundamentos de los algoritmos MPEG de compresión de video 11
MPEG-2 [8] 13
Sistemas de Video a la Demanda 17
Componentes de un Sistema VoD 19
Tecnologías de Acceso [5] 20
Video sobre ATM [3] 21
Servidores de Video [4] 23
Capítulo 3 Almacenamiento Magnético y Disk Scheduling 25
Características de los discos duros 25
Componentes de grabación 25
Componentes de posicionamiento 26
Controlador de Disco 29
Modelado de discos [6] 29
Parámetros de Desempeño del Disco 29
Tiempo de Búsqueda 30
Retardo Rotacional 30
Tiempo de Transferencia 30
Políticas de Disk Scheduling [16] 31
Algoritmos de Disk-Scheduling para sistemas Multimedia 35
Configuraciones de Múltiples Discos [1] 38
Capítulo 4 Simulación 39
Algoritmos de Disk Scheduling 39
i
Modelo del disco duro 42
Características Estadísticas del formato de compresión MPEG 45
Simulación 51
Capítulo 5 Resultados 54
Tiempo de Espera.. 54
Tiempo de Servicio 55
Simulación considerando la distribución gamma cuadro por cuadro 58
Capítulo 6 Conclusiones 63
Conclusiones 63
Trabajo futuro 64
Referencias 66
ii
111
iv
Capítulo I
Introducción
Los recientes avances tecnológicos en el área de las telecomunicaciones han hecho posible
cristalizar ideas que hace algunos años jamás hubiera sido posible realizarlas. La aparición
de nuevas tecnologías y protocolos de redes han permitido que el transporte de información
alcance velocidades cada vez mayores al mismo tiempo que el ancho de banda se
incrementa, inclusive hasta el usuario final. La aparición de las técnicas de digitalización
de video y de compresión del mismo ha dado pie a la idea de transmitir video digital en
tiempo real a través de la infraestructura de redes existente. El potencial de tal idea se
limita solamente a las restricciones tecnológicas existentes y que cada vez más, van
quedando atrás. El surgimiento de servidores de video que almacenan información digital
en formatos de compresión ha permitido desarrollar la idea del video a la demanda, en la
que un usuario podrá escoger y manipular alguna secuencia de video que desee sin
restricciones de horario e inclusive con capacidades similares a los de una reproductora de
cinta magnética. El diseño de tales servidores de video sigue presentando un reto para la
tecnología ya que se deben de cuidar varios aspectos como son : el colocamiento de la
información en el disco, los esquemas de control de admisión de nuevos clientes, y la
recuperación, y transmisión de la información. Existen políticas de disk scheduling que
han sido empleadas durante años para extraer información de los discos, y son esas mismas
técnicas las que son utilizadas por algunos servidores.
Objetivo
El objetivo de este trabajo es el de estudiar y comparar algunas políticas de disk
scheduling considerando que la información que se recupera se encuentra en un formato de
compresión de video digital (MPEG-2), para poder discutir sobre la eficiencia de dichas
políticas en un servidor de video.
1
Justificación
En la literatura existen varias referencias a los algoritmos que se emplean en este
trabajo, y, sin embargo, son muy pocos los artículos que incluyen el formato de compresión
MPEG-2 y en su mayoría utilizan el MPEG-1. Algunos de los artículos inclusive
recomiendan el estudio de las políticas de disk scheduling junto con MPEG-2.
Aportación
Este trabajo pretende dar un amplio panorama de las políticas clásicas dedisk
scheduling, mencionando su funcionamiento, características, ventajas y desventajas y al
mismo tiempo evaluar el desempeño de algunas de ellas cuando la información recuperada
es del tipo MPEG-2. Los resultados generados por este trabajo brindarán un inicio para el
análisis de información real que puede ser obtenida de hardware en un servidor de video
real.
2
Capítulo 2
Video a la Demanda
Hasta hace poco, las señales de video eran almacenadas y transmitidas exclusivamente de
forma analógica y al parecer continua a ser la situación más común. El medio principal de
almacenamiento es la cinta de video analógica, y los principales canales de transmisión son
el canal de difusión "aereo", cable y satélite. Sin embargo, y debido a los recientes avances
en el hardware y en la tecnología de compresión de imágenes, los sistemas para el
almacenamiento y la transmisión digital se han vuelto más comunes. De hecho se espera
que el video digital se vuelva predominante en el futuro. El video será almacenado en
forma digital en discos y cinta, y será transmitido digitalmente sobre redes de banda amplia,
así como en redes inalámbricas y canales de difusión. La Figura 1 muestra algunos de los
empleos actuales y futuros del video digital.
Entrenamiento
• Cursos Interactivos
• Just-ln-Time
(Ayuda Interactiva)
•» Aula
Internetflntranet
• Publicidad
• Acceso a
Información
• Entretenimiento
Presentaciones
• Ventas
• Kioscos comerciales
• ; Kioscos de
información
• Seminarios/Reportes Bases de Datos
• Archivos Históricos
• Video a la Demanda
• Referencia de
Información
• Juegos
Difusión
• Noticias
• Entretenimiento
Figura 1 Usos del video digital
3
Las señales de video son notorias por el consumo de grandes cantidades de ancho de banda.
Por ejemplo, una señal de video analógica National Televisión System Committee (NTSC)
utiliza un ancho de banda de 6 Mhz, mientras que una señal de video digital NTSC sin
comprimir requiere de una tasa de bit de alrededor de 100 Mbps. Para permitir una
transmisión y/o almacenamiento económico, es necesario utilizar esquemas más eficientes.
Este proceso se ve por lo general como una operación de compresión, en la que la calidad
se ve sacrificada; un punto de vista diferente es que se busca un esquema o representación
que entregue la máxima calidad de video para la tasa de datos disponible. A tasas de 20 a
30 Mbps, esto entregaría imágenes grandes de alta calidad (televisión de alta definición
HDTV), mientras que a tasas bajas como 64 Kbps e inferiores, esto resultaría en un sistema
que provee imágenes pequeñas de una calidad inferior y con capacidad limitada para
movimiento (videoteléfono).
Video Digital [9]
Las técnicas de codificación de fuente buscan explotar tanto la redundancia en la fuente y
los requerimientos de fidelidad del receptor para minimizar la distorsión para una tasa de
datos dada. Si un modelo estocástico de la fuente y un criterio de fidelidad para el receptor
son conocidos, se puede encontrar un desempeño óptimo utilizando teoría de distorsión de
tasa. Sin embargo, un codificador implementable con un retardo aceptable que pueda
entregar tal desempeño puede no estar disponible.
Características de la fuente y requerimientos del espectador
Un número de factores determina las características de la fuente y el nivel de redundancia
que puede ser explotado. Dichos factores incluyen el scanning formal, la relación señal a
ruido, la cantidad de detalle, y las características del movimiento.
El scanning formal abarca el tamaño de la imagen y la estructura de muestreo. Se asume
que la entrada al codificador de la fuente es completamente digital, y que es una secuencia
ordenada de palabras código binarias de longitud fija que representan el color de la imagen
en un conjunto discreto de puntos \\f. Esto se denota como:
4
U,(x,y,t), (x.y,t)eyh i=l,2,3.
donde u¡,U2,us representan coordenadas en un espacio de color. Estos pueden ser
componentes rojo-verde-azul o luminancia-crominancia. La estructura de muestreo \i/ es un
arreglo rectangular de puntos adecuado espacialmente al tamaño del cuadro de la imagen.
El tamaño de la imagen puede variar desde ventanas pequeñas hasta de pantallas completas.
Hay dos estructuras de scanning ampliamente utilizadas para video: scanning progresivo y
scanning entrelazado. En sistemas analógicos, donde la captura, transmisión y formatos de
despliegue son los mismos, el entrelazado es un método para alcanzar una resolución
vertical mayor para una tasa de sean vertical y un ancho de banda del sistema dados. La
tasa de sean vertical de 50 o 60 Hz utilizado en la mayoría de los sistemas se determina por
el requerimiento para minimizar la visibilidad de parpadeo (flicker) en la pantalla. Aunque
el entrelazado es una buena técnica en el contexto de los sistemas analógicos, por lo general
conduce a aliasing espacio-temporal cuando existe movimiento vertical, lo que hace que
todo el procesamiento subsiguiente, y especialmente la codificación de la fuente, se vuelva
mucho más difícil. Por esta razón se ha incrementado el interés por el scanning progresivo
en las propuestas de sistemas recientes.
La razón señal a ruido de la fuente tiene un impacto significativo en la eficiencia de la
compresión. En general, el ruido tiene poco redundancia y no puede ser comprimido
mucho; por lo tanto, debe de ser removido antes de la compresión si es posible. El
procesamiento compensado de movimiento es requerido para la reducción de ruido más
efectiva.
Las características del movimiento en la escena afectan la cantidad de compresión posible.
El movimiento aparente en la imagen puede ser debido ya sea al movimiento de la cámara
(incluyendo los acercamientos), al movimiento de los objetos, o a ambos. Generalmente el
movimiento puede ser "bajo", como en una aplicación de videoconferencia, o muy activo,
como en una evento deportivo; puede ser altamente estructurado (movimiento de cuerpo
rígido) o pseudoaleatorio (follajes). El conocimiento de las características del movimiento
puede afectar al algoritmo de codificación.
5
La redundancia en una fuente está relacionada con el concepto de predictibilidad. Dado
que una cierta porción de la señal de la fuente ya ha sido transmitida, el codificador puede
intentar predecir lo que sigue. Si la predicción es confiable, es mejor transmitir
información concerniente a la desviación de la predicción que información pura. La
predictibilidad implica una cierta regularidad de la información que puede ser capturada por
modelos estadísticos. En la dimensión espacial, si un cierto patrón aparece sobre cierta
área, uno puede asumir que el patrón continuará, y hacer la predicción basándose en ello.
En una imagen con movimiento, la suposición es que si un objeto se mueve con una cierta
velocidad y aceleración, continuará a hacerlo. Por lo tanto, si la velocidad y la aceleración
son conocidas, el codificador puede predecir como se verá el próximo cuadro, y transmitir
solamente el error entre esta predicción y el valor verdadero. En los cambios de escena, la
predicción será completamente errónea y deberá de transmitirse más información. Sin
embargo, en promedio existirá una compresión substancial. El cambio temporal no se debe
solamente al movimiento. La iluminación puede cambiar, y la luminiscencia de algunos
puntos de la escena pueden cambiar si los ángulos entre la superficie del objeto, la fuente
de iluminación, y la cámara cambian.
Aparte de la redundancia estadística en la fuente, existe la redundancia perceptual (también
llamada irrelevancia) en la que se considera que aquella información que no pueda ser
percibida por el usuario no necesita ser transmitida.
El objetivo de un codificador eficiente es maximizar la calidad (o minimizar la distorsión)
sujeto a un número de restricciones. En muchas aplicaciones de compresión de video, la
calidad o distorsión son medidas subjetivas que se determinan por las propiedades visuales
del espectador.Sin embargo, si se llegara a realizar una manipulación o procesamiento de
la secuencia, sería más apropiado tener un criterio objetivo ajustado ya que los defectos
invisibles al espectador podrían tener un efecto negativo en una operación de
procesamiento de la señal tal como el chroma key.
6
Otros requerimientos pueden afectar el tipo del algoritmo de codificación utilizado. Estos
incluyen: retardo, acceso aleatorio, control de reproducción, y escalabilidad. Tanto el
algoritmo como el canal de transmisión introducen un retardo. Dependiendo de la
aplicación, este retardo puede estar limitado de manera severa, especialmente para
aplicaciones interactivas. La aplicación más demandante en ese aspecto es la comunicación
cara a cara, en donde un retardo punto a punto máximo de alrededor de 200 ms puede ser
tolerado. Si el retardo es mayor a esto, la interacción espontánea se vuelve difícil. En una
aplicación de acceso a una base de datos, los retardos un poco mayores pueden ser
aceptables.
El algoritmo de codificación debe de tomar en cuenta las propiedades del canal o del medio
de almacenamiento. El canal puede permitir solamente la operación a una tasa de bit
constante (CBR) , o puede permitir la operación a una tasa de bit variable (VBR). En el
primer caso, el codificador debe de ser diseñado para producir un número fijo de bits sobre
una unidad de tiempo específica. En el otro caso, la tasa de bit puede variar en el tiempo,
aunque algunas limitantes negociadas en el momento de establecer la conexión deben de
ser respetadas (i.e. razón de tasa de bit pico a promedio). Otro requerimiento de un
algoritmo de codificación es un desempeño aceptable en la presencia de defectos típicos del
canal. Estos defectos pueden variar considerablemente para diferentes tipos de canal. Un
ejemplo de esto es que un enlace digital dedicado puede tener errores aleatorios con una
probabilidad de ocurrencia muy baja, mientras que un enlace inalámbrico puede tener
errores en ráfaga con una alta probabilidad de ocurrencia.
En algunas situaciones, la misma señal de video debe de ser entregada a una variedad de
receptores que poseen diferentes capacidades. La capacidad para transmitir solamente la
porción de la información requerida por la terminal, o para extraer un subconjunto de la
información, se conoce como escalabilidad. El enfoque más directo para esto es la difusión
simultánea o el almacenamiento múltiple de la información codificada para cada tipo de
receptor. Esto es complejo y se desperdicia la capacidad de almacenamiento y/o
transmisión. Para contrarrestar esto se utiliza un enfoque conocido como codificación
incrustada, en la que un subconjunto de la información codificada puede ser utilizada para
7
decodifícar una versión menor de la secuencia apropiada para su presentación en una
pantalla de menor capacidad.
Algoritmos de Codificación
El objetivo de un algoritmo de codificación de la fuente es por lo general proveer la mejor
calidad de imagen para un canal o una tasa de transmisión dada y sujeta a las limitaciones
en complejidad, retardo y los otros requermientos mencionados.
En las imágenes variantes en el tiempo, mucha de la información incremental en el tiempo
es proporcionada por el movimiento que ocurre en la escena. Por lo tanto, los algoritmos
de codificación más eficientes están basados en la estimación del movimiento y
compensación. Por lo general, una secuencia de imagen es codificada tanto por técnicas de
codificación intracuadro así como por técnicas de codificación intercuadro. Los algoritmos
de codificación intercuadro son muy similares a los algoritmos de codificación de imágenes
sin movimiento y se utilizan por las siguientes razones:
• Permitir el acceso aleatorio dentro de la secuencia.
• Permitir operaciones de adelantado y retroceso.
• Proveer robustez a errores en el canal.
• Respaldo cuando la codificación temporal falla (cambio de escena)
Compensación de Movimiento
El movimiento tridimensional de los objetos en una escena induce movimiento en dos
dimensiones en el plano de la imagen. La relación entre ellos depende de la transformación
de la perspectiva de la cámara y puede ser compleja. La imagen de un cierto punto de la
escena traza a través del tiempo una trayectoria en las coordenadas espacio-tiempo de la
imagen variante en el tiempo. El principio básico en esta codificación es que la
redundancia es muy alta en esta trayectoria. Esto es realizado utilizando la siguiente
estructura.
8
La señal de entrada es aplicada al módulo de estimación de movimiento que determina un
campo de movimiento. Este campo de movimiento establece las corresondencias entre las
muestras de la imagen que se encuentran sobre la misma trayectoria en imágenes sucesivas.
Aunque el campo de movimiento especifica desplazamientos estimados para cada pixel en
la secuencia de la imagen, puede ser especificado paramétricamente sobre regiones. El
campo de movimiento es luego codificado para su transmisión hacia el receptor a una tasa
RM- Se asume que cualquier cuantización del campo de movimiento toma lugar dentro del
módulo de estimación de movimiento. El campo de movimiento también se alimenta al
módulo de codificación de compensación de movimiento, el cual realiza una codificación
condicional de la secuencia de la imagen dado el campo de movimiento cuantizado y el
estimado. La salida de este módulo es transmitida al receptor a una tasa R¡.
La tasa total R para codificar la secuencia de video es igual a la suma de RM, la tasa de
transmisión de la información de movimiento, y R¡, la tasa para transmitir la información de
video codificada condicionalmente.
Existen dos enfoques para estimar el campo de movimiento: el enfoque paramétrico y el
enfoque basado en pixeles. En este último, un vector de desplazamiento es estimado para
cada pixel en la imagen utilizando algún algoritmo robusto. El campo de movimiento
resultante es entonces codificado eficientemente para alcanzar la tasa deseada. La
posibilidad de una compresión significativa es alta ya que el campo de movimiento es por
lo general muy redundante. El enfoque paramétrico es más común en la codificación de
video, en donde el campo de movimiento es representado paramétricamente sobre regiones
de la imagen. La técnica más común consiste en suponer un desplazamiento constante
sobre un bloque rectangular de pixeles. Una aproximación más general es la de asumir que
el movimiento es representado paramétricamente sobre regiones no rectangulares. En este
caso, la especificación de las fronteras de las regiones es parte de la representación del
movimiento. Existen muchos algoritmos para estimar el movimiento, incluyendo la
optimización basada en gradiente y métodos de transformación de dominio, entre otros.
Codificación Predictiva
El principio de la codificación predictiva es que, dada la información del movimiento y las
imágenes previamente decodificadas, es posible formar un buen estimado de la siguiente
imagen a codificar. Por lo tanto, solamente es necesario codificar y transmitir la desviación
de este estimado. Una estructura muy bien adaptada para esto es el differential pulse code
modulation (DPCM). En este sistema, la predicción es formada en base a las imágenes
previamente reconstruidas utilizando un decodificador local en el transmisor. El error de
predicción es cuantizado espacialmente y se codifica sin pérdidas en una tasa variable de
transmisión.
En el modo básico de operación, la información de la imagen en el tiempo t es predecida de
la información desplazada en el sean vertical previo en el tiempo t - T, donde T es el
tiempo de sean vertical. La predicción de la imagen de entrada muestreada u(x,y,t) está
dada por
Ü(x,y,t) = ü(x-dx(x,y,t), y-dy(x,y,t),t- T)
en donde (dx(x,y,t), dy(x,y,t)) es el desplazamiento estimado en (x,y,t) y ü es la salida
reconstruida localmente del codee. Si (x-dx, y-dy,t-T) no cae en la malla de muestreo, es
necesario utilizarinterpolación espacial para calcular ü de las muestras existentes de ü en el
tiempo t - T. Si la señal de video está en un formato entrelazado, cada sean vertical de la
imagen contiene solamente parte de la información espacial. Por lo tanto resulta muy
ventajoso utilizar una predicción más elaborada utlizando al menos los dos últimos cuadros,
como lo utiliza el Moving Pictures Expert Group - 2 (MPEG-2).
Una desventaja de la codificación predictiva es que el error de cuantización del codificador
residual se retroaliementa al predictor. Esto limita la eficiencia de la compresión, aun si la
fuente está altamente correlacionada a lo largo de las trayectorias de movimiento. Una
manera de contrarrestar este efecto es el uso de la codificación interpolativa para algunos
cuadros.
10
Codificación Interpolativa
La codificación interpolativa es llamada a veces codificación predictiva bidireccional. En
este método, se asume que algunos cuadros espaciados M cuadros de distancia, llamados
cuadros de referencia, ya han sido codificados por algún otro método (codificación
intracuadro o predictiva). Entonces, los cuadros intermedios son estimados basándose en
los cuadros de referencia previos y subsecuentes, utilizando compensación de movimiento.
El error de estimación es cuantizado espacialmente y codificado sin pérdidas para
transmisión.
Los pixeles en una imagen B pueden ser estimados de la imagen de referencia previa, la
imagen de referencia siguiente o de ambas, dependiendo de cual da los mejores resultados.
En general, las imágenes codificadas de forma interpolativa tienen menos errores que las
imágenes codificadas predictivamente a la misma tasa. Sin embargo, la eficiencia de
DPCM disminuye conforme se incrementa el espaciamiento entre las imágenes. La
codificación interpolativa es un método de lazo abierto; no existe retroalimentación del
error de cuantización como en DPCM.
Fundamentos de los algoritmos MPEG de compresión de video
Las técnicas MPEG de codificación de video digital son estadísticas por naturaleza. Las
secuencias de video contienen redundancia estadística tanto temporal como espacial. La
propiedad estadística básica sobre la que se basan las técnicas de compresión MPEG es la
correlación inter-pel (PEL, picture element), incluyendo la suposición de movimiento de
translación entre cuadros consecutivos. Por lo tanto se asume que la magnitud de un peí en
particular puede ser predicha de los pels vecinos dentro del mismo cuadro (utilizando
técnicas de codificación Intra-cuadro) o de pels de un cuadro cercano (utilizando técnicas
ínter-cuadro). De manera intuitiva resulta claro que en algunas circunstancias (durante
cambios de escena en una secuencia), la correlación temporal entre pels en cuadros vecinos
es pequeña o incluso desaparece - la escena de video junta entonces una colección de
imágenes fijas no correlacionadas. En ese caso, la codificación ínter-cuadro es apropiada
11
para explorar la correlación espacial de tal manera que se pueda lograr una eficiente
compresión de datos. Los algoritmos de compresión MPEG emplean técnicas de
codificación de Transformada Discreta Coseno (DCT, Discrete Cosine Transform) en
bloques de imagen de 8x8 pels para explorar eficientemente las correlaciones espaciales
entre pels vecinos dentro de la misma imagen. Sin embargo, si la correlación entre pels en
cuadros cercanos es alta es más deseable utilizar técnicas de codificación ínter-cuadro
DPCM (Differential Pulse Code Modulation) empleando predicción temporal ( predicción
compensada por movimiento entre cuadros). En los esquemas de codificación MPEG se
emplea una combinación de predicción temporal compensada por movimiento seguida por
una codificación de transformación (DCT) de la información espacial para lograr una alta
compresión de la información (codificación de video híbrida DPCM/DCT).
Actualmente, el grupo MPEG (Motion Picture Experts Group) de la ISO (International
Organisation for Standardisation) ha producido MPEG-1, el estándar en el cual se basan
productos como Video CD y MP3, MPEG-2, el estándar en el cual se basan productos
como el DVD y las STB (Set Top Boxes) para televisión digital y MPEG-4, el estándar de
multimedia para la red y movilidad.
La técnica de compresión de video desarrollada en MPEG-1 cubre muchas aplicaciones que
van desde sistemas interactivos en CD-ROM hasta la entrega de video sobre redes de
telecomunicación. Para poder soportar el amplio rango de aplicaciones, el MPEG-1 cuenta
con una diversidad de parámetros que pueden ser especificados por el usuario, incluyendo
el tamaño de imagen y la tasa de cuadros. Cada decodificador compatible con MPEG-1
debe de ser capaz de soportar al menos los siguientes parámetros de video: 720 pixels por
línea, 576 líneas por imagen, tasa de 30 cuadros por segundo y tasa de 1.86 Mbits por
segundo. La entrada estándar de video consiste de un formato de video no entrelazado.
El algoritmo de video MPEG-1 ha sido desarrollado con respecto a las actividades del Joint
Picture Experts Group (JPEG) y del CCITT H.261 y se dirige principalmente a aplicaciones
de video almacenado. Algunas características importantes provistas por el MPEG-1
incluyen el acceso aleatorio, búsquedas en modos fast forward y fast reverse y otros. Para
un estudio amplio de este estándar, se puede referir a [7].
12
MPEG-2 [8]
En 1991, los esfuerzos de estandarización de MPEG continuaron con una segunda fase
(MPEG-2) para proveer una solución de codificación de video para aplicaciones no
cubiertas originalmente por el estándar MPEG-1. De manera específica, el MPEG-2 tenía
el encargo de proveer una calidad de video no menor a la de NTSC/PAL y cercana a CCIR
601. Las aplicaciones emergentes tales como la distribución de televisión digital por cable
se verían beneficiadas por el incremento en la calidad esperada de la nueva fase de
estandarización.
Básicamente, el MPEG-2 puede ser visto como un superconjunto del estándar de
codificación MPEG-1 y fue diseñado para ser compatible con el mismo. Algunas
características de codificación fueron agregadas por el MPEG-2 para alcanzar una
funcionalidad y calidad suficientes, por lo que se desarrollaron modos de predicción para
soportar la codificación eficiente del video entrelazado. También se introdujeron
extensiones de codificación de video escalable para proveer funcionalidad adicional, tales
como la codificación incrustada de TV digital y de televisión de alta definición (HDTV) y
una degradación aceptable de la calidad en presencia de errores de transmisión.
Sin embargo, una implementación de la sintaxis completa puede no resultar práctica para la
mayoría de las aplicaciones. El MPEG-2 ha introducido el concepto de "Perfiles" y
"Niveles" para estipular la conformidad entre los equipos que no soporten la
implementación completa. Los Perfiles y Niveles proveen los medios para definir
subconjuntos de la sintaxis y por lo tanto las capacidades requeridas del decodificador para
decodificar un stream en particular.
Como una regla general, cada Perfil define un nuevo conjunto de algoritmos agregados
como un superconjunto a los algoritmos en el Perfil inferior. Un Nivel especifica el rango
de parámetros que son soportados por la implementación (i.e. tamaño de la imagen, tasa de
cuadros y tasas de bit). El algoritmo principal del MPEG-2 en el Perfil MAIN contiene la
codificación no escalable tanto de fuentes de video progresivas como entrelazadas, y se
13
espera que la mayoría de las implementaciones de MPEG-2 se apeguen al menos al perfil
MAIN en el nivel MAIN el cual soporta la codificación no escalable de video digital con
parámetros aproximados a la televisión digital - densidad máxima de 720 muestras por
línea y 576 líneas por cuadro, una tasa de cuadros máxima de 30 cuadros por segundo y una
tasa de bit máxima de 15 Mbits por segundo.
Modos de codificación no escalables del MPEG-2
El algoritmo MPEG-2 definido en el Perfil MAINes una extensión directa del esquema de
codificación del MPEG-1 para proveer la codificación de video entrelazado al mismo
tiempo que se mantiene el rango completo de la funcionalidad provista por el MPEG-1. De
manera idéntica al estándar MPEG-1, el algoritmo de codificación MPEG-2 está basado en
el esquema de codificación DCT/DPCM incorporando una estructura de Macrobloque,
compensación de movimiento y modos de codificación para el rellenado condicional de los
Macrobloques. El concepto de cuadros-I, cuadros-P y cuadros-B como se introdujo en
MPEG-1 se mantiene en MPEG-2 para lograr una predicción de movimiento efectiva y
para ayudar a la funcionalidad de acceso aleatorio. Debe de notarse que el algoritmo
definido por el Perfil SIMPLE es básicamente idéntico al del Perfil MAIN, con la
excepción de que no permiten modos de predicción de cuadros-B en el encoder. Por lo
tanto, la complejidad adicional para la implementación y el almacenamiento de cuadros
adicionales necesarios para la decodificación de los cuadros-B ya no son requeridos para
los decodificadores MPEG-2 que se apegan solamente al Perfil SIMPLE.
El MPEG-2 ha introducido el concepto de las imágenes de cuadro y de las imágenes de
campo con modos particulares de predicción de cuadro y predicción de campo para incluir
la codificación de video progresivo y entrelazado. Para las secuencias entrelazadas se
asume que la entrada al codificador consiste de una serie de campos impares (superior) y
pares (inferior) que se encuentran separados en tiempo por un periodo de campo. Dos
campos de un cuadro pueden estar codificados de manera separada (imágenes de campo).
En este caso cada campo es separado en Macrobloques adyacentes que no se traslapan y la
DCT es aplicada en el campo. De manera alternativa, es posible codificar dos campos
14
juntos como un cuadro (imagenes de cuadro) de manera similar a la codificacion
convencional de secuencias de video progresivas. Por lo tanto, las lineas consecutivas de
los campos superior e inferior son simplemente unidas para formar un cuadro. Notese que
es posible emplear tanto imagenes de cuadro como imagenes de campo en una sola
secuencia de video.
Prediccion de campo y de cuadro: En MPEG-2 se introdujeron nuevos modos de
prediccion de campo por compensacion de movimiento para codificar eficientemente las
imagenes de campo y las de cuadro. En la prediccion de campo, las predicciones son
hechas independientemente para cada campo empleando datos de uno o mas campos
previamente decodificados (por ejemplo, para un campo superior es posible obtener una
prediccion ya sea de un campo superior previamente decodificado (utilizando prediccion
compensada por movimiento) o de un campo inferior previamente decodificado
perteneciente a la misma imagen. Por lo general se prefiere la prediccion Inter-campo del
campo decodificado en la misma imagen si no ocurre movimiento entre campos.
La prediccion de cuadro realiza una prediccion para una imagen de cuadro basandose en
uno o mas cuadros previamente decodificados. En una imagen de cuadro es posible
emplear predicciones de campo o de cuadro y el modo de prediccion particular preferido
puede ser seleccionado en una base Macrobloque por Macrobloque.
El MPEG-2 ha introducido nuevos modos de compensacion de movimiento para explorar
eficientemente las redundancias temporales entre campos, principalmente la prediccion
"Dual Prime" y la compensacion de movimiento basada en bloques de 16x8.
Formatos de crominancia: El MPEG-2 especifica formates adicionales para la razon de
submuestreo de luminancia y crominancia Y:U:V para ayudar y adoptar aplicaciones con
requerimientos de alta calidad de video. Junto con el formato 4:2:0 ya soportado por el
MPEG-1, la especificacion de MPEG-2 se extiende a formatos 4:2:2 apropiados para
aplicaciones de codificacion de video de alta calidad.
15
Extensiones de Codificación Escalable
Las herramientas de escalabilidad estandarizadas por el MPEG-2 proveen soporte para
aplicaciones que se encuentran más allá de las que cubre el algoritmo de codificación del
Perfil MAIN. La intención de la codificación escalable es la de proveer interoperabilidad
entre diferentes servicios y proveer soporte de manera flexible para los receptores con
diferentes capacidades de despliegue. Los receptores que no son capaces o no desean
reconstruir la completa resolución del video pueden decodificar subconjuntos de las capas
del flujo de bits para desplegar el video con una resolución temporal o espacial más baja o
con una calidad inferior. Otro aspecto importante de la codificación escalable es proveer
un flujo de bits (video) en capas que pueda ser conducido por una transmisión con
prioridades. El reto principal de este aspecto es entregar señales de video de manera
confiable en presencia de errores del canal, tales como la pérdida de celdas en redes ATM o
la interferencia co-canal en difiísión digital.
Durante la fase de estandarización del MPEG-2 se encontró que era imposible desarrollar
un esquema de codificación escalable genérico capaz de acomodar todos los requerimientos
de las diversas aplicaciones que se tenían contempladas. Como consecuencia de esto, el
MPEG-2 ha estandarizado tres esquemas de codificación escalable: Escalabilidad SNR,
Escalabilidad Espacial y Escalabilidad Temporal. Las herramientas de escalabilidad
proveen extensiones algorítmicas al esquema no escalable definido en el Perfil MAIN y es
posible combinar diferentes herramientas de escalabilidad en un esquema de codificación
híbrido. La sintaxis del MPEG-2 provee soporte para hasta tres diferentes capas de
escalabilidad.
Escalabilidad Espacial: Se desarrolló para proveer soporte a displays con resoluciones
espaciales diferentes en el receptor. Esta funcionalidad es útil para muchas aplicaciones
incluyendo codificación incrustada para sistemas HDTV, permitiendo una migración desde
un servicio de televisión digital hacia servicios HDTV con una resolución espacial mucho
mayor. El algoritmo está basado en el enfoque piramidal para codificación progresiva de
imagen. La escalabilidad espacial puede soportar un amplio rango de resoluciones
16
espaciales pero agrega una considerable complejidad de implementación al esquema de
codificación del Perfil MAIN.
Escalabilidad SNR: Esta herramienta se desarrolló principalmente para proveer una
degradación suave (escalabilidad de calidad) de la calidad del video en medios de
transmisión con prioridades. Si la capa base puede ser protegida de errores de transmisión,
una versión del video con una calidad reducida puede ser obtenida únicamente mediante la
decodificación de la señal de la capa base. El algoritmo empleado para lograr la
degradación suave está basado en una técnica de escalabilidad en frecuencia.
Escalabilidad Temporal: El propósito de esta herramienta es similar al de la escalabilidad
espacial — el video estereoscópico puede ser soportado con un flujo de bits en capas
apropiado para los receptores que tengan la capacidad de despliegue estereoscópico.
Sistemas de Video a la Demanda
La disponibilidad de un gran ancho de banda y de poder de cómputo ha hecho posible la
entrega y procesamiento de la información en tiempo real por usuario y por sesión. La
habilidad de procesar información en la fuente permite que el proveedor de la información
pueda extraer datos relevantes y modificar ciertas características del servicio para el gusto
específico de cada usuario. Los usuarios de tales servicios tendrán la flexibilidad de
escoger el tipo de información que reciben así como la forma y el horario de recepción.
Los servicios interactivos darán a los usuarios la flexibilidad de seleccionar y recibir
información de acuerdo a sus preferencias.
Servicios Interactivos
Existen diferentes tipos de servicios interactivos cuya diferencia radica en el nivel de
interactividad que posean [5].
• Servicios Broadcast (No-VoD): El usuario es un participante pasivo y no tienecontrol sobre la sesión
17
• Pago por Evento (PPV): El usuario se suscribe y paga por una programación
específica y no tiene control sobre la sesión.
• Cuasi Video a la Demanda (Q-VoD): Los usuarios son agrupados basándose en
un mismo interés. Los usuarios puede realizar actividades de control
rudimentarias.
• Near video on demand (N-VoD): Algunas funciones como adelanto y atraso
son simuladas mediante transiciones en intervalos de tiempo discreto (del orden
de 5 minutos). Esta capacidad se provee con múltiples canales con la misma
programación defasada en tiempo.
• Truc video on demand (T-VOD): El usuario tiene el control total sobre la
sesión. El usuario tiene capacidades de adelante, atraso, pausa, posicionamiento
aleatorio, entre otros. T-VOD necesita solamente un canal.
Los servicios interactivos abarcan un amplio rango de aplicaciones que van desde películas
a la demanda hasta educación a distancia. Algunas áreas de aplicación se muestran en la
Tabla 1
Tabla 1 Aplicaciones y Servicios Interactivos
Aplicación
Películas a la Demanda Los clientes pueden seleccionar y reproducir películas
con capacidades de una reproductora de películas
(VCR)
Juegos de Video Interactivos Los clientes pueden obtener y jugar en linea copias de
juegos
Noticias Interactivas Las noticias pueden ser escogidas de acuerdo al gusto
de los clientes (más detalle en algunas noticias, menos
en otras)
Catálogos Los clientes pueden examinar y realizar compras de
productos comerciales
Educación a Distancia Los clientes se pueden suscribir a cursos y clases
impartidos en localidades remotas, y pueden ajustar
las clases y cursos a sus horarios y preferencias.
Publicidad Interactiva Los clientes pueden responder a los anuncios e
interactuar con los ofertantes.
Algunas de las funcionalidades que brindarán los servicios interactivos son:
• La habilidad de escoger una fuente de programación en lugar de aceptar una.
• La habilidad de evitar o escoger comerciales.
• Capacidades de una VCR virtual
18
• Accesibilidad a detalles extra de la información mediante enlaces.
Componentes de un Sistema VoD
Un sistema de Video a la Demanda tiene muchos elementos que son necesarios para el uso
del servicio completo. Dicho sistema incluye servidores de video, redes, oficina de
conmutación y equipo del usuario, como se observa en la Figura 2.
Switching
Office
Figura 2 Elementos de un sistema de video a la demanda
Terminal del Usuario: Este aparato junto con el monitor y un control remoto permite a los
usuarios conectarse a una fuente de video (servidor de video) y hojear a través de una
selección de videos (películas, juegos, noticias) u otros contenidos. Los componentes
principales de este aparato son el transceiver de la línea, un demodulador, la unidad de
descompresión, una interfaz para el canal de regreso, un control remoto y un driver para el
despliegue de las imágenes.
Red del Suscriptor: La infraestructura de comunicaciones entre el cliente y la oficina local
de conmutación recibe el nombre de Red del Suscriptor. Dicha infraestructura conecta el
servidor de video y la terminal del usuario. Existen diversas tecnologías que pueden servir
para tal efecto y cada una tiene su propio rango de servicio, ancho de banda y
características ambientales.
19
Tecnologías de Acceso [5]
A diferencia de las comunicaciones actuales de computadoras, la transmisión de sesiones
VoD requerirá de la disponibilidad del canal de transmisión por un tiempo considerable
para la transferencia continua de información.
Redes de televisión por cable: El sistema de distribución por cable (CATV) está basado en
una topología de árbol y en un futuro se basará en una topología de estrella. Las señales de
audio y video serán transmitidas mediante cable coaxial dentro del área del suscriptor y las
troncales por lo regular están hechas con fibra. Esta tecnología puede soportar múltiples
flujos de video comprimido con MPEG. El CATV tiene una enorme capacidad de ancho de
banda y soporta cientos de conexiones simultáneas. Más aún, debido a que esta tecnología
se encuentra ampliamente desplegada, el costo por soportar VoD será significativamente
más bajo, pero se necesitará de cierta adaptación para permitir la señalización bidireccional
requerida para los servicios interactivos.
ADSL. El lazo de abonado digital asimétrico (ADSL) se aprovecha de los avances en
codificación para proveer al cliente con una señal de banda amplia de bajada (1.536 Mbps),
y canal de subida (lóKbps) para control, en el cableado existente de par trenzado. No se
requiere de equipo adicional si el cliente se encuentra dentro de un radio de 5.5 kilómetros
de la oficina central. El costo en que incurre el usuario final es bastante bajo en este
esquema, ya que requiere muy pocos cambios al equipo existente.
HDSL. El lazo de abonado digital de alta velocidad (HDSL) permite una transmisión de
hasta 800 Kbps en distancias de hasta 5.5 kilómetros en las líneas de cobre existentes. Con
dos de estos circuitos en paralelo, esta tecnología puede soportar comunicación full-duplex
(1.544 Mbps).
Sonet. Sonet (Synchronous Optical NETwork) es una interfaz de transmisión óptica
estandarizada por el American National Standards Institute (ANSÍ). El estándar especifica
un formato de multiplexaje utilizando uno o mas canales de 51.84 Mbps y define el
estándar de señal óptica para conectar equipo. Esta tecnología provee una arquitectura
20
flexible que puede acomodar servicios futuros de banda ancha. La tasa de señalización
básica de 51.84 Mbps puede manejar tráfico de video digital con calidad HDTV.
En la Tabla 2 se resumen las principales tecnologías de acceso presentando la capacidad y el
medio de transmisión de cada una de ellas.
Tabla 2 Principales Tecnologías de Acceso
Tecnología de Acceso
ADSL
HDSL
CATV
Sonet
Capacidad
1.536Mbps (bajada)
1.544Mbps (Mi-dúplex)
45Mbps
Canales de 51.84 Mbps
Medio
Cobre
Cobre
Cobre
Fibra Óptica
Servicios de Comunicación
Un sistema VoD requiere de un alto grado de interconexión entre los usuarios y los
servidores de información. La naturaleza del tráfico de video requiere la transferencia de
grandes volúmenes de datos a muy altas velocidades. Muchos protocolos de comunicación
y arquitecturas de red se han propuesto para conectar los distintos componentes,
incluyendo:
• Asynchronous Transfer Mode (ATM)
• Fiber Distributed Data Interface (FDDI)
» Distributed Queue Dual Bus (DQDB)
• 100 Mbps Ethernet (IEEE 802.12)
Video sobre ATM [3]
Dado que ATM ha sido diseñado desde un principio para soportar el tráfico en tiempo real
y el tráfico de información, es un mecanismo de transporte ideal para video y audio en
tiempo real, incluyendo video a la demanda y videoconferencia, particularmente en
situaciones en donde el video es integrado dentro de un ambiente computacional.
21
Las aplicaciones de video que operan sobre ATM pueden ser agrupadas en tres categorías:
1. CODECs de video existentes de fabricantes como PICTURE-TEL y Compression
Laboratories que operan sobre redes de circuitos conmutados tradicionales utilizando
líneas de 64 Kbps o líneas de ISDN (banda estrecha): Este tráfico será transportado
sobre ATM utilizando servicios CBR, emulación de circuito y AAL 1.
2. Video paquetizado de redes heterogéneas: Aparte de los estándares de compresión de
video internacionales, se han introducido un número de algoritmos de compresión
propietarios (Quick Time de Apple, AVI de Microsoft e Indeo de Intel). En el corto
término, mucho de este tráfico de video será transportado en paquetes IP sobre AAL 5
sin hacer uso de las garantías de Quality of Service (QOS) disponibles en una red ATM.
3. Video paquetizado corriendo nativamente sobre ATM: Las aplicaciones de difusión de
video harán uso de nuevos CODECs de MPEG-2 diseñados para operar sobre AAL-5.
El foro ATM ha estandarizado un método para encapsular paquetes de transporte
MPEG-2 de 188 bytes en un PDU de AAL-5. Si dos paquetes de transporteson puestos
en un solo PDU, este será subsecuentemente separado en exactamente 8 celdas
consistiendo de 2 x 188 bytes mas 8 bytes (un total de 8 x 48 bytes) de overhead de
AAL-5 incluyendo un CRC de 32 bits y un indicador de la longitud de la carga útil.
Estas aplicaciones se encuentran en una posición tal que pueden emplear las garantías
de QoS provistas por la red ATM para soportar tráfico VBR que puede aproximarse a
una calidad constante en el video.
Las redes ATM están diseñadas para soportar todos los tipos de tráfico en un red de
servicios integrados, así como para operar a muy altas velocidades utilizando hardware de
conmutación dedicado, y están siendo ampliamente adoptadas tanto por operadores de
telecomunicaciones públicas y privadas, como por compañías de computadoras para la
construcción de redes LAN y MAN. Las redes ATM son muy adecuadas para la
transmisión de video. El video puede ser transmitido ya sea a una tasa de bit constante y
calidad variable o a una tasa de bit variable y una calidad constante. Los beneficios en la
forma de ganancia en el multiplexaje estadístico por el uso de una tasa de bit variable puede
estar disponible solamente sobre enlaces de alta capacidad ocupados en los que la razón de
22
capacidad de enlace a la capacidad pico del canal es grande. Esto es poco probable que
ocurra en muchas redes de área local ATM. Una investigación reciente se enfoca a la
transmisión de video sobre redes locales ATM mientras que la retroalimentación de la
congestión de la red se utiliza para modificar la tasa del video. Estas técnicas pueden
proveer una mejor calidad de video que la que se puede obtener de un CODEC CBR y una
utilización eficiente de la red.
Servidores de Video [4]
Actualmente, con la compresión MPEG-1 a 1.5 Mbps, una película de cerca de 90 minutos
de duración ocupa aproximadamente 1GB de espacio de almacenamiento. El almacenar tal
volumen de información en memoria resulta demasiado caro, a excepción de las películas
más frecuentemente pedidas. Para limitar los costos de almacenamiento, las películas son
típicamente almacenadas en discos. De hecho es posible almacenar las películas que no
gozan de mucha popularidad en cintas u otro tipo de medio terciario, sin embargo este tipo
de medios no es tan rentable como los discos aun para las películas accesadas no tan
frecuentemente.
Un servidor de video que almacene alrededor de 1000 películas (una tienda de renta de
video posee muchos más) tendría que gastar cerca de $100,000 dólares solamente para
almacenar las películas en disco a un costo de $0.10 / MB. Si se desea una calidad de
imagen superior y se utiliza MPEG-2 para la compresión a una tasa de 6 Mbps, el costo del
espacio en disco se incrementa casi cuatro veces. A esto falta agregar el costo del equipo
computacional requerido para almacenar la información. Sin embargo, el siempre
decreciente costo tanto del almacenamiento magnético (a razón de 50% cada 18 meses),
como del poder de cómputo (a razón de 54% cada año) hace que estas consideraciones de
costo sean un problema menor si los retos técnicos son superados.
La capacidad de almacenamiento y reproducción puede resaltar gran parte de los retos y
aspectos técnicos en la construcción de un servidor de video. Un servidor de video grande
puede ser organizado de manera distribuida. Un número de nodos actúan como nodos de
almacenaje. Dichos nodos son responsables del almacenamiento de la información de
23
video ya sea en memoria, disco, cinta u otro medio y entregar el ancho de banda de entrada
/ salida requerido por la información. El sistema también tiene nodos de red. Estos nodos
son responsables de pedir los bloques de datos apropiados de los nodos de almacenaje y
rutearlos hacia los clientes. Ambas funciones pueden residir en un mismo nodo de
multiprocesamiento, esto es, un nodo que puede ser un nodo de almacenaje, un nodo de red,
o ambos al mismo tiempo. El diseño de los nodos de red cambiará en base al medio de
entrega.
Para obtener un ancho de banda de entrada / salida alto, la información tiene que ser
separada (distribuida) en un cierto número de nodos de almacenaje. Si una película es
guardada completamente en un solo disco, el número de clientes que puedan pedir la
película será limitado por el ancho de banda del disco. Para poder servir un gran número de
streams de una sola película, cada película debe de ser distribuida en varios nodos.
Conforme se incrementa el número de nodos para la distribución, se incrementa el ancho de
banda para una película. Si todas las películas se distribuyen en todos los nodos, también se
puede mejorar el balance de la carga a través del sistema ya que cada nodo tiene que
participar para proveer acceso a la película. La unidad de distribución entre los nodos de
almacenaje es llamada bloque. En la literatura se reporta que un tamaño de bloque entre 64
y 256 kB es apropiado para entregar un ancho de banda alto en tiempo real del subsistema
del disco.
El servicio para un stream de video puede ser descompuesto en tres partes: (1) leer el
bloque requerido del disco al buffer en el nodo de almacenaje, (2) transferir este bloque del
buffer del nodo de almacenaje al buffer en el nodo de red y (3) entregar el bloque requerido
al usuario a través del medio de entrega. Los aspectos críticos en estos tres componentes
del servicio son el disk scheduling, la interconexión de la red, y las garantías de entrega.
24
Capítulo 3
Almacenamiento Magnético y Disk Scheduling
Uno de los componentes centrales de un sistema de video a la demanda es el medio
de almacenamiento de la información. La opción mas adecuada desde el punto de vista
costo/beneficio es el almacenamiento en medios magnéticos, más especificamente, en
discos duros.
Características de los discos duros
Los discos duros se componen de un mecanismo y un controlador. El mecanismo
está a su vez compuesto de elementos de grabación (los discos rotatorios y las cabezas que
los accesan) y elementos de posicionamiento (un brazo que se encarga de mover las
cabezas sobre la posición correcta junto con un sistema de seguimiento que se encarga de
mantenerlo en su lugar). El controlador de disco contiene un microprocesador, memoria y
una interfaz de bus. El controlador administra el almacenamiento y la recuperación de la
información y realiza el mapeo entre las direcciones lógicas y los sectores físicos del disco
en donde se encuentra la información.
Componentes de grabación
Un disco contiene uno, dos o hasta una docena de platos. La pila de platos rota
alrededor de un eje central. Las velocidades de rotación se han incrementado hasta las
7200 rpm (revoluciones por minuto). Una velocidad de rotación mayor incrementa las
tasas de transferencia y disminuye las latencias de rotación (el tiempo que le toma a la
información rotar hasta la cabeza), pero incrementa el consumo de energía y se requiere de
rodamientos muy precisos para el eje. La Figura 3 muestra los componentes principales de
un disco duro.
25
Plato
Eje í Cabeza (UE) .¿.-Brazo
I
\, _
~
Cilindro
Figura 3 Componentes de un disco duro
Cada superficie de un plato tiene una cabeza de disco asociada, la cual es
responsable de grabar (escribir) y sensar (leer) las variaciones de flujo magnético sobre la
superficie. El disco tiene un solo canal de lectura-escritura que puede ser conmutado entre
las cabezas. El canal es responsable de la codificación y decodificación del flujo de
información en o de una serie de cambios de fase magnética almacenados en el disco.
Componentes de posicionamiento
Cada superficie de información se configura de tal manera que se pueda almacenar
información en una serie de círculos concéntricos, o pistas. Una sola pila de pistas a una
distancia común del eje recibe el nombre de cilindro. Las pistas en cada plato deben de ser
consideradas independientes.
Sector Pista
Figura 4 Vista superior de un plato
26
Para accesar la información almacenada enuna pista, la cabeza del disco debe de ser
movida sobre ella y esto se realiza sujetando cada cabeza a un brazo. Todos los brazos del
disco se sujetan al mismo pivote de rotación, de tal manera que el movimiento de una
cabeza ocasiona que las otras también se muevan. El pivote de rotación es más inmune a
shocks lineales que los esquemas empleados anteriormente.
La tarea del sistema de posicionamiento es la de asegurar que la cabeza apropiada llegue a
la pista deseada lo más rápido posible y permanezca ahí aun en la presencia de vibración
extema, shocks, e imperfecciones del disco (pistas no concéntricas y no circulares)
Búsqueda (seeking). La velocidad del movimiento de la cabeza, o seeking, está limitada
por la potencia disponible para el motor del pivote (una reducción del tiempo de búsqueda
de un 50% requiere de cuadriplicar la potencia) y de la rigidez del brazo ya que dado que se
alcanzan aceleraciones de 30 a 40G, el brazo puede deformarse de tal manera que entre en
contacto directo con la superficie del plato.
Una búsqueda se compone de [6]
• Speedup, en donde el brazo es acelerado hasta que alcanza la mitad de la
distancia de búsqueda o una velocidad fija máxima.
• Coost, para búsquedas largas en las que el brazo se mueve a su velocidad
máxima.
• Slowdown, el brazo se lleva a descansar en un lugar cercano a la pista deseada.
• Settle, en donde el controlador del disco ajusta la cabeza para accesar la posición
deseada.
Las búsquedas muy cortas (2 a 4 cilindros) son dominadas por el tiempo de
establecimiento (settlé) (1-3 ms). Las búsquedas cortas (200 a 400 cilindros) se pasan la
mayor parte del tiempo en una fase de aceleración constante, y su tiempo es proporcional a
la raíz cuadrada de la distancia de búsqueda mas el tiempo de establecimiento. Las
búsquedas largas pasan la mayor parte del tiempo moviéndose a velocidad constante, y les
27
toma un tiempo que es proporcional a la distancia mas un overhead constante. Conforme el
tamaño del disco disminuye y las densidades de pista se incrementan, la fracción del tiempo
de búsqueda total atribuido a la fase de establecimiento se incrementa.
Track following. La función del sistema de seguimiento de pista es la de sintonizar de
manera precisa la posición de la cabeza al final de una búsqueda y mantener la cabeza en la
pista deseada.
El sistema de seguimiento también se usa para realizar una conmutación de cabeza.
Cuando el controlador cambia su canal de datos de una superficie a la siguiente en el
mismo cilindro, la nueva cabeza puede necesitar reposicionamiento para acomodar las
pequeñas diferencias en la alineación de las pistas en las diferentes superficies.
Data layout. Para el CPU, un disco aparece como un vector lineal de bloques
direccionables cuyos tamaños varían entre 256 y 1024 bytes. Estos bloques deben de ser
mapeados a sectores físicos del disco, los cuales son unidades de tamaño fijo de colocación
de información en los platos. Uno de los objetivos de la separación lógica y física del disco
es que el disco puede esconder sectores dañados y realizar optimizaciones de bajo nivel.
• Zoning. Resulta obvio que las pistas son mas largas al exterior del plato que en el
interior, por lo que para maximizar la capacidad de almacenamiento la densidad lineal
debe de permanecer cerca del máximo que el disco pueda soportar; por lo tanto, la
cantidad de información almacenada en cada pista debe de escalarse en proporción a su
longitud. Lo anterior se logra mediante una técnica llamada zoning, en donde los
cilindros adyacentes son agrupados en zonas. Las zonas cercanas al borde exterior
tienen más sectores por pista que las zonas en el interior. El número típico de zonas es
de 3 a 20. Dado que la tasa de transferencia de la información es proporcional a la tasa
a la que la información pasa bajo la cabeza, las zonas exteriores tienen tasas de
transferencias mas altas.
28
Controlador de Disco
El controlador del disco negocia el acceso al mecanismo, ejecuta el sistema de seguimiento,
transfiere la información entre el disco y el cliente, y en muchos casos, administra un cache
interno. Los controladores se construyen en base a microprocesadores especialmente
diseñados que poseen capacidades de procesamiento digital e interfaces especiales que les
permiten manipular el hardware directamente.
Modelado de discos [6]
Una vez conocidas las características físicas y tecnológicas de los discos es posible modelar
el comportamiento de los mismos. Los modelos de los discos duros han sido usados desde
que estos se emplean como medios de almacenamiento. Un modelado analítico preciso de
los discos no puede realizarse debido a su comportamiento no lineal y dependiente del
estado, por lo que mucho del trabajo en esta área utiliza la simulación. Sin embargo, los
modelos más sencillos simplemente asumen un tiempo fijo para una L/E o seleccionan
tiempos de una distribución uniforme. Los modelos más elaborados asumen que para
simular el tiempo necesario para realizar una operación de L/E es necesario considerar de
manera precisa el tiempo de búsqueda, el tiempo de transferencia y el retardo rotacional.
Parámetros de Desempeño del Disco
Los detalles de las operaciones de lectura y escritura de un disco dependen de la
computadora, el sistema operativo, y de la naturaleza del canal de E/S y del hardware del
controlador del disco.
Cuando la unidad de disco se encuentra trabajando, el disco rota a una velocidad constante.
Para leer o escribir, la cabeza debe de ser posicionada en la pista deseada y al principio del
sector deseado de esa pista. La selección de la pista involucra el mover la cabeza en un
sistema de cabeza móvil o de seleccionar electrónicamente una cabeza en un sistema de
cabeza fija. En un sistema de cabeza móvil, el tiempo que toma para posicionar la cabeza
29
en la pista se conoce como tiempo de búsqueda (seek time). En cualquier caso, una vez que
la pista es seleccionada, el controlador del disco espera hasta que el sector apropiado rota
para alinearse con la cabeza. El tiempo que le toma al principio del sector alcanzar la
cabeza se conoce como retardo rotacional (rotational delay), o latencia rotacional. La suma
del tiempo de acceso, si es que existe, y del retardo rotacional es el tiempo de acceso (i.e. el
tiempo que toma estar en posición para leer o escribir). Una vez que la cabeza se encuentra
posicionada, la operación de lectura o escritura se realiza conforme el sector se sitúa bajo la
cabeza; ésta es la parte de transferencia de datos de la operación.
Tiempo de Búsqueda
El tiempo de búsqueda es el tiempo requerido para mover el brazo del disco a la pista
requerida. El tiempo de búsqueda consiste a su vez de varios componentes clave: el
tiempo inicial de arranque, y el tiempo que toma atravesar los cilindros que tienen que ser
cruzados una vez que el brazo de acceso se encuentra listo. Desafortunadamente, el tiempo
de travesía no es una función lineal del número de pistas. Resulta posible aproximar el
tiempo de búsqueda con la Ecuación 1, donde a y b son parámetros dependientes de las
características del disco en cuestión y dis es la distancia en cilindros.
O si dis = O
tseek = I (1)
la + b * dis si dis * O
Retardo Rotacional
Por lo general, los discos rotan a 3600 rpm, lo cual es una revolución cada 16.7 ms. Por lo
tanto, en promedio, el retardo rotacional será de 8.3 ms.
Tiempo de Transferencia
El tiempo de transferencia hacia o desde el disco depende de la velocidad de rotación del
disco de la siguiente forma:
30
Tamaño del bloque a transferir
transferencia — " —'
Razón de transferencia de información
El tamaño del bloque a transferir se expresa en bytes y la razón de transferencia de
información se puede obtener con la velocidad de rotación del disco y de la capacidad de
una pista del disco en bytes.
Por lo tanto, el tiempo de acceso promedio total puede ser expresado como
tacceso = tseek + transferencia + latenClü rOtüCÍOnal(3)
Políticas de Disk Scheduling [16]
En la literatura se han propuesto varias políticas de scheduling para manejar una fila
de peticiones en una cabeza de disco móvil. Entre estas políticas se encuentran: Shortest-
seek-time-first (SSTF), SCAN, N-step SCAN, CSCAN y el esquema Eschenbach. Estos
métodos representan una mejora sobre la política de first-come-first-serve (FCFS).
FCFS First Come First Serve. La forma más sencilla de disk scheduling es first-come,
first-serve (FCFS). Este algoritmo es intrínsecamente justo, pero por lo general no provee
el servicio más rápido. El algoritmo no es óptimo con respecto al movimiento de la cabeza
ya que no considera la posición de las peticiones pendientes y esto ocasiona un tiempo de
búsqueda promedio alto. Considérese, por ejemplo, una cola del disco con peticiones de
E/S para bloques en los cilindros 55, 58, 39, 18, 90, 160, 38, 184. Suponiendo que la
cabeza del disco se encuentra inicialmente en el cilindro 100, ésta se moverá del 100 al 55,
y luego del 55 al 58, 39, 18, 90, 160, 38 y finalmente al 184 para una longitud de búsqueda
total de 498 cilindros y una longitud de búsqueda promedio de 55.3 cilindros (Figura 5).
31
0 18 3839 55 58 90 100 160 184 200
SCAN. Este método de acceso puede ser visto como el método básico de mejorar la
eficiencia de la fila del disco ya que las políticas mencionadas anteriormente pueden dejar
algunas peticiones pendientes hasta que la cola se vacía completamente. Con este
algoritmo, el brazo del disco barre todos los cilindros de afuera hacia adentro y de regreso,
atendiendo las peticiones. La dirección del movimiento cambia solamente en el cilindro
más interno y el más extemo (Figura 7). SCAN fue propuesto como una alternativa a SSTF
ya que no permite la discriminación que ocurre en SSTF. Existe un refinamiento a este
algoritmo y recibe el nombre de LOOK y consiste en satisfacer todas las peticiones
pendientes en una dirección hasta que no haya más en esa dirección, y entonces cambiar la
dirección del barrido.
O 18 3839 55 58 90 100 160 184 200
Figura 7 Ejemplo del movimiento de la cabeza bajo SCAN
Circular SCAN (C-SCAN). Este algoritmo es una variante de SCAN y está diseñado para
proveer un tiempo de espera más uniforme. Como SCAN, C-SCAN mueve la cabeza del
disco de un extremo a otro del disco, dando servicio a las peticiones que se encuentran en la
dirección del barrido. Sin embargo, cuando la cabeza llega al extremo extemo del disco,
ésta regresa al extremo interno sin atender peticiones de regreso. El algoritmo C-SCAN
trata a los cilindros como una lista circular que se cierra del último cilindro al primero. El
comportamiento de este algoritmo reduce el máximo retardo experimentado por nuevas
peticiones. Con SCAN, si el valor esperado del tiempo para un barrido del cilindro interno
al cilindro externo es t, entonces el intervalo de servicio esperado para los sectores en la
periferia es 2t. Con C-SCAN, el intervalo es del orden de t+sma, donde smax es el tiempo
máximo de búsqueda. Del ejemplo de peticiones anteriores, y asumiendo que la dirección
de la cabeza es hacia el cilindro extemo, el algoritmo atendería las peticiones de la
33
siguiente forma: 160, 184, 18, 38, 39, 55, 58, y 90 (Figura 8). La longitud total de la
búsqueda es de 323 cilindros con una longitud de búsqueda promedio de 35.8 cilindros.
O 18 3839 55 58 90 100 160 184 200
Figura 8 Ejemplo del movimiento de la cabeza con CSCAN
N-STEP SCAN. El propósito de este algoritmo es decrementar la varianza de los tiempos
de espera individuales sin degradar de manera significativa el throughput. Este algoritmo
segmenta la cola de peticiones del disco en subcolas de longitud N. Las subcolas se
procesan una a la vez, utilizando SCAN. Mientras que una cola es procesada, las nuevas
peticiones deben de ser agregadas a alguna otra cola. Si menos de N peticiones se
encuentran disponibles al final de un barrido, entonces todas ellas son procesadas con el
siguiente barrido. Resulta claro que para valores grandes de N, este algoritmo se aproxima
a SCAN, mientras que para N=l, este algoritmo se traduce en FCFS.
ESCHENBACH [15]. El esquema Eschenbach es un técnica de barrido determinística
diseñada para sistemas de conmutación de mensajes los cuales operan normalmente bajo
condiciones de carga pesadas. Un barrido Eschenbach de orden E se define como E
revoluciones por cilindro, con m/E sectores atendidos por revolución (m = número total de
sectores por pista). En este tipo de barrido, E - 1 sectores son evitados por cada sector
atendido. Este esquema posee optimización rotacional en el sentido que dentro de una
rotación dada se atiende al mayor número de sectores posible y de que el servicio se entrega
en la secuencia en que los sectores son encontrados.
Los resultados arrojados en la literatura muestran que FCFS no realiza optimización alguna;
SSTF, SCAN y N-step SCAN tienden a optimizar los tiempos de búsqueda y el esquema
Eschenbach tanto tiempos de búsqueda como de rotación.
34
Dada la naturaleza del video, los algoritmos convencionales de disk-scheduling no cubren
por completo los requerimientos de un servidor multimedia, por lo que se han propuesto
nuevos algoritmos que buscan satisfacer las necesidades de los clientes.
La adición de restricciones de tiempo real hace que la aplicación directa de los algoritmos
tradicionales sea inadecuada.
Algoritmos de Disk-Scheduling para sistemas Multimedia
Dado que un algoritmo de scheduling debe de ser justo y evitar la hambruna de
servicio de peticiones, los algoritmos de SSTF no son considerados. La política de
scheduling debe de proveer un tiempo de respuesta bajo para peticiones aperiódicas al
mismo tiempo que cumple con los requerimientos de las peticiones de tiempo real.
EDF Earliest Deadline First. Este algoritmo es óptimo si los tiempos de servicio de las
peticiones son conocidos a priori. Sin embargo, el tiempo de servicio del disco para una
petición depende en su posición relativa a la posición actual de la cabeza de L/E. EDF le
da a cada petición de tiempo real un deadline y atiende las peticiones en estricto orden. Un
scheduling de tiempo real estricto puede resultar en un costo excesivo de tiempo de
búsqueda y en una utilización pobre del disco
SCAN-EDF [12]. Este es un algoritmo híbrido que provee tanto optimización de búsqueda
como servicio de earliest deadline. Las peticiones son atendidas normalmente en orden
EDF. Si varias peticiones tienen el mismo deadline, estas son servidas de acuerdo a la
posición de la pista en el disco.
Dado que SCAN-EDF aplica optimización de búsqueda solamente a las peticiones que
tienen el mismo deadline, su eficiencia depende de que tanto la optimización de búsqueda
pueda ser aplicada.
35
Este algoritmo presume que las peticiones tienen tiempos de atención que son múltiplos del
período p. Por lo tanto, las peticiones son agrupadas en lotes y atendidas similarmente.
Cuando las peticiones tienen diferentes requerimientos de tasas de datos, SCAN EDF puede
ser combinado con una política de llenado periódico para dar a todas las peticiones el
mismo deadline. Las peticiones son atendidas en un ciclo, y cada petición tiene un tiempo
de servicio proporcional a su tasa de datos requerida. La longitud del ciclo es la suma de
todos los tiempos de servicio de todas las peticiones. A todas las peticiones en el ciclo
actual se les da un deadline al final del ciclo.
Una descripción del algoritmo es dada a continuación:
Paso 1: Sea T = conjunto de tareas con el deadline mas cercano
Paso 2: Si |T| = 1 (solamente hay una petición en T), atender esa petición
Sino sea t¡ la primera tarea en T en la dirección del barrido, atender t¡.
Ir al Paso 1.
Esta algoritmo también puede ser implementado con una ligera modificación a EDF.
Existen otros enfoques al problema de disk scheduling que procesan las peticiones en
rounds. Durante cada round, el servidor puede recuperar una secuencia de bloquespara
cada flujo. El procesamiento de las peticiones en rounds es más que una conveniencia ya
que al hacerlo, se explota la naturaleza periódica de la reproducción de medios continuos.
En cada round, un algoritmo de disk scheduling debe de ser seleccionado. La más sencilla
de tales técnicas es algoritmo de round-robin, el cual atiende a los clientes por turnos,
utilizando un orden fijo que no varia de un round al siguiente. Sin embargo, la mayor
desventaja de este enfoque es que no aprovecha las posiciones relativas de los bloques de
información que son extraidos durante un round. Por esta razón, los algoritmos de
colocamiento de información que reducen de forma inherente los retardos son empleados
en conjunción con el scheduling de round-robin.
36
Para eliminar los retardos en cada round, es posible aplicar simplemente el algoritmo
SCAN. Para los servidores de medios continuos (CM), unas alteraciones mínimas a SCAN
pueden resultar en una minimización de los retardos de búsqueda, y por lo tanto de la
longitud del round. Sin embargo, la minimización de la longitud del round no es el único
asunto involucrado en un servidor CM. En el caso del algoritmo de round-robin, el orden
en que los clientes son atendidos es fijo a través de los rounds. Por lo tanto, la separación
máxima entre los tiempos de extracción de peticiones sucesivas de un cliente está limitada
por la duración del round. Sin embargo, empleando SCAN, el orden relativo para atender
clientes se basa exclusivamente en el colocamiento de los bloques que van a ser
recuperados, por lo que es posible que un cliente reciba servicio al principio de un round y
luego al final del siguiente round.
Esta diferencia tiene algunas implicaciones en términos de retraso en el inicio de la
reproducción y de requerimientos de memoria. Para round-robin, es posible iniciar la
reproducción inmediatamente después de que todos los bloques de la primera petición han
sido recuperados. Sin embargo, con SCAN, la reproducción debe de esperar hasta el final
del round. Para prevenir la hambruna, el algoritmo de round-robin necesita suficiente
espacio de memoria para satisfacer el consumo por la duración de un round, mientras que
SCAN necesita de un espacio suficiente en el buffer para satisfacer el consumo durante
aproximadamente dos rounds. Sin embargo, los rounds en SCAN serán más cortos, por lo
que existe un compromiso entre la longitud del round y el número de rounds entre servicio
sucesivo.
Para aprovechar este compromiso, una generalización conocida como Grouped Sweeping
Scheme (GSS) particiona cada round en un número de grupos. Cada cliente es asignado a
un cierto grupo y los grupos son atendidos en un orden fijo en cada round. Para cada grupo
se emplea el algoritmo SCAN. Si todos los clientes son asignados al mismo grupo, GSS se
reduce a SCAN. Por otro lado, si a cada cliente se le asigna su propio grupo, GSS degenera
en round-robin. Mediante una derivación óptima del número de grupos, el servidor puede
balancear la reducción de la longitud del round contra el número de rounds entre servicio
sucesivo.
37
Configuraciones de Múltiples Discos [1]
En las secciones anteriores se ha considerado que el servidor de video cuenta con un solo
disco. Si un archivo completo de multimedia es almacenado en un solo disco, el número de
accesos concurrentes a dicho archivo esta limitado por el throughput de ese disco. Para
atacar este problema se podría considerar mantener copias del archivo en discos diferentes.
Sin embargo, este enfoque resulta muy caro ya que requiere de espacio de almacenamiento
redundante. Una visión más efectiva consiste en esparcir el archivo en múltiples discos.
Esta dispersión puede lograrse empleando dos técnicas: "data striping" y "data
interleaving".
Data Striping. La tecnología RAID (Redundant Array of Inexpensive Disks) ha
popularizado el uso del acceso paralelo a un arreglo de discos. Bajo este esquema, la
información es dispersada a través de cada disco. En esta configuración, los discos en el
conjunto están sincronizados respecto al eje y operan en un modo paralelo con candado de
paso. Dado que los accesos se realizan en paralelo, el tiempo de acceso es el mismo para
un bloque lógico y un bloque físico. Por lo tanto, la tasa de transferencia efectiva se
incrementa por el número de discos involucrados. Por lo anterior, los arreglos de discos
son una buena solución al problema de los requerimientos de un ancho de banda grande.
Data Interleaving. En este esquema, los bloques del archivo son almacenados de manera
intercalada a través del conjunto de discos. Los bloques sucesivos del archivo son
almacenados en discos diferentes. Un patrón sencillo de intercalado se obtiene
almacenando los bloques de una forma cíclica a lo largo del conjunto de N discos. En este
esquema, los discos en el conjunto no están sincronizados y operan independientemente.
38
Capítulo 4
Simulación
Para este trabajo se estudiará el comportamiento de cuatro algoritmos conocidos de disk
scheduling suponiendo que se trabaja con video comprimido con MPEG2. Los cuatro
algoritmos que se estudiarán son FCFS, LOOK, C-LOOK y SCAN-EDF.
Para comparar estos algoritmos se tomarán en cuenta estadísticas como el tiempo promedio
de respuesta y el tiempo promedio de espera para diferentes tasas de arribo de peticiones.
La tasa de arribo de peticiones será Poisson y el tiempo de servicio de las peticiones será
calculado como se menciona en una sección posterior.
Dado que el tiempo de servicio se encuentra relacionado con el tipo de información que
será extraído del disco, resulta necesario conocer las estadísticas principales del formato de
compresión MPEG2, las cuales se presentan en este capítulo.
Algoritmos de Disk Scheduling
A continuación se resumen algunas de las características de los cuatro algoritmos de
scheduling presentando sus características principales y algunos resultados conocidos de la
literatura.
FCFS
El algoritmo FCFS es el algoritmo más sencillo de todos, ya que atiende las peticiones
conforme fueron llegando. Este algoritmo no realiza optimización alguna y servirá como
punto de comparación para evaluar el desempeño de los demás algoritmos.
LOOK
39
El algortimo LOOK es una variante del algoritmo SCAN y la diferencia radica en el hecho
de que LOOK no recorre todos los cilindros del disco atendiendo peticiones sino que "ve"
las peticiones y determina cuándo es necesario regresar el brazo del disco para volver a
barrer el disco atendiendo peticiones en sentido opuesto al original.
C-LOOK
El algoritmo C-LOOK es una variante del algortimo LOOK y la diferencia radica en que
cuando no existen más peticiones que atender en cierta dirección, la cabeza del disco
regresa al inicio de la lista de peticiones (si estas se ordenan en orden ascendente) y va
barriendo el disco atendiendo las peticiones.
SCAN-EDF
El algoritmo SCAN-EDF es un algortimo que toma en cuenta la existencia de un deadline
para el servicio de peticiones en tiempo real. Cuando existen peticiones con el mismo
deadline, éstas son atendidas con política SCAN.
A continuación se presenta una breve descripición del desempeño de estos algoritmos como
se ha reportado en la literatura.
Uno artículo muy conocido en la literatura de disk scheduling es [15]. En dicho trabajo se
hace un análisis comparativo de cinco algoritmos de disk scheduling (FCFS, SSTF, SCAN,
ESCHENBACH, N-step SCAN) y se discute la interrelación de los mismos en lo que se
refiere a ciertas medidas de desempeño como son el tiempo de búsqueda promedio, el
tiempo de espera promedio y la varianza del mismo. En este artículo la variable controlada
es la tasa de arribos ya que, a juicio de los autores, es una mejor representación de las
condiciones de carga.
En el artículo se asume lo siguiente:
• Se considera un solo disco
40
• Las peticiones para registros de un mismo tamaño se distribuyen de manera
uniforme sobre todo el disco. Cada pista contiene