A dynamic study of providing quality of service using preemption policies with random selection

Bandwidth allocation is a fundamental problem in communication networks, especially where bandwidth is reserved for requests to guarantee a certain quality of service (QoS). Connection preemption, coupled with the capability to reroute connections, provides available and reliable services to high-priority connections when a network is heavily loaded and connection request arrival patterns are unknown, or when the network experiences transient overloads or faults that reduce the available capacity or routes. Preemption becomes more a more attractive strategy in a differentiated services scenario, especially when using DiffServ-aware traffic engineering approach. However, the complexity of such connection preemption algorithms is a very important performance criterion for implementation in real networks. In this paper, we analyze two simple and efficient preemption policies with random selection and examine their performance in a dynamic setting. To compare the dynamic performance of the new algorithms to the existing ones, we conduct complexity analysis and simulation studies.