Automatic selection of site-IDs for virtual private networks

• US 7,986,695 B1
• Filed: 01/10/2006
• Issued: 07/26/2011
• Est. Priority Date: 01/10/2006
• Status: Active Grant

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Kodeboyina, Chaitanya, Kompella, Kireeti, Rekhter, Yakov
• Primary Examiner(s): Ton; Dang T
• Assistant Examiner(s): Zhao; Wei
• Application Number:
  US11/329,371
• Time in Patent Office: 2,023 Days
• Field of Search: 370/392, 370/401, 380/282, 380/44
• US Class Current: 370/392
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/46 Cluster building
• CPC Class Codes: H04L 45/64 using an overlay routing layer

Abstract

Techniques are described for automatically selecting virtual private network (VPN) site-IDs for each customer site within a VPN established over a network. The techniques described herein enable a network router within a VPN to automatically allocate unique site-IDs for each customer site included in the VPN in a dense manner. In some cases, the VPNs may comprise virtual private local area network (LAN) service (VPLS) domains that transmit layer two (L2) traffic between customer sites, i.e., VPLS sites, via the network. For example, a network service provider may configure a network device, such as a router, to belong to one or more VPNs. When a customer site within one of the VPNs connects to the router, the router configures the customer site on the router. The router then automatically selects a site-ID for the customer site configured on the router.

Claims

1. A method comprising:

receiving a plurality of routing protocol advertisements with a first network device from a plurality of other network devices within an existing virtual private network (VPN) to which the first network device belongs, wherein the advertisements include site-IDs currently used by the plurality of other network devices for identifying customer sites that are already configured on the plurality of other network devices for the VPN;

configuring a new customer site of the VPN on the first network device;

automatically selecting, from a set of unused site-IDs, a unique site-ID for the new customer site of the VPN based on the site-IDs included within the received advertisements;

transmitting a claim advertisement for the selected site-ID with the first network device to the plurality of other network devices within the VPN; and

determining, with the first network device, that a collision of site identifiers has occurred and that the site-ID selected for the new customer site conflicts with a site identifier currently used by one of the other routers for a different customer site of the VPN when the first network device receives a routing protocol advertisement from one of the plurality of other network devices that includes the selected site identifier during a predetermined period of time after transmitting the claim advertisement;

upon determining that a collision has occurred, perform collision resolution by;

comparing values of configuration flags included in the claim advertisement from the first network device and the one of the received advertisements from one of the plurality of other network devices within the VPN;

resolving the collision in favor of the network device with the advertisement that includes the configuration flag indicating a manually configured site-ID when the configuration flags do not have the same value;

comparing types of label blocks included in the claim advertisement and the one of the received advertisements when the configuration flags have the same value;

resolving the collision in favor of the network device with the advertisement that includes the type of label block indicating a real advertisement with a non-zero label block size when the types of label blocks are not the same;

comparing local preference values included in the claim advertisement and the one of the received advertisements when the types of label blocks are the same;

resolving the collision in favor of the network device with the advertisement that includes a higher local preference value when the local preference values are not the same;

comparing next-hop values included in the claim advertisement and the one of the received advertisements when the local preference values are the same; and

resolving the collision in favor of the network device with the advertisement that includes a lower next-hop value.

2. The method of claim 1, further comprising:

configuring the first network device to belong to a plurality of VPNs; and

receiving routing protocol advertisements with the first network device from the plurality of other network devices within each of the plurality of VPNs, wherein the routing protocol advertisements include the site-IDs for customer sites of each of the plurality of VPNs configured on the plurality of other network devices.

3. The method of claim 1, wherein the first network device comprises a newly active network device, and wherein receiving the advertisements comprises receiving the advertisements during a first predetermined period of time prior to automatically selecting the unique site-ID for the new customer site.

4. The method of claim 1, wherein the first network device comprises a currently active network device, and wherein receiving the advertisements comprises receiving the advertisements during a second predetermined period of time prior to automatically selecting the unique site-ID for the new customer site.

5. The method of claim 1, further comprising storing information included in the received advertisements in a database within the first network device.

6. The method of claim 1, wherein the received advertisements include site-IDs, control flags, label block sizes, local preferences, and next-hop values.

