This dissertation is in the area of pervasive computing. It focuses on designing platforms for storing, querying, and computing contextual information. More specifically, we are interested in platforms for storing and querying spatio-temporal events where queries exhibit locality. Recent advances in sensor technologies have made possible gathering a variety of information on the status of users, the environment machines, etc. Combining this information with computation we are able to extract context, i.e., a filtered high-level description of the situation. In many cases, the information gathered exhibits locality both in space and time, i.e., an event is likely to be consumed in a location close to the location where the event was produced, at a time whic h is close to the time the event was produced. This dissertation builds on this observation to create better platforms for computing context. We claim three key contributions. We have studied the problem of designing and optimizing spatial organizations for exchanging context. Our thesis has original theoretical work on how to create a platform based on cells of a Voronoi diagram for optimizing the energy and bandwidth required for mobiles to exchange contextual information t hat is tied to specific locations in the platform. Additionally, we applied our results to the problem of optimizing a system for surveilling the locations of entities within a given region. We have designed a platform for storing and querying spatio-temporal events exhibiting locality. Our platform is based on a P2P infrastructure of peers organized based on the Voronoi diagram associated with their locations to store events based on their own associated locations. We have developed theoretical results based on spatial point processes for the delay experienced by a typical query in this system. Additionally, we used simulations to study heuristics to improve the performance of our platform. Finally, we came up with protocols for the replicated storage of events in order to increase the fault-tolerance of our platform. Finally, in this thesis we propose a design for a platform, based on RFID tags, to support context-aware computing for indoor spaces. Our platform exploits the structure found in most indoor spaces to encode contextual information in suitably designed RFID tags. The elements of our platform collaborate based on a set of messages we developed to offer context-aware services to the users of the platform. We validated our research with an example hardware design of the RFID tag and a software emulation of the tag's functionality. / text

