Ceci est une version archivée de NetGraph à 2006-05-30 16:41:45.

Date de rendu : vendredi midi, lire plus bas

Préliminaires

Le réseau Internet peut être grossièrement assimilé à un graphe, dont les noeuds sont les hôtes (machines, routeurs...) et les arêtes les liens entre ces hôtes. Depuis un noeud A donné, il est très difficile d'avoir une vue d'ensemble du réseau ; cependant, on peut effectuer un « traceroute » vers un autre noeud B, et dans la plupart des cas, obtenir une liste de noeuds formant un chemin entre A et B :
jpetazzo@kapouer:~$ traceroute www.jussieu.fr traceroute to idf.ext.jussieu.fr (134.157.81.129), 30 hops max, 38 byte packets 1 rumlv.univ-mlv.fr (193.50.159.1) 7.216 ms 5.828 ms 5.485 ms 2 195.220.83.5 (195.220.83.5) 6.229 ms 3.852 ms 1.239 ms 3 marne-g3-3.cssi.renater.fr (193.51.183.118) 1.110 ms 1.975 ms 1.239 ms 4 creteil-g0-2.cssi.renater.fr (193.51.180.133) 2.359 ms 2.262 ms 1.829 ms 5 jussieu-g0-3.cssi.renater.fr (193.51.180.153) 2.609 ms 2.726 ms 5.113 ms 6 gw-rap.rap.prd.fr (193.50.20.73) 5.857 ms 5.845 ms 5.986 ms 7 jussieu-rap.rap.prd.fr (195.221.127.182) 6.857 ms 7.474 ms 8.610 ms 8 r-intercon.reseau.jussieu.fr (134.157.254.123) 13.852 ms 7.589 ms 9.229 ms 9 idf.ext.jussieu.fr (134.157.81.129) 3.111 ms 2.973 ms 5.487 ms jpetazzo@kapouer:~$
On obtient une liste de routeurs situés entre la machine "kapouer" et la machine "www.jussieu.fr" ; à chaque fois il y a un numéro, un nom (le nom n'est pas toujours disponible, cf. ligne 2), une adresse IP, et des temps de réponse. On pourra totalement ignorer ces temps de réponse par la suite.

Sur Internet, une machine (ou un routeur, c'est pareil!) peut avoir 1 ou plusieurs adresses IP, et chaque adresse IP peut avoir 0, 1 ou plusieurs noms DNS rattachés. Inversement, un nom DNS peut être rattaché à 0, 1 ou plusieurs adresses IP. Comme les relations entre les adresses IP et les noms DNS sont complexes, on ignorera complètement les noms DNS dans un premier temps, pour ne se focaliser que sur les adresses IP. D'autre part, même si une machine peut avoir plusieurs adresses IP, on n'essaiera pas de « deviner » si plusieurs adresses appartiennent à la même machine ou pas. On raisonnera donc, finalement, en adresses IP plutôt qu'en machines ou routeurs ou noms DNS.

Il existe une option de la commande traceroute qui permet de désactiver la résolution DNS (la conversion des adresses IP en noms) ; n'hésitez pas à l'utiliser, la commande s'exécutera plus rapidement.

Pour convertir un nom DNS en adresse IP ou inversement, on peut utiliser la commande host, par exemple.

Parfois, traceroute donne des résultats bizarres :
jpetazzo@kapouer:~$ traceroute www.enix.fr traceroute to the-book.enix.fr (193.19.211.129), 30 hops max, 38 byte packets 1 rumlv.univ-mlv.fr (193.50.159.1) 5.136 ms 5.454 ms 5.596 ms 2 195.220.83.5 (195.220.83.5) 5.607 ms 8.224 ms 6.608 ms 3 marne-g3-3.cssi.renater.fr (193.51.183.118) 8.356 ms 5.972 ms 5.612 ms 4 creteil-g0-2.cssi.renater.fr (193.51.180.133) 7.358 ms 7.472 ms 7.986 ms 5 jussieu-g0-3.cssi.renater.fr (193.51.180.153) 10.356 ms 8.845 ms 8.609 ms 6 nri-c-pos2-0.cssi.renater.fr (193.51.180.158) 6.982 ms 7.843 ms 7.486 ms 7 ftld-nri-c.cssi.renater.fr (193.51.185.1) 8.481 ms 9.971 ms 8.485 ms 8 gi0-0.pascr1.Paris.opentransit.net (193.251.243.122) 8.108 ms 7.598 ms 7.236 ms 9 level3-2.GW.opentransit.net (193.251.240.214) 7.608 ms 7.975 ms 12.357 ms 10 so-6-0-0.mp2.Paris1?.Level3?.net (4.68.124.117) 8.480 ms 8.472 ms 8.360 ms 11 ge-11-2.ipcolo2.Paris1?.Level3?.net (212.73.240.118) 8.607 ms ge-11-0.ipcolo2.Paris1?.Level3?.net (212.73.240.40) 8.599 ms ge-11-1.ipcolo2.Paris1?.Level3?.net (212.73.240.84) 11.093 ms 12 212.73.242.2 (212.73.242.2) 7.969 ms 9.100 ms 8.859 ms 13 ge-1-1-0.cr1.itx.fr.bsocom.net (83.243.16.26) 8.482 ms 9.223 ms 9.358 ms 14 castor.enix.org (83.243.23.102) 9.357 ms 10.597 ms 8.233 ms 15 the-book.enix.org (193.19.211.129) 8.982 ms 8.098 ms 9.734 ms
Ici, sur la ligne 11 on a plusieurs adresses IP. En effet, traceroute fait 3 essais pour chaque « distance », et ici les 3 essais ont donné 3 résultats différents - il les indique donc tous les 3. Dans ce cas, le mieux est de considérer que les 3 résultats sont valides ; mais on peut aussi ne considérer que le premier pour des raisons de simplicité.

Autre exemple « étrange » :
jpetazzo@skalinka:~$ traceroute www.enix.fr traceroute to the-book.enix.fr (193.19.211.129), 30 hops max, 38 byte packets 1 192.168.9.41 (192.168.9.41) 4.064 ms 1.149 ms 1.537 ms 2 82.236.3.254 (82.236.3.254) 40.054 ms 39.327 ms 39.086 ms 3 * * * 4 * * * 5 * * * 6 cbv-6k-2-v828.intf.routers.proxad.net (212.27.51.97) 68.584 ms 46.877 ms 47.791 ms 7 ldc-6k-1-a0.routers.proxad.net (213.228.15.67) 40.230 ms 40.839 ms 39.473 ms 8 bsocom.FreeIX?.net (213.228.3.168) 51.084 ms 39.741 ms 40.147 ms 9 ge-4-1-0.cr2.cap.fr.bsocom.net (83.243.16.49) 39.902 ms 48.228 ms 39.530 ms 10 ge-1-1-0.cr1.itx.fr.bsocom.net (83.243.16.26) 39.901 ms 49.912 ms 39.843 ms 11 castor.enix.org (83.243.23.102) 73.762 ms 40.542 ms 39.883 ms 12 the-book.enix.org (193.19.211.129) 40.968 ms 41.392 ms 41.431 ms
Les étoiles correspondent à une absence de réponse. Ce n'est pas une erreur. En ce cas, cela signifie qu'on n'a pas d'information sur les machines correspondantes ; on ne sait pas ce qu'il y a entre 82.236.3.254 et 212.27.51.97 ; tout au plus peut-on dire qu'il y a probablement 3 autres machines (et encore, ce n'est pas sûr!)

Attention, le graphe d'Internet n'est pas forcément un graphe « idéal », et les chemins que vous verrez apparaître en faisant des « traceroute » ne seront pas forcément les meilleurs ou les plus courts. Ne vous étonnez pas si par exemple, sur un traceroute, vous voyez des chemins non-optimaux !

D'autre part, ce n'est pas non plus un graphe figé ni déterministe, donc d'un jour à l'autre (ou même d'une minute à l'autre) un même traceroute pourra donner des résultats différents.

But du projet

Il s'agit d'écrire un programme (ou un ensemble de programmes) permettant d'effectuer des traceroute automatiquement, en tâche de fond ; et pendant que se font ces traceroute, de rassembler des informations sur le graphe d'Internet. En particulier, pour chaque noeud du graphe (on assimilera un noeud à son adresse IP), on souhaite pouvoir connaître ses voisins, ainsi que sa distance minimale à l' « origine » (la distance n'est pas forcément constante, par exemple entre le noeud A et le noeud B, le noeud X peut apparaître en 5è position ; et le même noeud X peut apparaître en 8è position entre le noeud A et le noeud C -- c'est surprenant, mais c'est possible!).

Il est indispensable de pouvoir :

avoir plusieurs traceroute s'effectuant simultanément, afin de rassembler des informations le plus vite possible ;
pouvoir choisir à la volée combien de traceroute on souhaite exécuter en parallèle) ;
ajouter de nouvelles « cibles » pour traceroute pendant que l'ensemble fonctionne ;
ajouter des cibles « aléatoires » (en tirant des adresses IP au hasard) ;
visualiser des statistiques indiquant le nombre d'adresses IP « explorées » (nombre total, et classement par distance par rapport à l'origine) ;
indiquer les « voisins » d'un noeud donné par son adresse IP ;
exporter (et importer) l'état du graphe, sous forme de deux fichiers CSV : un contenant la liste des sommets (adresses IP) avec leur distance minimale à la source, et un autre contenant une liste de couples d'adresses IP ;
fournir un rapport expliquant les structures algorithmiques utilisées, avec une indication de leurs limites (mémoire, CPU, occupation disque...) -- c'est-à-dire une étude de la complexité des algorithmes utilisés ;
présenter un code propre et lisible, autant que faire ce peu.

