A longstanding problem in computer privacy is that of data anonymization. One common approach is to present a query interface to analysts, and anonymize on a query-by-query basis. In practice, this approach often uses a standard database back end, and presents the query semantics of the database to the analyst.

There are a number of designs for an online advertising system that allow for behavioral targeting without revealing user online behavior or user interest profiles to the ad network. However, none of the proposed designs have been deployed in real-life settings. We present an effort to fill this gap by building and evaluating a fully functional prototype of a practical privacy-preserving ad system at a reasonably large scale. With more than 13K opted-in users, our system was in operation for over two months serving an average of 4800 active users daily. During the last month alone, we registered 790K ad views, 417 clicks, and even a small number of product purchases. In addition, our prototype is equipped with a differentially private data collection mechanism, which we used as the primary means for gathering experimental data. The data we collected show, for example, that our system obtained click-through rates comparable with those for Google display ads. In this paper, we describe our first-hand experience and lessons learned in running the first fully operational "private-by-design'' behavioral advertising and analytics system.

There is a growing body of research on mechanisms for preserving online user privacy while still allowing aggregate queries over private user data. A common approach is to store user data at users' devices, and to query the data in such a way that a differentially private noisy result is produced without exposing individual user data to any system component. A particular challenge is to design a system that scales well while limiting how much the malicious users can distort the result. This paper presents SplitX, a high-performance analytics system for making differentially private queries over distributed user data. SplitX is typically two to three orders of magnitude more efficient in bandwidth, and from three to five orders of magnitude more efficient in computation than previous comparable systems, while operating under a similar trust model. SplitX accomplishes this performance by replacing public-key operations with exclusive-or operations. This paper presents the design of SplitX, analyzes its security and performance, and describes its implementation and deployment across 416 users.

Existing IP anonymity systems tend to sacrifice one of low latency, high bandwidth, or resistance to traffic-analysis. High-latency mix-nets like Mixminion batch messages to resist traffic-analysis at the expense of low latency. Onion routing schemes like Tor deliver low latency and high bandwidth, but are not designed to withstand traffic analysis. Designs based on DC-nets or broadcast channels resist traffic analysis and provide low latency, but are limited to low bandwidth communication.

Today, websites commonly use third party web analytics services t obtain aggregate information about users that visit their sites. This information includes demographics and visits to other sites as well as user behavior within their own sites. Unfortunately, to obtain this aggregate information, web analytics services track individual user browsing behavior across the web. This violation of user privacy has been strongly criticized, resulting in tools that block such tracking as well as anti-tracking legislation and standards such as Do-Not-Track. These efforts, while improving user privacy, degrade the quality of web analytics. This paper presents the first design of a system that provides web analytics without tracking. The system gives users differential privacy guarantees, can provide better quality analytics than current services, requires no new organizational players, and is practical to deploy. This paper describes and analyzes the design, gives performance benchmarks, and presents our implementation and deployment across several hundred users.

Online tracking of users in support of behavioral advertising is widespread. Several researchers have proposed non-tracking online advertising systems that go well beyond the requirements of the Do-Not-Track initiative launched by the US Federal Trace Commission (FTC). The primary goal of these systems is to allow for behaviorally targeted advertising without revealing user behavior (clickstreams) or user profiles to the ad network. Although these designs purport to be practical solutions, none of them adequately consider the role of the ad auctions, which today are central to the operation of online advertising systems. This paper looks at the problem of running auctions that leverage user profiles for ad ranking while keeping the user profile private. We define the problem, broadly explore the solution space, and discuss the pros and cons of these solutions. We analyze the performance of our solutions using data from Microsoft Bing advertising auctions. We conclude that, while none of our auctions are ideal in all respects, they are adequate and practical solutions.

