\documentstyle[12pt,epsf]{article}
\textheight 8.75in
\textwidth 6.5in
\oddsidemargin 0.2in
\topmargin -0.25in
%\pagestyle{empty}
\newcommand{\vsp}{\vspace*}
\newcommand{\hsp}{\hspace*}
\parindent 0in

\begin{document}

{\huge

%page1
\begin{center}
                    \vsp{10mm}
    {\huge \bf A Low Cost Algorithm 

          for Dynamic Multicast Routing 

                in Computer Networks}
                    \vsp{70mm}

{\Large
                       {by}
                    \vsp{18mm}

                   {Pingyan Tan}
                    \vsp{12mm}

        {Dr. Frederick C. Harris, Jr., Thesis Advisor}
                    \vsp{12mm}

                     Fall 1995
}

\end{center}
\newpage

%page2
\begin{center}
{\huge  \bf Definitions: Unicast, Broadcast, and Multicast}
\end{center}

\

\

Given a network $(N,L)$, where $N$ is a set of nodes and $L$ a set
of links, a source node $S {\in} N$ and a set of destination nodes 
$D {\subseteq} N$. 

\

\

\begin{tabular}{ll}
\hsp{0.5in} {\bf Unicast:}   & $|D| = 1$ \\
&\\
&\\
\hsp{0.5in} {\bf Broadcast:} & $|D|=|N|-1$\\
&\\
&\\
\hsp{0.5in} {\bf Multicast:} & $1 < |D| < |N| - 1$ \\
\end{tabular}

\newpage


%page 3
\begin{center}
{\huge \bf Some Issues in Multicast}
\end{center}

\

\

$\bullet$ Group notion

\

\

$\bullet$ Unknown destination feature

\

\

$\bullet$ Low-delay and low-cost routing

\

\

$\bullet$ Computation efficiency

\

\

$\bullet$ Compatibility with unicast routing






\newpage

%page4

\begin{center}
{\huge \bf Some Definitions}
\end{center}

\

\

$\bullet$ Subnetwork: {\Large subnetwork usually refers to local area\\
\hsp{.2in}network and subnetworks are attached to one or more routers}

\

$\bullet$ Router / Gateway / Bridge: {\Large router is a device\\
\hsp{.2in} that forwards message between subnetworks}. 


\

$\bullet$ Network: {\Large network is a collection of subnetworks connected\\
\hsp{.2in}through routers.}

\

$\bullet$ Routing table and group table

\

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

\newpage

%page6
%\begin{center}
%{\Large \bf Proposed Algorithm: Notions}
%\end{center}

%\

%\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. 

%\hsp{.2in} $D_j$: Neighbor $J$'s responsible destination set. 

%\hsp{.2in} $L_j$: Average length from neighbor node $j$ to $D_j$.

%\hsp{.2in} $A_i$: The assigned neighbor set. 

%\hsp{.2in} $d_{ij}$: The shortest path length from $i$ to $j$. 

%\newpage

%page6
\begin{center}
{\huge \bf Proposed Algorithm}
\end{center}

\

{\small
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{.2in} $A_i$ = $\{k\}$, where $p$ is from neighbor $k$ of node $i$.\\
\hsp{.2in} if $p$.radius = 0 \ \ then stop.

2. Compute node $i$'s responsible set
\[G_i= \{ g|g\in G,\ {\rm and}\ d_{ig} \leq p.radius,\ {\rm and}\ g\neq i\}\]

3. For each $j \in N_i$ and $j \not\in A_i$, compute $j$'s destination set
\[ D_j = \{g | g \in G_i,\ {\rm and}\  d_{jg} < d_{ig} \} \]
\hsp{.2in} and the average length
\[ L_j = (d_{ij} + \sum_{g \in D_j} d_{jg} - \hat{L}_j ) /|D_j| \]
\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}\] 
\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.

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
\[ R = \max_{g\in D_J} d_{Jg}       \]
\hsp{.2in}   send a packet with radius $R$ to node $J$.
     
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. 
     
\

{ \bf Terminating Conditions}

\hsp{.4in}      1) if all $D_j = \emptyset$ 

\hsp{.4in}      2) if $N_i = A_i$ 

\hsp{.4in}      3) if $G_i = \emptyset$

}

\newpage

%page7

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

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

\

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

{\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$} \\

\newpage

\vsp{1in}

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$

\newpage

\vsp{1in}
{\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$ 

\newpage

\vsp{1in}

{\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$ 

In the end, all packets at all involved nodes have R=0, the entire algorithm
execution is terminated. 
}

\newpage


%page8
\begin{center}
{\huge \bf The Compared Algorithm}
\end{center}

\

\

\

%{\normalsize
{\large
\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.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} for each adjacent node $j$ \\
\hsp{1.5in} if min-hops[$j$] $< \infty$ \\
\hsp{2.0in} send copy of packet to node $j$ \\ \hline \hline
\end{tabular}
\end{center}
}

\newpage

%page9

\begin{center}
{\huge \bf Simulation Tool}
\end{center}

\

\

{\bf smpl}: {\Large Event-oriented simulation language.}

\

\

{\bf Facilities}: {\Large A facility represents some work-performing \\
resource of the system being modeled.}

\

\

{\bf Token}: {\Large Tokens represent the active entities of the system.}

\

\

{\bf Event}: {\Large A change of state of any system entity is an event.}



\newpage

%page10

\begin{center}
{\huge \bf Performance Measures}
\end{center}

\

\

$\bullet$ {\bf Delay}  vs. {\bf offered load}


\

$\bullet$ {\bf Utilization}  vs. {\bf offered load}

\

\

In our simulation model:

\

{\bf Delay:} {\Large the interval between the generation of a packet and the 
arrival of the packet at the destination.} 

\

{\bf Utilization:} {\Large the average utilization of all links.}

\

{\bf Offered load:} {\Large the rate of the data packet generation.}

\


\newpage

%page11

%\begin{center}
%{\Large \bf Parameters for Simulation}
%\end{center}
%
%\

%\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}

