ATM Información

Creada por Efrain Ruh

PHANTOM FLOW CONTROL

Descripción General

El Control de Flujo "Fantasma", al que llamaremos PFC (Phantom Flow Control) fue presentado en la Conferencia ACM SIGCOMM ’96 California, EEUU, por Yehuda Afek, Yishay Mansour y Zvi Ostfeld, del Departamento de Computación de la Universidad de Tel-Aviv, Israel. El PFC es una de las opciones propuestas para implementar el esquema de control de flujo tasa de bit, recientemente aprobado por al ATM Forum, para conmutadores ATM.

Este algoritmo se presenta como una manera eficiente y sencilla para el manejo de tráfico de datos, tanto para ser utilizado en conmutadores ATM como para routers TCP.

La idea principal de este esquema es relacionar las tasas de transferencia de sesiones que comparten un enlace con la cantidad de ancho de banda no utilizado por ese enlace. La principal finalidad es mantener el criterio de asignación equitativa de canal (max-min fairness) . Se presenta como una variación de control de flujo basado en tasa de bit, donde la particularidad está en la forma cómo se calcula la tasa explícita asignada a cada sesión en las celdas RM (Resource Management, celda de Administración de Recursos).

El ancho de banda no utilizado representa una sesión "fantasma", y a partir del valor de ésta, se regula el ancho de banda permitido a las conexiones que atraviesan dicho enlace, así el enlace es compartido de forma equitativa entre todas las conexiones, incluyendo la fantasma.

Funcionamiento Básico

La idea es preservar una cierta porción de la capacidad de enlace sin utilizar, a lo que llamaremos la sesión fantasma o phantom, y limitar las tasas de las sesiones que comparten dicho enlace por la cantidad de ancho de banda sin utilizar en el enlace. Las sesiones cuya tasa sobrepasen el ancho de banda sin utilizar, representado por la sesión fantasma, son reducidas hacia el valor de la tasa de la sesión fantasma, y de igual forma las tasas de las sesiones que están por debajo pueden ser aumentadas. Este mecanismo alcanza un estado estable cuando la tasa de la sesión fantasma, el ancho de banda no utilizado, es igual a la tasa máxima de las sesiones que cruzan el enlace y cuando todas las sesiones que están limitadas en este enlace tienen esta misma tasa. El valor de ancho de banda no utilizado D es fácilmente calculado en cada puerto, contando el número de celdas que llegan en un intervalo de tiempo y restándole el número de celdas que pudiesen haber llegado en este mismo intervalo.

Por ejemplo, si tenemos un enlace de 100Mbps compartido por tres aplicaciones, en estado estacionario cada sesión recibe 25Mbps y la utilización del enlace es de 75% (en este caso la tasa de la sesión fantasma es 25Mbps también). Sin embargo, si dos de las tres sesiones son restringidas en alguna parte a 10Mbps cada una, la tercera aumenta a 40Mbps, la fantasma también obtiene 40Mbps.

Este esquema presenta los siguientes avances:

Requiere un número constante de variables en cada puerto de cada uno de los conmutadores. Por esto se define como un algoritmo de espacio constante.
Es rápido y robusto frente a variaciones buscas de tráfico.
Este esquema utiliza cualquier cantidad de ancho de banda disponible y puede ser fácilmente integrado a una red donde la cantidad de ancho de banda disponible varía con el tiempo.
En ciertas variaciones del esquema Fantasma, las celdas RM (Resource Management) no son necesarias.
Este esquema es fácilmente implementado en hardware ya que utiliza solo simples operaciones aritméticas, sin divisiones ni multiplicaciones.

El esquema Phantom ofrece a primera vista lo siguiente:

En condiciones normales, el esquema converge a un estado estable en el cual la utilización del enlace entre sesiones es equitativa. Esto responde al hecho de que todas las sesiones que son limitadas en un enlace obtienen la misma tasa en estado estable.
Ya que Phantom preserva parte de la capacidad del enlace, tiene una manera suave de reacomodar nuevas sesiones sin crecimiento en las colas.

