BC/NW 2009, №1 (14): 4.1

 

МАРШРУТИЗАЦИЯ В ПИРИНГОВЫХ СЕТЯХ

 

Хлюпин Ф. С.

 

(Москва, Московский государственный технологический университет «СТАНКИН», Россия)

 

Введение

В современном мире пиринговые сети (далее P2P) могут применяться для организации средств связи, таких как электронная почта, система мгновенных сообщений и телеконференций или организация систем обмена файлов. Основным компонентом P2P сетей является виртуальная сеть, которая непрерывно формируется при обнаружении новых участников, или группы участников, объединенных в такую же сеть.

Участники сети (узлы) присоединяются и покидают сеть. Такой процесс происходит постоянно. Нет никаких гарантий, что один раз установив оптимальный маршрут через тот или иной узел, он будет доступен в другой раз. Поэтому топология в такой сети постоянно меняется.

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

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

·        Масштабируемость

·        Сложность маршрутизации

·        Анонимность

Масштабируемость - это мера эффективности системы при возрастании количества узлов и/или числа сообщений в сети.

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

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

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

В данной статье рассматриваются различные реализации алгоритмов маршрутизации в P2P сетях. [1]

Алгоритмы

Gnutella

Одной из первых и крупнейших сетей массового использования была сеть Gnutella. Её концепция была проста. Для того чтобы присоединиться к сети, клиент обязан знать адрес хотя бы одного из узлов в данной сети. Установив однажды соединение с таким узлом, клиент может запросить адреса других узлов сети. Главная идея состоит в том, что каждый узел поддерживает соединение с определенным количеством соседних узлов, обычно с пятью участниками. [1]

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

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

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

Алгоритм, применяемый в сети Gnutella, хорошо работает для малого и среднего размеров сетей. Экспериментально доказано, что время поиска, при таком алгоритме, растет в геометрической прогрессии, при увеличении числа узлов в сети. Время поиска в сети Gnutella имеет следующую формулу: t=n^d, где n - количество времени, необходимое для опроса одного узла, а d - количество узлов вокруг данного узла.

Такой метод перебора, который вдобавок ещё и засоряет сеть большим числом сообщений, не самое оптимальное решение для маршрутизации P2P сетей. Также сеть Gnutella никак не приспособлена, для того, чтобы быть анонимной, а также производить простейший поиск по ресурсам в сети. [2]

Распределенные хеш-таблицы.

Алгоритм распределенных хеш-таблиц (далее DHT) очень удобен для публикации файлов, или других данных в P2P сети.

Существует хеш-функция, которая берет значение строки в байтах и возвращает идентификатор, который был сгенерирован на основе этого значения. Система хранит все идентификаторы файлов данных и их местоположение в огромной хеш-таблице, которая распределена по всем узлам. Одна исследовательская группа в массачусетском технологическом институте создала систему под названием Chord, в которой реализован алгоритм DHT. [1]

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

Когда узел захочет опубликовать какой-либо файл, он сгенерирует его идентификатор и пошлет свой IP и идентификатор своему предшественнику. Таким образом, все ресурсы будут проиндексированы в DHT и равномерно распределены по всем существующим узлам. Если 2 или более узла имеют одинаковый ресурс, то ключи будут храниться в таблицах на всех этих узлах, а запрашиваемой стороне будет представлен выбор.

Как только одному из узлов требуется получить файл, он берет его идентификатор и посылает запрос, который, со временем, дойдет до предшественника ресурса. Тот, в свою очередь, вернет IP адрес того узла, который хранит данные. Но каким образом узел запрашивает информацию именно у того узла, когда он не знает IP предшественника, а знает только ключ? Система Chord имеет, специальную адресную таблицу, где каждый узел хранит знания о тех узлах, которых он знает. Такие таблицы содержат списки ключей и IP адреса, которые организованы таким образом, что каждый узел хранит информацию об IP адресах, которые стоят перед данным узлом. Запрос включает в себя IP узла выполняемого запрос и, когда поиск останавливается на необходимом узле, высылается ответ. При этом не требуется обратное распространение ответа через все узлы.

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

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

Когда узел покидает сеть, он шлет свою таблицу, (так как сам является хранителем) своему хранителю, а также говорит своему предшественнику о выходе. При происхождении обоих событий адресные таблицы теряют актуальность. Поэтому, время от времени каждый узел шлет сообщения по всему кругу, целью найти новые узлы. [4]

Семантическая маршрутизация

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

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

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

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

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

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

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

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

данного метода маршрутизации.

Freenet

Freenet система p2p,  к которой перед разработкой поставили конкретные цели:

·        Политические (свобода слова, анонимность)

·        Технические (децентрализация всех функций сети и эффективное динамическое хранение и маршрутизация данных) [1]

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

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

в крайнем случае, как его вычислить. Как только это становится известно, пользователь шлет запрос на собственный узел. У каждого запроса есть значение таймаута и случайно сгенерированный ID, таким образом, другие участники сети могут легко распознавать данный запрос, если он у них уже был обработан ранее. Как только узел получает такой запрос, то он сначала проверяет собственное хранилище. Если файл присутствует, то возвращает сообщение, с идентификатором файла и ссылкой на него. Если не истек таймаут запроса, то узел передает запрос одному из своих соседей в собственной таблицы маршрутизации. Если запрос не удался, то узел передает другому соседу запрос. Если никто из соседей не вернул положительного ответа, то узел выдает для себя отрицательный результат. Если счетчик таймаута истек, то отрицательный результат передается обратно. Если положительный ответ получен, то узел посылает данные запросившему узлу, а тот, в свою очередь, передает данные тому узлу, кто инициировал запрос, при этом оставляя себе копию данного файла в своём хранилище. Если лимит хранилища истекает, автоматически удаляется последний по дате использования файл, а вместо него записывается данный. В таком случае наиболее популярная информация всегда хранится на большом количестве узлов, и к ней легко получить доступ. А данные, которые, не пользуются популярностью, в конце - концов, будут полностью удалены из такой файловой системы. [3]

Для того чтобы поместить файл в такую файловую систему, запрос делается по его хеш-ключу. Если такой файл будет найден раньше, чем случится таймаут по запросу, то файл добавлен не будет. Это связано с тем, что нет никакой потребности вставлять одинаковые данные по нескольку раз. Если файл найден не будет, то файл будет добавлен в файловую систему, а при первом запросе данного файла, он разойдется копиями по всему пути запроса от источника до запрашиваемого узла. При этом каждый узел, который имеет копию данного файла, может утверждать, что он является источником данного файла. Таким образом, предоставляется анонимность оригинальному источнику.

Выбор соседа, у которого стоит запрашивать данные, является одним из самых важных принципов работы сети Freenet, поскольку реализация данного алгоритма позволяет приспосабливаться к изменениям количества участников в сети. [1]

У каждого узла есть таблица маршрутизации, которая содержит адрес соседей, а также результаты работы в предыдущих запросах. Вначале данная оценка служила для получения информации о надежности узла, однако, потом была модернизирована и были добавлены характеристики, такие как время ответа и скорость передачи данных с данного узла. Когда узел получает запрос для нахождения специфического ключа, он производит поиск по собственной таблице, на предмет узла, который был наиболее успешен при нахождении данного ключа. Когда узел получает успешный ответ от другого узла, он создаст запись в собственной таблице. Важной особенностью этого процесса является то, что на периоде начальных запросов узлы станут специализироваться на специфических ключах. При первичной настройке сети, запросы шлются случайным образом, и если узел вернёт запрашиваемый файл, то запись в таблице будет заведена о данных узла и соответствующем ключе. Запросы о подобных ключах будут направлены к тому же узлу, и, в конечном счете, данный узел будет специализироваться на однотипных данных.[3]

Плюсы данной системы: [1]

·        Популярные данные быстро распространяются по всей сети.

·        Файлы распределены анонимно и свободно (это главная цель сети).

·        Алгоритм маршрутизации рассчитан на длительное функционирование сети.

Минусы данной системы:

·        Пользователи вынуждены хранить данные без их ведома, и выделять для них место на жестком диске.

·        Не так легко найти файл в сети, для этого необходимо знать его ключ.

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

·        Особенно медленен поиск, так как опрашивается только один узел в определённый момент.

 

Заключение

Бытует мнение, что пиринговые сети нужны только для распространения нелегальной информации. Однако этот далеко не так. Пиринговые сети в современном мире получают распространение при проектировании систем телеконференций, например Skype, а также позволяют повысить эффективность вычисления сложной задачи путем распределения процессов. [5]

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

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

Список используемой литературы:

1.     http://ntrg.cs.tcd.ie/undergrad/4ba2.05/group6/index.html P2P обзорная статья

2.     http://www.gnutellaforums.com/ Форум о сети Gnutella

3.     http://freenetproject.org/ официальный сайт проекта Freenet

4.     http://pdos.csail.mit.edu/chord/ страница проекта Chord

5.     http://www.compress.ru/Archive/CP/2005/10/39/ Статья Даниила Кальченко «Пиринговые сети»