Re: [Qirg] Similarities between RSVP IETF (RFC 2205) protocol and connection Setup in a Quantum Network

[Bruno Rijsman <[e-mail]>]

RSVP-TE AND GMPLS
=================

TL;DR: In my opinion the ideas in (G)MPLS and RSVP-TE are very applicable to quantum networks. At the very least we should use the concepts of (G)MPLS and RSVP-TE as inspiration for quantum networks. I think there might even be a possibility to extend the existing protocols / implementations for quantum networks.

SCOPE
-----

I want to start by being clear on the scope of applicability of (G)MPLS and RSVP-TE because there is some confusion about this on the mailing list.

I am *not* talking about using (G)MPLS and RSVP-TE to facilitate communication between the control plane on one quantum router and the control plane on another quantum router over the classical channel.

Indeed, for that we just need TCP/IP connectivity and any simple classical routing protocol (OSPF, ISIS, BGP, whatever) will do. We don't need anything complicated like (G)MPLS or RSVT-TE here.

What I am suggesting here is to use (G)MPLS and RSVP-TE or similar mechanisms to achieve the following:

(a) Compute the path for a quantum circuit over a sequence of quantum channels. I.e. what is the sequence of point-to-point link Bell pairs that we are going to "stitch together" (using swapping and distillation) to produce the desired end-to-end Bell pairs that are consumed by the application.

(b) Make sure that each end-to-end quantum circuit gets the required capacity in terms of Bell pairs per second (Bpps) and fidelity that is needed by the application. For that we need to "know" the capacity (in Bpps) of each individual link, we need to keep track of how much of that link capacity is already consumed by other circuits and how much remaining capacity is still available. We need to take the remaining capacity into account when we compute the 'best' path for each quantum circuit.

(c) Actually signal a quantum circuit once its path has been decided. We need to visit each quantum router on the path and install some state (Rodney calls it rules) that will cause the right sequence of actions (swaps, distillations, etc.) to happen at the right rate and under the right conditions to create the desired end-to-end quantum circuit.

INTRO
-----

First, a *very* brief (and hence somewhat simplified) introduction to RSVP-TE and GMPLS for those not familiar with it.

Consider the following example network topology:

 E1      R2----R3      E3
   \    /        \    /
    \  /          \  /
     R1            R5
    /  \          /  \
   /    \        /    \
 E2      +--R4--+      E4


E = End-point = Label Edge Router (LER) in MPLS terminology

R = Router = Label Switched Router (LSR) in MPLS terminology

Let's assume all links are 1 Gbps.

The job of RSVP-TE is to signal circuits from end-point to end-point. These circuits are called LSPs in MPLS terminology.

Each circuit can asks for a specific amount of bandwidth, and it is the job of RSVP-TE to signal a path that guarantees the requested bandwidth, or to deny the request if the bandwidth is not available (this is called call admission control, CAC).

Let's say we want to signal two circuits:

C1: E1->E3, 600 Mbps

C2: E2->E5, 700 Mbps

Let's say circuit C1 is established first [Note1].

The process of bringing circuit C1 up consist of the following steps:

* The ingress node E1 receives a request to establish a circuit of 600 Mbps to egress node E3.

* Ingress node E1 computes the optimal route for the circuit to E3 [Note2].

* In order to compute that path, E1 needs to know the full topology of the network. E1 uses a traditional link-state routing protocol such as OSPF or ISIS for that purpose. This is why we say that RSVP-TE needs a routing protocol.

* Not only that, E1 also needs to know how much bandwidth is still available on each link. For this reason both OSPF and ISIS have been enhanced with so-called traffic engineering (TE) extensions to flood not just the topology, but also the available bandwidth. This is called OSPF-TE and ISIS-TE.

* Given the topology and the bandwidth information for the whole network, ingress node E1 can compute the optimal path using the so-called constrained shortest path first (CSPF) algorithm.

* In this case the optimal path is E1 -> R1 -> R4 -> R5 -> E3

* Now that the so-called "path computation" function has been performed, it is time to actually signal the path. This is where RSVP-TE comes in.

* E1 takes the computed route, gives it to RSVP-TE as an explicit route object (ERO) and asks RSVP-TE to signal the path.

* RSVP-TE sends PATH messages, following the computed route in the ERO hop-by-hop, towards egress node E3. Then RSVP-TE sends RESV messages, following the computed route hop-by-hop in reverse, back to ingress node E1. The net result of this signaling is that the circuit is installed. All the necessary state (in this case MPLS label swaps) is installed on each router on the path.

* The installation of the end-to-end circuit has consumed some of the bandwidth on the network: we have consumed 600 Mbps out of the available 1 Gbps on links E1-R1, R1-R4, R4-R5, and R5-E3. Thus, we have 400 Mbps remaining on this link. OSPF-TE or ISIS-TE floods this information across the entire network.

Now let's say that we signal circuit C2 (E2->E4) next.

This follows the exact same sequence of steps as described above, with one difference.

When E2 computes the path by running the CSPF algorithm, it will detect that the shortest path E2->R1->R4->R5->E4 no longer has the required bandwidth of 700 Mbps available. For that reason, it will choose the longer path E2->R1->R2->R3->R5->E4.

Everything that I have described so far assumes that we are running an MPLS network, where we are forwarding data packets, namely MPLS packets. When RSVP-TE signals the end-to-end circuit, it allocates in-labels and out-labels on each hop, and it installs the circuit by populating MPLS swaps, pushes, and pops into the MPLS forwarding tables.

There is a generalization of MPLS which is called generalized MPLS (GMPLS).

In GMPLS, we use the same control plane (OSPF-TE/ISIS-TE + RSVP-TE) for a network that is not an MPLS network, or not even a packet switched network.

GMPLS is used for example for:

* Time division multiplexed networks (TDM) to compute the path for TDM circuits and to install the path by creating time-slot cross connects on the TDM switches.

* Optical transport networks (OTN) to compute the path for optical circuits in dense wavelength division multiplexed (DWDM) networks and to install the path by creating wavelength cross-connects using MEMS switches.

Finally, everything I have described so far assumes that the path computation is computed by the head-end of the circuit (which is what is considered a "distributed" control plane in MPLS networks). There is another model where a centralized path computation element or SDN controller is used to compute the path.

There are two sub-variations of that centralized model. In one variation the centralized controller talks to only to the head-end of the circuit, which then uses RSVP-TE (using the ERO provided by the controller) to install the path. In the other variation, the centralized controller talks directly to each router on the path (using OpenFlow or P4 or something similar) to install the circuit.

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


I thinks the (G)MPLS and RSVP-TE model is very applicable to quantum networks for the following reasons:

(1) It is not accurate to think of quantum networks in the same manner as a normal packet forwarding network. We are not forwarding a packet hop-by-hop, doing a lookup in a forwarding table to decide at each hop where we go next. As has been pointed out, a quantum network is more like a distributed computation where the quantum routers cooperate to produce end-to-end Bell pairs at the desired end-points at the desired rate. A "circuit" is a much more natural abstraction for this. An application could request that the quantum network creates a "circuit" from A to Z, and produces X bell pairs per second at fidelity Y at A and Z.

(2) Quantum networks will, at least initially, be extremely resource constrained. The capacity of links, in terms of Bell pairs per second, will be extremely limited. This a traffic engineering function where we keep track of the available and consumed resources will IMHO be essential.

(3) The state that is installed in each quantum router to implement a quantum circuit is much more complicated than a simple IP forwarding table entry or a simple MPLS forwarding table entry. It is much more akin to the complex rules that Rodney alludes to in his draft. I foresee a much more sophistical mechanism for distributing information about the network. Not only do we need to know the remaining available bandwidth, but also other constraints (e.g. available quantum memory) and attributes (e.g. is swap deterministic or not). I also foresee a much more sophisticated path computation function that only understands topology and resource available to compute the 'best' path, but that also understands the non-linear effects in quantum networks (e.g. non-linear slowdown of Bell pair rate as the circuit gets longer due to increased need for distillation etc.) For that reason, I think a centralized controller will make more sense, at least initially.

(4) MPLS has already been generalized into GMPLS to control non-packet-switched networks, such as TDM or OTN networks. These generalizations can be used to control quantum networks.

NOTES
-----

[Note 1] The fact that we are signaling circuits sequentially means that we are doing a greedy local optimization. There are alternative approaches, which are even more applicable to quantum networks, where the path computation is done by a centralized path computation element (PCE), or software defined networking (SDN) controller. This allows the path computation function to use more sophisticated algorithms and obtain a global optimum rather than a local greedy optimum. This approach is particularly useful in optical transport networks (OTN) where the optimization has to take all sorts of non-linearities into account (e.g. fiber losses). I think we are in a similar situation with quantum networks.

[Note 2] In the model alluded to in [Note 1] the path computation would be done by the centralized controller, instead of the ingress node. IETF has actually standardized a protocol between the ingress node and the controller specifically for this purpose. It is called the path computation element protocol (PCEP).

[Note 3] I plan to contribute a much reduced and summarized version of this as the MPLS section for the architectural principles draft.

— Bruno

> On Nov 20, 2019, at 12:26 PM, Dino Farinacci <[e-mail]> wrote:
> 
> I think you don’t need any of these mechanisms. If you look at the follownig topologies, all you need is for the the two QRs to talk to each other. They are nothing more than two hosts on an IP network connected via two CRs:
> 
> QR —— CR ——- CR —— QR
> 
> It is overkill to use RSVP and SR. They are protocols to route packets. If you use SR, you don’t need to construct a path between two QRs. All the QRs need to do is talk to each other. And you can pair up QRs with an app level path mechanism.
> 
> Dino
> 
>> On Nov 20, 2019, at 3:57 PM, Gelard Patrick <[e-mail]> wrote:
>> 
>> Hi dino,
>> 
>> In the text.
>> 
>> /Patrick
>> 
>> De : Dino Farinacci <[e-mail]> 
>> Envoyé : mercredi 20 novembre 2019 04:12
>> À : Gelard Patrick <[e-mail]>
>> Cc : [e-mail]; Frédéric Grosshans <[e-mail]>; Rodney Van Meter <rdv=[e-mail]>
>> Objet : Re: [Qirg] Similarities between RSVP IETF (RFC 2205) protocol and connection Setup in a Quantum Network
>> 
>> Note for RSVP to work as you describe, you need a multicast source-based distribution tree set up prior to any Path message sent. 
>> [PG]Yes, This is what I mention when I write “RSVP is not a routing protocol. It must be integrated with routing”.  Just as for the point to point where a path must first be established. Just as for the establishment of quantum network connection as recalled in Rodney's presentation : Stages of the Problem!•Need to select a path (routing) https://arxiv.org/1206.5655
>> 
>> Note that the key issues of Inserv and RSVP is scaling.
>> For point-to-point, there is also a scaling problem for its use in traffic engineering of the MPLS protocol (RSVP-TE : describes the use of standard RSVP [RFC2205] to  establish Label Switched Paths (LSPs)). Moreover, concerning the traffic engineering of MPLS, the per-connection traffic steering model of MPLS-TE does not easily exploit the load balancing offered by Equal Cost MultiPath (ECMP) routing in plain IP networks. In addition to other problems, this led IETF (SPRING) to define the concept of “segment Routing” (SR :  https://tools.ietf.org/html/rfc8402 ) ;  A concept that can be useful in establishing the path selecting quantum repeaters.
>> 
>> The Segment Routing offers an innovative and simple approach to enable traffic engineering. Additional information is simply placed in the packets that will condition their processing: a list of segments is added in each datagram and defines the network path that must be used. Segment Routing thus offers a very simple option for the implementation of traffic engineering without the need for additional states on the equipment, which allows to add a large number of rules without overloading the routers and complicating the infrastructure operation. The SR architecture can leverage both distributed and centralized network control paradigms to provide efficient network solutions, and thus in a centralized network control the programmability from controllers, which is a prerequisite for SDN infrastructures.
>> 
>> Good entry point for SR : “Segment Routing: a Comprehensive Survey of Research Activities, Standardization Efforts and Implementation Results” https://arxiv.org/abs/1904.03471 
>> 
>> 
>> And Path message refreshes happen to new receivers when new branches are formed on the multicast distribution tree. 
>> 
>> And also note that quantum repeaters are not likely to be deployed initially on the same sides of a classical channel. What I mean is you could have this topology:
>> 
>> QR —— CR ——- CR —— QR
>> 
>> where CR is a classical router and entanglement swapping happens by each QR. 
>> [PG]CR could be in path of the control plan of quantum network, but not in the data plane (i.e quantum channel). It should be noted that can use also quantum channel to encode classical information (bits. For example dense coding) and thus to transport the control plan
>> 
>> Dino
>> 
>> 
>> On Nov 19, 2019, at 8:40 PM, Gelard Patrick <[e-mail]> wrote:
>> 
>>  
>> Hi all,
>> 
>> There are similarities between  RSVP  IETF (RFC 2205) protocol and connection Setup in a Quantum Network ( https://tools.ietf.org/html/draft-van-meter-qirg-quantum-connection-setup-00 ) even if the goal isn’t the same.
>> 
>> - RSVP was designed independently of any network architecture offering a QoS such as IntServ for example. It is RFC 2210 that defines how to implement the Qos of the IntServ architecture using the RSVP protocol / the setup connection must also be independent of any quantum network architecture
>> - Reservation at the request of the receiver like setup connection which use the recipient to establish rules and Bell pairs distribution
>> - RSVP is not a routing protocol. It must be integrated with routing and admission control functions. Connection Setup also needs the support of a routing protocol to reach the receiver.
>> 
>> 
>> <image001.jpg>
>> 
>> Messages :
>> 
>> Path: setting the path (logical state).
>> Resv: reservation request.
>> ResvTear: deletes the reservation status
>> PathTear: clears the path state.
>> ResvErr: reservation error,
>> PathErr: path error.
>> ResvConf: reservation confirmation.
>> 
>> <image004.jpg>
>> 
>> /Patrick
>> 
>> -----Message d'origine-----
>> De : Qirg <[e-mail]> De la part de Frédéric Grosshans
>> Envoyé : mardi 12 novembre 2019 12:50
>> À : Patrick Gelard <[e-mail]>; [e-mail]; Gelard Patrick <[e-mail]>
>> Objet : Re: [Qirg] Multipatite entanglement
>> 
>> Hi Patrick,
>> 
>> Le 11/11/2019 à 09:04, Patrick Gelard a écrit :
>>> Now regarding the control plan for deploying such a service, he seems
>>> to me that one of the questions is: should we develop a new control
>>> plan or adapt some traditional network control plans (e.g Resource
>>> Reservation Protocol (RSVP) Mulicast ; SDN ; etc.) that could do the job?
>>> 
>> My problem with this is that I’m a physicist with a really elementary knowledge (if any!) of network protocols. For example, in the theoretician’s protocol we designed with Clément Meignant and Damian Markham, [arXiv:1811.05445 https://arxiv.org/abs/1811.05445],a key ingredient of GHZ state generation (which is a primitive for the following) is to find a subtree of the network linking the end-nodes. 
>> The operation on nodes of the tree are then local, and look a bit like entanglement-swapping for a repeater line, bit on a tree.
>> 
>> I guess the control plan would look a lot like the one for multicast, but it‘s pure speculation from me.
>> 
>> 
>> Cheers,
>> 
>>        Frédéric
>> 
>> _______________________________________________
>> Qirg mailing list
>> [e-mail]
>> https://www.irtf.org/mailman/listinfo/qirg
>> _______________________________________________
>> Qirg mailing list
>> [e-mail]
>> https://www.irtf.org/mailman/listinfo/qirg
> 
> _______________________________________________
> Qirg mailing list
> [e-mail]
> https://www.irtf.org/mailman/listinfo/qirg