Method and apparatus for providing service to entities

The present invention is related to a telecommunications system. More specifically, the present invention is related to a scheduler for a telecommunications system which dynamically allocates bandwidth to entities requesting service from a server of the telecommunications system.

In most asynchronous based networks, there are times when service from a server, such as a router or a switch or a CPU, must be allocated to more than one entity, such as a port, requesting service from the server. This is because at such times, more than one entity is requesting service of the server. Heretofore, a common technique to deal with such demands of a server is to establish rigid predefined allocations to entities demanding service, regardless of how much service they are actually demanding over time. The present invention allows the allocation of service to entities demanding service to be dynamically changed to take advantage of the available bandwidth of a network at any given time.

The present invention pertains to an apparatus for providing service to entities. The apparatus comprises a server for providing service. The apparatus comprises a first entity which requires the service of the server. The first entity is connected with the server. The apparatus comprises a second entity which requires the service of the server. The second entity is connected with the server. Also, the apparatus comprises a scheduler for dynamically scheduling when the first and second entity receives service from the server.

The present invention pertains to a scheduler for controlling when N entities, where N is an integer greater than or equal to 1, are operated upon by a server. The scheduler comprises a controller which chooses entities to receive service by the server based on a weighting factor corresponding with an entity. The controller dynamically changes the weighting factor corresponding with the entity as a function of a desired condition and time. The scheduler comprises a communication mechanism for communicating with entities. The communication mechanism is connected to the controller.

The present invention pertains to a method for serving entities. The method comprises the steps of providing service to a first entity by a server at a first rate based on a first weighting factor corresponding to the first entity during a first time period. Next there is the step of providing service to a second entity by the server at a second rate based on a second weighting factor corresponding to the second entity during the first time period. Then there is the step of changing the first weighting factor and second weighting factor dynamically to a third weighting factor and a fourth weighting factor, respectively, corresponding to the first entity and second entity, respectively. Next there is the step of providing service to the first entity by the server at a third rate based on the third weighting factor corresponding to the first entity during a second time period. Then there is the step of providing service to the second entity by the server at a fourth rate based on the fourth weighting factor corresponding to the second entity during the second time period.

In the accompanying drawings, the preferred embodiment of the invention and preferred methods of practicing the invention are illustrated in which:

FIG. 1 is a schematic representation of an apparatus of the present invention.

FIG. 2 is a schematic representation of a graph showing bandwidth allocation regarding the invention.

FIG. 3 is a schematic representation of an ATM network.

Referring now to the drawings wherein like reference numerals refer to similar or identical parts throughout the several views, and more specifically to FIG. 1 thereof, there is shown an apparatus 10 for providing service to entities 12 . The apparatus 10 comprises a server 14 for providing service. The apparatus 10 comprises a first entity 12 a which requires the service of the server 14 . The first entity 12 a is connected with the server 14 . The apparatus 10 comprises a second entity 12 b which requires the service of the server 14 . The second entity 12 b is connected with the server 14 . Also, the apparatus 10 comprises a scheduler 17 for dynamically scheduling when the first and second entity 12 b receives service from the server 14 .

Preferably, the scheduler 17 provides the first service to the first entity 12 a at a first rate during a first time period based on a first weighting factor of the first entity 12 a and provides service to the second entity 12 b at a second rate during the first time period based on a second weighting factor of the second entity 12 b . The scheduler 17 changes the first weighting factor to a third weighting factor and the second weighting factor to a fourth weighting factor to correspond with a desired condition so the first entity 12 a receives service from the server 14 during a second time period based on the third weighting factor of the first entity 12 a and the second entity 12 b receives service from the server 14 during the second time period based on a fourth weighting factor corresponding to the second entity 12 b . The third rate and fourth rate are different from the first rate and the second rate, respectively, and the first time period is different from the second time period.

Preferably, the schedule changes the first weighting factor and the second weighting factor to the third weighting factor and the fourth weighting factor to correspond with the desired condition according to

W i =FS +α×( Ri−FS )  (1)

