Discovering MPLS VPN services in a network

• US 20070280241A1
• Filed: 06/02/2006
• Published: 12/06/2007
• Est. Priority Date: 06/02/2006
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Verma, Alok
• Granted Patent: US 7,593,352 B2
• Time in Patent Office: Days
• US Class Current: 370/392
• 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 41/0213 Standardised network management protocols, e.g. simple network management protocol [SNMP]
• CPC Class Codes: H04L 41/0233 Object-oriented techniques, for representation of network management data, e.g. common object request broker architecture [CORBA]
• 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 45/02 Topology update or discovery
• 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]
• CPC Class Codes: H04W 40/00 Communication routing or communication path finding

Abstract

Discovering a network service topology of a virtual private network (VPN) that uses multiprotocol label switching (MPLS) comprises receiving route target values from a virtual private network (VPN) route forwarding table (VRF table) of a networking device; determining and storing in a table one or more link pairs based on the route target values, wherein each of the link pairs indicates a connection between a first site and a second site within the VPN; creating a set of VPN objects based on an association between a first VPN object and the one or more link pairs stored in the table, wherein each of the VPN objects includes information indicating connectivity between a subset of sites from a plurality of sites within the VPN; and determining the topology for the first VPN object based on applying one or more topology rules to the subset of sites within the first VPN object.

Claims

1. A machine-implemented method of discovering a network service topology, comprising:

receiving a plurality of route target values from a virtual private network (VPN) route forwarding table (VRF table) of a networking device;

determining and storing in a table one or more link pairs that are determined based on the route target values, wherein each of the link pairs indicates a logical connection between a first site and a second site within the VPN;

creating a set of VPN objects based on an association between a first VPN object and the one or more link pairs stored in the table, wherein each of the VPN objects includes information indicating connectivity between a subset of sites from a plurality of sites within the VPN; and

determining the topology for the first VPN object based on applying one or more topology rules to the subset of sites within the first VPN object.

2. A method as recited in claim 1, wherein determining and storing link pairs further comprises determining a first link pair based on a route target entry in a corresponding VRF table of a switch of a network.

3. A method as recited in claim 2, wherein the route target entry corresponds to a route target value imported into the corresponding VRF table for the first site.

4. A method as recited in claim 2, wherein the route target entry corresponds to a route target value exported from the corresponding VRF table for the first site.

5. A method as recited in claim 1, further comprising:

inserting a first route-target information into a first table for all imported route-target values within a VRF;

determining if the first route-target information is contained in a second table; and

creating and inserting into a third table, a first link pair when the first route-target information is also contained in the second table and the first link pair does not already exist in the table, and otherwise setting a marker indicating said first link pair is bidirectional.

6. A method as recited in claim 1, further comprising:

inserting a first route-target information into a first table for all export route-target values within a VRF;

determining if the first route-target information is contained in a second table; and

creating and inserting into a third table, a first link pair when the first route-target information is also contained in the second table and the first link pair does not already exist, and otherwise setting a marker indicating said first link pair is bidirectional.

7. A method as recited in claim 1, further comprising storing, for the subset of sites from the plurality of sites within the VPN, connectivity information associated with each of the sites within the subset of sites.

8. A method as recited in claim 1 wherein creating a set of VPN objects further comprises:

determining, for the first site within one or more link pairs retrieved from the table, whether a VPN object is associated with the first site;

creating a new VPN object when no VPN object is associated with the first site; and

inserting all sites associated with the first site into the VPN object.

9. A method as recited in claim 1, wherein a VPN object is a hashmap in which a key comprises information representing a first site and a value comprises information representing a plurality of sites connected to the first site.

10. A method as recited in claim 1, wherein one of the topology rules specifies that the topology of the VPN object is a full mesh topology when a first specified subset of sites equals the subset of sites within the first VPN object.

11. The method of claim 10, wherein the first specified subset of sites comprises all key values in a plurality of hashmaps associated with the set of VPN objects.

12. The method of claim 1, wherein the subset of sites within the first VPN object comprises sites that are connected to the first VPN object.