BGP Route Reflectors (RR), which are commonly used to help scale Internal BGP (iBGP), can produce oscillations, forwarding loops, and path inefficiencies. ISPs avoid these pitfalls through careful topology design, RR placement, and link-metric assignment. This paper presents Address-Based Route Reflection (ABRR): the first iBGP solution that completely solves all oscillation and looping problems, has no path inefficiencies, and puts no constraints on RR placement. ABRR does this by emulating the semantics of full-mesh iBGP, and thereby adopting the correctness and path efficiency properties of full-mesh iBGP. Both traditional Topology-Based Route Reflection (TBRR) and ABRR take a divide-and-conquer approach. While TBRR scales by making each RR responsible for all prefixes from some fraction of routers, ABRR scales by making each RR responsible for some fraction of prefixes from all routers. We have implemented a fully functional ABRR prototype. Using BGP data from a Tier-1 ISP, our analytical and implementation results show that ABRR's scaling and convergence properties compare positively with traditional TBRR.

IP Routers use sophisticated forwarding table (FIB) lookup algorithms that minimize lookup time, storage, and update time. This paper presents SMALTA, a practical, near-optimal FIB aggregation scheme that shrinks forwarding table size without modifying routing semantics or the external behavior of routers, and without requiring changes to FIB lookup algorithms and associated hardware and software. On typical IP routers using the FIB lookup algorithm Tree Bitmap, SMALTA shrinks FIB storage by at least 50%, representing roughly four years of routing table growth at current rates. SMALTA also reduces average lookup time by 25% for a uniform traffic matrix. Besides the benefits this brings to future routers, SMALTA provides a critical easy-to-deploy one-time benefit to the installed base should IPv4 address depletion result in increased routing table growth rate. The effective cost of this improvement is a sub-second delay in inserting updates into the FIB once every few hours. We describe SMALTA, prove its correctness, measure its performance using data from a Tier-1 provider as well as Route-Views. We also describe an implementation in Quagga that demonstrates its ease of implementation.

Online advertising supports many Internet services, such as search, email, and social networks. At the same time, there are widespread concerns about the privacy loss associated with user targeting. Yet, very little is publicly known about how ad networks operate, especially with regard to how they use user information to target users. This paper takes a first principled look at measurement methodologies for ad networks. It proposes new metrics that are robust to the high levels of noise inherent in ad distribution, identifies measurement pitfalls and artifacts, and provides mitigation strategies. It also presents an analysis of how three different classes of advertising -- search, contextual, and social networks, use user profile information today.

Fault management in networks is difficult. We argue that a major contributor to the difficulty of debugging network faults is the sheer volume of semantically anemic details exposed by protocols. Unlike past approaches that try to cope with the deluge of information exposed, in this paper we explore how to reduce and structure the management information exposed by data-plane protocols and devices to make them more amenable to fault management. To this effect, we delineate two conditions that the management interface of data-plane protocols should satisfy: it should provide a structured description of protocol reality and it should support what we call a "conservation of bytes" invariant. Based on this, we propose an architecture wherein data- plane protocols expose management information satisfying these conditions. This allows management applications to detect, localize and (possibly) resolve faults in a structured fashion. We discuss the detection of a representative set of real-world faults to illustrate our approach. We implemented these fault management features into three protocols and built a management application that uses the features to debug faults. Apart from serving as a proof of concept, this exercise indicates that our proposal does indeed simplify debugging of a large fraction of network faults.

This paper considers DoS attacks on DNS wherein attackers flood the nameservers of a zone to disrupt resolution of resource records belonging to the zone and consequently, any of its sub-zones. We propose a minor change in the caching behavior of DNS resolvers that can significantly alleviate the impact of such attacks. In our proposal, DNS resolvers do not completely evict cached resource records whose TTL has expired; rather, such resource records are stored in a separate "stale cache". If, during the resolution of a query, a resolver does not receive any response from the nameservers that are responsible for authoritatively answering the query, it can use the information stored in the stale cache to answer the query. In effect, the stale cache is the part of the global DNS database that has been accessed by the resolver and represents an insurance policy that the resolver uses only when the relevant DNS servers are unavailable. We analyze a 65-day DNS trace to quantify the benefits of a stale cache under different attack scenarios. Further, while the proposed change to DNS resolvers also changes DNS semantics, we argue that it does not adversely impact any of the fundamental DNS characteristics such as the autonomy of zone operators and hence, is a very simple and practical candidate for mitigating the impact of DoS attacks on DNS.

