|
Advances in the networking and computing technology have led to emergence of diverse applications and system
platforms, encompassing multimedia, virtual machine appliances, and network systems. Traditional systems lack
sufficient control over the scheduling and management of different system resources for these modern applications
to obtain their required Qualify-of-Service(QoS). The goal of my research is to derive better solutions to resource
management of systems and applications, to improve their overall QoS.
To date, my research mainly focuses on the resource management in soft real-time systems, virtual machine
systems, and Internet end-systems, though my interest spreads to all areas of computer systems. More specifically,
I have engaged in the design and development of new scheduling algorithms and feedback-based control mech-
anisms to provide some specific QoS such as delay, loss rate, bandwidth and fairness, for different systems. My
research is conducted through both theoretic analysis and empirical evaluation. I believe that building real systems
is critical in systems research. Previous work experience in VMware Inc., Intel China Research Center and Linx
Co. also helped me become aware of industry standards and trends, while appreciating both research and product
development.
The use of commercial off-the-shelf (COTS) systems, such as Linux, is gaining popularity in real-time and em-
bedded computing environments because they can reduce development and maintenance cost as well as providing
a common code-base. Interrupt handling is a main issue in COTS to support real-time service. RTLinux free, for
example, provides hard deadline guarantees by deferring all interrupts that do not have real-time handlers. This
solution requires separated real-time interrupt handlers, preventing the direct usage of legacy device driver, and
might also cause unbounded delay for standard Linux kernel.
My current research work with Prof. West explored the effect of I/O interrupts on process scheduling in COTS
systems, and proposed a new approach, Unified Scheduling and Accounting for I/O Interrupts and Processes
(USAIP), to provide more predictable service without introducing a separate real-time layer. This work targeted
two significant unsolved problems: 1) how to cooperatively schedule interrupts and processes so that predictable
service is guaranteed; 2) how to properly charge interrupt service time to the corresponding process, instead of an
arbitrary process that was active at the time the interrupt occurred. The basic idea is that I/O interrupts should be
scheduled and accounted, where possible, on behalf of the processes that request them. However, the challenge
is that such processes are usually unknown before the completion of interrupt handling. This work proposed a
simple prediction scheme to identify the corresponding processes. The experiments results showed the significant
improvements in predictability of a modified Linux system with the prototype implementation of USAIP.
As ongoing work, I proposed several other prediction schemes to derive the priority of interrupt handling. I
also developed an analytic scheduling model to show the real-time properties of this new approach in terms of
deadline misses and delays. Currently I am extending the prototype implementation to support SMP, while at the
same time evaluating its performance. I am also investigating how the proposed framework can improve fairness
besides providing real-time service. Another interesting direction is to apply this work to virtual machine systems
to provide real-time service.
Streaming multimedia applications such as live webcasts and interactive distance learning require real-time con-
straints for the data capture and transmission in keeping with end-user QoS requirements. Meanwhile, they can
also tolerate some packets being discarded or serviced late, as long as the consecutive number of such packets
is limited. Likewise, other soft real-time applications, such as data generation applications in sensor networks
and in embedded systems, also have similar delay and loss constraints. Window-constrained scheduling model
was proposed by West et al to guarantee a fraction of service in every infinite time window for above classes of
applications.
My Ph.D thesis work supervised by Prof. West extended the window-constrained scheduling model and previ-
ous Dynamic Window-Constrained Scheduling (DWCS) algorithm. While DWCS is capable of generating
a feasible window-constrained schedule that utilizes 100% of resources, it requires all jobs to have the same request
periods and some specific window-constraints. This work proposed a new algorithm, Virtual Deadline Scheduling
(VDS), which provides better window-constrained service guarantees to jobs, especially to those with
potentially different request periods. By dynamically adjusting their virtual deadlines based on their
current service, VDS maximizes resource utilization while limiting the extent of delay and loss. The
performance was evaluated by extensive simulations, and also by experiments in Linux kernel, where window-constrained
scheduling algorithms such as DWCS and VDS are implemented as both CPU scheduler and packet scheduler.
Based on VDS algorithm, I developed the Multi-hop Virtual Deadline Scheduling (MVDS) algorithm to pro-
vide end-to-end window-constraint guarantees. MVDS exploits the cooperation between hops by using a local
virtual deadline based priority scheme and a utilization-based probabilistic drop scheme. Results from the NS sim-
ulator show that MVDS can provide better window-constrained service guarantees than other related algorithms,
while still maintaining high link utilization.
Previous window-constrained scheduling models assume job instances are independent and homogeneous.
However, it may not be true in real systems. As ongoing work, I am developing a dependency-aware schedul-
ing approach for MPEG video streaming to provide better QoS. This work involves a study of the relationship
between different types of frames.
The increased use of "Virtual Machines" (VMs) as an architecture promotes safety and security to applications
running on the same host through isolation, and thus enabled services, possibly deployed by untrusted sources,
to be injected into a third party hosting infrastructure. However, this does not mitigate the challenge of ensuring
efficient and fair use of underlying resources.
My research work on Friendly VM (FVM) project with Prof. Bestavros et al is aimed at this challenge.
Using self-adaptation in the VMs themselves based on feedback about resource usage and availability, the FVM
framework enables each VM to adjust its demand for system resource in order to achieve efficiency and fairness.
Meanwhile, it does not make any assumptions about the underlying resources nor about the requirements of FVMs
competing for these resources. The analytic, control-theoretic model of FVM adaptation shows the convergence
and fairness properties. I also implemented a prototype in User-Mode Linux (UML), and the experimental results
confirm its performance beneifits.
While the FVM framework enables the design complexity of the underlying hosting systems to be significantly
reduced, the current prototype implementation was built on top of a fairly complex host OS (Linux). The applica-
bility and implementation on other virtual machine systems such as Xen is currently under investigation.
Adaptation mechanisms have been widely used in Internet services to respond to the dynamic and unpredictable
change of Internet traffic, in order to provide service guarantees. I participated in designing an adaptation frame-
work using elastic TCP-based tunnels to provide soft bandwidth guarantees over best effort IP architecture,
without any modifications to core routers. Our approach enables two edge routers to use an adaptive number of
TCP connections to set up a tunnel of desirable bandwidth between them.
Though various adaptation mechanisms in Internet End-systems have been heavily investigated for efficiency
and scalability purposes, security implications have been neglected by system designers. In collaboration with
Guirguis et al, we exposed adversarial exploits of the adaptation dynamics to Reduction of Quality (RoQ) attack
, which could induce significant inefficiencies or reduce the service quality of end-systems, without resorting
to brute-force Denial-of-Service(DoS). We instantiate our approach for the adaptation mechanisms used in the
admission controllers and load balancers in web servers, and validate the effect of RoQ exploits on those
optimization systems.
My long term research goal is to develop and maintain an internationally recognized research program in the
general area of system resource management, focusing on developing new techniques to provide better QoS and
security with less complexity for applications in real-time communication systems, embedded systems, virtual
machines and network systems. In the short term, I plan to proceed my research along the following directions
based on my current research results and experience. Besides, I would also like to have opportunity to collaborate
with colleagues and researchers in the community to work on other potential interesting topics.
Based on my current research, I would like to develop a comprehensive scheduling framework for both interrupts
and processes to support soft real-time applications on COTS systems. Specifically, I would like to analyze and
evaluate the performance of the USAIP framework integrated with other real-time scheduling algorithms such
as window-constrained algorithms. Meanwhile, I am interested in generalizing the current window-constrained
model with heterogeneous and dependent jobs. I also want to investigate the composition problem of resource,
time, loss and security properties in this scheduling framework. Moreover, I would like to experimentally validate
the framework with the implementations in different real-time systems, such as multimedia systems, embedded
systems and sensor networks. Furthermore, I am very interested in extending this framework on virtual machine
systems to provide real-time service.
To date, the FVM framework has been implemented and studied on a single host. I plan to investigate the ap-
plicability of this framework to the infrastructures in which resources are distributed, such as clustering virtual
machines. With consideration of hot migrating of VMs between different physical hosts, I would like to develop
an adaptive resource management framework to dynamically balance the resources between VMs as well as bal-
ance the load among the underneath hosts in the cluster.