Abstract:
A method for selecting one of several queues and for extracting one or more data segments from a selected queue for transmitting with the aid of an output interface includes: selecting the output interface by a first scheduler; selecting a number of queues by a second scheduler; selecting one queue from the number of queues by a third scheduler; and sending one or more data segments from the selected queue to the output interface for transmission.

Description:
BACKGROUND OF THE INVENTION 
       [0001]    1. Field of the Invention 
         [0002]    The present invention relates to a method for selecting one of several data queues in order to extract one or more data segments from the queue selected. 
         [0003]    2. Description of the Related Art 
         [0004]    Methods are known for selecting one of several queues in order to extract one or more data segments from the queue selected. 
       BRIEF SUMMARY OF THE INVENTION 
       [0005]    A queue is selected by a first scheduler, a second scheduler and a third scheduler, so that one or more data segments from the queue selected may be forwarded to the output interface. Owing to this advantageous three-step scheduling, first of all, high-priority data intended for a specific output interface is also treated and sent with high priority. Secondly, this three-step scheduling operation provides a method which may easily be implemented in hardware. 
         [0006]    Additional features, possibilities of application and advantages of the present invention are derived from the following description of exemplary embodiments of the invention, which are illustrated in the figures of the drawings. All of the features described or illustrated, alone or in any combination, constitute the subject matter of the present invention, regardless of their formulation or presentation in the specification or drawing. The same reference numerals are used in all figures for functionally equivalent sizes and features, even in the case of different specific embodiments. In the following, exemplary specific embodiments of the invention are explained with reference to the drawing. 
     
    
     
       BRIEF SUMMARY OF THE INVENTION 
         [0007]      FIG. 1  shows a communications schema. 
           [0008]      FIG. 2  shows a three-step scheduling method in schematic form. 
           [0009]      FIG. 3  shows a schematic process diagram. 
       
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
       [0010]      FIG. 1  shows a communications schema  2  in which a plurality of queues  4   a - 4   c  are filled with data. A single processing unit  6  is provided for queues  4 . Because there is a single processing unit  6 , a selection unit  8  must determine in what order and how long processing unit  6  receives data from different queues  4 . Processing unit  6  is connected to different output interfaces  10   a - 10   c,  to which the data from the queues is passed on. 
         [0011]      FIG. 2  shows a three-step scheduling method in a schematic view  12 . A first active circular list  14 , which is also denotable as active calendar wheel, contains a sequence of processing steps provided in each case for one time slot, one processing step being assigned to one output interface  10 . Circular list  14  is processed per entry into a time slot in accordance with an arrow  16 . After the lowest or last element of circular list  14  has been processed, here for interface  10   c,  circular list  14  is begun again at the first element, here for interface  10   a.  Thus, in each case one output interface  10  in circular list  14  is assigned to one time slot. 
         [0012]    In the first element of circular list  14 , one queue  4  is thus processed for output interface  10   a.  For the second and third entry, in each instance one queue  4  is processed for output interface  10   b.  For the last entry, one queue  4  is processed for output interface  10   c.    
         [0013]    One or more data segments are removed from a selected queue  4  only when output interface  10  is ready to receive in the instantaneous time slot. In another specific embodiment, a queue is selected only when particular intended output interface  10 , which is selected according to active circular list  14 , is ready to receive in the instantaneous time slot. 
         [0014]    Furthermore, in addition to active circular list  14 , a passive circular list  18  is shown in the background, which is able to be configured while active circular list  14  is being processed. After being configured, passive circular list  18  is able to replace active circular list  14 . Passive circular list  18  is used to take into account output interfaces  10  added or output interfaces  10  deactivated during the operation of processing unit  6 . In addition, a weighting may be factored in in the handling of interfaces  10  in passive calendar wheel  18 . 
         [0015]    Circular lists  14  and  18  are managed and processed with the aid of a first scheduler  20 , which selects output interface  10 . For instance, on the basis of the second entry in circular list  14 , output interface  10   b  is assigned a number of priorities  22   a  and  22   b,  the number of two priorities  22  shown being only by way of example. Via the number of priorities and a priority scheduling with regard to priorities  22 , it is possible to ensure that high-priority data in selected queues  4 , to which a higher-order priority  22  is assigned, are preferentially processed and sent. 
         [0016]    With the aid of a second scheduler  24 , a priority scheduling is carried out on the basis of fixed priorities  22 , and with that, a number of queues  4  is selected. A number of queues  4  is assigned to priority  22 . Thus, a first number of queues  4   d - 4   i  is assigned to priority  22   a.  A second number of queues  4   k  and  4   m  is assigned to second priority  22   b.    
         [0017]    The function of a third scheduler  26  is explained by way of example on the basis of the first number of queues  4   d - 4   i . Third scheduler  26  includes a Ready FIFO  30  as well as a Wait FIFO  32 . In order to carry out a weighted round robin process with the aid of third scheduler  26 , each of queues  4   d - 4   i  is assigned a weighting, and as a function of the processing, a counter is decremented per processing step of queue  4 , the counter initially being set to the value of the weighting upon entry of queue  4  into FIFO  30 . According to a first embodiment, a new queue  4  is inserted into FIFO  30  in accordance with arrow  34 , the counter of queue  4  being set to a product of the weighting of queue  4  and the number of queues  4  within priority  22 , divided by X. In an alternative embodiment, a new queue  4  is inserted into FIFO  32  in accordance with arrow  36 . 
         [0018]    Upon selection of queue  4 , first queue  4   g  is selected from Ready FIFO  30  for processing. If queue  4   g  is empty, and thus has no more data segments, queue  4   g  is excluded from the scheduling as per arrow  38 , queue  4   g  being removed accordingly. 
         [0019]    After one processing step of queue  4   g,  thus, after the extraction of one data segment or one data block including several segments, the counter of queue  4   g  is decremented. When the counter of queue  4   g  reaches a value of zero, then as per an arrow  40 , queue  4   g  is placed at the end of Wait FIFO  32 , and the counter of queue  4   g  is set to the value of the weighting of queue  4   g.  If, after the counter of queue  4   g  has been decremented, it is greater than zero, then according to arrow  42 , queue  4   g  is placed at the end of FIFO  30 . After the end of one processing step of queue  4   g,  queue  4   h  is placed at the beginning of FIFO  30 . 
         [0020]    A distinction is made between scheduling based on data segment and scheduling based on data block. In the case of scheduling based on data segment, as a function of output interface  10 , one data segment is extracted from selected queue  4  before there is a change to another queue  4 . For example, scheduling based on data segment is possible for output interfaces which have a plurality of input buffers and are able to resort the data segments received, since in the case of scheduling based on data segment, data segments of one data block are able to overtake each other, which means the original sequence of the data segments, e.g., in one data block, is no longer maintained. 
         [0021]    In the case of scheduling based on data block, one data block including a plurality of data segments is to be taken as a basis. As a function of output interface  10 , an entire data block is extracted from selected queue  4  before there is a change to another queue  4 . Scheduling based on data block is necessary, for example, for output interfaces which have only one input buffer for the data block and cannot easily resort the data received, since in the case of scheduling based on data segment, data segments of one data block are able to overtake each other, which means the original sequence of the data segments in the data block is no longer maintained. 
         [0022]    If no more queues are contained in active FIFO  30 , then FIFO  32  is activated and FIFO  30  is deactivated, FIFO  32  being treated exactly the same as FIFO  30  previously described. 
         [0023]    First scheduler  20  starts the scheduling of second and third schedulers  24  and  26  if, in the time slot of the scheduling by scheduler  20 , output interface  10  is not ready to receive data. In this case, data could get lost if the method or system is realized in hardware as a pipeline, and second and third schedulers  24 ,  26  as well as further processing units located towards the output interface have already processed or are processing data for particular intended output interface  10  no longer ready to receive. Buffer memories are advantageously provided for this in input interfaces, which prevent data segments from getting lost because an output interface  10  is not ready to receive. If a data loss occurs, this is signaled to the pertinent input interface, so that the data may be inserted again into a queue  4 . 
         [0024]      FIG. 3  shows, in schematic form, three concurrently proceeding processes which are carried out during one time slot  60 . A first process  62  records if new data of a queue  4  has been received and checks whether the appertaining queue is already assigned to a scheduler  26 . If a queue  4  which contains new data is still not assigned to a third scheduler  26 , it is then enqueued in appropriate FIFO  30  or  32  according to arrow  34  or  36  of  FIG. 2 . 
         [0025]    A second process  64  checks whether appertaining output interface  10  to be processed in the instantaneous time slot is already assigned to a third scheduler  26 . If respective output interface  10  is still not assigned to a scheduler  26 , process  64  then leads to at least one entry for respective output interface  10  in passive list  18 . On the other hand, if a third scheduler  26  is already active for the respective output interface, then third scheduler  26  selects next queue  4 . Second process  64  activates FIFO  32  as soon as FIFO  30  has no more queues  4 . 
         [0026]    Third process  66  executes the steps according to arrows  38 ,  40  and  42 . 
         [0027]    In the case of scheduling based on data block, only after the last data segment of a data block has been extracted from the queue does third process  66  select another queue. First process  62  marks a queue as not empty only after the last data segment of a data block is enqueued in the queue, whereupon the queue may be assigned to a scheduler  26 .