VOIP动态缓出时延算法研究分析

在以包为单位进行数据传输合、语音应用程序(VOIP,Voice Over Internet Protocol)中,为了补偿数据包在网络传输中不可预知的网络传输延迟,在接收端首先必须把接收到的数据包缓存起来,缓存一定的时间再播放出来,以减少通话的抖动,得到比较满意的通话质量。文章主要研究动态缓出时延算法,力求使这个缓出时延尽可能小,同时尽可能减少包的丢失率。文章提出了一个有效动态缓出时延算法,该算法主要跟踪最近到达的数据包的网络传输时延求出其近似分布函数,并利用这些信息和延迟峰的侦测算法预测下一个语音峰的缓出时延。实验结果表明利用该算法可以在缓出时延和包丢失率之间达到最佳平衡,是一种理想、有效的算法。     

Dynamic playout scheduling algorithms for continuous multimedia streams

In this paper, we investigate a playout scheduling framework for supporting the continuous and synchronized presentations of multimedia streams in a distributed multimedia presentation system. We assume a situation in which the server and network transmissions provide sufficient support for the delivery of media objects. In this context, major issues regarding the enforcement of the smooth presentation of multimedia streams at client sites must be addressed to deal with rate variance of stream presentations and delay variance of networks. We develop various playout-scheduling algorithms that are adaptable to quality-of-service parameters. The proposed algorithms permit the local adjustment of unsynchronized presentations by gradually accelerating or retarding presentation components, rather than abruptly skipping or pausing the presentation materials. A comprehensive experimental analysis of the proposed algorithms demonstrates that our algorithms can effectively avoid playout gaps (or hiccups) in the presentations. This scheduling framework can be readily used to support customized multimedia presentations.     

Synchronized delivery and playout of distributed stored multimedia streams

Multimedia streams such as audio and video impose tight temporal constraints for their presentation. Often, related multimedia streams, such as audio and video, must be presented in a synchronized way. We introduce a novel scheme to ensure the continuous and synchronous delivery of distributed stored multimedia streams across a communications network. We propose a new protocol for synchronized playback and compute the buffer required to achieve both, the continuity within a single substream and the synchronization between related substreams. The scheme is very general and does not require synchronized clocks. Using a resynchronization protocol based on buffer level control, the scheme is able to cope with server drop-outs and clock drift. The synchronization scheme has been implemented and the paper concludes with our experimental results.     

Traffic characterization algorithms for VBR video in multimedia networks

A network that offers deterministic, i.e., worst case, quality-of-service guarantees to variable-bit-rate (VBR) video must provide a resource reservation mechanism that allocates bandwidth, buffer space, and other resources for each video stream. Such a resource reservation scheme must be carefully designed, otherwise network resources are wasted. A key component for the design of a resource reservation scheme is the traffic characterization method that specifies the traffic arrivals on a video stream. The traffic characterization should accurately describe the actual arrivals, so that a large number of streams can be supported; but it must also map directly into efficient traffic-policing mechanisms that monitor arrivals on each stream. In this study, we present a fast and accurate traffic characterization method for stored VBR video in networks with a deterministic service. We use this approximation to obtain a traffic characterization that can be efficiently policed by a small number of leaky buckets. We present a case study where we apply our characterization method to networks that employ a dynamic resource reservation scheme with renegotiation. We use traces from a set of 25–30-min MPEG sequences to evaluate our method against other characterization schemes from the literature.     

Evaluating the performance of table processing algorithms

While techniques for evaluating the performance of lower-level document analysis tasks such as optical character recognition have gained acceptance in the literature, attempts to formalize the problem for higher-level algorithms, while receiving a fair amount of attention in terms of theory, have generally been less successful in practice, perhaps owing to their complexity. In this paper, we introduce intuitive, easy-to-implement evaluation schemes for the related problems of table detection and table structure recognition. We also present the results of several small experiments, demonstrating how well the methodologies work and the useful sorts of feedback they provide. We first consider the table detection problem. Here algorithms can yield various classes of errors, including non-table regions improperly labeled as tables (insertion errors), tables missed completely (deletion errors), larger tables broken into a number of smaller ones (splitting errors), and groups of smaller tables combined to form larger ones (merging errors). This leads naturally to the use of an edit distance approach for assessing the results of table detection. Next we address the problem of evaluating table structure recognition. Our model is based on a directed acyclic attribute graph, or table DAG. We describe a new paradigm, “graph probing,” for comparing the results returned by the recognition system and the representation created during ground-truthing. Probing is in fact a general concept that could be applied to other document recognition tasks as well. Received July 18, 2000 / Accepted October 4, 2001     

Failure recovery algorithms for multimedia servers

