Sharing Memory Optimally

Efficient design of service facilities, such as data or computer networks that meet random demands, often leads to the sharing of resources among users. Contention for the use of a resource results in queueing. The waiting room is a part of any such service facility. The number of accepted service requests per unit of time (throughput), or the fraction of the time the servers are busy (utilization), are often used as performance measures to compare designs. Most common models in queueing theory consider the design of the waiting rooms with the assumption that, although individual requests may differ from one another, they are statistically indistinguishable. However, there are several instances where available information allows us to classify the requests for service into different types. In such cases the design of the service facility not only involves the determination of an optimum size for the waiting room but also the rules of sharing it among the different types. Even with a fixed set of resources, the rules of sharing them can influence performance. In data networks (or computer networks) the "waiting room" consists of memory of one kind or another. Messages (jobs) destined for different locations (processors) sharing common storage is an important example of shared use of memory. Recently, Kleinrock and Kamoun have modeled such use of memory and computed the performance of various policies for managing the allocation of memory to several types of users. Decisions to accept or reject a demand for service were based on the number of waiting requests of each type. However, the optimal policy was not determined even in the case where there were only two types of users. We determine the structure of optimal policies for the model considered with three types of users. The optimal policy consists of limiting the number of waiting requests of each type, and reserving a part of the memory to each type.