Разработка методов и алгоритмов для автоматизированного распределения нагрузки производственного кластерного WEB-сервера тема диссертации и автореферата по ВАК РФ 05.13.06, кандидат технических наук Зар Ней Лин

• Зар Ней Лин
• кандидат технических наук
• 2009

Оглавление диссертации кандидат технических наук Зар Ней Лин

СПИСОК СОКРАЩЕНИЙ

ВВЕДЕНИЕ

1. АНАЛИЗ АРХИТЕКТУРЫ КЛАСТЕРНЫХ WEB-CEPBEPOB

Особенности архитектуры кластерных web-серверов

1 .'1.1. Архитектура кластерных систем

1.1.2. Области применения кластерных систем

1.1.3. Преимущества кластерных web-серверов

1.2. Классификация кластерных web-серверов

1.2.1. Классификация по способам маршрутизации

1.2.2. Классификация по способам распределения нагрузки

1.2.3. Классификация по способам кэширования данных

ВЫВОДЫ

2. КОНТЕНТНО-ЗАВИСИМЫЙ АЛГОРИТМ РАСПРЕДЕЛЕНИЯ НАГРУЗКИ ДЛЯ КЛАСТЕРНОГО WEB-CEPBEPA

2.1. Анализ алгоритмов распределения нагрузки кластерных web-серверов

2.1.1. Общая характеристика алгоритмов распределения нагрузки—

2.1.2. Алгоритмы распределения нагрузки четвертого уровня модели

2.1.3. Алгоритмы распределения нагрузки седьмого уровня модели OSI

2.2. Разработка контентно-зависимого алгоритма распределения нагрузки

2.2.1. Общая характеристика алгоритма

2.2.2. Формальное описание алгоритма

2.2.3. Анализ сценариев работы алгоритма

2.3. Анализ производительности контентно-зависимого алгоритма распределения нагрузки

2.3.1. Аналитическая модель алгоритма

ВЫВОДЫ

3. ПОДСИСТЕМА РАСПРЕДЕЛЕНИЯ НАГРУЗКИ ДЛЯ КЛАСТЕРНОГО WEB-CEPBEPA

3.1. Структура подсистемы распределения нагрузки

3.1.1. Общая структура

3.1.2. Узел распределения нагрузки

3.1.3. Узел предварительного кэширования

3.2. Реализация подсистемы распределения нагрузки на кластере компьютеров

3.2.1. Требования к формальному протоколу для представления подсистемы распределения нагрузки

3.2.2. Общие процедуры MPI (Интерфейс передачи сообщения)

3.2.3. Реализация подсистемы распределения нагрузки

ВЫВОДЫ

4. ИССЛЕДОВАНИЕ ПОКАЗАТЕЛЕЙ ФУНКЦИОНИРОВАНИЯ WEB-CEPBEPA НА ИМИТАЦИОННОЙ МОДЕЛИ

4.1. Математический аппарат имитационного моделирования

4.1.1. Сети Петри

4.1.2. Расширенные сети Петри

4.2. Имитационная модель входной нагрузки

4.2.1. Характеристика входной нагрузки web-сервера

4.2.2. Имитационная модель входной нагрузки

4.3. Имитационная модель подсистемы распределения нагрузки

4.3.1. Модель диспетчера web-сервера

4.3.2. Модель узла web-сервера

4.3.3. Результаты имитационных экспериментов

ВЫВОДЫ

Введение диссертации (часть автореферата) на тему «Разработка методов и алгоритмов для автоматизированного распределения нагрузки производственного кластерного WEB-сервера»

Актуальность проблемы. В настоящее время эффективное функционирование любой автоматизированной системы управления производством и, в частности, автоматизированной системы управления технологическим процессом (АСУТП), возможна только с применением информационных технологий. Это приносит значительные преимущества с точки зрения производительности труда и конкурентоспособности.

В связи с постоянным усложнением задач современного автоматизированного производства весьма актуальной становится задача создания автоматизированных производственных систем с использованием кластерных web-серверов.

Интенсивное развитие сети Интернет ставит проблемы увеличения производительности, надежности и доступности кластерных информационных систем, в том числе кластерных web-серверов. Один из способов решения указанных проблем - применение репликации. Однако использование репли-цированных данных требует наличия эффективных алгоритмов и программных средств управления данными, в частности, алгоритмов распределения нагрузки и протоколов распространения обновлений.

