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 7,792,987 B1
• Filed: 04/21/2003
• Issued: 09/07/2010
• Est. Priority Date: 04/21/2003
• Status: Expired due to Fees

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Sheth, Nischal, Vohra, Quaizar
• Primary Examiner(s): Jean; Frantz B
• Application Number:
  US10/419,370
• Time in Patent Office: 2,696 Days
• Field of Search: 709/227, 709/238, 709/249, 709/239, 709/240, 709/241, 709/242, 370/401, 370/352, 370/395.53, 370237-238, 370/389, 370/341, 370/400, 370/468, 370/238.1
• US Class Current: 709/238
• CPC Class Codes: H04L 12/4633 Interconnection of networks using encapsulation techniques, e.g. tunneling
• CPC Class Codes: H04L 12/4675 Dynamic sharing of VLAN information amongst network nodes configuration of the network or of network elements H04L41/08
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/028 Dynamic adaptation of the update intervals, e.g. event-triggered updates
• CPC Class Codes: H04L 45/03 by updating link state protocols
• CPC Class Codes: H04L 45/033 by updating distance vector protocols
• CPC Class Codes: H04L 45/586 of virtual routers

Abstract

Virtual Private Networks (VPNs) are supported in which customers may use popular internet gateway protocol (IGPs) without the need to convert such IGPs, running on customer devices to a single protocol, such as the border gateway protocol (BGP). Scaling problems, which might otherwise occur when multiple instances of an IGP flood link state information, are avoided by using a flooding topology which is smaller than a forwarding topology. The flooding topology may be a fully connected sub-set of the forwarding topology.

Claims

1. Apparatus for facilitating forwarding of addressed data in a network including tunnels coupling nodes associated with a virtual private network, the apparatus comprising:

a) a network topology discovery and distribution facility using a first topology of the virtual private network including at least some of the tunnels to flood network state information; and

b) a route determination facility using a second topology of the virtual private network including at least some of the tunnels to determine a routed path,

wherein the first topology is smaller than the second topology.

2. The apparatus of claim 1 wherein the first topology is a sub-set of the second topology.

3. The apparatus of claim 1 wherein each of the nodes can reach all of the other nodes via tunnels included in the first topology.

4. The apparatus of claim 1 wherein second topology is a full mesh topology.

5. The apparatus of claim 4 wherein the first topology is a hub and spoke topology.

6. The apparatus of claim 1 wherein the first topology is a hub and spoke topology.

7. The apparatus of claim 6 wherein the first topology includes at least two hubs.

8. The apparatus of claim 1 wherein the network state information flooded by the network topology discovery and distribution facility includes link state information.

9. The apparatus of claim 8 wherein the link state information includes the tunnels as virtual link adjacency information.

10. The apparatus of claim 1 further comprising:

c) a tunnel flooding and forwarding topology distribution and discovery facility for defining the first topology.

11. The apparatus of claim 10 wherein the tunnel flooding and forwarding topology distribution and discovery facility distributes to other nodes an indication of whether a virtual router is a hub or a spoke.

12. The apparatus of claim 11 wherein the indication of whether a virtual router is a hub or a spoke is a special attribute assigned by a border gateway protocol community.

13. The apparatus of claim 1 wherein the network topology discovery and distribution facility and the route determination facility belong to a virtual router instance associated with a virtual private network.

14. The apparatus of claim 1 wherein the network topology discovery and distribution facility is adapted to effect an interior gateway protocol.

15. The apparatus of claim 1 wherein the network topology discovery and distribution facility is adapted to effect an interior gateway protocol selected from a group of protocols consisting of (A) an open shortest path first protocol and (B) an intermediate system-intermediate system protocol.

16. The apparatus of claim 1 wherein the network topology discovery and distribution facility effects a link state protocol.

17. A machine readable non-transitory medium having stored thereon machine readable information comprising:

a) first information for identifying a router instance of a virtual private network;

b) second information for indicating whether or not the router instance identified by the first information is a hub or a spoke;

c) third information for identifying a second router instance that belongs to the private network; and

d) fourth information for indicating whether or not an interface with the second router instance identified by the third information is flooding or non-flooding.

18. The machine readable non-transitory medium of claim 17 wherein the machine readable information further comprises:

e) fifth information for identifying a node adapted to effect the virtual router instance identified by the first information.

19. For use with a router having tunnels defining adjacencies between it and another router of a virtual private network, a method for discovering and distributing network topology information, the method comprising:

a) defining, for each interface of the router, whether the interface is type flooding or type non-flooding; and

b) for each interface of the router, (i) if the interface is type flooding, then flooding network state information over the interface, and (ii) if the interface is type non-flooding, then not flooding network state information over the interface,

wherein, an interface is defined as type flooding if either virtual router interfaced by the interface is a hub, and an interface is defined as type non-flooding if both virtual routers interfaced by the interface are spokes.

20. The method of claim 19 wherein the routers are virtual router instances.

21. The method of claim 19 wherein the routers are physical router instances.

22. The method of claim 19 wherein the routers are selected from a group consisting of:

a) virtual router instances; and

b) physical routers.

23. The method of claim 19 wherein the network state information flooded includes link state information.

24. The method of claim 23 wherein the link state information includes the tunnels as virtual link adjacency information.

25. The method of claim 19 wherein the network state information is flooded in accordance with an interior gateway protocol.

26. The method of claim 19 wherein the network state information is flooded in accordance with an interior gateway protocol selected from a group of protocols consisting of (A) an open shortest path first protocol and (B) an intermediate system-intermediate system protocol.

27. The method of claim 19 wherein the network state information is flooded in accordance with a link state protocol.