Capacity-aware heuristic approach for placing software-defined networking (SDN) switches in hybrid SDN networks for single link/node failure

Patent metadata

Field	Value
Publication number	US-10158559-B2
Application number	US-201614997794-A
Country	US
Kind code	B2
Filing date	Jan 18, 2016
Priority date	Jan 29, 2015
Publication date	Dec 18, 2018
Grant date	Dec 18, 2018

Abstract

A network controller comprising a processor configured to obtain topology information of a network, wherein the topology information indicates a plurality of non-software-defined networking (non-SDN) network elements (NEs) interconnected by a plurality of links in the network, analyze each non-SDN NE according to the topology information to determine whether the non-SDN NE is a candidate NE for establishing a backup tunnel to protect a single-link failure at one of the plurality of links, and select a plurality of target NEs from the candidate NEs to protect against all single link-failures in the network, and a transmitter coupled to the processor and configured to send a first message to a first of the target NEs to dynamically enable software-defined networking (SDN) functionalities at the first target NE in order to facilitate single-link failure protection in the network.

First claim

What is claimed is:

1. A network controller comprising:
a processor configured to:
obtain topology information of a network, wherein the topology information indicates a plurality of non-software-defined networking (non-SDN) network elements (NEs) interconnected by a plurality of links in the network;
analyze each non-SDN NE according to the topology information to determine whether the non-SDN NE is a candidate NE for establishing a backup tunnel to protect a single-link failure at one of the plurality of links; and
select a plurality of target NEs from candidate NEs based on software-defined networking (SDN) functionalities of the candidate NEs to protect against all single link-failures in the network based on the topology information; and

a transmitter coupled to the processor and configured to send a first message to a first of the target NEs to dynamically enable the SDN functionalities at the first of the target NEs in order to facilitate single-link failure protection in the network.

2. The network controller of claim 1 , wherein the processor is further configured to analyze each non-SDN NE by:
obtaining routing information indicating a source NE of the plurality of non-SDN NEs reaches a plurality of destination NEs of the plurality of non-SDN NEs via a same next-hop link of the plurality of the links;
determining that the non-SDN NE is the candidate NE for establishing the backup tunnel with the source NE to protect the next-hop link when computing a first shortest path from the source NE to the non-SDN NE that excludes the next-hop link; and
computing a second shortest path from the non-SDN NE to each destination NE that excludes the next-hop link.

3. The network controller of claim 1 , wherein the processor is further configured to select the target NEs by determining a coverage weight value for each candidate NE according to a number of single-link failures protected by the candidate NE.

4. The network controller of claim 3 , wherein the processor is further configured to select the target NEs by:
determining a first threshold based on the coverage weight values for each candidate NE; and
selecting a first candidate NE corresponding to a first of the coverage weight values that satisfies the first threshold as the first of the target NEs.

5. The network controller of claim 4 , wherein the processor is further configured to select the plurality of target NEs by:
re-computing a coverage weight value for remaining candidate NEs by excluding single-link failures protected by the first of the target NEs;
determining a second threshold based on the recomputed coverage weight values;
determining that a second of the candidate NEs and a third of the candidate NEs comprise a same recomputed coverage weight value that satisfies the second threshold; and
selecting the second of the candidate NEs as a second of the plurality of target NEs when the second of the candidate NEs comprises a greater number of hops from the first of the target NEs than the third of the candidate NEs.

6. The network controller of claim 3 , wherein the processor is further configured to select the target NEs by:
determining a threshold based on the coverage weight values;
determining that a first of the candidate NEs and a second of the candidate NEs comprise a same coverage weight value that satisfies the threshold;
determining a first distance weight value for the first of the candidate NEs by computing a first average number of hops along first shortest paths corresponding to the first of the candidate NEs;
determining a second distance weight value for the second of the candidate NEs by computing a second average number of hops along first shortest paths corresponding to the second of the candidate NEs; and
selecting the first of the candidate NEs as the first of the target NEs when the first distance weight value is less than the second distance weight value.

7. The network controller of claim 3 , wherein the transmitter is further configured to send a second message to the first target NE instructing the first target NE to establish backup tunnel with a corresponding source NE according to a corresponding first shortest path for rerouting traffic around a corresponding next-hop link when a single-link failure occurs at the corresponding next-hop link.

8. The network controller of claim 2 , wherein the processor is further configured to generate a flow table according to the first shortest path and one of a plurality of second shortest paths corresponding to the first of the target NEs, and wherein the transmitter is further configured to send a second message to the first of the target NEs indicating the flow table.

9. The network controller of claim 1 , wherein the plurality of non-SDN NEs are Internet protocol (IP) routers.

10. A method implemented by a network controller, comprising:
obtaining, via a processor of the network controller, topology information of a network, wherein the topology information indicates a plurality of non-software-defined networking (non-SDN) network elements (NEs) interconnected by a plurality of links in the network;
analyzing, via the processor, each non-SDN NE according to the topology information to determine whether a location of the non-SDN NE is a candidate location for placing a software-defined network (SDN)-enabled NE to cover a single-link failure at one of the plurality of links;
selecting, via the processor, a plurality of target locations from the candidate locations for placing SDN-enabled NEs to cover all single link-failures in the network based on the topology information; and
sending, via a transmitter of the NE, a message to an administrative entity of the network identifying the target locations for placing SDN-enabled NEs in the network.

11. The method of claim 10 , wherein analyzing each non-SDN NE comprises:
obtaining routing information indicating a source NE of the plurality of non-SDN NEs reaches a plurality of destination NEs of the plurality of non-SDN NEs via a same next-hop link of the plurality of the links;
computing, via the processor, a plurality of backup paths for rerouting traffic around the next-hop link according to the topology information; and
determining, via the processor, that the location of the non-SDN NE is the candidate location when a first of the backup paths from the source NE to the non-SDN NE excludes the next-hop link and a second plurality of the backup paths from the non-SDN NE to the destinations NEs exclude the next-hop link.

12. The method of claim 10 , wherein selecting the target locations comprises:
constructing, via the processor, a table by generating a row to represent each single-link failure in the network and generating a column to represent each non-SDN NE location;
filling, via the processor, a cell in the table with a value of one when a corresponding non-SDN NE location is the candidate location for placing the SDN-enabled NE to protect a corresponding single-link failure;
filling, via the processor, a cell in the table with a value of a zero when a corresponding non-SDN NE location is not the candidate location for placing the SDN-enabled NE to protect a corresponding single-link failure;
computing, via the processor, a coverage weight value for each column by adding values of cells in the column;
determining, via the processor, a threshold based on the coverage weight values; and
selecting, via the processor, a first of the non-SDN NE locations corresponding to a first of the columns comprising a first of the coverage weight values that satisfies the threshold as a first of the target locations.

13. The method of claim 12 , wherei

Assignees

• Futurewei Technologies Inc

Inventors

• Luo Min
• Chu Cing-Yu
• Xi Kang
• Chao Hung-Hsiang Jonathan

Classifications

• H04L45/22 Primary

  Alternate routing · CPC title

• H04L45/02

  Topology update or discovery · CPC title

• H04L41/0836

  to enhance reliability, e.g. reduce downtime · CPC title

• H04L45/122

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

• H04L41/12

  Discovery or management of network topologies · CPC title