Prior work on LEO satellite networks focuses on regular constellations and grid-like topologies. Using existing Starlink satellite data, we uncover and systematically characterize the constellation's irregularities at multiple granularities, including shell distribution, orbital spacing, intra-orbit satellite placement, and hardware heterogeneity. To expose the actual impact of these irregularities, we try and superimpose grid-like topologies onto them, and study the impact of doing so. Our simulations show that forcing regular topologies on irregular constellations significantly affects routing and network performance, revealing a fundamental mismatch between idealized models and real deployments. Motivated by these findings, we outline future directions, including irregularity-aware topologies, systems and perspectives.

Modern networks of Low Earth Orbit (LEO) satellites promise to offer low-latency connectivity between any pair of devices on Earth. However, as the length of inter-satellite links constantly changes, the lowest-delay paths between satellites change over time even if the network topology does not. In this paper, we characterize the lowest-delay paths in LEO satellite networks whose topologies are lattice graphs. We show how the shape of these paths can be determined by knowing the satellites’ orbits, their movement direction and the topological positions of source and destination satellites. Our characterization has the potential to inspire several practical applications, including fast, resource-efficient routing algorithms and protocols.

ISPs may notice that traffic from certain sources is entering their network at an unexpected location, but it is hard to know if this represents a problem or is just normal spoofed background noise. If such traffic is not spoofed, it would be useful to generate alerts, but alerting on background noise is not useful.

BGP reconfigurations are a daily occurrence for most network operators, especially in large networks. Yet, performing safe and robust BGP reconfiguration changes is still an open problem. Few BGP reconfiguration techniques exist, and they are either (i) unsafe, because they ignore transient states, which can easily lead to invariant violations; or (ii) impractical, as they duplicate the entire routing and forwarding states, and require special hardware.

Avoiding packet loss is crucial for ISPs. Unfortunately, malfunctioning hardware at ISPs can cause long-lasting packet drops, also known as gray failures, which are undetectable by existing monitoring tools.

Data plane programmability is greatly improving network monitoring. Most new proposals rely on controllers pulling information (e.g., sketches or packets) from the data plane. This architecture is not a good fit for tasks requiring high reactivity, such as failure recovery, attack mitigation, and so on. Focusing on these tasks, we argue for a different architecture, where the data plane autonomously detects anomalies and pushes alerts to the controller. As a first step, we demonstrate that statistical checks can be implemented in P4 by revisiting definition and online computation of statistical measures. We collect our techniques in a P4 library, and showcase how they enable in-switch anomaly detection.

Motivated by conversations with operators and by possibilities to unlock future Internet-based applications, we study how to enable Internet Service Providers (ISPs) to reliably offer connectivity through disjoint paths as an advanced, value-added service. As ISPs are increasingly deploying Segment Routing (SR), we focus on implementing such service with SR. We introduce the concept of robustly disjoint paths, pairs of paths that are constructed to remain disjoint even after an input set of failures, with no external intervention (e.g., configuration change). We extend the routing theory, study the problem complexity, and design efficient algorithms to automatically compute SR-based robustly disjoint paths. Our algorithms enable a fully automated approach to offer the disjoint-path connectivity, based on configuration synthesis. Our evaluation on real topologies shows that such an approach is practical, and scales to large ISP networks.

One design principle of modern network architecture seems to be set in stone: a software-based control plane drives a hardware- or software-based data plane. We argue that it is time to revisit this principle after the advent of programmable switch ASICs which can run complex logic at line rate.

An ISP's customers increasingly demand delivery of their traffic without congestion and with low latency. The ISP's topology, routing, and traffic engineering, often over multiple paths, together determine congestion and latency within its backbone. We first consider how to measure a topology's capacity to route traffic without congestion and with low latency. We introduce low-latency path diversity (LLPD), a metric that captures a topology's flexibility to accommodate traffic on alternative low-latency paths. We explore to what extent 116 real backbone topologies can, regardless of routing system, keep latency low when demand exceeds the shortest path's capacity. We find, perhaps surprisingly, that topologies with good LLPD are precisely those where routing schemes struggle to achieve low latency without congestion. We examine why these schemes perform poorly, and offer an existence proof that a practical routing scheme can achieve a topology's potential for congestion-free, low-delay routing. Finally we examine implications for the design of backbone topologies amenable to achieving high capacity and low delay.

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.

