When Systems Don't Scale: Avoiding Collapse in Congestion-Sensitive Processing Systems
David Alderson
Division of Engineering and Applied Science
California Institute of Technology
Thursday, November 18, 2004
12:00 - 1:15 PM
Terman Engineering Center, Room 453
Abstract:
In this talk, I will introduce a class of congestion-sensitive
processing systems in which the instantaneous output rate changes with
the total amount of work in the system. Specifically, we consider
systems that are susceptible to "congestion-induced collapse", in the
sense that their output rate tends toward zero as their system
workload gets large. We develop a sequence of models that allow us to
characterize key features of system behavior, and we identify
management policies that achieve optimal performance while preventing
collapse. In particular, we develop stochastic models that show
collapse in these systems is unavoidable unless one can impose
admission control on newly arriving work. We prove that the optimal
admission policy is a non-randomized threshold policy, and we solve
for the threshold that maximizes system reward. This type of
congestion-sensitive behavior is relevant to a variety of
applications, including computer networking, telecommunications, and
transportation systems.
Operations Research Colloquia: http://or.stanford.edu/oras_seminars.html