PDF de programación - Tesis: Hugo Solano - Núcleo para Manejar Eventos en Tiempo Real Caso Particular Programación de Algoritmo de Enrutamiento Distribuido

-If IIIYESTIUCIU ' t\

IITUB18S ""z 'I•U DH

I. P . N .

• I . L IOTEC-'\
1NG£NIEI!IA ELECTRICA

CENTRO DE INVESTIGACION Y ESTUDJOS

AVANZADO

lnstituto Politecnico National

SECCION DE COMPUTACION

Ntlcleo para Manejar Eventos en Tiempo Real Caso Particular
ProgramaciOn de Algoritmo de Enrutamiento Distribuido.

Autor: Hugo Julio Solano Condor.

Asesor: Dr. Manuel Guzman Renteria.

Tesis para recibir el grado de Maestro en Ciencias en Ia especialidad de

Ingenieria Electrica.

CIN

:STA V
p 'I

I'DO'J1.11':10N
DE L"3,1S

- - - -- -

Mexico, D. F. Septiembre de 1994.

u•TRI g( l~YESTI6ACit• Y &l

UTUBIIS A v.- z •. ~S I OH

I. P. N .

a t • Lt OT ECA
'"'GENIEI!IA ELECTRICA

xM
C' • '>•~.
Q 4../7
"C'•JUIS .8/ l'f3~5
..,. 7 <f<.!
PROCEO "~ ...

,.I:.('HJ

AGRADECIMIENTO.

A asesor, Dr. Manuel Guzman Rentaria, que me apoyo en todo sentido para Ia
realizacion de este trabajo,

A mis Padres, que su apoyo moral fue fundamental para lerminar mis estudios,

A mi Hermana Ana y mis Hermanos Gonzalo y Alejandro por su colaboracion,

A mis alumnos de Ia Universidad NUR, que realizaron muchas pruebas de este
trabajo,

Y finalmente muy en especial a mi esposa Maye y mi Hijo Julio Edwin. A ellos
dedico este trabajo y esfuerzo.

Hugo Julio Solano Condor

CUTU II( /NVESTIUCJU y t;

fSTUIJU AV.NZA&el tEL

I.P. N.

IB LI OT EO .O.
•
"'~tNIERIA ElfCTRIU

INDICE

I. OBJETIVOS.

PARTE I

CAPITULO 1 ALGORITMO DE ENRUTAMIENTO DISTRIBUIDO

1.1. INTRODUCCION
1.2. ALGORITMO DE ENRUTAMIENTO DISTRIBUIDO

1.2.1. CARACTERISTICAS DE UN NODO
1.2.1 . PROCESOS DE UN NODO

1.3. ALGORITMO 'CAMBIO DE RED"

1.3.1. DESCRIPCION DE LOS ALGORITMOS.

1 .4. EJEMPLOS.

1
2
4
4
7
7
12

CAPITULO 2 C_CONCURRENTE PARA MANEJAR EVENTOS EN
TIEMPO REAL

2.1. INTRODUCCION.
2.2. DISENO DEL NUCLEO (NUCLEO.ASM)
2.3. DISENO DEL MONITOR
2.4. PRIMITIVAS DE CONCURRENCIA.

2.4.1. SEMAFOROS.
2.4.2. DESPERTADORES
28
2.4.3. MENSAJES.

20
21
21
27
27

28

CAPITULO 3 PINCEL

3.1. INTRODUCCION
3.2. DISENO DE PINGEL

3.2.1 . FUNGIONES PRIMITIVAS
30
3.2.2. FUNGIONES PARA MANEJAR VENTANAS
3.2.3. FUNGIONES PARA GENERAR LOS FONTS

29
30

31
32

CAPITULO 4 PROGRAMACION DE ALGORITMO DE ENRUTAMIENTO

4.1. INTRODUGGION
4.2. PROGRAMACION

4.2.1. CARACTERISTICAS DE UN NODO.

4.2.1.1. TABLAS EN EL NODO
4.2.1.2. BUZONES
4.2.1 .3. VARIABLES DE CONTROL
4.2.1.4. ESTRUCTURA DEL NOOO PARA C-Gonc.
4.2.1.5. ESQUEMA DE CONGURRENGIA
4.2.1.6. FUNGIONES DE PINGEL

4.2.2. PROGESOS POR GADA NODO
4.2.3. ALGORITMO "GAMBIO DE RED"
4.2.4. AGTUALIZAGION DE LA TABLA DE RUT AS
4.2.5. FUNGIONES DE APOYO

CAPITULO 5 PRUEBAS Y CONCLUSIONES

5.1. PRUEBAS
5.2. CONCLUSIONES
5.3. FUTURAS MEJORAS

33
34
34
34
35
36
36
36
38
39
40
44
44

46
53
56

PARTE II

APENDICE A 818UOGRAFIA

57

APENDICE B PINGEL (Interface Grafica)

8.1. PINCEL.C
8.2. NUMGEN
8.3. TEXT.H
8.4. NUM.H

APENDICE C CODIGO DE NUCLEO Y MONITOR

C.1. NUCLEO.ASM
73
C.2. MONITORC

APENDICE D CODIGO DE RUTI (Aigoritmo de Enrutamiento)

D.1. PROLOGO.H
D 2 TOPO.H
0.3. RUTT.C
90
D.4. M _ SIM.C

APENDICE E CONSIDERACIONES DE USO

58
65
68
71

80

85
89

97

101

APENDICE F APLICACION DEL ALGORITMO DE

ENRUTAMIENTO DISTRIBUIDO PARA INTERCONECTAR
REDES LOCALES

106

I. OBJETIVOS

El desarrollo del presente trabajo de tesis esta enmarcado en el area de Sistemas de Tiempo

Real. yen particular en Ia programacion de un Algoritrno de Enrutamiento Distribuido.
Este trabajo naci6 de Ia idea de encontrar un algoritmo del Nivel de Red para implementarlo
como parte de un proyecto en Ia construcci6n del modelo OSI de ISO.

Se debe mencionar que el Modelo OSI es un standard recomendable en el diserio de una Red
que tiene 7 Niveles o capas. Estos niveles son: Nivel Fisico. Nivel de Enlace de Datos, Nivel de
Red. Nivel de Transporte, Nivel de Sesi6n. Nivel de Presentacion y Nivel de Aplicaci6n. El
presente trabajo esta enmarcado en el Nivel de Red. que se encarga del enrutamiento de Datos
en una Red.

Objetivos y Requerimientos

Los requerimientos que debe cumplir el paquete y el algoritrno son:

1) Debe ser un Algoritrno Oistribuido Adaptativo. Es decir. Ia eleccion del camino por donde
debe ir un mensaje en cada Nodo, se basan en una Tabla de paramentos minimos que esta
tiene. Esta Tabla debe ser resultado del intercambio de informaci6n entre los diferentes nodos
de Ia red, para encontrar rutas 6ptimas.

2) El algoritrno encontrado debe en lo posible cumplir con las Metas de un Buen Algoritmo
detalladas en el Capitulo 1.

3) Es lmportante que el algoritmo deba tener un mecanismo de Actualizaci6n rapido y seguro
para adaptarse a cualquier cambia de los parametros de Ia Red, como ser Distancias, Costas o
Retardo. Este mecanismo oermitir hacer conocer a todos los demas Nodos de Ia Red sabre
estos cambios en Ia forma mas rapida.

