Many competing designs for Distributed Hash Tables exist exploring multiple models of addressing, routing and network maintenance. Designing a general theoretical model and implementation of a Distributed Hash Table allows exploration of the possible properties of Distributed Hash Tables. We will propose a generalized model of DHT behavior, centered on utilizing Delaunay triangulation in a given metric space to maintain the networks topology. We will show that utilizing this model we can produce network topologies that approximate existing DHT methods and provide a starting point for further exploration. We will use our generalized model of DHT construction to design and implement more efficient Distributed Hash Table protocols, and discuss the qualities of potential successors to existing DHT technologies.

Lookup tables are frequently used in many applications to store and retrieve keyvalue pairs. Designing efficient lookup tables can be challenging with constraints placed on storage, query response time and/or result accuracy. This thesis proposes Geometric filter, a lookup table with a space requirement close to the theoretical lower bound, efficient construction, fast querying speed, and guaranteed accuracy. Geometric filter consists of a sequence of hash tables, the sizes of which form a descending geometric series. Compared with its predecessor, Bloomier filter, its encoding runs two times faster, uses less memory, and it allows updates after encoding. We analyze the efficiency of the proposed lookup table in terms of its storage requirement and error bound, and run experiments on Web 1TB 5-gram dataset to evaluate its effectiveness.

No description available.

<p>Nuvarande implementationer av distribuerade hashtabeller (DHT) har en begränsad storlek för data som kan lagras, som t.ex. OpenDHTs datastorleks gräns på 1kByte. Är det möjligt att lagra filer större än 1kByte med DHT-tekniken? Finns det någon lösning för att skydda de data som lagrats utan att försämra prestandan? Vår lösning var att utveckla en klient- och servermjukvara. Mjukvaran använder sig av DHT tekniken för att dela upp filer och distribuera delarna över ett serverkluster. För att se om mjukvaran fungerade som tänkt, gjorde vi ett test utifrån de inledande frågorna. Testet visade att det är möjligt att lagra filer större än 1kByte, säkert med DHT tekniken utan att förlora för mycket prestanda.</p> / <p>Currently existing distributed hash table (DHT) implementations use a small storage size for data, such as OpenDHT’s storage size limitation of 1kByte. Is it possible to store larger files than 1kByte using the DHT technique? Is there a way to protect the data without losing to much performance? Our solution was to develop a client and server software. This software uses the DHT technique to split files and distribute their parts across a cluster of servers. To see if the software worked as intended we created a test based on our opening questions. This test shows that it indeed is possible to store large files securely using the DHT technique without losing any significant performance.</p>

A distributed hash table (DHT) is a type of peer-to-peer (P2P) network that, like traditional hash tables, maps keys to values. Unlike traditional hash tables, however, the data is distributed across a network with each node being responsible for a particular range of keys. Numerous other DHTs have been presented and have become the cornerstone of wildly popular P2P file-sharing applications, such as BitTorrent. Each of these DHTs trades-off the number of pointers maintained per node with the overhead and lookup time; storing more pointers decreases the lookup time at the expense of increased overhead. A Grouped Hamming Network (GHN), the overlay network presented in this thesis, allows for the number of pointers per node to be any increasing function of n, P(n) = Ω(log n). The system presented assumes that nodes fail independently and uniformly at random with some probability q = 1 − p. Three different schemes for routing in a GHN are presented. For each routing scheme a theoretical estimate on the probability of failure is given and optimal configurations in terms of n and P(n) are given. Simulations of GHNs with various configurations indicate that the given estimates are indeed accurate for reasonable values of q and that the optimal configurations are accurate.

A Peer-to-Peer system is a distributed system whose component nodes participate in similar roles. Every user node (the peer) can exchange and contribute its resources to another one in the system. Similar to the case that peers may dynamically join and leave the system, the data will also be inserted into and removed from the system dynamically. Given a certain range, a range query will find any data item whose value within the range. For example, a range query can find all the Beatle's works between 1961 and 1968 for us. However, once the range data is distributed over a P2P system through the hash function which has been used largely in many P2P systems, the continuity of the range data is not guaranteed to exist. Therefore, finding the scattered data whose value within a certain range costs much in a P2P system. The Distributed Segment Tree method (DST) preserves the local continuity of the range data at each node by using a segment tree and can break any given range into minimum number of node intervals whose union constitutes the whole requested range. The DST method works based on the Distributed Hash Table (DHT) logic; therefore, it can be applied in any DHT-based P2P system. However, data distribution of the DST method may cause overlapping. When searching a data range, the DST method sends more number of requests than what is really needed. Although the DST method designs the Downward Load Stripping Mechanism, the load on peers still may not be balanced. The main reason of these problems is that the DST method applies the DHT logic to the P2P systems. Therefore, in this thesis, we propose a method called Structured Segment Tree (SST) that does not use the DHT logic but embeds the structure of the segment tree into the P2P systems. In fact, the P2P network topology of an SST is the structure of a segment tree. Unlike a DST, an SST can fully reflect the properties of the original segment tree. Each peer in our proposed P2P system represents a node of a segment tree. Data intervals at the same level are continuous and will not overlap with each other. The union of data intervals at a level with full nodes is totally the whole data range which the P2P system can support. When searching a data range, the SST method sends as many number of requests as needed. In addition, we add sibling links to preserve the spatial locality and speed up the search efficiency. For the issue of load balance, our SST method also performs better than the DST method. From our simulation, we show that the SST method routes less number of peers to locate the requested range data than the DST method. We also show that the load based on our method is more balanced than that based on the DST method.

