%% LyX 1.1 created this file.  For more info, see http://www.lyx.org/.
%% Do not edit unless you really know what you are doing.
\documentclass[11pt]{article}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\setlength\parskip{\medskipamount}
\setlength\parindent{0pt}
\usepackage{graphics}

\makeatletter


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
\providecommand{\LyX}{L\kern-.1667em\lower.25em\hbox{Y}\kern-.125emX\@}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands.
\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}
\setlength{\topmargin}{0.0in}
\setlength{\headheight}{0in}
\setlength{\headsep}{0.5in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{8.5in}
\setlength{\parindent}{0in}
\setlength{\parskip}{0.05in}

\usepackage{times}
\usepackage{psfig}
\usepackage{fancyheadings}


\makeatother

\begin{document}

\pagestyle{fancy} \cfoot{FDDI: \thepage}


\title{The FDDI Protocol}


\author{Norman Matloff \\
 University of California at Davis\\
         \copyright{}2001, N. Matloff}


\date{November 30, 2001}

\maketitle

\section{Overview}

One of the earliest types of local area networks was the \textbf{token ring}.
As the name implies, the nodes are connected in a ring topology with point-to-point
links. A special bit pattern called a \textbf{token} continually circles around
the ring. Whenever a node wishes to send a message, it must wait for the token
to get there. It then temporarily removes the token from the ring, sends its
message, and then places the token back on the ring so that some other node
may send.

The Fiber Distributed Data Interface (FDDI) is a newer type of token ring. It
is fast, 100 Mbps, compared to the 4 Mbps of the IBM token ring and the original
10 Mbps rate for Ethernet. This speed was leapfrogged by Fast Ethernet at 100
Mbps, and now by Gigabit Ethernet at 1000 Mbps.

But FDDI has other advantages. First, it can be used on large networks, consisting
of 500 nodes in a circumference of over 60 miles.\footnote{%
These figures are for the optical-fiber version of FDDI, which is the common
one. There are copper versions as well.
} And FDDI is fault-tolerant (see the next section).

Due to the complexity of the FDDI protocol, FDDI interface chips are expensive,
and not worth the cost for small networks. Thus FDDI's main usage has been for
large \textbf{backbone} networks that connect together a number of smaller networks.


\section{Fault Tolerance}

FDDI is also built for fault tolerance. It is actually two networks, one going
counter-clockwise and the other clockwise (as usually drawn). Normally only
the primary links, i.e. the counter-clockwise ones, are used, but if a link
or even a node goes down, the secondary links will maintain the operation of
the network.

For example, consider a four-node network, with nodes A, B, C and D (in counter-clockwise
order). Say the link from D to A is accidentally cut. Then the secondaries will
automatically activate, so that the network makes {}``U-turns{}'' at A and
D: After a frame goes from B to C to D on the primary link, for instance, it
will next go \underbar{back} to C from D on the secondary link, etc. In this
manner, we retain the ring topology after the accidental break.

\vspace{0.3cm}
{\par\centering \includegraphics{FDDI.eps} \par}
\vspace{0.3cm}


\section{Capacity Allocation}

After an FDDI node transmits its data, it will place a new token onto the ring,
immediately following the last data frame it sends.\footnote{%
The term \textbf{token} here will correspond to the somewhat older term \textbf{free}
token. In more recent literature, what was formerly called a \textbf{busy} token
is now just considered part of a data frame, and thus not referred to as a token.
} In ring network terminology, this is referred to as \textbf{early token release}
or \textbf{release after transmit} (RAT), and contrasts to the other possibility,
which is to not place a new token onto the network until the leading edge of
the sender's frame circulates back to the sender. Clearly, RAT makes better
use of network bandwidth.

FDDI distinguishes between \textbf{synchronous} and \textbf{asynchronous} traffic.
The terms are misleading, as they do not have the same meaning as in other network
contexts. Instead, the term {}``synchronous{}'' simply refers to traffic which
must be delivered in a timely manner, such as voice and video, and traffic which
can tolerate delay, such as file transfers. What FDDI does then, is allow each
node to transmit a given amount of synchronous traffic each time it gets the
token, and transmit some asynchronous traffic if there is any {}``time left
over,{}'' in a manner described below.

The heart of the FDDI approach is the setting of a Target Token Rotation Time
(TRTT), which we will denote as \( \tau _{target} \). Here the word {}``rotation{}''
refers to the time between successive visits of a token to a given node, i.e.
successive opportunities for a given node to transmit. Note that \( \tau _{target} \)
will be fixed, while the actual rotation time, \( \tau _{actual} \), will vary,
both from node to node and from cycle to cycle for the same node.

The word {}``target{}'' is key, meaning that we aim for a token to rotate
in \( \tau _{target} \) time. Actually, we will see that the rotation time
could be as long as \( 2\tau _{target} \).

Denote the nodes of the network by \( N_{i} \), i = 0,1,2...,n-1. When a network
is first brought up (or when a new node is added), the nodes negotiate a value
for \( \tau _{target} \). Each node \( N_{i} \) bids a value of \( \tau _{target} \)
that is needed for its particular applications, so the final value becomes whatever
the lowest bid turns out to be (so that all nodes have their timely-delivery
needs satisfied). At that time, each node i will be assigned a value \( \sigma _{i} \),
which will be the amount of time the node will be allowed to send synchronous
data in one turn, i.e. in one possession of the token. These amounts will satisfy
the constraint

\begin{equation}
\sigma =\sum _{i=0}^{n-1}\sigma _{i}<\tau _{target}
\end{equation}


This is a strict inequality (i.e. it uses \( < \) rather than \( \leq  \)),
with the excess consisting of components such as the time that it takes one
bit to traverse the ring. We will assume that it is the only component causing
strict inequality above. Denoting the latency for a bit to travel from the \( i^{th} \)
to the \( i+1^{st} \) node\footnote{%
Here and below, subscripts will be taken to use mod-n+1 arithmetic. Thus {}``\( N_{n} \){}''
is actually \( N_{0} \).
} by \( \beta _{i} \), we then have

\begin{equation}
\label{targetdef}
\tau _{target}=\sigma +\beta 
\end{equation}


where \( \beta =\sum _{i}\beta _{i} \).\footnote{%
The token transmission time must also be accounted for, but we are assuming
here that the token is so small that that time is negligible.
}

When a node i receives a token, it can then send according to the following
rules. First, the node calculates \( \tau _{target}-\tau _{actual} \).\footnote{%
Remember, the subtrahend here will vary from one node to another, and from one
cycle to another.
} The token is then considered either {}``early{}'' or {}``late,{}'' according
to whether \( \tau _{target}-\tau _{actual} \) is positive or negative, respectively.
Then:

\begin{itemize}
\item Rule~1. 


Node i transmits as many synchronous frames as it has waiting for transmission,
up to (but not exceeding) time \( \sigma _{i} \). 

\item Rule~2. 


If the token had arrived early, node i is then allowed send as many asynchronous
frames as it has waiting, for a total time of \( \tau _{target}-\tau _{actual} \).\footnote{%
Plus {}``a little more,{}'' meaning that the final frame sent is allowed to
cause the total asynchronous transmission time to exceed \( \tau _{target}-\tau _{actual} \).
}

\end{itemize}
Let us look at the implications of these rules. First, what is the worst-case
value of \( \tau _{actual} \)? This will occur in the situation in which in
one cycle no node sends anything, and in the next cycle each node sends the
maximum allowed.

Specifically, look at any node, say \( N_{0} \), and define time units so that
current time is 0.0. Consider a cycle starting now, i.e. with the token leaving
\( N_{0} \) now, in which the token visits every node on the ring, but none
of the nodes sends anything at all (not even synchronous data). After leaving
\( N_{0} \), the token will arrive at \( N_{1} \) at time \( \beta _{0} \),
then arrive at \( N_{2} \) at \( \beta _{0}+\beta _{1} \), and so on. (Here
and below, refer to the table to more easily keep track of what happens at \( N_{0} \)
and \( N_{1} \), for example; note that a zero value for earliness means a
late visit.)

The token will make its next visit to \( N_{0} \) at time \( \beta  \), i.e.
\( \tau _{actual}=\beta  \). Thus the token will arrive to \( N_{0} \) early,
with the amount of earliness being \( \tau _{target}-\beta =\sigma  \). 
\begin{table}
{\centering \begin{tabular}{|r||r||r|}
\hline 
token visit number &
visit time and earliness, \( N_{0} \)&
visit time and earliness, \( N_{1} \)\\
\hline 
\hline 
1 &
0.0, NA &
\( \beta _{0} \), NA \\
\hline 
2&
\( \beta  \), \( \sigma  \)&
\( \beta +\sigma _{0}+\sigma +\beta _{0} \), 0\\
\hline 
3&
\( 2\tau _{target} \) , NA&
NA, NA\\
\hline 
\end{tabular}\par}\end{table}


Since the token arrived \( \sigma  \) amount of time early, \( N_{0} \) is
now allowed to send asynchronous data for \( \sigma  \) time, and it will do
so, since we are assuming all the nodes are now on a sending binge. This means
that it will send synchronous data for \( \sigma _{0} \) amount of time, and
then send asynchronous data for \( \sigma  \) amount of time. Then \( N_{0} \)
passes the token to \( N_{1} \).

Now, at this point, what will be the value of \( \tau _{actual} \) for \( N_{1} \)?
The current time will be \( \beta +\sigma _{0}+\sigma +\beta _{0} \) (the token
arrived at \( N_{0} \) at time \( \beta  \), then \( N_{0} \) sent data for
time \( \sigma _{0}+\sigma  \), then \( N_{0} \) sent the token, which took
time \( \beta _{0} \) to reach \( N_{1} \)). The time when the token last
reached \( N_{1} \) was \( \beta _{0} \). So, \( \tau _{actual} \) would
then be

\begin{equation}
\beta +\sigma _{0}+\sigma =\tau _{target}+\sigma _{0}
\end{equation}


In other words, the token arrives at \( N_{1} \) late! Thus \( N_{1} \) is
not allowed to send any asynchronous data. But it is allowed to send synchronous
data, for \( \sigma _{1} \) amount of time, and will do so.

Continuing this reasoning, you can see that \( N_{2} \) will now not be allowed
to send any asynchronous data, but it will still send its synchronous data for
\( \sigma _{2} \) amount of time, and so on. And then, adding up the results
of the actions at all the succeeding nodes, we can see that the token will make
its next vist to \( N_{0} \) at time

\begin{equation}
\beta +\sigma +\sum _{i}(\sigma _{i}+\beta _{i})=2\tau _{target}
\end{equation}


Since the previous visit to \( N_{0} \) had been at time \( \beta  \), that
means

\begin{equation}
\tau _{actual}=2\tau _{target}-\beta \leq 2\tau _{target}
\end{equation}


So an upper bound for \( \tau _{actual} \) is \( 2\tau _{target} \). (And
if \( \beta  \) is small relative to \( \sigma  \), the inequality above will
essentially be an equality.)

In other words, each node is secure in the knowledge that it will need to wait
no longer than \( 2\tau _{target} \) to have a chance to send.\footnote{%
On the other hand, keep in mind that the queue within a node could be quite
long, and thus any given frame may have to wait much longer than this to get
out onto the network.
}

Moreover, in the scenario outlined above, all nodes will find that the \underbar{next}
time the token pays them a visit, it will be not early. That means that they
will not be allowed to send any asynchronous frames in this next turn, so that
the scenario could not repeat itself in consecutive turns.

We can also see that the value of \( \tau _{actual} \) at one node will have
a direct impact on the value at the node's immediate downstream neighbor. For
example, using the following argument we can see that if there is no synchronous
traffic, then \( \tau _{actual} \) will be at most \( \tau _{target}+\phi  \),
where \( \phi  \) is an assumed upper bound on the amount of asynchronous traffic
a node will ever have available to send at a given time.

Here is how that comes about: Consider consecutive nodes A and B, and look at
two consecutive rotations of the token. Say the token visits A at time \( t_{A1} \),
whereupon A transmits asynchronous data for time \( X_{A1} \), after which
it sends the token to B. Denote the propagation delay between A and B by \( \alpha  \).

Then the token arrives at B at time

\begin{equation}
\label{b1}
t_{B1}=t_{A1}+X_{A1}+\alpha 
\end{equation}


B then sends asynchronous data for time \( X_{B1} \). Later, at time \( t_{A2} \),
the token makes its next visit to A; A sends for time \( X_{A2} \), and then
sends the token to B, arriving at time

\begin{equation}
\label{b2}
t_{B2}=t_{A2}+X_{A2}+\alpha 
\end{equation}


Let \( \tau _{actual,A} \) be the target rotation time for A in this situation,
i.e.

\begin{equation}
\label{taua}
\tau _{actual,A}=t_{A2}-t_{A1}
\end{equation}


and define \( \tau _{actual,B} \) similarly for B:

\begin{equation}
\label{taub}
\tau _{actual,B}=t_{B2}-t_{B1}
\end{equation}


Now, remember, we are trying to show that

\begin{equation}
\label{induction}
\tau _{actual}\leq \tau _{target}+\phi 
\end{equation}


for all nodes if there is no synchronous traffic. With this goal in mind, suppose
that this inequality held for node A in the situation outlined above, i.e.

\begin{equation}
\tau _{actual,A}\leq \tau _{target}+\phi 
\end{equation}


Then what about \( \tau _{actual,B} \)? Well, by performing some algebra on
Equations (\ref{b1}), (\ref{b2}), (\ref{taua}) and (\ref{taub}), we would
have

\begin{equation}
\label{baxx}
\tau _{actual,B}=\tau _{actual,A}+X_{A2}-X_{A1}
\end{equation}


Now consider two cases, the first one being that \( \tau _{actual,A} \) is
greater than \( \tau _{target} \). In this case, the token's second arrival
to A is late, so A is not allowed to send any asynchronous data, i.e. \( X_{A2}=0 \).
Thus, Equation (\ref{baxx}) implies that

\begin{equation}
\label{case1}
\tau _{actual,B}=\tau _{actual,A}-X_{A1}\leq \tau _{actual,A}
\end{equation}


with the inequality coming from the fact that \( X_{A1}\geq 0 \). Thus Equation
(\ref{case1}) shows that if Equation (\ref{induction}) holds for A then it
holds for B too.

In the second case, where \( \tau _{actual,A} \) is less than \( \tau _{target} \),
then from Equation (\ref{baxx})

\begin{equation}
\tau _{actual,B}=\tau _{actual,A}+X_{A2}-X_{A1}\leq \tau _{target}+X_{A2}-X_{A1}\leq \tau _{target}+\phi 
\end{equation}


where the last inequality is due to the fact that each of \( X_{A2} \) and
\( X_{A1} \) is between 0 and \( \phi  \) and thus their difference is no
more than \( \phi  \). So, in this case again we have that \ref{induction}
holds for B if it does for A.

We are almost done, except that we must deal with the word {}``if{}'' in the
last sentence. All we have shown so far is that once one node satisfies (\ref{induction}),
the next node will, and thus so will the next node after that, and so on. But
when the network first comes up and no node has anything to send, the first
rotation of the token, taking time \( \beta , \) will indeed take less than
\( \tau _{target} \) (see Equation (\ref{targetdef})), so that starts the
ball rolling. The argument above shows that \( \tau _{actual} \) will continue
to be less than \( \tau _{target}+\phi  \) after that, for all nodes and all
cycles of the token around the ring, even though \( \tau _{actual} \) will
vary within the ranger below this value.
\end{document}