7. The method of claim 1, further comprising:

generating the set of unused site-IDs for the VPN to which the first network device belongs based on the received advertisements; and

automatically selecting the site-ID for the new customer site from the set of unused site-IDs for the VPN.

8. The method of claim 7, wherein generating the set of unused site-IDs comprises:

generating a set of used site-IDs for the VPN based on the received advertisements; and

comparing the set of used site-IDs with a set of potential site-IDs for the VPN.

9. The method of claim 7, wherein automatically selecting the site-ID comprises automatically selecting the site-ID from the set of unused site-IDs in a sequential manner.

10. The method of claim 7, wherein automatically selecting the site-ID comprises automatically selecting the site-ID from a portion of the set of unused site-IDs in a random manner.

11. The method of claim 1, wherein automatically selecting the site-ID comprises automatically selecting the site-ID for the new customer site to be substantially dense with the site-IDs included in the received advertisements.

12. The method of claim 1, further comprising transmitting an advertisement for the selected site-ID with the first network device to the plurality of other network devices within the VPN.

13. The method of claim 12, wherein transmitting the advertisement comprises transmitting the advertisement with one of the border gateway protocol (BGP) or the label distribution protocol (LDP).

14. The method of claim 1, wherein determining whether a collision occurs comprises:

comparing site-IDs included in the received advertisements with the selected site-ID for the new customer site; and

detecting a collision when a site-ID included in one of the received advertisements is the same as the selected site-ID.

15. The method of claim 14, further comprising transmitting a real advertisement for the selected site-ID with the first network device to the plurality of other network devices within the VPN and using the selected site-ID for the new customer site when a collision is not detected.

16. The method of claim 1, further comprising transmitting a real advertisement for the selected site-ID with the first network device to the plurality of other network devices within the VPN and using the selected site-ID for the new customer site when the collision is resolved in favor of the first network device.

17. The method of claim 1, further comprising withdrawing the claim advertisement from the plurality of other network devices within the VPN and selecting another site-ID for the new customer site configured on the first network device when the collision is not resolved in favor of the first network device.

18. The method of claim 1, further comprising:

receiving withdrawal of advertisements with the plurality of other network devices within the VPN, wherein the advertisements include site-IDs for customer sites configured on the first network device when the first network device is shutting down;

allowing the first network device to reclaim the same site-IDs for the customer sites when the first network device restarts during a predetermined period of time after withdrawal of the advertisements; and

releasing the site-IDs when the first network device does not restart during the predetermined period of time after withdrawal of the advertisements.

19. The method of claim 1, further comprising:

determining that all of a plurality of interfaces between the new customer site and the first network device are disconnected;

transmitting an advertisement for the selected site-ID that includes an indication that all of the plurality of interfaces are disconnected; and

maintaining the site-ID for the new customer site within a set of used site-IDs for the VPN while all of the plurality of interfaces are disconnected.

20. The method of claim 1, further comprising:

determining that at least one of a plurality of interfaces between the new customer site and the first network device is disconnected;

transmitting an advertisement for the selected site-ID that includes an indication that the at least one of the plurality of interfaces is disconnected; and

maintaining the site-ID for the new customer site within a set of used site-IDs for the VPN while the at least one of the plurality of interfaces is disconnected.

21. The method of claim 1, wherein the VPN comprises a virtual private local area network service (VPLS) domain and the customer sites comprise VPLS sites.

22. The method of claim 1, wherein the network devices comprise routers.

23. A non-transitory computer-readable medium comprising instructions that cause a programmable processor to:

receive a plurality of routing protocol advertisements with a first network device from a plurality of other network devices within an existing virtual private network (VPN) to which the first network device belongs, wherein the advertisements include site-IDs for customer sites of the VPN configured on the plurality of other network devices;

configure a new customer site of the VPN on the first network device;

automatically select, from a set of unused site-IDs, a unique site-ID for the new customer site of the VPN based on the received advertisements;

transmit a claim advertisement for the selected site-ID with the first network device to the plurality of other network devices within the VPN; and

