Development of distributed algorithms for data search and content distribution in structured peer-to-peer network
Jordi Pujol Ahulló · TDR (Tesis Doctorales en Red) · 2010
Peer-to-peer (P2P) networks are broadly classified into two main categories: unstructured and structured. Unstructured P2P networks (UPNs) were the first kind to appear and allow a great flexibility on user dynamicty, namely churn, whereas the data search is flooded. This search mechanism is inefficient and motivated the introduction of the structured P2P networks (SPNs). This new category organizes nodes in a proper way that guarantees a great lookup time efficiency and ensures that, if the piece of data exists, it is found. The most relevant implementation of the structured peer-to-peer networks (SPNs) is constituted by distributed hash tables (DHTs). This implementation provides the same functionality than a traditional hash table, where buckets consist actually of the interconnected nodes. DHTs are mainly characterized by providing the pair of functions put(key, value) and value ← get(key). Above all, P2P networks are very attractive because they provide very interesting properties, like descentralization, by the use of computing resources at the edges of Internet; and system scalability by service distribution. At a first glance this functionality could seem sufficient for a wide range of applications, but actually end-user applications require of enhanced services, such as high-level queries (e.g., range queries or top-K queries), as well as content distribution services (e.g., publish/subscribe or application level multicast (ALM)). Since the very beginning of SPNs, this kind of networks has been very permeable and has been receiving an enormous effort to improve SPNs by introducing all these services. Nevertheless, a common factor among all those approaches is that they characterise a specific solution for a particular targeted system. The lack of genericity in these solutions make them probably efficient but non portable to other systems, and so the services constructed over them. We do believe, instead, that a SPN-generic solution is feasible. Another common factor is that SPNs use a number-based uni-dimensional keyspace to identify both nodes and data pieces, whilst the data domain of end-user applications can be of any kind, most of the times multi-dimensional (e.g., list of keywords for Information Retrieval or the pair latitude and longitude in location-based