Performance analysis of periodic and concurrent data structure maintenance strategies for network servers

Three strategies for designing servers and maintaining their data structures are discussed: incremental maintenance, periodic maintenance, and concurrent maintenance. The authors study periodic and concurrent maintenance strategies analytically in order to gain more insight into the behavior of servers using these strategies and determine when and how the maintenance should be performed. For periodic maintenance, it is shown that there is a value of the period which minimizes the average response time, and a formula to compute this value analytically is derived. For concurrent maintenance, a formula for its average response time and the condition under which concurrent maintenance would be preferable to periodic maintenance is derived. The authors have conducted a series of experiments to compare the performance of different maintenance strategies. For the system considered in the experiment, periodic maintenance yields the best average response time, whereas concurrent maintenance gives the least standard deviation and the smallest maximum response time