Multicasting in generalized multistage interconnection networks

Sourav Bhattacharya, Gary Elsesser, Wei Tek Tsai, Ding Zhu Du

Research output: Contribution to journalArticlepeer-review

9 Scopus citations


Multistage interconnection networks (MIN) are popular in switching and communication applications. It is also well known as a hypercube derived architecture, offering a fixed-degree alternative to hypercube for a large class of applications. Message routing strategy in MIN is well known, however, multicasting issues for MIN has not been considered. This paper formulates the multicasting problem for MIN. We demonstrate that reordering the dimensions in MIN can lead to traffic reduced multicasting. This leads to the formulation of optimality criteria in MIN multicast operation. Traffic optimum multicasting in MIN is shown as a NP-Complete problem. We present a polynomial time greedy heuristic to generate traffic reduced multicast in MIN. The greedy approach generates a locally optimum solution. Analytical study and simulation results are presented showing the traffic reduction that can be obtained using our approach over traditional linearly ordered dimensions approach.

Original languageEnglish (US)
Pages (from-to)80-95
Number of pages16
JournalJournal of Parallel and Distributed Computing
Issue number1
StatePublished - Jul 1994
Externally publishedYes

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Artificial Intelligence


Dive into the research topics of 'Multicasting in generalized multistage interconnection networks'. Together they form a unique fingerprint.

Cite this