Équilibrage de charge des serveurs Web

Ajouter des liens
Un article de Wikipédia, l'encyclopédie libre.
Articles principaux : Répartition de charge et Serveur Web.

L’équilibrage de charge des serveurs Web, ou répartition de charge des serveurs Web, regroupe l’ensemble des mécanismes utilisés pour distribuer les requêtes HTTP sur de multiples serveurs Web.

Cette pratique est devenue indispensable depuis l’explosion du trafic du World Wide Web. L’évolution des usages de l’Internet, passant d’une infrastructure de communication à une infrastructure de services électroniques, peut entrainer des congestions et des temps de réponses élevés. Les systèmes Web, éléments stratégiques du World Wide Web, doivent pouvoir absorber cette charge. Cela a entrainé une évolution des architectures, destinée à apporter plus de scalabilité, de disponibilité et de performances.

Basées sur les propriétés du protocole HTTP, en particulier sur le système de requêtes/réponses, différentes approches sont étudiées pour répondre à l’équilibrage de charge des serveurs Web. Les approches architecturales s’intéressent à l’agencement des serveurs informatiques entre eux, ainsi qu’à la pertinence d’utiliser un élément central. Les approches du routage s’intéressent aux différentes manières de transférer les paquets des clients Web vers les serveurs, et ce selon deux axes. D’une part à travers les différentes couches réseaux du modèle OSI, et d’autre part à travers les différents équipements traversés par une requête HTTP. Les travaux sur les algorithmes tendent à définir un algorithme optimal de sélection du serveur le plus apte à traiter la requête HTTP dans un système Web. Cette recherche d’algorithme s’effectue dans plusieurs directions : prise en compte ou pas du contenu de la requête, prise en compte ou pas des informations des clients et/ou des serveurs, algorithme statique ou dynamique.

Contexte[modifier | modifier le code]

Évolution des usages[modifier | modifier le code]

L'Internet subit de profonds changements en passant d'une infrastructure de communication à un média de gestion d'une multitude de services[1]. Avec la croissance rapide du stockage de l'information dans les serveurs Web du monde entier, rechercher et obtenir une donnée est devenu un comportement commun[2]. L'explosion du trafic sur le World Wide Web a entrainé une rapide augmentation du nombre de requêtes sur les sites Web populaires[3],[4],[5]. La plupart des services fournis par ces sites peuvent ainsi recevoir un nombre très important de connexions des clients dans une période très courte[2]. De plus, le trafic Internet en général et du World Wide Web en particulier a augmenté de manière exponentielle, et cette croissance est amenée à continuer[6].

Ce trafic grandissant peut entrainer des congestions importantes du réseau informatique[3],[2],[6] et des temps de réponses élevés[2],[4]. Ces perturbations peuvent avoir pour conséquence une instabilité du site[2] et du service pour les utilisateurs[4]. Pour un site Web populaire, la congestion réseau et la surcharge des serveurs peuvent amener à des problèmes sérieux dans l'avenir[6].

Ces changements profonds de l'Internet placent le serveur Web au centre d'une infrastructure de services électroniques[1],[7] et d'applications critiques[8], augmentant les exigences en termes de qualité de service, de disponibilité et de fiabilité dans un environnement imprévisible, rapide et très dynamique[1],[7],[8]. Les systèmes Web doivent être capables de démarrer petit et de grossir avec l'augmentation de la demande[7], créant un besoin de serveurs Web plus nombreux et plus puissants capables de servir les utilisateurs Internet[9]. L'augmentation croissante de la demande pour des serveurs Web de qualité est aujourd'hui incontestable[10].

Évolution des architectures[modifier | modifier le code]

L'amélioration de la performance des serveurs Web et la garantie de la fiabilité et de la disponibilité d'un site Web sont des notions importantes[2]. C'est pourquoi il arrive un moment ou soit le serveur Web doit être renforcé, soit la charge doit être répartie entre plusieurs serveurs[11]. Mais les sites Web populaires ne peuvent pas faire confiance à un seul serveur puissant pour faire face à la charge de requêtes toujours en augmentation[12]. La scalabilité et la disponibilité peuvent être fournis par une architecture Web qui régule les requêtes clientes à travers différents serveurs de manière transparente[12]. Dès lors comment fabriquer une grappe de serveurs Web qui traite et répond facilement aux requêtes devient un problème majeur[2].

Par le passé la seule solution pour élargir la capacité serveur était de remplacer l'ancien serveur par un nouveau. Perdre l'investissement dans l'ancien serveur pour en racheter un autre est une solution à court-terme et couteuse. Une solution à long terme passe par une scalabilité incrémentale qui fournit la possibilité de croitre graduellement avec la demande[9]. Pour construire des serveurs Web évolutifs, les constructeurs et les sites Web populaires se sont massivement tournés vers les architectures distribuées[13],[14],[15]. Les grappes de serveurs Web sont ainsi devenues l'une des principales solutions pour accroitre la disponibilité et éviter la surcharge d'un serveur seul[2].

Mais, alors que le World Wide Web peut apparaître comme possédant une scalabilité intrinsèque à travers la distribution des ressources sur des serveurs décentralisés, il existe des exemples où cette forme de distribution de charge est couteuse[16]. D'où l'importance d'un bon équilibrage de charge, qui peut être défini comme le processus de distribution des requêtes sur différents serveurs pour fournir un meilleur temps de réponse[17].

Précédent de la NCSA[modifier | modifier le code]

Logo de la NCSA
Logo de la NCSA

Le serveur Web de la NCSA subit un pic de charge, entre octobre et , qui surpassa sa capacité à répondre. La première solution fut d'utiliser un serveur informatique plus puissant qui ne tint pas la charge en . La NCSA a alors déterminée que la seule solution viable à long terme passait par une distribution de charge multi-serveurs[18].

La NCSA possédait deux solutions au problème de charge de son serveur Web : diviser l'arborescence à travers différents systèmes, chacun répondant à un nom d'hôte unique et traitant une partie de l'arbre. Cette solution requérait beaucoup de manipulations et entrainerait la cassure de liens existants, entrainant une grande complexité et un impact sur la communauté utilisateur. La deuxième solution était de partager l'ensemble des documents à travers plusieurs serveurs, chacun répondant à un nom d'hôte commun. Cette solution permettait de gérer la sollicitation croissante des serveurs tout en ayant peu d'impact sur la communauté utilisateurs[19].

L'architecture informatique mise en place permit à la NCSA d'augmenter dynamiquement la capacité des serveurs Web. L'équilibrage de charge élimina la plupart des points individuels de défaillance lié à l'implémentation d'un serveur unique. La stabilité et la fiabilité du système est ensuite assurée par l'ajout de nouvelles machines de manière transparente pour les utilisateurs. Cet équilibrage de charge des serveurs Web allait pouvoir être utilisé comme modèle pour d'autres implémentations[20].

Spécificités du serveur Web[modifier | modifier le code]

Le but d'un serveur Web est de stocker une information et de répondre aux requêtes clientes[3]. Pour récupérer une information du Web, le nom contenu dans l'URL doit être associé à une adresse IP, une adresse MAC et une localisation de l'objet[3],[21]. Chaque association offre ainsi une opportunité de rediriger la requête vers la machine la plus appropriée[21]. Cette nécessité de diriger les connexions entrantes vers des hôtes individuels représente justement un important défi[13].

Par ailleurs, le protocole de communication entre les clients et les serveurs Web est fourni par le protocole HTTP, qui est un protocole basé sur un système de requêtes/réponses[8] et est utilisé pour le World Wide Web depuis les années 1990[22]. Ce protocole étant sans état, une connexion TCP doit donc être établie pour chaque objet d'une page Web. Chaque requête peut être routée de manière indépendante, permettant ainsi un équilibrage de charge des serveurs Web[11].

Architecture[modifier | modifier le code]

Article connexe : Architecture (informatique).

Les services Web peuvent croitre par scalabilité verticale, en remplaçant des serveurs informatiques surchargés par de plus gros serveurs, ou ils peuvent croitre par scalabilité horizontale en ajoutant des serveurs supplémentaires[7] en fonction de la charge à absorber[11]. Mais l'utilisation des serveurs isolés est très risquée pour fournir des services fiables et flexibles[10]. De plus avec un unique serveur Web, un pic de requêtes important va facilement générer de la congestion et des erreurs logiciels. Il y a donc un besoin d'avoir plus de serveurs performants pour servir la demande croissante des utilisateurs[2].

De ce constat a été proposée une architecture basée sur plusieurs serveurs Web, appelée grappe de serveurs Web[2]. Cet ensemble de serveurs attachés ensemble pour agir comme une seule unité permet aux fournisseurs d'ajouter progressivement de nouvelles ressources peu chères afin de partager la charge de travail et ainsi d'augmenter la performance générale du système[9],[2] de manière transparente pour le client[3]. N'importe quel serveur d'application peut être mis en grappe s'il respecte ces deux propriétés[9] :

  1. l'application ne doit pas maintenir d'état avec le serveur. Toute information d'état doit être maintenue par le client, afin d'éviter les problèmes de cohérence avec les états distribués
  2. les transactions client/serveur doivent être relativement brèves et fréquentes, afin de pouvoir établir facilement des statistiques de distribution des paquets qui serviront à la répartition de charge

