Supporting multiple multicast trees in trill networks

RELATED APPLICATION

This application claims priority to U.S. Provisional Application No. 61/352,726, entitled “TRILL Multicast Trees,” by inventors Shunjia Yu, Raj Venkatesan, Anoop Ghanwani, Phanidhar Koganti, Mythilikanth Raman, Rajiv Krishnamurthy, and Dilip Chatwani, filed 8 Jun. 2010, the contents of which are incorporated herein by reference.

This application also claims priority to U.S. Provisional Application No. 61/427,057, entitled “Supporting Multiple Multicast Trees in TRILL Networks,” by inventors Shunjia Yu, Nagarajan Venkatesan, Anoop Ghanwani, Phanidhar Koganti, Mythilikanth Raman, Rajiv Krishnamurthy, and Dilip Chatwani, filed 23 Dec. 2010, the contents of which are incorporated herein by reference.

BACKGROUND

Technical Field

This disclosure relates to data communication and networking More specifically, this disclosure relates to systems and techniques for supporting multiple multicast trees in TRILL (Transparent Interconnection of Lots of Links) networks.

Related Art

The insatiable demand for bandwidth and the ever increasing size and complexity of computer networks has created a need for increasing the bandwidth and improving manageability of computer networks.

Computer networks often use multicasting to efficiently distribute high bandwidth content (e.g., streaming video) to multiple end-hosts in the network. In multicasting, copies of packets are forwarded over a multicast tree in the network. In some approaches, the network supports a single multicast tree for a given source and multicast address. For purposes of load balancing and failure recovery, it is generally desirable to support multiple multicast trees for a given source and multicast address. Unfortunately, supporting multiple multicast trees in the network can significantly increase the amount of resources required at each switch.

SUMMARY

Some embodiments of the present invention provide systems and techniques for efficiently supporting multiple multicast trees for a given source and multicast address. Specifically, some embodiments provide a system (e.g., a switch) that can determine an internal multicast group identifier based on a source address, a multicast address, and a multicast tree identifier field associated with a multicast packet. The multicast packet can be an Ethernet or TRILL multicast packet. The system can then forward the multicast packet based on the internal multicast group identifier. In this disclosure, unless otherwise stated, the phrase “based on” means “based solely or partly on.”

In some embodiments, the system can determine a first set of bits based on the source address and the multicast address of the multicast packet, and a second set of bits based on the multicast tree identifier field of the multicast packet. The system can then combine (e.g., concatenate) the first set of bits and the second set of bits to obtain the internal multicast group identifier.

The system can forward the multicast packet by determining a set of egress ports based on the internal multicast group identifier, and sending at least one copy of the multicast packet through each port in the set of egress ports. Note that multiple copies of the multicast packet may be sent over the same egress port if the multicast packet is to be forwarded to multiple Virtual Private Networks (VPNs) coupled to the egress port.

If the multicast packet is an Ethernet packet, the system can add a TRILL header to each copy of the multicast packet, and forward the TRILL-encapsulated packets based on the internal multicast group identifier.

In some embodiments, the scope of an internal multicast group identifier does not extend beyond a switch. As a packet traverses through different switches in the network, each switch can determine a different internal multicast group identifier.

Some embodiments of the present invention provide a network which includes at least one source switch, one or more intermediate switches, and at least one destination switch. A source switch may determine an internal multicast group identifier for a multicast packet based on one or more fields in the packet's header. Next, the source switch may encapsulate a copy of the multicast packet in a TRILL multicast packet, and forward the TRILL multicast packet based on the internal multicast group identifier.

The TRILL multicast packet may pass through one or more intermediate switches before reaching the destination switch. Each intermediate switch may determine an internal multicast group identifier, and forward the TRILL multicast packet based on the internal multicast group identifier. When the TRILL multicast packet reaches the destination switch, the destination switch may decapsulate the TRILL multicast packet to obtain the multicast packet, and forward the multicast packet based on an internal multicast group identifier. The internal multicast group identifier determined by a switch may or may not be the same as the internal multicast group identifiers that were determined by other switches that processed the multicast packet or the TRILL multicast packet.

BRIEF DESCRIPTION OF THE FIGURES

<figref idref="DRAWINGS">FIG. 1</figref> illustrates a TRILL network in accordance with some embodiments of the present invention.

<figref idref="DRAWINGS">FIG. 2</figref> illustrates a portion of an Ethernet packet which includes a TRILL header in accordance with some embodiments of the present invention.

<figref idref="DRAWINGS">FIG. 3A</figref> illustrates how an internal multicast group identifier can be determined in accordance with some embodiments of the present invention.

<figref idref="DRAWINGS">FIGS. 3B and 3C</figref> illustrate different multicast trees for the same source and multicast address in accordance with some embodiments of the present invention.

<figref idref="DRAWINGS">FIG. 3D</figref> illustrates how internal multicast group identifiers can be determined in accordance with some embodiments of the present invention.

<figref idref="DRAWINGS">FIG. 3E</figref> illustrates how an internal multicast group identifier can be used to determine a set of egress ports in accordance with some embodiments of the present invention.

<figref idref="DRAWINGS">FIG. 4</figref> illustrates how an RBridge can perform network layer multicasting in a TRILL network in accordance with some embodiments of the present invention.

<figref idref="DRAWINGS">FIG. 5</figref> illustrates a switch in accordance with some embodiments of the present invention.

<figref idref="DRAWINGS">FIG. 6A</figref> presents a flowchart that illustrates a process for forwarding packets based on an internal multicast group identifier in accordance with some embodiments of the present invention.

<figref idref="DRAWINGS">FIG. 6B</figref> presents a flowchart that illustrates a process for performing network layer multicasting in a TRILL network in accordance with some embodiments of the present invention.

<figref idref="DRAWINGS">FIG. 7</figref> illustrates a system in accordance with some embodiments of the present invention.

DETAILED DESCRIPTION

The following description is presented to enable any person skilled in the art to make and use the invention, and is provided in the context of a particular application and its requirements. Various modifications to the disclosed embodiments will be readily apparent to those skilled in the art, and the general principles defined herein may be applied to other embodiments and applications without departing from the spirit and scope of the present invention. Thus, the present invention is not limited to the embodiments shown, but is to be accorded the widest scope consistent with the principles and features disclosed herein.

TRILL (Transparent Interconnection of Lots of Links)

TRILL combines the advantages of bridging and routing. Bridges (e.g., devices that perform layer-2 forwarding) can transparently connect multiple links to create a single local area network. However, the topology on which traffic is forwarded in a bridged network must be a tree to prevent loops. Unfortunately, forwarding the traffic over a tree causes traffic concentration on the links that correspond to the tree edges, leaving other links completely unutilized. Unlike bridges, Internet Protocol (IP) routers (e.g., devices that perform IP forwarding) do not need to create a spanning tree for forwarding traffic. However, routers that forward IP traffic require more configuration than bridges, and moving nodes in an IP network requires changing the IP address of the nodes. Each link in an IP network is associated with an address prefix, and all nodes on that link must have that IP prefix. If a node moves to another link that has a different IP prefix, the node must change its IP address. Unless otherwise stated, the term “IP” refers to both “IPv4” and “IPv6” in this disclosure.

A TRILL network includes “routing bridges” (referred to as RBridges) which route packets, but like bridges, learn layer-2 address locations through receipt of packets. Since packets are routed, packet forwarding is not limited to a spanning tree. Also, since a hop count is included in a TRILL packet, packets do not circulate forever in the network in the presence of loops. Further, since the layer-2 address locations are learned, a TRILL network allows IP nodes to move from one link to another in the network without any restrictions.

<figref idref="DRAWINGS">FIG. 1</figref> illustrates a TRILL network in accordance with some embodiments of the present invention. TRILL network <b>100</b> can be a service provider's network which includes core RBridges <b>102</b> and <b>104</b> and edge RBridges <b>106</b>, <b>108</b>, and <b>110</b>. RBridges <b>102</b>, <b>106</b>, <b>108</b>, and <b>110</b> are coupled to customer devices, whereas RBridge <b>104</b> is not. Specifically, port P<b>3</b> on RBridge <b>102</b> can be coupled to a device in customer C<b>3</b>'s network at site S<b>1</b>; ports labeled P<b>1</b> on RBridges <b>106</b>, <b>108</b>, and <b>110</b> can be coupled to devices in customer C<b>1</b>'s networks at sites S<b>2</b>, S<b>3</b>, and S<b>4</b>, respectively; and port P<b>3</b> on RBridge <b>110</b> can be coupled to a device in customer C<b>3</b>'s network at site S<b>5</b>. Note that the port numbers in <figref idref="DRAWINGS">FIG. 1</figref> match the customer numbers, i.e., ports labeled P<b>1</b> are associated with customer C<b>1</b>, ports labeled P<b>3</b> are associated with customer C<b>3</b>, etc. This has been done for ease of discourse. In general, any port on any RBridge can potentially be assigned to one or more virtual networks that are associated with one or more customers.

A virtual local area network (VLAN) in a customer's network may span multiple customer sites. For example, VLANs <b>112</b> and <b>114</b> in customer C<b>3</b>'s network include nodes in sites S<b>1</b> and S<b>5</b>. Similarly, VLANs <b>116</b> and <b>118</b> in customer C<b>1</b>'s network include nodes in sites S<b>2</b> and S<b>3</b>, and VLAN <b>120</b> in customer C<b>1</b>'s network includes nodes in sites S<b>3</b> and S<b>4</b>.

Nodes that belong to the same VLAN, but which are located at different sites, can communicate with each other transparently through TRILL network <b>100</b>. Specifically, the ingress RBridge can encapsulate a packet (e.g., an Ethernet packet with or without one or more VLAN tags) received from a customer and route the packet within TRILL network <b>100</b> using a TRILL header. The egress RBridge can then strip the TRILL header and send the original customer packet on the appropriate port. For example, packet <b>122</b> can originate in customer C<b>3</b>'s network at site S<b>1</b>, and be received on port P<b>3</b> of RBridge <b>102</b> with a VLAN tag associated with VLAN <b>112</b>. Next, RBridge <b>102</b>, which is the ingress RBridge for this packet, can encapsulate packet <b>122</b> by adding a TRILL header to obtain packet <b>124</b> (the TRILL header is the shaded portion in packet <b>124</b>). Next, the TRILL header of packet <b>124</b> can be used to route packet <b>124</b> through TRILL network <b>100</b> until packet <b>124</b> reaches RBridge <b>110</b>, which is the egress RBridge for the packet. RBridge <b>110</b> can then strip away the TRILL header on packet <b>124</b> to obtain the original packet <b>122</b>, and send packet <b>122</b> on port P<b>3</b> so that the packet can be delivered to the intended destination in VLAN <b>112</b> in customer C<b>3</b>'s network at site S<b>5</b>. In <figref idref="DRAWINGS">FIG. 1</figref>, the packet that is received at the ingress RBridge and the packet that is sent from the egress RBridge are shown to be the same. However, these packets can be different. For example, if VLAN translation is being performed, then the packet that is received at the ingress RBridge and the packet that is sent from the egress RBridge can have different VLAN tags.

