Prevention of deadlocks and livelocks in lossless, backpressured packet networks
First Claim
Patent Images
1. 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 upsteam, 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.
3 Assignments
0 Petitions
Accused Products
Abstract
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 send 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 Xl to a receiving node Rl, via a link l, is controlled by (a) sending from the receiving node Rl to the upstream node Xl a feedback value fl that assures that there will be room in the buffer in the receiving node Rl to store packets subsequently received from the upstream node Xl; (b) assigning a priority level λp to packets stored in the buffer of the receiving node Rl; and (c) transmitting from the sending node Xl to the receiving node Rl, only those stored packets at Xl whose priority level λp exceeds the feedback value fl received from the receiving node Rl.
225 Citations
13 Claims
-
1. 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 upsteam, 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. - View Dependent Claims (4, 5, 6, 7)
-
-
2. 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.
-
-
3. 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.
-
-
8. 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, andtransmitting 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 ofthe prior value of λ
d at Rl, or1+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.
-
-
9. 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. - View Dependent Claims (13)
-
-
10. 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.
-
-
11. 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, andpermitting sending node Xl to end a packet to receiving node Rl only if 80 d≧
fl.
-
d less than or equal to i,
-
12. 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.
-
Specification
-
- Resources
Litigation Campaign Assessment
Thank you for your request. You will receive a custom alert email when the Litigation Campaign Assessment is available.
×
-
Current AssigneeLucent Technologies, Inc. (Nokia Corporation)
-
Original AssigneeLucent Technologies, Inc. (Nokia Corporation)
-
InventorsGolestani, S. Jamaloddin, Lee, David, Karol, Mark John
-
Primary Examiner(s)Nguyen, Brian
-
Assistant Examiner(s)Moore, Ian N.
-
Application NumberUS09/624,085Time in Patent Office1,674 DaysField of Search370412-418, 370/429, 370/440, 370/231, 370/235, 370/230, 370/232US Class Current370/231CPC Class CodesH04L 47/10 Flow control; Congestion co...H04L 47/13 in a LAN segment, e.g. ring...H04L 47/2433 Allocation of priorities to...H04L 47/2458 Modification of priorities ...H04L 47/26 using explicit feedback to ...H04L 47/267 sent by the destination end...H04L 47/30 in combination with informa...H04L 47/43 Assembling or disassembling...
