Multicast Routing Algorithms In Computer Networks  Posted on:20010502  Degree:Doctor  Type:Dissertation  Country:China  Candidate:Y Liu  Full Text:PDF  GTID:1118360002951302  Subject:Applied Mathematics  Abstract/Summary:  PDF Full Text Request  In computer networks, multicasting is becoming increasingly important. Multicast routing is a networklayer 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 treebased 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 delayconstrained multicast routing. In this thesis, firstly, the existing heuristic algorithms for Steiner tree problem are summarized; secondly, a further research is made on delayconstrained multicast routing and three kinds of delayconstrained multicasting algorithm are proposed; then, the degreeconstrained 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 delayconstrained 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 problemspecific. 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 degreeconstrained 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 twolayer genetic algorithm. The inner layer genetic algorithm builds the degreeconst...  Keywords/Search Tags:  Computer Networks, Multicast, Genetic Algorithm, Multicast Routing Algorithm, Distributed Algorithm, Local Search, Steiner Tree, Multicasting Tree, Bandwidth constraint, Degree constraint, DelayConstraint  PDF Full Text Request  Related items 
 
