Wait-Free Deflection Routing of Long Messages

In order to obtain the lowest possible latency, routing algorithms should try to avoid message waiting for resources (network links) blocked by other messages or multiplexing of more messages over one physical channel. This requirement becomes especially important in the case of long messages. The only type of protocols able to guarantee waiting free routing under heavy load are algorithms based on deflection (also called nonminimal adaptive or hot potato) routing. The paper deals with problems connected with the use of deflection algorithms. In contrast to the case of nonadaptive or partially (e.g. minimal) adaptive routing, it is very infrequent that an unrestricted deflection routing becomes deadlocked and similarly livelock is not a serious problem. On the other hand, there is another phenomenon, called a deflection jam, that limits throughput of deflection algorithms used to route long messages. It has been observed for many deflection heuristics, interconnection network ..