Patent ID: 8560647

Claim:
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 set of controllers within a network with a split architecture where control plane components of the split architecture network are executed by the set of controllers and the control plane components are separate from data plane components of the split architecture network, the placement of the set of controllers selected to minimize disruption of the split architecture network caused by a link failure, a switch failure or a connectivity loss between the set of controllers and the data plane components, the method comprising the steps of: graphing a topology of the split architecture network, with each link in the split architecture network represented as an edge in a graph and each network element in the split architecture network represented as a node; determining a set of clusters of nodes within the graph by applying an agglomerative clustering process or a partitive clustering process, either process comprising the further steps of, applying a cost function to measure a length of inter-cluster connecting edges, and modifying the set of clusters to minimize the length of inter-cluster connecting edges; determining, by the network topology design system, a centroid for each cluster in the set of clusters, wherein the centroid is a most central node in each cluster, determining the centroid comprising the further steps of, applying a cost function to measure intra-cluster edge length for each node in each cluster, and selecting a lowest cost node in each cluster to be the centroid for the cluster; assigning one of the set of controllers to each network element corresponding to a determined centroid in the graph; and assigning each controller to control a set of network elements corresponding to a cluster in the graph.