ALGORITMOS PARA ENCRIPTACI?N DE DATOS

3.2.3 Algoritmo para la optimización de recursos de red a través de una envolvente empírica

3.2.3.1 Introducción a la optimización del ancho de banda

El algoritmo de envolvente empírica fue estudiado del trabajo presentado por Enrique Hernández Orallo en su tesis doctoral, debido a que no existen fuentes bibliográficas tan completas como este estudio. Lo que se toma de este trabajo es la metodología de investigación para mostrar los avances que existen en el campo de la Optimización del Ancho de Banda.

En este apartado se aborda la optimización del ancho de banda reservado en los enlaces, utilizando el concepto de los puntos envolventes. Para realizar esta optimización se establece una condición: es necesario conocer el tráfico que se va a transmitir. Por ello, se plantea su utilización en la transmisión bajo demanda2, siendo también aplicable a otros tipos de transmisión.

Para establecer un canal3 habrá que reservar una serie de recursos en la red para asegurar que la transmisión se realiza con una determinada calidad de servicio. Es importante, para ahorrar recursos en la red, que la reserva de los recursos sea óptima. En general, se tiene un tráfico que sufre variaciones de ancho de banda en función del tiempo, lo que se denomina tráfico VBR (Variable Bit Rate). A la hora de transmitir este tráfico, se necesita un modelo que limite esta transmisión.

El modelo de tráfico más usado es el Leaky Bucket (s,.)4 donde el emisor no puede transmitir en el periodo [ 0,t ] más de s + .t bits. A partir de esta restricción y con los parámetros de la red se han desarrollado un conjunto de ecuaciones5 que nos permiten calcular el retraso del emisor al receptor a partir de una reserva de recursos de red realizada en los nodos. Para mayor detalle del desarrollo de estas ecuaciones ver Anexo

3.1 apartado 3.1.1 .

3.2.3.2 Objetivo de la Optimización

Cuando se reservan los recursos en la red para un determinado canal los parámetros de la red6 se conocen y son fijos. El problema reside el obtener los parámetros que caractericen el flujo y la optimización de la reserva de los recursos en la red. Como se muestra posteriormente, es iterativo y costoso, además de que se tiene que repetir para cada transmisión de un mismo video. Es costoso porque implica recorrer dicho vídeo para determinar los parámetros en cada iteración (por ejemplo, si se transmite una película se tendrá que recorrer 100 minutos de imagen que son unos 2 Gbytes).

2 Es un tipo de transmisión, en donde una serie de servidores conectados a la red permiten acceder en tiempo real a cualquier película, vídeo, música, etc., que nos interese. El cliente recibirá la película en su computadora y/o decodificador.

3 En general el medio (físico o virtual) por el que se realizan las comunicaciones se suele denominar canal. Estos canales son definidos con unos parámetros típicos como pueden ser el ancho de banda, retraso, variación del retraso (delay jitter) y fiabilidad.

4 Es un modelo de tráfico (algoritmo) que regula el tráfico y emplea dos parámetros para describir dicho algoritmo: la capacidad del cubo s (bits) y la tasa de drenaje .

(bits/s). Lo anterior fue descrito en el Capitulo II de este trabajo.

5 Entre estas ecuaciones, las más conocidas y las utilizadas en este trabajo son las basadas en el trabajo de Parekh y Gallager [Parekh92][Parekh93].

6 Cómo parámetros de red tenemos: enlaces, ancho de banda de los enlaces y MTU (Unidad máxima de transmisión).

En consecuencia, se propone un método alternativo basado en un proceso denominado envolvente empírica en el que se generan off-line una serie de puntos para cada vídeo que definen la carga. Y utilizando estos puntos, se puede realizar on-line este mismo cálculo de una forma muy rápida y directa.

3.2.3.3 Cálculo del retraso emisor – receptor

El retraso de emisor a receptor se calcula normalmente a partir de una descripción de la red y un modelo del tráfico, siendo normalmente función de la reserva realizada en los nodos. Para este fin y para un servicio garantizado7 se utiliza el otro modelo de tráfico Token Bucket8 (b,r,p) en donde el número de bits que la fuente puede transmitir es menor que b+rt para cualquier intervalo de t9. Para la obtención del retraso se utilizan las ecuaciones (1 y 2) descritas en el Anexo 3.1 apartado 3.1.1.