Ce type d'architecture représente une approche populaire utilisée pour fournir des services Web fiables, flexibles, efficaces et disponibles[10],[23]. Les avantages des solutions distribuées en grappes sont la haute puissance de calcul ainsi que la tolérance aux pannes. Les inconvénients sont les difficultés à ordonnancer et équilibrer chaque entité distribuées[10].

Un système de serveurs Web distribués comprend plusieurs serveurs Web ainsi qu'un mécanisme de répartition des requêtes sur les serveurs, ces derniers pouvant être répartis de manière locale ou géographique[24]. L'équilibrage de charge des serveurs informatiques dans une grappe est le processus de distribution des requêtes sur différents serveurs[17]. Cette répartition des requêtes est indispensable pour obtenir un temps de réponse réduit ainsi qu'une optimisation de l'utilisation des ressources informatiques[23],[17]. Dans une répartition locale des serveurs, le processus de distribution des requêtes est facilitée par la proximité en termes de réseau informatique. Alors que dans une répartition géographique ou globale des serveurs, le processus de distribution est plus complexe à cause des contraintes liées à la connectivité Internet entre les serveurs[25].

Les différentes architectures informatiques permettant l'équilibrage de charge des serveurs Web peuvent se distinguer par le niveau d'abstraction et la gestion de leur adresse IP[26] :

  • les grappes de serveurs Web, où une seule adresse IP est visible par le client et portée par un élément central
  • les grappes de serveurs Web virtuelle, où une seule adresse IP est visible par le client mais sans élément central
  • les systèmes distribués et serveurs miroirs, où toutes les adresses IP des serveurs Web sont visibles par les clients

Grappe de serveurs Web[modifier | modifier le code]

Une grappe de serveurs Web désigne un ensemble de serveurs informatiques hébergés localement et qui sont interconnectés à travers un réseau haut-débit[27],[7]. De plus, cet ensemble de serveurs doit apparaitre comme un hôte unique pour le monde extérieur et les utilisateurs[24],[11],[28]. Une seule machine, dont l'adresse est publiée à travers le DNS, a la responsabilité de la répartition de charge à travers la grappe de serveurs[7]. Dans une grappe de serveurs, tous les serveurs contiennent la même donnée. Chaque serveur a donc la possibilité de prendre en charge la requête d'un client[29]. Cette approche peut potentiellement améliorer les performances de débit et fournir au système Web une haute disponibilité et une bonne scalabilité[3],[4] car elle rend possible l'ajout de nouvelle machines sans interruption de service[11]. Elle peut également fournir une meilleure fiabilité par l'utilisation d'algorithmes de répartition de charge appropriés[11].

Une grappe de serveurs Web est composée d'un ordonnanceur, le répartiteur, situé entre les clients et les serveurs Web constitués de différents matériels ou systèmes d'exploitation[29]. Ce répartiteur est configuré avec une adresse IP particulière, l'adresse de la grappe de serveurs Web[23],[30]. Ainsi c'est le répartiteur qui reçoit les requêtes et les redirigent vers un des serveurs de la grappe[30],[14],[29] grâce à l'implémentation d'un algorithme d'équilibrage de charge[29],[28]. Il s'agit donc d'une approche centralisée qui n'est pas intrinsèquement élastique car le répartiteur central peut devenir un goulot d’étranglement en cas de forte charge[13]. Cependant, pour améliorer la fiabilité, un répartiteur de secours peut être déployé pour prendre le relais du répartiteur principal en cas de panne[23].

Grappe de serveurs Web

Grappe de serveurs Web virtuelle[modifier | modifier le code]

Cette approche est basée sur une architecture informatique complètement distribuée sans équipement centralisé en amont. Comme la grappe de serveurs Web, le système apparait comme une seule entité aux yeux du monde extérieur. La différence vient du fait que l'adresse IP de la grappe n'est plus portée par le répartiteur mais par chacun des serveurs, qui possèdent ainsi tous la même adresse IP[31],[23]. Chaque machine de la grappe aura la responsabilité de traiter ou non les requêtes qui lui arrivent[23].

Grappe de serveurs Web virtuelle

Systèmes distribués[modifier | modifier le code]

Ce type d'architecture informatique comprend un ensemble de serveurs Web répartis et qui sont visibles de manière individuelle par les clients, contrairement aux grappes de serveurs qui ne présentent qu'une seule adresse IP. Il n'y a pas de répartiteur central, le routage des requêtes peut être effectué par un serveur DNS accompagné éventuellement d'un deuxième niveau de routage effectué par les serveurs eux-mêmes[31].

Systèmes Web distribués

Serveurs miroirs[modifier | modifier le code]

Une approche particulière des systèmes distribués est la réplication en miroir d'un site Web en différents emplacements du monde. La page originale du site contient la liste des serveurs miroirs, ce qui permet à l'utilisateur de choisir le serveur en fonction de son emplacement[6]. Ce type d'approche pour la duplication de contenus populaires est chose commune[25]. Par exemple, apache.org maintient 246 sites miroirs à travers le monde (Liste des serveurs miroirs Apache).

Ce type de système peut réduire le temps de réponse utilisateur et réduire le trafic Internet[25]. Mais cette solution a plusieurs inconvénients, en particulier la non-transparence ainsi que le manque de contrôle sur la distribution des requêtes par le système Web[3],[6].

Mécanismes de routage[modifier | modifier le code]

Article connexe : Routage.

Lorsqu'un site est hébergé sur plusieurs serveurs informatiques, il faut sélectionner le serveur qui traitera la requête du client[32]. De plus pour le bon fonctionnement du système Web il faut des mécanismes de routage qui fournissent de la scalabilité, un véritable équilibrage de charge et une haute disponibilité dans un environnement constamment en mouvement[4].

La plupart des méthodes de grappes de serveurs existantes utilisent un répartiteur central qui reçoit les requêtes de l'Internet et les distribue au meilleur serveur de la grappe[23]. L'utilisation d'un répartiteur permet d'avoir un contrôle total sur la requête entrante et de masquer le routage à travers de multiples serveurs par l'utilisation d'une adresse IP publique unique, portée par le répartiteur[33]. Selon leur couche de travail au sens du modèle OSI, les répartiteurs sont classés en couche 4 (couche transport) ou couche 7 (couche application). Les répartiteurs couche 4 distribuent les requêtes en se basant sur l'adresse IP et le port du client, alors que les switchs niveau 7 peuvent effectuer une répartition en fonction du type et du contenu de la requête reçue[14],[34]. Par ailleurs, selon la technologie employée le répartiteur apparaitra aux serveurs de la grappe comme un commutateur, qui ne traite que les données entrantes, ou comme une passerelle, qui traite les données entrantes et sortantes[30],[34].

Mais il existe d'autres méthodes qui n'ont pas besoin de répartiteur central pour assurer le routage des requêtes. Une grappe de serveurs basée sur un nom d'hôte unique peut être implémentée avec un serveur DNS. Dans ce cas, le répartiteur est en fait un serveur DNS autoritaire qui répond avec l'adresse IP du serveur suivant dans la grappe[35],[33]. De même la distribution des requêtes sur des serveurs miroirs ne nécessite pas de répartiteur[35]. C'est également le cas pour des mécanismes réseaux tels que le DPR (Distributed Packet Rewriting) et le ONE-IP[35].

La décision de routage des paquets peut être prise tout au long du trajet de la requête. Les différents mécanismes de routage peuvent donc être classés en fonction de l'élément qui assure la redirection des requêtes[21],[32] :

  • au niveau du réseau, par l'intermédiaire d'un répartiteur ou de protocoles multicast ou anycast
  • au niveau du client Web qui initie la requête, éventuellement par l'intermédiaire du DNS
  • au niveau du serveur Web qui fait partie d'une grappe de serveurs ou est placé en amont

Routage par le réseau[modifier | modifier le code]

Le routage par le réseau peut se faire à plusieurs niveaux : au niveau de la couche transport, entre la couche liaison et la couche réseau ou au niveau de la couche application[21],[36].

Routage : différentes couches

L'élément qui assure le routage est appelé répartiteur[21],[4]. Ce répartiteur à un rôle central sur le routage des requêtes et leur distribution aux serveurs[4]. Habituellement le routage se fait au plus près des serveurs. Ainsi la capacité réseau entre l'ordonnanceur et les serveurs est élevée et les informations de charge des serveurs sont fiables[21].

Couche 2[modifier | modifier le code]

Dans le routage au niveau 2, les serveurs sont identiques au-delà de la couche 2 du modèle OSI. Ils ont un niveau 2 unique, chaque serveur a une adresse MAC, mais une couche 3 identique, donc une même adresse IP[30]. Avec ce mécanisme le routage est effectué entre la couche liaison et la couche réseau, et tous les serveurs ont la même adresse IP que l'adresse IP virtuelle (VIP) portée par le routeur et présentée au client[37]. Toutes les requêtes reçues par les serveurs ne sont traitées que par le serveur adéquat en se basant sur une fonction de hachage liée à l'adresse source du client[5],[38].

