ALGORITMOS PARA ENCRIPTACI?N DE DATOS

3.2.4.2.6 Las fuerzas y los diferenciadores de MSR

La tecnología MSR puede ser comparada con la compresión de datos de uso general tradicional puesto que ambas tecnologías reducen datos o tamaños del objeto al quitar repeticiones y redundancias en los datos.

Por lo tanto, el objetivo de ambas tecnologías es similar, es decir, encontrar y eliminar repeticiones en los datos.

La eficacia de una tecnología de compresión se mide típicamente en términos de la tasa de la reducción de datos que puede alcanzar. Pero la aplicación de la compresión de datos a la infraestructura del establecimiento de una red expone varios apremios adicionales que deben también ser considerados en la evaluación de una tecnología de reducción de datos. Estos nuevos apremios incluyen operabilidad en tiempo real, velocidad, latencia, dependencias entre paquetes codificados, transmisión de datos codificados con un medio no confiable y la operación incremental y continua.

Esta parte se examina el MSR y las técnicas de compresión de datos de uso general tradicionales con respecto a cada uno de estas ediciones y de su impacto en la reducción de datos y escalabilidad. Las técnicas de compresión de datos que se utilizan para una comparación son aquellas derivadas de los algoritmos de Lempel-Ziv [ LZ77, LZ78 ]. Muchas de las técnicas extensamente conocidas de compresión, incluyendo gzip, compress, LZW, y LZS (Stac compresión), derivadas del trabajo original de Lempel y Ziv.

3.2.4.2.6.1 Las fuerzas primarias de MSR que distinguen estas de las tradicionales técnicas de compresión son:

- La reducción de datos lineal y la escalabilidad del proceso

- Desacople del flujo de datos y la sincronización del diccionario

- Incremental y funcionalidad continúa

Las secciones siguientes discuten cada una de las características anteriores y las compara a las de las técnicas basadas LZ tradicionales de compresión.

3.2.4.2.6.2 La reducción de datos y la escalabilidad del proceso

El grado de reducción de datos que se puede alcanzar por un algoritmo de compresión es una función directa del número de patrones repetidos que puede descubrir. El número de patrones repetidos detectados depende del tamaño del buffer que guarda una copia de los símbolos previamente procesados de entrada y la eficiencia del algoritmo de búsqueda que busca repeticiones en este buffer. El tamaño del buffer histórico de entrada influye directamente en el número de patrones que pueden ser descubiertos y por lo tanto del grado de reducción de datos que el algoritmo puede alcanzar. El orden para que un patrón repetido sea detectado, el número de bytes que ocurren entre dos repeticiones subsecuentes de los patrones deben ser más pequeños que el tamaño de buffer. Es decir, ambos casos de repetición deben bajar dentro del buffer.

Por ejemplo, asumiendo:

D = la distancia promedio entre cualquier dos repeticiones de un patrón

B = tamaño del buffer de búsqueda

Si D = 100 bytes, implica que un patrón dado está repetido, en promedio, cada 100 bytes en los datos de entrada. Para detectar eficientemente una repetición de este patrón, B debe claramente ser más grande de 100 bytes. Si B es igual a 100 bytes más dos veces el tamaño de la repetición, la probabilidad de detectar cualquier repetición dada del patrón es el 50%. Mientras que B se hace más pequeño la probabilidad de detectar la repetición disminuye, y mientras que B se hace más grande la probabilidad aumenta y se acerca a 100%. Así, mientras más grande es el tamaño del buffer mayor es el número de patrones que será detectado y por lo tanto mayor es la reducción de datos que será alcanzado.

De acuerdo con el análisis anterior, los algoritmos de compresión deben intentar claramente maximizar el tamaño de buffer B para maximizar su tasa de reducción de datos. Pero como se aumenta B, el número de los bytes o símbolos que se deben examinar para buscar los patrones repetidos también incrementa. Así, la tasa de reducción de datos y la velocidad de proceso de un algoritmo de compresión se deben examinar simultáneamente.

El factor clave que determina la velocidad de una técnica de reducción de datos es su complejidad, que se define en los términos del número de operaciones de CPU requeridas para procesar una secuencia de entrada de n símbolos. La complejidad del algoritmo de MSR es O(n) o de "Orden (n)". Esto indica que el número de operaciones requeridas para procesar “n” bytes de entrada es proporcional a “n”. MSR es por lo tanto un algoritmo lineal puesto que el número de operaciones de CPU requeridas

