ALGORITMOS PARA ENCRIPTACIÓN DE DATOS

ALGORITMOS PARA ENCRIPTACI?N DE DATOS

Vega Lebrún Carlos
Arvizu Gutiérrez Diego
García Santillán Arturo

Volver al índice

 

 

 

ANEXOS

Anexo 3.1 Desarrollo y obtención de la reserva óptima

3.1.1 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 garantizado se utiliza el otro modelo de tráfico token bucket1- (b,r,p) en donde el número de bits que la fuente puede transmitir es menor que b+rt para cualquier intervalo de t20. El retraso en la cola se calcula por medio de las siguientes ecuaciones:

Si el tráfico está limitado por un flujo leaky bucket se tiene que (s, .) l(t) = s+.t, entonces el retraso máximo entre emisor y receptor para la sesión i es:

donde Li es el tamaño máximo del paquete para la sesión i, Lmaxj es el tamaño máximo del paquete en el nodo j, Cj el ancho de banda del nodo j y n el número de nodos21. Esta ecuación es equivalente a (1) cuando la tasa pico p tiende a infinito (los parámetros r y b son equivalentes a los s y ., Li = M22 y Lmaxj = MTUj). El tamaño del buffer en el nodo j será s+jLi

1- 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.

Como el objetivo es calcular la reserva a partir del retraso exigido, en las ecuaciones (1) y (3) se puede despejar R (ancho de banda) quedando:

3.1.2 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 leaky bucket23 donde no se puede transmitir s+.t bits para un tiempo t. Si la tasa de transmisión del cubo es .

y el número de tramas por segundo es ƒ entonces el número de bits que tiene el cubo en la trama i, ignorando la capacidad finita del cubo es:

Por lo tanto, el tráfico será conforme si se escoge la capacidad del cubo s tal que si <= s . i Se puede expresar s como función de .:

La Figura 3.1.1 representa el tráfico denominado LAMBS15009. En la figura

3.1.2 se muestran los valores de si en función del tiempo para una tasa .de 1Mb/s.

Se comprueba que para distintos pares de valores s, .se obtiene un cálculo del retraso diferente. Usando, por ejemplo, la red de la Figura 3.1.4, se tiene que los parámetros asociados a la red son Dtot = 0.0045s y Ctot = 40000b. Usando la ecuación (1) con el tráfico LAMBS1500 para un primer par de parámetros .1 =

240,000 b/s, s1 = 1,464,008 b la reserva para un retraso de 0.1s es de 2,008,63- b/s. Para el par .2 = 590,000 b/s, s2 = 64,392 b la reserva para el mismo retraso es de 961,627 b/s. Se obtiene que las reservas difieren mucho.

Cómo el objetivo es optimizar la reserva R en la red, empleando las ecuaciones

(4) ó (5) y utilizando un método iterativo para encontrar los valores de . y s que optimicen la reserva, tenemos que el valor de .

puede variar entre 0 y .. El cálculo de s depende del valor de . y es una función decreciente. Aunque s(.) en principio no es continua, debido a que el cálculo se realiza usando números enteros, para poder iterar se usa la misma ecuación (7) con todos sus parámetros reales devolviendo un valor s real.

Sustituyendo en (4) y (5) los valores de r y b por .y s(.) quedan las siguientes funciones que calculan la reserva R en función de .:

En Hernández Orallo se demuestra que la reserva óptima ocurre cuando R(.) = ., es decir, cuando la reserva es igual a la tasa de drenaje .. Además, se demuestra que este valor .minimiza R’ (.) y que por tanto R(.) = R’(.) = .. Esto simplifica, por tanto, la búsqueda de la reserva óptima al poder utilizar la ecuación (9), que es más simple, para ambos modelos de tráfico.

3.1.3 Cálculo de los puntos envolventes

Como se intuye en el punto anterior la obtención de estos puntos permitirá calcular todas las posibles rectas l(t) más ajustadas a la envolvente empírica. Para ello, en este punto se introduce el concepto de puntos envolventes. Antes de desarrollar los puntos envolventes es necesario definir el concepto de “rectas envolventes” que es una formalización del conjunto de rectas más ajustadas o próximas a la envolvente empírica.

Si una función l(t)=s + st describe el tráfico, cualquier función l(t) (se denomina al conjunto de estas rectas l*(t)) tendrá que contener E(t). Esto es:

Definición: Se llaman rectas envolventes al conjunto de rectas l(t) que contiene E(t) tal que no existe otra recta l’(t) con la misma pendiente y l’(t)<l(t).

