Master of Science / Department of Electrical and Computer Engineering / Caterina M. Scoglio / Recently, virtualization was proposed in many scientific fields. Virtualization is widely applied in telecommunications where networks are required to be extremely flexible to meet the current and the unpredictable future requirements. The creation of a virtual network over the physical network allows the application developers to design new services provided to the users without modifying the underlay resources. The creation of a virtual network of light paths and light trees over the optical network allows the resources managers to utilize the huge optical capacity more efficiently. In this thesis, we consider the optimal topology design for the virtual networks taking into consideration traffic demands and quality of service constraints of the applications. Considered examples of virtual networks are the overlay networks at the application layer and the virtual light path and light tree networks at the optical layer. In the design of overlay topologies, the performance of the virtual networks is affected by traffic characteristic, and behavior of nodes which can be selfish or cooperative. Both the static and dynamic traffic demand scenarios are considered. The static demand scenario follows well known probability distributions, while in the dynamic traffic scenario, the traffic matrix is predicted through measurements over each link in the network. We study the problem of finding the overlay topology that minimizes a cost function which takes into account the overlay link creation cost and the routing cost. We formulate the problem as an Integer Linear Programming and propose heuristics to find near-optimal overlay topologies with a reduced complexity. Virtual optical networks are designed to support many applications. Multicast sessions are an example of the applications running over the optical network. The main objective in creating the hybrid topology, composed by light paths and light trees, is to increase number of supported multicast sessions through sharing the network resources. The problem of establishing the hybrid topology is formulated using the Integer Linear Programming. Extensive data results and analysis are performed on the generated hybrid topologies for evaluation.

Dans cette thèse, nous abordons deux problèmes soulevés par les systèmes distribués décentralisés - le placement de réseaux logiques de façon compatible avec le réseau physique sous-jacent et la construction de cohortes d'éditeurs pour dans les systèmes d'édition collaborative. Bien que les réseaux logiques (overlay networks) été largement étudiés, la plupart des systèmes existant ne prennent pas ou prennent mal en compte la topologie du réseau physique sous-jacent, alors que la performance de ces systèmes dépend dans une grande mesure de la manière dont leur topologie logique exploite la localité présente dans le réseau physique sur lequel ils s'exécutent. Pour résoudre ce problème, nous proposons dans cette thèse Fluidify, un mécanisme décentralisé pour le déploiement d'un réseau logique sur une infrastructure physique qui cherche à maximiser la localité du déploiement. Fluidify utilise une stratégie double qui exploite à la fois les liaisons logiques d'un réseau applicatif et la topologie physique de son réseau sous-jacent pour aligner progressivement l'une avec l'autre. Le protocole résultant est générique, efficace, évolutif et peut améliorer considérablement les performances de l'ensemble. La deuxième question que nous abordons traite des plates-formes d'édition collaborative. Ces plates-formes permettent à plusieurs utilisateurs distants de contribuer simultanément au même document. Seuls un nombre limité d'utilisateurs simultanés peuvent être pris en charge par les éditeurs actuellement déployés. Un certain nombre de solutions pair-à-pair ont donc été proposées pour supprimer cette limitation et permettre à un grand nombre d'utilisateurs de collaborer sur un même document sans aucune coordination centrale. Ces plates-formes supposent cependant que tous les utilisateurs d'un système éditent le même jeu de document, ce qui est peu vraisemblable. Pour ouvrir la voie à des systèmes plus flexibles, nous présentons, Filament, un protocole décentralisé de construction de cohorte adapté aux besoins des grands éditeurs collaboratifs. Filament élimine la nécessité de toute table de hachage distribuée (DHT) intermédiaire et permet aux utilisateurs travaillant sur le même document de se retrouver d'une manière rapide, efficace et robuste en générant un champ de routage adaptatif autour d'eux-mêmes. L'architecture de Filament repose sur un ensemble de réseaux logiques auto-organisées qui exploitent les similarités entre jeux de documents édités par les utilisateurs. Le protocole résultant est efficace, évolutif et fournit des propriétés bénéfiques d'équilibrage de charge sur les pairs impliqués. / In this thesis, we address two issues in the area of decentralized distributed systems: network-aware overlays and collaborative editing. Even though network overlays have been extensively studied, most solutions either ignores the underlying physical network topology, or uses mechanisms that are specific to a given platform or applications. This is problematic, as the performance of an overlay network strongly depends on the way its logical topology exploits the underlying physical network. To address this problem, we propose Fluidify, a decentralized mechanism for deploying an overlay network on top of a physical infrastructure while maximizing network locality. Fluidify uses a dual strategy that exploits both the logical links of an overlay and the physical topology of its underlying network to progressively align one with the other. The resulting protocol is generic, efficient, scalable and can substantially improve network overheads and latency in overlay based systems. The second issue that we address focuses on collaborative editing platforms. Distributed collaborative editors allow several remote users to contribute concurrently to the same document. Only a limited number of concurrent users can be supported by the currently deployed editors. A number of peer-to-peer solutions have therefore been proposed to remove this limitation and allow a large number of users to work collaboratively. These decentralized solution assume however that all users are editing the same set of documents, which is unlikely to be the case. To open the path towards more flexible decentralized collaborative editors, we present Filament, a decentralized cohort-construction protocol adapted to the needs of large-scale collaborative editors. Filament eliminates the need for any intermediate DHT, and allows nodes editing the same document to find each other in a rapid, efficient and robust manner by generating an adaptive routing field around themselves. Filament's architecture hinges around a set of collaborating self-organizing overlays that utilizes the semantic relations between peers. The resulting protocol is efficient, scalable and provides beneficial load-balancing properties over the involved peers.

