Publish/Subscribe (in short pub/sub) allows clients that share common interest communicate in an asynchronous and loosely-coupled fashion. This paradigm is adopted by many distributed event-driven applications such as social networking services, distributed business processes and cyber-physical systems. These applications cannot afford to have the underlying pub/sub substrate perform unreliably, permanently fail or behave arbitrarily as it will cause significant disturbance to stably serving many end-users. Therefore, a research effort on making pub/sub systems resilient against various failures to sustain high quality of service to the clients is imperative. In this thesis, we focus on the overlay of pub/sub brokers that are widely adopted as a popular architecture for large-scale pub/sub systems. Broker overlays can suffer from various issues such as degradation of topology quality, brokers causing transient or permanent benign failures and Byzantine brokers behaving arbitrarily. We aim to make novel research contributions by exploring fundamental techniques that can help the broker overlays maintain functional and non-functional requirements even under the presence of the aforementioned failures and necessary administrative updates. We first build a set of overlay adaptation primitives that re-configure topologies such as shifting links and replicating brokers. These primitives are designed to involve a small local group of brokers in the pub/sub overlays so that the disruption during the execution of large-scale and dynamic changes can be controlled in a fined-grained manner. For the problem of degrading topology quality, automated planning systems are developed to find a sequence of adaptations that would cause minimal disruption to running services. Also, our primitives can be executed on demand to quickly fail-over a crashed broker or off-load congested brokers. In addition, these on-demand primitives can be used to form a group of dynamically replicated brokers that enforce a novel safety measure to prevent Byzantine brokers from sabotaging the pub/sub overlays. Our contributions are evaluated with systematic consideration of various trade-offs between functional and non-functional properties.

The constant growth in network communications technologies and the emergence of Service Specific Overlay Networks (SSONs), coupled with the rapid development of multimedia applications make the management of such technologies a major challenge. This thesis investigates the SSONs management problem and proposes an autonomic architecture, a self-organizing and self-adapting algorithm, and a utility function for monitoring the Quality of Experience (QoE) of IPTV streams in SSONs. First, we examine the different issues stemming from the autonomic management of SSONs and identify the limitations of existing approaches. We then propose an architecture to ease the management of SSONs by incorporating autonomic computing principles to make SSONs acquire self-management capabilities. The proposed architecture introduces autonomic control loops that continuously monitor network components and analyze the gathered data. An Autonomic System (AS) is comprised of one or more Autonomic Managers (AM) which take control of managing other elements in the network. The proposed architecture highlights the different components of an AM and identifies its purpose. The distributed nature of the proposed architecture avoids limitations of centralized management solutions. We then propose a scheme to allow AMs to emerge among the set of nodes in the network as the most powerful ones in terms of different factors, including processing capabilities and stability. Using a self-organizing and self-adapting distributed protocol, each node in the overlay selects an appropriate AM to report to so that sensed data is delivered error-free, and in a timely manner, while the load is distributed over the AMs. Finally, we propose a utility function to monitor the quality of IPTV streams by predicting QoE based on statistical Quality of Service (QoS) information. The proposed function is simple and does not require high processing power. It allows the QoE of IPTV users to be monitored in real-time by the AMs, so that quality degradations are accurately identified and adaptation mechanisms are triggered at the right moment to correct issues causing degradations. Theoretical analysis and simulations studies are presented to demonstrate the performance of the proposed schemes.

Data connectivity between cellular devices can be achieved in different ways. It is possible to enable full IPconnectivity in the cellular networks. However this connectivity is combined with a lot of issues such as security problems and the IPv4 address space being depleted. As a result of this many operators use Network Address Translation in their packet data networks, preventing users in different networks from being able to contact each other. Even if a transition to IPv6 takes place and the potential problem of address space is solved, it is not likely that operators will leave their packet data networks open to the Internet. An alternative to solving the problem on the IP level is to use overlay networks. In an overlay network applications on the cellular devices identify themselves at the application level rather than on the IP level. While full IP connectivity always gives the most efficient routing, an overlay network can offer services that are difficult to implement on the IP level. This can enable an application to span Network Address Translating entities without having to share the entire device. They can also provide private dynamic virtual networks and groups for users that trust each other. These private networks can use permissions and group casting functions, without the problems associated with traditional IP multicast. The relatively limited bandwidths of the GSM and UMTS networks allow for application level routing of continuous data streams if the overlay network is distributed enough and mapped to the physical network in an efficient way. One of the advantages of using overlay networks is that although standard IP networks may be able to offer similar services in the future, overlay networks can be implemented in the existing IPv4 networks today at comparatively low costs. This may create the incentive needed in order for future larger investments to be justified. A distributed overlay network not only allows for real-time services such as instant messaging, which is already possible with a centralized server solution, but it also allows for higher bandwidth services such as video conferencing, Voice over IP, etc. that are not possible on a large scale with a centralized relaying server. An overlay network could be implemented by any third party without the support of an operator. This suggests that free networks may be created for what could be called reversed file sharing, i.e. networks where users upload files to each other rather than download as in most existing file sharing networks. These could become direct competitors to SMS, MMS and other operator-owned services. The thesis investigates the mentioned possibilities and potential threats. Along with this an implementation of an overlay network for cellular devices is created that is totally independent of the operator’s network. / Datakonnektivitet mellan cellulära terminaler kan uppnås på olika sätt. Ett sätt är att utrusta de cellulära näten med full IP konnektivitet. Detta medför dock en del problem såsom säkerhetsfrågor och problem med att antalet IPv4 addresser kanske inte kan täcka framtidens behov. På grund av detta använder många operatörer såkallad nätverksadressöversättning i sina paketdatanät vilket hindrar användare i olika paketdatanät från att kunna kontakta varandra. Även om en framtida övergång till IPv6 löser problemen med för liten adressrymd så är det inte troligt att operatörerna kommer att lämna sina paketdatanät öppna mot resten av Internet. Ett alternativ till att lösa problemet på IP-nivån är att istället använda overlaynätverk. I ett sådant nätverk identifierar applikationer sig själva på applikationsnivån istället för på IP-nivån. Medans ren IP-konnektivitet innebär effektivast möjliga routing av data så erbjuder ett overlaynätverk möjlighet till tjänster som är svåra att implementera på IP-nivå. Bland annat kan applikationsnät som traverserar nätverksadressöversatta nätverk skapas utan att en mobil terminal behöver exponeras helt och hållet mot Internet. Dessa overlaynätverk kan också skapas dynamiskt och tillfälligt vilket ger användare möjlighet att skapa privata nätverk och grupper med med enheter de litar på, endast dessa får då tillgång till terminalen. Overlaynätverken kan också erbjuda multicast funktionalitet inom grupperna utan de problem som hör ihop med traditionell IP-multicast. De relativt begränsade bandbredderna i GSM och UMTS nätverken tillåter routing av data på applikationsnivån om overlaynätverket är tillräckligt väl distribuerat och effektivt mappat mot det underliggande nätverket. En av fördelarna med att använda overlaynätverk är att även om den eftersökta funktionaliteten kanske kan implementeras på IP-nivå i framtiden med hjälp av ny teknik så kan overlaynätverk implementeras i nuvarande IPv4-nätverk till relativt låga kostnader då de endast består av mjukvara som körs på existerande hårdvara. Ett distribuerat overlaynätverk erbjuder inte bara realtidstjänster såsom instant messaging vilket redan är möjligt och fungerar bra med en central serverlösning. Det distribuerade nätverket kan dessutom hantera routing av högre bandbredder mellan terminaler, såsom videokonferenser, Voice over IP etc. som inte är möjligt i stor skala med en centraliserad lösning. Overlaynätverk kan implementeras av en tredjepart utan operatörers samarbete. Detta kan innebära att gratisnätverk skapas för vad som skulle kunna kallas omvänd fildelning, dvs. nätverk där användare laddar upp information till varandra snarare än laddar ner vilket är fallet i de flesta existerande fildelningsnätverk. Dessa nätverk skulle kunna bli direkta konkurrenter till SMS, MMS och andra operatörsägda tjänster. Examensarbetet undersöker de nämnda möjligheterna och potentiella hoten i dessa nätverk. Utöver detta skapas även en implementation av ett overlaynätverk som är helt oberoende av operatörens nätverk.

No description available.

