With the increasing diffusion of Internet probing technologies, a large amount of regularly collected traceroutes are available for Internet service providers (ISPs) at low cost. We show how it is possible, given solely an arbitrary set of traceroutes, to spot routing paths that change similarly over time and aggregate them into inferred routing events. With respect to previous works, our approach does not require any knowledge of the network, does not need complex integration of several data sources, and exploits the asynchronicity of measurements to accurately position events in time. The formal model at the basis of our methodology revolves around the notion of empathy, a relation that binds similarly behaving traceroutes. The correctness and completeness of our approach are based on structural properties that are easily expressed in terms of empathic measurements. We perform experiments with data from public measurement infrastructures like RIPE Atlas, showing the effectiveness of our algorithm in distilling significant events from a large amount of traceroute data. We also validate the accuracy of the inferred events against ground-truth knowledge of routing changes originating from induced and spontaneous routing events. Given these promising results, we believe that our methodology can be an effective aid for troubleshooting at the ISPs level. The source code of our algorithm is publicly available at https://github.com/empadig.

Internet eXchange Points (IXPs) serve as landmarks where many network service providers meet to obtain reciprocal connectivity. Some of them, especially the largest, offer route servers as a convenient technology to simplify the setup of a high number of bi-lateral peerings. Due to their potential to support a quick and easy interconnection among the networks of multiple providers, IXPs are becoming increasingly popular and widespread, and route servers are exploited increasingly often. However, in an ever-growing level of market competition, service providers are pushed to develop concerns about many aspects that are strategic for their business, ranging from commercial agreements with other members of an IXP to the policies that are adopted in exchanging routing information with them. Although these aspects are notoriously sensitive for network service providers, current IXP architectures offer no guarantees to enforce the privacy of such business-critical information. We re-design a traditional route server and propose an approach to enforce the privacy of peering relationships and routing policies that it manages. Our proposed architecture ensures that nobody, not even a third party, can access such information unless it is the legitimate owner (i.e., the IXP member that set up the policy), yet allowing the route server to apply the requested policies and each IXP member to verify that such policies have been correctly deployed. We implemented the route server and tested our solutions in a simulated environment, tracking and analyzing the number of exchanged control plane messages.

In critical infrastructures, communication networks are used to exchange vital data among elements of Industrial Control Systems (ICSes). Due to the criticality of such systems and the increase of the cybersecurity risks in these contexts, best practices recommend the adoption of Intrusion Detection Systems (IDSes) as monitoring facilities. The choice of the positions of IDSes is crucial to monitor as many streams of data traffic as possible. This is especially true for the traffic patterns of ICS networks, mostly confined in many subnetworks, which are geographically distributed and largely autonomous. We introduce a methodology and a software architecture that allow an ICS operator to use the spare bandwidth that might be available in over-provisioned networks to forward replicas of traffic streams towards a single IDS placed at an arbitrary location. We leverage certain characteristics of ICS networks, like stability of topology and bandwidth needs predictability, and make use of the Software-Defined Networking (SDN) paradigm. We fulfill strict requirements about packet loss, for both functional and security aspects. Finally, we evaluate our approach on network topologies derived from real networks.

Federated networks have primarily emerged to support cloud computing services, in order to reduce costs for providers, as well as to increase their incomes. Up to now, the research activity has been mostly focused on architectures and cost models, setting aside technological aspects. In this paper, we propose SDNS, an SDN-system that opens the application fields of federated networks to federated connectivity services. By exploiting the centralized architecture offered by SDN and relying on the OpenFlow protocol, the most adopted enabler for SDN, we propose a way to easily interact with the Domain Name System (DNS) traffic in order to allow communication among multiple customers connected to different providers in presence of any type of IP address plan. We tested the scalability of our approach in a prototype implementation based on Netkit, a widely adopted simulation environment. We measured several control-plane overhead metrics, like the number of DNS, OpenFlow, and SDNS messages exchanged in the network. Our experiments show that the scalability of our method is essentially the same of the DNS service.

