The predominant use of wireless access networks is for media streaming applications. However, current access networks treat all packets identically, and lack the agility to determine which clients are most in need of service at a given time. Software reconfigurability of networking devices has seen wide adoption, and this in turn implies that agile control policies can be now instantiated on access networks. Exploiting such reconfigurability requires the design of a system that can enable a configuration, measure the impact on the application performance (Quality of Experience), and adaptively select a new configuration. Effectively, this feedback loop is a Markov Decision Process whose parameters are unknown. The goal of this work is to develop QFlow, a platform that instantiates this feedback loop, and instantiate a variety of control policies over it. We use the popular application of video streaming over YouTube as our use case. Our context is priority queueing, with the action space being that of determining which clients should be assigned to each queue at each decision period. We first develop policies based on model-based and model-free reinforcement learning. We then design an auction-based system under which clients place bids for priority service, as well as a more structured index-based policy. Through experiments, we show how these learning-based policies on QFlow are able to select the right clients for prioritization in a high-load scenario to outperform the best known solutions with over 25% improvement in QoE, and a perfect QoE score of 5 over 85% of the time.

Artificial Intelligence (AI) has the potential to leverage the immense amount of operational data of clouds, services, and social and communication networks. As a concrete example, AI techniques have been adopted by telcom operators to develop virtual assistants based on advances in natural language processing (NLP) for interaction with customers and machine learning (ML) to enhance the customer experience by improving customer flow. Machine learning has also been applied to finding fraud patterns which enables operators to focus on dealing with the activity as opposed to the previous focus on detecting fraud.

Network and Service analytics can harness the immense stream of operational data from clouds, to services, to social and communication networks. In the era of big data and connected devices of all varieties, analytics and machine learning have found ways to improve reliability, configuration, performance, fault and security management. In particular, we see a growing trend towards using machine learning, artificial intelligence and data analytics to improve operations and management of information technology services, systems and networks.

Wireless Internet access has brought legions of heterogeneous applications all sharing the same resources. However, current wireless edge networks that cater to worst or average case performance lack the agility to best serve these diverse sessions. Simultaneously, software reconfigurable infrastructure has become increasingly mainstream to the point that dynamic per packet and per flow decisions are possible at multiple layers of the communications stack. Exploiting such reconfigurability requires the design of a system that can enable a configuration, measure the impact on the application performance (Quality of Experience), and adaptively select a new configuration. Effectively, this feedback loop is a Markov Decision Process whose parameters are unknown. The goal of this work is to design, develop and demonstrate QFlow that instantiates this feedback loop as an application of reinforcement learning (RL). Our context is that of reconfigurable (priority) queueing, and we use the popular application of video streaming as our use case. We develop both model-free and model-based RL approaches that are tailored to the problem of determining which clients should be assigned to which queue at each decision period. Through experimental validation, we show how the RL-based control policies on QFlow are able to schedule the right clients for prioritization in a high-load scenario to outperform the status quo, as well as the best known solutions with over 25% improvement in QoE, and a perfect QoE score of 5 over 85% of the time.

Given the increasing scarcity of IPv4 addresses, network operators are resorting to measures to expand their address pool or prolong the life of existing addresses. One such approach is Carrier-Grade NAT (CGN), where many end-users in a network share a single public IPv4 address. There is limited data about the prevalence of CGN, despite the implications on performance, security, and ultimately, the adoption of IPv6. In this work, we present passive measurement-based techniques for detecting CGN deployments across the entire Internet, without the requirement of access to machines behind a CGN. Specifically, we identify patterns in how client IP addresses are observed at M-Lab servers and at the UCSD network telescope to infer whether those clients are behind a CGN. We apply our methods on data collected from 2014 to 2016. We find that CGN deployment is increasing rapidly. Overall, we infer that 4.1K autonomous systems are deploying CGN, 6 times the number inferred by the most recent studies.

