Method and algorithms of broker-based HTTP request global distribution

• Autorzy: Borzemski L. , Zatwarnicka A. , Zatwarnicki K.

Warianty tytułu

PL

Metoda i algorytmy globalnej dystrybucji żądań HTTP

• Języki publikacji: EN

Abstrakty

EN

In the paper we present new broker-based HTTP (Hypertext Transfer Protocol) request global distribution method and algorithm called GARDIB (Global Request Distribution with Broker). The method is based on a fuzzy-neural decision-making scheme allowing distributing HTTP requests based on the request response time. The decision at global level is made by the broker which is an intermediate server used by the Web clients to get Web pages. Each HTTP request is redirected by a broker which is located in the neighbor proximity of the user. Several brokers may serve to the same set of Web sites with the fully replicated content. Broker has ability to estimate request response time using own made network broker-to-Web sites latency measurements, as well as load conditions of every local Web sites, collected from local Web switches that locally distributes requests to the target local Web servers. In the paper we assume that localWeb switches are equipped with the FNRD (Fuzzy Neural Request Distribution) algorithm developed by the authors. FRND’s decision-making scheme also is based on fuzzy-neural modeling with request completion time as the performance metrics. GARDiB is evaluated via simulation experiments and compared with other candidates for global distribution, namely RR (Round Robin) andWRR (Weighted Round Robin) policies. The weighting in the latter case can be based on the local load state (WRR-L) or network throughput (WRR-T). Simulation experiments are made by means of CSIM19 software in C++. The results show that GARDiB can be e ectively used for global HTTP distribution exhibiting good performance in the wide range of load.

PL

W artykule prezentowana jest nowa metoda i algorytm globalnej dystrybucji żądań HTTP w sieci WWW nazwana GARDIB (ang. Global Request Distribution with Broker) charakteryzującego się specyficznym rozmyto-neuronalnym schematem decyzyjnym oraz czasem odpowiedzi jako kryterium jakości dystrybucji. Metoda i algorytm mogą znaleźć zastosowanie w rozproszonych systemach dostarczania treści webowych zwanych sieciami CDN (ang. Content Delivery Network). System opiera swoje działanie na ustalonej w metodzie współpracy klientów, serwisów webowych oraz pośredników - serwerów pośredniczących, zwanych brokerami.Klienci - są˛ końcowymi użytkownikami systemu, i w omawianym systemie są źródłem żądań HTTP. Serwisy webowe - zwane Serwisami Lokalnymi (ang. Local Services - LS) są rozproszonymi i autonomicznie działającymi klastrami zestawów serwerowych o konstrukcji: serwer WWW - serwer bazodanowy, wyposażonymi w rozdzielacz sieciowy (przełącznik webowy). Serwery pośredniczące są˛głównymi elementami systemu. Ich rola˛ jest pośredniczenie w komunikacji klient serwer WWW, co jest realizowane w następujący sposób. Użytkownik kieruje swoje żądania HTTP za pośrednictwem brokera zlokalizowanego w najbliższym sąsiedztwie. Zakłada się, że opóźnienie czasowe występujące w tej komunikacji jest pomijalnie małe. Broker korzystając z algorytmu dystrybucji globalnej przekazuje żądanie do realizacji do jednego z ośrodków lokalnych, gdzie rozdzielacz sieciowy dokonuje ostatecznego wyboru serwera docelowego. Odpowiedź od tego serwera wraca do klienta poprzez lokalny rozdzielacz oraz broker. W pracy proponuje się, aby dystrybucja globalna była realizowana z wykorzystaniem algorytmu GARDiB działającego wg rozmyto-neuronalnego schematu decyzyjnego, który każde z przychodzących żądań kieruje do tego lokalnego serwisu webowego, dla którego został wyestymowany najkrótszy czas odpowiedzi. Jest to czas obserwowany z punktu widzenia brokera. Na czas odpowiedzi składa się czas niezbędny do przesłania żądania od brokera do serwisu lokalnego, czas obsługi lokalnej żądania oraz czas transferu odpowiedzi od ośrodka lokalnego do brokera. Możemy przyjąć, że jest to również czas odpowiedzi z punktu widzenia klienta końcowego, ze względu na założoną lokalizację brokerów, których może być odpowiednio dużo zlokalizowanych blisko klientów, np. w ich domenach. Specyfiką tej metody jest zastosowanie po raz pierwszy w literaturze przedmiotu podejścia rozmyto-neuronalnego do globalnej dystrybucji żądań HTTP oraz wykorzystanie czasu odpowiedzi jako kryterium wydajności, co jest również unikatowym indeksem w problemie dystrybucji żądań HTTP, gdzie zazwyczaj stosowane są indeksy charakteryzujące poziom obciążenia serwerów, a celem dystrybucji jest wtedy np. równoważenie obciążeń serwerów.W systemie globalnej dystrybucji żądań GARDiB, w niniejszym artykule proponuje się aby w ośrodkach lokalnych działał autorski lokalny algorytm dystrybucji FNRD (ang. Fuzzy- Neural Request Distribution), który funkcjonuje również wg koncepcji sterownika rozmyto neuronalnego z kryterium czasu wykonania żądania, i który wielokrotnie wykazywał się swoimi dobrymi właściwościami w przeprowadzonych badaniach. W szczególności, wyszedł on obronną ręką w porównaniach ze znanymi algorytmami lokalnej dystrybucji żądań, takimi jak algorytm karuzelowy RR (ang. Round-Robin), LARD (ang. Locality-Aware Request Distribution) oraz CAP (ang. Content-Aware Policy). Dla potrzeb przeprowadzenia badań porównawczych w brokerze zasymulowano karuzelowy algorytm globalnej dystrybucji żądań RR oraz jego uogólnioą wersję z wagami, czyli algorytm WRR (ang. Weighted Round-Robin). W tym ostatnim przypadku badane są˛ dwa warianty algorytmu karuzelowego ważonego, a mianowicie wariant WRR-L - algorytm karuzelowy ważony ze względu na obciążenie Serwisów Lokalnych oraz wariant WRR-T - algorytm karuzelowy ważony ze względu na transfer na trasie pomiędzy LS a serwerem pośredniczącym. Do badań wykorzystane zostało środowisko symulacyjne, stworzone w języku C++ z wykorzystaniem bibliotek CSIM19, służących do programowania zadań symulacji zdarzeń dyskretnych. Artykuł pokazuje, że metoda oraz algorytmGARDiB mogą być z powodzeniem wykorzystywane do globalnej dystrybucji żądań w rozwiązaniach z serwerami pośredniczącymi, oraz że system globalnej dystrybucji treści wykorzystujący zaproponowaną metodę oraz algorytm dostarcza swoim użykownikom żądane treści w zadawalającym czasie - krótszym niż w przypadku pozostałych klasycznych algorytmów dystrybucji.