Mininet is the de-facto standard simulation environment for experimenting with SDN enabled networks based on the OpenFlow protocol. Although Mininet is powerful and not resource hungry, it has a strong limitation: it is not possible to use it for networks in which both OpenFlow and standard distributed routing protocols (e.g. Open Short Path First, OSPF) simultaneously run. In this paper we present SDNetkit, an enhanced release of the widely used Netkit network emulator that overcomes the limitation imposed by Mininet. We improved Netkit by adding all needed software to run OpenFlow based networks (e.g. OpenVSwitch and the Ryu framework). We show two use cases in which OpenFlow and standard protocols coexist. In particular, we address interoperability problems by presenting one use case in which OpenFlow nodes interact with standard ones (e.g. OSPF routers) in multi-domain networks, as well as one use case in which the OpenFlow protocol and OSPF run on the same machine, discussing some problems related to specific configurations. We believe that having the possibility to experiment SDN also in presence of interoperability scenarios results in opening to new research perspectives.

Network operators invest significant resources in monitoring and troubleshooting the infrastructure they run. Currently, the availability of large networks of probing devices, like, for example, RIPE Atlas, dramatically increases the amount of data an operator can rely on. In particular, the large amount of traceroutes they can produce are both an opportunity and a challenge. In this paper we provide a detailed description of RoutingWatch, a visual tool for interactively performing searches and analysis of routing events inferred from a large set of traceroutes. The key design choices of RoutingWatch are based on discussions with network operators. We evaluate the effectiveness of our approach by conducting a preliminary user study.

Software-Defined Networking (SDN) is a de-facto established approach that separates the packet switching functions of a device from its operational logic, which is controlled by a piece of software. Due to its potential for realizing new network architectures and services, a whole thread of scientific literature is devoted to SDN and its most adopted incarnation, OpenFlow. However, limited attention has been put in verifying the viability of the proposed approaches on currently available hardware. We address this deficiency through the following contributions: i) a critical review of the literature about SDN in terms of applicability issues stemming from publicly documented limitations of OpenFlow implementations; ii) a methodology for verifying the support of SDN-related functions in a network device, comprising an OpenFlow compliance test as well as custom targeted tests; iii) an application of the methodology to devices from 7 different vendors, unveiling extensive anomalous behaviors affecting even the most basic features; iv) a discussion of this outcome in terms of relevance of the discovered anomalies and of their implications on the applicability of state-of-the-art contributions on SDN. Besides taking a snapshot of the viability of research results, with this paper we intend to highlight aspects that operators should consider when picking SDN devices.

Federated networking is a promising approach to resource sharing that supports cost-effective services involving multiple parties. Research in this field largely focused on architectures and cost models, making limited progress on the technological side. On the other hand, the widely adopted Software-Defined Networking (SDN) model found its most successful application in data centers, exhibiting very little penetration in other scenarios. We leverage the unexplored potential of SDN on the edge of a network to introduce an approach that supports end-to-end connectivity among different federated partners. Our approach is based on simple Network Address and Port Translation (NAPT), making it applicable in standard IP networks. It is also very flexible, because it exploits SDN, and scalable, because address translations are performed on Customer Premises Equipment, where SDN is being progressively supported by device vendors. We define various alternative NAPT strategies and evaluate their effectiveness with simulations as well as emulated scenarios.

