京都大学 / 0048 / 新制・課程博士 / 博士(情報学) / 甲第22809号 / 情博第739号 / 新制||情||126(附属図書館) / 京都大学大学院情報学研究科通信情報システム専攻 / (主査)教授 大木 英司, 教授 守倉 正博, 教授 原田 博司 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

京都大学 / 新制・課程博士 / 博士(情報学) / 甲第23326号 / 情博第762号 / 新制||情||130(附属図書館) / 京都大学大学院情報学研究科通信情報システム専攻 / (主査)教授 大木 英司, 教授 守倉 正博, 教授 岡部 寿男 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

De nos jours les données ainsi que les applications dans le nuage (cloud) connaissent une forte croissance, ce qui pousse les fournisseurs à chercher des solutions garantissant un lien réseau stable et résilient à leurs utilisateurs. Dans cette thèse on étudie les protocoles réseaux et les stratégies de communication dans un environnement de centre de données distribués. On propose une architecture cloud distribuée, centrée sur l’utilisateur et qui a pour but de: (i) migrer des machines virtuelles entre les centres de données avec un temps d’indisponibilité faible; (ii) fournir un accès résilient aux machines virtuelles; (iii) minimiser le délai d'accès au cloud. On a identifié deux problèmes de décision: le problème d'orchestration de machines virtuelles, prenant en compte la mobilité des utilisateurs, et le problème de basculement et de configuration des localisateurs, prenant en compte les états des liens inter- et intra-centre de données. On évalue notre architecture en utilisant une plate-forme de test avec des centres de données distribués géographiquement et en simulant des scenarios basés sur des traces de mobilités réelles. On montre que, grâce à quelques modifications apportées aux protocoles d'overlay, on peut avoir des temps d'indisponibilité très faibles pendant la migration de machines virtuelles entre deux centres de données. Puis on montre qu’en reliant la mobilité des machines virtuelles aux déplacement géographiques des utilisateurs, on peut augmenter le débit de la connexion. De plus, quand l’objectif est de maximiser le débit entre l’utilisateur et sa ressource, on démontre par des simulations que la décision de l'emplacement des machines virtuelles est plus importante que la décision de basculement de point d'entrée du centre de données. Enfin, grâce à un protocole de transport multi-chemins, on montre comment optimiser les performances de notre architecture et comment à partir des solutions de routage intra-centre de données on peut piloter le basculement des localisateurs. / While many business and personal applications are being pushed to the cloud, offering a reliable and a stable network connectivity to cloud-hosted services becomes an important challenge to face in future networks. In this dissertation, we design advanced network protocols, algorithms and communication strategies to cope with this evolution in distributed data center architectures. We propose a user-centric distributed cloud network architecture that is able to: (i) migrate virtual resources between data centers with an optimized service downtime; (ii) offer resilient access to virtual resources; (iii) minimize the cloud access latency. We identify two main decision making problems: the virtual machine orchestration problem, also taking care of user mobility, and the routing locator switching configuration problem, taking care of both extra and intra data center link states. We evaluate our architecture using real test beds of geographically distributed data centers, and we also simulate realistic scenarios based on real mobility traces. We show that migrating virtual machines between data centers at negligible downtime is possible by enhancing overlay protocols. We then demonstrate that by linking cloud virtual resource mobility to user mobility we can get a considerable gain in the transfer rates. We prove by simulations using real traces that the virtual machine placement decision is more important than the routing locator switching decision problem when the goal is to increase the connection throughput: the cloud access performance is primarily affected by the former decision, while the latter decision can be left to intra data center traffic engineering solutions. Finally, we propose solutions to take profit from multipath transport protocols for accelerating cloud access performance in our architecture, and to let link-state intra data center routing fabrics piloting the cloud access routing locator switching.

Nowadays Network Virtualization provides a new perspective for running multiple, relatively independent applications on same physical network (the substrate network) within shared substrate resources. This method is especially useful for researchers or investigators to get involved into networking field within a lower barrier. As for network virtualization, Virtual Network Mapping (VNM) problem is one of the most important aspects for investigation. Within years of deeply research, several efficient algorithms have been proposed to solve the Virtual Network Mapping problem, however, most of the current mapping algorithm assumes that the virtual network request topology is known or given by customers, in this thesis, a new VNM assumption based on traffic matrix is proposed, also using existing VNM benchmarks, we evaluated the mapping performance based on various metrics, and by comparing the new traffic matrix based VNM algorithm and existing ones, we provide its advantages and shortcomings and optimization to this new VNM algorithm.

