Fundamental tradeoffs in distributed algorithms for rate adaptive multimedia streams

Rate adaptive multimedia streams adjust the encoding rate dynamically (with corresponding changes in media content resolution) in response to changing levels of congestion along the route. The field of optimization based congestion control has yielded sophisticated distributed algorithms for resource allocation among competing elastic streams. In this work we study the fundamental tradeoffs for a class of optimization based distributed algorithms for rate adaptive streams. We focus on three tradeoffs: (i) the tradeoff between maximizing client average quality of service (QoS) and client fairness, (ii) the tradeoff between granularity of control (both temporal and spatial) and QoS, and (iii) the tradeoff between maximizing the received volume and minimizing the fluctuations in received rate. We illustrate these tradeoffs through extensive ns-2 simulations on two distinct topologies – (i) a single bottleneck like and (ii) a linear network.     

QoS-Aware Shared Component Composition for Distributed Stream Processing Systems

Many emerging online data analysis applications require applying continuous query operations such as correlation, aggregation, and filtering to data streams in real time. Distributed stream processing systems allow in-network stream processing to achieve better scalability and quality-of-service (QoS) provision. In this paper, we present Synergy, a novel distributed stream processing middleware that provides automatic sharing-aware component composition capability. Synergy enables efficient reuse of both result streams and processing components, while composing distributed stream processing applications with QoS demands. It provides a set of fully distributed algorithms to discover and evaluate the reusability of available result streams and processing components when instantiating new stream applications. Specifically, Synergy performs QoS impact projection to examine whether the shared processing can cause QoS violations on currently running applications. The QoS impact projection algorithm can handle different types of streams including both regular traffic and bursty traffic. If no existing processing components can be reused, Synergy dynamically deploys new components at strategic locations to satisfy new application requests. We have implemented a prototype of the Synergy middleware and evaluated its performance on both PlanetLab and simulation testbeds. The experimental results show that Synergy can achieve much better resource utilization and QoS provisioning than previously proposed schemes, by judiciously sharing streams and components during application composition.     

Sublinear Fully Distributed Partition with Applications

We present new efficient deterministic and randomized distributed algorithms for decomposing a graph with n nodes into a disjoint set of connected clusters with radius at most k−1 and having O(n ^1+1/k ) intercluster edges. We show how to implement our algorithms in the distributed CONGEST\mathcal{CONGEST} model of computation, i.e., limited message size, which improves the time complexity of previous algorithms (Moran and Snir in Theor. Comput. Sci. 243(1–2):217–241, 2000; Awerbuch in J. ACM 32:804–823, 1985; Peleg in Distributed Computing: A Locality-Sensitive Approach, 2000) from O(n) to O(n ^1−1/k ). We apply our algorithms for constructing low stretch graph spanners and network synchronizers in sublinear deterministic time in the CONGEST\mathcal{CONGEST} model.     

Quality of service (QoS) metrics for continuous media

This paper presents quality of service (QoS) metrics for continuity and synchronization specifications in continuous media (CM). Proposed metrics specify continuity and synchronization, with tolerable limits on average and bursty defaults from perfect continuity, timing and synchronization constraints. These metrics can be used in a distributed environment for resource allocation. Continuity specification of a CM stream consists of its sequencing, display rate and drift profiles. The sequencing profile of a CM stream consists of tolerable aggregate and consecutive frame miss ratios. Rate profiles specify the average rendition rate and its variation. Given a rate profile, the ideal time unit for frame display is determined as an offset from the beginning of the stream. Drift profile specifies the average and bursty deviation of schedules for frames from such fixed points in time. Synchronization requirements of a collection of CM streams are specified by mixing, rate and synchronization drift profiles. Mixing profiles specify vectors of frames that can be displayed simultaneously. They consist of average and bursty losses of synchronization. Rate profiles consist of average rates and permissible deviations thereof. Synchronization drift profiles specify permissible aggregate and bursty time drifts between schedules of simultaneously displayable frames. It is shown that rate profiles of a collection of synchronized streams is definable in terms of rate profiles of its component streams. It is also shown that mixing and drift profiles of a collection of streams are non-definable in terms of sequencing and drift profiles of its constituents. An important consequence of the mutual independence of synchronization and continuity specification is that, in a general purpose platform with limited resources, synchronized display of CM streams may require QoS tradeoffs. An algorithm that makes such tradeoffs is presented as a proof of applicability of our metrics in a realistic environment.     