where W i is the ith weighting factor and i is an integer greater than 2, FS = 1 MAX  ( 2 , #  N + 1 )

where N is the number of entities requesting service, α<1 where α is a constant and Ri is the measured rate of the ith entity at the first time.

The present invention pertains to a scheduler for controlling when N entities 12 , where N is an integer greater than or equal to 1, are operated upon by a server 14 . The scheduler comprises a controller 16 which chooses entities 12 to receive service by the server 14 based on a weighting factor corresponding with an entity. The controller 16 dynamically changes the weighting factor corresponding with the entity as a function of a desired condition and time. The scheduler comprises a communication mechanism 18 for communicating with entities 12 . The communication mechanism 18 is connected to the controller 16 .

The present invention pertains to a method for serving entities 12 . The method comprises the steps of providing service to a first entity 12 a by a server 14 at a first rate based on a first weighting factor corresponding to the first entity 12 a during a first time period. Next there is the step of providing service to a second entity 12 b by the server 14 at a second rate based on a second weighting factor corresponding to the second entity 12 b during the first time period. Then there is the step of changing the first weighting factor and second weighting factor dynamically to a third weighting factor and a fourth weighting factor, respectively, corresponding to the first entity 12 a and second entity 12 b , respectively. Next there is the step of providing service to the first entity 12 a by the server 14 at a third rate based on the third weighting factor corresponding to the first entity 12 a during a second time period. Then there is the step of providing service to the second entity 12 b by the server 14 at a fourth rate based on the fourth weighting factor corresponding to the second entity 12 b during the second time period.

In the operation of the preferred embodiment, and by way of an example with reference to FIG. 2, the scheduler receives a request from a first entity A at time T 0 for service from the server 14 . First entity A has a transmission rate (TR) of 0.8. Applying Equation (1) to determine allocation rate (AR), where α=0.9 and FS=0.5, since there is only one entity requesting service at time, T 0 yields the following:

Substituting

0.9(0.8−0.5)+0.5=0.77

Thus, and referring to FIG. 2, at time T 1 , the available bandwidth of the system has gone from 100% at time T 0 when the request by the first entity A was initially made, to 23% at time T 1 when the first entity A is receiving service; the allocation rate (AR) of the first entity A goes from 0 at time T 0 to 77% at time T 1 with a measured rate (MR) out to a port of a connection from the server 14 and the AR being 0.8 at time T 1 from 0.2 at time T 0 .

At time T 1 where the system has had time to stabilize in regard to the request by the first entity A, a second entity B having a transmission rate of 0.2, also requests service from the server 14 . Now at time T 1 , FS=0.33 since there are two entities requesting service (FS=1/3). For the second entity B the equation at time T 1 yields the following

0.9(0.2−0.33)+0.33=−0.117+0.33=0.213=AR;

And for the first entity A

0.9(0.8−0.33)+0.33=0.9(0.47)+0.33=0.423+0.33=0.753=AR.

From time T 1 the server 14 provides the respective AR to each of the entities, as depicted in FIG 2 , until some change occurs to the system. This is a simple example, but it shows the power of Equation (1) in regard to dynamically change the bandwidth available to entities over time, whether there are one, two or thousands of entities.

As is apparent, the scheduler having the algorithm in it is as either software or firm ware only concerns itself with the demands placed on it, not with what is occurring at other parts of the network or connection. If a comparison when more entities require service, then the scheduler can adapt the available bandwidth to accommodate the demands of the entities. Similarly, if at a given time fewer entities need service, then greater bandwidth can be made available to entities requesting service which has been freed by the entities which no longer need service at a given time.

One possible application of the algorithm is with ATM. As shown in FIG. 3, four sources A 1 , B 1 , C 1 and D 1 connected to a switch S 1 are transmitting ATM cells on an ATM network. The bandwidth of the network to a second switch S 2 is allocated according to Equation (1) and according to a fair queue, as described in U.S. patent application 08/476,365, incorporated by reference herein now Pat. No. 5,828,878. The second switch S 2 receives additional demand from source E 1 , but provides the respective ATM cells to the respective destinations B 2 , C 2 and D 2 of source B 1 , C 1 and D 1 , respectively. According to the Equation (1) and the fair queue, the bandwidth of the network to a third switch S 3 from the second switch S 2 is allocated. The destinations A 2 and E 2 from sources A 1 and E 1 , respectively, which are connected to the third switch S 3 , receive the respective ATM cells. If at any time one or more of the sources are not requiring service, there allocation can be provided to the other sources to allow the other sources to receive more service at a given time. The pseudo-code for the algorithm can be found in the Appendix.

Although the invention has been described in detail in the foregoing embodiments for the purpose of illustration, it is to be understood that such detail is solely for that purpose and that variations can be made therein by those skilled in the art without departing from the spirit and scope of the invention except as it may be described by the following claims.