A virtual private network (“VPN”) is a network that uses a public telecommunication infrastructure, such as the Internet, to provide remote offices or individual users with secure access to their organization's network. A virtual private network can be contrasted with an expensive system of owned or leased lines that can only be used by one organization. The goal of a VPN is to provide the organization with the same capabilities, but at a much lower cost. A VPN works by using the shared public infrastructure while maintaining privacy through security procedures and tunnelling protocols. In effect, the protocols, by encrypting data at the sending end and decrypting it at the receiving end, send the data through a “tunnel” that cannot be “entered” by data that is not properly encrypted. An additional level of security involves encrypting not only the data, but also the originating and receiving network addresses. Thus, a VPN is a form of private network that uses a public network (usually the Internet) to connect remote sites or users together. Instead of using a dedicated, real-world connection such as leased line, a VPN uses “virtual” connections routed through the Internet from the company's private network to the remote site or employee.
A Layer 3 VPN (“L3VPN”) interconnects set of hosts and routers based on Layer 3 addresses. The widely-adopted Open Standards Interconnection (“OSI”) model defines seven layers of interconnection. Layer 3 (“L3”) is the network layer. It determines how data is transferred between computers. It also addresses routing within and between individual networks. The Internet Protocol (“IP”), for example, is used in gateways to connect networks at L3 and above. The IP is part of the Transmission Control Protocol/Internet Protocol (“TCP/IP”) family of protocols describing software that tracks the Internet address of nodes, routes outgoing messages, and recognizes incoming messages.
For reference, a method by which a Service Provider (“SP”) may use an IP backbone to provide L3VPNs (or IP VPNs) for its customers is described in Request for Comments (“RFC”) 4364 (RFC 4364, “BGP/MPLS IP Virtual Private Networks (VPNs)”, The Internet Society, February 2006), which is incorporated herein by reference. This method uses a “peer model”, in which the customers' edge routers (“CE routers”) send their routes to the SP's edge routers (“PE routers”). The Border Gateway Protocol (“BGP”) is then used by the SP to exchange the routes of a particular VPN among the PE routers that are attached to that VPN. This is done in a way that ensures that routes from different VPNs remain distinct and separate, even if two VPNs have an overlapping address space. The PE routers distribute, to the CE routers in a particular VPN, the routes from other CE routers in that VPN. The CE routers do not peer with each other, hence there is no “overlay” visible to the VPN's routing algorithm. The term “IP” in “IP VPN” is used to indicate that the PE receives IP datagrams from the CE, examines their IP headers, and routes them accordingly. Each route within a VPN is assigned a Multiprotocol Label Switching (“MPLS”) label. When BGP distributes a VPN route, it also distributes an MPLS label for that route. Before a customer data packet travels across the SP's backbone, it is encapsulated with the MPLS label that corresponds, in the customer's VPN, to the route that is the best match to the packet's destination address. This MPLS packet is further encapsulated (e.g., with another MPLS label or with an IP or Generic Routing Encapsulation (“GRE”) tunnel header) so that it gets tunnelled across the backbone to the proper PE router. Thus, the backbone core routers do not need to know the VPN routes. The primary goal of this method is to support the case in which a client obtains IP backbone services from a SP or SPs with which it maintains contractual relationships. The client may be an enterprise, a group of enterprises that need an extranet, an Internet Service Provider, an application service provider, another VPN SP that uses this same method to offer VPNs to clients of its own, etc. The method makes it very simple for the client to use the backbone services. It is also very scalable and flexible for the SP, and allows the SP to add value.
In networks running RFC 4364 (or it predecessor RFC 2547) VPNs, PE routers maintain virtual routing and forwarding tables (“VRFs”). A VRF is a per-site forwarding table. Every site to which the PE router is attached is associated with one of these tables. A particular packet's IP destination address is looked up in a particular VRF only if that packet has arrived directly from a site that is associated with that table.
Now, customers are becoming increasingly concerned about security as more L3VPN services are rolled out by SPs and as the number of customer private networks that share the same provider core network increases. In general, the larger a customer is, the greater the number of interfaces “connected” to the VPN. However, increasing the number of interfaces makes it more difficult to ensure traffic flow or connectivity between all members of the VPN.
To test connectivity in a network, a “ping” operation may be used. A ping operation sends an echo request packet to an address, and then awaits a reply. The result of the ping operation can help SPs evaluate path-to-host reliability, delays over the path, and whether the host can be reached or is functioning. The ping operation is based on Internet Control Message Protocol (“ICMP”) traffic and it uses public routing tables in order to get to the required destination (if it exists). In a VPN, when attempting to ping from a PE router to a CE router, or from a PE router to PE router, the standard ping operations will not work. Accordingly, “ping VRF” operations are used to ping the IP addresses of LAN interfaces on CE routers. A ping VRF operation is the same as a standard ping operation except that it uses private VPN routing and forwarding tables (i.e., VRFs) instead of public routing tables.
When provisioning medium and large scale L3VPN services, the task of making sure all the connected members are up and running is complex and time consuming. For example, for a VPN with 100 interfaces distributed across 10 VRFs, the number of “ping VRF” operations required to confirm connectivity is 10*90 or 900 operations. Conducting such operations manually is time consuming and the risk to making an error increases with increases in the size of the VPN.
In addition, when provisioning multiple L3VPN services on the same core network, “traffic leak” may occur if provisioning errors are made. For example, consider two customers each having a respective VPN. These networks share the same network core but are supposed to operate separately. If a VPN site that is supposed to be configured for operation on the first customer's VPN is erroneously configured for operation on the second company's VPN, then a traffic leak has occurred in that the site will have access to information on the second company's VPN that it is not supposed to have. In other words, the security of the VPN has been jeopardized. Accordingly, it is important to ensure for customers sharing the same core that VPN traffic stays within its own VPN. To ensure that there is no traffic leak, every “connected” interface in the customer VPN has to be pinged from all the other VRFs which don't belong to that VPN. Again, the higher the number of interfaces in the VPN (and in the other VPNs), the more difficult testing for traffic leak becomes. For example, for two VPNs each having 100 interfaces distributed across 10 VRFs, the number of ping VRF operations that need to be performed is 10*100+10*100=2000 operations.
Thus, connectivity and security are two problems SPs face when providing L3VPN services to their customers.
A need therefore exists for an improved method and system for verifying connectivity in virtual private networks. Accordingly, a solution that addresses, at least in part, the above and other shortcomings is desired.
USPTO Backgrounds
USPTO Backgrounds