Adaptive rate shaping to prevent overflow

The rate at which a node transmits data is modified dependent on the receive rate by selecting one of a plurality of predetermined quantum values dependent on the difference between the number of bytes received and the number of bytes transmitted. An offset equal to the difference between the number of bytes transmitted and the number of bytes received is compared to a predetermined threshold value. A predetermined quantum value is selected dependent on the result of the comparison. Rate shaping is applied to the transmit data by halting data transmission for an inter-gap interval dependent on the selected quantum value.

BACKGROUND OF THE INVENTION

A major problem in a synchronous data network is preventing data overflow in a node in which data is being received faster than it is being transmitted. Receive and transmit data rates in a node differ if there is a difference in frequency between the receive clock and the transmit clock. This frequency difference occurs if the transmit data rate is dependent on the node's transmit clock and the receive data rate is dependent on the adjacent node's transmit clock.

One method for preventing overflow is to synchronize the transmit clock and the receive clock. One such clock synchronization method is described in U.S. Pat. No. 5,896,427 issued on Apr. 20, 1999 entitled “System and Method for Maintaining Network Synchronization Utilizing Digital Phase Comparison Techniques with Synchronous Residual Time Stamps” by Muntz et al. This method requires synchronizing on a per bit basis which is complex and expensive and can not be used on all data networks.

Another method for preventing data overflow is to provide a large buffer in the node. The disadvantages of this method are that the buffer adds delay to the transfer of data through the node, the addition of a buffer to the node increases the cost of the node and the buffer cannot prevent overflow if the buffer is not large enough.

Yet another method for preventing data overflow is to implement flow control in the node. Flow control requires large buffers which add delay through the node. Also, flow control can not be used in all data networks, such as wide area networks.

SUMMARY OF THE INVENTION

In a node connected to a computer network the transmit data rate and the receive data rate are synchronized by modifying the transmit data rate. The transmit data rate is increased or decreased dependent on an offset equal to the difference between the number of bytes received and the number of bytes transmitted. The offset selects the predetermined quantum value used to modify the transmit data rate.

If the offset is less than or equal to a predetermined threshold, a quantum value is selected to decrease transmit data rate. If the offset is greater than the predetermined threshold, a quantum value is selected to increase the transmit data rate. The quantum value is dependent on the inaccuracy between the receive clock and the transmit clock. Preferably the offset is incremented every time a predetermined number of bytes is received and decremented every time the predetermined number of bytes is transmitted.

The transmitter modifies the data transmit rate by halting transmission of transmit data for a period of time dependent on the selected quantum value.

The present invention eliminates the need for expensive and complex clock synchronization required in existing synchronous computer networks, such as the Synchronous Optical NETwork (“SONET”) network.

DETAILED DESCRIPTION OF THE INVENTION

FIG. 1illustrates a computer network with three nodes100a-cconnected through computer links106,108. Each of the nodes includes an oscillator102a-cand data transfer logic104a-c.The nodes100a-cconnected to the network operate in “free-run” mode. That is, the receive clock is derived from the incoming receive data stream and the transmit clock is derived from the local oscillators102a-c.The receive clock is encoded in the incoming receive data stream using techniques well known in the art, for example, Manchester encoding or 8B/10B encoding.

Node_A100ais connected to Node_B110bthrough communications link a-b106. Node_B100bis connected to Node_C100cthrough communications link b-c108. In order to transmit data from Node_A100ato Node_C100c,the data flows through the data transfer logic104bin Node_B100b.The rate at which data is transmitted from Node_A100ais dependent on the frequency of Node_A's oscillator102a.The rate at which data is transmitted from Node_B100bis dependent on the frequency of Node_B's oscillator102b.

Thus, the rate at which data is received at Node_B100bon communications link a-b106, that is, Node_B's100bincoming rate may differ from the rate at which it is transmitted to Node_C100con communications link b-c108, that is, Node_B's100boutgoing rate. Synchronization of the outgoing data rate with the incoming data rate is performed by inserting an idle bandwidth at Node_B's100boutput. Idle is defined as no data being transmitted from Node_B100bwhile the data transfer logic104bis enabled for transmitting.