Further details on TRILL and RBridges can be found in Radia Perlman, <i>Rbridges: Transparent Routing</i>, Proceedings of IEEE INFOCOM, 2004, which is incorporated herein by reference. Details on TRILL and RBridges can also be found in Joe Touch and Radia Perlman, <i>TRILL: Problem and Applicability</i>, IETF RFC 5556, May 2009, which is incorporated herein by reference. Details of the TRILL packet format and RBridge forwarding can be found in IETF draft “RBridges: Base Protocol Specification,” available at http://tools.ietf.org/html/draft-ietf-trill-rbridge-protocol-16, which is incorporated herein by reference.

Although some examples in this disclosure are presented in the context of a TRILL network that includes RBridges, the present invention is not limited to TRILL networks or RBridges. The terms “frame” or “packet” generally refer to a group of bits. The use of the term “frame” is not intended to limit the present invention to layer-2 networks. Similarly, the use of the term “packet” is not intended to limit the present invention to layer-3 networks. Unless otherwise stated, the terms “frame” or “packet” may be substituted with other terms that refer to a group of bits, such as “cell” or “datagram.”

Network Virtualization

Network virtualization enables a service provider to provision virtual networks (VNs) over a common network infrastructure. To a user on a VN it appears as if the traffic is being carried over a separate network that has been specifically built for the user. However, in reality, the traffic from multiple VNs may be carried over a common network infrastructure.

Network virtualization has many uses. For example, network virtualization can be used to create multiple, logically distinct networks on the same physical network to comply with government regulations. Other uses of network virtualization include, but are not limited to, partitioning network resources between different organizations in a company, reducing network costs and simplifying network management during a merger between two companies by provisioning a virtual private network for each company.

One approach for supporting network virtualization is to duplicate resources (e.g., routers, switches, etc.) in the network so that the resources can be provisioned on a per-customer basis. However, this approach is impractical because it is costly and it is not scalable.

Some embodiments of the present invention implement network virtualization and/or partitioning in the TRILL network by embedding a VPN identifier in a TRILL option field in the TRILL header. Specifically, the ingress RBridge can determine a VPN identifier for each packet it receives from a customer, and embed the VPN identifier in a TRILL option field in the TRILL header. Next, the VPN identifier can be used to support network virtualization and/or partitioning in the TRILL network. Specifically, once the VPN identifier is embedded into the TRILL header, RBridges in the TRILL network can use the VPN identifier to determine how to handle the packet.

In some embodiments, the system can use a service provider VLAN identifier to implement network virtualization and/or partitioning. Specifically, ingress RBridges can add appropriate S-tags to packets received from customers (note that the S-tag based approach may not work for incoming packets that already have an S-tag). Next, the S-tag can be used to implement virtualization and/or partitioning in the network.

Packet Format

<figref idref="DRAWINGS">FIG. 2</figref> illustrates a portion of an Ethernet packet which includes a TRILL header in accordance with some embodiments of the present invention. The packet shown in <figref idref="DRAWINGS">FIG. 2</figref> is for illustration purposes only, and is not intended to limit the present invention.

Packet <b>200</b> can include one or more of the following fields: outer MAC (medium access control) addresses <b>202</b>, outer VLAN tag <b>204</b>, TRILL header field <b>206</b>, TRILL option field <b>208</b>, inner MAC addresses <b>210</b>, and inner VLAN tags <b>212</b>. Typically, the packet is transmitted from top to bottom, i.e., the bits associated with outer MAC addresses <b>202</b> will appear on the transmission medium before the bits associated with outer VLAN tag <b>204</b> appear on the transmission medium, and so forth. The contents of these fields and their uses are discussed below.

Outer MAC addresses <b>202</b> can include outer destination MAC address <b>214</b> and outer source MAC address <b>216</b>. These MAC addresses and outer VLAN tag <b>204</b> typically change at each TRILL hop as the packet traverses the service provider's network. Specifically, at each hop, outer source MAC address <b>216</b> is associated with the MAC address of the source node (e.g., RBridge) for that hop, outer destination MAC address <b>214</b> is associated with the MAC address of the destination node (e.g., RBridge) for that hop, and outer VLAN tag <b>204</b> is associated with the VLAN that includes the source node and the destination node for that hop.

Outer VLAN tag <b>204</b> can include Ethernet type field <b>218</b> and outer VLAN identifier <b>220</b>. The value of Ethernet type field <b>218</b> can indicate that the next field is a VLAN identifier. VLAN identifier <b>220</b> can be used in the service provider's network to create multiple broadcast domains.

TRILL header field <b>206</b> can include Ethernet type field <b>222</b> and TRILL header <b>224</b>. The value of Ethernet type field <b>222</b> can indicate that the next field is a TRILL header. TRILL header <b>224</b> can include information for routing the packet through a TRILL network that is embedded in the service provider's network. Specifically, as shown in <figref idref="DRAWINGS">FIG. 2</figref>, TRILL header <b>224</b> can include version field <b>246</b> which indicates the TRILL version, reserved field <b>248</b> which may be reserved for future use, multicast field <b>250</b> which indicates whether this packet is a multicast packet, TRILL option length <b>252</b> which indicates the length (in terms of 32-bit words) of any TRILL option field that follows the TRILL header, and hop count <b>254</b> which may be decremented at each RBridge as the packet traverses the service provider's network.