Słowa kluczowe

EN

HTTP request distribution; WWW server; simulation

• Wydawca: Instytut Informatyki Teoretycznej i Stosowanej Polskiej Akademii Nauk
• Czasopismo: Theoretical and Applied Informatics
• Rocznik: 2008
• Tom: Vol. 20, No. 1
• Strony: 15--27
• Opis fizyczny: Bibliogr. 17 poz., rys.

Twórcy

autor

Borzemski L.

autor

Zatwarnicka A.

autor

Zatwarnicki K.

• Institute of Information Science and Engineering Wrocław University of Technology Wybrzeże St. Wyspiańskiego 27, Wrocław, Poland,

Bibliografia

• [1] M.F. Arlitt, R. Friedrich, T. Jin: Workload characterization of a Web proxy in a cable modem environment, ACM Performance Evaluation Review, 27(2): pp. 25-36, Aug. 1999.
• [2] M. Aron, P. Druschel, W. Zwaenpoel: E#cient support for P-HTTP in clusterbased Web servers. Proc. of Usenix Annual Technical Conference, pp. 185-198, 1999.
• [3] N. Bhatti, A. Bouch, A. Kuchinsky: Integrating user-perceived quality into Web server design. Proc. of the 9th International World-Wide Web Conference, pp. 1-16, May 2000.
• [4] L. Borzemski, K. Zatwarnicki: Using adaptive fuzzy-neural control to minimize response time in cluster-based Web systems. Proceeding of 3rd Atlantic Web Intelligence Conference, Poland, Łód´z. Lecture Notes in Computer Science, Springer, Berlin, pp. 63-68, 2005.
• [5] L. Borzemski, K. Zatwarnicki: Performance evaluation of fuzzy-neural HTTP request distribution for Web clusters. Proc. of 8th International Conference Artificial Intelligence and Soft Computing - ICAISC 2006. Lecture Notes in Computer Science, Springer, pp. 192-201, 2006.
• [6] L. Borzemski, A. Zatwarnicka, K. Zatwarnicki: Global adaptive request distribution with broker. Proc. of 11th International Conference on Knowledge-Based and Intelligent Information & Engineering Systems, Lecture Notes in Computer Science 4693, Springer, pp. 271-278, 2007.
• [7] v. Cardellini, E. Casalicchio, M. Colajanni, M. Mambelli: Web switch support for di#erentiated services. ACM Perf. Eval. Rev., Vol. 29, No. 2 (2001), pp. 14-19.
• [8] V. Cardellini, E. Casalicchio, P.S. Yu: The state of the art in locally distributed Web-server systems. ACM Computing Surveys, vol.34, no 2, pp. 263-311, 2002.
• [9] E. Casalicchio: Cluster-based Web Systems: Paradigms and Dispatching Algorithms. PhD Thesis. [@:]http://www.ce.uniroma2.it/publications/PhDThesiscasa.ps. Universit? di Roma “Tor Vergata”, 2002.
• [10] E. Casalicchio, M. Colajanni: A client-aware dispatching algorithm for Web cluster providing multiple services. Proc. of 10th World Wide Web Conference, Hong Kong, pp. 535-544, May 2001.
• [11] E. Casalicchio, S. Tucci: Static and dynamic scheduling algorithm for scalable Web server farm. Proc. of 9th Euromicro Workshop on PDP, Italy, pp. 369-376, 2001.
• [12] CSIM [@:] http://www.mesquite.com.
• [13] T. Czachórski: Modele kolejkowe w ocenie efektywno´sci sieci i systemów komputerowych. Wydawnictwo Pracowni Komputerowej Jacka Skalmierskiego, Gliwice, 1999.
• [14] D.A. Menasce, V.A.F. Almeida: Capacity planning for Web performance. Metrics, Models, and Methods. Prentice Hall, New York, USA, 2002.
• [15] V.S. Pai, M. Aron, G. Banga, M. Svendsen, P. Druschel, W. Zwaenpoel, E. Nahum: Locality-aware request distribution in cluster-based network servers. Proc. of 8th ACM Conference On Architectural Support for Programming Languages and Operating Systems, pp. 205-216, 1998.
• [16] Pcap [@:] http://www.tcpdump.org/pcap.htm
• [17] Wget [@:] http://www.gnu.org/software/wget/