\chapter{Introduction}

	\hsp{8mm} Routing is one of the most important aspects of
	computer networks.  Unicast routing has been  the dominant
	scheme used in  network routing. However, in the past few
	years, multicast routing has seen widespread use in those
	networks that support it. There exist many cases where an
	application must send the same information to more than one
	destination, such as:
 
	\noindent\hspace*{0.2in}$\bullet$ updating all copies of a 
		replicated file or database.\\
	\hspace*{0.2in}$\bullet$ sending data packets to all 
		participants in computer mediated conference.\\
	\hspace*{0.2in}$\bullet$ emailing to more than one receiver.\\
	\hspace*{0.2in}$\bullet$ dissemination of intermediate results 
		to a set of processors supporting a distributed 
		computation.

	Multicast routing can be defined as follows: 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$. If $1<|D|<|N|-1$, then the
	problem is a multicast problem. If $|D|=1$, then the problem is
	a unicast problem and if $|D| = |N|-1$, then the problem is a
	broadcast problem.

	The subset $D$ is called a {\em group}, and there can be more
	than one group existing in a network at the same time.
	Multicasting should be more efficient than unicasting separate
	copies to each destination, because it should reduce the
	transmission overhead.

	Modern networks also require the {\em unknown-destination}
	delivery function for routing. If a set of destinations can be
	identified by a single group address, such a group address can
	be used to reach one or more destinations whose individual
	addresses are unknown to the sender, or whose address may
	change over time.

	Algorithms for solving the multicast routing problem can be
	divided into two categories: low-delay algorithms and low-cost
	algorithms. Low-delay routing algorithms minimize the path
	length from the source to every destination node. This usually
	requires that the message be sent to every destination along
	the shortest path. Low-cost routing algorithms minimize the
	total traffic. The total traffic is equivalent to the total
	length of the path in a delivery tree. Finding a minimum cost
	routing tree is a Steiner Tree Problem in a graph, which is
        known to be NP-complete\cite{HWANG}.

	This thesis presents a new algorithm for multicast routing.
	This algorithm is aimed at low-cost routing, and supports the
	{\em unknown-destination} delivery function as well.


	In Chapter 2 we review  what is known about 
        routing problems, describing different
	aspects of the  problem and some known algorithms from the
	literature.  Chapter 3 gives the formal description of our
	proposed algorithm and a simple network example to explain the
	algorithm. Chapter 4 develops a simulation model for our
	proposed algorithm and a compared algorithm which is presented
	in \cite{DEERING}.  Chapter 5 concludes this thesis with a
	discussion of the advantages of our algorithm.