TRILL header <b>224</b> also includes egress RBridge nickname <b>256</b> and ingress RBridge nickname <b>258</b>. Ingress RBridge nickname <b>258</b> corresponds to the ingress RBridge which receives the packet from the customer's network, and, for unicast packets, egress RBridge nickname <b>256</b> corresponds to the egress RBridge which sends the packet to the customer's network. For multicast packets, egress RBridge nickname <b>256</b> corresponds to the egress RBridge at the root of the multicast tree on which the packet is to be forwarded. For example, in <figref idref="DRAWINGS">FIG. 1</figref>, when packet <b>122</b> is received at ingress RBridge <b>102</b>, ingress RBridge <b>102</b> can use the header information in packet <b>122</b> to determine that packet <b>122</b> needs to be routed to egress RBridge <b>110</b>. Next, ingress RBridge <b>102</b> can add TRILL header field <b>206</b> to packet <b>122</b> to obtain packet <b>124</b>. Specifically, RBridge <b>102</b> can set ingress RBridge nickname <b>258</b> in packet <b>124</b>'s TRILL header to RBridge <b>102</b>'s nickname, and set egress RBridge nickname <b>256</b> in packet <b>124</b>'s TRILL header to RBridge <b>110</b>'s nickname. RBridge <b>102</b> can then forward packet <b>124</b> based solely or partly on packet <b>124</b>'s TRILL header.

TRILL option field <b>208</b> can include bit-encoded options and one or more options encoded in a TLV (type-length-value) format. Specifically, TRILL option field <b>208</b> can include bit-encoded options <b>260</b> which are one-bit option flags, and TLV-encoded option <b>226</b>. For example, a 20-bit VPN identifier can be encoded as a TLV-encoded option. Specifically, the value of type field <b>262</b> can indicate that this option specifies a VPN identifier. Length field <b>264</b> can indicate the length of the data portion of the TLV-encoded option in octets. In the packet shown in <figref idref="DRAWINGS">FIG. 2</figref>, TLV-encoded option <b>226</b> is used for specifying a 20-bit VPN identifier, and length field <b>264</b> is set to the value 0x6. The data portion of TLV-encoded option <b>226</b> begins immediately after length field <b>264</b>. Specifically, in the packet shown in <figref idref="DRAWINGS">FIG. 2</figref>, the total length (in octets) of fields <b>266</b>, <b>268</b>, and <b>228</b> is equal to 0x6 as specified by length field <b>264</b>. Further, as shown in <figref idref="DRAWINGS">FIG. 2</figref>, the last 20 bits of the data portion in TLV-encoded option <b>226</b> can be used for specifying VPN identifier <b>228</b>.

Note that a 20-bit VPN identifier can be specified using a smaller data portion, e.g., only 0x3 octets instead of 0x6 octets. However, some embodiments use the following non-obvious insight: it may be desirable to align the 20-bit VPN identifier with the word boundary to simplify chip design and/or to improve performance. Thus, in some embodiments, 0x6 octets are used instead of 0x3 octets so that the 20-bit VPN identifier is aligned with a 32-bit word boundary. For example, as shown in <figref idref="DRAWINGS">FIG. 2</figref>, VPN identifier <b>228</b> is aligned with the 32-bit word boundary.

Inner MAC addresses <b>210</b> can include inner source MAC address <b>232</b> and inner destination MAC address <b>230</b>. Inner MAC addresses <b>210</b> can be the MAC addresses that were present in the header of the packet that was received from the customer's network. For example, in <figref idref="DRAWINGS">FIG. 1</figref>, suppose a source node in VLAN <b>112</b> in customer C<b>3</b>'s network at site S<b>1</b> sends a packet to a destination node in VLAN <b>112</b> in customer C<b>3</b>'s network at site S<b>5</b>. In this scenario, inner source MAC address <b>232</b> can correspond to the source node at site S<b>1</b>, and inner destination MAC address <b>230</b> can correspond to the destination node at site S<b>5</b>.

Inner VLAN tags <b>212</b> can include one or more VLAN tags that are used within the customer's network. For example, inner VLAN tags <b>212</b> can include an S-tag which includes Ethernet type field <b>234</b> and S-VLAN-identifier <b>236</b>, a C-tag which includes Ethernet type field <b>238</b> and C-VLAN-identifier <b>240</b>, and a congestion-notification-tag (CN-TAG) which includes Ethernet type field <b>242</b> and flow-identifier <b>244</b>. Each VLAN tag can also include a three-bit Priority Code Point (PCP) field, e.g., PCP <b>270</b>, and a one-bit Canonical Form Indicator (CFI) field, e.g., CFI <b>272</b>. The values in Ethernet type fields <b>234</b>, <b>238</b>, and <b>242</b> can indicate that the tag includes a VLAN identifier for an S-tag, a VLAN identifier for the C-tag, and a flow-identifier, respectively. The S-tag and the C-tag can be used by the customer to create a stacked-VLAN architecture, e.g., as defined in the Provider Bridging standard. The S-tag may also be used by the service provider to implement network virtualization and/or partitioning. The congestion-notification-tag may be used by the customer to manage network congestion.

Note that a packet may or may not include all of the fields shown in <figref idref="DRAWINGS">FIG. 2</figref>. For example, in some embodiments, a packet may not include inner VLAN tags <b>212</b> and/or outer VLAN tag <b>204</b>. Further, certain combinations of fields may not be allowed in some embodiments. For example, in some embodiments, a packet may include either an S-tag or a TRILL option field, but not both. Additionally, the values of some fields may be related to each other. For example, in some embodiments, S-VLAN-identifier <b>236</b> may be copied into the 12 least significant bits of VPNID <b>228</b>.