In Node_B100b,the maximum and minimum outgoing rates are determined as shown in Equations 1 and 2 below, where the clock inaccuracy is the difference in frequency between the receive clock from Node_A100aand the transmit clock in Node_B100b:
maximum outgoing rate=incoming rate (1+clock inaccuracy)  Equation 1
minimum outgoing rate=incoming rate (1−clock inaccuracy)  Equation 2

FIG. 2is a block diagram illustrating the data transfer logic104bin Node_B100bshown in FIG.1. Receive Data logic216determines if the destination of the data received on communications link a-b106is Node_B100bor Node_C100c.If Node_B100bis the destination of the data, the received data is forwarded through node receive data224to the Receive FIFO200. If Node_B100bis not the destination of the data, the received data is forwarded through transit buffer receive data226to the transit buffer202and forwarded through the transmit data select logic210and the rate shape logic208to Node_C100c(FIG. 1) on communications link b-c108.

The receive data logic216recovers the receive byte clock218encoded in the data received on communications link a-b106. The method for deriving the receive byte clock218is dependent on the technique used to encode the receive clock in Node_A100a.The transit buffer receive data226is inserted in the transit buffer202dependent on the receive byte clock218.

The oscillator102bprovides a transmit clock228for transmitting data on communications link b-c108to Node_C100c(FIG.1). The data transmitted on communications link b-c108is the data received from Node_A100a(FIG. 1) stored in the transit buffer202to be forwarded to Node_C100c(FIG. 1) or the data originating in Node_B100bin the Transmit FIFO204. The transmit data select logic210selects the transmit data to forward on transmit data in222to the rate shape logic208.

The transmit data select logic210generates a transmit byte clock212dependent on the transmit clock228. Transit buffer transmit data220is removed from the transit buffer202dependent on the transmit byte clock212. Thus, the receive byte clock218and transmit byte clock212control the insertion and removal of a predetermined number of bytes into or from the transit buffer202.

In one implementation of the transit buffer202well-known in the art, the transit buffer202may be a First In-First Out (“FIFO”) memory, with transmit buffer receive data226inserted at the bottom of the transit buffer202dependent on the receive byte clock218, and transit buffer transmit data220removed from the top of the transit buffer202dependent on the transmit byte clock212.

The synchronous control logic206monitors the rate at which transit buffer receive data226is inserted into the transit buffer202dependent on the receive byte clock218and the rate at which transit buffer transmit data220is removed from the transit buffer202dependent on the transmit byte clock212. The synchronous control logic206sets a fast/slow signal214to fast or slow dependent on an offset equal to the difference between the number of bytes inserted into the transit buffer202and the number of bytes removed from the transit buffer202. The fast/slow signal214is forwarded to the rate shape logic208.

The rate shape logic208inserts idle bandwidth on communications link b-c108by transmitting no data for a predetermined time interval dependent on the state of the fast/slow signal214. The idle bandwidth accounts for the rate difference between the incoming data rate on communications link b-c108and the outgoing data rate on communications link a-b106. Thus, data is transmitted on communications link b-c108at a rate dependent on the receive data rate on communications link a-b106. The overall transmit rate of the node is rate shaped to accommodate the worst case difference between the receive byte clock218and the transmit byte clock212.

FIG. 3is a block diagram illustrating the synchronous control logic206shown in FIG.2. The synchronous control logic206includes a transit buffer slip counter300, a comparator302, and a threshold register306. The transit buffer count304is a positive number or zero. If a node100is idle before data is received into the transit buffer202(FIG.2), the transit buffer slip counter300is reset to set the transit buffer count304to zero. The transit buffer slip counter300is incremented by the receive byte clock218every time a predetermined number of bytes of transit buffer receive data226(FIG. 2) are inserted into the transit buffer202(FIG. 2) and is decremented by a transmit byte clock212every time the predetermined number of bytes of transit buffer transmit data220(FIG. 2) are removed from the transit buffer202(FIG.2).

