Simulation Analysis of Routing Strategies in Multicasting Multiservice Loss Networks

Abstract

This paper begins with an overview of multicast algorithms, which are the most promising candidates to be in wide use in first generation Asynchronous Transfer Mode (ATM) based Broadband Integrated Services Digital Networks (B-ISDN). Since the Multiple Destination Routing (MDR) problem and the associated Steiner Tree problem are known to be NP-complete and therefore a number of heuristic algorithms have been proposed in the literature, we first need to establish which of these are the best candidates for the B-ISDN. We conclude that the weighted greedy -type algorithms are promising ones, and therefore we examine the behavior of these algorithms in terms of blocking probability and network utilization. In doing so, we use a B-ISDN call level simulation program, which proves to be an indispensable tool in the quest for efficient multicast algorithms. We find that shortest path routing with appropriate (adaptive) weight functions combined with the complete partitioning link allocation policy may give satisfactory blocking values and good network utilization in networks of different sizes.

Keywords

Multiservice networks multicast algorithms blocking probability routing

Get full access to this article

View all access options for this article.

References

Bharath-Kumar

Jaffe

J.M.

1983. “Routing to Multiple Destinations in Computer Networks.” IEEE Transactions on Communications vol. COM-31, no. 3, March, pp. 343–351.

Chow

C.-H.

1991. “On multicast path finding algorithms.” IEEE INFOCOM '91, pp. 1274–1283.

Kou

Markowsky

Berman

1981. “A Fast Algorithm for Steiner Trees.” Acta Informatica vol. 15, pp. 141–145.

Kompella

W.P.

Pasquale

J.C.

Polyzos

G.C.

1992. “Multicasting for multimedia applications.” IEEE INFOCOM '92, Florence, Italy, May, pp. 2078–2085.

Leung

Y.-W.

Yum

T.-S.

1991. “Efficient algorithms for multiple destinations routing.” International Conference on Communications vol. 3, June, pp. 1311–1317.

Tanaka

Huang

P.-C.

1993. “Multiple destination routing algorithms.” IEICE Transactions on Communication vol. E76-B, no. 5, May, pp. 544–552.

Waxman

B.M.

1988. “Routing of multipoint connections.” IEEE J. Selected Areas in Communications vol. 6, no. 9, December, pp. 1617–1622.

Waxman

B.M.

1993. “Performance evaluation of multipoint routing algorithms.” IEEE INFOCOM '93, San Francisco, CA, USA, pp. 980–986.

Kelly

F.P.

1995. “The Clifford Paterson lecture.” Proc. of Royal Soc., London.

10.

Ross

K.W.

1995. Multiservice Loss Models For Broadband Telecommunications Networks. Sage UK: London, England: SAGE Publications.

11.

11 Fodor

, et al. 1994. “A flexible simulation platform for ATM networks.” SCS European Simulation Symposium ESS '94, Istanbul, Turkey.

12.

Garey

M.R.

Johnson

D.S.

1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. Sage UK: London, England: SAGE Publications.

13.

Prim

1957. “Shortest connection networks and some generalizations.” Bell Systems Tech. J. vol. 36, pp. 1389–1401.

14.

14 Fodor

, et al. 1995. “On the call and cell level resource allocation in ATM networks.” SCS European Simulation Symposium, ESS '95, Erlangen, Germany.

15.

15 Fodor

, et al. 1996. “Simulative analysis of end-to-end call blocking probability evaluation techniques in multirate loss networks.” Proceedings of the SCS European Simulation Multiconference, ESM '96, Budapest, Hungary.

16.

Szarkowicz

1995. Multicasting in ATM Networks. Master's Thesis, Technical University of Budapest, Department of Telecommunications and Telematics, Hungary.

17.

Buhr

P.A.

Ditchfield

Stroobosscher

R.A.

Younger

B.M.

Zarnke

C.R.

1992. “mC++: Concurrency in the object-oriented language C++.” Software - Practice and Experience vol. 22, no. 2, February, pp. 137–172.

18.

Doar

Leslie

1993. “How bad is naive multicast routing?” IEEE INFOCOM '93, San Francisco, CA, USA, pp. 82–89.

19.

Noronha

C.A.

Jr.

1994. Routing of Video/Audio Streams in Packed-Switched Networks. Technical Report No. CSL-TR-94-653, Computer Systems Laboratory, Department of Electrical Engineering and Computer Science, Stanford University, Stanford, CA, USA, December.

20.

Szarkowicz

Fodor

Faragó

Henk

1997. “Simulative analysis of optimal link allocation strategies in multicasting multiservice loss networks.” In preparation.