Теоретическим исследованиям и разработке фундаментальных основ распределения нагрузки, созданию математического аппарата, моделей и методов для автоматизированного распределения нагрузки в кластерных web-cepBepax посвящены труды видных ученых R. Mukherjee, G. Banga, V. Cardellini, Е. Casalicchio и многих других.

Однако существующие алгоритмы распределения нагрузки web-сервера обладают рядом недостатков, в частности: низкое быстродействие, низкая интеллектуальность распределения нагрузки, не учитывающая динамические файлы.

В связи с этим актуальной является разработка методов и алгоритмов для автоматизированного распределения нагрузки производственного кластерного web-сервера.

Целью диссертационной работы является разработка методов и алгоритмов для автоматизированного распределения нагрузки производственного кластерного web-сервера, обеспечивающей повышенную отказоустойчивость, производительность и надежность кластерного web-сервера.

В соответствии с указанной целью в работе решаются следующие задачи:

- анализ архитектуры кластерных web-серверов;

- разработка контентно-зависимого алгоритма (КЗА) распределения нагрузки;

- анализ производительности КЗА распределения нагрузки;

- программная реализация подсистемы распределения нагрузки на вычислительном кластере;

- имитационное моделирование и экспериментальное исследование показателей функционирования кластерного web-сервера.

Методы исследования. Для решения сформулированных задач использовались методы теории графов, сетей Петри, теории систем массового обслуживания, теории вероятностей, аналитического и имитационного моделирования дискретных систем.

Научная новизна. Разработанные алгоритмы и программные средства учитывают специфику построения информационных систем на кластере компьютеров, а также обеспечивают повышенную отказоустойчивость, производительность и надежность web-сервера. В отличие от большинства существующих, разработанные алгоритмы являются интеллектуальными, поскольку учитывают при распределении нагрузки не только текущее распределение соединений по компьютерам кластера, но и содержание запросов пользователей. Кроме того, разработанные алгоритмы дают выигрыш снижения времени ответа кластерного Web-сервера.

В процессе работы над диссертацией получены следующие новые научные результаты:

1. Разработан и реализован эффективный интеллектуальный контентно-зависимый алгоритм распределения нагрузки для кластерного web-сервера, учитывающий запросы не только к статическим, но и к динамическим web-страницам.

2. Разработана имитационная модель подсистемы распределения нагрузки для кластерного web-сервера на основе математического аппарата расширенных сетей Петри. Результаты работы имитационной модели подтверждают, что разработанный алгоритм обеспечивает повышение производительности на 35 % по сравнению с алгоритмом WRR и на 55 % по сравнению с алгоритмом LARD.

3. Разработана имитационная модель Интернет-трафика на основе математического аппарата расширенных сетей Петри, которая может быть использована для задания входной нагрузки при имитационном моделировании web-серверов с целью разработки алгоритмов диспетчиро-вания и распределения нагрузки.

4. Предложена методика расчета времени обслуживания для различных категорий ресурсов web-систем.

Достоверность полученных результатов. Достоверность полученных в ходе работы над диссертацией научных результатов подтверждается успешными результатами имитационного моделирования, подтвердившими преимущества предложенных методов и алгоритмов.

Практическая ценность работы Применение разработанного алгоритма и подсистемы распределения нагрузки в кластерных информационных системах позволяет: уменьшить время ответа; повысить пропускную способность и доступность информационной системы; увеличить надежность системы в целом.

Разработанный алгоритм обеспечивает повышенную отказоустойчивость, производительность и надежность Web-cepBepa, а также снижение времени ответа кластерного Web-сервера. Разработанный алгоритм даёт выигрыш производительности на 35 % по сравнению с алгоритмом WRR (Weighted Round Robin) и на 55 % по сравнению с алгоритмом LARD (Locality Aware Request Distribution). Фактически, при использовании разработанного алгоритма время ожидания не превышает 2-х секунд, в то время как для алгоритма WRR оно составляет приблизительно 7 секунд, а для алгоритма LARD -приблизительно 20 секунд.

Самостоятельное практическое значение имеет разработанная имитационная модель Интернет-трафика, которая может быть использована для задания входной нагрузки при имитационном моделировании web-серверов с целью разработки алгоритмов диспетчирования и распределения нагрузки.

Личный вклад автора. Все основные результаты диссертационной работы получены лично автором, в частности:

1. Исследованы архитектуры кластерных web-серверов и проведена их классификация.

2. Разработан контентно-зависимый алгоритм распределения нагрузки кластерного web-сервера.

3. Разработана математическая модель для расчета времени обслуживания предлагаемого алгоритма.

