References

1

S. Sabri and B. Prasada, ``Video conferencing systems'', Proceedings of the IEEE, vol. 73, no. 4, pp. 671--688, April 1985.

2

S. Casner, K. Seo, W. Edmond, and C. Topolcic, ``N-way conferencing with packet video'', in Proceedings of the Third International Workshop on Packet Video, March 22--23 1990.

3

C.A. Ellis, S.J. Gibbs, and G.L. Rein, ``Groupware: Some issues and experiences'', Communications of the ACM, vol. 34, no. 1, pp. 39--58, January 1991.

4

I. Grief, Ed., Computer Supported Co-operative Work, Morgan Kaufmann Publishers, 1992.

5

B. Leiner, ``Critical issues in high bandwidth networking'', Internet Request For Comments, November 1988, RFC 1077.

6

C. Partridge, ``Workshop report: Internet research steering group workshop on very-high-speed networks'', Internet Request For Comments, April 1990, RFC 1152.

7

W.D. Sincoskie, ``Video on demand: is it feasible?'', in Proceedings of the IEEE GLOBECOM '90, December 1990, pp. 201--205.

8

J. Sutherland and L. Litteral, ``Residential video services'', IEEE Communications Magazine, vol. 30, no. 7, pp. 36--41, July 1992.

9

L. Guojun, ``Advances in digital image compression techniques'', Computer Communications, vol. 16, no. 4, pp. 202--214, April 1993.

10

D. Le Gall, ``MPEG: A video compression standard for multimedia applications'', Communications of the ACM, vol. 34, no. 4, pp. 46--58, April 1991.

11

M. Liou, ``Overview of the 64 Kbit/s video coding standard'', Communications of the ACM, vol. 34, no. 4, pp. 59--63, April 1991.

12

``Engineering and operations in the Bell system'', AT&T Bell Laboratories, 1984.

13

D. Ferrari, ``Client requirements for real-time communication services'', IEEE Communications Magazine, vol. 28, no. 11, pp. 65--72, November 1990.

14

D.B. Hehman, M.G. Salmony, and H.J. Stuttgen, ``Transport services for multimedia applications on broadband networks'', Computer Communications, vol. 13, no. 4, pp. 197--203, May 1990.

15

D. Ferrari, ``Delay jitter control scheme for packet-switching internetworks'', Computer Communications, vol. 15, no. 6, pp. 367--373, July-August 1992.

16