There is significant interest in the technical and policy communities regarding the extent, scope, and consumer harm of persistent interdomain congestion. We provide empirical grounding for discussions of interdomain congestion by developing a system and method to measure congestion on thousands of interdomain links without direct access to them. We implement a system based on the Time Series Latency Probes (TSLP) technique that identifies links with evidence of recurring congestion suggestive of an under-provisioned link. We deploy our system at 86 vantage points worldwide and show that congestion inferred using our lightweight TSLP method correlates with other metrics of interconnection performance impairment. We use our method to study interdomain links of eight large U.S. broadband access providers from March 2016 to December 2017, and validate our inferences against ground-truth traffic statistics from two of the providers. For the period of time over which we gathered measurements, we did not find evidence of widespread endemic congestion on interdomain links between access ISPs and directly connected transit and content providers, although some such links exhibited recurring congestion patterns. We describe limitations, open challenges, and a path toward the use of this method for large-scale third-party monitoring of the Internet interconnection ecosystem.

The goal of this work is to investigate the prevalence, causes, and impact of congestion on the African IXP substrate. Towards this end, we deployed Ark probes (within networks peering) at six African IXPs and ran the time-sequence latency probes (TSLP) algorithm, thereby collecting latency measurements to both ends of each mapped AS link for a whole year. We were able to detect congestion events and quantify their periods and magnitudes at four IXPs. We then verified the events and investigated the causes by interviewing the IXP operators. Our results show that only 2.2% of the discovered IP links experienced (sustained or transient) congestion during our measurement period. Our findings suggest the need for ISPs to carefully monitor the provision of their peering links, so as to avoid or quickly mitigate the occurrence of congestion. Regulators may also define the maximum level of packet loss in those links to provide some protection to communications routed through local IXPs.

The right vantage point is critical to the success of any active measurement. However, most research groups cannot afford to design, deploy, and maintain their own network of measurement endpoints, and thus rely measurement infrastructure shared by others. Unfortunately, the mechanism by which we share access to measurement endpoints today is not frictionless; indeed, issues of compatibility, trust, and a lack of incentives get in the way of efficiently sharing measurement infrastructure.

We develop and validate Internet path measurement techniques to distinguish congestion experienced when a flow self-induces congestion in the path from when a flow is affected by an already congested path. One application of this technique is for speed tests, when the user is affected by congestion either in the last mile or in an interconnect link. This difference is important because in the latter case, the user is constrained by their service plan (i.e., what they are paying for), and in the former case, they are constrained by forces outside of their control. We exploit TCP congestion control dynamics to distinguish these cases for Internet paths that are predominantly TCP traffic. In TCP terms, we re-articulate the question: was a TCP flow bottlenecked by an already congested (possibly interconnect) link, or did it induce congestion in an otherwise idle (possibly a last-mile) link?

We revisit the use of crowdsourced throughput measurements to infer and localize congestion on end-to-end paths, with particular focus on points of interconnections between ISPs. We analyze three challenges with this approach. First, accurately identifying which link on the path is congested requires fine-grained network tomography techniques not supported by existing throughput measurement platforms. Coarse-grained network tomography can perform this link identification under certain topological conditions, but we show that these conditions do not always hold on the global Internet. Second, existing measurement platforms provide limited visibility of paths to popular web content sources, and only capture a small fraction of interconnections between ISPs. Third, crowdsourcing measurements inherently risks sample bias: using measurements from volunteers across the Internet leads to uneven distribution of samples across time of day, access link speeds, and home network conditions. Finally, it is not clear how large a drop in throughput to interpret as evidence of congestion. We investigate these challenges in detail, and offer guidelines for deployment of measurement infrastructure, strategies, and technologies that can address empirical gaps in our understanding of congestion on the Internet.