Optionnellement, vous pourrez développer :

un contrôle du nombre de traceroute effectués par minute ( de 1 à ... autant que possible!) le but étant d'empêcher l'ensemble de consommer trop de ressources ;
une interface plus ou moins graphique permettant de se promener dans le graphe de manière interactive ;
un système de gestion DNS basique, permettant d'indiquer sur la ligne de commande des noms DNS à la place des adresses IP ;
un système de gestion DNS plus élaboré, permettant de rechercher, par exemple, toutes les adresses IP dont le nom DNS se termine par .fr, ou contient univ- ;
la possibilité d' « injecter » dans le programme des résultats de traceroute effectués depuis d'autres machines (on ignorera alors l'information de distance à l'origine) ;
la possibilité d' « injecter » dans le programme un export des données (fait éventuellement à partir d'un autre programme) sans écraser les données présentes.

Notation

Chaque ensemble suivant compte environ 5 points :

exécution parallèle des traceroute et contrôle du nombre de processus traceroute ; ajout de nouvelles cibles (spécifiées ou aléatoires)
statistiques sur le graphe et exploration du graphe ; import/export des données
rapport + qualité du code

Pour les options :

contrôle de l'utilisation des ressources de la machine : 2 à 5 points
interface graphique : 2 à 5 points
DNS : 2 à 5 points
injection d'autres données : 2 à 5 points

