A Computational Complexity-Aware Model for Performance Analysis of Software Servers

Queueing models are routinely used to analyze the per-formance of software systems. However, contrary to com-mon assumptions, the time that a software server takes to complete jobs may depend on the total number of active sessions in the server. In this paper, we present a queueing model that explicitly takes into account the time, taken by al-gorithms in the server, that varies with the user population. The model analytically predicts response time and “satura-tion number ” of such systems. We validate our model with simulation and further demonstrate its usefulness by sug-gesting a heuristic technique to “discover ” the complexity of algorithms in server software, solely from response time measurement. We applied the discovery technique to a Web-server test-bed, and found that we can identify the asymp-totic behavior of processing time as a function of the user population with a fair amount of accuracy. The results show that this promises to be one of the many “black-box analy-sis ” techniques, often found necessary in the real world. 1