Multicasting schemes and performance issues of interconnection networks
Cathy Wai-Chun Chan, Soung Chang Liew · 1997
One of the major challenges in the design of switching networks is the provision of multicast capability, or the ability to support point-to-multipoint connections, which is required in a wide range of applications such as tele-conferencing and video distribution systems. While many multistage multicast packet switches have been proposed to handle these connections in the switching context in which nodes are connected via a central packet switch, little effort has been spent on supporting multicast connections among nodes in a closed network. This thesis focuses on multicasting in the closed network scenario and investigates how this can be achieved in a systematic manner in arbitrary closed networks. A multistage multicast packet switch is usually obtained by a cascade combination of a copy network and a point-to-point packet switch. In the closed network scenario, we can apply a similar methodology by splitting the multicast process into the replication phase and the routing phase in the time domain. In the replication phase, sufficient copies of a multicast packet are first generated by a replication algorithm. These copies are subsequently routed to their respective destinations in the routing phase. We show that by using a general replication algorithm for the replication phase, multicast capability can be incorporated into any closed interconnection networks. We will evaluate the performance of the general multicast network and derive a general throughput equation that relates the multicast throughput to the point-to-point routing delay. In this way, the performance of a multicast network can be obtained by making use of the results of the point-to-point analysis of the same network. Our analysis results indicate that the performance of a multicast network is affected by two detrimental phenomena known as deadlocks and network instability. To prevent such problems, we propose a deadlock-breaking mechanism and several access control schemes. With these protective measures, the maximum network throughput can be achieved. To complete the study, we investigate the memory requirements associated with the multicast scheme and discuss several alternatives in the destination address resolution process at the end of the packet replication phase. We will show that by properly choosing the locations for the destination address information, the amount of memory required can be significantly reduced at the cost of a slight reduction in network throughput.