The widely popular World Wide Web along with advances in desktop computers has brought the world into a new age of computing and communications. Low bit-rate video applications across the Internet are quickly emerging. The ITU-T H.263 standard was designed for low bit-rate video conferencing across phone lines and is an ideal candidate to be extended for Internet video applications. This paper focuses on the error robustness issue of compressed H.263 video streams when transmitted over the Internet. The traditional approach of inserting intra-coded frames increases the error resilience at the expense of bursty output traffic, lower picture quality, and uneven frame dropping. By extending the macroblock force update feature of the H.263 standard, we developed a scheme that complies with the standard and increases the robustness of the video stream. This macroblock updating scheme analyzes the temporal dependencies of macroblocks in successive frames and selectively updates the macroblocks which have the most impact on later frames. The performance evaluation of the proposed technique demonstrates that it achieves a good balance between error recovery speeds and video quality.

The feasible-region is a simple and optimal framework for scheduling the transmission of data with deadlines. We establish the fundamental relationship between the bandwidth requirement and the initial delay in feasible-region-based transmission scheduling. The relationship represents the optimal bandwidth/delay tradeoff. In the process, we identify the essential bandwidth, the exact bandwidth lower bound regardless of the initial delay. Efficient algorithms are given to calculate the essential bandwidth as well as the optimal bandwidth/delay tradeoff. The results extend the previous results on feasible-region-based scheduling, most of which were derived in the context of video traffic smoothing. When applied to the problem of scheduling scalable multimedia, we show that the feasible-region framework enables the integrated scheduling of presentation and transmission and is a new and promising approach of dealing with scalable multimedia. We establish the presentation feasibility condition and present some initial results on scheduling spatial scalability.

The Internet explosion is driving the need for new collaboration tools which will enable two or more users to share data, audio, and video. The real-time packet-based solutions which are emerging differ considerably from the circuit-switch solutions which have existed for some time now. In this paper, we present one such packet-based approach, the Multimedia Multiparty Teleconferencing (MMT) system, which was fully implemented as a research prototype. Using MMT as an example, we address some of the fundamental issues related to videoconferencing systems in a packet-based environment, and discuss the differences with the traditional circuit-switch approaches, namely, the ITU H.320 standard. In particular, MMT is a distributed solution, while H.320 is centralized. The use of multicast and a novel video-mixing technique to facilitate the distributed solution are presented. Furthermore, MMT audio and video streams are susceptible to congestion and packet loss in the shared media packet-based environment, while H.320 streams use dedicated connections. As such, synchronization, error resilience, and dynamic rate control schemes for the packet-based system are presented.

An approximation technique is presented to evaluate the dependability of FDDI networks. This technique, based on the most likely paths to failure concept, is simple and practical. It may be applied easily to evaluate and compare the dependability of different FDDI network configurations. The effects of various network parameters on the network availability are examined. We conclude that, in order to guarantee high availability, an FDDI network backbone should be interconnected using dual-attachment concentrators. Furthermore, dual-homing configurations are required for high-availability paths between end stations and the backbone. For less stringent availability requirements, single-attachment concentrator trees with single attachment stations may suffice. We also discuss how the technique may be extended easily to more general heterogeneous networks including Token Ring and Ethernet.

At the data-link layer, ATM offers a number of features, such as high-bandwidth and per-session quality-of-service (QoS) guarantees, making it particularly attractive to multimedia applications. Unfortunately, many of these features are not visible to applications because of the inadequacies of existing higher-level protocol architectures. Although there is considerable effort underway to tune these protocols for ATM networks, we believe that a new ATM-specific protocol stack is essential to effectively exploit all the benefits of ATM. We describe the semantics of such a protocol stack, and discuss its advantages over traditional protocol architectures from the perspective of multimedia applications. The performance impact of the new protocol architecture is experimentally demonstrated on a video conferencing testbed built around IBM RS/6000's equipped with prototype hardware for video/audio processing, and connected via ATM links.

Asynchronous transfer mode (ATM) is a connection-oriented technology in which all communication is based on virtual connections established prior to the transfer of data. It is expected that the bulk of traffic carried by the ATM network will be data traffic, e.g., local area network (LAN) internetwork traffic. Hence, a major issue regarding ATM is the support for connectionless (datagram) traffic. A scheme for the efficient support for connectionless traffic in ATM LANs based on trees of virtual connections is proposed. In this scheme, a sink tree is built for every switch in the LAN. Each tree provides an efficient means of routing connectionless traffic from any switch in the network to the sink switch (root) of the tree. The sink tree solution may also be used to broadcast connectionless messages in the reverse direction. The trees can easily be updated to adapt to topological changes or congestion in the network. A protocol for refreshing the tree structure using the ATM switch routing tables is described. An adaptive rate control solution, in conjunction with fast back pressure at the ATM layer, is presented. It is shown that this scheme achieves high utilization of available bandwidth for connectionless traffic, has low cell loss probability, and small overhead.

ATM is a connection-oriented technology in which all communication is based on virtual connections established prior to the transfer of data. Initially, it is expected that the bulk of traffic carried by the ATM network will be data traffic. Hence, a major issue regarding ATM is the support for connectionless (datagram) traffic. A scheme for the efficient support for connectionless traffic in ATM LANs based on trees of virtual connections is proposed. In this scheme a sink tree is built for every switch in the LAN. Each tree provides an efficient means of routing connectionless traffic from any switch in the network to the sink switch (root) of the tree. The sink tree solution may also be used to broadcast connectionless messages in the reverse direction. The trees can easily be updated to adapt to topological changes or congestion in the network. A protocol for refreshing the tree structure using the ATM switch routing tables is described.>

