Transcript SkipNet: A Scalable Overlay Network with Practical Locality Properties

SkipNet: A Scalable Overlay Network
with Practical Locality Properties
Nicholas J. A. Harvey, Michael B. Jones, Stefan
Saroiu, Marvin Theimer, and Alec Wolman
Presented by Koji Yatani
Problem
 DHTs cannot control where data is stored.
 It may be far from the users.
 It may be outside the administrative domain to which it
belongs.
SkipNet
 A scalable overlay network integrating two locality
properties
 Content locality
 Path locality
 Content locality
 The ability to explicitly place data on specific nodes or
distribute it across nodes within a given organization
 Path locality
 The ability to guarantee that message traffic between
two nodes within the same organization is routed
within that organization only.
Locality Properties of SkipNet
 Content and routing path locality
 Content locality: Incorporating a node’s name ID into
content name
john.microsoft.com/doc-name
 Routing path locality: Sharing a prefix in the “reversed”
name IDs
 com.microsoft.john
 com.microsoft.alice
 com.microsoft.bob
Locality Properties of SkipNet
 Constrained load balancing (CLB)
 The name of data has two parts.
 The CLB domain: it specifies the set of nodes over
which DHT load balancing should be performed
 The CLB suffix: it is used as input to the DHT’s hash
function
 Example: msn.com/DataCenter!TopStories.html
Experimental Evaluation
 Basic routing costs
 Constrained load balancing
 Network proximity
 Effect of locality of data placement
 Fault tolerance
SkipNet shows significant performance improvements
and great fault tolerance as the locality of data reference
increases.
Discussions
 What is the reason why CLB in SkipNet was not so
great?
 Did it hit the theoretical limit?
 Was there something wrong with the assumptions for
the simulation?
 How could we overcome the problem?
Discussions
 Is there any other good way to evaluate SkipNet (or a
P2P system in general)?
 What kind of evaluations would make our paper
stronger?
 Taxonomy in the paper we looked at last week
 Decentralization
 Architecture
 Lookup Protocol
 System Parameters
 Routing Performance
 Routing State
 Peers Join and Leave
 Security
 Reliability
Discussions
 Is there any other useful guarantee/functionality in
a P2P system?
 Untraceable identities (Winny)
 Clustering
 Detection of fake/virus files
 Anything else?
Discussions
 Could we apply the SkipNet structure to a social
networking system?
 People would belong to many different organizations.
 The “main” organization might be dynamically
changed.
 Day -> “CS grad students at UofT”
 Night -> “Residents in Graduate House”
 Would SkipNet improve the performance of a social
networking system? How?
Discussions
 What kind of guarantees/improvements would we
need for a social network?
 We would not want a message to be routed through an
unfamiliar/outside node.
 We would want to connect a node outside the
organization more effectively.
Discussions
 Could we explore other enhancements on SkipNet
with a social networking?
 A better way to construct and maintain P-table
 CLB with a more flexible subset of the network
 Clustering
 A collaborative uploading/downloading
Thank you.
Any other discussion?
Distributed Hash Table (DHT)
 A nodeID is assigned to each node.
 Data is placed deterministically with an identifier
called key which is determined by a hash function.
 Each peer maintains information on its
neighborhood nodeIDs and IP addresses.
 Queries are forwarded so that it can get closer to the
key in the identifier space.
 Theoretically, a DHT-based system can guarantee
that any date can be located in O(logN) hops.
DHT
 Disadvantage: the system cannot know where the
desired data is.
 It may be far from the users.
 It may be outside the administrative domain to which it
belongs.
Routing over SkipNet
 Analogy to Skip List
 A sorted linked list in which some nodes are
supplemented with pointers that skip over many list
elements
Routing over SkipNet
 Skip List
 A perfect Skip List: The height of a i-th node can be
determined as the exponent of the largest power-oftwo that divides i.
 A probabilistic Skip List: The height of each node can
be chosen with the probability with (½)^h.
The SkipNet Structure
D
M
O
A
T
Z
R-table
V
X
Level
Clockwise
Anti-clockwise
Level
Clockwise
Anti-clockwise
2
T
T
2
D
D
1
M
X
1
Z
O
0
D
Z
0
X
T
The SkipNet Structure
 Numeric ID
 Its first h bits determine ring membership.
M
D
110
010
O
101
A 000
001
100
Z
011
X
111
V
T
The SkipNet Structure
 Routing by Numeric ID
 Node A wants to send a message to node 1011.
M
D
1100
0100
O
1001
A 0000
0001
1000
Z
0101
X
1101
V
T
Locality Properties of SkipNet
 Limitation of CLB in the SkipNet
 It does not support load balancing over an arbitrary
subset of the nodes.
 Only over any naming subtree of the SkipNet
 Transparent remapping to a different load balancing
domain is not possible.
 The CLB domain is encoded in the name of a data object.
SkipNet Enhancement
 Sparse and dense routing table
 Using non-binary digits for the numeric IDs
 Decreasing the total number of pointers in the R-table
 Increasing the routing hops to a specific node
SkipNet Enhancement
 Network proximity
 The problem: A message my be routed through a node
which is located at a distant place.
USA
UK
aaa.com/nodeA
bbb.com/nodeB
ccc.com/nodeC
SkipNet Enhancement
 Network proximity
 The second routing table: P-table
 Inspired by Pastry’s proximity-aware routing tables
Experimental Evaluation
 Relative Delay Penalty (RDP): The ratio of the latency
of the overlay network path between to two nodes to
the latency of the IP-level path between them.
 Basic routing costs
 Constrained load balancing
 Network proximity
 Physical network hops
 Effect of locality of data placement
 Numbers of failed lookups
 Fault tolerance
Experimental Evaluation
 Basic routing costs
 Basic SkipNet and Chord: do not support proximity-
aware rooting
 Full SkipNet and Pastry: do support proximity-aware
rooting
Experimental Evaluation
 Absolute latency for lookups as a function of data
access locality
 SkipNet was not so great here.
 Inter-domain links had the same cost as intra-domain
links.
Experimental Evaluation
 Fault tolerance
 SkipNet showed a great fault tolerance.
Locality Properties of SkipNet
 Constrained load balancing
 SkipNet was not so great again… why?
 Is there any good way to evaluate the performance of
CLB?
Experimental Evaluation
 Network proximity
 Density parameter k: controls the density of P-table
pointers.
 Choosing k=8 provides a good performance with a
reasonable number of pointers.