Decentralized Location Services
Download
Report
Transcript Decentralized Location Services
Ongoing Work on Peer-toPeer Networks
April 9, 2016
Prof. Ben Y. Zhao
[email protected]
Large-scale Network Applications
Context
trend: applications increasing in scale (clients, distribution)
examples: wide-area real-time multicast (PayPerView), data
dissemination (PointCast), large distributed FS
mutual sharing of data, inter-node communication
Challenges as networks scale
how does A find a particular piece of data?
start with simple name (complex queries later)
how does node A send message to B?
IP addresses are too static, need app-level location independent names
how do we make communication reliable?
Ongoing work in P2P Networks
[email protected]
2
Adding Name-based Structure to Networks
No network structure
any node can connect to any node: flexible
scalability issue: too many routing table entries
need more flexible naming, IP address too static
Trade off flexibility for scalability
name all nodes with application level nodeIDs
route incrementally to destination
use nodeID as measure of routing progress
Ongoing work in P2P Networks
[email protected]
3
Outline
Motivation
Protocols
routing: Chord, Tapestry/Pastry, etc…
dynamic algorithms
Application Interfaces
Ongoing Work
Wrap-up
Ongoing work in P2P Networks
[email protected]
4
Structured Peer-to-Peer Overlays
Assign random nodeIDs and keys from secure hash
incrementally route towards destination ID
each node has small set of outgoing routes, e.g. prefix routing
ID: ABCE
ABC0
To: ABCD
AB5F
A930
Ongoing work in P2P Networks
[email protected]
5
What’s in a Protocol?
Definition of name-proximity
Size of routing table
worst case routing performance (in overlay hops, not IP)
Network locality
amount of state kept by each node as f (N), N = network size
# of overlay routing hops
each hop gets you “closer” to destination ID
prefix routing, numerical closeness, hamming distance
does choice of neighbor consider network distance
impact on “actual” performance of P2P routing
Application Interface
Ongoing work in P2P Networks
[email protected]
6
Chord
NodeIDs are numbers on ring
Closeness defined by numerical
proximity
Finger table
keep routes for next node
namespace
routing table size: log2 n
n = total # of nodes
0
2i
away in
iterative hops from source
at most log2 n hops
128
896
256
768
Routing
Ongoing work in P2P Networks
Node 0/1024
640
384
512
[email protected]
7
Chord II
Pros
Cons
simplicity
limited flexibility in routing
neighbor choices unrelated to network proximity
* but can be optimized over time
Application Interface:
distributed hash table (DHash)
Ongoing work in P2P Networks
[email protected]
8
Tapestry / Pastry
incremental prefix routing
Node 0/1024
0
routing table
11110XXX00XX
000X0000
128
896
keep nodes matching at least i
digits to destination
256
768
table size: b * logb n
routing
640
recursive routing from source
at most logb n hops
Ongoing work in P2P Networks
[email protected]
384
512
9
Routing in Detail
Example: Octal digits, 212 namespace, 2175 0157
2175
0880
0123
0154
0157
0 1
0 1
0 1
0 1
0 1
2
2
2
2
2
3 4 5
3 4 5
3 4 5
3 4 5
3 4 5
Neighbor 2175
Map
For “2175” (Octal)
6 7
6 7
6 7
6 7
6 7
0xxx
20xx
210x
2170
1xxx 0880
----
211x
2171
----
22xx
212x
2172
3xxx
23xx
213x 0123
2173
4xxx
24xx
214x
2174
5xxx 0154
25xx
215x
----
6xxx
26xx
216x
2176
7xxx
27xx
----
2177
0157
4
3
2
1
Routing Levels
Ongoing work in P2P Networks
[email protected]
10
Tapestry / Pastry II
Pros
Cons
large flexibility in neighbor choice
choose nodes closest in physical distance
can tune routing table size and routing hops using
parameter b
more complex than Chord to implement
Application Interface
Tapestry: decentralized object location
Pastry: distributed hash table
Ongoing work in P2P Networks
[email protected]
11
Lots and Lots of Protocols
Other designs: Kademlia, Coral, etc…
For network locality
SkipNet / Skip graphs
LAND
For theory
Viceroy (dynamic adaptation of butterfly network)
Symphony
Ulysseus
For performance
One-hop / Two-hop Routing (static hierarchy)
Brocade (two layered approach for WAN routing)
XRing / ZRing
Ongoing work in P2P Networks
[email protected]
12
Questions?
Ongoing work in P2P Networks
[email protected]
13
Outline
Motivation
Protocols
Application Interfaces
distributed hash tables
decentralized object location
multi-tiered interfaces
Ongoing Work
Wrap-up
Ongoing work in P2P Networks
[email protected]
14
How Do We Use Them?
Key-based Routing layer
Large sparse ID space N
(160 bits: 0 – 2160 represented as base b)
Nodes in overlay network have nodeIDs N
Given k N, overlay deterministically maps k
to its root node (a live node in the network)
Main routing call
route (key, msg)
Route message to node currently responsible for key
Leveraging KBR
storage: pick a node by name to store data
routing: route messages between nodes by nodeID
Ongoing work in P2P Networks
[email protected]
15
Storage: Distributed Hash Tables
P2P layer = a hash table
write (key, data)
key is object ID
store data at k nodes closest in name to key
k is system parameter (replication factor)
data = read (key)
read data from any of k nodes close to key
Ongoing work in P2P Networks
[email protected]
16
DHT II
Pros
simplicity, just store and forget
rely on storage layer to keep data available across changes
in node membership
servers generally distance in network and faultindependent
Cons
P2P layer controls parameters
where data is stored, how many replicas
one size rarely fits all
lack of network locality
Ongoing work in P2P Networks
[email protected]
17
Storage: Decentralized Object Location
routeobj(k)
routeobj(k)
backbone
k
publish(k)
k
let application choose where to store data
P2P layer provides directory service to locate objects
redirect data traffic using log(n) in-network redirection pointers
[email protected]
average # of pointers/machine:
log(n) * avg files/machine
Ongoing work in
P2P Networks
18
DOLR II
Pros
application has control over data placement
can optimize location, replication factor for
performance
Cons
directory pointers require state in network
additional complexity in managing data
Ongoing work in P2P Networks
[email protected]
19
Outline
Motivation
Protocols
Application Interfaces
Ongoing Work
Wrap-up
Ongoing work in P2P Networks
[email protected]
20
Many Structured P2P Applications
Data storage
Search on P2P
service discovery, P2P databases
Routing
file systems, FS backup, stegnographic FS
Web Caches, CDNs, DNS services
application-level multicast, pub/sub
resilient routing tunnels
Others
spam-filtering, collaborative network measurement,
machine fault diagnosis
Ongoing work in P2P Networks
[email protected]
21
But Few (if any) Are Deployed
Deployment outside of research networks
Consider some factors
still file-sharing based (Kenosis/BitTorrent, E-Donkey)
Why? Is P2P only good for file-sharing?
killer app with real user demand
usability (software engineering)
incentives vs. per user cost
security
How do we do about this?
Ongoing work in P2P Networks
[email protected]
22
Addressing P2P Security
The problem
lots of users, spread over wide-area, multiple network domains
no uniform security policy or management capability
result: expect compromised nodes in normal operation
Existing work
secure routing: trade off efficiency for improved resilience against collusion
prognosis is bleak
one against many (colluding attackers)
An alternative
balance the scale: many against many
form trusted groups to collaboratively stave off attackers
incrementally build trust groups with anonymous verification
Ongoing work in P2P Networks
[email protected]
23
P2P Security cont.
Mechanisms
highly dynamic collaborative reputation system
anonymous communication in P2P
todo
under development: Cashmere
Policies / algorithms
how to perform anonymous verification
how to derive / adapt online reputations
A related topic
what are the weaknesses of current P2P systems
what are the main methods of attack?
how do we perform / protect against these attacks?
Ongoing work in P2P Networks
[email protected]
24
Finding the Right Incentive/Cost Model
Deployment
current focus on infrastructure services
need useful, light-weight apps for home users
Design and implement Quartz
lightweight p2p data sharing system
store your most critical files (<100MB) online
use simple application-specific handlers to provide fast data
synchronization (a la CVS)
synchronize your HTML bookmarks across machines
synchronize your papers, homework files, financial records
end to end encryption
Ongoing work in P2P Networks
[email protected]
25
Other Directions
Understanding unstructured P2P systems
understanding content-based centralization and its
implications
edge-based measurements of Freenet
studies of Maze, an academic P2P system from China
More P2P applications
Reliable and efficient event propagation
(large-scale distributed gaming)
P2P Ebay, (secure online commerce)
Ongoing work in P2P Networks
[email protected]
26
Other Directions cont.
Applying decentralized algorithms elsewhere
routing and data management in sensor and ad-hoc
networks
reduce routing state and flooding traffic
energy efficient data aggregation in sensor nets
spectrum allocation and MAC-layer device coordination
Ongoing work in P2P Networks
[email protected]
27
Outline
Motivation
Protocols
Application Interfaces
Ongoing Work
Wrap-up
Ongoing work in P2P Networks
[email protected]
28
Finally…
Structured Peer-to-Peer Networks are useful (& fun)
holds promise for self-maintaining decentralized networks at Internet
scales
relevance to numerous areas in CS
sensor networks, ad-hoc routing, security, theory
For more information …
see the webpage for my Winter 290
http://www.cs.ucsb.edu/~ravenben/classes/290F
see papers from IPTPS:
http://iptps05.cs.cornell.edu/
http://iptps04.cs.ucsd.edu
http://iptps03.cs.berkeley.edu
Ongoing work in P2P Networks
[email protected]
29