Routing Properties of a Recursive Interconnection Network

Kow Chuen Chang, Hong Y. Wang

Research output: Journal article publicationJournal articleAcademic researchpeer-review

4 Citations (Scopus)

Abstract

In this paper, we consider a highly recursive interconnection network known as the fully connected cubic network (FCCN). By exploiting its recursive properties, we thoroughly analyze the performance of a simple routing algorithm for the FCCN. We show that at least 80% of the routes obtained from this simple algorithm are shortest paths, and this percentage increases further with the network size. Subsequently, we obtain the network diameter and average internodal distance, taking into account the communication locality that is exhibited in many parallel computations. The presence of the communication locality significantly reduces the average internodal distance.
Original languageEnglish
Pages (from-to)838-849
Number of pages12
JournalJournal of Parallel and Distributed Computing
Volume61
Issue number6
DOIs
Publication statusPublished - 1 Jun 2001

Keywords

  • Communication locality
  • Cubic networks
  • Interconnection networks
  • Recursive topologies
  • Shortest-path routing algorithms

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Software
  • Hardware and Architecture
  • Computer Networks and Communications
  • Artificial Intelligence

Cite this