面向智能路由的多级哈希网络数据存储结构

doi:10.11959/j.issn.1000-0801.2020287

电信科学 ›› 2020, Vol. 36 ›› Issue (10): 67-78.doi: 10.11959/j.issn.1000-0801.2020287

面向智能路由的多级哈希网络数据存储结构

朱峰¹,黄群²

¹ 中国科学院计算技术研究所，北京100190
² 北京大学，北京 100871

修回日期:2020-10-10 出版日期:2020-10-20 发布日期:2020-11-07
作者简介:朱峰（1993- ），男，中国科学院计算技术研究所先进计算机系统研究中心工程师，主要研究方向为网络测量系统|黄群（1988- ），男，博士，北京大学计算机科学技术系研究员、博士生导师，2020年获工业和信息化部中国电子学会“中国优秀科学工作者”称号。主要研究方向为网络与分布式系统
基金资助:
国家重点研发计划项目(2019YFB1802600);国家自然科学基金资助项目(61802365)

Multi-stage hashing network storage structure for intelligent routing

Feng ZHU¹,Qun HUANG²

¹ Institute of Computing Technology,Chinese Academy of Sciences,Beijing 100190,China
² Peking University,Beijing 100871,China

Revised:2020-10-10 Online:2020-10-20 Published:2020-11-07
Supported by:
The National Key Research and Development Program of China(2019YFB1802600);The National Natural Science Foundation of China(61802365)

摘要/Abstract

摘要：

网络数据的采集和存储是智能路由控制的基础，为智能路由提供了大量的网络流量数据进行模型训练和决策。然而，作为网络数据存储系统中的核心设备，交换机的存储空间非常有限，且设计灵活性低，无法满足智能路由控制对全面高精度的数据存储和轻量级存储系统的需求，进而影响智能路由控制的效果。提出一种面向智能路由控制的多级哈希网络数据存储结构，高效利用交换机有限的存储空间，实现低碰撞率的网络数据存储。该结构通过多级哈希表增加数据的可存储空间数量，从而降低存储冲突率并提高存储空间利用率。同时，该结构使用基于低开销时间戳的LRU算法解决哈希冲突：在发生哈希冲突时总是保存最新的网络数据，清除陈旧数据，以尽可能减少后续的存储冲突。基于真实网络流量数据的实验证明了相比目前普遍使用的单级哈希存储结构，多级哈希存储结构在存储碰撞率和负载率两方面存在显著的性能优势。

关键词: 智能路由, 存储结构, 多级哈希, LRU

Abstract:

Network data collection and storage are fundamental for intelligent routing control,providing massive flow data for model training and decision-making.However,as the key device in network storage system,switches have very limited memory size and design flexibility,which can’t satisfy the needs of intelligent routing control for comprehensive high-precision data and lightweight storage system,thus reducing the effectiveness of intelligent routing control.A multi-stage hashing network storage structure (MHNSS) was proposed for intelligent routing control,which fully utilized the limited memory resource of switch and completed network data storage with low collision rate.The number of candidate buckets of the flow key was augmented by multi-stage hash table,thus reducing collision rate and improving memory load ratio.Hash collision was resolved via coarse-grained timestamp LRU algorithm,which always stored most recently used data and cleared least recently used data to avoid subsequent collisions as far as possible.Trace-driven experiments showed that compared with widely used single hash table,MHNSS had significant performance advantage in collision rate and load ratio.

Key words: intelligent routing, storage structure, multi-stage hashing, LRU

中图分类号:

TN915

朱峰,黄群. 面向智能路由的多级哈希网络数据存储结构[J]. 电信科学, 2020, 36(10): 67-78.

Feng ZHU,Qun HUANG. Multi-stage hashing network storage structure for intelligent routing[J]. Telecommunications Science, 2020, 36(10): 67-78.

图/表 6

图1

图2

图3

图4

图5

图6

参考文献 25

[1]	GAO K , LI D , CHEN L ,et al. Incorporating intra-flow dependencies and inter-flow correlations for traffic matrix prediction[C]// Proceedings of 2020 IEEE/ACM 28th International Symposium on Quality of Service (IWQoS). Piscataway:IEEE Press, 2020: 1-10.
[2]	WANG S , LI D , GENG J . Geryon:accelerating distributed cnn training by network-level flow scheduling[C]// Proceedings of IEEE INFOCOM 2020-IEEE Conference on Computer Communications. Piscataway:IEEE Press, 2020: 1678-1687.
[3]	金子晋, 兰巨龙, 江逸茗 ,等. SDN环境下基于QLearning算法的业务划分路由选路机制[J]. 网络与信息安全学报, 2018,4(9): 17-22.
	JIN Z J , LAN J L , JIANG Y M ,et al. QLearning based business differentiating routing mechanism in SDN architecture[J]. Chinese Journal of Network and Information Security, 2018,4(9): 17-22.
[4]	胡涛, 张建辉, 孔维功 ,等. SDN 中基于双向匹配的多控制器动态部署算法[J]. 通信学报, 2018,39(1): 159-169.
	HU T , ZHANG J H , KONG W G ,et al. Dynamic deployment algorithm for multi-controllers based on bidirectional matching in software defined networking[J]. Journal on Communications, 2018,39(1): 159-169.
[5]	王勇, 周慧怡, 俸皓 ,等. 基于深度卷积神经网络的网络流量分类方法[J]. 通信学报, 2018,39(1): 14-23.
	WANG Y , ZHOU H Y , FENG H ,et al. Network traffic classification method basing on CNN[J]. Journal on Communications, 2018,39(1): 14-23.
