************************************************************************ ATM Forum Document Number: ATM Forum/94-0987 ************************************************************************ Title: Ordered BECN: Why we need a timestamp or sequence number in the RM Cell ************************************************************************ Abstract: BECN cells and FECN cells can arrive at the source out of order and the effect of a BECN can be nullified by subsequent FECN cells that actually bring older information. Knowing which RM Cell represents newer information helps get full advantage of BECN. This can be done by having a sequence number or time stamp field in the RM cell. The Ordered BECN option of the OSU scheme is described and the effect of BECN with and without this order is shown. ************************************************************************ Source: Ra j Jain, Shiv Kalyanaraman and Ram Viswanathan The Ohio State University Department of CIS Columbus, OH 43210 Phone: 614-292-3989, Fax: 614-292-2911, Email: Jain@ACM.Org The presentation of this contribution at ATM Forum is sponsored by NIST. ************************************************************************ Date: October 25-26, 1994 ************************************************************************ Distribution: ATM Forum Technical Working Group Members (Traffic Management) ************************************************************************ Notice: This contribution has been prepared to assist the ATM Forum. It is offered to the Forum as a basis for discussion and is not a binding proposal on the part of any of the contributing organizations. The statements are sub ject to change in form and content after further study. Specifically, the contributors reserve the right to add to, amend or modify the statements contained herein. ************************************************************************ One common criticism of end-to-end feedback control schemes is that the control is slow if the round-trip delays are large. This is particularly important for high-speed networks since the propagation delays become significant compared to the data transmission delays. One way to overcome this is for the switch to send the feedback right back to the source and thus avoiding the round-trip delay of the remaining path. Although this option, commonly known as backward Explicit Congestion Notification (BECN) has been known for quite some time and is even allowed by the frame-relay and ATM UNI standards, no satisfactory schemes have been developed for this. This is because, most designers of the BECN have missed the key point, that correlating feedback with the correct control is the most important aspect of a congestion control scheme (and for that matter, any control system) design. The problem with BECN can be seen easily by the configuration of Figure 1. The source is sending at 150 Mbps and sends three control cells. The switch 1 happens be unloaded at the time of the first two control cells and so lets them go unchanged. By the time, the third control cell arrives, the switch 1 is loaded by a factor of 3 and sends a BECN to the source to come down to 50 Mbps. A little bit later the second control cell returns from Switch 2 telling the source to reduceto 100 Mbps. Finally the first control cell arrives from the destination telling it that 150 Mbps is ok. The control cell are received out of order rendering the BECN ineffective. The second and control cells actually make the source increase the rate. To ensure correct operation for BECN, we have developed the following rules, called "The OSU Ordered BECN Rules" for using the BECN option: 1. The BECN should be sent only when a switch is overloaded. There is no need to send BECN if the switch is underloaded. This avoids the problem of one switch asking a source to go up and a subsequent switch asking it to go down. 2. The source should include a timestamp in the control cell indicating the time when the control cell was generated. This helps distinguish successive cells. The timestamp is ignored at all intermediate switches and the destination and is used only at the source. Thus, no clock synchronization among nodes is required or assumed. 3. All control cells complete a round-trip. If a switch wants to send a BECN, it waits until it receives an control cell. It makes two copies of the it. One copy is forwarded in the forward direction. The other is sent back to the source. 4. The control cell also includes a bit called "BECN bit." This bit is initialized to zero at the source and is set by the congested switch in the copy of control cell that is sent backward. This helps the source know whether a received control cell has visited the complete path or only a part of it. The cells that have completed only a part of the path are called "BECN cells" as opposed to "FECN cells" that have completed the entire path. 5. The source remembers the time stamp of the last BECN or FECN cell that it has acted upon in a variable called "Time already acted (Taa)." If the timestamp in an returned control (BECN or FECN) cell is lessthan Taa, the cell is ignored. This rule helps avoid out-of-order control cells. 6. If the timestamp of an control cell received at the source is equal to or greater than Taa AND the rate indicated in the cell is less than source's current rate, the rate is reduced. Otherwise, the BECN is ignored. With above rules, the BECN option reduces the time to reach the efficiency zone. The reduction is significant only in those WAN cases where the remaining path length is large. Figure 2 shows the same previous example with timestamps. After the source receives a RM Cell (at t=50), it notes the time in the RM cell in the variable Taa (time already acted). Taa is set to 30. The source reduces the rate to 50 Mbps. When the second RM cell is received at t=60. The timestamp in the cell is 20, which is less than Taa, and so it is ignored. Similarly, when the FECN RM cell is received at t=70, the timestamp in it is 10, which is again less than Taa, and so it is ignored also. To best show the effect of BECN we selected the configuration shown in Figure 3. It consists of four VCs and three switches. The second link is shared by VC1 and VC4. However, because of the first link, VC1 is limited to a throughput of 1/3 the link rate. VC4 should, therefore, get 2/3 of the second link. This configuration is helpful in checking if the scheme will allocate all unused capacity to those sources that can use it. The first link is 1 km long while the second is 1000 km long. The long link helps show the effect of long end-to-end round trip delay. The simulation results with BECN but without the timestamp are shown in Figure 4. Notice that thare are large oscillations. In general, this is caused by out of order contractictory messages. BECN's ask the sources to go down to 60 Mbps but are soon overruled by FECN asking them to go up to 150 Mbps and the cycle repeats. The results with the ordered BECN are shown in Figure 5. Notice that all unneccessary oscillations have been eliminated. Note that BECN does not have any significant effect in the LAN environment since the round trip delays are small. We recommend BECN use only in large WANs.