Sin embargo, al esquema presentado inicialmente se le realizaron algunas modificaciones:

Medición de D : Debido a que la medida de D puede ser bastante inestable, se aplica una técnica de filtrado para reducir las variaciones y el ruido en el valor de D . El valor resultante se le denomina MACR (Maximum Allowed Cell Rate, Tasa de bit Máxima Permitida).

El valor de a se toma igual a 1/16.

Sensibilidad a la longitud de la cola: Debido a que el esquema básico no toma en cuenta el largo de la cola ABR en el conmutador, es posible que esta crezca debido a errores en la medición, por esto el valor absoluto de la longitud de la cola debe incorporarse dentro del cálculo del MACR.
Debido a que el valor de a debe ser igual dependiendo si estamos incrementando o disminuyendo el MACR, el valor de la longitud de la cola define los valores de a _inc y a _dec según la siguiente tabla:

Largo de la cola	a inc	a dec
Largo de la cola < QT	a	a /16
QT < Largo de la cola < 2QT	a /2	a /8
2QT < Largo de la cola < 4QT	a /4	a /4
4QT < Largo de la cola < 8QT	a /8	a /2
8QT < Largo de la cola < 16QT	a /16	a
16QT < Largo de la cola	a /32	2a
QT= Umbral de cola (queue threshold)

Modificación de parámetros a partir del largo de la cola, PFC.

Utilización: Si solamente sesiones de gran ancho de banda ocupan el enlace, el esquema haría que este fuese subutilizado. Esto se ha resulto haciendo que la sesión fantasma sea solo una porción del ancho de banda no utilizado D . A este valor se le denomina "factor de utilización".

Consideración de la Varianza: Cuando muchas sesiones comparten un enlace con un alto factor de utilización, puede traer consigo grandes oscilaciones en MARC y en el largo de la cola. Para eliminar este fenómeno se calcula un aproximado de la desviación estándar de D para integrarlo al cálculo de MACR. Dependiendo del valor de la varianza, se disminuye el valor de a por el factor ratio

s	Ratio=f(s )
s < MACR	1
MACR < s < 2MACR	1/2
2MACR < s < 4MACR	1/4
4MACR < s < 8MACR	1/8
8MACR < s	1/16

Modificación de parámetros a partir la varianza de MACR, PFC.

Reducción del largo máximo de las colas: Consideremos el siguiente escenario: muchas sesiones que se encuentran limitadas por el mismo enlace, al liberarse una porción de ancho de banda considerable, comenzarán a transmitir a una tasa muy alta simultáneamente (alto MACR), esto producirá congestión en el enlace generando una larga cola. Para evitar esto, el algoritmo fue modificado para evitar que la tasa sea incrementada de manera muy rápida, así que solo se le permite como máximo aumentar el doble de la tasa actual de la fuente (CCR) por cada RTT(Round Trip Time, Tiempo de viaje ida y vuelta).

Este esquema de control de flujo para tráfico ABR basado en tasa de bit, se presenta como una alternativa bastante viable, ya que el estándar promovido por el ATM Forum, define el comportamiento de los sistemas terminales más no el de los sistemas intermedios, permitiendo que cada fabricante decida la manera de implementar el algoritmo en cada conmutador manteniendo a su vez la compatibilidad e interoperabilidad con otros conmutadores basados en tasa. Quedará de parte de cada fabricante, la manera de brindar una calidad de servicio (QoS) igual o superior a la esperada.

Otros Esquemas Basados en Tasa de Bit

EPRCA, Enhanced Proportional Rate Control Algorithm.

