Source: http://www.google.com/patents/US20090080431
Timestamp: 2017-10-24 03:20:38
Document Index: 622169843

Matched Legal Cases: ['§ 119', '§ 112', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4']

Patent US20090080431 - Edge devices for providing a transparent lan segment service and ... - Google Patents
A transport LAN segment service is provided over a transport network. The transport network will include edge devices configured to support one or more transparent LAN segments. Configuration is simplified by advertising TLS-port-label information, layer 2 address learning, and multicasting when the...http://www.google.com/patents/US20090080431?utm_source=gb-gplus-sharePatent US20090080431 - Edge devices for providing a transparent lan segment service and configuration such edge devices
Publication number US20090080431 A1
Application number US 12/329,858
Also published as US7463639, US7983286, US8693487, US20110206057
Publication number 12329858, 329858, US 2009/0080431 A1, US 2009/080431 A1, US 20090080431 A1, US 20090080431A1, US 2009080431 A1, US 2009080431A1, US-A1-20090080431, US-A1-2009080431, US2009/0080431A1, US2009/080431A1, US20090080431 A1, US20090080431A1, US2009080431 A1, US2009080431A1
Original Assignee Yakov Rekhter
Patent Citations (1), Referenced by (65), Classifications (8), Legal Events (2)
US 20090080431 A1
1. For use in an edge device of a transport network adapted to provide a transparent LAN segment service, a method for processing ingress data received by a port of the edge device, the method comprising:
d) forwarding the modified data towards an edge device identified by the edge device identifier of the selected one of the at least one entry of the selected forwarding information.
6. The method of claim 1 wherein the act of forwarding the modified data towards an edge device identified by the edge device identifier of the selected one of the at least one entry of the selected forwarding information includes
7. For use in an edge device of a transport network adapted to provide a transparent LAN segment service, a method for processing egress data, having a label, received by the edge device, the method comprising:
a) determining, using the edge device, a port of the edge device based on at least one of the label and a layer 2 address of the egress data; and
b) providing, using the edge device, at least a part of the egress data to the port determined.
8. The method of claim 7 wherein the act of determining a port of the edge device based on the label and a layer 2 address of the egress data includes
iii) determining the port of the edge device to be the port associated with the layer 2 address of the selected one of the at least one entry of the selected forwarding information.
10. The method of claim 7 wherein the determined port identifier is associated with a transparent LAN segment,
11. The method of claim 7 wherein the egress data is an Ethernet packet provided with a label, and
14. For use by an egress edge device of a transport network supporting a transparent LAN segment service, a method for populating a forwarding table associated with a transparent LAN segment based on data received, the data received including a label and a layer 2 source address, the method comprising:
a) determining, using the egress edge device, an edge device of the transport network on which the data entered the transport network based on the label of the data received;
b) determining, using the egress edge device, a port of the determined edge device on which the data entered the determined edge device based on the label of the data received; and
c) generating, using the egress edge device, an entry in the forwarding table, the entry including
iii) a label associated with the determined port.
15. The method of claim 14 wherein the label information includes a label base, and a label range,
16. The method of claim 15 wherein the label information further includes a label block offset, and
17. The method of claim 14 wherein the data received is an Ethernet packet and wherein each of the layer 2 addresses is a media access control address.
18. For use by an edge device of a transport network supporting a transparent LAN segment service, a method determining forwarding information based on data received on a local port, the data received including a layer 2 source address, the method comprising:
a) determining, using the edge device, a forwarding table associated with the transparent LAN segment based on the local port on which the data was received; and
b) generating, using the edge device, an entry in the forwarding table determined, the entry including
i) a layer 2 address set to the layer 2 source address of the data, and
ii) a port set to the local port on which the data was received.
19. The method of claim 18 wherein the data received is an Ethernet packet and wherein each of the layer 2 addresses is a media access control address.
20. A device for use at the edge of a transport network supporting a transparent LAN segment service, the device comprising:
i) a first forwarding table, the first forwarding table including at least one entry, one of the at least one entry including
A) a layer 2 address,
B) a label associated with the layer 2 address, and
C) an egress edge device identifier associated with the layer 2 address,
wherein the label is used by an egress edge device identified by the egress edge device identifier to determine a port associated with the layer 2 address, and
ii) a second forwarding table including transport network forwarding information associated with the egress edge device;
b) means for applying the label to ingress data to generate modified data; and
c) a forwarding facility for forwarding the modified data towards an appropriate egress edge device based on the forwarding information of the second forwarding table.
21. The device of claim 20 wherein the ingress data is an Ethernet packet and wherein each of the layer 2 addresses is a media access control address.
22. The device of claim 20 wherein the first forwarding table further includes at least one other entry including
A) a layer 2 address, and
B) a port on the device associated with the layer 2 address.
23. The device of claim 20 wherein the first forwarding table further includes at least one other entry including at least one set of associated information, each of the at least one set of associated information including a label and an associated edge device identifier, wherein the at least one other entry does not include a layer 2 address.
24. A transport network providing a transparent LAN segment service between a first LAN and a second LAN, the transport network comprising:
a) a first transport network edge device, the first transport network edge device having
i) a port, coupled with the first LAN, for receiving ingress data including a layer 2 destination address,
ii) a storage facility for storing
A) a first forwarding table, the first forwarding table including at least one entry, one of the at least one entry including
1) a layer 2 address,
2) a label associated with the layer 2 address, and
3) a second transport network edge device identifier associated with the layer 2 address, and
B) a second forwarding table including transport network forwarding information associated with the second transport network edge device, and
iii) a forwarding facility for
A) applying the label to the received ingress data to generate modified data, and
B) forwarding the modified data towards the second edge device based on the forwarding information of the second forwarding table; and
b) the second transport network edge device, the second transport network edge device having
i) a port coupled with the second LAN,
ii) a forwarding table including at least one entry including
A) the layer 2 address, and
B) the port associated with the layer 2 address, and
ii) a forwarding facility for placing received data on the port
wherein the label is used by the forwarding facility of the second transport network edge device to determine the port associated with the layer 2 address.
This application is a continuation application of U.S. patent application Ser. No. 10/123,353, filed on Apr. 16, 2002, titled “EDGE DEVICES FOR PROVIDING A TRANSPARENT LAN SEGMENT SERVICE AND CONFIGURATION SUCH EDGE DEVICES”, listing Yakov Rekhter as the inventor, scheduled to issue as U.S. Pat. No. 7,463,639 on Dec. 9, 2008, and which claimed benefit, under 35 U.S.C. § 119(e)(1), to the filing date of provisional patent application Ser. No. 60/325,344, entitled “SUPPORT OF TRANSPARENT LAN SEGMENT”, filed on Sep. 26, 2001 and listing Yakov Rekhter as the inventor, for any inventions disclosed in the manner provided by 35 U.S.C. § 112, ¶ 1. Those utility and provisional applications are expressly incorporated herein by reference. The present invention is not limited to any particular embodiments described in those applications.
For many entities (such as businesses, universities, etc.), local area networks (or “LANs”) suffice for intra-entity communications. Indeed, LANs are quite popular since they are relatively inexpensive to deploy, operate, and manage, and are based on mature, well-developed technology, such as Ethernet, for example. Unfortunately, however, most entities need to communicate (voice and/or data) with their own facilities, or others, beyond their immediate location. Thus, wide area networks (or “WANs”) are needed. Very often, entities want at least some privacy or security attached to their communications.
Dedicated wide area networks (“WANs”) are typically implemented using leased lines or dedicated circuits to connect multiple sites. Customer premise equipment (“CPE”) routers or switches at these sites connect these leased lines or dedicated circuits together to facilitate connectivity between each site of the network. Most private networks with a relatively large number of sites will not have “fully meshed” networks (i.e., direct connections between each of the sites) due to the cost of leased lines or dedicated circuits and to the complexity of configuring and managing customer premises equipment. Rather, some form of hierarchical network topology is typically employed in such instances. 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 (or “RBOCs”), or some other service provider, are often used to allow remote users to connect to an enterprise network using the public-switched telephone network (or “PSTN”), an integrated services digital network (or “ISDN”), or some other type of transport network technology. (Note that the word “public” in the phrase “public transport network” connotes the fact that more than one entity may use it, even though it may be privately owned and managed, and not available to the general public.) Such remote access may be facilitated by deploying network access servers (or “NASs”) at one or more central cites. When users connect to (e.g., dial into) a NAS, it works with authentication, authorization and accounting (or “AAA”) servers to verify the identity of the user and to check which services that user is authorized to use.
As can be appreciated, private dedicated WANs are beyond the financial reach of many entities. Accordingly, so-called public transport networks have become quite popular. Unfortunately, however, various incompatible public transport networks have been introduced over the years in response to the then perceived needs to support various applications. Examples of such public transport network technologies include switched multimegabit data service (“SMDS”), X.25 packet switched networks, frame relay, broadband ISDN, and asynchronous transport mode (“ATM”).
The fact that public transport networks use incompatible technologies has two onerous implications for service providers. First, technologies with which customers access the transport network (referred to as “access technologies”) must be compatible with the technology used in the transport network (unless there is a handoff between networks, which is expensive). Thus, customers are locked into a technology from end-to-end. Further, such dependencies between access technologies and transport network technologies have forced public transport network service providers to support, maintain and administer separate networks.
The present invention may be use to (i) provide data transport that can act as a transparent LAN segment, (ii) facilitate the provisioning one or more such a transparent LAN segments, and (iii) facilitate the configuration of the transport network, including the service provider edge devices, to support a provisioned transparent LAN segment service.
As a packet destined for a particular device (as defined by a layer 2, e.g., MAC, destination address) is forwarded from a source device on a first LAN to a destination device on a second LAN, where both the first and second LANs are coupled via a transparent LAN segment, it may traverse a path having three basic parts; namely, (i) from the first LAN to an associated ingress service provider edge device, (ii) from that ingress service provider edge device to an egress service provider edge device associated with the second LAN having the destination device, and (iii) from that egress service provider edge device to the second LAN. The second part of the path—from the ingress service provider edge device to the egress service provider edge device—may exploit known label switched path forwarding techniques.
Using the present invention, an ingress PE router R1 can cause a packet to be delivered to the egress PE router R2 by pushing some label onto the packet and sending the result to one of its adjacencies. This label is referred to as the “tunnel label”, and the corresponding label switched path is referred to as the “tunnel LSP”. Such tunnel LSPs could be established via known protocols such as BGP, LDP, RSVP, for example. The tunnel LSP merely gets packets from the ingress PE router R1 to the egress PE router R2—the corresponding tunnel label doesn't tell the egress PE router R2 what to do with the payload. In fact, if penultimate hop popping is used, the egress PE router R2 may never even see the corresponding tunnel label. (If the ingress PE router R1 itself is the penultimate hop, a tunnel label may not even get pushed on.) The present invention may be used to provide an additional label, which is made available to the egress PE router R2 (it may be encapsulated by the tunnel label so that it is preserved), and which is used by the egress PE router R2 to determine how to treat the received packet. This label is referred to as the “TLS label”.
To avoid the need to make global changes (i.e., to all PEs) to configuration information each time a port is added to a TLS, the present invention may permit the service provider to configure ports locally (i.e., at the given edge device PE having the added port). The present invention may do so by providing (e.g., signaling), to all other service provider edge devices (PEs) that support the TLS, an identifier of the service provider edge device, an identifier of the TLS, a port identifier and label information used by the port. The label information may include a label offset (if any), a label base, and a label range. Service provider edge devices (PEs) receiving such signaling may then update a layer 2 (MAC) forwarding information table (an/or TLS information) related to the TLS. The service provider edge device (PE) may also update the layer 2 (MAC) forwarding information table related to the TLS based on packets received either locally, or from another (remote) service provider edge device (PE). If a forwarding entry for a particular layer 2 (MAC) destination address is not yet provided, instances of a packet destined to that layer 2 (MAC) address may be forwarded to any and all PEs having at least one port belonging to the relevant TLS. That is, multicasting packets based on “wild card” entries may be used as an interim solution until forwarding information for the layer 2 (MAC) destination device is learned/discovered.
FIG. 9 illustrates the arrangement of drawing sheets including FIGS. 9A and 9B which collectively illustrate a flow diagram of an exemplary method that may be used to effect ingress service provider edge device forwarding operations.
The present invention involves novel methods, apparatus and data structures for providing a transport network that can act as a transparent LAN segment, as well as methods, apparatus and data structures for provisioning and configuring such a transport network. The following description is presented to enable one skilled in the art to make and use the invention, and is provided in the context of particular applications and their requirements. Various modifications to the disclosed embodiments will be apparent to those skilled in the art, and the general principles set forth below may be applied to other embodiments and applications. Thus, the present invention is not intended to be limited to the embodiments shown and the inventor regards his invention as the following disclosed methods, apparatus and data structures and any other patentable subject matter.
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, an exemplary service provider edge device (PE) that may be used to effect various aspects of the present invention is introduced in § 4.3. Then, exemplary methods and data structures that may be effected by and stored by, respectively, a service provider edge device are described in § 4.4. Thereafter, examples of network configuration and packet forwarding, are provided in § 4.5. Finally, some conclusions regarding various aspects of the present invention are provided in § 4.6.
FIG. 1 illustrates an exemplary environment 100 in which the present invention may operate. A service provider may operate a transport network 110 to provide a transparent LAN segment service for use by a customer having multiple LANs 140 at multiple sites. Each of the LANs 140 may have a one or more host devices (not shown), and may be coupled with the transport network 110 via a customer edge (“CE”) device (not shown). The customer edge device may, in turn, be coupled with a service provider edge (“PE”) device 120, such as a router for example. Internal nodes 130, such as routers, may be used to permit communications between various service provider edge devices 120 of the transport network 110. In this environment 100, a virtual LAN 150 may include LANs 140 a-d, as well as transparent LAN segments 155 a-c. The transparent LAN segments 155 a-c can be thought of as coupling or bridging geographically remote LANs 140 a-d.
In one exemplary embodiment, the transport network 110 may be a label-switching network, such as a multi-protocol label switching (“MPLS”) network. FIG. 2 illustrates a label switched path 130′ across a network 110′. Notice that label switched paths 130′ may be simplex—traffic flows in one direction from a head-end label switching router (or “LSR”) 120 a′ at an ingress edge to a tail-end label switching router 120 c′ at an egress edge. Duplex traffic typically requires two label switched paths—one for each direction. Notice that a label switched path 130′ is defined by the concatenation of one or more label-switched hops, allowing a packet to be forwarded from one label switching router (LSR) to another across the MPLS domain 130′.
As is known, a label may be a short, fixed-length value carried in the packet's header to identify a forwarding equivalence class (or “FEC”). An FEC is a set of packets that are forwarded over the same path through a network even if their ultimate destinations are different. Alternatively, labels needn't be explicitly defined in a packet's header. Labels may be inferred. For example, in Generalized MPLS, a label could be a time slot (e.g., in SONET/SDH cross-connects), or even a port number (e.g., in Optical Cross-Connects).
FIG. 3 illustrates the operation of a label-switched path. The present invention may use labels as “tunnel labels” to transport data from an ingress service provider edge device to an egress service provider edge device. In such a case, at the ingress edge of the network, the router 320 a may operate in accordance with the method 450 a′ described with reference to FIG. 9 to assign each packet an initial tunnel label (as well as a TLS label, described later). More specifically, referring to the example illustrated in FIG. 3, an ingress label switching router 320 a determines a transparent LAN segment based on the port on which the unlabeled packet was received. (Note that if virtual LANs (“VLANs”) are supported, a port may have multiple VLANs associated with it. In this case, a transparent LAN segment is determined based on a combination of the port on which the unlabeled packet was received and the VLAN-id carried in the packet.) Using a layer 2 (MAC) forwarding information table associated with the determined transparent LAN segment and ingress port, a destination (e.g., MAC) address 340 of the unlabeled packet is used to determine an inner (TLS) label and an egress edge device. An appropriate tunnel label is then determined based on the determined egress edge device. To reiterate, this tunnel label is used for forwarding the packet to the proper egress label switching router 320 c (The TLS label is used for forwarding the packet from the egress label switching router 320 c.).
In the MPLS domain, the label switching routers (LSRs) 330 simply forward the packet using label-swapping. More specifically, when a labeled packet arrives at a label switching router (LSR), the input port number and the tunnel label are used as lookup keys into an MPLS forwarding table. When a match is found, the forwarding component retrieves the associated outgoing label, the outgoing interface (or port), and the next hop address from the forwarding table. The incoming tunnel label is replaced with the outgoing tunnel label and the packet is directed to the outgoing interface for transmission to the next hop in the label switched path. FIG. 3 illustrates such label switching by label switching routers (LSRs) 330 a and 330 b.
When the labeled packet arrives at the egress label switching router 320 c, the router may operate in accordance with the method 450 b′ described with reference to FIG. 10 to determine a port on which to place the packet based on the layer 2 (e.g., MAC) address of the packet and information in a layer 2 (MAC) forwarding information table selected based on the TLS label that was applied to the packet at the ingress router 320 a.
The forgoing description of the packet forwarding using label switching presumed the existence of label switched paths and associated label entries in forwarding tables. These paths are determined and provided to each of the label switching routers (LSRs) in the label-switched path (LSP). Such path determination and distribution may be performed using known label distribution protocols such as label distribution protocol (“LDP”), resource reservation protocol (“RSVP”) and border gateway protocol (“BGP”).
As described below, a high-level application of the present invention may be to provide data transport that can act as a transparent LAN segment. This application is further described in § 4.2.1 below. Another high-level application of the present invention may be to facilitate the provisioning one or more such a transparent LAN segments. This application is further described in § 4.2.2 below. Yet another high-level application of the present invention may be to facilitate the configuration of the transport network, including the service provider edge devices, to support a provisioned transparent LAN segment service. This application is further described in § 4.2.3 below.
As a packet destined for a particular device (as defined by a layer 2, e.g., MAC, destination address) is forwarded from a source device on a first LAN to a destination device on a second LAN, where both the first and second LANs are coupled via a transparent LAN segment, it traverses a path having three basic parts; namely, (i) from the first LAN to an associated ingress service provider edge device, (ii) from that ingress service provider edge device to an egress service provider edge device associated with the second LAN having the destination device, and (iii) from that egress service provider edge device to the second LAN. Exemplary methods and data structures for effecting the first and third parts of the path are described in more detail in § 4.4.2 below, with reference to FIGS. 7, 9 and 10. The second part of the path—from the ingress service provider edge device to the egress service provider edge device—may exploit known label switched path forwarding techniques, as described below in terms of inter-PE connectivity.
Assume it is desired to transport an Ethernet packet from ingress PE router (R1) to egress PE router (R2), across an intervening MPLS network (Assume that there is a label switched path from R1 to R2.). That is, the ingress PE router R1 can cause a packet to be delivered to the egress PE router R2 by pushing some label onto the packet and sending the result to one of its adjacencies. This label is referred to as the “tunnel label”, and the corresponding label switched path is referred to as the “tunnel LSP”. Such tunnel LSPs could be established via known protocols such as BGP, LDP, RSVP, for example. The tunnel LSP merely gets packets from the ingress PE router R1 to the egress PE router R2—the corresponding tunnel label doesn't tell the egress PE router R2 what to do with the payload. In fact, if penultimate hop popping is used, the egress PE router R2 may never even see the corresponding tunnel label. (If the ingress PE router R1 itself is the penultimate hop, a tunnel label may not even get pushed on.) Thus the present invention provides an additional label, which is made available to the egress PE router R2 (it may be encapsulated by the tunnel label so that it is preserved), and which is used by the egress PE router R2 to determine how to treat the received packet. This label is referred to as the “TLS label”.
§ 4.2.2 Provisioning Transparent LAN Segments
For each TLS offered by a service provider, the service provider provisions its edge devices (PEs) such that within a given TLS, each (logical) port has a unique number (referred to as “port ID”). In addition, for each TLS offered by the service provider, the service provider estimates the number of ports that are to belong to the TLS. Note that this is just an estimate, and from a practical point of view the service provider should overprovision this number. For each TLS that has at least one port on a given service provider edge device (PE), the PE is configured with the estimated number of ports of that TLS.
Exemplary methods and data structures for effecting the provisioning of ports to TLSs, and TLS labels to ports, are described in more detail in § 4.4.1 below, with reference to FIGS. 5, 6 and 8.
The service provider edge device (PE) may also update the layer 2 (MAC) forwarding information table related to the TLS based on packets received either locally, or from another (remote) service provider edge device (PE). If a forwarding entry for a particular layer 2 (MAC) destination address is not yet provided, instances of a packet destined to that layer 2 (MAC) address may be forwarded to any and all PEs having at least one port belonging to the relevant TLS. That is, multicasting packets based on “wild card” entries may be used as an interim solution until forwarding information for the layer 2 (MAC) destination device is learned/discovered.
Exemplary methods and data structures for effecting various aspects of configuration are described in more detail in § 4.4.3 below, with reference to FIGS. 7 and 13-15.
§ 4.3 EXEMPLARY APPARATUS
FIG. 4 is a bubble chart of operations that may be effected by, and data that may be stored by, a service provider edge device (PE) to effect various aspects of the present invention. Generally, a service provider edge device (PE) will include customer-side port operation(s) 430 and transport network-side port operation(s) 440. The customer-side port operation(s) 430 may be coupled with a LAN 432. The transport network-side port operation(s) 440 may terminate links to other components of the transport networks 410. Basically, forwarding operations 450 are used to forward packets from a customer side-side port operation 430 or transport network-side port operation 440 to an appropriate one of a customer-side port or a transport network-side port, as determined based on information in the layer 2 (MAC) forwarding information tables (also referred to as “Virtual Forwarding Instances” or “VFIs”) 460, transport network forwarding information 415, and/or TLS information 470.
FIG. 16 is high-level block diagram of a machine 1600 which may effect one or more of the operations and/or store the data discussed above. The machine 1600 basically includes a processor(s) 1610, an input/output interface unit(s) 1630, a storage device(s) 1620, and a system bus (es) and/or a network(s) 1640 for facilitating the communication of information among the coupled elements. An input device(s) 1632 and an output device(s) 1634 may be coupled with the input/output interface(s) 1630. Operations of the present invention may be effected by the processor(s) 1610 executing instructions. The instructions may be stored in the storage device(s) 1620 and/or received via the input/output interface(s) 1630. The instructions may be functionally grouped into processing modules.
§ 4.4 EXEMPLARY METHODS AND DATA STRUCTURES
As introduced in § 4.2 above, three high-level applications may be performed by the present invention—provisioning transparent LAN segments, data forwarding, and configuring service provider edge devices to support transparent LAN segment service. Exemplary methods and data structures that may be used to effect these applications are described in §§ 4.4.1, 4.4.2 and 4.4.3, respectively, below.
§ 4.4.1 Provisioning Transparent LAN Segments of Virtual LANs
FIG. 8 is a flow diagram of an exemplary method 484′/485′ that may be used to effect the provisioning operations 484/485. As indicated by 810 and 880, a number of acts can be performed for each service provider edge device (PE). Such acts may be performed locally, at the given PE, although at least some of the provisioning will conform to a TLS-wide plan. Further, as indicated by 820 and 870, a number of acts are performed for each transparent LAN segment (TLS) that the given service provider edge device (PE) is to support. More specifically, as indicated by block 830, for each TLS to be supported by the given PE, a (MAC) layer 2 forwarding table (or more generally, a VFI) is associated with the TLS. An example of a TLS 710—(MAC) layer 2 forwarding table 730 association is illustrated in FIG. 7.
As indicated by block 840, for each TLS to be supported by the given PE, (logical) ports are assigned to the TLS. In one exemplary embodiment, the service provider sequentially numbers (starting with 1) the ports that belong to that TLS, as illustrated by columns 622 of FIG. 6. As a result, within a given TLS each port has a unique number, though different TLSs can have overlapping port numbers. This number is referred to as “port ID”. Recall that for each TLS, the service provider estimates the number of ports that are to belong to the TLS. Recall further that this is just an estimate, and from a practical point of view the service provider should overprovision this number. For each port of a TLS, the port is provisioned with a number of TLS labels used to reach the other ports (or potential future ports) of that TLS.
FIG. 5 illustrates terms used in a naming convention to describe exemplary TLS labels that may be used in the present invention. For each TLS port configured on a PE, the PE chooses a contiguous group of labels, with the number of labels in the group being equal to the estimated number of ports to be associated with that TLS. This set is referred to as a “label-block”. As shown in FIG. 5 and columns 626 and 628 of FIG. 6, the smallest label in a label-block is referred to as the “label-base” and the number of labels in the label-block is referred to as the “label-range”. To allow a service provider to add more (logical) ports to particular TLS at a later time, the PE could be provided with a new label-block with n labels, where n is the number of additional ports. This process might be repeated several times if and when more ports are added. As shown in FIG. 5 and column 624 of FIG. 6, to permit the multiple label-blocks to be distinguished, a block offset is used to identify the position of a given label-block in the set of label-blocks associated with a (logical) port. For a label-block m, this label-block is denoted as “Lm”, its block offset is denoted as “LOm”, its label-base is denoted as “LBm”, and its label-range is denoted as “LRm”.
§ 4.4.2 Data Forwarding
As shown in FIG. 7, the VFI is a layer 2 (MAC) forwarding information table 730 that is associated with a transparent LAN segment 710, a group used for targeting the distribution of advertisements (e.g., a route target BGP extended community) 720 and (logical) ports (not shown). In this exemplary embodiment, the VFI is modeled as a table 730 having three types of entries—remote, local, and wildcard. A “remote” type entry includes (a) layer 2 (e.g., MAC) address, (b) a TLS label, and (c) an egress PE. A “local” type entry includes (a) a layer 2 (e.g., MAC) address, and (b) a local outgoing port. Finally, a “wild card” type entry includes a list of {TLS label, egress PE} tuples. Note that for each local port that belongs to a particular TLS, the VFI 730 associated with the TLS maintains exactly one wild card type entry. Wild card type entries are used until a MAC address-port or MAC address-TLS label-egress PE association is discovered/learned.
Recall that a “tunnel” label is used to forward packets over the transport network 110, from an ingress service provider edge device (PE) to an egress service provider edge device (PE). Recall further that a TLS label is used by the egress PE to select a particular outgoing port. Therefore, the ingress (PE) stacks a TLS label and a tunnel label onto an incoming packet. Briefly stated, the TLS label and the appropriate egress PE is determined based on information stored in a VFI (e.g., a layer 2 (MAC) forwarding information table). The “tunnel” label is determined from information in a forwarding table using the egress PE, the contents of which may be managed using known protocols or techniques. Finally, recall that a tunnel label might not be needed for “local” forwarding through a single given PE.
As shown in FIG. 7, the exemplary table 730 includes a column 734 including MAC addresses. Also note that the entries (rows) of the exemplary table 730 include a type value 732 which is either (a) “remote”, (b) “local”, or (c) “wild card”. As indicated by 915 of FIG. 9, the remaining part of the method 450 a′ is dependent on the type of the entry matching the MAC address. If the entry is found, and the entry type is “local”, then, as indicated by block 920, the ingress PE determines the outgoing port of the matching entry. (See, e.g., column 738 of FIG. 7.) As indicated by block 925, the ingress PE then sends the packet out on the outgoing port identified, as specified in the found entry, before the method 450 a′ is left via RETURN node 960. Since the port is local, that is no egress PE is involved, no “tunnel” label is needed in this case.
Referring back to 915, if an entry with a matching MAC address is found, and the entry type is “remote”, then, as indicated by block 930, the ingress PE determines the TLS label and the egress PE from the found entry (See, e.g., columns 738 and 739 of FIG. 7.). As indicated by block 932, the TLS label is added to the packet. Then, as indicated by block 934, the packet with the TLS label is prepared for transport to the egress PE. If a label switched path exists between the ingress and egress PEs, this act may involve providing the packet with the TLS within a tunnel label. Then, as indicated by block 936, the resulting packet is forwarded through the transport network towards the egress PE, before the method 450 a′ is left via RETURN node 960.
Referring back to 915, if neither a local, nor a remote type entry is found (i.e., if no entry has a matching MAC address), or if the destination MAC address is either broadcast or multicast, the packet is handled by using a wild card type entry associated with the port as follows. The wild card type entry may include a number of {TLS label, egress PE} tuples. More specifically, as indicated by loop 942-950, for each {TLS label, egress PE} tuple from the wildcard entry, a number of acts are performed. That is, for each {TLS label, egress PE} tuple from the wildcard entry, the ingress PE applies (e.g., prepends) the TLS label to (an instance of) the packet as indicated by block 944, prepares the packet for transport to the egress PE as indicted by block 946, and sends the packet toward the specified egress PE as indicted by block 948. Referring, via node A 951, to FIG. 9B, in addition, if there are other ports on the PE associated with the same VFI (i.e., all ports 738 of any and all “local” type entries), (an instance of) the packet is sent on all these ports. In this case, the TLS label needn't be applied. More specifically, as indicated by loop 952-958, for each “local” type entry, an outgoing port is determined as indicated by block 954 and (an instance of) the packet is put on the determined outgoing port as indicated by block 956. The method 450 a′ is then left via RETURN node 960.
As can be appreciated from the foregoing, wild card type entries can be used if the port/PE serving the destination MAC address isn't known. In such a case, the packet may be multicast to all PEs and ports of the TLS known to the ingress PE. Although such multicasting is not efficient, it is an interim measure, only used until the ingress PE “learns” or “discovers” the port and PE which serve the device having the relevant MAC address.
The second part of the path—from the ingress service provider edge device PE to the egress service provider edge device PE—may exploit known forwarding techniques, such as known label switched path forwarding techniques. FIG. 3 illustrates the forwarding of a packet 340 with a TLS label encapsulated in a tunnel label. The tunnel label, initially “5”, is changed to “9” by the label-switching router 330 a, and then changed from “9” to “2” by the label-switching router 330 b.
Forwarding on the Egress PE
FIG. 10 is a flow diagram of an exemplary method 450 b′ that may be used to forward packets received on the egress service provider edge device (PE). As indicated by decision block 1010, the main part of the method 450 b′ is triggered upon receipt of a packet (e.g., from a port coupled with a node of the transport network). At block 1012, the tunnel label may be stripped (if it was not already stripped at the penultimate hop, i.e., the node immediately preceding the egress service provider edge device). A given PE may support single lookup forwarding, double lookup forwarding, or both. FIG. 10 illustrates operations of an exemplary PE supporting both. Decision block 1015 is used to determine whether the egress PE is to use single lookup forwarding, or double lookup forwarding. Single lookup forwarding can use the TLS label and TLS information 470 to determine a port as indicated by block 1035. The TLS label may then be stripped as indicated by block 1040, before the packet is placed on the determined port as indicated by block 1050, before the method 450 b′ is left via RETURN node 1080. As will be described in § 4.3.3 below, with reference to FIG. 15, the TLS label is used for layer 2 (e.g., MAC) address learning. Since such learning uses the TLS label, it should be performed before the TLS label is stripped. If the TLS information has no mapping of the TLS label to a port, the method 450 b′ may try to forward the packet using double lookup forwarding (discussed with reference to blocks 1020, 1025, 1030, 1040, 1050, 1060 and 1070 below).
Referring back to decision block 1015, if double lookup forwarding is to be used, as indicated by block 1020, an appropriate (MAC) layer 2 forwarding information table (or VFI) is determined based on the TLS label of the received packet. Then, as indicated by decision block 1025 and block 1030, if the VFI has a local type entry with a MAC address matching the packet's destination MAC address, using the determined VFI table, an outgoing port is determined based on the destination MAC address of the packet. (Recall, e.g., columns 734 and 738 of a “local” entry.) As indicated by block 1040, the TLS label may be removed at this point. As mentioned above, since layer 2 (MAC) address learning uses the TLS label, it should be performed before the TLS label is stripped. Finally, as indicated by block 1050, the packet is placed on the determined outgoing port, before the method 450 b′ is left via RETURN node 1080. Referring back to decision block 1025, if the VFI does not have a local type entry with a MAC address matching the packet's destination MAC address, then the TLS label may be removed as indicated by block 1060 and (an instance of) the packet is placed on all local ports that belong to the TLS as indicated by block 1070, before the method 450 b′ is left via RETURN node 1080.
§ 4.4.3 Configuration
In the forwarding operations described in § 4.4.2 above, it was assumed that the VFI (e.g., the layer 2 (MAC) forwarding information table) was populated with appropriate entries. Although these entries may be manually entered and maintained, doing so would be difficult, slow, labor intensive, and subject to human-error. This section describes exemplary ways of maintaining the VFI. Entries of the VFI may be generated and/or maintained based on advertisements and based on (e.g., “learned” from) information taken from packets entering or exiting the transport network. Exemplary methods and data structures for performing such advertisement and VFI maintenance are described here.
FIG. 13 is a flow diagram of an exemplary method 482′ that may be used to effect an ad generation operation 482. As indicated by block 1310, information related to a (logical) port (e.g., port ID, label-blocks, etc.) is obtained. Recall from FIG. 4 that this may have been provisioned and stored in a label information base 470. As indicated by block 1320, a contiguous set of labels is defined, starting with the label base and proceeding to {label base+label range−1}. Then, as indicated by block 1330, an ad is assembled based on this information. FIG. 14 illustrates an exemplary data structure 1400 that may be used to advertise provisioned TLS-port information. As shown, this exemplary data structure 1400 may include an identifier of the PE generating the ad (e.g., an Internet protocol layer 3 address) 1410, a TLS identifier 1420, a (logical) port ID 1430, label-block offset (if any) 1440, a label base 1450, a label range 1460, and any further information 1470. Referring back to FIG. 13, as indicated by block 1340, the ad is then sent (e.g., multicast) to other PEs. If a full mesh topology is desired, the ad should be send to all other PEs. The method 482′ is then left via RETURN node 1350. Such ad distribution may be accomplished by using BGP, and is related to the method described in U.S. patent application Ser. No. 09/865,050, entitled “TRANSPORT NETWORKS SUPPORTING VIRTUAL PRIVATE NETWORKS, AND CONFIGURING SUCH NETWORKS”, filed on May 24, 2001 by Kireeti Kompella. That application is incorporated herein by reference.
Referring back to 1510, when a PE receives a local (ingress) packet, it may update or add a “local” type of the VFI associated with the local port entry. More specifically, as indicated by block 1540, the “local” type VFI entries on a PE may be updated using the packets that the PE receives on the (local) ports associated with the TLS that the VFI is associated with. For example, when a PE receives a packet on one of its local ports, the PE creates a “local” type entry in the VFI that the port is associated with. In the “local” type entry, the MAC address 734 is set to the MAC source address in the packet, and the outgoing port 738 is set to the port on which the packet was received. The method 486′ is then left via RETURN node 1570.
Referring back to 1510, when a PE receives a packet from some other PE (also referred to as a “remote packet” or an “egress packet”), it may update or add a “remote” type VFI entry. More specifically, as indicated by block 1550, the PE may use the TLS label of the packet to determine the ingress PE and the port on the ingress PE where the packet came from. This may be done as follows. First the PE searches through the label-blocks that it advertises (or had advertised) to other PEs for the block m that satisfies LBm<=TLS_label<LBm+LRm. (Recall label information base 470 of FIG. 4.) Once the label-block that satisfies the condition is found, the port ID of the ingress port is defined as LOm+TLS_label−LBm. The TLS label also identifies a particular VFI, and therefore a particular TLS that has this port. Using this port ID and the BGP routing information that the PE received from other PEs, the PE can determine the address of the ingress PE. (Recall fields 1410 and 1430 of the ad 1400 of FIG. 14.) Once the PE determines the ingress PE and the port on the ingress PE where the packet came from, as indicated by block 1560, the PE creates a “remote” type entry with the MAC address 734 set to the MAC source address in the packet, the egress PE 739 set to the address (or some other identifier) of the ingress PE, and the TLS label 736 set to a value determined as follows. Denoting the port ID of the port on the ingress PE as k, the TLS label in the “remote” type entry is set to LBm+k−LOm, where the label-block m satisfies LOm<=k<LOm+LRm. (Note that the above could be precomputed, so that when the PE receives a packet with a TLS label, a single table lookup on this label would produce both the address of the ingress PE (the PE where the packet came from), and the TLS label that should go into the VFI table “remote” type entry.) The method 486′ may then be left via RETURN node 1570.
As indicated by the foregoing, labels provide the egress PE with the information about the ingress PE and the port on the ingress PE where the packet came from. This is used by the egress PE for what is known as “MAC address learning”, and specifically for discovering a particular {PE, port} pair that should be used to reach a particular MAC address.
§ 4.4.4 Supporting VLAN Flooding Scope
§ 4.5 EXEMPLARY OPERATIONS
Examples illustrating exemplary provisioning, configuration and forwarding operations in an exemplary embodiment of the present invention are now provided.
§ 4.5.1 Provisioning and Configuration Example
Similarly, when PE0 receives the advertisement 1720, it sets a {label,egress PE} tuple(s) of the wild card entry (Recall, e.g., 736 and 739 of FIG. 7.) of the (MAC) layer 2 forwarding information table associated with TLS=i. In this case, the PE is set to PE2. The TLS label is set to 4000+0−0=4000. This entry is for any packets that PE0 receives on the port with Port ID=0. Since Port ID=1 also belongs to TLS=i, PE0 also needs to compute a wildcard label for any packets PE0 receives on the port with Port ID=1 (unless the egress PE is to use double lookup forwarding (exclusively)). For such packets the label will be 4000+1−0=4001. Thus, each ingress port has its own forwarding table (at least conceptually). That is (at least conceptually), on PE 0, there is not one, but two forwarding tables for TLSi—one used for handling packets received on PortID=0, and another used to handle packets received on PortID=1. This allows the egress PE to use single lookup (TLS label->port) forwarding, and avoids the need to use double lookup (TLS label->TLS table, and MAC address->port) forwarding. With the double lookup forwarding alternative, only one label per TLS need be provided on a PE, even if the PE has more than one port associated with that TLS.
In each case, once the label-block is found, the port ID of the ingress port is defined as LOz+TLS_label−LBz. Each case gives the same result. That is, the Port ID=0+1004−1000=4, or 0+2004−2000=4. The label block(s) satisfying the condition also identifies a particular VFI, and therefore a particular TLS that has this port. Using this Port ID and the BGP routing information that PE0 received from PE2, PE0 can determine the address of the ingress PE (PE2). (Recall message 1720 of FIG. 17 and fields 1410 and 1430 of the ad 1400 of FIG. 14.) Once PE0 determines that the ingress PE is PE2, and the port on PE2 where the packet came from as Port ID=4, the PE creates a “remote” type entry with the MAC address 734 set to the MAC source address of the packet, the egress PE 739 set to the address of the ingress PE2, and the TLS label 736 set to a value determined as follows. (Recall 1560 of FIG. 15.) Denoting the Port ID of the port on the ingress PE as k, recall that the TLS label in the “remote” type entry is set to LBm+k−LOm, where the label-block m satisfies LOm<=k<LOm+LRm. (Note that the above could be precomputed, so that when the PE receives a packet with a TLS label, a single table lookup on this label would produce both the address of the ingress PE (the PE where the packet came from), and the TLS label that should go into the VFI “remote” type entry.) In this example, the TLS labels are 4000+0−0=4000 (used for data arriving on port assigned port ID=0), and 4000+1−0=4001 (used for data arriving on port assigned port ID=1). Thus, if a particular MAC address, MAC1, is reachable via PortID=0, and another MAC address, MAC2 is reachable via PortID=1, then PE2 wants to send data to MAC1 PE2 needs to put different inner label then when sending data to MAC2. In this way, egress PE0 need only perform single lookup forwarding (just on the label), and avoids the need to perform double lookup forwarding (first on the label to find the appropriate TLS, and then on the MAC address to find out the specific outgoing port).
The foregoing example illustrated how the present invention supports provisioning and the population of the VFI (e.g., a layer 2 (MAC) forwarding table) based on advertisements and layer 2 (MAC) address learning. Now, in § 4.5.2 below, examples illustrating data forwarding using such information is described.
§ 4.5.2 Data Forwarding Example
In a second example, referring to FIG. 12A, assume that a packet 1210 having a destination MAC address 1212 is received at a port assigned to port ID=0 on PE 0 and further assume that the (MAC) layer 2 forwarding table (associated with the Port ID that received the packet) has a remote type entry having a MAC address (Recall 734 of FIG. 7.) that matches the destination MAC address of the packet. (Recall, e.g., block 930 of FIG. 9.) In this case, recall from FIG. 18 that the TLS label 736 had been set to 4000 and the egress PE 739 had been set to PE2. Recall further from FIG. 17 that the tunnel label to get to PE 2 is “9999”. As shown in FIG. 12A, the packet 1210 is provided with the TLS label (set to 4000) 1224 and transport encapsulation (e.g., a tunnel label set to “9999”) 1222. (Recall, e.g., blocks 932 and 934 of FIG. 9.) The resulting packet 1220 is forwarded, using, for example, known forwarding techniques such as label-switched routing, to PE 2. (Recall, e.g. block 936 of FIG. 9.)
Referring to FIG. 12B, which illustrates double lookup forwarding at the egress PE, the packet 1220′ arriving at PE 2 is similar to the packet 1220 that left PE 0, but the tunnel label 1222′ will have changed. At PE 2, an appropriate (MAC) layer 2 forwarding information table (or VFI) is determined based on the TLS label of the received packet. (Recall, e.g., block 1020 of FIG. 10.) In this example, PE 2 knows that label 4000 is associated with TLS=i. (Recall, upper right hand portion of FIG. 17 which includes a label information base. Recall also association of 710 and 730 of FIG. 7.) Then, using the determined VFI, an outgoing port is determined based on the destination MAC address 1212 of the packet 1210. (Recall, e.g., columns 734 and 738 of a “local” type entry, whose values were entered as a part of local MAC learning.) At this point, the TLS label and the tunnel label (if any) may be removed (if they haven't already been removed earlier). (Recall, e.g., 1040 of FIG. 10.) Finally, the packet is placed on the determined outgoing port. (Recall, e.g., 1050 of FIG. 10.) In this example, assume that the destination MAC address 1212 of the packet 1210, is that same as the source MAC address of the packet 1810 of FIG. 18. In this case, the outgoing port would be port ID=4.
As can be appreciated from the foregoing detailed description, the present invention permits a service provider to provide a transparent LAN segment service over a transport network. This service is easy to provision. Further, it is easy to add more ports. Finally customers can use a mature, inexpensive technology, such as Ethernet LANs, without the geographic limitations traditionally found in such technologies. Finally, the service provider's transport network is protected against malicious or incompetent customers.
US8279871 * Oct 29, 2008 Oct 2, 2012 Marvell Israel (M.I.S.L.) Ltd. Methods and apparatus for processing multi-headed packets
US8665754 * Dec 16, 2011 Mar 4, 2014 Fujitsu Limited Path generating method, relay device, and computer product
US8995446 * Dec 21, 2009 Mar 31, 2015 Cisco Technology, Inc. Efficient generation of VPN-based BGP updates
US9559954 * Jan 15, 2014 Jan 31, 2017 Cisco Technology, Inc. Indexed segment ID
US20120207164 * Dec 16, 2011 Aug 16, 2012 Fujitsu Limited Path generating method, relay device, and computer product
US20140254596 * Jan 15, 2014 Sep 11, 2014 Cisco Technology, Inc. Indexed segment id
CN105075194A * Feb 25, 2014 Nov 18, 2015 思科技术公司 Indexed segment ID
Cooperative Classification Y10S707/99936, H04L12/4641, H04L12/4645, H04L45/50
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:REKHTER, YAKOV;REEL/FRAME:036679/0938