Characterize the minimum required resources for admission control of pre-recorded VBR video transmission by an O(n log n) algorithm

Given a pre-recorded VBR video, we have proposed an O(n) algorithm to smooth the transmission schedule with the minimum required resources. N is the number of video frames. As n is usually very large and varying for different videos, it is not suitable for online computation. To facilitate resource management and admission control for QoS (quality-of-service) guarantees, we need to explore the relations among the required resources. Thus, whenever a new request is presented, the admission control procedure can easily check the required resources against the available resources and decides to admit this new request or not. To compute these relations (such as rate-buffer and rate-delay), a native algorithm takes O(n³) time complexity. An O(n log n) algorithm is proposed to characterize the low-bounds of resources allocated for transmitting a pre-recorded VBR video. Having these pre-computed functions, the admission control procedure is as simple as a chart look-up with O(1) time complexity to allocate the required resources