Early in in the Internet's history, routing within a single provider's WAN centered on placing traffic on the shortest path. More recent traffic engineering efforts aim to reduce congestion and/or increase utilization within the status quo of greedy shortest-path first routing on a sparse topology. In this paper, we argue that this status quo of routing and topology is fundamentally at odds with placing traffic so as to minimize latency for users while avoiding congestion. We advocate instead provider backbone topologies that are more mesh-like, and hence better at providing multiple low-latency paths, and a routing system that directly considers latency minimization and congestion avoidance while dynamically placing traffic on multiple unequal-cost paths. We offer a research agenda for achieving this new low-latency approach to WAN topology design and routing.

In this paper, we study how to perform traffic engineering at an extremely-small time scale with segment routing, addressing a critical need for modern wide area networks. Prior work has shown that segment routing enables to better engineer traffic, thanks to its ability to program detours in forwarding paths, at scale. Two main approaches have been explored for traffic engineering with segment routing, respectively based on integer linear programming and constraint programming. However, no previous work deeply investigated how quickly those approaches can react to unexpected traffic changes and failures. We highlight limitations of existing algorithms, both in terms of required execution time and amount of path changes to be applied. Thus, we propose a new approach, based on local search and focused on the quick re-arrangement of (few) forwarding paths. We describe heuristics for sub-second recomputation of segment-routing paths that comply with requirements on the maximum link load (e.g., for congestion avoidance). Our heuristics enable a prompt answer to sudden criticalities affecting network services and business agreements. Through extensive simulations, we indeed experimentally show that our proposal significantly outperforms previous algorithms in the context of time-constrained optimization, supporting radical traffic changes in few tens of milliseconds for realistic networks.

Network operators often face the problem of remote outages in transit networks leading to significant (sometimes on the order of minutes) downtimes. The issue is that BGP, the Internet routing protocol, often converges slowly upon such outages, as large bursts of messages have to be processed and propagated router by router.

Disruption-free updates are a key primitive to effectively operate SDN networks and maximize the benefits of their programmability. In this paper, we study how to implement this primitive safely (with respect to forwarding correctness and policies), efficiently (in terms of consumed network resources) and robustly to unpredictable factors, such as delayed message delivery and processing. First, we analyze the fundamental limitations of prior proposals, which either: 1) progressively replace initial flow rules with new ones or 2) instruct switches to maintain both initial and final rules. Second, we show that safe, efficient, and robust updates can be achieved by leveraging a more general approach. We indeed unveil a dualism between rule replacements and additions that opens new degrees of freedom for supporting SDN updates. Third, we demonstrate how to build upon this dualism. We propose FLIP, an algorithm that computes operational sequences combining the efficiency of rule replacements with the applicability of rule additions. FLIP identifies constraints on rule replacements and additions that independently prevent safety violations from occurring during the update. Then, it explores the solution space by swapping constraints that prevent the same safety violations, until it reaches a satisfiable set of constraints. Fourth, we perform extensive simulations, showing that FLIP can significantly outperform prior work. In the average case, it guarantees a much higher success rate than algorithms only based on rule replacements, and massively reduces the memory overhead needed by techniques solely using rule additions.

The support for safe network updates, i.e., live modification of device behavior without service disruption, is a critical primitive for current and future networks. Several techniques have been proposed by previous works to implement such a primitive. Unfortunately, existing techniques are not generally applicable to any network architecture, and typically require high overhead (e.g., additional memory) to guarantee strong consistency (i.e., traversal of either initial or final paths, but never a mix of them) during the update. In this paper, we deeply study the problem of computing operational sequences to safely and quickly update arbitrary networks. We characterize cases, for which this computation is easy, and revisit previous algorithmic contributions in the new light of our theoretical findings. We also propose and thoroughly evaluate a generic sequence-computation approach, based on two new algorithms that we combine to overcome limitations of prior proposals. Our approach always finds an operational sequence that provably guarantees strong consistency throughout the update, with very limited overhead. Moreover, it can be applied to update networks running any combination of centralized and distributed control-planes, including different families of IGPs, OpenFlow or other SDN protocols, and hybrid SDN networks. Our approach therefore supports a large set of use cases, ranging from traffic engineering in IGP-only or SDN-only networks to incremental SDN roll-out and advanced requirements (e.g., per-flow path selection or dynamic network function virtualization) in partial SDN deployments.

