[Qirg] Is segment routing a good fit for quantum networks?

[Bruno Rijsman <[e-mail]>]

SEGMENT ROUTING
===============

During the QIRG meeting I promised to send an e-mail to document my opinion on the (non-)applicability of segment routing to quantum networks.

TL;DR: In my opinion, segment routing is not a natural fit for quantum networks for three main reasons. (1) Qubits don't have headers, so they cannot carry a stack of SIDs with them. (2) It is not correct to think of qubits as being sent across the network using hop-by-hop forwarding. Thus the model of popping a SID at each hop to decide the next hop is not a natural fit. (3) Signaled circuits is a better model for quantum networking because of the resource constraints and more complex and stateful processing rules at each hop.

INTRO
-----

First, a *very* brief (and hence somewhat simplified) introduction to segment routing for those not familiar with it.

Consider the following network topology (use fixed-width font to see figures):

                   +----+    +----+
             +-----|LSR2|----|DST1|
             |     +----+    +----+
             |
+----+    +----+
|SRC |----|LSR1|
+----+    +----+
             |
             |     +----+    +----+
             +-----|LSR3|----|DST2|
                   +----+    +----+

SRC = Source
DST = Destination
LSR = Label Switched Router

In traditional MPLS (Multi-Protocol Label Switching) using LSPs (Label Switched Paths, think of them as circuits), each LSR has one in-label and an out-label for each LSP.

Consider LSP1 = LSP from SRC to DST1
         LSP2 = LSP from SRC to DST2

The MPLS forwarding tables will look as follows:
    
                 In-label 10: Swap 11, DST1
                     .
LSP1: Push 10, LSR1  .     In-label 11, Pop
LSP2: Push 20, LSR1  .         .
  .                  .         .
  .                  v         v
  .                +----+    +----+
  .          +-----|LSR2|----|DST1|
  .          |     +----+    +----+
  v          |
+----+    +----+
|SRC |----|LSR1|
+----+    +----+
           ^ |
           . |     +----+    +----+
           . +-----|LSR3|----|DST2|
           .       +----+    +----+
           .         ^         ^
           .         .         .
           .         .     In-label 21: Pop
           .         .
           .     In-label 20: Swap 21, DST2
           .
       In-label 10: Swap 11, LSR1
       In-label 20: Swap 21, LSR2

Note 1: I have chosen MPLS labels that are globally unique to make the example easy to understand, but in real life the MPLS labels are only locally significant, so the same MPLS label value can and typically is re-used by multiple LSRs.

Note 2: To keep things simple, I have ignored an optimization called Pen-ultimate Hop Popping (PHP).

The network is "aware" of each LSP, in the following sense:

(1) There is one entry in each MPLS forwarding table for each LSP. If there are N LSPs in the network, then there are N entries in the MPLS forwarding table. The number of LSPs can be very large. For example, in some use cases N = E^2 where E is the number of edge routers in the network (full mesh of LSPs from every edge router to every other edge router). This can make the MPLS forwarding tables very large.

(2) The signaling protocol, e.g. RSVP-TE, is aware of each LSP and populates the MPLS in-labels and out-labels for each LSP in each LSR on the path of the LSP. Since the number of LSPs can be large, the signaling load on RSVP-TE can be very heavy.

(3) When the application sends traffic, it can only send the traffic into an existing LSP. Thus, when an application wants to send traffic to DST3, it is necessary that an LSP to DST3 is first signaled. Furthermore, the application cannot directly influence the route that the traffic to DST3 follows. It simply follows the route that was chosen by the path computation function (e.g. CSPF = Constrained Shortest Path First) when the LSP was established.

Now, consider the same topology with segment routing.

Here, each LSR allocates one MPLS in-label for each neighbor (as opposed to one in-label for each LSP that goes through the LSR):

The MPLS forwarding tables will look as follows:
    
                 In-label 20: Pop, SRC
                 In-label 21, Pop, DST1
                     .
                     v
                   +----+    +----+
             +-----|LSR2|----|DST1|
             |     +----+    +----+
             |
