Multi hour robust routing and fast load change detection for traffic engineering

Abstract

Traffic Engineering (TE) has become a challenging mechanism for network management and resources optimization due to the uncertainty and the difficulty to predict current traffic patterns. Recent works have proposed robust optimization techniques to cope with uncertain traffic, computing a stable routing configuration that is immune to demand variations within certain uncertainty set. However, using a single routing configuration for long-time periods can be highly inefficient. Even more, the presence of abnormal and malicious traffic has magnified the network operation problem, claiming for solutions which not only deal with traffic uncertainty but also allow to identify faulty traffic. In this paper, we propose two complementary methods to tackle both problems. Based on expected traffic patterns, we adapt the uncertainty set and build a multi-hour yet robust routing scheme that outperforms the stable approach. For the case of anomalous and unexpected traffic, we propose a fast anomaly detection/isolation algorithm which relies on a novel linear spline-based model of traffic demands to identify traffic problems and decide routing changes. This algorithm is optimal in the sense that it minimizes the decision delay for a given mean false alarm rate and false isolation probabilities. Both proposals are validated using real traffic data from two Internet backbone networks.