Investigation of the M2/G2/1/∞,N queue with restricted admission of priority customers and its application to HSDPA mobile systems

This paper investigates a queuing system for QoS optimization of multimedia traffic consisting of aggregated streams with diverse QoS requirements transmitted to a mobile terminal over a common downlink shared channel. The queuing system, proposed for buffer management of aggregated single-user traffic in the base station of High-Speed Downlink Packet Access (HSDPA), allows for optimum loss/delay/jitter performance for end-user multimedia traffic with delay-tolerant non-real-time streams and partially loss tolerant real-time streams. In the queuing system, the real-time stream has non-preemptive priority in service but the number of the packets in the system is restricted by a constant. The non-real-time stream has no service priority but is allowed unlimited access to the system. Both types of packets arrive in the stationary Poisson flow. Service times follow general distribution depending on the packet type. Stability condition for the model is derived. Queue length distribution for both types of customers is calculated at arbitrary epochs and service completion epochs. Loss probability for priority packets is computed. Waiting time distribution in terms of Laplace–Stieltjes transform is obtained for both types of packets. Mean waiting time and jitter are computed. Numerical examples presented demonstrate the effectiveness of the queuing system for QoS optimization of buffered end-user multimedia traffic with aggregated real-time and non-real-time streams.     

Message delay and DisCSP search algorithms

Distributed constraint satisfaction problems (DisCSPs) are composed of agents, each holding its own variables, that are connected by constraints to variables of other agents. Due to the distributed nature of the problem, message delay can have unexpected effects on the behavior of distributed search algorithms on DisCSPs. This has been recently shown in experimental studies of asynchronous backtracking algorithms (Bejar et al., Artif. Intell., 161:117–148, 2005; Silaghi and Faltings, Artif. Intell., 161:25–54, 2005). To evaluate the impact of message delay on the run of DisCSP search algorithms, a model for distributed performance measures is presented. The model counts the number of non concurrent constraints checks, to arrive at a solution, as a non concurrent measure of distributed computation. A simpler version measures distributed computation cost by the non-concurrent number of steps of computation. An algorithm for computing these distributed measures of computational effort is described. The realization of the model for measuring performance of distributed search algorithms is a simulator which includes the cost of message delays. Two families of distributed search algorithms on DisCSPs are investigated. Algorithms that run a single search process, and multiple search processes algorithms. The two families of algorithms are described and associated with existing algorithms. The performance of three representative algorithms of these two families is measured on randomly generated instances of DisCSPs with delayed messages. The delay of messages is found to have a strong negative effect on single search process algorithms, whether synchronous or asynchronous. Multi search process algorithms, on the other hand, are affected very lightly by message delay.     

具有优先级特征的多媒体流的资源管理

本文研究了具有优先级特征的分布式多媒体流的资源管理，提出了一种基于节优先级的资源管理的设计方法，包括资源管理机制，资源管理策略，服务质量（ＱｏＳ）协商调整算法和高优先级节枪占算法，它能够保证稳定的具估优先级特征的多媒体流，能够极大地调度并发的多媒体流，特别是在系统资源不足时，能够最大限度地调度高优先级的多媒体流，并能保证各多媒体流量了的ＱｏＳ。     

Impact of video scheduling on bandwidth allocation for multiplexed MPEG streams

We present efficient schemes for scheduling the delivery of variable-bit-rate MPEG-compressed video with stringent quality-of-service (QoS) requirements. Video scheduling is being used to improve bandwidth allocation at a video server that uses statistical multiplexing to aggregate video streams prior to transporting them over a network. A video stream is modeled using a traffic envelope that provides a deterministic time-varying bound on the bit rate. Because of the periodicity in which frame types in an MPEG stream are typically generated, a simple traffic envelope can be constructed using only five parameters. Using the traffic-envelope model, we show that video sources can be statistically multiplexed with an effective bandwidth that is often less than the source peak rate. Bandwidth gain is achieved without sacrificing the stringency of the requested QoS. The effective bandwidth depends on the arrangement of the multiplexed streams, which is a measure of the lag between the GOP periods of various streams. For homogeneous streams, we give an optimal scheduling scheme for video sources at a video-on-demand server that results in the minimum effective bandwidth. For heterogeneous sources, a sub-optimal scheduling scheme is given, which achieves acceptable bandwidth gain. Numerical examples based on traces of MPEG-coded movies are used to demonstrate the effectiveness of our schemes.     

