Abstract Efficient Broadcast in Structured P2P Networks.pdf
文本预览下载声明
Efficient Broadcast in Structured P2P Networks
Sameh El-Ansary1, Luc Onana Alima2, Per Brand1, Seif Haridi2
1Swedish Institute of Computer Science, Kista, Sweden
2IMIT-Royal Institute of Technology, Kista, Sweden
{sameh, perbrand}@sics.se, {onana, seif}@it.kth.se ?
Abstract
In this position paper, we present an efficient algorithm
for performing a broadcast operation with minimal cost
in structured DHT-based P2P networks. In a system of
N nodes, a broadcast message originating at an arbitrary
node reaches all other nodes after exactlyN?1 messages.
We emphasize the perception of a class of DHT systems
as a form of distributed k-ary search and we take ad-
vantage of that perception in constructing a spanning
tree that is utilized for efficient broadcasting. We con-
sider broadcasting as a basic service that adds to existing
DHTs the ability to search using arbitrary queries as well
as dissiminate/collect global information.
1 Introduction
Research in P2P systems resulted in the creation of many
Data/Resource- location systems. Two approaches were
used to tackle this problem; the flooding approach and
the Distributed Hash Table approach approach. The
common characteristic of both approaches is the con-
struction of an application-level overlay network. Table
1 includes some of the major differences between the two
approaches.
Flooding DHT
Queries Arbitrary Key Lookup
Query-Induced Traffic O(N) O(log(N))
Hit Guarantees Low High
Connectivity Graph Random Structured
Table 1: Flooding Approach vs. DHT Approach
The DHT approach with a structured overlay network,
determinism, relatively low traffic and high guarantees
is currently perceived in the P2P research community
as the ”reasonable” approach. Many systems were con-
structed based on that approach such as Tapestry [15],
Pastry [11], CAN [8], Chord [12], Kademlia [7]. In con-
trast, the flooding-based approach represented by [4, 3]
?This work is funded by the Swedish funding agency VIN-
NOVA, PPC project and by the Euro
显示全部