\chapter{Review of the Literature}

	\hspace*{8mm} The routing algorithms that we refer to will be the
	algorithms used in the  network layer protocol that guides the
	packets through the communication subnet to their correct
	destination. The network is abstracted into a set of nodes and
	links, or a graph. A subnetwork is treated as a node at this
	level, so that the activities within a subnetwork are hidden.
	In other words, we consider point-to-point links.


	\section{Main Issues in Routing} 

		\hspace*{8mm} The two main functions performed by a
		routing algorithm are the selection of routes for
		various source-destination pairs and the delivery of
		messages to their correct destination once the routes
		have been selected.

		The two main performance measures affected by routing
		algorithms are packet delay and the throughput. The
		packet delay is defined to be the time between the
		generation of a packet and the arrival of that packet
		at its destination.  The throughput is commonly defined
		to be the difference between the offered load and the
		rejected load, where the offered load is the messages
		issued by each node, and the rejected load is the
		messages rejected by the network because of traffic
		congestion\cite{BERTSEKAS}.

	\section{Classification of Routing Schemes} 

		\hspace*{8mm} There are a number of ways to classify
		routing algorithms. We briefly discuss some of the
		classifications \cite{BERTSEKAS,DEERING,STALLINGS}, and
		then pay more attention to the ones that are related to
		our work.

		The first classification we will look at is based on
		the decision time. The times at which routing decisions
		are made depend on whether the network uses datagrams
		or virtual circuits. In a datagram network, two
		successive packets of the same source-destination pair 
                may travel
		along different routes, and a routing decision is
		necessary for each individual packet. In a virtual
		circuit network, a routing decision is made when a
		virtual circuit is set up. We are mainly concerned with
		datagram routing.

		The second classification  divides routing algorithms
		into centralized and distributed. In centralized
		algorithms, all routing choices are made at a central
		node, while in a distributed algorithm the computation
		of routes is shared among the network nodes with
		information exchanged between them as necessary.

		The third classification of routing algorithm is based
		on the routing strategies. There are four major types
		of routing strategies: fixed routing, flooding
		routing, random routing, and adaptive routing.

		One of the simplest routing strategies is fixed
		routing.  In this case, a route is selected for each
		source-destination pair of nodes in the network. The
		routes are fixed, or at least only changed when there
		is a change in the topology of the network. Thus the
		costs used in designing routes cannot be based on any
		dynamic variable such as traffic. It can, however, be
		based on cost or expected traffic. The advantage of
		fixed routing is its simplicity. Its disadvantage is
		its lack of flexibility.

		Another simple routing strategy is flooding routing.
		This technique requires no network information, and
		works as follows. A packet is sent by a source node to
		every one of its neighbors. At each node, an incoming
		packet is retransmitted on all outgoing links except
		for the link that it arrived from. If the incoming
		packet is a duplicate it will not be forwarded. This
		ensure that the flooding process will eventually
		terminate.  This technique is highly robust and can be
		used to send high-priority messages. The disadvantage
		of flooding is the total traffic load that it
		generates.

		The next routing strategy is random routing. With
		random routing, a node selects only one outgoing path
		for retransmission of an incoming packet. The outgoing
		link is chosen at random, generally excluding the link
		on which the packet arrived. Random routing has the
		simplicity and robustness of flooding with less traffic 
		load. To ensure that the routing process terminates,
		it may have to keep track of the duplicated packets.
		Also, a pure random routing scheme may fail to
		cover all nodes in the network. One way to solve 
		this problem is to forward packets to the outlinks 
		round-robinly. Random routing is not commonly used 
		because of the unpredictable delay and high traffic 
		caused by this scheme.

		The final routing strategy is adaptive routing.
		Adaptive routing strategies adapt to measurable
		changing condition such as topology change  and by
		other elements such as adaptive routing update time.

		The fourth classification of routing algorithms is
		based on the transmission methods. There are two major
		classifications of transmission methods,
		store-and-forward and hot-potato forwarding.

		Store-and-forward is probably the easiest to explain
		and the most widely implemented. When a packet or
		message arrives at a intermediate node on its path to
		the destination site, it waits in a queue for its turn
		to be transmitted on the next link in its path.

		Hot-potato forwarding states that for all packets
		simultaneously arriving at a given node and not
		intended for reception at that node are immediately
		placed onto the outbound links leaving that node. If
		two or more packets contend for the same outgoing link
		to achieve minimum distance routing, then all but one
		will be misrouted to links which produce longer paths
		to the eventual destination.

		The fifth classification of routing algorithms is based
		on the number of destinations a packet may be addressed
		to. We'll focus on this type of routing.  Three types
		of routing schemes are Unicast Routing, Broadcast
		Routing, and Multicast Routing.

		Unicast Routing is defined to be routing from a single
		source node to a single destination node in the network
		and will be discussed in Section 2.3.
		Broadcast Routing is routing from a single source node
		to all other nodes in the network and  we will be
		described in Section 2.4.
		Multicast Routing is routing from a single source to a
		subset of the other nodes in the network. We will refer
		to this subset as a group.  Multicast Routing also
		includes the case of routing from a single source to
		several groups which may overlap one another. We will
		discuss this type of routing in Section 2.5.

		We must point out that the above three types of routing
		are not mutually exclusive; on the contrary, they often
		coexist in a network.

	\section{Unicast Routing}

		\hspace*{8mm} Unicast routing is  the dominant activity
		in the network. It can be seen as a special case of
		multicast routing, but it is never treated that way
		because of its dominance. In this section we will
		describe the shortest-path based algorithms which are
		widely used in network routing\cite{BERTSEKAS}.

		In a network each link is assigned a cost, which can
		simply be one, the recent traffic, or the queue length
		at the link.  The cost for the same link from the two
		opposite directions can therefore be different. The
		goal of the shortest-path based routing is to choose a
		path which gives the minimum sum of link costs.

		In unicast routing algorithms,  each node  usually has
		a routing table with entries of the form

		{\small
		\begin{center}
		\begin{tabular}{|l|l|l|l|} \hline
		destination & distance & next hop & ...\\ \hline
		\end{tabular}
		\end{center}
		}

		\noindent where next hop tells which link to take to
		reach the destination on the shortest path from the
		current node. When a packet arrives at a node, the
		shortest path is looked up from the table and the
		packet is sent to the ``next hop'' link.  The routing
		table is updated when there is a topology change or a
		change in link cost. Link cost change is possible only
		when the link cost reflects the traffic. In this case,
		a cost change message is nothing but a traffic report,
		which is broadcast periodically.

		Several shortest path algorithms are important to us.
		We describe them precisely since we will implement some
		of them for our study.

		\subsection{Bellman-Ford Algorithm }

			\hspace*{8mm} The first algorithm we wish to
			look at is the Bellman-Ford Algorithm
			\cite{BERTSEKAS,STALLINGS}. In this
			algorithm you first find the shortest paths
			from a given source node subject to the
			constraint that the paths contain at most one
			link; then find the shortest paths with a
			constraint that paths can be at most two links;
			and so on. This algorithms proceeds in stages
			and is  formally described below. First we must
			define a few terms that will be used.

			\begin{eqnarray*}
			s     &=& {\rm source\ node} \\
			d_{ij}&=& \left\{\begin{array}{ll}
			   0 & {\rm if \;} i=j; \\
			   \infty & {\rm if\ the\ two\ nodes\ 
				are\ not\ directly\ connected;}\\
			   <\infty & {\rm if\ the\ two\ nodes\ 
				are\ directly\ connected.}
			  \end{array} \right. \\
			h   &=& {\rm max.\ no.\ of\ links\ in\ 
				a\ path\ at\ the\ current\ stage}\\
			D_n^{(h)} &=& {\rm cost\ of\ the\ 
				shortest\ path\ from}\;s\;
			        {\rm to}\;n\; {\rm with}\;\leq h\; 
				{\rm links.} 
			\end{eqnarray*}
			The algorithms has two steps; the first step is
			just initialization and the second step  is
			repeated until none of the costs change:
			\begin{list}{}{\setlength{\leftmargin}{0.5in}
			               \setlength{\rightmargin}{0.5in}}
			\item[1.] Initialize:\\
			          $D_n^{(0)} = \infty$, for all $n \not= s$\\
			          $D_s^{(h)} = 0$,  for all $h$

			\item[2.] For each successive $h \geq 0$:\\
			          $D_n^{(h+1)} = \min_j \{D_j^{(h)} + d_{jn}\}$
			\end{list}
			\noindent The path from $s$ to $i$ terminates
			with the link from $j$ to $i$.

			For the iteration of step 2 with $h = k$, and
			for each destination node $n$, the algorithm
			compares potential paths from $s$ to $n$ of
			length $k+1$ with the path that existed at the
			end of the previous iteration. If the previous
			shortest path has less cost, then that path is
			retained. Otherwise, a new path with length
			$k+1$ is defined from $s$ to $n$; this path
			consists of a hop from node $j$ to node $n$. In
			this case, the path from $s$ to $j$ that is
			used is the $k$-hop path for $j$ defined in the
			previous iteration.

		\subsection{Dijkstra's Algorithm}

			\hspace*{8mm} The second algorithm is known as
			the Dijkstra's algorithm\cite{BERTSEKAS,STALLINGS}. 
			You first find the
			shortest paths from a given source node to all
			other nodes by developing  paths in order of
			increasing path length. The algorithm also
			proceeds in stages. By the $k$-th stage, the
			shortest paths to the $k$ nodes closest to
			(least cost away from) the source node have
			been determined; these nodes are in a set $M$.
			At stage $k+1$ , the node not in $M$
			that has the shortest path from the source node
			is added to $M$. As each node is added to $M$,
			its path from the source is defined. Before we
			can  formally describe the algorithm we must
			define some notation.

			{\small
			\begin{eqnarray*}
			N &=& {\rm set\ of\ nodes\ in\ the\ network} \\
			s &=& {\rm source\ node} \\
			M &=& {\rm set\ of\ nodes\ so\ far\ 
				incorporated\ by\ the\ algorithm} \\
			d_{ij} &=& \left\{ \begin{array}{ll}
			  0 & {\rm if} \; i = j; \\
			  \infty & {\rm if\ the\ two\ nodes\ are\ 
				not\ directly\ connected};\\
			  <\infty & {\rm if\ the\ two\ nodes\ are\ 
				directly\ connected}.\\
			\end{array} 
			\right. \\
			D_n &=& {\rm cost\ of\ the\ shortest\ path\ 
				from}\;s\; {\rm to}\;n,\
			        {\rm currently\ known\ to\ the\ algorithm}
			\end{eqnarray*}
			}

			The algorithm has three steps. The first step
			again is initialization and the second and
			third steps are repeated until $M=N$.  That is,
			steps 2 and 3 are repeated until final paths
			have been assigned to all nodes in the
			network.
			\begin{list}{}{\setlength{\leftmargin}{0.5in}
			               \setlength{\rightmargin}{0.5in}}
			\item[1.] Initialize:\\
			          $M = \{s\}$\\
			          $D_n = d_{sn}$ for $n \not= s$
			\item[2.] Find the neighboring node not in M
				that has the least-cost path from node
				$s$ and incorporate that node into
				$M$:\\ Find $w \not\in M$ such that
				$D_w = \min D_j,\; j \not\in M$\\ Add
				$w$ to $M$
			\item[3.] Update least-cost paths:\\
				  $D_n = \min\{D_n, D_w+d_{wn}\}$ for
				  all $n\not\in M$\\ If the latter term
				  is the minimum, the path from $s$ to
				  $n$ is now the path from $s$ to $w$
				  concatenated with the link from $w$
				  to $n$.
			\end{list}

		\subsection{Floyd-Warshall Algorithm}

			\hspace*{8mm} The third main unicast algorithm
			is the Floyd-Warshall algorithm\cite{BERTSEKAS}. 
			This algorithm
			finds the shortest paths between all pairs of
			nodes. It also assumes that there are no
			negative length cycles. For clarity, suppose we
			want to find the shortest paths from node 1 to
			all other nodes.

			Let $D^{(n)}_{ij}$ be the shortest path length
			from node $i$ to $j$ when only nodes 1 to $n$
			can be on the intermediate path. The algorithm
			goes as below.

			\begin{enumerate}
			\item $D^{(0)}_{ij} = d_{ij}$
			\item $D^{(n+1)}_{ij}=\min \left\{ D^{(n)}_{ij},\; 
				D^{(n)}_{i,(n+1)}+D^{(n)}_{(n+1),j}\right\}$
			\end{enumerate}

			\noindent Step 2 is repeated until $n$ reaches
			$N$, the number of nodes in the network.

		\subsection{Distributed Bellman-Ford Algorithm}

			\hspace*{8mm} The fourth main algorithm is the
			Distributed Bellman-Ford algorithm
			\cite{BERTSEKAS}. We will
			describe the basic form of the algorithm and
			then some improvements for solving  problems
			that the basic algorithm cannot handle.

			First let us  look at the basic algorithm.
			Consider a routing algorithm that routes each
			packet along a shortest path from the packet's
			source to its destination. The link cost may
			change either due to link failures and repairs,
			or due to changing traffic conditions in the
			network.  It is therefore necessary to update
			shortest paths in response to these changes.
			Algorithms which do this are called distributed
			algorithms. The main idea is to compute the shortest
			distances from every node to every other node
			by means of a distributed version of the
			Bellman-Ford algorithm.

			Assume that each link $(i,j)$ has a positive
			length $d_{ij}$, the network is strongly
			connected (meaning that all nodes in the
			network are mutually reachable), and if $(i,j)$ 
			is a link, then
			$(j,i)$ is also a link.  This algorithm only
			requires that each node know the length of its
			outgoing links and the identity of every node
			in the network.

			The algorithm calculates the shortest distance
			$D_i$ from each node $i$ to, for example,
			node~1. Let $N(i)$ denote the neighbors of node
			$i$, the Bellman-Ford algorithm \[D^{(h+1)}_i =
			\min_{j\in N(i)} [d_{ij}+D^{(h)}_j], \; \; i
			\not= 1\] suggests that only the information on
			the neighbors of $i$ is necessary for
			calculation to carry on.  The distributed
			asynchronous Bellman-Ford algorithm is as
			follows:

			At each time $t$, a node $i \not= 1$ knows
			$D^i_j(t)$, the latest distance estimate of
			node $j\in N(i)$, and $D_i(t)$, the latest
			distance estimate of node $i$. Here distance
			means the distance to node 1. Initially these
			distances are set to be arbitrary positive
			values (usually quite large.) Each node 
			updates its information
			only at some times $t_0, t_1, \dots t_n$.  At
			any time $t_k$, one of the three events
			occurs:
			\begin{list}{}{\setlength{\leftmargin}{0.25in}
			               \setlength{\rightmargin}{0.25in}}
			\item[(1)] Node $i$ updates $D_i(t)$ by 
			           $D_i(t)=\min_{j\in N(i)}[d_{ij}+D^i_j(t)]$
			           and all $D^i_j(t)$ unchanged.
			\item[(2)] Node $i$ receives from some $j\in 
				N(i)$ new $D_j$ and update $D^i_j$.
			\item[(3)] Node $i$ is idle, no estimates held 
				by node $i$ are changed.
			\end{list}

			\noindent All nodes performs the same
			calculations in parallel and asynchronously,
			and all $D_i(t)$ converge to the correct
			shortest distances within finite time.

			Now let us look at some improvements on the
			distributed Bellman-Ford algorithm, most of
			which are based upon versions of distributed
			shortest path algorithms.

			First, Humblet\cite{HUMBLET} proposed an
			adaptive distributed shortest path algorithm
			which does not suffer from the ``routing table
			looping'' behavior associated with the
			Bellman-Ford distributed shortest path
			algorithm. For the basic Bellman-Ford
			distributed algorithm, link failures will cause
			the looping problem, i.e., some nodes will be
			updating their routing table endlessly,
			incrementing the distance entry forever (this
			is known as {\em counting}), and messages will
			cycle back and forth among involved nodes. In
			other words, the algorithm will not converge.
			In \cite{HUMBLET}, the problem was solved by
			setting an upper-bound on the maximum length
			that a link can achieve, and more importantly,
			by maintaining at each node a shortest path
			tree that is rooted at that node.

			Next Awerbuch and Gopal\cite{AWERBUCH} proposed
			an approximate distributed Bellman-Ford
			algorithm which has a polynomial message
			complexity.  This algorithm is an improvement
			upon the basic algorithm which suffers from
			exponential message complexity in some
			scenarios.  The only difference between the
			approximate algorithm and the basic algorithm
			is in the adopting rule. In the basic
			algorithm, the adopting rule is: Suppose node
			$x$, with a label $a(x)$, receives $a'(x)$ from
			$z$. If $a'(x) < a(x)$, then $x$ adopts $a'(x)$
			and sets the value of parent$(x)$ to $z$. In
			the approximate algorithm, the adopting rule
			is: Suppose node $x$, with a label $b(x)$,
			receives $b'(x)$ from $z$.  If $b'(x) <
			b(x)/k$, then $x$ adopts $b'(x)$ and sets the
			value of parent$(x)$ to $z$. Where the label
			$a(x)$ and $b(x)$ are the current known
			shortest distance from node $s$ to node $x$,
			and parent$(x)$ contains the identity of its
			previous node on the current known shortest
			path from $s$ to $x$.  Note that the two
			algorithms become identical when $k=1$. For the
			approximate algorithm $k$ is greater than or
			equal to 1.

	\section{Broadcast Routing}

		\hspace*{8mm} There are many cases in which a message
		needs to be broadcast to all nodes in the network. The
		most important use is to transfer control information
		when links are removed or the topology is changed.
		Flooding and Spanning tree are two major algorithms for
		broadcasting.

		Flooding is a simple algorithm for broadcasting. A node
		broadcasts an update message to all nodes by sending
		the message to its neighbors, which in turn send the
		message to their neighbors other than the one from
		which the message comes.

		Given a connected graph $G=(V,E)$ with $V$ the vertex
		set and $E$ the edge set, and a weight $W_{ij}$  for
		each edge $(i,j)$, the problem is to construct a
		spanning tree with minimum sum of edge weights. Such a
		tree is called a Minimum Weight Spanning Tree~(MST). An
		MST may be useful for disseminating messages destined
		for every node in a data network.  An edge weight
		represents the communication cost of a message along
		the edge in either direction, and the total spanning
		tree weight represents the cost of broadcasting a
		message to all nodes along the spanning tree.

		Broadcast algorithms often need a sequence number for
		each packet to avoid duplicates received at a node; and
		sometimes a periodical broadcast is used to guarantee
		that up-to-data information will become available
		within some fixed time.  Spinelli and
		Gallager\cite{SPINELLI} proposed an algorithm for
		broadcasting network topology change, 
		which does not require a sequence
		number and does not require a periodical broadcast.
		The main idea of the algorithm is to keep each network
		node informed of the entire network topology when the
		topology occasionally changes over time.  This
		algorithm is an event driven algorithm, i.e., it sends
		messages only in response to receiving other messages,
		or in response to topological changes in adjacent
		links.

		Gossiping\cite{KNISELY} is another way to broadcast. In
		Gossiping, each node exchanges information with exactly
		one of its neighbors at prescribed time instants. At
		different times, a node may exchange information with
		different neighbors. In doing so, every node is
		eventually informed of the state of all other nodes
		after  what is defined as the cyclic gossiping time.
		To minimize the gossiping time and the number of links
		required for information exchange, the gossiping
		procedure is first mapped into a graph coloring
		problem, in which adjacent edges are colored with
		different colors; for a graph with $k$ distinct colors,
		at time $t,\; t = 0, 1, 2, \dots$, each pair of
		vertices which are joined by an edge colored $i=t({\rm
		mod}\; k)$ exchange all of their information at that
		time. Some limited results are given in
		\cite{KNISELY}.

	\section{Multicast Routing}

		\hspace*{8mm} There is a large potential demand for
		multicast transmission such as e-mail, where a message
		has to be sent to more than one address; distributed
		database management, where a query may be sent to
		several sites that may have the data to answer it; and
		tele-conferencing. Deploying multicast routing
		algorithms in a very large network is a complex task.
		In this section, we will first review several basic
		multicast routing algorithms, then we will introduce
		some other algorithms which describe different aspects
		of multicast routing.

		\subsection{Flooding}

			\hspace*{8mm} Flooding is the simplest
			algorithm and was  described in Section 2.4.  A
			node in the network will receive a packet that
			was sent to a multicast destination. It will
			first try to ascertain whether this is the
			first reception of this particular packet or
			whether this is a duplicate. If it is a first
			transmission, it will transmit a copy of the
			packet on all neighbors, ensuring that the
			packet eventually reaches all network
			destinations. The key problem to any flooding
			implementation is indeed the test for ``first
			reception.'' One of the methods for solving
			this problem is by looking in the link state
			database, if the received link state update is
			newer than the local value, the database is
			updated and the packet is forwarded, else
			it is ignored.

		\subsection{Spanning Trees}

			\hspace*{8mm} A more efficient solution than
			flooding is the ``spanning tree'' technique.
			One will simply build up an ``overlay'' network
			by marking source links as ``part of the tree''
			and other links as ``unused.'' The set of
			selected links forms a loopless graph or a tree
			which spans to all nodes in the network.  Once
			a spanning tree has been built, the propagation
			of multicast packets becomes very simple. When
			a multicast packet is received it is
			immediately forwarded to all outgoing links
			that are part of the tree except the incoming
			link. Since the tree is loopless, we guarantee
			that the packet will reach all destinations.
			But the basic spanning tree has two drawbacks:
			it does not take into account group membership
			and it concentrates all the traffic into a
			small subset of the network links. This results
			in an algorithm that is very easy to implement,
			but is very inefficient.

		\subsection{Reverse-Path Forwarding (RPF)} 

			\hspace*{8mm} The RPF algorithm takes advantage
			of a routing table to ``orient'' the network
			and to compute an implicit spanning tree for
			each network source. In its simplest form, the
			RPF algorithm works as follows:
  			\begin{enumerate}
				\item When a multicast packet is
				received, note source $S$, and the incoming
				link $I$ (which can be thought of as an
				adjacent node.)
				\item If $I$ belongs to the shortest
				path to $S$, forward the packet to all
				links except $I$.
				\item If the test in step 2 is false,
				refuse the packet.
  			\end{enumerate}

			The advantage of this simple form is that RPF
			does not require any more resources than the
			normal ``unicast'' routing table; if we know
			how to compute the route toward $S$, then we
			can safely process multicast packets received
			from $S$.

			One obvious drawback of RPF is it only works
			when hop-distance is used, or when the
			distances in opposite directions are equal.
			The problem with the simple form of RPF is that
			group membership is not taken into account when
			building the tree and packets are simply
			flooded to the whole network.

		\subsection{RPF and Prunes} 

			\hspace*{8mm} The ``pruning'' idea is to
			complete the basic RPF by memorizing the group
			membership and to forward a packet only if
			there is a group member down the tree. This
			will result in minimal trees but requires very
			dynamic updates. When a multicast transmission
			starts from source $S$, the first packet is
			propagated to all the network nodes. This is
			the flooding.  The leaf nodes will all receive
			the first multicast packet. If there is a group
			member attached to the leaf node, everything is
			fine, but if there is no group member the node
			does not want to receive further packets. It
			will thus send back a ``prune message'' to the
			node that sent it this packet: don't send
			further packets from source $S$ to group $G$ on
			this interface $I$.

			The intermediate nodes that receive the prunes
			memorize them. If they have received a prune
			message through all the interfaces on which
			they forwarded the first packet and if there is
			no local recipient, they have no need for
			receiving from this source further packets for
			that group.  They will forward the prune
			command up the RPF tree. Eventually, the tree
			will include only the branches that lead to
			active recipients.

			There are two obvious drawbacks in the flood 
			and prune algorithm:
			\begin{enumerate}
			\item  The first packet is flooded to the whole network.
			\item  The nodes must keep states per group and source.
			\end{enumerate}

		\subsection{Steiner Trees} 

			\hspace*{8mm} Given a connected, weighted graph
			$G=(V, E)$, where $V$ is the vertex set and $E$
			the edge set, also given a subset $M$ of $V$,
			we can find more than one subgraph $S=(V', E')$
			of $G$ such that $M \subseteq V'$ and there is
			a path in $S$ between every pair of nodes in
			$M$. $S$ is defined to be a Steiner Graph. The Steiner
			Tree problem in a graph is to find a Steiner Graph $T$
			such that the sum of edge weights in $T$ is the
			minimum.

			If we forward a packet along a Steiner Tree
			that connects the multicast destination nodes
			and the source node, the communication cost
			will be the minimum. This will eventually help
			reduce the packet delay and increase the
			throughput.

			Since the Steiner Tree problem is NP-complete
			\cite{HWANG}, no polynomial time algorithms for
			this problem exist. Many heuristics have been
			developed, and Table \ref{Steiner} \cite{HWANG}
			gives a listing of existing heuristic solutions
			to the Steiner Tree problem in a graph.

{
\baselineskip=13pt 
\begin{table}
\begin{center}
\begin{tabular}{|l|l|c|c|}  \hline \hline
Method & Submethod & Acronym & Complexity \\  \hline \hline
Path heuristics & shortest paths & SPH & $O(n(e+v\log v))$ \\ \cline{2-4}
  & repetitive  & SPH-N & $O(n^2v^2)$   \\ \cline{3-4}
  &             & SPH-V & $O(nv^3)$     \\ \cline{3-4}
  &             & SPH-zN & $O(n^2v^2)$  \\ \cline{3-4}
  &             & SPH-NN & $O(n^3v^2)$  \\ \cline{2-4}
  & with origin & SPOH & $O(e+v\log v)$ \\ \cline{2-4}
  & Kruskal     & KBH & $O(nv^2)$       \\ \cline{2-4}
  & Y           & YH & $O(n^2e\log v)$  \\ \hline
Tree heuristics & MST & MSTH & $O(e+v\log v)$ \\ \cline{2-4}
  & greedy           & GTH  & $O((v-n)^2v+n^2)$   \\ \cline{2-4}
  & distance network & DNH  & $O(e+v\log v)$      \\ \cline{2-4}
  & repetitive       & RDNH & $O((v-n)^qn^2+v^3)$ \\ \cline{2-4}
  & multiple         & MDNH & $O(ev+v^2\log v)$   \\ \cline{2-4}
  & simulated annealing & SAH &    \\ \cline{2-4}
  & hill climing     & HCH &   \\ \hline
Vertex heuristics & average distance & ADH & $O(v^3)$ \\ \cline{2-4}
  & fast       & FADH & $O(v^3)$        \\ \cline{2-4}
  & restricted & RADH & $O(n^2e\log v)$ \\ \cline{2-4}
  & median     & MH   & $O((v-n)v^2)$   \\ \cline{2-4}
  & antimedian & AMH  & $O((v-n)v^2)$   \\ \cline{2-4}
  & upgrading  & UH   & $O(v^3+vn^3)$   \\ \cline{2-4}
  & modified upgrading & MDH &   \\ \hline
Contraction  &  & CH  & $O(v^3)$ \\ \hline
Dual Accent  &  & DAH &          \\ \hline
Set Covering &  & SCH &          \\ \hline \hline
\end{tabular}
\end{center}
\caption{Steiner Tree Heuristics [8]} \label{Steiner}
\end{table}
}

		\subsection{Flow Model and Optimal Routing} 

			\hspace{8mm} The shortest path algorithm is a
			greedy algorithm because it puts all the
			traffic between a source-destination pair on
			the single shortest path. Optimal routing tries
			to build a precise model for overall optimality
			and solve a nonlinear optimization problem,
			i.e., the traffic is distributed among all
			possible paths between the pair. In this
			subsection, we will first describe the model
			for unicasting and then introduce the model for
			multicasting.

			\paragraph{Unicasting Flow Model.}  
				Let $F_{ij}$ be the traffic arrival
				rate at link $(i,j)$. $F_{ij}$ is
				called the flow of link $(i,j)$.

				Let the cost function for optimization
				be \[D = \sum_{(i,j)}D_{ij}(F_{ij})
				\hsp{0.2in} D_{ij}(F_{ij}) =
				\frac{F_{ij}}{C_{ij}-F_{ij}}+d_{ij}F_{ij}\]
				\noindent where $C_{ij}$ is the link
				capacity of $(i,j)$.

				Denote $\omega(k,l)$ to be a
				source-destination pair (SD pair) from
				node $k$ to node $l$, let $r_\omega$ be
				the input arrival rate entering $k$ and
				destined for $l$. Let $P_\omega$ be the
				set of paths connecting $k$ and $l$,
				and $x_p$ be the flow of a path $p$.
				Then for link $(i,j)$ \[F_{ij} =
				\sum_{p\;{\rm containing}\;(i,j)} x_p\]
				The optimization problem is defined as
				\[ {\rm minimize} \;\;
				\sum_{i,j}D_{ij}(F_{ij})\] \[ {\rm
				subject\; to}\;\; \sum_{p\in P_\omega}
				x_p = r_\omega, \;\; x_p \geq 0 \] The
				solution is the specification of
				traffic flow to each path. The major
				problem is that an analytical solution
				to the problem does not exist in most
				cases. Several iterative algorithms had
				been developed and are covered very
				thoroughly in \cite{BERTSEKAS}.

			\paragraph{Multicasting Flow Model.}  
				Stassinoponlos and Kazartzakis give a
				model for the multidestination optimal
				dynamic routing problem in
				\cite{STASSINOPOULOS} and
				\cite{STASSINOPOULOSa}. Their
				algorithms are based on the maximal
				flow-minimal cut
				theorem\cite{SEDGEWICK} and solve the
				problem by an iterative link-by-link
				optimization method. The following is
				the model:

				Let $N$ be the set of nodes, $M
				\subseteq N$ is the set of destination
				nodes, and $L$ is the set of directed
				links $(p,q),\; p, q \in N$. Link
				$(p,q)$ has the capacity $ C_{pq} >
				0$.  If $i=(j,k)$ is an
				source-destination pair  with $j\in
				N,\; k\in M-\{j\}$, we let $x_i$ and
				$r_i$ denote the initial traffic and
				external arrival rate at node $j$
				destined for node $k$. The set $I$
				comprises all source-destination pairs
				$i$ for which $x_i$ or $r_i$ is
				nonzero. Each link $(p, q) \in L$ can
				serve traffic belonging only to some
				source-destination pairs in general. We
				denote by $I_{pq}$ to be the set of all pairs
				in $I$ for which there is an path from
				the source to the destination node
				passing through link $(p,q)$.

				For each $i\in I$, define a nonnegative
				capacity allocation function
				$\xi_i(\cdot,\cdot)$ where domain is
				the set of links $L$, i.e.,
               			\[\xi_i(\cdot,\cdot):\; L \rightarrow R\]
               			\[(p,q) \rightarrow \xi_i(p,q)\]
				the capacity allocated for each
				source-destination pair over the whole
				network is given by the family
				$\{\xi_i(\cdot,\cdot)\}_{ i\in I}$
				which must satisfy
  				\[ \sum_{i \in I_{pq}} \xi_i (p,q) = C_{pq}, 
					\;\; \forall (p,q) \in L \] 
  				\[ \xi_i(p,q)=0,\;\;  i \not\in I_{pq} \]
				For each $i\in I$ we say that the
				subset $A_i \subset N$ is a cut if
				$A_i$ contains the source and $N - A_i$
				contains the destination node.

				We let ${\bf A}_i$ be the family of all
				possible cuts $A_i$. For each $i \in I$
				the external arrival rate $r_i$ can be
				served if and only if
				\[\sum_{(p,q) \in A_i} \xi_i(p,q)-r_i 
				\geq 0, \forall A_i \in {\bf A}_i\] 
				Our problem is the minimization of
				\[\max_{i\in I} \left\{ \max_{A_i \in 
				{\bf A}_i} \left\{ x_i \left(\sum_{(p,q)
				\in A_i} \xi_i(p,q)-r_i\right)^{-1} \; 
				\right\} \right\} \]
				and to maximize
				\[\min_{i\in I} \left\{ \min_{A_i \in 
				{\bf A}_i} \left\{ x_i^{-1} \sum_{(p,q)
				\in A_i} \xi_i(p,q)-r_i \; \right\} 
				\right\} \]
				The determination of the flow on a
				single link requires an $O(|n|^6)$ time
				complexity per iteration for a network
				of $n$ nodes, based on this model and
				the solution given
				in~\cite{STASSINOPOULOSa}.

		\subsection{Related Algorithms for Multicast}

			\hspace*{8mm} In this subsection, we briefly
			introduce several earlier algorithms and then
			pay more attention to the link state algorithms
			by Deering\cite{DEERING} which are relatively
			new and have been experimented with on the
			Internet.  First we will give some detailed
			description of Deering's algorithms. This will
			help understand the assumptions made in our
			proposed algorithm presented in Chapter 3.  The
			details are also necessary because we will
			simulate one of Deering's algorithms and
			compare it with our algorithm in Chapter 4.

			Aguilar\cite{AGUILAR} proposed a algorithm for
			internet multicast routing which makes use of
			the IP (Internet Protocol) header for the
			destination address. The maximum size of an IP
			header is 60 bytes, of which 20 are used for
			identification and control information,
			including 4 for an internet destination
			address.  The other 40 bytes can be used for
			options. These 40 bytes can be used for the
			internet addresses of multiple destinations.
			Since each address uses 4 bytes, with 8 bytes
			for control information, eight destination
			addresses can be included; this together with
			the already existing IP destination  gives us 9
			possible addresses. The routing follows
			``shortest'' paths and the algorithm places all
			its destination addresses in an Internet
			packet. During propagation, the packet is
			replicated at gateways and the address list is
			partitioned among the newly created packets,
			according to their next Internet stop. This
			scheme's advantage is that it can be done
			without additional protocol information and no
			changes to the subnetwork routing.  It can be
			deployed in an internet regardless of the
			subnetworks transmission mode and regardless of
			whether the subnets have or do not have
			multicast capacity. The drawback for this
			algorithm is that it limits the size of the
			multicast destinations to only 9.

			Belkeir and Ahamad\cite{BELKEIR} proposed two
			heuristic algorithms in dynamic multicast which
			update the multicast tree incrementally as the
			membership changes and reduce the total
			bandwidth required for sending data and control
			messages. These two algorithms are Restricted
			Broadcast Algorithm (RBA) and Nearest-Insertion
			Algorithm~(NIA).

			Restricted Broadcast Algorithm (RB) is a
			broadcast-tree based algorithm. The idea is to
			construct a multicast tree for each multicast
			group as the sub-tree of a minimal cost
			broadcast spanning tree. This type of multicast
			tree can be computed in polynomial time.  The
			broadcast tree is constructed once and used as
			the basic structure to support message delivery
			for all multicast groups. Furthermore, when the
			membership of the group changes, the algorithm
			is executed by a node to update the multicast
			tree incrementally.

			In Nearest-Insertion Algorithm (NI), when a
			multicast tree needs to be extended (when a new
			member joins the group), all links in the
			broadcast tree should be considered as
			potential candidates to be added to the
			multicast tree. The algorithm considers all
			nodes and links, and chooses the ones that are
			on the path to a participant node in the group
			which is nearest to the new member.

			The advantage of the RB and NI algorithm is
			that they have no disruption of the multicast
			tree since the trees are incrementally updated
			without reconstruction. The problem is the
			broadcast tree is fixed, not dynamic, which
			does not respond to the change of traffic in
			the network, and the maintenance of a separate
			multicast tree is still required for each
			source-group pair.

			Early in 1983, Bharath-Kumar and
			Jaffe\cite{BHARATH} studied several heuristic
			algorithms for multicast routing and evaluated
			their performance.  These algorithms are
			Minimum Spanning Tree (MST), Minimum
			Destination Cost (MINDC), Nearby Heuristic 1
			(NH1), Nearby Heuristic 2 (NH2), and Nearest
			Neighbor Heuristic (NN).

			A minimum spanning tree for the ``induced
			graph'' (also called distance
			graph\cite{HWANG}), $I(G)$, of the given graph
			$G$ is constructed and used for multicast. The
			algorithm is as follows:

			Given network graph $G$, source node $s$, and
			destination node set $D$, with $|D| = m$, we
			define $I(G)$ to be the complete graph on $m+1$
			nodes (one node s and one for each $d \in D$)
			with cost {\em sd}$(i, j)$ associated with edge
			$(i,j)$ where {\em sd}$(i,j)$ is the shortest
			distance from $i$ to $j$ in $G$. The algorithm
			executes following steps:

			1) Determine {\em sd}$(i,j)$ for every $i,j 
				\in \{s\} \cup D$.

			2) Construct $I(G)$.

			3) Determine the Minimal Spanning Tree $T$ 
			for $I(G)$, and route according to $T$ as follows: 

			\begin{list}{}{\setlength{\leftmargin}{20mm}
			               \setlength{\rightmargin}{0mm}}
				\item[a)] For each neighbor of $s$ in $T$, $s$
				sends a copy of the message. Node $s$
				includes in each message the portion of
				$T$ rooted at that neighbor.

				\item[b)] Each node receiving such a message
				sends out copies if it is not a leaf of
				the tree, using the same distribution
				algorithm as the source.
			\end{list}

			MINDC uses local information, which is defined
			to be the shortest path information from the
			source to all destinations.  This algorithm is
			to choose the  routing that minimizes DC, i.e.,
			the message is sent from the source to each
			destination node on its shortest path routes.

			Both  NH1 and NH2 algorithms require nearby
			information defined as the shortest path tables
			of the neighbors of the source node as well.
			In  NH1, the source node uses all information
			available to its neighbors as follows. Assume
			that $s$ were to bifurcate to neighbors $n_1,\;
			n_2$, and $n_3$. Assume further that $s$ routes
			to a set of destinations $D_i$ through $n_i$
			with $D_i \cap D_j = \emptyset$ for $i \not=j$
			and $\cup_i D_i = D$.  Then the local cost of
			the routing is the sum of the costs of the
			three links, connecting $s$ to $n_1$, $n_2$,
			and $n_3$. The estimated global cost is
			$\sum_{(i=1)}^3$(sum of costs from $n_i$ to
			each node in $D_i$).

			Algorithm NH1 routes from $s$ to its neighbors
			by choosing the routing that has the smallest
			total estimated cost. Once this is done,
			intermediate nodes choose their next nodes in
			the same way.  One of major problem with 
                        NH1 is that it  has to consider all $2^m$
			partitions of $D$, giving an exponential time
			complexity.

			In NH2, the algorithm investigates the
			possibility of using the neighbors one by one.
			The destination $d$ closest to $s$ is chosen,
			and the neighbor $n_1$ which lies on the
			shortest path from $s$ is investigated.  For
			each $d' \in D$, if the least cost path from
			$n_1$ to $d'$ is smaller than that from $s$ to
			$d'$, $d'$ is assigned to $n_1$. After every
			$d' \in D$ is examined, if any are left
			unassigned, the one that is closest is chosen
			next. Let $n_2$ be the neighbor on the shortest
			path from $s$ to it. We now attempt to assign
			the remaining destinations to $n_2$ as above.
			The procedure continues until all destinations
			are assigned to neighbors of $s$. A copy of the
			message to be routed is sent to these
			neighbors. Then, the analogous procedure is
			used at each of these nodes.

			In NN algorithm, each node $I$ that has
			responsibility to route to a certain
			destination sends the message on the shortest
			path to the destination nearest to $I$. Also,
			responsibility for all other destinations are
			transferred to that destination.

			Deering\cite{DEERING} implemented, among
			others, two algorithms based on link-state (LS)
			routing: LS Truncated-Broadcast Routing and LS
			Multicast Routing. As mentioned previously, we
			will give more details for these two
			algorithms.  We first introduce a protocol
			called ``Host Membership Protocol'' which is
			the basis of the multicast in~\cite{DEERING},
			then describe basic LS routing and the two
			algorithms introduced by Deering.

			\paragraph{The Host Membership Protocol.} 
				This protocol provides information for
				routers so that routers can learn which
				host groups are present on their
				directly-attached subnetworks. The
				protocol enables every router attached
				to a subnetwork to learn which host
				groups are present on the subnetwork,
				when the router starts up; to detect
				when a new host group appears on the
				subnetwork; and to detect when a host
				group disappears from the subnetwork.

				The Host Membership Protocol is based
				on a simple query-response scheme.  On
				each subnetwork, one of the attached
				routers is elected as the
				interrogator.  The interrogator
				periodically multicasts a host
				membership query packet to the
				subnetwork, the query packet is sent to
				the all-hosts group, whose scope is
				local to the subnetwork, and to which
				all hosts belong.

				For each group that is present on the
				subnetwork, one member host responds to
				the query by multicasting a host
				membership report packet. The report
				packet is addressed to the group that
				is being reported, and is sent with a
				maximum hop-limit of one. This results
				in delivery to all other members of
				that group on the same subnetwork, plus
				all attached routers. The report serves
				two purposes: it tells the routers that
				the group is present, and it tells the
				other members not to report the group.
				The routers conclude that a group is no
				longer present when no report is
				received for the group after a small
				number of queries. This protocol
				comprises two algorithms: the Host
				algorithm and the Router algorithm.

				The host algorithm operates on abstract
				objects called ``membership''; a
				membership $m$ has the following
				attributes:

				{\small
				\begin{center}
				\begin{tabular}{ll}
				  $m$.group  & host group address \\
				  $m$.subnet & attached subnetwork identifier \\
				  $m$.timer  & retransmission/delay timer \\
				  $m$.count  & retransmission counter 
				\end{tabular}
				\end{center}
				}

				\noindent
				Whenever an upper-layer protocol
				invokes the JoinGroup operation, a new
				membership is created. This informs the
				routers of the group's presence, in
				case there were no previous members
				present on the subnetwork---the sooner
				the routers learn of the group, the
				sooner they are able to forward
				multicast packets destined to the group
				onto the subnetwork, thus minimizing
				join latency.  When an upper-layer
				protocol invokes the LeaveGroup
				operation, the corresponding membership
				is deleted.  When a host receives a
				host membership query, it does not
				respond immediately. Instead, for each
				group to which it belongs on the
				subnetwork and whose scope is wider
				than the subnetwork, it sets its
				membership's timer to a random delay
				value between zero and some maximum
				delay $T_d$; a separate random delay is
				chosen for each group.  When a
				membership's timer expires, a
				corresponding host membership report is
				transmitted.

				Whenever a host membership report is
				received, if the host belongs to the
				reported group, it stops its timer for
				that group and abstains from sending
				its own report.

				The router algorithm operates on two
				types of object. A ``group presence''
				object $p$ has the following
				attributes:

				{\small
				\begin{center}
				\begin{tabular}{ll}
				  $p$.group     & host group address  \\
				  $p$.subnet    & attached subnetwork 
						identifier  \\
				  $p$.time-left & time left until group 
					is assumed absent
				\end{tabular}
				\end{center}
				}

				\noindent 
				and an ``attached subnetwork'' object
				$k$ has the following attributes:

				{\small
				\begin{center}
				\begin{tabular}{ll}
				   $k$.interrogator &  true if this router 
						is interrogator for $k$ \\
				   $k$.timer        &  retransmission/query 
						timer \\
				   $k$.count        &  retransmission counter
				\end{tabular}
				\end{center}
				}

				\noindent 
				The $k$.interrogator Boolean is set by
				an interrogator election algorithm.

				When a router starts up, it immediately
				sends $N$ queries at intervals of
				$T_n$, so that it may quickly learn
				what groups are present without waiting
				for the interrogator to issue the next
				periodic query. After the initial $N$
				transmissions, if the router has been
				elected interrogator, it proceeds to
				send periodic queries at intervals of
				$T_q$, until it fails or resigns as
				interrogator.

				Whenever a router receives a host
				membership report from a particular
				group on a subnetwork, it resets the
				time-left for that group to a value
				$T_p$. If a group's time-left expires,
				the router concludes that the group is
				no longer present on the subnetwork and
				deletes its record.

			\paragraph{Link-State Routing.} 
				Under the link-state routing algorithm,
				every router monitors the state of each
				of its incident links or subnetworks.
				The state of a subnetwork includes
				whether or not the subnetwork is
				operational, the set of neighboring
				routers reachable across the
				subnetwork, and in some cases, a
				measure of the traffic load on the
				subnetwork. Whenever the state of a
				subnetwork changes, the routers
				attached to that subnetwork broadcast
				the new state to every other router in
				the internetwork. The broadcast may be
				accomplished by a special-purpose,
				high-priority flooding protocol that
				ensures that every router quickly and
				reliably learns the new state. All
				routers know the state of all
				subnetworks and all routers, from which
				they can each determine the complete
				topology of the internetwork. Each
				router independently computes the
				shortest paths from itself to every
				possible destination, using Dijkstra's
				algorithm.

			\paragraph{LS Truncated-Broadcast Routing.}  
				Given the complete topological
				knowledge available in every LS router,
				any router can directly compute the
				shortest-path broadcast tree rooted at
				any particular source $s$, using
				Dijkstra's algorithm.  The router can
				also identify from the tree
				computation, which of its child
				subnetworks are leaf subnetworks in the
				broadcast tree for $s$.

				The LS truncated-broadcast algorithm is
				shown in table \ref{lstb}.  This
				algorithm operates on ``route''
				objects, which are the entries in the
				LS routing table; a route object $r$
				has the following attributes of
				relevance to this algorithm:

				{\small
				\begin{center}
				\begin{tabular}{ll}
				   $r$.destination &  internetwork 
					destination address \\
				   $r$.parent      &  parent subnetwork, 
					for broadcasts from destination \\
				   $r$.child$[k]$  &  child flags, per 
					attached subnetwork $k$ \\
				   $r$.leaf$[k]$   &  leaf flags, per 
					attached subnetwork $k$
				\end{tabular}
				\end{center}
				}

				\noindent 
				The algorithm also operates on the
				``group presence'' and ``attached
				subnetwork'' objects described earlier
				except that each attached subnetwork
				$k$ has one additional attribute:
				\begin{center}
				$k$.designated: true if this router is
				LS designated router for subnetwork
				$k$.
				\end{center}

				{\small
				\begin{table*}
				\begin{center}
				\begin{tabular}{|l|} 
				\hline
				1. on change of designated router on
				subnetwork $k$: \\ 
				\hsp{0.3in}$k$.interrogator
				$=k$.designated \\
				2. on change of topology: \\ 
				\hsp{0.3in}for each route $r$,
				$r$.parent $=$ undefined \\
				3. on receipt of multicast packet from
				$s$ to $g$ via subnetwork $k$: \\
				\hsp{0.3in}if $\exists$ route $r$ such
				that $r$.destination $= s$ \\
				\hsp{0.6in}    if $r$.parent $=$ undefined,  
					$<$compute $r$.parent, $r$.child, 
					$r$.leaf $>$ \\
				\hsp{0.6in}    if $r$.parent $=k$ \\
				\hsp{0.9in} for each subnetwork $j$ \\
				\hsp{1.2in} if $r$.child$[j]$ and 
					(( not r.leaf$[j]$) or 
                      			($\exists$ group presence $p$ \ \\
				\hsp{1.5in} such that $p$.group$=g$ and 
					$p$.subnet$=j$)) \\
				\hsp{1.8in} send copy of packet on 
					subnetwork $j$ \\
				\hline
				\end{tabular}
				\end{center}
				\caption{LS Truncated Broadcast} \label{lstb}
				\end{table*}
				}

				In Table \ref{lstb}, each numbered item is
				called an event. There are three events
				in this algorithm, as described below.

				\noindent 
				{\bf Event 1.} The election of a
				designated router  to serve as a
				membership interrogator is required by
				the Host Membership Protocol.

				\noindent
				{\bf Event 2.} On any change of
				topology, the LS routing algorithm
				recomputes its entire routing table.

				\noindent
				{\bf Event 3.} Delivery of multicast
				packets by truncated-broadcast. The
				source of an incoming multicast packet
				is looked up in the routing table. If
				the route entry contains an undefined
				parent value, that indicates  that this
				is the first multicast packet from that
				particular source since the last
				topology change; in that case, the
				parent, child, and leaf fields are
				computed. The router then checks that
				the packet arrived on the correct
				parent subnetwork for its source and,
				if so, forwards it on all child
				networks that are not leaf subnetworks
				or that have members of the destination
				group, which is the normal
				truncated-broadcast forwarding
				procedure.  The determination of the
				parent, child, and leaf values for a
				route entry entails the execution of
				Dijkstra's algorithm to compute the
				shortest-path broadcast tree rooted at
				the source. 

                                The algorithm works by
				starting with a node for the root, and
				iteratively adding all other nodes to
				the tree, nearest nodes first. When the
				router adds a descendent subnetwork
				node to its own node, it sets the child
				and leaf flags for that subnetwork,
				when the router adds a descendent
				router node to one of those child
				subnetwork nodes, it clears the leaf
				flag for that subnetwork. When all the
				nodes have been added to the tree, the
				child and leaf information is
				complete.

			\paragraph{LS Multicasting Routing.}  
				This algorithm is an extension of the
				LS truncated-broadcast algorithm. The
				main idea behind this algorithm is to
				consider the set of groups present on a
				subnetwork to be part of the state of
				that subnetwork. Whenever the set of
				groups changes, as with any other state
				change, the designated router for that
				subnetwork floods a link-state update
				message to all other routers, reporting
				the change. All routers end up with
				complete and consistent knowledge of
				which groups are present on which
				subnetworks.

				The LS multicast algorithm is shown in
				Table \ref{lsmulti}.  The algorithm
				operates on ``cache record'' objects
				that hold the information required to
				forward multicast packets. A cache
				record $c$ has the following
				attributes:

{\small
\begin{center}
\begin{tabular}{ll}
$c$.source        & source of multicast packet \\
$c$.group         & destination of multicast packets \\
$c$.parent        & parent subnetwork, for multicast from $c$.source \\
$c$.min-hops$[k]$ & min hops to $c$.group, per attached subnetwork $k$ \\
\end{tabular}
\end{center}
}


				{\small
				\begin{table}
				\begin{center}
				\begin{tabular}{|l|}  \hline
				1. on change of designated router on 
					subnetwork $k$: \\
					\hsp{0.4in}$k$.interrogator 
					$=k$.designated \\
				2. on appearance of disappearance of group 
					$g$ on subnetwork $k$: \\
					\hsp{0.4in}if $k$.designated \\
					\hsp{0.8in}   flood link-state 
					update, reporting change of $g$ on 
					$k$ \\
				3. on generation or receipt of link state 
					update, reporting change of $g$: \\
					\hsp{0.4in}for each cache record $c$ 
					such that $c$.group $=g$ \\
					\hsp{0.8in}   discard $c$ \\
				4. on change of topology: \\
					\hsp{0.4in}for each cache record $c$ \\
					\hsp{0.8in}    discard $c$ \\
				5. on receipt of multicast packet from 
					source $s$ to group $g$ via 
					subnetwork $k$, \\
					\hsp{0.4in}with remaining hop 
					limit {\em hl}: \\
					\hsp{0.4in}if $\exists$ no cache 
					record $c$ such that $c$.source 
					$=s$ and $c$.group $= g$ \\
					\hsp{0.8in}   create cache record 
					$c$; $c$.source $=s$; $c$.group 
					$=g$ \\
					\hsp{0.8in} $<$compute $c$.parent 
					and $c$.min hops attributes$>$ \\
					\hsp{0.8in} if $c$.parent $= k$ \\
					\hsp{1.2in} {\em hl} = {\em hl} - 1 \\
					\hsp{1.2in} for each subnetwork $j$ \\
					\hsp{1.6in} if hl $\geq$ 
						min-hops$[j]$ \\
					\hsp{2.0in} send copy of packet 
						on subnetwork $j$ \\
				\hline
				\end{tabular}
				\end{center}
				\caption{LS Multicast} \label{lsmulti}
				\end{table}
				}

				The algorithm also operates on
				``attached subnetwork'' objects as
				defined for the router part of the Host
				Membership Protocol, except that each
				attached subnetwork $k$ has one
				additional attribute:

				\begin{center}
				$k$.designated: true if this router is LS 
				designated router for subnetwork $k$
				\end{center}

				\noi Similar to LS Truncated algorithm, this    
				algorithm defines five events as follows.

				\noindent 
				{\bf Event 1.} The election of a
				designated router serves as an
				membership interrogator, as required by
				the Host Membership Protocol.

				\noindent
				{\bf Event 2.} Whenever the procedure
				for the Host Membership Protocol
				detects the appearance of a new group
				on an attached subnetwork or the
				disappearance of a previously present
				group, if the router is the LS
				designated router for that subnetwork,
				it invokes the LS protocol procedures
				to flood a link-state update, reporting
				the change.

				\noindent
				{\bf Event 3.} When a link-state update
				for a group is generated by the
				procedure for event 2 or received from
				another router, all cache records
				referring to that group are discarded.

				\noindent
				{\bf Event 4.} Similar to event 3,
				whenever there is a topology change,
				all cache records are discarded.

				\noindent
				{\bf Event 5.} Multicast packet from
				source $s$ to group $g$. Look up the
				cache record for that (source, group)
				pair; if there is no such record,
				create one and compute its parent and
				min-hops attributes. Then if the cache
				records shows that the packet arrived
				via the correct parent subnetwork,
				decrement the hop limit and forward a
				packet to each child subnetwork which
				leads to a group member within the
				remaining hop limit. A child subnetwork
				$k$ is indicated by a finite value of
				min-hops$[k]$ which is the distance to
				the nearest group member via $k$ in the
				delivery tree.

