Port scheduler and method for scheduling service providing guarantees, hierarchical rate limiting with/without overbooking capability

• US 6,122,673 A
• Filed: 07/22/1998
• Issued: 09/19/2000
• Est. Priority Date: 07/22/1998
• Status: Expired due to Term

• Current Assignee: Ericsson AB (Telefonaktiebolaget LM Ericsson)
• Original Assignee: FORE Systems, Inc. (Cornhill Corp. Holdings LLP)
• Inventors: Pappu, Surya, Zhou, Fan, Basak, Debashis
• Primary Examiner(s): VU, VIET DUY
• Application Number:
  US09/120,697
• Time in Patent Office: 790 Days
• Field of Search: 709/223, 709/225, 709/226, 709/238, 709/102, 709/104, 709/105, 370/395, 370/412, 370/428, 370/429
• US Class Current: 709/238
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

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 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. The scheduler includes a virtual clock that keeps track of virtual time so the finishing times f_i 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.

Claims

1. 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.

2. 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.

3. 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.

4. 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.

5. A scheduler as described in claim 4 wherein the controller operates virtual time corresponding to

6. 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.

7. A scheduler as described in claim 6 wherein the controller provides service to the entity with the earliest finishing time.

8. 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.

9. 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.

10. 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.

11. 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.

12. 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.

13. 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.

14. 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.

15. 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.

19. 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.

16. 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.

20. 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.

17. 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.

18. A method as described in claim 17 wherein the sum of rates of the entities is greater than 1.