4. Создана программа реализации подсистемы распределения нагрузки на кластере компьютеров.

5. Разработана имитационная модель входной нагрузки web-сервера.

6. Разработана имитационная модель распределения нагрузки для кластерного web-cepBepa.

Внедрение результатов работы. Все работы по реализации и внедрению проводились при непосредственном участии автора. Результаты диссертационной работы используются в учебном процессе кафедры ИПОВС Московского государственного института электронной техники.

В результате проведенных исследований получены и выносятся на защиту следующие основные научные результаты:

1. Контентно-зависимый алгоритм распределения нагрузки для кластерного web-cepBepa.

2. Формализованное представление входной нагрузки кластерного web-сервера.

3. Программная реализация алгоритма распределения нагрузки кластерного web-cepBepa.

4. Имитационная модель подсистемы распределения нагрузки кластерного web-cepBepa.

5. Результаты внедрения, экспериментальных исследований и апробация материалов диссертационной работы.

Апробация работы и публикации. Основные положения диссертационной работы докладывались и обсуждались на следующих конференциях:

1. Международная школа-конференция (по приоритетному направлению «Информационно-телекоммуникационные системы» с участием молодых ученых, аспирантов и студентов стран-членов СНГ) - Москва, МИЭТ, 2005.

2. 13-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов "Микроэлектроника и информатика - 2006" -Москва, МИЭТ, 2006.

3. 14-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов "Микроэлектроника и информатика - 2007" -Москва, МИЭТ, 2007.

4. XI Московская международная телекоммуникационная конференция студентов и ученых «Молодежь и наука» - Москва, МИФИ, 2008.

По результатам исследований опубликовано 9 печатных работ, в том числе одна статья в издании, входящем в перечень ВАК.

Структура и объем работы. Диссертация состоит из введения, 4 глав, заключения, списка литературы и приложений, содержащих листинги про

Заключение диссертации по теме «Автоматизация и управление технологическими процессами и производствами (по отраслям)», Зар Ней Лин

ВЫВОДЫ

Разработана имитационная модель подсистемы распределения нагрузки, использующей предложенный алгоритм КЗА, представленный в главе 2, на основе математического аппарата сетей Петри. Эксперименты с моделями выполнены при помощи программного средства моделирования Winsim.

Создана имитационная модель подсистемы распределения нагрузки для кластерного web-cepBepa на основе математического аппарата сетей Петри. Для получения пульсирующего трафика предлагается использовать в модели суперпозицию четырех IPP-источников, причем каждый IPP-источник охватывает различный интервал времени — от секунд до дней. Представлена имитационная модель алгоритма распределения нагрузки на основе формального математического аппарата сетей Петри. Данные результатов экспериментов совпали с данными, полученными с помощью аналитической модели.

Результаты проведенных имитационных эксперимертов подтвердили, что алгоритм КЗ А улучшает работу web-кластера на 35 % по сравнению с алгоритмом WRR и на 55 % по сравнению с LARD. Фактически, при 90-процентном времени ожидания страницы, при использовании алгоритма КЗА время ожидания страницы меньше, чем 2 секунды, в то время ожидания страницы равно приблизительно 7 секунд для алгоритма WRR и приблизительно 20 секунд для алгоритма LARD.

ЗАКЛЮЧЕНИЕ

В ходе выполнения диссертационной работы предложены новые эффективные методы и алгоритмы для автоматизированного распределения нагрузки производственного кластерного web-сервера.

При этом получены следующие основные научные и практические результаты.

1. Разработан новый интеллектуальный контентно-зависимый алгоритм распределения нагрузки для производственного кластерного web-сервера, учитывающий запросы не только к статическим, но и к динамическим web-страницам.

2. Разработана имитационная модель подсистемы распределения нагрузки для производственного кластерного web-сервера на основе математического аппарата расширенных сетей Петри.

3. Обосновано, что применение разработанного алгоритма и подсистемы распределения нагрузки в кластерных информационных системах позволяет: уменьшить время ответа; повысить пропускную способность и доступность информационной системы; повысить надежность системы в целом.

4. Разработана имитационная модель Интернет-трафика на основе математического аппарата расширенных сетей Петри, которая может быть использована для задания входной нагрузки при имитационном моделировании web-серверов с целью разработки алгоритмов диспетчеризации и распределения нагрузки.

5. Предложена методика расчета времени обслуживания для различных категорий ресурсов web-систем.

