October 9^th, 1999, the poverty-fighting NetAid concerts kick off live on the Web [NAID99]. In just the first half an hour of the concert, an estimated 125,000 people had tried to log onto the NetAid Web site. However, the sheer volume slowed the system, making pictures grainy and tardy. In fact, over the years, many high-profile events have faired even worse on the Web, for example, the Mars Pathfinder site and the shows of Victoria’s Secret, just to name a few. "Perhaps it may be a little ambitious to use Internet technology at this point," said the people who operate the NetAid site.

The Internet technology that is missing here is a way to distribute content to vast audiences in a timely, efficient and, most importantly, scalable fashion. A key technology that can enable this is IP multicast [SED89]. With IP multicast, applications send one copy of the information to a group address, reaching all recipients who want to receive it. Without multicasting, the same information must be carried over the Internet multiple times, one time for each recipient, consuming more bandwidth and limiting the number of participants [VJ97]. In order for content distribution applications such as on-line TV stations to reach millions of Internet users, multicast is a requirement, not an option. Here, "multicast" can be IP multicast and/or application-level multicast such as web caching.

However, many compelling network applications, such as on-line trading and live news distribution, require reliable multicast support. The challenge is to implement a scalable, low latency, and bandwidth-efficient reliable multicast protocol (see Section 1.1). Moreover, since IP multicast provides synchronous delivery ¾ information is delivered to all receivers at the same time, it has limited applicability to the Web because the Web access pattern is asynchronous ¾ users may request a web page at different times. Instead, caching handles asynchronous requests better than IP multicast.

We believe that large-scale reliable multicast can be implemented efficiently and with low latency and it is a useful and powerful network service. We demonstrate this by devising such a reliable multicast protocol and applying it to solve an important problem in web caching. Combining reliable multicast and web caching, we can distribute content to vast audiences in a timely, efficient and scalable fashion.

Internet gaming, on-line trading, and live news distribution, etc., are compelling network applications of the coming Internet era, all of which require scalable reliable multicast support. However, previous work lacks bandwidth-efficient and low-latency loss recovery techniques. This dissertation makes three contributions to address the challenge of scalable reliable multicast and to scale the Web using reliable multicast and web caching.

The first contribution is OTERS (On-Tree Efficient Recovery using Subcast) -- a scalable reliable multicast protocol. We show that OTERS substantially reduces the recovery latency and the traffic load compared to previously proposed approaches, yet only requires simple, natural and low overhead extensions to the network layer. OTERS consists of a fusion tree formation protocol (FTFP) and a loss recovery protocol (LRP). FTFP builds a fusion tree dynamically among the multicast group members that closely matches the multicast delivery tree. LRP employs subcast retransmission to efficiently repair correlated packet losses.

The second contribution is an evaluation of the utility of forward error correction (FEC) with reliable multicast (RM). We show that FEC does not provide significant improvement to well-designed RM protocols (e.g., OTERS) and OTERS outperforms other RM protocols that benefit significantly from FEC. When OTERS is integrated with FEC, the packet delivery latency increases substantially while the bandwidth reduction is only marginal. Compared to other RM protocols (with or without FEC), OTERS makes a better tradeoff between the packet delivery latency and the traffic load.

The third contribution is MMO (Multicast invalidation with Multicast delivery using OTERS) -- a web proxy caching protocol for frequently updated objects. We show that MMO provides efficient bandwidth utilization and service scalability, and makes strong web cache consistency for frequently updated objects practical. MMO employs a reliable multicast channel (per volume of objects) to proactively disseminate cache invalidations and object updates from the web server to web cache proxies. MMO is the most efficient for disseminating popular, frequently modified and correlated web objects in a volume to a large number of web cache proxies.

Overall, we show that large-scale reliable multicast can be implemented efficiently and with low latency and it is a useful and powerful network service. Combining reliable multicast and web caching, we can distribute content to vast audiences in a timely, efficient and scalable fashion.

This dissertation studies the efficient and reliable multi-point delivery of data. Our solutions span multiple internetworking layers. On the application layer, we propose a scalable web caching protocol MMO for objects that are less dynamic than real time multimedia but more dynamic than online dictionaries. On the transport layer, we propose a scalable reliable multicast protocol OTERS that offers efficient and low-latency multi-point data transport. On the network layer, we propose the use of subcast and mtrace to recover correlated packet losses intelligently and efficiently. Each higher-layer solution is built upon the lower-layer solutions.

Combining reliable multicast and web caching, we can distribute content to vast audiences in a timely, efficient and scalable fashion. For example, on-line TV stations can multicast their live programming to millions of viewers; static on-line manuals and RFC can be effectively cached by web cache proxies; frequently changing news and stock quotes can be scalably multicast in a volume to interested web caches and later retrieved locally from the caches.

In the case of customization such as my.yahoo.com, the content provider can focus only on the task of generating a customized front page, which is just a list of URLs and is therefore fairly small. The actual content of the URLs is either retrieved from a nearby cache or received via multicast streaming. Web cache proxies may even perform some customization on behalf of the web servers if they can form a more closely coupled relationship [PC98b].

At the time of writing, many of the above schemes are not yet the common practice due to research, development and deployment reasons. In short, much can be accomplished using reliable multicast and web caching and much more has yet to come to make the Internet truly scalable.