Prevention of deadlocks and livelocks in lossless, backpressured packet networks

In a network of nodes connected to each other via bidirectional links, each of said nodes having a buffer for storing packets prior to transmission toward an ultimate destination, a method to control congestion on each of said links, said method comprising the steps of:

• assigning a priority level λp from amongst at least two possible priority levels, to packet stored in a sending node Xl buffer for transmission downstream via a link l to a receiving node Rl, said link l being a portion of the path from said sending node Xl to said ultimate destination, wherein said priority level λp is periodically changed when a packet is received in said receiving node Rl, such that when a packet p with ultimate destination d arrives at Rl from another network node (Xl) over some link l, the priority level λd of all packets at Rl destined for node d, is updated as the maximum of
• (a) the prior value of λd at Rl, or
• (b) 1+fl;
• transmitting upstream, via said link l, a feedback value fl from said receiving node Rl to said sending node Xl, said feedback value fl being indicative of the ability of said receiving node Rl to store said packet in said receiving node Rl buffer, and
• transmitting downstream from said sending node Xl to said receiving node Rl, via said link l, only those packets stored in said sending node Xl buffer whose priority level λp equals or exceeds the feedback value fl.

In a network of nodes connected to each other via bidirectional links, each of said nodes having a buffer for storing packets prior to transmission toward an ultimate destination, a method to control congestion on each of said links, said method comprising the steps of:

• assigning a priority level λn from amongst at least two possible priority levels to packets stored in a sending node Xl buffer for transmission downstream via a link l to a receiving node Rl, said link l being a portion of the path from said sending node Xl t to said ultimate destination, wherein the maximum value of said priority level λp is equal to the difference between (a) the maximum number D of nodes that a packet may traverse through said network from any originating node to any ultimate destination, and (b) the number of nodes between said sending node Xl and said ultimate destination node;
• transmitting upstream, via said link l, a feedback value fl from said receiving node Rl to said sending node Xl, said feedback value fl being indicative of the ability of said receiving node Rl to store said packet in said receiving node Rl buffer;
• and
• transmitting downstream from said sending node Xl to said receiving node Rl, via said link l, only those packets stored in said sending node Xl buffer whose priority level λp equals or exceeds the feedback value fl.

In a network of nodes connected to each other via bidirectional links, each of said nodes having a buffer for storing packets prior to transmission toward an ultimate destination, a method to control congestion on each of said links, said method comprising the steps of:

• assigning a priority level λp from amongst at least two possible priority levels, to packets stored in a sending node Xl buffer for transmission downstream via a link l to a receiving node Rl, said link l being a portion of the path from said sending node Xl to said ultimate destination;
• transmitting upstream, via said link l, a feedback value fl from said receiving node Rl to said sending node Xl, said feedback fl being indicative of the ability of to said receiving node Rl to store said packet in said receiving node Rl buffer wherein said feedback value fl is determined by
• setting in the buffer at the receiving node Rl thresholds Bi that limit the maximum amount of space for packets with priority levels λd less than or equal to i,
• monitoring the priority levels λd of arriving and departing packets and the total space in the buffer at Rl occupied by packets of various priority levels λd,
• increasing priority levels λp of previously-stored packets, and
• transmitting from the receiving node Rl to the sending node Xl a feedback value fl that represents the lowest priority level of packets that the receiving node Rl could accept without violating any of the Bi buffer threshold constraints,
• wherein said increasing step includes periodically changing said priority level λp when a packet is received in said receiving node Rl, such that when a packet p with ultimate destination d arrives at Rl from another network node (Xl) over some link l, the priority level λd at Rl associated with d is updated as the maximum of
• the prior value of λd at Rl, or
• 1+fl;
• and
• transmitting downstream from said sending node Xl to said receiving node Rl, via said link l, only those packets stored in said sending node Xl buffer whose priority level λp equals or exceeds the feedback value fl.

In a packet communication network comprised of interconnected nodes arranged to transmit variable length packets to adjacent nodes, wherein each node includes a buffer for storing packets enroute from a source node to a destination node, a method of controlling the transmission of a packet p from a sending node Xl to a receiving node Rl, via a link l, said method comprising the steps of