High-speed organizational networks running over leased fiber-optic lines or VPNs suffer from the well-known limitations of TCP over long-fat pipes. High-performance protocols like XCP require changes in the network. Other protocols like FastTCP assume nothing about the network but may not perform as well as network-aware protocols. In this paper, we present a new transport protocol that exploits the fact that these networks can offer priority queuing, thus finding the sweet spot between assuming too much and too little about the network. Our protocol splits a given transport flow into two prioritized flows. The higher priority flow operates with the legacy congestion control while the lower priority flow aggressively exploits spare capacity in the network while not interfering with the other participating flows. This isolation of the aggressive flow into strictly lower priority queues gives us more latitude in how to operate the aggressive component. We show through Emulab experiments of our implementation as well as simulations that this protocol can produce near-perfect goodputs in lossy networks, can considerably improve the completion time of short flows, and can sustain a high bottleneck utilization even in changing network conditions.

Finding the nearest peer, in terms of latency, is an important problem in many Internet applications. In this paper, we argue that existing solutions, which only examine inter-peer latencies as part of their operation will find it costly, in certain commonly occurring scenarios, to discover the nearest peer in P2P systems. The difficulty arises out of the way the PoP access networks are laid out in the Internet, where a single PoP (point of presence) belonging to an ISP provides connectivity to numerous client networks. This setup makes a group of peers all appear roughly the same distance from each other, leading to inefficiencies in the existing solutions. In this paper, we use large-scale measurements to show that the problematic topology does occur, use simulations of the Meridian closest-server algorithm to show that the condition does indeed lead to difficulty in finding the exact-closest peer, and propose solutions.

Networks are hard to manage and in spite of all the so called holistic management packages, things are getting worse. We argue that the difficulty of network management can partly be attributed to a fundamental flaw in the existing architecture: protocols expose all their internal details and hence, the complexity of the ever-evolving data plane encumbers the management plane. Guided by this observation, in this paper we explore an alternative approach and propose Complexity Oblivious Network Management (CONMan), a network architecture in which the management interface of data-plane protocols includes minimal protocol-specific information. This restricts the operational complexity of protocols to their implementation and allows the management plane to achieve high level policies in a structured fashion. We built the CONMan interface of a few protocols and a management tool that can achieve high-level configuration goals based on this interface. Our preliminary experience with applying this tool to real world VPN configuration indicates the architecture's potential to alleviate the difficulty of configuration management.

There have been many incidents of prefix hijacking in the Internet. The hijacking AS can blackhole the hijacked traffic. Alternatively, it can transparently intercept the hijacked traffic by forwarding it onto the owner. This paper presents a study of such prefix hijacking and interception with the following contributions: (1). We present a methodology for prefix interception, (2). We estimate the fraction of traffic to any prefix that can be hijacked and intercepted in the Internet today, (3). The interception methodology is implemented and used to intercept real traffic to our prefix, (4). We conduct a detailed study to detect ongoing prefix interception.

The current model for flow establishment in the Internet: DNS Names, IP addresses, and transport ports, is inadequate. Not all of the problem is due to the small IPv4 address space and resulting NAT boxes. Even where global addresses exist, firewalls cannot glean enough information about a flow from packet headers, and so often err, typically by being over-conservative: disallowing flows that might otherwise be allowed. This paper presents a novel architecture, protocol design, and implementation, for flow establishment in the Internet. The architecture, called NUTSS, takes into account the combined policies of endpoints and network providers. While NUTSS borrows liberally from other proposals (URI-like naming, signaling to manage ephemeral IPv4 or IPv6 data flows), NUTSS is unique in that it couples overlay signaling with data-path signaling. NUTSS requires no changes to existing protocol stacks, and combined with recent NAT traversal techniques, works with IPv4 and existing NAT/firewalls. This paper describes NUTSS and shows how it satisfies a wide range of "end-middle-end"network requirements, including access control, middlebox steering, multi-homing, mobility, and protocol negotiation.

