Rumour Routing
Les protocoles précédents utilisent une forme d'inondation pour la propagation des intérêts ou des données. Le protocole Rumour Routing essaie de trouver un compromis entre l'inondation des intérêts et la propagation des données.
Les auteurs ont utilisé un procédé probabiliste, reposant sur le fait suivant : Des simulations basées sur la méthode de Monte-Carlo ont montré que la probabilité que deux lignes se croisent au sein d'une région rectangulaire est 0.69. De plus, si on utilise 5 lignes passant par un point, la probabilité qu'une autre ligne croise l'une des cinq lignes est 0.997 !
Par conséquent, si on considère le puits et la source comme deux points, et en établissant un nombre réduit de mi-chemins depuis la source et le puits, on aura une forte chance que deux mi-chemins se joignent, créant ainsi un chemin complet entre la source et la destination, tout en évitant l'inondation. La création de ces mi-chemins se base sur la notion d'agent. Un agent est un paquet avec une grande portée (TTL) qui traverse le réseau de noeud en noeud afin d'établir des tables de relais. Il existe deux types d'agents : d'évènement et de requête.
Chaque noeud maintient une table de relais locale, qui contient, pour chaque intérêt, le prochain saut vers le puits et vers la source, ainsi qu'une métrique qui représente le nombre de saut vers chaque extrémité. Lorsqu'un noeud observe un nouvel évènement, il crée un nouvel agent suivant une certaine probabilité. L'agent contient la table d'évènements parcourus au sein du chemin ainsi que le nombre de sauts vers la source de chaque évènement. De plus, l'agent doit transporter avec lui la liste des noeuds parcourus ainsi que leurs voisin directs. La source choisit un voisin aléatoire et lui émet l'agent. Lorsqu'un noeud reçoit un agent, il effectue les opérations suivantes :
-
Si l'agent contient un nouvel évènement, une nouvelle entrée dans la table locale est créée.
-
Le noeud met à jour sa table locale et/ou la table de l'agent pour les entrées communes, suivant le nombre de sauts optimal : i.e. si l'agent possède une route plus courte vers un certain évènement, le noeud met à jour sa table, et vice-versa. Cette méthode permet d'optimiser des routes déjà établies par d'autres agents.
-
Si le noeud connaît des évènements non connus par l'agent, il ajoute les entrées nécessaires dans la table de l'agent.
-
Le noeud choisit comme prochain saut un de ses voisins n'appartenant pas à la liste des noeuds de l'agent, et modifie en conséquence sa table locale pour le prochain saut vers le puits (i.e. le noeud choisi représente le prochain vers le puits).
-
Le noeud ajoute à la liste des noeuds parcourus son identificateur, ainsi que ceux de ses voisins.
-
Le message est envoyé au noeud choisi.
Lorsque le puits désire prélever une donnée du réseau, il consulte sa table locale pour une route fraîche. Si aucune entrée n'est trouvée, il initialise un agent de requête. L'agent contient seulement la liste des noeuds visités. Lorsqu'un noeud reçoit un agent de requête, il vérifie l'existence d'un chemin dans sa table locale. Si ce n'est pas le cas, il choisit un voisin aléatoire et lui transmet l'agent, tout en ajoutant son identificateur dans la liste transportée par l'agent.
