Time Slot Groups - A Data Structure for QoS-Constrained Advance Bandwidth Reservation and Admission Control

In this paper we present Time Slot Groups (TSG), a novel, efficient data structure for QoS-constrained advance bandwidth reservation and admission control. The data structure divides the time horizon into T equally sized time slots and can be used for serving efficiently complex bandwidth reservation requests specifying the duration of the reservation, the minimum required bandwidth, the earliest possible starting time and the latest possible finish time. The data structure supports reservation queries in time O(k+(T/k)* log(k)) and reservation updates in time O(k+(T/k)), where k is a user-defined parameter.