Buffer Management as Inventory Control

Abstract

We consider computer subsystems that use buffering as a mechanism to enhance communication performance between two or more components exhibiting a short-term speed mismatch. Often, a fixed size buffer is inserted in such a communication path since it can improve performance by dampening speed variations. We formalize this buffer management problem within the framework of inventory control theory. We show that among all admissible policies for controlling such communications, the structure of the optimal one is analogous to the reorder point/order up to level policy that arises in the single commodity, continuous review, inventory control problem. This confirms the appropriateness of the intuitive and often-used high water mark/low water mark policy for buffer management. Given this policy structure, we derive expressions for the optimal parameter values. We discuss extensions of these results whereby policy parameters are dynamically estimated based on current observations of the communication characteristics. An algorithm to generate the optimal ordering decisions (and resulting costs) when communication patterns are known a priori is developed as a useful benchmark for evaluating the goodness of on-line policies.