Method and apparatus for implementing a backpressure mechanism in an asynchronous data transfer and source traffic control system

0001This application is related to co-owned U.S. Pat. Nos. 5,901,146 and 6,104,724, the complete disclosures of which are hereby incorporated by reference herein.

BACKGROUND OF THE INVENTION

00021. Field of the Invention

0003The invention relates to asynchronous data communication among a bus master and a plurality of bus users. More particularly, this invention relates to a bus frame and bus structure for an asynchronous data transfer system which allows a bus user to assert a congestion signal (CONG) to indicate a congestion condition and which places certain limits on data transfer when a CONG signal is detected.

00042. State of the Art

0005The CELLBUS® backplane is an asynchronous data transfer and source traffic control system which has been very successful in the field of telecommunications. In particular, the CELLBUS® backplane is very useful as an alternative to a standard switch fabric in an ATM switch. As shown in prior art <figref idref="DRAWINGS">FIG. 3</figref>, the CELLBUS® asynchronous data transfer system includes a timing master and bus arbiter <b>100</b> and a plurality of users <b>112</b>, <b>114</b>, <b>116</b> which are coupled to a bidirectional data bus <b>118</b>, a clock bus <b>120</b>, and a frame bus <b>122</b>. The users <b>112</b>, <b>114</b>, <b>116</b> are also coupled to a bidirectional acknowledge (ACK) bus <b>126</b>, and a bidirectional congestion (CONG) bus <b>128</b>. The clock bus <b>120</b> provides a system clock to each bus user and the frame bus <b>122</b> provides a frame clock to each bus user. The system clock is the basic transfer clock of the system (i.e., data is put onto the data bus and taken off the data bus during one system clock cycle), whereas the frame clock designates the start of a frame.

0006Prior art <figref idref="DRAWINGS">FIG. 4</figref> illustrates the frame format which preferably includes sixteen system clock cycles, a first one of which is designated the request field and a last one of which includes a grant field. One or more other cycles may be assigned control and/or routing information and the remainder of the cycles are assigned to the transfer of data from one particular user onto the bus and off the bus to one or more other users. During the first cycle of each bus frame, a number of bus users may request access, which requests are received by the bus master during the same first cycle. During the last cycle of each bus frame, the bus master grants access to a selected bus user for the entire data portion of the next frame. Bus users are thus regularly (once each cell) allowed to request access for the next frame and the bus master is regularly (once each frame) granting access to a selected bus user. Which user is granted access to the next frame is determined according to an arbitration method in the bus master which is unknown to the bus users. The arbitration method may thus be changed at any time by the bus master without informing the bus users. Thus, for example, as traffic conditions on the bus change (as different users request more or less access) the arbitration method can be adjusted accordingly by the bus master to provide the most efficient allocation of bus access.

0007In the CELLBUS® system thus described, ATM cells may be transferred from any bus user to any other bus user, or to any number of other bus users (multicast). One user at a time sends a cell to the bus, which may be read from the bus by any user or users. The bus timing master sources the system transfer clock and bus framing signal, both of which are used to synchronize all bus access operations. Bus access is controlled by the bus arbiter. Users request bus access from the bus arbiter. Each bus user is assigned two bits of the request field. Thus, sixteen users are supported in one implementation of a CELLBUS® system. The use of two bits for a request allows the requests to be prioritized in three levels. Another implemention of a CELLBUS® system allows up to thirty-two users. In order to preserve the two-bit request format, each user may only make a request every other frame, e.g. every even frame or every odd frame. The bus arbiter accepts access requests, queues them as needed, and issues grants. When a grant is issued, it is for one user to send one cell to the bus. All grants are for a single cell time on the bus only. When a user is granted access by the bus arbiter, it will indicate acceptance by asserting the ACK line during the grant phase of the same frame in which the cell was sent. Local conditions at the addressed terminal, such as congestion, may cause an ACK not to be generated. The sending bus user may detect a congested indication at the destination by sensing an asserted CONG signal on the CONG line during the grant phase of the same frame in which the cell was sent. The timing of the CONG signal is identical to that of the ACK signal, during the grant phase of the same frame in which the cell was sent. An active CONG is an indication of congestion. An inactive CONG indicates no indication. The definition of what condition defines congestion and the consequential actions of an active CONG indication are unspecified in the CELLBUS® specification. Preferably, however, a CONG signal is sent before the bus user is incapable of accepting any more data.

SUMMARY OF THE INVENTION

0008It is therefore an object of the invention to provide a logical method for implementing congestion control in an asynchronous data transfer and source traffic control system.

0009It is another object of the invention to provide a logical method which uses a congestion signal to implement congestion control in an asynchronous data transfer and source traffic control system.

0010It is also an object of the invention to provide a logical method for implementing congestion control in a CELLBUS® system.

0011It is still another object of the invention to provide a logical method which uses the CELLBUS® CONG signal to implement congestion control.

0012In accord with these objects which will be discussed in detail below, according to a first embodiment of the invention, the bus arbiter is programmed to detect when a bus user is experiencing congestion and to prevent other bus users from sending cells to the congested user. In particular, if congestion is detected for two consecutive frames, the arbiter is inhibited from granting access to any bus user for one frame.

