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

[Bruno Rijsman <[e-mail]>]

Ah, I (finally) get it (I think).

Sorry for the coin being so slow to drop.

I totally agree with you.

So, yes, in Rodney's protocol it would be good to be able to use a computed path instead of always simply following the Dijkstra path.

And, yes, once we have chosen a path, we need some mechanism to force the PathSetupRequest (classical) messages to follow the chosen path and to force the PathSetupResponse (classical) message to follow the chosen path in reverse.

RSVP uses a very non-elegant mechanism for that (ERO object in combination with the IP router alert option).

Segment Routing would be a more elegant solution for that, although it assumes that the network supports segment routing (whereas the RSVP approach only assumes IP is supported).

-- Bruno


> On Nov 21, 2019, at 12:18 PM, Gelard Patrick <[e-mail]> wrote:
> 
> Yes i am agree with what you wrote, but as I have already said the objective isn’t to use SR routing  + PC to distributed Bell Pair  on the Quantum plane !!! but to used it (SR + PC) instead of Dijkstra’s algorithm (Proposed by Rodney et al. https://arxiv.org/pdf/1206.5655.pdf <https://arxiv.org/pdf/1206.5655.pdf>) to build and select a classical path to which the QR are attached.
>  
> /Patrick
>  
> De : Bruno Rijsman <[e-mail] <mailto:[e-mail]>> 
> Envoyé : jeudi 21 novembre 2019 12:00
> À : Gelard Patrick <[e-mail] <mailto:[e-mail]>>
> Cc : [e-mail] <mailto:[e-mail]>
> Objet : Re: [Qirg] Is segment routing a good fit for quantum networks?
>  
> Okay, now I understand the point that you are making.
>  
> And yes, in a classical network is very attractive that the computed path can be encoded into the packet itself without the need for any a-priori signaling of per-circuit state in the network itself.
>  
> There are a few complications that make it difficult to apply the segment routing paradigm to quantum networks.
>  
> Complication 1: Different model
>  
> In classical networks, packets are forwarded hop-by-hop across the network, from source S across some routers R1, R2, R3, ..., Rn to destination D. Each router R does a lookup to decide what to do next.
>  
> In classical segment routing, source S encodes the path into the packet using a label stack. And each router R pops a label off the stack to decide what to do next.
>  
> Quantum networks use a completely different model.
>  
> Adjacent routers R1-R2, R2-R3, etc. create link-local Bell pairs. Then the routers perform a distribution computation (swaps, distillations) to combine these link Bell pairs into end-to-end S-D Bell pairs.
>  
> The application then consumes these end-to-end Bell pairs at S and D, for example to teleport an arbitrary qubit.
>  
> Thus, to summarize, in the classical world, the application gives a packet to the network which is then transported. But in quantum world, the network produces end-to-end Bell pairs, which are then given to the application that consumes them.
>  
> [PG] Yes i am agree, but the objectif is to use PC + SR
>  
> Complication 2: Distributed computation
>  
> The distributed computation is a complex multi-step stateful process that is subject to very tight timing constraints. 
>  
> The involved routers need to run some sort of signaling protocol to agree on where the Bell pairs need to be produced exactly, what the characteristics of the Bells pairs are (e.g. fidelity), how often they need to be produced (how many Bell pairs per second), how they are going to be produced (what rules) given the capabilities of the router technology (how many qubits), etc.
>  
> Thus, it is a more natural model to signal the existence of a circuit from S to D a-priori, along with the desired parameters for that circuit (throughput in Bpps, fidelity, etc.)
>  
> Just before the circuit is signaled, the network chooses the "rules" for producing the necessary end-to-end entanglements at the right rate and fidelity.
>  
> And once the circuit has been signaled, the network goes about its business of actually producing the end-to-end entanglements by executing the chosen and signaled rules.
>  
> If we tried to apply a segment routing model to the quantum network, the application would give an individual request to the network, for example: "I want you to create an end-to-end entanglement from here (S) to there (D), I want you to use this path (R1-R2-R3-R4), and I want you to do it right now.”
>  
> The whole point of segment routing is that the network does not now what will happen next, until the next request actually comes down from the application.
>  
> Theoretically, the network could take this request and do all the necessary work on-the-spot, based on what in that particular individual request: create the link entanglements, swap them, distill them, etc.
>  
> In practice this is not possible because it is such a complex process and subject to such strict timing constraints that this cannot be done on-demand. If we did it on-demand, the original qubit to-be-teleported would have long de-cohered by the time the desired end-to-end Bell pair was in place.
>  
> Thus, the distributed computation has to be planned and scheduled in advance. This is a better match for the circuit model.
>  
> Complication 3: no header
>  
> The last complication is that qubits don't have headers into which we can encode a label stack.
>  
> This is the least of the complications, as I can imagine that we could create a "companion" classical packet that follows the qubit over the classical channel.
>  
> — Bruno
> 
> 
> On Nov 21, 2019, at 11:17 AM, Gelard Patrick <[e-mail] <mailto:[e-mail]>> wrote:
>  
> Hi,
>  
> Hi,
>  
> Yep, I understand that Path Computation can be build in a functional component (PCE : Path Computation Element) in an abstract architecture. RFC 4655 : It’s purpose is to determine paths through a network by taking into account Traffic Engineering (connectivity graph ; Node constraints and link constraints e.g metrics and capabilities ; Learned from the routing protocol in the network, or from the inventory database, or direct from the network nodes). 
>  
> The architecture model implementing the Path Computation Function may be centralized ( Centralized path computation : all path computations for a given domain are performed by a single, centralized PCE ) or distributed (Distributed path computation : multiple PCEs are deployed in a given domain. computation of paths is shared among those PCEs).  PCE function may be either standalone device(s) or embedded in some nodes. Indeed, the PCE can be located in a router, or more likely, it can be an off-network server
> The PCE collects and maintain the TE ( Traffic Engineering )  information in a dedicated TE ( Traffic Engineering ) Database (TED)  Now, PCE is not a centralized "all-seeing oracle in the sky"; It makes use of cooperative and distributed functionalities for TE information maintenance and computational ability.
>  
> However, Path Computation function relies on the existence forwarding paths across the network which can be build by Segment Routing for example. In this example PCE instruct ingress routers ( Unlike RSVP-TE based LSPs, in which the mid-points hold state, SR requires that only the ingress provider-edge holds state. For any transit or egress SR routers, any required state information is contained in the segment list. ) which paths to use through the network, and for which services.
>  
> This it seems to me that for quantum network, we effectively need a Path Computation function, but also a protocol that enables building the forwarding paths across the classical channel of the quantum repeater or router (QR) to apply the RuleSet in return (By following in return the path selected by the PCE). An while not using Segment Routing  for this role ?
>  
> While SR rather than RSVP-TE ? : Segment Routing provides the same ability as RSVP-TE to source route, but due to its lack of midpoint state, SR has significantly higher scaling properties than RSVP-TE. However, this same lack of midpoint
> state makes it impossible for the ingress LSR to compute a path through the network based on available bandwidth at intermediate hops. The increased scalability of SR together with the ability to signal a path based on bandwidth constraints means that the use of PCE has re-emerged as a viable proposition for large networks. (Refhttps://www.tmcnet.com/tmc/whitepapers/documents/whitepapers/2015/11525-segment-routing-path-computation-element-using-traffic-engineering.pdf <https://www.tmcnet.com/tmc/whitepapers/documents/whitepapers/2015/11525-segment-routing-path-computation-element-using-traffic-engineering.pdf> )
>  
>  
> QR have interfaces with Classical Channel (CC) and with Quantum Chanel (QC). The classical channel is used to transport the signaling of the control and management plan for the classic network itself  and for the quantum network.   
>  
>  
> /Patrick
>  
> De : Bruno Rijsman <[e-mail] <mailto:[e-mail]>> 
> Envoyé : mercredi 20 novembre 2019 16:19
> À : Gelard Patrick <[e-mail] <mailto:[e-mail]>>
> Cc : [e-mail] <mailto:[e-mail]>
> Objet : Re: [Qirg] Is segment routing a good fit for quantum networks?
>  
> Hi Patrick,
>  
> We absolutely definitely need a path selection function (= path computation function using classical terminology) in quantum networks.  
>  
> And yes, it very much needs to take the quantum equivalent of congestion into account (classical congestion = running out of buffer space, quantum congestion = running out of some quantum resource such as communication qubits or memory qubits, etc.)
>  
> I quickly scanned the Arxiv paper, and the suggested path computation algorithms seem to make sense at first blush.
>  
> But whether or not we need a path computation function is an orthogonal question to what abstraction we use for the forwarding plane (traditional LSPs? segment routing? something else?)
>  
> Both segment routing and “traditional” MPLS LSPs have a path computation function.
>  
> The path computation function doesn’t really know or care whether the forwarding plane uses segment routing or traditional MPLS LSPs.
>  
> The path computation as input: a network topology, the current available bandwidth, a traffic demand matrix (possibly in the form of a set of requested circuits) and then it computes the route (= path) for each requested circuit.
>  
> Once the path is computed, it gives the computed path to a magic black box that is responsible for “making it so”, i.e. for signaling the chosen path.
>  
> Once again, the path computation function doesn’t need to know or care how that happens: it could be RSVP to signal traditional LSPs, it could be segment routing to do it packet by packet, it could be OpenFlow or P4 to talk directly to the MPLS tables on each forwarding device, etc.
>  
> In fact, I know of at least one SDN controller that has two separate signaling modules (one for segment routing and one for traditional LSPs using RSVP) that share a common path computation module.
>  
> Hope that makes it more clear,
>  
> — Bruno 
> 
> 
> 
> On Nov 20, 2019, at 4:05 PM, Gelard Patrick <[e-mail] <mailto:[e-mail]>> wrote:
>  
> Hi Bruno,
>  
> Thank you for this overview on segment Routing.
>  
> >> 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.
>  
> …
>  
> I think many of us agree that segment routing isn’t applicable at the quantum plane of a quantum network.  As Diego recalls : “A quantum plane, that is the equivalent to a classical data plane. I think the differences here are big enough to use a different denomination.”
>  
> Now what about its use (With adaptations to be defined. Add metrics specific to quantum network) for the step  “ select a path (routing) https://arxiv.org/abs/1206.5655 <https://arxiv.org/abs/1206.5655>  ”  Reminded in Rodney's presentation (Slide 3)   https://datatracker.ietf.org/meeting/106/materials/slides-106-qirg-connection-setup-in-a-quantum-network <https://datatracker.ietf.org/meeting/106/materials/slides-106-qirg-connection-setup-in-a-quantum-network> ? There will also be congestion in the quantum repeater and thus a need of quantum traffic engineering to distribute the bell pair. 
>  
> Best regards
> Patrick
>  
>  
>  
> De : Qirg <[e-mail] <mailto:[e-mail]>> De la part de Bruno Rijsman
> Envoyé : mercredi 20 novembre 2019 12:02
> À : [e-mail] <mailto:[e-mail]>
> Objet : [Qirg] Is segment routing a good fit for quantum networks?
>  
> 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
>