胖树的网络演算模型

J4 ›› 2014, Vol. 36 ›› Issue (12): 2272-2279.

胖树的网络演算模型

秦广军，祝明发，肖利民，阮利

(1.北京航空航天大学软件开发环境国家重点实验室，北京 100191；2.北京航空航天大学计算机学院，北京 100191)

收稿日期:2014-08-30 修回日期:2014-11-01 出版日期:2014-12-25 发布日期:2014-12-25
基金资助:
北京市自然科学基金资助项目(4122042)；国家教育部博士点专项基金资助项目(20101102110018)；国家自然科学基金资助项目(61370059)

Network calculus for fattree network

Qin Guangjun,ZHU Mingfa,XIAO Limin,RUAN Li

(1.State Key Laboratory of Software Development Environment,Beihang University,Beijing 100191;
2.School of Computer Science and Engineering,Beihang University,Beijing 100191,China)

Received:2014-08-30 Revised:2014-11-01 Online:2014-12-25 Published:2014-12-25

摘要/Abstract

摘要：

网络演算近年来已成为网络领域重要的性能分析工具之一，但是，传统的网络演算主要关注网络的QoS性质，通过计算数据流的最大数据积压、最大端到端延迟、服务曲线等来分析网络的性能。在高性能计算系统中，则主要关心网络系统的吞吐率、通信延迟以及网络的饱和参数等，传统的网络演算理论无法有效计算这些参数。将网络演算与排队论结合，定义和推导了网络演算下的通信延迟和吞吐率，构造了一套适合高性能网络分析的网络演算分析方法。基于设计的方法，通过对胖树网络下均匀流量模式的分析，表明本文所设计的方法能够有效分析高性能网络的通信延迟、吞吐率等参数，并能有效捕捉网络的饱和状态，与模拟器的对比结果也表明本文模型能够基本吻合仿真结果。

关键词: 胖树网络, 网络演算, 通信延迟, 吞吐量, 流量模式

Abstract:

Network calculus is one of the most important performance analysis tools in the network research area. The classical network calculus is mainly focused on the QoS, and the maximum backlog, the maximum network delay and the service curve are the significant analyzing metrics. However, the researchers in the highperformance computing systems are more concerned about the throughput, the communication latency, the network saturation point, etc., which cannot be inferred from the classical network calculus. The queuing theory is introduced into the network calculus, the communication latency and the throughput formulas are derived, and a network calculus analysis method for highperformance network calculus is proposed. Based on the analysis method, the uniform traffic pattern of the fattree network is analyzed. The analysis results indicate that the method can efficiently describe the network communication process and capture the saturation point, and basically be consistent with simulated results.

Key words: fat-tree network;network calculus;communication latency;throughput;traffic patterns

秦广军，祝明发，肖利民，阮利. 胖树的网络演算模型[J]. J4, 2014, 36(12): 2272-2279.

Qin Guangjun,ZHU Mingfa,XIAO Limin,RUAN Li. Network calculus for fattree network [J]. J4, 2014, 36(12): 2272-2279.

参考文献［19］

［1］	Dally W J, Towles B P. Principles and practices of interconnection networks［M］. NY:Elsevier, 2004.
［2］	Banks J, Carson J S, Nelson B L, et al. Discrete event system simulation［M］.Beijing:China Machine Press,2007.(in Chinese)
［3］	Nan Jiang, Becker D U, Michelogiannakis G, et al. A detailed and flexible cycleaccurate networkonchip simulator［C］∥Proc of the 2013 IEEE International Symposium on Performance Analysis of Systems and Software, 2013:1.
［4］	Ns3［EB/OL］.［20140702］.https://www.nsnam.org/.
［5］	OMNET++［EB/OL］.［20140702］.http://www.omnetpp.org/.
［6］	Eslami K A. performance analysis and design space exploration of onchip interconnection networks［D］. Sweden:KTH Royal Institute of Technology, 2013.
［7］	Boudec J Y L, Thiran P. Network calculus:A theory of deterministic queuing system for the Internet［M］∥LNCS 2050, Berlin:Springer Verlag, 2012.
［8］	Cruz R L. A calculus for network delay. I. network elements in isolation［J］. IEEE Transactions on Information Theory, 1991, 37(1):114131.
［9］	Parekh A K, Gallagher R G. A generalized processor sharing approach to flow control in integrated services networks:The multiple node case［J］. IEEE/ACM Transactions on Networking (TON), 1994, 2(2):137150.
［10］	Chang C S. On deterministic traffic regulation and service guarantees:A systematic approach by filtering［J］. IEEE Transactions on Information Theory, 1998, 44(3):10971110.
［11］	Fidler M, Recker S. Conjugate network calculus:A dual approach applying the legendre transform［J］. Computer Networks, 2006, 50(8):10261039.
［12］	Fan Baohua, Dou Qiang, Zhang Heying. A matrix interpretation of network calculus［J］. Chinese Journal of Computers, 2009,32(12):24112419.(in Chinese)
［13］	Zhang Xinming, Chen Guoliang, Gu Jun. On the computation of endtoend delay bound in guaranteed service by network calculus［J］.Journal of Software, 2001,12(6):889893.(in Chinese)
［14］	Qian Yue. Calculus models and performance analysis for networksonchip［D］.Changsha:National University of Defense Technology,2010.(in Chinese)
［15］	Jiang Y, Liu Y. Stochastic network calculus［M］. Heidelberg:Springer, 2008.
［16］	Lin Y, Xu X, Lin Y. Communication delay analysis based on network calculus［C］∥Proc of the 2nd International Conference on Software Technology and Engineering (ICSTE), 2010:V2153V2157.
［17］	Leiserson C E. Fattrees:Universal networks for hardwareefficient supercomputing［J］. IEEE Transactions on Computers, 1985, 100(10):892901.
［18］	Ohring S R, Ibel M, Das S K, et al. On generalized fat trees［C］∥Proc of the 9th International Parallel Processing Symposium, 1995:3744.
［19］	Hua Xing.Queueing and random service system［M］.Shanghai:Shanghai Translation Publishing Company,1987.(in Chinese)
［20］	Rodriguez G, Minkenberg C, Beivide R, et al. Oblivious routing schemes in extended generalized fat tree networks［C］∥Proc of HPIDC’09, 2009:18.
［21］	Peh L S, Dally W J. A delay model for router microarchitectures［J］. IEEE Micro, 2001, 21(1):2634.
	附中文参考文献：