ONE-IP

Dans ONE-IP, un mécanisme de broadcast est utilisé pour envoyer une requête entrante sur toutes les machines de la grappe de serveurs. Les machines ont des adresses MAC et des adresses IP primaires différentes mais une adresse IP secondaire identique. Un filtre est mis en place sur la machine qui fait qu'une seule machine va traiter le paquet dans les couches réseaux supérieures[35]. Pour que ce mécanisme fonctionne, le routeur en amont des serveurs doit modifier l'adresse MAC de destination des paquets entrants par une adresse MAC de broadcast. Cela requiert d'avoir une entrée permanente dans le cache ARP associant l'adresse MAC de broadcast à l'adresse IP virtuelle du routeur[35],[21].

Routage couche 2 par ONE-IP
Clone Cluster

Afin d'éviter une modification du routeur en entrée du réseau, cette approche propose que toutes les machines aient la même adresse IP et la même adresse MAC. Toutes les machines partagent le même segment LAN, ainsi tous les paquets sont vus par toutes les machines. Un filtre sur chaque machine est utilisé pour sélectionner les requêtes à traiter dans les couches réseaux supérieures[38],[39].

Routage couche 2 par Clone Cluster

Cette approche nécessite une modification des serveurs afin de ne pas prendre en compte les requêtes ARP gratuites, utilisées notamment pour vérifier que deux adresses IP ne coexistent pas sur le réseau. Une deuxième modification est nécessaire afin de résoudre un problème lié à ICMP : puisque tous les serveurs ont la même MAC et la même IP, une réponse UDP ou ICMP à un paquet envoyé par l'un des membres sera reçu par tous les serveurs. Puisque les autres serveurs n'ont pas généré de paquet, un message ICMP "port inatteignable" sera envoyé. La modification consiste à empêcher l'envoi de ce paquet d'erreur ICMP[38].

Critiques

Ce type de routage évite d'avoir un goulot d'étranglement et un point individuel de défaillance représenté par le répartiteur. Par contre, il nécessite que toutes les machines soient sur le même segment réseau et l'algorithme d'équilibrage de charge est limité à une fonction de hachage[39]. De plus ces solutions utilisent le mécanisme de broadcast et envoient donc les paquets à tous les serveurs, induisant une charge de travail supplémentaire sur ces derniers[40],[21]. Enfin, ces solutions nécessitent une modification des serveurs pour y implémenter les filtres nécessaires au routage des paquets[40].

Couche 4[modifier | modifier le code]

Dans le routage couche 4, correspondant dans le modèle OSI à la couche transport, chaque serveur à une adresse IP unique[21]. Le routage réalisé au niveau de la couche 4 par un répartiteur distribue les requêtes en se basant sur l'adresse IP et le port TCP sources et destinations[15]. Afin de s'assurer que tous les paquets d'une connexion existante d'un client arrivent au même serveur, une table de session est maintenue par le répartiteur[34]. À noter que la capacité réseau du répartiteur doit être supérieur à celle de chacun des serveurs du cluster[37]. De plus, chaque paquet doit être inspecté par le répartiteur et la modification des champs du paquet IP comme le contrôle de redondance cyclique et le temps de vie induisent des coûts de traitement supplémentaires[21].

Simple réécriture du paquet

Dans cette approche le répartiteur route le paquet du client vers le serveur en modifiant l'adresse IP du paquet[33]. En effet tous les paquets destinés à l'adresse IP logique du répartiteur sont inspectés et l'adresse de destination est remplacée par l'adresse IP d'un des serveurs de la grappe de serveurs[21],[5]. Puis le serveur renvoie la réponse directement au client et remplace l'adresse source du paquet par l'adresse source du répartiteur[5].

Routage couche 4 par simple réécriture du paquet

Cette solution est transparente pour le client mais nécessite une modification du noyau des serveurs Web puisque le remplacement de l'adresse IP s'effectue au niveau TCP/IP[5],[33]. D'un autre côté, cette approche fournit une solution de haute disponibilité car en cas de panne d'un serveur, son adresse peut être supprimé de la table du répartiteur afin qu'il ne reçoive plus de requêtes des clients[33].

Double réécriture du paquet

Ce type de routage est aussi basé sur la présence d'un répartiteur central qui va recevoir les requêtes des clients et les distribuer sur les serveurs du cluster. La différence avec le routage par réécriture simple et qu'ici la réécriture par le répartiteur se fait également pour les paquets en provenance des serveurs et à destination des clients. Ce mécanisme de double réécriture est à la base du mécanisme de Network Address Translation (NAT)[41].

Routage couche 4 par double réécriture du paquet

Pour que le mécanisme soit transparent, le répartiteur doit modifier les adresses IP de tous les paquets dans les deux sens. De plus, les transactions doivent être routées vers le même serveur[37].

Critiques

Les solutions basées sur la double réécriture par le répartiteur ont l'inconvénient majeur de solliciter l'équipement à la fois pour la réécriture des paquets entrants et des paquets sortants, qui sont généralement plus nombreux[36]. Ces solutions ont par contre l'avantage que les serveurs peuvent être sur des réseaux locaux différents[42].

Les solutions basées sur la simple réécriture du paquet doivent absorber la charge liée à la réécriture par le répartiteur mais réduisent le risque de goulot d’étranglement en reportant la réécriture des nombreux paquets sortants sur les serveurs Web[36]. Par contre, ils nécessitent une modification au niveau du système d'exploitation serveurs qui doivent prendre en charge la réécriture des paquets sortants[43]

Couche 7[modifier | modifier le code]

Le routage à la couche 7, ou couche application selon le modèle OSI, permet d'effectuer une distribution des requêtes en prenant en compte le contenu HTTP de cette requête, fournissant ainsi des stratégies de routage plus flexibles. En contrepartie, la charge générée sur le répartiteur est plus importante[15],[44],[25].

Passerelle TCP

Dans cette architecture, un proxy implémenté sur le répartiteur va jouer le rôle d'intermédiaire réseau entre les clients et les serveurs. Le proxy maintient une connexion persistante avec chacun des serveurs Web par laquelle vont transiter les paquets dans les deux sens, du client vers le serveur et inversement[44],[45]. Le proxy fonctionne selon deux modes : un mode de transfert des paquets et un mode de contrôle des paquets. Les deux modes sont activés pour les requêtes des clients, mais généralement seul le mode de transfert est activé pour les réponses des serveurs[46].

Epissage TCP

Ce mécanisme se veut être une amélioration de la passerelle TCP, lourde en termes de charge de travail car chaque paquet de requête/réponse doit être inspecter jusqu'à la couche application[44],[45]. L'épissage TCP est une interface de programmation applicative qui va détecter le passage en mode transfert du proxy et gérer ces opérations directement au niveau de l'espace noyau plutôt qu'au niveau de l'espace utilisateur[47]. Ainsi seules les opérations propres à la couche application, celles du mode de contrôle, seront traités dans l'espace utilisateur[45]. L'implémentation de cette technique permet dans la plupart des cas d'éviter le goulot d'étranglement que représente le simple transfert des paquets du client au serveur, qui ne nécessitent pas d'opérations particulières au niveau de la couche application[48].

Routage couche 7 par aller retour (Passerelle TCP et Epissage TCP)
Remise TCP

Le principe de cette approche est la remise au serveur sélectionné de la connexion TCP établie entre le client et le répartiteur. Une fois remise, le répartiteur transfert les paquets du client vers le serveur, et le serveur répond directement au client sans passer par le répartiteur[49],[50],[51]. Cette remise est transparente à la fois pour le client et pour les applications du serveur Web. Par contre, elle nécessite une modification de la gestion du réseau par le noyau du système d'exploitation qui doit accepter de prendre en charge une connexion TCP pour laquelle il n'a pas réalisé l'initialisation[49]. Cette approche améliore la performance du répartiteur qui n'a plus à traiter les paquets jusqu'à la couche application, puisqu'il ne fait que transférer les paquets au niveau TCP, majoritairement des paquets d'acquittement, une fois la remise effectuée à un serveur[49],[50].

Routage couche 7 par aller simple (Remise TCP)
Critiques

Les répartiteurs couche 7 qui permettent aux serveurs de répondre directement aux clients permettent d'avoir une plus grande scalabilité[43]. Ainsi, le mécanisme de remise TCP offre plus de scalabilité que le mécanisme d'épissage TCP[50].

Par contre, la réponse directe du serveur au client nécessite des modifications au niveau du système d'exploitation du serveur et du répartiteur. De plus, la gestion des requêtes et des réponses permet de bénéficier de fonctionnalités de Cache web prises en charge directement par le répartiteur[43].

Routage par le client[modifier | modifier le code]

Le routage client peut être appliqué pour n'importe quelle architecture Web répliquée même si les nœuds ne sont pas du tout coordonnés. Le routage peut se faire par le client Web ou par le serveur mandataire côté client[24].

Les mécanismes de routage par le client peuvent être classés en deux groupes : ceux qui sont transparents et ceux qui ne le sont pas[21].

Routage DNS[modifier | modifier le code]

