Tina Han-Ting Wong
EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-00-1114
November 2000
The Internet has seen tremendous growth in the recent years. Traditional data types such as image and text no longer dominate the World Wide Web (WWW). Compared to the past, emerging applications transmitting video and audio present much higher bandwidth and more stringent latency requirements. Moreover, large-scale applications such as content delivery and interactive worlds pose serious scalability problems for the Internet. To improve performance of the Internet, the de facto Internet Protocol (IP) Unicast or client-server model has been augmented with Multicast, providing one-to-many and many-to-many delivery mechanisms. IP Multicast increases bandwidth efficiency, because packets destined to multiple receivers travel only once on common parts of the network. It also reduces server load, as a sender transmits packets only once for any number of receivers.
The scalability of IP Multicast has been a hot research topic for the past decade. Most work focuses on routing protocols, address allocations, and widespread deployments. Only recently researchers have considered forwarding state scalability as the most critical issue facing IP Multicast deployment. The costs of forwarding state come in terms of memory at the routers, and processing of periodic control messages to maintain such state. These costs increase with the number of concurrently active multicast groups in the Internet. We, and several others, argue that there will be a substantial number of simultaneous groups to warrant concern.
In one particular category of multicast applications, called large-scale applications, receivers show very different preferences for data. The problem of IP Multicast, despite its many advantages, is it uses one data stream to satisfy inevitably heterogenous receivers. If we transmit each unit of preference in a large-scale application on a separate multicast address, not only does the application creates a non-trivial amount of forwarding state in the network, but more severely, it overloads end-hosts with connection state. Receivers exhibiting different preferences on application data also lead to a range of reliability demands, such that eventual delivery of all data is unnecessary. The standard Transmission Control Protocol (TCP) is designed for one-to-one data transfer, where there is tight coupling between source and receiver. TCP is thus inappropriate for large-scale applications with many receivers.
In this dissertation, we study and propose solutions to the problem of multicast state scalability, which arises both at the network-level as forwarding state, and at the application-level for connection maintenance. First, we present a comprehensive analysis of the forwarding state problem. Although several schemes have been proposed recently to reduce such state, most are based on intuitions and assumptions about the Internet. Our analysis explores these intuitions and assumptions, while studying the general scaling trends of forwarding state. We conducted detailed simulation experiments on both real and generated network graphs, while varying a range of parameters driven by multicast application characteristics. Through a model defined independently of the IP Multicast deployment progress, our results on state are applicable in the future. We describe how to use these results in network provisioning, and multicast protocol and application designs.
Second, we present a clustering protocol to handle heterogeneous receiver preferences in large-scale applications. Although several subcasting mechanisms have been proposed to enable the sending of packets to arbitrary subset of receivers on a multicast tree, these mechanisms require changes to the current Internet infrastructure and service model. Our protocol follows the end-to-end principle, relying only on simple network primitives, to perform application-level group formation.
Advisor: Randy H. Katz
BibTeX citation:
@phdthesis{Wong:CSD-00-1114,
Author = {Wong, Tina Han-Ting},
Title = {Multicast Forwarding and Application State Scalability in the Internet},
School = {EECS Department, University of California, Berkeley},
Year = {2000},
Month = {Nov},
URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2000/6423.html},
Number = {UCB/CSD-00-1114},
Abstract = {The Internet has seen tremendous growth in the recent years. Traditional data types such as image and text no longer dominate the World Wide Web (WWW). Compared to the past, emerging applications transmitting video and audio present much higher bandwidth and more stringent latency requirements. Moreover, large-scale applications such as content delivery and interactive worlds pose serious scalability problems for the Internet. To improve performance of the Internet, the de facto Internet Protocol (IP) Unicast or client-server model has been augmented with Multicast, providing one-to-many and many-to-many delivery mechanisms. IP Multicast increases bandwidth efficiency, because packets destined to multiple receivers travel only once on common parts of the network. It also reduces server load, as a sender transmits packets only once for any number of receivers.<p>The scalability of IP Multicast has been a hot research topic for the past decade. Most work focuses on routing protocols, address allocations, and widespread deployments. Only recently researchers have considered forwarding state scalability as the most critical issue facing IP Multicast deployment. The costs of forwarding state come in terms of memory at the routers, and processing of periodic control messages to maintain such state. These costs increase with the number of concurrently active multicast groups in the Internet. We, and several others, argue that there will be a substantial number of simultaneous groups to warrant concern. <p>In one particular category of multicast applications, called large-scale applications, receivers show very different preferences for data. The problem of IP Multicast, despite its many advantages, is it uses one data stream to satisfy inevitably heterogenous receivers. If we transmit each unit of preference in a large-scale application on a separate multicast address, not only does the application creates a non-trivial amount of forwarding state in the network, but more severely, it overloads end-hosts with connection state. Receivers exhibiting different preferences on application data also lead to a range of reliability demands, such that eventual delivery of all data is unnecessary. The standard Transmission Control Protocol (TCP) is designed for one-to-one data transfer, where there is tight coupling between source and receiver. TCP is thus inappropriate for large-scale applications with many receivers.<p>In this dissertation, we study and propose solutions to the problem of multicast state scalability, which arises both at the network-level as forwarding state, and at the application-level for connection maintenance. First, we present a comprehensive analysis of the forwarding state problem. Although several schemes have been proposed recently to reduce such state, most are based on intuitions and assumptions about the Internet. Our analysis explores these intuitions and assumptions, while studying the general scaling trends of forwarding state. We conducted detailed simulation experiments on both real and generated network graphs, while varying a range of parameters driven by multicast application characteristics. Through a model defined independently of the IP Multicast deployment progress, our results on state are applicable in the future. We describe how to use these results in network provisioning, and multicast protocol and application designs.<p>Second, we present a clustering protocol to handle heterogeneous receiver preferences in large-scale applications. Although several subcasting mechanisms have been proposed to enable the sending of packets to arbitrary subset of receivers on a multicast tree, these mechanisms require changes to the current Internet infrastructure and service model. Our protocol follows the end-to-end principle, relying only on simple network primitives, to perform application-level group formation.}
}
EndNote citation:
%0 Thesis %A Wong, Tina Han-Ting %T Multicast Forwarding and Application State Scalability in the Internet %I EECS Department, University of California, Berkeley %D 2000 %@ UCB/CSD-00-1114 %U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2000/6423.html %F Wong:CSD-00-1114