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

摘要

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.