Simplified switch algorithm for flow control of available bit rate ATM communications

• US 6,381,216 B1
• Filed: 10/27/1998
• Issued: 04/30/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): Vincent, David R.
• Assistant Examiner(s): NGUYEN, VAN KIM T
• Application Number:
  US09/179,183
• Time in Patent Office: 1,281 Days
• Field of Search: 370/229, 370/231-233, 370/236, 370/236.1, 370/389, 370/395.1, 370/395.7, 370/395.43
• US Class Current: 370/236.1
• CPC Class Codes: H04L 2012/5635 Backpressure, e.g. for ABR
• CPC Class Codes: H04L 49/3081 ATM peripheral units, e.g. policing, insertion or extraction
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

An Asynchronous Transfer Mode (ATM) switch (8) and method of operating the same to allocate Available Bit Rate (ABR) communications therethrough is disclosed. The switch (8) receives resource management (RM) cells over a sequence of measurement periods. Within each measurement period, the message flow associated with a received RM cell is identified, and a flag (SEEN₁) in a memory array (22) is interrogated to determine whether an RM cell for the message flow has yet been received in the measurement period. If not, a sum value (SUM) is updated with the current cell rate (CCR) of the flow and, if the CCR of the flow is equal to or greater than the highest cell rate (r₁) yet measured in the measurement period, a highest cell rate field (r₁) in memory and a count (m₁) of flows having the highest cell rate are updated. Upon completion of the measurement period, a bottleneck rate is calculated by the switch (8) as the larger of the ratio of ABR bandwidth to ABR flows, or the largest cell rate (r₁) plus the surplus bandwidth; the surplus bandwidth is determined by subtracting the cell rate sum (SUM) from the ABR bandwidth, and dividing by the number (m₁) of flows having the highest cell rate. The bottleneck rate is then sent to the ATM 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:

receiving a resource management cell from each of the plurality of message flows, the resource management cell including a current cell rate value;

identifying a highest current cell rate value from the resource management cells associated with the plurality of message flows;

identifying the number of flows having the highest current cell rate value;

determining a surplus bandwidth value for the link;

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 number of available bit rate message flows in the plurality of available bit rate message flows; 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:

identifying the number of flows having the highest current cell rate value;

adding the current cell rates of the plurality of message flows to produce a rate sum;

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

dividing the result of the subtracting step by the number of flows having the highest data rate.

3. The method of claim 2, further comprising:

initializing a first array of flags in a memory, each of the plurality of flags corresponding to one of the plurality of available bit rate message flows;

after the receiving step for one of the resource management cells, and responsive to the flag associated with the corresponding one of the plurality of available bit rate message flows not being set, then setting the associated flag and performing the identifying and determining steps; and

responsive to the flag associated with the corresponding one of the plurality of available bit rate message flows being set, not performing the identifying and determining steps.

4. The method of claim 3, wherein the receiving, identifying, and determining steps are performed over a measurement period;

and further comprising;

after expiration of the measurement period, resetting the first array of flags.

5. The method of claim 4, wherein the setting step is performed relative to the first array over a first instance of the measurement period;

wherein the resetting step is performed after expiration of the first instance of the measurement period;

further comprising;

initializing a second array of flags in a memory, each of the plurality of flags corresponding to one of the plurality of available bit rate message flows;

then performing the receiving, setting, identifying, and determining steps over a second instance of the measurement period, wherein the setting step is performed relative to the second array over the second instance of the measurement period; and

after expiration of the second instance of the measurement period, resetting the second array of flags.

6. The method of claim 5, wherein the step of resetting the first array of flags is performed during the second instance of the measurement period.

7. The method of claim 2, wherein the step of determining a surplus bandwidth value is performed after receiving each resource management cell, and comprises the steps of:

comparing the current cell rate value of the received resource management cell with the highest current cell rate value and, responsive to the current cell rate value of the received resource management cell being higher than the highest current cell rate value, replacing the highest current cell rate value with the current cell rate value of the received resource management cell and setting, to the value one, a counter for storing a value corresponding to the number of flows having the highest current cell rate value;

responsive to the current cell rate value of the received resource management cell being equal to the highest current cell rate value, incrementing the value stored in the counter; and

adding the current cell rate value to a current value of the rate sum.

8. 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 control processor, 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 the steps of;

responsive to the line interface receiving a resource management cell from the plurality of message flows, identifying a highest current cell rate value from the resource management cells associated with the plurality of message flows;

identifying the number of flows having the highest current cell rate value;

determining a surplus bandwidth value for the link;

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 number of available bit rate message flows in the plurality of available bit rate message flows; and

controlling the line interface associated with the link to communicate 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.

9. The switch of claim 8, wherein the control processor is programmed to determine the surplus bandwidth value for the link by performing the operations of:

identifying the number of flows having the highest current cell rate value;

adding the current cell rates of the plurality of message flows to produce a rate sum;

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

dividing the result of the subtracting step by the number of flows having the highest data rate.

10. The switch of claim 8, further comprising:

a memory, coupled to the control processor, and arranged as a plurality of pairs of arrays, each array pair associated with one of the plurality of links, each array in the pair including a plurality of flags, each flag associated with one of the plurality of message flows communicated by its associated link;

and wherein the control processor is programmed to perform the identifying and determining steps for each link over first and second measurement periods, and wherein the sequence of operations further comprises;

initializing the plurality of flags in the first array;

responsive to receiving one of the resource management cells in the first measurement period, and responsive to the flag in the first array associated with the corresponding one of the plurality of available bit rate message flows not being set, then setting the associated flag and performing the identifying and determining steps;

responsive to the flag in the first array associated with the corresponding one of the plurality of available bit rate message flows being set, not performing the identifying and determining steps; and

after expiration of the first measurement period, resetting the plurality of flags in the first array;

initializing the plurality of flags in the second array;

responsive to receiving one of the resource management cells in the second measurement period, and responsive to the flag in the second array associated with the corresponding one of the plurality of available bit rate message flows not being set, then setting the associated flag and performing the identifying and determining steps;

responsive to the flag in the second array associated with the corresponding one of the plurality of available bit rate message flows being set, not performing the identifying and determining steps; and

after expiration of the second measurement period, resetting the plurality of flags in the second array.

11. The switch of claim 10, wherein the control processor resets the flags in the first array during the second measurement period.