低速率流淘汰与d-Left散列相结合的大流检测算法

李春强; 董永强; 吴国新

doi:10.7544/issn1000-1239.2019.20170732

低速率流淘汰与d-Left散列相结合的大流检测算法

¹(东南大学计算机科学与工程学院南京 211189)
²(计算机网络和信息集成教育部重点实验室(东南大学) 南京 211189) (Lcq9432@163.com)

基金项目: 国家“八六三”高技术研究发展计划基金项目(2013AA013503)；国家自然科学基金项目(61272532)；赛尔网络下一代互联网技术创新项目(NGII20160407)

详细信息

中图分类号: TP393
计量
- 文章访问数: 925
- HTML全文浏览量: 0
- PDF下载量: 321
出版历程
- 发布日期: 2019-01-31

Elephant Flow Detection Algorithm Based on Lowest Rate Eviction Integrated with d-Left Hash

¹(School of Computer Science and Engineering, Southeast University, Nanjing 211189)
²(Key Laboratory of Computer Network and Information Integration (Southeast University), Ministry of Education, Nanjing 211189)

摘要

摘要: 网络中少量较高速率和较大数据量的流生成了网络的大部分流量；利用有限的存储空间有效地识别出这些数据流，对实施流量工程、缓解网络拥塞、改善网络传输具有非常重要的意义.随着网络技术的发展，传输链路的带宽容量和数据流的传输速率越来越高.具有高速报文转发能力的网络设备对数据流检测算法的处理提出了高的性能要求.将超过一定的数据量和传输速率的数据流定义为大流，提出了将低速流淘汰与d-Left散列表存储结构相结合的大流检测算法.为了满足高速网络传输的性能需求，使用d-Left散列表存储流检测的数据结构，将d-Left散列表的存储结构与流缓存替换相结合以实现高效的大流检测.通过低速率的淘汰,提高了检测算法的准确性.基于真实网络数据的测试结果表明：所提算法在相近的存储开销下保持了高的处理性能，其准确性优于LRU派生算法S-LRU和L-LRU以及CSS和WCSS检测算法.
- 大流检测 /
- d-Left 散列 /
- 传输速率 /
- 缓存替换 /
- 高速网络
Abstract: A small percentage of high rate large-sized flows consume most of the network bandwidth. It is of great significance to efficiently identify these flows for traffic engineering, so as to alleviate network congestion and improve network transport performance. With the development of network technology, the capacity of transmission links and the transfer rate of data flows become higher and higher. So the network equipment with high-speed packets forwarding capability put forward high performance requirements for flows identifying algorithms. The flows whose size and transmission rate both exceed certain thresholds are usually defined as elephant flows. In this paper, a novel algorithm is proposed for elephant flow detection, in which the data structure of flow entries is indexed by d-Left Hash table to meet the performance requirements of high speed packet processing. The proposed detection algorithm combines the d-Left Hash data structure with the eviction of low-rate flows’ entries in order to identify elephant flows efficiently. The accuracy of the proposed detection algorithm is improved by the eviction of low rate flows’ entries. Theoretical analysis is conducted to demonstrate the accuracy, performance and memory overhead of the proposed detection algorithm. Experimental results on real data sets show that the proposed algorithm outperforms CSS, WCSS, S-LRU and L-LRU algorithms in terms of accuracy and performance at comparable memory overhead.
- elephant flow detection /
- d-Left Hash /
- transmission rate /
- cache eviction /
- high speed networks

HTML全文

参考文献(0)

施引文献(18)

期刊类型引用(7)

1.	史涯晴，许山山，易明煜，简开宇. 基于协议模型的嵌入式软件接口测试数据生成. 陆军工程大学学报. 2024(05): 57-66 . 百度学术
2.	高冬梅，梅新奎，宿文玲，宋笑兵. 金融分布式接口自动化测试工具设计. 智能计算机与应用. 2023(01): 149-152+157 . 百度学术
3.	耿嘉祺，李鑫丽，祝小兰. 支持用例集并行测试的接口测试平台. 计算机系统应用. 2023(06): 91-98 . 百度学术
4.	雷建胜，苏晓，金明磊. 一种分布式可持续集成自动化测试平台. 计算机与现代化. 2020(04): 14-18 . 百度学术
5.	徐京京，马素霞，王海威. 一种面向多监测终端厂家服务的调用方法. 计算机与数字工程. 2020(04): 895-898 . 百度学术
6.	虞砺琨，左万娟，于倩，陈华南，黄晨. 基于数据模型的接口用例自动生成. 测控技术. 2020(07): 24-29 . 百度学术
7.	刘国庆，汪兴轩. 基于Charles录制会话的HTTP接口自动化测试框架设计与实现. 计算机应用与软件. 2019(06): 7-13 . 百度学术