[Qirg] a #QuantumInternet Architecture position paper

[Rodney Van Meter <[e-mail]>]

(Happy Mother’s Day to the mothers of all QIRGers, and to all QIRGers who are mothers!  Maybe I should wait until Monday to send this out, more likely to hit some eyeballs then…but what the heck, I just finished it, so here it is.)

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 a. the Quantum Recursive Network
Architecture (QRNA), b. RuleSet-based connections, c. a two-pass
connection setup mechanism, d. qDijkstra with seconds per Bell pair as
link cost for routing, and e. ??? for multiplexing.

Of course, a lot of this is covered in my book
(https://onlinelibrary.wiley.com/doi/book/10.1002/9781118648919,
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
https://aqua.sfc.wide.ad.jp/publication_en.html and
https://scholar.google.co.jp/citations?hl=en&user=-YlArkcAAAAJ&view_op=list_works
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:

1. the nature of the fundamental service: Bell pairs?  measured-out
   classical bits?  qubit teleportation? multi-party graph states?
2. how networks will come together to make an internetwork -- what is the
   nature of the interaction?  (affected strongly by connections, below)
3. 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?
4. nature of connections: entanglement swapping and purification (1G),
   or QEC (2G, 3G)? (affects internetworking)
5. both of the above points affect whether a connection requires state
   at each repeater/router
6. how connections are established
7. how a path or route is chosen through the network
8. all of the above affect choice of whether to try to do multipath for
   a single connection
9. 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:
https://datatracker.ietf.org/doc/draft-irtf-qirg-principles/

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 https://arxiv.org/abs/1105.1238
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.
https://spie.org/Publications/Proceedings/Paper/10.1117/12.893272
or
https://aqua.sfc.wide.ad.jp/publications/Aparicio-master-thesis.pdf

*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.
https://www.nature.com/articles/srep20463
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.
https://arxiv.org/abs/2102.04471 or https://science.sciencemag.org/content/372/6539/259)

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.
https://arxiv.org/abs/1508.04599

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:
https://arxiv.org/abs/1908.10758
or a PRA paper on the topic:
https://arxiv.org/abs/1904.08605

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.  When the connection request reaches the Responder, it
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, https://indico.hep.caltech.edu/event/837/?print=1 -- 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
(https://tools.ietf.org/html/draft-van-meter-qirg-quantum-connection-setup-01)
that I hope to revive, and in some of the documentation on our Quantum
Internet Simulation Package (QuISP).
https://github.com/sfc-aqua/quisp/tree/master/doc

Which brings us to point seven...how to pick a route.  We investigated
quite some time ago in
https://link.springer.com/article/10.1007%2Fs13119-013-0026-2 or
https://arxiv.org/abs/1206.5655 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.
https://arxiv.org/abs/2005.04617 and
https://arxiv.org/abs/1701.04587
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.

Rodney Van Meter
[e-mail]
Professor, Faculty of Environment and Information Studies, Keio University, Japan