Transcript P2P File Sharing Protocol for Reducing Duplicated Messages

Structured P2P Network for Loop
Avoidance
Chanmo Park
August 27, 2003
[email protected]
NETWORKed MEDIA LAB.
DEPT. OF INFO. & COMM., K-JIST
Contents
 What is P2P?
 Essentials of P2P Sharing
 Approaches toward P2P Sharing (gnutella, Kazza,
Morpheus and CAN)
 Challenges
 Approach to Structured P2P Network
 Overview of Structured P2P Network
 Elements of Structured P2P Network
 Details of Structured P2P Network
 Conclusion
 References
NETWORKed MEDIA LAB.
DEPT. OF INFO. & COMM., K-JIST
2/26
What is P2P?
 Direct access between peer computers, rather than
through a centralized server
 Applications that take advantage of resources (storage,
cycles, content, human presence) available at the edges
of the internet
 Offers a way of decentralizing administration on the
resources
 Sharing of computer resources by direct exchange
 Self-organizing capacity
NETWORKed MEDIA LAB.
DEPT. OF INFO. & COMM., K-JIST
3/26
Essentials of P2P Sharing
 Construction of P2P Network
o Self-Organization
 Decentralized Resource Administration
o Sharing resources
 Content Discovery
 Stability
o Recovery from the failure
NETWORKed MEDIA LAB.
DEPT. OF INFO. & COMM., K-JIST
4/26
Approaches toward P2P Sharing
 Unstructured network and pure decentralized
o Gnutella
 Unstructured network and partially decentralized
o Kazza, Morpheus
 Structured network and pure decentralized
o CAN
NETWORKed MEDIA LAB.
DEPT. OF INFO. & COMM., K-JIST
5/26
Gnutella Protocol for P2P File Sharing(1)
 Characteristics
o Gnutella is a distributed system for file sharing
 provide means for network discovery
 provide means for file searching and sharing
o Defines a network at the application level
o Employs the concept of peer-to-peer
 all hosts are equal (symmetry)
 there is no central point
o anonymous search, but reveal the IP addresses when
downloading
NETWORKed MEDIA LAB.
DEPT. OF INFO. & COMM., K-JIST
6/26
Gnutella Protocol for P2P File Sharing(2)
 Network Discovery
o A discovers its horizon (e.g., TTL = 2)
 send ping to its neighbors (broadcast)
 ping msg is forwarded if TTL>0
o Receiving ping, B,C and E, respond pong
 pong contains network info about its sender
 B forwards pong msgs from E and C, to A
NETWORKed MEDIA LAB.
DEPT. OF INFO. & COMM., K-JIST
7/26
Gnutella Protocol for P2P File Sharing(2)
 Network querying
o A searches the network (e.g., TTL = 2)
 send query to its neighbors (broadcast)
 the query is forwarded if TTL > 0
o B,C and E, respond with query_hit
 query_hit contains network info about where to
download the file from
 B forwards query_hit msgs from E and C, to
NETWORKed MEDIA LAB.
DEPT. OF INFO. & COMM., K-JIST
8/26
Gnutella Protocol for P2P File Sharing(3)
 There is nothing that stops a servant flooding its network region
with messages.
 Cost of maintaining Network
 Cost of searching file
From “A Quantitative Analysis of the Gnutella Network Traffic”
NETWORKed MEDIA LAB.
DEPT. OF INFO. & COMM., K-JIST
9/26
Kazza and Morpheus
 Kazza, Morpheus
o unstructured network
o partially centralized systems which use the concept of “SuperNodes”
o Peers are automatically elected to become SuperNodes if they
have sufficient bandwidth and processing power
o In Morpheus,
 a central server provides new peers with a list of one or more
SuperNodes with which they can connect.
 SuperNodes index the files shared by peers connected to them and
proxy search requests on behalf of these peers. Queries are therefore
sent to superNodes
NETWORKed MEDIA LAB.
DEPT. OF INFO. & COMM., K-JIST
10/26
CAN (Content Addressable Network)
 CAN (Content Addressable Network)
o a distributed, internet-scale hash table that maps file names
to their location in the network
 Purely decentralized
 Scalable
NETWORKed MEDIA LAB.
DEPT. OF INFO. & COMM., K-JIST
11/26
Challenges
 Duplicated Messages
o From loop and flooding
 Missing some contents
o From loop and TTL
 Oriented to File
 Why?
o Unstructured Network
o Too Specific
NETWORKed MEDIA LAB.
DEPT. OF INFO. & COMM., K-JIST
12/26
Approach to Structured P2P Network
 Contribute to a way
o to construct structured and general P2P network without loops and
TTL
o to know knowledge about constructed P2P network
 2-D Space
o Mapping each nodes’ network identifier into 2-D space
o Zone
 Each node occupies allocated area
 Aggregate nodes with same network identifier into a zone
 Maintain a binary tree
o Core
 Represent each zone
 Manage it’s zone
 Gateway between neighbor zones and it’s member
o Member
 Belonged to a zone
 Each message should be sent to its zone and members in its zone
NETWORKed MEDIA LAB.
DEPT. OF INFO. & COMM., K-JIST
13/26
Overview of Structured P2P Network
216
zone
0
Core node
216
Member node
Member Tree
Tx within a zone
Tx between zones
Tx between zones
NETWORKed MEDIA LAB.
DEPT. OF INFO. & COMM., K-JIST
14/26
Elements of Structured P2P Network
 Core/Member Nodes