• sending from the receiving node Rl to the sending node Xl a feedback level fl such that there will be room in the buffer in the receiving node Rl to store packets subsequently received from the upstream node Xl;
• assigning a priority level λp to packets stored in the buffer of the receiving node Rl such that all packets destined for the same destination have the same priority level;
• and
• transmitting from the sending node Xl to the receiving node Rl, only those stored packets whose priority level λp is at least equal to the feedback level received from the receiving node Rl.

In a packet communication network comprised of interconnected nodes arranged to transmit variable length packets to adjacent nodes, wherein each node includes a buffer for storing packets enroute from a source node to a destination node, a method of controlling the transmission of a packet p from a sending node Xl to a receiving node Rl, via a link l, said method comprising the steps of

• sending from the receiving node Rl to the sending node Xl a feedback level fl such that there will be room in the buffer in the receiving node Rl to store packets subsequently received from the upstream node Xl;
• assigning a priority level λp to packets stored in the buffer of the receiving node Rl such that all packets destined for the same destination have the same priority level, wherein D is the maximum number of hops that a packet must traverse through said network from a source one of said nodes to a destination one of said nodes, and wherein said assigning step includes assigning a level that is less than or equal a to D minus the number of hops remaining between said receiving node Rl and said destination;
• and
• transmitting from the sending node Xl to the receiving node Rl, only those stored packets whose priority level λp is at least equal to the feedback level received from the receiving node Rl.

In a packet communication network comprised of interconnected nodes arranged to transmit variable length packets to adjacent nodes, wherein each node includes a buffer for storing packets enroute from a source node to a destination node, a method of controlling the transmission of a packet p from a sending node Xl to a receiving node Rl, via a link l, such that (a) feedback is provided from each receiving node to each sending node regarding the fullness of the buffer at said receiving node, and (b) the occurrence of deadlocks and livelocks in said receiving node is avoided and no packets sent from said sending node Xl to said receiving node Rl are lost, said method comprising the steps of

• transmitting from said receiving node Rl to said sending node Xl, a periodically updated transmit feedback parameter fl, said feedback value fl being determined by
• (i) setting in the buffer at the receiving node Rl thresholds Bi that limit the maximum amount of space for packets with priority levels λd less than or equal to i,
• (ii) monitoring at the receiving node Rl the priority levels λd of arriving and departing packets and the total space in the buffer at Rl occupied by packets of various priority levels λd,
• (iii) increasing priority levels λp of previously-stored packets, and
• (iv) adjusting the feedback fl sent from the receiving node Rl to the sending node Xl to represent the lowest priority level of packets that the receiving node Rl could accept without violating any of the Bi buffer threshold constraints,
• assigning in said sending node Xl, a level table associating, for each destination d to which said sending node may transmit a packet a level λd, such that (a) λd is initially zero, (b) any packet in said node intended for destination d has the same level, and (c) when a packet arrives at sending node Xl intended for destination d, λd is updated as the maximum of the previous value of λd or (1+fl), whichever is greater, and
• permitting sending node Xl to end a packet to receiving node Rl only if 80 d≧fl.

In a network of nodes connected to each other via bidirectional links, each of said nodes having a buffer for storing packets prior to transmission toward an ultimate destination, a method to provide feedback from receiving nodes to sending nodes to control packet transmission such that packets are not lost, and transmission of packets can occur without creating overflow in said buffers and without creating deadlocks or livelocks, said method comprising the steps of:

• assigning a priority level λp from amongst at least two possible priority levels, to packets stored in a sending node Xl buffer for transmission downstream via a link l to a receiving node Rl, said link l being a portion of the path from said sending node Xl to said ultimate destination;
• transmitting upstream, via said link l, a feedback value fl from said receiving node Rl to said sending node Xl, said feedback value fl being indicative of the ability of said receiving node Rl to store said packet in said receiving node Rl buffer;
• transmitting downstream from said sending node Xl to said receiving node Rl, via said link l, only those packets stored in said sending node Xl buffer whose priority level λp is at least equal to the feedback value fl;
• and
• periodically adjusting said feedback value fl and said priority level λp.