Multicast Routing Algorithms In Computer Networks

In computer networks, multicasting is becoming increasingly important. Multicast routing is a network-layer function that constructs paths along which data packets from a source are distributed to reach many, but not all, destinations in a communication network. A fundamental issue in multicast communication is how to determine an efficient message route (multicast routing). Tree construction is a commonly used approach in solving the multicast routing problem. Popularity of the tree-based approach arises from the ability to potentially share many links in transmitting the message to the destination set. Also, multicast trees minimize data replication; message need only be replicated at forking nodes. Multicast routing algorithms. are used to compute multicast trees that satisfy QoS requirements. Now, researches on multicast routing algorithm mainly focus on multicasting algorithm without constraints and delay-constrained multicast routing. In this thesis, firstly, the existing heuristic algorithms for Steiner tree problem are summarized; secondly, a further research is made on delay-constrained multicast routing and three kinds of delay-constrained multicasting algorithm are proposed; then, the degree-constrained multicasting algorithms and bandwidth constrained multicasting algorithms are studied. This paper centers around how to construct multicast routing trees with minimum cost. The main research work and results are follows: 1. Summarize all heuristic algorithms for Steiner tree problem because the minimum cost multicast tree problem can be reduced to Steiner tree problem. This is the basis of the work following. 2. Propose three algorithms for delay-constrained multicast routing. The first one is a hybrid genetic algorithm (HGA) which adopts the local search and natural coding technique. In HGA, the individual is a spanning tree that spans the source and destination nodes and the genetic operators are problem-specific. The second one is a genetic algorithm using binary code and normal genetic operators. The algorithm searches for all the possible Steiner nodes to find the final Steiner nodes included in the optimal tree. The experimental results show that the two algorithms proposed above perform as well as the BSMA algorithm but these two algorithms have lower time complexity than BSMA. The last one is a localized multicast routing algorithm, which builds the route by querying only incident links for cost and delay information, and the source node does not need store the network topology. Thislocalized algorithm performs as well as CDKS algorithm. So it is a practical multicast routing algorithm. 3. Deal with the multicast routing problem when not all the nodes in the networks have the multicasting abilities. Using degree constraint to notify the multicast capability of every node, we design three degree-constrained multicast routing algorithms. The first one is a distributed multicast routing algorithm. It has several advantages: 1) every node need not store the network topology; 2) only the source node and the destination nodes take par?in the algorithm; 3) Integration of multicast routing with connection configuration; 4) the algorithm uses a small number of messages and short convergence time to establish a connection, and the message cost is even comparable to those using centralized routing. The second one is a two-layer genetic algorithm. The inner layer genetic algorithm builds the degree-const...