US6262986B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for packet scheduling using queue length and connection weight
Assignee: Toshiba Corp
•
Filing: 1996-07-08
•
Granted: 2001-07-17
•
Expires: 2016-07-08
Abstract
Abstract A packet scheduling scheme capable of realizing a fair scheduling regardless of weights of connections. A packet scheduler has a plurality of packet queues for temporarily storing entered packets, to each of which a weight is set up; a packet input unit for entering packets into the packet queues; a scheduling information management unit for managing scheduling information for specifying an order to read out packets stored in the packet queues, according to a queue length of each packet queue and the weight set up for each packet queue; and a packet output unit for reading out and outputting desired packets from the packet queues according to the scheduling information. In a case of fixed length packets, the scheduling information management unit always holds as many scheduling information corresponding to one packet queue as a smaller one the queue length of that one packet queue and the weight set for that one packet queue, so as to make a processing time required for scheduling constant regardless of a number of connections.
Inventors
- 👤 Yoshihiro Oba
- 👤 Tsuguhiro Hirose
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 13:17
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/5651; H04L2012/5678; H04L2012/5679
Claims Analysis
Total Claims: 50
Claim 1
Independent Claim
117 words
A packet scheduling apparatus, comprising: a plurality of packet queues for temporarily storing entered packets, to each of which a weight is set up; a packet input unit for entering the packets into at least one of said plurality of packet queues; a scheduling information management unit for managing scheduling information for specifying an order to read out the packets stored in said plurality of packet queues, according to a queue length of each of the packet queues and the weight set up for the each ofthe packet queues; and a packet output unit for reading out and outputting desired packets from said plurality queues according to the scheduling information managed by the scheduling information management unit.
Claim 2
Dependent Claim
117 words
A packet scheduling apparatus, comprising: a plurality of packet queues for temporarily storing entered packets, to each of which a weight is set up; a packet input unit for entering the packets into at least one of said plurality of packet queues; a scheduling information management unit for managing scheduling information for specifying an order to read out the packets stored in said plurality of packet queues, according to a queue length of each of the packet queues and the weight set up for the each ofthe packet queues; and a packet output unit for reading out and outputting desired packets from said plurality queues according to the scheduling information managed by the scheduling information management unit.
Claim 3
Dependent Claim
94 words
The apparatus of claim 1 , wherein the scheduling information management unit manages the scheduling information by using an evaluation value of said each of the packet queues such that a packet stored in one of the packet queues for which the evaluation value is smallest among said plurality of packet queues is to be sequentially read out, the evaluation value being sequentially updated in inverse proportion to a smaller one of the queue length of said each of the packet queues and the weight set up for said each of the packet queues.
Claim 4
Dependent Claim
30 words
The apparatus of claim 1 , wherein the scheduling information corresponding to said each of the packet queues is given by an identifier of said each of the packet queues.
Claim 5
Dependent Claim
34 words
The apparatus of claim 1 , wherein the scheduling information corresponding to each packet queue is given by an identifier of a virtual connection when said each packet queue corresponds to one virtual connection.
Claim 6
Dependent Claim
32 words
The apparatus of claim 1 , wherein the scheduling information corresponding to each packet queue is given by an identifier of a class when said each packet queue corresponds to one class.
Claim 7
Dependent Claim
33 words
The apparatus of claim 1 , wherein the scheduling information corresponding to each packet queue is given by a virtual path identifier (VPI) when said each packet queue corresponds to one virtual path.
Claim 8
Dependent Claim
36 words
The apparatus of claim 1 , wherein the scheduling information corresponding to each packet queue is given by a virtual path and virtual channel identifier (VPI/VCI) when said each packet queue corresponds to one virtual channel.
Claim 9
Dependent Claim
35 words
The apparatus of claim 1 , wherein the weight set up for each packet queue is given by a relative ratio of bandwidth set up for a VC connection corresponding to said each packet queue.
Claim 10
Dependent Claim
20 words
The apparatus of claim 1 , wherein the scheduling information management unit is formed by at least one FIFO queue.
Claim 11
Dependent Claim
21 words
The apparatus of claim 1 , wherein the scheduling information management unit is formed by at least one random out queue.
Claim 12
Dependent Claim
56 words
The apparatus of claim 1 , wherein packets entered by the packet input unit are fixed length packets, and the scheduling information management unit always holds as many scheduling information corresponding to one packet queue as a smaller one the queue length of said one packet queue and the weight set for said one packet queue.
Claim 13
Dependent Claim
54 words
The apparatus of claim 11 , wherein when a packet is entered into one packet queue, one scheduling information corresponding to said one packet queue is entered into the scheduling information management unit if the queue length of said one packet queue is not greater than the weight set for said one packet queue.
Claim 14
Dependent Claim
65 words
The apparatus of claim 11 , wherein when a packet is read out from one packet queue, one scheduling information corresponding to said one packet queue is taken out from the scheduling information management unit, and then entered into the scheduling information management again if the queue length of said one packet queue is not less than the weight set for said one packet queue.
Claim 15
Dependent Claim
109 words
The apparatus of claim 11 , wherein when a packet is read out from one packet queue, one scheduling information corresponding to said one packet queue is taken out from the scheduling information management unit, and then entered into the scheduling information means again if the queue length of said one packet queue is not less than a number of the scheduling information corresponding to said one packet queue managed in the scheduling information management means and the weight set for said one packet queue is also not less than said number of the scheduling information corresponding to said one packet queue managed in the scheduling information management unit.
Claim 16
Dependent Claim
53 words
The apparatus of claim 11 , wherein when the weight set for one packet queue is dynamically increased, a number of the scheduling information corresponding to said one packet queue managed in the scheduling information management unit is increased in proportion to an increase of the weight set for said one packet queue.
Claim 17
Dependent Claim
86 words
The apparatus of claim 11 , wherein the weight set for each packet queue takes a real number value, and the scheduling information management unit manages the scheduling information by using a variable for each packet queue which has an average value equal to the weight set up for each packet queue and whose integer part is equal to an integer part of the weight set up for each packet queue or an integer part of the weight set up for each packet queue plus one.
Claim 18
Dependent Claim
53 words
The apparatus of claim 16 , wherein when a packet is entered into one packet queue, one scheduling information corresponding to said one packet queue is entered into the scheduling information management unit if the queue length of said one packet queue is not greater than said variable for said one packet queue.
Claim 19
Dependent Claim
108 words
The apparatus of claim 16 , wherein when a packet is read out from one packet queue, one scheduling information corresponding to said one packet queue is taken out from the scheduling information management unit, and then entered into the scheduling information management again if the queue length of said one packet queue is not less than a number of the scheduling information corresponding to said one packet queue managed in the scheduling information management unit and said variable for said one packet queue is also not less than said number of the scheduling information corresponding to said one packet queue managed in the scheduling information management unit.
Claim 20
Dependent Claim
24 words
The apparatus of claim 1 , wherein the scheduling information management unit manages the scheduling information separately for different classes to which packets belong.
Claim 21
Dependent Claim
117 words
The apparatus of claim 19 , wherein the scheduling information management unit carries out a scheduling for classes by using a class by class weight set up for each class, and changes a value of the class by class weight set up for each class when the queue length of a packet queue corresponding to a connection contained in said each class changes from zero to a positive value at a time of entering a packet into one packet queue, and when the queue length of a packet queue corresponding to a connection contained in said each class changes from a positive value to zero at a time of reading out a packet from one packet queue.
Claim 22
Dependent Claim
99 words
The apparatus of claim 19 , wherein the scheduling information management unit manages the scheduling information by using a class by class evaluation value of each class, the class by class evaluation value being sequentially updated when the queue length of a packet queue corresponding to a connection contained in said each class changes from zero to a positive value at a time of entering a packet into one packet queue, and when a queue length of said each class changes from a positive value to zero at a time of reading out a packet from one packet queue.
Claim 23
Dependent Claim
25 words
The apparatus of claim 1 , wherein the scheduling information management means manages the scheduling information separately for different virtual paths to which packets belong.
Claim 24
Dependent Claim
122 words
The apparatus of claim 22 , wherein the scheduling information management unit carries out a scheduling for virtual paths by using a path by path weight set up for each virtual path, and changes a value of the path by path weight set up for each virtual path when the queue length of a packet queue corresponding to a connection contained in said each virtual path changes from zero to a positive value at a time of entering a packet into one packet queue, and when the queue length of a packet queue corresponding to a connection contained in said each virtual path changes from a positive value to zero at a time of reading out a packet from one packet queue.
Claim 25
Dependent Claim
102 words
The apparatus of claim 22 , wherein the scheduling information management unit manages the scheduling information by using a path by path evaluation value of each virtual path, the path by path evaluation value being sequentially updated when the queue length of a packet queue corresponding to a connection contained in said each virtual path changes from zero to a positive value at a time of entering a packet into one packet queue, and when a queue length of said each virtual path changes from a positive value to zero at a time of reading out a packet from one packet queue.
Claim 26
Independent Claim
118 words
A method of packet scheduling in a scheduler, comprising the steps of: entering packets into at least one of a plurality of packet queues of the scheduler for temporarily storing the packets, to each of which a weight is set up: reading out and outputting desired packets from said plurality of packet queues according to a scheduling information managing the scheduling information for specifying an order to read out the packets stored in said plurality of packet queues, according to a queue length of each of the packet queues and the weight set up for said each of the packet queues in response to entering and outputting of the packets at the entering step and the reading step.
Claim 27
Independent Claim
118 words
A method of packet scheduling in a scheduler, comprising the steps of: entering packets into at least one of a plurality of packet queues of the scheduler for temporarily storing the packets, to each of which a weight is set up: reading out and outputting desired packets from said plurality of packet queues according to a scheduling information managing the scheduling information for specifying an order to read out the packets stored in said plurality of packet queues, according to a queue length of each of the packet queues and the weight set up for said each of the packet queues in response to entering and outputting of the packets at the entering step and the reading step.
Claim 28
Dependent Claim
92 words
The method of claim 25 , wherein the managing step manages the scheduling information by using an evaluation value of said each of the packet queues such that a packet stored in one of the packet queues for which the evaluation value is smallest among said plurality of packet queues is to be sequentially read out, the evaluation value being sequentially updated in inverse proportion to a smaller one of the queue length of said each of the packet queues and the weight set up for said each of the packet queues.
Claim 29
Dependent Claim
25 words
The method of claim 25 , wherein the scheduling information corresponding to each packet queue is given by an identifier of said each packet queue.
Claim 30
Dependent Claim
34 words
The method of claim 25 , wherein the scheduling information corresponding to each packet queue is given by an identifier of a virtual connection when said each packet queue corresponds to one virtual connection.
Claim 31
Dependent Claim
32 words
The method of claim 25 , wherein the scheduling information corresponding to each packet queue is given by an identifier of a class when said each packet queue corresponds to one class.
Claim 32
Dependent Claim
38 words
The method of claim 25 , wherein the scheduling information corresponding to said each of the packet queues is given by a virtual path identifier (VPI) when said each of the packet queues corresponds to one virtual path.
Claim 33
Dependent Claim
36 words
The method of claim 25 , wherein the scheduling information corresponding to each packet queue is given by a virtual path and virtual channel identifier (VPI/VCI) when said each packet queue corresponds to one virtual channel.
Claim 34
Dependent Claim
35 words
The method of claim 25 , wherein the weight set up for each packet queue is given by a relative ratio of bandwidth set up for a VC connection corresponding to said each packet queue.
Claim 35
Dependent Claim
21 words
The method of claim 25 , wherein the managing step manages the scheduling information by using at least one FIFO queue.
Claim 36
Dependent Claim
22 words
The method of claim 25 , wherein the managing step manages the scheduling information by using at least one random out queue.
Claim 37
Dependent Claim
62 words
The method of claim 25 , wherein packets entered at the entering step are fixed length packets, and the managing step always holds as many scheduling information corresponding to one packet queue as a smaller one the queue length of said one packet queue and the weight set for said one packet queue, in a scheduling information management unit of the scheduler.
Claim 38
Dependent Claim
58 words
The method of claim 35 , wherein when a packet is entered into one packet queue, one scheduling information corresponding to said one packet queue is entered into the scheduling information management unit if the queue length of said one packet queue is not greater than the weight set for said one packet queue at the managing step.
Claim 39
Dependent Claim
70 words
The method of claim 35 , wherein when a packet is read out from one packet queue, one scheduling information corresponding to said one packet queue is taken out from the scheduling information management unit, and then entered into the scheduling information management unit again if the queue length of said one packet queue is not less than the weight set for said one packet queue at the managing step.
Claim 40
Dependent Claim
114 words
The method of claim 35 , wherein when a packet is read out from one packet queue, one scheduling information corresponding to said one packet queue is taken out from the scheduling information management unit, and then entered into the scheduling information management unit again if the queue length of said one packet queue is not less than a number of the scheduling information corresponding to said one packet queue managed in the scheduling information management unit and the weight set for said one packet queue is also not less than said number of the scheduling information corresponding to said one packet queue managed in the scheduling information management unit at the managing step.
Claim 41
Dependent Claim
57 words
The method of claim 35 , wherein when the weight set for one packet queue is dynamically increased, a number of the scheduling information corresponding to said one packet queue managed in the scheduling information management unit is increased in proportion to an increase of the weight set for said one packet queue at the managing step.
Claim 42
Dependent Claim
84 words
The method of claim 35 , wherein the weight set for each packet queue takes a real number value, and the managing step manages the scheduling information by using a variable for each packet queue which has an average value equal to the weight set up for each packet queue and whose integer part is equal to an integer part of the weight set up for each packet queue or an integer part of the weight set up for each packet queue plus one.
Claim 43
Dependent Claim
57 words
The method of claim 40 , wherein when a packet is entered into one packet queue, one scheduling information corresponding to said one packet queue is entered into the scheduling information management unit if the queue length of said one packet queue is not greater than said variable for said one packet queue at the managing step.
Claim 44
Dependent Claim
113 words
The method of claim 40 , wherein when a packet is read out from one packet queue, one scheduling information corresponding to said one packet queue is taken out from the scheduling information management unit, and then entered into the scheduling information management unit again if the queue length of said one packet queue is not less than a number of the scheduling information corresponding to said one packet queue managed in the scheduling information management unit and said variable for said one packet queue is also not less than said number of the scheduling information corresponding to said one packet queue managed in the scheduling information management unit at the managing step.
Claim 45
Dependent Claim
22 words
The method of claim 25 , wherein the managing step manages the scheduling information separately for different classes to which packets belong.
Claim 46
Dependent Claim
115 words
The method of claim 43 , wherein the managing step carries out a scheduling for classes by using a class by class weight set up for each class, and changes a value of the class by class weight set up for each class when the queue length of a packet queue corresponding to a connection contained in said each class changes from zero to a positive value at a time of entering a packet into one packet queue, and when the queue length of a packet queue corresponding to a connection contained in said each class changes from a positive value to zero at a time of reading out a packet from one packet queue.
Claim 47
Dependent Claim
97 words
The method of claim 43 , wherein the managing step manages the scheduling information by using a class by class evaluation value of each class, the class by class evaluation value being sequentially updated when the queue length of a packet queue corresponding to a connection contained in said each class changes from zero to a positive value at a time of entering a packet into one packet queue, and when a queue length of said each class changes from a positive value to zero at a time of reading out a packet from one packet queue.
Claim 48
Dependent Claim
23 words
The method of claim 25 , wherein the managing step manages the scheduling information separately for different virtual paths to which packets belong.
Claim 49
Dependent Claim
120 words
The method of claim 46 , wherein the managing step carries out a scheduling for virtual paths by using a path by path weight set up for each virtual path, and changes a value of the path by path weight set up for each virtual path when the queue length of a packet queue corresponding to a connection contained in said each virtual path changes from zero to a positive value at a time of entering a packet into one packet queue, and when the queue length of a packet queue corresponding to a connection contained in said each virtual path changes from a positive value to zero at a time of reading out a packet from one packet queue.
Claim 50
Dependent Claim
100 words
The method of claim 46 , wherein the managing step manages the scheduling information by using a path by path evaluation value of each virtual path, the path by path evaluation value being sequentially updated when the queue length of a packet queue corresponding to a connection contained in said each virtual path changes from zero to a positive value at a time of entering a packet into one packet queue, and when a queue length of said each virtual path changes from a positive value to zero at a time of reading out a packet from one packet queue.
References Cited (Backward Citations)
US5379297A
Cited
US5619502A
Cited
US5541912A
Cited
US5475679A
Cited
US5583864A
Cited
US5748614A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2004-07-16 | 2005-01-15 | 2005-07-17 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2008-07-16 | 2009-01-15 | 2009-07-17 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2012-07-16 | 2013-01-15 | 2013-07-17 | $7700.00 | Window Closed / Lapsed |