PREVENTION OF DEADLOCKS AND LIVELOCKS IN LOSSLESS, BACKPRESSURED PACKET NETWORKS

摘要

A packet communication network is arranged so that a backpressure or feedback signal is sent from a receiving node to a node having packets to se nd to the receiving node, selectively allowing only certain packets to be considered eligible for transmission. The backpressure is arranged to be lossless, and to avoid network deadlocks and livelocks. The transmission of a packet p from a sending node X~ to a receiving node R~, via a link ~, is controlled by (a) sending from the receiving node R~ to the upstream node X~ a feedback value f~ that assures that there will be room in the buffer in the receiving node R~ to store packets subsequently received from the upstream node X~; (b) assigning a priority level .lambda.p to packe ts stored in the buffer of the receiving node R~; and (c) transmitting from the sending node X~ to the receiving node R~, only those stored packets at X~ whose priority level .lambda.p exceeds the feedback value f~ received from the receiving node R~. The assigning step can be accomplished by assigning a level that is less than or equal to D (the maximum number of hops that a packet must traverse through said network from node X~ to node R~) minus the number of hops remaining between the receiving node R~ and the destination, and is further arranged such that the priorityl evel .lambda.p assigned to packets stored in the buffer at R~ is based upon the destination to which the packets are to be transmitted, and is the same (referred to as .lambda.d ) for all packets intended for the same destination. The feedback value f~ sent from a receivi ng node R~ to a sending node X~, which represents the lowest priority level of packe ts that the receiving node R~ could accept without violating any of the B i buffer threshold constraints, is determined by first setting in the buffer at the receiving node R~ thresholds B i that limit the maximum amount of space for packets with priority levels .lambda.d less than or equal to i. At all times, all B i buffer threshold constraints must be satisfied. The receiving node R~ thereafter monitors the priority levels ~d of arriving and departing packets, and the increasing of priority levels .lambda.p of previously-stored packets (so that all packets destined for a given destination d have the sam e priority level .lambda.d), and thus keeps track of the total space in the buffer at R ~ occupied by packets of various priority levels .lambda.d.