[go: up one dir, main page]

CN116155796B - A low-overhead OSPF protocol improvement method for large-scale polar orbit constellations - Google Patents

A low-overhead OSPF protocol improvement method for large-scale polar orbit constellations

Info

Publication number
CN116155796B
CN116155796B CN202211687006.1A CN202211687006A CN116155796B CN 116155796 B CN116155796 B CN 116155796B CN 202211687006 A CN202211687006 A CN 202211687006A CN 116155796 B CN116155796 B CN 116155796B
Authority
CN
China
Prior art keywords
link
time
time slot
track
state
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
Application number
CN202211687006.1A
Other languages
Chinese (zh)
Other versions
CN116155796A (en
Inventor
李文峰
王宇成
张运泽
赵康僆
方元
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Nanjing University
Original Assignee
Nanjing University
Priority date (The priority date 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 date listed.)
Filing date
Publication date
Application filed by Nanjing University filed Critical Nanjing University
Priority to CN202211687006.1A priority Critical patent/CN116155796B/en
Publication of CN116155796A publication Critical patent/CN116155796A/en
Application granted granted Critical
Publication of CN116155796B publication Critical patent/CN116155796B/en
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/02—Topology update or discovery
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04B—TRANSMISSION
    • H04B7/00—Radio transmission systems, i.e. using radiation field
    • H04B7/14—Relay systems
    • H04B7/15—Active relay systems
    • H04B7/185—Space-based or airborne stations; Stations for satellite systems
    • H04B7/18578—Satellite systems for providing broadband data service to individual earth stations
    • H04B7/18584—Arrangements for data networking, i.e. for data packet routing, for congestion control
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L43/00—Arrangements for monitoring or testing data switching networks
    • H04L43/08—Monitoring or testing based on specific metrics, e.g. QoS, energy consumption or environmental parameters
    • H04L43/0805—Monitoring or testing based on specific metrics, e.g. QoS, energy consumption or environmental parameters by checking availability
    • H04L43/0811—Monitoring or testing based on specific metrics, e.g. QoS, energy consumption or environmental parameters by checking availability by checking connectivity
    • 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

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Computing Systems (AREA)
  • Physics & Mathematics (AREA)
  • Astronomy & Astrophysics (AREA)
  • Aviation & Aerospace Engineering (AREA)
  • General Physics & Mathematics (AREA)
  • Environmental & Geological Engineering (AREA)
  • Radio Relay Systems (AREA)

Abstract

The low-overhead OSPF protocol improvement method for the large-scale polar orbit constellation is based on the original mechanism of OSPF/OSPF+ protocol, and comprises the following steps of 1) dividing 'orbit areas', reducing the expenditure of route calculation resources, 2) presetting a link state database, reducing unnecessary message transmission, and 3) adding a new link 'test state', and ensuring the link connection reliability. And adding a new 'test state' on the basis of adding the 'leave state' into the original OSPF+ neighbor state machine. Whether a link is located in a "track area" or between "track areas", the link and its corresponding neighbors have four deterministic states, connect, leave, test, close. When the link is interrupted and recovered predictably, the link state update message is not announced any more, so that the speed of route re-convergence when the link is interrupted and recovered predictably is increased, and unnecessary occupation of inter-satellite link resources is reduced.

Description

