Discovery of border gateway protocol (BGP) multi-protocol label switching (MPLS) virtual private networks (VPNs)

• US 20060002401A1
• Filed: 06/30/2004
• Published: 01/05/2006
• Est. Priority Date: 06/30/2004
• Status: Active Grant

• Current Assignee: RPX Corporation
• Original Assignee: Alcatel-Lucent USA, Inc. (Nokia Corporation)
• Inventors: Rangarajan, Sampath, Mukherjee, Sarit, Naik, Tejas
• Granted Patent: US 7,400,611 B2
• Time in Patent Office: Days
• US Class Current: 370/401
• CPC Class Codes: H04L 12/4641 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 Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/033 by updating distance vector protocols
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]

Abstract

A method and apparatus for identifying virtual private networks (VPNs) in a network of a service provider. The method and apparatus includes generating a VPN routing forwarding—route target (VRF-RT) table for the network. From the VRF-RT table, at least one of a VRF-VRF table and a VRF connectivity graph is generated. From the VRF-RT table, a set of atomic full-mesh components are identified, and from the at least one of a VRF-VRF table and a VRF connectivity graph, at least one set of other types of VPN components are identified, such as atomic single hub-and-spoke components, molecular multi-hub-and-spoke components, composite full-mesh components, composite single hub-and-spoke components, and/or composite multi hub-and-spoke components.

Claims

1. A method of identifying virtual private networks (VPNs) in a network of a service provider, comprising:

generating a VPN routing forwarding—

route target (VRF-RT) table for said network;

generating at least one of a VRF-VRF table and a VRF connectivity graph from said VRF-RT table;

determining, from said VRF-RT table, a set of atomic full-mesh components;

determining, from said at least one of a VRF-VRF table and a VRF connectivity graph, at least one set of other types of VPN components.

2. The method of claim 1, wherein said other types of VPN components comprise at least one of atomic single hub-and-spoke components, molecular multi-hub-and-spoke components, composite full-mesh components, composite single hub-and-spoke components, and composite multi hub-and-spoke components.

3. The method of claim 2, wherein an atomic full-mesh component is a full-mesh topology having one route target (RT), an atomic single hub-and-spoke component is a largest single hub-and-spoke topology having two RTs, and a molecular multi-hub-and-spoke component is a largest multi-hub-and-spoke topology having two RTs without restriction of overlapping links and nodes with atomic components.

4. The method of claim 1, wherein said generating said VRF-RT table comprises:

identifying n-VRF tables associated with a plurality of nodes in the network;

identifying m-RTs in said network, where m and n are integers greater than 1; and

determining unidirectional and bi-directional communications between said nodes based on said VRF tables and RTs.

5. The method of claim 1, wherein said generating at least one of a VRF-VRF table and a VRF connectivity graph comprises:

identifying export and import RT values associated with each of said nodes in said network; and

identifying in-degree and out-degree links therebetween said nodes.

6. The method of claim 5, further comprising removing unidirectional links from said graph.

7. The method of claim 5, further comprising reducing redundant RTs from said VRF-VRF table.

8. The method of claim 2, wherein determining each atomic full-mesh component of a set of atomic full-mesh components comprises:

identifying at least two nodes associated with a selected RT of said VRF-RT table that both export and import said selected RT.

9. The method of claim 8, further comprising:

removing at least one of table entries and links associated with said set of atomic full-mesh components respectively from said at least one of a VRF-VRF table and a VRF connectivity graph.

10. The method of claim 2, wherein determining each atomic single hub-and spoke component of a set of atomic single hub-and-spoke components comprises:

determining a set of candidate hubs from said graph;

determining all distinct RTs used to export from each candidate hub;

identifying a set of spokes for each distinct RT;

determining, for each set of spokes, a largest subset of nodes that use a common RT to export to the hub;

determining a hub from the set of candidate hubs having a largest in-degree value; and

selecting one of said hubs from said set of candidate hubs.

11. The method of claim 10, wherein said selecting one of said hubs from said set of candidate hubs comprises selecting a candidate hub from a set of preferred hubs in an instance where multiple hubs in the set of candidate hubs qualify.

12. The method of claim 11, further comprising:

generating said set of preferred hubs from said set of candidate hubs, where an RT used for determining an atomic full-mesh component is also associated with at least one node that imports that RT.

13. The method of claim 11, wherein said selecting a candidate hub from a set of preferred hubs comprises randomly selecting one of said preferred hubs in an instance where there are multiple preferred hubs.

14. The method of claim 11, wherein said selecting one of said hubs from said set of candidate hubs comprises randomly selecting one of said hubs in an instance where said set of preferred hubs is empty.

15. The method of claim 10, further comprising:

removing at least one of table entries and links associated with the set of single hub-and-spoke components respectively from said at least one of a VRF-VRF table and a VRF connectivity graph, and