The predetermined number of bytes of data, that is, the width of the transit buffer202(FIG. 2) may be dependent on a SONET optical carrier (“OC”) standard implemented in the node100(FIG.1). For example, the preset number of bytes for OC-3 is one, the preset number of bytes for OC-12 is two and the preset number of bytes for OC-48 is four.

Thus, if OC-12 is implemented in the node100, the transit buffer slip counter300is incremented by the receive byte clock218every time two bytes are inserted in the transit buffer200(FIG.2). The transit buffer count304, a positive integer, is the difference between the number of bytes inserted in the transit buffer300and the number of bytes removed from the transit buffer300.

A threshold register306stores a predefined threshold value. The threshold value determines the transit buffer count304at which the current transmit rate is to be adjusted. The threshold value is selected such that, if the receive data rate is equal to the transmit date rate, the transit buffer count304will vary between the selected threshold value and zero.

The comparator302compares the transit buffer count304with the threshold value stored in the threshold register306and determines whether to set the fast/slow signal214to fast or slow. If the transit buffer count304is less than the threshold value stored in the threshold register306, the fast/slow signal214is set to slow to decrease or maintain the current transmit rate. If the transit buffer count304is greater than or equal to the threshold value stored in the threshold register306, the fast/slow signal214is set to fast to increase the transmit rate. Thus, if the transmit rate is equal to the receive rate the transit buffer count304will be less than or equal to the threshold value stored in the threshold register306and the fast/slow signal214is set to slow. The fast/slow signal214is forwarded to the rate shape logic208(FIG. 2) to modify the transmit rate.

FIG. 4is a block diagram illustrating the rate shape logic208shown in FIG.2. The rate shape logic208includes an interval counter400, a token buffer counter logic414, halt_transmit logic402, transmit logic408, a Quantum_1register410, and a Quantum _2register412.

The interval counter400defines the interval period over which rate shaping is performed and provides an interval clock404with a period equal to the interval period. The interval counter400is clocked by the system clock406in the node100. The interval period is selected such that it is sufficiently large to provide accurate rate shaping.

The token buffer count logic414counts the number of bytes transmitted from the node100. The interval clock404is forwarded to the token buffer count logic414. The Quantum_1value or the Quantum_2value is added to the token buffer count416in the token buffer count logic414at the start of an interval period dependent on the state of the fast/slow signal214. The token buffer count416is decremented by the token buffer count logic414dependent on transmit data in222as data is transmitted from the node100.

The halt_transmit logic402monitors the token buffer count416and the data being transmitted on transmit data in212. Upon determining that the token buffer count416is less than zero and there is a packet boundary, the halt_transmit logic402generates the halt_transmit signal418. If the token buffer count416is less than zero and a packet boundary has not been reached, the token buffer count logic414continues to decrement the token buffer count416until a packet boundary has been reached. The halt_transmit signal418is forwarded to the transmit logic408. While the halt_transmit signal218is asserted the transmit logic408does not allow transmit data in222to be forwarded from the node100. In each interval period, the halt_transmit signal418is asserted for a period of time dependent on the token buffer count416at the beginning of the interval period, the length of the interval period and the token buffer count416at the end of the interval period.

Thus, over a large number of interval periods, the halt_transmit signal418is asserted for an average period of time equal to the length of the interval period minus the average value token added to the token buffer counter logic at the beginning of each interval period, where the token added may be either the stored Quantum_l value or Quantum_2value.

The Quantum_1and Quantum_2values are determined by solving for Equations 4 and 5 after substituting Equation 3 in Equations 1 and 2:
outgoing rate=quantum/interval*system clock rate  Equation 3

The incoming rate is dependent on the OC standard implemented in the node100. The incoming rate is the bandwidth available for the data payload excluding the bandwidth for overhead bytes. For example, for OC-12, the incoming rate is the Synchronous Payload Envelope (“SPE”) and is 600 Megabits per second (“Mbps”). The clock inaccuracy is determined by the worst case difference between the frequency of the receive and transmit clocks of adjacent nodes.

