Computing Service Chain-Aware Paths

• US 20150319078A1
• Filed: 05/01/2015
• Published: 11/05/2015
• Est. Priority Date: 05/02/2014
• Status: Active Grant

• Current Assignee: Futurewei Technologies Incorporated (Huawei Investment & Holding Co., Ltd.)
• Original Assignee: Futurewei Technologies Incorporated (Huawei Investment & Holding Co., Ltd.)
• Inventors: Lee, Young, Dunbar, Linda, Zhang, Hong
• Granted Patent: US 9,634,867 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: H04L 12/6418 Hybrid transport
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 45/12 Shortest path evaluation

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.

Claims

1. A method comprising:

receiving, by a path computation element (PCE), 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, 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, at least a first of the network paths according to the SF input; and

sending, by the PCE, a path computation response indicating at least 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 delay, bandwidth, or combinations thereof.

3. The method of claim 2, wherein the path computation request further comprises an ingress node address and an egress node address for the source-destination pair, 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 path computation request is received from a network controller, and wherein the method further comprises:

selecting, by the PCE, a second of the network paths according to the SF input; and

determining, by the PCE, that the first network path comprises less number of hops than the second network path.

7. The method of claim 1, wherein the path computation request is received from a network controller, wherein the method further comprises:

selecting, by the PCE, a second of the network paths according to the SF input; and

determining, by the PCE, that the first network path and the second network path comprise a same number of hops, and

wherein the path computation response further indicates the second network path.

8. 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.

9. A method comprising:

obtaining, by a network controller, service chain (SC) information associated with an SC that is associated with a plurality of service functions (SFs);

obtaining, by the network controller, 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 request 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.

10. The method of claim 9, 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.

11. The method of claim 9, 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 a 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.

12. The method of claim 9, further comprising sending, by a 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.

13. The method of claim 9, 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.

14. The method of claim 9, 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.

15. The method of claim 9, wherein the SC information and the node-SF map are obtained from an SC orchestration entity.

16. A network element (NE) comprising:

a receiver configured to receive a path computation request message comprising a source-destination pair, at least one network routing constraint, and a service function (SF) input associated with a 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 of the shortest paths according to the SF input; and

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

17. The NE of claim 16, wherein the SF input indicates:

an SC associated with the plurality of SF types; and

a plurality of network nodes that provide instances of the plurality of SF types, and

wherein the processor is further configured to select the first shortest path by determining that the first shortest path traverses through at least some of the network nodes and one instance of each SF type.

18. The NE of claim 17, wherein the SF input comprises an SF sequence indicating a first of the SF types is positioned before a second of the SF types, and wherein the first shortest path traverses through a first of the network nodes that provides a first instance of the first SF type before a second of the network nodes that provides a second instance of the second SF type.

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

20. The NE of claim 16, wherein the network topology information comprises a link state database (LSDB).