A group of switch schedulers make packet scheduling decisions based on predefined bandwidth allocation for each flow. Allocating bandwidth for best effort flows is challenging due to lack of allocation criteria and fairness principles. In this paper, we propose sequential and parallel algorithms to allocate bandwidth for best effort flows in a switch, to achieve fairness and efficiency. The proposed algorithms use the queue length proportional allocation criterion, which allocates bandwidth to a best effort flow proportional to its queue length, giving more bandwidth to congested flows. In addition, the algorithms adopt the max-min fairness principle, which maximizes bandwidth utilization and maintains fairness among flows. We first formulate the problem based on the allocation criterion and fairness principle. Then, we present a sequential algorithm and prove that it achieves max-min fairness. To accelerate the allocation process, we propose a parallel version of the algorithm, which allows different input ports and output ports to conduct calculation in parallel, resulting in fast convergence. Finally, we present simulation data to demonstrate that the parallel algorithm is effective in reducing the convergence iterations.

Application-layer overlay networks are receiving considerable popularity due to its flexibility and readily deployable nature thereby providing support for a plethora of Peer-to-Peer (P2P) applications. Currently, the real-world deployment of Internet-scale P2P media streaming systems involve the usage of tracker server for content discovery in on-demand model with asynchronous interactivity. The inherent drawbacks of tracker-server based approach are obvious due to scalability and bottleneck issues, which prompted us to pursue a structured P2P based proposition such as Distributed Hash Tables (DHT) which are already proved to be stable substrates. The challenging issue of accommodating a large number of update operations with the continuous change of user's playing position in DHT-based overlay is addressed in our previous work by the concept of Temporal-DHT which exploits the temporal dynamics of the content to estimate playing position. In this paper, we incorporate the notion of popularity awareness in the Temporal-DHT framework which will help to adapt the query resolution mechanism by addressing the skew ness of content popularity typically found in real multimedia user access patterns. The essential objective of popularity awareness mechanism is to increase the overall performance of Temporal-DHT by optimizing the search cost among the entire content set within the system. We formulate the problem and provide practical solutions with extensive simulation results that demonstrates the effectiveness of popularity-aware Temporal-DHT by achieving optimized query resolution cost and high streaming quality for on-demand systems in a dynamic network environment where user's are free to asynchronously join/leave the system.

The voice communication industry is undergoing a rapid phase change with continuously evolving technologies such as cellular, mobile and Internet telephony. Effective evaluation of system performance is becoming critical, which will serve as an important instrument for service providers to monitor and manage quality. Recently, Quality of Experience (QoE) metrics are found to be more valuable quality assessment mechanism since they are more closely related to human perception as compared to traditional QoS-based techniques. In this paper, we investigate a new affect-based approach for QoE evaluation. Our hypothesis states that QoE in voice communication is correlated to user's affective behavior, which will vary across networking conditions. We conduct extensive user study based on natural human-human voice communication. The experimental results indicate very promising prospect of this approach.

Various distributed multi-source applications such as 3D Virtual Immersive Systems (3DVIS), 2D/3D Videoconferencing, Multi-party games, etc. require the construction of a multicast overlay through which the video blocks are streamed from source to receiver. The most general multicast model involves a single source and a set of receiver nodes also known as multicast set with a single stream to each receiver. In this paper, we are interested to investigate a different multicast model consisting of multiple sources and receivers which is quite common in 3DVIS/video conferencing applications where each node serves both as a source and a receiver. The problem of constructing a multicast overlay for multi-source is hard and we are interested to guarantee certain QoS constraints such as end-to-end latency and latency variations. Latency variation constraints are very important in collaborative applications for maintaining realtime interactivity and multi-stream synchronization. We present an efficient heuristic solution for the muti-source multicast construction problem with an economical time-complexity.

