Open Access
Add to BibSonomyAbstract
Quantum key distribution (QKD) appears as a promising technique for encrypted communication, preserving security even in the presence of a future powerful quantum computer. At the same time, communication infrastructure becomes increasingly complex, and the exponentially increasing traffic volume makes the application of QKD a challenging task. In addition, current hardware for QKD modules is still subject to research to gain maturity, to guarantee secret key rates, and to mitigate key rate fluctuations and instabilities. Our study analyzes and optimizes five routing algorithms to efficiently use the secret keys as a resource in meshed national-wide networks. By fulfilling distinct security and performance levels, the algorithms are compared with respect to key performance indicators and optimized for blocking probabilities, load balancing, or the management traffic amount. Depending on the application, our study allows operators to choose a well-suited algorithm and gives performance estimates, including an assessment of the performance gap to globally optimized algorithms.
© 2024 Optica Publishing Group under the terms of the Optica Open Access Publishing Agreement
1. INTRODUCTION
Cryptography is undergoing a fundamental transformation due to increasing computing capacities and significant progress in the realization of quantum computers. These advancements necessitate a thorough review of cryptographic standards. Algorithms previously assumed to be safe, e.g., the Rivest–Shamir–Adleman (RSA) algorithm, may become breakable in a fraction of the computing time using a quantum computer. The RSA encryption standard is based on factoring large prime numbers. Shor proved that a quantum computer can break such asymmetric encryption in a fraction of the time compared to a classical CPU-based computer [1,2]. According to [3], RSA may become insecure even with long keys of 4096 bits in approximately 30 years. Information encrypted by current standards could be stored and decrypted at a later point in time using a quantum computer. Especially critical infrastructure like governmental communication needs to be secured for a long time and thus requires quantum secure encryption.
An emerging approach is pursued by quantum key distribution (QKD) as a promising method to allow information-theoretical security. It is based on fundamental laws of quantum physics, such as the Heisenberg uncertainty principle of quantum mechanics, and does not rely on computational complexity. Therefore, it is secure against quantum attacks independent of new attacking methods or increasing computing capacity [4].
QKD systems are already commercially available from different vendors, but the deployment of large meshed QKD networks for securing data transmission for, e.g., authorities, is still in the planning stage. Since the realization of such a network is very cost-intensive, it must be carefully planned. The generation of secret keys is time consuming, and the secret key rate is limited and subject to fluctuations over time. Hence, the distribution of keys is a dynamic process that will strongly influence the performance of the network. Therefore, the metrics at the network controller for the routing process have to be chosen carefully.
This paper investigates long-reach, meshed QKD networks, which are equipped with trusted nodes [5] to bridge link distances longer than 80 km, while keeping the secret key rate at a sufficient level.
Our contributions are as follows:
- • Within this study, we developed and implemented different routing schemes based on state-of-the-art routing algorithms and optimized those for application in QKD networks.
- • The study compares the performance, trades off different security implications, and estimates the overhead for the control- and management-planes.
For this purpose, we assume a central network controller. An essential and primary requirement for this controller is continuously maintaining sufficiently filled key stores at all network nodes.
The paper is structured as follows. In Section 2 we briefly explain the theoretical background of QKD and describe the realization of a meshed long-haul QKD network. Section 3 introduces the network architecture and explains the simulation setup. Section 4 is about routing without sharing sensitive information with the network controller. For this purpose, three different routing approaches are introduced. In the following section, we extend the routing approaches with two algorithms where the network controller has full knowledge about all important network parameters. In Section 6 we compare the different routing algorithms with respect to blocking probability, key store utilization, and network management traffic. Finally, we conclude the paper in Section 7.
2. THEORETICAL BACKGROUND
This section explains the basic principles of QKD and the generation of secret keys to motivate our approaches in routing optimization. The description serves as a basis for our simulation framework to estimate secret key rates realistically. Additionally, we explain how a possible meshed long-haul QKD network can be realized. At the end of the section, we give a short overview of the state-of-the-art in QKD routing.
A. Basic Principles of QKD
A QKD module is responsible for generating the secret keys, which are used to encrypt the data transmission. For key generation two neighboring QKD modules are needed which communicate via two different channels. The classical channel is used for transmitting conventional information signals. The quantum channel carries out the transmission of quantum signals and therefore the generation of the secret keys. In standard key distribution schemes, information is sent over the classical channel, where an eavesdropper can gain meaningful information on the data without being noticed. This process is unattainable within the framework of QKD. Quantum bits (qubits), such as polarized single photons, cannot be simply copied, a principle substantiated by the no-cloning theorem, which establishes the impossibility of duplicating a quantum state without inducing alterations to its original configuration [6]. Furthermore, Heisenberg’s uncertainty principle states that the properties of a quantum particle cannot be precisely measured without simultaneously disturbing its fundamental state [4]. This principle underlines the security of QKD, because an eavesdropper cannot measure or copy transmitted qubits and therefore is not able to gain information about the secret key without revealing its presence.
To enable secure transmission, the data is symmetrically encrypted using the secret keys exchanged by QKD. Most often the advanced encryption scheme (AES) utilizing a length of at least 256 bits is used, which is assumed to be secure also toward future powerful quantum computers, as discussed in [7]. Consequently, the sequence of secret bits generated by a QKD device is divided into discrete blocks of 256 bits, which we subsequently denote as “secret keys.”
B. Generation of Secret Keys
To simulate realistic link length-dependent key rates, we used a model derived from deployed QKD modules. Within this model, the basic protocol adopted is the BB84 protocol, conceptualized by Bennett and Brassard [8].
In the following we derive the block length of secret bits ${N_{\rm{sec}}}$. The values and descriptions of the parameters for the key generation are summarized in Table 1 (based on [9,10]). The quantum bit error rate (QBER) is the ratio between key rate and the error rate and provides information about the potential presence of an eavesdropper. The following equations are derived from [11], and the QBER is calculated as follows:
Table 1. Parameters for Calculating the Secret Key Block Length after a Certain Time Interval
With the binary Shannon entropy of the QBER, i.e., $h({\rm QBER})$, it is possible to calculate the compression factor ${f_{\rm{PA}}}$. The post-processing input block size is the number of bits which have been exchanged between two QKD modules, but before processes like error correction and privacy amplification. Under consideration of ${f_{\rm{PA}}}$ and assuming ${N_{\rm{pp}}} = \;{10^6}$, the block length of secret keys in a certain time interval results in
Figure 1 shows the resulting secret key rate as a function of the fiber length of a QKD link. It shows an exponential decrease, because of attenuation and diverse fiber-induced effects. Therefore, the length of individual links is strongly limited and requires either the deployment of quantum repeaters [12] or trusted nodes for bridging longer distances. The model above is used to calculate the link length-dependent key rates for refilling the key stores in our simulations.
Fig. 1. Exponential decrease of the secret key rate in relation to the fiber length according to the presented model.
C. Application of QKD to Meshed Networks
Due to the limited range in key exchange, as previously shown, intermediate amplification would be necessary. As traditional amplification methods cannot be employed for amplifying qubits, because they would alter their state and result in information loss, an alternative is needed.
Consequently, a promising strategy involves the introduction of “Trusted Nodes” (TRs) after certain distances, such as around 80 km as fully transparent quantum repeaters are not available yet. These TRs serve as intermediate security checkpoints, allowing QKD-secured communication over extended spans.
To secure communication across multiple hops, the adoption of key relays becomes necessary, aligning with the recommendations outlined in ITU-T Y.3803 [13]. One of the recommended approaches involves leveraging the one time pad (OTP) method, which provides information-theoretic security. This process entails bitwise XOR ($\oplus$) operations between keys of neighboring edges on the path, effectively encrypting their respective keys. The resulting composite key is then forwarded to a centralized node. Hence, the centralized node receives the encrypted keys of all intermediate nodes and calculates a bitwise XOR operation to the encrypted keys. The result is sent to the destination node, which decrypts the final end-to-end key. The approach enables end-to-end keys even in scenarios that involve TRs. The bitwise XOR operation needs the same key length between neighboring nodes. Hence, the lowest key rate between neighboring nodes bounds the key rate of the end-to-end key. A graphical representation illustrating this concept is depicted in Fig. 2. As the technology evolves, future development might replace TRs with quantum repeaters, resulting in enhanced efficiency, security, and scalability to QKD networks.
Fig. 2. Process of key relaying using trusted nodes [10]. The operator $\oplus$ represents the bitwise XOR operation.
D. State-of-the-Art in QKD Routing
Research projects recently investigated QKD and its application for securing wired connections. Mehic et al. summarize an analysis of routing strategies in conjunction with the deployments of prototypes [14,15]. Due to similarities of routing in QKD networks and classical networks, initial attempts apply traditional routing algorithms, e.g., open shortest path first (OSPF), to QKD networks and tune them according to QKD-specific properties [15]. However, the analysis of prototypes is often limited to a reduced number of nodes and does not study meshed networks with node degrees larger than four. In [16], the authors developed a decentralized routing scheme and applied it to meshed networks. However, the analysis focuses on the homogenous distribution of end-to-end keys given point-to-point keys between neighboring nodes. There is no simulation framework considering the utilization of keys and the evolvement of the network over time. Furthermore, recent proof-of-concept investigations to utilize software-defined networking (SDN) within the management of QKD networks enable more complex routing schemes and the optimized operation of deployed QKD networks [17]. The SDN controller fulfills the functionalities of monitoring and/or operating the network. However, the analysis of a meshed network and optimized routing algorithms is missing and also SDN integration may imply further security issues. Besides the progress of QKD networks, the advancements of optical transport network (OTN) technologies enable dynamic adaptation according to the current network state [18]. These developments potentially allow a dynamic routing scheme for optimized utilization of QKD networks with unknown key demands.
3. ARCHITECTURE AND SIMULATION SETUP
In this section we first introduce the architecture, which we assume in our simulation setup to realize a meshed QKD network. After that a short introduction of the security requirements on the network controller follows. We conclude this section with the description of our simulation setup.
A. Architecture
The availability of keys at all links is a key factor for satisfying communication demands and routing at intermediate nodes. We consider a centralized SDN or QKD controller responsible for routing and resource allocation that responds to communication demands. Hence, the central controller possesses comprehensive information, at a minimum, regarding the network’s topology. Based on the information, the network controller performs the routing. The architectural configuration is illustrated in Fig. 3. Within the quantum layer, the quantum key distribution and communication between neighboring QKD modules takes place. In the quantum layer, only neighboring nodes share secret keys. The key management layer is responsible for the end-to-end keys and performs the key relay. We assume quantum key pools (QKPs), a concept introduced in [19], for buffering the keys. These QKPs serve as virtual substores, storing secret keys corresponding to each pair of interconnected nodes within the network. When initiating communication, the user forwards a request to the controller, which subsequently executes the path computation. This computation hinges on the controller’s exhaustive insight into the network’s connectivity, i.e., full knowledge of the network topology. The controller forwards the result of the path computation to the nodes included in the path of the key management layer. By utilizing the QKPs and key relays, the end-to-end key is provided to the communication request.
Fig. 3. Sketch of the assumed architecture based on [15] including the different QKD modules, key managers (KMs) and quantum key pools (QKPs).
Furthermore, we assume that QKD and dense wavelength division multiplexing (DWDM) channels do not influence each other because of the availability of an additional fiber for every QKD link.
B. Security Requirements on the Network Controller
A controller with complete knowledge of the health parameters, e.g., filling level of QKPs or secret key rates, can process encryption requests in a sustainable manner. Either the controller performs a demand-wise routing depending on the filling levels of the key stores and the key generation rate, or it collects demands and places them based on an integer linear programming (ILP) algorithm.
The more information the controller has about the network, the better it can route demands. However, this also provides a target for potential attacks. According to [20] management traffic is also an attack point and hence has to be secured properly. Information about, e.g., the filling level of the key stores can be corrupted and negatively affect the routing process.
It could be a possible way to minimize the management traffic, or the attack area. Machine learning (ML) is promising for predicting future demands to optimize the weights of a routing algorithm without explicit knowledge about the health parameters of the network.
C. Simulation Setup
The simulation is Python-based, and we adapt the “NOBEL-Germany” topology [21] and implemented it using the “NetworkX” library [22]. The topology comprises 17 nodes. For the realization of a meshed QKD network we added 41 additional (trusted) nodes to links which are longer than 80 km as otherwise the secret key rate would be too low (compare Fig. 1). All of the nodes are assumed to be trusted nodes, but only the 17 original nodes function as access nodes and can act as source or destination nodes for adding or dropping traffic. The topology is depicted in Fig. 4. Additionally, we added some edges to the network (e.g., between Frankfurt and Stuttgart) to avoid a too-rapid congestion of certain spans by providing more alternative paths.
Fig. 4. Schematic representation of the simulated network topology. Access nodes are represented in pink and trusted nodes are colored green.
The communication demands for the simulation stem from the “SNDlib” [21], a resource which provides dynamic traffic for the “NOBEL-Germany” topology. This dataset contains 288 demand matrices, collectively comprising 73,512 demands. These traffic patterns have been measured over 24 h and are segmented into discrete 5-min intervals. Each matrix contains various information per demand including the source and destination nodes and the amount of data. At the beginning of each simulation we assume an initial state of 10,000 keys, each with a length of 256 bits, stored within each QKP. This means that before the network operation starts, there is an initialization phase where keys are generated. During the simulation the key stores are refilled with new keys according to the model provided in Subsection 2.B [23]. We assume an interval of 60 s and believe that this is a realistic key provisioning interval, that is accounting for time-intensive stages in key generation processes, such as qubit transmission, reconfiguration periods, feedback loops, and error correction mechanisms. We assume that each secret key possesses the capability of securely encrypting a maximum data volume of 0.3887 terabytes, as elaborated in [24].
The number of secret keys which are generated between two neighboring nodes is calculated according to the model provided in Section 2. To harmonize the key generation with the demand matrices, we subdivided each demand matrix into five submatrices of equal size, each containing 60 s of dynamic data traffic.
In addition, as some demands have very low values, we scaled them using a linear factor of 100 to increase their influence on the network.
The path calculation depends on the choice of the routing algorithm, presented in the next sections. However, the general process of a simulation remains the same, so this is explained briefly below. Except for the ILP algorithm, all demands are processed sequentially.
The routing algorithm extracts source, destination, and the data amount from the matrix. The data is scaled with a traffic factor to investigate the influence of an increase in traffic volume. This information is used to calculate a path using the corresponding routing algorithm. For the calculated paths it is checked by the controller, if all QKPs along the paths have a sufficient number of secret keys to encrypt the demand (remember: a 256-bit secret key is able to encrypt 0.3887 terabyte of data). If enough keys are available at every QKP, the corresponding number of keys is consumed from the QKPs, else the routing demands is rejected. After processing all demands from the matrix, new keys are generated and distributed to the QKPs.
To account for potential very high individual demands included in the dataset, we established an upper limit on the number of keys that can be requested, arbitrarily set at 1000 keys per individual demand. This proactive measure circumvents a scenario wherein a single demand could exhaust all keys within a particular QKP, thereby ensuring the robustness of the simulation dynamics. Additionally, the demands contained in each matrix are randomly shuffled to prevent the order from influencing the routing algorithms. A conceptual visualization of the simulation process is depicted in Fig. 5.
4. ROUTING OPTIMIZATION WITHOUT SHARING SENSITIVE DATA
As a general network planning study, we use different routing approaches in our simulation framework. In this section, we assume that the network controller has no information about parameters like the key store filling levels of the QKPs or the key generation rate between the various nodes. The knowledge is limited to network connectivity (i.e., the graph). We create a baseline with a hop-based routing algorithm and compare it with two algorithms that use prediction of future data traffic to optimize the routing.
A. Baseline Optimizing Hop Count
As a simple baseline, based on full knowledge of the topology, we implemented a hop-based routing algorithm. Within this context, the hop-based $k$-shortest path routing algorithm emerges as a valuable tool employed in communication networks to identify multiple viable paths between a source and a designated destination node. This method calculates $k$ (a parameter defined by the user) shortest paths, with the primary metric for path selection being the number of hops (or nodes) traversed. Consequently, the algorithm initializes all edges with a uniform weight of “1.” Upon its completion, the algorithm produces a roster of $k$-shortest, loopless paths, arranged in ascending order based on the number of hops, ranging from the fewest to the most.
During our simulations, also in the following sections, the value of $k$ remains consistently set to 5. Subsequently, the controller undertakes an iterative assessment of the calculated paths, ensuring the presence of sufficient keys along these paths. If all $k$ paths do not have the key capacity required for encryption, the demand is classified as infeasible and subsequently marked as a blocked demand. Paths with adequate key resources undergo key consumption from the QKPs distributed along the route. This comprehensive key utilization procedure is executed for all demands within the dataset.
B. (Hypothetical) Perfect Prediction of Traffic Demands
Serving as a benchmark for subsequent prediction-based routing optimization, we establish a hypothetical scenario of perfect demand matrix prediction. This involves utilizing the demand matrix from the upcoming time step as input for an optimization algorithm. Leveraging this speculative prediction, the controller executes a simulation-based routing of the anticipated demands. Before processing the first demand, we initialize all network edges with a uniform weight of “1” (similar to the optimization of the hop count).
In the following steps, the controller computes the $k$-shortest paths and tries to find a viable path. Should a QKP exhibit insufficient available keys, a penalty of 0.5 is added to the respective edge weight. This iterative process is applied across all predicted demands. It is worth mentioning that during this optimization procedure, key consumption is carried out exclusively within a simulated replica of the network, independent of an impact on the actual QKPs. This strategy changes the attractiveness of heavily utilized edges for a weight-based $k$-shortest-path algorithm. As a result, these intensively utilized edges experience reduced use. Consequently, the heavily used key stores are granted additional time for regeneration, thereby facilitating the transport of a higher number of demands overall and reducing the likelihood of rejections.
After the weights are optimized for the predicted matrix, the actual routing of the real demand matrix takes place using a weight-based $k$-shortest path algorithm.
The presented optimization mechanism, based on the concept of perfect prediction enhances the routing efficiency within the system. By strategically adapting edge weights based on the predicted demand, the approach fosters a more balanced and optimized allocation of resources, thus improving the overall throughput in the network.
C. LSTM-Based Optimization
In addition to the perfect prediction, we implement and show a long short-term memory-based (LSTM) prediction algorithm for optimized routing. The LSTM is used with multiple parallel inputs and a single-step output. That means that we only predict the next step. The first 50 demand matrices are used for training the LSTM. During training time, we use the baseline from $A$ for routing.
In the training phase, the data streams between each pair of access nodes are extracted from the matrices and fed into the LSTM as a vector. As access to dynamic data traffic is limited, we use a small LSTM with 10 units in each of the two layers. The training takes place over 400 epochs at a learning rate of 0.001. The “rectified linear unit” is used as an activation function and the “Adam” algorithm as optimizer. For predicting the next step, the demand matrices of the last three time steps are used. After the training phase, the weight optimization is performed analogously to the algorithm of the hypothetical perfect prediction.
Figure 6 shows the prediction of the LSTM for an exemplary demand matrix. In the context of the logarithmic plot, it becomes evident that accurate prediction of lower magnitude values shows a greater deviation from the true values. We found out that the influence of these small traffic factors, however, is rather low, as small amounts of data also need fewer secret keys for encryption. With an increase in the traffic factor, however, also the influence of small traffic values increases as the deviation is scaled with a linear factor. The optimization algorithm is therefore applied to values that increasingly deviate from the actual values. This can lead to a deterioration in the path selection.
Fig. 6. Visualization of the deviations between real values and values predicted by the LSTM algorithm for an exemplary demand matrix.
5. ROUTING OPTIMIZATION USING A CONTROLLER WITH A GLOBAL NETWORK VIEW
We additionally extend the simulation with two more routing algorithms. These routing schemes require knowledge of the number of keys available in all QKPs. Therefore, we assume that the controller has detailed information on this metric for all edges of the network. This leads to a trade-off between better routing results and increasing security risks, as more information about the complete network is shared with the controller.
A. Weight Optimization Approach
As mentioned, the first implementations of routing algorithms in QKD networks adapted OSPF [15]. The advantage of this method is that the total number of consumed keys in the network is minimal. However, it ignores traffic engineering capabilities. This conduct leads to high consumption rates of keys on some edges of the network culminating in empty QKPs around central nodes with high demands. To prevent the exhaustion of QKPs, the proposed approach involves adjusting the penalty, depending on the number of keys in its corresponding QKP.
Specifically, this means that edges with a reduced number of stored keys are assigned a higher weight and thus are artificially penalized. Then, like in OSPF, a Dijkstra algorithm is applied to find the shortest path considering those weighted edges. The objective is to equalize the consumption of keys across the network such that all QKPs remain filled evenly.
The performance of this routing approach depends on the way to compute the individual weights. The Dijkstra algorithm seeks the combination of edges that add up to the minimal total weight. This results in the path with the lowest cumulative weight of its edges. Depending on the equation for the calculation of the weight the performance varies. For better handiness, we describe the QKP filling degree by its contrary, termed as the emptiness $E$, representing the difference between maximum capacity and the current filling degree in percentage. Because of the Dijkstra’s cumulative approach, a substantial increase in the resulting edge weight becomes necessary during periods of heightened QKP emptiness. Hence, an exponential modulation of the resulting edge weight $W$ depending on the emptiness $E$ was selected:
We introduce the parameter $a$ to enable additional linear adaptations to enhance the overall performance of this approach. Extended simulations revealed an appropriate setting of $a = 1$ for the given topology and the simulation procedure.In this weight optimization approach, every demand is routed individually. Then, after computing an updated weight for each edge, the controller applies the Dijkstra algorithm and determines the currently best path.
B. Integer Linear Programming Approach
Besides the different heuristic-based algorithms, we also propose a routing scheme based on ILP. We utilize ILP to jointly optimize the demands’ routing that corresponds to 60 s of operation.
To develop the ILP, we specify the input first:
- • ${\cal N}$: Set of access nodes in the graph.
- • ${\cal L}$: Set of directed links in the graph. We consider an undirected graph between neighboring nodes $i$ and $j$ as a pair of directed links: $({i,j}) \in {\cal L}$ and $({j,i}) \in {\cal L}$.
- • ${\cal D}$: Set of end-to-end demands ${d_i}$ between source ${s_i}$ and destination ${t_i}$ with ${s_i} \in {\cal N}$, ${t_i} \in {\cal N}$ requesting a capacity ${c_i} \in \mathbb{N}$.
- • ${B^t}$: Vector of links at time point $t$ weighted with the buffer status in bits. We differentiate between $B_C^t$ and $B_{\textit{CF}}^t$, where $B_C^t$ represents the buffer status after consumption and before filling and $B_{\textit{CF}}^t$ represents the buffer status after consumption and filling at time point $t$.
- • ${R_{{d_i},k}}$: Routing vector per demand ${d_i}$, and path indicating whether a link is used or not.
- • $K$: Integer number of $k$-shortest paths, that can be used per demand.
The ILP algorithm chooses the following variable for optimizing the routing:
- • ${x_{{d_i},k}}$: Equals 1, if the route of the $k$-shortest path is chosen to serve the demand ${d_i}$; equals 0 otherwise.
The objectives are the following:
The objectives are subject to the following constraints:
The first objective shown in Eq. (5) expresses the maximization problem to place as many demands as possible. This is the primary objective. The secondary objective, i.e., Eq. (6), expresses the max-min-problem to maximize the least filled buffer. The ILP maximizes the secondary objective after maximizing the primary objective. Equation (7) represents the calculation of the buffer status at time point $t$ based on the previous buffer status, the $k$-shortest paths, and the variable ${{\boldsymbol x}_{{{\boldsymbol d}_{\boldsymbol i}},{\boldsymbol k}}}$, which is subject to optimization. Furthermore, Eq. (8) ensures that at most one path out of the $k$-shortest paths is chosen for every demand, and Eq. (9) ensures that the buffer status for every link is non-negative. For the sake of compatibility, we set $K = {5}$.
The ILP algorithm can jointly compute the optimized routing for all demands. Following the optimization at time point ${\boldsymbol t}$, we simulate the routing and key consumption. The buffer status after the consumption is subject to the buffer filling according to the model introduced in Section 2. After consumption and filling, we obtain ${\boldsymbol B}_{{\boldsymbol {CF}}}^{{\boldsymbol t} + 1}$ as the initial vector for the following time point ${\boldsymbol t} + 1$. We repeat the procedure every 60 s.
The ILP has the additional constraint, compared to the other algorithms, that it jointly considers the demands of one time-step. Therefore, it does not route demand-wise, like the other algorithms, but block-wise.
6. RESULTS AND COMPARISON
This section is split into three subsections to compare the different routing optimization techniques. The first subsection is about the increasing traffic in the network and its influence on the blocking probability. The second subsection deals with the ability of the different algorithms to distribute the traffic evenly over the network. The last subsection is about the management traffic that is necessary for routing.
A. Blocking Probabilities of Different Approaches
Ensuring a minimum number of blocking events is a principal objective in our investigation. A demand is blocked if an algorithm is unable to calculate a path on which each QKP has sufficient secret keys to encrypt the data. To probe the response of the algorithms to increasing encryption demands, we progressively multiplied the data rates to be encrypted by a traffic scaling factor to investigate the impact of an increase in traffic volume. Subsequently, we counted rejected demands and calculated the percentage of rejected demands in relation to the total number of demands. Illustrated in Fig. 7, this analysis encompasses traffic scaling factors ranging from 1 to 20,000 (with respect to the original demand matrix given in the SND library). Notably, the hop count algorithm exhibited lower performance compared to all other algorithms. For the hop count algorithm, the emergence of blocking incidents started at a traffic factor of 500, indicating that not sufficient keys were available on specific links. However, utilization can increase again once the filling level of the key store recovered.
Fig. 7. Blocking probability of the five routing algorithms in relation to the traffic scaling factor.
In contrast, the prediction-based algorithms, characterized by limited network insight, and the weight-centric algorithm, equipped with an extensive network perspective, managed to route with negligible occurrence of blocking events until the traffic factor approached approximately 2500. Surpassing these performances, only the ILP algorithm enabled unobstructed demand routing until the traffic factor reached 5000. Notably, the LSTM-based algorithm showed reduced efficacy for higher demand scaling conditions, attributable to amplified discrepancies between forecasted and actual values as mentioned before.
The initial performance of the (hypothetical) perfect prediction is closest to that of the ILP algorithm, which constitutes the upper performance bound in our simulations. Hereby, the good performance of the prediction-based algorithm is highlighted.
Upon surpassing certain demand scaling factors, convergence in blocking probabilities is apparent for the weight-centric and perfect prediction-based algorithms. It is important to emphasize that the blocking probability exclusively considers the absolute number of obstructed encryption requests with respect to the total number of requests.
In conclusion, the ILP algorithm shows the best performance in avoiding blockages due to the approach of collecting demands and placing them in the network. When we consider demand-wise routing, the perfect prediction performs best, which, however, is only based on a hypothetical assumption. Therefore, a comparison of the LSTM prediction and the weight optimization algorithm is more useful. The weight optimization algorithm performs better, but also requires full knowledge about the network parameters. It is therefore a trade-off between performance and necessary management traffic.
B. Key Store Utilization
Within this subsection, our examination centers on the observed impact of the different routing algorithms on the critical aspect of load balancing. For effective visualization, we chose to focus on the geographical region encompassing Frankfurt, a central node within the broader network architecture. As depicted in Fig. 8, we present an analysis of the filling levels of the QKP between Frankfurt and Cologne as a function of the demand numbers, particularly under a traffic factor of 5000 over time.
Fig. 8. Exemplary visualization of the key store filling levels between Frankfurt and Cologne (in percent) after each routed demand.
It is notable to observe that the hop count algorithm swiftly transitions from its initial state of occupancy (100% filling) to a state of overload, scarcely achieving a QKP occupancy exceeding 50% throughout the simulation duration. In contrast, the (hypothetical) perfect prediction algorithm demonstrates an improved QKD filling level, which helps to reduce blocking on this edge. The LSTM algorithm, which initially behaves similar to the hop-based algorithm, shows a strong change once the prediction-based optimization starts working (around 15,000 demands), resulting in effective edge offloading. For this specific edge, the weight optimization algorithm marginally outperforms the prediction-based algorithms.
Fig. 9. Mean percentage of the key store filling levels for the area around Frankfurt for all different routing methods.
Showing the best algorithmic performance, the ILP algorithm achieves maintaining the QKP occupancy consistently above the 50% threshold for a substantial portion of the simulation. The detailed dynamics of load balancing are further investigated in Fig. 9, wherein we show the mean key store filling levels (in percent) across all edges leaving Frankfurt. Here, the hop-based algorithm shows the worst performance, swinging between either near-full or near-empty store states throughout the simulation interval.
Conversely, the (hypothetical) perfect prediction, LSTM optimization, and the weighting algorithm collectively demonstrate more efficient load-balancing capabilities. Particularly notable is the significant disparity between the least filled buffers, wherein the mean key store levels of all other algorithms are approximately twice as large compared to those from the hop-based paradigm. The best performance in load balancing is achieved by the ILP algorithm, exhibiting superiority over all alternative methodologies.
C. Management Traffic
Finally, we analyze the management traffic dynamics in response to increasing traffic demand factors. Our examination focuses specifically on requests originating from the network controller to target individual QKPs. The visualization of the results is depicted in Fig. 10.
Fig. 10. Number of management requests for all routing algorithms in relation to the traffic factor.
The ILP algorithm emerges as the optimum algorithm in this context, showing only approximately 100,000 management requests. This efficiency can be attributed to the fact that the algorithm only needs to query all 73 QKPs once before processing a matrix. However, it is limited in the way that the ILP is unable to process demands as they occur.
In contrast, the weighting optimization approach necessitates repetitive queries of the QKPs to ascertain the real-time statuses of QKPs for every demand, thereby incurring inherent drawbacks.
Importantly, both prediction-based algorithms require a relatively high volume of management traffic compared to the hop-based algorithm. This increased query load is an inherent outcome of the iterative edge weight optimization process, wherein the controller routinely probes the QKPs to verify the availability of the required key quantities.
In conclusion, these observations underline the remarkable ability of the ILP algorithm in effectively orchestrating management traffic dynamics.
7. CONCLUSION
We have realized various implementations of routing algorithms for meshed long-haul QKD networks and conducted a comprehensive evaluation across various metrics. Notably, the ILP algorithm achieves the overall best performance in our study. However, it assumes a complete availability of the demand matrix of each time-step. Conversely, the other considered approaches are not restricted by this limitation.
For the weight optimization algorithm, a trade-off needs to be taken between the volume of management traffic and the quality of the routing decisions. The prediction-based algorithms have the advantage of significantly reduced management traffic, yet their operational efficacy relies on the precision of the prediction. In this context, the (hypothetical) perfect prediction serves as an upper-performance bound for the LSTM algorithm. Furthermore, it is noteworthy that with access to extended temporal records of dynamic traffic, the LSTM algorithm could potentially achieve performance closer to the (hypothetical) perfect prediction.
An added advantage inherent to prediction-based routing optimization lies in the significantly reduced exchange of sensitive parameters necessitating sharing with the controller. The information exchange is confined to a query concerning QKP viability in providing a specific key quantity, avoiding the use of the exact number of keys residing within the QKPs.
With respect to the computational cost, the ILP solution has the highest requirements. The controller needs to compute the optimized solution within the time frame of 60 s imposing high requirements on the available computational resources especially for larger networks. Hence, requirements for the controller are lower for all other algorithms. The required computational resources limit also the scalability of the ILP solution either with a growing network size or a higher number of demands.
Funding
Bundesministerium für Bildung und Forschung (16KISQ066, 16KISQ069).
Acknowledgment
We thank the Fraunhofer HHI and especially Nino Waltena for providing the QKD model.
REFERENCES
1. P. W. Shor, “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer,” SIAM J. Comput.26, 1484–1509 (1997). [CrossRef]
2. R. Van Meter and D. Horsman, “A blueprint for building a quantum computer,” Commun. ACM56, 84–93 (2013). [CrossRef]
3. A. K. Lenstra, Key Lengths Contribution to The Handbook of Information Security (2010).
4. D. Gottesman and H.-K. Lo, “Proof of security of quantum key distribution with two-way classical communications,” arXiv, arXiv:quant-ph/0105121 (2023). [CrossRef]
5. L. Salvail, M. Peev, E. Diamanti, et al., “Security of trusted repeater quantum key distribution networks,” J. Comput. Secur.18, 61–87 (2010). [CrossRef]
6. V. Scarani, H. Bechmann-Pasquinucci, N. J. Cerf, et al., “The security of practical quantum key distribution,” Rev. Mod. Phys.81, 1301–1350 (2009). [CrossRef]
7. V. Mavroeidis, K. Vishi, M. D. Zych, et al., “The impact of quantum computing on present cryptography,” Int. J. Adv. Comput. Sci. Appl.9, 54 (2018). [CrossRef]
8. C. H. Bennett and G. Brassard, “Quantum cryptography: public key distribution and coin tossing,” Theor. Comput. Sci.560, 7–11 (2020). [CrossRef]
9. N. Walenta, A. Burg, D. Caselunghe, et al., “A fast and versatile QKD system with hardware key distillation and wavelength multiplexing,” New J. Phys.16, 013047 (2014). [CrossRef]
10. S.-H. Baek, S.-C. Yang, C.-Y. Park, et al., “Room temperature quantum key distribution characteristics of low-noise InGaAs/InP single-photon avalanche diode,” J. Korean Phys. Soc.78, 634–641 (2021). [CrossRef]
11. P. Eraerds, N. Walenta, M. Legre, et al., “Quantum key distribution and 1 Gbit/s data encryption over a single fibre,” New J. Phys.12, 063027 (2010). [CrossRef]
12. W. J. Munro, K. Azuma, K. Tamaki, et al., “Inside quantum repeaters,” IEEE J. Sel. Top. Quantum Electron.21, 78–90 (2015). [CrossRef]
13. “Quantum key distribution networks - key management,” ITU-T Recommendation Y.3803 (2022).
14. M. Mehic, M. Niemiec, S. Rass, et al., “Quantum key distribution: a networking perspective,” ACM Comput. Surv.53, 96 (2021). [CrossRef]
15. M. Peev, C. Pacher, R. Alléaume, et al., “The SECOQC quantum key distribution network in Vienna,” New J. Phys.11, 075001 (2009). [CrossRef]
16. C. Lee, Y. Kim, K. Shim, et al., “Key-count differential-based proactive key relay algorithm for scalable quantum-secured networking,” J. Opt. Commun. Netw.15, 282–293 (2023). [CrossRef]
17. R. Bassi, Q. Zhang, A. Gatto, et al., “Quantum key distribution with trusted relay using an ETSI-compliant software-defined controller,” in 19th International Conference on the Design of Reliable Communication Networks (DRCN) (2023).
18. E. Arabul, R. S. Tessinari, O. Alia, et al., “100 Gb/s dynamically programmable SDN-enabled hardware encryptor for optical networks,” J. Opt. Commun. Netw.14, A50–A60 (2022). [CrossRef]
19. Y. Cao, Y. Zhao, C. Colman-Meixner, et al., “Key on demand (KoD) for software-defined optical networks secured by quantum key distribution (QKD),” Opt. Express25, 26453–26467 (2017). [CrossRef]
20. “Security framework for quantum key distribution networks,” ITU-T Recommendation X.1710 (2020).
21. S. Orlowski, R. Wessäly, M. Pióro, et al., “SNDlib 1.0—survivable network design library,” Networks55, 276–286 (2010). [CrossRef]
22. A. Hagberg, P. J. Swart, and D. A. Schult, “Exploring network structure, dynamics, and function using NetworkX,” LA-UR-08-05495 (Los Alamos National Laboratory, 2008), https://www.osti.gov/biblio/960616.
23. E. Fitzke, L. Bialowons, T. Dolejsky, et al., “Scalable network for simultaneous pairwise quantum key distribution via entanglement-based time-bin coding,” PRX Quantum3, 020341 (2022). [CrossRef]
24. A. Luykx and K. Paterson, “Limits on authenticated encryption use in TLS,” 2016, https://www.semanticscholar.org/paper/Limits-on-Authenticated-Encryption-Use-in-TLS-Luykx-Paterson/81edbc8b8cf013ef1be73e1ca9b4da10b29148a5.
