Abstract:
In methods and apparatus for acquiring VPN reachability information at a node of a data network, a VPN reachability information request is transmitted from a requesting node. The VPN reachability information request comprises a VPN identifier. Other nodes of the data network receive the VPN reachability information request and, if they have reachability information relevant to that VPN, they transmit such information to the requesting node where it is received and stored. The invention can be used in MPLS VPN architectures.

Description:
CROSS-REFERENCE TO RELATED APPLICATION(S) 
     This application is a divisional of U.S. patent application Ser. No. 10/978,684 filed Nov. 1, 2004 now U.S. Pat. No. 7,296,090, which is a continuation of U.S. patent application Ser. No. 09/441,367 filed on Nov. 17, 1999 now U.S. Pat. No. 6,813,644 which claims priority to Canadian Patent Application No. 2,254,813 filed Nov. 18, 1998. 
    
    
     FIELD OF THE INVENTION 
     This invention relates to distribution of reachability information in Virtual Private Networks (VPNs). 
     BACKGROUND OF THE INVENTION 
     A typical Internet network implementation comprises a Service Provider Network (SPN) connected to a plurality of customer data facilities, commonly referred to as Customer Premises Equipment (CPE). The SPN is operated by an Internet Service Provider (ISP), and comprises a network Provider Edge (PE) nodes (for example, routers and/or IP switches). Each PE node is connected to one or more instances of CPE by access links. The PE nodes are connected within the SPN directly, via other nodes and via route reflectors. Each CPE may comprise a computer or network of computers operated by a customer, the computers being interconnected, for example, by a Local Area Network (LAN). Virtual Private Networks. A VPN is an emulated multi-site wide area routed network using IP facilities which are operated and implemented by an Internet Service Provider (ISP). Thus an SPN can be used to “connect” CPE across multiple sites. These “connections” are shared in the sense that the same PE nodes can be used to connect the CPE of more than one customer. Typically, a VPN is operated by establishing tunnels between Provider Edge (PE) devices supporting the sites of a VPN. 
     The Internet Engineering Task Force (IETF) is an industry consortium which seeks to define standards for implementation of Internet networks. Participants submit Internet Drafts to the IETF for discussion in working groups. Some proposals contained in Internet Drafts may eventually be adopted as standards by the IETF. Copies of Internet Drafts are available at Internet address ftp://frp.ietf.org/internet-drafts. 
     Recent IETF drafts make proposals concerning the implementation of Virtual Private Networks (VPNs) in SPNs using Multi-Protocol Label Switching (MPLS). Such drafts include:
         [1] J. Heinanen et al, “VPN Support with MPLS”, &lt;draft-heinanen-mpls-vpn-01.txt&gt;, March 1998.   [2] D. Jamieson et al, “MPLS VPN Architecture”, &lt;draft-jamieson-mpls-vpn-00.txt&gt;, August  1998 .   [3] T. Li, “CPE Based VPNs using MPLS”, &lt;draft-li-mpls-vpn-00.txt&gt;, October 1998.   [4] E. Rosen et al, “BGP/MPLS VPNs”, &lt;draft-rosen-vpn-mpls-00.txt&gt;, November 1998.       

     To implement VPNs on SPNs using MPLS, [3] proposes that a CPE will transmit a Border Gateway Protocol (BGP) message to the SPN to indicate its presence in the network and to indicate the set of VPNs in which the CPE wants to participate. The BGP message includes “VPN reachability information”, including the CPE&#39;s address in the ISP&#39;s address space and a VPN identifier. 
     The BGP message is received by the PE node which is connected to the CPE. The PE node can filter or otherwise examine the message to ensure that it complies with the ISP&#39;s policies. If the message does comply with the ISPs policies, the message is propagated to other PE nodes of the SPN according to the specifications of BGP (see IETF document RFC 1771). 
     The other PE nodes of the SPN store the VPN reachability information and forward the BGP message to any of their connected CPE that are participating in the same VPN. The CPE receiving the BGP message can then use MPLS signalling protocol to set up a MPLS tunnel to the CPE which has just joined the VPN. The PE nodes use the stored VPN reachability information to establish the MPLS tunnels. 
     The method described in [3] requires very little or no intervention by an ISP when a new CPE is added to a VPN. However, in a large SPN which supports a large number of VPN subscribers, each PE node of the SPN would be required to store a very large amount of VPN reachability information. Moreover, only a small percentage of the stored VPN reachability information may actually be needed by any particular PE node. 
     For example, in an SPN having 2000 PE nodes and 1000 VPN interfaces per PE node with an average of 10 sites per VPN, 2 million VPN reachability information records would be distributed to each PE node. Assuming conservatively that each VPN reachability information record requires 30 bytes of storage, the VPN reachability information would require 60 Mbytes of storage at each PE node. However, according to the above assumptions, only 10,000 of the stored VPN reachability information records would actually be used by a typical PE node to establish VPN tunnels. The remaining 1.99 million of the 2 million reachability information records, stored at a typical PE node, i.e. 99.5% of the stored records, would not be used. 
     [4] proposes that PE nodes transmitting BGP messages apply outbound filtering so as not to propagate VPN reachability information to other PE nodes which are not participating in the VPN identified in the BGP message. Alternatively, [4] proposes that PE nodes receiving BGP messages apply inbound filtering so as not to store VPN reachability information for VPNs in which they are not participating. These filtering approaches may address the storage inefficiencies noted above. However, should CPE requiring access to a particular VPN be connected to a PE node not previously participating in that VPN, such filtering would result in the PE node lacking VPN reachability information for that VPN. The required VPN reachability information would need to be provided to the PE node, either by operator provisioning or by dropping and reestablishing the connection between the PE node and other PE nodes of the SPN so that all other PE nodes of the SPN automatically transmit all of their accumulated VPN reachability information to the PE node. The former method for acquiring the required VPN reachability information is time-consuming, error-prone and expensive. In a large network, the latter method for acquiring the required VPN reachability information would take too long and have too great an impact on SPN performance to be acceptable. 
     SUMMARY OF THE INVENTION 
     The invention seeks to reduce or eliminate the above problems by enabling a particular PE node to solicit specified VPN reachability information from other PE nodes when such information is needed at the particular PE node. Preferred embodiments of the invention will be described which present a scalable solution which reduces the storage requirements at each node and which can co-exist with existing equipment. 
     In one embodiment there is provided, for use in a route reflector in a data network, the data network including a plurality of nodes capable of communicating with each other, each node coupled to at least one unit of a customer network, the route reflector coupled to a plurality of client peer nodes and at least one non-client peer node, computer-executable instructions stored on a computer-readable storage medium for providing a plurality of Virtual Privacy Networks (VPNs), the computer-executable instructions operable for maintaining, for each VPN in which at least one unit coupled to a client peer node is participating, a route repeater send list of client peer nodes coupled to at least one unit participating in that VPN; receiving from a first client peer node VPN reachability information (VRI) for a first unit coupled to the first client peer node, the received VRI identifying a VPN in which the first unit is participating; reflecting the VRI to all client peer nodes on the route repeater send list for the identified VPN that are not the first client veer node; and reflecting the VRI to all non-client veer nodes. 
     In yet another embodiment, there is provided a method of operating a route reflector in a data network, the data network including a plurality of nodes capable of communicating with each other, each node coupled to at least one unit of a customer network, the route reflector coupled to a plurality of client peer nodes and at least one non-client peer node. The method includes maintaining, for each VPN in which at least one unit coupled to a client peer node is participating, a route repeater send list of client peer nodes coupled to at least one unit participating in that VPN; receiving from a first client peer node VPN reachability information (VRI) for a first unit coupled to the first client peer node, the received VRI identifying a VPN in which the first unit is participating; reflecting the VRI to all client peer nodes on the route repeater send list for the identified VPN that are not the first client peer node; and reflecting the VRI to all non-client peer nodes. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       Embodiments of the invention are described below with reference to the accompanying drawings, by way of example only. In the drawings: 
         FIG. 1  is a block schematic diagram of a data network embodying a first implementation of the invention; 
         FIG. 2  is a flow chart showing steps in a process performed by a solicit-capable PE node on receipt of a VPN connection request from CPE; 
         FIG. 3  is a flow chart showing steps in a process performed by a solicit-capable PE node on receipt of a VPN reachability information request; 
         FIG. 4  is a flow chart showing steps in a process performed by a solicit-capable PE node on receipt of VPN reachability information; 
         FIGS. 5   a  and  5   b  are message flow diagrams showing message flows resulting in distribution of VPN reachability information; 
         FIG. 6  is a flow chart showing steps in a process performed by a solicit-capable PE node on receipt of a VPN disconnect request from CPE; 
         FIG. 7  is flow chart showing steps in a process performed by a solicit-capable FE node on receipt of a VPN withdraw request; 
         FIG. 8  is a message flow diagram showing message flows resulting in deletion of VPN reachability information; 
         FIG. 9  is a block schematic diagram showing a data network embodying a second implementation of the invention; and 
         FIG. 10  is flow chart showing steps in a process performed by a route reflector on receipt of VPN reachability information. 
         FIG. 11  is a block schematic diagram of a data network embodying a third implementation of the invention; 
         FIG. 12  is a flow chart showing steps in a process performed by a solicit-capable PE node on receipt of a VPN connection information from NCU; and 
         FIG. 13  illustrates an example of the internal data structures maintained by each PE node for each VPN, according to an embodiment of the invention. 
     
    
    
     DETAILED DESCRIPTION OF EMBODIMENTS 
       FIG. 1  is a block schematic diagram of a data network embodying a first implementation of the invention. The data network comprises a Service Provider Network (SPN)  10  connected to a plurality of customer networks  202 - 206 . The SPN  10  comprises a plurality of Provider Edge (PE) nodes  12  which are peered, for example, by connections  14 . Each FE node  12  of the SPN  10  is connected to one or more Customer Premises Equipment CPE units of one or more customer network. 
     A typical customer has data networks at multiple sites and contracts with the service provider to link those sites via the SPN  10  to form a VPN for that customer. For the example illustrated in  FIG. 1 , customer  1  links customer networks  203  and  205  via PE 3  and PE 4  of the SPN  10 ; and customer  2  links customer networks  202  and  206  via the same PE 3  and PE 4  of the SPN  10 . Because PE 3  and PE 4  of the SPN  10  are shared, the connections constitute Virtual Private Networks (VPNs). 
     In a Multi-Protocol Label Switching (MPLS) network, the FE nodes require VPN reachability information to establish MPLS tunnels corresponding to VPN connections. As described above, in previously proposed MPLS VPN architectures, the PE nodes are each required to store a full set of VPN reachability information, only a small proportion of which is used at any one PE node. 
     In this description, the term “VPN Reachability Information” will be abbreviated to “VRI” for convenience. 
     In the SPN  10  constructed according to an embodiment of the invention, at least some of the PE nodes  12  are “solicit-capable”—i.e. they are provided with functionality that enables them to request VRI when they need it without unduly disrupting operation of the SPN  10 . 
       FIG. 13  illustrates an example of the internal data structures maintained by each PE node for each VPN, according to an embodiment of the invention. In this example, the PE is assumed to have connections to 4 peers, (labelled as Peers  1 - 4  at the left of the drawing) and 5 CPE&#39;s (labelled as Links  1 - 5  at the right of the drawing). Furthermore, the FE supports 4 VPN&#39;s (labelled as VPN A, B, C, and D). There is a VPN associated with each Link (with a separate IP address). Note that VPN&#39;s may be supported over multiple links. In this example the PE supports VPN C across two separate Links, as shown in  FIG. 15 , with VPN C associated with both Link  3  (at IP address 10.3.0.1) and Link  5  (at IP address 10.3.0.2). In  FIG. 13 , there are two main data structures: VPN Link data, which contains a database of which VPN&#39;s are associated with which links; and BGP VPN data, which contains three databases for each VPN: a send list, an adj-RIB-out database and an adj-RIB-In database. 
     Send List is a set of peers which are known to participation in a given VPN. When there is a change in VPN information on a PE, the send list is used to distribute the changes to the appropriate peers. 
     As is known, adj-RIB-In is a database which contains the VRIs learned from peers. It is organized to associated the VRIs with the peer from which they are learned. 
     Also as is known, adj-RIB-Out is a database which contains the VRIs to be sent to peers. 
     Note that the data structures are illustrated as being organized by VPN. This facilitates the ability to manage the databases so that only relevant entries are maintained, and so that routing tables can be created and maintained per VPN. Advantageously, different policies can be applied on a per VPN basis. Furthermore, this organization (by VPN) allows each PE node to notify PEERs (via its adj-RIB-out table) on a VPN basis. 
       FIG. 2  is a flow chart showing steps in a process performed by a solicit-capable FE node on receipt of a VPN connection request (from a CPE or from the NCU for  FIG. 12 ), the connection request specifying a VPN identifier for the VPN in which the CPE wishes to participate. The PE node determines whether it already has another CPE registered for that VPN. If the PE node has another CPE registered for that VPN, it already has the required VRI and it has a send list identifying all peer nodes participating in that VPN. Consequently, it transmits VRI received from the CPE with the VPN connection request to peer nodes on the send list for that VPN without requesting further VRI. 
     If, however, the PE node does not have the required VRI, it transmits the VRI received with the VPN connection request together with specified overhead bits set to indicate that further VRI is required for that VPN to all peer nodes. The resulting message acts as a VRI request. 
       FIG. 3  is a flow chart showing steps in a process performed by a solicit-capable PE node on receipt of a VPN reachability information request. The PE node determines whether it has VRI for that VPN. If the PE node has the requested VRI, it retrieves the VRI and transmits it to the requesting peer node. The FE node receiving the VRI request also adds the requesting peer node to the send list for that VPN. 
       FIG. 4  is a flow chart showing steps in a process performed by a solicit-capable PE node on receipt of VPN reachability information. If the VRI is received from a non-solicit-capable PE node, the PE node stores the VRI for possible future use. If the VRI is received from a solicit-capable PE node, the receiving PE node stores the VRI only if it is currently participating in that VPN. The PE node adds the sending peer node to the send list for that VPN. 
       FIG. 5   a  is a message flow diagram showing how the processes of  FIGS. 2 and 3  work together to provide message flows which result in distribution of VPN reachability information in  FIG. 5   a . The CPE sends a VPN connection request to its PE node. If that PE node was previously unaware of the requested VPN, the PE node sends a VRI request to all other PEER nodes. Each PEER node having knowledge of the VPN sends the VRI local to that peer node back to the requesting PE node. The requesting PE node in turn stores the VRI received from each peer, forwards this information to the requesting CPE, and adds each replying peer to its send list. In  FIG. 5   b , the VPN is known to the PE. The PE therefore only sends the VRI to its send list peers (without the VPN Reachability Information Request). Each peer which receives this VRI stores it and adds the sending peer to its send list. 
       FIG. 6  is a flow chart showing steps in a process performed by a solicit-capable PE node on receipt of a VPN disconnect request from CPE (or receipt of an indication that the link to the CPE is discontinued, e.g., from NCU described below). The PE sends a VPN withdraw message to peer nodes in its send list. If the receiving PE node is connected to other CPE participating in that VPN, the sender list for that VPN is still required at that PE node. Therefore, only the adj-RIB-Out VRI (for that CPE for that VPN) is deleted (possibly indirectly via deletion of entries in the rating tables). However, if no other CPE connected to that node is participating in that VPN, the PE node deletes the send list and all VRI (in both adj-RIB-In and adj-RIB-Out) for that VPN. Should that PE node require the VRI for that VPN again in the future, it can request the required VRI using the processes described above. 
       FIG. 7  is flow chart showing steps in a process performed by a solicit-capable PE node on receipt of a VPN withdraw request. The receiving PE node deletes the VRI for the specified VPN specified in the VPN withdraw request from the sending peer node. The PE node also deletes the sending node from the send list for that VPN if it has no other VRI registered for that VPN at the sending peer node. 
       FIG. 8  is a message flow diagram showing how the processes of  FIGS. 6 and 7  work together to provide message flows resulting in deletion of VPN reachability information. 
     We will now further describe the operation of the above system with reference to a specific example wherein the PE nodes are routers which communicate via BGP. In this example, the following definitions will be helpful:
         i) VPN Reachability Information (VRI) includes a BGP route associated with a VPN which contains VPN specific route information   ii) a solicitation is a request for VRI from an IBGP PE to other IBGP PEs.   iii) in any given network a router can be Solicitation Capable (SC or Non-Solicitation Capable (NSC).       

     Routers incorporating this embodiment of this invention utilize two new BGP-4 path attributes: Solicitation Request (Type Code  16 ): and Solicitation Withdraw (Type Code  17 ). 
     The Solicitation Request (SOL_REQ) path attribute is an optional transitive attribute of length  0 . It is used by a SC PE to solicit VRI from other SC PEs. 
     The Solicitation Withdraw (SOL_WD) path attribute is an optional transitive attribute of variable length. 
     The SOL_WD path attribute consists of a list of four octet values, each of which indicates membership withdraw from a particular VPN. Each SOL_WD path attribute is represented by a list of tuples of form &lt;length, VPN identifiers&gt;, where each tuple is encoded as shown below: 
     
       
         
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 Length (2 octets) 
               
               
                   
                 VPN identifiers (variable) 
               
               
                   
                   
               
             
          
         
       
     
     Length—total length of the VPN identifiers in octets VPN identifiers—a list of withdrawing VPN identifiers 
     An UPDATE message that contains the SOL_WD attribute is not required to carry any other path attributes. 
     The solicitation extension path attributes are not passed to EBGP peers. 
     The first time a SC PE A advertises a VRI for VPN X, PE A includes a SOL_REQ path attribute along with the VRI. This VRI is distributed to all IBGP peers. It should be noted that subsequent 
     VRIs advertised by PE A for VPN X should not include the SOL_REQ path attribute. 
     When a SC PE B which supports VPN X receives the VRI originated from PE A (may come from a route reflector), B must distribute all of its LOCAL VRIs associated with VPN X back to the peer from which it received the solicitation. 
     A SC PE not in VPN X may discard the reachability information from PE A (i.e. does not store it in its Adj-RIB-In). 
     A NSC PE C receiving PE A&#39;s UPDATE message ignores the SOL_REQ path attribute, store the reachability information in its Adj-RIB-In and continue to distribute its VRIs for VPN X to all of its peers. Meanwhile, PE A should store all reachability information from C in its adj-RIB-In regardless whether C participates in the same VPN(s) or not. 
     When a member of VPN X unsubscribes, a SC PE A will notify all other IBGP peers known to support VPN X. Multiple members of VPN X may be supported by PE A. But if the last member of VPN X is withdrawn from PE A, all other SC PE that support X should stop sending VPN X&#39;s VRI to PE A. To withdraw membership from VPN X, a SC PE A may include a SOL_WD path attribute along with the unfeasible route(s) in its UPDATE message. Upon receiving this UPDATE message, a SC PE B withdraws the unfeasible route(s). B also stops sending reachability information related to VPN X to PE A if the last reachability information related to VPN X from PE A has been withdrawn. 
     Advantageously, the above described system allows a BGP-4 equipped PE node to discard Adj-RIB-In entries that are not relevant and solicit those that are. Furthermore, this architecture allows NSC PE (including route reflectors) to continue supporting the general VPN architecture without any loss of VRI. 
       FIG. 9  is a block schematic diagram showing a data network embodying a second implementation of the invention. In this embodiment, PE nodes  120 ,  130  are peered with a route reflector  140 , PE nodes  150 ,  160  are peered with another route reflector  17  and the two route reflectors  140 ,  170  are peered. A PE node  32  of another SPN  30  is connected to one of the route reflectors  170 . Route reflector  140  has as client peer nodes the PE nodes  120 ,  130 , and as non-client peer node the route reflector  170 . Route reflector  170  has as client peer nodes the PE nodes  150 ,  160 , as non-client peer node the route reflector  140  and as external peer node the PE node  32 . 
       FIG. 10  is flow chart showing steps in a process performed by the route reflector  170  on receipt of VPN reachability information. If the VRI is received from one of the client peer nodes  150 , the route reflector  170  forwards the received VRI to its non-client peer node  140  and to its other client peer node  160  provided that the other client peer node  160  is either a non-solicit-capable node or a solicit-capable node that is currently participating in that VPN. If the VRI is received from the external peer node  32 , the route reflector  170  forwards the VRI to its non-client peer node  140  and to its client nodes  150 ,  160  if they are non-solicit-capable or if they are solicit-capable and currently participating in that VPN. If the VRI is received from the non-client peer  140 , the route reflector forwards the VRI to its client nodes  150 ,  160  if they are non-solicit-capable or if they are solicit-capable and currently participating in that VPN. 
     BGP route reflectors which do not support solicitation operate in a conventional manner. BGP route reflectors which support solicitation according to an embodiment of the invention operates as follows. 
     Each route reflector keeps track of the VPN associated with each of its SC-Client peers. When a route is received by a route reflector, it selects the best path based on its path selection rule. 
     After the best path is selected, it does the following depending on the type of peer it is receiving the best path from:
         1) A route from a Non-Client peer
           reflect to all SC-Client peers in the same VPN, and   reflect to all NSC-Client peers;   
           2) A route from a Client peer
           reflect to all Non-Client peers, and   reflect to SC-Client peers in the same VPN other than the originator, and   reflect to all NSC-Client peers other than the originator;   
           3) A route from an EBGP peer
           reflect to all Non-Client peers, and   reflect to SC-Client peers in the same VPN, and   reflect to all NSC-Client peers.   
               

       FIG. 11  is a block schematic diagram of a data network according to an alternative embodiment of the invention. This figure is similar to  FIG. 1 , but includes a network control unit (NCU)  300  which has connections to each of the PE nodes in the SPN. An NCU is a device or set of devices that are network connected which consist of a database of information relevant to other devices in the network and a mechanism to communicate the relevant information to the other devices over the network. Advantageously, the NCU is used to facilitate the solicitation methods described above without requiring any changes to the CPEs. In this example, the NCU can comprise a server (for example a workstation or dedicated hardware), which includes a processor, and memory for storing instructions for storing VPN information on a per CPE basis for each PE and for communicating this information and status changes to each PE. 
       FIG. 12  is a modified version of  FIG. 2  for use with the embodiment of  FIG. 11 . Note the process steps for  FIGS. 3 to 8  are similar, but information regarding changes in CPE connections originates from the NCV. Furthermore, the NCV can be used with an SPN which includes route reflectors. 
     The embodiments of the invention described above may be modified without departing from the broad principles of the invention. 
     For example, the order of some steps in some of the processes described above may be interchanged without appreciably altering their effect. 
     The format of the VRI request may be altered without departing from the principles of the invention. In the embodiment described above, the VRI request is implemented as a flag in a VRI distribution message sent by a PE node to inform peer nodes that a CPE has registered for VPN participation at the sending PE node. Alternatively, the VRI request could take the form of a separate VRI request message. 
     These and other modifications of the embodiments described above are intended to be within the scope of the invention as defined by the claims which follow.