Denial of service protection mechanisms usually require classifying malicious traffic, which can be difficult. Another approach is to price scarce resources. However, while congestion pricing has been suggested as a way to combat DoS attacks, it has not been shown quantitatively how much damage a malicious player could cause to the utility of benign participants. In this paper, we quantify the protection that congestion pricing affords against DoS attacks, even for powerful attackers that can control their packets' routes. Specifically, we model the limits on the resources available to the attackers in three different ways and, in each case, quantify the maximum amount of damage they can cause as a function of their resource bounds. In addition, we show that congestion pricing is provably superior to fair queueing in attack resilience.

Current distributed routing paradigms (such as link-state, distance-vector, and path-vector) involve a convergence process consisting of an iterative exploration of intermediate routes triggered by certain events such as link failures. The convergence process increases router load, introduces outages and transient loops, and slows reaction to failures. We propose a new routing paradigm where the goal is not to reduce the convergence times but rather to eliminate the convergence process completely. To this end, we propose a technique called Failure-Carrying Packets (FCP) that allows data packets to autonomously discover a working path without requiring completely up-to-date state in routers. Our simulations, performed using real-world failure traces and Rocketfuel topologies, show that: (a) the overhead of FCP is very low, (b) unlike traditional link-state routing (such as OSPF), FCP can provide both low loss-rate as well as low control overhead, (c) compared to prior work in backup path pre-computations, FCP provides better routing guarantees under failures despite maintaining lesser state at the routers.

It is accepted wisdom that the current Internet architecture conflates network locations and host identities, but there is no agreement on how a future architecture should distinguish the two. One could sidestep this quandary by routing directly on host identities themselves, and eliminating the need for network-layer protocols to include any mention of network location. The key to achieving this is the ability to route on flat labels. In this paper we take an initial stab at this challenge, proposing and analyzing our ROFL routing algorithm. While its scaling and efficiency properties are far from ideal, our results suggest that the idea of routing on flat labels cannot be immediately dismissed.

Ternary content-addressable memories (TCAMs) have gained wide acceptance in the industry for storing and searching Access Control Lists (ACLs). In this paper, we propose algorithms for addressing two important problems that are encountered while using TCAMs: reducing range expansion and multi-match classification.Our first algorithm addresses the problem of expansion of rules with range fields to represent range rules in TCAMs, a single range rule is mapped to multiple TCAM entries, which reduces the utilization of TCAMs. We propose a new scheme called Database Independent Range PreEncoding (DIRPE) that, in comparison to earlier approaches, reduces the worst-case number of TCAM entries a single rule maps on to. DIRPE works without prior knowledge of the database, scales when a large number of ranges is present, and has good incremental update properties.Our second algorithm addresses the problem of finding multiple matches in a TCAM. When searched, TCAMs return the first matching entry; however, new applications require either the first few or all matching entries. We describe a novel algorithm, called Multi-match Using Discriminators (MUD), that finds multiple matches without storing any per-search state information in the TCAM, thus making it suitable for multi-threaded environments. MUD does not increase the number of TCAM entries needed, and hence scales to large databases.Our algorithms do not require any modifications to existing TCAMs and are hence relatively easy to deploy. We evaluate the algorithms using real-life and random databases.

There has been much work on developing techniques for estimating the capacity and the available bandwidth of network paths based on end-point measurements. The focus has primarily been on settings where the constrained link can be modeled as a point-to-point link with a well-defined bandwidth, serving packets in FIFO order. In this paper, we point out that broadband access networks, such as cable modem and 802.11-based wireless networks, break this model in various ways. The constrained link could (a) employ mechanisms such as token bucket rate regulation, (b) schedule packets in a non-FIFO manner, and (c) support multiple distinct rates. We study how these characteristics impede the operation of the various existing methods and tools for capacity and available bandwidth estimation, and present a new available bandwidth estimation technique, Probe- Gap, that overcomes some of these difficulties. Our evaluation is based on experiments with actual 802.11a and cable modem links.

Most P2P systems that provide a DHT abstraction distribute objects randomly among "peer nodes" in a way that results in some nodes having /spl theta/(log N) times as many objects as the average node. Further imbalance may result due to non-uniform distribution of objects in the identifier space and a high degree of heterogeneity in object loads and node capacities. Additionally, a node's load may vary greatly over time since the system can be expected to experience continuous insertions and deletions of objects, skewed object arrival patterns, and continuous arrival and departure of nodes. We propose an algorithm for load balancing in such heterogeneous, dynamic P2P systems. Our simulation results show that in the face of rapid arrivals and departures of objects of widely varying load, our algorithm achieves load balancing for system utilizations as high as 90% while moving only about 8% of the load that arrives into the system. Similarly, in a dynamic system where nodes arrive and depart, our algorithm moves less than 60% of the load the underlying DHT moves due to node arrivals and departures. Finally, we show that our distributed algorithm performs only negligibly worse than a similar centralized algorithm, and that node heterogeneity helps, not hurts, the scalability of our algorithm.

We consider the problem of service composition in a wide area network, where an end-user can send its packets through intermediate processing points (middleboxes) which can perform a variety of services. Example of such services are filtering, intrusion detection, anonymization, transcoding, and caching. In this paper, we argue that the Internet Indirection Infrastructure (i3)--an overlay network architecture that enables users to locate services and control the path followed by their packets--provides a natural platform for service composition. We discuss the challenges in implementing service compositions on top of i3, and suggest several approaches to address these challenges.

Designing a flexible, yet secure communication infrastructure has long been an elusive goal. Most of the proposals that seek to address the problem of flexibility have opened up the system for new forms of attacks. In this paper, we consider one particular proposal, i3 [2], a flexible indirection infrastructure that provides natural support for a multitude of communication primitives such as multicast, anycast and mobility. We systematically identify the attacks on i3, and propose techniques that address the security problems without sacrificing the flexibility that i3 offers. Our techniques, ranging from cryptographically constraining the forwarding entries to challenge-based mechanisms for inserting forwarding entries, while being simple, both conceptually and to implement, make most of the attacks provably hard. We believe that this paper represents an important step towards designing communication infrastructures that are both secure and flexible.

Currently the Internet has only one level of name resolution, DNS, which converts user-level domain names into IP addresses. In this paper we borrow liberally from the literature to argue that there should be three levels of name resolution: from user-level descriptors to service identifiers; from service identifiers to endpoint identifiers; and from endpoint identifiers to IP addresses. These additional levels of naming and resolution (1) allow services and data to be first class Internet objects (in that they can be directly and persistently named), (2) seamlessly accommodate mobility and multi-homing and (3) integrate middleboxes (such as NATs and firewalls) into the Internet architecture. We further argue that flat names are a natural choice for the service and endpoint identifiers. Hence, this architecture requires scalable resolution of flat names, a capability that distributed hash tables (DHTs) can provide.

With the rapid growth in the popularity of and the research interest in peer-to-peer (P2P) systems, an interesting question is what the quality of network connectivity between peers in the "real world" is and what implications this has for applications. In this paper, we describe an effort called PeerMetric to directly measure P2P network performance from the vantage point of broadband-connected residential hosts. Our measurements indicate significant asymmetry in bandwidth, with median downstream and upstream available bandwidths of 900 Kbps and 212 Kbps, respectively. We argue that the availability of last-hop bandwidth is more important than the traditional consideration of locality for overlay multicast over broadband hosts. We also consider the peer selection problem and find that a simple delay-vector based approach is effective for finding proximate peers in terms of latency. However, P2P latency turns out to be a poor predictor of P2P TCP throughput, which may be the metric of interest for applications such as file sharing.