Online multicast in connection oriented networks
Baruch Awerbuch, Tripurari Singh · 2000
Multicast applications, wherein a set of network users receive a given signal, has attracted a lot of attention lately. Video conferencing is perhaps the most popular application of multicasting; live broadcasts on the Internet are another. More recently web replication has also emerged as an important application of multicast. Web replication requires heavily loaded web sites to be cached at different geographical locations, so that most requests can be satisfied locally. The task of keeping these cache copies current is essentially a multicast problem. Routing and admission control are two important issues in multicast. Routing a connection requires the network administrator to compute a path from the requested connection's source node to its destination node. Admission control is the more fundamental question of deciding which connections to accept and which to reject. Accepted connections are then routed. In this thesis we examine two scenarios, one in which admission control is needed and another in which it is not. Specifically, we first take an algorithmic approach to the “Throughput Competitive Multicast Problem” described below. Admission control is the central issue in this problem. We then experimentally study routing in the Private Network to Network Interconnect (PNNI) framework. This problem does not involve admission control. In the throughput competitive online multicast problem requests for connections to various signal sources arrive online and the network administrator has to make both admission control and routing decisions. These decisions must be made online and he has to ensure that no link is assigned more traffic than its capacity. Connection requests that are rejected are lost forever. The network administrator's objective is to maximize the throughput of the network; or more generally the revenue earned by the network, if each requesting node promises money in exchange for connection. The throughput competitive online multicast problem forms the bulk of this thesis. In the process of solving it we define the Online Maximal Dense Tree problem and provide a polylogarithmically competitive solution. Using this algorithm we provide a polylogarithmically competitive algorithm for the throughput competitive online multicast problem. Finally, we study the issues of topology aggregation in a hierarchical network, and the routing problem given the aggregated topology. The objective of our study is to maximize the throughput of the network, and minimize its control load. Over two hundred network scenarios are simulated in an attempt to optimize performance.