%\documentstyle[twoside,twocolumn,12pt,infocom,sober]{article}
\documentstyle[twocolumn,sober]{article}
% TODO get the graphs in the right places 
% TODO get the page number up or delete it (DELETE?) infocom.sty can have 
% foot* changed to zero too
% TODO get the page sizes correct for infocom
% don't use one line of a page!
% copies to gill@essex.ac.uk? fingerhut, zwang@cs.ucl.ac.uk, nhl@cl

\newcommand{\x}{\!\times\!}
%\renewcommand{\topfraction}{1}
%\renewcommand{\bottomfraction}{1}
%\renewcommand{\textfraction}{0}
%\renewcommand{\floatpagefraction}{0}

%\dbltopnumber{2}
%\dbltotalnumber{2}
%\parskip 1ex

\pagestyle{empty}
% stuff from infocom organisers
\setlength{\textheight}{8.75in}
\setlength{\columnsep}{2.0pc}
\setlength{\textwidth}{6.8in}
\setlength{\footheight}{0.0in}
\setlength{\topmargin}{0.25in}
\setlength{\headheight}{0.0in}
\setlength{\headsep}{0.0in}
\setlength{\oddsidemargin}{-.19in}
\setlength{\parindent}{1pc}

\makeatletter
\def\@normalsize{\@setsize\normalsize{12pt}\xpt\@xpt
\abovedisplayskip 10pt plus2pt minus5pt\belowdisplayskip \abovedisplayskip
\abovedisplayshortskip \z@ plus3pt\belowdisplayshortskip 6pt plus3pt
minus3pt\let\@listi\@listI} 

%need an 11 pt font size for subsection and abstract headings
\def\subsize{\@setsize\subsize{12pt}\xipt\@xipt}

%make section titles bold and 12 point, 2 blank lines before, 1 after
\def\section{\@startsection {section}{1}{\z@}{24pt plus 2pt minus 2pt}
{12pt plus 2pt minus 2pt}{\large\bf}}

%make subsection titles bold and 11 point, 1 blank line before, 1 after
\def\subsection{\@startsection {subsection}{2}{\z@}{12pt plus 2pt minus 2pt}
{12pt plus 2pt minus 2pt}{\subsize\bf}}
\makeatother


\input{psfig}


\begin{document}
%\centerline{Submission for Infocom 1993}
%\vspace{5 mm}
%\centerline{Area of interest : Routing and Flow Control}
%\vspace{1.0cm}
 
\title{\Large\bf How Bad is Na\"{\i}ve Multicast Routing?} 
\author{
%\begin{tabular}[t]{c@{\extracolsep{8em}}c}
Matthew Doar and Ian Leslie \\
%\\
%\thanks{
University of Cambridge Computer Laboratory, \\
New Museums Site, 
Pembroke Street, 
Cambridge 
CB2 3QG. 
U.K. 
%Tel: +44 223 334600, 
%Fax: +44 223 334678,
%Telex: via 81240 CAMSPL G.
%} \\
%{\footnotesize (jmsd,iml) @cl.cam.ac.uk} \\
%{\it University of Cambridge Computer Laboratory, England}
%\end{tabular}
}
\date{}
\maketitle
%\vspace{8mm}
\thispagestyle{empty}
       
%\centerline{\it ABSTRACT}
\subsection*{\centering ABSTRACT}
%\begin{quotation}
{\em 
When the problem of routing multicast connections in networks has been
previously considered, the aim has been to minimise overall costs,
possibly subject to a delay constraint.  The emphasis has been on
examining the problem with a source transmitting to a fixed set of
destinations (the multicast group) which are known when communication
is established.  There are clearly some applications for which  the set of
destinations will be dynamic, with destinations joining and leaving
the multicast group during the communication.  Under these conditions
the computation of an ``optimal'' spanning tree for each new multicast
group may not be the best way to proceed.  An alternative is to make
modest alterations to an existing spanning tree to derive a new one.
An extreme variation of this is to use minimal cost source to destination
routing for each destination, effectively ignoring the existing multicast 
tree.
This na\"{\i}ve approach leads to a simple implementation but
clearly produces non-optimal spanning trees.
In this paper we examine just how non-optimal these trees are in random 
general topology networks and conclude
that they are worse by only a small factor. 
The factor is reduced still further if a hierarchy is imposed upon the random
network to give a more realistic model.
%This leads us to hope that other
%routing algorithms exist which are more suitable for  real applications with dynamic multicast groups.
%%\end{quotation}
}

%Keywords: Multicast, Routing.

%double spaced lines
%\baselineskip=24pt

\section{Introduction}
%---------------------
\label{Introduction}

%\setcounter{footnote}{0}
Multicast, which here we consider in the limited 
sense\footnote{There are of course many-to-one (`concast') and 
many-to-many forms of multicast as well.}  as
the connection of multiple destinations, the multicast group,
 to a single source, is likely to
become increasingly important as networks are used to carry continuous media
traffic such as voice and video to the end user and potential bandwidth reductions become more significant.
One of the more difficult aspects of providing multicast is deciding how the
connections should be routed within a network to minimise or meet constraints
for a series of
parameters including delay, jitter and the link capacity used. 
Any scheme which is chosen must also be able to cope with heterogeneous 
networks~\cite{Infocom91.11B.1}, where some nodes provide 
multicast capability and others do not. 
This situation is likely to arise in the wide area 
for economic reasons but should be less of a concern
 in the local area. Another problem is that a route
 may  only have a limited degree of replication 
available at an intermediate node~\cite{Infocom92.9A.2}. 

Multicast groups may be either dynamic or static in nature.
A static group, once set up, remains
unmodified until it is discarded. 
A connection to a static group tends to be
set up following a request from the source, for instance, file replication across
a network.
Unlike a static group, the membership of a dynamic group can vary with time.
The state of the dynamic group tends to be driven by destinations,
either destinations which are already part of the connection and
wish to leave, 
or destinations which are outside the connection and wish to join it. 
The modifications are usually made by the source following a request from a destination.
An example of an application which has dynamic groups
is entertainment video distribution.

The problem of connecting a subset of nodes, $\cal S$, in an undirected 
graph $\cal G$, using the minimal cost subgraph such that there is a path
between each pair of nodes in $\cal G$,
 is known as the Minimum Steiner Tree (MST) problem. The MST problem 
  is one of the classic
NP-complete problems of graph theory~\cite{Gilbert,Karp}. 
The nodes which are not in $\cal S$ but which are used in the
subgraph to connect the chosen nodes are known as {\em Steiner nodes}.
The construction of a Steiner tree for multicast routing is one extreme form
of multicast routing, as shown in Figure~\ref{fig:routing-categories}.

\begin{figure*}[tbh]
\begin{center}
\mbox{\psfig{figure=categories.ps}}
\caption{Multicast Routing Categories}
\label{fig:routing-categories}
\end{center}
\end{figure*}

Previous work on heuristic solutions (summarised by Winter~\cite{Winter}) of
the MST problem has generally taken one of the two following
approaches.  In the first approach, likely Steiner nodes are selected and
then a minimum spanning tree of these nodes, together with the nodes
in $\cal S$, is constructed~\cite{RS}.  In the second approach,
a minimum spanning tree of the whole graph
is pruned to remove superfluous nodes and then perturbed to try to
include more Steiner nodes, which 
may reduce the overall cost of the spanning tree~\cite{Wall}.  It is one of the original
versions of the latter approach by Kou, Markowsky and Berman~\cite{KMB}, referred to hereafter as KMB, which has been chosen as the basis of comparison with the
simple algorithm detailed below. 

The KMB algorithm is described in further  elsewhere~\cite{Wall} but  briefly, consists of five
steps. An all-pairs, shortest path graph of  $\cal S$ is
constructed and a minimum spanning tree of this graph is found. This tree
is used 
as a template to add the relevant shortest paths in $\cal G$, possibly introducing new
nodes. A minimum spanning tree of this new subgraph is then constructed. 
Finally,  this
new graph is pruned until all the leaves of the tree are destinations.


The performance of heuristic solutions can be described by two properties,
their computational complexity and their {\em inefficiency}.  By inefficiency
we mean the ratio of the cost of the resulting spanning tree  to the cost
of the minimal Steiner tree.

The worst case computational complexity of the KMB algorithm is 
$O({\vert}{\cal S}{\vert}{\vert}{{\cal G}{\vert}}^{2})$ 
and it has a
worst case inefficiency which is bounded by 2(1-1/$l$), where $l$ is the number
of leaves in $\cal S$, and inefficiency is defined as the ratio of the cost of
the heuristic tree to the cost of the optimal tree.
% the optimal tree.
% why ``optimal'' tree?  Isn't it the number of elements in S????
% Matt says: S is a subset of the optimal tree's nodes. No leaves other
% than those in S, so clearer to use S, OK, done.
The mean inefficiency of the heuristic
algorithms is generally considerably better than this, often less than
1.05.  The KMB MST heuristic algorithm, whilst not having a
computational complexity as low as others, is relatively 
simple to implement and
shows similar inefficiency characteristics when compared with the other
more complex heuristics of both approaches~\cite{Jiang,Waxman}.  The
mean performance of the KMB heuristic is close enough to the optimal
solution to permit its use for the purposes of comparison of the
simple algorithm introduced in Section~\ref{Addition}.

Whilst there are many parameters which are important in setting up a
multicast connection, most of which involve some form of heuristic
solution to the MST problem for various factors, the dynamic aspect of
many multicast connections means that the time and effort expended in
setting up a near-optimal solution is likely to be wasted soon after
completion, when the configuration must be changed yet again.
This is especially true as the size of $\cal S$ grows or the rate of change of
group membership increases. 

As shown in Figure~\ref{fig:routing-categories}, there are three ways in which
heuristic Steiner trees may be used for routing multicast groups whose
membership is dynamic.  One is to re-route the whole tree whenever the
group membership changes.
This may have repercussions for members who remain in the
group, since  there may be a disturbance in the communication, and in an ATM network~\cite{CCITT:150},
such a change may allow cells to arrive out of order at the destination.
Another method is to permit partial or local rearrangement of the tree when
modifications to the membership occur. This has the same reordering drawback as
total re-routing. 

Yet another  approach is to begin with an optimal (or near optimal) tree and make
minimal changes to it as group membership changes --- in the extreme causing
no disruption to members who remain in the group.  This is consequential to
the approach described by Waxman in~\cite{Waxman}.  
As membership in the group changes, one would
expect the inefficiency of this method to degrade and indeed simulation 
studies have shown occasional `spikes' of very high inefficiency~\cite{Waxman92}.

A third category of multicast routing is shown on the right in Figure~\ref{fig:routing-categories}. This is to choose a suboptimal tree which will be resilient to
changes.  In the extreme case, finding the minimum source to destination
path for all destinations independently and taking the union of these paths
produces a tree which will be resilient to changes 
 but will produce suboptimal trees.
 By resilience we mean that the spikes of inefficiency should be much smaller, since the inefficiencies are 
 independent of the order in which the  modifications occur.
The computational complexity of a single-source shortest paths algorithm, such
as that due to Dijkstra, is $O({\vert}{{\cal G}{\vert}}^{2})$ but can be
reduced to $O(e\log |\cal G|)$ for sparsely connected  graphs, where
 $e$ is the number of edges in $\cal G$.


We consider that the scarce resource in future multicast networks will not be the
bandwidth, but instead will be the number of signalling messages which must be
generated and, in ATM networks, ensuring that no reordering of cells occurs.
% would like to compare to Waxman's work in detail
% but don't have enough detail in JSAC paper
% and his thesis isn't done yet. Can compare general trends.
In this paper we examine the performance of the 
last approach on randomly constructed networks
undergoing stochastic addition
and removal of destinations from a multicast connection.
The use of  well-known routing algorithms such as minimum source-destination
path routing also provides a simple way to involve 
the requisite constraints such as delay, bandwidth
and reliability, since these are relatively well understood for
point-to-point routing~\cite{Wang92}.

%\subsection*{Layout of Paper}

\section{Network Models}
%--------------------------
\label{Models}

\subsection{Random Graphs}
\label{rg}

To ensure that simulations of the effects of the different routing algorithms
were independent of the idiosyncrasies of any specific  network, random
graphs were constructed. These were developed so that  their connectivity characteristics
approximated those observed in real networks.

The first network model to be considered, following Waxman~\cite{Waxman}, was one where graphs were constructed by distributing $n$
nodes across a Cartesian coordinate grid. The location of each node had
integer coordinates and multiple nodes were permitted to exist at any
location. The edges were added to the graph by considering all possible pairs 
 $(u,v)$ of nodes and using the probability function
%
   \begin{equation}
  \label{eq:edge}
  P_e(u,v) = \beta \exp{\frac{-d(u,v)}{\alpha L}}
   \end{equation}
%   
to create an edge, where $d(u,v)$ was the Euclidean distance between the nodes'
locations, 
$L$ was the maximum possible distance between two nodes and  $\alpha$ and
$\beta$ were parameters in the range $0 < \alpha, \beta \leq 1$.
%(0.1] 
A large value of $\alpha$ increases the number of connections to nodes further away, whilst a large value of $\beta$ increases the number of
edges from each node.
The cost of an edge was defined simplistically as $d(u,v)$, the distance between its
nodes, being a  typical factor in multicast routing problems. 
Each graph was tested to ensure that only one connected component
existed, i.e.\ that a spanning tree existed which covered all the nodes in $\cal G$.
Graphs were generated until one with a single connected component had been created.

This method of graph construction produces graphs which model some aspects 
of real networks. 
For instance, values of 0.25 and 0.2 for $\alpha$ and $\beta$ provide 
graphs which have the appearance roughly resembling that 
of geographical maps of the major nodes in the Internet. 
However, one problem with the model as originally proposed is that 
as the number of nodes increases, the number of edges  from each node ({\em degree} tends to increase as
well. 
The graph on the left of Figure~\ref{fig:rg150} shows a 150 node random graph with a relatively large number (approximately six) of
edges from each node.
The modification proposed and implemented is to scale $P_e$ by a factor related to the number of nodes in the graph.
This is successful since the probability of each edge existing is independent
for each node
and hence forms a binomial distribution, which has a mean directly
proportional to the number of samples, in this case, the number of nodes in the graph.
To ensure that the mean degree of each node remains constant, another scale factor
related to the mean distance between two random points must be introduced. 
For $\alpha=0.25$ and $\beta=0.2$, this factor, $k$, is approximately 25, by measurement.
The modified probability function is shown in equation~\ref{eq:edge2}, 
where $\overline{e}$ is the mean degree of a node 
 and ${\vert}{\cal G}{\vert}$ is the number of nodes in $\cal G$.
% CHECK : NEED HARD MATH TO FIND THIS FIGURE EXACTLY.
%
   \begin{equation}
  \label{eq:edge2}
  P_e(u,v) = \frac{k \overline{e}}{{\vert}{\cal G}{\vert}} \beta \exp{\frac{-d(u,v)}{\alpha L}}
   \end{equation}
%   
The graph on the right of Figure~\ref{fig:rg150} shows a 150 node random graph with a mean degree of three edges from each node.
As can be seen, the constant degree random graph network model provides
networks which more closely resemble real ones in their connectivity.

\begin{figure*}[htbp]
\begin{center}
\mbox{\psfig{figure=dense.ps,width=2.85in,height=3.75in}}
\mbox{\psfig{figure=sparse.ps,width=2.85in,height=3.75in}}
\caption{\label{fig:rg150} Original random graph and constant degree version}
\end{center}
\end{figure*}

\subsection{Hierarchical Graphs}

The second model of networks proposed attempts to model the hierarchy of 
networks that exist in reality, with multiple LANs connected to a WAN, or 
a LAN comprising many small switches.
A proportion of the $n$ nodes were used as
a core, connected in the manner of the modified random graphs of 
Section~\ref{rg} using the scaled version of the edge probability $P_e$ and checking for the existence of a single connected component.
The remaining nodes were divided into equal sized clusters, which were 
connected internally in the same fashion as the core. 
The clusters were then attached  by a fixed number of edges, typically two, to randomly chosen nodes in the core, not necessarily unique. 
Both the size of the central core and the size of the clusters on the Cartesian grid were specified. 
The final parameter was  whether the graph was separated or non-separated,
i.e.\ whether
 the clusters were permitted to overlap
the central core.
In the simulations presented in Section~\ref{Results}, non-separated graphs
were used and  the
clusters were permitted to overlap each other, modelling the existence of
multiple LANs at a site.
% CHECK : ENFORCING separation does what to TIME?

Figure~\ref{fig:hierarchy} shows typical network models constructed using
these guidelines.
Both graphs contain 100 nodes, 40 of which are in the core and the remaining
60 divided into three clusters of 20 each.
The clusters were limited in area to squares of side 200 in a square grid
of side 1000. The core was limited to a square of side 500 centred in the
grid.
The mean degree of each node was set at three and each cluster was connected to the core by two edges.
% CHECK : COMMENT ON TIME TO GENERATE?

\begin{figure*}[htbp]
\begin{center}
\mbox{\psfig{figure=nosep.ps,width=2.85in,height=3.75in}}
\mbox{\psfig{figure=sep.ps,width=2.85in,height=3.75in}}
\caption{\label{fig:hierarchy} Hierarchical graphs without and with separation}
\end{center}
\end{figure*}

\section{Modification Algorithm}
%---------------------------
\label{Mods}


After the graph had been constructed, one node was chosen at random
as the notional source of the multicast connection.
Another different node was also chosen and the shortest path
was found between them. 
Now that the multicast connection existed, further
destinations were added or deleted from the multicast tree using the following
probability function.
%
  \begin{equation}
  P_c(k) \: = \: \frac{\gamma(n-k)}{\gamma(n-k)+(1-\gamma)k}
  \label{eq:mod}
  \end{equation}
%  
where $P_c$ is the probability that the modification is an addition, 
$k$ is the number of destinations
 in the multicast connection, $n$ is the number 
of nodes in the graph and $\gamma$ is a parameter in the range 
$0 < \gamma < 1$.  
$\gamma$ is  the mean fraction of destinations/nodes in the connection.  
If $\gamma\ = k/n$, then $P_c(k) = 1/2$, if $k/n < \gamma$,
then $ P_C(k) > 1/2$ and if $k/n > \gamma$, then $ P_C(k) < 1/2$. 
A modification was defined as either an addition or a deletion.
  
%Note that a mean fraction of 100\% 

%THIS IS NOT WHAT WAS WRITTEN IN THE CODE BUT THE RESULTS ARE THE SAME
% SINCE THIS TEST IS NEVER TRUE WITH THE DEFINITION OF P_c AS ABOVE
%If the upper limit of all $n$ nodes in $\cal G$ being part of the multicast
%connection was reached and the probability function indicated that another
%node should be added, that modification was ignored (null action).

\subsection{Algorithms for the Addition of Nodes}
\label{Addition}

Waxman's original algorithms~\cite{Waxman,Waxman92} for connecting new destinations to an existing multicast connection were:

\begin{description}

\item[Greedy] Find the nearest node already in the connection to the node to
be added and connect the two. 
%Delete a node only if it is a leaf. Otherwise, leave it in the tree as an inactive destination.

\item[Weighted Greedy] Take a proportion of the weight from the greedy
algorithm and a proportion (e.g.\ 0.3) of the distance from a node known as the notional owner 
(the source) of the connection. 
Use the minimum of the sum of these two weights to decide
which existing node in the multicast connection  to route to the new node 
from.

\end{description}


Other proposed costs include the distance from the centre of the tree (see
\cite{AHO}, pp.\ 213--214 for a definition of centrality) or the number of
connections attached to a node. 

The above algorithms all fall into the category of
heuristic Steiner trees with addition, as shown in
Figure~\ref{fig:routing-categories}. 
The algorithm used in the simulations described in this paper is one in which
  the tree which is constructed is independent of the order of the modifications.
  The particular algorithm chosen was to find the shortest path
from the source to the node which had been chosen to be added and to add all the nodes along that
path into the multicast connection as Steiner nodes.

An example of another simple algorithm would be to find the shortest path from the source
using dynamic costs on the edges. 
If $k$ paths to destinations used an
edge in the graph, then its cost would be scaled by $k$, encouraging Steiner trees with minimal diversion until near the destinations.


\subsection{Algorithm for the Deletion of Nodes}
%-----------------
\label{Deletion}

Multiple destinations were allowed to exist at the same node in the graph, modelling multiple destinations on the same LAN, for instance.
If a node chosen for deletion was found to have multiple destinations,  
then the number
of destinations was simply decremented by one. 
However, if there was only one destination at the node chosen for deletion
 and the node was a leaf, then, after deletion of the node, its immediate predecessor
 was  considered recursively for deletion. 
The recursive deletion ceased when a  node was encountered which was 
part of an internal path to another destination.
In this case the node  was left in the Steiner tree, but marked as deleted for later action if
 the other dependent destinations subsequently became deleted.  
The source node was never deleted in this scenario, and if 
the lower limit of two nodes in the connection was reached and the modification 
function indicated the deletion of a node, then  no action was taken.


This series of decisions and recursions is realistic, since routing tables
at each node  have to contain enough information about the numbers
of multicast destinations using the node to permit timely recovery of
resources when a destination is removed from the multicast connection.


\section{Results}
%---------------------
\label{Results}

Multiple simulations of the above models were performed and the results are
shown in Figures~\ref{fig:single-run} to~\ref{fig:g}. 
%\ref{fig:a}, \ref{fig:b}, \ref{fig:c} and 
For each run a graph was generated according to one of the network models 
described in Section~\ref{Models} and 2000 modifications were
simulated. The ratio of the cost of the multicast tree obtained by the
simple algorithm to that of the KMB Steiner heuristic tree constructed afresh
 for the current set of 
destinations was evaluated every 10 modifications.
This ratio is  close to the inefficiency mentioned in Section~\ref{Introduction}. 
Ten series of  generation of a graph and a run of modifications were performed for each point to obtain the
Student-t distribution confidence intervals shown in the graphs.
Longer runs indicated little reduction in confidence intervals in most
cases.

Figure~\ref{fig:single-run} shows how the inefficiency changes with the number of
modifications made.
The graph shown on the left is for a 100 node constant degree random graph with a mean of
50 destinations in the multicast connection and a mean degree of three. 
The graph on the right shows how the number of nodes involved in the multicast
connection changes during the simulation.
The shape of these graphs is typical of the changes in the inefficiency
and number of nodes 
as modifications are made for many different sizes of graphs, fractions of the graph nodes involved in the multicast connection and different network 
models.
The spikes are not so sharp as those seen by Waxman~\cite{Waxman92} due to  
the nature of the na\"{\i}ve algorithm, since the multicast tree constructed by
it is independent of the order in which the modifications occurred. The
inefficiencies which do occur are due to occasions when a new node being added
is close to one already in the multicast tree, but a (partially) disjoint path is used to
reach it and the path is only slightly shorter than the path to the new node
 via the existing node.

%{\sc NOTE: Simulations of the algorithms originally proposed by
%Waxman~\cite{Waxman} and described in Section~\ref{Addition} are underway
%to provide graphical comparisons of the `spikes' mentioned here.}
% CHECK comparison to real minimum STs?

\begin{figure*}[htbp]
\begin{center}
\mbox{\psfig{figure=single-run2.ps,width=2.85in,height=3.75in}}
\mbox{\psfig{figure=single-run-nodes.ps,width=2.85in,height=3.75in}}
\caption{\label{fig:single-run} Inefficiency and number of nodes for a single run}
\end{center}
\end{figure*}


Figure~\ref{fig:a} shows how the mean and maximum values of the inefficiency changes with an increasing
number of destinations involved in the multicast connection for
various sizes of the original random graphs network model. 
As can be seen, increasing the graph size results in an increase in the
inefficiency whilst the changing proportion of destinations makes only a
minor difference to the inefficiency.
%% really ought to rerun some simulations to get these low values?
%For low proportions of destinations, the na\"{\i}ve algorithm's cost is close to
%that of the KMB algorithm, since there are only a few obvious choices for
%different paths. 
The inefficiency is unity when only two nodes are involved in the connection, since the shortest path between the two is also the (trivial) Steiner tree.
When all the nodes are involved in a connection, the KMB tree is the minimum
spanning tree of the network. This does not occur in the graphs shown since
multiple destinations can exist at a single node.
The increase in confidence intervals as the size of the graph increases is
probably due to the increased possibility of the existence of long paths
mostly separated from the rest of the multicast tree, which affect the
performance of the simple algorithm drastically.
This effect can also be seen in the graph of the maximum values, though the
general trend in both cases is that the inefficiency increases as the
number of nodes, and in this case the degree, increases.
% CHECK : THINK HARD ABOUT THIS FOR THESIS

\begin{figure*}[htbp]
\begin{center}
\mbox{\psfig{figure=giga4.2.mean.ps,width=2.85in,height=3.75in}}
\mbox{\psfig{figure=giga4.2.max.ps,width=2.85in,height=3.75in}}
\caption{\label{fig:a} Mean and maximum inefficiency of original random graph}
\end{center}
\end{figure*}


    
 Figure~\ref{fig:b} shows how the mean values of the inefficiency changes with an increasing
 number of destinations involved in the multicast connection for
various sizes of  random graphs with the constant degree network model.
As can be seen in the graph on the left, increasing the graph size
 results in little change in the
inefficiency if the degree is constant.
It also shows that the inefficiency is relatively independent of the 
number of nodes in the network for a given proportion of destinations involved in a multicast connection. 
The graph on the right in Figure~\ref{fig:b} shows the results of varying
 the degree of a 100 node constant degree random graph.
   It suggests that the performance of
the simple addition algorithm is indeed directly related  to the mean
degree of the graph. 
Figure~\ref{fig:d} confirms that this relationship is
approximately linear.

\begin{figure*}[htbp]
\begin{center}
\mbox{\psfig{figure=giga6.mean.ps,width=2.85in,height=3.75in}}
\mbox{\psfig{figure=giga9.mean.ps,width=2.85in,height=3.75in}}
\caption{\label{fig:b} Inefficiency of constant degree random graph for various graph sizes and degrees}
\end{center}
\end{figure*}

  Figure~\ref{fig:c} shows how the mean  value of the inefficiency changes with an increasing
 number of destinations involved in the multicast connection for
various sizes of the hierarchical graphs network model.
As can be seen in the graph on the left, increasing graph sizes again result in little change in the
inefficiency.
The values of the inefficiency obtained
with the hierarchical model are less than those obtained with the constant 
degree model, probably due to a more
limited set of inter-cluster paths from node to node, so the na\"{\i}ve algorithm is more likely to choose the same ones as an optimal MST algorithm.
The graph on the right in Figure~\ref{fig:c} shows  the
effects of varying the degree of a 100 node non-separated hierarchical graph.
   It suggests that, as with the constant degree model,  the performance of
the simple addition algorithm is related  to the mean
degree of the graph.

\begin{figure*}[htbp]
\begin{center}
\mbox{\psfig{figure=giga7.mean.ps,width=2.85in,height=3.75in}}
\mbox{\psfig{figure=giga10.mean.ps,width=2.85in,height=3.75in}}
\caption{\label{fig:c} Mean Inefficiency of non-separated hierarchical graph for various sizes and degrees}
\end{center}
\end{figure*}

Figure~\ref{fig:d} confirms the approximately linear relationship between the degree and the
inefficiency for both network models. The values shown are for 20\% and
60\% destinations/nodes in the 100 nodes of the graph being  involved in 
the multicast connection  (on average). As the degree increases, the number of available
paths between any two nodes increases and hence the possibility of the shortest
path tree coming close to the heuristic KMB tree decreases and the
inefficiency increases.
% not sure why it's linear tho'

\begin{figure*}[htbp]
\begin{center}
\mbox{\psfig{figure=20-60.ps,width=2.85in,height=3.75in}}
\caption{\label{fig:d} Mean Inefficiency for both network models and various degrees at 20\% and 60\% destination nodes/total nodes} 
\end{center}
\end{figure*}

%As mentioned in Section~\ref{Introduction}, the computational order of the KMB heuristic is
%$O({\vert}{\cal S}{\vert}{\vert}{{\cal G}{\vert}}^2)$ 
%If an adjacency list is used to represent the (sparse) graph and a
%partially ordered tree used to represent the costs (see~\cite{AHO},
%pp.\ 207,211), then the worst case computational complexity for 
%Dijkstra's shortest path algorithm can be reduced to $O(e\log |\cal G|)$, where
%$e$ is the number of edges in the graph, which is directly proportional to
%$|\cal G|$ in the constant degree random graph network model.

% should the figures have the conf ints removed for high and low
% values for clarity?
Figures~\ref{fig:e} to~\ref{fig:g} all refer to random graphs with 100 nodes and give further insight into the difference in performance 
between heuristic Steiner tree algorithms such as KMB and the na\"{\i}ve but robust shortest path algorithm.

Figure~\ref{fig:e} shows how the maximum path length varies with the
percentage of destinations/total nodes and also with the mean degree.
As may be seen, the paths chosen by the na\"{\i}ve algorithm are indeed
shorter than those chosen by KMB and the length of the paths decreases as the
degree of connection of the graph increases. The maximum path length tends to
increase in KMB trees as the proportion of destinations increases. In shortest
path trees, the change is less marked. This is probably due to the extended
nature of the trees constructed from pruned minimum spanning trees, compared 
to the more compact nature of a tree constructed from shortest paths.

\begin{figure*}[htbp]
\begin{center}
\mbox{\psfig{figure=path-percent-maxlength.ps,width=2.85in,height=3.75in}}
\mbox{\psfig{figure=path-degree-maxlength.ps,width=2.85in,height=3.75in}}
\caption{\label{fig:e} Maximum path length for Shortest Path (SP) and KMB trees with  various percentages of destination nodes/total nodes and degrees} 
\end{center}
\end{figure*}

Figure~\ref{fig:f} shows  the maximum hop count for each path in the two sets of trees, and how it varies with the
percentage of destination nodes/total nodes and also with the mean degree.
Again, very little difference is seen in the values from the shortest path
graphs as the proportion of destinations changes. A small decrease with
respect to the degree can be seen in the graph on the right. The changes for
the KMB graphs are even more marked than the maximum path length seen in
Figure~\ref{fig:e}, though the reasons for them are much the same.
The maximum hop count for the KMB trees is observed to change very little with
respect to the degree of the underlying tree, increasing slightly as the degree increases.
% WHY?

\begin{figure*}[htbp]
\begin{center}
\mbox{\psfig{figure=path-percent-maxhop.ps,width=2.85in,height=3.75in}}
\mbox{\psfig{figure=path-degree-maxhop.ps,width=2.85in,height=3.75in}}
\caption{\label{fig:f} Maximum number of hops for Shortest Path (SP) and KMB trees with  various percentages of destination nodes/total nodes and degrees} 
\end{center}
\end{figure*}

Figure~\ref{fig:g} shows the mean bandwidth used by each tree, defined as mean of
the reciprocal of $n_e$ for each edge in the multicast tree subgraph, where $n_e$ is the
number of paths which use the edge e. 
The bandwidth is scaled to the bandwidth which would be required if
no multicast were possible except at the source.
Thus an edge which is only used by one
path has a bandwidth of 100\%, compared to one used by two paths, which uses 50\%, 
and so on. As may be seen from the figure, the KMB algorithm gives a
substantial reduction in the bandwidth used, compared to the shortest path 
algorithm. The reduction is again dependent upon the percentage of destination
nodes/total nodes 
involved in the multicast tree, this time improving as the proportion
increases.
%WHY
The na\"{\i}ve shortest path algorithm on the other hand gives a relatively small sharing
of bandwidth resources, though it is almost independent of the mean degree of the
graph.
% talk about merging/adaptive improvements?

\begin{figure*}[htbp]
\begin{center}
\mbox{\psfig{figure=path-percent-meanbw.ps,width=2.85in,height=3.75in}}
\mbox{\psfig{figure=path-degree-meanbw.ps,width=2.85in,height=3.75in}}
\caption{\label{fig:g} Mean bandwidth relative to unicast network, for Shortest Path (SP) and KMB trees with  various percentages of destination nodes/total nodes and degrees} 
\end{center}
\end{figure*}


\section{Improvements}
%---------------------
\label{Improvements}

Whilst the simple  algorithm described above provides a set
of multicast connections which  appear to tend to a fixed multiple of the cost of an optimal solution in the long run, the erratic
nature of call modification means that there may be opportunities for an
intermittent process to exist, whose purpose would be  to examine the existing tree
and construct a set of modifications which would transform the tree into a
near-optimal Steiner tree. 
The algorithm used for this process would be a modification of one of the previously mentioned heuristic algorithms, possibly limited by the number and 
type of 
routes that it would be permitted to alter. 
Alternatively, one of the heuristics could be used as they were presented 
and the whole multicast tree could be periodically torn down and set up again, probably closer to an optimum solution. 

The timing of this optional process of improvement could be 
controlled by the source to avoid re-routing during transmission and the consequent risk of reordering. It 
might be encouraged by a possible reduction in the   charge for the
 multicast connection in a WAN.

\section{Conclusions}
%---------------------
\label{Conclusions}

The proof that multicast routing was equivalent to constructing a Steiner tree, which is an NP-complete problem, lead to various
heuristics being proposed, with worst case performance generally twice that of the
optimum solution but with average performance much closer to the optimum. 
These heuristics were modified to optimise the tree for
various parameters, all of which are important, but none  of which is crucial in itself.

In the long-term operation of any real
network which  provides multicast capability, the dynamic nature of 
multicast applications is
such that the previously proposed heuristic algorithms are likely to provide 
solutions whose success is only ephemeral.

The simulations in Section~\ref{Results} imply that even one of the simplest
routing algorithms can provide a mean inefficiency  
 (for a mean number of three edges per node)
 which is
within a factor of 1.5 of typical heuristic solutions, which themselves have
an upper-bound of being within a factor of 2 of the optimal solution (and typically within a  factor of 1.2).
More realistic network models such as the hierarchical model indicate even
better performance.

It is suggested that any future work in this area should concentrate upon the
ability to add and remove connections from a multicast tree and attempting to
improve the routes chosen in an incremental fashion, rather than constructing
monolithic solutions to a problem specification that may only be valid for a
unprofitably short duration. The further development of hierarchical random
graph network models is also of interest for future studies in this area.


%{\bf Acknowledgements:} 


\begin{thebibliography}{99}
%----------------------------

%Heterogeneous networks
\bibitem{Infocom91.11B.1} C H Chow, {\em On Multicast Path Finding
Algorithms}, Proceedings of IEEE Infocom 1991, Miami.

%h/w has an influence on protocol, limited mcast
\bibitem{Infocom92.9A.2} H Tode, Y Sakai, M Yakamoto, H Okada and Y Tezuka,
{\em Multicast Routing Algorithm for Nodal Load Balancing}, Proceedings of IEEE
Infocom 1992, Florence.

\bibitem{Gilbert} E N Gilbert and H O Pollak, {\em Steiner Minimal Trees},
SIAM Journal of Applied Mathematics, Vol.16, No.1, pp.1--29, 1968.

\bibitem{Karp} R M Karp, Reducibility among combinatorial problems. In {\em
Complexity of Computer Computations}, R E Miller and J W Thatcher (editors),
pp.85--103. Plenum Press, New York, 1972.

\bibitem{Winter} P Winter, {\em Steiner Problem in Networks}, Networks, Vol.17,
pp.129--167, 1987.

\bibitem{RS} V J Rayward-Smith and A Clare, {\em On finding Steiner Vertices},
Networks, Vol.16, pp.283--294, 1986.

\bibitem{Wall} D Wall, Selected Broadcast in Packet-Switched Networks. In {\em
Multicast Communication in Distributed Systems}, M Ahamad (editor), IEEE
Computer Society Press, 1990.

\bibitem{KMB} L Kou, G Markowsky and L Berman, {\em A Fast Algorithm for
Steiner Trees}, Acta Informatica Vol.15, pp.141--145, 1981


\bibitem{Jiang} X F Jiang, {\em Multipoint Digital Video Communications}, PhD
Thesis, University of Cambridge Computer Laboratory, 1991.

\bibitem{Waxman}
	Bernard M Waxman, 
	{\em Routing of Multipoint Connections},
	IEEE J. Selected Areas in Communications, Vol.6, No.9, December 1988.

\bibitem{CCITT:150} CCITT, Draft Recommendation I.150, {\em B-ISDN ATM Aspects}, Geneva, January 1990.

\bibitem{Waxman92} Private communications with B M Waxman.


%\bibitem{Newman90}
%    P Newman and M Doar,
%    {\em A Slotted Ring Copy Fabric for a Multicast Fast Packet Switch},
%    Proc. Int. Switching Symp. 1990 (ISS '90),
%    Stockholm, Sweden,
%    May,
%    1990

\bibitem{Wang92} Z Wang, {\em Routing and Congestion Control in Datagram Networks},
PhD Thesis, University College, London, January 1992.


\bibitem{AHO} Aho, Hopcroft and Ullman, {\em Data Structures and Algorithms},
Addison-Wesley, 1983.


%\bibitem{IEETransCom} thput?

%\bibitem{Snapshot2} {\em ATM Document Collection}, Systems Research Group
%Technical Note, 29th February 1992, University of Cambridge Computer
%Laboratory.

%\bibitem{sac-qos} qos considerations for mcast, ref sac?

%\bibitem{Shachum92} hierarchical stuff of Shachum?



%\bibitem{RS-GA} A Kapsalis, V J Rayward-Smith, G D Smith, {\em Solving the
%Graphical Steiner Tree Problem using Genetic Algorithms}, Internal Report
%SYS-C92-01, School of Information Studies, University of East Anglia, Norwich,
%UK.

\end{thebibliography}

\end{document}
