Proyecto BID/Conicyt 153/92
Departamento de Investigación Operativa - InCo
Facultad de Ingeniería, UDELAR, Montevideo, Uruguay

Copyright (c) 1992-1997 Universidad de la República.
Todos los derechos reservados.

Contenido

1  Prefacio

HEIDI provee un editor de redes y un conjunto de operaciones que permiten calcular distintas características de la red, así como buscar topologías alternativas con vistas a mejorar la confiabilidad [9,5]. HEIDI está disponible bajo el sistema operativo SunOS 4.1. Por más información sobre el equipo y el proyecto HEIDI, así como sobre los aspectos teóricos de las operaciones disponibles en la herramienta, es posible consultar la página WEB del Depto. de Investigación Operativa, situadas en la dirección http://www.fing.edu.uy/ cancela/io/io.html.

2  Introducción

La figura 1 muestra la interfaz gráfica de HEIDI, la cual está organizada en dos partes, el área de comandos, , la cual está situada en la parte superior de la pantalla, y el área de edición de grafos.

2.1  Área de comandos

• Menú de opciones, se encuentra en la parte superior y realiza las operaciones de archivos, configuración del ambiente, cáclulos sobre el grafo editado. etc. En la próxima sección se describen cada uno de los menús en forma detallada.
• Control del estado dd edición, el cual se encuentra en la parte inferior. Selecciona el estado de edición, el que varía según si se quiere dibujar, borrar o ponderar elementos del grafo (nodos y/o aristas).

2.2  Área de edición

3  Menú

3.1  Menú de Archivo

• Nuevo: crea un grafo nuevo. En el caso de que se esté editando y se seleccione esta opción, se despliega un cuadro de diálogo, que pide confirmación para borrar el grafo en edición. Si se desea grabar previamente el grafo, debe elegirse la opción No del cuadro, almacenar el grafo (con la opción Recuperar/Salvar del menú de Archivos), y ejecutar nuevamente la opción Nuevo.
• Recuperar/Salvar: graba o recupera un grafo. Al seleccionar esta opción, se despliega en pantalla una ventana donde se pide el nombre del archivo, luego de ingresado el nombre presione ENTER y seleccione el botón correspondiente a la operación a realizar (Salvar o Recuperar).

 









• Exportar/Importar: exporta o importa un grafo. Al seleccionar esta opción, se despliega en pantalla una ventana donde se pide el nombre del archivo, luego de ingresado el nombre presione ENTER y seleccione el botón correspondiente a la operación a realizar (Importar o Exportar).

• Directorio: permite visualizar una lista de archivos según el filtro especificado. Al seleccionar esta opción, se despliega una nueva ventana la cual nos muestra los archivos seleccionados según el filtro. Para seleccionar un conjunto de archivos con un patrón en común, muévase al campo del Filtro, digite el patrón adecuado (p.ej.: *.grf), y presione ENTER. Para ejecutar alguna de las operaciones del directorio (Recuperar o Importar) seleccione con el mouse un archivo de la lista desplegada en pantalla y presione el botón de la operación.

 









• Salir: permite cerrar la interfaz gráfica y salir de HEIDI.

3.2  Menú de Ver

• Valores Nodos: Configura los atributos de los nodos que se visualizarán en pantalla. Si se quiere visualizar cualquiera de los atributos de los nodos, seleccionar Valores Nodos del menú Ver y presionar el botón MOSTRAR correspondiente al atributo deseado. De forma análoga, para ocultar los valores de los atributos de los nodos, presionar el botón NO MOSTRAR correspondiente al atributo en cuestión.
• Valores Aristas: Configura los atributos de las aristas que se visualizarán en pantalla. Si se quiere visualizar cualquiera de los atributos de las aristas, seleccionar Valores Aristas del menú Ver y presionar el botón MOSTRAR correspondiente al atributo deseado. De forma análoga, para ocultar los valores de los atributos de las aristas, presionar el botón NO MOSTRAR correspondiente al atributo en cuestión.

 









• Tipo letra: permite configurar la familia, el estilo y escala de la letra. Para seleccionar una nueva familia elija Tipo letra del menú Ver, se desplegará un cuadro de diálogo en el cual elegirá con el botón derecho del mouse.

 









• Escala: determina el tamaño de visualización del grafo. Seleccionando esta opción se despliega un cuadro de diálogo que permite cambiar el tamaño del grafo de dos maneras: la primera es por teclado, digitando el valor del tamaño de visualización y presionando ENTER; la segunda es arrastrando con el mouse el botón de la barra del tamaño de visualización.









