Chinese Journal of Computers   Full Text
Title	Multicast Routing Algorithms with High Bandwidth Efficiency for LEO Satellite Networks
Authors	CHENG Lian-Zhen LIU Kai ZHANG Jun
Address	(CNS/ATM Laboratory of CAAC, Beihang University, Beijing 100083)
Year	2007
Issue	No.7(1064—1073)
Abstract &   Background	Abstract To resolve the channel resources waste problem of the typical source-based multicast routing algorithm in low earth orbit (LEO) satellite IP networks, this paper proposes a new core-based shared tree algorithm called the core-cluster combination shared tree (CCST) algorithm and its improved version (i.e. the w-CCST algorithm). The CCST algorithm consists of the dynamic approximate center (DAC) core selection method and the core-cluster combination multicast route construction method. The DAC method can adaptively select the optimal core node according to group distribution in the network. And the core-cluster combination method takes core node and its nearest group member in hops as initial core-cluster, and expands it to construct entire multicast tree with the lowest tree cost stepwise by a shortest path scheme between newly-generated core-cluster and surplus group members, which can greatly improve transport bandwidth utilization and transport efficiency. In the w-CCST algorithm, a weighted factor is used to make tradeoff between tree cost and end-to-end propagation delay. Therefore, tree cost can be increased a bit and meanwhile end-to-end propagation delay is decreased slightly to meet strict end-to-end delay requirements of some real-time multicast applications by adjusting the weighted factor. Performance of the CCST and w-CCST algorithms is compared with several other algorithms. And simulation results show that average tree cost of the CCST multicast tree is greatly lower than that of multicast tree of other algorithms, and its average end-to-end propagation delay is a bit higher than that of others, while average end-to-end propagation delay of the w-CCST multicast tree is lower than that of the CCST multicast tree. keywords satellite networks; LEO; multicast; shared tree; core selection background Satellite networks are suitable to forward multicast traffics due to broadcast capability and world-wide coverage. Compared to geosynchronous earth orbit(GEO) and medium earth orbit(MEO) satellite networks, low earth orbit(LEO) satellite networks have much lower end-to-end propagation delay, so that they can support IP-based real-time multicast services, such as video conferences. However, they have to face the challenge of scarce onboard resources (bandwidth, memory and processing capability etc.). Multicast routing is an important technique with bandwidth-efficiency. It disseminates packets from a source to all members of a multicast group. Instead of sending packets separately to each individual group member, a source just transmits one copy to its downstream branch node(s) along multicast tree, and every intermediate node and destination group member node receive the packet only from their upstream branch nodes, which results in that packets are transferred only once at each link of a multicast tree, and thus transmission bandwidth on entire delivery path can be greatly reused and saved. Multicast routing algorithms are used to determine multicast tree connecting source(s) and member nodes of a multicast group. And they are classified into source-based scheme and shared tree scheme. Typical source-based algorithms, such as DVMRP and MOSPF, are only appropriate to be applied in networks with a static or slowly changing network topology. And for typical shared tree algorithms such as CBT and PIM-SM, frequent information exchange will be induced by rapid movement of nodes and thus consume large amounts of bandwidth resources in a dynamic network. Therefore they are not suitable for satellite IP networks due to rapid satellite mobility and scarce onboard resources. Multicast routing algorithm(MRA) is a typical multicast routing algorithm for LEO satellite IP networks, while the created multicast trees have considerably high tree cost and consume large amounts of network transmission resources because only one-hop local information(i.e., next-hop directions) of current on-tree nodes to destinations are employed to merge routes by it. To resolve the channel resources waste problem of the MRA, a novel single-core shared tree algorithm called core-cluster combination-based shared tree(CCST) is proposed in this paper, which includes dynamic approximate center (DAC) core selection method and core-cluster combination multicast route construction scheme. And its improved version called the weighted CCST(w-CCST) algorithm is presented to make tradeoff between performance of tree cost and that of end-to-end propagation delay to support some real time multicast applications with strict end-to-end delay requirements. This work is a part of projects of the National Natural Science Foundation of China under grant No.60532030 and 10577005, and the Innovation Foundation of Aerospace Science, and Technology of China. These projects aim to develop fundamental theories and key technologies of the Integration of space, air and ground information networks. And satellite networks are indispensable integrant of it. The author’s research area covers routing protocols of satellite networks.