+----+    +----+
|SRC |----|LSR1|
+----+    +----+
           ^ |
           . |     +----+    +----+
           . +-----|LSR3|----|DST2|
           .       +----+    +----+
           .         ^
           .         .
           .     In-label 30: Pop, SRC
           .     In-label 31: Pop, DST2
           .
       In-label 10: Pop, SRC
       In-label 11: Pop, LSR2
       In-label 12: Pop, LSR3


When SRC wants to send a packet to DST1, it constructs a packet with the following MPLS label stack and sends it to LSR1:

+----+----+---------+
| 11 | 21 | Payload |
+----+----+---------+

 (1) When LSR1 receives the packet, it looks at the outermost label 11. The MPLS forwarding table says: Pop and send to LSR2.

At this point the packet looks like this:

+----+---------+
| 21 | Payload |
+----+---------+

(2) When LSR2 receives this packet, it looks at the outermost label 21. The MPLS forwarding table says: Pop and send to DST.

At this point the packet looks like this:

+---------+
| Payload |
+---------+

(3) Now DST receives the packet as intended. The MPLS label stack has already been "consumed".

As you can see, this is a flavor of "source routing" where the source SRC encoded the desired route of the individual packet into the header of the packet in the form of an MPLS label stack.

As the packet is being forwarded through the network on a hop-by-hop basis, each LSR on the route "peels off" (= Pops) one MPLS label to decide what to do next with the packet.

Note: I am glossing over some technical details that the things in the stack on the packet are actually called SIDs and could be IPv6 headers instead of MPLS labels as well.

We can see some clear differences:

(1) The MPLS forwarding table only contains one entry per direct neighbor. This scales with the number of interfaces (tens, hundreds at most) instead of the number of LSPs (potentially tens of thousands or even more). Thus, the MPLS forwarding tables are smaller.

(2) We don't need to signal LSPs before sending packet. The application just sends each packet without having to signal an LSP first.

(3) The application is in full control of the route that each individual sent packet takes. The sending application can encode the desired route into the MPLS label stack that is pushed on the individual packet.

The application needs to know the topology of the network and needs to know which MPLS label each LSR has assigned to each neighbor. To achieve this, the standard routing protocols OSPF, ISIS, etc. have been extended to carry these label bindings. Note that the routing protocol load is constant, and does not depend on the traffic patterns (we are not signaling LSPs).

Note: I am glossing over some technical details where the application doesn't need to know every single hop in the topology, but can do the equivalent of "loose source routing" where it only sets "waypoints" that need to be visited by the packet.

Note: I am also glossing over some technical details where a MPLS label could be used to indicate other behaviors in addition to "send to neighbor".

APPLICABILITY TO QUANTUM NETWORKS
---------------------------------

My assessment is that segment routing is not a natural fit for quantum networks for the following reasons.

(1) Qubits do not have headers. Thus, we cannot push a stack of MPLS labels (or some other flavor of SID) onto each qubit.

(2) It is not a good mental model to think of qubits as being forwarded hop-by-hop over a quantum network. As Rodney likes to say, a better model is to think of quantum networks as performing a distributed computation that produces Bell pairs at the end points, that are consumed by (e.g.) teleportation. Thus, the segment routing model (where each packet contains an MPLS label stack that is processed hop-by-hop as the packet travels through the network, popping labels along the way to determine the nexthop) is not appropriate.

(3) Quantum networks, at least for the foreseeable future, will be extremely resource constrained. Furthermore, processing at each hop will be much more elaborate than just doing a stateless lookup in a forwarding table. Thus, IMHO, a protocol that explicitly signals a path for each quantum circuit and explicitly allocates resources and programs "rules" for that circuit is more appropriate than the fully stateless "the network is not aware of the circuit" model of segment routing. Such a protocol will, IMHO, look very similar to RSVP-TE. Indeed, the protocol outlined in Rodney's quantum-connection draft does have strong similarities to RSVP-TE.

To remedy issue (1) we could potentially come up with some scheme where each qubit is somehow accompanied by a classical packet that carries the MPLS label stack on behalf of the qubit. That seems non-trivial, and it still does not fix issues (2) and (3).

I am not ready to say that segment routing is "impossible" for quantum networks, but at first sight at least, it does not seem like a natural fit.

-- Bruno