Check out the new USENIX Web site.

Home About USENIX Events Membership Publications Students
OSDI '04 Paper    [OSDI '04 Technical Program]

Improving the Reliability of Internet Paths with One-hop Source Routing

Krishna P. Gummadi, Harsha V. Madhyastha,
Steven D. Gribble, Henry M. Levy, and David Wetherall
Department of Computer Science & Engineering
University of Washington
{gummadi, harsha, gribble, levy, djw}


Recent work has focused on increasing availability in the face of Internet path failures.  To date, proposed solutions have relied on complex routing and path-monitoring schemes, trading scalability for availability among a relatively small set of hosts.

This paper proposes a simple, scalable approach to recover from Internet path failures.  Our contributions are threefold.  First, we conduct a broad measurement study of Internet path failures on a collection of 3,153 Internet destinations consisting of popular Web servers, broadband hosts, and randomly selected nodes.  We monitored these destinations from 67 PlanetLab vantage points over a period of seven days, and found availabilities ranging from 99.6% for servers to 94.4% for broadband hosts.  When failures do occur, many appear too close to the destination (e.g., last-hop and end-host failures) to be mitigated through alternative routing techniques of any kind. Second, we show that for the failures that can be addressed through routing, a simple, scalable technique, called one-hop source routing, can achieve close to the maximum benefit available with very low overhead. When a path failure occurs, our scheme attempts to recover from it by routing indirectly through a small set of randomly chosen intermediaries.

Third, we implemented and deployed a prototype one-hop source routing infrastructure on PlanetLab. Over a three day period, we repeatedly fetched documents from 982 popular Internet Web servers and used one-hop source routing to attempt to route around the failures we observed.  Our results show that our prototype successfully recovered from 56% of network failures. However, we also found a large number of server failures that cannot be addressed through alternative routing.

Our research demonstrates that one-hop source routing is easy to implement, adds negligible overhead, and achieves close to the maximum benefit available to indirect routing schemes, without the need for path monitoring, history, or a-priori knowledge of any kind.

1  Introduction

Internet reliability demands continue to escalate as the Internet evolves to support applications such as banking and telephony. Yet studies over the past decade have consistently shown that the reliability of Internet paths falls far short of the "five 9s" (99.999%) of availability expected in the public-switched telephone network [11]. Small-scale studies performed in 1994 and 2000 found the chance of encountering a major routing pathology along a path to be 1.5% to 3.3% [17,26].

Previous research has attempted to improve Internet reliability by various means, including server replication, multi-homing, or overlay networks. While effective, each of these techniques has limitations. For example, replication through clustering or content-delivery networks is expensive and commonly limited to high-end Web sites. Multi-homing (provisioning a site with multiple ISP links) protects against single-link failure, but it cannot avoid the long BGP fail-over times required to switch away from a bad path [12]. Overlay routing networks, such as RON, have been proposed to monitor path quality and select the best available path via the Internet or a series of RON nodes [2]. However, the required background monitoring is not scalable and therefore limits the approach to communication among a relatively small set of nodes.

This paper re-examines the potential of overlay routing techniques for improving end-to-end Internet path reliability. Our goal is to answer three questions:

  1. What do the failure characteristics of wide-area Internet paths imply about the potential reliability benefits of overlay routing techniques?
  2. Can this potential be realized with a simple, stateless, and scalable scheme?
  3. What benefits would end-users see in practice for a real application, such as Web browsing, when this scheme is used?

To answer the first question, we performed a large-scale measurement study that uses 67 PlanetLab vantage points to probe 3,153 Internet destinations for failures over seven days. Of these destinations, 378 were popular Web servers, 1,139 were broadband hosts, and 1,636 were randomly selected IP addresses. During the course of our 7-day study we observed more failures than the 31 node RON testbed saw in 9 months [7].

Our results show that end-to-end path availability varies substantially across different destination sets. On average, paths to popular Web servers had 99.6% availability, but paths to broadband hosts had only 94.4% availability. The vast majority of paths experienced at least one failure. Unfortunately, many failures are located so close to the destination that no alternative routing or overlay scheme can avoid them: 16% of failures on paths to servers and 60% of failures on paths to broadband hosts occur were last-hop or end-system failures. Effective remedies for these failures are increased end-system reliability and multi-homing.

To answer the second question, we use our measurement results to show that when an alternative path exists, that path can be exploited through extremely simple means. Inspired by the Detour study [21] and RON [2], we explore the use of a technique we call one-hop source routing. When a communication failure occurs, the source attempts to reach the destination indirectly through a small set of intermediary nodes. We show that a selection policy in which the source node chooses four potential intermediary nodes at random (called random-4) can obtain close to the maximum possible benefit. This policy gives well-connected clients and servers the ability to route around failures in the middle of the network without the need for complex schemes requiring a priori communication or path knowledge.

To answer the third question, we built and evaluated a prototype one-hop source routing implementation called SOSR (for Scalable One-hop Source Routing). SOSR uses the Linux netfilter/iptables facility to implement alternative packet routing for sources and NAT-style forwarding for intermediaries - both at user level. SOSR is straightforward to build and completely transparent to destinations. On a simple workload of Web-browsing requests to popular servers, SOSR with the random-4 policy recovered from 56% of network failures. However, many failures that we saw were application-level failures, such as server timeouts, which are not recoverable through any alternative routing or overlay schemes. Including such application-level failures, SOSR could recover from only 20% of the failures we encountered. The user-level perception of any alternative routing scheme is ultimately limited by the behavior of the servers as well as of the network.

The rest of the paper is organized as follows. We present our measurement study characterizing failures in the next section. Section 3 then shows the potential effectiveness of different practical policies for improving Internet path reliability. Section 4 describes the design, implementation, and evaluation of our prototype one-hop source routing system. We end with a discussion of related work (Section 5) and our conclusions (Section 6).

2  Characterizing Path Failures

This section describes our large-scale measurement study of Internet path failures. Our goals were: (1) to discover the frequency, location, and duration of path failures, and (2) to assess the potential benefits of one-hop source routing in recovering from those failures.

2.1  Trace methodology

From August 20, 2004 to August 27, 2004 we monitored the paths between a set of PlanetLab [18] vantage points and sets of destination hosts in the Internet. We periodically sent a probe on each path and listened for a response. If we received a response within a pre-defined time window, we declared the path to be normal. If not, we declared a loss incident on that path. Once a loss incident was declared, we began to probe the path more frequently to: (1) distinguish between a "true" path failure and a short-lived congestion episode and (2) measure the failure duration. We used traceroute to determine where along the path the failure occurred. In parallel, we also sent probes from the vantage point to the destination indirectly through a set of intermediary nodes. This allowed us to measure how often indirect paths succeeded when the default path failed.

