Method and apparatus for backward explicit congestion notification (BECN) in an ATM network

• US 5,457,687 A
• Filed: 09/02/1993
• Issued: 10/10/1995
• Est. Priority Date: 09/02/1993
• Status: Expired due to Term

• Current Assignee: Network Equipment Technologies Incorporated (Ribbon Communications, Inc.)
• Original Assignee: Network Equipment Technologies Incorporated (Ribbon Communications, Inc.)
• Inventors: Newman, Peter
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): HOM, SHICK C
• Application Number:
  US08/115,857
• Time in Patent Office: 768 Days
• Field of Search: 370/60.1, 370/60, 370/84, 370/13, 370/94.1, 370/94.2, 370/95.1, 370/95.3, 370/85.2, 370/85.3
• US Class Current: 370/232
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 2012/5616 Terminal equipment, e.g. codecs, synch.
• CPC Class Codes: H04L 2012/5632 Bandwidth allocation
• CPC Class Codes: H04L 2012/5635 Backpressure, e.g. for ABR
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

Reactive congestion control in an asynchronous transfer mode (ATM) network where the network is formed by the interconnection of nodes each including a forward path for transfer of information from source to destination through the network and a return path for returning congestion control signals. Each source includes a modifiable issue rate unit which issues forward information signals at different rates for virtual channels in response to the presence and absence of congestion signals received on the return path. When congestion occurs, for example, a queue exceeds a threshold, a request is made to send congestion signals, in the form of backward explicit congestion notification (BECN) cells, back to the sources of the virtual channels currently submitting traffic to the queue. On receipt of a BECN cell on a particular virtual channel, a source reduces it transmission rate for the indicated virtual channel. If no BECN cells are received on a particular virtual channel for a certain period of time, a source may gradually restore its transmission rate. In order to reduce the number of congestion cells, a filter is provided for filtering requests for congestion signals. Fairness is promoted in the recovery of transmission rates using a rate recovery algorithm that increases slower rate transmitters faster than higher rate transmitters.

Claims

1. A communication system having reactive congestion control comprising,

a plurality of sources, each source including a modifiable issue rate unit which transmits forward information signals at different transmission rates in response to congestion signals, said issue rate unit decreasing a transmission rate in response to congestion signals,

a plurality of destinations,

one or more nodes, forming an asynchronous transfer mode (ATM) network connecting the sources to the destinations, each node including,

a forward path for transfer of information in a forward direction toward a destination through the network,

a return path for returning congestion signals in a reverse direction through the network toward a source,

congestion signal generating means for generating requests for congestion signals in response to congestion in the node, said congestion signal generating means connected to said return path in said node,

filter means for filtering said requests and for responsively providing said congestion signals,

said network having a plurality of virtual channels where, for each virtual channel,

one of said plurality of sources is linked to one of said plurality of destinations through said network by linking forward paths from one or more nodes, and wherein said issue rate unit transmits forward information signals at different transmission rates in response to congestion signals over the virtual channel,

said one of said plurality of destinations is linked to said one of said plurality of sources through said network by linking return paths from said one or more nodes,

the congestion signal generating means in one of said intermediate nodes generates said congestion signals for the virtual channel in response to congestion in said one of said intermediate nodes and said congestion signals from said one of said intermediate nodes returns in the reverse direction without need for propagation to said destination.

2. The communication system of claim 1 wherein said filter means includes,

storage means for storing congestion indicators, said storage means operative in response to requests to read said storage means to access any stored congestion indicator and thereafter to store a congestion indicator into said storage means,

a filter clock providing a filter clock signal having a filter period for resetting said congestion indicators in said storage means,

gate means responsive to an absence of a congestion indicator from said storage means and to each of said requests to provide said congestion signal.

3. The communication system of claim 2 wherein said storage means includes a one bit store shared by all of said virtual channels.

4. The communication system of claim 2 wherein said storage means includes a one bit store for each of said virtual channels.

5. The communication system of claim 2 wherein said storage means includes a content addressable memory having a location for each of said virtual channels.

6. The communication system of claim 1 wherein said filter means includes,

storage means for storing a congestion indicator for each virtual channel, said storage means operative in response to each request from a virtual channel to read said storage means to access any stored congestion indicator for the virtual channel and thereafter to store a congestion indicator into said storage means for the virtual channel,

a filter clock providing a filter clock signal having a filter period for resetting once per filter period said congestion indicators for all virtual channels in said storage means,

gate means responsive to an absence of a congestion indicator from said storage means for a virtual channel and to said request signal for a virtual channel to provide said congestion signal.

7. The communication system of claim 1 wherein said issue rate unit increases the transmission rate in response to an absence of congestion signals.

8. The communication system of claim 1 wherein a congestion signal returning from a congested node to the source has a transmission interval that is less than the interval between information signals transmitted over the virtual channel whereby the issue rate unit reactively responds to modify the transmission rate to reduce congestion.

9. The communication system of claim 2 wherein a congestion signal returning from a congested node to the source has a transmission interval and said filter period is related to the transmission interval.

10. The communication system of claim 2 wherein a congestion sisal returning from a congested node to the source has a transmission interval and said filter period is approximately twice the transmission interval.

11. The communication system of claim 1 wherein a congestion signal returning from a congested node to the source has a transmission interval and the transmission interval is short thereby enabling the issue rate unit to reactively modify the transmission rate and thereby reduce congestion.

12. The communication system of claim 1 wherein a congestion signal returning from a congested node to the source has a transmission interval and the transmission interval is less than the interval between information signals transmitted over the virtual channel whereby the issue rate unit reactively responds to modify the transmission rate to reduce congestion.

13. The communication system of claim 1 wherein a congestion signal returning from a congested node to the source has a transmission interval and the transmission interval is less than ten intervals between information signals transmitted over the virtual channel whereby the issue rate unit reactively responds to modify the transmission rate to reduce congestion.

14. The communication system of claim 1 wherein a congestion signal returning from a congested node to the source has a transmission interval and a processing time required to generate said congestion signal at each node wherein said processing time is much less than said transmission interval.

15. The communication system of claim 1 wherein said issue rate unit has means for decreasing said transmission rate by a divide-by-two amount in response to a congestion signal.

16. The communication system of claim 1 wherein said issue rate unit has means for decreasing said transmission rate by a fractional multiple amount in response to a congestion signal.

17. The communication system of claim 16 wherein said issue rate unit, after decreasing said transmission rate at a decreasing rate, has means for increasing said transmission rate at an increasing rate in response to an absence of a congestion signal with said increasing rate varying with the transmission rate whereby lower transmission rates increase faster than higher transmission rates.

18. The communication system of claim 16 wherein the rate of increasing said transmission rate is less than the rate of decreasing said transmission rate.

19. The communication system of claim 1 wherein said forward information signals are fragmented into cells, each cell including a virtual channel identifier, and wherein each node includes a switching element, each switching element including,

a switch fabric,

a plurality of port controllers interconnected by said switch fabric, each of said port controllers including,

an input controller,

an output controller,

congestion detection means for detecting congestion in the node,

reversing means for copying a cell, having a virtual channel identifier, from the forward path to the return path to thereby generate a congestion signal on said return path.

20. The communication system of claim 19 wherein said reversing means includes reverse marker means for marking copied cells with a return path indicator whereby return cells are distinguished from forward cells.

21. The communication system of claim 19 wherein each of said port controllers includes selector means for selecting cells from one virtual channel for the forward path or from another virtual channel for the return path.

22. The communication system of claim 21 wherein said selector means grants priority to cells from the return path whereby congestion signals are given priority in the network.

23. The communication system of claim 19 wherein said forward path includes a queue for storing cells in the forward direction and having a queue fullness, said queue including means for providing a queue-level signal, as a function of the queue fullness, to form the congestion signal.

24. The communication system of claim 1 wherein said forward information signals are fragmented into cells, each cell including a virtual channel identifier, and wherein each node includes a switching element, each switching element including,

a switch fabric,

a plurality of port controllers interconnected by said switch fabric, each port controller connected to a communication link and each port controller including,

an input controller for said link including a translator for receiving the virtual channel identifier of incoming cells on the link and responsively translating the input virtual channel identifier of incoming cells to an output virtual channel identifier of outgoing cells for another link for another port controller connected to said switch fabric,