End-to-end IPv6 performance is a factor that can influence IPv6 adoption. The stability of IPv6 - both in the control and data plane - is an important determinant of end-to-end performance, as it influences packet loss, network latency, and hence application performance. In this paper we compare stability and performance measurements from the control and data plane in IPv6 and IPv4. To study control plane stability, we use BGP feeds from five dual-stacked vantage points to measure routing dynamics towards IPv4 and IPv6 destinations. To study data plane stability, we probe dual-stacked webservers in 629 target ASes to determine the availability, RTT performance and RTT stability of paths toward these targets. In both control and data plane experiments IPv6 exhibited less stability than IPv4. In the control plane, most routing dynamics were generated by a small fraction of pathological unstable prefixes. In the data-plane, episodes of unavailability were longer on IPv6 than on IPv4. We found evidence of correlated performance degradation over IPv4 and IPv6 caused by shared infrastructure.

Peering in the Internet interdomain network has long been considered a “black art”, understood in-depth only by a select few peering experts while the majority of the network operator community only scratches the surface employing conventional rules-of-thumb to form peering links through ad hoc personal interactions. Why is peering considered a black art? What are the main sources of complexity in identifying potential peers, negotiating a stable peering relationship, and utility optimization through peering? How do contemporary operational practices approach these problems? In this work we address these questions for Tier-2 Network Service Providers. We identify and explore three major sources of complexity in peering: (a) inability to predict traffic flows prior to link formation (b) inability to predict economic utility owing to a complex transit and peering pricing structure (c) computational infeasibility of identifying the optimal set of peers because of the network structure. We show that framing optimal peer selection as a formal optimization problem and solving it is rendered infeasible by the nature of these problems. Our results for traffic complexity show that 15% NSPs lose some fraction of customer traffic after peering. Additionally, our results for economic complexity show that 15% NSPs lose utility after peering, approximately, 50% NSPs end up with higher cumulative costs with peering than transit only, and only 10% NSPs get paid-peering customers.

We introduce and demonstrate the utility of a method to localize and quantify inter-domain congestion in the Internet. Our Time Sequence Latency Probes (TSLP) method depends on two facts: Internet traffic patterns are typically diurnal, and queues increase packet delay through a router during periods of adjacent link congestion. Repeated round trip delay measurements from a single test point to the two edges of a congested link will show sustained increased latency to the far (but not to the near) side of the link, a delay pattern that differs from the typical diurnal pattern of an uncongested link. We describe our technique and its surprising potential,carefully analyze the biggest challenge with the methodology (interdomain router-level topology inference), describe other less severe challenges, and present initial results that are sufficiently promising to motivate further attention to overcoming the challenges.

Peering agreements between Autonomous Systems affect not only the flow of interdomain traffic but also the economics of the entire Internet ecosystem. The conventional wisdom is that transit providers are selective in choosing their settlement-free peers because they prefer to offer revenue-generating transit service to others. Surprisingly, however, a large percentage of transit providers use an Open peering strategy. What causes this large-scale adoption of Open peering, especially among transit providers? More importantly, what is the impact of this peering trend on the economic performance of the population of transit providers? We approach these questions through game-theoretic modeling and agent-based simulations, capturing the dynamics of peering strategy adoption, inter-network formation and interdomain traffic flow. We explain why transit providers gravitate towards Open peering even though that move may be detrimental to their economic fitness. Finally, we examine the impact of an Open peering variant that requires some coordination among providers.

In February 2011 the Internet Assigned Numbers Authority (IANA) exhausted its free pool of IPv4 addresses, and the regional registries (RIRs) have started to run out of IPv4 addresses as well. As RIRs have started rationing allocations, IPv4 transfer markets have emerged as a new mechanism to acquire IPv4 addresses. Barring a few high-profile exceptions, IPv4 transfers have largely flown under the radar. In this work, we use the lists of transfers published by three RIRs to characterise the transfer market - the types of players involved, the sizes and characteristics of transferred address blocks, and the visibility of transferred address blocks in the routing table before and after the transfer. Next, we take first steps toward detecting address transfers using BGP data from the Routeviews and RIPE repositories from 2004-2013. We identify reasons why legitimate changes in prefix origin could be mistakenly inferred to be transfers, and implement a series of 10 filters that remove 86% of candidate transfers. Our results indicate that BGP-based detection of transfers is prone to false positives due to significant noise in BGP data, while some transfers remain undetectable as they involve non-BGP speakers. We describe some additional data sources and analysis techniques that may help reveal an opaque market for IPv4 address block transfers.

