DHT has 2 disadvantages: no control over where data is stored and no guarantee that routing paths remain within an administrative domain.
Skipnet provide controlled data placement and guaranteed routing locality. It maintain 2 address spaces: a string name ID space, a numeric ID space. Nodes organized similar to skip list. A skip list is a linked list some nodes are supplementaed with pointers that skip over many list lements. Each node linked at higher level with probability 1/2.
Skipnet take the notion of maintaining a sorted list of data records as well as pointers that skip over varying numbers of records. It forms a ring. Each node in the ring has routing table, store 2logN entries. (2 level 0 neighbour, 2 level 1 nighbor, 2...level logN (height) neighbor). Each ring at level h is split into 2 rings at level h+1 by having nodes randomly choose which ring belongs to. Similar to Chord ring.
Routing can be done by name id and numeric id. name id routing: every time rout to highest level pointer btw source and destination. terminate at node closest to destination. (keep locality) numeric id routing: everytime rout to higher level with one more prefix close to destination.
node join and departure: join: find the top level ring corressponds to the new comers's numeric id. (rout a message to the newcomer's numeric id), then find neighobrs in this top lievel ring. useing search by name id. start from one nieghobr the newcommer search for its name id at the next lower level and finds neighbours at this lower level.
Content and routing path locality: incorporate a node's name id into a content name graranteees that the content will be hosted on that node. e.g: store 'doc-name' to john.microsoft.com, nameing it joh.sicorsoft.com/doc-mane. (reverse DNS, come.micorsoft.john)
Constrained load balance(CLB): divide a data object's name into 2 parts: CLB domain (specifies the set of nodes over which DHT load balancing should be proformed) and CLB suffix ( used as input to the DHTs' hash function). use '!' . e.g. msn.com/datacenter!topStories.html. To search for a data obj, first search CLB domain using search by name id. then perform search by numeric id within the CLB domain for the hash of the CLB suffic.
