Internet interdomain routing is policy-driven, and thus physical connectivity does not imply reachability. On average, routing on today's Internet works quite well, ensuring reachability for most networks and achieving reasonable performance across most paths. However, there is a serious lack of understanding of Internet routing resilience to significant but realistic failures such as those caused by the 911 event, the 2003 Northeast blackout, and the recent Taiwan earthquake in December 2006. In this paper, we systematically analyze how the current Internet routing system reacts to various types of failures by developing a realistic failure model, and then pinpoint reliability bottlenecks of the Internet. For validity of our simulation results, we generate topology graphs by addressing concerns over the incompleteness of topology and the inaccuracy of inferred AS relationships. By focusing on the impact of structural and policy properties, our analysis provides guidelines for future Internet design. The simulation tool we provide for analyzing routing resilience is also efficient to scale to Internet-size topologies.

The growing reliance of networked applications on timely and reliable data transfer requires the underlying networking infrastructure to provide adequate services even in the presence of "persistent" failures (e.g., broken links/routers). It is much more difficult to meet this requirement for multicast sessions than for unicast communications because any on-tree component failure may often cause simultaneous service disruptions to multiple receivers. This paper presents a new multicast routing protocol, called the survivable multicast routing protocol (SMRP), which facilitates fast recovery of multicast sessions in face of persistent failures via local detour paths. Our evaluation results show that SMRP trades end-to-end delay and resource usage for short, and hence fast, recovery paths. For example, under a certain set of parameter values, SMRP shortens the recovery path by 20% with only a 5% increase of end-to-end delay and resource usage. Moreover, several design enhancements have made SMRP efficient, robust, flexible and scalable.

A hard real-time system is usually subject to stringent reliability and timing constraints. One way to avoid missing deadlines is to trade the quality of computation results for timeliness, and software fault tolerance is often achieved with the use of redundant programs. A deadline mechanism which combines these two methods is proposed to provide software fault tolerance in hard real-time periodic task systems. We consider the problem of scheduling a set of real-time periodic tasks each of which has two versions: primary and alternate. The primary version contains more functions and produces good quality results, but its correctness is more difficult to verify. The alternate version contains only the minimum required functions and produces less precise results and its correctness is easy to verify. We propose a scheduling algorithm which 1) guarantees either the primary or alternate version of each critical task to be completed in time and 2) attempts to complete as many primaries as possible. Our basic algorithm uses a fixed priority-driven preemptive scheduling scheme to preallocate time intervals to the alternates and, at runtime, attempts to execute primaries first. An alternate will be executed only if necessary because of time or bugs.