Buffered crossbar switches are special crossbar switches with an exclusive buffer at each crosspoint. They demonstrate unique advantages over traditional unbuffered crossbar switches, such as asynchronous scheduling and variable length packet handling. However, since crosspoint buffers are expensive on-chip memories, it is desired that each crosspoint has only a small buffer. In this paper, we propose a scheduling algorithm called Fair Asynchronous Segment Scheduling (FASS) for buffered crossbar switches, which reduces the crosspoint buffer size by dividing packets into shorter segments before transmission. FASS also provides tight constant performance guarantees by emulating the ideal Generalized Processor Sharing (GPS) model. Furthermore, FASS requires no speedup for the crossbar, lowering the hardware cost and improving the switch capacity. By theoretical analysis, we prove that FASS is strongly stable and therefore achieves 100% throughput. We also calculate the size bound for the crosspoint buffers. Moreover, we show that FASS provides bounded delay guarantees. Finally, we present simulation data to verify the analytical results.

A parallel packet switch (PPS) provides huge aggregate bandwidth by combining the capacities of multiple switching fabrics. Most existing PPSs use output queued switches as the switching fabrics, which require speedup and result in high implementation cost. In this paper, we present a buffered crossbar based parallel packet switch (BCB- PPS), whose switching fabrics need no speedup. We propose the Batch-WF2Q algorithm to dispatch packets to the parallel switching fabrics, and leverage the sMUX algorithm in to schedule packet transmission for the switching fabrics. Such a design enables a simple round-robin algorithm to efficiently collect packets from the switching fabrics. In addition, our design requires no packet resequencing, and thus needs no buffers at either external or internal outputs. We show that BCB-PPS has tight delay guarantees and bounded buffer sizes. Finally, we present simulation data to verify the analytical results and to evaluate the performance of our design.

Peer-to-Peer (P2P) based Video-on-Demand (VoD) streaming services are gaining popularity. Meanwhile, the technical barriers of P2P-VoD systems still exist because of asynchronous and dynamic user interactivity where any user can jump to random locations in the video stream along with the support for Fast-Forward/Fast-Backward operations. An important component to address these issues lies in efficient neighbor discovery mechanism for searching and receiving desired data in a peer-to-peer fashion with less burden of the server. We advocate a Distributed Hash Table (DHT) based overlay for efficient lookup with its desirable features of provable scalability, robustness and decentralization for supporting Internet-scale P2P applications. However, one big challenge associated with a DHT-based overlay is how to accommodate a large number of update operations with the continuous change of peers' playing position. To solve this inadequacy, we propose a novel concept of temporal-DHT which exploits the temporal dynamics of the content to estimate the playing position of peers, thereby greatly reducing the update overhead. We also propose a new content management and discovery scheme by the skillful integration of: (1) random/out-of-order/static caching to support interactive operations and (2) playing/in-order/dynamic caching to maintain streaming efficiency and playback continuity. Extensive simulation results demonstrate that our mechanism achieves low messaging overhead with high streaming quality for P2P-VoD systems in a dynamic environment where peers asynchronously join/leave the network.

Three-dimensional tele-immersive (3DTI) environments have great potential to promote collaborative work among geographically distributed users. However, most existing 3DTI systems only work with two sites due to the huge demand of resources and the lack of a simple yet powerful networking model to handle connectivity, scalability, and quality-of-service (QoS) guarantees. In this article, we explore the design space from the angle of multi-stream management to enable multi-party 3DTI communication. Multiple correlated 3D video streams are employed to provide a comprehensive representation of the physical scene in each 3DTI environment, and are rendered together to establish a common cyberspace among all participating 3DTI environments. The existence of multi-stream correlation provides the unique opportunity for new approaches in QoS provisioning. Previous work mostly concentrated on compression and adaptation techniques on the per-stream basis while ignoring the application layer semantics and the coordination required among streams. We propose an innovative and generalized ViewCast model to coordinate the multi-stream content dissemination over an overlay network. ViewCast leverages view semantics in 3D free-viewpoint video systems to fill the gap between high-level user interest and low-level stream management. In ViewCast, only the view information is specified by the user/application, while the underlying control dynamically performs stream differentiation, selection, coordination, and dissemination. We present the details of ViewCast and evaluate it through both simulation and 3DTI sessions among tele-immersive environments residing in different institutes across the Internet2. Our experimental results demonstrate the implementation feasibility and performance enhancement of ViewCast in supporting multi-party 3DTI collaboration.

