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

doi:10.11959/j.issn.1000-0801.2020287

Abstract

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

CLC Number:

TN915

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

Figures/Tables 6

References 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.

Metrics

Recommended 0

No Suggested Reading articles found!

Multi-stage hashing network storage structure for intelligent routing

RichHTML

PDF下载

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 6

References 25

Related Articles 1

Metrics

Recommended 0