A Deadlock-Free Non-minimal Fully Adaptive Routing Using Virtual Cut-Through Switching

System area networks (SANs), which usually employ virtual cut-through switching, have been used to connect hosts in modern PC clusters and massively parallel computers. In this paper, we propose a non-minimal fully adaptive deadlock-free routing mechanism for virtual-cut-through networks called “Semi-deflection”. Semi-deflection routing guarantees deadlock-free packet transfer without use of virtual channels by allowing non-blocking transfer between specific pairs of routers. As the result of throughput evaluation, Semi-deflection routing improved throughput by up to 26 percent compared with that of north-last turn model, which is a typical adaptive routing, and also reduced latency.