In video-on-demand services, each video title is deployed as a bitrate ladder—a set of pre-encoded representations with increasing bitrate and quality. This paper introduces NILO, a Nested and Iterative Ladder Optimization method for designing bitrate ladders in video streaming services. NILO balances the tradeoffs between user Quality of Experience (QoE) and Content Delivery Network (CDN) efficiency, while meeting the operational needs of large-scale production systems. Our contributions include a multi-objective optimization framework that captures QoE and CDN efficiency during ladder construction, and a novel method that uniquely integrates standard optimization components to address this complex problem. We evaluate NILO at a large video streamer using trace-driven simulations and an A/B test in production with over one million users. Our results show that NILO achieves significant efficiency gains while maintaining QoE comparable to highly tuned production ladders. Specifically, NILO reduces storage by approximately 20% and streaming rate by about 2%, with options for greater efficiency gains at the cost of modest QoE degradation.

Several systems rely on traceroute to track a large number of Internet paths as they change over time. Monitoring systems perform this task by remapping paths periodically or whenever a change is detected. This paper shows that such complete remapping is inefficient, because most path changes are localized to a few hops of a path. We develop RemapRoute, a tool to remap a path locally given the previously known path and a change point. RemapRoute sends targeted probes to locate and remap the often few hops that have changed. Our evaluation with trace-driven simulations and in a real deployment shows that local remapping reduces the average number of probes issued during remapping by 63% and 79%, respectively, when compared with complete remapping. At the same time, our results show that local remapping has little impact on the accuracy of inferred paths.

On-demand streaming video traffic is managed by an adaptive bi-trate (ABR) algorithm whose job is to optimize quality of experience (QoE) for a single video session. ABR algorithms leave the question of sharing network resources up to transport-layer algorithms. We observe that as the internet gets faster relative to video streaming rates, this delegation of responsibility gives video traffic a burstier on-off traffic pattern. In this paper, we show we can substantially smooth video traffic to improve its interactions with the rest of the internet, while maintaining the same or better QoE for streaming video. We smooth video traffic with two design principles: application-informed pacing, which allows ABR algorithms to set an upper limit on packet-by-packet throughput, and by designing ABR algorithms that work with pacing. We propose a joint ABR and rate-control scheme, called Sammy, which selects both video quality and pacing rates. We implement our scheme and evaluate it at a large video streaming service. Our approach smooths video, making it a more friendly neighbor to other internet applications. One surprising result is that being friendlier requires no compromise for the video traffic: in large scale, production experiments, Sammy improves video QoE over an existing, extensively tested and tuned production ABR algorithm.

Internet-wide scanning is commonly used to understand the topology and security of the Internet. However, IPv4 Internet scans have been limited to scanning only a subset of services---exhaustively scanning all IPv4 services is too costly and no existing bandwidth-saving frameworks are designed to scan IPv4 addresses across all ports. In this work we introduce GPS, a system that efficiently discovers Internet services across all ports. GPS runs a predictive framework that learns from extremely small sample sizes and is highly parallelizable, allowing it to quickly find patterns between services across all 65K ports and a myriad of features. GPS computes service predictions in 13 minutes (four orders of magnitude faster than prior work) and finds 92.5% of services across all ports with 131× less bandwidth, and 204× more precision, compared to exhaustive scanning. GPS is the first work to show that, given at least two responsive IP addresses on a port to train from, predicting the majority of services across all ports is possible and practical.

Web performance anomalies (e.g. time periods when metrics like page load time are abnormally high) have significant impact on user experience and revenues of web service providers. Existing methods to automatically detect web performance anomalies focus on popular websites (e.g. with tens of thousands of visits per minute). Across a wider diversity of websites, however, the number of visits per hour varies enormously, and some sites will only have few visits per hour. Low rates of visits create measurement gaps and noise that prevent the use of existing methods. This paper develops WMF, a web performance anomaly detection method applicable across a range of websites with highly variable measurement volume. To demonstrate our method, we leverage data from a website monitoring company, which allows us to leverage cross-site measurements. WMF uses matrix factorization to mine patterns that emerge from a subset of the websites to "fill in" missing data on other websites. Our validation using both a controlled website and synthetic anomalies shows that WMF's F1-score is more than double that of the state-of-the-art method. We then apply WMF to three months of web performance measurements to shed light on performance anomalies across a variety of 125 small to medium websites.

