Accessibility navigation

An oblivious shortest-path routing algorithm for fully connected cubic networks

Yang, X.F., Megson, G.M. and Evans, D.J. (2006) An oblivious shortest-path routing algorithm for fully connected cubic networks. Journal of Parallel and Distributed Computing, 66 (10). pp. 1294-1303. ISSN 0743-7315

Full text not archived in this repository.

It is advisable to refer to the publisher's version if you intend to cite from this work. See Guidance on citing.

To link to this item DOI: 10.1016/j.jpdc.2006.03.008


Fully connected cubic networks (FCCNs) are a class of newly proposed hierarchical interconnection networks for multicomputer systems, which enjoy the strengths of constant node degree and good expandability. The shortest path routing in FCCNs is an open problem. In this paper, we present an oblivious routing algorithm for n-level FCCN with N = 8(n) nodes, and prove that this algorithm creates a shortest path from the source to the destination. At the costs of both an O(N)-parallel-step off-line preprocessing phase and a list of size N stored at each node, the proposed algorithm is carried out at each related node in O(n) time. In some cases the proposed algorithm is superior to the one proposed by Chang and Wang in terms of the length of the routing path. This justifies the utility of our routing strategy. (C) 2006 Elsevier Inc. All rights reserved.

Item Type:Article
ID Code:15481
Uncontrolled Keywords:interconnection network, hierarchical interconnection network, fully, connected cubic network, routing algorithm, shortest path, MESH OPTOELECTRONIC COMPUTER, 2-LEVEL HYPERNET NETWORKS, INTERCONNECTION NETWORKS, HIERARCHICAL HYPERCUBE, TOPOLOGICAL, PROPERTIES, OTIS-NETWORKS, SYSTEMS

University Staff: Request a correction | Centaur Editors: Update this record

Page navigation