D.D. Clark, S. Shenker, and L. Zhang, ``Supporting real-time applications in an integrated services packet network: Architecture and mechanism'', Computer Communications Review, vol. 22, no. 4, pp. 14--26, October 1992, (Proceedings of the ACM SIGCOMM '92).

17

L. Zhang, S. Deering, D. Estrin, S. Shenker, and D. Zappala, ``RSVP: A new resource reservation protocol'', IEEE Network, vol. 7, no. 5, pp. 8--18, September 1993.

18

J.C. Bolot, T. Turletti, and I. Wakeman, ``Scalable feedback control for multicast video distribution in the Internet'', Computer Communications Review, vol. 24, no. 4, pp. 58--67, October 1994, (Proceedings of the ACM SIGCOMM '94).

19

M. Nomura, T. Fujii, and N. Ohta, ``Basic characteristics of variable rate video coding in ATM environment'', IEEE Journal on Selected Areas in Communications, vol. 7, no. 5, pp. 752--760, June 1989.

20

W.H. Leung, T.J. Baumgartner, Y.H Hwang, M.J. Morgan, and S.C. Tu, ``A software architecture for workstations supporting multimedia conferencing in packet switching networks'', IEEE Journal on Selected Areas in Communications, vol. 8, no. 3, pp. 380--390, April 1990.

21

L. Trajkovic and S.J. Golestani, ``Congestion control for multimedia services'', IEEE Network, vol. 6, no. 5, pp. 20--26, September 1992.

22

A.E. Eckberg, ``B-ISDN/ATM traffic and congestion control'', IEEE Network, vol. 6, no. 5, pp. 28--37, September 1992.

23

J. Kurose, ``Open issues and challenges in providing QoS guarantees in high-speed networks'', Computer Communications Review, vol. 23, no. 1, pp. 6--15, January 1993.

24

G. Karlsson and M. Vetterli, ``Packet video and its integration into the network architecture'', IEEE Journal on Selected Areas in Communications, vol. 7, no. 5, pp. 739--751, June 1989.

25

M. Ghanbari, ``Two-layer coding of video signals for VBR networks'', IEEE Journal on Selected Areas in Communications, vol. 7, no. 5, pp. 771--781, June 1989.

26

A. Lippman, ``Feature sets for interactive images'', Communications of the ACM, vol. 34, no. 4, pp. 92--102, April 1991.

27

D.M. Lucantoni and S.P. Parekh, ``Selective cell discard mechanisms for a B-ISDN congestion control architecture'', in Proceedings of the 7th International Teletraffic Congress Symposium, 1990.

28

G.K. Wallace, ``The JPEG still picture compression standard'', Communications of the ACM, vol. 34, no. 4, pp. 30--44, April 1991.

29

A.J. Frank, L.D. Wittie, and A.J. Bernstein, ``Multicast communication on network computers'', IEEE Software, vol. 2, no. 3, pp. 49--61, May 1985.

30

M. Ahamad, Ed., Protocols for High-Speed Networks, Technology Series. IEEE Computer Society Press, 1990.

31

S.T. Chanson, G.W. Neufeld, and L. Liang, ``A bibliography on multicast and group communications'', Operating Systems Review, vol. 23, no. 4, pp. 20--25, October 1989.

32

D.R. Cheriton and S.E. Deering, ``Host groups: A multicast extension for datagram internetworks'', in Proceedings of the 9th Data Communications Symposium, September 1985, pp. 172--179.

33

J. Crowcroft and K. Paliwoda, ``A multicast transport protocol'', Computer Communications Review, vol. 18, no. 4, pp. 247--256, August 1988, (Proceedings of the ACM SIGCOMM '88).

34

E.W. Dijkstra, ``A note on two problems in connection with graphs'', Numerische Mathematik, vol. 1, pp. 269--271, 1959.

35

R.E. Bellman, Dynamic Programming, Princeton University Press, Princeton, N.J., 1957.

36

L.R. Ford Jr. and D.R. Fulkerson, Flows in Networks, Princeton University Press, Princeton, N.J., 1962.

37

J. Moy, ``Multicast routing extensions for OSPF'', Communications of the ACM, vol. 37, no. 8, pp. 61--66, August 1994.

38

S.E. Deering and D.R. Cheriton, ``Multicast routing in internetworks and extended LANs'', ACM Transactions on Computer Systems, vol. 8, no. 2, pp. 85--110, May 1990.

39

S.L. Hakimi, ``Steiner's problem in graphs and its implications'', Networks, vol. 1, pp. 113--133, 1971.

40

M.R. Garey, R.L. Graham, and D.S. Johnson, ``The complexity of computing Steiner minimal trees'', SIAM Journal on Applied Mathematics, vol. 34, pp. 477--495, 1978.

41

V.J. Rayward-Smith, ``The computation of nearly minimal Steiner trees in graphs'', Intl. J. Math. Educ. Sci. Tech., vol. 14, no. 1, pp. 15--23, 1983.

42

L. Kou, G. Markowsky, and L. Berman, ``A fast algorithm for Steiner trees'', Acta Informatica, vol. 15, pp. 141--145, 1981.

43

D.W. Wall, Mechanisms for Broadcast and Selective Broadcast, PhD thesis, Computer Science Department, Stanford University, 1982.

44

B.M. Waxman, ``Routing of multipoint connections'', IEEE Journal on Selected Areas in Communications, vol. 6, no. 9, pp. 1617--1622, December 1988.

45

B.K. Kabada and J.M. Jaffe, ``Routing to multiple destinations in computer networks'', IEEE Transactions on Communications, vol. 31, no. 3, pp. 343--351, March 1983.

46

L. Aguilar, J.J. Garcia-Luna-Aceves, D. Moran, E.J. Graighill, and R. Brungardt, ``Architecture for a multimedia teleconferencing system'', in Proceedings of the ACM SIGCOMM '86 Symposium, August 1986, pp. 126--136.

47

A. Ballardie, J. Crowcroft, and P. Francis, ``Core based trees (CBT) --- An architecture for scalable inter-domain multicast routing'', Computer Communications Review, vol. 23, no. 4, pp. 85--95, October 1993, (Proceedings of the ACM SIGCOMM '93).

48

S. Deering, D. Estrin, D. Farinacci, V. Jacobson, C. Liu, and L. Wei, ``An architecture for wide-area multicast routing'', Computer Communications Review, vol. 24, no. 4, pp. 126--135, October 1994, (Proceedings of the ACM SIGCOMM '94).

49

S. Pingali, D. Towsley, and J.F. Kurose, ``A comparison of sender-initiated and receiver-initiated reliable multicast protocols'', Performance Evaluation Review, vol. 22, no. 1, pp. 221--230, May 1994, (Proceedings of the ACM SIGMETRICS Conference on Measurement and Modelling of Computer Systems).

50

K. Mase, T. Takenada, H. Yamamoto, and M. Shinihara, ``Go-back-n ARQ schemes for point-to-multipoint satellite communications'', IEEE Transactions on Communications, vol. 31, no. 4, pp. 583--589, April 1983.

51

S.R. Chandran and S. Lin, ``Selective-repeat-ARQ schemes for broadcast links'', IEEE Transactions on Communications, vol. 40, no. 1, pp. 12--19, January 1992.

52

P.V. Mockapetris, ``Analysis of reliable multicast algorithms for local networks'', in Proceedings of the 8th Data Comm. Symp., October 1983, pp. 150--157.

53

H. Santoso and S. Fdida, ``Transport layer multicast: An enhancement for XTP bucket error control'', IFIP Transactions C (Communication Systems), vol. C-14, pp. 333--349, 1993.

54

S. Armstrong, A. Freier, and K. Marzullo, ``Multicast transport protocol'', Internet Request For Comments, February 1992, RFC 1301.

55

N. Shacham and P McKenney, ``Packet recovery in high-speed networks using coding and buffer management'', in Proceedings of the IEEE INFOCOM '90, June 1990, pp. 124--131.

56

E.W. Biersack, ``Performance evaluation of forward error correction in ATM networks'', Computer Communications Review, vol. 22, no. 4, pp. 248--257, October 1992, (Proceedings of the ACM SIGCOMM '92).

57

L. Hughes, ``Survey of multicast address handling techniques for Ethernet communication controllers'', Microprocessors and Microsystems, vol. 13, no. 9, pp. 563--568, November 1989.

58

J.S. Turner, ``Design of a broadcast packet switching network'', IEEE Transactions on Communications, vol. 36, no. 6, pp. 734--743, June 1988.

59

W. De Zong, Y. Onozato, and J. Kaniyil, ``A copy network with shared buffers for large-scale multicast ATM switching'', IEEE/ACM Transactions on Networking, vol. 1, no. 2, pp. 157--165, April 1993.

60

H. Eriksson, ``MBONE: The multicast backbone'', Communications of the ACM, vol. 37, no. 8, pp. 54--60, August 1994.

61

A. Huang and S. Knauer, ``Starlite: A wideband digital switch'', in Proceedings of the IEEE GLOBECOM '84, December 1984, pp. 121--125.

62

K.Y. Eng, M.G Hluchyj, and Y.S. Yeh, ``Multicast and broadcast services in a knockout packet switch'', in Proceedings of the IEEE INFOCOM '88, March 1988, pp. 29--34.

63

T.T. Lee, ``Nonblocking copy networks for multicast packet switching'', IEEE Journal on Selected Areas in Communications, vol. 6, no. 9, pp. 1455--1467, December 1988.

64

J.S. Turner, ``Managing bandwidth in ATM networks with bursty traffic'', IEEE Network, vol. 6, no. 5, pp. 50--58, September 1992.

65

N. Shacham, ``Multipoint communication by hierarchically encoded data'', in Proceedings of the IEEE INFOCOM '92, May 1992, pp. 2107--2114.

66

R.K. Jurgen Ed., ``An abundance of video formats'', IEEE Spectrum, pp. 26--28, March 1992.

67

C. Partridge, ``A proposed flow specification'', Internet Request For Comments, September 1992, RFC 1363.

68

D. Ferrari and D.C. Verma, ``A scheme for real-time channel establishment in wide-area networks'', IEEE Journal in Selected Areas on Communications, vol. 8, no. 3, pp. 368--379, April 1990.

69

V.P. Kompella, J.C. Pasquale, and G.C. Polyzos, ``Multicast routing for multimedia communication'', IEEE/ACM Transactions on Networking, vol. 1, no. 3, pp. 286--292, June 1993.

70

V.P. Kompella, J.C. Pasquale, and G.C. Polyzos, ``Optimal multicast routing with quality of service constraints'', To appear in Journal of Systems and Network Management, 1996.

71

X. Jiang, ``Routing broadband multicast streams'', Computer Communications, vol. 15, no. 1, pp. 45--51, January-February 1992.

72

E. Biersack and J. Nonnenmacher, ``WAVE: A new multicast routing algorithm for static and dynamic multicast groups'', in Proceedings of the 5th International Workshop on Network and Operating System Support for Digital Audio and Video, April 1995.

73

M. Doad and I. Leslie, ``How bad is naive multicast routing?'', in Proceedings of the IEEE INFOCOM '93, April 1993, pp. 82--89.

74

L. Wei and D. Estrin, ``The trade-offs of multicast trees and algorithms'', Tech. Rep. USC-CS-93-560, University of Southern California, Los Angeles, CA, September 1993.

75

L. Wei and D. Estrin, ``Multicast routing in dense and sparse modes: Simulation study of tradeoffs and dynamics'', Tech. Rep. USC-CS-95-613, University of Southern California, Los Angeles, CA, 1995.

76

J.C. Pasquale, G.C. Polyzos, E.W. Anderson, and V.P. Kompella, ``The multimedia multicast channel'', Internetworking: Research and Experience, vol. 5, no. 4, pp. 151--162, December 1994.

77

J.C. Pasquale, G.C. Polyzos, E.W. Anderson, and V.P. Kompella, ``Filter propagation in dissemination trees: Trading off bandwidth and processing in continuous media networks'', in Proceedings of the 4th International Workshop on Network and Operating System Support for Digital Audio and Video, November 1993, pp. 259--268.

78

T. Turletti, ``The INRIA videoconferencing system (IVS)'', ConneXions, vol. 8, no. 10, pp. 20--24, October 1994.

79

S.Y. Cheung, M.H. Ammar, and X. Li, ``On the use of destination set grouping to improve fairness in multicast video distribution'', Tech. Rep. GIT-CC-95-25, Georgia Insitute of Technology, Atlanta, GA, July 1995, To appear in the Proceedings of the IEEE INFOCOM '96.

80

V. Jacobson, ``Congestion avoidance and control'', Computer Communications Review, vol. 18, no. 4, pp. 314--329, August 1988, (Proceedings of the ACM SIGCOMM '88).

81

S. Casner, ``First IETF Internet audiocast'', Computer Communications Review, vol. 22, no. 3, pp. 92--97, July 1992.

82

S. Deering, ``Host extensions for IP multicasting'', Internet Request For Comments, August 1989, RFC 1112.

83

S. Deering, C. Partridge, and D. Waitzman, ``Distance vector multicast routing protocol'', Internet Request For Comments, November 1988, RFC 1075.

84

J. Moy, ``Multicast extensions to OSPF'', Internet Request For Comments, March 1994, RFC 1584.

85

J. Moy, ``MOSPF: Analysis and experience'', Internet Request For Comments, March 1994, RFC 1585.

86

C. Topolcic, ``Experimental Internet stream protocol, Version 2 (ST-II)'', Internet Request For Comments, October 1990, RFC 1190.

87

C. Partridge and S. Pink, ``An implementation of the revised internet stream protocol (ST-2)'', Internetworking: Research and Experience, vol. 3, no. 1, pp. 27--54, March 1992.

88

L. Delgrossi and L. Berger, ``Internet stream protocol Version 2 (ST2) protocol specification - Version ST2+'', Internet Request For Comments, August 1995, RFC 1819.

89

D.J. Mitzel, D. Estrin, S. Shenker, and L. Zhang, ``An architectural comparison of ST-II and RSVP'', in Proceedings of the IEEE INFOCOM '94, June 1994, pp. 716--725.

90

H. Schulzrinne, S. Casner, R. Frederick, and V. Jacobson, ``RTP: A transport protocol for real-time applications'', Internet Draft, Audio-Video Transport Working Group.

91

M. Hardly and V. Jacobson, ``SDP: Session description protocol'', Internet Draft, Multipart Multicast Session Control Working Group.

 
Figure 1:  The multicast tree obtained by combining the separate optimal cost paths from the sender to each of the receivers. The total cost is 21, the average delay is and the maximum delay is 4. The example graph is taken from [70].

 
Figure 2:  The multicast tree obtained by combining the separate optimal delay paths from the sender to each of the receivers. The total cost is 32, the average delay is 2 and the maximum delay is 3.

 
Figure 3:  One of the many possible Steiner multicast trees for this graph. For this tree, the total cost is 20, the average delay is and the maximum delay is 8. Note how simple cost minimisation can lead to significant increases in delay.

 
Figure:  A core based tree[47], with node H as the core. Optimal delay paths from the core to all receivers are used and senders unicast their data towards the core, again using optimal delay paths. Everything except link FH is shared among all senders. The total cost is 29, the average delay is and the maximum delay is 5. Using again H as the core, if we try to minimise cost, the resulting core tree is identical to the tree in Figure 3, with all links except FA and AE shared among all senders. The delay characteristics are the same as packets do not have to reach the core to be re-routed: multicasting starts when the path from the sender first encounters the shared tree.

 
Figure:  A Steiner tree with bounded maximum delay. The total cost is again 20, the average delay is and the (bounded) maximum delay is 4. Compare this tree with the one in Figure 3.