Route Planning and Online Routing for Quantum Key Distribution Networks

• URL: http://arxiv.org/abs/2508.09735v1
• Date: Wed, 13 Aug 2025 12:00:55 GMT
• Title: Route Planning and Online Routing for Quantum Key Distribution Networks
• Authors: Jorge López, Charalampos Chatzinakis, Marc Cartigny,
• Abstract summary: Quantum Key Distribution (QKD) networks harness the principles of quantum physics in order to securely transmit cryptographic key material.<n>We show that traditional shortest paths algorithms for routing perform poorly on both route planning and online routing.<n>We prove that the widest shortest path routing strategy has a competitive ratio greater or equal than $frac12$.
• Score: 1.7287035469433212
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Quantum Key Distribution (QKD) networks harness the principles of quantum physics in order to securely transmit cryptographic key material, providing physical guarantees. These networks require traditional management and operational components, such as routing information through the network elements. However, due to the limitations on capacity and the particularities of information handling in these networks, traditional shortest paths algorithms for routing perform poorly on both route planning and online routing, which is counterintuitive. Moreover, due to the scarce resources in such networks, often the expressed demand cannot be met by any assignment of routes. To address both the route planning problem and the need for fair automated suggestions in infeasible cases, we propose to model this problem as a Quadratic Programming (QP) problem. For the online routing problem, we showcase that the shortest (available) paths routing strategy performs poorly in the online setting. Furthermore, we prove that the widest shortest path routing strategy has a competitive ratio greater or equal than $\frac{1}{2}$, efficiently addressing both routing modes in QKD networks.

Related papers

• Blockchain-Enabled Routing for Zero-Trust Low-Altitude Intelligent Networks [77.17664010626726]
  We focus on the routing with multiple UAV clusters in low-altitude intelligent networks (LAINs)<n>To minimize the damage caused by potential threats, we present the zero-trust architecture with the software-defined perimeter and blockchain techniques.<n>We show that the proposed framework reduces the average E2E delay by 59% and improves the TSR by 29% on average compared to benchmarks.
  arXiv  Detail & Related papers  (2026-02-27T04:30:35Z)
• Can Neural Networks Provide Latent Embeddings for Telemetry-Aware Greedy Routing? [22.04675077514561]
  We propose emphPlacer, a novel algorithm using Message Passing Networks to transform network states into latent node embeddings.<n>These embeddings facilitate quick greedy next-hop routing without directly solving the all-pairs shortest paths problem.
  arXiv  Detail & Related papers  (2026-02-13T10:31:09Z)
• Distributed Link Sparsification for Scalable Scheduling Using Graph Neural Networks (Journal Version) [50.894272363373126]
  In wireless networks characterized by dense connectivity, the significant signaling overhead generated by distributed link scheduling algorithms can exacerbate issues like congestion, energy consumption, and radio footprint expansion.<n>We propose a distributed link sparsification scheme employing graph neural networks (GNNs) to reduce scheduling overhead for delay-tolerant traffic while maintaining network capacity.<n>A GNN module is trained to adjust contention thresholds for individual links based on traffic statistics and network topology, enabling links to withdraw from scheduling contention when they are unlikely to succeed.
  arXiv  Detail & Related papers  (2025-09-05T18:59:14Z)
• Opportunistic Routing in Wireless Communications via Learnable State-Augmented Policies [7.512221808783587]
  This paper addresses the challenge of packet-based information routing in large-scale wireless communication networks.<n>Opportunistic routing exploits the broadcast nature of wireless communication to dynamically select optimal forwarding nodes.<n>We propose a State-Augmentation (SA) based distributed optimization approach aimed at maximizing the total information handled by the source nodes in the network.
  arXiv  Detail & Related papers  (2025-03-05T18:44:56Z)
• Entanglement Routing in Quantum Networks: A Comprehensive Survey [2.624902795082451]
  Entanglement routing in near-term quantum networks consists of choosing the optimal sequence of short-range entanglements to combine. We classify and discuss the studied quantum routing schemes into reactive, proactive, opportunistic, and virtual routing.
  arXiv  Detail & Related papers  (2024-08-02T12:48:40Z)
• Differentiated Service Entanglement Routing for Quantum Networks [4.522468619087071]
  We propose a differentiated service entanglement routing (DSER) scheme, which firstly finds out the lowest loss paths and supported wavelength channels with the tensor-based path searching algorithm, and then allocates the paired channels with the differentiated routing strategies. The evaluation results show that the proposed DSER scheme can be performed for constructing various large scale quantum networks.
  arXiv  Detail & Related papers  (2024-01-30T23:37:16Z)
• Comparando Estrat\'egias de Roteamento em Redes Qu\^anticas Oportun\'isticas [0.0]
  This paper presents a comparative analysis of three routing strategies in opportunistic quantum networks. routing strategies are compared based on the fidelity of the chosen routes, the number of entangled pairs created, and the number of route recalculations.
  arXiv  Detail & Related papers  (2023-11-03T01:52:26Z)
• Fidelity-Guarantee Entanglement Routing in Quantum Networks [64.49733801962198]
  Entanglement routing establishes remote entanglement connection between two arbitrary nodes. We propose purification-enabled entanglement routing designs to provide fidelity guarantee for multiple Source-Destination (SD) pairs in quantum networks.
  arXiv  Detail & Related papers  (2021-11-15T14:07:22Z)
• Deep Reinforcement Learning Aided Packet-Routing For Aeronautical Ad-Hoc Networks Formed by Passenger Planes [99.54065757867554]
  We invoke deep reinforcement learning for routing in AANETs aiming at minimizing the end-to-end (E2E) delay. A deep Q-network (DQN) is conceived for capturing the relationship between the optimal routing decision and the local geographic information observed by the forwarding node. We further exploit the knowledge concerning the system's dynamics by using a deep value network (DVN) conceived with a feedback mechanism.
  arXiv  Detail & Related papers  (2021-10-28T14:18:56Z)
• Road Network Guided Fine-Grained Urban Traffic Flow Inference [108.64631590347352]
  Accurate inference of fine-grained traffic flow from coarse-grained one is an emerging yet crucial problem. We propose a novel Road-Aware Traffic Flow Magnifier (RATFM) that exploits the prior knowledge of road networks. Our method can generate high-quality fine-grained traffic flow maps.
  arXiv  Detail & Related papers  (2021-09-29T07:51:49Z)
• Packet Routing with Graph Attention Multi-agent Reinforcement Learning [4.78921052969006]
  We develop a model-free and data-driven routing strategy by leveraging reinforcement learning (RL) Considering the graph nature of the network topology, we design a multi-agent RL framework in combination with Graph Neural Network (GNN)
  arXiv  Detail & Related papers  (2021-07-28T06:20:34Z)
• Purification and Entanglement Routing on Quantum Networks [55.41644538483948]
  A quantum network equipped with imperfect channel fidelities and limited memory storage time can distribute entanglement between users. We introduce effectives enabling fast path-finding algorithms for maximizing entanglement shared between two nodes on a quantum network.
  arXiv  Detail & Related papers  (2020-11-23T19:00:01Z)
• Attention Routing: track-assignment detailed routing using attention-based reinforcement learning [0.23453441553817037]
  We propose a new router: attention router, which is the first attempt to solve the track-assignment detailed routing problem using reinforcement learning. The attention router and its baseline genetic router are applied to solve different commercial advanced technologies analog circuits problem sets.
  arXiv  Detail & Related papers  (2020-04-20T17:50:13Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.