Multicast tree construction in bus-based networks. (technical)

Multicast Tree Construction in Bus-Based Networks In recent years, there has been an increase in the number of group-based applications composed of cooperative processing entities. Examples of such applications include multimedia teleconferencing [3], replicated databases [47], distributed operating system services [7, 13, 49, 51], factory automation [25], and parallel processing [24]. The communication among processes in group-based applications can be characterized in three ways. First, such communication typically requires the multicast transmission capability. Multicast allows for one source node to communicate with more than one destination node. Second, the communication is often temporally local, that is, the time between group messages is short relative to the lifetime of the group. Indeed, communication may be isochronous in that data messages must be transmitted and received at regular intervals of time. Third, communication is usually symmetric, that is, any group member may send messages to the other group members. We define group communication to be temporally local, symmetric, multicast communication.

Concurrently with the burgeoning of group-based applications, networks composed of multiple-access media, or buses, are becoming increasingly popular. We refer to a bus-based network as one in which every communication link is a multiple-access medium. Examples of bus-based networks include interconnected local area networks [43], multichannel local area networks [33], and bus-based interconnection networks for parallel processors [5]. In bus-based networks, a relatively small number of buses can support a large number of nodes. Hence, the diameter of the network can be kept small, making it possible to closely couple clusters of nodes. These properties are desirable for carrying group communication.

A multicast tree is a collection of communication links spanning the nodes on which the members of a process group reside [15, 50]. 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. For most group-based applications, it is beneficial to establish multicast connections between the group members over multicast trees. The overhead associated with routing messages is incurred only once, when the multicast tree is constructed. This article addresses the multicast tree construction problem in bus-based networks. This problem differs fundamentally from the tree construction problem in point-to-point networks [50]. Because they fail to account for the broadcast property of the media, algorithms for constructing multicast trees in point-to-point networks perform poorly in bus-based networks. The tree construction problem has been shown to be NP-hard for most classes of bus-based networks. We present heuristic algorithms that exploit the broadcast property of the media in order to construct good trees. In addition to a heuristic algorithm for construction of multicast trees in general bus-based networks, that is, networks with arbitrary topologies, we also present simpler algorithms for constructing trees in an important class of bus-based networks: grids of buses. (Due to space limitations, many details are omitted in this paper; they may be found in [35-41]).

In this article, we will first discuss bus-based networks and review several multicast strategies. Next, we formulate the tree construction problem for bus-based networks in graph theoretical terms. Following sections will present a heuristic algorithm for multicast tree construction in general bus-based networks, discuss its worst-case complexity, and compare its performance with that of a multicast tree algorithm designed for point-to-point networks. Also, we discuss the multicast tree problem in two-dimensional grids. Polynomialtime algorithms for constructing trees in regular grids and general grids are described. Finally, we review related results and summarize our thoughts.

BACKGROUND AND MOTIVATIONS

Figure 1 depicts four examples of bus-based networks. The most well-known examples of bus-based networks are interconnected local area networks (LANs), where each LAN is a bus. LANs may be connected using either bridges or routers [45]. Passive star couplers offer an efficient way to organize optical fibers as buses [32]. Figure 1a depicts twelve nodes networked together with three optical stars. Another type of bus-based network is the multiple-hop packet radio network [30, 46]. In these networks, mobile nodes share a common radio channel, but only nodes within line of sight of one another can communicate directly. Messages sent among nodes not within line of sight must be relayed one or more times. Figure 1b shows the graphical representation of a packet radio network. Network nodes are represented by vertices. There is a dashed edge between two vertices if the two nodes they represent are within line of sight. Each clique, or complete subgraph, can be thought of as a bus. A third type of bus-based network is the bus-based multicomputer network, used for parallel processing. In a bus-based multicomputer, the individual processors communicate by passing messages via a communication network consisting of multiple-access media. Again, optical star couplers provide an effective way to construct interconnection networks for bus-based multicomputers [32]. An example of a bus-based multicomputer is the spanning bus hypercube [52], shown in Figure 1c. Advances in fiber optic technology have been largely responsible for the interest in a fourth type of bus-based network, the multichannel network. A multichannel network consists of parallel multiple-access channels multiplexed on a single physical medium [33]. Multichannel networks offer a practical way to harness the high bandwidths of optical fibers, limit the cost and complexity of interfaces at network nodes, permit more gradual system growth, and increase the fault-tolerance of the network. Requiring that every node have a transmitter/receiver pair, or transceiver, to every channel may be prohibitively expensive. Hence, several proposed interconnection schemes for multichannel networks offer only partial connectivity [1, 34]. The result is a logical bus-based network constructed atop a single physical medium. Figure 1d shows an example of a multichannel network in which six nodes share a four-channel network. Each node has a bus interface that permits access to two buses.

When groups of processes in a computer network communicate, it is better to use an underlying multicast communication service than to require that applications implement their own protocols. Multicast can be supported using separate addressing, in which a separate copy of the message is sent to each destination. It can also be supported using multidestination addressing, in which a small number of multiply-addressed messages are sent for each multicast. When a message arrives at an intermediate node, its destination addresses are apportioned among multiple copies of the message such that destinations along the same route share the same copy. Multidestination addressing has been studied for general internets [2, 10], packet radio networks [6], and multicomputer networks, particularly binary hypercubes [29]. Other multicast transmission methods include source routing [43, 44] in bridged local area networks. Source routing is similar to multidestination addressing, but explicit routing information, rather than a list of destinations, is placed in the header. An extensive discussion of multicast strategies can be found in [16].

The multicast schemes just mentioned have drawbacks when used to support group communication. With separate addressing, redundant copies of a message and a separate acknowledgment from each destination may result in excessive bandwidth consumption and network congestion. Multidestination addressing and source routing require variable length message headers, as well as apportioning of addresses and routing at intermediate nodes for every message. Source routing is inefficient in that acknowledgments must be sent individually from each destination to the source.

Tree-forwarding [15, 16] avoids these problems by constructing multicast virtual circuits between …