This paper presents the result of three years of experience in research, design, and deployment of a complete architecture aimed at automatically identifying service disruptions in large BGP/MPLS VPN networks. We present the main components of a comprehensive architecture that can be operated in production environments, highlighting the requirements that led to their design. We describe the data that are collected from the network using IETF standard protocols, the processing that is performed onto them to detect anomalies, and the scaling aspects that need to be considered when ingesting the large amounts of data that is necessary for the purpose at hand. We report on two and a half years of deployment experience on the Swisscom BGP/MPLS VPN Network services, by analyzing the behavior of our system in the face of actual network incidents. After each incident, we systematically performed postmortem analyzes. These investigations led us to conclude that the rule-based approaches that are currently used in deployment, supported by a profiling of the VPN customers to fine-tune rule parameters, enables the detection of service disruptions with the required accuracy.

Identifying anomalies in a network is a crutial endeavor for Internet Service Providers (ISPs). Anomalies that impact the traffic of the ISP customers can lead to a degradation in the reputation of the company. Moreover, silent anomalies that do not break connectivity can impact the revenue and business of ISPs. Therefore, monitoring and anomaly detection has become essential for ISPs. In this paper, we present an ongoing research project aimed at identifying anomalies in Internet services provided by an ISP. We aim at detecting anomalies within the domain managed by the ISP that impact the customers and the business of the ISP. We propose a rule-based approach designed to promptly detect and provide reporting for such anomalies in near real time, giving information that allows the operator to identify whether a solution can be brought. In this paper, we describe the collected network telemetry metrics and illustrate how they are processed using open-source solutions. We introduce a set of use cases showing that an ISP can monitor Internet services using IETF standard metrics.

It is well known that internet infrastructure deployment is progressing at a rapid pace in the African continent. A flurry of recent research has quantified this, highlighting the expansion of its underlying connectivity network. However, improving the infrastructure is not useful without appropriately provisioned services to exploit it. This article measures the availability and utilisation of web infrastructure in Africa. Whereas others have explored web infrastructure in developed regions, we shed light on practices in developing regions. To achieve this, we apply a comprehensive measurement methodology to collect data from a variety of sources. We first focus on Google to reveal that its content infrastructure in Africa is, indeed, expanding. That said, we find that much of its web content is still served from the US and Europe, despite being the most popular website in many African countries. We repeat the same analysis across a number of other regionally popular websites to find that even top African websites prefer to host their content abroad. To explore the reasons for this, we evaluate some of the major bottlenecks facing content delivery networks (CDNs) in Africa. Amongst other factors, we find a lack of peering between the networks hosting our probes, preventing the sharing of CDN servers, as well as poorly configured DNS resolvers. Finally, our mapping of middleboxes in the region reveals that there is a greater presence of transparent proxies in Africa than in Europe or the US. We conclude the work with a number of suggestions for alleviating the issues observed.

