# Algoritmo de enrutamiento para un modelo de red en anillo

###### Integrantes: Franco Artico, Francisco Percivaldi y Martin Piloni

***
## Índice
[TOC]

***

## Resumen
El objetivo principal de este trabajo se basó en el análisis y desarrollo de un algoritmo de enrutamiento. En este informe, se explorará en detalle tanto la solución de este problema como los análisis previos y posteriores a la implementación del algoritmo.

## Introducción
En el código dado por la cátedra tenemos una topología de red en forma de **anillo** _full duplex_ en la que cada nodo se conecta exactamente con dos vecinos a los que puede transmitirle información al mismo tiempo, formando lo que es una única ruta continúa por donde pueden mandarse los paquetes.
A continuacion, dejamos una imagen ilustrativa de la red en cuestión:


Cada nodo de este modelo cuenta con:

- Una **capa de aplicación** (```app```).
- Una **capa de red** (```net```).
- Dos **capas de enlace** (```lnk[0]``` y ```lnk[1]```).

La **capa de aplicación** implementa generadores de tráfico y la **capa de enlace** _buffers_, tal como vimos en laboratorios anteriores. En el caso de la **capa de red** ella es quien decidirá por que interfaz enviar los paqutes que le llegan, ya sea desde la capa de aplicación superior o desde la capa de enlace.

Por lo tanto, cada nodo está constituido de la siguiente manera:


Entonces, la capa de red entregada por la cátedra es muy símple y funciona de la siguiente forma:

- Cada paquete que se recibe es evaluado para determinar si el nodo actual es el destino final del mismo.
- En el caso de que lo sea, **el paquete es enviado a la capa de aplicación** local.
- **De lo contrario**, se elige una interfaz para retransmitirlo.

> La capa de red de la cátedra elige siempre la interfaz número 0, que es la que envía el tráfico en sentido de las agujas del reloj.

En la tarea de análisis se pide analizar el rendimiento del sistema de enrutamiento planteado, para este experimento lo evaluaremos en dos casos
- **Caso 1**: Fuente de tráfico configurada de tal manera que los nodos ```node[0]``` y ```node [2]``` transmitan datos a ```node[5]```.
- **Caso 2**: Fuente de trafico configurada de tal manera que todos los nodos generan tráfico hacia ```node[5]``` .

Luego, se desarollara un algoritmo de enrutamiento que supere al planteado por la cátedra y se compararan los resultados de las mediciones.

## Resultados de la simulación sin el algoritmo implementado
### Caso 1

> Fuentes de trafico configuradas de tal forma que los nodos 0 y 2 transmiten paquetes de datos al nodo 5.

#### Ocupacion de buffers


Podemos ver que los nodos 1, 6 y 7 tienen comportamientos similares, esto se debe a que estos nodos solo transmiten los paquetes de datos pero no los generan, luego como la tasa de datos en la que reciben paquetes es igual a la que envian la ocupacion de su buffer se mantiene constante. Tambien se puede observar que los nodos 3 y 4 no forman parte del grafico, esto es debido a que como siempre los paquetes se envian en sentido horario y son generados en los nodos 0 y 2 luego estos nodos no transmiten paquetes, esto sera claramente una desventaja pues estamos desaprovechando parte de la red y por lo tanto los nodos por los que se transmiten los paquetes tendran una mayor carga.

Tanto en el nodo 0 como en el nodo 2, donde en ambos se generan paquetes, se tiene un comportamiento distinto al de los demas nodos, veamos mas en detalle lo que ocurre:

##### Buffer del nodo 0


Este nodo es uno de los que genera los paquetes de datos, por lo tanto el buffer de este nodo recibe paquetes de datos tanto de su capa de aplicacion como de los que le transmite el nodo 1 (generados en el nodo 2). Debido a esto se puede observar que el crecimiento del buffer crece linealmente pues en lo que este nodo envia un paquete se reciben dos paquetes, uno a traves del nodo 1 y otro a traves de su capa de aplicacion.

##### Buffer del nodo 2

Este nodo tambien se encarga de generar paquetes de datos pero la diferencia con el nodo anterior es que este no recibe paquetes de ningun otro nodo, luego la unica forma de que la ocupacion de este buffer aumente es que el nodo genere paquetes mas rapido que lo que demora en enviarlos, esto puede ocurrir a veces como se observa en el grafico pues la generacion de paquetes esta ligada a una distribucion exponencial centrada en 1.

##### Buffers de los nodos 1, 6 y 7


Estos nodos tienen comportamiento similares pues no se encargan de generar paquetes si no que solamente transmiten los paquetes de datos generados por los nodos 0 y 2, ademas como la tasa de datos a la que reciben es igual a la que envian luego la ocupacion de sus buffers oscilara siempre entre 0 y 1.

#### Cantidad de saltos


Los paquetes se generan tanto en el nodo 0 como en el nodo 2 y siempre se enviaran en sentido horario, luego es evidente que la cantidad de saltos que tendran los paquetes para llegar a su destino, el nodo 5, oscilara entre tres y cinco pues del nodo 0 al nodo 5 hay cinco saltos y del nodo 2 al nodo 5 hay tres saltos.

#### Delay de los paquetes


Este grafico representa lo que demora en llegar un paquete desde el nodo origen al nodo destino. Es posible notar que la demora crece linealmente, esto se debe a lo que ocurre en el nodo 0: Como la ocupacion del buffer crece linealmente entonces a medida que el buffer este mas ocupado mas deberan esperar los paquetes antes de ser enviados al siguiente nodo lo que hara que demoren mas en llegar al destino.

#### Uso de los recursos de la red
Como se ha discutido previamente podemos ver que no existe un uso eficiente de la red, esto se debe a que todos los nodos envian sus paquetes en sentido horario y no toman una decision en base a la distancia o al estado de la red. En este caso se puede observar que los nodos 3 y 4 nunca reciben ni envian paquetes desaprovechando parte de la red mientras que el nodo 0 crece linealmente. Para mejorar esto se puede implementar un algoritmo de enrutamiento que decida cual es la mejor ruta para cada paquete en cada momento dado de la red, basandose tanto en la distancia como en el estado de cada nodo.

### Caso 2

> Fuentes de trafico configuradas de tal forma que todos los nodos transmiten paquetes de datos al nodo 5.

#### Ocupacion de buffers


Es posible notar que el crecimiento lineal en este caso ocurre en casi todos los nodos, esto se debe a que ahora todos los nodos generan paquetes de datos y transmiten al mismo tiempo, lo que genera un comportamiento similar al del nodo 0 en el caso 1.

Veamos mas en detalle el nodo que no tiene el mismo comportamiento a los demas:

##### Buffer del nodo 4

Se puede observar un comportamiento similar al del buffer del nodo 2 en el caso 1. Esto se debe a que el nodo 4 solo envia los paquetes que genera el mismo pero no reenvia paquetes de otros nodos dado que todos los nodos envian en sentido horario y al nodo 4 solo le podria enviar el nodo 5, pero este es el nodo destino que no envia paquetes.

#### Cantidad de saltos


En este caso como todos los nodos generan paquetes de datos, la cantidad de saltos que realiza un paquete para llegar del nodo origen al nodo destino puede variar desde 1 a 7 dado que hay 7 nodos que originan paquetes todos destinados al mismo nodo destino.

#### Delay de los paquetes


Se puede observar un aumento del delay de los paquetes en comparacion al caso 1, esto es debido a que ahora la ocupacion de todos los buffers incrementa en vez de solo incrementar la ocupacion del buffer del nodo 0, luego cada paquete tiene que esperar mas tiempo en cada buffer antes de ser reenviado hasta llegar al destino. Tambien es importante notar que el crecimiento es lineal esto es debido a que al principio los buffers no estan ocupados, pero a medida que pasa el tiempo la ocupacion de los buffers crece de manera lineal.

La oscilacion se da debido a que el delay dependera de en cual nodo se origine el paquete recibido, pues si el paquete se origina en un nodo que requiera pocos saltos en sentido horario para llegar al nodo destino entonces el delay sera menor que si el paquete se origina en un nodo que requiera muchos saltos para llegar al destino.

### Estabilizacion de la red
Para hablar de estabilizicacion de la red primero es necesario definir el concepto:
Este concepto se refiere a que la ocupacion de todos los buffers se mantendra constante y no crecera linealmente, por lo tanto el delay de los paquetes no crecera linealmente, manteniendo asi estable el tiempo que cada paquete demora en llegar de un nodo origen a un nodo destino.

Para encontrar la estabilidad de la red se hicieron pruebas con distintos valores de InterArrivalTime, variable que determina cada cuanto tiempo se generara un paquete en los nodos origen. Recordemos que la generacion de los paquetes esta ligada a una distribucion exponencial.

