Method to share available bandwidth, a processor realizing such a method, and a scheduler, an intelligent buffer and a telecommunication system including such a processor

• US 6,469,982 B1
• Filed: 07/29/1999
• Issued: 10/22/2002
• Est. Priority Date: 07/31/1998
• Status: Expired due to Term

• Current Assignee: Alcatel SA (Nokia Corporation)
• Original Assignee: Alcatel SA (Nokia Corporation)
• Inventors: Henrion, Michel André Robert, Desmet, Emmanuel, Verkinderen, Johan Gabriël August, Bonaventure, Olivier, Barri, Peter Irma August
• Primary Examiner(s): NGO, RICKY QUOC
• Application Number:
  US09/363,039
• Time in Patent Office: 1,181 Days
• Field of Search: 370/230, 370/235, 370/395.1, 370/395.4, 370/395.41, 370/395.42, 370/395.43, 370/465, 370/468, 370/437, 370/439, 370/230.1, 370/231, 370/232, 370/233, 370/234, 370/235.1, 370/236
• US Class Current: 370/230
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 2012/5632 Bandwidth allocation
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

The method shares available bandwidth on a common link in a communication network among a plurality of data flows which are transmitted via the common link. The method is used by a processor and includes sharing reserved bandwidth included in the available bandwidth among the plurality of data flows, and sharing unreserved bandwidth among the plurality of data flows according to a respective unreserved data packet share which is associated to each one of the plurality of data flows. The unreserved bandwidth is included in the available bandwidth in excess of the reserved bandwidth. The sharing of the unreserved bandwidth includes associating to one of the plurality of data flows a respective adaptable administrative weight and determining the respective unreserved data packet share which is associated to the one data flow as a function of its respective adaptable administrative weight.

Claims

1. A method for sharing available bandwidth on a common link in a communication network among a plurality of data flows being transmitted via said common link, said method executed by a processor, wherein said method comprises:

sharing reserved bandwidth included in said available bandwidth among said plurality of data flows, and

sharing unreserved bandwidth among said plurality of data flows according to a respective unreserved data packet share being associated to each one of said plurality of data flows, said unreserved bandwidth being included in said available bandwidth in excess of said reserved bandwidth,

wherein sharing said unreserved bandwidth further comprises associating to at least one of said plurality of data flows a respective adaptable administrative weight and determining said respective unreserved data packet share being associated to said at least one data flow based on said respective adaptable administrative weight.

2. The method for sharing available bandwidth according to claim 1, wherein said method further comprises determining said at least one data flow as an active one of said plurality of data flows having at least one data packet in a buffer coupled to said processor.

3. The method for sharing available bandwidth according to claim 1, wherein said processor controls a buffer that stores received data packets, and said sharing of reserved bandwidth further comprises a first process of sharing guaranteed bandwidth, up to an amount of reserved bandwidth predefined for each data flow and included in said available bandwidth, and said sharing of unreserved bandwidth further comprises a second process of sharing non-guaranteed bandwidth among said plurality of data flows according to a respective non-guaranteed bandwidth share, said non-guaranteed bandwidth share comprising the unreserved bandwidth as well as the actually unused part of said reserved bandwidth, said unreserved bandwidth being included in said available bandwidth in excess of said reserved bandwidth, and in that said second process of sharing said non-guaranteed bandwidth comprises associating said respective adaptable administrative weight to at least one of said plurality of data flows, said respective non-guaranteed bandwidth share being determined as a function of said respective adaptable administrative weight associated to said at least one data flow.

4. The method for sharing available bandwidth according to claim 3, wherein at each service time moment, said method further comprises:

determining whether, for at least each active data flow of said plurality of data flows, a respective entitled reserved bandwidth share of said reserved bandwidth has been reached or not; and

selecting, when at least one active data flow has not reached its respective entitled reserved bandwidth share, one of said plurality of active data flows not having reached its entitled reserved bandwidth share, whereby guaranteed bandwidth is granted at said service time moment, and

