Fondements de l’algorithmique des réseaux Stéphane Devismes 17/04/2014SCI121

SCI121

Fondements de l’algorithmique des réseaux

Stéphane Devismes

17/04/2014

SCI121

Plan

• Réseau ?• Algorithme distribué ?• Problème à résoudre ?• Exemple : circulation d’un jeton• Conclusion

17/04/2014

SCI121

Plan

• Réseau ?• Algorithme distribué ?• Problème à résoudre ?• Exemple : circulation d’un jeton• Conclusion

17/04/2014

SCI121

Réseaux

17/04/2014

• « En informatique, un réseau est un ensemble interconnecté d’appareils électroniques, géographiquement distants qui échangent des informations »

Wikipédia

SCI121

Exemples de réseaux

• Internet• Le réseau de l’Université• Le réseau téléphonique (filaire, cellulaire)• GPS• Réseau de capteurs (surveillance sismique)• ...

17/04/2014

SCI121

Appareils Electroniques

17/04/2014

SCI121

Interconnections

17/04/2014

SCI121

Echange d’informations

17/04/2014

SCI121

Couches de communication (Modèle OSI)

17/04/2014

ApplicationPrésentation

SessionTransport

RéseauMAC

PhysiqueEnvoi d’un seul bit d’information point à point

Envoi d’une trame de bits (message) point à point

Protocoles réseaux : Algorithmes distribués

Deux fonctions : - Envoi(M,v)- Réception(M,v)

Utilisateur final

SCI121

Objectifs

• Communiquer : mail, chat …• Echanger : fichiers (mp3, doc)• Partager les resources :– Physique (imprimantes)– De calculs (applications)

• Accélérer le calcul– Grid computing– SETI@HOME

17/04/2014

SCI121

Plan

• Réseau ?• Algorithme distribué ?• Problème à résoudre ?• Exemple : circulation d’un jeton• Conclusion

17/04/2014

SCI121

Modèle théorique pour les réseaux : Les systèmes distribués

• Machines ≈ Processus

17/04/2014

SCI121

Les systèmes distribués

• Machines ≈ Processus• Caractéristiques:– Pas de contrôle centralisé• Programmes locaux• Mémoires locales

17/04/2014

SCI121

Les systèmes distribués

• Machines ≈ Processus• Caractéristiques:– Pas de contrôle

centralisé• Programmes locaux• Mémoires locales

– Asynchrones– Pas de temps global

17/04/2014

SCI121

Les systèmes distribués

• Machines ≈ Processus• Caractéristiques:– Pas de contrôle

centralisé• Programmes locaux• Mémoires locales

– Asynchrones– Pas de temps global– Interconnectés

17/04/2014

SCI121

Les systèmes distribués

• Machines ≈ Processus• Caractéristiques:– Pas de contrôle centralisé

• Programmes locaux• Mémoires locales

– Asynchrones– Pas de temps global– Interconnectés

• Passage de messages asynchrone et FIFO

17/04/2014

SCI121

FIFO

17/04/2014

SCI121

FIFO

17/04/2014

A

SCI121

FIFO

17/04/2014

B A

SCI121

FIFO

17/04/2014

C B A

SCI121

FIFO

17/04/2014

AC B

SCI121

FIFO

17/04/2014

BC

SCI121

FIFO

17/04/2014

C

SCI121

Les systèmes distribués

• Hypothèses– Liens bidirectionnels

17/04/2014

SCI121

Liens bidirectionnels : pas toujours !

17/04/2014

SCI121

Les systèmes distribués

• Hypothèses– Liens bidirectionnels– Identité unique

(e.g., adresse IP)

17/04/2014

12

4078

42

167

23

SCI121

Les systèmes distribués

• Hypothèses– Liens bidirectionnels– Identité unique – Topologie statique et

connexe (≈graphe) • Nous excluons ici les

réseaux téléphoniques sans-fils !

17/04/2014

1674078

12

2342

SCI121

Rappel : Connexité

Connexe !

17/04/2014

SCI121

Rappel : Connexité

Pas connexe !

17/04/2014

SCI121

Algorithme distribué

17/04/2014

SCI121

Algorithme DistribuéExemple : Calcul d’un arbre couvrant

17/04/2014

SCI121

Algorithme DistribuéExemple : Calcul d’un arbre couvrant

17/04/2014

SCI121

Algorithme DistribuéExemple : Calcul d’un arbre couvrant

17/04/2014

SCI121

• Entrées réparties

Algorithme DistribuéExemple : Calcul d’un arbre couvrant

17/04/2014

Racine= fauxRacine= vrai

Racine= faux

Racine= fauxRacine= faux

SCI121

