Transcript ThesisPresentation1.1

PEER DISCOVERY PROTOCOL FOR JXTA
SNEHAL PATEL
ADVISIOR: DR. HUIPING GUO
CALIFORNIA STATE UNIVERSITY LOS ANGELES
1 DECEMBER 2006
1
Outline
• Peer-to-Peer Architecture
• Peer-to-Peer Networks
• Related Work on Peer Discovery
• Suggested Peer Discovery Protocol
• Conclusion
2
Peer-to-Peer Architecture
•
P2P are distributed systems
without any centralized control or
hierarchical organization.
•
Each peer is considered as a
server and a client is called a
servent.
•
P2P networks are self-organized
and self-administrative.
3
Outline
• Peer-to-Peer Architecture
• Peer-to-Peer Networks
– Type of P2P
– Advantages and Disadvantages of P2P
– JXTA and Gnutella
• Related Work on Peer Discovery
• Suggested Peer Discovery Protocol
• Conclusion
4
Types of P2P Networks
• Collaborative Computing: Combines the idle or unused
CPU processing power and/or free disk space of many
computer in the network
– Grid MP Platform
• Instant Messaging:
– MSN Messenger
– AOL Messenger.
• Affinity Communities: Group of P2P networks that is based
around file-sharing
– Napster
– Gnutella
5
Advantages of P2P
• Distributes the responsibility of providing services
• Prevents from a single point of failure
• Improves scalability
• Reduces network congestion
6
Disadvantages of P2P
• Query flooding
• Scalability
• Security
• Efficient group communication
7
Gnutella
• A common P2P file sharing network
• Purely a query flooding-based protocol
• Works on five different packet types:
–
–
–
–
–
•
ping: discover hosts on network
pong: reply to ping
query: search for a file
query hit: reply to query
push: download request for firewalled servents
Query flooding is one of the problems with Gnutella
8
Gnutella
9
JXTA
• Introduced by Sun Microsystems.
• JXTA is a set of open, generalized P2P protocol
specification, that allows any connected device, from cell
phone and PDAs, to desktops and servers; to network,
communicate, and collaborate in a fully decentralized
manner.
• Developed in Java and XML
• JXTA protocols are language-independent, platform
independent.
10
JXTA Peer Discovery Protocol
11
Outline
• Peer-to-Peer Architecture
• Peer-to-Peer Networks
• Related Work on Peer Discovery
– Decentralized and Self-Organizing
– Instant Message Relaying
• Suggested Peer Discovery Protocol
• Conclusion
12
Decentralized & Self Organizing
Mechanism
• Proposed by Moore and Suda.
• A discovery mechanism that structures relationship and
forwards discovery queries based on keyword similarity,
usage history, and small-world clustering.
• The peers in the networks are considered as agents that
contain a limited number of relationships to the other
agents.
13
Decentralized & Self Organizing
Mechanism
• The algorithm is divided into following sections
– The definition of agents and their relationship
– How the overall network of relationship are to be
organized
– How the relationship organization is used for discover
forwarding
• This peer discovery mechanism is limited to a small
clustering.
14
Instant Message Relaying Mechanism
•
Proposed by Cuihong Li, Bin Yu, and Katia Sycara.
•
The peer discovery mechanism is developed based on sending
messages to each other.
•
The source peer sends the query to some neighbors and promises
some payment to each receiver.
•
Each receiver decides the number of neighbors she relays the
message to.
•
Not feasible for an anonymous message relaying process.
•
Limited by the free-riding problem.
15
Outline
• Peer-to-Peer Architecture
• Peer-to-Peer Networks
• Related Work on Peer Discovery
• Suggested Peer Discovery Protocol
– Semi-Centralized, Agent-based Hierarchical Model
– Caching Mechanism
– Evaluation of the Model
– Update Mechanism
– Failure Handling and Recovery
– Performance
• Conclusion
16
Suggested Peer Discovery Protocol
• The thesis proposes a semi-centralized, agent-based
hierarchical tree schema for peer discovery of JXTA.
• The main proposal of the thesis is to use edge peers as
hosts, rendezvous peers as agents, and group the edge
peers based on their network proximity.
• This type of structure would provide better scalability than a
fully decentralized system.
17
Semi-Centralized, Agent-based Model
• The components used to construct the framework are:
– Registration Server (RS): Maintains a database about the
IP address of all the agents at different levels of the
hierarchy
– Agents: Act as a service provider to hosts.
18
Determine the number of Agents and their
threshold
Determine the no. of agents and their threshold
Input: N[DNS]
Output: N[A], N[G]
1.
N [P] = c % * N [DNS] where c is constant; 5 < c
<10
2.
N [A] = p % * N [P] = p % * c% * N [DNS] where c
is constant
3.
N [G] = N [P] / N [A]; N [A] < N [G]
19
Tmin
Determine the Host’s Agents and Grouping
Mechanism
Construction of Agent based Framework
Input: RS, Ah[i], H[j]
Output: join [H[j]; A1 [i]]
1: register [A1[i] for every i ; RS];
2: query [H[j] for any j; RS];
3: response [RS; H[j] for any j ];
4: ping [H[j] for any j; A1 [i] for every i];
20
Determine the Host’s Agents and Grouping
Mechanism
5: ST[k] ← Record time [H[j] for any j; A1 [i] for every i ] for
k = 1,2.. N
6: compute T[i] = Σ ST[k] / n for every k = 1
7: compute = min [T[i] for every i];
8: join [H[j]; A1 [i] with];
21
Caching Mechanism
• A peer will ping all the agents of level 1 to discover its
closest agent and computes the shortest time.
• A peer host will also cache the IP address and ping times of
a few agents having the shortest times.
• The main advantage is that if a host leaves the network and
tries to join again, it does not have to go through the query
and ping message process again.
22
Evaluation of the Framework
• The main contribution of this thesis is to provide a scalable
model for peer discovery, while maintaining load balancing
of the nodes and proximity feature of the grouping
mechanism.
• The model is very dynamic in nature once the framework is
constructed.
• The cost factor is involved with the maintenance of the
agents.
• The self-organization property of the P2P network is violated;
hence the model is more like a hybrid P2P model.
23
Update Mechanism
Peer join/leave mechanism
Input: Host, Agents at level 1
Output: Join the group
for every peer host
{
send_query_message (host [source] , RS [destination] )
send_response_message ( RS[source] , host [destination] )
send_ping_message ( host [source] , Agent_level_1(i) where i =
1,2,3,….[destination] )
compute sample ping times(host [source] , Agent_level_1(i) where i
= 1,2,3,….[destination])
compute_average_time ( host [source] , Agent_level_1(i) where i =
1,2,3,….[destination] )
24
Update Mechanism
compute min_average_time
send_join_message ( host[source] , Agent_level_1 with min_average_time
[destination] )
cache the IP addresses of few agents with the minimum ping times
}
Input: Host, Agent, quit message
Output: leave the group
Host sends a quit message to its agent
The agent breaks the connection with the host
The agent updates the database
25
Failure Handling and Recovery
• In a hierarchical tree structure failure handling can be
established by back up links.
• Back up links are created with agents that have the second
shortest ping time response.
• The failure detection can be done using “KeepAlive
messages”.
• The host and agents, or two agents exchange “KeepAlive
messages” to test network connectivity.
26
Performance of the Hierarchical Model
• The performance of discovery process is mainly based on
the number of routing connections.
• Fewer connections have a quick discovery process and
higher system performance.
• The average service discovery speed v can be defined as
v= r/d where r is the total number of requests
d is the total number of connections
• The complexity of the model is O(m) + O(log n) where m is
the no. of agents at level 1 and n is total no. of nodes.
27
Conclusion
• The thesis proposes a semi-centralized, agent-based
hierarchical model for peer discovery of the JXTA network.
• It would provide better efficiency and load balancing than
a fully decentralized model.
28
References
[1] JXTA First Edition. Brendon J. Wilson, June 2002.
[2] Mastering JXTA: Building Java Peer-to-Peer Applications. Joseph D. Gradecki.
[3] J. Verbeke, N. Nadgir, G. Ruetsch, et al., "Framework for Peer-to-Peer Distributed
Computing in a Heterogeneous, Decentralized Environment,"
[4] "Project JXTA Community Home Page," http://www.jxta.org/
[5] JXTA Technology: Creating Connected Communities, Sun Microsystems, Jan. 2004.
[6] Project JXTA: An Open, Innovative Collaboration, Sun Microsystems, April 25, 2001.
[7] Emir Halepovic, Ralph Deters, “The Costs of Using JXTA”, Department of Computer Science,
University of Saskatchewan
[8] Buyya , Rajkumar, Steve Chapin, and David DiNucci, “ Architectural Models for Resource
Management in the Grid”. In First IEEE/ACM International Workshop on Grid Computing
(GRID 2000), Bangalore, India, December 2000.
[9] Clarke, Ian, Oskar Sandberg, Brandon Wiley, and Theodor W. Hong., "Freenet: A distributed
anonymous information storage and retrieval system". In Proceedings of the Workshop on
Design Issues in Anonymity and Unobservability, July 2000, pp. 46-66
[10] Kalogeraki, Vana, Dimitrios Gunopulos, and D. Zeinalipour-Yiatzi," A local search
mechanism for peer-to-peer networks". In Proceedings of the Eleventh International
Conference on Information and Knowledge Management, 2002, pp. 300-307
[11] Junginger Markus, and Yugyung Lee, "A high performance messaging system for peer-topeer computing". In Proceedings of IEEE P2P Conference 2002, pp. 49-56
29
References
[12] Lee, Yugyung, Changgyu Oh, and E. K. Park, "Intelligent knowledge discovery in peer-topeer file sharing". In Proceedings of the Eleventh International Conference on Information
and Knowledge Management, 2002, pp. 308-315
[13] Napster. Available from http://www.napster.com/;
[14] Ratnasamy, Sylvia, Paul Francis, Mark Handley, Richard Karp, and Scott Shenker, "A
scalable content-addressable network". In proceedings of the 2001 Conference on
Applications, Technologies, Architectures, and Protocols for Computer Communications
August 2001
[15] Stoica, Ion, Robert Morris, David Karger, M. Frans Kaashoek, and Hari Balakrishnan,
"CHORD: A scalable peer-to-peer lookup service for Internet applications". Technical
report TR-819, MIT, March 2001
[16] Michael Moore and Tatsuya Suda, "A Decentralized and Self-Organizing Discovery
Mechanism”. Department of Information and Computer Science, University of California,
Irvine
[17] Cuihong Li, Bin Yu, and Katia Sycara, "An incentive mechanism for message relaying in
peer-to-peer discovery". In the proceedings of second workshop on the economics of
peer-to-peer systems, 2004
[18] M. Kelaskar, V. Matossian, P. Mehra, D. Paul, and M. Parashar, "A Study of Discovery
Mechanisms for Peer-to-Peer Applications". Department of Electrical and Computer
Engineering, Rutgers University, Piscataway, NJ
30
References
[19] Carlo Mastroianni, Domenico Talia, and Oreste Verta, ""A Super-Peer Model for Building
Resource Discovery Services in Grids: Design and Simulation Analysis". In the proceeding
of EGC 2005, LNCS 3470, pp. 132 – 143, 2005
[20] Cameron Ross Dunne, "Using Mobile Agents for Network Resource Discovery in Peer-toPeer Networks”. School of Computer Applications, Dublin City University, Dublin 9, Ireland
[21] Luciana dos Santos Lima, Antônio Tadeu Azevedo Gomes, Artur Ziviani,
Markus Endler, Luiz Fernando Gomes Soares, and Bruno Schulze, "Peer-to-Peer Resource
Discovery in Mobile Grids". Pontifícia Universidade Católica do Rio de Janeiro (PUC-Rio),
Laboratório Nacional de Computação Científica (LNCC), August, 2005
[22] Zhanping Yin and Victor C.M. Leung, "Third-Party Handshake Protocol for Efficient Peer
Discovery and Route Optimization in IEEE 802.15.3 WPANs". In the proceeding of IEEE
BroadNets 2005, Boston, MA, Oct. 2005
[23] Michael J. Freedman and Robert Morris, "Tarzan: A Peer-to-Peer Anonymizing Network
Layer". In the proceeding of CCS’02, November 2002
[24] Jan Sacha, Jim Dowling, Raymond Cunningham and René Meier, "Using Aggregation for
Adaptive Super-Peer Discovery on the Gradient Topology". In the proceeding of Digital
Business Ecosystem Project IST-507953
[25] Adeep S. Cheema, Moosa Muhammad, and Indranil Gupta, "Peer-to-peer Discovery of
Computational Resources for Grid Applications". In the proceeding of NSF CAREER, June 3,
2005
31
References
[26] Andraž Jere, Marko Meža, Boštjan Marušič, Štefan Dobravec, Tomaž Finkšt, and Jurij F.
Tasič, "Peer to Peer Search Engine and Collaboration Platform Based on JXTA Protocol". In
the proceeding of EUROCON 2003
[27] Massimo Paolucci, Katia Sycara, Takuya Nishimura, and Naveen Srinivasan, "Using DAMLS for P2P Discovery". Carnegie Mellon University, USA
[28] Michael Moore and Tatsuya Suda, "Adaptable Peer-to-Peer Discovery of Objects that
Match Multiple Keywords". In the proceeding of the 2004 International Symposium on
Applications and the Internet Workshops, 2004
[29] Tie-Yan Li, Zhi-Gang Zhao, and Si-Zhen You, "A-peer: An Agent Platform Integrating Peerto-Peer Network". In the proceeding of the Proceedings of the 3rd IEEE/ACM International
Symposium on Cluster Computing and the Grid, 2003
[30] Jan Sacha, Jim Dowling, Raymond Cunningham, and René Meier, "Discovery of Stable
Peers in a Self-Organizing Peer-to-Peer Gradient Topology". In the proceeding of
International Federation for Information Processing
[31] Naveen Srinivasan and Timothy Finin, "Enabling Peer-to-Peer SDP". University of Maryland
Baltimore County, Baltimore MD 21250
[32] P.A. Felber, E.W. Biersack, L. Garcés-Erice, K.W. Ross, and G. Urvoy-Keller, "Data Indexing
and Querying in DHT Peer-to-Peer Networks". Institute EURECOM, 06904 Sophia Antipolis,
France
32
Thank you!!
33
34
35
36