Method and System for Scheduling Utilization of Resources, Related Communication Network and Computer Program Product

• US 20080025301A1
• Filed: 04/26/2004
• Published: 01/31/2008
• Est. Priority Date: 04/26/2004
• Status: Active Grant

• Current Assignee: Telecom Italia S.p.A.
• Original Assignee: Telecom Italia S.p.A.
• Inventors: Scarrone, Enrico, Vercellone, Vinicio, Lenzini, Luciano, Mingozzi, Enzo, Stea, Giovanni, Sassi, Massimo
• Granted Patent: US 7,801,152 B2
• Time in Patent Office: Days
• US Class Current: 370/389
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/2408 for supporting different services, e.g. a differentiated services [DiffServ] type of service
• CPC Class Codes: H04L 47/2416 Real-time traffic
• CPC Class Codes: H04L 47/245 using preemption
• CPC Class Codes: H04L 47/283 in response to processing delays, e.g. caused by jitter or round trip time [RTT]
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/521 Static queue service slot or fixed bandwidth allocation
• CPC Class Codes: H04L 47/522 Dynamic queue service slot or variable bandwidth allocation
• CPC Class Codes: H04L 47/562 Attaching a time tag to queues
• CPC Class Codes: H04L 47/6215 Individual queue per QOS, rate or priority

Abstract

A system for scheduling utilization of a service resource by a plurality of flows of information packets, wherein the flows include rate-guaranteed synchronous flows and best-effort asynchronous flows, the asynchronous flows exploiting the service capacity of the resource left unexploited by the synchronous flows. A server visits the flows, in subsequent rounds, by visiting first the synchronous flows followed by the asynchronous flows. The server is configured for detecting any backlogged synchronous flow, and when the server visits any said backlogged synchronous flow, it allows the backlogged synchronous flow to utilize the resource for a given time, whereby the synchronous flows have a guaranteed transmission window on each round. When the server visits any asynchronous flow, the time elapsed since the last visit by the server to the same asynchronous flow is determined. If the visit to the asynchronous flow occurs later than expected based on a reference round time, the asynchronous flow being visited is restrained from utilizing the resource for the ongoing round, and if the visit occurs earlier than expected based on the reference round time the asynchronous flow being visited is allowed to utilize the resource for a respective given time.

Claims

1-24. -24. (canceled)

25. A method of scheduling utilization of a service resource by a plurality of flows of information packets, said plurality of flows comprising rate-guaranteed synchronous flows and best-efforts asynchronous flows, wherein said asynchronous flows exploit the service capacity of said resource left unexploited by said synchronous flows, comprising the steps of:

providing a server that visits said plurality of flows in subsequent rounds, said server visiting first within each said round said synchronous flows followed by said asynchronous flows;

detecting any backlogged synchronous flow in said plurality of synchronous flows,

when said server visits any said backlogged synchronous flow, allowing said backlogged synchronous flow to utilize said resource for a given time, whereby said synchronous flows have a guaranteed transmission window on each said round;

determining a reference round time indicative of the expected time for said server to complete a round of visits of said plurality of flows,

when said server visits any said asynchronous flow, determining the time elapsed since the last visit by said server to the same asynchronous flow, and;

i) if the visit to said asynchronous flow occurs later than expected based on said reference round time, restraining said asynchronous flow being visited from utilizing said resource for the ongoing round,

ii) if the visit to said asynchronous flow occurs earlier than expected based on said reference round time, allowing said asynchronous flow being visited to utilize said resource for a respective given time, said respective given time being a function of the earliness of the server visit, whereby said function regulates the exploitation by each said asynchronous flows of said service capacity of said resource left unexploited by said synchronous flows.

26. The method of claim 25, wherein said server stops visiting any said flows,

when said given time or respective given time has elapsed, or

when the flow being visited has cleared its backlog, whichever occurs first.

27. The method of claim 25, comprising the steps of:

determining a synchronous bandwidth for said synchronous flows; and

setting an upper bound to said given time as a function of said synchronous bandwidth.

28. The method of claim 25, comprising the steps of:

associating with each said asynchronous flow a value indicative of the delay accumulated by said server in visiting said asynchronous flow in the previous rounds,

when said server visits said asynchronous flow, subtracting from said reference round time the duration of the previous round to obtain a substraction result, and

subtracting said value from said substraction result thus computing an earliness value for the current round.

29. The method of claim 25, comprising the steps of:

if said earliness value is negative, storing the absolute value thereof in said value indicative of the delay accumulated, and

restraining said asynchronous flow being visited from utilizing said resource for the ongoing round.

30. The method of claim 25, comprising the steps of:

if said earliness value is positive, resetting to zero said value indicative of the delay accumulated; and

granting said asynchronous flow being visited said respective given time for utilizing said resource.

31. The method of claim 25, comprising the step of selecting respective functions regulating the exploitation by said asynchronous flows of the service capacity of said resource left unexploited by said synchronous flows.

32. The method of claim 25, comprising the step of making said respective given time proportional to said earliness via a proportionality factor.

33. The method of claim 32, comprising the step of selecting said proportionality factor in a range (0,1].

34. The method of claim 32, comprising the step of selecting respective proportionality factors for said asynchronous flows.

35. The method of claim 25, comprising the step of determining respective synchronous bandwidths for said synchronous flows, wherein the sum of the time intervals corresponding to said synchronous bandwidths is lower than or equal to said reference round time.

48. A computer program product loadable in the memory of at least one computer and comprising software code portions capable of performing the method of claim 25.

36. A system for scheduling utilization of a service resource by a plurality of flows of information packets, said plurality of flows comprising rate-guaranteed synchronous flows and best-effort asynchronous flows, wherein said asynchronous flows exploit the service capacity of said resource left unexploited by said synchronous flows, the system comprising a server configured for visiting said plurality of flows in subsequent rounds, said server visiting first within each said round said synchronous flows followed by said asynchronous flows, said server being configured for:

detecting any backlogged synchronous flow in said plurality of synchronous flows,

when said server visits any said backlogged synchronous flow, allowing said backlogged synchronous flow to utilize said resource for a given time, whereby said synchronous flows have a guaranteed transmission window on each said round;

determining a reference round time indicative of the expected time for said server to complete a round of visits of said plurality of flows,

when said server visits any said asynchronous flow, determining the time elapsed since the last visit by said server to the same asynchronous flow, and;

i) if the visit to said asynchronous flow occurs later than expected based on said reference round time, restraining said asynchronous flow being visited from utilizing said resource for the ongoing round,

ii) if the visit to said asynchronous flow occurs earlier than expected based on said reference round time, allowing said asynchronous flow being visited to utilize said resource for a respective given time, said respective given time being a function of the earliness of the server visit, whereby said function regulates the exploitation by each said asynchronous flows of said service capacity of said resource left unexploited by said synchronous flows.

37. The system of claim 36, wherein said server is configured for stopping visiting any said flows:

when said given time or respective given time has elapsed, or

when the flow being visited has cleared its backlog, whichever occurs first.

38. The system of claim 36, wherein said sever is configured for:

determining a synchronous bandwidth for said synchronous flows; and

setting an upper bound to said given time as a function of said synchronous bandwidth.

39. The system of claim 36, wherein said server is configured for:

associating with each said asynchronous flow a value indicative of the delay accumulated by said server in visiting said asynchronous flow in the previous rounds,

when said server visits said asynchronous flow, subtracting from said reference round time the duration of the previous round to obtain a substraction result, and

subtracting said value from said substraction result, thus computing an earliness value for the current round.

40. The system of claim 36, wherein said server is configured for:

if said earliness value is negative, storing the absolute value thereof in said value indicative of the delay accumulated, and

restraining said asynchronous flow being visited from utilizing said resource for the ongoing round.

41. The system of claim 36, wherein said server is configured for:

if said earliness value is positive, resetting to zero said value indicative of the delay accumulated, and

granting said asynchronous flow being visited said respective given time for utilizing said resource.

42. The system of claim 36, wherein said server is configured for using respective functions regulating the exploitation by said asynchronous flows of the service capacity of said resource left unexploited by said synchronous flows.

43. The system of claim 36, wherein said server is configured for making said respective given time proportional to said earliness via a proportionality factor.

44. The system of claim 43, wherein said server is configured for using as said proportionality factors proportionality factors in a range (0,1].

45. The system of claim 43, wherein said server is configured for using respective proportionality factors for said asynchronous flows.

46. The system of claim 36, wherein said server is configured for determining respective synchronous bandwidths for said synchronous flows, wherein the sum of the time intervals corresponding to said synchronous bandwidths is lower than or equal to said reference round time.

47. A communication network comprising the system of claim 36.