Network Topologies for QKD Networks

arXiv:2608.28036v1 [cs.NI] 28 Aug 2026

Network Topologies for QKD Networks Ori Rottenstreich

Ran Hasson Ruso

Eliahu Cohen

Technion

NVIDIA

Bar-Ilan University

Abstract—Quantum key distribution (QKD) is a method for distributing cryptographic keys between remote endpoints, enjoying security based on quantum physics. This paper makes a first step towards studying topologies for QKD networks. QKD networks imply several required characteristics for their reliability and efficiency. We express such properties in terms of graph structure. For the comparison of potential graphs, we describe cost functions that allow us to identify families of graphs that are reliable and efficient. To make the discussion realistic, we summarize representative field-reported QKD performance numbers and illustrate the sensitivity of secret-key rate (SKR) to a few dB of additional loss. Last, we present methods to construct large efficient graphs through connecting smaller graphs.

I. I NTRODUCTION Quantum key distribution (QKD) is a method for distributing cryptographic keys between two entities, enjoying security based on quantum physics. QKD is one of the most mature technologies among emerging technologies that leverage quantum capabilities for outperforming conventional methods in terms of functionality and performance [1]. A physical QKD system is a communication system that exploits quantum physics to facilitate a distribution of quantum correlations between parties that can lead to joint computation of a secret key. QKD [2], [3] relies on three main foundational principles known as (i) Quantization and indivisibility of quanta; (ii) Quantum uncertainty; (iii) No-cloning theorem. Several recent studies aim to examine the integration of QKD in datacenters to enhance security [4], [3]. Datacenter networks are emerging to satisfy the computation, communication and caching requirements of growing services. Many of these services also have high security requirements. These can include, among others, hospitals, smart cities, banking and military applications. The security of traditional key-distribution techniques can be compromised with the developments in quantum computing. While traditional datacenters often have 3C requirements such as communication, computation and caching, with QKD they also include a fourth fundamental requirement of cryptographic capabilities. Jointly they are often known as 4C. The design of traditional datacenters has been studied over the years, in multiple dimensions, such as their physical structure (topology) [5], [6], [7], resource allocation (e.g., mapping of tenants) [8] and routing for communication among hosts of the same application (path selection) [9]. Fig. 1 illustrates the Vienna SECOQC trusted-relay QKD network, one of the earliest multi-node QKD network demonstrations [10] (see also [2]). The FP6 Project SECOQC (Secure Communication based on Quantum Cryptography) involved 41 research and

STP

SIE

ERD

BRT

GUD

FRM

Fig. 1. Example of a real QKD Topology of the SECOQC QKD network with six nodes and eight edges. Node’s names are mentioned as their original names. Source: Mehic et al. [2].

industrial partners from 11 European Union countries, Russia, and Switzerland in 2004. The traditional approaches in the three dimensions might not optimize QKD networks due to some special properties: (i) (Robustness) QKD networks should be able to handle node and link failures quickly. This should be taken into account, e.g, in selecting multiple paths which can be disjoint with regards to their intermediate nodes or links. (ii) (Limited path length) In practice, each quantum link is loss-limited: fibre attenuation (added optical loss, in dB) and component insertion loss directly reduce the secret-key rate (SKR) and can drive it to zero. End-to-end key delivery across multiple hops is typically achieved by trusted relays and key management [11]; therefore, hop count mainly increases the trust assumptions and consumes link key capacity, rather than “accumulating quantum noise” end-to-end [2]. (iii) (Routing criteria) Beyond path length, additional criteria can affect path selection, such as the level of trust in nodes along the path. Including vulnerable nodes along the path can harm security. (iv) (Loss sensitivity and hardware insertion loss) In a datacenter, a “logical” edge may traverse patch panels, wavelength division multiplexing (WDM) components, or optical switches; even a few dB of extra loss can materially reduce SKR, and beyond a loss budget the SKR can drop to zero. This motivates making topological comparison explicitly lossaware (see Fig. 2). Note that below we focus on trusted-relay (hop-by-hop) QKD networks. Quantum repeaters are beyond the scope of this work. QKD terminology for networking readers. (i) We use secret-key rate (SKR) as the link-level keygeneration capacity: after the quantum transmission, reconciliation, and privacy-amplification steps, it is the rate at which two adjacent QKD devices obtain shared secret bits.

Distance / loss

Reported performance

Vienna SECOQC (2008)