6. Результаты имитационного моделирования показали, что разработанный алгоритм даёт выигрыш производительности на 35 % по сравнению с алгоритмом WRR (Weighted Round Robin) и на 55 % по сравнению с алгоритмом LARD (Locality Aware Request Distribution).

7. Экспериментально установлено, что при использовании разработанного алгоритма время ожидания загрузки не превышает 2-х секунд, в то время как для алгоритма WRR оно составляет приблизительно 7 секунд, а для алгоритма LARD - около 20 секунд.

8. Результаты диссертационной работы внедрены в учебный процесс кафедры "Информатика и программное обеспечение вычислительных систем" Московского государственного института электронной техники (технический университет).

Список литературы диссертационного исследования кандидат технических наук Зар Ней Лин, 2009 год

1. Либман Л. Философия распределения нагрузки // Журнал сетевых решений LAN, 2000, с. 225.

2. Robert J.S. Windows Server 2003 Clustering & Load Balancing Hill .: Osborne McGraw.

3. Clark D., Blumenthal M. Rethinking the design of the Internet // The end to end arguments vs. the brave new world, August 2000.

4. Mcllraith S.T., Zeng Т.Н. Semantic Web Services // IEEE Intelligent Syestems, March/April 2001.

5. Stevens W.R. TCP/IP Illustrated, Volume 3: TCP for Transactions, HTTP, NNTP, and the UNIX Domain Protocols.

6. Либман Л. Философия распределения нагрузки // Журнал сетевых решений LAN, 2001, с. 350.

7. Cardellini V., Casalicchio Е., Colajanni М., Yu P.S. The State of the Art in Locally Distributed Web-server Systems // IBM Research Report, 2001, October.

8. Cardellini V., Colajanni M., Yu P.S. High-Performance Web-server Systems // IEEE Internet Computing, 1999, May-June.

9. Hunt G., Goldszmidt G., King R., Mukherjee R. Network Dispatcher: a connection router for scalable Internet service // Computer Networks and ISDN Systems, 1998, vol. 30.

10. Joseph G.D., Thomas F.L. Microsoft Windows Server 2003 TCP/IP Protocols and Services.

11. Richard W.S., Gary R.W. TCP/IP Illustrated Volume 2: The Implementation.

12. Hunt G., Nahum E., Tracey J. Enabling content-based load distribution for scalable services // Technical report, IBM T.J. Watson Research Center, 1997, May.

13. VeriSign fends off critics at ICANN confab. CNET News.com. Retrieved on 2007-09-22.

14. Mockapetris P. Domain Names Implementation and Specification.

15. Shivaratri N.G., Rrueger P., Singhal M. Load distributing for locally distributed systems // IEEE Computer, Dec. 1992, vol. 25, p. 33-44.

16. Postel J. R. File Transfer Protocol (FTP). Oct-1985.

17. Stierhoff G.C., Davis A.G. A History of the IBM Systems Journal // IEEE Annals of the History of Computing, Jan. 1998, vol. 20, № 1, p. 29-35.

18. Barish G., Obraczrf K. World Wide Web Caching: Trends and Techniques // IEEE Commun. Mag., 2000, vol. 38, no. 5. p. 178-184.

19. Cao P., Liu C. Maintaining Strong Cache Consistency in the World Wide Web // IEEE trans. Сотр., 1998, vol. 47, no. 4, p. 445-457.

20. Tewari R., Dahlin M., Vin H. Ray J. Design Considerations for Distributed Caching on the internet // Proc. 19th Conf on Distributed Computing Systems, IEEE, 1999. p. 273-284.

21. Wolman A., Voelker G., Sharma N., Cardwell N., Rarlin A., Levy H. On the scale and performance of Cooperative Web Proxy Caching // Proc. 17 Symp. Operating System Principles, ACM, 1999, p. 16-31.

22. Cao, P., Zhang J., and Beach K. Active Cache: Caching Dynamic Contents on the Web // Proc. Middleware '98. IFIP, 1998. p. 373-388.

23. Leighton F., Lewin D. Global Hosting System // United States Patent, № 6, Aug. 2000, p. 108.

24. Casavant T.L., Kuhl. J.G. A taxonomy of scheduling in general-purpose distributed computing systems // IEEE Trans. Softw. Eng., 1988, vol. 14, p. 141154.

25. Shirazi B.A., Hurson A.R., Ravi K.M. Scheduling and Load Balancing in Parallel and Dstributed Systems // IEEE Computer Soc., 1995, vol. 5, p. 120-130.