an output controller for said link,

congestion detection means for detecting congestion in the node,

reversing means for copying a cell, having a virtual channel identifier, from the forward path to the return path to thereby generate a congestion signal on said return path, said reversing means connecting said output virtual channel identifier to be reverse translated to said input virtual channel identifier whereby the virtual channel identifiers for cells in the forward path and in the return path over the link are the same.

25. The communication system of claim 24 wherein said port controller includes one or more queues connected in parallel for queuing cells for the forward path and the return path of a link, said queues providing queue-level signals indicating the fullness of the queues and including selection means for selecting cells from said queues.

26. The communication system of claim 25 wherein said selector means grants priority to cells from the return path whereby congestion signals are given priority in the network.

27. The communication system of claim 24 wherein said reversing means includes reverse marker means for marking copied cells with a return path indicator whereby return cells are distinguished from forward cells.

28. The communication system of claim 24 wherein each of said port controllers includes selector means for selecting cells from one virtual channel for the forward path or from another virtual channel for the return path.

29. The communication system of claim 25 wherein said selector means grants priority to cells from the return path whereby congestion signals are given priority in the network.

30. The communication system of claim 24 wherein said forward path includes a queue for storing cells in the forward direction and having a queue fullness, said queue including means for providing a queue-level signal, as a function of the queue fullness, to form the congestion signal.

31. A wide-area communication system having local reactive congestion control comprising,

a plurality of local communication systems, each local communication system including,

a plurality of local sources, each local source including a modifiable issue rate unit which transmits forward information signals at different transmission rates, said issue rate unit decreasing the transmission rate in response to a presence of congestion signals and increasing the transmission rate in response to an absence of congestion signals,

a plurality of local destinations,

one or more local nodes forming an asynchronous transfer mode (ATM) local network connecting the sources to the destinations, each local node including,

a forward path for transfer of information at different selectable transmission rates in a forward direction toward a destination through the network,

a return path for returning congestion signals in a reverse direction through the network toward a source,

congestion signal generating means for generating requests for congestion signals in response to congestion in the local node, said congestion signal generating means connected to said return path in said local node.

filter means for filtering said requests and for responsively providing said congestion signals,

said network having a plurality of virtual channels where, for each virtual channel,

one of said plurality of local sources is linked to one of said plurality of local destinations through said local network by linking forward paths from one or more local nodes, and wherein said issue rate unit transmits forward information signals at different transmission rates in response to congestion signals over the virtual channel,

said one of said plurality of local destinations is linked to said one of said plurality of local sources through said network by linking return paths from said one or more local nodes,

the congestion signal generating means in one of said local nodes generates said requests for congestion signals for the virtual channel in response to congestion in said one of said local nodes and returns said congestion signals from said one of said local nodes in the reverse direction,

one or more wide-area sources connected to one of said local networks,

one or more wide-area destinations connected to another one of said local networks,

a plurality of local network links interconnecting two or more local networks to form a wide-area network, said wide-area network having a plurality of virtual channels where, for each virtual channel, one of a plurality of wide-area sources is linked to one of a plurality of wide-area destinations through a plurality of said local networks over said local networks and said local network links.

32. The wide-area communication system of claim 31 wherein a congestion signal returning from a congested..local node to the local source has a transmission interval and the transmission interval is short thereby enabling the issue rate unit to reactively modify the transmission rate and thereby reduce congestion in the wide-area communication system.

33. The wide-area communication system of claim 31 wherein a congestion signal returning from a congested local node to the local source has a transmission interval and the transmission interval is less than the interval between information signals transmitted over the virtual channel whereby the issue rate unit reactively responds to modify the transmission rate to reduce congestion in the wide-area communication system.

34. The wide-area communication system of claim 31 wherein a congestion signal returning from a congested local node to the local source has a transmission interval and the transmission interval is less than ten intervals between information signals transmitted over the virtual channel whereby the issue rate unit reactively responds to modify the transmission rate to reduce congestion in the wide-area communication system.

