Bandwidth packing

We model a server that allocates varying amounts of bandwidth to "customers" during service. Customers could be computer jobs with demands for storage bandwidth or they could be calls with demands for transmission bandwidth on a network link. Service times are constants, each normalized to 1 time unit, and the system operates in discrete time, with packing (scheduling) decisions made only at integer times. Demands for bandwidths are for fractions of the total available and are limited to the discrete set {1/k, 2/k, . . . , 1} where k is a given parameter. More than one customer can be served at a time, but the total bandwidth allocated to the customers in service must be at most the total available. Customers arrive in k flows and join a queue. The j th flow has rate λ_j and contains just those customers with bandwidth demands j/k. We study the performance of the two packing algorithms First Fit and Best Fit, both allocating bandwidth by a greedy rule, the first scanning the queue in arrival order and the second scanning the queue in decreasing order of bandwidth demand. We determine necessary and sufficient conditions for stability of the system under the two packing rules. The average total bandwidth demand of the arrivals in a time slot must be less than 1 for stability under any packing rule, i.e., the condition equation presented must hold. We prove that if the arrival rates λ₁, . . . , λ_k-1 are symmetric, i.e., λ_i = λ_k-i for all i, 1 ≤ i ≤ k-1, then p < 1 is also sufficient for stability under both rules. Our Best Fit result strengthens an earlier result confined to Poisson flows and equal rates λ₁ = ⋯ = λ_k-1, and does so using a far simper proof. Our First Fit result is completely new. The work here extends earlier results on bandwidth packing in multimedia communication systems, on storage allocation in computer systems, and on message transmission along slotted communication channels. It is not surprising that ρ < 1 is sufficient under Best Fit, since in a congested system, Best Fit tends to serve two complementary (matched) customers in each time slot, with bandwidth demands being i/k and (k - i)/k for some i, 1 ≤ i ≤ k - 1. It is not so obvious, however, that ρ < 1 is also sufficient under First Fit. Interestingly, when the system becomes congested, First Fit exhibits a "self-organizing" property whereby an ordering of the queue by time of arrival becomes approximately the same as an ordering by decreasing bandwidth demand.