CSC-91-16-MULTICAST ROUTING IN UNRELIABLE NETWORKS

Martina Schollmeyer

This work was supported in part by the National Science
Foundation under Grant Numbers MIP-8909749 and CDA-8820714, and
in part by the AMOCO Faculty Development Program.

The efficient routing of messages in a multicomputer
interconnection network is the key to the performance of such a
network. Multicast communication refers to the delivery of a
message from a source node to several destination nodes. 
Although multicast is highly desirable for many applications, it
is not directly supported in most multicomputer architectures. 
This paper examines existing algorithms for multicast routing in
multicomputer networks and groups them into a number of
categories such as multicast trees, multicast paths, multicast
stars, etc.  These algorithms are evaluated in  terms of deadlock
handling, adaptability and suitability for wormhole routing. 
Wormhole routing is a very promising switching technique for
routing in new generation multicomputer networks.  The aspect of
fault tolerance in unreliable networks is also examined briefly
and the need for the development of a deadlock-free adaptive and
fault-tolerant wormhole routing algorithm for multicast in
multicomputer networks is explaind.  The architecture of main
interest is the k-ary n-cube which comprises many commonly used
topologies from 2-D meshes to hypercubes.