À la demande de la DARPA, Jon Postel et Paul Mockapetris ont conçu le « Domain Name System » en 1983 et en écrivirent la première réalisation. La plupart des liens Web utilise un nom canonique (CNAME) plutôt qu'une adresse IP. La correspondance entre le CNAME et l'IP est réalisée par un serveur DNS[11]. En plus de fournir l'adresse IP, le DNS spécifie également une période de validité ou Time to live (TTL) de mise en cache[52]. Le routage DNS est simple à implémenter mais possède deux défauts. Premièrement, la mise en mémoire (cache) des adresses IP dans les clients et les serveurs DNS secondaires conduira à une charge non équitablement répartie sur les serveurs. Deuxièmement, si un serveur n'est plus disponible, il n'y a pas de moyen automatique pour le serveur DNS de le savoir et d'arrêter d'y envoyer des requêtes[35]. Cette approche est transparente pour le client[21].

Schéma d’approche basée sur le DNS
Algorithme avec TTL constant

Une mécanisme utilisé pour la distribution des requêtes est le système DNS round-robin qui résout un nom d'hôte unique en plusieurs adresses IP[23]. Un nom de domaine est associé à plusieurs adresses IP correspondant à chaque serveur du cluster. Cette approche, pour la première fois mise en œuvre par le NCSA, afin de gérer l'augmentation du trafic sur son site, était dans le cadre d'un architecture homogène[53]. Très simple à mettre en œuvre, il pose cependant un problème fondamental d'efficacité en raison de la mise en cache sur les DNS locaux. Tant que la valeur du Time to live (TTL) n'est pas expiré, les futures demandes n'accèdent pas au cluster DNS ce qui génère une répartition déséquilibrée de la charge[54]. Cet algorithme ne tenant compte ni de la capacité ni de la disponibilité des serveurs (algorithme apatride), aucun mécanisme ne peut arrêter les clients d'essayer d'accéder au serveur par son adresse en cache[55]. La connaissance de l'état des serveurs est essentielle pour un système hautement disponible afin d'exclure les serveurs inaccessibles en raison de défauts ou de congestion. Combiner la politique basée sur le DNS avec un mécanisme d'alarme évite toute surcharge du système serveur-web[56].

L'algorithme lbnamed exige que le DNS définisse la valeur du TTL à zéro. Ainsi, le DNS, après avoir reçu une demande d'adresse, va sélectionner le serveur le moins chargé et inhiber l'adresse mis en cache sur les serveurs de noms[57]. La connaissance de l'état client est également fort intéressante, deux types d'informations peuvent provenir du côté client : la charge qui arrive au système serveur-web et la localisation géographique[57]. L'index de poids de charge caché mesure le nombre moyen de requêtes de données envoyées à partir de chaque domaine connecté à un site web, au cours de la période de mise en cache (TTL)[56]. Cet ordonnancement DNS, qui utilise principalement ces informations pour attribuer des requêtes au serveur le plus approprié, essaye d'identifier le domaine demandeur et le poids de charge caché imposée par ce domaine[56]. Un exemple de cet algorithme est le Round robin multi niveau. Ces algorithmes basés sur la localisation géographique ne fonctionne pas bien si le mappage URL-IP est caché par les serveurs de noms intermédiaires. Pour les faire fonctionner, le cluster DNS définit le TTL à zéro, cependant cette solution est limitée par les serveurs de noms non coopératifs[57]. Les algorithmes qui utilisent à la fois la connaissance de l'état client et de l'état serveur sont les plus efficaces. L'acquisition de ces informations d'état du système nécessaire exige des estimateurs efficaces, plusieurs approches dynamiques ont été suggérées[57].

Algorithme avec TTL adaptatif

Ces algorithmes utilisent un processus de décision en deux étapes. Tout d'abord, le DNS sélectionne le serveur web de manière similaire aux algorithmes de poids de charge cachés, puis il choisit la valeur TTL appropriée. Les demandes d'adresses provenant de domaines très populaire recevront un TTL inférieur à celui des requêtes en provenance de petits domaines[58]. Pour équilibrer les demandes entre les systèmes de serveurs Web répartis, les algorithmes avec TTL adaptatifs sont les plus robustes et efficaces, malgré des charges asymétriques et serveurs de noms non coopératives. Ces algorithmes, cependant, ne considèrent pas le client à distance de serveur à prendre des décisions de planification[57].

Par le client Web[modifier | modifier le code]

Le client Web peut jouer un rôle actif dans le routage s'il a connaissance des différents serveurs Web répliqués[59]. Une fois que le client Web a reçu la requête de l'utilisateur, il est capable de sélectionner un serveur Web dans la grappe de serveurs et de lui soumettre la requête. Ce serveur Web est alors responsable du traitement de la requête[59].

La manière d'accéder au site de Netscape Communication à travers le navigateur Netscape a été le premier exemple d'architecture Web distribué dont le routage est géré par le client. Le mécanisme était le suivant : lorsque l'utilisateur accédait à la page d'accueil de Netscape (www.netscape.com), le navigateur sélectionnait un nombre aléatoire i entre 1 et le nombre de serveurs. Puis il envoyait la requête de l'utilisateur à l'adresse wwwi.netscape.com. Cette approche n'est généralement pas applicable, puisque le nombre de sites ayant le privilège de posséder leur propre navigateur pour répartir la charge est très limité. Par ailleurs la solution n'est pas flexible à moins de réinstaller le navigateur. Enfin, le mode de sélection aléatoire ne garantit pas la disponibilité du serveur et le bon équilibrage de charge[59]. Cette approche est non-transparente puisqu'elle nécessite une modification du navigateur du client[21].

L'approche du client intelligent vise à transférer certaines fonctionnalités du serveur vers le client. Les requêtes de l'utilisateur sont traitées à travers une applet Java, installée sur le client, qui connait les adresses IP des serveurs et peut les interroger pour connaitre leur statut et leur charge de travail. Ces informations sont ensuite analysées pour choisir le serveur le plus approprié. Les requêtes du client seront alors transférées à ce serveur. L'inconvénient majeur de cette approche est l'augmentation du trafic réseau lié aux messages de statut envoyés aux serveurs par le client[59],[5]. Cette approche permet de masquer au client les détails de la connexion vers les différents serveurs[5].

Par le serveur mandataire du client[modifier | modifier le code]

Le serveur mandataire est un autre élément d'Internet qui peut distribuer les requêtes clients vers les serveurs Web. Cependant toute implémentation d'un mécanisme de répartition de charge requiert des modifications du serveur mandataire qui n'est généralement pas géré par la même organisation que celle qui gère le site Web[60].

Routage par le serveur[modifier | modifier le code]

Ces techniques utilisent un mécanisme de répartition à deux niveaux. D'abord le DNS primaire du système Web attribue les demandes des clients aux nœuds de serveurs Web, puis, chaque serveur peut réaffecter une demande reçue à tout autre serveur du système[61]. Cette approche distribuée permet à tous les serveurs de participer à l'équilibrage de charge du système, en la couplant avec l'approche centralisée basée sur les DNS, elle permet de résoudre la plupart des problèmes d'ordonnancement de DNS[61]. Une solution repose sur la redirection de paquets, l'autre sur la redirection HTTP.

DPR[modifier | modifier le code]

Distributed Packet Rewritting (DPR) ou réécriture de paquet par serveur, utilise un mécanisme de Round robin pour planifier les demandes entre les serveurs web[62]. Le serveur accessible par une demande redirige la connexion à un autre serveur à travers un mécanisme de réécriture de paquets qui est transparent pour le client[63]. Avec DPR chaque machine du cluster a connaissance de la charge des autres serveurs. Les adresses IP de toutes les machines sont publiées, ainsi chacune peut recevoir des requêtes. Une requête entrante sur n'importe quelle machine sera dirigée sur la machine la moins chargée en utilisant le TCP hand-off[35] Cependant, le hand-off des connexions TCP est un problème complexe à résoudre et requiert que la machine d'origine qui a effectué le hand-off ait en mémoire la connexion jusqu'à ce qu'elle soit terminée[35]..

Redirection HTTP[modifier | modifier le code]

L'architecture du système World Wide Web (SWEB) utilise un politique DNS de Round Robin comme premier niveau de planification puis un système asynchrone distribué comme second niveau[63]. Chaque serveur web redirige les requêtes en fonction de la sélection du serveur qui minimise le temps de réponse de la demande du client, il s'agit d'une valeur estimée sur la base des capacités de traitement du serveur et de la bande passante/délai d'internet[63]. L'inconvénient de cette solution est que le routage est fait au niveau application, la requête doit donc remonter toute la pile de protocole[21]. Cette solution peut être intéressante lorsque le facteur limitant est le temps de traitement de la requête. Dans la plupart des cas, le serveur sera un goulot d’étrangement et cette solution n'est pas élastique[21].

Algorithmes de répartition[modifier | modifier le code]

Article connexe : Algorithme.

