Computer Science

Colloquium Details

Multicast Scheduling and Routing Problems

Abstract

This talk describes some recent research on multicast communication. We first examine a multicast scheduling problem that arises in heterogeneous clusters of workstations. We consider parameterized communication models for such clusters and propose efficient approximation algorithms for scheduling multicasts under these models. We next examine several multicast routing problems in wavelength-division multiplexed (WDM) optical networks. We show that while a number of these problems are NP-complete, efficient algorithms can be found for several special cases of practical interest. We give both analytical and experimental results for these algorithms.