Group communication in bus-based computer networks

In recent years, there has been an increase in the number of group-based applications composed of cooperative processing entities. Examples include multimedia teleconferencing, distributed databases, distributed operating system services, cooperating processes in automated control, and parallel processing. The communication among processes in group-based applications typically involves multiple destinations and is often symmetric and temporally local.An increasing number of networks are composed of multiple-access media, or buses. A bus-based network is one in which every communication link is a multiple-access medium. Examples of bus-based networks are found in many types of computer networks, including metropolitan area networks, interconnected local area networks, multichannel local area networks, and interconnection networks for parallel processors.This thesis addresses the problem of supporting group communication in bus-based computer networks. The work presented in the thesis consists of two related parts. The first part addresses the problem of constructing multicast trees in bus-based networks. A multicast tree is a collection of communication links spanning the processors on which process group members reside. Messages entering the tree from one group member are routed and copied as necessary by intermediate nodes in order to be delivered to every group member. Because of the multiple-access property of the media, the problem of constructing multicast trees in bus-based networks differs fundamentally from that in point-to-point networks. In this thesis, we investigate the multicast tree construction for several classes of bus-based network topologies. For some regular topologies, we present optimal algorithms for solving the problem. In topologies for which the multicast tree problem is shown to be NP-complete, we develop and study the performance of heuristic algorithms.The second part of the thesis addresses the problem of choosing interconnection topologies for multichannel networks. Multichannel networks consisting of several parallel, medium-speed logical channels multiplexed on a single high-speed medium offer several advantages over networks with a single high-speed channel. Permitting every node to have continuous access to every channel, however, may be prohibitively expensive, and a good deal of research has addressed the problem of how to reduce the number of transceivers per node without seriously degrading the performance of the network. We study the multichannel network connectivity problem with emphasis on supporting group communication in two classes of multichannel networks. In particular, we analyze those properties of multichannel interconnection topologies that facilitate an adaptive topology. Using these results, we develop simple protocols that use recent network traffic patterns to trigger connection changes, enabling the topology to conform to network traffic patterns and, specifically, group locality.U of I OnlyETDs are only available to UIUC Users without author permissio