selecting, when each one of said plurality of active data flows has reached its respective entitled reserved bandwidth share, one of said plurality of active data flows, whereby non-guaranteed bandwidth is granted at said service time moment.

5. The method for sharing available bandwidth according to claim 3, wherein said method further comprises:

associating to each one of said plurality of data flows a respective service grant counter;

initializing said service grant counter at each start of a predefined time period to a respective predefined initial credit value which is derived from said reserved bandwidth as being equal to the corresponding number of entitled service grants for reserved bandwidth during said predefined time period;

updating, at each service time moment, the respective service grant counter that is associated to the data flow being served at said service time moment, until a respective predefined end value is reached for said respective service grant counter; and

detecting that an entitled respective reserved bandwidth share of a data flow is reached when said associated service grant counter reached said respective predefined end value.

6. The method for sharing available bandwidth according to claim 5, wherein, when successively serving complete packets of variable length, said updating of said respective service grant counter is performed by counting a number of service grants in proportion to the length of the served packet.

7. The method for sharing available bandwidth according to claim 5, wherein said predefined time period has the same duration for all data flows.

8. The method for sharing available bandwidth according to claim 7, wherein said predefined time period of same duration is synchronized for all data flows, so that said initializing of said service grant counter of each data flow at each start of the predefined time period is performed simultaneously for all service grant counters of all data flows.

9. The method for sharing available bandwidth according to claim 7, wherein said predefined time period of same duration is not synchronized for all data flows, so that said initializing of said service grant counter of each data flow at each start of the said predefined time period is not performed simultaneously for all service grant counters of all data flows.

10. The method for sharing available bandwidth according to claim 5, wherein said predefined time period has a specific duration for each data flow.

11. The method for sharing available bandwidth according to claim 4, wherein said determining of whether a respective entitled reserved bandwidth share of said reserved bandwidth has been reached or not for at least each active data flow includes a common guaranteed bandwidth share data flow counter, wherein said common guaranteed bandwidth share data flow counter:

records the current number of active data flows not having reached their said respective entitled reserved bandwidth share of said reserved bandwidth for a predefined time period;

decrements each time an active data flow has reached its said respective entitled reserved bandwidth share, or decrements each time an active data flow becomes inactive even if it has not yet reached its said respective entitled reserved bandwidth share;

increments each time a data flow becomes active while it was not previously active and had not yet reached its said respective entitled reserved bandwidth share, or increments each time an active data flow is newly detected as having not yet reached its said respective entitled reserved bandwidth share while it was previously considered as having reached the latter;

and indicates, at each said service time moment, whether guaranteed bandwidth is to be granted to an active data flow not having reached its entitled reserved bandwidth share when said common counter is not empty, or non-guaranteed bandwidth is to be granted to an active data flow when said common counter is empty.

12. The method for sharing available bandwidth according to claim 4, wherein selecting one data flow to be served at each service time moment further comprises:

determining a guaranteed bandwidth schedule parameter for at least each active data flow which has not reached its respective entitled reserved bandwidth share, and providing thereby to each one said guaranteed bandwidth schedule parameter, each guaranteed bandwidth schedule parameter being determined as a function of its said reserved bandwidth;

determining a non-guaranteed schedule parameter for at least each active data flow which has reached its respective entitled reserved bandwidth share, and providing thereby to each one said non-guaranteed schedule parameter, each non-guaranteed schedule parameter being determined as a function of its respective adaptable administrative weight;

performing scheduling on the basis of said guaranteed bandwidth schedule parameter when guaranteed bandwidth is granted to an active data flow having not yet reached its entitled respective reserved bandwidth share;

performing scheduling on the basis of said non-guaranteed schedule parameters when non-guaranteed bandwidth is granted to an active data flow having reached its entitled respective reserved bandwidth share; and

selecting, upon reception by said processor of either a granting guaranteed bandwidth signal or a granting non-guaranteed bandwidth signal, according to predefined rules and conditions, a data flow which is detected as being respectively, either the one having lowest value among said guaranteed bandwidth schedule parameter or the one having lowest value among non-guaranteed schedule parameters.

