Bandwidth allocation is a fundamental problem in the design of networks whe
re bandwidth has to be reserved for connections in advance. The problem is
intensified when the overall requested bandwidth exceeds the capacity and n
ot all requests can be served. Furthermore, acceptance/rejection decisions
regarding connections have to be made online, without knowledge of future r
equests. We show that the ability to preempt (i.e., abort) connections whil
e in service in order to schedule "more valuable" connections substantially
improves the throughput of some networks. We present bandwidth allocation
strategies that use preemption and show that they achieve constant competit
iveness with respect to the throughput, given that any single call requests
at most a constant fraction of the bandwidth. Our results should be contra
sted with recent works showing that nonpreemptive strategies have at most i
nverse logarithmic competitiveness.