Source Routing, currently facilitated by Segment Routing (SR), enables routers to add forwarding instructions to the packet to follow a particular path that deviates from the typical IGP path. These instructions form a list of detours (called segments). However, the number of segments that can be imposed at line-rate is tightly constrained by the hardware. Hence, the main challenge consists in incorporating this constraint into a path computation algorithm. The goal is to be able to solve many existing problems, including finding multi-constrained paths and re-routing packets after a failure, in a way that is deployeable in existing networks using Segment Routing. Existing solutions either lack generality, correctness, optimality, or practical computing efficiency – in particular for sparse realistic networks. In this paper, we address all such challenges with GOFOR-SR. Our framework extends usual path computation algorithms by integrating the SR constraint within the path computation itself and modifying the distance comparison method. GOFOR allows algorithm with various optimization objectives to efficiently compute optimal segment lists. Despite the loss of substructure optimality induced by SR, GOFOR proves particularly efficient, inducing only a linear overhead at worst. It also offers different strategies and path diversity options for intricate load-balancing. We formally prove the correctness and optimality of GOFOR, implement our framework for various practical use-cases, and demonstrate its performance and benefits on both real and challenging topologies.

Companies like Netflix increasingly use the cloud to deploy their business processes. Those processes often involve partnerships with other companies, and can be modeled as workflows. This shift towards the cloud environment has led to more and more data leaks and breaches, resulting in huge losses of money for businesses like the movie industry, as well as a loss of user privacy for businesses dealing with user data like the pharmaceutical industry.In this paper, we show how those workflows can be enforced while preventing data exposure. Following the principles of zero-trust, we develop an infrastructure using the isolation provided by a microservice architecture, to enforce owner policy. We show that our infrastructure is resilient to the set of attacks considered in our security model. We implement a simple, yet realistic, workflow with our infrastructure in a publicly available proof of concept. We then verify that the specified policy is correctly enforced by testing the deployment for policy violations, and estimate the overhead cost of authorization.

Companies like Netflix increasingly use the cloud to deploy their business processes. Those processes often involve partnerships with other companies, and can be modeled as workflows where the owner of the data at risk interacts with contractors to realize a sequence of tasks on the data to be secured.In practice, access control is an essential building block to deploy these secured workflows. This component is generally managed by administrators using high-level policies meant to represent the requirements and restrictions put on the workflow. Handling access control with a high-level scheme comes with the benefit of separating the problem of specification, i.e. defining the desired behavior of the system, from the problem of implementation, i.e. enforcing this desired behavior. However, translating such high-level policies into a deployed implementation can be error-prone.Even though semi-automatic and automatic tools have been proposed to assist this translation, policy verification remains highly challenging in practice. In this paper, our aim is to define and propose structures assisting the checking and correction of potential errors introduced on the ground due to a faulty translation or corrupted deployments. In particular, we investigate structures with formal foundations able to naturally model policies. Metagraphs, a generalized graph theoretic structure, fulfill those requirements: their usage enables to compare high-level policies to their implementation. In practice, we consider Rego, a language used by companies like Netflix and Plex for their release process, as a valuable representative of most common policy languages. We propose a suite of tools transforming and checking policies as metagraphs, and use them in a global framework to show how policy verification can be achieved with such structures. Finally, we evaluate the performance of our verification method.

Interactions between the intra- and inter-domain routing protocols received little attention despite playing an important role in forwarding transit traffic. More precisely, by default, IGP distances are taken into account by BGP to select the closest exit gateway for the transit traffic (hot-potato routing). Upon an IGP update, the new best gateway may change and should be updated through the (full) re-convergence of BGP, causing superfluous BGP processing and updates in many cases. We propose OPTIC (Optimal Protection Technique for Inter-intra domain Convergence), an efficient way to assemble both protocols without losing the hot-potato property. OPTIC pre-computes sets of gateways (BGP next-hops) shared by groups of prefixes. Such sets are guaranteed to contain the post-convergence gateway after any single IGP event for the grouped prefixes. The new optimal exits can be found through a single walk-through of each set, allowing the transit traffic to benefit from optimal BGP routes almost as soon as the IGP converges. Compared to vanilla BGP, OPTIC's structures allow it to consider a reduced number of entries: this number can be reduced by 99% for stub networks. The update of OPTIC's structures, which is not required as long as border routers remain at least bi-connected, scales linearly in time with its number of groups.

