| Contained below is the content of an upcoming FDDI Newsletter.
FDDI Bridge Stripping and Ring Purging
----------------------------------------
Before beginning any discussion on FDDI bridge stripping or ring purging, it
is useful to review some of the basic rules of an FDDI network relevant to
this topic:
1) In FDDI, a station is either repeating frames, transmitting frames,
or removing (stripping) frames.
2) While not transmitting or stripping frames, all stations act as
repeaters of any received frame; therefore, every station receives
and retransmits every frame in the ring.
3) A station must be holding the token in order to transmit a frame. A
station cannot transmit a frame to any other station until it captures
and holds the token.
4) A transmitting station has the responsibility for stripping its own
frame from the ring when the frame returns to the station.
5) Network management for error/fault detection and recovery is
distributed - there is no master station in the FDDI network.
Since every FDDI frame has both a source and a destination address associated
with it, it is a relatively easy decision for a workstation or computer system
to decide if it needs to remove a frame. It simply checks the source address
of the frame and compares that to its own FDDI address. If the addresses
match, the station removes the frame; if not, the station repeats the frame.
The Source Address Match algorithm spelled out in the ANSI FDDI MAC standard
specifies the procedure for this. (See Figure 1 - Station X is responsible
for removing its own frames when they return to it.)
+-----------+ +-----------+
| FDDI | | FDDI |
| Station +-----------+ Station |
| Address X +-----------+ Address Y |
| | | |
+----++-----+ +-----++----+
|| ||
|| FDDI RING ||
|| ||
|| +-----------+ ||
|| | FDDI | ||
|+----+ Station +------+|
+-----+ Address Z +-------+
| |
+-----------+
Figure 1
Bridge Stripping
----------------
Now let's look at what happens in the case of a transparent (IEEE 802.1d-
compliant) bridge connecting an Ethernet network to an FDDI backbone. The
transparent bridge uses the same source address in the FDDI frame as the
source address in the Ethernet frame, thereby making the bridge "transparent"
to the two communicating stations. (see Figure 2.)
+-----------+ +-------------+ +-----------+
| | | | | FDDI |
| Station | | Transparent +---------+ Station |
| Address A | | Bridge +---------+ Address Y |
| | | Address X | | |
+-----+-----+ | | +-----++----+
| +---+-----++--+ ||
| | || FDDI RING ||
| | || ||
| | || +-----------+ ||
----------+---------------------+-- || | FDDI | ||
ETHERNET |+---+ Station +--+|
+----+ Address Z +---+
| |
+-----------+
Ethernet Frame with becomes FDDI Frame with
Source Address = A Source Address = A
Destination Address = Y Destination Address = Y
Figure 2
The bridge is masquerading as the Ethernet station. But since there may be
dozens or hundreds of stations on the Ethernet, the transparent bridge will
generate hundreds of FDDI frames with dozens or hundreds of
DIFFERENT source addresses.
So how does the bridge know what frames to remove from the ring as frames
return to it? There are two basic ways to address this question, but one has
severe limitations.
The bridge could keep a table of all source addresses that it used in FDDI
frames, but this approach is limited by the SIZE of the table. If a size "n"
is picked for the table, then this scheme would fall apart when "n+1" source
addresses had to be used. Also if a very large size is chosen for "n", then
an exceptionally fast processor or CAM is needed in order to parse the table
to keep up with FDDI speeds.
Digital created an algorithm that was a better approach. The algorithm allows
frames to be stripped independently of the content or source address of the
frame. This algorithm allows FDDI stations like bridges to strip frames with-
out having to do extensive address comparison in real time.
The algorithm, called Frame Content Independent Stripping (FCIS), specifies
that a station strips the same number of frames that it has transmitted since
the last token capture. The station does this by keeping a local count of
frames transmitted but not yet stripped. It strips frames until the count is
zero. Each time a frame is transmitted, the station increments the count, and
each time an 'error free' frame is received and stripped, it decrements the
count. In addition to the count mechanism, at the end of transmitting the
frames and prior to releasing the token, a special frame called a Void frame
is transmitted to mark the end of the burst (train) of frames. (See Figure 3.)
+-------+ +-------+ +-------------+ +-----------+
| | | | | | | FDDI |
|Station| |Station| | Transparent +---------+ Station |
| A | ...... | M | | Bridge +---------+ Address Y |
| | | | | Address X | | |
+---+---+ +---+---+ | | +-----++----+
| | +---+-----++--+ ||
| | | || FDDI RING ||
| | | || ||
| | | || +-----------+ ||
--+----------------+------------+-- || | FDDI | ||
ETHERNET |+---+ Station +--+|
+----+ Address Z +---+
Bridge transmits onto FDDI: | |
Frame with SA = A, Sets Count = 1 +-----------+
Frame with SA = F, Sets Count = 2
Frame with SA = M, Sets Count = 3
Void Frame with SA = X
Token Then Bridge Strips Frames and Decrements
Count Until:
Count = 0 or
Void Frame with SA = X Received
or
Reset by Token, Claim, or Beacon
Frame
Figure 3
A Void frame is a special frame which is defined by the ANSI MAC Standard. It
can be transmitted by any station on FDDI. It is NOT an LLC or SMT frame. A
well-formed Void frame contains destination address, source address, and frame
check sequence (FCS). All well-formed Void frames used by the FCIS contain the
transmitter's address as the source address, so they are properly stripped by
the transmitter. The Void frame operates only within a single ring; it does
not cross bridges or routers to other FDDI rings or LANs.
When a bridge or a station receives its own well-formed Void frame,and there
are no errors in the frame, the local frames transmitted count is uncondition-
ally set to zero. The count is also reset to zero upon reception of a Token,
Claim, or Beacon frame.
Digital presented the FCIS algorithm to the ANSI FDDI Committee in 1988 and
again in 1989. The committee was convinced that the algorithm had all the
right properties and was robust, and they used the work presented for part of
an update to the MAC standard. Digital also published and presented papers on
the FCIS algorithm at SIGCOMM 90 and the Local Computer Network Conference 1990.
Variants of Digital's FCIS algorithm have been implemented by several FDDI
vendors.
Ring Purger
-----------
The Void frame is also used by Digital in solving another FDDI issue, namely
cleaning "no-owner" frames off the network, or purging the ring. A little back-
ground is needed on the problem before discussing the solution.
All token rings have the property that a frame can circulate indefinitely until
it is removed. A frame that is not removed (stripped) after its first
traversal around the ring is called a No Owner Frame (NOF). There are several
causes of NOFs. One example is when a transmitting station is removed (powered
down) from the ring prior to receiving its own frame back in a network of large
extent. When this happens, the frame can't be removed by the transmitting
station. Another example is when the Source Address in the frame becomes
corrupted as it passes around the network so that it does not match any
connected station's address; again, the frame does not get removed.
The occurrence of an NOF is infrequent (low probability), but the impact of an
NOF can be severe. For example, a single NOF that was a broadcast or multi-
cast frame can cause stations and attached midspeed LANs (Ethernet and Token
Ring) to be flooded with duplicate NOFs.
To solve this problem, Digital invented an algorithm called the Ring Purger.
There are two parts to the Ring Purger. The first part is a distributed
election algorithm (similar to the bridge's election process for a "root"
bridge) which elects a station to become the Ring Purger. This election
algorithm ensures that there is one and only one Ring Purger operating in the
ring. The result is that one of Digital's stations will become the ring purger
for the complete network. The ANSI Station Management (SMT) Extended Service
Frame (ESF) is used for the election protocol.
The Ring Purger cleans (purges) the ring each time it sees the token. The Ring
Purger complies with the MAC protocol, as all stations should. It waits for the
token, and captures it each time it sees it. If the Ring Purger has LLC or SMT
frames to transmit, it transmits the frames first, again following the MAC
protocol. At the end of transmitting the frames, the Ring Purger transmits
two well-formed Void frames (with both the source and destination address equal
to its station address), and then releases the token. If the Ring Purger has
no LLC or SMT frames to transmit, it transmits 2 well-formed Void frames before
releasing the token. (See Figure 4)
After transmitting the token, the Ring Purger strips all frames until it
receives one of its returning Void frames. The transmission of Void frames and
stripping until the reception of Void frames is similar to the FCIS used with
bridge stripping. If the Ring Purger receives a token, Claim frame, or Beacon
frame while waiting for its Void frame to return, it stops purging the ring
immediately. So, the Ring Purger cleans the ring of NOFs or other meaningless
frames (such as partial frames) on the ring each time the token is received.
+-----------+ +-----------+ +-----------+
| FDDI | | FDDI | | FDDI |
| Station +-----------+ Station +-----------+ Station |
| Address A +-----------+ Address B +-----------+ Address C |
| | | | | |
+----++-----+ +-----------+ +-----++----+
|| ||
|| ||
|| F D D I R I N G ||
|| ||
+----++-----+ +-----------+ +-----++----+
| FDDI | | FDDI | | FDDI |
| Station +-----------+ Station +-----------+ Station |
| Address F +-----------+ Address E +-----------+ Address D |
| | | | | |
+-----------+ +-----------+ +-----------+
Ring Purger Example:
1) Station E Elected Ring Purger
2) Station E Generates Two Void Frames with SA and DA = E
Each Time It Receives the Token
3) Station E Strips Frames Until:
Void Frames with SA and DA = E Received
or
Reset by Token, Claim, or Beacon Frame
Figure 4
The MAC access protocol used by the Ring Purger complies to the FDDI MAC
Standard in terms of when a station can transmit. It is really no different
from a station which always has 2 Void frames to transmit each time the token
passes by.
Performance Aspects
-------------------
At first glance it might seem that the Ring Purger generates a heavy load on
the ring. However, Void frames are transmitted when no one else is using the
token. As the load increases on the ring, the frequency of token rotation
decreases and therefore the number of Void frames transmitted by the Ring
Purger decreases at the same rate. Also, the Void frames will have no negative
effect on other stations, since the standard states that Void frames are not to
be copied by stations. In short, the effect of the Void frames on the usable
ring bandwidth is negligible.
For example, in the worst case, the effect on the usable ring bandwidth due to
Void frames transmitted by the Ring Purger is less than 0.22%, and this only
occurs at high load (i.e., not when the ring is idle or lightly loaded) and
with a minimum Target Token Rotation Time (TTRT). On the average, there is no
effect on the usable bandwidth at idle or low load; instead, the token is
delayed by about 5 microseconds, which is again negligible.
Conclusion
----------
The use of Void frames in both Bridge Stripping and FDDI Ring Purging yields
standards-compliant, robust solutions to two "thorny" issues that could
negatively impact the performance of an FDDI network. These additional
benefits are realized without any bandwidth or delay issues that are typically
associated with other solutions.
|