Date de remise: vendredi 11 juillet 2014, 23:59:59

Routage par la méthode des états de liens

Le but de ce travail est d’implanter une version simplifiée de l’algorithme distribué des états de liens vu en cours. Comme il est plutôt difficile de mettre en oeuvre un inter-réseau privé pour ce genre d’exercice, on utilise un simulateur de réseau. Ce simulateur permet le déploiement d’un réseau arbitrairement complexe impliquant des noeuds indépendants et concurrents, ainsi que des liens de fiabilité déterminée. Votre travail consiste à implanter l’algorithme du point de vue d’une fonction nommée run() exécutée sur chaque noeud, indépendamment. Cette fonction doit exécuter une boucle de réception de messages et de réactions aux événements, de manière à accumuler progressivement les états de liens des autres noeuds du réseau et de créer sa table de routage.

Utilisation du simulateur

Le simulateur est mis en oeuvre à l’aide de la classe NetworkSimulator mise en oeuvre par le module sim.py. Le programme suivant présente son utilisation:

from sim import NetworkSimulator
import time

nsim = NetworkSimulator()

# On ajoute d'abord des noeuds. Chaque noeud doit être muni d'un nom
# unique qui lui fait office d'adresse sur le réseau.
#
# Ici, on ajoute cinq noeuds, nommés A, B, C, D et E.
nsim.add("A", "B", "C", "D", "E")

# On connecte ensuite les noeuds devant être voisins. Chaque lien ainsi
# créé est muni d'un coût et d'une fiabilité (point flottant). Le coût est
# utilisé tel quel par le routage; la fiabilité note la probabilité qu'un
# message envoyé sur ce lien soit perdu (donc ne soit pas reçu par le
# destinataire). La fiabilité par défaut est 1.0.
#
# À chaque connexion, les noeuds concernés reçoivent un message spécial de
# l'émetteur 0. N'utilisez pas 0 comme nom de noeud! Les noeuds ne peuvent
# envoyer et recevoir de messages que de 0 et de leurs voisins immédiats.
# Les messages devant voyager vers des récepteurs qui ne sont pas
# connectés directement doivent être relayés explicitement.
nsim.link("A", "C", 1.0)
nsim.link("B", "C", 2.0, 0.95)  # 1 message sur 20 est perdu.
nsim.link("D", "A", 3.0)
nsim.link("A", "E", 1.0, 0.8)   # 1 message sur 5 est perdu.
nsim.link("D", "E", 1.0)

# À ce point du programme, les noeuds sont en marche, ils reçoivent des
# messages sur l'apparition de leurs nouveaux voisins et peuvent réagir
# en leur envoyant des messages à leur tour, mettant en route l'algorithme
# de routage (inondation fiable, construction de la table de routage). Il
# faut quelques secondes au réseau pour s'inonder; on peut attendre avec
time.sleep(10.0)  # 10 secondes.

# Consulter la carte de routage. Il s'agit d'un dictionnaire associant
# chaque noeud (par son nom) à la dernière table de routage qu'il a
# enregistrée (liste de routes).
map_routing = nsim.get_routing_tables()

# On peut changer la topologie du réseau à tout moment!
nsim.link("B", "C", 3.0, 0.95)  # Nouveau coût: les noeuds en sont informés.
nsim.link("D", "E", 1.0, 0.7)   # Nouvelle fiabilité: les noeuds n'en sont
                                # PAS informés.
nsim.link("A", "E", 1.0, 0.0)   # Fiabilité 0 => tous les messages sont perdus.
                                # Correspond à toute fin pratique à une déconnexion.
nsim.add("F")                   # Nouveau noeud, ok.
nsim.link("B", "F", 2.0)
nsim.remove("D")                # Le retrait d'un noeud coupe les liens
                                # avec les voisins et retire le noeud de
                                # la carte de routage. Les voisins ne
                                # reçoivent PAS de message explicite de
                                # cette disparition.

