Inesperables

Luis Enrique Sánchez Loor

Redes de Datos I, Escuela Superior Politécnica del Litoral
Campus Prosperina, Guayaquil, Ecuador

luiensan@espol.edu.ec

Abstract— Este documento expone la importancia de la teoría de colas para el análisis de sistemas y de la preparación para consideraciones del rendimiento de este. Entre sus aplicaciones se encuentran los sistemas de telecomunicaciones.

Keywords— Cola, Queue, Telecomunicación, Telecommunication, Aplicación, Application.

1. Introducción

El contenido del documento explica la manera en la que un ingeniero o analista de sistemas de telecomunicaciones,  emplea la teoría de colas en resoluciones de rendimiento de una red. La utilización de esta teoría nos brinda la capacidad de predecir, mediante modelos de procesos estocásticos, efectos sobre una red ante cambios. Ya sean cambios planificados o de imprevisto, el correcto estudio del comportamiento de una simple cola nos dará una visión más detallada de factores estadísticos esenciales del rendimiento de la red, tales como el tiempo de respuesta, el retardo y el throughput. Al hallar los resultados para una simple cola también se puede estimar para varias colas, las cuales son parte del sistema de telecomunicaciones.

Se expone el interés en sistemas de colas guiado a las telecomunicaciones, en donde encontramos numerosas aplicaciones para protocolos conocidos como TCP/IP, frame relay, ATM, etc. De todas maneras, se empezará conociendo su importancia a sistemas comunes en general.

1. Teoría de Colas

En la vida cotidiana existe el fenómeno, del cual todos hemos sido parte en algún momento, que trata acerca de la formación de líneas de espera para la atención de cierto servicio. Estas líneas de espera, o también llamadas colas, aparecen cuando la demanda de clientes supera la capacidad de atención del servicio en interés.

Actualmente se escucha con frecuencia su utilización en campos de tecnología e informática, ya que este campo siempre está creciendo en rendimiento de cliente-servidor.

Los problemas de formación de colas, explicadas como clientes que esperan en cola por falta de recursos necesarios para atender peticiones,  normalmente se concentran en la velocidad variable de llegada de peticiones de los clientes y la velocidad variable del servicio en prestarles atención.

Fig. 1  Diagrama que muestra dos decisiones fundamentales a tomar para la creación o modificación de un sistema.

En el diseño de un modelo de colas, aparece el análisis matemático estadístico, el cual nos provee de varias opciones para dicho modelo. En la Fig. 1 nos resalta el balance económico en las decisiones del administrador en el momento de la implementación de un sistema [2]. La teoría de colas nos ayuda a la toma de estas decisiones, a pesar de que no se resuelve a pleno estos costos.

El objetivo de la teoría de colas es el de encontrar el balance más óptimo entre los aspectos cualitativos del servicio y los cuantitativos de costos, considerando en el mayor de los casos la satisfacción del cliente en el momento de calificar su paciencia consumida.

1. Elementos de un Modelo de Colas

Definimos en primera instancia el proceso básico de un modelo de colas. En determinado tiempo, llega un cliente con petición de uso del servicio. Este cliente se agrega a una cola, en donde espera mientras se es atendido a los otros miembros existentes en la cola, mediante alguna política de selección conocida como disciplina de servicio. Al ser elegido el cliente, es atendido por medio de un mecanismo de servicio, luego de lo cual el cliente sale del sistema.

1)  Fuente de Entrada: Conocida también como la población potencial, su característica importante es el tamaño. Estas unidades se las conoce luego como población de entrada, por lo que se categoriza según su tamaño entre finito o infinito (limitado o ilimitado). Resulta más sencillo analizar la fuente de entrada en caso infinito, ya que no hay que considerar los clientes ya presentes en la línea de espera dentro del sistema. Sin embargo, se debe especificar el patrón estadístico mediante el cual acuden los clientes en el tiempo. En nuestro caso de forma aleatoria, se usa una distribución Poisson con cierta tasa media fija indiferente de cuantos clientes se encuentren ya ahí.

2)  Cola: El elemento básico de este estudio es, sencillamente, la formación de los clientes en espera a un servicio específico. Los clientes pueden ser personas, usuarios finales, paquetes de datos, etc. La propiedad principal de la cola es su límite, similar al caso con la fuente de entrada, es más sencillo analizar una cola sin límite (infinito) que una con límite (finito).

