Моделирование переноса и поиска данных в децентрализованной распределенной системе, использующей N-k-схему хранения информации тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Петров, Виктор Анатольевич

• Петров, Виктор Анатольевич
• кандидат физико-математических наук
• 2008

Оглавление диссертации кандидат физико-математических наук Петров, Виктор Анатольевич

Введение.

1. Актуальность темы.

2. Цель работы, задачи исследования.

3. Научная новизна.

4. Практическая ценность.

5. Краткое содержание работы.

I. Обзоры существующих систем.

1. Системы хранения данных.

Google File System (GFS).

Pastry.

Beehive.

2. Системы доставки информации.

Akamai.

Border Gateway Protocol (BGP).

Выбор ближайшего веб-сервера.

3. Методики моделирования.

Моделирование распределенных систем управления с помощью марковских процессов.

Моделирование распределенных систем с помощью сетей Петри.

И. Модели распределенной системы.

1. Круг рассматриваемых систем.

Предпосылки.

Схема хранения файлов.

2. Имитационная модель.

Обозначения.

Передача данных.

Усеченное нормальное распределение.

3. Теоретическая модель.

III. Прогнозирование длительности поиска.

1. Процедура получения файла.

Обоснование выбора.

Описание процедуры.

2. Постановка задачи.

3. Вывод времени поиска.

1. Обозначения.

2. Время поиска.

4. Особенности практического использования выведенного.

1. Метод расчета.■.

2. Выбор начальных параметров.

5. Пример использования.

1. Условия расчета.

2. Представление результатов.

3. Результаты.

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

1. Базовые понятия. a) Регулярность структуры. b) Точечная загруженность.

2. Математическая постановка.

3. Имитационное моделирование.

4. Теоретическая оценка.

5. Результаты.

V. Длительность миграции.

1. Задача о миграции.

Базовые термины.

Два этапа миграции.

Математическая постановка.

2. Оценка длительности миграции.

Имитационная.

Теоретическая.

3. Сложность алгоритмов.

Имитационного.

Теоретического.

4. Пример.

Выбор распределений.

Распределенная система.

Результаты.

VI. Перенос задания в вычислительной системе.

1. Задача о переносе.

Актуальность задачи.

Модель вычислительной распределенной системы.

Модель компьютера.

Предположения и допущения.

Постановка задачи.

Введение диссертации (часть автореферата) на тему «Моделирование переноса и поиска данных в децентрализованной распределенной системе, использующей N-k-схему хранения информации»

Общая схема.84

Сетевые расходы.85

Вычисление задержки.85

Функции потребления ресурсов. Вычисление постоянного члена.92

Заключение.97

Список использованных источников.99

Приложение А. Альтернативный способ расчета вероятностей в математической модели поиска данных.111

Введение.

1. Актуальность темы.

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

Главное преимущество децентрализованных распределенных систем перед имеющими ярко выраженный центральный узел - отказоустойчивость. Причем с развитием сетевой инфраструктуры возрастает важность этого свойства, побуждая активное расширение этого класса распределенных систем. iV-fc-схема хранения данных позволяет собирать разбитый на N порций файл из любых к из них. Это компромисс между избыточностью хранения и экономией свободного места, позволяющий гибко регулировать границу между ними. Схема начинает применяться в распределенных системах, получая все большее распространение.

Виртуальный сервер имитирует реальный: обрабатывает сетевые запросы от клиентов. Одной из самых существенных характеристик реального сервера является его доступность. В любой момент времени он должен быть готовым обработать поступивший запрос. Длительность миграции виртуального сервера - это то время, в течение которого он будет недоступным для клиентов. Поэтому крайне важно знать оценку этой величины. На основе этой оценки может приниматься решение о том, производить миграцию или нет.

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

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Петров, Виктор Анатольевич

Приведем в заключение основные результаты и выводы работы:

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

2. Предложена математическая модель процедуры поиска файла в децентрализованной распределенной системе с регулярной структурой, использующей N-k-схсму для хранения данных. Полученные аналитические оценки средней длительности поиска подтверждены результатами имитационного моделирования.

3. С помощью математической и имитационной моделей получена зависимость средней длительностей поиска файла от уровня загруженности сети. Определен пороговый уровень загруженности.

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Петров, Виктор Анатольевич, 2008 год

1. Хасин М.А. Модель распределенного хранилища в глобальной сети. //