［2］	Banks J, Carson J S, Nelson B L,等. 离散事件系统仿真［J］. 第四版. 北京:机械工业出版社, 2007.
［12］	樊葆华, 窦强, 张鹤颖. 网络演算的矩阵解释［J］. 计算机学报, 2009, 32(12):24112419.
［13］	张信明, 陈国良, 顾钧. 基于网络演算计算保证服务端到端延迟上界［J］. 软件学报, 2001,12(6):889893.
［14］	钱悦. 片上网络演算模型及性能分析［D］. 长沙:国防科学技术大学, 2010.
［19］	华兴. 排队论与随机服务系统［M］. 上海:上海翻译出版公司, 1987.

[1]	朱新峰1,张智浩1，王彦凌2. 移动边缘计算环境下的动态资源分配策略[J]. 计算机工程与科学, 2019, 41(07): 1184-1190.
[2]	张长森，陈鹏鹏. 基于竞争窗口递减因子自适应调整退避算法[J]. 计算机工程与科学, 2016, 38(12): 2507-2513.
[3]	方飞1,2，毛玉明1. OFDM符号特性对DCF性能影响研究[J]. J4, 2015, 37(03): 471-478.
[4]	吕绍和1，廖林冰1，李雯2，张以维3，王晓东1，周兴铭1. 无线网络抗干扰攻击的自适应无速率通信[J]. J4, 2015, 37(03): 479-485.
[5]	江明，刘锋. PbRED：基于优先级的RED改进算法[J]. J4, 2015, 37(02): 245-251.
[6]	毋晓鹤1，冉茂儒2，习勇1，周力1. 第三代短波通信HDL协议性能研究[J]. J4, 2014, 36(02): 265-269.
[7]	杜静，敖富江，郭晋，周颖. 基于集群平台的SAR成像算法多级通信延迟隐藏技术[J]. J4, 2013, 35(11): 48-53.
[8]	王永庆，张民选. 链路层上可靠的虚跨步交换支持技术[J]. J4, 2012, 34(8): 119-124.
[9]	高红亮1，2，汪秉文1，高超1，胡晓娅1. 无线传感器网络QoS仿真与研究[J]. J4, 2012, 34(11): 7-13.
[10]	钱悦1，鲁中海2，窦强1，窦文华1. 片上网络二维和三维结构的通信性能分析[J]. J4, 2011, 33(3): 34-40.
[11]	樊葆华，张鹤颖，窦文华. 基于双子代数理论的网络建模与分析[J]. J4, 2011, 33(2): 17-22.
[12]	张麟麟，李东生，雍爱霞. 基于3D Mesh结构的一种静态路由算法[J]. J4, 2011, 33(11): 60-64.
[13]	王圣[1,2] 苏金树[2]. 基于延时的拥塞控制中反向流量的影响分析[J]. J4, 2008, 30(9): 18-21.
[14]	虞万荣王晓东周兴铭. CTMAC协议性能分析比较[J]. J4, 2007, 29(9): 49-52.
[15]	王媛丽[1] 刘湘辉[1,2] 殷建平[1] 景宁[2]. 基于干扰模式的无线传感器网络链路调度算法[J]. J4, 2007, 29(9): 94-96.