Path selection algorithm: The strategy for designing deterministic routing from alternative paths

Michihiro Koibuchi, Akiya Jouraku, Hideharu Amano

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)


System Area Networks (SANs), which usually accept irregular topologies, have been used to connect nodes in PC/WS clusters or high-performance storage systems. Although routing algorithms for SANs usually find out alternative paths, SANs usually accept only deterministic routings. Thus, path selection algorithm, which chooses a single path from alternative paths, becomes essential for advanced routings in SANs. However, a few studies of it have been done only for SANs without virtual channels, and its impact is not well analyzed. In this paper, (1) we propose four path selection algorithms which have different concepts to distribute paths in SANs with virtual channels, and (2) we investigate the performance influences of various path selection algorithms through a flit-level simulation. Simulation results show that one of the four algorithms improves up to 92% of throughput against simple path selection algorithms, and policies to remove paths crossing the bottleneck channels are more efficient than ones to keep paths crossing channels that are not crowded.

Original languageEnglish
Pages (from-to)117-130
Number of pages14
JournalParallel Computing
Issue number1
Publication statusPublished - 2005 Jan


  • Deterministic routing
  • Interconnection networks
  • Path selection algorithm
  • System Area Networks
  • Virtual channels

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Computer Graphics and Computer-Aided Design
  • Artificial Intelligence


Dive into the research topics of 'Path selection algorithm: The strategy for designing deterministic routing from alternative paths'. Together they form a unique fingerprint.

Cite this