基于Cayley图与小世界现象的网络拓扑结构研究
|
摘要
并行分布系统中，互连网络拓扑结构决定了网络的性能。许多基于Cayley图的互连网络模型被提出，如超立方体网络、Torus网络、蝶网络、de Bruijn和Kautz网络等。学者们一般是针对某种具体的网络结构进行研究，且大多采用直观的方法。由于互连网络表示符号的不同，经常会出现本质相同的网络结构被重复地提出，因此，有必要用基于Cayley图的研究方法来统一处理互连网络拓扑结构问题。
小世界网络因其具有高的聚集系数和小的网络直径而受到广泛关注。基于Cayley图可以构建具有确定性小世界特征的网络拓扑结构，研究证明，结合了Cayley图和小世界现象的网络拓扑结构上的算法简单高效。
本文的主要研究内容和创新点包括以下几个方面：
1．首先，使用群直积和半直积的方法，对一些现行的互连网络拓扑结构进行分析，对其构造的过程加以研究和分类；接着，拓展OTIS网络为SN网络，分析BSN网络与SN网络的关系，论证BSN网络和因子网的关系；最后，将BSN互连结构加以推广，生成更具普遍意义的MSN互连结构，对其拓扑性质、路由和广播算法、嵌入、节点不相交路径等方面做出相关研究。
2．对地铁网络进行了全耦合建模，对网络拓扑结构的度量指标进行了计算和分析，比如最短路径数目、节点的度分布情况、聚集系数、鲁棒性等方面。研究表明，基于全耦合的地铁网络拓扑结构具有小世界现象。通过对高密度换乘节点和偏远节点的分析，可以对地铁未来的规划提供有意义的数据作为参考。
3．使用Cayley图方法研究P2P覆盖网络，得到了一类符合小世界特性的Cayley图，并以此Cayley图作为P2P覆盖网络的静态拓扑，提出了一类具有小世界特征的P2P覆盖网络拓扑结构模型CHC。通过对比发现，CHC具有对称性好、聚集系数大、平均距离小等许多优势。
4.提出使用Cayley图作为虚拟拓扑的静态模型，利用Cayley图的高对称性，使得静态模型具有许多优秀的性质，例如，更简单的路由算法，更高的可靠性和容错性。并以WDM光网络和WMN无线网络为例，讨论Cayley图可以简化拓扑设计中的众多的约束条件，得到一些好的规律。
Performance of the network is determined by the topology of interconnection network inparallel distributed system. Many models of interconnection networks based on Cayley graphhave been proposed, such as hypercube, torus, butterfly, de Bruijn and Kautz networks.Most researches focused on a specific structure of the network intuitively. Some samenetwork structures are repeatedly proposed for different symbols. So it is necessary to use themethods based on Cayley graph to unify interconnection network topology.
Small-world network interests a lot of researcher for high clustering coefficient andsmall network diameter. Network Topology based on Cayley Graph can be constructed withdeterministic small-world characteristics. The algorithms are simple and efficient if thenetwork topology base on Cayley graph has small-world phenomenon.
The main contents and innovations include the following aspects:
1. First, some interconnection network topologies are studied and classified by directproduct or semidirect method. Second, OTIS is extended to SN. The relationship of SN andBSN is analyzed. The relationship of BSN and basis network is proved.Finally, more generalinterconnection structure—MSN is proposed by generalizing BSN. Many researches of MSNare in progress, such as topological properties, routing and broadcasting algorithms,embedding, node-disjoint paths, etc.
2. All-coupling model is designed for the subway network. Data were calculated andanalyzed by the network topology metrics, such as the number of shortest paths, node degreedistribution, clustering coefficient, robustness and so on. Research shows that theAll-coupling network topology of the subway has small-world phenomenon. Analysinghigh-density nodes and remote nodes, some advices can be provided to the subway company.
3. The Cayley graph with small-world characteristics can be static P2P overlay networktopology. CHC is proposed that its static topology model is Cayley graph. CHC has manyadvantages, such as good symmetry, high clustering coefficient and small average distance.
4. Cayley graph can be used as a virtual topology static model. Many good properties are found for good symmetry, such as simpler routing algorithm, higher reliability andfault-tolerant. In WDM optical networks and wireless mesh networks, Cayley graph can beused to simplify some constraints of topology design and some good law can be obtained.
小世界网络因其具有高的聚集系数和小的网络直径而受到广泛关注。基于Cayley图可以构建具有确定性小世界特征的网络拓扑结构，研究证明，结合了Cayley图和小世界现象的网络拓扑结构上的算法简单高效。
本文的主要研究内容和创新点包括以下几个方面：
1．首先，使用群直积和半直积的方法，对一些现行的互连网络拓扑结构进行分析，对其构造的过程加以研究和分类；接着，拓展OTIS网络为SN网络，分析BSN网络与SN网络的关系，论证BSN网络和因子网的关系；最后，将BSN互连结构加以推广，生成更具普遍意义的MSN互连结构，对其拓扑性质、路由和广播算法、嵌入、节点不相交路径等方面做出相关研究。
2．对地铁网络进行了全耦合建模，对网络拓扑结构的度量指标进行了计算和分析，比如最短路径数目、节点的度分布情况、聚集系数、鲁棒性等方面。研究表明，基于全耦合的地铁网络拓扑结构具有小世界现象。通过对高密度换乘节点和偏远节点的分析，可以对地铁未来的规划提供有意义的数据作为参考。
3．使用Cayley图方法研究P2P覆盖网络，得到了一类符合小世界特性的Cayley图，并以此Cayley图作为P2P覆盖网络的静态拓扑，提出了一类具有小世界特征的P2P覆盖网络拓扑结构模型CHC。通过对比发现，CHC具有对称性好、聚集系数大、平均距离小等许多优势。
4.提出使用Cayley图作为虚拟拓扑的静态模型，利用Cayley图的高对称性，使得静态模型具有许多优秀的性质，例如，更简单的路由算法，更高的可靠性和容错性。并以WDM光网络和WMN无线网络为例，讨论Cayley图可以简化拓扑设计中的众多的约束条件，得到一些好的规律。
Performance of the network is determined by the topology of interconnection network inparallel distributed system. Many models of interconnection networks based on Cayley graphhave been proposed, such as hypercube, torus, butterfly, de Bruijn and Kautz networks.Most researches focused on a specific structure of the network intuitively. Some samenetwork structures are repeatedly proposed for different symbols. So it is necessary to use themethods based on Cayley graph to unify interconnection network topology.
Small-world network interests a lot of researcher for high clustering coefficient andsmall network diameter. Network Topology based on Cayley Graph can be constructed withdeterministic small-world characteristics. The algorithms are simple and efficient if thenetwork topology base on Cayley graph has small-world phenomenon.
The main contents and innovations include the following aspects:
1. First, some interconnection network topologies are studied and classified by directproduct or semidirect method. Second, OTIS is extended to SN. The relationship of SN andBSN is analyzed. The relationship of BSN and basis network is proved.Finally, more generalinterconnection structure—MSN is proposed by generalizing BSN. Many researches of MSNare in progress, such as topological properties, routing and broadcasting algorithms,embedding, node-disjoint paths, etc.
2. All-coupling model is designed for the subway network. Data were calculated andanalyzed by the network topology metrics, such as the number of shortest paths, node degreedistribution, clustering coefficient, robustness and so on. Research shows that theAll-coupling network topology of the subway has small-world phenomenon. Analysinghigh-density nodes and remote nodes, some advices can be provided to the subway company.
3. The Cayley graph with small-world characteristics can be static P2P overlay networktopology. CHC is proposed that its static topology model is Cayley graph. CHC has manyadvantages, such as good symmetry, high clustering coefficient and small average distance.
4. Cayley graph can be used as a virtual topology static model. Many good properties are found for good symmetry, such as simpler routing algorithm, higher reliability andfault-tolerant. In WDM optical networks and wireless mesh networks, Cayley graph can beused to simplify some constraints of topology design and some good law can be obtained.
引文
[1] S.B.Akers, B.Krishnamurthy. Group graphs as interconnection networks[A],In Proc,14thInt. Conf. Fault Tolerant Comput.,1984:422-427.
[2] S.B.Akers, B. Krishnamurthy. A Group Theoretic Model for Symmetric InterconnectionNetworks[J]. IEEE Trans. Computers,1989,38(4):555-566.
[3] M. Heydemann. Cayley Graphs and Interconnection Networks in Graph Symmetry:Algebraic Methods and Applications[M]. Kluwer Academic,1997:167-224.
[4] Lakshmivarahan, L.S., Jung-Sing Jwo, Dall, S.K..Symmetry in interconnection networkbased on Cayley graphs of permutation groups: A survey[J]. Parallel Computing,1993,19(4):361-407.
[5] G.Cooperman, L.Finkelstein, N.Sarawagi. Application of Cayley graphs[M], NewYork:Springer,1991:367-378.
[6] G.Cooperman, L.Finkelstein. New methods for using Cayley graphs in interconnectionnetworks[J]. Special issue on interconnection networks, Discrete Appl. Math.,1992,37-38:95-118.
[7] Godsil C., Royle G.: Algebraic Graph Theory [M]. New York:Springer-Verlag,2001.
[8]徐明曜,黄建华,李慧陵,李世荣.有限群导引(下)[M].北京:科学出版社,1999.
[9]徐俊明.组合网络理论[M].北京:科学出版社,2007.
[10] Rowstron A.,Druschel P.. Pastry: Scalable, Distributed Object Location and Routing forLarge-Scale Peer-to-Peer Systems [C]. Proc. IFIP/ACM Int. Conf. Distributed SystemsPlatforms (Middleware), Heidelberg, Germany.2001.
[11] Adar E, Huberman BA. Freeriding on gnutella[R]. Palo Alto: Technical Report,SSL-00-63, Internet Ecologies Area Xerox Palo Alto Research Center.2002.
[12] Ion Stoiea, Robert Morris, David Karge. Chord: A scalable Peer-to-Peer lookup servicefor internet applications [A]. Proeeeding of ACM SIGCOMM2001-Applications,Technologies, Architectures, and Protocols for Computers Communications[C]. NewYork: Association for Computing Machinery.2001:149-160.
[13] S. Ratnasamy, P. Francis, M. Handley, et. Al. A Scalable Content Addressable Network[C], Proc. Annual Conf. ACM Special Interest Group on Data Communications(SIGCOMM).USA.2001.
[14] B. Y. Zhao, L. Huang, J. Stribling, et. al., Tapestry: A Resilient Global-Scale Overlayfor Service Deployment[J].IEEE J. Selected Areas in Communications.2004,22(1):41-53.
[15] D. J. Watts, S. H. Strogatz. Collective Dynamics of ‘Small-world’ Networks[J]. Nature,1998,393(4):440-442.
[16]汪小帆,李翔,陈关荣.复杂网络理论及其应用[M]．北京:清华出版社,2006.
[17] F. Comellas, J. Ozón, J. G. Peters. Deterministic small world communicationnetworks[J]. Inf. Process. Lett.,2000,76:83-90.
[18] F. Comellas, M. Sampels. Deterministic small world networks[J]. Phys. A.2002,309:231-235.
[19] Z.Z Zhang, L.L Rong, C.H Guo. A deterministic small world network created by edgeiterations[J]. Phys. A.2006,39:3253-3261.
[20] W.J. Xiao, B. Parhami. Cayley graphs as models of deterministic small worldnetworks[J]. Inf. Process. Lett..2006,97:115-117.
[21] B.Parhami. Introduction to parallel Processing: Algorithms and Architectures[M].Plenum,1999:292-294.
[22] Biggs N.L. Algebraic Graph Theory[M].2nd Ed.Cambridge University Press,1993.
[23] Wu F. L., Lakshmivarahan S., and Dhall S. K. Routing in a Class of Cayley Graph ofSemidirect Products of Finite Groups [J]. J. of Parallel and Distributed Computing,2000,60:539-565.
[24] S. Lakshmivarahan and Sudarshan K. Dhall. Ring, torus and hypercube architectures/algorithms for parallel computing[J]. Parallel Computing，1999,25(13-14):1877-1906.
[25] Zheng S.Q., Wu jie. Dual of a complete graph as an interconnection network [J].Journal of Parallel and Distributed Computing,2000,60(9):1028-1046.
[26] Wenjun Xiao, B.Parhami. Some mathematical properties of Cayley digraphs withapplications to interconnection network design[J]. International Journal of ComputerMathematics.2005,82(5):521-528.
[27]陈宝兴.基于Cayley图的互连网络的研究[D].博士学位论文,厦门大学,2004.
[28]周书明.互连网络的拓扑结构分析和容错性分析[D].博士学位论文,厦门大学,2005
[29] Behrooz Parhami. Swapped interconnection networks: Topological, performance, androbustness attributes[J]. J. Parallel Distrib. Comput.,2005,65(1):1443-1452.
[30] Wang C.F., Sahni S. Basic Operations on the OTIS-Mesh Optoelectronic Computer [J].IEEE Trans. Parallel and Distributed Systems,1998,9(12):1226-1236.
[31] Zane F., Marchand P., Paturi R., Esener S. Scalable Network Architectures Using theOptical Transpose Interconnection System (OTIS)[J]. J. Parallel and DistributedComputing,2000,60(5):521–538.
[32] Day K., Al-Ayyoub A. E.. Topological properties of OTIS-Networks [J]. IEEETransactions on Parallel and Distributed Systems,2002,13(4):359-366.
[33] Parhami B. The Hamiltonicity of Swapped (OTIS) Networks Built of HamiltonianComponent Networks [J]. Information Processing Letters,2005,95:441-445.
[34]胡冠章，王殿军.应用近世代数[M].第3版,北京:清华大学出版社,2006.
[35] Jie Wu. A Adaptive Fault-Tolerant Routing in Cube-Based Multicomputers UsingSafety Vectors[J]. IEEE Trans. On parallel and Distributed Systems,1998,9(4):321-334
[36] Jie Wu. Satety Levels-An Efficient Mechanism for Achiveing Reliable Broadcasting inHypercubes[J], IEEE Trans. Computers,1995,44(5):702-706.
[37] Jie Wu.Reliable Unicasting in Faulty Hypercubes Using Safety Levels[J], IEEE Trans.On Computers,1997,46(2):241-247.
[38] Jie Wu. Optimal broadcasting in injured hypercubes using directed safety levels[J],Journal of parallel and Distributed Computing,2003,63(9):815-826.
[39] Jie Wu, Kejun Yo. A limited-information-based Multicasting Scheme for FaultyHypercubes[J]. IEEE Trans.On Computers,1995,44(9):1162-1167.
[40] D.Meliksetian, C.chen. optimal routing algorithm and the diameter of thecube-connected cycles[J]. IEEE Trans. Parallel Distributed Systems,1993,4(10):1172-1178.
[41]王雷，林亚平，陈治平等.超立方体中基于极大安全通路矩阵的容错路由[J].软件学报，2004,15(7):47-57.
[42] Decayeux, C.; Seme.D.3D hexagonal network: modeling, topological properties,addressing scheme, and optimal routing algorithm[J]. Parallel and Distributed Systems,IEEE Transactions on,2005,16(9):875-884.
[43] Huaxi GU, Jie ZHANG, Zengji LIU and Xiaoxing TU. Routing in Hexagonal Networksunder a Corner-Based Addressing Scheme[J]. IEICE Transactions on Information andSystems,2006,89(5):1755-1758.
[44] W.Xiao, B.Parhami. Hexagonal and pruned tours networks as Cayley graphs[C],Proceedings of the internat. Conf. on communication in computing, CIC’04,2004:107-112.
[45] Mingxin He, Wenjun Xiao. A unified Addressing Schema for Hexagonal andHoneycomb Networks with Isomorphic Cayley Graphs[C]. Proceedings of the FirstInternational Multi-Symposiums on Computer and Computational Sciences(IMSCCS’06),2006:486-492.
[46] Stojmenovic I. Honeycomb Networks: Topological Properties and CommunicationAlgorithms [J]. IEEE Trans. Parallel and Distributed Systems.1997,8(10):1036-1042.
[47] Stojmenovic I. Honeycomb Networks: Topological Properties and CommunicationAlgorithms [J].IEEE Trans. Parallel and Distributed Systems.1997,8(10):1036-1042.
[48] B.Parhami, D.M.Kwai, A unified formulation of honeycomb and diamond networks[J].IEEE Trans. Parallel Distrib. Systems,2001,12(1):74-79.
[49] Wenjun Xiao, B.Parhami. Some General Properties of Cayley Digraphs withApplication to Interconnection Networks[J]. Int. J. Comput. Math.2005,82(5):521-528.
[50] D-M, Kwai, B.Parhami. A Class of Fixed-Degree Cayley-Graph InterconnectionNetworks Derived by Pruning K-Ary n-cubes[C]. Proc.Int’l Conf. parallel andDistributed Computing and Systems,1999,9:19-22.
[51] D-M.Kwai, B.Parhami. Pruned three-dimensional toridal networks[J]. InformationProcessing Letters,1998,68(4):179-183.
[52] Wenjun Xiao, B.parhami. A Group Construction Method with Applications to DerivingPruned Interconnection Networks[J]. IEEE Trans. Parallel Distrib. Syst.2007,18(5):637-643.
[53] Shu-Ming Zhou, Wen-Jun Xiao. A New Family of Interconnection Networks of FixedDegree Three[J]. Journal of Computer Science and Technology,2004,l(2):31-39.
[54] Marsden G., Marsden P., Harvey P., and Esener S.. Optical Transpose InterconnectionSystem Architecture [J]. Optical Letters,1993,18:1083-1085.
[55] C.-H. Yeh and B. Parhami. Swapped Networks: Unifying the Architectures andAlgorithms of a Wide Class of Hierarchical Parallel Processors[C], Proc. InternationalConf. Parallel and Distributed Systems,1996,6:230-237.
[56] A. Krishnamoorthy, P. Marchand, F. Kiamilev, S. Esener. Grain-size considerations foroptoelectronic multistage interconnection networks [J]. Applied Optics,1992,31(26):5480–5507.
[57] S. Rajasekaran, S. Sahni. Randomized routing. Selection and sorting on the OTIS-Mesh[J].IEEE Transactions on Parallel and Distributed Systems,1998,9(9):833–840.
[58] K. Day. Optical transpose k-ary n-cube networks [J]. Journal of system architecture,2004,50:697-705.
[59] D. Coudert, A. Ferreira, S. Perennes. De Bruijn, Isomorphisms and free space opticalnetworks[C]. In: IEEE International Parallel and Distributed Processing Symposium,IPDPS2000,2000:769-774.
[60] D. Coudert, A. Ferreira, X. Mu oz. Topologies for optical interconnection networksbased on the optical transpose interconnection system [J]. Applied Optics—IP,2000:39(17):2965-2974.
[61] Wenjun Xiao et al.The Properties of Biswapped-Networks[J].SNPD (2),2007:193-198.
[62] Latora V, Marchiori M. Is the Boston subway a small-world network[J]. PhysicaA.2002,314(1/4):109-113.
[63] Sen Parongama et al. Small-world properties of the Indian railway network[J].Physical Review E-Statistical, Nonlinear, and Soft Matter Physics,2003,67(32).
[64] Seaton K A, Hackett L M. Station, trains and small-world networks[J]. PhysicalA,2004,339(3/4):635-644.
[65] Angeloudis P, Fisk D. Large subway systems as complex networks[J]. Physica A,2006,367(2):553-558.
[66] B.Y.Zhao, L.Huang, J.Stribling, et.al., Tapestry: A Resilient Global-scale Overlay forService Deployment[J]. IEEE Journal on Selected Areas in Communications,2004,22(1):41-53.
[67] A. Kumar, S. Merugu, J. Xu, X. Yu. Ulysses: A robust, low-diameter, low-latencypeer-to-peer network[J]. European transaction on telecommunications,2004,15(6):571-587.
[68] D. Malkhi, M. Naor, D. Ratajczak. Viceroy: A scalable and dynamic emulation of thebutterfly[C]. Proc. of ACM PODC,2002.
[69] J. Xu. On the fundamental tradeoffs between routing table size and network diameter inpeer-to-peer networks[C]. Proc. of IEEE Infocom2003,2003(1-3):2177-2187.
[70] C. Qu, W. Nejdl, M. Kriesell. Cayley DHTs–A Group-Theoretic Framework forAnalyzing DHTs Based on Cayley Graphs[C], Proc.2nd International Symp. Paralleland Distributed Processing and Applications (ISPA),2004.
[71] K. Aberer, L. O. Alima, A. Ghodsi, S. Girdzijauskas, S. Haridi, and M. Hauswirh. Theessence of p2p: a reference architecture for overlay networks[C]. Fifth IEEEInternational Conference on Peer-to-Peer Computing,2005.
[72] W. Xiao, B. Parhami, Cayley Graph as Models of Deterministic Small-WorldNetworks[J]. Information Processing Letters,2006,97(3):115-117.
[73] F.T. Leighton. Introduction to Parallel Algorithms and Architectures: Arrays, Trees,Hypercubes[M], Morgan Kaufmann,1992.
[74] F.G. Nocetti, I. Stojmenovic, J. Zhang. Addressing and Routing in HexagonalNetworks with Applications for Tracking Mobile Users and Connection Rerouting inCellular Networks[J]. IEEE Trans. Parallel and Distributed Systems,2002,13(9):963-971.
[75] B. Parhami, D.M. Kwai. Incomplete k-ary n-cube and Its Derivatives[J]. Parallel andDistributed Computing,2004,64(2):183-190.
[76] B. Stong. On Hamiltonian cycles in Cayley Graphs of Wreath Products[J]. DiscreteMathematics,1987,65:75-80.
[77] W.J. Xiao, W.D. Chen, M.X. He, W.H. Wei, B. Parhami. Biswapped Networksand Their Topological Properties[C].8th ACIS International Conference on SoftwareEngineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing(SNPD2007),2007:193-198.
[78] Chen, G. H., Duh, D. R.. Topological properties, communication and computation onWK-recursive networks[J]. Networks,1994,24(6):303-317.
[79] Su Ming-Ying, Chen Gen-Huey, Duh Dyi-Rong. Broadcasting on incompleteWK-recursive networks[J]. Journal of Parallel and Distributed Computing,1999,57:217-224.
[80] Fernandes,R.,Kanevsky,A.. Generalized ring interconnection networks[C]. TheProceedings of1994International Conference on Parallel Processing,IEEE,1994:30-34.
[81] Das, S.K., Ohring, S., Banerice, A. K.. Embedding into hyper Petersen network: yetanother Hypercube-like topology[J]. Journal of VLSI Design,1995,2(4):335-351.
[82] Yeh, Chi-Hsiang, Parhami Behrooz. Routing and embeddings in cyclic Petersennetwork: an efficient extension of the Petersen graph[C]. Proc of Int’l Conf on ParallelProcessing, IEEE, Japan,1999:258-265.
[83] Howard Jay Siegel. Interconnection Networks for Large Scale Parallel Processing[M].New York: McGraw-Hill Publishing Company,1990.
[84] Parhami Behrooz, Chi-Hsiang Yeh. Why network diameter is still important[C]. ProcInternational Conference on Communications, Las Vegas,USA,2000:26-29.
[85] Xiao W.J., Parhami B..Further Mathematical Properties of Cayley Digraphs Applied toHexagonal and Honeycomb Meshes [J]. Discrete Applied mathematics,2007,155(13):1752-1760.
[86]刘方爱,刘志勇,乔香珍.一种实用的互连网络拓扑结构RP(k)及路由算法.中国科学(E辑),2002,32(3):380-385.
[87] Liu Fang’ai,Liu Zhiyong, Qiao Xiangzhen. A practical interconnection network RP(k)and its routig algorithms[J]. Science in China (Series F),2001,44(6):461-473.
[88] J.A.Bondy and U.S.R.Murty. Group Theory with Applications[M]. New York: NorthHolland,1979.
[89]刘方爱,刘志勇,乔香珍.一类层次环网络的构造及路由算法[J].计算机学报,2002,25(12):1397-1404.
[90]刘方爱,刘志勇,张永胜.环、mesh嵌入RP(k)网络[J].中国科学（E辑,信息科学）2004,34(8):939-950.
[91]王雷,林亚平,陈治平等.二维环/双环连接Petersen图网络及其路由算法[J].计算机学报,2004,27(9):1290-1296.
[92]王雷,林亚平.基于超立方体环连接的Petersen图互连网络研究[J].计算机学报,2005,28(3):409-413.
[93]王雷,林亚平,夏巍.双环Petersen图互连网络及其路由算法[J].软件学报,2006,17(5):1115-1123.
[94] Behrooz Parhami. The Hamiltonicity of swapped (OTIS) networks built of Hamiltoniancomponent networks[J]. Information Processing Letters,2005,95:441-445.
[95] J.S.Fu, G.H.Chen, Hemiltonicity of the hierarchical cubic network[J], Theory Comput.Systems,2002,35:59-79.
[96] Yeh, Chi-Hsiang, Parhami Behrooz. Hierarchical swapped networks: Efficientlow-degree alternatives to Hypercube and generalized Hypercubes[C]. ProcInternational Symposium on Parallel Architectures, Algorithms, and Networks, Beijing,1996:90-96.
[97] Behrooz Parhami. The Hamiltonicity of swapped (OTIS) networks built of Hamiltoniancomponent networks[J]. Information Processing Letters,2005,95:441-445.
[98] K. Sripanidkulchai, B. Maggs, H. Zhang. Effcient content location using interest-basedlocality in peer-to-peer systems[C]. Proc. of IEEE Infocom2003: The conference oncomputer communications,2003(1-3):2166–2176.
[99] B. Mukherjee. Optical WDM Networks[M]. Springer,2006.
[100] Mohsenian-Rad, A. H. Joint logical topology design, interface assignment, channelallocation, and routing for multi-channel wireless mesh networks[J]. IEEE Trans.Wireless Communications,2007,6(12):4432-4440.
[101] Akyildiz I.F., Wang X., Wang W. Wireless mesh networks: a survey [J]. Computernetworks,2005,47(4):445-487.
[102]欧中洪,宋美娜,战晓苏等.移动对等网络关键技术[J].软件学报,2008,19(2):404-418.
[103] Jun Jangeun, Sichitiu M.L. The nominal capacity of wireless mesh networks [J].Wireless Communications,2003,10(5):8-14.
[104] Ashish R., Chiueh Tzi-cker. Architecture and algorithms for an IEEE802.11-basedmulti-channel wireless mesh network [A]. Proceedings IEEE24th Annual JointConference of the IEEE Computer and Communications Societies [C]. Washington:IEEE Computer Society,2005:2223-2234.
[2] S.B.Akers, B. Krishnamurthy. A Group Theoretic Model for Symmetric InterconnectionNetworks[J]. IEEE Trans. Computers,1989,38(4):555-566.
[3] M. Heydemann. Cayley Graphs and Interconnection Networks in Graph Symmetry:Algebraic Methods and Applications[M]. Kluwer Academic,1997:167-224.
[4] Lakshmivarahan, L.S., Jung-Sing Jwo, Dall, S.K..Symmetry in interconnection networkbased on Cayley graphs of permutation groups: A survey[J]. Parallel Computing,1993,19(4):361-407.
[5] G.Cooperman, L.Finkelstein, N.Sarawagi. Application of Cayley graphs[M], NewYork:Springer,1991:367-378.
[6] G.Cooperman, L.Finkelstein. New methods for using Cayley graphs in interconnectionnetworks[J]. Special issue on interconnection networks, Discrete Appl. Math.,1992,37-38:95-118.
[7] Godsil C., Royle G.: Algebraic Graph Theory [M]. New York:Springer-Verlag,2001.
[8]徐明曜,黄建华,李慧陵,李世荣.有限群导引(下)[M].北京:科学出版社,1999.
[9]徐俊明.组合网络理论[M].北京:科学出版社,2007.
[10] Rowstron A.,Druschel P.. Pastry: Scalable, Distributed Object Location and Routing forLarge-Scale Peer-to-Peer Systems [C]. Proc. IFIP/ACM Int. Conf. Distributed SystemsPlatforms (Middleware), Heidelberg, Germany.2001.
[11] Adar E, Huberman BA. Freeriding on gnutella[R]. Palo Alto: Technical Report,SSL-00-63, Internet Ecologies Area Xerox Palo Alto Research Center.2002.
[12] Ion Stoiea, Robert Morris, David Karge. Chord: A scalable Peer-to-Peer lookup servicefor internet applications [A]. Proeeeding of ACM SIGCOMM2001-Applications,Technologies, Architectures, and Protocols for Computers Communications[C]. NewYork: Association for Computing Machinery.2001:149-160.
[13] S. Ratnasamy, P. Francis, M. Handley, et. Al. A Scalable Content Addressable Network[C], Proc. Annual Conf. ACM Special Interest Group on Data Communications(SIGCOMM).USA.2001.
[14] B. Y. Zhao, L. Huang, J. Stribling, et. al., Tapestry: A Resilient Global-Scale Overlayfor Service Deployment[J].IEEE J. Selected Areas in Communications.2004,22(1):41-53.
[15] D. J. Watts, S. H. Strogatz. Collective Dynamics of ‘Small-world’ Networks[J]. Nature,1998,393(4):440-442.
[16]汪小帆,李翔,陈关荣.复杂网络理论及其应用[M]．北京:清华出版社,2006.
[17] F. Comellas, J. Ozón, J. G. Peters. Deterministic small world communicationnetworks[J]. Inf. Process. Lett.,2000,76:83-90.
[18] F. Comellas, M. Sampels. Deterministic small world networks[J]. Phys. A.2002,309:231-235.
[19] Z.Z Zhang, L.L Rong, C.H Guo. A deterministic small world network created by edgeiterations[J]. Phys. A.2006,39:3253-3261.
[20] W.J. Xiao, B. Parhami. Cayley graphs as models of deterministic small worldnetworks[J]. Inf. Process. Lett..2006,97:115-117.
[21] B.Parhami. Introduction to parallel Processing: Algorithms and Architectures[M].Plenum,1999:292-294.
[22] Biggs N.L. Algebraic Graph Theory[M].2nd Ed.Cambridge University Press,1993.
[23] Wu F. L., Lakshmivarahan S., and Dhall S. K. Routing in a Class of Cayley Graph ofSemidirect Products of Finite Groups [J]. J. of Parallel and Distributed Computing,2000,60:539-565.
[24] S. Lakshmivarahan and Sudarshan K. Dhall. Ring, torus and hypercube architectures/algorithms for parallel computing[J]. Parallel Computing，1999,25(13-14):1877-1906.
[25] Zheng S.Q., Wu jie. Dual of a complete graph as an interconnection network [J].Journal of Parallel and Distributed Computing,2000,60(9):1028-1046.
[26] Wenjun Xiao, B.Parhami. Some mathematical properties of Cayley digraphs withapplications to interconnection network design[J]. International Journal of ComputerMathematics.2005,82(5):521-528.
[27]陈宝兴.基于Cayley图的互连网络的研究[D].博士学位论文,厦门大学,2004.
[28]周书明.互连网络的拓扑结构分析和容错性分析[D].博士学位论文,厦门大学,2005
[29] Behrooz Parhami. Swapped interconnection networks: Topological, performance, androbustness attributes[J]. J. Parallel Distrib. Comput.,2005,65(1):1443-1452.
[30] Wang C.F., Sahni S. Basic Operations on the OTIS-Mesh Optoelectronic Computer [J].IEEE Trans. Parallel and Distributed Systems,1998,9(12):1226-1236.
[31] Zane F., Marchand P., Paturi R., Esener S. Scalable Network Architectures Using theOptical Transpose Interconnection System (OTIS)[J]. J. Parallel and DistributedComputing,2000,60(5):521–538.
[32] Day K., Al-Ayyoub A. E.. Topological properties of OTIS-Networks [J]. IEEETransactions on Parallel and Distributed Systems,2002,13(4):359-366.
[33] Parhami B. The Hamiltonicity of Swapped (OTIS) Networks Built of HamiltonianComponent Networks [J]. Information Processing Letters,2005,95:441-445.
[34]胡冠章，王殿军.应用近世代数[M].第3版,北京:清华大学出版社,2006.
[35] Jie Wu. A Adaptive Fault-Tolerant Routing in Cube-Based Multicomputers UsingSafety Vectors[J]. IEEE Trans. On parallel and Distributed Systems,1998,9(4):321-334
[36] Jie Wu. Satety Levels-An Efficient Mechanism for Achiveing Reliable Broadcasting inHypercubes[J], IEEE Trans. Computers,1995,44(5):702-706.
[37] Jie Wu.Reliable Unicasting in Faulty Hypercubes Using Safety Levels[J], IEEE Trans.On Computers,1997,46(2):241-247.
[38] Jie Wu. Optimal broadcasting in injured hypercubes using directed safety levels[J],Journal of parallel and Distributed Computing,2003,63(9):815-826.
[39] Jie Wu, Kejun Yo. A limited-information-based Multicasting Scheme for FaultyHypercubes[J]. IEEE Trans.On Computers,1995,44(9):1162-1167.
[40] D.Meliksetian, C.chen. optimal routing algorithm and the diameter of thecube-connected cycles[J]. IEEE Trans. Parallel Distributed Systems,1993,4(10):1172-1178.
[41]王雷，林亚平，陈治平等.超立方体中基于极大安全通路矩阵的容错路由[J].软件学报，2004,15(7):47-57.
[42] Decayeux, C.; Seme.D.3D hexagonal network: modeling, topological properties,addressing scheme, and optimal routing algorithm[J]. Parallel and Distributed Systems,IEEE Transactions on,2005,16(9):875-884.
[43] Huaxi GU, Jie ZHANG, Zengji LIU and Xiaoxing TU. Routing in Hexagonal Networksunder a Corner-Based Addressing Scheme[J]. IEICE Transactions on Information andSystems,2006,89(5):1755-1758.
[44] W.Xiao, B.Parhami. Hexagonal and pruned tours networks as Cayley graphs[C],Proceedings of the internat. Conf. on communication in computing, CIC’04,2004:107-112.
[45] Mingxin He, Wenjun Xiao. A unified Addressing Schema for Hexagonal andHoneycomb Networks with Isomorphic Cayley Graphs[C]. Proceedings of the FirstInternational Multi-Symposiums on Computer and Computational Sciences(IMSCCS’06),2006:486-492.
[46] Stojmenovic I. Honeycomb Networks: Topological Properties and CommunicationAlgorithms [J]. IEEE Trans. Parallel and Distributed Systems.1997,8(10):1036-1042.
[47] Stojmenovic I. Honeycomb Networks: Topological Properties and CommunicationAlgorithms [J].IEEE Trans. Parallel and Distributed Systems.1997,8(10):1036-1042.
[48] B.Parhami, D.M.Kwai, A unified formulation of honeycomb and diamond networks[J].IEEE Trans. Parallel Distrib. Systems,2001,12(1):74-79.
[49] Wenjun Xiao, B.Parhami. Some General Properties of Cayley Digraphs withApplication to Interconnection Networks[J]. Int. J. Comput. Math.2005,82(5):521-528.
[50] D-M, Kwai, B.Parhami. A Class of Fixed-Degree Cayley-Graph InterconnectionNetworks Derived by Pruning K-Ary n-cubes[C]. Proc.Int’l Conf. parallel andDistributed Computing and Systems,1999,9:19-22.
[51] D-M.Kwai, B.Parhami. Pruned three-dimensional toridal networks[J]. InformationProcessing Letters,1998,68(4):179-183.
[52] Wenjun Xiao, B.parhami. A Group Construction Method with Applications to DerivingPruned Interconnection Networks[J]. IEEE Trans. Parallel Distrib. Syst.2007,18(5):637-643.
[53] Shu-Ming Zhou, Wen-Jun Xiao. A New Family of Interconnection Networks of FixedDegree Three[J]. Journal of Computer Science and Technology,2004,l(2):31-39.
[54] Marsden G., Marsden P., Harvey P., and Esener S.. Optical Transpose InterconnectionSystem Architecture [J]. Optical Letters,1993,18:1083-1085.
[55] C.-H. Yeh and B. Parhami. Swapped Networks: Unifying the Architectures andAlgorithms of a Wide Class of Hierarchical Parallel Processors[C], Proc. InternationalConf. Parallel and Distributed Systems,1996,6:230-237.
[56] A. Krishnamoorthy, P. Marchand, F. Kiamilev, S. Esener. Grain-size considerations foroptoelectronic multistage interconnection networks [J]. Applied Optics,1992,31(26):5480–5507.
[57] S. Rajasekaran, S. Sahni. Randomized routing. Selection and sorting on the OTIS-Mesh[J].IEEE Transactions on Parallel and Distributed Systems,1998,9(9):833–840.
[58] K. Day. Optical transpose k-ary n-cube networks [J]. Journal of system architecture,2004,50:697-705.
[59] D. Coudert, A. Ferreira, S. Perennes. De Bruijn, Isomorphisms and free space opticalnetworks[C]. In: IEEE International Parallel and Distributed Processing Symposium,IPDPS2000,2000:769-774.
[60] D. Coudert, A. Ferreira, X. Mu oz. Topologies for optical interconnection networksbased on the optical transpose interconnection system [J]. Applied Optics—IP,2000:39(17):2965-2974.
[61] Wenjun Xiao et al.The Properties of Biswapped-Networks[J].SNPD (2),2007:193-198.
[62] Latora V, Marchiori M. Is the Boston subway a small-world network[J]. PhysicaA.2002,314(1/4):109-113.
[63] Sen Parongama et al. Small-world properties of the Indian railway network[J].Physical Review E-Statistical, Nonlinear, and Soft Matter Physics,2003,67(32).
[64] Seaton K A, Hackett L M. Station, trains and small-world networks[J]. PhysicalA,2004,339(3/4):635-644.
[65] Angeloudis P, Fisk D. Large subway systems as complex networks[J]. Physica A,2006,367(2):553-558.
[66] B.Y.Zhao, L.Huang, J.Stribling, et.al., Tapestry: A Resilient Global-scale Overlay forService Deployment[J]. IEEE Journal on Selected Areas in Communications,2004,22(1):41-53.
[67] A. Kumar, S. Merugu, J. Xu, X. Yu. Ulysses: A robust, low-diameter, low-latencypeer-to-peer network[J]. European transaction on telecommunications,2004,15(6):571-587.
[68] D. Malkhi, M. Naor, D. Ratajczak. Viceroy: A scalable and dynamic emulation of thebutterfly[C]. Proc. of ACM PODC,2002.
[69] J. Xu. On the fundamental tradeoffs between routing table size and network diameter inpeer-to-peer networks[C]. Proc. of IEEE Infocom2003,2003(1-3):2177-2187.
[70] C. Qu, W. Nejdl, M. Kriesell. Cayley DHTs–A Group-Theoretic Framework forAnalyzing DHTs Based on Cayley Graphs[C], Proc.2nd International Symp. Paralleland Distributed Processing and Applications (ISPA),2004.
[71] K. Aberer, L. O. Alima, A. Ghodsi, S. Girdzijauskas, S. Haridi, and M. Hauswirh. Theessence of p2p: a reference architecture for overlay networks[C]. Fifth IEEEInternational Conference on Peer-to-Peer Computing,2005.
[72] W. Xiao, B. Parhami, Cayley Graph as Models of Deterministic Small-WorldNetworks[J]. Information Processing Letters,2006,97(3):115-117.
[73] F.T. Leighton. Introduction to Parallel Algorithms and Architectures: Arrays, Trees,Hypercubes[M], Morgan Kaufmann,1992.
[74] F.G. Nocetti, I. Stojmenovic, J. Zhang. Addressing and Routing in HexagonalNetworks with Applications for Tracking Mobile Users and Connection Rerouting inCellular Networks[J]. IEEE Trans. Parallel and Distributed Systems,2002,13(9):963-971.
[75] B. Parhami, D.M. Kwai. Incomplete k-ary n-cube and Its Derivatives[J]. Parallel andDistributed Computing,2004,64(2):183-190.
[76] B. Stong. On Hamiltonian cycles in Cayley Graphs of Wreath Products[J]. DiscreteMathematics,1987,65:75-80.
[77] W.J. Xiao, W.D. Chen, M.X. He, W.H. Wei, B. Parhami. Biswapped Networksand Their Topological Properties[C].8th ACIS International Conference on SoftwareEngineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing(SNPD2007),2007:193-198.
[78] Chen, G. H., Duh, D. R.. Topological properties, communication and computation onWK-recursive networks[J]. Networks,1994,24(6):303-317.
[79] Su Ming-Ying, Chen Gen-Huey, Duh Dyi-Rong. Broadcasting on incompleteWK-recursive networks[J]. Journal of Parallel and Distributed Computing,1999,57:217-224.
[80] Fernandes,R.,Kanevsky,A.. Generalized ring interconnection networks[C]. TheProceedings of1994International Conference on Parallel Processing,IEEE,1994:30-34.
[81] Das, S.K., Ohring, S., Banerice, A. K.. Embedding into hyper Petersen network: yetanother Hypercube-like topology[J]. Journal of VLSI Design,1995,2(4):335-351.
[82] Yeh, Chi-Hsiang, Parhami Behrooz. Routing and embeddings in cyclic Petersennetwork: an efficient extension of the Petersen graph[C]. Proc of Int’l Conf on ParallelProcessing, IEEE, Japan,1999:258-265.
[83] Howard Jay Siegel. Interconnection Networks for Large Scale Parallel Processing[M].New York: McGraw-Hill Publishing Company,1990.
[84] Parhami Behrooz, Chi-Hsiang Yeh. Why network diameter is still important[C]. ProcInternational Conference on Communications, Las Vegas,USA,2000:26-29.
[85] Xiao W.J., Parhami B..Further Mathematical Properties of Cayley Digraphs Applied toHexagonal and Honeycomb Meshes [J]. Discrete Applied mathematics,2007,155(13):1752-1760.
[86]刘方爱,刘志勇,乔香珍.一种实用的互连网络拓扑结构RP(k)及路由算法.中国科学(E辑),2002,32(3):380-385.
[87] Liu Fang’ai,Liu Zhiyong, Qiao Xiangzhen. A practical interconnection network RP(k)and its routig algorithms[J]. Science in China (Series F),2001,44(6):461-473.
[88] J.A.Bondy and U.S.R.Murty. Group Theory with Applications[M]. New York: NorthHolland,1979.
[89]刘方爱,刘志勇,乔香珍.一类层次环网络的构造及路由算法[J].计算机学报,2002,25(12):1397-1404.
[90]刘方爱,刘志勇,张永胜.环、mesh嵌入RP(k)网络[J].中国科学（E辑,信息科学）2004,34(8):939-950.
[91]王雷,林亚平,陈治平等.二维环/双环连接Petersen图网络及其路由算法[J].计算机学报,2004,27(9):1290-1296.
[92]王雷,林亚平.基于超立方体环连接的Petersen图互连网络研究[J].计算机学报,2005,28(3):409-413.
[93]王雷,林亚平,夏巍.双环Petersen图互连网络及其路由算法[J].软件学报,2006,17(5):1115-1123.
[94] Behrooz Parhami. The Hamiltonicity of swapped (OTIS) networks built of Hamiltoniancomponent networks[J]. Information Processing Letters,2005,95:441-445.
[95] J.S.Fu, G.H.Chen, Hemiltonicity of the hierarchical cubic network[J], Theory Comput.Systems,2002,35:59-79.
[96] Yeh, Chi-Hsiang, Parhami Behrooz. Hierarchical swapped networks: Efficientlow-degree alternatives to Hypercube and generalized Hypercubes[C]. ProcInternational Symposium on Parallel Architectures, Algorithms, and Networks, Beijing,1996:90-96.
[97] Behrooz Parhami. The Hamiltonicity of swapped (OTIS) networks built of Hamiltoniancomponent networks[J]. Information Processing Letters,2005,95:441-445.
[98] K. Sripanidkulchai, B. Maggs, H. Zhang. Effcient content location using interest-basedlocality in peer-to-peer systems[C]. Proc. of IEEE Infocom2003: The conference oncomputer communications,2003(1-3):2166–2176.
[99] B. Mukherjee. Optical WDM Networks[M]. Springer,2006.
[100] Mohsenian-Rad, A. H. Joint logical topology design, interface assignment, channelallocation, and routing for multi-channel wireless mesh networks[J]. IEEE Trans.Wireless Communications,2007,6(12):4432-4440.
[101] Akyildiz I.F., Wang X., Wang W. Wireless mesh networks: a survey [J]. Computernetworks,2005,47(4):445-487.
[102]欧中洪,宋美娜,战晓苏等.移动对等网络关键技术[J].软件学报,2008,19(2):404-418.
[103] Jun Jangeun, Sichitiu M.L. The nominal capacity of wireless mesh networks [J].Wireless Communications,2003,10(5):8-14.
[104] Ashish R., Chiueh Tzi-cker. Architecture and algorithms for an IEEE802.11-basedmulti-channel wireless mesh network [A]. Proceedings IEEE24th Annual JointConference of the IEEE Computer and Communications Societies [C]. Washington:IEEE Computer Society,2005:2223-2234.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |