Quelques contributions à la résistance au facteur
d’échelle dans les réseaux de communication
C. PhamSoutenance d’HDR
Mardi 16 décembre 2003ENS Lyon
22
Brève présentation de mon parcours
Juil. 1997: Thèse en informatique à Paris 6, Laboratoire LIP6, sous la direction du Pr. Serge Fdida
Sep. 1997: Année post-doctorale à UCLA, sous la direction du Pr. Rajive Bagrodia
Oct. 1998: MCF à U. Lyon 1 dans l'équipe de Bernard Tourancheau
Jan. 1999: Création de la JE UCBL RESAM et membre permanent de cette structure
Sep. 1999: Création de l'action RESO de L'INRIA Rhône-Alpes et membre de l'action
Juil. 2000: Déménagement dans les locaux de l’ENS
33
Enseignement
Responsable du DESS IIR Réseaux, UCBL Depuis 1999, responsable pédagogique d’une
formation professionnalisante dans le domaine pointu des réseaux: définitions des enseignements, gestion des intervenants, des plannings…
Cours 3ème cycle DEA DIF, DEA DISIC, DESS CCI, DESS IIR
Cours 2ème cycle Maitrise informatique, MIM, MIAG
Encadrement d’étudiants: maitrise, master, DEA, DESS
Le visage de l’Internet
Le big-bang
1969
2003: environ 200 millions de machines
55
www.explosion-du-web.org
66
Les changements technologiques et d’échelle
Généralisation de la fibre optique (DWDM)
Débit dans le cœur du réseau de plusieurs dizaines de Gbits/s!
0,1
1
10
100
1000
10000
1985 1990 1995 2000
Spec95Int CPU results
0,1
1
10
100
1000
10000
1985 1990 1995 2000
Fib
er
Ca
pa
cit
y (
Gb
it/s
)
TDM DWDM
2x / 18 months 2x / 7 months
Packet processing Power Link Speed
From McKeown
77
DWDM, Myrinet, 10GE,Infiniband…
Système de communicationtraditionnel
Comment y arriver?
200km/h 100km/h
180km/h
50km/h
170km/h
Performances de bout-en-bout?
88
Le tout-IP
QuickTime™ et undécompresseur TIFF (LZW)sont requis pour visionner cette image.
Transparent de Jim Kurose
99
Les difficultés liées à la taille
Comment connaître/prendreen compte l’état
global du système?
Exemples
RoutageDéploiement de protocoles
Contrôle de congestion
1010
Les difficultés liées à la taille
Aggrégation du trafic:comment supporter la
charge?
Exemples
Sites web populairesFeedbacks
1111
Les difficultés liées à la taille
Comment étudier lesystème?
Exemples
Validation de protocolesEtude de performances
SimulationsExpérimentations
E=MC2
1212
Résistance au facteur d’échelle
Dans les méthodes d’évaluation Dans les protocoles de
communication Dans la conception des systèmes de
communication
AGGREGEONS!
1313
Quelle taille pour quelle complexité
QuickTime™ et undécompresseur TIFF (LZW)sont requis pour visionner cette image.
Transparent emprunté à Jim Kurose
1969
1414
réseaux actifs
protocoles de haut niveau
app
li
interfaces bas niveau
x Gbits/s100 à 1000 Mbits/s
intelligence embarquée
100 à 1000 Mbits/s
Rajouter de l’intelligence!
Aggréger n’est pas suffisant, il faut aussi une distribution de l’intelligence: où, quand et comment?
1515
Mes 3 thèmes de recherches
Simulationsparallèles sur
grappes de PCs
Multicastfiable actif
Optimisationsous-systèmes
de comm.
RESISTANCE AU FACTEUR D’ECHELLE
www.robust.com
1616
Les étudiants contributeurs
Thèse & DEA M. Maimour E. Lemoine
Maîtrise F. Goffinet, S. Oranger L. Cavallin J. Mazuy (encadré par M. Maimour) X. Prost
Master C. Albrecht R. Asthana
Simulations parallèles sur grappes
Multicast fiable actif
Optimisation de sous-systèmes de
comm.
1818
Simuler des systèmes complexes: 100 minutes pour convaincre!
Réseaux Gbits/s 200 routeurs 1000 sources de trafic, 100Mbits/s Simulation au niveau du packet (500 octets), 1 évènement par paquet
capacité des liens temps de simulation généralement, plus d’ 1 événement par
paquet
Plus de 30 millions d’évènements à simuler pour 1sde temps réel. 12h pour simuler 72s (event=20us)
1919
Simulation parallèle de réseaux
logical process (LP)
packetheventt
parallèle
2020
CSAM
CSAM: Conservative Simulator for ATM network Model
Simulation au niveau de la cellule Approche conservative (aucune faute
temporelle) Fonctionne sur CM-5, Cray T3E Exploite le lookahead des liens de
communication: usage transparent
travauxde thèse
2121
Modèle de base: 78 comm. ATM
Routage avec fonctions de coût dynamiquesContrôle d’admission
travauxde thèse
2222
La suite MPI-BIP/BIP-SMP/BIP
Projet BIP [Prylli, Tourancheau]: librairie de communication optimisée pour Myrinet
MPI-BIP, BIP-SMP [Westrelin, Geoffray, Tourancheau]
Myrinet physical layer
BIP BIP-SMP
MPI-BIP
les NICs programmableschangent la distributionspatiale traditionnelle des tâches.
2323
Facilement « upgradés » Facilement intégrés Perf. interconnexion
Machines parallèles vs grappes
Cluster SUN/e-Toile
Station de travail
Chères Vite dépassés Peu accessibles
2424
Les clusters dans le TOP 500
16 Nov. 2003
7 clusters dansle TOP 10!
2626
Simulations // avec BIP & MPI/BIP
Aggrégeons l’envoi des messages (Obsolètes)
Comment améliorer ces performances?
Simulations parallèles sur grappesPentium Pro 200MHz
2727
Pourquoi peut-on aggréger?
Le simulateur alterne phase de traitement et phase de récupération de messages
Encadrement de C. Albrecht, Univ. Luebeck
Événements à traiteravant d’en récupérer d’autres
2828
Aggréger dans CSAM
Aggrégation: 1 buffer/récepteur Etude de la taille d’aggrégation
prise en compte des perf. de BIP/MPI-BIP
Taille d’un message = 42 octets
2929
Machine multi-processeurs
Travaux effectués avec P. Geoffray, utilisation de BIP-SMP
Aggrégation sur des CLUters of Multi-Processors (CLUMPs)
Performances assymmétriques
3030
Gain de l’aggrégation assymmétrique
0
0.5
1
1.5
2
2.5
no aggr 156 256 512 1024 256-156
512-156
1024-156
speedup
2 ext. 2 int. 4 ext. 2x2 int.
Dual Pentium Pro 450MHz
aggr. x-y: x=distant, y=interne
3131
Comparaison de différentes stratégiesTravaux avec C. Albrecht, R. Westrelin
Senderinitiated
Receiverinitiated
Simulations parallèles sur grappes
Multicast fiable actif
Optimisation de sous-systèmes de
comm.
3333
Thèse de Moufida Maimour
1ère thèse encadrée (encadrant HDR: Pascale Vicat-Blanc Primet)
« Conception, Analyse et Validation de Protocoles de Multicast Fiables à Assistance des Routeurs », soutenue le 25 nov. 2003, ENS Lyon
Source
data
datadata
data
Receiver Receiver Receiver
Source
data
datadata
data
Receiver Receiver Receiver
datadata
3434
Exemple: visio-conférence
Adresse de groupe multicast 224.34.7.12
224.34.7.12
Vue de l’usager
3535
Ce qu’il y a derrière…
domain
Point de peering
Routeur de l’Internet
Routeur d’accès
224.34.7.12
déploiementgestion de groupessession advertising
construction de l’arbreallocation d’adresses
routagefiabilité
multicastunicast
routing
TCP ?
3737source www.multicasttech.com/status
~33%
L’internet n’est pas (encore) multicast!
~3-4% des AS
3838
INTERNET
En image cela donne…
multicast ASunicast AS
3939
Les problèmes d’échelle liés au multicast fiable
Implosion des NACKs!
NACK4
NACK4
NACK4
NACK4
source
Grand nombre de récepteurs
source1Mbps 1Mbps
0.5Mbps2Mbps
2Mbps
5Mbps
Contrôle du débit?
4040
Protocoles de multicast fiable
Approches de bout en bout : avec recouvrement local :
Approche probabiliste [SRM] Approches hiérarchiques statiques [RMTP] ou
dynamiques [TMTP, TRAM] Approches avec assistance de routeurs
un arbre de recouvrement identique à l’arbre physique du multicast avec cache de données au niveau de nœuds intermédiaires [ARM, RMANP, AER]
un arbre de recouvrement logique construit avec l’assistance des routeurs [LMS, PGM, AIM]
4141
Réseaux actifs/programmables
Casse la vision d’un réseau « bête » en autorisant les routeurs à exécuter des codes spécifiques (services actifs)
DataData
code A1
code A2
A1
A2Plus de flexibilité pour implémenter et déployer des services spécifiques aux applications et aux protocoles.
Plus de performance globalement grâce à la réduction du trafic, à une meilleure régulation…
4242
Ex: suppression globale des NACKs
NACK4
NACK4
NACK4
NACK4data4
NACK4
1 seul NACK esttransmis vers lasource
TAMANOIR[GELAS,LEFEVRE]
4343
Etude des différentes stratégies
S1 : suppression globale des NACK
S2 : suppression locale des NACK S2S : + subcast à partir de la source
S3 : suppression globale des NACK + subcast à partir des routeurs
S3S : + subcast à partir de la source
4444
Analyses préliminaires
4545
S1
Bénéfices de l’aggrégation globale
4646
Impacts de la puissance des routeurs
S3
2
4747
La proposition DyRAM
Protocole avec de nouveaux services actifs légers (autre que le cache) pour résister au passage à
l’échelle et permettre de faibles latences
ElectionDynamique
Contrôle de
Congestion
subcast desrepair
SuppressionGlobaleNACK
DétectionRapide des
pertes
PartitionnementDes
Récepteurs
4848
Impacts sur la latence
p=0.25
#grp: 6…244 récepteurs/groupe
DPP est très bénéfiqueà DyRAM
A : supp. des NACKs
D : A + Détection des pertes
DyRAM : A + Election
DyRAM+ : DyRAM + Détection des pertes
4949
Contrôle de congestion AMCA
AMCA se base sur des services actifs d’estimation des RTTs par section
Fournit une compatibilité satisfaisante avec TCP
5050
Data replications
Code & data transfers, interactive job submissions
Data communications for distributed applications (collective & gather operations, sync. barrier)
Databases, directories services
Data replications
Code & data transfers, interactive job submissions
Data communications for distributed applications (collective & gather operations, sync. barrier)
Databases, directories services
Multicast address group 224.2.0.1
224.2.0.1
SDSC IBM SP1024 procs5x12x17 =1020
NCSA Origin Array256+128+1285x12x(4+2+2) =480
ENS cluster48 nodes
Multicast fiable pour la grille
5151
Scénario de déploiement
Réseau Gbits/sVTHD
routeur actif routeur actif
routeur actif
sourcesource
Internet Data Center
centre de calcul
centre de calcul
campus/entreprise
aggrégationsubcastélectioncalcul RTT
aggrégationsubcastdétection des pertes
5252
Multicast sur E-Toile (RNTL)
ENS CERN
CEAROCQ
VTHD
source
Implémentation deDyRAM [Bouhafs]
Demo 5 juin, 2003
5353
La démo sans effet démo!
source
CERN ENS
ENS ENS
5454
Projets
Abondement ANVAR: prototypage de services actifs sur une plate-forme de réseaux actifs d'expérimentation
Projet RNTL e-Toile: protocoles de multicast fiable actif pour une grille de calcul active
Projet RNRT VTHD++: expérimentations du multicast actif sur un réseau très haut-débit
ACI GRID: Services Réseaux et Intelligence pour la Grille
Simulations Parallèles sur grappes
Multicast fiable actif
Optimisation de sous-systèmes de
comm.
5656
Thèse de Eric Lemoine
Stage de DEA: Intelligence embarquée dans les interfaces réseaux
Interaction entre le système d'exploitation et le système de communication: exécuter mieux, et plus tôt, les tâches liées à la communication
Etude des performances du déport de composantes logicielles vers les cartes d'interface réseaux, prototypes avec des applications cibles
Continuation en thèse CIFRE avec SUN Labs, Europe (encadrement 50% avec L. Lefèvre)
Contribue à l’obtention de la performance de bout-en-bout
5757
Problème de robustesse
NIC DMA
CPU1 CPU2
DRIVER
Backlogqueue
RINT
RISR
interruptionslogicielle Copies effectuées dans le
contexte de l’interruption
Dmax
Système robuste
Effondrement desperformances
Dmax
Débit d’entrée
Débit de sortie
5858
Problème de performance
NIC DMA
CPU1 CPU2DRIVERDevicequeue
RINT
interruptionlogicielle
RISR
NAPI dans Linux[SALIM et al]
Mode polling: on vide et traite l’anneau entièrement
(RINT disabled)
CPU1 CPU2 CPU3 CPU4
t
5959
www.non-robuste.com
Exemple: serveur web
Contenu populaire Beaucoup de
petites requêtes: plusieurs milliers/min…
…engendrant des flux lourds en retour.
Sujet aux attaques de type DOS, DDOS
6060
Proposition KNET
NICDMA
DRIVER
Threadsréseau
CPU1 CPU2
classification
CPU1 CPU2
Devicequeue
RINT
RISR
1 anneau de réception par CPUClassification au plus tôt
Remonté en parallèle de paquets
Myrinet
ip_src & (nb_proc-1)
Proposition de nouveaux services à mettre dans les cartes d’interface
6161
Premiers résultats
KNET+sendfile()
KNET+send()
NAPI+sendfile()
NAPI+send()
34%
17%
6262
Collaborations et contrats
SUN Labs 3 thèses CIFRE avec SUN Labs, Grenoble
(M. Herbert, E. Lemoine et J. Laganier)
Perspectives & Conclusions
6464
Perspectives de recherche
Mieux utiliser les techniques de simulations parallèles
Reste un énorme travail d’ingénierie pour le multicast. Etude de la problématique liée aux réseaux très haut-débit.
Mécanismes de QoS pour les sous-systèmes de communications
6565
Conclusions
Le métier d’enseignant-chercheur est formidable!
3 axes de recherches qui contribuent à la résistance au facteur d’échelle.
La recherche aussi doit nous permettre de mieux enseigner.