US5402416A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and system for buffer occupancy reduction in packet switch network
Assignee: International Business Machines Corp
•
Filing: 1994-01-05
•
Granted: 1995-03-28
•
Expires: 2014-01-05
Abstract
Abstract A packet switch system having a buffer occupancy reduction mechanism for controlling data flow through switched nodes of the system to avoid congestion and reduce required buffer storage at the nodes. For an isochronous connection, buffers are initially allocated at each switching node connection to ensure listless transmission of packets. A buffer occupancy trace for the connection is recorded and the delay time of an isochronous packet at a particular switch port is returned to a preceding switch port. The preceding switch port employs the feedback message to delay subsequent packets through the connection to reduce the queuing time at the particular switch port. Once the isochronous connection has stabilized, buffer reallocation is performed wherein a scheduler at each switch node along the connection attempts to combine buffer allocations for different isochronous connections. This occurs provided the corresponding buffer occupancy traces of the isochronous connections do not overlap. Buffer occupancy reduction is therefore accomplished through the delaying of isochronous packets propagated through the connections of the packet switch system and the reallocating of buffers initially assigned to two or more isochronous connections.
Inventors
- 👤 Randall A. Cieslak
- 👤 Christos J. Georgiou
- 👤 Chung-Sheng Li
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-31 16:14
CPC Classifications
H; H04; H04L; H04L47/00; H04L47/10; H04L12/00; H04L12/64
Claims Analysis
Total Claims: 33
Claim 1
Independent Claim
220 words
A method for processing an isochronous connection established within a multinode packet switch network having at least two isochronous connections through a common switch port, each of said at least two isochronous connections having stream of packets propagating therethrough, said streams of packets each having a fixed packet phase and a same nearly constant packet rate, 1/T frame , into the common switch port, said at least two isochronous connections comprising a first isochronous connection and a second isochronous connection, said processing method comprising the steps of: (a) monitoring buffer occupancy time of a current packet in the stream of packets provided to the common switch port by the first isochronous connection; (b) returning a feedback message along the first isochronous connection to a previous switch node of the multinode packet switch network, said feedback message being representative of the buffer occupancy time monitored in said step (a); and (c) adjusting at the previous switch node the packet phase of subsequent packets relative to the nearly constant packet rate 1/T frame of the stream of packets propagating through the first isochronous connection to the common switch port such that once delivered to the common switch port, buffer occupancy time for the subsequent packets is reduced in comparison with buffer occupancy time of the current packet monitored in said step (a).
Claim 2
Independent Claim
220 words
A method for processing an isochronous connection established within a multinode packet switch network having at least two isochronous connections through a common switch port, each of said at least two isochronous connections having stream of packets propagating therethrough, said streams of packets each having a fixed packet phase and a same nearly constant packet rate, 1/T frame , into the common switch port, said at least two isochronous connections comprising a first isochronous connection and a second isochronous connection, said processing method comprising the steps of: (a) monitoring buffer occupancy time of a current packet in the stream of packets provided to the common switch port by the first isochronous connection; (b) returning a feedback message along the first isochronous connection to a previous switch node of the multinode packet switch network, said feedback message being representative of the buffer occupancy time monitored in said step (a); and (c) adjusting at the previous switch node the packet phase of subsequent packets relative to the nearly constant packet rate 1/T frame of the stream of packets propagating through the first isochronous connection to the common switch port such that once delivered to the common switch port, buffer occupancy time for the subsequent packets is reduced in comparison with buffer occupancy time of the current packet monitored in said step (a).
Claim 3
Dependent Claim
57 words
The processing method of claim 1, further comprising the step of initially allocating to each of said at least two isochronous connections at least one buffer at the common switch port, said at least one buffer allocation to each isochronous connection being sufficient to retain a packet of the stream packets provided through the corresponding isochronous connection.
Claim 4
Dependent Claim
36 words
The processing method of claim 2, further comprising the step of repeating steps (a)-(c) for a plurality of current packets of the stream of packets propagated to the common switch port through the first isochronous connection.
Claim 5
Dependent Claim
43 words
The processing method of claim 3, further comprising the step of discontinuing said repeating of said steps (a)-(c) once monitored buffer occupancy time for successive packets of the stream of packets provided to the common switch port through the first isochronous connection stabilizes.
Claim 6
Dependent Claim
97 words
The processing method of claim 4, further comprising the steps of: monitoring buffer occupancy time of a packet in the stream of packets delivered to the common switch port through the second isochronous connection; and combining buffer allocations for the first isochronous connection and the second isochronous connection such that the at least two isochronous connections share a buffer at the common switch port when there is no overlap in monitored buffer occupancy time for the phase adjusted subsequent packets of the first isochronous connection and the packet of the second isochronous connection undergoing buffer occupancy monitoring.
Claim 7
Dependent Claim
48 words
The processing method of claim 5, further comprising the step of deallocating at least one buffer initially allocated to the first isochronous connection and the second isochronous connection whenever the at least two isochronous connections are combined such that a buffer is shared at the common switch port.
Claim 8
Dependent Claim
54 words
The processing method of claim 4, wherein said discontinuing step comprises discontinuing said repeating of said steps (a)-(c) once monitored buffer occupancy time between packets of the stream of packets provided through the first isochronous connection to the common switch port stabilizes at a value less than or equal to a predefined value ε.
Claim 9
Dependent Claim
69 words
The processing method of claim 4, wherein said discontinuing step comprises discontinuing said repeating of said steps (a)-(c) after N packets of the stream of packets provided through the first isochronous connection to the common switch port have undergone said buffer occupancy time monitoring of step (a) with corresponding feedback messages having been sent to the previous switch node for each of the N packets (wherein N=an integer number).
Claim 10
Dependent Claim
37 words
The processing method of claim 1, further comprising the step of establishing a new isochronous connection within the multinode packet switch network, and wherein said processing method includes repeating said steps (a)-(c) for the new isochronous connection.
Claim 11
Dependent Claim
45 words
The processing method of claim 1, wherein said first isochronous connection is established through a plurality of switch ports and wherein said processing method includes performing steps (a)-(c) for at least some of said plurality switch ports through which the first isochronous connection is established.
Claim 12
Dependent Claim
75 words
The processing method of claim 1, wherein said adjusting step (c) includes adjusting at the previous switch node the packet phase of subsequent packets relative to the nearly constant packet rate 1/T frame of the stream of packets propagating through the first isochronous connection to the common switch port such that delivery of the subsequent packets is delayed by an amount less than or equal to the buffer occupancy time monitored in said step (a).
Claim 13
Dependent Claim
209 words
In a packet switch network having an isochronous connection established through a first node and a second node such that a stream of packets is delivered from the first node to the second node at a nearly constant packet rate, 1/T frame , and packet phase, a method for reducing buffer occupancy time of packets delivered to the second node without affecting the nearly constant packet rated 1/T frame , said method comprising the steps of: (a) monitoring buffer occupancy time at the second node of a current packet of the stream of packets delivered from the first node to the second node; (b) generating at the second node a feedback message representative of the buffer occupancy time monitored in said step (a); (c) sending the feedback message back along the isochronous connection from the second node to the first node; and (d) adjusting at the first node the packet phase of subsequent packets of the stream of packets relative to the nearly constant packet rate 1/T frame without effecting the nearly constant packet rate 1/T frame such that once delivered to the second node, buffer occupancy time for the subsequent packets is reduced in comparison with buffer occupancy time of the current packet monitored in said step (a).
Claim 14
Dependent Claim
209 words
In a packet switch network having an isochronous connection established through a first node and a second node such that a stream of packets is delivered from the first node to the second node at a nearly constant packet rate, 1/T frame , and packet phase, a method for reducing buffer occupancy time of packets delivered to the second node without affecting the nearly constant packet rated 1/T frame , said method comprising the steps of: (a) monitoring buffer occupancy time at the second node of a current packet of the stream of packets delivered from the first node to the second node; (b) generating at the second node a feedback message representative of the buffer occupancy time monitored in said step (a); (c) sending the feedback message back along the isochronous connection from the second node to the first node; and (d) adjusting at the first node the packet phase of subsequent packets of the stream of packets relative to the nearly constant packet rate 1/T frame without effecting the nearly constant packet rate 1/T frame such that once delivered to the second node, buffer occupancy time for the subsequent packets is reduced in comparison with buffer occupancy time of the current packet monitored in said step (a).
Claim 15
Dependent Claim
32 words
The method of claim 12, further comprising the step of repeating steps (a)-(d) for a plurality of packets of the stream of packets delivered from the first node to the second node.
Claim 16
Dependent Claim
39 words
The method of claim 13, further comprising the step of discontinuing said repeating of said steps (a)-(d) once monitored buffer occupancy time for at least some packets of the stream of packets has stabilized below a predefined value ε.
Claim 17
Dependent Claim
72 words
The method of claim 12, wherein said adjusting step (d) includes adjusting at the first node the packet phase of subsequent packets of the stream of packets relative to the nearly constant packet rate 1/T frame such that the subsequent packets are delayed in time by an amount equal to or less than the buffer occupancy time monitored in said step (a) without affecting the nearly constant packet rate 1/T frame .
Claim 18
Independent Claim
238 words
A method for processing at least two isochronous connections established within a multinode packet switch network, said at least two isochronous connections including a first isochronous connection and a second isochronous connection which share a common switch port at a switch node of the multinode packet switch network, said at least two isochronous connections each providing a stream of packets to the common switch port, said streams of packets having the same nearly constant packet rate, 1/T frame , and independent packet phases, each of the at least two isochronous connection having a unique buffer allocation at the common switch port, said processing method comprising the steps of: (a) evaluating buffer occupancy time relative to said packet rate 1/T frame of at least one packet in the stream of packets provided through the first isochronous connection to the common switch port, and evaluating buffer occupancy time relative to said packet rate 1/T frame of at least one packet in the stream of packets provided through the second isochronous connection to the common switch port; and (b) combining buffer allocations for the first isochronous connection and the second isochronous connection such that the at least two isochronous connections share a buffer at the common switch node provided that there is no overlap in evaluated buffer occupancy times for the at least one packet of the first isochronous connection and the at least one packet of the second isochronous connection.
Claim 19
Independent Claim
238 words
A method for processing at least two isochronous connections established within a multinode packet switch network, said at least two isochronous connections including a first isochronous connection and a second isochronous connection which share a common switch port at a switch node of the multinode packet switch network, said at least two isochronous connections each providing a stream of packets to the common switch port, said streams of packets having the same nearly constant packet rate, 1/T frame , and independent packet phases, each of the at least two isochronous connection having a unique buffer allocation at the common switch port, said processing method comprising the steps of: (a) evaluating buffer occupancy time relative to said packet rate 1/T frame of at least one packet in the stream of packets provided through the first isochronous connection to the common switch port, and evaluating buffer occupancy time relative to said packet rate 1/T frame of at least one packet in the stream of packets provided through the second isochronous connection to the common switch port; and (b) combining buffer allocations for the first isochronous connection and the second isochronous connection such that the at least two isochronous connections share a buffer at the common switch node provided that there is no overlap in evaluated buffer occupancy times for the at least one packet of the first isochronous connection and the at least one packet of the second isochronous connection.
Claim 20
Dependent Claim
55 words
The processing method of claim 16, further comprising the step of initially allocating to each of said at least two isochronous connections the unique buffer allocation at the common switch port, said unique buffer allocation to each isochronous connection being sufficient to retain a packet of the stream of packets propagated through the corresponding connection.
Claim 21
Dependent Claim
43 words
The processing method of claim 17, wherein said step (a) includes recording buffer occupancy time for the at least one packet of the first isochronous connection and the at least one packet of the second isochronous connection in a buffer occupancy trace table.
Claim 22
Dependent Claim
33 words
The processing method of claim 16, further comprising the step of deallocating the unique buffer allocation for one of said at least two isochronous connections after combining buffer allocations in said step (b).
Claim 23
Dependent Claim
228 words
A multinode packet switch network having an established isochronous connection wherein a stream of packets propagates through the network at a nearly constant packet rate, 1/T frame , and packet phase, said packet switch network comprising: a first switch node and a second switch node through which the isochronous connection is established and the stream of packets propagates, said first switch node delivering the stream of packets to the second switch node at said nearly constant packet rate, 1/T frame , said second switch node including a buffer for temporarily retaining a current packet of the stream of packets; means for monitoring buffer occupancy time at the second switch node of the current packet of the stream of packets delivered from the first switch node to the second switch node; means for generating at the second switch node a feedback message representative of the monitored buffer occupancy time; means for sending the feedback message from the second switch node to the first switch node; and means for adjusting at the first switch node the packet phase of subsequent packets of the stream of packets relative to the nearly constant packet rate 1/T frame without affecting the nearly constant packet rate 1/T frame such that once delivered to the second switch node, buffer occupancy time for the subsequent packets is reduced in comparison with the monitored buffer occupancy time.
Claim 24
Dependent Claim
228 words
A multinode packet switch network having an established isochronous connection wherein a stream of packets propagates through the network at a nearly constant packet rate, 1/T frame , and packet phase, said packet switch network comprising: a first switch node and a second switch node through which the isochronous connection is established and the stream of packets propagates, said first switch node delivering the stream of packets to the second switch node at said nearly constant packet rate, 1/T frame , said second switch node including a buffer for temporarily retaining a current packet of the stream of packets; means for monitoring buffer occupancy time at the second switch node of the current packet of the stream of packets delivered from the first switch node to the second switch node; means for generating at the second switch node a feedback message representative of the monitored buffer occupancy time; means for sending the feedback message from the second switch node to the first switch node; and means for adjusting at the first switch node the packet phase of subsequent packets of the stream of packets relative to the nearly constant packet rate 1/T frame without affecting the nearly constant packet rate 1/T frame such that once delivered to the second switch node, buffer occupancy time for the subsequent packets is reduced in comparison with the monitored buffer occupancy time.
Claim 25
Dependent Claim
71 words
The packet switch network of claim 20, wherein said means for adjusting includes means for adjusting at the first switch node the packet phase of subsequent packets of the stream of packets relative to the nearly constant packet rate 1/T frame without affecting the nearly constant packet rate 1/T frame and such that the subsequent packets are delayed by an amount less than or equal to the monitored buffer occupancy time.
Claim 26
Dependent Claim
212 words
A multinode packet switch network having at least two isochronous connections established through a common switch port, each of said at least two isochronous connections having a stream of packets propagating therethrough, said streams of packets each having a fixed packet phase and a same nearly constant packet rate, 1/T frame into the common switch port, said at least two isochronous connections comprising a first isochronous connection and a second isochronous connection, said multinode packet switch network comprising: means for monitoring buffer occupancy time of a current packet in the stream of packets provided to the common switch port by the first isochronous connection; means for returning a feedback message along the first isochronous connection to a previous switch node of the multinode packet switch network, said feedback message being representative of the monitored buffer occupancy time; and means for adjusting at the previous switch node the packet phase of subsequent packets relative to the nearly constant packet rate 1/T frame of the stream of packets propagating through the first isochronous connection without affecting the nearly constant packet rate 1/T frame and such that once delivered to the common switch port buffer occupancy time for the subsequent packets is reduced in comparison with the monitored buffer occupancy time of the current packet.
Claim 27
Dependent Claim
212 words
A multinode packet switch network having at least two isochronous connections established through a common switch port, each of said at least two isochronous connections having a stream of packets propagating therethrough, said streams of packets each having a fixed packet phase and a same nearly constant packet rate, 1/T frame into the common switch port, said at least two isochronous connections comprising a first isochronous connection and a second isochronous connection, said multinode packet switch network comprising: means for monitoring buffer occupancy time of a current packet in the stream of packets provided to the common switch port by the first isochronous connection; means for returning a feedback message along the first isochronous connection to a previous switch node of the multinode packet switch network, said feedback message being representative of the monitored buffer occupancy time; and means for adjusting at the previous switch node the packet phase of subsequent packets relative to the nearly constant packet rate 1/T frame of the stream of packets propagating through the first isochronous connection without affecting the nearly constant packet rate 1/T frame and such that once delivered to the common switch port buffer occupancy time for the subsequent packets is reduced in comparison with the monitored buffer occupancy time of the current packet.
Claim 28
Dependent Claim
100 words
The multinode packet switch network of claim 22, further comprising: means for monitoring buffer occupancy time of a packet in the stream of packets delivered to the common switch port through the second isochronous connection; and means for combining buffer allocations of the first isochronous connection and the second isochronous connection such that the at least two isochronous connections share a buffer at the common switch node when there is no overlap in monitored buffer occupancy time for the phase adjusted subsequent packets of the first isochronous connection and the packet of the second isochronous connection undergoing buffer occupancy monitoring.
Claim 29
Dependent Claim
87 words
The multinode packet switch network of claim 22, wherein said means for adjusting the packet phase at the previous switch node includes means for adjusting the packet phase of subsequent packets relative to the nearly constant packet rate 1/T frame of the stream of packets propagating through the first isochronous connection without affecting the nearly constant packet rate 1/T frame and such that the subsequent packets are delayed in time by an amount less than or equal to the monitored buffer occupancy time for the current packet.
Claim 30
Dependent Claim
235 words
A multinode packet switch network having at least two isochronous connections which share a common switch port at a switch node of the multinode packet switch network, said at least two isochronous connections each providing a stream of packets to the common switch port, said streams of packets having the same nearly constant packet rate, 1/T frame , and independent packet phases, each of the at least two isochronous connections having a unique buffer allocation at the common switch port, said at least two isochronous connections including a first isochronous connection and a second isochronous connection, said multinode packet switch network comprising: means for evaluating buffer occupancy time relative to the packet rate 1/T frame of at least one packet in the stream of packets provided through the first isochronous connection to the common switch port; means for evaluating buffer occupancy time relative to the packet rate 1/T frame of at least one packet in the stream of packets provided through the second isochronous connection to the common switch port; and means for combining buffer allocations for the first isochronous connection and the second isochronous connection such that the at least two isochronous connections share a buffer at the common switch port provided that there is no overlapping in evaluated buffer occupancy times for the at least one packet of the first isochronous connection and the at least one packet of the second isochronous connection.
Claim 31
Dependent Claim
235 words
A multinode packet switch network having at least two isochronous connections which share a common switch port at a switch node of the multinode packet switch network, said at least two isochronous connections each providing a stream of packets to the common switch port, said streams of packets having the same nearly constant packet rate, 1/T frame , and independent packet phases, each of the at least two isochronous connections having a unique buffer allocation at the common switch port, said at least two isochronous connections including a first isochronous connection and a second isochronous connection, said multinode packet switch network comprising: means for evaluating buffer occupancy time relative to the packet rate 1/T frame of at least one packet in the stream of packets provided through the first isochronous connection to the common switch port; means for evaluating buffer occupancy time relative to the packet rate 1/T frame of at least one packet in the stream of packets provided through the second isochronous connection to the common switch port; and means for combining buffer allocations for the first isochronous connection and the second isochronous connection such that the at least two isochronous connections share a buffer at the common switch port provided that there is no overlapping in evaluated buffer occupancy times for the at least one packet of the first isochronous connection and the at least one packet of the second isochronous connection.
Claim 32
Dependent Claim
57 words
The multinode packet switch network of claim 25, further comprising means for recording buffer occupancy time for the at least one packet of the first isochronous connection and the at least packet of the second isochronous connection, said means for recording buffer occupancy time including means for storing buffer occupancy times in a buffer occupancy trace table.
Claim 33
Dependent Claim
36 words
The multinode packet switch network of claim 25, wherein said means for combining buffer allocations includes means for deallocating the unique buffer allocation for one of the at least two isochronous connections after combining buffer allocations.
References Cited (Backward Citations)
US4616359A
Cited
US4899333A
Cited
US5199028A
Cited
US4969149A
Cited
US5050162A
Cited
US5218680A
Cited
US5063562A
Cited
US5276677A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-03-27 | 1998-09-26 | 1999-03-28 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-03-27 | 2002-09-26 | 2003-03-28 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-03-27 | 2006-09-26 | 2007-03-28 | $7700.00 | Window Closed / Lapsed |