Αποδοτικοί αλγόριθμοι εξισορρόπησης φορτίου στο διαδίκτυο με βάση το περιεχόμενο των αιτήσεων και της κατάστασης των εξυπηρετητών

Abstract

High Utilization of web based applications and implementation of more and more services over HTTP, lead to re-design and building of more efficient web servers and services or even implementation of different scheduling policies at requests. The emerging web 2.0 technologies and tools, followed by Google and many social, e-health, e-learning and e-government web services, is a mature indication that the World Wide Web and more specifically HTTP protocol services traffic is definitely becoming the most excessive form of traffic for routers, that shall geometrically increase web servers processing efforts over the following years. Focusing on further improving web server capabilities, distributed web architectures have been developed, consisting of web server farms and load balancing architectures were deployed for HTTP traffic. Such distributed web architectures are the cluster-based web systems. The front end node of a cluster-based web system is the web switch. The web switch receives all in-bound connections that clients send to the VIP address and routes them to the system web server nodes accordingly. A clusterbased web system design is comprised of two basic structural parts: The balancing process, which selects the best suited target servers to respond to requests and the routing mechanism, which redirects clients to the appropriate target server. Cluster-based web systems routing mechanisms are divided into content aware (layer 7) and noncontent aware (layer 2/3/4), while load balancing algorithms used at a web switch are classified into five distinct categories: 1. Stateless non-adaptive, 2. Stateful non-adaptive, 3. Stateless adaptive, 4. Stateful adaptive and 5. Content aware. As stateful/stateless algorithms, we characterise those algorithms that keep track or not of client connection requests. As adaptive/non-adaptive, we characterize those algorithms that take into account web server status metrics feedback and adapt their behaviour based on metric transitions. Content aware algorithms extend adaptive algorithm potential by also investigating HTTP request header information and HTTP request payload size (content length) for balancing decisions. This thesis presents an Adaptive Load BaLancing algorithm (ALBL), for cluster-based web systems. ALBL is and adaptive load balancing algorithm that focuses in prediction of network conditions and web servers’ load without the use of feedback information obtained by web servers. That is achieved with frequent service and network probes towards web servers by the web switch. Tests of performance and scalability of the ALBL implementation against known balancing algorithms used at web-farms are presented and show that ALBL outperforms these algorithms and scales well as the number of balancing servers and web cluster’s contention increases, under specific network or processing load conditions. Based on ALBL capabilities from experimental results, a new content aware load balancing algorithm was also designed; called ALBL/HSC. This algorithm maintains classes of HTTP traffic and differentiates traffic based on content of HTTP requests. Then it utilizes ALBL algorithm to load balance requests per class accordingly. That is, ALBL/HSC maintains separate ALBL processes per HTTP service class for balancing traffic among web servers assigned to each class. ALBL/HSC algorithm was put to the test against ALBL over a cluster based load balancing system. Additionally, CPU performance tests performed at the web switch and performance tests at the web servers indicate both capabilities and drawbacks of content aware ALBL/HSC and adaptive ALBL algorithm. New capabilities that can be part of content aware algorithms are also presented. That is, clustering prediction capability, bandwidth and web farm utilization estimation and sharing mechanisms among classes of HTTP traffic. Finally, in order to improve performance of ALBL algorithm in the ALBL/HSC content aware mechanism with a more adaptive, multi-metric algorithm that receives feedback from both the web switch as well as web servers, a new load balancing algorithm, called AWLB for cluster based web systems was proposed. This algorithm maintains agents both at the web cluster and web servers in order to adapt its balancing decisions accordingly. AWLB algorithm also maintains its own protocol specification for signaling purposes among web switch and cluster nodes and also utilizes other protocols such as SNMP and/or ICMP for its balancing process. Performance gains are shown from tests of AWLB against known balancing algorithms used by web-farms. CPU performance tests at the web switch show both advantages and drawbacks of complicated but accurate adaptive decisions over less accurate but misbalancing policies.