# Quand on a fini de s'amuser, on met fin à la simulation. À partir d'ici,
# on ne peut plus rien faire avec le simulateur: plus de changement de
# topologie ni de consultation de la carte de routage.
nsim.stop()

Le simulateur met en oeuvre une transmission probabiliste de chaque message. En plus de décider au hasard si un message envoyé à un autre sera perdu (c’est-à-dire, ne sera pas transmis par le simulateur à son destinataire), le temps de transmission de chaque message est distribué selon une loi de probabilité exponentielle, de moyenne 1.0 seconde (indépendant du coût donné au lien). C’est ce qui justifie le temps réel pris par les messages pour sauter d’un émetteur à son destinataire. Tenez compte de la longueur des chemins dans votre réseau pour vous donner une idée du temps maximum vraisemblablement nécessaire pour réaliser l’inondation fiable.

Le programme exécuté sur chaque noeud

Votre travail est d’implanter la fonction run() dans le module user.py, qui doit être placé dans le même répertoire que le module sim.py. Cette fonction est exécutée par chacun des noeuds pour qu’il réalise son travail d’inondation fiable et de construction d’une table de routage. Voici un point de départ pour ce noeud:

def run(ui):
    while True:
        origin, msg = ui.recv()
        # Analyse de qui envoie le message, et de sa nature...

Le lien entre chaque noeud est mis en oeuvre par l’objet ui: il s’agit de l’interface d’accès aux services permis par le simulateur. Voici les membres et méthodes publics de cet objet:

`ui.name`

Le nom du noeud, qui lui fait office d’adresse dans le réseau.

`ui.send(dest, msg)`

Envoie un message au noeud à l’adresse dest. Le message peut être n’importe quel objet, qui sera relayé tel quel au destinataire (s’il n’est pas perdu). Il n’est pas nécessaire de sérialiser ou d’encoder le message, ce peut vraiment être n’importe quel objet Python.

Si le noeud émetteur n’est pas directement connecté (voisin) de l’émetteur du message, le message est perdu. Le message est aussi susceptible d’être perdu au gré de la fiabilité du lien.

`origin, msg = ui.recv(timeout)`

Permet la réception du prochain message dans la file de communication du noeud. La valeur de sortie origin dénote l’adresse du noeud ayant envoyé le message; msg est l’objet originalement soumis à la méthode send().

Cette méthode est utile pour attendre la gestion d’un événement muni d’un délai d’attente (timeout). Par exemple, soyons à vouloir envoyer un message de rappel qu’on est vivant à tous les voisins à toutes les secondes. Ayant importé le module time, on définit le moment du prochain tel message:

moment_hello = time.time() + 1.0

Quand on est prêt, on invoque

origin, msg = ui.recv(moment_hello - time.time())

Ainsi, si on reçoit un message avant que le délai d’attente soit passé, on peut le traiter, avant de reprendre l’attente. Sinon, la méthode recv rend le contrôle au bout du délai d’attente, avec origin fixé à None. Si timeout est None (valeur par défaut), le noeud attend indéfiniment la réception d’un message.

En fin de compte, on peut recevoir des messages des noeuds voisins, en plus de deux émetteurs spéciaux:

0: informe le noeud qu’il a été connecté à un nouveau voisin (msg.peer) et que le coût de ce lien est msg.cost. C’est le seul mécanisme par lequel un noeud peut connaître ses voisins. Il revient au noeud de stocker cette information.
None: aucun message n’a été reçu; plutôt, le délai d’attente donné est écoulé.

`r = ui.make_route(dest, cost, next_hop)`

Instancie un objet de type Route, qu’on doit utiliser pour populer la liste soumise comme table de routage du noeud.

`ui.set_routing_table(list_routes)`

Soumet au simulateur la table de routage la plus récemment composée par le noeud. Cette table doit consister en une liste de routes, lesquelles sont des objets instanciés par la méthode make_route.