• Mover: permite mover el grafo en pantalla, siendo posible indicar en el cuadro de diálogo el valor del desplazamiento.

 

3.3  Menú de Agregación

• Hacer agregación: dado un conjunto de nodos marcados realiza una agregación. Para marcar los nodos que pertenecerán a la agregación se debe seleccionar cada uno de ellos con el botón derecho del mouse. Luego de marcar los nodos elija la opción Hacer Agregación en el menú Agregación, en ese momento todos los nodos marcados se incluirán en la agregación.
• Deshacer agregación: deshace una agregación realizada por la opción de Hacer agregación. Para efectuar esta operación, seleccione Deshacer agregación del menú Agregación, luego posicione el mouse sobre la agregación y presione el botón izquierdo.
• Ver agregación: permite visualizar una agregación, o sea que explota el contenido de la gregación (un subgrafo). Para visualizar una agrecación seleccione la opción Ver agregación en el menú Agregación, luego posicione el mouse sobre la agregación y presione el botón izquierdo.
• Salir agregación: se utiliza para salir del estado de visualización (explosión) de una agregación (por lo tanto, sólo se emplea cuando está en efecto una operación de Ver agregación).

3.4  Menú de Valores

• Aristas (Todas): asigna valores a los atributos de todas las aristas del grafo. Para asignar valores a todas las aristas, deberá seleccionar la opción Aristas del menú Valores. Se desplegará un cuadro de diálogo en el cual se puede asignar valor al o a los atributos que se desee.

 









• Nodos (Todos): asigna valores a los atributos de todos los nodos del grafo. Para asignar valores a todos los nodos, deberá seleccionar la opción Nodos del menú Valores. Se desplegará un cuadro de diálogo en el cual se puede asignar valor al o a los atributos que se desee.
• Nodos (Marcados): asigna valores a los atributos de los nodos marcados. Para asignar valores a un conjunto de nodos, deberá seleccionar la opción Nodos (Marcados) del menú Valores. Se desplegará un cuadro de diálogo en el cual se puede asignar valor al o a los atributos que se desee.

3.5  Menú de Algoritmos

Figura 2: Ventana de resultados

Nota: los campos de la ventana de resultados que aparecen en color claro reflejan resultados no actualizados y posiblemente incorrectos, ya posteriormente a su cálculo se produjo una modificación del grafo.

Las opciones del menú de Algoritmos son las siguientes:

• Costo: calcula la suma de los costos de todas las aristas del grafo. Es necesario que sea asignado un costo a cada arista; si una arista no tiene costo asociado, se toma por defecto el valor 0.
• Diametro: calcula el número de aristas que componen el camino más corto entre el par de nodos más distantes.
• Cintura: es el número de aristas que forman el ciclo más corto del grafo.
• Cohesion: es el mínimo número de aristas tales que al eliminarlas se desconecta el grafo.
• Conectividad: es el mínimo número de nodos tales que al eliminarlos se desconecta el grafo.
• Conexo: indica si el grafo es o no conexo.
• Grado min: es el grado del nodo de menor grado.
• Confiab (exacta): es la probabilidad de que todos los nodos del grafo estén conectados (medida de confiabilidad R_V). Para calcular esta medida, cada arista debe tener asignado un valor de confiabilidad; si no se asignó valor a alguna arista, se toma por defecto el valor 0 para su confiabilidad (ver el Menú de Valores para asignar confiabilidades a todas las aristas). Esta opción calcula la confiabilidad de forma exacta, utilizando el método de Ahmad extendido a R_V [3].
• Confiab (MC crudo): calcula la confiabilidad del grafo, utilizando simulación, y más particularmente el método Monte Carlo crudo (también llamado estándar). Al ejecutar esta opción aparece la ventana siguiente:

 






que pregunta la cantidad de replicaciones que se utilzarán en el cálculo de la confiabilidad.

• Confiab (Antit.Gr.): calcula la confiabilidad del grafo, utilizando el método de simulación Antitético generalizado [6,18] Al ejecutar esta opción aparece la ventana siguiente:

 






que pregunta la cantidad de bloques que se utilzarán en el cálculo de la confiabilidad, y el tamaño de cada uno. El ingreso debe hacerse dando los valores requeridos separados por una barra ("/").

• Arboles Cubr.: el número de árboles de cubrimiento del grafo [10,13].
• Optim (LS): propone un grafo alternativo al desplegado, intentando mejorar su confiabilidad (o vulnerabilidad) mediante el empleo de un algoritmo de búsqueda local simple (local search). Al ejecutar esta opción aparece la ventana siguiente:

 









