Method and a scheduler for controlling when a server provides service to an entity

Claim 2

A scheduler for controlling when N entities, where N is an integer ≧2, are operated upon by a server, each entity having a rate at which it is to receive service from the server, at least two entities having different rates, all rates of the entities total <1, comprising: a starting time memory having arrival times s i of the N entities, where 1<i<N and is an integer, and s i corresponds to the time the i'th entity first requests service from the server; a finishing time 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 time so the arrival times s i and finishing times f i can be identified; and a controller which chooses entities to be operated upon by the server in the order of the entities with an earliest finishing time f i and an arrival time s i being operated upon first, and then the entities with the earliest or latest starting time s i or having the highest or lowest id or rate if their finishing times are the same being operated upon next at each given time, with entities able to be operated upon by the server before their finishing time f i , said controller causing the virtual clock to increment virtual time to the earliest start time of an entity if the earliest start time of an entity is later than virtual time, otherwise the controller causes the virtual clock to increment virtual time by a unit of virtual time.

Claim 3

An apparatus as described in claim 1 wherein the controller provides service to the entities from the server sequentially.

Claim 4

An apparatus as described in claim 1 wherein the controller causes the virtual clock to move present virtual time forward when an entity receives service from the server.

Claim 5

An apparatus as described in claim 3 wherein the starting time memory is a starting time priority queue and the finish time memory is a finishing time priority queue.

Claim 6

A scheduler as described in claim 4 including an element pool which is connected with the N entities and receives elements from the N entities to be operated upon by the server, and wherein the arrival times s i of elements corresponds to the time an element from the i'th entity arrives in the element pool and the finishing times f i compared to the time an element from the i'th entity is to leave the element pool and be operated upon by the server and the controller transfers elements to the server from the element pool.

Claim 7

An apparatus as described in claim 5 wherein the controller is connected to the virtual clock, the element pool, the starting time memory and the finishing time memory for controlling time of the virtual clock, storing the elements in the element pool and their arrival times s i and their finishing times f i in the starting time priority queue and the finishing time priority queue, respectively.

Claim 8

An apparatus as described in claim 6 wherein the controller transfers the element out of the element pool which has the earliest finishing time f i and a starting time s i , unless there is more than one element with the earliest finishing time f i in which case the element with the earliest starting time s i is transferred out of the element pool by the controller and before its finishing time f i .

Claim 11

A method as described in claim 8 including after the providing step, there is the step of repeating the providing step in regard to other entities who have requested service from the server.

Claim 12

A scheduler for controlling when N entities, where N is an integer ≧1, are operated upon by a server comprising: a starting time memory having starting times s i of the N entities, where 1<i<N and is an integer, and s i corresponds to the time the i'th entity first requests to be operated upon by the server; a finishing time memory having finishing times f i of the N entities, where f i corresponds to the time the i'th entity is to have been operated upon by the server; a virtual clock that keeps track of time so present virtual time, arrival times s i and finishing times f i can be identified; and a controller which chooses entities to be operated upon by the server in the order of the entity with an earliest finishing time f i and a starting time s i being operated upon first, and then the entities based on a predetermined criteria, said controller causing the virtual clock to increment virtual time to the earliest starting time of an entity if the earliest starting time of an entity is later than virtual time, otherwise, the controller causing the virtual clock to increment present virtual time by a unit of virtual time, said controller causing the virtual clock to increment virtual time to the earliest start time of an entity if the earliest start time of an entity is later than virtual time, otherwise the controller causes the virtual clock to increment virtual time by a unit of virtual time.

Claim 13

A scheduler for controlling when N entities, where N is an integer ≧1, are operated upon by a server comprising: a starting time memory having starting times s i of the N entities, where 1<i<N and is an integer, and s i corresponds to the time the i'th entity first requests to be operated upon by the server; a finishing time memory having finishing times f i of the N entities, where f i corresponds to the time the i'th entity is to have been operated upon by the server; a virtual clock that keeps track of time so present virtual time, arrival times s i and finishing times f i can be identified; and a controller which chooses entities to be operated upon by the server in the order of the entity with an earliest finishing time f i and a starting time s i being operated upon first, and then the entities based on a predetermined criteria, said controller causing the virtual clock to increment virtual time to the earliest starting time of an entity if the earliest starting time of an entity is later than virtual time, otherwise, the controller causing the virtual clock to increment present virtual time by a unit of virtual time, said controller causing the virtual clock to increment virtual time to the earliest start time of an entity if the earliest start time of an entity is later than virtual time, otherwise the controller causes the virtual clock to increment virtual time by a unit of virtual time.

Claim 14

A scheduler for scheduling when N entities each of which has a weight w, where N is an integer ≧1 and w is a real number, are served by a server comprising: a starting time memory having starting times s i when the N entities request service, where 1>i≧N and is an integer, and s i is the time at which the i'th entity may next get service from the server; a finishing time memory having finishing times f i when the N entities should be serviced, where f i is the time by which the i'th entity should be serviced by the server; a virtual clock that keeps track of time V k where k≧0 and is an integer and V.sub.k =MAX((V.sub.k-1 +P)+(1*X)+((1/AW)*T), (s.sub.Smin *Y)+((f.sub.Fmin -s.sub.Smin)*Z)) wherein (|P|+|T"+|X|)*(|Y.vertline.+|Z|)>0 where S Smin is the earliest start time s i of when an entity requests service from the server, f Fmin is the earliest finish time of an entity waiting for service from the server, V k-i is the virtual time when the server last served an entity, AW=sum over all entities currently asking for service of w i , where w i is the i'th entity's weight, and P, X, T, Y and Z are real numbers; and a controller which chooses which entity is to be operated upon by the server in the order of the entity with an earliest finishing time f i and a start time s i receiving service first, and then the entities based on a predetermined criteria, said controller causing the virtual clock to increment virtual time to the earliest start time of an entity if the earliest start time of an entity is later than virtual time otherwise the controller causes the virtual clock to increment virtual time by a unit of virtual time.

Claim 15

A scheduler for scheduling when N entities each of which has a weight w, where N is an integer ≧1 and w is a real number, are served by a server comprising: a starting time memory having starting times s i when the N entities request service, where 1>i≧N and is an integer, and s i is the time at which the i'th entity may next get service from the server; a finishing time memory having finishing times f i when the N entities should be serviced, where f i is the time by which the i'th entity should be serviced by the server; a virtual clock that keeps track of time V k where k≧0 and is an integer and V.sub.k =MAX((V.sub.k-1 +P)+(1*X)+((1/AW)*T), (s.sub.Smin *Y)+((f.sub.Fmin -s.sub.Smin)*Z)) wherein (|P|+|T"+|X|)*(|Y.vertline.+|Z|)>0 where S Smin is the earliest start time s i of when an entity requests service from the server, f Fmin is the earliest finish time of an entity waiting for service from the server, V k-i is the virtual time when the server last served an entity, AW=sum over all entities currently asking for service of w i , where w i is the i'th entity's weight, and P, X, T, Y and Z are real numbers; and a controller which chooses which entity is to be operated upon by the server in the order of the entity with an earliest finishing time f i and a start time s i receiving service first, and then the entities based on a predetermined criteria, said controller causing the virtual clock to increment virtual time to the earliest start time of an entity if the earliest start time of an entity is later than virtual time otherwise the controller causes the virtual clock to increment virtual time by a unit of virtual time.

Claim 18

A method as described in claim 12 wherein the identifying step includes the step of identifying when the first entity first requests service from the server.

Claim 19

A scheduler for controlling when a server provides service to entities comprising: a memory having times which are a function of when entities request service from the server; a virtual clock that keeps track of time as a function of when entities request service from the server; and a controller which causes an entity to receive service from the server as a function of when the entity requests service from the server, said controller causing the virtual clock to increment virtual time to the earliest start time of an entity if the earliest start time of an entity is later than virtual time, otherwise the controller causes the virtual clock to increment virtual time by a unit of virtual time.

Claim 20

A scheduler for controlling when a server provides service to entities comprising: a memory having times which are a function of when entities request service from the server; a virtual clock that keeps track of time as a function of when entities request service from the server; and a controller which causes an entity to receive service from the server as a function of when the entity requests service from the server, said controller causing the virtual clock to increment virtual time to the earliest start time of an entity if the earliest start time of an entity is later than virtual time, otherwise the controller causes the virtual clock to increment virtual time by a unit of virtual time.

Claim 27

A scheduler as described in claim 1 wherein said controller chooses an element to be operated upon by the server such that said element is to be operated upon by the server at the same virtual time.

Claim 28

A method as described in claim 8 wherein the providing step includes the step of transferring an element of N elements at a same virtual time out of the first location.

Claim 29

A scheduler as described in claim 1 wherein the virtual clock keeps track of virtual time so each request for service from the server by an entity is schedulable and each entity will receive service from the server.