13. A method as recited in claim 1 wherein one of the topology rules specifies that the topology of the VPN object is a partial mesh topology when the subset of sites within the first VPN object is null.

14. A method as recited in claim 1, wherein one of the topology rules specifies that the topology of the VPN object is a hub and spoke topology when a first specified subset of sites equals the subset of sites within the first VPN object and when an intersection of a second specified subset of sites equals the subset of sites within the first VPN object.

15. The method of claim 14 wherein the second specified subset of sites comprises all sites that are not key values within a plurality of hashmaps associated with the set of VPN objects but not contained in the subset of sites within the first VPN Object.

16. A computer-readable tangible medium carrying instructions which, when executed by one or more processors, cause performing:

receiving a plurality of route target values from a virtual private network (VPN) route forwarding table (VRF table) of a networking device;

determining and storing in a table one or more link pairs that are determined based on the route target values, wherein each of the link pairs indicates a logical connection between a first site and a second site within the VPN;

creating a set of VPN objects based on an association between a first VPN object and the one or more link pairs stored in the table, wherein each of the VPN objects includes information indicating connectivity between a subset of sites from a plurality of sites within the VPN; and

determining the topology for the first VPN object based on applying one or more topology rules to the subset of sites within the first VPN object.

17. An apparatus, comprising:

one or more processors;

one or more network interfaces communicatively coupled to the processors and a network;

a computer-readable tangible storage medium coupled to the one or more processors and carrying instructions which, when executed by the one or more processors, cause performing;

receiving a plurality of route target values from a virtual private network (VPN) route forwarding table (VRF table) of a networking device;

determining and storing in a table one or more link pairs that are determined based on the route target values, wherein each of the link pairs indicates a logical connection between a first site and a second site within the VPN;

creating a set of VPN objects based on an association between a first VPN object and the one or more link pairs stored in the table, wherein each of the VPN objects includes information indicating connectivity between a subset of sites from a plurality of sites within the VPN; and

determining the topology for the first VPN object based on applying one or more topology rules to the subset of sites within the first VPN object.

18. The apparatus of claim 17, wherein the instructions for determining and storing link pairs further comprise instructions which when executed cause determining a first link pair based on a route target entry in a corresponding VRF table of a switch of a network.

19. The apparatus of claim 18, wherein the route target entry corresponds to a route target value imported into the corresponding VRF table for the first site.

20. The apparatus of claim 18, wherein the route target entry corresponds to a route target value exported from the corresponding VRF table for the first site.

21. The apparatus of claim 17, further comprising instructions which when executed cause:

inserting a first route-target information into a first table for all imported route-target values within a VRF;

determining if the first route-target information is contained in a second table; and

creating and inserting into a third table, a first link pair when the first route-target information is also contained in the second table and the first link pair does not already exist in the table, and otherwise setting a marker indicating said first link pair is bidirectional.

22. The apparatus of claim 17, further comprising instructions which when executed cause:

inserting a first route-target information into a first table for all export route-target values within a VRF;

determining if the first route-target information is contained in a second table; and

creating and inserting into a third table, a first link pair when the first route-target information is also contained in the second table and the first link pair does not already exist, and otherwise setting a marker indicating said first link pair is bidirectional.

23. The apparatus of claim 17, further comprising instructions which when executed cause storing, for the subset of sites from the plurality of sites within the VPN, connectivity information associated with each of the sites within the subset of sites.

24. The apparatus of claim 17 wherein the instructions for creating a set of VPN objects further comprise instructions which when executed cause:

determining, for the first site within one or more link pairs retrieved from the table, whether a VPN object is associated with the first site;

creating a new VPN object when no VPN object is associated with the first site; and

inserting all sites associated with the first site into the VPN object.

25. The apparatus of claim 17, wherein a VPN object is a hashmap in which a key comprises information representing a first site and a value comprises information representing a plurality of sites connected to the first site.

26. The apparatus of claim 17, wherein one of the topology rules specifies that the topology of the VPN object is a full mesh topology when a first specified subset of sites equals the subset of sites within the first VPN object.

