Algorithm For Detecting Large Flows Based On Self-Adaptive Decay And Compensation

Detecting large flows is a very important task in network measurement.It has great significance for network operation,billing,network congestion control and other applications.However,with the explosive growth of network traffic and the fast transmission speed of network packets,network measurement faces a huge challenge.To improve the speed of large flow detection,the module for large flow detection is usually placed in on-chip memory,but on-chip memory has limited space and needs to hold other modules.This means that the space left for the large flow detection is very small.This poses a challenge to the existing algorithms of large flow detection in terms of memory consumption.this thesis proposes an accurate and efficient algorithm SDC(Self-adaptive Decay and Compensation).Compared with existing algorithms,SDC detects large flows with higher accuracy while consuming the same memory consumption.This is because the algorithm uses two key strategies to detect large flows,namely the self-adaptive decay strategy and the compensation strategy.Both strategies rely on the storage structure of SDC,which records the label,counter value,and number of negative votes of candidate large flows.Self-adaptive decay strategy calculates the decay probability with the counter value and the number of negative votes of the candidate large flows.The strategy protects large flows and evicts small flows by control decay probabilities.When the candidate large flows are larger,the decay probabilities are smaller,thus achieving the purpose of protecting the large flows.When the number of negative votes is larger,the decay probability is also larger.For a small flow,its number of negative votes can easily exceed its counter value,so the small flow will be easily evicted.Decay causes the count of candidate large flows to be less than its true length.For the loss of length of the candidate large flows,we propose a compensation strategy.The strategy estimates the average amount of loss of candidate large flows and compensates it to that candidate large flows.This ensures that the estimated length of candidate large flows is closer to the true length,thus further improving the accuracy of the algorithm in detecting large flows.This thesis makes theoretical analyses of the error bound of estimated length of flows,time consumption and space consumption of SDC algorithm.Moreover,a lot of experiments based on the real network traces have also been done.The experimental results show that SDC algorithm performs well in terms of average relative error,detection precision and recall rate.