Detalles del algoritmo de depósito de tokens

El algoritmo del depósito de tokens es uno de los algoritmos más utilizados para modelar el tráfico de red y limitar la velocidad. Normalmente, el algoritmo del depósito de tokens se utiliza para controlar la cantidad de datos transmitidos a la red y permitir la transmisión de ráfagas de datos.

Nombre chino: Introducción al algoritmo Token Bucket, parámetros de funcionamiento del Token Bucket, marcado, clasificación, introducción Al transmitir datos en la red, para evitar la congestión de la red, es necesario limitar el flujo de tráfico de salida. de la red para que el flujo pueda ser una transmisión de velocidad relativamente uniforme. El algoritmo del depósito de tokens implementa esta función, controlando la cantidad de datos transmitidos a la red y permitiendo la transmisión de datos en ráfagas. El algoritmo del depósito de tokens es uno de los algoritmos más utilizados para modelar el tráfico de red y limitar la velocidad. Normalmente, el algoritmo del depósito de tokens se utiliza para controlar la cantidad de datos transmitidos a la red y permitir la transmisión de ráfagas de datos. Un depósito de tokens con un tamaño fijo permite que los tokens se generen continuamente a un ritmo constante. Si los tokens no se consumen, o se consumen a un ritmo más lento del que se producen, los tokens seguirán aumentando hasta que se llene el cubo. Los tokens generados posteriormente se desbordarán del depósito. La cantidad máxima de tokens que se pueden contener en el último depósito nunca excederá el tamaño del depósito. Los paquetes enviados al depósito de tokens consumen tokens. Para paquetes de diferentes tamaños, la cantidad de tokens consumidos es diferente. Un depósito de tokens es un mecanismo de control que indica cuándo se puede transmitir el tráfico en función de si hay tokens en el depósito de tokens. Cada token en el depósito de tokens representa un byte. Si hay tokens en el depósito de tokens, se permite el tráfico; si no hay tokens en el depósito de tokens, no se permite el tráfico. Por lo tanto, si el umbral de ráfaga está configurado correctamente y hay suficientes tokens en el depósito de tokens, el tráfico se puede transmitir a velocidades máximas. El proceso básico del algoritmo del depósito de tokens es el siguiente: si la velocidad de transmisión promedio configurada por el usuario es r, entonces se agrega un token al depósito cada 1/r segundos, se supone que el depósito puede almacenar y emitir hasta; b fichas. Si el depósito de tokens está lleno cuando llega el token, el token se descartará cuando llegue un paquete de n bytes, se eliminarán n tokens del depósito de tokens y el paquete se enviará a la red si hay menos de; n tokens en el depósito, los tokens no se eliminarán y se considerará que los paquetes exceden el límite de tráfico; el algoritmo permite ráfagas de hasta b bytes, pero según los resultados de la ejecución a largo plazo, la velocidad de los paquetes es limitada. r constante, los paquetes que exceden el límite de flujo se pueden manejar de diferentes maneras: se pueden descartar; se pueden poner en cola para su transmisión cuando se hayan acumulado suficientes tokens en el depósito de tokens y se pueden continuar transmitiendo, pero se requiere un procesamiento especial; Marque, cuando la red esté sobrecargada, estos paquetes especialmente marcados se descartarán. Nota: El algoritmo Token Bucket no debe confundirse con "Leaky Bucket", otro algoritmo común. La principal diferencia entre los dos algoritmos es que el algoritmo del depósito con fugas puede imponer un límite en la velocidad de transmisión de datos, mientras que el algoritmo del depósito de tokens puede limitar la velocidad de transmisión de datos promedio y también permitir algunas transmisiones en ráfaga. En el "Algoritmo de depósito de tokens", siempre que haya tokens en el depósito de tokens, se permite que los datos se transmitan repentinamente hasta que se alcance un umbral configurado por el usuario, por lo que es adecuado para tráfico con características de ráfagas. El proceso de trabajo de los parámetros de trabajo del depósito de tokens incluye tres etapas: generación de tokens, consumo de tokens y determinación de si el paquete de datos ha pasado. Están involucrados dos parámetros: la tasa de generación de tokens CIR (tasa de información comprometida)/EIR (tasa de información en exceso) y el tamaño del depósito de tokens CBS (tamaño de ráfaga comprometido)/EBS (tamaño de ráfaga en exceso). A continuación utilizamos un cuadro para resumir brevemente la relación entre estas tres etapas y dos parámetros. Genere tokens: agregue tokens al depósito de tokens regularmente a una tasa de CIR/EIR, y la cantidad de tokens en el depósito continuará aumentando. Si la cantidad de tokens en el depósito ha alcanzado CBS/EBS, los tokens redundantes se descartan. Consumir token: los paquetes entrantes consumirán el token en el depósito. En la transmisión de red, el tamaño de los paquetes de datos suele ser inconsistente. Los paquetes grandes consumen más tokens que los paquetes pequeños. Determine si el paquete pasa: el resultado del paquete de entrada que pasa a través del depósito de tokens incluye los paquetes de salida y los paquetes descartados. Cuando la cantidad de tokens en el depósito puede satisfacer la demanda de tokens del paquete de datos, se genera el paquete de datos; de lo contrario, el paquete de datos se descarta. La medición y señalización del tráfico marcado se utiliza principalmente en arquitecturas de servicios diferenciados. La función del medidor es principalmente medir y probar las características de flujo del tráfico en función de las especificaciones de flujo relacionadas con el flujo, y determinar si cumple con las especificaciones de flujo y si cumple con las especificaciones de flujo acordadas. La base para la medición es la especificación comercial del flujo del paquete de servicios.