As more and more Internet IP prefix hijacking incidents are being reported, the value of hijacking detection services has become evident. Most of the current hijacking detection approaches monitor IP prefixes on the control plane and detect inconsistencies in route advertisements and route qualities. We propose a different approach that utilizes information collected mostly from the data plane. Our method is motivated by two key observations: when a prefix is not hijacked, 1) the hop count of the path from a source to this prefix is generally stable; and 2) the path from a source to this prefix is almost always a super-path of the path from the same source to a reference point along the previous path, as long as the reference point is topologically close to the prefix. By carefully selecting multiple vantage points and monitoring from these vantage points for any departure from these two observations, our method is able to detect prefix hijacking with high accuracy in a light-weight, distributed, and real-time fashion. Through simulations constructed based on real Internet measurement traces, we demonstrate that our scheme is accurate with both false positive and false negative ratios below 0.5%.

The rising popularity of live IPTV has triggered renewed interest in P2P multicast. In particular, the simple and robust 'swarming' style of P2P multicast is currently favored over more traditional tree-based approaches, which are seen to be complex and fragile. Swarming approaches, however, exhibit a basic control-overhead-versus-latency tradeoff that gears it more towards high-volume, latency-tolerant applications. This paper presents a new unstructured P2P multicast protocol called Chunkyspread that is tree-based yet simple and robust. Chunkyspread uses multiple trees to provide fine-grained control over member load, reacts quickly to membership changes, scales well, and has low overhead. This paper gives a detailed description of Chunkyspread and an apples-to-apples comparison with the DHT-based Splitstream multi-tree P2P multicast algorithm. We show that Chunkyspread exhibits far better control over transmit load than Splitstream, while exhibiting comparable or better latency and responsiveness to churn. This comparison establishes Chunkyspread as the 'best of breed' among tree- based P2P multicast algorithms, thus setting the stage for future comparisons with swarming-based approaches.

IP routing scalability is based on hierarchical routing, which requires that the IP address hierarchy be aligned with the physical topology. Both site multi-homing and switching ISPs without renumbering break this alignment, resulting in large routing tables. This paper presents CRIO: a new approach to IP scalability for both global and VPN routing. Using tunneling and virtual prefixes, CRIO decouples address hierarchy and physical topology, effectively giving ISPs the ability to trade-off routing table size for path length. Though CRIO is a new routing architecture, it works with existing data-plane router mechanisms. Through static simulation on a Rocketfuel-measured Internet topology and traffic data from a Tier 1 ISP, we show that CRIO can shrink the BGP RIB by nearly two orders of magnitude, the global FIB by one order of magnitude, and the VPN FIB by ten to twenty times, all with very little increase in overall path length.

Despite its growing use in critical infrastructure services, the performance of IP(v4) Anycast and its interaction with IP routing practices is not well understood. In this paper, we present the results of a detailed measurement study of IP Anycast. Our study uses a two-pronged approach. First, using a variant of known latency estimation techniques, we measure the performance of current commercially operational IP Anycast deployments from a large number (>20,000) of vantage points. Second, we deploy our own small-scale anycast service that allows us to perform controlled tests under different deployment and failure scenarios. To the best of our knowledge, our study represents the first large-scale evaluation of existing anycast services and the first evaluation of the behavior of IP Anycast under failure.We find that: (1) IP Anycast, if deployed in an ad-hoc manner, does not offer good latency-based proximity, (2) IP Anycast, if deployed in an ad-hoc manner, does not provide fast failover to clients, (3) IP Anycast typically offers good affinity to all clients with the exception of those that explicitly load balance traffic across multiple providers, (4) IP Anycast, by itself, is not effective in balancing client load across multiple sites. We thus propose and evaluate practical means by which anycast deployments can achieve good proximity, fast failover and control over the distribution of client load. Overall, our results suggest that an IP Anycast service, if deployed carefully, can offer good proximity, load balance, and failover behavior.

