On multicast routing in clos networks

Jan Ming Ho, De Ron Liang, Kuo Hui Tsai

Research output: Contribution to journalArticlepeer-review


Multicast routing in high speed networks is one of the key issues in the design and implementation of applications such as video conferencing. Traditionally, the problem is formalized as either the shortest path problem or Steiner tree problem, where the objective function is either the shortest path or the minimum costs associated with the path. Furthermore, the problem of multicast routing is usually solved as an offline problem in the sense that the set of multicast requests to which the network is subject is static and is given beforehand. In this paper, we study an online multicast routing problem in a Clos network with two optimizing criteria: network throughput and quality of service (or QOS). We propose five routing algorithms according to five system measures using a routing index. The problem of finding an optimal routing according to each of these system measures corresponds to an off-line routing problem. We prove that all of these off-line routing problems except the least-busy routing problem (LB) are NP-complete. We also give the results of a series of simulation experiments on carried out to study the system performance, namely, the network throughput and QOS, using these routing algorithms as online algorithms, The simulation results indicate that the routing algorithms have little impact on the network throughput, but that they have a major impact on the QOS. The LB, the linear time algorithm, outperforms other algorithms when they are used as online routing algorithms as far as the QOS is concerned.

Original languageEnglish
Pages (from-to)417-429
Number of pages13
JournalJournal of Information Science and Engineering
Issue number3
StatePublished - Sep 1997


  • ATM networks
  • Clos networks
  • Multicast routing
  • Routing algorithms
  • Simulation


Dive into the research topics of 'On multicast routing in clos networks'. Together they form a unique fingerprint.

Cite this