2.1.1  Probes and traceroutes

Our probes consist of TCP ACK packets sent to a high-numbered port on the destination. Correspondingly, probe responses consist of TCP RST packets sent by the destination. We used TCP ACK packets instead of UDP or ICMP probes for two reasons. First, many routers and firewalls drop UDP or ICMP probes, or treat them with lower priority than TCP packets, which would interfere with our study. Second, we found that TCP ACK probes raise fewer security alarms than other probes. Before we included a candidate destination in our study, we validated that it would successfully respond to a burst of 10 TCP ACK probes. This ensured that destinations were not rate-limiting their responses, avoiding confusion between rate-limiting and true packet loss.

To determine where a failure occurred along a path, we used a customized version of traceroute to probe the path during a loss incident. Our version of traceroute uses TTL-limited TCP ACK packets, probing multiple hops along the route in parallel. This returns results much faster than the standard traceroute and permits us to determine the location of even short-lived failures.

2.1.2  Node selection

Initially, we selected 102 geographically distributed PlanetLab nodes as vantage points. Following the experiment, we examined the logs on each node to determine which had crashed or were rebooted during our trace. We then filtered the trace to remove any nodes with a total downtime of more than 24 hours, reducing the set to 67 stable vantage points for our analysis. We similarly selected 66 PlanetLab nodes to use as intermediaries, but only 39 of these survived crash/reboot post-filtering.

Using our vantage points, we monitored paths to three different sets of Internet hosts: popular Web servers, broadband hosts, and randomly selected IP addresses. A full list of IP addresses in each set and additional details describing our selection process are available at

