A Novel Globally Adaptive Load-Balanced Routing Algorithm for Torus Interconnection Networks

A globally adaptive load-balanced routing algorithm for torus interconnection networks is proposed. Unlike previously published algorithms, this algorithm employs a new scheme based on collision detection to handle deadlock, and has higher routing adaptability than previous algorithms. Simulation results show that the authors' algorithm outperforms previous algorithms by 16% on benign traffic patterns, and by 10% to 21% on adversarial traffic patterns. Torus interconnection networks are widely used as processor/memory interconnects in parallel computing systems or Packet Switching Fabrics (PSF) in Internet routers/switches.