Abstract — Unstructured p2p and overlay network applications often require that a random graph be constructed, and that some form of random node selection take place over that graph. A key and difficult requirement of many such applications is heterogeneity: peers have different node degrees in the random graph based on their capacity. Using simulations, this paper compares a number of techniques—some novel and some variations on known approaches—for heterogeneous graph construction and random node selection on top of such graphs. Our focus is on practical criteria that can lead to a genuinely deployable toolkit that supports a wide range of applications. These criteria include simplicity of operation, support for node heterogeneity, quality of random selection, efficiency and scalability, load balance, and robustness. We show that all these criteria can more-or-less be met by all the approaches. Our novel approach, however, stands out as the best from a practical perspective because of its simplicity: it achieves the criteria while requiring each node to set only a single tuning parameter, its desired relative load. I.

IP anycast, with its innate ability to find nearby resources in a robust and efficient fashion, has long been considered an important means of service discovery. The growth of P2P applications presents appealing new uses for IP anycast. Unfortunately, IP anycast suffers from serious problems: it is very hard to deploy globally, it scales poorly by the number of anycast groups, and it lacks important features like load-balancing. As a result, its use is limited to a few critical infrastructure services such as DNS root servers. The primary contribution of this paper is a new IP anycast architecture, PIAS, that overcomes these problems while largely maintaining the strengths of IP anycast. PIAS makes use of a proxy overlay that advertises IP anycast addresses on behalf of group members and tunnels anycast packets to those members. The paper presents a detailed design of PIAS and evaluates its scalability and efficiency through simulation. We also present preliminary measurement results on anycasted DNS root servers that suggest that IP anycast provides good affinity. Finally, we describe how PIAS supports two important P2P and overlay applications.

The Internet is not secure due to its design goals being at odds with the principle of least privilege. The Internet strives to allow any host to communicate with any other host, while the principle of least privilege advocates limiting host connectivity to the smallest set necessary for performing a task. Our goal is to secure the Internet by largely turning off connectivity in the Internet, and then using explicit signaling to selectively enable only those connections that are deemed necessary for performing a task.

Today Internet QoS is deployed piecemeal - typically at known bottleneck links like enterprise access links or wireless links. A more comprehensive, end-to-end QoS deployment, for instance across large enterprise networks or the global Internet, remains elusive. There is growing interest in the idea of using overlay networks to provide differential QoS services (improve performance for some flows at the expense of other flows). A necessary building block is the ability to provide differential service over a single overlay link that traverses many IP router hops. This work presents MPAT, the first truly scalable algorithm for fairly providing differential services to TCP flows that share a bottleneck link. Unlike known schemes, our approach preserves the cumulative fair share of the aggregated flows even where the number of flows in the aggregate is large. Specifically we demonstrate, primarily through experiments on the real Internet, that congestion state can be shared across more than 100 TCP flows with throughput differentials of 95:1. This is up to five times better than differentials achievable by known techniques. Indeed, MPAT scalability is limited only by the delay-bandwidth product of the aggregated flows. With this tool, it is now possible to seriously explore the viability of network QoS through overlay network services.

This paper presents and analyzes IPNL (for IP Next Layer), a NAT-extended Internet protocol architecture designed to scalably solve the address depletion problem of IPv4. A NAT-extended architecture is one where only hosts and NAT boxes are modified. IPv4 routers and support protocols remain untouched. IPNL attempts to maintain all of the original characteristics of IPv4, most notably address prefix location independence. IPNL provides true site isolation (no renumbering), and allows sites to be multi-homed without polluting the default-free routing zone with per-site prefixes. We discuss IPNL's architectural benefits and drawbacks, and show that it comes acceptably close to achieving its goals.