Three-dimensional tele-immersive (3DTI) environments have great potential to promote collaborative work among geographically distributed users. However, most existing 3DTI systems only work with two sites due to the huge demand of resources and the lack of a simple yet powerful networking model to handle connectivity, scalability, and quality-of-service (QoS) guarantees.

Distributed Multi-party/Multi-stream systems require a multicast subnetwork capable of satisfying QoS constraints such as delay and delay variation bound so that the messages reach each destination node at almost the same time within a certain specified time limit. In addition, certain multi-stream systems also demand that different streams for each different destination node should reach with minimum delay variation. So, we propose the problem of minimizing both inter-destination and intra-destination delay variation along with the maximum delay bound and present efficient heuristic solution that achieves the tightest possible combined bound. This problem is NP-complete as shown in the literature. Computer simulation results approve that our heuristic is efficient with a low running time and the tightest combined delay variation.

The past decades have witnessed a rapid growth of Distributed Interactive Multimedia Environments (DIMEs). Despite their intensity of user-involved interaction, the existing evaluation frameworks remain very much system-centric. As a step toward the human-centric paradigm, we present a conceptual framework of Quality of Experience (QoE) in DIMEs, to model, measure, and understand user experience and its relationship with the traditional Quality of Service (QoS) metrics. A multi-displinary approach is taken to build up the framework based on the theoretical results from various fields including psychology, cognitive sciences, sociology, and information technology. We introduce a mapping methodology to quantify the correlations between QoS and QoE, and describe our controlled and uncontrolled studies as illustrating examples. The results present the first deep study to model the multi-facet QoE construct, map the QoS-QoE relationship, and capture the human-centric quality modalities in the context of DIMEs.

Multi-stream/multi-site 3D video collaborative systems are promising as they enable remote users to interact in a 3D virtual space with a sense of co-presence. However, the decentralized content dissemination remains a challenge. In this work, we explore approaches to construct adaptive overlay based on the users' visual interest in the collaborative space. Particularly, we consider the practical challenge that the user's interest might change dynamically. We propose, compare, and evaluate three algorithms to handle the view dynamics. With extensive experiments, we demonstrate that an algorithm that exploits view locality can achieve efficient bandwidth utilization, high topology stability, and great scalability.

3D tele-immersion (3DTI) has recently emerged as a new way of video-mediated collaboration across the Internet. Unlike conventional 2D video-conferencing systems, it can immerse remote users into a shared 3D virtual space so that they can interact or collaborate "virtually". However, most existing 3DTI systems can support only two sites of collaboration, due to the huge demand of networking resources and the lack of a simple yet efficient data dissemination model. In this paper, we propose to use a general publish-subscribe model for multi-site 3DTI systems, which efficiently utilizes limited network resources by leveraging user interest. We focus on the overlay construction problem in the publish-subscribe model by exploring a spectrum of heuristic algorithms for data dissemination. With extensive simulation, we identify the advantages of a simple randomized algorithm. We present optimization to further improve the randomized algorithm by exploiting semantic correlation. Experimental results demonstrate that we can achieve an improvement by a factor of five.

We present our implementation and evaluation of TEEVE, a distributed 3D tele-immersive system. TEEVE is among the first to support multi-stream/multi-site 3D tele-immersive environments with commercial off-the-shelf hardware and software infrastructures. It promotes collaborative physical activities among geographically dispersed sites by immersing the 3D representations of remote participants into a joint 3D virtual space. In this paper, we describe our implementation of TEEVE and introduce the recent advances in its different system components. In particular, we present an implemented protocol for semantic-aware data dissemination to support multi-site remote collaboration. We evaluate the TEEVE system by deploying it on the Internet. The experimental results demonstrate that it achieves stable visual quality, soft real-time delay, and efficient resource usage.