4) Debe ser sencillo de programar. es decir, las Estructuras y el c6digo del Algoritmo deben
ser muy flexibles y sencillas para poderlo implementar en un Nodo, pudiendo usar cualquier
lenguaje e inclusive el Ensamblador.

5) Mostrar Ia simulaci6n de varias Topologia con situaciones Diferentes para permitir
demostrar que el algoritmo funciona.

6) Construir las herramientas basicas (Nucleo. funciones de despliegue. etc) que permitan
Programar Otro tipo de Algoritrnos de Enrutamiento basados en Tablas, y tambien los que no
estan basados en T ablas.

7) Facilitar el uso del paQuete a cuaiQuier persona Que desea saber el comportamiento de un
Algoritmo para una determinada Topologia. Proporcionar una material didactico para alumnos
de Redes de Licenciatura o Maestria.

Una vez establecido los reQuerimientos, definimos el alcance de esta Tesis con el Dr. Manuel
Guzman, que consiste en construir un NUcleo que permita mostrar el funcionamiento de un
Algoritmo de Enrutamiento Distribuido. La elecciOn del Nucleo (ProgramaciOn Concurrente)
permite facilidad y claridad en Ia programaciOn de Ia actividad de cada Nodo.

Desarrollo de Ia Solucilin.

Se decidiO usar el algoritmo Que maneja distancias Minimas, considerando a cada enlace de
Ia Red con un peso de 1. Para implementar el Algoritmo Que considere costo minimos o
retardo minimo solamente se debe dar peso a cada enlace o revisar constantemente Ia Cola de
los buzones de las salidas de cada Nodo. Es importante Que tenga un mecanisme Que permita
actualizar las tablas de los Nodos dado un cambio en los parametres de Ia Red. Se penso en
dos alternativas: a) Que el rnecanismo sea mediante envio de Ia Tablas de Rutas cada
determinado Tiempo (ARPANET). b) Manejar mensajes de control cada vez Que se produzca
un cambia en los parametres.

