Bandwidth allocation is a fundamental problem in communication networks where bandwidth needs to be reserved for requests (connections) to guarantee a certain quality of service (QoS) for the request. Guaranteeing QoS to the request means that the user can explicitly speclfy certain requirements for a request such as bandwidth. The problem of bandwidth allocation is further intensified when the requested bandwidth exceeds the available unused bandwidth and so not all requests can be completely served. This research examines on-line bandwidth allocation, where the decision for acceptance or rejection of the request has to be made when future requests and their arrival statistics are not known. A request can be defined as a flow of information fiom a source to a destination with a certain amount of bandwidth, a priority level, a utility fbnction that is based on the bandwidth received, and a worth that is based on the utility function and the priority level. The goal of the research is to develop a scheduling heuristic for an overloaded system that attempts to schedule the requests such that the sum of the worths of the requests satisfied in a fixed interval of time is the maximum. The scheduling heuristic can preempt or degrade already scheduled requests. Three different types of utility functions, step, linear, and concave are examined. Other parameters being considered include network loading and the relative weights of the different priority levels.

Date of this Version

July 2000