[6]	李传煌, 孙正君, 袁小雍 ,等. 基于深度学习的实时DDoS攻击检测[J]. 电信科学, 2017,33(7): 53-65.
	LI C H , SUN Z J , YUAN X Y ,et al. Real-time DDoS attack detection based on deep learning[J]. Telecommunications Science, 2017,33(7): 53-65.
[7]	李洪成, 吴晓平, 姜洪海 . 基于改进聚类分析的网络流量异常检测方法[J]. 网络与信息安全学报, 2015,1(1): 66-71.
	LI H C , WU X P , JIANG H H . Traffic anomaly detection method in networks based on improved clustering algorithm[J]. Chinese Journal of Network and Information Security, 2015,1(1): 66-71.
[8]	WANG S , LI D , GENG J ,et al. Impact of network topology on the performance of DML:theoretical analysis and practical factors[C]// Proceedings of IEEE INFOCOM 2019-IEEE Conference on Computer Communications. Piscataway:IEEE Press, 2019: 1729-1737.
[9]	NARAYANA S , SIVARAMAN A , NATHAN V ,et al. Language-directed hardware design for network performance monitoring[C]// Proceedings of Conference of the ACM Special Interest Group. New York:ACM Press, 2017: 85-98.
[10]	GUPTA A , HARRISON R , CANINI M ,et al. Sonata:query-driven streaming network telemetry[C]// Proceedings of the 2018 Conference of the ACM Special Interest Group on Data Communication. New York:ACM Press, 2018: 357-371.
[11]	LI D , WANG S , ZHU K ,et al. A survey of network update in SDN[J]. Frontiers of Computer Science, 2017,11(1): 4-12.
[12]	PAGH R , RODLER F F . Cuckoo hashing[J]. Journal of Algorithms, 2004,51(2): 122-144.
[13]	FOTAKIS D , PAGH R , SANDERS P ,et al. Space efficient hash tables with worst case constant access time[J]. Theory of Computing Systems, 2005,38(2): 229-248.
[14]	DIETZFELBINGER M , WEIDLING C . Balanced allocation and dictionaries with tightly packed constant size bins[J]. Theoretical Computer Science, 2007,380(1-2): 47-68.
[15]	SUN Y , HUA Y , JIANG S ,et al. SmartCuckoo:a fast and cost-efficient hashing index scheme for cloud storage systems[C]// Proceedings of 2017 USENIX Annual Technical Conference. Santa Clara:USENIX Press, 2017: 553-565.
[16]	LI Q , HUA Y , HE W ,et al. Necklace:an efficient cuckoo hashing scheme for cloud storage services[C]// Proceedings of 2014 IEEE 22nd International Symposium of Quality of Service (IWQoS). Piscataway:IEEE Press, 2014: 153-158.
[17]	LI D , DU R , LIU Z ,et al. Multi-copy cuckoo hashing[C]// Proceedings of 2019 IEEE 35th International Conference on Data Engineering (ICDE). Piscataway:IEEE Press, 2019: 1226-1237.
[18]	FRIEZE A , MELSTED P , MITZENMACHER M . An analysis of random-walk cuckoo hashing[M]// Approximation,Randomization,and Combinatorial Optimization.Algorithms and Techniques. Berlin:Springer, 2009: 490-503.
[19]	KIRSCH A , MITZENMACHER M , WIEDER U . More robust hashing:cuckoo hashing with a stash[J]. SIAM Journal on Computing, 2010,39(4): 1543-1561.
[20]	AUMüLLER M , DIETZFELBINGER M , WOELFEL P . Explicit and efficient hash families suffice for cuckoo hashing with a stash[J]. Algorithmica, 2014,70(3): 428-456.
[21]	LI Y , MIAO R , KIM C ,et al. Flowradar:a better netflow for data centers[C]// Proceedings of 13th USENIX Symposium on Networked Systems Design and Implementation. Santa Clara:USENIX Press, 2016: 311-324.
[22]	TAMMANA P , AGARWAL R , LEE M . Distributed network monitoring and debugging with switchpointer[C]// Proceedings of 15th USENIX Symposium on Networked Systems Design and Implementation. Renton:USENIX Press, 2018: 453-456.
[23]	FAN B , ANDERSEN D G , KAMINSKY M . Memc3:compact and concurrent memcache with dumber caching and smarter hashing[C]// Proceedings of the 10th USENIX Symposium on Networked Systems Design and Implementation. Lombard:USENIX Press, 2013: 371-384.
[24]	HUANG Q , SUN H , LEE P P C ,et al. OmniMon:re-architecting network telemetry with resource efficiency and full accuracy[C]// Proceedings of the Annual conference of the ACM Special Interest Group on Data Communication on the Applications,Technologies,Architectures,and Protocols for Computer Communication. New York:ACM Press, 2020: 404-421.
[25]	BEN-BASAT R , CHEN X , EINZIGER G ,et al. Efficient measurement on programmable switches using probabilistic recirculation[C]// Proceedings of 2018 IEEE 26th International Conference on Network Protocols (ICNP). Piscataway:IEEE Press, 2018: 313-323.

面向智能路由的多级哈希网络数据存储结构

Multi-stage hashing network storage structure for intelligent routing

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 6

参考文献 25

相关文章 2

Metrics

推荐阅读 0

[1]	伍仲丽, 曹园园, 黄文睿, 戴彬, 莫益军. 面向确定性网络的按需智能路由技术[J]. 电信科学, 2021, 37(11): 11-16.
[2]	王歆平,王茜,刘恩慧,马亦然,林程勇,史凡. 基于SDN的按需智能路由系统研究与验证[J]. 电信科学, 2014, 30(4): 8-14.