For Internet Service Provider (ISP) operators, getting an accurate picture of how their network behaves is challenging. Given the traffic volumes that their networks carry and the impossibility to control end-hosts, ISP operators are typically forced to randomly sample traffic, and rely on aggregated statistics. This provides coarse-grained visibility, at a time resolution that is far from ideal (seconds or minutes). In this paper, we present Mille-Feuille, a novel monitoring architecture that provides fine-grained visibility over ISP traffic. Mille-Feuille schedules activation and deactivation of traffic-mirroring rules, that are then provisioned network-wide from a central location, within milliseconds. By doing so, Mille-Feuille combines the scalability of sampling with the visibility and controllability of traffic mirroring. As a result, it supports a set of monitoring primitives, ranging from checking key performance indicators (e.g., one-way delay) for single destinations to estimating traffic matrices in sub-seconds. Our preliminary measurements on existing routers confirm that Mille-Feuille is viable in practice.

To guarantee correct operation of their networks, operators have to promptly detect and diagnose data-plane issues, like broken interface cards or link failures. Networks are becoming more complex, with a growing number of Equal Cost MultiPath (ECMP) and link bundles. Hence, some data-plane problems (e.g. silent packet dropping at one router) can hardly be detected with control-plane protocols or simple monitoring tools like ping or traceroute. In this paper, we propose a new technique, called SCMon, that enables continuous monitoring of the data-plane, in order to track the health of all routers and links. SCMon leverages the recently proposed Segment Routing (SR) architecture to monitor the entire network with a single box (and no additional monitoring protocol). In particular, SCMon uses SR to (i) force monitoring probes to travel over cycles; and (ii) test parallel links and bundles at a per-link granularity. We present original algorithms to compute cycles that cover all network links with a limited number of SR segments. Further, we prototype and evaluate SCMon both with simulations and Linux-based emulations. Our experiments show that SCMon quickly detects and precisely pinpoints data-plane problems, with a limited overhead.

We propose FLIP, a new algorithm for SDN network updates that preserve forwarding policies. FLIP builds upon the dualism between replacements and additions of switch flow-table rules. It identifies constraints on rule replacements and additions that independently prevent policy violations from occurring during the update. Moreover, it keeps track of alternative constraints, avoiding the same policy violation. Then, it progressively explores the solution space by swapping constraints with their alternatives, until it reaches a satisfiable set of constraints. Extensive simulations show that FLIP outperforms previous proposals. It achieves a much higher success rate than algorithms based on rule replacements only, and massively reduces the memory overhead with respect to techniques solely relying on rule additions.

Video streaming, in conjunction with social networks, have given birth to a new traffic pattern over the Internet: transient, localized traffic surges, known as flash crowds. Traditional traffic-engineering methods can hardly cope with these surges, as they are unpredictable by nature. Consequently, networks either have to be over-provisioned, which is expensive and wastes resources, or risk to periodically incur congestion, which infuriates customers. This demonstration shows how Fibbing can improve network performance and preserve users’ quality of experience when accessing video streams, by implementing a fine-grained load-balancing service. This service leverages two unique features of Fibbing: programming per destination load-balancing and implementing uneven splitting ratios.

Given the distributed and business-driven nature of the Internet, economic interests of autonomous systems (ASes) may be incompatible. Previous works studied specific effects of incompatible interests, especially BGP policy conflicts leading to routing and forwarding anomalies. In this paper, we focus on the effects of incompatible interests that do not trigger such anomalies. We take the perspective of a single AS: we show that incompatible interests can have a tangible impact on its business and provide a classification of its unsatisfied interests. Since incompatible interests cannot be solved automatically, our effort is directed to support network managers in their business decisions. Hence, we describe algorithms to identify and assess their impact, as well as a prototype of a warning system aimed at signaling the most relevant unsatisfied interests. We evaluate our prototype on real data from two operational networks. In addition, to illustrate the potential of our system, our evaluation shows that unsatisfied interest are relatively frequent and likely affect a significant amount of traffic in practice.

Network operators can and do deploy multiple routing control-planes, e.g., by running different protocols or instances of the same protocol. With the rise of SDN, multiple control-planes are likely to become even more popular, e.g., to enable hybrid SDN or multi-controller deployments. Unfortunately, previous works do not apply to arbitrary combinations of centralized and distributed control-planes. In this paper, we develop a general theory for coexisting control-planes. We provide a novel, exhaustive classification of existing and future control-planes (e.g., OSPF, EIGRP, and Open-Flow) based on fundamental control-plane properties that we identify. Our properties are general enough to study centralized and distributed control-planes under a common framework. We show that multiple uncoordinated control-planes can cause forwarding anomalies whose type solely depends on the identified properties. To show the wide applicability of our framework, we leverage our theoretical insight to (i) provide sufficient conditions to avoid anomalies, (ii) propose configuration guidelines, and (iii) define a provably-safe procedure for reconfigurations from any (combination of) control-planes to any other. Finally, we discuss prominent consequences of our findings on the deployment of new paradigms (notably, SDN) and previous research works.

SDN simplifies network management by relying on declarativity (high-level interface) and expressiveness (network flexibility). We propose a solution to support those features while preserving high robustness and scalability as needed in carrier-grade networks. Our solution is based on (i) a two-layer architecture separating connectivity and optimization tasks; and (ii) a centralized optimizer called framework, which translates high-level goals expressed almost in natural language into compliant network configurations. Our evaluation on real and synthetic topologies shows that framework improves the state of the art by (i) achieving better trade-offs for classic goals covered by previous works, (ii) supporting a larger set of goals (refined traffic engineering and service chaining), and (iii) optimizing large ISP networks in few seconds. We also quantify the gains of our implementation, running Segment Routing on top of IS-IS, over possible alternatives (RSVP-TE and OpenFlow).

Centralizing routing decisions offers tremendous flexibility, but sacrifices the robustness of distributed protocols. In this paper, we present Fibbing, an architecture that achieves both flexibility and robustness through central control over distributed routing. Fibbing introduces fake nodes and links into an underlying link-state routing protocol, so that routers compute their own forwarding tables based on the augmented topology. Fibbing is expressive, and readily supports flexible load balancing, traffic engineering, and backup routes. Based on high-level forwarding requirements, the Fibbing controller computes a compact augmented topology and injects the fake components through standard routing-protocol messages. Fibbing works with any unmodified routers speaking OSPF. Our experiments also show that it can scale to large networks with many forwarding requirements, introduces minimal overhead, and quickly reacts to network and controller failures.

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.

Internet service providers (ISPs) run the internal Border Gateway Protocol (iBGP) to distribute interdomain routing information among their BGP routers. Previous research consistently assumed that iBGP is always configured as a mere dispatcher of interdomain routes. However, router configuration languages offer operators the flexibility of fine-tuning iBGP. In this paper, we study the impact of deploying routing policies in iBGP. First, we devise a provably correct inference technique to pinpoint iBGP policies from public BGP data. We show that the majority of large transit providers and many small transit providers do apply policies in iBGP. Then, we discuss how iBGP policies can help achieve traffic engineering and routing objectives. We prove that, unfortunately, the presence of iBGP policies exacerbates the iBGP convergence problem and invalidates fundamental assumptions for previous results, affecting their applicability. Hence, we propose provably correct configuration guidelines to achieve traffic engineering goals with iBGP policies, without sacrificing BGP convergence guarantees. Finally, for the cases in which our guidelines are not applicable, we propose a novel technique to verify the correctness of an iBGP configuration with iBGP policies. We implement a prototype tool and show the feasibility of offline analyses of arbitrary policies on both real-world and in vitro configurations.

Link-state routing protocols (e.g., OSPF and IS-IS) are widely used because they are scalable, robust, and based on simple abstractions. Unfortunately, these protocols are also relatively inflexible, since they direct all traffic over shortest paths. In contrast, Software Defined Networking (SDN) offers fine-grained control over routing, at the expense of controller overhead, failover latency, and deployment challenges.

