|
      
|
|
|
|
Peer-to-peer overlay networks can be divided into two classes based on how they store data: structured and unstructured systems. Structured systems, such as DHTs, mandate a fixed mapping of data items to nodes. This simplifies locating an item to a routing problem and makes the behaviour of such systems easier to bound. However, DHTs only support exact lookups and do not apply potentially useful key-space information in routing. As a result, complex queries, such as range queries and approximate matches, are inefficient. Unstructured systems are more flexible and mandate only that nodes autonomously store item-to-node routing table entries, but their effectiveness has been limited to small networks and is not easily bounded. These systems discard a plethora of valuable locality and clustering information that could be used to achieve improved performance.
This work explores the use of prefix hash tables (PHTs) to preserve key-space locality in well-balanced hash tables and proposes to employ prefix hash tables in both structured and unstructured systems. PHTs could be used to support semantic routing in DHTs, allowing range queries and approximate match lookups. Using prefix hash tables, it is also proposed to develop weighted Bloom filters -- a new probabilistic data structure -- and use them in the routing tables of an unstructured system. It is thought that weighted Bloom filters will improve the lookup performance, besides possibly being useful in other applications. The ongoing goal of the research is to develop scalable, resilient overlay networks that incorporate key-space locality to obtain more intelligent routing.
