Routing reserved bandwith multi-point connections

ABSTRACT

Some important classes of multi-point bandwidth-intensive applications like video-conferencing with mixing and the distributed classroom can be characterized as consisting of a broadcast from a source node to several destinations nodes, and point-to-point flows from the destination nodes to the source node. Determining a tree in an arbitrary mesh network which satisfies the bandwidth constraints and minimizes the cost of reserved bandwidth is a NP-hard problem. In this paper, we look at some heuristics that can be used to solve the problem of routing these multi-point connections. The heuristics are based on finding the capacity-constrained minimum cost tree which minimizes the cost of bandwidth reserved for point-to-point communication from destinations to the source, and weights are assigned to minimize the number of extra nodes in the tree which increase the cost of bandwidth reserved from the source to the destination. A theoretical bound on the performance of some of the heuristics, as well as simulation results comparing their performance to that of the optimum solution are presented. The results are encouraging, the heuristics find a tree with a cost within 2% of the optimum on the average, and with a cost within 10% of the optimum in those cases when the heuristic fails to find the optimum tree.

REFERENCES

• 1: Hakimi, S. "Steiner's Problem in Graphs and Its Implications'', Networks, vol. 1, pp 113-133, 1971.
• 2: Kou L, Markowsky G, and Berman L, "A fast algorithm for Steiner Trees", Acta Informatica, vol. 15(1981) pp 141- 145.
• 3: V J Rayward-Smith , A Clare, On finding Steiner vertices, Networks, v.16 n.3, p.283-294, Fall 1986 [doi>10.1002/net.3230160305]
• 4: Waxman B M, "Routing of Multipoint Connections", IEEE Journal on Selected Areas in Communication, vol. 6 (1988) pp 1617-1622.
• 5: Subramanian N and Liu S, "Centralized Multi-point Routing in Wide Area Networks", Symposium on Applied Computing, Kansas City, MO, April 1991.
• 6: Xiaofeng Jiang, Routing broadband multicast streams, Computer Communications, v.15 n.1, p.45-51, Jan./Feb. 1992 [doi>10.1016/0140-3664(92)90044-F]
• 7: Robert W. Floyd, Algorithm 97: Shortest path, Communications of the ACM, v.5 n.6, p.345, June 1962 [doi>10.1145/367766.368168]
• 8: Chachra V., Ghare P M and Moore J M, "Applications of Graph Theory Algorithms", North Holland, 1979.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees; Path and circuit problems

  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.3 Communications Applications
          Subjects: Computer conferencing, teleconferencing, and videoconferencing

General Terms:
Design, Performance, Verification