کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
430053 | 687788 | 2013 | 18 صفحه PDF | دانلود رایگان |
• We define multiswapped networks to extend the range of potential hybrid optoelectronic/electronic interconnection networks.
• We derive a structural properties of multiswapped networks in terms of these properties of its two constituent component graphs.
• We develop a deterministic multipath source routing algorithm for our multiswapped network.
We generalise the biswapped network Bsw(G)Bsw(G) to obtain a multiswapped network Msw(H;G)Msw(H;G), built around two graphs G and H . We show that the network Msw(H;G)Msw(H;G) lends itself to optoelectronic implementation and examine its topological and algorithmic. We derive the length of a shortest path joining any two vertices in Msw(H;G)Msw(H;G) and consequently a formula for the diameter. We show that if G has connectivity κ⩾1κ⩾1 and H has connectivity λ⩾1λ⩾1 where λ⩽κλ⩽κ then Msw(H;G)Msw(H;G) has connectivity at least κ+λκ+λ, and we derive upper bounds on the (κ+λ)(κ+λ)-diameter of Msw(H;G)Msw(H;G). Our analysis yields distributed routing algorithms for a distributed-memory multiprocessor whose underlying topology is Msw(H;G)Msw(H;G). We also prove that if G and H are Cayley graphs then Msw(H;G)Msw(H;G) need not be a Cayley graph, but when H is a bipartite Cayley graph then Msw(H;G)Msw(H;G) is necessarily a Cayley graph.
Journal: Journal of Computer and System Sciences - Volume 79, Issue 8, December 2013, Pages 1269–1286