A distributed hash table (DHT) is a type of peer-to-peer (P2P) network that, like traditional hash tables, maps keys to values. Unlike traditional hash tables, however, the data is distributed across a network with each node being responsible for a particular range of keys. Numerous other DHTs have been presented and have become the cornerstone of wildly popular P2P file-sharing applications, such as BitTorrent. Each of these DHTs trades-off the number of pointers maintained per node with the overhead and lookup time; storing more pointers decreases the lookup time at the expense of increased overhead. A Grouped Hamming Network (GHN), the overlay network presented in this thesis, allows for the number of pointers per node to be any increasing function of n, P(n) = Ω(log n). The system presented assumes that nodes fail independently and uniformly at random with some probability q = 1 − p. Three different schemes for routing in a GHN are presented. For each routing scheme a theoretical estimate on the probability of failure is given and optimal configurations in terms of n and P(n) are given. Simulations of GHNs with various configurations indicate that the given estimates are indeed accurate for reasonable values of q and that the optimal configurations are accurate.

Nuvarande implementationer av distribuerade hashtabeller (DHT) har en begränsad storlek för data som kan lagras, som t.ex. OpenDHTs datastorleks gräns på 1kByte. Är det möjligt att lagra filer större än 1kByte med DHT-tekniken? Finns det någon lösning för att skydda de data som lagrats utan att försämra prestandan? Vår lösning var att utveckla en klient- och servermjukvara. Mjukvaran använder sig av DHT tekniken för att dela upp filer och distribuera delarna över ett serverkluster. För att se om mjukvaran fungerade som tänkt, gjorde vi ett test utifrån de inledande frågorna. Testet visade att det är möjligt att lagra filer större än 1kByte, säkert med DHT tekniken utan att förlora för mycket prestanda. / Currently existing distributed hash table (DHT) implementations use a small storage size for data, such as OpenDHT’s storage size limitation of 1kByte. Is it possible to store larger files than 1kByte using the DHT technique? Is there a way to protect the data without losing to much performance? Our solution was to develop a client and server software. This software uses the DHT technique to split files and distribute their parts across a cluster of servers. To see if the software worked as intended we created a test based on our opening questions. This test shows that it indeed is possible to store large files securely using the DHT technique without losing any significant performance.

[pt] Este trabalho surgiu da seguinte observação: os clássicos algoritmos de busca em 2d-tree começam da raiz para acessar dados armazenados nas folhas. Entretanto, como as folhas são os nós mais distantes da raiz, por que começar as buscas pela raiz? Com representações clássicas de 2d-trees, não existe outra forma de acessar uma folha. Existem 2d- trees, porém, que permitem acessar em tempo constante qualquer nó, dado sua posição e seu nível. Para o algoritmo de busca, a posição é conhecida, mas o nível não. Para estimar o nível de um nó qualquer, um método de otimização estatística do custo médio das buscas é proposto. Como os piores custos de busca são obtidos quando se começa da raiz, este método melhora ambos: o consumo de memória pelo uso de 2d-trees que permitem acessar em tempo constante qualquer nó, e o tempo de execução através da otimização proposta. / [en] This work emerged from the following observation: usual search procedures for 2d-trees start from the root to retrieve the data stored at the leaves. But since the leaves are the farthest nodes to the root, why start from the root? With usual 2d-trees representations, there is no other way to access a leaf. However, there exist 2d-trees which allow accessing any node in constant time, given its position in space and its depth in the 2d-tree. Search procedures take the position as an input, but the depth remains unknown. To estimate the depth of an arbitrary node a statistical optimization of the average cost for the search procedures is introduced. Since the highest costs of these algorithms are obtained when starting from the root, this method improves on both, the memory footprint by the use of 2d-trees which allow accessing any node in constant time, and execution time through the proposed optimization.

