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

[Gelard Patrick <[e-mail]>]

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. (Ref 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]>
Envoyé : mercredi 20 novembre 2019 16:19
À : Gelard Patrick <[e-mail]>
Cc : [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  ”  Reminded in Rodney's presentation (Slide 3)   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