16333487
Playback restart in interactive streaming video applications
Low latency is crucial in networked multimedia applications such as on-demand streaming audio and video. In this paper we consider the problem of restarting or resuming playback following an interactive operation such as fast forward, rewind, or indexed jump in stored on-demand video. We present two approaches to restart playback after an interactive operation, and develop algorithms to compute the latencies incurred in restarting playback. Using long MPEG-1 traces, with an optimal smoothing technique to transmit data for regular playback, we demonstrate that the latencies incurred under our approaches are very small. We next examine the latencies incurred when restarting playback in a video server under two policies for sharing its bandwidth: (a) one in which only regular playback bandwidth is available to restart playback and (b) one in which additional free server bandwidth (if any) is accessible. We find playback restart latencies to be similarly low under both policies, suggesting that the simpler approach (a) is sufficient.
2290480
Optimal multicast smoothing of streaming video over an internetwork
A number of applications such as internet video broadcasts, corporate telecasts, distance learning etc. require transmission of streaming video to multiple simultaneous users across an internetwork. The high bandwidth requirements coupled with the multi-timescale burstiness of compressed video make it a challenging problem to provision network resources for transmitting streaming multimedia. For such applications to become affordable and ubiquitous, it is necessary to develop scalable techniques which can efficiently deliver streaming video to multiple heterogeneous clients across a heterogeneous internetwork. We propose using multicasting of smoothed video and differential caching of the video at intermediate nodes in the distribution tree, as techniques for reducing the network bandwidth requirements of such dissemination. We formulate the multicast smoothing problem, and develop an algorithm for computing the set of optimally smoothed transmission schedules for the tree (such that the transmission schedule along each link in the tree has the lowest peak rate and rate variability for any feasible transmission schedule for that link) given a buffer allocation to the different nodes in the tree. We also develop an algorithm to compute the minimum total buffer allocation to the entire tree and the corresponding allocation to each node, such that feasible transmission is possible to all the clients, when the tree has heterogeneous rate constraints. MPEG-2 trace-driven performance evaluations indicate that there are substantial benefits from multicast smoothing and differential caching. For example, the optimal multicast smoothing can reduce the total transmission bandwidth requirements in the distribution tree by more than a factor of 3 as compared to multicasting the unsmoothed stream.
6303606
Class-of-service mapping for QoS: a statistical signature-based approach to IP traffic classification
The ability to provide different Quality of Service (QoS) guarantees to traffic from different applications is a highly desired feature for many IP network operators, particularly for enterprise networks. Although various mechanisms exist for providing QoS in the network, QoS is yet to be widely deployed. We believe that a key factor holding back widespread QoS adoption is the absence of suitable methodologies/processes for appropriately mapping the traffic from different applications to different QoS classes. This is a challenging task, because many enterprise network operators who are interested in QoS do not know all the applications running on their network, and furthermore, over recent years port-based application classification has become problematic. We argue that measurement based automated Class of Service (CoS) mapping is an important practical problem that needs to be studied.
 In this paper we describe the requirements and associated challenges, and outline a solution framework for measurement based classification of traffic for QoS based on statistical application signatures. In our approach the signatures are chosen in such as way as to make them insensitive to the particular application layer protocol, but rather to determine the way in which an application is used -- for instance is it used interactively, or for bulk-data transport. The resulting application signature can then be used to derive the network layer signatures required to determine the CoS class for individual IP datagrams. Our evaluations using traffic traces from a variety of network locations, demonstrate the feasibility and potential of the approach.