33 km, 7.5 dB

Switzerland (150 km link)

150 km, 43 dB

China metro (2012)

85.1 km, 18.4 dB

Cambridge UK network

10.6 km, 3.9 dB

Commercial datacenter interconnect

(see [12])

SKR 3.1 kbps, QBER 2.6% SKR 2.5 bps, QBER 5% (COW) SKR 0.77 kbps, QBER 5.26% (decoy BB84) SKR 2580 kbps, QBER < 2.5% Avg. SKR 2.392 kbps, QBER ≈ 1.9%

103.5 SKR (bps)

Deployment (examples)

103

4

TABLE I I NDICATIVE FIELD - REPORTED QKD PERFORMANCE HIGHLIGHTS ( SUMMARISED IN [12] AND REFERENCES THEREIN ).

6

8

10

Added attenuation (dB)

(a) SKR vs. added attenuation.

(ii) Quantum bit error rate (QBER) is the fraction of sifted key bits on which the two endpoints disagree. It reflects noise, device imperfections, and other errors, and it directly affects how much secret key can be extracted. We focus on trustedrelay QKD networks, where an end-to-end key over multiple hops is supported by hop-by-hop QKD keys and intermediate relays must be trusted. Thus, path length is cruical not because a quantum signal traverses many hops end-to-end, but because each hop consumes link key capacity and each relay increases the trust surface. (iii) Finally, each physical QKD link has a finite optical-loss budget, including fiber loss and insertion loss from connectors, patch panels, WDM components, or optical switches. Since attenuation is measured in dB, a few additional dB can substantially reduce photon arrival probability and therefore SKR. Beyond a platform-dependent threshold, the net key rate can become effectively zero. From graph metrics to QKD practice. We first use unweighted graph metrics as protocol-agnostic proxies for (i) robustness (critical nodes, disjoint paths) and (ii) keytransport overhead (mean hop distance) in trusted-relay QKD networks. We then make the same comparison loss-aware by assigning each edge a loss Le and a key-generation capacity Ke ≈ SKR(Le ) (Sec. II-A–II-C), linking d¯ and |E| to delivered key rate. Disjoint paths can also enable multipath key splitting to reduce reliance on any single relay (Sec. II-C). Field numbers and loss sensitivity. Table I summarizes indicative (and highly variable) field-reported QKD performance points, as collected in [12]. Fig. 2 reproduces a datacenter interconnect attenuation test from [12], showing how SKR degrades as added attenuation increases. These numbers are not meant as universal benchmarks; rather, they motivate why a topology “cost function” should include edge loss budgets (fibre length + insertion loss) and not only hop count. We focus on the following research avenues: • Developing cost metrics for networks optimized for QKD in terms of their overhead and robustness. • Designing new topologies for QKD networks which can have a good tradeoff between robustness and the implied overhead. • Discussion on the extension of the results beyond graph structure. Table II summarizes the main notations of the paper.

QBER (%)

3

2

1

0

4

6

8

10

Added attenuation (dB)

(b) QBER vs. added attenuation. Fig. 2. Sensitivity of QKD key parameters to added attenuation in a commercial datacenter interconnect field trial (values from Table 3 in [12]). TABLE II S UMMARY OF M AIN N OTATIONS . Notation n O R C Φ(G), Ψ(G) α, β, γ D, d¯

Meaning Number of participating nodes Operational cost for nodes and edges of a graph Reliability factor of a graph Connectivity factor of a graph Cost functions for a graph Parameters of graph cost functions maximal distance (diameter) and mean distance among nodes

II. G RAPH P ROPERTIES AND E FFICIENT E VALUATION We study simple graph properties that can impact the efficiency of QKD networks. A. Fundamental Graph Properties Consider a connected graph G = (V, E) describing a QKD network. Denote by n = |V | the number of nodes in a graph. Number of edges Mean degree - The mean degree of a node among the n nodes • Max degree - Maximal degree among the n nodes • Mean distance - The average distance in the graph among
all n2 pairs of nodes. Distance affects latency for key distribution. • Max distance (diameter) - The longest shortest path in the graph represents the worst-case latency for key distribution. • •

Family index 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