It is well known that Africa's mobile and fixed Internet infrastructure is progressing at a rapid pace. A flurry of recent research has quantified this, highlighting the expansion of its underlying connectivity network. However, improving the infrastructure is not useful without appropriately provisioned services to utilise it. This paper measures the availability of web content infrastructure in Africa. Whereas others have explored web infrastructure in developed regions, we shed light on practices in developing regions. To achieve this, we apply a comprehensive measurement methodology to collect data from a variety of sources. We focus on a large content delivery network to reveal that Africa's content infrastructure is, indeed, expanding. However, we find much web content is still served from the US and Europe. We discover that many of the problems faced are actually caused by significant inter-AS delays in Africa, which contribute to local ISPs not sharing their cache capacity. We discover that a related problem is the poor DNS configuration used by some ISPs, which confounds the attempts of providers to optimise their delivery. We then explore a number of other websites to show that large web infrastructure deployments are a rarity in Africa and that even regional websites host their services abroad. We conclude by making suggestions for improvements.

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 anticipate the offering of an increasing variety of cloud-based services with stringent Service Level Agreements. Technologies currently supporting IP networks however lack the flexibility and scalability properties to realize such evolution. In this article, we present Segment Routing (SR), a new network architecture aimed at filling this gap, driven by use-cases defined by network operators. SR implements the source routing and tunneling paradigms, letting nodes steer packets over paths using a sequence of instructions (segments) placed in the packet header. As such, SR allows the implementation of routing policies without per-flow entries at intermediate routers. This paper introduces the SR architecture, describes its related ongoing standardization efforts, and reviews the main use-cases envisioned by network operators.

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).

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 trend toward more peering between networks is commonly conflated with the trend of Internet flattening, i.e., reduction in the number of intermediary organizations on Internet paths. Indeed, direct peering interconnections bypass layer-3 transit providers and make the Internet flatter. This paper studies an emerging phenomenon that separates the two trends: we present the first systematic study of remote peering, an interconnection where remote networks peer via a layer-2 provider. Our measurements reveal significant presence of remote peering at IXPs (Internet eXchange Points) worldwide. Based on ground truth traffic, we also show that remote peering has a substantial potential to offload transit traffic. Generalizing the empirical results, we analytically derive conditions for economic viability of remote peering versus transit and direct peering. Because remote-peering services are provided on layer 2, our results challenge the traditional reliance on layer-3 topologies in modeling the Internet economic structure. We also discuss broader implications of remote peering for reliability, security, accountability, and other aspects of Internet research.

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.

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.

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.

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.

Network operators use traffic engineering (TE) to control the flow of traffic across their networks. Existing TE methods require manual configuration of link weights or tunnels, which is difficult to get right, or prior knowledge of traffic demands and hence may not be robust to link failures or traffic fluctuations. We present a self-configuring TE scheme, SculpTE, which automatically adapts the network-layer topology to changing traffic demands. SculpTE is responsive, stable, and achieves excellent load balancing.

Internet routing table size growth and BGP update churn are two prominent Internet scaling issues. There is widespread belief in a high and fast growing number of ASs that deaggregate prefixes, e.g., due to multi-homing and for the purpose of traffic engineering. Moreover, researchers often blame specific classes of ASs for generating a disproportionate amount of BGP updates. Our primary objective is to challenge such widespread assumptions (“myths”) and not solely to confirm previous findings. Surprisingly, we find severe discrepancies between existing myths and reality. According to our results, there is no trend towards more aggressive prefix deaggregation or traffic engineering over time. With respect to update dynamics, we observe that deaggregated prefixes generally do not generate a disproportionate number of BGP updates, with respect to their share of the BGP routing table. On the other side, we observe much more widespread traffic engineering in the form of AS path prepending and scoped advertisements compared to previous studies. Overall, our work gives a far more positive picture compared to the alarming discourses typically heard: The impact of “bad guys” on routing table size growth and BGP churn has not changed for the worse in recent years. Rather, it increases at the same pace as the Internet itself.

Internet Service Providers design their network with resiliency in mind, having multiple paths towards external IP subnets available at the borders of their network. However, with the current internal Border Gateway Protocol, BGP routers and route reflectors only propagate their (unique) best path over their iBGP sessions. As a result, at the BGP router level, path diversity tends to be poor. Such lack of path diversity can lead to MED oscillations, prevents an efficient use of multipath BGP and does not allow for a fast and local recovery upon nexthop failure. Advertising multiple paths over iBGP sessions with BGP Add-Paths solves those issues, depending on the way the additional paths are selected. In this paper, we analyze the various options for the selection mode of the paths to be advertised. We show that these modes differently fulfill the needs of Add-Paths applications such as fast recovery upon failure and MED oscillation avoidance. We also show in our analysis that the costs and benefits bound with these modes depend on the connectivity of the AS where it is deployed. To support the analysis, we developed a tool allowing to measure the scaling of these modes in a given network. We illustrate the utilization of this tool on synthetic Internet topologies, and provide some recommendations for the choice of an Add-Paths selection mode.