De las ecuaciones de retraso descritas en el Anexo 3.1 (1, 2 y 3) se obtiene que el retraso es inversamente proporcional a la reserva de ancho de banda a realizar. Esto implica, que para que una conexión obtenga un retraso pequeño tiene que reservar un ancho de banda elevado, incluso mayor que la tasa pico. Esto puede provocar que se desperdicien recursos cuando una conexión que necesita retrasos pequeños tenga poco tráfico.

Es importante resaltar que las ecuaciones descritas en el Anexo 3.1 (1, 2 y 3) no consideran a la latencia, por lo que hay que agregar la latencia mínima de la red para calcular el retraso total. La latencia mínima es fija y dependerá principalmente de los medios de transmisión físicos, que normalmente suele ser despreciable respecto al retraso en red, aunque este valor puede ser importante en enlaces transoceánicos o vía satélite (por la distancia de estos enlaces).

En el caso que fuera necesario considerar la latencia mínima, se restará al retraso pedido esta latencia y se utilizarán las ecuaciones descritas en el Anexo 3.1 (4 y 5).

7 Es la calidad de servicio destinada para aplicaciones con requerimientos exigentes de tiempo real. Esta calidad asegura: un ancho de banda, un límite en el retraso y ninguna pérdida en las colas.

8 Es otro modelo de tráfico cuyo objetivo de este algoritmo es permitir transmitir a mayores velocidades cuando la fuente recibe un pico (p); donde “b” es la cantidad máxima de tokens permitidos en el cubo y “r” es la tasa de generación de tokens. Para mayor referencia ver Capítulo II de este trabajo.

- Realmente si se establece una tasa pico p, el tráfico no puede exceder min[pt, b+rt].

En forma concreta, para calcular la reserva de recursos se necesita:

- Un modelo de la red, para obtener los parámetros de red Ctot10, Dtot y M11, que son determinados, y

- Calcular los parámetros del flujo (s,.)12. De estos parámetros, la tasa pico es de cálculo directo y determinado. El problema es cómo calcular los parámetros s y para optimizar la reserva13.

3.2.3.4 Optimización de la reserva del ancho de banda

Las secuencias en un vídeo constan de n tramas, donde en cada trama i se transmiten una serie de bits Ei. La transmisión de vídeo está limitada por un conformador de tráfico Leaky Bucket14 donde no se puede transmitir s+.t bits para un tiempo t. La obtención de la reserva óptima del ancho de banda varía para distintos pares de valores s y ., en donde se obtienen cálculos de retrasos diferentes. Es decir a mayor capacidad de s tenemos una menor tasa de transferencia . para un valor determinado de retraso implicando ello una mayor reserva. Y visceversa a menor capacidad de s se tiene una mayor tasa de transferencia . para el mismo valor de retraso dando ello una menor reserva. Por esta diferencia tan grande en los cálculos de reserva, se emplea un método iterativo para encontrar los valores de s y . que permitan encontrar los valores óptimos de la reserva. El desarrollo y la comprobación de este método viene descrito en el anexo 3.1 apartado 3.1.2.

Hernández Orallo demuestra que la reserva óptima (ancho de banda “R”) ocurre cuando la reserva es igual a la tasa de drenaje ..bucket como los parámetros b y r de token bucket.

3.2.3.5 Descripción del método para la reserva óptima en línea de recursos.

3.2.3.5.1 Introducción

Como se ha visto en el punto anterior es necesario obtener los valores s, .que optimicen la reserva de recursos, es decir, que cumplan con lo que establece la ecuación (9) descrita en el anexo 3.1. Para ello, en este punto se emplea un proceso denominado envolvente empírica con el objeto de obtener una información condensada, que permita optimizar la reserva.

Esta información condensada se concreta en lo que se ha denominado puntos envolventes. A partir de los puntos envolventes se describe un método rápido para obtener la reserva óptima.

Cualquier recta l(t) que contenga a la envolvente empírica estará definiendo los parámetros s, del Leaky Bucket y por definición estará limitando el tráfico como se puede ver en la Figura 3.1. Gráficamente, se puede ver, que para una misma envolvente empírica se pueden ajustar dos rectas l1(t) y l2(t), lo que proporciona dos pares de valores s y ..