Graph Example (list of edges) (A,B), (A,C), (A,D), (A,E) (A,B), (A,D), (A,E), (B,C) (A,C), (A,E), (B,C), (B,D) (A,B), (A,C), (A,D), (A,E), (B,C) (A,B), (A,C), (A,E), (B,C), (B,D) (A,C), (A,D), (A,E), (B,C), (B,D) (A,B), (A,E), (B,C), (B,D), (C,D) (A,D), (A,E), (B,C), (B,E), (C,D) (A,B), (A,C), (A,D), (A,E), (B,C), (B,D) (A,C), (A,D), (A,E), (B,C), (B,D), (B,E) (A,B), (A,C), (A,E), (B,C), (B,D), (C,D) (A,B), (A,C), (A,D), (A,E), (B,E), (C,D) (A,B), (A,D), (A,E), (B,C), (B,E), (C,D) (A,B), (A,C), (A,D), (A,E), (B,C), (B,D), (B,E) (A,B), (A,C), (A,D), (A,E), (B,C), (B,D), (C,D) (A,B), (A,C), (A,D), (A,E), (B,C), (B,E), (C,D) (A,C), (A,D), (A,E), (B,C), (B,D), (B,E), (C,D) (A,B), (A,C), (A,D), (A,E), (B,C), (B,D), (B,E), (C,D) (A,B), (A,C), (A,D), (A,E), (B,D), (B,E), (C,D), (C,E) (A,B), (A,C), (A,D), (A,E), (B,C), (B,D), (B,E), (C,D), (C,E) (A,B), (A,C), (A,D), (A,E), (B,C), (B,D), (B,E), (C,D), (C,E), (D,E)

# Edges

Mean degree

Max degree

Mean Distance

Diameter

4 4 4 5 5 5 5 5 6 6 6 6 6 7 7 7 7 8 8 9 10

1.6 1.6 1.6 2.0 2.0 2.0 2.0 2.0 2.4 2.4 2.4 2.4 2.4 2.8 2.8 2.8 2.8 3.2 3.2 3.6 4.0

4 3 2 4 3 3 3 2 4 3 3 4 3 4 4 4 3 4 4 4 4

1.6 1.8 2.0 1.5 1.6 1.6 1.7 1.5 1.4 1.4 1.5 1.4 1.4 1.3 1.3 1.3 1.3 1.2 1.2 1.1 1.0

2 3 4 2 3 3 3 2 2 2 3 2 2 2 2 2 2 2 2 2 1

Non-critical Nodes 4 3 2 4 3 4 3 5 4 5 4 4 5 5 4 5 5 5 5 5 5

Pairs with Disjoint Paths 0 0 0 3 3 6 3 10 6 10 6 6 10 10 6 10 10 10 10 10 10

TABLE III BASIC PROPERTIES OF THE VARIOUS CONNECTED FAMILIES FOR GRAPHS WITH n = 5 NODES .

Critical nodes - A critical node refers to a node whose removal (with its connected edges) eliminates the graph connectivity. • Pairs with Disjoint Paths - Connectivity is reliable when maintained upon failures. We measure the number of pairs of nodes with at least two link-disjoint paths. Such paths allow connectivity even upon any single failure of a link. Disjoint paths are not only useful for availability under failures. In trusted-relay QKD networks, they can also support trust reduction via multipath secret sharing; we revisit this idea when defining trust-aware objectives in Sec. 2.3. Loss-weighted edges and QKD-feasible connectivity. For analyzing QKD networks, hop count alone is insufficient. Each edge e ∈ E corresponds to an optical path with total loss (dB) •

