Transcript Peer-to-Peer Algorithms

UNIVERSITY OF JYVÄSKYLÄ
Peer-to-Peer Algorithms and
Prototypes in Jyväskylä
Presentation for Workshop on Peer-to-Peer Networking
10.10.2005
Mikko Vapa, research student
[email protected]
Department of Mathematical Information Technology
University of Jyväskylä, Finland
http://tisu.it.jyu.fi/cheesefactory
UNIVERSITY OF JYVÄSKYLÄ
Contents
• Peer-to-Peer Algorithms
– Formalization of Peer-to-Peer Resource Discovery Problem
– Approximation of Optimum for P2P Resource Discovery
Algorithms using k-Steiner Minimum Trees
– NeuroSearch – P2P Resource Discovery Using Evolutionary
Neural Networks
• Peer-to-Peer Prototypes
– Chedar Peer-to-Peer Middleware
– Mobile Chedar
– Peer-to-Peer Studio
– Peer-to-Peer Distributed Computing
– Mobile Peer-to-Peer Encounter Networks
– Gasoline Price Comparison System and BlueCheese
• Development History and Future
UNIVERSITY OF JYVÄSKYLÄ
Peer-to-Peer Algorithms
UNIVERSITY OF JYVÄSKYLÄ
Formalization of P2P
Resource Discovery
Problem
• Currently, only textual definitions
of P2P resource discovery
problem exist: “given a resource
name, find the node or nodes that
manage the resource”
• Textual definitions are poor,
because they do not precisely tell:
– What kind of a graph is used
for finding resources
– What information is locally
available to nodes taking part
in the finding process
 Therefore, the task of
forwarding a resource query is
unclear
Problem 1. Resource Discovery Problem
Graph G, resources R, root node r, number of
resources to discover k and forwarding algorithm 
Tree S containing message paths
Output:
(1) t c  1, t a  1, ES   (Initialization)
Input:
(2) VS  (t a , r , true, false)
(3) S = (VS,ES)
(4) while t  t do
c
a
(5)
(6)
(7)
(8)
(9)
(10)
(11)
(12)
(13)
(14)
(15)
(16)
f  tc
g  (VS , f )
if (VS , f ) = false then do (Forward resource reply)
if g = r then do (Reply arrived to query originator)
else (Reply arrived to intermediate node)
ta = ta + 1
ES  ES  { f , t a }
p = (VS , f )
VS  VS  (t a , p, false, false)
end if
end if
if (VS , f ) then do (Resource was found first time}
(17)
(18)
ta = ta + 1
ES  ES  { f , t a }
p = (VS , f )
(19)
(21)
(22)
VS  VS  (t a , p, false, false)
end if
L f  ( S , f , g )
(23)
(24)
M
(25)
(26)
(27)
for i = 1 to |N| do (Forward resource query)
ta = ta + 1
ES  ES  { f , t a }
(20)
(28)
(29)
(30)
(31)
(32)
(33)
(34)
(35)
(36)
(37)
N  (G, f )
f

, N  ( f , k , L f , M f , N )
if i  R then do (Resource will be found first time)
R=R\i
VS  VS  (t a , N i , true, true)
else (A new resource will not be found}
VS  VS  (t a , N i , true, false)
end if
end for
tc = tc + 1
end while
return S
UNIVERSITY OF JYVÄSKYLÄ
Formalization of P2P Resource
Discovery Problem
• Formalization can be used for:
– Formalization of peer-to-peer resource discovery algorithms
• Breadth-First Search
• Highest Degree Search
– Evaluating the performance of peer-to-peer resource
discovery algorithms
– Pointing out the information available in the P2P resource
discovery problem, but which is not yet utilized by any local
resource discovery algorithm
• Reply path forwarding
• Aggregating information from parallel query paths
• Branching factor
• Branching resources to discover
UNIVERSITY OF JYVÄSKYLÄ
Approximation of Optimum for P2P
Resource Discovery Algorithms using
k-Steiner Minimum Trees
•
If global information about P2P network is available, the optimum for
P2P resource discovery algorithms can be approximated by solving kSteiner Minimum Tree problem (finding the exact optimum would be a
NP-complete problem)
Problem:
Given:
Find:
Rooted k-Steiner Minimum Tree
A connected graph G = (V,E,W), terminal set L  V ,
root vertex r  L and 2  k  | L |
A Steiner tree T for L in G rooted to vertex r and
containing k terminal vertices, such that w(T) = min
{|w(T’)| | T’ is a Steiner tree for k vertices in L}
UNIVERSITY OF JYVÄSKYLÄ
Approximation of Optimum for P2P
Resource Discovery Algorithms using
k-Steiner Minimum Trees
• MST k-Steiner Minimum Tree Algorithm was developed for
finding an approximation solution:
l1
7
3
1
m2
1
1
l3
1
m3
7
l1
l2
6
1
m1
6
1
l1
l2
6
5
3
1
5
Time Complexity:
5
5
l3
l4
Graph G
5
5
6
l5
1
l3
l4
Graph GL after step (1)
l1
1
1
l3
m2
1
1
m3
l4
Graph H after step (3)
1
m2
l5
l3
3
m1
3
1
l4
1
1
m3
m1
3
1
l4
Tree T after step (4)
l5
1
l3
2

