Multicast has become an important service in modern network applications. Multicast routing is a difficult issue, particularly under delay or bandwidth constraints. This paper discusses Steiner trees in the modeling of multicast routings and various routing constraints required by applications. It also discusses the existing multicast routing algorithms, especially the routings under constraints, such as delay constraint, limited available bandwidth, and traffic load balancing. Extensive simulations have been conducted to reveal the relationships between the network cost of the routing and each of the discussed constraints.
GilbertPollakH.O.1968. “Steiner minimal tree.” SIAM J. Appl Math. vol. 16.
2.
GareyM.R.JohnsonD.S.1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. Sage UK: London, England: SAGE Publications.
3.
KouL.MarkowskyG.MermanL.1981. “A fast algorithm for Steiner trees.” Acta Informatica vol. 15, pp. 141–145.
4.
MakkiK.1991. “A new approximation algorithm for the Steiner tree problem.” Congressus Numerantium vol. 80.
5.
MakkiK.PissinouN.FriederP.1996. “Efficient solutions to multicast routing in communication networks.” Mobile Networks and Applications vol. 2, no. 5, October.
6.
Rayward-SmithV.J.ClareA.1986. “On finding Steiner vertices.” Networks vol. 16, pp. 283–294.
7.
TakahashiH.MatsuyamaA.1980. “An approximate solution for the Steiner problem in graphs.” Math. Japan vol. 24, no. 6, pp. 573–577.
8.
WaxmanB.M.1988. “Routing of multipoint connections.” IEEE Journal on Selected Areas in Communications vol. 6, no. 9, December, pp. 1617–1622.
9.
HwangF.K.RichardsD.S.1992. “Steiner tree problems.” Networks vol. 22, pp. 55–89.
10.
WinterP.1987. “Steiner problem in networks: A survey.” Networks vol. 17, pp. 129–167.
11.
RosenkrantzD.J.StearnsR.E.LewisP.M.1977. “An analysis of several heuristics for the traveling salesman problem.” SIAM J. Comput. vol. 3, no. 6.
FordJ.FulkersonD.R.1962. Flows in Networks. SAGE Publications, Sage UK: London, England.
14.
ChenG.HouleM.KuoM.1993. “The Steiner problem in distributed computing systems.” Information Sciences vol. 74, no. 1-2, October, pp. 73–96.
15.
GallargerR.G.HumbletP.A.SpiraP.M. “A distributed algorithm for minimum-weight spanning trees.” ACM Transactions on Programming Languages and Systems vol. 5, no. 1, pp. 66–77.
16.
KompellaV.P.PasqualeJ.C.PolyzosG.C., “Optimal multicast routing with quality of service constraints.” Journal of Network and Systems Management vol. 4, no. 2, pp. 107–131.
17.
Bharath-KumarK.JaffeJ.M.1983. “Routing to multiple destinations in computer networks.” IEEE Trans. Commun. vol. COM-31, March, pp. 343–351.
18.
BauerF.VarmaA.1996. “Distributed algorithms for multicast path set up in data networks.” IEEE/ACM Transactions on Networking vol. 4, no. 2, April, pp. 181–191.
19.
CormenT.H.LeisersonC.E.RivestR.L.1992. Introduction to Algorithms. SAGE Publications, Sage UK: London, England.
20.
JiaX.1996. “A distributed multicast algorithm in data networks.” submitted to IEEE Transactions on Parallel and Distributed Computing.
21.
JiaX.PissinouN.MakkiK.1996. “A delay bounded multicast routing algorithm in wide area networks.” Proceedings of the 6th International Conference on Computer Communications and Networks. SAGE Publications, Sage UK: London, England, pp. 207–212.
22.
KompellaV.P.PasqualeJ.C.PolyzosG.C.1993. “Multicast routing for multimedia communication.” IEEE/ACM Transactions on Networking vol. 1, no. 3, June, pp. 286–292.
23.
JiaX.LeeC.H.NgJ.M.ChanE.1996. “Multiple minimum Steiner trees for multicast routing in wide area networks.” Proceedings of the 19th Australian Computer Science Conference (ACSC-19). Melbourne, February, pp. 383–390.
24.
AhnS.DuD.H.1993. “A load balancing multicast tree approach for group-based multimedia applications.” Proceedings of the IEEE 18th Conference on Local Computer Networks. Minnesota, September, pp. 327–336.