%\newpage

%page11

\begin{center}
{\huge \bf Information at a Node}
\end{center}

\

\

{\bf Routing table:}

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

\

{\bf Group table:}
\begin{center}
\begin{tabular}{|l|l|l|l|} \hline
group & node 1 & node 2 & ... \\ \hline
\end{tabular}
\end{center}

\

{\bf Group presence table:}
\begin{center}
\begin{tabular}{|l|l|l|l|} \hline
 group 1 & group 2 & group 3 & ... \\ \hline
\end{tabular}
\end{center}

\

{\bf Cache records:} 
\begin{center}
\begin{tabular}{|l|l|l|l|} \hline
source & group & parent & min-hops[ ]  \\ \hline
\end{tabular}
\end{center}

\newpage

%page12
\begin{center}
{\huge \bf The Simulation Model}
\end{center}

\begin{figure*}[hhh]
\epsfxsize=5in
\centerline{\epsffile{event.ps}}
\caption{Events} 
\end{figure*}

\

\

{\large
{\bf Packet Types}

\

\hsp{0.5in} DATAS: unicast data packet.

\hsp{0.5in} DATAG: multicast data packet.

\hsp{0.5in} GRPJL: group Join/Leave packet.

}

\newpage

%page13
\begin{center}
{\huge \bf Parameter Values}
\end{center}

\

\

\


{\Large
\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}
}

\newpage


%page14
\begin{center}
{\huge \bf Simulation Results ($N=75$)}
\end{center}

\begin{figure}[hhh]
\epsfxsize=2.4in
\centerline{\epsffile{x1delay.ps}}
\caption{Delay ($N=75$)} 
\end{figure}

\begin{figure}[hhh]
\epsfxsize=2.4in
\centerline{\epsffile{x1load.ps}}
\caption{Util. ($N=75$)} 
\end{figure}

\newpage

%page15
\begin{center}
{\huge \bf Simulation Results ($N=97$)}
\end{center}

\begin{figure}[hhh]
\epsfxsize=2.4in
\centerline{\epsffile{x2delay.ps}}
\caption{Delay ($N=97$)} 
\end{figure}

\begin{figure}[hhh]
\epsfxsize=2.4in
\centerline{\epsffile{x2load.ps}}
\caption{Util. ($N=97$)} 
\end{figure}

\newpage

%page16
\begin{center}
{\huge \bf Simulation Results ($N=123$)}
\end{center}

\begin{figure}[hhh]
\epsfxsize=2.4in
\centerline{\epsffile{x4delay.ps}}
\caption{Delay ($N=123$)} 
\end{figure}

\begin{figure}[hhh]
\epsfxsize=2.4in
\centerline{\epsffile{x4load.ps}}
\caption{Util. ($N=123$)} 
\end{figure}

\newpage

%page17
\begin{center}
{\huge\bf Simulation Results (Reduction)}
\end{center}

\begin{figure}[hhh]
\epsfxsize=2.4in
\centerline{\epsffile{xdelayred.ps}}
\caption{Delay Reduction}  
\end{figure}

\begin{figure}[hhh]
\epsfxsize=2.4in
\centerline{\epsffile{xloadred.ps}}
\caption{Util. Reduction}  
\end{figure}

\newpage

%page18
\begin{center}
{\huge \bf Simulation Results (enlarged)}
\end{center}

\begin{figure}[hhh]
\epsfxsize=1.4in
\centerline{\epsffile{x1delaya.ps}}
\caption{Delay (Enlarged, $N=75$)} 
\end{figure}

\begin{figure}[hhh]
\epsfxsize=1.4in
\centerline{\epsffile{x2delaya.ps}}
\caption{Delay ($Enlarged, N=97$)} 
\end{figure}

\begin{figure}[hhh]
\epsfxsize=1.4in
\centerline{\epsffile{x4delaya.ps}}
\caption{Delay (Enlarged, $N=123$)} 
\end{figure}

\newpage

%page19
\begin{center}
{\huge \bf Simulation Results ($N=40$)}
\end{center}

\begin{figure}[hhh]
\epsfxsize=2.4in
\centerline{\epsffile{x3delay.ps}}
\caption{Delay ($N=40$)} 
\end{figure}

\begin{figure}[hhh]
\epsfxsize=2.4in
\centerline{\epsffile{x3load.ps}}
\caption{Util. ($N=40$)} 
\end{figure}


\newpage


\begin{center}
{\huge \bf Reductions ($N=40$)}
\end{center}

\

\

\

{\large
\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}

}


\newpage
%page20 

\begin{center}
{\huge \bf Conclusions}
\end{center}

\

$\bullet$ {\bf Performance}

\

$\bullet$ {\bf Functionality}

\

$\bullet$ {\bf Scalability} 

\

$\bullet$ {\bf Compatibility}

\

$\bullet$ {\bf Reliability} 

\

$\bullet$ {\bf Simplicity} 



} % sizing

\end{document}