We present the design and evaluation of ITMgen, a tool for generating synthetic but representative Interdomain Traffic Matrices (ITMs). ITMgen is motivated by the observation that gravity-based models do not reflect application level or regional characteristics of Internet traffic. ITMgen works at the level of connections, taking into account the relative sizes of ASes, their popularity with respect to various applications, and the relation between forward and reverse traffic for different application types. The necessary parameters for integrating application types and the distribution of content popularity can be realistically estimated by combining public sources like Alexa that capture traffic trends at a macro level with local traffic sampling (NetFlow, DPI) for providing an additional enhancement layer at the micro level. Using the above philosophy we demonstrate that we can synthesize ITMs that match real-world measurements closer than the current state of the art. In addition, the modular design philosophy of ITMgen makes it easy to integrate additional enhancement layers that improve the accuracy of our existing implementation.

Business relationships between ASes in the Internet are typically confidential, yet knowledge of them is essential to understand many aspects of Internet structure, performance, dynamics, and evolution. We present a new algorithm to infer these relationships using BGP paths. Unlike previous approaches, our algorithm does not assume the presence (or seek to maximize the number) of valley-free paths, instead relying on three assumptions about the Internet's inter-domain structure: (1) an AS enters into a provider relationship to become globally reachable; and (2) there exists a peering clique of ASes at the top of the hierarchy, and (3) there is no cycle of p2c links. We assemble the largest source of validation data for AS-relationship inferences to date, validating 34.6% of our 126,082 c2p and p2p inferences to be 99.6% and 98.7% accurate, respectively. Using these inferred relationships, we evaluate three algorithms for inferring each AS's customer cone, defined as the set of ASes an AS can reach using customer links. We demonstrate the utility of our algorithms for studying the rise and fall of large transit providers over the last fifteen years, including recent claims about the flattening of the AS-level topology and the decreasing influence of tier-1 ASes on the global Internet.

We use historical BGP data and recent active measurements to analyze trends in the growth, structure, dynamics and performance of the evolving IPv6 Internet, and compare them to the evolution of IPv4. We find that the IPv6 network is maturing, albeit slowly. While most core Internet transit providers have deployed IPv6, edge networks are lagging. Early IPv6 network deployment was stronger in Europe and the Asia-Pacific region, than in North America. Current IPv6 network deployment still shows the same pattern. The IPv6 topology is characterized by a single dominant player -- Hurricane Electric -- which appears in a large fraction of IPv6 AS paths, and is more dominant in IPv6 than the most dominant player in IPv4. Routing dynamics in the IPv6 topology are largely similar to those in IPv4, and churn in both networks grows at the same rate as the underlying topologies. Our measurements suggest that performance over IPv6 paths is comparable to that over IPv4 paths if the AS-level paths are the same, but can be much worse than IPv4 if the AS-level paths differ.

We propose an agent-based network formation model for the Internet at the Autonomous System (AS) level. The proposed model, called GENESIS, is based on realistic provider and peering strategies, with ASes acting in a myopic and decentralized manner to optimize a cost-related fitness function. GENESIS captures key factors that affect the network formation dynamics: highly skewed traffic matrix, policy-based routing, geographic co-location constraints, and the costs of transit/peering agreements. As opposed to analytical game-theoretic models, which focus on proving the existence of equilibria, GENESIS is a computational model that simulates the network formation process and allows us to actually compute distinct equilibria (i.e., networks) and to also examine the behavior of sample paths that do not converge. We find that such oscillatory sample paths occur in about 10% of the runs, and they always involve tier- 1 ASes, resembling the tier-1 peering disputes often seen in practice. GENESIS results in many distinct equilibria that are highly sensitive to initial conditions and the order in which ASes (agents) act. This implies that we cannot predict the properties of an individual AS in the Internet. However, certain properties of the global network or of certain classes of ASes are predictable. We also examine whether the underlying game is zero-sum, and identify three sufficient conditions for that property. Finally, we apply GENESIS in a specific “what-if” question, asking how the openness towards peering affects the resulting network in terms of topology, traffic flow and economics. Interestingly, we find that the peering openness that maximizes the fitness of different network classes (tier-1, tier-2 and tier-3 providers) closely matches that seen in real-world peering policies.