Simultaneously providing flexibility, evolvability and correctness of routing is one of the basic and still unsolved problems in networking. Route redistribution provides a tool, used in many enterprise networks, to either partition a network into multiple routing domains or merge previously independent networks. However, no general technique exists for changing a live network's route redistribution configuration without incurring packet losses and service disruptions. In this paper, we study the problem of how to safely transition between route redistribution configurations. We investigate what anomalies may occur in the reconfiguration process, showing that many long-lasting forwarding loops can and do occur if naive techniques are applied. We devise new sufficient conditions for anomaly-free reconfigurations, and we leverage them to build provably safe and practical reconfiguration procedures. Our procedures enable seamless network re-organizations to accomplish both short-term objectives, such as local repair or traffic engineering, and long-term requirement changes.

A significant portion of what is known about Internet routing stems out from public BGP datasets. For this reason, numerous research efforts were devoted to (i) assessing the (in)completeness of the datasets, (ii) identifying biases in the dataset, and (iii) augmenting data quality by optimally placing new collectors. However, those studies focused on techniques to extract information about the AS-level Internet topology. In this paper, we show that considering different metrics influences the conclusions about biases and collector placement. Namely, we compare AS-level topology discovery with iBGP policy inference. We find that the same datasets exhibit significantly diverse biases for these two metrics. For example, the sensitivity to the number and position of collectors is noticeably different. Moreover, for both metrics, the marginal utility of adding a new collector is strongly localized with respect to the proximity of the collector. Our results suggest that the “optimal” position for new collectors can only be defined with respect to a specific metric, hence posing a fundamental trade-off for maximizing the utility of extensions to the BGP data collection infrastructure.

To configure, troubleshoot and operate their networks, operators often have no alternatives than relying on error-prone manual procedures. The emerging Software Defined Networking paradigm opens new possibilities for more structured networking methodologies.We argue that provably-effective practices can be borrowed from more developed engineering fields, especially software engineering. In this paper, we propose an adaptation of test-driven software development methodologies to software defined networks (SDNs). To support our methodological guidelines, we propose an expressive requirement formalization language. Further, we describe a prototype tool able to check the compliance of an SDN controller with requirements expressed in the proposed language. Our evaluation of the prototype shows promising results on the practical viability of our approach.

Because of its practical relevance, the Border Gateway Protocol (BGP) has been the target of a huge research effort since more than a decade. In particular, many contributions aimed at characterizing the computational complexity of BGP-related problems. In this paper, we answer computational complexity questions by unveiling a fundamental mapping between BGP configurations and logic circuits. Namely, we describe simple networks containing routers with elementary BGP configurations that simulate logic gates, clocks, and flip-flops, and we show how to interconnect them to simulate arbitrary logic circuits. We then investigate the implications of such a mapping on the feasibility of solving BGP fundamental problems, and prove that, under realistic assumptions, BGP has the same computing power as a Turing Machine. We also investigate the impact of restrictions on the expressiveness of BGP policies and route propagation (e.g., route propagation rules in iBGP and Local Transit Policies in eBGP) and the impact of different message timing models. Finally, we show that the mapping is not limited to BGP and can be applied to generic routing protocols that use several metrics.

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.

Monitoring Internet performance and measuring user quality of experience are drawing increased attention from both research and industry. To match this interest, large-scale measurement infrastructures have been constructed. We believe that this effort must be combined with a critical review and calibrarion of the tools being used to measure performance.

Network upgrades, performance optimizations and traffic engineering activities often force network operators to adapt their IGP configuration. Recently, several techniques have been proposed to change an IGP configuration (e.g., link weights) in a disruption-free manner. Unfortunately, none of these techniques considers the impact of IGP changes on BGP correctness. In this paper, we show that known reconfiguration techniques can trigger various kinds of BGP anomalies. First, we illustrate the relevance of the problem by performing simulations on a Tier-1 network. Our simulations highlight that even a few link weight changes can produce long-lasting BGP anomalies affecting a significant part of the BGP routing table. Then, we study the problem of finding a reconfiguration ordering which maintains both IGP and BGP correctness. Unfortunately, we show examples in which such an ordering does not exist. Furthermore, we prove that deciding if such an ordering exists is NP-hard. Finally, we provide sufficient conditions and configuration guidelines that enable graceful operations for both IGP and BGP.

