CAM01-3: Connection Preemption in Multi-Class Networks

We address the problem of connection preemption in a multi-class network environment. Our objective is: (i) to minimize the number of preempted connections, and (ii) to minimize the total preempted bandwidth, in that order. We show that this problem is NP-complete by reducing it to a well-known NP complete problem - the subset sum problem. Therefore, a known polynomial time algorithm, such as Minn.Conn [1], to solve this problem is suboptimal. We present an optimal algorithm with exponential complexity that can be used when the network load is light. We also present a fully polynomial time approximation algorithm that performs within a bounded factor from the optimal, and can be used in large networks having thousands of connections. We compare the performance of exact and approximate algorithms in a practical scenario by conducting simulations on a network representing twenty largest metros in the U.S. The simulations show that, on average, the approximate algorithm preempts bandwidth which is only a small fraction more as compared to that preempted by the exact algorithm, but is an order of magnitude more efficient in terms of execution time.