| Multicasting is a means of group communications. It delivers information from a source to several destinations in the same time. The building-up of multicasting tree is one of the common methods for resolving the problem of rout-translation. There are mainly three types of multicasting trees: the tree based on the data source, Steiner tree and the tree based on the center. Of these three types, the most representative ones are the shortest path tree based on the data source (the brief name SPT) and the Steiner tree. The most important advantage of the SPT is that it makes the least postpone from the source node to each purpose node; and the Steiner tree makes the minimum total consumption of all the conjunctions possible and shares a maximum bandwidth. If each node excluding the source node in network is the destination node, the tree will be defined as the minimum spanning tree (the brief name MST).In a certain network, the building-up of multicasting tree from the source node to other purpose nodes can hardly achieve the least postpone and the minimum total consumption at the same time. Therefore, the building-up of the Steiner tree which satisfies appointed postpone has generated a large number of researches by scholars. When the network become enough big, there are usually more than one shortest routes from the source node to some destination nodes, and therefore the SPT also will not be the only one. Of the numerous SPTs, the total consumptions of each tree are also different. As a result, it is necessary to research the problem of how to lower the total consumption of SPT.The algorithm of shortest best path tree (SBPT) adopts the greedy method to select the shortest path in the process of constructing SPT, which lowers the total consumption of the construct spanning tree. The time complexity of the algorithm is too difficult to solve a large network. The algorithm of destination-driven multicasting route translation DDMC lowers the total consumption of the multicasting tree by the sharing of as many destination nodes as possible. The algorithm of destination-driven shortest path DDSP adopts the basic idea of the Dijkstra algorithm of increasing the path, and combines the method of the DDMC algorithm whose purpose node share path. When there is not an only shortest path from source node to some node, a shortest path whose sharing path is longest with other destination nodes is always chosen, which lowers the total consumption of the SPT. It is suitable to calculate the shortest path tree which has large destination nodes. The in keeping with calculation purpose node counts most short-circuit path tree.The algorithm of fast low-cost shortest path tree FLSPT is developed from the DDSP algorithm. The multicasting tree it constitutes has the same function with the multicasting tree structured by DDSP algorithm, but its time complexity is lower than that of DDSP algorithm.After a careful research on the FLSPT algorithm, we can discover: after choosing the minimum node u near the source node S from the Q set, if we don't delete the node u from the Q set, it will appear to endless loop; In the meantime, if u is the purpose node, and if we don't delete it from the purpose node set, it will also appear to endless loop.Therefore we have to add two sentences in algorithm: Delete u from Q and Delete u from D.In the meantime, at analytical time complications, FLSPT didn't consider it had deleted a node from Q in each loop when we select and delete a node from sequence Q. Therefore, the time complexity of FLSPT can express with the more excellent expression.In the algorithm of Dijkstra, the experiment expresses that the insertion of node which is waiting for development has very strong partial property, it is that the distribution of the node's insertion is unbalance. Thus, we put forward an algorithm of FLSPT based on ordinal circularly double linked list, The imitated experiment of random network indicates that the efficiency of DKFLSPT algorithm can raise 19%. |
PDF Full Text Request