\chapter{Simulation Model and Results}

	\section{Performance Measurements}

		\hsp{8mm} The simulation study will measure two
		different relationships: one is delay versus offered
		load, the other is utilization versus offered load.
		Delay is defined to be the interval between the time a
		packet is generated and the time the packet arrives at
		the destination. In a multicast environment, the delay
		is the average delay for all destinations. If a packet
		is sent to a destination more than once, we only count
		the delay for the first one. Offered load is defined to
		be the offered rate of packet generation. Utilization
		is defined to be the average utilization of all links.
		We also define the throughput as:\\
		\hsp{20mm}{\it throughput = offered load}\\
		(In networks, throughput is commonly defined as offered
		load $-$ rejected load\cite {BERTSEKAS}. In our
		simulation, we always have rejected load $=$ 0.)

	\section{Network Parameters}

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

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


	\section{Data Structures Used with Simulation}

		\subsection {Network} 

			\hsp{8mm} A network is a set of nodes and a set
			of directional links, where nodes can be
			numbered from 0 to $N-1$ for a network with $N$
			nodes. Connectivity information is stored in a
			list of neighbors which is attached to every
			node. For the simulation purpose, We only need
			to maintain one copy of the network topology
			description (connectivity and link length),
			although in reality the description is
			duplicated at every node.

			The information stored at a node includes:

			1. Routing table. For our purpose, the
			following entry is enough. For an $N$ nodes
			network, there should be $N-1$ entries for each
			routing table.

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

			2. Group table. This is a global group table.
			Each entry comprises a group number  and a bit
			map indicating which node is in the group. If
			there are $k$ groups existing in network, there
			should be $k$ entries for the group table.

			{\small
			\begin{center}
			\begin{tabular}{|l|l|l|l|} \hline
			group & node 1 & node 2 & ... \\ \hline
			\end{tabular}
			\end{center}
			}

			3. Group presence table. This is a local group
			table. It is a hash table since groups join and
			leave and insert/delete operations are
			expected. This table indicates that the current
			node is participating in which group.

			{\small
			\begin{center}
			\begin{tabular}{|l|l|l|l|} \hline
			 group 1 & group 2 & group 3 & ... \\ \hline
			\end{tabular}
			\end{center}
			}

			4. For the proposed algorithm, a node also
			needs the routing tables from its neighbors.
			For simulation, we don't need to store
			duplicated tables at different nodes. We may
			ignore the impact of transferring routing table
			information between neighbors. (In fact, if
			data transfer is not desirable, a separate
			calculation will also be able to generate the
			neighbors' routing tables at a small cost.)

			5. For the algorithm we are comparing ours with
			we need, as described earlier, a set of cache
			records at each node.

			{\small
			\begin{center}
			\begin{tabular}{|l|l|l|l|} \hline
			source & group & parent & min-hops[ ]  \\ \hline
			\end{tabular}
			\end{center}
			}

			\noindent 
			where `min-hops' is an array of $K$ elements
			for $K$ neighbors.

		\subsection{Packets} 

			\hsp{8mm} We define three types of packets:
			DATAS, DATAG, and GRPJL.  All packets have the
			common fields:

			{\small
			\begin{center}
			\begin{tabular}{|ll|} \hline
			type         & the packet type\\
			src          & where the packet is originated \\
			at-node      & currently the packet is at which node \\
			from-link    & from which link the packet comes 
					to this node \\
			to-link      & to which link the packet will be 
					forwarded \\
			\hline
			\end{tabular}
			\end{center}
			}

			\noindent
			Each type of packet  has its particular fields:

			1) DATAS: This type is unicast data packet with
			a single destination address.

			{\small
			\begin{center}
			\begin{tabular}{|ll|} \hline
			dst-addr & destination address \\
			seq &  sequence number for this (src, dst) pair \\
			birth-time & when the packet is generated \\
			\hline
			\end{tabular}
			\end{center}
			}

			2) DATAG: This type is multicast data packet
			with a group destination address.

			{\small
			\begin{center}
			\begin{tabular}{|ll|} \hline
			gid  & destination group address\\
			seq  & sequence number for this (src, grp) pair \\
			radius & proposed algorithm only \\
			radius-time & when the radius is computed \\
			hop-limit  & compared algorithm only \\
			birth-time & when the packet is generated \\
			\hline
			\end{tabular}
			\end{center}
			}

			3) GRPJL: This type is group Join/Leave packet.

			{\small
			\begin{center}
			\begin{tabular}{|ll|} \hline
			gid  & group that src is joining/leaving \\
			op   & JOIN/LEAVE \\
			\hline
			\end{tabular}
			\end{center}
			}

	\section {The Compared Algorithm}

		\hsp{8mm} We simulate and compare the performance of
		our proposed algorithm with the LS multicast routing
		algorithm by Deering \cite{DEERING}.  Both algorithms
		require roughly the same amount of information, but
		Deering's algorithm, a low-delay algorithm, needs to
		maintain a delivery tree for each active source-group
		pair. For simplicity, we omit the detail of a
		subnetwork, and treat each router as a node, which can
		also serve as a host.  A simplified version of
		Deering's algorithm is given in table \ref{compalg}.

		{\normalsize
		\begin{table}
		\begin{center}
		\begin{tabular}{|l|} \hline \hline
		1. On appearance/disappearance of group $g$ on node $k$: \\
		\hsp{0.5in} flood link-state update, reporting change 
			of $g$ on $k$ \\
		2. On generation/receipt of link-state update, 
			reporting change of $g$ \\
		\hsp{0.5in} for each cache record $c$ with $c$.group = $g$ \\
		\hsp{1.0in}    discard $c$ \\
		3. On receipt of multicast packet from source $s$ to 
			group $g$ via node $k$ \\
		\hsp{0.18in} with remaining hop-limit {\em hl}: \\
		\hsp{0.5in} if no cache recode $c$ such that $c$.source = 
			$s$ and $c$.group = $g$ \\
		\hsp{1.0in} create cache record $c$; $c$.source = $s$; 
			$c$.group = $g$ \\
		\hsp{1.0in} $<$compute $c$.parent and $c$.min-hops$>$ \\
		\hsp{0.5in} if $c$.parent = $k$ \\
		\hsp{1.0in} {\em hl} $=$ {\em hl} $-1$ \\
		\hsp{1.0in} for each adjacent node $j$ \\
		\hsp{1.5in} if {\em hl} $\geq$ min-hops[$j$] \\
		\hsp{2.0in} send copy of packet to node $j$ \\ \hline \hline
		\end{tabular}
		\end{center}
		\caption{{\em Tree} Algorithm}  \label{compalg}
		\end{table}
		}

	\section{The Simulation Model}

		\hsp{8mm} We use a software called {\em smpl}, which is
		described in \cite{MCDOUGALL}, as our tool for the
		simulations.  The {\em smpl} package is an
		event-oriented simulation language which is designed
		for the simulation of computer and communication
		systems.

		We use a {\em smpl} facility, which in essence is a
		server in the queuing model, to represent the links
		between nodes. Link $<i,j>$ is considered different
		from link $<j,i>$ as physically they are two channels
		and can have unequal length.  Hence they are defined as
		two facilities. The utilization of this facility will
		be equal to the utilization of the links. A {\em smpl}
		token is used to represent a pointer to a packet. 
		%where the token may represent jobs or customers, etc.

		We assume that the packet generation interval for both
		unicast and multicast is exponentially distributed with
                mean $1/\lambda_u$ and $1/\lambda_m$ respectively. We
		also assume that the group's birth and death interval
		is exponentially distributed with mean $1/\lambda_g$.

		\paragraph{Event routines.} 
			The simulation model comprises six event
			routines as shown in Figure \ref{event}. We
			assume a broadcast protocol for link state
			report which includes group membership change
			report (Join, Leave). To ensure fast delivery
			of such information and not go into the details
			of flooding protocols, we pre-calculate a
			broadcast tree. The broadcast packet will have
			the highest priority. When a broadcast packet
			arrives at a node, the packet will be forwarded
			to all neighbors in the broadcast tree except
			where it is from. 
			%Such a tree is a subgraph of
			%the network and can be represented by attaching
			%to every node a list of its neighbors that are
			%in the tree.  
			The events are described as follows.

			\begin{figure}
			\epsfxsize=3.5in
			\centerline{\epsffile{chap04/event.ps}}
			\caption{Events} \label{event} 
			\end{figure}

			\noi 
			{\bf DATAGEN} \ The simulation enters this
			event when a data packet is generated at a
			node. The packet can be either a unicast data
			packet or a multicast data packet. For unicast,
			a destination node is randomly picked up; for
			multicast, a destination group is randomly
			picked up; and for each packet being generated,
			a PKTARR event is scheduled. Finally an event
			for the same data type is scheduled, whose time
			exponentially distributed with mean
			$1/\lambda_u$ or $1/\lambda_m$, respectively.


			\noi 
			{\bf GRPJL} \ This event means a node
			joins/leaves a group. The join/leave period is
			exponentially distributed.

			On a BIRTH event, a group size is randomly
			chosen between min-size and max-size, and a set
			of nodes are randomly picked up as group
			members. A packet of type GRPJL and operation
			JOIN is generated for each group member, with a
			random delay, then a PKTARR event is scheduled
			for each packet. Another BIRTH event is also
			scheduled, in time exponentially distributed
			with mean $1/\lambda_g$.

			On a DEATH event, a group is randomly chosen.
			Then for each group member, a packet of type
			GRPJL and operation LEAVE is generated, also
			with a random delay. Similarly a PKTARR event
			is scheduled for each packet.  Another DEATH
			event is scheduled too, similar to a BIRTH
			event.

			\noi 
			{\bf PKTARR} \ This event is entered when a
			packet arrives at a node, or when a packet is
			just generated at a node. This is the major
			event where activities for the two algorithms
			differ. Generally, if this node is a
			destination node, do statistics. If the packet
			needs to be forwarded, calculate the link(s)
			the packet should be forwarded onto and
			schedule a REQLINK event for each forwarding
			link.  The three different types of packets are
			treated differently as described below:

			DATAS:  Unicast packet. This packet is simply
			to be sent to the next hop which can be looked
			up from the routing table.

			DATAG: Multicast data packet. One of the
			algorithm procedures {\em radius} (for the
			proposed algorithm) or {\em tree} (Deering's
			algorithm) is to be called to compute the next
			hops, then the replicated packets are sent to
			these next hop nodes.

			GRPJL: Group join/leave packet.  If the node is
			the one that originates the packet, both the
			local group table and the global group table in
			this node are updated. If it is not the
			originating node, only the global-group table
			is updated. The packet is also forwarded to the
			neighbors in the broadcast tree. For the
			compared algorithm, the receiving node of this
			packet will delete all cache records $c$ such
			that $c$.group equals the involved group.

			\noi 
			{\bf REQLINK} \ The packet tries to reserve a
			link for transmission.  If the link is
			available, schedule a PKTARR event in time
			$t_p$ and a FREELINK event immediately. If the
			link is busy, this event will be queued at the
			link, and later when the link is free, the
			queued event will be scheduled again.

			\noi 
			{\bf FREELINK} \ The link previously reserved
			is released after the transmission is
			completed.  The head of the queued packets
			along with the REQLINK event at that link will
			be scheduled by the system to occur
			immediately.


	\section {Simulation Results}

		\hspace*{8mm}For simplicity, we call our algorithm
		``{\em Radius} algorithm'' and Deering's algorithm
		``{\em Tree} algorithm.'' We randomly generated four
		networks with 40, 75, 97, and 123 nodes respectively (these
		sizes are sufficiently representative.) In each
		network, the group population fluctuates along an
		average, by a birth/death procedure, and the group size
		fluctuates as a random number uniformly distributed in
		a certain range. In the simulation, the multicast
		packet generation rate $\lambda_m$ is set to be the
		same as he unicast rate $\lambda_u$. These rates are
		changing for different passes of simulation. The rates
		are assigned the values with which no severe congestion
		is observed and reasonable utilizations are obtained.
		The following table gives other parameter ranges for
		the four networks:

{\small
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
\hline
network&$G$&$G_{\min}$&$G_{\max}$&av. \#&hit  &$\lambda_g$&$t_p$&link \\ 
       &   &        &        &links &ratio&           &     & len \\ \hline
40     & 3 & 2      & 39     & 2.95 & 91\%    & 1/1000 & 0.1 & 1  \\ 
75     & 5 & 2      & 37     & 2.59 & 91\%    & 1/1000 & 0.1 & 1  \\ 
97     & 4 & 2      & 48     & 3.22 & 92\%    & 1/1000 & 0.1 & 1  \\
123    & 3 & 2      & 40     & 3.25 & 86-95\% & 1/1000 & 0.1 & 1  \\
\hline
\end{tabular}
\end{center}
}

		See Section 4.2 for the meaning of the variables.  In
		the table, the value 1/1000 for $\lambda_g$ means that
		the group birth and death rate 
		is 1/1000 of the unicast packet generation rate.

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

		We execute both our algorithm and Deering's algorithm
		with exactly the same network parameters.

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

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

		The simulation results are shown in Figures
		\ref{x3delay} to \ref{xloadred}. In these figures, the
		horizontal axes represent the message rate which is the
		offered load. The vertical axes represent the delay
		(Figures \ref{x1delay}, \ref{x2delay}, and
		\ref{x4delay}), utilization (Figures \ref{x1load},
		\ref{x2load}, and \ref{x4load}), and reduction
		percentage (Figures \ref{xdelayred} and
		\ref{xloadred}), respectively. 
		Figures \ref{x3delaya},\ref{x1delaya},
		\ref{x2delaya}, and \ref{x4delaya} are the enlarged
		lower portion of Figures \ref{x3delay},
		\ref{x1delay}, \ref{x2delay},
		and \ref{x4delay}, respectively.  Figures
		\ref{xdelayred} and \ref{xloadred} are the average
		reduction percentage for delay and utilization on the
		three larger networks, by using the following formula:
		\[ A=\frac{\sum_{i=1}^3\frac{T_i-R_i}{T_i}}{3}\times 100\% \]
		where\\
		\hsp{8mm} $A$: average percentage delay or 
			utilization reduction.\\
		\hsp{8mm} $T_i:$  {\em Tree} delay or utilization for 
			the $i$th network.\\
		\hsp{8mm} $R_i:$ {\em Radius} delay or utilization for 
			the $i$th network.

		The results for the smaller, 40 node network, are based
		on a different range of message rates (100 to 800) from 
		that used in the three larger networks (50 to 400), 
		because the smaller network can tolerate
		higher message rates for both algorithms. Therefore, the 
		reduction cannot be averaged with the lager network results.
		We give similar calculations in the following table for
		the 40 node network.

\begin{center}
\begin{tabular}{|l|r|r|r|r|r|r|r|r|} \hline
Message rate    & 100 & 200 & 300 & 400 & 500 & 600 & 700 & 800 \\ \hline
Delay reduction & -2.6& 2.5 & 17.0& 10.3& 29.8& 23.2& 29.6& 2.6 \\ \hline
Util. reduction & 0.0 & 5.0 & 7.4 & 5.6 & 4.3 & 6.0 & 3.4 & 3.0 \\ \hline
\end{tabular}
\end{center}

		\noi In the table, the numbers in the last two rows
		are reduction percentages. 
		%The only negative number
		%represents a small increase of delay from 0.38 to 0.39 
		%at the message rate 100.

	\section {Simulation Results Analysis}

		\hsp{8mm} The simulation results show that our
		algorithm has a better performance than the compared
		algorithm since both the delay and the utilization are
		lower on the four networks. At certain crucial message
		rates, the delay can be lowered by 40--50\%. The delay
		reduction at these rates means {\em Radius} can support
		higher offered load than can {\em Tree}.

		Since the results for all four networks are similar, we
		only give a detailed analysis of the 75 node network 
                (Figures \ref{x1delay}, \ref{x1load}, and \ref{x1delaya}). For
		this 75 node network, when the message rate is from 50
		to 100 packets/unit time, the delay goes from 0.55 to
		0.58 for {\em Radius} and from 0.57 to 0.60 for {\em
		Tree}. In such a low message rate range, the main delay
		for both algorithms is caused by the transmission
		delay. Since {\em Tree} needs to reconstruct the
		delivery tree occasionally, this causes the higher
		delay than that of {\em Radius}. When the message rate
		is higher than 100 packets/unit time, the delay and
		utilization for both algorithm increase, but the delay
		and utilization for {\em Radius} are always lower. The
		reason is given as follows:

		When the message rate increases, the corresponding
		utilization of links increases, as seen in figure
		\ref{x1load}. Utilization reflects the traffic load.
		The increased traffic causes some packets to be queued
		for the available links. At this time, the queuing delay
		becomes dominant, while the transmission delay becomes
		insignificant. A few calculations can also show that 
		the delivery tree computation time will have little 
		impact on the total delay
		at higher message rates.  The 75 node network has
		$E=97$ links, therefore the tree computation time is
		$(N+E)\log N = 1071$, which is roughly the time to
		transmit one packet from a node. Suppose on average a
		packet travels half the ``diameter'' of the network, or
		$\sqrt{75}/2=4.33$ hops to reach its destination, with
		a 90\% cache hit ratio, the probability of having one
		tree computation on its way is $4.33\times 0.1 =
		0.433$. In other words, a packet will on average need
		0.433 tree computations, or equivalently, in its total
		delay a portion of 0.433 packet transmission times is
		caused by tree computations. Given that a packet
		transmission time is 0.1 in the time scale shown in the
		delay figures, from Figure \ref{x1delay}, we can see
		the delay at the higher range is in the order of 100 to
		more than 1000 packet transmission times, compared with
		which 0.433 is certainly a tiny portion.  In the case
		when the queuing delay plays the major role, the {\em
		Radius} algorithm shows more advantages, since it is a
		low-cost algorithm.  Reduced total cost means reduced
		total traffic load, while the reduction in traffic load
		will decrease the waiting time for queued packets.
		Therefore, the total delay is eventually decreased.
		This is why {\em Radius} has lower delay than {\em
		Tree}, despite the fact that {\em Tree} always uses the
		shortest paths and {\em Radius} may use longer paths
		from time to time.  Note that for the 123 nodes network
		in Figure \ref{x4delay}, there is a crossover. From the
		figure, we can see that the curve for {\em Radius} is
		smoothly increasing when the message rate increases,
		while the curve for {\em Tree} suddenly slows down when
		the message rate increases from 300 to 350, and goes up
		again for the message rate 400.  This might be caused
		by some special combination of network topology and
		message distribution, since both the network and the
		messages are randomly generated.
		
		\begin{figure}
		\epsfxsize=2.7in
		\centerline{\epsffile{chap04/x3delay.ps}}
		\caption{Delay ($N=40$)} \label{x3delay} 
		\end{figure}

		\begin{figure}
		\epsfxsize=2.7in
		\centerline{\epsffile{chap04/x3load.ps}}
		\caption{Util. ($N=40$)} \label{x3load} 
		\end{figure}
		

		\begin{figure}[h]
		\epsfxsize=2.7in
		\centerline{\epsffile{chap04/x1delay.ps}}
		\caption{Delay ($N=75$)} \label{x1delay} 
		\end{figure}

		\begin{figure}
		\epsfxsize=2.7in
		\centerline{\epsffile{chap04/x1load.ps}}
		\caption{Util. ($N=75$)} \label{x1load} 
		\end{figure}

		\begin{figure}
		\epsfxsize=2.7in
		\centerline{\epsffile{chap04/x2delay.ps}}
		\caption{Delay ($N=97$)} \label{x2delay} 
		\end{figure}
		
		\begin{figure}
		\epsfxsize=2.7in
		\centerline{\epsffile{chap04/x2load.ps}}
		\caption{Util. ($N=97$)} \label{x2load} 
		\end{figure}

		\begin{figure}
		\epsfxsize=2.7in
		\centerline{\epsffile{chap04/x4delay.ps}}
		\caption{Delay ($N=123$)} \label{x4delay} 
		\end{figure}
		
		\begin{figure}
		\epsfxsize=2.7in
		\centerline{\epsffile{chap04/x4load.ps}}
		\caption{Util. ($N=123$)} \label{x4load} 
		\end{figure}
		
		\begin{figure}
		\epsfxsize=2.7in
		\centerline{\epsffile{chap04/xdelayred.ps}}
		\caption{Delay Reduction}  \label{xdelayred} 
		\end{figure}
		
		\begin{figure}
		\epsfxsize=2.7in
		\centerline{\epsffile{chap04/xloadred.ps}}
		\caption{Util. Reduction}  \label{xloadred} 
		\end{figure}
		
		\begin{figure}
		\epsfxsize=2.7in
		\centerline{\epsffile{chap04/x3delaya.ps}}  
		\caption{Delay (Enlarged, $N=40$)} \label{x3delaya} 
		\end{figure}

		\begin{figure}
		\epsfxsize=2.7in
		\centerline{\epsffile{chap04/x1delaya.ps}}
		\caption{Delay (Enlarged, $N=75$)} \label{x1delaya} 
		\end{figure}

		\begin{figure}
		\epsfxsize=2.7in
		\centerline{\epsffile{chap04/x2delaya.ps}}
		\caption{Delay (Enlarged, $N=97$)} \label{x2delaya} 
		\end{figure}

		\begin{figure}
		\epsfxsize=2.7in
		\centerline{\epsffile{chap04/x4delaya.ps}}
		\caption{Delay (Enlarged, $N=123$)} \label{x4delaya} 
		\end{figure}
