Today's distributed systems exist on a scale that was unimaginable only a few decades ago. Distributed systems now can consist of thousands or even millions of computers spread across the entire world. These large systems are often organized into overlay networks - networks composed of virtual links, with each virtual link realized by one or more physical links. Self-stabilizing overlay networks promise that, starting from any weakly-connected configuration, the correct network topology is always built. This area of research is young, and prior examples of self-stabilizing overlay networks have either been for simple topologies, or involved complex algorithms that were difficult to verify and extend. We address these limitations in this thesis. First, we present the Transitive Closure Framework, a generic framework to transform any locally-checkable overlay network into a self-stabilizing network. This simple framework has a running time which is at most a logarithmic number of rounds more than optimal, and in fact is optimal for a particular class of overlay networks. We also prove the only known non-trivial lower bound on the convergence time of any self-stabilizing overlay network. To allow fast and efficient repairs for local faults, we extend the Transitive Closure Framework to the Local Repair Framework. We demonstrate this framework by implementing an efficient algorithm for node joins in the Skip+ graph. Next, we present the Avatar network, which is a generic locally checkable overlay network capable of simulating many other overlay networks. We design a self-stabilizing algorithm for a binary search tree embedded onto the Avatar network, and prove this algorithm requires only a polylogarithmic number of rounds to converge and limits degree increases to within a polylogarithmic factor of optimal. This algorithm is the first to achieve such efficiency, and its modular design makes it easy to extend. Finally, we introduce a technique called network scaffolding, which builds other overlay network topologies using the Avatar network.

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.

While the demand for video streaming services has risen rapidly in recent years, supporting video streaming service to a large number of receivers still remains a challenging task. Issues of video streaming in the Internet, such as scalability, and reliability are still under extensive research. Recently proposed network contexts such as overlay networks, and mobile ad hoc networks pose even tougher challenges. This thesis focuses on supporting scalable video streaming applications under various network environments. More specifically, this thesis investigates the following problems: i) Server selection in replicated batching video on demand (VoD) systems: we find out that, to optimize the user perceived latency, it is vital to consider the server state information and channel allocation schemes when making server selection decisions. We develop and evaluate a set of server selection algorithms that use increasingly more information. ii) Scalable live video streaming with time shifting and video patching: we consider the problem of how to enable continuous live video streaming to a large group of clients in cooperative but unreliable overlay networks. We design a server-based architecture which uses a combined technique of time-shifting video server and P2P video patching. iii) A Cooperative patching architecture in overlay networks: We design a cooperative patching architecture which shifts video patching responsibility completely to the client side. An end-host retrieves lost data from other end-hosts within the same multicast group. iv) V3: a vehicle to vehicle video streaming architecture: We propose V3, an architecture to provide live video streaming service to driving vehicles through vehicle-to-vehicle (V2V) networks. V3 incorporates a novel signaling mechanism to continuously trigger video sources to send video data back to the receiver. It also adopts a store-carry-and-forward approach to transmit video data in a partitioned network environment. We also develop a multicasting framework that enables live video streaming applications from multiple sources to multiple receivers in V2V networks. A message integration scheme is used to suppress the signaling overhead, and a two-level tree-based routing approach is adopted to forward the video data.

Configuration capabilities are important for modern advanced network services. Network conditions and user populations have been significantly diversified after decades of evolution of the Internet. Configuration capabilities allow network services to be adapted to spatial, temporal, and managerial variations in application requirements and service operation conditions. Network service providers need to decide on the best configuration. Ideally, a network service should have all of its components optimally configured to most effectively deliver the functionality for which it was designed. The optimal configuration, however, is always a compromise between different metrics. To decide on an optimal configuration, the prominent performance and cost metrics must be identified, modeled, and quantified. Optimization objective functions and constraints that combine these metrics should be formulated and optimization techniques should be developed. More important, in the scenarios where the application requirements and system conditions change over time, the service configuration needs to be dynamically adjusted and strategies that guide the reconfiguration decisions need to be developed. Because the actual process of configuring a network service incurs configuration costs, an optimal reconfiguration strategy should be one that achieves a tradeoff between the (re)configuration costs and static optimization objectives. Furthermore, such tradeoffs must be based on the consideration of long-term benefits instead of short-term interest. This thesis focuses on understanding the strategies for dynamic (re)configuration of advanced network services positioned above the Transport Layer. Specifically, this thesis investigates the configuration and more important dynamic reconfiguration strategies for two types of advanced network services: Service Overlay Networks, and Content Resiliency Service Networks. Unlike those network services whose configuration involves mainly arrangement of hard-wired components, these network services have the ability to change service configuration in small time scales. This makes the modeling of application requirements and system condition dynamics not only possible but also meaningful and potentially useful. Our goal is to develop modeling and optimization techniques for network service configuration and dynamic reconfiguration policies. We also seek to understand how effective techniques can improve the performance or reduce the cost of these advanced network services, thus demonstrating the advantage of allowing configurability in these advanced network services.

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.

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.

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.

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.