Hermes é um arcabouço para a programação de aplicações P2P. Com ele, pode-se criar diversos tipos de aplicações distribuídas, sem se preocupar com a camada de comunicação. O Hermes não é uma implementação de uma rede de sobreposição P2P, e sim uma camada acima das implementações já existentes. O desenvolvedor da aplicação fica isolado da implementação da rede de sobreposição utilizada. Esse isolamento é feito de forma tal que não há limitações quanto à arquitetura de rede utilizada pela implementação, seja ela centralizada, descentralizada, distribuída estruturada ou distribuída não-estruturada. Entre os serviços oferecidos pelo Hermes estão: troca de mensagens, busca, comunicação em grupo e armazenamento distribuído. Geralmente, no início do desenvolvimento de uma aplicação distribuída, tem-se poucas informações sobre o seu tamanho final ou perfil de utilização. O Hermes possibilita ao desenvolvedor da aplicação adiar, até o momento da efetiva implantação do sistema, a decisão sobre qual arquitetura de rede ou qual implementação de rede de sobreposição são as mais apropriadas para suas necessidades. Possibilita também, quando o perfil de utilização muda com o tempo, a troca da implementação utilizada por uma outra que se adeque mais ao novo perfil sem alterações no código da aplicação. / Hermes is a framework for P2P application programming. Using it, one can create several kinds of distributed applications without worrying about the underlying network. Hermes is not a P2P overlay network implementation, but a shell envolving existing implementations. The application developer is isolated from the implementation of the overlay network in use. This isolation is done in a way that poses no limitations on the network architecture used, which may be centralized, decentralized, structured or unstructured. Amongst the services offered by Hermes are: message exchange, search, group communication, and distributed storage. In the early stages of the development of a distributed application, information as to its final size or utilization profile is often unknown. Hermes gives the application developer the possibility of delaying, until the actual moment of system deployment, the decision as to which network architecture or which overlay network implementation is the most appropriate. It also gives the developer the choice, when utilization profile changes over time, of replacing the network implementation with one more suitable to the application needs, without changes on the application code.

This dissertation presents algorithms for data structures called distributed hash tables (DHT) or structured overlay networks, which are used to build scalable self-managing distributed systems. The provided algorithms guarantee lookup consistency in the presence of dynamism: they guarantee consistent lookup results in the presence of nodes joining and leaving. Similarly, the algorithms guarantee that routing never fails while nodes join and leave. Previous algorithms for lookup consistency either suffer from starvation, do not work in the presence of failures, or lack proof of correctness. Several group communication algorithms for structured overlay networks are presented. We provide an overlay broadcast algorithm, which unlike previous algorithms avoids redundant messages, reaching all nodes in O(log n) time, while using O(n) messages, where n is the number of nodes in the system. The broadcast algorithm is used to build overlay multicast. We introduce bulk operation, which enables a node to efficiently make multiple lookups or send a message to all nodes in a specified set of identifiers. The algorithm ensures that all specified nodes are reached in O(log n) time, sending maximum O(log n) messages per node, regardless of the input size of the bulk operation. Moreover, the algorithm avoids sending redundant messages. Previous approaches required multiple lookups, which consume more messages and can render the initiator a bottleneck. Our algorithms are used in DHT-based storage systems, where nodes can do thousands of lookups to fetch large files. We use the bulk operation algorithm to construct a pseudo-reliable broadcast algorithm. Bulk operations can also be used to implement efficient range queries. Finally, we describe a novel way to place replicas in a DHT, called symmetric replication, that enables parallel recursive lookups. Parallel lookups are known to reduce latencies. However, costly iterative lookups have previously been used to do parallel lookups. Moreover, joins or leaves only require exchanging O(1) messages, while other schemes require at least log(f) messages for a replication degree of f. The algorithms have been implemented in a middleware called the Distributed k-ary System (DKS), which is briefly described. / QC 20100824

Middleware has become a key enabler for the development of distributed applications. Unfortunately, conventional middleware technologies do not yet offer sufficient functionality to make them suitable for mobile environments. This dissertation proposes a novel middleware approach termed opportunistic overlays and its dynamically reconfigurable support framework for building efficient mobile applications. Specifically, we address the inefficiency of content delivery introduced by node mobility and by dynamically changing system loads, in the context of publish/subscribe systems. In response to changes in physical network topology, in nodes' physical locations, and in network node behaviors, the opportunistic overlay approach dynamically adapts event dissemination structures (i.e., broker overlays) with the goal of optimizing end-to-end delays in event delivery. Adaptation techniques include the dynamic construction of broker overlay networks, runtime changes of mobile clients' assignments to brokers, and dynamic broker load balancing. Essentially, opportunistic overlays implement a middleware-level analogue of the networking routing protocols used in wireless communications (i.e., Mobile IP, AODV, DSR and DSDV). By thus coordinating network- with middleware-level routing, opportunistic overlays can attain substantial performance improvements over non-adaptive event systems. Such improvements are due to their use of shorter network paths and better balancing of loads across event brokers. Opportunistic overlays and the adaptive methods they use are realized by a set of distributed protocols implemented in a Java-based publish/subscribe infrastructure. Comprehensive performance evaluations are performed via simulation, emulation, and with two representative applications on actual networks. Experimental results demonstrate that the opportunistic overlay approach is practically applicable and that the performance advantages attained from the use of opportunistic overlays can be substantial, in both infrastructure-based mobile environments and mobile ad hoc networks.

