CN118523913B - Quantum key relay route calculation method and system - Google Patents
Quantum key relay route calculation method and system Download PDFInfo
- Publication number
- CN118523913B CN118523913B CN202410985643.XA CN202410985643A CN118523913B CN 118523913 B CN118523913 B CN 118523913B CN 202410985643 A CN202410985643 A CN 202410985643A CN 118523913 B CN118523913 B CN 118523913B
- Authority
- CN
- China
- Prior art keywords
- node
- nodes
- key
- adjacent
- virtual
- 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
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
- H04L9/08—Key distribution or management, e.g. generation, sharing or updating, of cryptographic keys or passwords
- H04L9/0816—Key establishment, i.e. cryptographic processes or cryptographic protocols whereby a shared secret becomes available to two or more parties, for subsequent use
- H04L9/0852—Quantum cryptography
- H04L9/0855—Quantum cryptography involving additional nodes, e.g. quantum relays, repeaters, intermediate nodes or remote nodes
-
- 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
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
- H04L9/08—Key distribution or management, e.g. generation, sharing or updating, of cryptographic keys or passwords
- H04L9/0861—Generation of secret information including derivation or calculation of cryptographic keys or passwords
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Computer Security & Cryptography (AREA)
- Physics & Mathematics (AREA)
- Electromagnetism (AREA)
- Theoretical Computer Science (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
Abstract
本发明公开了一种量子密钥中继路由计算方法及系统，方法包括收集量子密钥网络中各量子设备的设备状态及链路信息并构建网络拓扑图；融合链路密钥生成速率、节点状态及并发中继数量，从所述网络拓扑图中删除无用的节点，得到索引子图；采用路径规划算法对所述索引子图进行启发式搜索，计算最佳路由路径；本发明保证在出现密钥中继请求时能够快速计算出最优路由且兼顾业务的实时并发情况，所提方法实际可用且高效。
The present invention discloses a quantum key relay route calculation method and system, the method comprises collecting the device status and link information of each quantum device in a quantum key network and constructing a network topology map; integrating the link key generation rate, the node status and the number of concurrent relays, deleting useless nodes from the network topology map, and obtaining an index sub-map; using a path planning algorithm to perform a heuristic search on the index sub-map, and calculating an optimal routing path; the present invention ensures that when a key relay request occurs, the optimal route can be quickly calculated and the real-time concurrency of the business is taken into consideration, and the proposed method is practical and efficient.
Description
Technical Field
The invention relates to the technical field of quantum communication, in particular to a quantum key relay route calculation method and a system.
Background
Quantum cryptography based on quantum key distribution (Quantum Key Distribution, QKD) protocol is one of the future industries that has developed rapidly in recent years, and unlike traditional cryptography based on mathematics, quantum cryptography is based on quantum mechanics, ensures security of symmetric key distribution by utilizing quantum physical characteristics, and cryptographically protects data by utilizing distributed quantum keys.
The network for generating and distributing quantum keys and providing quantum cryptographic services to the outside is called a quantum cryptographic network, in which a quantum key distribution network based on an optical path and a quantum key distribution device (i.e., QKD device) and a quantum key management network based on a classical communication link and a quantum key management device are integrated. Because of the limitation of the maximum effective distance of key generation between QKD devices, many QKD devices do not have direct quantum links, and direct distribution of quantum keys cannot be realized, but relay transmission of quantum keys is realized by a quantum key management network. Due to network deployment difficulty and cost, a quantum key distribution network is not generally a full connected graph, so that a proper quantum relay link, namely a quantum key relay route, needs to be selected in the quantum key relay process.
In the related art, patent application document with publication number CN104579964a discloses a quantum cryptography network routing method, which calculates routes centrally through a routing server, periodically updates network topology and issues the updated routes to all relay nodes, and the relay nodes calculate routes themselves. The route calculation method takes the relay node as a root node to construct a tree, and finishes the route from one node to all nodes in a breadth-first traversal mode. When selecting a route, a route with the least passing node is preferentially selected; when a plurality of paths with the same node number exist, selecting a path with the maximum minimum value of the residual quantum key quantity in the nodes; when there are multiple paths with the same minimum value, the path with the largest next-smallest value is selected, and so on.
Patent application publication No. CN115460129A discloses a quantum key distribution routing method based on an OSPF protocol, wherein each relay KM monitors the change of a neighbor relation and transmits link change information to the whole area through flooding, and each KM updates a link database maintained by itself. When calculating the route, the KM uses the node as a tree root, and calculates the optimal path using a weighted SPF algorithm, but the algorithm does not give a definition of the weight.
The routing method disclosed in the patent application publication No. CN116032821A takes the rate with the lowest generation rate in the quantum key link as the link rate and takes the rate as the route selection basis; the key generation method disclosed in the patent application document with publication number of CN114362937A integrates the KM key quantity and the key reduction rate of the period to order the links; the routing method disclosed in the patent application publication CN106230582a is to select a plurality of shortest paths based on a distance vector routing algorithm and randomly select one of the shortest paths as a routing result.
In the scheme, node information reported by KM is directly sequenced and connected to form a routing table, and calculation of an optimal routing path is not involved.
In the above technology, the whole network topology is generally established manually by default by an administrator, and the device cannot be updated adaptively; in addition, although the related technology has the functions of collecting topology and calculating routes by the central management node and the functions of discovering adjacency and calculating routes by each relay node, no method is considered in the process of route calculation, and the usability in actual network deployment and the possible lack in engineering application exist. Because the existing method has complicated networking, equipment cannot be automatically found when the network is accessed, the automatic network access is realized by manually configuring the equipment by equipment, and a pair of keys is preset for all the equipment pairs to be connected. And each node needs to deploy a switch, and the connection lines include but are not limited to: KM and QKDN, KM and KMN, KM, a network management system and the like. In the existing route calculation method, each node self-calculation method requires the KM node to store and maintain a large amount of route information, and the network state change can cause large-scale KM route change to cause flooding effect.
Disclosure of Invention
The invention aims to solve the technical problem of providing a practical and efficient quantum cryptography network route calculation method, which ensures that the optimal route can be calculated quickly when a key relay request occurs and gives consideration to the real-time concurrency of services.
The invention solves the technical problems by the following technical means:
the invention provides a quantum key relay route calculation method, which comprises the following steps:
Collecting device states and link information of all quantum devices in a quantum key network and constructing a network topology graph;
fusing the link key generation rate, The state of the nodes and the number of concurrent relays are deleted from the network topology map to be uselessNodes obtain index subgraphs;
and performing heuristic search on the index subgraph by adopting a path planning algorithm, and calculating an optimal routing path.
Further, the collecting the device state and the link information of each quantum device in the quantum key network and constructing a network topology graph includes:
transmitting hello messages to the directly connected neighbor nodes to confirm the connection relation, and storing the connection state of the current quantum key network by adopting a data structure;
At each of After successful network access, the equipment receives successful network accessReporting information sent by equipment, wherein the reporting information comprises equipment state, adjacent equipment information and link information;
Based on each successful network access The equipment gradually perfects the network connection state stored in the data structure untilAll the adjacent device information uploaded by the device is already present in the data structure storing the network connection state;
Timing receiving successful network access And the quantum key generation rate reported by the device, and the quantum key generation rate, the key pool capacity and the network connection state in the data structure are correspondingly stored to generate the network topology graph, wherein the network topology graph is a right undirected graph, nodes in the right undirected graph are all quantum devices in the quantum key network, and the edges are connection states.
Further, the key pool capacity is that network access is successfulThe device successfully obtains the data fromAnd (5) checking the quantum key of the device at fixed time.
Further, the fused link key generation rate,The state of the nodes and the number of concurrent relays are deleted from the network topology map to be uselessThe node, obtain index subgraph, include:
Normal state in the network topology diagram The nodes are respectively split into a set number of virtual nodes, and the available key quantity of each virtual node is calculated based on the key pool residual quantity of each virtual node, the average key generation rate of the virtual node and the adjacent nodes in the past time period T and the key relay task borne by the virtual node;
Judging whether the available key quantity of a certain virtual node exceeds the applied key quantity of the key relay in a certain upcoming time period;
if yes, reserving the virtual node;
If not, deleting the virtual node;
If the state is normal If the virtual nodes are not deleted, each node is respectively deletedAnd all virtual nodes under the node are contracted into one node, and the index subgraph is obtained.
Further, the node in the network topology graph is in normal stateThe node is split into a set number of virtual nodes, and based on the key pool remaining amount of each virtual node, the average key generation rate of the virtual node and the adjacent nodes in the past time period T and the key relay task borne by the virtual node, the method calculates the available key amount of each virtual node, and comprises the following steps:
Copying the network topological graph to obtain an index graph;
Deleting the index map in the fault state Node and will be in normal stateThe node is split into a set number of virtual nodes, and based on the key pool remaining quantity of each virtual node, the average key generation rate of the virtual node and the adjacent nodes in the past time period T and the key relay task borne by the virtual node, the available key quantity of each virtual node is calculated as follows:
in the method, in the process of the invention, Is the firstThe amount of keys available to the individual virtual nodes,Is the firstThe key pool remaining amount of the individual virtual nodes,Is the firstThe average key generation rate of each virtual node and the neighboring node over the past period T,Is the firstThe key relay task that the individual virtual nodes are assuming,，The number of relay tasks that are undertaken for the virtual node.
Further, the heuristic search is performed on the index subgraph by using a path planning algorithm, and an optimal routing path is calculated, including:
Adding a departure node in the index subgraph into an open list;
Adding the reachable adjacent node of the starting node into an open list, setting the starting node as a parent node of the reachable adjacent node, and calculating the cost of the reachable adjacent node from the starting node as the cost of the parent node from the starting node plus 1;
Removing the departure node from the open list and adding the departure node to the close list;
traversing each node in the open list as a current node, calculating the priority of each node in the open list according to the cost of the current node from the departure node and the cost of the current node from the target node, and removing the node with the highest priority from the open list and adding the node into the close list;
Retrieving adjacent nodes of the nodes added into the close list, if the adjacent nodes are skipped in the close list, otherwise, calculating the cost of the adjacent nodes from the departure node;
Repeating the step of calculating the priority of each node in the open list until the target node is added into the open list;
and gradually tracking the father node from the target node until reaching the departure node, and obtaining the optimal routing path.
Further, the cost of the current node from the departure node is the number of nodes from the departure node to the current node path, and the cost of the current node from the target node is the number of nodes from the current node to the target node path.
Further, the calculation formula of the cost of the current node from the target node is as follows:
in the method, in the process of the invention, For the current nodeThe cost of the distance from the target node,For the current nodeIs a function of the longitude of (1),For the current nodeIs a function of the latitude of (1),Is the longitude of the target node,As the latitude of the target node,For the purpose of kilometers,Representing an upward rounding.
Further, the priority calculation formula of each node is:
in the method, in the process of the invention, Representing nodesIs a comprehensive priority of (1); Is a node Cost from the departure node; Is a node An estimated cost from the target node.
Further, the method further comprises:
When a plurality of nodes with the same priority exist in the open list, one node is randomly selected from the plurality of nodes with the same priority, removed from the open list and added into the close list.
Further, the retrieving the neighboring node of the node added to the close list, if the neighboring node is skipped in the close list, otherwise, calculating the cost of the neighboring node from the departure node includes:
retrieving the neighboring nodes of the node added to the close list and judging whether the neighboring nodes of the node newly added to the close list are in the close list;
If in close list, skip;
If the node is not in the close list, judging whether the adjacent node of the node newly added into the close list is in the open list;
If not, adding the adjacent node into an open list, setting a parent node of the adjacent node of the node newly added into the close list, and calculating the cost of the adjacent node from the departure node as the cost of the parent node from the departure node plus 1;
If yes, calculating the cost of the adjacent node from the departure node in the new path as the cost of the parent node of the adjacent node from the departure node plus 1, and comparing the cost of the adjacent node from the departure node when the adjacent node passes through the previous path;
Based on the comparison result, if the previous path is better, no operation is performed, and if the new path is better, the parent node of the adjacent node is set as the node newly added into the close list.
In addition, the invention also provides a quantum key relay route computing system, which comprises:
the network topology diagram construction module is used for collecting the device states and link information of all quantum devices in the quantum key network and constructing a network topology diagram;
an index sub-graph generation module for fusing the link key generation rate, The state of the nodes and the number of concurrent relays are deleted from the network topology map to be uselessNodes obtain index subgraphs;
And the optimal route calculation module is used for performing heuristic search on the index subgraph by adopting a route planning algorithm to calculate an optimal route.
Furthermore, the invention also provides a computer readable storage medium, on which a computer program is stored, which when being executed by a processor, implements the quantum key relay route calculation method as described above.
The invention has the advantages that:
(1) The invention firstly collects the device state and link information of each quantum device and constructs the network topology diagram, and generates the index subgraph on the basis of the network topology diagram, the generation mode of the index subgraph increases the consideration of the link key generation rate and the concurrent relay quantity, and also considers the conditions of node states and the like, thereby effectively avoiding the core cause The problem that no key is available in the relay which occurs later due to the overlarge relay concurrence of the node; finally, actively searching a path consistent with the direction of the target node on the index subgraph through a heuristic function, and determining an optimal routing path; the quantum key relay route calculation method is a practical and efficient quantum cipher network route calculation method, and ensures that the optimal route can be calculated quickly when a key relay request occurs and the real-time concurrency condition of the service is considered.
(2) The invention is based on real-time uploadingThe adjacency dynamically changes the network topology, and is helpful for screening out the optimal path by the network relay route.
(3) The invention actively searches the path consistent with the direction of the destination node through the heuristic function, takes the minimum number of nodes passing through the path as the optimal path, and can effectively reduce the relay key quantity wasted in the relay process.
(4) The invention realizes the network control and network management by fusion, improves the multiplexing rate of management information, reduces the amount of management information transmitted in the network, lightens the load of a management and control system and is beneficial to practical realization.
Additional aspects and advantages of the invention will be set forth in part in the description which follows and, in part, will be obvious from the description, or may be learned by practice of the invention.
Drawings
Fig. 1 is a schematic flow chart of a quantum key relay route calculation method according to an embodiment of the present invention;
FIG. 2 is a flow chart of network topology generation in an embodiment of the present invention;
FIG. 3 is a diagram of an original network topology constructed in an embodiment of the present invention;
FIG. 4 is a schematic diagram illustrating virtual node splitting in accordance with an embodiment of the present invention;
FIG. 5 is a topology diagram of an embodiment of the invention resulting from the deletion of available nodes from FIG. 4;
FIG. 6 is a sub-graph of the index translated from FIG. 5 in accordance with one embodiment of the present invention;
FIG. 7 is a schematic diagram of a routing path calculation algorithm according to an embodiment of the present invention;
FIG. 8 is a schematic diagram illustrating a quantum key relay routing computing system according to an embodiment of the present invention;
fig. 9 is a diagram of a quantum key distribution network architecture implemented using a network control and network management convergence in one embodiment of the invention.
Detailed Description
For the purpose of making the objects, technical solutions and advantages of the embodiments of the present invention more apparent, the technical solutions in the embodiments of the present invention will be clearly and completely described in the following in conjunction with the embodiments of the present invention, and it is apparent that the described embodiments are some embodiments of the present invention, but not all embodiments. All other embodiments, which can be made by those skilled in the art based on the embodiments of the invention without making any inventive effort, are intended to be within the scope of the invention.
As shown in fig. 1, a first embodiment of the present invention proposes a quantum key relay route calculation method, which includes the following steps:
S10, collecting device states and link information of all quantum devices in a quantum key network and constructing a network topology graph;
it should be noted that, in the quantum key collecting network of the present embodiment Device status and link information for devices, QKD devices, etc., specifically, device status and link status may be collected in an incremental manner, eachThe device only maintains the device information adjacent to the device and the directly connected link information, and does not maintain the whole network topology and the route.
It should be understood that the number of the devices,Devices adjacent to the device include, but are not limited to, quantum key network distribution controller QKDNC, othersDevices, QKD devices, traffic systems, etc.
S20, fusing the link key generation rate,The state of the nodes and the number of concurrent relays are deleted from the network topology map to be uselessNodes obtain index subgraphs;
It should be noted that, in this embodiment, considering that in an actual quantum key distribution network, key relay between a plurality of different nodes may occur simultaneously, when performing new relay route calculation, key consumption generated by an ongoing key relay and repeated occurrence in a relay link should be estimated And the concurrency capability of the nodes is fused with the link key generation rate, the node state and the concurrency relay quantity, and an index subgraph is generated from the network topological graph and is used for calculating the current route path.
S30, heuristic searching is carried out on the index subgraph by adopting a path planning algorithm, and an optimal routing path is calculated.
The quantum key relay route calculation method provided by the embodiment can be applied to quantum key distribution equipment, and by generating index subgraphs on the basis of a network topological graph, the generation mode of the index subgraphs increases the consideration of the link key generation rate and the concurrent relay quantity, also considers the conditions of node states and the like, and can effectively avoid the core-caused situationThe problem that no key is available in the relay which occurs later due to the overlarge relay concurrence of the node; finally, actively searching a path consistent with the direction of the target node on the index subgraph through a heuristic function, and determining an optimal routing path; the proposal can ensure that the optimal route can be calculated rapidly when the key relay request occurs and give consideration to the real-time concurrence condition of the service.
Further, for the purpose of convenient management and minimizing the amount of management information in the network, the embodiment fuses the network element for implementing the QKD network control function and the network element for implementing the QKD network management function based on the design of the architecture and the division of the network elements in the quantum secret communication network function architecture popular in the current industry, so as to form a quantum key network distribution controller (Quantum Key Distribution Network Controller, abbreviated as QKDNC) which can be used for collecting the device state and the link state for implementing the QKD network management function to draw the network topology.
In this network architecture, devices that have just entered the network (includingDevice and QKD device) applies QKDNC for network access, successful network accessThe device reports device information and link state to QKDNC, which is used for topology drawing of the quantum key network and can be multiplexed in network device management. The multiplexing rate of the management information is improved through the integration of the network control and the network management, the amount of the management information transmitted in the network is reduced, the load of a management and control system is lightened, and the practical deployment is facilitated.
Further, after obtaining the device state and link information of each quantum device in the quantum key network, constructing a network topology, wherein the constructing steps are as follows:
S11, a hello message is sent to a directly connected neighbor node to confirm the connection relation, and a data structure is adopted to store the connection state of the current quantum key network;
Specifically, QKDNC sends hello packets to the neighboring nodes to confirm the connection relationship, and stores the connection state of the current quantum key network by adopting a data structure, where the data structure may be an adjacency table, an adjacency matrix, an adjacency multiple table, and the like, and the stored network connection state includes, but is not limited to, adjacency relationship, device type, and the like, and the embodiment is not limited specifically.
S12, at eachAfter successful network access, the equipment receives successful network accessReporting information sent by equipment, wherein the reporting information comprises equipment state, adjacent equipment information and link information;
In particular, network access After successful network access, the device sends hello message to its neighbor node to confirm connection relationship, and records information such as adjacency relationship, device type, etc. so as to make QKDNC receive successful network accessReporting information sent by the equipment.
It should be noted that the neighboring nodes described in this embodiment include, but are not limited to QKDNC, othersDevices, QKD devices, traffic systems, etc., the present embodiment is not particularly limited.
S13, according to each successful network accessThe equipment gradually perfects the network connection state stored in the data structure untilAll the adjacent device information uploaded by the device is already present in the data structure storing the network connection state;
In particular, the method comprises the steps of, The device reports the information to QKDNC when the device collects the information each time and finds that the collected information is different from the information reported to QKDNC last time; QKDNC retrieving the newly received report information in a data structure for storing the network connection state, and if the information is not retrieved, supplementing and perfecting the content of the data structure; when the information such as the adjacency relation and the equipment type received by QKDNC are the same as the stored connection information, the data structure for storing the network connection state is not modified.
S14, receiving successful network access at fixed timeAnd the quantum key generation rate reported by the device, and the quantum key generation rate, the key pool capacity and the network connection state in the data structure are correspondingly stored to generate the network topology graph, wherein the network topology graph is a right undirected graph, nodes in the right undirected graph are all quantum devices in the quantum key network, and the edges are connection states.
Specifically, after the network-connected QKD device successfully establishes a quantum key distribution link and generates a quantum key, counting the key generation rate of the network-connected QKD device, and reporting the quantum key generation rate to QKDNC every time when the QKD device passes a specific time interval; network accessThe device periodically checks the key pool capacity and reports to QKDNC after successfully acquiring the quantum key from the QKD device.
As shown in FIG. 2, QKDNC initially knows only the direct connection theretoDevice presence and device status, with eachAfter successful network access, the device status, adjacent device information and link information are uploaded to QKDNC, and QKDNC gradually improves the network topology untilAll adjacent device information uploaded by the device exists in the topology, QKDNC corresponds and stores the received key generation rate and key pool capacity with the stored connection relation, a right-of-no-direction diagram is formed as shown in figure 3, the nodes of the diagram are all quantum devices in the network, the sides are connected, the nodes refer to a physical machine room, and one node is internally provided with one physical machine roomA device and one or more QKD devices.
The scheme provided by the embodiment is convenient to network, reduces the number of links of each node and the number of overall links in the network, and enables all devices to be automatically connected QKDNC to access the network, so that the dynamic self-adaption device off-network and on-network can be realized.
Further, the method comprises the steps of,The device performs the purpose onceAfter the device relays the operation for its own key, report the message that the relay has been completed to QKDNC.
Further, whenWhen an abnormal alarm occurs to the device or QKD device, alarm information is reported QKDNC.
Further, the step S20: fusing the link key generation rate,The state of the nodes and the number of concurrent relays are deleted from the network topology map to be uselessThe node obtains an index subgraph, and specifically comprises the following steps:
S21, the state in the network topological graph is normal The nodes are respectively split into a set number of virtual nodes, and the available key quantity of each virtual node is calculated based on the key residual quantity in a key pool of each virtual node, the average key generation rate of the virtual node and the adjacent node in the past time period T and the key relay task born by the virtual node;
S22, judging whether the available key quantity of a certain virtual node exceeds the key quantity applied for the key relay in a certain upcoming time period, if so, executing a step S23, and if not, executing a step S24;
s23, reserving the virtual node;
s24, deleting the virtual node;
s25, if the state is normal If the virtual nodes are not deleted, each node is respectively deletedAnd all virtual nodes under the node are contracted into one node, and the index subgraph is obtained.
Further, the step S21: normal state in the network topology diagramThe node is split into a set number of virtual nodes, and based on the key pool remaining amount of each virtual node, the average key generation rate of the virtual node and the adjacent nodes in the past time period T and the key relay task borne by the virtual node, the method calculates the available key amount of each virtual node, and specifically comprises the following steps:
S211, copying the network topological graph to obtain an index graph;
It should be noted that, considering that there may be paths between a plurality of different nodes that are calculated concurrently, it is not possible to process on the original network topology at the same time, and if it is processed on the original network topology, it is only possible to perform the route calculation once, and it is not possible to perform the route calculation next time, so this embodiment copies the network topology, and operates on the index map obtained by the copying.
S212, for anyNode, assuming that the node is connected toGenerating a key between adjacent nodes, the node maintainsPersonal key poolDeleting the key link in the fault state in the index mapNode, whenWhen the state of the node is normal, the state is normalSplitting the nodes into a set number of virtual nodes to obtain a network topological graph with the virtual nodes split as shown in fig. 4, and calculating the available key quantity of each virtual node based on the key pool remaining quantity of each virtual node, the average key generation rate of the virtual node and the adjacent nodes in the past time period T and the key relay task born by the virtual node, wherein the available key quantity of each virtual node is as follows:
in the method, in the process of the invention, Is the firstThe amount of keys available to the individual virtual nodes,Is the firstThe key pool remaining amount of the individual virtual nodes,Is the firstThe average key generation rate of each virtual node and the neighboring node over the past period T,Is the firstThe key relay task that the individual virtual nodes are assuming,，The number of relay tasks that are undertaken for the virtual node.
For example, after splitting the virtual nodes, calculating the available key quantity for each virtual node, calculating the key stock of the node after 3 minutes according to the key generation rate on the current link, deleting the virtual nodes with unavailable or insufficient key quantity, the deleting result is shown in fig. 5, and generating an index subgraph is shown in fig. 6.
It should be noted that, considering that in the actual quantum key distribution network, key relays between a plurality of different nodes may occur at the same time, when new relay route calculation is performed, key consumption generated by the ongoing key relay and concurrency capability of KM nodes repeatedly occurring in the relay link should be estimated, link key generation rate, node state and concurrency relay number are fused, an index sub-graph is generated from the connection relation graph, the consideration of the link key generation rate and the concurrency relay number is increased by the index sub-graph generation mode, the conditions of abnormal node state and the like are also considered, and the route is generated on the basis of the index sub-graph, so that the problem that relay keyless is available after the relay concurrency quantity of the core KM nodes is overlarge can be effectively avoided.
Further, the step S30: and performing heuristic search on the index subgraph by adopting a path planning algorithm, and calculating an optimal routing path, wherein the method specifically comprises the following steps of:
S31, setting the departure node in the index subgraph Adding to open list;
it should be noted that the departure node is the node that puts forward the demand.
S32, setting the departure nodeAdding reachable adjacent nodes into open list, and adding the departure node to the open listSetting a parent node of the reachable adjacent node, and calculating the cost of the reachable adjacent node from the departure node as the cost of the parent node from the departure node plus 1;
From the departure node, the method Starting, willAdding an open list, the cost of the departure node from the starting point is the cost of the departure nodeAnd is noted as 0.
In particular, the search and departure nodeAdjacent nodes, adding the reachable nodes in the adjacent nodes into open list, and starting the nodesSetting the parent nodes of the reachable nodes and setting the cost of the reachable nodes from the departure node as the parent nodes。
S33, the departure nodeRemove from open list and add to close list;
S34, traversing each node in the open list as a current node, calculating the priority of each node in the open list according to the cost of the current node from the departure node and the cost of the current node from the target node, and removing the node with the highest priority from the open list and adding the node into the close list;
S35, searching adjacent nodes of the nodes added into the close list, if the adjacent nodes are skipped in the close list, otherwise, calculating the cost of the adjacent nodes from the departure node;
s36, repeating the steps S34-S35 until the target node is added into the open list;
s37, gradually tracking the father node from the target node until reaching the departure node, and obtaining the optimal routing path.
Further, the cost of the current node from the departure node is the number of nodes from the departure node to the current node path, and the cost of the current node from the target node is the number of nodes from the current node to the target node path.
In the quantum key relay, the smaller the number of nodes passed, the smaller the number of keys consumed by the relay, and the lower the generated delay, so in this embodiment, the number of nodes used is used to judge the node priority. And recording the number of nodes passing from the starting node to the current node, predicting the number of nodes passing from the current node to the target node, and searching the index subgraph in the range.
Further, the calculation formula of the cost of the current node from the target node is as follows:
in the method, in the process of the invention, For the current nodeThe cost of the distance from the target node,For the current nodeIs a function of the longitude of (1),For the current nodeIs a function of the latitude of (1),Is the longitude of the target node,As the latitude of the target node,For the purpose of kilometers,Representing an upward rounding.
In this embodiment, based on a semi-normal formula, an earth model is selected as a spherical model, and the spherical distance between two coordinates is calculated based on the equatorial radius to averageKilometers a node to estimate the number of nodes of the path from the current node to the target node,The value is determined by the specific network deployment scenario.
Further, the priority calculation formula of each node is:
in the method, in the process of the invention, Representing nodesIs a comprehensive priority of (1); Is a node Cost from the departure node; Is a node An estimated cost from the target node.
When the routing calculation is performed, in view of the fact that the quantum network is a two-dimensional authorized undirected non-connected graph, the graph is unobstructed, a heuristic algorithm is suitable to be used, and the path planning algorithm is selected in the embodimentA heuristic search is performed to compute the priority of each node as a heuristic function, wherein,A smaller value indicates a smaller cost to consume, a shorter path, and a higher overall priority for the node.
Further, the present embodiment selects one from the open listNode with minimum valueRemoving it from the open list and adding a close list; if the comprehensive priority values of a plurality of nodes are the same, one node is randomly selected from the plurality of nodes, removed from the open list and added to the close list.
Further, the step S35: retrieving a neighboring node of the node added into the close list, if the neighboring node is skipped in the close list, otherwise, calculating the cost of the neighboring node from the departure node, specifically comprising the following steps:
S351, searching adjacent nodes of the nodes added into the close list, judging whether the adjacent nodes of the nodes newly added into the close list are in the close list, if yes, skipping, and if not, executing step S352;
S352, judging whether the adjacent node of the node newly added into the close list is in the open list, if not, executing the step S353, and if so, executing the step S354;
S353, adding the adjacent node into an open list, setting a parent node of the adjacent node of the node newly added into the close list, and calculating the cost of the adjacent node from the departure node as the cost of the parent node from the departure node plus 1;
S354, calculating the cost of the adjacent node from the departure node in the new path, wherein the cost of the parent node of the adjacent node from the departure node is added with 1, and comparing with the cost of the adjacent node from the departure node when the adjacent node passes through the previous path;
and S355, based on a comparison result, if the previous path is better, not operating, and if the new path is better, setting the father node of the adjacent node as the node newly added into the close list.
In particular, if a node newly added to close listIf the adjacent node is not in close list and is not in open list, then the adjacent node is added to open list, and the node is addedSet as the father node of the adjacent nodes, and set the adjacent nodes as the father node of the adjacent nodesThe value being set as its parent nodeA value of +1; if a neighboring node is already in the open list, then the neighboring node in the new path is calculatedThe value being its parent nodeA kind of electronic deviceValue +1, and the adjacent node passes through the previous pathComparing the values, if the previous path is better, not operating, if the new path is better, setting the father node of the node as the nodeAnd to connect the adjacent nodesValue replacement to the node in the new pathValues.
As shown in fig. 7, in this embodiment, a heuristic function is used to actively find a path consistent with the direction of a destination node, and the path with the least number of nodes passing through is used as an optimal path, so that the amount of relay keys wasted in the relay process can be effectively reduced.
Further, as shown in fig. 8, a second embodiment of the present invention proposes a quantum key relay routing calculation system, the system including:
The network topology diagram construction module 10 is used for collecting the device state and link information of each quantum device in the quantum key network and constructing a network topology diagram;
an index sub-graph generation module 20 for fusing the link key generation rate, The state of the nodes and the number of concurrent relays are deleted from the network topology map to be uselessNodes obtain index subgraphs;
and the optimal route calculation module 30 is configured to perform heuristic search on the index subgraph by using a path planning algorithm to calculate an optimal route.
According to the method, the index subgraph is generated on the basis of the generated network topological graph, the index subgraph generation mode increases the consideration of the link key generation rate and the concurrent relay quantity, the conditions of abnormal node states and the like are also considered, and the problem that a relay is not available after the core KM node relay concurrency quantity is too large can be effectively avoided.
Specifically, the quantum key relay routing computing system provided in this embodiment may be implemented by adopting a network control and network management fusion, where a quantum key distribution network architecture is shown in fig. 9, and in this embodiment, a currently occurring quantum key relay requirement is initiated by KM-1, so as to establish a 300bytes quantum key shared between KM-1 and KM-9. QKDNC carrying out virtual node splitting on nodes in the generated network topological graph, after the virtual nodes are split, calculating available key quantity for each virtual node, calculating key stock of the node after 3 minutes according to the key generation rate on the current link, deleting the virtual nodes which are not available or have insufficient key quantity, generating an index subgraph, and carrying out optimal route calculation based on the index subgraph.
Further, the network topology construction module 10 includes:
the information storage module is used for sending hello messages to the directly connected neighbor nodes to confirm the connection relation and storing the connection state of the current quantum key network by adopting a data structure;
information receiving module for each After successful network access, the equipment receives successful network accessReporting information sent by equipment, wherein the reporting information comprises equipment state, adjacent equipment information and link information;
information updating module for each successful network access The equipment gradually perfects the network connection state stored in the data structure untilAll the adjacent device information uploaded by the device is already present in the data structure storing the network connection state;
a topology diagram generation module for receiving success of network access at fixed time And the quantum key generation rate reported by the device, and the quantum key generation rate, the key pool capacity and the network connection state in the data structure are correspondingly stored to generate the network topology graph, wherein the network topology graph is a right undirected graph, nodes in the right undirected graph are all quantum devices in the quantum key network, and the edges are connection states.
Further, the index subgraph generation module specifically includes:
A node splitting unit for splitting the state in the network topology graph to be normal The nodes are respectively split into a set number of virtual nodes, and the available key quantity of each virtual node is calculated based on the key pool residual quantity of each virtual node, the average key generation rate of the virtual node and the adjacent nodes in the past time period T and the key relay task borne by the virtual node;
The key quantity judging unit is used for judging whether the available key quantity of a certain virtual node exceeds the applied key quantity of the key relay in a certain upcoming time period;
The node operation unit is used for reserving the virtual node when the output result of the key quantity judging module is yes, and deleting the virtual node when the output result of the key quantity judging module is no;
index subgraph generation unit for generating index subgraph in normal state If the virtual nodes are not deleted, each node is respectively deletedAnd all virtual nodes under the node are contracted into one node, and the index subgraph is obtained.
Further, the node splitting unit is specifically configured to perform the following steps:
Copying the network topological graph to obtain an index graph;
Deleting the index map in the fault state Node and will be in normal stateThe node is split into a set number of virtual nodes, and based on the key pool remaining quantity of each virtual node, the average key generation rate of the virtual node and the adjacent nodes in the past time period T and the key relay task borne by the virtual node, the available key quantity of each virtual node is calculated as follows:
in the method, in the process of the invention, Is the firstThe amount of keys available to the individual virtual nodes,Is the firstThe key pool remaining amount of the individual virtual nodes,Is the firstThe average key generation rate of each virtual node and the neighboring node over the past period T,Is the firstThe key relay task that the individual virtual nodes are assuming,，The number of relay tasks that are undertaken for the virtual node.
Further, the best route calculation module is specifically configured to perform the following steps:
Adding a departure node in the index subgraph into an open list;
Adding the reachable adjacent node of the starting node into an open list, setting the starting node as a parent node of the reachable adjacent node, and calculating the cost of the reachable adjacent node from the starting node as the cost of the parent node from the starting node plus 1;
Removing the departure node from the open list and adding the departure node to the close list;
traversing each node in the open list as a current node, calculating the priority of each node in the open list according to the cost of the current node from the departure node and the cost of the current node from the target node, and removing the node with the highest priority from the open list and adding the node into the close list;
Retrieving adjacent nodes of the nodes added into the close list, if the adjacent nodes are skipped in the close list, otherwise, calculating the cost of the adjacent nodes from the departure node;
Repeating the step of calculating the priority of each node in the open list until the target node is added into the open list;
and gradually tracking the father node from the target node until reaching the departure node, and obtaining the optimal routing path.
Further, the calculation formula of the cost of the current node from the target node is as follows:
in the method, in the process of the invention, For the current nodeThe cost of the distance from the target node,For the current nodeIs a function of the longitude of (1),For the current nodeIs a function of the latitude of (1),Is the longitude of the target node,As the latitude of the target node,For the number of kilometers,Representing an upward rounding.
Further, the priority calculation formula of each node is:
in the method, in the process of the invention, Representing nodesIs a comprehensive priority of (1); Is a node Cost from the departure node; Is a node An estimated cost from the target node.
It should be noted that, other embodiments of the quantum key relay routing computing system or the implementation method thereof may refer to the above method embodiments, and are not repeated herein.
Furthermore, a third embodiment of the present invention also proposes a computer-readable storage medium, on which a computer program is stored, which when executed by a processor implements the quantum key relay route calculation method according to the first embodiment.
It should be noted that the logic and/or steps represented in the flowcharts or otherwise described herein, for example, may be considered as a ordered listing of executable instructions for implementing logical functions, and may be embodied in any computer-readable medium for use by or in connection with an instruction execution system, apparatus, or device, such as a computer-based system, processor-containing system, or other system that can fetch the instructions from the instruction execution system, apparatus, or device and execute the instructions. For the purposes of this description, a "computer-readable medium" can be any means that can contain, store, communicate, propagate, or transport the program for use by or in connection with the instruction execution system, apparatus, or device. More specific examples (a non-exhaustive list) of the computer-readable medium would include the following: an electrical connection (electronic device) having one or more wires, a portable computer diskette (magnetic device), a Random Access Memory (RAM), a read-only memory (ROM), an erasable programmable read-only memory (EPROM or flash memory), an optical fiber device, and a portable compact disc read-only memory (CDROM). In addition, the computer readable medium may even be paper or other suitable medium on which the program is printed, as the program may be electronically captured, via, for instance, optical scanning of the paper or other medium, then compiled, interpreted or otherwise processed in a suitable manner, if necessary, and then stored in a computer memory.
It is to be understood that portions of the present invention may be implemented in hardware, software, firmware, or a combination thereof. In the above-described embodiments, the various steps or methods may be implemented in software or firmware stored in a memory and executed by a suitable instruction execution system. For example, if implemented in hardware, as in another embodiment, may be implemented using any one or combination of the following techniques, as is well known in the art: discrete logic circuits having logic gates for implementing logic functions on data signals, application specific integrated circuits having suitable combinational logic gates, programmable Gate Arrays (PGAs), field Programmable Gate Arrays (FPGAs), and the like.
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, structure, material, 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 do not necessarily refer to the same embodiments or examples. Furthermore, the particular features, structures, materials, or characteristics described may be combined in any suitable manner in any one or more embodiments or examples.
Furthermore, the terms "first," "second," and the like, are used for descriptive purposes only and are not to be construed as indicating or implying a relative importance or implicitly indicating the number of technical features indicated. Thus, a feature defining "a first" or "a second" may explicitly or implicitly include at least one such feature. In the description of the present invention, the meaning of "plurality" means at least two, for example, two, three, etc., unless specifically defined otherwise.
While embodiments of the present invention have been shown and described above, it will be understood that the above embodiments are illustrative and not to be construed as limiting the invention, and that variations, modifications, alternatives and variations may be made to the above embodiments by one of ordinary skill in the art within the scope of the invention.
Claims (11)
Priority Applications (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202410985643.XA CN118523913B (en) | 2024-07-23 | 2024-07-23 | Quantum key relay route calculation method and system |
| PCT/CN2024/117308 WO2026020559A1 (en) | 2024-07-23 | 2024-09-06 | Quantum key relay routing calculation method and system |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202410985643.XA CN118523913B (en) | 2024-07-23 | 2024-07-23 | Quantum key relay route calculation method and system |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN118523913A CN118523913A (en) | 2024-08-20 |
| CN118523913B true CN118523913B (en) | 2024-10-01 |
Family
ID=92281379
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202410985643.XA Active CN118523913B (en) | 2024-07-23 | 2024-07-23 | Quantum key relay route calculation method and system |
Country Status (2)
| Country | Link |
|---|---|
| CN (1) | CN118523913B (en) |
| WO (1) | WO2026020559A1 (en) |
Families Citing this family (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN120128524B (en) * | 2025-04-01 | 2025-11-04 | 广州市英球通信设备有限公司 | Multi-node secure communication method and system based on quantum key distribution |
Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN110808837A (en) * | 2019-11-21 | 2020-02-18 | 国网福建省电力有限公司 | A method and system for quantum key distribution based on tree QKD network |
| CN117176345A (en) * | 2023-10-31 | 2023-12-05 | 中电信量子科技有限公司 | Quantum cryptography network key relay dynamic routing method, device and system |
Family Cites Families (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7706535B1 (en) * | 2003-03-21 | 2010-04-27 | Bbn Technologies Corp. | Systems and methods for implementing routing protocols and algorithms for quantum cryptographic key transport |
| CN104579964B (en) * | 2013-01-07 | 2017-10-13 | 山东量子科学技术研究院有限公司 | A kind of quantum cryptography networks dynamic routing architecture system |
| CN105827397B (en) * | 2015-01-08 | 2019-10-18 | 阿里巴巴集团控股有限公司 | Quantum key distribution system, method and device based on trusted relay |
| CN109995515B (en) * | 2017-12-29 | 2020-08-11 | 成都零光量子科技有限公司 | Quantum key relay method |
-
2024
- 2024-07-23 CN CN202410985643.XA patent/CN118523913B/en active Active
- 2024-09-06 WO PCT/CN2024/117308 patent/WO2026020559A1/en active Pending
Patent Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN110808837A (en) * | 2019-11-21 | 2020-02-18 | 国网福建省电力有限公司 | A method and system for quantum key distribution based on tree QKD network |
| CN117176345A (en) * | 2023-10-31 | 2023-12-05 | 中电信量子科技有限公司 | Quantum cryptography network key relay dynamic routing method, device and system |
Also Published As
| Publication number | Publication date |
|---|---|
| CN118523913A (en) | 2024-08-20 |
| WO2026020559A1 (en) | 2026-01-29 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN112346854B (en) | In-network resource scheduling method and system for hierarchical collaborative decision and storage medium | |
| US8447849B2 (en) | Negotiated parent joining in directed acyclic graphs (DAGS) | |
| US20130010648A1 (en) | Apparatus, system and method for reliable, fast and scalable multicast message delivery in service overlay networks | |
| US20120182865A1 (en) | Systems, Methods, and Apparatuses for Managing the Flow of Traffic in Data Networks | |
| JP4421978B2 (en) | Delay guarantee path setting system | |
| JP2003249958A (en) | Peer-to-peer based network performance measurement and analysis system and method for large scale network | |
| US20090228604A1 (en) | Apparatus and method for calculating communication paths | |
| CA2531453A1 (en) | Bandwidth management for mpls fast rerouting | |
| CN111130853B (en) | Future route prediction method of software defined vehicle network based on time information | |
| EP2063586A1 (en) | Method for routing and load balancing in communication networks | |
| CN118523913B (en) | Quantum key relay route calculation method and system | |
| CN109167637B (en) | Key pool filling resource determination method, apparatus, device and readable storage medium | |
| CN116132292B (en) | Network slice deployment method based on resource scheduling and adaptation joint optimization | |
| Kwon et al. | Path-aware overlay multicast | |
| Mokhtarian et al. | Minimum-delay multicast algorithms for mesh overlays | |
| CN120469982B (en) | Collaborative data migration scheduling method based on topology awareness and deep reinforcement learning | |
| Llewellyn et al. | Distributed fault-tolerant quality of wireless networks | |
| CN115914891B (en) | Data center elastic optical network distance adaptive traffic distribution method and system | |
| JP3755527B2 (en) | Multicast transfer route calculation method, multicast transfer route calculation device, and program | |
| CN114980185B (en) | A routing selection method for vehicular self-organizing networks based on topology evolution | |
| Fekair et al. | An efficient fuzzy logic-based and bio-inspired QoS-compliant routing scheme for VANET | |
| JP4128944B2 (en) | Multicast transfer route setting method, multicast transfer route calculation device, program, and recording medium | |
| CN118802687A (en) | Transmission path determination method, device and electronic device | |
| Alabbad et al. | Localised credit based QoS routing | |
| JP3925423B2 (en) | Optimal detour route control system and method, program and recording medium thereof, and communication apparatus |
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 |