Graph Spanners in the Streaming Model: An Experimental Study

This article reports the results of an extensive experimental analysis of efficient algorithms for computing graph spanners in the data streaming model, where an (α,β)-spanner of a graph G is a subgraph S⊆G such that for each pair of vertices the distance in S is at most α times the distance in G plus β. To the best of our knowledge, this is the first computational study of graph spanner algorithms in a streaming setting. We compare experimentally the randomized algorithms proposed by Baswana () and by Elkin (In: Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP 2007), Wroclaw, Poland, pp. 716–727, 9–13 July 2007) for general stretch factors with the deterministic algorithm presented by Ausiello et al. (In: Proceedings of the 15th Annual European Symposium on Algorithms (ESA 2007), Engineering and Applications Track, Eilat, Israel, 8–10 October 2007. LNCS, vol. 4698, pp. 605–617, 2007), designed for building small stretch spanners. All the algorithms we implemented work in a data streaming model where the input graph is given as a stream of edges in arbitrary order, and all of them need a single pass over the data. Differently from the algorithm in Ausiello et al., the algorithms in Baswana () and Elkin (In: Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP 2007), Wroclaw, Poland, pp. 716–727, 9–13 July 2007) need to know in advance the number of vertices in the graph. The results of our experimental investigation on several input families confirm that all these algorithms are very efficient in practice, finding spanners with stretch and size much smaller than the theoretical bounds and comparable to those obtainable by off-line algorithms. Moreover, our experimental findings confirm that small values of the stretch factor are the case of interest in practice, and that the algorithm by Ausiello et al. tends to produce spanners of better quality than the algorithms by Baswana and Elkin, while still using a comparable amount of time and space resources. Work partially supported by the Italian Ministry of University and Research under Project MAINSTREAM “Algorithms for Massive Information Structures and Data Streams”. A preliminary version of this paper was presented at the 15th Annual European Symposium on Algorithms (ESA 2007) 5.     

Design and performance analysis of an inductive QoS routing algorithm

Routing mechanism is key to the success of large-scale, distributed communication and heterogeneous networks. Consequently, computing constrained shortest paths is fundamental to some important network functions such as QoS routing and traffic engineering. The problem of QoS routing with multiple additive constraints is known to be NP-complete but researchers have been designing heuristics and approximation algorithms for multi-constrained paths algorithms to propose pseudo-polynomial time algorithms. This paper introduces a polynomial time approximation quality of service (QoS) routing algorithm and constructs dynamic state-dependent routing policies. The proposed algorithm uses an inductive approach based on trial/error paradigm combined with swarm adaptive approaches to optimize lexicographically various QoS criteria. The originality of our approach is based on the fact that our system is capable to take into account the dynamics of the network where no model of the network dynamics is assumed initially. Our approach samples, estimates, and builds the model of pertinent aspects of the environment which is very important in heterogeneous networks. The algorithm uses a model that combines both a stochastic planned pre-navigation for the exploration phase and a deterministic approach for the backward phase. Multiple paths are searched in parallel to find the K best qualified ones. To improve the overall network performance, a load adaptive balancing policy is defined and depends on a dynamic traffic path probability distribution function. We conducted a performance analysis of the proposed QoS routing algorithm using OPNET based on a platform simulated network. The obtained results demonstrate substantial performance improvements as well as the benefits of learning approaches over networks with dynamically changing traffic.     

Randomized mutual exclusion with sub-logarithmic RMR-complexity