Η ραγδαία ανάπτυξη των διαδικτυακών εφαρμογών και ειδικότερα των εφαρμογών του παγκόσμιου ιστού (Word Wide Web-WWW) οδήγησε στην ανάπτυξη πιο αποδοτικών υπηρεσιών (services) και συστημάτων εξυπηρέτησης (web servers). Οι εξελισσόμενες web 2.0 τεχνολογίες και οι πλατφόρμες ανάπτυξης web εφαρμογών, όπως τα εργαλεία ανάπτυξης της Google, οι CMS (Content Μanagement Systems) πλατφόρμες ανάπτυξης, οι ιστοχώροι κοινωνικής δικτύωσης και οι υπηρεσίες που παρέχονται μέσω του διαδικτυακού ιστού (e-health, e-learning, e-gov, e-info, e-vote), καθιστούν σήμερα το διαδικτυακό ιστοχώρο και εν συνέπεια την μεταφορά πληροφορίας πάνω από το πρωτόκολλο HTTP ως την πλέον σημαντικότερη διαδικτυακή κίνηση για τους δρομολογητές. Αυτό έχει ως αποτέλεσμα την ανάγκη για πιο αποδοτικούς, ευέλικτους και επεκτάσιμους εξυπηρετητές και συστήματα εξυπηρέτησης της HTTP διαδικτυακής κίνησης. Για την βελτίωση της απόδοσης των εξυπηρετητών αναπτύχθηκαν κατανεμημένες αρχιτεκτονικές συστημάτων. Τα συστήματα αυτά αποτελούνται από συστοιχίες διαδικτυακών εξυπηρετητών (web farms), οι οποίοι αποτελούν μια ενοποιημένη συστημική δομή για το χρήστη και κάθε εξυπηρετητής λαμβάνει προς εξυπηρέτηση ένα μέρος των αιτήσεων εξυπηρέτησης του συστήματος. Αυτές οι αρχιτεκτονικές διακρίνονται σε: 1. Διανεμόμενες αρχιτεκτονικές (distributed architectures), όπου χρησιμοποιούν συστοιχίες εξυπηρετητών ανά διαδικτυακή υπηρεσία ή συλλογή ομοιογενούς περιεχομένου και όπου οι αιτήσεις διανέμονται με μια στατική μέθοδο, 2. Εικονικούς ή γεωγραφικά τοποθετημένους εξυπηρετητές (βλέπε μηχανή αναζήτησης google) όπου η εξυπηρέτηση των αιτήσεων διαμοιράζεται σε εξυπηρετητές που είναι υπεύθυνοι για την εξυπηρέτηση στην εν λόγω γεωγραφική περιοχή των πελατών (στατικός τρόπος εξυπηρέτησης-μέσω DNS) και 3. Συστήματα συστοιχίας (cluster based web systems) όπου η εξυπηρέτηση των πελατών γίνεται με δυναμικό τρόπο λαμβάνοντας υπόψη την διαθεσιμότητα σε υπολογιστικούς πόρους τόσο του εξυπηρετητή (web server) όσο και δικτυακών πόρων του συστήματος. Τα συστήματα συστοιχίας (cluster-based systems) εξετάζονται στα πλαίσια αυτής της διδακτορικής διατριβής. Η δομή ενός συστήματος συστοιχίας περιλαμβάνει έναν αριθμό εξυπηρετητών διασυνδεδεμένων με ένα κεντρικό σύστημα λήψης αποφάσεων (web switch), υπεύθυνο για τον έλεγχο των εξυπηρετητών, της δικτυακής κίνησης από και προς κάθε ένα εξυπηρετητή και την κατανομή των HTTP αιτήσεων στους εξυπηρετητές με τη χρήση κατάλληλων αλγορίθμων κατανομής φορτίου και μηχανισμών επαναδρομολόγησης αιτήσεων. Στα πλαίσια αυτής της διατριβής αναπτύχθηκαν τρεις αλγόριθμοι κατανομής φορτίου για συστήματα συστοιχίας: 1. Ο αλγόριθμος ALBL (Adaptive Load BaLancing αλγόριθμος) ο οποίος χρησιμοποιεί μετρικές για των υπολογισμό του φόρτου των εξυπηρετητών και του διαθέσιμου εύρους (bandwidth) από το web switch χωρίς άντληση πληροφορίας (feedback) από τους εξυπηρετητές με στόχο την δυναμική και προσαρμοστική (adaptive) κατανομή των αιτήσεων στους εξυπηρετητές της συστοιχίας. 2. O αλγόριθμος AWLB (Adaptive Workload Load Balancing) που έχει κοινά χαρακτηριστικά με τον ALBL αλλά χρησιμοποιεί μια πληθώρα μετρικών που μετρούν οι εξυπηρετητές και αποστέλλουν με τη χρήση του SNMP πρωτοκόλλου στο web switch. O αλγόριθμος αυτός έχει ένα πιο πολύπλοκο, σε σχέση με τον ALBL, σύστημα υπολογισμού βαρών αλλά και ένα πιο δίκαιο σύστημα κατανομής αιτήσεων λαμβάνοντας υπόψη του παρελθόντες κατανομές. 3. O αλγόριθμος ALBL/HSC (Adaptive Load Balancing with Hierarchical Service Classes) ο οποίος αρχικά διαμοιράζει την κίνηση όπως ένα σύστημα διαμοιρασμού κίνησης (Distributed system), σε κλάσεις εξυπηρέτησης ανάλογα με το περιεχόμενο της αίτησης και στη συνέχεια χρησιμοποιεί τον προσαρμοστικό ALBL αλγόριθμο για την απόδοση της αίτησης στον κατάλληλο εξυπηρετητή της ομάδας εξυπηρετητών που εξυπηρετεί τις αιτήσεις της κάθε κλάσης. Οι παραπάνω αλγόριθμοι υλοποιήθηκαν και εξετάστηκαν τόσο ως προς την απόδοσή τους όσο ως προς την κλιμάκωσή τους αλλά και την πολυπλοκότητα με την μορφή υπολογιστικού φόρτου που εισάγουν αλγοριθμικά στο web switch. Τα αποτελέσματα αυτά συγκρίθηκαν με μετρήσεις από υπάρχοντες αλγορίθμους συστημάτων κατανομής φορτίου όπως ο RR (Round Robin), LC (Least Connections-ελαχίστων συνδέσεων) και LL (Least Load-ελαχίστου φορτίου) και βρέθηκαν πιο αποτελεσματικοί ενώ παράλληλα εξήχθησαν χρήσιμα συμπεράσματα για την περαιτέρω βελτίωσή τους και γενικότερα για τη δημιουργία ακόμα πιο αποδοτικών αλγορίθμων κατανομής φορτίου.