Abstract:
A method and apparatus for determining and identifying types of Virtual Private Networks is disclosed. The method comprises the steps of representing the network by a model containing a plurality of object classes, evaluating an import/export relationship of a first one and a second one of the object classes and identifying the network type based on the evaluated relationship.

Description:
CLAIM OF PRIORITY  
       [0001]     This application claims the benefit, pursuant to 35 USC §119(e), of the earlier filing date of the Provisional Patent Application Ser. No. 60/505,802, entitled “Model-Based Discovery of Multi-Protocol Label Switching Virtual Private Networks, filed on Sep. 25, 2003, the contents of which are incorporated by reference herein.  
       RELATED APPLICATIONS  
       [0002]     This application is related to concurrently-filed:  
         [0003]     U.S. patent application Ser. No. ______ entitled “Model-Based Method and Apparatus for Determining MPLS Network Properties;” and  
         [0004]     U.S. patent application Ser. No. ______ entitled “Method and Apparatus for Modeling and Analyzing MPLS and Virtual Private Networks,” the contents of both of which are incorporated by reference herein. 
     
    
     FIELD OF THE INVENTION  
       [0005]     The invention relates generally to computer networks, and more specifically to systems and methods for modeling and identifying Virtual Private Network (VPN) topologies, memberships and member roles.  
       BACKGROUND OF THE INVENTION  
       [0006]     The concepts, terms, and acronyms of Virtual Private Network (VPN) are well-known in the art. For example, the memorandum entitled  BGP/MPLS VPNs , E. Rosen and Y. Rekhter, RFC 2547, March 1999, Internet Engineering Task Force (IETF), is an example of the literature regarding VPNs.  
         [0007]     The ability to analyze VPNs has been limited by the network models that have been employed. For example, one model uses a Common Information Model (CIM) that defined objects and relationships. (see  Common Information Model: Implementing the Object Model for Enterprise Management , Bumpus, et al., John Wiley &amp; Sons, December 1999, ISBN: B00007FY8X). This model is limited by the pre-defined and standard objects and relationships defined in the Common Information Model (CIM). For example, one cannot easily capture the relationship between a VPN Routing and Forwarding Table (VRF) and a RouteTarget (RT). (See, for example,  BGP/MPLS VPNs , E. Rosen and Y. Rekhter, RFC2547bis, IETF, July 2000.)  
         [0008]     In a second model, the definition of MPLS and VPN Management Information Bases (MIBs) are established. (See, for example,  SNMP, SNMPv 2,  SNMPv 3,  and RMON  1  and  2 (3 rd Edition ), William Stallings, Addison-Wesley Pub Co, December 1998, pages 71-162 ISBN: 0201485346). However, MIBs typically do not capture relationships between objects. For example the MPLS end-to-end Label-Switched Path (LSP) is difficult to represent explicitly in a MIB.  
         [0009]     The lack of a systematic model specifically suited for the MPLS and/or VPN objects and relationships limits several forms of important analysis. For example, it is difficult to determine the members of each VPN; what is the role of each VPN member; what is the type of each VPN or sub-set of the VPN.  
         [0010]     Hence there is a need in the industry for a method and system for analyzing VPN systems that overcomes known deficiencies in identifying VPN components and the VPN topology.  
       SUMMARY OF THE INVENTION  
       [0011]     A method and apparatus for determining and identifying types of Virtual Private Networks is disclosed. The method comprises the steps of representing the network by a model containing a plurality of object classes, evaluating an import/export relationship of a first one and a second one of the object classes and identifying the network type based on the evaluated relationship. 
     
    
     DETAILED DESCRIPTION OF THE FIGURES  
       [0012]      FIG. 1  illustrates a logical view of a conventional VPN network;  
         [0013]      FIG. 2  illustrates a model representation of VPNs in accordance with the principles of the invention;  
         [0014]      FIG. 3  illustrates an example of a model-ed representation of a VPN;  
         [0015]      FIGS. 4   a - 4   d  illustrate examples of model-ed representations of VPN topologies;  
         [0016]      FIG. 5  illustrates an example of identifying VPN topologies in accordance with the principles of the invention;  
         [0017]      FIGS. 6   a - 6   d  illustrate an example of the application of the VPN model with regard to a physical network in accordance with the principles of the invention; and  
         [0018]      FIG. 7  illustrates a system for implementing the processing shown herein. 
     
    
       [0019]     It is to be understood that these drawings are solely for purposes of illustrating the concepts of the invention and are not intended as a definition of the limits of the invention. The embodiments shown in the figures herein and described in the accompanying detailed description are to be used as illustrative embodiments and should not be construed as the only manner of practicing the invention. Also, the same reference numerals, possibly supplemented with reference characters where appropriate, have been used to identify similar elements.  
       DETAILED DESCRIPTION  
       [0020]      FIG. 1   a  illustrates an exemplary representation of a virtual private network  100  composed of components, referred to as provider edge routers (PE),  110 ,  160  and  180  that represent the means for providing information items to, and receiving information items from, network  100 . Also shown are Customer Edge (CE) nodes or routers  115 ,  165 ,  167  and  185 , which are in communication with corresponding provider edge nodes  110 ,  160  and  180 . The CE nodes  115 ,  165 ,  167  and  185  represent components or routers located at the customer premises that are directly connected, at either a network Layer  2  or Layer  3  level (of the OSI stack) to the ingress and egress provider edge routers  110 ,  160  and  180 . Internal routers, which are not shown, are responsible for converting the packet or frame structure from the one used to communicate with CE routers  115 ,  165 ,  167 , and  185  to the packet or frame structure used internally by an associated private network.  
         [0021]     A CE router or node is typically connected to only one provider edge router or node. However, as shown in this illustrative case, provider edge router  160  is connected to CE router  165  and CE router  167 . Hence, CE router  185 , for example, may communicate privately with CE router  165  and/or  167 . The communication between the CE nodes and the PE nodes may take place using any Layer  2  or Layer  3  network protocol.  
         [0022]     VPN routing and addressing structures are created for each customer in the PE and internal nodes (not shown), and designate the path assigned to the customer. VPN Routing and Forwarding Tables (VRFs) are a well-known means for creating virtual private networks. The VRFs exchange routes using, for example, Multiprotocol Border Gateway Protocol (MP-BGP). The typical attributes of a VRF instance include a name, associated interfaces, route-distinguisher, import route-targets, export route-targets, and a routing table. RouteTargets (RTs) are identifiers associated with a set of routes through the network  100 . The identifiers are used by the VRFs to control the importing or the exporting of routes to other VRFs. Each VRF, thus, can export or import routes or paths via a list of export or import RTs. In this illustrative case, CE  115  for example, may communicate privately with CE  167  by the appropriate selection of VRFs in each edge router or node and the not shown internal routers or nodes. In one aspect of the invention, a Route-Distinguisher may also be specified that provides a distinguishing characteristic for the specific route. This distinguishing characteristic is used when duplicate addresses are encountered.  
         [0023]      FIG. 2  illustrates an exemplary abstract model  200  of a VPN network in accordance with the principles of the invention. The VPN model shown is an extension of a known network models  210 , such as the SMARTS® InCharge™ Common Information Model (ICIM), or similarly defined or pre-existing CIM-based model. SMARTS and Incharge are trademarks of System Management ARTs, Inc., having a principle place of business in White Plains, N.Y., USA. CIM models are known to represent selected ones of the physical network components, e.g., nodes, routers, computer systems, disk drives, etc., and/or logical network components, e.g., software, application software, ports, disk drive designation, etc., by defining object classes, which are a representation of the component. Those network components that are selected for representation in the model are hereinafter referred to as managed components. The representation of the managed components includes aspects or properties of the component. Similarly, the relationships between the managed components are also represented and contained in the model.  
         [0024]     With regard to the ICIM, this model defines object classes such as ServiceConnection  210 . 1 , NetworkService  210 . 2 , and LogicalNetwork  210 . 3  that are representative of generic concepts or components of service connections, network services, and logical networks, respectively.  
         [0025]     In accordance with the principles of the invention with regard to modeling VPNs, object class RouteTargets  220 . 1  is selected as a type of service connection, VRF  220 . 2  is designated as a type of network service, and VPN  220 . 3  is designated as a type of logical network. Object classes RouteTargets, VRF, VPN are hereinafter referred to as RouteTargets, VRF, VPN unnecessary technical terminology. Those skilled in the art would recognize that such references refer to the respective object classes. Furthermore, the terms RouteTarget and RouteTargets may also refer to an element(s) or instances of the object class RouteTargets. Similar terminology is also used with regard to VRF, VRFs, VPN and VPNs.  
         [0026]     The VPN model shown further illustrates the relationship between RouteTargets  210 . 1  and VRFs  220 . 2 , which are represented with the classes Imported By/Imports and Exported by/Exports. Similarly, the relationship between VRFs and the VPN may be expressed as Hubsof/Hubs and SpokesOf/Spokes.  
         [0027]     It would be recognized by those skilled in the art that the information to populate or determine instances of the object classes, i.e., representation of components, and the relationship between components, i.e., representation of component relationships, of the models defined herein may be pre-loaded or predetermined or may be determined dynamically by importation, discovery or provided by one or more sources of such information, e.g., Simple Network Management Protocol (SNMP) MIBs, MPLS-LSR-MIB, MPLS forwarding tables, MPLS-VPN-MIB. Similarly, manual commands such as Command Line Interface (CLI) at network devices, Show commands that retrieve and display information regarding forwarding-table, VRFs, BGP and MBGP sessions, may be used to provide information to populate the object classes shown. Each of these sources of information are representative of communications that may occur dynamically over the physical network that the model overlays, i.e., layered over, and should not be considered the only methods to dynamically populate the object classes shown.  
         [0028]      FIG. 3  illustrates an example of an import/export relationship between VRFs and RouteTargets for a VPN in accordance with the principles of the invention. In this illustrated example, VRFs  305 ,  307 ,  309  have import/export relationships with RTs  301  and  303  that are tabulated in Table 1.  
                               TABLE 1                                   VRF   Imports   Exports                           V1   —   RT1, RT2           V2   RT1, RT2   RT1           V3   RT2   RT3                        
         [0029]     The ImportedBy/Imports and the ExportBy/Exports relationships shown in  FIG. 3  may be expressed as: 
 
Im(R 1 ) is the set {V 2 };   [1]
 
Ex(R 1 ) is the set {V 1 , V 2 };   [2]
 
Im(R 2 ) is the set {V 2 ,V 3 }; and   [3]
 
Ex(R 2 ) is the set {V 1 ,V 3 }  [4]
        Where Im(R x ) is the set of VRFs that import the RouteTarget R x ; and 
            Ex(R x ) is the set of VRFs that export the RouteTarget R x.      
               
 
         [0032]      FIG. 4   a  illustrates a representation  400  of the relationship between VRFs and RTs in a Full-Mesh (FM) topology in accordance with an aspect of the principles of the invention. A Full-Mesh topology allows routing of packets from any node in the VPN to any other node in the VPN. Hence, in accordance with the principles of the invention, in an FM topology Route Target (RT)  405  is such that it is both imported and exported by the VRF  410 . This may be expressed as: 
   Im (R)= Ex (R)   [5] 
         [0033]      FIGS. 4   b - 4   d  illustrate graphic representations of the relationship between VRFs and RTs in Hub-and-Spoke (H-S) topologies in accordance with the principles of the invention. In an H-S topology, hub VRFs may communicate with either hub or spoke VRFs, whereas spoke VRFs can only communicate with hub VRFs. An H-S VPN topology may be determined when one of the following configurations is satisfied:  
         [0034]     1. Hub VRFs export R 2  and both import and export R 1  while spoke VRFs import R 2  and export R 1 . See  FIG. 4   b;    
         [0035]     2. Hub VRFs both import and export R 2  and import R 1  while spoke VRFs import R 2  and export R 1 . See  FIG. 4   c ; or  
         [0036]     3. Hub VRFs both import and export R 2  and both import and export R 1  while spoke VRFs import R 2  and export R 1 . See  FIG. 4   d.    
         [0037]     Accordingly, an H-S topology may be determined when, for an ordered pair of Route Targets, denoted as R 1  and R 2 , the following conditions are satisfied:  
         [0038]     1. The import set of R 1  is identical to the export set of R 2 ; and  
         [0039]     2. The set of VRFs that export R 1  but do not import R 1  is identical to the set of VRFs that import R 2  but do not export R 2 ; and  
         [0040]     3. The export set of R 1  is not identical to the import set of R 2 , or there is at least one VRF that both imports and exports R 1 .  
         [0041]     These criteria may be expressed as: 
 
 Im (R 1 )= Ex (R 2 ); and   [6]
 
 Ex (R 1 )\ IM (R 1 )= Im (R 2 )\ Ex (R 2 ); and   [7]
 
 Ex (R 1 )≠ Im (R 2 ) OR  Ex (R 1 )∩ Im (R 1 )≠Empty set   [8]
 
         [0042]     In another aspect of the invention, the members of an H-S topology may then be determined as those members of the union of the import and the export sets of R 1 . In this aspect of the invention, the spoke members may be determined as those members of the set of VRFs that export but do not import R 1 , and the remaining members of the VPN are hub members.  
         [0043]      FIG. 5  illustrates a VRF-RT model used as an example for determining VPN topologies, and element members, in accordance with the principles of the present invention. In this illustrative example, the ImportedBy/Imports and ExportedBy/Exports relationships between RTs  510 - 550 , i.e., R 1 -R 5 , and VRFs  560 - 576 , i.e., V 1 -V 9 , are graphically illustrated using an arrow notation wherein the arrowhead denotes importing/exporting. Utilizing the notation discussed previously, RouteTarget  520  (R 2 ), for example, imports VRF  564  (V 3 ), VRF  574  (V 8 ) and VRF  576  (V 9 ) and exports VRF  566  (V 4 ) and VRF  568  (V 5 ). The import and export sets with respect to Route Targets R 1 -R 5  may be determined as shown in Table 2 as:  
                               TABLE 2                                   Route Target   Im(R)   Ex(R)                           R 1     {V 1 , V 2 , V 7 }   {V 1 , V 2 , V 7 }           R 2     {V 4 , V 5 }   {V 3 , V 8 , V 9 }           R 3     {V 4 , V 7 }   {V 6 }           R 4     {V 3 , V 4 , V 5 , V 8 , V 9 }   {V 4 , V 5 }           R 5     {V 6 }   {V 4 , V 6 , V 7 }                        
         [0044]     In this case, the import set and the export set associated with R 1  are identical and, hence, satisfy the conditions of equation 1. Thus, VRFs  960 ,  962 ,  972  (i.e., V 1 , V 2 , V 7 ) constitute a VPN of a Full-Mesh topology.  
         [0045]     A Hub-and-Spoke topology may be determined between Route Target  920  and  930  (i.e, R 2  and R 4 , respectively) as the following conditions are satisfied: 
 
 Im (R 2 )={V 4,V   5   }=Ex (R 4 ); 
 
 Ex (R 2 )\ Im (R 2 )={V 3 ,V 8 ,V 9 }\{V 4 ,V 5 }={V 3 ,V 8 ,V 9 } and 
 
 Im (R 4 )\ Ex (R 4 )={V 3 ,V 4 ,V 5 ,V 8 ,V 9 }\{V 4 ,V 5 }={V 3 ,V 8 ,V 9 }; and 
 
 Ex (R 2 )={V 3 ,V 8 ,V 9 }≠{V 3 ,V 4 ,V 5 ,V 8 ,V 9   }=Im (R 4 ). 
 
         [0046]     Accordingly, VRFs  964 ,  966 ,  968 ,  974 ,  976  (i.e., V 3 , V 4 , V 5 , V 8  and V 9 ) constitute a Hub-and-Spoke topology. In a similar manner, it may be determined that the ordered pair of Route Targets  950 ,  920  (R 5 , R 2 ) also constitute a Hub-and-Spoke topology.  
         [0047]     The spoke members of a H-S topology may be determined as those members of the set of VRFs that export but do not import the first Route Target of the ordered pair of Route Targets and the remaining members of the H-S topology VPN are then deemed hub VRFs. 
 