3)  Disciplina de la Cola: Se refiere al orden de selección de clientes para ser atendidos por el sistema. Los métodos más comunes encontramos:

• FIFO (first in, first out) el primero en llegar es el primero en ser atendido.
• LIFO (last in, fisrt out) el último en llegar es el primero en ser atendido.
• RSS (random selection of service) los clientes son atendidos de manera aleatoria.

4)  Cliente: Es todo agente o individuo que inicia una petición a un servicio en específico. Forman parte de la cola, ya que son quienes participan de forma activa en el estudio de un sistema. En el campo de las telecomunicaciones, estos clientes serían paquetes de datos con todos los encabezados requeridos para la aceptación y operación del servicio a solicitar. Los clientes necesitan ser analizados por medio de una distribución estadística para dar información de tiempos entre llegadas.

5)  Mecanismo de Servicio: Es el proceso de servicio entregado al cliente. El mecanismo de servicio consiste en una o más instalaciones de servicio, cada una de ellas con uno o más canales paralelos de servicio, llamados servidores. Si existe más de una instalación de servicio que se active de manera secuencial, se conoce como canales de servicio en serie. El tiempo que se necesita desde que un cliente entra al proceso, hasta que termina se conoce como tiempo o duración de servicio. De manera similar a los clientes, la atención del servicio debe ser modelado con distribuciones probabilísticas de los tiempos de servicio. (ejemplos de sistemas de colas reales y, proceso de nacimiento y muerte de modelos Poisson [3]).

1. Servicio y Atención

La manera en que llegan las peticiones de los clientes, se puede modelar de tres diferentes maneras en cuanto al tiempo entre llegadas. La forma determinística, es el caso en donde ese intervalo se mantiene constante y no suceden cambios. La forma probabilística  nos dice que el tiempo de llegadas es variable, se definen mediante una distribución de probabilidad.

Esta última forma mencionada es la más empleada para analizar sistemas actuales, donde los clientes son personas o usuarios que por medio de canales de comunicación (paquetes de datos) realizan peticiones. Para esto se usan distribuciones, la distribución exponencial ha demostrado brindar mayor confianza que otras. Su función de densidad depende del valor de l y está dada por:

• f (t) = (1/l)e^-lt. Donde l es el promedio de llegadas por unidad de tiempo.
• P(tiempo entre llegadas <= T) = 1-e^-lt. Para hallar probabilidad de que el siguiente cliente llegue dentro de T tiempo.

Fig. 2  Gráfica: Probabilidad vs Tiempo (segundos). Distribución de probabilidad exponencial para l=10.

El método en que las estaciones de servicio atienden a los clientes se conoce como proceso de servicio. Puede estar dispuesto de manera tal que todos los clientes que llegan reciben la misma atención, para más de una instalación de servicio. A esto se le conoce como sistema de canal múltiple, indiferentemente de si estas instalaciones comparten el mismo servidor. Otra disposición de estas estaciones, es la de canal sencillo. En este arreglo existe una única instalación que brinda el servicio requerido, y puede estar formada por más de un servidor que opere simultáneamente en el requerimiento.

El proceso de servicio debe estudiar si permite la prioridad en las peticiones de ciertos clientes. Un ejemplo claro son las emergencias en una clínica u hospital. Por otro lado, se debe determinar el retardo que demanda el servicio y así tener la idea de la cantidad de tiempo que debe esperar un cliente para salir del sistema. De manera similar al proceso de llegada, existen los mismos factores para los tiempos de atención.

Determinístico para estaciones que brinden a los clientes con un intervalo aproximadamente constante, la atención que demanda. Probabilístico para intervalos inciertos de atención al proceso dado por un cliente. Para la última instancia se le fía la distribución exponencial y su correspondiente función de densidad f (t) = (1/m)e^-mt, dependiente de m. Donde m es el número promedio de clientes atendidos por unidad de tiempo.

Existen varios estudios matemáticos de estas distribuciones que son parte de la teoría de colas, los cuales acompañan a la toma de decisiones y las aplicaciones que se les puede asignar  (lectura de distribuciones de probabilidad en detalle en [4], [5]).