para procesar la entrada crece linealmente con el número de símbolos de entrada. Así, si la tasa de transmisión de datos en un enlace de red fuera doblada, MSR necesitaría realizar dos veces el número de operaciones en el mismo tiempo para procesar todos los datos sobre el enlace. El algoritmo de descubrimiento del patrón de MSR es el componente clave que proporciona esta escalabilidad lineal.

El algoritmo de descubrimiento del patrón tiene la capacidad de buscar en cualquier tamaño de un buffer arbitrario en un tiempo constante, así asegurándose de que cada símbolo de entrada incurra en un número constante de operaciones. Por lo tanto, el tamaño del buffer de búsqueda, B, no aparece en la ecuación de la complejidad de MSR. Además, puesto que la tasa de reducción del algoritmo del MSR es proporcional al tamaño del buffer, podemos concluir que la velocidad del algoritmo de MSR es independiente de la tasa de reducción que puede alcanzar. Es decir, el tamaño del buffer de MSR, B, se puede hacer arbitrariamente grande para alcanzar una reducción de datos más alta sin la afectación de la velocidad o de la complejidad del algoritmo.

En contraste con MSR donde las variables del tamaño del buffer de búsqueda y la velocidad son independientes, la mayoría de las técnicas tradicionales de compresión basadas en LZ son inversamente relacionadas. Por lo tanto, las técnicas tradicionales de compresión deben compensar la velocidad para alcanzar una reducción de datos más alta o la reducción de datos de compensación para alcanzar la velocidad de proceso más alta. Esto es debido al hecho de que la complejidad de estos algoritmos de compresión es O(n f(B)), donde “n” es el número de símbolos de entrada y B es el tamaño del buffer de búsqueda. Esto indica que el número de operaciones requeridas para procesar una secuencia de “n” símbolos de entrada es proporcional al producto de “n” y de una función del tamaño de buffer B. Así, si el tamaño de buffer B aumenta para alcanzar una reducción de datos más alta, el número de operaciones requeridas para procesar “n” símbolos de entrada también aumenta. Esto alternadamente disminuye la velocidad y el rendimiento de procesamiento total del algoritmo de compresión.

Debido a la dependencia inversa de la velocidad al tamaño del buffer, las técnicas tradicionales basadas en LZ de compresión utilizan generalmente un buffer muy pequeño de búsqueda. Los algoritmos de compresión fuera de línea tales como "gzip", utilizan típicamente un tamaño de buffer de 8 KB a 32 KB. Los algoritmos de compresión en línea deben funcionar en tiempo real con tráfico de red en vivo utilizando incluso buffers más pequeños, típicamente 2KB o menos.

Adicionalmente, las restricciones de la red (descritas en el siguiente apartado) limitan a las técnicas tradicionales de compresión forzándolas a funcionar independientemente en cada paquete individual. Es decir, cada paquete se comprime independientemente del resto de los paquetes y el algoritmo de la compresión reajusta su estado después de que cada paquete se procesa. Puesto que el tamaño de buffer de búsqueda no puede exceder el tamaño de los datos de entrada que se están procesando, las técnicas tradicionales de compresión de la red por lo tanto se limitan a menudo a un tamaño de buffer de 1500 bytes (es decir, al MTU16 de la red).

La escalabilidad y la reducción de datos MSR y la compresión tradicional, puede ser explorada más a fondo modelando la distancia entre las repeticiones del tráfico en la red. Los enlaces de la red típicamente se actualizan a velocidades de mayor capacidad para apoyar tasas de transferencia más altas de datos, más usuarios y más aplicaciones. Por lo tanto, enlaces de mayor velocidad apoyan típicamente mayores volúmenes y variedad de tráfico. Esto además implica que a velocidades más altas, la distancia promedio entre objetos repetidos también aumenta (es decir, pues las velocidades de la red aumenta el número promedio de bytes que ocurren entre dos instancias por los incrementos mismos de patrones). Podemos por lo tanto modelar la distancia entre las repeticiones cómo una variable aleatoria normalmente distribuida, donde la media y la desviación estándar son una función de la velocidad del enlace. Para el análisis actual, la distancia media entre las repeticiones se modela para ser el 20% del número de los bytes transferidos por segundo y la desviación estándar es el 10% de la tasa de transferencia del byte (es decir, la mitad de la media).

Media: µ = (bytes por segundo) * 0.2

Desviación Estándar: s = (bytes por segundo) * 0.1