Le = αfib · ℓe + ILe , where αfib ≈ 0.2 dB/km at 1550 nm, ℓe is fiber length, and ILe aggregates insertion loss (connectors/patch panels, WDM elements, switches). Since SKR can degrade sharply with a few dB of extra loss (Fig. 2), we associate to each edge an effective key-generation capacity Ke = max{0, SKR(Le )}. A simple analytical approximation for the loss dependence can be obtained from the exponential attenuation of photons in optical fibre. If ηe = 10−Le /10 denotes the channel transmittance, the secret-key rate for common DV QKD protocols (e.g., decoy-state BB84) scales approximately linearly with ηe in the moderate-loss regime. A convenient first-order model is therefore ( K0 · 10−Le /10 , Le ≤ Lmax , SKR(Le ) ≈ 0, Le > Lmax , where K0 is the achievable SKR at negligible loss (set by source rate, detector efficiency, and post-processing), and Lmax is a platform- and protocol-dependent loss budget beyond which dark counts / noise and finite-size effects drive the net SKR to (effectively) zero.

Number of nodes (n) Total families Connected families

3 4 2

4 11 6

5 34 21

6 156 112

7 1044 853

8 12346 11117

TABLE IV N UMBER OF FAMILIES OF GRAPHS AS A FUNCTION OF THE NUMBER OF NODES .

Define the feasible-edge set Efeas = {e ∈ E : Ke > 0} and the feasible subgraph Gfeas = (V, Efeas ). We call the network QKD-feasible connected if Gfeas is connected (or if a target subset of node pairs remains connected in Gfeas ). A Graph Example. Fig. 3 illustrates an example of a graph C B G = (V, E) with n = |V | = 5 nodes A, B, C, D, E with |E| = E D A 5 edges. The mean node degree is directly given by the number Fig. 3. Graph example of edges as 2 · |E|/n = 10/5 = 2 such that the nodes with the maximal degree are A and B, each with
degree 3. To compute the mean distance we consider the n2 = 10 pairs of nodes which together imply mean distance of 1.6 and diameter (maximal distance) of 3. We can see that connectivity is maintained even if one of the nodes C, D or E are eliminated but not if A or B are disconnected. We refer to A and B as critical nodes and illustrate them as being colored in red with dots. We can also see that among the pair of nodes, between any two nodes among A, B, C we can establish two link-disjoint paths. In this case, they refer to the directed edge and to the path through the other nodes among the three. We cannot establish such paths for pairs that involve D and E so the number of pairs with disjoint paths is 3. B. Practical Evaluation for Small Graphs For a small number of nodes (such as n ≤ 8), we would like to simply identify graphs with properties allowing efficient QKD. However, examining all potential graphs can be intensive. As there are m = n· (n − 1) / 2 edges, and each

E

B

C

A

D

E

(a) Star (1)

E

B

C

A

D

B

C

A

D

(m) C5 + chord (13)

E

C

A

D

E

(b) Fork (2)

(g) C3 with 2 tails (sep) (7)

E

B

B

C

A

D

(s) Wheel (W5 ) (19)

E

B

C

A

D

(h) Cycle (C5 ) (8)

E

B

C

A

D

(n) K4 with tail (center) (14)

D

B

A

C

E

(c) Path (3)

E

B

A

C

(d) Triangle + Starcenter (4)

B

C

C

D

A

D

A

B

(i) Diamond + tail (A) (9)

E

D

B

C

A

D

(o) K4 with (leaf) (15)

C

A

D

(p) C5 with 2 chords (X) (16)

tail

E

E

B

B

C

A

D

C

A

D

(e) C3 with Path-tail (5)

E

(j) Bipartite (K2,3 ) (10)

E

E

B

B

C

A

D

E

D

B

A

C

(f) C4 with tail (6)

E

B

C

A

D

(k) Diamond + tail (D) (11)

(l) Butterfly (12)

B

D

B

C

A

C

A

D

E

(q) C5 with 2 chords (parallel) (17)

(t) K5 minus 1 edge (20)

E

(r) K5 minus 2 adjacent edges (18)

E

B

C

A

D

(u) Complete Graph (K5 ) (21)

Fig. 4. Illustration of the families of graphs with n = 5 nodes. The properties of the families are detailed in Table III. Critical nodes are shown in red with dots.

edge can be included or not, there are 2m potential graphs. As the mentioned properties from Sec. II-A can be derived from the graph structure, many of those graphs are identical with respect to these properties. There is no need to consider all such graphs but only to examine a representative of each group of graphs with the same structure. We refer to a group of graphs with the same structure as a family, namely we see nodes as without any particular labeling. These families are also known as isomorphism classes of unlabeled graphs. For instance, with n = 3 and nodes A, B, C we refer to the three graphs with two edges (A,B), (A,C) or (A,B), (B,C) or (A,C), (B,C) as of the same family. In the same family, graphs have the same basic properties such as number of edges, average and max degree, etc. Interestingly, for small n, the number of families is not that large. Among these families, we can focus on connected families, namely those referring to connected graphs. For n = 5 for instance, there are only 21 connected families. Table IV shows the number of families and the number of connected families per various values of the nodes count n ∈ {3, 4, 5, 6, 7, 8}. Consider, for instance, graphs with n = 5 nodes. We can compare the 21 connected families of graphs with regard to several properties affecting QKD network performance. Table III shows several graph properties that can be computed for the various 21 families of graphs which are connected and have n = 5 nodes. It refers to the properties from

Sec. II-A. Families are arranged in an increasing order of the number of edges (ranging between 4 to 10). The graph from Fig. 3 appears in the table as the family with index (5). There is a clear connection between several of the properties. As many of these properties have been well studied in graph theory, we present only a short overview. (i) Upon adding edges, a node can become non-critical. (ii) A node with degree 1 is a non-critical node. However, such a node cannot be among the pairs of nodes with two or more disjoint paths. (iii) There are graphs with n edges in the form of a cycle (often denoted by Cn ) where all nodes are non-critical and all pairs of nodes have disjoint paths. There are no graphs with less than n edges having any of these two properties. Fig. 4 provides a visual illustration of these 21 families, previously summarized in Table III. Again, the critical nodes are shown in red with dots. We informally refer to the structure of each family in the caption of each subfigure. C. Cost Functions for Graphs There is no one way to measure the various properties of a graph G. Accordingly, we do not aim to indicate a particular formula and only overview two such forms that can be justified. Before presenting the formulas, we overview their potential components:

1.8 1.44

16

1.08

14

0.72

12

0.36

10

0 1 2 3 4 5 6 7 8 9 101112131415161718192021

cost

18

operational cost reliability connectivity

reliability and connectivity

operational cost

20

90 80 70 60 50 40 30 25 20 15 10 5 0

Cost function Φ Cost function Ψ

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

family index

family index Fig. 5. Components of the cost function for the 21 graph families connecting n = 5 nodes (with parameter values α = β = γ = 2).

O - This is the operational cost of the graphs, measured as its number of nodes plus its number of edges. O = α · |V | + |E| = α · n + m The parameter α allows to change the weight of overhead of nodes with regards to links. We typically set α = 2. When the number of nodes n is fixed, the operational cost is affected only by the number of edges. R - The reliability factor of the graph can take into account both properties of the number of non-critical nodes and the number of pairs with link-disjoint paths. Let nnc ∈ [0, n] be
the number of non-critical nodes. Likewise, let np ∈ [0, n2 ] the number of pairs of nodes with link-disjoint pairs of paths. For some weight β, the factor is given as   1  n R= β · nnc /n + np / . β+1 2 The reliability factor has values in [0, 1]. The parameter β allows to change the weight of the two components of the factor. We typically set β = 2 such that the weight of the ratio of non-critical nodes has a higher weight than the ratio of pairs with disjoint paths. C - The connectivity factor takes into account both mean ¯ and the graph diameter distance among nodes (denoted as d) (denoted as D). Both are measured in units of number of hops. To compare graphs of various number of nodes, we scale the values by log n as often several properties related to distance and diameter in random graphs scale with such a factor under some assumptions [13], [14].

C = (γ + 1) · log n / γ · d¯ + D . The parameter γ balances the two values. We typically set γ = 2 such that the mean distance has higher weight than the diameter as it is influenced by all pairs of nodes. The three factors O, R, C can be jointly considered in multiple ways. Overall, we prefer lower operational cost and higher reliability and connectivity factors. Two simple cost functions are √ Φ(G) = O/(R · C) and Ψ(G) = O/ R · C.

Fig. 6. Values the cost functions for the 21 graph families connecting n = 5 nodes (with parameter values α = β = γ = 2).

Rank 21st (Lowest) 20th 19th

Function Φ Family 21 (12.42) Family 8 (15.53) Family 10 (15.90)

Function Ψ Family 8 (15.26) Family 21 (15.76) Family 10 (15.95)

1st (Highest) 2nd 3rd

Family 3 (87.05) Family 2 (47.84) Family 7 (39.76)

Family 3 (34.12) Family 2 (25.88) Family 7 (24.42)

TABLE V R ANKING OF GRAPH FAMILIES BY THEIR COST VALUES . F OR THE TWO FUNCTIONS , THE THREE FAMILIES WITH THE LOWEST AND HIGHEST COST VALUES ARE SHOWN . L OW FUNCTION VALUES REPRESENT EFFICIENCY AND INDICATE LOW OPERATIONAL COST WITH HIGH RELIABILITY AND CONNECTIVITY.

From Graph Structure to Delivered Secret-Key Rate. To connect d¯ and |E| to key delivery, consider an idealized setting where each edge can generate K secret bits/sec and end-toend key transport uses hop-by-hop one-time-pad protection
over trusted relays. If all n2 pairs demand the same end-toend key rate k and traffic is perfectly balanced, the network
must “spend” approximately n2 · k · d¯ link-key bits/sec (each delivered bit traverses d¯ hops on average). Since the network produces at most |E| · K bits/sec across all links, feasibility requires   n k ≤ |E| · K · d¯−1 / . 2 This highlights why (i) more edges increase aggregate keygeneration resources, while (ii) smaller mean distance improves key-transport efficiency. In a real QKD network, K becomes edge-dependent (K → Keeff ) and decays with loss (Fig. 2), motivating loss-aware evaluation beyond Φ, Ψ. Fig. 5 illustrates the values of the three components (operational, reliability and connectivity) for the 21 families of graphs with n = 5 nodes. Similarly, Fig. 6 shows the values of the two cost functions Φ(G) and Ψ(G) for those 21 families. Table V lists the three families with the lowest and highest values for the two cost functions. Low values indicate high efficiency. For both cost functions, Family 3 which refers to the path graph has the highest cost. The reason is its low reliability and connectivity values. As shown by the nodes in red in Fig. 4, it has more critical nodes than all other families and it also has no pairs with disjoint paths. The path structure

also implies the highest mean distance as well as the highest diameter. Family 2 and Family 7 also have relatively high values of the two cost functions. On the positive side, the three families with the lowest values for the two cost functions are Family 8, 10, and 21, while the superiority alternates between Family 8 and 21. a) QKD-aware extensions (capacity, loss, and trust).: The structural objectives Φ(G), Ψ(G) are useful, but a deployed QKD network is naturally a weighted graph. Using the per-edge loss Le and key-generation capacity Ke defined in Sec. II-A, we obtain two complementary objective families: (1) Capacity-aware objectives. Given a demand matrix {dst } (target key supply between node pairs) and per-edge capacities {Ke }, one canP optimize a multi-commodity flow of key material subject to (s,t) fst (e) ≤ Ke for allPedges. A simple objective is to maximize a utility such as s<t wst · log(kst + ε), where kst is delivered end-to-end key rate and wst ≥ 0 is an application-defined weight (priority) for the pair (s, t). (2) Trust/risk-aware objectives. If intermediate nodes are treated as trusted relays, then each multi-hop path induces an explicit trust surface. One can assign each node a risk score rv (from operational security assessment) and penalize paths P by Risk(P ) = v∈P \{s,t} rv , or prefer solutions that keep all high-value flows within a low-risk subgraph. Combining (1) and (2) yields a more realistic “cost function” for topology design than purely structural metrics. D. Efficient Graphs for Larger n Values For larger values of n (e.g., n > 8), exhaustive enumeration of graph families becomes more challenging. A natural next step could be to apply local search and dedicated heuristics which directly optimize the selected cost function (structural Φ, capacity-aware, or trust-aware) under constraints on maximum degree and total number of links. We describe two alternative simple methods to construct efficient graphs for such n values: Construction I. If for instance n = k · n0 for small k ∈ [3, n0 ], we consider k copies of an efficient family for n0 nodes. We select a representative node from each family as a node with link-disjoint path to many other nodes. We
make all representatives to be fully connected by adding k2 links. Fig. 7 illustrates a construction of a graph with n = 15 nodes based on three graphs of 5 nodes, each in the form of Family 10 in Fig. 4, which was ranked among the families with lowest values of the cost functions (Table V). In this family, all five nodes are non-critical and there are link-disjoint paths between all 10 pairs. Such properties allow establishing link
disjoint paths between any pair among the 15 = 105 pairs 2 in the joint topology. All nodes besides the three representing nodes A, F, M are non-critical nodes. Adding the three edges in red makes all nodes be non-critical. We deduce interesting properties for Construction I (with the red edges): Property 1. Consider Construction I. (i) While the links connecting the multiple copies of the family increase the mean