1. Notación Kendall

Por estándar, la teoría de colas se etiqueta para conocer los métodos de distribución de probabilidad seleccionada y el orden que existe o se supone aplicar, para las estaciones de servicio.

TABLA I
Formato de Notación Kendall

Modelo Básico (Extendido)
A/B/n1/(n2/n3/n4)
Elemento	Valores posibles
A	G, M, D, E
B	G, M, D, E
n1	número de servidores
n2	número máximo de clientes
n3	disciplina (FIFO,LIFO,RSS)
n4	tamaño población donde se originan los clientes

Para propósitos generales, es suficiente un modelo básico, de todas maneras se da a conocer los parámetros para el modelo extendido. De acuerdo a la Tabla 1, el elemento A será el tipo de distribución usada para los intervalos de tiempo de llegada de clientes. Las opciones de distribución general (G), exponencial de Markov (M), determinísticas (D) o del tipo Erlang (E). El elemento B es la distribución para la atención del  servicio, se usan las mismas siglas. El elemento n1 informa sobre el número de servidores usados para el sistema.

Los elementos que siguen son parte de la notación Kendall extendida, los cuales son del tipo limitantes o de disciplina del proceso de colas (una visión más detallada en [6]).

III.  Diseño del Sistema de Telecomunicación

Se ha expuesto la teoría de colas como metodología importante en el comportamiento y rendimiento de un sistema, mediante el uso de fórmulas derivadas de distribuciones de probabilidad. Para el caso de una red de telecomunicaciones los requerimientos o peticiones de los clientes, se transforman en paquetes de red que circulan por un medio, hasta llegar al destinatario otorgador de algún servicio en particular.

Fig. 3  Esquema  básico de un sistema de colas [7].

La cola en telecomunicaciones, como de manera general, se forma cuando la demanda del servicio supera la capacidad del mismo. La meta del administrador de la red será mantener un promedio aceptable de capacidad de atención del servicio. No bastará con ser mayor que el promedio de requerimientos del servicio, al menos que, la tasa con la que estas peticiones llegan esté distribuida en el tiempo constantemente entre una y otra.

Una característica importante de las llegadas al sistema, es la dependencia de estas con otras en cualquier instante de tiempo. En el caso de una población potencial grande, es independiente lo que un cliente decida o no usar un servicio. Tal es el caso de personas en una heladería, donde los clientes deciden que saber o tipo de helado consumir sin importar lo que haya pedido clientes anteriores.

Desde el punto de vista del servicio se opera de la misma forma, estudiando la independencia o no de la tasa de tiempo invertido en atender a un cliente, afecte o no, a la atención de algún otro que llegue en el futuro. Resumiendo entre llegadas de peticiones y atención a dichas peticiones, tenemos [7]:

• Llegadas constantes - atención constante
• Llegadas aleatorias - atención constante
• Llegadas constantes - atención aleatoria
• Llegadas aleatorias - atención aleatoria

1. Desarrollo de la Red

La última categoría anteriormente expuesta, es en donde cae un sistema de telecomunicaciones dado que son los usuarios finales los que realizan las peticiones a los servidores, y estas peticiones varían con el tiempo al igual que la atención prestada para atenderlas.

Casos como llamadas telefónicas a una central de cierta empresa, no depende una de otra para ser realizadas. Las transferencias de datos de archivos a través de un servidor, son atendidas de la misma manera sin depender del tiempo que demore en llegar la petición. De estos ejemplos podemos rescatar la importancia en la duración del proceso del sistema en atender una cola, como también las propiedades de la red para tolerar paquetes de cualquier tamaño.

Las distribuciones de Poisson y exponencial, brindan un muy buen manejo en la interpretación y predicción de eventos para llegadas aleatorias y para atenciones aleatorias. Sin embargo el análisis a realizar en este documento, será sencillo usando fórmulas de nivel básico donde se asume que las peticiones se originan independientemente desde un tamaño grande población.

Libros y fuentes donde explican más profundamente las distribuciones mencionadas en la teoría de colas (en [4], [5]).

1. Fórmula Básica

La teoría de colas, contiene varias fórmulas derivadas de funciones de distribución de probabilidad. Estas son parte de procesos estocásticos, los cuales describen el rendimiento de operación de un sistema. Se empleará el análisis proyectado a sistemas de comunicación con paquetes como clientes, desde un nivel general.  A continuación se presenta una fórmula básica de retardo para hallar el nivel del tiempo en atender una petición o de esperar en la cola.

Fig. 4  Fórmula básica del retardo en atender a un requerimiento en cola. En donde el retardo (D) depende del uso (U) y de la velocidad de atención de la estación de servicio (Ts).

El entendimiento de esta fórmula es sencillo. Cuando el uso del servidor crece, con una tasa constante de atención de parte de la instalación de servicio, el tiempo de espera en la cola aumenta. Al alcanzar el 50% de uso, el tiempo de espera se vuelve directamente dependiente de la velocidad del proceso de atención por parte de la instalación de servicio. En el caso de que el uso llegue al 100% significará una saturación en el servidor, puesto que el retardo en atención se vuelve infinito, lo que se concluirá un mal desempeño del sistema.

En las telecomunicaciones hay que prevenir este tipo de saturación, recomendando que no pase del 50% de utilización. Un efecto similar ocurre en la comunicación de paquetes de datos por una red LAN, donde un router atiende al paquete entrante siempre que se encuentre desocupado. Estos tiempos de retardo, aumenta la latencia de transmisión de datos por una red, como también otros factores de rendimiento de la misma.

La utilización (U) del servidor y la velocidad de la estación de servicio (Ts) también describen que tan ocupado se encuentra el servidor. Continuando con ejemplo del router, si un paquete de 10000 bits es transmitido por un canal DSL a 56 kbps, el paquete ocupará .185 segundos más un adicional de retardo causado por factores eléctricos. Durante ese tiempo ningún otro paquete o cliente podrá usar ese servicio, esto es lo que se conoce como velocidad de la estación de servicio o Ts [7].

1. Factor de Relación de Utilización

Como parte de la fórmula expuesta en la Fig. 4, se encuentra una relación entre utilización (U) y su complemento (1-U), que define lo ocupado que se encuentra una estación de servicio. Cuando "U" es menor que el 50% se obtiene la tasa de atención de servicio multiplicada por una fracción. Para el caso contrario, es por un número entero lo cual hace una gran diferencia de tiempo, ya que el retardo se incrementa de manera exponencial. En otra palabras, si el factor de  relación de utilización es mayor que uno, el tiempo de espera se incrementa rápidamente provocando congestión y posible saturación, como se muestra en la Fig. 5.

Fig. 5  Gráfica Retardo vs Utilización, para tres clases de Ts  [7].

Se concluye entonces que para velocidades de recursos más altas, el retardo se ve menos afectado para los valores crecientes de utilización. Por lo que si el medio de comunicación entre el cliente y el servidor es rápido, el retardo disminuirá indiferentemente de lo ocupado que se encuentre el servidor. Lo mismo si tenemos una estación de servicio de tasas rápidas de atención, esto se ve en calidad de los dispositivos de una red. Un router de mejor calidad y velocidad de procesamiento, colaborará con la prevención de incrementos en la línea de espera, a comparación de uno de menor calidad.

La tasa de velocidad promedio de atención de un servidor, será también dependiente del tipo de petición o paquete a procesar. Esto es en el caso de un paquete grande, al ser procesado por un router, a pesar de que sea rápido, existirá mayor retardo en comparación a paquetes de menor tamaño. Entonces se dice que para requerimientos grandes, hay más posibilidad de quedar saturado, que con requerimientos pequeños. Será importar considerar este análisis en el momento de establecer límites o políticas de transacciones (peticiones) de servicio, dado que se puede producir un aumento de utilización en cualquier instante provocando que las curvas de retardo alcance picos indeseables.

A pesar de que se empleó una fórmula muy básica, se conoce que en las redes de hoy, no existe un control en el envío de paquetes de datos, ni tampoco en la atención a estos requerimientos. Lo que resulta en la aleatoriedad de ambas partes, concentrando el estudio del rendimiento en la ocupación del servidor en sí. Por lo que no está tan mal usar este análisis, para concluir el desempeño de algún dispositivo de la red.

1. Aplicación en VOIP