The members of each set were chosen as follows:

  • We culled our popular server set from a list of the 2,000 most popular Web sites according to Removing hosts that failed the TCP ACK rate-limit test and filtering duplicate IP addresses left us with 692 servers. The path behavior to a popular server is meant to be representative of the experience of a client when contacting a well-provisioned server.
  • We selected our broadband hosts from an IP address list discovered through a 2002 crawl of Gnutella [20]. From that set, we removed hosts whose reverse DNS lookup did not match a list of major broadband providers (e.g., adsl* and again filtered those that failed the rate-limit test. Finally, we selected 2,000 nodes at random from those that survived this filtering. The path behavior to a broadband host is meant to be representative of a peer-to-peer application or voice-over-IP (VoiP).
  • The random IP address set consists of 3,000 IP addresses that were randomly generated and that survived the rate-limit test. We use this set only as a basis for comparison.

We partitioned the destination sets across our initial vantage points such that each destination node was probed by only one vantage point. Because some of the vantage points were filtered from the trace due to failure or low availability, some of the destinations were consequently removed as well. Following this filtering, 378 servers, 1,139 broadband hosts, and 1,636 random IP addresses remained in the trace. Note that while we filtered vantage points and intermediaries for availability, we did not filter any of the destination sets beyond the initial TCP ACK rate-limit test. As a consequence, some destinations crashed or otherwise shut down during the trace, causing last-hop path failures.

2.1.3        Probe timing

Figure 1: Probe timing. (a) The sequence of probes that are sent along each path during the trace. (b) A loss incident begins with a single probe loss, and ends after 10 consecutive successful probe responses. (c) For each of the first 10 probe intervals of a loss incident, we issued indirect probes through each of 66 intermediaries.

During the 7-day trace period, we probed each path every 15 seconds. If the vantage point failed to receive a response within 3 seconds, we declared a loss to have occurred. A single loss transitioned the path into a loss incident - an event initiated by a single probe loss and ended by the reception of ten consecutive probe responses (Figure 1a). While a path is in the midst of a loss incident, we probed every 5 seconds (Figure 1b). We also issued a traceroute from the vantage point to the destination at the start of the loss incident.

For each of the first 10 probe intervals during a loss incident, we also attempted to probe the destination indirectly through each of the 66 PlanetLab intermediaries selected at the beginning of the experiment. Thus, during one of these probe intervals, the vantage point emits a probe to an intermediary every 5/66th of a second (Figure 1c). We allow six seconds for a response to flow back from the destination through the intermediary to the vantage point; if no response is received in this time we declare a loss through that intermediary.

2.1.4  Failures vs. loss incidents

In principle, it may seem simple to declare a path failure when some component of a path has malfunctioned and all packets sent on that path are lost. In practice, however, failures are more complex and difficult to define. For example, packet loss may be due to a true long-term failure or a short-term congestion event. In general, any operational definition of failure based on packet loss patterns is arbitrary.

We strove to define failure as a sequence of packet losses that would have a significant or noticeable application impact. We did not want to classify short sequences of packet drops as failures, since standard reliability mechanisms (such as TCP retransmission) can successfully hide these. Accordingly, we elevated a loss incident to a failure if and only if the loss incident began with three consecutive probe losses and the initial traceroute failed. We defined the failure to last from the send of the first failed probe until the send of the first of the ten successful probes that terminated the loss incident. For example, the loss incident shown in Figure 1b corresponds to a failure that lasted for 30 seconds.

2.2  Failure characteristics

Table 1 summarizes the high-level characteristics of the failures we observed, broken down by our three destination sets. In the table we show as classifiable those failures for which our modified traceroute was able to determine the location of the failure; the remainder we show as unclassifiable. The classifiable failures are further broken down into last-hop failures, which are failures of either the end-system or last-hop access link (we cannot distinguish the two), and non-last-hop failures, which occurred within the network.

For the popular servers, we saw 1,486 failures spread over 294 paths and 337 links along these paths. Of the 962 classifiable failures, 811 (84%) occurred within the network, while 16% were last-hop failures. On average, a path experienced 3.9 failures during the week-long trace, of which 0.4 were last-hop failures, 2.1 were non-last-hop failures, and 1.4 were unclassifiable.

Table 1: High-level characterization of path failures, observed from 08/20/04 to 08/27/04. We obtained path information using traceroutes. A failure is identified as a last-hop failure when it is attributable to either the access link connecting the destination to the network or the destination host itself.

For the broadband hosts we saw 7,560 failures of which 5,723 were classifiable. On average, a broadband path experienced 6.6 failures over the week, nearly double that of the popular server set. Of these 6.6 failures, 3.0 were last-hop, 2.0 non-last-hop, and 1.6 were unclassifiable. Comparing server and broadband paths, we saw approximately the same rate of non-last-hop failures, but broadband paths showed a much higher rate of last-hop failures (0.4 per path per week for servers, and 3.0 per path per week for broadband). Therefore, the network behaved similarly for broadband and popular server hosts, except over the last-hop.

2.2.1  Location of failures

To describe the failure locations in a meaningful way, we divide each path into four parts: last_hop, middle_core, src_side, and dst_side. Last_hop are either end-system failures or last-hop access-link failures. Middle_core failures occur in the "core of the Internet," which we define as the Tier1 domains. These are the few important domains, such as AT&T and Sprint, through which the vast majority of all Internet paths pass. We identify them using the methodology of Subramanian et al. [23]. Src_side and dst_side are therefore the remaining path segments between the core and source, or core and destination, respectively. If traceroute could not classify the failure location, we labeled it "unclassifiable."

Figure 2: Location of failures. Failures are spread throughout the Internet for all three destination sets. Last-hop failures dominate other failures for broadband hosts, but for popular servers, last-hop failures are rare.

Figure 2 shows the distribution of failures across these categories. Failures are spread throughout the Internet, and all three data sets observe approximately equal source-side and core failures. For popular servers, there are relatively few last-hop failures, and in fact the last-hop appears to be more reliable than the rest of the Internet! This is strong evidence that techniques such as one-hop source routing can improve end-to-end availability for server paths, as it targets these non-last-hop failures. For broadband hosts, however, last-hop failures dominate all other failures, and accordingly we should expect less of a benefit from one-hop source routing.

Not surprisingly, the random IP destination set behaves in a manner that is consistent with a blend of server-like and broadband-like hosts. Somewhat surprisingly, however, the random IP set sees a greater rate of destination-side failures than both servers and broadband hosts. We do not yet have an explanation for this.

2.2.2  Duration of failures

In Table 2, we show high-level statistics that characterize failure duration and path availability in our trace. The average path to a server is down for 2,561 seconds during our week long trace, which translates into an average availability of 99.6%. In comparison, the average path to a broadband host is down for 33,630 seconds during trace, leading to an average availability of 94.4%. Paths to broadband hosts are an order of magnitude less available than paths to server hosts. This is unsurprising, of course, since broadband hosts are less well maintained, tend to be powered off, and likely have worse quality last-hop network connections.

Table 2: Path downtime and failure durations. This table shows average and median path downtime, as well as average and median failure durations, for our three destination sets. The downtime for a path is the sum of all its failure durations.

The median path availability is significantly better than the average path availability, suggesting that the distribution of path availabilities is non-uniform. Figure 3 confirms this: for all three destination sets, more than half of the paths experienced less than 15 minutes of downtime over the week. As well as being generally less available than server paths, a larger fraction broadband paths suffer from high unavailability: more than 30% of broadband paths are down for more than an hour, and 13% are down for more than a day (not shown in graph).

Figure 3: Availability of paths (CDF). The cumulative distribution of total downtime experienced by the paths during our trace, for each of our three destination sets.

Table 2 also shows the average and median failure durations. On paths to servers, the average failure lasted for just under 11 minutes; in comparison, on paths to broadband hosts, the average failure lasted for 84 minutes. For both destination sets, last-hop failures lasted approximately an order of magnitude longer than non-last-hop failures. Unfortunately, this reduces the potential effectiveness of one-hop source routing. Last-hop failures can last for a long time, and they are also hard to route around. Like path availability, failure duration has a non-uniform distribution - median failure durations are significantly lower than average failure durations.

2.2.3  Frequency of failures

We can compute the number of failure-free paths by subtracting the number of failed paths from the number of paths probed (both shown in Table 1). This reveals that only 22% of server paths, 12% of broadband paths, and 15% of random paths were failure-free: most paths in each destination set experienced at least one failure.

Figure 4: Frequency of path failures. Paths are ordered by the number of failures experienced. Most paths experience few failures, but a small number of paths experience many failures. Note that both axes are in log-scale.

Figure 4 plots the number of failures each path experienced, using a log-scale on both axes. Each destination set is sorted in rank order from most-failing to least-failing path. This graph demonstrates two points: (1) a small number paths experience a very large number of failures, and (2) most paths experienced a small but non-zero number of failures. Additional analysis (not shown) also demonstrates that for broadband hosts, the failure-prone paths tend to fail on the last-hop, while for servers, the failure-prone paths tend to fail uniformly across the Internet, favoring neither the source-side, nor the core, nor the destination-side.

2.3  The potential of one-hop source routing

As previously described, during a loss incident we probed the destination indirectly through each of 39 intermediaries. If any of these indirect probes were successful, we considered the path to be recoverable using one-hop source routing. If not, we considered it to be unrecoverable. Note that this definition of recoverable provides an upper bound, since in practice an implementation is not likely to try such a large number of intermediaries when attempting to route around a failure.

Table 3: Potential effectiveness of one-hop source routing. Source routing can help recover from 66% of all failures on paths to servers, but fewer on paths to broadband hosts. Last-hop failures tend to confound recovery, while core failures are more recoverable.

The results of this experiment, shown in Table 3, indicate that 66% of all failures to servers are potentially recoverable through at least one intermediary. A smaller fraction (39%) of broadband failures are potentially recoverable. For all destination sets, one-hop source routing is very effective for failures in the Internet core, but it is less effective for source-side or destination-side failures. Somewhat surprisingly, some last-hop failures are recoverable. In part, this is due to multi-homing: i.e., there may be a last-hop failure on the default path to a destination, but a different last-hop link may be accessible on a different path through a destination. However, this is also due in part to our failure definition. If a last-hop link is not dead but merely "sputtering," sometimes probes along the default path will fail while an intermediary will be more "lucky" and succeed.

2.4  Summary

Our study examined failures of Internet paths from 67 vantage points to over 3,000 widely dispersed Internet destinations, including popular servers, broadband hosts, and randomly selected IP addresses. Overall, we found that most Internet paths worked well: most paths only experienced a handful of failures, and most paths experienced less than 15 minutes of downtime over our week-long trace. But failures do occur, and when they do, they were widely distributed across paths and portions of the network. However, broadband hosts tend to experience significantly more last-hop failures than servers, and last-hop failures tend to last long.

These failure characteristics have mixed implications for the potential effectiveness of one-hop source routing. Since server path failures are rarely on the last hop, there should be plenty of opportunity to route around them. Indeed, our initial results suggest that one-hop source routing should be able to recover from 66% of server path failures. In contrast, since broadband path failures are often on the last hop, there is less opportunity for alternative routing. Our results show than one-hop source routing will work less than 39% of the time in this case.

In the next section of the paper, we will examine one-hop source routing in greater detail, focusing initially on its potential for improving server path availability. Our goal in the next section is to use our trace to hone in on an effective, but practical, one-hop source routing policy. By effective, we mean that it successfully routes around recoverable failures. By practical, we mean that it succeeds quickly and with little overhead.

Figure 5: One-hop source routing. (a) The source (src) experiences a path failure to destination dst1, but it successfully routes through intermediary i5. (b) The source experiences a path failure to destination dst2. It uses a more aggressive recovery policy by simultaneously routing to intermediaries i2, i3, i4, and i5. The path to intermediary i2 experiences a path failure of its own, as does the path from intermediary i3 to the destination. Fortunately, the source is able reach dst2 through both i4 and i5.

3  One-Hop Source Routing

We have seen that 66% of all popular server path failures and 39% of all broadband host path failures are potentially recoverable through at least one of the 39 preselected intermediary nodes. This section investigates an obvious implication of this observation, namely, that one-hop source routing is a potentially viable technique for recovering from Internet path failures.

One-hop source routing is conceptually straightforward, as shown in Figure 5. After a node detects a path failure, it selects one or more intermediaries and attempts to reroute its packets through them. If the resulting indirect path is sufficiently disjoint from the default route, the packets will flow around the faulty components and successfully arrive at the destination. Assuming that the reverse path through the intermediary also avoids the fault, end-to-end communication is restored.

This approach raises several questions. Given a set of potential intermediaries for a failed path, how many of them on average will succeed at contacting the destination? What policy should the source node use to select among the set of potential intermediaries? To what extent does the effectiveness of one-hop source routing depend on the location of the failure along the path? Does a priori knowledge of Internet topology or the ability to maintain state about previous failures increase the effectiveness of a policy? When should recovery be initiated and when should recovery attempts be abandoned? The remainder of this section answers these questions.

3.1  Methodology

To answer these questions we rely on the data described in Section 2. As previously noted, following each failure we sent probe messages from the source to 39 PlanetLab intermediaries. The intermediaries then probed the destination and returned the results. If the source heard back from an intermediary before it heard back directly from the (recovered) destination, then we considered that intermediary to be successful. Thus, for each default-path failure, we were able to determine how many of the 39 PlanetLab intermediaries could have been used to route around it.

From this data we can analyze the effectiveness of policies that route through specific subsets of the intermediaries. For example, one policy might route through a single, randomly chosen intermediary; another policy might route through two preselected intermediaries in parallel, and so on. We can therefore compare various policies by simulating their effect using the data from our intermediate-node measurements.

3.2     What fraction of intermediaries help?

Figure 6: Disjoint paths. (a) The default path to the destination fails due to a faulty link. (b) Routing through intermediary i2 would succeed, since the diverted path is disjoint from the faulty link. (c) Routing through intermediary i1 would fail, since the diverted path rejoins the default path before the faulty link.

How many of the intermediaries succeed in routing around a particular failure depends on a number of factors, including the positions of the source, the destination, and the intermediaries in the network. For example, some intermediaries may not divert the packet flow sufficiently, either failing to pull packets from the default path before the fault or failing to return them to the default path after the fault. This can be seen in Figure 6a, where the route from src to dst fails due to the failure marked "X." An attempt to re-route through intermediary i2 would succeed (Figure 6b). However, routing through i1 would fail (Figure 6c), because i1's path to dst joins src's path to dst before the failure.


Figure 7: The number of useful intermediaries. For each failure, we measured the number of useful intermediaries in our candidate set of 39. (a) This histogram shows the aggregated results for popular servers only. For example, we observed 168 failures (165 non-last-hop and 3 last-hop) for which there were exactly 21-25 useful intermediaries. (b) A CDF of the same data for the recoverable failures only.

As described above, for each detected failure we counted the number of "useful intermediaries" through which the source node could recover. Note that we continue attempting to recover until either an intermediary succeeds or the default path self-repairs, up to a maximum of 10 probe intervals. If the default path self-repairs before any intermediary succeeds, we do not classify the event as a recovered failure.

Figure 7(a) shows the results for popular servers, grouped by the number of useful intermediaries on the x-axis. Out of the 1486 failures, 503 (34%) could not recover through any intermediary, as shown by the left-most bar. Last-hop failures accounted for 89 of those unrecoverable failures.

Figure 7(b) presents a CDF of this data for the remaining 983 failures (66%) that were recoverable. The figure shows that 798 (81%) of these failures could be recovered through at least 21 of the 39 intermediaries. It's clear, then, that a significant fraction of failures are recoverable through a large number of intermediaries. However, there are also failures for which only a small number of intermediaries are useful. For example, 55 (5.6%) of the 983 recoverable failures could be recovered through only 1-5 nodes. Thus, some recoverable failures require a careful choice of intermediary.

None of the failures were recoverable through more than 36 of the 39 intermediaries. Investigating further, we found that four PlanetLab intermediaries were subject to a routing policy that prevented them from communicating with the vast majority of our destinations. If we exclude these nodes from consideration, many failures would be recoverable through all 35 of the remaining intermediaries. However, in many cases, there were still a few intermediaries that should be avoided.

3.3  Is random-k an effective policy?

The results in Figure 7 suggest that a very simple strategy for selecting intermediaries may work well. Similar in spirit to randomized load-balancing [15,6], a source should be able to avoid failures by randomly picking k intermediaries through which to attempt recovery. The source could send packets through all k intermediaries in parallel and then route through the intermediary whose response packet is first returned.

To evaluate this strategy, we examine a policy in which the random selection is done once for each failure instance. When a failure is detected, the source selects a set of k random intermediaries. During the failure, if none of the k intermediaries succeed on the first attempt, the source continues to retry those same intermediaries. At the next failure, the source selects a new set of k random intermediaries. We call this policy random-k.

Since many intermediaries can be used to avoid most recoverable faults, even a single random selection (random-1) should frequently succeed. By selecting more than one random intermediary, the source ensures that a single unlucky selection is not fatal. However, as there are some failures for which only a few specific intermediaries are helpful, picking a small number of random intermediaries will not always work.

Figure 8: The effectiveness of random-k. This graph shows the effectiveness of random-k at recovering from failures as a function of k (the number of randomly selected intermediaries the source tries concurrently).

Figure 8 shows the effectiveness of random-k as a function of k. For popular servers, random-1 can route around 43% of all failures we observed. By definition, random-39 can route around all recoverable failures (66% of all failures for popular servers). The "knee in the curve" is approximately k=4: random-4 can route around 61% of all failures (92% of all recoverable failures) for popular servers. From this, we conclude that random-4 makes a reasonable tradeoff between effort (the number of concurrent intermediaries invoked per recovery attempt) and the probability of success.

3.4  Which failures can random-k handle?

As we showed in Section 2, the location of a failure has a significant impact on the likelihood that one-hop source routing can recover. For example, last-hop failures are much harder to recover from than core failures. To understand the impact of failure location on random-k's ability to recover, we classified recovery attempts according to the failure location. Figure 9 shows the same data as Figure 8 broken down according to this classification, but for popular servers only.

Figure 9: Failures random-k can handle. This graph breaks Figure 8 data down according to the classes of failures from which random-k recovers, for servers. Random-k can recover from most failures in the core, and near the destination, but it is less capable at handle failures near the source or on the last hop.

Random-k recovers poorly from near-source and last-hop failures, as shown in the figure. For example, random-4 recovers from only 37% of last-hop failures and 50% of near-source. However, random-4 is very successful at coping with the other failure locations, recovering from 89% of middle_core and 72% of near-destination failures. Intuitively, the Internet core has significant path diversity, therefore a failure in the core is likely to leave alternative paths between many intermediaries and the source and destination. However, the closer the failure is to the source or the destination, the more intermediaries it will render ineffective.

3.5  Are there better policies than random-k?

Figure 8 shows that random-k is a very effective policy: there is little room to improve above random-k before "hitting the ceiling" of recoverable failures. But can we be smarter? This subsection explores two alternative policies that use additional information or state to further improve on random-k. These policies might not be practical to implement, as they require significant amounts of prior knowledge of Internet topology or state. Nonetheless, an analysis of these policies offers additional insight into one-hop source routing. Like random-k, each of the alternative policies selects k intermediaries through which to route concurrently for each recovery attempt. The two additional policies we consider are:

  1. History-k. In this policy, we assume that the source node remembers the intermediary that it most recently used to recover from a path failure for each destination. When the source experiences a path failure, it selects k-1 intermediaries at random, but it chooses this recently successful intermediary as the kth intermediary. If the source has never experienced a failure for the destination, this policy reverts to random-k. The rationale for this policy is that an intermediary that previously provided a sufficiently disjoint path to a destination is likely to do so again in the future.
  2. BGP-paths-k. In this policy, we assume that the source is able to discover the path of autonomous systems (ASs) between it and the destination, and between all intermediaries and the destination, as seen by BGP. For each intermediary, the source calculates how many ASs its path has in common with the intermediary's path. When the source experiences a path failure to the destination, it orders the intermediaries by their number of common ASs and selects the k intermediaries with the smallest number in common. The rationale for this policy is that the source wants to use the intermediary with the "most disjoint" path to the destination in an attempt to avoid the failure.

Figure 10: Effectiveness of alternative policies. This graph shows the effectiveness of our alternative policies as a function of k. We include random-k for comparison.

Figure 10 shows how effective these policies were in recovering from failures. While there is some measurable difference between the policies for low values of k, this difference diminishes quickly as k increases. There is some benefit to using a more clever policy to pick the "right" intermediary; however, slightly increasing the number of intermediaries is more effective than using a smarter policy. For example, though BGP-paths-1 beats random-1, it does not beat random-4. Furthermore, unlike BGP-paths, random-4 requires no prior knowledge and no overhead for acquiring that knowledge.

These more sophisticated policies do have some positive effect on the ability to recover from path failures. They essentially attempt to bias their intermediary selection towards "better" intermediaries, and this biasing has some value. However, the goal of path failure recoverability is to avoid bad choices, rather than finding the best choice. Even with small k, random-k is extremely unlikely to select only bad choices, which is why it is competitive with these other strategies.

3.6  How persistent should random-4 be?

So far, we allow a source node recovering from a path failure to continue issuing random-4 attempts every 5 seconds until: (1) one of the four randomly selected intermediaries succeeds, (2) the path self-repairs, or (3) ten attempts have failed. We now consider the question of whether the source node should give up earlier, after fewer attempts. To answer this, we calculated the probability that the next random-4 attempt would succeed but the default path remains down, as a function of the number of previously failed random-4 attempts.

Figure 11: The diminishing returns of repeated recovery attempts. The probability that the next random-4 attempt will succeed, as a function of the number of previously failed attempts. After a single attempt, the probability of future success plummets.

Figure 11 shows the results. Immediately after noticing the failure, random-4 for popular servers has a 58% chance of recovering before the path self-repairs; for broadband hosts, this number is 28%. However, after a single failed random-4 attempt, the chance that the next attempt succeeds before the path self-repairs plummets to 1.6% for servers and 0.8% for broadband hosts. There is little reason to try many successive random-4 attempts; the vast majority of the time, the default path will heal before a future random-4 attempt succeeds.

In a sense, random-4 is an excellent failure detector: if a random-4 attempt fails, it is extremely likely that the destination truly is unreachable. To be conservative, though, we allow four random-4 attempts before giving up on intermediary-based recovery.

3.7     How eager should random-4 be?

Figure 12: The cost of being eager. Average number of overhead packets per connection and per recovery invocation, as a function of the number of consecutive packet drops seen before random-4 recovery is invoked. Because failures happen rarely, recovery is inexpensive.

Our methodology defines a failure to have occurred after three consecutive packet drops and a failed traceroute. There is nothing preventing a source from invoking random-4 before making this determination, however. For example, a source may choose to invoke random-4 after seeing only a single packet drop. However, this approach might potentially confuse short-term congestion for failure and needlessly introduce recovery overhead.

To investigate this apparent tradeoff between recovery time and overhead, we used our measurement data to calculate the overhead of recovery relative to hypothetical background HTTP traffic. To do this, we consider each 15-second probe attempt to be a hypothetical HTTP request. We estimate that the transfer of a 10KB Web page, including TCP establishment and teardown, would require 23 IP packets. Using this estimate, we can calculate the amount of packet overhead due to random-4 recovery attempts.

Figure 12 shows this overhead as a function of how eagerly recovery is invoked. The left-hand y-axis shows the average number of additional packets sent per HTTP transfer, and the right-hand y-axis shows the average number of additional packets sent per transfer for which recovery was invoked. As our previous results suggested, we abandon after four repeated random-4 attempts.

Failures occur rarely and there is no overhead to pay when the default path succeeds. Additionally, when failures do occur, random-4 usually succeeds after a single attempt. For these two reasons, there is very little overhead associated with the average connection: only 0.048 additional packets per connection on average (on top of the estimated 23 IP packets), assuming recovery begins immediately after a lost packet. Even when failures occur, there are only 4.1 additional packets on average. There is therefore little cost to being eager.

Figure 13: The benefit of being eager. This graph compares the likelihood that the default-path, a single-intermediary, and four intermediaries will succeed as a function of the number of consecutive packet drops observed. After just two observed packet drops, random-4 has a significantly higher probability of success than the default path.

Figure 13 demonstrates why it is useful to recover eagerly. We compare the probability that on the next attempt (1) the default-path will succeed, (2) a single randomly chosen intermediary will succeed, and (3) four randomly chosen intermediaries will succeed, as a function of the number of previously observed consecutive packet drops along the default path. After a single packet drop, all three strategies have an equally high probability of succeeding on the next attempt. But, with additional packet drops, the probability that the default path succeeds quickly decays, while random-1 and random-4 are more likely to work.

Note that random-1 has a slightly lower probability of succeeding than the default path after only one packet drop. For random-1, both the source to intermediary and the intermediary to destination paths must work, while for default-path, only the source to destination path must work.

There is a benefit to recovering early, and as we previously showed, there is very little cost. Accordingly, we believe random-4 should be invoked after having observed just a single packet drop.

3.8  Putting it all together

Our results suggest that an effective one-hop source routing policy is to begin recovery after a single packet loss, to attempt to route through both the default path and four randomly selected intermediaries, and to abandon recovery after four attempts to each of the randomly selected intermediaries fail, waiting instead for the default path to recover itself. For the remainder of this paper, we will refer to this set of policy decisions as "random-4."

We now ask what the user experience will be when using random-4. To answer this, we measured how long the user must wait after experiencing a path failure for end-to-end connectivity to be re-established, due either to the success of random-4 or path self-repair.


Figure 14: Recovery latency. This graph plots the cumulative probability that a failed path has recovered - due either to random-4 succeeding or self-repair of the default path - as a function of time, for (a) popular servers, (b) broadband hosts.

Figure 14 shows the results. For popular servers, we see that 58.1% of failures recover after a single attempt (five seconds). After four attempts (20 seconds), 75.3% of path failures recovered. Random-4 recovered from 60.2% of the failures by that point, while the path self-repaired from 15.1% of the failures. Since we abandon random-4 after four failed attempts, the fraction of paths that recover due to random-4 peaks at 60.2%. For broadband hosts, we see a similar pattern, except that random-4 is much less successful at recovering from failures: after four attempts, random-4 recovery has peaked at 29.4%.

Overall, we see that the major benefit of random-4 one-hop source routing is that it quickly finds alternative paths for recoverable failures. However, many failures are not recoverable with one-hop source routing. Bounding repeated random-4 to four attempts restricts the effort expended, instead allowing the path to self-repair.

3.9  Summary

This section examined specific policies for exploiting the potential benefit of one-hop source routing. Our results show that a simple, stateless policy called random-4 comes close to obtaining the maximum gain possible. For example, from our trace data, random-4 found a successful intermediary for 60% of popular server failures (out of the 66% achievable shown previously in Section 2). Furthermore, random-4 is scalable and requires no overhead messages. In comparison, the alternative knowledge-based policies we examined have higher cost and only limited benefit, relative to random-4.

The crucial question, then, is whether one-hop source routing can be implemented practically and can work effectively in a real system. We attempt to answer this question in the next section.

4  An Implementation Study

The goals of this section are twofold: (1) to discuss the pragmatic issues of integrating one-hop source routing into existing application and OS environments, and (2) to evaluate how well it works in practice. To this end, we developed a one-hop source routing prototype, which we call SOSR (for scalable one-hop source routing), and evaluate the prototype experimentally in the context of a Web-browsing application for popular servers.

4.1  Prototype Implementation

The high-level SOSR architecture consists of two major parts: one for the source-node and one for the intermediary-node. The source-node component retries failed communications from applications through one or more intermediaries. For scalability, all decision making rests with the source. The intermediate-node component forwards the messages it receives to the destination, acting as a proxy for the source. There is no destination-node component; SOSR is transparent to the destination.

Our source-node component, shown in Figure 15a, is implemented on top of the Linux netfilter framework [16]. Netfilter/iptables is a standard feature of the Linux kernel that simplifies construction of tools such as NATs, firewalls, and our SOSR system. It consists of an in-kernel module that forwards packets to a user-mode module for analysis. After receiving and examining a packet, the user-mode module can direct netfilter on how to handle it, acting in essence as an intelligent IP-level router.

We use the iptables rule-handling framework to inform netfilter about which packets to redirect to the user-level SOSR code and which to pass through. Our rules cause specific TCP flows (messages in both directions) to be redirected, based on port numbers or IP addresses. As well, they associate each flow with a SOSR policy module to handle its messages. Each policy module consists of failure detection code and intermediary selection code that decides when and where to redirect a packet.


Figure 15: The SOSR architecture. (a) The source node uses netfilter to redirect packets from the Linux kernel to a user-level SOSR policy module, which encapsulates the application packet and tunnels it to a chosen intermediary. Note that the application is unmodified. (b) The intermediary node decapsulates the packet, passes it through a user-level NAT daemon, and transmits it to the (unmodified) destination node.

The SOSR intermediary node acts as a NAT proxy [9], forwarding packets received from a source to the correct destination, and transparently forwarding packets from the destination back to the correct source. Figure 15b shows the encapsulation of indirected messages flowing through the intermediary. The source node encapsulates a TCP segment and information identifying the destination, and tunnels it to the intermediary through UDP. On receiving the UDP packet, the intermediary unwraps the TCP segment, passes it through its NAT component, and sends it to the destination using raw sockets. The NAT component of the intermediary maintains a hash table associating the sending node, the destination node, and the sending port it used to forward the segment. When a packet arrives back from the destination, the intermediary finds the associated (original) source address in the table, encapsulates the segment in a UDP packet along with the destination address, and returns it to the original source.

4.2  Evaluation Methodology

We evaluate our SOSR prototype by measuring its effectiveness in handling end-to-end Web-browsing failures for a set of popular Web servers. These failures include path failures, end-host failures, and application-level failures - anything that disrupts the browser from successfully completing an HTTP server transaction. The destination set consisted of 982 of the popular Web servers we considered in our measurement trace.

For our experiments, we used the same 39 SOSR intermediaries as in our earlier trace-based experiment. We then used three client machines at the University of Washington to repeatedly fetch Web pages from the destination set. Each machine ran a different error-handling protocol. The first simply ran the wget command-line Web browser on an unmodified Linux kernel. The second ran the same wget browser, but with the SOSR implementation in place, implementing the random-4 policy described in Section 3. The third ran wget on a modified, aggressive TCP stack; in place of standard TCP exponential back-off, we sent five duplicate packets every three seconds on a packet loss. This provides a balanced comparison to SOSR, in that it sends packets in the same number and frequency as random-4, but without the path diversity provided by the intermediaries.

Each client machine fetched a Web page once per second, rotating through the 982 Web servers a total of 279 times, ultimately issuing 273,978 requests. The machines fetched the same Web page at the same time, so that a path failure that affected one would hopefully affect the others as well. We ran our experiment for slightly more than 72 hours.

4.2.1  Failure classification

We classified failures as either network-level failures or application-level failures. If wget could not establish a TCP connection to the remote server, we classified the request as a network-level failure. However, if the destination returned a TCP RST packet to the source to refuse the connection, we classified the request as a "TCP refused" application-level failure, since the network path was clearly working.

If wget successfully established a TCP connection, but could not successfully complete an HTTP transaction within 15 minutes, we classified the request as an application-level failure. We further sub-classify application-level failures according to whether the HTTP transaction timed out ("HTTP timeout") or was dropped by the server before completion ("HTTP refused"). Though we do not consider them to be failures, we also noted HTTP response that contained an HTTP error code, such as "HTTP/1.1 500 server error."

4.3     Results

Table 4: Failures observed. Summary of our SOSR prototype evaluation results, showing the number of network-level and application-level failures each of our three test clients observed.

Table 4 summarizes our results. Overall, we observed few failures in our 72-hour experiment. The default wget client saw 481 failures in 273,978 requests, a failure rate of only 0.18%. We classified 69% as network-level failures and 31% as application-level failures. Thus, the network was responsible for approximately twice as many failures as the Web servers. However, indirect routing cannot recover from the Web server failures.

In comparison, the wget-SOSR client experienced 20% fewer failures than the default wget client: 383 compared to 481. Of these, 145 (38%) were network-level failures and 238 (62%) were application-level failures. wget-SOSR recovered from many of the network-level failures that the default wget experienced. The network-level recovery rate for wget-SOSR was 56%, slightly below the 66% we measured in Section 3. However, since application-level errors are unrecoverable, wget-SOSR's overall recovery rate was just 20%.

The wget-aggressiveTCP client experienced a marginally higher number of failures than the default wget: i.e., an aggressive TCP stack did not reduce the overall failure rate. However, it did reduce the number of network-level failures by 25%. The aggressive retransmissions were able to deal with some of the failures, but not as many as wget-SOSR. This confirms that SOSR derives its benefit in part because of path diversity, and in part because of its more aggressive retransmission.

Interestingly, both wget-SOSR and wget-aggressiveTCP observed a higher application-level failure rate than the default wget, receiving a significant increase in HTTP refused and timeout responses. While we cannot confirm the reason, we suspect that this is a result of the stress that the additional request traffic of these protocols causes on already overloaded servers. These additional application-level failures in balance reduced (for wget-SOSR) or canceled (for wget-aggressiveTCP) the benefits of the lower network-level failure rate.

4.4  Summary

This section presented a Linux-based implementation of one-hop source routing, called SOSR. SOSR builds on existing Linux infrastructure (netfilter/iptables) to route failures through a user-mode policy module on the source and a user-mode NAT proxy on intermediaries.

Our SOSR implementation was able to reduce recoverable (network-level) failures by 56% - close to what was predicted by our trace. However, with the Web-browsing application, we saw a new class of failures caused by the Web servers themselves rather than the network; these application-level failures cannot be recovered using indirect network routing. Including these non-recoverable failures, our SOSR implementation was able to reduce the end-to-end failure rate experienced by Web clients by only 20%.

Given the extremely low failure rate that non-SOSR Web clients experience today, we do not believe that SOSR would lead to any noticeable improvement in a person's Web browsing experience. However, this does not imply that one-hop source routing is without value. SOSR is very successful at routing around non-last-hop network failures, and moreover, it has very little overhead. An application that requires better path availability than the Internet currently provides can achieve it using one-hop source routing, assuming that the paths it communicates over have relatively few last-hop failures. Finally, it is likely that SOSR achieves close to the maximum achievable benefit of alternative routing; overlay schemes that attempt to improve reliability are unlikely to better SOSR's recovery rate, and have significant scalability problems due to high message overhead as well.

5  Related Work

Internet reliability has been studied for at least a decade. Paxson's study of end-to-end paths found the likelihood of encountering a routing pathology to be 1.5% in 1994 and 3.3% in 1995 [17]. Zhang concluded that Internet routing had not improved five years later [26]. Chandra observed an average wide-area failure rate of 1.5%, close to "two 9s" of availability [5]. Labovitz's study of routing found path availability to vary widely between "one 9" and "four 9s" [13]. These studies all demonstrate that Internet reliability falls short of that measured for the telephone network [11].

Feamster characterized path failures between overlay nodes. He found wide variation in the quality of paths, failures in all regions of the network, and many short failures [7]. Our work offers a more comprehensive study of network failures that measures paths to a much larger set of Internet-wide destinations. Our results are largely consistent with these earlier findings.

Server availability may be improved using content distribution networks (CDNs) [10] and clusters [8,4]. This is common for high-end Web sites. However, unlike our technique, it is applicable only to particular services, such as the Web.

Akella uses measurements to confirm that multi-homing has the potential to improve reliability as well as performance [1]. However, a strategy is still needed to select which path to use to obtain these benefits. Our technique is one such strategy; it will take advantage of multi-homing when it exists. There are also commercial products that operate at the BGP routing level to select paths [19,22]. The advantage of operating at the packet level, as we do, is more rapid response to failures. Conversely, it is known that BGP dynamics can result in a relatively long fail-over period [12] and that BGP mis-configurations are common [14].

Our work is most closely related to overlay routing systems that attempt to improve reliability and performance. The Detour study suggested that this could be accomplished by routing via intermediate end-systems [21]. RON demonstrated this to be the case in a small-scale overlay [2,3]. Our work differs in two respects. First, we target general communication patterns rather than an overlay. This precludes background path monitoring. Second, and more fundamentally, we show that background monitoring is not necessary to achieve reliability gains. This eliminates overhead in the common no failure case. Our finding is consistent with the study by Teixeira [24] that observed a high-level of path diversity that is not exploited by routing protocols. The NATRON system [25] uses similar tunneling and NAT mechanisms as SOSR to extend the reach of a RON overlay to external, RON-oblivious hosts.

6  Conclusions

This paper proposed a simple and effective approach to recovering from Internet path failures. Our approach, called one-hop source routing, attempts to recover from path failures by routing indirectly through a small set of randomly chosen intermediaries. In comparison to related overlay-based solutions, one-hop source routing performs no background path monitoring, thereby avoiding scaling limits as well as overhead in the common case of no failure.

The ability to recover from failures only matters if failures occur in practice. We conducted a broad measurement study of Internet path failures by monitoring 3,153 randomly selected Internet destinations from 67 PlanetLab vantage points over a seven day period. We observed that paths have relatively high average availability (99.6% to popular servers, but only 94.4% for broadband), and that most monitored paths experienced at least one failure. However, 16% of failures on paths to servers and 60% of failures on paths to broadband hosts were located on the last-hop or end-host. It is impossible to route around such last-hop failures. Overall, our measurement study demonstrated that a simple one-hop source routing technique called "random-4" could recover from 61% of path failures to popular servers, but only 35% of path failures to broadband hosts.

We implemented and deployed a prototype one-hop source routing infrastructure on PlanetLab. Over a 48 hour period, we repeatedly accessed 982 popular Web servers and used one-hop source routing to attempt to route around failures that we observed. Our prototype was able to recover from 56% of network failures, but we also observed a large number of server failures that cannot be addressed through alternative routing techniques. Including such application-level failures, our prototype was able to recover from 20% of failures encountered.

In summary, one-hop source routing is easy to implement, adds negligible overhead, and achieves close to the maximum benefit available to any alternative routing scheme, without the need for path monitoring, history, or a-priori knowledge of any kind.

7  Acknowledgments

We wish to thank Brian Youngstrom and the members of PlanetLab support who helped us with our trace, and Stavan Parikh who helped us develop SOSR. We also gratefully acknowledge the valuable feedback of Neil Spring, Ratul Mahajan, and Marianne Shaw, and we thank Miguel Castro for serving as our shepherd. This research was supported by the National Science Foundation under Grants ITR-0121341 and CCR-0085670 and by a gift from Intel Corporation.



A. Akella, B. Maggs, S. Seshan, A. Shaikh, and R. Sitaraman. A measurement-based analysis of multihoming. In Proceedings of ACM SIGCOMM 2003, Karlsruhe, Germany, August 2003.


D. G. Andersen, N. Feamster, S. Bauer, and H. Balakrishnan. Resilient overlay networks. In Proceedings of the 18th ACM Symposium on Operating Systems Principles, Marseille, France, November 2002.


D. G. Andersen, A. C. Snoeren, and H. Balakrishnan. Best-path vs. multi-path overlay routing. In Proceedings of ACM/USENIX Internet Measurement Conference 2003, October 2003.


V. Cardellini, E. Casalicchio, M. Colajanni, and P. S. Yu. The state of the art in locally distributed web-server systems. Technical Report RC22209 (W0110-048), IBM T. J. Watson Research Center, October 2001.


M. Dahlin, B. Chandra, L. Gao, and A. Nayate. End-to-end wan service availability. IEEE/ACM Transactions on Networking, 11(2), April 2003.


D. L. Eager, E. D. Lazowska, and J. Zahorjan. Adaptive load sharing in homogeneous distributed systems. IEEE Transactions on Software Engineering, 12(5):662-675, May 1986.


N. Feamster, D. Andersen, H. Balakrishnan, and F. Kaashoek. Measuring the effects of internet path faults on reactive routing. In Proceedings of ACM SIGMETRICS 2003, San Diego, CA, June 2003.


A. Fox, S. D. Gribble, Y. Chawathe, E. A. Brewer, and P. Gauthier. Cluster-based scalable network services. In Proceedings of the 16th ACM Symposium on Operating Systems Principles, pages 78-91, Saint Malo, France, 1997.


Network Working Group. The ip network address translator (nat). RFC 1631, May 1994.


B. Krishnamurthy, C. Willis, and Y. Zhang. On the use and performance of content distribution networks. In Proceedings of ACM SIGCOMM Internet Measurement Workshop 2001, November 2001.


D. R. Kuhn. Sources of failure in the public switched telephone networks. IEEE Computer, 30(4):31-36, April 1997.


C. Labovitz, A. Ahuja, A. Abose, and F. Jahanian. An experimental study of delayed internet routing convergence. In Proceedings of ACM SIGCOMM 2000, Stockholm, Sweden, August 2000.


C. Labovitz, A. Ahuja, and F. Jahanian. Experimental study of internet stability and backbone failures. In Proceedings of the 29th International Symposium on Fault-Tolerant Computing, pages 278-285, 1999.


R. Mahajan, D. Wetherall, and T. Anderson. Understanding bgp misconfiguration. In Proceedings of ACM SIGCOMM 2002, pages 3-16, Pittsburgh, PA, 2002.


M. Mitzenmacher. On the analysis of randomized load balancing schemes. Technical Report 1998-001, Digital Systems Research Center, February 1998.




V. Paxson. End-to-end routing behavior in the internet. IEEE/ACM Transactions on Networking, 5(5):601-615, October 1997.






Stefan Saroiu, P. Krishna Gummadi, and Steven D. Gribble. A measurement study of peer-to-peer file sharing systems. In Proceedings of Multimedia Computing and Networking (MMCN) 2002, January 2002.


S. Savage, A. Collins, E. Hoffman, J. Snell, and T. Anderson. The end-to-end effects of Internet path selection. In Proceedings of ACM SIGCOMM 1999, Cambridge, MA, September 1999.




L. Subramaniam, S. Agarwal, J. Rexford, and R. H. Katz. Characterizing the internet hierarchy from multiple vantage points. In Proceedings of IEEE INFOCOM 2002, New York, USA, June 2002.


R. Teixeira, K. Marzullo, S. Savage, and G. M. Voelker. Characterizing and measuring path diversity of internet topologies. In Proceedings of ACM SIGMETRICS 2003, pages 304-305, San Diego, CA, 2003.


Alexander Siumann Yip. NATRON: overlay routing to oblivious destinations. Master's thesis, 2002.


Y. Zhang, V. Paxson, and S. Shenker. The stationarity of internet path properties: Routing, loss, and throughput. Technical report, ACIRI, May 2000.


File translated from TEX by TTH, version 3.63.
4 Oct 2004, 13:35.

This paper was originally published in the Proceedings of the 6th Symposium on Operating Systems Design and Implementation,
December 6–8, 2004, San Francisco, CA

Last changed: 18 Nov. 2004 aw
OSDI '04 Technical Program
OSDI '04 Home