Nested measurement period switch algorithm for flow control of available bit rate ATM communications

• US 6,377,550 B1
• Filed: 10/27/1998
• Issued: 04/23/2002
• Est. Priority Date: 10/28/1997
• Status: Expired due to Term

• Current Assignee: Texas Instruments, Inc.
• Original Assignee: Texas Instruments, Inc.
• Inventors: Prasad, Sharat
• Primary Examiner(s): Kizou, Hassan
• Assistant Examiner(s): LOGSDON, JOSEPH B
• Application Number:
  US09/179,789
• Time in Patent Office: 1,274 Days
• Field of Search: 370/229, 370/230, 370/231, 370/232, 370/233, 370/234, 370/235, 370/236, 370/237, 370/395, 370/464, 370/465, 370/466, 370/468, 370/471, 370/236.1, 370/389, 370/395.1, 370/396, 370/397, 370/398, 370/399
• US Class Current: 370/236.1
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 2012/5635 Backpressure, e.g. for ABR
• CPC Class Codes: H04L 2012/5636 Monitoring or policing, e.g. compliance with allocated rate, corrective actions

Abstract

An Asynchronous Transfer Mode (ATM) switch (8) and method of operating the same to allocate Available Bit Rate (ABR) communications therethrough. The switch receives resource management (RM) cells over a sequence of measurement periods. A plurality of rate levels are defined, each associated with a measurement period of a corresponding duration; the measurement periods being nested. Saved and current values of the number of flows associated with each level, and saved and current values of the aggregate rates of these flows, are retained in memory. RM cells are received during the various measurement periods, and the various numbers and aggregate rates are maintained for each rate level, including the use of estimates for flows that have changed rate level. A bottleneck rate is determined as the larger of the ratio of ABR bandwidth to ABR flows, or the largest cell rate plus surplus bandwidth derived according to this sum. The bottleneck rate is then sent to the AT sources by backward-traveling RM cells, for adjustment of the ABR traffic.

Claims

1. A method of allocating data rates among a plurality of available bit rate message flows, at a communications link in a network, the link having an available bit rate bandwidth associated with available bit rate traffic, the method comprising the steps of:

responsive to receiving a resource management cell associated with one of the plurality of message flows, the resource management cell including a current cell rate value, performing the steps of;

assigning a rate level to the associated message flow, the rate level corresponding to a range of cell rates and to a corresponding one of a plurality of measurement periods of varying duration, wherein shorter duration measurement periods are associated with higher cell rates, and wherein expiration of each of the longer ones of the plurality of measurement periods coincides with the expiration of shorter ones of the plurality of measurement periods;

incrementing a current level count value for the assigned rate level;

adding the current cell rate value to a current level rate value for the assigned rate level;

responsive to the current cell rate value exceeding a maximum cell rate value, setting the maximum cell rate value to the current cell rate value and initializing a maximum cell rate count value; and

responsive to the current cell rate value equaling the maximum cell rate value, incrementing the maximum cell rate count value;

wherein each of a plurality of level memory entries is associated with one of the rate levels, and includes fields for storing the current level rate value and the current level count value, and also fields for storing a stored level rate value generated during a previous measurement period and a stored level count value also generated during a previous measurement period; and

responsive to one of the plurality of measurement periods expiring, performing the operations of;

generating a total link rate sum by adding a sum of the current level rate values for each rate level associated with an expiring measurement period with a sum of the stored level rate values for each rate level associated with a non-expiring measurement period;

generating a total link flow count of the sum of the stored level count values for each rate level;

determining a surplus bandwidth value for the link from the total link rate sum;

calculating a first bottleneck rate by adding the highest current cell rate value to the surplus bandwidth value;

generating a bottleneck rate corresponding to the larger of the first bottleneck rate and a ratio of the available bit rate bandwidth to the total link flow count; and

communicating backward-traveling resource management cells to sources of each of the plurality of available bit rate message flows, each of the backward-traveling resource management cells having an explicit rate value no higher than the bottleneck rate.

2. The method of claim 1, wherein the step of determining a surplus bandwidth value comprises:

subtracting the total link rate sum from an available bit rate bandwidth of the link; and

dividing the result of the subtracting step by the maximum cell rate count value.

3. The method of claim 1, further comprising:

after the step of generating the bottleneck rate, and for each of the rate levels associated with an expiring measurement period;

storing the current level count value as the stored level count value;

storing the current level rate value as the stored level rate value; and

resetting the current level count value and the current level rate value.

4. The method of claim 1, further comprising:

after the assigning step, determining whether a resource management cell associated with the same message flow has already been received during a current instance of the measurement period associated with the assigned rate level; and

then performing the incrementing and adding steps responsive to the determining step determining that a resource management cell associated with the same message flow has not already been received during a current instance of the measurement period associated with the assigned rate level.

5. The method of claim 4, wherein each of the plurality of level memory entries also includes a counter value;

wherein each of a plurality of flow memory entries is associated with one of the message flows, and includes a flow rate level field for storing a previous rate level for the flow, and a timestamp field, and;

wherein the determining step comprises;

comparing the timestamp field of the associated flow with the counter value of the level memory entry corresponding to the previous rate level;

and further comprising;

responsive to one of the plurality of measurement periods expiring, also incrementing the counter value of the level memory entry for each rate level associated with an expiring measurement period.

6. The method of claim 5, further comprising:

after the incrementing and adding steps, determining whether the assigned rate level equals the previous rate level; and

responsive to the determining step determining that the assigned rate level equals the previous rate level, storing the assigned rate level into the flow rate level field and storing the counter value of the level memory entry for the assigned rate level into the timestamp field.

7. The method of claim 6, further comprising:

responsive to the determining step determining that the assigned rate level does not equal the previous rate level, performing the steps of;

decrementing the value of the stored level rate count associated with the previous rate level; and

reducing the stored level rate value associated with the previous rate level.

8. The method of claim 7, wherein the reducing step comprises:

responsive to the assigned rate level corresponding to higher cell rates than the previous rate level, subtracting a minimum rate level of the range of cell rates corresponding to the next faster rate level than the previous rate level, from the stored level rate value; and

responsive to the assigned rate level corresponding to lower cell rates than the previous rate level, subtracting a minimum rate level of the range of cell rates corresponding to the previous rate level, from the stored level rate value.

9. A switch for routing cell-based communications received at one of a plurality of links, comprising:

a plurality of physical layer interfaces, each associated to and interfacing with one of the plurality of links;

a plurality of line interfaces, each coupled to one of the plurality of physical layer interfaces;

switch fabric, coupled to the plurality of line interfaces, for routing communications thereamong; and

a memory, for storing a plurality of level memory entries, each level memory entry associated with each of a plurality of rate levels, each of the plurality of rate levels corresponding to a range of cell rates and to a corresponding one of a plurality of measurement periods of varying duration, wherein longer duration measurement periods are associated with higher cell rates, and wherein expiration of each of the longer ones of the plurality of measurement periods coincides with the expiration of shorter ones of the plurality of measurement periods, each level memory entry including fields for storing the current level rate value and the current level count value, and also fields for storing a stored level rate value generated during a previous measurement period and a stored level count value also generated during a previous measurement period;

a control processor, coupled to the memory, for allocating data rates among a plurality of available bit rate message flows received over the plurality of links, wherein each of the plurality of links has an available bit rate bandwidth associated with available bit rate traffic, by performing a sequence of operations, for each link, comprising;

responsive to receiving a resource management cell associated with one of the plurality of message flows, the resource management cell including a current cell rate value, performing the operations of;

assigning a rate level to the associated message flow, based upon the current cell rate;

incrementing the current level count value for the assigned rate level;

adding the current cell rate value to the current level rate value for the assigned rate level;

responsive to the current cell rate value exceeding a maximum cell rate value, setting the maximum cell rate value to the current cell rate value and initializing a maximum cell rate count value; and

responsive to the current cell rate value equaling the maximum cell rate value, incrementing the maximum cell rate count value; and

responsive to one of the plurality of measurement periods expiring, performing the operations of;

generating a total link rate sum by adding a sum of the current level rate values for each rate level associated with an expiring measurement period with a sum of the stored level rate values for each rate level associated with a non-expiring measurement period;

generating a total link flow count of the sum of the stored level count values for each rate level;

determining a surplus bandwidth value for the link from the total link rate sum;

calculating a first bottleneck rate by adding the highest current cell rate value to the surplus bandwidth value;

generating a bottleneck rate corresponding to the larger of the first bottleneck rate and a ratio of the available bit rate bandwidth to the total link flow count; and

communicating backward-traveling resource management cells to sources of each of the plurality of available bit rate message flows, each of the backward-traveling resource management cells having an explicit rate value no higher than the bottleneck rate.

10. The switch of claim 9, wherein the operation of determining a surplus bandwidth value comprises:

subtracting the total link rate sum from an available bit rate bandwidth of the link; and

dividing the result of the subtracting operation by the maximum cell rate count value.

11. The switch of claim 9, wherein the control processor is further programmed to perform the operations of:

after the operation of generating the bottleneck rate, and for each of the rate levels associated with an expiring measurement period;

storing the current level count value as the stored level count value;

storing the current level rate value as the stored level rate value; and

resetting the current level count value and the current level rate value.

12. The switch of claim 9, wherein the control processor is further programmed to perform the operations of:

after the assigning operation, determining whether a resource management cell associated with the same message flow has already been received during a current instance of the measurement period associated with the assigned rate level; and

then performing the incrementing and adding operations responsive to the determining operation determining that a resource management cell associated with the same message flow has not already been received during a current instance of the measurement period associated with the assigned rate level.

13. The switch of claim 12, wherein each of the plurality of level memory entries also includes a counter value;

wherein the memory further comprises a plurality of flow memory entries, each associated with one of the message flows, and each including a flow rate level field for storing a previous rate level for the flow, and a timestamp field, and;

wherein the determining operation comprises;

comparing the timestamp field of the associated flow with the counter value of the level memory entry corresponding to the previous rate level;

and wherein the control processor is further programmed to perform the operation of;

responsive to one of the plurality of measurement periods expiring, also incrementing the counter value of the level memory entry for each rate level associated with an expiring measurement period.

14. The switch of claim 13, wherein the control processor is further programmed to perform the operations of:

after the incrementing and adding operations, determining whether the assigned rate level equals the previous rate level; and

responsive to the determining operation determining that the assigned rate level equals the previous rate level, storing the assigned rate level into the flow rate level field and storing the counter value of the level memory entry for the assigned rate level into the timestamp field.

15. The switch of claim 14, wherein the control processor is further programmed to perform the operations of:

responsive to the determining operation determining that the assigned rate level does not equal the previous rate level, performing the operations of;

decrementing the value of the stored level rate count associated with the previous rate level; and

reducing the stored level rate value associated with the previous rate level.

16. The switch of claim 15, wherein the reducing operation comprises:

responsive to the assigned rate level corresponding to higher cell rates than the previous rate level, subtracting a minimum rate level of the range of cell rates corresponding to the next faster rate level than the previous rate level, from the stored level rate value; and

responsive to the assigned rate level corresponding to lower cell rates than the previous rate level, subtracting a minimum rate level of the range of cell rates corresponding to the previous rate level, from the stored level rate value.