\documentstyle[12pt,epsf,fleqn]{article}
   
\topmargin=0.15in
\textheight=8.35in
\headsep=0.25in
\topskip=0pt
\oddsidemargin=0.3in
\textwidth=6.0in
\parskip=0pt
\parsep=0pt
\columnsep=2em
\parindent=1.5em

\newcommand{\eS}{\emptyset}
\newcommand{\ovl}{\overline}
\newcommand{\hsp}{\hspace*}
\newcommand{\vsp}{\vspace*}
\newcommand{\lam}{\lambda}
\newcommand{\ct}{\cite}
\newcommand{\mc}{\multicolumn}
\newcommand{\noi}{\noindent}

\topsep=1.25ex

\begin{document}
\baselineskip 4ex

\begin{center}
{\Large \bf A Low-cost Algorithm for Dynamic Multicast Routing} 
\vsp{2ex}

Pingyan Tan \\
Frederick C. Harris, Jr.\\
\vsp{1ex}

Department of Computer Sciences\\
UNIVERSITY OF NEVADA, RENO\\
\end{center}
\vsp{2ex}

\begin{center}
{\large \bf Abstract}
\end{center}

\begin{list}{}{
              \setlength{\leftmargin}{1.5em} 
              \setlength{\rightmargin}{1.5em}
              \setlength{\itemsep}{0pt}
              \setlength{\parsep}{0pt}
              \setlength{\topsep}{0pt}
              \setlength{\labelsep}{1em}
              }
\item[] 
This paper presents a low-cost algorithm for multicast routing in computer 
networks. For performance evaluation, it is compared a different algorithm 
known as link-state multicast routing which is a low-delay algorithm, and 
is used by the Internet MOSPF procotol\cite{HUITEMA}.
Our algorithm supports group addressing by the notions of distance 
radius and the minimum average distance. Another important feature 
of this algorithm is that no delivery tree has to be maintained, 
which eliminates the problem of memory and CPU congestion. Moreover, 
its computation time complexity is only linear in the group size. 
Simulation study shows that this algorithm can lower delay by as mush 
as 40 percent for the same offered load, compared with the low-delay 
algorithm.
\end{list}

\section{Introduction}
Multicast routing has been widely used in those networks that
support it in the recent years. In many cases an application must 
send the same information to more than one destination, such as in
distributed computations, distributed databases, and in computer 
mediated conferences.
   
Multicast routing can be defined as follows: Given a network $(N,L)$, 
where $N$ is a set of nodes and $L$ a set of links, a source node 
$s\in N$, and a set of destination nodes $D{\subseteq} N$; if 
$1<|D|<|N|-1$, then the problem is a multicast problem. (If $|D|=1$, 
it is a unicast problem and if $|D| = |N|-1$, it is a broadcast problem.)

The subset $D$ is called a {\em group}. A multicast group is
a  set of destination nodes to which a message is delived. Each 
destination node is a member of the group. For each source, there 
can be many different destination groups. Multicasting should be 
more efficient than unicasting separate copies to each destination, 
because it should reduce the transmission overhead.

Modern networks also require the {\em unknown-destination}
delivery function for routing. If a set of destinations can be
identified by a single group address, such a group address can
be used to reach one or more destinations whose individual
addresses are unknown to the sender, or whose address may
change over time. This is the implication of group addressing.
 
Algorithms for solving the multicast routing problem can be
divided into two categories: low-delay algorithms and low-cost
algorithms. Low-delay routing algorithms minimize the path
length from the source to every destination node. This usually
requires that the message be sent to every destination along
the shortest path. Low-cost routing algorithms minimize the
total traffic. The total traffic is equivalent to the total
length of the path in a delivery tree. Finding a minimum cost
routing tree is a Steiner Tree Problem in a graph, which is
known to be NP-complete\cite{HWANG}. Many traditional heuristics 
for Steiner Tree problem\cite{HWANG} are not suitble for 
multicasting when the network is large.

A number of algorithms have been proposed for multicast routing 
problems. The earlier algorithms\cite{AGUILAR,BHARATH} do not 
support group addressing. The optimal multicast routing 
algorithms\cite{STASSINOPOULOS,STASSINOPOULOSa} are too costly 
to be practical. The algorithms described in \cite{DEERING,HUITEMA}
are mainly low-delay algorithms. The low-cost algorithm\cite{BELKEIR}
that incrementally updates a delivery tree will lose incentives
when group changes are frequent and when the number of source/group 
pairs is large, for it requires information be kept at each node
for each such pair.

In this paper, we present a low-cost multicast algorithm that requires
a packet to carry only one short field in addition to the group address.
It is computational efficient and effective in reducing the cost.
In the following, the algorithm is described formally, followed 
by a simple example for explaning the algorithm.
Then a simulation model is implemented and results are given. 

\section{Description of the Algorithm}

In an internetwork environment, it is assumed that subnetworks have 
the ability for multicast routing. In our model, each router and its 
attached subnetwork are treated as a node. We omit the details 
within subnetworks and abstract the network into a set of nodes
connected by links. It is also assumed that each node maintains 
a routing table for the whole network. Each node can determine 
the complete network topology and can independently compute the 
shortest path from itself to every possible destination. Each 
node also maintains the group-member information which ensures 
that every node knows the membership of every group. When a packet 
arrives at a node, the node can decide whether there is any member 
in its site. 

Our algorithm is aimed at low-cost routing, and supports {\em group} 
addressing. The simulation results strongly show that the new algorithm 
has a better performance than a compared, low-delay algorithm, in both 
cost and delay.
    
To describe the algorithm, we first define the following variables:
\begin{list}{}{
              \setlength{\leftmargin}{4em} 
              \setlength{\itemsep}{0pt}
              %\setlength{\partopsep}{0pt}
              \setlength{\parsep}{0pt}
              \setlength{\topsep}{1ex}
              %\setlength{\labelsep}{1em}
              \renewcommand{\makelabel}[1]{#1{\hfill}}
              }
\item[{$G$}]    The destination set, that is, a group.
\item[{$G_i$}]  Node $i$'s responsible destination set. It is the subset
                of $G$ to which node $i$ is responsible for delivering the 
                message.
\item[$N_i$]    Node $i$'s open neighborhood set, i.e., all of node $i$'s 
                neighbor nodes except for node $i$ itself. 
\item[$D_j$]    Neighbor $j$'s responsible destination set. 
\item[$L_j$]    Average distance from neighbor node $j$ to $j$'s responsible 
                destination set.
\item[$A_i$]    The assigned neighbor set, i.e., the subset of $G_i$ that
                has been assigned to a link.
\item[$d_{ij}$] The shortest path distance from node $i$ to node $j$.
\end{list}

In addition to the routing table of its own, each node also keeps
the routing table of its neighbors', which is the common practice 
in the distributed Bellman-Ford algorithms\cite{BERTSEKAS}. As usual, 
the routing table at each node is assumed to contain following entries
that are related to our work:
%
\begin{center}
\begin{tabular}{|l|l|l|} \hline
destination & shortest distance & next hop \\ \hline
\end{tabular}
\end{center}
%
where ``next hop'' tells which link to take to reach the 
destination on the shortest path from the current node. 
We do not use the tabled next hop directly, but compute the next
hop based on our algorithm. In the algorithm, each packet $p$ is 
required to carry a small integer $p$.radius that is used in c
onjunction with the next-hop entries to compute the routing path. 

Suppose packet $p$ arrives at node $i$ via a neighbor node $k$ of
$i$'s, or is generated at node $i$, following is the description of 
the algorithm: 
\newcounter{xdb}
\begin{list}{\arabic{xdb}.}
            {\usecounter{xdb}
              \setlength{\leftmargin}{3.25em} 
              %\setlength{\partopsep}{0pt}
              \setlength{\parsep}{0pt}
              \setlength{\topsep}{1ex}
              \setlength{\itemsep}{0.0ex}
              \setlength{\labelsep}{1em}
            }
\item If $i$ is the source node then \\
      \hsp{\mathindent}$R = \infty$;\hsp{1em} $A_i = \emptyset$;\\
      else \\
      \hsp{\mathindent}$R = p$.radius;\hsp{1em} $A_i$ = $\{k\}$;\\
      If $R=0$, \  stop. 
\item Compute node $i$'s responsible set
  \[ G_i = \{g\,|\,g\in G,\  d_{ig} \leq R,\ {\rm and}\ g\neq i\} \]
\item For each $j\in N_i$ and $j\not\in A_i$, compute $j$'s destination set
  \[ D_j = \{g | g \in G_i,\ {\rm and}\  d_{jg} < d_{ig} \} \]
  and the average length
  \[ L_j = (d_{ij} + \sum_{g \in D_j} d_{jg} - \hat{L}_j ) /|D_j| \]
  where $\hat{L}_j$ is the sum of the overlapped next-hop link, defined as
  \[ \hat{L}_j = \sum_{n_{jk} > 1} (n_{jk}-1) l_{jk}\] 
  where $n_{jk}$ is the number of members in $D_j$ that will be sent via 
  link $k$ from node $j$, and $l_{jk}$ is the length of the link. 

  If (all $D_j = \emptyset$) or ($N_i = A_i$), \ stop.
\item  Let $J$ be the subscript such that 
   \[L_J=\min_{j\in N_i, j\not\in A_i} L_j\]
 and define
   \begin{equation}
      R_J = \max_{g\in D_J} d_{Jg}         \label{eqRJ}
   \end{equation}
 send a packet with radius $R_J$ to node $J$.
\item  $G_i = G_i - D_J \hsp{\mathindent}  A_i = A_i \cup \{J\}$ 
  if $G_i = \emptyset$\\
  \hsp{\mathindent} stop \\
  else\\
  \hsp{\mathindent} go to step 3.  \hfill $\clubsuit$
\end{list}

The algorithm will terminate at a node in three cases: 
\newcounter{hlb}
\begin{list}{\arabic{hlb})}
            {\usecounter{hlb}
              \setlength{\leftmargin}{6em} 
              \setlength{\rightmargin}{0em}
              %\setlength{\partopsep}{0pt}
              \setlength{\parsep}{0pt}
              \setlength{\topsep}{1ex}
              \setlength{\itemsep}{0ex}
              \setlength{\labelsep}{1em}
            }
 \item if all $D_j = \emptyset$ 
 \item if $N_i = A_i$ 
 \item if $G_i = \emptyset$
\end{list}

If none of the above condition are satisfied, it will
go back to step 3 to process other neighbor nodes until
one of the three conditions is satisfied.

Each node executes the same algorithm as its ancestors
whenever a packet arrives. The whole algorithm
execution will finally stop when the radius for every
packet becomes zero.

\subsection{An Example}

We use the network shown in Figure \ref{example1} to illustrate 
our algorithm. The result shows that the cost generated by our 
algorithm is 11; but with shortest path algorithm, the total 
cost is 13.
%
\begin{figure}[htbp]
\epsfxsize=18em
\centerline{\epsffile{example.ps}}
\caption{Example Network} \label{example1} 
\end{figure}
%

Assume that the source node is $S$, and the destination set 
$G = \{E, F, M \}$.

{\baselineskip 3ex
{\small
\begin{tabbing}
\hsp{1.5em}\={\bf At node $S$}\\ 
\hsp{1.5em}\>\hsp{1.5em}\=\hsp{2em}\=\hsp{1.5em}\=\hsp{2em}\=\hsp{2em}\=
\hsp{2em}\=\hsp{2em}\=\\
\>1)\>The packet is generated at $S$, $R=\infty$, $A_S = \emptyset$ \\
\>2)\>$G_S = \{E,F,M\}$ \\
\>3)\>$N_S = \{H,C,B,M\}$,  $A_S = \emptyset$ \\
\>  \>$D_H = \{E\}$    \>\>\>\> $L_H = 3 + 2 =5$ \\
\>  \>$D_C = \{E,F\}$  \>\>\>\> $L_C = (3 + 4 + 2)/2 = 4.5$ \\
\>  \>$D_B = \{F,M\}$  \>\>\>\> $L_B = (2+2+3)/2=3.5$ \\
\>  \>$D_M = \{M,F\}$  \>\>\>\> $L_M=(4+0+2)/2=3$ \\
\>4)\>$J=M$, $R_J=2$  \\
\>  \>---{\bf send packet $p$ to $M$ with $p.{\rm radius}=2$} \\
\>5)\>$G_S=\{E\}$, $A_S = \{M\}$ --- go to step 3 \\
\>  \> \>3)\> $N_S - A_S = \{H, C, B\}$ \\
\>  \> \>\> $D_H=\{E\}$ \>\>\>$L_H=5$ \\
\>  \> \>\> $D_C=\{E\}$ \>\>\>$L_C=7$ \\
\>  \> \>\> $D_B=\emptyset$ \>\>\>$L_B = \infty$ \\
\>  \> \>4)\> $J=H$, $R_J=2$ \\
\>  \> \>\>---{\bf send packet $p$ to $H$ with $p.{\rm radius}=2$}\\
\>  \> \>5)\> $G_S = \emptyset$ --- stop
\end{tabbing}
}
{\small
\begin{tabbing}
\hsp{1.5em}\={\bf At node $M$} \\ 
\hsp{1.5em}\>\hsp{1.5em}\=\hsp{2em}\=\hsp{1.5em}\=\hsp{2em}\=\hsp{2em}\=
\hsp{2em}\=\hsp{2em}\=\\
\>1)\>$G=\{E,F,M\}$,  $R=2$,  $A_M=\{S\}$ \\
\>2)\>$G_M=\{M,F\}$ \\
\>3)\>$N_M=\{B,S,F\}$, $A_M=\{S\}$, $N_M-A_M=\{B,F\}$ \\
\>  \>$D_H = \{E\}$    \>\>\>\> $L_H = 3 + 2 =5$ \\
\>  \>$D_B=\emptyset$  \>\>\>\> $L_B=\infty$ \\
\>  \>$D_F=\{F\}$      \>\>\>\> $L_F=2/1=2$ \\
\>4)\>$J=F$,  $R_J=0$ \\
\>  \>---{\bf send packet $p$ to $F$ with $p.{\rm radius}=0$} \\
\>5)\>$G_M=\{M\}$, $A_M=\{S,F\}$ ---  go to step 3 \\
\>  \> \>3)\>$N_M-A_M=\{B\}$ \\
\>  \> \>  \>$D_B=\emptyset$ ---  stop.
\end{tabbing}
}
{\small
\begin{tabbing}
\hsp{1.5em}\={\bf At node $H$} \\ 
\hsp{1.5em}\>\hsp{1.5em}\=\hsp{2em}\=\hsp{1.5em}\=\hsp{2em}\=\hsp{2em}\=
\hsp{2em}\=\hsp{2em}\=\\
\> 1)\>$G=\{E,F,M\}$, $R=2$,  $A_H=\{S\}$ \\
\> 2)\>$G_H=\{E\}$ \\
\> 3)\>$N_H=\{E,S\}$, $N_H-A_H=\{E\}$ \\
\>   \>$D_E=\{E\}$ \>\>\>\>$L_E=2$ \\
\> 4)\>$J=E$, $R_J=0$ \\
\>   \>---{\bf send packet $p$ to E with $p.{\rm radius}=0$} \\
\> 5)\>$G_H=\emptyset$ --- stop
\end{tabbing}
}
} %baselineskip

\noindent 
In the end, all packets at all involved nodes have
$R=0$; the entire algorithm execution is terminated.    
        
\section{Simulation Sduties}
Simulation studies are performed on this and a compared algorithm. The 
compared algorithm is the Link State multicast algorithm descriped in 
\cite{DEERING}, which is a low-delay algorithm. This algorithm is chosen 
because it assumes roughly the same network information as does our 
algorithm, and because it is the multicast version of the Intenet standard
protocol OSPF and is used in the experimental MOSPF protocol\cite{HUITEMA}.
Also to compare with a low-delay algorithm, we will be able to study
the impact on delay by traffic reductions.

\subsection{Performance Measurements}
The simulation study will measure two different relationships: 
one is delay versus offered load, the other is utilization versus 
offered load.  Delay is defined to be the interval between the 
time a packet is generated and the time the packet arrives at
the destination. In a multicast environment, the delay is the 
average delay for all destinations. Offered load is defined to 
be the offered rate of packet generation. Utilization is defined 
to be the average utilization of all links. 

\subsection{Simlulation Model and Network Parameters}
Queueing model is used for the simulation study, where the link 
from node $i$ to node $j$ is modeled as a queue. Unicast packets
and multicast packets with random destinations are generaged at 
each node by exponentially distributed intervals. Groups of random 
sizes appear and disappear also by exponentially distributed 
intervals. The group population is maitained in a stable level
by equal birth and death rates.

The parameters of interest in our algorithm are defined in 
Table~\ref{netpara}. Note that the {\em ms} in the table should 
be interpreted as a relative time unit. The initial group population 
is also the average number of active groups, with the group birth
and death rates being equal.

\begin{table}[htbp]
\begin{center}
\begin{tabular}{ll}
$t_b$ & transmission rate, bits/{\em ms} \\
$t_p$ & packet transmission time,  {\em ms}\\
$\lambda_u$ & unicast packet arrival rate, packet/{\em ms}/node \\ 
$\lambda_m$ & multicast packet arrival rate, packet/{\em ms}/node  \\ 
$\lambda_g$ & birth and death rate of groups, group/{\em ms} \\
$G$         & initial group population \\
$G_{\max}$  & maximum size of a group \\
$G_{\min}$  & minimum size of a group \\
\end{tabular}
\end{center}
\caption{Network Parameters}  \label{netpara}
\end{table}
        

\subsection {The Compared Algorithm}
The Link State multicast algorithm needs to maintain a delivery 
tree for each active source/group pair. For simplicity, we omit 
the detail of a subnetwork, and treat each router as a node. A 
simplified version of the LS multicast algorithm is given in 
Figure~\ref{compalg}. 
%
\begin{figure}[htbp]
\begin{center}
\begin{tabular}{ll} 
1.& On link-state update reporting change of $g$ \\
  &\hsp{2em}for each cache record $c$ with $c$.grp = $g$ \\
  &\hsp{4em}    discard $c$ \\
2.&On receipt of multicast packet from \\
  &source $s$ to group $g$ via node $k$ \\
  &\hsp{2em}if no cache record $c$ such that\\
  &\hsp{2em}$c$.src = $s$ and $c$.grp = $g$ \\
  & \hsp{4em} create $c$; $c$.src = $s$; $c$.grp = $g$ \\
  & \hsp{4em} compute $c$.parent and $c$.child \\
  & \hsp{2em} if $c$.parent = $k$ \\
  & \hsp{4em} for each child node $j$ \\
  & \hsp{6em} send copy of packet to node $j$ 
\end{tabular}
\end{center}
\caption{{\em Tree} Algorithm}  \label{compalg}
\end{figure}
%
This algorithm will be referred to as {\em Tree} algorithm. 
In the algorithm, a cache record $c$ is created for
each active source/group pair to maintain the delivery tree.
A cache record at a node has the fields $c$.src, $c$.grp, $c$.parent,
and $c$.child to keep the source, the group, the parent and the children
nodes in the delivery tree for that source/group pair. Whenever a group 
$g$ appears or dispears on a node $k$, node $k$ will flood link-state 
update to report this change.

\subsection {Simulation Results}
We randomly generated four networks with 40, 75, 97, and 123 nodes 
respectively. In each network, the group population fluctuates along an
average, by a birth/death process, and the group size fluctuates on a 
random number uniformly distributed in a certain range. In the 
simulation, the multicast packet generation rate $\lambda_m$ is 
set to be the same as the unicast rate $\lambda_u$. These rates are
changing for different passes of simulation. The rates are assigned 
the values with which no severe congestion is observed and reasonable 
utilizations are obtained. Table~\ref{paravalue} gives the ranges for
the values of other parameters for the four networks (refer to 
Table~\ref{netpara}.)
%
\begin{table}[htbp]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
\hline
net-&$G$&$G_{\min}$&$G_{\max}$&av. \#&hit  &$\lambda_g$&$t_p$&link \\ 
work&   &        &        &links &ratio&            &     & len \\ \hline
40  & 3 & 2      & 39     & 2.95 & 91\%    & $1/1K$ &0.1 & 1  \\ 
75  & 5 & 2      & 37     & 2.59 & 91\%    & $1/1K$ &0.1 & 1  \\ 
97  & 4 & 2      & 48     & 3.22 & 92\%    & $1/1K$ &0.1 & 1  \\
123 & 3 & 2      & 40     & 3.25 & 86-95\% & $1/1K$ &0.1 & 1  \\
\hline
\end{tabular}
\end{center}
\caption{Parameter values}           \label{paravalue}
\end{table}
%   
In the table, the value $1/1K$ for $\lambda_g$ means that
the group birth and death rate is $1/1024$ of the unicast 
packet generation rate.

The hit ratio is the ratio for not reconstructing the
delivery tree for LS multicast algorithm. This is not a
free variable, rather it is the function of other
parameters.  We choose the parameters so that the ratio
is approximately slightly over 90\%, which should be a
reasonable assumption. This ratio can be decreased by
increasing group appearance/disappearance or group
membership change frequency, or by increasing group
size or the number of groups.

We execute both our algorithm and the {\em Tree} algorithm
with exactly the same network parameters.

We assume that the time for the reconstruction of the
delivery tree for the Tree algorithm is $(E+N)\log N$
units\cite{SEDGEWICK}, where $N$ is the number of
nodes, and $E$ is the total number of links in the
network. This is equivalent to transmitting $((E+N)\log N)/L$ 
packets from one node, where $L$ is the packet
length (in bits). We also assume that the time for
selecting the next hop for our algorithm is
$G_s\times N_l$ units for each node, where $G_s$ is the
destination group size and $N_l$ is the number of links
at that node. This time is equivalent to transmitting
$G_s\times N_l/L$ packets.

The first 3,000 packets received at each node (on average) 
are discarded to ensure that the network reaches a steady 
state; then statistics are collected for the subsequent 
10,000 packets received at each node (on average).