Cette thèse propose une nouvelle architecture Peer-to-Peer pour l’établissement de sessions SIP (Session Initiation Protocol) sur les réseaux ad hoc. SIP est un protocole con¸cu à l’origine sur un modèle centralisé est n’est pas nativement adapté aux réseaux mobiles ad hoc (MANET) en raison de leurs caractéristiques inhérentes de mobilité. Nous avons ciblé nos études sur un mécanisme de lookup distribué Peer-to-Peer (P2P) tolérant aux fautes, même en cas de mobilité des noeuds du réseau. Cette thèse s’articule autour de quatre principales contributions: Nous introduisons le concept de Structured Mesh Overlay Network (SMON) : un overlay P2P sur MANET permettant d’effectuer des lookups de ressources rapides dans un environnement ad hoc. SMON utilise une architecture cross layer design basée sur une Distributed Hash Table (DHT) utilisant directement les informations de routage OLSR. Cette architecture cross layer permet d’optimiser les performances du réseau overlay lors d’un changement de topologie du réseau. La seconde contribution, SIPMON, est un overlay SIP sur réseau SMON. Sa particularité est d’utiliser un DHT pour distribuer les identifiants d’objet SIP dans le réseau overlay SMON. Les expérimentations menées prouvent que cette approche garantit une durée de découverte SIP constante et permet un établissement de session plus rapide entre deux usagers sur réseau ad hoc. SIPMON ne s’applique cependant qu’à un réseau MANET isolé. Notre troisième contribution SIPMON+ permet un interfonctionnement de plusieurs overlays SIPMON connectés à Internet. SIPMON+ unifie donc les overlays de réseau et permet de joindre un client SIP qu’il soit localisé sur un réseau ad hoc ou sur l’internet. De plus, SIPMON+ permet une continuité de service sans couture lors du passage entre un réseau MANET et un réseau d’infrastructure. Notre prototype a démontré que les performances de temps d’établissement d’appel SIPMON+ étaient meilleures que pour l’approche concurrente MANEMO (MANET for Network Mobility). Le scénario d’usage principal est la fourniture de services de communication multimédia d’urgence rapidement déployables en cas de catastrophe majeure. Nous avons développé un prototype SIPMON+ totalement fonctionnel de service de communication P2P multimédia. Ce prototype a été expérimenté en situation réelle de catastrophe. Notre prototype sans infrastructure a donné de biens meilleurs résultats que MANEMO en termes de temps de déploiement, de taux de perte de paquets et de temps d’établissement d’appel. / This work presents a novel Peer to Peer (P2P) framework for Session Initiation Protocol (SIP) on Mobile Ad Hoc Network (MANET). SIP is a client-server model of computing which can introduce a single point of failure problem. P2P SIP addresses this problem by using a distributed implementation based on a P2P paradigm. However, both the traditional SIP and P2P SIP architectures are not suitable for MANETs because they are initially designed for infrastructured networks whose most nodes are static. We focus on distributed P2P resource lookup mechanisms for SIP which can tolerate failures resulting from the node mobility. Our target application is SIP-based multimedia communication in a rapidly deployable disaster emergency network. To achieve our goal, we provide four contributions as follows. The first contribution is a novel P2P lookup architecture based on a concept of P2P overlay network called a Structured Mesh Overlay Network (SMON). This overlay network enables P2P applications to perform fast resource lookups in the MANET environment. SMON utilizes a cross layer design based on the Distributed Hashing Table (DHT) and has direct access to OLSR routing information. Its cross layer design allows optimizing the overlay network performance during the change of network topology. The second contribution is a distributed SIP architecture on MANET providing SIP user location discovery in a P2P manner which tolerates single-point and multiple-point of failures. Our approach extends the traditional SIP user location discovery by utilizing DHT in SMON to distribute SIP object identifiers over SMON. It offers a constant time on SIP user discovery which results in a fast call setup time between two MANET users. From simulation and experiment results, we find that SIPMON provides the lowest call setup delay when compared to the existing broadcast-based approaches. The third contribution is an extended SIPMON supporting several participating MANETs connected to Internet. This extension (SIPMON+) provides seamless mobility support allowing a SIP user to roam from an ad hoc network to an infrastructured network such as Internet without interrupting an ongoing session. We propose a novel OLSR Overlay Network (OON), a single overlay network containing MANET nodes and some nodes on the Internet. These nodes can communicate using the same OLSR routing protocol. Therefore, SIPMON can be automatically extended without modifying SIPMON internal operations. Through our test-bed experiments, we prove that SIPMON+ has better performance in terms of call setup delay and handoff delay than MANET for Network Mobility (MANEMO). The fourth contribution is a proof-of-concept and a prototype of P2P multimedia communication based on SIPMON+ for post disaster recovery missions. We evaluate our prototype and MANEMO-based approaches through experimentation in real disaster situations (Vehicle to Infrastructure scenarios). We found that our prototype outperforms MANEMO-based approaches in terms of call setup delay, packet loss, and deployment time.