Skipnet
From P2P Wiki
Contents |
Overview
Skpnet is a Scalable Overlay Network with Practical Locality Properties. Other overlays such as Chord, CAN, Tapestry, Pastry present the following disadvantages:
- No locality properties.
- Content locality:
- Constraining data placement.
- Path locality:
- Locality of the routing path between two overlay nodes in a domain does not leave the domain.
SkipNet is designed to provide the above two features.
Motivation
Why bother about content locality & path locality?
Hashing distributes data uniformly across the overlay, so closely related data is not necessarily located in contiguous nodes. The main idea is creating group related data in contiguous nodes to break the load balanced distribution of keys to nodes. As routing tables depend on the uniform distribution of ids to stablish connections, 2 ids are used, a numID, which is uniform in the identifier space, in opposition to the nameID which is chosen in relation to the data.
So we have two ID-space:
- Name ID
- Numeric ID (similar to Chord,Pastry etc).
Data Structure
We call it Skip List, it has the following properties:
- In-memory dictionary data structure.
- Sorted linked list.
- Each node holds a data record, with a subset of nodes having additional links to skip over data records.
Perfect skip list:
- Every (2^i)th node has a pointer to 2^i nodes ahead of it.
- Search: O (log N), N – number of nodes in the list.
- Insertion/deletion: expensive.
Probabilistic skip list:
- Each node chooses a height h such that the prob. of choosing height h is 1/2^h.
- Search, Insert, Delete: O (log N).
Problems with SkipList:
- Efficient search only possible from head.
- Some nodes more likely to be in routing path.
Skipnet's routing table
- A probalistic skiplist where every node is a head.
- The keys are just the names of the nodes.
- The ordering is lexicographic.
Routing example
Graphic example: Routing from A to V. The simple rule is forwarding to the node which is closer to destination.
We are pretending to route a message from node A (with identifier 000) to node V (identifier 101).
After routing to node T, we can go to any of the destinations allowed by T's routing table.
As we can see in the previous picture, we have direct access to V from T at level 0, so we are done.
Conclusions
- Data locality is a very interesting feature for achieving range queries over the overlay.
- Distributed indexes and data location can really benefit from skipnet overlay structure.
- Retrieval of related data does not imply contacting far away nodes.
- But: contiguous data could be in contiguous nodes in different countries (USA node – China Node – Australia node).
