US 6,289,066 B1Grant
Method and apparatus for recentering an elasticity FIFO when receiving 1000BASE-X traffic using minimal information
Issue Date:2001-09-11
•14 Claims
•3 Drawing Sheets
Abstract
A method and apparatus is provided that solves the problem of data overrun and underrun, for example in a system that exchanges data using the Gigabit Ethernet protocol. A single 8-bit data path is provided as output and the main protocol state machines are kept running in the clock domain of the rest of the circuit, after an elasticity FIFO, so that no additional synchronization is necessary. The invention makes no demands upon the receive clock other than those specified in the relevant standard for duty cycle and accuracy. The invention correctly combines the two effective data streams back into a single data stream, only modifying the FIFO when it is acceptable to do so, and in a way that does not corrupt data packets passing through the FIFO. By providing a minimal set of logic running in the receive clock domain, it is possible to simplify the design of the main protocol state machines. Only a very small portion of the design must be aware of the dual-clock nature of the physical interface. In addition, because all key state machines are no longer in the receive clock domain, any state information or registers are available even if the receive clocks are not running correctly, as is the case with a removable transceiver design.
Metadata
Assignee
- Hewlett-Packard Company
Inventors
- Bruce E. LaVigne
- Patricia A. Thaler
- Paul O'Connor
Application Information
Application Number:US 09/096,143
Filing Date:1998-06-11
Priority Date:1998-06-11
Art Unit:7
Classifications
IPC:
H04L 700
Field of Search:
375372375354375371375377370516370517370518370505370503713400
Patent Drawings (3 sheets)
Description
Background of the Invention
[0002] 1. Technical Field
[0003] The invention relates to computer networks. More particularly, the invention relates to a synchronizing system, and further relates to means used between two devices transmitting data at different speeds to counteract this speed differential as a buffer in systems that are used for the exchange of information over a computer network, especially with regard to the Gigabit Ethernet protocol (IEEE 802.3, clause 36, 1000BASE-X).
[0004] 2. Description of the Prior Art
[0005] In any circuit interfacing two non-correlated and asynchronous clocks, there exists a non-zero probability of sampling a signal from one system with the clock from the other system while the signal is changing. The result of such a sampling, where set-up and hold times are not met, may be an erroneous output. Unpredictably the output can be logic “1”, logic “0”, or in a metastable state between “1” and “0.” This undefined logic state may be interpreted differently by different receiving devices, and in a general configuration it is able to propagate through the succeeding logic gates.
[0006] This metastable state is discussed in L. Marino, General Theory of Metastable Operation, IEEE TRANSACTIONS ON COMPUTERS, Vol. C.30, No. 2, pp. 107-115 (February 1981); T. Chaney et al, Anomalous Behavior of Synchronizer and Arbiter Circuits, IEEE TRANSACTIONS ON COMPUTERS, Correspondence, pp. 421-422 (April 1973); and D. Kinniment et al, Circuit Technology in a large computer system, THE RADIO AND ELECTRONIC ENGINEER, Vol. 43, No. 7, pp. 435-441 (July 1973).
[0007] The metastable state is potentially unstable and the probability that the output stays in a metastable state decays exponentially with time. All logic families exhibit the metastable operation, when sampling occurs on a transition. However, families with a high-gain bandwidth product are less inclined to exhibit the metastable state than those with a low-gain bandwidth product. The metastable problem is a fundamental problem in digital circuits interfacing asynchronous clocks, and there exists no exact solution to avoid errors. However, the probability of inducing errors due to the metastable operation can be reduced by allowing longer time for the output to settle from the metastable state and by employing high-gain bandwidth product devices.
[0008] A method of allowing this output to settle while still receiving data from the source uses what is referred to as an elasticity FIFO, where data is input into the FIFO structure in the incoming clock, and output several unit times later with the outgoing clock. The FIFO acronym refers to “First In First Out”, meaning that each datum is output in the order it was received.
[0009] In Fiber Channel and Gigabit Ethernet (IEEE 802.3, clause 36, 1000BASE-X, the serial data stream runs continuously and the transmit and receive clock frequencies may differ by as much as 200 parts per million (ppm). The result is that over time, the FIFO that is used to cross this clock boundary reaches a full or empty position. Accordingly, some action must be taken to prevent data overrun or underrun.
[0010] An elasticity FIFO (see V. Cavanna, Synchronizing System, U.S. Pat. No. 4,873,703 (Oct. 10, 1989)) was used in a Fiber Channel ASIC (Tachyon), manufactured by Hewlett-Packard Company of Palo Alto, Calif. In the Cavanna design, the solution to adding/deleting entries from the FIFO is to put an elasticity FIFO after the protocol decoder. This allows the FIFO to be aware of when it may safely add or remove symbols. Unfortunately, this approach has the disadvantage that a greater share of the circuit's logic is running off of the incoming clock(s). This is an undesirable result, especially in the Ethernet switching market, where removable transceivers are common—and thus there are times when there is no incoming clock. It is also desirable for testability of the chip to have as much circuitry as possible running off a single clock, Also, keeping the circuitry in the receive clock domain small is better design practice since in cases where circuitry is split between multiple clocks, bugs are often introduced by using a signal from one clock domain in the other clock domain.
[0011] For both Fiber Channel and Gigabit Ethernet, the defined interface (see ANSI Technical Report TR/X3.18-1997) uses two receive clocks, each 180 degrees out of phase from one another. This dual clocking allows the interface to use slower logic, but introduces many problems as well. The Cavanna design solves these problems by widening the data path to 16 bits and by clocking most logic off one of the receive clocks. This is acceptable for Fiber Channel devices because all transactions are performed in units of 16 or 32 bits. For Gigabit Ethernet, however, the minimum unit is only 8 bits. While implementations have been developed using wider data paths for Gigabit Ethernet, such wider data path adds size and complexity to the design, especially where it is necessary to signal how many bytes of data are valid within a single data unit and when handling corner cases which arise out of this design style.
[0012] Another possible solution to the foregoing problem is to generate a 2× clock from the incoming receive clocks. This design, however, would be fraught with problems. For example, this design would require a phase locked loop (PLL) circuit to lock on to the receive clocks, where the receive clocks are already the output of another PLL.
[0013] It would be advantageous to provide a method and apparatus that prevents data overrun or underrun in a system that exchanges data using such data exchange protocols as the Gigabit Ethernet protocol.
Summary of the Invention
[0014] The invention provides a method and apparatus that solves the problem of data overrun and underrun, for example in a system that exchanges data using the Gigabit Ethernet protocol, providing a single 8-bit data path as output and keeping the main protocol state machines running in the clock domain of the rest of the circuit, after an elasticity FIFO, so no additional synchronization is necessary. The invention makes no demands upon the receive clock other than those specified in the relevant standard for duty cycle and accuracy. The mechanism provided by the invention correctly combines the two effective data streams back into a single data stream, only modifying the FIFO when it is acceptable to do so, and in a way that does not corrupt data packets passing through the FIFO.
Brief Description of the Drawings
[0015] FIG. 1 is a block schematic diagram of a computer network showing a system A, a system B, and a synchronizer;
[0016] FIG. 2 is a block schematic diagram of a FIFO showing the insert and extract areas according to the invention; and
[0017] FIG. 3 is a flow diagram of the insert/extract decision on whether or not to move the extract pointer.
Detailed Description of the Invention
[0018] The invention provides a method and apparatus that solves the problem of data overrun and underrun, for example in a system that exchanges data using the Gigabit Ethernet protocol, providing a single 8-bit data path as output and keeping the main protocol state machines running in the clock domain of the rest of the circuit, after an elasticity FIFO, so that no additional synchronization is necessary. The invention makes no demands upon the receive clock other than those specified in the relevant standard for duty cycle and accuracy. The mechanism provided by the invention correctly combines the two effective data streams back into a single data stream, only modifying the FIFO when it is acceptable to do so, and in a way that does not corrupt data packets passing through the FIFO.
[0019] By providing a minimal set of logic running in the receive clock domain, it is possible to simplify the design of the main protocol state machines. Only a very small portion of the design must be aware of the dual-clock nature of the physical interface. In addition, because all key state machines are no longer in the receive clock domain, any state information or registers are available even if the receive clocks are not running correctly, as is the case with a removable transceiver design.
[0020] In FIG. 1, a typical synchronizing system is shown as a system configuration. The synchronizing system consists of a synchronizer 101 having a receiving side 101A coupled to a system A 102 and a transmitting side 101B coupled to a system B 103. The coupling of the synchronizer 101 to the system A 102 and the system B 103 is performed by a synchronous and interlocked handshake operation. It is synchronous because all lines in the interface are synchronous with the transfer clock frequency. It is used on the input and output side of the synchronizer circuit in which case the synchronizer translates one synchronous handshake into a similar handshake synchronous with an arbitrary second clock. Data (DATA) are transferred in bytes of any width at the rate of a clock signal (CLK). Each data byte is labeled with a “data available” signal (DAV). For each clock cycle, the data sink presents a “ready for data” signal (RFD).
[0021] The invention provides a mechanism within the synchronizer that enhances the synchronizing FIFO described in V. Cavanna, Synchronizing System, U.S. Pat. No. 4,873,703 (Oct. 10, 1989), to merge symbols from two separate input clock domains, 180 degrees out of phase with one another, into the single output clock domain. This invention provides this mechanism with a minimal amount of additional circuitry necessary to add or remove elements from the FIFO correctly, to maintain a valid Gigabit Ethernet data stream in the face of disparate (up to 200 ppm) input and output clock frequencies.
[0022] A key aspect of this mechanism is determining when it is acceptable to add or remove symbols from the data stream. This requires some understanding of the protocol used by Gigabit Ethernet (IEEE 802.3 clause 36, 1000BASE-X). Data produced and consumed by the MAC layer are converted from 8-bit bytes into 10-bit symbols, which are then serialized across the physical medium. During packet transmission, each byte is converted into a single 10-bit symbol. However, during the idle periods between packets, a pair of 10-bit symbols are used repeatedly, and during link configuration, a quartet of 10-bit symbols (CONFIG words) are used repeatedly. Thus, during packet reception, no symbols may be added or removed without corrupting the incoming packet. During idle, symbols may be added or removed, but only in pairs. During configuration, symbols may be added or removed, but only in quartets (unless the upper layer is made aware of the operation—as is practiced by the invention, which only adds/removes in pairs).
[0023] FIG. 2 is a block schematic diagram of a FIFO showing the insert and extract areas according to the invention. The preferred embodiment of the invention uses a single insert pointer 26 into two banks (i.e. bank 0 and bank 1, 20 and 22, respectively) of the FIFO 10. In FIG. 2, the banks are actually the data elements, e.g. bank 0 consists of all the elements JLNPBDFH. Each input clock writes data symbols from a common data stream 32 into a specific, corresponding bank of the FIFO, and the insert pointer moves forward after bank 0 is written. The output clock 34, running at roughly 2× the input clock 35, alternately reads data symbols from the two banks by muxing the output of the two FIFO banks with a multiplexer 24 as controlled by a bank selector 40 which toggles during every output clock cycle.
[0024] Another key to the design is monitoring the next four symbols in the FIFO, in the output clock domain. If the FIFO is getting too full or too empty, and the symbols indicate that the system is at a point where it is safe to perform an add/delete operation, then the operation is performed. Because the preferred embodiment of the invention only adds/deletes in pairs, a signal is sent up to the upper level state machine indicating that a shortened CONFIG word may have been created due to the add/delete.
[0025] The Gigabit Ethernet protocol always results in idle and configuration sequences starting with the first byte on the bank 0 clock. Therefore, the first byte of the idle signal and the 1st and 3rd bytes of a configuration word is always in bank 0. The second byte of the idle signal and the 2nd and 4th bytes of a configuration word are always in bank 1. The preferred embodiment makes use of this characteristic to simplify detection of configuration and idle as well as insertion and deletion of symbols.
[0026] By way of example of the operation of the preferred embodiment of the invention, in FIG. 2 it is assumed that bank 0 has just been written, and that the insert pointer 26 has moved to point to element “A” as the next element about to be written. Also, it is assumed the bank selector 40 just toggled to 1 and the extract pointer 27 has moved to point to element “I” as the next element to be read. The FIFO is half full: entries “I”, “J”, “K”, “L”, “M”, “N”, “O”, and “P” are filled. The shaded elements “I”, “J”, “K”, and “L” are being examined to determine if the FIFO can allow modifications. If the symbols in these locations map to IDLE or CONFIG sequences, then it is permissible to modify the FIFO. In this case, because the FIFO is exactly half full, it is in the neutral position 28, such that no additions or deletions are necessary. If the FIFO is under half full, it is said to be in the “add” region 29, if the FIFO is over half full, it is said to be in the “delete” region 30. Note also that if the FIFO content falls to only four symbols, it is effectively empty because it is necessary to examine the next four symbols to determine if the FIFO may be modified.
[0027] The single insert pointer 26 always moves forward after bank 0 has been written (except if the FIFO is about to overflow) which, combined with the two input clocks 180 degrees out of phase, alternately writes symbols from each clock domain into the FIFO. Normally, the extract pointer 27 moves forward after the bank 0 read, and holds during the bank 1 read. This, combined with an alternating bank selector, allows the mechanism described herein to pull data out of the FIFO from every other bank in order.
[0028] If the insert pointer 26 is in the “add” region 29 and the symbols in elements “I”, “J”, “K”, and “L” are idle or configuration symbols, then the extract pointer 27 instead holds after a bank 0 read, thus replicating elements “I” and “J.” In the case of an IDLE stream, this mechanism replicates an entire IDLE pair. For a CONFIG stream, this mechanism replicates the first two symbols. Accordingly, the upper layers are notified so they can ignore the extra symbols to maintain synchronization with the data stream.
[0029] If the insert pointer 26 is in the “delete” region 30 and the symbols in elements “I”, “J”, “K”, and “L” are idle or configuration symbols, then the extract pointer clocks ahead after the bank 1 read, as well as after the bank 0 read. This has the effect of removing elements “J” and “K.” In the case of the IDLE stream, this mechanism deletes the second half of one IDLE and the first half of the next IDLE, effectively merging two IDLEs into one. For a CONFIG stream, this mechanism deletes the second and third symbols of a CONFIG quartet. This leaves the data stream with the first and fourth symbols of a CONFIG word. The upper layers are notified that a delete has taken place, which is seen during the decode of the first symbol. The upper layer then ignores the fourth symbol and proceeds back to the beginning, looking for the first symbol of the next CONFIG word.
[0030] Any symbol insertion or removal may cause a running disparity error, whether during IDLE or CONFIG. Accordingly, the mechanism signals to the upper layers to ignore running disparity during FIFO modification and to recompute the running disparity based upon the revised data stream.
[0031] The result is a FIFO design which has minimal knowledge of the underlying protocol, but which maintains correct operation under all required conditions, turning data from two clock domains into a valid data stream in a third clock domain.
[0032] FIG. 3 is a flow diagram of the insert/extract decision on whether or not to move the extract pointer. When the decision process begins (100), a determination is made as to how full the FIFO currently is (110). It may be in the add region, the delete region, or the neutral region. If the FIFO remains neutral (i.e. it is not too full or too empty) a determination is made if the bank selector is in bank 0 (160). If the selector is not in bank 0 , the system holds the pointer and extracts data (130) from the FIFO; if the selector is in bank 0, the system increments the pointer and extracts data (150). If the FIFO is in the add region, then the system determines if the four elements at the head of the FIFO consist of IDLE or CONFIG (120). If either conditions are true, then a hold/extract operation is performed (130) to the FIFO; otherwise, a determination is made whether the selector is in bank 0, as discussed above. If the FIFO is in the delete region, then the system determines if the four elements at the head of the FIFO consist of IDLE or CONFIG (140). If either conditions are true, then an increment operation is performed (150) to the FIFO; otherwise, a determination is made whether the selector is in bank 0, as discussed above.
[0033] The module, shown in Table 1 below, implements an elasticity FIFO for a receive Gigabit Ethernet PCS block. The FIFO crosses the clock boundary between RBC0/RBC1 and grx_clk and is based on the synchronizer FIFO architecture disclosed by V. Cavanna, Synchronizing System, U.S. Pat. No. 4,873,703 (Oct. 10, 1989). The invention herein provides, in part, for moving the FIFO to a nominal state with eight octets full, so that during times when the FIFO cannot be adjusted (i.e. packet bursts), a data transfer session can survive the clock skew (up to 1.9 bytes in 9730 grx_clks). To do this, the preferred embodiment of the invention removes any of IDLEs, half of CONFIG quads, or pairs of arbitrary octets if synchronization is not yet gained. Thus, an empty indication occurs when the FIFO runs below four octets available. The module of Table 1 is a verilog expression of a hardware implementation of the invention. It will be appreciated by those skilled in the art that the invention may be implemented in either hardware or software, or a combination of hardware and software, and that the invention is not limited to the embodiment shown in the module below.
[0034] Although the invention is described herein with reference to the preferred embodiment, one skilled in the art will readily appreciate that other applications may be substituted for those set forth herein without departing from the spirit and scope of the present invention. Accordingly, the invention should only be limited by the claims included below.
Claims
What is claimed is:
1. In a synchronizing system consisting of a synchronizer having a receiving side coupled to a first system and a transmitting side coupled to a second system, a mechanism within said synchronizer comprising:
a synchronizing FIFO for merging symbols from two separate input clock domains, 180 degrees out of phase with one another, into a single output clock domain; and
means for selectively adding or removing elements from said synchronizing FIFO to maintain a valid data stream.
2. The mechanism of claim 1, wherein said data stream is a Gigabit Ethernet (IEEE 802.3 clause 36, 1000BASE-X) data stream.
3. The mechanism of claim 1, further comprising:
means for determining when it is acceptable to add or remove symbols from said data stream.
4. The mechanism of claim 3, further comprising:
means wherein, during configuration, symbols may be added or removed, but only in quartets, unless an upper layer is made aware of said add/remove operation, which only adds/removes in pairs.
5. The mechanism of claim 3, further comprising:
means wherein, during idle, symbols may be added or removed, but only in pairs.
6. The mechanism of claim 3, further comprising:
means for signaling a disparity check circuitry so that symbol removal does not cause detection of a disparity error.
7. The mechanism of claim 3, said synchronizing FIFO further comprising:
an insert pointer into said FIFO, wherein each input clock writes data symbols into a specific, corresponding location of said FIFO; and
an extract pointer.
8. The mechanism of claim 1, said synchronizing FIFO comprising:
at least two banks.
9. The mechanism of claim 8, further comprising:
an output clock for alternately reading data symbols from said at least two synchronizing FIFO banks by muxing the output of said two synchronizing FIFO banks with a bank selector which toggles during every output clock cycle.
10. The mechanism of claim 8, further comprising:
means for monitoring a predetermined number of next symbols in said synchronizing FIFO in an output clock domain to determine if said mechanism is at a point where it is safe to perform an add/remove operation.
11. The mechanism of claim 8, wherein a signal is sent up to an upper level state machine indicating that a shortened configuration (CONFIG) word may have been created due to an add/remove operation.
12. The mechanism of claim 10, wherein it is permissible to modify said synchronizing FIFO if said next symbols map to IDLE or CONFIG sequences.
13. The mechanism of claim 8, wherein said synchronizing FIFO is in a neutral position when it is filled to a predetermined portion of its capacity such that no additions or removals are necessary; wherein said synchronizing FIFO is in an add region when it is filled to less than said predetermined portion of it's capacity; and wherein said synchronizing FIFO is in a remove region when it is filled to more than said predetermined portion of it's capacity.
14. In a synchronizing system consisting of a synchronizer having a receiving side coupled to a first system and a transmitting side coupled to a second system, a mechanism within said synchronizer comprising:
a synchronizing FIFO for receiving symbols from a single clock domain, said synchronizing FIFO comprising a single bank; and
means for selectively adding or removing elements from said synchronizing FIFO upon the occurrence of predetermined conditions to maintain a valid data stream, wherein said means for selectively adding or removing elements, upon detection of an idle or configuration condition in the front bytes of said FIFO, skips at least one next byte for a delete and repeats the at least one next byte for an insert.
Patent Citations (6)
Non-Patent Literature (1)
- “Fibre Channel—10-bit Interface”, X3 Technical Committee of American National Standards Institute, Information Technology Industry Council, Revision 2.3.Applicant