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.

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.

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.

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.