VLAN tagging is specified in IEEE (Institute of Electrical and Electronics Engineers) standard IEEE 802.1Q. The original specification of this standard describes how a single VLAN tag can be added to an Ethernet packet to create multiple broadcast domains within the same local area network (LAN). The term “Q-in-Q tagging” (also referred to as “QinQ tagging”) refers to an amendment of this standard which allows an S-VLAN tag (a service VLAN tag is sometimes referred to as a provider tag) to be stacked in a single Ethernet packet. Q-in-Q tagging enables a service provider to carry VLAN traffic from multiple customers on a shared Q-in-Q network infrastructure without restricting the VLAN address space available to each customer. Further details on Q-in-Q tagging can be found in the specification for standard IEEE 802.1ad. In some embodiments, the system can add a TRILL header to a Provider Bridging (Q-in-Q) packet. In these embodiments, the packet received from the customer network may include an S-tag. The service provider's network may then add a TRILL header to the packet. In some embodiments, the system may ensure that the priority bits in the outermost VLAN tag are the same as the priority bits in the S-tag.

Supporting Multiple Multicast Trees in TRILL Networks

When a multicast packet is received on an input port, the multicast packet header is processed by the switch to determine the set of output ports on which the multicast packet is to be forwarded. Oftentimes, the forwarding mechanism (e.g., an application-specific integrated circuit designed for performing forwarding look-ups) is the bottleneck in the data path. Consequently, increasing the processing speed and decreasing the size and complexity of the forwarding mechanism is usually very important.

One approach for supporting multiple multicast trees is to have multiple forwarding entries (e.g., one entry per multicast tree) in the forwarding table for a given source address and multicast group address. Unfortunately, this approach can substantially increase the size of the forwarding table or severely limit the number of multicast groups that can be supported by the forwarding table.

Some embodiments determine an internal multicast group identifier based on one or more fields in the multicast packet's header. The multicast group identifier is then used to determine a set of egress ports through which the multicast packet is to be forwarded.

<figref idref="DRAWINGS">FIG. 3A</figref> illustrates how an internal multicast group identifier can be determined in accordance with some embodiments of the present invention.

Internal multicast group identifier <b>312</b> is composed of two sets of bits. The first set of bits <b>308</b> can be determined by looking up forwarding table <b>304</b> using the source address and multicast address <b>302</b> of a multicast packet. In some embodiments, forwarding table <b>304</b> is implemented using a content-addressable memory. The second set of bits <b>310</b> can be determined based on a multicast tree identifier <b>306</b> in the multicast packet. If the multicast packet does not have a multicast tree identifier, the switch can select the second set of bits <b>310</b> on its own, e.g., by using a hash-based technique.

Note that the forwarding table does not store an entry for each multicast tree supported by the switch. Instead, the forwarding table stores a single entry for a given source address and multicast address. The second set of bits is then used to select a particular tree from the multiple multicast trees that are associated with the given source address and multicast address. Since the forwarding table is not required to store an entry for each multicast tree, some embodiments of the present invention are capable of supporting a substantially greater number of multicast trees than other approaches that require the forwarding table to store an entry for each multicast tree.

<figref idref="DRAWINGS">FIGS. 3B and 3C</figref> illustrate different multicast trees for the same source and multicast address in accordance with some embodiments of the present invention.

RBridges <b>322</b>-<b>336</b> can be in a TRILL network. A multicast group can include RBridges <b>322</b>, <b>326</b>, <b>328</b>, <b>330</b>, and <b>336</b> (the RBridges in the multicast group are shown using a dotted circle). <figref idref="DRAWINGS">FIGS. 3B and 3C</figref> illustrate two multicast trees using dotted lines. Note that both multicast trees are rooted at RBridge <b>330</b>.

<figref idref="DRAWINGS">FIG. 3D</figref> illustrates how an internal multicast group identifier can be determined in accordance with some embodiments of the present invention.

When a multicast packet is received at RBridge <b>326</b>, it may use source and multicast address <b>352</b> of the multicast packet to look up forwarding table <b>354</b> to obtain a first set of bits <b>358</b>. Source and multicast address <b>352</b> can be Ethernet or IP addresses.

Next, RBridge <b>326</b> may use the multicast tree identifier in the multicast packet to determine a second set of bits. Note that the multicast tree identifier in the multicast packet identifies the multicast tree over which the multicast packet is to be forwarded. In some embodiments, the multicast tree identifier is an RBridge nickname. For example, RBridge <b>330</b> may be associated with multiple nicknames which may correspond to multiple multicast trees rooted at RBridge <b>330</b>.

The multicast tree illustrated in <figref idref="DRAWINGS">FIG. 3B</figref> can be associated with multicast tree identifier <b>356</b>, and RBridge <b>326</b> may use multicast tree identifier <b>356</b> to determine second set of bits <b>360</b>. The multicast tree illustrated in <figref idref="DRAWINGS">FIG. 3C</figref> can be associated with multicast tree identifier <b>366</b>, and RBridge <b>326</b> may use multicast tree identifier <b>366</b> to determine second set of bits <b>370</b>.

RBridge <b>326</b> can then combine the first set of bits and the second set of bits to obtain the internal multicast group identifier. For example, if the multicast packet contains multicast tree identifier <b>356</b>, RBridge <b>326</b> can combine first set of bits <b>358</b> with second set of bits <b>360</b> to obtain internal multicast group identifier <b>362</b>. On the other hand, if the multicast packet contains multicast tree identifier <b>366</b>, RBridge <b>326</b> can combine first set of bits <b>358</b> with second set of bits <b>370</b> to obtain internal multicast group identifier <b>372</b>.