Recent advances in programmable data planes, software-defined networking, and the adoption of IPv6 support novel, more complex load balancing strategies. We introduce the Multipath Classification Algorithm (MCA), a probing algorithm that extends traceroute to identify and classify load balancing in Internet routes. MCA extends existing formalism and techniques to consider that load balancers may use arbitrary combinations of bits in the packet header for load balancing. We propose optimizations to reduce probing cost that are applicable to MCA and existing load balancing measurement techniques. Through large-scale measurement campaigns, we characterize and study the evolution of load balancing on the IPv4 and IPv6 Internet with multiple transport protocols. Our results show that load balancing is more prevalent and that load balancing strategies are more mature than previous characterizations have found.

Poor Wi-Fi quality can disrupt home users' internet experience, or the Quality of Experience (QoE). Detecting when Wi-Fi degrades QoE is extremely valuable for residential Internet Service Providers (ISPs) as home users often hold the ISP responsible whenever QoE degrades. Yet, ISPs have little visibility within the home to assist users. Our goal is to develop a system that runs on commodity access points (APs) to assist ISPs in detecting when Wi-Fi degrades QoE. Our first contribution is to develop a method to detect instances of poor QoE based on the passive observation of Wi-Fi quality metrics available in commodity APs (e.g., PHY rate). We use support vector regression to build predictors of QoE given Wi-Fi quality for popular internet applications. We then use K-means clustering to combine per-application predictors to identify regions of Wi-Fi quality where QoE is poor across applications. We call samples in these regions as poor QoE samples. Our second contribution is to apply our predictors to Wi-Fi metrics collected over one month from 3479 APs of customers of a large residential ISP. Our results show that QoE is good most of the time, still we find 11.6% of poor QoE samples. Worse, approximately 21% of stations have more than 25% poor QoE samples. In some cases, we estimate that Wi-Fi quality causes poor QoE for many hours, though in most cases poor QoE events are short.

One of the limits of web content discovery tools, let them be recommender systems or content curation tools such as social rating, social bookmarking and other social media, is the scarcity of user input (e.g. rate, submit, share). This problem is even worse in the case of what we call communities of a place: people who study, live or work at the same place. Such people often share common interests but either do not know each other or fail to actively engage in submitting and relaying information. In this paper, we investigate the feasibility of using the aggregated clicks of entire communities of users to passively emulate a content curation service a la Reddit. To this end, we prototype and deploy WeBrowse, a content curation service based on the processing of raw HTTP logs. Evaluation based on our deployments demonstrates feasibility at scale while respecting user privacy. The majority of WeBrowse's users welcome the quality of content it promotes.

Routing events impact multiple paths in the Internet, but current active topology mapping techniques monitor paths independently. Detecting a routing event on one Internet path does not trigger any measurements on other possibly-impacted paths. This approach leads to outdated and inconsistent routing information. We characterize routing events in the Internet and investigate probing strategies to efficiently identify paths impacted by a routing event. Our results indicate that targeted probing can help us quickly remap routing events and maintain more up-to-date and consistent topology maps.

Matching the profiles of a user across multiple online social networks brings opportunities for new services and applications as well as new insights on user online behavior, yet it raises serious privacy concerns. Prior literature has showed that it is possible to accurately match profiles, but their evaluation focused only on sampled datasets. In this paper, we study the extent to which we can reliably match profiles in practice, across real-world social networks, by exploiting public attributes, i.e., information users publicly provide about themselves. Today's social networks have hundreds of millions of users, which brings completely new challenges as a reliable matching scheme must identify the correct matching profile out of the millions of possible profiles. We first define a set of properties for profile attributes--Availability, Consistency, non-Impersonability, and Discriminability (ACID)--that are both necessary and sufficient to determine the reliability of a matching scheme. Using these properties, we propose a method to evaluate the accuracy of matching schemes in real practical cases. Our results show that the accuracy in practice is significantly lower than the one reported in prior literature. When considering entire social networks, there is a non-negligible number of profiles that belong to different users but have similar attributes, which leads to many false matches. Our paper sheds light on the limits of matching profiles in the real world and illustrates the correct methodology to evaluate matching schemes in realistic scenarios.