De acuerdo con este modelo, podemos calcular exactamente la probabilidad de un buffer de búsqueda de tamaño B para capturar dos casos de una repetición. Por ejemplo, si B es igual a la media, µ, entonces la mitad del promedio de las repeticiones caerá dentro del buffer y la mitad bajará fuera del buffer (asumiendo, para propósitos del modelo, que el tamaño de la repetición es insignificante comparado a la distancia entre las repeticiones). Así para B = µ, el porcentaje de repeticiones que serán detectadas es el 50%. Para todos los valores de B, el porcentaje de detección de patrones se calcula como el área debajo de la curva estándar de la distribución normal menos que Z, donde Z se define como:

Z = (B – µ) / s

La Tabla 3.2 muestra el tamaño de buffer B para MSR y para la compresión tradicional a varias velocidades de la red. Puesto que MSR puede incrementar el tamaño de buffer sin afectar la complejidad del algoritmo, el tamaño de buffer para cada velocidad del enlace se fija como:

BMSR = µ + 2 * s

Por lo tanto, la cuenta de Z para MSR es siempre:

ZMSR = (BMSR – µ) / s = 2

Una cuenta constante de Z de 2 implica que la probabilidad de una repetición que ocurre dentro de BMSR bytes es de 0.97, es decir, el porcentaje de repeticiones que serán detectadas por MSR es una constante de 97%.

Debido a las limitaciones de los algoritmos tradicionales de compresión, el tamaño de buffer, B, para estas técnicas se mantiene constante en 1500 bytes. Así para cada velocidad del enlace, el porcentaje de patrones que son detectados es calculado basado en la siguiente cuenta de Z:

La probabilidad de dos repeticiones cualesquiera que ocurran dentro de 1500 bytes entonces se calcula en cada caso como el área debajo de la curva normal estándar menos que ZCompresion.

La Figura 3.6 muestra los resultados de este análisis en un formato gráfico. Se observa que los resultados demuestran solamente el porcentaje de repeticiones que se detectan y no la reducción de datos total alcanzada. La reducción de datos total se puede calcular como el producto de la tasa en la cual las repeticiones ocurren en los datos y el porcentaje de estas repeticiones que son detectadas. Así si la tasa en la cual las repeticiones ocurren es del 80% y el porcentaje de repeticiones detectadas es 97.7%, la reducción de datos total será aproximadamente del 78%.

Para ciertos tipos de datos (tales como texto ASCII) MSR y para las técnicas tradicionales de compresión pueden adicionalmente proporcionar reducción de datos usando esquemas de codificación estadísticos para comprimir más los paquetes de salida. Estas técnicas estadísticas de codificación son cálculos costosos y proporcionan solamente ventajas a un sistema muy limitado de tipos de datos. Así, si la reducción de datos alcanzada es alta eliminando repeticiones (cómo el caso de MSR) el valor incremental de esta codificación estadística es marginal y no justifica el costo computacional agregado.

Por otra parte, puesto que el porcentaje de repeticiones detectadas es bajo para las técnicas tradicionales de compresión, deben confiar ampliamente en la codificación estadística para proporcionar la compresión adicional para ciertos tipos de datos limitados.

3.2.4.2.6.3 El flujo de datos desacoplado y la sincronización del diccionario

Un segundo punto importante de MSR es la técnica que utiliza para mantener y sincronizar sus diccionarios de patrones. El diccionario MSR consiste en una tabla explícita de patrones y de etiquetas asociadas. Este diccionario así mismo se codifica en una estructura de datos optimizada que permita maximizar el almacenaje de patrones en una cantidad pequeña de memoria física. Esta estructura de codificación optimizada también reduce al mínimo el overhead de la sincronización del diccionario permitiendo que el dispositivo de codificación MSR transmita solamente actualizaciones incrementales pequeñas del diccionario al dispositivo decodificador.

Puesto que el diccionario MSR es mantenido y actualizado explícitamente por un módulo independiente, los componentes de procesamiento de datos son desacoplados del proceso de sincronización del diccionario.

Aunque la reducción de datos y los procesos re-ensamblados requieren la sincronización del diccionario para garantizar la codificación y decodificación exacta, no participan directamente en la tarea de sincronización del diccionario. Los paquetes codificados y encapsulados que se transmiten del dispositivo de codificación del MSR al dispositivo decodificador por lo tanto no tienen ninguna dependencia entre ellos.

