Congestion Prevention at Ingress Peering Links

This paper focuses on the problem of congested ingress interfaces in the case of peering agreement. For various reasons, in this case, it is not possible to increase the interface capacity. Therefore, traffic engineering is a good candidate to better balance load in ingress interfaces. Traffic can be redirected from the congested interface to another one thanks to specific BGP mechanisms. However, the problem of selecting which traffic to redirect can become quite difficult due to its combinatorial structure. Nonetheless, the problem, that we show to be NP-hard, can be tackled by exact approaches. We propose an Integer Linear Program (ILP) formulation which can be used, together with a solver, to obtain, within very short computing times, exact optimal solutions. The benefit of this approach is assessed by comparing its optimal results with a natural greedy heuristic algorithm that serves as a baseline solution. The results of both approaches, applied on instances collected from a real tier-1 transit network, show that the optimal exact approach allows to reduce the number of interfaces to reconfigure by up to 19% on average. More importantly, this exact approach is much more efficient in finding feasible solutions, whereas the greedy sometimes fails, and hence does not provide useful solutions to the network administrators.