Наукові конференції, Научные конференции » Наука і життя (16-18.05.2016) » Агеєнко Ю. М., професор, доктор технічних наук, Кулаков Ю. О. СПОСІБ ДИНАМІЧНОЇ МАРШРУТИЗАЦІЇ В МЕРЕЖАХ P2P

Агеєнко Ю. М., професор, доктор технічних наук, Кулаков Ю. О. СПОСІБ ДИНАМІЧНОЇ МАРШРУТИЗАЦІЇ В МЕРЕЖАХ P2P

Категорія: Наука і життя (16-18.05.2016), Сучасні інформаційні технології

УДК: 004.771

 

СПОСІБ ДИНАМІЧНОЇ МАРШРУТИЗАЦІЇ В МЕРЕЖАХ P2P

Агеєнко Ю. М., професор, доктор технічних наук, Кулаков Ю. О.

Національний технічний університет України «Київський політехнічний інститут», Україна, м. Київ

 

У статті проведено огляд існуючих способів динамічної маршрутизації в мережах Peer-to-Peer, розглянуто їх основну концепцію, характерні переваги та недоліки. Запропоновано модифікацію алгоритму динамічної маршрутизації в неструктурованих децентралізованих мережах P2P на основі вивчення зовнішнього локального стану мережі. Представлено переваги модифікованого алгоритму, який дозволяє зменшити час відповіді на запит, збільшити подібність документів до теми запиту та кількість успішних запитів.

Ключові слова: алгоритм маршрутизації, пошук інформації, пошук в ширину, індекс маршрутизації, експертні групи, однорангова мережа.

 

Агеенко Ю. Н., Кулаков Ю. А. Способ динамической маршрутизации поиска інформации в неструктурированных сетях P2P. Национальный технический университет Украины «Киевский политехнический институт», Украина, г. Киев

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

Ключевые слова: алгоритм маршрутизации, поиск информации, поиск в ширину, индекс маршрутизации, экспертные группы, одноранговая сеть.

 

Yuliia Aheienko, Yurii Kulakov Adaptive routing algorithm in P2P networks/ National Technical University of Ukraine "Kyiv Polytechnic Institute", Ukraine, Kyiv

The article reviewed the existing methods of dynamic routing in Peer-to-Peer networks, considered their basic concept, specific advantages and disadvantages. Propose the modification of the dynamic routing algorithm in unstructured decentralized P2P networks based on the study of the external local network conditions. Presented the benefits of the modified algorithm, which allows reduce time of a reply to the request, increase similarity of documents to request subject and the number of successful requests.

Key words: routing algorithm, information search, breadth-first search (BFS), routing index, expert groups, peer-to-peer network (P2P).

 

Вступ. У наш час широкого розповсюдження набув варіант архітектури системи, основою якої є мережа рівноправних вузлів, тобто peer-to-peer архітектура. Однорангові (peer-to-peer, P2P – рівний до рівного) мережі – це концепція інформаційної мережі, в якій її ресурси розосереджені по усіх системах. В одноранговій мережі всі комп'ютери рівноправні, кожний з них може бути як клієнтом, так і сервером, що дозволяє зберігати працездатність мережі при будь-якій кількості й будь-якій комбінації доступних вузлів [1].

Через те, що кожен мережевий комп'ютер може служити сервером, користувачам важко відслідковувати, на якій машині знаходиться необхідна їм інформація, а це означає, що у мережах P2P важко організовувати зберігання та облік даних. З ростом числа вузлів, на яких повинна відбуватися перевірка, пошук ресурсів ускладнюється через децентралізовану природу мережі.

Актуальність і постановка задачі. Відповідно до способу організації даних, системи P2P поділяють на дві категорії: структуровані та неструктуровані. У неструктурованих мережах позиція вузла в мережі не є попередньо визначеною, в той час як структуровані мають конкретні правила, в яких роз’яснено, де розташовується вузол, приєднаний до мережі. Беручи до уваги, що в неструктурованих системах P2P, вузли з'єднані один з одним в довільному порядку, ці мережі пропонують більш гнучке і автономне середовище, оскільки не потребують значного управління для розміщення ресурсів та контролю топології вузлів.

Так як пошук ресурсів вважається слабким місцем в масштабованості неструктурованих P2P мереж, то основною їх проблемою є створення ефективної стратегії маршрутизації для пошуку, тобто визначення місцезнаходження інформації, необхідної користувачу. Більшість існуючих систем підтримує простий пошук об'єкта по ключу чи ідентифікатору. Деякі системи можуть підтримувати більш складні запити, наприклад, за ключовими словами, які знаходять документи, що містять їх. Одні P2P системи спрямовані на пошук єдиного елементу даних, інші – на пошук всіх елементів даних або якомога більшої їх кількості, що задовольняють умові. Бажані властивості алгоритмів пошуку включають високоякісні результати запиту, мінімальні витрати на підтримку маршрутного стану вузла, високу ефективність направлення запитів, балансування навантаження, стійкість до збоїв вузла та підтримку складних запитів.

