US5629936A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Control of consecutive packet loss in a packet buffer
Assignee: University of Iowa Research Foundation
•
Filing: 1994-08-01
•
Granted: 1997-05-13
•
Expires: 2014-08-01
Abstract
Abstract A circuit and method provides for optimal packet dropping to directly control consecutive packet loss (also called "average packet gap") in a packet buffer. The circuit and method can be used in a packet switched system having either a single packet class or multiple packet classes. The invention can be used at any point of the packet switched system, e.g., source buffers, switching node buffers, and destination buffers. A detailed proof shows that depending on configuration, the packet dropping policy is optimal for either minimizing or maximizing the average packet gap. More generally, the circuit and method can be used for controlling the source gaps created in any service system with a finite buffer. When a subset of customers from an ordered sequence of customers must be denied service due to to system overflow.
Inventors
- 👤 Chaewoo W. Lee
- 👤 Mark S. Andersland
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 21:33
CPC Classifications
H; H04; H04L; H04L12/00; H04L12/54; H04L12/56; H04L12/5601; H04L12/5602; H04L47/00; H04L47/10; H04L47/16; H04L47/26; H04L47/263; H04Q; H04Q11/00; H04Q11/04; H04Q11/0428; H04Q11/0478; H04L12/64; H04L2012/5638; H04L2012/5646; H04L2012/5647; H04L2012/5651; H04L2012/5678; H04L2012/5681
Claims Analysis
Total Claims: 26
Claim 1
Independent Claim
70 words
A method for producing a desired average packet gap size in a packet buffer, comprising the steps of: receiving incoming packets at said packet buffer; transmitting outgoing packets from said packet buffer; selecting a state transition rule based on the desired average packet gap size; and dropping packets from said packet buffer according to said state transition rule, when said buffer reaches overflow, to produce said average packet gap size.
Claim 2
Independent Claim
70 words
A method for producing a desired average packet gap size in a packet buffer, comprising the steps of: receiving incoming packets at said packet buffer; transmitting outgoing packets from said packet buffer; selecting a state transition rule based on the desired average packet gap size; and dropping packets from said packet buffer according to said state transition rule, when said buffer reaches overflow, to produce said average packet gap size.
Claim 3
Dependent Claim
25 words
The method as claimed in claim 1, wherein said selecting step comprises selecting the state transition rule so as to minimize average packet gap size.
Claim 4
Dependent Claim
26 words
The method as claimed in claim 1, wherein said selecting step comprises selecting the state transition rule so as to minimize said average packet gap size.
Claim 5
Dependent Claim
16 words
The method as claimed in claim 1, wherein said packets are at least of one class.
Claim 6
Dependent Claim
31 words
The method as claimed in claim 4, wherein the next packet of each of said at least one class of packets to be dropped is determined prior to the next overflow.
Claim 7
Dependent Claim
26 words
The method as claimed in claim 1, wherein the next packet to be dropped can be determined prior to each overflow using said state transition rule.
Claim 8
Dependent Claim
21 words
The method as claimed in claim 1, wherein said method is independent of packet arrival statistics, buffer size, and buffer location.
Claim 9
Dependent Claim
23 words
The method as claimed in claim 1, wherein said system reaches steady-state within the time required for servicing one complete buffer of packets.
Claim 10
Dependent Claim
31 words
The method as claimed in claim 1, wherein said dropping step occurs with a packet dropping policy that creates the gap as close as possible to the front of the buffer.
Claim 11
Dependent Claim
14 words
The method as claimed in claim 1, wherein said packets have deterministic service requirements.
Claim 12
Independent Claim
81 words
A method for producing a desired average gap size between customer processes in a finite buffer of a service system, comprising the steps of: receiving incoming customer processes at said service system; releasing outgoing customer processes from said service system; selecting a state transition rule based on the desired average gap size; and creating gaps in said finite buffer according to said state transition rule, when said finite buffer reaches overflow, to produce said desired average gap size between customer processes.
Claim 13
Independent Claim
81 words
A method for producing a desired average gap size between customer processes in a finite buffer of a service system, comprising the steps of: receiving incoming customer processes at said service system; releasing outgoing customer processes from said service system; selecting a state transition rule based on the desired average gap size; and creating gaps in said finite buffer according to said state transition rule, when said finite buffer reaches overflow, to produce said desired average gap size between customer processes.
Claim 14
Dependent Claim
107 words
A packet buffer circuit for producing a desired consecutive packet loss, comprising: a buffer storage means for receiving incoming packets and transmitting departing packets, said buffer storage means generating at least one buffer state signal to indicate an overflow condition and receiving a dropping pointer signal to indicate the location of a packet to be dropped; and a dropping pointer generator, connected to said buffer storage means, for receiving said at least one buffer state signal and for generating, in response to said at least one buffer state signal, a dropping pointer signal, according to a state transition rule selected to produce said desired consecutive packet loss.
Claim 15
Dependent Claim
107 words
A packet buffer circuit for producing a desired consecutive packet loss, comprising: a buffer storage means for receiving incoming packets and transmitting departing packets, said buffer storage means generating at least one buffer state signal to indicate an overflow condition and receiving a dropping pointer signal to indicate the location of a packet to be dropped; and a dropping pointer generator, connected to said buffer storage means, for receiving said at least one buffer state signal and for generating, in response to said at least one buffer state signal, a dropping pointer signal, according to a state transition rule selected to produce said desired consecutive packet loss.
Claim 16
Dependent Claim
130 words
A packet switched system having an interconnected plurality of nodes, wherein at least one of said plurality of nodes includes a buffer circuit for producing a desired consecutive packet loss, wherein said buffer circuit includes: a buffer storage means for receiving incoming packets and transmitting departing packets, said buffer storage means generating at least one buffer state signal to indicate an overflow condition and receiving a dropping pointer signal to indicate the location of a packet to be dropped; and a dropping pointer generator, connected to said buffer storage means, for receiving said at least one buffer state signal and for generating, in response to said at least one buffer state signal, a dropping pointer signal, according to a state transition rule selected to produce said desired consecutive packet loss.
Claim 17
Dependent Claim
130 words
A packet switched system having an interconnected plurality of nodes, wherein at least one of said plurality of nodes includes a buffer circuit for producing a desired consecutive packet loss, wherein said buffer circuit includes: a buffer storage means for receiving incoming packets and transmitting departing packets, said buffer storage means generating at least one buffer state signal to indicate an overflow condition and receiving a dropping pointer signal to indicate the location of a packet to be dropped; and a dropping pointer generator, connected to said buffer storage means, for receiving said at least one buffer state signal and for generating, in response to said at least one buffer state signal, a dropping pointer signal, according to a state transition rule selected to produce said desired consecutive packet loss.
Claim 18
Independent Claim
66 words
A method for producing a desired average packet gap size in a packet buffer, comprising the steps of: receiving an arriving packet at said packet buffer; dropping a packet at a predetermined position at any location within said packet buffer, said predetermined position indicated by a pointer in said packet buffer at the time of an overflow; and appending said arriving packet in said packet buffer.
Claim 19
Independent Claim
66 words
A method for producing a desired average packet gap size in a packet buffer, comprising the steps of: receiving an arriving packet at said packet buffer; dropping a packet at a predetermined position at any location within said packet buffer, said predetermined position indicated by a pointer in said packet buffer at the time of an overflow; and appending said arriving packet in said packet buffer.
Claim 20
Dependent Claim
19 words
The method as claimed in claim 14, further comprising the step of updating said pointer after said dropping step.
Claim 21
Independent Claim
94 words
A method for producing a desired average packet gap size in a packet buffer, wherein the desired average packet gap size is determined by the type of information in the packet buffer, comprising the steps of: receiving an arriving packet at said packet buffer; and dropping one of said arriving packet and a packet at a predetermined position in said packet buffer indicated by a pointer at the time of an overflow, wherein said predetermined position can be any position within said packet buffer and is determined by the desired average packet gap size.
Claim 22
Independent Claim
94 words
A method for producing a desired average packet gap size in a packet buffer, wherein the desired average packet gap size is determined by the type of information in the packet buffer, comprising the steps of: receiving an arriving packet at said packet buffer; and dropping one of said arriving packet and a packet at a predetermined position in said packet buffer indicated by a pointer at the time of an overflow, wherein said predetermined position can be any position within said packet buffer and is determined by the desired average packet gap size.
Claim 23
Independent Claim
113 words
A method for directly controlling average packet gap size in a packet buffer in a system carrying multiple classes of packets, comprising the steps of: receiving incoming packets of said multiple classes of packets at said packet buffer; transmitting outgoing packets of said multiple classes of packets from said packet buffer; and dropping packets of said multiple classes of packets from said packet buffer according to class-specific state transition rules, when said packet buffer reaches overflow, to minimize average packet gap size of at least one of said multiple classes of packets and to maximize average packet gap size of at least one other of said multiple classes of packets for each overflow.
Claim 24
Independent Claim
113 words
A method for directly controlling average packet gap size in a packet buffer in a system carrying multiple classes of packets, comprising the steps of: receiving incoming packets of said multiple classes of packets at said packet buffer; transmitting outgoing packets of said multiple classes of packets from said packet buffer; and dropping packets of said multiple classes of packets from said packet buffer according to class-specific state transition rules, when said packet buffer reaches overflow, to minimize average packet gap size of at least one of said multiple classes of packets and to maximize average packet gap size of at least one other of said multiple classes of packets for each overflow.
Claim 25
Dependent Claim
48 words
The method as claimed in claim 17, wherein the minimization of average packet gap size of said at least one of said multiple classes of packets and the maximization of average packet gap size of said at least one other of said multiple classes of packets occur simultaneously.
Claim 26
Dependent Claim
85 words
The method as claimed in claim 17, wherein the minimization of average packet gap size of said at least one of said multiple classes of packets and the maximization of average packet gap size of said at least one other of said multiple classes of packets can be dynamically changed from minimization to maximization, and vice versa, as the needs of each of said at least one of said multiple classes of packets and said one other of said multiple classes of packets traffic change.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-05-12 | 2000-11-11 | 2001-05-13 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-05-12 | 2004-11-11 | 2005-05-13 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-05-12 | 2008-11-11 | 2009-05-13 | $7700.00 | Window Closed / Lapsed |