Controller placement for fast failover in the split architecture

• US 8,811,212 B2
• Filed: 02/22/2012
• Issued: 08/19/2014
• Est. Priority Date: 02/22/2012
• Status: Active Grant

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Beheshti-Zavareh, Neda, Zhang, Ying, Halpern, Joel
• Primary Examiner(s): Nawaz, Asad
• Assistant Examiner(s): ALI, SYED
• Application Number:
  US13/402,732
• Publication Number:
  US 20130215769A1
• Time in Patent Office: 909 Days
• Field of Search: 370/252
• US Class Current: 370/252
• CPC Class Codes: H04L 41/0663 Performing the actions predefined by failover planning, e.g. switching to standby network elements
• CPC Class Codes: H04L 41/0836 to enhance reliability, e.g. reduce downtime
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 41/122 of virtualised topologies, e.g. software-defined networks [SDN] or network function virtualisation [NFV]
• CPC Class Codes: H04L 41/145 involving simulating, designing, planning or modelling of a network
• CPC Class Codes: H04L 41/22 comprising specially adapted graphical user interfaces [GUI]
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/64 using an overlay routing layer
• CPC Class Codes: H04W 16/18 Network planning tools

Abstract

A method implemented by a network topology design system, the network topology design system including a processing device. The method to determine placement of a controller within a network with a split architecture where control plane components of the split architecture network are executed by a controller and the control plane components are separate from data plane components of the split architecture network. The placement of the controller is selected to minimize disruption of the split architecture network caused by a link failure, a switch failure or a connectivity loss between the controller and the data plane components.

Claims

1. A method implemented by a network topology design system, the network topology design system including a processing device, the method to determine placement of a controller within a network with a split architecture where control plane components of the split architecture network are executed by a controller and the control plane components are separate from data plane components of the split architecture network, wherein the placement of the controller is selected to minimize disruption of the split architecture network caused by a link failure, a switch failure or a connectivity loss between the controller and the data plane components, the method comprising the steps of:

graphing, by the processing device, a topology of the split architecture network, with links in the split architecture network represented as a set of edges in a graph and network elements in the split architecture network represented as a set of nodes;

sorting, by the processing device, the set of nodes in descending order based on a number of links to neighbor nodes for each node;

traversing, by the processing device, the set of nodes to calculate a protection metric for one or more nodes, wherein the protection metric measures resilience of the split architecture network as a degree of node failure protection within the split architecture network for a potential controller placement, the degree of node failure protection determining a subset of protected nodes in the set of nodes, where a protected node in the subset of protected nodes can redirect control traffic over a tunnel to an intermediate node in the graph that is not downstream of the protected node, and where the tunnel traverses at least one downstream node of the protected node; and

selecting, by the processing device, the network element corresponding to the node with a best protection metric to be the controller for the split architecture network.

2. The method of claim 1, wherein traversing the set of nodes to calculate the protection metric further comprises the step of:

determining a number of protected neighbor nodes with a connection to other nodes.

3. The method of claim 2, wherein selecting the network element corresponding to the node with a best protection metric to be the controller for the split architecture network comprises the step of:

selecting a node with a largest number of protected neighbor nodes to be the controller.

4. A computer system for determining a placement of a controller for a split architecture network where control plane components of the split architecture network are executed by the controller and the control plane components are separate from data plane components of the split architecture network, wherein the placement of the controller is selected to minimize disruption of the split architecture network caused by a link failure, a switch failure or a connectivity loss between the controller and the data plane components, the computer system comprising:

a processor configured to execute a topology graphing module and controller placement module,

the topology graphing module configured to graph a topology of the split architecture network, with links in the split architecture network represented as a set of edges in a graph and network elements in the split architecture network represented as a set of nodes

the controller placement module configured to sort the set of nodes in descending order based on a number of links to neighbor nodes for each node and to traverse the set of nodes to calculate a protection metric for one or more nodes, wherein the protection metric measures resilience of the split architecture network as a degree of node failure protection within the split architecture network for a potential controller placement, the degree of node failure protection determining a subset of protected nodes in the set of nodes, where a protected node in the subset of protected nodes can redirect control traffic over a tunnel to an intermediate node in the graph that is not downstream of the protected node, and where the tunnel traverses at least one downstream node of the protected node, the controller placement module further configured to select the network element corresponding to a node with a best protection metric to be the controller for the split architecture network.

5. The computer system of claim 4, wherein the controller placement module is further configured to determine a number of protected neighbor nodes with a connection to other nodes.

6. The computer system of claim 5, wherein the controller placement module is further configured to select a node with a largest number of protected neighbor nodes to be the controller.