J

I

H

G

F

Q

P

O

C

D

N

M

A

B

E

Fig. 7. An illustration of the construction of a graph with n = 15 nodes based on k = 3 graphs of an efficient family with 5 nodes and 6 edges (Family 10).

J

I

H

G

F

L

Q

P

O

C

D

N

M

A

B

X

W

R

S

Z

Y

T

U

E

V

Fig. 8. An illustration of the hierarchical construction of a graph with n = 25 nodes based on k = 5 graphs of an efficient family with 5 nodes and 6 edges (Family 10).

node degree by less than 1, they bound the diameter to be at most 2D + 1, where D = 2 is the diameter of Family 10. (ii) The construction allows establishing pairs of linkdisjoint paths also between all pairs of nodes from two distinct copies of the n-node graph. (iii) Moreover, in the construction all nodes are non-critical.
Proof. To see (i), the inequality k2 < k 2 /2 ≤ k · n0 /2 = n/2 bounds the increase in the mean node degree as we connect all pairs of copies of
n0 nodes with two links, making the added links to be 2 · k2 < n. In each copy of the family nodes can connect within a distance of the diameter D. To connect nodes in various copies, the path can use a single link connecting the copies in addition of the use of at most D edges within each family. For (ii) link-disjoint paths can be established based on the ability to establish such path in Family 10. In each copy we connect the node to the two representing nodes by linkdisjoint paths. Family 10 allows establishing such paths. We add to the paths the two links connecting the two pairs of nodes with one node in each copy in each pair. To see (iii) recall that all nodes in Family 10 are non-critical. Connecting each pair of copies with two edges guaranties the connectivity is maintained for any failure of a node. Construction II. This construction is hierarchical and is based on an efficient family of n0 nodes for establishing graphs of (n0 )2 nodes. To do so, we replace each node in the family by a copy of the family. Namely, we connect a representative node from n0 copies of the family in a graph with the form of the family itself. Fig. 8 illustrates a construction of a graph with n = 25 nodes based on five graphs of 5 nodes, each in the form of