13. The method for sharing available bandwidth according to claim 12, wherein said guaranteed bandwidth schedule parameter is only used for those data flows which have not reached their respective entitled reserved bandwidth share, said non-guaranteed schedule parameter is only used for those data flows which have reached their respective entitled reserved bandwidth share, and each data flow is scheduled at any point in time by using one single schedule parameter in an exclusive way, being either said guaranteed bandwidth schedule parameter or said non-guaranteed schedule parameter.

14. The method for sharing available bandwidth according to claim 4, wherein selecting one data flow to be served at each service time moment further comprises:

maintaining a guaranteed bandwidth data flow circular list of those active data flows which have not reached their respective entitled reserved bandwidth share;

determining a non-guaranteed schedule parameter for at least each active data flow which has reached its respective entitled reserved bandwidth share, and providing thereby to each one said non-guaranteed schedule parameter, each non-guaranteed schedule parameter being determined as a function of its said respective adaptable administrative weight;

performing scheduling on the basis of said guaranteed bandwidth data flow circular list when guaranteed bandwidth is granted to an active data flow having not yet reached its entitled respective reserved bandwidth share;

performing scheduling on the basis of said non-guaranteed schedule parameters when non-guaranteed bandwidth is granted to an active data flow having reached its entitled respective reserved bandwidth share; and

selecting, upon reception by said processor either a granting guaranteed bandwidth signal or a granting non-guaranteed bandwidth signal, according to predefined rules and conditions, a data flow which is detected as being respectively either the one at the head of said guaranteed bandwidth data flow circular list or the one having lowest value among said non-guaranteed schedule parameters.

15. The method for sharing available bandwidth according to claim 4, wherein selecting one data flow to be served at each service time moment further comprises:

determining a guaranteed bandwidth schedule parameter for at least each active data flow which has not reached its respective entitled reserved bandwidth share, and providing thereby to each one said guaranteed bandwidth schedule parameter, each guaranteed bandwidth schedule parameter being determined as a function of its said reserved bandwidth;

associating to each one of said plurality of data flows a respective extra service grant counter;

initializing said extra service grant counter of each data flow which has reached its respective reserved bandwidth share, to a respective predefined initial extra service grant credit value which is proportional to said respective adaptable administrative weight, this initialization operation being performed each time all said extra service grant counters have reached a respective predefined end value;

updating, at each service time moment, the respective extra service grant counter that is associated to the data flow being served at said service time moment, until a respective predefined end value is reached for said respective extra service grant counter, the total number of possible updates for an extra service grant counter being in proportion to said respective adaptable administrative weight of said associated data flow;

maintaining a non-guaranteed bandwidth data flow circular list of those active data flows which have reached their respective entitled reserved bandwidth share;

performing scheduling on the basis of said guaranteed bandwidth schedule parameters when guaranteed bandwidth is granted to an active data flow having not yet reached its entitled respective reserved bandwidth share;

performing scheduling on the basis of said non-guaranteed bandwidth data flow circular list when non-guaranteed bandwidth is granted to an active data flow having reached its entitled respective reserved bandwidth share; and

selecting, upon reception by said processor either a granting guaranteed bandwidth signal or a granting non-guaranteed bandwidth signal, according to predefined rules and conditions, a data flow which is detected as being respectively either the one having lowest value among said guaranteed bandwidth schedule parameters or the one at the head of said non-guaranteed bandwidth data flow circular list.

16. The method for sharing available bandwidth according to claim 4, wherein selecting one data flow to be served at each service time moment further comprises:

maintaining a guaranteed bandwidth data flow circular list of those active data flows which have not reached their respective entitled reserved bandwidth share;

associating to each one of said plurality of data flows a respective extra service grant counter;