Network virtualization promises to play a dominant role in shaping the future Internet by overcoming the Internet ossification problem. Since a single protocol stack cannot accommodate the requirements of diverse application scenarios and network paradigms, it is evident that multiple networks should co-exist on the same network infrastructure. Network virtualization supports this feature by hosting multiple, diverse protocol suites on a shared network infrastructure. Each hosted virtual network instance can dynamically instantiate custom set of protocols and functionalities on the allocated resources (e.g., link bandwidth, CPU, memory) from the network substrate. As this technology matures, it is important to consider the security issues and develop efficient defense mechanisms against potential vulnerabilities in the network architecture. The architectural separation of network entities (i.e., network infrastructures, hosted virtual networks, and end-users) introduce set of attacks that are to some extent different from what can be observed in the current Internet. Each entity is driven by different objectives and hence it cannot be assumed that they always cooperate to ensure all aspects of the network operate correctly and securely. Instead, the network entities may behave in a non-cooperative or malicious way to gain benefits. This work proposes set of defense mechanisms that addresses the following challenges: 1) How can the network virtualization architecture ensure anonymity and user privacy (i.e., confidential packet forwarding functionality) when virtual networks are hosted on third-party network infrastructures?, and 2) With the introduction of flexibility in customizing the virtual network and the need for intrinsic security guarantees, can there be a virtual network instance that effectively prevents unauthorized network access by curbing the attack traffic close to the source and ensure only authorized traffic is transmitted?. To address the above challenges, this dissertation proposes multiple defense mechanisms. In a typical virtualized network, the network infrastructure and the virtual network are managed by different administrative entities that may not trust each other, raising the concern that any honest-but-curious network infrastructure provider may snoop on traffic sent by the hosted virtual networks. In such a scenario, the virtual network might hesitate to disclose operational information (e.g., source and destination addresses of network traffic, routing information, etc.) to the infrastructure provider. However, the network infrastructure does need sufficient information to perform packet forwarding. We present Encrypted IP (EncrIP), a protocol for encrypting IP addresses that hides information about the virtual network while still allowing packet forwarding with longest-prefix matching techniques that are implemented in commodity routers. Using probabilistic encryption, EncrIP can avoid that an observer can identify what traffic belongs to the same source-destination pairs. Our evaluation results show that EncrIP requires only a few MB of memory on the gateways where traffic enters and leaves the network infrastructure. In our prototype implementation of EncrIP on GENI, which uses standard IP header, the success probability of a statistical inference attack to identify packets belonging to the same session is less than 0.001%. Therefore, we believe EncrIP presents a practical solution for protecting privacy in virtualized networks. While virtualizing the infrastructure components introduces flexibility by reprogramming the protocol stack, it doesn't directly solve the security issues that are encountered in the current Internet. On the contrary, the architecture increases the chances of additive vulnerabilities, thereby increasing the attack space to exploit and launch several attacks. Therefore it is important to consider a virtual network instance that ensures only authorized traffic is transmitted and attack traffic is squelched as close to their source as possible. Network virtualization provides an opportunity to host a network that can guarantee such high-levels of security features thereby protecting both the end systems and the network infrastructure components (i.e., routers, switches, etc.). In this work, we introduce a virtual network instance using capabilities-based network which present a fundamental shift in the security design of network architectures. Instead of permitting the transmission of packets from any source to any destination, routers deny forwarding by default. For a successful transmission, packets need to positively identify themselves and their permissions to each router in the forwarding path. The proposed capabilities-based system uses packet credentials based on Bloom filters. This high-performance design of capabilities makes it feasible that traffic is verified on every router in the network and most attack traffic can be contained within a single hop. Our experimental evaluation confirm that less than one percent of attack traffic passes the first hop and the performance overhead can be as low as 6% for large file transfers. Next, to identify packet forwarding misbehaviors in network virtualization, a controller-based misbehavior detection system is discussed as part of the future work. Overall, this dissertation introduces novel security mechanisms that can be instantiated as inherent security features in the network architecture for the future Internet. The technical challenges in this dissertation involves solving problems from computer networking, network security, principles of protocol design, probability and random processes, and algorithms.