Summary In the era of virtualization, virtual networking plays an important role. Besides production use, virtual networking can be effectively adopted in many other contexts where accurate emulation of functionalities is important, like testing before deployment, evaluation of what‐if scenarios, research, and, increasingly, didactics. In this paper, we describe our 10‐year experience in designing, implementing, using, and maintaining Netkit, an environment for simple, inexpensive, and lightweight network emulation targeted at didactics. We analyze the peculiar requirements in this context and discuss how the architecture chosen for Netkit is tailored to fulfill them. We show that Netkit is particularly well suited for a quick preparation of complex network scenarios comprising a wide range of networking technologies. These scenarios can be specified using configuration languages that are similar to those used on real devices and, once set up, can be easily distributed via email or published on the Web. Netkit comes with a rich set of ready‐to‐use pre‐configured networks, accompanied by lecture slides that enable users to immediately experiment with specific case studies. To complete the picture, we report our experience in supporting and fostering the growth of the community of users revolving around Netkit: more than 15 educational institutions worldwide take advantage of Netkit, allowing teachers and students to practice with realistic networks without the need of expensive laboratories. We also detail how we profitably use Netkit within advanced academic‐level networking courses and related examinations at the Roma Tre University. Copyright © 2014 John Wiley & Sons, Ltd.

Multi Protocol Label Switching (MPLS) Virtual Private Networks (VPNs) have seen an unparalleled increasing adoption in the last decade. Although their flexibility as transport technology and their effectiveness for traffic engineering are well recognized, VPNs are difficult to set up and manage, due to the complexity of configurations, to the number of involved protocols, and to the limited control and predictability of network behaviors. On the other hand, Software-Defined Networking (SDN) is a consolidated, yet still emerging paradigm by which the control plane logic of a network device is implemented by an arbitrarily programmed software that runs outside the device itself. We conjugate the effectiveness of traditional VPNs with the programmability of SDN, proposing a novel and improved realization of MPLS VPNs based on SDN. With our approach, provisioning and setup of VPNs are accomplished by using a simple and flexible configuration language. Management and troubleshooting are facilitated because only a minimal set of technologies (notably, just MPLS) is retained. Control and predictability of network behaviors are enhanced by the centralized coordination enforced by the SDN controller. Besides illustrating our proposed approach and specifying the configuration language, we describe a prototype implementation of a controller and the outcome of tests we conducted in several configuration scenarios.

Virtual Private Networks (VPNs) implemented by Multi Protocol Label Switching (MPLS) tunnels appear in the service offer of many Internet Service Providers (ISPs). Due to the number of technologies that they involve and to the intricacy of their interactions, provisioning, setup, and maintenance of VPNs is a cumbersome task, whose complexity is usually mitigated by using advanced network management systems. We cut these difficulties at their roots by taking advantage of Software Defined Networking (SDN). We showcase the design and a prototype implementation of an SDN controller that, starting from a centralized specification of VPN settings expressed in a high-level simple and flexible language, automatically fills flow tables to implement the requested VPNs. Our implementation of VPNs with SDN promptly reacts to network dynamics (e.g., newly appeared links) and simplifies management a lot by dropping many unneeded technologies.

With the increasing diffusion of Internet probing technologies, a large amount of regularly collected traceroutes are available for Internet Service Providers (ISPs) at low cost. We introduce a practically applicable methodology and algorithm that, given solely an arbitrary set of traceroutes, spot routing paths that change similarly over time, aggregate them into inferred events, and report each event along with the impacted observation points and a small set of IP addresses that can help identify its cause. The formal model at the basis of our methodology revolves around the notion of empathy, a relation that binds similarly behaving traceroutes. The correctness and completeness of our approach are based on structural properties that are easily expressed in terms of empathic measurements. We perform experiments with data from public measurement infrastructures like RIPE Atlas, showing the effectiveness of our algorithm in distilling events from a large amount of traceroute data. We also validate the accuracy of the inferred events against ground-truth knowledge of routing changes originating from induced and spontaneous routing events. Given these promising results, we believe our methodology can be an effective aid for ISPs to detect and track routing changes affecting many users (with potentially adverse effects on their connection quality).

