The widespread use of Smart Home devices has attracted significant research interest in understanding their behavior within home networks. Unlike general-purpose computers, these devices exhibit relatively simple and predictable network activity patterns. However, previous studies have primarily focused on normal network conditions, overlooking potential hidden patterns that emerge under challenging conditions. Discovering the latter is crucial for assessing device robustness.This paper addresses this gap by presenting a framework that systematically and automatically reveals these hidden communication patterns. By actively disturbing communication and blocking observed traffic, the framework generates comprehensive profiles structured as behavior trees, uncovering traffic flows that are missed by more shallow methods. This approach was applied to ten real-world devices, identifying 254 unique flows, with over 27% only discovered through this new method. These insights enhance our understanding of device robustness, and the thus obtained profiles provide a more complete description of the network behavior of devices, as needed, for example, for the configuration of security solutions.

BGP data collection platforms as currently architected face fundamental challenges that threaten their long-term sustainability. Inspired by recent work, we analyze, prototype, and evaluate a new optimization paradigm for BGP collection. Our system scales data collection with two components: analyzing redundancy between BGP updates and using it to optimize sampling of the incoming streams of BGP data. An appropriate definition of redundancy across updates depends on the analysis objective. Our contributions include: a survey, measurements, and simulations to demonstrate the limitations of current systems; a general framework and algorithms to assess and remove redundancy in BGP observations; and quantitative analysis of the benefit of our approach in terms of accuracy and coverage for several canonical BGP routing analyses such as hijack detection and topology mapping. Finally, we implement and deploy a new BGP peering collection system that automates peering expansion using our redundancy analytics, which provides a path forward for more thorough evaluation of this approach.

Dramatic growth in Internet connectivity poses a challenge for the resource-constrained data collection efforts that support scientific and operational analysis of interdomain routing. Inspired by tradeoffs made in other disciplines, we explore a fundamental reconceptualization to how we design public BGP data collection architectures: an overshoot-and-discard approach that can accommodate an order of magnitude increase in vantage points by discarding redundant data shortly after its collection. As defining redundant depends on the context, we design algorithms that filter redundant updates without optimizing for one objective, and evaluate our approach in terms of detecting two noteworthy phenomena using BGP data: AS-topology mapping and hijacks. Our approach can generalize to other types of Internet data (e.g., traceroute, traffic). We offer this study as a first step to a potentially new area of Internet measurement research.

Supporting such an all-to-all traffic matrix is challenging as it can easily lead to congestion. Scheduling patterns are designed to avoid such congestion by spreading the communications over time. The time is divided in phases and communications are spread across the phases. However, current scheduling algorithms are not fault-tolerant. In this paper we propose a fault-adaptive congestion-free scheduling to support an all-to-all exchange in fat tree topology. Our approach consist in the computation of the minimum number of communication phases required to support the all-to-all exchange with the available links, and of the scheduling of the communications on these phases. It enables to recover from failures and makes optimal use of the remaining bandwidth. We show that our scheduling approach provides better performance than the most common approach which is the Linear-shift scheduling. The throughput is improved by roughly 80% with our approach, for as little as one link failure.

Scrutinizing BGP routes is part of the everyday tasks that network operators and researchers conduct to monitor their networks and measure Internet routing. This task is facilitated by the expansion of routing information services such as RIPE RIS [2] and Route-Views [3] that collect BGP routes from an increasing number of Vantage Points (VPs). Unfortunately, while more data is often beneficial, in the case of BGP, it involves downloading and processing large volumes of route updates that exhibit a high level of redundancy. Today with more than one billion route updates collected every day, users often have no other option than to focus on a subset of the VP. Because of the highly skewed location of the VP, randomly selecting them may result in a lot of missing information.

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

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

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

The software architecture of most applications is more and more fragmented, and relying on micro-services. Moreover, some parts may be specialized, and a customer may choose to delegate a task to a service provider. In this situation, the customer must be sure to get results that comply with the task when they pay the service provider, and inversely. We propose a framework based on atomic swaps to enable such simultaneous exchanges. Our scheme is based on exchanging a transactional key during an atomic swap. Our framework protects both actors, and enables non-repudiation, from both sides, even in an asynchronous environment.

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

The growth of the Internet worldwide has been fuelled by the development of the “National Research and Education Networks” (NRENs), i.e., networks of academic and educational institutions. In Africa the establishment of NRENs is more recent. In this paper we analyse the readiness of African NRENs to be part of “The Things Network” (TTN), a network of IoT gateways that has fostered the growth of IoT in Europe by adopting a community network model. We analyse RTT and packet loss toward the nearest TTN network server, in African countries where RIPE Atlas (RIPE - “Réseaux IP Européens”, French for “European IP Networks”) probes are hosted both in academic and commercial networks. Our conclusion is that NRENs and commercial ISPs are on an equal foot in hosting TTN gateways in most countries we considered.

Pinpointing autonomous systems which deploy specific inter-domain techniques such as Route Flap Damping (RFD) or Route Origin Validation (ROV) remains a challenge today. Previous approaches to detect per-AS behavior often relied on heuristics derived from passive and active measurements. Those heuristics, however, often lacked accuracy or imposed tight restrictions on the measurement methods.

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

BGP reconvergence events involving a large number of prefixes may result in the loss of large amounts of traffic. Based on the observation that a very small number of prefixes carries the vast majority of traffic, we propose Power Prefixes Prioritization (PPP) to ensure the routes of these popular BGP prefixes converge first. By doing so, we significantly reduce the amount of traffic lost during reconvergence events. To achieve this, PPP obtains an ordered list of popular prefixes through traffic inspection, and configures the resulting prefix rank in the BGP routers to prioritize the processing and advertisement of BGP routes. We model the benefits of PPP over traditional BGP processing in terms of traffic loss for both generic and a Zipf traffic distribution, and we consider the impact of sampling in the process of obtaining the prefix rank. Applying the mechanism to real traffic traces obtained from WIDE, we show that PPP reduces the amount of traffic lost by an order of magnitude, even when we configure it to use conservative sampling rates. We prototype our proposal in Quagga to show the feasibility of its implementation, and we observe similar traffic loss reduction. PPP can be deployed incrementally, as it is implemented purely as a change in the router-internal BGP processing behavior.

Smart Cities need real time information to improve the efficiency of their transportation systems. In particular, crowd sensing may help to identify the current speed in each street, the congested areas, etc. In this context, map matching techniques are required to map a sequence of GPS waypoints into a set of streets on a common map. Unfortunately, most map matching approaches are probabilistic. We propose rather an unambiguous algorithm, able to identify all the possible paths that match a given sequence of waypoints. We need an unambiguous identification for each waypoints set. For instance, the actual speed should be assigned to the correct set of streets, without error. To identify all the possible streets, we construct the set of candidates iteratively. We identify all the edge candidates around each waypoint, and reconstruct all the possible sub-routes that connect them. We then verify a set of constraints, to eliminate impossible routes. The road segments common to all computed routes form an unambiguous match. We evaluate the matching ratio of our technique on real city maps (London, Paris and Luxembourg). We also validate our approach with a real GPS trace in Seattle.

Understanding data plane health is essential to improving Internet reliability and usability. For instance, detecting disruptions in distant networks can identify repairable connectivity problems. Currently this task is difficult and time consuming as operators have poor visibility beyond their network's border. In this paper we leverage the diversity of RIPE Atlas traceroute measurements to solve the classic problem of monitoring in-network delays and get credible delay change estimations to monitor network conditions in the wild. We demonstrate a set of complementary methods to detect network disruptions and report them in near real time. The first method detects delay changes for intermediate links in traceroutes. Second, a packet forwarding model predicts traffic paths and identifies faulty routers and links in cases of packet loss. In addition, we define an alarm score that aggregates changes into a single value per AS in order to easily monitor its sanity, reducing the effect of uninteresting alarms. Using only existing public data we monitor hundreds of thousands of link delays while adding no burden to the network. We present three cases demonstrating that the proposed methods detect real disruptions and provide valuable insights, as well as surprising findings, on the location and impact of the identified events.

In this paper, we propose the BGP Visibility Toolkit, a system for detecting and analyzing anomalous behavior in the Internet. We show that interdomain prefix visibility can be used to single out cases of erroneous demeanors resulting from misconfiguration or bogus routing policies. The implementation of routing policies with BGP is a complicated process, involving fine-tuning operations and interactions with the policies of the other active ASes. Network operators might end up with faulty configurations or unintended routing policies that prevent the success of their strategies and impact their revenues. As part of the Visibility Toolkit, we propose the BGP Visibility Scanner, a tool which identifies limited visibility prefixes in the Internet. The tool enables operators to provide feedback on the expected visibility status of prefixes. We build a unique set of ground-truth prefixes qualified by their ASes as intended or unintended to have limited visibility. Using a machine learning algorithm, we train on this unique dataset an alarm system that separates with 95% accuracy the prefixes with unintended limited visibility. Hence, we find that visibility features are generally powerful to detect prefixes which are suffering from inadvertent effects of routing policies. Limited visibility could render a whole prefix globally unreachable. This points towards a serious problem, as limited reachability of a non-negligible set of prefixes undermines the global connectivity of the Internet. We thus verify the correlation between global visibility and global connectivity of prefixes.

Public measurement platforms composed of low-end hardware devices such as RIPE Atlas have gained significant traction in the research community. Such platforms are indeed particularly interesting as they provide Internet-wide measurement capabilities together with an ever growing set of measurement tools. To be scalable though, they allow for concurrent measurements between users. This paper answers a fundamental question for any platform user: Do measurements launched by others impact my results? If so, what can I do about it?

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.

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.