Mutual exclusion is a fundamental distributed coordination problem. Shared-memory mutual exclusion research focuses on local-spin algorithms and uses the remote memory references (RMRs) metric. Attiya, Hendler, and Woelfel (40th STOC, 2008) established an Ω(log N) lower bound on the number of RMRs incurred by processes as they enter and exit the critical section, where N is the number of processes in the system. This matches the upper bound of Yang and Anderson (Distrib. Comput. 9(1):51–60, 1995). The upper and lower bounds apply for algorithms that only use read and write operations. The lower bound of Attiya et al., however, only holds for deterministic algorithms. The question of whether randomized mutual exclusion algorithms, using reads and writes only, can achieve sub-logarithmic expected RMR complexity remained open. We answer this question in the affirmative by presenting starvation-free randomized mutual exclusion algorithms for the cache coherent (CC) and the distributed shared memory (DSM) model that have sub-logarithmic expected RMR complexity against the strong adversary. More specifically, each process incurs an expected number of O(log N / log log N) RMRs per passage through the entry and exit sections, while in the worst case the number of RMRs is O(log N).     

A Framework for Providing User Level Quality of Service Guarantees in Multi-Class Rate Adaptive Systems

The problem of channel sharing by rate adaptive streams belonging to various classes is considered. Rate adaptation provides the opportunity for accepting more connections by adapting the bandwidth of connections that are already in the system. However, bandwidth adaptation must be employed in a careful manner in order to ensure that (a) bandwidth is allocated to various classes in a fair manner (system perspective) and (b) bandwidth adaptation does not affect adversely the perceived user quality of the connection (user quality). The system perspective aspect has been studied earlier. This paper focuses on the equally important user perspective. It is proposed to quantify user Quality of Service (QoS) through measures capturing short and long-term bandwidth fluctuations that can be implemented with the mechanisms of traffic regulators, widely used in networking for the purpose of controlling the traffic entering or exiting a network node. Furthermore, it is indicated how to integrate the user perspective metrics with the optimal algorithms for system performance metrics developed earlier by the authors. Simulation results illustrate the effectiveness of the proposed framework.

Choosing a Random Peer in Chord

We present two new algorithms, Arc Length and Peer Count, for choosing a peer uniformly at random from the set of all peers in Chord (Proceedings of the ACM SIGCOMM 2001 Technical Conference, 2001). We show analytically that, in expectation, both algorithms have latency O(log n) and send O(log n) messages. Moreover, we show empirically that the average latency and message cost of Arc Length is 10.01log n and that the average latency and message cost of Peer Count is 20.02log n. To the best of our knowledge, these two algorithms are the first fully distributed algorithms for choosing a peer uniformly at random from the set of all peers in a Distributed Hash Table (DHT). Our motivation for studying this problem is threefold: to enable data collection by statistically rigorous sampling methods; to provide support for randomized, distributed algorithms over peer-to-peer networks; and to support the creation and maintenance of random links, and thereby offer a simple means of improving fault-tolerance. Research of S. Lewis, J. Saia and M. Young was partially supported by NSF grant CCR-0313160 and Sandia University Research Program grant No. 191445.     

The design and implementation of a Jini/Java-based A/V stream control and management

Distributed multimedia applications make diverse demands on communication services and quality of service. These requirements must be met end-to-end in an efficient and integrated manner through the enabling middleware of end systems and communication networks. The middleware should allow an adaptive quality of service (QoS) to be specified and supported; it should also provide application programming interfaces with integrated group communication support that simplify the programming task of multimedia applications. This paper focuses on the latter aspect and presents a distributed solution known as Stream Manager. Stream Manager allows heterogeneous media devices to be connected by the same session initiation procedures of Stream Manager. Through an underlying network connection management service, it allows a new group stream to be supported in addition to the OMGs unicast streams and point-to-multipoint multicast streams. The basic operations of Stream Manager and its application interfaces will be described, and the design and implementation of a prototype in Jini/Java will be presented. The performance of the prototype was measured experimentally in terms of throughput, delay, and latencies of joining and leaving a stream. We then compared its performance with that of streams handled by using Java RMI, Java sockets, and CORBA A/V stream. The performance of our system was found to be superior to that of Java RMI and comparable to that of Java socket but slightly inferior to that of CORBA A/V stream due to the higher intrinsic Java processing overhead.     

Average Rate Speed Scaling

Speed scaling is a power management technique that involves dynamically changing the speed of a processor. This gives rise to dual-objective scheduling problems, where the operating system both wants to conserve energy and optimize some Quality of Service (QoS) measure of the resulting schedule. Yao, Demers, and Shenker (Proc. IEEE Symp. Foundations of Computer Science, pp. 374–382, 1995) considered the problem where the QoS constraint is deadline feasibility and the objective is to minimize the energy used. They proposed an online speed scaling algorithm Average Rate (AVR) that runs each job at a constant speed between its release and its deadline. They showed that the competitive ratio of AVR is at most (2α) ^α /2 if a processor running at speed s uses power s ^α . We show the competitive ratio of AVR is at least ((2−δ)α) ^α /2, where δ is a function of α that approaches zero as α approaches infinity. This shows that the competitive analysis of AVR by Yao, Demers, and Shenker is essentially tight, at least for large α. We also give an alternative proof that the competitive ratio of AVR is at most (2α) ^α /2 using a potential function argument. We believe that this analysis is significantly simpler and more elementary than the original analysis of AVR in Yao et al. (Proc. IEEE Symp. Foundations of Computer Science, pp. 374–382, 1995).     

Color to gray conversions in the context of stereo matching algorithms

This study tackles the image color to gray conversion problem. The aim was to understand the conversion qualities that can improve the accuracy of results when the grayscale conversion is applied as a pre-processing step in the context of vision algorithms, and in particular dense stereo matching. We evaluated many different state of the art color to grayscale conversion algorithms. We also propose an ad-hoc adaptation of the most theoretically promising algorithm, which we call Multi-Image Decolorize (MID). This algorithm comes from an in-depth analysis of the existing conversion solutions and consists of a multi-image extension of the algorithm by Grundland and Dodgson (The decolorize algorithm for contrast enhancing, color to grayscale conversion, Tech. Rep. UCAM-CL-TR-649, University of Cambridge, 2005) which is based on predominant component analysis. In addition, two variants of this algorithm have been proposed and analyzed: one with standard unsharp masking and another with a chromatic weighted unsharp masking technique (Nowak and Baraniuk in IEEE Trans Image Process 7(7):1068–1074, 1998) which enhances the local contrast as shown in the approach by Smith et al. (Comput Graph Forum 27(2), 2008). We tested the relative performances of this conversion with respect to many other solutions, using the StereoMatcher test suite (Scharstein and Szeliski in Int J Comput Vis 47(1–3):7–42, 2002) with a variety of different datasets and different dense stereo matching algorithms. The results show that the overall performance of the proposed MID conversion are good and the reported tests provided useful information and insights on how to design color to gray conversion to improve matching performance. We also show some interesting secondary results such as the role of standard unsharp masking vs. chromatic unsharp masking in improving correspondence matching.     

Learning to search: Functional gradient techniques for imitation learning

Programming robot behavior remains a challenging task. While it is often easy to abstractly define or even demonstrate a desired behavior, designing a controller that embodies the same behavior is difficult, time consuming, and ultimately expensive. The machine learning paradigm offers the promise of enabling “programming by demonstration” for developing high-performance robotic systems. Unfortunately, many “behavioral cloning” (Bain and Sammut in Machine intelligence agents. London: Oxford University Press, 1995; Pomerleau in Advances in neural information processing systems 1, 1989; LeCun et al. in Advances in neural information processing systems 18, 2006) approaches that utilize classical tools of supervised learning (e.g. decision trees, neural networks, or support vector machines) do not fit the needs of modern robotic systems. These systems are often built atop sophisticated planning algorithms that efficiently reason far into the future; consequently, ignoring these planning algorithms in lieu of a supervised learning approach often leads to myopic and poor-quality robot performance. While planning algorithms have shown success in many real-world applications ranging from legged locomotion (Chestnutt et al. in Proceedings of the IEEE-RAS international conference on humanoid robots, 2003) to outdoor unstructured navigation (Kelly et al. in Proceedings of the international symposium on experimental robotics (ISER), 2004; Stentz et al. in AUVSI’s unmanned systems, 2007), such algorithms rely on fully specified cost functions that map sensor readings and environment models to quantifiable costs. Such cost functions are usually manually designed and programmed. Recently, a set of techniques has been developed that explore learning these functions from expert human demonstration. These algorithms apply an inverse optimal control approach to find a cost function for which planned behavior mimics an expert’s demonstration. The work we present extends the Maximum Margin Planning (MMP) (Ratliff et al. in Twenty second international conference on machine learning (ICML06), 2006a) framework to admit learning of more powerful, non-linear cost functions. These algorithms, known collectively as LEARCH (LEArning to seaRCH), are simpler to implement than most existing methods, more efficient than previous attempts at non-linearization (Ratliff et al. in NIPS, 2006b), more naturally satisfy common constraints on the cost function, and better represent our prior beliefs about the function’s form. We derive and discuss the framework both mathematically and intuitively, and demonstrate practical real-world performance with three applied case-studies including legged locomotion, grasp planning, and autonomous outdoor unstructured navigation. The latter study includes hundreds of kilometers of autonomous traversal through complex natural environments. These case-studies address key challenges in applying the algorithm in practical settings that utilize state-of-the-art planners, and which may be constrained by efficiency requirements and imperfect expert demonstration.