Ensuite, si vous faites le projet seul, votre note est divisée par 15 ; à deux, divisée par 20 ; à trois, divisée par 25 ; à quatre, divisée 30. La note finale est multipliée par 20.
Concrètement, si vous avez 12 points et que vous avez fait le projet seul, cela vous fait 12/15*20 = 16 ; si vous avez 22 en faisant le projet à 4, vous vous retrouvez avec 22/30*20 = 14,5 chacun.

Rendu

Pour le 10 avril : proposer un pré-rapport (sans code) expliquant les structures et algorithmes utilisés (format : PostScript, une page au plus, schémas et annexes inclus ; vous avez le droit d'écrire petit si vous pensez avoir vraiment beaucoup de choses à expliquer).
Rendu final : à déterminer (environ la date du dernier TD de système + 2 semaines).

Le rendu final se fait par l'envoi d'une archive "login1_login2_login3.tar.gz" à allali@univ-mlv.fr.
N'envoyer qu'une seule archive par groupe.
L'archive devra contenir :
- un répertoire "src": avec les sources du projet
- un répertoire "doc": avec la doc du projet
- un fichier "README": indiquant comment compiler le projet ainsi qu'une description des programmes
- un fichier "EXAMPLE": donnant un exemple d'utilisation du projet

L'archive devra arriver dans la boite mail (cachet du serveur faisant foi) avant le Vendredi 2 Juin 12h00 heure locale de l'UMLV (GMT+2)

IMPORTANT : reconsultez ces instructions mercredi midi, elles auront probablement changé (la date limite restera vendredi midi, mais les modalités de rendu seront probablement différentes, sauf incident technique!)

Informations techniques

Une adresse IP = 4 octets. Généralement on la représente sous la forme 134.157.0.129 (sous forme de 4 nombres entiers, en décimal, séparés par des points).
Les plages d'adresses suivantes sont « privées », c'est-à-dire internes :

10.0.0.0 à 10.255.255.255
172.16.0.0 à 172.31.255.255
192.168.0.0 à 192.168.255.255

La plage 224.0.0.0 à 239.255.255.255 est réservée au multicast.
Les adresses de 240.0.0.0 à 255.255.255.255 sont réservées.
Toutes ces plages (adresses privées, multicast, réservées) doivent être traitées de manière spéciale ; il est parfaitement acceptable de ne pas les stocker dans le graphe (de les considérer comme les « * » qui apparaissent parfois dans traceroute).

Le format CSV à utiliser, pour la liste des noeuds : adresse IP, distance1.2.3.4,17 134.157.0.129,8 193.55.63.92,2
Le format CSV à utiliser, pour la liste des arêtes : adresse IP1, adresse IP21.2.3.4,1.2.3.5 134.157.0.129,134.157.254.1 193.55.63.1,193.55.63.29
On utilisera \n comme séparateur de lignes.