que permite indicar la función objetivo a optimizar en la búsqueda. Las opciones son las siguientes:
 

• Función 1 (Tf0):

Cintura+grMin Diametro + Xe(2) + Xn(2) +2*cardE/cardX

• Función 2 (Tf1):

Cintura+grMin+Conectividad Diametro + Xe(2) + Xn(2) +2*cardE/cardX

• Función 3 (P0):

Cintura+grMin Diametro + Xe(Cohesion) + Xn(Conectividad) +2*cardE/cardX

• Función 4 (P1):

Cintura+grMin+Conectividad Diametro + Xe(Cohesion) + Xn(Conectividad) +2*cardE/cardX

• Función 5 (H1):

Cintura+Cohesion*Conectividad Diametro + Xe(Cohesion) + Xn(Conectividad)

• Optim (SA): propone un grafo alternativo al desplegado, intentando mejorar su confiabilidad mediante el empleo de un algoritmo de Simulated Annealing [7]. Al ejecutar esta opción aparece la ventana siguiente:

 









que permite indicar ciertos parámetros del algoritmo de búsqueda: Temperatura inicial, número de replicaciones, cota superior al costo del grafo, y parámetro b de descenso de temperatura. El ingreso debe hacerse dando los valores requeridos separados por una barra ("/"). En este método, la evaluación de la confiabilidad se realiza utilizando el método Monte Carlo crudo.

• Optim (SA+Antit.): propone un grafo alternativo al desplegado, intentando mejorar su confiabilidad (o vulnerabilidad) mediante el empleo de un algoritmo de Simulated Annealing. Al ejecutar esta opción aparece la ventana siguiente:

 









que permite indicar ciertos parámetros del algoritmo de búsqueda: Temperatura inicial, número de replicaciones, cota superior al costo del grafo, y parámetro b de descenso de temperatura. La evaluación de la confiabilidad se realiza utilizando el método Monte Carlo Antitético Generalizado.

• Confiab Rk (RVR): calcula la confiabilidad Rk del grafo, utilizando simulación, y más particularmente el método de Reducción Recursiva de la Varianza. Al igual que para el cálculo de la confiabilidad por MC crudo se debe especificar la cantidad de replicaciones. Para indicarse los nodos que forman del conjunto K de terminales, se deben setear con costo 1 tales nodos.
• Confiab Rk (MCC): calcula la confiabilidad Rk del grafo, utilizando el método de simulación Monte Carlo crudo. También se debe especificar la cantidad de replicaciones y los nodos terminales se indican de la misma forma que para el caso anterior.
• Confiab Rk (GCE): calcula la confiabilidad Rk exacta del grafo, utilizando el algoritmo de Generación Completa de Estados. Los nodos terminales se indican de la misma forma que para el caso anterior.

3.6  Menú de Entorno

• Desplegar estado: despliega el estado interno del editor de grafos.
• Grafo dirigido: configura el grafo como dirigido. En la pantalla se observa la dirección de cada arista por medio de una flecha ubicada en la mitad de la misma.
• Grafo no dirigido: configura el grafo como no dirigido (valor por defecto).

4  Edición

4.1  Estados

A continuación se describen los estados con mayor detalle.

4.2  Editor

Para insertar una arista alcanza con seleccionar el estado de EDITOR y luego seleccionar con el botón izquierdo del mouse los dos nodos entre los cuales se desea trazar la arista. Para insertar un bucle, se presiona dos veces sobre el mismo nodo.

Para mover un nodo alcanza con seleccionar el estado de EDITOR y posicionar el mouse en el lugar donde se desea insertar el nodo, presionando allí el botón derecho. El nodo acompañará el movimiento del mouse hasta que se presione el botón izquierdo, en ese momento quedará fijo en la nueva posición.

Para mover una arista alcanza con seleccionar el estado de EDITOR y luego seleccionar la arista colocando el mouse en un extremo de la misma y presionando el botón derecho; se posiciona el mouse en el nuevo nodo extremidad, y se presiona el botón izquierdo para soltar la arista.

4.3  Cambio de atributos

Por lo tanto existe una manera de cambiar el valor de estos atributos para un elemento del grafo específicamente. En el caso del cambio de atributos de un nodo, basta con seleccionar el estado CAMBIAR ATRIBUTOS del control del estado de edición y seleccionar el nodo posicionando el mouse sobre él y presionando el botón izquierdo. Aparecerá un cuadro de diálogo que permite elegir el atributo correspondiente y ponderarlo. Para cambiarse de atributo utilice el mouse y luego de ingresar el valor presione ENTER (en todos los atributos).