27. The apparatus of claim 26, wherein the first specified subset of sites comprises all key values in a plurality of hashmaps associated with the set of VPN objects.

28. The apparatus of claim 17, wherein the subset of sites within the first VPN object comprises sites that are connected to the first VPN object.

29. The apparatus of claim 17 wherein one of the topology rules specifies that the topology of the VPN object is a partial mesh topology when the subset of sites within the first VPN object is null.

30. The apparatus of claim 17, wherein one of the topology rules specifies that the topology of the VPN object is a hub and spoke topology when a first specified subset of sites equals the subset of sites within the first VPN object and when an intersection of a second specified subset of sites equals the subset of sites within the first VPN object.

31. An apparatus for discovering a network service topology, comprising:

means for receiving a plurality of route target values from a virtual private network (VPN) route forwarding table (VRF table) of a networking device;

means for determining and storing in a table one or more link pairs that are determined based on the route target values, wherein each of the link pairs indicates a logical connection between a first site and a second site within the VPN;

means for creating a set of VPN objects based on an association between a first VPN object and the one or more link pairs stored in the table, wherein each of the VPN objects includes information indicating connectivity between a subset of sites from a plurality of sites within the VPN; and

means for determining the topology for the first VPN object based on applying one or more topology rules to the subset of sites within the first VPN object.

32. The apparatus of claim 31, wherein the means for determining and storing link pairs further comprises means for determining a first link pair based on a route target entry in a corresponding VRF table of a switch of a network.

33. The apparatus of claim 32, wherein the route target entry corresponds to a route target value imported into the corresponding VRF table for the first site.

34. The apparatus of claim 32, wherein the route target entry corresponds to a route target value exported from the corresponding VRF table for the first site.

35. The apparatus of claim 31, further comprising:

means for inserting a first route-target information into a first table for all imported route-target values within a VRF;

means for determining if the first route-target information is contained in a second table; and

means for creating and inserting into a third table, a first link pair when the first route-target information is also contained in the second table and the first link pair does not already exist in the table, and otherwise setting a marker indicating said first link pair is bidirectional.

36. The apparatus of claim 31, further comprising:

means for inserting a first route-target information into a first table for all export route-target values within a VRF;

means for determining if the first route-target information is contained in a second table; and

means for creating and inserting into a third table, a first link pair when the first route-target information is also contained in the second table and the first link pair does not already exist, and otherwise setting a marker indicating said first link pair is bidirectional.

37. The apparatus of claim 31, further comprising means for storing, for the subset of sites from the plurality of sites within the VPN, connectivity information associated with each of the sites within the subset of sites.

38. The apparatus of claim 31 wherein the means for creating a set of VPN objects further comprises:

means for determining, for the first site within one or more link pairs retrieved from the table, whether a VPN object is associated with the first site;

means for creating a new VPN object when no VPN object is associated with the first site; and

means for inserting all sites associated with the first site into the VPN object.

39. The apparatus of claim 31, wherein a VPN object is a hashmap in which a key comprises information representing a first site and a value comprises information representing a plurality of sites connected to the first site.

40. The apparatus of claim 31, wherein one of the topology rules specifies that the topology of the VPN object is a full mesh topology when a first specified subset of sites equals the subset of sites within the first VPN object.

41. The method of claim 40, wherein the first specified subset of sites comprises all key values in a plurality of hashmaps associated with the set of VPN objects.

42. The method of claim 31, wherein the subset of sites within the first VPN object comprises sites that are connected to the first VPN object.

43. The apparatus of claim 31 wherein one of the topology rules specifies that the topology of the VPN object is a partial mesh topology when the subset of sites within the first VPN object is null.

44. The apparatus of claim 31, wherein one of the topology rules specifies that the topology of the VPN object is a hub and spoke topology when a first specified subset of sites equals the subset of sites within the first VPN object and when an intersection of a second specified subset of sites equals the subset of sites within the first VPN object.

45. The method of claim 44 wherein the second specified subset of sites comprises all sites that are not key values within a plurality of hashmaps associated with the set of VPN objects but not contained in the subset of sites within the first VPN Object.