Si observamos la funcionalidad de los puertos de entrada y salida y las configuraciones indicadas en la Figura 3, es evidente que se pueden formar colas de paquetes tanto en un puerto de entrada como en un puerto de salida. En importante analizar estas colas con un poco más de detenimiento, pues cuando crecen en exceso pueden desbordar el espacio de buffers del router, ocasionando pérdida de paquetes. Es común indicar que los paquetes se “pierden dentro de la red” o “se eliminan en un router”. Es justo aquí, en estas colas internas del router, donde se eliminan y se pierden tales paquetes. La ubicación real de la pérdida de paquetes (bien en las colas de los puertos de entrada, bien en las colas de los puertos de salida) dependerá de la carga de tráfico, la velocidad relativa del entramado de conmutación y la velocidad de la línea, como ya se indicará más adelante.
Supongamos que las velocidades de las líneas de entrada y de salida son idénticas, y que hay n puertos de entrada y n puertos de salida. Si la velocidad del entramado de conmutación es al menos n veces superior que la velocidad de la línea de entrada, no habrá colas en los puertos de entrada. La razón es que aún en el peor de los casos (que las n líneas den entrada estén recibiendo paquetes), el conmutador será capaz de transferir n paquetes desde los puertos de entrada a los de salida, a la vez que cada uno de los n puertos de entrada reciben (simultáneamente) un único paquete. Pero, ¿qué pasa en los puertos de salida? Supongamos que el entramado de conmutación es al menos n veces más rápido que las líneas de salida. En el peor de los casos, los paquetes que lleguen a cada uno de los n puertos de salida irán destinados al mismo puerto. En este caso, en el tiempo que lleva recibir (o enviar) un solo paquete, llegarán otros tantos n paquetes a este puerto de salida. Puesto que el puerto de salida sólo puede transmitir un único paquete en una unidad de tiempo (el tiempo de transmisión del paquete), los n paquetes entrantes tendrán que hacer cola (esperar) para ser transmitidos por el enlace de salida. Aún así, podrían llegar n paquetes más en el tiempo empleado en la emisión de uno de los n paquetes que han estado haciendo cola previamente, y así sucesivamente. Finalmente, el número de paquetes haciendo cola puede crecer lo suficiente como para agotar el espacio de memoria del puerto de salida, en cuyo caso se perderán paquetes.
El encolamiento en el puerto de salida se ilustra en la Figura 5. En el instante t, llega un paquete a cada uno de los puertos de salida, cada uno destinado al puerto de salida superior.
Suponiendo idénticas velocidades en las líneas y un conmutador operando tres veces más rápido que la velocidad de la línea, una unidad de tiempo más tarde (es decir, justo el tiempo necesario para recibir o enviar un paquete) cada uno de los tres paquetes originales ha sido transferidos al puerto saliente, uno solo de estos tres paquetes habrá sido transmitido por el enlace de salida. En nuestro ejemplo, dos nuevos paquetes llegan al punto de entrada del conmutador; uno de estos paquetes va destinado al puerto de salida superior.
Una consecuencia del encolamiento en los puertos de salida es que el planificador de paquetes en el puerto de salida deberá elegir un paquete entre aquéllos que esperan ser transmitidos. La selección podrá hacerse siguiente un método simple, como la planificación primero en llegar-primero en ser servido -FCFS, first-come-first-served), o siguiendo un mecanismo de planificación más sofisticado, como la espera equitativa ponderada -WFQ, weighted fair queuing-, que comparte el enlace de salida equitativamente entre las diversas conexiones punto a punto que utilizan la cola para su transmisión. La planificación de paquete juega un papel crucial en la obtención de garantías de calidad de servicio.
Igualmente, si no hay suficiente memoria para alojar un paquete entrante, deberemos decidir entre desechar el paquete entrante -esta política se conoce como drop-tail-, o eliminar uno o más de los paquetes ya almacenados para hacer espacio al paquete recién llegado. En algunos casos, es bueno desechar (o marcar para eliminar en la cabecera) cierto paquete antes de que el buffer se llene, para evitar tener que enviar una señal de congestión al emisor.
En Labrador16 se han propuesto y analizado cierto número de políticas de desecho y marcado de paquetes, conocidas colectivamente como algoritmos de gestión activa de colas -AQM, active queue management-. Uno de los algoritmos AQM más ampliamente estudiados e implementados es el algoritmo de detección temprana aleatoria -RED, random early detection-.
En RED, se mantiene una media ponderada para la longitud de la cola de salida. Si la longitud media de la cola es menor que un umbral mínimo, minu, cuando llegue un paquete será admitido en dicha cola. En cambio, si la cola está llena o si la longitud media de la cola es mayor que cierto umbral maxu, cuando llegue un paquete será marcado o desechado. Finalmente, si el paquete llega a una cola cuya longitud media se halla en el intervalo [minu, maxu], el paquete probablemente será marcado, siendo dicha probabilidad una función de la longitud media de la cola, minu y maxu. Se han propuesto varias funciones de probabilidad de marcado/desechado, y se han modelado, analizado, simulado y/o implantado diversas funciones de RED. Christiansen17 y Floyd18 dan una visión general y referencia de lecturas adicionales.
Figura 5. Encolamiento en los puertos de salida.
Si el entramado de conmutación no es lo suficientemente rápido (con respecto a las velocidades de las líneas de entrada) a la hora de transferir todos los paquetes entrantes en el entramado sin demora, también habrá esperas en las colas de los puertos de entrada, donde los paquetes esperarán su turno para ser transferidos a través del entramado de conmutación hacia los puertos de salida. Para ilustrar una importante consecuencia de esta espera, consideremos un entramado de tipo crossbar, y supongamos que: (1) todas las velocidades de los enlaces son idénticas, (2) un paquete puede ser transferido de cualquier puerto de entrada a un puerto de salida dado en el mismo tiempo que lleva la recepción de un paquete por un puerto de entrada, y (3) los paquetes se mueven desde una cola de entrada dada a su cola de salida al modo FCFS. Varios paquetes podrán ser transferidos en paralelo cuando sus puertos de salida no coincidan. Sin embargo, si dos paquetes que están en el extremo de dos colas de entrada van destinados al mismo puerto de salida, uno de ellos se bloqueará, y deberá esperar en la cola de entrada; el entramado de conmutación sólo puede transferir un paquete a un puerto dado en cada momento.
La Figura 6 muestra un ejemplo de dos paquetes en el extremo de sus colas de entrada que van destinados al mismo puerto de salida, que es el superior. Supongamos que el entramado de conmutación elige transferir el paquete de la cola entrante superior. En ese caso, el paquete de la cola inferior deberá esperar. Pero no sólo este último, sino también el siguiente paquete que le sigue, incluso en el caso de que no haya conflicto por el puerto de salida del medio (que es el de destino de este paquete). Este fenómeno se conoce como bloqueo en la cabeza de la línea -HOL, head-of-the-line- en una entrada del conmutador; cierto paquete que espera en una cola de entrada debe esperar a ser transferido a través del entramado (incluso aunque el puerto de salida esté libre), puerto que se encuentra bloqueado en ella por otro paquete a la cabeza de la línea. Karol19 demuestra que debido a un bloque HOL, la cola de entrada podía crecer sin límite (en otras palabras, que habría una pérdida significativa de paquetes) bajo ciertas condiciones tan pronto como la tasa de llegada de paquetes en los enlaces de entrada alcance sólo el 58% de su capacidad. En McKeon20 1997b se discuten varias soluciones al bloque HOL.
Figura 6. Bloqueo en colas de entrada HOL de un conmutador.
16 M. Labrador, S. Banerjee, "Packet Dropping Policies for ATM and IP Networks," IEEE
Communications Surveys, Vol. 2, No. 3 (Third Quarter 1999), pp. 2-14. Ver
http://www.comsoc.org/livepubs/surveys/public/3q99issue/banerjee.html
17 M. Christiansen,
K. Jeffay, D. Ott, F. D. Smith, "Tuning Red for Web Traffic,"
IEEE/ACM Transactions on Networking, Vol. 9, No. 3 (June 2001), pp. 249-264,
Ver http://www.cs.unc.edu/~jeffay/papers/IEEE-ToN-01.pdf
18 S. Floyd, "References on RED
(Random Early Detection) Queue Management," Ver
http://www.icir.org/floyd/red.html
19 M. Karol, M.
Hluchyj, A. Morgan, "Input Versus Output Queuing on a Space-Division
Packet Switch," IEEE Transactions on Communications, Vol. COM-35, No. 12
(Dec. 1987), pp. 1347-1356.
20 N. McKeown, M. Izzard, A. Mekkittikul,W.
Ellersick, M. Horowitz, "The Tiny Tera: A Packet Switch Core," IEEE
Micro Magazine, Jan.-Feb. 1997. Ver http://tiny-tera.stanford.edu/~nickm/papers/HOTI_96.pdf