资源描述:
《constructing node-disjoint routes in k-ary n-cubesnew》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、CONSTRUCTINGNODE-DISJOINTROUTESINK-ARYN-CUBESKhaledDay,andAbdelElahAl-AyyoubDepartmentofComputerScience,SultanQaboosUniversityPOBox36,Muscat123,SultanateofOmanABSTRACT:Inthispaper,amethodforconstructingnode-disjoint(parallel)pathsink-aryn-cubeinterconnectionnetworksisdescribed.Westartbyshowinginge
2、neralhowtoconstructparallelpathsinanyCartesianproductoftwographsbasedonknownpathsinthefactorgraphs.Thenweapplythegeneralresulttobuildacompletesetofparallelpaths(i.e.,asmanypathsasthedegreeofthenetwork)betweenanytwonodesofak-aryn-cubewhichcanbeviewedastheCartesianproductofcompletegraphs.Eachoftheco
3、nstructedpathsisoflengthatmost2plustheminimumdistancebetweenthetwonodes.Theseparallelpathsareusefulinspeeding-upthetransferoflargeamountsofdatabetweentwonodesandinofferingalternateroutesincasesoffaultynodes.IndexTerms-Cartesianproductofgraphs,fault-tolerance,interconnectionnetworks,k-aryn-cube,nod
4、e-disjointpaths,routing.INTRODUCTIONManygraphshavebeenstudiedasattractiveinterconnectiontopologiesforlargemultiprocessorsystemsincludingthebinary-hypercube(SaadandSchultz,1988),the2-dimensionaltorus(DallyandSeitz,1986,Gravanoetal,1994),andthek-aryn-cube(AgrawalandBhuyan,1984,LakshmivarahnandDhall,
5、1988,GrahamandSeidel,1993).Thereisaconfusionintheliteratureaboutwhichgraphiscalledthek-aryn-cube.Forexample,whatiscalledthetorusnetworkin(DallyandSeitz)and(Gravanoetal,1994)iscalledthek-aryn-cubein(LinderandHarden,1991)and(Boseetal,1995)whilein(GrahamandSeidel,1993)thek-aryn-cubereferstoadifferent
6、topology.Asdefinedlater,thek-aryn-cubeconsideredinthispaperisthesameasin(GrahamandSeidel,1993).GrahamandSeidel(1993)haveshownthatthek-aryn-cubeperformsbetterintermsofone-to-allbroadcastingandcompletebroadcastingthanthestargraphwithacomparablenumberofnodesforpracticalnetworksizes.Ingeneral,thecrite
7、riausedinevaluatinginterconnectionnetworksrelatetotheirtopologicalpropertiesofsymmetry,scalability,lowdegreeanddiameter,efficientdistributedroutingalgorithms,recursivestructure,faulttolerance,low-costembeddingofo