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-2016226701-A1
Application number	US-201614997794-A
Country	US
Kind code	A1
Filing date	Jan 18, 2016
Priority date	Jan 29, 2015
Publication date	Aug 4, 2016
Grant date	—

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

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; and determining that a non-SDN NE is a candidate NE for establishing a 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 2 , 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; and selecting a first candidate NE corresponding to a first of the coverage weight values that satisfies the first threshold as the first target NE.

5 . The network controller of claim 4 , wherein the processor is further configured to select the target NEs by:
re-computing a coverage weight value for remaining candidate NEs by excluding single-link failures protected by the first target NE; 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 candidate NE as a second of the target NEs when the second candidate NE comprises a greater number of hops from the first target NE than the third candidate NE.

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 candidate NE by computing a first average number of hops along first shortest paths corresponding to the first candidate NE; determining a second distance weight value for the second candidate NE by computing a second average number of hops along first shortest paths corresponding to the second candidate; and selecting the first candidate NE as the first target NE when the first distance weight value is less than the second 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 a 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 3 , wherein the processor is further configured to generate a flow table according to a first shortest path and one of the second shortest paths corresponding to the first target NE, and wherein the transmitter is further configured to send a second message to the first target NE 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 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 a processor of the NE, 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; 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; and computing, via the processor, 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 a 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 11 , 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 a candidate location for placing an 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 a candidate location for placing an 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 , wherein selecting the target locations further comprises:
eliminating, via the processor, a first of the rows from the table when a cell in the first column corresponding to the first row comprises a value of one; and repeating, via the processor, coverage weight value computation and target location selection until all rows are el

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/036

  Updating the topology between route computation elements, e.g. between OpenFlow controllers · CPC title

• H04L41/122

  of virtualised topologies, e.g. software-defined networks [SDN] or network function virtualisation [NFV] · CPC title

• H04L41/0895

  Configuration of virtualised networks or elements, e.g. virtualised network function or OpenFlow elements · CPC title

• H04L41/40

  using virtualisation of network functions or resources, e.g. SDN or NFV entities · CPC title