Constrained and viable path computation systems and methods

Patent metadata

Field	Value
Publication number	US-9686176-B2
Application number	US-201514618364-A
Country	US
Kind code	B2
Filing date	Feb 10, 2015
Priority date	Dec 19, 2014
Publication date	Jun 20, 2017
Grant date	Jun 20, 2017

Abstract

Path calculation systems and methods for determining a path, based on constraints and rules, for a connection at one or more layers in a network, include determining a path exploration map of the network based on a multi-layer network model of the network defining external edges and intra-node paths, the path exploration map comprising every external port in the network that is reachable from a source port; and utilizing the path exploration map to determine a viable path, from a destination port to the source port, subject to the constraints and the rules and based on a cost.

First claim

What is claimed is:

1. A path calculation method for determining a path, based on constraints and rules, for a connection through one or more layers in a network, the path calculation method comprising:
determining a path exploration map of the network based on a multi-layer network model of the network defining external edges and intra-node paths, the path exploration map comprising every external port in the network that is reachable from a source port;
utilizing the path exploration map to determine a viable path, from a destination port to the source port at a plurality of layers, subject to the constraints and the rules and based on a cost and recursively building the viable path by following both the external edges and the intra-node paths through the plurality of layers from the destination port to the source port, wherein the plurality of layers are modeled in the path exploration map as the intra-node paths comprising one or more internal transformation edges which model a transition between layers of the plurality of layers and internal forwarding edges which model signal forwarding at same layers within a node; and
causing creation of the viable path in the network.

2. The path calculation method of claim 1 , wherein the path exploration map includes paths to every external port from the source port, in both transmit and receive directions.

3. The path calculation method of claim 1 , wherein the determining the path exploration map proceeds from the source port to the destination port and the utilizing the path exploration map proceeds from the destination port to the source port.

4. The path calculation method of claim 1 , wherein partial paths are explored in the utilizing the path exploration map and included or excluded based on the constraints and the rules.

5. The path calculation method of claim 1 , wherein the external edges are between the external ports, and the intra-node paths are between ports within a same node.

6. The path calculation method of claim 1 , wherein the constraints and/or the rules are evaluated in the utilizing the path exploration map over one or more hops, concurrently while determining the viable path.

7. The path calculation method of claim 1 , wherein the multi-layer network model considers any of Layer 0, 1, 2, and/or 3 in a same graph.

8. The path calculation method of claim 1 , wherein the performing step and the determining step are performed by a Software Defined Networking controller.

9. A controller configured to determine a path in a network, based on constraints and rules, for a connection at one or more layers, the controller comprising:
a processor; and
memory storing instructions that, when executed, cause the processor to
determine a path exploration map of the network based on a multi-layer network model of the network defining external edges and intra-node paths, the path exploration map comprising every external port in the network that is reachable from a source port, and
utilize the path exploration map to determine a viable path, from a destination port to the source port at a plurality of layers, subject to the constraints and the rules and based on a cost and recursively building the viable path by following both the external edges and the intra-node paths through the plurality of layers from the destination port to the source port, wherein the plurality of layers are modeled in the path exploration map as the intra-node paths comprising one or more internal transformation edges which model a transition between layers of the plurality of layers and internal forwarding edges which model signal forwarding at same layers within a node.

10. The controller of claim 9 , wherein the path exploration map includes paths to every external port from the source port, in both transmit and receive directions.

11. The controller of claim 9 , wherein the path exploration map is determined from the source port to the destination port and the path exploration map is utilized from the destination port to the source port to determine the viable path.

12. The controller of claim 9 , wherein partial paths are explored in the path exploration map and included or excluded based on the constraints and the rules.

13. The controller of claim 9 , wherein the external edges are between the external ports and the intra-node paths are between ports within a same node.

14. The controller of claim 13 , wherein the intra-node paths are either forwarding edges at a same Layer or transformation edges between Layers.

15. The controller of claim 9 , wherein the constraints and/or the rules are evaluated in the path exploration map over one or more hops, concurrently while determining the viable path.

16. The controller of claim 9 , wherein the multi-layer network model considers any of Layer 0, 1, 2, and/or 3 in a same graph.

17. The controller of claim 9 , wherein the controller is a Software Defined Networking controller.

18. A node configured to determine a path in a network, based on constraints and rules, for a connection at one or more layers, the node comprising:
a plurality of ports configured to communicate with other ports to form external edges;
a switch system between the plurality of ports configured to form forwarding edges and transformation edges between the plurality of ports; and
a controller communicatively coupled to the plurality of ports and the switch, the controller is configured to
determine a path exploration map of the network based on a multi-layer network model of the network defining the external edges and intra-node paths, the path exploration map comprising every external port in the network that is reachable from a source port, and
utilize the path exploration map to determine a viable path, from a destination port to the source port at a plurality of layers, subject to the constraints and the rules and based on a cost and recursively building the viable path by following both the external edges and the intra-node paths through the plurality of layers from the destination port to the source port, wherein the plurality of layers are modeled in the path exploration map as the intra-node paths comprising one or more internal transformation edges which model a transition between layers of the plurality of layers and internal forwarding edges which model signal forwarding at same layers within a node.

19. The node of claim 18 , wherein the path exploration map includes paths to every external port from the source port, in both transmit and receive directions.

Assignees

• Traxler Norman Steven
• Miedema David Jeffrey
• Slobodrian Sergio
• Webb William
• Ciena Corp

Inventors

• Traxler Norman Steven
• Miedema David Jeffrey
• Slobodrian Sergio
• Webb William

Classifications

• H04L45/02

  Topology update or discovery · CPC title

• H04L41/14

  Network analysis or design · CPC title

• H04L45/122 Primary

  by minimising distances, e.g. by selecting a route with minimum of number of hops · CPC title

• H04L45/64

  using an overlay routing layer · CPC title