Las rectas envolventes están definiendo en origen el valor s para la pendiente ..

Es decir, a partir de las rectas envolventes se puede obtener el valor s en función de ., como se verá en este punto y el siguiente. Para obtener estas rectas envolventes se utilizarán los puntos envolventes.

Si E(t) fuese una función continua se podrían calcular las rectas tangentes para cualquier valor de t y tendríamos el conjunto de rectas l(t) más próximas. Dado que E(t) es creciente, las pendientes en cualquier punto de la curva serían positivas:

pero esto no significa que las pendientes sean siempre decrecientes. Esto implica que alguna de las rectas anteriores cortarán E(t) y no cumplen la condición (10). Para que las rectas tangentes a una función creciente no corten a ésta en un intervalo definido y estén siempre por encima, está función tendría que ser cóncava por debajo. Si E(t) cumpliese esta condición se obtendrían todas las rectas en función de t:

Pero los tráficos reales son discretos, es decir, se tiene un conjunto de valores en función de unos incrementos de t, con lo que no se puede aplicar la derivada para hallar la tangente a la curva. La condición (10) se sigue cumpliendo. Por un punto ti pueden pasar varias rectas con distintas pendientes ., pero ninguna de estas rectas podrá cortar a E(t). Sea l-(t) la recta con menor pendiente que corta con un punto anterior de E(t) y l+(t) la recta con mayor pendiente que corta con un punto posterior de E(t). La condición para que ti sea un punto envolvente sería que no exista otro punto anterior ti-1 donde la pendiente l-(ti-1) sea menor a l(ti) y ningún punto posterior ti+1 donde la pendiente l+(ti+1) sea mayor a l+(ti). En la Figura 3.7a se pueden ver las dos rectas. Esto se puede formular por medio de la siguiente expresión:

El objetivo consiste en obtener una serie de puntos de E(t) donde la pendiente de la recta que une la anterior sea siempre mayor que la pendiente de los puntos posteriores y que la pendiente de recta que une al punto posterior sea menor a las anteriores. Formalmente: como se ve en la Figura 3.1.5b. Es decir, se obtienen las rectas que unen los puntos de forma que las pendientes son siempre decrecientes. En resumen, lo que esto implica es la eliminación de los “valles” de la envolvente empírica, quedando los “picos” (Figura 3.2 del Capitulo 3.2).

Con esta condición se puede desarrollar un algoritmo para el cálculo de estos puntos el cual está detallado en la Figura 3.1.6. La complejidad de este algoritmo es de O(n*m) donde n son los valores de t y m los puntos obtenidos.

El objetivo de esta sección es demostrar que con los puntos envolventes se puede obtener una función s’(r) equivalente a la función (7) s(r). Para ello, se demostrará que a partir de estos puntos se obtienen las rectas envolventes. A partir de esta demostración, se obtiene una simplificación a la hora de obtener la reserva óptima que permite una búsqueda de la solución rápida y acotada.

Para un punto i el valor de está en el intervalo [.i-1, .i]. Por este punto pasarán el siguiente conjunto de rectas:

Despejando por tanto s y variando en este intervalo se pueden calcular todas las rectas que pasan por el punto i: entonces s‘(r) es la composición de funciones lineales .i(r) para cada intervalo definido por los m puntos envolventes.

Lema 3: s’(r) es monótona decreciente y continua en el intervalo [0, p ].

Demostración: 25 La función (14) si(r) es monótona decreciente al depender sólo de en el intervalo [.i-1, .i ]. El valor de E(t0) es igual a cero con lo que s(.)=0.

Cuando es cero el valor de s(0)= E(tm). Por definición, la recta que pasa por el punto ti con pendiente ri-1 también pasa por el punto ti-1 y por lo tanto tiene el mismo valor en el origen s. Por ello si (.i-1)= si-1(si-1). Para .i es lo mismo y por tanto si(.i)= si+1(.i).

Además, por la propia definición, si(.) es una función decreciente por intervalos lineales como se puede ver en la Figura 3.1.7 Se ha llegado por tanto, a un mecanismo por el cual se obtienen los segmentos comentados sobre la Figura

3.3.

Como se ve, el rango de s’(r) para el dominio [0, . ] es [0, T ] donde T es el total de bits transmitidos (que es igual a E(tn) ). Se define L.(t) como el conjunto de rectas l(t) generadas para cualquier valor de .. Esto es:

Lema 4: L.(t) es el conjunto de rectas envolventes a la envolvente empírica E(t).