Our goal is to understand the evolution of the autonomous system (AS) ecosystem over the last 12 years. Instead of focusing on abstract topological properties, we classify ASs into a number of types depending on their function and business type. Furthermore, we consider the semantics of inter-AS links: customer-provider versus peering relations. We find that the available historic datasets from RouteViews and RIPE are not sufficient to infer the evolution of peering links, and so we restrict our focus to customer-provider links. Our findings highlight some important trends in the evolution of the Internet over the last 12 years and hint at what the Internet is heading toward. After an exponential increase phase until 2001, the Internet has settled into a slower exponential growth in terms of both ASs and inter-AS links. The growth is mostly due to enterprise networks and content/access providers at the periphery of the Internet. The average path length remains almost constant, mostly due to the increasing multihoming degree of transit and content/access providers. The AS types differ significantly from each other with respect to their rewiring activity; content/access providers are the most active. A few large transit providers act as “attractors” or “repellers” of customers. For many providers, strong attractiveness precedes strong repulsiveness by 3-9 months. Finally, in terms of regional growth, we find that the AS ecosystem is now larger and more dynamic in Europe than in North America.

Recent measurements and anecdotal evidence indicate that the Internet ecosystem is rapidly evolving from a multi-tier hierarchy built mostly with transit (customer-provider) links to a dense mesh formed with mostly peering links. This transition can have major impact on the global Internet economy as well as on the traffic flow and topological structure of the Internet. In this paper, we study this evolutionary transition with an agent-based network formation model that captures key aspects of the interdomain ecosystem, viz., interdomain traffic flow and routing, provider and peer selection strategies, geographical constraints, and the economics of transit and peering interconnections. The model predicts several substantial differences between the Hierarchical Internet and the Flat Internet in terms of topological structure, path lengths, interdomain traffic flow, and the profitability of transit providers. We also quantify the effect of the three factors driving this evolutionary transition. Finally, we examine a hypothetical scenario in which a large content provider produces more than half of the total Internet traffic.

The reconvergence of routing protocols in response to changes in network topology can impact application performance. While improvements in protocol specification and implementation have significantly reduced reconvergence times, increasingly performance-sensitive applications continue to raise the bar for these protocols. As such, monitoring the performance of routing protocols remains a critical activity for network operators. We design tool{}, a tool based on passive data plane measurements that we use in conjunction with control plane monitors for offline debugging and analysis of forwarding table dynamics. We discuss practical constraints that affect tool{}, and show how they can be addressed in real deployment scenarios. As an application of tool{}, we study forwarding table updates by backbone routers at a tier-1 ISP. We detect interesting behavior such as delayed forwarding table updates and routing loops due to buggy routers -- confirmed by network operators -- that are not detectable using traditional control plane monitors.

