Abstract

We compare and evaluate how well-known and novel networkwide objective functions for Traffic Engineering (TE) algorithms fulfil TE requirements. To compare the objective functions we model the TE problem as a linear program and solve it to optimality, thus finding for each objective function the best possible target of any heuristic TE algorithm. We show that all the objective functions are not equivalent and some are far better than others. Considering the preferences a network operator may have, we show which objective functions are adequate or not. Peer reviewed

Abstract

Multi-Protocol Label Switching (MPLS) provides ways to control the Label Switched Paths (LSPs) followed by traffic trunks in a network and thereby to better traffic engineer it. In this context, we look at the problem of organizing the mapping of LSPs in an optimal way throughout the network on the basis of a given objective function. This problem is highly combinatorial and makes dynamic and real-time features a difficult issue for any LSP routing scheme. For this reason, we propose a computationally efficient, though approximate, on-line scheme adapted to an incremental optimization of the network state. It is then applied to a seldom mentioned traffic engineering problem: the compromise between load-balancing and traffic minimization. It is expected that clever routing strategies to balance the network load will sometimes favor longer paths in order to avoid congestion, leading to an increase of the overall network utilization. This reasoning is confirmed by our study, and we show that an improvement in network management can be made by appropriately tuning this compromise. Peer reviewed

Abstract

In order to accommodate fluctuations in network conditions, adaptive applications need to obtain information about resource availability, Using active networks, new models for adaptive applications can be envisaged, which can benefit from the possibility to send mobile code to the network nodes. We describe a model for trading resources inside an active net-work node, based on the interaction between capsules as reactive user agents, and resource manager agents which reside in the network nodes. We apply the model to the case of a many-to-one audio application with congestion control, which trades off link resources against memory when there is congestion at the outgoing interface towards the destination. Our simulation results indicate that the application makes effective use of the available resources, and it also allows resources to be shared according to user preferences. Peer reviewed

Abstract

The Internet is a wide network of computers in constant evolution. Each year, more and more organizations are connected to this worldwide network. Each of them has its own structure and administration that are not publicly revealed for economical, political, and security reasons. Consequently, our perception of the Internet structure, and more specifically, its topology, is incomplete. In order to balance this lack of knowledge, the research community relies on network measurements. Most of the time, they are performed based on the well-known tool traceroute. However, in practice, an operator may privilege other technologies than IP to forward packets inside its network. MultiProtocol Label Switching (MPLS) is one them. Even if it is heavily deployed by operators, it has not been really investigated by researchers. Prior to this thesis, only two studies focused on the identification of MPLS tunnels in traceroute data. Moreover, while one of them does not take all possible scenarios into account, the other lack of precision in some of its models. In addition, MPLS tunnels may hide their content to traceroute. Topologies inferred from such data may thus contain false links or nodes with an artificially high degree, leading so to biases in standard graph metrics used to model the network. Even if some researchers already tried to tackle this issue, the revelation of hidden MPLS devices in traceroute data is still an open question. This thesis aims at characterizing MPLS in two different ways. On the one hand, at an architectural level, we will analyze in detail its deployment and use in both IPv4 and IPv6 networks in order to improve its state-of-the-art view. We will show that, in practice, more than one IPv4 trace out of two crosses at least one MPLS tunnel. We will also see that, even if this protocol can simplify the internal architecture of transit networks, it also allows some operators to perform traffic engineering in their domain. On the other hand, MPLS will be studied from a measurement point of view. We will see that routers from different manufacturers may have distinct default behaviors regarding to MPLS, and that these specific behaviors can be exploited to identify MPLS tunnels during traceroute measurements. More precisely, we will focus on new methods able to infer the presence of tunnels that are invisible in traceroute outputs, as well as on mechanisms to reveal their content. We will also show that they can be used in order to improve the inference of Internet graph properties, such as path lengths and node degrees. Finally, these techniques will be integrated into Trace the Naughty Tunnels (TNT), a traceroute extension able to identify all types of MPLS tunnels along a path towards a destination. We will prove that this tool can be used in order to get a detailed quantification of MPLS tunnels in the worldwide network. TNT is publicly available, and can therefore be part of many future studies conducted by the research community. Internet est un immense réseau informatique en constante évolution. Chaque année, de plus en plus d’organisations s’y connectent. Chacune d’elles est gérée et administrée indépendamment des autres. En pratique, l’architecture interne de leur réseau n’est pas rendue publique pour des raisons politiques, économiques, ou de sécurité. Par conséquent, notre perception de la structure d’Internet, et plus particulièrement de sa topologie, est incomplète. Afin de pallier ce manque de connaissance, la communauté de la recherche s’appuie sur des mesures de réseau. La plupart du temps, elles sont réalisées avec l’outil traceroute. Cependant, des technologies autres que IP peuvent être privilégiées pour transférer les paquets dans un réseau. MultiProtocol Label Switching (MPLS) est l’une d’entre elles. Même si cette technologie est largement déployée dans Internet, elle n’est pas bien étudiée par les chercheurs. Avant cette thèse, seulement deux travaux se sont intéressés à l’identification d’MPLS dans les données collectées avec traceroute. Alors que le premier ne prend pas en compte tous les scénarios possibles, le second propose des modèles qui manquent de précision. De plus, les tunnels MPLS peuvent dissimuler leur contenu à traceroute. Les topologies inférées sur base de ces données peuvent donc contenir de faux liens, ou des noeuds avec un degré anormalement élevé. Les différentes modélisations d’Internet qui en résultent peuvent alors être biaisées. Aujourd’hui, la question de la révélation des routeurs MPLS qui sont invisibles dans les données de mesure n’est toujours pas résolue, même si certains chercheurs ont déjà proposé quelques méthodes pour y parvenir. Cette thèse a pour but de caractériser MPLS de deux manières différentes. Dans un premier temps, au niveau architectural, nous analyserons en détail son déploiement et son utilisation dans les réseaux IPv4 et IPv6 afin d’améliorer l’état de l’art. Nous montrerons qu’en pratique, plus d’une trace IPv4 sur deux traverse au moins un tunnel MPLS. Nous découvrirons également que bien que ce protocole peut être utilisé pour simplifier l’architecture interne des réseaux de transit, il peut aussi être déployé pour la mise en place de solutions d’ingénierie de trafic. Dans un second temps, MPLS sera étudié d’un point de vue mesure. Nous verrons que les comportements par défaut liés au protocole varient d’un fabricant de routeur à l’autre, et qu’ils peuvent être exploités afin d’identifier les tunnels MPLS dans les données traceroute. Plus précisément, nous découvrirons de nouvelles méthodes capables d’inférer la présence de tunnels invisibles avec traceroute, ainsi que de nouvelles techniques pour révéler leur contenu. Nous montrerons également qu’elles peuvent être utilisées afin d’améliorer la modélisation d’Internet. Pour terminer, ces techniques seront intégrées à Trace the Naughty Tunnels (TNT), une extension de traceroute qui permet d’identifier tous les types de tunnels MPLS le long du chemin vers une destination. Nous prouverons que cet outil peut être utilisé pour obtenir des statistiques détaillées sur le déploiement d’MPLS sur Internet. TNT est disponible publiquement, et peut donc être librement exploité par la communauté de la recherche pour de multiples futures études.

