Kang G. Shin Real-Time Computing Laboratory Department of Electrical Engineering and Computer Science The University of Michigan 1301 Beal Avenue Ann Arbor, MI 48109-2122 1-734-763-0391 (voice) 1-734-763-8094 (fax) URL: http://www.eecs.umich.edu/~kgshin
Kang G. Shin is the Kevin and Nancy O'Connor Chair Professor of Computer Science, and the Founding Director of the Real-Time Computing Laboratory, Department of Electrical Engineering and Computer Science, The University of Michigan, Ann Arbor, Michigan. His current research focuses on QoS-sensitive networking and computing as well as on embedded real-time OS, middleware and applications, all with emphasis on timeliness and dependability.
He has supervised the completion of 42 PhD theses, and authored/coauthored over 600 technical papers and numerous book chapters in the areas of distributed real-time computing and control, computer networking, fault-tolerant computing, and intelligent manufacturing. He has co-authored (jointly with C. M. Krishna) a textbook ``Real-Time Systems,'' McGraw Hill, 1997. He received the Outstanding IEEE Transactions on Automatic Control Paper Award in 1987, Research Excellence Award in 1989, Outstanding Achievement Award in 1999, Service Excellence Award in 2000, and Distinguished Faculty Achievement Award in 2001 from The University of Michigan. He also coauthored papers with his students which received the Best Student Paper Awards from the 1996 IEEE Real-Time Technology and Application Symposium, and the 2000 UNSENIX Technical Conference.
EMERALDS (Extensible Microkernel for Embedded, ReAL-time, Distributed Systems) is a real-time microkernel designed for small-memory embedded applications. These applications must run on slow (15-25MHz) processors with just 32-128 Kbytes of memory, either to keep production costs down in mass-produced systems or to keep weight and power consumption low. To be feasible for such applications, the OS must not only be small in size (less than 20 kbytes) but also have low-overhead kernel services. Unlike commercial embedded OSs which rely on carefully-optimized code to achieve efficiency, EMERALDS takes the approach of re-designing the basic OS services of task scheduling, synchronization, communication, and system call mechanism by using characteristics found in small-memory embedded systems such as small code size and a priori knowledge of task execution & communication patterns. With these new schemes, the overheads of various OS services are reduced 20-40% without compromising any OS functionality.
This work is done jointly with Khawar M. Zuberi and Babu Pillai.
In recent years, there has been a rapid and wide spread of non-traditional computing platforms, especially mobile and portable computing devices. As applications become increasingly sophisticated and processing power increases, the most serious limitation on these devices is the available battery life. Dynamic Voltage Scaling (DVS) has been a key technique in exploiting the hardware characteristics of processors to reduce energy dissipation by lowering the supply voltage and operating frequency. The DVS algorithms are shown to be able to make dramatic energy savings while providing the necessary peak computation power in general-purpose systems. However, for a large class of applications in embedded real-time systems like cellular phones and camcorders, the variable operating frequency interferes with their deadline guarantee mechanisms, and DVS in this context, despite its growing importance, is largely overlooked/under-developed. To provide real-time guarantees, DVS must consider deadlines and periodicity of real-time tasks, requiring integration with the real-time scheduler. In this talk, we present a class of novel algorithms called the real-time DVS (RT-DVS) that modify the OS's real-time scheduler and task management service to provide significant energy savings while maintaining real-time deadline guarantees. We show through simulations and a working prototype implementation that these RT-DVS algorithms closely approach the theoretical lower bound on energy consumption, and can easily reduce energy consumption 20% to 40% in an embedded real-time system.
This is joint work with Padmanabhan Pillai.
Communication in real-time systems has to be predictable, because unpredictable delays in the delivery of messages can adversely affect the execution of tasks dependent on these messages.
This talk will deal with the problem of providing predictable fault-tolerant inter-process communication in real-time systems with (partially connected) point-to-point networks, which provides guarantees on the maximum delivery time for messages. For the real-time part, we will detail the concept of a real-time channel, a unidirectional connection between source and destination. A real-time channel has parameters which describe the performance requirements of the source--destination communication, e.g., from a sensor station to a control site. Once such a channel is established, the communications subsystem guarantees that these performance requirements will be met.
For the fault-tolerant part, this talk will detail a scheme for restoring real-time channels, each with guaranteed timeliness, from component failures in multi-hop networks. To ensure fast/guaranteed recovery, backup channels are set up a priori in addition to each primary channel. That is, a dependable real-time connection consists of a primary channel and one or more backup channels. If a primary channel fails, one of its backup channels is activated to become a new primary channel. I will describe a protocol which provides an integrated solution to the failure-recovery problem (i.e., channel switching, resource re-allocation, etc.).
This is joint work with S.-J. Han
How to control hand-off drops is a very important Quality-of-Service (QoS) issue in cellular networks since mobile users (1) expect to be able to maintain on-going sessions even during their hand-off from one cell to another, and (2) are expected to experience more frequent hand-offs as a result of the current trend of shrinking cell size. In order to keep the hand-off dropping probability below a pre-specified target value (thus providing a `probabilistic' QoS guarantee), we design and evaluate predictive and adaptive schemes for the bandwidth reservation for the existing connections' hand-offs and the admission control of new connections.
We first develop a method to estimate user mobility based on an aggregate history of hand-offs observed in each cell. This method is then used to predict (probabilistically) mobiles' directions and hand-off times in a cell. For each cell, the bandwidth to be reserved for hand-offs is calculated by estimating the total sum of fractional bandwidths of the expected hand-offs within a mobility-estimation time window. We also develop an algorithm that controls this window for efficient use of bandwidth and effective response to (1) time-varying traffic/mobility and (2) inaccuracy of mobility estimation. Three different admission-control schemes for new connection requests using this bandwidth reservation are proposed. Then, we evaluate the performance of the proposed schemes to show that they meet our design goal, and determine that one of the three is superior to the others.
This is joint work with S. Choi, D. Qiao, and j.-T. Chou