SCS Undergraduate Thesis Topics

2005-2006
Student Advisor(s) Thesis Topic
Gwen Stockman Mor Harchol-Balter/Adam Wierman The Impact of Abandonment in Multi-Class Priority Queues

Scheduling in web applications has been successful and is an important technique used for improving the performance of web servers, routers, and other web applications. Many applications of different scheduling policies have been studied, such as time-sharing, and size-based policies, however most studies have assumed that users are infinitely patient. This is not true in practice, where congestion leads to user frustration, and eventual abandonment (such as hitting the reload button where opening a website). Abandonment may cause problems for many scheduling policies, because when a job abandons, any work performed on it so far is lost (wasted). If abandonment is controlled then less service will be wasted, and jobs that complete will have lower response times. Abandonment is typically dealt with using admission control, by allowing a maximum number of jobs in the system at a given time, and rejecting any jobs that arrive while the system is full.

Even in simple queuing models analyzing the effects of abandonment is difficult under many scheduling policies. As a result we limit our focus to m-class priority queues and develop simple approximations that characterize the effects on performance of abandonment both with and without admission control. In addition to mathematical analysis, we are using simulation to validate the accuracy of these approximations.


Close this window