PDF de programación - Tipos Abstractos de Datos para Desarrollo de Programas de Simulación en C++

Tipos Abstractos de Datos para Desarrollo de Programas de Simulación en C++



Marco Aurelio Alzate Monroy
Universidad Distrital F.J.C.

Resumen

La simulación de eventos discretos resulta una herramienta imprescindible para la evaluación de desempeño
de redes de comunicaciones. En este contexto, el uso de un lenguaje de propósito general para desarrollo de
programas de simulación tiene dos ventajas principales: el conocimiento previo que el analista tiene del
lenguaje y la flexibilidad que se gana al poder desarrollar cualquier modelo con el nivel de precisión deseado.
Sin embargo, debe invertirse un gran esfuerzo de programación para resolver problemas generales que nada
tienen que ver con el modelo particular que se quiere evaluar, tales como el control del avance del tiempo que
permita una secuenciación adecuada de los eventos, la generación de muestras de variables aleatorias para
modelamiento de tráfico y otros aspectos no determinísticos del modelo, la adquisición de estadísticas para
obtención de medidas de desempeño y el manejo de las colas que se forman en la competencia por los
recursos del sistema. Este artículo presenta algunos tipos abstractos de datos en C++ (clases) que resuelven
los cuatro problemas mencionados, permitiendo al analista desarrollar sus programas de simulación en C++
mientras concentra su esfuerzo de programación en el modelo particular y no en detalles adicionales. Con el
propósito de introducir la herramienta, se hace un repaso de los conceptos principales de la simulación de
eventos discretos y, finalmente, se muestran dos ejemplos de aplicación de la herramienta desarrollada.

1. Introducción

Para el correcto diseño de redes de comunicaciones es necesario contar con técnicas adecuadas de evaluación
de desempeño, las cuales incluyen la medición directa, el cálculo analítico y el uso de modelos de simulación.
Aunque cada enfoque tiene importantes ventajas sobre los demás, la simulación cobra cada vez mayor
popularidad debido a que la medición directa requiere la existencia y la disponibilidad de la red, lo cual es
una condición poco común en problemas de diseño, mientras que los cálculos analíticos suelen basarse en
simplificaciones de las interacciones entre los componentes del sistema, por lo cual sólo se obtienen
resultados aproximados que pueden estar muy distantes de la realidad[1].

Para la simulación de redes de comunicaciones se pueden utilizar paquetes de software de aplicación
específica como ComNet III o BONeS PlanNet, lenguajes de simulación como SimScript II.5 o GPSS, y
lenguajes de programación de propósito general como Pascal, C ó C++. En el primer caso se tiene la máxima
facilidad de uso pues, típicamente, se disponen de interfaces gráficas de alto nivel para la descripción de la
red y se puede dar inicio a la simulación sin ningún esfuerzo de programación. Sin embargo existen serias
limitaciones de flexibilidad pues sólo se pueden estudiar los sistemas que se construyan con los bloques
predefinidos en la herramienta[5]. Los lenguajes de simulación, en cambio, tienen mayor flexibilidad pues
permiten construir cualquier modelo, pero sacrifican la facilidad de uso al requerir un considerable esfuerzo
de programación. Esta opción también tiene la desventaja de que los ingenieros de comunicaciones que vayan
a desarrollar los experimentos de simulación deberán aprender un nuevo lenguaje de programación, lo cual
puede requerir un tiempo adicional considerable[5]. Por último, la utilización de un lenguaje de programación
de propósito general tiene las ventajas de que el ingeniero de comunicaciones puede estar familiarizado con él
previamente y de que la flexibilidad es máxima pues se pueden desarrollar los modelos con el nivel de detalle
que se desee. Sin embargo, a pesar de estas importantes ventajas, casi nunca se considera la opción de utilizar
un lenguaje de propósito general pues el esfuerzo de programación suele ser prohibitivamente excesivo. En
efecto, deben resolverse problemas delicados como la generación de variables aleatorias para modelar el
tráfico de entrada a la red, el control del avance de tiempo para secuenciar adecuada y eficientemente los
eventos, la adquisición de estadísticas sobre las medidas de desempeño de interés y el análisis de los
resultados de la simulación[4]. Sin embargo, si se pudiesen obviar estas dificultades de manera que el esfuerzo
de programación pudiera concentrarse en el desarrollo del modelo, podrían aprovecharse las ventajas de la
flexibilidad y el uso de una herramienta conocida que ofrecen los lenguajes de propósito general.
Como cada vez es más popular el lenguaje de programación C++, en este artículo se reporta la elaboración de
unos tipos abstractos de datos (clases en C++) que facilitan el desarrollo de programas de simulación de

