Method and system for load balancing at a data network

Patent metadata

Field	Value
Publication number	US-9338097-B2
Application number	US-201314068311-A
Country	US
Kind code	B2
Filing date	Oct 31, 2013
Priority date	Oct 31, 2013
Publication date	May 10, 2016
Grant date	May 10, 2016

Abstract

A method of load balancing implemented at a data network is disclosed. The data network contains a number of data plane nodes and a number of clusters of a control node. The method starts with deriving a graph from a topology of the data plane nodes, where the graph contains vertices, each representing one of the data plane nodes, and edges, each representing a connection between a pair of data plane nodes. The method continues with partitioning the graph into a number of sub-graphs, where the partition aims at minimizing connectivity among the number of sub-graphs, and where the number of sub-graphs equal to the number of clusters. The control node then assigns each cluster to one of the data plane nodes, where each cluster is assigned to one or more data plane node partitioned into the same sub-graph.

First claim

What is claimed is:

1. A method implemented at a data network, wherein the data network contains a plurality of data plane nodes carrying user traffic and a plurality of clusters of a control node managing the plurality of data plane nodes, the method comprising:
learning the topology of the plurality of data plane nodes based on one of: registration of the data plane nodes at the control node, and automatic discovery of the data plane nodes at the control node;
deriving a graph from a topology of the plurality of data plane nodes, wherein the graph contains vertices, each representing one of the plurality of data plane nodes, and edges, each representing a connection between a pair of data plane nodes within the plurality of data plane nodes;
partitioning the graph into a plurality of sub-graphs, each sub-graph containing one or more vertices and edges representing data plane nodes and connections between the data plane nodes respectively, wherein the partition aims at minimizing connectivity among the plurality of sub-graphs, and wherein the plurality of sub-graphs equal to the plurality of clusters; and
assigning each cluster to one of the plurality of data plane nodes, wherein each cluster is assigned to one or more data plane node partitioned into a same sub-graph.

2. The method of claim 1 , wherein partitioning the graph into the plurality of sub-graphs further aims making each sub-graph contains substantially same number of vertices.

3. The method of claim 1 , wherein assigning each cluster is performed by a load balancer of a software defined network (SDN) controller, and wherein the control node is the SDN controller.

4. The method of claim 1 , wherein the edges of the graph carries weights based on at least one of bandwidth and latency of links connecting the plurality of data plane nodes.

5. A method implemented at a data network, wherein the data network contains a plurality of data plane nodes carrying user traffic and at least a cluster of a control node managing the plurality of data plane nodes, the cluster containing a plurality of physical servers, the method comprising:
learning the topology of the plurality of data plane nodes prior to deriving the graph based on one of:
registration of the data plane nodes at the control node, and
automatic discovery of the data plane nodes at the control node;
deriving a graph from a topology of the plurality of data plane nodes, wherein the graph contains vertices, each representing one of the plurality of data plane nodes, and edges, each representing a connection between a pair of data plane nodes within the plurality of data plane nodes;
partitioning the graph into a plurality of sub-graphs, each sub-graph containing one or more vertices and edges representing data plane nodes and connections between the data plane nodes respectively, wherein the partition aims at minimizing connectivity among the plurality of sub-graphs, wherein the plurality of sub-graphs equal to the plurality of physical servers; and
assigning each physical server to one of the plurality of data plane nodes, wherein each physical server is assigned to one or more data plane node partitioned into a same sub-graph.

6. The method of claim 5 , wherein each data plane node has a plurality of IP connections to the control node through a plurality of IP addresses of the control node, wherein each of the plurality of IP addresses corresponds to one of the plurality of physical servers, wherein one physical server serves as a master server for the data plane node, and the rest of the plurality of physical servers having corresponding IP addresses serve as slave servers.

7. The method of claim 6 , wherein assigning physical server to one of the plurality of data plane nodes comprises setting the assigned physical server as the master server.

8. The method of claim 5 , wherein the control node is a software defined network (SDN) controller.

9. A network device coupled to a data network, wherein the data network contains a plurality of data plane nodes carrying user traffic and a plurality of clusters of a control node managing the plurality of data plane nodes, the network device comprising:
a graph partitioner configured to derive a graph from a topology of the plurality of data plane nodes, wherein the graph contains vertices, each representing one of the plurality of data plane nodes, and edges, each representing a connection between a pair of data plane nodes within the plurality of data plane nodes,
the graph partitioner further configured to partition the graph into a plurality of sub-graphs, each sub-graph containing one or more vertices and edges representing data plane nodes and connections between the data plane nodes respectively, wherein the partition aims at minimizing connectivity among the plurality of sub-graphs, and wherein the plurality of sub-graphs equal to the plurality of clusters, and
a control allocator configured to assign each cluster to one of the plurality of data plane nodes, wherein each cluster is assigned to one or more data plane node partitioned into a same sub-graph;
wherein the network device coupled to a data plane node topology unit and a controller database,
wherein the data plane node topology unit comprises one of:
a data plane node registration unit configured to register the plurality of data plane nodes at the control node, and
a data plane node topology discovery unit configured to automatically discover the plurality of data plane nodes at the control node, wherein topology of the plurality of data plane nodes is learned from the registration or discovery, and
wherein the controller database configured to save the learned topology of the plurality of data plane nodes.

10. The network device of claim 9 , wherein partitioning the graph into the plurality of sub-graphs further aims making each sub-graph contains substantially same number of vertices.

11. The network device of claim 9 , wherein the network device is a load balancer of a software defined network (SDN) controller, and wherein the control node is the SDN controller.

12. The network device of claim 9 , wherein the edges of the graph carries weights based on at least one of bandwidth and latency of links connecting the plurality of data plane nodes.

13. A network device coupled to a data network, wherein the data network contains a plurality of data plane nodes carrying user traffic and at least a cluster of a control node managing the plurality of data plane nodes, the cluster containing a plurality of physical servers, the network device comprising:
a control assignment processor, including:
a graph partitioner configured to derive a graph from a topology of the plurality of data plane nodes, wherein the graph contains vertices, each representing one of the plurality of data plane nodes, and edges, each representing a connection between a pair of data plane nodes within the plurality of data plane nodes,
the graph partitioner further configured to partition the graph into a plurality of sub-graphs, each sub-graph containing one or more vertices and edges representing data plane nodes and connections between the data plane nodes respectively, wherein the partition aims at minimizing connectivity among the plurality of sub-graphs, wherein the plurality of sub-graphs equal to the plurality of physical servers, and
a control allocator configured to assign each physical server to one of the plurality of data plane nodes, wherein each physical server is assigned to one or more data plane node partitioned into a same sub-graph; and
a data plane node topology unit, including at least one of:
a data plane node registration uni

Assignees

• Ericsson Telefon Ab L M

Inventors

• Anand Prashant
• Rajamani Srikar

Classifications

• H04L47/125 Primary

  by balancing the load, e.g. traffic engineering · CPC title

• H04L41/122 Primary

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

• H04L67/1025

  Dynamic adaptation of the criteria on which the server selection is based · CPC title

• H04L41/12

  Discovery or management of network topologies · CPC title

• H04L41/0893

  Assignment of logical groups to network elements · CPC title