La tarea de esta semana constitió en:
- Investigar sobre los métodos de ruteo en el simulador NS-2 o NS-3, y cómo habilitarlos y/o cambiarlos para una simulación.
- Crear un generador de topologías.
Para las simulaciones utilizaré NS-2 ya que, aunque ya es antiguo considero que tiene mejor documentación y sirve muy bien para las actividades requeridas.
Para su instalación y configuración pueden seguir la guía que escribí en la entrada anterior:
Métodos de ruteo
En NS-2 es posible activar 3 métodos diferentes de ruteo, cada uno con sus tipos más específicos, los métodos son:
- Unicast: Se utiliza cuando la información (paquetes) viajan desde un solo emisor a un solo receptor. Es decir, de nodo a nodo.
- Multicast: Se utiliza cuando la información (paquetes) viajan desde un emisor a varios destinatarios. De un nodo a una lista específica de nodos.
- Adhoc: Se utiliza en las transmisiones inalámbricas, donde no existe un nodo central sino que todos están listos para enviar y recibir información.
Unicast:
Es el método de ruteo por default en NS-2 y por lo general no es necesario especificarlo, sin embargo, se pueden activar diferentes protocolos y algoritmos que entran en ésta clasificación:
- Static: Es la estrategia de ruteo por default, y utiliza el algoritmo de Dijkstra para el calculo de las rutas, el cual corre una vez justo después del inicio de la simulación
- Session: Se utiliza para realizar cambios en el ruteo de los nodos de la topología, lo que permite redes dinámicas. Sin embargo, no es muy realista ya que no hay interrupciones transitorias como en el caso del ruteo estático.
- DV: Implementación del algoritmo Bellman-Ford para hallar las mejores rutas entre los nodo. Las rutas se actualizan periódicamente según un intervalo de tiempo establecido.
- Cost: Establece costos a cada una de las conexiones entre los nodos, los costos pueden ser diferentes en cada dirección.
- Multi-path
Para activar cualquiera de los protocolos o algoritmos de ruteo unicast se debe hacer una llamada al procedimiento rtproto y después especificar el tipo de ruteo a aplicar, por ejemplo:
$ns rtproto Static; $ns rtproto Session; $ns rtproto DV $n1 $n2 $n3;
Multicast:
- CtrMcast: Similar al PIM-SM (Protocol Independent Multicast Sparse Mode), es un protocolo para ruteo eficiente a grupos de multicast, construye un esquema tipo árbol de cada emisor a receptor en el grupo de multicast.
- DM: Similar al PIM-DM (Protocol Independent Multicast Sparse Mode), es un protocolo adecuado donde muchos nodos se suscriben para recibir paquetes multicast
- ST: Shared Tree Model
- BST: Bi-directional Shared Tree Model
Para activar cualquiera de los protocolos de ruteo basados en multicast se deben hacer llamadas a 2 procedimientos multicast y mrtproto:
$ns multicast (justo despues de set $ns [new Scheduler]) $ns mrtproto BST $ns mrtproto ST $ns mrtproto CtrMcast
Adhoc:
Los protocolos adhoc se utilizan en redes inálambricas, y solo es posible utilizarlo y el nodo se configura especifícamente para ser nodo inalámbrico (que en NS-2 se conoce como nodo móvil [mobile node]). Para configurar un nodo de forma inalámbrica, se deben de tomar en cuenta las siguientes opciones y elegir de los parámetros los que apliquen en nuestro modelo:
| Opciones | Parametros | Notas |
|---|---|---|
| addressType | flat, hierarchichal | |
| MPLS | ON,OFF | Multi protocol Label Switching |
| wiredRouting | ON, OFF | |
| llType | LL, LL/Sat | Link Layer |
| macType | Mac/802_11, Mac/Csma/Ca, Mac/Sat, Mac/Sat/UnslottedAloha, Mac/Tdma | Medium Access Control |
| ifqType | Queue/DropTail, Queue/DropTail/PriQueue | Interface Queue type |
| phyType | Phy/wirelessPhy, Phy/Sat | Physical Layer Type |
| adhocRouting | DIFFUSION/RATE, DIFFUSION/PROB, DSDV, DSR, FLOODING, OMNIMCAST,AODV,TORA,PUMA | adhoc routing protocol |
| propType | Propagation/TwoRayGround, Propagation/Shadowing | Propagation Type |
| antType | Antenna/OmniAntenna, | Antenna type |
| Channel | Channel/WirelessChannel, Channel/Sat | Channel to be used |
| mobileIP | ON,OFF | to set the IP for Mobile or not |
| energyModel | EnergyModel | energy model to be enabled or not |
| initialEnergy | <joule> | in terms of joules (Ex: 3.24) |
| txPower | Power in terms of Watts (0.32) | |
| rxPower | Power in terms of Watts (0.1) | |
| idlePower | Power in terms of Watts (0.02) | |
| agentTrace | ON, OFF | Tracing to be on or off |
| routerTrace | ON, OFF | Tracing to be on or off |
| macTrace | ON, OFF | Tracing to be on or off |
| movementTrace | ON, OFF | Tracing to be on or off |
| errProc | UniformErrorProc | |
| toraDebug | ON, OFF |
En la opción adhocRouting se pueden elegir los diferentes modos de ruteo.
Un ejemplo de configuración de un nodo inalámbrico con protocolo de enrutamiento adhoc sería:
$ns node-config -addressType hierarchical \ -adhocRouting AODV \ -llType LL \ -macType Mac/802_11 \ -ifqType Queue/DropTail/PriQueue \ -ifqLen 50 \ -antType Antenna/OmniAntenna \ -propType Propagation/TwoRayGround \ -phyType Phy/WirelessPhy \ -topologyInstance \$topo \ -channel Channel/WirelessChannel \ -agentTrace ON \ -routerTrace ON \ -macTrace OFF \ -movementTrace OFF
Manual:
Si se decide por un método de ruteo manual, se tendrán que escribir las tablas de ruteo una por una, las cuales no son más que un conjunto de reglas que especifican hacia donde viajan los paquetes, cuál nodo es el inicial, cuál nodo es el destino, etcétera. Un ejemplo con 2 nodos:
$ns rtproto Manual set n1 [$ns node] set n2 [$ns node] $ns duplex-link $n1 $n2 10Mb 100ms DropTail [$n1 get-module "Manual"] add-route-to-adj-node -default $n2 [$n1 get-module "Manual"] add-route-to-adj-node $n2 [$n2 get-module "Manual"] add-route-to-adj-node -default $n1
Por default, en la mayoría de los protocolos de ruteo el algoritmo utilizado para hallar los caminos entre los nodos es el algoritmo de Dijkstra.
También se pueden realizar tareas más avanzadas como modificar la tabla de ruteo en cada nodo, o escribir nuestro propio algoritmo de ruteo.
Errores de red
Un concepto adicional y que aporta más realismo a una simulación es la programación de errores en la red. La forma más simple es insertar un error para la pérdida de paquetes en una conexión entre dos nodos. La manera de hacerlo es la siguiente:
set loss_module [new ErrorModel] $loss_module set rate_ 0.01 $loss_module unit pkt $loss_module ranvar [new RandomVariable/Uniform] $loss_module drop-target [new Agent/Null] $ns lossmodel $loss_module $n0 $n1
Generación de topologías
Para la generación de topologías, me centré solamente en un los tipos de ruteo unicast y multicast. El script para la generación de topologías es escalable, por lo que no sería complejo implementar otros métodos de ruteo, como el adhoc, exceptuando el manual el cual tendría que aplicarse editando directamente el archivo *.tcl que da como salida el script
El lenguaje que utilicé para la generación de topologías fue Python, y mediante este script genero un archivo *.tcl.
Primeramente, el script recibe como entrada un archivo separado por comas donde viene especificada la configuración de la red, el archivo tiene el siguiente formato:
El lenguaje que utilicé para la generación de topologías fue Python, y mediante este script genero un archivo *.tcl.
Primeramente, el script recibe como entrada un archivo separado por comas donde viene especificada la configuración de la red, el archivo tiene el siguiente formato:
sim,3.0,unicast,DV red,r1,30,5,50,duplex-link,null,m;1.0 subred,s1,10,1,75,duplex-link,udp,e subred,s2,10,1,80,duplex-link,tcp,e subred,s3,10,1,50,duplex-link,udp,a
El primer elemento es una etiqueta, ahora solo se soportan 3 etiquetas, cada una con un formato especifico, en este orden deben escribirse en el archivo:
- sim: Refiere a los parámetros generales de la simulación en orden, los parámetros especificados en esta linea son tiempo de la simulación, tipo de ruteo, subtipo de ruteo.
- red: Aquí se especifican los parámetros de la red a crear, en orden, los parámetros especificados son: un id para identificar el objeto, el numero de nodos de toda la red, ancho de banda, latencia, tipo de conexiones, tipo de trafico, tipo de topología, parámetros específicos de la topología.
- subred: Una vez que se ha creado la red, la red se divide en subredes. Los parámetros son los mismos que para toda la red. Se tiene que ajustar manualmente el número de nodos de cada subred y al final la suma debe coincidir con la cantidad de nodos de toda la red.
Las topologías soportadas son 3 (las más comunes):
- Estrella: Un nodo central y todos los demás nodos conectados a él.
- Anillo: Un nodo central, conectados en forma de lista enlazada, el último nodo se conecta con el primero.
- Malla: Conecta todos los nodos entre sí, pero recibe un parámetro adicional que es un valor entre 0.0 y 1.0, este parámetro es la probabilidad de conexión lo que permite crear topologías con forma de grafo. Se crea una matriz de adyacencia para crear las conexiones pero aun falta ajustar un poco pues pueden salir nodos huerfanos.
Para el caso de las redes con forma de grafo, no es necesario especificar la etiqueta subred, solo en la etiqueta red especifican la cantidad de nodos y el script arma la red completamente.
Los tipos de ruteo soportados son los que entran en la clasificación de unicast y multicast.
El tráfico soportado por el script es de dos tipos:
- TCP: De tipo FTP
- UDP: De tipo CBR
El tráfico se genera de manera automática también, pero es diferente para cada subred. Se toman los nodos de una subred y se configuran para ser generadores de tráfico y receptores a la vez.
Sin embargo, el script decide cuales de las posibles conexiones estará activa.
Los tipos de conexión soportados son:
- Simplex-link
- Duplex-link
Evaluando las posibilidades, pienso que se pueden simular una buena cantidad de redes con estas características ya que, por si sola, la topología de malla puede tomar muchas formas y soportar una gran cantidad de nodos.
Capturas de ejemplo:
Ejemplo de 2 estrellas y 2 anillos, conectados por una malla
Ejemplo de una red con forma de grafo
Videos
El primer video es básico, una topología de grafo simple con un método de ruteo Unicast tipo Session.
El segundo video es un poco más complejo, 4 topologías, 2 estrellas y 2 anillos conectadas por una malla, utilizando ruteo Unicast tipo DV.
Se puede ver en los primeros segundos como la red envía mensajes broadcast a todos los nodos para calcular las tablas de ruteo.
Hay ciertos segundos donde lo vuelve a hacer pero por la calidad del video no se alcanzan a apreciar claramente.
Código
Implementar la lógica del programa fue todo un desafío, sobre todo tomando en cuenta que el script debe aceptar redes escalables, conectar los nodos, asignar los agentes correctamente y que el trafico se genere y termine donde debe ser, sin embargo, pienso que el resultado final fue muy bueno.
Aún faltan detalles por afinar y cosas que implementar, acepto recomendaciones.
Referencias:Aún faltan detalles por afinar y cosas que implementar, acepto recomendaciones.
- http://nile.wpi.edu/NS/components.html
- http://www.cs.virginia.edu/~cs757/slidespdf/cs757-ns2-tutorial1.pdf
- http://www.mathcs.emory.edu/~cheung/Courses/558/Syllabus/
- http://www.nsnam.com/2012/09/wireless-node-configuration-in-network.html
- http://www.isi.edu/nsnam/ns/ns-tutorial/wireless.ppt
- http://webstaff.itn.liu.se/~vanan11/TNK092/2011/Lecture_4_DRAFT.pdf
- http://www.tti.unipa.it/~ilenia/course/ns_2.pdf
- http://www-sop.inria.fr/members/Eitan.Altman/COURS-NS/n3.pdf
Investiga protocolos de ruteo tipo DSR que en sí toman decisiones sobre las rutas de los paquetes. Para lo de topologías se podría hacer cosas más "realistas" (investiga sobre small-world networks y scale-free networks – las mencioné en adaptativos). 6 pts.
ResponderEliminar