The Optimal Connection Preemption Algorithm in a Multi-Class Network
Conference Paper
Overview
Identity
Additional Document Info
Other
View All
Overview
abstract
In an integrated network in which multiple classes with different priorities exist, when the network does not have enough unused bandwidth, the connection preemption algorithms (CPA) play an important role in accepting a new session with a high priority by preempting the already admitted flows of the lower priorities. Although there are lots of studies about which connections to preempt to optimize the preemption factors (the priority of connections, the bandwidth to be preempted, and the number of connections to be preempted), the existing CPAs are only suboptimal in the viewpoint of the preemption factors because of the computational complexity. The connection preemption problem in a centralized fashion is proved to be NP-complete. To avoid the complexity of the centralized scheme, the decentralized/distributed algorithms are proposed. However their solutions are optimal only at the hop level. In order to avoid the priority order problem and to minimize the number of preempted and rerouted sessions, we propose to order the priority of the preemption factors in a new way. We also propose an optimal connection preemption algorithm which optimizes the newly ordered preemption factors in the connection preemption events. The proposed algorithm is the first optimal algorithm that provides a guideline about the upper bound of the computational complexity of the optimal CPAs.
name of conference
2002 IEEE International Conference on Communications. Conference Proceedings. ICC 2002 (Cat. No.02CH37333)