35. The wide-area communication system of claim 31 wherein a congestion signal returning from a congested node to the source has a transmission interval and a processing time required to generate Said congestion signal at each node wherein said processing time is much less than said transmission interval.

36. The communication system of claim 31 wherein said issue rate unit has means for decreasing said transmission rate by a divide-by-two amount in response to a congestion signal.

37. The communication system of claim 31 wherein said issue rate unit has means for decreasing said transmission rate by a fractional multiple amount in response to a congestion signal.

38. The communication system of claim 37 wherein said issue rate unit, after decreasing said transmission rate at a decreasing rate, has means for increasing said transmission rate at an increasing rate in response to an absence of a congestion signal with said increasing rate varying with the transmission rate whereby lower transmission rates increase faster than higher transmission rates.

39. The wide-area communication system of claim 31 wherein said forward information is fragmented into cells, each cell including a virtual channel identifier, and wherein each node includes a switching element, each switching element including,

a switch fabric,

a plurality of port controllers interconnected by said switch fabric, each of said port controllers including,

an input controller,

and an output controller,

congestion detection means for detecting congestion in the node,

reversing means for copying a cell, having a virtual channel identifier, from the forward path to the return path to thereby generate a congestion signal on said return path.

40. The wide-area communication system of claim 39 wherein said reversing means includes reverse marker means for marking copied cells with a return path indicator whereby return cells can be distinguished from forward cells.

41. The wide-area communication system of claim 39 wherein each of said port controllers includes selector means for selecting cells from one virtual channel for the forward path or from another virtual channel for the return path.

42. The wide-area communication system of claim 39 wherein said selector means grants priority to cells from the return path whereby congestion signals are given priority in the network.

43. The wide-area communication system of claim 42 wherein said forward paths include queues for storing cells in the forward direction, each of said queues including means for providing a queue-level signal, as a function of the fullness of the queue, to form the request for a congestion signal in response to the queue-level signal.

44. The wide-area communication system of claim 31 wherein said forward information signals are fragmented into cells, each cell including a virtual channel identifier, and wherein each node includes a switching element, each switching element including,

a switch fabric,

a plurality of port controllers interconnected by said switch fabric, each port controller connected to a communication link and each port controller including,

an input controller for said link including a translator for receiving the virtual channel identifier of incoming cells on the link and responsively translating the input virtual channel identifier of incoming cells to an output virtual channel identifier of outgoing cells for another link for another port controller connected to said switch fabric,

an output controller for said link,

congestion detection means for detecting congestion in the node,

reversing means for copying a cell, having a virtual channel identifier, from the forward path to the return path to thereby generate a congestion signal on said return path, said reversing means connecting said output virtual channel identifier to be reverse translated to said input virtual channel identifier whereby the virtual channel identifiers for cells in the forward path and in the return path over the link are the same.

45. A communication system having reactive congestion control comprising,

a plurality of sources, each source including a modifiable issue rate unit which transmits forward information signals at different transmission rates in response to congestion signals, said issue rate unit decreasing a transmission rate in response to congestion signals,

a plurality of destinations,

a plurality of nodes, including one or more intermediate nodes, forming an asynchronous transfer mode (ATM) network connecting the sources to the destinations, each intermediate node including,

a forward path for transfer of information in a forward direction toward a destination through the network,

a return path for returning congestion signals in a reverse direction through the network toward a source,

congestion signal generating means for generating requests for congestion signals in response to congestion in the intermediate node, said congestion signal generating means connected to said return path in said intermediate node,

filter means for filtering said requests and for responsively providing said congestion signals to said return path for propagation directly to one of said sources,

said network having a plurality of virtual channels where, for each virtual channel,

one of said plurality of sources is linked to one of said plurality of destinations through said network by linking forward paths from one or more nodes, and wherein said issue rate unit transmits forward information signals at different transmission rates in response to congestion signals over the virtual channel,

said one of said plurality of destinations is linked to said one of said plurality of sources through said network by linking return paths from said one or more nodes,

the congestion signal generating means in one of said intermediate nodes generates said congestion signals for the virtual channel in response to congestion in said one of said intermediate nodes and said congestion signals from said one of said intermediate nodes returns in the reverse direction without need for propagation to said destination.