Η ραγδαία ανάπτυξη του διαδικτύου και των τεχνολογιών που το υποστηρίζουν έχει οδηγήσει στην ραγδαία αύξηση των εφαρμογών διαμοίρασης δεδομένων. Ταυτόχρονα, οι ανάγκες για ταχεία μεταφορά δεδομένων γίνονται ολοένα και μεγαλύτερες. Μία από τις πιο απαιτητικές κατηγορίες εφαρμογών που διανέμουν πληροφορία είναι οι εφαρμογές πολλαπλής αποστολής δεδομένων. Σε αυτές τις εφαρμογές, ένας αποστολέας θέλει να στείλει δεδομένα σε μία ομάδα παραληπτών, οι οποίοι στη γενική περίπτωση είναι γεωγραφικά κατανεμημένοι. Είναι προφανές ότι ο αποστολέας δεν μπορεί να στείλει τα δεδομένα σε όλους τους παραλήπτες ταυτόχρονα, γιατί το έυρος ζώνης που διαθέτει είναι περιορισμένο, ενώ οι παραλήπτες μπορεί να είναι χιλιάδες. Έτσι, υιοθετείται συνήθως η τακτική δημιουργίας ενός δέντρου διανομής, όπου ο αρχικός κόμβος στέλνει σε μερικούς μόνο παραλήπτες, οι οπόιοι προωθούν το μήνυμα στα παιδιά τους κ.ο.κ. Το δέντρο διανομής συνήθως κατασκευάζεται πάνω από ένα δομημένο δίκτυο ομοτίμων (p2p networks) και πιο συγκεκριμένα πάνω από ένα δίκτυο βασισμένο σε Κατανεμημένους Πίνακες Κατακερματισμού (Distributed Hash Tables - DHT). Αυτή η τεχνική, αν και λύνει το πρόβλημα της πολλαπλής αποστολής, αντιμετωπίζει όμως κάποια προβλήματα. Πιο συγκεκριμένα, το δέντρο διανομής είναι στατικό, δηλαδή δεν μπορεί να μεταβληθούν οι συνδέσεις μεταξύ των κόμβων αν αλλάξουν οι συνθήκες του υφιστάμενου δικτύου. Ακόμα, δεν υπάρχει κάποιος έλεγχος για τις δυνατότητες των κόμβων που βρίσκονται στα υψηλότερα επίπεδα του δέντρου. Αυτό έχει σαν αποτέλεσμα το δέντρο να χάνει μεγάλο μέρος από την αποδοτικότητά του. Στα πλαίσια της εργασίας αυτής, μελετάμε τη δημιουργία ενός δυναμικού δέντρου διανομής, το οποίο μπορεί να αναπροσαρμόζεται στις εκάστοτε συνθήκες, αυξάνοντας έτσι σημαντικά τη συνολική αποδοτικότητα. Πιο συγκεκριμένα, η βασική μετρική είναι το εύρος ζώνης που παρατηρούν οι χρήστες κατα τη διάρκεια μιας αποστολής δεδομένων. Παρουσιάζουμε διάφορα στατιστικά στοιχεία που δείχνουν τη δραστική βελτίωση που επιτυγχάνουμε με τη χρήση του συγκεκριμένου αλγορίθμου. Ακόμα, μελετάμε τη δημιουργία ενός δέντρου διανομής που θα εκμεταλλεύεται τη δομή των DHT δίκτύων και θα μπορεί να διανέμει την πληροφορία αξιόπιστα (με χρήση erasure coding τεχνικών) ενώ θα εγγυάται ένα λογαριθμικό μέσο αριθμό βημάτων για την αποστολή των δεδομένων. Ταυτόχρονα, το σύστημα προσπαθεί να ισοκατανείμει το φόρτο προώθησης των μηνυμάτων σε όλους τους κόμβους του δικτύου. Και τα δύο συστήματα έχουν υλοποιηθέι και αξιολογηθεί χρησιμοποιώντας το DHT σύστημα Pastry και την υλοποίησή του σε Java (FreePastry). / The rapid evolution of the Internet and network technologies has led to an equally rapid increase in data dissemination applications. At the same time, the need for quick data transfer increase daily. One of the most demanding categories of information disseminating applications are file sharing applications. In these applications, one transmitter wants to send data to a group of receivers, that are geographically distributed. It is obvious that the transmitter can not send the data to all receivers simultaneously, because his bandwidth is limited , while the receivers may be hundreds or even thousands. Therefore, the most common method is that of the creation of a dissemination tree, where the initial node forwards the information to some recipients and they forward it to their children, etc. The dissemination tree is usually constructed over a peer-to-peer network, and specifically over a Distributed Hash Table (DHT) network. This method, although solves the problem of multicasting, faces some problems. First, the dissemination tree is static, which means that the connections between the nodes can not be rearranged, if the conditions of the underlying network change. Moreover, there is no control over the efficiency of the nodes in the highest levels of the tree. This leads to a significant drop in tree efficiency. In this thesis, we study the creation of a dynamic dissemination tree, which can adapt to the network conditions, thereby increasing the tree performance. Specifically, the basic evaluation metric is the bandwidth that end users perceive. We present evidence that shows the improvement that our algorithm imposes. We also study the creation of a dissemination tree that uses the existing DHT structure to efficiently and reliably (using erasure coding techniques) disseminate information and guarantees a logarithmic number of hops for message delivery. At the same time, the system tries to balance the load among all network nodes. Both systems were implemented and evaluated using the Pastry system and its implementation in Java (FreePastry).

Objetivos generales: - Investigar los aspectos vinculados a la obtención de servicios de streaming, el modelado de redes de datos y la caracterización del tráfico allí cursado. - Determinar un mecanismo que permita establecer un orden entre los nodos que brindan un determinado servicio o recurso deseado en una red "best effort" como es Internet Objetivos específicos: - Armar una taxonomía de los servicios que se pueden brindar en redes IP. - Analizar diferentes formas de modelizar redes de datos, de manera tal que resulte lo más fiel posible a la realidad de una red como Internet, en cuanto a topología, velocidad de enlaces, agregación y caracterización del tráfico, congestión, etc. - Diagramar y ejecutar simulaciones, en un modelo de red, que permitan cuantificar parámetros de comunicación (bandwidth, delay, jitter, packet loss) en diferentes tipos de servicios que se pueden brindar en dicha red. - Establecer un criterio que permita ordenar los nodos que ofrecen el servicio deseado considerando los resultados de las simulaciones abordadas.

