Scalable Bandwidth Optimization in Advance Reservation Networks

In this paper, we present an algorithm for continuous bandwidth optimization in networks supporting advance reservations such as Grid computing environments or QoS-aware MPLS networks. The need for such reoptimization arises when resources for incoming reservation requests are allocated using fast dynamic routing with simple path selection algorithms. Although this is often necessary to satisfy time constraints for answering reservation requests, it inevitably leads to network inefficiencies due to the fact that the resulting uneven load distribution leads to bottlenecks within the network. We propose a combination of fast online bandwidth reservation with background reoptimization which continuously frees up bandwidth for future time slots in order to allow the network to carry more traffic without adding further capacity. A combinatorial time-approximation scheme suitable for large networks will be used. In addition, we evaluate several performance metrics and show that a significant improvement in request admission rate and bandwidth utilization can be achieved under the proposed scheme.