Transcript Slides

UNIVERSITY OF JYVÄSKYLÄ
Chedar: Peer-to-Peer Middleware
Presentation for 8th International Workshop on Javatm for
Parallel and Distributed Computing (IWJPDC 2006)
25.4.2006
Annemari Auvinen, research student
Department of Mathematical Information Technology
University of Jyväskylä, Finland
http://tisu.it.jyu.fi/cheesefactory
With co-authors Mikko Vapa, Niko Kotilainen, Matthieu Weber and Jarkko Vuori
UNIVERSITY OF JYVÄSKYLÄ
Agenda
•
•
•
•
•
Peer-to-Peer Networks
Chedar
Chedar’s Structure
Messages
Topology Management Algorithms
UNIVERSITY OF JYVÄSKYLÄ
Peer-to-Peer Networks
• Peer-to-Peer (P2P) networks allow sharing of
resources (e.g., computing power, storage
space) over the Internet
• Every node serves as a server and a client
• In contrast to clusters, in P2P networks all the
tasks and responsibilities for managing the
network are shared between peers
UNIVERSITY OF JYVÄSKYLÄ
Related Work
• Gnutella
– Pure P2P protocol
– Search queries are broadcasted by using BFS with TTL
– Pre-defined amount of neighbors
• Chedar differs:
–
–
–
–
–
Middleware
Topology management algorithms
4 search algorithms
Resource reply routing
XML-based structured resource description
UNIVERSITY OF JYVÄSKYLÄ
Chedar
• Chedar is a totally decentralized P2P
middleware implemented using Java
• Neighbor’s goodness is defined based on the
resource replies the node has received from
the neighbor
• Basis for P2P applications: distributed
computing (P2PDisCo), data fusion,
extension for mobile devices
UNIVERSITY OF JYVÄSKYLÄ
Structure 1/3
• ChedarClient
– API for Chedar
startConnecting()
setMonitor(iMonitor)
pingMessage()
setResources(resource)
createResourceQuery(query,
algorithm, ttl)
setTrafficLimit(limit)
forceConnection(id)
forceDisconnection(id)
closeAllConnections
– By implementing a
monitoring interface
iMonitor the application
may get events about
sent and discarded
queries, forwarded
messages, sent replies,
received replies and
connection requests
UNIVERSITY OF JYVÄSKYLÄ
Structure 2/3
• ConnectionManager
–
–
–
–
Manages active connections and history data
Keeps cache about the forwarded messages
Forwards received messages to the right component
Measures traffic:
• Traffic limit and meter -> Overload
• TopologyManager
– Makes decisions which connections are dropped and where
to establish a new connection
– Handles topology management messages
UNIVERSITY OF JYVÄSKYLÄ
Structure 3/3
• PropagationEngine
– Handles the resource queries and replies
– 4 resource discovery algorithms: BFS, Random
Walk, Highest Degree Search and NeuroSearch
• Connections
– Include local information about node’s neighbors
– Used by topology management algorithms
UNIVERSITY OF JYVÄSKYLÄ
Connections
• Chedar keeps information about active connections
and history data about the earlier connections in XML
trees
• Active connections and history data contains
–
–
–
–
IP address and TCP port
Resource types the node provides
Hit values
Request time
• Hit value is increased every time the node gets a
resource reply from its neighbor
• Relayed hits include the neighbor’s neighbors and the
amount of replies those have relayed to the node
through the neighbor
UNIVERSITY OF JYVÄSKYLÄ
Messages
• Topology management messages
– Connection requests and replies for establishing
connections
– NeighborList requests and replies for quering
neighbor’s neighbors
– ServiceList requests and replies for quering the
resource types neighbor provides
• Resource requests and replies
UNIVERSITY OF JYVÄSKYLÄ
Resource reply ”routing”
• Reply goes back to the iniator of the query
same route as the query came if all nodes are
still available
• If the node where the query came to the node
is not available the reply is tried to sent to the
second next node on the return path
• If the previous node is not available the reply
is sent directly to the iniator of the query
query
Peer 1
Peer 2
Peer 3
Peer 4
reply
UNIVERSITY OF JYVÄSKYLÄ
Topology Management Algorithms 1/4
•
Node Selection
1. Tries to establish the connections which the peer
had before leaving the network
2. History data
1. Connections with hit values and ”old” request time
2. Connections with ”old” request time or unrequested
connections
3. Connections without hit values and request time
4. Connections with hit values
UNIVERSITY OF JYVÄSKYLÄ
Topology Management Algorithms 2/4
• Node Removal
– Selects the ”worst” connection
– Worst connection is a connection which has the
smallest goodness value
– Goodness value: connections hits+its neighbors’
relayed hits
UNIVERSITY OF JYVÄSKYLÄ
Topology Management Algorithms 3/4
• Overload Estimation
– Connections are established and dropped based
on the amount of traffic going through the node
– ConnectionManager measures the traffic in the
given time sequence and if it is more than the
given upper traffic limit one connection is dropped
by using Node Removal
– If the traffic meter is less than the lower traffic
limit, algorithm tries to establish a new connection
by using Node Selection
UNIVERSITY OF JYVÄSKYLÄ
Topology Management Algorithms 4/4
• Overtaking
– Peer moves closer to the ”good” peers by
overtaking the current connection
– If connection has neighbor which relayed hits
proportion of all neighbors’ relayed hits and
connection’s hits is more than the given overtaking
percent a new connection to that neighbor is
established and current connection is dropped
– Peers which provide lots of resources are in the
middle of the network
1
3
Relayed
hits:6 (60%)
4
Relayed
hits:2 (20%)
2
Hits:2
3
1
2
4
UNIVERSITY OF JYVÄSKYLÄ
Future
• Further development of the topology
management algorithms and NeuroSearch
resource discovery algorithm
• Further development of applications using
Chedar
– P2PDisco which is used for speeding up the
training of neural networks with evolutionary
algorithm