Ex(R x )\Im(R x )   [9]
        where R x  is the first RT of the ordered pair        
 
         [0049]     Thus, in the H-S topology determined from the ordered pair of Route Targets  920 ,  940  (R 2 , R 4 ), the spoke members may be determined to be VRFs V 3 , V 8  and V 9  and the hub members are VRFs V 3  and V 4.  Similarly, in the H-S VPN topology determined from the ordered pair of Route Targets R 5 , R 2 , the spoke members are VRFs V 4  and V 7  and the hub member is VRF V 6 .  
         [0050]     In another aspect of the invention, not all pairings of Route Targets need be tested. In this aspect of the invention, the pairing of Route Targets may be reduced by considering the following criteria:  
         [0051]     1. Route Targets that define a Full-Mesh VPN need not be evaluated; or  
         [0052]     2. For a selected RouteTarget, only RouteTargets that are exported by some VRF that is in the import set of the given RouteTarget need be evaluated.  
         [0053]     In accordance with this aspect of the invention with regard to the above example, R 1  need not be evaluated with regard to the remaining RTs as R 1  was determined to be in a Full-Mesh network. Similarly, R 3  and R 4  need not be evaluated with regard to each other as they fail to satisfy condition 2.  
         [0054]      FIGS. 6   a - 6   d  illustrate an application of the present invention with regard to a physical network.  FIG. 6   a  illustrates an example of two MPLS VPNs  600  and  650  wherein VPN  600  is in a Full Mesh configuration and VPN  650  is in a Hub-and-Spoke configuration. And will be determining in accordance with the principles of the invention.  FIG. 6   a  illustrates that VPN  600  communicates, through provider edge nodes  610 - 640 , to customer edge nodes  612 ,  622 ,  632  and  642 , respectively, and VPN  650  communicates, through provider edge nodes  610 - 640 , to consumer edge nodes  612 ,  622 ,  634  and  644 , respectively.  
         [0055]     Table 3 tabulates the imports and exports of the RTs for each VRF shown in  FIG. 6   a . This information is stored at the respective provider edge node where the VRFs reside.  
                                   TABLE 3                                   VRF   Node   Imports   Exports                           VRF1   PE1   RT1A   RT1B           VRF1   PE2   RT1A, RT1B   RT1A           VRF1   PE3   RT1A   RT1B           VRF1   PE4   RT1A, RT1B   RT1A           VRF2   PE1   RT2   RT2           VRF2   PE2   RT2   RT2           VRF2   PE3   RT2   RT2           VRF2   PE4   RT2   RT2                      
 
         [0056]      FIGS. 6   b  and  6   c  illustrate the ImportedBy/Imports and ExportedBy/Exports relationships of VRFs with respect to RTs in the exemplary VPNs  600  and  650  shown in  FIG. 6   a .  FIG. 6   b  illustrates that RT 1 A is imported by each VRF 1  in each provider edge node  610 - 640  (PE 1 -PE 4 ), while RT 1 B is imported by VRF 1  at provider edge nodes  620  and  640  (i.e., PE 2  and PE 4 ). Similarly, RT 2  is imported by VRF 2  at each provider edge node  610 - 640  (PE 1 -PE 4 ).  FIG. 6   c  illustrates that RT 1 A is exported by VRF 1  at provider edge nodes  620  and  640 , while RT 1 B is exported by VRF 1  at provider edge nodes  610  and  630 . RT 2 , on the other hand, is exported by each VRF 2  at each provider edge node  610 - 640 . Table 4 tabulates the Imported By and Exported By relationships, wherein V ij  represents the instantiation of VRF i  at PE j .  
                               TABLE 4                                       Im(R)   Ex(R)                           RT1A   {V 11 , V 12 , V 13 , V 14 }   {V 12 , V 14 }           RT1B   {V 12 , V 14 }   {V 11 , V 13 }           RT2   {V 21 , V 22 , V 23 , V 24 }   {V 21 , V 22 , V 23 , V 24 }                        
         [0057]     Evaluating the entries shown in Table 4, utilizing the criteria shown in equations 5-8, it may be determined that VPN  600  is an FM-type VPN as RT 2  is imported and exported by all VRF 2 s. Further, VPN  650  may be determined to be a H-S type VPN. It may further be determined that PE 1    610  and PE 3    630  are spoke VRFs and PE 2 ,  620  and PE 4 ,  640  are be hub VRFs.  FIG. 6   d  illustrates the VRFs associated with the determined VPN types.  
         [0058]      FIG. 7  illustrates an exemplary embodiment of a system  700  that may be used for implementing the principles of the present invention. System  700  may contain one or more input/output devices  702 , processors  703  and memories  704 . I/O devices  702  may access or receive information from one or more sources or devices  701 . Sources or devices  701  may be devices such as routers, servers, computers, notebook computer, PDAs, cells phones or other devices suitable for transmitting and receiving information responsive to the processes shown herein. Devices  701  may have access over one or more network connections  750  via, for example, a wireless wide area network, a wireless metropolitan area network, a wireless local area network, a terrestrial broadcast system (Radio, TV), a satellite network, a cell phone or a wireless telephone network, or similar wired networks, such as POTS, INTERNET, LAN, WAN and/or private networks, e.g., INTRANET, as well as portions or combinations of these and other types of networks.  
         [0059]     Input/output devices  702 , processors  703  and memories  704  may communicate over a communication medium  725 . Communication medium  725  may represent, for example, a bus, a communication network, one or more internal connections of a circuit, circuit card or other apparatus, as well as portions and combinations of these and other communication media. Input data from the client devices  701  is processed in accordance with one or more programs that may be stored in memories  704  and executed by processors  703 . Memories  704  may be any magnetic, optical or semiconductor medium that is loadable and retains information either permanently, e.g. PROM, or non-permanenty, e.g., RAM. Processors  703  may be any means, such as general purpose or special purpose computing system, such as a laptop computer, desktop computer, a server, handheld computer, or may be a hardware configuration, such as dedicated logic circuit, or integrated circuit. Processors  703  may also be Programmable Array Logic (PAL), or Application Specific Integrated Circuit (ASIC), etc., which may be “programmed” to include software instructions or code that provides a known output in response to known inputs. In one aspect, hardware circuitry may be used in place of, or in combination with, software instructions to implement the invention. The elements illustrated herein may also be implemented as discrete hardware elements that are operable to perform the operations shown using coded logical operations or by executing hardware executable code.  
         [0060]     In a one aspect, the processes shown herein may be represented by computer readable code stored on a computer readable medium. The code may also be stored in the memory  704 . The code may be read or downloaded from a memory medium  783 , an I/O device  785  or magnetic or optical media, such as a floppy disk, a CD-ROM or a DVD,  787  and then stored in memory  704 .  
         [0061]     Information from device  701  received by I/O device  702 , after processing in accordance with one or more software programs operable to perform the functions illustrated herein, may also be transmitted over network  780  to one or more output devices represented as display  785 , reporting device  790  or second processing system  795 .  
         [0062]     As one skilled in the art would recognize, the term computer or computer system may represent one or more processing units in communication with one or more memory units and other devices, e.g., peripherals, connected electronically to and communicating with the at least one processing unit. Furthermore, the devices may be electronically connected to the one or more processing units via internal busses, e.g., ISA bus, microchannel bus, PCI bus, PCMCIA bus, etc., or one or more internal connections of a circuit, circuit card or other device, as well as portions and combinations of these and other communication media or an external network, e.g., the Internet and Intranet.  
         [0063]     While there has been shown, described, and pointed out fundamental novel features of the present invention as applied to preferred embodiments thereof, it will be understood that various omissions and substitutions and changes in the apparatus described, in the form and details of the devices disclosed, and in their operation, may be made by those skilled in the art without departing from the spirit of the present invention. It is expressly intended that all combinations of those elements that perform substantially the same function in substantially the same way to achieve the same results are within the scope of the invention. Substitutions of elements from one described embodiment to another are also fully intended and contemplated. For example, although the present invention has been disclosed with regard to VPNs of the Full Mesh and Hub-and-Spoke topologies, the techniques described herein are not limited to the topologies shown. For example, Partial Mesh topologies are known in the art as being Hub-and-Spoke topologies with multiple hubs. In addition, Spoke-and-Spoke topologies may similarly be determined. Accordingly, it would be within the knowledge of those skilled in the art to expand the teachings described herein to other topologies, which have been contemplated and are considered within the scope of the invention. Similarly, the invention described herein describes a generic modeling approach for VPNs. However, the invention is not limited by the model discussed, and used as an example, or the specific proposed modeling approach described herein.