Many IoT applications rely on data streams, flowing from producers to consumers. Typically, Named Data Networking has been designed to manipulate directly data chunks, and is particularly relevant in IoT networks. However, in multi-tenant networks, privacy is a major concern, and producers may refuse to share the personal data they generate with non trusted stakeholders. To guarantee k-anonymity, producers can require their data to be aggregated with the one of other producers. We propose here a routing scheme based on aggregation, relying on a pub-sub approach. By appropriately constructing and querying the set of offers, i.e. the list of data streams that are collected, aggregated and transformed together, our routing aggregation scheme provides a privacy aware large-scale interconnection, where the consumer does not access directly to individual measurements. Our performance evaluation highlights the flexibility of our solution to accommodate a large set of queries, while still respecting privacy.

Smart Cities rely on a broad variety of services generating an heterogeneous traffic load, and having diverse privacy and performance requirements. In this paper, we focus on mobility services for an Intelligent Transportation System (ITS), where several applications inter-operate by sharing information. In particular, we consider three main services: ride-hailing, smart parkings and traffic regulation. To investigate the load generated by these mobility services, we rely on two real datasets. Our goal is to study whether a given technology can scale with realistic conditions related to the envisioned smart mobility scenario. In particular, we analyze here how many LoRa gateways are necessary and how they should be deployed to support these mobility services. We highlight the bottlenecks occurring in most dense areas of the network and argue that heterogeneous deployments can efficiently handle such hot spots.

The full Internet feed, reaching ~867K prefixes as of March 2021, has been growing at ≈50K prefixes/year over the last 10 years. To counterbalance this sustained increase, Autonomous Systems (ASes) may filter prefixes, perform prefix aggregation and use default routes. Despite being effective, such workarounds may result in routing inconsistencies, i.e., in routers along a forwarding route mapping the same IP addresses to different IP prefixes. In turn, the exit AS border routers associated with these distinct prefixes may potentially differ. For some prefixes, forwarding detours (FDs) may occur, i.e., traffic may deviate from best IGP paths. In this work we investigate the phenomenon of FDs and derive a methodology to detect them. In particular, our tool is able to pinpoint cases where multiple prefixes are subject to FDs. We run measurements from 100 vantage points of the NLNOG RING monitoring infrastructure and find FDs in 25 out of 54 ASes. We see that FDs are heterogeneous, i.e., the number of prefixes and AS border routers in between which we detect FDs strongly depend on the studied AS. Finally, we discover a remarkable binary effect such that either all transit traffic traversing between two border routers of an AS detours, or none does.

The Internet of Things (IoT) is expected to integrate a large number of sensors, and actuators to the Internet. Multiple concurrent applications may cohabit on top of the same IoT infrastructure, and may re-use the same data for various purpose. However, privacy represents a major concern for many IoT applications, such as in smart building and healthcare. We propose here a multi-domain IoT framework where each domain aggregates distinct data-streams to respect their privacy concerns. We argue that removing sensitive meta-data and aggregating values reported by each data-stream is sufficient to hide individual private measurements. Moreover, relying on the Named Data Networking (NDN) paradigm, we can exploit caching strategies and perform in-network processing to ensure both scalability and privacy. In this paper, we discuss the necessary mechanisms to design a scalable inter-domain, privacy aware NDN scheme.

The Internet of Things (IoT) interconnects a large collection of low power devices to the Internet. Instead of relying on the usual approach where IoT devices push their data to a cloud, we envision a decentralized approach, where multiple IoT domains cooperate to exchange data safely. As privacy is critical regarding IoT data, each domain should define what it accepts to export. We propose to create a multi-domain overlay of border routers, defining their own privacy constraints. Border routers export their available data streams and policies to their peering domains. Such policies define how streams should be aggregated and transformed to be compliant with the privacy requirements. We take advantage of the Named Data Networking (NDN) architecture to enable data re-usability and in-network transformations. Our evaluation highlights the scalability of our approach: NDN content stores supporting data aggregation and transformation reduce both the network and the cache load while enforcing privacy natively.

With the growth of demands for quasi-instantaneous communication services such as real-time video streaming, cloud gaming, and industry 4.0 applications, multi-constraint Traffic Engineering (TE) becomes increasingly important. While legacy TE management planes have proven laborious to deploy, Segment Routing (SR) drastically eases the deployment of TE paths and thus became the most appropriate technology for many operators. The flexibility of SR sparked demands in ways to compute more elaborate paths. In particular, there exists a clear need in computing and deploying Delay-Constrained Least-Cost paths (DCLC) for real-time applications requiring both low delay and high bandwidth routes. However, most current DCLC solutions are heuristics not specifically tailored for SR. In this work, we leverage both inherent limitations in the accuracy of delay measurements and an operational constraint added by SR. We include these characteristics in the design of BEST2COP, an exact but efficient ECMP-aware algorithm that natively solves DCLC in SR domains. Through an extensive performance evaluation, we first show that BEST2COP scales well even in large random networks. In real networks having up to thousands of destinations, our algorithm returns all DCLC solutions encoded as SR paths in way less than a second.