initializing said extra service grant counter of each data flow which has reached its respective reserved bandwidth share, to a respective predefined initial extra service grant credit value which is proportional to said respective adaptable administrative weight, this initialization operation being performed each time all said extra service grant counters have reached a respective predefined end value;

updating, at each service time moment, the respective extra service grant counter that is associated to the data flow being served at said service time moment, until a respective predefined end value is reached for said extra respective service grant counter, the total number of possible updates for an extra service grant counter being in proportion to said respective adaptable administrative weight of said associated data flow;

maintaining a non-guaranteed bandwidth data flow circular list of those active data flows which have reached their respective entitled reserved bandwidth share;

performing scheduling on the basis of said guaranteed bandwidth data flow circular list when guaranteed bandwidth is granted to an active data flow having not yet reached its entitled respective reserved bandwidth share;

performing scheduling on the basis of said non-guaranteed bandwidth data flow circular list when non-guaranteed bandwidth is granted to an active data flow having-reached its entitled respective reserved bandwidth share; and

selecting, upon reception by said processor either a granting guaranteed bandwidth signal or a granting non-guaranteed bandwidth signal, according to predefined rules and conditions, a data flow which is detected as being respectively either the one at the head of said guaranteed bandwidth data flow circular list or the one at the head of said non-guaranteed bandwidth data flow circular list.

17. The method for sharing available bandwidth according to claim 15, wherein, when successively serving complete packets of variable length, said updating of said respective extra service grant counter is performed by counting a number of service grants in proportion to the length of the served packet.

18. The method for sharing available bandwidth according to claim 15, wherein said respective service grant counter is only used for those data flows which have not reached their respective entitled reserved bandwidth share, said respective extra service grant counter is only used for those data flows which have reached their respective entitled reserved bandwidth share, and a counter associated to each data flow is used, either acting as said respective service grant counter for a data flow which has not yet reached its entitled respective reserved bandwidth share, or acting as said respective extra service grant counter for a data flow which has reached its entitled respective reserved bandwidth share.

19. A processor to share available bandwidth on a common link in a communication network among a plurality of data flows being transmitted via said common link, said processor comprising:

a first processing means to share reserved bandwidth included in said available bandwidth among said plurality of data flows according to a respective reserved data packet share being associated to each one of said plurality of data flows,

a second processing means to share unreserved bandwidth among said plurality of data flows according to a respective unreserved data packet share being associated to each one of said plurality of data flows, said unreserved bandwidth being included in said available bandwidth in excess of said reserved bandwidth,

associating means to associate to at least one of said plurality of data flows an adaptable administrative weight, and that said second processing means comprises second determining means to determine said respective unreserved data packet share being associated to said at least one data flow in function of said respective adaptable administrative weight, and

a control means to control said first processing means and said second processing means and to provide a shared bandwidth signal being a measure for said respective reserved data packet share and said respective unreserved data packet share.

20. The processor to share available bandwidth according to claim 19, wherein said processor further comprises third determining means to determine said at least one data flow as an active one of said plurality of data flows having at least one data packet in a buffer coupled to said processor.

21. The processor to share available bandwidth according to claim 19, wherein said first processing means comprises:

first determining means to determine said respective reserved data packet share in function of a minimum data packet rate being associated to said each one data flow and which guarantees for said each one data flow a minimum guaranteed bandwidth, and

wherein said control means activates said second processing means in the event when said minimum guaranteed bandwidth being respected by said first processing means.

22. The processor according to claim 19, wherein said processor supports a guaranteed frame rate service in an asynchronous transfer mode telecommunication system.

23. The processor according to claim 19, wherein said processor supports a variable length packet telecommunication system.

24. A scheduler in a communication network to share available bandwidth on a common link among a plurality of data flows being transmitted via said common link, said scheduler comprising:

a buffer to sort incoming data packets of said plurality of data flows provided at an at least one input of said scheduler, according to its associated data flow, into a plurality of buffer queues being included in said buffer and each one being associated to one of said plurality of data flows, and to provide thereby a plurality of sorted data packets,

