\chapter{The Proposed Algorithm}  

	\hsp{8mm} In this chapter we propose an algorithm for datagram
	multicast routing which we call {\em Minimum Average Distance}
        algorithm.  We first give a brief description of the
	main issues which we need to address. Then we give a formal
	description of our algorithm and a simple example to explain
	the algorithm.

	\section{Main Issues in Internetwork Multicast}

		\hsp{8mm} For clarity, we will restate here some of the
		concepts previously introduced.  In internetworks,
		multicast packets are delivered to each member of a
		multicast group. A multicast group is a set of
		destination nodes to which a message needs to be
		delivered. Each destination node is a {\em member} of
		the group.  For each source there can be many different
		destination groups. For up-layer users, they need only
		know the group address, not the group member addresses.
		This is the ``unknown-destination'' delivery feature.
		It is the router that takes the burden of addressing 
                the message to group members.

		We assume that the subnetwork supports multicast (most
		local-area networks  have the ability to address and
		deliver a packet to a set of destinations.) Based on
		this assumption, we omit the detail of a subnetwork and
		treat each router as a node. In this context, we use
		node and router interchangeably.

		A multicast group may be of arbitrary size, the
		membership of a multicast group may change dynamically,
		and the members of a group may be located anywhere in
		the internetwork.

		We use the datagram model (or connectionless model) for
		our multicasting. Each packet doesn't carry the
		multiple destination addresses, each router maintains a
		routing table for all nodes, and each routing table
		entry records the shortest path and the first-hop node
		for each destination. Each router can determine the
		complete topology of the internetwork and can
		independently compute the shortest paths from itself to
		every possible destination. We also assume that routers
		maintain the group-member information which ensure that
		every router knows the membership of a group. When a
		packet arrives at a router, the router can
		independently decide whether there is any member in its
		attached subnetwork to which the packet will be
		forwarded.

		We assign each link a state which includes the length
		of the link, the membership of a group, and whether the
		link has been disconnected or is reconnected. Whenever
		a link state changes, we assume that there is a
		designated router which broadcasts the new state to
		every other router in the internetwork and that all routers
		will quickly and reliably update their state database
		corresponding to the new state.

		For a dynamic multicast routing algorithm, some basic
		requirements should be considered:

		1) The algorithm should be computationally efficient:
		an algorithm is hardly useful if it requires  more than
		a linear time to determine to which link a packet is to
		be sent.  A constant time complexity is preferred.

		2) The algorithm should be scalable: it should not
		heavily dependent on network size, group size, etc.

		3) The algorithm should be compatible with unicast
		routing: it should not require excessive information
		compared with unicast routing, and should not change
		dramatically from unicast environment.

		4) The algorithm should seek a minimization of delay
		and traffic: these two goals may or may not conflict
		with each other. A minimum cost tree may require
		packets to reach some member host along a non-shortest
		path. But when the minimum cost tree is utilized, the
		entire traffic is reduced, which may help reduce the
		delay.

		Another important issue is that of the low-delay and
		low-cost routing.  Low-delay routing is to minimize the
		path length from the source to every destination node.
		It usually requires the message to be sent to every
		destination along the shortest path or its equivalent
		as in unicast routing. Each link is assigned a length
		which can simply be 1 or the recent traffic rate or
		queue length on the link. The link length from two
		opposite directions can be different. Low-cost routing
		is to minimize the total traffic, which is equivalent
		to the total  length of the paths in a delivery tree.
		In graph-theoretic terms, a minimum delay routing
		corresponds to a shortest-path tree, while a
		minimum-cost routing corresponds to a Minimum Steiner
		Tree in a graph. Finding a Minimum Steiner Tree is an  
                NP-complete
		problem. There exist some heuristic algorithms for
		computing low-cost multicast tree, as listed in Chapter
		2, but they either suffer from high computational cost
		or are not suitable for the datagram environment.

		Our algorithm focuses on low-cost multicasting. This
		algorithm's computational complexity is only linear in
		the group size. In chapter 4, the simulation result
		shows that the performance of this algorithm is
		sufficiently satisfactory.

		The main idea behind this algorithm is that we use the
		{\em minimum average distance} method to select the
		forwarding links. When a packet arrives at a node, the
		algorithm computes the average distance for each
		neighbor of the current node, where the {\em average
		distance} is the average distance from the neighbor
		node to all nodes in its {\em responsible destination
		set}. Then we select the neighbor node which has the
		minimum average distance to forward the packet.  This
		procedure continues until all destination members are
		processed.  A simple example presented in Section 3.3 will
		demonstrate the operation of the algorithm.  Another
		important feature of this algorithm  is that we do not
		construct the delivery tree at all.  It uses the
		routing tables of neighbor nodes to compute the next
		node to which the packet will be forwarded, this saves
		memory and computation time.

	\section{Algorithm Description}

		\hsp{8mm} First, we give the definitions for the following
		variables which will be used in the algorithm
		description.

		\noi
		\hsp{.2in} $G$: The destination set, that is, a group. \\
		\hsp{.2in} $G_i$: Node $i$'s responsible destination set. \\
		\hsp{.2in} $N_i$: Node $i$'s open neighborhood set, i.e., 
			all of node $i$'s neighbor nodes except \\
		\hsp{.55in} for node $i$ itself. \\
		\hsp{.2in} $D_j$: Neighbor $j$'s responsible destination set. \\
		\hsp{.2in} $L_j$: Average length from the neighbor node 
			$j$ to its responsible destination set. \\
		\hsp{.2in} $A_i$: The assigned neighbor set. \\
		\hsp{.2in} $d_{ij}$: The shortest path distance from node 
			$i$ to node $j$. 


		\noi We also define the routing table at each node 
		with entries as:

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

		\noindent 
		where ``next hop'' is used in the shortest path
		algorithm for both unicasting and multicasting. Next
		hop tells which link to take to reach the destination
		on the shortest path from the current node. We do not
		use next hop directly, but compute the next hop based
		on our algorithm. Following is the description of the
		algorithm:

		\noi 
		1. A packet $p$ addressed to group $G$ is now at node
		$i$:\\ \hsp{.2in} if $i$ is the source node then
		$p$.radius = $\infty$; $A_i = \emptyset$;\\ \hsp{.2in}
		else $\;p$.radius = $R$, where $R$ is a radius which is
		carried with $p$.\\ \hsp{.525in} $A_i$ = $\{k\}$, where
		$p$ is from neighbor $k$ of node $i$.\\ \hsp{.2in} if
		$p$.radius = 0 \ \ then stop.

		\noi 
		2. Compute node $i$'s responsible set
		\begin{equation}
		G_i = \{ g|g\in G,\ {\rm and}\  d_{ig} \leq p.radius,\ 
		{\rm and}\ g\neq i\} \label{one}
		\end{equation}

		\noi 
		3. For each $j \in N_i$ and $j \not\in A_i$, compute
		$j$'s destination set
		\begin{equation}
		D_j = \{g | g \in G_i,\ {\rm and}\  d_{jg} < d_{ig} \}    
		\label{two}
		\end{equation}

		\noi 
		\hsp{.2in} and the average length
		\begin{equation}
		L_j = (d_{ij} + \sum_{g \in D_j} d_{jg} - \hat{L}_j ) /|D_j| 
		\label{three}
		\end{equation}

		\noi 
		\hsp{.2in} where $\hat{L}_j$ is the sum of the 
		overlapped next-hop link, defined as
		\[ \hat{L}_j = \sum_{n_{jk} > 1} (n_{jk}-1) l_{jk}\] 

		\noi 
		\hsp{.2in} where $n_{jk}$ is the number of members in 
		$D_j$ that will be sent via link $k$ from \\ \hsp{.2in} 
		node $j$, and $l_{jk}$ is the length of the link. \\
		\hsp{.2in} if (all $D_j = \emptyset$) or ($N_i = A_i$), 
		stop.

		\noi 
		4.  Let $J$ be the subscript such that 
		\[L_J=\min_{j\in N_i, j\not\in A_i} L_j\]
		\hsp{0.2in} and
		\begin{equation}
		     R = \max_{g\in D_J} d_{Jg}         \label{four}
		\end{equation}
		\hsp{.2in}   send a packet with radius $R$ to node $J$.
     
		\noi 
		5. $G_i = G_i - D_J \ \ \  A_i = A_i \cup \{J\}$ \\
		\hsp{.2in}  if $G_i = \emptyset$, \ \ \  stop \\
		\hsp{.2in}  else loop back to step 3. 
     
		\noi 
		When a packet arrives at a node $i$ and is addressed to
		group $G$, we give a condition to limit the size of the
		destination set; that is, to decide to which members of
		group $G$ should be sent the packet from the current
		node $i$. We use a variable $p$.radius as the
		condition. The value of $p$.radius is the path distance
		between the current node and the remotest destination
		member. That is, the current node $i$ only sends
		packets to those members (in $G_i$) whose shortest path
		distance from node $i$ to them is less than or equal to
		$p$.radius (step 2). If node $i$ is the source node, we
		set $p$.radius $=\infty$; this means that at the
		beginning, we consider all members of the group $G$ as
		the destination set. If node $i$ is not the source
		node, the packet must have come from its parent node;
		the packet then carries a radius with it which was
		computed at the parent node. $A_i$ at the source node
		is $\emptyset$. When a packet arrives at node $i$ from
		its parent, $A_i$ initially contains the parent node.
		$A_i$ will be increased by adding node $i$'s neighbors
		one by one until it contains all of the neighbors or
		other terminating conditions are satisfied (step 3).

		For each neighbor $j\in N_i$ and $j\not \in A_i$,  we
		compute $j$'s responsible destination set $D_j$ by
		(\ref{two}) and each $j$'s average length $L_j$ by
		(\ref{three}). We then send the packet together with a
		radius to the selected neighbor node which has the
		minimum average path length. The radius is computed by
		(\ref{four}); it is the  path length between the
		selected neighbor node and the remotest member from
		$G_J$. $G_i$ is updated by taking out the destination
		set of the selected neighbor node. $A_i$ is updated by
		adding in the selected neighbor node.

		The algorithm will terminate at a node in three cases: \\
		\hsp{.4in}      1) if all $D_j = \emptyset$ \\
		\hsp{.4in}      2) if $N_i = A_i$ \\
		\hsp{.4in}      3) if $G_i = \emptyset$

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

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

	\section{Example}

		\hsp{8mm}  We use the network shown in Figure
		\ref{example1} to illustrate our algorithm.  The result
		shows that the cost generated by our algorithm is 11;
		but with shortest path algorithm, the total cost is
		13.

		\begin{figure*}[hhh]
		\epsfxsize=3.0in
		\centerline{\epsffile{chap03/example1.ps}}
		\caption{Example Network} \label{example1} 
		\end{figure*}

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

		\noindent 
		{\bf At node $S$} \\
		1) The packet is generated at $S$, $p$.radius $=\infty$, 
			$A_S = \emptyset$ \\
		2) $G_S = \{E, F, M\}$ \\
		3) $N_S = \{H, C, B, M\}, \ \ A_S = \emptyset$ \\
			\hsp{.135in}
			$D_H = \{E\}  \ \ \ \ \ \ L_H = 3 + 2 =5$ \\
			\hsp{.135in} 
			$D_C = \{E,F\} \ \ \ \ \ \ L_C = (3 + 4 + 2)/2 = 4.5$ \\
			\hsp{.135in} 
			$D_B = \{ F,M\} \ \ \ \ \ \ L_B = (2+2+3)/2=3.5$ \\
			\hsp{.135in} 
			$D_M = \{M,F\} \ \ \ \ \ \ L_M=(4+0+2)/2=3$ \\
		4) $J=M \ \ \ \ \ \ R=2$  \\
			\hsp{.135in}   
			{\bf send packet to node $M$ with $R=2$} \\
		5) $G_S=\{E\} \ \ \ \ \  A_S = \{M\} \ \ goto \ step \ 3$ \\
			\hsp{.4in} 3) $N_S - A_S = \{H, C, B\}$ \\
			\hsp{.58in}  $D_H=\{E\} \ \ \ \ \ \ L_H=5$ \\
			\hsp{.58in}  $D_C = \{E\} \ \ \ \ \ \ L_C = 7$ \\
			\hsp{.58in}  
			$D_B = \emptyset \ \ \ \ \ \ L_B = \infty$ \\
			\hsp{.4in}    4) $J=H \ \ R=2 \ \ $ \\
			\hsp{.58in}  {\bf send packet to node $H$ with $R=2$} \\
			\hsp{.4in}    5) $G_S = \emptyset \ \ \ stop$

		\noindent 
		{\bf At node $M$:} \\
		1) $G=\{E,F,M\}$,\ \  $p$.radius $=2$,\ \  $A_M=\{S\}$ \\
		2) $G_M=\{M,F\}$ \\
		3) $N_M=\{B,S,F\} \ \ \ \ A_M=\{S\} \ \ \ \ N_M-A_M=\{B,F\}$ \\
			\hsp{.135in}  $D_B=\emptyset \ \ L_B=\infty$ \\
			\hsp{.135in}  $D_F=\{F\} \ \ L_F=2/1=2$ \\
		4) $J=F \ \ \ \ \ \ R=0$ \\
			\hsp{.135in} {\bf send packet to node $F$ with $R=0$} \\
		5) $G_M=\{M\} \ \ \ A_M=\{S,F\} \ \ \ goto \ step \ 3$ \\
			\hsp{.4in}   3) $N_M-A_M=\{B\}$ \\
			\hsp{.58in}     $D_B=\emptyset \ \ \ stop$ 

		\noindent 
		{\bf At node $H$:} \\
		1) $G=\{E,F,M\}$,\ \  $p$.radius $=2$,\ \  $A_H=\{S\}$ \\
		2) $G_H=\{E\}$ \\
		3) $N_H=\{E,S\} \ \ \ \ \ \ N_H-A_H=\{E\}$ \\
			\hsp{.135in}    $D_E=\{E\} \ \ \ \ L_E=2$ \\
		4) $J=E \ \ \ \ \ \ R=0$ \\
			\hsp{.135in}  {\bf send packet to node E with $R=0$} \\
		5) $G_H=\emptyset \ \ stop$  

		\noindent 
		In the end, all packets at all involved nodes have
		$R=0$; the entire algorithm execution is terminated.

	\section {Practical Considerations}

		\hsp{8mm} For more efficiency, we can allow the packet
		to carry a limited number of member addresses. Suppose
		we let the packet carry the addresses of the four
		remotest members, the radius $R$ will be smaller and
		the algorithm will converge faster. As we saw in
		Chapter 2, the IP header usually has 40 bytes for
		optional use\cite{AGUILAR}; therefore, such
		consideration is highly feasible.