The Tele-immersive Dance Environment (TED) is a geographically distributed, real-time 3-D virtual room where multiple participants interact independent of physical distance. TED, a highly interactive collaborative environment, offers digital options with multiple viewpoints, enhancing the creative movement composition involved with dance choreography. A symbiotic relationship for creativity and design exists between dance artists and computer scientists as the tele-immersive environment is analyzed as a creativity and learning tool. We introduce the advancements of the interactive digital options, new interface developments, user study results, and the possibility of a computational model for human creativity through Laban Movement Analysis.

We demonstrate the Tele-immersive Dance Environment (TED), a geographically distributed, real-time 3-D virtual room where multiple participants interact independent of physical distance. TED, a highly interactive collaborative environment, offers digital options with multiple viewpoints, enhancing the creative movement composition involved with dance choreography. We present the advancements of the interactive digital options, new interface developments, and user study results.

The study of 3D Tele-immersion impact on remote collaborative work represents a very interesting and challenging research topic. In this paper, we introduce the latest accomplishments of TEEVE research which merges computer science with dance choreography. This collaborative research model is ideal for creative, interdisciplinary problem solving. TEEVE offers an entirely new interface for dance choreography as a creative tool and alternative performance venue.

Tele-immersion is emerging as a new medium that creates 3D photorealistic, immersive, and interactive experience between geographically dispersed users. However, most existing tele-immersive systems can only support two-way collaboration. In this paper we propose a multi-layer framework and a new data dissemination protocol to support multi-site collaboration. The problem context is unique as multiple remote sites participate in an interactive tele-immersive session, where each site has multiple correlated 3D video streams to send (later referred as multi-stream/multi-site environments). The key challenge is to disseminate such large number of 3D live video streams among these sites subject to the bandwidth and latency constraints while satisfying QoS guarantees in visual quality. Among our findings is that the simple randomized algorithm outperforms many other static algorithms in the unique context. Moreover, the streams generated from one site have high semantic correlation, because often cameras at one site are shooting the same scene, only from different angles. We exploit the stream correlation in the multicast protocol to minimize the level of loss.

Real-time distributed multi-party/multi-stream systems are becoming more popular in many areas such as 3D tele-immersion, multi-camera conferencing and security surveillance. However, the construction of such systems in large scale is impeded by the huge demand of computing and networking resources and the lack of a simple yet powerful networking model to handle interconnection, scalability and quality of service (QoS) guarantees. We make two main contributions in the paper: (1) we propose a novel generalized ViewCast model for multi-party/multi-stream video-mediated systems that fills the gap between high-level user interest and low level per-stream management, and (2) we demonstrate the ViewCast model by applying it to the multi-party 3D Tele-Immersive (3DTI) collaboration among geographically dispersed users. More specifically, we show how the ViewCast model is used in supporting stream data dissemination, coordination and QoS management among multiple 3D tele-immersive environments. We present our experimental results in both real implementation and simulation to show that our ViewCast-based solution achieves high efficiency, scalability, and quality in supporting multi-party 3DTI collaboration.

We first present the tele-immersive environments developed jointly by University of Illinois at Urbana-Champaign and University of California at Berkeley. The environment features 3D full and real body capturing, wide field of view, multi-display 3D rendering, and attachment free participant. We then describe a study of collaborative dancing between remotely located dancers in the shared virtual space. Two professional dancers are invited to the tele-immersive site of each university. As a preliminary experiment, we let the dancers perform elementary body movements and coordinate their dancing. The coordination requires one dancer to take the lead while the other follows her by appropriate movements. During the experiment, the dancers are dancing at various motion rates to evaluate how well the collaborative dancing is supported with the current technical boundary. Our important findings indicate that 1) tele-immersive environments have strong potential impact on the concept of choreography and communication of live dance performance, 2) the presence of multi-display system, real body 3D rendering, audio channel, and less intrusive-ness greatly enhances the immersive and dancing experience, and 3) the level of synchronization achieved by the dancers is higher than that expected from the video rate