The network infrastructure of Internet service providers (ISPs) undergoes constant evolution. Whenever new requirements arise (e.g., the deployment of a new Point of Presence or a change in the business relationship with a neighboring ISP), operators need to change the configuration of the network. Due to the complexity of the Border Gateway Protocol (BGP) and the lack of methodologies and tools, maintaining service availability during reconfigurations that involve BGP is a challenge for operators. In this paper, we show that the current best practices to reconfigure BGP do not provide guarantees with respect to traffic disruptions. Then, we study the problem of finding an operational ordering of BGP reconfiguration steps that guarantees no packet loss. Unfortunately, finding such an operational ordering, when it exists, is computationally hard. To enable lossless reconfigurations, we propose a framework that extends current features of carrier-grade routers to run two BGP control planes in parallel. We present a prototype implementation and show the effectiveness of our framework through a case study.

Routing stability and correctness in the Internet have long been a concern. Despite this, few theoretical frameworks have been proposed to check BGP configurations for convergence and safety. The most popular approach is based on the Stable Paths Problem (SPP) model. Unfortunately, SPP requires enumeration of all possible control-plane paths, which is infeasible in large networks. In this work, we study how to apply algebraic frameworks to the BGP configuration checking problem. We propose an extension of the Stratified Shortest Path Problem (SSPP) model that has a similar expressive power to SPP, but enables more efficient checking of configuration correctness. Our approach remains valid when BGP policies are applied to iBGP sessions - a case which is often overlooked by previous work, although common in today's Internet. While this paper focuses mainly on iBGP problems, our methodology can be extended to eBGP if operators are willing to share their local-preference configurations.

Internal BGP (iBGP) is used to distribute interdomain routes within a single ISP. The interaction between iBGP and the underlying IGP can lead to routing and forwarding anomalies. For this reason, several research contributions aimed at defining sufficient conditions to guarantee anomaly-free configurations and providing design guidelines for network operators. In this paper, we show several anomalies caused by defective dissemination of routes in iBGP. We define the dissemination correctness property, which models the ability of routers to learn at least one route to each destination. By distinguishing between dissemination correctness and existing correctness properties, we show counterexamples that invalidate some results in the literature. Further, we prove that deciding whether an iBGP configuration is dissemination correct is computationally intractable. Even worse, determining whether the addition of a single iBGP session can adversely affect dissemination correctness of an iBGP configuration is also computationally intractable. Finally, we provide sufficient conditions that ensure dissemination correctness, and we leverage them to both formulate design guidelines and revisit prior results.

Network-wide migrations of a running network, such as the replacement of a routing protocol or the modification of its configuration, can improve the performance, scalability, manageability, and security of the entire network. However, such migrations are an important source of concerns for network operators as the reconfiguration campaign can lead to long, service-disrupting outages. In this paper, we propose a methodology that addresses the problem of seamlessly modifying the configuration of link-state Interior Gateway Protocols (IGPs). We illustrate the benefits of our methodology by considering several migration scenarios, including the addition and the removal of routing hierarchy in a running IGP, and the replacement of one IGP with another. We prove that a strict operational ordering can guarantee that the migration will not create any service outage. Although finding a safe ordering is NP-complete, we describe techniques that efficiently find such an ordering and evaluate them using several real-world and inferred ISP topologies. Finally, we describe the implementation of a provisioning system that automatically performs the migration by pushing the configurations on the routers in the appropriate order while monitoring the entire migration process.

BGP, the core protocol of the Internet backbone, is renowned to be prone to oscillations. Despite prior work shed some light on BGP stability, many problems remain open. For example, determining how hard it is to check that a BGP network is safe, i.e., it is guaranteed to converge, has been an elusive research goal up to now. In this paper, we address several problems related to BGP stability, stating the computational complexity of testing if a given configuration is safe, is robust, or is safe under filtering. Further, we determine the computational complexity of checking popular sufficient conditions for stability. We adopt a model that captures Local Transit policies, i.e., policies that are functions only of the ingress and the egress points. The focus on Local Transit policies is motivated by the fact that they represent a configuration paradigm commonly used by network operators. We also address the same BGP stability problems in the widely adopted SPP model. Unfortunately, we find that the most interesting problems are computationally hard even if policies are restricted to be as expressive as Local Transit policies. Our findings suggest that the computational intractability of BGP stability be an intrinsic property of policy-based path vector routing protocols that allow policies to be specified in complete autonomy.

