Research On Accurate Measurement Methods Of Elephant Flows For High-Speed Network Traffic

As an essential task in network measurement,Top-k flow identification or elephant flow identification is fundamental to network management and network quality control,providing indispensable support for load balancing,route scheduling,instruction detection,flow table caching,traffic engineering,network performance diagnosis and strategy implementation,etc.However,with the rapid expansion of network traffic and the limitation of hardware devices,the existing identifying algorithms have been unable to achieve high accuracy and low space overhead in the meantime.Thus,this paper mainly studies the accurate identification of Top-k flows and elephant flows,aiming to achieve high identification accuracy with low space overhead.The main research work and innovations are summarized as follows:(1)In terms of accurately identifying Top-k flows,this paper utilizes the idea of filtering mice flows before monitoring elephant flows to construct a high-precision Top-k flow identification architecture,which contains mice flow filter and elephant flow monitoring table.To solve the problem that traditional filters tend to fail due to the gradual overflow of their fixed counters,this paper designs an adaptive update mice flow filter based on the data structure sketch.The filter uses two counters to record the number of packets arriving in the current period and the recent period,and the counters are updated by a half-count update strategy to continuously and effectively filter mice flows.Further,this paper devises an elephant flow monitor and designs a hash algorithm to provide multiple storage locations for each flow,and adopts the voting idea to replace mice flows,so as to accurately and efficiently identify Top-k flows.The experimental results show that the proposed method achieves above 0.99 precision with low memory overhead in identifying Top-k flows.(2)In terms of accurately identifying elephant flows,this paper constructs an elephant flow identification architecture including pyramid filter and elephant flow monitoring table.The pyramid filter is composed of multi-layer counter arrays,where the underlying counters use a flag to record whether flows in the current and adjacent periods reach the threshold,and the filter can initially select elephant flows via the flag.Moreover,the high-level counters record the size of all flows by counter sharing to further filter mice flows.The elephant flow monitoring table,which is based on hash table and linked list,stores the constantly arriving elephant flows by the scalable linked list nodes,and provides multiple alternative storage locations for each flow through repositioning strategy.Meanwhile,the elephant flow monitoring table uses the probabilistic replacement strategy to evict mice flows to efficiently and accurately track elephant flows.The experimental results show that the proposed method can rightly identify 98%of elephant flows in network traffic,and achieve higher accuracy and lower error rate with the same memory size than the state-of-the-art.