OPTIMIZING MAINTENANCE COST OF P2P VORONOI OVERLAY NETWORKING

Abstract

We present a P2P overlay network protocol based on Voronoi diagram and Delaunay triangulation. The proposed algorithms of node join and leave include the resolution of conflicts between distributed operations, by which concurrent networking is provided. The topology updating operations are performed having minimized maintenance cost measured in the number of messages. The proposed approach provides scalability by guaranteeing that for a large network the cost of a single join operation is constant. For proving this result, we evaluated the network maintenance cost by using an event-driven simulator. В цій роботі ми представляємо протокол для оверлейної пірингової мережі, заснований на діаграмі Вороного і тріангуляції Делоне. Запропоновані алгоритми приєднання і від'єднання мережевого вузла включають в себе вирішення конфліктів між розподіленими операціями, за допомогою чого забезпечується функціонування операцій зі зміни мережевої топології в синхронному режимі. Операції відновлення топології виконуються з мінімізацією витрат, які ми вимірюємо в кількості повідомлень. Пропонований підхід забезпечує масштабованість: гарантується, що у великій мережі вартість окремого приєднання вузла наближається до постійних значень. За допомогою емулятора оцінено вартість операцій по зміні мережевої топології. В этой работе мы представляем протокол для оверлейной пиринговой сети, основанный на диаграмме Вороного и триангуляции Делоне. Предложенные алгоритмы присоединения и отсоединения сетевого узла включают в себя разрешение конфликтов между распределенными операциями, с помощью чего обеспечивается функционирование операций по изменению сетевой топологии в синхронном режиме. Операции по восстановлению топологии выполняются с минимизацией затрат, которые мы измеряем в количестве сообщений. Предлагаемый подход обеспечивает масштабируемость: гарантируется, что в большой сети стоимость отдельного присоединения узла приближается к постоянному значению. С помощью программы-эмулятора была оценена стоимость операций по изменению сетевой топологии.