Modern network services are in most cases virtualized and the traffic of various users is multiplexed over the same physical links. Traditional network monitoring methods which predominantly rely on the physical interface monitoring are not sufficient because they do not provide the insight into the behaviour of the traffic in the specific network service instance or per-user service experience. This paper presents NetMon, a framework that gathers performance indicators inside the network service and at the same time allows an efficient spatial performance degradation localization capability. NetMon is technology agnostic and suitable for various network technologies ranging from legacy to the new type of services based on network function virtualization, chaining service functions or programmable network elements. The paper presents an original solution to the problem of scalable active network service monitoring with the capability to distinguish the measurements of different virtual networks. The proposed hybrid monitoring method which mixes the active probing and capturing this probe traffic provides a good trade-off between the granularity of the results and the traffic overhead created by the monitoring system itself. The system was tested in the pan-European GEANT network which connects European research and education infrastructures and showed reliable performance over long periods of time.

Internet topology discovery aims at analyzing one of the most complex distributed systems currently deployed. Usually, it relies on measurement campaigns using hop-limited probes sent with traceroute. However, this probing tool comes with several limits. In particular, some MPLS clouds might obfuscate collected traces. The resulting Internet maps, their inferred properties, and the graph models are thus incomplete and inaccurate. In this paper, we introduce TNT (Trace the Naughty Tunnels), an extension to Paris traceroute for revealing, or at least detect, all MPLS tunnels along a path. First, along with traceroute and ping probes, TNT looks for hints indicating the presence of hidden tunnels. Those hints are peculiar patterns in the resulting output, e.g., significant TTL shifts or duplicate IP addresses. Second, if those hints trigger alarms, TNT launches additional dedicated probing for possibly revealing hidden tunnels. We use GNS3 to reproduce, verify, and understand the limits and capabilities of TNT in a controlled environment. We also calibrate the thresholds at which alarms are triggered through a dedicated measurement campaign. Finally, we deploy TNT on the Archipelago platform and provide a quantified classification of MPLS configurations. All our results, including the data, the code, and the GNS3 experiments, are fully and publicly available.

In this paper, we are interested in the relationship between packet losses and routing changes in an operational network. To do so we designed and deployed DCART, a monitoring platform over RENATER, the French research and education network. Our platform collects four data sources using both active and passive measurements in order to unveil their temporal correlations. Active probing allows especially for measuring packet losses on specifically crafted data flows. Those flows explore several load balanced paths and ease the revelation of forwarding loops. Passive monitoring is achieved by listening to all routing updates from IS-IS, the intra-domain routing protocol in use, and by retrieving tickets generated by the Network Operations Center (NOC). During our monitoring campaign, we observe that most of the series of loss were correlated to routing events either because routing changes lead to inconsistent state transitions , or because faulty – and so lossy – links trigger numerous periods of link flapping. In particular, we show that losses due to forwarding loops resulting from inconsistent routing states are quite common when links come back after an outage. We also show that link flapping sometimes induce very long lasting lossy periods frequently unnoticed by the NOC. A lightweight monitoring platform such as DCART could be used to better anticipate recurrent network outages and to improve the ticketing system.

For years, Internet topology research has been conducted through active measurement. For instance, Caida builds router level topologies on top of IP level traces obtained with traceroute. The resulting graphs contain a significant amount of nodes with a very large degree, often exceeding the actual number of interfaces of a router. Although this property may result from inaccurate alias resolution, we believe that opaque MPLS clouds made of invisible tunnels are the main cause. Using Layer-2 technologies such as MPLS, routers can be configured to hide internal IP hops from traceroute. Consequently, an entry point of an MPLS network appears as the neighbor of all exit points and the whole Layer-3 network turns into a dense mesh of high degree nodes.

Traffic Engineering (TE) is one of the keys for improving packet forwarding in the Internet. It allows IP network operators to finely tune their forwarding paths according to various customer needs. One of the most popular tool available today for optimizing the use of networking resources is MPLS. On the one hand, operators may use MPLS and label distribution mechanisms such as RSVP-TE in conjunction with BGP to define multiple transit paths (for a given edge pair) verifying different constraints on their network. On the other hand, when operators simply enable LDP for distributing MPLS labels in order to improve the scalability of their network, another kind of path diversity may appear thanks to the ECMP feature of IGP routing.

