CN115955708B - Multicast routing switching method for low-orbit satellite networks based on virtual topology - Google Patents
Multicast routing switching method for low-orbit satellite networks based on virtual topology Download PDFInfo
- Publication number
- CN115955708B CN115955708B CN202211621811.4A CN202211621811A CN115955708B CN 115955708 B CN115955708 B CN 115955708B CN 202211621811 A CN202211621811 A CN 202211621811A CN 115955708 B CN115955708 B CN 115955708B
- Authority
- CN
- China
- Prior art keywords
- switching
- multicast tree
- node
- strategy
- path
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
Classifications
-
- Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y02—TECHNOLOGIES OR APPLICATIONS FOR MITIGATION OR ADAPTATION AGAINST CLIMATE CHANGE
- Y02D—CLIMATE CHANGE MITIGATION TECHNOLOGIES IN INFORMATION AND COMMUNICATION TECHNOLOGIES [ICT], I.E. INFORMATION AND COMMUNICATION TECHNOLOGIES AIMING AT THE REDUCTION OF THEIR OWN ENERGY USE
- Y02D30/00—Reducing energy consumption in communication networks
- Y02D30/70—Reducing energy consumption in communication networks in wireless communication networks
Landscapes
- Data Exchanges In Wide-Area Networks (AREA)
- Radio Relay Systems (AREA)
Abstract
The invention discloses a multicast route switching method of a low orbit satellite network based on virtual topology, which is characterized in that in each time slot of a system period, multicast route switching is carried out according to the following procedures, wherein discrete topology snapshots of a current time slot are obtained and represented by using an undirected graph, a multicast tree is calculated based on the undirected graph, the multicast tree is forwarded among nodes for use, switching strategies are selected from preset multiple switching strategies to update the current multicast tree according to the relation between a target switching node and the current multicast tree in response to switching requirements under different switching scenes, and a new multicast tree is forwarded among the nodes for use, and the multiple switching strategies comprise a path cutting strategy, a path expanding strategy, a traditional rerouting strategy and an improved rerouting strategy. The invention effectively reduces the calculated amount caused by frequent switching, improves the current situations of frequent switching of links, topology change and the like caused by high-speed dynamic performance of the low-orbit satellite, and improves the utilization rate of resources of the low-orbit satellite network.
Description
Technical Field
The invention belongs to the technical field of low-orbit satellite networks, and particularly relates to a multicast route switching method of a low-orbit satellite network based on virtual topology.
Background
With the rapid development of communication technology, low-orbit satellite networks gradually become a research hot spot by virtue of the characteristics of global coverage and low time delay and the support of wide-band communication prospects in the future at any time and any place, and are widely researched.
Due to the high speed and periodic motion characteristics of low-orbit satellites and the unique inter-satellite link connection relationship of low-orbit satellite networks, low-orbit satellite networks are not fully adapted to conventional terrestrial routing techniques. In order to solve the routing problem in the low orbit satellite network, the existing research is mainly divided into the following three categories according to the topology processing mode, namely virtual node routing, virtual topology snapshot routing and dynamic topology analysis routing.
The virtual topology snapshot route fully considers the characteristics of predictability, periodicity, regularity and the like of a satellite network, and the dynamic property of a low-orbit satellite is shielded to a certain extent by dividing the system period T of the satellite network into a plurality of time slots (T1, T2,..Tn), but the phase change is actually converted into rerouting in the time slots and rerouting among the time slots, so that the calculation of the low-orbit satellite route is simplified to a certain extent, and the technical problem of frequent route recalculation caused by frequent change of links still exists.
Disclosure of Invention
In order to solve the problems in the prior art, the invention provides a multicast route switching method of a low-orbit satellite network based on virtual topology.
The technical problems to be solved by the invention are realized by the following technical scheme:
The multicast route switching method of the low-orbit satellite network based on the virtual topology comprises the following steps of:
obtaining a discrete topology snapshot of a low orbit satellite network in a current time slot, and representing the discrete topology snapshot by using an undirected graph;
Calculating a multicast tree of the low-orbit satellite network by utilizing a shortest path algorithm based on the undirected graph so as to enable the multicast tree to be forwarded among nodes for use;
Responding to switching requirements under different switching scenes, selecting a switching strategy from preset multiple switching strategies to update the current multicast tree according to the relation between a target switching node and the current multicast tree, and forwarding and using a new multicast tree among nodes;
the plurality of switching strategies comprise a path cut-off strategy, a path expansion strategy, a traditional rerouting strategy and an improved rerouting strategy;
the traditional rerouting strategy is a routing strategy for calculating the shortest path for a starting node and a terminating node based on the discrete topological snapshot;
The improved rerouting strategy is based on a modified discrete topology snapshot, wherein the modified discrete topology snapshot is obtained after shielding non-path endpoints belonging to a current multicast tree in the discrete topology snapshot, and the path endpoints comprise a starting node and a terminating node when the shortest path is calculated.
Optionally, the switching scene comprises a multicast receiving switching scene with a target switching node as a target node;
Responding to the switching requirements under different switching scenes, selecting a switching strategy from preset multiple switching strategies to update the current multicast tree according to the relation between a target switching node and the current multicast tree, and forwarding and using a new multicast tree among nodes, wherein the method comprises the following steps:
Responding to the switching requirement of multicast receiving switching scene, counting new destination node number for all user terminals to be switched, and judging whether the counted value exceeds half of the original destination node number of the user terminals;
If the current multicast tree exceeds the current multicast tree, the traditional rerouting strategy is selected to recalculate the shortest path between the source node and the new destination node of each user terminal, and the current multicast tree is updated according to the calculation result;
If not, aiming at each user terminal of the destination node to be switched, selecting a switching strategy from the plurality of switching strategies to update the current multicast tree according to the topological relation between the new destination node and the current multicast tree;
After the update operation of the multicast tree is completed for all the user terminals to be switched to the destination node, the new multicast tree is forwarded among the nodes for use.
Optionally, the selecting, for each ue to switch the destination node, a switching policy from the multiple switching policies according to a topological relation between a new destination node and a current multicast tree, to update the current multicast tree includes:
for each user terminal to be handed over to the destination node,
If the new destination node belongs to the current multicast tree, the path cut-off strategy is selected to update the current multicast tree;
and if the new destination node does not belong to the current multicast tree, selecting a switching strategy from the rest strategies to update the current multicast tree.
Optionally, if the new destination node does not belong to the current multicast tree, selecting a switching policy from the remaining policies to update the current multicast tree, including:
If the new destination node does not belong to the current multicast tree, further judging whether the user terminal has the original destination node leading to the new destination node and the leading path meets the preset same track hop constraint and loop avoidance constraint;
when the judgment result is yes, the path expansion strategy is selected to update the current multicast tree;
And when the judgment result is negative, selecting the improved rerouting strategy to recalculate the shortest path between the original destination node and the new destination node of the user terminal, and updating the current multicast tree according to the calculation result.
Optionally, the switching scene comprises a multicast source switching scene with a target switching node as a source node;
Responding to the switching requirements under different switching scenes, selecting a switching strategy from preset multiple switching strategies to update the current multicast tree according to the relation between a target switching node and the current multicast tree, and forwarding and using a new multicast tree among nodes, wherein the method comprises the following steps:
Responding to the switching requirement under the multicast source switching scene, aiming at each user terminal needing to switch source nodes, selecting a switching strategy from a plurality of preset switching strategies according to the topological relation between the new source nodes and the current multicast tree, and updating the current multicast tree;
after the update operation of the multicast tree is completed for all the user terminals to be switched to the source node, the new multicast tree is forwarded among the nodes for use.
Optionally, for each ue to switch source nodes, according to the topological relation between its new source node and the current multicast tree, selecting a switching policy from preset multiple switching policies to update the current multicast tree, including:
For each user terminal to which the source node is to be handed over,
If the new source node belongs to the current multicast tree, further judging whether the new source node is a trunk node of the current multicast tree, if the new source node is the trunk node, directly switching, if the new source node is not the trunk node, selecting the traditional rerouting strategy to recalculate the shortest path between the new source node and the destination node of the user terminal, and updating the current multicast tree according to the calculation result;
if the new source node does not belong to the current multicast tree, further judging whether the user terminal has the original source node leading to the new source node and the leading path meets the preset same track hop constraint and loop avoidance constraint;
when the judgment result is yes, the path expansion strategy is selected to update the current multicast tree;
And when the judgment result is negative, selecting the improved rerouting strategy to recalculate the shortest path between the original source node and the new source node of the user terminal, and updating the current multicast tree according to the calculation result.
Optionally, the shortest path method comprises a single-source shortest path method, a multi-source shortest path method or an ant colony algorithm.
Optionally, the judging manner of the same track hop constraint includes:
Calculating [ S A/S ] and [ S B/S ] aiming at two nodes at two ends of a path to be judged, wherein S A、SB is the number of the two nodes respectively, s=n/p, n is the total number of nodes of the low-orbit satellite network, and p is the number of orbit planes;
If [ S A/S ] is equal to [ S B/S ], further judging whether |s- |S A-SB |is smaller than or equal to k, wherein k is a preset hop count, and [ (S ] represents rounding operation;
If |s- |S A-SB |is smaller than or equal to k, judging that the to-be-judged path meets the same track hop count constraint, otherwise, judging that the to-be-judged path does not meet the same track hop count constraint.
Optionally, the loop avoidance constraint judging method includes:
Judging whether all other nodes except the initial node of the path to be judged do not belong to the current multicast tree;
when the judgment result is yes, judging that the path to be judged meets the loop avoidance constraint;
And when the judging result is negative, judging that the path to be judged does not meet the loop avoidance constraint.
Optionally, the low orbit satellite network comprises an iridium satellite network.
In the multicast route switching method of the low-orbit satellite network based on the virtual topology, the characteristics of large satellite bandwidth and wide coverage range are utilized, the multicast route technology is applied to the low-orbit satellite network, and the low-orbit satellite multicast route switching method based on the virtual topology is researched by combining switching and routing. The invention uses the undirected graph to represent the discrete topological snapshot of a single time slot, calculates the multicast tree of the low-orbit satellite network by using the shortest path algorithm based on the undirected graph, and effectively combines the periodic motion characteristics of the low-orbit satellite. In addition, the invention responds to the switching requirements under different switching scenes, and selects the switching strategy from the preset various switching strategies to update the current multicast tree according to the relation between the target switching node and the current multicast tree, comprehensively considers the relation between the multicast tree before switching and the target switching node to be switched, and effectively combines the characteristics of the low orbit satellite network based on virtual topology. The invention discloses a method for switching between a current multicast tree and a current multicast tree, wherein the switching strategy which can be used in the invention comprises a path cut-off strategy, a path expansion strategy, a traditional rerouting strategy and an improved rerouting strategy, wherein the path cut-off strategy and the path expansion strategy do not need to recalculate the route, and in the improved rerouting strategy, the non-path end points belonging to the current multicast tree in a discrete topology snapshot are shielded to calculate the shortest path between the starting node and the ending node later, so that the number of the nodes participating in calculation is reduced, and the recalculated path does not conflict with the original path of the current multicast tree, thereby greatly changing the current multicast tree is not needed. Therefore, compared with the method for re-calculating the route when the link is changed in the prior art, the method effectively reduces the calculated amount caused by frequent switching and reduces the route maintenance cost and the maintenance difficulty, thereby improving the current situations of frequent switching, topology change and the like of the link caused by the high-speed dynamics of the low-orbit satellite and improving the utilization rate of resources of the low-orbit satellite network.
The present invention will be described in further detail with reference to the accompanying drawings.
Drawings
Fig. 1 is a flowchart of a multicast route switching method of a low-orbit satellite network based on a virtual topology according to an embodiment of the present invention;
fig. 2 is a flowchart of updating a multicast tree in a multicast reception handover scenario according to an embodiment of the present invention;
fig. 3 is a flowchart of updating a multicast tree in a multicast source switching scenario according to an embodiment of the present invention;
Fig. 4 shows paths and comparison results of performing multicast switching by using the method provided by the embodiment of the present invention and performing switching by completely using a conventional rerouting policy in a multicast receiving switching scenario;
Fig. 5 shows a comparison result of node change numbers of switching performed by the method provided by the embodiment of the present invention and switching performed by completely using a conventional rerouting policy in a multicast receiving switching scenario;
Fig. 6 shows paths and comparison results of switching by using the method provided by the embodiment of the present invention and switching by completely using the conventional rerouting policy in a multicast source switching scenario;
Fig. 7 shows a comparison result of node change numbers of switching performed by the method provided by the embodiment of the present invention and switching performed by completely using a conventional rerouting policy in a multicast source switching scenario;
Fig. 8 shows a curve comparison result of the number of nodes of the path change quantity along with the change of the new purpose when the method provided by the embodiment of the invention is used for switching and the conventional rerouting strategy is completely used for switching under the multicast receiving switching scene.
Detailed Description
The present invention will be described in further detail with reference to specific examples, but embodiments of the present invention are not limited thereto.
In the low-orbit satellite route switching technology based on virtual topology, many researches are beam-to-beam switching, and a scheme which is a mainstream for frequent switching of topology and links is to adopt a re-calculated re-routing strategy, but the re-routing has huge resource consumption and the characteristic of low-orbit satellite network cannot be effectively utilized.
In order to effectively reduce the calculated amount caused by frequent switching, thereby improving the current situations of frequent switching of links, topology change and the like caused by high-speed dynamics of a low-orbit satellite and improving the utilization rate of resources of a low-orbit satellite network, the embodiment of the invention provides a multicast route switching method of the low-orbit satellite network based on virtual topology, and the method is shown in fig. 1, and the multicast route switching is executed in each time slot of a system period of the low-orbit satellite network according to the following flow:
And S10, acquiring a discrete topology snapshot of the low orbit satellite network in the current time slot, and representing the discrete topology snapshot by using an undirected graph.
It can be understood that when dividing the system period into a plurality of time slots, the time slot division can be equally spaced, or the division can be unequal spaced and considered in topology change, so that a discrete topology snapshot topo= { G 1,G2,…,Gt } corresponding to each time slot can be obtained, wherein the network topology in each time slot is fixed, an undirected graph g= { V, E } can be used for representing the satellite network topology condition of a single time slot, V represents the set of all satellite nodes in the time slot, E represents the set of all satellite links in the time slot, the satellite links are the connection relations of the nodes in the undirected graph, and the connection relations are actually stored by using an adjacency matrix.
And S20, calculating a multicast tree of the low-orbit satellite network by utilizing a shortest path algorithm based on the undirected graph so that the multicast tree is forwarded among nodes for use.
Specifically, from the global aspect, centralized and unified calculation and processing are performed by using a shortest path algorithm, and the multicast routing information meeting the conditions is obtained through calculation processing to form a multicast tree, so that the multicast tree is forwarded and used by each satellite node. The shortest path method includes, but is not limited to, a single-source shortest path method, a multi-source shortest path method, or an ant colony algorithm.
And S30, responding to the switching requirements under different switching scenes, selecting a switching strategy from preset multiple switching strategies to update the current multicast tree according to the relation between the target switching node and the current multicast tree, and forwarding and using a new multicast tree among the nodes.
The plurality of switching strategies comprise a path cut-off strategy, a path expansion strategy, a traditional rerouting strategy and an improved rerouting strategy.
It can be understood that the path cut-off strategy is a strategy for cutting off part of paths in the multicast tree, the path expansion strategy is a strategy for expanding new paths on the basis of the original multicast tree, and the traditional rerouting strategy is a routing strategy for calculating the shortest paths for the starting node and the ending node based on discrete topology snapshot.
Compared with the traditional rerouting strategy, the improved rerouting strategy in the embodiment of the invention calculates the shortest path routing strategy for the starting node and the ending node based on the modified discrete topology snapshot, wherein the modified discrete topology snapshot is obtained after shielding the non-path end points belonging to the current multicast tree in the discrete topology snapshot, and the path end points comprise the starting node and the ending node when calculating the shortest path, so that the corresponding non-path end points are nodes which are not path end points in the shortest path.
The core idea of this step S30 is to make full use of the route configuration information (i.e. the multicast tree) before the handover occurs and the relation (including the positional relation, etc.) between the new node to be handed off (i.e. the target handover node) and the multicast tree, and to select a suitable handover policy according to the specific conditions in the specific handover scenario.
Specifically, in consideration of virtual topology and multicast, when switching occurs, a user terminal of a low-orbit satellite network always searches for satellite node connection, and relative to the movement of the user terminal, the rapid movement between satellites influences the switching, so that the switching is mainly performed by changing accessed satellite nodes, the scene is still an on-satellite topology, and the actual switching scene can be basically divided into three types, including three situations of multicast receiving switching scene with a target switching node as a target node, multicast source switching scene with the target switching node as a source node and snapshot inter-time slot switching scene.
For the switching scene among the time slots of the snapshots, as the snapshots are switched, the on-board nodes correspondingly connected with the user terminals are also changed, and the topology connection in the corresponding snapshots is also changed and is changed greatly, the method is applicable to rerouting, namely, when each new time slot arrives, the multicast tree of the low-orbit satellite network is recalculated by utilizing a shortest path algorithm based on the undirected graph corresponding to the time slot.
For the multicast receiving switching scene, the situation that the default multicast destination node of the scene may change is that the destination nodes connected with the user terminal are switched, namely the destination nodes connected with the user terminal are switched due to the relative motion of the user terminal and the satellite, and the situation comprises that 1, the destination nodes connected with the user terminal are switched, 2, the user terminal is changed, and the connected destination nodes are switched. In the scene, as long as the switched path is basically consistent with the original path, the packet loss rate can be ensured to be less.
Specifically, referring to fig. 2, when the switching scenario is a multicast receiving switching scenario, in response to a switching requirement in the multicast receiving switching scenario, according to a relationship between a target switching node and a current multicast tree, a switching policy is selected from a plurality of preset switching policies to update the current multicast tree, and a new multicast tree is forwarded between nodes for use, including:
(1) In response to the switching requirement in the multicast receiving switching scene, the user terminals facing all the destination nodes to be switched count new destination node numbers (i.e. the user terminals facing all the destination nodes to be switched count the number of the destination nodes to be tangential) and judge whether the counted value exceeds half of the original destination node numbers of the user terminals.
Specifically, in response to a switching requirement in a multicast receiving switching scenario, a set of new destination nodes of all user terminals to be switched is counted, where the set is expressed as:
Dchange＝{Dnew1,Dnew2,…,Dnewm},1≤m≤n;
Where m represents the number of nodes in D change and n represents the total number of satellite nodes of the low-orbit satellite network.
Then, it is determined whether m exceeds half the number of original destination nodes w of the user terminals, that is, whether m > w/2 is established.
(2) If the current multicast tree exceeds the current multicast tree, i.e. if m is more than w/2, a traditional rerouting strategy is selected to recalculate the shortest path between the source node and the new destination node of each user terminal, and the current multicast tree is updated according to the calculation result.
Specifically, the source node of the user terminal is set as the initial node of the shortest path to be calculated, the new destination node is set as the termination node of the shortest path, the shortest path between the original destination node and the new destination node of each user terminal is uniformly calculated by utilizing a shortest path algorithm on the basis of the nodes contained in the discrete topology snapshot and the connection relation among the nodes, the multicast routing information meeting the conditions is obtained by calculation, and the multicast routing information is used for forming a multicast tree to replace the current multicast tree, namely the update of the current multicast tree is completed.
(3) If the number m is not more than or equal to w/2, selecting a switching strategy from the multiple switching strategies to update the current multicast tree according to the topological relation between the new destination node and the current multicast tree for each user terminal of the destination node to be switched.
(4) After the update operation of the multicast tree is completed for all the user terminals to be switched to the destination node, the new multicast tree is forwarded among the nodes for use.
Specifically, in the step (3), if m is less than or equal to w/2, as shown in fig. 2, for each user terminal to be switched to a destination node, if a new destination node belongs to a current multicast tree, a path cut-off strategy is selected to update the current multicast tree, and if the new destination node does not belong to the current multicast tree, a switching strategy is selected from the remaining strategies to update the current multicast tree. It is understood that the remaining policies referred to herein include path expansion policies, conventional rerouting policies, and improved rerouting policies.
The method comprises the steps of providing a source node of a user terminal as S, wherein the source node of the user terminal is assumed to be S, the new destination node comprises D 1,D2…Dw, an edge set related in paths from S to D 1,D2…Dw respectively is E tree＝{edges1,edges2,…,edgesw, an intermediate node passing through the path comprises M 1,M2,…,Mt, and a multicast route node set related to the user terminal in the current multicast number is V tree＝{S,M1,M2,…,Mt,D1,D2,…,Dw. If Node change∈[D1,D2,…,Dw is located on the current multicast tree, namely Node change∈V＝{Node1,Node2,Node3,…,Noden, the current multicast tree is updated by adopting a path cut-off strategy.
More specifically, assuming that edge set where S is located to the original destination Node of the user terminal is represented by edge i (1. Ltoreq.i≤w), if Node change is exactly on the path formed by edge i (1. Ltoreq.i≤w) when Node change∈V＝{Node1,Node2,Node3,…,Noden } is present, then only the edge of edge i from S to Node change needs to be reserved, and the path on the original destination Node is cut off from the path irrelevant to Node change. If Node change is not on the path formed by edges i, it is only necessary to keep the path from S to Node change in the current multicast tree, and the same cut-off process is performed on the path of the original destination Node as the path not related to Node change.
For the case that the new destination node of the user terminal does not belong to the current multicast tree, referring to fig. 2, it can be further determined whether the original destination node of the user terminal leads to the new destination node thereof, and the leading path meets the preset same track hop constraint and loop avoidance constraint, where it can be determined whether the original destination node of the user terminal can lead to the new destination node thereof according to the discrete topology snapshot of the current time slot.
When the judgment result is yes, namely when the user terminal has the original destination node leading to the new destination node and simultaneously meets the constraint of the same track hop count and the constraint of loop avoidance, a path expansion strategy is selected to update the current multicast tree, and specifically, the new destination node is added in the original multicast tree, and the paths of the original destination node and the new destination node are added.
And when the judgment result is negative, selecting an improved rerouting strategy to recalculate the shortest path between the original destination node and the new destination node of the user terminal, and updating the current multicast tree according to the calculation result.
Specifically, when the judgment result is no, setting the original destination node of the user terminal as the starting node, setting the new destination node as the ending node, shielding all nodes which belong to the current multicast tree and are except the original destination node in the discrete topology snapshot to obtain a modified discrete topology snapshot, and then uniformly calculating the shortest paths between the original destination node and the new destination node of each user terminal by utilizing a shortest path algorithm on the basis of the nodes contained in the modified discrete topology snapshot and the connection relation among the nodes, and adding the newly calculated paths into the current multicast tree to finish updating the current multicast tree.
It should be noted that, although the rerouting policy is used here, the updated multicast tree is only added with some new destination nodes and paths between the new destination nodes and the original destination nodes compared with the original multicast tree, so most structures of the updated multicast tree are the same as those of the original multicast tree, and the switching frequency is not high.
The above-described determination as to whether the same-track hop count constraint is satisfied or not is aimed at avoiding the occurrence of a loop. Specifically, when a path leading from an original destination node of a user terminal to a new destination node is added to a current multicast tree, the new destination node becomes a leaf node in the new multicast tree. At this time, if the new destination node and the original destination node do not meet the constraint of the same track hop count and the constraint of loop avoidance, that is, the distance between the new destination node and the original destination node exceeds the constraint value of the preset hop count, or the calculated path and the path on the current multicast tree overlap, the level difference of the new destination node and the original destination node in the current multicast tree is very large, and the possibility of having a loop is relatively high.
In order to make the layout of the specification clear, a detailed description will be given of a specific judgment mode of the same track hop count constraint and the loop avoidance constraint.
The multicast source switching scene mainly comprises two cases, namely 1, switching of source nodes connected by a user terminal in a fixed mode and 2, switching of the source nodes caused by change of the user terminal connected with the source nodes.
Specifically, when the switching scenario is a multicast source switching scenario, step S30 specifically includes:
(1) Responding to the switching requirement under the multicast source switching scene, aiming at each user terminal needing to switch source nodes, selecting a switching strategy from a plurality of preset switching strategies according to the topological relation between the new source nodes and the current multicast tree, and updating the current multicast tree;
(2) After the update operation of the multicast tree is completed for all the user terminals to be switched to the source node, the new multicast tree is forwarded among the nodes for use.
Specifically, referring to fig. 3, in the step (1), for each ue to switch source nodes, if the new source node to be tangential belongs to the current multicast tree, whether the new source node is a trunk node of the current multicast tree is further determined, if the new source node is the trunk node, the original source node is directly replaced by the new source node, if the new source node is not the trunk node, a shortest path between the new source node and the destination node of the ue is recalculated by selecting a conventional rerouting strategy, and the current multicast tree is updated according to the calculation result.
More specifically, when the new source node is not a trunk node on the multicast tree, the destination node of the user terminal is set as an initial node, and the new source node is set as a termination node, and on the basis of the connection relationship between the nodes included in the discrete topology snapshot, the shortest path between the new source node and the destination node of the user terminal is uniformly calculated by using a shortest path algorithm, the calculation processing obtains the multicast routing information meeting the condition, and the multicast routing information is used for forming a multicast tree to replace the current multicast tree, so that the update of the current multicast tree is completed.
It can be understood that, because the recalculation performed by the conventional rerouting strategy is adopted at this time, the calculated multicast routing information is greatly changed relative to the original multicast tree, and therefore, the multicast tree formed by the calculated multicast routing information is directly used to replace the current multicast tree.
If the new source node to be tangential of the user terminal does not belong to the current multicast tree, as shown in fig. 3, further judging whether the user terminal has the original source node leading to the new source node and the leading path meets the preset same-track hop constraint and loop avoidance constraint;
When the judgment result is yes, namely when the original source node of the user terminal leads to the new source node of the user terminal and simultaneously meets the constraint of the same track hop count and the constraint of loop avoidance, a path expansion strategy is selected to update the current multicast tree;
And when the judgment result is negative, selecting an improved rerouting strategy to recalculate the shortest path between the original source node and the new source node of the user terminal, and updating the current multicast tree according to the calculation result.
And then uniformly calculating the shortest paths between the original source node and the new source node of each user terminal by utilizing a shortest path algorithm on the basis of the connection relation between the nodes contained in the modified discrete topology snapshot and the nodes, and adding the newly calculated paths into the current multicast tree to finish updating the current multicast tree.
Although the rerouting strategy is used here, the updated multicast tree is only added with some new source nodes and paths between the new source nodes and the original source nodes compared with the original multicast tree, so that most structures of the updated multicast tree are the same as the original multicast tree, and the switching frequency is not high.
The following describes a determination method of the same track hop count constraint and the loop avoidance constraint.
Firstly, a judging mode of the same track hop limit is described, which specifically comprises the following steps:
(a) Calculating [ S A/S ] and [ S B/S ] aiming at two nodes at two ends of a path to be judged, wherein S A、SB is the number of the two nodes respectively, s=n/p, n is the total number of nodes of a low-orbit satellite network, and p is the number of orbit planes;
(b) If [ S A/S ] is equal to [ S B/S ], further judging whether |s- |S A-SB |k is not more than k, wherein k is a preset hop count, k can be flexibly adjusted according to the actual low-orbit satellite network, weather and other factors, and [ (S ] represents rounding operation.
(C) If the S & lt- & gt S A-SB & lt & gtk is met, judging that the to-be-judged path meets the same track hop count constraint, otherwise, judging that the to-be-judged path does not meet the same track hop count constraint.
It can be understood that, for the multicast receiving switching scenario, the path to be determined is the path from the original destination node to the new destination node of the user terminal, so that only the numbers of the two nodes are required to be obtained, and the same track hop constraint determination is performed according to the flows of the steps (a) - (c). And for the multicast source switching scene, the path to be judged is the path of the original source node of the user terminal to the new source node to be tangential, and the same path hop number constraint judgment is carried out according to the processes of the steps (a) - (c) by only obtaining the numbers of the two nodes.
Then, a judgment mode of loop avoidance constraint is described, specifically comprising the following steps:
(a) Judging whether all other nodes except the initial node of the path to be judged do not belong to the current multicast tree;
(b) When the judgment result is yes, judging that the path to be judged meets the loop avoidance constraint;
(c) And when the judging result is negative, judging that the path to be judged does not meet the loop avoidance constraint.
It can be understood that, as long as all the other nodes except the initial node in the path to be determined do not belong to the current multicast tree, after the path to be determined is updated to the multicast tree, no loop is formed in the updated multicast tree. For the multicast receiving switching scenario, the path to be judged is the path from the original destination node to the new destination node of the user terminal, wherein the original destination node is the initial node of the path to be judged. For the multicast source switching scenario, the path to be determined is the path from the original source node of the user terminal to the new source node to be tangential, wherein the original source node is the initial node of the path to be determined.
In the multicast route switching method of the low-orbit satellite network based on the virtual topology, provided by the embodiment of the invention, the characteristics of large satellite bandwidth and wide coverage range are utilized, the multicast route technology is applied to the low-orbit satellite network, and the low-orbit satellite multicast route switching method based on the virtual topology is researched by combining switching and routing. The embodiment of the invention uses the undirected graph to represent the discrete topological snapshot of a single time slot, calculates the multicast tree of the low-orbit satellite network by using the shortest path algorithm based on the undirected graph, and effectively combines the periodic motion characteristics of the low-orbit satellite. In addition, the embodiment of the invention responds to the switching requirements under different switching scenes, selects the switching strategy from the preset multiple switching strategies to update the current multicast tree according to the relation between the target switching node and the current multicast tree, comprehensively considers the relation between the multicast tree before switching and the target switching node to be switched, and effectively combines the characteristics of the low orbit satellite network based on virtual topology. The switching strategy which can be used in the embodiment of the invention comprises a path cut-off strategy, a path expansion strategy, a traditional rerouting strategy and an improved rerouting strategy, wherein the path cut-off strategy and the path expansion strategy do not need to recalculate the route, and in the improved rerouting strategy, the non-path end points belonging to the current multicast tree in the discrete topology snapshot are shielded to calculate the shortest path between the starting node and the ending node later, so that the number of the nodes participating in calculation is reduced, and the recalculated path does not conflict with the original path of the current multicast tree, thereby needing not to greatly change the current multicast tree. Therefore, compared with the method for re-calculating the route when the link is changed in the prior art, the method effectively reduces the calculated amount caused by frequent switching and reduces the route maintenance cost and the maintenance difficulty, thereby improving the current situations of frequent switching, topology change and the like of the link caused by the high-speed dynamics of the low-orbit satellite and improving the utilization rate of resources of the low-orbit satellite network.
The embodiment of the invention mainly utilizes the characteristic of change of topology regularity between time slots of the low-orbit satellite network based on virtual topology, refines switching scenes in the low-orbit satellite network based on virtual topology, combines the similarity among various switching scenes, updates and processes routing information on the basis of the original path, reduces the switching times compared with the frequent rerouting mode, and can effectively reduce the calculation cost caused by frequent rerouting.
The low orbit satellite network in the embodiment of the invention can comprise an iridium satellite network, but is not limited to the iridium satellite network. The iridium network comprises 66 satellites which are uniformly distributed on six orbit surfaces, and each satellite has four links in front, back, left and right, wherein the links in the orbits are always connected, and the links between the orbits are sometimes influenced by reverse slots and polar regions and are possibly disconnected.
The method provided by the embodiment of the invention can be applied to electronic equipment. In practical applications, the electronic device may be a desktop computer, a portable computer, a ground station of a low-orbit satellite network. And are not limited thereto.
Fig. 4 shows a path and a comparison result of performing multicast switching by using the method provided by the embodiment of the present invention and performing switching by completely using the conventional rerouting policy, where the "hybrid switching policy" corresponds to the switching method of the embodiment of the present invention, the "rerouting policy" corresponds to the switching method of completely using the conventional rerouting policy, and fig. 5 to 8 also correspond to the same, and according to the comparison of data in fig. 4, the paths of the two methods are substantially equal, which illustrates that the path obtained by the embodiment of the present invention and the optimal path obtained by the conventional rerouting remain consistent.
Fig. 5 shows comparison results of node change numbers of the switching performed by the method provided by the embodiment of the invention and the switching performed by the completely conventional rerouting strategy in a multicast receiving switching scene, and the comparison results show that the embodiment of the invention effectively reduces the node change numbers and correspondingly reduces the switching times.
In fig. 6, paths and comparison results of switching by using the method provided by the embodiment of the present invention and switching by completely using the conventional rerouting policy are shown in a multicast source switching scenario, and in comparison, the paths of the embodiment of the present invention are larger, which illustrates that the path sum of the embodiment of the present invention is slightly increased compared with the optimal path sum obtained by the conventional rerouting policy.
Fig. 7 shows the comparison result of the node change number of the switching performed by the method provided by the embodiment of the invention and the switching performed by the conventional rerouting strategy in the multicast source switching scene, and the comparison shows that the node change number of the embodiment of the invention is less, and the corresponding switching times are less.
Fig. 8 shows the curve comparison result of the path change quantity along with the change node number of the new purpose when the method provided by the embodiment of the invention is used for switching and the traditional rerouting strategy is completely used for switching under the multicast receiving switching scene, and the comparison shows that the change node number of the embodiment of the invention is always lower than the prior art, thereby proving the effectiveness of the method provided by the embodiment of the invention.
The above completes the scheme description of the multicast route switching method of the low-orbit satellite network based on the virtual topology provided by the embodiment of the invention.
It should be noted that the terms "first," "second," and the like are used for distinguishing between similar objects and not necessarily for describing a particular sequential or chronological order. It is to be understood that the data so used may be interchanged where appropriate such that the disclosed embodiments described herein may be implemented in other sequences than those illustrated or otherwise described herein. The implementations described in the following exemplary examples are not representative of all implementations consistent with the present disclosure. Rather, they are merely examples of apparatus and methods consistent with aspects of the present disclosure.
In the description of the present specification, a description referring to terms "one embodiment," "some embodiments," "examples," "specific examples," or "some examples," etc., means that a particular feature or characteristic described in connection with the embodiment or example is included in at least one embodiment or example of the present invention. In this specification, schematic representations of the above terms are not necessarily directed to the same embodiment or example. Furthermore, the particular features or characteristics described may be combined in any suitable manner in any one or more embodiments or examples. Further, one skilled in the art can engage and combine the different embodiments or examples described in this specification.
Although the invention is described herein in connection with various embodiments, other variations to the disclosed embodiments can be understood and effected by those skilled in the art in practicing the claimed invention, from a study of the drawings and the disclosure. In the description of the present invention, the word "comprising" does not exclude other elements or steps, the "a" or "an" does not exclude a plurality, and the "a" or "an" means two or more, unless specifically defined otherwise. Moreover, some measures are described in mutually different embodiments, but this does not mean that these measures cannot be combined to produce a good effect.
It will be apparent to those skilled in the art that embodiments of the present invention may be provided as a method, apparatus (device), or computer program product. Accordingly, the present invention may take the form of an entirely hardware embodiment, an entirely software embodiment, or an embodiment combining software and hardware aspects all generally referred to herein as a "module" or "system. Furthermore, the present invention may take the form of a computer program product embodied on one or more computer-usable storage media (including, but not limited to, disk storage, CD-ROM, optical storage, and the like) having computer-usable program code embodied therein. A computer program may be stored/distributed on a suitable medium supplied together with or as part of other hardware, but may also take other forms, such as via the Internet or other wired or wireless telecommunication systems.
The present invention is described with reference to flowchart illustrations and/or block diagrams of methods, apparatus (devices) and computer program products according to embodiments of the invention. It will be understood that each flow and/or block of the flowchart illustrations and/or block diagrams, and combinations of flows and/or blocks in the flowchart illustrations and/or block diagrams, can be implemented by computer program instructions. These computer program instructions may be provided to a processor of a general purpose computer, special purpose computer, embedded processor, or other programmable data processing apparatus to produce a machine, such that the instructions, which execute via the processor of the computer or other programmable data processing apparatus, create means for implementing the functions specified in the flowchart flow or flows and/or block diagram block or blocks.
These computer program instructions may also be stored in a computer-readable memory that can direct a computer or other programmable data processing apparatus to function in a particular manner, such that the instructions stored in the computer-readable memory produce an article of manufacture including instruction means which implement the function specified in the flowchart flow or flows and/or block diagram block or blocks.
These computer program instructions may also be loaded onto a computer or other programmable data processing apparatus to cause a series of operational steps to be performed on the computer or other programmable apparatus to produce a computer implemented process such that the instructions which execute on the computer or other programmable apparatus provide steps for implementing the functions specified in the flowchart flow or flows and/or block diagram block or blocks.
The foregoing is a further detailed description of the invention in connection with the preferred embodiments, and it is not intended that the invention be limited to the specific embodiments described. It will be apparent to those skilled in the art that several simple deductions or substitutions may be made without departing from the spirit of the invention, and these should be considered to be within the scope of the invention.
Claims (7)
1. The multicast route switching method of the low-orbit satellite network based on the virtual topology is characterized in that in each time slot of the system period of the low-orbit satellite network, the multicast route switching is executed according to the following flow:
obtaining a discrete topology snapshot of a low orbit satellite network in a current time slot, and representing the discrete topology snapshot by using an undirected graph;
Calculating a multicast tree of the low-orbit satellite network by utilizing a shortest path algorithm based on the undirected graph so as to enable the multicast tree to be forwarded among nodes for use;
Responding to switching requirements under different switching scenes, selecting a switching strategy from preset multiple switching strategies to update the current multicast tree according to the relation between a target switching node and the current multicast tree, and forwarding and using a new multicast tree among nodes;
the plurality of switching strategies comprise a path cut-off strategy, a path expansion strategy, a traditional rerouting strategy and an improved rerouting strategy;
the traditional rerouting strategy is a routing strategy for calculating the shortest path for a starting node and a terminating node based on the discrete topological snapshot;
The improved rerouting strategy is a routing strategy for calculating the shortest path for an initial node and a termination node based on a modified discrete topology snapshot, wherein the modified discrete topology snapshot is obtained after shielding a non-path endpoint belonging to a current multicast tree in the discrete topology snapshot;
the switching scene comprises a multicast receiving switching scene with a target switching node as a target node;
Responding to the switching requirements under different switching scenes, selecting a switching strategy from preset multiple switching strategies to update the current multicast tree according to the relation between a target switching node and the current multicast tree, and forwarding and using a new multicast tree among nodes, wherein the method comprises the following steps:
Responding to the switching requirement of multicast receiving switching scene, counting new destination node number for all user terminals to be switched, and judging whether the counted value exceeds half of the original destination node number of the user terminals;
If the current multicast tree exceeds the current multicast tree, the traditional rerouting strategy is selected to recalculate the shortest path between the source node and the new destination node of each user terminal, and the current multicast tree is updated according to the calculation result;
If not, aiming at each user terminal of the destination node to be switched, selecting a switching strategy from the plurality of switching strategies to update the current multicast tree according to the topological relation between the new destination node and the current multicast tree;
After the update operation of the multicast tree is completed for all the user terminals of the destination node to be switched, the new multicast tree is forwarded among the nodes for use;
the step of selecting a switching strategy from the plurality of switching strategies to update the current multicast tree according to the topological relation between the new destination node and the current multicast tree by the user terminal aiming at each destination node to be switched comprises the following steps:
for each user terminal to be handed over to the destination node,
If the new destination node belongs to the current multicast tree, the path cut-off strategy is selected to update the current multicast tree;
If the new destination node does not belong to the current multicast tree, selecting a switching strategy from the rest strategies to update the current multicast tree;
and if the new destination node does not belong to the current multicast tree, selecting a switching strategy from the rest strategies to update the current multicast tree, wherein the method comprises the following steps:
If the new destination node does not belong to the current multicast tree, further judging whether the user terminal has the original destination node leading to the new destination node and the leading path meets the preset same track hop constraint and loop avoidance constraint;
when the judgment result is yes, the path expansion strategy is selected to update the current multicast tree;
And when the judgment result is negative, selecting the improved rerouting strategy to recalculate the shortest path between the original destination node and the new destination node of the user terminal, and updating the current multicast tree according to the calculation result.
2. The method for switching multicast routes of a low-orbit satellite network based on virtual topology according to claim 1, wherein the switching scenario further comprises a multicast source switching scenario in which a target switching node is a source node;
Responding to the switching requirements under different switching scenes, selecting a switching strategy from preset multiple switching strategies to update the current multicast tree according to the relation between a target switching node and the current multicast tree, and forwarding and using a new multicast tree among nodes, wherein the method comprises the following steps:
Responding to the switching requirement under the multicast source switching scene, aiming at each user terminal needing to switch source nodes, selecting a switching strategy from a plurality of preset switching strategies according to the topological relation between the new source nodes and the current multicast tree, and updating the current multicast tree;
after the update operation of the multicast tree is completed for all the user terminals to be switched to the source node, the new multicast tree is forwarded among the nodes for use.
3. The method for switching multicast routes of a low-orbit satellite network based on virtual topology according to claim 1, wherein the selecting a switching policy from a plurality of preset switching policies to update a current multicast tree according to the topological relation between a new source node and the current multicast tree for each user terminal to be switched, comprises:
For each user terminal to which the source node is to be handed over,
If the new source node belongs to the current multicast tree, further judging whether the new source node is a trunk node of the current multicast tree, if the new source node is the trunk node, directly switching, if the new source node is not the trunk node, selecting the traditional rerouting strategy to recalculate the shortest path between the new source node and the destination node of the user terminal, and updating the current multicast tree according to the calculation result;
if the new source node does not belong to the current multicast tree, further judging whether the user terminal has the original source node leading to the new source node and the leading path meets the preset same track hop constraint and loop avoidance constraint;
when the judgment result is yes, the path expansion strategy is selected to update the current multicast tree;
And when the judgment result is negative, selecting the improved rerouting strategy to recalculate the shortest path between the original source node and the new source node of the user terminal, and updating the current multicast tree according to the calculation result.
4. The method for switching multicast routes for a low-orbit satellite network based on a virtual topology according to claim 1, wherein the shortest path method comprises a single-source shortest path method, a multi-source shortest path method or an ant colony algorithm.
5. A method for multicast routing handover of a low-orbit satellite network based on virtual topology according to claim 1 or 3, wherein the determination of the same-orbit hop count constraint comprises:
for two nodes at two ends of the path to be judged, calculating AndWherein, the method comprises the steps of,The numbers of the two nodes are respectively,,For the total number of nodes of the low-orbit satellite network,The number of track planes is the number of track planes;
If it is Equal toFurther judgeWhether or not it is true, k is a preset hop count,Representing a rounding operation;
If it is And if yes, judging that the to-be-judged path meets the same track hop count constraint, otherwise, judging that the to-be-judged path does not meet the same track hop count constraint.
6. A method for multicast routing handover of a low-orbit satellite network based on virtual topology according to claim 1 or 3, wherein the determining manner of the loop avoidance constraint comprises:
Judging whether all other nodes except the initial node of the path to be judged do not belong to the current multicast tree;
when the judgment result is yes, judging that the path to be judged meets the loop avoidance constraint;
And when the judging result is negative, judging that the path to be judged does not meet the loop avoidance constraint.
7. The method for multicast routing handover for a virtual topology based low-orbit satellite network according to claim 1, wherein the low-orbit satellite network comprises an Iridium network.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202211621811.4A CN115955708B (en) | 2022-12-16 | 2022-12-16 | Multicast routing switching method for low-orbit satellite networks based on virtual topology |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202211621811.4A CN115955708B (en) | 2022-12-16 | 2022-12-16 | Multicast routing switching method for low-orbit satellite networks based on virtual topology |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN115955708A CN115955708A (en) | 2023-04-11 |
| CN115955708B true CN115955708B (en) | 2025-07-01 |
Family
ID=87286950
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202211621811.4A Active CN115955708B (en) | 2022-12-16 | 2022-12-16 | Multicast routing switching method for low-orbit satellite networks based on virtual topology |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN115955708B (en) |
Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN107370536A (en) * | 2017-07-19 | 2017-11-21 | 哈尔滨工业大学深圳研究生院 | Satellite network multi-broadcast routing method and system based on minimum connected dominating set |
| CN109586785A (en) * | 2019-01-07 | 2019-04-05 | 南京邮电大学 | Low-track satellite network routing policy based on K shortest path first |
Family Cites Families (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20050105524A1 (en) * | 2003-11-17 | 2005-05-19 | Hughes Electronics Corporation | System and method for provisioning of route information in a meshed communications network |
| JP5600215B2 (en) * | 2010-10-04 | 2014-10-01 | テルコーディア テクノロジーズ インコーポレイテッド | Method and system for determining a route in an LEO satellite network using bandwidth and priority awareness and adaptive routing |
| US10374871B2 (en) * | 2014-09-16 | 2019-08-06 | CloudGenix, Inc. | Methods and systems for business intent driven policy based network traffic characterization, monitoring and control |
| CN108989223B (en) * | 2018-06-13 | 2021-09-03 | 昆宇蓝程（北京）科技有限责任公司 | Satellite routing method under strong link constraint condition |
-
2022
- 2022-12-16 CN CN202211621811.4A patent/CN115955708B/en active Active
Patent Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN107370536A (en) * | 2017-07-19 | 2017-11-21 | 哈尔滨工业大学深圳研究生院 | Satellite network multi-broadcast routing method and system based on minimum connected dominating set |
| CN109586785A (en) * | 2019-01-07 | 2019-04-05 | 南京邮电大学 | Low-track satellite network routing policy based on K shortest path first |
Also Published As
| Publication number | Publication date |
|---|---|
| CN115955708A (en) | 2023-04-11 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Liu et al. | Scalable routing in delay tolerant networks | |
| KR100450407B1 (en) | A Multi QoS Path Computation Method | |
| Bian et al. | Boosting named data networking for data dissemination in urban VANET scenarios | |
| CN113438156B (en) | A Time Deterministic Multipath Routing Method Based on Time Expansion Graph | |
| CN107370536A (en) | Satellite network multi-broadcast routing method and system based on minimum connected dominating set | |
| CN117424636A (en) | Functional domain routing method for mega-constellations based on non-dominated sorting genetic algorithm | |
| CN111917645A (en) | SDN-based path optimization method and system for mobile network | |
| CN118264605B (en) | Routing direction determining method and device, storage medium and electronic equipment | |
| CN112637061B (en) | Dynamic multi-factor path calculation method based on heuristic algorithm | |
| Misra et al. | Routing bandwidth guaranteed paths for traffic engineering in WiMAX mesh networks | |
| AU2013370779B2 (en) | Multi-protocol routing system and method driven by integration of applications and networks | |
| CN115955708B (en) | Multicast routing switching method for low-orbit satellite networks based on virtual topology | |
| CN106982162B (en) | Method, apparatus and system for forwarding traffic flow | |
| RU2623450C2 (en) | Methods and devices for message routing using stem resources of radio access meshed networks | |
| US8023412B2 (en) | Systems and methods for modeling a mobile ad hoc wireless network | |
| US12192097B2 (en) | System and methods for computing flooding topology | |
| CN107682259A (en) | Method for searching and device | |
| CN109412950B (en) | On-path cache-based data distribution method in satellite-ground hybrid network | |
| Dong et al. | Robust software defined multicast in broadband LEO constellations | |
| Gotani et al. | OpenFlow based information flow control considering route switching cost | |
| Ben-Asher et al. | Ad-hoc routing using virtual coordinates based on rooted trees | |
| CN113315702B (en) | A method, device and system for transmitting node identification | |
| CN113794600A (en) | Method and device for searching transmission circuit route | |
| CN108259343B (en) | Routing strategy matching method and device | |
| Krishna et al. | Cognitive radio enabled cache map-and-route using context mapping and decision making approach in software defined networks |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |