Network virtualization and overlay networks have emerged as powerful tools for improving the flexibility of the Internet. Overlays are used to provide a wide range of useful services in today's networking environment, and they are also viewed as important building blocks for an agile and evolvable future Internet. Regardless of the specific service it provides, an overlay needs assistance in several areas in order to perform properly throughout its existence. This dissertation focuses on the mechanisms underlying the provision of auxiliary support services that perform control and management functions for overlays, such as overlay assignment, resource allocation, overlay monitoring and diagnosis. The priorities and objectives in the design of such mechanisms depend on network conditions and the virtualization environment. We identify opportunities for improvements that can help provide auxiliary services more effectively at different overlay life stages and under varying assumptions. The contributions of this dissertation are the following: 1. An overlay assignment algorithm designed to improve an overlay's diagnosability, which is defined as its property to allow accurate and low-cost fault diagnosis. The main idea is to increase meaningful sharing between overlay links in a controlled manner in order to help localize faults correctly with less effort. 2. A novel definition of bandwidth allocation fairness in the presence of multiple resource sharing overlays, and a routing optimization technique to improve fairness and the satisfaction of overlays. Evaluation analyzes the characteristics of different fair allocation algorithms, and suggests that eliminating bottlenecks via custom routing can be an effective way to improve fairness. 3. An optimization solution to minimize the total cost of monitoring an overlay by determining the optimal mix of overlay and native links to monitor, and an analysis of the effect of topological properties on monitoring cost and the composition of the optimal mix of monitored links. We call our approach multi-layer monitoring and show that it is a flexible approach producing minimal-cost solutions with low errors. 4. A study of virtual network embedding in software defined networks (SDNs), identifying the challenges and opportunities for embedding in the SDN environment, and presenting two VN embedding techniques and their evaluation. One objective is to balance the stress on substrate components, and the other is to minimize the delays between VN controllers and switches. Each technique optimizes embedding for one objective while keeping the other within bounds.

The Internet has scaled massively over the past 15 years to extend to billions of users. These users increasingly require extensive applications and capabilities from the Internet, such as Quality of Service (QoS) optimized paths between end hosts. When default Internet paths may not meet their requirements adequately, there is a need to facilitate the discovery of such QoS optimized paths. Fortunately, even though the route offered by the Internet may not work (to the required level of performance), often there exist alternate routes that do work. When the direct Internet path between two Internet hosts for instance is sub-optimal (according to specific user defined criterion), there is a possibility that the direct paths of both to a third host may not be suffering from the same problem owing to path disjointness. Overlay Networks facilitate the discovery of such composite alternate paths through third party hosts. To discover such alternate paths, overlay hosts regularly monitor both Internet path quality and choose better alternate paths via other hosts. Such measurements are costly and pose scalability problems for large overlay networks. This thesis asserts and shows that these overheads could be lowered substantially if the network layer path information between overlay hosts could be obtained, which facilitates selection of disjoint paths. This thesis further demonstrates that obtaining such network layer path information is very challenging. As opposed to the path monitoring which only requires cooperation of overlay hosts, disjoint path selection depends on the accuracy of information about the underlay, which is out of the domain of control of the overlay and so may contain inaccuracies. This thesis investigates how such information could be gleaned at different granularities for optimal tradeoffs between spatial and/or temporal methods for selection of alternate paths. The main contributions of this thesis are: (i) investigation of scalable techniques to facilitate alternate path computation using network layer path information; (ii) a review of the realistic performance gains achievable using such alternate paths; and (iii) investigation of techniques for revealing the presence of incorrect network layer path information, proposal of new techniques for its removal.

The Internet has scaled massively over the past 15 years to extend to billions of users. These users increasingly require extensive applications and capabilities from the Internet, such as Quality of Service (QoS) optimized paths between end hosts. When default Internet paths may not meet their requirements adequately, there is a need to facilitate the discovery of such QoS optimized paths. Fortunately, even though the route offered by the Internet may not work (to the required level of performance), often there exist alternate routes that do work. When the direct Internet path between two Internet hosts for instance is sub-optimal (according to specific user defined criterion), there is a possibility that the direct paths of both to a third host may not be suffering from the same problem owing to path disjointness. Overlay Networks facilitate the discovery of such composite alternate paths through third party hosts. To discover such alternate paths, overlay hosts regularly monitor both Internet path quality and choose better alternate paths via other hosts. Such measurements are costly and pose scalability problems for large overlay networks. This thesis asserts and shows that these overheads could be lowered substantially if the network layer path information between overlay hosts could be obtained, which facilitates selection of disjoint paths. This thesis further demonstrates that obtaining such network layer path information is very challenging. As opposed to the path monitoring which only requires cooperation of overlay hosts, disjoint path selection depends on the accuracy of information about the underlay, which is out of the domain of control of the overlay and so may contain inaccuracies. This thesis investigates how such information could be gleaned at different granularities for optimal tradeoffs between spatial and/or temporal methods for selection of alternate paths. The main contributions of this thesis are: (i) investigation of scalable techniques to facilitate alternate path computation using network layer path information; (ii) a review of the realistic performance gains achievable using such alternate paths; and (iii) investigation of techniques for revealing the presence of incorrect network layer path information, proposal of new techniques for its removal.

Master of Science / Department of Electrical and Computer Engineering / Caterina Scoglio / Overlay networks are application-layer networks that are constructed using the existing Internet infrastructure. Nodes in an overlay network construct logical links toward other nodes to form an overlay topology. Common routing algorithms, such as the link state and distance vector algorithms, are then used to determine how to route data in the overlay network. Previous work has demonstrated that overlay networks can be used to improve routing performance in the Internet. These quality of service improvements make overlay networks attractive for a variety of network applications. Recently, game-theoretic approaches to constructing overlay network topologies have been proposed. In these approaches, nodes establish logical links toward other nodes in a decentralized and selfish manner. Despite the selfish behavior, it has been shown that desirable global network properties emerge. These approaches, however, neglect the traffic-demand between nodes. In this thesis, a game-theoretical approach is presented to constructing overlay network topologies that considers the traffic-demand between nodes. This thesis shows that the traffic-demand between nodes has a significant effect on the topologies formed. Nodes with statistically higher traffic-demand from others become members of the graph center, while nodes that have statistically higher traffic-demand toward others establish logical links toward members of the graph center. This thesis also shows that a traffic-demand aware overlay network topology is better suited to transport the required traffic in the overlay network. Unfortunately, the game-theoretic approach is intractable. In order to construct larger overlay networks, approximate or heuristic approaches are required. In this thesis, a machine learning approach is proposed that characterizes the attributes of neighbor nodes during the construction of the overlay network topology. The approach proposed uses this knowledge and experience to learn a set of human-readable rules. This rule set is then used to decide whether to construct a logical link toward a node. This thesis shows that the machine learning approach results in similar overlay network topologies as the game-theoretic approach. Additionally, it is shown that the machine learning approach is tractable and scales to larger networks.

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.

<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