Como se ha visto en el punto anterior el valor de s se calcula en función de la carga y de la tasa .. Por ejemplo, si tenemos el siguiente tráfico {1, 2, 0, 4, 2, 0, 1}, los valores de s para los siguientes valores de .

Para cada valor de se define por tanto una función de tráfico limitado l(t). En la Figura 3.2 se tiene la envolvente empírica sobre el tráfico y las rectas anteriores. Como se puede observar, las cuatro rectas tocan la envolvente empírica pero sin cortarla en ningún punto. Por la definición de la envolvente empírica toda recta l(t) que toque sin cortar será la mejor aproximación al tráfico y el valor en el origen será s. El objetivo, por tanto, es obtener el conjunto de todas estas rectas.

Viendo la figura se puede intuir como obtenerlas: las rectas tocan a la envolvente empírica sólo en determinados puntos: el 1, 2, 5 y 7. La obtención de estos puntos servirá para calcular todas las rectas l(t).

3.2.3.5.2 Cálculo de los puntos envolventes

La obtención de estos puntos se describe en el anexo 3.1. apartado 3.1.3 y permite obtener todas las posibles rectas l(t) que mejor se ajustan a la envolvente empírica. Y de los resultados obtenidos permiten el desarrollo de un algoritmo para determinar los puntos envolventes. La complejidad de este algoritmo es de O(n*m) donde n son los valores de t15 y m los puntos obtenidos. Dicho algoritmo es descrito en anexo 3.1. apartado 3.1.3

3.2.3.5.3 Obtención de la reserva óptima

Para la obtención de la reserva óptima de los recursos, se utiliza los puntos envolventes y con estos puntos se obtienen las rectas envolventes. La demostración de este apartado se detalla en el Anexo 3.1.

Apartado 3.1.3

15 t es el intervalo de tiempo del tráfico.

Conociendo el intervalo en donde se encuentra la raíz (R=.) se puede obtener directamente el valor de R. La búsqueda del intervalo es fácil y acotado: se puede hacer una búsqueda binaria en los puntos envolventes hasta encontrar el intervalo. Cuando se encuentra el intervalo se aplica el teorema 3 (el cual viene desarrollado en el Anexo 3.1 apartado 3.1.3) para la obtención de R. Un algoritmo para encontrar la solución se detalla Anexo 3.1. El costo de encontrar la solución es muy rápido, con un costo computacional de O (log m), el valor de m es pequeño (entre 20 y 100 puntos para el vídeo analizado en este trabajo).

La reserva mínima de buffer en los nodos puede ser calculada usando las ecuaciones descritas en el Anexo 3.1 (apartado 3.1.1). El algoritmo descrito optimiza la reserva de ancho de banda dando un valor mínimo de s para un retraso especificado. Si la restricción se impone en el tamaño del buffer, esto implica una limitación en el valor de s y por tanto la reserva debe ser calculada empleando las ecuaciones descritas en Anexo 3.1 (4 y 5) directamente.

Resumiendo, el proceso completo está esquematizado en la Figura 3.3 y se compone de dos fases diferenciadas. La primera fase, que es la más costosa, se puede realizar en el momento que se planee introducir el vídeo en el servidor. La segunda fase ocurre cuando se establece un canal para la transmisión del vídeo. Detallando los procesos en cada fase sobre las Figuras 3.3 y 3.4

FASE I: El objetivo es calcular los puntos envolventes a partir del vídeo almacenado. Para ello, (a) se calcula la envolvente empírica a partir del vídeo, y (b) aplicando el algoritmo descrito en el Anexo 3.1 (Figura 3.1.6) se obtienen los puntos envolventes y se almacenan en un archivo que estará asociado al vídeo. El proceso más costoso de esta fase es el cálculo de la envolvente empírica que es de O(n2). Existen otros algoritmos más eficientes para calcular la envolvente empírica, pero dado que son procesos off-line no se consideraron.

FASE II: empieza cuando se establece un canal para la transmisión del vídeo. En esta fase un cliente (c) pide ver un vídeo iniciando el establecimiento de un canal con unas características determinadas, (d) en el servidor se calcula la reserva usando el algoritmo de la Figura 3.1.8 del Anexo 3.1 sobre los puntos envolventes calculados en la fase anterior y (e) se reservan los recursos calculados en la red empezando a continuación la transmisión. El costo de obtener la solución es, como se ha visto, de O(log m).