The paper investigates the scheduling of packets under overload in the context of wireless building control networks. We focus on the transmission specification of the IEEE 802.15.4 standard to provide actual transmission estimates. The paper analyses the optimal conditions for sending periodic packets with 1 or 2 transmission times and fixed deadlines. Simulations provide the transceiver usage values under the calculated optimal scheduling conditions. The simulations extend the results by looking at 8 transmission times and an exponential distribution of packet release times. A counterintuitive result is the occurrence of a performance decrease with increasing deadline, other conditions remaining constant.

This paper outlines an efficient variation of the Flooding Time Synchronization Protocol (FTSP) on real hardware with an IEEE 802.15.4 MAC layer. The paper compares the performance of two clock drift estimation techniques: Least Squares Linear Regression and the Kalman filter. In assessing the viability of time synchronization in an industrial setting, our reliance on real hardware gives confidence for the deployment in future products. The concrete result is a high time synchronization accuracy, with an achievable average error of 0.4 μs, and a repetition interval of a few seconds, while using a star network topology.

In this article we provide a model for the dynamic behavior of media processing chains of tasks communicating via bounded buffers. The aim is to find the overall behavior of a chain from which performance parameters (such as start time and response time of individual tasks, chain end-to-end response time, number of context switches and resource utilization) follow. This behavior is characterized in terms of the elementary actions of the tasks that make up the chain. From this we derive corollaries that give design guidelines, supporting the goal of improving chain end-to-end response time and the optimization of resources, which is achieved by minimizing context-switching overhead and buffer sizes

The paper addresses the issue of controlling streaming of scalable video over wireless links to resource-constrained devices (terminals). A controller on the terminal maximizes user perceived quality taking into account available computing resources and condition of the network. The controller determines the number of layers to be processed using a strategy calculated for the given layers configuration and network conditions. We present a method to decrease the number of pre-calculated strategies for the controller by exploring the dependency between layers configuration and network conditions.

Streaming video over wireless networks can be complicated by a highly varying link capacity. We present an approach that allows close-to-optimal utilization of the link bandwidth. We use a property of the medium access control (MAC) of the 802.11 standard to do instant detection of the bandwidth fluctuations by observing the transmission rate from the sending buffer. The specifics of a general MPEG stream allow classifying video-frames by their importance for the user-perceived quality. We build a scheduling mechanism that favors transmission of more important frames at the expense of the less important ones. We validate our approach by means of test-bed experiments and demonstrate a significant improvement of the end video quality.

This work shows that scalable video techniques together with a controlling mechanism for a device that receives and decodes video data provide a solution to some challenges posed by in-home networks. The challenges are resource limitations of devices (processor, memory, etc) and network (bandwidth). Additionally, a wireless network usually has bandwidth fluctuations that consecutively lead to rapid throughput fluctuations. These rapid changes severely reduce the quality of viewing as perceived by an end user. We developed a controller that optimizes user-perceived quality when looking at available input data and available processing power. The quality is optimized by smoothening the quality fluctuations and avoiding deadline misses. The strategy used by the controller is created offline by means of a Markov decision process

This paper investigates the tradeoff between reliability and effectiveness for the IPv4 Zeroconf protocol, proposed by Cheshire/Adoba/Guttman in 2002, dedicated to the selfconfiguration of IP network interfaces. We develop a simple stochastic cost model of the protocol, where reliability is measured in terms of the probability to avoid an address collision after configuration, while effectiveness is viewed as the average penalty perceived by a user. We derive an analytical expression for the user penalty which we use to derive optimal configuration parameters of the network, restricting to those parameters which are under the control of a consumer electronics manufacturer. In particular we show that minimal cost and maximal reliability are qualities that cannot be achieved at the same time.

Concerns the formal specification and mechanical verification of transaction processing systems aimed at distributed databases. In such systems, a standard set of ACID (Atomicity, Consistency, Isolation and Durability) properties must be ensured by a combination of concurrency control and recovery protocols. In the existing literature, these protocols are often studied in isolation, making strong assumptions about each other. The problem of combining them in a formal way has been largely ignored. To study the formal verification of combined protocols, we specify a transaction processing system, integrating strict two-phase locking, undo/redo recovery and two-phase commit. In our method, the locking and undo/redo mechanism at distributed sites is defined by state machines, whereas the interaction between sites according to the two-phase commit protocol is specified by assertions. We have proved, using the interactive proof checker of PVS, that our system satisfies atomicity, durability and serializability properties.

