Controller driven designated forwarder election in EVPN networks for optimized load distribution

Patent metadata

Field	Value
Publication number	US-11418403-B2
Application number	US-202016934731-A
Country	US
Kind code	B2
Filing date	Jul 21, 2020
Priority date	Jul 21, 2020
Publication date	Aug 16, 2022
Grant date	Aug 16, 2022

Abstract

A method is performed by a network controller. The method includes receiving information that defines a topology of a network having Ethernet Segments configured with virtual local area networks (VLANs) and including provider edges that are multi-homed to customer edges. The method further comprises, based on the topology, determining for the VLANs particular provider edges among the provider edges that are to operate as designated forwarders of traffic for the VLANs, such that the VLANs are load balanced across the particular provider edges. The method also includes programming the particular provider edges as the designated forwarders of traffic for the VLANs.

First claim

What is claimed is:

1. A method comprising:
at a network controller, receiving information that defines a topology of a network having Ethernet Segments configured with virtual local area networks (VLANs) and including provider edges that are multi-homed to customer edges;
constructing, from the topology, a bipartite graph that include first vertices to represent the VLANs, second vertices to represent the provider edges, and edges to represent matchings of the VLANs to the provider edges;
using a semi-matching algorithm, determining matchings of the VLANs to particular provider edges of the provider edges along cost-reducing paths of the bipartite graph having vertices among the second vertices that meet predetermined criteria with respect to an in-degree of edges at the vertices, wherein the particular provider edges are to operate as designated forwarders across which traffic for the VLANs is load balanced; and
programming the particular provider edges as the designated forwarders for the VLANs.

2. The method of claim 1 , wherein:
programming includes programming the particular provider edges as the designated forwarders of the traffic for the VLANs with the matchings to the particular provider edges.

3. The method of claim 1 , wherein the information includes capabilities of the provider edges, and the method further comprises:
assigning relative weights to the provider edges based on the capabilities; and
replicating one or more of the provider edges in the bipartite graph according to the relative weights, to produce one or more replica provider edges in the bipartite graph,
wherein determining the matchings includes determining the matchings based on the provider edges and the one or more replica provider edges in the bipartite graph.

4. The method of claim 3 , wherein:
the capabilities include processing powers of the provider edges; and
assigning relative weights includes assigning relative weights to the provider edges based on the processing powers.

5. The method of claim 1 , wherein the information includes link capacities of interfaces of the Ethernet Segments, and the method further comprises;
assigning relative weights to the interfaces based on the link capacities; and
replicating one or more of the interfaces in the bipartite graph according to the relative weights, to produce one or more replica interfaces in the bipartite graph,
wherein determining the matchings includes determining the matchings based on the interfaces and the one or more replica interfaces in the bipartite graph.

6. The method of claim 5 , wherein the interfaces are represented as respective (provider edge, Ethernet segment identifier) tuples.

7. The method of claim 1 , wherein the provider edges are configured to forward broadcast, unknown unicast, and multicast traffic originating from source equipment.

8. The method of claim 1 , wherein:
the bipartite graph includes unmatched edges and matched edges to represent the VLANs as being unmatched and matched to the provider edges, respectively; and
the semi-matching algorithm defines (i) an alternating path in the bipartite graph as a path that alternates between unmatched and unmatched edges, and (ii) a cost-reducing path as an alternating path in which a difference in an in-degree of matched edges of a start vertex and an end vertex of the cost-reducing path is at least two.

9. The method of claim 1 , wherein programming the particular provider edges as the designated forwarders includes notifying the particular provider edges of their designated forwarder status via Border Gate Protocol (BGP) notifications.

10. The method of claim 1 , wherein the Ethernet Segments share at least some of the provider edges.

11. The method of claim 1 , wherein the Ethernet Segments are configured with respective sets of VLANs and share a common provider edge among the provider edges, and determining includes electing the common provider edge as a designated forwarder for a given VLAN in the respective sets of VLANs as a function of all of the respective sets of VLANs.

12. An apparatus comprising:
a network interface unit to communicate with a network; and
a processor coupled to the network interface unit and configured to operate as a network controller, the processor configured to perform:
receiving information that defines a topology of a network having Ethernet Segments configured with virtual local area networks (VLANs) and including provider edges that are multi-homed to customer edges;
constructing, from the topology, a bipartite graph that include first vertices to represent the VLANs, second vertices to represent the provider edges, and edges to represent matchings of the VLANs to the provider edges;
using a semi-matching algorithm, determining matchings of the VLANs to particular provider edges of the provider edges along cost-reducing paths of the bipartite graph having vertices among the second vertices that meet predetermined criteria with respect to an in-degree of edges at the vertices, wherein the particular provider edges are to operate as designated forwarders across which traffic for the VLANs is load balanced; and
programming the particular provider edges as the designated forwarders for the VLANs.

13. The apparatus of claim 12 , wherein:
the processor is configured to perform programming by programming the particular provider edges as the designated forwarders of the traffic for the VLANs with the matchings to the particular provider edges.

14. The apparatus of claim 12 , wherein the information includes capabilities of the provider edges, and the processor is further configured to perform:
assigning relative weights to the provider edges based on the capabilities; and
replicating one or more of the provider edges in the bipartite graph according to the relative weights, to produce one or more replica provider edges in the bipartite graph,
wherein the processor is configured to perform determining the matchings by determining the matchings based on the provider edges and the one or more replica provider edges in the bipartite graph.

15. The apparatus of claim 12 , wherein the provider edges are configured to forward broadcast, unknown unicast, and multicast traffic originating from source equipment.

16. The apparatus of claim 12 , wherein:
the bipartite graph includes unmatched edges and matched edges to represent the VLANs as being unmatched and matched to the provider edges, respectively; and
the semi-matching algorithm defines (i) an alternating path in the bipartite graph as a path that alternates between unmatched and unmatched edges, and (ii) a cost-reducing path as an alternating path in which a difference in an in-degree of matched edges of a start vertex and an end vertex of the cost-reducing path is at least two.

17. The apparatus of claim 12 , wherein the Ethernet Segments share at least some of the provider edges.

18. A non-transitory computer readable medium encoded with instructions that, when executed by a processor, cause the processor of a network controller to perform:
receiving information that defines a topology of a network having Ethernet Segments configured with virtual local area networks (VLANs) and including provider edges that are multi-homed to customer edges;
constructing, from the topology, a bipartite graph that include first vertices to represent the VLANs, second vertices to represent the provider edges, and edges to represent matchings of the VLANs to the provider edges;
using a semi-matching algorithm, determining matchings of the VLANs to parti

Assignees

• Cisco Tech Inc

Inventors

• Mohanty Satya Ranjan
• Ghosh Mrinmoy
• Rao Dhananjaya
• Gulrajani Sameer R
• Mishra Mankamana Prasad

Classifications

• H04L45/48

  Routing tree calculation · CPC title

• H04L45/22

  Alternate routing · CPC title

• H04L41/122

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

• H04L12/4641 Primary

  Virtual LANs, VLANs, e.g. virtual private networks [VPN] (LAN interconnection over a bridge based backbone H04L12/462; encapsulation techniques H04L12/4633; routing of packets H04L45/00; packet switches H04L49/00; virtual private networks for security H04L63/0272) · CPC title

• H04L45/66

  Layer 2 routing, e.g. in Ethernet based MAN's · CPC title