In this paper, we present two novel disk failure recovery methods that utilize the inherent characteristics of video streams for efficient recovery. Whereas the first method exploits the inherent redundancy in video streams (rather than error-correcting codes) to approximately reconstruct data stored on failed disks, the second method exploits the sequentiality of video playback to reduce the overhead of online failure recovery in conventional RAID arrays. For the former approach, we present loss-resilient versions of JPEG and MPEG compression algorithms. We present an inherently redundant array of disks (IRAD) architecture that combines these loss-resilient compression algorithms with techniques for efficient placement of video streams on disk arrays to ensure that on-the-fly recovery does not impose any additional load on the array. Together, they enhance the scalability of multimedia servers by (1) integrating the recovery process with the decompression of video streams, and thereby distributing the reconstruction process across the clients; and (2) supporting graceful degradation in the quality of recovered images with increase in the number of disk failures. We present analytical and experimental results to show that both schemes significantly reduce the failure recovery overhead in a multimedia server.     

A protocol for performance evaluation of line detection algorithms

Accurate and efficient vectorization of line drawings is essential for any higher level processing in document analysis and recognition systems. In spite of the prevalence of vectorization and line detection methods, no standard for their performance evaluation protocol exists. We propose a protocol for evaluating both straight and circular line extraction to help compare, select, improve, and even design line detection algorithms to be incorporated into line drawing recognition and understanding systems. The protocol involves both positive and negative sets of indices, at pixel and vector levels. Time efficiency is also included in the protocol. The protocol may be extended to handle lines of any shape as well as other classes of graphic objects.     

Real-time spatial processing of sounds for music, multimedia and interactive human-computer interfaces

This paper gives an overview of the principles and methods for synthesizing complex 3D sound scenes by processing multiple individual source signals. Signal-processing techniques for directional sound encoding and rendering over loudspeakers or headphones are reviewed, as well as algorithms and interface models for synthesizing and dynamically controling room reverberation and distance effects. A real-time modular spatial-sound-processing software system, called Spat, is presented. It allows reproducing and controling the localization of sound sources in three dimensions and the reverberation of sounds in an existing or virtual space. A particular aim of the Spatialisateur project is to provide direct and computationally efficient control over perceptually relevant parameters describing the interaction of each sound source with the virtual space, irrespective of the chosen reproduction format over loudspeakers or headphones. The advantages of this approach are illustrated in practical contexts, including professional audio, computer music, multimodal immersive simulation systems, and architectural acoustics.     

Efficient admission control algorithms for multimedia servers

In this paper, we have proposed efficient admission control algorithms for multimedia storage servers that are providers of variable-bit-rate media streams. The proposed schemes are based on a slicing technique and use aggressive methods for admission control. We have developed two types of admission control schemes: Future-Max (FM) and Interval Estimation (IE). The FM algorithm uses the maximum bandwidth requirement of the future to estimate the bandwidth requirement. The IE algorithm defines a class of admission control schemes that use a combination of the maximum and average bandwidths within each interval to estimate the bandwidth requirement of the interval. The performance evaluations done through simulations show that the server utilization is improved by using the FM and IE algorithms. Furthermore, the quality of service is also improved by using the FM and IE algorithms. Several results depicting the trade-off between the implementation complexity, the desired accuracy, the number of accepted requests, and the quality of service are presented.     

Distance-based outliers: algorithms and applications

This paper deals with finding outliers (exceptions) in large, multidimensional datasets. The identification of outliers can lead to the discovery of truly unexpected knowledge in areas such as electronic commerce, credit card fraud, and even the analysis of performance statistics of professional athletes. Existing methods that we have seen for finding outliers can only deal efficiently with two dimensions/attributes of a dataset. In this paper, we study the notion of DB (distance-based) outliers. Specifically, we show that (i) outlier detection can be done efficiently for large datasets, and for k-dimensional datasets with large values of k (e.g., ); and (ii), outlier detection is a meaningful and important knowledge discovery task. First, we present two simple algorithms, both having a complexity of , k being the dimensionality and N being the number of objects in the dataset. These algorithms readily support datasets with many more than two attributes. Second, we present an optimized cell-based algorithm that has a complexity that is linear with respect to N, but exponential with respect to k. We provide experimental results indicating that this algorithm significantly outperforms the two simple algorithms for . Third, for datasets that are mainly disk-resident, we present another version of the cell-based algorithm that guarantees at most three passes over a dataset. Again, experimental results show that this algorithm is by far the best for . Finally, we discuss our work on three real-life applications, including one on spatio-temporal data (e.g., a video surveillance application), in order to confirm the relevance and broad applicability of DB outliers. Received February 15, 1999 / Accepted August 1, 1999     

Some simple distributed algorithms for sparse networks

Summary. We give simple, deterministic, distributed algorithms for computing maximal matchings, maximal independent sets and colourings. We show that edge colourings with at most colours, and maximal matchings can be computed within deterministic rounds, where is the maximum degree of the network. We also show how to find maximal independent sets and -vertex colourings within deterministic rounds. All hidden constants are very small and the algorithms are very simple. Received: August 2000 / Accepted: November 2000     

Checking the temporal integrity of interactive multimedia documents

Abstract. When authoring multimedia scenarios, and in particular scenarios with user interaction, where the sequence and time of occurrence of interactions is not predefined, it is difficult to guarantee the consistency of the resulting scenarios. As a consequence, the execution of the scenario may result in unexpected behavior or inconsistent use of media. The present paper proposes a methodology for checking the temporal integrity of interactive multimedia document (IMD) scenarios at authoring time at various levels. The IMD flow is mainly defined by the events occurring during the IMD session. Integrity checking consists of a set of discrete steps, during which we transform the scenario into temporal constraint networks representing the constraints linking the different possible events in the scenario. Temporal constraint verification techniques are applied to verify the integrity of the scenario, deriving a minimal network, showing possible temporal relationships between events given a set of constraints. Received June 9, 1998 / Accepted November 10, 1999     

Accuracy bounds and optimal computation of robot localization

We present an optimal method for estimating the current location of a mobile robot by matching an image of the scene taken by the robot with a model of the known environment. We first derive a theoretical accuracy bound and then give a computational scheme that can attain that bound, which can be viewed as describing the probability distribution of the current location. Using real images, we demonstrate that our method is superior to the naive least-squares method. We also confirm the theoretical predictions of our theory by applying the bootstrap procedure. Received: 17 March 1998 / Accepted: 7 April 2001     

Improving multimedia systems performance using constant-density recording disks

Multimedia systems store and retrieve large amounts of data which require extremely high disk bandwidth and their performance critically depends on the efficiency of disk storage. However, existing magnetic disks are designed for small amounts of data retrievals geared to traditional operations; with speed improvements mainly focused on how to reduce seek time and rotational latency. When the same mechanism is applied to multimedia systems, overheads in disk I/O can result in dramatic deterioration in system performance. In this paper, we present a mathematical model to evaluate the performance of constant-density recording disks, and use this model to analyze quantitatively the performance of multimedia data request streams. We show that high disk throughput may be achieved by suitably adjusting the relevant parameters. In addition to demonstrating quantitatively that constant-density recording disks perform significantly better than traditional disks for multimedia data storage, a novel disk-partitioning scheme which places data according to their bandwidths is presented.     

Multimedia network protocols: where are we?

Protocols for multimedia communication are needed to integrate into a single network services intended to satisfy the different requirements of multiple types of traffic. An essential prerequisite for designing these protocols is that the services to be offered by the network must be selected and specified in detail. We present the service models proposed, or being developed, by the Internet community, by the ATM community, and by the Tenet Group. We compare their common characteristics, which reveal the characteristics of the first integrated services networks are likely to offer. The services referred to in this paper are those at the network and transport layers, which support the services to be offered to the system's end users.     

An algebra for creating and querying multimedia presentations

Over the last few years, there has been a tremendous increase in the number of interactive multimedia presentations prepared by different individuals and organizations. In this paper, we present an algebra for creating and querying interactive multimedia presentation databases. This algebra operates on trees whose branches reflect different possible playouts of a set of presentations. The algebra not only extends all the classical relational operators to such databases, but also introduces a variety of novel operators for combining multiple presentations. As our algebra supports merging parts or all of existing presentations, this algebra can also be used as an authoring tool for creating multimedia presentations. We prove a host of equivalence results for queries in this algebra, which may be used to build query optimizers for interactive presentation databases.     

The optimal location of replicas in a network using a READ-ONE-WRITE-ALL policy

We consider the problem of locating replicas in a network to minimize communications costs. Under the assumption that the read-one-write-all policy is used to ensure data consistency, an optimization problem is formulated in which the cost function estimates the total communications costs. The paper concentrates on the study of the optimal communications cost as a function of the ratio between the frequency of the read and write operations. The problem is reformulated as a zero-one linear programming problem, and its connection to the p-median problem is explained. The general problem is proved to be NP-complete. For path graphs a dynamic programming algorithm for the problem is presented. Received: May 1993 / Accepted: June 2001     

Packet video transport in ATM networks with single-bit feedback

The promise of a broadband integrated service digital network has led to the design of mechanisms for efficient transport of real-time compressed video in packet switching networks. We examine feedback control for video transport in ATM networks where the available feedback is a single bit of information carried in the cell header. We investigate the performance of three single-bit schemes for source rate adaptation. Two were originally for congestion control of bursty data traffic and are modified to control video traffic. The third scheme conveys more information about the state of queue(s) at the bottleneck. The simulation results show that all three schemes for feedback control of VBR video streams work remarkably well. During severe network congestion, the signal quality degrades gracefully, but not uniformly across all connections. Based on insights from the initial simulations, we propose a scheme to improve the fairness of service and demonstrate its effectiveness.