Low-overhead OSPF protocol improvement method for large-scale polar orbit constellation
Technical Field
The invention belongs to the field of satellite communication, and particularly relates to a low-overhead OSPF protocol improvement method for a large-scale polar orbit constellation.
Background
The OSPF protocol is an intra-domain routing protocol based on a link state algorithm and developed by IETF organization, and has the characteristics of wide application range, no self-loop, quick response to link change, convenience for hierarchical network design and the like. In the low orbit satellite network, the links are interrupted or disabled due to the factors of link switching, faults, environmental interference and the like, and the topology is frequently changed, so that dynamic routing is necessary to cope with the network topology change. Because a significant portion of the network topology changes are predictable in the low orbit satellite network, the OSPF protocol is not effective in coping with predictable link on-off changes, and a certain decision time still needs to elapse before a link break can be determined and the route recalculated each time the link is periodically broken. Aiming at the problem, xu Mingwei et al (Xu Mingwei, xia Anqing, yang Yan, wang Yuliang, sang Meng. Day-to-earth integrated network intra-domain routing protocol OSPF+ [ J ]. The university of Qinghua university (natural science edition), 2017,57 (01): 12-17) propose an day-to-earth integrated intra-domain routing protocol OSPF+ based on the OSPF protocol, which skips the judging process of the establishment or failure of the neighbor relation of the original OSPF protocol when the predictable link is interrupted by introducing a link prediction mechanism, thereby realizing the rapid update of the routing table.
For small or medium-scale satellite communication systems, the ospf+ protocol enables rapid convergence when predictable topology changes occur. However, when ospf+ is used in a large-scale low-orbit satellite communication system, there are two disadvantages:
Firstly, in a large-scale low orbit satellite communication system, the OSPF+ protocol uses the original regional division mechanism of the OSPF protocol, so that the number of nodes in a single region cannot be effectively reduced, the routing recalculation cost is high, and the load of an on-board processor is increased. Specifically, the OSPF protocol requires that the non-backbone area must be directly connected to the backbone area during the area division process, the backbone area must be logically continuous, and in the case that the backbone area is logically discontinuous, a backbone area where virtual link connection is separated needs to be configured. In the process of regional division, satellites on the same orbit surface are preferably divided into the same region. In this case, if a virtual link is not used, it can be divided into at most three areas (a backbone area in the middle and non-backbone areas on both sides), whereas in the case of using a virtual link, it can be divided into a plurality of areas, however, one backbone area needs to be present every interval, and these backbone areas are logically continuous, eventually leading to an ineffective reduction in the size of the backbone areas. Such zoning is thus less effective in satellite networks.
Secondly, the redundant link state notification message occupies a large amount of on-board resources, and under the conditions of high inter-satellite link error rate and large transmission delay, the inter-satellite link bandwidth is extruded to cause resource waste, and the transmission of service data streams is affected. Specifically, each time a link is interrupted and restored predictably, a link state advertisement message (LINK STATE Update, LSU) is still required to be used for advertisement, wherein the link state advertisement message (LINK STATE ADVERTISEMENT, LSA) is included, and after each node receives LSUs from other nodes, the LSAs in the link state advertisement message are stored in a link state Database (LINK STATE Database, LSDB) of the node, and all LSAs in the link state advertisement message are flooded to all other ports. Because of more nodes in the network, when a large number of links are periodically changed, the generated LSU messages are huge in quantity, and a large amount of link bandwidth resources are consumed.
In a large-scale low-orbit satellite communication system, common constellation configurations include two kinds of oblique orbit constellations and polar orbit constellations. In the inclined orbit constellation, the satellite connection relation is stable, so that the update and recalculation of the inter-satellite routing information are less, and the defect of the OSPF+ protocol is not remarkably reflected. In polar orbit constellations, however, the typical scenario of link establishment is that each satellite establishes a link with two satellites adjacent to the same orbit while establishing a link with satellites of the same number as the adjacent orbit surfaces, a stable link cannot be established at a reverse slot (sea) because the satellite running directions are opposite, and the link is not established any more, and when the satellite runs to a higher latitude, the link establishment is not facilitated because the satellite relative movement speed between the adjacent orbits is faster, so that the on-off change of the link in the orbit occurs when the satellite enters and exits the polar region. In this case, if the number of satellites in the whole system is large, the on-off change of the link will continuously occur, and the two-point drawbacks of the ospf+ protocol will be significantly reflected, so an improved dynamic routing protocol is needed to adapt to the large-scale polar orbit low orbit satellite communication system.
Disclosure of Invention
The invention aims to provide a low-overhead OSPF (open shortest path first) improved protocol for a large-scale polar orbit constellation and an implementation method thereof, and aims to realize the effective operation of a dynamic routing protocol in a large-scale polar orbit low-orbit satellite communication system by using fewer satellite resources, and solve the defects of the operation of the existing dynamic routing protocols such as OSPF/OSPF+ and the like in the large-scale polar orbit satellite communication system, namely the problem of the waste of the calculation resources caused by the large calculation overhead (routing recalculation overhead) and the problem of the resource waste caused by the occupation of inter-satellite links by a large number of redundant messages.
The technical scheme of the invention is that the low-overhead OSPF protocol improvement method facing the large-scale polar orbit constellation is based on the original mechanism of OSPF/OSPF+ protocol, the invention provides the following improvement measures:
(1) And the track area is divided, so that the cost of the route calculation resource is reduced.
The original partitioning mechanism of the network is changed, the whole space network is divided into a plurality of track areas, each track area comprises a plurality of tracks, and a fixed IP network segment is endowed. For all links inside the "track area" a separate IP sub-network segment will be allocated under the "track area" network segment.
The routing information in the track area is calculated through the first type of LSA which is originally defined by the OSPF protocol and is generated by each node in the track area, namely Router-LSA, and the routing information outside the track area is calculated through the fifth type of LSA which is originally defined by the OSPF protocol and is generated by the boundary node of the track area, namely AS-External-LSA. Meanwhile, the boundary node of the 'track area' and the adjacent node of the other 'track area' send Hello messages to each other to detect whether the connecting link between the two nodes of the 'track area' is effective, and once any node finds that the connecting link is invalid, the LSU messages broadcast a fifth type LSA to inform the other nodes in the 'track area' respectively.
(2) And presetting a link state database, and reducing unnecessary message transmission.
The whole period of satellite ground-around operation in the system is divided into a plurality of time slots. In each time slot, if no unexpected fault occurs, the connection relationship between satellites in the whole system is kept stable. When the time slot is switched, the predictable on-off change of the link is needed to occur in the whole system, and meanwhile, the route is switched. For a specific polar orbit constellation scenario, the number of time slots and the switching interval need to be determined according to the topology and link planning of the polar orbit constellation that actually runs the protocol.
A link state database is preset for each "track area", respectively, which all nodes within the "track area" will hold. The first class LSA information and the fifth class LSA information of all nodes in the 'track area' in the whole running period are contained in a preset database, and the on-off information of all links in the first class LSA information and the fifth class LSA information are respectively attached to all links in the first class LSA information and the fifth class LSA information. When the time slot switching happens, if a certain node detects that the states of all the connected links after the time slot switching accord with preset information through the Hello message, the LSU message is not sent even if the on-off relation of the adjacent links is changed. That is, any predictable link interruption and recovery will not be notified by LSU messages, and each node can autonomously calculate the route after the slot switch. When a node detects that an unpredictable interruption occurs in a link connected with the node, the rest nodes in a track area where the node is positioned are notified through LSU messages, and if the link returns to normal after a period of time, the link is also notified through the LSU messages.
All nodes should also manage their own link state databases, respectively, when a slot switch occurs. The LSA associated with the unpredictable link outage will be easily distinguished from the pre-set LSA because it will not have time slot information as it is acquired via LSU messages. And checking whether a link disconnected in the next time slot exists in the LSA which is still inconsistent with the preset information, and labeling the LSA if the link disconnected in the next time slot exists, so that the LSA does not participate in the shortest path calculation of the next time slot. After management is completed, route recalculation is performed to adapt to the topology in the new time slot.
(3) And the link test state is newly added, so that the link connection reliability is ensured.
Due to the relatively harsh communication environment, the satellite nodes cannot accurately build links at preset time points. For this reason, a new "test state" is added based on the original OSPF+ neighbor state machine adding "away state". Whether a link is located in a "track area" or between "track areas", the link and its corresponding neighbors have four deterministic states, connect, leave, test, close. Each node is provided with a neighbor state machine for all neighboring nodes, and each neighboring node has a corresponding link. In operation, for each node, the states of all its links and neighbor nodes are transformed as follows:
before any node in the system starts to operate, all the links and neighbors connected with the node are respectively placed in a closed state, and when the node enters the first time slot, the node is selected to enter the connected state or the leaving state according to preset link on-off information.
If a link of a node is in a "connected state" and the next slot link is disconnected, the next slot link enters a "leaving state" directly after the slot switch, and the disconnected link will no longer participate in the route calculation.
If a certain link of a node is in "leaving state" and is converted to "connected state" in the next time slot prediction, a period of time T Test (e.g., 30 s) is advanced before the time slot switching occurs, so as to start to attempt to connect to the link, and a Hello packet is continuously sent to a neighbor of the opposite end of the link at a certain time interval T Hello (e.g., 3 s), at which time the link enters "test state". The advanced connection time T Test should ensure that the link can complete connection within the time without accidents, and at the same time, the corresponding latitude at the time point of completing connection should be designed reasonably, so as to ensure that the moment of starting connection has the link connection condition. The selection of the T Hello should ensure that a certain number of Hello packets can be sent within the time of the T Test, so that misjudgment caused by accidental packet loss is prevented, the T Hello and the T Test can be determined according to the actual satellite packet loss probability test result, and the number of sent packets can ensure certain judgment accuracy. If the link between the node and the neighbor node is successfully connected in the test state, no LSU message is sent, and the rest nodes in the track area where the node is located directly complete calculation according to LSAs in a preset database. If the connection cannot be completed within the time T Test, notifying the rest nodes in the track area where the node is located through LSU messages, and calculating the rest nodes according to LSAs contained in the received LSU messages, meanwhile, the neighbor state machine stays in the test state to continuously detect whether the link is connected or not, and once the connection with the neighbor node at the opposite end of the link is completed, notifying the rest nodes that the link has been restored to normal again through the LSU messages. If the link is not connected in the entire time slot, then when the next time slot switch occurs, the link is considered to have failed temporarily, and the neighbor state machine transitions to the "off state" to wait for the link to repair.
For a total number of satellites N, the number of orbits P, and the phase factor F (i.e., the phase difference between adjacent orbits and numbered satellites isF is more than or equal to 0 and less than or equal to P-1, and F is an integer), wherein the typical condition of establishing inter-satellite links is that each satellite establishes links with two satellites adjacent to the same orbit, simultaneously establishes links with satellites with the same number as the adjacent orbit surface, and does not establish links at reverse seams, and when the satellites run above a certain latitude, the inter-orbit links are disconnected. If the link establishment of a polar-track constellation meets the above-described typical situation, the operation of the OSPF protocol can be configured in the following five steps. If the satellite has deviation from the ideal constellation position, but the satellite does not influence the communication between the satellite and other satellites or ground nodes at all times, the position of the satellite in the actual constellation can be mapped to the ideal position, and then the improved OSPF protocol is deployed according to the following steps.
For convenience of explanation, it is assumed that satellites in the system are represented by S (i, j) (i is greater than or equal to 0 and less than or equal to P-1, j is greater than or equal to 0 and less than or equal to N-1), where i represents an orbit number, j represents a satellite number in the orbit, a latitude where a satellite link is broken is denoted as lat M, and the number of satellites in a single orbit is denoted as N, where np=n.
Step 1, determining the number m of time slots.
The period of satellite operation within the overall system is divided into a number of time slots. In each time slot, if no unexpected fault occurs, the connection relationship between satellites in the whole system is kept stable. When the time slot is switched, the predictable on-off change of the link is needed to occur in the whole system, and meanwhile, the route is switched. Thus, the total number of times of route switching occurs in a polar orbit satellite communication constellation around the earth operation period is the time slot number m.
In order to conveniently obtain the value of m, considering that the topology of the polar orbit constellation has repeatability, the minimum orbit number k for enabling the topology to be repeated needs to be determined first. The meaning of k is that let i=0, and the connection relationship between the ith orbit and the (i+1) th orbit is observed, i increases from 0 to P-2 in order. After passing through k orbits, the connection relationship between satellites at the same latitude may be completely repeated, that is, the connection between the k orbits and the satellites at the k+1 orbits is completely the same as the connection relationship between satellites at the corresponding latitudes at the 0 th and 1 st orbits at any time. The value of k is calculated by equation (1):
The number of slots is thereafter calculated as follows:
(1) If kn is even, when M=kn when integer, otherwise m=2kn;
(2) If kn is odd, when When being an integer, m=2kn, otherwise m=4kn.
And 2, determining the on-off state of all links in each time slot.
(1) Assuming that the satellite S (0, 0) is located at the north latitude lat M, the latitudes at which the satellites at both ends of all inter-orbit links are located at this time are calculated as initial latitude values, and the current slot value is recorded as 0. And determining that the satellite belongs to a connection or disconnection state according to the latitude values of the satellites at the two ends of each link.
(2) The track is assumed to be running in the direction that S (0, 0) is moving from north to south at time slot 0. Finding out the link closest to the switching in the current time slot (when a plurality of links exist, the links are selected at will), calculating the latitude lat add which is needed to be rotated when the distance from the link is switched, adding 1 to the time slot value, calculating the latitude values of the two ends of the link after all satellites rotate the latitude lat add according to the running direction, and judging that the link belongs to the connection or disconnection state.
(3) And (2) repeating the step until the satellite S (0, 0) completes one circle around the ground, wherein the time slot value is increased to m-1, and the on-off state of all links in each time slot is calculated. At the same time, since the latitude lat add rotated by each handoff is calculated and the angular velocity of the satellite operation is known, the handoff time interval is also determined.
And 3, dividing the track area.
The number of tracks per "track area" is determined and the "track area" division is performed. If the routing computation is desired to be shortest, the "track area" may be partitioned as follows:
let x tracks in each track area, x is a positive integer and x is equal to or greater than 2 (routing islands are easy to occur when x is taken to be 1, and thus not considered.) The number of nodes within each "track area" may be denoted nx.
If there are y Router-LSAs in the database, in the case of calculating the shortest path by using the priority queue, the route calculation time can be expressed as:
t 1(y)＝aylog2 y+by+c (where a, b, c are fixed parameters) (2)
If there are y AS-External-LSAs in the database, the route calculation time can be expressed AS:
t 2 (y) =dy+e (where d, e are fixed parameters) (3)
The parameters a, b, c, d, e can be determined by testing the routing calculation module of the protocol, respectively changing the number of Router-LSA and AS-External-LSA, measuring the routing calculation time, performing multiple sets of measurement, and determining a, b, c, d, e value by adopting a statistical regression mode.
The calculated total time T (x) can be expressed as:
Derived from
Thus T' (x) monotonically increases, which can be divided into the following cases:
(1) When T '(2) is less than or equal to 0, x 0 epsilon [2, ++ infinity exists, so that T' (x 0) =0, the route calculation time reaches the minimum value, and x 0 can be solved numerically by means of a computer. Generally, x 0 is not an integer, x 1 is taken to be the largest integer no greater than x 0, and x 2 is taken to be the smallest integer no less than x 0. If T (x 1)≤T(x2), then x 1 is the optimal value, otherwise x 2 is the optimal value.
(2) When T '(2) is >0, x 0 epsilon 2 is absent, + -infinity), such that T' (x 0) =0, thus making the number of tracks with the shortest route calculation time 2.
After the number x Best of tracks in a single "track area" which minimizes the route calculation time is obtained, the "track area" can be divided, and only the x Best tracks are divided into one "track area" in sequence from the track No. 0. When (when)If the remainder is not an integer, the last track is merged into the last track area if the remainder is 1, and if the remainder is more than or equal to 2, the track which is not allocated at the end is divided into one track area independently.
And 4, carrying out IP address allocation and writing out a preset link state database.
After the "track area" division is completed, a separate network segment is assigned to each "track area", the subnet mask length of the network segment is ensured, each link in the network segment can be allocated to a subnet segment under the "track area", and the subnet mask length of the link subnet segment is at most 30. Meanwhile, the link between two "track areas" is also assigned an independent IP network segment.
And for each track area, directly writing out a link state database according to the network segment allocation and the link on-off calculation. During operation, all nodes within each "track area" will be loaded with the same pre-set link state database.
And 5, loading a preset link state database, and operating the protocol after aligning the time slots.
When the protocol is run on the satellite, the link state database of the "track area" to which it belongs is first loaded. When satellite S (0, 0) runs from north to south to north latitude lat M, the slot is set to 0 and the modified OSPF protocol begins to run. Alternatively, when the satellite position in the system matches the position at the beginning of a certain time slot, all satellites in the system are synchronized to the time slot and then start to operate.
Under the condition that the satellite does not increase or decrease in the system and the link does not permanently fail, the preset database is kept unchanged all the time; under the condition that satellites are increased or reduced or a link is permanently invalid, an original link state message synchronization mechanism of OSPF can be used first, rerouting can be rapidly completed through sending LSU messages, and then, the number of time slots and on-off information are needed to be recalculated for the changed topology and the related 'orbit zone', the link state database is rewritten, and the preset link state databases of all satellites in the 'orbit zone' are updated.
The invention removes the limit of the original OSPF/OSPF+ protocol partitioning mechanism in the large-scale polar orbit satellite communication system by a new partitioning mechanism, thereby greatly reducing the route recalculation expenditure, and removes the transmission of unnecessary link state messages by the presetting and management of the link state database, thereby leading the inter-satellite link resources to be more used for the transmission of data messages. The invention only relates to the forwarding of inter-satellite routing, and is not limited in detail for inter-satellite access.
Compared with the OSPF and the OSPF+ protocols, the method and the device have the advantages that calculation and message expenses generated by the operation of the OSPF/OSPF+ dynamic routing protocol in a large-scale polar orbit communication system can be effectively reduced, and the effective operation of the dynamic routing protocol can be realized by using less on-board calculation resources under the condition that the performance of an on-board processor is limited. On one hand, the invention overcomes the possible limit factor of the prior OSPF/OSPF+ region dividing mechanism applied to the large polar orbit constellation by dividing the orbit region, and the prior OSPF/OSPF+ region dividing mechanism is applied to the large polar orbit constellation, and the constraint condition that the backbone region is logically continuous and the non-backbone region is directly connected with the backbone region causes the region scale to be unable to be effectively reduced. On the other hand, any predictable link interruption and recovery will not be announced by LSU message, thus greatly reducing unnecessary message expenditure, accelerating the speed of route reconvergence when the predictable link interruption and recovery occur, and reducing unnecessary inter-satellite link resource occupation.
Drawings
FIG. 1 is a flow chart of an overall implementation.
Fig. 2 is a polar orbit constellation link establishment diagram.
Fig. 3 is a schematic diagram of a "track area" division.
Fig. 4 is a schematic diagram of satellite link state transition.
Fig. 5 is a diagram of a neighbor state machine.
Fig. 6 is a schematic diagram of an interface state machine.
Fig. 7 (a), fig. 7 (b), and fig. 7 (c) are schematic diagrams of "routing islands", respectively showing the occurrence of routing islands when one, two, and three links are included in the "track area".
Fig. 8 is a schematic diagram of IP address assignment.
Fig. 9 (a) and 9 (b) are schematic diagrams of Router-LSA and AS-External-LSA preset information, respectively.
Detailed Description
In order to better understand the technical content of the present invention, a specific embodiment is specifically illustrated and described below with reference to the accompanying drawings, and the overall implementation flow is shown in fig. 1. According to the exemplary scenario of polar-orbit constellation inter-satellite links described in the background, fig. 2 is a schematic diagram of a simple polar-orbit constellation link setup, which may be abstracted into a grid-like topology.
The invention removes the limit of the original OSPF/OSPF+ protocol partitioning mechanism in the large-scale polar orbit satellite communication system by a new partitioning mechanism, thereby greatly reducing the route recalculation expenditure, and removes the transmission of unnecessary link state messages by the presetting and management of the link state database, thereby leading the inter-satellite link resources to be more used for the transmission of data messages. Based on the original mechanism of the OSPF/OSPF+ protocol, the invention provides the following improvement measures:
(1) And the track area is divided, so that the cost of the route calculation resource is reduced.
The original partitioning mechanism of the network is changed, the whole space network is divided into a plurality of track areas, each track area comprises a plurality of tracks, and a fixed IP network segment is endowed. For all links inside the "track area" a separate IP sub-network segment will be allocated under the "track area" network segment, as shown in fig. 3.
The routing information in the track area is calculated through the first type of LSA which is originally defined by the OSPF protocol and is generated by each node in the track area, namely Router-LSA, and the routing information outside the track area is calculated through the fifth type of LSA which is originally defined by the OSPF protocol and is generated by the boundary node of the track area, namely AS-External-LSA. Meanwhile, the boundary node of the 'track area' and the adjacent node of the other 'track area' send Hello messages to each other to detect whether the connecting link between the two nodes of the 'track area' is effective, and once any node finds that the connecting link is invalid, the LSU messages broadcast a fifth type LSA to inform the other nodes in the 'track area' respectively.
(2) And presetting a link state database, and reducing unnecessary message transmission.
The whole period of satellite ground-around operation in the system is divided into a plurality of time slots. In each time slot, if no unexpected fault occurs, the connection relationship between satellites in the whole system is kept stable. When the time slot is switched, the predictable on-off change of the link is needed to occur in the whole system, and meanwhile, the route is switched. For a specific polar orbit constellation scenario, the number of time slots and the switching interval need to be determined according to the topology and link planning of the polar orbit constellation that actually runs the protocol.
A link state database is preset for each "track area", respectively, which all nodes within the "track area" will hold. The first class LSA information and the fifth class LSA information of all nodes in the 'track area' in the whole running period are contained in a preset database, and the on-off information of all links in the first class LSA information and the fifth class LSA information are respectively attached to all links in the first class LSA information and the fifth class LSA information. When the time slot switching happens, if a certain node detects that the states of all the connected links after the time slot switching accord with preset information through the Hello message, the LSU message is not sent even if the on-off relation of the adjacent links is changed. That is, any predictable link interruption and recovery will not be notified by LSU messages, and each node can autonomously calculate the route after the slot switch. When a node detects that an unpredictable interruption occurs in a link connected with the node, the rest nodes in a track area where the node is positioned are notified through LSU messages, and if the link returns to normal after a period of time, the link is also notified through the LSU messages.
All nodes should also manage their own link state databases, respectively, when a slot switch occurs. The LSA associated with the unpredictable link outage will be easily distinguished from the pre-set LSA because it will not have time slot information as it is acquired via LSU messages. And checking whether a link disconnected in the next time slot exists in the LSA which is still inconsistent with the preset information, and labeling the LSA if the link disconnected in the next time slot exists, so that the LSA does not participate in the shortest path calculation of the next time slot. After management is completed, route recalculation is performed to adapt to the topology in the new time slot.
(3) And the link test state is newly added, so that the link connection reliability is ensured.
Due to the relatively harsh communication environment, the satellite nodes cannot accurately build links at preset time points. For this reason, a new "test state" is added based on the original OSPF+ neighbor state machine adding "away state". Whether a link is located in a "track area" or between "track areas", the link and its corresponding neighbors have four deterministic states, connect, leave, test, close. Each node is provided with a neighbor state machine for all neighboring nodes, and each neighboring node has a corresponding link. In operation, for each node, the states of all its links and neighbor nodes are transformed as follows:
before any node in the system starts to operate, all the links and neighbors connected with the node are respectively placed in a closed state, and when the node enters the first time slot, the node is selected to enter the connected state or the leaving state according to preset link on-off information.
If a link of a node is in a "connected state" and the next slot link is disconnected, the next slot link enters a "leaving state" directly after the slot switch, and the disconnected link will no longer participate in the route calculation.
If a certain link of a node is in "leaving state" and is converted to "connected state" in the next time slot prediction, a period of time T Test (e.g., 30 s) is advanced before the time slot switching occurs, so as to start to attempt to connect to the link, and a Hello packet is continuously sent to a neighbor of the opposite end of the link at a certain time interval T Hello (e.g., 3 s), at which time the link enters "test state". The advanced connection time T Test should ensure that the link can complete connection within the time without accidents, and at the same time, the corresponding latitude at the time point of completing connection should be designed reasonably, so as to ensure that the moment of starting connection has the link connection condition. The selection of the T Hello should ensure that a certain number of Hello packets can be sent within the time of the T Test, so that misjudgment caused by accidental packet loss is prevented, the T Hello and the T Test can be determined according to the actual satellite packet loss probability test result, and the number of sent packets can ensure certain judgment accuracy. If the link between the node and the neighbor node is successfully connected in the test state, no LSU message is sent, and the rest nodes in the track area where the node is located directly complete calculation according to LSAs in a preset database. If the connection cannot be completed within the time T Test, notifying the rest nodes in the track area where the node is located through LSU messages, and calculating the rest nodes according to LSAs contained in the received LSU messages, meanwhile, the neighbor state machine stays in the test state to continuously detect whether the link is connected or not, and once the connection with the neighbor node at the opposite end of the link is completed, notifying the rest nodes that the link has been restored to normal again through the LSU messages. If the link is not connected in the entire time slot, then when the next time slot switch occurs, the link is considered to have failed temporarily, and the neighbor state machine transitions to the "off state" to wait for the link to repair.
As shown in fig. 4, a schematic diagram of a link state transition of a satellite is shown in the case that no abnormal failure occurs in the link. The Neighbor State Machine (NSM) and the Interface State Machine (ISM) of the OSPF protocol are correspondingly improved, and schematic diagrams of the Neighbor State Machine (NSM) and the Interface State Machine (ISM) are respectively shown in fig. 5 and 6, the Down state is the closed state, and the Full state and the P2P state correspond to neighbor connection states in the track area. The meaning of the new state is that NSM_leaving (in-track neighbor Leaving), NSM_testing (in-track neighbor connection test), NSM_IOA_leaving (in-track neighbor connection), NSM_IOA_leaving (in-track neighbor Leaving), NSM_IOA_testing (in-track neighbor test), ISM_leaving (in-track link Leaving), ISM_testing (in-track link connection test), ISM_IOA (in-track link connection), ISM_IOA_leaving (in-track link Leaving) and ISM_IOA_testing (in-track link connection test) are respectively included in the neighbor state machine.
For a total number of satellites N, the number of orbits P, and the phase factor F (i.e., the phase difference between adjacent orbits and numbered satellites isF is more than or equal to 0 and less than or equal to P-1, and F is an integer), wherein the typical condition of establishing inter-satellite links is that each satellite establishes links with two satellites adjacent to the same orbit, simultaneously establishes links with satellites with the same number as the adjacent orbit surface, and does not establish links at reverse seams, and when the satellites run above a certain latitude, the inter-orbit links are disconnected. If the link establishment of a polar-track constellation meets the above-described typical situation, the operation of the OSPF protocol can be configured in the following five steps. If the satellite has deviation from the ideal constellation position, but the satellite does not influence the communication between the satellite and other satellites or ground nodes at all times, the position of the satellite in the actual constellation can be mapped to the ideal position, and then the improved OSPF protocol is deployed according to the following steps.
For convenience of explanation, it is assumed that satellites in the system are represented by S (i, j) (i is greater than or equal to 0 and less than or equal to P-1, j is greater than or equal to 0 and less than or equal to N-1), where i represents an orbit number, j represents a satellite number in the orbit, a latitude where a satellite link is broken is denoted as lat M, and the number of satellites in a single orbit is denoted as N, where np=n.
Step 1, determining the number m of time slots.
The period of satellite operation within the overall system is divided into a number of time slots. In each time slot, if no unexpected fault occurs, the connection relationship between satellites in the whole system is kept stable. When the time slot is switched, the predictable on-off change of the link is needed to occur in the whole system, and meanwhile, the route is switched. Thus, the total number of times of route switching occurs in a polar orbit satellite communication constellation around the earth operation period is the time slot number m.
In order to conveniently obtain the value of m, considering that the topology of the polar orbit constellation has repeatability, the minimum orbit number k for enabling the topology to be repeated needs to be determined first. The meaning of k is that let i=0, and the connection relationship between the ith orbit and the (i+1) th orbit is observed, i increases from 0 to P-2 in order. After passing through k orbits, the connection relationship between satellites at the same latitude may be completely repeated, that is, the connection between the k orbits and the satellites at the k+1 orbits is completely the same as the connection relationship between satellites at the corresponding latitudes at the 0 th and 1 st orbits at any time. The value of k is calculated by equation (1):
The number of slots is thereafter calculated as follows:
(1) If kn is even, when M=kn when integer, otherwise m=2kn;
(2) If kn is odd, when When being an integer, m=2kn, otherwise m=4kn.
And 2, determining the on-off state of all links in each time slot.
(1) Assuming that the satellite S (0, 0) is located at the north latitude lat M, the latitudes at which the satellites at both ends of all inter-orbit links are located at this time are calculated as initial latitude values, and the current slot value is recorded as 0. And determining that the satellite belongs to a connection or disconnection state according to the latitude values of the satellites at the two ends of each link.
(2) The track is assumed to be running in the direction that S (0, 0) is moving from north to south at time slot 0. Finding out the link closest to the switching in the current time slot (when a plurality of links exist, the links are selected at will), calculating the latitude lat add which is needed to be rotated when the distance from the link is switched, adding 1 to the time slot value, calculating the latitude values of the two ends of the link after all satellites rotate the latitude lat add according to the running direction, and judging that the link belongs to the connection or disconnection state.
(3) And (2) repeating the step until the satellite S (0, 0) completes one circle around the ground, wherein the time slot value is increased to m-1, and the on-off state of all links in each time slot is calculated. At the same time, since the latitude lat add rotated by each handoff is calculated and the angular velocity of the satellite operation is known, the handoff time interval is also determined.
And 3, dividing the track area.
The number of tracks per "track area" is determined and the "track area" division is performed.
Firstly, describing the case of "routing island", fig. 7 (a), fig. 7 (b), and fig. 7 (c) show that when the "track area" includes one, two, and three links, the routing island occurs, and the gray and black nodes cannot perform normal routing. Therefore, when the number of tracks in the track area is larger, more link interruption occurs to generate a routing island, and the situation that only one track is contained in the track area easily occurs.
If the routing computation is desired to be shortest, the "track area" may be partitioned as follows:
let x tracks in each track area, x is a positive integer and x is equal to or greater than 2 (routing islands are easy to occur when x is taken to be 1, and thus not considered.) The number of nodes within each "track area" may be denoted nx.
If there are y Router-LSAs in the database, in the case of calculating the shortest path by using the priority queue, the route calculation time can be expressed as:
t 1(y)＝aylog2 y+by+c (where a, b, c are fixed parameters) (2)
If there are y AS-External-LSAs in the database, the route calculation time can be expressed AS:
t 2 (y) =dy+e (where d, e are fixed parameters) (3)
The parameters a, b, c, d, e can be determined by testing the routing calculation module of the protocol, respectively changing the number of Router-LSA and AS-External-LSA, measuring the routing calculation time, performing multiple sets of measurement, and determining a, b, c, d, e value by adopting a statistical regression mode.
The calculated total time T (x) can be expressed as:
Derived from
Thus T' (x) monotonically increases, which can be divided into the following cases:
(1) When T '(2) is less than or equal to 0, x 0 epsilon [2, ++ infinity exists, so that T' (x 0) =0, the route calculation time reaches the minimum value, and x 0 can be solved numerically by means of a computer. Generally, x 0 is not an integer, x 1 is taken to be the largest integer no greater than x 0, and x 2 is taken to be the smallest integer no less than x 0. If T (x 1)≤T(x2), then x 1 is the optimal value, otherwise x 2 is the optimal value.
(2) When T '(2) is >0, x 0 epsilon 2 is absent, + -infinity), such that T' (x 0) =0, thus making the number of tracks with the shortest route calculation time 2.
After the number x Best of tracks in a single "track area" which minimizes the route calculation time is obtained, the "track area" can be divided, and only the x Best tracks are divided into one "track area" in sequence from the track No. 0. When (when)If the remainder is not an integer, the last track is merged into the last track area if the remainder is 1, and if the remainder is more than or equal to 2, the track which is not allocated at the end is divided into one track area independently.
And 4, carrying out IP address allocation and writing out a preset link state database.
After the "track area" division is completed, a separate network segment is assigned to each "track area", the subnet mask length of the network segment is ensured, each link in the network segment can be allocated to a subnet segment under the "track area", and the subnet mask length of the link subnet segment is at most 30. Meanwhile, the link between two "track areas" is also assigned an independent IP network segment.
In fig. 3, a simple example has been given for network segment allocation. The constellation is divided into n "track areas", denoted OA i (0≤i≤n-1), which is assigned a segment 10.i.0.0/16, under which all links should be arbitrarily assigned a sub-segment. The links where OA i connects with OA i+1 are assigned segments 10.128+i.0.0/16. For example, in FIG. 8, links < S (0, 0), S (0, 1) >, and S (1, 0), S (2, 0) >, are both located inside OA i, with sub-segments 10.0.0.8/30, 10.0.0/4/30 allocated to each of the two links at 10.0.0/16, and links < S (2, 0), S (3, 0) >, S (2, 1), S (3, 1) >, are all located between OA 0 and OA 1, and thus sub-segments 10.128.0.0/30 and 10.128.0.4/30 are allocated at 10.128.0.0/16.
And for each track area, directly writing out a link state database according to the network segment allocation and the link on-off calculation. During operation, all nodes within each "track area" will be loaded with the same pre-set link state database. The specific writing method comprises the following steps:
(1) Each node needs to generate a Router-LSA that will contain IP address information for all links within the "track area" to which the node is connected. For a node inside a "track area" it should contain IP address information of 4 links to which it is connected, and for a node outside a "track area" it should contain IP address information of 3 nodes inside the "track area" to which it is connected. Meanwhile, since the 'track area' division is already adopted, the original area division mode of the OSPF is not necessary to be used, and therefore all the 'track area' internal network segments are declared to be positioned in the backbone area.
(2) For each "track area" border node, one AS-External-LSA should be generated for each of the segments of the remaining "track area" to which it leads. Specifically, the border node located on the left side of the "track area" needs to generate one AS-External-LSA for each of all the segments of the "track area" on the left side thereof, and the border node located on the right side of the "track area" needs to generate one AS-External-LSA for each of all the segments of the "track area" on the right side thereof.
(3) For all Router-LSA and AS-External-LSA, the additional time slot information is needed, the number of time slots is calculated according to the step 2, and the on-off information is calculated according to the step 3.
AS shown in fig. 9 (a) and 9 (b), which are examples of Router-LSA and AS-External preset information, respectively, in the slot information matrix, "0" indicates that the link is available in the slot and "1" indicates that it is not available. As shown in fig. 9 (a), the Router-LSA contains 4 links, and note that in the Router-LSA, for each inter-satellite link configured as a point-to-point link type, two pieces of link information will be contained, one of which is of a point-to-point type (P2P) and the other of which is of a tip type (stub). Each border node needs to generate an AS-External-LSA for each External network segment declared by the border node, and the AS-External-LSA advertised by the same router only needs to share a link-on-off matrix, which only includes one link, i.e., a link where the border node of the "track area" is connected to another "track area", AS shown in (b) of fig. 9.
And 5, loading a preset link state database, and operating the protocol after aligning the time slots.
When the protocol is run on the satellite, the link state database of the "track area" to which it belongs is first loaded. When satellite S (0, 0) runs from north to south to north latitude lat M, the slot is set to 0 and the modified OSPF protocol begins to run. Alternatively, when the satellite position in the system matches the position at the beginning of a certain time slot, all satellites in the system are synchronized to the time slot and then start to operate.
Under the condition that the satellite does not increase or decrease in the system and the link does not permanently fail, the preset database is kept unchanged all the time; under the condition that satellites are increased or reduced or a link is permanently invalid, an original link state message synchronization mechanism of OSPF can be used first, rerouting can be rapidly completed through sending LSU messages, and then, the number of time slots and on-off information are needed to be recalculated for the changed topology and the related 'orbit zone', the link state database is rewritten, and the preset link state databases of all satellites in the 'orbit zone' are updated.
The invention provides an OSPF protocol improvement method for a large-scale polar orbit constellation, which is described in detail above and aims to reduce the running overhead of an OSPF/OSPF+ protocol in the large-scale polar orbit constellation, and the performance improvement is mainly characterized in that firstly, the invention overcomes the limiting factors possibly occurring when the original OSPF/OSPF+ region division mechanism is applied to the large-scale polar orbit constellation through the division of a 'orbit region', and the calculation overhead can be less increased under the condition that the number of the constellation orbits is greatly increased, so that the overall performance of the system is ensured. Secondly, when the link is interrupted and restored predictably, the LSU message is not announced, so that unnecessary message expenditure is greatly reduced, and the route re-convergence speed is increased when the link interruption and restoration predictably occur. Through the improvement of the performance of the two points, the calculation and message overhead generated by the operation of the OSPF/OSPF+ dynamic routing protocol in a large polar orbit constellation can be effectively reduced, and the effective operation of the dynamic routing protocol is still realized under the conditions of limited performance of an on-board processor and limited link bandwidth resources.
The above examples are provided only to assist in understanding the core idea of the invention, and it is within the scope of the appended claims that the specific embodiments may be changed according to the idea of the invention when the invention is applied in actual constellations.

