One of the most common approaches to deadlock prevention is a mechanism known as buffer preallocation. The key concept is that buffers are allocated, most usually for a virtual circuit or class of virtual circuits, before any data is transmitted, and this allocation is done in such a way that no deadlocks are possible. This preallocation typically occurs through the transmission of reservation control messages prior to the transmission of normal data traffic. Control traffic deadlock prevention has yet to be studied. It is shown that deadlocks may occur in connection with this initializing control traffic, and that the resolution of such deadlocks must be handled with some care. If such resolution is not handled with sufficient care, a condition termed standoff may result, whereby contention for the allocation of one or more critical buffers results in resource being allocated to none of the contending parties. Protocols that prevent the phenomenon of standoff, thereby ensuring true deadlock-free operation are described.>

The authors consider a special case of multilink protocol, namely, a system consisting of two half-duplex parallel links that carry data in opposite directions between two nodes. They construct a protocol that simulates a full-duplex reliable link between the two nodes. Synchronization is achieved without resorting to the use of serial numbers. A validation proof of the protocol is provided. The design of the protocol exhibits an instance of the value of correctness proofs in the design process, as several successive protocols, discussed in the paper, were only found to be incorrect through the effort to prove them otherwise.>

The problem of obtaining a minimum cost topology for a mesh network given matrices specifying the cost of links between all pairs of nodes and the internode requirements is considered. A heuristic algorithm which works in terms of general network design principles and uses utilization as a figure of merit is presented. The procedure is applicable to a wide variety of networks, especially to the problem of obtaining starting topologies for other network design procedures. The algorithm's computational complexity is shown to be of order N/sup 2/, a significant improvement over currently used algorithms and fast enough to be embedded in the inner loop of other more general design procedures, e.g., node selection procedures. Computational experience is presented which shows that the procedure is fast and simple and yields solutions of a quality competitive with other much slower procedures.>

The authors model the internal structure of a packet-switching node in a real-time system and characterize the tradeoff between throughput, delay, and packet loss as a function of the buffer size, switching speed, etc. They assume a simple shared-single-path switch fabric, though the analysis can be generalized to a wider class of switch fabrics. They show that with a small number of buffers the node will provide a guaranteed delay bound for high-priority traffic, a low average delay for low-priority traffic, no loss of packets at the input and low probability of packet loss at output.>