On multicast routing in clos networks

Jan Ming Ho, De Ron Liang, Kuo Hui Tsai

研究成果: 雜誌貢獻期刊論文同行評審


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.

頁(從 - 到)417-429
期刊Journal of Information Science and Engineering
出版狀態已出版 - 9月 1997


深入研究「On multicast routing in clos networks」主題。共同形成了獨特的指紋。