• Entrées réparties• Calculs locaux– Mémoires locales– Programmes locals– Envoi de messages– Décision locale

Algorithme DistribuéExemple : Calcul d’un arbre couvrant

17/04/2014

Racine= faux

SCI121

• Entrées réparties• Calculs locaux– Mémoires locales– Programmes locals– Envoi de messages– Decision locale

• Sorties réparties

Algorithme DistribuéExemple : Calcul d’un arbre couvrant

17/04/2014

Racine= fauxRacine= vrai

Racine= faux

Racine= fauxRacine= faux

SCI121

Algorithme DistribuéExemple : Calcul d’un arbre couvrant

• Entrées réparties• Calculs locaux– Mémoires locales– Programmes locals– Envoi de messages– Decision locale

• Sorties réparties• Tâche globale

17/04/2014

Racine= fauxRacine= vrai

Racine= faux

Racine= fauxRacine= faux

SCI121

Evaluation des performancesQuel est le meilleur algorithme ?

• #Messages

• Volume (en bits)

• Temps (en rondes)

• Occupation mémoire (en bits)

17/04/2014

SCI121

Plan

• Réseau ?• Algorithme distribué ?• Problème à résoudre ?• Exemple : circulation d’un jeton• Conclusion

17/04/2014

SCI121

Problèmes classiques

• Echange de donnée : routage, diffusion, …

• Accords : consensus, élection, …

• Auto-organisation : arbre couvrant, clustering

• Allocation de ressources : exclusion mutuelle,

diner des philosophes…

17/04/2014

SCI121

Echange de donnée : routage

17/04/2014

SCI121

Echange de donnée : routage

17/04/2014

Source

Destination

SCI121

Echange de donnée : routage

17/04/2014

SCI121

Accord : électionCalculer un chef !

17/04/2014

SCI121

Accord : électionCalculer un chef !

17/04/2014

42

22

34

5856

7231

15

12

SCI121

Accord : électionCalculer un chef !

17/04/2014

42

22

34

5856

7231

15

1212

12

12 12

12

12 12

12 12

SCI121

Auto-organisation : k-Clustering

17/04/2014

SCI121

Auto-organisation : k-Clustering

17/04/2014

SCI121

Auto-organisation : k-Clustering

• Ex. k=2

17/04/2014

≤k

SCI121

Auto-organisation : k-Clustering

• Ex. k=2

17/04/2014

≤k

SCI121

Allocation de ressources : exclusion mutuelle

17/04/2014

SCI121

Allocation de ressources : exclusion mutuelle

17/04/2014

SCI121

Allocation de ressources : exclusion mutuelle

17/04/2014

SCI121

Allocation de ressources : exclusion mutuelle

17/04/2014

SCI121

Allocation de ressources : exclusion mutuelle

17/04/2014

SCI121

Plan

• Réseau ?• Algorithme distribué ?• Problème à résoudre ?• Exemple : circulation d’un jeton• Conclusion

17/04/2014

SCI121

Circulation d’un jeton

• Plan– Définition– Solution dans un réseau en anneau (token ring)– Solution dans un réseau en arbre– Solution dans un réseau quelconque

17/04/2014

SCI121

Circulation d’un jeton : définition

• Un message appelé « jeton »

– Circule séquentiellement dans le réseau

– Il doit visiter tous les processus

– La circulation termine

17/04/2014

SCI121

Circulation d’un jeton dans un anneau

17/04/2014

SCI121

Circulation d’un jeton dans un anneau

17/04/2014

0

11

1

1

11

1

0

0

000

0

0

1

SCI121

Circulation d’un jeton dans un anneau

• Un initiateur

17/04/2014

0

11

1

1

11

1

0

0

000

0

0

1

SCI121

Circulation d’un jeton dans un anneau

• L’initiateur envoie le jeton J sur le canal 0

17/04/2014

0

11

1

1

11

1

0

0

000

0

0

1

J

SCI121

Circulation d’un jeton dans un anneau

• Sur réception du canal i, un non-initiateur renvoie le jeton sur le canal (i+1) mod 2

17/04/2014

0

11

1

1

11

1

0

0

000

0

0

1 J

SCI121

Circulation d’un jeton dans un anneau

• Sur réception du canal i, un non-initiateur renvoie le jeton sur le canal (i+1) mod 2

17/04/2014

0

11

1

1

11

1

0

0

000

0

0

1

J

SCI121

Circulation d’un jeton dans un anneau

• Sur réception du canal i, un non-initiateur renvoie le jeton sur le canal (i+1) mod 2

17/04/2014

0

11

1

1

11

1

0

0

000

0

0

1

J

SCI121

Circulation d’un jeton dans un anneau

• Sur réception du canal i, un non-initiateur renvoie le jeton sur le canal (i+1) mod 2