<figref idref="DRAWINGS">FIG. 3E</figref> illustrates how an internal multicast group identifier can be used to determine a set of egress ports in accordance with some embodiments of the present invention.

Egress port lookup table <b>380</b> can be used to determine a set of egress ports based on the internal multicast group identifier. For example, performing a table lookup at RBridge <b>326</b> using internal multicast group identifier <b>362</b> may output set of egress ports {P-<b>336</b>}. Port P-<b>336</b> represents a port on RBridge <b>326</b> that is coupled to RBridge <b>336</b>. Similarly, performing a table lookup at RBridge <b>326</b> using internal multicast group identifier <b>372</b> may output set of egress ports {P-<b>322</b>, P-<b>336</b>}. Port P-<b>322</b> represents a port on RBridge <b>326</b> that is coupled to RBridge <b>322</b>. Once the set of egress ports has been determined, the system can forward copies of the multicast packet through the egress ports. Egress port lookup table <b>380</b> may be implemented as an array that is indexed using the internal multicast group identifier. Each entry in the array may store the set of egress ports.

Network Layer Multicasting in TRILL Networks

Some embodiments provide systems and techniques for performing network layer (e.g., IP layer) multicasting. Computer networking is typically accomplished using a layered software architecture, which is often referred to as a networking stack. Each layer is usually associated with a set of protocols which define the rules and conventions for processing packets in that layer. Each lower layer performs a service for the layer immediately above it to help with processing packets. At the source node, each layer typically adds a header as the payload moves from higher layers to lower layers through the source node's networking stack. The destination node typically performs the reverse process by processing and removing headers of each layer as the payload moves from the lowest layer to the highest layer at the destination node.

The multicast group membership at the network layer (e.g., the IP layer) can span multiple virtual networks, e.g., VPNs and/or VLANs. For example, in <figref idref="DRAWINGS">FIG. 1</figref>, a network layer multicast group may include end-hosts that are part of VLANs <b>116</b>, <b>118</b>, and <b>120</b> at sites S<b>2</b>, S<b>3</b>, and S<b>4</b>, respectively. In some embodiments, an RBridge can perform network layer multicasting, i.e., the RBridge can forward packets based on a network-layer multicast-address in addition to forwarding packets based on the TRILL header, VPN identifier, MAC addresses, and/or VLAN tags.

<figref idref="DRAWINGS">FIG. 4</figref> illustrates how an RBridge can perform network layer multicasting in a TRILL network in accordance with some embodiments of the present invention.

RBridges <b>402</b>-<b>416</b> can be in a TRILL network which includes multiple virtual networks, e.g., VPNs and/or VLANs. Each virtual network may support multiple TRILL multicast trees. For example, TRILL multicast tree <b>418</b>, which is illustrated using dotted lines, may belong to VLAN V<b>1</b>, and TRILL multicast tree <b>420</b>, which is illustrated using dashed lines, may belong to VLAN V<b>2</b>.

A network layer (e.g., IP layer) multicast group can include end-hosts that are spread across multiple virtual networks, e.g., VPNs and/or VLANs. For example, a multicast group may include end-hosts that are in VPNs and/or VLANs coupled to RBridges <b>402</b>, <b>408</b>, <b>412</b>, and <b>416</b> (these RBridges have been highlighted by drawing a circle around them). When a multicast packet for this multicast group is received at an RBridge, the RBridge may forward the multicast packet over a TRILL multicast tree on a particular VLAN. For example, when the multicast packet is received at RBridge <b>404</b>, it may forward the packet over TRILL multicast tree <b>418</b> on VLAN V<b>1</b>.

When the multicast packet is received at RBridge <b>410</b>, it may forward the packet based on the multicast packet's network-layer multicast-address. Specifically, RBridge <b>410</b> may determine that the multicast packet needs to be forwarded on both VLAN V<b>1</b> and VLAN V<b>2</b>. RBridge <b>410</b> may forward the multicast packet on any one of the multiple multicast trees that are supported on VLAN V<b>2</b>. However, to ensure correct multicast forwarding, RBridge <b>410</b> may need to forward the multicast packet on VLAN V<b>1</b> along the same multicast tree on which the multicast packet was received. Specifically, if RBridge <b>410</b> forwards the multicast packet on a multicast tree on VLAN V<b>1</b> that is different from the one it was received on, it can create a forwarding loop and/or the multicast packet may not reach all of the end-hosts in the multicast group. Note that these problems do not arise if the network does not support multiple multicast trees.

Note that an RBridge may or may not be configured to perform network layer multicasting. For example, in the above example, RBridge <b>404</b> is not configured to perform network layer multicasting, whereas RBridge <b>410</b> is configured to perform network layer multicasting.

In some embodiments, the multicast packet can be a TRILL multicast packet, and can include a multicast tree identifier associated with the multicast tree over which the multicast packet is to be forwarded. The header of a TRILL multicast packet can include a multicast field (e.g., multicast field <b>250</b> in <figref idref="DRAWINGS">FIG. 2</figref>) which indicates that the TRILL packet is a multicast packet. The egress RBridge nickname (e.g., egress RBridge nickname <b>256</b> in <figref idref="DRAWINGS">FIG. 2</figref>) can correspond to the root of the multicast tree over which the multicast packet is to be forwarded.

<figref idref="DRAWINGS">FIG. 5</figref> illustrates a switch in accordance with some embodiments of the present invention.

