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

摘要

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. 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 method for scheduling service from a server. The method includes the steps of receiving a first request from a first entity having a first rate for service from the server. Next there is the step of storing a finishing time in a memory when the first entity is to receive service from the first entity. Then there is the step of receiving a second request from a second entity having a second rate for service from the server. Next there is the step of storing the finishing time when the second entity is to receive service from the server in the memory. The finishing time of the second entity is the same finishing time as the first entity. Then there is the step of providing service to the first entity. Next there is the step of stopping virtual time. Then there is the step of providing service to the second entity from the server at the same virtual time that the first entity receives service from the server. <IMAGE>