En el caso del cambio de atributos de una arista, basta con seleccionar el estado CAMBIAR ATRIBUTOS del control del estado de edición y seleccionar la arista posicionando el mouse sobre uno de sus extremos y presionando el botón izquierdo. Aparecerá un cuadro de diálogo que permite elegir el atributo correspondiente y ponderarlo. Para cambiarse de atributo utilice el mouse y luego de ingresar el valor presione ENTER (en todos los atributos).
 

4.4  Borrado de elementos del grafo

Para borrar un nodo se selecciona el estado BORRAR NODO del control del estado de edición y luego se elige el nodo a borrar posicionándose sobre él con el mouse y presionando el botón izquierdo.

Para borrar una arista se selecciona el estado BORRAR ARISTA del control del estado de edición y luego se elige la arista a borrar posicionándose sobre uno de sus extremos con el mouse y presionando el botón izquierdo.

5  Problemas conocidos

• El ingreso de cualquier dato debe ser completado presionando la tecla Enter antes de elegir los botones de aceptar o continuar, sin lo cual el dato no es considerado por el programa. Esto se da tanto en los ingresos de un dato único (como parámetro de un cálculo, o nombre de archivo, etc.), como en los ingresos de múltiples datos (valores de aristas y nodos).
• Diferencias de funcionamiento en la asignación de valores al costo, confiabilidad y capacidad de las aristas y nodos: cuando se asigna valor vía el menú de (asignar costos a todas las aristas, todos los nodos, o todos los nodos seleccionados), esos valores son números reales; en cambio, cuando se utiliza la funcion cambiar atributo del editor, es posible ingresar no solo valores reales sino tambien cualquier texto (para realizar los calculos, los textos corresponden a valores de 0). Este comportamiento tambien se da en la grabacion y exportacion/importación de grafos, en los cuales es posible que las ponderaciones de nodos y aristas sean textos arbitrarios.
• El orden de los valores costo, confiabilidad y capacidad es distinto para las aristas (costo, confiabilidad y capacidad) y para los nodos (confiabilidad, costo y capacidad). Esto puede aparejar confusiones.
• Para importar un grafo, es necesario que cada nodo tenga una etiqueta diferente; al exportar un grafo, es posible que esta condición no se cumpla, y luego no sea posible importarlo nuevamente en la herramienta (este problema no aparece con las opciones de Salvar y Recuperar).
• El formato de exportación de un grafo no indica si el mismo es orientado o no orientado.
• Aunque es posible editar grafos orientados y no orientados, la algoritmia utilizada sólo es correcta en el caso no orientado (si se utiliza en un grafo orientado, implícitamente se elimina la orientación).
• El cálculo de confiabilidad exacta por el método de Ahmad tiene un error que ocasiona la caída del programa cuando se desea evaluar un grafo con solo dos nodos.
• El ingreso de parámetros de los métodos de cálculo no controla la existencia de todos los parámetros requeridos: si el usuario no los ingresa en el formato indicado, se toma por defecto el valor 0 para los mismos, aún cuando no es el más adecuado.
• El editor de grafos permite ingresar multigrafos (grafos con múltiples aristas entre el mismo par de nodos), y también bucles (aristas de un nodo a sí mismo). La algoritmia no soporta este formalismo, por lo que los resultados de las operaciones son indefinidos en este caso (así como los resultados de exportar un multigrafo). Las operaciones de Salvar y Recuperar en cambio, están bien definidas.
• La opción Directorio del menú de Archivo sólo permite visualizar la lista de archivos del directorio de arranque de HEIDI, y seleccionar para Recuperar o Importar un archivo de esta lista; no es posible cambiar el directorio de trabajo en forma dinámica. Para recuperar un grafo almacenado en otro directorio, es necesario ingresar su ubicación manualmente (en forma absoluta, o relativa al directorio de arranque de HEIDI).
• El manejo de errores y situaciones de excepción no es muy sofisticado, reduciéndose a mensajes en pantalla y a veces en la ventana de comandos de donde se ejecutón inicialmente HEIDI. No existe una lista completa de los errores que pueden producirse durante la ejecución del programa.
• El número máximo de nodos y aristas soportados por la algoritmia es respectivamente de Nro_Max_Nodos=200 y Nro_Max_Aristas=1000; para alterar este número, es necesario modificar estas constantes en los archivos de cabezal nodo.h y grafo.h y recompilar el programa.
• HEIDI no funciona bajo el emulador del entorno Unix X-Win32.

6  Referencias

[1]

An improvement to the total hazard method for system reliability simulation. H. Cancela and M. El Khadiri. Probability in the Engineering and Informational Sciences, 10(2):187-196, 1996.