#### Exponencial centrada en 3

##### Ocupacion de buffers

Se puede notar que la ocupacion de los buffers de la mayoria de los nodos sigue creciendo linealmente, luego no se consigue una estabilidad de la red con este valor.

##### Delay de los paquetes

En el punto anterior se vio que la ocupacion de los buffers crece linealmente luego por consecuente el delay de los paquetes tambien crecera linealmente, objetivo contrario al que se busca.

#### Exponencial centrada en 5

##### Ocupacion de buffers

En este caso tambien se ve que la ocupacion de los buffers de algunos nodos crece linealmente pero es importante notar que a medida que crece el centro de la distribucion exponencial la ocupacion de los buffers es menor.

##### Delay de los paquetes

Como se vio anteriormente que la ocupacion de los buffers crece linealmente luego con el delay ocurrira lo mismo, se puede ver que el delay de los paquetes es menor que en el caso con una exponencial centrada en 3.

#### Exponencial centrada en 7.5

##### Ocupacion de buffers

Se ve como la ocupacion de todos los buffers se mantiene constante a traves de los 200 segundos de simulacion.

##### Delay de los paquetes

Como se vio en el punto anterior la ocupacion de los buffers de todos los nodos se mantiene constante, luego el delay de los paquetes tambien se mantendra constante y se lograra la estabilidad de la red.

#### Conclusion
Se logra una estabilidad de la red, en donde la ocupacion de los buffers de todos los nodos se mantiene constante y por lo tanto el delay de los paquetes se mantiene constante a partir de una distribucion exponencial centrada en 7,5. Con valores inferiores a estos se sigue observando un crecimiento lineal de la ocupacion de los buffers y por lo tanto del delay de los paquetes.

Es importante destacar que si se usa una distribucion exponencial centrada en valores superiores a 7.5 se desaprovecharia la red dado que se enviarian menos paquetes de los que la red puede soportar mientras mantiene su estabilidad.

## Métodos
Se diseño un algoritmo de enrutamiento en donde se asume que tenemos un modelo de red de anillo. El algoritmo realiza las siguientes tareas:

* Cada nodo de la red envia un paquete de tipo Network que es usado para identificar la red, es decir saber cuantos nodos hay en el anillo y a cuanta distancia estan.
* Este paquete pasa de nodo en nodo, siempre enviandose en sentido horario hasta llegar al nodo que lo creo (da una vuelta entera al anillo).
* En cada salto se registra el nombre del nodo por el que paso en una lista propia del paquete.
* Cuando el paquete de tipo Network regresa al nodo emisor, el nodo emisor crea una tabla de enrutamiento para saber por cual enlace enviar un paquete a cada nodo.
* Para armar la tabla de enrutamiento el nodo observa la longitud de la lista de nodos por los que paso el paquete (cantidad de nodos vecinos en el anillo).
* Si tenemos N posibles vecinos en el anillo se decide enviar por el enlace 0 (sentido horario) los paquetes cuyo destino sean los primeros N/2 nodos de la lista, pues seran los mas cercanos usando este enlace.
* Por el enlace 1 (sentido antihorario) se enviaran los paquetes cuyo destino sean los ultimos N/2 nodos de la lista, pues estos seran los mas lejanos en sentido horario por lo tanto los mas cercanos en sentido antihorario.
* En caso de que el numero de nodos vecinos sea impar se enviaran por el enlace 0 los paquetes cuyo destino sean los primeros floor(N/2) nodos de la lista, luego por el enlace 1 se enviaran los paquetes cuyo destino sean los ultimos N - floor(N/2) nodos de la lista.
* Una vez creada la tabla de enrutamiento se comienzan a enrutar los paquetes de datos.
* Previo a enviar cada paquete de datos se observa cual es el nodo destino de cada paquete y se decide por cual enlace enviar cada paquete en base a la tabla de enrutamiento.

## Resultados de la simulación con el algoritmo implementado

### Caso 1
#### Ocupacion de buffers

Es posible notar una gran diferencia respecto al grafico analizado previamente para el mismo caso sin el algoritmo implementado. En este caso la ocupacion de todos los buffers se mantiene constante, en especial el buffer del nodo 0, que en el mismo caso sin el algoritmo crecia linealmente.

