Opportunity based path computation systems and methods in constraint-based routing

Patent metadata

Field	Value
Publication number	US-9497521-B2
Application number	US-201414301397-A
Country	US
Kind code	B2
Filing date	Jun 11, 2014
Priority date	Apr 30, 2014
Publication date	Nov 15, 2016
Grant date	Nov 15, 2016

Abstract

A method, a controller, and a network include determining an opportunity cost metric for each of a plurality of links in a network including a plurality of nodes, wherein the opportunity cost metric comprises a future constraint reflecting expectations for growth on currently established connections on each link of the plurality of links; receiving a request for a new connection between two nodes of the plurality of nodes in the network; and utilizing a constraint-based routing algorithm to determine a path for the new connection between the two nodes, wherein the constraint-based routing algorithm determines the path through the plurality of nodes via the plurality of links based on a plurality of constraints including the opportunity cost metric.

First claim

What is claimed is:

1. A method, comprising:
determining an opportunity cost metric for each of a plurality of links in a network comprising a plurality of nodes, wherein the opportunity cost metric comprises a future constraint reflecting expectations for growth on currently established connections on each link of the plurality of links;
receiving a request for a new connection between two nodes of the plurality of nodes in the network; and
utilizing a constraint-based routing algorithm to determine a path for the new connection between the two nodes, wherein the constraint-based routing algorithm determines the path through the plurality of nodes via the plurality of links based on a plurality of constraints comprising the opportunity cost metric.

2. The method of claim 1 , wherein the opportunity cost metric comprises a flag identifying a presence or absence of expandable connections of the currently established connections on each link of the plurality of links.

3. The method of claim 2 , wherein the opportunity cost metric is based on a presence or absence of flexible Optical channel Data Unit (ODU) connections on each link of the plurality of links.

4. The method of claim 1 , wherein the opportunity cost metric comprises a numerical value identifying an amount of expandable connections for the currently established connections on each link of the plurality of links.

5. The method of claim 4 , wherein the numerical value is based on a Committed Information Rate (CIR)/Committed Burst Size (CBS) and an Excess Information Rate (EIR)/Excess Burst Size (EBS) for the currently established connections on each link of the plurality of links.

6. The method of claim 1 , wherein the opportunity cost metric is defined for each of a plurality of bandwidth chunks on each link of the plurality of links.

7. The method of claim 1 , wherein the opportunity cost metric is defined for a capability of adding any of a plurality of bandwidth chunks on each link of the plurality of links.

8. The method of claim 1 , further comprising:
biasing the constraint-based routing algorithm to select links of the plurality of links based on a lower opportunity cost metric than other links of the plurality of links.

9. The method of claim 1 , further comprising:
for links of the plurality of links that comply with a maximum delay constraint, selecting the links based on the opportunity cost metric.

10. The method of claim 1 , further comprising:
publishing and maintaining the opportunity cost metric for each of the plurality of links via control plane signaling in the network.

11. The method of claim 1 , wherein the constraint-based routing algorithm comprises any of Constrained Shortest Path First (CSPF), Constraint-based Routing Label Distribution Protocol (CR-LDP), Resource Reservation Protocol-Traffic Engineering (RSVP-TE), Private Network-to-Network Interface (PNNI), Open Shortest Path First (OSPF), OSPF-Traffic Engineering (OSPF-TE), and Intermediate System to Intermediate System (IS-IS).

12. A controller, comprising:
a network interface communicatively coupled to one or more nodes of a plurality of nodes in a network;
a processor communicatively coupled to the network interface; and
memory storing instructions that, when executed, cause the processor to:
receive or determine an opportunity cost metric for each of a plurality of links interconnecting the plurality of nodes, wherein the opportunity cost metric comprises a future constraint reflecting expectations for growth on currently established connections on each link of the plurality of links;
receive a request for a new connection between two nodes of the plurality of nodes in the network; and
utilize a constraint-based routing algorithm to determine a path for the new connection between the two nodes, wherein the constraint-based routing algorithm determines the path through the plurality of nodes via the plurality of links based on a plurality of constraints comprising the opportunity cost metric.

13. The controller of claim 12 , wherein the opportunity cost metric comprises a flag identifying a presence or absence of expandable connections of the currently established connections on each link of the plurality of links; and
wherein the opportunity cost metric is based on a presence or absence of flexible Optical channel Data Unit (ODU) connections on each link of the plurality of links.

14. The controller of claim 12 , wherein the opportunity cost metric comprises a numerical value identifying an amount of expandable connections for the currently established connections on each link of the plurality of links; and
wherein the numerical value is based on a Committed Information Rate (CIR)/Committed Burst Size (CBS) and an Excess Information Rate (EIR)/Excess Burst Size (EBS) for the currently established connections on each link of the plurality of links.

15. The controller of claim 12 , wherein the opportunity cost metric is one of defined for each of a plurality of bandwidth chunks on each link of the plurality of links and defined for a capability of adding any of a plurality of bandwidth chunks on each link of the plurality of links.

16. The controller of claim 12 , wherein the instructions that, when executed, further cause the processor to:
bias the constraint-based routing algorithm to select links of the plurality of links based on a lower opportunity cost metric than other links of the plurality of links.

17. The controller of claim 12 , wherein the instructions that, when executed, further cause the processor to:
for links of the plurality of links that comply with a maximum delay constraint, select the links based on the opportunity cost metric.

18. The controller of claim 12 , wherein the instructions that, when executed, further cause the processor to:
maintain the opportunity cost metric for each of the plurality of links via control plane signaling in the network.

19. The controller of claim 12 , wherein the constraint-based routing algorithm comprises any of Constrained Shortest Path First (CSPF), Constraint-based Routing Label Distribution Protocol (CR-LDP), Resource Reservation Protocol-Traffic Engineering (RSVP-TE), Private Network-to-Network Interface (PNNI), Open Shortest Path First (OSPF), OSPF-Traffic Engineering (OSPF-TE), and Intermediate System to Intermediate System (IS-IS).

20. A network, comprising:
a plurality of nodes interconnected by a plurality of links; and
a control plane operating in the network and utilizing a constraint-based routing algorithm; wherein the control plane is configured to:
receive or determine an opportunity cost metric for each of the plurality of links, wherein the opportunity cost metric comprises a future constraint reflecting expectations for growth on currently established connections on each link of the plurality of links;
receive a request for a new connection between two nodes of the plurality of nodes in the network; and
utilize the constraint-based routing algorithm to determine a path for the new connection between the two nodes, wherein the constraint-based routing algorithm determines the path through the plurality of nodes via the plurality of links based on a plurality of constraints comprising the opportunity cost metric.

Assignees

• Sareen Jatin
• Juneja Kapil
• Kannan Rajagopalan
• Ciena Corp

Inventors

• Sareen Jatin
• Juneja Kapil
• Kannan Rajagopalan

Classifications

• H04L45/124

  using a combination of metrics · CPC title

• H04Q11/0062 Primary

  Network aspects · CPC title

• H04Q2011/0077

  Labelling aspects, e.g. multiprotocol label switching [MPLS], G-MPLS, MPAS · CPC title

• H04L45/50

  using label swapping, e.g. multi-protocol label switch [MPLS] · CPC title

• H04Q2011/009

  Topology aspects · CPC title