4824
правки
P2P: различия между версиями
Материал из WEGA
м
→Постановка задачи
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Одноранговая сеть (''Peer to peer''); перекрытие, оверлей (''Overlay''); оверлейная сеть (''Overlay network''); DHT; распределенная хэш-таблица (''Distributed hash table''); CDN; сеть доставки контента (''Content delivery network''); совместный доступ к файлам (''File sharing''); совмес...») |
Irina (обсуждение | вклад) |
||
| Строка 12: | Строка 12: | ||
Из-за своей симметричной и бессерверной природы такие сети называются P2P-сетями. В последующем обсуждении узлы, участвующие в сети, будут также называться пирами (peers). | Из-за своей симметричной и бессерверной природы такие сети называются ''P2P''-сетями. В последующем обсуждении узлы, участвующие в сети, будут также называться ''пирами'' (peers). | ||
Наиболее влиятельным механизмом в этой области является последовательное | Наиболее влиятельным механизмом в этой области является ''последовательное хэширование'', впервые примененное в работе Каргера и др. [21]. Идея приблизительно заключается в следующем. Часто хорошим способом организации каталога поиска является хэш-таблица, обеспечивающая быстрый доступ к данным со сложностью O(1). Для масштабирования и обеспечения высокой доступности сервисов поиска мы разбиваем хэш-таблицу на части и назначаем разные части разным серверам. Например, если в хэш-таблице есть записи от 1 до <math>n</math>, а в системе поиска участвуют <math>k</math> серверов, мы можем дать возможность каждому серверу выбрать виртуальный идентификатор от 1 до <math>n</math> случайным образом. Тогда сервер <math>i</math> будет отвечать за значения ключей, которые ближе к <math>i</math>, чем к идентификатору любого другого сервера. При хорошей рандомизации хэш-ключей мы можем получить более или менее сбалансированное распределение информации между нашими <math>k</math> серверами. Ожидается, что каждый сервер будет отвечать за <math>(n/k)</math> ключей. Кроме того, отключение или подключение сервера затрагивает только один или два других сервера с соседними виртуальными идентификаторами. | ||
Сеть серверов, реализующих последовательное | Сеть серверов, реализующих последовательное хэширование, называется ''распределенной хэш-таблицей'' (DHT). Многие современные сети совместного использования ресурсов и практически все академические исследовательские проекты в этой области построены на идее DHT. | ||
Задача поддержки DHT состоит из двух частей: | Задача поддержки DHT состоит из двух частей: | ||
Оверлейная маршрутизация | '''Оверлейная маршрутизация''' | ||
Пусть имеется хэш-ключ i. Начиная с любого узла r в сети, задача заключается в том, чтобы найти сервер s, диапазон ключей которого содержит i. Имя ключа i не имеет отношения к какому-либо реальному сетевому адресу, например IP-адресу узла, и поэтому мы не можем использовать базовую IP-инфраструктуру для поиска s. Оверлейная сеть маршрутизации связывает узлы и предоставляет им протокол маршрутизации, так что r может направиться к s, используя цель маршрутизации i. | Пусть имеется хэш-ключ <math>i</math>. Начиная с любого узла <math>r</math> в сети, задача заключается в том, чтобы найти сервер <math>s</math>, диапазон ключей которого содержит <math>i</math>. Имя ключа <math>i</math> не имеет отношения к какому-либо реальному сетевому адресу, например IP-адресу узла, и поэтому мы не можем использовать базовую IP-инфраструктуру для поиска <math>s</math>. Оверлейная сеть маршрутизации связывает узлы и предоставляет им протокол маршрутизации, так что <math>r</math> может направиться к <math>s</math>, используя цель маршрутизации <math>i</math>. | ||
Динамическая поддержка | '''Динамическая поддержка''' | ||
DHT должны работать в очень динамичной среде, где размер сети не известен заранее, и где нет постоянных серверов для поддержки хэш-функции или оверлейной сети (предполагается, что все серверы эфемерны). Это особенно актуально для P2P-сети, где серверами являются временные пользователи, которые могут приходить и уходить по своему усмотрению. Следовательно, должен существовать децентрализованный протокол, исполняемый присоединяющимися и уходящими пирами, который бы поступательно поддерживал структуру системы. Кроме того, присоединяющийся пир должен быть способен корректно выполнить этот протокол, изначально имея информацию только об одном, произвольном узле сети. | DHT должны работать в очень динамичной среде, где размер сети не известен заранее, и где нет постоянных серверов для поддержки хэш-функции или оверлейной сети (предполагается, что все серверы эфемерны). Это особенно актуально для P2P-сети, где серверами являются временные пользователи, которые могут приходить и уходить по своему усмотрению. Следовательно, должен существовать децентрализованный протокол, исполняемый присоединяющимися и уходящими пирами, который бы поступательно поддерживал структуру системы. Кроме того, присоединяющийся пир должен быть способен корректно выполнить этот протокол, изначально имея информацию только об одном, произвольном узле сети. | ||
