US5764641A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Early and integrated tail packet discard system
Assignee: Cisco Technology Inc
•
Filing: 1995-09-08
•
Granted: 1998-06-09
•
Expires: 2015-09-08
Abstract
Abstract A switch in an asynchronous transfer mode system utilizes an early packet discard (EPD) scheme and discards all but the end-of-packet cell of packets that are expected to prevent other partially transmitted packets from being transmitted through the switch. The switch also utilizes an integrated tail packet discard (I-TPD) scheme and, once a cell of a packet has been discarded for any reason, discards all of the remaining cells of the packet except the end-of-packet cell. Each of the EPD and the I-TPD schemes retain the last cell of a packet in order to maintain packet boundaries. Further, they each set the loss-priority of the end-of-packet cell to high, to increase the likelihood that the cell will be transmitted through the remaining switches in the route to the station to which the packet is directed. When the end-of-packet cell is received, the switch retains the cell unless its maximum queue limit is exceeded, and resets any associated early or tail packet discard flag. When the beginning of the next packet is received, the switch checks its queue length against an associated queue limit and against a CLP and an EPD threshold to determine whether or not to retain the cell. If the cell is discarded, the switch invokes, as appropriate, either the EPD or I-TPD and thereafter discards cells of the same packet. It invokes EPD when the queue limit exceeds the EPD threshold, and invokes I-TPD if it discards this or any cell when (a) it is policing a usage or network parameter control violation, (b) its associated queue exceeds an applicable queue limit, or (c) it selectively discards low-priority cells.
Inventors
- 👤 Arthur Lin
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-25 20:07
CPC Classifications
H; H04; H04Q; H04Q11/00; H04Q11/04; H04Q11/0428; H04Q11/0478; H04L; H04L12/00; H04L12/54; H04L12/56; H04L12/5601; H04L2012/5638; H04L2012/5646; H04L2012/5647; H04L2012/5651; H04L2012/5652; H04L2012/5665
Claims Analysis
Total Claims: 27
Claim 1
Independent Claim
184 words
A method of operating a switch to discard or retain cells received over a network operating in asynchronous transfer mode, the method including the steps of: A. determining if a received cell is an end-of-packet cell, and if so, retaining the cell and associating with the cell a high priority; B. determining if the received cell is the beginning of a packet, and if so, determining if a queue of received packets that is associated with an output port to which the cell is directed exceeds an early packet discard threshold, C. if the early packet discard threshold is exceeded discarding the received beginning-of-packet cell and setting an early packet discard flag associated with a virtual circuit identified in the cell, and otherwise retaining the cell; D. if the cell is not a beginning-of-packet cell or an end-of-packet cell, determining if the early packet discard flag associated with the virtual circuit identified in the cell is set, and if the flag is set discarding the cell or if the flag is not set retaining the cell; and F. repeating steps A-D for each cell.
Claim 2
Independent Claim
184 words
A method of operating a switch to discard or retain cells received over a network operating in asynchronous transfer mode, the method including the steps of: A. determining if a received cell is an end-of-packet cell, and if so, retaining the cell and associating with the cell a high priority; B. determining if the received cell is the beginning of a packet, and if so, determining if a queue of received packets that is associated with an output port to which the cell is directed exceeds an early packet discard threshold, C. if the early packet discard threshold is exceeded discarding the received beginning-of-packet cell and setting an early packet discard flag associated with a virtual circuit identified in the cell, and otherwise retaining the cell; D. if the cell is not a beginning-of-packet cell or an end-of-packet cell, determining if the early packet discard flag associated with the virtual circuit identified in the cell is set, and if the flag is set discarding the cell or if the flag is not set retaining the cell; and F. repeating steps A-D for each cell.
Claim 3
Dependent Claim
96 words
The method of claim 1 further including: a first step of L. determining if the cell is in violation of a usage or network parameter control, and if so, discarding the cell and setting the associated tail packet discard flag; and in the step of discarding or retaining the cell that is not a beginning-of-packet cell or an end-of-packet cell, further including M. determining if the tail packet discard flag associated with the virtual circuit identified in the cell is set and if so discarding each received cell that is not an end of packet cell.
Claim 4
Dependent Claim
75 words
The method of claim 2 further including, before the step of determining if the cell is an end-of-packet cell, the steps of: N. determining if the received cell has a low cell loss priority, and if so, comparing the length of the queue of received cells associated with the output port to a predetermined low-priority buffer threshold; Q. discarding the received cell if the threshold is exceeded, and setting the associated tail packet discard flag.
Claim 5
Dependent Claim
23 words
The method of claim 1 wherein the early packet discard threshold is a percentage of an associated service class per port queue limit.
Claim 6
Dependent Claim
21 words
The method of claim 1 wherein the early packet discard threshold is a percentage of an associated per connection queue limit.
Claim 7
Dependent Claim
30 words
The method of claim 4 wherein if the threshold based on the service class queue limit is exceeded, an associated threshold based on a per connection queue limit is checked.
Claim 8
Independent Claim
231 words
A method of operating a switch to discard or retain cells received over a network operating in asynchronous transfer mode, the method including the steps of: A. determining if a received cell violates usage or network parameter controls, and if so discarding the cell and setting a tail packet discard flag; B. if the tail packet discard flag is not set, determining if a queue of retained cells, that is associated with an output port that is part of the virtual circuit identified in the cell, exceeds an associated queue limit, and if the limit is exceeded, discarding the cell and setting the associated tail packet discard flag; C. determining, if the switch is operating in a CLP-selective discard mode and the cell has a low priority, and if so, comparing the length of the output port queue with a predetermined low-CLP threshold and discarding the cell and setting the associated tail packet discard flag if the threshold is exceeded; D. determining if the cell is an end-of-packet cell, and if so associating with the cell a high priority, retaining the cell and re-setting, as necessary, the associated tail packet discard flag; E. if the cell is not an end-of-packet cell, determining if the associated tail packet discard flag is set, and if so discarding the cell; and F. retaining the cell if the cell is not discard in steps A-E.
Claim 9
Independent Claim
231 words
A method of operating a switch to discard or retain cells received over a network operating in asynchronous transfer mode, the method including the steps of: A. determining if a received cell violates usage or network parameter controls, and if so discarding the cell and setting a tail packet discard flag; B. if the tail packet discard flag is not set, determining if a queue of retained cells, that is associated with an output port that is part of the virtual circuit identified in the cell, exceeds an associated queue limit, and if the limit is exceeded, discarding the cell and setting the associated tail packet discard flag; C. determining, if the switch is operating in a CLP-selective discard mode and the cell has a low priority, and if so, comparing the length of the output port queue with a predetermined low-CLP threshold and discarding the cell and setting the associated tail packet discard flag if the threshold is exceeded; D. determining if the cell is an end-of-packet cell, and if so associating with the cell a high priority, retaining the cell and re-setting, as necessary, the associated tail packet discard flag; E. if the cell is not an end-of-packet cell, determining if the associated tail packet discard flag is set, and if so discarding the cell; and F. retaining the cell if the cell is not discard in steps A-E.
Claim 10
Dependent Claim
109 words
The method of claim 7, further including the steps of: G. determining if the cell is a beginning-of-packet cell, and if so, determining if the queue associated with the output port exceeds an early packet discard buffer threshold; H. if the early packet discard threshold is exceeded, discarding the cell and setting an associated early packet discard flag; I. if the early packet discard flag is set, discarding each of the cells associated with the same virtual circuit until the end-of-packet cell is received; J. when the end-of-packet cell is received, resetting the associated early packet discard flag, associating a high priority with the cell and retaining the cell.
Claim 11
Dependent Claim
21 words
The method of claim 8, wherein the tail packet discard flag and the early packet discard flag are the same flag.
Claim 12
Dependent Claim
34 words
The method of claim 7 wherein the step of determining if the associated output port queue is exceeded further includes determining if an associated threshold based on a service class queue limit is exceeded.
Claim 13
Dependent Claim
23 words
The method of claim 10 further including determining if a second threshold based on a service class per port queue limit is exceeded.
Claim 14
Dependent Claim
298 words
A switch for discarding or retaining for further transmission cells received over a network operating in asynchronous transfer mode, the cells being associated with a packet that includes a plurality of cells, the switch including: A. plurality of input ports for receiving cells over the network; B. a plurality of output ports for transmitting cells over the network; C. a buffer with a plurality of locations for retaining in each of the locations a cell for transmission by one or more of the output ports; D. a controller for controlling the ports and the buffer, the controller including i. means for associating with each output port one or more queue limits that set maximum numbers of buffer locations that may be allocated to retained cells that are awaiting transmission by the port; ii. means for determining, when a cell is received, if the cell violates associated usage or network control parameters, and if so, discarding the cell; iii. means for determining if the queue of retained cells associated with the output port to which the cell is directed has reached the applicable queue limit, and if so, discarding the cell; iv. tail packet discard means for, when a cell is discarded, invoking tail packet discarding, said means discarding all the received cells that are associated with the same packet as the cell that caused the invocation of the tail packet discarding, except an associated end-of-packet cell; v. end-of-packet means for determining if the received cell is an end-of-packet cell, said means associating a high priority with the end-of-packet cell and retaining the cell, said means directing the tail packet discard means to revoke the tail packet discarding when the end-of-packet cell is retained; and vi. means for retaining in the buffer the cells that have not been discarded.
Claim 15
Dependent Claim
298 words
A switch for discarding or retaining for further transmission cells received over a network operating in asynchronous transfer mode, the cells being associated with a packet that includes a plurality of cells, the switch including: A. plurality of input ports for receiving cells over the network; B. a plurality of output ports for transmitting cells over the network; C. a buffer with a plurality of locations for retaining in each of the locations a cell for transmission by one or more of the output ports; D. a controller for controlling the ports and the buffer, the controller including i. means for associating with each output port one or more queue limits that set maximum numbers of buffer locations that may be allocated to retained cells that are awaiting transmission by the port; ii. means for determining, when a cell is received, if the cell violates associated usage or network control parameters, and if so, discarding the cell; iii. means for determining if the queue of retained cells associated with the output port to which the cell is directed has reached the applicable queue limit, and if so, discarding the cell; iv. tail packet discard means for, when a cell is discarded, invoking tail packet discarding, said means discarding all the received cells that are associated with the same packet as the cell that caused the invocation of the tail packet discarding, except an associated end-of-packet cell; v. end-of-packet means for determining if the received cell is an end-of-packet cell, said means associating a high priority with the end-of-packet cell and retaining the cell, said means directing the tail packet discard means to revoke the tail packet discarding when the end-of-packet cell is retained; and vi. means for retaining in the buffer the cells that have not been discarded.
Claim 16
Dependent Claim
88 words
The switch of claim 12, wherein the controller further includes vii. CLP-selective discarding means for determining if a received cell has associated with it a low priority, and if so, determining if the associated queue has reached a low-CLP threshold, discarding the cell if the queue has reached the threshold, and if the cell has a high priority, setting the priority of the cell to low and retaining the cell, said means directing the tail packet discard means to invoke tail packet discarding if the cell is discarded.
Claim 17
Dependent Claim
110 words
The switch of claim 13, wherein the controller further includes viii. an early packet discard means, said means determining if a cell is a beginning-of-packet cell, and if so, determining if the queue associated with the output port queue to which the cell is directed exceeds an early packet discard threshold, said means discarding the cell and invoking early packet discarding if the appropriate threshold is exceeded, wherein said means discards all received cells that are associated with the same packet as the cell that caused the invocation of the early packet discarding, except an end-of-packet cell, said means revoking the early packet discarding if the end-of-packet cell is retained.
Claim 18
Dependent Claim
25 words
The switch of claim 14, wherein the buffer is shared among the output ports, and the buffer locations are dynamically allocated to the output ports.
Claim 19
Dependent Claim
26 words
The switch of claim 15, wherein the early packet discard threshold associated with a particular output port is based on the expected traffic at the port.
Claim 20
Dependent Claim
19 words
The switch of claim 16, wherein the queue limits associated with the output ports vary by delay service class.
Claim 21
Dependent Claim
29 words
The switch of claim 17, wherein the controller determines if the received cell is the end-of-packet cell by determining the state of a status flag in the cell header.
Claim 22
Dependent Claim
19 words
The switch of claim 14, wherein the CLP and early packet discard thresholds are percentages of the queue limits.
Claim 23
Dependent Claim
22 words
The switch of claim 19, wherein the early packet discard threshold is a percentage of a service class per port queue limit.
Claim 24
Dependent Claim
21 words
The switch of claim 19, wherein the early packet discard threshold is a percentage of an associated per connection queue limit.
Claim 25
Dependent Claim
43 words
The switch of claim 20, wherein the early packet threshold further includes a second threshold based on a per connection queue limit, the early packet discard means determining if the second threshold is exceeded after it determines that the first threshold is exceeded.
Claim 26
Dependent Claim
32 words
The switch of claim 12 wherein the tail packet discard means discards successive packets in a transmission window once tail packet discarding is invoked for one of the packets in the window.
Claim 27
Dependent Claim
32 words
The switch of claim 14 wherein the early packet discard means discards successive packets in a transmission window once early packet discarding is invoked for one of the packets in the window.
References Cited (Backward Citations)
US5231633A
Cited
US5166930A
Cited
US5321692A
Cited
US5303302A
Cited
US5323389A
Cited
US5479401A
Cited
US5434855A
Cited
US5528588A
Cited
US5495478A
Cited
US5541918A
Cited
US5548588A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-06-08 | 2001-12-08 | 2002-06-09 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-06-08 | 2005-12-08 | 2006-06-09 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-06-08 | 2009-12-08 | 2010-06-09 | $7700.00 | Window Closed / Lapsed |