This paper proposes an isolation layer -- a shim -- betweeninter-domain routing and packet forwarding. The job of this layer isto coordinate between Autonomous Systems (AS's) on when and how tomodify the forwarding state to ensure inter-domain routing loops donot cause forwarding loops. The benefits of a consistency layer aretwofold. First, it prevents the creation of transient inter-domainforwarding loops and the resulting packet loss, high latency, andconnection failures.Second, by taking the burden of forwarding consistency off theinter-domain routing protocol, it enables inter-domain routingprotocols with more complex convergence characteristics than BGP, suchas protocols that optimize route selection based on performance. Weoffer two possible designs for the consistency layer. We prove thatboth designs are free of forwarding loops and show they are easy todeploy in the current Internet.

No description available.

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.

The issue of providing Quality of Service (QoS) in the Internet is becoming more and more important because of two phenomena: (1) the growth of the value added services that require QoS (e.g., VPNs, IPTV) and (2) network convergence towards a unified IP-based architecture, for voice, image and data services. In this context, the limitations of existing QoS technologies emerge: it is currently difficult for an operator to guarantee that its network can offer a specific level of service. Furthermore, it is hard to ensure a consistent treatment of end-to-end QoS-sensitive flow that cross networks controlled by several operators. Indeed, the control on such traffic flows is shared between all the traversed operators. In the thesis, we have studied these issues. Specifically, we have addressed the problems of routing and dynamic traffic engineering at inter-domain level. We have proposed several algorithmic solutions to compute paths subject to multiple performance constraints. Analytical studies and simulations show that our algorithms are efficient and scalable. Finally, we have integrated our solutions into an architecture that is under ongoing standardization by the IETF and we have studied the protocol adaptations required for the deployment of our algorithms. Our work represents an important step towards more effective inter-domain traffic management in traffic engineered networks

Grâce au partenariat avec l'entreprise luxembourgeoise Post Luxembourg, nous avons pu tester différentes méthodes pour mesurer le trafic interdomaine à la bordure de leur réseau avec Internet. Le choix s'est porté sur une technologie existante : Netflow. Avec ces données nous avons pu réaliser diverses analyses afin de comprendre l'évolution du trafic en fonction de différents paramètres comme l'heure de la journée, le jour de la semaine... D'après ces analyses, plusieurs solutions ont été envisagées pour modéliser le trafic. Deux méthodes ont été proposées et testées sur des données réelles : une méthode d'analyse de séries temporelles et une méthode de machine learning reposant sur les processus gaussiens. Ces techniques ont été comparées sur différents systèmes autonomes. Les résultats sont satisfaisants pour les deux méthodes avec un avantage pour la méthode des processus gaussiens. Cette thèse propose le développement d'une solution logicielle ANODE mise en production chez Post Luxembourg et permettant l'analyse de bout en bout du trafic de cœur de réseau : mesure de données, modélisation, prédiction et détection d'anomalies / Inter-domain routing statistics are not usually publicly available but with the partnership with Post Luxembourg, we deployed a network wide measurements of Internet traffic. Those statistics show clear daily and weekly pattern and several points of interest. From all the information gathered, two modelling approach were chosen: the first one from the time series domain and the second one from the machine learning approach. Both were tested on several dataset of autonomous systems and the second one, Gaussian Process, was kept for the next steps. The proposal of this study is the development of a software solution called ANODE, which is used at Post Luxembourg, allowing the analysis of backbone traffic: measurments, modelling, forecasting and anomaly detection