Family 10 in Fig. 4. Recall that this family had low values of the cost functions (Table V). We deduce interesting properties also for Construction II: Property 2. Consider Construction II. (i) The diameter is at most 3 · D, where D = 2 is the diameter of Family 10. (ii) The construction allows establishing pairs of linkdisjoint paths also between all pairs of nodes from two distinct copies of the n-node graph. (iii) In the new construction, all nodes besides those which are connecting the families (A, F, M, R, W) are non-critical nodes. The proof is similar to the proof of the corresponding property for Construction I with the following changes: As there is no direct edge between all copies of Family 10, the diameter is larger. This also makes one node in each copy of the family to be a critical-node. Overall, Construction II allows connecting a similar number of nodes but with fewer edges compared to Construction I. However, this saving in the number of nodes, results in a small increase in the diameter and implies that some of the nodes be critical nodes. High-level Evaluation of Simple Datacenter Topologies. We suggest benchmarking against several baseline topologies that are realistic in a datacenter setting. We focus on Construction I rather than Construction II for comparing topologies with almost identical number of nodes. We make the following comparison: (a) Graph from Fig. 7 (with red edges) based on Construction I, (b) small fat-tree [5] (16 nodes in four groups of 4 each, connected to 4 rail nodes and 2 upper spines), (c) Dragonfly+ [6] (with four groups of 4 leaves), (d) Torus [15] (of size 2 × 2 × 4) and (e) ring. For each topology, we can report in Table VI graph metrics (like Table III) that shows the efficiency of Construction I. Topology # nodes (+# internal) # links O R C Φ Ψ

