Source: https://patents.google.com/patent/US7792987B1/en
Timestamp: 2018-05-22 00:47:00
Document Index: 792635906

Matched Legal Cases: ['§1', '§1', '§1', '§1', '§1', '§6', '§4', '§4', '§4', '§4', '§4', '§4', '§4']

US7792987B1 - Supporting virtual private networks using a first network topology for forwarding and a subset of the first network topology or a smaller topology for signaling - Google Patents
Supporting virtual private networks using a first network topology for forwarding and a subset of the first network topology or a smaller topology for signaling Download PDF
US7792987B1
US7792987B1 US10419370 US41937003A US7792987B1 US 7792987 B1 US7792987 B1 US 7792987B1 US 10419370 US10419370 US 10419370 US 41937003 A US41937003 A US 41937003A US 7792987 B1 US7792987 B1 US 7792987B1
US10419370
§1.2.1 Known Private Networking Technologies
Dedicated WANs are typically implemented using leased lines or dedicated circuits to connect multiple sites. Customer premises equipment (CPE), such as routers or switches, connect these leased lines or dedicated circuits together to facilitate connectivity between each site of the network. Unfortunately, dedicated WANs are relatively expensive and typically require the customer to have some networking expertise. Public transport networks, which are typically deployed by regional bell operating companies (RBOCs), or some other service provider, are often used to allow remote users to connect an enterprise network using the public-switched telephone network (PSTN), an integrated services digital network (or ISDN), or some other type of transport network technology. Unfortunately, however, various incompatible public transport networks have been introduced over the years in response to the perceived needs to support various applications. Administering and maintaining these separate networks is expensive for those entities providing public transport network services. Virtual private networks (VPNs) have been introduced to permit wide-area communication without the drawbacks of WANs and public transport networks. Two of the more popular ways to implement VPNs, as well as their perceived shortcomings, are introduced in §§1.2.1.1 and 1.2.1.2.
§1.2.1.1 Layer 3 VPNs and Their Perceived Limitations
Layer 3 VPNs have been proposed. See, e.g., the paper E. Rosen et. al., “BGP/MPLS VPNs,” RFC 2547, The Internet Engineering Task Force, The Internet Society (March 1999) (This paper is incorporated herein by reference and hereafter referred to as “RFC 2547”). Unfortunately, layer 3 VPNs have a number of limitations. For example, RFC 2547 contemplated that PE routers would be administered solely by the service provider, and that the customers would have no access to PE administration. (See RFC 2547, §1.2.) Since the transport network is locked into BGP, if the customer uses an interior gateway protocol (IGP) such as open shortest path first (OSPF) or intermediate system-intermediate system (IS-IS), such protocols need to be mapped or otherwise converted to BGP if routing is to take place across the customer-service provider boundary. Similarly, hacks to BGP are necessary if the customer is running multicast.
§1.2.1.2 Virtual Router-Based VPNs and Their Perceived Limitations
VPN members (i.e., nodes having VRs belonging to a VPN) can be “discovered” using various techniques, such as BGP for example. However, routes (or “reachability” information) are exchanged by running existing routing protocols on a per-VPN basis across the tunnels. (See, e.g., §6 of the VR draft.) Unfortunately, this later feature can lead to scalability problems. More specifically, most popular IGP routing protocols, such as OSPF and IS-IS, are so-called “link state routing” protocols. In link state routing protocols, neighbor devices are discovered, a delay or cost metric to each of the neighbor devices is determined, and this “link state” information is send to all other routers. Each router then uses this “network topology” information to determine paths, such as shortest paths or lowest cost paths, to the other routers in the network. Typically, link state information is distributed by flooding it out to all the participating neighbors. In a transport network where a PE may support multiple VPNS, each VPN may be formed by connecting all the VRs in the VPN on all participating PEs via tunnels in a full mesh. That is, each VR instance on each PE can flood link state information across all tunnels interfaced by the PE. This causes a lot of traffic over the network and therefore does not scale well to a large number of VPNs.
§4.1 Exemplary Environment in Which the Invention May Operate
The principles of the invention may be performed in one or more VRs provided in, or used with, one or more PEs. Exemplary operations and data structures, consistent with the principles of the invention, are described in §4.2.
§4.2 Exemplary Apparatus, Operations, Methods and Data Structures
§4.2.1 Exemplary Operations and Data Structures
As shown, there can be multiple instances 210 of route-based forwarding information generation operation—one for each VR. (Any element or elements for effecting such an operation may be referred to as a “route-based forwarding information generation facility.”) A given instance of a path (or route) determination operation 210 a includes a network topology discovery and distribution operations 212 a and a route determination operations 214 a. (Any element or elements for effecting such operations may be referred to as a “network topology discovery and distribution facility” and a “route determination facility.”) Network topology discovery and distribution operations 212 a can learn about and disseminate forwarding topology information 220 a. For example, as is known to those skilled in the art, many popular IGPs, such as OSPF and IS-IS for example, learn about adjacent nodes as well as the cost or distance of links to those adjacent nodes. This information is commonly referred to as “link-state information” or “adjacency information.” Typically, this information is then flooded (sent out over all of a node's links) to other nodes, so that each node will learn about the topology—shown as forwarding topology information 220 a—of the network in which it is a part. The invention considers tunnels to be links to be advertised as link state or adjacency information. However, the invention uses a smaller topology, such as a sub-set of the tunnel topology, to disseminate tunnel “link state” information. Information about that smaller topology is referred to as flooding topology information 230 a.
The flooding topology information should be “fully connected.” That is, each PE should be able to reach each of the other PEs, though not necessarily directly (in one hop). For example, a hub and spoke topology may be used so that each spoke PE can reach any other spoke PE via a hub PE. More than one hub PE may be defined (e.g., to increase reliability). Alternative flooding topologies are possible.
Exemplary methods for performing the operations discussed above, and exemplary data structures for storing the information discussed above, are now described in §4.2.2.
§4.2.2 Exemplary Methods and Data Structures
§4.3 Exemplary Operations
US10419370 2003-04-21 2003-04-21 Supporting virtual private networks using a first network topology for forwarding and a subset of the first network topology or a smaller topology for signaling Active 2028-11-13 US7792987B1 (en)
US10419370 US7792987B1 (en) 2003-04-21 2003-04-21 Supporting virtual private networks using a first network topology for forwarding and a subset of the first network topology or a smaller topology for signaling
US12852225 US8185658B2 (en) 2003-04-21 2010-08-06 Supporting virtual private networks using a first network topology for forwarding and a subset of the first network topology or a smaller topology for signaling
US12852225 Continuation US8185658B2 (en) 2003-04-21 2010-08-06 Supporting virtual private networks using a first network topology for forwarding and a subset of the first network topology or a smaller topology for signaling
US7792987B1 true US7792987B1 (en) 2010-09-07
ID=42669754
US10419370 Active 2028-11-13 US7792987B1 (en) 2003-04-21 2003-04-21 Supporting virtual private networks using a first network topology for forwarding and a subset of the first network topology or a smaller topology for signaling
US12852225 Active US8185658B2 (en) 2003-04-21 2010-08-06 Supporting virtual private networks using a first network topology for forwarding and a subset of the first network topology or a smaller topology for signaling
US (2) US7792987B1 (en)
US20130286893A1 (en) * 2011-05-25 2013-10-31 Huawei Technologies Co., Ltd. Route calculation method and master node device in virtual network element
US7046662B1 (en) * 2001-08-21 2006-05-16 Nortel Networks Ltd System, device, and method for distributing routing information in an optical virtual private network
Kompella, K., Leelanivas, M., Vohra, Q., Achirica, J., Bonica, R., Cooper D., Liljenstolpe, C., Metz, E., Ould-Brahim, H., Sargor, C., Shah, H., Srinivasan, V., and Zhang, Z., "Layer 2 VPNs Over Tunnels," draft-kompella-ppvpn-12vpn-02.txt (Dec. 2002) pp. 1-30.
Ould-Brahim, H., Wright, G., Gleeson, B., Sloane, T., Bubenik, R., Sarhor, C., Negusse, I., Yu, J., Bach, R., Young, A., Fang, L., and Weber, C., "Network based IP VPN Architecture using Virtual Routers," draft-ietf-ppvpn-vpn-vr-03.txt (Jul. 2002) pp. 1-19.
Rosen, E., Rekhter, Y., "BGP/MPLS VPNs," Request for Comments 2547, (The Internet Society, Mar. 1999) pp. 1-25.
US9077608B2 (en) * 2011-05-25 2015-07-07 Huawei Technologies Co., Ltd. Route calculation method and master node device in virtual network element
US8185658B2 (en) 2012-05-22 grant
US20100296414A1 (en) 2010-11-25 application
US20090157901A1 (en) 2009-06-18 System and method for using routing protocol extensions for improving spoke to spoke communication in a computer network
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:VOHRA, QUAIZAR;SHETH, NISCHAL;SIGNING DATES FROM 20030414 TO 20030416;REEL/FRAME:013989/0878