Dynamic storage allocation with known durations

This paper is concerned with a new version of on-line storage allocation in which the durations of all processes are known at their arrival time. This version of the problem is motivated by applications in communication networks and has not been studied previously. We provide an on-line algorithm for the problem with a competitive ratio of O(min{log Δ,log τ}), where Δ is the ratio between the longest and shortest duration of a process, and τ is the maximum number of concurrent active processes that have different durations. For the special case where all durations are powers of two, the competitive ratio achieved is O(loglog Δ).     

Bandwidth allocation for guaranteed versus best effort service categories

Modern communication networks evolve towards integration of guaranteed-performance and best-effort service types. The coexistence of these two service types offers substantial benefits, such as resource sharing between service classes, and the ability of the user to select an appropriate service class according to its individual requirements and preferences. Notwithstanding, such interaction gives rise to more complicated system behavior and related performance issues, which need to be explored and understood in order to allow efficient network operation. In this paper we examine potential congestion phenomena, which arise due to the combined effect of bandwidth sharing and user migration between service classes. We propose a simplified fluid model for session flow, consisting of two coupled queues with state-dependent flows, which captures the essential ingredients of service-class interaction. Our analysis shows that the system might exhibit bistable behavior, in the sense that transient congestion may stir the system from a stable and efficient operating point to an inefficient and congested one. We identify conditions which give rise to bistability, and propose a call admission control scheme which prevents the system from getting trapped in a congested-type equilibrium, while not interfering with normal system operation. This revised version was published online in June 2006 with corrections to the Cover Date.