6084623
Proxy prefix caching for multimedia streams
High latency and loss rates in the Internet make it difficult to stream audio and video without introducing a large playback delay. To address these problems, we propose a prefix caching technique whereby a proxy stores the initial frames of popular clips. Upon receiving a request for the stream, the proxy initiates transmission to the client and simultaneously requests the remaining frames from the server. In addition to hiding the delay, throughput, and loss effects of a weaker service model between the server and the proxy, this novel yet simple prefix caching technique aids the proxy in performing workahead smoothing into the client playback buffer. By transmitting large frames in advance of each burst, workahead smoothing substantially reduces the peak and variability of the network resource requirements along the path from the proxy to the client. We describe how to construct a smooth transmission schedule, based on the size of the prefix, smoothing, and playback buffers, without increasing client playback delay. Experiments with MPEG traces show how a few megabytes of buffer space at the proxy can substantially reduce the bandwidth requirements of variable-bit-rate video. Drawing on these results, we present guidelines for allocating buffer space for each stream, and how to effectively share buffer and bandwidth resources among multiple clients and streams.
1681173
Optimal proxy cache allocation for efficient streaming media distribution
We address the problem of efficiently streaming a set of heterogeneous videos from a remote server through a proxy to multiple asynchronous clients so that they can experience playback with low startup delays. We determine the optimal proxy prefix cache allocation to the videos that minimizes the aggregate network bandwidth cost. We integrate proxy caching with traditional server-based reactive transmission schemes such as hatching, patching and stream merging to develop a set of proxy-assisted delivery schemes. We quantitatively explore the impact of the choice of transmission scheme, cache allocation policy, proxy cache size, and availability of unicast versus multicast capability, on the resulting transmission cost. Our evaluations show that even a relatively small prefix cache (10%-20% of the video repository) is sufficient to realize substantial savings in transmission cost. We find that carefully designed proxy-assisted reactive transmission schemes can produce significant cost savings even in a predominantly unicast environment such as the Internet.
1578205
Broadcast on demand: efficient and timely dissemination of data in mobile environments
The demand for efficient scalable and cost effective mobile information access systems is rapidly growing. Radiofrequency broadcast plays a major role in mobile computing, and there is a need to provide service models for broadcasting information according to mobile users' needs. The authors present a model called broadcast on demand (BoD), which provides timely broadcasts according to requests from users. Compared to static broadcast, this approach has a different emphasis: it is based on a demand driven framework, aimed at satisfying the temporal constraints of the requests, and uses scheduling techniques at the server side to utilize the limited bandwidth dynamically and efficiently. Several broadcast transmission scheduling policies for BoD are examined. The study indicates that EDF-based policies combined with batching of requests achieve good performance. The results show that BoD is successful in satisfying the temporal constraints of the requests and is a viable service model for wireless broadcast stations.
10902519
Effects of Local Information on Group Behavior
Researchers in the field of Distributed Artificial Intelligence have studied the effects of local decisionmaking on overall system performance in both cooperative and self-interested agent groups (Bond & Gasser, 1988) . The performance of individual agents depends critically on the quality of information available to it about local and global goals and resources. Whereas in general it is assumed that the more accurate and up-to-date the available information, the better is the expected performance of the individual and the group, this conclusion can be challenged in a number of scenarios. The populace in human societies tend to look for opportunities and search for better opportunities in their environment (Bartos, 1967) . The theory of migration in social behavior and occupational mobility suggests that the stability of the population depends on how an individual chooses its action based on the prevailing circumst antes. As agent designers, we are faced with the problem of developing decision mechanisms that allow agent societies to stabilize in states where system resources are effectively utilized. In this research, we focus on a particular aspect of distributed decision-making: the effect of limited global knowledge on group behavior. The research question that we are asking is the following: Can limited local knowledge be a boon rather than a bane in a multiagent system ? To investigate this issue we use a resource utilization problem where a number of agents are distributed between several identical resources. We assume that the cost of using any resource is directly proportional to its usage. This cost can be due to a delay in processing of the task in hand, or a reduction in the quality of the resource due to congestion. Hence, there is a justified urge in agents to seek out and move to resource with lesser usage. Other researchers have shown that such systems can exhibit oscillatory or chaotic behavior where agents move back and forth between resources (Hogg & Huberman 1991; Kephart, Hogg & Huberman 1989) resulting in ineffective uti1406 AAAI-96 lization of system resources. Whereas asynchrony, heterogeneous agent decision mechanisms, etc. has been suggested as possible means for solving the instability problem, our proposed solution of using locally differing global views is a novel mechanism to introduce asymmetry in group decisions that expedites group stability.
6555481
An Efficient Protocol for Negotiation over Multiple Indivisible Resources
We study the problem of autonomous agents negotiating the allocation of multiple indivisible resources. It is difficult to reach optimal outcomes in bilateral or multi-lateral negotiations over multiple resources when the agents' preferences for the resources are not common knowledge. Self-interested agents often end up negotiating inefficient agreements in such situations. We present a protocol for negotiation over multiple indivisible resources which can be used by rational agents to reach efficient outcomes. Our proposed protocol enables the negotiating agents to identify efficient solutions using systematic distributed search that visits only a subspace of the whole solution space.
929830
Parallel searching in generalized Monge arrays with applications
This paper investigates the parallel time and processor complexities of several searching problems involving Monge and Monge-composite arrays. We present array-searching algorithms for concurrent-readconcurrent-write (CRCW) PRAMS, concurrent-readexclusive-write (CREW) PRAMS, hypercubes, cubeconnected-cycles, and shuffle-exchange networks. All these algorithms run in optimal time, and their processor-time products are all within an O(lg n) factor of the worst-case sequential bounds. Several applications of these algorithms are also given. Two applications improve previous results substantially, and the others provide novel parallel algorithms for problems not previously considered.
9022148
Parallel Searching in Generalized Monge Arrays
Abstract. This paper investigates the parallel time and processor complexities of several searching problems involving Monge, staircase-Monge, and Monge-composite arrays. We present array-searching algorithms for concurrent-read-exclusive-write (CREW) PRAMs, hypercubes, and several hypercubic networks. All these algorithms run in near-optimal time, and their processor-time products are all within an 
 $O (\lg n)$ factor of the worst-case sequential bounds. Several applications of these algorithms are also given. Two applications improve previous results substantially, and the others provide novel parallel algorithms for problems not previously considered.
15537048
Modeling opponent decision in repeated one-shot negotiations
In many negotiation and bargaining scenarios, a particular agent may need to interact repeatedly with another agent. Typically, these interactions take place under incomplete information, i.e., an agent does not know exactly which offers may be acceptable to its opponent or what other outside options are available to that other agent. In such situations, an agent can benefit by learning its opponent's decision model based on its past experience. In particular, being able to accurately predict opponent decisions can enable an agent to generate offers to optimize its own utility. In this paper, we present a learning mechanism using Chebychev's polynomials by which an agent can approximately model the decision function used by the other agent based on the decision history of its opponent. We study a repeated one-shot negotiation model which incorporates uncertainty about opponent's valuation and outside options. We evaluate the proposed modeling mechanism for optimizing agent utility when negotiating with different class of opponents.