A #QuantumInternet Architecture Position Paper
Rodney Van Meter
2021/5/9
Okay, here's something I've been intending to write down for some years...a brief outline of my ideas for a Quantum Internet architecture, based both on our published works and some ideas that aren't yet published. The tl;dr is
- the Quantum Recursive Network Architecture (QRNA),
- RuleSet-based connections,
- a two-pass connection setup mechanism,
- qDijkstra with seconds per Bell pair as link cost for routing, and
- ??? for multiplexing.
Of course, a lot of this is covered in my book (Quantum Networking, available in the ACM online learning center, I believe, though just now I couldn't find it). But quite a bit about our ideas has evolved since I wrote the book, and it's good to summarize them anyway. Importantly, this is not a full survey of history or current thought; this is my idea for how things should go. I suppose you could call this my #QuantumInternet #PositionPaper.
See the AQUA group publications page and my Google Scholar page for access to some of these papers and to others.
First off, of course, it's important to recognize that there will be an internetwork, a network of networks. http://dx.doi.org/10.1109/MNET.2012.6246754 or, for an unfancy copy, https://aqua.sfc.wide.ad.jp/publications/van-meter-networking-review-preprint.pdf.
There will be more than one network architecture, no doubt; but to build a true Quantum Internet there will ultimately be only a single internetwork architecture.
There are a number of key design decisions that must be made:
- the nature of the fundamental service: Bell pairs? measured-out classical bits? qubit teleportation? multi-party graph states?
- how networks will come together to make an internetwork -- what is the nature of the interaction? (affected strongly by connections, below)
- the multiplexing discipline for resources (n.b.: not for access to wavelengths; this is a higher-level, end-to-end concept): circuit switching? time division muxing? statistical muxing, as in the Internet? buffer space muxing?
- nature of connections: entanglement swapping and purification (1G), or QEC (2G, 3G)? (affects internetworking)
- both of the above points affect whether a connection requires state at each repeater/router
- how connections are established
- how a path or route is chosen through the network
- all of the above affect choice of whether to try to do multipath for a single connection
- security for the network
There are more, but those are some of the critical ones. For more on these kinds of issues, (as well as a super-brief intro to quantum networking for those without the background), see our Internet Draft, hopefully to become an RFC soon.
On individual links, using memories at each end and photons to entangle, it seems pretty obvious to me that the fundamental primitive is the physical Bell pair (which we also call a "base entangled state"). Everything else builds on top of this.
However, that's made more complicated by the possibility of all-optical repeaters, an area we are currently researching. (See https://quantum-journal.org/papers/q-2021-02-15-397/ and work backwards from there.) An especially tricky issue we are actively working on right now is how to terminate such connections and how to make them interoperate with other types of connections/nodes/networks.
I believe that end-to-end multiparty states (GHZ, W, graph states) are likely to be extremely valuable, but I think it's an open question whether they are part of the fundamental service or should be created and managed entirely by applications running at end nodes. (In particular, I'm not at all sure what the APIs at the responders are like to make something like this happen. What is listen() like in this case?) At any rate, I think QRNA and our RuleSet-based approach can handle either connection-level or multiparty graph states as we develop it over time.
Same for multipath connections. It's a pretty obvious idea, and sorry but I can't remember who first proposed them in print (Perdrix? Benjamin?). My own opinion is that the benefits of multipath are likely to be minor, as a. often, the first hop will be the bottleneck anyway, b. asymmetry in the paths in the real world means that benefits will be minimal, and c. I assume there will be a lot of competition for resources on the net, and so the occasions when you can actually acquire the resources to do multipath effectively will be few. Oh, and d. the software complexity is high. So, I think it's doable in QRNA+RuleSet, but it's far down my list of things to work on.
So, let's stick with Bell pairs for the moment as both the fundamental link service and the *primary* end-to-end service. If we build well, it will be possible to extend later.
That disposes of...let's see...point 1 in the list above. On to point 2...
I think that the internetwork architecture should be a fully recursive system; we have named this the Quantum Recursive Network Architecture (QRNA), after Joe Touch's RNA. (Joe collaborated with us on this.) Today, an idealization of the Internet is that it's a two-level system, with BGP as the external gateway protocol and your choice of internal gateway protocol (OSPF and IS-IS being two of the most prominent). The reality, with tunneling having long been common, with switched Ethernets requiring a spanning tree protocol underneath even though they are nominally "link layer", and lately with the huge emphasis on virtualizing networks and services (e.g., network slices), is that the Internet has long been a multi-tier system with ad hoc interactions at each level. Designing from scratch, if we do a good job, this means that they are all unified into a single system.
Of course, if you want, at your network boundary, you can run anything you want inside: you just have to match the semantics of the connection's requests where they cross your borders.
Today, in the Internet, when a packet arrives at your border, the implied semantics are for you to forward it across (for transit) or to the matching end node (for termination). For the Quantum Internet, connections will have to be established in advance, with a certain amount of state. What I envision is a connection request protocol where, in a multi-tier system, connections are for some boundary-to-boundary (for transit) or boundary-to-end node (for request termination) operations. Presumably, for transit, what connection requests see is each entire network as a node in the graph at this level (i.e., top-level eBGP graph). Requests, then, are of the nature, "Please give me Bell pairs of fidelity F=x between here and address 1.2.3.4," where the requester knows that at this level of the graph that 1.2.3.4 is the next hop toward the destination.
Therefore, it's the responsibility of border routers to rewrite the request to internal actions that will fulfill this goal. Again, internally, it can be what you like -- but if you adopt QRNA internally, it can be creating a new set of QRNA requests that reach from here to the gateway on the other side of the network.
There's lots more to say on QRNA; see our original journal paper or discussion in my book. Beyond this vision, there is still a lot of work to do!
Two down, seven points to go...
Multiplexing: Lucho Aparicio's master's thesis addressed circuit switching, time-division multiplexing, statistical multiplexing (like Internet best-effort forwarding), and buffer space multiplexing, where the qubits at each router node are assigned to specific connections but multiple connections can pass through, getting assigned a share of the qubits. We studied aggregate throughput and fairness, and found, somewhat to our surprise, that stat mux works pretty well. Aggregate throughput is actually above circuit switching, because it does a pretty good job of allowing multiple areas of the network to be working productively at the same time. What's more, as far as I am aware, this was the world's first simulation of a quantum repeater network, as opposed to just a chain of repeaters. See Lucho's SPIE paper or Lucho's master's thesis.
However, that said, those early sims were for small-scale networks. I think this needs to be studied in much more detail to assess robustness in the face of complex, varying traffic patterns. In particular, I really fear that something akin to congestion collapse is possible, and is to be avoided. We already know that connection state will have to be maintained at repeaters & routers; quite probably there will have to be some active management of resources here, as well.
This has to coordinate with routing, below. Naturally, we want to avoid fully blocking muxing protocol if possible.
Oh, and one more point on this: given that early networks will be low performance, how do we prioritize connections? Do we create a static priority scheme, based on...how much money people have? Auction off time slots? Use a fixed accounting/charging scheme and lower nodes' priority the more they use, like an OS multi-level feedback queue? (Can you tell that I lectured on MLFQ last week?)
Point four: an internetwork architecture needs to accommodate 1G, 2G and 3G networks. Although these designations address advances in dealing with types of errors as our capabilities improve, they do not necessarily correspond to time. Nevertheless, 1G, using acknowledged link layer entanglement creation to handle photon loss and purification (quantum error detection) to handle noise and decoherence, will definitely be the first deployed. (Indeed, Delft is getting there, one step at a time.)
So, we need an internetwork capable of interconnecting different connection architectures. We have addressed how routers at the boundary can make entangled states that cross the borders.
Even for first-generation networks, though, you have to have a mechanism for saying, "Okay, Bob, once you get a Bell pair with Alice and a Bell pair with Charlie, execute entanglement swapping, then send the Pauli frame correction to Charlie and a notice-of-entanglement-transfer to Alice," and "If you have two Bell pairs with Alice, both with fidelity less than 0.9, then purify."
Our approach to this is to define Rules that have a condition clause and an action clause, very analogous to classical software defined networking (SDN). For a connection, each node is given a RuleSet that should comprehensively define what to do as local events occur (entanglement success, timeout, etc.) and as messages arrive.
This RuleSet-based operation is the heart of our work these days, and allows for explicit reasoning about how to achieve the maximum asynchrony in the network (rather than waiting for explicit instructions at every operation or attempts to make everything proceed in lockstep). The best reference to date on RuleSets is Takaaki's master's thesis or our PRA paper on the topic.
I believe this RuleSet-based approach meshes will with the vision of QRNA. Indeed, when combined with a rewrite engine at network borders, as described above, it should serve well as an instantiation of QRNA.
All right, that actually handles point five, as well; RuleSets and any qubits at the nodes that are currently assigned to a particular connection, well, that's connection state at each repeater/router. The scalability of this needs to be assessed, but I don't see a way around it right now.
(n.b.: as a network architecture aside, for the foreseeable future, there won't be any high-performance links; they'll all be low performance. Therefore, there won't really be backbone, long-haul, high-bandwidth links, either; the network topology is going to have to be richer. So there might not be huge numbers of connections passing through individual routers, anyway.)
So, point six, how do we set up connections...our approach is to use a two-pass system. On the outbound leg (starting, appropriate enough, at the Initiator), you collect information about links and available resources. The connection request eventually reaches the Responder, which takes that information and builds RuleSets for everyone along the path. Those RuleSets are then distributed in a return pass, then the operation for the connection begins.
This has a few interesting points: a. it limits the amount of information each node has to have on hand about the entire network, b. it allows Responders to innovate (within the bounds of the RuleSet architecture), and c. it will work well with the border rewrites necessary for QRNA.
I have presented this approach in any number of talks (see, oh, for example, my 2020 virtual talk at Caltech -- there is a video file there as well as PDF of my slides), but so far it's only written down in an expired Internet Draft that I hope to revive, and in some of the documentation on our Quantum Internet Simulation Package (QuISP).
Which brings us to point seven...how to pick a route. Quite some time ago, we investigated a variant of Dijkstra's algorithm, which we inventively call qDijkstra. We define link cost as "seconds per Bell pair of some index fidelity," e.g., seconds to make a Bell pair of e.g. F=0.98. Including fidelity in the metric makes a lot of sense; a high data rate but with poor fidelity may be less useful than one with a lower rate but higher fidelity. Thus, if your base fidelity is poor, you have to take into account purification, which automatically reduces throughput by half and more likely by 3/4 or more. We compared (via simulation) the throughput of various paths with heterogeneous links, and found a good correlation with our calculated path cost. Fidelity is actually too simple a metric, so the correlation isn't perfect, but we think it's good enough.
The biggest open question here -- and one of the things we are investigating -- is how to combine path selection with multiplexing/resource reservation.
Whew...let's see, we covered multipath above when talking about connections, so we're set there.
Bringing us to point nine, network security: in fact, we are the only group in the world looking at security of network operations for quantum repeaters. But this doesn't mean at all that we have a complete plan for secure operation of the Quantum Internet. Fairly obviously, all of the protocols we've talked about above need authentication and tamper resistance; whether privacy is also required or useful is an open question. Given the previous Internet (and, to a lesser extent, telephone network) experiences with lack of security in routing, accounting, DoS, etc., and the likely high cost of quantum connections, it seems pretty imperative to have a solid framework in place very early in the Quantum Internet, basically well before we have a truly operational network. And, this ties into the muxing decisions as outlined above -- you can't have accounting and authorization without authentication.
Whew, that's a lot of decisions, and lays out a lot of work to do. And we haven't even addressed some important topics, like naming.
If you can't carry all that in your head, just remember the three critical points: a recursive architecture for internetworking, RuleSet-based connection operation, and a two-pass connection setup routine (outbound info collection, inbound RuleSet distribution).
And although there is solid work on routing and multiplexing, designing a system that will be robust at scale and that will serve us well for decades is a big, open issue.
