大规模计算环境下网络模拟任务划分研究
|
摘要
在网络模拟研究中,单节点计算环境无法模拟大规模网络。并行网络模拟通过引入更多的计算节点可以解决这个问题。方法是将模拟拓扑划分为几个部分,分别由各个计算节点负责模拟,可以实现模拟大规模网络并能减少模拟时间。
现有的网络模拟拓扑划分通常需要计算环境的指导,即把计算环境和模拟拓扑作为划分算法的输入,在划分中考虑到节点的计算性能,并尽量减少各个划分块之间的链路负载,以期望能降低并行模拟的通信开销。现有的划分算法,在计算环境规模较小的情况下,能根据计算节点的性能,合理的把模拟拓扑映射到计算环境中,能收到较好的划分效果。但是,对于大规模的并行计算环境,计算节点数目众多,性能层次不齐,无法确定为一个特定模拟任务分配资源的多少。因此,现有划分算法受到计算环境的限制,不再适用于大规模计算平台的网路模拟任务划分。
本文提出了一种基于模拟拓扑特征的并行网络模拟的拓扑划分方法,该划分方案通过分析基准实验,引入了影响并行模拟的几个主要因素,如负载均衡和减少通信开销,最终能实现拓扑划分中,通信开销所占比例较小,并利用大规模并行计算网络中节点性能的多样性,实现了负载均衡,可以提高并行网络模拟平台的吞吐率和模拟效率。较之现有的划分方法,不需要计算环境的指导,完全从分析模拟拓扑本身出发,提高了并行模拟加速比,具有很强的应用价值。
最后,本文还整合了现有的划分工具,设计了大规模网络模拟平台的管理调度系统,方便管理和调度计算资源,可以实现了一键式并行网络模拟,较之传统的手工方式,极大的方便了研究人员使用平台,提高了并行网络模拟的易用性。
In the network simulation research, large-scale network can not be simulated in single-node due to limited computing capacity. With more computing nodes, Parallel network simulation can solve this problem. The key method is dividing the network into several parts of topology, and then calculating by multi-nodes, which can expand the scale of the simulation topology and reduce the simulation time.
The existing topology partition method, using both the computing environment and the simulation topology as input, considers the difference of node’s calculating performance, and maps the simulation topology to computing environment with loading balance and minimizing the communication overhead. This method does a good job in small-scale computing environment, but in large-scale parallel network simulation platform, because of plentiful nodes and variety of the computing performance, this method can not make sure how much resource should be allocated for a simulation topology. Because of needing guidance of computing environment, existing partition method can not work efficiently for large-scale parallel network simulation platform.
This paper designs a new partition method based on the simulation topology itself, with minimizing the communication overhead. For the variety of the computing performance of the large-scale platform, loading balance can be easily got. First, we consider the factor of parallel network simulation and do an experiment to analyze it, and then design the partition algorithm; finally we use some case to verify the performance. Comparing the existing method, this one does not need the guidance of the computing environment, and can discover the maximum speedup in a higher possibility, which can improve the efficiency and throughput of platform.
At last, we design a system for a large-scale network simulation platform to facilitate the scheduling and management of computing resources and to achieve a one-button-simulation, greatly helping the researchers to use platform conveniently.
现有的网络模拟拓扑划分通常需要计算环境的指导,即把计算环境和模拟拓扑作为划分算法的输入,在划分中考虑到节点的计算性能,并尽量减少各个划分块之间的链路负载,以期望能降低并行模拟的通信开销。现有的划分算法,在计算环境规模较小的情况下,能根据计算节点的性能,合理的把模拟拓扑映射到计算环境中,能收到较好的划分效果。但是,对于大规模的并行计算环境,计算节点数目众多,性能层次不齐,无法确定为一个特定模拟任务分配资源的多少。因此,现有划分算法受到计算环境的限制,不再适用于大规模计算平台的网路模拟任务划分。
本文提出了一种基于模拟拓扑特征的并行网络模拟的拓扑划分方法,该划分方案通过分析基准实验,引入了影响并行模拟的几个主要因素,如负载均衡和减少通信开销,最终能实现拓扑划分中,通信开销所占比例较小,并利用大规模并行计算网络中节点性能的多样性,实现了负载均衡,可以提高并行网络模拟平台的吞吐率和模拟效率。较之现有的划分方法,不需要计算环境的指导,完全从分析模拟拓扑本身出发,提高了并行模拟加速比,具有很强的应用价值。
最后,本文还整合了现有的划分工具,设计了大规模网络模拟平台的管理调度系统,方便管理和调度计算资源,可以实现了一键式并行网络模拟,较之传统的手工方式,极大的方便了研究人员使用平台,提高了并行网络模拟的易用性。
In the network simulation research, large-scale network can not be simulated in single-node due to limited computing capacity. With more computing nodes, Parallel network simulation can solve this problem. The key method is dividing the network into several parts of topology, and then calculating by multi-nodes, which can expand the scale of the simulation topology and reduce the simulation time.
The existing topology partition method, using both the computing environment and the simulation topology as input, considers the difference of node’s calculating performance, and maps the simulation topology to computing environment with loading balance and minimizing the communication overhead. This method does a good job in small-scale computing environment, but in large-scale parallel network simulation platform, because of plentiful nodes and variety of the computing performance, this method can not make sure how much resource should be allocated for a simulation topology. Because of needing guidance of computing environment, existing partition method can not work efficiently for large-scale parallel network simulation platform.
This paper designs a new partition method based on the simulation topology itself, with minimizing the communication overhead. For the variety of the computing performance of the large-scale platform, loading balance can be easily got. First, we consider the factor of parallel network simulation and do an experiment to analyze it, and then design the partition algorithm; finally we use some case to verify the performance. Comparing the existing method, this one does not need the guidance of the computing environment, and can discover the maximum speedup in a higher possibility, which can improve the efficiency and throughput of platform.
At last, we design a system for a large-scale network simulation platform to facilitate the scheduling and management of computing resources and to achieve a one-button-simulation, greatly helping the researchers to use platform conveniently.
引文
1雷擎,王行刚.计算机网络模拟方法与工具.通信学报,2001,22(9): p.84-90.
2 S. McCanne and S. Floyd,“The LBNL network simulator”Software on-line: http://www.isi.edu/nsnam, 1997, Lawrence Berkeley Laboratory.
3 S. Bertolottia and L. Dunand,“Opnet 2.4: and environment for communication network modeling and simulation”in Proceedings of European Simulation Symposium, October 1993.
4 X Zeng, R. Bagrodia, and M. Gerla,“GloMoSim: a library for parallel simulation of large-scale wireless networks”in Proceedings of the 12th workshop on Parallel and Distributed Simulation, May 1998.
5 B. Liu, D. R. Figueiredo, Y. GAO, J. Kurose, and D. Towsley,“A Study of Networks Simulation Efficiency: Fluid Simulation vs. Packet-level Simulation”presented an IEEE INFOCOM’2001 Anchorage, Alaska, 2001.
6 G. F. Riley, T. M. Jaafar, and R. M. Fujimoto, "Integrated Fluid and Packet Network Simulations," presented at MASCOTS'02, Fort Worth, Texas, 2002.
7 R. Brown, "Calendar queues: A fast O(1) priority queue implementation for the simulation event set problem," Communications of the ACM, vol. 31, pp. 1220-1227, 1988.
8 R. M. Fujimoto, Parallel and Distributed Simulation Systems: Wiley Interscience, 2000.
9 Riley George, Ammar Mostafa, Fujimoto Richard, A Federated approach to distributed network simulation. ACM Transactions on Modeling and Computer Simulation. 2004 14(2).
10 Nicol D, Liu J, Liljenstam M, et al. Simulation of large-scale networks using SSF. Preceedings of the 2003 Winter Simulation Conference. New Orleans, LA: , 2003. 650~657
11 Yu Liu, Boleslaw Szymanski, Adnan Saifee. Genesis: A Scalable Distributed System for Large-scale Parallel Network Simulation. Computer Network Journal, to appear 2005.
12 Karypis G., Kumar V.. Multilevel k-way partitioning scheme for irregular graphs. Journal of Parallel and Distributed Computing, 1998, 48: 96 ~129
13 R. M. Fujimoto, K. Perumalla, A. Park, H. Wu, and M. H. Ammar, "Large-Scale Network Simulation: How Big? How Fast?," presented at Meeting of the IEEE International Symposium
14 Fujimoto M R. Parallel Discrete Event Simulation [J] .Communication of ACM, 1990, 33(4):31-53
15林健,杨新华.并行离散事件仿真框架研究.系统仿真学报. 2001,
2:146~149, 23
16林健,毛晶莹.并行离散事件仿真PDES策略比较研究.系统工程理论与实践. 1998, 9:14~19
17刘步权,王怀民,姚益平.基于HLA的时间同步技术.计算机工程与科学. 2004, 26:96~9
18刘步权,王怀民,姚益平.一种无死锁的时间管理算法.软件学报. 2003, 14:1515~152
19 K. M. Chandy, R. Sherman. The Conditional Event Approach to Distributed Simulation. Distributed Simulation Conference. 1989:100~10
20刘步权,王怀民,姚益平. RTI中乐观推进机制的实现.软件学报. 2004, 15:338~34
21 Naroska and Schwiegelshohn. Conservative Parallel Simulation of a Large Number of Processes, SIMULATION.1999; 72: 150-162
22 D. R. Jefferson. Virtual time. ACM Transactions on Programming Languages and Systems. 1985, 7(3):404~425
23 K. M. Chandy, J. Misra. Distributed Simulation: A case study in Design and Verification of Distributed Programs. IEEE Transactions on Software Engineering. 1979,5 440~452
24 R. E. Bryant. Simulation of Packet Communications Architecture Computer Systems Massachusetts Institute of Technology. MIT-LCS-TR-188, 1977
25 V. Jha, R. Bagrodia. A Performance Evaluation Methodology for Parallel Simulation Protocols. Proceedings of the Tenth Workshop on Parallel and Distributed Simulation. 1996, 26:180~18
26 Alfred Park, Richard M. Fujimoto, Kalyan S. Perumalla. Conservative Synchronization of Large-Scale Network Simulations. PADS’04
27 Rob Simmonds, R.B., and Brian Unger. Applying parallel discrete event simulation to network emulation. in 14th Workshop on Parallel and Distributed Simulation (PADS 2000). May 28-31, 2000. Bologna, Italy.
28 Jason Liu, a.D.M.N. Learning Not to Share. in Proceedings of the 15th Workshop on Parallel and Distributed Simulation (PADS 2001). 2001. Lake Arrowhead, CA.
29 Stephen T. Barnard and Horst D. Simon. A fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems. In Proceedings of the sixth SIAM conference on Parallel Processing for Scientific Computing, pages 711–718, 1993.
30 Bruce Hendrickson and Robert Leland. An improved spectral graph partitioning algorithm for mapping parallel computations. Technical Report SAND92-1460, Sandia National Laboratories, 1992.
31 Gary L. Miller, Shang-Hua Teng, and Stephen A. Vavasis. A unified geometric approach to graph separators. In Proceedings of 31st Annual Symposium on Foundations of Computer Science, pages 538–547, 1991.
32 Gary L. Miller, Shang-Hua Teng, W. Thurston, and Stephen A. Vavasis.Automatic mesh partitioning. In A. George, John R.Gilbert, and J. W.-H. Liu, editors, Sparse Matrix Computations: Graph Theory Issues and Algorithms. (An IMA Workshop Volume). Springer-Verlag, New York, NY, 1993.
33 F. Pellegrini, J.R. SCOTCH: a software package for static mapping by dual recursive bipartitioning of process and architecture graphs. in High-performance Computing and Networking, Proc. HPCN'96. 1996. Springer, Berlin.
34 Earl R. Barnes. An algorithm for partitioning the nodes of a graph. SIAM J. Algebraic Discrete Methods, 3(4):541–550, December 1984.
35 A. George. Nested dissection of a regular finite-element mesh. SIAM Journal on Numerical Ananlysis, 10:345–363, 1973.
36 Jinsheng Xu, Moon Jung Chung. Predicting the Performance of Synchronous Discrete Event Simulation. IEEE Transactions on Parallel and Distributed Systems, 2004, 15(12) 1~8
37 Brian White, J.L., Leigh Stoller, Robert Ricci, Shashi Guruprasad, Mac Newbold, Mike Hibler, Chad Barb, and Abhijeet Joglekar. An Integrated Experimental Environment for Distributed Systems and Networks. in Proceedings of 5th Symposium on Operating Systems Design and Implementation (OSDI).December, 2002
38 Bruce Hendrickson and Robert Leland. A multilevel algorithm for partitioning graphs. Technical Report SAND93-1301,Sandia National Laboratories, 1993.
39 G. Karypis and V. Kumar. Analysis of multilevel graph partitioning. Technical Report TR 95-037, Department of Computer Science, University of Minnesota, 1995. Also available on WWW at URL http://www.cs.umn.edu/?karypis/papers/mlevel analysis.ps. A short version appears in Supercomputing 95.
40 G Karypis, V Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on Scientific Computing, 1998
41 B. Kernighan and S. Lin. An effcient heuristic procedure for partitioning graphs. The Bell System Technical Journal,49(2):291-307, 1970.
42 C. Fiduccia and R. Mattheyses. A linear time heuristic for improving network partitions. In In Proc. 19th IEEE Design Automation Conference, pages 175-181, 1982.
43 G. F. Riley, E. W. Zegura, and M. H. Ammar,“Efficient routing using nix-vector(long version)”May 2001.
44 K Fall, K Varadhan, The ns Manual http://www.isi.edu/nsnam/ns/doc/index.html 2002-04
45 Kalyan Perumalla,“libsynk/rti,”Software online: http://www.cc.gatech.edu/computing/pads/kalyan/linsynh.html, 2004
2 S. McCanne and S. Floyd,“The LBNL network simulator”Software on-line: http://www.isi.edu/nsnam, 1997, Lawrence Berkeley Laboratory.
3 S. Bertolottia and L. Dunand,“Opnet 2.4: and environment for communication network modeling and simulation”in Proceedings of European Simulation Symposium, October 1993.
4 X Zeng, R. Bagrodia, and M. Gerla,“GloMoSim: a library for parallel simulation of large-scale wireless networks”in Proceedings of the 12th workshop on Parallel and Distributed Simulation, May 1998.
5 B. Liu, D. R. Figueiredo, Y. GAO, J. Kurose, and D. Towsley,“A Study of Networks Simulation Efficiency: Fluid Simulation vs. Packet-level Simulation”presented an IEEE INFOCOM’2001 Anchorage, Alaska, 2001.
6 G. F. Riley, T. M. Jaafar, and R. M. Fujimoto, "Integrated Fluid and Packet Network Simulations," presented at MASCOTS'02, Fort Worth, Texas, 2002.
7 R. Brown, "Calendar queues: A fast O(1) priority queue implementation for the simulation event set problem," Communications of the ACM, vol. 31, pp. 1220-1227, 1988.
8 R. M. Fujimoto, Parallel and Distributed Simulation Systems: Wiley Interscience, 2000.
9 Riley George, Ammar Mostafa, Fujimoto Richard, A Federated approach to distributed network simulation. ACM Transactions on Modeling and Computer Simulation. 2004 14(2).
10 Nicol D, Liu J, Liljenstam M, et al. Simulation of large-scale networks using SSF. Preceedings of the 2003 Winter Simulation Conference. New Orleans, LA: , 2003. 650~657
11 Yu Liu, Boleslaw Szymanski, Adnan Saifee. Genesis: A Scalable Distributed System for Large-scale Parallel Network Simulation. Computer Network Journal, to appear 2005.
12 Karypis G., Kumar V.. Multilevel k-way partitioning scheme for irregular graphs. Journal of Parallel and Distributed Computing, 1998, 48: 96 ~129
13 R. M. Fujimoto, K. Perumalla, A. Park, H. Wu, and M. H. Ammar, "Large-Scale Network Simulation: How Big? How Fast?," presented at Meeting of the IEEE International Symposium
14 Fujimoto M R. Parallel Discrete Event Simulation [J] .Communication of ACM, 1990, 33(4):31-53
15林健,杨新华.并行离散事件仿真框架研究.系统仿真学报. 2001,
2:146~149, 23
16林健,毛晶莹.并行离散事件仿真PDES策略比较研究.系统工程理论与实践. 1998, 9:14~19
17刘步权,王怀民,姚益平.基于HLA的时间同步技术.计算机工程与科学. 2004, 26:96~9
18刘步权,王怀民,姚益平.一种无死锁的时间管理算法.软件学报. 2003, 14:1515~152
19 K. M. Chandy, R. Sherman. The Conditional Event Approach to Distributed Simulation. Distributed Simulation Conference. 1989:100~10
20刘步权,王怀民,姚益平. RTI中乐观推进机制的实现.软件学报. 2004, 15:338~34
21 Naroska and Schwiegelshohn. Conservative Parallel Simulation of a Large Number of Processes, SIMULATION.1999; 72: 150-162
22 D. R. Jefferson. Virtual time. ACM Transactions on Programming Languages and Systems. 1985, 7(3):404~425
23 K. M. Chandy, J. Misra. Distributed Simulation: A case study in Design and Verification of Distributed Programs. IEEE Transactions on Software Engineering. 1979,5 440~452
24 R. E. Bryant. Simulation of Packet Communications Architecture Computer Systems Massachusetts Institute of Technology. MIT-LCS-TR-188, 1977
25 V. Jha, R. Bagrodia. A Performance Evaluation Methodology for Parallel Simulation Protocols. Proceedings of the Tenth Workshop on Parallel and Distributed Simulation. 1996, 26:180~18
26 Alfred Park, Richard M. Fujimoto, Kalyan S. Perumalla. Conservative Synchronization of Large-Scale Network Simulations. PADS’04
27 Rob Simmonds, R.B., and Brian Unger. Applying parallel discrete event simulation to network emulation. in 14th Workshop on Parallel and Distributed Simulation (PADS 2000). May 28-31, 2000. Bologna, Italy.
28 Jason Liu, a.D.M.N. Learning Not to Share. in Proceedings of the 15th Workshop on Parallel and Distributed Simulation (PADS 2001). 2001. Lake Arrowhead, CA.
29 Stephen T. Barnard and Horst D. Simon. A fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems. In Proceedings of the sixth SIAM conference on Parallel Processing for Scientific Computing, pages 711–718, 1993.
30 Bruce Hendrickson and Robert Leland. An improved spectral graph partitioning algorithm for mapping parallel computations. Technical Report SAND92-1460, Sandia National Laboratories, 1992.
31 Gary L. Miller, Shang-Hua Teng, and Stephen A. Vavasis. A unified geometric approach to graph separators. In Proceedings of 31st Annual Symposium on Foundations of Computer Science, pages 538–547, 1991.
32 Gary L. Miller, Shang-Hua Teng, W. Thurston, and Stephen A. Vavasis.Automatic mesh partitioning. In A. George, John R.Gilbert, and J. W.-H. Liu, editors, Sparse Matrix Computations: Graph Theory Issues and Algorithms. (An IMA Workshop Volume). Springer-Verlag, New York, NY, 1993.
33 F. Pellegrini, J.R. SCOTCH: a software package for static mapping by dual recursive bipartitioning of process and architecture graphs. in High-performance Computing and Networking, Proc. HPCN'96. 1996. Springer, Berlin.
34 Earl R. Barnes. An algorithm for partitioning the nodes of a graph. SIAM J. Algebraic Discrete Methods, 3(4):541–550, December 1984.
35 A. George. Nested dissection of a regular finite-element mesh. SIAM Journal on Numerical Ananlysis, 10:345–363, 1973.
36 Jinsheng Xu, Moon Jung Chung. Predicting the Performance of Synchronous Discrete Event Simulation. IEEE Transactions on Parallel and Distributed Systems, 2004, 15(12) 1~8
37 Brian White, J.L., Leigh Stoller, Robert Ricci, Shashi Guruprasad, Mac Newbold, Mike Hibler, Chad Barb, and Abhijeet Joglekar. An Integrated Experimental Environment for Distributed Systems and Networks. in Proceedings of 5th Symposium on Operating Systems Design and Implementation (OSDI).December, 2002
38 Bruce Hendrickson and Robert Leland. A multilevel algorithm for partitioning graphs. Technical Report SAND93-1301,Sandia National Laboratories, 1993.
39 G. Karypis and V. Kumar. Analysis of multilevel graph partitioning. Technical Report TR 95-037, Department of Computer Science, University of Minnesota, 1995. Also available on WWW at URL http://www.cs.umn.edu/?karypis/papers/mlevel analysis.ps. A short version appears in Supercomputing 95.
40 G Karypis, V Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on Scientific Computing, 1998
41 B. Kernighan and S. Lin. An effcient heuristic procedure for partitioning graphs. The Bell System Technical Journal,49(2):291-307, 1970.
42 C. Fiduccia and R. Mattheyses. A linear time heuristic for improving network partitions. In In Proc. 19th IEEE Design Automation Conference, pages 175-181, 1982.
43 G. F. Riley, E. W. Zegura, and M. H. Ammar,“Efficient routing using nix-vector(long version)”May 2001.
44 K Fall, K Varadhan, The ns Manual http://www.isi.edu/nsnam/ns/doc/index.html 2002-04
45 Kalyan Perumalla,“libsynk/rti,”Software online: http://www.cc.gatech.edu/computing/pads/kalyan/linsynh.html, 2004
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |