Table of Contents
Abstract
1
Acknowledgements
iii
Abstract
1
1 Introduction
1.1 Motivation . . .
1.2 Objectives . . .
1.3 Contributions .
1.4 Thesis structure
.
.
.
.
2
2
4
5
5
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
6
6
6
7
8
9
10
10
10
11
12
12
13
14
15
16
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
2 Background
2.1 Multicast . . . . . . . . . . . . . . . . . . . . . . .
2.1.1 Introduction . . . . . . . . . . . . . . . . . .
2.1.1.1 IP Multicast . . . . . . . . . . . .
2.1.1.2 Application Layer Multicast . . .
2.1.2 Application layer multicast protocols . . . .
2.1.2.1 Application Domain . . . . . . . .
2.1.2.2 Deployment Level . . . . . . . . .
2.1.2.3 Group Management . . . . . . . .
2.1.2.4 Routing Mechanism . . . . . . . .
2.2 DHT-based multicast . . . . . . . . . . . . . . . . .
2.2.1 Introduction of P2P Networks . . . . . . . .
2.2.1.1 Unstructured P2P Network model
2.2.1.2 Hybrid P2P Network model . . . .
2.2.1.3 Structured P2P Network model . .
2.2.2 DHT-based structure P2P networks . . . . .
iv
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
TABLE OF CONTENTS
2.3
v
2.2.2.1 Chord Network . . . . . . . . . . . . . . . . . . . . .
2.2.2.2 Content Adressable Network . . . . . . . . . . . . . .
2.2.3 DHT-based multicast . . . . . . . . . . . . . . . . . . . . . . .
2.2.3.1 CAN-based multicast . . . . . . . . . . . . . . . . . .
2.2.3.2 Chord-based multicast . . . . . . . . . . . . . . . . .
2.2.3.3 Scribe . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.4 Topology optimization issues for DHT-based multicast . . . .
Related works on topology optimization for DHT-based multicast . .
2.3.1 SplitStream . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3.2 Capacity Aware Multicast based on Overlay Network - CAMChord . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3.3 DHT-based lightweight broadcast algorithms in large-scale computing infrastructures . . . . . . . . . . . . . . . . . . . . . . .
3 Bandwidth Adaptive Multicast
3.1 Overview . . . . . . . . . . . .
3.1.1 Node identifier . . . .
3.1.2 Finger table . . . . . .
3.2 Network Construction . . . .
3.3 Multicast method . . . . . . .
over
. . .
. . .
. . .
. . .
. . .
4 Simulations and Evaluations
4.1 Simulation description . . . . . . .
4.2 Evaluation . . . . . . . . . . . . . .
4.2.1 The depth of multicast tree
4.2.2 Control Overhead . . . . . .
5 Conclusions
Chord : BAM Chord
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
18
20
22
22
24
25
26
26
26
27
28
.
.
.
.
.
31
31
32
34
35
36
.
.
.
.
38
38
38
38
40
42
List of Figures
2.1
Type of transmissions . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
2.2
IP Multicast . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
2.3
A Comparison between IP multicast and application-layer multicast .
9
2.4
P2P Network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.5
A unstructured P2P Network with a server . . . . . . . . . . . . . . . 13
2.6
Gnutella-like P2P . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.7
An example of Hybrid P2P Model . . . . . . . . . . . . . . . . . . . . 15
2.8
Scheme of a classic Hash Table . . . . . . . . . . . . . . . . . . . . . 16
2.9
Scheme of a Distributed Hash Table (DHT) . . . . . . . . . . . . . . 17
2.10 A Chord ring with 6 bit identifier. Notice how the finger table is
organized and how K54 is looked up following Chord’s algorithm . . . 18
2.11 Example of Chord Finger table . . . . . . . . . . . . . . . . . . . . . 20
2.12 Example of Content Addressable Network . . . . . . . . . . . . . . . 21
2.13 Smart multicast in CAN. The dot represents the starting node . . . . 23
2.14 An example of Chord-based multicast method. In this example, Node
1 sends messages to all nodes in the Chord ring. . . . . . . . . . . . . 24
2.15 A simple example illustrating the basic approach of SplitStream.
Original content is split into two stripes and correlatively, an independent multicast tree is built for each stripes. A node is a leaf in
one tree and a interior in the other . . . . . . . . . . . . . . . . . . . 27
2.16 An example of CAM- Chord, neighbors of x. N = [0..31], cx = 3 . . . 28
2.17 Balanced Distributed broadcast tree construction using token in 16node Chord . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.18 Balanced Distributed broadcast tree construction using partition in
an 11-node Chord . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.1
An example of CAM- Chord, neighbors of x. N = [0..31], cx = 3 . . . 33
vi
LIST OF FIGURES
vii
3.2
3.3
An example of CAM- Chord, neighbors of x. N = [0..31], cx = 3 . . . 35
An example of CAM- Chord, neighbors of x. N = [0..31], cx = 3 . . . 37
4.1
4.2
4.3
Average path length . . . . . . . . . . . . . . . . . . . . . . . . . .
Maximum path length . . . . . . . . . . . . . . . . . . . . . . . . .
Average path length in Chord, CAM-Chord and BAM-Chord after
32 time steps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Average link number per node in Chord . . . . . . . . . . . . . . .
Average link in Chord, CAM-Chord and BAM-Chord after 32 time
steps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4
4.5
. 39
. 40
. 40
. 41
. 41
List of Tables
2.1
Definition of variables for node n, using m-bit identifiers . . . . . . . 19
viii
Abstract
In recent years, Distributed Hash Table (DHT) becomes active and ongoing area of
research at a lot of universities and labs. DHT has many advantages: Decentralization, scalability, fault tolerance, load balancing, data integrity, and performance,...
Those properties make DHTs are very suitable for deploying multicast services at
application layer and in fact, DHT-based network such as CAN, Chord, Pastry,
Tapestry, etc can be used to implement Internet-scale application layer multicast.
However, early DHT-based multicast systems are insufficient in addressing all
of these issues: Heterogeneous node capacity, large- scale multicast and dynamic
membership. Moreover, in those system, when one node joins into system through an
arbitrary way, some factors are not considered: nodes bandwidth, nodes positon on
DHT network (i.e node identifiers), thus, the multicast tree can be built inefficiently
and not balance in structure. The solution for assigning an appropriate number of
child nodes to each node is far from optimal in term of bandwidth: If the number
of child nodes is too high, low capacity node will be overloaded, therefore slows the
entire session multicast down. If the number of child nodes is too low, high capacity
nodes will be used inefficiently.
In this thesis, we study the method to optimize topology for DHT-based multicast. We propose a DHT- based bandwidth adaptive multicast system that forcus
on host heterogeneity, scalibility, fault tolerate. In our system, nodes bandwidth is
firstly considered, result of this process is the basis for determining the level of the
node and correlatively caculating nodes identify. Level of a node is used to define
maximum number of its child nodes. As a result, in our model, each node is assigned
an optimal numbers of child nodes to forward multicast data. Thus, our method can
make tradeoff between depth of the multicast tree and bandwidth of every node and
take advandtages of DHTs in maintaining multicast tree in churn overlay. System
chosen for implementation and avaluation is Chord. This model is called Bandwidth
Adaptive Multicast over Chord: BAM-Chord.
1
Chapter 1
Introduction
1.1
Motivation
Today, Internet continues to grow rapidly, many communication requirements that
we must deal with. Cause of the explosion in data communications, demand on
transferring large volumes of data to many destination quickly increases. To solve
bandwidth problems, multicast is a effective solution. As the most cost-effective
way of delivering the same data to a multiple receivers at the same time, multicast
is suited to a large number of applications as mobile Internet, e-commerce, content
rich applications, and multi-media services: television broadcast, video conferencing.
The word ”multicast” is typically used to refer to network layer multicast - IP
multicast and was proposed about some decades ago. However, IP multicast still
has not been widely deployed because of various technical and administrational
reasons. The disadvantages of implementing multicast at the IP level has led to
an interesting application-level multicast. Application layer multicast refers to the
implementation of multicast capability at the application layer instead of network
layer. A number of application-level multicast systems have been proposed that are
built using structured peer-to-peer (p2p) overlays.
Originally, distribute hash table (DHTs) were developed with applications like
peer-to-peer file sharing. Recent years, there has been considerable interest in applying DHTs to overlay multicast applications since it has many advantages: Decentralization, Scalability, Fault tolerance, Load balancing, and performance,...Those
properties make DHTs are very suitable for deploying multicast services at application layer and in fact, DHT-based network such as CAN, Chord, Pastry, Tapestry,
2
1.1. Motivation
3
etc has been already used to implement Internet -scale applicastion layer muticast.
However, early DHT-based multicast systems are insufficient in addressing a number
of technical issues:
• Heterogeneous output bandwidth of Node: Since the number of child nodes
of a node in a multicast tree is decided based on the DHT algorithm without
consideration of nodes bandwidth capacity, a node with low bandwidth may
become a bottleneck if it is an internal node of a multicast tree
• Effective bandwidth utilization: If a node with high bandwidth is a leaf node,
the system can not utilize the bandwidth capacity of the node to deliver multicast messages.
• Dynamic membership: The optimization of multicast trees must be achieved
even when member nodes join or leave at anytime.
To limit the multicasting load on a node, M. Castro, el al. propose a solution
in SplitStream (M.Castro, ), where one node informs its out-degree. When it receives a futher join requests, it pushdown this request to its children. Nevertheless,
Bharambe, et al. explored and found heterogeneity issue is not address with SplitStream (Feb, February 24 25 2005). With CAM CAM-Chord and CAM-Koorde
designs in (6-1, 6 10 June 2005), heterogeneity is tackled by allowing node to alter out-degree according to its capacity. However, they did not describe how to
maintain topology when the out-degree limits. Therefore, heterogeneity issue remains open, and should be addressed before deploying DHTs for high-bandwidth
multicasting applications. S. Ratnasamy, M. Handley, R. Karp, and S. Shenker
proposed CAN-based multicast (S. Ratnasamy & Shenker, Nov 7 9 2001). That
was the first application-level multicast scheme scales to groups of several thousands of nodes. Solution in (S.Q.Zhuang & J.D.Kubiatowicz., 2001) can scales to
large groups but has a single root node for each multicast group. It supports the
any-source model only by having the root node operate as a reflector for multiple senders. There have been several ways to deal with dynamic membership: In
(S.Q.Zhuang & J.D.Kubiatowicz., 2001), they ensure that the root node of the multicasting tree does not handle all requests to join or leave the multicast group; In
(J. Li & Lim, 2005), use multiple interior-node- disjoint trees to avoid single points
of failure in tree structures; In (S. El-Ansary & Haridi, February 2003) The earliest
4
Chapter 1. Introduction
DHT-based broadcasting work by El-Ansary, et al. did not address the issue of
dynamic membership.
Moreover, in those system, one node join into system through an arbitrary way,
thus, the multicast tree can be built inefficiently and not balance in structure. The
solution for assigning an appropriate number of children to each node is far from
optimal in term of bandwidth: If the number of children is too high, low capacity
node will be overload, therefore slows the entire session multicast down. If the
number of children is too low, high capacity nodes will be used inefficiently.
In this thesis, we study the method to optimize topology for DHT-based multicast. We propose a DHT- based bandwidth adaptive multicast system that forcus on
host heterogeneity, scalibility, fault tolerate. System chosen for implementation and
avaluation is Chord, a DHTs representative. We extend Chord to be more flexible
and it is called BAM-Chord: Bandwidth Adaptive Multicast Chord. Our method
can make tradeoff between depth of the multicast tree and out-degree of every node
and retain the advantages of a DHT network.
1.2
Objectives
This thesis aims our works at building a multicast system over DHT-based network.
Hence, we will study to attain the following objectives:
• Study P2P network, application layer multicast, DHT-based network and
DHT-based multicast system
• Study topology optimization problems for DHT-based multicast;
• Study models have been proposed on topology optimazation for DHT-based
multicast, advantages and disadvantages of those model
• Propose a improvement model for deploying multicast over DHT network:
BAM-Chord
• Evaluate the simulation results and compare with some existing model.
1.3. Contributions
1.3
5
Contributions
In the scope of this thesis,we propose a model for deploying multicast service over
DHT-based network. This thesis not only introduces the background of P2P network, DHT-based network, overall view of DHT-based multicast and related technical issues, but also makes the following contributions:
• Proposes an improvement that can optimize network topology. This makes
multicast tree more balanced and node’s bandwidth adaptation. This
• Proposes an algorithm to find an optimal position when node joins into multicast session.
• Proposes a improvement model that can address technical issues in earlier
existing systems
1.4
Thesis structure
Thesis is organized in 5 chapters. Besides the Introduction in Chapter 1, the rest of
this thesis is organized as followed:
• Chapter 2 introduces multicast, IP multicast, application layer multicast,
DHT-based network, multicast over DHT-based network and related works
on topology optimization for DHT-based multicast
• Chapter 3 descirbes proposed model for deploying multicast over Chord, a
DHT representative: Banwidth adaptive multicast over Chord: BAM-Chord
• Chapter 4 shows the simulation and evaluate the simulation results in comparison with Chord, CAM-Chord
• Chapter 5 concludes our work and points out some possible improvements of
our system in the future.
Chapter 2
Background
2.1
2.1.1
Multicast
Introduction
Unicast is a basic type of transmission in which information is sent from only one
source to only one destination. In another words, Unicast transmission is between
one-to-one nodes. This type of transmission is used at almost network protocols:
IP, TCP, UDP, HTTP, FTP,.... However, when one sender sends the same data to
many receivers, it is not effective to use unicast.
Broadcast is a type of transmission in which information is sent from just one
source but is received by all destinations connected to the network. This would
mean that every time a node use broadcast transmission, all the other node will
receive that information.
An example of broadcast is ARP (Address Resolution Protocol) which will broadcast the address resolution request to all other computers on the network. Another
example is DHCP (Dynamic Host Configuration Protocol)
Figure 2.1: Type of transmissions
6
2.1. Multicast
7
Multicast is a very much different from Unicast and Broadcast in definition and
application as well. It is a type of transmission or communication in which the
information is sent by one source to a set of destination.
Many people think is an excellent transmission method for multimedia: Internet
radio broadcast, television broadcast, video conferencing, stock market tickers, slide
presentations, etc. However, multicast is also suited to a large number of other
applications: file transfers to multiple locations, dynamic web page updates, online
gaming, news feeds, chatrooms,...
Multicast is the most efficient method of delivering the same data to multiple
receivers at the same time. Servers send only one data stream to reach any number
of end-users. Using unicast, a server would need to send out as many streams as
there are receivers. This increases the CPU load, bandwidth required to reach that
audience. Using multicast, there will only be a single copy of the data streamed
across any links, therefore, can decrease bandwidth without upgrading links and
routers.
2.1.1.1
IP Multicast
The type of communication between one sender and one receiver (a connection between a Web browser and a server) can be addressed by basic TCP/TP network.
However, there is an emerging class of applications require multi-point communications between one or more senders and several receivers in order to work well.
In this case, data is sent from a sender to the receivers asynchronously as needed.
IP Multicast is designed to solve this problem. First introduced by S. Deering in
1988 [1], IP multicast is a method of sending Internet Protocol (IP) datagrams to a
group of interested receivers in a single transmission. In IP multicast, router has to
be equipped with multicasting capabilities. Router actively participate in multicast
and has a very important role. Routers make copies of packets as need and forward
towards multicast receivers.
In this model, all interested host form a multicast group for communicating with
each other through sending a message to multicast router using multicast group
membership discovery protocol as: IGMP (IPv4) or MLD (IPv6). IMGP stands
for Internet Group Management Protocol and MLD stands for Multicast Listener
Discovery. After joining to a multicast group, a host can receive all data that are
sent for that belonging multicast group without knowing the source address. Each
8
Chapter 2. Background
Figure 2.2: IP Multicast
of the multicast group is identified by a special multicast address called class-D
address (224.0.0.0 through 239.255.255.255).
IP muticast has all of advantages of multicast transmission. However, important
issues such as routing, group management, address allocation, authorization and
security, quality of Service (QoS) and scalability are not addressed effectively, IP
Multicast has not been widely deployed.
Due to the increasing number of application such as video-conferencing, multiparty games, private chat rooms, web cache replication and database/directory replication, and a lack of widely deployment of IP multicast in all IP-based networks,
there has been interest in multicast protocols that can be supported without relying
on the IP multicast infrastructure, and do not depend on multicast-capable routers.
This is the so-called application-layer multicast (ALM).
2.1.1.2
Application Layer Multicast
The concept of application level multicast is implementation of multicasting functionality at application layer instead of network layer. As a result, the multicastrelated functionalities are moved from routers to end-hosts. The basic idea of
application-layer multicast is shown in Figure 2.3 : S establishes unicast connections and send data to D1 and D2; In turn, D1, D2 delivers data to D3, D4 via
unicast connection respectively.
In IP multicast, data packets are replicated at routers inside the network. In
2.1. Multicast
9
Figure 2.3: A Comparison between IP multicast and application-layer multicast
ALM, data packets are replicated at end hosts. Logically, the end-hosts form an
overlay network, and the goal of ALM is to construct and maintain an overlay for
data transmission. Since IP Multicast is implemented by network routers and avoids
multiple copies of the same multicast packet on the same link. ALM is implemented
by application end-host and can not avoid multiple copies of the same packet on
the same link. Thus, ALM is less efficient than network layer multicast. However,
compared to IP multicast, application level multicast has some advantages:
• First, most proposed ALM models do not require any special support from
network routers, therefore, ALM can be widely deployed.
• Second, ALM is more easily deploy than IP multicast because ALM avoids
issues related to iner-domain multicast.
• Third, in recent years, numbers of improvements in ALM technology overcome its weakness and ALM become a up-and coming solution, DHT-based
multicast is an example.
2.1.2
Application layer multicast protocols
There have been a lot of ALM protocols with a different approaches and characteristics. In this thesis, we only review and give brief introduction about some important
categories and general approaches of different protocols as presented in (M. Hosseini,
2007).
10
Chapter 2. Background
2.1.2.1
Application Domain
The application domain determines the number of users that a protocol must support, the data types a protocol supply users, and the metrics that multicast tree
attempts to optimize. Thus, ALMs deploy as some categorization:
• Audio/video streaming: Protocols in this application domain usually involve
a single source distributing media to a large number of receivers. The metric
is bandwidth and latency
• Audio/video conferencing: Protocols in this application domain usually involve
a multi-party conferencing session, interacting groups in this session have small
to medium size. Important metrics are bandwidth and latency.
• Generic multicast service Protocols in this application domain usually try to
create a generic multicast service based on specific metrics that can affect a
variety of applications.
• Realiable data broadcast and file transfer: Reliable transfer and distribution
of files. Bandwidth is the only metric.
2.1.2.2
Deployment Level
Deployment level determines what level the protocol is expected to be deployed:
at the infrastructure level or end system level. Infrastructure-level, also known as
proxy-based ALM protocols, requires the deployment of dedicated servers/proxies
on the Internet where they self-organized into an overlay network and provides a
transparent multicast service to the end-user. End system level ALM protocols
assume only a unicast service from the infrastructure and expect end-system hosts
to participate in providing the multicasting functionality by taking on some of the
forwarding responsibility
2.1.2.3
Group Management
After deciding what is application domain and deployment level of ALM protocol,
designer must make some key decisions to determine how to manage a group of
nodes in a multicast session. Some key factors are considered: How users find out
the multicast session, how users join a session, how users leave, can the users still
contribute to existing multicast session even if they are not a part of it; Group
2.1. Multicast
11
management is centralized or distributed and how this affects the design and service
provided; Mesh-first approach or tree-first approach is taken? The advantages and
the disadvantages of each approach?
Mesh-first versus Tree-first In the mesh-first approach, the mest topology is
created at the begining, member nodes keep a connected in this topology. Then
multicast tree is built based on the mesh relative of nodes to the root. In the treefirst approach, the multicast tree is built directly without any mesh. The member
nodes explicitly select their parent from the known members in the tree. Parents
is chosen based on running algorithm to detect and avoid loops. The advantages of
tree-first approach is that this approach gives direct control over the tree, mer nodes
can select a best parent neighbor that has enough resources. Another advantage of
the tree-first approach is that it has a lower communication overhead. However, the
disadvantage is that when a member changes a parent, it drags all of it descendents
with it. The advantage of the mesh-first approach is fault tolerance, it is possible
to manipulate the tree topology to a significant extent by selecting mesh neighbors
and changing the metrics. This approach is suitable for multi-source applications.
The disadvantages of this approach is that it is difficult to do load balancing and it
has higher control overhead.
Source Specific Tree versus Shared Tree Source-specific tree is built by minimizing
the length of the path to a specific individual destination. Shared tree is built by
minimizing the total number of hops or the cummulative end-to-end delay to forward
the packet to all the destination. The choice between a source-specific tree and
shared tree usually depends on whether the multiple sources use the same overlay
for data distribution or not. When there is a multiparty communication, shared trees
are preferred because it is better than source specific tree in term of the maintenance
cost. On the other hand, source specific tree allows for optimization of the tree for
a given source, but cannot support efficiently multiple sources on that tree
2.1.2.4
Routing Mechanism
Group 1: Shortest Path This group of ALMs use RTT measurement to determine
the shortest path tree from the source to the end hosts and minimize the time delay
for each applicastion while considering the degree constraint and QoS. A Shortest
Path Tree constructs a minimum cost path from source node to all its receivers. For
example: Yoid, SpreadIt, TAG...
12
Chapter 2. Background
Group 2: Minimum Spanning Tree This group tries to construct a low cost
tree. A Minimum Spanning Tree is a tree with minimum total cost spanning all the
members. For example: ALMI, HBM
Group 3: Clustering Structure This group constructs a cluster of nodes that can
be use to construct trees. For example: NICE, ZIGZAG
Group 4: Peer-to-Peer Structure In P2P structure, Reverse-path forwarding or
Forward-path forwarding is used for routing
2.2
2.2.1
DHT-based multicast
Introduction of P2P Networks
In simplest form, a peer-to-peer (P2P) network is created when two or more computers are connected and share resources (such as processing power, disk storage
or network bandwidth) without going through a server. Contrast to client-server
networks, in P2P network, peers are both suppliers and consumers of resources. A
P2P network model allows many PCs to pool their resources together.
Figure 2.4: P2P Network
When Shawn Fanning created Napster in 1999, he did not imagine that today,
P2P networks have been receiving increasing demand from users. P2P networks are
decentralized, self-organized, and dynamic, they offer an alternative to the traditional client-server model of computing. In contrast to Client-server architecture,
P2P networks are almost unlimited in their scalability.
In recent years, due to the advantages of P2P networks, they have been widely
used in many ares: Instant Messaging, File Sharing, Collaborative Community, IP
2.2. DHT-based multicast
13
Telephony, High Performance Computing - Grid Computing the P2P networks have
become a focus of research at almost every major university.
2.2.1.1
Unstructured P2P Network model
Unstructured P2P network is form when each participating node connects to others
arbitrarily, and such networks can be easily constructed. When a new peer wants
to join the network, it can copy links of another existing node then forms its own
links.
Figure 2.5: A unstructured P2P Network with a server
In an unstructured P2P network, if a peer wants to find desired data in the
network, the query has to be flooded through the network to find as many peers as
possible. However, there is no way to guarantee that flooding will find a peer has
the desired data. Thus, the main disadvantage with unstructured P2P networks is
that the queries may not always be resolved. When a peer looks for data shared by
only a few other peers, its search will be likely unsuccessful and hence such networks
typically have very poor search efficiency. Also, the bandwidth cost of searching on
unstructured P2P network would grow exponentially to the number of connected
nodes.
The typical unstructured P2P networks is Gnutella. Peer nodes of the system
are organized randomly in unstructured overlay and described as servent. A new
node, who wants to join in the system, would perform an operation ”Join”. Firstly,
it would contact with a bootstrap node. Then bootstrap node would send back its
14
Chapter 2. Background
own contact list of existed node, which is chosen randomly. The new node would
store this list of the existed node as its neighbors. The new node may reach other
nodes in the communication network base on its neighbor. Following figure shows
an example of locating resources in a Gnutella-like P2P environment.
Figure 2.6: Gnutella-like P2P
2.2.1.2
Hybrid P2P Network model
In Unstructured P2P Network model, there is no correlation between a peer and its
data, queries might not always be resolved. In hybrid P2P network model, problems
of routing and lookup in unstructured P2P Network are solved . There peer nodes
are divided into two types, data nodes and hub nodes. Data node stores real data
and information of a hub node. Hub node is the same as a ”server”, it do not store
real data. It store only indexes to files in the network. To join in the system, each
node has to contact with a server. Since, the server would create indexes for these
files, and then it stores these indexes in its database.
As unstructured P2P Network model, Hybrid P2P network is easily constructed
because it does not need to implement distribution and routing algorithms. Moreover, Hybrid model does not use query flooding or random searching, since it is
more efficient than unstructured model. However, this model is essentially based
on ”servers” to guarantee successful routing and searching, system can not exist if
those servers get error.
In Hybrid P2P Model, eDonkey network is a typical example. There is no central
hub for the network. eDonkey client programs connect to the network to share files.
2.2. DHT-based multicast
15
Figure 2.7: An example of Hybrid P2P Model
eDonkey servers act as communication hubs for the clients, allowing users to locate
files within the network.
2.2.1.3
Structured P2P Network model
Unlike Hybrid P2P network where some hub nodes acting as ”servers”, the Structured P2P Network is completely decentralized and self-organizing. Structured P2P
model is constructed to achieve efficiently data searching, routing and distribution
among peers. Each node has capacities of storing data and routing to other nodes
based on a common routing algorithm. Nodes are arranged in a structured fashion.
When a new node joins into the network, a network identify (ID) is assigned to
it, this ID is created by using a global consistent hash function. Node ID represent
its position on the network and correlatively, a portion of data corresponding to.
When a node wishes to look for a resource, it must be redirected to the node which
is supposed to hold it by using a efficient look up function.
Structured P2P network is a scalable, efficient, completely decentralized and
self-organizing, and load balanced model. Each node stores information of O(logN)
neighbors. Routing algorithm allows it looking up any key with O(logN) hop time.
Because of the routing algorithm based on globally consistent hash function, a set of
keys are distributed equally to the key space. However, this P2P network model faces
to some challengers such as: avoiding bottlenecks in particular nodes, adaptation to
- Xem thêm -