Diversity is a widely existing and much desired property in many networking systems. This dissertation studies diversity problems in Internet, which is the largest computer networking system in the world. The motivations of diversifying the Internet are two-fold. First, diversifying the Internet improves the Internet routing robustness and reliability. Most problems we have encountered in our daily use of Internet, such as service interruptions and service quality degradation, are rooted in the inter-domain routing system of Internet. Inter-domain routing is policy-based routing, where policies are often based on commercial agreements between ASes. Although people know how to safely accommodate a few commercial agreements in inter-domain routing, for a large set of diverse commercial agreements, it is not clear yet what policy guidelines can accommodate them and guarantee convergence. Accommodating diverse commercial agreements not only is needed for ASes in Internet to achieve their business goals, it also provides more path diversity in inter-domain routing, which potentially benefits the inter-domain routing system. However, more reliable and robust routing cannot be achieve unless the routing system exploits the path diversity well. However, that is not the case for the current inter-domain routing system. There exist many paths in the underlying network, but the routing system cannot find those paths promptly. Although many schemes have been proposed to address the routing reliability problem, they often add significant more complexity into the system. The need for a more reliable inter-domain routing system without adding too much complexity calls for designing practical schemes to better exploit Internet path diversity and provide more reliable routing service. The increasing demands of providing value-added services in Internet also motivates the research work in this dissertation. Recently, network virtualization substrates and data centers are becoming important infrastructures. Network virtualization provides the ability to run multiple concurrent virtual networks in the same shared substrate. To better facilitate building application-specific networks so as to test and deploy network innovations for future Internet, a network virtualization platform must provide both high-degree of flexibility and high-speed packet forwarding in virtual networks. However, flexibility and forwarding performance are often tightly coupled issues in system design. Usually we have to sacrifice one in order to improve the other one. The lack of a platform that has both flexibility and good forwarding performance motivates the research in this dissertation to design network virtualization platforms to better support virtual networks with diverse functionalities in future Internet. The popularity of data centers in Internet also motivates this dissertation to studying scalable and cost-efficient data center networks. Data centers with a cluster of servers are already common places in Internet to host large scale networking applications, which require huge amount of computation and storage resources. To keep up with the performance requirements of those applications, a data center has to accommodate a large number of servers. As Internet evolves and more diverse applications emerge, the computation and storage requirements for data centers grow quickly. However, using the conventional interconnection structure is hard to scale the number of servers in data centers. Hence, it is of importance to design new interconnection structures for future data centers in Internet. Four interesting topics are explored in this dissertation: (i) accommodating diverse commercial agreements in inter-domain routing, (ii) exploiting the Internet AS-level path diversity, (iii) supporting diverse network data planes, and (iv) diverse interconnection networks for data centers. The first part of this dissertation explores accommodating diverse commercial agreements in inter-domain routing while guaranteeing global routing convergence, so as to provide more path diversity in Internet. The second part of this dissertation studies exploiting the path diversity in Internet by running multiple routing processes in parallel, which compute multiple paths and those paths can complement each other in case one path has problems when dynamics present in the routing system. The third part of this dissertation studies supporting concurrent networks with heterogeneous data plane functions via network virtualization. Two virtual network platforms are presented, which achieve both high-speed packet forwarding in each virtual network and high degree of flexibility for each virtual network to customize its data plane functions. The last part of this dissertation presents a new scalable interconnection structure for data center networks. The salient feature of this new interconnection structure is that it expands to any number of servers without requiring to physically upgrading the existing servers.

Wireless network virtualization is a promising avenue of research for next-generation 5G cellular networks. This work investigates the problem of selecting base stations to construct virtual networks for a set of service providers, and adaptive slicing of the resources between the service providers to satisfy service provider demands. A two-stage stochastic optimization framework is introduced to solve this problem, and two methods are presented for approximating the stochastic model. The first method uses a sampling approach applied to the deterministic equivalent program of the stochastic model. The second method uses a genetic algorithm for base station selection and adaptively slicing via a single-stage linear optimization problem. A number of scenarios are simulated using a log-normal model designed to emulate demand from real world cellular networks. Simulations indicate that the first approach can provide a reasonably tight solution, but is constrained as the time expense grows exponentially with the number of parameters. The second approach provides a significant improvement in run time with the introduction of marginal error. / Master of Science / 5G, the next generation cellular network standard, promises to provide significant improvements over current generation standards. For 5G to be successful, this must be accompanied by similarly significant efficiency improvements. Wireless network virtualization is a promising technology that has been shown to improve the cost efficiency of current generation cellular networks. By abstracting the physical resource—such as cell tower base stations— from the use of the resource, virtual resources are formed. This work investigates the problem of selecting virtual resources (e.g., base stations) to construct virtual wireless networks with minimal cost and slicing the selected resources to individual networks to optimally satisfy individual network demands. This problem is framed in a stochastic optimization framework and two approaches are presented for approximation. The first approach converts the framework into a deterministic equivalent and reduces it to a tractable form. The second approach uses a genetic algorithm to approximate resource selection. Approaches are simulated and evaluated utilizing a demand model constructed to emulate the statistics of an observed real world urban network. Simulations indicate that the first approach can provide a reasonably tight solution with significant time expense, and that the second approach provides a solution in significantly less time with the introduction of marginal error.

A tecnologia de virtualização de redes é um novo paradigma de redes que permite a múltiplas redes virtuais (VNs) compartilharem de uma forma eficiente e eficaz a mesma rede de infraestrutura denominada rede de substrato (SN). A implementação e o desenvolvimento de novos protocolos, testes de novas soluções e arquiteturas para a Internet atual e do futuro podem ser tratadas por meio da virtualização de redes. Com a virtualização de redes surge um desafio denominado problema VNE. O problema de virtualização de redes embutidas (VNE) consiste em realizar o mapeamento dos nós virtuais e o mapeamento dos enlaces virtuais sobre uma rede de substrato (SN). O problema é conhecido como NP-Hard e a sua solução é realizada por meio de algoritmos heurísticos e aproximados que realizam o mapeamento de nós e enlaces virtuais em dois estágios de forma independente ou coordenada. A presente tese tem o objetivo de resolver o mapeamento dos enlaces virtuais do problema VNE com a utilização da álgebra de caminhos. A solução apresentada fornece o melhor desempenho quando comparada com as demais soluções de virtualização de redes encontradas na literatura. Os resultados obtidos nas simulações para o problema VNE foram avaliados e analisados com a utilização do algoritmo desenvolvido nesta tese denominado Path Algebra for Virtual Link Mapping (PAViLiM), que utiliza a álgebra de caminhos para realizar o mapeamento de enlaces virtuais para caminhos na rede de substrato. A álgebra de caminhos é poderosa e flexível. Tal flexibilidade permite que ocorra uma exploração detalhada do espaço de soluções e a identificação do melhor critério e política que devem ser utilizados para a virtualização de redes. / The network virtualization technology is a new paradigm of network that allows multiple virtual networks (VNs) share in an efficient and effective way the same network infrastructure called substrate network (SN). The implementation and the development of new protocols, testing of new solutions and architectures for current and future Internet can be addressed through network virtualization. With the network virtualization arises a challenge called VNE problem. The problem of virtual network embedded (VNE) is to conduct the mapping of the virtual nodes and mapping of the virtual links over a substrate network (SN).The problem is known as NP-Hard and its solution is accomplished by means of approximate and heuristic algorithms that perform the mapping of virtual nodes and links in two stages independently or coordinated. This thesis aims to solve the mapping of virtual links for VNE problem using the paths algebra. The solution presented provides the best performance when compared with other networks virtualization solutions from the literature. The results of simulation for the VNE problem were evaluated and analyzed using the algorithm developed in this thesis called Path Algebra for Virtual Link Mapping (PAViLiM), which uses the paths algebra to perform the mapping of virtual links to paths in substrate network. The paths algebra is powerful and flexible. This flexibility allows the occurrence of a detailed exploration for identifying the best solutions and political criteria to be used for network virtualization.