Hash tables - which map "keys" onto "values" - are an essential building block in modern software systems. We believe a similar functionality would be equally valuable to large distributed systems. In this paper, we introduce the concept of a Content-Addressable Network (CAN) as a distributed infrastructure that provides hash table-like functionality on Internet-like scales. The CAN is scalable, fault-tolerant and completely self-organizing, and we demonstrate its scalability, robustness and low-latency properties through simulation.

There is an increasing need to quickly and efficiently learn network distances, in terms of metrics such as latency or bandwidth, between Internet hosts. For example, Internet content providers often place data and server mirrors throughout the Internet to improve access latency for clients, and it is necessary to direct clients to the nearest mirrors based on some distance metric in order to realize the benefit of the mirrors. We suggest a scalable Internet-wide architecture, called IDMaps, which measures and disseminates distance information on the global Internet. Higher level services can collect such distance information to build a virtual distance map of the Internet and estimate the distance between any pair of IP addresses. We present our solutions to the measurement server placement and distance map construction problems in IDMaps. We show that IDMaps can indeed provide useful distance estimations to applications such as nearest mirror selection.

There is an increasing need for Internet hosts to be able to quickly and efficiently learn the distance, in terms of metrics such as latency or bandwidth, between Internet hosts. For example, to select the nearest of multiple equal content Web servers. This paper explores technical issues related to the creation of a public infrastructure service to provide such information. In so doing, we suggest an architecture, called IDMaps, whereby Internet distance information is distributed over the Internet, using IP multicast groups, in the form of a virtual distance map. Systems listening to the groups can estimate the distance between any pair of IP addresses by running a spanning tree algorithm over the received distance map. We also presents the results of experiments that give preliminary evidence supporting the architecture. This work thus lays the initial foundation for future work in this new area.

NTT Software Labs. is producing a distributed, self-configuring information navigation infrastructure designed to scale to global proportions. For reasons of large scale, unreliability (of the Internet, its connected computers, and the implementations), and the complete autonomy of the participants, a number of difficult database and cache consistency problems arise that are not solved by techniques commonly used either for the Internet (i.e. DNS), or for existing distributed database systems. This paper describes a set of strategies designed to solve these problems. In particular, it focuses on the use of third-party detection and notification of database and cache inconsistency.

Due to a limited address space and poor scaling of backbone routing information, the Internet Protocol (IP) is rapidly reaching the end of its useful lifetime. The Simple Internet Protocol Plus (SIPP), a proposed next generation Internet Protocol, solves these problems with larger internet layer addresses. In addition, SIPP provides a number of advanced routing and addressing capabilities including mobility, extended (variable-length) addressing, provider selection, and certain forms of multicast. These capabilities are all achieved through a single mechanism, a generalization of the IP loose source route. We argue that, for reasons of simplicity and evolvability, a single powerful mechanism to achieve a wide range of routing and addressing functions is preferable to having multiple specific mechanisms, one for each function.

The authors investigate fast routing table lookup techniques, where the table is composed of hierarchical addresses such as those found in a national telephone network. The hierarchical addresses provide important benefits in large networks, but existing fast routing table lookup techniques, based on hardware such as content addressable memory (CAM), work only with flat addresses. Several fast routing table lookup solutions for hierarchical address based on binary and ternary CAMs are presented, and their advantages and drawbacks are analyzed.>

One of the central problems in one-to-many wide-area communications is forming the delivery tree - the collection of nodes and links that a multicast packet traverses. Significant problems remain to be solved in the area of multicast tree formation, the problem of scaling being paramount among these.In this paper we show how the current IP multicast architecture scales poorly (by scale poorly, we mean consume too much memory, bandwidth, or too many processing resources), and subsequently present a multicast protocol based on a new scalable architecture that is low-cost, relatively simple, and efficient. We also show how this architecture is decoupled from (though dependent on) unicast routing, and is therefore easy to install in an internet that comprises multiple heterogeneous unicast routing algorithms.