Навігація
Головна
ПОСЛУГИ
Авторизація/Реєстрація
Реклама на сайті
 
Головна arrow Інформатика arrow Моделирование сложных сетей
< Попередня   ЗМІСТ   Наступна >

Модели поиска в пиринговых сетях

Модели поиск в сетевой среде рассмотрим на примере поиска в так называемых пиринговых сетях. Пиринговые сети (Peer-to-peer, P2P -равный с равным) - это компьютерные сети, основанные на равноправии участников. В таких сетях отсутствуют выделенные серверы, а каждый узел (peer) является как клиентом, так и сервером. Впервые фраза "peer-to-peer" была использована в 1984 году Парбауэллом Йохнухуйтсманом (Parbawell Yohnuhuitsman) при разработке архитектуры Advanced Peer to Peer Networking фирмы IBM.

Гуркин Ю.Н. Семенов Ю.А. Файлообменные сети Р2Р: основные принципы, протоколы, безопасность. Сети и системы связи, 2006.- № 11. - с. 62.

P2P - это сетевой протокол, обеспечивающий возможность создания и функционирования сети равноправных узлов, их взаимодействия. Во многих случаях P2P являются наложенными сетями, использующими существующие транспортные протоколы стека TCP/IP - TCP или UDP. Следует отметить, что на практике пиринговые сети состоят из узлов, каждый из которых взаимодействует лишь с некоторым подмножеством других узлов сети (из-за ограниченности ресурсов). Для реализации протокола P2P используются клиентские программы, обеспечивающие функциональность как отдельных узлов, так и всей пиринговой сети.

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

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

Централизованная архитектура "клиент/сервер" подразумевает, что сеть зависит от центральных узлов (серверов), обеспечивающих подключенные к сети терминалы (клиенты) необходимыми сервисами. В этой архитектуре ключевая роль отводится серверам, которые определяют сеть независимо от наличия клиентов. Несмотря на то, что все узлы в Р2Р имеют одинаковый статус, реальные возможности их могут существенно отличаться.

Очевидно, что рост количества клиентов сети типа "клиент/сервер" приводит к росту нагрузок на серверную часть, в результате чего она может оказаться перегруженной.

Децентрализованная пиринговая сеть, напротив, становится более производительной при увеличении количества узлов, подключенных к ней. Действительно, каждый узел добавляет в сеть Р2Р свои ресурсы (дисковое пространство и вычислительные возможности), в результате суммарные ресурсы сети увеличиваются.

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

Помимо названных выше преимуществ пиринговых сетей, им присущ также ряд недостатков.

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

Большая проблема - это легитимность контента, передаваемого в таких Р2Р-сетях. Неудовлетворительное решение этой проблемы привело уже к скандальному закрытию многих таких сетей (например, Napster в июле 2001 года). Есть и другие, проблемы, имеющие социальную природу. Так в системе Gnutella, например, 70% пользователей не добавляют вообще никаких файлов в сеть. Более половины ресурсов в этой сети предоставляется одним процентом пользователей, т.е. сеть эволюционирует в направлении клиент-серверной архитектуры.

Kalogeraki V., Gunopulos D., Zeinalipour-Yazti D. A Local Search Mechanism for Peer-to-Peer Networks. Proc. of CIKM'02, McLean VA, USA, 2002. Zeinalipour-Yazti D. Information Retrieval in Peer-to-Peer Systems. M.Sc Thesis, Dept. of Computer Science, University of California Riverside, June 2003. Zeinalipour-Yazti D., Kalogeraki V., Gunopulos D. Information Retrieval in Peer-to-Peer Networks. IEEE CiSEMagazine, Special Issue on Web Engineering, 2004. - pp. 1-13.

Еще одна проблема Р2Р-сетей связана с качеством и достоверностью предоставляемого контента. Серьезной проблемой является фальсификация файлов и распространение фальшивых ресурсов. Защита распределенной сети от хакерских атак, ботнетов, вирусов и "троянских коней" является очень сложной задачей. Зачастую информация с данными об участниках Р2Р-сетей хранится в открытом виде, доступном для перехвата. Еще одной проблемой является возможность фальсификации Ю узлов.

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

Рассмотрим подробно такие методы (алгоритмы) децентрализованного поиска:

  • - алгоритм поиска ресурсов по ключам;
  • - метод широкого первичного поиска (Breadth First Search);
  • - метод случайного широкого первичного поиска (Random Breadth First Search);
  • - интеллектуальный поисковый механизм (Intelligent Search Mechanism);
  • - метод "большинства результатов по прошлой эвристике" (>RES);
  • - алгоритм "случайных блужданий" (Random Walkers Algorithm).

Алгоритм поиска ресурсов по ключам

В большинстве пиринговых сетей, ориентированных на обмен файлами, используется два вида сущностей, которым приписываются соответствующие идентификаторы (ID): узлы и ресурсы, характеризующиеся ключами (Key), т.е. сеть может быть представлена двумерной матрицей размерности MN, где M — количество узлов, N — количество ресурсов. В данном случае задача поиска сводится к нахождению ID узла, на котором хранится ключ ресурса. На рис. 2.2.1 представлен процесс поиска ресурса, запускаемый с узла с ID 0.

