Principles for High Speed Network Control: Lossless-ness and Deadlock-Freeness, Self-Routing and a Single Buffer Per Link

        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 congestions and failures. All these properties are implemented in a distributed manner.

By: Yoram Ofek and Moti Yung

Published in: ACM Symposium on Principles of Distributed Computing (9th), Proceedings. , New York, ACM, p.161-75 in 1990

Please obtain a copy of this paper from your local library. IBM cannot distribute this paper externally.

Questions about this service can be mailed to .