GPN网络的通信算法和动态修正
|
摘要
随着计算机网络技术与计算科学的发展,并行计算机及其互连网络作为一个跨数学、计算科学与信息科学等多门学科的领域,逐渐成为计算机科学研究的热点之一。各种拓扑结构的互连网络,如环、Mesh、超立方体、星型网络等得到迅速发展。在一个多处理器互连网络中,处理器之间的有效通信是衡量系统性能的一个重要标准。Petersen图是多处理机系统中常见的一种互连网络,这种网络拓扑结构由于具有直径小、结构对称、网络寻路算法简单等优点,且多种拓扑结构的互连网络都可以很容易的嵌入其中,因而成为最重要和最具吸引力的网络模型之一。本文即是基于Petersen图进行扩展,并对扩展得到GPN网络路由算法和动态修正进行研究,主要研究内容如下:
1.阐述了并行计算机系统的概念和分类,然后详细介绍了并行计算机模型、特性以及常用的互连网络拓扑结构,包括一维线性阵列、环、Mesh、Torus、树形拓扑、超立方体、Petersen图和GP(n,k)网络。
2.基于Petersen图,提出了GPN的网络结构,并对其特性进行了研究,证明了GPN网络具有正则性以及良好的可扩展性,同时还具有比RP(k)、2-D Torus更短的直径和良好的并行能力。另外,还基于GPN网络给出了路由算法,证明其具有较好的通信效率。
3.为得到更符合实际网络的网络模型,并将网络性质进一步提高,在GPN网络基础上,通过WS小世界模型构造算法与BA无标度模型构造算法对GPN网络进行修正,模拟修正后网络的平均路径长度和聚类系数,并将修正后网络的性质与规则GPN网络、随机GPN网络进行比对,得到修正后的GPN网络在平均路径长度和聚类系数方面分别具有更好的性质。
本文已经对GPN网络的一些基本性质作了研究,并进行了动态修正,但是仍有很多工作需要继续,主要是:
1.进一步分析GPN网络的各种性质,如可分组性,并且给出网络的容错路由算法和自适应算法等。
2.应用其它模型构造算法对GPN网络进行修正,使网络的平均路径长度及聚类系数等性质更进一步提高,同时对现实网络的其它统计性质进行研究,并讨论网络修正后在这些统计性质上的提高。
With the development of computer networks and computing science, paralleling computer and interconnection networks, covering mathematics, computing science, information science and so on, are becoming one of the hotspots of computer science research. All kinds of interconnection networks with different topologies, such as Ring, Mesh, Hypercube, star topology network etc. have developed rapidly. In the interconnection networks with multiprocessor, it is an important standard to evaluate the efficient communication among different processors. Petersen graph is one of the common interconnection networks. It has the metrics of small diameter, symmetrical structure and simple path searching algorithms, etc., what is more, many interconnection networks with different topologies can be easily embedded in. Thus, it becomes one of the most important and attractive network models. In this thesis, based on the Petersen graph, the routing algorithms and dynamic correction of GPN are studied. Several aspects of work mainly to be done are as follows.
1. Elaborated the concept of parallel computer systems and classification, and then introduces parallel computer models, features, and common interconnection network topologies, including a linear array, ring, Mesh, Torus、tree topology, hypercube, Petersen graph and GP(n, k) graph.
2. GPN network structure is proposed based on Petersen graph, and its properties are studied, proving that the GPN network has the nature of regularity and good scalability, but also has a ratio of RP (k), 2-D Torus shorter diameter and good parallelism. In addition, routing algorithm is given based on GPN network, proving that it has better communication efficiency.
3. Modifies dynamically based on the GPN network, in order to obtain the network model in line with the actual network and further improve the nature of network. Rectifies the GPN network by the small world model constructed by WS and BA free model network construction algorithm GPN, simulates average path length and clustering coefficient of the network after correction, and checks the nature of the revised network.
This article has studied some basic properties of the GPN network. However, there are still a lot of work to continue, including mainly:
1. Further analyzes various natures of the GPN network, such as the nature of being grouped, and gives fault-tolerant routing algorithm and adaptive algorithm of the network.
2. Modifies the GPN network applying construction algorithm of other models, so as to make the network average path length and clustering coefficient nature of the further increase, meanwhile, concerns about other statistical properties of real networks, and reflectes in the amendments and simulation of the network.
1.阐述了并行计算机系统的概念和分类,然后详细介绍了并行计算机模型、特性以及常用的互连网络拓扑结构,包括一维线性阵列、环、Mesh、Torus、树形拓扑、超立方体、Petersen图和GP(n,k)网络。
2.基于Petersen图,提出了GPN的网络结构,并对其特性进行了研究,证明了GPN网络具有正则性以及良好的可扩展性,同时还具有比RP(k)、2-D Torus更短的直径和良好的并行能力。另外,还基于GPN网络给出了路由算法,证明其具有较好的通信效率。
3.为得到更符合实际网络的网络模型,并将网络性质进一步提高,在GPN网络基础上,通过WS小世界模型构造算法与BA无标度模型构造算法对GPN网络进行修正,模拟修正后网络的平均路径长度和聚类系数,并将修正后网络的性质与规则GPN网络、随机GPN网络进行比对,得到修正后的GPN网络在平均路径长度和聚类系数方面分别具有更好的性质。
本文已经对GPN网络的一些基本性质作了研究,并进行了动态修正,但是仍有很多工作需要继续,主要是:
1.进一步分析GPN网络的各种性质,如可分组性,并且给出网络的容错路由算法和自适应算法等。
2.应用其它模型构造算法对GPN网络进行修正,使网络的平均路径长度及聚类系数等性质更进一步提高,同时对现实网络的其它统计性质进行研究,并讨论网络修正后在这些统计性质上的提高。
With the development of computer networks and computing science, paralleling computer and interconnection networks, covering mathematics, computing science, information science and so on, are becoming one of the hotspots of computer science research. All kinds of interconnection networks with different topologies, such as Ring, Mesh, Hypercube, star topology network etc. have developed rapidly. In the interconnection networks with multiprocessor, it is an important standard to evaluate the efficient communication among different processors. Petersen graph is one of the common interconnection networks. It has the metrics of small diameter, symmetrical structure and simple path searching algorithms, etc., what is more, many interconnection networks with different topologies can be easily embedded in. Thus, it becomes one of the most important and attractive network models. In this thesis, based on the Petersen graph, the routing algorithms and dynamic correction of GPN are studied. Several aspects of work mainly to be done are as follows.
1. Elaborated the concept of parallel computer systems and classification, and then introduces parallel computer models, features, and common interconnection network topologies, including a linear array, ring, Mesh, Torus、tree topology, hypercube, Petersen graph and GP(n, k) graph.
2. GPN network structure is proposed based on Petersen graph, and its properties are studied, proving that the GPN network has the nature of regularity and good scalability, but also has a ratio of RP (k), 2-D Torus shorter diameter and good parallelism. In addition, routing algorithm is given based on GPN network, proving that it has better communication efficiency.
3. Modifies dynamically based on the GPN network, in order to obtain the network model in line with the actual network and further improve the nature of network. Rectifies the GPN network by the small world model constructed by WS and BA free model network construction algorithm GPN, simulates average path length and clustering coefficient of the network after correction, and checks the nature of the revised network.
This article has studied some basic properties of the GPN network. However, there are still a lot of work to continue, including mainly:
1. Further analyzes various natures of the GPN network, such as the nature of being grouped, and gives fault-tolerant routing algorithm and adaptive algorithm of the network.
2. Modifies the GPN network applying construction algorithm of other models, so as to make the network average path length and clustering coefficient nature of the further increase, meanwhile, concerns about other statistical properties of real networks, and reflectes in the amendments and simulation of the network.
引文
[1] Newman M E J. The structure and function of complex networks[J]. Society for Industrial and Applied Mathematics,2003,45:167-256.
[2] Lun Li, David Alderson, Reiko Tanaka, John C.Doyle, Walter Willinger. Towards a Theory of Scale-Free Graphs: Definition Properties and plications[J]. Internet Mathematics,2005.
[3] Marco Tomassini, Mario Giacobini, Christian Darabos. Evolution of Small-World Networks of Automata for Computation[J].PPSN VIII, LNCS, 2004,3242:672-681.
[4] M.R.Samatham, D.K.Pradhan. The de Bruijn multiprocessor network: A versatile parallel processing and sorting network for VLSI[J].IEEE Trans. on computers,1989. 38(4):567-581.
[5] S.B.Akers, D.Harel, and B.Krishnamurthy. The star graph: an attractive alternative to the n-cube[C].Proc. International Conference Parallel Processing,1987: 393-400.
[6] J.Opatrny, D.Sotteau, N.Srinivasan, and K.Thulasiraman[J].Dcc linear ongruential graphs:a new class of interconnection networks. IEEE Trans.Computer,1996,45(2). 56-164.
[7] Almasi and Gottlieb, Highly Parallel Computing[C].1989.
[8] M.J.Flyn. Some Computer Organizations and Their Effectiveness[J].IEEE Trans. Computers,1972,21(9):948-960.
[9] JoséDuato, Sudhakar Yalamanchili著.谢伦国,窦强等译.并行计算机互连网络技术——一种工程方法[M].北京:电子工业出版社,2004:121-123.
[10] Satoshi Fujita and Arthur M.Farley. Sparse Hypercube----A Minimal k-Line Broadcast Graph[J]. Proceedings of IPPS/SPDP’99, IEEE, San Juan, Puerto Pico. 1999:320-324.
[11] M.S.Chen, K.G.Shin and D.D.Kandlur. Addressing,routing and broadcasting in hexagonal mesh multiprocessors[J].IEEE.Trans.Comput., 1990,39:10-18.
[12] Y.Saad and M.Schultz. Topological Properties of Hypercubes[J]. IEEE Trans. Computers,1988,37: 867-872.
[13]汪小帆,李翔,陈关荣.复杂网络理论及其应用[M].北京:清华大学出版社, 2006:8-9.
[14] Wei Shi and Pradip K.Srimani. One to All Broadcast in Hyper Butterfly Networks[C]. Proceedings of the 5th International Conf. on High Performance Computing,1998:155-162.
[15] Sigurd L., Lillevik. The Touch stone 30 Gigaflop DELTA Prototype Q.F.Stoutand M.Wolfe, eds[C]. IEEE Proceedings of the Sixth Distributed Memory Computing Conference Portland,Oregon:IEEE Computer Society Press,1991:671-677.
[16] Lenosji D., Laudon J., Gharachorloo Ketal. The Stanford DASH multiprocessor [J]. IEEE Computer,1992,25(3):63-79.
[17] Intel A touchstone DELTA system description[R]. Technical Report, Intel Advanced Information, Intel Portland, Oregon, Intel Corporation, 1991.
[18] Seitz C.L.,The architecture and programming of the Amete Series 2010 multicomputer[A].G.C.Fox,eds,Proceedings third conference hypercube concurrent computers and applications[M].New York:ACM press,1998,:33-36.
[19] Michael A.Gallo,William M.Hancock著,王玉峰,邹仕洪,黄东晖,范锐译.计算机通信和网络技术[M].北京:人民邮电出版社,2007,332-334.
[20] Laurence E LaForge, Kirk F Korver, M Sami Fadali. What Designers of Bus and Network Architectures Should Know about Hypercubes[J].IEEE Transactions on Computers (S0018-9340),2003,52(4):525-544.
[21] Y.Saad,M.H.Shultz. Topological properties of hypercubes[J].IEEE Transactions on Computers,1988,C-37(7):867-872.
[22] A.Trew and G..Wilsom,editors.Past,Present,Parallel:A Survey of Available Parallel Computer Systems, 1991,4:125-147.
[23]刘有耀,韩俊刚.Torus连接Petersen图互连网络及路由算法[J].计算机科学,2009, 36(3):78-85.
[24] Chen Lijun,Low S H. Doyle J C Joint Congestion Control and Media Access Control Design for Ad Hoc Wireless Network[J].Infoeom,2005.
[25] Srivastava V,Motani M.Cross-Layer Design:A Survey and the Road Ahead[J]. IEEE Communications Magazine, 2005:112—119.
[26] Dimic G, Sidiropoulos N D, Zhang R. Medium Access Control—Physical Cross-Layer Design[J].IEEE Sig, Proc.2004,21(5):40-50.
[27] Singh AK,Iyer SATCP. Improving TCP performance over mobile wireless environments.Mobile and Wireless Communications Network[J].2002 of the 4th International Workshop. 2002:239—243.
[28]张玫.超立方体网络中基于LIP的广播容错路由算法[J].山东师范大学学报(自然科学版),2008,23(3):28-30.
[29] Das S.K., Ohring S., Baneriee A.K., Embedding into hyper Petersen Hypercube -like topology[J].VLSI Design,1995,2(4):335-351.
[30]刘方爱,刘志勇,乔香珍.一种实用的网络拓扑结构RP(k)及路由算法[J].中国科学(E辑), 2002.32(3):380-385.
[31]许丹,李翔,汪小帆.复杂网络病毒传播的局域控制研究[J].物理学报,2007, 56(3):1313-1317.
[32] Newman M E J. The structure and function of complex networks[J]. SIAM Review, 2003, 45: 167-256.
[33] Wats, D.J.. Small Worlds[J].Princeton, New Jersey: Princeton University Press, 1999.
[34]刘涛,陈忠,陈晓荣.复杂网络理论及其应用研究概述[J].系统工程, 2005,23(6):50-56.
[35] Albert R, Barabási A-L. Statistical mechanics of complex networks[J]. Reviews of Modern Physics, 2002,74: 47-97.
[36] Wats. Six Degrees: the Science of a Connected Age[J].Norton, New York, 2003.
[37] D.J.Wats, P.S.Dodds, M.E.J. Newman. Identity and search in social networks[J].Science, 2002,296:1302-1305.
[38] S.H.Strogatz.Exploring complex networks[J].Nature, 2001,410: 268-276.
[39] L. Da,F. Costa,F. A. Rodrigues,G. Travieso and P. R. Villas Boas[J].Advances in Physics, 2007,56(1):167.
[40]汪小帆,李翔,陈关荣.复杂网络理论及其应用[M].北京:清华大学出版社, 2006:8-9.
[41]何大韧,刘宗华,汪秉宏.复杂系统与复杂网络[M].北京:高等教育出版社,2009: 130-131.
[42] Watts D J, Strogatz S H. Collective dynamics of small-world networks[J].Nature,1998, 393(6684): 440-442.
[43] Barabási A-L, Albert R Emergence of scaling in random networks[J]. Science, 1999,286(5439): 509-512.
[44] Milo R, Shen-Orr S S, Itzkovitz S, et al. Network motifs: simple building blocks of complex networks[J]. Science, 2002, 298: 824–827.
[45] Shen-Orr S S, Milo R, Mangan S, et al. Network motifs in the transcriptional regulation network of Escherichia coli[J]. Nature Genet., 2002, 31: 64–68.
[46] Kashtan N, Itzkovitz S, Milo R et al. Topological Generalizations of network motifs[J]. Phys. Rev. E, 2004:134-137.
[47] Ravasz E, Somera A L, Mongru D A, et al. Hierarchical organization of modularity in metabolic networks[J]. Science, 2002, 297: 1551–1555.
[48] Milo R, et al. Superfamilies of evolved and designed networks[J]. Science, 2004, 303: 1538-1542.
[2] Lun Li, David Alderson, Reiko Tanaka, John C.Doyle, Walter Willinger. Towards a Theory of Scale-Free Graphs: Definition Properties and plications[J]. Internet Mathematics,2005.
[3] Marco Tomassini, Mario Giacobini, Christian Darabos. Evolution of Small-World Networks of Automata for Computation[J].PPSN VIII, LNCS, 2004,3242:672-681.
[4] M.R.Samatham, D.K.Pradhan. The de Bruijn multiprocessor network: A versatile parallel processing and sorting network for VLSI[J].IEEE Trans. on computers,1989. 38(4):567-581.
[5] S.B.Akers, D.Harel, and B.Krishnamurthy. The star graph: an attractive alternative to the n-cube[C].Proc. International Conference Parallel Processing,1987: 393-400.
[6] J.Opatrny, D.Sotteau, N.Srinivasan, and K.Thulasiraman[J].Dcc linear ongruential graphs:a new class of interconnection networks. IEEE Trans.Computer,1996,45(2). 56-164.
[7] Almasi and Gottlieb, Highly Parallel Computing[C].1989.
[8] M.J.Flyn. Some Computer Organizations and Their Effectiveness[J].IEEE Trans. Computers,1972,21(9):948-960.
[9] JoséDuato, Sudhakar Yalamanchili著.谢伦国,窦强等译.并行计算机互连网络技术——一种工程方法[M].北京:电子工业出版社,2004:121-123.
[10] Satoshi Fujita and Arthur M.Farley. Sparse Hypercube----A Minimal k-Line Broadcast Graph[J]. Proceedings of IPPS/SPDP’99, IEEE, San Juan, Puerto Pico. 1999:320-324.
[11] M.S.Chen, K.G.Shin and D.D.Kandlur. Addressing,routing and broadcasting in hexagonal mesh multiprocessors[J].IEEE.Trans.Comput., 1990,39:10-18.
[12] Y.Saad and M.Schultz. Topological Properties of Hypercubes[J]. IEEE Trans. Computers,1988,37: 867-872.
[13]汪小帆,李翔,陈关荣.复杂网络理论及其应用[M].北京:清华大学出版社, 2006:8-9.
[14] Wei Shi and Pradip K.Srimani. One to All Broadcast in Hyper Butterfly Networks[C]. Proceedings of the 5th International Conf. on High Performance Computing,1998:155-162.
[15] Sigurd L., Lillevik. The Touch stone 30 Gigaflop DELTA Prototype Q.F.Stoutand M.Wolfe, eds[C]. IEEE Proceedings of the Sixth Distributed Memory Computing Conference Portland,Oregon:IEEE Computer Society Press,1991:671-677.
[16] Lenosji D., Laudon J., Gharachorloo Ketal. The Stanford DASH multiprocessor [J]. IEEE Computer,1992,25(3):63-79.
[17] Intel A touchstone DELTA system description[R]. Technical Report, Intel Advanced Information, Intel Portland, Oregon, Intel Corporation, 1991.
[18] Seitz C.L.,The architecture and programming of the Amete Series 2010 multicomputer[A].G.C.Fox,eds,Proceedings third conference hypercube concurrent computers and applications[M].New York:ACM press,1998,:33-36.
[19] Michael A.Gallo,William M.Hancock著,王玉峰,邹仕洪,黄东晖,范锐译.计算机通信和网络技术[M].北京:人民邮电出版社,2007,332-334.
[20] Laurence E LaForge, Kirk F Korver, M Sami Fadali. What Designers of Bus and Network Architectures Should Know about Hypercubes[J].IEEE Transactions on Computers (S0018-9340),2003,52(4):525-544.
[21] Y.Saad,M.H.Shultz. Topological properties of hypercubes[J].IEEE Transactions on Computers,1988,C-37(7):867-872.
[22] A.Trew and G..Wilsom,editors.Past,Present,Parallel:A Survey of Available Parallel Computer Systems, 1991,4:125-147.
[23]刘有耀,韩俊刚.Torus连接Petersen图互连网络及路由算法[J].计算机科学,2009, 36(3):78-85.
[24] Chen Lijun,Low S H. Doyle J C Joint Congestion Control and Media Access Control Design for Ad Hoc Wireless Network[J].Infoeom,2005.
[25] Srivastava V,Motani M.Cross-Layer Design:A Survey and the Road Ahead[J]. IEEE Communications Magazine, 2005:112—119.
[26] Dimic G, Sidiropoulos N D, Zhang R. Medium Access Control—Physical Cross-Layer Design[J].IEEE Sig, Proc.2004,21(5):40-50.
[27] Singh AK,Iyer SATCP. Improving TCP performance over mobile wireless environments.Mobile and Wireless Communications Network[J].2002 of the 4th International Workshop. 2002:239—243.
[28]张玫.超立方体网络中基于LIP的广播容错路由算法[J].山东师范大学学报(自然科学版),2008,23(3):28-30.
[29] Das S.K., Ohring S., Baneriee A.K., Embedding into hyper Petersen Hypercube -like topology[J].VLSI Design,1995,2(4):335-351.
[30]刘方爱,刘志勇,乔香珍.一种实用的网络拓扑结构RP(k)及路由算法[J].中国科学(E辑), 2002.32(3):380-385.
[31]许丹,李翔,汪小帆.复杂网络病毒传播的局域控制研究[J].物理学报,2007, 56(3):1313-1317.
[32] Newman M E J. The structure and function of complex networks[J]. SIAM Review, 2003, 45: 167-256.
[33] Wats, D.J.. Small Worlds[J].Princeton, New Jersey: Princeton University Press, 1999.
[34]刘涛,陈忠,陈晓荣.复杂网络理论及其应用研究概述[J].系统工程, 2005,23(6):50-56.
[35] Albert R, Barabási A-L. Statistical mechanics of complex networks[J]. Reviews of Modern Physics, 2002,74: 47-97.
[36] Wats. Six Degrees: the Science of a Connected Age[J].Norton, New York, 2003.
[37] D.J.Wats, P.S.Dodds, M.E.J. Newman. Identity and search in social networks[J].Science, 2002,296:1302-1305.
[38] S.H.Strogatz.Exploring complex networks[J].Nature, 2001,410: 268-276.
[39] L. Da,F. Costa,F. A. Rodrigues,G. Travieso and P. R. Villas Boas[J].Advances in Physics, 2007,56(1):167.
[40]汪小帆,李翔,陈关荣.复杂网络理论及其应用[M].北京:清华大学出版社, 2006:8-9.
[41]何大韧,刘宗华,汪秉宏.复杂系统与复杂网络[M].北京:高等教育出版社,2009: 130-131.
[42] Watts D J, Strogatz S H. Collective dynamics of small-world networks[J].Nature,1998, 393(6684): 440-442.
[43] Barabási A-L, Albert R Emergence of scaling in random networks[J]. Science, 1999,286(5439): 509-512.
[44] Milo R, Shen-Orr S S, Itzkovitz S, et al. Network motifs: simple building blocks of complex networks[J]. Science, 2002, 298: 824–827.
[45] Shen-Orr S S, Milo R, Mangan S, et al. Network motifs in the transcriptional regulation network of Escherichia coli[J]. Nature Genet., 2002, 31: 64–68.
[46] Kashtan N, Itzkovitz S, Milo R et al. Topological Generalizations of network motifs[J]. Phys. Rev. E, 2004:134-137.
[47] Ravasz E, Somera A L, Mongru D A, et al. Hierarchical organization of modularity in metabolic networks[J]. Science, 2002, 297: 1551–1555.
[48] Milo R, et al. Superfamilies of evolved and designed networks[J]. Science, 2004, 303: 1538-1542.