With growing number of devices connected to the network, there is a greater need for use of Peer-to-Peer (P2P) networks and distributed P2P protocols.Devices participating in the P2P network do not usually need to use any central server that links up connections. It has many advantages but it needs to use so-called overlay network that consists of protocols used for traffic routing and decision making. Protocols used in today’s P2P networks are mostly not considerate of particular participating nodes and all the nodes in the network are usually equal. This can have negative impacts on network performance. In order to avoid or reduce some unwanted negative impacts, it would be advantageous if the overlay network could route traffic and make decisions according to context information like battery levels or connection speeds. This work reviews a few popular P2P overlay networks and based on that it introduces an improvement of one of them – Chord. The structure of the improved version of the Chord protocol called Context-Aware Chord is described. Then results of the evaluation are presented. With a use of the improved protocol, nodes can participate longer in the network and throughput of lookup messages is improved.

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.

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.

<p>Structured overlay networks form a major classof peer-to-peer systems, which are touted for their abilitiesto scale, tolerate failures, and self-manage. Any long livedInternet-scale distributed system is destined to facenetwork partitions. Although the problem of network partitionsand mergers is highly related to fault-tolerance andself-management in large-scale systems, it has hardly beenstudied in the context of structured peer-to-peer systems.These systems have mainly been studied under churn (frequentjoins/failures), which as a side effect solves the problemof network partitions, as it is similar to massive nodefailures. Yet, the crucial aspect of network mergers has beenignored. In fact, it has been claimed that ring-based structuredoverlay networks, which constitute the majority of thestructured overlays, are intrinsically ill-suited for mergingrings. In this thesis, we present a number of research papers representing our work on handling network partitions and mergers in structured overlay networks. The contribution of this thesis is threefold. First, we provide a solution for merging ring-based structured overlays. Our solution is tuneable, by a {\em fanout} parameter, to achieve a trade-off between message and time complexity. Second, we provide a network size estimation algorithm for ring-based structured overlays. We believe that an estimate of the current network size can be used for tuning overlay parameters that change according to the network size, for instance the fanout parameter in our merger solution.Third, we extend our work from fixing routing anomalies to achieving data consistency. We argue that decreasing lookup inconsistencies on the routing level aids in achieving data consistency in applications built on top of overlays. We study the frequency of occurence of lookup inconsistencies and discuss solutions to decrease the affect of lookup inconsistencies.</p>

In the literature, Cognitive radio (CR) as well as full-duplex (FD) communication technologies are proposed to increase the spectrum efficiency. The main contribution of this thesis is to introduce prediction and estimation techniques with low control overhead, and use the predicted or estimated information in resource allocation in CR networks, both in the overlay networks and the underlay networks. Prediction and estimation are important in increasing the data rate and keeping the interference at a low level. In the overlay scheme, I modeled the primary user (PU) traffic characteristics of the channels using the Probabilistic Suffix Tree (PST) algorithm. Then using this PST algorithm, I introduced a frequency hopping based control channel and derived its theoretical properties. Then I proposed two methods for selecting a channel set for transmission, which took into account both the PU channel usage statistics and, secondary user (SU) channel usage statistics as perceived by an SU of interest. The first scheme selected channels having the highest probability of successful transmission, while the second calculated a net reward using a marked Markov chain. Then using simulations, I showed that our scheme caused acceptable interference to the PUs and has better throughput performance, compared to a scheme selecting channels randomly. Then I proposed two joint channel assignment and power allocation schemes for a bi-directional FD underlay CR network with network assistance. The first scheme used the information on the number of total SU pairs present in the network. In the second scheme, I used least squares based estimation and Kalman filtering to estimate the interference at the monitoring stations using the local interference. It reduced the control overhead of keeping track of active SUs. In both of these schemes each SU pair decided on the channels to be used in the half-duplex mode and the full-duplex mode using local information. This joint optimization was done running channel assignment and power allocation algorithms alternatively. In the power allocation problem, I used a technique called monotonic optimization. After simulating both of these schemes I showed that the scheme based on estimation performs satisfactorily given that it has less control overhead. / October 2016

Distributed applications built on top of Structured Overlay Networks (SONs) operate based on certain self-* behaviors of the underlying Peer-to-Peer network. Among those, self-organization and self-healing are the two most prominent and assumed properties. The operating environment of distributed systems continues to be more inhospitable with the advance and demand of new technologies; for example in case of mobile and ad hoc networks Churn (node turnover) can be extremely high due to node mobility, frequent disconnects/reconnects and configuration changes. Also, in such dynamic environments, the system may face high Churn (node turnover) and Network partition in a frequent manner. The situation becomes worse if the self-healing behavior of underlying SON is not complete and well defined. This implies the following non-trivial questions: Can the maintenance mechanism of a SON heal the damage to the structure due to harshness of the operating environment and reverse it back? What are the pre-conditions; in other words, what properties the healing mechanism should possess in order to achieve reversibility against stressful environments? Existing literature lacks such assessment and verification study of the self-healing property of a SON. In this thesis, we investigate both the behavior and design of a system that operate in inhospitable environments. This work is relevant to systems with both peaks of high stress (e.g. partitions, churn, network dynamicity etc.) and continuous high stress. We evaluate existing overlay maintenance strategies, namely Correction-on-Change, Correction-on-Use, Periodic Stabilization, and Ring Merge. We define the reversibility property of a system as its ability to repair itself to its original state. We propose a new strategy, called Knowledge Base, to improve conditions for reversibility against inhospitable environments. By means of simulations, we demonstrate reversibility for overlay networks with high levels of partition and churn. We make general conclusions about the ability of the maintenance strategies to achieve reversibility. Identification of Phase Transitions in a SON can provide useful information about the properties of each state of the system. Also, this enables to find the critical points in the operating space and parameters influencing them. The applications running on top of the SON can potentially utilize this knowledge to adapt its operation accordingly in different system states. In this thesis, a representative ring-based SON, namely Beernet is chosen and extended to achieve reversibility. The resulting overlay, Beernet++ exhibits reversible phase transitions under churn. We analyze the critical points observed during such transitions. We present the behavior of Beernet++ for high level of churn and network partitioning, along with their interaction. / <p>QC 20150929</p>

Conventional wisdom suggests that in order to build a secure system, security must be an integral component in the system design. However, cost considerations drive most system designers to channel their efforts on the system's performance, scalability and usability. With little or no emphasis on security, such systems are vulnerable to a wide range of attacks that can potentially compromise confidentiality, integrity and availability of sensitive data. It is often cumbersome to redesign and implement massive systems with security as one of the primary design goals. This thesis advocates a proactive approach that cleanly retrofits security solutions into existing system architectures. The first step in this approach is to identify security threats, vulnerabilities and potential attacks on a system or an application. The second step is to develop security tools in the form of customizable and configurable plug-ins that address these security issues and minimally modify existing system code, while preserving its performance and scalability metrics. This thesis uses overlay network applications to shepherd through and address challenges involved in supporting security in large scale distributed systems. In particular, the focus is on two popular applications: publish/subscribe networks and VoIP networks. Our work on VoIP networks has for the first time identified and formalized caller identification attacks on VoIP networks. We have identified two attacks: a triangulation based timing attack on the VoIP network's route set up protocol and a flow analysis attack on the VoIP network's voice session protocol. These attacks allow an external observer (adversary) to uniquely (nearly) identify the true caller (and receiver) with high probability. Our work on the publish/subscribe networks has resulted in the development of an unified framework for handling event confidentiality, integrity, access control and DoS attacks, while incurring small overhead on the system. We have proposed a key isomorphism paradigm to preserve the confidentiality of events on publish/subscribe networks while permitting scalable content-based matching and routing. Our work on overlay network security has resulted in a novel information hiding technique on overlay networks. Our solution represents the first attempt to transparently hide the location of data items on an overlay network.

Overlay networks have recently gained popularity as a viable alternative to overcome functionality limitations of the Internet (e.g., lack of QoS, multicast routing). They offer enhanced functionality to end-users by forming an independent and customizable virtual network over the native network. Typically, the routing at the overlay layer operates independent of that at the underlying native layer. There are several potential problems with this approach because overlay networks are selfish entities that are chiefly concerned with achieving the routing objective of their own users. This leads to complex cross-layer interactions between the native and overlay layers, and often tends to degrade the achieved performance for both layers. As overlay applications proliferate and the amount of selfish overlay traffic surges, there is a clear need for understanding the complex interactions and for strategies to manage them appropriately. Our work addresses these issues in the context of "service overlay networks", which represent virtual networks formed of persistent nodes that collaborate to offer improved services to actual end-systems. Typically, service overlays alter the route between the overlay nodes in a dynamic manner in order to satisfy a selfish objective. The objective of this thesis is to improve the stability and performance of overlay routing in this multi-layer environment. <br><br> We investigate the common problems of functionality overlap, lack of cross-layer awareness, mismatch or misalignment in routing objectives and the contention for native resources between the two layers. These problems often lead to deterioration in performance for the end-users. This thesis presents an analysis of the cross-layer interaction during fault recovery, inter-domain policy enforcement and traffic engineering in the multi-layer context. Based on our characterization of the interaction, we propose effective strategies that improve overall routing performance, with minimal side-effects on other traffic. These strategies typically 1) increase the layer-awareness (awareness of information about the other layer) at each layer, 2) introduce better control over routing dynamics and 3) offer improved overlay node placement options. Our results demonstrate how applying these strategies lead to better management of the cross-layer interaction, which in turn leads to improved routing performance for end-users.