We present a demonstration of WTF (Where's The Fault?), a system that localizes performance problems in home and access networks. We implement WTF as custom firmware that runs in an off-the-shelf home router. WTF uses timing and buffering information from passively monitored traffic at home routers to detect both access link and wireless network bottlenecks.

In this paper, we implement and evaluate a system that predicts and tracks Internet path changes to maintain an up-to-date network topology. Based on empirical observations, we claim that monitors can enhance probing according to the likelihood of path changes. We design a simple predictor of path changes and show that it can be used to enhance probe targeting. Our path tracking system, called DTRACK, focuses probes on unstable paths and spreads probes over time to minimize the chances of missing path changes. Our evaluations of DTRACK with trace-driven simulations and with a prototype show that DTRACK can detect up to three times more path changes than traditional trace-route-based topology mapping techniques.

We measure Web performance bottlenecks in home broadband access networks and evaluate ways to mitigate these bottlenecks with caching within home networks. We first measure Web performance bottlenecks to nine popular Web sites from more than 5,000 broadband access networks and demonstrate that when the downstream throughput of the access link exceeds about 16 Mbits/s, latency is the main bottleneck for Web page load time. Next, we use a router-based Web measurement tool, Mirage, to deconstruct Web page load time into its constituent components (DNS lookup, TCP connection setup, object download) and show that simple latency optimizations can yield significant improvements in overall page load times. We then present a case for placing a cache in the home network and deploy three common optimizations: DNS caching, TCP connection caching, and content caching. We show that caching only DNS and TCP connections yields significant improvements in page load time, even when the user's browser is already performing similar independent optimizations. Finally, we use traces from real homes to demonstrate how prefetching DNS and TCP connections for popular sites in a home-router cache can achieve faster page load times.

We design predictors of user dissatisfaction with the performance of applications that use networking. Our approach combines user-level feedback with low level machine and networking metrics. The main challenges of predicting user dissatisfaction, that arises when networking conditions adversely affect applications, comes from the scarcity of user feedback and the fact that poor performance episodes are rare. We develop a methodology to handle these challenges. Our method processes low level data via quantization and feature selection steps. We combine this with user labels and employ supervised learning techniques to build predictors. Using data from 19 personal machines, we show how to build training sets and demonstrate that non-linear SVMs achieve higher true positive rates (around 0.9) than predictors based on linear models. Finally we quantify the benefits of building per-application predictors as compared to general predictors that use data from multiple applications simultaneously to anticipate user dissatisfaction.

Home gateways offer Internet connectivity for all devices in the home, allowing services such as telephony or gaming. However, typical home gateways do not include any mechanism to guarantee optimal performance when applications are competing for the same resources. In this paper we outline an application performance optimization approach for home networks. In particular we study the feasibility of application performance tracking on home gateways, which involves both identification of active applications and monitoring their performance. Our results show that although the home gateway has limited resources, it still has the capacity to do more than just forwarding packets. It can collect and export all the information needed to perform our application performance optimization.

We present the first large-scale analysis of Web performance bottlenecks as measured from broadband access networks, using data collected from extensive home router deployments. We analyze the limits of throughput on improving Web performance and identify the contribution of critical factors such as DNS lookups and TCP connection establishment to Web page load times. We find that, as broadband speeds continue to increase, other factors such as TCP connection setup time, server response time, and network latency are often dominant performance bottlenecks. Thus, realizing a "faster Web" requires not only higher download throughput, but also optimizations to reduce both client and server-side latency.

We study how potential attackers can identify accounts on different social network sites that all belong to the same user, exploiting only innocuous activity that inherently comes with posted content. We examine three specific features on Yelp, Flickr, and Twitter: the geo-location attached to a user's posts, the timestamp of posts, and the user's writing style as captured by language models. We show that among these three features the location of posts is the most powerful feature to identify accounts that belong to the same user in different sites. When we combine all three features, the accuracy of identifying Twitter accounts that belong to a set of Flickr users is comparable to that of existing attacks that exploit usernames. Our attack can identify 37% more accounts than using usernames when we instead correlate Yelp and Twitter. Our results have significant privacy implications as they present a novel class of attacks that exploit users' tendency to assume that, if they maintain different personas with different names, the accounts cannot be linked together; whereas we show that the posts themselves can provide enough information to correlate the accounts.

For analyzing network performance issues, there can be great utility in having the capability to measure directly from the perspective of end systems. Because end systems do not provide any external programming interface to measurement functionality, obtaining this capability today generally requires installing a custom executable on the system, which can prove prohibitively expensive. In this work we leverage the ubiquity of web browsers to demonstrate the possibilities of browsers themselves offering such a programmable environment. We present Fathom, a Firefox extension that implements a number of measurement primitives that enable websites or other parties to program network measurements using JavaScript. Fathom is lightweight, imposing < 3.2% overhead in page load times for popular web pages, and often provides 1 ms timestamp accuracy. We demonstrate Fathom's utility with three case studies: providing a JavaScript version of the Netalyzr network characterization tool, debugging web access failures, and enabling web sites to diagnose performance problems of their clients.

Users today connect to the Internet everywhere - from home, work, airports, friend's homes, and more. This paper characterizes how the performance of networked applications varies across networking environments. Using data from a few dozen end-hosts, we compare the distributions of RTTs and download rates across pairs of environments. We illustrate that for most users the performance difference is statistically significant. We contrast the influence of the application mix and environmental factors on these performance differences.

No abstract available.

This paper presents the design and evaluation of HomeNet Profiler, a tool that runs on an end-system in the home to collect data from home networks. HomeNet Profiler collects a wide range of measurements including: the set of devices, the set of services (with UPnP and Zeroconf), and the characteristics of the WiFi environment. Since the release of HomeNet Profiler in April 2011, we have collected data from over 2,400 distinct homes in 46 different countries.

This paper investigates to what extent it is possible to use traceroute-style probing for accurately tracking Internet path changes. When the number of paths is large, the usual traceroute based approach misses many path changes because it probes all paths equally. Based on empirical observations, we argue that monitors can optimize probing according to the likelihood of path changes. We design a simple predictor of path changes using a nearest neighbor model. Although predicting path changes is not very accurate, we show that it can be used to improve probe targeting. Our path tracking method, called DTrack, detects up to two times more path changes than traditional probing, with lower detection delay, as well as providing complete load-balancer information.

We present the first study of network access link performance measured directly from home gateway devices. Policymakers, ISPs, and users are increasingly interested in studying the performance of Internet access links. Because of many confounding factors in a home network or on end hosts, however, thoroughly understanding access network performance requires deploying measurement infrastructure in users' homes as gateway devices. In conjunction with the Federal Communication Commission's study of broadband Internet access in the United States, we study the throughput and latency of network access links using longitudinal measurements from nearly 4,000 gateway devices across 8 ISPs from a deployment of over 4,200 devices. We study the performance users achieve and how various factors ranging from the user's choice of modem to the ISP's traffic shaping policies can affect performance. Our study yields many important findings about the characteristics of existing access networks. Our findings also provide insights into the ways that access network performance should be measured and presented to users, which can help inform ongoing broader efforts to benchmark the performance of access networks.

Tools to measure Internet properties usually assume the existence of just one single path from a source to a destination. However, load-balancing capabilities, which create multiple active paths between two end-hosts, are available in most contemporary routers. This paper extends Paris trace route and proposes an extensive characterization of multipath routing in the Internet. We use Paris traceroute from RON and PlanetLab nodes to collect various datasets in 2007 and 2009. Our results show that the traditional concept of a single network path between hosts no longer holds. For instance, 39% of the source-destination pairs in our 2007 traces traverse a load balancer. This fraction increases to 72% if we consider the paths between a source and a destination network. In 2009, we notice a consolidation of per-flow and per-destination techniques and confirm that per-packet load balancing is rare.

This paper studies how intradomain routing instability relates to events in network trouble tickets for two networks: a VPN provider and the Internet2 backbone network. Our goal in performing this joint analysis of routing and trouble tickets is to better understand the likely underlying causes of intradomain routing instability. We develop a method to correlate trouble tickets with instability events and find that, although unplanned events last longer than scheduled maintenance, there is no single underlying cause for most instability, and that these causes differ across networks. In comparison to a similar study from Labovitz et al. from ten years ago, we find that, while certain causes of instability such as maintenance and circuit problems remain significant, power issues have become much less prevalent, and software-related problems have become more common.

Network equipments generate an overwhelming number of reports and alarms every day, but only a small fraction of these alarms require the intervention of network operators. Our goal is to build a system to automatically select the set of critical alarms, so that network operators can focus their time and effort on these critical events. As a first step, we focus on alarms from intradomain routing. Our key observation is that operators already use trouble ticketing systems to record all events that require their intervention. Hence, we can use the history of trouble tickets combined with intradomain routing messages to train a classifier. Then, we can apply this classifier online to process intradomain routing messages and single out the critical events. This paper shows the feasibility of this approach by using the k-nearest neighbor algorithm to build classifiers from IS-IS and trouble ticket data from two networks. Our results show that we can accurately pinpoint approximately 70% of critical events for both networks.

Researchers and network operators often say that BGP table transfers are slow. Despite this common knowledge, the reasons for slow BGP transfers are not well understood. This paper explains BGP table transfer delays by combining BGP messages collected at a large VPN provider backbone and controlled experiments with routers of three different vendors as well as a software BGP speaker. Our results show that table transfers both in the provider network and in the controlled experiments contain gaps, i.e., periods in which both the sending and receiving routers are idle, but no BGP routes are exchanged. Gaps can represent more than 90% of the table transfer time. Our analysis of a software router and discussions with router vendors indicate that gaps happen because of the timer-driven implementation of sending of BGP updates. Hence, gaps represent an undocumented design choice that gives preference to more controlled router load over faster table transfers.

Abstract: Binary tomography—the process of identifying faulty network links through coordinated end-to-end probes—is a promising method for detecting failures that the network does not automatically mask (e.g., network “blackholes”). Because tomography is sensitive to the quality of the input, however, naive end-to-end measurements can introduce inaccuracies. This paper develops two methods for generating inputs to binary tomography algorithms that improve their inference speed and accuracy. Failure confirmation is a per-path probing technique to distinguish packet losses caused by congestion from persistent link or node failures. Aggregation strategies combine path measurements from unsynchronized monitors into a set of consistent observations. When used in conjunction with existing binary tomography algorithms, our methods identify all failures that are longer than two measurement cycles while inducing relatively few false alarms. In two wide-area networks, our techniques decrease the number of alarms by as much as two orders of magnitude. Compared to the state of the art in

The automatic detection of failures in IP paths is an essential step for operators to perform diagnosis or for overlays to adapt. We study a scenario where a set of monitors send probes toward a set of target end-hosts to detect failures in a given set of IP interfaces. Unfortunately, there is a large probing cost to monitor paths between all monitors and targets at a very high frequency. We make two major contributions to reduce this probing cost. First, we propose a formulation of the probe optimization problem which, in contrast to the established formulation, is not NP complete. Second, we propose two linear programming algorithms to minimize probing cost. Our algorithms combine low frequency per-path probing to detect per-interface failures at a higher frequency. We analyze our solutions both analytically and experimentally. Our theoretical results show that the probing cost increases linearly with the number of interfaces in a random power-law graph. We confirm this linear increase in Internet graphs measured from PlanetLab and RON. Hence, Internet graphs belong to the most costly class of graph to probe.

Traceroute is widely used to report the path packets take between two Internet hosts, but the widespread deployment of load balancing routers breaks a basic assumption - that there is only a single such path. We specify an adaptive, stochastic probing algorithm, the multipath detection algorithm (MDA), to report all paths that probes can follow between a source and a destination. We establish the foundations of, and show how to calculate, rigorous statistical guarantees for the discovery of the entire multipath route. We explore algorithm cost/guarantee tradeoffs in real experiments and show the inadequacy of the classic practice of sending three probes per hop.

Network tomography is a promising technique to identify the location of of IP faults. The goal of tomography is to infer the status of network internal characteristics based on end-to-end observations. In particular, binary tomography identifies the set of failed links from end-to-end path meausrments. Upon detecting the failure of one or more of the monitored paths, a monitor sends its measurements to a central coordinator. The coordinator then runs the binary tomography algorithm, which takes as input the topology of the network and the status (i.e., up or down) of all monitored paths and finds the minimum set of links that explain the observations.

The current Internet offers a diverse set of applications for end-users (e.g., online gaming, IPTV, VoIP, VoD). These applications require a timely delivery of packets to avoid the deterioration of user-perceived performance. Slow web-browsing, momentarily drops of voice in Internet telephony and lagging remote connections are some of the most common problems that affect the usability of Internet services. Ideally, if applications had access to measurements that quantify network performance, they could dynamically adapt to network conditions and improve user satisfaction. Most importantly, when application service quality falls below expectations, online measurements help users understand who to blame and what to do to bypass the problem.

Enterprises often have sites that are spread in distant locations. These sites need to interconnect with the same level of privacy as in a local-area network. Virtual Private Networks (VPNs) were introduced to serve this need. A common VPN technology uses Multiprotocol extensions for the Border Gateway Protocol (MP-BGP) and Multiprotocol Label Switching (MPLS). This technology allows a service provider to share its IP backbone among multiple VPN clients while preserving privacy. MPLS tunnels provide traffic isolation, whereas MP-BGP distributes VPN routes. Despite the wide deployment of BGP/MPLS VPNs[1], there have been only few studies to understand their behavior, mostly because of the lack of public data. Prior work focused on BGP convergence [3] and on integrity constraints to ensure connectivity [2].

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.

We call network events incidents that disturb the normal behavior of one or more elements of an IP network. Routers, network interface cards, and IP links can fail or malfunction for many reasons. For example, operators may need to reboot a router for a software upgrade, an interface card may crash, and IP links may be overloaded because of a denial-of-service attack. Any of these network events can impact customer's traffic (packets can be lost or delayed, and, in extreme cases, customers may lose connectivity to parts of the network). When customers complain, network operators need to intervene to diagnose and, hopefully, fix the problem. In this work, we characterize network events according to their causes by using data collected from the Virtual Private Network (VPN) backbone of a large European provider. The European VPN network do not connect to Internet, but interconnects sites of over ten thousand enterprise networks.

Tools to measure internet properties usually assume the existence of a single path from a source to a destination. However, load-balancing capabilities, which create multiple active paths between two end-hosts, are available in most contemporary routers. This paper proposes a methodology to identify load-balancing routers and characterize load-balanced paths. We enhance our traceroute-like tool, called Paris traceroute, to find all paths between a pair of hosts, and use it from 15 sources to over 68 thousand destinations. Our results show that the traditional concept of a single network path between hosts no longer holds. For instance, 39% of the source-destination pairs in our traces traverse a load balancer. Furthermore, this fraction increases to 70% if we consider the paths between a source and a destination network.

Traceroute [2] is used to learn the path between two machines in the internet. Uses range from the diagnosis of network problems to the assemblage of internet maps. Unfortunately, traceroute measurements can be inaccurate and incomplete when the measured route traverses a load balancer.

The automatic detection of applications associated with network traffic is an essential step for network security and traffic engineering. Unfortunately, simple port-based classification methods are not always efficient and systematic analysis of packet payloads is too slow. Most recent research proposals use flow statistics to classify traffic flows once they are finished, which limit their applicability for online classification. In this paper, we evaluate the feasibility of application identification at the beginning of a TCP connection. Based on an analysis of packet traces collected on eight different networks, we find that it is possible to distinguish the behavior of an application from the observation of the size and the direction of the first few packets of the TCP connection. We apply three techniques to cluster TCP connections: K-Means, Gaussian Mixture Model and spectral clustering. Resulting clusters are used together with assignment and labeling heuristics to design classifiers. We evaluate these classifiers on different packet traces. Our results show that the first four packets of a TCP connection are sufficient to classify known applications with an accuracy over 90% and to identify new applications as unknown with a probability of 60%.

Traceroute is widely used, from the diagnosis of network problems to the assemblage of internet maps. However, there are a few serious problems with this tool, in particular due to the presence of load balancing routers in the network. This paper describes a number of anomalies that arise in nearly all traceroute-based measurements. We categorize them as "loops", "cycles", and "diamonds". We provide a new publicly-available traceroute, called Paris traceroute, which controls packet header contents to obtain a more precise picture of the actual routes that packets follow. This new tool allows us to find conclusive explanations for some of the anomalies, and to suggest possible causes for others.

The separation of intradomain and interdomain routing has been a key feature of the Internet's routing architecture from the early days of the ARPAnet. However, the appropriate "division of labor" between the two protocols becomes unclear when an Autonomous System (AS) has interdomain routes to a destination prefix through multiple border routers---a situation that is extremely common today because neighboring domains often connect in several locations. We believe that the current mechanism of early-exit or hot-potato routing---where each router in an AS directs traffic to the "closest" border router based on the intradomain path costs---is convoluted, restrictive, and sometimes quite disruptive. In this paper, we propose a flexible mechanism for routers to select the egress point for each destination prefix, allowing network administrators to satisfy diverse goals, such as traffic engineering and robustness to equipment failures. We present one example optimization problem that uses integer-programming techniques to tune our mechanism to improve network robustness. Experiments with topology and routing data from two backbone networks demonstrate that our solution is both simple (for the routers) and expressive (for the network administrators).

Hot-potato routing is a mechanism employed when there are multiple (equally good) interdomain routes available for a given destination. In this scenario, the Border Gateway Protocol (BGP) selects the interdomain route associated with the closest egress point based upon intradomain path costs. Consequently, intradomain routing changes can impact interdomain routing and cause abrupt swings of external routes, which we call hot-potato disruptions. Recent work has shown that hot-potato disruptions can have a substantial impact on large ISP backbones and thereby jeopardize the network robustness. As a result, there is a need for guidelines and tools to assist in the design of networks that minimize hot-potato disruptions. However, developing these tools is challenging due to the complex and subtle nature of the interactions between exterior and interior routing. In this paper, we address these challenges using an analytic model of hot-potato routing that incorporates metrics to evaluate network sensitivity to hot-potato disruptions. We then present a methodology for computing these metrics using measurements of real ISP networks. We demonstrate the utility of our model by analyzing the sensitivity of a large AS in a tier~1 ISP network.

Despite the architectural separation between intradomain and interdomain routing in the Internet, intradomain protocols do influence the path-selection process in the Border Gateway Protocol (BGP). When choosing between multiple equally-good BGP routes, a router selects the one with the closest egress point, based on the intradomain path cost. Under such hot-potato routing, an intradomain event can trigger BGP routing changes. To characterize the influence of hot-potato routing, we conduct controlled experiments with a commercial router. Then, we propose a technique for associating BGP routing changes with events visible in the intradomain protocol, and apply our algorithm to AT&T's backbone network. We show that (i) hot-potato routing can be a significant source of BGP updates, (ii) BGP updates can lag 60 seconds or more behind the intradomain event, (iii) the number of BGP path changes triggered by hot-potato routing has a nearly uniform distribution across destination prefixes, and (iv) the fraction of BGP messages triggered by intradomain changes varies significantly across time and router locations. We show that hot-potato routing changes lead to longer delays in forwarding-plane convergence, shifts in the flow of traffic to neighboring domains, extra externally-visible BGP update messages, and inaccuracies in Internet performance measurements.

Internet Service Providers (ISPs) can exploit path diversity to balance load and improve robustness. Unfortunately, it is difficult to evaluate the potential impact of these approaches without routing and topological data, which are confidential. In this paper, we characterize path diversity in the real Sprint network. We then characterize path diversity in ISP topologies inferred using the Rocketfuel tool. Comparing the real Sprint topology to the one inferred by Rocketfuel, we find that the Rocketfuel topology has significantly higher apparent path diversity.(As a metric, path diversity is particularly sensitive to the presence of false or missing links, both of which are artifacts of active measurement techniques.) We evaluate heuristics that improve the accuracy of the inferred Rocketfuel topologies. Finally, we discuss limitations of active measurements techniques to capture topological properties such as path diversity.

No abstract available.