Routage dans les réseaux augmentés

22 juin 2005 P. Fraigniaud - GT Sphère - GDR I3 1

Routage dans les réseaux augmentés

Pierre FraigniaudCNRS

LRI, Univ. Paris Sud (Orsay)


Objectifs

• Expérience de Milgram (1967)• Modélisation (Kleinberg, 2000)• Petits Mondes Navigation• Limites du modèle• Autres modèles• Applications


Expérience de Milgram

Personnes sources s1,s2,...,sk

Personne cible tBut = acheminer une lettre de si à t :

La personne x détenant actuellement la lettre la retransmet à une personne y que x connaît personnellement et dont il espère qu’elle soit plus proche de t.


Résultats de l’expérience

1. Beaucoup de lettres sont arrivées à destination

2. Parmi les lettres arrivées à destination, la médiane du nombre d'intermédiaires fût environ 5

Six degrés de séparation entre individus


Le phénomène semble reproductible

• Dodds, Muhamad, Watts (2003)• Utilisation de la messagerie

électronique• Parmi les chaînes réussies, il se

vérifie que la médiane est d’environ 5

• Attention toutefois : beaucoup de chaînes ne réussissent pas !


Les graphes augmentés

• Un graphe G modélise un ensemble de connaissances communes à tous :

• La Norvège est “plus proche” de la France que l’Uzbékistan

• Un biologiste est “plus proche” d’un médecin que d’un trapéziste

• G est augmenté avec des liens longs choisis aléatoirement, suivant une loi D, pour modéliser les hasards de la vies


Exemple

Noeud x

Noeud y

Le noeud y est le contact distant de x


Modèle de Kleinberg

• Le graphe G est une grille à d dimensions et de n noeuds

• Chaque noeud x choisit y comme contact distant avec probabilité prob(xy) harmonique, c-à-d proportionnel à 1/dist(x,y)


Routage glouton

• Parmi ses 2d+1 noeuds voisins, chaque noeud choisit celui qui est le plus proche de la destination, et lui transmet le message

• Attention : distance de «Manhattan»


Glouton converge

Noeud courant Noeud suivant Cible


Performances du routage glouton

• Si = d alors le routage glouton s’effectue en O(log2n) nombre de pas en moyenne.

• Si ≠ d alors le routage glouton s’effectue en Ω(n) nombre de pas en moyenne, >0.


Preuve

• Coefficient normalisateur (d = 1): ∑1≤i≤n/2(1/i) ≈ log n

• Prob(xy) ≈ 1/(dist(x,y)d log n)

mx

tB = y / dist(y,t) ≤ m/2


Prob(xB) = ∑y Prob(xy)

≥ |B| Prob(xz) ≈ md/(md log n) = 1/log n

mx

tB = y / dist(y,t) ≤ m/2 z


Quelques critiques

1. Le routage glouton est-il représentatif de l’expérience de Milgram ? Peut-on faire mieux ?

2. Pour = d, les performances du routage sont indépendantes de d

3. Les performances du routage ne sont « bonnes » que si = d


Quelques critiques





Peut-on faire mieux ?• L’analyse est exacte : (log2n) (Barrière, Fraigniaud, Kranakis, Krizanc)

• Diamètre (log n) (Martel, Nguyen) • Avec log n liens longs par noeud :

– Glouton : O(log n) (Kleinberg) – NoN : O(log n / loglog n) (Manku, Naor, Wieder)

• Il est possible de construire de façon distribuée un chemin de longueur

O((log n)(loglog n)2) (Lebhar, Schabanel)


Autres distributions

• Quelque soit la distribution (presque !) le routage glouton s'effectue en Ω(log2n/loglog n) étapes en moyenne.

(Aspnes, Diamadi, Shah)


Quelques critiques





Critères de sélection(Killworth & Bernard)

• Expérience à la Milgram : – Recherche avec ≥ 2 critères marche

bien– Recherche avec 1 critère marche mal

• Peut-on interpréter les dimensions de la grille comme autant de critères ?


Routage indirect

• Chaque noeud x possède une liste Lx de liens longs

• Pour router : – le noeud courant x sélectionne y Lx tel que

le lien long de y conduit le plus près de la cible t

– Parmi ses 2d+1 noeuds voisins, x choisit celui qui est le plus proche de y, et lui transmet le message


Performances du routage indirect

• Si, pour tout noeud x, Lx est la liste des liens longs des log n noeuds les plus proches de x (dans la grille), alors le routage indirect s’effectue en O(log1+1/d

n) étapes en moyenne. (Fraigniaud, Gavoille,

Paul)


Quelques critiques





Vers un modèle plus général...

• Contexte : réseaux sociaux modélisés par un graphe augmenté (G,D)

• Questions : • Comment choisir le graphe G ? • Comment choisir la distribution D ?• Que devrait-on observer à propos du

routage glouton dans (G,D) ?


