constructing node-disjoint routes in k-ary n-cubesnew

《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