Un análisis rápido de la aplicación de la teoría de colas para este caso, muestra que el esperar en colas disminuye la calidad del sentido de la aplicación si es tratada como cualquier otro tipo de paquete. Para el caso de voz sobre IP, los paquetes de datos no pueden darse el lujo de tener retrasos arduos y comunes. Más bien debe operar una configuración en donde se priorice cierto tipo de paquetes para procesar, esto es, crear un esquema de prioridades dentro de las distribuciones de estos procesos.

Resulta algo complejo el estructurar esos esquemas, por lo que se debe considerar factores de utilización de servidores y velocidad de los mismos como se ha visto. El mejor de los casos sería operar en servidores libres de congestión, o evadiendo estas congestiones en caso que las hubieran. En tal caso los dispositivos también serían parte fundamental en el desempeño de la red, ya que habrá que cuidar que no hayan bajas velocidades de atención en alguno de ellos.

IV. Conclusiones

La teoría de colas es importante en el diseño de cualquier sistema, dado que el mundo real, la mayoría de servicios existentes contienen la estructura básica expuesta en el documento, por lo que el desarrollo libre en extender este concepto para nuevas tecnologías siempre estará presente, y por ende su importancia de estudiarla.

En el campo de las telecomunicaciones, se adaptaron los elementos de un sistema de colas a lo conocido tecnológicamente. Esto es, el cliente pasó a ser paquete de datos. La disciplina de cola, se instanció dependiendo de la configuraciones de los dispositivos de red. Las instalaciones de servicio, son servidores, o cualquier otro dispositivo intermedio de red, como routers o switches. La adaptación de estos elementos, promovieron el entendimiento de la teoría de colas dentro de los sistemas de telecomunicación.

Una vez adaptada la terminología se confirmaron, por medio del análisis de una fórmula general de retardo, factores importantes dentro de un reporte de rendimiento de la red. Tales como la utilización del servidor y la velocidad del servidor. El factor de relación de utilización del servidor, nos dio una visión matemática y medible del porcentaje de saturación de una entidad de servicio. El tamaño de los paquetes influye en cambios no esperados de velocidad de servidor.

La velocidad del servidor dependiente más que nada de los dispositivos empleados, aunque importante, tienes sus falencias en ambas cotas. Esto es, si la velocidad es baja, el retardo crecerá rápidamente conforme a la utilización. En el caso de que la velocidad sea alta, el retardo no subirá tan de golpe, sino hasta que alcance cierto porcentaje de utilización en donde peligrará la saturación total del sistema en caso de que haya un salto brusco de utilización.

Agradecimientos

Quiero agradecer antes que todo a la capacidad de investigación y comprensión brindada todo este tiempo de mi vida por parte de mi familia. Luego por la oportunidad de experimentar mi primer artículo utilizando formatos internacionales de la IEEE, de parte de la Ingeniera Patricia Chávez.

Referencias

[1]        Wikipedia the free encyclopedia. Throughput. (2010) [Online]. Available: http://en.wikipedia.org/wiki/Throughput.

[2]        Matías Martínez Ferreira, julio 2006. Wikilearning. (2010) [Online]. http://www.wikilearning.com/monografia/la_teoria_de_colas /15124

[3]        Facultad de Ingeniería, Universidad Santa María, República Bolivariana de Venezuela. Cátedra: "Investigación de Operaciones. Teoría de Colas", noviembre 2009. Tecnológico. (2010) [Online]. http://www.mitecnologico.com/Main/TeoriaDeColasProcesoDeNacimientoYMuerteModelosPoisson

[4]        Docstoc, Documents for Small Business and Professionals. Telecommunications Queuing Theory, julio 2010. (2010) [Online]. http://www.docstoc.com/docs/21520711/Telecommunications-Queuing-Theory

[5]        John N. Daigle. "Queuing Theory with Applications to Packet Telecommunication". University of Mississippi, MS 38677, 2005. Telecom Books Blog. (2010)[Online]. http://telecombooksblog.com

[6]        Tijms, H.C,Algorithmic Analysis of Queues, Capítulo 9. A First Course in Stochastic Models, Wiley, Chichester, 2003.

[7]        McGuire Consulting. "Applying Queuing Theory for Network Design". (2010) [Online]. http://mcguireconsulting.com/newsl_queuing.html