Esto además implica que la entrega confiable y en orden de estos paquetes encapsulados no es un requisito necesario para la sincronización del diccionario y codificación exacta de los datos. Ésta es una fuerza clave de MSR, puesto que permite que cada paquete de salida sea encapsulado en una conexión independiente. Si un paquete encapsulado se pierde durante el tránsito o si los paquetes encapsulados se entregan al dispositivo decodificador fuera de servicio, el motor decodificador MSR no será afectado y continuará decodificando exactamente todos los paquetes. Puesto que la comunicación end-to-end se basa típicamente en protocolos de transporte confiables por ejemplo TCP, los paquetes encapsulados comprimidos en un segundo canal TCP pueden afectar perceptiblemente el funcionamiento de la red. Los lazos de control múltiples de la jerarquización TCP dentro de cada uno pueden causar comportamiento inestable de la red y degradar perceptiblemente el funcionamiento. Por lo tanto, la capacidad de MSR de realizar la reducción de datos a través de todos los paquetes pero de transmitir cada paquete procesado vía un canal no confiable del transporte es un diferenciador significativo de esta tecnología.

Según lo descrito en la sección anterior, las técnicas tradicionales de compresión de datos se limitan a menudo a los tamaños de buffer pequeños de cerca de 2 Kilobytes debido a las razones de funcionamiento. Por lo tanto, estas técnicas tratan cada paquete de entrada independientemente del resto de los paquetes y no buscan repeticiones a través de los paquetes múltiples. Incluso si las técnicas tradicionales de compresión pudieran superar esta limitación del funcionamiento y buscar repeticiones a través de los paquetes múltiples, entonces podrían enfocarse con la emisión de las dependencias al interior del paquete.

La mayoría de las técnicas basadas LZ de compresión de datos utilizan un esquema de codificación de repeticiones basado en apuntadores que codifican patrones repetidos señalando la posición anterior en la cadena de entradas donde ocurrió el patrón. Por ejemplo, si un patrón en el paquete que se está procesando actualmente hubiera ocurrido en el paquete anterior que fue procesado, el algoritmo de compresión codificaría el caso actual del patrón señalando su localización exacta en el paquete anterior. Así, el algoritmo de compresión requeriría que ambos paquetes lleguen el dispositivo decodificador en el mismo orden que fueron transmitidos y que ninguno de los dos paquetes esté perdido durante el transporte.

Este requisito puede ser alcanzado solamente encapsulando todos los paquetes comprimidos vía un protocolo confiable de transporte tal como TCP.

Según lo descrito anteriormente, el encapsulado de los paquetes comprimidos en un canal de TCP puede causar el comportamiento imprevisible de la red debido al anidamiento de los lazos de control múltiple de TCP. En el mismo tiempo, puesto que muchas sesiones independientes del usuario son transportadas con una sola sesión de encapsulación TCP, los mecanismos de control de congestión de TCP's podrían reducir perceptiblemente la utilización del ancho de banda y degradar a un más el funcionamiento. Debido a estos factores, las técnicas basadas LZ tradicionales de compresión no pueden codificar repeticiones a través de los paquetes y deben reajustar su estado después de cada paquete. Esto refuerza aún más las simples limitaciones del paquete de las técnicas tradicionales de compresión que fueron descritas en la sección anterior.

3.2.4.2.6.4 Incrementabilidad y funcionalidad continúa

Un tercer diferenciador significativo de MSR es su capacidad de funcionar incrementalmente y en tiempo real en una cadena continua de datos. MSR procesa cada símbolo de entrada incrementalmente y genera salida mientras que continúa procesando más datos de entrada. Los algoritmos no incrementales procesan típicamente bloques grandes de entrada a la vez y pueden generar solamente salida después de que se haya procesado un bloque completo. La naturaleza incremental de MSR es una característica importante puesto que evita la latencia adicional de tener que esperar una cantidad fija de datos de entrada antes de generar la salida reducida. Aunque el MSR busca parar y eliminar repeticiones a través de los paquetes, la salida codificada para un paquete de entrada está disponible para la transmisión tan pronto como se haya procesado el paquete de entrada. Así no hay latencia adicional introducida para cada paquete de entrada.

El MSR puede funcionar continuamente con recursos finitos en una cadena indefinida de datos de entrada. Todos los recursos, tales como espacio físico de memoria y del diccionario, son utilizados óptimamente y se reutilizan para asegurarse de que el algoritmo nunca exceda sus límites asignados. La reutilización de los recursos del diccionario se realiza a través de un patrón adaptativo "que se olvida" del proceso que substituye patrones infrecuentemente utilizados por patrones más relevantes y recientemente descubiertos. Los módulos de administración de recursos no afectan la linealidad o escalabililidad total del algoritmo de MSR de ninguna manera.

Así, el diccionario adaptativo MSR aprende y olvida procesos para poder funcionar continuamente mientras que todavía mantiene la complejidad lineal y la escalabilidad del algoritmo.