\documentclass[10pt,twocolumn]{article}
\usepackage[dvips]{epsfig,graphicx}
\usepackage[]{subfigure}
\usepackage[]{latexsym}

\newcommand{\Hi}{{\cal H}^\infty}
\hoffset -0.5in
\voffset -0.5in % for LaserWriter

% \leftmargin -0.5in
\topmargin -0.5in
\textheight 9.5in
\textwidth 7.5in
\setlength{\columnsep}{0.25in}

\parindent 0pt
\parskip 1ex

\newcommand{\U}[1]{\underline{\hspace{#1}}}
\newcommand{\LA}{\mbox{$\leftarrow$}}
\def\psminipage(#1,#2)#3{
\leavevmode
\includegraphics \times [bb = 0 0  8.5in 11in,angle=270,scale = 0.5,clip]{#3}
\typeout{Including PostScript file #3}
}

%This macro is used for figures in ERICA/figs directory
\def\includefige#1#2#3#4#5{
\begin{figure}[htb]
\centerline{\epsfig{height=#1,width=#2,angle=-90,figure=figs/#3.eps}}
\caption{#4}
\label{#5}
\end{figure}
}

%This macro is used for flow charts
\def\includefigf#1#2#3#4#5{
\begin{figure}[htb]
\centerline{\epsfig{height=#2,width=#1,angle=0,figure=figs/#3.eps}}
\caption{#4}
\label{#5}
\end{figure}
}

%This macro is used for figures in Qcontrol/figs directory
\def\includefigq#1#2#3#4#5{
\begin{figure}[htb]
\centerline{\epsfig{height=#1,width=#2,angle=-90,figure=../QCTRL_REPORTS/figs/#3.eps}}
\caption{#4}
\label{#5}
\end{figure}
}

\def\putfigq#1#2#3#4{
\begin{figure}[htb]
\begin{center}
\leavevmode
\includegraphics \times [bb = 0 0  #4  800, 
width=2.5in,angle=270,clip ]{../QCTRL_REPORTS/figs/#3.eps}
\end{center}
\caption{#2}
\label{#1}
\end{figure}
}

\def\putfigsc#1#2#3#4#5{
   \def\goodgap{                 
     \hspace{\subfigtopskip}
     \hspace{\subfigbottomskip}}
   \begin{figure}         
     \centering                      
     \begin{tabular}[t]{cc}
       \subfigure[Allowed Cell Rate (ACR)]{
          \includegraphics[height=3.0in,angle=270]{figs/#1/r.ps}
       } 
       \subfigure[Queue Length]{
          \includegraphics[height=3.0in,angle=270]{figs/#1/q.ps}
       }\\   
       \\
       \subfigure[Transmitted Cell Rate]{
          \includegraphics[height=3.0in,angle=270]{figs/#2/r.ps}
       }        
       \subfigure[Queue Length]{
          \includegraphics[height=3.0in,angle=270]{figs/#2/q.ps}
       }
     \end{tabular}
     \caption{#3} 
     \label{#4}
   \end{figure}                        
  \clearpage
}

\def\putfigsb#1#2#3#4#5{
   \def\goodgap{                 
     \hspace{\subfigtopskip}
     \hspace{\subfigbottomskip}}
   \begin{figure}         
     \centering                      
     \begin{tabular}[t]{cc}
       \subfigure[Transmitted Cell Rate (basic ERICA)]{
          \includegraphics[height=3.0in,angle=270]{/n/fish/0/cong/tests/param/1996/ERICA/#1/r.ps}
       } 
       \subfigure[Cells Received (basic ERICA)]{
          \includegraphics[height=3.0in,angle=270]{/n/fish/0/cong/tests/param/1996/ERICA/#1/t.ps}
       }\\   
       \\
       \subfigure[Transmitted Cell Rate]{
          \includegraphics[height=3.0in,angle=270]{/n/fish/0/cong/tests/param/1996/ERICA/#2/r.ps}
       }        
       \subfigure[Cells Received]{
          \includegraphics[height=3.0in,angle=270]{/n/fish/0/cong/tests/param/1996/ERICA/#2/t.ps}
       }
     \end{tabular}
     \caption{#3} 
     \label{#4}
   \end{figure}                        
  \clearpage
}

\def\putfigsa#1#2#3{
   \def\goodgap{                 
     \hspace{\subfigtopskip}
     \hspace{\subfigbottomskip}}
   \begin{figure}         
     \centering                      
     \begin{tabular}[t]{cc}
       \subfigure[Allowed Cell Rate (ACR)]{
          \includegraphics[height=3.0in,angle=270]{figs/#1/r.ps}
       } 
       \subfigure[Bottleneck Queue Lengths]{
          \includegraphics[height=3.0in,angle=270]{figs/#1/allq.ps}
       }\\   
       \\
       \subfigure[Bottleneck Link Utilizations]{
          \includegraphics[height=3.0in,angle=270]{figs/#1/allu.ps}
       }        
%       \subfigure[Cells Received]{
%          \includegraphics[height=3.0in,angle=270]{figs/#1/t.ps}
%       }
     \end{tabular}
     \caption{#2} 
     \label{#3}
   \end{figure}                        
}

\def\newputfigsa#1#2#3{
   \def\goodgap{                 
     \hspace{\subfigtopskip}
     \hspace{\subfigbottomskip}}
   \begin{figure*}         
     \centering                      
     \begin{tabular}[t]{ccc}
       \subfigure[Allowed Cell Rate (ACR)]{
          \includegraphics[height=2.3in,angle=270]{figs/#1/r.ps}
       } 
       \subfigure[Bottleneck Queue Lengths]{
          \includegraphics[height=2.3in,angle=270]{figs/#1/allq.ps}
       }   
       \subfigure[Bottleneck Link Utilizations]{
          \includegraphics[height=2.3in,angle=270]{figs/#1/allu.ps}
       }        
%       \subfigure[Cells Received]{
%          \includegraphics[height=3.0in,angle=270]{figs/#1/t.ps}
%       }
     \end{tabular}
     \caption{#2} 
     \label{#3}
   \end{figure*}                        
}

\def\putfigsx#1#2#3{
   \def\goodgap{                 
     \hspace{\subfigtopskip}
     \hspace{\subfigbottomskip}}
   \begin{figure}         
     \centering                      
     \begin{tabular}[t]{cc}
        \subfigure[VBR Rate]{
          \includegraphics[height=2.1in,angle=270]{figs/#1/vbru.ps}
       }
       \subfigure[Allowed Cell Rate (ACR)]{
          \includegraphics[height=2.1in,angle=270]{figs/#1/r.ps}
       } 
       \subfigure[Bottleneck Queue Length]{
          \includegraphics[height=2.1in,angle=270]{figs/#1/abrq.ps}
       }

\\   
       \\
       \subfigure[Bottleneck Link Utilization]{
          \includegraphics[height=2.1in,angle=270]{figs/#1/lnu.ps}
       }        
%       \subfigure[TCP Congestion Window]{
%          \includegraphics[height=2.1in,angle=270]{figs/#1/cw.ps}
%       }
       \subfigure[TCP Send Sequence Numbers]{
          \includegraphics[height=2.1in,angle=270]{figs/#1/sn.ps}
       }
     \end{tabular}
     \caption{#2} 
     \label{#3}
   \end{figure}                        
}


\def\newputfigsx#1#2#3{
   \def\goodgap{                 
     \hspace{\subfigtopskip}
     \hspace{\subfigbottomskip}}
   \begin{figure*}         
     \centering                      
     \begin{tabular}[t]{cc}
        \subfigure[VBR Rate]{
          \includegraphics[height=2.3in,angle=270]{figs/#1/vbru.ps}
       }
       \subfigure[Allowed Cell Rate (ACR)]{
          \includegraphics[height=2.3in,angle=270]{figs/#1/r.ps}
       } 
       \subfigure[Bottleneck Queue Length]{
          \includegraphics[height=2.3in,angle=270]{figs/#1/abrq.ps}
       }

\\   
       \\
       \subfigure[Bottleneck Link Utilization]{
          \includegraphics[height=2.3in,angle=270]{figs/#1/lnu.ps}
       }        
%       \subfigure[TCP Congestion Window]{
%          \includegraphics[height=2.1in,angle=270]{figs/#1/cw.ps}
%       }
       \subfigure[TCP Send Sequence Numbers]{
          \includegraphics[height=2.3in,angle=270]{figs/#1/sn.ps}
       }
     \end{tabular}
     \caption{#2} 
     \label{#3}
   \end{figure*}                        
}


\def\putfigsaq#1#2#3#4{
   \def\goodgap{                 
     \hspace{\subfigtopskip}
     \hspace{\subfigbottomskip}}
   \begin{figure}         
     \centering                      
     \begin{tabular}[t]{cc}
       \subfigure[Transmitted Cell Rate]{
          \includegraphics[height=3.0in,angle=270]{/n/fish/0/cong/tests/param/1996/ERICA+/#1/r.ps}
       } 
       \subfigure[Queue Length]{
          \includegraphics[height=3.0in,angle=270]{/n/fish/0/cong/tests/param/1996/ERICA+/#1/q.ps}
       }\\   
       \\
       \subfigure[Link Utilization]{
          \includegraphics[height=3.0in,angle=270]{/n/fish/0/cong/tests/param/1996/ERICA+/#1/u.ps}
       }        
       \subfigure[Cells Received]{
          \includegraphics[height=3.0in,angle=270]{/n/fish/0/cong/tests/param/1996/ERICA+/#1/t.ps}
       }
     \end{tabular}
     \caption{#2} 
     \label{#3}
   \end{figure}                        
  \clearpage
}

%\renewcommand{\baselinestretch}{1.5}

\begin{document}

\begin{center}

{\large \bf The ERICA Switch Algorithm for ABR Traffic Management in
ATM Networks\footnote{This work was supported by NSF Contract \#9628438}}\\
%Ram Viswanathan \footnote{Ram Viswanathan is now in Microsoft Corp., WA}
Shivkumar Kalyanaraman\footnote{Shivkumar Kalyanaraman is now in
Department of ECSE, Rensselaer Polytechnic Institute, Troy, NY 12180-3590},
Raj Jain,  Sonia Fahmy\footnote{Sonia Fahmy is now with
Department of Computer Science, Purdue University, Indiana.}, Rohit
Goyal\footnote{Rohit Goyal  is at Nexabit Networks (Lucent), Massachusetts.} and Bobby Vandalore\\
The Ohio State University, Department of CIS\\
Columbus, OH 43210-1277\\
%%Phone: 614-292-3989, Fax: 614-292-2911\\
Email:  {\em shivkuma}@ecse.rpi.edu, \{{\em jain, fahmy, goyal, vandalor}\}@cis.ohio-state.edu
\end{center}

{\bf Abstract}

This paper describes the ``Explicit Rate Indication for Congestion
Avoidance (ERICA)'' scheme for rate-based feedback from ATM switches.
In ERICA, the switches monitor their load on each link, determine a
load factor, the available capacity, and the number of currently
active virtual channels.  This information is used to advise the
sources about the rates at which they should transmit.  The algorithm
is designed to achieve high link utilization with low delays and fast
transient response. It is also fair and robust to measurement errors
caused by the variations in ABR demand and capacity. We present
performance analysis of the scheme using both analytical arguments and
simulation results.  The scheme is being considered for implementation
by several ATM switch manufacturers.

\section{Introduction}

The key new feature of ATM that distinguishes it from other networking
technologies is that it provides very sophisticated traffic
management.  ATM networks use connection admission control, traffic
shaping, policing, selective discard, packet discard, and explicit
feedback to manage the traffic. Traffic management is particularly
important at high speeds since even a short-term overload at these
speeds can lead to significant queues and data loss. 

ATM networks provide several services. Of these, the available bit
rate (ABR) service is ideal for data. In this service, switches use an
option to provide an explicit rate feedback to the sources and sources
control their traffic accordingly.  The ATM Forum Traffic Management
Specification \cite{tm4} contains detailed rules for the ABR source
and destination end systems.  The rules for switches are also
specified.  The switch behavior, however, is only coarsely specified
so that various vendors can implement their own switch rate allocation
algorithms and distinguish their products. The switch rules simply
ensure that switches from different vendors will inter-operate, though
the operation may not be optimal.  Several switch algorithms have been
developed \cite{ifip}-\cite{dissert}.  This paper describes one of the
earliest of such switch algorithms.

The explicit rate indication for congestion avoidance (ERICA)
algorithm was presented at the ATM Forum in February 1995.  Since
then, its performance has been independently studied in many papers
\cite{phantom,hkust,murali:fmmra}. Also, we have incorporated several
modifications into the algorithm~\cite{dissert,erica-patent}. This
paper provides a consolidated description and a performance analysis
of the algorithm.  

The paper is organized as follows. The next two sections examine the
ABR service, and describe the switch model and design
goals. Section~\ref{sec:erica-algo} describes the algorithm and
examines the tradeoffs involved in selecting the algorithm metrics and
parameters. Section~\ref{sec:simulations} presents representative
simulations to show the performance of the scheme under strenuous
conditions. We also present limited analytical arguments of
the convergence of the algorithm in appendix~\ref{app:proof}.

\section{The ABR Control Mechanism}

According to the ATM Forum specifications, ATM networks currently 
offer five service categories: constant bit rate (CBR),
real-time variable bit rate (rt-VBR), non-real time variable bit rate
(nrt-VBR), available bit rate (ABR), and unspecified bit rate
(UBR). Of these, ABR and UBR are designed for data traffic exhibiting
bursty unpredictable behavior. 

The UBR service is simple and does not give sources any guarantees.
The network elements try to improve throughput and reduce loss using
intelligent buffer allocation \cite{goyal-fba}, cell drop \cite{epd}
and scheduling. The ABR service provides better service for data
traffic by periodically advising sources about the rates at which they
should be transmitting.  The switches monitor their load, and divide
the available bandwidth fairly among active flows. This allows
competing sources to get a fair share of the bandwidth while also
allowing the link to be fully utilized. The feedback from the switches
to the sources is indicated in resource management (RM) cells, which
are periodically generated by the sources and turned around by the
destinations (refer to figure \ref{fig:rmcell}).

\includefige{200pt}{120pt}{rmcell}{RM cell path}{fig:rmcell}

The RM cells contain the source's current cell rate (CCR) and several
fields that can be used by the switches to provide feedback to the
source. These fields are: Explicit Rate (ER), Congestion Indication
(CI) flag, and No Increase (NI) flag. The ER field indicates the rate
that the network can support at the particular instant in time.  When
starting at the source, the ER field is usually set to the peak cell
rate, and the CI and NI flags are clear. On the path, each switch
reduces the ER field to the maximum rate it can support, and sets CI
or NI if necessary~\cite{tutorial}.

The RM cells flowing from the source to the destination are called
forward RM cells (FRMs) while those returning from the destination to
the source are called backward RM cells (BRMs).  When a source
receives a BRM, it computes its allowed cell rate (ACR) using its
current ACR, the CI and NI flags, and the ER field of the RM cell
\cite{src-rule-paper}.

\section{Switch Model}
\label{sec:switch-model}

% needed: figure, and additional references
% ~\ref{fig:model}

Our switch model is shown in figure~\ref{fig:swmodel}. Each service
category has a separate first-in, first-out (FIFO) output queue which
feeds to the output link under the control of a scheduling
mechanism. The ERICA algorithm works at every ABR queuing point
(assumed to be at the output for this paper). For simplicity, we
assume that there are at most two classes (VBR and ABR) and ABR has
the lower priority, i.e., it gets the left-over capacity after VBR
cells are transmitted.  We do not consider the case of ABR virtual
connections (VCs)
guaranteeing non-zero minimum cell rates in this paper. Techniques for
adapting a switch scheme to guarantee such rates are suggested in
\cite{chiussi:dmrca}.  Other issues not addressed in this paper
include the effect of more complex queuing strategies like per-VC
queuing, network segmentation using the virtual source/virtual
destination (VS/VD) option \cite{tm4}, and multipoint ABR
connections. Some of these issues are addressed in
\cite{dissert,sonia-multicast}.

\includefige{200pt}{150pt}{swmodel}{Switch Model}{fig:swmodel}

In ERICA, the time is divided into consecutive equal-sized slots called
{\em ``switch averaging intervals.''}  As shown in
figure~\ref{fig:swmodel}, the measured load in the forward direction
in each slot is used to provide feedback in the reverse direction in
the next slot. The feedback may be computed at the end of each slot
or when a backward RM cell (BRM) is received.

One of the design features of ERICA is that switches 
give {\em at most one} feedback value per flow
during any averaging interval. This precludes the switch from giving
multiple conflicting feedback indications in a single averaging
interval using the same control values. 

%Further, since there can be
%multiple switches on a VC's path, the final allocation given to a flow
%is the minimum of allocations at various switches along the path.

%Although performance is better when all the switches implement the same
%switch algorithm \cite{nina-infocom}, the traffic management
%standard \cite{tm4} allows switches from multiple vendors to
%interoperate. 

ERICA gives feedback only in the explicit rate field in
the RM cell. It is possible to additionally throttle or moderate the
sources by setting the CI and NI bits in the RM cell using policies
suggested by several other schemes \cite{phantom, chiussi:dmrca}.

\subsection{Design Goals}
\label{sec:design-goals}

In designing ERICA, our main goals were to maximize link utilization,
minimize queuing delays, achieve fair allocation, reduce transient
response time, and achieve stable and robust operation. Each of these
goals is explained below.

%We provide a qualitative description of design goals in the
%steady-state and under transient conditions. Rigorous quantitative
%formulations are under study by several researchers
%\cite{h-infinity,basar,lofti,rohrs}. Therefore, the ERICA algorithm as
%presented in this paper should be viewed as an engineering solution to
%the complex problem of rate-based feedback control, with limited
%analytical and simulation arguments.

\begin{description}
\item[Utilization:] Our first goal was to maximize the link
utilization $\rho(t)$. This is done by allocating as much of the
available capacity to active ABR flows as possible.  The entire link
capacity that is not used by the higher priority VBR and CBR service
categories is potentially available to ABR.

ERICA tracks ABR utilization using a metric called ``load factor''
($z$, refer to section~\ref{sec:load-factor}). Specifically, $z$ is
proportional to the ratio of the ABR input rate to the ABR
capacity. Using $z$, the ERICA utilization goal is a {\em
steady-state} operating point in the neighborhood of $z = 1$. In
certain configurations, this goal cannot be realized for all
bottlenecks, in which case, the maximization of $z$ (where $z \le 1$)
is desired for those bottlenecks.

%If the system
%has {\em no steady state}, the goal of ERICA is to give highest
%priority for maximizing the average ABR utilization.  For the latter
%case, note that if the aggregate demand is consistently small, maximum
%utilization cannot be achieved. Further, the utilization metric gives
%only a partial picture of efficiency. Ideally, an ``efficient'' scheme
%should also control queuing delays within acceptable limits (discussed
%next).

\item[Queuing Delay:] High link utilization can result in large queues
and long delays.  The instantaneous utilization $\rho(t)$ is unity when
a large queue backlog exists at the bottleneck.  Our efficiency goal is
to maximize the link utilization while keeping the steady-state
queuing delay under a target maximum value.
%A special case of this
%goal occurs when the steady state queuing delay equals the target
%value.  
The concept of maximizing throughput (utilization) and
minimizing delay is known as ``congestion avoidance''
\cite{Jain88}. In ERICA, the definition of congestion avoidance
has been broadened to include the goal of reducing the delay.
When the queuing delay is more than the target,
allocations are reduced so that queue size decreases. 

%Note that our definition weakens the queuing delay
%constraint in congestion avoidance. The ERICA algorithm factors the
%queuing delay into the the load factor metric $z$, such that the
%steady queuing delay constraint is achieved only if $z$ is in the
%neighborhood of unity.

%Observe
%that our model replaces the delay minimization criterion in congestion
%avoidance with a delay target criterion.  The motivation for this goal
%is to allow the system a ``pocket of cells'' which can keep a link
%temporarily utilized when capacity suddenly becomes available. Note
%that when the system is in a state of high variation, we may never
%achieve the target queuing delay because the system itself has no
%steady state. Under these conditions, the aim is to keep the average
%utilization high, the average queue size small (preferably under the
%target value), and prevent queuing delays from becoming unbounded.

%In a configuration with $n$ contending sources, where the
%$i$th source is allocated a bandwidth $x_{i}$, the allocation vector
%$\{x_{1}, x_{2}, \ldots, x_{n}\}$ is said to be feasible if all link
%load levels are less than or equal to 100\%. If we order the elements
%of the vector in ascending order, then the max-min allocation is
%defined as the vector which is lexicographically the largest among the
%set of vectors. 

\item[Fairness:] A commonly used criterion for describing fairness is
the {\em max-min allocation} \cite{mit}.  Among the allocation vectors
(with elements in a descending order) that result in link utilizations
less than or equal to 100\%, the lexicographically largest vector is
the max-min allocation.  In simple terms, the goal of max-min
allocation is to give equal shares of a resource to all contending
sources. However, if some sources cannot use their shares (since they
are constrained at some other bottleneck), they are given the maximum
share that they can use, and the left-over is available for equal
allocation to other contending sources.  This process can be shown to
lead to max-min allocation, provided the source demands are fixed and
non-infinite. Several schemes including ERICA
\cite{icc,eprca,chiussi:dmrca} use this method and search for a
``maximum equal share'' value to allocate to all contending sources.  In
ERICA, fairness is sought only after efficiency has been achieved,
that is, the load factor $z$ is in the neighborhood of unity. If the
load is too high or too low, rates for all sources are decreased or
increased so that efficiency is rapidly achieved.
\end{description}

%For the design of ERICA we use a
%weaker notion of max-min fairness.  Specifically, our steady state
%fairness goal is to allocate the {\em maximum possible equal share,
%subject to the constraint that the load factor ($z$) is in the
%neighborhood of unity}. The ATM Forum has also specified several
%fairness definitions for cases when ABR VCs have non-zero Minimum Cell
%Rates (MCRs) \cite{tm4}.

%It should be noted that fairness is a long-term concept, i.e., if two
%sources send traffic for a sufficiently long time (like two large file
%downloads), then their average rates of transfer should be
%max-min. During system transients, the max-min balance may be
%disturbed, but the system should converge back to max-min rates if no
%further transient conditions occur. However, a service class such as
%ABR (whose capacity and demand vary dynamically) may {\em always} be
%in a transient state. If the system has only persistent sources, but
%its capacity varies, fairness can be measured over the long-term using
%average source rates. However, if the demand fluctuates as well, there
%is currently no known model for quantifying fairness.
In addition to the above ``steady state'' goals, ERICA aims to achieve
the following goals:
\begin{description}
\item[Stability and Transient Performance:] A {\em stable} system is
     one which can re-establish its steady state after
     perturbations. The {\em transient performance} of the scheme
     determines how quickly the steady state is re-established. 
%For example,
%     the queue length should not be unbounded, or the average
%     utilization should not be very low if the average demand is not
%     low.

\item[Robustness:] In cases where the system has {\em no steady-state}
(e.g., due to persistent variation in capacity and demand), the scheme
should be robust. This means that its essential performance metrics
should not degrade to unacceptable levels.
%ERICA aims to
%provide a graceful degradation of steady-state goals, and its
%parameters are tunable to provide a desired degree of robustness.
\end{description}

We emphasize that ERICA is an engineering solution which incorporates
these design goals. We provide limited analytical arguments and
simulations to support our performance claims. 
%It should be noted that
%the general problem of building a mathematical framework incorporating
%these goals and proving that algorithms meet or do not meet these
%specifications is an open problem.  Preliminary work on building a
%mathematical formulation of the general rate-based control problem
%incorporating these goals may be found in \cite{h-infinity} and
%references therein.  This paper also does not address the issues
%of scheduling, policing, buffer allocation, cell drop policies and
%interaction with transport layers in this paper. References
%\cite{dissert,goyal-fba} look at some of these issues in greater
%detail.
                

\section{The ERICA Algorithm}
\label{sec:erica-algo}

The ERICA algorithm periodically monitors the load on each link and
determines 
the ABR capacity, the load factor ($z$), and
the number of
active virtual connections ($N$) during each ``averaging
interval.'' 

%Recall that the measurements are made in the forward
%direction, whereas the feedback is given in RM cells going in the
%reverse direction. At most one new feedback per source is given in any
%averaging interval.  
The complete pseudo-code including all features of ERICA, is given
in~\cite{dissert}.  Below we present the key steps in ERICA as a
pseudo-code.  The variable MaxAllocPrevious (or MaxAllocPrev.,
abbreviated) represents the maximum allocation given during the
previous averaging interval to any source transmitting to this output
link.  Similarly, MaxAllocCurrent (or MaxAllocCurrent., abbreviated)
is used to determine the maximum allocation given to any source so far
in the current averaging interval.


{\bf Initialization:}

MaxAllocPrevious $\LA$ MaxAllocCurrent $\LA$ FairShare

{\bf End of Averaging Interval:}
\begin{eqnarray}
\mbox{Total ABR Cap.} & \LA & \mbox{Link Cap.} - \mbox{VBR
Cap.} \label{eq:totalcap}\\
\mbox{Target ABR Cap.} & \LA & Fraction \times \mbox{Tot. ABR
Cap.}
\label{eq:targetcap}\\
z  & \LA & \frac{\mbox{ABR Input Rate}}{\mbox{Target ABR Cap.}} \label{eq:z}\\
\mbox{FairShare} & \LA & \frac{\mbox{Target ABR
Capacity}}{\mbox{Number of Active VCs}} \label{eq:fs} \\
\mbox{MaxAllocPrevious} & \LA & \mbox{MaxAllocCurrent} \label{eq:maxprev}\\
\mbox{MaxAllocCurrent}  & \LA & \mbox{FairShare} \label{eq:maxcurrent}
\end{eqnarray}

{\bf When an FRM is received:}

CCR[VC] $\LA$ CCR\_in\_RM\_Cell

{\bf When a BRM is received:}
\begin{eqnarray}
\mbox{VCShare} \hspace*{-0.1in}& \LA & \hspace*{-0.1in}\frac{CCR[VC]}{z} \label{eq:vcshare}\\
\mbox{IF}~(z > 1+ \delta) \hspace*{-0.1in}& &\hspace*{-0.1in} \nonumber \\
\mbox{THEN ER}\hspace*{-0.1in}& \LA &\hspace*{-0.1in} \mbox{Max (FairShare, VCShare)} \label{eq:max1}\\
\mbox{ELSE ER}\hspace*{-0.1in}& \LA &\hspace*{-0.1in} \mbox{Max (MaxAllocPrev., VCShare)} \label{eq:max2}\\
\mbox{MaxAllocCur.}\hspace*{-0.1in}& \LA &\hspace*{-0.1in}  \mbox{Max (MaxAllocCur.,ER)} \label{eq:updatecurrent}\\
\mbox{IF (ER} > \mbox{FairShare} \hspace{-0.35in}& & \mbox{AND } \mbox{CCR[VC]} < \mbox{FairShare)}
 \nonumber \\
\mbox{THEN ER}\hspace*{-0.1in}& \LA & \hspace*{-0.1in}\mbox{FairShare} \label{eq:fsfirst}\\
\mbox{ER$_{RM\_Cell}$}\hspace*{-0.1in}& \LA &
\hspace*{-0.1in}\mbox{Min (ER$_{RM\_Cell}$, ER,} \nonumber \\ 
& & \mbox{\hspace{0.25in}}\mbox{Target ABR Cap.)} \label{eq:rmcell}
\end{eqnarray}


This pseudo-code achieves the goals of efficiency, fairness, and bounded delay
as explained next.

\subsection{Efficiency: Using the Load Factor Metric}
\label{sec:load-factor} 

The key metric used in ERICA is the load factor ($z$) which
is the ratio of the measured input rate at the
port to the target ABR capacity, as given by equation~(\ref{eq:z}):
\[z \LA \frac{\mbox{ABR Input Rate}}{\mbox{Target ABR Capacity}}\]

The target ABR capacity is a fraction of the total ABR capacity
(equation~(\ref{eq:targetcap})), where the fraction may be determined
based upon 
queuing delays (refer to section~\ref{sec:qcontrol}). The load factor is a
compact and accurate congestion indicator, and is arguably better for
rate-based schemes than using queue length alone \cite{osu}.

The load factor is used in ERICA with the goal of driving the system towards an
{\em efficient operating point, defined as the neighborhood of $z = 1$}.  
The simplest way to achieve efficiency is to reduce each VC's activity by
a factor of $z$. In other words,
each VC's allocation (``VCShare'' in the pseudo-code above)
is set to the VC current cell rate (CCR) divided by the load factor $z$, or
$\frac{CCR[VC]}{z}$.  Here, CCR is the estimate of the source current
rate. CCR may be 
read from the forward RM cells of the VC, or measured by the
switch. Either way, the CCR value is stored in a table and used for
this calculation. 
%The motivation behind using the VCShare term is that
%in a symmetric synchronous feedback system (all sources get feedback
%and respond simultaneously) with a single bottleneck and unconstrained
%sources, the allocation VCShare drives the system to the neighborhood
%of $z =1$ in a single cycle. 
The analytical arguments given in the
appendix show that this technique does drive the system
to the neighborhood of $z=1$.

Though VCShare can be used to achieve efficiency, it may not be a fair
allocation.  A mechanism is required to equalize the rate allocations,
while ensuring that the bottleneck load factor remains in the
neighborhood of unity. This is the topic of the following section.

% {\bf Motivation:} The efficiency goal of ERICA is bring the bottleneck
%to an operating point where the load factor ($z$) is in the
%neighborhood of unity. In the ERICA algorithm, the measured load
%factor (also referred to as ``overload factor'' or ``overload'') is
%used as an indicator of the congestion level of the link. An
%alternative indication of congestion used by other schemes is queue
%length \cite{eprca,chiussi:dmrca}. As discussed in our earlier work
%\cite{osu}, queue length is an imprecise indicator of congestion in a
%rate-based flow control system. However, we show in
%section~\ref{sec:qcontrol} that it can be used for limiting queuing
%delays.

\subsection{Max-Min Fairness: Equalizing Allocations}
\label{sec:max-min}

%As described in section~\ref{sec:design-goals}, ERICA attempts to
%achieve a weaker notion of max-min fairness where each contending
%source is allocated the maximum possible equal share, subject to the
%constraint that the load factor is in the neighborhood of unity. This
%notion is also used by several other algorithms (peg:
%\cite{icc,eprca}). The stronger notion of fairness (based upon the
%lexicographic ordering definition) is attempted in algorithms like
%\cite{mit,ifip}.

One way to equalize allocations is to calculate the {\em maximum} of
the VCShare values and assign this maximum value to all sources.  This
can result in sharp load changes (and extended periods of
overload). For example, consider the case when the allocation of N
sources are ($C - n\epsilon, \epsilon, ..., \epsilon$), where
$\epsilon$ and $n\epsilon$ are negligibly small. The load factor is
close to unity (assuming no prior queue buildups). The maximum of
these allocations is $C - n\epsilon$, which we call
``MaxAllocPrevious'' referring to the fact that the maximum is
calculated in the previous cycle and used in the next cycle. In the
next cycle, the allocations based upon this maximum value would be:
($C - n\epsilon, C - n\epsilon, ..., C - n\epsilon$), leading to a
load factor of almost n. To avoid this,
%The
%engineering assumption in ERICA is that real systems will approach
%such an allocation if the convergence process is controlled. Maximum
%equal share probing in done by other schemes, albeit, using parametric
%techniques like exponential averaging \cite{eprca,icc,chiussi:dmrca}.
%A disadvantage with the proposed equalizing technique in an
%asynchronous feedback system with different delays is the
%possibility of sharp load changes and extended periods of overload.
ERICA uses a two step process. A variable, ``FairShare,'' is computed
as the ratio of the target ABR capacity and the number of active
connections. If a VC is initially sending at a rate below FairShare,
it is not allowed to increase its rate to MaxAllocPrevious in the
current cycle. In particular, all sources sending below the FairShare
are allowed to rise to FairShare, and those sending above FairShare
are allowed to rise to MaxAllocPrevious. Therefore a VC sending at a
rate below FairShare would take two cycles (steps) to reach the
maximum possible allocation.


%``FairShare,'' which guarantees {\em minimum fairness} to contending
%sources. ERICA allows any source sending at a rate below the
%$FairShare$ to rise to $FairShare$ at every feedback opportunity, {\em
%but not more than $FairShare$ in the first cycle}
%(equation~(\ref{eq:fsfirst})).  FairShare is computed at the end of an
%averaging interval as in equation~(\ref{eq:fs}):
%\[\mbox{FairShare} \LA \frac{\mbox{Target ABR Capacity}}{\mbox{Number of Active VCs}}\]

These features and mechanisms (VCShare, rate equalization, at least
FairShare, at most FairShare if rate is low) are incorporated into
the ERICA algorithm as presented in equations~(\ref{eq:vcshare})
through~(\ref{eq:fsfirst}). 
%The variables $MaxAllocCurrent$ and
%$MaxAllocPrevious$ are used to find the maximum allocation in one
%interval, and to use this value in calculating the allocation in the
%subsequent interval (equations~(\ref{eq:maxprev}),
%(\ref{eq:maxcurrent}), (\ref{eq:max2}), (\ref{eq:updatecurrent})).
The parameter $\delta$ is used for the equalization of allocations
(equation~(\ref{eq:max2})) and defines the ``neighborhood
of unity.''

% It is set to a small value (0.05 to 0.1), because large
%values would result in extended periods of overload. The allocation
%written in the RM cell is the minimum of the calculated ER value, the
%value already in the cell (possibly written by other switches), and
%the target ABR capacity (equation~(\ref{eq:rmcell})).

%The description given so far is the core of the ERICA algorithm.
%Appendix~\ref{app:proof} outlines an analytical argument showing convergence
%to max-min allocations under a limited set of assumptions. The proof
%uses the core algorithm, a single bottleneck, infinite sources,
%different round-trip times (RTTs), and switch averaging intervals at
%least as large as the maximum RTT of any VC through it (i.e. reliable
%measurement).

\subsection{Queue Control}
\label{sec:qcontrol}

In section~\ref{sec:load-factor}, we noted that the Target ABR Capacity
is a fraction of the Total ABR Capacity. This fraction
can be a function of the current queue length, f(Q), i.e.,\\
Target ABR Capacity = f(Q) $\times$ Total ABR Capacity.

The function f(Q), called the ``queue control function,'' allows only
a specified fraction of the available capacity to be allocated to the
sources. Such a function should not artificially restrict the system
utilization to a value smaller than 100\%, and it should compensate
for errors in measurement (which manifest as queues). Further, given a
fixed number of persistant sources of traffic, it should allow the
system to achieve a queuing delay target. A control-theoretic
definition of these steady-state and robust stability conditions is
given in Ozbay et al \cite{h-infinity} and an analysis of queue
management techniques for ABR while maintaining max-min fairness is
presented by Ma and Ramakrishnan \cite{qma97}. A simple queue control
function such as a constant function used in earlier versions of ERICA
and the OSU scheme (called ``Target Utilization ($U$)') does not meet
these requirements.

% i.e., a fixed
%parameter.  This function (called ``Target Utilization ($U$)'') was
%used in the OSU scheme \cite{osu}, and earlier versions of
%ERICA. While this function was adequate in representative LAN (small
%round trip), and low variance WAN (large round trip) cases, it suffers
%from a number of drawbacks. 

% The original ERICA philosophy was that correct rate
%assignments depend more upon the aggregate input rate, rather than the
%queue length. However, three facts about queuing delays make them
%important to consider in feedback calculation: {\bf a)} non-zero
%steady state queues imply 100\% utilization, {\bf b)} a system with
%very long queues is not operating efficiently, and, {\bf c)} a service
%providing controlled queuing delay may help scalably support applications with
%delay requirements (e.g., variable quality video).

\includefigq{200pt}{120pt}{tr-qfn}{The queue control function in ERICA}{fig:qctrl-fn}

The alternative is for f(Q) to vary depending upon the queuing
delay. A number of such functions can be designed
\cite{bobby:qcontrol,qma97}. One of the functions that worked
particularly well is the following (also refer to
figure~\ref{fig:qctrl-fn}):
\[ f(Q) = Max (QDLF, \frac{a \times Q0}{(a-1) \times q + Q0}) \: \:  {\mbox for} \: q > Q0 \]
and 
\[
\mbox{f(Q)} = \frac{b \times Q0}{(b-1) \times Q + Q0} \: \:  {\mbox for} \: 0 \le Q \le Q0
\]

Here, f(Q) is a truncated rectangular hyperbola assuming values between 1
and $QDLF$ (queue drain limit factor) in the range $Q0$ to infinity,
and values between $b$ and 1 in the range 0 to $Q0$. Both curves
intersect at $Q0$, where the value is 1. To emphasize the control of
queuing delay, ERICA uses a parameter $T0$ (target queuing delay)
which is converted into the target queue length $Q0$ parameter before
performing the calculation given above. The parameter settings are
discussed in section~\ref{sec:params}.

\section{Parameter Choices and Robustness Issues}
\label{sec:params}

The robustness and performance of ERICA are significantly dependent
upon how measurements are performed and parameters are chosen.
ERICA parameters may be classified into: (1) parameters related to
measurement and averaging, (2) queue control parameters, and (3)
max-min fairness parameter $\delta$.

\subsection{Measurement and Averaging Related Parameters}

As previously mentioned, the essential metrics used in ERICA, i.e.,
load factor ($z$) and number of active connections ($N$, for FairShare
calculation) are measured during consecutive switch averaging
intervals. Variation in demand, available capacity, and number of
currently active connections, could lead to errors in the estimation
of these metrics, which, in turn, would lead to errors in
feedback. ERICA is particularly sensitive to under-estimation of $N$,
because FairShare (which is calculated using $N$) is the {\em minimum}
allocation given to sources. ERICA is also sensitive to oscillations
in estimation of the load factor $z$ during alternating periods of
demand activity and inactivity, and in the presence of higher priority
VBR traffic. Therefore, the choice of the switch averaging interval is
critical to the performance of ERICA.

To determine a reliable averaging interval, observe that the activity
of any source is determined within a round trip time ({\em
RTT}). Moreover, the maximum time for feedback from any switch to
reach a source, and the resultant activity to be experienced at the
switch (called the ``feedback delay'') is the maximum RTT (max RTT)
plus the maximum inter-RM-cell-time (max inter-RM-cell-time). Allowing
time for transient loads between averaging intervals to subside, a
reliable value for the switch averaging interval is at least 2
$\times$ {\em (max RTT $+$ max inter-RM-cell-time)}.

Choosing averaging intervals smaller than {\em max RTT} poses the risk
of errors in $z$ and $N$ (due to temporary inactivity of sources), and
choosing intervals smaller than {\em max inter-RM-cell-time} poses the
risk of not giving feedback to some sources in every measurement
interval. In fact, intervals smaller than the maximum inter-cell-time
would guarantee that $N$ is underestimated.

One solution to the problem of estimation errors with small intervals
is to use separate averaging intervals for $N$ and $z$ to allow
reliable estimation of each, and give feedback in every $z$-interval
which would be the smaller of the two. ERICA employs an alternate
method. The method is to use a single {\em base averaging interval},
and optionally use exponential averaging techniques to improve
reliability and reduce variance in the measurements. The base
averaging interval is chosen statically in the range [5 ms, 20 ms] for
a OC-3 bottleneck link (used in our simulations) and may be scaled by
the ratio of OC-3 (155 Mbps) speed to the given bottleneck link speed
for slower or faster links.

Exponential averaging can be applied for the load factor $z$ using the
formula: $z$ = (exponential average of input rate)/(f(Q) $\times$
(exponential average of available capacity)), where the exponential
average of input rate or available capacity (denoted as $x$) is
calculated as: $x = \alpha x + (1 - \alpha) x$.  Our simulations
indicate that an $\alpha$ value of 0.8 is sufficient given a base
averaging interval choice in the range [5 ms, 20 ms]. This $\alpha$
value gives significant weight to the latest sample of input rate or
available capacity. Our simulations use OC-3 bottleneck links, and
encompass LAN/WAN/satellite configurations with significant variation
in demand and available capacity \cite{dissert}. 

Averaging the number of active VCs, $N$, is performed in a different
manner. The problem is that when not even one cell of an ``active'' VC
is seen in the base averaging interval, it would be counted as
inactive. This error would result in an increase in FairShare which is
the {\em minimum} allocation given to VCs, and could lead to
instability (manifested as unbounded queues). This problem can be
simply addressed by using a separate interval for measuring $N$ and
set this interval to Max \{ RTT, 1/(minimum rate allocation) \} of any
VC. Since this is not possible, we approximate it though this
procedure. We first define the ``activity level'' of a VC as a real
number between 0 and 1. The activity level is initialized to 1
whenever any cell from the VC is seen and decayed by a multiplicative
parameter, {\em DecayFactor}, in each successive interval in which a
VC is inactive. At the end of each interval, the sum of all activity
levels would give the value of $N$ (which is now a real
number). Setting {\em DecayFactor} to a value sufficiently close to
unity would ensure that the error in estimation due to the exponential
decay would be small. We have observed that a value of $DecayFactor$
in the range [0.9, 0.95] is sufficient given our base averaging
interval choice in the range [5 ms, 20 ms].


%for the maximum of all VC's round trip times. , then an adequate setting
%for the parameter {\em DecayFactor}. 

%If a VC is active during an
%interval, its activity level is reset to one.  The {\em DecayFactor}
%parameter (which ranges from 0 to 1) determines how fast an idle VC is
%considered inactive, and how much underestimation of $N$ is possible
%for a given base averaging interval length. Specifically, if $k
%\times$ Base Averaging Interval Length = max RTT, then a value of
%$DecayFactor$ such that $DecayFactor^{k} > fraction$ would guarantee
%that at least a {\em fraction} of the number of active connections
%would be recorded in any interval. While this is a worst case bound,


\subsection{Queue Control Parameters}

Recall that the queue control function f(Q) used in ERICA
(section~\ref{sec:qcontrol}) is one of several possible functions
\cite{bobby:qcontrol}, and has four parameters: $T0$, $QDLF$, $a$ and
$b$.  The parameter $T0$, which specifies the target queuing delay, is
affected by several other system parameters such as the available
buffer size, the bottleneck link speed, and the maximum round trip
time (or the base averaging interval length). $T0$ also
affects the decrease function component of f(Q) in conjunction with
the parameters $a$ and $b$. The decrease function affects how quickly
excess queues are drained. The combination of these factors make the
choice of $T0$ important.

A heuristic used in ERICA ensures that the maximum oscillation of
queues in the steady-state will be no larger than $Q0$. As described
in appendix~\ref{app:proof}, in steady-state, the maximum deviation of
the load factor is determined by the parameter $\delta$. Specifically,
assuming that queuing deviations are corrected in one averaging
interval, we have the relationship: $T0 \ge \delta \times Base
Averaging Interval$. Given that our choice of $\delta$ is 0.1 (refer to
next section) and the base averaging interval lies between [5 ms, 20
ms], then $T0$ lies between [0.5 ms, 2 ms].

The parameter $QDLF$ (queue drain limit factor) limits the amount of
available capacity that can be allocated as {\em drain capacity} to
clear excess queues, and determines the effectiveness of the queue
control policy in reacting to transient queues. When the
aggregate input rate is equal to the available capacity (i.e., a
balanced load), $QDLF$ also determines the minimum value of the 
load factor, $z$. The range of $z$ determines the range of possible
feedback values or the maximum possible oscillations in feedback (a
stability concern). We have found that a $QDLF$ choice of 0.5
balances these conflicting concerns for a wide range of configurations
and loads.

The parameters $a$ and $b$, in conjunction with $T0$, determine the
slope of the rectangular hyperbolas. The steeper the slope, the more
sensitive the scheme is to small variations in queue length. Further
larger difference in the slopes of the two hyperbolas accentuates the
effect of the discontinuity of f(Q) at $Q0$ leading to larger
oscillations around Q0 in the steady state (if one exists and is
reached). Since $a$ and $b$ affect these slopes, the choice must be made 
considering these issues as well.

To be consistent with the steady-state queue fluctuation heuristic for
choosing $T0$, the ideal choice for $b$ is 1 which eliminates the
$b$-hyperbola. In practice, a value between [1, 1.05] can be chosen
where a larger value of $b$ allows the steady-state queuing delay to
be closer to the target, at the risk of incurring steady-state
oscillations. For the parameter $a$, we have found that a value in the
range [1.10, 1.25] sufficiently differentiates the ERICA queue control
function from simple step or linear functions. Larger values of $a$
make the function closer to a step function with the possibility of
larger queue oscillations, and smaller values make the function closer
to a linear function with a small slope, which limits the speed of
response to transient queues.

% is chosen for LAN links to be in the range
%$[1,1.05]$. This setting aims for a steady-state target queuing
%delay. For WAN links, robustness assumes priority over steady-state
%queuing delays and we recommend setting the parameter $b$ to one. This
%setting avoids implementing the $b$-hyperbola as well as avoids
%oscillatory behavior due to fluctuation of queues in the steady-state.
%For the parameters $a$ and $QDLF$, we have found the parameter
%settings $a = 1.15$ and $QDLF = 0.5$ to be successful for a wide range
%of configurations \cite{dissert}. Smaller values of $a$ and larger
%values of $QDLF$ reduce the capability of the scheme to respond to
%sudden queue increases. On the other hand, larger values of $a$ and
%smaller values of $QDLF$ result in the scheme being over-sensitive to
%changes in queue behavior. The parameter $T0$ determines when the
%scheme starts allocating capacity to drain queues, and subsequently
%affects how quickly such drain capacity is allocated.  In general, a
%large value for $T0$ is undesirable both for LANs and WANs. On the
%other hand, a value of $T0$ very close to zero results in increased
%sensitivity to changes in queues and oscillations in rate allocations.
%A value of $T0$ in the range $[0.5 ms, 2 ms]$ allows target queuing
%delays to be in the order of the end-to-end propagation delays for
%LANs, and provides quick allocation of drain capacity to clear out
%transient queues for WANs. The queue control parameter settings used
%in our simulations are $a$ = 1.15, $b$ = 1, $T0$ = 1.5 ms, $QDLF$ =
%0.5.

%The properties of our function f(Q) are as follows. It assumes a value
%of 1 at the desired steady-state (utilization = 100\%, queuing delay =
%$T0$). For delays smaller than $T0$, the hyperbola controlled by parameter
%$b$ (called $b$-hyperbola) is used to allow queues to accumulate till
%the target value. If the ``pocket of cells'' goal is not desired (e.g.,
%in environments with high load/capacity variance), the $b$-hyperbola
%is not necessary, leaving us with just three parameters. This is the
%setting ($b=1$) used in our simulation results.

%The $a$-hyperbola, in conjunction with $T0$, determines how much ``drain
%capacity'' is used for draining out the queues built up. More drain
%capacity is allocated when the queue lengths are larger, up to a
%maximum of $(1 - QDLF)$. An important use of the queue control
%function is to compensate for measurement and feedback errors caused
%by system (load/capacity/source activity) variation. The parameter
%$QDLF$ defines the tolerance limit of the system to such variation. If
%variation is large, other techniques like the use of larger averaging
%intervals, and long-term averaging of metrics (refer to
%section~\ref{sec:robustness}) must be combined with queue control for
%ensuring robustness and effective control of the system. The queue
%control parameter choices are further described in
%section~\ref{sec:params}. Another alternative in this case (which we
%don't explore further) is to set the CI and NI bits if the queue
%lengths grow unacceptably high.

\subsection{The Max-min Fairness Parameter $\delta$}

The max-min fairness parameter, $\delta$, defines the steady-state
operating region towards which ERICA attempts to drive the
system. Specifically, in ERICA, we consider the system be max-min fair
when the load factor $z$ is in the range $[1, 1+\delta]$ and all
allocations are equal. We use this weaker definition of max-min
fairness because converging to $z=1$ exactly is not guaranteed in
ERICA. Further, when $z > 1+\delta$, we consider the system
allocations to be ``infeasible'' (i.e. we estimate average load to be
larger than average capacity which is unsustainable) \cite{qma97,
mit}, and therefore not max-min fair. When $z < 1+\delta$, the
allocations cannot be max-min fair by definition \cite{mit}.

Observe that in the steady-state, the minimum drain capacity is
determined by the relation: \[ 0 \le \delta \times \mbox{Target
Cap.} \le \mbox{Available Cap.} - \mbox{Target
Cap.} \] 
Rearranging the terms and applying the relationship that
target capacity is at least $QDLF \times \mbox{Available Capacity}$,
we have: 
\[\delta \in (0, (1/QDLF) - 1]\] 
For $QDLF$ of 0.5, this gives us a range of (0, 0.5] for $\delta$. The
upper bound is a weak one since a $\delta$ value of 0.5 would result
in minimal drain capacity and possibly large transient queues (due to
the equalization of rates to the maximum allocation). The value of
$\delta$ chosen in ERICA is 0.1 which allows sufficient drain
capacity, and leaves a non-trivial zone for rate-equalization to
improve convergence towards max-min fairness.

%purpose and effect of the {\bf {\it max-min fairness parameter}},
%$\delta$, 
%is described in section~\ref{sec:max-min} and in
%appendix~\ref{app:proof}. Briefly, $\delta$ determines the range of
%load factor values when the rate allocations are equalized to achieve
%max-min fairness. The algorithm reaches a steady-state where
%its load factor remains in the range $[1, 1+\delta]$ (refer to
%appendix~\ref{app:proof}). If $\delta$ is large, the queue control
%algorithm is strained to keep the steady-state queues under
%control. If $\delta$ is too small, then the algorithm takes longer to
%converge to max-min fairness. We therefore recommend a range [0.05, 0.1]
%for $\delta$. Our simulations use the value $0.1$.

%\subsubsection{Switch Averaging Intervals}

%The ERICA algorithm measures certain quantities during consecutive
%averaging intervals. The question which immediately arises is how long
%each interval should be. Ideally, the interval length should be at
%least the maximum of the following: the longest round trip time and
%the time required to see at least one RM cell of every active
%source. This is the assumption used in the proof described in
%appendix~\ref{app:proof}. While this assumption is reasonable for LANs
%where the round trips are short, it requires long intervals in WANs
%and satellite networks. Since ERICA gives only one feedback per
%averaging interval, links could experience long periods of
%underutilization due to lack of new feedback. The performance can be
%enhanced using shorter averaging intervals which could temporarily
%reallocate available capacity to nearby sources keeping the link
%utilization high, and then converge to max-min fairness when the long
%RTT source(s) respond. The drawback for shorter intervals is the
%possibility of variation (errors) in measurement.

%The averaging interval parameter can be of fixed length or of variable
%length (triggered when a fixed number of cells are received, M). The
%latter method would have quicker response when the load is high; but
%require special care when quantities like load factor or capacity
%(ratios) are averaged over multiple intervals \cite{jain:perfbook}.

%For example, the
%analytical arguments in appendix~\ref{app:proof} assume that the
%switch averaging interval to be larger than the sum of the round trip
%time and the inter-RM cell time. But simulations (see
%section~\ref{sec:simulations}) show that a much smaller averaging
%interval can be used in practice to considerably enhance
%performance. However, small intervals can lead to measurement errors
%under several conditions (eg: large number of low rate sources,
%variance in demand and capacity etc). The ERICA algorithm contains
%techniques to compensate for such measurement errors. In this section,
%we discuss measurement aspects and describe optional scheme features
%that reduce errors in measurement.

%As a rule of thumb, the interval length should
%be set such that it is possible to see at least one cell (preferably
%one RM cell) of every source during the interval, assuming that the
%minimum rate of any source does not fall below some low threshold. In
%addition, the interval must be long enough to smooth out high
%frequency oscillations in load and capacity. 

\section{Performance Evaluation of ERICA}
\label{sec:simulations}

In this section, we present simulations to verify the performance of
ERICA under strenuous conditions not considered in the analytical
arguments in appendix~\ref{app:proof}.  Our simulations use all the
features of ERICA algorithm.

The parameter set used in our simulations is shown in Table~1:\\

\vspace*{-0.1in}
\begin{table*}[ht]
\begin{center}
\caption{Parameter values}
\begin{tabular}{llll}
\hline\hline
Parameter & Value & Suggested Range & Purpose \\
\hline\hline
$\delta$  & 0.1 & (0, 0.5] & Max-min fairness \\
$T0$      & 1.5 ms & [0.5 ms, 2 ms] & Queue control \\
$a$       & 1.15 & [1.10, 1.25] & Queue control \\
$b$       & 1 & [1, 1.05] & Queue control \\
$QDLF$    & 0.5 & 0.5 & Queue control \\
Averaging Interval & 5 ms & [5 ms, 20 ms] & Measurement of metrics \\
$DecayFactor$ & 0.9 & [0.9, 0.95] & Long-term averaging of number of active VCs\\
$\alpha$      & 0.8 & [0.7, 0.9] & Long-term averaging of input rate
and capacity\\
\hline\hline
\end{tabular}

\end{center}
\label{tbl:params}
\end{table*}


\subsection{Max-Min Fairness}

We use the popular Generic Fairness Configuration-2 (GFC-2) to test
the utilization, queue lengths and fairness of the scheme. The
configuration (illustrated in Figure~\ref{fig:gfc2}) has multiple
bottlenecks and connections with different round-trip times. This
configuration was selected by the ATM Forum traffic management working
group as the test configuration to compare various schemes.

\includefige{270pt}{180pt}{gfc2}{The Generic Fairness Configuration-2}{fig:gfc2}

  
%                  D(1)      E(2)    F(1)      H(2)  A(3)C(3)   G(7) 
%                   ^         ^       ^         ^      ^  ^      ^
%                   |         |       |         |      |  |      |
%       +----+   +-----+   +----+   +----+   +----+   +----+   +----+
%       |    |4D |     |2D |    | D |    | D |    | D |    |2D |    |
% A(1)->| S1 |-->| S2  |-->| S3 |-->| s4 |-->| s5 |-->| s6 |-->| S7 |->B(3)
%       |    |   |     |   |    |   |    |   |    |   |    |   |    |
%       +----+50 +-----+100+----+50 +----+150+----+150+----+50 +----+
%        ^ ^  Mbs^ ^ ^  Mbs ^  ^ Mbs ^  ^ Mbs  ^   Mbs  ^   Mbs   
%        | |     | | |      |  |  ^  |  |      |    ^   |    ^
%      B(1)D(1) E(2)|B(1) A(1)F(1 | B(1)H(2)  C(3)  |  G(7)  |
%                  A(1)       Congested     The studied     Congested
%                            link for A VCs     link       link for B VCs
%                                            Congested link
%                                            for C VCs
% D is the link distance and can be varied


The following are the expected rate allocations as per the max-min
fairness criterion. Note that the link bandwidth is adjusted by 48/53
to get an expected application throughput.

\begin{tabular}{lllrrl}
{\bf VC } & \multicolumn{3}{c}{Fair share calculation} & \multicolumn{2}{c}{Fairshare} \\
A &1/4 of 40  &=& 10$\times$48/53 = &9.1& Mbps\\
B &1/10 of 50 &=&  5$\times$48/53 = &4.5 &Mbps\\
C &1/3 of 105   &=& 35$\times$48/53 = &31.7& Mbps\\
D &      35    &=& 35$\times$48/53 = &31.7& Mbps\\
E &1/2 of 70   &=& 35$\times$48/53 = &31.7& Mbps\\
F &      10    &=& 10$\times$48/53 = &9.1& Mbps\\
G &1/10 of 50   &=&  5$\times$48/53 = &4.5& Mbps\\
H &1/2 of 105   &=& 52.5$\times$48/53 = &47.6& Mbps
\end{tabular}

\newputfigsa{gfc2.sim1}{Simulation results with the GFC-2 configuration}{fig:gfc2-sim}
%
%\putfigsa{gfc2.sim}{Simulation Results with the GFC-2 Configuration}{fig:gfc2-sim}
% \twocolumn

Simulation results are shown in
Figure~\ref{fig:gfc2-sim}. Figure~\ref{fig:gfc2-sim}(a) shows the
allowed cell rates (ACRs) of the sources. Figure~\ref{fig:gfc2-sim}(b)
shows the queue lengths at the ports connected to the next switch for
the first six switches. Figure~\ref{fig:gfc2-sim}(c) shows the link
utilizations of the links connecting two switches.  The optimal
allocations are achieved in under 400 ms (under 4 round trips), and
the queues are drained within 800 ms (under 7 round trips). During the
transient period, the link utilizations are close to 100\% and the
queue lengths are controlled to reasonable values (maximum queue is $<
30000$ cells, i.e., $< 270$~ms or 2 round trip times at 50 Mbps
bottleneck rate).  The steady-state utilizations are close to 100\%
and the queue lengths are kept close to zero. The minimal oscillations
in the steady-state are due to the small variation in queuing
delays. The initial rate assignment for each source in this simulation
was picked randomly. For reasonable confidence, we repeated this
experiment with other random values which gave similar results.

\subsection{Robustness}

For testing the robustness of the scheme, we need a configuration
which attacks the weaknesses of the scheme, namely, its dependency
upon measurements. Variation in load and capacity could lead to
measurement and feedback errors resulting in unbounded queues or low
average utilization.  The TCP and VBR configuration (refer to
figure~\ref{fig:100tcp}) is designed to test this case.

\vspace*{0.25in}
\includefige{180pt}{85pt}{100tcp}{TCP + VBR Configuration}{fig:100tcp}

The configuration simulates capacity variation by using a higher
priority VBR virtual circuit which carries traffic multiplexed from
fifteen long-range dependent sources \cite{dissert}. The traffic
generated by this VC (and as a result, the ABR capacity) is highly
variable as shown in figure~\ref{fig:100tcp-sim}(a). The configuration
simulates load variation by using TCP sources carrying infinite {\em
ftp} traffic. The load variation is caused by the startup dynamics of
TCP. The TCP slow start protocol begins with small window sizes, and
the amount of data it sends is limited by the window size
(window-limited), rather than a network-assigned rate. As a result,
the load offered by an individual TCP connection is bursty, i.e., it
consists of active and idle periods. As the TCP window size grows, the
active periods become longer. Assuming no packet losses, the TCP
source eventually appears to be the same as a persistent source and
its load is controlled by network-assigned rates (rate-limited). The
queues build up when both demand variation and capacity variation
exist in the system.  We use 100 sources and synchronize them such
that the load phases (idle and active periods) of multiple sources
coincide to create a worst case scenario.

% \twocolumn
\newputfigsx{tcp100_1}{Simulation results with the 100 TCP and VBR configuration}{fig:100tcp-sim}
%
%\putfigsx{tcp100_1}{Simulation Results with the 100 TCP + VBR
%Configuration}{fig:100tcp-sim}

%\twocolumn

Figures~\ref{fig:100tcp-sim}(b), (c) and (d) show ATM level metrics
(ACRs of sources 1, 50 and 100; queue length at output port of switch
1; link utilization of bottleneck link), while
figures~\ref{fig:100tcp-sim}(e) and (f) show the TCP level metrics
(congestion windows and sender sequence numbers of sources 1, 50 and
100).  The graphs show that ERICA successfully controls the TCP
sources once they become rate-limited. As a result, the buffer
requirement at the bottleneck is not a linear function of the number
of sources. Though the system does not have a steady-state (VBR
traffic is always variable), ERICA controls the maximum and average
queues and keeps utilization high (consistent with the priorities
assigned in section~\ref{sec:design-goals}).  The congestion window
and sender sequence number graphs show that the allocations to
contending sources are fair despite the variation in load and
capacity.

\section{Concluding Remarks}
\label{sec:conclusions}

In this paper, we have described the design and evaluation of the
ERICA switch algorithm for ATM ABR congestion control.  We presented a
simple switch model and explained design goals.  The key design goals
are max-min fair steady-state operation with controlled queuing
delays, stability, and robustness to variation in ABR load and
capacity. We then presented the ERICA algorithm, showing how the goals
and simplicity requirements determine every step in the algorithm.

The scheme requires that the switches periodically monitor their load
on each link and determine a load factor, the available capacity, the
queue length, and the number of currently active virtual
connections. This information is used to calculate a fair and
efficient allocation of the available bandwidth to all contending
sources.  The measurement aspects which determine the robustness of
the algorithm are treated in depth. 

A limited analysis of the convergence properties is given in
appendix~\ref{app:proof}. In addition, we present simulation results
illustrating that the scheme meets the desired goals, including good
steady-state behavior (high utilization, controlled queuing delay,
max-min fairness), rapid convergence from network transients, and
robustness to load and capacity variations.

In conclusion, we note that the promise of explicit rate control is
higher fidelity control in terms of a number of objectives (fairness,
utilization, queueing delays). But the addition of provable robustness
as a goal, especially with the uncertainty in a large number of
parameter dimensions (like time-delays, load, capacity, number of
active sources), and extension to multiple bottleneck cases with
independent controllers makes it a non-trivial control problem. ERICA
represents an engineering tradeoff.

%The ERICA scheme has considerably influenced the design of
%contemporary switch schemes.  Notably, the ATM Forum traffic
%management specification 4.0~\cite{tm4} cites ERICA as an example
%switch mechanism. A patent on the scheme features has been awarded
%\cite{erica-patent}.

\begin{thebibliography}{99}

\bibitem{tm4} 
``The ATM Forum Traffic Management Specification Version 4.0,''
ATM Forum Traffic Management AF-TM-0056.000, April 1996.
Available as
ftp://ftp.atmforum.com/pub/approved-specs/af-tm-0056.000.ps

\bibitem{ifip} L. Kalampoukas, A. Varma and K. K. Ramakrishnan, ``An
efficient rate allocation algorithm for ATM networks providing max-min
fairness,'' In {\em Proceedings of the 6th IFIP International Conference on
High Performance Networking}, September 1995.

\bibitem{icc} K. Siu and T. Tzeng, ``Intelligent congestion control
for ABR service in ATM networks,'' {\em Computer Communication Review},
Volume 24, No. 5, pp. 81-106, October 1995.

%\bibitem{adaptive} F. Bonomi, D. Mitra and J. B. Seery,
%``Adaptive algorithms for feedback-based flow control in high-speed,
%wide-area ATM networks,'' {\em IEEE Journal on Selected Areas in
%Communications}, Volume 13, No. 7, September 1995.

\bibitem{eprca} L. Roberts, ``Enhanced PRCA (Proportional Rate-Control
Algorithm),'' {\em AF-TM 94-0735R1}, August 1994.

\bibitem{phantom} Y. Afek, Y. Mansour and Z. Ostfeld, ``Phantom:
A simple and effective flow control scheme,'' In {\em Proceedings of the ACM
SIGCOMM}, August 1996.

%\bibitem{closed} N. Yin and M. G. Hluchyj, ``On closed-loop rate
%control for ATM cell relay networks,'' Proceedings of the IEEE INFOCOM
%'94, pp. 99-108, June 1994.

%\bibitem{dynamic} Y. Gong and I. Akyildiz, ``Dynamic traffic control
%using feedback and traffic prediction in ATM networks,''
%Proceedings of the IEEE INFOCOM
%'94, pp. 91-98, June 1994.

%\bibitem{compare} T. Tzeng and K. Siu, ``Comparison of performance
%among existing rate control schemes,''
%{\em AF-TM 94-1078}, November 1994.

\bibitem{hkust} D. Tsang and W. Wong, ``A new rate-based switch
algorithm for ABR 
traffic to achieve max-min fairness with analytical approximation and
delay adjustment,'' In
{\em Proceedings of IEEE INFOCOM}, pp. 1174-1181, March 1996.

%\bibitem{nist} N. Golmie, Y. Chang and D. Su, ``NIST ER
%switch mechanism (an example),'' {\em AF-TM 95-0695}, June 1995.

%\bibitem{example} A. Barnhart, ``Example switch algorithm for section
%5.4 of TM spec,'' {\em AF-TM 95-0195}, February 1995.

\bibitem{mit} A. Charny, D. D. Clark and R. Jain, ``Congestion Control
with Explicit Rate Indication,'' In {\em Proceedings of ICC'95}, June
1995. http://www.cis.ohio-state.edu/$\tilde{~~}$jain/papers/charny.htm

\bibitem{murali:fmmra} A. Arulambalam, X. Chen and N. Ansari,
``Allocating Fair Rates for Available Bit Rate Service in ATM Networks,''
{\em {IEEE} Communications Magazine}, 34(11):92--100, November 1996.

\bibitem{osu}
R. Jain, S. Kalyanaraman and R. Viswanathan, ``The OSU Scheme for
Congestion 
 Avoidance in
ATM Networks: Lessons Learnt and Extensions,''
Performance Evaluation Journal, 
Vol. 31/1-2, December 1997.
http://www.cis.ohio-state.edu/$\tilde{~~}$jain/papers/perf-sub.htm

\bibitem{dissert} S. Kalyanaraman,  ``Traffic Management for
the Available Bit Rate (ABR) Service in Asynchronous Transfer Mode
(ATM) networks'' {\em Ph.D. Dissertation}, Dept. of Computer and
Information Science, The Ohio State University, August 1997.
http://www.cis.ohio-state.edu/$\tilde{~~}$jain/theses/shiv.htm

%\bibitem{sample-scheme}
%R. Jain, S. Kalyanaraman, R. Viswanathan, and R. Goyal,
%``A Sample Switch Algorithm,''
%{\em AF-TM 95-0178R1}\footnote{Throughout this section, 
%AF-TM refers to ATM Forum Traffic Management sub-working group
%contributions.}, February 1995.

%\bibitem{erica-complete}
%R. Jain, S. Kalyanaraman, R. Goyal, S. Fahmy, and R.
%Viswanathan, ``ERICA Switch Algorithm: A Complete Description,''
%{\em AF-TM 96-1172}, August 1996.

\bibitem{erica-patent} R. Jain, S. Kalyanaraman, R. Viswanathan,
R. Goyal and S. Fahmy, ``ERICA: Explicit Rate Indication for Congestion
Avoidance in ATM Networks,'' {\em U.S. Patent No. 5,805,577}, Issued
September 8, 1998.
http://www.cis.ohio-state.edu/$\tilde{~~}$jain/patents/patente.htm

\bibitem{anish:closure} A. Arora and M. Gouda, ``Closure and
convergence: A foundation of fault-tolerant computing'' {\em IEEE
Transactions on Software Engineering,} Vol. 19, No. 10,
pages 1015 -- 1027, 1993. 

\bibitem{tutorial}
R. Jain, ``Congestion Control and Traffic Management in ATM Networks:
Recent Advances and a Survey,'' {\em Computer
Networks and ISDN Systems}, October 1996.
http://www.cis.ohio-state.edu/$\tilde{~~}$jain/papers/cnis.htm

\bibitem{Jain88} R.~Jain and K.~K. Ramakrishnan.  ``Congestion
avoidance in computer networks with a connectionless network layer:
Concepts, goals, and methodology,'' In {\em Proceedings of IEEE
Computer Networking Symposium}, pp 134-143, April 1988.
http://www.cis.ohio-state.edu/$\tilde{~~}$jain/papers/cr1.htm

\bibitem{src-rule-paper} R. Jain, S. Kalyanaraman, S. Fahmy and R. Goyal,
``Source Behavior for ATM ABR Traffic Management: An Explanation,''
{\em IEEE Communications Magazine}, November 1996.
http://www.cis.ohio-state.edu/$\tilde{~~}$jain/papers/src\_rule.htm

%\bibitem{dynamic-averaging} Bo-Kyoung Kim, Byung G. Kim and Ilyoung Chong,
%``Dynamic Averaging Interval Algorithm for ERICA ABR Control Scheme,''
%{\em AF-TM 96-0062}, February 1996.

\bibitem{tcp-abr-vbr} 
S. Kalyanaraman, R. Jain, S. Fahmy, R. Goyal and J. Jiang,
``Performance of TCP over ABR on ATM backbone and with various VBR 
traffic patterns,'' In {\em Proceedings of ICC'97}, June 1997.
http://www.cis.ohio-state.edu/$\tilde{~~}$jain/papers/tcp\_vbr.htm

%\bibitem{fba} J. Heinanen and K. Kilkki, 
%``A fair buffer allocation scheme,'' {\em unpublished manuscript}.

\bibitem{goyal-fba} R. Goyal, R. Jain, S. Kalyanaraman, S. Fahmy,
B. Vandalore and S. Kota, ``TCP Selective Acknowledgments and UBR Drop
Policies to Improve ATM-UBR Performance over Terrestrial and Satellite
Networks'', In {\em Proceedings of ICCCN'97}, September 1997,
http://www.cis.ohio-state.edu/$\tilde{~~}$jain/papers/ic3n97.htm

%R. Goyal, R. Jain, S. Kalyanaraman, S. Fahmy,
% B. Vandalore, ``Improving the Performance of TCP over the
%ATM-UBR service'', {\em Submitted to Computer Communications}, July 1997.


%\bibitem{goyal:avail-capacity} R.Goyal, S. Kalyanaraman, R.Jain,
%S. Fahmy, B. Vandalore ``Available Capacity of a Resource Shared by
%Multiple Classes,'' preprint.

\bibitem{epd} A. Romanov and S. Floyd, ``Dynamics of TCP Traffic over ATM
Networks,'' {\em IEEE Journal on Selected Areas of Communications},
Vol 13, No. 4, May 1996.

\bibitem{chiussi:dmrca}
F.~M. Chiussi, Y.~Xia and V.~P. Kumar. ``Dynamic max rate
control algorithm for available bit rate service in ATM networks,'' In
{\em Proceedings of the {IEEE} GLOBECOM}, volume~3, pages  2108--2117, November 1996.

\bibitem{vsvd-paper} R. Goyal, X. Cai, R. Jain, S. Fahmy and
B. Vandalore, ``Per-VC Rate Allocation Techniques for ATM-ABR Virtual
Source Virtual Destination Networks,'' In {\em Proceedings of GLOBECOM},
November 1998.
http://www.cis.ohio-state.edu/$\tilde{~~}$jain/papers/globecom98.htm

\bibitem{sonia-multicast} S. Fahmy, R. Jain, R. Goyal, B. Vandalore,
S. Kalyanaraman, S. Kota and P. Samudra, ``Feedback Consolidation
Algorithms for ABR Point-to-Multipoint Connections in ATM Networks,''
{\em Proceedings of IEEE INFOCOM}, volume 3, pp. 1004--1013, April
1998.
http://www.cis.ohio-state.edu/$\tilde{~~}$jain/papers/cnsldt.htm

\bibitem{nina-infocom} N. Plotkin and J. Sydir, ``Behavior of Multiple
ABR Flow Control Algorithms Operating Concurrently within an ATM
Network,'' In {\em Proceedings of IEEE INFOCOM}, April 1997.

\bibitem{qma97} Q. Ma and K.K. Ramakrishnan, ``Queue Management for
Explicit Rate Based Congestion Control,'' In {\em Proceedings of
ACM SIGMETRICS'97}, pp. 39-51, Seattle, Washington, June, 1997.

\bibitem{h-infinity} H. \"Ozbay, S. Kalyanaraman and A.~\.{I}ftar, ``On
Rate-Based Congestion Control in High Speed Networks: Design of an
$\Hi$ Based Flow Controller for a Single Bottleneck,'' In {\em Proceedings of 
American Control Conference, 1998}. 
Through http://www.ecse.rpi.edu/Homepages/shivkuma/

\bibitem{basar} E. Altman, T. Basar and R. Srikant, ``Multi-user
rate-based flow control with action delays: a team-theoretic
approach,'' In {\em Proceedings of 36th Conference on Decision and
Control}, December 1997, pp. 2387--2392.

\bibitem{lofti} L. Benmohamed and S. M. Meerkov, ``Feedback control
of congestion in packet switching networks: the case of a single
congested node,'' {\em IEEE/ACM Trans. on Networking}, Vol.~1 (1993),
pp.~693--707.

\bibitem{rohrs} C. Rohrs and R. Berry, ``A linear control approach
to explicit rate feedback in ATM networks,'' In {\em Proceedings of INFOCOM
'97}, April 1997.

\bibitem{jain:perfbook} R. Jain, ``The Art of Computer Systems
Performance Analysis,'' {\em John Wiley \& Sons}, 1991.
http://www.cis.ohio-state.edu/$\tilde{~~}$jain/books/perfbook.htm

%\bibitem{stallings:atm} W. Stallings, ``
%High-Speed Networks, TCP/IP and ATM Design Principles,''
%{\em Prentice Hall}, 1998.

\bibitem{bobby:qcontrol} 
B. Vandalore, R. Jain, R. Goyal and S. Fahmy,
``Design and Analysis of Queue Control Functions for Explicit Rate
Switch Schemes,'' In
{\em  Proceedings of IC3N}, October 1998.
http://www.cis.ohio-state.edu/$\tilde{~~}$jain/papers/qctrl\_bv.htm

\bibitem{proof-tr} 
S. Kalyanaraman,  R. Jain, S. Fahmy, R.
Goyal and B. Vandalore, 
``Analytical arguments for the convergence of the ERICA switch
algorithm to max-min fairness: Single and multiple bottleneck cases''
{\em Technical Report}, Ohio State University, 1998.

\end{thebibliography}

\appendix
\section{Analytical Argument of Convergence to Max-Min Fairness}
\label{app:proof}

In this appendix, we give a limited analytical argument for the
convergence of a single bottleneck node implementing ERICA towards
max-min fair rate allocations. Some model assumptions in this argument
are unrealistic, but they simplify the analysis considerably. This
section should be used only to get further insights into the engineering
decisions taken in the ERICA algorithm.  We have not published an
extension of this argument for a multiple-bottleneck system, but are
exploring it under a new effort to cast such non-linear rate-based
algorithms in a control-theoretic framework \cite{h-infinity}.  The
general proof of convergence, stability and robustness (under
assumptions of multiple bottlenecks, queuing delay targets and
asynchrony) of rate-based algorithms is currently an open problem
studied by several researchers (see
\cite{h-infinity,basar,lofti,rohrs}). 

Our modeling assumptions are:
\begin{itemize}
\item There is only one bottleneck node.
\item The ``core'' ERICA algorithm (defined in
      section~\ref{sec:max-min}) is used with two exceptions:
        \begin{enumerate}
        \item We ignore the effect of the queue control function.
        \item We ignore the moderation step (equation~(\ref{eq:fsfirst})): \\
        IF (ER $>$ FairShare AND CCR $<$ FairShare) THEN ER = FairShare
        \end{enumerate}
\item Sources are persistent (always have data to send), though some
(not all) might be source-bottlenecked at low rates.
\item Round-trip times of various sources are different (the case of equal
round trip times is a special case of this).
\item The effect of any transient queuing between intervals is ignored.
(unrealistic).
\item Switch averaging interval is at least the twice the sum of {\bf
a)} the largest RTT of any VC though the bottleneck, and {\bf b)} the
maximum time required to see at least one RM cell of every active
source (maximum inter-RM cell time). This means that measurements are
reliable, and transient loads caused by asynchrony can be ignored.
We call such an averaging interval a {\em ``cycle''}.
\item Load factor ($z$) $>$ 0, ER $<$ Link Rate, and for any source
CCR $<$ Link Rate. The last condition is satisfied since ATM signaling 
ensures that the ``peak cell rate (PCR)'' parameter is never larger than
any link rate along the path
\item Source-bottleneck behavior (if any) does not change during the 
convergence period.
\end{itemize}


{\bf Notation:}
\begin{itemize}
\item Rate of source $i$ in cycle $j$ (CCR) is $R(i,j)$
\item MaxAllocPrevious in cycle $j$ is $Max_{i} \; R(i,j) $
\item The ER for source $i$ in cycle $j$ is the same as the rate of
 source $i$ in cycle $j+1$, i.e., $R(i,j+1)$
\item $z_{j}$ = overload factor measured in $j$th cycle (and used in
                   $(j+1)$ th cycle).
\item $C$: Target ABR capacity of the bottleneck.
\item $B$: Sum of the rates of bottlenecked sources, also equal to
 $b \times C$, $b \le 1$
\item $N$: Number of active sources
\end{itemize}

{\bf Definition:} A source is said to be {\em satisfied} at a given
rate if it is bottlenecked elsewhere and cannot utilize higher 
rate allocations. 

{\bf To prove:} that for the system described above, the ERICA
algorithm causes it to converge towards max min operation in at most O(log N)
number of cycles.

{\bf Proof:}

The proof methodology used here was proposed in reference
\cite{anish:closure}. We first prove a set of {\em safety (closure)}
properties which show that the system remains within a closed state
space, S.
The closed state space, S is:\\
        S:      $0 < z < N$\\

Then we prove a set of {\em convergence properties} which
show that the system reaches and remains in a target state space, T.
The target convergence state space, T is:\\
        T:      $(1 \le z \le 1+\delta)$    AND
        Allocations are Max-Min fair, 

where the term ``Max-Min fair'' implies that contending sources are allocated the
highest possible {\em equal} rates,  satisfying the condition on $z$.

{\bf Closure Properties: }

{\it {\bf Lemma 0:}} Given that the maximum rate (C) of any VC is at
most the target link rate (condition imposed during ATM signaling and 
connection setup), the overload factor lies between 0 and N, where N is 
the number of VCs set up (assumed active).

Trivial based upon the assumptions.  \hfill $\Box$

{\bf Convergence Properties: }

\includefige{240pt}{150pt}{proof1}{Movement of single bottleneck controlled by ERICA towards max-min fairness}{fig:max-min}

Figure~\ref{fig:max-min} shows how ERICA converges to max-min fairness
under these model assumptions. It should be noted that this
convergence property is what motivated the design of the components of
the algorithm, based upon $z$ and FairShare.

Specifically, the load factor ($z$) can fall into one of three zones $(0,1),
[1,1+\delta], (1+\delta,N]$. The goal is to reach the second zone,
while ensuring that the rate allocations are equal, i.e. the state space, T.
The convergence unfolds in five stages as follows 
(of which stages 1 to 4 shown in the figure):
\begin{description}
\item[Stage 0:] Irrespective of the initial rates, each source
is given a chance to reach FairShare (C/N) in one cycle (Lemma
1).
\item[Stage 1:] Assuming stage 0 is the initialization of the algorithm, if
the bottleneck is in the zone: $z \in (0,1)$, within O(log N)
cycles the system reaches a state where $z \ge 1$ (Lemma 2). 
\item[Stage 2:] Once the system is in a state where $z \ge 1$, then the switch
      remains in such a state $z \ge 1$, and converges within O(log N)
      cycles to the state where $z \in [1,1+\delta]$ within O(log N)
      steps. (Lemma 3, parts A and B)
\item[Stage 3:] When the system is the state where $z \in [1,1+\delta]$, the
      contending sources get an equal rate allocation. (Lemma 3, part
      C).
\item[Stage 4:] The system may now stay in the state $z \in [1,1+\delta]$, in
      which case max-min fairness is achieved (Lemma 3, Part C, Note
      1). Alternatively it may move to a state $z \in [1+\delta,N]$,
      from where in O(log N) additional cycles it reaches the state $z
      \in [1,1+\delta]$, but now since rate allocations are equal,
      rate allocations are unchanged and max-min fairness is
      achieved (Lemma 3, Part C, Note 1 and Theorem 1)
\end{description}

The details of the proof are presented below:

{\it {\bf  Lemma 1:}} ERICA takes one cycle 
         to satisfy sources bottlenecked at rates below equal
         FairShare (C/N).

{\bf Proof:} In every cycle, ERICA allocates at least FairShare = ``fs'' =
C/N to every source.  If there exist sources which are bottlenecked
such that they cannot utilize rate allocations above fs, the system
{\em satisfies} such sources in one cycle. This first cycle is called
{\em ``initialization cycle''} in what follows. \hfill $\Box$


{\it {\bf Note 1:}} During convergence, there is at most one
       initialization cycle for any configuration.

{\it {\bf  Note 2:}} After the VCs below fs are satisfied, the unused capacity (if
       any) will be reflected in the value of the overload factor, $z$
       (which is the ratio of the total load and the target capacity).

{\it {\bf Note 3:}} The following lemmas assume that the initialization cycle is
completed, and that there is at least one ``greedy'' or
``unconstrained''  source going
through each bottleneck which can utilize any bandwidth allocated to
it.

{\it {\bf Lemma 2:}} If a switch is underloaded, i.e., $z < 1$, then
         in O(log(N)) cycles, either the system converges to the
         target state space, T, or the load factor increases to reach
         a value greater than unity.

{\bf Proof:}

During underload ($z < 1$), ERICA uses the following formula to allocate rates:\\
       ER = Max(MaxAllocPrevious,  $CCR/z$).

Recall that  ER = $R(i,j)$,  MaxAllocPrevious = $ Max_{i} \; R(i,j-1)$, and $CCR/z = R(i,j-1)/z_{j-1}$

Hence, the ERICA formula can be rephrased as:
\begin{equation}
R(i,j) = Max ( \; Max_{i} \; R(i,j-1), \; R(i,j-1)/z_{j-1}  \; )
\label{eq:erica-eq}
\end{equation}


Note that MaxAllocPrevious ( $Max_{i} \; R(i,j-1)$ ) is at least $C/N$
(equal to the maximum of the allocations in the previous cycle) and
$CCR/z$ is greater than $CCR$.  As a result, the allocation of {\em
every unsatisfied source increases}. 

If all sources are greedy and and
initially equal, the new load factor is unity, with all sources
equal. {\em In this case the target T is achieved in a single cycle}.

In the case that source rate allocations are unequal and/or some
sources are satisfied, the behavior of the system is different.
Satisfied sources stay constant and the overload factor increases in
the next cycle. If all sources are greedy, they get a rate of C/N in
the first cycle. As a result, the new load factor is at least
load/capacity = $(N \times (C/N)) / C = 1$.  {\em In this case, the load
factor becomes greater than unity in a single cycle}.

We now show that even if the above special conditions do not hold, the
load factor becomes greater than unity in O(log N) cycles. Assume that
some sources at bottlenecked at rates below $C/N$, and the sum of
their rates is B. The remaining sources get at least the maximum
allocation of the previous cycle, i.e. $Max_{i} \; R(i,j-1)$.
Starting from an initial load factor of $z_{0}$, the system increases
its load factor in every cycle. Assume that, in the $(j-1)$ st cycle
the overload factor, $z_{j-1}$ is less than $1/( 1 + \epsilon)$, for
small $\epsilon$. Now,

\[z_{j}  =   \frac{B + \sum_{i} R(i,j)}{C}  \ge   \frac{B + \sum_{i}
\frac{R(i,j-1)}{z_{j-1}}}{C} \; \; \; \;  \; \; \; \; \mbox{from (\ref{eq:erica-eq})}\]

\[\ge  \frac{B + \sum_{i} \frac{R(i,j-2)}{z_{j-2} \times z_{j-1}}}{C}
\ge \frac{B + \sum_{i} \frac{R(i,0)}{ z_{0} \times z_{1} \times \: \ldots
\: \times z_{j-1}} }{C} \]
\[ \ge \frac{B + \sum_{i} \frac{R(i,0)}{ (1/ 1 + \epsilon)^{j} } }{C} \]


For $z_{j}$ to become greater than 1, it is sufficient that:  

\[B + \sum_{i}  \frac{R(i,0)}{ (1/ 1 + \epsilon)^{j} } > C , \; \; \;
\; \mbox{i.e.,}\]
\[ j < \left|\log_{ 1 + \epsilon} \sum_{i} \frac{R(i,0)}{C - B} \right|  \]


Since $B$ and $R (i,0)$ are constants, and C is upper bounded by the
link capacity $j = O(log N)$ in the worst case.

{\it {\bf Note 1:}}  $z_{j}$ can also become greater than 1 when: 

$B + \sum_{i} Max_{i} \; R(i,j-1) = B + (N- Nb) \times Max_{i} \;
R(i,j-1) > C $, where Nb is the number of
bottlenecked sources.  Here, we have taken the $Max_{i} \; R(i,j-1)$ term in
the ERICA step given in equation (\ref{eq:erica-eq}) instead of the
$R(i,j-1)/z_{j-1}$ term which is used in the above proof. This new inequality reduces to:\\
$Max_{i} \; R(i,j-1) > (C - B)/(N - Nb)$

Observe that the right hand side of the above inequality is the target
max-min rate allocation, which means that $z_{j}$ becomes greater than
unity in {\em one cycle} when {\em any one} of the rates $R(i,j-1)$ is
greater than the final max-min allocation. Note that this assumes that
the moderation step (see list of assumptions) has been ignored. \hfill
$\Box$

{\it {\bf  Lemma 3:}} If a switch is overloaded, i.e., $z \ge 1$, then the
         switch remains overloaded i.e. $z \ge 1$, and converges
         within O(log N) cycles to the desired operating region, T.


{\bf Proof:} We split the proof into three parts:\\
{\bf Part A:} We first prove that the system remains in the region $z
\ge 1$.

With the system starting at $z_{j-1} \ge 1$, we show that the 
minimum value of the new load factor after a cycle, $z_{j},$ is
greater than or equal to unity.

The ERICA code segment used for this proof is:
\begin{description}
\item[] IF $(z \le 1+ \delta ) ER = Max( \mbox{MaxAllocPrevious,}  CCR/z)$ \\
ELSE $ER = Max(C/N,  CCR/z)$
\end{description}

We argue that the ER value obtained by the assignment statement 
$ER = Max( \mbox{MaxAllocPrevious,}  CCR/z)$ does not reduce the load
factor below its current value.
Recall that \mbox{MaxAllocPrevious} =  $Max_{i} \; R(i,j-1)$ and $CCR/z =
R(i, j-1)/z$. Now, since $z \ge 1, \; \mbox{MaxAllocPrevious} \ge CCR/z$.
As a result, this term is not
going to reduce $z$. Therefore, we simply deal with the second
assignment statement in the ERICA code segment above, i.e., $ER = Max(C/N,
CCR/z)$.

Split the set of sources into two categories:
\begin{enumerate}
\item Sources bottlenecked at rates equal to or below $C/N$, which have a
total rate of $b \times C, b \ge 0$.
\item Sources above $C/N$, with a total rate of $d \times C$.
\end{enumerate}

The current load factor is $z_{j-1} = ((b+d) \times C)/C = b+d > 1$.
If all sources were to divide their rates by $z_{j-1}$, the new load
factor $z_{j}$ would be unity.  In our case only sources above $C/N$
reduce their rates. The new load factor is $b + (d/z_{j-1})$. To
complete the proof of part A, note that:

$z_{j} =   b + (d/z_{j-1}) \ge (b+d)/z_{j-1} = 1$ \hfill $\Box$

 {\bf Part B:} In the worst case, the system first reaches the region $1 \le z <
     1+ \delta$ in O(log N) cycles.

If the system is already in region $1 \le z < 1 + \delta$, the proof
is trivial. 

Else, let the initial load factor be $z_{0}$ and the current load
factor be $z_{j}$. Let $B = b \times C$ be the sum of bottlenecked rates
at or below C/N.  The remaining rates $R(i,j) \ge C/N$, and $z_{k} > 1
+ \delta, \;  \forall k < j$. A technique similar to the one shown in
lemma~2 can be used to prove that $j = O(logN)$, i.e., the system
reaches the operating region $1 \le z < 1 + \delta$ in O(log N)
cycles. \hfill $\Box$

{\bf Part C:} The contending sources get an equal rate allocation in the
region $1 \le z < 1 + \delta$

The ERICA allocation in this region (in the $j+1$ th cycle) is: Max(MaxAllocPrevious, $CCR/z$)
i.e. $ Max ( \; Max_{i} \; R(i,j),  \; R(i,j)/z_{j} \; ) $

Since $z_{j} \ge 1, \; R(i,j)/z_{j} < Max_{i} \; R(i,j), \; $ and the
ERICA allocation is simply $Max_{i} \; R(i,j)$ for all sources.  In
other words, the rate allocations to all sources in this region are
equal.

{\bf Note 1:} Observe that if $R(i,j)$ s were already equal, the load factor
would be unchanged in subsequent cycles, i.e., the system would remain
at $1 \le z < 1 + \delta$, and rates of contending sources $R(i,j)$
are equalized, leading to max-min fair allocations. That is, the
system has reached the state, T, and stays in this state until new
input changes occur.

If the rates $R(i,j)$ are not equal before this {\em ``equalization
cycle''}, the new load factor can be greater than $1 +
\delta$. As proved in part B, the system requires at most
O(log N) cycles to converge to the state where $1 \le z < 1 +
\delta$. However note that at every cycle of this aforementioned
convergence process, all rate allocations remain equal since they are 
scaled by the same factor ($z$). This implies that the system has
reached a state where $1 \le z < 1 + \delta$ AND all rate allocations
of unconstrained sources are equal. But this state is the same as the target
state space, T.

{\bf Theorem 1:} From an arbitrary initial state, the ERICA algorithm
brings the system to the target operating region T within O(log N)
cycles.

An arbitrary initial state can be characterized by a value of the load
factor $z$ between 0 and N (closure, lemma 0). If $z < 1$, we have
shown in lemma 2 that the system reaches a state where $z \ge 1$ within
O(log N) cycles. Once $z \ge 1$, we have shown that the load factor
does not reduce below unity (lemma 3, part A). Further, the system
moves to the region $1 \le z < 1 + \delta$ within O(log N) cycles
(lemma 3, part B) and the rates are equalized in a single in this
region (lemma 3, part C). The system may now remain stable in the
region $1 \le z < 1 + \delta$, with equal rates (i.e.  max-min fair
allocations), or move out of the region and converge back and remain
in this region in O(log N) cycles with the rates being equal at every
cycle during this convergence process (lemma 3, part C, note 1). This
final region of stability is in fact the target state space, T, i.e.,
$1 \le z < 1 + \delta$, and allocations are max-min fair.  The maximum
number of cycles to converge to T from an arbitrary initial state is
O(log N). \hfill $\Box$

%\includefige{400pt}{180pt}{rmcell}{RM cell path}{fig:rmcell}
%\includefige{360pt}{225pt}{swmodel}{Switch model}{fig:swmodel}
%\includefigq{270pt}{135pt}{tr-qop-pt}{Target throughput-delay behavior of the system}{fig:erica+-op-pt}
%\includefigq{290pt}{130pt}{tr-qfn}{The queue control function in ERICA}{fig:qctrl-fn}
%\includefige{400pt}{180pt}{gfc2}{The Generic Fairness Configuration-2}{fig:gfc2}
%\putfigsa{gfc2.sim1}{Simulation results with the GFC-2 configuration}{fig:gfc2-sim}
%\includefige{360pt}{170pt}{100tcp}{TCP and VBR configuration}{fig:100tcp}
%\putfigsx{tcp100_1}{Simulation results with the 100 TCP and VBR configuration}{fig:100tcp-sim}
%\includefige{360pt}{225pt}{proof1}{Movement of single bottleneck
%controlled by ERICA towards max-min fairness}{fig:max-min}
%%\newpage


%\includefige{270pt}{180pt}{rev-feed}{Reverse direction feedback}{rev-feed}
%\includefige{270pt}{180pt}{indep}{Independence of source and switch intervals}{indep}
%\putfigq{fig:step}{Step functions for ERICA}{qctrl4}{434}
%\putfigq{fig:linear}{Linear functions for ERICA}{qctrl3}{434}
%\putfigq{fig:hysterisis}{Hysteresis functions for ERICA}{qctrl5}{424}

\end{document}