l1
3
m1

O E log E

Worst-Case
Approximation Ratio:
1
Tree TL after step (2)
l1
3
l5
l5
1
m3
3
1
l4
Tree T after step (5)
l5
L
2
UNIVERSITY OF JYVÄSKYLÄ
Query Path of MST k-Steiner
UNIVERSITY OF JYVÄSKYLÄ
Efficiency
MST k-Steiner Minimum Tree algorithm (Steiner) shows that current
local search algorithms for peer-to-peer networks are far from optimal
Efficiency of the Algorithms
Optimal
Steiner
HDS
BFS
1,2
1
Efficiency
•
0,8
0,6
0,4
0,2
0
0,0
20,0
40,0
60,0
% of Resources
80,0
100,0
UNIVERSITY OF JYVÄSKYLÄ
Future Work of MST k-Steiner
• The future work of finding optimum consists of:
– Getting the results published:
Vapa M., Auvinen A., Tawast T., Ivanchenko Y., Vuori J.,
”K-Steiner Minimum Tree Is An Upper Bound for Peer-toPeer Resource Discovery Algorithms”, submitted to IEEE
INFOCOM 2006
– Now we have all the tools available for discovering the
theoretical limit of peer-to-peer technology in terms of total
traffic induced on a telecommunication network in a realworld peer-to-peer network compared to client-server
approach
– Development of distributed k-Steiner minimum tree resource
discovery algorithm using principles of proactive routing
protocols such as Open Shortest Path First
UNIVERSITY OF JYVÄSKYLÄ
NeuroSearch: P2P Resource Discovery
Using Neural Networks
• NeuroSearch resource discovery algorithm uses neural networks
and evolution to adapt its’ behavior to given environment
• Multiple layers enable the algorithm to express non-linear
behavior
• With enough neurons the algorithm can universally approximate
any decision function
UNIVERSITY OF JYVÄSKYLÄ
Performance
HDS is currently the best known local search algorithm for power-law
distributed scenario
Efficiency of the Algorithms
Optimal
Steiner
HDS
NeuroSearch
BFS
1,2
1
Efficiency
•
0,8
0,6
0,4
0,2
0
0,0
20,0
40,0
60,0
% of Resources
80,0
100,0
UNIVERSITY OF JYVÄSKYLÄ
The Swift from Depth-First Search
to Breadth-First Search
•
NeuroSearch is close to HDS in performance, but different in nature
Hops Used by the Algorithms
HDS
NeuroSearch
Steiner
BFS
140
Branching Factor of the Algorithms
120
BFS
Branching Factor
100
Hops
80
60
40
Steiner
NeuroSearch
7
6
5
4
3
2
1
0
0,0
20,0
40,0
60,0
% of Resources
20
0
0,0
20,0
40,0
60,0
% of Re s ource s
80,0
100,0
80,0
100,0
Typical Query Pattern of NeuroSearch
UNIVERSITY OF JYVÄSKYLÄ
UNIVERSITY OF JYVÄSKYLÄ
Future Work of NeuroSearch
• After two months of extensive simulations with 70 workstations,
we have discovered from 23 different inputs 7 critical ones (Bias,
White, PacketsNow, Sent, EnoughReplies,
FromNeighborAmount and RepliesToGet), which need to be
present to have good performance
– Next, we are going to boost these 6 inputs by generalizing
them to give more accurate information for forwarding
• Also, we need to discover:
– What are the scalability factors of NeuroSearch in large
graphs
– The performance in dynamic real-world scenarios where
peers are joining and leaving the network
UNIVERSITY OF JYVÄSKYLÄ
Peer-to-Peer Prototypes
UNIVERSITY OF JYVÄSKYLÄ
Chedar Peer-to-Peer Middleware
• Chedar (CHEap Distributed Architecture) is a P2P middleware
for searching resources from a distributed network
• Resources can be i.e. computing power or files
• Distributed system without any central points
• Contains different resource discovery and topology management
algorithms
• Implemented with Java 2 Standard Edition
P2P Applications
Chedar
TCP
Chedar
Chedar
TCP
TCP
IP
Network
TCP
Chedar
TCP
Chedar
Chedar
TCP
UNIVERSITY OF JYVÄSKYLÄ
Mobile Chedar
• Mobile Chedar is an
extension of Chedar
to mobile devices
• Bluetooth Java 2 Micro
Edition implementation
ready for Symbian
Series 60
• WLAN & Bluetooth
Python implementation
for Nokia 770 Linux
Internet Tablet planned
for autumn 2005
UNIVERSITY OF JYVÄSKYLÄ
Peer-to-Peer Studio
• P2PStudio is used for measuring the performance, visualizing
network topology and controlling of Chedar peer-to-peer network
in an automated and centralized manner
• Implemented with Java 2 Standard Edition
Peer-to-Peer Studio
User
Interface
Server
Chedar
node
Chedar
node
Chedar
node
Chedar
node
UNIVERSITY OF JYVÄSKYLÄ
Peer-to-Peer Distributed Computing
• Peer-to-Peer Distributed Computing (P2PDisCo) distributes
computations to idling workstations
• Implemented on top of Chedar and deployed in Agora building
• The node that offers computation time has to implement
Distributed interface to be able to receive start, stop and is
application running signals
• Reading of parameters and writing of results are done for the
stream offered by P2PDisCo
 Any Java program reading input from files and writing output
