Here it is more details on our implementation.

RFC5440 implementation in BGPCEP project

Introduction

The goal of this memo is to explain how we have implemented the full support of RFC5440 (PCEP) and RFC4605 (PCE Architecture) in BGPCEP project. Indeed, if the BGPCEP project support all RFC5440 messages, PCRequest and PCReply messages are not handle and no Path Computation Algorithm is provided. These new bundles provide support of aforementioned messages as well as Constraint Shortest Path First (CSPF) path computation.

4 new bundles are introduced:

• pcep-server-api: This bundle provides new Yang models and Java Interfaces in order to publish new services and API to other bundles
• pcep-server-ted: This bundle is in charge to build and update the Traffic Engineering Database which is mandatory for the path computation algorithm
• pcep-server-algo: This bundle provides path computation capabilities
• pcep-server-provider: This bundle provides the implementation of the pcep server functionality

Traffic Engineering Database

Path computation algorithms are based on graph theory. For that purpose, they need a connected, oriented and weighted graph that represent the underlying network topology. If actual BGPCEP provides topology acquisition through BGP-LS, information are store in the DataStore as a flat topology which follow IETF TE yang model and not a connected graph. Of course, it is possible to use the Linkstate Route or Linkstate Topology models stored in DataStore, but at the price of performance. Indeed, the path algorithm crawl the graph to find the shortest path that meet the constraints. A connected graph implementing in Java class will link edges and vertices directly as Java Objects i.e. Edge Java class has reference to Vertices Java class and reciprocally. This ease the crawling function i.e. when the algorithm search the next vertices, it just get the list of edges of this vertices and once an edge chosen, get the vertices connected to the destination of this edge. In a flat topology, like available in the DataStore, crawling need to get edge from the edge hash table and then get the vertices from the vertices hash table as edge and vertices are only connected through String identifier and not Java Object. On small topology (say less than 50 nodes) and powerful server the performance difference is small, but on large network topology (say around 1000 nodes) the performance becoming a blocking factor.

As it is not possible to model a connected graph in Yang, we proceed in two steps:

• Design a new Yang model to define Node and Link
• Create new Vertex and Edge Java Class that extend the NodeBuilder and LinkBuilder Java Class generated by the yang tools.

This way we could store graph elements in the DataStore as well as built the graph in memory for Path Computation Algorithms. Graph is also available in config in order to provide static topology or complete topology collected through BGP-LS (e.g. AS peering links).

Constraint Shortest Path First

Once graph available, it is possible to compute path. For that purpose, we implement a registration mechanism of algorithms. This principle allows flexibility and enhancement of the algorithms and more specifically allow to manage the Objective Function of the PCEP protocol. Indeed, a PCC could request different objective in the PCReq message through the Objective Function Object (See RFC 5441, RFC 8306, RFC 8233 and IANA registration https://www.iana.org/assignments/pcep/pcep.xhtml#of)
 
There is numerous CSPF algorithms and different way to proceed (e.g. prune the graph where Vertex end Edge don't meet constraints and then run a standard SPF on this sub-graph). We choose to implement the SAMCRA (Self-Adaptive Multiple Constraints Routing Algorithm) proposed by Fernando Kuipers. It has been mathematically proven that if it exists a solution for a path with given set of constraints, SAMCRA will compute the best solution. We implement the standard algorithm and the optimised version with lookahead option.

We have performed numerous tests on real topology and simulated topologies to assess our code.

Server

The last bundle publishes the server as a new blueprint service and implements the new APIs that allow a user to request path computation and enforce path without the need to specify Explicit Route.

This new path computation service is also integrated in existing PCEP code in order to answer to PCReq message by a PCReply message with a valid Explicit Route Object (ERO) when path computation success or a NoPath Object when it fails. Modification is mostly done in Statefull07TopologySessionListener class which now could handle PCReq message. Java <Future> class is used to call the path computation class and send back the reply to the PCC with a PCRep message leaving the Statefull07TopologySessionListener class continuing managing new PCEP message.

Unsupported Object

Up to now, Include Route Object (IRO) and eXclude Route Object (XRO) are not supported. Only default Objective Function is supported. These objects will be supported in next release. Segment Routing is not yet address while, the graph is already ready to store Node SID and path computation is independent from the way the LSP is enforced (RSVP-TE or Segment Routing). In next release we will implement the conversion of the ERO into a label stack suitable for Segment Routing.