Враховуючи, що задача пошуку в однорангових мережах зводиться до швидкого та ефективного знаходження найбільш релевантних відповідей на запит, що передається вузлом у всю мережу, а також той факт, що стратегія маршрутизації пошуку в неструктурованій P2P мережі повинна враховувати її динамічні аспекти, можна зробити висновок, що вивчення, аналіз та дослідження алгоритмів маршрутизації пошуку в динамічних неструктурованих мережах P2P є дуже важливим завданням. Зокрема, актуальними у наш час є задачі покращення алгоритму маршрутизації пошуку, зменшення мережевого трафіку, що генерується під час обробки запиту, і у той же час отримання швидких і якомога якісніших результатів.

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

Існують різні класифікації методів пошуку. Одна з класифікацій базується на пересиланні запитів: детермінована та імовірнісна [2]. У детермінованому підході запит, що пересилається, є детермінованим (наприклад, має локальні індекси), інформація про шлях запиту використовується для маршрутизації. При ймовірнісному підході запит направляється або за певними правилами, або у випадковому порядку (маршрут запитів будується через випадково обрані вузли).

Друга класифікація – це методи сліпого та інформованого пошуку [3]. Ця класифікація базується на інформації про місцезнаходження вузлів чи об'єктів: у сліпому пошуку вузли не тримають інформацію про місце розташування об'єкта, а у інформованому пошуку вузли збирають деякі метадані, які допомагають при операціях пошуку.

Способи сліпого пошуку мають просту реалізацію і не використовують додаткових параметрів, але часто завантажують мережеві канали великою кількістю. Вузли не тримають ніякої інформації про P2P мережу або ймовірні місця розташування об'єктів для маршрутизації запитів. До таких методів відносять: пошук в ширину (Breadth First Search, BFS) [3; 4], випадковий пошук в ширину (Random BFS, RBFS) [3; 4], ітеративне поглиблення [2], алгоритм випадкового обходу [2; 3] та алгоритм випадкового обходу рівня k [3].

Найбільш цікавими методами пошуку в неструктурованих мережах є способи інформованого пошуку. У інформованих пошукових механізмах вузли зберігають деяку інформацію про маршрутизацію для пересилки запитів до підходящих вузлів. Ця інформація базується на декількох параметрах, таких як популярність об'єктів, ймовірність успішного знаходження інформації тощо. Інформовані підходи мають складнішу реалізацію і вимагають використання додаткових параметрів вузла, але є більш ефективними. До таких методів відносять: інтелектуальний пошук (Intelligent Search Mechanism, ISM) [3; 4], адаптивно-ймовірнісний пошук (Adaptive Probabilistic Search, APS) [2; 3], пошук на основі індексів маршрутизації [4] та алгоритм експертних груп з використанням індексів маршрутизації [5].

Пошук на основі індексів маршрутизації є модифікацією алгоритму пошуку в глибину (Depth First Search, DFS), всі інші – модифікації BFS пошуку; алгоритм ітеративного поглиблення належить до детермінованих методів пошуку, всі інші – імовірнісні. Інший підхід класифікації схем пошуку в неструктурованих системах P2P розділяє їх на алгоритми з відправленням запиту всім сусідам і тільки підмножині сусідів. Кращими є алгоритми з використанням підмножини сусідів, адже запит в даному підході відправляється тільки підмножині домінуючих вузлів, пріоритет яких розраховується в різних алгоритмах за своїми критеріями. В ітеративному поглибленні та в класичному методі пошуку в ширину запит відправляється всім сусідам вузла, у всіх інших схемах – лише підмножині сусідів.

Опис модифікованого алгоритму. Враховуючи, що ключову роль при пошуку ресурсів відіграє час затримки та якість результатів, можна зробити висновок, що для вирішення поставленої задачі більше підходять алгоритми модифікованого BFS пошуку. Найкращі результати серед них показує алгоритм експертних груп з використанням індексів маршрутизації, який відноситься до ймовірнісних алгоритмів з відправленням запиту тільки підмножині сусідів.

Алгоритм експертних груп з використанням індексів маршрутизації представлено у роботі [5]. Індекс маршрутизації зберігає значення подібності теми поточного вузла до однієї з тем сусіднього вузла і якщо це значення не менше за необхідний поріг подібності тем, то цей вузол є “хорошим” сусідом для перенаправлення йому запиту. Варто звернути увагу, що індекс маршрутизації спочатку порожній і заповнюється при додаванні документів до вузла. Коли пір приєднується до мережі, він вибирає випадкових сусідів для з'єднання. Після цього він повинен поширити свої знання, щоб отримати знання від інших вузлів, широкомовно передаючи свої характеристичні вектори.

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


Повний текст статті за посиланням Stattya_Ageyenko.doc [94,5 Kb] (cкачиваний: 0)

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

Добавление комментария

Имя:*
E-Mail:
Коментар:
Введите код: *

Карта сайту

^