Scheduling a shared resource among synchronous and asynchronous packet flows

A method for the scheduling of a service resource shared among several information packet flows that generate respective associated queues, said flows including synchronous flows (i=1, 2, . . . , Ns) that require a guaranteed minimum service rate (ri) and asynchronous flows (j=1, 2, . . . , NA) that use the service capacity of said the resource that is left unused by the synchronous flows, method making use of a server and comprising the following steps:

• (a) causing said server to visit the respective queues associated to said flows (i, j) in successive cycles on the basis of a target rotation time value (TTRT), which identifies the time necessary for the server to complete a visit cycle on said respective queues;
• (b) associating each synchronous flow (i) with a respective synchronous capacity value (Hi) indicating a maximum period of time for which the respective synchronous flow can be serviced before the server moves on;
• (c) associating each asynchronous flow (j) with a first respective delay value (Li) that identifies a value that must be made up for the respective queue to have the right to be serviced, and a second respective value (last_visit_time) that indicates an instant in which the server visited the respective queue in a previous cycle, determining for said respective queue, a time that has elapsed since the server's previous visit;
• (d) servicing each queue associated to a synchronous flow (i) for a maximum service time relative to said respective value of synchronous capacity (Hi);
• (e) servicing each queue associated to an asynchronous flow
• (j) only if the server's visit occurs before the expected instant, said advance being determined as the difference between said target rotation time value (TTRT) and time that has elapsed since the server's previous visit and the accumulated delay;
• if positive, this difference defining a maximum service time for each asynchronous queue;
• and
• (f) defining said respective synchronous capacity value (Hi) for the queue associated to the i-th synchronous flow by, insuring that:
• (f1) a sum of the synchronous capacity values for said synchronous flows plus the duration of the longest packet services by said shared service resource (Tmax) does not exceed said target rotation time value (TTRT);
• and
• (f2) said target rotation time value (TTRT) is not lower than a ratio of said longest packet serviced by said shared service resource (Tmax) to a complement to one of the sum over said synchronous flows of the minimum service rates (ri) required by said synchronous flows normalized to the service capacity (C) of said shared service resource.

A system for the scheduling of a service resource shared among several information packet flows that generate respective associated queues, said flows including synchronous flows (i=1, 2, . . . , NS) that require a guaranteed minimum service rate and asynchronous flows (j=1, 2, . . . , NA) destined to use the service capacity of said resource left unused by the synchronous flows, the system including a server able to visit the respective queues associated to said flows (i, j) in successive cycles, which is configured to perform the following operations:

• determine a target rotation time value (TTRT) that identifies the time necessary for the server to complete a visiting cycle of said respective queues,
• associate to each synchronous flow (i) a respective synchronous capacity value (Hi) indicating the maximum amount of time for which a synchronous flow can be serviced before moving on to the next,
• associate to each asynchronous flow (j) a first respective delay value (Lj) that identifies the delay that must be made up for the respective queue to have the right to be serviced, and a second respective value (last_visit_time) that indicates the instant in which in the previous cycle the server visited the respective queue, determining for said respective queue, the time that has elapsed since the server's previous visit,
• service each queue associated to a synchronous flow (i) for a maximum period of time relating to said respective synchronous capacity value (Hi), and
• service each queue associated to an asynchronous flow (j) only if the server's visit occurs before the expected instant, said advance being determined as the difference between said target rotation time (TTRT) and the time that has elapsed since the server's (10) previous visit and the accumulated delay difference, if positive, defining the maximum service time for each said asynchronous queue,
• the system being configured to define said respective synchronous capacity value (Hi) for the queue associated to the i-th synchronous flow by ensuring that:
• the sum of the synchronous capacity values for said synchronous flows plus the duration of the longest packet serviced by said shared service resource (T) does not exceed said target rotation time value (TTRT);
• and
• said target rotation time value (TTRT) is not lower than the ratio of said longest packet serviced by said shared service resource (Tmm) to the complementary to one of the sum over said synchronous flows of the minimum service rates (ri) required by said synchronous flows normalized to the service capacity (C of said shared service resource.