Internet Service Providers (ISPs) need to balance multiple opposing objectives. On one hand, they strive to offer innovative services to obtain competitive advantages; on the other, they have to interconnect with potentially competing ISPs to achieve reachability, and coordinate with them for certain services. The complexity of balancing these objectives is reflected in the diversity of policies of the Border Gateway Protocol (BGP), the standard inter-domain routing protocol. Unforeseen interactions among the BGP policies of different ISPs can cause routing anomalies. In this work, we propose a methodology to allow ISPs to check their BGP policy configurations for guaranteed convergence to a single stable state. This requires that a set of ISPs share their configurations with each other, or with a trusted third party. Compared to previous approaches to BGP safety, we (1) allow ISPs to use a richer set of policies, (2) do not modify the BGP protocol itself, and (3) detect not only instability, but also multiple stable states. Our methodology is based on the extension of current theoretical frameworks to relax their constraints and use incomplete data. We believe that this provides a rigorous foundation for the design and implementation of safety checking tools.

Internet Service Providers (ISPs) use routing policies to implement the requirements of business contracts, manage traffic, address security concerns and increase scalability of their network. These routing policies are often a high-level expression of strategies or intentions of the ISP. They have meaning when viewed from a network-wide perspective (e.g., mark on ingress, filter on egress). However, configuring these policies for the Border Gateway Protocol (BGP) is undertaken at a low-level, on a per router basis. Unintended routing outcomes have been observed. In this work, we define a language that allows analysis of network-wide configurations at the high-level. This language aims at bridging the gap between router configurations and abstract mathematical models capable of capturing complex policies. The language can be used to verify desired properties of routing protocols and hence detect potential unintended states of BGP. The language is accompanied by a tool suite that parses router configuration languages (which by their nature are vendor-dependent) and translates them into vendor-independent representations of policies.

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.

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.

The Internet is organized as a collection of administrative domains, known as Autonomous Systems (ASes). These ASes interact through the Border Gateway Protocol (BGP) that allows them to share reachability information. Adjacent routers in distinct ASes use external BGP (eBGP), whereas in a given AS routes are propagated over internal BGP (iBGP) sessions between any pair of routers. In large ASes where a logical full-mesh is not possible, confederations or route reflectors (RRs) are used. However, these somewhat scalable alternatives have introduced their own set of unpredictable effects (persistent routing oscillations and forwarding loops causing an increase of the convergence time) addressed in the literature [1].

IP fast reroute techniques have been proposed for achieving fast failure recovery in just a few milliseconds. The basic idea of IP fast reroute is to reduce recovery time after failure by precomputing backup routes. A multiple routing configurations (MRC) algorithm has been proposed for obtaining IP fast reroute. MRC prepares backup configurations, which are used for finding a detour route after failure. On the other hand, requiring too many backup configurations consumes more network resources. It is necessary to recover more traffic flows with fewer backup configurations to ensure scalability. We propose a new backup configuration-creation algorithm for maximizing traffic flows which are fast recovered as much as possible under a limited number of backup configurations. The basic idea is to construct a spanning tree excluding failure links with higher link-loads in each backup configuration. We show that our algorithm has more robust on actual large IP networks.

The Internet has grown extremely fast in the last two decades. The number of routes to be supported by the routers has become very large. Moreover, the number of messages exchanged to distribute the routes has increased even faster. To keep up with the increase, network operators regularly have to perform costly upgrades of the routers. It is unclear whether advances in hardware will be able to keep up with the increasing routing load. More importantly, the large number of routes and iBGP messages negatively impacts iBGP convergence time leading to long connectivity losses. In this paper, we propose a scalable way to support the Internet routes in a Service Provider network. We make use of distributed servers that select routes on behalf of the routers. Then, routes are stored in a Distributed Hash Table (DHT). We adapted the concept of DHT for that purpose. Each router maintains its share of Internet routes in addition to a cache of routes currently in use to forward the Internet traffic. We call our proposal SpliTable. We show that our proposal is more scalable in the number of routes supported in each router than current iBGP route distribution solutions. Moreover, the number of control messages exchanged with our proposal is bounded contrary to current sparse iBGP route distribution solutions which may never converge.

In a service provider (SP) network, routes for external destinations are distributed on iBGP sessions. This traditionally required the establishment of a full-mesh of iBGP sessions in the network. A common practice is now to make use of route reflectors (RR). Such a practice is more scalable in the number of iBGP sessions to be configured in a SP network. However, it has been shown that RRs have a negative impact on the diversity of routes available in the network. This is an important issue as routers may not be able to quickly use an alternate route in case of a route failure. In this paper we tackle the problem of route diversity in a service provider network composed of RRs. We propose an algorithm to design iBGP session topologies with improved route diversity. We rely on an initial route reflection topology. Our algorithm proposes the addition of a few iBGP sessions to some border routers of the domain. These border routers receive a large number of external routes for which routers lack diversity. We show by means of simulations that our algorithm meets its goals. In the resulting topologies, each BGP router knows at least two different ways to reach distant destinations. This is ensured as long as a prefix advertisement is received at different nodes at the border of the AS. Secondly, we observe that the number of iBGP sessions required to achieve this goal is significantly below the number of sessions required in the case of a full-mesh. Finally, the remaining lack of route diversity after the use of our design algorithm indicates that new external peering sessions should be established. In this case, our algorithm shows that diversity cannot be reached for some prefixes independently of the iBGP topology, with the current external peering sessions.

No abstract available.