Routage glouton dans (G,D)

• Parmi ses degG(x)+1 noeuds voisins, chaque noeud x choisit celui qui est le plus proche de la destination dans G, et lui transmet le message

• Attention : distance dans G


1) « Petitmondisation »

Un graphe G est petitmondisable s’il existe une distribution D telle que le routage glouton dans (G,D) s’effectue en O(polylog n) nombre d’étapes en moyenne.


Extension de la grille

• Un graphe est de croissance bornée si, pour tout noeud x et tout r>0, la taille de la boule de rayon r centrée en x est rf(r,x) où f satisfait... bon, disons des « conditions spécifiques ».

• Tout graphe de croissance bornée est petitmondisable.

(Duchon, Hanusse, Lebhar, Schabanel)


2) Modèles Hiérarchiques

Prob(xy) ≈ hauteur de leur plus petit ancêtre commun(Kleinberg)

x y


Hiérarchies imbriquées

• Lieu d’habitation, profession, hobbies, etc. • Comment extraire une hiérarchie « globale »

qui reflète toutes ces hiérarchies ?

Outil = décompositions arborescentes


Décomposition arborescente

(Robertson & Seymour)Une décomposion arborescente d’un

graphe G=(V,E) est une paire (T,X) où T est un arbre d’ensemble de sommets I, et X est une collection Xi V, i I telle que :

1. iI Xi = V

2. e=x,y E, i I / x,y Xi

3. Si j est sur le plus court chemin entre i et k dans T alors Xj Xk Xi


Xi

Xk

Xj


Sommet x


Séparateurs récursifs


Largeur d’arborescence• La largeur d’une décomposition

arborescente (T,X) est w(T,X) = maxiI |Xi| - 1

• La largeur d’arborescence tw(G) d’un graphe G est la largeur minimale d’une décomposition arborescente (T,X) de G

tw(G) = min(T,X) w(T,X)


CentroïdeLe centroïde d’un arbre T de n noeuds est un noeud v tel que T-v est une forêt d’arbres d’au plus n/2 noeuds.


Centroïdes récursifs et augmentation

(1)

(3)

(2)

x (4)


Routage glouton

• Pour tout graphe G de largeur d’arborescence ≤ k, il existe une distribution D telle que le routage glouton dans (G,D) s’effectue en

O(k log2n) étapes en moyenne.

(Fraigniaud)

• Application : graphes de largeur arborescente bornée (arbres, cycles, planaires extérieurs, etc.)


Réseaux sociaux Les réseaux sociaux ont (pour la

plupart) un coefficient de « clustering » élevé, c-à-d la probabilité que deux noeuds ayant un voisin commun soit connectés est « élevée ».


Une mauvaise nouvelle

• Les réseaux sociaux sont localement denses !

ils ont une grande largeur d’arborescence...


Une bonne nouvelle• Les réseaux sociaux sont

localement denses ! ils n’ont généralement que

peu de cycles longs


CordalitéLa cordalité d’un graphe est la longueur

de son plus long cycle induit



Graphe de cordalité bornée

• Pour tout graph G de cordalité ≤ k, il existe une distribution D telle que le routage glouton dans (G,D) s’effectue en

O((k + log n) log n) étapes en moyenne.

(Fraigniaud)

• Application: graphes de cordalité O(log n)


Application possibles Conception de : réseaux pair-à-pair réseaux de processeurs


Réseaux pair-à-pair• S’oppose au modèle « maître-

esclave » : tous jouent le même rôle. • Publication et recherche : Table de

Hachage Distribuée (DHT)– Espace de clés K (espace métrique)– Fichiers et utilisateurs sont « hachés » dans

cet espace (fonction de hachage h commune)

– Un utilisateur de clé K prend en charge les fichiers de clé les plus proches de dans K


Router vers une clé

• Objectif central : aller au noeud x en charge de la clé K

• Solution 1 : Maintenir de façon dynamique une topologie structurée

• Solution 2 : Utiliser l’anneau augmenté « harmoniquement »



Conclusion (1)

• Les résultats de l’expérience de Milgram ne sont pas encore très bien compris ni d’un « point de vue conceptuel », ni d’un « point de vue formel ».

• Besoin d’un modèle hiérarchique vraiment satisfaisant.

• De nombreuses applications potentielles : pair-à-pair, réseaux dynamiques, etc.


Conclusion (2)

Problèmes ouverts : – Tout graphe est-il petitmondisable ? – Peut-on augmenter l’anneau de façon

à ce que le routage glouton s’effectue en O(log2n/loglog n) nombre moyen d’étapes ?


Des pointeurs

« A New Perspective on the Small-World Phenomenon: Greedy Routing in Tree-Decomposed Graphs »

In 13th Annual European Symposium on Algorithms (ESA), 2005.

http://www.lri.fr/~pierre

Documents

Routage dans les réseaux augmentés