Our goal is to understand the evolution of the Autonomous System (AS) ecosystem over the last decade. Instead of focusing on abstract topological properties, we classify ASes into a number of "species" depending on their function and business type. Further, we consider the semantics of inter-AS links, in terms of customer-provider versus peering relations. We find that the available historic datasets from RouteViews and RIPE are not sufficient to infer the evolution of peering links, and so we restrict our focus to customer-provider links. Our findings highlight some important trends in the evolution of the Internet over the last decade, and hint at what the Internet is heading towards. After an exponential increase phase until 2001, the Internet now grows linearly in terms of both ASes and inter-AS links. The growth is mostly due to enterprise networks and content/access providers at the periphery of the Internet. The average path length remains almost constant mostly due to the increasing multihoming degree of transit and content/access providers. In recent years, enterprise networks prefer to connect to small transit providers, while content/access providers connect equally to both large and small transit providers. The AS species differ significantly from each other with respect to their rewiring activity; content/access providers are the most active. A few large transit providers act as "attractors" or "repellers" of customers. For many providers, strong attractiveness precedes strong repulsiveness by 3-9 months. Finally, in terms of regional growth, we find that the AS ecosystem is now larger and more dynamic in Europe than in North America.

The distributed nature of the Internet makes it difficult for a single service provider to troubleshoot the disruptions experienced by its customers. We propose NetDiagnoser, a troubleshooting algorithm to identify the location of failures in an internetwork environment. First, we adapt the well-known Boolean tomography technique to work in this environment. Then, we significantly extend this technique to improve the diagnosis accuracy in the presence of multiple link failures, logical failures (for instance, misconfigurations of route export filters), and incomplete topology inference. In particular, NetDiagnoser takes advantage of rerouted paths, routing messages collected at one provider's network and Looking Glass servers. We evaluate each feature of Net-Diagnoser separately using C-BGP simulations on realistic topologies. Our results show that NetDiagnoser can successfully identify a small set of links, which almost always includes the actually failed/misconfigured links.

Multihoming has been used by stub networks for several years as a form of redundancy, improving the availability of Internet access. More recently, Intelligent Route Control (IRC) products allow multihomed networks to dynamically switch parts of their egress or ingress traffic between ISPs, also improving cost and performance. IRC products assume that the set of upstream ISPs is given and fixed. Typically, however, a multihomed network has several ISP choices and the actual selection of ISPs can significantly affect cost, availability, and performance. In the first part of this work, we develop a methodology to select the best set of upstream ISPs, optimizing monetary cost and availability. Our results, based on measurements of actual Internet traffic and topology, show that the proposed algorithm selects the best possible set of ISPs in terms of resiliency to inter-AS single-link failures. The algorithm also performs well in the presence of double or triple link failures. In the second part of this work, we focus on the egress path selection problem. Specifically, we propose a stochastic search algorithm, based on simulated annealing, to allocate the network’s egress traffic between upstream ISPs. The objectives are to minimize cost, also ensuring that the selected paths to the major destinations of egress traffic are congestion-free. Simulation results show that the proposed algorithm performs very well in meeting the previous objectives, when congestion-free paths exist.

Packet buffers in router/switch interfaces constitute a central element of packet networks. The appropriate sizing of these buffers is an important and open research problem. Much of the previous work on buffer sizing modeled the traffic as an exogenous process, i.e., independent of the network state, ignoring the fact that the offered load from TCP flows depends on delays and losses in the network. In TCP-aware work, the objective has often been to maximize the utilization of the link, without considering the resulting loss rate. Also, previous TCP-aware buffer sizing schemes did not distinguish between flows that are bottlenecked at the given link and flows that are bottlenecked elsewhere, or that are limited by their size or advertised window. In this work, we derive the minimum buffer requirement for a drop-tail link, given constraints on the minimum utilization, maximum loss rate, and maximum queueing delay, when it is feasible to achieve all three constraints. Our results are applicable when most of the traffic (80-90%) at the given link is generated by large TCP flows that are bottlenecked at that link. For heterogeneous flows, we show that the buffer requirement depends on the harmonic mean of their round-trip times, and on the degree of loss synchronization. To limit the maximum loss rate, the buffer should be proportional to the number of flows that are bottlenecked at that link, when that number exceeds a certain threshold. The maximum queueing delay constraint, on the other hand, provides a simple upper bound on the buffer requirement. We also describe how to estimate the parameters of our buffer sizing formula from packet and loss traces, evaluate the proposed model with simulations, and compare it with two other buffer provisioning schemes.