В данном случае с узла с ID 0 запускается поиск ресурса с ключем 14. Запрос проходит определенный маршрут и достигает узла, на котором находится ключ 14. Далее узел с ID 14 пересылает узлу с ID 0, адреса всех узлов, обладающих ресурсом, соответствующим ключу 14.

Рассмотрим алгоритмы поиска в пиринговых сетях, ограничившись основными методами поиска по ключевым словам.

Модель поиска ресурса по ключу (в черных узлах содержатся документы с ключами - в белых - не содержатся)

Рис. 2.2.1 - Модель поиска ресурса по ключу (в черных узлах содержатся документы с ключами - в белых - не содержатся)

Метод широкого первичного поиска

Метод широкого первичного поиска (Breadth First Search, BFS) широко используется в реальных файлообменных сетях P2P, таких как, например, Gnutella (gnutella.com). Метод BFS (рис. 9) в сети P2P размерности N реализуется следующим образом. Узел q генерирует запрос, который адресуется ко всем соседям (ближайшим по некоторым критериям узлам). Когда узел p получает запрос, выполняется поиск в его локальном индексе. Если некоторый узел r принимает запрос (Query) и обрабатывает его, то он генерирует сообщение-отклик (QueryHit), чтобы возвратить результат. Сообщение QueryHit включает информацию о релевантных документах, которая доставляется по сети запрашивающему узлу (рис. 2.2.2).

Метод BFS

Рис. 2.2.2 - Метод BFS

Когда узел q получает QueryHits от более чем одного узла, он может загрузить файл с наиболее доступного ресурса. Сообщения QueryHit возвращаются тем же путем, что и первичный запрос. В BFS каждый запрос вызывает чрезмерную нагрузку сети, так как он передается по всем связям (в том числе и узлам с высоким временами ожидания). Поэтому узел с низкой пропускной способностью может стать узким местом. Один метод, позволяющий избежать перегрузки всей сети сообщениями заключается в приписывании каждому запросу с параметром времени жизни (Time-to-level, TTL). Параметр TTL определяет максимальное число переходов, по которым можно пересылать запрос. При типичном поиске начальное значение для TTL составляет обычно 5-7, которое уменьшается каждый раз, когда запрос пересылается. Когда TTL становится равным 0, сообщение больше не передается. BFS гарантирует высокий уровень качества совпадений за счет большого числа сообщений.

Метод случайного широкого первичного поиска

Метод случайного широкого первичного поиска (Random Breadth First Search, RBFS) был предложен как улучшение "наивного" подхода BFS. В методе RBFS (рис. 2.2.3) узел q пересылает поисковое предписание только части узлов сети, выбранной в случайном порядке. Какая именно часть узлов - это параметр метода RBFS.

Метод RBFS

Рис. 2.2.3 - Метод RBFS

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

Интеллектуальный поисковый механизм

Интеллектуальный поисковый механизм (Intelligent Search Mechanism, ISM) - новый метод поиска в сетях P2P (рис. 2.2.4). Улучшение скорости и эффективности поиска информации с помощью данного метода достигается за счет минимизации затрат на связи, то есть на число сообщений, передающихся между узлами, и минимизация количества узлов, которые опрашиваются для каждого поискового запроса. Чтобы достичь этого, для каждого запроса оцениваются лишь те узлы, которые наиболее соответствуют данному запросу.

Метод ISM

Рис. 2.2.4 - Метод ISM

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

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

При реализации модели ISM используется единый стек запросов размером O(TN), в котором сохраняется по T запросов для N узлов. Как только стек заполняется, происходит замена "последнего наименее используемого" (Least Recently Used, LRU) для сохранения последних запросов. Функция "ранг релевантности" (Relevance Rank, RR) используется узлом P, чтобы выполнять оперативную

классификацию его соседей для определения тех, которые следует опрашивать первыми по запросу q . Для вычисления ранга релевантности каждого узла P, Pl сравнивает q со всеми запросами в структуре профайла, для которого известен список ответов на предыдущие запросы, и вычисляется RR(P1, q):

В этой формуле Q - множество запросов, на которые был ответ у узла P, S(Pl, qj) — число результатов, возвращаемых узлом P по запросу qj, а метрика Sim рассчитывается по правилу косинуса, аналогично рассмотренному в векторно-пространственной модели поиска:

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

В случае, когда а большое, запросы с большим подобием доминируют в приведенной выше формуле. Рассмотрим ситуацию, когда узел Р1 соответствует запросам д1 и д2 значениями подобия для запроса д:

и а узел P2 соответствуют запросам дъ и д4 значениями

и Если выбрать a = 10, то доминирует, так как

Однако для a = 1 все запросы весят одинаково, и P2 дает более высокую релевантность. При a= 0 учитывается только количество результатов, возвращенных каждым узлом.