Se puede observar que la ocupacion de los buffers de nodos que solo se encargan de reenviar paquetes de datos oscilan entre 0 y 1 al igual que antes de implementar el algoritmo, solo que es importante destacar que con el algoritmo implementado se hace uso de los nodos 3 y 4.

Veamos mas en detalle la ocupacion de los buffers de los nodos que ademas de reenviar paquetes de datos tambien los generan:

##### Buffer del nodo 0

Se puede notar un gran mejoria, pues sin implementar el algoritmo la ocupacion del buffer de este nodo crecia linealmente y con el algoritmo se mantiene constate, esto se debe a que con el algoritmo el nodo 0 no se tiene que encargar de reenviar los paquetes generados por el nodo 2, si no que solo envia lo que el genera dado que los paquetes generados por el nodo 2 se envian por otra ruta.

##### Buffer del nodo 2

Este caso es similar al del nodo 0, como este paquete solo envia los paquetes de datos que genera y no se encarga de reenviar otros paquetes de datos la ocupacion del buffer se mantiene constante y no crece linealmente.

##### Buffers de los nodos 3, 4, 6 y 7

La ocupacion de los buffers de estos nodos oscilan entre 0 y 1 debido a que estos nodos solo se encargan de reenviar los paquetes de datos generados por los nodos 0 y 2, ademas tienen una tasa de transferencia igual a la tasa en la que reciben datos, por lo tanto no se genera congestion en estos nodos.

Es importante notar que no se hace uso del nodo 1, esto se debe al algoritmo de enrutamiento ya que para los paquetes originados en el nodo 0 se elige la ruta: 7-6-5, y para los paquetes originados en el nodo 2 se elige la ruta: 3-4-5.

#### Cantidad de saltos

El algoritmo de enrutamiento se encarga de elegir la ruta mas corta para transmitir cada paquete desde un nodo origen a un nodo destino, como desde el nodo 0 y desde el nodo 2 al nodo 5 solo hay 3 saltos, luego la cantidad de saltos de los paquetes sera constantemente 3.

#### Delay de los paquetes

Como la ocupacion de los buffers se mantiene constante para todos los nodos, luego el delay de los paquetes tambien se mantendra constante.

Podemos destacar que se esta logrando una estabilidad de la red con el algoritmo implementando en este caso que sin el algoritmo no se conseguia.

### Caso 2:

#### Ocupacion de buffers

En este caso la ocupacion de los buffers de todos los nodos crece linealmente a excepcion de los buffers de los nodos 0 y 1. Se puede notar una mejoria respecto al caso en el que no se tenia el algoritmo implementado pues tenemos dos nodos con ocupacion de buffer constante cuando antes teniamos solo uno.

Veamos mas en detalle los nodos que tienen un comportamiento distintos a los demas:

##### Nodo 0

Este nodo solo envia paquetes generados por el mismo, pues por la decision de enrutamiento de los demas nodos ningun paquete pasa por este nodo, por lo tanto el crecimiento de la ocupacion del buffer solo depende de la diferencia entre la tasa de transferencia y la tasa de generacion (ligada a una distribucion exponencial centrada en 1). Es por esto que la ocupacion del buffer de este nodo no crece al mismo ritmo que la ocupacion del buffer de todos los demas nodos.

##### Nodo 1

La ocupacion del buffer de este nodo se comporta igual que en el nodo 0.

#### Cantidad de saltos

La cantidad de saltos posibles para los paquetes es de 1, 2, 3 o 4. Esto dependera de cual sea el nodo origen, por ejemplo la ruta mas larga posible de un paquete desde un nodo origen al nodo destino es de 4 saltos, esto se da cuando se transmite desde el nodo 1 hacia el nodo 5, luego la cantidad de saltos posibles para los paquetes es de 1, 2, 3 o 4.
Se puede observar una mejoria respecto a cuando el algoritmo no estaba implementado, pues antes un paquete podia llegar a tener hasta 7 saltos, lo que significa un mayor delay para llegar a destino.

#### Delay de los paquetes

Es importante notar que como la ocupacion de los buffers de la mayoria de los nodos crece linealmente, luego el delay de los paquetes crecera linealmente por lo ya antes explicado. Esto significa que la red no estara estabilizada.

### Estabilizacion de la red con algoritmo

Considerando la misma definicion de estabilizacion de la red que se dio para el analisis de equilibrio de red sin el algoritmo implementado, se analizan distintos casos para determinar a partir de que valor de InterArrivalTime se consigue la estabilizacion de la red:

