Source: https://patents.google.com/patent/US20110286456A1/en
Timestamp: 2020-01-22 04:50:47
Document Index: 129695483

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

US20110286456A1 - Transport networks supporting virtual private networks, and configuring such networks - Google Patents
US20110286456A1
US20110286456A1 US13/205,343 US201113205343A US2011286456A1 US 20110286456 A1 US20110286456 A1 US 20110286456A1 US 201113205343 A US201113205343 A US 201113205343A US 2011286456 A1 US2011286456 A1 US 2011286456A1
US13/205,343
US8493980B2 (en
2006-09-11 Priority to US11/519,110 priority patent/US7620069B2/en
2009-10-27 Priority to US12/606,925 priority patent/US8009674B2/en
2011-08-08 Application filed by Juniper Networks Inc filed Critical Juniper Networks Inc
2011-08-08 Priority to US13/205,343 priority patent/US8493980B2/en
2011-11-24 Publication of US20110286456A1 publication Critical patent/US20110286456A1/en
2013-07-23 Publication of US8493980B2 publication Critical patent/US8493980B2/en
2015-09-29 Assigned to JUNIPER NETWORKS, INC. reassignment JUNIPER NETWORKS, INC. ASSIGNMENT OF ASSIGNORS INTEREST (SEE DOCUMENT FOR DETAILS). Assignors: KOMPELLA, KIREETI
The present application is a continuation of U.S. patent application Ser. No. 12/606,925 (referred to as “the '925 application” and incorporated herein by reference), filed on Oct. 27, 2009, titled “TRANSPORT NETWORKS SUPPORTING VIRTUAL PRIVATE NETWORKS, AND CONFIGURING SUCH NETWORKS” and listing Kireeti KOMPELLA as the inventor, which is a continuation of U.S. patent application Ser. No. 11/519,110 (referred to as “the '110 application” and incorporated herein by reference), filed on Sep. 11, 2006, titled “TRANSPORT NETWORKS SUPPORTING VIRTUAL PRIVATE NETWORKS, AND CONFIGURING SUCH NETWORKS” and listing Kireeti KOMPELLA as the inventor, which issued as U.S. Pat. No. 7,620,069 on Nov. 17, 2009 and which is a continuation of U.S. patent application Ser. No. 09/865,050 (referred to as “the '050 application” and incorporated herein by reference), filed on May 24, 2001, titled “TRANSPORT NETWORKS SUPPORTING VIRTUAL PRIVATE NETWORKS, AND CONFIGURING SUCH NETWORKS,” listing Kireeti KOMPELLA as the inventor, which issued as U.S. Pat. No. 7,136,374 on Nov. 14, 2006, and which claims the benefit of U.S. Provisional Patent Application Ser. No. 60/277,112 (incorporated herein by reference), filed on Mar. 19, 2001 and titled “TRANSPORT NETWORKS SUPPORTING VIRTUAL PRIVATE NETWORKS AND CONFIGURING SUCH NETWORKS.”
§1.2.1.1 Dedicated WANs
§1.2.1.2 Virtual Private Networks
§1.2.2 Limitations of Known Transport Network Technologies
§1.2.3 Layer 3 Virtual Private Networks and Their Perceived Limitations
In the following, an exemplary environment in which the invention may operate is described in §4.1. Then, high-level applications that may be performed by the present invention are introduced in §4.2. Thereafter, operations related to those high-level applications, as well as apparatus, methods and data structures that may be used to effect those high level applications, are described in §4.3. Thereafter, examples of packet forwarding, and network configuration, are provided in §4.4. Finally, some conclusions regarding various aspects of the present invention are provided in §4.5.
§4.1 Exemplary Environment in which the Present Invention may Operate
§4.2 High-Level Applications that may be Performed by the Invention
§4.2.1 Data (Packet) Transport
§4.2.2 Support Virtual Private Networks
The present invention may support virtual private networks (“VPNs”). As stated in §1.2.3 above, private dedicated wide area networks (“WANs”) are beyond the financial reach of most entities. Accordingly, public transport networks have become quite popular. VPNs can provide customers with most or all of the features of private networks, at a greatly reduced cost. However, addressing and security challenges arise when providing VPN services.
§4.2.3 Network Configuration
§4.3 Exemplary Apparatus, Operations, Methods and Data Structures
§4.3.2 Exemplary Methods and Data Structures
§4.3.2.1 Exemplary Packet Forwarding and Layer 2 Transport Methods
FIG. 4 is a high level flow diagram of an exemplary method 330′ that may be used to effect data packet forwarding at an ingress service provider edge device (PE) 212 a′. As indicated by conditional branch point 410, it is assumed that the method 330′ is invoked upon receipt of data (e.g., a packet) from a customer edge device (CE) 260 a′. When a packet arrives at a service provider edge device (PE) 212 a′ from a customer edge device (CE) 260 a′, in a layer 2 virtual private network, the layer 2 address of the packet identifies the destination customer edge device (CE) 260 b′. The configuration operations 320, described in §4.3.2.5 below, will have previously installed a route that maps the layer 2 address (as a channel or circuit identifier) for a given VPN to a first (e.g., outer) label, used to get the data to the proper egress service provider edge device (PE) 212 b′, and a second (e.g., inner) label, associated with the destination customer edge device 260 b′. (See, e.g., information 1040 of FIG. 10, described later.) The channel (or circuit) identifier may be a layer 2 address, a DLCI, a VPI/VCI, etc. Multiple services may be provided over a given physical connection. The method 330′ may use such an installed route to determine inner and outer labels based on the layer 2 address of the destination customer edge device (CE) 260 b′ (as a channel or circuit identifier), as indicated by block 420. The layer 2 address may be stripped from the packet as indicated by block 430. This act 430 is optional, as indicated by the phantom lines. The inner and outer labels may then be added (e.g., prepended) to the data, as indicated by block 440. Finally, the packet may be encapsulated as an MPLS packet, as indicated by block 450 (e.g., provided with header information that identifies it as an MPLS packet), and sent towards the egress service provider edge device (PE) 212 b′ to which the destination customer edge device (CE) 260 b′ is attached, as indicated by block 460. The method 330′ may then be left via RETURN node 470. Naturally, if another layer 2 technology is used in the transport network 210′ instead of MPLS, the packet may be appropriately encapsulated as another type of packet identifying a protocol other than MPLS. For example, other tunneling technologies are possible. Further, generic routing encapsulation (“GRE”) can be used for encapsulation.
§4.3.2.5 Exemplary Configuration Methods
As can be appreciated, within a given VPN, each customer edge device (CE) also “knows” which channel (or circuit) identifier connects it to each other customer edge device (CE). The CE ID of the other CE may be used as an index into the list of channel (or circuit) identifiers this CE has (with zero-based indexing, i.e., 0 is the first index). For example, CE0 is connected to CE3 through its fourth channel (or circuit) identifier, 103. This is the methodology used in the examples illustrated in §4.4 below. The actual methodology used to pick the channel (or circuit) identifier to be used is a local matter. In this way, a first customer edge device (CE) may communicate with a second customer edge device (CE) using a different channel (or circuit) identifier than the one that the second customer edge device (CE) uses to communicate to the first customer edge device (CE). Thus, the service provider transport network effectively acts as a giant Frame Relay switch. This fact advantageously decouples the channel (or circuit) (or circuit) identifiers used at each CE site, thereby simplifying configuration.
§4.3.2.5.1 Advertisement Generation Methods
Value Encapsulation 0 Reserved 1 ATM PDUs (AAL/5) 2 ATM Cells 3 Frame Relay 4 PPP 5 Cisco-HDLC 6 Ethernet VLAN (unswitched) 7 MPLS
§4.3.2.5.2 Received Advertisement Processing Methods
§4.4 Exemplary Operations
§4.4.1 Forwarding Example
An example of data (e.g., a packet) being forwarded in accordance with the present invention is now described with reference to FIGS. 3, 9, 10, 17A and 17B. Referring to FIG. 3, it is assumed that the identifier of a source customer edge device 260 a′ is CE 0, the identifier of a destination customer edge device 260 b′ is CE 4, and that there exists one or more label-switching routers between ingress service provider edge device 212 a′ and egress service provider edge device 212 b′.
Referring to FIG. 17A, the data 1710 sent by the source customer edge device 260 a′ may include layer 2 destination information (e.g., as a channel or circuit identifier) 1712, data 1716, and other information 1714. Referring to
FIG. 9, the source customer edge device 260 a′ may include a channel (or circuit) identifier (e.g., 104) associated with a destination customer edge device (e.g., CE 4) in the VPN. The layer 2 destination information 1712 and/or the other information 1714 may identify the VPN.
§4.4.2 Configuration Example
First, it 212 c may look up the configuration information associated with CE 4. (Recall e.g. 1510 of FIGS. 15 and 1020 of FIG. 10.) In this example, it is assumed that the advertised encapsulation type matches the configured encapsulation type (e.g., both are Frame Relay), so it 212 c proceeds. (Recall 1512 of FIG. 15, 1028 of FIG. 10, 1310 of FIGS. 13 and 1420 of FIG. 14.) Assume that CE 4's range R4 is 9, its channel (or circuit) identifier list D4[] is [107, 209, 265, 301, 414, 555, 654, 777, 888], and its label base L4 is 4000. Since the customer edge devices CE 0 and CE 4 have different identifiers (i.e., 0 and 4) the processing continues. (Recall, e.g., 1518 of FIG. 15.) To reiterate, this check ensures that the addressing information does not conflict within the VPN.
Assume that CE 0's range R0 is 10, its channel (or circuit) identifier list D0[] is [100, 101, 102, 103, 104, 105, 106, 107, 108, 109], and its label base L0 is 1000. Since the customer edge devices CE 0 and CE 4 have different identifiers (i.e., 0 and 4) the processing continues. (Recall, e.g., 1518 of FIG. 15.) To reiterate, this check ensures that the addressing information does not conflict within the VPN.
b) at least one storage device storing processor-executable instructions which, when executed by the at least one processor, perform a method for automatically disseminating information about a newly added customer edge device belonging to a layer 2 virtual private network, from a first transport network edge device to other edge devices of the transport network, the method including
1) generating, by the first transport network edge device, at least one message, the at least one message collectively including a first field for identifying the layer 2 virtual private network to which the newly added customer edge device belongs,
2) copying the at least one message generated to generate a plurality of copies, and
3) forwarding each of copies to one of the other edge devices.
2. The apparatus of claim 1 wherein the acts of copying and forwarding are performed by a device running the Interior Border Gateway Protocol.
3. The apparatus of claim 1 wherein the acts of copying and forwarding are performed by a route reflector device.
4. The apparatus of claim 1 wherein the act of forwarding forwards each of the copies to one of the other edge devices regardless of whether or not the other edge device services a customer edge device belonging to the identified layer 2 virtual private network.
5. The apparatus of claim 1 wherein the act of forwarding forwards at least one of the copies to one of the other edge devices which does not service a customer edge device belonging to the identified layer 2 virtual private network.
6. The apparatus of claim 1 wherein the at least one message generated further includes a second field for identifying a range value associated with the newly added customer edge device, a third field for identifying a label base associated with the newly added customer edge device, and a fourth field for identifying the newly added customer edge device, and wherein a value in the fourth field is unique within the layer 2 virtual private network identified in the first field.
7. The apparatus of claim 1 wherein the at least one message generated further includes a second field for defining an encapsulation type used by the newly added customer edge device.
8. The apparatus of claim 1 wherein the at least one message generated further includes a second field for identifying the first transport network edge device.
9. The apparatus of claim 1 wherein the at least one message generated further includes a second field for identifying a range value associated with the newly added customer edge device, and a third field for identifying a label base associated with the newly added customer edge device, wherein the range value is greater than a number of customer devices presently belonging to the layer 2 virtual private network.
10. Apparatus including:
1) receiving, by a first transport network edge device, a copy of at least one message, the at least one message collectively including a first field for identifying a layer 2 virtual private network to which the newly added customer edge device belongs,
2) determining, by the first transport network edge device, whether the first transport network edge device services a customer edge device belonging to the layer 2 virtual private network identified in the first field, and
3) responsive to a determination that the first transport network edge device belongs to the layer 2 virtual private network identified in the first field, generating information to allow any customer edge devices that both (1) access the transport network via the first transport network edge device, and (2) belong to the layer 2 virtual private network identified in the first field, to communicate with the newly added customer edge device, and otherwise either (A) discarding the copy of the at least one message, or (B) storing at least some of the information contained in the copy of the at least one message at the first transport network edge device.
11. The apparatus of claim 10 wherein at least some of the information contained in the copy of the at least one message was stored at the first transport network edge device, the method further including
4) using the stored information to permit a second new customer device that accesses the transport network via the first transport network edge device to communicate with the newly added customer edge device of the layer 2 virtual private network serviced by a service provider edge device that sourced the at least one message.
12. The apparatus of claim 10 wherein the act of generating information to allow any customer edge devices that both (1) access the transport network via the first transport network edge device, and (2) belong to the layer 2 virtual private network identified in the first field, to communicate with the newly added customer edge device includes
i) determining a first label for getting to a second transport network edge device sourcing the information about the newly added customer edge device,
ii) determining a second label for reaching the newly added customer edge device from the second transport network device,
iii) determining a third label for data from the newly added customer edge device to reach the customer edge devices that both (1) access the transport network via the first transport network edge device, and (2) belong to the layer 2 virtual private network identified in the first field from the first transport network edge device,
iv) determining a first route mapping an identifier of the newly added customer edge device, used by the second customer edge device, to the first label and the second label, and
v) determining a second route mapping the third label to a channel identifier of the second customer edge device.
13. The apparatus of claim 12 wherein the act of determining a second label for reaching the newly added customer edge device from the second transport network edge device includes determining a function of a label base of the newly added customer edge device and a value derived from an identifier of the second customer edge device.
14. The apparatus of claim 12 wherein the act of determining a third label for data from the newly added customer edge device to reach the second customer edge device includes determining a function of a label base of the second customer edge device and a value derived from the identifier of the newly added customer edge device.
15. The apparatus of claim 12 wherein the range associated with the newly added customer edge device corresponds to a number of elements in a list of channel identifiers provisioned at the newly added customer edge device.
16. The apparatus of claim 12 wherein the copy of the at least one message received, by a first transport network edge device, is received from a device running the Interior Border Gateway Protocol.
17. The apparatus of claim 12 wherein the copy of the at least one message received, by a first transport network edge device, is received from a route reflector device.
b) at least one storage medium storing processor-executable instructions which, when executed by the at least one processor, perform a method including
1) receiving, by a first transport network edge device, a copy of at least one message, the at least one message collectively including
i) a first field identifying a layer 2 virtual private network, and
ii) a second field including connectivity information of a newly added customer edge device belonging to the layer 2 virtual private network,
2) determining, by the first transport network edge device, whether or not to process the copy of the at least one message using the connectivity information included in the first field of the copy of the at least one message, and
3) responsive to a determination that the copy of the at least one message is to be processed, generating information to allow any customer edge devices that both (1) access the transport network via the first transport network edge device, and (2) belong to a layer 2 virtual private network to which the newly added customer edge device also belongs, to communicate with the newly added customer edge device, and otherwise either (A) discarding the copy of the at least one message, or (B) storing at least some of the information contained in the copy of the at least one message for future use.
19. The apparatus of claim 18 wherein the connectivity information includes at least one color associated with the newly added customer edge device and a spoke attribute, and wherein the act of determining whether or not to process the copy of the at least one message determines that the newly added customer edge device and the customer edge devices that both (1) access the transport network via the first transport network edge device, and (2) belong to a layer 2 virtual private network to which the newly added customer edge device also belongs are connected if they share a color in common and are not both spokes.
20. The apparatus of claim 18 wherein the connectivity information includes at least two colors associated with the newly added customer edge device and a spoke attribute, and wherein the act of determining whether or not to process the copy of the at least one message determines that the newly added customer edge device and the customer edge devices that both (1) access the transport network via the first transport network edge device, and (2) belong to a layer 2 virtual private network to which the newly added customer edge device also belongs uses the at least two colors.
21. A non-transitory storage medium storing machine-executable instructions which, when executed by a machine, cause the machine to perform a method for automatically disseminating information about a newly added customer edge device belonging to a layer 2 virtual private network, from a first transport network edge device to other edge devices of the transport network, the method including:
a) generating, by the first transport network edge device, at least one message, the at least one message collectively including a first field for identifying the layer 2 virtual private network to which the newly added customer edge device belongs;
b) copying the at least one message generated to generate a plurality of copies; and
c) forwarding each of copies to one of the other edge devices.
22. The non-transitory storage medium of claim 21 wherein the acts of copying and forwarding are performed by a device running the Interior Border Gateway Protocol.
23. The non-transitory storage medium of claim 21 wherein the acts of copying and forwarding are performed by a route reflector device.
24. The non-transitory storage medium of claim 21 wherein the act of forwarding forwards each of the copies to one of the other edge devices regardless of whether or not the other edge device services a customer edge device belonging to the identified layer 2 virtual private network.
25. The non-transitory storage medium of claim 21 wherein the act of forwarding forwards at least one of the copies to one of the other edge devices which does not service a customer edge device belonging to the identified layer 2 virtual private network.
26. The non-transitory storage medium of claim 21 wherein the at least one message generated further includes a second field for identifying a range value associated with the newly added customer edge device, a third field for identifying a label base associated with the newly added customer edge device, and a fourth field for identifying the newly added customer edge device, and wherein a value in the fourth field is unique within the layer 2 virtual private network identified in the first field.
27. The non-transitory storage medium of claim 21 wherein the at least one message generated further includes a second field for defining an encapsulation type used by the newly added customer edge device.
28. The non-transitory storage medium of claim 21 wherein the at least one message generated further includes a second field for identifying the first transport network edge device.
29. The non-transitory storage medium of claim 21 wherein the at least one message generated further includes a second field for identifying a range value associated with the newly added customer edge device, and a third field for identifying a label base associated with the newly added customer edge device, wherein the range value is greater than a number of customer devices presently belonging to the layer 2 virtual private network.
30. A non-transitory storage medium storing machine-executable instructions which, when executed by a machine, cause the machine to perform a method including:
a) receiving, by a first transport network edge device, a copy of at least one message, the at least one message collectively including a first field for identifying a layer 2 virtual private network to which the newly added customer edge device belongs;
b) determining, by the first transport network edge device, whether the first transport network edge device services a customer edge device belonging to the layer 2 virtual private network identified in the first field;
c) responsive to a determination that the first transport network edge device belongs to the layer 2 virtual private network identified in the first field, generating information to allow any customer edge devices that both (1) access the transport network via the first transport network edge device, and (2) belong to the layer 2 virtual private network identified in the first field, to communicate with the newly added customer edge device, and otherwise either (A) discarding the copy of the at least one message, or (B) storing at least some of the information contained in the copy of the at least one message at the first transport network edge device.
31. The non-transitory storage medium of claim 30 wherein at least some of the information contained in the copy of the at least one message was stored at the first transport network edge device, the method further comprising:
d) using the stored information to permit a second new customer device that accesses the transport network via the first transport network edge device to communicate with the newly added customer edge device of the layer 2 virtual private network serviced by a service provider edge device that sourced the at least one message.
32. The non-transitory storage medium of claim 30 wherein the act of generating information to allow any customer edge devices that both (1) access the transport network via the first transport network edge device, and (2) belong to the layer 2 virtual private network identified in the first field, to communicate with the newly added customer edge device includes
33. The non-transitory storage medium of claim 32 wherein the act of determining a second label for reaching the newly added customer edge device from the second transport network edge device includes determining a function of a label base of the newly added customer edge device and a value derived from an identifier of the second customer edge device.
34. The non-transitory storage medium of claim 32 wherein the act of determining a third label for data from the newly added customer edge device to reach the second customer edge device includes determining a function of a label base of the second customer edge device and a value derived from the identifier of the newly added customer edge device.
35. The non-transitory storage medium of claim 32 wherein the range associated with the newly added customer edge device corresponds to a number of elements in a list of channel identifiers provisioned at the newly added customer edge device.
36. The non-transitory storage medium of claim 32 wherein the copy of the at least one message received, by a first transport network edge device, is received from a device running the Interior Border Gateway Protocol.
37. The non-transitory storage medium of claim 32 wherein the copy of the at least one message received, by a first transport network edge device, is received from a route reflector device.
38. A non-transitory storage medium storing machine-executable instructions which, when executed by a machine, cause the machine to perform a method including:
a) receiving, by a first transport network edge device, a copy of at least one message, the at least one message collectively including
ii) a second field including connectivity information of a newly added customer edge device belonging to the layer 2 virtual private network;
b) determining, by the first transport network edge device, whether or not to process the copy of the at least one message using the connectivity information included in the first field of the copy of the at least one message; and
c) responsive to a determination that the copy of the at least one message is to be processed, generating information to allow any customer edge devices that both (1) access the transport network via the first transport network edge device, and (2) belong to a layer 2 virtual private network to which the newly added customer edge device also belongs, to communicate with the newly added customer edge device, and otherwise either (A) discarding the copy of the at least one message, or (B) storing at least some of the information contained in the copy of the at least one message for future use.
39. The non-transitory storage medium of claim 38 wherein the connectivity information includes at least one color associated with the newly added customer edge device and a spoke attribute, and wherein the act of determining whether or not to process the copy of the at least one message determines that the newly added customer edge device and the customer edge devices that both (1) access the transport network via the first transport network edge device, and (2) belong to a layer 2 virtual private network to which the newly added customer edge device also belongs are connected if they share a color in common and are not both spokes.
40. The non-transitory storage medium of claim 38 wherein the connectivity information includes at least two colors associated with the newly added customer edge device and a spoke attribute, and wherein the act of determining whether or not to process the copy of the at least one message determines that the newly added customer edge device and the customer edge devices that both (1) access the transport network via the first transport network edge device, and (2) belong to a layer 2 virtual private network to which the newly added customer edge device also belongs uses the at least two colors.
US13/205,343 2001-03-19 2011-08-08 Transport networks supporting virtual private networks, and configuring such networks Active 2021-09-10 US8493980B2 (en)
US12/606,925 Continuation US8009674B2 (en) 2001-03-19 2009-10-27 Transport networks supporting virtual private networks, and configuring such networks
US13/948,015 Continuation US9042271B2 (en) 2001-03-19 2013-07-22 Transport networks supporting virtual private networks, and configuring such networks
US20110286456A1 true US20110286456A1 (en) 2011-11-24
US8493980B2 US8493980B2 (en) 2013-07-23
US20130156035A1 (en) * 2011-12-19 2013-06-20 Electronics And Telecommunications Research Institute Method and system for domain based packet forwarding
US20130223228A1 (en) * 2012-02-27 2013-08-29 Cisco Technology, Inc., A Corporation Of California Resilient Forwarding of Packets with a Per-Customer Edge (per-CE) Label
FR2846169B1 (en) * 2002-10-22 2005-02-04 At & T Corp Private virtual network based on the label permutation procedure (mpls) adapted to measure traffic exchange between single tariff zones
US10140049B2 (en) 2012-02-24 2018-11-27 Missing Link Electronics, Inc. Partitioning systems operating in multiple domains
RU2685036C2 (en) 2013-01-02 2019-04-16 ЭКСЕЛЕРЕЙШН СИСТЕМЗ, ЭлЭлСи SYSTEMS AND METHOD FOR PROVISION OF ReNAT COMMUNICATION ENVIRONMENT
WO2015119606A1 (en) * 2014-02-06 2015-08-13 Acceleration Systems Systems and methods for providing a multiple secure link architecture
US8885647B2 (en) * 2011-12-19 2014-11-11 Electronics And Telecommunications Research Institute Method and system for domain based packet forwarding
US7136374B1 (en) 2006-11-14
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:KOMPELLA, KIREETI;REEL/FRAME:036678/0008