Claims (4)

1.一种面向大规模极地轨道星座的低开销OSPF协议改进方法，其特征在于，在OSPF/OSPF+协议原有机制的基础之上，改进步骤如下：1. A low-overhead OSPF protocol improvement method for large-scale polar orbit constellations, characterized by the following improvement steps based on the original mechanism of the OSPF/OSPF+ protocol: (1)进行“轨道区”划分，降低路由计算资源开销；(1) Divide the “track area” to reduce the routing computing resource overhead; 改变网络原有的分区机制，将整个空间网络划分为多个“轨道区”，每个“轨道区”包含若干条轨道，并赋予固定的IP网段；对于“轨道区”内部的所有链路，都将在该“轨道区”网段之下，被分配一个独立的IP子网段；Changing the original network partitioning mechanism, the entire spatial network is divided into multiple "track zones". Each "track zone" contains several tracks and is assigned a fixed IP network segment. For all links within the "track zone", an independent IP subnet segment will be assigned under the "track zone" network segment. “轨道区”内部的路由信息通过内部每个节点产生的OSPF协议原有定义的第一类LSA即Router-LSA进行计算，“轨道区”外部的路由信息通过“轨道区”边界节点产生的OSPF协议原有定义的第五类LSA即AS-External-LSA进行计算；同时，“轨道区”边界节点与另一“轨道区”相邻节点，都将互相发送Hello报文探测这两个节点之间的“轨道区”间连接链路是否有效，一旦任一节点发现该连接链路失效，即通过LSU报文广播第五类LSA通知其各自“轨道区”内部其余节点；Routing information within a track area is calculated using the first type of LSA (Router-LSA) defined by the OSPF protocol, generated by each node within the area. Routing information outside the track area is calculated using the fifth type of LSA (AS-External-LSA) defined by the OSPF protocol, generated by the edge nodes of the track area. At the same time, the edge nodes of the track area and the adjacent nodes of another track area will send Hello messages to each other to detect whether the link between the two nodes is valid. Once any node finds that the link is invalid, it will broadcast the fifth type of LSA via LSU message to notify the other nodes within its respective track area. (2)预置链路状态数据库，减少不必要报文发送；(2) Pre-set link state database to reduce unnecessary message sending; 将系统内卫星绕地运行的整个周期划分为若干时隙；每个时隙中，如果没有发生意外故障，整个系统内卫星间的连接关系保持稳定；而在时隙发生切换时，整个系统内必有链路发生可预测通断变化，同时进行路由切换；针对具体的极地轨道星座场景，时隙的数量以及切换间隔需要根据实际运行该协议的极地轨道星座的拓扑和链路规划进行确定；The entire orbital cycle of satellites in the system is divided into several time slots. During each time slot, unless an unexpected failure occurs, the connection between satellites in the entire system remains stable. However, when a time slot switches, links in the entire system must undergo predictable connectivity changes, and routing switches are performed simultaneously. For specific polar orbit constellation scenarios, the number of time slots and switching intervals need to be determined based on the topology and link planning of the polar orbit constellation in which the protocol is actually running. 针对每个“轨道区”，都分别预置一个链路状态数据库，该“轨道区”内的所有节点都将持有该数据库；预置数据库中，包含在整个运行周期内的该“轨道区”内所有节点的第一类和第五类LSA信息，并对于其中的所有链路，分别附带其在所有时隙内的通断信息；时隙切换发生时，如果某个节点通过Hello报文探测到其所有相连链路在时隙切换后的状态符合预置信息，那么即使其相邻链路的通断关系发生改变，也不会发送LSU报文；即任何可预测的链路中断与恢复，都将不再通过LSU报文进行通知，每个节点都能够自主计算时隙切换后的路由；而当某节点探测到其所连接的链路发生不可预测中断时，将通过LSU报文通知其所在的“轨道区”内部其余节点，若该链路在一段时间后恢复正常，将同样通过LSU报文进行通知；A link state database is pre-set for each "track area" and all nodes in the "track area" will hold this database. The pre-set database contains the first and fifth type LSA information of all nodes in the "track area" during the entire operation cycle, and for all links in it, the on-off information of each link in all time slots is attached. When a time slot switch occurs, if a node detects through a Hello message that the status of all its connected links after the time slot switch is consistent with the pre-set information, then even if the on-off relationship of its adjacent links changes, it will not send an LSU message. In other words, any predictable link interruption and recovery will no longer be notified through LSU messages, and each node can independently calculate the route after the time slot switch. When a node detects an unpredictable interruption of the link it is connected to, it will notify the other nodes in the "track area" in its location through an LSU message. If the link recovers after a period of time, it will also notify the other nodes through an LSU message. 在时隙切换发生时，所有节点还应当分别对于自己的链路状态数据库进行管理；不可预测链路中断相关的LSA由于通过LSU报文进行获取，将不带有时隙信息，因而容易与预置的LSA进行区分；对于已经恢复为与预置信息一致的LSA，恢复为原有预置的带有时隙信息的LSA；对于仍然与预置信息不一致的LSA，检查其中是否有在下一时隙发生断开的链路，如果有则对其打上标签，使其不参与下一时隙的最短路径计算；完成管理后，进行路由重新计算，以适应新时隙内的拓扑；When a time slot switch occurs, all nodes should also manage their own link state databases. LSAs related to unpredictable link interruptions are obtained through LSU messages and do not carry time slot information, making them easy to distinguish from pre-set LSAs. For LSAs that have been restored to be consistent with the pre-set information, the original pre-set LSAs with time slot information are restored. For LSAs that are still inconsistent with the pre-set information, check whether there are links that will be disconnected in the next time slot. If so, label them so that they do not participate in the shortest path calculation in the next time slot. After the management is completed, the route is recalculated to adapt to the topology in the new time slot. (3)新增链路“测试状态”，保证链路连接可靠性；(3) Added link "test status" to ensure link connection reliability; 在原有OSPF+邻居状态机加入“离开状态”的基础之上，加入一种新的“测试状态”；无论某条链路位于“轨道区”内或“轨道区”之间，该链路以及该链路对应的邻居都具有四种确定性状态：连接、离开、测试、关闭；每个节点，针对其相邻的所有邻居节点，都将独立设置一个邻居状态机，且每个邻居节点都有一条对应的链路；在运行过程中，对于每个节点而言，其所有链路与邻居节点的状态，按照如下描述进行转换：In addition to the "Leaving State" added to the existing OSPF+ neighbor state machine, a new "Testing State" has been added. Regardless of whether a link is within or between "track zones," the link and its corresponding neighbor have four deterministic states: Connected, Leaving, Testing, and Down. Each node has a separate neighbor state machine for all of its neighboring nodes, and each neighbor node has a corresponding link. During operation, for each node, the states of all its links and neighbor nodes transition as described below: 对于系统内任意一个节点而言，开始运行前，分别将其所有相连的链路及邻居置于“关闭状态”，在进入第一个时隙时，根据预置的链路通断信息，选择进入“连接状态”或“离开状态”；Before any node in the system starts running, it puts all its connected links and neighbors into the "Closed State". When entering the first time slot, it chooses to enter the "Connected State" or "Leaving State" according to the preset link connection and disconnection information. 如果一个节点的某条链路处于“连接状态”，且下一时隙链路断开，则时隙切换后直接进入“离开状态”，该断开的链路将不再参与路由计算；If a link of a node is in the "connected state" and the link is disconnected in the next time slot, it will directly enter the "left state" after the time slot switch, and the disconnected link will no longer participate in the routing calculation; 如果一个节点的某条链路处于“离开状态”，且在下一时隙预测转换为“连接状态”，则将在时隙切换发生时刻之前，提前一段时间TTest即开始尝试连接链路，TTest的选取应当保证其大于链路连接的最小时间，并向该链路对端的邻居以一定时间间隔THello持续发送Hello包，此时该链路进入“测试状态”；该提前一段时间TTest应当保证链路在不发生意外的情况下，能够在该时间内完成连接，同时也应当合理设计完成连接的时间点处对应的纬度，保证开始连接的时刻具备链路连接条件；THello的选取应当保证在TTest时间内能够发送一定数量的Hello包，防止由于意外丢包造成误判，THello和TTest根据实际星上丢包概率测试结果进行确定，发包数量能够保证一定的判断准确性即可；如果在“测试状态”内，此节点与邻居节点之间的链路成功完成连接，则不发送LSU报文，该节点所在的“轨道区”内部其余节点将直接按照预置的数据库中的LSA完成计算；如果TTest时间内无法完成连接，将通过LSU报文通知该节点所在“轨道区”内部的其余节点，其余节点将根据收到的LSU报文中包含的LSA进行计算；同时，邻居状态机停留在该“测试状态”下，继续探测该链路是否连接，一旦完成与该链路对端邻居节点的连接，则再次通过LSU报文通知其余节点该链路已经恢复正常；假如该链路在整个时隙内始终未完成连接，那么在下一个时隙切换发生时，认为该链路已经暂时失效，邻居状态机转化为“关闭状态”以等待该链路修复。If a link of a node is in the "Leaving State" and is predicted to transition to the "Connecting State" in the next time slot, the node will begin attempting to connect to the link for a period of time T Test before the time slot switch occurs. T Test should be selected to ensure that it is greater than the minimum link connection time. Hello packets will be continuously sent to the neighbor at the other end of the link at a certain time interval T Hello . At this time, the link enters the "Testing State". The advance time T Test should ensure that the link can be connected within this time without any accidents. At the same time, the latitude corresponding to the time point of connection completion should be reasonably designed to ensure that the link connection conditions are met at the time of connection initiation. T Hello should be selected to ensure that a certain number of Hello packets can be sent within T Test time to prevent misjudgment due to accidental packet loss. T Hello and T Test are determined based on the actual on-board packet loss probability test results. The number of packets sent is sufficient to ensure a certain degree of judgment accuracy. If the link between this node and the neighboring node is successfully connected in the "Testing State", no LSU message is sent. The other nodes in the "orbital area" where the node is located will directly complete the calculation according to the LSA in the preset database. If T If the connection cannot be completed within the Test time, the LSU message will be used to notify the other nodes in the "track area" where the node is located. The other nodes will perform calculations based on the LSA contained in the received LSU message. At the same time, the neighbor state machine remains in the "test state" and continues to detect whether the link is connected. Once the connection with the neighbor node at the other end of the link is completed, the LSU message will be used again to notify the other nodes that the link has returned to normal. If the link is not connected throughout the entire time slot, then when the next time slot switch occurs, the link is considered to have temporarily failed, and the neighbor state machine will be converted to the "closed state" to wait for the link to be repaired. 2.根据权利要求1所述的面向大规模极地轨道星座的低开销OSPF协议改进方法，其特征是，配置与部署方式如下：2. The low-overhead OSPF protocol improvement method for large-scale polar orbit constellations according to claim 1 is characterized in that the configuration and deployment method is as follows: 对于一个卫星总数为N，轨道数量为P，相位因子为F的极地轨道星座，即相邻轨道同编号卫星的相位差为0≤F≤P-1且F为整数；其星间链路建立的典型情况为：每颗卫星将与同一轨道相邻的两颗卫星建立链路，同时与相邻轨道面相同编号的卫星建立链路，反向缝处不建立链路；当卫星运行到一定纬度之上时，轨道间链路将发生断开；如果一个极地轨道星座的链路建立符合上述典型情况，则可按照如下五个步骤配置OSPF协议的运行；若卫星与理想星座的位置存在偏差，但卫星与其理想位置的偏差，在所有时刻都不影响其与其余卫星或地面节点的连通，则可将实际星座中卫星的位置映射到其理想位置，再根据以下步骤部署改进后的OSPF协议；For a polar orbit constellation with a total number of satellites N, a number of orbits P, and a phase factor F, the phase difference between satellites with the same number in adjacent orbits is 0≤F≤P-1, where F is an integer. A typical inter-satellite link establishment scenario is that each satellite establishes links with two adjacent satellites in the same orbit, and also with satellites with the same number in adjacent orbital planes. No links are established at the reverse seam. When a satellite orbits above a certain latitude, the inter-orbit link is disconnected. If the link establishment for a polar orbit constellation meets the above typical scenarios, the OSPF protocol can be configured according to the following five steps. If a satellite's position deviates from the ideal constellation, but this deviation does not affect its connectivity with other satellites or ground nodes at all times, the actual constellation satellite position can be mapped to its ideal position, and the improved OSPF protocol can be deployed according to the following steps. 系统内的卫星采用S(i,j)，0≤i≤P-1,0≤j≤n-1进行表示，其中i表示轨道编号，j表示轨道内卫星编号，将卫星链路发生断开处纬度记为latM，单个轨道内的卫星数量记为n，则有nP＝N；The satellites in the system are represented by S(i, j), 0≤i≤P-1, 0≤j≤n-1, where i represents the orbit number and j represents the satellite number in the orbit. The latitude where the satellite link is disconnected is recorded as lat M , and the number of satellites in a single orbit is recorded as n, then nP＝N; 步骤1：确定时隙数量m；Step 1: Determine the number of time slots m; 将整个系统内的卫星运行的周期划分为若干个时隙；每个时隙中，如果没有发生意外故障，整个系统内卫星间的连接关系保持稳定；而在时隙发生切换时，整个系统内必有链路发生可预测通断变化，同时进行路由切换；因而一个极地轨道卫星通信星座绕地运行周期内发生路由切换的总次数，即为时隙数量m；The satellite operation cycle of the entire system is divided into several time slots. In each time slot, if there is no unexpected failure, the connection relationship between satellites in the entire system remains stable. However, when a time slot switch occurs, the links in the entire system must undergo predictable on-off changes and route switching. Therefore, the total number of route switches that occur during the orbital cycle of a polar orbiting satellite communication constellation is the number of time slots m. 为了方便得到m的取值，考虑到极地轨道星座的拓扑具有重复性，因而首先需要确定使得拓扑发生重复的最小轨道数量k；k的含义为，令i＝0，观察第i条轨道和第i+1条轨道间卫星的连接关系，i从0依次增加至P-2；经过k条轨道后，位于相同纬度的卫星的连接关系间可能发生完全重复，即k号轨道与k+1号轨道上卫星间的连接，在任何时刻，都与第0号和第1号轨道上对应纬度的卫星之间的连接关系完全相同；k的值通过式(1)计算得到：In order to conveniently obtain the value of m, considering that the topology of the polar orbit constellation is repetitive, it is first necessary to determine the minimum number of orbits k that causes the topology to repeat. The meaning of k is that, let i = 0, observe the connection relationship between the satellites in the i-th orbit and the i+1-th orbit, and i increases from 0 to P-2. After k orbits, the connection relationship between satellites at the same latitude may be completely repeated, that is, the connection between the satellites in orbit k and orbit k+1 is exactly the same as the connection relationship between the satellites at the corresponding latitudes in orbit 0 and orbit 1 at any time. The value of k is calculated by formula (1): 此后按照如下方式计算时隙数量：The number of time slots is then calculated as follows: (1)若kn为偶数，则当为整数时，m＝kn，否则m＝2kn；(1) If kn is an even number, then When it is an integer, m＝kn, otherwise m＝2kn; (2)若kn为奇数，则当或为整数时，m＝2kn，否则m＝4kn；(2) If kn is an odd number, then or When it is an integer, m＝2kn, otherwise m＝4kn; 步骤2：确定所有链路在每个时隙内的通断状况；Step 2: Determine the on/off status of all links in each time slot; (1)假设初始时刻卫星S(0,0)位于北纬latM处，计算此时所有轨道间链路两端的卫星位于的纬度，作为初始纬度值，并将当前时隙值记录为0；根据每条链路两端卫星的纬度值，确定其属于连接或断开状态；(1) Assume that the satellite S(0,0) is located at lat M at the initial moment. Calculate the latitudes of the satellites at both ends of all inter-orbital links at this moment as the initial latitude values, and record the current time slot value as 0. Based on the latitude values of the satellites at both ends of each link, determine whether it is connected or disconnected. (2)假设轨道的运行方向为：在时隙0时，S(0,0)正由南向北运动；找出当前时隙内最接近切换的链路，有多条时，任意选取即可；并计算距离此条链路距离发生切换需要转过的纬度latadd，此后时隙值加1，计算所有卫星按照运行方向转过纬度latadd后链路两端的纬度值，并判断其属于连接或断开状态；(2) Assume that the orbital direction is: at time slot 0, S(0,0) is moving from south to north; find the link closest to the handover in the current time slot. If there are multiple links, any link can be selected; and calculate the latitude lat add that needs to be rotated from this link for the handover to occur. After that, the time slot value is increased by 1. Calculate the latitude values of both ends of the link after all satellites rotate through the latitude lat add in the direction of operation, and determine whether it is connected or disconnected. (3)重复步骤(2)，直到卫星S(0,0)完成绕地一周，此时时隙值应增加为m-1，所有链路在每个时隙内的通断状况已经完成计算；与此同时，由于每次切换转过的纬度latadd已计算得到，而卫星运行的角速度已知，切换的时间间隔也将随之确定；(3) Repeat step (2) until the satellite S(0,0) completes one orbit around the Earth. At this time, the time slot value should increase to m-1, and the on-off status of all links in each time slot has been calculated. At the same time, since the latitude lat add of each handover has been calculated and the angular velocity of the satellite is known, the time interval of the handover will also be determined accordingly. 步骤3：进行“轨道区”划分；Step 3: Divide the “track area”; 确定每个“轨道区”的轨道数量，并进行“轨道区”划分；Determine the number of tracks in each "track area" and divide the "track area"; 步骤4：进行IP地址分配，并写出预置链路状态数据库；Step 4: Allocate IP addresses and write the pre-configured link state database; 完成“轨道区”划分后，对于每一个“轨道区”赋予一个独立的网段，该网段的子网掩码长度，要保证其中的每一条链路，都能在该“轨道区”网段下分配一个子网段，而链路子网段的子网掩码长度最长为30；同时，两个“轨道区”之间的链路也要被分配独立的IP网段；After the "track area" is divided, each "track area" is assigned an independent network segment. The subnet mask length of the network segment must ensure that each link in it can be allocated a subnet segment under the "track area" network segment, and the subnet mask length of the link subnet segment is up to 30. At the same time, the link between two "track areas" must also be assigned an independent IP network segment. 针对每个“轨道区”，根据上述网段分配和链路通断性计算，直接写出其链路状态数据库；运行过程中，每个“轨道区”内部的所有节点都将加载相同的预置链路状态数据库；For each "track zone", its link state database is directly written based on the above network segment allocation and link connectivity calculation. During operation, all nodes within each "track zone" will load the same preset link state database. 步骤5：加载预置链路状态数据库，对齐时隙后，运行协议；Step 5: Load the pre-set link state database, align the time slots, and run the protocol; 在星上运行该协议时，首先加载其所属“轨道区”的链路状态数据库；对时隙设置有两种情况：一，当卫星S(0,0)由南向北运行至北纬latM处时，将时隙设置为0，并开始运行改进后的OSPF协议；二，当系统内卫星位置与某一时隙起始时的位置相符时，系统内所有卫星同步置为该时隙，然后开始运行。When running the protocol on a satellite, the link state database of the "orbital zone" to which it belongs is first loaded; there are two cases for setting the time slot: first, when the satellite S(0,0) moves from south to north and reaches lat M , the time slot is set to 0 and the improved OSPF protocol begins to run; second, when the position of a satellite in the system matches the position at the start of a certain time slot, all satellites in the system are synchronized to that time slot and then start running. 3.根据权利要求1所述的面向大规模极地轨道星座的低开销OSPF协议改进方法，其特征是，进行“轨道区”划分的具体步骤：3. The low-overhead OSPF protocol improvement method for large-scale polar orbit constellations according to claim 1 is characterized in that the specific steps of dividing the "orbital area" are: 设每个“轨道区”有x条轨道，x为正整数且x≥2，整个系统的轨道区数量表示为每个“轨道区”内的节点数量表示为nx；Assume that each "track zone" has x tracks, x is a positive integer and x ≥ 2, the number of track zones in the entire system is expressed as The number of nodes in each “track zone” is denoted as nx; 若数据库中有y条Router-LSA，在采用优先级队列进行计算最短路径的情况下，其路由计算时间表示为：If there are y Router-LSAs in the database and priority queuing is used to calculate the shortest path, the route calculation time is expressed as: T1(y)＝aylog2y+by+c，其中a、b、c为固定参数 (2)T 1 (y) = aylog 2 y + by + c, where a, b, and c are fixed parameters (2) 若数据库中有y条AS-External-LSA，则其路由计算时间表示为：If there are y AS-External-LSAs in the database, the route calculation time is expressed as: T2(y)＝dy+e，其中d、e为固定参数 (3)T 2 (y) = dy + e, where d and e are fixed parameters (3) 对于参数a、b、c、d、e，用如下方式进行确定：对于协议的路由计算模块进行测试，分别改变Router-LSA和AS-External-LSA的数量，测量其路由计算时间，进行多组测量后，采用统计回归的方式，确定a、b、c、d、e的取值；The parameters a, b, c, d, and e are determined as follows: The protocol's route calculation module is tested by varying the number of Router-LSAs and AS-External-LSAs and measuring the route calculation time. After performing multiple measurements, statistical regression is used to determine the values of a, b, c, d, and e. 计算总时间T(x)表示为：The total calculation time T(x) is expressed as: 求导有The derivative is 因而T′(x)单调递增，分为如下情况：Therefore, T ′ (x) is monotonically increasing, which can be divided into the following cases: (1)当T′(2)≤0时，存在x0∈[2,+∞)，使得T′(x0)＝0，此时路由计算时间达到最小值，x0可借助计算机进行数值求解；x0不为整数，取x1为不大于x0的最大整数，x2为不小于x0的最小整数；若T(x1)≤T(x2)，则x1为最优取值，反之则x2为最优取值；(1) When T ′ (2) ≤ 0, there exists x 0 ∈ [2, + ∞) such that T ′ (x 0 ) = 0. At this time, the routing calculation time reaches the minimum value, and x 0 can be numerically solved with the help of a computer. If x 0 is not an integer, x 1 is the largest integer not greater than x 0 , and x 2 is the smallest integer not less than x 0. If T(x 1 ) ≤ T(x 2 ), then x 1 is the optimal value, otherwise x 2 is the optimal value. (2)当T′(2)>0时，不存在x0∈[2,+∞)，使得T′(x0)＝0，因而使得路由计算时间最短的轨道数量为2；(2) When T ′ (2)>0, there is no x 0 ∈[2,+∞) such that T ′ (x 0 )＝0, so the number of tracks with the shortest routing calculation time is 2; 取得令路由计算时间最小的单个“轨道区”内的轨道数量xBest后，即可进行“轨道区”划分，只要从0号轨道开始，依次将xBest个轨道划分为一个“轨道区”即可；当不为整数时，若相除余数为1，则将最后一条轨道并入最后一个“轨道区”，若余数大于等于2，则将末尾未分配的轨道单独划分为一个“轨道区”。After obtaining the number of tracks x Best in a single "track area" that minimizes the routing calculation time, the "track area" can be divided. Just start from track 0 and divide the x Best tracks into a "track area" in sequence. When it is not an integer, if the remainder is 1, the last track will be merged into the last "track area". If the remainder is greater than or equal to 2, the unallocated track at the end will be divided into a separate "track area". 4.根据权利要求1所述的面向大规模极地轨道星座的低开销OSPF协议改进方法，其特征是，在系统中卫星未出现增加或减少，且链路不出现永久性失效的情况下，预置数据库将始终保持不变；在卫星增加或减少的情况下，或链路出现永久性失效的情况下，首先使用OSPF原有的链路状态报文同步机制，通过LSU报文的发送，快速完成重路由，此后，需要针对变化后的拓扑，针对涉及到的“轨道区”，重新计算时隙数量和通断信息，重新写出链路状态数据库，并对于“轨道区”内所有卫星的预置链路状态数据库进行更新。4. The low-overhead OSPF protocol improvement method for large-scale polar orbit constellations according to claim 1 is characterized in that, when the number of satellites in the system does not increase or decrease, and the link does not permanently fail, the preset database will always remain unchanged; when the number of satellites is increased or decreased, or when a link fails permanently, the original link state message synchronization mechanism of OSPF is first used to quickly complete rerouting by sending LSU messages. After that, it is necessary to recalculate the number of time slots and on/off information for the "orbital area" involved in the changed topology, rewrite the link state database, and update the preset link state database of all satellites in the "orbital area".
CN202211687006.1A 2022-12-27 2022-12-27 A low-overhead OSPF protocol improvement method for large-scale polar orbit constellations Active CN116155796B (en)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN202211687006.1A CN116155796B (en) 2022-12-27 2022-12-27 A low-overhead OSPF protocol improvement method for large-scale polar orbit constellations

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN202211687006.1A CN116155796B (en) 2022-12-27 2022-12-27 A low-overhead OSPF protocol improvement method for large-scale polar orbit constellations