determine, with the first network device, that a collision of site identifiers has occurred and that the site-ID selected for the new customer site conflicts with a site identifier currently used by one of the other routers for a different customer site of the VPN when the first network device receives a routing protocol advertisement from one of the plurality of other network devices that includes the selected site identifier during a predetermined period of time after transmitting the claim advertisement;

upon determining that a collision has occurred, perform collision resolution by;

comparing values of configuration flags included in the claim advertisement from the first network device and the one of the received advertisements from one of the plurality of other network devices within the VPN;

resolving the collision in favor of the network device with the advertisement that includes the configuration flag indicating a manually configured site-ID when the configuration flags do not have the same value;

comparing types of label blocks included in the claim advertisement and the one of the received advertisements when the configuration flags have the same value;

resolving the collision in favor of the network device with the advertisement that includes the type of label block indicating a real advertisement with a non-zero label block size when the types of label blocks are not the same;

comparing local preference values included in the claim advertisement and the one of the received advertisements when the types of label blocks are the same;

resolving the collision in favor of the network device with the advertisement that includes a higher local preference value when the local preference values are not the same;

comparing next-hop values included in the claim advertisement and the one of the received advertisements when the local preference values are the same; and

resolving the collision in favor of the network device with the advertisement that includes a lower next-hop value.

24. The computer-readable medium of claim 23, further comprising instructions that cause the programmable processor to:

generate the set of unused site-IDs for the VPN to which the first network device belongs based on the received advertisements; and

automatically select the site-ID for the new customer site from the set of unused site-IDs for the VPN.

25. The computer-readable medium of claim 23, wherein the instructions that cause the programmable processor to determine whether a collision occurs cause the programmable processor to:

compare site-IDs included in the received advertisements with the selected site-ID for the new customer site; and

detect a collision when a site-ID included in one of the received advertisements is the same as the selected site-ID.

26. The computer-readable medium of claim 25, further comprising instructions that cause the programmable processor to:

transmit a real advertisement for the selected site-ID with the first network device to the plurality of other network devices within the VPN and using the selected site-ID for the new customer site when a collision is not detected; and

perform collision resolution procedures with the first network device when a collision is detected.

27. The computer readable medium of claim 23, further comprising instructions that cause the programmable processor to:

receive withdrawal of advertisements with the plurality of other network devices within the VPN, wherein the advertisements include site-IDs for customer sites configured on the first network device when the first network device is shutting down;

allow the first network device to reclaim the same site-IDs for the customer sites when the first network device restarts during a predetermined period of time after withdrawal of the advertisements; and

release the site-IDs when the first network device does not restart during the predetermined period of time after withdrawal of the advertisements.

28. The computer-readable medium of claim 23, further comprising instructions that cause the programmable processor to:

determine that all of a plurality of interfaces between the new customer site and the first network device are disconnected;

transmit an advertisement for the selected site-ID that includes an indication that all of the plurality of interfaces are disconnected; and

maintain the site-ID for the new customer site within a set of used site-IDs for the VPN while all of the plurality of interfaces are disconnected.

29. The computer-readable medium of claim 23, further comprising instructions that cause the programmable processor to:

determine that at least one of a plurality of interfaces between the new customer site and the first network device is disconnected;

transmit an advertisement for the selected site-ID that includes an indication that the at least one of the plurality of interfaces is disconnected; and

maintain the site-ID for the new customer site within a set of used site-IDs for the VPN while the at least one of the plurality of interfaces is disconnected.

30. A first network device comprising:

a control unit that receives a plurality of routing protocol advertisements from a plurality of other network devices within an existing virtual private network (VPN) to which the first network device belongs, wherein the advertisements include site-IDs for customer sites of the VPN configured on the plurality of other network devices;

a VPN module included in the control unit that configures a new customer site of the VPN on the first network device;

a site-ID allocation module included in the control unit that automatically selects, from a set of unused site-IDs, a unique site-ID for the new customer site of the VPN based on the received advertisements;

a collision resolution module included in the control unit that determines whether a collision occurs based on advertisements received from the plurality of other network devices during a predetermined period of time after the control unit transmits the claim advertisement, wherein the collision resolution module;

compares values of configuration flags included in the claim advertisement from the first network device and the one of the received advertisements from one of the plurality of other network devices within the VPN;

