Performance evaluation of online call routing and admission control algorithms

We consider the problem of call routing and admission control in general topology networks. Given a network, a call request consists of an origin-destination pair, and a bandwidth requirement. For each request, the routing algorithm must find a path in the network satisfying the bandwidth requirement, and the admission control algorithm must decide whether or not to accept the call. If the call is to be accepted, the required bandwidth needs to be allocated on the path selected throughout the duration of the call. The goal of the admission control algorithm is to decide online which calls to accept, without prior knowledge of future calls, so as to maximize the network throughput over time. By using a large set of simulation experiments, we evaluate the performance of online admission control algorithms proposed by several researchers in the context of competitive worst-case analysis. We first analyze the behavior of the EXP algorithm proposed by Gawlick et. al .[25] We propose small variations to the admission control algorithm that each greatly reduce the unfairness of EXP on a dense commercial network topology, without affecting the throughput. Additionally, we conducted experiments on the recently proposed KPP algorithm. (Abstract shortened by UMI.