Adaptive and Low-cost Traffic Engineering based on Traffic Matrix Classification

Traffic engineering (TE) attracts extensive researches over the years. Operators expect to design a TE scheme which accommodates traffic dynamics well and achieves good TE performance with little overhead. Some approaches like oblivious routing compute an optimal static routing based on a large traffic matrix (TM) range, which usually leads to much performance loss. Many approaches compute routings based on one or a few representative TMs obtained from observed historical TMs. However, they may suffer performance degradation for unexpected TMs and usually induce much overhead of system operating. In this paper, we propose ALTE, an adaptive and low-cost TE scheme based on TM classification. We develop a novel clustering algorithm to properly group a set of historical TMs into several clusters and compute a candidate routing for each TM cluster. A machine learning classifier is trained to infer the proper candidate routing online based on the features extracted from some easily measured statistics. We implement a system prototype of ALTE and do extensive simulations and experiments using both real and synthetic traffic traces. The results show that ALTE achieves near-optimal performance for dynamic traffic and introduces small overhead of routing updates.