Les grappes de serveurs ont besoin d'une stratégie d'équilibrage de charge pour distribuer les requêtes vers l'un des serveurs de la grappe[2]. Plus précisément, la distribution des requêtes vers le serveur le moins chargé garanti que la requête sera toujours envoyée sur le serveur le plus à même de la traiter dans les meilleurs délais[35]. Les algorithmes d'équilibrage de charge ont pour but de répartir la charge entre les serveurs pour optimiser leur utilisation et diminuer le temps d'exécution des requêtes[64]. Il joue une part importante dans le temps de réponse au client ainsi que dans la disponibilité de la ressource[29].

À cause de la diversité croissante des profils de charge et des configurations des grappes de serveurs, il est très difficile de proposer un unique algorithme qui soit performant dans toutes les conditions[4]. En particulier, la variation des objets interrogés causera habituellement un déséquilibre de charge[2]. De même pour des requêtes qui ne représentent pas la même charge de travail, l'utilisation de la machine sera probablement inégale. La requête ne sera pas forcément envoyée au meilleur serveur possible[35].

Dans une architecture avec un répartiteur, ce dernier transfère la requête entrante à un serveur cible en se basant sur différentes stratégies pour équilibrer au mieux la charge[28],[65]. Ces stratégies peuvent être classifiées selon plusieurs critères[66],[29] :

  • avec ou sans connaissance du contenu de la requête HTTP
  • statique ou dynamique
  • avec prise en compte des informations du client et/ou du serveur
Couches du modèle OSI prise en compte par les différents algorithmes de répartition

Sans connaissance du contenu[modifier | modifier le code]

Algorithmes statiques[modifier | modifier le code]

Les algorithmes statiques distribuent les requêtes aux serveurs de la grappe sans utiliser les informations d'état de charge de ces serveurs[5]. Ils sont par conséquent très rapides et simples à implémenter mais ne sont pas optimaux car la non prise en compte de ces informations peut les amener à prendre de mauvaises décisions et conduire à un déséquilibre de la charge[67],[68],[29].

Aléatoire
Distribution aléatoire des requêtes sur les serveurs Web

Dans la répartition aléatoire, chaque requête entrante est envoyée à un serveur sélectionné aléatoirement. Cet algorithme est très rapide et il assure un bon équilibrage de charge sur une période de temps donnée. Par contre, si le nombre de requêtes est faible, la probabilité d'un déséquilibre de charge est forte[28],[66].

Round-Robin

L'algorithme de round-robin transfère chaque requête entrante au prochain serveur de la liste[66]. Tous les serveurs sont traités de manière égalitaire sans prendre en compte leur nombre de connexions entrantes ou leur temps de réponse[28],[69],[35].

Distribution round-robin des requêtes sur les serveurs Web

Contrairement au DNS Round-robin, la granularité est plus fine puisqu'elle se situe au niveau de la connexion réseau plutôt qu'au niveau de l'hôte. Cela évite les inconvénients liés au cache du DNS qui peut conduire à un déséquilibre de charge[28],[70]. Par contre, le mécanisme du Round-Robin peut engendrer un déséquilibre de charge si le temps des requêtes ou la capacité des serveurs sont différents. Ceci est dû au fait qu'ils ne prennent pas en compte la charge de travail des serveurs[2].

Round-robin à poids

L'algorithme de round-robin à poids est mis en place pour mieux gérer les serveurs ayant des capacités de traitement différents. Chaque serveur se voit assigner un poids qui indique sa capacité de traitement. L'ordonnancement par le répartiteur tiendra alors compte de ce poids pour transférer les requêtes aux serveurs[28],[71].

La répartition par round-robin à poids est plus efficace que par round-robin simple lorsque la capacité des serveurs est différente. Cependant, cela peut conduire à un déséquilibre si la charge des requêtes varie beaucoup. Il est possible que la majorité des requêtes lourdes soit toujours dirigée vers le même serveur[28],[70].

Algorithmes dynamiques[modifier | modifier le code]

Ces algorithmes sont dits dynamiques car ils ont besoin de collecter dynamiquement les informations des clients ou des serveurs pour déterminer vers quel serveur sera envoyée la requête du client[28],[69],[5]. Les informations doivent être accessibles au répartiteur et peuvent être récupérées par le protocole ICMP, par un agent installé sur les serveurs, par une inspection des paquets ou par une analyse du temps de réponse[69],[68],[35]. Les algorithmes dynamiques sont plus performants mais la charge réelle de serveurs Web est difficile à quantifier car variable et le transfert de ces informations alourdit grandement le réseau[67],[68],[29].

Informations du client

Du côté des informations clients, puisque le répartiteur n'a pas accès au contenu de la requête, il est limité aux informations des couches 4 et inférieures du modèle OSI contenues dans les paquets TCP et IP. Ces informations peuvent être utilisées pour équilibrer la charge en distribuant les requêtes des mêmes clients aux mêmes serveurs en utilisant par exemple une fonction de hachage appliquée à l'adresse IP du client[66].

Informations du serveur

Une première application d'utilisation des informations du serveur pour équilibrer la charge consiste à transférer les requêtes entrantes vers le serveur possédant le moins de connexions établies[69],[28]. Ce type de répartition est utile pour équilibrer la charge lorsque la charge des requêtes varie beaucoup et que les serveurs ont des performances comparables[28]. Si deux serveurs ont le même nombre de connexions, le serveur avec l'identifiant le plus petit sera choisi. Cela signifie que les nouvelles connexions dans un système vide arriveront toujours sur le même serveur[69].

Une deuxième application est de se baser sur la charge réelle du serveur, et pas seulement sur le nombre de connexions, pour optimiser la distribution des requêtes[72],[71].

Une autre application est l'exploitation du temps de réponse. Les requêtes entrantes seront en priorité distribuées aux serveurs possédant le temps de réponse le plus rapide[71].

Informations du client et du serveur

Les informations des clients et des serveurs peuvent être combinées pour rendre compatible l'équilibrage de charge avec un besoin fonctionnel. Des applications comme FTP ou SSL peuvent nécessiter l’existence d'une affinité du client avec le serveur, c'est-à-dire que les connexions d'un client donné soit redirigées sur le même serveur que la toute première connexion. Ce mécanisme nécessite le maintien d'une table de correspondance client/serveur par le répartiteur[73],[74],[75].

Avec connaissance du contenu[modifier | modifier le code]

Les algorithmes de répartition basée sur la connaissance du contenu des requêtes sont de plus en plus populaires dans les grappes de serveurs Web[76]. Ces algorithmes sont complexes car ils doivent inspecter le paquet reçu jusqu'à la couche HTTP avant de prendre une décision de routage[77]. Ils utilisent les informations ainsi récupérées dans plusieurs buts[78],[79],[80],[81] :

  • améliorer l’indexation des contenus dans le cache Web du serveur afin de réduire les accès disques
  • utiliser des serveurs spécialisés selon le contenu à servir (pages statiques, dynamiques, diffusion en flux, ...)
  • accroitre le partage de la charge entre les différents serveurs
  • améliorer l'affinité client/serveur à travers l'utilisation d'informations SSL et des témoins de connexions
  • améliorer la granularité de la distribution des requêtes en cas d'utilisation de la version 1.1 du protocole HTTP

Basés sur les informations du client[modifier | modifier le code]

Ces algorithmes examine toutes les couches de la requête HTTP reçue par le client. Les informations récupérées sont utilisées pour prendre une décision sur le routage de la requête[82].

Affinité du cache

Dans ce schéma, l'information client utilisée est le localisateur uniforme de ressource (URL). Une fonction de hachage est utilisée par le répartiteur sur l'URL demandée par le client afin de diriger la requête vers l'un des serveurs de la grappe[83]. L'avantage est une optimisation importante du cache Web du serveur puisqu'il reçoit un ensemble défini de requêtes. Par contre cela ne fonctionne que pour les contenus statiques[83]. L'inconvénient est l'absence de partage équitable de charge dû à la difficulté de définir une fonction de hachage qui prenne en compte la taille et la fréquence d'utilisation des contenus demandés. Cela peut conduire à des goulots d'étranglements lorsque les contenus les plus demandés se trouvent sur le même serveur[84],[85].

Serveurs spécialisés

Pour les sites Web fournissant des services hétérogènes, l'URL envoyée par le client peut être utilisée pour répartir les requêtes vers le serveur correspondant au service demandé. Les services auront été partitionnés sur les différents serveurs de la grappe[83],[86]. Le but de cette approche est de prendre en compte les différences de traitement entre contenus afin d'améliorer les performances du système. Par exemple, l'exécution d'un script CGI demande beaucoup plus de ressources au serveur Web que pour servir un fichier statique. Cette approche permet dans ce cas d'utiliser des serveurs puissants pour les CGI et des serveurs moins puissants pour les contenus statiques[86].

Partage de charge

Ces algorithmes ont pour but de partager la charge sans partitionnement logique ou physique prédéfini comme précédemment[83].

Un premier algorithme utilisé, nommé SITA-E pour Size Interval Task Assigment with Equal load, établit un partitionnement dynamique des requêtes en fonction de la taille des fichiers demandés[83],[87]. Les intervalles de ces partitions, définis par la taille des fichiers, sont réévalués régulièrement par le répartiteur pour équilibrer la charge sur les différents serveurs[87]. Cette implémentation est surtout performante lorsque les tailles des fichiers demandés par les clients sont très variables[87]. Par ailleurs, l'algorithme part du postulat que le temps de réponse d'une requête est proportionnelle à la taille, ce qui le réserve à l'utilisation de ressources statiques[83].