Publications (2)

Publication Number Publication Date
CN116155796A CN116155796A (en) 2023-05-23
CN116155796B true CN116155796B (en) 2025-08-22

Family

ID=86357511

Family Applications (1)

Application Number Title Priority Date Filing Date
CN202211687006.1A Active CN116155796B (en) 2022-12-27 2022-12-27 A low-overhead OSPF protocol improvement method for large-scale polar orbit constellations

Country Status (1)

Country Link
CN (1) CN116155796B (en)

Families Citing this family (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN117544227B (en) * 2023-11-22 2025-05-13 深圳星移联信科技发展有限公司 Intersatellite routing method and device for low-orbit constellation network based on BGP protocol
WO2025137777A1 (en) * 2023-12-28 2025-07-03 Mda Systems Ltd. Computer system and method for providing secure and reliable high-bandwidth low latency communications in remote locations

Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN107835128A (en) * 2017-09-29 2018-03-23 北京空间飞行器总体设计部 It is a kind of that OSPF method for routing is strengthened based on the spatial network for determining Link State
CN111371489A (en) * 2020-03-18 2020-07-03 重庆邮电大学 A topology-predictable inter-satellite routing method for satellite networks

Family Cites Families (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7805536B1 (en) * 2003-05-23 2010-09-28 Juniper Networks, Inc. Determining forwarding plane liveness
EP2625800A4 (en) * 2010-10-04 2016-11-23 Telcordia Tech Inc METHOD AND SYSTEM FOR ROAD DETERMINATION IN LOW-LEVEL ORBIT (LEO) SATELLITE NETWORKS WITH BANDWIDTH AND PRIORITY TAKING AND ADAPTIVE REROUTING
CN105375974B (en) * 2015-10-16 2019-03-01 中国人民解放军国防科学技术大学 Low overhead dynamic routing method towards mobile satellite network
CN113824636B (en) * 2020-06-18 2024-10-15 中兴通讯股份有限公司 Message sending method, receiving method, electronic device, system and storage medium
CN113489528A (en) * 2021-07-05 2021-10-08 北京理工大学 Self-adaptive survivability method suitable for inter-satellite routing

Patent Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN107835128A (en) * 2017-09-29 2018-03-23 北京空间飞行器总体设计部 It is a kind of that OSPF method for routing is strengthened based on the spatial network for determining Link State
CN111371489A (en) * 2020-03-18 2020-07-03 重庆邮电大学 A topology-predictable inter-satellite routing method for satellite networks

Also Published As

Publication number Publication date
CN116155796A (en) 2023-05-23

Similar Documents

Publication Publication Date Title
CN112468206B (en) Partition-based constellation satellite network distributed routing method and device
CN116155796B (en) A low-overhead OSPF protocol improvement method for large-scale polar orbit constellations
US7206309B2 (en) High availability packet forward apparatus and method
US7155632B2 (en) Method and system for implementing IS-IS protocol redundancy
CN101465859B (en) Method and device for triggering main and standby interface board inverse switch
CN101471849B (en) Protection method for packet transmission network
JP4449903B2 (en) Router device and network connection method
CN110708245B (en) SDN data plane fault monitoring and recovery method under multi-controller architecture
US20140146661A1 (en) Method and apparatus for facilitating process restart in an is-is system
CN101483592B (en) Method and apparatus for inhibiting bidirectional forwarding detection link oscillation
JPH09224026A (en) Communication node, failure recovery method, and communication network
CN102474446A (en) Recovery mechanism for point-to-multipoint traffic
CN103780407A (en) Gateway dynamic switching method and apparatus in distributed resilient network interconnection (DRNI)
WO2018166308A1 (en) Distributed nat dual-system hot backup traffic switching system and method
CN117394904A (en) Link fault recovery method and system for large-scale domain-division satellite network
EP1940091B1 (en) Autonomous network, node device, network redundancy method and recording medium
CN116566472A (en) A Wide-area Routing Mechanism for Space-Ground Integrated Networks Oriented to Dynamic Discrete Topology
CN107547374B (en) Aggregation route processing method and device
CN101964743A (en) Multiprotocol label-switched path APS (Active Protection System) protection and management method, equipment and system
Lv et al. Research of adaptive routing scheme for LEO network
CN101562575A (en) MPLS TE FRR fast switching method and device thereof
US7496644B2 (en) Method and apparatus for managing a network component change
JP2004080211A (en) Route control method and device, route control program, and storage medium storing route control program
WO2017063166A1 (en) Method and device for establishing label-switched path circumventing disconnected link
RU2586568C2 (en) Method and device for protection of interring communication service

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