a selection means to select one of said plurality of sorted data packets in order to transmit said one sorted data packet on said common link,

wherein said scheduler further comprises a processor according to claim 19, said processor being coupled to said selection means in order to control said selection according to said shared bandwidth signal.

25. An intelligent buffer in a communication network to share available bandwidth on a common link among a plurality of data flows being transmitted via said common link, said intelligent buffer comprising:

a decision means to decide whether to accept or to discard an incoming data packet of one of said plurality of data flows provided at an at least one input of said intelligent buffer, and to provide thereby in the event when said incoming data packet is accepted, an accepted data packet,

a buffer means being coupled to said decision means to store said accepted data packet and to transmit said accepted data packet on said common link, wherein said intelligent buffer further comprises a processor according to claim 19, said processor being coupled to said decision means in order to control said decision according to said shared bandwidth signal.

26. A telecommunication system characterized in that said telecommunication system comprising at least one processor as described in claim 19.

30. The processor according to claim 19, wherein said processor supports a guaranteed frame rate service in an asynchronous transfer mode telecommunication system.

27. A processor to share available bandwidth on a common link in a communication network among a plurality of data flows being transmitted via said common link, said processor comprising:

a first processor to share reserved bandwidth included in said available bandwidth among said plurality of data flows according to a respective reserved data packet share being associated to each one of said plurality of data flows,

a second processor to share unreserved bandwidth among said plurality of data flows according to a respective unreserved data packet share being associated to each one of said plurality of data flows, said unreserved bandwidth being included in said available bandwidth in excess of said reserved bandwidth,

a memory that associates to at least one of said plurality of data flows an adaptable administrative weight, and that said second processor comprises an unreserved packet share determiner circuit that determines said respective unreserved data packet share being associated to said at least one data flow in function of said respective adaptable administrative weight, and

a controller that controls said first processor and said second processor and to provide a shared bandwidth signal being a measure for said respective reserved data packet share and said respective unreserved data packet share.

28. The processor to share available bandwidth according to claim 27, wherein said processor further comprises an active flow determiner circuit that determines said at least one data flow as an active one of said plurality of data flows having at least one data packet in a buffer coupled to said processor.

29. The processor to share available bandwidth according to claim 27, wherein said first processor comprises:

reserved packet share determiner circuit that determines said respective reserved data packet share in function of a minimum data packet rate being associated to said each one data flow and which guarantees for said each one data flow a minimum guaranteed bandwidth, and

wherein said control means activates said second processor in the event when said minimum guaranteed bandwidth being respected by said first processor.

31. The processor according to claim 27, wherein said processor supports a variable length packet telecommunication system.

32. A scheduler in a communication network to share available bandwidth on a common link among a plurality of data flows being transmitted via said common link, said scheduler comprising:

a buffer to sort incoming data packets of said plurality of data flows provided at an at least one input of said scheduler, according to its associated data flow, into a plurality of buffer queues being included in said buffer and each one being associated to one of said plurality of data flows, and to provide thereby a plurality of sorted data packets,

a selector to select one of said plurality of sorted data packets in order to transmit said one sorted data packet on said common link,

wherein said scheduler further comprises a processor according to claim 27, said processor being coupled to said selector in order to control said selection according to said shared bandwidth signal.

33. An intelligent buffer in a communication network to share available bandwidth on a common link among a plurality of data flows being transmitted via said common link, said intelligent buffer comprising:

a decision circuit that decides whether to accept or to discard an incoming data packet of one of said plurality of data flows provided at an at least one input of said intelligent buffer, and to provide thereby in the event when said incoming data packet is accepted, an accepted data packet, and

a buffer being coupled to said decision circuit to store said accepted data packet and to transmit said accepted data packet on said common link,

wherein said intelligent buffer further comprises a processor according to claim 27, said processor being coupled to said decision means in order to control said decision according to said shared bandwidth signal.

34. A telecommunication system characterized in that said telecommunication system comprising at least one processor as described in claim 27.