#### Exponencial centrada en 3

##### Ocupacion de buffers

Se puede notar que la ocupacion del buffer del nodo 4 crece linealmente, luego no se consigue una estabilidad de la red con este valor.

##### Delay de los paquetes

En el punto anterior se vio que la ocupacion del buffer del nodo 4 crece linealmente luego por consecuente el delay de los paquetes que pasen por el nodo 4 en su ruta crecera linealmente. Es importante entender que los paquetes que no pasen por el nodo 4 en su ruta no tendran ese delay, eso es lo que genera ese cambio brusco en el grafico.

#### Exponencial centrada en 4.5

##### Ocupacion de buffers

Es posible observar como la ocupacion de los buffers de todos los nodos se mantiene constante a traves de los 200 segundos de simulacion.

##### Delay de los paquetes

Como se vio en el punto anterior la ocupacion de los buffers de todos los nodos se mantiene constante, luego el delay de los paquetes tambien se mantendra constante y se lograra la estabilidad de la red.

#### Exponencial centrada en 7.5

##### Ocupacion de buffers

En este caso la ocupacion de los buffers de todos los paquetes se mantendra constante, pero esto trae una desventaja en el siguiente grafico sera mencionada.

##### Delay de los paquetes

Como la ocupacion de los buffers de todos los nodos se mantiene constante luego el delay de los paquetes se mantendra constante y se conseguira el equilibrio de la red, pero esto hara que se desaproveche la capacidad de la red pues se estan enviando menos paquetes de los que la red podria enviar sin dejar de estar equilibrada.

#### Conclusion
Se logra una estabilidad de la red, en donde la ocupacion de los buffers de todos los nodos se mantiene constante y por lo tanto el delay de los paquetes se mantiene constante a partir de una distribucion exponencial centrada en 4,5. Con valores inferiores a estos se sigue observando un crecimiento lineal de la ocupacion de los buffers y por lo tanto del delay de los paquetes.

Es importante destacar que si se usa una distribucion exponencial centrada en valores superiores a 4.5, como por ejemplo 7.5 al igual que antes de implementar el algoritmo, se desaprovecharia la red dado que se enviarian menos paquetes de los que la red puede soportar mientras mantiene su estabilidad.

Finalmente se puede destacar que el algoritmo consigue una estabilizacion de la red con un valor menor de InterArrivalTime, lo que significa que se generaran mas paquetes por segundo y se enviaran mas datos en menos tiempo, aprovechando asi mejor la red.

## Discusión

### Mejoras de diseño

#### Desconexion de enlaces
El algoritmo implementado no aprovecha al maximo el modelo de red de tipo anillo. En el caso de que uno de los enlaces se desconecte o se sature se podria modificar la tabla de enrutamiento para que se envien los paquetes por el enlace en direccion contraria, para esto seria necesario verificar la red periodicamente para saber el estado de los enlaces y de la congestion de los nodos vecinos.

#### Enrutamiento jerarquico
Un posible problema que podria tener el algoritmo implementado es que la tabla de enrutamiento crezca mucho en tamaño, esto se daria en el caso de que haya muchos nodos en la red. Para solucionar este problema se podria implementar un tipo de enrutamiento jerarquico, donde los nodos se agrupan en distintas zonas y la tabla de enrutamiento contiene el enlace por el que enviar a cada zona y no a cada nodo.

#### Permitir otro tipo de redes
El algoritmo implementando solo funciona para redes de tipo anillo, se podria expandir el algoritmo para que funcione en redes con otra topologia, para esto habria que cambiar la forma en que se mide la distancia a cada nodo de la red y por lo tanto la forma en que se arma la tabla de enrutamiento.

### Loops de enrutamiento
En el algoritmo implementado no se producen loops de enrutamiento, esto se debe a que cada nodo siempre elige enviar por el enlace que tenga el camino mas corto para llegar a destino (haciendo uso de su tabla de enrutamiento), lo que produce que nunca se envie un paquete hacia atras porque esto aumentaria el largo del camino hacia el nodo destino.

## Referencias

* [Modelo de anillo (_Wikipedia_)](https://es.wikipedia.org/wiki/Red_en_anillo)
* [Full-duplex (_Wikipedia_)](https://es.wikipedia.org/wiki/D%C3%BAplex_(telecomunicaciones))
* Redes de computadoras: un enfoque descendente (Kurose y Ross).
* Tanenbaum (5 edicion).