Transcript Chedar P2P platform InBCT 3.2 Peer-to

UNIVERSITY OF JYVÄSKYLÄ
Chedar P2P platform
InBCT 3.2 Peer-to-Peer communication
Cheese Factory -project
http://tisu.it.jyu.fi/cheesefactory
Research Assistant
Annemari Auvinen
University of Jyväskylä
Agora Center
[email protected]
UNIVERSITY OF JYVÄSKYLÄ
Generally
• Chedar is a Peer-to-Peer(P2P) platform for
searching resources from the distributed
network
• Resources can be i.e. computing power or
files
• Distributed system without any central points
P2P Applications
Chedar
TCP
Chedar
Chedar
TCP
TCP
IP
Network
2003
TCP
Chedar
TCP
Chedar
Chedar
TCP
UNIVERSITY OF JYVÄSKYLÄ
Architecture
UNIVERSITY OF JYVÄSKYLÄ
Components 1/3
• ChedarClient
– Control interface of a Chedar
node
– Applications and user interfaces
communicate with Chedar
through the ChedarClient
– Used by P2PStudio, data fusion
and distributed computing
applications
2003
P2PStudio,
Data Fusion,
Distibuted
Computing
ChedarClient
Chedar
UNIVERSITY OF JYVÄSKYLÄ
Components 2/3
• ConnectionManager
– Manages active connections and history data
– 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
– Optimizes the topology locally
2003
UNIVERSITY OF JYVÄSKYLÄ
Components 3/3
• PropagationEngine
– Handles the resource queries and replies
• Connection
– Represents the TCP connection to neighboring
Chedar node
2003
UNIVERSITY OF JYVÄSKYLÄ
Connections
• Chedar keeps a track of active and earlier
connections
• Active connections and history data contains
– Number of the neighbors
– Hit values:
• One is increased every time the node gets reply to resource
query
• Actual hits is increased when node selects to use the
neighbor’s resource
• Verified hits is added when node wants to give feedback to
used resource
– Relayed hits
• Connection measures how many replies their neighbor has
relayed
2003
UNIVERSITY OF JYVÄSKYLÄ
Messages
• Topology management messages
– Connection requests and replies
– NeighborList requests and replies
– ServiceList requests and replies
• Resource requests and replies
2003
UNIVERSITY OF JYVÄSKYLÄ
Resource discovery algorithms
• Breadth-First Search algorithm
– Query is forwarded to all node’s neighbors if there is time-tolive value left
– When resource is found the node sends the reply
• NeuroSearch
– Uses neural network for forwarding decisions
• Other algorithms currently under implementation
– Highest degree search
– Random walker
– Adaptive Breadth-First Search
2003
UNIVERSITY OF JYVÄSKYLÄ
Topology Management Algorithms
UNIVERSITY OF JYVÄSKYLÄ
Overtaking 1/2
• Peer moves closer to the ”good” peers
• Overtaking percent
• If connection has neighbor which relayed hits
proportion of all neighbors relayed hits and
connection’s hits is more than the given
percent a new connection to that neighbor is
established and current connection is dropt
3
1
2
Hits:2
2003
Relayed
hits:6 (60%)
3
1
4
Relayed
hits:2 (20%)
2
4
UNIVERSITY OF JYVÄSKYLÄ
Overtaking 2/2
• Peers which provide lots of good resources
are in the middle of the network
• Power-law network: a few nodes with many
neighbors and a lot of nodes with a few
neighbors -> fault tolerant and efficient
topology for searching
2003
UNIVERSITY OF JYVÄSKYLÄ
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
2003
UNIVERSITY OF JYVÄSKYLÄ
Node Removal
• Selects the ”worst” connection
• Worst connection is a connection which has
the lowest goodness value
• Goodness value: connections hits+its
neighbors relayed hits
2003
UNIVERSITY OF JYVÄSKYLÄ
Overload estimation
• Connections are established and dropped
based on the traffic amount flowing through
the node
• ConnectionManager measures the traffic in
the given time sequence and if it is more than
the given traffic limit one connection is
dropped by using Node Removal
• If the traffic meter is less than the limit,
algorithm tries to establish a new connection
by using Node Selection
1
2003
2
3
1
2
3
UNIVERSITY OF JYVÄSKYLÄ
Resource reply ”routing”
• Reply goes back to sender same route as it
came if all nodes are still available
• If the node where the query came to the node
is not available anymore the reply is tried to
sent to the previous node
• If the previous node is not available the reply
is sent directly to the sender
query
Peer 1
2003
Peer 2
Peer 3
Peer 4
reply
UNIVERSITY OF JYVÄSKYLÄ
Future
• Point-to-Point Protocol to enable two peer-topeer nodes to communicate with each other
• Topology management using a neural
network for making Chedar adaptive in wide
range of peer-to-peer networks
• New search algorithms for studying the
performance of local search algorithms and
the NeuroSearch
2003