Bien qu'Internet soit considéré comme le grand succès de ces dernières années, il est devenu une infrastructure critique à cause de l'absence de changements dans le réseau cœur et de la rigidité des équipements déployés. La mise en place et le déploiement des nouveaux services réseau sont devenus difficiles et coûteux. La virtualisation des réseaux a été présentée comme un nouveau paradigme pour palier aux problèmes de l’architecture actuelle de l'Internet. Dans ce travail de thèse, nous présentons la virtualisation des réseaux et les réseaux définis par logiciels (SDN) comme solution avec laquelle les fournisseurs de services peuvent offrir, au travers des réseaux virtuels (VN), des nouveaux services aux utilisateurs avec une meilleure qualité de service, tout en optimisant l'utilisation des ressources réseaux physiques. La première contribution consiste à démontrer le potentiel de SDN dans la gestion de la QoS dans le contexte d’un réseau domestique virtualisé. Nous proposons et implémentons le mécanisme ''FlowQoS'' qui peut être déployé par un fournisseur d’accès Internet au niveau de la boucle locale ou bien dans la passerelle domestique. Les mesures des performances montrent que cette solution permet de partager la bande passante entre plusieurs applications selon la configuration définie par l’utilisateur pour garantir la QoS pour chaque trafic actif. La seconde contribution est une modélisation, par la théorie des jeux, de l’interaction entre les fournisseurs de services et les fournisseurs de l’infrastructure pour le partage dynamique de l’infrastructure physique entre plusieurs VN avec différents besoins en QoS. Il s'agit d'un ensemble de jeux non-coopératifs pour modéliser la phase de négociation et celle de l’allocation dynamique des nœuds et des liens physiques pour chaque VN déployé. La troisième contribution porte sur une approche prédictive qui permet d’offrir un contrôle adaptatif de l’allocation de bande passante dans le but de réduire les délais des paquets d'un VN sur chaque lien physique. Ces deux dernières contributions offrent des modèles de partage dynamique des ressources d’une infrastructure physique tout en garantissant la QoS pour chaque VN / Internet has been successful in the recent years. The critical infrastructure of the internet has become stagnant due to the absence of changes in the core networks and stiffness of deployed equipment. It has become difficult and expensive to deploy new network services. Network virtualization is a new paradigm to overcome this problem. In this thesis, we present network virtualization and Software Defined Networking (SDN) as a solution that can be used by service providers. It enables them to provide new services to users through virtual networks (VNs) with better quality of service while optimizing the use of physical network resources. Firstly, we demonstrate the potential of SDN in the QoS management ofa virtualized home network (VN). We propose and implement ''FlowQoS'', a mechanism that can be deployed by an Internet Service Provider in the last-mile hop or in the home gateway. Performance measurements show that this solution can share bandwidth between applications according to user-defined configuration to guarantee QoS for each active traffic. The second contribution is modeling the interaction between service providers and infrastructure providers using game theoretic framework to offer dynamic sharing of physical infrastructure across multiple VN with different QoS requirements. We present a set of non-cooperative games to model the negotiation phase and the dynamic allocation of nodes and physical links for each deployed VN. Finally we focus on a predictive approach that allows an adaptive control of bandwidth allocation in order to reduce the packet delays for a given VN on each physical link. The last two contributions offer dynamic sharing models of physical infrastructure resources while guaranteeing the QoS for each VN

A tecnologia de virtualização de redes é um novo paradigma de redes que permite a múltiplas redes virtuais (VNs) compartilharem de uma forma eficiente e eficaz a mesma rede de infraestrutura denominada rede de substrato (SN). A implementação e o desenvolvimento de novos protocolos, testes de novas soluções e arquiteturas para a Internet atual e do futuro podem ser tratadas por meio da virtualização de redes. Com a virtualização de redes surge um desafio denominado problema VNE. O problema de virtualização de redes embutidas (VNE) consiste em realizar o mapeamento dos nós virtuais e o mapeamento dos enlaces virtuais sobre uma rede de substrato (SN). O problema é conhecido como NP-Hard e a sua solução é realizada por meio de algoritmos heurísticos e aproximados que realizam o mapeamento de nós e enlaces virtuais em dois estágios de forma independente ou coordenada. A presente tese tem o objetivo de resolver o mapeamento dos enlaces virtuais do problema VNE com a utilização da álgebra de caminhos. A solução apresentada fornece o melhor desempenho quando comparada com as demais soluções de virtualização de redes encontradas na literatura. Os resultados obtidos nas simulações para o problema VNE foram avaliados e analisados com a utilização do algoritmo desenvolvido nesta tese denominado Path Algebra for Virtual Link Mapping (PAViLiM), que utiliza a álgebra de caminhos para realizar o mapeamento de enlaces virtuais para caminhos na rede de substrato. A álgebra de caminhos é poderosa e flexível. Tal flexibilidade permite que ocorra uma exploração detalhada do espaço de soluções e a identificação do melhor critério e política que devem ser utilizados para a virtualização de redes. / The network virtualization technology is a new paradigm of network that allows multiple virtual networks (VNs) share in an efficient and effective way the same network infrastructure called substrate network (SN). The implementation and the development of new protocols, testing of new solutions and architectures for current and future Internet can be addressed through network virtualization. With the network virtualization arises a challenge called VNE problem. The problem of virtual network embedded (VNE) is to conduct the mapping of the virtual nodes and mapping of the virtual links over a substrate network (SN).The problem is known as NP-Hard and its solution is accomplished by means of approximate and heuristic algorithms that perform the mapping of virtual nodes and links in two stages independently or coordinated. This thesis aims to solve the mapping of virtual links for VNE problem using the paths algebra. The solution presented provides the best performance when compared with other networks virtualization solutions from the literature. The results of simulation for the VNE problem were evaluated and analyzed using the algorithm developed in this thesis called Path Algebra for Virtual Link Mapping (PAViLiM), which uses the paths algebra to perform the mapping of virtual links to paths in substrate network. The paths algebra is powerful and flexible. This flexibility allows the occurrence of a detailed exploration for identifying the best solutions and political criteria to be used for network virtualization.