The formal specification and mechanical verification of an atomic commitment protocol (ACP) for distributed real-time and fault-tolerant databases is presented. As an example, the non-blocking ACP of Babaoglu and Toueg (1993) is analyzed. An error in their termination protocol for recovered participants has been detected. We propose a new termination protocol which has been proved correct formally. To stay close to the original formulation of the protocol, timed state machines are used to specify the processes, whereas the communication mechanism between processes is defined using assertions. Formal verification has been performed incrementally: adding recovery from crashes only after having proved the basic protocol. The verification system PVS was used to deal with the complexity of this fault-tolerant protocol.

We consider a system in which many users run queries to examine subsets of a large object set. The object set is partitioned into files on tape. A single subset of objects will be visited by multiple queries in the workload. This locality of access creates the opportunity for caching on disk. We introduce and evaluate a novel optimisation, cache filtering, in which the 'hot' objects are automatically extracted from the files that are staged on disk, and then cached separately in new files on disk. Cache filtering can lead to complex situations in the disk cache. We show that these do not prevent effective caching and we introduce a special cache replacement algorithm to maximise efficiency. Through simulations we evaluate the system over a broad range of likely workloads. Depending on workload and system parameters, the cache filtering optimisation yields speedup factors up to 6.

The authors propose database support for large sets of temporal, real-time data. Prediction models are supported: transactions can write data items to the database that have been "measured in the future". Therefore, it is necessary to allow multiple instances of the same data item, with different times of measurement. This requires larger storage requirements, but can also be used for interpolation of intermediate values, and extrapolation of future values. It is recognized that temporal correctness of data is a characteristic of the usage of the data item. Real-time data requirements are specified for each individual transaction, rather than for each data item. Transactions can access multiple instances of the same data item (for extrapolation purposes), and can specify separate temporal constraints for each accessed instance. An implementation of a hard-real-time database that realizes these requirements is given, to show that the specified requirements are realistic.

We optimize the speed of real-time databases by optimizing the scheduler. The performance of a database is directly linked to the environment it operates in, and we use environment characteristics as guidelines for the optimization. A typical telecom environment is investigated, and characteristics that are relevant to performance are derived. A theoretical study of database scheduler performance is combined with the characteristics of the telecom environment. Design issues are extracted from this combination. It turns out that the scheduler overhead, rather than the concurrency is the most important factor in database performance. With the derived issues in mind, a light-weight optimistic concurrency control (OCC-light) scheduler has been designed. The OCC-light is implemented in the Mnesia database. Experiments were conducted to compare OCC-light against the existing two phase locking (2PL) scheduler. The OCC-light compared favorably to 2PL, as was already suggested by our theoretical study.

In the very large object database systems planned for some future particle physics experiments, typical physics analysis jobs will traverse millions of read-only objects, many more objects than fit in the database cache. Thus, a good clustering of objects on disk is highly critical to database performance. We present the implementation and performance measurements of a prototype reclustering mechanism which was developed to optimise I/O performance under the changing access patterns in a high energy physics database. Reclustering is done automatically and on-line. The methods used by our prototype differ greatly from those commonly found in proposed general-purpose reclustering systems. By exploiting some special characteristics of the access patterns of physics analysis jobs, the prototype manages to keep database I/O throughput close to the optimum throughput of raw sequential disk access.

PORS is a system designed for on-line event reconstruction in high energy physics (HEP) experiments. It uses the CPREAD reconstruction program. Central to the system is a parallel in-memory database which is used as communication medium between parallel workers. A farming control structure is implemented with PORS in a natural way. The database provides structured storage of data with a short life time. PORS serves as a case study for the construction of a methodology on how to apply parallel in-memory databases to HEP software, providing systematic structuring of HEP data, easier parallelization and consequently a simpler development and maintenance of code. PORS runs on a SPARCcenter 2000 8-node shared memory computer.