17/04/2014

0

11

1

1

11

1

0

0

000

0

0

1

J

SCI121

Circulation d’un jeton dans un anneau

• Sur réception du canal i, un non-initiateur renvoie le jeton sur le canal (i+1) mod 2

17/04/2014

0

11

1

1

11

1

0

0

000

0

0

1

J

SCI121

Circulation d’un jeton dans un anneau

• Sur réception du canal i, un non-initiateur renvoie le jeton sur le canal (i+1) mod 2

17/04/2014

0

11

1

1

11

1

0

0

000

0

0

1

J

SCI121

Circulation d’un jeton dans un anneau

• Sur réception du canal i, un non-initiateur renvoie le jeton sur le canal (i+1) mod 2

17/04/2014

0

11

1

1

11

1

0

0

000

0

0

1J

SCI121

Circulation d’un jeton dans un anneau

• Sur réception, l’initiateur décide la terminaison

17/04/2014

0

11

1

1

11

1

0

0

000

0

0

1

SCI121

Circulation d’un jeton dans un arbre

• Quasiment le même algorithme !

17/04/2014

0

0

0 0 0

0

1

11

2

SCI121

Circulation d’un jeton dans un arbre

• L’initiateur envoie le jeton J sur le canal 0

17/04/2014

0

0

0 0 0

0

1

11

2

J

SCI121

Circulation d’un jeton dans un arbre

• Sur réception du canal i, un non-initiateur renvoie le jeton sur le canal (i+1) mod δ

• Ici δ = 3• (2+1) mod 3 = 0

17/04/2014

0

0

0 0 0

0

1

11

2J

SCI121

Circulation d’un jeton dans un arbre

• Sur réception du canal i, un non-initiateur renvoie le jeton sur le canal (i+1) mod δ

• Ici δ = 3• (2+1) mod 3 = 0

17/04/2014

0

0

0 0 0

0

1

11

2

J

SCI121

Circulation d’un jeton dans un arbre

• Sur réception du canal i, un non-initiateur renvoie le jeton sur le canal (i+1) mod δ

• Ici δ = 1• (0+1) mod 1 = 0

17/04/2014

0

0

0 0 0

0

1

11

2

J

SCI121

Circulation d’un jeton dans un arbre

• Sur réception du canal i, un non-initiateur renvoie le jeton sur le canal (i+1) mod δ

• Ici δ = 3• (0+1) mod 3 = 1

17/04/2014

0

0

0 0 0

0

1

11

2

J

SCI121

Circulation d’un jeton dans un arbre

• Sur réception du canal i, un non-initiateur renvoie le jeton sur le canal (i+1) mod δ

• Ici δ = 1• (0+1) mod 1 = 0

17/04/2014

0

0

0 0 0

0

1

11

2

J

SCI121

Circulation d’un jeton dans un arbre

• Sur réception du canal i, un non-initiateur renvoie le jeton sur le canal (i+1) mod δ

• Ici δ = 3• (1+1) mod 3 = 2

17/04/2014

0

0

0 0 0

0

1

11

2J

SCI121

Circulation d’un jeton dans un arbre

• Sur réception du canal i, un non-initiateur renvoie le jeton sur le canal (i+1) mod δ

• Ici δ = 2• (0+1) mod 2 = 1

17/04/2014

0

0

0 0 0

0

1

11

2

J

SCI121

Circulation d’un jeton dans un arbre

• Sur réception du canal i, un non-initiateur renvoie le jeton sur le canal (i+1) mod δ

• Ici δ = 2• (0+1) mod 2 = 1

17/04/2014

0

0

0 0 0

0

1

11

2

J

SCI121

Circulation d’un jeton dans un arbre

• Sur réception du canal i, un non-initiateur renvoie le jeton sur le canal (i+1) mod δ

• Ici δ = 1• (0+1) mod 1 = 0

17/04/2014

0

0

0 0 0

0

1

11

2

J

SCI121

Circulation d’un jeton dans un arbre

• Sur réception du canal i, un non-initiateur renvoie le jeton sur le canal (i+1) mod δ

• Ici δ = 2• (1+1) mod 2 = 0

17/04/2014

0

0

0 0 0

0

1

11

2J

SCI121

Circulation d’un jeton dans un arbre

• Sur réception du canal δ-1, l’initiateur décide la terminaison

• Ici δ-1 = 1

17/04/2014

0

0

0 0 0

0

1

11

2

SCI121

Circulation d’un jeton dans un réseau quelconque ?

• Est-ce que l’algorithme précédent fonctionne ?

NON !

17/04/2014

SCI121

Exemple

17/04/2014

0

1

2

0

1

0

0 0

0

0

0

0

1

1

1

1

1

1

SCI121

Solution

• Algorithme de Tarry (1885)

• Problème de Labyrinthe• « Ne reprendre l'allée initiale qui a conduit à un

carrefour pour la première fois que lorsqu'on ne peut pas faire autrement »

• Sommets = intersections• Liens = allées entre les intersections des arêtes

17/04/2014

SCI121

Variables

• Pour chaque processus

– Un pointeur P {NULL} {0…δ-1}∈ ∪ (initialisé à NULL)

– Un tableau de Booléen VISITE[0…δ-1], initialement toutes les cases sont à faux.

17/04/2014

SCI121

Exemple

17/04/2014

0

1

2

0

1

0

0 0

0

0

0

2

1

1

1

1 11

02

SCI121

Exemple

17/04/2014

0

1

2

0

1

0

0 0

0

0

0

2

1

1

1

1 11

02

J

SCI121

Exemple

17/04/2014

0

1

2

0

1

0

0 0

0

0

0

2

1

1

1

1 11

02

J

SCI121

Exemple

17/04/2014

0

1

2

0

1

0 0

0

0

0

2

1

1

1

1 11

02

J

0

SCI121

Exemple

17/04/2014

0

1

2

0

1

0

0

0

0

2

1

1

1

1 11

02

J

0

0

SCI121

Exemple

17/04/2014

0

1

2

0

1

0

0

0

0

2

1

1

1

1 11

2

J

0

0

0

SCI121

Exemple

17/04/2014

0

1

2

0

1

0

0

0

0

2

1

1

1

1 11

2J

0

0

0

SCI121

Exemple

17/04/2014

0

1

2

0

1

0

0

0

0

2

1

1

1

1 11

2

J

0

0

0

SCI121

Exemple

17/04/2014

0

1

2

0

1

0

0

0

0

2

1

1

1

1 11

2

J

0

0

0

SCI121

Exemple

17/04/2014

0

1

2

0

1

0

0

0

0

2

1

1

1 11

2

J

0

0

0

1

SCI121

Exemple

17/04/2014

0

1

2

0

1

0

0

0

0

2

1

1 11

2

J0

0

0

1

1

SCI121

Exemple

17/04/2014

0

1

2

0

1

0

0

0

0

2

1 11

2

J

0

0

0

1

1

1

SCI121

Exemple

17/04/2014

0

1

2

0

1

0

0

0

0

2

1 11

2

J

0

0

0

1

1

1

SCI121

Exemple

17/04/2014

0

1

2

0

1

0

0

0

0

2

1 11

2

J0

0

0

1

1

1

SCI121

Exemple

17/04/2014

0

1

2

0

1

0

0

0

0

2

1 11

2

J

0

0

0

1

1

1

SCI121

Exemple

17/04/2014

0

1

2

0

1

0

0

0

0

2

1 11

2

J

0

0

0

1

1

1

SCI121

Exemple

17/04/2014

0

1

2

0

1

0

0

0

0

2

1 11

2

J

0

0

0

1

1

1

SCI121

Exemple

17/04/2014

0

1

2

0

1

0

0

0

0

2

1 11

2

J 0

0

0

1

1

1

SCI121

Exemple

17/04/2014

0

1

2

0

1

0

0

0

0

2

1 11

2

J

0

0

0

1

1

1

SCI121

Exemple

17/04/2014

0

1

2

0

1

0

0

0

0

2

1 11

2

J

0

0

0

1

1

1

SCI121

Exemple

17/04/2014

0

1

2

0

1

0

0

0

2

1 11

2

J

0

0

0

1

1

10

SCI121

Exemple

17/04/2014

0

1

2

0

1

0

0

0

2

1 11

20

0

0

1

1

10

Terminé !

SCI121

Plan

• Réseau ?• Algorithme distribué ?• Problème à résoudre ?• Exemple : circulation d’un jeton• Conclusion

17/04/2014

SCI121

Conclusion

• Depuis 40 ans– La plupart des problèmes d’algorithmiques

réparties ont été résolus de manière efficace

– En supposant des réseaux sans pannes …

17/04/2014

SCI121

Conclusion: Challenge actuel

• Les réseaux modernes sont à grande-échelle et fait de machines hétérogènes et produites en masses à faible coût, e.g.– Internet

• (10 milliard de machine connectée d’ici 2016)• Internet des objets

– Réseaux sans fils• Communication radio : beaucoup de pertes de messages • Crash de machines à cause des batteries limitées

⇒ Forte probabilité de pannes⇒ Intervention humain impossible

⇒ Besoin d’algorithmes distribués tolérant les pannes17/04/2014

SCI12117/04/2014

Merci de votre attention !