EPRCA, (Enhanced Proportional Rate Control Algorithm, Algoritmo de Control de tasa proporcional mejorado), fue propuesto por Dr. Lawrence G. Roberts, Presidente de ATM Systems División en Connectware Inc, en la reunión del ATM Forum de Julio de 1994. Este algoritmo, MACR (Maximum Allowed Cell Rate, Tasa máxima permitida por celda) es calculado para puerto de salida a partir de la información recibida en las celdas RM generadas por la fuente. El cálculo de MACR, y las limitaciones de la tasa de cada una de las sesiones, depende del estado de las colas, dependiendo de un umbral que indica si el conmutador está congestionado, no congestionado o muy congestionado. Cuando se está no congestionado, la tasa de las sesiones no es limitada. En cambio cuando se está congestionado o muy congestionado, las tasas son restringidas por una fracción de MACR, es decir se multiplican por un factor de disminución y se actualiza el valor ER en las celdas RM.

APRC (Adaptive Proportional Rate Control With Intelligent Congestion Indication)

Este esquema se presentó como una modificación del EPRCA de Roberts propuesta por Siu y Tzeng llamada APRC (Adaptive Proportional Rate Control with Intelligent Congestion Indication, Control por Tasa de bit Proporcional Adaptivo con Indicación de Congestión Inteligente). Aquí la definición de congestión cambia. En vez de ser una función del largo de las colas, es entonces una función de la tasa a la cual el largo de las colas está cambiando (es decir, la derivada del largo de la cola). Esto quiere decir, si la derivada del largo de las colas es positiva el enlace está congestionado y viceversa. Dependiendo del valor de dicha derivada será disminuida la tasa explícita de las fuentes de tráfico que atraviesan dicho nodo.

CAPC (Congestion Avoidance Using Proportional Control)

CAPC (Congestion Avoidance using Proportional Control, Prevención de Congestión Utilizando Control Proporcional) fue propuesto por Barnhart en 1994. Se basa en el cálculo de la fracción de ancho de banda no utilizado para controlar las acciones del algoritmo. El estimado de la repartición equitativa del enlace lleva el nombre de ERS (Explicit Rate for Switch, tasa explícita por conmutador), el cual corresponde al MACR en Phantom. El parámetro principal utilizado para controlar los cambios de ERS es la relación entre la tasa del tráfico entrante y la capacidad del enlace. Si esta relación es menor a la unidad entonces se multiplica ERS por un factor de aumento, en caso contrario se reduce ERS por un factor también multiplicativo.

ERICA Y ERICA+ (Explicit Rate Indication For Congestion Avoidance)

La Universidad del Estado de Ohio presentó los algoritmos ERICA (Explicit Rate Indication for Congestion Avoidance, Indicación de tasa Explícita para Evitar Congestión) y ERICA+ en 1995. En ERICA el conmutador calcula dos parámetros básicos: El Factor de Carga, el cual es igual a la tasa de entrada dividida por la tasa a alcanzar (se supone un 95% del ancho de banda disponible), y FS (Fair Share), el cual es la tasa a alcanzar dividida entre las sesiones activas. Una vez obtenidos estos parámetros, el algoritmo permite a cada sesión cambiar su tasa a un máximo entre FS y la tasa actual de la conexión multiplicada por el factor de carga. Así, si el enlace está congestionado las sesiones bajan su tasa hacia FS y si está subutilizado pueden incrementar su tasa.

En ERICA+ la tasa a alcanzar es una función dinámica del largo de las colas, es decir, tasa a alcanzar = radio * ancho de banda disponible, donde radio es incrementado si el largo de la cola disminuye y viceversa.

Estos esquemas presentan varias ventajas. Primero, los largos de las colas son bastante pequeños, segundo, el algoritmo reacciona frente a cambios en los requerimientos del tráfico relativamente rápido y tercero, es un algoritmo simple.

Phantom: A Simple and Effective Flow Control Scheme

This page was last updated Tuesday, December 2, 1997.

by Efrain Ruh

Any comments write to: [email protected]

Best seen using Netscape Communicator 4