Thus, knowing the constant value for the clock inaccuracy, and selecting a constant interval period, the constant values for the Quantum_l and Quantum_2values can be calculated. These values are calculated one time for the node and stored in the Quantum_l and Quantum_2registers410,412so that they can be used to adjust an inter-packet gap at the beginning of each interval period.
quantum_1=interval period*(receive rate/system clock rate)*(1−clock inaccuracy)  Equation 4
quantum_2=interval period*(receive rate/system clock rate)*(1+clock inaccuracy)  Equation 5

The selection of the Quantum_1and Quantum_2values is described for a numerical example for which the interval period is selected to be 218system clock cycles (262,144 clock cycles) and the OC-12 line rate, that is, the incoming rate, is 600 Mbps. The system clock is 50 Megahertz (MHz), therefore at two bytes per system clock, the system clock rate is 800 Mbps (16 bits @ 50 Mhz). The frequency of the receive clock dependent on Node_A's oscillator102a(FIG. 1) and the frequency of the transmit clock dependent on Node_B's oscillator102b(FIG. 1) differ by no more than 100 parts per million (ppm). Thus, the clock inaccuracy is 10−4. Solving Equations 4 and 5 using the above numerical values, Quantum_l is 196,588 and Quantum_2is 196,628.

Thus, 196,588 clock cycles or 196,628 clock cycles are added to the token buffer counter logic414dependent on the state of the fast/slow signal214. The halt_transmit signal218is asserted when the token buffer counter logic404is equal or less than zero. At the end of the interval period at 262,144 clock cycles the token buffer count416is again summed with Quantum_1or, Quantum_2dependent on the state of the fast/slow signal214.

FIG. 5is a flow diagram illustrating the steps for providing rate shaping in the rate shape logic208shown in FIG.4.FIG. 6is a timing diagram illustrating the timing of the signals in the rate shape logic208shown in FIG.4. The operation of the rate shape logic208is described in conjunction withFIGS. 4-6.

The interval period600is shown in FIG.6. At the start of the interval period602, the halt_transmit signal218(FIG. 4) is asserted.

Continuing withFIG. 5, at step500, if the start of an interval period600(FIG. 6) is detected processing continues with step502.

At step502, the halt_transmit signal218(FIG. 4) is de-asserted as shown at604(FIG. 6) allowing data to be transmitted from the node100on communications link b-c108(FIG.4). Processing continues with step504.

At step504, the token buffer counter logic414(FIG. 4) determines from the fast/slow signal214whether to add Quantum_l or Quantum_2to the token buffer count416. If the fast/slow signal214is set to fast processing continues with step506. If the fast/slow signal214is set to slow processing continues with step508.

At step506in the token buffer counter logic414, Quantum_2is added to the token buffer count416(FIG. 4) at606(FIG.6). Processing continues with step510.

At step508in the token buffer counter logic414, Quantum_1is added to the token buffer count416(FIG. 4) at606(FIG.6). Processing continues with step510.

At step510, as data is transmitted on the transmit data signal108(FIG.4), the token buffer counter logic414(FIG. 4) is decremented dependent on transmit data in222(FIG.4). Processing continues with step512.

At step512, the halt_transmit logic402(FIG. 4) monitors the token buffer count416(FIG.4). If the token buffer count416(FIG. 4) is less than zero as shown at608(FIG. 6) processing continues with step514. If not, processing continues with step510.

At step514, the halt_transmit logic402(FIG. 4) monitors transmit data in222(FIG.4). If a packet boundary is detected as shown at610(FIG.6), processing continues with step515. If not, processing continues with step510.

At step515, the halt_transmit logic402(FIG. 4) asserts the halt_transmit signal418(FIG. 4) at612(FIG. 6) to halt data transfer on communications link b-c108(FIG.4). Processing continues with step500.

Thus, an inter-packet gap is generated by disabling transmit data from the node for a period of time dependent on the difference between the receive data rate and the transmit data rate.

While this invention has been particularly shown and described with reference to preferred embodiments within thereof, it will be understood by those skilled in the art that various changes in form and details may be made therein without departing from the scope of the invention encompassed by the appended claims.