Switch <b>500</b> can include a plurality of mechanisms which may communicate with one another via a communication channel, e.g., a bus. Switch <b>500</b> may be realized using one or more integrated circuits.

In some embodiments, switch <b>500</b> is an RBridge (e.g., RBridge <b>102</b>) which includes receiving mechanism <b>502</b>, determining mechanism <b>504</b>, forwarding mechanism <b>506</b>, encapsulation mechanism <b>508</b>, and decapsulation mechanism <b>510</b>. In some embodiments, these mechanisms may be part of an application-specific integrated circuit.

Receiving mechanism <b>502</b> may be configured to receive a multicast packet (e.g., an Ethernet or TRILL multicast packet). Determining mechanism <b>504</b> may be configured to determine an internal multicast group identifier based on a source address, a multicast address, and a multicast tree identifier field associated with the multicast packet.

Forwarding mechanism <b>506</b> may be configured to forward the packet based on the internal multicast group identifier. Specifically, forwarding mechanism <b>506</b> may include a table (e.g., an array in memory) which is indexed using the internal multicast group identifier. Each record in the table (e.g., an array element) can include information that indicates how to forward the packet. For example, the record may include a set of egress port identifiers that identifies the egress ports. The record may also include instructions and/or information for modifying one or more fields in the header (e.g., the record may indicate that VLAN translation is to be performed and specify the new VLAN identifier). Additionally, the record may include header fields that need to be added to the packet (e.g., a TRILL header). Multiple copies of a multicast packet may be sent on an egress port of switch <b>500</b> if the multicast packet is to be sent to multiple VLANs that are coupled to the egress port.

Encapsulation mechanism <b>508</b> may be configured to encapsulate a copy of the multicast packet in a TRILL multicast packet. Specifically, encapsulation mechanism <b>508</b> may add a TRILL header to a copy of the multicast packet to obtain a TRILL multicast packet. In some embodiments, the TRILL header and the internal multicast group identifier may be determined concurrently. Once the TRILL header has been added, the TRILL multicast packet can be sent through the outgoing port.

Decapsulation mechanism <b>510</b> may be configured to decapsulate a TRILL multicast packet (e.g., by removing the TRILL header) to obtain the multicast packet that was encapsulated in the TRILL multicast packet. The multicast packet can then be forwarded to the customer's network (e.g., a customer VLAN).

In some embodiments, switch <b>500</b> (e.g., RBridge <b>410</b> in <figref idref="DRAWINGS">FIG. 4</figref>) may be configured to perform network layer multicasting. In these embodiments, receiving mechanism <b>502</b> may be configured to receive a multicast packet that includes a network-layer multicast-address. Specifically, receiving mechanism <b>502</b> may receive the multicast packet on a first multicast tree (e.g., TRILL multicast tree <b>418</b> in <figref idref="DRAWINGS">FIG. 4</figref>) associated with a first virtual network (e.g., VLAN V<b>1</b>). The multicast packet may include a first multicast tree identifier associated with the first multicast tree. The first multicast tree identifier can be the nickname of the RBridge at the root of the first multicast tree.

Determining mechanism <b>504</b> may be configured to determine, based on the network-layer multicast-address, one or more multicast trees associated with one or more virtual networks over which the packet is to be forwarded. For example, determining mechanism <b>504</b> may be configured to determine, based on the network-layer multicast-address, a second multicast tree (e.g., TRILL multicast tree <b>420</b> in <figref idref="DRAWINGS">FIG. 4</figref>) associated with a second virtual network (e.g., VLAN V<b>2</b>) over which the multicast packet is to be forwarded.

Forwarding mechanism <b>506</b> may be configured to forward the multicast packet on one or more multicast trees. For example, forwarding mechanism <b>506</b> may be configured to forward the multicast packet on the first multicast tree associated with the first virtual network, and forward a copy of the multicast packet on the second multicast tree associated with the second virtual network. The copy of the multicast packet may include a second multicast tree identifier associated with the second multicast tree. The second multicast tree identifier can be the nickname of the RBridge at the root of the second multicast tree.

In some embodiments, determining mechanism <b>504</b> may be configured to determine an internal multicast group identifier based on the network-layer multicast-address and a network-layer source-address of the multicast packet, and forwarding mechanism <b>506</b> may be configured to forward the multicast packet based on the internal multicast group identifier.

Note that <figref idref="DRAWINGS">FIG. 5</figref> is for illustration purposes only, and is not intended to limit the present invention to the forms disclosed. Specifically, in some embodiments, switch <b>500</b> may not be an RBridge, and/or may include fewer or more mechanisms than those shown in <figref idref="DRAWINGS">FIG. 5</figref>.

<figref idref="DRAWINGS">FIG. 6A</figref> presents a flowchart that illustrates a process for forwarding packets based on an internal multicast group identifier in accordance with some embodiments of the present invention.

The process can be performed by a switch, e.g., RBridge <b>102</b>. Upon receiving a multicast packet (e.g., an Ethernet or TRILL multicast packet), the switch can determine an internal multicast group identifier based on a source address (e.g., a source MAC or IP address), a multicast address (e.g., a multicast MAC or IP address), and a multicast tree identifier field associated with the multicast packet (operation <b>602</b>).

In some embodiments, the system can determine the internal multicast group identifier by combining two sets of bits: one set of bits determined based on the source address and the multicast address, and a second set of bits determined based on the multicast tree identifier. Specifically, in some embodiments, combining the two sets of bits involves concatenating the two sets of bits to create the internal multicast group identifier.

