TABLE OF CONTENTS We formulate a revenue-based single-resource allocation problem for multiple service classes. To fix ideas, the resource under management is the bandwidth on the link from the hosting facility network access router to the Internet POP, although our methods and results can be applied more generally. Classes i are distinguished by the bandwidth request A i and the rate R i they are willing to pay for the request. The system can decide to allocate all of the bandwidth or to reject the service request. There is no best-effort service class.
The optimal policy is achieved by discrete-time dynamic programming. Theoretical and simulation results based on actual HTTP trace logs concur with conventional wisdom that as resource usage approaches 100%, head room should be reserved for premium users. A greedy policy works well at low resource usage and in states when there are a large number of departures relative to arrivals, which suggests that one may simplify the implementation of dynamic programming policies by classifying states and applying class-based rules.
We also discuss the optimal off-line solution and report the revenue gap between on-line and off-line algorithms. Performance numbers from the off-line algorithm are not attainable in practice, but they provide the ceiling on those of the on-line algorithm. We found that the gap narrows as the service capacity increases.
The rest of this section is organized as follows. Section 10.2.1 develops the discrete-time dynamic programming framework for bandwidth allocation. Section 10.2.2 describes approximation...