Se decidiO usar Ia Segundo opciOn, dado Que en el primero debe implementarse un Reloj
para controlar el enviar de los mensajes cada determinado tiempo. En Ia segundo opciOn, EL
PROPIO algoritmo. de acuerdo a Ia informaciOn Que puede darle Ia Capa de Enlace sobre
activaciOn de algun enlace o Nodo, o los cambios en los costos o el tamano de las colas para
cada salida, puede determinar si existe cambios en Ia Tabla y activar su mecanisme de
Actualizaci6n a toda Ia Red.

lnvestigando entre revistas y Journals se encontrO un Algoritmo Que cumple muchos de los
reQuerimientos propuestos. Tajibnapis, el autor del articulo, describe con mucho detalle el
funcionamiento y sugiere tambien algunas pautas de implementaciOn.

Una vez elegido el Algoritmo, se desarrollo todo el trabajo. En el Primer Capitulo se muestra
un estudio del algoritmo de Enrutamiento seleccionado, para conocer su comportamiento en
varias situaciones. Esto se muestra usando ejemplos.

Una vez realizado el estudio, se empezO a disenar un Nucleo sobre el cual se ProgramO el
algoritmo. La decisiOn de usar un Nucleo es basicamente para facilitar Ia programaciOn de Ia
actividad de los Nodos, y poder darle mayor independencia a cada Nodo. Para esto se
aprovecho del Turbo C y se construyO un peQueno nucleo con 3 funciones basicas
(newprocess, transfer,
iotranfer) las cuales permiten realizar un cambio de contexte
rapidamente. Estas PRIMITIVAS se construyeron en lenguaje ensamblador por Ia sencillez y
rapidez QUe presenta el mismo.

En base a estas priminvas, se construyO un MONITOR que permite administrar el
calendarizador (SCHEDULER) y las colas de semaforos. mensajes y despertadores. Este se
construyo en C aprovechado su eficiente manejo de apuntadores y listas.

Para Ia visualizaciOn del Comportamiento del Algoritrno se diseM una pequena libreria de
tunciones que permiten desplegar texto, ventanas, lineas. numeros, etc. Estas funciones
realizan acceso DIRECTO a memoria de Ia tarjeta CGA, evitando asi usar interrupciones. Todas
las funciones de esta libreria estan en base a 4 runnas: (1) Encender a apagar un punta en Ia
pantalla en Ia posiciOn X,Y, (2) dibujar una linea usando el algoritmo de Breseenham, (3)
despliegue de tetras y numeros y finatmente (4) los mecanismos de manejo de ventanas. Los
detalles del desarrollo de esta pequena intertace se explican en el Capitulo 3.

Finalmente, teniendo el Nucleo y las funciones de despliegue, se programo el Algoritrno de
Enrutamiento Distribuido. Oebo mencionar que en Ia programaciOn se tomo muy en cuenta Ia
sencillez del mismo. Es decir, que cualquier persona con conocimientos de lenguaje C puede
entender Ia acnvidad del algoritrno viendo el cOdigo del programa. Los detalles de Ia
programacion se muestran el Capitulo 4.

Presentation de los Resultados

Se realizaron pruebas con varias !apologias (se seleccionaron