o Neighboring zone information
 core info, zone info, direction
o Member information
 member node information, routing table
 Strategies
o
o
o
o
o
Routing Messages
Constructing Structured P2P Network
Managing Zone
Constructing Member Tree
Discovering Contents
NETWORKed MEDIA LAB.
DEPT. OF INFO. & COMM., K-JIST
15/26
Core/Member nodes
 7 neighboring zone information
o Core node (IP, Port#)
o Zone Range (x1,y1)~(x2,y2)
 Numbering zone
o
o
o
o
4 bits
00 : less than
01 : belong to
10 : greater than
1000
1001
1010
0110
0100
 Member information
o IP, Port#
 Member Tree
0000
0001
0010
o Uplink node info (only 1)
o Downlink node info (limited by 2)
NETWORKed MEDIA LAB.
DEPT. OF INFO. & COMM., K-JIST
16/26
Routing Messages
 Within a zone
o Depends on the Member Tree
(Binary Tree)
 Between zones
o If not a core, just send its
core
o Then core route this message
along X coordinate until
reaching destination x
o After that, route the message
along Y coordinate
 Every Message should have
originator’s IP and Port
NETWORKed MEDIA LAB.
DEPT. OF INFO. & COMM., K-JIST
1000
1001
0110
0100
0000
1010
0001
0010
17/26
Constructing Structured P2P Network(JOIN)
Node
Core
Bootstrapping
RP
JOIN/(JOIN_FWD)
Routing Message
Zone Management
Join As Core/Join As Member
Inform Neighboring Zones
Inform Members
Inform Neighboring Zones
NETWORKed MEDIA LAB.
DEPT. OF INFO. & COMM., K-JIST
18/26
Managing Zone(1)
same network identifier?
Yes
No
Msg Type?
AsMember
Split Zone
&
Accept as a Member
Rearrange Neighbors
Inform Members
Inform Neighbors
AsCore
Set itself
&
Inform Neighbors
Msg AsCore
Msg AsMember
Reply
NETWORKed MEDIA LAB.
DEPT. OF INFO. & COMM., K-JIST
Join Completed
19/26
Managing Zone(2)
 Splitting Zone
Y
o Network ID of New node
is within its zone range,
but Network ID is different
 Direction of Split
o X or Y direction
o Depends on Difference of
X and Y between two
network IDs
X
 Rearrange neighboring
zones
 Two nodes inform
neighbors of this change
NETWORKed MEDIA LAB.
DEPT. OF INFO. & COMM., K-JIST
20/26
Constructing Member Tree
 Each node
o Maintain information of all
members
o Creates a binary tree
6
2
 Using sorted IP address
4
o Rule
 one link between core
and a member
 Uplink is only one
 Downlink is limited by 2
Core
1
5
3
7
NETWORKed MEDIA LAB.
DEPT. OF INFO. & COMM., K-JIST
21/26
Discovering Content
 Content Discovery
o Send the Msg to its
Member and it’s core
o Core
Y
216-1
 On receiving it, Send it
neighbor zones along X
coordinate
 Also send it Neighboring
Y zones with flooding
 DiscoveryHit
NETWORKed MEDIA LAB.
DEPT. OF INFO. & COMM., K-JIST
X
216-1
0
22/26
Current Status
 Still Experimenting
 Environment
o GT-ITM
 Creating Network Topology
 About 100,000 nodes
 Your advice
o Simulator
 Myns
o OS
 Linux
o Dev. Lang.
 Gcc/g++ version 2.96
NETWORKed MEDIA LAB.
DEPT. OF INFO. & COMM., K-JIST
23/26
Conclusion
 By introducing 2-D space
o Construct structured P2P network
o Reduce duplicated msgs (from zone and aggregation of
same LAN nodes)
o Guarantee visiting the whole node
 Future Work
o
o
o
o
implementing simulator
Add Recovery Mechanism
Add native IP multicasting on Local Area Network
Reflect real network topology on simulator
NETWORKed MEDIA LAB.
DEPT. OF INFO. & COMM., K-JIST
24/26
Thank You!
NETWORKed MEDIA LAB.
DEPT. OF INFO. & COMM., K-JIST
25/26
References
 K. Calvert, M. Doar, and E. Zegura. Modeling Internet Topology.
IEEE Transactions on Communications, pages 160-163, December
1997.
 GT_ITM, Geogia Tech.
 myns Simulator, http://www.cs.umd.edu/~suman/research/myns/,
Univ. of Maryland, Suman Banerjee
 S. Ratnasamy, P. Francis, M. Handley, R. Karp, S. Shenker, "A
Scalable Content-Addressable Network", ACM Sigcomm 2001
 Peer-to-Peer Architecture Case Study: Gnutella. M. Ripeanu.
2001 International Conference on Peer-to-Peer Computing
(P2P2001), Linkoping, Sweeden, August 2001
 Kazza, http://www.kazaa.com/us/index.htm
 Morpheus, http://www.openp2p.com/lpt/a/990
NETWORKed MEDIA LAB.
DEPT. OF INFO. & COMM., K-JIST
26/26