US6094435A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method for a quality of service in a multi-layer network element
Assignee: Microsoft Corp
•
Filing: 1997-06-30
•
Granted: 2000-07-25
•
Expires: 2017-06-30
Abstract
Abstract A multi-layer network element for forwarding received packets from an input port to one or more output ports with quality of service. When output queues exceed or meet a threshold value below the queue's capacity packets are ramdomly discarded. When the queue becomes full, the network element determines which flow caused the queue to overflow. The priority of that flow is lowered. In a multicast packet, the packet may have different priorities at each output port. Scheduling of multiple output queues at each output port uses a weight round robin approach that allocates a weight portion of packets to transmit at each time interval. A packet is not interrupted during its transmission, even if the weight portion is met during a packet's transmission. The excess number of bytes transmited as a result of not interrupting the packet are accounted for in the next round.
Inventors
- 👤 Don Hoffman
- 👤 Shree Murthy
- 👤 Asad Khamisy
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 06:59
CPC Classifications
H; H04; H04L; H04L47/00; H04L47/10; H04L47/15; H04L47/20; H04L47/21; H04L47/24; H04L47/2458; H04L47/30; H04L47/32; H04L47/326; H04L47/50; H04L47/52; H04L47/522; H04L47/62; H04L47/6215; H04L47/622; H04L47/6225; H04L47/623; H04L47/625; H04L47/6265; H04L49/00; H04L49/90; H04L49/901; H04L49/9042; H04L49/9047; H04L49/9063; H04L49/9078; H04Q; H04Q2213/00; H04Q2213/13103
Claims Analysis
Total Claims: 6
Claim 1
Independent Claim
425 words
An apparatus for detecting and handling queue congestion in an output port of a multi-layer network element comprising: a central processing unit (CPU); a switching element coupled to the CPU and configured to output packets to a network through the output port, the switching element including: at least one output queue having storage locations for packet pointers, each pointer configured to point to portions of a packet to be transmitted on the network, associated with the output port, and wherein the number of storage locations is variable, a start register configured to store a pointer to the storage location at the front of the queue, an end register configured to store a pointer to the storage location at the end of the queue as determined by the number of storage locations, a next-free register configured to store a pointer to the next available storage location, wherein packet pointers are stored in the output queue beginning at the location pointed to by the start register and the next-free register is incremented as the next available storage location moves toward the second pointer, a programmable threshold register configured to store a threshold pointer to a storage location between the location represented by the start register and the location represented by the end register, threshold logic configured to output a congestion signal when the value in the next free register represents a storage location logically located between the location pointed to key the threshold register and including the storage location pointed to by the end register, random discarding logic configured to randomly select packets to discard in response to the signal, so that once the threshold is exceeded, incoming packets are randomly discarded, capacity logic configured to output a queue full signal to the CPU when the value in the next free register is equal to the value in the end register, a memory having at least one entry configured to store information about forwarding decisions for the packet, wherein the entry is adapted to indicate whether packets associated with that entry should be counted, memory access logic configured to access the entry when an incoming packet associated with that entry arrives at the switching element, and a packet counter configured to count the number of times the entry is accessed, to represent an entry bandwidth; and a computer program mechanism coupled to the CPU configured to compare the contents of the packet counter to a reservation-based protocol negotiated value for lowering a priority of any future packet associated with the entry and destined for the output queue.
Claim 2
Independent Claim
425 words
An apparatus for detecting and handling queue congestion in an output port of a multi-layer network element comprising: a central processing unit (CPU); a switching element coupled to the CPU and configured to output packets to a network through the output port, the switching element including: at least one output queue having storage locations for packet pointers, each pointer configured to point to portions of a packet to be transmitted on the network, associated with the output port, and wherein the number of storage locations is variable, a start register configured to store a pointer to the storage location at the front of the queue, an end register configured to store a pointer to the storage location at the end of the queue as determined by the number of storage locations, a next-free register configured to store a pointer to the next available storage location, wherein packet pointers are stored in the output queue beginning at the location pointed to by the start register and the next-free register is incremented as the next available storage location moves toward the second pointer, a programmable threshold register configured to store a threshold pointer to a storage location between the location represented by the start register and the location represented by the end register, threshold logic configured to output a congestion signal when the value in the next free register represents a storage location logically located between the location pointed to key the threshold register and including the storage location pointed to by the end register, random discarding logic configured to randomly select packets to discard in response to the signal, so that once the threshold is exceeded, incoming packets are randomly discarded, capacity logic configured to output a queue full signal to the CPU when the value in the next free register is equal to the value in the end register, a memory having at least one entry configured to store information about forwarding decisions for the packet, wherein the entry is adapted to indicate whether packets associated with that entry should be counted, memory access logic configured to access the entry when an incoming packet associated with that entry arrives at the switching element, and a packet counter configured to count the number of times the entry is accessed, to represent an entry bandwidth; and a computer program mechanism coupled to the CPU configured to compare the contents of the packet counter to a reservation-based protocol negotiated value for lowering a priority of any future packet associated with the entry and destined for the output queue.
Claim 3
Independent Claim
195 words
An apparatus for queue scheduling in a network element comprising: at least one output port configured to output packets, each packet having a byte length; at least two queues associated with each output port, configured to queue packets to be output at each output port; a weight register associated with each queue and adapted to receive a value representing a weight number; weighting logic for generating the weight number for each queue; transmitting logic at each output port configured to transmit packets identified in each queue according to a queue select signal and responsive to a done signal; scheduling logic at each output port configured to select one of the queues and to generate the queue select signal to the transmitting logic to indicate which queue will be transmitting; counter logic, at each output port, associated with the counters configured to decrement the weight register equal to a number of bytes transmitted by the transmitting logic; and reloading logic configured to determine the number of packets transmitted after the done signal and to place in the weight register a value equal to the weight number minus the number of packets transmitted after the done signal.
Claim 4
Independent Claim
195 words
An apparatus for queue scheduling in a network element comprising: at least one output port configured to output packets, each packet having a byte length; at least two queues associated with each output port, configured to queue packets to be output at each output port; a weight register associated with each queue and adapted to receive a value representing a weight number; weighting logic for generating the weight number for each queue; transmitting logic at each output port configured to transmit packets identified in each queue according to a queue select signal and responsive to a done signal; scheduling logic at each output port configured to select one of the queues and to generate the queue select signal to the transmitting logic to indicate which queue will be transmitting; counter logic, at each output port, associated with the counters configured to decrement the weight register equal to a number of bytes transmitted by the transmitting logic; and reloading logic configured to determine the number of packets transmitted after the done signal and to place in the weight register a value equal to the weight number minus the number of packets transmitted after the done signal.
Claim 5
Dependent Claim
27 words
The apparatus of claim 2, wherein the scheduling logic is configured to respond to the done signal and the transmitting logic to select a next transmitting queue.
Claim 6
Dependent Claim
29 words
The apparatus of claim 2, wherein the scheduling logic is configured to select a next transmitting queue at a time prior to the zero logic generating the done signal.
References Cited (Backward Citations)
US4539637A
Cited
US4627052A
Cited
US4652874A
Cited
US4641302A
Cited
US4935869A
Cited
US4737953A
Cited
US4850042A
Cited
US4807111A
Cited
US4811337A
Cited
US4899333A
Cited
US4922503A
Cited
US4933938A
Cited
US5220562A
Cited
US5130977A
Cited
US5278830A
Cited
US5163046A
Cited
US5159685A
Cited
US5210746A
Cited
US5301333A
Cited
US5309437A
Cited
US5231633A
Cited
US5150358A
Cited
US5481540A
Cited
US5251205A
Cited
US5353412A
Cited
US5490260A
Cited
US5293379A
Cited
US5872904A
Cited
US5500860A
Cited
US5420862A
Cited
US5392432A
Cited
US5623489A
Cited
US5875464A
Cited
US5461624A
Cited
US5313454A
Cited
US5343471A
Cited
US5742760A
Cited
US5720032A
Cited
US5432907A
Cited
US5457681A
Cited
US5517488A
Cited
US5425028A
Cited
US5291482A
Cited
US5490252A
Cited
US5410540A
Cited
US5649109A
Cited
US5404538A
Cited
US5425026A
Cited
US5410722A
Cited
US5459714A
Cited
US5365514A
Cited
US5485578A
Cited
US5386413A
Cited
US5477537A
Cited
US5402415A
Cited
US5455820A
Cited
US5426736A
Cited
US5396602A
Cited
US5553067A
Cited
US5394402A
Cited
US5450399A
Cited
US5555405A
Cited
US5610905A
Cited
US5515376A
Cited
US5473607A
Cited
US5422838A
Cited
US5574861A
Cited
US5790546A
Cited
US5485455A
Cited
US5570365A
Cited
US5535202A
Cited
US5761435A
Cited
US5509123A
Cited
US5493564A
Cited
US5459717A
Cited
US5602841A
Cited
US5572522A
Cited
US5592476A
Cited
US5557610A
Cited
US5689518A
Cited
US5606669A
Cited
US5461611A
Cited
US5617421A
Cited
US5583981A
Cited
US5600641A
Cited
US5615340A
Cited
US5751967A
Cited
US5640605A
Cited
US5619500A
Cited
US5594727A
Cited
US5490139A
Cited
US5675741A
Cited
US5784573A
Cited
US5931980A
Cited
US5726977A
Cited
US5619497A
Cited
US5867677A
Cited
US5550816A
Cited
US5566170A
Cited
US5563878A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-07-25 | 2004-01-24 | 2004-07-25 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-07-25 | 2008-01-24 | 2008-07-25 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-07-25 | 2012-01-24 | 2012-07-25 | $7700.00 | Window Closed / Lapsed |