Treffer: Efficient Routing using Class Climbing

This paper concentrates on a routing algorithm that is adaptive and avoids deadlocks and starvation. It is a general store-and-forward packet router that has been developed to be used as part of a distributed runtime system for Concurrent Clean, an experimental, lazy, higher-order parallel functional programming language based on term graph rewriting. The routing algorithm is based on the one used by the communication processor of the Decentralised Object Oriented Machine (DOOM) architecture, which uses a class climbing algorithm to avoid deadlocks. It has been altered in such a way that it can be used for the Inmos T800 transputer. Efficiency issues will be focused on. Performance figures clearly indicate that algorithm is significantly faster - and more reliable - than the communication primitives of the Helios operating system. 1. Introduction The T800 transputer hardware allows each transputer to be connected to no more than four others, which means that networks of more than fi.