0013The first embodiment guarantees that the congested bus user will not receive a cell for at least one out of every three frames. This will absolutely help relieve congestion at the egress FIFO which will result in lower cell loss across the bus. The traffic is backpressured to the ingress devices which must now absorb more traffic. This, however, is desirable because the ingress buffers are often much larger than the CELLBUS® rate decoupling buffers. A potential disadvantage of this approach is that it may result in slightly longer transport delays for high priority traffic during times when no bus user is permitted to use the bus.

0014A second embodiment of congestion control according to the invention results in fewer transport delays for high priority traffic. According to the second embodiment, if congestion is detected during any frame, all the bus users are prevented from transmitting low priority traffic until congestion is absent for four consecutive frames. This method does not absolutely guarantee that congestion will be relieved, particularly if the traffic on the bus is predominantly high priority traffic. However, in most applications, the volume of high priority traffic is relatively low compared to the volume of low priority traffic. Thus, in most applications, the second embodiment will succeed in reducing congestion without delaying the high priority traffic. The second embodiment can be implemented in two ways. According to the first way, each bus user is programmed such that its scheduler ignores low priority traffic during the period of congestion. According to the second way, the bus arbiter decides, based on the priority indicated by the two-bit request, which requests are high priority and declines grants to low priority requests during periods of congestion.

0015Additional objects and advantages of the invention will become apparent to those skilled in the art upon reference to the detailed description taken in conjunction with the provided figures.

BRIEF DESCRIPTION OF THE DRAWINGS

0016<figref idref="DRAWINGS">FIG. 1</figref> is a simplified flow chart illustrating the methods of the invention;

0017<figref idref="DRAWINGS">FIG. 2</figref> is a simplified block diagram illustrating an apparatus according to the invention;

0018<figref idref="DRAWINGS">FIG. 3</figref> is a simplified block diagram of a prior art CELLBUS® system; and

0019<figref idref="DRAWINGS">FIG. 4</figref> is a diagram of the frame used in the CELLBUS® system.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

0020Referring now to <figref idref="DRAWINGS">FIG. 1</figref>, the two embodiments of methods according to the invention are illustrated in a single flow chart. Starting at <b>200</b>, it is determined at <b>202</b> which method will be used. Continuing on the left side of the chart, the first method determines at <b>204</b> whether congestion exists. If congestion exists, i.e. CONG is asserted by a bus user experiencing egress congestion, no access is granted by the bus master to the next frame as indicated at <b>206</b>. When there is no congestion, access is granted as usual.

0021Turning to the right side of <figref idref="DRAWINGS">FIG. 1</figref>, the second method begins by permitting both low and high priority dequeuing at <b>208</b>. If it is determined at <b>210</b> that congestion exists, i.e. CONG is asserted by any user, all bus users are prevented at <b>212</b> from transmitting low priority traffic. The ban on low priority traffic remains in effect until it is determined at <b>214</b> that congestion has been absent for four consecutive frames. If congestion is absent for four consecutive frames, bus access returns to normal.

0022The illustration of both methods in <figref idref="DRAWINGS">FIG. 1</figref> implies that both methods be available for application at any time. However, it is within the scope of the invention to implement only one of the methods. In addition, the use of the terms “CONG” and “frame” imply that the methods are implemented in conjunction with a CELLBUS® system. However, the first method can be used in any system employing a repeating frame and where congestion can be detected. The second method can be used in any system having mixed high priority and low priority traffic which employs a repeating frame and where congestion can be detected.

0023The presently preferred embodiment of the invention is implemented in a CELLBUS® system which is illustrated in <figref idref="DRAWINGS">FIG. 2</figref>. The system includes a bus master <b>300</b> and up to thirty-two bus users <b>301</b>-<b>332</b> coupled to a CELLBUS® backplane <b>350</b>. According to the presently preferred embodiment, any bus user may be configured to be the bus master. The bus master and the bus users are preferably coupled to a host processor <b>352</b>. The host processor is used to configure the bus users and the bus master to carry out the methods of the invention described above with reference to <figref idref="DRAWINGS">FIG. 1</figref>.

0024The present invention may be implemented with virtually any CELLBUS® compatible device. An exemplary device is the ASPEN® EXPRESS™ device produced by TranSwitch Corporation, Shelton, Conn. The ASPEN® EXPRESS™ device has a configurable shared buffer space for 512K ATM cells. Thus it is well equipped to tolerate backpressure imposed by the methods of the invention.

0025The first embodiment can be implemented entirely in the bus arbiter. The second embodiment can be implemented in two ways. According to the first way, each bus user is programmed such that its scheduler ignores low priority traffic during the period of congestion. According to the second way, which can be implemented entirely in the bus arbiter, the bus arbiter decides which requests are high priority based on the two-bit request, and declines grants to low priority requests during periods of congestion.

0026There have been described and illustrated herein methods and apparatus for implementing a backpressure mechanism in an asynchronous data transfer and source traffic control system. While particular embodiments of the invention have been described, it is not intended that the invention be limited thereto, as it is intended that the invention be as broad in scope as the art will allow and that the specification be read likewise. For example, while the number of congested frames in the first embodiment is stated to be two, the congestion threshold could be higher or lower depending on expected traffic conditions. Similarly, the four frame decongestion threshold in the second embodiment could be adjusted for similar reasons. It will therefore be appreciated by those skilled in the art that yet other modifications could be made to the provided invention without deviating from its spirit and scope as so claimed.