Esta etiqueta marca cada paquete IP medido como base para que la red procese el paquete en función de esta etiqueta en el futuro. En una arquitectura de servicios diferenciados, un paquete está marcado por su configuración y servicios. Las funciones de medición y marcado se completan en colaboración y los resultados de la medición se transmiten a la máquina de marcado como base para el marcado. El marcado generalmente se refiere a la combinación de dos funciones y su composición es como se muestra en la figura. Hay dos formas de clasificar los marcadores: una es clasificar los marcadores según diferentes colores, incluidos marcadores de dos colores y marcadores de tres colores, la otra es clasificar los marcadores según el mecanismo de implementación, incluidos los marcadores basados ​​en depósitos de tokens y los basados ​​en tasas; marcadores y marcadores basados ​​en políticas. Existen muchos algoritmos típicos de clasificación de tokens basados ​​en depósitos de tokens. El algoritmo básico incluye principalmente marcado de entrada/salida (FM) y marcado de tres colores (TCM), y el algoritmo extendido incluye principalmente marcado de tres colores de tasa única (srTCM) y marcado de tres colores de tasa dual (trTCM). Entre ellas, la calificación de tasa única y la calificación de tasa doble se denominan respectivamente recomendaciones estándar del IETF. Marca de entrada/salida justa (FM) FM es una marca de cubo de un solo token de dos colores. Su Tspec es la velocidad promedio de paquetes del sistema registrada como R, y la ráfaga permitida es b. Su principio de funcionamiento es que cuando llega un paquete IP, si hay suficientes tokens en el depósito, el paquete que satisface Tspec se marcará en. . Si no hay suficientes tokens en este momento, se considera que el paquete de datos que llega no cumple con Tpsec, y el paquete de datos que no cumple con Tpsec se marcará como OUT. La red puede realizar un procesamiento diferente en estos paquetes marcados. con diferentes atributos según la póliza correspondiente. Marcador de tres colores de tasa única (srTCM) srTCM es un marcador de cubo de token dual de tres colores cuyo Tpsec tiene tres parámetros: tasa de información comprometida, tamaño de ráfaga comprometido y tamaño de ráfaga excedente. CIR usa bps, CBS y EBS usan Byte. SrTCM consta de dos depósitos de tokens C y E, que tienen el mismo CIR y la misma capacidad de CBS y EBS respectivamente. La memoria del depósito C está llena de fichas amarillas y los depósitos de fichas C y E están llenos al principio. Si el paquete entrante no excede CBS, se marca en verde; si excede CBS pero no excede EBS, se marca en amarillo; de lo contrario, se marca en rojo; En DiffServ, el rojo, el amarillo y el verde se pueden asignar a diferentes valores DSCP. Marcador de doble velocidad (trTCM) trTCM también es un marcador de cubo de doble token de tres colores. Su Tpsec tiene cuatro parámetros: velocidad de información máxima (PIR), tamaño de ráfaga máxima (PBS), tasa de información comprometida (CIR) y ráfaga de cabello comprometida. tamaño (CBS). Las unidades de PIR y CIR son bps y las unidades de PBS y CBS son bytes.