2. Работа на соискание степени кандидата физико-математических наук. -М.: МФТИ, 2001 -93 с.

3. Чернова Н.И. Теория вероятностей: Курс лекций, pdf. (http ://www.nsu.Ri/mmf/tvims/chernova/tv/portr.pdf).

4. Гнеденко Б.В. Курс теории вероятностей, М.: Наука, 1988 - 448 с.

5. Rowstron, P. Druschel Pastry: Scalable, decentralized object location and routing for large-scale peer-to-peer systems, pdfj (http://research.microsoft.com/~antr/PAST/pastry.pdf).

6. Pastry, html. (http://en.wikipedia.org/wiki/Pastry %28DHT%29).

7. Ramasubramanian V., Sirer E. G. Beehive: 0(1) Lookup Performance for Power-Law Query Distributions in Peer-to-Peer Overlays, pdf. (http .7/www.cs. Cornell. edu/People/egs/papers/beehive .pdf).

8. Ghemawat S., Gobioff H., Leung S.T. The Google File System, pdf. (http://labs.google.com/papers/gfs-sosp2003.pdf).

9. Strickland, Jonathan, How the Google File System Works, HowStuffWorks.com, 2008, html. (http://communication.howstuffworks.coi'n/google-file-system.htm).

10. Google File System, http://en.wikipedia.org/wiki/GoogleFileSystem.

11. A Distributed Infrastructure for e-Business Real Benefits, Measurable Returns. - Akamai White Paper, October 2001, html., (www.akamai.com).

12. Ratul Mahajan, Akamai, html. (http://research.microsoft.com/-ratu1/akairiai.html).

13. Border Gateway Protocol, html. (http://www.cisco.com/univercd/cc/td/doc/cisintwk/ito doc/bgp.htm#l 020583 )•

14. BGP4 Case Studies/Tutorial, Sam Halabi, cisco Systems, html. (http://www.ittc.ku.edu/EECS/EECS 800.ira/bgp tutorial4).

15. BGP • Fundamentals, html. (http://www.riverstonenet.coin/support/bgp/fimdaiTientals').

16. Yair Amir, AlecPeterson, David Show, Seamlessly selecting the best copy from Internet-wide replicated web-servers, Johns Hopkins University, html. (http://citeseerx. ist.psu.edu/viewdoc/summ ary?doi=l 0.1.1.40.6523).

17. Google Dance The Index Update of the Google Search Engine, html. fhttp://dance.efactory.de/).

18. Yair Amir and Ciprian Tutu. From total order to database replication. Proceedings of the International Conference on Distributed Computing Systems, Johns Hopkins University, November 2001, html. (www.cnds.jhu.edu./publications).

19. C.C. Бежитский, E.C. Семенкин Эволюционные алгоритмы для автоматизации проектирования распределенных систем обработкиинформации и управления, doc. (raai.org/resurs/papers/kii-2006/seminar/Bezhitskiy.doc).

20. Беэюитский С.С. Выбор оптимальной , структуры аппаратно-программного комплекса системы управления движением автомобильного транспорта, // Вестник университетского комплекса: Сб. научных трудов Вып. 6 (20). - Красноярск: ВСФ РГУИП, НИИ СУВПТ, 2005.

21. Семенкин Е.С., В.Л. Лебедев Методы обобщенного адаптивного поиска для синтеза систем управления сложными системами. М.: МАКС Пресс, 2002.

22. И. А. Ломазова Вложенные сети Петри и моделирование распределенных систем, pdf. (http://www.botik.ru/PSI/disk 20/e-book/e-book/l-4/02-Lomazo va-Vlozhennve-seti-p-337.pdf).

23. И.Котов В. Е. Сети Петри, — М: Наука, 1984 160с.

24. Smith Е. Principles of high-level net theory. // Lectures on Petri Nets: Advances in Petri Nets Lecture Notes in Computer Science. M: Springer Berlin / Heidelberg, 1998, pp. 174-210, html. (http://www.springerlink.eom/content/78125201814583v8).

25. Pinheiro E. Truly-Transparent Checkpointing of Parallel Applications // Federal University of Rio de Janeiro, UFRJ., 2002., ps. (ftp://ftp.inria.fr/INRIA/publication/publi-ps-gz/RR/IlR-5755.ps.gzy

26. OpenVZ, html. (httpy/openvz.orgl.

27. Xen, html. (http://www.xen.org),

28. VMware, Inc. html. (http://www.vmware.com).

29. The Sprite Operating System., html. (http://www.eecs.berkelev.edu/Research/Proiects/CS/sprite/sprite.html').

30. Петров В.А. Доставка информации пользователю в распределенных системах. // Совр. проблемы фундаментальных и прикладных наук. Управление и прикладная математика: Труды XL VIII научной конференции. / МФТИ М.: Долгопрудный, 2005. - С. 43.

31. Петров В.А., Тормасов А.Г. Доставка информации пользователю в распределенных системах // Проблемы выч. математики, мат. моделирования и информатики, сборник научных трудов, М.: МЗ Пресс, 2006, С. 156-194.

32. АО.Петров В.А., Тормасов А.Г. Перенос задания в вычислительной системе // Моделирование и обработка информации, сборник научных трудов -М.: МФТИ, 2008. С. 207-216.

33. Петров В.А., Тормасов А.Г. Миркин A.JI. Длительность миграции виртуальных серверов в распределенной системе // Вестник НГУ. Серия: Информационные Технологии. 2008 - Т.6, вып. 3. - С. 38-57.

34. Lustre documentation, pdf. fhttp://wiki.lustre.org/index.php?title^LustreDocumentationy

35. Lustre: A Scalable, High-Performance File System, white paper, http://www.sun.com/servers/hpc/docs/lustrefilesvstem wp.pdf.

36. Peter Druschel, Antony Rowstron, PAST: A large-scale, persistent peer-to-peer storage utility, Rice University, Houston, USA, pdf. (http://frazer.rice.edu/epit/documents/peter/PAST-hotos.pdf).

37. Antony Rowstron, Peter Druschel, Storage management and caching in PAST, a large-scale, persistent peer-to-peer storage utility, Microsoft Research, pdf. (http://research.microsoft.com/~antr/PAST/past-sosp.pdf).

38. A. Rowstron, A-M. Kermarrec, M. Castro and P. Druschel. SCRIBE: The design of a large-scale event notification infrastructure, London, November 2001, pdf. (http://research.microsoft.com/~antr/PAST/scribe.pdf).

39. Castro, M. B. Jones, A-M. Kermarrec, A. Rowstron, M. Theimer, H. Wang and A. Wolman, An Evaluation of Scalable Application-level Multicast Built Using Peer-to-peer overlays, 2003, pdf. rhttp://research.microsoft.com/~antr/P AST/in focom-compare.pdf).

40. B. Y. Zhao, J. D. Kubiatowicz, A. D. Joseph. Tapestry: An infrastructure for fault-resilient wide-area location and routing, Berkeley, April 2001, pdf.http://oceanstore.cs.berkeley.edu/publications/papers/pdf/tapestrysigcomm tr.pdf).

41. Xiaofeng Ren and David Liu, Smart Routing in the Tapestry Routing/Location Infrastructure, pdf. (http://www.cs.berkeley.edu/-kubitron/coiirses/cs252-FOO/proiects/reports/proiectlO report.pdf).

42. Zhao, B.Y.; Ling Huang; Stribling, J.; Rhea, S.C.; Joseph, A.D.; Kubiatowicz, J.D. Tapestry: a resilient global-scale overlay for service deployment 11 Selected Areas in Communications, IEEE Journal on Volume 22, Issue 1, Jan. 2004 Page(s): 41-53.

43. Beehive implementation, html. (http://www.usenix.org/events/nsdi04/tecli/full papers/ramasubramanian/ram asubramanian html/node7 .html).

44. V.Ramasubramanian, E.G. Sirer Beehive: Achieving 0(1) Lookup. Performance in P2P Overlays for. Zipf-like Query Distributions, pdf. (https://research.microsoft.com/users/rama/Beehive/beehive(nsdi).talk.pdf).

45. Stoica, R. Morris, D. Karger, M. Frans Kaashoek, H. Balakrishnan Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications, pdf. (http://pdos.csail.mit.edU/papers/chord:sigcomm01/chord sigcomm.pdf).

46. Chord project, html. (http://pdos.csail.mit.edu/chord/\

47. J. Kubiatowicz, D. Bindel, P. Eaton, Y. Chen, D. Geels, R. Gummadi, S. Rhea, W. Weimer, C. Wells, H. Weatherspoon, B. Zhao Oceanstore: An architecture for globalscale persistent store. // Proceedings of ACM ASPLC)S'2000, Cambridge, MA, November 2000.

48. S. Rhea, C. Wells, P. Eaton, D. Geels, B. Zhao, H. Weatherspoon, J. Kubiatowicz. Maintenance-free global storage in OceanStore. // Submission to IEEE Internet Computing, 2001.

49. The OceanStore Project, html. fhttp://oceanstore.cs.berkelev.eduA

50. S. Ratnasamy, P. Francis, M. Handley, R. Karp, S. Shenker A scalable content-addressable network. // Proceedings of ACM SIGCOMM'Ol, San Diego, CA, Aug. 2001.

51. P. Fraigniaud, P. Gauron, The Content-Addressable Network D2B, 2003, pdf.fhttp://citeseer.ist.psu.edu/cache/papers/cs/30136/http:zSzzSzwww.lri.frzSz~pierrezSzPOSTSCRIPTSzSzTech-Report1349.pdfyfraigniaud03contentaddressable.pdf).

52. Vedran Kordic Petri Net: Theory and Applications. M.: I-Tech Education and Publishing, 2008.-534 c.

53. Clarke, O. Sandberg, T. W. Hong, B. Wiley Freenet: A Distributed Anonymous Information Storage and Retrieval System, pdfj Qittp://www.cl.cam.ac.uky~twh25/academic/papers/icsi-revised.pdf).

54. The Free Network Project, html. (http://freenetproiect.orR/).68./. Clarke, T. Hong, S. Miller, O. Sandberg, B. Wiley Protecting free expression online with freenet. // IEEE Internet Computing, 6:40-49, 2002.

55. Ian Clarke, Freenet's Next Generation Routing Protocol, July 2003, html. fhttp: //freenetpro i ect. or g/n grouting, html).

56. E. Adar, B. Huberman, Free riding on gnutella, October 2000, pdf. fhttp://www.hpl.hp.com/researcli/idl/papers/gnutella/gnutella.pdf).

57. Clip2, "Gnutella measurement project," May 2001. html. (littp ://www. clip2. com/).

58. R. Anderson. The Eternity service. // Proceedings of PRAGOCRYPT'96, pages 242-252. CTU Publishing House, 1996. Prague, Czech Republic.

59. Brown. Eternity service design. html.,http://www.cvpherspace.org/eternitv-design.htmlY

60. Farsite Project, html. (http://research.microsoft.com/farsite/).

61. J. R. Douceur, A. Adya, J. Benaloh, W. J. Bolosky, G. Yuval; Proceedings of the 18th ACS AC, December 2002, pdf. (http://research.microsoft.com/farsite/ACSAC2002.pdf).

62. SQ.B.Pawlowski, C.Juszczak, P.Staubach, C. Smith, D.Lebel, D.Hitz. NFS version 3 design and implementation. //Proceedings of the Summer USENIX Conference, pages 137-152, June 1994.

63. Network File System, html.http://www.redhat.com/docs/manuals/linux/RHL-9-Manual/ref-guide/ch-nfs.html).

64. InterMezzo, 2003, html. fhttp.V/www.inter-mezzo.org).

65. Bill von Hagen, Using the InterMezzo Distributed Filesystem. Getting Connected in a Disconnected World html. (http ://www. linuxplanet. com/linuxplanet/reports/4368/1 /).

66. Coda File System, html. (http://www.coda.cs.emu.edu/).

67. Peter J. Braam, The Coda Distributed File System, Carnegie Mellon University, html. (http://www.coda.cs.cmu.edu/lipaper/li.htmn.

68. Peter J. Braam, Coda Authentication and Protection, html. ditto ://www. coda, cs. emu, edu/ doc/html/sec. html).87A. Tanenbaum, Distributed Operation Systems, M: Prentice Hall, 1995.

69. Ван Стеен Маартен Распределенные системы. Принципы и парадигмы -М: Питер, 2003.-880 с.89.7". Кормен, Ч. Лейзерсон, Р. Ривест Алгоритмы: построение и анализ -М.: Москва, 2004 960 с.

70. Кудрявцев Л.Д. Курс математического анализа М. Наука, 1981, т.1,2.

71. Laszlo Lovasz, Computation Complexity. pdf. fhttp://www.cs.bu.edu/~gacs/papers/lovasz-notes.pdf).