Srikant Sharma\ \ \ Tzi-cker Chiueh
Department of Computer Science
Stony Brook
NY-11794
\mycomment{ Despite its popularity, the service providers of metro Ethernet itself are cold to Ethernet deployment in the network core. The metro Ethernet services are provided by tunneling Ethernet frames over traditional circuit switched technologies like SONET, RPR, ATM, or switching technologies like MPLS, etc. Similarly, the popularity Ethernet in Cluster and Storage networks is driven by its interconnection simplicity and cost effectiveness. The deployments are usually monolithic or limited to a few switches with large port densities, exploiting the performance of the switch crossbars rather than the Ethernet technology itself. The primary reason for this trend is the inability to explicitly choose switching paths in Ethernet precluding traffic engineering to maximize the performance on a broader scale. In this paper, we propose a programmable switching paradigm for Ethernet networks, which enables MPLS like switching path selection with fault-tolerant capabilities paving way for traffic engineering and QoS in Ethernet and facilitates efficient reliable multicast beneficial for cluster and storage networks. Programmable switching promises multi-fold throughput gains with sub-second level recovery. This mechanism is realized by relying on simple programmable features of commodity Ethernet switches such as VLAN configurability, status monitoring, rate limiting, and IGMP snooping. Since it does not require any changes to commercially available Ethernet switches, it is readily deployable in today's networks. } Modern Ethernet switches support many advanced features beyond route learning and packet forwarding such as VLAN tagging, IGMP snooping, rate limiting, and status monitoring, which can be controlled through a programmatic interface. Traditionally, these features are mostly used to statically configure a network. This paper proposes to apply them as dynamic control mechanisms to maximize physical network link resources, to minimize failure recovery time, to enforce QoS requirements, and to support link-layer multicast without broadcasting. With these advanced programmable control mechanisms, standard Ethernet switches can be used as effective building blocks for metropolitan-area Ethernet networks (MEN), storage-area networks (SAN), and computation cluster interconnects. We demonstrate the usefulness of this new level of control over Ethernet switches with a MEN architecture that features multi-fold throughput gains and sub-second failure recovery time.
mymacros.tex
%
% Various macros
% **************
%
% Various Commands
% ----------------
%
% \Ol: Overline; Argument im Roman-Style.
% \Ul: Underline; Argument im Roman-Style.
% \hi: high, Slanted-Style.
% \lo: low, Slanted-Style.
% \hilo: high \rightarrow low, Slanted-Style.
% \lohi: low \rightarrow high, Slanted-Style.
% \functim : reference of timing figure in Funktionsbeschreibung
%
%
\newcommand{\Ol}[1]{\(\overline{\rm #1}\) }
\newcommand{\Ul}[1]{\(\underline{\rm #1}\) }
\newcommand{\hi}{{\sl high}}
\newcommand{\lo}{{\sl low}}  
\newcommand{\hilo}{\mbox{{\sl high} $\rightarrow$ {\sl low}}}
\newcommand{\lohi}{\mbox{{\sl low} $\rightarrow$ {\sl high}}}
\newcommand{\functim}[1]{Figure \ref{#1} in Kapitel \ref{Funktionale Timingdiagramme} `Funktionale Timingdiagramme' }
%  
%
% Signal Definitions
% ------------------
%
\newcommand{\berr}{\Ol{BERR}}
\newcommand{\kalah}{{\it Kalah\,}}
\newcommand{\att}{\mbox{AT\,\&\,T\,}}

%
% Sections
% --------
%
% According to the manual ' ' are not allowed in \label.
% But it works ...
% Define macros for two-line titles as well
%
\newcommand{\Pt}[1]{\part{#1}\label{#1}}
\newcommand{\Ch}[1]{\chapter{#1}\label{#1}}
\newcommand{\Se}[1]{\section{#1}\label{#1}}
\newcommand{\Sse}[1]{\subsection{#1}\label{#1}}
\newcommand{\Ssse}[1]{\subsubsection{#1}\label{#1}}
\newcommand{\ChTwo}[2]
{\chapter[#1 #2]{#1 \protect\newline #2}\label{#1 #2}}
\newcommand{\SeTwo}[2]
{\section[#1 #2]{#1 \protect\newline #2}\label{#1 #2}}
\newcommand{\SseTwo}[2]
{\subsection[#1 #2]{#1 \protect\newline #2}\label{#1 #2}}
%
% Lists
% -----
%
\newcommand{\I}{\item}
\newcommand{\Bi}{\begin{itemize}}
\newcommand{\Ei}{\end{itemize}}
\newcommand{\Bn}{\begin{enumerate}}
\newcommand{\En}{\end{enumerate}}
\newcommand{\Bd}{\begin{description}}
\newcommand{\Ed}{\end{description}}
\newcommand{\Bq}[1]{\begin{equation}\label{#1}}
\newcommand{\Eq}{\end{equation}}
\newcommand{\Bqn}[1]{\begin{eqnarray}\label{#1}}
\newcommand{\Eqn}{\end{eqnarray}}
%
%
\newcommand{\isnik}{ISNIK}
\newcommand{\ISNIK}{{\mbox{\bf I\hspace{-.1em}\raisebox{.5ex}{\tiny 
		     $\heartsuit$}\hspace{-.05em}\bf SNIK}}}
%
% Tabulars
% --------
%
\newcommand{\Hl}{\hline}
\newcommand{\Ctr}[2]{\multicolumn{1}{#2}{#1}} 
\newcommand{\BTab} { \vspace{0.3cm} \begin{table}[phtb] \centering }
\newcommand{\ETab}[2] {\caption{#2} \label{#1:tab} \end{table} \vspace{0.3cm} }
\newcommand{\BTAB} { \vspace{0.3cm} \begin{table*}[phtb] \centering }
\newcommand{\ETAB}[2] {\caption{#2} \label{#1:tab} \end{table*} \vspace{0.3cm} }
\newcommand{\re}{\item[\ ]  }
%
%
% Emphasize
% ---------
%
\newcommand{\e}[1]{{\em #1\/}}
%
% Umlauts
% -------
%
\newcommand{\uee}{\"u}
\newcommand{\Uee}{\"U}
\newcommand{\oee}{\"o}
\newcommand{\Oee}{\"O}
\newcommand{\aee}{\"a}
\newcommand{\Aee}{\"A}
%
%
% Index and glossary
% ------------------
%
% X:  index the first argument, the second arg. can give mor info
%     *not* appearing in the text (but in the index entry).
% Xd: denotes the defining (main) index entry.
% Xe: same, but emphasize in the text.
% Xx: is for entries not associated with a word in the text (second entry).
%
% G,Gd,Ge,Gx: analogous for glossary.
% Any glossary term gets an index as well!
%
\newcommand{\X}[2] {#1\index{#1 #2}}
\newcommand{\Xd}[2] {#1\index{!#1 #2}}
\newcommand{\Xe}[2] {{\em #1\/}\index{!#1 #2}}
\newcommand{\Xx}{\index}
\newcommand{\G}[2] {#1\index{#1 #2}\glossary{#1 #2}}
\newcommand{\Gd}[2] {#1\index{!#1 #2}\glossary{!#1 #2}}
\newcommand{\Ge}[2] {{\em #1\/}\index{!#1 #2}\glossary{!#1 #2}}
\newcommand{\Gx}[1] {\index{#1}\glossary{#1}}
%
% Junk
% ----
%
% Simply eats its argument.
%
\newcommand{\junk}[1] {}
%
% References
% ----------
%
\newcommand{\Cr}[1] {Chapter~\ref{#1}}
\newcommand{\Crs}[1] {Chapters~\ref{#1}}
\newcommand{\Sr}[1] {Section~\ref{#1}}
\newcommand{\Srs}[1] {Sections~\ref{#1}}
\newcommand{\Fr}[1] {Figure~\ref{#1}}
\newcommand{\Frs}[1] {Figures~\ref{#1}}
%
% Figures
% -------
%
% Arguments: h|t|b|p, size in cm, name (of file/label), caption,
%	     a comment, arguments passed to special [PsFig, MacFig only]
% Three display modes:
% default:
%		Figure-label, caption and hight, but no white space
% \sizedfigurestrue:
%		Figure-label and caption in the right amount of white space
% \includefigurestrue:
%		Include the figures from file figure-label.psf
%		(if PsFig or MacFig) or figure-label.tex (if TexFig).
% \figurenamesinmargintrue:
%		Print the figure name in the margin (nice to tune text,
%		probably only useful in addition to includefigurestrue)
%
\newif\ifsizedfigures \sizedfiguresfalse
\newif\ifincludefigures \includefiguresfalse
\newif\iffigurenamesinmargin \figurenamesinmarginfalse
%
\newcommand{\Fig}[3]
{
\begin{figure}[htp]
	\parbox{1in}{\vspace*{#1cm}} \
	\caption{#3}
	\label{#2}
\end{figure}

%\begin{figure}[{#1}]
%  \ifsizedfigures
%    \parbox{1in}{\vspace*{#2cm}} \
%    [Cut-And-Paste-Figure ``{#3}'' ({#2} cm): {#5}]
%  \else
%    [Cut-And-Paste-Figure ``{#3}'' ({#2} cm): {#5}]
%  \fi
%  \caption{#4}
%  \label{#3}
%\end{figure}
}
%
% Include a LaTex figure:
%
\newcommand{\TexFig}[5]
{
\iffigurenamesinmargin
  \marginpar{{\tiny {\sloppy ``#3''}}}
\fi
\begin{figure}[{#1}]
  \ifincludefigures
    \include{#3}
  \else
    \ifsizedfigures
      \parbox{1in}{\vspace*{#2cm}} \
      [TeX-Figure ``{#3}'' ({#2} cm): {#5}]
    \else
      [TeX-Figure ``{#3}'' ({#2} cm): {#5}]
    \fi
  \fi
  \caption{{\sl #4}}
  \label{#3}
\end{figure}
}
%
% Include a PostScript figure:
% 
% \PsFig{filepath}{vspace}{caption}{label}
%
\newcommand{\PsFig}[4]
{
\iffigurenamesinmargin
  \marginpar{{\tiny {\sloppy ``#3''}}}
\fi
\begin{figure}[htbp]
  \ifincludefigures
    \vspace*{#2cm}
    \special{psfile=#1}
  \else
    \ifsizedfigures
      \parbox{1in}{\vspace*{#2cm}} \
      [PS-Figure ``{#1}''
		 ({#2} cm)]
    \else
      [PS-Figure ``{#1}''
		 ({#2} cm)]
    \fi
  \fi
  \caption{{\sl #3}}
  \label{#4}
\end{figure}
}
%
% Same, but the (0,0) point is at the upper left:
%
% \PedFig{filepath}{vspace}{caption}{label}
%
\newcommand{\PedFig}[4]
{
\iffigurenamesinmargin
  \marginpar{{\tiny {\sloppy ``#3''}}}
\fi
\begin{figure}[htbp]
  \ifincludefigures
    \special{psfile=#1}
    \vspace*{#2cm}
  \else
    \ifsizedfigures
      \parbox{1in}{\vspace*{#2cm}} \
      [Ped-Figure ``{#1}''
		 ({#2} cm)]
    \else
      [Ped-Figure ``{#1}''
		 ({#2} cm)]
    \fi
  \fi
  \caption{{\sl #3}}
  \label{#4}
\end{figure}
}
%
% Obsolete old name:
%
\newcommand{\MacFig}[6]{\PedFig{#1}{#2}{#3}{#4}{#5}{#6}}
%
% Include a SUNDRAW figure:
% 
% \sfig{label,filename}{size}{caption}
%
\newcommand{\sfig}[3]
{
\begin{figure}[htbp]
  \begin{center}
     { \PS{/usr/kesch/iis/pfister/isnik/doku/sdraw/#1.eps}{#2}}
  \end{center}
  \caption{{#3}}
  \label{#1:fig}
\end{figure}
}
%
% Include a FIG figure:
% 
% \figfig{label,filename}{size}{caption}
%
%
%
\newcommand{\figfig}[3]
{
\begin{figure}[htbp]
  \centerline{\psfig{figure=figs/#1.eps,height=#2}}
  \caption{#3}
  \label{#1:fig}
\end{figure}
}

%
% Include a PS figure:
% 
% \fig{label,filename}{size}{caption}
%
%
%
\newcommand{\fig}[3]
{
\begin{figure}[htbp]
\centerline{\psfig{figure=./figs/#1.eps,height=#2}}
\caption{#3}
  \label{#1:fig}
\end{figure}
}

%\newcommand{\figfig}[3]
%{
%\FigCap{ \PSfig{/usr/kesch/iis/pfister/isnik/doku/figs/#1.ps}{#2}}
%       {\label{#1:fig}#3}
%}
%
% Include a Spoof figure:
% 
% \spfig{size}{label}{caption}
%
%
\newcommand{\spfig}[3]
{
\begin{figure}[htbp]
  \vspace*{#1cm}
  {\special{psfile=/usr/kesch/iis/pfister/isnik/doku/sdraw/#2.spoof.ps vscale=900 hscale=900}}
  \vspace*{1cm}
  \caption{{\sl #3}}
  \label{#2}
\end{figure}
}

psfig.tex
% Psfig/TeX 
\def\PsfigVersion{1.9}
% dvips version
%
% All psfig/tex software, documentation, and related files
% in this distribution of psfig/tex are 
% Copyright 1987, 1988, 1991 Trevor J. Darrell
%
% Permission is granted for use and non-profit distribution of psfig/tex 
% providing that this notice is clearly maintained. The right to
% distribute any portion of psfig/tex for profit or as part of any commercial
% product is specifically reserved for the author(s) of that portion.
%
% *** Feel free to make local modifications of psfig as you wish,
% *** but DO NOT post any changed or modified versions of ``psfig''
% *** directly to the net. Send them to me and I'll try to incorporate
% *** them into future versions. If you want to take the psfig code 
% *** and make a new program (subject to the copyright above), distribute it, 
% *** (and maintain it) that's fine, just don't call it psfig.
%
% Bugs and improvements to trevor@media.mit.edu.
%
% Thanks to Greg Hager (GDH) and Ned Batchelder for their contributions
% to the original version of this project.
%
% Modified by J. Daniel Smith on 9 October 1990 to accept the
% %%BoundingBox: comment with or without a space after the colon.  Stole
% file reading code from Tom Rokicki's EPSF.TEX file (see below).
%
% More modifications by J. Daniel Smith on 29 March 1991 to allow the
% the included PostScript figure to be rotated.  The amount of
% rotation is specified by the "angle=" parameter of the \psfig command.
%
% Modified by Robert Russell on June 25, 1991 to allow users to specify
% .ps filenames which don't yet exist, provided they explicitly provide
% boundingbox information via the \psfig command. Note: This will only work
% if the "file=" parameter follows all four "bb???=" parameters in the
% command. This is due to the order in which psfig interprets these params.
%
%  3 Jul 1991	JDS	check if file already read in once
%  4 Sep 1991	JDS	fixed incorrect computation of rotated
%			bounding box
% 25 Sep 1991	GVR	expanded synopsis of \psfig
% 14 Oct 1991	JDS	\fbox code from LaTeX so \psdraft works with TeX
%			changed \typeout to \ps@typeout
% 17 Oct 1991	JDS	added \psscalefirst and \psrotatefirst
%

% From: gvr@cs.brown.edu (George V. Reilly)
%
% \psdraft	draws an outline box, but doesn't include the figure
%		in the DVI file.  Useful for previewing.
%
% \psfull	includes the figure in the DVI file (default).
%
% \psscalefirst width= or height= specifies the size of the figure
% 		before rotation.
% \psrotatefirst (default) width= or height= specifies the size of the
% 		 figure after rotation.  Asymetric figures will
% 		 appear to shrink.
%
% \psfigurepath#1	sets the path to search for the figure
%
% \psfig
% usage: \psfig{file=, figure=, height=, width=,
%			bbllx=, bblly=, bburx=, bbury=,
%			rheight=, rwidth=, clip=, angle=, silent=}
%
%	"file" is the filename.  If no path name is specified and the
%		file is not found in the current directory,
%		it will be looked for in directory \psfigurepath.
%	"figure" is a synonym for "file".
%	By default, the width and height of the figure are taken from
%		the BoundingBox of the figure.
%	If "width" is specified, the figure is scaled so that it has
%		the specified width.  Its height changes proportionately.
%	If "height" is specified, the figure is scaled so that it has
%		the specified height.  Its width changes proportionately.
%	If both "width" and "height" are specified, the figure is scaled
%		anamorphically.
%	"bbllx", "bblly", "bburx", and "bbury" control the PostScript
%		BoundingBox.  If these four values are specified
%               *before* the "file" option, the PSFIG will not try to
%               open the PostScript file.
%	"rheight" and "rwidth" are the reserved height and width
%		of the figure, i.e., how big TeX actually thinks
%		the figure is.  They default to "width" and "height".
%	The "clip" option ensures that no portion of the figure will
%		appear outside its BoundingBox.  "clip=" is a switch and
%		takes no value, but the `=' must be present.
%	The "angle" option specifies the angle of rotation (degrees, ccw).
%	The "silent" option makes \psfig work silently.
%

% check to see if macros already loaded in (maybe some other file says
% "\input psfig") ...
\ifx\undefined\psfig\else\endinput\fi

%
% from a suggestion by eijkhout@csrd.uiuc.edu to allow
% loading as a style file. Changed to avoid problems
% with amstex per suggestion by jbence@math.ucla.edu

\let\LaTeXAtSign=\@
\let\@=\relax
\edef\psfigRestoreAt{\catcode`\@=\number\catcode`@\relax}
%\edef\psfigRestoreAt{\catcode`@=\number\catcode`@\relax}
\catcode`\@=11\relax
\newwrite\@unused
\def\ps@typeout#1{{\let\protect\string\immediate\write\@unused{#1}}}
\ps@typeout{psfig/tex \PsfigVersion}

%% Here's how you define your figure path.  Should be set up with null
%% default and a user useable definition.

\def\figurepath{./}
\def\psfigurepath#1{\edef\figurepath{#1}}

%
% @psdo control structure -- similar to Latex @for.
% I redefined these with different names so that psfig can
% be used with TeX as well as LaTeX, and so that it will not 
% be vunerable to future changes in LaTeX's internal
% control structure,
%
\def\@nnil{\@nil}
\def\@empty{}
\def\@psdonoop#1\@@#2#3{}
\def\@psdo#1:=#2\do#3{\edef\@psdotmp{#2}\ifx\@psdotmp\@empty \else
    \expandafter\@psdoloop#2,\@nil,\@nil\@@#1{#3}\fi}
\def\@psdoloop#1,#2,#3\@@#4#5{\def#4{#1}\ifx #4\@nnil \else
       #5\def#4{#2}\ifx #4\@nnil \else#5\@ipsdoloop #3\@@#4{#5}\fi\fi}
\def\@ipsdoloop#1,#2\@@#3#4{\def#3{#1}\ifx #3\@nnil 
       \let\@nextwhile=\@psdonoop \else
      #4\relax\let\@nextwhile=\@ipsdoloop\fi\@nextwhile#2\@@#3{#4}}
\def\@tpsdo#1:=#2\do#3{\xdef\@psdotmp{#2}\ifx\@psdotmp\@empty \else
    \@tpsdoloop#2\@nil\@nil\@@#1{#3}\fi}
\def\@tpsdoloop#1#2\@@#3#4{\def#3{#1}\ifx #3\@nnil 
       \let\@nextwhile=\@psdonoop \else
      #4\relax\let\@nextwhile=\@tpsdoloop\fi\@nextwhile#2\@@#3{#4}}
% 
% \fbox is defined in latex.tex; so if \fbox is undefined, assume that
% we are not in LaTeX.
% Perhaps this could be done better???
\ifx\undefined\fbox
% \fbox code from modified slightly from LaTeX
\newdimen\fboxrule
\newdimen\fboxsep
\newdimen\ps@tempdima
\newbox\ps@tempboxa
\fboxsep = 3pt
\fboxrule = .4pt
\long\def\fbox#1{\leavevmode\setbox\ps@tempboxa\hbox{#1}\ps@tempdima\fboxrule
    \advance\ps@tempdima \fboxsep \advance\ps@tempdima \dp\ps@tempboxa
   \hbox{\lower \ps@tempdima\hbox
  {\vbox{\hrule height \fboxrule
          \hbox{\vrule width \fboxrule \hskip\fboxsep
          \vbox{\vskip\fboxsep \box\ps@tempboxa\vskip\fboxsep}\hskip 
                 \fboxsep\vrule width \fboxrule}
                 \hrule height \fboxrule}}}}
\fi
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% file reading stuff from epsf.tex
%   EPSF.TEX macro file:
%   Written by Tomas Rokicki of Radical Eye Software, 29 Mar 1989.
%   Revised by Don Knuth, 3 Jan 1990.
%   Revised by Tomas Rokicki to accept bounding boxes with no
%      space after the colon, 18 Jul 1990.
%   Portions modified/removed for use in PSFIG package by
%      J. Daniel Smith, 9 October 1990.
%
\newread\ps@stream
\newif\ifnot@eof       % continue looking for the bounding box?
\newif\if@noisy        % report what you're making?
\newif\if@atend        % %%BoundingBox: has (at end) specification
\newif\if@psfile       % does this look like a PostScript file?
%
% PostScript files should start with `%!'
%
{\catcode`\%=12\global\gdef\epsf@start{%!}}
\def\epsf@PS{PS}
%
\def\epsf@getbb#1{%
%
%   The first thing we need to do is to open the
%   PostScript file, if possible.
%
\openin\ps@stream=#1
\ifeof\ps@stream\ps@typeout{Error, File #1 not found}\else
%
%   Okay, we got it. Now we'll scan lines until we find one that doesn't
%   start with %. We're looking for the bounding box comment.
%
   {\not@eoftrue \chardef\other=12
    \def\do##1{\catcode`##1=\other}\dospecials \catcode`\ =10
    \loop
       \if@psfile
	  \read\ps@stream to \epsf@fileline
       \else{
	  \obeyspaces
          \read\ps@stream to \epsf@tmp\global\let\epsf@fileline\epsf@tmp}
       \fi
       \ifeof\ps@stream\not@eoffalse\else
%
%   Check the first line for `%!'.  Issue a warning message if its not
%   there, since the file might not be a PostScript file.
%
       \if@psfile\else
       \expandafter\epsf@test\epsf@fileline:. \\%
       \fi
%
%   We check to see if the first character is a % sign;
%   if so, we look further and stop only if the line begins with
%   `%%BoundingBox:' and the `(atend)' specification was not found.
%   That is, the only way to stop is when the end of file is reached,
%   or a `%%BoundingBox: llx lly urx ury' line is found.
%
          \expandafter\epsf@aux\epsf@fileline:. \\%
       \fi
   \ifnot@eof\repeat
   }\closein\ps@stream\fi}%
%
% This tests if the file we are reading looks like a PostScript file.
%
\long\def\epsf@test#1#2#3:#4\\{\def\epsf@testit{#1#2}
			\ifx\epsf@testit\epsf@start\else
\ps@typeout{Warning! File does not start with `\epsf@start'.  It may not be a PostScript file.}
			\fi
			\@psfiletrue} % don't test after 1st line
%
%   We still need to define the tricky \epsf@aux macro. This requires
%   a couple of magic constants for comparison purposes.
%
{\catcode`\%=12\global\let\epsf@percent=%\global\def\epsf@bblit{%BoundingBox}}
%
%
%   So we're ready to check for `%BoundingBox:' and to grab the
%   values if they are found.  We continue searching if `(at end)'
%   was found after the `%BoundingBox:'.
%
\long\def\epsf@aux#1#2:#3\\{\ifx#1\epsf@percent
   \def\epsf@testit{#2}\ifx\epsf@testit\epsf@bblit
	\@atendfalse
        \epsf@atend #3 . \\%
	\if@atend	
	   \if@verbose{
		\ps@typeout{psfig: found `(atend)'; continuing search}
	   }\fi
        \else
        \epsf@grab #3 . . . \\%
        \not@eoffalse
        \global\no@bbfalse
        \fi
   \fi\fi}%
%
%   Here we grab the values and stuff them in the appropriate definitions.
%
\def\epsf@grab #1 #2 #3 #4 #5\\{%
   \global\def\epsf@llx{#1}\ifx\epsf@llx\empty
      \epsf@grab #2 #3 #4 #5 .\\\else
   \global\def\epsf@lly{#2}%
   \global\def\epsf@urx{#3}\global\def\epsf@ury{#4}\fi}%
%
% Determine if the stuff following the %%BoundingBox is `(atend)'
% J. Daniel Smith.  Copied from \epsf@grab above.
%
\def\epsf@atendlit{(atend)} 
\def\epsf@atend #1 #2 #3\\{%
   \def\epsf@tmp{#1}\ifx\epsf@tmp\empty
      \epsf@atend #2 #3 .\\\else
   \ifx\epsf@tmp\epsf@atendlit\@atendtrue\fi\fi}


% End of file reading stuff from epsf.tex
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% trigonometry stuff from "trig.tex"
\chardef\psletter = 11 % won't conflict with \begin{letter} now...
\chardef\other = 12

\newif \ifdebug %%% turn me on to see TeX hard at work ...
\newif\ifc@mpute %%% don't need to compute some values
\c@mputetrue % but assume that we do

\let\then = \relax
\def\r@dian{pt }
\let\r@dians = \r@dian
\let\dimensionless@nit = \r@dian
\let\dimensionless@nits = \dimensionless@nit
\def\internal@nit{sp }
\let\internal@nits = \internal@nit
\newif\ifstillc@nverging
\def \Mess@ge #1{\ifdebug \then \message {#1} \fi}

{ %%% Things that need abnormal catcodes %%%
	\catcode `\@ = \psletter
	\gdef \nodimen {\expandafter \n@dimen \the \dimen}
	\gdef \term #1 #2 #3%
	       {\edef \t@ {\the #1}%%% freeze parameter 1 (count, by value)
		\edef \t@@ {\expandafter \n@dimen \the #2\r@dian}%
				   %%% freeze parameter 2 (dimen, by value)
		\t@rm {\t@} {\t@@} {#3}%
	       }
	\gdef \t@rm #1 #2 #3%
	       {{%
		\count 0 = 0
		\dimen 0 = 1 \dimensionless@nit
		\dimen 2 = #2\relax
		\Mess@ge {Calculating term #1 of \nodimen 2}%
		\loop
		\ifnum	\count 0 < #1
		\then	\advance \count 0 by 1
			\Mess@ge {Iteration \the \count 0 \space}%
			\Multiply \dimen 0 by {\dimen 2}%
			\Mess@ge {After multiplication, term = \nodimen 0}%
			\Divide \dimen 0 by {\count 0}%
			\Mess@ge {After division, term = \nodimen 0}%
		\repeat
		\Mess@ge {Final value for term #1 of 
				\nodimen 2 \space is \nodimen 0}%
		\xdef \Term {#3 = \nodimen 0 \r@dians}%
		\aftergroup \Term
	       }}
	\catcode `\p = \other
	\catcode `\t = \other
	\gdef \n@dimen #1pt{#1} %%% throw away the ``pt''
}

\def \Divide #1by #2{\divide #1 by #2} %%% just a synonym

\def \Multiply #1by #2%%% allows division of a dimen by a dimen
       {{%%% should really freeze parameter 2 (dimen, passed by value)
	\count 0 = #1\relax
	\count 2 = #2\relax
	\count 4 = 65536
	\Mess@ge {Before scaling, count 0 = \the \count 0 \space and
			count 2 = \the \count 2}%
	\ifnum	\count 0 > 32767 %%% do our best to avoid overflow
	\then	\divide \count 0 by 4
		\divide \count 4 by 4
	\else	\ifnum	\count 0 < -32767
		\then	\divide \count 0 by 4
			\divide \count 4 by 4
		\else
		\fi
	\fi
	\ifnum	\count 2 > 32767 %%% while retaining reasonable accuracy
	\then	\divide \count 2 by 4
		\divide \count 4 by 4
	\else	\ifnum	\count 2 < -32767
		\then	\divide \count 2 by 4
			\divide \count 4 by 4
		\else
		\fi
	\fi
	\multiply \count 0 by \count 2
	\divide \count 0 by \count 4
	\xdef \product {#1 = \the \count 0 \internal@nits}%
	\aftergroup \product
       }}

\def\r@duce{\ifdim\dimen0 > 90\r@dian \then   % sin(x+90) = sin(180-x)
		\multiply\dimen0 by -1
		\advance\dimen0 by 180\r@dian
		\r@duce
	    \else \ifdim\dimen0 < -90\r@dian \then  % sin(-x) = sin(360+x)
		\advance\dimen0 by 360\r@dian
		\r@duce
		\fi
	    \fi}

\def\Sine#1%
       {{%
	\dimen 0 = #1 \r@dian
	\r@duce
	\ifdim\dimen0 = -90\r@dian \then
	   \dimen4 = -1\r@dian
	   \c@mputefalse
	\fi
	\ifdim\dimen0 = 90\r@dian \then
	   \dimen4 = 1\r@dian
	   \c@mputefalse
	\fi
	\ifdim\dimen0 = 0\r@dian \then
	   \dimen4 = 0\r@dian
	   \c@mputefalse
	\fi
%
	\ifc@mpute \then
        	% convert degrees to radians
		\divide\dimen0 by 180
		\dimen0=3.141592654\dimen0
%
		\dimen 2 = 3.1415926535897963\r@dian %%% a well-known constant
		\divide\dimen 2 by 2 %%% we only deal with -pi/2 : pi/2
		\Mess@ge {Sin: calculating Sin of \nodimen 0}%
		\count 0 = 1 %%% see power-series expansion for sine
		\dimen 2 = 1 \r@dian %%% ditto
		\dimen 4 = 0 \r@dian %%% ditto
		\loop
			\ifnum	\dimen 2 = 0 %%% then we've done
			\then	\stillc@nvergingfalse 
			\else	\stillc@nvergingtrue
			\fi
			\ifstillc@nverging %%% then calculate next term
			\then	\term {\count 0} {\dimen 0} {\dimen 2}%
				\advance \count 0 by 2
				\count 2 = \count 0
				\divide \count 2 by 2
				\ifodd	\count 2 %%% signs alternate
				\then	\advance \dimen 4 by \dimen 2
				\else	\advance \dimen 4 by -\dimen 2
				\fi
		\repeat
	\fi		
			\xdef \sine {\nodimen 4}%
       }}

% Now the Cosine can be calculated easily by calling \Sine
\def\Cosine#1{\ifx\sine\UnDefined\edef\Savesine{\relax}\else
		             \edef\Savesine{\sine}\fi
	{\dimen0=#1\r@dian\advance\dimen0 by 90\r@dian
	 \Sine{\nodimen 0}
	 \xdef\cosine{\sine}
	 \xdef\sine{\Savesine}}}	      
% end of trig stuff
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\def\psdraft{
	\def\@psdraft{0}
	%\ps@typeout{draft level now is \@psdraft \space . }
}
\def\psfull{
	\def\@psdraft{100}
	%\ps@typeout{draft level now is \@psdraft \space . }
}

\psfull

\newif\if@scalefirst
\def\psscalefirst{\@scalefirsttrue}
\def\psrotatefirst{\@scalefirstfalse}
\psrotatefirst

\newif\if@draftbox
\def\psnodraftbox{
	\@draftboxfalse
}
\def\psdraftbox{
	\@draftboxtrue
}
\@draftboxtrue

\newif\if@prologfile
\newif\if@postlogfile
\def\pssilent{
	\@noisyfalse
}
\def\psnoisy{
	\@noisytrue
}
\psnoisy
%%% These are for the option list.
%%% A specification of the form a = b maps to calling \@p@@sa{b}
\newif\if@bbllx
\newif\if@bblly
\newif\if@bburx
\newif\if@bbury
\newif\if@height
\newif\if@width
\newif\if@rheight
\newif\if@rwidth
\newif\if@angle
\newif\if@clip
\newif\if@verbose
\def\@p@@sclip#1{\@cliptrue}


\newif\if@decmpr

%%% GDH 7/26/87 -- changed so that it first looks in the local directory,
%%% then in a specified global directory for the ps file.
%%% RPR 6/25/91 -- changed so that it defaults to user-supplied name if
%%% boundingbox info is specified, assuming graphic will be created by
%%% print time.
%%% TJD 10/19/91 -- added bbfile vs. file distinction, and @decmpr flag

\def\@p@@sfigure#1{\def\@p@sfile{null}\def\@p@sbbfile{null}
	        \openin1=#1.bb
		\ifeof1\closein1
	        	\openin1=\figurepath#1.bb
			\ifeof1\closein1
			        \openin1=#1
				\ifeof1\closein1%
				       \openin1=\figurepath#1
					\ifeof1
					   \ps@typeout{Error, File #1 not found}
						\if@bbllx\if@bblly
				   		\if@bburx\if@bbury
			      				\def\@p@sfile{#1}%
			      				\def\@p@sbbfile{#1}%
							\@decmprfalse
				  	   	\fi\fi\fi\fi
					\else\closein1
				    		\def\@p@sfile{\figurepath#1}%
				    		\def\@p@sbbfile{\figurepath#1}%
						\@decmprfalse
	                       		\fi%
			 	\else\closein1%
					\def\@p@sfile{#1}
					\def\@p@sbbfile{#1}
					\@decmprfalse
			 	\fi
			\else
				\def\@p@sfile{\figurepath#1}
				\def\@p@sbbfile{\figurepath#1.bb}
				\@decmprtrue
			\fi
		\else
			\def\@p@sfile{#1}
			\def\@p@sbbfile{#1.bb}
			\@decmprtrue
		\fi}

\def\@p@@sfile#1{\@p@@sfigure{#1}}

\def\@p@@sbbllx#1{
		%\ps@typeout{bbllx is #1}
		\@bbllxtrue
		\dimen100=#1
		\edef\@p@sbbllx{\number\dimen100}
}
\def\@p@@sbblly#1{
		%\ps@typeout{bblly is #1}
		\@bbllytrue
		\dimen100=#1
		\edef\@p@sbblly{\number\dimen100}
}
\def\@p@@sbburx#1{
		%\ps@typeout{bburx is #1}
		\@bburxtrue
		\dimen100=#1
		\edef\@p@sbburx{\number\dimen100}
}
\def\@p@@sbbury#1{
		%\ps@typeout{bbury is #1}
		\@bburytrue
		\dimen100=#1
		\edef\@p@sbbury{\number\dimen100}
}
\def\@p@@sheight#1{
		\@heighttrue
		\dimen100=#1
   		\edef\@p@sheight{\number\dimen100}
		%\ps@typeout{Height is \@p@sheight}
}
\def\@p@@swidth#1{
		%\ps@typeout{Width is #1}
		\@widthtrue
		\dimen100=#1
		\edef\@p@swidth{\number\dimen100}
}
\def\@p@@srheight#1{
		%\ps@typeout{Reserved height is #1}
		\@rheighttrue
		\dimen100=#1
		\edef\@p@srheight{\number\dimen100}
}
\def\@p@@srwidth#1{
		%\ps@typeout{Reserved width is #1}
		\@rwidthtrue
		\dimen100=#1
		\edef\@p@srwidth{\number\dimen100}
}
\def\@p@@sangle#1{
		%\ps@typeout{Rotation is #1}
		\@angletrue
%		\dimen100=#1
		\edef\@p@sangle{#1} %\number\dimen100}
}
\def\@p@@ssilent#1{ 
		\@verbosefalse
}
\def\@p@@sprolog#1{\@prologfiletrue\def\@prologfileval{#1}}
\def\@p@@spostlog#1{\@postlogfiletrue\def\@postlogfileval{#1}}
\def\@cs@name#1{\csname #1\endcsname}
\def\@setparms#1=#2,{\@cs@name{@p@@s#1}{#2}}
%
% initialize the defaults (size the size of the figure)
%
\def\ps@init@parms{
		\@bbllxfalse \@bbllyfalse
		\@bburxfalse \@bburyfalse
		\@heightfalse \@widthfalse
		\@rheightfalse \@rwidthfalse
		\def\@p@sbbllx{}\def\@p@sbblly{}
		\def\@p@sbburx{}\def\@p@sbbury{}
		\def\@p@sheight{}\def\@p@swidth{}
		\def\@p@srheight{}\def\@p@srwidth{}
		\def\@p@sangle{0}
		\def\@p@sfile{} \def\@p@sbbfile{}
		\def\@p@scost{10}
		\def\@sc{}
		\@prologfilefalse
		\@postlogfilefalse
		\@clipfalse
		\if@noisy
			\@verbosetrue
		\else
			\@verbosefalse
		\fi
}
%
% Go through the options setting things up.
%
\def\parse@ps@parms#1{
	 	\@psdo\@psfiga:=#1\do
		   {\expandafter\@setparms\@psfiga,}}
%
% Compute bb height and width
%
\newif\ifno@bb
\def\bb@missing{
	\if@verbose{
		\ps@typeout{psfig: searching \@p@sbbfile \space  for bounding box}
	}\fi
	\no@bbtrue
	\epsf@getbb{\@p@sbbfile}
        \ifno@bb \else \bb@cull\epsf@llx\epsf@lly\epsf@urx\epsf@ury\fi
}	
\def\bb@cull#1#2#3#4{
	\dimen100=#1 bp\edef\@p@sbbllx{\number\dimen100}
	\dimen100=#2 bp\edef\@p@sbblly{\number\dimen100}
	\dimen100=#3 bp\edef\@p@sbburx{\number\dimen100}
	\dimen100=#4 bp\edef\@p@sbbury{\number\dimen100}
	\no@bbfalse
}
% rotate point (#1,#2) about (0,0).
% The sine and cosine of the angle are already stored in \sine and
% \cosine.  The result is placed in (\p@intvaluex, \p@intvaluey).
\newdimen\p@intvaluex
\newdimen\p@intvaluey
\def\rotate@#1#2{{\dimen0=#1 sp\dimen1=#2 sp
%            	calculate x' = x \cos\theta - y \sin\theta
		  \global\p@intvaluex=\cosine\dimen0
		  \dimen3=\sine\dimen1
		  \global\advance\p@intvaluex by -\dimen3
% 		calculate y' = x \sin\theta + y \cos\theta
		  \global\p@intvaluey=\sine\dimen0
		  \dimen3=\cosine\dimen1
		  \global\advance\p@intvaluey by \dimen3
		  }}
\def\compute@bb{
		\no@bbfalse
		\if@bbllx \else \no@bbtrue \fi
		\if@bblly \else \no@bbtrue \fi
		\if@bburx \else \no@bbtrue \fi
		\if@bbury \else \no@bbtrue \fi
		\ifno@bb \bb@missing \fi
		\ifno@bb \ps@typeout{FATAL ERROR: no bb supplied or found}
			\no-bb-error
		\fi
		%
%\ps@typeout{BB: \@p@sbbllx, \@p@sbblly, \@p@sbburx, \@p@sbbury} 
%
% store height/width of original (unrotated) bounding box
		\count203=\@p@sbburx
		\count204=\@p@sbbury
		\advance\count203 by -\@p@sbbllx
		\advance\count204 by -\@p@sbblly
		\edef\ps@bbw{\number\count203}
		\edef\ps@bbh{\number\count204}
		%\ps@typeout{ psbbh = \ps@bbh, psbbw = \ps@bbw }
		\if@angle 
			\Sine{\@p@sangle}\Cosine{\@p@sangle}
	        	{\dimen100=\maxdimen\xdef\r@p@sbbllx{\number\dimen100}
					    \xdef\r@p@sbblly{\number\dimen100}
			                    \xdef\r@p@sbburx{-\number\dimen100}
					    \xdef\r@p@sbbury{-\number\dimen100}}
%
% Need to rotate all four points and take the X-Y extremes of the new
% points as the new bounding box.
                        \def\minmaxtest{
			   \ifnum\number\p@intvaluex<\r@p@sbbllx
			      \xdef\r@p@sbbllx{\number\p@intvaluex}\fi
			   \ifnum\number\p@intvaluex>\r@p@sbburx
			      \xdef\r@p@sbburx{\number\p@intvaluex}\fi
			   \ifnum\number\p@intvaluey<\r@p@sbblly
			      \xdef\r@p@sbblly{\number\p@intvaluey}\fi
			   \ifnum\number\p@intvaluey>\r@p@sbbury
			      \xdef\r@p@sbbury{\number\p@intvaluey}\fi
			   }
%			lower left
			\rotate@{\@p@sbbllx}{\@p@sbblly}
			\minmaxtest
%			upper left
			\rotate@{\@p@sbbllx}{\@p@sbbury}
			\minmaxtest
%			lower right
			\rotate@{\@p@sbburx}{\@p@sbblly}
			\minmaxtest
%			upper right
			\rotate@{\@p@sbburx}{\@p@sbbury}
			\minmaxtest
			\edef\@p@sbbllx{\r@p@sbbllx}\edef\@p@sbblly{\r@p@sbblly}
			\edef\@p@sbburx{\r@p@sbburx}\edef\@p@sbbury{\r@p@sbbury}
%\ps@typeout{rotated BB: \r@p@sbbllx, \r@p@sbblly, \r@p@sbburx, \r@p@sbbury}
		\fi
		\count203=\@p@sbburx
		\count204=\@p@sbbury
		\advance\count203 by -\@p@sbbllx
		\advance\count204 by -\@p@sbblly
		\edef\@bbw{\number\count203}
		\edef\@bbh{\number\count204}
		%\ps@typeout{ bbh = \@bbh, bbw = \@bbw }
}
%
% \in@hundreds performs #1 * (#2 / #3) correct to the hundreds,
%	then leaves the result in @result
%
\def\in@hundreds#1#2#3{\count240=#2 \count241=#3
		     \count100=\count240	% 100 is first digit #2/#3
		     \divide\count100 by \count241
		     \count101=\count100
		     \multiply\count101 by \count241
		     \advance\count240 by -\count101
		     \multiply\count240 by 10
		     \count101=\count240	%101 is second digit of #2/#3
		     \divide\count101 by \count241
		     \count102=\count101
		     \multiply\count102 by \count241
		     \advance\count240 by -\count102
		     \multiply\count240 by 10
		     \count102=\count240	% 102 is the third digit
		     \divide\count102 by \count241
		     \count200=#1\count205=0
		     \count201=\count200
			\multiply\count201 by \count100
		 	\advance\count205 by \count201
		     \count201=\count200
			\divide\count201 by 10
			\multiply\count201 by \count101
			\advance\count205 by \count201
			%
		     \count201=\count200
			\divide\count201 by 100
			\multiply\count201 by \count102
			\advance\count205 by \count201
			%
		     \edef\@result{\number\count205}
}
\def\compute@wfromh{
		% computing : width = height * (bbw / bbh)
		\in@hundreds{\@p@sheight}{\@bbw}{\@bbh}
		%\ps@typeout{ \@p@sheight * \@bbw / \@bbh, = \@result }
		\edef\@p@swidth{\@result}
		%\ps@typeout{w from h: width is \@p@swidth}
}
\def\compute@hfromw{
		% computing : height = width * (bbh / bbw)
	        \in@hundreds{\@p@swidth}{\@bbh}{\@bbw}
		%\ps@typeout{ \@p@swidth * \@bbh / \@bbw = \@result }
		\edef\@p@sheight{\@result}
		%\ps@typeout{h from w : height is \@p@sheight}
}
\def\compute@handw{
		\if@height 
			\if@width
			\else
				\compute@wfromh
			\fi
		\else 
			\if@width
				\compute@hfromw
			\else
				\edef\@p@sheight{\@bbh}
				\edef\@p@swidth{\@bbw}
			\fi
		\fi
}
\def\compute@resv{
		\if@rheight \else \edef\@p@srheight{\@p@sheight} \fi
		\if@rwidth \else \edef\@p@srwidth{\@p@swidth} \fi
		%\ps@typeout{rheight = \@p@srheight, rwidth = \@p@srwidth}
}
%		
% Compute any missing values
\def\compute@sizes{
	\compute@bb
	\if@scalefirst\if@angle
% at this point the bounding box has been adjsuted correctly for
% rotation.  PSFIG does all of its scaling using \@bbh and \@bbw.  If
% a width= or height= was specified along with \psscalefirst, then the
% width=/height= value needs to be adjusted to match the new (rotated)
% bounding box size (specifed in \@bbw and \@bbh).
%    \ps@bbw       width=
%    -------  =  ---------- 
%    \@bbw       new width=
% so `new width=' = (width= * \@bbw) / \ps@bbw; where \ps@bbw is the
% width of the original (unrotated) bounding box.
	\if@width
	   \in@hundreds{\@p@swidth}{\@bbw}{\ps@bbw}
	   \edef\@p@swidth{\@result}
	\fi
	\if@height
	   \in@hundreds{\@p@sheight}{\@bbh}{\ps@bbh}
	   \edef\@p@sheight{\@result}
	\fi
	\fi\fi
	\compute@handw
	\compute@resv}

%
% \psfig
% usage : \psfig{file=, height=, width=, bbllx=, bblly=, bburx=, bbury=,
%			rheight=, rwidth=, clip=}
%
% "clip=" is a switch and takes no value, but the `=' must be present.
\def\psfig#1{\vbox {
	% do a zero width hard space so that a single
	% \psfig in a centering enviornment will behave nicely
	%{\setbox0=\hbox{\ }\ \hskip-\wd0}
	%
	\ps@init@parms
	\parse@ps@parms{#1}
	\compute@sizes
	%
	\ifnum\@p@scost<\@psdraft{
		%
		\special{ps::[begin] 	\@p@swidth \space \@p@sheight \space
				\@p@sbbllx \space \@p@sbblly \space
				\@p@sbburx \space \@p@sbbury \space
				startTexFig \space }
		\if@angle
			\special {ps:: \@p@sangle \space rotate \space} 
		\fi
		\if@clip{
			\if@verbose{
				\ps@typeout{(clip)}
			}\fi
			\special{ps:: doclip \space }
		}\fi
		\if@prologfile
		    \special{ps: plotfile \@prologfileval \space } \fi
		\if@decmpr{
			\if@verbose{
				\ps@typeout{psfig: including \@p@sfile.Z \space }
			}\fi
			\special{ps: plotfile "`zcat \@p@sfile.Z" \space }
		}\else{
			\if@verbose{
				\ps@typeout{psfig: including \@p@sfile \space }
			}\fi
			\special{ps: plotfile \@p@sfile \space }
		}\fi
		\if@postlogfile
		    \special{ps: plotfile \@postlogfileval \space } \fi
		\special{ps::[end] endTexFig \space }
		% Create the vbox to reserve the space for the figure.
		\vbox to \@p@srheight sp{
		% 1/92 TJD Changed from "true sp" to "sp" for magnification.
			\hbox to \@p@srwidth sp{
				\hss
			}
		\vss
		}
	}\else{
		% draft figure, just reserve the space and print the
		% path name.
		\if@draftbox{		
			% Verbose draft: print file name in box
			\hbox{\frame{\vbox to \@p@srheight sp{
			\vss
			\hbox to \@p@srwidth sp{ \hss \@p@sfile \hss }
			\vss
			}}}
		}\else{
			% Non-verbose draft
			\vbox to \@p@srheight sp{
			\vss
			\hbox to \@p@srwidth sp{\hss}
			\vss
			}
		}\fi	



	}\fi
}}
\psfigRestoreAt
\let\@=\LaTeXAtSign





switching.tex
%\documentclass[10pt,twocolumn]{article}
%\documentclass[10pt,twocolumn]{IEEEtran}
\documentclass[conference]{IEEEtran}
%\hoffset -1in
%\voffset -1in
%\topmargin 0.75in
%\setlength{\oddsidemargin}{-0.15in}
%\setlength{\evensidemargin}{-0.15in}
%\setlength{\rightmargin}{.625in}
%\setlength{\textwidth}{7.25in}
%setlength{\textheight}{9.25in}
%\setlength{\leftmargin}{.625in}

%\setlength{\textheight}{8.7in}
%\headheight 0in \headsep 0in
%\setlength{\oddsidemargin}{0.25in}
\renewcommand{\thefootnote}{\fnsymbol{footnote}}

\input{psfig}
\input{mymacros}

%% Following for pdf document
\newif\ifpdf\ifx\pdfoutput\undefined\pdffalse\else\pdfoutput=1\pdftrue\fi
\newcommand{\pdfgraphics}{\ifpdf\DeclareGraphicsExtensions{.pdf,.jpg}\else\fi}
\pagestyle{empty}

\usepackage{times}
%\usepackage[pdftex]{graphicx}
\newcommand{\mycomment}[1]{}

\newcommand{\figh}[3]
{
\begin{figure}
%\vspace{-.2in}
%\centerline{\includegraphics[height=#2]{fig/#1.pdf}}
\centerline{\psfig{figure=fig/#1.eps,height=#2}}
%\vspace{-.1in}
\caption{\label{#1:fig} #3}
\end{figure}
}

\newcommand{\figw}[3]
{
\begin{figure}
%\vspace{-.2in}
%\centerline{\includegraphics[width=#2]{fig/#1.pdf}}
\centerline{\psfig{figure=fig/#1.eps,width=#2}}
%\vspace{-.1in}
\caption{\label{#1:fig} \small #3}
\end{figure}
}



\newcommand{\myfig}[3]
{
\begin{figure}[t]
\centerline{\psfig{figure=fig/#1.eps,width=#2}}
\caption{\small #3}
\label{#1:fig}
\end{figure}
}

\newcommand{\kfig}[3]
{
\begin{figure}
\centerline{\psfig{figure=fig/#1.eps,height=#2}}
\caption{\small{#3}}
\label{#1:fig}
\end{figure}
}

\begin{document}
%\title{\bf A Programmable Switching Paradigm for Ethernet Networks
\title{\bf Programmable Ethernet Switches and Their Applications 
}
\author{
Srikant Sharma\ \ \ Tzi-cker Chiueh \\
{\small \{srikant,chiueh\}@cs.sunysb.edu}    \\
Department of Computer Science \\
Stony Brook University, Stony Brook, NY-11794\\ 
}

\date{}
\maketitle


%Introduction
%  o Efforts to reduce the gap between L2 and L3
%  o Routing Switches
%  o IP switch
%  o Gigabit routing on RAW
%  o MPLS
%  o Ethernet in the First Mile
%  o Applicable to Ethernet core networks
%  o Who can benefit?
%    x Metro Networks
%    x Low latency synchronous Storage Area Networks
%    x System Area Networks
%
%Mechanism
%  o Issues
%    x Link Enabling 
%      # VLANs
%      # Multicast IGMP snooping
%      # Disconnected components
%    x QoS provisioning
%      Why global view is required? .. why QoS in IP is tough? ... how can resource provisioning
%      help?
%      Reservation for qos traffic, residual bandwidth for best effort traffic
%    x Traffic Engineering : Pathfinder
%      # LCBR
%      # Hose Model
%      # Multicast groups
%  o Desired Programmability Features
%    x VLAN based Spanning Tree configuration
%    x IGMP snooping
%    x Rate limiting
%
%Applications
%  o Metro Ethernet
%    x VLANs and multiple spanning trees, LCBR
%  o Storage Area Networks
%    x in network replication
%    x Reliable link layer multicast, merging for primary and log disk
%    x fast response from logdisk (trail) can be used to infer synchronous write
%  o System Area Networks
%    x HECs can be connected using multicast groups
%    x Multicast group limit is the challenge
%
%Performance
%  o Metro Ethernet
%  o viking performance
%
%Conclusion

\begin{abstract}
\mycomment{
Despite its popularity, the service providers of metro Ethernet itself are
cold to Ethernet deployment in the network core. The metro Ethernet services
are provided by tunneling Ethernet frames over traditional circuit switched technologies
like SONET, RPR, ATM, or switching technologies like MPLS, etc. Similarly,
the popularity Ethernet in Cluster and Storage networks is driven by
its interconnection simplicity and cost effectiveness. The deployments are
usually monolithic or limited to  a few switches with large port densities, 
exploiting the performance of the switch crossbars rather than the Ethernet technology itself.
The primary reason for this trend is the inability to explicitly choose
switching paths in Ethernet precluding traffic engineering to maximize the performance on a broader scale.
In this paper, we propose a programmable switching paradigm for Ethernet networks, which enables
MPLS like switching path selection with fault-tolerant capabilities paving way for traffic engineering
and QoS in Ethernet and facilitates efficient reliable multicast beneficial for cluster and storage networks.
Programmable switching promises multi-fold throughput gains with sub-second level recovery.
This mechanism is realized by relying on simple programmable features of commodity Ethernet switches
such as VLAN configurability, status monitoring, rate limiting, and  IGMP snooping. Since it does
not require any changes to commercially available Ethernet switches, it is readily deployable in today's
networks.
}
Modern Ethernet switches support many advanced features beyond route
learning and packet forwarding such as VLAN tagging, IGMP snooping,
rate limiting, and status monitoring, which can be controlled through
a programmatic interface. Traditionally, these features are mostly used
to statically configure a network. This paper proposes to apply them as
dynamic control mechanisms to maximize physical network link resources,
to minimize failure recovery time, to enforce QoS requirements, and to
support link-layer multicast without broadcasting. With these advanced
programmable control mechanisms, standard Ethernet switches can be used as
effective building blocks for metropolitan-area Ethernet networks (MEN),
storage-area networks (SAN), and computation cluster interconnects. We
demonstrate the usefulness of this new level of control over Ethernet
switches with a MEN architecture that features multi-fold throughput
gains and sub-second failure recovery time.

\end{abstract}
{\small
Keywords: System design, Simulations, Experimentation with real networks/Testbeds, Ethernet, 
Spanning Tree.
}

\Se{Introduction}
% Ethernet is becoming the ubiquitous networking technology
% Metro Ethernet, Gigabit Ethernet, 10G, EFM
%\mycomment{
Ethernet technology has come a long way from its initial shared-media 10
Mbps capability to today's switched-media form providing throughput up to
several Gbps. Its simplicity, cost effectiveness,  and the
economies of scale have enabled it to make forays into practically
various scales of networks, including metropolitan area networks.
%ease of connectivity have enabled Ethernet to make forays into
%the metropolitan area networks (MAN). 
Recent technological
advances, such as Ethernet in the First Mile~\cite{8023ah}, which
enables subscribers to connect to an Ethernet-based core network over a wide
variety of media ranging from voice grade copper to multi-mode fiber,
further reinforce the case of metropolitan Ethernet network (MEN) architecture.
Bandwidth availability of up to 10~Gbps and micro-second
level message latencies also make Ethernet a low-cost alternative to
widely used cluster interconnects (CI) such as Myrinet~\cite{myrinet},
Quadrics~\cite{quadrics}, and Infiniband~\cite{infiniband}. Finally, with the increasing
momentum of IP storage, 
Ethernet-based storage area networks (SAN) are becoming  formidable challengers
against fiber channel-based SAN because of lower cost and additional flexibility. 
These new applications
of Ethernet elevate it from a LAN technology to a ubiquitous networking
technology.

\mycomment{
% MPLS, IP Switching etc. are solutions to reducing the routing complexities
% Switching all the way yields low latency packet dispatch
Communication in large scale network has to deal with one very contentious
issue of whether to choose communication paths between a pair of nodes
based on routing or switching.  There are many obvious advantages of
routing over conventional switching, such as, added fault tolerance,
higher network utilization, adaptability to congestion etc. However,
with increasing intelligence in switching devices, the distinction
between routing and switching is getting blurred. Earlier, the Layer-2
switching devices addressed bottlenecks within LAN environments. With
increasing network speeds, Layer-3 devices had to keep up by moving
the forwarding logic to high speed switching hardware resulting in
Layer-3 switches. Multiprotocol Label switching (MPLS)~\cite{mpls}
provided further improvement in high speed packet forwarding by reducing
the problem of variable length IP prefix lookup to fixed length label
lookup. These labels, embedded in packet headers, are used to determine
the switching path for packets belonging to different flows.  This
mechanism enables explicit selection of paths which are not necessarily
the shortest paths thus enabling traffic engineering~\cite{te-qos} and
QoS in networks. All these developments point to the obvious trend to
,``Switch packets as long as one can and route them when one must.''  }

% Results in large Ethernet Core networks
% Metro, SAN, High Perf Interconnect System Area Networks
% Brief overview of issues in Ethernet Core
% QoS, Spanning Tree, Load balancing, Multicast
Many Metro Ethernet services today are actually built on  
circuit switched technologies such as SONET, ATM, RPR, or
established packet switching technologies like MPLS etc.
These services are actually provided by means of tunnels set up 
over these physical carrier technologies. Deployment of standard  
Ethernet switches in the core is still very rare, because there are
several architectural deficiencies with switching in Ethernet.
First, Ethernet networks
use a spanning tree protocol (IEEE 802.1d)~\cite{8021d} to
establish a path between any pair of nodes. 
It is well known that
the spanning tree approach fails to exploit all the physical network resource.
In addition, failure of switches and links requires rebuilding the
of spanning tree, which is a lengthy process.  IEEE 802.1w~\cite{8021w},
the rapid spanning tree configuration protocol (RSTP),  mitigates this
problem by providing mechanisms to detect failures and quickly reconfigure
the spanning tree. However, the recovery period can still range from an
optimistic 10 milliseconds to more realistic multiple seconds {\em after} failure detection,
which is still not adequate for many applications.  
Second, Ethernet does not support any
mechanism akin to MPLS~\cite{mpls}, which allows the user to route packets/flows 
along a particular path. As a result, it is impossible to  
apply any traffic engineering technique~\cite{te-qos} to balance traffic load
across the network. Traffic engineering may not be useful in small
local area networks, but is very important in the context of MAN,
SAN, and CI. In particular, the ability to route traffic on a given route
can also greatly help enforcing QoS by leveraging the traffic 
prioritization scheme (IEEE 802.1p)~\cite{8021p}, which  
prioritizes certain classes of
traffic over others.

%For storage and cluster
%networks, Ethernet is a good fit because of cost and simplicity
%reasons.
%and the thrust of adaptation is not driven by only
%comparable if not better performance.

% Our solution in brief
% MPLS realization in Ethernet 
% Use VLAN ids as MPLS ids
% Shortage of VLANs ? .. use multicast and IGMP snooping
% QoS and Load balancing: Switching paths based on load characterization
% SAN, use multicast to save bandwidth and TCP coalescing, can be done at switches
% System Area Networks, use VLANs and IGMP snooping

The key insight of this work is that modern Ethernet switches incorporate 
advanced network control mechanisms that are programmatically configurable 
and could be used to improve the aggregate throughput, the availability 
and the QoS.
Virtual LAN (VLAN)~\cite{8021q} technology 
provides a mechanism to a physical subnet into 
multiple broadcast domains to improve the security
and performance of LANs. Multiple spanning tree (MST) protocol~\cite{8021s}
makes it possible
to configure multiple spanning tree instances on 
a network, each associated with a distinct VLAN, to isolate traffic from one
another.  Many commercially available Ethernet switches also support IGMP
snooping~\cite{igmpsnoop} for making intelligent multicast forwarding
decision by examining the Layer-3 IP headers and  use the network
resources more efficiently. Finally, most Ethernet switches can  
limit the rate of incoming or outgoing packets over their physical interfaces.


Most of these advanced structuring mechanisms in modern Ethernet switches 
are accessible through SNMP, HTTP, or command line interface.
It is possible to remotely configure VLANs and their associated spanning trees,
IGMP snooping and interface rate limits using management protocols.
It is also possible to remotely monitor switches for failures
and different activities can be triggered in reaction to these failure
events.  These features are thus referred to as programmable features of
modern Ethernet switches.

In this paper, we show that the programmable control mechanisms 
of modern Ethernet switches can be used to build 
the following high-level functionalities that are critical to 
MEN, SAN, and CI applications -- 
(i)~Enable traffic engineering that in turn routes
packet traffic to balance the load of physical network links. 
Routes obtained from switching path selection
are enforced by means of VLAN tags in a fashion similar to MPLS
labels. (ii)~Enable proactive switch and link disjoint backup path
provisioning to provide a very high degree of tolerance of  
switch or link failures. (iii)~Use rate limiting features of
Ethernet switches to regulate the bandwidth consumption of end nodes in
order to isolate different traffic from one another. (iv)~Use IGMP
snooping and link-layer multicast to support link-layer multicasting 
without broadcasting.

%and facilitating state checkpointing
%and message logging with lower bandwidth consumption.

\mycomment{
This paper is organized as follows: In Section~\ref{Switching Path
Selection}, we discuss how load balanced switching path selection can be
enabled in Ethernet environment and how status monitoring features of commodity
Ethernet switches can be used to provide fault tolerance features in
such a load balanced environment.  In Section~\ref{Efficient Reliable
Multicast}, we discuss how Layer-3 awareness of Ethernet switches can be
used to provide an efficient link-layer reliable multicast mechanism
in Ethernet. The requirement about QoS enforcement in Ethernet is
discussed in Section~\ref{QoS Enforcement}.  We discuss about the overall
programmability requirements and some implications about use of these
features in different networks. We give details about some performance
benefits that can be obtained from this programmable switching paradigm in
Section~\ref{Performance Benefits}.  Finally, we summarize the discussion
in Section~\ref{Conclusion}.
}


%Mechanism
%  o Issues
%    x Link Enabling 
%      # VLANs
%      # Multicast IGMP snooping
%      # Disconnected components
%    x QoS provisioning
%      Why global view is required? .. why QoS in IP is tough? ... how can resource provisioning
%      help?
%      Reservation for qos traffic, residual bandwidth for best effort traffic
%    x Traffic Engineering : Pathfinder
%      # LCBR
%      # Hose Model
%      # Multicast groups
%  o Desired Programmability Features
%    x VLAN based Spanning Tree configuration
%    x IGMP snooping
%    x Rate limiting
%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\figw{load-imbalance}{2in}{Load imbalance scenario in spanning
tree based switching. Three different flows, A-to-B, A-to-Root, and
Root-to-B share same set of links despite the presence of a link between
switch A and B. If somehow flow A-to-B can be switched along link A-B, 
the overall network throughput can be improved significantly.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\Se{Switching Path Selection}
% What is the current status ?
In Ethernet, packets are always switched along the spanning tree of
the network.  The sender nodes\footnote{Throughout this paper, we use
the terms {\em nodes} and {\em hosts} to refer to the end-hosts that
are connected to a switched networks. The switch-nodes of the network
are always explicitly referred as {\em switches} in the paper.}  do not
have any control over the switching path.  In large scale networks like
MAN, the number of network elements (links and switches) involved in
a path between far off end-hosts is usually high.  Failure of any of
these elements can cause a complete communication breakdown between the
given pair of end-hosts.  Further, the intermediate links are shared by
multiple switching paths.  This sharing may lead to an overload situation
and the absence of alternate switching paths precludes any scope of load
balancing by offloading traffic to other links.  \mycomment{This would
happen even if redundant links are provided in the network because of
the very nature of STP to put the redundant links in blocking state.}
Figure~\ref{load-imbalance:fig} depicts a typical load imbalance scenario
when switching is done along a spanning tree.

Storage and cluster networks primarily  require  high
switching bandwidth and low communication latency between different
nodes. In switched Ethernet, the peak bandwidth between any two segments
is limited by the bandwidth of the link connecting them.  Addition of
multiple links does not improve the situation because, in spanning
tree topology, there can be only one active link forwarding traffic
to a segment. Thus, the general tendency is to aggregate the cluster
nodes on a single switch with high port density.  The aggregation cost
of switching networks increases rapidly with the size of the cluster
which in turn raises the per port cost factor.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}
\begin{center}
{\sf
{\small
\begin{tabbing}
abc\=foo\=foo\=foo\=foo\=foo\=foo\=foo\=foooooooooooo\=\kill
\>\> Let the set of all load balanced paths be $P$ \\
\>\> Let the set of all edge pairs be $EP$ \\
\>\> Let the set of spanning trees be $S$ \\
\>\> Let $S$ = $\phi$ \\
\>\> Sort the members of $P$ in the descending order of path \\
\>\> length \\
\>\> While ($EP$ $!=$ $\phi$ and $P$ $!=$ $\phi$ ) \\
\>\> Sort the members of $EP$ in descending order of their \\
\>\> frequency of  appearance in members of $P$ \\
\>\>\> Let $ep$ = Next element in $EP$ \\
\>\>\> While $\exists$ $p$ $\in$ $P$ such that $ep$ $\subset$ $p$ \\
\>\>\>\> Remove $p$ from $P$ \\
\>\>\>\> Find $s$ $\in$ $S$ such that $p$  and $s$ do not form a loop \\
\>\>\>\> Merge  $p$ with $s$ \\
\>\>\>\> If no such $s$ is found, add $p$ to $S$ \\
\end{tabbing}
}
}
\end{center}
\vspace{-0.1in}

\caption{\small Path Aggregation algorithm. For the given input of
selected paths $P$ and the network topology, the algorithm computes
a set of spanning trees. Each spanning tree can be associated with a
unique VLAN.}

\label{alg:aggregation}
%\vspace{-0.3in}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\Sse{VLAN-based switching} 

IEEE 802.1s MST protocol allows for the existence of multiple spanning
trees in an Ethernet network, where each spanning tree corresponds to
different VLANs. These multiple spanning trees can be used to provide load
balanced and fault-tolerant switching paths for different communicating
nodes.  Given the traffic profile or traffic requirements of any network,
one can come up with different load balanced switching paths such that
the overall network utilization is efficient~\cite{gopalan03efficient}.
These load balanced switching paths can be aggregated together such that
there are no loops in the aggregation. Such a constrained aggregation
would yield multiple spanning trees. Each spanning tree can further be
associated with a unique VLAN tag. The details of deriving load balanced
switching paths and grouping them into multiple spanning trees are
discussed in~\cite{viking}.  The path aggregation algorithm is shown in
Figure~\ref{alg:aggregation} for quick reference. This algorithm tries to
minimize the overall  number of spanning trees and hence VLANs required
after aggregation. Since the number of overall spanning trees required
is inversely proportional to the number of paths grouped together,
the number of spanning trees can be reduced by including larger number
of paths together. To increase the number of paths per spanning tree,
the algorithm tries to merge paths which share {\em common features}
such as sub paths, edges, or simply nodes. The end result would be
that each load balanced path is part of a spanning tree which is identified
by a unique VLAN tag.

For every incoming packet, the switches analyze the Ethernet header
for VLAN tags.  If a VLAN tag is found, the packet is switched along
the corresponding spanning tree.  Thus, any specific switching path can
be selected by simply inserting the appropriate VLAN tag in the packet
header. A host can insert different VLAN tags while communicating with
different destination nodes and thus can select different load balanced
switching paths.  This mechanism is very much analogous to MPLS, where
the packet switching paths are selected based on the labels present in
packet headers. The difference is that, in MPLS, the labels are inserted
by ingress routers, whereas here the VLAN tags need to be inserted by
the end hosts.

This VLAN-based switching is feasible only if a desired VLAN spanning
tree can be imposed (configured) on any network. This is where the
programmability features of Ethernet switches come into picture. Almost
all switches, which provide support for 802.1s MST protocol, also
facilitate programmability of links in terms of associated VLANs. Usually,
whenever VLANs are associated with different switches (links) in a
switched network, the switches participate in a distributed spanning tree
setup process and build a packet forwarding spanning tree. However, if the
links with which a particular VLAN is associated already form a spanning
tree, this spanning tree becomes the default switching spanning tree for
that VLAN. Thus, with the availability of VLAN programmability features in
switches, it is possible to realize this programmable VLAN-based switching
which enables efficient traffic engineering.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\figw{backup}{2.2in}{Event monitoring based failure recovery mechanism.
The Status Monitor registers with all switches (0-9) for event
notifications. Node A and Node B communicate with each other using
path 0-3-6-7-9 over VLAN P. The failure of link 3-6 is detected by
switch 3 and the status monitor is notified about it. The status
monitor determines the list of all affected sender nodes and sends
them notifications to start using alternate VLANs.  In this case,
Node A receives a notification to use alternate VLAN Q which provides
the path 0-1-4-5-9. The entire recovery period comprises of failure
detection, failure notification to the status monitor, status monitor
lookup for alternate VLANs, and notification to the affected nodes.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\Sse{Fault Tolerance}

Most managed (programmable) switches provide status monitoring facilities
where one can remotely setup traps which can get triggered  by various events like,
link failure, neighboring switch failure, link recovery, switch recovery,
neighbor discovery, etc. Using these traps one can detect topology changes
and failures in the network. If for every communicating host-pair, a backup
path is provisioned, it is easy to deal with failure scenario by simply
switching the communication over to the VLAN that corresponds to the
backup path.  In order to deal with failure of any switch or link in the
communication path, the backup path must be a link and switch disjoint
path to the primary path.  Due to the disjoint nature,  the primary and
backup paths belong to different spanning trees (and hence different
VLANs). Failures in one spanning tree do not affect other spanning trees
which do not include the failed links. Since the primary and backup paths
are pre-provisioned through traffic engineering, the fail-over duration
is limited to failure detection and event communication latencies between
switch and the status monitoring nodes.  The failure detection latencies
for commercially available managed switches such as Cisco Catalyst 2924
range from 400 to 500 milliseconds.  The fail-over period observed in
this case does not exceed 500 to 600 milliseconds and is consistently in
the sub-second range.  This is a significant improvement over multiple
second fail-over latency of 802.1w RSTP deployment. Note that, 802.1w
failure recovery period does not take into account the failure detection
period and is just the convergence period for spanning tree recovery.

One caveat about the above mentioned detection and recovery mechanism
is that it needs the presence of  status monitoring node(s) in the
network which is(are) aware of the entire network topology and the traffic
provisioning therein. Further, it is essential that the status monitoring
node is always reachable from all the switched in the network and all
nodes which need to be notified about the failure and the new VLAN tags
that need to be used.  If a network failure  disrupts the communication
path between the failure detecting switch and the monitoring node
itself, the fail-over mechanism cannot proceed.  However, this situation
can be overcome by dispatching the failure notification over multiple
communication paths to the status monitoring node. Another possibility
is to have multiple status monitoring nodes strategically located in
the network such that at least one status monitoring node can communicate
with  the failure detecting switch and all the affected nodes. An example
failure recovery scenario is depicted in Figure~\ref{backup:fig}.

\Se{Efficient Reliable Multicast}

Nodes in any high end cluster interconnect need to communicate with
each other for exchanging data as well as perform state checkpointing
and message logging for fault tolerance. It is often the case that
the same data is transmitted to multiple nodes during checkpointing and
message logging. For example, the cluster nodes may exchange periodic
heartbeat messages with  several other nodes monitoring the health of the
entire cluster.  The state checkpointing data may be replicated across
multiple nodes for an increased level of fault tolerance.  In storage
area networks, data is usually mirrored over multiple storage nodes. In
all these cases, the network performance can be significantly improved if
such communication is done over a multicast protocol rather than unicast
protocol. Traditionally, link-layer multicast over Ethernet networks was
implemented through coarse broadcast-and-filter semantics. The Ethernet
switches treated link-layer multicast packets as broadcast packets and the
transmission was done over all the switch port.  The onus of filtering out
irrelevant broadcast packets on the basis of destination MAC addresses
was placed on the end-host network interface cards (NICs). Though this
mechanism relieved end-host CPUs from redundant packet processing burden,
the network performance suffered significantly because of unnecessary
packet forwarding to all the ports.

Fortunately, most modern Ethernet switches, particularly Gigabit switches,
support a feature called {\em IGMP snooping}, which was designed to
support IP multicast without using link-layer broadcasting. In the IP
multicast schema, a node can join or leave a multicast group by sending
a {\tt join} or {\tt leave} IGMP~\cite{igmp} packets to the designated
routers which take care of propagating these messages to upstream routers.
In order to avoid redundantly broadcasting  the downstream multicast
traffic, Ethernet switches monitor these IGMP {\tt join} and {\tt leave}
messages to determine the ports on which the multicast traffic needs to
be forwarded. Subsequently, all downstream multicast traffic is forwarded to
only specific ports.

Although IGMP snooping was designed to improve the efficiency of IP
multicast on switched Ethernet networks, it can be exploited to support
link-layer multicast as well. Whenever a multicast group rooted at a
particular node needs to be created, the only thing the participating
nodes need to do is to send an IGMP {\tt join} message to the root
node. The intermediate switches would monitor the IGMP messages and
construct a spanning tree connecting the participating ports. Once such
a spanning tree is established, all multicast packets are forwarded along
the spanning tree rather than link-layer broadcasting.  If different such
spanning trees, catering to different multicast groups, are pre-configured
through traffic engineering for efficient network performance, all these
trees can be aggregated together in a way similar to path aggregation
described in Figure~\ref{alg:aggregation}.  This aggregation would yield
system-wide spanning trees.  These spanning trees can then be constructed
in the network by using the programmable features mentioned earlier.

The reliability of the link-layer multicast can be ensured by implementing
a positive acknowledgment and timeout based scheme. In this scheme,
after every multicast transmission, the sender sets a timer and expects
every receiver in the group to return an acknowledgment before
the timer expires. If some receivers fail to acknowledge the reception
in time, the sender can resort to unicast transmission to each such
receiver. This scheme is simple and efficient, and is optimized for the
case when packet drops and corruptions are extremely rare, as in the
case of switched Ethernet networks.

% Talk about in-network replication here.
% Latency reduction
% Bandwidth savings
% Consistency issues
% This multicast mechanism is highly beneficial in storage area networks where
% data may be mirrored over several storage nodes. 

The number of link-layer multicast groups a switch can support is
limited.  Typically, the commodity switches can support up to
500 multicast groups.  To perform traffic engineering based on the
communication profile of all the nodes and to limit the number of
per-switch multicast groups  are some of the key challenges in multicast
provisioning. These problem can be addressed  by maximizing the number of
nodes that can share a multicast tree without affecting the overall performance
and then performing traffic engineering.  There can be various
ways the traffic engineering can be performed. One of the plausible
ways is to use the {\em hose} model~\cite{hose} developed for resource
management in VPNs. Though this model is challenging to support from
traffic provisioning aspect, it captures the essence of multicast traffic
in the sense that the traffic profile specification is in the form of
the amount traffic moving in and out of the nodes rather than pairwise
statistics as required by the traditional pipe models.

%\Se{Traffic Engineering}

\Se{QoS Enforcement}
Traffic engineering and bandwidth provisioning alone cannot provide
quality of service in a network. It requires network usage policing
and regulation to provide a desired degree of QoS in the network.
Without usage regulation, the best one can do is to provide QoS
on the lines of priority based DiffServ~\cite{diffserv} in the
Internet. This kind of mechanism is inadequate to insulate different
traffic flows from one another and is not an acceptable scenario in
MAN where adherence to service level agreement (SLA) is a very crucial
requirement. Ethernet also specifies a DiffServ like traffic class
prioritization mechanism~\cite{8021p} which is supported by almost
all Ethernet switches. But it is clearly inadequate because of lack of
global enforcement.

The key to regulate the network usage and insulate different traffic flows
from one another is to monitor and enforce the usage right at the ingress
points in the network. If the amount of inflow network traffic does
not exceed the total engineered traffic, different traffic flows cannot
affect each other unless some of the network elements have failed. If
the traffic engineering is performed with proper backup provisioning, it
can be ensured that all the traffic flows are insulated from each other even
after failures.

Many mid-end and high-end Gigabit Ethernet switches support programmable
rate limiting features. For efficient wire speed,
these features are usually implemented in hardware. Rate limiting
can be used to provide restricted bandwidth usage based on predefined
profile or per physical port usage. Excess traffic can either be dropped
or reprioritized.  Though typically supported programmable parameters
of rate limiting are quite extensive, it can be simply specified  in
terms of the raw bandwidth limitations and the burst size limits. Using
these rate limiting features, it is possible to regulate the inflowing
traffic at the ingress ports. The amount of allowed inflow traffic
can be determined from the SLA in metro network scenario or from the
traffic characterization in the cluster interconnect scenario. Further,
the 802.1p traffic classification and prioritization can be used to mark
lower priority for the traffic that is sent in excess of the allowed
traffic so that  this  traffic is serviced only if there is spare
bandwidth available on every link and every switch along the path.

\Se{Programmability Requirements}
% Features required
To realize the programmable switching Ethernet paradigm there are
certain minimum features that should be supported by the switches in
the network. The most important feature is the 802.1q tag based VLAN
support with 802.1s MST support. This feature needs to be supported
by all the switches in the network.  Similarly, all switches also
need to support link and switch status monitoring capability for fault
tolerance. Further, for a robust fault tolerance mechanism, the status
monitoring node needs to be able to communicate with all the switches
even after multiple failure.  This can be achieved by sending multiple
failure notification over different paths. Another alternative can be
to place multiple status monitors at strategic locations in the network.

% QoS rate limiting needs to be looked into : too strict
The rate limiting feature is required to regulate the inflow of traffic
from end-hosts. It is worth exploring,  whether  all switches in the network need
to support this feature. Rate limiting is essential only when an end-host is
connected to a switch. In MAN setup, the switches can be classified
as core switches and edge switches where the edge switches serve as
ingress points. The core switches need not participate in the rate
limiting activity as the edge switches ensure that the traffic reaching
core switches is already rate limited. This mechanism is analogous to
ingress filtering in Internet.  An alternate viewpoint can be that,
usually there is spare bandwidth available at the edges but the core
of the network carries most of the traffic, so it should be the core
where bandwidth regulation takes place rather than at the edges. This
argument also has some merit in it.  However, the final decision can
be made only after traffic engineering. But unfortunately, traffic
engineering requires the knowledge of topology which usually gets
acquired after deployment. Moreover, when bandwidth provisioning is done
based on customer requirements and SLAs, service providers prefer to use
statistical multiplexing to maximize the network utilization.  The rate
limiting feature cannot deal with congestion occurring because of inherent
inability of statistical multiplexing to deal with worst case scenario.

In cluster and storage networks, potentially all switches may support
end-hosts. This makes it essential to support rate limiting at all
the switches. Also, the traffic profile may change from time to time.
Strict rate limiting on a changing traffic profile fails to capture
the changing requirement and hence is inappropriate. The proper way
to tackle this is to adapt soft rate filtering with re-prioritization
of excess traffic so that no traffic is dropped as long as there is
network capacity available to service it.  In addition, if the current
traffic profile differs significantly from the profile used for bandwidth
provisioning, traffic re-engineering needs to be carried out

% Requirement of a central controller
% Distributed nature is lost
% Traffic monitoring
Throughout the discussion, we implicitly assumed the availability of
traffic monitoring and engineering mechanism. Traditional pipe model
based traffic engineering requires pairwise load statistics for all
end-hosts. Even if traffic specifications is provided by customers, as in
MAN case, precise traffic profiling is required to exploit statistical
multiplexing. Commodity Ethernet switches maintain statistics such that
the amount of traffic entering and leaving the ports and some other
finer details such as traffic per VLAN, amount of multicast traffic, etc.
This is clearly insufficient to build a complete pairwise traffic profile.
There are two possible solutions to this problem.  The traffic engineering can use
the  {\em hose model}~\cite{hose} of resource management. This model 
provides the flexibility of traffic specification in terms of required 
input and output capacities at the end-hosts rather than a pairwise
traffic matrix. However, resource provisioning becomes a tougher problem
to solve in this context. An alternative is to modify the end-hosts to keep
track of pairwise traffic between all peers. These end-hosts can then
periodically communicate these statistics to the nodes responsible for
traffic engineering. This approach is feasible in storage and cluster
networks where all the nodes fall under a common administrative domain.

% VLAN selection capability
Whenever end-hosts need to communicate with other peers, the switching
path is selected by specifying the VLAN corresponding the spanning tree
along which the packets are switched. The sending node needs to insert the
appropriate VLAN tag in the packet header. This tag needs to be obtained
from some node aware of traffic engineering. Further, during fail-over,
the status monitors inform the sender nodes to change over to backup
VLANs.  This requires all senders to be aware of the path-selection
and fail-over mechanism in order to comply with and utilize them. It
may not be possible to modify the network stack of customer nodes in
environments like MAN.  In such cases, the service provider can address
this problem by placing proxy nodes which take care of interacting with
service provider nodes.

% 802.1ad Stacked VLANs

% Reference design

% Direct response to end hosts rather than status monitor


\mycomment{
\Sse{Application Specific Requirements}
%Applications
%  o Metro Ethernet
%    x VLANs and multiple spanning trees, LCBR
%  o Storage Area Networks
%    x in network replication
%    x Reliable link layer multicast, merging for primary and log disk
%    x fast response from logdisk (trail) can be used to infer synchronous write
%  o System Area Networks
%    x HECs can be connected using multicast groups
%    x Multicast group limit is the challenge
\Ssse{Metro Ethernet}
% Topology acquisition
\Ssse{Storage Area Networks}
% In network replication
% Building a storage area network


\Ssse{Cluster Interconnects}
% Insufficient VLANs
% Multicast groups
}

\Se{Performance Benefits}
We studied the improvement in aggregate through of a VLAN-based
multi-spanning-tree Ethernet architecture over its single spanning
tree counterpart using simulations. The simulations were carried out
to determine the maximum bandwidth that could be supported in the
network. The network topology was assumed to be a grid topology which
can represent metro Ethernets and cluster networks. The simulations were
carried out against a uniform traffic pattern of each node communicating
with other nodes with equal traffic load.
The uniform traffic distribution is a representation of cluster networks.
The simulations were run against grids of sizes 16, 25, 36,
49, and 64 nodes connected using links with a capacity of 100 Mbps. 
The traffic between nodes was 10, 8, 5, 2, and 1 Mbps for grids of sizes 16, 25, 36, 49, and 64 respectively.  
The effectiveness of path selection was compared for possible
throughput against the single spanning tree case. The path selection
was carried out for both cases, with and without backup redundancy. All
traffic comprised of at least one hop between the switches.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\figw{traffic-all}{2.2in}{ Total end-to-end traffic in network with
single spanning tree, and multiple spanning trees with and without
backup provisioning. The network follows a uniform traffic pattern while
communicating with each other.  }
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Figure~\ref{traffic-all:fig} shows the comparative maximum throughput
for single spanning tree network against the VLAN-based switching path
selection. The traffic pattern is assumed to have a uniform distribution
across all node pairs. This is a representative distribution of cluster
networks. It can be seen that the total aggregate end-to-end throughput
is always more in system. As the number of nodes increases the performance
shows considerable increase. This is because of availability of additional
number of active links in topology.

\mycomment{
Figure~\ref{traffic-real:fig} shows similar scenario with a skewed
traffic pattern.  It can be noted that, for a network of 49 nodes,
there is a performance dip compared to the 36 node network. The
reason for this can be attributed to the positioning of servers in the
network. Figure~\ref{skew-49-dip:fig} shows the traffic distribution
across different links for this network of 49 nodes. It can be seen that,
because of saturation of links in the vicinity of certain server nodes
the performance of the entire network is bottlenecked. This can be tackled
by using additional links to connect the switches facing high load.
}

\mycomment{
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\figw{traffic-real}{3.0in}{Total end-to-end traffic in network with
single spanning tree, and multiple spanning trees with and without
backup provisioning. The network follows a skewed traffic pattern while
communicating with each other. The case with 49 switches shows a dip in
performance because of saturation of links near servers.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\figw{skew-49-dip}{3.0in}{Load distribution in a 7x7 grid network. The
edges represent duplex links of 100 Mbps capacity. The links are
marked with the total provisioned bandwidth.  Note that certain links
in the vicinity of servers (marked as squares) are completely saturated.
This network can be tuned by adding new links in parallel to the existing
links.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\figw{tcp}{2.2in}{Behavior of TCP across fail-over. After fail-over,
TCP has to adapt to the existing traffic on backup links. The amount of
traffic on backup links was maintained at a sufficiently high level so
that the links are saturated after fail-over.  This was the worst case
scenario for fail-over.  It was observed that TCP takes around 300 ms
to 400 ms to recover from fail-over.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Figure~\ref{tcp:fig} shows the effect of link failure on TCP throughput.
The experiment was run with a setup where two switches were connected by
two links.  These links were then configured to belong to two different
VLANs. To have a more realistic scenario, we introduced enough background
traffic to keep the link utilization at the maximum level in the VLAN
that served the main traffic.  Upon link failures, the TCP traffic passing
through this link falls back onto the backup VLAN, which happens to pass
through the other link.  There was an expected drop of bandwidth for the
recovery period (around 600 milliseconds) Once the backup VLAN was used,
the TCP flow regained its momentum hardly suffering any more delay and
attaining stability in around 300ms to 400ms.
Thus, the {\em complete} failure recovery time can be broken down
into following components: The failure detection time, including the
event notification to status monitor, of around 400 to 600 milliseconds and
the VLAN change notification time of a few milliseconds.  The total down-time
incurred is in sub-second range.


%
%Performance
%  o Metro Ethernet
%  o viking performance
%

%Conclusion
\Se{Conclusion}
Lack of fine-grained path selection mechanism in Ethernet networks 
is a major barrier for the application of traffic engineering technology. 
The fallout of this restriction has been a limiting
factor for Ethernet deployment in the core carrier networks. Though Ethernet is becoming more and more
popular, this popularity is from access perspective and not from the core network
perspective. In this paper, we described how the programmable 
control mechanisms in modern Ethernet switches support  
MPLS-like load-balancing path selection 
to provide multi-fold network throughput gains. When combined with 
status monitoring in Ethernet, this fine-grained path selection can be used to provide
sub-second level fault tolerance, 
which is a required feature in core networks. 
We also described a simple efficient reliable multicast protocol which uses Layer-3 awareness
of commercially Ethernet 
switches to improve the performance of storage and cluster networks.
%The described switching paradigm can be realized by 
%exploiting the programmable features of commodity
%Ethernet switches making it readily deployable.
We believe there are many more high-level functionalities 
that can be composed from the basic programmable control mechanisms.
%This  is one direction along which we plan to take for this project.  
One of the future directions for this work is to explore and build
interesting high-level functionalities that can enhance large scale
networks as a whole.
%{\small
\bibliography{switching}
\bibliographystyle{IEEE}
%}

\end{document}


switching.bbl
\begin{thebibliography}{10}

\bibitem{8023ah}
IEEE,
\newblock ``{IEEE Standard for Local and Metropolitan Area Networks: Ethernet
  in the First Mile},'' Institute of Electrical and Electronics Engineers,
  2004.

\bibitem{myrinet}
Nanette~J. Boden, Danny Cohen, Robert~E. Felderman, Alan~E. Kulawik, Charles~L.
  Seitz, Jakov~N. Seizovic, and Wen-King Su,
\newblock ``{Myrinet: A Gigabit-per-Second Local Area Network},''
\newblock {\em IEEE Micro}, vol. 15, no. 1, pp. 29--36, 1995.

\bibitem{quadrics}
F.~Petrini, W.~Feng, A.~Hoisie, S.~Coll, and E.~Frachtenberg,
\newblock ``{The Quadrics NetworkL High-Performance Clustering Technology},''
\newblock {\em IEEE Micro}, vol. 22, no. 1, pp. 46--57, 2002.

\bibitem{infiniband}
``{Infiniband Specification},'' Infiniband Trade Association, Jun 2001.

\bibitem{8021d}
IEEE,
\newblock ``{IEEE Standard for Local and Metropolitan Area Networks: Media
  Access Control (MAC) Bridges},'' Institute of Electrical and Electronics
  Engineers, 1990.

\bibitem{8021w}
IEEE,
\newblock ``{IEEE Standard for Local and Metropolitan Area Networks: Rapid
  Configuration of Spanning Tree},'' Institute of Electrical and Electronics
  Engineers, 2000.

\bibitem{mpls}
E.~Rosen, A.~Viswanathan, and R.~Callon,
\newblock ``{Multiprotocol Label Switching Architecture},'' IETF RFC 3031, Jan
  2001.

\bibitem{te-qos}
G.~Ash,
\newblock ``{Traffic Engineering \& QoS Methods for IP-, ATM-, \& TDM-Based
  Multiservice Networks},'' Internet Draft, Oct 2001.

\bibitem{8021p}
IEEE,
\newblock ``{IEEE Standard for Local and Metropolitan Area Networks: Supplement
  to Media Access Control (MAC) Bridges: Traffic Class Expediting and Multicast
  Filtering},'' Institute of Electrical and Electronics Engineers, 1998.

\bibitem{8021q}
IEEE,
\newblock ``{IEEE Standard for Local and Metropolitan Area Networks: Virtual
  Bridged Local Area Networks},'' Institute of Electrical and Electronics
  Engineers, 1998.

\bibitem{8021s}
IEEE,
\newblock ``{IEEE Standard for Local and Metropolitan Area Networks: Multiple
  Spanning Trees},'' Institute of Electrical and Electronics Engineers, 2002.

\bibitem{igmpsnoop}
``{Understanding IGMP Snooping},'' Dell PowerConnect Application Note~18.

\bibitem{gopalan03efficient}
K.~Gopalan,
\newblock ``Efficient network resource allocation with {QoS} guarantees,''
  Technical Report TR-133, Experimental Computer Systems Labs, Department of
  Computer Science, State University of New York at Stony Brook, March 2003.

\bibitem{viking}
Srikant Sharma, Kartik Gopalan, Susanta Nanda, and Tzi cker Chiueh,
\newblock ``{Viking: A Multi-Spanning-Tree Ethernet Architecture for
  Metropolitan Area and Cluster Networks},''
\newblock in {\em Proceedings of the IEEE INFOCOM`04}, Mar 2004.

\bibitem{igmp}
W.~Fenner,
\newblock ``{Internet Group Management Protocol, Version 2},'' IETF RFC 2236,
  Nov 1997.

\bibitem{hose}
N.~G. Duffield, Pawan Goyal, Albert Greenberg, Partho Mishra, K.~K.
  Ramakrishnan, and Jacobus~E. van~der Merive,
\newblock ``A flexible model for resource management in virtual private
  networks,''
\newblock in {\em ACM SIGCOMM}, 1999, vol.~32 of {\em 3}, pp. 33--46.

\bibitem{diffserv}
S.~Blake, D.~Black, M.~Carlson, E.~Davies, Z.~Wang, and W.~Weiss,
\newblock ``{An Architecture for Differentiated Service},'' IETF RFC 2475,
  December 1998.

\end{thebibliography}