Manageability and high availability are critical properties for IP networks. Unfortunately, with link-state routing protocols commonly used in such networks, topological changes lead to transient forwarding loops inducing service disruption. This reduces the frequency at which operators can adapt their network. Prior works proved that it is possible to avoid disruptions due to the planned reconfiguration of a link by progressively changing its weight, leading to a solution that does not require changing protocol specification. In this paper, we study the more general problem of gracefully modifying the logical state of multiple interfaces of a router, while minimizing the number of weight updates. Compared to single-link modifications, the router update problem is k-dimensional for a router having k neighbors. We also show that multidimensional updates may trigger new kinds of disruptions that make the problem more challenging than the single-link case. We then present and evaluate efficient algorithms that compute minimal sequences of weights enabling disruption-free router reconfigurations. Based on analysis of real IP network topologies, we show that both the size of such sequences and the computing time taken by our algorithms are limited.

The use of real-time multimedia or mission-critical applications over IP networks puts strong pressure on service providers to operate disruption-free networks. However, after any topological change, link-state Interior Gateway Protocols (IGPs), such as IS-IS or OSPF, enter a convergence phase during which transient forwarding loops may occur. Such loops increase the network latency and cause packet losses. In this paper, we propose and evaluate an efficient algorithm aimed at avoiding such traffic disruptions without modifying these IGPs. In case of an intentional modification of the weight of a link (e.g., to shut it down for maintenance operations or to perform traffic engineering), our algorithm iteratively changes this weight, splitting the modification into a sequence of loop-free transitions. The number of weight increments that need to be applied on the link to reach its target state is minimized in order to remain usable in existing networks. Analysis performed on inferred and real Internet service provider (ISP) topologies shows that few weight increments are required to handle most link shutdown events (less than two intermediate metrics for more than 85% of the links). The evaluation of our implementation also reveals that these minimal sequences can be computed in a reasonable time.

Manageability and evolvability are crucial needs for IP networks. Unfortunately, planned topological changes may lead to transient forwarding loops in link-state routing protocols commonly used in IP networks. These lead to service unavailability, reducing the frequency at which operators can adapt the network topology. Prior works proved that the state of a given link can be modified while avoiding forwarding inconsistencies without changing protocol specifications. In this paper, we study the more general problem of gracefully modifying the state of an entire router, while minimizing the induced operational impact. As opposed to a single-link modification, the router update problem is k-dimensional for a node of degree k. Moreover, we show that the interplay between operations applied at the router granularity can lead to loops that do not occur considering a single-link modification. In this paper, we present an efficient algorithm that computes minimal sequences of weights to be configured on the links of the updated node. Based on real IP network topologies, we show that the size of such sequence is limited in practice.

Fingerprinting networking equipment has many potential applications and benefits in network management and security. More generally, it is useful for the understanding of network structures and their behaviors. In this paper, we describe a simple fingerprinting mechanism based on the initial TTL values used by routers to reply to various probing messages. We show that main classes obtained using this simple mechanism are meaningful to distinguish routers platforms. Besides, it comes at a very low additional cost compared to standard active topology discovery measurements. As a proof of concept, we apply our method to gain more insight on the behavior of MPLS routers and to, thus, more accurately quantify their visible/invisible deployment.

Recent developments in router level topology discovery have suggested the introduction of IGMP probing in addition to standard techniques such as traceroute and alias resolution. With a single IGMP probe, one can obtain all multicast interfaces and links of a multicast router. If such a probing is a promising approach, we noticed that IGMP probes are subject to filtering, leading so to the fragmentation of the collected multicast graph into several disjoint connected components. In this paper, we cope with the fragmentation issue. Our contributions are threefold: (i) we experimentally quantify the damages caused by IGMP filtering on collected topologies of large tier-1 ISPs; (ii) using traceroute data, we construct a hybrid graph and estimate how far each IGMP fragment is from each other; (iii) we provide and experimentally evaluate a recursive approach for reconnecting disjoint multicast components. The key idea of the third contribution is to recursively apply alias resolution to reassemble disjoint fragments and, thus, progressively extend the mapping of the targeted ISP. Data presented in the paper, as well as reconstructed topologies, are freely available at http://svnet.u-strasbg.fr/merlin.

