12313444
Real time guarantee of aperiodic packets in single hop ad hoc wireless networks
Building real-time applications on 802.11 wireless networks is challenging because the medium access protocol is distributed and nodes contend for the channel nondeterministically. So far all attempts at providing real-time services in 802.11 require restrictive traffic assumptions such as periodicity. In this paper we describe distributed admission control, a modification to 802.11 that, when used with distributed prioritization, provides real-time guarantees for aperiodic packets. We show that barring external errors such as interference on the channel or incorrect priority scheduling this protocol guarantees deadlines will be met.
195349457
Analysis of cache-related preemption delay in fixed-priority preemptive scheduling
We propose a technique for analyzing cache-related preemption delays of tasks that cause unpredictable variation in task execution time in the context of fixed-priority preemptive scheduling. The proposed technique consists of two steps. The first step performs a per-task analysis to estimate cache-related preemption cost for each execution point in a given task from the number of useful cache blocks at the execution point. The second step computes the worst case response time of each task using a response time equation and a linear programming technique which takes as its input the preemption cost information of tasks obtained in the first step. Our experimental results show that the proposed technique gives a prediction of the worst case cache-related preemption delay that is up to 60% tighter than that obtained from previous approaches.
7460330
Enhanced analysis of cache-related preemption delay in fixed-priority preemptive scheduling
We propose an enhanced technique for analyzing, and thus bounding cache related preemption delay in fixed priority preemptive scheduling focusing on instruction caching. The proposed technique improves upon previous techniques in two important ways. First, the technique takes into account the relationship between a preempted task and the set of tasks that execute during the preemption when calculating the cache related preemption delay. Second, the technique considers phasing of tasks to eliminate many infeasible task interactions. These two features are expressed as constraints of a linear programming problem whose solution gives a guaranteed upper bound on the cache related preemption delay. The paper also compares the proposed technique with previous techniques. The results show that the proposed technique gives up to 60% tighter prediction of the worst case response time than the previous techniques.
17289303
Spare CASH: reclaiming holes to minimize aperiodic response times in a firm real-time environment
Scheduling periodic tasks that allow some instances to be skipped produces spare capacity in the schedule. Only a fraction of this spare capacity is uniformly distributed and can easily be reclaimed for servicing aperiodic requests. The remaining fraction of the spare capacity is non-uniformly distributed, and no existing technique has been able to reclaim it. We present a method for improving the response times of aperiodic tasks by identifying the non-uniform holes in the schedule and adding these holes as extra capacity to the capacity queue of the CASH mechanism. The non-uniform holes can account for a significant portion of spare capacity, and reclaiming this capacity results in considerable improvements to aperiodic response times.
42435746
Efficiently supporting hard/soft deadline transactions in real-time database systems
As in other application areas, there is an increasing need for managing a large amount of data in the real-time area. This need gave birth to a system called a real-time database system (RTDBS) that provides database operations with timing constraints. One typical timing constraint in an RTDBS is temporal consistency that states that a transaction must read temporally valid data objects. This requires the data objects to be updated repeatedly. This paper proposes three novel schemes that aim to minimize the number of updates of data objects needed for guaranteeing the temporal consistency requirements of transactions with hard-deadlines. The three guarantee schemes differ from each other in the amount of updates and the implementation complexity. This paper also gives a framework for integrating transactions with soft-deadlines into the three guarantee schemes.
16132542
Stochastic analysis of periodic real-time systems
This paper describes a stochastic analysis method for general periodic real-time systems. The proposed method accurately computes the response time distribution of each task in the system, thus making it possible to determine the deadline miss probability of individual tasks, even for systems with maximum utilization factor greater than one. The method uniformly covers both fixed-priority scheduling (such as rate monotonic) as well as dynamic-priority scheduling (such as earliest deadline first) and can handle arbitrary relative deadlines and execution time distributions. The accuracy of the method is proven by comparing the results from the analysis with those obtained from simulations, as well as other methodologies in the literature.
203663688
Practical Solutions for QoS-Based Resource Allocation
An apparatus and method is disclosed for forming a liquid-tight container having a rectangular cross-section formed from a one-piece, T-shaped blank of paperboard material. The carton preferably includes an access flap and straw element on one side thereof which, when manually lifted, exposes an end of the straw element from which the contents of the carton may be consumed by a user. The apparatus is compact in nature, possessing relatively few transport mechanisms which advance the T-shaped carton blank through a plurality of work stations. A novel method and apparatus for serially applying the straw element and access panel to the carton blank is disclosed, wherein the straw element and a length of polyethylene coated Mylar tape is automatically bonded to the carton blank upon a rotating heat sealing and alignment drum. A conveyor for collating a plural number of the carton blanks about a forming mandrel is also provided, and is positioned transversely to the remainder of the apparatus thereby significantly reducing the overall size of the apparatus. An ultrasonic welder bonds the side seams and end closure panels of the container upon a rotating crossbar mandrel which eliminates any misalignment during the sealing process. A substantially rigid conveyor transport carries a plurality of the carton blanks through pre-form, filler, and end closure work stations, and includes plural anvils for the ultrasonic welding process. An ejector mechanism is additionally provided which ejects the filled carton blanks from the rigid conveyor along a dual direction path, thereby eliminating the possibility of creasing or puncturing the filled and sealed container. The apparatus of the present invention additionally accommodates the production of differing size containers with only minor adjustments.
6801906
Attention-based design of augmented reality interfaces
The objects and surfaces of a task-based environment can be layered with digital interfaces to make them easier and safer to use. Once information can be projected anywhere in the space, it becomes crucial to design the information to make optimal use of users' attention. We have prototyped and evaluated a real-world augmented reality kitchen where user-centered interfaces and displays can be projected anywhere in the space to improve its usability. The augmented environment is designed to support the activities of a variety of people in diverse kitchen environments.This paper presents five intelligent kitchen systems that layer useful interfaces onto the refrigerator, range, cabinets, countertops and sink. The interface design is driven by human factors, especially attention theory and user evaluations. By projecting interfaces where they require the least cognitive load, we hope to improve the performance and confidence of users. The design employs cueing and search principles from attention theory. We present the results of pilot studies and future directions for our work.
2862791
A data delivery strategy in ubiquitous computing systems
Browsing Web pages through wireless devices will become more and more popular in the near future. However, accessing a large chunk of Web data incurs a great amount of access latency while a mobile user migrates across cells. This paper investigates this problem and proposes an effective way of delivering such data to a mobile user in a ubiquitous computing system. Our data delivery (/spl Dscr//sup 2/) strategy is based on the dynamic programming skill needed to pre-assign the user-requested data on the possible cells to be visited in order to reduce the access latency. We first design an encoding method for the cells and then derive the properties of the encoding scheme. These properties are then used in our algorithm to deliver the data. Finally, experiments are conducted to demonstrate the feasibility and efficiency of the proposed method.
33610569
Compression-based broadcast strategies in wireless information systems
Data delivery is through broadcast in wireless information systems due to the asymmetric communication property. However, broadcasting data easily wastes large access time because the large amount of data pages needs to be broadcast. In this paper we propose three compression-based strategies considering access order to reduce access time. Then, the expected access time of three proposed strategies is also derived by using the probability model. Our analytic and experimental results show that the compression-based broadcast strategies can dramatically reduce the access time for mobile users (MU).
38028125
Lover's cups: drinking interfaces as new communication channels
This paper shows how computer interfaces can enhance common activities and use them as communication method between people. In this paper, the act of drinking is used as an input of remote communication with the support of computer interfaces. We present Lover's Cups which enable people to share the time of drinking with someone they care about in different places. Using a wireless connection, an otherwise ordinary pair of cups becomes a communication device, amplifying the social aspect of drinking behavior.