Data Structure for a Time-Based Bandwidth Reservations Problem

2003/02/06 by Andrej Brodnik, Andreas Nilsson, Brodnik, Andrej +1
Computer Science · #C.2.3 #Data Structures and Algorithms (cs.DS) #E.1 #FOS: Computer and information sciences #Networking and Internet Architecture (cs.NI) #cs.DS #cs.NI

paper · pdf · doi:10.48550/arxiv.cs/0302009

arxiv created 2003/02/06 · arxiv updated 2009/11/30

Abstract

We discuss a problem of handling resource reservations. The resource can be reserved for some time, it can be freed or it can be queried what is the largest amount of reserved resource during a time interval. We show that the problem has a lower bound of Ω(log n) per operation on average and we give a matching upper bound algorithm. Our solution also solves a dynamic version of the related problems of a prefix sum and a partial sum.

Related

• Static Data Structure for Discrete Advance Bandwidth Reservations on the Internet
• Dynamic Allocation of Reusable Resources: Logarithmic Regret in Overloaded Networks
• A Flexible Bandwidth Reservation Framework for Bulk Data Transfers in\n Grid Networks
• Sequential Resource Access: Theory and Algorithm
• A Distributed Method for Optimal Capacity Reservation