removing singleton nodes from said set of candidate hubs.

16. The method of claim 2, wherein determining a molecular multi hub-and-spoke component from a set of molecular multi hub-and-spoke components comprises:

identifying a new full-mesh component from said set of atomic full-mesh components, wherein node members of said new full-mesh component are associated with a preferred hub of said set of preferred hubs;

selecting a full-mesh component;

determining if each of said nodes in the full-mesh component is a hub in the single hub-and-spoke set; and

determining, for each atomic single hub-and spoke, whether an RT exported by a hub to its spokes is identical, the RT exported is used for creating said full-mesh component, and an RT imported by the hub from all its spokes is identical.

17. The method of claim 16, further comprising:

assigning identified full-mesh and associated single hub-and-spoke components to a set of multi hub-and spoke components; and

removing said identified full-mesh and associated single hub-and-spoke components respectively from a set full-mesh components and a set of single hub-and spoke components.

18. The method of claim 2, further comprising:

determining whether a complex VPN is a composite full-mesh component.

19. The method of claim 18, wherein said determining whether a complex VPN is a composite full-mesh component comprises:

determining, from said VRF-VRF table, whether each entry in an upper triangular matrix formed above a diagonal of said VRF-VRF table has a corresponding RT entry in a lower triangular matrix formed below said diagonal of said VRF-VRF table.

20. The method of claim 2, further comprising:

determining whether a complex VPN is a composite single hub-and-spoke component.

21. The method of claim 20, wherein said determining whether a complex VPN is a composite single hub-and-spoke component comprises:

determining that a set of all atomic full-mesh components is empty; and

defining said VPN network as a composite single hub-and-spoke topology in an instance where all single hub-and-spoke components in the set of atomic single hub-and-spoke components have a common hub.

22. The method of claim 2, further comprising:

determining whether a complex VPN is a composite multi hub-and-spoke component.

23. The method of claim 22, wherein said determining whether a complex VPN is a composite multi hub-and-spoke component comprises:

identifying, from the VRF-VRF table, a composite full mesh component being largest in size;

identifying, from a set of all atomic hub and spokes, all the composite single hub-and-spoke components;

identifying, from all the composite hub-and-spoke components, that all the hubs belong to the composite full mesh component, and a spoke set of each composite single hub-and-spoke set are identical.

24. Apparatus for identifying virtual private networks (VPNS) in a network of a service provider, comprising:

means for generating a VPN routing forwarding—

route target (VRF-RT) table for said network;

means for generating at least one of a VRF-VRF table and a VRF connectivity graph from said VRF-RT table;

means for determining, from said VRF-RT table, a set of atomic full-mesh components;

means for determining, from said at least one of a VRF-VRF table and a VRF connectivity graph, at least one set of other types of VPN components.

25. The apparatus of claim 24, wherein said other types of VPN components comprise at least one of atomic single hub-and-spoke components, molecular multi-hub-and-spoke components, composite full-mesh components, composite single hub-and-spoke components, and composite multi hub-and-spoke components.

26. The apparatus of claim 25, wherein an atomic full-mesh component is a full-mesh topology having one route target (RT), an atomic single hub-and-spoke component is a largest single hub-and-spoke topology having two RTs, and a molecular multi-hub-and-spoke component is a largest multi-hub-and-spoke topology having two RTs without restriction of overlapping links and nodes with atomic components.

27. The apparatus of claim 25, wherein determining each atomic full-mesh component of a set of atomic full-mesh components comprises:

means for identifying at least two nodes associated with a selected RT of said VRF-RT table that both export and import said selected RT.

28. The method of claim 25, wherein determining each atomic single hub-and spoke component of said set of atomic single hub-and-spoke components comprises:

means for determining a set of candidate hubs from said graph;

means for determining all distinct RTs used to export from each candidate hub;

means for identifying a set of spokes for each distinct RT;

means for determining, for each set of spokes, a largest subset of nodes that use a common RT to export to the hub;

means for determining a hub from the set of candidate hubs having a largest in-degree value; and

means for selecting one of said hubs from said set of candidate hubs.

29. The apparatus of claim 25, wherein determining a molecular multi hub-and-spoke component from a set of molecular multi hub-and-spoke components comprises:

means for identifying a new full-mesh component from said set of atomic full-mesh components, wherein node members of said new full-mesh component are associated with a preferred hub of said set of preferred hubs;

means for selecting a full-mesh component;

means for determining if each of said nodes in the full-mesh component is a hub in the single hub-and-spoke set; and

means for determining, for each atomic single hub-and spoke, whether an RT exported by a hub to its spokes is identical, the RT exported is used for creating said full-mesh component, and an RT imported by the hub from all its spokes is identical.

30. The apparatus of claim 25, further comprising:

means for determining whether a complex VPN is one of a composite full-mesh component, a composite single hub-and-spoke component, and a composite multi hub-and-spoke component.