Parallel computing on networks of workstations is fast becoming a cost-effe
ctive high-performance computing alternative to MPPs. Such a computing envi
ronment typically consists of processing nodes interconnected through a swi
tch-based irregular network. Many of the problems that were solved for regu
lar networks have to be solved anew for these systems. One such problem is
that of efficient multicast communication. In this paper, we propose two br
oad categories of schemes for efficient multicasting in such irregular netw
orks: network interface-based (NI-based) and switch-based. The NI-based mul
ticasting schemes use the network interface of intermediate destinations fo
r absorbing and retransmitting messages to other destinations in the multic
ast tree. In contrast, the switch-based multicasting schemes use hardware s
upport for packet replication at the switches of the network and a concept
known as multidestination routing to convey a multicast message from one so
urce to multiple destinations. We first present alternative schemes for eff
icient multipacket forwarding at the NI and derive an optimal k-binomial mu
lticast tree for multipacket NI-based multicast. We then propose two switch
-based multicasting schemes that differ in the power of the encoding scheme
and the complexity of the decoding logic at the switches. These multicasti
ng schemes use path-based multidestination worms that can cover all nodes c
onnected to switches along a valid unicast path and tree-based multidestina
tion worms that can cover entire destination sets in a single phase using o
ne worm, respectively. For each scheme, we describe the associated header e
ncoding and decoding operation, the method for deriving multidestination wo
rms that cover arbitrary multicast destination sets, and the multicasting s
cheme using the derived multidestination worms. We then compare the NI-base
d multicasting scheme to the switch-based multicasting schemes with path-ba
sed and tree-based multidestination worms using simulation to determine the
system parameters that affect each of the schemes and the range of system
parameters for which each scheme performs best. Our results show that the s
witch-based multicasting scheme using a single tree-based multidestination
worm performs the best among the three schemes. However, the NI-based multi
casting scheme is capable of delivering high performance compared to the sw
itch-based multicast using path-based worms, especially when the software o
verhead at the network interface is less than half of the overhead at the h
ost. We therefore conclude that support for multicast at the NI is an impor
tant first step to improving multicast performance. However, there is still
considerable gain that can be achieved by supporting hardware multicast in
switches. Finally, while supporting such hardware multicast, it is better
to support schemes that can achieve multicast in one phase.