DEAD RECKONING - A PRIMITIVE AND EFFICIENT SELF-ROUTING PROTOCOL FOR ULTRAFAST MESH NETWORKS

The authors describe a new approach to the problem of self-routing in ultra-high-speed multi-computer interconnection networks. The method i s based on the concept of 'dead reckoning' (self-navigation without th e use of landmarks), and is applicable to networks with a mainly regul ar mesh topology. The packet header contains, in addition to the usual destination address, a tiny amount of directional information (as lit tle as 2 bits in the case of the Manhattan street network). With this additional data, the algorithm for path selection at the network nodes becomes extraordinarily simple, allowing very fast processing with go od routing efficiency and high throughput. Most significantly, with th is method it is not necessary to read each binary digit of the destina tion address of every packet arriving at every intermediate routing no de; it is sufficient only to perform a single-stage pattern match betw een the packet address and the address of the routing node. This featu re, and the low latency of this self-routing technique, make it partic ularly well suited to ultrafast photonic networks.