Un serveur, une antenne, un routeur consomment presque autant vides que pleins. La solution est combinatoire : regrouper la charge sur le minimum d'équipements et endormir le reste. Trois problèmes classiques, trois algorithmes, tous NP-difficiles, tous approchés.
Le trafic varie du simple au triple dans la journée, la consommation des équipements presque pas. On économise donc en concentrant la charge et en endormant le reste. Cela donne bin packing pour les VM dans un data center (First-Fit, Best-Fit, First-Fit-Decreasing), set cover pour les antennes mobiles (algorithme glouton, rapport H(s)) et routage économe pour les réseaux filaires (heuristique LL-SP). Ces trois problèmes sont NP-difficiles : on utilise des heuristiques dont on sait borner l'erreur.
01 · Pourquoi les réseaux gaspillent
Internet représente 3 à 4 % de l'énergie mondiale et ça monte. La cause n'est pas seulement le volume : l'infrastructure est surdimensionnée et disponible en permanence, liens et équipements sont calibrés pour l'heure de pointe, et la consommation totale reste à peu près constante malgré des profils de trafic très cycliques (baisse la nuit, hausse le jour, observé sur une quarantaine d'ISP américains et européens).
Éléments plus sobres, moins complexes. Exemple : commutation purement optique, des térabits pour bien moins de puissance (Baliga 2007). Adoption encore lointaine.
Power scaling (fréquence et tension) et idle logic (éteindre vite les sous-composants inactifs). Courant dans les CPU, rare dans le matériel réseau.
Mettre en veille ce qui ne sert pas. Exige du proxying (un Network Connectivity Proxy garde la présence réseau du nœud endormi). C'est l'objet de ce cours.
Éteindre ne marche que si le système reste utilisable : il faut que toutes les demandes soient encore servies. C'est ce qui transforme « économiser » en problème d'optimisation sous contraintes.
02 · Data centers
Un data center héberge des applications dans des machines virtuelles, qu'un ordonnanceur place sur des serveurs ayant assez de ressources. Un serveur consomme à peu près tout ou rien (modèle ON/OFF). Économiser revient à tasser les VM sur le minimum de serveurs et éteindre les autres.
Bin packing. Des items de tailles entières, des boîtes de capacité B. Quel est le nombre minimal K de boîtes pour tout ranger ? On note OPT ce minimum. Ici un item est une VM, une boîte est un serveur.
Aucun algorithme d'approximation de rapport absolu meilleur que 3/2 sauf si P = NP. Pseudo-polynomial pour K fixé, polynomial pour B fixé.
Un algorithme polynomial qui rend une solution réalisable à un facteur garanti de OPT. Une 2-approximation utilise au plus 2 x OPT boîtes.
Il faut au moins ceil(somme des tailles / B) boîtes. Utile pour savoir si on est optimal sans tout énumérer.
First-Fit (FF) // items dans l'ordre d'arrivée pour chaque item : le mettre dans la première boîte où il rentre, sinon ouvrir une boîte // FF(L) <= 1,7 OPT Best-Fit (BF) pour chaque item : le mettre dans la boîte la plus chargée où il rentre, sinon ouvrir une boîte // BF(L) <= 1,7 OPT First-Fit-Decreasing (FFD) trier les items par taille décroissante, puis appliquer FF // FFD(I) <= 11/9 OPT(I) + 6/9
L'intuition de FFD : les gros items sont ceux qui posent problème, on les place d'abord et les petits comblent les trous. Essaie-le sur les instances des exercices (capacité 10). L'instance e est celle où FF et BF échouent alors que FFD trouve l'optimum.
03 · Réseaux mobiles
Une antenne consomme presque autant avec peu de trafic qu'avec beaucoup (pas de proportionnalité, encore). Deux idées : endormir les antennes inutilisées, puis regrouper les communications pour en vider d'autres. Le défi : trouver l'association mobiles-antennes qui utilise le minimum d'antennes.
Minimum Set Cover. Un univers U (les mobiles à servir) et des ensembles S1..Sn (chaque antenne couvre certains mobiles). Choisir le moins d'ensembles possible dont l'union est U (coût uniforme 1).
Glouton tant que U n'est pas couvert : choisir l'ensemble qui couvre le plus d'éléments non encore couverts // temps linéaire en la somme des tailles (file à seaux) // rapport d'approximation H(s) = 1 + 1/2 + ... + 1/s <= ln s + 1
Le glouton peut donc donner un recouvrement H(s) fois plus grand que l'optimum. Sur un petit univers de 6 éléments, H(6) = 2,45. Regarde l'instance Ex2 (b) : le glouton se laisse séduire par l'ensemble le plus gros et finit avec 4 ensembles alors que 3 suffisent.
04 · Réseaux filaires
Sur un routeur, la charge influence peu la consommation : pour économiser il faut éteindre des interfaces et des châssis. L'Energy Aware Routing route toutes les demandes en minimisant le nombre d'équipements actifs. Contrairement au plus court chemin qui étale le trafic partout, on le concentre sur un sous-réseau et on éteint le reste.
Pas de garantie d'approximation, contrairement aux deux problèmes précédents. On modélise en MILP (programme linéaire mixte) avec un solveur, ou on utilise une heuristique.
Least Loaded + Shortest Path : on essaie d'endormir le nœud le moins chargé, on route tout par plus courts chemins, si c'est infaisable on le rallume.
L = V tant que L non vide : lln = nœud le moins chargé de L essayer de mettre lln en veille router toutes les demandes par plus courts chemins si le routage n'est pas réalisable : remettre lln en marche, revenir au routage précédent retirer lln de L
Le petit réseau ci-dessous a six routeurs et des liens de capacité 2. Trois scénarios reprennent l'idée du profil journalier : en heure creuse on peut éteindre un routeur au prix d'un détour, la nuit un nœud vide s'éteint gratuitement, à l'heure de pointe rien ne s'éteint.
Dans le scénario « heure creuse », éteindre B rallonge le chemin A vers C de 2 à 4 sauts : c'est le stretch. Les économies d'énergie se paient en latence, et les chemins de secours disparaissent, donc la résilience aux pannes baisse. Le cours étudie ces deux effets (allongement des routes, protection contre les pannes).
05 · Bilan
| Contexte | Problème | Complexité | Algorithme | Garantie |
|---|---|---|---|---|
| Data center | Bin packing (VM sur serveurs) | NP-complet fort | FF, BF, FFD | FF, BF <= 1,7 OPT ; FFD <= 11/9 OPT + 6/9 |
| Mobile | Set cover (antennes) | NP-difficile | Glouton | H(s) <= ln s + 1 |
| Réseau coeur | Routage économe | NP-complet, non approximable | MILP ou LL-SP | Aucune (heuristique) |
Beaucoup de choses ont été proposées depuis 2008, et beaucoup reste à mettre en pratique. Les pistes : matériel plus économe, SDN et virtualisation, réseau ubiquitaire et optimisation conjointe.
Pour ne pas être surpris en contrôle.
06 · Exercices corrigés
Les exercices de bin packing et de set cover viennent des slides du prof. Les corrigés ont été calculés par programme et vérifiés contre une recherche exhaustive de l'optimum.
Les exercices à figure du cours (set cover Ex3 et Ex4 avec des disques d'antennes, routage EAR et LL-SP sur le graphe du prof) reposent sur des schémas. Ils ne sont pas inclus tant qu'ils n'ont pas été redessinés fidèlement. Le réseau à six routeurs de cette page est un exemple d'illustration, pas celui du prof.
Trois instances, capacité 10.
Énoncé. Combien de boîtes de capacité 10 faut-il pour I = {4, 8, 1, 4, 2, 1}, puis {9, 8, 2, 2, 5, 4}, puis {2, 5, 4, 7, 1, 3, 8} ? Proposer un algorithme efficace.
Somme = 20, donc au moins 2 boîtes. {8, 2} et {4, 4, 1, 1} conviennent : OPT = 2.
Somme = 30 mais 3 boîtes exigeraient trois boîtes exactement pleines. Or le 9 ne se range qu'avec un 1, qui n'existe pas : il reste seul. Le 8 ne se range qu'avec un 2. Il reste 2, 5, 4 (somme 11 > 10) qui ne tiennent pas dans une seule boîte. Donc OPT = 4, par exemple {9}, {8, 2}, {5, 4}, {2}.
Somme = 30, borne basse 3. {8, 2}, {7, 3}, {5, 4, 1} remplissent chaque boîte exactement : OPT = 3.
Le problème est NP-complet : pas d'algorithme exact polynomial connu. On propose FFD (trier par taille décroissante puis First-Fit), garanti à 11/9 OPT + 6/9. Sur les trois instances ci-dessus FFD trouve l'optimum.
Deux instances où l'ordre d'arrivée fait perdre une boîte.
Énoncé. Appliquer FF, BF puis FFD (capacité 10) à I = {5, 7, 3, 4, 8}, puis à I = {5, 7, 2, 4, 3, 8}.
| Algo | Boîtes | Total |
|---|---|---|
| FF | {5, 3} {7} {4} {8} | 4 |
| BF | {5, 4} {7, 3} {8} | 3 |
| FFD (8, 7, 5, 4, 3) | {8} {7, 3} {5, 4} | 3 |
Détail FF : 5 ouvre la boîte 1 ; 7 ne rentre pas (12), boîte 2 ; 3 rentre dans la boîte 1 (8) ; 4 ne rentre ni dans la 1 (12) ni dans la 2 (11), boîte 3 ; 8 ne rentre nulle part, boîte 4. Détail BF : pour le 3, les boîtes 1 (charge 5) et 2 (charge 7) conviennent, on prend la plus chargée, la 2, ce qui laisse de la place au 4 dans la 1. OPT = 3 : FF perd une boîte.
| Algo | Boîtes | Total |
|---|---|---|
| FF | {5, 2, 3} {7} {4} {8} | 4 |
| BF | {5, 4} {7, 2} {3} {8} | 4 |
| FFD (8, 7, 5, 4, 3, 2) | {8, 2} {7, 3} {5, 4} | 3 |
Somme = 29, borne basse 3, et FFD l'atteint : OPT = 3. FF et BF ratent l'optimum ici parce qu'ils rangent le 7 et le 8 avant d'avoir vu les petits items qui les complètent. FFD place les gros d'abord.
Aucun algorithme glouton n'est optimal, mais trier avant de placer change beaucoup. Et un algorithme peut gagner sur une instance (BF sur la première) et perdre sur une autre.
Transformer un rapport d'approximation en nombre de boîtes maximal.
Énoncé. Pour une instance d'optimum OPT = 3 puis OPT = 4, combien de boîtes au plus utilisent FF (1,7 OPT) et FFD (11/9 OPT + 6/9) ?
FF : 1,7 x 3 = 5,1, donc au plus 5 boîtes. FFD : 11/9 x 3 + 6/9 = 33/9 + 6/9 = 39/9 = 4,33, donc au plus 4 boîtes.
FF : 6,8, donc au plus 6. FFD : 44/9 + 6/9 = 50/9 = 5,55, donc au plus 5.
Avec OPT = 3, FF a utilisé 4 boîtes, sous la garantie de 5. La borne est un pire cas, pas ce qu'on observe. On prend l'entier inférieur car un nombre de boîtes est entier.
Ex1, Ex2 (a) et Ex2 (b) des slides.
Le 4 n'appartient qu'à S3 et le 2 qu'à S4 : ils sont forcés et couvrent 2, 3, 4, 5, 6. Il reste le 1, couvert par S1 ou S5. Minimum = 3, par exemple {S1, S3, S4}. Glouton : S3 (3 nouveaux), puis S4 ({2, 6}), puis S1 : 3 ensembles, optimal.
(Le slide nomme deux ensembles S2 ; on les renomme.) Le 4 n'est que dans D, qui couvre aussi le 1. Il reste {2, 3, 5, 6} qu'aucun ensemble seul ne couvre : OPT = 3. Glouton : A (ou C) en premier avec 3 éléments, puis D, puis C ou E : 3 ensembles, optimal.
Le 4, le 6 et le 2 ne sont respectivement que dans S1, S3 et S4, qui couvrent tout : OPT = 3 avec {S1, S3, S4}. Glouton : S2 d'abord (3 nouveaux), mais il faut ensuite S1, S3 et S4 quand même pour couvrir 4, 6 et 2. Total 4. Le glouton n'est pas optimal, et S2 est inutile dans la solution optimale.
Repérer les éléments couverts par un seul ensemble donne les ensembles forcés, et suffit souvent à trouver l'optimum à la main.
Pourquoi rien ne s'éteint à l'heure de pointe ?
Énoncé. Réseau de la page (routeurs A à F, liens A-B, B-C, D-E, E-F, A-D, B-E, C-F de capacité 2). Demandes A vers C et D vers F. Appliquer LL-SP. Puis ajouter la demande A vers F.
A vers C : A-B-C. D vers F : D-E-F. Charges (chemins par nœud) : A 1, B 1, C 1, D 1, E 1, F 1. Tous à égalité, on prend A par ordre alphabétique.
A : extrémité d'une demande, infaisable. B : les demandes se reroutent, A vers C par A-D-E-F-C (4 sauts) et D vers F reste D-E-F ; les liens D-E et E-F portent 2 chemins, capacité respectée. B dort. Les essais suivants (C, D, E, F) échouent : C et D, F sont des extrémités, et éteindre E couperait D vers F. Résultat : 5 routeurs actifs sur 6.
Le chemin A-B-C-F charge A-B et B-C à 2. Tout retrait de nœud force un détour qui dépasse la capacité 2 d'un lien : aucun routeur ne peut dormir. Rien n'est économisé : c'est l'heure de pointe.
LL-SP est une heuristique : l'ordre d'essai (par charge croissante) peut rater une meilleure solution. Sans garantie d'approximation (problème non approximable), on ne sait pas de combien.
07 · Réviser
Le QCM tire un échantillon au hasard dans le pool ; chaque réponse est corrigée et expliquée.
Entraîneur Pour un QCM qui s'adapte à ton niveau, revient sur tes erreurs et explique chaque réponse avec une fiche illustrée : s'entraîner sur ce chapitre.
Pool de 24 questions. Tire un échantillon au hasard, correction immédiate et explication à chaque réponse.