In this paper, we investigate the topology convergence problem for the gossip-based Gradient overlay network. In an overlay network where each node has a local utility value, a Gradient overlay network is characterized by the properties that each node has a set of neighbors containing higher utility values, such that paths of increasing utilities emerge in the network topology. The Gradient overlay network is built using gossiping and a preference function that samples from nodes using a uniform random peer sampling service. We analyze it using tools from matrix analysis, and we prove both the necessary and sufficient conditions for convergence to a complete gradient structure, as well as estimating the convergence time. Finally, we show in simulations the potential of the Gradient overlay, by building a more efficient live-streaming peer-to-peer (P2P) system than one built using uniform random peer sampling. / <p>© 2011 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. QC 20111124</p>

Content delivery through service overlay networks has gained popularity due to the overlays’ abilities to provide effective and reliable services. Inefficiencies of one-to-one matching of user requirements to a single service have given rise to service composition. Customized media delivery can be achieved through dynamic compositions of Service Specific Overlay Networks (SSONs). However, the presence of SSONs in dynamic environments raises the possibility of unexpected failures and quality degradations. Thus constructing, managing, and repairing corrupted service paths are challenging dilemmas. This thesis investigates the problem of autonomous SSON construction and management and identifies the drawbacks of current approaches. A novel multi-layered, autonomous, self-adaptive framework for constructing SSONs is presented. The framework includes a Hybrid Service Overlay Network layer (H-SON). The H-SON is a dynamic hybrid overlay dedicated to service composition for multimedia delivery in dynamic networks. Node placement in the overlay depends on the node’s stability, types and quality of provided services. Changes in stability and QoS of service nodes are reflected by dynamic re-organizations of the overlay. The H-SON permits fast and efficient searches for component services that meet client functional and quality expectations. Self-managed overlay nodes coordinate their behaviors to formulate a service composition path that meets the client’s requirements. Two approaches are presented in this work. The first illustrates how SSONs are established through dynamically adaptable MS-designed plans. The imprecise nature of nonfunctional service characteristics, such as QoS, is modeled using a fuzzy logic system. Moreover, semantic similarity evaluations enable us to include, in compositions, those services whose operations match, semantically, the requirements of the composition plan. Plan-based composition solutions restrict service discovery to defined abstract models. Our second composition approach introduces a semantic similarity and nearness SSON composition method. The objective is to free service nodes from the adherence to restrictive composition plans. The presented work illustrates a service composition solution that semantically advances service composition paths towards meeting users’ needs with each service hop while simultaneously guaranteeing user-acceptable QoS levels. Simulation results showcase the effectiveness of the presented work. Gathered results validate the success of our service composition methods while meeting user requirements.

Content delivery through service overlay networks has gained popularity due to the overlays’ abilities to provide effective and reliable services. Inefficiencies of one-to-one matching of user requirements to a single service have given rise to service composition. Customized media delivery can be achieved through dynamic compositions of Service Specific Overlay Networks (SSONs). However, the presence of SSONs in dynamic environments raises the possibility of unexpected failures and quality degradations. Thus constructing, managing, and repairing corrupted service paths are challenging dilemmas. This thesis investigates the problem of autonomous SSON construction and management and identifies the drawbacks of current approaches. A novel multi-layered, autonomous, self-adaptive framework for constructing SSONs is presented. The framework includes a Hybrid Service Overlay Network layer (H-SON). The H-SON is a dynamic hybrid overlay dedicated to service composition for multimedia delivery in dynamic networks. Node placement in the overlay depends on the node’s stability, types and quality of provided services. Changes in stability and QoS of service nodes are reflected by dynamic re-organizations of the overlay. The H-SON permits fast and efficient searches for component services that meet client functional and quality expectations. Self-managed overlay nodes coordinate their behaviors to formulate a service composition path that meets the client’s requirements. Two approaches are presented in this work. The first illustrates how SSONs are established through dynamically adaptable MS-designed plans. The imprecise nature of nonfunctional service characteristics, such as QoS, is modeled using a fuzzy logic system. Moreover, semantic similarity evaluations enable us to include, in compositions, those services whose operations match, semantically, the requirements of the composition plan. Plan-based composition solutions restrict service discovery to defined abstract models. Our second composition approach introduces a semantic similarity and nearness SSON composition method. The objective is to free service nodes from the adherence to restrictive composition plans. The presented work illustrates a service composition solution that semantically advances service composition paths towards meeting users’ needs with each service hop while simultaneously guaranteeing user-acceptable QoS levels. Simulation results showcase the effectiveness of the presented work. Gathered results validate the success of our service composition methods while meeting user requirements.

Content delivery through service overlay networks has gained popularity due to the overlays’ abilities to provide effective and reliable services. Inefficiencies of one-to-one matching of user requirements to a single service have given rise to service composition. Customized media delivery can be achieved through dynamic compositions of Service Specific Overlay Networks (SSONs). However, the presence of SSONs in dynamic environments raises the possibility of unexpected failures and quality degradations. Thus constructing, managing, and repairing corrupted service paths are challenging dilemmas. This thesis investigates the problem of autonomous SSON construction and management and identifies the drawbacks of current approaches. A novel multi-layered, autonomous, self-adaptive framework for constructing SSONs is presented. The framework includes a Hybrid Service Overlay Network layer (H-SON). The H-SON is a dynamic hybrid overlay dedicated to service composition for multimedia delivery in dynamic networks. Node placement in the overlay depends on the node’s stability, types and quality of provided services. Changes in stability and QoS of service nodes are reflected by dynamic re-organizations of the overlay. The H-SON permits fast and efficient searches for component services that meet client functional and quality expectations. Self-managed overlay nodes coordinate their behaviors to formulate a service composition path that meets the client’s requirements. Two approaches are presented in this work. The first illustrates how SSONs are established through dynamically adaptable MS-designed plans. The imprecise nature of nonfunctional service characteristics, such as QoS, is modeled using a fuzzy logic system. Moreover, semantic similarity evaluations enable us to include, in compositions, those services whose operations match, semantically, the requirements of the composition plan. Plan-based composition solutions restrict service discovery to defined abstract models. Our second composition approach introduces a semantic similarity and nearness SSON composition method. The objective is to free service nodes from the adherence to restrictive composition plans. The presented work illustrates a service composition solution that semantically advances service composition paths towards meeting users’ needs with each service hop while simultaneously guaranteeing user-acceptable QoS levels. Simulation results showcase the effectiveness of the presented work. Gathered results validate the success of our service composition methods while meeting user requirements.

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.