[2]

A recursive variance-reduction algorithm for estimating communication-network reliability. H. Cancela and M. El Khadiri. IEEE Transactions on Reliability, 44(4):595-602, December 1995.

[3]

Network reliability evaluation by the Ahmad Method H. Cancela Bosi, M.E. Urquhart, G. Rubino, en Proceedings de XXIII Conferencia Latinoamericana de Informatica CLEI, a realizarse en noviembre 1997 en Valparaiso, Chile.

[4]

A simulation algorithm for source-terminal communication network reliability. H. Cancela and M. El Khadiri. en Proceedings de 29th Annual Simulation Symposium, pages 155-161, New Orleans, Louisiana, April 1996. IEEE Computer Society Press.

[5]

Evaluation and design of communication networks. H.Cancela, G.Rubino, M.E.Urquhart. En Proceedings de ICIL'95, International Conference on Industrial Logistics. Ouro Preto, Brazil, December 1995. University of Southampton, UK, and Naval Monterrey School, USA.

[6]

Métodos Monte Carlo en la estimación de la confiabilidad de redes de comunicaciones - Estado del arte. H. Cancela, M. Urquhart. En Proceedings de 24 JAIIO, Jornadas Argentinas de Informática e Investigación Operativa, Buenos Aires, Argentina, August 1995

[7]

Simulated Annealing and Communication Network Optimization. H. Cancela, M. Urquhart. PANEL'95 - XV SBC - Canela, Brasil, July 1995. In Proceedings of XXI Latin American Conference on Informatics. CLEI - SBC.

[8]

Fast Monte Carlo methods for evaluating highly dependable Markovian systems .H. Cancela, G. Rubino and B. Tuffin. In 2nd International Conference on Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, Salzburg, Austria, Julio 1996.

[9]

HEIDI: una herramienta de apoyo a la evaluación y diseño de redes. H. Cancela, L. Petingi, G. Rubino, and M.E. Urquhart. En VIII CLAIO, ALIO (Asociación LatinoamericanoIberoamericana de Investigación Operativa) - SOBRAPO (Sociedad Brasilera de Pesquisa Operacional). pages 581-586, Rio de Janeiro, Brazil, August 1996.

[10]

Computation of two communication network vulnerability indexes. L. Petingi and M.E. Urquhart. En VIII CLAIO, Congreso Latinoamericano de Investigación Operativa, ALIO - SOBRAPO, Rio de Janeiro, Brazil, August 1996.

[11]

Simplification techniques in Monte Carlo network reliability evaluation. H. Cancela and M. El Khadiri. In VIII CLAIO, ALIO-SOBRAPO, pages 587-592,Rio de Janeiro, Brazil, August 1996.

[12]

Construcción de modelos para la evaluación de la seguridad de funcionamiento. H. Cancela and G. Rubino.In VII CLAIO, Santiago, Chile, July 1994.Resumen extendido elegido para su publicación como artículo.

[13]

Algorithms for the computation of communication network vulnerability indexes. L. Petingi and M.E. Urquhart Technical Report INCO 96-04, PEDECIBA Informática, Facultad de Ingeniería, UDELAR, 1996.ISSN 0797-6410.

[14]

Network reliability evaluation by the Ahmad method. H. Cancela, G. Rubino and M. Urquhart. Technical Report INCO 96-03, PEDECIBA Informática, Facultad de Ingeniería, UDELAR, 1996.ISSN 0797-6410.

[15]

Series-parallel reductions in Monte Carlo network reliability evaluation. H. Cancela and M. El Khadiri. Technical Report INCO 96-01, PEDECIBA Informática, Facultad de Ingeniería, UDELAR, 1996.ISSN 0797-6410.

[16]

Elección de un método Montecarlo para el cálculo de la medida Rv de confiabilidad en redes de comunicaciones y su implementación en la herramienta HEIDI. H. Cancela, M. Urquhart, Technical Report INCO 95-05 ISSN 0797-6410.

[17]

Simulated Annealing and Communication Network Optimization. H. Cancela, M. Urquhart. Technical Report INCO 95-02, March 1995.ISSN 0797-6410.

[18]

Métodos Monte Carlo en la estimación de la confiabilidad de redes de comunicaciones - Estado del arte- , H.Cancela M. Urquhart, Technical Report INCO 94-06. ISSN 0797-6410.

[19]

A recursive variance-reduction algorithm for estimating communication-network reliability H. Cancela, M. El Khadiri Technical Report PI860, IRISA, Rennes, september 1994.