Demostración: Si el rango de pendientes de L.(t) va de 0 a ., lo que hay que probar es que no existe otra recta l’(t) con la misma pendiente tal que l’(t)<l(t).

Por la condición (12) la recta l(t) tocará la envolvente empírica en un punto ti. Si existiera una recta l’(t)<l(t) con la misma pendiente ., esto implicará que s’<s.

Esto supone que el valor de l’(t) en ti será menor que l(ti). Dado que l(ti)=E(ti), esto significa que l’(t) corta a la envolvente empírica con lo que se incumple la condición (10).

Dado que s’(r) es continua y monótona decreciente (lema 3) se obtienen todas las rectas l(t) para cualquier valor de .. Por lo que L.(t) es el conjunto de todas ellas.

Teorema 2: La función s’(.) es equivalente a s(.).

Demostración: Por el lema 4, L.(t) es el conjunto de rectas envolventes de la envolvente empírica. Esto implica, que el valor en el origen s de estas rectas es el menor para una tasa de drenaje ., que es igual al valor s(.). Dado que s’(.) es continua y decreciente entonces s’(.) = s(.) para todo entre 0 y p.

Por lo tanto, dado que s’(.) devuelve los mismos valores que s(.) se puede utilizar para iterar en la ecuación (9) y encontrar raíces de la misma forma. Esto permite obtener la solución a partir de los puntos envolventes, pero se sigue utilizando un método iterativo y no acotado para encontrar la solución R(.)=.. Pero dado que s’(.) está formada por segmentos lineales, esto permite desarrollar un método directo para encontrar la solución que se describe a continuación:

Teorema 3: Si la raíz R= está en el intervalo [.i-1, .i], entonces:

Demostración: Si la raíz R= está en [.i-1, .i ], se tiene que: si(.) = E(ti) - Rti y sustituyendo en la ecuación (9) y despejando R:

Esto implica que si se sabe en qué intervalo está la raiz 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 aplicará el teorema 3 para obtener R. Un algoritmo para encontrar la solución se detalla en la Figura 3.1.8 El costo de encontrar la solución es muy rápido, con un costo computacional de O (log m). Como se verá en el siguiente punto, el valor de m es pequeño (entre 20 y 100 puntos para los vídeos analizados).

La reserva mínima de buffer en los nodos puede ser calculada usando las ecuaciones vistas en el punto 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 usando las ecuaciones (4) y (5) directamente.

3.1.4 Algunos resultados aplicando la optimización

En este punto se muestran los resultados sobre algunas trazas considerando vídeo tipo MPEG. Por el corolario 1 las reservas son equivalentes para las ecuaciones del IETF/RSVP y Parekh. Por ejemplo, los puntos generados para el tráfico LAMBS1500 están en la Figura 3.1.- Como se puede ver, una de las propiedades más interesantes de estos puntos es que es una descripción sintetizada del tráfico. Así, el primer valor de es siempre la tasa pico p.

Con estos datos y usando el ejemplo puesto en el punto 3.1.2 para un retraso máximo de 0.1s, se tiene que el par de valores obtenidos s y son 50208 bits y 944590 b/s, lo que conduce a una reserva de 944590 b/s. Por el corolario 2 se puede calcular el retraso mínimo que se puede exigir que es:

En la Figura 3.1.10 se muestra el cálculo de la reserva y el valor s en función del retraso exigido desde 0s a 5s en la red de ejemplo de la Figura 3.1.4 Cuanto mayor es el retraso mayor tiene que ser el valor de s debido a que se tiene que almacenar las tramas en la red. El incremento de este valor en función del tiempo es bastante lineal. En cambio, el valor . decrece exponencialmente hasta 0.25s para después decrecer linealmente.

Anexo 5.1 Otros estudios realizados

Este estudio fue extraído del sitio de Internet de www.cisco.com y sirve cómo referencia del uso que el fabricante Cisco® esta haciendo en sus diferentes plataformas de equipos routers en lo referente al uso de la compresión de datos. Y solo sirve cómo referencia de los resultados obtenidos anteriormente [5].

Este estudio compara el funcionamiento del software (Cisco IOS®) basado en la compresión de datos; así como también por hardware a través de un Adaptador de Servicio por Compresión (CSA) ambas en plataformas de routers de la serie Cisco 7200 y 7500. El algoritmo de compresión usado en este estudio es el algoritmo Lossless de compresión de datos de LZS-STAC.

El Software de Cisco IOS soporta tres diversos métodos para implementar la compresión:

- Software-basado en compresión usando el procesador del router principal (Route Switch Processsor) [RSP] o el Network Processing Engine [NPE]).