resolves the collision in favor of the network device with the advertisement that includes the configuration flag indicating a manually configured site-ID when the configuration flags do not have the same value;

compares types of label blocks included in the claim advertisement and the one of the received advertisements when the configuration flags have the same value;

resolves the collision in favor of the network device with the advertisement that includes the type of label block indicating a real advertisement with a non-zero label block size when the types of label-blocks are not the same;

compares local preference values included in the claim advertisement and the one of the received advertisements when the types of label blocks are the same;

resolves the collision in favor of the network device with the advertisement that includes a higher local preference value when the local preference values are not the same;

compares next-hop values included in the claim advertisement and the one of the received advertisements when the local preference values are the same; and

resolves the collision in favor of the network device with the advertisement that includes a lower next-hop value.

31. The first network device of claim 30, wherein the first network device belongs to a plurality of VPNs, the control unit receives advertisements from a plurality of other network devices within each of a plurality of VPNs, wherein the advertisements include site-IDs for customer sites of each of the plurality of VPNs configured on the plurality of other network devices.

32. The first network device of claim 30, wherein the first network device comprises a newly active network device, and wherein the control unit receives the advertisements from the plurality of other network devices during a first predetermined period of time before the site-ID allocation module automatically selects the unique site-ID for the new customer site.

33. The first network device of claim 30, wherein the first network device comprises a currently active network device, and wherein the control unit receives advertisements from the plurality of other network devices during a second predetermined period of time before the site-ID allocation module automatically selects the unique site-ID for the new customer site.

34. The first network device of claim 30, wherein the VPN module stores information included in the received advertisements in a database included in the control unit, wherein the received advertisements include site-IDs, control flags, label block sizes, local preferences, and next-hop values.

35. The first network device of claim 30, wherein the site-ID allocation module generates a set of unused site-IDs for the VPN based on the received advertisements, and automatically selects the site-ID for the new customer site from the set of unused site-IDs for the VPN.

36. The first network device of claim 35, wherein the VPN site-ID allocation module automatically selects the site-ID from the set of unused site-IDs in a sequential manner.

37. The first network device of claim 35, wherein the site-ID allocation module automatically selects the site-ID from a portion of the set of unused site-IDs in a random manner.

38. The first network device of claim 30, wherein the site-ID allocation module automatically selects the site-ID for the new customer site to be substantially dense with the site-IDs included in the received advertisements.

39. The first network device of claim 30, wherein the control unit transmits a claim advertisement for the selected site-ID to the plurality of other network devices within the VPN.

40. The first network device of claim 39, wherein the control unit uses one of the border gateway protocol (BGP) or the label distribution protocol (LDP) to transmit the advertisement.

41. The first network device of claim 30, wherein the collision resolution module compares site-IDs included in the received advertisements with the selected site-ID for the new customer site, and detects a collision when a site-ID included in one of the received advertisements is the same as the selected site-ID.

42. The first network device of claim 41,

wherein the control unit transmits a real advertisement for the selected site-ID to the plurality of other network devices within the VPN and uses the selected site-ID for the new customer site when a collision is not detected, and

wherein the collision resolution module performs collision resolution procedures when a collision is detected.

43. The first network device of claim 42, wherein the control unit transmits a real advertisement for the selected site-ID to the plurality of other network devices within the VPN and uses the selected site-ID for the new customer site when the collision resolution module resolves the collision in favor of the first network device.

44. The first network device of claim 42,

wherein the control unit withdraws the claim advertisement from the plurality of other network devices within the VPN when the collision resolution module does not resolve the collision in favor of the first network device, and

wherein the site-ID allocation module selects another site-ID for the new customer site.

45. The first network device of claim 32, wherein the configuration flag included in an advertisement indicates a manually configured site-ID when set to a value of zero and indicates an automatically generated site-ID when set to a value of one.

46. The first network device of claim 32, wherein the type of label block included in an advertisement indicates a claim advertisement when set to a zero label block size and indicates a real advertisement when set of a non-zero label block size.

47. The first network device of claim 30,

wherein the control module withdraws advertisements including site-IDs for customer sites configured on the first network device when the first network device is shutting down,

wherein the plurality of other network devices within the VPN allow the first network device to reclaim the same site-IDs for the customer sites when the first network device restarts during a predetermined period of time after withdrawal of the advertisements, and

wherein the plurality of other network device within the VPN release the site-IDs when the first network device does not restart during the predetermined period of time after withdrawal of the advertisements.

48. The first network device of claim 30,

wherein the control unit determines that all of a plurality of interfaces between the new customer site and the first network device are disconnected, and transmits an advertisement for the selected site-ID including an indication that all of the plurality of interfaces are disconnected, and

wherein the plurality of other network devices within the VPN maintain the site-ID for the new customer site on the first network device within a set of used site-IDs for the VPN while all of the plurality of interfaces are disconnected.

49. The first network device of claim 48, wherein the indication included in the advertisement comprises a disconnect flag that indicates at least one of the plurality of interfaces are connected when set to a value of zero, and indicates all of the plurality of interfaces are disconnected when set of a value of one.

50. The first network device of claim 30,

wherein the control unit determines that at least one of a plurality of interfaces between the new customer site and the first network device is disconnected, and transmits an advertisement for the selected site-ID including an indication that the at least one of the plurality of interfaces is disconnected, and

wherein the plurality of other network devices within the VPN maintain the site-ID for the new customer site on the first network device within a set of used site-IDs for the VPN while the at least one of the plurality of interfaces is disconnected.

51. The first network device of claim 50, wherein the indication included in the advertisement comprises a disconnect flag that indicates all of the plurality of interfaces are connected when set to a value of zero, and indicates at least one of the plurality of interfaces is disconnected when set of a value of one.

52. The first network device of claim 30, wherein the VPN comprises a virtual private local area network service (VPLS) and the customer sites comprise VPLS sites.

53. The first network device of claim 30, wherein the network devices comprise routers.

54. A system for automatically selecting virtual private network (VPN) site-IDs, the system comprising:

at least one VPN established over a network;

a plurality of customer sites; and

a plurality of routers,

wherein each of the plurality of routers is coupled to at least one of the plurality of customer sites, and

wherein each of the plurality of routers is configured to belong to at least one of the VPNs, and

wherein each of the plurality of routers is configured to transmit a routing protocol advertisement, each of the advertisements comprising a site-ID for the customer site of the VPN to which the router is configured to belong,

wherein a first router of the plurality of routers automatically selects an unused site-ID for one of the plurality of customer sites to which the first router is coupled when the customer site to which the first router is coupled is a new customer site of the VPN,

wherein, when selecting the site-ID, the first router executes a collision resolution procedure to determine that the site-ID selected for the new customer site conflicts with a site-ID advertised by one of the other routers for a different one of the customer sites during a predetermined period of time after transmitting the claim advertisement; and

wherein the first router performs a resolution procedure with the collision resolution module to use the selected site-ID for the new customer network or select a different unique site-ID for the new customer site.

55. The system of claim 54, wherein each of the plurality of routers uses one of the border gateway protocol (BGP) or the label distribution protocol (LDP) to transmit an advertisement.

56. A method for automatically selecting unique virtual private network site identifiers (site-IDs) for customer sites of a virtual private network comprising:

executing a routing protocol on a processor of a router to exchange routing protocol advertisements with a plurality of other routers within a network, wherein each of the routers is coupled to one or more customer sites of the virtual private network, and wherein the routing protocol advertisements include site identifiers currently assigned to the customer sites by the routers;

executing, on the router, a VPN module that configures a new customer site for the virtual private network;

executing, on the router, a site identifier allocation module that determines a set of unused site identifiers for the virtual private network based on the site identifiers specified within the received routing protocol advertisements and selects a unique site identifier for the new customer site from the set of unused site identifiers for the VPN;

transmitting, with the routing protocol, a routing protocol advertisement to the other routers to claim the selected site identifier for the new customer site;

executing a collision resolution module on the router to determine that the site identifier selected for the new customer site conflicts with a site identifier selected by one of the other routers for a different customer site upon receiving a routing protocol advertisement that includes the selected site identifier; and

performing a resolution procedure with the collision resolution module to use the selected site identifier for the new customer network or select a different unique site identifier for the new customer site.