Patent US6122673A successfully refreshed from Google Patents.
US6122673A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Port scheduler and method for scheduling service providing guarantees, hierarchical rate limiting with/without overbooking capability
Assignee: Ericsson AB
•
Filing: 1998-07-22
•
Granted: 2000-09-19
•
Expires: 2018-07-22
Abstract
Abstract A scheduler for controlling when entities are operated upon by the server. The scheduler includes N entities, where N is an integer greater than or equal to 2. Each entity has a rate at which it is to receive service from the server. The scheduler includes a memory having finishing times fi of the N entities, where fi corresponds to the time the i'th entity is to be operated upon by the server. The scheduler includes a virtual clock that keeps track of virtual time so the finishing times fi can be identified. The scheduler includes a controller which chooses entities to be operated upon by the server as a function of the finishing times. The controller slows virtual time to provide service to the entities. The controller is connected to the virtual clock and the memory. A scheduler for controlling when entities are operated upon the server. The scheduler includes N entities, where N is an integer greater than or equal to 2. Each entity has a rate at which it is to receive service from the server. At least a first entity of the N entities has a plurality of connections, and the controller chooses the first entity to provide service when at least one of the plurality of connections is waiting for service and has a finishing time which is the earliest finishing time of the entities waiting for service.
Inventors
- 👤 Debashis Basak
- 👤 Fan Zhou
- 👤 Surya Pappu
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 19:05
CPC Classifications
H; H04; H04L; H04L12/00; H04L12/54; H04L12/56; H04L12/5601; H04L12/5602; H04Q; H04Q11/00; H04Q11/04; H04Q11/0428; H04Q11/0478; H04L2012/5678; H04L2012/5679
Claims Analysis
Total Claims: 23
Claim 1
Independent Claim
129 words
A scheduler for controlling when entities are operated upon by a server comprising: N entities, where N is an integer greater than or equal to 1, each entity having a rate at which it is to receive service from the server; a memory having finishing times f i of the N entities, where f i corresponds to the time the i'th entity is to be operated upon by the server; a virtual clock that keeps track of virtual time so the finishing times f i can be identified; and a controller which chooses entities to be operated upon by the server as a function of the finishing times, said controller slowing virtual time to provide service to the entities, said controller connected to the virtual clock and the memory.
Claim 2
Dependent Claim
129 words
A scheduler for controlling when entities are operated upon by a server comprising: N entities, where N is an integer greater than or equal to 1, each entity having a rate at which it is to receive service from the server; a memory having finishing times f i of the N entities, where f i corresponds to the time the i'th entity is to be operated upon by the server; a virtual clock that keeps track of virtual time so the finishing times f i can be identified; and a controller which chooses entities to be operated upon by the server as a function of the finishing times, said controller slowing virtual time to provide service to the entities, said controller connected to the virtual clock and the memory.
Claim 3
Dependent Claim
33 words
A scheduler as described in claim 1 wherein each entity has a rate for requesting service from the server, with the sum of rates of said entities able to be greater than 1.
Claim 4
Dependent Claim
32 words
A scheduler as described in claim 2 wherein the controller causes virtual time to stop until all entities having a finishing time equal to virtual time have received service from the server.
Claim 5
Dependent Claim
34 words
A scheduler as described in claim 3 wherein the controller provides service to each entity as a function of each entity's rate and the amount the sum of the rates is greater than 1.
Claim 6
Dependent Claim
30 words
A scheduler as described in claim 4 wherein the controller operates virtual time corresponding to V(t+1)=min(V(t)+1, minF), where minF denotes the earliest finish time among all entities having finishing times.
Claim 7
Dependent Claim
57 words
A scheduler as described in claim 5 wherein the memory has starting times s i of the N entities, where 1≦i<N and is an integer, and s i corresponds to the earliest time when the i'th entity can request next service from the server and the memory has rate limit times TI i of the N entities.
Claim 8
Dependent Claim
20 words
A scheduler as described in claim 6 wherein the controller provides service to the entity with the earliest finishing time.
Claim 9
Dependent Claim
107 words
A scheduler as described in claim 7 wherein there is a hierarchy of controllers such that at least a first entity of the N entities represents a plurality of entities in a controller in a second tier, and a second entity in the second tier represents entities in a controller in a third tier wherein a connection requiring service storing a time interval and start time in a memory associated with the controller to which the connection first connects in the scheduler, a controller connected to a lower level controller stores a time interval, start time, in the memory associated with the controller at the lower tier.
Claim 10
Dependent Claim
104 words
A hierarchical scheduler as described in claim 8 wherein the controller at the first tier chooses a first entity to provide service when the entity is eligible and has earliest finish time of entities waiting for service, updating the start and finish time of the entity in its local memory; the first entity including another controller in the next tier, the other controller further chooses a second entity to provide service when the second entity is eligible and has earliest finish time of entities waiting for service at the second controller, updating the start and finish time of the entity in its local memory.
Claim 11
Dependent Claim
47 words
A hierarchical scheduler as described in claim 9 wherein each controller maintains a virtual clock independent of all other virtual clocks of other controllers of different tier or the same tier with all virtual clocks being updated based on finish times of eligible entities connected to it.
Claim 12
Dependent Claim
54 words
A hierarchical scheduler as described in claim 10 wherein all virtual clocks are incremented each cycle time, the minimum operation being performed on a virtual clock, to obtain the correct value of the clock, when its controller receives service, allowing the controller to use the correct value of the clock in a next level.
Claim 13
Dependent Claim
44 words
A hierarchical scheduler as described in claim 9 wherein the sum of rates of entities at a controller can be greater than 1, thus allowing the scheduler to be overbooked, and during congestion the controller ensures slowdown of virtual clock to reflect overbooking behavior.
Claim 14
Dependent Claim
54 words
A hierarchical scheduler as described in claim 12 wherein the rate received by an entity with no overbooking is equal to its rate but with overbooking the rate received by an entity is the minimum of its rate or its rate scaled down by the sum of rates of eligible entities at the controller.
Claim 15
Dependent Claim
37 words
A scheduler as described in claim 13 wherein at least one of the entities is guaranteed service from the server when it has a finishing time with the earliest finishing time of the entities waiting for service.
Claim 16
Dependent Claim
52 words
A scheduler as described in claim 14 wherein the entity which is guaranteed service is reviewed first by the controller when the controller is determining which entity is to receive service next to identify if the entity which is guaranteed service has the earliest finishing time of the entities waiting for service.
Claim 17
Dependent Claim
182 words
A scheduler for controlling when entities are operated upon the server comprising: N entities, where N is an integer greater than or equal to 1, each entity having a rate at which it is to receive service from the server, at least a first entity of the N entities has a plurality of connections, and the controller chooses the first entity to provide service when at least one of the plurality of connections is waiting for service and has a finishing time which is the earliest finishing time of the entities waiting for service; a memory having finishing times f i of the N entities, where f i corresponds to the time the i'th entity is to be operated upon by the server; a virtual clock that keeps track of virtual time so the finishing times f i can be identified; and a controller which chooses entities to be operated upon by the server as a function of the finishing times, said controller slowing virtual time to provide service to the entities, said controller connected to the virtual clock and the memory.
Claim 18
Dependent Claim
182 words
A scheduler for controlling when entities are operated upon the server comprising: N entities, where N is an integer greater than or equal to 1, each entity having a rate at which it is to receive service from the server, at least a first entity of the N entities has a plurality of connections, and the controller chooses the first entity to provide service when at least one of the plurality of connections is waiting for service and has a finishing time which is the earliest finishing time of the entities waiting for service; a memory having finishing times f i of the N entities, where f i corresponds to the time the i'th entity is to be operated upon by the server; a virtual clock that keeps track of virtual time so the finishing times f i can be identified; and a controller which chooses entities to be operated upon by the server as a function of the finishing times, said controller slowing virtual time to provide service to the entities, said controller connected to the virtual clock and the memory.
Claim 19
Independent Claim
91 words
A method for scheduling service from a server comprising the steps of: receiving a first request from a first entity having a first rate for service from the server; storing a finishing time in a memory when the first entity is to receive service from the first entity; receiving a second request from a second entity having a second rate for service from the server; providing service to the first entity; stopping virtual time if second entity's finishing time is equal to virtual time; and providing service to the second entity.
Claim 20
Independent Claim
91 words
A method for scheduling service from a server comprising the steps of: receiving a first request from a first entity having a first rate for service from the server; storing a finishing time in a memory when the first entity is to receive service from the first entity; receiving a second request from a second entity having a second rate for service from the server; providing service to the first entity; stopping virtual time if second entity's finishing time is equal to virtual time; and providing service to the second entity.
Claim 21
Dependent Claim
19 words
A method as described in claim 17 wherein the sum of rates of the entities is greater than 1.
Claim 22
Dependent Claim
43 words
A method as described in claim 14 wherein the step of providing service to the first entity includes the step of providing service to a first connection of the first entity and then providing service to a second connection of the first entity.
Claim 23
Dependent Claim
43 words
A method as described in claim 16 wherein before the step of providing service to the first entity, there is the step of determining whether the first entity has a finishing time which is the earliest finishing time of entities with finishing times.
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) | 2003-09-19 | 2004-03-20 | 2004-09-19 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-09-19 | 2008-03-20 | 2008-09-19 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-09-19 | 2012-03-20 | 2012-09-19 | $7700.00 | Window Closed / Lapsed |