US6047000A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Packet scheduling system
Assignee: Hong Kong University of Science and Technology
•
Filing: 1997-07-24
•
Granted: 2000-04-04
•
Expires: 2017-07-24
Abstract
Abstract A packet scheduling system is disclosed in which a plurality of first-in-first-out input buffers are provided each corresponding to a respective input data stream to a switching node or multiplexer. Credit is allocated to each stream having packets waiting to be transmitted and which is unable to transmit, and the next stream to be transmitted is based on the allocated credit values, the credit of a transmitted stream being reduced after transmission of a data packet from that stream.
Inventors
- 👤 Danny Hin-Kwok Tsang
- 👤 Brahim Bensaou
- 👤 King Tung Chan
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 13:24
CPC Classifications
H; H04; H04L; H04L47/00; H04L47/50; H04L47/56; H04L47/562; H04L12/00; H04L12/54; H04L12/56; H04L12/5601; H04L12/5602; H04L47/52; H04L47/527; H04L47/62; H04L47/6215; H04L49/00; H04L49/90; H04L49/9021; H04Q; H04Q11/00; H04Q11/04; H04Q11/0428; H04Q11/0478; H04L2012/5638; H04L2012/5646; H04L2012/5651; H04L2012/5678; H04L2012/5679; H04L2012/5681
Claims Analysis
Total Claims: 13
Claim 1
Independent Claim
274 words
A packet scheduling system for packets of variable size, comprising: a plurality of first-in-first-out buffers each corresponding to a respective input stream of data packets that is allocated a share of the bandwidth of an output transmission link, means for allocating credit to each said buffer when said buffer contains at least one data packet and is unable to transmit, means for successively selecting a buffer holding data to be transmitted based on the credit allocated to said buffers and chosen fairness criteria, including means for determining the credit allocated to each buffer, the bandwidth allocated to each input stream, and the size of the head-of-line packet waiting to be transmitted in each buffer, means for sorting said head-of-line packets in accordance with the difference between said packet size and said allocated credit as a proportion of the bandwidth allocated to the associated input stream, whereby the buffer having an allocated credit closest to the packet size as a proportion of allocated bandwidth of its associated input stream is selected for transmission, and means for increasing the credits of all the buffers having packets to be transmitted which are unable to transmit by an incremental amount equal to the proportion of their respective stream's bandwidth share to the bandwidth share of the stream associated with the selected buffer, multiplied by the difference between the transmitted packet size and the allocated credit of the stream associated with the selected buffer, means for transmitting a waiting packet from a selected buffer to said output transmission link, and means for reducing the credit of said selected buffer upon transmission of a waiting packet from said selected buffer.
Claim 2
Dependent Claim
274 words
A packet scheduling system for packets of variable size, comprising: a plurality of first-in-first-out buffers each corresponding to a respective input stream of data packets that is allocated a share of the bandwidth of an output transmission link, means for allocating credit to each said buffer when said buffer contains at least one data packet and is unable to transmit, means for successively selecting a buffer holding data to be transmitted based on the credit allocated to said buffers and chosen fairness criteria, including means for determining the credit allocated to each buffer, the bandwidth allocated to each input stream, and the size of the head-of-line packet waiting to be transmitted in each buffer, means for sorting said head-of-line packets in accordance with the difference between said packet size and said allocated credit as a proportion of the bandwidth allocated to the associated input stream, whereby the buffer having an allocated credit closest to the packet size as a proportion of allocated bandwidth of its associated input stream is selected for transmission, and means for increasing the credits of all the buffers having packets to be transmitted which are unable to transmit by an incremental amount equal to the proportion of their respective stream's bandwidth share to the bandwidth share of the stream associated with the selected buffer, multiplied by the difference between the transmitted packet size and the allocated credit of the stream associated with the selected buffer, means for transmitting a waiting packet from a selected buffer to said output transmission link, and means for reducing the credit of said selected buffer upon transmission of a waiting packet from said selected buffer.
Claim 3
Dependent Claim
21 words
A system as claimed in claim 1 wherein each said buffer comprises an independent buffer associated with a respective input stream.
Claim 4
Dependent Claim
26 words
A system as claimed in claim 1 wherein said buffers comprise a shared buffer in which each input stream is associated with a linked memory list.
Claim 5
Dependent Claim
25 words
A system as claimed in claim 1 wherein after transmitting a packet from one stream the counter corresponding to that stream is reset to zero.
Claim 6
Dependent Claim
218 words
A packet scheduling system for packets which are all of a fixed size, comprising: a plurality of first-in-first-out buffers each corresponding to a respective input stream of data packets that is allocated a share of the bandwidth of an output transmission link, where a stream with the largest reserved bandwidth is designated as a default reference stream, means for allocating credit to each said buffer when said buffer contains at least one data packet and is unable to transmit, means for successively selecting a buffer holding data to be transmitted based on the credit allocated to said buffers and chosen fairness criteria, including means for choosing randomly from all the buffers having an allocated credit equal to or greater than a normalized fixed packet size, and in the absence of any such buffer the buffer associated with the reference stream, and means for increasing the credits of all the buffers having packets to be transmitted which are unable to transmit by an incremental amount equal to the proportion of their associated stream's respective bandwidth share to the largest bandwidth share of any stream, means for transmitting a waiting packet from a selected buffer to said output transmission link, and means for reducing the credit of said selected buffer upon transmission of a waiting packet from said selected buffer.
Claim 7
Dependent Claim
218 words
A packet scheduling system for packets which are all of a fixed size, comprising: a plurality of first-in-first-out buffers each corresponding to a respective input stream of data packets that is allocated a share of the bandwidth of an output transmission link, where a stream with the largest reserved bandwidth is designated as a default reference stream, means for allocating credit to each said buffer when said buffer contains at least one data packet and is unable to transmit, means for successively selecting a buffer holding data to be transmitted based on the credit allocated to said buffers and chosen fairness criteria, including means for choosing randomly from all the buffers having an allocated credit equal to or greater than a normalized fixed packet size, and in the absence of any such buffer the buffer associated with the reference stream, and means for increasing the credits of all the buffers having packets to be transmitted which are unable to transmit by an incremental amount equal to the proportion of their associated stream's respective bandwidth share to the largest bandwidth share of any stream, means for transmitting a waiting packet from a selected buffer to said output transmission link, and means for reducing the credit of said selected buffer upon transmission of a waiting packet from said selected buffer.
Claim 8
Dependent Claim
23 words
A system as claimed in claim 5 wherein each stream that is transmitted has its credit reduced by the normalized fixed packet size.
Claim 9
Dependent Claim
31 words
A system as claimed in claim 5 wherein the unused bandwidth allocated to streams having no data packets to transmit is available for use by streams having data packets to transmit.
Claim 10
Dependent Claim
17 words
A system as claimed in claim 5 wherein each stream only has available its respective bandwidth share.
Claim 11
Dependent Claim
236 words
A packet scheduling system for data packets which are all of a fixed size and transmitted via input streams that are allocated a respective share of the bandwidth of an output transmission link, wherein unused bandwidth allocated to streams having no packets to transmit is available for use by streams having a packet to transmit, and wherein a predetermined time interval is defined equal to the time required to transmit one data packet, comprising: a plurality of first-in-first-out buffers each corresponding to a respective input stream of data packets, means for allocating credit to each said buffer when said buffer contains at least one data packet and is unable to transmit, wherein for each time interval that a buffer having packets to transmit is unable to transmit the credit for that buffer is increased by an increment corresponding to the bandwidth share of its associated stream as a fraction of the total bandwidth of the output link, means for successively selecting a buffer holding data to be transmitted based on the credit allocated to said buffers and chosen fairness criteria, including means for comparing the credit allocated to said buffers and means for choosing the buffer with the largest credit allocation, means for transmitting a waiting packet from a selected buffer to said output transmission link, and means for reducing the credit of said selected buffer upon transmission of a waiting packet from said selected buffer.
Claim 12
Dependent Claim
236 words
A packet scheduling system for data packets which are all of a fixed size and transmitted via input streams that are allocated a respective share of the bandwidth of an output transmission link, wherein unused bandwidth allocated to streams having no packets to transmit is available for use by streams having a packet to transmit, and wherein a predetermined time interval is defined equal to the time required to transmit one data packet, comprising: a plurality of first-in-first-out buffers each corresponding to a respective input stream of data packets, means for allocating credit to each said buffer when said buffer contains at least one data packet and is unable to transmit, wherein for each time interval that a buffer having packets to transmit is unable to transmit the credit for that buffer is increased by an increment corresponding to the bandwidth share of its associated stream as a fraction of the total bandwidth of the output link, means for successively selecting a buffer holding data to be transmitted based on the credit allocated to said buffers and chosen fairness criteria, including means for comparing the credit allocated to said buffers and means for choosing the buffer with the largest credit allocation, means for transmitting a waiting packet from a selected buffer to said output transmission link, and means for reducing the credit of said selected buffer upon transmission of a waiting packet from said selected buffer.
Claim 13
Dependent Claim
25 words
A system as claimed in claim 9 wherein each stream that is transmitted has its credit allocation reduced by the size of a data packet.
References Cited (Backward Citations)
US5313454A
Cited
US5392280A
Cited
US5633867A
Cited
US5796735A
Cited
US5850398A
Cited
US5864540A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-04-04 | 2003-10-04 | 2004-04-04 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-04-04 | 2007-10-04 | 2008-04-04 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-04-04 | 2011-10-04 | 2012-04-04 | $7700.00 | Window Closed / Lapsed |