基于LRU 的大流检测算法A LRU Based Algorithm for Identifying and.pdf

第29 卷第10 期 电 子 与 信 息 学 报 Vol.29No.10 2007 年10 月 Journal of Electronics Information Technology Oct. .2007 基于LRU 的大流检测算法 王洪波 裴育杰 林 宇 程时端 金跃辉 (北京邮电大学网络与交换技术国家重点实验室 北京 100876) 摘 要：高速网络中，检测大流是进行准确流量测量的一种重要可扩展解决方案。该文提出了一种新的基于 LRU 大流检测算法。它通过引入“小流早期丢弃”和“大流预保护”机制以提高测量准确性。算法分析表明：新算法具 有10Gbps 线速处理能力。该文基于实际互联网数据进行了实验比较，结果显示：与已有算法相比，新算法具有更 高的测量准确性和实用性。 关键词：流量测量；大流；重尾分布；最近最久未使用 中图分类号：TP393.06 文献标识码：A 文章编号：1009-5896(2007)10-2487-06 A LRU Based Algorithm for Identifying and Measuring Large Flows Wang Hong-bo Pei Yu-jie Lin Yu Cheng Shi-duan Jin Yue-hui (State Key Laboratory of Networking and Switching, Beijing University of Posts Telecommunications, Beijing 100876, China) Abstract: Identifying and measuring large flows is an important scalable solution for traffic measuring accurately on high-speed networks. A new algorithm based on LRU replacement scheme is proposed, which uses the policies of “early dropping small flows” and “preparatively protecting large flows” to enhance the accuracy of traffic measurement. An analysis demonstrates that the new algorithm can support the 10Gbps line-speed processing. Experiments are also conducted based on real network traces. Results show that the proposed method is more accurate and practicable than existing algorithms. Key words: Traffic measurement; Large flows; Heavy tailed distribution; Least Recently Used (LRU) 1 引言 的流量。例如，文献[2]中结果显示：9 ％的自治域(AS)间的 互联网中，流量测量(traffic measurement)是网络监测、 字节流量占所有自治域间流量的90％。事实上，对许多应用 控制和管理的基础。测得的流量信息可用于网络计费 来说只获取大流的流量信息就能满足需求。例如，在计费应 (network accounting)、流量工程(traffic engineering)、拒绝 用中，基于使用量计费和基于时间计费是常用的两种计费方