Quantitative assessment of user-level QoS and its mapping

This paper proposes a scheme for quantitative assessment of user-level (or perceptual) quality of service (QoS) for audio-video transmission by means of two psychometric methods: the method of paired comparisons and the law of comparative judgment. Moreover, we discuss QoS mapping from application-level QoS to user-level QoS by principal component analysis and multiple regression analysis. In the assessment, we simulate the transmission of an audio-video stream over a loaded network. In order to investigate the effect of the contents on QoS mapping, we treat two types of audio-video streams. By experiment, we demonstrate that our scheme can construct an interval scale as the user-level QoS parameter for each stream and represent it as a function of two application-level QoS parameters with high accuracy. We notice that the multiple regression line depends on the contents. We also propose the concept of control gain by media synchronization, which indicates how much media synchronization control subjectively lightens the average network load.     

Recording and playing back interactive media streams

Recording systems and media servers for networked audio and video streams have become an important part of today's Internet. In contrast to this, only a few recording and playback solutions currently exist for the data streams of interactive media applications (e.g., shared whiteboards and distributed virtual environments). So far these solutions are application-specific: individual algorithms and implementations are required for each application that is to be recorded. In this paper, we are proposing generic algorithms for the recording and playback of interactive media streams. These algorithms are based on a common model for the class of interactive media. They enable full random access to recordings by initializing the replaying applications with the required state information (e.g., the current slide in a recorded presentation). We have implemented these algorithms in the Interactive Media on Demand (IMoD) system. In order to interpret the semantics of an interactive media stream, the system requires that the Real-Time Application-Level Protocol for Distributed Interactive Media (RTP/I) protocol is used for the framing of the transmitted data. Any application using RTP/I can be recorded directly using the system without any modification. Interactive media streams not using RTP/I can be recorded using the generic recording algorithms. However, they require an adaptation of the system so that it is able to extract a minimal set of information from the application-level protocol of these streams. In addition to the generic recording algorithms, we present the architecture and major design considerations of the system and discuss the experiences gained from recording different interactive media applications.     

Evalvid-RA: trace driven simulation of rate adaptive MPEG-4 VBR video

Due to the increasing deployment of conversational real-time applications like VoIP and videoconferencing, the Internet is today facing new challenges. Low end-to-end delay is a vital QoS requirement for these applications, and the best effort Internet architecture does not support this natively. The delay and packet loss statistics are directly coupled to the aggregated traffic characteristics when link utilization is close to saturation. In order to investigate the behavior and quality of such applications under heavy network load, it is therefore necessary to create genuine traffic patterns. Trace files of real compressed video and audio are text files containing the number of bytes per video and audio frame. These can serve as material to construct mathematical traffic models. They can also serve as traffic generators in network simulators since they determine the packet sizes and their time schedule. However, to inspect perceived quality, the compressed binary content is needed to ensure decoding of received media. The EvalVid streaming video tool-set enables this using a sophisticated reassembly engine. Nevertheless, there has been a lack of research solutions for rate adaptive media content. The Internet community fears a congestion collapse if the usage of non-adaptive media content continues to grow. This paper presents a solution named Evalvid-RA for the simulation of true rate adaptive video. The solution generates real rate adaptive MPEG-4 streaming traffic, using the quantizer scale for adjusting the sending rate. A feedback based VBR rate controller is used at simulation time, supporting TFRC and a proprietary congestion control system named P-AQM. Example ns-2 simulations of TFRC and P-AQM demonstrate Evalvid-RA’s capabilities in performing close-to-true rate adaptive codec operation with low complexity to enable the simulation of large networks with many adaptive media sources on a single computer.