Управление доступом к общим ресурсам в пиринговых системах тема диссертации и автореферата по ВАК РФ 05.13.13, кандидат технических наук Обейдат Атеф Ахмед
- Специальность ВАК РФ05.13.13
- Количество страниц 171
Оглавление диссертации кандидат технических наук Обейдат Атеф Ахмед
ВВЕДЕНИЕ.
ГЛАВА 1. КЛИЕНТСКИЕ РАСПРЕДЕЛЕННЫЕ СРЕДСТВА.
1.1. Клиентские информационно-вычислительные средства
1.2. Децентрализованные файловые пиринговые сети.
1.3. Классификация пиринговых сетей.
1.3.1. Структурированные пиринговые сети.
1.3.2. Неструктурированные пиринговые сети.
1.3.3. Сети с супер-узлами.
1.4. Проблема взаимного исключения в пиринговых сетях.
1.4.1. Вводные замечания.
1.4.2. Анализ существующих решений в распределенных системах
1.4.3. Подходы для решения проблемы взаимного исключения.
1.4.4. Показатели качества алгоритмов взаимного исключения.
1.5. Тиражирование и аутентичность и дубликатов объекта.
1.5.1. Тиражирование в структурированных пиринговых сетях.
1.5.2. Аутентичность дубликатов объекта.
1.6. Модель пиринговых сетей.
Рекомендованный список диссертаций по специальности «Телекоммуникационные системы и компьютерные сети», 05.13.13 шифр ВАК
Математическое моделирование средств управления ресурсами и данными в распределенных и виртуализованных средах2007 год, доктор физико-математических наук Тормасов, Александр Геннадьевич
Модель распределенного хранилища в глобальной сети2001 год, кандидат физико-математических наук Хасин, Михаил Александрович
Разработка методики и алгоритмов повышения эффективности взаимодействия сетевых приложений на верхних уровнях модели OSI2013 год, кандидат наук Городилов, Алексей Владиславович
Математическое и программное обеспечение асинхронной репликации данных реляционных СУБД методом выделения объектов2008 год, кандидат технических наук Апанасевич, Дмитрий Александрович
Методы и средства разработки компонентного управления Web - сайтом на основе динамической объектной модели2005 год, кандидат технических наук Быков, Михаил Юрьевич
Введение диссертации (часть автореферата) на тему «Управление доступом к общим ресурсам в пиринговых системах»
2.2. Существующие решения взаимного исключения в пиринговых сетях.44
2.2.1. Описание алгоритмов.44
2.2.2. Анализ нагрузки сети и производительности существующих решений.45
2.2.3. SWOT-анализ существующих алгоритмов.47
2.3.Предлагаемые алгоритмы.51
2.3.1. Алгоритм взаимного исключения «Узел-Координатор»(У2К) 51
2.3.1.1. Основы алгоритма.51
2.3.1.2. Описание алгоритма У2К.53
2.3.1.3. Обработка отказов в сети с помощью алгоритма У2К.56
2.3.1.4. Свойства алгоритма У2К.57
2.3.1.5. Анализ производительности алгоритма У2К.59
2.3.1.6. Корректность алгоритма У2К.61
2.3.2. Древовидной алгоритм взаимного исключения (ДАВИ).64
2.3.2.1. Вводные замечания.64
2.3.2.2. Основа алгоритма.65
2.3.2.3. Архитектура и блок-схема алгоритма ДАВИ.68
2.3.2.4. Обработка отказов в сети с помощью ДАВИ.73
2.3.2.5. Свойства алгоритма.75
2.3.2.6. Корректность ДАВИ.77
2.3.2.7. Анализ производительности ДАВИ.81
2.4. Основные результаты и выводы по главе.83
ГЛАВА 3. ТИРАЖИРОВАНИЕ И ОБЕСПЕЧЕНИЕ АУТЕНТИЧНОСТИ
ДУБЛИКАТОВ ОБЪЕКТА В ПИРИНГОВЫХ СЕТЯХ .84
3.1. Вводные замечания.84
3.2. Существующие методы тиражирования для структурированных пиринговых сетей.85
3.2.1. Различные хэш-функции.85
3.2.2. Наборы преемников и лист-наборы узлов.85
3.3. Предлагаемые алгоритмы тиражирования.91
3.3.1. Алгоритм тиражирования с использованием опубликования информации о местоположении всех дубликатов у координатора
ТОДК).91
3.3.1.1 .Опубликование дубликатов в алгоритме ТОДК.92
3.3.1.2. Операции алгоритма ТОДК.92
3.3.1.3.Преимущества алгоритма ТОДК.97
3.3.2. Алгоритм тиражирования с использованием сцепленной хэш-функции (ТСХФ).98
3.3.2.1.Основы алгоритма.98
3.3.2.2,Операции алгоритма ТСХФ.100
3.3.2.3.Преимущества алгоритма ТСХФ.104
3.3.2.4.0бработка отказов.105
3.4. Анализ сложности алгоритмов.106
3.5. Заключение и выводы по третьей главе.109
ГЛАВА 4. ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ДЛЯ ИССЛЕДОВАНИЯ
МОДЕЛЕЙ ПИРИНГОВЫХ СЕТЕЙ.111
4.1. Обоснование выбора программных средств.111
4.2. Описание Pastry.Ill
4.2.1. Схема маршрутизации Pastry.113
4.2.2. Вход и выход узла.113
4.2.3. Программный прикладной интерфейс Pastry.115
4.3. Программное обеспечение для исследования моделей пиринговых сетей.116
4.4. Средства имитации.'.117
4.4.1. Подсистема редактирования модели.119
4.4.2. Подсистема прогона модели.119
4.4.3. Подсистема обработки результатов.121
4.4.4. Реализация программного пакета для реальной работы в Р2Р сетях.122
4.5. Апробация разработанного программного пакета.123
4.7. Основные результаты и выводы по главе.123
ГЛАВА 5. РЕЗУЛЬТАТЫ ИССЛЕДОВАНИЙ.125
5.1. Описание подхода к моделированию.125
5.2. Результаты имитационного моделирования алгоритмов.126
5.2.1. Проверка масштабируемости и загрузки сети служебным трафиком.126
5.2.2. Сравнение показателей вида: среднее время ответа, задержка синхронизации и пропускная способность.128
5.2.3. Влияние на нагрузку сети коэффициента текучести.131
5.2.4. Влияние на нагрузку сети количества дубликатов.131
5.2.5. Влияние на нагрузку сети типа алгоритмов тиражирования .132
5.3. Основные результаты и выводы по главе.133
ГЛАВА 6. ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ДЛЯ РАБОТЫ В Р2Р
СЕТЯХ.135
6.1. Программный прикладной интерфейс Pastry.135
6.2. Описание программное обеспечения.136
6.3. Средства программы.143
6.4. Интерфейс программного пакета.145
6.5. Апробация разработанного программного пакета.147
6.6. Основные результаты и выводы по главе.148
ЗАКЛЮЧЕНИЕ.149
СПИСОК ЛИТЕРАТУРЫ.151
ПРИЛОЖЕНИЕ 1. Копии документов об использовании результатов работы.163
ПРИЛОЖЕНИЕ 2. Копии дипломов участника конференции.168
ВВЕДЕНИЕ
Актуальность темы. Пиринговые сети (от англ. peer-to-peer (Р2Р) — ровня с ровней, равный с равным (Р2Р) или пользователь — пользователь (П2П)) — это среда, основанная на равноправии всех участников, в которых нет специально выделенных серверов данных или приложений, а каждый его участник - узел (peer) является как клиентом (получателем информации), так и сервером (поставщиком информации). Иными словами Р2Р-сети являются распределенной дуальной системой (средой), содержащей взаимосвязанные узлы, способные к самоорганизации в сетевую технологию с целью разделения различных ресурсов (контентов, циклов процессоров, устройств хранения, полос пропускания и т.п.), самоадаптирующихся к отказам и переменному числу узлов, поддерживая при этом приемлемый уровень связности и производительности без необходимости в посредниках или поддержки глобального центрального сервера. Они изначально ориентированны на нестабильность, переменное количество узлов в сети, устойчивость к отказам и самоадаптацию. Их дуальность (двойственность) связана с тем, что, с одной стороны, это совокупность распределенных взаимосвязанных узлов, абсолютно равноправных с точки зрения функциональности и выполняемых задач, необязательно однородных, с другой, совокупность приложений, которые используют одни и те же ресурсы (диски, циклы процессоров, контент и т.п.).
В настоящее время резко возрос интерес к пиринговым сетям (Р2Р), в которых, посредством Интернета в качестве средств (среды) обмена неизменяемых объектов, используются такие системы как Kazaa, Gnutella и BitTorrent. Недавние исследования показывают, что в течение последних лет 70% трафика Интернета связаны с деятельностью пиринговых сетей. Это объясняется тем, что использование пиринговых сетей для управления ресурсом даёт преимущества в виде уменьшения стоимости, хорошей масштабируемости и поддержки специальных сетей. Наряду с таким развитием появилась потребность в приложениях, позволяющих сотрудничать друг с другом большему количеству пользователей. До сих пор большинство решений связано с моделью «клиент-сервер», в которой сервер контролирует обновление общих данных приложения. Эта модель позволяет легко поддерживать одновременно доступ к ресурсам и аутентичность (тождественность) данных приложений, однако сервер становится единой точкой отказа системы и «узким местом», которое может препятствовать тому, чтобы приложение было доступно большому количеству пользователей. Для того, чтобы в полной мере использовать потенциал широкополосных сетей, необходимо хорошее распределение данных, являющееся ключом к обеспечению свойства масштабируемости системы. Последние исследования в области пиринговых систем были направлены на поиск решений, обеспечивающих хорошее распределение работы, выполняемой приложением, с учетом, во-первых, динамически подключающихся и отключающихся от системы узлов, во-вторых, допустимости большой динамики изменений общих ресурсов. Несмотря на то, что пиринговые системы обычно ассоциируются с размещением распределенных данных, они также могут быть использованы для объединения или крупномасштабного распространения информации.
Однако для того, чтобы реализовать такие режимы работы систем, необходимы алгоритмы управления доступом к общим ресурсам. В частности для обеспечения эффективности, повышения доступности и отказоустойчивости пиринговых сетей необходимо аутентичное (тождественное) тиражирование одинаковых ресурсов. Существующие же алгоритмы не удовлетворяют в должной мере требованиям масштабируемости, аутентичности, изменчивости, так как не обладают механизмами защиты от одновременного доступа к общим ресурсам в случае выполнения взаимоисключающих операций (например, чтение одним пользователем и изменение содержимого другим пользователем) с общими объектами.
В диссертации разработаны алгоритмы доступа, пригодные для таких приложений общего назначения, названных «совместным окружением», как партнерское текстовое редактирование, видео конференц-связь, игры с многопользовательской версией, он-лайн аукцион, образовательные приложения и т.д., то есть таких приложений, в которых различным пользователям необходимо иметь общий доступ к информации и изменять ее в режиме реального времени в распределенном виде.
Разработанные алгоритмы, реализованные в распределенном окружении при наличии динамизма, гарантируют, во-первых, доступ к совместно используемому и изменяемому объекту в любое заданное время только одному пользователю, во-вторых, аутентичность дубликатов объекта в условиях присоединения узлов к сети и отсоединения их от нее.
Сложность разработки таких алгоритмов связана с тем, что для поддержания взаимодействия динамично изменяемой по структуре пиринговой сети в режиме реального времени необходимо обеспечить требования ее эффективности и масштабируемости, в частности обеспечение масштабируемых коммуникаций управления процессами и изменением информации среди взаимодействующих узлов наиболее эффективным и непротиворечивым (согласованным) способом. Система должна допускать подключения или выходы из нее любого количества узлов в любые моменты времени. Это требует разработки таких алгоритмов взаимного исключения для децентрализованной пиринговой сети, которые исключат возможность одновременного доступа пользователей (узлов) с противоречивыми намерениями (запись, чтение; изменение или сохранение содержимого и т.п.) и позволят изменять масштаб сети, т.е. количество узлов и процессов в ней. Это также требует разработки и исследования алгоритмов тиражирования дубликатов объектов и обеспечения их аутентичности.
Основные вопросы проблемы взаимного исключения одновременного доступа к общим ресурсам в вычислительных системах и сетях рассматриваются в работах L. Lamport. , R. Agrawala, G. Ricart, A. Agrawala, M. Singhal, K. Raymond, M. Maekawa и др. В результате для децентрализованных вычислительных сетей предложено множество решений этой проблемы. Однако специфика пиринговых сетей не всегда позволяет эффективно использовать известные решения из-за различий в базовых моделях сетей, строения и функционирования пиринговых и других сетей. Например, ряд алгоритмов не может быть применен из-за отсутствия в пиринговых сетях централизованного сервера для отслеживания местоположения членов сети и наличия таких требований к пиринговым сетям, как отсутствие централизованного сервера индексного поиска информации для хранения списка членов и обеспечения координации между ними. Другим отличием является то, что классические децентрализованные алгоритмы используют несколько передач «от каждого к каждому» (all-to-all), что не является масштабируемым и эффективным. В результате не все известные решения могут быть эффективно и отказоустойчиво использованы в пиринговых сетях. Специальные же существующие решения для Р2Р систем обладают рядом недостатков (например, наличие единой точки отказа сети, отсутствие упорядоченности, высокая загрузка сети служебным трафиком, отсутствие обеспечения аутентичности дубликатов ресурса).
Поэтому, несмотря на большое количество существующих решений взаимного исключения, текущего тиражирования и обеспечения при этом аутентичности копий, в традиционных средствах параллельных вычислений, описанных в литературе, децентрализованность, переменная масштабируемость пиринговых сетей, непредсказуемая изменчивость сетей и объектов в них, вынуждают искать новые решения.
В связи с этим тема работы является актуальной и практически важной.
Цель диссертационной работы. Целью данной диссертации является разработка и исследование модельного, алгоритмического и программного обеспечения эффективного бесконфликтного доступа в динамических пиринговых сетях к общим непредсказуемо изменяемым объектам, т.е. доступа с гарантированным исключением одновременного выполнения противоречивых запросов на работу с одним и тем же изменяемым объектом с обеспечением множественности и аутентичности его дубликатов.
В соответствии с поставленной целью решаются следующие задачи исследования:
1. Выбрать класс семейства пиринговых сетей, как базовую основу для разработки и исследования алгоритмов, рассматриваемых в диссертации, и создать для него системную модель.
2. Выполнить анализ архитектурных особенностей выбранного семейства пиринговых сетей, провести систематизацию и исследование существующих методов и алгоритмов предоставления распределенного доступа к объектам в них.
3. Разработать бесконфликтные масштабируемые отказоустойчивые алгоритмы, обеспечивающие эффективный доступ к совместно используемым изменяемым объектам в динамических пиринговых сетях выбранного класса, быструю тиражируемость и аутентичность дубликатов непредсказуемо изменяемых объектов.
4. Создать средства для оценки показателей качества предложенных алгоритмов и провести сравнительное исследование алгоритмов.
5. Опробовать разработанные алгоритмы доступа к дубликатам объектов.
Методы исследования. Для решения задач, поставленных в диссертации, используются методы анализа эффективности функционирования распределенных вычислительных систем, элементы SWOT-анализа, математической статистики, имитационного моделирования.
Научная новизна полученных в диссертационной работе результатов состоит в следующем:
1. Создана формализованная системная модель класса рассматриваемых сетей.
2. Систематизированы и проанализированы существующие алгоритмы взаимного исключения одновременного доступа к общим объектам и обеспечения аутентичности дубликатов объектов в динамических пиринговых сетях.
3. Разработаны новые бесконфликтные алгоритмы доступа к общим ресурсам, обеспечивающие взаимное исключение одновременного доступа к запрашиваемому объекту: алгоритм «узел-координатор» (У2К) и древовидный алгоритм взаимного исключения (ДАВИ).
4. Разработаны два алгоритма тиражирования с обеспечением аутентичности (тождественности) и множественности дубликатов динамически изменяемых объектов.
5. Разработано программное обеспечение для имитационного исследования предложенных алгоритмов по основным показателям качества, проведено апробирование и исследование алгоритмов.
Практическая ценность работы заключается в том, что:
1. Использование предложенных алгоритмов и методов позволяет разработчикам при написании Р2Р-приложений не беспокоиться о поддержании низкоуровневых механизмов защиты от одновременного доступа к совместно используемым объектам и об обеспечении аутентичности их дубликатов.
2. На основе созданных алгоритмов возможна разработка большого количества приложений, называемых «совместным окружением», которые позволяют различным пользователям иметь общий доступ к информации и изменять её в режиме реального времени в распределенном виде, в частности перенос приложений, применяющихся на модели «клиентсервер», в Р2Р системы. Примерами является партнерское текстовое редактирование, видео конференц-связь, он-лайн игры, он-лайн аукционы, образовательные приложения и т.д.
3. Предложенные алгоритмы взаимного исключения имеют меньшую сложность. Результаты имитации алгоритмов выявили, что они обладают намного большей масштабируемостью, требуют в среднем в 3-4 раза меньшего количества служебных сообщений.
4. Созданное на основе системы FreePastry приложение позволяет обеспечить функционирование и тестирование предложенных алгоритмов.
Реализация работы. Созданный программный пакет, реализующий алгоритмы управления доступом к объектам в пиринговых сетях, был использован в компаниях, занимающихся разработкой и внедрением программных систем, - ООО «Инфо-Стрим» и ООО «ИДЕЛЬ», для решения исследования моделей проектируемых приложений. Результаты работы также использованы в учебном процессе Новосибирского государственного технического университета (НГТУ), что подтверждается соответствующими документами, копии которых приведены в приложении к диссертации.
Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на:
1. II Всероссийском смотре научных и творческих работ иностранных студентов и аспирантов, 28- 29 апреля, 2008 г., Томск, Россия;
2. Международной конференции «The Third International Forum on Strategic Technologies (IFOST)», 23-29 июня, 2008 г., Новосибирск, Россия;
3. Международной конференции «The 10th International Workshop on Computer Science and Information Technologies (CSIT)», 15-17 сентября, 2008г., Antalya, Turkey;
4. Российской научной конференции «Наука, Технологии, Инновации», 4-7 декабря,2008г., Новосибирск, Россия;
5. XV международной научно-технической конференции студентов и аспирантов «РАДИОЭЛЕКТРОНИКА, ЭЛЕКТРОТЕХНИКА И ЭНЕРГЕТИКА»// 26 - 27 февраля, 2009 г., Москва, Россия;
6. Всероссийской конференции «Винеровские чтения 2009», 11-16 марта, 2009 г., Иркутск, Россия;
7. Международной конференции «International Siberian Conference on Control and Communications (SIBCON-2009)», 27-28 марта, 2009 г., Томск, Россия.
8. Седьмой всероссийской научно-практической конференции студентов, аспирантов и молодых ученых с международным участием «Молодежь и современные информационные технологии», 24-27 февраля, 2009г., ТПУ, г. Томск, Россия;
9. II Всероссийской научно-практической конференции «Научная инициатива иностранных студентов и аспирантов российских вузов», 21-22 мая, 2009 г., ТПУ, г. Томск, Россия.
10.The Forth International Forum on Strategic Technologies (IFOST), 21-23 октября , 2009 г., Ho Chi Minh city, Vietnam.
Публикации. Содержание диссертации отражено в 15 печатных работах, из которых 2 статьи опубликованы в изданиях, рекомендованных ВАК РФ.
На защиту выносятся следующие результаты:
1. Результаты исследования существующих решений.
2. Эффективные алгоритмы бесконфликтного доступа к запрашиваемому объекту в децентрализованных пиринговых системах: алгоритм «узел-координатор» (У2К) и древовидный алгоритм взаимного исключения (ДАВИ).
3. Алгоритмы тиражирования динамично получаемых дубликатов непредсказуемо изменяемых объектов с обеспечением их аутентичности
4. Программное обеспечение для проведения имитационного исследования предложенных алгоритмов по выбранным показателям качества и результаты их исследования.
Структура и содержание работы
Диссертация состоит из введения, шести глав, заключения, списка литературы, включающего 105 наименований, из которых 88 иностранных, и двух приложений. Текст диссертации изложен на 171 странице, включает 36 рисунков и 8 таблиц. В приложении содержатся копии документов об использовании результатов работы и дипломов за участие в научно-технических конференциях.
Похожие диссертационные работы по специальности «Телекоммуникационные системы и компьютерные сети», 05.13.13 шифр ВАК
Алгоритмы репликации данных в распределенных системах обработки информации2005 год, кандидат технических наук Белоусов, Всеволод Евгеньевич
Модели, методы и программное обеспечение для построения объединенного интернет/интранет сервера организации, обеспечивающего безопасность информационных ресурсов2005 год, кандидат физико-математических наук Ермаков, Дмитрий Германович
Исследование и разработка архитектуры, алгоритмического и программного обеспечения средств гарантированной доставки информации для автоматизированной информационной системы почтовой связи России2002 год, кандидат технических наук Шинкарюк, Александр Георгиевич
Математическое и программное обеспечение параллельного и распределенного управления многоузловым мониторингом объектов многоканальной системы2021 год, кандидат наук Николаев Дмитрий Александрович
Разработка и исследование стохастических методов и средств защиты программных систем ответственного назначения2005 год, доктор технических наук Иванов, Михаил Александрович
Заключение диссертации по теме «Телекоммуникационные системы и компьютерные сети», Обейдат Атеф Ахмед
5.3. Основные результаты и выводы по главе
Методами имитационного моделирования проведены исследования предложенных алгоритмов и сравнения их с существующими. Проведены следующие исследования.
ДАВИ У2К Е2Е NONE2E SIGMA
Алгоритмы
1. Проверка масштабируемости и загрузки сети служебным трафиком.
2. Сравнение показателей вида: среднее время ответа, задержки синхронизации и пропускная способность.
3. Влияние показателя текучести.
4. Влияние количества дубликатов на нагрузку сети.
5. Влияние типа алгоритмов тиражирования на нагрузку сети. Показано, что предложенные алгоритмы по всем показателям превосходят известные алгоритмы.
ГЛАВА 6. ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ДЛЯ РАБОТЫ В Р2Р СЕТЯХ
В данной главе описывается созданный программный пакет для реальной работы в Р2Р сетях согласно требованиям, сформулированным в первой главе, и по предложенным алгоритмам во второй и третей главах а|е ф ф $
4 ,7 ,13 ,105 ]. Программный пакет называется РМАМО-Р2Р (Program of Management the Access to Mutable Objects in Peer-to-Peer Networks — Программное обеспечение для управления доступом к изменяемым объектам в пиринговых сетях). Программный пакет РМАМО-Р2Р гарантирует одновременное выполнение противоречивых запросов на работу с одним и тем же объектом и обеспечение аутентичности и множественности его дубликатов. Под объектом мы будем понимать реальный файл или базу данных. В нем были реализованы алгоритмы, показавшие лучшие результаты после практических исследований, описанных в главе 5. 6.1. Программный прикладной интерфейс Pastry
В качестве рабочей версии для реализации пакета РМАМО-Р2Р выбрана полностью децентрализованная пиринговая модель Pastry и её реализация FreePastry. Обоснование выбора реализации аналогично изложенному в главе 4.
Далее кратко описывается программный прикладной интерфейс (API -Application Programming Interface) Pastry. Для ясности представленный API немного упрощен. Кроме того API был применен для написания приложений без привязки к определенному протоколу, что обеспечивает переносимость приложений из Pastry в Chord, CAN, Tapestry и др.
Pastry реализует следующие операции:
• Id = pastryln\t(Credentials, Application) приводит к присоединению нового узла к существующей сети Pastry (или создает новую), инициализации всех значимых состояний и возврату идентификатора Id нового узла.
Специализированные параметры Credentials содержат информацию для аутентификации нового узла. Аргумент Application является идентификатором объекта приложения, который обеспечивает вызов процедур на узле Pastry при возникновении определенных событий, например, при получении сообщения.
• route(M, key) приводит к отправке сообщения М узлу с идентификатором Id, численно наиболее близким к идентификатору (ключу) key среди всех активных узлов Pastry.
ЗАКЛЮЧЕНИЕ
Таким образом в диссертационной работе, согласно поставленной цели, было разработано модельное, алгоритмическое и программное обеспечение, пригодное для организации эффективного множественного бесконфликтного доступа к общим изменяемым объектам в динамических децентрализованных пиринговых сетях, имеющее важное значение в различных областях знаний и народного хозяйства, где применяются подобные сети. А именно, в работе:
1. Выполнен обзор децентрализованных файловых пиринговых сетей и дана их классификация. Выявлены требующие решения задачи, характерные для пиринговых сетей. Это задачи взаимного исключения, тиражирования и обеспечения аутентичности дубликатов объектов. Формализована системная модель класса рассматриваемых сетей.
2. Проведена систематизация и дан анализ существующих решений взаимного исключения в пиринговых сетях, рассмотрены их сильные и слабые стороны. Предложены и исследованы алгоритмы взаимного исключения «узел-координатор» (У2К) и древовидный алгоритм взаимного исключения (ДАВИ), детально описаны их основы и свойства. Рассмотрена возможность обнаружения отказов в сети и устранения их последствий с помощью предложенных алгоритмах. Проведено аналитическое исследование свойств алгоритмов и показано, что разработанные алгоритмы являются более эффективными по сравнению с существующими.
3. Проведена систематизация и дан анализ существующих методов тиражирования объектов, показаны их недостатки. Разработаны алгоритмы тиражирования ТОДК и ТСХФ, детально описаны их основы, рассмотрены преимущества, показано, что они эффективнее существующих методов и свободны от их недостатков. Решена задача обеспечения аутентичности динамично получаемых дубликатов непредсказуемо изменяемых объектов в этих алгоритмах.
4. Разработан, реализован, апробирован и внедрен программный пакет для исследования предложенных алгоритмов. С его помощью проведено имитационное исследование предложенных алгоритмов, сравнение их с существующими. Показано, что предложенные алгоритмы по всем показателям превосходят известные алгоритмы.
5. Проведена апробация разработанного программного пакета на задачах исследования проектируемых вычислительных сетей.
Результаты диссертационной работы могут быть полезны для разработчиков сетевых решений, администраторов сетей различного назначения. Они могут быть применены в Интернете для таких приложений общего назначения, как партнерское текстовое редактирование, видео конференц-связь, игры с многопользовательской версией, он-лайн аукцион, образовательные приложения и т.д., то есть таких приложений, в которых различным пользователям необходимо иметь общий доступ к информации и изменять ее в режиме реального времени в распределенном виде.
151
Список литературы диссертационного исследования кандидат технических наук Обейдат Атеф Ахмед, 2009 год
1. Введение в пиринговые сети: Bittoreent — (MetalMind I I http: // www. Metalmind.ru / wedenie v piringovyie seti bittorrent.html).
2. Velazquez М. G. A Survey of Distributed Mutual Exclusion Algorithms/ M. G. Velazquez //Colorado State University, Technical Report CS.93-116.-1993.
3. Открытые системы 2004 .- № 12.
4. Сухорослов O.B. Пиринговые системы: концепции, архитектура и направления исследований / О.В. Сухорослов // Проблемы вычисленийв распределенной среде: прикладные задачи. Труды ИСА РАН .- М.: РОХОС.-2004.-С. 7-43.
5. Таненбаум Э. Распределенные системы. Принципы и парадигмы / Э. Таненбаум, М. Ван Стен// СПб.: Питер .- 2003 .- 877 с.
6. Agrawal D. Exploiting logical structures in replicated databases/ D.Agrawal, A. EL ABBADI // Information Processing Letters, Vol. 33, №. 5 .- January 1990 .-P. 255-260.
7. Ahamad M. Replicated data management in distributed systems/M. Ahamad, M. Ammar, S. Cheung // IEEE Computer Society .- Los Alamitos, CA .— January 1994 .-P.572-591.
8. Androutsellis-Theotokis S. A survey of peer-to-peer content distribution technologies / S. Androutsellis-Theotokis, D. Spinellis// A CM Computing Surveys, 36(4), December 2004 P.335-371.
9. Bamboo, http: // bamboo-dht.org 2006.
10. Bernstein P. A. A proof technique for concurrency control and recovery algorithms for replicated databases / P. A. Bernstein, N. Goodman// Distributed Computing, 2(1) January 1987 .-P.32-44.
11. Carvalho O. On mutual exclusion in computer networks / O. Carvalho, G. Roucairol // Technical Correspondence," Communications of the ACM", Vol. 26. -№. 2 .-Feb. 1983 .-P. 146-147.
12. Castro M. Scribe: A large-scale and decentralized application level multicast infrastructure / M. Castro, P. Druschel, A. Kermarrec // IEEE J. Sel. Areas Commun .-Vol.20. -№. 8 Oct. 2002 .-P. 1489- 1499.
13. Cheung S. Y. The Grid protocol: A high performance scheme for maintaining replicated data / S. Y. Cheung , M. H. Ammar, and M. Ahamad // IEEE
14. Transactions on Knowledge and Data Engineering, 4(6) December 1992 .— P.582-592
15. Clarke I. Freenet. A distributed anonymous information storage and retrieval system / I. Clarke, O. Sandberg, B. Wiley, T. Hong // In Proc. of the ICSI Workshop on Design Issues in Anonymity and Unobservability.- Berkeley, CA.- July 2000 P. 311-320.
16. Crespo A. Routing indices for peer-to-peer systems / A. Crespo, H. Garcia-Molina // In Proc. of the IEEE Int. Conf. on Distributed Computing Systems (ICDCS) .- Vienna, Austria .- July 2002 .- P. 23-33.
17. Dijkstra E.W. Solution of a Problem in Concurrent Programming Control, Communications/ E.W. Dijkstra // ACM 8.-9 Sept. 1965 .- P.569.
18. Dingledine R.The FreeHaven project: distributed anonymous storage service/ R. Dingledine, M. Freedman, D. Molnar // In Proc. of the Workshop on Design Issues in Anonymity and Unobservability .- Berkeley, California — July 2000 .-P. 67-95.
19. Direct connect.- 2007 .- (http://www.dconnect.net).
20. FIPS 180-1. Secure hash standard // Tech. Rep. Publication 180-1, Federal Information Processing Standard (FIPS), National Institute of Standards and Technology, US Department of Commerce, Washington D.C .- April 1995.
21. Foster I. The Grid: Blueprint for a new computing infrastructure / I. Foster, C. Kesselman // Morgan Kaufman .- 1998 677 p.
22. Harrell F. Survey of Locating & Routing in Peer-to-Peer Systems / F. Harrell, H. Yuanfang , G. Wang, H. Xia // Department of Computer Science and Engineering .- 2001 .-(http://www.cse.ucsd.edu/classes/fa01/cse221/projects/groupl5.pdf).
23. Freepastry .- 2006 —URL: http://freepastry.rice.edu/
24. Ganesan P. Canon in G major: Designing DHTS with hierarchical structure / P. Ganesan, P. K. Gummadi, H. Garcia-Molina // 24th international conference on distributed computing systems (ICDCS 2004).-23-26 March .- 2004.- Tokyo, Japan.-P. 263-272.
25. Coulours G. Distributed systems / G. Coulours, J. Dollimore ,T. Kindberg // 4th edition, Addison-wesley .- 2005 .- 927p.
26. Gifford D. K. Weighted voting for replicated data / D. K. Gifford // In Proc. of the 7th Symposium on Operating Systems Principles .- Pacific Grove, CA .-December 1979 .-P. 150-162.
27. Файлообмен: Freenet и Gnutella .- 1997 . .— (http ://www.computerra.ru/ softerra/net/32144/).
28. Gnutella .— 2000 .— ( http://www.gnutelliums.com).
29. Helary J. A distributed algorithm for mutual exclusion in an arbitrary network/ J.Helary, N. Plouzeau , M. Raynal // Computer Journal, Vol. 31, №. 4.- 1988 .-P. 289-295.
30. Jovanovic M. Scalability issues in large peer-to-peer networks: a case study of Gnutella. Technical report/ M. Jovanovic, F. Annexstein, K. Berman // ECECS Department, University of Cincinnati, Cincinnati, Ohio, January 2001.
31. JXTA Community .- 2008 .- ( http://www.jxta.org/).
32. Kalogeraki V. A local search mechanism for peer-to-peer networks / V. Kalogeraki, D. Gunopoulos, D. Zeinalipour-Yazti // In Proc. of the ACM Int. Conf. on Information and Knowledge Management (CIKM) .- McLean, Virginia .-November 2002 .-P. 300-307.
33. Kazaa .- 2006 .- (http://www.kazaa.com/).
34. Kumar A. Hierarchical Quorum Consensus: A New Algorithm for Managing Replicated Data / A. Kumar // IEEE Transactions on Computers.- vol.40. n.9- 1991.-P. 996-1004.
35. Lamport L. Time, clocks and the ordering of events in a distributed system / L. Lamport // Communications of the ACM .- Vol. 21 .- 1978 .- P. 558-565.
36. LvQ. Search and replication in unstructured peer-to-peer networks/ LvQ. , CaoP., CohenE. , K. Li , S. Shenker // In Proc. of the ACM Int. Conf. on Supercom-puting (ICS) .- ACM New York, NY, USA.- June 2002 .- P.84-95.
37. Maekawa M. Operating Systems, Advanced Concepts/ M. Maekawa, A.E. Oldehoeft, R.R. Oldehoeft//Benjamin-Cummings .— 1987.
38. Maymounkov P. Kademlia: A peer-to-peer information system based on the xor metric / P. Maymounkov and D. Mazi'eres // Proceedings of the IPTPS, Cambridge, MA, USA .- February 2002 .- P.53-65.
39. Mishra. S. Fault-tolerant mutual exclusion algorithms / S. Mishra., P. Srimani // Journal of Systems Software, Vol. 11. №. 2 .- Feb. 1990 .- P. 111-129.
40. Mizuno M. A Token based distributed mutual exclusion algorithm based on Quorum Agreements / M. Mizuno, M.L. Neilsen, R. Rao // 11th Intl. Conference on Distributed Computing Systems .- 20-24 may 1991 -P.361
41. Moosa Muhammad. Efficient Mutual Exclusion in Peer-To-Peer Systems/ Moosa Muhammad // University of Illinois at Urbana-Champaign .- 2005 .— P. 296-299.
42. Morpheus home page .— 1999 .- (www.moipheussoftware.net).
43. Mosberger D. Memory consistency models / D. Mosberger // Tech. rep., University of Arizona .— Nov., 1993.
44. Muhammad M. Efficient mutual exclusion in peer-to-peer systems. / M. Muhammad, A. S. Cheema // 6th IEEE ACM International Conference on Grid Computing 2005 .- P. 296-299.
45. Naimi M. How to detect a failure and regenerate the token in the log(n) distributed algorithm for mutual exclusion / M. Naimi, M. Trehel // Proc. of the Second Int. Workshop on Distributed Algorithms, Lecture Notes in CS .1987 .-P. 155-166.
46. Napster home page .- 2003 .- (http://www.napster.com).
47. Neilsen M.L. A DAG-based algorithm for distributed mutual exclusion / M. L. Neilsen, M. Mizuno// 11th Intl. Conference on Distributed Computing Systems .- 20 24, May ,1991 .- P. 354 - 360 (http://www.scipub.org/fiilltext/jcs/jcs55398-404.pdf).
48. Nejdl W. Design issues and challenges for RDF- and schema-based peer-to- peer systems / W. Nejdl, W. Siberski, M. Sintek // ACM SIGMOD Record, 32(3) September 2003 .-P.41-46.
49. Nejdl W. Edutella: a P2P networking infrastructure based on RDF/ W. Nejdl, B.Wolf, C. Qu , S. Decker, M. Sintek, A. Naeve , M. Nilsson , M. Palmer ,T. Risch // In Proc. of the Int. World Wide Web Conference (WWW) Honolulu,
50. Hawaii .-May 2002 .-P. 604-615.
51. Overnet Web site : eDonkey2000 Overnet .- 2000 .-(http://www.overnet.com/).
52. Malkhi D. Viceroy: a scalable and dynamic emulation of the butterfly / D. Malkhi, M. Naor , D. Ratajczak // Proc. 21st Ann. ACM Symp. Principlesof Distributed Computing (PODC) .- July 2002 P. 183-192.
53. Michael N. H. SkipNet: A Scalable Overlay Network with Practical Locality Properties / N. H. Michael, M. B. Jones, S. Saroiu, M. Theimer, A. Wolman // .— 2003 .- (http://research.microsoft.eom/users/alecw//usits-2).
54. Raymond K. A distributed algorithm for multiple entries to a critical section / K. Raymond // Information Processing Letters, №. 30, Feb. 1989, pp. 189193.
55. Raymond K. A tree-based algorithm for distributed Mutual Exclusion / K. Raymond // ACM Transactions on Computer Systems, Vol. 7, №. 1 .— Feb. 1989 .-P. 61-77.
56. Raynal M. A simple taxonomy for distributed mutual exclusion algorithms / M. Raynal // Operating Systems Review, Vol. 25, №. 2, Apr. 1991, P. 47-49.
57. Raynal M. Prime numbers as a tool to design distributed algorithms// M. Raynal / Information Processing Letters, Vol. 33. №. 1 .- Oct. 1989 P. 53-58.
58. Ricart G. An optimal algorithm for mutual exclusion in computer networks / G. Ricart, A. Agrawala // Communications of the ACM, Vol. 24, №. 1, Jan. 1981 .-P. 9-17.
59. Ricart G. Author response to 'on mutual exclusion in computer networks' by Carvalho and Roucairol / G. Ricart, A. K. Agrawala // Communications of the ACM, Vol. 26, №. 2 .-Feb. 1983 .-P.147 148.
60. Saito Y. Optimistic replication/ Y. Saito, M. Shapiro// ACM Computing Surveys, 37 (1) .- March 2005 .- P.42-81 (http://citeseer.ist.psu.edu/saito03optimistic.html).
61. Sanders B. The information structure of distributed mutual exclusion algorithms / B. Sanders // ACM Transactions on Computer Systems, Vol. 5, №. 3 .-Aug. 1987,.— P.284-299.
62. Shiding L. A practical distributed mutual exclusion protocol in dynamic peer-to-peer systems / L. Shiding , Qiao Lian, Ming Chen, Zheng Zhang // 3rd International Workshop on Peer-to-Peer Systems (IPTPS'04) .- San Diego, CA, USA .- Feb.2004 P. 1-10.
63. Silberschatz A. and Peterson, J.L. Operating System Concepts / A. Silberschatz, J.L. Peterson//Addison-Wesley .- Alternate edition .- 1988.
64. Singhal M. A dynamic information-structure mutual exclusion algorithm for distributed systems / M. Singhal // IEEE Transactions on Parallel and Distributed Systems, Vol. 3, №. 1 .-Jan. 1992 -P. 121-125.
65. Singhal M. A heuristically-aided algorithm for mutual exclusion in distributed systems / M. Singhal //IEEE Transactions on Computers, Vol. 38, №. 5 .-may 1989 .-P.651-662.
66. Srimani P. Another distributed algorithm for multiple entries to a critical section / P. Srimani, R. Reddy // Information Processing Letters .- Vol. 41, №. 1 .-Jan. 1992 .-P.51-57.
67. Stockinger Heinz. Defining the Grid: A Snapshot on the Current View / http: // www.gridclub .- 26.06 2006.
68. Stoica I. Chord: A scalable Peer- To-Peer lookup service for internet applications /1. Stoica, R. Morris, D. Karger, F. Kaashoek, H. Balakrishnan //
69. Proceedings of the ACM SIGCOMM 2001 Conference. ACM Press-New York. 2001 .- P. 149-160.
70. Suzuki I. and Kasami T. A distributed mutual exclusion algorithm /1. Suzuki, T. Kasami // ACM Transactions on Computer Systems, Vol. 3. — №. 4 — Nov. 1985 .-P. 344-349.
71. The Gnutella protocol specification .— (http://dss.clip2.com/GnutellaProtocol04.pdf. 2000).
72. Thomas R. H. A majority consensus approach to concurrency control for multiple copy databases / R. H. Thomas // ACM Transactions on Database Systems, Vol. 4. №. 2 .- June 1979 .- P. 180-209.
73. Vidal M. Survey of data replication in P2P systems / M. Vidal, E. Pacitti, P. Valduriez 2006 .- (http://hal.inria.fr/inria-00122282/en).
74. Waldman M. Publius: a robust, tamper-evident, censorship-resistant, web publishing system / M. Waldman, R. AD, C. LF // In Proc. of the USENIX Security Symposium -Denver, Colorado August2000 -P. 59-72.
75. Mitchell B.WinMX .- 1999 (http://compnetworking.about.eom/b/2005/09/27/winmx-p2p-network-meetS" its-demise-almost.htm).
76. Yang B. Improving search in peer-to-peer networks / B. Yang, H. Garcia-Molina // In Proc. of the IEEE Int. Conf. on Distributed Computing Systems (ICDCS) Vienna, Austria.- July 2002 .- P. 5-14.
77. Zhao B. A Global-scale Overlay for Rapid Service Deployment/ B. Y. Zhao, L. Huang, S. C. Rhea, J. Stribling, A. D. Joseph, and J. D. Kubiatowicz// IEEE Journal on Selected Areas in communications (JSAC) .- 22(1),January 2004 .-P. 41-53.
78. Zhao B.Y. Tapestry: An infrastructure for fault-tolerant wide-area location and routing / B.Y Zhao, J. Kubiatowicz, A. D. Joseph // Technical Report UCB/CSD-01-1141, University of California.-Berkeley, California, USA.-2001.
Обратите внимание, представленные выше научные тексты размещены для ознакомления и получены посредством распознавания оригинальных текстов диссертаций (OCR). В связи с чем, в них могут содержаться ошибки, связанные с несовершенством алгоритмов распознавания. В PDF файлах диссертаций и авторефератов, которые мы доставляем, подобных ошибок нет.