ALGORITMOS PARA ENCRIPTACI?N DE DATOS

2.6.5 Planificadores

2.6.5.1 Introducción

Los planificadores de tráfico pueden ser usados en distintos entornos para satisfacer una amplia variedad de objetivos [Varma97]. Una aplicación común de los algoritmos de planificación es proporcionar una calidad de servicio a nivel de red aislando unos tráficos de otros.

Los planificadores también pueden ser usados para permitir a los usuarios compartir un enlace de forma equitativa o determinista.

Un planificador puede ser contemplado como un sistema de colas que consiste en un servidor que proporciona servicio a un conjunto de clientes. Los clientes encolan paquetes para ser servidos y estos son escogidos por el planificador basándose en una disciplina de servicio definida por el algoritmo de planificación. La disciplina de servicio puede ser diseñada para cumplir los requerimientos de calidad de servicio deseados por cada cliente.

Los atributos deseables para un algoritmo de planificación son los siguientes [Varma97]:

- Aislamiento de flujos: Aislar un canal de los efectos indeseables de otros.

- Retraso emisor-receptor garantizado: El planificador debe proporcionar un retraso garantizado de emisor a receptor. Además, es deseable que este límite del retraso dependa sólo de los parámetros de la sesión y que no dependa del resto de las sesiones.

- Utilización: El algoritmo debe maximizar el uso de ancho de banda del enlace.

- Equidad (Fairness): El planificador debe servir a las sesiones con tasas proporcionales a su reserva en cada instante, esto es, distribuyendo el ancho de banda libre proporcionalmente entre las activas. Lo ideal sería que se comportase como un flujo perfecto repartiendo perfectamente el ancho de banda. Pero debido a la cuantificación en paquetes de los flujos esto es prácticamente imposible. Por tanto, se introduce el índice de equidad (WFI: Worstcase fairness index) que mide la desviación de servicio ofrecido por un planificador con respecto a un modelo perfecto.

- Simplicidad de implementación: El algoritmo de planificación debe ser fácil de implementar y con baja complejidad. Esto es importante si se va implementar por hardware.

- Escalabilidad: El algoritmo debe comportarse bien en nodos con un gran número de sesiones y con una variedad de velocidades de enlace.

2.6.5.2 Disciplinas de servicio

El objetivo de los planificadores es asignar los recursos de acuerdo a la reserva realizada con anterioridad con el objetivo de cumplir la calidad de servicio exigida. Tres tipos de recursos son asignados por los planificadores: ancho de banda (qué paquete es transmitido), tiempo (cuándo es transmitido el paquete) y memoria (qué paquetes son

descartados), lo que afecta a tres parámetros básicos: rendimiento, retraso y tasa de pérdida.

En general, se distinguen dos tipos de disciplinas de servicio en los nodos [Zhang98]:

- Non work-conserving en el que los nodos intentan mantener el modelo del tráfico, aunque esto implique que en determinados periodos no se transmita nada. En este caso, cuando entra un paquete en el nodo se le asocia un tiempo de elegibilidad. En el caso de que no haya paquetes en estado de elegibilidad, no se transmite nada. Ejemplos de estas disciplinas de servicio son las de tasa controlada (“rate-controlled”): RCSP [Zhang94] , Jitter-EDD [Verma91], “Stop-and-go” [Golestani90] y “Hierarchical Round Robin” [Kalmanek90]. Cada planificador provoca un retraso acotado y calculable para cada paquete. Dado que cada nodo mantiene el modelo del tráfico el cálculo del retraso total es la suma de los retrasos en cada nodo.

- Work-conserving en el que si existen paquetes en el nodo por transmitir se envían. A este grupo pertenecen Virtual Clock [ZhangL90], Weighted Fair Queuing (WFQ) y GPS (General Processor Sharing) [Demers89] [Parekh92]. Para todos estos esquemas existen funciones para calcular el retraso máximo emisor-receptor que están basadas en el trabajo de Parekh y Gallaguer [Parekh93].

Normalmente, el cálculo del retraso es dependiente de la reserva de ancho de banda en los nodos.

Hay que tomar en cuenta el costo computacional de los algoritmos de planificación para su implementación en redes de alta velocidad. Por ejemplo, un planificador FCFS tiene un costo de implementación bajo, pero sólo puede soportar un límite de retraso para todas las conexiones.

En el otro extremo, el algoritmo EDD es complejo ya que involucra una operación de búsqueda del paquete con el deadline más corto.

Otras disciplinas de servicio gestionan la compartición del enlace de una forma controlada, permitiendo una estructura jerárquica, como el planificador CBQ (Class-based queueing) [Floyd95].

A continuación se describen dos disciplinas de servicio que el autor considera los más representativos para cada tipo de servicio: el servicio RCSP del tipo non-workconserving y el planificador WFQ del tipo workconserving.

2.6.5.3 Servicio RCSP

La disciplina de servicio RCSP (Rate-Controlled Static Priority) fue introducida por H. Zhang en el grupo Tenet [Zhang94]. Como se muestra en la Figura 2.14 un servidor RCSP está formado por dos componentes: un controlador de tasa y un planificador con prioridades estáticas. Conceptualmente, el controlador de tasa está formado por el conjunto de reguladores asociados a cada canal que atraviesa el nodo.

Cada regulador es un conformador de tráfico que regula el tráfico de entrada al nodo al modelo de tráfico deseado para el planificador.

Cuando un paquete llega, el regulador calcula un tiempo de elegibilidad y es retenido en el regulador hasta que cumpla este tiempo. A continuación, se introduce en el planificador deseado en función del nivel asignado. El planificador dispone de un conjunto de colas para cada nivel de prioridad y selecciona los paquetes de la cola más prioritaria que no esté vacía. Cada conexión tiene asignado un nivel de prioridad desde el momento del establecimiento del canal y depende principalmente del retraso exigido.

La forma de calcular el tiempo de elegibilidad depende del modelo del tráfico, el cual va a definir como se regula el tráfico. Para RCSP se utiliza el modelo Tenet (Xmin, Xave, I, Smax). Con este modelo se obtienen las ecuaciones que definen el tiempo de elegibilidad de un paquete para un canal de tal forma que el tráfico mantiene sus características a lo largo de la red.

El tiempo de elegibilidad para el paquete de orden k de la conexión j en el nodo i, ek i,j, se define usando el tiempo de elegibilidad calculado para paquetes anteriores de la misma conexión: