Subject: [6tsch] PCEP for centralized scheduling in 6TSCH architecture

From: Maria Rita PALATTELLA <[email-masked]>
Date: Tue, 30 Apr 2013 08:53:26 +0000

Dear all,
I have started investigating the RFC5440 "Path Computation Element Communication Protocol (PCEP)" in order to check " if" and "how" it could fit in our 6TSCH architecture.
In detail, I wanted to see if we could use PCEP + TASA (Traffic Aware Scheduling Algorithm) for computing and distributing the schedule from the PCE to the nodes in a 6TSCH architecture that uses a centralized scheduling algorithm.
I had some preliminary discussion already with Thomas on this topic, but let's discuss all together on the ML. We would like to have your feedback in order to see if we can really use PCEP, and how we can fix some open issues in the 6TSCH context.
I will use some extracts from the RFC5440, that summarize the behavior of the protocol, and show features that we could exploit.
This will result in a *very long* email. Sorry for that. And thanks for going through it, and come back to me with your comments, questions, suggestions.
Maria Rita

>>PCEP is such a protocol designed specifically for communications between a PCC and a PCE [...] a PCC may use PCEP to send a path computation request for one or more TE LSPs to a PCE, and the PCE may reply with a set of computed paths if one or more paths can be found that satisfies the set of constraints.
>> PCC:  Path Computation Client; any client application requesting a path computation to be performed by a Path Computation Element.
>> PCE:  Path Computation Element; an entity (component, application, or network node) that is capable of computing a network path or route based on a network graph and applying computational constraints.
>> Explicit path:  Full explicit path from start to destination; made of a list of strict hops where a hop may be an abstract node such as an AS.
 [MR] The explicit path could be seen as a 6TSCH track, composed by hard cells.

>> [...] it is assumed that the PCE has the required information (usually including network topology and resource information) so as to perform the computation of a path for a TE LSP.  Such information can be gathered by routing protocols or by some other means.  The way in which the information is gathered is out of the scope of this document (i.e, RFC5440).
 [Thomas] Is that not a bit limiting? This means that we need one protocol (PCEP) to send data from the PCE to the motes, and another for stats and topological and requirement data to go from the motes to the PCE.
 [MR] Yes, it is. Like 15.4e TSCH that uses a schedule but it doesn't specify how to build and distribute it, PCEP does not define how to collect the required information (network topology, requirements) used for computing paths. But the motes can specify the requirements of the requested path within the PCReq messages.

>>  Transport Protocol. PCEP operates over TCP using a registered TCP port (4189). This allows the requirements of reliable messaging and flow control to be met without further protocol work. All PCEP messages MUST be sent using the registered TCP port for the source and destination TCP port.
 [Thomas] can PCEP run on something else than TCP? It looks like no. There is always the possibility for proposing a UDP version of PCEP, but it's unclear to me how much rework is required.
[MR] According to the RFC5440, a PCEP session can be established ONLY  over a  TCP connection. In other words, first a TCP connection (3-way handshake) between the PCC and the PCE has to be established, and after a PCEP session can be started. About proposing an UDP version of PCEP, it is something to be investigated.

>> Once the PCC has selected a PCE, it sends a Path Computation Request to the PCE (PCReq message) that contains a variety of objects that
specify the set of constraints and attributes for the path to be computed.  For example, "Compute a TE LSP path with source IP address=x.y.z.t,
 destination IP address=x'.y'.z'.t', bandwidth=B Mbit/s, Setup/Holding priority=P, ...".  Additionally, the PCC may desire to specify the urgency
 of such request by assigning a request priority.

[Thomas]If the PCE received a PCReq to go from A to B, is there a way for the PCE to contact all the motes along the multi-hop path between A and B and
install cells/links? it looks like the PCE is only used to calculate a multi-hop path on an already existing topology.
[MR]I agree with you. PCEP can set up a multi-hop path on an already existing topology. There is correspondence 1-to-1 between PCReq and PCRep. Thus, it seems that PCE cannot contact the motes along the multi-hop path between A and B. BUT... PCEP include some RP in the messages (see below)
 >>A Path Computation Reply(PCRep) Message can contain either a set of computed paths if the request can be satisfied, or a negative reply if not.  The negative reply may indicate the reason why no path could be found.
>>The RP (Request Parameters) object MUST be carried within each PCReq and PCRep messages. The RP object is used to specify various characteristics of the path computation request.
 >> The END-POINTS object is used in a PCReq message to specify the source IP address and the destination IP address of the path for which a path computation is requested. Note that the source and destination addresses specified in the END-POINTS object may correspond to the source and destination IP address of the TE LSP or to those of a path segment.
 [MR] Setting the END-POINT object, maybe it could be possible to allocate cells/links for each path segment. This is something to be investigated.
 >>The BANDWIDTH object is used to specify the requested bandwidth for a TE LSP. The notion of bandwidth is similar to the one used for RSVP >>signaling in [RFC2205], [RFC3209], and [RFC3473].
 >>The METRIC object is optional and can be used for several purposes. In a PCReq message, a PCC MAY insert one or more METRIC objects:
 o To indicate the metric that MUST be optimized by the path computation algorithm (IGP metric, TE metric, hop counts).
Currently, three metrics are defined: the IGP cost, the TE metric (see [RFC3785]), and the number of hops traversed by a TE LSP.
 o To indicate a bound on the path cost that MUST NOT be exceeded for the path to be considered as acceptable by the PCC.
 >>The path computation algorithmic aspects used by the PCE to optimize a path with respect to a specific metric are outside the scope of this >>document.
[MR] TASA could be a possible algorithm for computing the path. It seems to fits well with the RFC5440 Specification.

TASA provides a method to the PCE for computing a network path, based on the network graph and applying computational constraints (i.e., selecting duplex- and
interference-free conflict links, according to local and global queue level).
Each node in the TSCH TASA-based network could act as PCC (Path Computation Client), requesting a path computation to be performed by the PCE. In detail, with the PCReq message,
the PCC asks the PCE to compute a path toward it (thus, source IP address = PCC IP address, destination IP address = PCE destination address), having a  given bandwidth, equal to the number of packets it wants to transmit (i.e., TASA local queue level, or  in other word, traffic load offered by the single node to the network).
After having collected all the PCReq messages from all the nodes in the network, the PCE can build a schedule, setting one or more paths for each PCC.
Once, the schedule has been built according to TASA matching and coloring procedures, it is transmitted to each node in the network, using PCRep messages.
Then, the 6TSCH 6TUS adaptation protocol can provide the functionality for delivering the traffic in the queues, according to the schedule built with TASA+PCEP.

Some Open ISSUES:

Q1: How the PCE collect the information related to the network graph?
R1: Note that this is out of the scope of both RCF5440 and TASA. However, we may suppose that such information are provided by the routing protocol, RPL, as suggested in RFC5440.
"How" still has to be defined!
[Thomas] Agreed, that's a really important point.

Q2: How the network is set up before implementing TASA+PCEP for building the schedule?
R2: TASA does not specify how the network is built. In fact, TASA runs over a network that has been already built, and that needs a schedule in order
to allow traffic-flow exchanges (i.e., transmissions between each node and the PCE). Maybe, 6TUS could fill this gap and provide the functionality for the 15.4e TSCH network formation.

[Thomas] I believe the "minimal" use case identified in the charter covers this.

Q3: Is there any need to change the PCReq and PCRep messages format, for allowing the integration of PCEP with TASA?
[MR] there could be such need.

Q4:How the info in the PCRep messages can be used by 6TUS?

[Thomas] The entity in the motes which received PCRep message simply send commands over the 6tus interface.

Q5: How would a TASA+PCEP solution work for P2P traffic? That is, data flowing from a switch to a light without going through the DAGroot?
[MR]TASA supports multi-point-to-point traffic (from each mote in the network to the DODAGroot). PCEP support P2P traffic. TASA+PCEP maybe could support P2P traffic. This is something to be investigated.

---

From: Thomas Watteyne <[email-masked]>
Date: Tue, 30 Apr 2013 20:38:51 -0700

Maria Rita,

Awesome! Thanks for putting this on the ML.

One important step I think is to decide what we want the scope of this
protocol to be.

Here are a couple of thoughts on what the goals are (I'm at the airport, so
please forgive the not-so-organized nature of this e-mail):
- this is the protocol used for signalling messages to flow between the PCE
and the nodes in the network
- the nodes use this protocol (if possible) to tell the PCE how they are
doing. This includes topological information, traffic requirements, etc.
- what happens in the PCE is independent from this protocol,
- the PCE uses this protocol to drive the network schedule, installing and
moving tracks in the network, probably using mostly hard cells.

On top of this, I can think on the following requirements:
- reuse existing protocols and techniques as much as possible
- security: nodes and PCE should be able to authenticate each other. It
might also be useful to ensure confidentiality, so that a node can not
overhear the traffic between the PCE and another node.
- simplicity and applicability to out simple LLNs (i.e. small state, small
overhead,...)

Thoughts?

Thomas

On Tue, Apr 30, 2013 at 1:53 AM, Maria Rita PALATTELLA <
[email-masked]> wrote:

>  Dear all,****
>
> I have started investigating the* RFC5440 “Path Computation Element
> Communication Protocol (PCEP)” *in order to check " if" and "how" it
> could fit in our 6TSCH architecture. ****
>
> In detail, I wanted to see if we could use *PCEP + TASA (Traffic Aware
> Scheduling Algorithm) *for computing and distributing the schedule from
> the PCE to the nodes in a 6TSCH architecture that uses a centralized
> scheduling algorithm.    ****
>
> I had some preliminary discussion already with Thomas on this topic, but
> let's discuss all together on the ML. We would like to have your feedback
> in order to see if we can really use PCEP, and how we can fix some open
> issues in the 6TSCH context.****
>
> I will use some extracts from the RFC5440, that summarize the behavior of
> the protocol, and show features that we could exploit.****
>
> This will result in a *very long* email. Sorry for that. And thanks for
> going through it, and come back to me with your comments, questions,
> suggestions.****
>
> Maria Rita****
>
> ** **
>
> >>PCEP is such a protocol designed specifically for communications between
> a PCC and a PCE […] a PCC may use PCEP to send a path computation request
> for one or more TE LSPs to a PCE, and the PCE may reply with a set of
> computed paths if one or more paths can be found that satisfies the set of
> constraints.****
>
> >> PCC:  Path Computation Client; any client application requesting a path
> computation to be performed by a Path Computation Element.****
>
> >> PCE:  Path Computation Element; an entity (component, application, or
> network node) that is capable of computing a network path or route based on
> a network graph and applying computational constraints.****
>
> >> Explicit path:  Full explicit path from start to destination; made of a
> list of *strict hops* where a hop may be an abstract node such as an AS.**
> **
>
>  [MR] The explicit path could be seen as a 6TSCH track, composed by hard
> cells.****
>
>  ****
>
> >> […] it is assumed that the PCE has the required information (usually
> including network topology and resource information) so as to perform the
> computation of a path for a TE LSP.  Such information can be gathered by
> routing protocols or by some other means.  The way in which the information
> is gathered is out of the scope of this document (i.e, RFC5440). ****
>
>  [Thomas] Is that not a bit limiting? This means that we need one
> protocol (PCEP) to send data from the PCE to the motes, and another for
> stats and topological and requirement data to go from the motes to the PCE.
> ****
>
>  [MR] Yes, it is. Like 15.4e TSCH that uses a schedule but it doesn’t
> specify how to build and distribute it, PCEP does not define how to collect
> the required information (network topology, requirements) used for
> computing paths. But the motes can specify the requirements of the
> requested path within the PCReq messages. ****
>
>  ****
>
> >>  Transport Protocol. PCEP operates over TCP using a registered TCP port
> (4189). This allows the requirements of reliable messaging and flow control
> to be met without further protocol work. All PCEP messages MUST be sent
> using the registered TCP port for the source and destination TCP port.****
>
>  [Thomas] can PCEP run on something else than TCP? It looks like no.
> There is always the possibility for proposing a UDP version of PCEP, but
> it's unclear to me how much rework is required.****
>
> [MR] According to the RFC5440, a PCEP session can be established ONLY
> over a  TCP connection. In other words, first a TCP connection (3-way
> handshake) between the PCC and the PCE has to be established, and after a
> PCEP session can be started. About proposing an UDP version of PCEP, it is
> something to be investigated.****
>
> ** **
>
> >> Once the PCC has selected a PCE, it sends a Path Computation Request to
> the PCE (PCReq message) that contains a variety of objects that
> specify the set of constraints and attributes for the path to be
> computed.  For example, "Compute a TE LSP path with source IP
> address=x.y.z.t,
>  destination IP address=x'.y'.z'.t', bandwidth=B Mbit/s, Setup/Holding
> priority=P, ...".  Additionally, the PCC may desire to specify the urgency
>  of such request by assigning a request priority.  ****
>
> ** **
>
> [Thomas]If the PCE received a PCReq to go from A to B, is there a way for
> the PCE to contact all the motes along the multi-hop path between A and B
> and****
>
> install cells/links? it looks like the PCE is only used to calculate a
> multi-hop path on an already existing topology.****
>
> [MR]I agree with you. PCEP can set up a multi-hop path on an already
> existing topology. There is correspondence 1-to-1 between PCReq and PCRep.
> Thus, it seems that PCE cannot contact the motes along the multi-hop path
> between A and B. BUT… PCEP include some RP in the messages (see below)****
>
>  >>A Path Computation Reply(PCRep) Message can contain either a set of
> computed paths if the request can be satisfied, or a negative reply if
> not.  The negative reply may indicate the reason why no path could be found.
> ****
>
> >>The RP (Request Parameters) object MUST be carried within each PCReq and
> PCRep messages. The RP object is used to specify various characteristics of
> the path computation request. ****
>
>  >> The END-POINTS object is used in a PCReq message to specify the source
> IP address and the destination IP address of the path for which a path
> computation is requested. Note that the source and destination addresses
> specified in the END-POINTS object may correspond to the source and
> destination IP address of the TE LSP or to those of a path segment.****
>
>  [MR] Setting the END-POINT object, maybe it could be possible to
> allocate cells/links for each path segment. This is something to be
> investigated. ****
>
>  >>The BANDWIDTH object is used to specify the requested bandwidth for a
> TE LSP. The notion of bandwidth is similar to the one used for RSVP
> >>signaling in [RFC2205], [RFC3209], and [RFC3473].****
>
>  >>The METRIC object is optional and can be used for several purposes. In
> a PCReq message, a PCC MAY insert one or more METRIC objects:****
>
>  o To indicate the metric that MUST be optimized by the path computation
> algorithm (IGP metric, TE metric, hop counts).****
>
> Currently, three metrics are defined: the IGP cost, the TE metric (see
> [RFC3785]), and the number of hops traversed by a TE LSP.****
>
>  o To indicate a bound on the path cost that MUST NOT be exceeded for the
> path to be considered as acceptable by the PCC.****
>
>  *>>The path computation algorithmic aspects used by the PCE to optimize
> a path with respect to a specific metric are outside the scope of this
> >>document.*****
>
> [MR] TASA could be a possible algorithm for computing the path. It seems
> to fits well with the RFC5440 Specification.****
>
> ** **
>
> TASA provides a method to the PCE for computing a network path, based on
> the network graph and applying computational constraints (i.e., selecting
> duplex- and
> interference-free conflict links, according to local and global queue
> level).****
>
> Each node in the TSCH TASA-based network could act as PCC (Path
> Computation Client), requesting a path computation to be performed by the
> PCE. In detail, with the PCReq message,
> the PCC asks the PCE to compute a path toward it (thus, source IP address
> = PCC IP address, destination IP address = PCE destination address), having
> a  given bandwidth, equal to the number of packets it wants to transmit
> (i.e., TASA local queue level, or  in other word, traffic load offered by
> the single node to the network).****
>
> After having collected all the PCReq messages from all the nodes in the
> network, the PCE can build a schedule, setting one or more paths for each
> PCC.****
>
> Once, the schedule has been built according to TASA matching and coloring
> procedures, it is transmitted to each node in the network, using PCRep
> messages.****
>
> Then, the 6TSCH 6TUS adaptation protocol can provide the functionality for
> delivering the traffic in the queues, according to the schedule built with
> TASA+PCEP. ****
>
>  ****
>
> *Some Open ISSUES:*
>
> ** **
>
> *Q1:* How the PCE collect the information related to the network graph?***
> *
>
> *R1:* Note that this is out of the scope of both RCF5440 and TASA.
> However, we may suppose that such information are provided by the routing
> protocol, RPL, as suggested in RFC5440.****
>
> “How” still has to be defined!****
>
> [Thomas] Agreed, that's a really important point.****
>
> ** **
>
> *Q2:* How the network is set up before implementing TASA+PCEP for
> building the schedule?****
>
> *R2:* TASA does not specify how the network is built. In fact, TASA runs
> over a network that has been already built, and that needs a schedule in
> order
> to allow traffic-flow exchanges (i.e., transmissions between each node and
> the PCE). Maybe, 6TUS could fill this gap and provide the functionality for
> the 15.4e TSCH network formation.****
>
> ** **
>
> [Thomas] I believe the "minimal" use case identified in the charter covers
> this.****
>
>  ****
>
> *Q3: *Is there any need to change the PCReq and PCRep messages format,
> for allowing the integration of PCEP with TASA?****
>
> [MR] there could be such need.****
>
> ** **
>
> ** **
>
> *Q4:*How the info in the PCRep messages can be used by 6TUS?****
>
> ** **
>
> [Thomas] The entity in the motes which received PCRep message simply send
> commands over the 6tus interface. ****
>
>  ****
>
> *Q5:* How would a TASA+PCEP solution work for P2P traffic? That is, data
> flowing from a switch to a light without going through the DAGroot?****
>
> [MR]TASA supports multi-point-to-point traffic (from each mote in the
> network to the DODAGroot). PCEP support P2P traffic. TASA+PCEP maybe could
> support P2P traffic. This is something to be investigated.****
>
> ** **
>
> ** **
>