In wireless sensor networks, energy efficiency is generally achieved by turning off some capabilities from a subset of deployed sensors. The set of active nodes must therefore meet the application requirements (e.g. area coverage, data redundancy) while remaining fully connected to allow further data collection. Here, we focus on the case of a nomad sink entering the network and gathering every monitoring data. At the routing layer, minimizing the number of nodes acting as relays requires to construct a maximum leaf spanning tree (MLST). However, optimizing convergecast communications consists in minimizing the hop distance between the sink and all others nodes, leading so to a shortest path tree rooted at the sink. In this paper, we propose a distributed routing protocol that aims at constructing an energy efficient backbone being convergecast efficient at the same time. Our proposal introduces a tradeoff parameter to adjust the compromise “number of relays / routing efficiency” and then constructs a hybrid routing structure based on the combination of variants of the Wu-Li algorithm and a gradient-based routing protocol. For all topologies we simulated, and when tuned for energy saving, our approach outperforms a 2-approximation for constructing a MLST. Furthermore, when tuned for convergecast routing, simulation results show that our solution constructs a routing optimal backbone that involves a small fraction of relays.

For a long time, traceroute measurements combined with alias resolution methods have been the sole way to collect Internet router level maps. Recently, a new approach has been introduced with the use of a multicast management tool, mrinfo, and a recursive probing scheme. In this paper, after analyzing advantages and drawbacks of probing approaches based on traceroute and mrinfo, we propose a hybrid discovery tool, Merlin (MEasure the Router Level of the INternet), mixing mrinfo and traceroute probes. Using a central server controlling a set of distributed vantage points in order to increase the exploration coverage while limiting the probing redundancy, the purpose of Merlin is to provide an accurate router level map inside a targeted Autonomous System (AS). Merlin also takes advantage of alias resolution methods to reconnect scattered multicast components. To evaluate the performance of Merlin, we report experimental results describing its efficiency in topology exploration and reconstruction of several ASes.

The Internet topology data collected through traceroute exploration has been extensively studied in the past. In particular, a remarkable property of the Internet, the power-law shape of node degree distribution, drew the attention of the research community. Several studies have since questioned this property.

Redundant connectivity (or multiconnectivity) between adjacent autonomous systems (ASes) is important for interdomain traffic engineering and fast recovery in case of failures. However, the redundancy of ASes business relationship links has not been quantitatively studied, mainly due to the difficulty of obtaining relevant data. In this paper, we show that the mrinfo multicast monitoring tool can provide useful data about the Internet topology and such redundant links in particular. Our analysis relies on more than four years of daily queries to about ten thousand routers mapped into more than two hundred ASes. We demonstrate that peering links between ASes are frequently redundant. In particular, our analysis shows that more than half of the studied ASes pairs are connected through multiple physical links. We then refine our analysis by considering the different types of ASes and their business relationships. A particular result of our analysis is that at least 75% of the peer-to-peer relationships between adjacent Tier-1 ASes are redundant, i.e., the connections between these ASes involve several physical links. Our analysis is conservative, providing so a lower bound, as some links might not be seen by mrinfo due to ISPs filtering policies.

Energy efficiency is one of the most important issue to be tackled in wireless sensor networks. Activity scheduling protocols aim at prolonging the network lifetime by reducing the proportion of nodes that participate in the application. Among the vast range of criteria existing to schedule nodes activities, area coverage by connected sets is one of the most studied. Active nodes must ensure area coverage while remaining connected in order to guarantee proper data collection to the sink stations. As wireless communications stand for the main source of energy consumption, we investigated the communication redundancy of the active nodes set. We define a path diversity based metric that allows to characterize the communication redundancy of a given set of nodes. We show that one of the most used connectivity criterion is far from building minimal connected sets in terms of communicating nodes involved. Our results open new directions to design localized connected sets solutions.

Internet service providers have to provision network resources to optimize bandwidth utilization. Dynamic routing protocols take traffic variations into account to control the load distribution. Multipath routing protocols attempt to take advantage of the path diversity to bring network robustness and reliability. Indeed, with a specific traffic engineering policy, they enable load balancing across several paths. Our aim is to compute a set of loopfree paths in order to allow routers to share the load on several next hops depending on current load measurement. In this paper, we first describe our original Incoming Interface Multipath Routing technique, DT(p), then we present a scheme for load balancing, DT(p)-TE, based on link monitoring. We evaluate and compare our technique with several existing approaches by a set of simulations, using different scenarios and topologies. The simulations results suggest that the path diversity achieved with our proposition can significantly improve the network response time.