Date: March 4, 1999
Time: Noon
Place: Wean Hall 8220
Speaker: Raj Rajkumar, Carnegie Mellon University
The QoS-based Resource Allocation Model
Abstract:
Perhaps no other term has been abused more in recent years than the term "quality of service". The "QoS" buzzword is used so broadly and widely in the networking, real-time and telecommunication worlds among others that it almost seems meaningless. In many cases, people use it to mean timeliness of response but also may want to imply other desirable attributes like freedom from jitter, reliable delivery, privacy, etc.
In Q-RAM, the service needs of an application are composed from multiple QoS dimensions such as audio sampling rate, video frame size and end-to-end latencies. In addition, applications (users) must assign utility values to operating points in this multi-dimensional QoS space. These utility functions seem to have a natural property of concavity where additional "quality" along one dimension adds more value with successively diminishing returns. Q-RAM maps these operating points to system resource demands, and allocates available system resources such that the global utility derived by all applications together is maximized. As its foundation, Q-RAM assumes the semantics of an underlying resource kernel which provides resource and timeliness guarantees.
In this talk, we will summarize some of the key results obtained so far. First, the Q-RAM problem of finding the optimal resource allocation to satisfy multiple QoS dimensions (at least one of which is dependent on another) is NP-hard. However, we have designed a polynomial algorithm which yields a solution within a provably fixed and short distance from the optimal allocation. The global resource allocation problem is further complicated by the fact that different alternatives can be used to satisfy one given operating QoS setpoint (e.g. consume CPU cycles to compress data but save on network bandwidth). This problem can be formulated as a mixed integer programming problem that can be solved efficiently to yield an optimal resource allocation. Finally, we also present the run-times of these optimizations to illustrate how these solutions can be applied in practice and perhaps in real-time. A discrete version of this problem has also recently been formulated and solved by a graduate student, Chen Lee, with very promising results.
This is joint work with Chen Lee, John Lehoczky and Dan Siewiorek carried out in coordination by the "Resource Kernel" and "Amaranth" projects under the DARPA Quorum program.
SDI / LCS Seminar Questions?
Karen Lindenfelser, 86716, or visit www.pdl.cmu.edu/SDI/