基于网络演算的聚合模型分析方法及其评估

doi:10.3969/j.issn.0372-2112.2018.08.003

电子学报 ›› 2018, Vol. 46 ›› Issue (8): 1815-1821.DOI: 10.3969/j.issn.0372-2112.2018.08.003

基于网络演算的聚合模型分析方法及其评估

龙彦辰¹, 沈海斌¹, 鲁中海²

1. 浙江大学超大规模集成电路设计研究所, 浙江杭州 310027;
2. 瑞典皇家工学院, 斯德哥尔摩 16440

收稿日期:2017-06-01 修回日期:2017-09-04 出版日期:2018-08-25
- 作者简介:
- 龙彦辰 女,1988年生,浙江大学电路与系统专业博士生.研究方向为片上网络服务质量保证.E-mail:yanchen@kth.se;沈海斌 男,1967年生,浙江大学教授,研究方向为面向智能安全的高性能计算及其芯片实现.E-mail:shen_hb@zju.edu.cn;鲁中海 男,1968年生,瑞典皇家工学院副教授,研究方向为计算机体系结构.E-mail:zhonghai@kth.se

Analysis and Evaluation of Delay Bounds for Multiplexing Models Based on Network Calculus

LONG Yan-chen¹, SHEN Hai-bin¹, LU Zhong-hai²

1. Institute of VLSI Design, Zhejiang University, Hangzhou, Zhejiang 310027, China;
2. KTH Royal Institute of Technology, Stockholm 16440, Sweden

Received:2017-06-01 Revised:2017-09-04 Online:2018-08-25 Published:2018-08-25

摘要/Abstract

摘要： 在资源共享的通信媒介中，例如总线、交叉矩阵、网络，聚合模型的应用十分普遍.经由聚合节点发送的数据包的延迟上界可以通过网络演算理论得到，然而对于这种延迟上界紧致性的研究一直以来都是开放性问题.本文基于网络演算理论，讨论了单节点、多节点聚合模型的分析方法，包括两种到达曲线模型、两种等价服务曲线分析方法.同时以实验手段对延迟上界的紧致性进行了经验性的评估.最后作为结论，本文归纳了各种分析模型的质量，总结了各个参数是如何影响延迟上界的紧致性的.

关键词: 网络演算, 聚合模型, 延迟上界, 紧致性

Abstract: In resource-sharing communication media such as buses,crossbars and networks,multiplexings are inevitable.While sending packets over a multiplexing node,the worst-case delay bound can be computed using network calculus.The tightness of such delay bound remains an open problem.This paper studies different analysis approaches for multiplexing models,from the single multiplexing node to multi-flow-multi-node model,applying two traffic arrival models,and two service properties when getting equivalent service curves.We analyze per-flow delay bounds with different models,then empirically evaluate the tightness of the delay bounds.Our results show the quality of different analysis models,and how influential each parameter is to tightness.

Key words: network calculus, multiplexing model, delay bound, tightness

中图分类号:

TP302

龙彦辰, 沈海斌, 鲁中海. 基于网络演算的聚合模型分析方法及其评估[J]. 电子学报, 2018, 46(8): 1815-1821.

LONG Yan-chen, SHEN Hai-bin, LU Zhong-hai. Analysis and Evaluation of Delay Bounds for Multiplexing Models Based on Network Calculus[J]. Acta Electronica Sinica, 2018, 46(8): 1815-1821.

参考文献

[1] 欧阳一鸣,何鑫城,等.针对路径故障与局部拥塞的NoC容错路由算法[J].电子学报,2016,44(4),920-925. Ouyang Y,He X,et at.A fault-tolerant routing algorithm aiming at a path fault and local congestion in NoC[J].Acta Electronica Sinica,2016,44(4):920-925.(in Chinese)
[2] 姚磊,蔡觉平,等.基于内建自测技术的Mesh结构NoC无虚通道容错路由算法[J].电子学报,2012,40(5):983-989. Yao L,Cai J,et al.A fault-tolerant routing algorithm based on BIST for 2D-mesh Network-on-Chip without using virtual channels[J].Acta Electronica Sinica,2012,40(5):983-989.(in Chinese)
[3] Xue S,et al.Parallel FFT implementation based on multi-core DSPs[A].IEEE International Conference on Computational Problem-Solving[C].IEEE,2011.426-430.
[4] Cruz R L.A calculus for network delay,Part I:Network elements in isolation;Part Ⅱ:Network analysis[J].IEEE Transactions on Information Theory,1991,37(1):114-141.
[5] Agrawal R,Cruz R L,Okino C,et al.Performance bounds for flow control protocols[J].IEEE/ACM Transactions on Networking,1999,7(3):310-323.
[6] LeBoudec J-Y,Thiran P.Network Calculus:A Theory of Deterministic Queuing Systems for the Internet:Vol 2050[M].[S.l.]:Springer-Verlag,2001.
[7] Qian Y,Lu Z,Dou W.Analysis of worst-case delay bounds for best-effort communication in wormhole networks on chip[A].3rd ACM/IEEE International Symposium on Networks-on-Chip[C].ACM/IEEE,2009.44-53.
[8] Ogras U Y,Bogdan P,Marculescu R.An analytical approach for network-on-chip performance analysis[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2010,29(12):2001-2013.
[9] Bogdan P,Marculescu R.Workload characterization and its impact on multicore platform design[A].Proceedings of the Eighth IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis[C].IEEE/ACM/IFIP,2010.231-240.
[10] Wang J,Li Y,Peng Q.A novel analytical model for network-on-chip using semi-Markov process[J].Advances in Electrical and Computer Engineering,2011,11(1):111-118.
[11] No.RFC 2210,The use of RSVP with IETF integrated services[S].

基于网络演算的聚合模型分析方法及其评估

Analysis and Evaluation of Delay Bounds for Multiplexing Models Based on Network Calculus

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 4

编辑推荐

Metrics

[1]	王昊天;丁凡;熊华钢. 光纤通道交换式网络的虚拟通道分配策略[J]. 电子学报, 2011, 39(10): 2251-2257.
[2]	樊葆华;张鹤颖;窦文华. 一种非确定性的网络演算[J]. 电子学报, 2010, 38(11): 2691-2696.
[3]	陈昕;周拥军;蒋文保;万剑雄. AFDX协议性能分析及调度算法研究[J]. 电子学报, 2009, 37(5): 1000-1005.
[4]	王子君, 许维胜, 王中杰, 吴启迪. 控制网络的确定性延迟演算理论研究[J]. 电子学报, 2006, 34(2): 380-383.