Network-wide migrations of a running network, such as the replacement of a routing protocol or the modification of its configuration, can improve the performance, scalability, manageability, and security of the entire network. However, such migrations are an important source of concerns for network operators as the reconfiguration campaign can lead to long and service-affecting outages.

Internet Service Providers can enforce a fine-grained control of Interdomain Routing by cleverly configuring the Border Gateway Protocol. However, the price to pay for the flexibility of BGP is the lack of convergence guarantees. The literature on network protocol design introduced several sufficient conditions that routing policies should satisfy to guarantee convergence. However, a methodology to systematically check BGP policies for convergence is still missing. This paper presents two fundamental contributions. First, we describe a heuristic algorithm that statically checks BGP configurations for guaranteed routing convergence. Our algorithm has several highly desirable properties: i) it exceeds state-of-the-art algorithms by correctly reporting more configurations as stable, ii) it can be implemented efficiently enough to analyze Internet-scale configurations, iii) it is free from false positives, namely never reports a potentially oscillating configuration as stable, and iv) it can help spot troublesome points in a detected oscillation. Second, we propose an architecture for a modular tool that exploits our algorithm to process native router configurations and report the presence of potential oscillations. Such a tool can effectively integrate syntactic checkers and assist operators in verifying configurations. We validate our approach using a prototype implementation and show that it scales well enough to enable Internet-scale convergence checks.

Border Gateway Protocol (BGP) allows providers to express complex routing policies preserving high degrees of autonomy. However, unrestricted routing policies can adversely impact routing stability. A key concept to understand the interplay between autonomy and expressiveness on one side, and stability on the other side, is safety under filtering, i.e., guaranteed stability under autonomous usage of route filters. BGP route filters are used to selectively advertise specific routes to specific neighbors. In this paper, we provide a characterization of safety under filtering, filling the large gap between previously known necessary and sufficient conditions. Our characterization is based on the absence of a particular kind of dispute wheel, a structure involving circular dependencies among routing preferences. We exploit our result to show that networks admitting multiple stable states are provably unsafe under filtering, and the troublesome portion of the configuration can be pinpointed starting from the stable states alone. This is especially interesting from an operational point of view since networks with multiple stable states actually happen in practice (BGP wedgies). Finally, we show that adding filters to an existing configuration may lead to oscillations even if the configuration is safe under any link failure. Unexpectedly, we find policy configurations where misconfigured filters can do more harm than network faults.

Internet Service Providers (ISPs) run the internal flavor of the Border Gateway Protocol (iBGP) for distributing routing information among border routers. While configuration languages allow routers to change iBGP attributes as a BGP message travels within the ISP's network, most prior work neglected this possibility, focusing only on the common case where iBGP attributes are left untouched. In this paper we aim at understanding what are the pros and cons of changing iBGP attributes. We estimate how many ISPs change iBGP attributes, and we motivate such a practice by showing usage scenarios where modified iBGP attributes yield better traffic engineering. We also revisit a well-studied problem in iBGP, that is, routing stability. We show that changing iBGP attributes can generate routing oscillations which are not possible otherwise, and are not detectable by state-of-the-art algorithms. We present a technique to check for routing oscillations even when iBGP attributes are changed, and we give simple guidelines for changing iBGP attributes while preserving stability.

BGP allows providers to express complex routing policies preserving high degrees of autonomy. However, unrestricted routing policies can adversely impact routing stability. A key concept to understand the interplay between autonomy and expressiveness on one side, and stability on the other side, is safety under filtering, i.e., guaranteed stability under autonomous usage of route filters. BGP route filters are used to selectively advertise specific routes to specific neighbors. We provide a necessary and sufficient condition for safety under filtering, filling the large gap between previously known necessary and sufficient conditions. Our characterization is based on the absence of a particular kind of dispute wheel, a structure involving circular dependencies among routing preferences. We exploit our result to show that networks admitting multiple stable states are provably unsafe under filtering. This is especially interesting from an operational point of view, since networks with multiple stable states actually happen in practice (BGP wedgies). Finally, we show that adding filters to an existing configuration may lead to oscillations even if the configuration is safe under any link failure. Unexpectedly, we find policy configurations where misconfigured filters can do more harm than network faults.