Path computation in a segment routing network

An apparatus for path computation in a segment routing network, the segment routing network comprising a set of nodes, the apparatus comprising a processor and memory, the memory containing instructions executable by the processor whereby the apparatus is operative to:

• receive a request for computation of a path between end nodes in the segment routing network, the request including a path constraint;
• determine an initial optimum path, between the end nodes, which meets the path constraint using a full topology of the segment routing network, the initial optimum path being defined by a sequence of hops between a sub-set of the set of nodes, wherein the end nodes are comprised in the sub-set of the set of nodes;
• determine a segment identifier-optimised path defined by a stack of one or more segment identifiers, wherein the segment identifier-optimised path meets the path constraint,
• wherein the determination of the segment identifier-optimised path comprises analysis of a topology that comprises:
• the sub-set of the set of nodes, wherein the sub-set of the set of nodes comprises nodes of the initial optimum path,
• links between the nodes of the initial optimum path, and
• virtual links between the sub-set of the set of nodes,
• wherein each link and each virtual link has an associated metric, and the segment identifier-optimised path is determined by comparing the metric(s) associated with the links and/or virtual links defining paths of the segment routing network, and
• wherein the apparatus is configured to output at least one segment identifier which defines the determined segment identifier-optimised path.

A non-transitory machine-readable medium carrying instructions which, when executed by a processor, cause the processor to perform a method of path computation in a segment routing network, the segment routing network comprising a set of nodes, the method comprising:

• receiving a request for computation of a path between end nodes in the segment routing network, the request including a path constraint;
• determining an initial optimum path, between the end nodes, which meets the path constraint using a full topology of the segment routing network, the initial optimum path being defined by a sequence of hops between a sub-set of the set of nodes, wherein the end nodes are comprised in the sub-set of the set of nodes;
• determining a segment identifier-optimised path defined by a stack of one or more segment identifiers, wherein the segment identifier-optimised path meets the path constraint,
• wherein the determining of the segment identifier-optimised path comprises analysing a topology that comprises:
• the sub-set of the set of nodes, wherein the sub-set of the set of nodes comprises nodes of the initial optimum path,
• links between the nodes of the initial optimum path, and
• virtual links between the sub-set of the set of nodes,
• wherein each link and each virtual link has an associated metric, and the segment identifier-optimised path is determined by comparing the metric(s) associated with the links and/or virtual links defining paths of the segment routing network;
• and
• outputting at least one segment identifier which defines the determined segment identifier-optimised path.