std::string apellidos[] = { "Achával", "Maraschio", "Peyronel" };
for (std::string apellido : apellidos)
std::cout << "Tomás " << apellido << std::endl;
Este lab se basa en analizar e implementar algoritmos de enrutamiento de la capa de red.
Primero analizamos el comportamiento de un protocolo de enrutamiento muy simple. Luego, implementamos nuestro propio algoritmo de enrutamiento y vimos qué cambió con respecto a la solución inicial.
- Los nodos de la red tendrán una tasa de envío de 1 Mbps.
- El tamaño de los paquetes de datos será de 125 000 B (1 Mb).
- Con estos valores, un paquete tarda 1s en transmitirse al medio.
- El intervalo de generación de paquetes estándar será de 1 paquete por segundo, pero analizaremos distintos casos.
Red de nodos | Cada nodo, internamente |
---|---|
![]() |
![]() |
Esta es la red sobre la que vamos a estar trabajando: es una red anillo donde cada nodo tiene dos interfaces, una para cada vecino.
El algoritmo usado en esta parte es el que venía dado en el proyecto: cuando llega un paquete a un router se fija si está destinado a él, si no lo está lo manda al vecino de la derecha (interfaz 0). Como se ve, este es un algoritmo muy sencillo y funciona solo para redes anillo.
A continuación analizamos dos casos de uso de la red, y la carga que se genera en la misma.
Como se puede ver en el siguiente video, este caso consiste en que los nodos 0 y 2 generan paquetes para enviar con destino al nodo 5.
En este caso, como se puede observar, todos los nodos generan y mandan paquetes hacia el 5, excepto este último que solo recibe. Lo probaremos con distintos intervalos de generación y tomaremos algunas medidas del uso de la red.
Todos los gráficos de arriba se pueden resumir en el siguiente gráfico de delay medido, donde cada curva corresponde a uno de los intervalos de generación de paquetes analizado.
Algunos conceptos:
- Matriz de costos: es una matriz almacenada en cada nodo que mapea una dirección al costo de llegar a ella a través de sus diferentes vecinos.
- Mejores salidas: es un vector, tambien almacenado en cada nodo, que mapea una dirección destino a la dirección del vecino por el que pasa el camino de menor costo. Estos son elegidos a partir de mínimos por fila en la matriz de costos.
- Vector de distancia: lo creamos a partir de las mejores salidas y la matriz de costos. Tiene pares < destino, costo al destino >.
Explicación del algoritmo implementado: Nosotros hicimos una implementación similar al algoritmo de enrutamiento de vector de distancia⁽¹⁾ que vimos en el teórico, donde cada router recibe los vectores de distancia de sus vecinos, y a partir de estos arma su vector de distancia propio. Para representar los costos de las rutas nosotros decidimos usar como distancia la cantidad de saltos entre nodos. Cada nodo usa como dirección su índice en la red (números del 0 al 7), esto lo hicimos porque necesitamos que cada nodo tenga una dirección única. Notar que no asumimos nada con respecto a la posición de un nodo en base a su dirección, son simplemente identificadores. Cuando empieza la simulación, cada nodo envía paquetes Hello a sus vecinos. En estos paquetes cada nodo pone su dirección. A su vez, cuando recibe un paquete Hello, guarda la interfaz desde dónde llegó y la dirección del vecino que lo envió; también agrega a su vector de distancia que puede llegar a ese vecino con costo 1. Cuando un nodo recibe un vector de distancia de un vecino, actualiza su matriz de costos y se fija si hay cambios en su vector de mejores salidas. En caso de haberlos, manda su vector de distancia actualizado a sus vecinos.
Mismo caso que la parte 1, nodos 2 y 0 generan y envían paquetes a nodo 5.
Como se puede ver en el video, esta vez con nuestro algoritmo en acción, se seleccionan los caminos más cortos y por lo tanto todos los paquetes enviados son recibidos sin demoras extra por esperas en bufers (salvo mínimas por aleatoriedad). No hay mucho para analizar aquí pues ninguna parte de la red se satura (el intervalo de generación aqui es de 1 paquete por segundo).
Volvemos a analizar la carga en buffers para distintos intervalos de generación, esta vez con nuestro algoritmo en acción.
A diferencia de la parte 1, donde todos los paquetes compartían un mismo camino, aquí se forman dos caminos (más cortos) por los cuales pasarán los paquetes. Es por ello que en los gráficos que se encuentran a continuación se puede ver que la estabilidad de la red se logra a partir del intervalo de generación de 1 paquete cada 4 segundos, pues el camino más largo hasta el destino tiene 4 nodos y por lo tanto nunca habrá un "grupo productor" que genere más de 4 paquetes por segundo.
No ponemos los gráficos para más de 5 paquetes por segundo pues son todos de la misma forma debido a que ya se alcanzó la estabilidad.
Algunas observaciones notables de la implementaciones:
- El algoritmo implementado en el kickstart depende de la topología de la red (el hecho de mandar siempre por la interfaz 0 podría generar que nunca se llegue a destino en una red no-anillo). Por otro lado, nuestro algoritmo tiene mecanismos para aprender sobre la topología de la red y los caminos más cortos hacia el resto de los nodos.
- Nuestro algoritmo podría mejorarse para manejar las situaciones en las que algún nodo se cae o se incorpora un nuevo nodo. También estaría bueno que el algortimo decida la mejor ruta teniendo en cuenta la congestión de la red (es decir, que el costo no sea solamente la cantidad de saltos).
Para finalizar, en este video se puede ver nuestro algoritmo funcionando en una red con una topología más compleja.