====================================== FDDI MAC Counter Flushing Patch version 1.0.0 (1999-Mar-27-Sat) Adam M. Costello ====================================== This is a list of changes to be made to the FDDI MAC specification (ANSI X3.139-1987) to make the token-passing self-stabilizing. For related documents, see: http://www.cs.berkeley.edu/~amc/research/fddi/ Remove all references to restricted tokens. 4.2.1 Token. After FC add RC (Rotation Counter) (12 bits encoded in 5 Data Symbols for corruption detection) and PB (Phase Bit) (1 bit encoded in 1 Data Symbol for corruption detection). Replace ED (End Delimiter) with an Idle Symbol, so that a Token looks like a Frame fragment (which is how it is treated). 4.2.2 Frame Add RC and PB as in 4.2.1. 4.3.7.1 Token Ending Delimiter. Remove this section. 4.3.9 Rotation Counter and Phase Bit. New section. Give details of rotation counter encoding and phase bit encoding. Behavior common to Leaders and non-Leaders: If either RC or PB is corrupt in an incoming Token/Frame, the Token/Frame is stripped. When Tokens are created, the Rotation Counter and Phase Bit are copied from an internal register. When Frames are created, the Rotation Counter is copied, but the Phase Bit is 0. Non-Leader behavior: While repeating Tokens/Frames/fragments, non-Leaders copy the Rotation Counter and Phase Bit into an internal register (if they are not corrupt). If this changes the register, and the internal phase bit is now 1, then the message carries a token, which the station may optionally capture by changing the Phase Bit of the message to a 0 before repeating it. (A full Frame never carries a token in normal operation--only during stabilization, so it is not necessary to repeat the rest of the message after the Phase Bit.) Leader behavior: While repeating Tokens/Frames/fragments, the Leader copies in the other direction--from the internal register into the Rotation Counter and Phase Bit of the message. It also compares the original values in the message to the ones in its internal register. If they are equal, the Leader increments its internal rotation counter, and the message carries a token, which the Leader automatically captures (but which can be released effortlessly). Note that the Leader's internal phase bit is always 1. When the Leader's transmitter is idle, it repeatedly sends Tokens rather than just Idle symbols (which is why releasing an unuseful token is effortless). 4.4.3 Valid-Transmission Timer (TVX). Perhaps remove this section. TVX is not needed, and may not be worth the complexity. It is primarily useful for fast recovery from Leader crashes. TVX is also mention in sections 5.3.2 R(01), 5.3.5 R(34), 5.3.7 R(51c), 5.4.1 T(04), 5.4.2 T(14), 5.4.3 T(24), 5.4.4 T(34). 5.1.3 Frame Stripping. Change "PA, SD, FC, DA, and SA" to "PA, SD, FC, RC, PB, DA, and SA". Stations act on RC and PB fields in fragments just as they do in complete Frames. 5.1.5.1 Claim Token Process. The winner of the bidding is the Leader. The Leader sets its internal phase bit to 1. 5.3.1 Token and Frame Validity Criteria (1) Token (a) unchanged (b) unchanged (c) Has 6 additional Data Symbols forming valid RC and PB fields. (d) remove (2) Frame (included in Frame_Ct) (a) unchanged (b) unchanged (c) Has valid RC and PB fields. (d) same as old (c) (e) same as old (d) (3) unchanged (4) unchanged (5) Valid Data Length (a) Is an integral number of Data Symbol pairs (octets) between Starting and Ending Delimiters (or after Starting Delimiter if there is no Ending Delimiter). (b) Is a minimum number of octets as follows: FC Interpretation Minimum Octets CLFF ZZZZ to ZZZZ 0X00 0000 Void 4 1X00 0000 Token 4 0000 0001 to 1111 SMT frame 12 0100 0001 to 1111 SMT frame 20 1000 0001 to 1111 MAC frame 16 1100 0001 to 1111 MAC frame 24 X001 XXXX LLC frame 12 X101 XXXX LLC frame 20 X010 XXXX Implementor frame 12 X110 XXXX Implementor frame 20 X011 XXXX Reserved 12 X111 XXXX Reserved 20 (6) unchanged (7) unchanged (8) unchanged 5.3.4 State R2: RC_FR_CTRL (Receive Frame Control Field) Unchanged until... R(21b): Format Error. This transition ... occurs if [unchanged] or if an error is detected in the Rotation Counter or Phase Bit fields. R(23): Start of Frame Rename this transition to Start of Frame or Token. Non-Leaders: If no errors are detected in the incoming Rotation Counter and Phase Bit, copy them into an internal register, noticing whether the register changes. If it does, and the internal phase bit is now 1, a token has been received, so take the actions of old R(51c). Leader: If no errors are detected in the incoming Rotation Counter and Phase Bit, compare them to internal register (whose phase bit is always 1). If they are equal, a token has been received, so increment the internal rotation counter and take the actions of old R(51c). If the FC field indicates a next station addressing frame, then the N_Flag shall be set. R(25) Start of Token Remove this transition. 5.3.5 State R3: RC_FR_BODY (Receive Frame Body). Unchanged until... R(31b): Format Error. This transition ... occurs if [unchanged] or if the maximum PDU length of 9000 symbols is exceeded. 5.3.6 State R4: RC_FR_STATUS (Receive Frame Status). Add the transition: R(41g): Format Error. This transition to state R1 occurs if the maximum PDU length of 9000 symbols is exceeded. On this transition, the FO_Error signal shall be generated and the Lost_Ct shall be incremented. 5.3.7 State R5: CHECK_TK (Check Token). Remove this section. 5.4.1 State T0: TX_IDLE (Transmitter Idle). The only thing that changes in this state is that the Leader transmits tokens instead of just idle symbols. This requires the Leader to have a buffer between input and output big enough to hold a Token (27 symbols including a 16-symbol preamble), and to enqueue an entire Token in one atomic action whenever the buffer is empty. But if a token has just been received (TK_Received signal), the Leader should instead merely enqueue an idle symbol (whether the buffer is empty or not). This is crucial if the token is usable (lest the Leader immediately give it away), and sensible even if the token is unusable (since the transition to state T3 ISSUE_TK will cause a token to be sent anyway). Likewise, when a FR_Strip signal is received, the Leader should enqueue an idle symbol to ensure that the fragment boundary is still marked for the next station. 5.4.2 State T1: REPEAT (Repeat). Introduction is unchanged except for the third sentence: If a usable token is detected, then the transmitter of a non-Leader changes the Phase Bit to 0 before repeating it and thus acquires the token. The Leader always overwrites the Rotation Counter and Phase Bit from its internal register. T(10a): Token Capture. Renumber this section to T(12). A transition to State T2 occurs if a token has been received (TK_Received signal) if the token is usable. A token is usable when the ring is operational (Ring_Operational) and either: (1) unchanged (2) unchanged (3) unchanged At this point, the station captures the token by changing the Phase Bit to 0 before it is repeated (except that the Leader always uses its internal phase bit value, which is 1). After the Phase Bit is transmitted, the actions of T(02) are performed, followed by the change to state T2. Other transitions are unchanged. 5.4.3 State T2: TX_DATA (Transmit Data). Introduction unchanged except for this addition: Use the internal register to generate the Rotation Counter for the new Frame. The Phase Bit shall be 0. Caveat: It is quite possible that the receiver will try to write to the register at the same time that the transmitter is trying to read from it. The reads and writes need to be atomic to avoid sending corrupt values. Scratch space may be necessary. T(23): Done. ....This transition shall also be taken if [unchanged], or on a TK_Received signal, or if the internal phase bit is 0. 5.4.4 State T3: ISSUE_TK (Issue Token). Introduction is unchanged except for this addition: Use the internal register to generate the Rotation Counter and Phase Bit for the new Token. (The internal phase bit should normally be 1 in this state, but might be 0 if we are stabilizing.) Transitions are unchanged except for this one: T(30b): Token Issued. A transition to State T0 occurs after the transmitter has issued the Phase Bit of the Token. 5.4.5 State T4: CLAIM_TK (Claim Token). Upon entering this state, the Leader_Flag is cleared, [unchanged]. T(43) Successful Claim. Insert: Leader_Flag and Phase Bit shall be set.