An approximation technique is presented to evaluate the dependability of computer networks. This technique, based on the most likely paths to failure, is simple and practical. It may easily be applied by a network designer in evaluating and comparing different network configurations. The approximation technique is applied to a variety of FDDI network configurations. The effect of certain network parameters on the network availability are examined. From these results the authors conclude that, in order to guarantee high availability, an FDDI network backbone should be interconnected using dual attachment concentrators. Furthermore, dual-homing configurations are required for high availability paths between end-stations and the backbone. For less stringent availability requirements, single attachment concentrator trees with single attachment stations may suffice.>

This paper examines the issues involved in the design of conference servers that support multiparty, multimedia conferences. These servers, called multipoint control units (MCUs) in the telephony world, coordinate the distribution of audio, video, and data streams amongst the multiple participants in a videoconference. The MCU is responsible for the processing of video and audio so that a conference participant can hear and see one or more of the other participants in the conference. It is also responsible for handling and forwarding the data streams from the participants. This paper presents different approaches to the design of an MCU to implement these functions. It also describes the design of a related device-a transcoding gateway that enables conferencing between participants using different video/audio equipment.>

The suitability of IEEE 802.5 token ring LANs for the transport of multimedia traffic is examined. The token ring priority mechanisms and end-station queuing policies are studied in order to understand their effect on the delay characteristics of multimedia traffic. The multimedia traffic is modeled as isochronous data streams. Simulation results are presented to illustrate the access and queuing delays under various load conditions and traffic mixes.

Dynamic load balancing strategies for minimizing the execution time of single applications running in parallel on multicomputer systems are discussed. Dynamic load balancing (DLB) is essential for the efficient use of highly parallel systems when solving non-uniform problems with unpredictable load estimates. With the evolution of more highly parallel systems, centralized DLB approaches which make use of a high degree of knowledge become less feasible due to the load balancing communication overhead. Five DLB strategies are presented which illustrate the tradeoff between 1) knowledge - the accuracy of each balancing decision, and 2) overhead - the amount of added processing and communication incurred by the balancing process. All five strategies have been implemented on an Inter iPSC/2 hypercube.>

Three transport services are offered by FDDI: asynchronous, synchronous, and isochronous (FDDI-II). In order to support the stringent multimedia (e.g., real-time video and voice) delay and bandwidth requirements the asynchronous transfer service will not suffice. The isochronous and synchronous transport services differ considerably in their implementation, but the differences in the service provided can be made to appear transparent to many multimedia applications. It is shown that synchronous traffic can support a wide range of application requirements efficiently at moderate cost when the connection between source and destination are on the same physical ring. However, isochronous class traffic has advantages, particularly when the network traffic is well behaved (the peak data rate is close to the mean data rate) and when connections traverse multiple rings.>

A mechanism is required which prevents the initiation of the claim process and maintains a constant ring latency during the insertion and removal of stations into the ring. Such a mechanism, graceful insertion and removal, is described. The mechanism is designed to support the graceful insertion and removal of stations into the M-ports of concentrators and requires no hardware modification of the endstations.>

The advantages and disadvantages of isochronous and synchronous transport services of the fiber distributed data interface (FDDI) are summarized. A comparison of both services is made based on application requirements (e.g. real-time video and voice). These requirements include timing constraints, such as jitter and delay, bandwidth utilization, and end-station requirements. It is shown that synchronous traffic can support a wide range of application requirements efficiently at moderate cost when the connections between source and destination are on the same physical ring. However, isochronous traffic has advantages, particularly when the network traffic is well behaved (the peak data rate is close to the mean data rate) and when connections traverse multiple rings.>

The effects of station insertion and removal from concentrators attached to the dual ring in FDDI networks are examined. The frame-loss caused by the insertion and removal of stations is compared to the frame-loss caused by the ring bit error rate (BER). This is found to be significant for most FDDI networks. Algorithms for 'graceful' insertion and removal are proposed to minimize the impact of these actions on the network performance. The effect on the network bandwidth of the proposed solutions is compared to the effect of normal insertion and removal. Overall, the merits of graceful insertion and removal are found to be marginally significant.>

Various FDDI network configurations are characterized and their availabilities evaluated. From these results it is concluded that an FDDI network backbone should be interconnected using dual attachment concentrators. This is essential for guaranteeing high availability. Furthermore, dual-homing configurations are required to maintain high availability of the path between end-stations and the backbone. For less stringent availability requirements, single attachment concentrator trees with single attachment stations may suffice. A cost analysis of the configurations is also included.>

Nonuniform problems are characterized by a behavior that is data dependent and cannot be determined at compile time. Currently, no formal methods for implementation or evaluation exist for this class of algorithms. This paper presents an implementation of the region growing problem, which is representative of one class of nonuniform problems, on a highly parallel SIMD computer. The region growing paradigm for image segmentation groups neighboring pixels into regions depending upon a predetermined homogeneity criteria. Our algorithm is based upon a parallel merging paradigm, which involves the selection of the best of all merge possibilities for all regions concurrently. A key requirement of any parallel region growing scheme is the ability to concurrently compute functions on irregular shaped regions. A set of general primitive functions for region growing is defined and techniques for implementing these functions on an SIMD processor are developed. These techniques make use of an embedded tree data structure to represent regions. The results of implementing a parallel split-and-merge region growing algorithm on the Massively Parallel Processor are discussed. A comparison is made to an MIMD implementation of the algorithm on the Intel iPSC/2 hypercube. The SIMD approach is shown to be efficient primarily for images involving large numbers of regions.