The simulation results are shown in Figures \ref{xdelaylow} to 
\ref{xreduce}. In these figures, the curves labeled `Radius'
is for our algorithm, those with `Tree' are for the compared
algorithm. In Figures \ref{xdelaylow} to \ref{xload40}, the
horizontal axes represent the message rate which is the
offered load. The vertical axes represent the delay
(Figures \ref{xdelaylow}, \ref{xdelayhigh}, \ref{xdelay40} and
utilization (Figures \ref{xload}, xload40). Figure~\ref{xreduce}
shows the average delay and utilization reductions by algorithm
{\em Radius} over algorithm {\em Tree}. The reductions are calculated
by the following fomula:
\[ 
A=\frac{\sum_{i=1}^4\frac{T_i-R_i}{T_i}}{4}\times 100\% 
\]
where
%
\begin{list}{}{
              \setlength{\leftmargin}{3.5em} 
              \setlength{\itemsep}{0pt}
              %\setlength{\partopsep}{0pt}
              \setlength{\parsep}{0pt}
              \setlength{\topsep}{1ex}
              \setlength{\labelsep}{1em}
            }
\item[$A$]   average percentage delay or utilization reduction.
\item[$T_i$] {\em Tree} delay or utilization for the $i$th network.
\item[$R_i$] {\em Radius} delay or utilization for the $i$th network.
\end{list}

\noi
The delays and utilizations for the smaller network of 40 nodes are
based on a different range of message rates (100 to 800) from 
that used in the three larger networks (50 to 400), because the 
smaller network can tolerate higher message rates for both algorithms. 
To calculate the average, the message rates are normalized with
the highest rate used in each network.

The simulation results show that our algorithm has a better 
performance than the compared algorithm since both the delay 
and the utilization are lower on the four networks---For the
same offered load, both the delays and network traffic are 
lower. At certain crucial message rates, the delay can be 
lowered by 40 percent. The delay reduction at these rates 
means our algorithm can support higher offered load than can 
the compared algorithm.
                                 
When the message rate increases, the corresponding utilization 
of links increases, as seen in Figures~\ref{xload} and \ref{xload40}. 
Utilization reflects the traffic load. The increased traffic causes 
packets to be queued for the available links. In the case when the 
queuing delay plays the major role, our algorithm shows more 
advantages, since it is a low-cost algorithm.  Reduced total 
cost will decrease the waiting time for queued packets. Therefore, 
the total delay is eventually decreased. 

\subsection {Conclusions}
It is known that low-cost algorithm can reduce traffic and delay.
This study shows that with our simple algorithm that requires only
a linear time complexity, the delay can be substantially lower than 
that offered by always taking the shortest path, and yet this algorithm
has all the elements that are required for multicasting, such as
efficient computation, group addressing, and compatibility with
unicasting. The radius concept and the minimum average distance method
are effective in resolving group addressing and provide a practical
low-cost algorithm for multicasting in internetworks.

\begin{figure}[htbp]
\vsp{-2ex}
\epsfxsize=18em
\centerline{\epsffile{xdelaylow.ps}}
\vsp{-4ex}
\caption{Delays (lower message rates)} \label{xdelaylow} 
\end{figure}

\begin{figure}[htbp]
\vsp{-2ex}
\epsfxsize=18em
\centerline{\epsffile{xdelayhigh.ps}}
\vsp{-4ex}
\caption{Delays (higher message rates)} \label{xdelayhigh} 
\end{figure}
 
\begin{figure}[htbp]
\vsp{-2ex}
\epsfxsize=18em
\centerline{\epsffile{xdelay40.ps}}
\vsp{-4ex}
\caption{Delays for $N=40$} \label{xdelay40} 
\end{figure}

\begin{figure}[htbp]
\vsp{-2ex}
\epsfxsize=18em
\centerline{\epsffile{xload.ps}}
\vsp{-4ex}
\caption{Utilizations} \label{xload} 
\end{figure}

\begin{figure}[htbp]
\vsp{-2ex}
\epsfxsize=18em
\centerline{\epsffile{xload40.ps}}
\vsp{-4ex}
\caption{Utilizations for $N=40$} \label{xload40} 
\end{figure}
 
\begin{figure}[htbp]
\vsp{-2ex}
\epsfxsize=18em
\centerline{\epsffile{xreduce.ps}}
\vsp{-4ex}
\caption{Reductions} \label{xreduce} 
\end{figure}

\newpage
\baselineskip 13pt
\bibliographystyle{ieee}
\bibliography{bib}
\end{document}