26. Shivaratri N.G., Rrueger P., Singhal M. Load distributing for locally distributed systems // IEEE Computer, Dec. 1992, vol. 25, p. 33-44.

27. Wang Y.T., Morris R.J. Load sharing in distributed systems // IEEE Trans. Computer, Mar. 1985, vol. 34, p. 204-217.

28. Kremier O., Kramer J. Methodical analysis of adaptive load sharing algorithms // IEEE Trans. Parall. Distrib. Syst., Nov. 1992, vol. 3, p. 747-760.

29. Dahlin M. Interpreting stale load information // IEEE Trans. Parall. Distrib. Syst., Oct. 2000, vol. 11, p. 1033-1047.

30. Cisco Systems. 2002. http://www.cisco.com.

31. F5 Networks. 2002. http://www.f5labs.com.

32. Linux Virtual Server project, http://www.linuxvirtualserver.org.

33. Foundry Networks. 2002. Foundry networks server iron. http://www.foundrynet.com/products/webswitches/serveriron.

34. Hunt G.D., Goldszmidn G.S., King R.P., Murherjee R. Network Dispatcher: A connection router for scalable Internet services // Computer Networks, 1998, vol. 30, p. 347-357.

35. Douglas E.C. Internetworking with TCP/IP: Principles, Protocols, and Architecture, 5th .: Prentice Hall., 2006.

36. Hunt G.D., Goldszmidn G.S., King R.P., Murherjee R. Network Dispatcher: A connection router for scalable Internet services // Computer Networks, 1998, vol. 30, p. 347-357.

37. Crovella M.E., Bestavros A. Self similarity in World Wide Web traffic: Evidence and possible causes // IEEE/ACM Trans. Networking, Dec. 1997, vol. 5, p. 835-846.

38. Harchol-Balter M., Crovella M.E., Murta C.D. On choosing a task assignment policy for a distributed server system // Parallel and Distributed Computing, 1999, vol. 59, p. 204-228.

39. Casalicchio E., Colajanni M. A client-aware dispatching algorithm for Web clusters providing multiple services // In Proceedings of the 10th International World Wide Web Conference (Hong Kong, May), ACM Press, New York, 2001, p. 535-544.

40. Stallings W.R. The Origins of OSI, 1998.

41. Charles W.B. Finding Aid. ANSI/SPARC/DISY // Charles Babbage Institute Center for the History of Information Technology, University of Minnesota.

42. David P., Garth A.G., Randy K. A Case for Redundant Arrays of Inexpensive Disks (RAID) // SIGMOD Conference, 1988, p. 109 -116.

43. ANSI Draft SASI Standard, Rev D, February 17, 1982, pg. ii states, "9/15/81 first presentation to ANSI committee X3T9-3 (2 weeks following announcement in Electronic Design)."

44. Microsoft Security Bulletin MS06-007: Vulnerability in TCP/IP Could Allow Denial of Service (913446).

45. International Technical Support Organization RS/6000 SP: Practical MPI Programming. August 1999.

46. Костин А.Е., Илюшечкина JI.B. Модифицированные Е-сети для исследования систем распределенной обработки информации // Автоматика и вычислительная техника, 1988, № 6, с. 27 35.

47. Arlitt М., Wiliamson С. Web Server Workload Characterization: The search for Invariants // Proc. ACM '96 SIGMETRICS Conf. Measurement Comput. Syst., Philadelphia, Pennsylvania, May 1996, p. 126 137.

48. Crovella M., Btstavros A. Self-Similarity in World Wide Web Traffic: Evidence and Possible Causes // IEEE/ACM Transactions on Networking, Dec. 1997.

49. Lenland W., Taqqu M., Willinger W., Wilson D. On the Self-Similar Nature of Ethernet Traffic // IEEE/ACM Trans. Commun. Techno., Feb. 1994.

50. Banga G., Druschel P. Measuring the Capacity of a Web Server // Proc. USENIX Symp. Internet Technol. Syst., Monterey, California, Dec. 1997.

51. V.S. Pai, M. Aron, G. Banga, M. Svendsen, P. Druschel, W. Zwaenepoel, E. Nahum. Locality-aware request distribution in cluster-based network servers // In Proc. of 8th ACM Conf. on Arch. Support for Progr. Languages, San Jose, CA, Oct. 1998.

52. G.D.H. Hunt, G.S. Goldszmidt, R.P. King, R. Mukherjee. Network Web switch: A connection router for scalable Internet services // Proc. of 7th Int. World Wide Web Conf., Brisbane, Australia, April. 1998.