Fig. 7 15 24 54 1 0.934 57.82 55.87

Fat-tree 16 6 24 68 0.812 0.828 101.14 82.93

Dragonfly+ 16 16 88 152 1 1.335 113.86 131.54

Torus 16 32 64 1 0.978 65.44 64.72

ring 16 16 48 1 0.519 92.49 66.67

TABLE VI H IGH LEVEL COMPARISON OF DATACENTER TOPOLOGIES AND SIMPLE GRAPH STRUCTURES FOR SERVING QKD.

III. C ONCLUSIONS AND F UTURE W ORK This manuscript takes a first step toward topology design for trusted-relay QKD networks by connecting graph structure to key delivery. We propose structural objectives such as operational cost, robustness (non-critical nodes and disjoint paths), and hop distance and then combine them into simple cost functions Φ, Ψ. Using these, we enumerate and rank

unlabeled connected graph families for small n (illustrated for n = 5) and give a simple composition method for larger networks. To tie the graph-theoretic view to physics, we also introduce a lightweight edge model (loss Le and capacity Ke ≈ SKR(Le )) and highlight the sensitivity of SKR to a few dB of additional loss. Our future work will employ these tools and move further, even beyond graph theory, by optimizing routing and key management on weighted graphs. Concretely, we plan to (i) compute capacity-aware routing / multi-commodity key flows under heterogeneous {Ke }, (ii) incorporate explicit trust/risk constraints and multipath key splitting to reduce reliance on any single relay, and (iii) benchmark candidate topologies on realistic datacenter layouts under measured insertion-loss budgets and reconfiguration duty cycles that affect effective key capacity and security. R EFERENCES [1] S. Pirandola, U. L. Andersen, L. Banchi, M. Berta, D. Bunandar, R. Colbeck, D. Englund, T. Gehring, C. Lupo, C. Ottaviani et al., “Advances in quantum cryptography,” Advances in optics and photonics, vol. 12, no. 4, pp. 1012–1236, 2020. [2] M. Mehic, M. Niemiec, S. Rass, J. Ma, M. Peev, A. Aguado, V. Martin, S. Schauer, A. Poppe, C. Pacher et al., “Quantum key distribution: A networking perspective,” ACM Computing Surveys (CSUR), vol. 53, no. 5, pp. 1–41, 2020. [3] Q. Zhu, X. Yu, Y. Zhao, A. Nag, and J. Zhang, “Resource allocation in quantum-key-distribution-secured datacenter networks with cloud-edge collaboration,” IEEE Internet Things J., vol. 10, no. 12, pp. 10 916– 10 932, 2023. [4] N. Jain, U. Hoff, M. Gambetta, J. Rodenberg, and T. Gehring, “Quantum key distribution for data center security–a feasibility study,” arXiv preprint arXiv:2307.13098, 2023. [5] M. Al-Fares, A. Loukissas, and A. Vahdat, “A scalable, commodity data center network architecture,” in ACM SIGCOMM, 2008. [6] A. Shpiner, Z. Haramaty, S. Eliad, V. Zdornov, B. Gafni, and E. Zahavi, “Dragonfly+: Low cost topology for scaling datacenters,” in IEEE HiPINEB Workshop, 2017. [7] J. H. Ahn, N. L. Binkert, A. Davis, M. McLaren, and R. S. Schreiber, “HyperX: Topology, routing, and packaging of efficient large-scale networks,” in ACM/IEEE Conference on High Performance Computing (SC), 2009. [8] O. Rottenstreich and J. Yallouz, “Edge-disjoint tree allocation for multitenant cloud security in datacenter topologies,” IEEE/ACM Trans. Netw., vol. 32, no. 4, pp. 2858–2874, 2024. [9] F. Zahid, E. G. Gran, B. Bogdanski, B. D. Johnsen, and T. Skeie, “Efficient network isolation and load balancing in multi-tenant HPC clusters,” Future Gener. Comput. Syst., vol. 72, pp. 145–162, 2017. [10] M. Peev et al., “The SECOQC quantum key distribution network in Vienna,” New Journal of Physics, vol. 11, no. 7, p. 075001, 2009. [11] E. Dervisevic, A. Tankovic, E. Kaljic, M. Voznak, and M. Mehic, “Design of a key management system for efficient key supply in quantum key distribution networks,” Journal of Optical Communications and Networking, vol. 18, no. 2, pp. 98–113, 2026. [12] K. Qiu, J. Y. Haw, H. Qin, N. H. Y. Ng, M. Kasper, and A. Ling, “Quantum-secured data centre interconnect in a field environment,” Journal of Surveillance, Security and Safety, vol. 5, pp. 184–197, 2024. [13] R. Albert and A.-L. Barabási, “Statistical mechanics of complex networks,” Reviews of modern physics, vol. 74, no. 1, p. 47, 2002. [14] D. J. Watts and S. H. Strogatz, “Collective dynamics of ‘smallworld’networks,” nature, vol. 393, no. 6684, pp. 440–442, 1998. [15] Google, “TPU architecture,” 2026. [Online]. Available: https://docs.cloud.google.com/tpu/docs/system-architecture-tpu-vm

Related documents

• Point-to-Point Protocol (PPP) Bridging Control Protocol (BCP)#193141
• PPP Bridging Control Protocol (BCP)#142132
• Hybrid QKD-PQC Network Emulation through Automated and Scalable Cloud-Native Orchestration#1129950
• Hybrid QKD-PQC Network Emulation through Automated and Scalable Cloud-Native Orchestration#1108610
• Qexploit#1133652