17022940
Using Windows NT for Real-Time Applications: Experimental Observations and Recommendations
Windows NT was not designed as a real time operating system, but market forces and the acceptance of NT in industrial applications have generated a need for achieving real time functionality with NT. As its use for real time applications proliferates, based on an experimental evaluation of NT, we quantitatively characterize the obstacles placed by NT. As a result of these observations, we provide a set of recommendations for users to consider while building real time applications on NT. These are validated by the use of NT for a prototype application involving real time control that includes multimedia information processing. The results of the above study should provide system designers with guidelines, as well as insight, into the design of an architecture based on NT for supporting applications with components having real time constraints.
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.
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.
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.
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.
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.
3541834
A buyer's agent
Personal agents have been developed that assist user with information processing needs by generating, filtering, collecting, or transforming information. On the other hand internet stores are providing services customized by the needs and interests of individual customers. Such services can be viewed as "seller's agents" whose goal is to push merchandise and/or services on to the users. This leads us to believe that there is a growing need for deploying "buyer's agents" whose goal is to best serve the user's interests. In particular, such agents should alert the user of the complex interactions between specified preferences and prevailing market conditions. The availability of such information makes the user a more informed customer. We discuss the design and prototype implementation of a buyer's agent in an apartment locator application.
31766769
Improved selection in totally monotone arrays
This paper's main result is an -time algorithm for computing the kth smallest entry in each row of an m×n totally monotone array. (A two-dimensional array A={a[i, j]} is totally monotone if for all i1<i2 and j1<j2, a[i1, j1]<a[i1, j2] implies a[i2, j1]<a[i2, j2].) For large values of k (in particular, for k=⌈n/2⌉), this algorithm is significantly faster than the O(k(m + n))-time algorithm for the same problem due to Kravets and Park. An immediate consequence of this result is an O(n3/2lg1/2 n)-time algorithm for computing the kth nearest neighbor of each vertex of a convex n-gon. In addition to the main result, we also give an O(n lg m)-time algorithm for computing an approximate median in each row of an m×n totally monotone array; this approximate median is an entry whose rank in its row lies between ⌊n/4⌋ and ⌈3n/4⌉ − 1.
36334586
Developing an Automated Distributed Meeting Scheduler
Automated scheduling agents allow users to concentrate on productive tasks and to improve the quality of information processing. The author uses a distributed approach with intelligent agents to design and develop efficient meeting scheduling. The purpose of the project is to design and implement a software system that uses intelligent meeting-scheduling agents that can negotiate with other agents without compromising their user-specified constraints. A small group of researchers in our department runs the prototype system, and we are using feedback from them to improve the interface and to expand the functionality of the system.
17017836
Limiting deception in groups of social agents
In open environments there is no central control over agent behaviors. On the contrary, agents in such systems can be assumed to be primarily driven by self-interests. Under the assumption that agents remain in the system for significant time periods, or that the agent composition changes only slowly, a prescriptive strategy has been previously presented for promoting and sustaining cooperation in the group. This strategy was shown to improve both individual and group performance in the long run. The prescribed strategy has been an adaptive, probabilistic, reciprocity-based policy for deciding which other individual to cooperate with. In this paper two mechanisms are investigated to limit exploitation of the reciprocative strategy by deceptive agents: 1) a penalty factor for declining requests for help, and 2) a cutoff limit on outstanding balance of help. The relative effectiveness of these mechanisms is evaluated for augmenting robustness of agent behaviors, without adversely affecting performance of homogeneous groups of reciprocative agents.
207161230
FeedMe: a collaborative alert filtering system
As the number of alerts generated by collaborative applications grows, users receive more unwanted alerts. FeedMe is a general alert management system based on XML feed protocols such as RSS and ATOM. In addition to traditional rule-based alert filtering, FeedMe uses techniques from machine-learning to infer alert preferences based on user feedback. In this paper, we present and evaluate a new collaborative naïve Bayes filtering algorithm. Using FeedMe, we collected alert ratings from 33 users over 29 days. We used the data to design and verify the accuracy of the filtering algorithm and provide insights into alert prediction.