Multi-stage hashing network storage structure for intelligent routing

Feng ZHU; Qun HUANG

doi:10.11959/j.issn.1000-0801.2020287

您当前的位置：

首页 >

文章列表页 >

Multi-stage hashing network storage structure for intelligent routing

Topic:Intelligent Communication Technology | 更新时间：2024-06-05

- Multi-stage hashing network storage structure for intelligent routing
- Telecommunications Science Vol. 36, Issue 10, Pages: 67-78(2020)
- 作者机构：
  
  1. 中国科学院计算技术研究所，北京100190
  2. 北京大学，北京 100871
- 作者简介：
- 基金信息：
- DOI：10.11959/j.issn.1000-0801.2020287
  CLC： TN915
- Published Online：2020-10，
  
  Published：20 October 2020
- 稿件说明：
移动端阅览
Feng ZHU, Qun HUANG. Multi-stage hashing network storage structure for intelligent routing[J]. Telecommunications science, 2020, 36(10): 67-78.
DOI：

Feng ZHU, Qun HUANG. Multi-stage hashing network storage structure for intelligent routing[J]. Telecommunications science, 2020, 36(10): 67-78. DOI： 10.11959/j.issn.1000-0801.2020287.

摘要

网络数据的采集和存储是智能路由控制的基础，为智能路由提供了大量的网络流量数据进行模型训练和决策。然而，作为网络数据存储系统中的核心设备，交换机的存储空间非常有限，且设计灵活性低，无法满足智能路由控制对全面高精度的数据存储和轻量级存储系统的需求，进而影响智能路由控制的效果。提出一种面向智能路由控制的多级哈希网络数据存储结构，高效利用交换机有限的存储空间，实现低碰撞率的网络数据存储。该结构通过多级哈希表增加数据的可存储空间数量，从而降低存储冲突率并提高存储空间利用率。同时，该结构使用基于低开销时间戳的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.

关键词

Keywords

references

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 .

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 .

金子晋 , 兰巨龙 , 江逸茗 , 等 . 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 .

胡涛 , 张建辉 , 孔维功 , 等 . 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 .

王勇 , 周慧怡 , 俸皓 , 等 . 基于深度卷积神经网络的网络流量分类方法 [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 .

李传煌 , 孙正君 , 袁小雍 , 等 . 基于深度学习的实时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 .

李洪成 , 吴晓平 , 姜洪海 . 基于改进聚类分析的网络流量异常检测方法 [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 .

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 .

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 .

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 .

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 .

PAGH R , RODLER F F . Cuckoo hashing [J ] . Journal of Algorithms , 2004 , 51 ( 2 ): 122 - 144 .

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 .

DIETZFELBINGER M , WEIDLING C . Balanced allocation and dictionaries with tightly packed constant size bins [J ] . Theoretical Computer Science , 2007 , 380 ( 1-2 ): 47 - 68 .

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 .

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 .

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 .

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 .

KIRSCH A , MITZENMACHER M , WIEDER U . More robust hashing:cuckoo hashing with a stash [J ] . SIAM Journal on Computing , 2010 , 39 ( 4 ): 1543 - 1561 .

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 .

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 .

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 .

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 .

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 .

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 .

Views

574

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

No data

Related Author

No data

Related Institution

No data

⁰