Recommender systems are widely used to achieve a constantly growing variety of services. Alongside with social networks, recommender systems that take into account friendship or trust between users have emerged. In this thesis, we propose an evolution of trust-based recommender systems adapted to decentralized architectures that can be deployed on top of existing social networks. Users profiles are stored locally and are exchanged with a limited, user-defined, list of trusted users. Our approach takes into account friends' similarity and propagates recommendation to direct friends in the social network in order to prevent ratings from being globally known. Moreover, the computational complexity is reduced since calculations are performed on a limited dataset, restricted to the user's neighborhood. On top of this propagation, our approach investigates several aspects. Our system computes and returns to the final user a confidence on the recommendation. It allows the user to tune his/her choice from the recommended products. Confidence takes into account friends' recommendations variance, their number, similarity and freshness of the recommendations. We also propose several heuristics that take into account peer-to-peer constraints, especially regarding network flooding. We show that those heuristics decrease network resources consumption without sacrificing accuracy and coverage. We propose default scoring strategies that are compatible with our constraints. We have implemented and compared our approach with existing ones, using multiple datasets, such as Epinions and Flixster. We show that local information with default scoring strategies are sufficient to cover more users than classical collaborative filtering and trust-based recommender systems. Regarding accuracy, our approach performs better than others, especially for cold start users, even if using less information.

Le routage par clé et par contenu sont des systèmes de routage ou la destination d'un message suit un parcours entre les nœuds du réseau qui dépend seulement du contenu du message même. On peut les trouver utilisés soit dans des systèmes pair-à-pair connus comme Réseaux Overlay Structurés (Structured Overlay Networks, SON), soit dans les architecture internet de nouvelle génération, les Réseaux Centrés sur les Contenus (Content-Centric Networks, CCN). Le but de cette thèse est double. D'un côté, on explore le sujet de l'interconnexion et de la coopération des réseaux d'overlay, et on propose une architecture capable de permettre à plusieurs réseaux d'overlay hétérogènes, avec différentes topologies et différents mécanismes de routage, d'interagir, grâce à une infrastructure basée sur des nœuds passerelles. On montre, par des moyennes de simulation et déploiement dans un réseaux réel, que la solution est scalable et permet un routage quasi-exhaustif avec un nombre relativement bas des nœuds passerelle bien connectés. De plus, on présente deux exemples d'applications qui pourront bénéficier de cette architecture. Dans une deuxième partie, on rentre plutôt dans les possibilités offertes par le routage basé sur les contenus hors sa "zone de confort": d'abord, on analyse les améliorations qu'un réseau d'overlay structuré peut porter à un système de diffusion vidéo pair-à-pair, en termes de qualité du vidéo et de perte des paquets pendant la transmission. Après, on examine un système entièrement centré sur le routage basé sur les contenus, en développant une solution de diffusion vidéo en temps réel dans un réseau CCN.

There is no doubt that BitTorrent nowadays is one of the most popular peer-to-peer (P2P) applications on the Internet, contributing to a significant portion of the total Internet traffic and being a basis for many other emerging services such as P2P Internet Protocol Television and Video on Demand. On the other hand, Network Address Translation (NAT) devices have become pervasive in almost all networking scenarios. Despite of the effort of NAT traversal, it is still very likely that applications, especially P2P ones, cannot receive incoming connection requests properly if they are behind NAT. Although this phenomenon has been widely observed in measurement work, so far there is no quantitative study in the literature examining the impact of NAT on P2P applications. In this work, we build analytical models to capture the performance of BitTorrent-like P2P systems in a steady state, in the presence of homogeneous and heterogeneous NAT peers. We also propose biased optimistic unchoke strategies, in order to improve the overall system performance and fairness metrics considerably. The analytical models have been validated by simulation results, which also reveal some interesting facts about the coexistence of NAT and public peers in P2P systems.

