the long-term average properties of detoured paths against Internet- phasis on high performance packet classification and routing. It uses IP-in-IP encapsulation to send packets along alternate paths While ron shares with detour the idea of routing via other 2.2 Network-layer Techniques nodes, our work differs from Detour in three significant ways. First, Much work has been done on performance-based and fault- RON seeks to prevent disruptions in end-to-end communication in tolerant routing within a single routing domain, but practical mecl the face of failures. RoN takes advantage of underlying Internet anisms for wide-area Internet recovery from outages or badly per- path redundancy on time-scales of a few seconds, reacting respon- forming paths are lacking sively to path outages and performance failures. Second,RON As though today's wide-area BGP-4 routing is based largely on designed as an application-controlled routing overlay; because each hop-counts, early ARPANET routing was more dynamic, re RON is more closely tied to the application using it, RON more ding to the current delay and utilization of the network. by readily integrates application-specific path metrics and path selec- 1989, the ARPANET evolved to using a delay- and congestion- tion policies. Third, we present and analyze experimental results based distributed shortest path routing algorithm [11]. However, from a real-world deployment of a ron to demonstrate fast re- the diversity and size of today's decentralized Internet necessitated covery from failure and improved latency and loss-rates even over the deployment of protocols that perform more aggregation and short time -scales fewer updates. As a result, unlike some interior routing protocols An alternative design to ron would be to use a generic overlay within ASS, BGP-4 routing between As's optimizes for scalable infrastructure like the X-Bone and port a standard network routing operation over all el protocol (like OSPF or RIP) with low timer values. However, this By treating vast collections of subnetworks as a single entity for by itself will not improve the resilience of Internet communications global routing purposes, BGP-4 is able to summarize and aggregate for two reasons. First, a reliable and low-overhead outage detection enormous amounts of routing information into a format that scales module is required, to distinguish between packet losses caused by to hundreds of millions of hosts. To prevent costly route oscilla congestion or error-prone links from legitimate problems with a tions, BGP-4 explicitly damps changes in routes. Unfortunately, path. Second, generic network-level routing protocols do not utilize while aggregation and damping provide good scalability, they in application-specific definitions of faults terfere with rapid detection and recovery when faults occur. RON Various Content Delivery Networks(CDNs) use overlay tech- handles this by leaving scalable operation to the underlying Inter- niques and caching to improve the performance of content del het substrate moving fault detection and recovery to a higher layer for specific applications such as Http and streaming video The overlay that is capable of faster response because it does not have functionality provided by RON may ease future CDn development to worry about scalabil by providing some routing components required by these services An oft-cited"solution" to achieving fault-tolerant network con- advertising a customer network through multiple ISPs. The idea 3. Design Goals is that an outage in one ISP would leave the customer connected The design of RoN seeks to meet three main design goals: (i) via the other. However, this solution does not generally achieve failure detection and recovery in less than 20 seconds, (ii) tighter fault detection and recovery within several seconds because of the integration of routing and path selection with the application, and degree of aggregation used to achieve wide-area routing scalabil (ii) expressive policy routing cept routing announcements for fewer than 8192 contiguous ad- 3.1 Fast Failure Detection and recovery dresses(a"/19 netblock). Small companies, regardless of their Todays wide-area Internet routing system based on BGP-4 does fault-tolerance needs, do not often require such a large address not handle failures well. From a network perspective, we define block, and cannot effectively multi-home. One alternative may be two kinds of failures. Link failures occur when a router or a link rovider-based addressing, where an organization gets addresses rom multiple providers, but this requires handling two distinct sets problem, or link disconnection. Path failures occur for a variety of of addresses on its hosts. It is unclear how on-going connections reasons, including denial-of-service attacks or other bursts of traffic on one address set can seamlessly switch on a failure in this model that cause a high degree of packet loss or high, variable latencies 2.3 Overlay-based Techniques Applications perceive all failures in one of two ways: outages or performance failures. Link failures and extreme path failures cause Overlay networks are an old idea; in fact, the Internet itself was outages, when the average packet loss rate over a sustained period developed as an overlay on the telephone network. Several Inter- net overlays have been designed in the past for various purpose tocols including TCP to degrade by several orders of magnitude including providing OSI network-layer connectivity [10), easing Performance failures are less extreme, for example, throughput, la IP multicast deployment using the MBone [6, and providing IPv6 tency, or loss-rates might degrade by a factor of two or three onnectivity using the 6-Bone [9). The X-Bone is a recent infras- BGP-4 takes a long time on the order of several minutes, to con- tructure project designed to speed the deployment of IP-based over- verge to a new valid route after a link failure causes an outage [ 12] lay networks [26]. It provides management functions and mecha- In contrast, RON's goal is to detect and recover from outages and nisms to insert packets into the overlay, but does not yet support performance failures within several seconds. Compounding this fault-tolerant operation or application-controlled path selection. Few overlay networks have been designed for efficient fault de such as packet foods and persistent congestion on links or paths tection and recovery, although some have been designed for better that greatly degrade end-to-end performance. As long as a link is end-to-end performance. The Detour framework [5, 22] was mo- deemed"live"(i.e, the BGP session is still alive), BGP's AS-path architecture designed to support altermate-hop routing, with an em- for an application usikk may nop ackets down the faulty path tivated by the potential long-term performance benefits of indirect based routing will continue to rout routing [23]. It is an in-kernel packet encapsulation and routing fortunately, such a path ovide adequate performancethe long-term average properties of detoured paths against Internet￾chosen paths. 2.2 Network-layer Techniques Much work has been done on performance-based and fault￾tolerant routing within a single routing domain, but practical mech￾anisms for wide-area Internet recovery from outages or badly per￾forming paths are lacking. Although today’s wide-area BGP-4 routing is based largely on AS hop-counts, early ARPANET routing was more dynamic, re￾sponding to the current delay and utilization of the network. By 1989, the ARPANET evolved to using a delay- and congestion￾based distributed shortest path routing algorithm [11]. However, the diversity and size of today’s decentralized Internet necessitated the deployment of protocols that perform more aggregation and fewer updates. As a result, unlike some interior routing protocols within AS’s, BGP-4 routing between AS’s optimizes for scalable operation over all else. By treating vast collections of subnetworks as a single entity for global routing purposes, BGP-4 is able to summarize and aggregate enormous amounts of routing information into a format that scales to hundreds of millions of hosts. To prevent costly route oscilla￾tions, BGP-4 explicitly damps changes in routes. Unfortunately, while aggregation and damping provide good scalability, they in￾terfere with rapid detection and recovery when faults occur. RON handles this by leaving scalable operation to the underlying Inter￾net substrate, moving fault detection and recovery to a higher layer overlay that is capable of faster response because it does not have to worry about scalability. An oft-cited “solution” to achieving fault-tolerant network con￾nectivity for a small- or medium-sized customer is to multi-home, advertising a customer network through multiple ISPs. The idea is that an outage in one ISP would leave the customer connected via the other. However, this solution does not generally achieve fault detection and recovery within several seconds because of the degree of aggregation used to achieve wide-area routing scalabil￾ity. To limit the size of their routing tables, many ISPs will not accept routing announcements for fewer than 8192 contiguous ad￾dresses (a “/19” netblock). Small companies, regardless of their fault-tolerance needs, do not often require such a large address block, and cannot effectively multi-home. One alternative may be “provider-based addressing,” where an organization gets addresses from multiple providers, but this requires handling two distinct sets of addresses on its hosts. It is unclear how on-going connections on one address set can seamlessly switch on a failure in this model. 2.3 Overlay-based Techniques Overlay networks are an old idea; in fact, the Internet itself was developed as an overlay on the telephone network. Several Inter￾net overlays have been designed in the past for various purposes, including providing OSI network-layer connectivity [10], easing IP multicast deployment using the MBone [6], and providing IPv6 connectivity using the 6-Bone [9]. The X-Bone is a recent infras￾tructure project designed to speed the deployment of IP-based over￾lay networks [26]. It provides management functions and mecha￾nisms to insert packets into the overlay, but does not yet support fault-tolerant operation or application-controlled path selection. Few overlay networks have been designed for efficient fault de￾tection and recovery, although some have been designed for better end-to-end performance. The Detour framework [5, 22] was mo￾tivated by the potential long-term performance benefits of indirect routing [23]. It is an in-kernel packet encapsulation and routing architecture designed to support alternate-hop routing, with an em￾phasis on high performance packet classification and routing. It uses IP-in-IP encapsulation to send packets along alternate paths. While RON shares with Detour the idea of routing via other nodes, our work differs from Detour in three significant ways. First, RON seeks to prevent disruptions in end-to-end communication in the face of failures. RON takes advantage of underlying Internet path redundancy on time-scales of a few seconds, reacting respon￾sively to path outages and performance failures. Second, RON is designed as an application-controlled routing overlay; because each RON is more closely tied to the application using it, RON more readily integrates application-specific path metrics and path selec￾tion policies. Third, we present and analyze experimental results from a real-world deployment of a RON to demonstrate fast re￾covery from failure and improved latency and loss-rates even over short time-scales. An alternative design to RON would be to use a generic overlay infrastructure like the X-Bone and port a standard network routing protocol (like OSPF or RIP) with low timer values. However, this by itself will not improve the resilience of Internet communications for two reasons. First, a reliable and low-overhead outage detection module is required, to distinguish between packet losses caused by congestion or error-prone links from legitimate problems with a path. Second, generic network-level routing protocols do not utilize application-specific definitions of faults. Various Content Delivery Networks (CDNs) use overlay tech￾niques and caching to improve the performance of content delivery for specific applications such as HTTP and streaming video. The functionality provided by RON may ease future CDN development by providing some routing components required by these services. 3. Design Goals The design of RON seeks to meet three main design goals: (i) failure detection and recovery in less than 20 seconds; (ii) tighter integration of routing and path selection with the application; and (iii) expressive policy routing. 3.1 Fast Failure Detection and Recovery Today’s wide-area Internet routing system based on BGP-4 does not handle failures well. From a network perspective, we define two kinds of failures. Link failures occur when a router or a link connecting two routers fails because of a software error, hardware problem, or link disconnection. Path failures occur for a variety of reasons, including denial-of-service attacks or other bursts of traffic that cause a high degree of packet loss or high, variable latencies. Applications perceive all failures in one of two ways: outages or performance failures. Link failures and extreme path failures cause outages, when the average packet loss rate over a sustained period of several minutes is high (about 30% or higher), causing most pro￾tocols including TCP to degrade by several orders of magnitude. Performance failures are less extreme; for example, throughput, la￾tency, or loss-rates might degrade by a factor of two or three. BGP-4 takes a long time, on the order of several minutes, to con￾verge to a new valid route after a link failure causes an outage [12]. In contrast, RON’s goal is to detect and recover from outages and performance failures within several seconds. Compounding this problem, IP-layer protocols like BGP-4 cannot detect problems such as packet floods and persistent congestion on links or paths that greatly degrade end-to-end performance. As long as a link is deemed “live” (i.e., the BGP session is still alive), BGP’s AS-path￾based routing will continue to route packets down the faulty path; unfortunately, such a path may not provide adequate performance for an application using it