Principles for high speed network control. Loss-less and deadlock-freeness, self-routing and a single buffer per link

Abstract

A high-speed network is a new environment motivated by recent advances in transmission technology. The high-speed environment requires that the network node operate (fast) based solely on local information (at least most of the time). This fact implies properties that are much different than those existing in current architectures and algorithms for traditional large-area networks. The new environment poses new challenges for the network architect and the algorithm designer. In this paper we present principles of operation for the basic control functions of a high-speed network with an arbitrary topology, we then suggest a design of such a network. In the architecture we design, on one hand a node can try to transmit asynchronously, without reservation, as much as it can, and on the other hand the network access and flow control will ensure no loss, fair access to the network, no deadlocks and self-routing. The switching over this network requires only a single buffer on each side of the full-duplex links. The transmission via the receiving buffer can be 'cut through', i.e., the incoming packet can be sent to the next link before the entire packet has arrived (unlike 'store-and-forward'). A dynamic self-routing technique is implemented, in which the packet header contains only the destination identification when it leaves the source. This information is sufficient for reaching the destination, not necessarily on the same route each time, and to overcome congrestion and failures. All these properties are implemented in a distributed manner. The system is asynchronous and designed for transmission of variable size packets.