- Software-basado en compresión usando procesadores versátiles del interfaz (VIPs) (basado en procesador distribuido).

- Hardware-basado en compresión usando el adaptador del servicio de compresión (CSA).

5.1.1 El estudio del funcionamiento.

El estudio se hace en tres partes. Primero, el rendimiento de procesamiento de varios enlaces se mide sin ninguna compresión permitida. En segundo lugar, la compresión por software basado en Cisco IOS. Esta prueba, además de dar el funcionamiento del rendimiento de procesamiento, también proporciona el porcentaje de carga del CPU y la tasa de compresión de los datos de prueba. La última prueba realizada es la compresión basada en hardware (CSA), que también proporciona el funcionamiento del rendimiento de procesamiento, el porcentaje de carga del CPU, y la tasa de compresión.

Las pruebas se realizan para tamaños de paquetes de 103 y 551 bytes. El paquete de 103 bytes representa un paquete de tamaño pequeño, mientras que un paquete de 551 bytes representa un paquete por default del Protocolo de Transferencia de Archivos (FTP). El algoritmo de compresión usado en todos los casos es STAC-LZS Lossless que es el algoritmo de compresión de datos que se utiliza en todos los casos.

Ambos funcionamientos por software y hardware de compresión se miden para diversas velocidades del enlace: 64 Kbps y el E1, incluyendo 1.54, 2.015, 4.030, y 8.061 Mbps. Los resultados se obtuvieron en plataformas Cisco 7200 y 7500.

En la plataforma del Cisco 7200, el funcionamiento de la compresión se mide contra ambos modelos de NPEs (NPE-150 y NPE-200). En la plataforma del Cisco 7500, el funcionamiento de la compresión se mide contra RSP4 y ambos VIPs (VIP2-40 y VIP2-50).

Las gráficas siguientes muestran el funcionamiento del número máximo de paquetes de datos (medidos en miles de paquetes por segundo) para ambos tamaños de paquetes de 551 y 103 bytes, para una velocidad dada del enlace (medida típicamente en Megabits por Segundo).

La tasa sin comprimir del paquete refleja el número de paquetes por segundo requerido para alcanzar una tasa lineal para varias velocidades de enlace. La tecnología de compresión reduce el tamaño del paquete, de tal modo que aumenta el número de paquetes transmitidos para la misma tasa del enlace. El efecto es virtual, al aumentar el ancho de banda total del enlace.

Por ejemplo, en la prueba 1, para una velocidad del enlace de 4Mbps, el número máximo de paquetes sin comprimir (551 bytes) que pueden ser transportados es de 0.914 kpps. Este número se traduce en 4 Mbps, que es también la tasa máxima del enlace. Usando la compresión por software, el número máximo de paquetes (551 bytes) es transportado en 1.156 Kpps. Este número se traduce en

5.095 Mbps de datos transportados en el mismo enlace físico que funciona a la misma velocidad del enlace, que es 4 Mbps. Esto representa un aumento aproximadamente de 1 Mbps del rendimiento de procesamiento de datos.

Ahora, usar CSA basado en la compresión por hardware, el número máximo de paquetes (551 bytes) transportados es 2.062 kpps. Este número se traduce en 9.08- Mbps de datos transportados en el mismo enlace de 4Mbps, más de dos veces el transporte sin comprimir los datos.

5.1.1.1 CASO 1 Plataforma: VIP2-40 en Cisco 7500

Puerto Adaptador: PA-4T+ y CSA-Comp/1 (768 KB)

Cisco IOS Ver.: 11.1(14.5) CA

Tamaño del Paquete: 551 y 103 bytes

En la Figura 5.1.1 se demuestra que la compresión ayuda definitivamente a aumentar el rendimiento de procesamiento de datos, con la compresión por hardware se envían más datos sobre el enlace que por software. La compresión de paquetes de datos mejora la utilización del ancho de banda del enlace WAN disponible traducidos directamente en ahorros de costos de acceso a la WAN.

En el caso de compresión por software, el funcionamiento del CPU es el cuello de botella para la compresión en enlaces de alta velocidad (véase el caso de los 8M). El hecho de que la utilización del CPU estuviese cerca de 99%, es porqué el rendimiento de procesamiento por compresión por software está por debajo del rendimiento de procesamiento sin comprimir. La tasa de compresión es 2.35.

La utilización del enlace por compresión por hardware es más de dos veces que la velocidad del enlace de 8M, que es equivalente a cuatro enlaces E1. La utilización del CPU del procesador de VIP soportado por el puerto adaptador CSA es menos de 50. La tasa de compresión es 2.28.

El funcionamiento de la compresión por software depende fuertemente de la capacidad del procesador. El tamaño más pequeño del paquete pone más carga en el procesador, como es evidente en el funcionamiento reducido de la compresión para los enlaces de alta velocidad, por ejemplo para los 4M.

La compresión por hardware (CSA), se recomienda definitivamente para la compresión en enlaces de alta velocidad. Esta compresión también libera al procesador para otras funciones importantes del router tales como generar y actualizar tablas de ruteo, etc.

5.1.1.2 CASO 2 Platforms: VIP2-50 in Cisco 7500 platform

Port Adapter: PA-4T+ and CSA-Comp/1 (768 KB)

Cisco IOS Ver.: 11.1(14.5) CA

Data Packet Size: 551 bytes and 103 bytes

El funcionamiento de la compresión por software es mejor con el VIP2-50 que con el VIP2-40 porque el VIP2-50 tiene un procesador más rápido. Esto es evidente para los enlaces de alto velocidad tales como 4 Mbps (dos enlaces E1) visto en la Figura 5.1.3. La carga del procesador se encontraba cerca de 99% para las velocidades del enlace de 4 Mbps y demás capacidad. Esto confirma de nuevo que la compresión por software es ideal para los enlaces de poca velocidad. La tasa de compresión en este caso es 2.35.

La utilización del enlace con la compresión por hardware es más de dos veces tanto como se vio en el Figura 5.1.1. El uso eficiente de enlaces WAN con compresión por hardware resulta de una orden de magnitud de utilización más alta del enlace, de tal modo que reduce los costos de acceso del enlace WAN. La utilización del CPU del VIP que soporta el adaptador en el puerto CSA fue menos del 50 por ciento. La tasa de compresión es 2.28.

El funcionamiento de la compresión por software depende fuertemente de la capacidad del procesador. El tamaño más pequeño del paquete pone más carga en el procesador, como se muestra en el funcionamiento reducido de la compresión para enlaces más altos en velocidad, como 4 Mbps y 8 Mbps por ejemplo. La utilización del procesador se encontraba cerca del 99% en ambos casos. La tasa de compresión es de 1.81.

5.1.2 Análisis del algoritmo utilizado por la tecnología de compresión de Cisco®

El algoritmo de compresión usado por la tecnología Cisco®, cómo se menciona en este estudio, es el algoritmo Lossless de compresión de datos de LZS-STAC.

Haciendo un análisis comparativo de lo que ofrece la tecnología de Cisco vs la tecnología utilizada en las mediciones de este trabajo, encontramos una serie de diferencias en lo referente a características técnicas, no fue posible comparar los resultados en el campo experimental debido a que la empresa Corporativa que se selecciona no tiene en sus equipos de routers habilitada la opción de compresión de datos.

Cisco® (LZS-STAC) Peribit® (MSR) Manejo de un buffer o tamaño de ventana No maneja un buffer fijo; sino más bien fijo, se limita a menudo a la Unidad dinámico.

Máxima de Transmisión (MTU) de la red, es decir un tamaño de buffer de 1500 bytes.

Detecta solo aquellos patrones que son igual o menor al tamaño de ventana establecido Detecta todos aquellos patrones repetidos, independiente de su tamaño La compresión varia, dependiendo de la velocidad del enlace, el tipo y el grado de agregación de los datos a través del enlace.

La compresión se comporta de manera lineal para cualquier velocidad de enlace.

Son eficaces en enlaces de poca velocidad, simples usuarios, o enlaces de aplicaciones simples, pero con un % de reducción de datos muy baja.

La compresión se comporta de igual manera para cualquier enlace.

La velocidad del algoritmo de búsqueda depende fuertemente de tamaño de la ventana o buffer.

Es independiente el algoritmo de búsqueda al tamaño de ventana o buffer.

Latencia aproximadamente de 30 ms (*) Latencia de 2 ms Adicionan carga a la red, dependiendo del No se adiciona carga a la red, es todo por esquema de configuración de la Hardware compresión: Por software, SI. Por Hardware, NO Complejidad Computacional: No lineal de Complejidad Computacional: Lineal de orden O(n f(B)), donde “n” es el número de orden O(n). Esto indica que el número de símbolos de entrada y “B” es el tamaño operaciones requeridas para procesar “n” del buffer de búsqueda. bytes de entrada es proporcional a “n” bytes.

Nota: (*) Valor teórico, no fue posible obtenerlo de manera experimental.