to files can be distributed
Master
queryResource
sendData
Application
Distributed
receivedData
startApplication
stopApplication
applicationRunning
readFile
writeFile
P2PDisCo
receivedData
Chedar
queryResource
resourceReply
sendData
registerResource
sendData
Chedar
UNIVERSITY OF JYVÄSKYLÄ
Mobile P2P
Encounter Networks
•
•
Information distributes over mobile device encounters
(Mobile P2P is a future distribution model)
– no centralized server, free communication
bandwidth, no infrastructure
Applications
– information distribution
– e.g. cheapest bulk product search (gasoline)
1. gasoline payment with mobile device
2. mobile devices communicate with each
other (e.g. Bluetooth)
3. everybody tells what he/she has paid for
the gasoline and gets in exchange prices
of other gas stations
4. based on this information, mobile device
can recommend the cheapest place to fill
the tank
– boosts the market based economy by giving
equal information over the market situation to all
participants
– grocery store price service, dating service, joke
service, event service, newspaper service…
UNIVERSITY OF JYVÄSKYLÄ
Gasoline Price Comparison System
• Test application for verifying the feasibility of mobile peer-to-peer
encounter networks using Bluetooth
• Uses BlueCheese mobile peer-to-peer middleware implemented
by the MoPeDi student software project during autumn 2003
• Implemented with C++ for Symbian Series 60 mobile devices
GPCS User Interface
UNIVERSITY OF JYVÄSKYLÄ
BlueCheese Protocol Stack
Software
UNIVERSITY OF JYVÄSKYLÄ
Development
History and Future
Chedar
Publications
2002
Data Fusion
P2PStudio
• Research work proceeds Topology Management
NeuroSearch
as breakthroughs
P2PRealm (100x)
– P2PRealm network
simulator speeded
Distributed Data Fusion
up the project 100x
BlueCheese
– P2PDisCo is
speeding up the
NS-2 Simulator
project another 100x
MST k-Steiner
when fully deployed
P2PDisCo (100x)
• In 2006, the publications
Mobile Chedar
side will strengthen
NeuroTopology
significantly: currently 9
Gasoline Price
manuscripts are under
Comparison System
peer review
Formalization of P2P
Resource Discovery
----------2003
----------2004
-----------
MP2P Co-operative Learning
NeuroSearch
Mobile Chedar
P2PDisCo
2005