An Effective Analytical Model for Deflection Routing in Hierarchical Ring Interconnection Networks

摘要

Deflection routing as a method for resolving output path selection conflicts in the crossover switches between levels in hierarchical ring networks is studied. These networks can be used to transfer cache line packets in a shared-memory multiprocessor. An approximate analytical model for 2- and 3-level hierarchies is developed for the determination of packet delay as a function of network configuration and offered traffic load. The model is shown to be very accurate for low to medium loads, with discrepancies from simulation results rising to about 14% for the S-level hierarchy and to about 26% for the 3-level hierarchy, at high load when significant deflection traffic occurs.