Un autre algorithme, nommé CAP pour Client-aware policy, peut être utilisé sur le répartiteur qui classe alors les requêtes Web selon leur impact sur les ressources physiques (CPU, disque) des serveurs[88]. Le répartiteur ne peut pas obtenir la charge du serveur mais peut estimer le type de charge d'une requête à partir de l'URL reçue. En fonction de l'impact principal, la requête est dirigée vers un serveur d'une liste préétablie en fonction des ressources utilisées[89],[90],[83].

Affinité du client

Dans cette approche, les requêtes d'un client donné seront toujours envoyées au même serveur, créant une affinité client-serveur. Cette stratégie est similaire à celle utilisée lorsque le répartiteur n'a pas la connaissance du contenu de la requête. L'apport de la connaissance du contenu permet de créer une affinité non plus uniquement via les informations TCP mais avec des informations plus précises telles que l'identifiant SSL ou le témoin de connexion du client[91].

Basés sur les informations du client et du serveur[modifier | modifier le code]

En plus des informations du client, ces algorithmes prennent également en compte les informations du serveur comme la disponibilité ou la charge[82].

Affinité du cache

Ces algorithmes sont similaires aux algorithmes basés sur l'affinité du cache à partir des informations du client. En plus des informations du clients, ils étendent les possibilités de distribution des requêtes en prenant en compte les informations du serveur telles que la charge et la disponibilité[90],[91].

Partage de charge

Un algorithme de répartition nommé LARD pour Locality-Aware Request Distribution[81] se base à la fois sur l'emplacement des ressources et sur la charge des serveurs[90],[91]. Le principe de base de LARD est de rediriger toutes les requêtes d'une ressource Web donnée vers un même serveur Web, optimisant ainsi l'utilisation du cache Web, jusqu'à l'atteinte d'un seuil de charge. Une fois le seuil atteinte, les requêtes seront dirigées vers un serveur moins chargé[92],[90],[91]. Cet algorithme est surtout performant lorsque la plupart des contenus Web est statique[90].

Perspectives[modifier | modifier le code]

Protocoles HTTP[modifier | modifier le code]

Article connexe : Hypertext Transfer Protocol.

La standardisation du nouveau protocole HTTP/1.1 ajoute une fonctionnalité permettant de transférer plusieurs requêtes dans une même connexion[93]. Pour les routages aux couches 4 et 7, la charge de travail générée par l'établissement d'une nouvelle connexion par le répartiteur peut être amortie par le grand nombre d'objets utilisant cette connexion. Par contre la charge engendrée par le transfert des paquets restera la même. L'équilibrage de charge devient plus difficile puisque chaque décision de routage peut avoir un impact important dû aux variations de bande passante en cas de connexion longue. Pour le routage couche 2, où la charge de travail est liée à l'établissement de la connexion, cette nouvelle version du protocole HTTP réduit donc globalement la charge[21].

Le HTTP 2.0 est également en étude, l'IETF HTTPbis-WG a pris comme base de cette prochaine version : SPDY (prononcé « speedy », comme « rapide » en anglais), conçu et proposé par Google[94]. Le flux multiplexage est au cœur de la performance de SPDY, elle réduit le nombre de rotations nécessaires pour aller chercher les ressources, réduisant ainsi la charge[95].

Algorithmes génétiques[modifier | modifier le code]

Article connexe : Algorithme génétique.

Aujourd'hui, le partage de la charge et le temps de réponses sont les principaux défis pour les algorithmes d'équilibrage de charge, qui deviennent de plus en plus centraux dans la performance d'un système Web[96],[64],[4]. Les principales difficultés des algorithmes dynamiques d'équilibrage de charge sont les suivantes[64] :

  • mesure de la charge : les informations de charge arrivent très régulièrement et le calcul doit être le plus fiable possible
  • l'échange d'informations : la collecte et le maintien des informations de charge représentent un compromis entre le coût du stockage et la fiabilité de la connaissance des systèmes. Le principal problème est la période d’échantillonnage
  • l'opération d'équilibrage de charge : elle doit avoir lieu au bon moment, suffisamment rapide pour éviter qu'un serveur ne s'écroule mais pas suffisamment lente pour ne pas être contre-productive.

Les algorithmes d'équilibrage de charge traditionnels fonctionnent en point-à-point et génèrent un grand nombre d'erreurs qui affectent négativement la recherche du meilleur résultat. De par leur forte capacité à effectuer des recherches globales multi-points, les algorithmes génétiques pourraient être une solution optimale d'équilibrage de charge[96].

Les algorithmes génétiques s'inspirent des mécanismes de sélection naturelle et de la génétique pour gagner en efficacité[97]. En plus d'être utilisés dans différents domaines, ce type d'algorithme intéresse également les chercheurs en équilibrage de charge. Mais il leur manque aujourd'hui les capacités de régulation automatiques[97] et ilspeuvent avoir pour défaut une convergence trop rapide, et non optimale, des solutions[96]. Les recherches récentes sur les améliorations des algorithmes génétiques pour l'équilibrage de charge tendent à les améliorer et donnent des résultats concluants[98],[99]. Par exemple, les travaux sur l'ajout d'algorithmes de type ISODATA lors de la phase de mutation permet d'ajouter à l'algorithme génétique une fonctionnalité de régulation automatique qui lui manquait[98]. Pour autre exemple, les travaux sur un algorithme génétique immunitaire introduit les concepts d'antigène, d'anticorps et de vaccination afin de pallier la convergence trop rapide des solutions des algorithmes génétiques standards[99].

Bibliographie[modifier | modifier le code]

Document utilisé pour la rédaction de l’article : document utilisé comme source pour la rédaction de cet article.

  • (en) H. Bryhni, E. Klovning et O. Kure, « A comparison of load balancing techniques for scalable Web servers », IEEE Network, vol. 14, no 4,‎ , p. 58-64 (ISSN 0890-8044) Document utilisé pour la rédaction de l’article
  • (en) T.-S. Chen et K.-L. Chen, « Balancing workload based on content types for scalable Web server clusters », Advanced Information Networking and Applications, vol. 2,‎ , p. 321-325 (ISBN 0769520510) Document utilisé pour la rédaction de l’article
  • (en) A. Mahmood et I. Rashid, « Comparison of load balancing algorithms for clustered web servers », Information Technology and Multimedia,‎ , p. 1-6 (ISBN 9781457709883) Document utilisé pour la rédaction de l’article
  • (en) V. Cardellini, M. Colajanni et P. S. Yu, « Dynamic Load Balancing on Web-server Systems », IEEE Internet Computing, vol. 3, no 3,‎ , p. 28-39 (ISSN 1089-7801, DOI 10.1109/4236.769420) Document utilisé pour la rédaction de l’article
  • (en) V. Cardellini, E. Casalicchio, M. Colajanni et P. Yu, « The State of the Art in Locally Distributed Web-Server Systems », ACM Computing Surveys, vol. 34,‎ , p. 263-311 (DOI 10.1145/508352.508355) Document utilisé pour la rédaction de l’article
  • (en) M. Castro, « Load balancing and control for distributed World Wide Web servers », Control Applications,‎
  • (en) E.D. Katz, « A scalable HTTP server: The NCSA prototype », Computer Networks and ISDN Systems, vol. 27,‎ , p. 155-164 Document utilisé pour la rédaction de l’article
  • (en) T.F. Abdelzaher, K.G. Shin et N. Bhatti, « Performance guarantees for Web server end-systems: a control-theoretical approach », Parallel and Distributed Systems, IEEE Transactions on, vol. 13,‎ , p. 80-96 (ISSN 1045-9219, DOI 10.1109/71.980028) Document utilisé pour la rédaction de l’article
  • (en) B. Devlin, J. Gray et G. Spix, « Scalability Terminology: Farms, Clones, Partitions, and Packs: RACS and RAPS », Parallel and Distributed Systems, IEEE Transactions on, vol. 13,‎ , p. 80-96 (ISSN 1045-9219, DOI 10.1109/71.980028) Document utilisé pour la rédaction de l’article
  • (en) Z.-K. Du et J.-B. Ju, « A completely distributed architecture for cluster-based Web servers », Parallel and Distributed Computing, Applications and Technologies,‎ , p. 483 - 487 (ISBN 0-7803-7840-7, DOI 10.1109/PDCAT.2003.1236349) Document utilisé pour la rédaction de l’article
  • (en) T.T. Kwan, R.E. McGrath et D.A. Reed, « NCSA's World Wide Web server : Design dans Performance », Computer Vol. 28, N°.11,‎ , pp 68-74 (ISSN 0018-9162) Document utilisé pour la rédaction de l’article
  • (en) Z. Genova et K.J. Christensen, « Challenges in URL Switching for Implementing Globally Distributed Web Sites », Parallel Processing, 2000. Proceedings. 2000 International Workshops on,‎ , pp 89-94 (ISBN 0-7695-0771-9, ISSN 1530-2016, DOI 10.1109/ICPPW.2000.869091) Document utilisé pour la rédaction de l’article
  • (en) Dongeum. Kim, Ho Park Cheol et Park Daeyeon, « Request rate adaptive dispatching architecture for scalable Internet server », Cluster Computing, 2000. Proceedings. IEEE International Conference,‎ , p. 289 - 296 (ISBN 0-7695-0896-0, DOI 10.1109/CLUSTR.2000.889082) Document utilisé pour la rédaction de l’article
  • (en) L. Aversa et A. Bestavros, « Load balancing a cluster of web servers: using distributed packet rewriting », Performance, Computing, and Communications Conference, 2000. IPCCC '00. Conference Proceeding of the IEEE International,‎ , p. 24-29 (ISBN 0-7803-5979-8, DOI 10.1109/PCCC.2000.830297) Document utilisé pour la rédaction de l’article
  • (en) S. Vaidya et K.-J. Christensen, « A single system image server cluster using duplicated MAC and IP addresses », Local Computer Networks, 2001. Proceedings. LCN 2001. 26th Annual IEEE Conference on,‎ , p. 206 - 214 (ISBN 0-7695-1321-2, ISSN 0742-1303, DOI 10.1109/LCN.2001.990789) Document utilisé pour la rédaction de l’article
  • (en) T. Schroeder, S. Goddard et B. Ramamurthy, « Scalable Web server clustering technologies », Network, IEEE, vol. 14, no 3,‎ , p. 38-45 (ISSN 0890-8044, DOI 10.1109/65.844499) Document utilisé pour la rédaction de l’article
  • (en) A. Singhai, « the SunSCALR framework for Internet servers », Fault-Tolerant Computing, 1998. Digest of Papers. Twenty-Eighth Annual International Symposium on, IEEE,‎ , p. 108-117 (ISSN 0731-3071, DOI 10.1109/FTCS.1998.689460)
  • (en) E. Martel, J. Miranda, L. Hernandez et F. Guerra, « Remote management of distributed application », Parallel, Distributed and Network-Based Processing, 2004. Proceedings. 12th Euromicro Conference on,‎ , p. 159-166 (ISBN 0-7695-2083-9, ISSN 1066-6192, DOI 10.1109/EMPDP.2004.1271441) Document utilisé pour la rédaction de l’article
  • (en) S.H.H. Tse, « Approximate algorithms for document placement in distributed Web servers », Parallel Architectures, Algorithms and Networks, 2004. Proceedings. 7th International Symposium on,‎ , p. 61-66 (ISBN 0-7695-2135-5, ISSN 1087-4089, DOI 10.1109/ISPAN.2004.1300458) Document utilisé pour la rédaction de l’article
  • (en) C. Li-Chuan et C. Hyeong-Ah, « Approximation algorithms for data distribution with load balancing of web servers », Cluster Computing, 2001. Proceedings. 2001 IEEE International Conference on,‎ , p. 274-281 (ISBN 0-7695-1390-5, ISSN 1552-5244, DOI 10.1109/CLUSTR.2001.959988) Document utilisé pour la rédaction de l’article
  • (en) M. Colajanni, P.S. Yu et D.M. Dias, « Analysis of task assignment policies in scalable distributed web-server systems », Parallel and Distributed Systems, IEEE Transactions on (Volume:9 , Issue: 6),‎ , p. 585-600 (ISSN 1045-9219, DOI 10.1109/71.689446)
  • (en) B.A. Mah, « An empirical model of HTTP network traffic », INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution., Proceedings IEEE, vol. 2,‎ , p. 592-600 (ISBN 0-8186-7780-5, ISSN 0743-166X, DOI 10.1109/INFCOM.1997.644510)
  • (en) D.M. Dias, W. Kish, R. Mukherjee et R. Tewari, « A scalable and highly available web server », Compcon '96. 'Technologies for the Information Superhighway' Digest of Papers, vol. 2,‎ , p. 85-92 (ISBN 0-8186-7414-8, ISSN 1063-6390, DOI 10.1109/CMPCON.1996.501753)
  • (en) J. Vashistha et A.K. Jayswal, « Comparative Study of Load Balancing Algorithms », IOSR Journal of Engineering (IOSRJEN), vol. 3, no 3,‎ , p. 45-50 (ISSN 2278-8719)
  • (en) K.H. Yeung, K.W. Suen et K.Y. Wong, « Least load dispatching algorithm for parallel Web server nodes », Communications, IEE Proceedings, vol. 149, no 4,‎ , p. 223-226 (ISSN 1350-2425, DOI 10.1049/ip-com:20020169) Document utilisé pour la rédaction de l’article
  • (en) R. Bhinder, M. Maheswaran et J. Diamond, « Evaluation of request distribution schemes for Web-server clusters », Electrical and Computer Engineering, 2004. Canadian Conference on, vol. 3,‎ , p. 1609-1612 (ISBN 0-7803-8253-6, ISSN 0840-7789, DOI 10.1109/CCECE.2004.1349717)
  • (en) A. Bestavros, M. Crovella, J. Liu et D. Martin, « Distributed packet rewriting and its application to scalable server architectures », Network Protocols, 1998. Proceedings. Sixth International Conference on,‎ , p. 290-297 (ISBN 0-8186-8988-9, DOI 10.1109/ICNP.1998.723750) Document utilisé pour la rédaction de l’article
  • (en) Z.-K. Du et J.-B. Ju, « Distributed content-aware request distribution in cluster-based Web servers », Parallel and Distributed Computing, Applications and Technologies, 2003. PDCAT'2003. Proceedings of the Fourth International Conference on,‎ , p. 99-103 (ISBN 0-7803-7840-7, DOI 10.1109/PDCAT.2003.1236267) Document utilisé pour la rédaction de l’article
  • (en) G.D.H. Hunt, G.S. Goldszmidt, R.P. King et R. Mukherjee, « Network Dispatcher : a connection router for scalable Internet services », Computer networks and ISDN systems, vol. 30, nos 1-7,‎ , p. 347-357 (ISSN 0169-7552, DOI 10.1016/S0169-7552(98)00088-9) Document utilisé pour la rédaction de l’article
  • (en) V. Cardellini, M. Colajanni et P.S. Yu, « Redirection algorithms for load sharing in distributed Web-server systems », Distributed Computing Systems, 1999. Proceedings. 19th IEEE International Conference on,‎ , p. 528-535 (ISSN 1063-6927, DOI 10.1109/ICDCS.1999.776555)
  • (en) D. Andresen, T. Yang et O.H. Ibarra, « Toward a Scalable Distributed WWW Server on Workstation Clusters », Journal of Parallel and Distributed Computing 42,‎ , p. 91-100 (ISSN 0743-7315) Document utilisé pour la rédaction de l’article
  • (en) M.E. Crovella, R. Frangioso et M. Harchol-Balter, « Connection scheduling in web servers », ProceedingUSITS'99 Proceedings of the 2nd conference on USENIX Symposium on Internet Technologies and Systems, vol. 2,‎ , p. 22-42 Document utilisé pour la rédaction de l’article
  • (en) M. Arlitt et T. Jin, « A workload characterization study of the 1998 World Cup Web site », Network, IEEE, vol. 14, no 3,‎ , p. 30-37 (ISSN 0890-8044, DOI 10.1109/65.844498) Document utilisé pour la rédaction de l’article
  • (en) C.S. Yang et M.Y. Luo, « A content placement and management system for distributed Web-server systems », Distributed Computing Systems, 2000. Proceedings. 20th International Conference on,‎ , p. 691-698 (ISBN 0-7695-0601-1, ISSN 1063-6927, DOI 10.1109/ICDCS.2000.840986) Document utilisé pour la rédaction de l’article
  • (en) M. Harchol-Balter, M.E. Crovella et C.D. Murta, « On Choosing a Task Assignment Policy for a Distributed Server System », Journal of Parallel and Distributed Computing, vol. 59, no 2,‎ , p. 204-228 (DOI 10.1006/jpdc.1999.1577) Document utilisé pour la rédaction de l’article
  • (en) E. Casalicchio, V. Cardellini et M. Colajanni, « Content-Aware Dispatching Algorithms for Cluster-Based Web Servers », Journal Cluster Computing, vol. 5, no 1,‎ , p. 65-74 (DOI 10.1023/A:1012796706047) Document utilisé pour la rédaction de l’article
  • (en) E. Casalicchio et M. Colajanni, « A client-aware dispatching algorithm for web clusters providing multiple services », Proceeding WWW '01 Proceedings of the 10th international conference on World Wide Web, vol. 5, no 1,‎ , p. 535-544 (ISBN 1-58113-348-0, DOI 10.1145/371920.372155) Document utilisé pour la rédaction de l’article
  • (en) M. Aron, P. Druschel et W. Zwaenepoel, « Efficient support for P-HTTP in cluster-based web servers », Proceeding ATEC '99 Proceedings of the annual conference on USENIX Annual Technical Conference,‎ , p. 14-28 Document utilisé pour la rédaction de l’article
  • (en) V.S. Pai, M. Aron, W. Zwaenepoel, G. Banga, P. Druschel et E. Nahum, « Locality-aware request distribution in cluster-based network servers », Proceedings of the eighth international conference on Architectural support for programming languages and operating systems,‎ , p. 205-216 (ISBN 1-58113-107-0, DOI 10.1145/291069.291048) Document utilisé pour la rédaction de l’article
  • (en) R. Su et W. Yu, « Immune Genetic Algorithm-based Load Balancing in Web Cluster », Genetic and Evolutionary Computing (ICGEC), 2010 Fourth International Conference on,‎ , p. 321-324 (ISBN 978-0-7695-4281-2, DOI 10.1109/ICGEC.2010.86) Document utilisé pour la rédaction de l’article
  • (en) A.Y. Zomaya et Y.H. Tei, « Observations on using genetic algorithms for dynamic load-balancing », Parallel and Distributed Systems, IEEE Transactions on, vol. 12, no 9,‎ , p. 899-911 (ISSN 1045-9219, DOI 10.1109/71.954620) Document utilisé pour la rédaction de l’article
  • (en) Z. Zhu, Y. Tian, J. Xu, X. Deng et X. Ren, « An Improved Partitioning-Based Web Documents Clustering Method Combining GA with ISODATA », Fuzzy Systems and Knowledge Discovery, 2007. FSKD 2007. Fourth International Conference on, vol. 2,‎ , p. 208-213 (ISBN 978-0-7695-2874-8, DOI 10.1109/FSKD.2007.165) Document utilisé pour la rédaction de l’article
  • (en) Z. Zhengyu, H. Ping, Y. Chunlei et L. Lipei, « A dynamic genetic algorithm for clustering web pages », Software Engineering and Data Mining (SEDM), 2010 2nd International Conference on,‎ , p. 506-511 (ISBN 978-1-4244-7324-3)
  • (en) D.A. Maltz et P. Bhagwat, « TCP splice application layer proxy performance », Journal of High Speed Networks, vol. 8, no 3,‎ , p. 225-240 (ISSN 0926-6801) Document utilisé pour la rédaction de l’article
  • (en) Y. Elkhatib, G. Tyson et M. Welzl, « Can SPDY really make the web faster? », Networking Conference, 2014 IFIP,‎ , p. 1-9 (DOI 10.1109/IFIPNetworking.2014.6857089)
  • (en) O. Spatscheck, J.S. Hansen, J.H. Hartman et L.L. Peterson, « Optimizing TCP forwarder performance », Networking, IEEE/ACM Transactions on, vol. 8, no 2,‎ , p. 146-157 (DOI 10.1109/90.842138) Document utilisé pour la rédaction de l’article
  • (en) L. Zhenhua, L. Minghong, W. Adam, H.L. Steven et L.H. Lachlan, « Greening geographical load balancing », SIGMETRICS '11 Proceedings of the ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems,‎ , p. 233-244 (ISBN 978-1-4503-0814-4, DOI 10.1145/1993744.1993767) Document utilisé pour la rédaction de l’article

Notes et références[modifier | modifier le code]

  1. ↑ a b et c Abdelzaher 2002, p. 80
  2. ↑ a b c d e f g h i j k l m et n Chen 2004, p. 321
  3. ↑ a b c d e f et g Cardellini 1999, p. 2
  4. ↑ a b c d e f g h et i Mahmood 2011, p. 1
  5. ↑ a b c d e f g h et i Yeung 2002, p. 223
  6. ↑ a b c d et e Li-Chuan 2001, p. 274
  7. ↑ a b c d e et f Devlin 1999, p. 3
  8. ↑ a b et c Martel 2004, p. 159
  9. ↑ a b c et d Schroeder 2000, p. 38
  10. ↑ a b c et d Tse 2004, p. 61
  11. ↑ a b c d e f et g Bryhni 2000, p. 58
  12. ↑ a et b Cardellini 1999, p. 1
  13. ↑ a b et c Aversa 2000, p. 24
  14. ↑ a b et c Du 2003, p. 1
  15. ↑ a b et c Du 2003
  16. ↑ Katz 1994, p. 155
  17. ↑ a b et c Devlin 1999, p. 9
  18. ↑ Katz 1994, p. 156
  19. ↑ Katz 1994, p. 157
  20. ↑ Katz 1994, p. 163
  21. ↑ a b c d e f g h i j k l m n o p et q Bryhni 2000, p. 59
  22. ↑ RFC 2616, sur le site de l'IETF
  23. ↑ a b c d e f g et h Vaidya 2001, p. 206
  24. ↑ a b et c Cardellini 1999, p. 3
  25. ↑ a b c et d Genova 2000, p. 89
  26. ↑ Cardellini 2002, p. 270
  27. ↑ Cardellini 2002, p. 271
  28. ↑ a b c d e f g h i j et k Mahmood 2011, p. 2
  29. ↑ a b c d e f g et h Chen 2004, p. 322
  30. ↑ a b c et d Schroeder 2000, p. 39
  31. ↑ a et b Cardellini 2002, p. 272
  32. ↑ a et b Cardellini 2002, p. 268
  33. ↑ a b c d et e Cardellini 1999, p. 10
  34. ↑ a b et c Cardellini 2002, p. 274
  35. ↑ a b c d e f g h i j k et l Vaidya 2001, p. 207
  36. ↑ a b et c Cardellini 1999, p. 14
  37. ↑ a b et c Bryhni 2000, p. 60
  38. ↑ a b et c Vaidya 2001, p. 208
  39. ↑ a et b Cardellini 2002, p. 282
  40. ↑ a et b Cardellini 1999, p. 15
  41. ↑ Cardellini 1999, p. 11
  42. ↑ Cardellini 2002, p. 279
  43. ↑ a b et c Cardellini 2002, p. 280
  44. ↑ a b et c Cardellini 2002, p. 277
  45. ↑ a b et c Maltz 1999, p. 225
  46. ↑ Spatscheck 2000, p. 146
  47. ↑ Spatscheck 2000, p. 148
  48. ↑ Maltz 1999, p. 238
  49. ↑ a b et c Pai 1998, p. 214
  50. ↑ a b et c Aron 1999, p. 18
  51. ↑ Cardellini 2002, p. 278
  52. ↑ Cardellini 1999, p. 29
  53. ↑ Kwan 1995, p. 68
  54. ↑ Dongeun Kim 2000, p. 290
  55. ↑ Cardellini 1999, p. 30
  56. ↑ a b et c Colajanni 1998, p. 590
  57. ↑ a b c d et e Cardellini 1999, p. 31
  58. ↑ Dongeum 2000, p. 290
  59. ↑ a b c et d Cardellini 1999, p. 4
  60. ↑ Cardellini 1999, p. 5
  61. ↑ a et b Cardellini 1999, p. 35
  62. ↑ Bestavros 1998, p. 292
  63. ↑ a b et c Cardellini 1999, p. 36
  64. ↑ a b et c Zomaya 2001, p. 899
  65. ↑ Cardellini 2002, p. 286
  66. ↑ a b c et d Cardellini 2002, p. 288
  67. ↑ a et b Yeung 2002, p. 224
  68. ↑ a b et c Cardelliini 2002, p. 287
  69. ↑ a b c d et e Bryhni 2000, p. 61
  70. ↑ a et b « Job Scheduling Algorithms in Linux Virtual Server », sur Linux Virtual Server
  71. ↑ a b et c Cardellini 2002, p. 289
  72. ↑ Mahmood 2011, p. 3
  73. ↑ Cardellini 2002, p. 290
  74. ↑ « Persistence Handling in LVS », sur Linux Virtual Server
  75. ↑ Hunt 1998, p. 353
  76. ↑ Du 2003, p. 100
  77. ↑ Casalicchio 2002, p. 66
  78. ↑ Cardellini 2002, p. 291
  79. ↑ Casalicchio 2002, p. 67
  80. ↑ Aron 1999, p. 14
  81. ↑ a et b Pai 1998, p. 205
  82. ↑ a et b Casalicchio 2002, p. 68
  83. ↑ a b c d e f et g Cardellini 2002, p. 29
  84. ↑ Crovella 1999, p. 4`
  85. ↑ Arlitt 2000, p. 36
  86. ↑ a et b Yang 2000, p. 691
  87. ↑ a b et c Harchol 1999, p. 212
  88. ↑ Casalicchio 2001, p. 535
  89. ↑ Casalicchio 2001, p. 536
  90. ↑ a b c d et e Casalicchio 2002, p. 69
  91. ↑ a b c et d Cardellini 2002, p. 293
  92. ↑ Pai 1998, p. 207
  93. ↑ « RFC 2616 (HTTP/1.1) », sur IETF
  94. ↑ Elkhatib 2014, p. 1
  95. ↑ Elkhatib 2014, p. 9
  96. ↑ a b et c Su 2010, p. 321
  97. ↑ a et b Zhu 2007, p. 208
  98. ↑ a et b Zhu 2007, p. 213
  99. ↑ a et b Su 2010, p. 324
Ce document provient de « https://fr.wikipedia.org/w/index.php?title=Équilibrage_de_charge_des_serveurs_Web&oldid=178725110 ».