The multifaceted utilization of mobile computing devices, including smart phones, PDAs, tablet computers with increasing functionalities and the advances in wireless technologies, has fueled the utilization of collaborative computing (peer-to-peer) technique in mobile environment. Mobile collaborative computing, known as mobile peer-to-peer (MP2P), can provide an economic way of data access among users of diversified applications in our daily life (exchanging traffic condition in a busy high way, sharing price-sensitive financial information, getting the most-recent news), in national security (exchanging information and collaborating to uproot a terror network, communicating in a hostile battle field) and in natural catastrophe (seamless rescue operation in a collapsed and disaster torn area). Nonetheless, data/content dissemination among the mobile devices is the fundamental building block for all the applications in this paradigm. The objective of this research is to propose a data dissemination scheme for mobile distributed systems using an MP2P technique, which maximizes the number of required objects distributed among users and minimizes to object acquisition time. In specific, we introduce a new paradigm of information dissemination in MP2P networks. To accommodate mobility and bandwidth constraints, objects are segmented into smaller pieces for efficient information exchange. Since it is difficult for a node to know the content of every other node in the network, we propose a novel Spatial-Popularity based Information Diffusion (SPID) scheme that determines urgency of contents based on the spatial demand of mobile users and disseminates content accordingly. The segmentation policy and the dissemination scheme can reduce content acquisition time for each node. Further, to facilitate efficient scheduling of information transmission from every node in the wireless mobile networks, we modify and apply the distributed maximal independent set (MIS) algorithm. We also consider neighbor overlap for closely located mobile stations to reduce duplicate transmission to common neighbors. Different parameters in the system such as node density, scheduling among neighboring nodes, mobility pattern, and node speed have a tremendous impact on data diffusion in an MP2P environment. We have developed analytical models for our proposed scheme for object diffusion time/delay in a wireless mobile network to apprehend the interrelationship among these different parameters. In specific, we present the analytical model of object propagation in mobile networks as a function of node densities, radio range, and node speed. In the analysis, we calculate the probabilities of transmitting a single object from one node to multiple nodes using the epidemic model of spread of disease. We also incorporate the impact of node mobility, radio range, and node density in the networks into the analysis. Utilizing these transition probabilities, we construct an analytical model based on the Markov process to estimate the expected delay for diffusing an object to the entire network both for single object and multiple object scenarios. We then calculate the transmission probabilities of multiple objects among the nodes in wireless mobile networks considering network dynamics. Through extensive simulations, we demonstrate that the proposed scheme is efficient for data diffusion in mobile networks.

No description available.

Les systèmes pair-à-pair (P2P) sont utilisés par des millions d'usagers tous les jours. Dans beaucoup de cas, un usager souhaite communiquer, échanger du contenu ou des services à travers différents systèmes P2P. Cela requiert de la coopération entre les différents systèmes P2P, ce qui est très souvent difficile ou même impossible à obtenir, à cause des raisons suivantes; in primis, l'absence d'une infrastructure de routage entre les réseaux, ce qui rend la communication étanche et, in secundis, l'incompatibilité des protocoles et des opérations des susdits systèmes. L'objectif principal de cette thèse est celui de permettre la coopération entre systèmes P2P. La thèse introduit un cadre de coopération rétro-compatible entre systèmes P2P hétérogènes constitué de deux parties. La première est un cadre de routage intra-réseaux permettant à des réseaux hétérogènes de communiquer. La deuxième est une application coopérative, conçue à l'aide et au travers du cadre de routage, dont l'objectif est celui de résoudre les incompatibilités protocolaires des systèmes P2P sous-jacents. Comme étude de cas de notre cadre de coopération, on présente une solution complète permettant une coopération entre des réseaux P2P spécialisés dans l'échange des fichiers pouvant s'appliquer aux réseaux P2P actuels. Dans la deuxième partie de la thèse, on présente une étude de cas d'usage de notre architecture d'interconnexion des réseaux P2P pour la collecte et la gestion des données dans réseaux d'électricité intelligents.

Ordinary desktop computers continue to obtain ever more resources – in-creased processing power, memory, network speed and bandwidth – yet these resources spend much of their time underutilised. Cycle stealing frameworks harness these resources so they can be used for high-performance computing. Traditionally cycle stealing systems have used client-server based architectures which place significant limits on their ability to scale and the range of applica-tions they can support. By applying a fully decentralised network model to cycle stealing the limits of centralised models can be overcome. Using decentralised networks in this manner presents some difficulties which have not been encountered in their previous uses. Generally decentralised ap-plications do not require any significant fault tolerance guarantees. High-performance computing on the other hand requires very stringent guarantees to ensure correct results are obtained. Unfortunately mechanisms developed for traditional high-performance computing cannot be simply translated because of their reliance on a reliable storage mechanism. In the highly dynamic world of P2P computing this reliable storage is not available. As part of this research a fault tolerance system has been created which provides considerable reliability without the need for a persistent storage. As well as increased scalability, fully decentralised networks offer the ability for volunteers to communicate directly. This ability provides the possibility of supporting applications whose tasks require direct, message passing style communication. Previous cycle stealing systems have only supported embarrassingly parallel applications and applications with limited forms of communication so a new programming model has been developed which can support this style of communication within a cycle stealing context. In this thesis I present a fully decentralised cycle stealing framework. The framework addresses the problems of providing a reliable fault tolerance sys-tem and supporting direct communication between parallel tasks. The thesis includes a programming model for developing cycle stealing applications with direct inter-process communication and methods for optimising object locality on decentralised networks.