Abstract

Software-Defined Networking (SDN) provides network administrators opportunities to control network devices more simply and easily than in traditional networking. However, heterogeneity in switch hardware, especially in forwarding pipeline architecture, renders the task of network application developers and network administrators tedious, by hampering portability across switch models. In this paper, we propose FlowConvertor, an algorithm capable of converting rules from any forwarding pipeline to any other different forwarding pipeline, as long as both pipelines offer compatible operations. More precisely, FlowConvertor is an online algorithm that operates on flow updates issued to the origin pipeline and computes the corresponding updates for the target pipeline in real time. Performance evaluation shows that the latency introduced by FlowConvertor on the path between the SDN controller and the target switch is of the order of 1ms in most cases, and is thus acceptable for practical deployment.

Abstract

The emergence of electric vehicles (EVs), combined with the rise of renewable energy production capacities, will strongly impact the way electricity is produced, distributed and consumed in the very near future. This position paper focuses on the problem of optimizing charging strategies for a fleet of EVs in the context where a significant amount of electricity is generated by (distributed) renewable energy. It exposes how a mobile application may offer an efficient solution for addressing this problem. This app can play two main roles. Firstly, it would incite and help people to play a more active role in the energy sector by allowing photovoltaic (PV) panel owners to sell their electrical production directly to consumers, here the EVs’ agents. Secondly, it would help distribution system operators (DSOs) or transmission system operators (TSOs) to modulate more efficiently the load by allowing them to influence EV charging behaviour in real time. Finally, the present paper advocates for the introduction of a two-sided market-type model between EV drivers and electricity producers. Peer reviewed

Abstract

Since the late 90’s, the Internet topology discovery has been an attractive and important research topic, leading, among others, to multiple probing and data analysis tools developed by the research community. This paper looks at the particular problem of discovering subnets (i.e., a set of devices that are located on the same connection medium and that can communicate directly with each other at the link layer). In this paper, we first show that the use of traffic engineering policies may increase the difficulty of subnet inference. We carefully characterize those difficulties and quantify their prevalence in the wild. Next, we introduce WISE (Wide and lInear Subnet inferencE), a novel tool for subnet inference designed to deal with those issues and able to discover subnets on wide ranges of IP addresses in a linear time. Using two groundtruth networks, we demonstrate that WISE performs better than state-of-the-art tools while being competitive in terms of subnet accuracy. We also show, through large-scale measurements, that the selection of vantage point with WISE does not matter in terms of subnet accuracy. Finally, all our code (WISE, data processing, results plotting) and collected data are freely available. Peer reviewed

Abstract

We compare and evaluate how well-known and novel network-wide objective functions for Traffic Engineering (TE) algorithms fulfil TE requirements. To compare the objective functions we model the TE problem as a linear program and solve it to optimality, thus finding for each objective function the best possible target of any heuristic TE algorithm. Our first results on the GEANT network suggest that they can give quite different results.

Abstract

The Routing Research Group (RRG) of the Internet Research Task Force (IRTF) is currently discussing several architectural solutions to build an interdomain routing architecture that scales better than the existing one. The solutions family currently being discussed concerns the addresses separation into locators and identifiers, LISP being one of them. Such a separation provides opportunities in terms of traffic engineering. In this paper, we propose an open and flexible solution that allows an ISP using identifier/locator separation to engineer its interdomain traffic. Our solution relies on the utilization of a service that transparently ranks paths using cost functions. We implement a prototype server and demonstrate its benefits in a LISP testbed. Peer reviewed

Abstract

In this paper we propose a new method to approach optimal Traffic Engineering routing. The method consists of dividing the traffic matrix into $N$ sub-matrices, called strata, and route each of these independently. We propose two different implementations of our method in routers. Our method can also be used to compute a very precise approximation of the optimal value of a given objective function for comparison to heuristic Traffic Engineering algorithms. For this application, our algorithm is very efficient on large topologies compared to an LP formulation. Peer reviewed