Метод ISM эффективно работает в сетях, где узлы содержат некоторые специализированные сведения. В частности, исследование сети Gnutella показывает, что качество поиска очень зависит от "окружения" узла, с которого задается запрос. Еще одна проблема в методе ISM состоит в том, что поисковые сообщения могут зацикливаться, поэтому не в состоянии достичь некоторых частей сети. Чтобы разрешить эту проблему в был предложен такой подход. Выбиралось маленькое случайное подмножество узлов (в эксперименте дополнительно выбирался один случайный узел) и оно добавилось к набору релевантных узлов для каждого запроса. В результате механизм ISM стал охватывать большую часть сети.

Методы "большинства результатов по прошлой эвристике"

В рамках метода "большинства результатов по прошлой эвристике" (>RES) (рис. 2.2.5) каждый узел пересылал запрос подмножеству своих узлов, образованному на основании некоторой обобщенной статистики.

Метод >RES

Рис. 2.2.5 - Метод >RES

Запрос в методе >RES является удовлетворительным, если выдается Z или больше результатов (Z - некоторая постоянная). В методе >RES узел q пересылает запросы к k узлам, выдавшим наибольшие результаты для последних m запросов. В их экспериментах k изменялось от 1 до 10 и таким путем метод >RES варьировался от BFS до подхода глубинного первичного поиска (Depth-first-search). Метод >RES подобен методу ISM, который рассматривался, но использует более простую информацию об узлах. Его главный недостаток по сравнению с ISM - отсутствие анализа параметров узлов, содержание которых связано с запросом. Поэтому метод >RES характеризуется скорее как количественный, а не качественный подход. Из опыта известно, что >RES хорош тем, что он маршрутизирует запросы в большие сегменты сети (которые возможно, также содержат более релевантные ответы). Он также захватывает соседей, которые менее перегружены, начиная с тех, которые обычно возвращают больше результатов.

Метод "случайных блужданий"

Ключевая идея алгоритма "случайных блужданий" (Random Walkers Algorithm, RWA) заключается в том, что каждый узел случайным образом пересылает сообщение с запросом, именуемое "посылкой" одному из своих узлов. Чтобы сократить время, необходимое для получения результатов, идея одной "посылки" расширена до " k -посылок", где k - число независимых посылок, последовательно запущенных с поискового узла. Ожидается, что "k -посылок" после T шагов достигнет тех же результатов, что и одна посылка за kT шагов. Этот алгоритм напоминает метод RBFS, но в RBFS каждый узел пересылает сообщение запроса части из его соседей. К тому же, в RBFS предполагается экспоненциальное увеличение пересылаемых сообщений, а в методе случайных блужданий -линейное. Оба метода - и RBFS, и RWA не используют никаких явных правил для того чтобы адресовать поисковый запрос к наиболее релевантному содержанию.

Еще одной методикой, подобной RWA, является "адаптивный вероятностный поиск" (Adaptive Probabilistic Search, APS). В APS каждый узел развертывает на своих ресурсах локальный индекс, содержащий значения условных вероятностей для каждого соседа, который может быть выбран для следующего перехода для будущего запроса. Главное отличие от RWA в данном случае - это то, что в APS узел использует обратную связь от предыдущих поисков (в виде условных вероятностей) вместо полностью случайных переходов. Поэтому метод APS часто дает лучшие результаты, чем RWA.

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

Существует много областей, где успешно применяется Р2Р-технология, например, параллельное программирование, кэширование данных, резервное копирование данных.

Благодаря таким характеристикам, как живучесть, отказоустойчивость, способность к саморазвитию, пиринговые сети находят все большее применение в системах управления производствами и организациями (например, Р2Р-технология сегодня применяется в Государственном Департаменте США). В данном случае возможный выход из строя части узлов или серверов не существенно влияют на управляемость всей системы. Система доменных имен (DNS) в сети Интернет также фактически является сетью обмена данными, построенной по принципу Р2Р.

Реализацией технологии Р2Р является также популярная в настоящее время система распределенных вычислений GRID. Еще одним примером распределенных вычислений может служить проект distributed.net, участники которого занимаются легальным взломом криптографических шифров, чтобы проверить их надежность.

 
Якщо Ви помітили помилку в тексті позначте слово та натисніть Shift + Enter
< Попередня   ЗМІСТ   Наступна >
 
Дисципліни
Агропромисловість
Банківська справа
БЖД
Бухоблік та Аудит
Географія
Документознавство
Екологія
Економіка
Етика та Естетика
Журналістика
Інвестування
Інформатика
Історія
Культурологія
Література
Логіка
Логістика
Маркетинг
Медицина
Менеджмент
Нерухомість
Педагогіка
Політологія
Політекономія
Право
Природознавство
Психологія
Релігієзнавство
Риторика
РПС
Соціологія
Статистика
Страхова справа
Техніка
Товарознавство
Туризм
Філософія
Фінанси
Інші