eventos discretos en este lenguaje. Después de explicar brevemente en qué consiste la simulación de eventos
discretos y describir la herramienta desarrollada, se presentan algunos ejemplos prácticos de su utilización.

2. Simulación de Eventos Discretos

Desde una perspectiva de alto nivel, las redes de telecomunicaciones se pueden observar como unos recursos
de comunicación por los que los usuarios generan demandas y unos protocolos o algoritmos distribuidos que
controlan la asignación de los recursos de la red para satisfacer dichas demandas[1]. La generación de estas
demandas y cada uno de los pasos que sufren dentro de la red para ser atendidas constituyen eventos
instantáneos que alteran el estado de la red. Este procesamiento basado por eventos, natural en el contexto de
las redes de telecomunicaciones, conduce al método conocido como “Simulación de Eventos Discretos”,
DES[6].

En los modelos DES, hay un reloj de simulación que se actualiza con la ejecución ordenada de los eventos,
donde el Evento es la unidad básica ejecutable. Existe un conjunto de variables de estado que describen al
sistema, las cuales se modifican al ejecutarse las rutinas asociadas con cada evento. Para controlar la sucesión
de eventos se utiliza una lista de eventos futuros, LEF, en la cual se almacenan los próximos eventos en un
orden cronológico ascendente. Las rutinas asociadas con cada evento pueden añadir o eliminar eventos en la
LEF, para lo cual utilizan generadores de variables pseudo-aleatorias que representan el tráfico y otras
condiciones estocásticas dentro del sistema. Así, el algoritmo de simulación consiste, esencialmente, en
extraer de la LEF el evento más próximo, actualizar el reloj de simulación según el tiempo de activación de
dicho evento, llamar a la rutina correspondiente al evento seleccionado y repetir el proceso iterativamente
(Figura 1)[6].


Lista de Eventos
Evento Tiempo

E1
E2
.
.
.
E i
.
.
.
E j

T1
T2
.
.
.
T i
.
.
.
T j

T i

E i

Actualiza
el Reloj

Actualiza
el Estado
del Sistema

Actualiza las
Estadísticas

E j

T j

Determina un evento
posterior y su tiempo

de ocurrencia

Genera
Números
Aleatorios

No

¿Fin?

Si

Reporte



Figura 1. Flujo de una simulación DES



Por ejemplo, durante la simulación de un concentrador de datos en una red de transmisión de paquetes, la lista de
eventos consistirá en dos eventos futuros: la llegada del próximo paquete y el fin de transmisión del paquete que
se está atendiendo, si hay alguno. Cada vez que ocurre una llegada o un fin de transmisión, el simulador
determina cuánto tiempo transcurrirá hasta la próxima vez que este tipo de evento vuelva a suceder, le suma el
valor actual del reloj de simulación y almacena esta suma en la lista de eventos futuros. Así, para determinar cuál
será el próximo evento, el simulador simplemente debe buscar el mínimo de los tiempos almacenados en la
lista[1].

Como se puede observar en la figura 1, muchos de los algoritmos que se deben implementar son comunes para
cualquier simulación DES, independientemente del modelo particular que se esté evaluando. Los cuatro
problemas básicos que se deben solucionar son la sucesión de eventos adecuadamente ordenada en el tiempo, la
generación de variables aleatorias, la adquisición de estadísticas y, en el caso específico de modelos para redes de
comunicaciones, el manejo de buffers para administrar las demandas por los recursos[1].

2.1 Control del Avance del Tiempo


Respecto al primer problema, el algoritmo queda planteado en la Figura 1 y constituye el corazón de cualquier
programa de simulación DES. Una herramienta de software que implemente este algoritmo deberá disponer de
una LEF con algoritmos asociados que permitan la introducción de eventos futuros ordenados de acuerdo con su
tiempo de ocurrencia y una rutina principal que extraiga de la LEF el evento más próximo, actualice el reloj de
simulación y ejecute la rutina correspondiente al evento seleccionado. La interface con el usuario deberá incluir
dos funciones básicas: Activar_Evento, que le permite programar un evento futuro para su posterior ejecución, e
Iniciar_Simulación, con la que entrega el control a la rutina principal que desarrolla el algoritmo DES. Cuando el
programa retorne de esta rutina, ya la simulación habrá terminado.

Obsérvese cómo, de esta manera, el analista sólo debe preocuparse por definir cuáles son los eventos en su
modelo y desarrollar una rutina para cada evento. En el programa principal, dará inicio a la simulación después
de activar los primeros eventos, que suelen ser generadores de tráfico. El analista nunca deberá llamar las rutinas
de cada evento desde su programa, pues de eso se encargará la rutina de control de tiempo de acuerdo con la
secuenciación temporal de los