Abstract:
There is disclosed a scheduler, and a method, for scheduling a plurality of input flows to an output flow, comprising: means for allocating to each input flow a flow level and a threshold value, the flow level being indicative of the number of bits to be scheduled from the input flow, wherein the value of the flow level relative to the threshold value indicates whether the current scheduling of that input flow is sufficient to meet a necessary throughput for that input flow; means for increasing the value of each flow level by a predetermined amount; and means for selecting the input flow to be scheduled in dependence on the flow having a highest priority of those flows having a flow level greater than the respective threshold level, wherein there is further included means for, if no input flows have a flow level above the respective threshold level, increasing the flow level for each input flow having data to transmit by a second predetermined value.

Description:
FIELD OF THE INVENTION  
         [0001]    The present invention relates to the scheduling of traffic channel flows, and particularly but not exclusively to radio resource scheduling in mobile communication systems. An example of such a mobile communication system is enhanced general packet radio service (EGPRS).  
         BACKGROUND TO THE INVENTION  
         [0002]    In mobile radio communication systems, such as the enhanced general packet radio service (EGPRS) there is a requirement for radio resource scheduling in the packet data traffic channel. Established algorithms for radio resource scheduling in EGPRS include weighted round-robin (WRR) and deficient round-robin (DRR).  
           [0003]    Any radio resource scheduling must fulfill various requirements to be compatible with traffic flow specifications defined by the mobile communication system. In most cases, different traffic classes are specified with four parameters: priority; throughput; average delay; and delay jitter (variation of delay).  
           [0004]    Wireless communication channels, such as in EGPRS, offer limitations that must be taken into account in designing the system. Examples of limitations are fast capacity variations due to bit errors, different coding schemes, or multi-slot capability. The radio resource use for signalling must always pre-empt a data transfer. Long pauses in the data transfer may be caused during cell reselections. Unnecessary re-transmissions need to be avoided. Fixed transmission turns for data may be necessary due to polling requirements.  
           [0005]    In general, all these limitations increase the network generated burstiness of the data flow. A scheduler which handles the scheduling of traffic channels should ideally try to provide a predictable service to the various data flows. However this is difficult due to network throughput and delay variation, and burstiness.  
           [0006]    If the traffic is already bursty on arrival, and the burstiness is generated by the EGPRS core network, then ideally the scheduler may attempt to smooth the traffic to some extent. This is especially important with TCP/IP (transmission control protocol/internet protocol), because maximum throughput is achieved only when the windowing in the TCP works optimally, which requires nearly constant service in terms of throughput and delay.  
           [0007]    In addition, most network protocols have an implicit minimum throughput requirement that must be provided by the network in order to make the protocol work. Thus, the scheduler should ideally provide guaranteed throughput for all traffic flows. This guarantee can in practice be very small, near to the minimum limit. If the connection cannot be provided with service that is good enough for the protocol to work, then the connection is not useful to consume resources for signalling the connection open, because it would be dropped.  
           [0008]    WO 01/24428 discloses hierarchical prioritised round-robin scheduling technique. Token bucket rate classifiers are used to mark each individual packet as conforming or not conforming to a traffic specification for the flow.  
           [0009]    It is an object of the present invention to provide an improved technique for scheduling channels, which addresses one or all of the above-identified problems.  
         SUMMARY OF THE INVENTION  
         [0010]    According to one embodiment of the present invention there is provided a method of scheduling a plurality of input flows to an output flow comprising: allocating a flow level to each input flow, the flow level indicating whether the current scheduling of that input flow is sufficient to meet a necessary throughput for that input flow; and scheduling an input flow for which the respective flow level indicates a throughput of less than the necessary throughput.  
           [0011]    The method may further comprise the step of determining if an input flow has data to be transmitted; and scheduling only those input flows having data to be transmitted.  
           [0012]    The output flow may be divided into time-slots, the method further comprising: determining the time-slot of an input flow; and scheduling those input flows having data to be transmitted in the current output flow time-slot.  
           [0013]    The input flows may be associated with a predetermined sequence, such that if more than one input flow has a respective flow level indicating a throughput less than a necessary throughput, each such input flow is scheduled in sequence.  
           [0014]    A scheduled input flow may be moved to the end of the sequence.  
           [0015]    The method may further comprise the step of allocating a priority to each input flow; the step of scheduling an input flow being further dependent on the priority allocated to an input flow.  
           [0016]    The method may further comprise the step of allocating a priority to each input flow, wherein a scheduled input flow is moved to the end of the sequence of flows having the same priority.  
           [0017]    An input flow may have the highest priority is scheduled ahead of any other input flow.  
           [0018]    If more than one input flow has the same priority, the input flows are scheduled in sequence.  
           [0019]    The step of allocating a flow level to each input flow may include allocating a threshold value for each input flow, the threshold value being set such that the flow level exceeding the threshold value indicates that the necessary throughput is not being met. The threshold value may be zero.  
           [0020]    In an initial step the scheduling may comprise increasing the flow level of each input flow by a respective predetermined amount.  
           [0021]    If the flow level of all input flows indicates that the current throughput is more than the required guaranteed throughput for the respective input flow, the flow level for each input flow may be increased by a respective predetermined amount.  
           [0022]    The flow level for each input flow may be associated with a maximum flow level, wherein the flow level is not allowed to exceed the maximum flow level.  
           [0023]    The method may further comprise the step of, responsive to the scheduling of an input flow, decreasing the flow level associated with that input flow.  
           [0024]    The flow level may be decreased by an amount corresponding to the number of bits scheduled.  
           [0025]    The flow level for each input flow may be associated with a minimum flow level, wherein the flow level is not allowed to exceed the minimum flow level.  
           [0026]    According to the present invention there is also provided a method of scheduling a plurality of input flows to an output flow, comprising: allocating to each input flow a flow level and a threshold value, the flow level being indicative of the number of bits to be scheduled from the input flow, wherein the value of the flow level relative to the threshold value indicates whether the current scheduling of that input flow is sufficient to meet a necessary throughput for that input flow; determining if the flow level of an input flow is above its respective threshold value, and if the flow level is above its respective threshold value, scheduling that input flow, and reducing the flow level for that input flow by an amount corresponding to the number of bits scheduled.  
           [0027]    In an initial step the flow level for each input flow may be increased by a first predetermined value.  
           [0028]    The method may further include the step of determining a priority for each input flow, wherein if a plurality of input flows have a flow value above their respective threshold value the one having the highest priority is scheduled.  
           [0029]    A scheduled input flow may be moved to the end of the sequence.  
           [0030]    A method may further comprise the step of allocating a priority to each input flow, wherein a scheduled input flow is moved to the end of the sequence of flows having the same priority.  
           [0031]    An input flow may be scheduled further in dependence on the input flow being permitted to transmit data.  
           [0032]    If no input flow has a flow level above its threshold level, the flow level for each input flow may be increased by a second predetermine amount.  
           [0033]    According to a further aspect of the present invention there is provided a method of scheduling a plurality of input flows to an output flow, comprising: allocating to each input flow a flow level and a threshold value, the flow level being indicative of the number of bits to be scheduled from the input flow, wherein the value of the flow level relative to the threshold value indicates whether the current scheduling of that input flow is sufficient to meet a necessary throughput for that input flow; increasing the value of each flow level by a predetermined amount; and selecting the input flow to be scheduled in dependence on the flow having a highest priority of those flows having a flow level greater than the respective threshold level, wherein if no input flows have a flow level above the respective threshold level, the flow level for each input flow having data to transmit is increased by a second predetermined value.  
           [0034]    The present invention still further provides a scheduler for scheduling a plurality of input flows to an output flow comprising: means for allocating a flow level to each input flow, the flow level indicating whether the current scheduling of that input flow is sufficient to meet a necessary throughput for that input flow; and means for scheduling an input flow for which the respective flow level indicates a throughput of less than the necessary throughput.  
           [0035]    The scheduler may further comprise means for determining if an input flow has data to be transmitted; wherein the scheduling means is adapted to schedule only those input flows having data to be transmitted.  
           [0036]    The input flows may be associated with a predetermined sequence, the scheduling means being adapted such that if more than one input flow has a respective flow level indicating a throughput of less than a necessary throughput, each such input flow is scheduled in sequence.  
           [0037]    A scheduled input flow may be moved to the end of the sequence.  
           [0038]    A priority may be associated with each input flow; the scheduler being adapted to schedule an input flow in dependence on the priority allocated to an input flow.  
           [0039]    The scheduler may further be adapted to allocate a priority to each input flow, wherein a scheduled input flow is moved to the end of the sequence of flows having the same priority.  
           [0040]    The means for allocating a flow level to each input flow may include means for allocating a threshold value for each input flow, the threshold value being set such that if the flow level exceeds the threshold value the necessary throughput is not being met.  
           [0041]    The scheduling means may increase the flow level of each input flow by a respective predetermined amount prior to scheduling.  
           [0042]    The scheduler may further include means for increasing the flow level for each input flow by a second predetermined amount if the flow level of all input flows indicates that the current throughput is more than the required guaranteed throughput for the respective input flow.  
           [0043]    The scheduler may further include means, responsive to the scheduling of an input flow, for decreasing the flow level associated with that input flow.  
           [0044]    According to a further aspect the invention provides a scheduler for scheduling a plurality of input flows to an output flow, comprising: means for allocating to each input flow a flow level and a threshold value, the flow level being indicative of the number of bits to be scheduled from the input flow, wherein the value of the flow level relative to the threshold value indicates whether the current scheduling of that input flow is sufficient to meet a necessary throughput for that input flow; means for determining if the flow level of an input flow is above its respective threshold value, and if the flow level is above its respective threshold value, means for scheduling that input flow, and reducing the flow level for that input flow by an amount corresponding to the number of bits scheduled.  
           [0045]    The scheduler may further include means for increasing the flow value for each input flow by a first predetermined value.  
           [0046]    The scheduling means may be adapted to be responsive to a priority for each input flow, wherein if a plurality of input flows have a flow value above their respective threshold value the one having the highest priority is scheduled.  
           [0047]    According to a further aspect of the invention there is provided a scheduler for scheduling a plurality of input flows to an output flow, comprising: means for allocating to each input flow a flow level and a threshold value, the flow level being indicative of the number of bits to be scheduled from the input flow, wherein the value of the flow level relative to the threshold value indicates whether the current scheduling of that input flow is sufficient to meet a necessary throughput for that input flow; means for increasing the value of each flow level by a predetermined amount; and means for selecting the input flow to be scheduled in dependence on the flow having a highest priority of those flows having a flow level greater than the respective threshold level, wherein there is further included means for, if no input flows have a flow level above the respective threshold level, increasing the flow level for each input flow having data to transmit by a second predetermined value. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0048]    The present invention is now described by way of reference to the figures which illustrate a particular example embodiment of the present invention, and in which:  
         [0049]    [0049]FIG. 1 illustrates schematically the concept of a scheduler in accordance with a preferred embodiment of the present invention;  
         [0050]    [0050]FIG. 2 illustrates a more detailed implementation of the scheduler in accordance with a preferred embodiment of the present invention;  
         [0051]    [0051]FIG. 3 illustrates the method steps in an initialisation stage in a preferred embodiment of the present invention;  
         [0052]    [0052]FIG. 4 illustrates the main scheduling steps in accordance with a preferred embodiment of the present invention;  
         [0053]    [0053]FIG. 5 illustrates in more detail a particular method sequence of the embodiment of FIG. 4; and  
         [0054]    [0054]FIG. 6 illustrates the concept of monitoring queue flow levels in accordance with a preferred embodiment of the present invention. 
     
    
     DESCRIPTION OF PREFERRED EMBODIMENTS  
       [0055]    The present invention is described herein with reference to a particular non-limiting example. One skilled in the art will appreciate that the invention is not limited to these examples, and may be more broadly applied.  
         [0056]    In particular the present invention is described in relation to an enhanced general packet radio service (EGPRS) example implementation. As such, the description of the embodiments given herein specifically refer to terminology which is directly related to EGPRS. Such terminology is only used in the context of the presented examples, and does not limit the invention.  
         [0057]    Referring to FIG. 1, there is illustrated the principle of the operation of the present invention. The left-hand side of FIG. 1 shows four incoming data flows. Each data flow is associated with a queue. As the described examples relate to EGPRS, a queue is referred to herein as a context. Wherever a context is referred to, it will be understood by a skilled person that in fact the description applies to any type of queue or incoming data flow.  
         [0058]    Thus in FIG. 1, a first queue (context  1 ) identified by reference numeral  104   a  is received on a signal line  106   a  to a scheduler  100 . A second queue (context  2 ) identified by reference numeral  104   b  is received on an input line  106   b . A third queue (context  3 ) identified by reference numeral  104   c  is received on an input line  106   c . More generally, an nth queue identified by “context n” and referenced as reference numeral  104   n  is received on an nth input line  106   n  to the scheduler  100 .  
         [0059]    As is conceptually illustrated in FIG. 1, each of the respective queues is associated with a queue controller. Thus the queue context  1  is associated with context controller  1   102   a . The queue context  2  is associated with a context controller  2   102   b . The queue context  3  is associated with a context controller  3   102   c . The queue context n is associated with a context controller n  102   n . In addition, the scheduler  100  is provided with a scheduler controller  108  which interfaces with all of the context controllers  102   a - 102   n.    
         [0060]    The scheduler  100  is further provided with a single output  110  which forms an output flow  112 . The purpose of the scheduler is to control each of the input queues on the inputs  106   a - 106   n  such that they are presented on the single output  110 . The implementation of the scheduling in accordance with the preferred embodiments of the present invention is described in further detail hereinafter.  
         [0061]    A particular embodiment of the present invention is described in further detail with relation to the flow diagrams of FIGS.  3 - 5 . However in order to fully understand the preferred embodiment of the present invention, FIG. 2 illustrates in detail an example implementation of a context controller, such as context controller n  102   n  of FIG. 1. FIG. 2 also illustrates in detail an example implementation of the scheduler controller  108  of FIG. 1. It will be appreciated, in referring to FIG. 2, that each of the context controllers  102   a - 102   n  is constructed similarly to the context controller  102   n . Similarly each of the context controllers  102   a - 102   n  interfaces with a scheduler controller  108  in a similar manner to that described in relation to the context controller n  102   n  in FIG. 2.  
         [0062]    The context controller n  102   n  includes a context control block  200 , a first storage block  202 , a second storage block  204 , comparators  220  and  226 , an incrementor  224 , an adder  218  and a multiplexer  222 . The context control block  200  generally controls the context controller  102   n , using internal control signals  201 . Thus all of the blocks illustrated in the block  102   n  in FIG. 2 will be operated under the control of the context control block  200 .  
         [0063]    The storage means  202  includes a set of storage locations which relate to parameters fixed for the current context. The storage means  202  includes a store  206  for storing a priority level associated with the context, a store  208  for storing a primary context quantum associated with the context, a store  210  for storing a maximum deficit associated with the context, a store  212  for storing a maximum secondary addition associated with the context, a store  211  for storing a secondary context quantum, and a store  213  for storing a minimum deficit value. The storage means  204  stores parameters associated with the context which may change as the context is processed by the scheduler. The storage means  204  includes a storage location  214  for a deficit level, and a storage location  216  for a secondary addition counter.  
         [0064]    The adder  218  receives as its two inputs the values stored in the primary context quantum  208  and the deficit level  214 . The comparator  220  receives as its inputs the value stored in the maximum deficit store  210  and the output of the adder  218 . The multiplexer  222  receives as its inputs the value stored in the maximum deficit store  210  and the output of the adder  218 . The multiplexer  222  is controlled by the output of the comparator  220  to output one of its inputs on its output line, which forms an input to the deficit level  214  to update the value stored therein. The increment block  224  receives as its input the secondary addition counter value  216 , and provides its output to the secondary addition counter value  216 . The comparator  226  receives as its inputs the secondary addition counter value  216  and the maximum secondary additions value  212 , and the comparator  226  forms an input to the context control block  200 , on a control line  201   a.    
         [0065]    The scheduler controller  108  in accordance with a preferred embodiment includes a scheduler control block  230 , a current maximum priority storage location  232 , a selected context storage location  239 , a multiplexer  234 , a comparator  236 , and a comparator  238 . The scheduler control block  230  generally controls the scheduler controller  108 . Control lines  229  interface the scheduler control block to various elements of the scheduler controller  108 . Thus all blocks of the scheduler controller  108  operate under the control of the scheduler control block  230 .  
         [0066]    The comparator  236  receives as its inputs the priority level in storage location  206  of the context controller  102   n  and the current maximum priority in storage location  232 . The multiplexer  234  similarly receives as its inputs the priority level in storage location  206  and the current maximum priority in storage location  232 . The multiplexer  234  is controlled by the output of the comparator  236  to provide one of its two inputs as its output, which provides an updated value to the current maximum priority in storage location  232 . The comparator  238  receives as an input the deficit level value in storage location  214  of the context controller  102   n . The comparator  238  simply operates to compare this value to zero.  
         [0067]    Before describing a preferred embodiment with reference to FIGS.  3 - 5 , an important principle of the present invention is first described with reference to FIG. 6. An important principle of the present invention is that the data flow from each queue, in terms of transmitted bits, is tracked. That is, a flow value for each queue is stored and maintained. As shown in FIG. 2, each of the context controllers  102  is provided with a deficit level in a storage location  214 . The deficit level is an important part for implementing the present invention. FIG. 6 illustrates the principle of operation of the deficit level.  
         [0068]    Referring to FIG. 6, reference numeral  600  generally refers to a “bucket” into which “bit quantums” are added. As discussed further hereinbelow, the content of the bucket represents the deficit level in the storage location  214 .  
         [0069]    Each bucket  600  has a “zero” level  606  at which a deficit level in the bucket is zero. The deficit level may vary above and below zero. If the deficit level varies above zero, then the queue or context associated with the bucket  600  has a lag compared to the guaranteed bit rate. In FIG. 6, a deficit level is shown at a level  604  above the zero level  606 , and therefore  602  represents a lag of capacity over the guaranteed bit rate. If the deficit level is below the zero level, then the queue or context associated with the bucket  600  has a lead compared to the guaranteed bit rate. The deficit level has a maximum value  620 , and a minimum value  622 .  
         [0070]    In summary, therefore, a positive deficit level (or value) means that the flow has capacity lag, i.e. it needs more capacity in order to obtain the guaranteed bit rate. A negative deficit level (or value) indicates that the flow is satisfied.  
         [0071]    A positive deficit level, i.e. between the zero level  606  and the maximum level  620 , indicates that the queue associated with the bucket  600  should be given more transmission turns in order to obtain the guaranteed bit rate. If the queue is empty, no transmission turns are granted to the queue.  
         [0072]    In accordance with the principles of the present invention, as long as the bucket deficit value is above the zero level  606 , the scheduler  100  shares the capacity of the output with that queue. As will be discussed further in detail hereinbelow, queues having the highest priority are scheduled first, followed by lower priority queues in the priority order. The guaranteed throughput for each queue is controlled by the quantum parameter, denoted by Q 1 . The quantum parameter for each queue represents the number of bits added to the bucket  600  in an initialisation step as discussed further hereinbelow. In FIG. 6 it is assumed that the implementation is an EGPRS implementation, and that in a 20 millisecond transmission period n bits  616   a - 616   n  are added to the bucket, the n bits comprising the quantum value Q 1 . As discussed in further detail hereinbelow, the quantum value is added to the bucket for each queue in a primary addition algorithm executed at the beginning of a transmission scheduling cycle.  
         [0073]    The maximum deficit parameter,  620 , indicates the maximum throughput lag, measured in bits. As such, the maximum deficit also defines the maximum throughput compensation time that one queue can achieve. The minimum deficit value parameter  622  defines the maximum throughput lead for the queue and is measured in bits. This parameter defines how much capacity one context can borrow from the future. The maximum deficit value is stored in the storage location  210  in the context controller  102  associated with that queue. Similarly the minimum deficit value may be stored in a similar storage location.  
         [0074]    The context quantum Q 1  for a queue is stored in the context quantum storage location  208 .  
         [0075]    A secondary quantum parameter, Q 2 , is used as described further hereinbelow when all the queues have achieved their guaranteed throughput. Residual capacity is then distributed with proportions defined by the secondary quantum values. This parameter is used in a secondary deficit update algorithm as described in further detail hereinbelow.  
         [0076]    A maximum secondary additions parameter, M 2 , is also defined together with the secondary quantum Q 2 . The maximum secondary additions parameter defines the absolute maximum throughput that one context can use in one transmission, independently of its time slot allocation. The maximum secondary additions parameter is stored in a storage location  212  of the context controller.  
         [0077]    As discussed hereinabove, each context or queue is associated with a priority level. The priority level defines the internal handling priority. During scheduling, higher priority queues or contexts are always serviced before lower priority ones. That is, scheduling is done in a strict priority order between the priority bounds. The main contribution of the priority parameter is notable in frame delays, such that frames in higher priority contexts experience lower delays. The priority for a particular queue is stored as the priority level in a storage location  206  of the context controller. For each context or queue, variable parameter values must be maintained in the storage means  204 . As discussed hereinabove, the deficit level is stored in storage location  214 , indicating the capacity deficit level in the bucket. The deficit value is positive when there is capacity deficit in the bucket, and vice versa.  
         [0078]    The number of secondary additions is stored in the storage location  216 . This counts the number of secondary additions for the current scheduling round. This counter is cleared during the primary update that starts the scheduling round.  
         [0079]    The various parameters required for implementing the preferred embodiment of the present invention are preferably stored for the whole lifetime of a particular data queue or context. However this is likely to be an implementation issue. These parameters should ideally be transferred to a new transceiver during cell reselection, if possible. This is required if the capacity loss during cell reselection needs to be fully compensated for.  
         [0080]    Referring to FIG. 3, a primary deficit update for a preferred embodiment of the present invention is now described. The primary deficit update is the initial sequence of steps carried out during the operation of the scheduler  100 . One scheduling cycle occurs for every transmission period, and the primary update takes place at the beginning of that scheduling cycle.  
         [0081]    The primary deficit update begins in a step  302 . The purpose of the primary deficit update is to share capacity to queues or contexts which have data which needs to be scheduled with guaranteed throughput. In order for data in a queue to be scheduled in accordance with the present invention, it is necessary for the deficit level  214  for that queue to have a value above zero. The primary deficit update procedure carries out an initialisation of each queue, as discussed further hereinbelow.  
         [0082]    In a first step the first context from the list of contexts is selected, as represented by steps  304 . In the present example, it is assumed that this is the context  1  of FIG. 1.  
         [0083]    In a step  306 , the deficit level  214  for the context is increased by the primary context quantum, Q 1 ,  208 . This operation is carried out by the adder  218  which adds the values of the storage locations  208  and  214 .  
         [0084]    In a step  308  it is then determined whether the result of this addition is greater than the maximum deficit allowable. The comparator  220  carries out this operation, by comparing the output of the adder  218  with the maximum deficit value stored in the location  210 . If the comparator determines that the output of the adder  218  is less than the maximum deficit value  210 , then it controls the multiplexer  222  to set the output of the adder  218  as the new deficit level in the storage location  214 . If the comparator  220  determines that the output of the adder exceeds the maximum deficit value, then the comparator  220  controls the multiplexer  222  to load the maximum deficit value in storage location  210  into the deficit level in storage location  214 . Step  310  represents the operation of setting the deficit level  214  to the maximum deficit value  210 .  
         [0085]    After the setting of the deficit to the maximum value in step  310  the method proceeds to step  312 . If there is no deficit overflow, the method proceeds directly to step  312  from step  308 .  
         [0086]    In step  312  the value of the secondary additions counter in location  216  is cleared and set to zero under control of the context control block  200 . The secondary additions counter  216  is always set to zero during a primary deficit update for a particular queue.  
         [0087]    In a step  314  the next queue or context at the input of the scheduler is processed. In a step  316  it is determined whether another queue or context exists. If a further queue or context exists, then steps  306 - 312  are repeated for that queue, and for all further queues at the inputs to the scheduler. If no further context exists, or if all contexts have been processed, then the method moves to step  318 , and the primary deficit update is ended.  
         [0088]    Thus in a primary deficit update the deficit level for all context or queues is increased by the context quantum, Q 1 , for that queue. After the primary deficit update, the method moves on to the main scheduling cycle, as illustrated by FIG. 4. The scheduling cycle begins in step  400 , immediately after the end of the primary deficit update process.  
         [0089]    In a step  402 , the first context or queue is selected. Again, for the purposes of example, it is assumed that the context  1  queue  104   a  is first selected. In a first step  404  it is determined whether the packet controller unit (not shown) of which the scheduler  100  is a part has permitted the particular queue or context selected to send data. If the context or queue is not permitted to send data, then the process jumps to step  412 . If the queue or context is permitted to send data, then the process proceeds to step  406 .  
         [0090]    In step  406  the priority level of the selected context or queue is compared to a previous priority level maximum. The scheduler controller  108  reads the priority for the current context from the priority level in storage location  206  and reads the current maximum priority from the storage location  232 , and compares them in comparator  236 . For the first context, the current maximum priority  232  will be set to a predetermined value. Typically this predetermined value will represent the lowest available priority. Thus, in the present case, if it is determined that the priority of the current context is greater than the highest priority so far. The comparator  236  controls the multiplexer  234  to set the current maximum priority value  232  to be equal to the priority level  206 . That is, the value in store  206  is carried to store  232 . The process then moves on to step  408 . If the priority in storage location  206  is equal to or lower than the current maximum priority  232 , then this means that there are contexts or queues at the inputs of the scheduler which have a higher priority than the current context or queue, and as such the process moves on to step  412 .  
         [0091]    In step  408 , it is determined whether the deficit level for the particular context or queue in storage location  214  is greater than zero. The scheduler controller  108  reads the deficit level from storage location  214  and provides it as an input to comparator  238 , which compares the said value with zero. If the value is greater than zero, i.e. the flow has capacity lag, then the method progresses to step  410 . If the deficit is not greater than zero, i.e. the flow has capacity lead, then the process moves on to step  412 .  
         [0092]    In step  410 , it has now been determined that the current context has the highest priority, and that the deficit level in storage location  214  for the current context or queue is greater than zero. As such, in step  410  this particular queue or context is selected, and the priority level in storage location  206  for this particular context or queue is copied to storage location  232  and set as the current maximum priority using the multiplexer  234 . The scheduler control block  230  uses one of its signals  229 ,  229   a , to enter the identification of the current context or queue into a selected context storage location  239 .  
         [0093]    In a step  412 , the next context in the list is selected. In a step  414 , it is determined whether a next context actually exists. If such context exists, then the steps  404 - 412  are repeated for that context. If any of the next contexts have a priority level which is higher than the priority of any preceding context, then that context is selected and its identification stored in the location  239  of the scheduler controller  108 . Such context or queue is only selected, however, if the deficit of such context or queue is greater than zero. Thus, the steps  404 - 412  are repeated for each context or queue. At the end of this sequence for each of the context or queues, the identification of the context or queue having the highest priority and having a deficit level greater than zero is stored in the storage location  239 .  
         [0094]    If in steps  404 - 414  it is determined that no context or queue has a deficit greater than zero, then no context will be selected and stored in the selected context storage location  239 . In step  416  it is determined whether a context has been selected. If no context has been selected, because no contexts have a deficit level greater than zero, or were not allowed to transmit, then the method proceeds to perform a secondary deficit update in a step  428 . The secondary deficit update  428  is described further herein with reference to FIG. 5.  
         [0095]    If a context has been successfully selected, and this is identified in step  416 , then the method proceeds to step  418 . In step  418  it is determined if a new radio link control (RLC) block is to be transmitted. The transmission of a RLC block is specific to this EGPRS embodiment. More generally, it may be considered in step  418  as to whether a block of payload data is to be transmitted. If the queue or context is about to perform a transmission of an already transmitted block, i.e. a retransmission, then the step  420  is by-passed, and the deficit level is not updated.  
         [0096]    If a newly generated RLC block is to be transmitted, then the deficit level in storage location  214  is decremented by the number of bits constituting the RLC block. This is represented by step  420 .  
         [0097]    In a step  422  the deficit limits are checked. That is, it is checked that the deficit level has not been decreased below the minimum deficit value, level  622  in FIG. 6. If the deficit level has been decreased below such value, then the deficit level is set at the minimum deficit value. The method then moves on to a step  424 .  
         [0098]    In step  424 , the context or queue which has just been assigned a transmission turn is relocated to the end of the list of queues or contexts. Thus, following each scheduling step, the selected flow is always placed at the end of the flow list for the next round of scheduling. This provided round-robin scheduling within a given priority level. This round-robin functionality is especially important if the scheduler is overloaded, even for a short-time.  
         [0099]    Then in a step  426  the scheduling step is terminated.  
         [0100]    After the scheduling step ends in step  426 , then in a new scheduling cycle a next primary deficit update is performed in accordance with the procedure of FIG. 3. Thereafter a next scheduling step is performed in accordance with the above described procedure for FIG. 4. Thus the scheduler  108  rotates between a primary deficit update for all queues or context, and the scheduling step for all queues or context.  
         [0101]    As discussed hereinabove, if during steps  404 - 410  for all queues or contexts no context is selected in step  416 , then a secondary deficit update  428  is performed. The secondary deficit update is now described with reference to FIG. 5.  
         [0102]    The secondary deficit update begins in step  500 . In a step  502  the first context or queue at the input to the scheduler  100  is selected. Again, it is assumed that this is the context  1   104   a.    
         [0103]    In a first step it is determined whether the secondary update has been performed for this particular context more than the value in the maximum secondary addition storage location  212 . For the first iteration, the value in the secondary additions count storage location  216  will be zero. The comparator  226  operates to compare the secondary additions count value in storage location  216  with the maximum secondary additions value in storage location  212 , and the output of the comparator to an input on the control line  218  to the context control block  200 . If the output of the comparator  226  indicates that the secondary additions count value  216  is equal to the maximum secondary additions value  212  then the secondary deficit update for the current context or queue is abandoned, and the method proceeds to step  514 .  
         [0104]    If the secondary additions count  216  does not exceed the maximum secondary additions count  212 , then the method proceeds to step  306 . In step  306 , the incrementor  224  increments the value of the secondary addition count  216  by one. The incrementor  224  reads in the current value of the secondary additions count and storage location  216 , incremented by one, and then writes in the new value to the secondary additions count at storage location  216 .  
         [0105]    In step  508 , the deficit level  214  is increased by the secondary quantum value. An adder receives the deficit level in storage location  214  and the secondary quantum value and provides a summed value on the output thereof.  
         [0106]    In a step  510  it is determined whether the value at the output of the adder exceeds the maximum deficit value in storage location  210 . If the maximum deficit value  210  is not exceeded, then a multiplexer is controlled by the output of the comparator to update the deficit level in storage location  214  with the output of the adder. The method then moves on to step  514 .  
         [0107]    If in step  510  it is determined that the output of the adder does exceed the maximum deficit value  210 , then the deficit level in storage location  214  is replaced with the maximum deficit value  210 , by the multiplexer  222  under control of the comparator  220 . Thereafter the method proceeds to step  514 .  
         [0108]    In step  514  a further context is selected. In step  516  it is determined whether another context exists. If another context exists, then steps  504 - 512  are repeated for that context. If in step  516  it is determined that no further context exists, or that all contexts had been processed, then the secondary deficit update terminates in step  518 . It should be noted that the secondary deficit update is only performed for those queues which have data and can transmit in the timeslot to be scheduled.  
         [0109]    After the end of the secondary deficit update in step  518 , the scheduling step of FIG. 4 proceeds to step  430 , in which it is determined whether any deficit was modified during the update. That is, whether any deficit count value  214  was modified during the update. If it is determined that no count values are modified during the update, then the method proceeds to step  426  and the scheduling step ends, as there is no data to transmit, or the modification of all deficit levels was prohibited by the maximum additions limits. If it is determined that any deficit level was changed, then the method returns to step  402 , and the steps  404 - 412  are repeated for each context or queue. Once the steps  404 - 412  are repeated for each context or queue, it is possible that there is still no active context or queue which has a deficit greater than zero. If this is the case, then a further secondary deficit update may be performed in step  428 . If a further secondary deficit update is performed, following the steps of FIG. 5, then the secondary additions count value  216  for each queue is further updated for having such further secondary deficit update.  
         [0110]    The method only proceeds to a primary deficit update on the beginning of a new scheduling cycle. During the primary deficit update, on a new scheduling cycle, the secondary additions counter for any queue which is processed is reset to zero.  
         [0111]    The present invention is thus related to scheduling. Scheduling is performed before every transmission. In EGPRS, this means that scheduling is performed once every 20 ms. The context, or queue, list is transmission wide. That is, the context list is associated with the transmission. The scheduling of one transmission means that the transmitting temporary block flow is selected for each time slot. The scheduling starts, as discussed herein, with a primary update. This primary update is performed once, at the beginning of the transmission scheduling cycle. Thereafter, the scheduling step is performed for each time slot, one after each other. Thus, in the EGPRS example, the scheduling step schedules eight time slots, and up to eight radio blocks may be transmitted following each scheduling cycle. That is, eight radio blocks may be transmitted between primary updates. The queues are transmission specific, but depending on the multi-slot allocation, the queues may only be active on selected time-slots within the transmission period. If the first iteration does not find a non-empty queue with deficit level value above zero, then a secondary update is performed on that time-slot. The secondary additions counter is cleared at the beginning of the transmission scheduling, and may be incremented on any time slot where the secondary update is performed. As any queue (temporary block flow) may be active on many time slots in the transmission, the check in step  404  of FIG. 4 is performed. This check determines whether a queue (temporary block flow) can actually transmit on the time slot to be scheduled.  
         [0112]    In summary, in the scheduling step described in relation to FIG. 4, a queue is selected for the output  110  of the scheduler  100  in dependence on the following rules:  
         [0113]    1. Only data contexts are considered which have a temporary block flow on the time slot to be scheduled, and which have a deficit level above zero, and actually have data to send.  
         [0114]    2. In that list, select those contexts that have the highest priority.  
         [0115]    3. Select the first context in the list of the previously selected contexts.  
         [0116]    In these rules, it can occur that all contexts have a deficit value below zero and thus do not have permission to send. This means that the time slot has capacity that is not allocated for guaranteed throughput data context. In that case, the secondary scheduling step algorithm is used, as described in relation to FIG. 5.  
         [0117]    In summary, the secondary update step of FIG. 5 is performed when all data contexts in a time slot are satisfied, i.e. their guaranteed throughput requirements are fulfilled. This is performed according to the following rules:  
         [0118]    1. A secondary update is performed as described in relation to FIG. 5. The secondary quantum is added to the deficit level of each active context or queue, that have their secondary additions variable parameter lower than the maximum number of variable additions allowed.  
         [0119]    2. The secondary additions counter for the particular context or queue is incremented.  
         [0120]    3. If the maximum additions parameter indicates that the secondary additions counter for all context or queues has reached its maximum value, then the secondary deficit update is abandoned.  
         [0121]    4. If the secondary deficit update is abandoned, then the scheduling cycle is repeated from the start.  
         [0122]    In the secondary update step, the maximum throughput limitation is imposed by the maximum additions parameter. It may occur that all contexts are limited by the maximum additions parameter, and then the transmission turn must be left unused, and a dummy or an idle RLC block sent in that time slot.  
         [0123]    As has been described hereinabove, the deficit levels of all contexts are updated with a primary quantum at a fixed time in the GSM time structure, using the primary deficit update algorithm as described in relation to FIG. 3. This primary deficit update algorithm takes place at a predetermined time. In GPRS, the predetermined time is the start of a TDMA frame. The new deficit level for every context is computed with the following rules:  
         [0124]    1. Add the quantum value to the deficit level.  
         [0125]    2. If the deficit level is above the maximum value, set it to the maximum value.  
         [0126]    3. Clear the secondary additions counter.  
         [0127]    Because of the repetitive nature of the update, the guaranteed bit rate of a data context is simply the sum of primary quantum additions in one second. As the primary addition is done at the start of each scheduling cycle, it happens exactly 50 times per second in an EGPRS implementation (based on a 20 ms transmission period). Thus the context guaranteed throughput is: 
           T   G =50 *Q   1  bits/ s   
         [0128]    where Q 1  is the quantum of that context.  
         [0129]    In the same way, the maximum throughput is: 
           T   M =50*( Q   1   +M   2 * Q   2 ) bits/ s   
         [0130]    where Q 2  is the secondary quantum and M 2  is the maximum number of secondary additions.  
         [0131]    The allowed traffic burstiness and forced smoothing is controlled by the minimum and maximum deficit values. The deficit level in the “bucket” of FIG. 6 defines how much the context has used capacity above or below the allocated throughput. For example, if the context does not use all quanta collected in the bucket, the deficit value increases, and the context can use the capacity later. Thus the maximum deficit value defines how much capacity the context can store for future use, or how many bits it can transmit without scheduler posed limitations, if it has allocated capacity for it.  
         [0132]    In the same way, the minimum value defines the maximum penalty imposed on the context for the use of non-allocated capacity. If the context uses more capacity than allocated, the deficit value sinks below zero, and the context must wait for the deficit value to rise again above zero. This is only possible if the context is allowed to send even if the deficit is below zero. This situation happens only when other functions require data transmission, for example in EGPRS for polling and downlink power control.  
         [0133]    The minimum and maximum deficit limits essentially define the memory property of the scheduler. As such, the effect on other flows must also be considered carefully, because too high values for maximum deficit may easily break the context isolation. However, for full compensation of cell reselections, the maximum deficit should not be too low.  
         [0134]    During cell reselection, the scheduler variables are transferred to the new packet control unit (PCU). This requires inter-PCU communication, and as such is a preferable feature where such intercommunication is implemented.  
         [0135]    The technique according to the present invention also preferably provides a fallback mechanism for overload situations. In such a situation, the deficit values for nearly all contexts are positive, and the scheduler serves the highest priority context in a round robin fashion, until their deficit values fall below zero. When the deficit values of the high priority contexts fall below zero, the next priority context will get round-robin service. However, admission control is preferably utilised to keep the scheduler well below the overload limit.  
         [0136]    The preferred implementation of the present invention requires that the deficit value is updated every time when a new RLC block is generated, even when the transmission turn is forced by other blocks in the system. However the deficit is not updated after retransmissions. This is essential for the guaranteed throughput, because retransmissions do not provide throughput from the scheduler point of view. After the transmission related deficit update, the deficit value should be checked against the minimum deficit, to determine whether an underflow has happened. In that case, the deficit is set to the minimum value.  
         [0137]    The data flow from the logical link control (LLC) queue is tracked. During retransmissions, no data is de-queued from the LLC queue and the deficit level is not decremented, keeping it above zero. Thus the context will get transmission turns until something is properly getting through to the RLC layer. This function provides indirect, yet fast, RLC level retransmission compensation.  
         [0138]    The present invention preferably allows even for best effort context to have reasonable resource allocation. This is feasible because the channel capacity fluctuation renders the contexts with best effort service nearly useless, if the schedule does not provide absolute minimum service for those contexts. The allocation for such context can be set to the minimum value that allows the upper layer protocols to work properly.  
         [0139]    The present invention can be preferably configured to smooth the control traffic flows. This behaviour is particularly important with the TCP/IP, which is an important upper layer protocol used with EGPRS.  
         [0140]    The scheduler described herein may be implemented in an appropriate network element. For example, the scheduler may advantageously be implemented in a base station controller or packet controller unit, at RLC protocol level in the protocol stack. Corresponding scheduling takes place in the serving GPRS support node (SGSN) at a higher protocol stack layer.  
         [0141]    The present invention has been described herein with reference to particular examples, and particularly with reference to an implementation in an EGPRS system. A person skilled in the art will appreciate that the invention is not limited to such an implementation. The invention is more generally applicable to any application which requires scheduling of data flows.  
         [0142]    The skilled person will appreciate modifications to the presented embodiments and examples which allow the present invention to be implemented in alternative applications. The scope of protection afforded by the application is defined in the appended claims.