Simplified calculation of cell transmission rates in a cell based netwook

• US 5,812,527 A
• Filed: 04/01/1996
• Issued: 09/22/1998
• Est. Priority Date: 04/01/1996
• Status: Expired due to Term

• Current Assignee: Google Technology Holdings LLC (Alphabet Inc.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Ramakrishnan, Krishnan, Gun, Levent, Kline, Richard B.
• Primary Examiner(s): Hsu, Alpus H.
• Application Number:
  US08/625,116
• Time in Patent Office: 904 Days
• Field of Search: 370/230, 370/231, 370/232, 370/233, 370/234, 370/235, 370/236, 370/252, 370/253, 370/395, 370/396, 370/397, 370/409, 370/412, 370/465, 370/545, 395/200.16, 395/200.13
• US Class Current: 370/232
• CPC Class Codes: H04L 2012/5635 Backpressure, e.g. for ABR
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 49/255 Control mechanisms for ATM switching fabrics
• 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

A cell based network (100) for transmitting ATM user cells (118), including ABR data cells (118_D) and forward control, or RM, cells (118_FRM) at predetermined cell rates from at least one user source (102) in a virtual connection (VC, 110) through at least one ATM switch (120) and at least one transmission link (130) in the network to at least one user destination (104), employs a method and apparatus for controlling a user source (102) transmission cell rate in the presence of congestion in the VC (110). The calculation of a Fair Share cell transmission rate is written into a backward control, or RM, cell (118_BRM) optionally takes place only in the presence of congestion at an ATM Switch (120). The calculation of the Fair_-- Share value is simplified and calculation time is shortened by changing the number of active ABR VCs (N_ABR) to a factor of two (E_NABR) and dividing the maximum cell transmission rate by E_NABR.

Claims

1. In a cell based network for transmitting user cells, including data cells and control cells defining an explicit rate, at predetermined cell rates in a forward direction from at least one user source to at least one user destination in a virtual connection through a transmission path including at least one switch and at least one egress transmission link coupled to the switch by an egress physical port, each switch and physical port of each transmission link having limited cell transmission resources and being susceptible to congestion of multiple virtual connections made therethrough, a method of reducing such congestion comprising the steps of:

establishing a programmed cell rate for each egress physical port coupled to the switch;

upon the arrival of a control cell at the switch, calculating a user source fair share cell transmission rate by;

determining a count of a number of virtual connections through the egress physical port coupled to the switch;

quantizing the count of the number of virtual connections by incrementing the count of the number of virtual connections to a next higher power of two, thereby producing a quantized count; and

determining a fair share cell transmission rate as a function of the programmed cell rate and the quantized count; and

changing the explicit rate in the control cell arriving at the switch to the fair share cell transmission rate.

2. The method of claim 1 further comprising the steps of:

determining, at the switch, the presence of congestion of the limited resources of any one of the switch and the at least one transmission link coupled thereto; and

selectively initiating, in response to the step of determining, the step of calculating the user source fair share cell transmission rate when congestion is present.

3. The method of claim 1 wherein said cell based network operates to transmit said user cells in a bi-directional manner in forward and backward directions according to the steps of:

at each user source, periodically transmitting the user cells including control cells and data cells to each transmission link and switch in the virtual connection in the forward direction to the user destination, the control cells having an explicit rate field;

at each switch, and during the transmission of user cells in the forward direction, determining whether congestion is present in virtual connections in the switch and in physical ports coupled thereto;

at each destination, sending control cells as backward control cells in a backward direction of the virtual connection through said switch and physical ports to said user source;

at each switch, and only in the presence of congestion, changing an explicit rate field value for those backward control cells related to congested virtual connections; and

at the user sources, and upon return of the backward control cells, changing a present cell transmission rate to the explicit rate field value.

4. The method of claim 1 wherein the step of determining a count comprises the step of dynamically measuring active virtual connections (VCs), and wherein the step of determining the fair share cell transmission rate further comprises the step of dividing the maximum cell transmission rate by the number of active VCs.

5. The method of claim 1 wherein the step of determining the fair share cell transmission rate further comprises the step of dividing the programmed cell rate by the quantized count in a manner that does not require a floating point calculation.

6. In a cell based network for transmitting user cells, including data cells and control cells defining an explicit rate, at predetermined cell rates in a forward direction from at least one user source to at least one user destination in a virtual connection through a transmission path including at least one switch and at least one egress transmission link coupled to the switch by an egress physical port, each switch and physical port of each transmission link having limited cell transmission resources and being susceptible to congestion of multiple virtual connections made therethrough, a method of reducing such congestion comprising the steps of:

establishing a programmed cell rate for each egress physical port coupled to the switch;

determining a count of a number of virtual connections through the egress physical port coupled to the switch, the step of determining comprising;

providing an indicia of VC activity in the egress physical port; and

altering the indicia of VC activity based on whether a first VC is active; and

upon the arrival of a control cell at the switch, calculating a user source fair share cell transmission rate, the step of calculating comprising;

quantizing the count of the number of virtual connections by incrementing the count of the number of virtual connections to a next higher power of two thereby producing a quantized count; and

determining the fair share cell transmission rate as a function of the programmed cell rate and the quantized count.

7. The method of claim 6 wherein the indicia comprises a counter, and wherein said step of altering the indicia comprises the step of incrementing the counter when the first VC is found to be active.

8. The method of claim 7, wherein the indicia comprises a counter, and wherein said step of altering the indicia comprises the step of decrementing the counter when the first VC is found to be idle.

9. The method of claim 6 wherein the indicia comprises a flag, and wherein said step of altering the indicia comprises the step of setting the flag when the first VC is found to be active.

10. The method of claim 7, wherein the indicia comprises a flag, and wherein said step of altering the indicia comprises the step of clearing the flag when the first VC is found to be idle.

11. In an Asynchronous Transfer Mode (ATM) information network for serially transmitting ATM user cells of ATM traffic categories, including Available Bit Rate (ABR) traffic comprising ABR user data cells and Resource Management (RM) cells having Explicit Rate (ER) fields, each ATM user cell having a defined header with identification data defining a Virtual Connection (VC) from an ATM traffic user source (SES) in a transmission path including one or more ATM switches and interconnecting transmission links having physical ports coupled with the ATM Switches, to an ATM user destination (DES) at an actual cell transmission rate established at the SES, wherein congestion of VCs in a transmission path may occur, a method of controlling such congestion by reducing the actual cell transmission rate of ABR traffic to a Fair Share cell transmission rate comprising the steps of:

transmitting data and RM cells of ABR traffic from the SES in a forward direction in a VC through the transmission path at the cell transmission rate;

at each ATM switch in the transmission path of the VCs in the forward direction,

determining whether egress or ingress congestion exists in the ATM switch, and providing an indication of congestion in response thereto; and

determining a programmed cell rate of the physical port of the VC having the indication of congestion;

sending backward RM cells of ABR traffic in a backward direction from the DES to each ATM switch in the transmission path of each VC;

on receipt of a backward RM cell at each ATM switch in the transmission path of the VC, responding to the indication of congestion by;

determining a count of the number of VCs through the egress physical port coupled to the ATM Switch; and

quantizing the count of the number of VCs to an incremented count of a power of two;

determining a Fair Share cell transmission rate as a function of the programmed cell rate of the egress physical port used in the VC and the incremented count;

writing the Fair Share cell transmission rate in the ER fields of the backward RM cells; and

sending the backward RM cells of the ABR traffic in the backward direction from each such ATM switch in the transmission path of each VC toward the SES; and

at the SES, changing the actual cell transmission rate of ABR traffic generated by the SES to the Fair Share cell transmission rate.

12. The method of claim 11 further comprising the step of:

comparing the explicit rate in the backward RM cells received at the switch to the Fair Share cell transmission rate prior to changing the explicit rate; and

selectively changing the explicit rate, responsive to the step of comparing, when the Fair Share transmission rate is found to be less than the explicit rate.

13. The method of claim 11 wherein the step of determining the Fair Share cell transmission rate further comprises the step of dividing the maximum cell transmission rate by the incremented count.

14. The method of claim 11 wherein said step of quantizing the count of the number of VCs and the step of determining the Fair Share cell transmission rate are performed substantially simultaneously using a single iterative loop.

15. The method of claim 14, wherein an exponent of the actual cell transmission rate is stored in a first memory location and the count of the number of VC'"'"'s is stored in a second memory location, and wherein the step of using a single iterative loop comprises the step of;

decrementing the exponent stored in the first memory location by one; and

right-shifting the number of VC'"'"'s stored in the second memory location.

16. In an Asynchronous Transfer Mode (ATM) information network for serially transmitting ATM user cells of ATM traffic categories, including Available Bit Rate (ABR) traffic comprising ABR user data cells and Resource Management (RM) cells having Explicit Rate (ER) fields, each ATM user cell having a defined header with identification data defining a Virtual Connection (VC) from an ATM traffic user source (SES) in a transmission path including one or more ATM switches and interconnecting transmission links having maximum cell transmission rates, to an ATM user destination (DES) at a cell transmission rate established at the SES, wherein congestion of VCs in a transmission path may occur, apparatus for controlling such congestion through controlling the cell transmission rate of ABR traffic to a Fair Share cell transmission rate comprising:

means for transmitting data and RM cells of ABR traffic from the SES in a forward direction in a VC through the transmission path at the cell transmission rate;

at the ATM switch in the transmission path of the VCs in the forward direction,

means for determining the presence of congestion of the ATM switch ingress cell memory or of an egress physical port coupled thereto and providing a set indication of congestion in response thereto;

means for determining a maximal cell transmission rate of the physical port of the VC having the set indication of congestion;

means for sending backward RM cells of ABR traffic in a backward direction from the DES to each ATM switch in the transmission path of each VC;

at the ATM switch in the transmission path of the VCs in the backward direction, means operable on receipt of a backward RM cell at each ATM switch in the transmission path of the VC including;

means for determining a count of the number of VCs through the egress physical port coupled to the ATM Switch; and

means for changing the count of the actual number of VCs to a changed count of a power of two;

means for determining a Fair share cell transmission rate as a function of the maximum cell

transmission rate of the egress physical port used in the VC and the changed count;

means for writing the Fair Share cell transmission rate in the ER fields of the backward RM cells; and

means for sending the backward RM cells of the ABR traffic in the backward direction from each such ATM switch in the transmission path of each VC toward the SES; and

at the SES, means for changing the actual cell transmission rate of ABR traffic generated by the SES to the Fair Share cell transmission rate in the ER field of the backward RM cells.

17. The apparatus of claim 16 further comprising:

means for comparing the cell transmission rate in the ER field in the backward RM cells received at the ATM switch to the Fair Share cell transmission rate prior to changing the ER; and

means for selectively writing the ER field, in response to the means for comparing, when the Fair Share cell transmission rate is less than the cell transmission rate in the ER field.

18. The apparatus of claim 16 wherein the means for determining the Fair Share cell transmission rate further comprises means for dividing the maximum cell transmission rate by the changed count.

19. The apparatus of claim 18 wherein said means for changing the count further comprises means for incrementing the count to the next higher power of two.

20. The apparatus of claim 16 wherein said means for changing the count further comprises means for incrementing the count to the next higher power of two.