Computing service chain-aware paths

Patent metadata

Field	Value
Publication number	US-9634867-B2
Application number	US-201514702503-A
Country	US
Kind code	B2
Filing date	May 1, 2015
Priority date	May 2, 2014
Publication date	Apr 25, 2017
Grant date	Apr 25, 2017

Abstract

A method implemented by a path computation element (PCE), comprising receiving a path computation request to compute a network path for a source-destination pair in a service chain (SC) network, wherein the path computation request comprises at least one network routing constraint and a service function (SF) input associated with a plurality of SFs, computing a plurality of network paths through the network for the source-destination pair according to the network routing constraint, selecting at least a first of the network paths according to the SF input, and sending a path computation response indicating at least the first network path in response to the received path computation request.

First claim

What is claimed:

1. A method comprising:
receiving, by a path computation element (PCE), a path computation request from a network controller to compute a network path for a source-destination pair in a service chain (SC) network, wherein the path computation request comprises at least one network routing constraint and a service function (SF) input associated with a plurality of SFs;
computing, by the PCE, a plurality of network paths through the network for the source-destination pair according to the network routing constraint;
selecting, by the PCE, a first network path from the plurality of network paths according to the SF input;
selecting, by the PCE, a second network path from the plurality of network paths according to the SF input; and
comparing, by the PCE, a number of hops in the first network path to the number of hops in the second network path; and
responsive to a determination that the first network path comprises a fewer number of hops than the second network path, sending, by the PCE, a path computation response indicating the first network path in response to the received path computation request.

2. The method of claim 1 , further comprising obtaining, by the PCE, network topology information comprising link costs associated with the network, wherein the link costs are associated with a delay, a bandwidth, or combinations thereof.

3. The method of claim 2 , wherein the path computation request further comprises an ingress node address for an ingress node that is a source and an egress node address for an egress node that is a destination, wherein computing the plurality of network paths comprises finding a shortest path from the ingress node to the egress node according to the network topology information and the network routing constraint, and wherein the shortest path is a minimum link cost path that satisfies the network routing constraint.

4. The method of claim 1 , wherein the SF input indicates:
a plurality of network nodes associated with the plurality of SFs; and
an SC associated with the plurality of SFs, and
wherein selecting the first network path comprises determining that the first network path traverses through at least some of the network nodes and at least some of the SFs.

5. The method of claim 4 , wherein the SF input further indicates that the plurality of SFs is arranged in an ordered sequence in the SC, wherein a first of the SFs is arranged before a second of the SFs in the sequence, and wherein the first network path traverses through a first of the network nodes associated with the first SF before a second of the network nodes associated with the second SF.

6. The method of claim 1 , wherein the method further comprises:
responsive to a determination that the first network path and the second network path comprise a same number of hops, indicating the first network path and the second network path in the path computation response.

7. The method of claim 1 , wherein the network routing constraint is associated with a minimum-hop criterion, a path type, a bandwidth, a delay, or combinations thereof.

8. A method comprising:
obtaining, by a network controller from a service chain (SC) orchestration entity, SC information associated with an SC that is associated with a plurality of service functions (SFs);
obtaining, by the network controller from the SC orchestration entity, a node-SF map indicating network locations of the SFs;
sending, by the network controller, a path computation request message to request a path computation for a source-destination pair according to at least one network routing constraint, the SC information, and the node-SF map; and
receiving, by the network controller, a path computation response message comprising a route list in response to the path computation r q St message, wherein the route list comprises one or more network paths for the source-destination pair, and wherein each network path satisfies the network routing constraint and traverses through at least some the network locations of the SFs.

9. The method of claim 8 , wherein the plurality of SFs is arranged in an ordered sequence in the Sc, wherein a first of the SFs is arranged before a second of the SFs in the sequence, and wherein each path traverses through a first of the network locations of the first SF before a second of the network locations of the second SF.

10. The method of claim 8 , wherein the source-destination pair comprises a first network address of an ingress node associated with the SC and a second network address of an egress node associated with the SC, wherein the method further comprises sending, by the network controller, a path configuration message to the ingress node, and wherein the path configuration message indicates at least one of the network paths received from the path computation response message.

11. The method of claim 8 , further comprising sending, by the network controller, a path configuration message to a network node along one of the network paths in the route list, wherein the path configuration message indicates at least a portion of the network path.

12. The method of claim 8 , wherein the node-SF map comprises an identifier (ID) that identifies the SC, an SF instance path indicating at least one instance of a first of the SFs, and a network address that identifies an SF steering node associated with the SF instance path, or combinations thereof.

13. The method of claim 8 , wherein the SC information comprises policy information associated with the SC, an ordered sequence for the plurality of SFs, an ingress node address associated with the SC, an egress node address associated with the SC, or combinations thereof.

14. The method of claim 8 , wherein the network routing constraint comprises a quality-of-service (QoS) parameter associated with a delay, a bandwidth, a number of hops, or combinations thereof.

15. A network element (NE) comprising:
a receiver configured to receive a path computation request e, age comprising a source-destination pair, at least one network routing constraint, and a service function (SF) input associated with a plurality of SF types, wherein the SF input indicates a service chain (SC) associated with the plurality of SF types, and a plurality of network nodes that provide instances of the plurality of SF types, wherein the SF input comprises an SF sequence indicating a first SF type of the plurality of SF types is positioned before a second SF type of the plurality of SF types;
a processor coupled to the receiver and configured to:
obtain network topology information;
compute a plurality of shortest paths according to the network topology information and the network routing constraint; and
select a first shortest path of the plurality of shortest paths by determining that the first shortest path traverses through at least some of the plurality of network nodes and one instance of each SF type, wherein the first shortest path traverses through a first network node of the plurality of network nodes that provides a first instance of the first SF type before a second network node of the plurality of network nodes that provides a second instance of the second SF type;

a transmitter coupled to the processor and configured to send a path computation response message comprising at least the first shortest path.

16. The NE of claim 15 , wherein the network routing constraint comprises a quality-of-service (QoS) parameter associated with a delay, a bandwidth, a number of hops, or combinations thereof.

17. The NE of claim 15 , wherein the network topology information comp

Assignees

• Futurewei Technologies Inc

Inventors

• Lee Young
• Dunbar Linda
• Zhang Hong

Classifications

• H04L41/12

  Discovery or management of network topologies · CPC title

• H04L12/6418 Primary

  Hybrid transport · CPC title

• H04L45/12

  Shortest path evaluation · CPC title