We present a new approach to lightweight intelligent transportation systems. Our approach does not rely on traditional expensive infrastructures, but rather on advanced machine learning algorithms. It takes images from traffic cameras at a limited number of locations and estimates the traffic over the entire road network. Our approach features two main algorithms. The first is a probabilistic vehicle counting algorithm from low-quality images that falls into the category of unsupervised learning. The other is a network inference algorithm based on an inverse Markov chain formulation that infers the traffic at arbitrary links from a limited number of observations. We evaluated our approach on two different traffic data sets, one acquired in Nairobi, Kenya, and the other in Kyoto, Japan.

This talk will share with the technical community on some directions of Services Research at IBM.

Given N request streams and L/spl les/N LRU caches, the cache assignment problem asks to which cache each stream should be assigned in order to minimize the overall miss rate. An efficient solution to this problem is provided, based on characterizing each stream using the stack reference model and characterizing the interaction of the streams using a bursty stream model. It is shown that for Bernoulli (purely random) mixing of streams, the optimal cache assignment is to have one cache per stream. In practice streams are mixed in a way that is much "burstier" than can be represented by the Bernoulli model. Therefore a method is presented for superposition of bursty streams. The performance of the methods developed for bursty stream superposition and cache assignment are tested using trace data obtained from the database system DB2. The resulting cache assignment recommendations are then applied to the DB2 system, and considerable performance improvement is found to result.

We present an exact analysis of the superposition of address streams into a cache buffer which is managed according to a least recently used (LRU) replacement policy. Each of the streams is characterized by a stack depth distribution, and we seek the cache hit ratio for each stream, when the combined, or superposed, stream is applied to a shared LRU cache. The combining process is taken to be a Bernoulli switching process. This problem arises in a number of branches of computer science, particularly in database systems and processor architecture. Previously, a number of approximation techniques of various complexities have been proposed for the solution of this problem. The main contribution of the paper is the description of an exact technique. We evaluate the performance of the exact and an approximate technique on realistic data, both in a lab environment and a large database installation. The results allow comparisons of the techniques, and provide insight into the validity of the Bernoulli switching assumption.>

Neural networks appear well suited to applications in the control of communications systems for two reasons: adaptivity and high speed. This paper describes application of neural networks to two problems, admission control and switch control, which exploit the adaptivity and speed property, respectively. The admission control problem is the selective admission of a set of calls from a number of inhomogeneous call classes, which may have widely differing characteristics as to their rate and variability of traffic, onto a network. It is usually unknown in advance which combinations of calls can be simultaneously accepted so as to ensure satisfactory performance. The approach adopted is that key network performance parameters are observed while carrying various combinations of calls, and their relationship is learned by a neural network structure. The network model chosen has the ability to interpolate or extrapolate from the past results and the ability to adapt to new and changing conditions. The switch control problem is the service policy used by a switch controller in transmitting packets. In a crossbar switch with input queueing, significant loss of throughput can occur when head-of-line service order is employed. A solution can be based on an algorithm which maximizes throughput. However since this solution is typically required in less than one microsecond, software implementation policy is infeasible. We will carry out an analysis of the benefits of such a policy, describe some existing proposed schemes for its implementation, and propose a further scheme that provides this submicrosecond optimization.

We consider the superposition of address streams into a cache buffer which is managed according to a Least Recently Used (LRU) replacement policy. Each of the streams is characterized by a stack depth distribution, i.e., the cache hit ratio as a function of the cache size, if that individual stream were applied to a LRU cache. We seek the cache hit ratio for each stream, when the combined stream is applied to a shared LRU cache. This problem arises in a number of branches of computer science, particularly in database systems and processor architecture.We provide two techniques to solve this problem and demonstrate their effectiveness using database I/O request streams. The first technique is extremely simple and relies on an assumption that the buffer is "well-mixed". The second technique relaxes this assumption and provides more accurate results. We evaluate the performance of the two techniques on realistic data, both in a lab environment and a large database installation. We find that the first simple technique provides accuracy which is sufficient for most practical purposes. By investigating sources of error and trying various improvements in the model we obtain some insight into the nature of database I/O request streams.

The computer-vision problem of determining object orientation from the consensus of orientations of individual symbols or marks is examined. The problem arises in automatic inspection where orientation can be detected from printed text but there is no knowledge of the content of the text. This is a high-dimensional classification problem, and there is a requirement for highly accurate detection and rapid processing. The typical multilayer threshold networks are seen as unsuitable, and the optimal Bayesian detector is derived and found to have the highly parallel structure of a feedforward network. The learning vector quantization neural network method of T. Kohonen (1988) is also applied. Experimental results, comparisons, and a complete implementation are described.>

Neural network memories with storage prescriptions based on Hebb’s rule are known to collapse as more words are stored. By requiring that the most recently stored word be remembered precisely, a new simple short-term neural network memory is obtained and its steady state capacity analyzed and simulated. Comparisons are drawn with Hopfield’s method, the delta method of Widrow and Hoff, and the revised marginalise model of Mezard, Nadal, and Toulouse.

The LRU cache hit function is used as a general characterization of locality of reference to address the synthesis question of whether benchmarks can be created that have a required locality of reference. Several results are given that show circumstances under which this synthesis can or cannot be achieved. An additional characterization called the warm-start cache hit function is introduced and shown to be efficiently computable. The operations of repetition and replication are used to form new programs, and their characteristics are derived. Using these operations, a general benchmark synthesis technique is obtained and demonstrated with an example.>

An important part of a distributed system design is the choice of a load sharing or global scheduling strategy. A comprehensive literature survey on this topic is presented. We propose a taxonomy of load sharing algorithms that draws a basic dichotomy between source-initiative and server-initiative approaches. The taxonomy enables ten representative algorithms to be selected for performance evaluation. A performance metric called the Q-factor (quality of load sharing) is defined which summarizes both overall efficiency and fairness of an algorithm and allows algorithms to be ranked by performance. We then evaluate the algorithms using both mathematical and simulation techniques. The results of the study show that: i) the choice of load sharing algorithm is a critical design decision; ii) for the same level of scheduling information exchange, server-initiative has the potential of outperforming source-initiative algorithms (whether this potential is realized depends on factors such as communication overhead); iii) the Q-factor is a useful yardstick; iv) some algorithms, which have previously received little attention, e.g., multiserver cyclic service, may provide effective solutions.

Synchronous and asynchronous I/O access disciplines are compared for use in a transaction-processing system. Synchronous access causes an executing process to be suspended while its I/O is performed, whereas asynchronous access permits a process to continue execution concurrently with the servicing of its I/O requests. While it is intuitively clear that asynchronous access generally yields superior performance due to the greater concurrency allowed between transactions, our results considerably sharpen such intuition by quantifying the margin of improvement. The performances of the two disciplines are studied under a variety of conditions by using simple and standard queuing network models. Of particular interest is a situation where an I/O device is congestion-adaptive in service rate. Simulation models for a realistic implementation are described and the results compared with those of the queuing models. The paper concludes by giving guidelines which determine whether, for a particular system, asynchronous I/O is likely to provide a significantly better processing capacity than synchronous I/O. We also observe that similar performance advantages (due to greater transaction concurrency) can be obtained by a transaction-processing architecture which uses re-entrant procedures and dynamically generates a process and data area for each active transaction.