TOKEN BUCKET FILTER (TBF) Por Rodrigo D. Roldán
Para comprender este mecanismo de traffic control (control de trafico) hemos buscado documentación en la Web. Lamentablemente la misma es algo confusa con lo cual decidimos investigar y consultar a expertos en la materia para luego poder escribir este pequeño tutorial. En el cual intentamos esclarecer la funcionabilidad de este algoritmo. También agradecemos a la cooperación de Werner Almesberger que nos dedico un tiempito para aclarar algunas dudas al respecto y a German Roldán por hacer ese hermoso gráfico.
En este documento encontraremos una explicación algo avanzada para aquellos
con mayores conocimientos del tema y al final del documento una analogía
para aquellos que recien comienzan.
El TBF es un algoritmo que lo van a encontrar seguido en cualquier mecanismo de control de tráfico. El control de tráfico suele tener alguno de los siguientes objetivos:
-
Shaping: reducir ancho de banda
-
Policing: denegar paquetes que superen ciertos limites
-
Scheduling: Planificacion, para determinar que paquetes tienen prioridad de transmicion.
Nos vamos a detener en el primero, que es donde actua el TBF. El TBF es una mecanismo de control de tráfico que justamente sirve para reducir el ancho de banda. Por ejemplo, si estamos trabajando en un router, aplicando el TBF podemos reducir al ancho de banda de algun equipo en particular o de alguna aplicación o supongamos que necesitamos limitar a un host un determinado ancho de banda fijo, de manera tal que el mismo no moleste al resto de la red con sus “densas” descargas. Para eso será necesario un mecanismo que limite la cantidad de bytes por segundos que ese host desea descargar. También nos puede ser muy util en algun ambiente de laboratorio, para simular algun enlace que tenga bajo ancho de banda. De que manera lo hacemos?… una de las soluciones seria la aplicación del algoritmo Token Bucket Filter(TBF). La pregunta es, donde se aplica el TBF?… bueno, puede aplicarse en cualquier lado donde se transmita algo, por ejemplo, una interface de red (eth0, eth1, ppp0, etc) o en algun programa que realice transmicion de datos (un proxy server, un web server).
Para entender la explicación, vamos a referirnos siempre al control de tráfico en una interface de red. Despues veremos como aplicarlo a otra situación.
Veamos una explicación avanzada para los mas entendidos.
Linux en particular tiene asociado en cada interface una cola (queue), es el lugar donde se van guardando los paquetes que se tienen que tranmitir. Por defecto, se utiliza un mecanismo llamado FIFO, el primer paquete que entra en la cola es el primero que sale, siempre a maxima velocidad (lo que el hardware permita).
Ahora bien, agreguemos el TBF en alguna interface. La cola, ahora se llamará buffer. Este buffer tiene una capacidad en bytes (el parametro limit determina el tamaño del buffer), que cuando es superada no se podran guardar más paquetes y por lo tanto estos seran descartados (se dropean, desaparen, no existen mas 
). Este buffer tiene que vaciarse en algun momento, aca es donde aparece un termino nuevo, el bucket. El bucket almacena los famosos tokens (no confundir con Tocken Ring ni nada semejante, los token son solo simbólicos). El tamaño del bucket lo determina la variable burst y su valor, si el burst vale 10 tengo 10 tokens disponibles (son como creditos, si tengo credito puedo gastarlo, y un token equivale a un byte).
Entonces, sabemos que tengo paquetes esperando para salir del buffer, es importante que se entienda que si existen tokens en el bucket puedo enviar los paquetes a la MAXIMA VELOCIDAD QUE ME DEJA EL HARDWARE, esta velocidad máxima tambien podemos limitarla con la variable peakrate pero generalmente esta variable se deja por defecto. Luego de transmitir cierta cantidad de paquetes que tengo en el buffer, me voy a quedar sin creditos (tokens), ahi es donde aparece nuestra variable mas importante llamada rate, el rate es el encargado de medir la velocidad con la que los token llegan al bucket. Cuando recupero el credito? El credito se recupera de acuerdo al ancho de banda que yo configure en el shaper. Por lo tanto, podemos tener las siguientes situaciones:
-
Hay paquetes en el buffer y tengo credito: transmito hasta gastar el credito.
-
No hay paquetes en el buffer por cierto periodo y no tengo creditos: Los creditos durante ese periodo se recuperan hasta volver a llenar el bucket (el bucket tiene un valor maximo que se llama burst).
-
Del punto 2 volvemos a estar en la misma situacion que en el punto 1 si el buffer se llena de golpe de paquetes.
-
Ahora, supongamos que ni el buffer ni el bucket estan llenos, pero ambos tienen algo. Si la cantidad de tokens del bucket alcanza para transmitir como minimo un paquete del buffer, este se envia.
-
Que pasa si el buffer tiene algo, pero el bucket nada? Lo que esta en el buffer debe esperar a que haya suficientes tokens.
Bueno, esta es la base de TBF. Fijense lo siguiente, el ancho de banda maximo permito esta determinado por la velocidad en la que se recuperan los tokens (creditos). Si la velocidad a la que arriban los paquetes al buffer es similar a la velocidad a la que se recuperan los tokens, el bucket y el buffer van a mantenerse vacios siempre. Si la velocidad es mayor, los paquetes se acumularan en el buffer y el bucket estara siempre vacio. Si la velocidad es menor, el buffer estara siempre vacio y el bucket acumulara creditos de sobra.
Una ultima conclusion para entenderlo ( o para confundir mas ). EL TBF permite rafagas de datos a maxima velocidad. Si la cantidad de tokens es suficiente como para vacia el buffer, los paquetes acumulados se transmiten a lo que el hardware permita. Si luego de cierto periodo vuelven a entrar paquetes y el bucket tuve tiempo de llenarse, estos vuelven a trasmitirse a maxima velocidad. La conclusion es, el TBF regula el trafico que tenga un determinado ancho de banda por un periodo de tiempo prolongado.
Veamos una analogía (si entendieron lo anterior no lean esto por que puede confundirlos)
Nota: Es importante para entender la analogía realizar un dibujo a medida que
vayamos asociando las entradas y salidas, las máquinas y los recipientes con
los nombres colocados entre paréntesis. Los valores fueron tomados de manera
arbitraria. Igualmente el Gráfico que veremos a continuación nos ayudará a
comprender mejor este algoritmo.
Tenemos una fábrica de alfajores. En la misma se encuentran varios empleados que elaboran alfajores dependiendo de la cantidad de pedidos reciban de los clientes. También tenemos dos maquinas, una se encarga crear los envoltorios y la otra de envolverlos. Cuando llega un pedido de alfajores los empleados empiezan a elaborar los mismos y los ponen en un recipiente (buffer) que tiene capacidad (limit) para x cantidad de alfajores en este ejemplo pondremos 100, para luego ser envueltos por la máquina envolvedora. La misma envuelve cada alfajor(paquete) con el envoltorio(token) que se encuentra en un balde(bucket), ese balde a su vez también tiene una profundidad(burst) en donde se almacenan los envoltorios(tokens) en este caso al balde le pondremos una profundidad para 50 envoltorios. Complicamos la situación un poco. La máquina envolvedora de paquetes, envuelve un alfajor cada 5 segundos(a esta velocidad la llamamos peakrate), mientras que la otra máquina arroja un envoltorio al balde cada 10 segundos(a esta otra velocidad la llamamos rate). Ahora vayamos a la practica, los empleados estuvieron una hora inactivos con lo cual la máquina envolvedora de paquetes se encargo de terminar de envolver todos los alfajores que había en el recipiente(buffer) y la otra máquina a llenado el balde(bucket) de envoltorios(tokens). De repente empieza a llegar pedidos y los empleados comienzan a fabricar alfajores, los primeros 50 son envueltos a… (50 * 5 segundos) 250 segundos… , luego continua a la misma velocidad de la envolvedora hasta que se terminen los envoltorios que hay en el balde, luego estariamos envolviendo la cantidad restante cada 10 segundos ya que la máquina generadora de envoltorios trabaja a esa velocidad. Conclusión:
1- Si los empleados se esfuerzan pueden lograr que el recipiente(buffer)
rebalse y los alfajores sobrantes se desecharian. Para evitar que se rebalse
tendríamos que tener un recipiente(buffer) con mayor capacidad (limit).
2- Si queremos que la mayor cantidad de tiempo estemos trabajando a la
velocidad de la máquina envolvedora(peakrate) tendríamos que tener una
profundidad de balde(burst) bastante grande ya que es mas lenta que la
máquina envolvedora.
3- Si queremos que la mayor cantidad de tiempo estemos trabajando a la
velocidad de la máquina generadora de envoltorios(rate) tendríamos que tener
una profundidad de balde(burst) bastante pequeña.
4- También podemos modificar las velocidades de las maquinas a nuestro
antojo!
Fin de analogía.
Realizado por: Rodrigo D. Roldán (Roldyx) - e-mail = roldyx at linux.org.ar
Diego A. Woitasen (diegows) - e-mail = diegows at linux.org.ar
Julio de 2004
0 comments so far