Optimization aspects of deadlock prevention in packet-switching networks

Packet-switching networks empoly store-and-forward mechanism for transmission of equal-size packets through the network. This mechanism potentially offers dynamic resource sharing, high reliability, flexibility in setting up user connections, etc. It involves, however, a danger of stored-and-forward deadlock occurring when a circular chain of packets exists in which each packet occupies a buffer that is requested by the next packet in the chain. Therefore solution of this problem is necessary to achieve potential profits of packet switching. This paper is concerned with distributed strategies for store-and-forward deadlock prevention in packet-switching networks of arbitrary topology. These strategies prevent deadlocks at some cost involved in buffer utilization, flexibility and efficiency of packet routing, independence of network topology and its reconfigurations. In this context many particular optimization problems can be formulated. This paper deals with some of them, including such aspects as: optimization of buffer pool partitioning and buffer allocation for hop-so-far strategies, minimization of routing constraints imposed by strategies based on the barrier graph concept, and maximization of liberty of buffer allocation for networks with flxed as well as adaptive routing.