Suggestions, simplifications et trucs

En vrac, voici diverses notes visant à faciliter et simplifier votre travail.

Le simulateur n’offre aucun service permettant d’indiquer la panne d’un lien. Veillez à échanger des messages du genre "hello" pour vous assurer qu’un lien fonctionne toujours. Ces messages devraient être envoyés à toutes les secondes.
Ayant égard à la distribution de probabilité du temps de transfert des messages, plus de 99% des messages sont transmis en 5.0 secondes ou moins. On peut donc considérer qu’un lien est en panne si on n’a pas reçu de "hello" de ce voisin depuis 5.0 secondes.
Le RTT moyen d’un tel lien est de 2.0 secondes. Ainsi, dans la mise en oeuvre de l’algorithme d’envoi-et-attente menant à l’inondation fiable, on peut se donner un délai d’attente de 4.0 secondes.
On laisse tomber le TTL des LSPs. Une information topologique demeure dans chaque noeud jusqu’à ce qu’elle soit explicitement remplacée.
Assurez-vous que votre mise en oeuvre supporte les réseaux qui ne sont pas complètement connectés, c’est-à-dire des réseaux dont certains sous-groupes de noeuds ne sont pas connectés aux autres. Par exemple:
```
  nsim.add("A", "B", "C", "D", "E")
  nsim.link("A", "B", 1.0)
  nsim.link("A", "C", 1.0)
  nsim.link("B", "C", 1.0)
  nsim.link("D", "E", 1.0)
```
Les noeuds A, B et C sont connectés entre eux, ainsi que D et E, mais il n’y a pas de lien entre ces deux composantes. Les tables de routage de A, B et C auront des routes pour ces noeuds seulement, alors que celles de D et de E auront des routes vers seulement E et D, respectivement.

Instructions pour la remise

Le travail est exécuté par équipes de deux.
Le travail doit être remis par courriel à l’une de ces deux adresses: benoit@benoithamelin.com, benoit.hamelin@usherbrooke.ca.
- Le sujet du courriel: IFT585 TP3
- Le corps du courriel doit contenir le nom des deux coéquipiers.
- Un fichier nommé user.py doit être inclus en pièce jointe.

Évaluation

Le travail est évalué sur 20 points:
- Conformité aux instructions de remise: 1 point
- Propreté de la sortie des programmes (pas d’énoncé de déboguage): 1 point
- Satisfaction des consignes de développement: 3 points
  - Pas d’usage des méthodes ou membres privés de l’instance de ui.
  - Pas d’interception de l’exception _Stopped.
  - Pas de variable globale partagée entre les threads simulant chacun des noeuds indépendants (toute information devant être partagée l’est par transmission de messages).
- Construction des tables de routage pour des configurations de réseau simples et des mutations de base: 10 points.
- Construction des tables de routage pour des configurations de réseau et des mutations plus compliquées: 5 points.
La conformité du code aux exigences sera testée par la construction d’un réseau dans le simulateur, suivie d’un temps adéquat à la propagation des informations de routage. On examine ensuite les tables de routage construites en chaque noeud par le truchement de la fonction run() du module user que vous fournissez. Certains de ces scénarios de simulation suivent la stabilisation initiale des tables de routage avec des mutations du réseau. On attend à nouveau la stabilisation avant de consulter les nouvelles tables de routage. Ce cycle peut être réalisé plus d’une fois.
Mettre en oeuvre des tests adéquats en regard de la spécification fait partie de votre travail. Ces tests ne sont ni évalués ni remis, mais ils vous permettent de vérifier que votre code fonctionne.
Les qualités intrinsèques du code ne sont pas évaluées. On s’attend à ce que la difficulté du problème cause des problèmes de maintenance intractables (ou, à tout le moins, douloureux) pour des programmes conçus avec négligence ou sans égard à la lisibilité.