This paper presents techniques that improve the efficiency and manageability of an IP Fast Reroute (IPFRR) technology: NotVia. NotVia provides the IPFRR service for all destinations in an ISP's network upon any single link or node failure, while previous proposals such as Loop-free Alternates (LFA) can not guarantee this level of coverage. However, NotVia increases the computational and memory costs of the IPFRR service, and poses new challenges to network management, as routers are unaware of the links and nodes (hence the amount of traffic) that they actually protect. This paper introduces three techniques: NotVia aggregation, prioritized NotVia computation, and the rNotVia algorithm that collectively reduce the overhead of NotVia and improve its manageability. We use simulations to evaluate these techniques on real ISP topologies as well as on randomly generated topologies. The results show that the computational and memory overhead of NotVia are reduced to a fraction of their previous values on various topologies, suggesting that the techniques proposed in this paper make NotVia a more efficient and easy-to-manage IPFRR solution.

A few modifications to software and/or hardware of routers have been proposed recently to avoid the transient micro loops that can occur during the convergence of link-state interior gateway protocols like IS-IS and OSPF. We1 propose in this paper a technique that does not require modifications to ISIS and OSPF, and that can be applied now by ISPs. Roughly, in the case of a manual modification of the state of a link, we progressively change the metric associated with this link to reach the required modification by ensuring that each step of the progression will be loop-free. The number of changes that are applied to a link to reach the targeted state by ensuring the transient consistency of the forwarding inside the network is minimized. Analysis performed on real regional and tier-1 ISP topologies show that the number of required transient changes is small. The solution can be applied in the case of link metric updates, manual set up, and shut down of links.

This paper presents a solution aimed at avoiding losses of connectivity when an eBGP peering link is shut down by an operator for a maintenance. Currently, shutting down an eBGP session can lead to transient losses of connectivity even though alternate path are available at the borders of the network. This is very unfortunate as ISPs face more and more stringent service level agreements, and maintenance operations are predictable operations, so that there is time to adapt to the change and preserve the respect of the service level agreement.

We first show by measurements that BGP peering links fail as frequently as intradomain links and usually for short periods of time. We propose a new fast-reroute technique where routers are prepared to react quickly to interdomain link failures. For each of its interdomain links, each router precomputes a protection tunnel, i.e. an IP tunnel to an alternate nexthop which can reach the same destinations as via the protected link. We propose a BGP-based auto-discovery technique that allows each router to learn the candidate protection tunnels for its links. Each router selects the best protection tunnels for its links and when it detects an interdomain link failure, it immediately encapsulates the packets to send them through the protection tunnel. Our solution is applicable for the links between large transit ISPs and also for the links between multi-homed stub networks and their providers. Furthermore, we show that transient forwarding loops (and thus the corresponding packet losses) can be avoided during the routing convergence that follows the deactivation of a protection tunnel in BGP/MPLS VPNs and in IP networks using encapsulation.

No abstract available.

Multiple areas in OSPF have been introduced to improve the scalability of IGP routing in large networks. The principle is to partition the links of the network into areas, each link belonging to a single area. In this paper, we show that the way OSPF routers compute their routes makes it possible for deflection to arise, i.e. the forwarding path followed by IP packets differs from the routing path computed by the routing protocol. We give a necessary and sufficient condition for deflection to arise in a domain, and describe how to detect it. The goal is to provide a tool to decide where to establish OSPF virtual links to remove the deflection. The detection of deflection will be implemented in C-BGP [1], an open-source routing solver.

When the topology of an IP network changes due to a link failure or a link metric modification, the routing tables of all the routers must be updated. Each of those updates may cause transient loops. In this paper, we prove that by ordering the updates of the routing tables on the routers, it is possible to avoid all transient loops during the convergence of ISIS or OSPF after a planned link failure, an unplanned failure of a protected link and after a link metric modification. We then propose a protocol that allows the routers to order the update of their routing tables to avoid transient loops without requiring any complex computation.

We present a robust and reproducible method to map the main land cover classes in an irrigated area near Marrakech (bare soil, herbaceous crops, trees on bare soil, trees on herbaceous understory), using a time series of 9 SPOT high resolution images. The images were first radiometrically corrected in reflectance using a physical model (SMAC), and then applying an adjustment based on invariant objects located on the scene. The 9 images were then used to generate a NDVI profile for each pixel, which was analyzed using simple decision rules to assign it to a landcover class, considering simple criteria like the minimum, maximum, and dynamics of the NDVI.