Performance evaluation continues to play an important role in network research. Two types of research efforts related to network performance evaluation are particularly noteworthy: (1) using performance evaluation to understand specific problems and to design better solutions, and (2) designing efficient performance evaluation methodologies. This thesis addresses several performance evaluation challenges, encompassing both categories of effort listed above, in building high-performance TCP-based network services in the context of overlay routing and peer-to-peer systems. With respect to the first type of research effort, this thesis addresses two issues related to the design of TCP-based network services: 1. Prediction of large transfer TCP throughput: Predicting the TCP throughput attainable on given paths is used for applications such as route selection in overlay routing. Based on a systematic measurement study, we evaluate the accuracy of two categories of TCP throughput prediction techniques. We then analyze the factors that affect the accuracy of each. 2. Congestion control and message loss in Gnutella peer-to-peer networks: We evaluate the congestion control mechanisms and message loss behavior in a real-world overlay network, the Gnutella system. The challenges for congestion control in such a network are analyzed, as are the design tradeoffs of alternative mechanisms. In order to study systems such as the above with details of the network, we build a scalable, extensible and portable packet-level simulator of peer-to-peer systems. The second part of the thesis, representing the second type of effort above, proposes two techniques to improve network simulation by exploiting the detailed knowledge of TCP: 1. Speed up network simulation by exploiting TCP steady-state predictability: We develop a technique that uses prediction to accurately summarize a series of packet events and, therefore, to save on processing cost while maintaining fidelity. Our technique integrates well with packet-level simulations and is more faithful in several respects than previous optimization techniques. 2. TCP workload generation under link load constraints: We develop an algorithm that generates traffic for a specific network configuration such that realistic and specific load conditions are obtained on user-specified links. At the same time, the algorithm minimizes the simulation memory requirement.

The Internet has been designed as a best-effort network, which does not provide any additional services to applications using the network. Overlay networks, which form an application layer network on top of the underlying Internet, have emerged as popular means to provide specific services and greater control to applications. Overlay networks offer a wide range of services, including content distribution, multicast and multimedia streaming. In my thesis, I focus on overlay networks for content distribution, used by applications such as bulk data transfer, file sharing and web retrieval. I first investigate the construction of such overlay networks by studying the bootstrapping functionality in an example network (the Gnutella peer-to-peer system). This study comprises the analysis and performance measurements of Gnutella servents and measurement of the GWebCache system that helps new peers find existing peers on the Gnutella network. Next, I look at fairness issues due to the retrieval of data at a client in the form of multipoint-to-point sessions, formed due to the use of content distribution networks. A multipoint-to-point session comprises multiple connections from multiple servers to a single client over multiple paths, initiated to retrieve a single application-level object. I investigate fairness of rate allocation from a session point of view, and propose fairness definitions and algorithms to achieve these definitions. Finally, I consider the problem of designing an overlay network for content distribution, which is fair to competing overlay networks, while maximizing the total end-to-end throughput of the data it carries. As a first step, I investigate this design problem for a single path in an Overlay-TCP network. I propose two schemes that dynamically provision the number of TCP connections on each hop of an Overlay-TCP path to maximize the end-to-end throughput using few extraneous connections. Next, I design an Overlay-TCP network, with the secondary goal of intra-overlay network fairness. I propose four schemes for deciding the number of TCP connections to be used on each overlay hop. I show that one can vary the proportion of sharing between competing overlay networks by varying the maximum number of connections allowed on overlay hops in each competing network.

A covert communications network (CCN) is a connected, overlay peer-to-peer network used to support communications within a group in which the survival of the group depends on the confidentiality and anonymity of communications, on concealment of participation in the network to both other members of the group and external eavesdroppers, and finally on resilience against disconnection. In this dissertation, we describe the challenges and requirements for such a system. We consider the topologies of resilient covert communications networks that: (1) minimize the impact on the network in the event of a subverted node; and (2) maximize the connectivity of the survivor network with the removal of the subverted node and its closed neighborhood. We analyze the properties of resilient covert networks, propose measurements for determining the suitability of a topology for use in a covert communication network, and determine the properties of an optimal covert network topology. We analyze multiple topologies and identify two constructions that are capable of generating optimal topologies. We then extend these constructions to produce near-optimal topologies that can “grow” as new nodes join the network. We also address protocols for membership management and routing. Finally, we describe the architecture of a prototype system for instantiating a CCN.