On multicast routing in clos networks

Abstract

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.