We present a study of collaborative dancing between remote dancers in a tele-immersive environment which features 3D full and real body capturing, wide field of view, multi-display 3D rendering, and attachment free participant. We invite two professional dancers to perform collaborative dancing in the environment. The coordination requires one dancer to take the lead while the other follows by appropriate movement. Throughout the experiment, the dancers are dancing at various motion rates to evaluate how well the collaborative dancing is supported with the current technical boundary. Our important findings indicate that 1) tele-immersive environments have strong potential impact on the concept of choreography and communication of live dance performance, 2) the presence of multi-view display, real body 3D rendering, audio channel, and less intrusiveness greatly enhances the immersive and dancing experience, and 3) the level of synchronization achieved by the dancers is higher than that expected from the video rate.

Tele-immersive environments will improve the state of collaboration among distributed participants. However, along with the promise a new set of challenges have emerged including the real-time acquisition, streaming and rendering of 3D scenes to convey a realistic sense of immersive spaces. Unlike 2D video conferencing, a 3D tele-immersive environment employs multiple 3D cameras to cover a much wider field of view, thus generating a very large volume of data that need to be carefully coordinated, organized, and synchronized for Internet transmission, rendering and display. This is a challenging task and a dynamic bandwidth management must be in place. To achieve this goal, we propose a multi-stream adaptation framework for bandwidth management in 3D tele-immersion. The adaptation framework relies on the hierarchy of mechanisms and services that exploits the semantic link of multiple 3D video streams in the tele-immersive environment. We implement a prototype of the framework that integrates semantic stream selection, content adaptation, and 3D data compression services with user preference. The experimental results have demonstrated that the framework shows a good quality of the resulting composite 3D rendered video in case of sufficient bandwidth, while it adapts individual 3D video streams in a coordinated and user-friendly fashion, and yields graceful quality degradation in case of low bandwidth availability.

Tele-immersive 3D multi-camera room environments are starting to emerge and with them new challenging research questions. One important question is how to organize the large amount of visual data, being captured, processed, transmitted and displayed, and their corresponding resources, over current COTS computing and networking infrastructures so that "everybody" would be able to install and use tele-immersive environments for conferencing and other activities. In this paper, we propose a novel cross-layer control and streaming framework over general purpose delivery infrastructure, called TEEVE (tele-immersive environments for everybody). TEEVE aims for effective and adaptive coordination, synchronization, and soft QoS-enabled delivery of tele-immersive visual streams to remote room(s). The TEEVE experiments between two tele-immersive rooms residing in different institutions more than 2000 miles apart show that we can sustain communication of up to 12 3D video streams with 4/spl sim/5 3D frames per second for each stream, yielding 4/spl sim/5 tele-immersive video rate.

Multihop wireless hotspot network [A. Balachandran et al., (2003), F. Fitzek et al., (2003), Y-D. Lin et al., (1999), K-C. Wang et al., (2003)] has been recently proposed to extend the coverage area of a base station. However, with selfish nodes in the network, multihop packet forwarding cannot take place without an incentive mechanism. In this paper, we adopt the "pay for service" incentive model, i.e., clients pay the relaying nodes for their packet forwarding service. Our focus in this paper is to determine a "fair" pricing for packet forwarding. To this end, we model the system as a market where the pricing for packet forwarding is determined by demand and supply. Depending on the network communication scenario, the market models are different. We classify the network into four different scenarios and propose different pricing mechanisms for them. Our simulation results show that the pricing mechanisms are able to guide the market into an equilibrium state quickly. We also show that maintaining communication among the relaying nodes is important for a stable market pricing.

Wireless 2D cameras are becoming more widely used for applications such as video surveillance and conferencing due to their easy deployment. These scenarios require multiple high quality video streams that share limited wireless channel resource. Therefore, a bandwidth management that is sensitive to application QoS requirements, content extraction and the specifics of a camera array environment is essential. This paper addresses the problem of bandwidth management to coordinate multiple video flows and to support streaming from wireless camera array. We present a bandwidth management framework that deploys a coordination scheme between the camera array and system resources. Especially, the framework explores different relations and scheduling policies between cameras and the bandwidth allocation to achieve better multi-view video delivery. The implementation uses Linux platform and IEEE 802.11b wireless ad hoc network. Our experimental results show that the bandwidth management framework helps achieving streaming differentiation while maintaining high quality video delivery.