Internal routing inside an ISP network is the foundation for lots of services that generate revenue from the ISP's customers. A fine-grained control of paths taken by network traffic once it enters the ISP's network is therefore a crucial means to achieve a top-quality offer and, equally important, to enforce SLAs. Many widespread network technologies and approaches (most notably, MPLS) offer limited (e.g., with RSVP-TE), tricky (e.g., with OSPF metrics), or no control on internal routing paths. On the other hand, recent advances in the research community are a good starting point to address this shortcoming, but miss elements that would enable their applicability in an ISP's network. We extend pathlet routing by introducing a new control plane for internal routing that pursues the following qualities: it is designed to operate in the internal network of an ISP; it enables fine-grained management of network paths with suitable configuration primitives; it is scalable because routing changes are only propagated to the network portion that is affected by the changes; it supports independent configuration of specific network portions without the need to know the configuration of the whole network; it is robust thanks to the adoption of multipath routing; it supports the enforcement of QoS levels; it is independent of the specific data plane used in the ISP's network; it can be incrementally deployed and it can nicely coexist with other control planes. Besides formally introducing the dissemination mechanisms and algorithms of our control plane, we propose an experimental validation in the simulation framework OMNeT++ that we use to assess the effectiveness and scalability of our approach.

The flexibility and ease of setup of MPLS Virtual Private Networks (VPNs) and Virtual Private LAN Service (VPLS) motivate the large and growing user base of these services. It is therefore important for an Internet Service Provider (ISP) to ensure their uninterrupted operation, as also specified in service contracts. Although network monitoring is regarded as an essential activity to pursue this goal, existing monitoring approaches are often limited in the ability to capture the effects of VPN-related events such as reconfigurations and device failures. In this paper we provide several contributions: 1) a methodology to monitor the status of MPLS VPN and VPLS over time, which considers the BGP signaling messages sent by routers to propagate VPN information; the methodology is founded on an analysis of the observable effects of network events; it also envisions presenting the status of MPLS VPN and VPLS in an easy-to-understand visual form that allows to immediately spot potential anomalies; 2) an extensive discussion of the tradeoff between scalability of our monitoring approach and visibility of the effects of network events; 3) an architecture and prototype implementation of a tool based on our methodology; 4) a thorough experimentation of our approach in a realistic network scenario. As an example, the methodology allowed us to spot a subtle routing anomaly triggered by an implementation choice in the routing software used in our experiments.

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.

Compliance with the Gao-Rexford conditions [1] is perhaps the most realistic explanation of Internet routing stability, although BGP is renowned to be prone to oscillations. Informally, the Gao-Rexford conditions assume that (i) the business relationships between Internet Service Providers (ISPs) yield a hierarchy, (ii) each ISP behaves in a rational way, i.e., it does not offer transit to other ISPs for free, and (iii) each ISP ranks routes through customers better than routes through providers and peers.

We propose a novel, passive, nonintrusive method to measure the one-way delay ofallthe packets flowing between customer sites connected by a provider backbone. Our approach does not sample traffic and requires the injection of a negligible amount of control packets, possibly none. This is obtained by deploying a Measurement Agent in each customer site and exploiting a covert channel to carry information about each packet that transits between the Measurement Agents. Further, we address the theoretical problems of encoding measurement information into the very limited amount of bits made available by the covert channel, obtaining one-way delay measurements with predictable accuracy. Finally, we experimentally validate the applicability of our approach.

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.

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. Network protocol design literature introduced several sufficient conditions that routing policies should satisfy to guarantee convergence. However, to our knowledge, none of these conditions has yet been exploited to automatically check BGP policies for convergence.

For an Internet Service Provider (ISP), the knowledge of which interdomain paths could be traversed by its BGP announcements - and thus traffic flows - is essential to predict the impact of network faults, to develop effective traffic engineering and peering strategies, and to assess the quality of upstream providers. However, current methodologies do not provide this information. We present methodologies to discover how the BGP announcements for an ISP’s prefix are propagated through the Internet using withdrawals and specially crafted AS-sets. The techniques allow an ISP to determine which paths could be traversed in the presence of network faults or different routing policies on the ISP’s part and to deduce the routing policies of other ISPs with respect to its network. We validate our techniques through experimentation in the IPv6 and IPv4 Internet, showing that they can be safely and effectively applied in real-world situations.