Flow Correlation-Based Rerouting Method For Traffic Matrix Estimation

Traffic Matrix(TM)is key input information for many important network management operations,such as traffic engineering,load balancing,and network management.So to accurately measure TM has been attracting extensive attentions of the research communities.However,to directly measure all of flows in TM is typically a prohibitively expensive method due to the tremendous consumption,such as network bandwidth,storage capacity and processing time.Therefore,an alternative approach is to estimate TM by some network traffic informations,e.g.,the link load.In order to improve the accuracy of TM estimation,as much additional measurement information as possible is required beacuse the TM estimation problem is under-dertermined.Rerouting flows is one way to add additional measurement information.Since there is correlation between flows,if this correlation information is not taken into account when rerouting,it will lead to “redundant measurements”.The complete measurement process using the rerouting method requires multiple rounds of route deflection.The rerouting schemes of flows are mutually constrained due to restrictions,so the rerouting order of flows affects the total number of measured flows,which makes rounds interrelated.Based on the above problems,this paper takes the correlation among flows into consideration for avoiding “redundant measurements”,in order to maximize the total number of measured flows.The contributions of this paper are summarized as follows:(1)To avoid “redundant measurements”,this paper proposes the TM estimation method based on the single-round optimization model,taking into consideration the correlation among flows.For determining the single-round route deflection strategy,firstly,this paper constructs auxiliary tripartite graphs,then based on which the singleround measurement problem is modeled as a linear programming problem with weighted tripartite matching.(2)In order to improve the performance of the above model,a new model is put forward based on the principle of maximizing the rank-increasing,which ensures that each rerouted flow can effectively increase the rank of the solved set of equations.Since solving this model is a NP-hard problem,the heuristic algorithm is proposed to obtain an approximate solution of the model.(3)With the purpose of maximizing the total number of measured flows,the measurement strategy of multiple rounds is jointly optimized with a global perspective.First,the measurement process of consecutive multiple rounds is considered as a Markov decision process.Then,the optimization problem of the multi-round measurement strategy is mapped as a reinforcement learning model.Finally,this paper proposes a joint optimization estimation method combining reinforcement learning A3 C algorithm and the heuristic algorithm which is used as a reward function in the reinforcement learning model while avoiding “redundant measurements”.(4)The data from three real backbone network are utilized to validate the above TM estimation methods.The results show that all three methods proposed in this paper outperform the existing algorithms and can measure more flows.