For example, the source IP address and the multicast IP address can be used to look up the first set of bits in a context addressable memory. If the multicast packet includes a multicast tree identifier (e.g., RBridge nickname), then the multicast tree identifier can be used to determine the second set of bits. If the multicast packet does not include a multicast tree identifier, then the system can determine the second set of bits by hashing one or more fields in the multicast packet (or by any other means). Next, the first set of bits can be concatenated with the second set of bits to obtain the internal multicast group identifier.

Next, the switch can forward the multicast packet based on the internal multicast group identifier (operation <b>604</b>). Specifically, the system can determine a set of egress ports based on the internal multicast group identifier. Next, the system can send at least one copy of the multicast packet through each port in the set of egress ports. The switch can additionally encapsulate the multicast packet in a TRILL multicast packet by adding a TRILL header, and send copies of the TRILL multicast packet through the set of egress ports which was determined based on the internal multicast group identifier.

<figref idref="DRAWINGS">FIG. 6B</figref> presents a flowchart that illustrates a process for performing network layer multicasting in a TRILL network in accordance with some embodiments of the present invention.

The process can be performed by a switch, e.g., RBridge <b>410</b> in <figref idref="DRAWINGS">FIG. 4</figref>. The switch can receive a multicast packet (e.g., an Ethernet or TRILL multicast packet) that includes a network-layer multicast-address, wherein the multicast packet is received on a first multicast tree associated with a first virtual network (operation <b>652</b>). For example, RBridge <b>410</b> may receive a multicast packet from RBridge <b>404</b> over TRILL multicast tree <b>418</b> on VLAN V<b>1</b>.

Next, the switch can determine, based on the network-layer multicast-address, a second multicast tree associated with a second virtual network over which the multicast packet is to be forwarded (operation <b>654</b>). For example, RBridge <b>410</b> may determine TRILL multicast tree <b>420</b> on VLAN V<b>2</b> over which the multicast packet is to be forwarded. The second multicast tree can be determined randomly or it can be determined based on link utilization (e.g., by determining the least congested multicast tree).

The switch can then forward the multicast packet on the first multicast tree associated with the first virtual network, and forward a copy of the multicast packet on the second multicast tree associated with the second virtual network (operation <b>656</b>). For example, RBridge <b>410</b> may forward the multicast packet to RBridges <b>408</b> and <b>414</b> over TRILL multicast tree <b>418</b>, and forward a copy of the multicast packet to RBridges <b>406</b> and <b>416</b> over TRILL multicast tree <b>420</b>.

<figref idref="DRAWINGS">FIG. 7</figref> illustrates a system in accordance with some embodiments of the present invention.

System <b>700</b> can include processor <b>702</b> (e.g., a network processor) and memory <b>704</b>. Processor <b>702</b> may be capable of accessing and executing instructions stored in memory <b>704</b>. For example, processor <b>702</b> and memory <b>704</b> may be coupled by a bus. Memory <b>704</b> may store instructions that when executed by processor <b>702</b> cause system <b>700</b> to perform the processes illustrated in <figref idref="DRAWINGS">FIGS. 6A and/or 6B</figref>.

Specifically, memory <b>704</b> may store instructions for receiving a multicast packet, determining an internal multicast group identifier for a multicast packet based on a source address, a multicast address, and a multicast tree identifier field associated with the multicast packet, and forwarding the multicast packet based on the internal multicast group identifier. Memory <b>704</b> may optionally store instructions for encapsulation and/or decapsulation.

In some embodiments, the multicast packet include a network-layer multicast-address and it may be received on a first multicast tree associated with a first virtual network. Memory <b>704</b> may store instructions for determining, based on the network-layer multicast-address, a second multicast tree associated with a second virtual network over which the multicast packet is to be forwarded. In these embodiments, memory <b>704</b> may also store instructions for forwarding the multicast packet on the first multicast tree associated with the first virtual network, and forwarding a copy of the multicast packet on the second multicast tree associated with the second virtual network.

The data structures and code described in this disclosure can be partially or fully stored on a non-transitory computer-readable storage medium and/or a hardware module and/or a hardware apparatus. A computer-readable storage medium includes, but is not limited to, volatile memory, non-volatile memory, magnetic and optical storage devices such as disk drives, magnetic tape, CDs (compact discs), DVDs (digital versatile discs or digital video discs), or other non-transitory media, now known or later developed, that are capable of storing code and/or data. Hardware modules or apparatuses described in this disclosure include, but are not limited to, application-specific integrated circuits (ASICs), field-programmable gate arrays (FPGAs), dedicated or shared processors, and/or other hardware modules or apparatuses now known or later developed. Specifically, the methods and/or processes may be described in a hardware description language (HDL) which may be compiled to synthesize register transfer logic (RTL) circuitry which can perform the methods and/or processes.

The methods and processes described in this disclosure can be partially or fully embodied as code and/or data stored in a computer-readable storage medium or device, so that when a computer system reads and/or executes the code and/or data, the computer system performs the associated methods and processes. The methods and processes can also be partially or fully embodied in hardware modules or apparatuses, so that when the hardware modules or apparatuses are activated, they perform the associated methods and processes. Further, the methods and processes can be embodied using a combination of code, data, and hardware modules or apparatuses.

The foregoing descriptions of embodiments of the present invention have been presented only for purposes of illustration and description. They are not intended to be exhaustive or to limit the present invention to the forms disclosed. Accordingly, many modifications and variations will be apparent to practitioners having ordinary skill in the art. Additionally, the above disclosure is not intended to limit the present invention. The scope of the present invention is defined by the appended claims.