Patent Description:
<CIT> relates to tracing packets in a packet processing pipeline of an SDN switch. A record of the route taken is recorded in the trace packet.

<CIT> relates to a method of detecting loops in Ethernet by recording the route in the payload of a special detection frame.

Example embodiments disclose an apparatus according to claim <NUM>. Further examples are provided in the dependent claims.

Example embodiments disclose a method according to claim <NUM>. Further examples are provided in the dependent claims.

The example embodiments in the summary and in the detailed description are not meant to be restrictive, but illustrative. The scope of the disclosure is defined in the claims.

An ethernet bridge includes different ports to receive and transmit packets, and forwards packets between the different ports based on entries in a table such as a MAC forwarding table. The entries in the MAC forwarding table include destination MAC addresses and corresponding destination ports that are used by the ethernet bridge to forward data link layer packets. In some cases, the ethernet bridge is a "self-learning bridge" because the MAC forwarding table is constructed using MAC addresses in received packets. For example, an initially empty MAC forwarding table in an ethernet bridge is configured based on packets that traverse the ethernet bridge along a path from a source host (identified by a first MAC address) to a destination host (identified by a second MAC address). If the source host sends the packet from a first port to a second port at the destination host, the transmitted packet includes a tuple formed of the first MAC address and the second MAC address. The ethernet bridge examines the packet and adds an entry to its MAC forwarding table that includes the first MAC address received from the source. However, the MAC forwarding table does not include an entry for the second MAC address because the ethernet bridge has not received a packet from the destination host. To gather the information needed for an entry for the second MAC address, the ethernet bridge floods copies of the packet on all links connected to the ethernet bridge. The same process is repeated on other ethernet bridges until a copy reaches the destination host, which may respond with a new packet including the second MAC address. The originating ethernet bridge (and any intervening ethernet bridges) use the information received in the new packet to complete the entry in their MAC forwarding tables for the second MAC address.

A network of ethernet bridges typically includes redundant paths between two or more points in the network for resiliency. However, the redundant paths also cause the flooded ethernet packets to repeatedly traverse paths through the network, a process referred to herein as looping. Conventional networks avoid the loops in the packet forwarding paths by implementing protocols such as a spanning tree protocol (STP) or variations thereof. The STP protocol builds a loop-free logical topology for the ethernet network to prevent loops and unnecessary broadcast radiation of packets that results from the loops. Once the loop-free logical topology has been identified by the STP protocol, links that can create loops for packets traversing the network are blocked by the ethernet bridges. In some cases, the STP protocol identifies backup links to provide fault tolerance in the event of failure of an active link. The STP protocol can selectively activate or block the backup links depending on whether a corresponding active link has failed. However, implementing the STP protocol does not avoid all loops in networks of ethernet bridges.

Inconsistencies or errors in the MAC forwarding tables at one or more of the ethernet bridges can generate transient or permanent loops even after implementation of an STP protocol. For example, a transient loop can occur in response to a topology change before convergence of the STP protocol at all the ethernet bridges in the network. Transient loops typically resolve in response to convergence of the STP protocol, although the STP convergence time can be significant and grows with the size of the network. For another example, faulty behavior of an ethernet bridge can create a permanent loop that routes packets along a previously traversed path. The loops create broadcast storms in which the ethernet bridges flood broadcast and multicast packets from all their ports and repeatedly rebroadcast or remulticast the flooded packets into the network. The ethernet header does not support a time-to-live (TTL) or hop-count field so that packets that are transmitted into a loop topology can continue to loop forever. Conventional ethernet bridges detect loops by periodically transmitting a loop protocol packet and waiting to see if the loop protocol packet is returned to the ethernet bridge. If so, the ethernet bridge detects a loop and shuts down the port that received the packet. In some cases, a loop can produce incorrect entries in the MAC forwarding table that causes a looping packets to toggle between two ports. The ethernet bridge identifies loops by detecting the instability of a source MAC address between the different ports (since the path from a host to another host in the topology built by STP is symmetric). For example, when packets are looping, the ethernet bridge learns the source MAC address in the packets alternately from two different ports: (<NUM>) the port connected to the source, on which the packet actually arrived and (<NUM>) the port of arrival after completing the loop. The ethernet bridge shuts down the affected port(s) in response to detecting the instability. This is a drastic action because good (i.e., non-looping) packets also suffer due to shutting down of an entire port for the looping/bad packets.

Ethernet bridges can also be configured using shortest path bridging (SPB), which determines paths between the ethernet bridges in the network using link state protocols such as intermediate system-to-intermediate system (IS-IS). The link state protocol floods the status of locally connected networks and links of the ethernet bridges across the network. Each ethernet bridge builds an identical copy of the network topology based on the status information and then independently computes the paths to every other ethernet bridge (and any advertised networks), using path algorithms such as Dijkstra's Shortest Path First (SPF) algorithm, which computes the shortest paths between the nodes in a graph that represents the ethernet bridges in the network. The MAC forwarding table is therefore built using link state protocols based on an SPF algorithm instead of a MAC learning technique. However, as discussed above, inconsistencies or errors in the MAC forwarding tables can produce loops in the ethernet bridges that are configured using SPB, including micro-loops that cause packets to loop back and forth between a pair of ethernet bridges and macro-loops that traverse three or more ethernet bridges. The SPB routes are symmetric so that a route from one host to another is the same going back. This allows SPB to use some of the management and monitoring technologies already in use for self-learning bridges. For example, since the paths are symmetric, the loop detection techniques of self-learning bridges may be applied in SPB, provided the ethernet bridges can learn the source MAC addresses of received packets for loop detection purposes. However, the source MAC learning action is costly for SPB and even if implemented, is subject to the same limitations as mentioned earlier for the loop detection technique (e.g., the ethernet bridge shuts down the entire port and penalizes looping and non-looping packets). Secondly, it may be possible to relax current default behavior of symmetric routes to allow asymmetric routes. In that case, there is no loop detection mechanism.

In a border gateway protocol (BGP) EVPN, the provider edge (PE) routers host a bridging instance for each EVPN. For example, a PE router hosts a MAC forwarding table per EVPN. A packet conveyed from one host to another host within an EVPN may traverse a set of PE routers and each PE router forwards the packet to its next PE router based on the MAC forwarding table for the EVPN. Thus, the PE routers form the network of ethernet bridges for an EVPN instance. The entries in the MAC forwarding tables are built by BGP running among the PE routers. Host addresses of a directly connected EVPN site are advertised by the local PE router using BGP and the other PE routers participating in the EVPN accordingly learn the host addresses. Then, a PE router computes the best path for each known MAC address in the EVPN using conventional BGP procedures. This enables the forwarding of ethernet packets to take advantage of features of traditional IP routing, such as Equal Cost Multi-Path (ECMP) and asymmetric routing in which a route from one host to another may not be same going back to the original host. The PE routers do not implement a loop detection mechanism and, consequently, packets in the network could loop forever if there are errors or inconsistencies in a MAC forwarding table at a PE router or faulty behavior of BGP in a PE router.

<FIG> disclose embodiments of an ethernet bridge that detects looping data link layer packets in a network of ethernet bridges after a single micro or macro-loop using a recorded route for ethernet (RRE) that is included in an ethernet header in the data link layer packets. Examples of data link layer packets include ethernet packets that are transmitted in the forwarding or data plane. The ethernet bridges in the network are assigned identifiers that uniquely identify the ethernet bridges within the network. Examples of bridge identifiers include virtual local area network (VLAN) identifiers that are assigned to the ethernet bridges from a central database of VLAN identifiers for the bridges in the network, a MAC address of the ethernet bridge, and the like. In response to receiving a packet, the ethernet bridge examines the identifiers in the RRE of the ethernet header in the data link layer packet. If the ethernet bridge does not find its unique identifier in the RRE, the ethernet bridge pushes its unique identifier onto the RRE and forwards the data link layer packet to the next hop based on information in the MAC forwarding table at the ethernet bridge. If the ethernet bridge detects its unique identifier in the RRE, which indicates that the data link layer packet has traversed a loop back to the ethernet bridge after the first reception of the packet at the ethernet bridge, the ethernet bridge drops the packet. In some embodiments, the ethernet bridge provides a loop detection notification that identifies the ethernet bridge and includes the RRE to facilitate diagnosis and repair of the loop. In some embodiments, loop detection is enabled for ethernet bridges in response to rerouting of a data link layer that encountered a link failure in the network. Ethernet bridges that implements selective enabling of loop detection also examine received packets to determine whether an RRE is present. If so, the ethernet bridge enables loop detection and examines the identifiers in the RRE of the ethernet header, as discussed above. An ingress ethernet bridge appends an RRE including its unique identifier to data link layer packets if loop detection is enabled, either selectively or by default.

<FIG> is a block diagram of a communication system <NUM> including an ethernet network that implements self-learning bridges according to some embodiments. The communication system <NUM> provides communication pathways to convey packets from a source <NUM> to a destination <NUM> via a set of ethernet bridges <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, which are collectively referred to herein as "the ethernet bridges <NUM>-<NUM>. " Although the term "bridge" as used to refer to the nodes in the ethernet network implemented in the communication system <NUM>, nodes in an ethernet network are also referred to using other terms including "switches" and the phrase "ethernet bridge" used herein will be understood to refer generally to nodes in an ethernet network that operate at the ethernet layer of a protocol stack and receive/forward ethernet packets.

Ethernet bridges <NUM>-<NUM> use a table such as a media access control (MAC) forwarding table to control the forwarding of packets between ports of the ethernet bridges <NUM>-<NUM>. Initially, the MAC forwarding table is empty and entries are added as the ethernet bridges <NUM>-<NUM> receive packets. The source MAC address of a packet received by one of the ethernet bridges <NUM>-<NUM> is added as an entry in the corresponding MAC forwarding table with the port of arrival as the forwarding port for the MAC address. If the destination MAC address entry is not found in the MAC forwarding table, the packet is flooded to all other ports of the receiving ethernet bridge <NUM>-<NUM>, except the port from which the packet was received. In response to receiving one of these flooded packets, a host in the communication system <NUM> (such as the destination <NUM>) may respond with a packet that includes the destination MAC address as the source address MAC address of the packet. The originating ethernet bridge <NUM>-<NUM> uses the response packet to create a MAC database entry. Both source and destination addresses are used in this process: source addresses are recorded as entries in the MAC forwarding table, while destination addresses are looked up in the table and matched to the proper port to send the packet to. The ethernet bridges <NUM>-<NUM> are also termed as "self-learning bridges" since MAC forwarding table is built automatically by snooping source MAC addresses of received packets.

In the illustrated embodiment, the ethernet network in the communication system <NUM> includes redundant paths between the source <NUM> and the destination <NUM> for resiliency. However, the redundant paths can also cause loops for flooded ethernet packets. To avoid loops in packet forwarding paths, the conventional ethernet network shown in <FIG> deploys a Spanning Tree Protocol (STP) or one of its variants such as rapid spanning tree protocol (RSTP), multiple spanning tree protocol (MSTP), and the like. As used herein, the term "STP" refers to all such loop resolution protocols used in traditional ethernet bridging. The STP procedure builds a loop-free logical topology for ethernet networks and the basic function is to prevent loops and the broadcast radiation that results from them. The STP procedure also allows a network design to include backup links providing fault tolerance if an active link fails. For example, STP is enabled on all interconnecting links between the ethernet bridges <NUM>-<NUM>. As a result, the ethernet bridge <NUM> blocks the link <NUM>, as indicated by the dashed arrow <NUM>, which means the ethernet bridge <NUM> does not forward or receive packets on the link <NUM>. The STP triggers the ethernet bridge <NUM> to activate the link <NUM> in response to failure of the link <NUM>. For another example, the ethernet bridge <NUM> blocks the link <NUM>, as indicated by the dashed arrow <NUM>. As a result, the ethernet network provides a loop free logical topology (a tree, represented by the arrow <NUM>) interconnecting the ethernet bridges <NUM>, <NUM>.

The source <NUM> identified by the MAC address M1 sends an ethernet packet to a destination <NUM>, which is identified by MAC address M2. The packet is received by the ethernet bridge <NUM>, which adds the entry for M1 into the MAC forwarding table with the link <NUM> as the forwarding port. The ethernet bridge <NUM> does not find any entry for M2 in the table, so it floods the packet on all links, e.g., on the link <NUM> and the link <NUM>. The ethernet bridge <NUM> drops the copy of the packet it receives on the link <NUM>, which is blocked by STP. Similarly, the other ethernet bridges <NUM>-<NUM> flood the packet and a copy eventually reaches the destination <NUM>, which may generate a response packet in response to receiving the copy. The ethernet bridges <NUM>-<NUM> eventually receive a copy of the response packet. The ethernet bridges <NUM>-<NUM> use the exchanged packets to create entries in the MAC forwarding tables. For example, the ethernet bridges <NUM>-<NUM> uses the information in the original packet (or copy thereof) to learn the MAC address M1 of the source <NUM>. The ethernet bridges <NUM>-<NUM> install entries for the source <NUM> (and corresponding MAC address M1) in their respective MAC forwarding tables. If the destination <NUM> subsequently sends an ethernet packet to the source <NUM>, then the ethernet bridges <NUM>-<NUM> forward (unicast) the packet to its designated port based on the entry for M1 in their MAC forwarding tables. For another example, the ethernet bridges <NUM>-<NUM> use the information in the response packet (or copy thereof) to learn the MAC address M2 of the destination <NUM>. The ethernet bridges <NUM>-<NUM> uses information to install entries for the destination <NUM> (and corresponding MAC address M2) in their respective MAC forwarding tables. If the source <NUM> subsequently sends a packet to the destination <NUM>, the ethernet bridges <NUM>-<NUM> do not perform packet flooding since an entry for M2 exists in MAC forwarding tables in the ethernet bridges <NUM>-<NUM>.

Although STP is intended to prevent loops in the ethernet network of the communication system <NUM>, loops can occur in some circumstances. Transient loops occur in the ethernet network during STP convergence across the network due to topology changes. Faulty behaviour of one or more of the ethernet bridges <NUM>-<NUM> can cause permanent loops. For example, a failure of one of the ethernet bridges <NUM>-<NUM> can redirect ethernet data packets along an incorrect path so that the packets re-enter a previously traversed path. This permanently creates broadcast storms as broadcasts and multicasts of the packet are forwarded out of every port as the ethernet bridges <NUM>-<NUM> flood the ethernet network with copies of the packets. Furthermore, the ethernet header does not support a time-to-live (TTL) field or a hop count field so ethernet packets that are sent into a looped topology can continue to loop forever.

Loops are detected in some cases using a looped detection protocol that runs atop the ethernet protocol. For example, when loop detection is enabled on a port of an ethernet bridge <NUM>-<NUM>, the port periodically transmits and ethernet multicast packet with a user-defined MAC address. The ethernet bridge <NUM>-<NUM> then waits to see if the loop detection packet is returned to the ethernet bridge <NUM>-<NUM>, which indicates the presence of the loop. If the ethernet bridge <NUM>-<NUM> detects a loop on a port, the ethernet bridge <NUM>-<NUM> shuts down the port that receive the packet. For another example, loops generate erroneous or misleading entries in the MAC forwarding table of an ethernet bridge <NUM>-<NUM> because the looping packet would toggle between two arriving ports and the ethernet bridge <NUM>-<NUM> would learn the same source MAC address from at least two different ports. The ethernet bridge <NUM>-<NUM> can therefore detect a loop by identifying a port instability (e.g., toggling of learnt MAC address between multiple ports) in the MAC forwarding table. In this case the ethernet bridge <NUM>-<NUM> also shuts down the ports associated with the looping packet. Shutting down the ports is a brute force technique that also impacts packets that are not in a loop.

Conventional ethernet bridging using the STP technique also has other limitations. The STP convergence of the ethernet network is relatively slow and inefficient. Furthermore, the convergence time depends on the size of the network and can require minutes to converge in some cases. The size dependence of the STP convergence time also sets a limit on the size of the ethernet network. Multipath routing is also not possible in an ethernet network that uses STP because the MAC addresses learned by the ethernet bridges <NUM>-<NUM> are bound to specific links. Thus, all packets destined to the same MAC address are forwarded along the same (fixed) path through the network.

<FIG> is a block diagram of a communication system <NUM> including an ethernet network that implements shortest path bridging (SPB) according to some embodiments. The communication system <NUM> provides communication pathways to convey packets from a source <NUM> to a destination <NUM> via a set of ethernet bridges <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, which are collectively referred to herein as "the ethernet bridges <NUM>-<NUM>. " SPB allows multiple equal cost paths to be active concurrently, provides larger layer ethernet topologies, supports faster convergence times, and improves efficiency by allowing traffic to load chair across multiple paths in the network. SPB provides logical Ethernet networks on native Ethernet infrastructures using a link state protocol to advertise both topology and logical network membership. The control plane of the ethernet network is based on the Intermediate System to Intermediate System (IS-IS) routing protocol and is equivalent to Interior Gateway Protocols (IGPs) such as OSPF, IS-IS, OSPFv3 based IP networks in the ethernet networks. The ethernet bridges <NUM>-<NUM> that implement SPB are not self-learning bridges. Instead, the ethernet bridges <NUM>-<NUM> build MAC forwarding tables based on the topology database built by link state protocols. The ethernet bridges <NUM>-<NUM> compute the paths to all external MAC addresses in the topology database by using the Shortest Path First (SPF) algorithm and installing entries in MAC forwarding tables. Since there is no self-learning action, there is no unnecessary flooding of packets in SPB when a packet needs to be sent to an unknown destination MAC address. If destination MAC address of a packet is not found in MAC forwarding table then the packet is dropped.

In the illustrated embodiment, the ethernet bridges <NUM>-<NUM> flood topology information across the network, e.g., using IS-IS as the link state protocol. As a result, an identical topology database is built by each of the ethernet bridges <NUM>-<NUM>. Based on the topology database, the ethernet bridges <NUM>-<NUM> independently compute the shortest path to every other known destination MAC address and installs entries in their MAC forwarding tables. For example, the ethernet bridges <NUM>-<NUM> compute shortest paths to the source <NUM> (indicated by the MAC address M1) and the destination <NUM> (indicated by the MAC address M2). Entries for the MAC addresses M1, M2 are therefore installed in the MAC forwarding tables of the ethernet bridges <NUM>-<NUM>. When the source <NUM> sends a packet to the destination <NUM>, an entry to M2 already exists in the MAC forwarding tables and the packet is unicasted by each transiting bridge (e.g., the ethernet bridges <NUM>-<NUM>) towards the destination <NUM>. In some embodiments, there are multiple equal cost paths between the ingress ethernet bridge <NUM> and the egress ethernet bridge <NUM>. For example, equal cost paths may include a first path along ethernet bridge <NUM> → ethernet bridge <NUM> → ethernet bridge <NUM> and a second path along ethernet bridge <NUM> → ethernet bridge <NUM> → ethernet bridge <NUM> → ethernet bridge <NUM>. Packets transmitted from the source <NUM> to the destination <NUM> can therefore be load balanced between the two paths by the source <NUM>.

Loops can occur in the ethernet network of the communication system <NUM> for various reasons. The loops include micro-loops that are formed between pairs of the ethernet bridges <NUM>-<NUM> and macro-loops that include more than two of the ethernet bridges <NUM>-<NUM>.

<FIG> is a block diagram of the communication system <NUM> that has developed micro-loops during SPB convergence according to some embodiments. The communication system <NUM> provides communication pathways to convey packets from a source <NUM> to a destination <NUM>, as indicated by the arrow <NUM>. The source <NUM> and the destination <NUM> are implemented in one or more entities such as desktop computers, laptop computers, tablet computers, smart phones, Internet of Things (IoT) devices, and the like. The communication system <NUM> includes a set of ethernet bridges <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, which are collectively referred to herein as "the ethernet bridges <NUM>-<NUM>.

Packets are conveyed from the source <NUM> to the destination <NUM> along a path that includes the ethernet bridges <NUM>-<NUM>. In the illustrated embodiment, a link between the ethernet bridge <NUM> and the ethernet bridge <NUM> fails, as indicated by the cross <NUM>. In response to failure of the link, the ethernet bridge <NUM> sends a link state update that informs the ethernet bridges <NUM>-<NUM> that the link has failed. The SPF algorithm implemented in the ethernet bridges <NUM>-<NUM> eventually recomputes their respective paths to <NUM> and <NUM> based on the modified topology. For some of the ethernet bridges the path to <NUM> or <NUM> may change or may not change depending on whether the link <NUM> was along the shortest paths to the respective hosts. Due to failure of the link <NUM>, the shortest path from the source <NUM> to the destination <NUM> is from the ethernet bridge <NUM> to the ethernet bridge <NUM> via the ethernet bridges <NUM>-<NUM>. Each bridge independently computes SPF algorithm and eventually updates their MAC forwarding table entry for <NUM> along that path. However, the SPF algorithm takes a finite amount of time to converge at the ethernet bridges <NUM>-<NUM> and does not necessarily converge at the same time at all the ethernet bridges <NUM>-<NUM>, which can result in the ethernet bridges <NUM>-<NUM> forwarding packets to <NUM> along an inconsistent path.

Loops form between the ethernet bridges <NUM>-<NUM> while the SPF algorithms are converging at the ethernet bridges <NUM>-<NUM>. For example, if the SPF algorithm at the ethernet bridge <NUM> converges before the SPF algorithm at the ethernet bridge <NUM>, the ethernet bridge <NUM> continues to forward packets to the ethernet bridge <NUM> (along the original shortest path) and the ethernet bridge <NUM> forwards the packets back to the ethernet bridge <NUM> (along the new shortest path), thereby forming a loop <NUM>. In response to the SPF algorithm converging at the ethernet bridge <NUM>, the ethernet bridge <NUM> forwards packets to the ethernet bridge <NUM>. However, if the SPF algorithm has not yet converged at the ethernet bridge <NUM>, the ethernet bridge <NUM> forwards packets to the ethernet bridge <NUM> (along the new shortest path) and the ethernet bridge <NUM> forwards the packets back to the ethernet bridge <NUM> (along the original shortest path) thereby forming a loop <NUM>. In a similar manner, loops <NUM>, <NUM>, <NUM> can form while the SPF algorithm is converging at the ethernet bridges <NUM>, <NUM>, <NUM>. The loops <NUM>, <NUM>-<NUM> form between pairs of ethernet bridges <NUM>-<NUM> and are therefore referred to herein as micro-loops. The duration of the loops is proportional to the time required to propagate the topology change through the network, as well as the time required for the SPF algorithm to converge at the ethernet bridges <NUM>-<NUM> and for the ethernet bridges <NUM>-<NUM> to update the MAC forwarding tables.

In principle, the effects of the micro-loops could be eliminated by speeding the whole convergence process to almost zero, but fundamental limits such as the speed of light and memory update latency make this highly unlikely or impossible. Some embodiments of ethernet networks reduce the impact of transient loops using Fast-Rerouting (FRR) of packets in an SPB network. The FRR technique uses loop free alternate (LFA) paths computed by link state protocols as a backup path if the backup path doesn't cause a forwarding loop. To avoid forwarding loops, the ethernet bridges <NUM>-<NUM> perform additional calculations to verify that a candidate backup path does not create a forwarding loop. A path that does not cause a forwarding loop is identified as an LFA path. The ethernet bridges <NUM>-<NUM> identify the LFA paths in advance and install them against the respective primary paths (shortest paths) into the MAC forwarding table.

<FIG> is a block diagram of a communication system <NUM> that computes backup paths based on metrics or costs associated with links according to some embodiments. The communication system <NUM> provides communication pathways to convey packets from a source <NUM> to a destination <NUM>. The communication system <NUM> includes a set of ethernet bridges <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, which are collectively referred to herein as "the ethernet bridges <NUM>-<NUM>. " The ethernet bridges <NUM>-<NUM> are interconnected by corresponding links <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, which are collectively referred to herein as "the links <NUM>-<NUM>. " The metric or cost of the links <NUM>-<NUM> are shown in circles alongside the links <NUM>-<NUM>.

In the illustrated embodiment, the ethernet bridge <NUM> is connected to the source <NUM> of ethernet packets and therefore calculates paths through the communication system <NUM>. The ethernet bridges <NUM>, <NUM> are neighbors of the ethernet bridge <NUM>. The ethernet bridge <NUM> is connected to the destination <NUM> and so the ethernet bridge <NUM> advertises the destination <NUM> as a local destination in the link state protocol. The ethernet bridge <NUM> computes the shortest path to the ethernet bridge <NUM> as ethernet bridge <NUM> → ethernet bridge <NUM> → ethernet bridge <NUM>, which is a total cost of <NUM>. For this path, the ethernet bridge <NUM> is the primary next hop. The ethernet bridge <NUM> also computes an alternate, loop-free, path as ethernet bridge <NUM> → ethernet bridge <NUM> → ethernet bridge <NUM>→ ethernet bridge <NUM> because the shortest path to <NUM> from the ethernet bridge <NUM> is not through the local router <NUM>. Traffic sent by the ethernet bridge <NUM> to the backup next hop <NUM> is not sent back to the ethernet bridge <NUM> so the ethernet bridge <NUM> can use the ethernet bridge <NUM> as a backup next hop for the path to the ethernet bridge <NUM>. The ethernet bridge <NUM> therefore programs the path to the ethernet bridge <NUM> (and all its attached hosts) into its MAC forwarding table with the ethernet bridge <NUM> is the primary next hop and the ethernet bridge <NUM> as the backup next hop. In response to the link <NUM> failing, the ethernet bridge <NUM> fast reroutes ethernet packets to the ethernet bridge <NUM> via the backup next hop which is the ethernet bridge <NUM>, which forwards the packets along the primary path ethernet bridge <NUM> → ethernet bridge <NUM>→ ethernet bridge <NUM>.

In some embodiments, the ethernet bridge <NUM> computes an LFA path to the ethernet bridge <NUM> to protect against failure of its primary next-hop ethernet bridge <NUM>. As evident from the topology, the alternate path ethernet bridge <NUM> → ethernet bridge <NUM>→ ethernet bridge <NUM>→ ethernet bridge <NUM> (total cost <NUM>) is loop-free, because the shortest path for the ethernet bridge <NUM> (ethernet bridge <NUM> → ethernet bridge <NUM>→ ethernet bridge <NUM>, cost <NUM>) is not via the ethernet bridge <NUM>. Thus, the ethernet bridge <NUM> programs the ethernet bridge <NUM> (and all its attached hosts) into its MAC forwarding table with the ethernet bridge <NUM> as the primary next-hop and the ethernet bridge <NUM> as backup next-hop.

<FIG> is a block diagram of the communication system <NUM> that uses the backup paths during concurrent failure of multiple links according to some embodiments. In the illustrated embodiment, the link <NUM> between the ethernet bridge <NUM> and the ethernet bridge <NUM> fails concurrently with the link <NUM> between the ethernet bridge <NUM> and the ethernet bridge <NUM>, as indicated by the crosses <NUM>, <NUM>. Thus, both the primary path and the alternate path that were previously calculated using the SPF algorithms in the ethernet bridges <NUM>-<NUM> are interrupted by the concurrent link failures. Failure of the link <NUM> between the ethernet bridge <NUM> and the ethernet bridge <NUM> causes the ethernet bridge <NUM> to fast reroute packets along the alternate path to the next hop ethernet bridge <NUM>. However, failure of the link between the ethernet bridge <NUM> and the ethernet bridge <NUM> causes the ethernet bridge <NUM> to fast reroute packets along the alternate path to the next hop ethernet bridge <NUM>. A loop <NUM> is therefore formed between the ethernet bridge <NUM> and the ethernet bridge <NUM> due to the multiple link failures. The loop <NUM> persists until the SPF algorithms executed by the ethernet bridges <NUM>-<NUM> converge to a new solution in the presence of the link failures, e.g., a new shortest path from the source <NUM> to the destination <NUM> that conveys packets along a path from the ethernet bridge <NUM> to the ethernet bridge <NUM> to the ethernet bridge <NUM> to the ethernet bridge <NUM>.

<FIG> is a block diagram of a communication system <NUM> that determines a primary shortest path and an alternate shortest path using a shortest path first (SPF) algorithm according to some embodiments. The communication system <NUM> includes ethernet bridges <NUM>, <NUM>, <NUM>, <NUM>, which are collectively referred to herein as "the ethernet bridges <NUM>-<NUM>. " In the illustrated embodiment, the ethernet bridge <NUM> is a source router that is connected to a source and the ethernet bridge <NUM> is a destination router that is connected to a destination. The metrics or costs of the links are indicated in the circled numerals. For example, the cost of the link between the ethernet bridge <NUM> and the ethernet bridge <NUM> is one and the cost of the link between the ethernet bridge <NUM> and the ethernet bridge <NUM> is three.

The ethernet bridges <NUM>, <NUM>, <NUM> compute the primary and alternate shortest paths to the destination ethernet bridge <NUM> based on the metrics or costs. The ethernet bridge <NUM> computes a primary path that includes the ethernet bridges <NUM>, <NUM>, <NUM> (at a cost of two) and an alternate path that includes the ethernet bridges <NUM>, <NUM>, <NUM> (at a cost of four). The primary path from the ethernet bridge 601to the ethernet bridge <NUM> as indicated by the arrow <NUM>. The ethernet bridge <NUM> computes a primary path that includes the ethernet bridges <NUM>, <NUM> (at a cost of one) and an alternate path that includes the ethernet bridges <NUM>, <NUM>, <NUM> (at a cost of five). The ethernet bridge <NUM> computes a primary path that includes the ethernet bridges <NUM>, <NUM> (at a cost of two) and an alternate path that includes the ethernet bridges <NUM>, <NUM>, <NUM>, <NUM> (at a cost of four).

<FIG> is a block diagram of the communication system <NUM> that forms a macro-loop <NUM> in response to concurrent failure of multiple links according to some embodiments. In the illustrated embodiment, the link between the ethernet bridge <NUM> and the ethernet bridge <NUM> fails concurrently with the link between the ethernet bridge <NUM> and the ethernet bridge <NUM>, as indicated by the crosses <NUM>, <NUM>. In response to receiving a packet from the ethernet bridge <NUM>, the ethernet bridge <NUM> detects the failure of the link to the ethernet bridge <NUM> and reroutes the received packet via its previously calculated alternate path to the next hop ethernet bridge <NUM>. In response to receiving the packet from the ethernet bridge <NUM>, the ethernet bridge <NUM> detects the failure of the link to the ethernet bridge <NUM> and reroutes the received packet via its previously calculated alternate path to the ethernet bridge <NUM>, which forwards the packet via its primary path to the ethernet bridge <NUM>, thereby forming a macro-loop <NUM> including the ethernet bridges <NUM>, <NUM>, <NUM>. In this case, the macro-loop <NUM> resolves in response to convergence of the SPF algorithm at the ethernet bridges <NUM>-<NUM> following the link failures.

Macro-loops also form in the communication system <NUM> in non-failure scenarios. For example, if the ethernet bridges <NUM>, <NUM> incorrectly compute the shortest paths or incorrectly update the MAC forwarding table based on a correctly computed shortest path, the macro-loop <NUM> can form in the communication system <NUM>. In response to receiving a packet from the ethernet bridge <NUM>, the ethernet bridge <NUM> forwards the received packet based on the incorrectly calculated or stored shortest path to the next hop ethernet bridge <NUM>. In response to receiving the packet from the ethernet bridge <NUM>, the ethernet bridge <NUM> forwards the received packet based on the incorrectly calculated or stored shortest path to the ethernet bridge <NUM>, which forwards the packet via its primary path to the ethernet bridge <NUM>, thereby forming the macro-loop <NUM> including the ethernet bridges <NUM>, <NUM>, <NUM>. In this case, the macro-loop <NUM> is not transient and may not be resolved without intervention.

Traditionally, SPB routes are symmetric so that a route from one host to another is the same going back to the original host. This allows SPB to use some of the management and monitoring technologies already in use for self-learning bridges. For example, since the paths are symmetric, the loop detection techniques of self-learning bridges may be applied in SPB, provided the ethernet bridges employing SPB can also learn the source MAC addresses of received packets for loop detection purposes. However, the source MAC learning action is costly for SPB and even if implemented, is subject to the same limitations as mentioned earlier for the loop detection technique (e.g., the ethernet bridge shuts down the entire port and penalizes looping and non-looping packets). Secondly, it may be possible to relax current default behavior of symmetric routes to allow asymmetric routes. In that case, there is no loop detection mechanism in SPB.

<FIG> is a block diagram of a communication system <NUM> that includes a public network <NUM> that provides VPN services for multiple VPNs according to some embodiments. The public network <NUM> includes transit or provider (P) routers <NUM>, <NUM>, <NUM>, <NUM> (collectively referred to herein as "the routers <NUM>-<NUM>") that route packets through the public network <NUM> based on information included in the packets and forwarding tables stored in the P routers <NUM>-<NUM>. The public network <NUM> also includes PE routers <NUM>, <NUM>, <NUM>, <NUM>, which are collectively referred to herein as "the PE routers <NUM>-<NUM>. " The PE routers <NUM>-<NUM> are gateways that provide access to services offered by the public network <NUM>, such as VPN services. In the illustrated embodiment, the PE routers <NUM>-<NUM> act as ethernet bridges for the VPN sites described below.

In the illustrated embodiment, the public network <NUM> offers connectivity between remote sites of two VPNs <NUM>, <NUM>. The VPN <NUM> includes a remote site <NUM>-<NUM> that is connected to the PE router <NUM> in the public network <NUM> by a customer edge (CE) router <NUM> via an access link <NUM>, a remote site <NUM>-<NUM> that is connected to the PE router <NUM> by a CE router <NUM> via an access link <NUM>, a remote site <NUM>-<NUM> that is connected to the PE router <NUM> by a CE router <NUM> via an access link <NUM>, and a remote site <NUM>-<NUM> that is connected to the PE router <NUM> by a CE router <NUM> via an access link <NUM>. The VPN <NUM> includes a remote site <NUM>-<NUM> that is connected to the PE router <NUM> in the public network <NUM> by a CE router <NUM> via an access link <NUM>, a remote site <NUM>-<NUM> that is connected to the PE router <NUM> by a CE router <NUM> via an access link <NUM>, a remote site <NUM>-<NUM> that is connected to the PE router <NUM> by a CE router <NUM> via an access link <NUM>, and a remote site <NUM>-<NUM> that is connected to the PE router <NUM> by a CE router <NUM> via an access link <NUM>. The PE routers <NUM>-<NUM> identify the VPNs <NUM>, <NUM> that provided packets based on the access links <NUM>-<NUM>, <NUM>-<NUM> that conveyed the packets to the PE routers <NUM>-<NUM>. In the illustrated embodiment, the PE routers <NUM>-<NUM>, and the CE routers <NUM>-<NUM> act as ethernet bridges for the VPN sites <NUM>, <NUM>.

Within the public network <NUM>, only the PE routers <NUM>-<NUM> maintain VPN-specific forwarding states. Some embodiments of the PE routers <NUM>-<NUM> maintain private forwarding tables for each VPN associated with the PE router. The private forwarding tables are sometimes referred to as "native VPN forwarding tables" in the following discussion. The native VPN forwarding tables in the PE routers <NUM>-<NUM> contain the forwarding rules for the "native" packet type of the VPN. For example, the native packet type is an IP packet in an IP-VPN, the native packet type is an Ethernet packet for an Ethernet based VPN, etc. When the PE routers <NUM>-<NUM> are operating as ingress routers, the forwarding rules in the native VPN forwarding tables are used to match and forward native packets received from a local VPN site via the access links <NUM>-<NUM>, <NUM>-<NUM> to one or more remote PE routers <NUM>-<NUM>. When the PE routers <NUM>-<NUM> are operating as egress routers, the forwarding rules in the native VPN forwarding tables are used to match and forward native packets received from a remote PE router <NUM>-<NUM> to local VPN sites via the access links <NUM>-<NUM>, <NUM>-<NUM>.

Table <NUM> is an example of a native VPN forwarding table at a PE router for an IP-VPN. In the terminology of IP-VPN, Table <NUM> is referred to as a Virtual Route Forwarder (VRF) for a VPN indicated by the value z.

The PE router accesses the native VPN forwarding table (e.g., Table <NUM>) in response to receiving an IPv4 packet for the VPN z from an access link. The IPv4 packet includes a destination address, e.g., the destination IP address of the packet is <NUM>. The PE router looks up the destination IP address in the native VPN forwarding table based on longest-prefix-match (LPM) to make a forwarding decision. In this case, the lookup matches the prefix <NUM>. <NUM>/<NUM>, which is in remote PE x. The PE router therefore sends the IPv4 packet to remote PE x. Similarly, if the PE router receives an IPv4 packet for VPN z from a remote PE router and the destination address in the packet as <NUM>. <NUM>, the PE router looks up a corresponding entry in the native VPN forwarding table, <NUM>. <NUM>/<NUM>, which results in the PE router forwarding the packet to the locally connected site of VPN z via access link y.

Some embodiments of the VPNs <NUM>, <NUM> are Layer-<NUM> VPNs such as BGP signaled multi-protocol label switching (MPLS) based Ethernet VPN (EVPN) and the PE routers <NUM>-<NUM> act as ethernet bridges for the VPN sites. The PE routers <NUM>-<NUM> learn the MAC addresses within a locally connected VPN site using MAC learning actions on the access links <NUM>-<NUM>, <NUM>-<NUM>. The learned MAC addresses are advertised by BGP in the context of the VPN-ID (Route Distinguisher) to all remote PE routers <NUM>-<NUM> and the VPN-Label is exchanged along with the MAC address advertisements. In case of EVPN, the VPN forwarding table at the PE routers <NUM>-<NUM> are MAC forwarding tables. In operation, an ingress PE router receives an Ethernet packet from a CE router in a VPN, looks up the destination MAC address of the ethernet packet in corresponding MAC forwarding table to retrieve the egress PE router that had advertised the MAC address. The ingress PE router then sends the ethernet packet to the egress PE router with the VPN-Label advertised by the egress PE router. Upon receipt of an ethernet packet with a VPN-Label, the egress PE router forwards the packet by looking up the destination MAC address of the packet in the MAC forwarding table.

In the illustrated embodiment, the PE routers <NUM>-<NUM> are not directly connected with each other, so the PE routers <NUM>-<NUM> tunnel the packets encapsulated by a VPN-Label between the PE routers <NUM>-<NUM> across the public network <NUM> using tunneling protocols such as MPLS based LSPs (Labelled Switched Paths), IP based tunneling methods such as GRE (Generic Routing Encapsulation), VXLAN (Virtual Extensible Local Area Network), MPLS over user datagram protocol (MPLSoUDP), and the like. The tunnels are sometimes referred as Packet Switched Network (PSN) tunnels. In the illustrated embodiment, the tunnels are implemented using MPLS LSPs as PSN Tunnels. The MPLS LSPs are established by LDP (Label Distribution Protocol), RSVP-TE (Resource Reservation Protocol - Traffic Engineering) or the tunnels are source routed stateless LSPs such as SR (Segment Routing), SR-TE (Segment Routing - Traffic Engineering), and the like. Packets from multiple VPNs can be multiplexed and sent on the same PSN tunnel between the PE routers <NUM>-<NUM> since the VPN-Label acts as a demultiplexer to distinguish packets for the VPNs.

In the illustrated embodiment, multiple VPNs <NUM>, <NUM> span the same set of PE routers <NUM>-<NUM>. However, in other embodiments, the VPNs <NUM>, <NUM> only a subset of the PE routers <NUM>-<NUM> in common. Furthermore, embodiments of the PE routers <NUM>-<NUM> allocate a single VPN Label and advertise the label to all remote/ingress PE routers. Some embodiments of the PE routers are implemented as a mesh network such that the VPN site <NUM>, <NUM> are interconnected by multiple PE routers in a multi-hop topology.

<FIG> is a block diagram of a communication system <NUM> that implements an ethernet virtual private network (EVPN) according to some embodiments. The communication system <NUM> includes two VPN sites <NUM>, <NUM> such as the VPN sites <NUM>-<NUM>, <NUM>-<NUM> shown in <FIG>. The VPN sites <NUM>, <NUM> are interconnected by a set of PE routers <NUM>, <NUM>, <NUM>, <NUM>, <NUM> (collectively referred to herein as "the PE routers <NUM>-<NUM>") that function as ethernet bridges for the EVPN. The PE routers are not directly connected to each other, rather interconnected by a public network of P routers, which are not shown in <FIG> in the interest of clarity. In the illustrated embodiment, the PE routers <NUM>-<NUM> are implemented as a mesh network over a public network. The BGP protocol running on the PE routers <NUM>-<NUM> advertises the MAC addresses that have been learned from the VPN site <NUM>, <NUM>, as discussed herein. The BGP protocol also computes pathways through the mesh topology and supports multipath routing of ethernet packets, which leads to looping scenarios as in the SPB protocols discussed above with regard to <FIG>.

In summary, the presence of loops is a problem in conventional ethernet bridging, SPB, and EVPN networks. The loop detection techniques implemented in conventional ethernet bridging shuts down a port in response to detecting a loop in a packet arriving at the port, which penalizes all the good (i.e., non-looping) packets that are also flowing through this port. Networks that implement SPB utilize several techniques for loop detection. However, these techniques are complex and work only in a few best-case topologies and non-critical failures, which makes them impractical to implement. Furthermore, loops caused by misbehavior at the ethernet bridges cannot be prevented using these techniques. The EVPN networks do not implement any loop detection schemes.

Adding a TTL or Hop Count extension header to ethernet headers can reduce, but not eliminate, the damage caused by looping packets. A looping packet may amplify traffic and consume bandwidth until the TTL expires or the packet escapes following MAC forwarding table convergence, which can transiently cause congestion even on a well provisioned link by increasing the traffic. Congestion reduces the bandwidth for other traffic (which would not have been affected otherwise) and causes delay and congestive packet loss on the links. The duration of the delay is determined by the duration of the loop. If the loop is a permanent one due to misbehavior of the ethernet bridges, then packets continue to loop until the TTL expires, which amplifies the bandwidth consumption by an amount determined by the number of loops before the TTL expires. If a loop consists of N routers and the TTL before the start of the loop is T, then a packet will make at least T/N loops before it gets dropped. Secondly, in the TTL expiry method, there is no meaningful way to report the set of ethernet bridges involved in the loop so that administrative actions can be taken; the first bridge that expires the TTL drops the packet and is agnostic of the nature of the loop.

<FIG> is a block diagram of an ethernet network <NUM> that implements loop detection based on a recorded route for ethernet (RRE) included in ethernet packets according to some embodiments. The ethernet network <NUM> includes ethernet bridges <NUM>, <NUM>, <NUM>, <NUM>, which are collectively referred to herein as "the ethernet bridges <NUM>-<NUM>. " The ethernet bridges may be traditional ethernet bridges or bridges in SPB network or EVPN instances in PE routers or the like. In the illustrated embodiment, the ethernet bridges <NUM>-<NUM> are implemented using a transceiver <NUM> to transmit and receive ethernet packets that are conveyed through the network, a memory <NUM> to store data and instructions, and a processor <NUM> to execute the instructions, e.g., by performing operations indicated by the instructions stored in the memory <NUM> on the data stored in the memory <NUM> and storing the results in the memory <NUM>.

The ethernet bridges <NUM>-<NUM> are configured with a network wide unique bridge identifier to uniquely identify the ethernet bridges <NUM>-<NUM> in the network. Some embodiments of the ethernet bridges <NUM>-<NUM> configure a local MAC address, which is used as the bridge identifier. The ethernet bridges <NUM>-<NUM> are therefore uniquely identified within the ethernet network <NUM> by the MAC addresses <NUM>-<NUM>, which are also represented as M1-M4 in <FIG>. A list of bridge identifiers of the ethernet bridges <NUM>-<NUM> along a path traversed by an ethernet packet is referred to herein as a "Recorded Route for Ethernet (RRE). " The list describes the set of bridges traversed along a path in their order of occurrence in the path. For example, the RRE for the path that connects the ethernet bridges <NUM>, <NUM>, <NUM> is {M3, M2, M1}. The bridge identifiers are pushed in reversed order and the RRE is appended to the ethernet header for which loop detection is being performed.

Some embodiments of the ethernet bridges <NUM>-<NUM> are assigned a VLAN Identifier (VID) as their unique network-wide identifier. The VID space used for the bridge identifiers is orthogonal to the VIDs used for VLAN based partitioning of network segments, as the former is not encoded into the packet as VLAN tag, rather encoded within RRE. The VID space used to allocate network-wide unique bridge identifiers is referred to herein as the "bridge identifier VID space (Br-VID space)" and a VID allocated from this space is referred herein as the "bridge identifier VID" (Br-VID). Identifying the ethernet bridges <NUM>-<NUM> using the VID as bridge identifier enables compact encoding of the RRE since size of a VID is <NUM> bits as opposed to <NUM>-octets of a MAC address. However, Br-VID based scheme requires centralized management of the Br-VID space and explicit configuration of Br-VIDs into the ethernet bridges <NUM>-<NUM> as identifiers.

The ethernet bridges <NUM>-<NUM> perform loop detection based on the RRE included in ethernet packets transmitted and received by the ethernet bridges <NUM>-<NUM>. An ethernet bridge <NUM>-<NUM> that intends to enable loop detection on an ethernet packet appends an RRE after the ethernet header processed by the ethernet bridge <NUM>-<NUM>. The ethernet bridge <NUM>-<NUM> encodes its own bridge identifier in the RRE, which is initially the only bridge identifier in the RRE. In response to receiving an ethernet packet, the ethernet bridges <NUM>-<NUM> inspect the ethernet packet to determine whether an RRE is appended to the ethernet header. If an RRE is found, then the ethernet bridge <NUM>-<NUM> performs the following actions:.

In the illustrated embodiment, a bridge does not push an RRE when a packet is forwarded normally along the primary path connecting the ethernet bridges <NUM>-<NUM>. The RRE is pushed only by an ethernet bridge that fast-reroutes a packet (if it does not contain an RRE already). For example, links to the bridge <NUM> have failed, as indicated by the crosses <NUM>, <NUM>. The ethernet bridge <NUM> transmits a packet to the ethernet bridge <NUM>, which makes a forwarding decision to the ethernet bridge <NUM> in response to receiving the ethernet packet. Due to the link failure indicated by the cross <NUM>, the ethernet bridge <NUM> fast-reroutes the packet via backup link to the ethernet bridge <NUM>. The ethernet bridge <NUM> appends the RRE after the ethernet header and encodes its bridge identifier M2 into RRE. The resultant packet with RRE = {M2} is sent to the ethernet bridge <NUM>.

On receiving the packet, the ethernet bridge <NUM> finds an RRE after the ethernet header and scans the RRE to look for its own bridge identifier M4. Since M4 is not found in the RRE, the ethernet bridge <NUM> makes a forwarding decision to the ethernet bridge <NUM>. Due to the link failure indicated by the cross <NUM>, the ethernet bridge <NUM> fast-reroutes the ethernet packet via the backup link to the ethernet bridge <NUM>. The ethernet bridge <NUM> pushes its own bridge identifier M4 onto the RRE. The ethernet bridge <NUM> sends the packet to the ethernet bridge <NUM> with RRE = {M3, M2}.

On receiving the packet, the ethernet bridge <NUM> finds an RRE after the ethernet header and so scans the RRE to look for its own bridge identifier M1. Since M1 is not found in RRE, it makes a forwarding decision to the ethernet bridge <NUM>. The ethernet bridge <NUM> pushes its bridge identifier M1 onto RRE. The packet is sent to the ethernet bridge <NUM> with RRE = {M1, M3, M2}.

On receiving the packet, the ethernet bridge <NUM> finds the RRE after the ethernet header and so scans the RRE to look for its bridge identifier M2. Since M2 is found in the RRE, the ethernet bridge <NUM> detects a loop <NUM> and drops the packet. If a reporting entity is configured in the network, then the ethernet bridge <NUM> generates a loop detection notification to the reporting entity. In the notification, the ethernet bridge <NUM> includes the copy of the packet. In the copy, the ethernet bridge <NUM> pushes its bridge identifier M2 onto the RRE. Consequently, the reporting entity receives the packet with RRE = {M2, M1, M3, M2}. The entity traces back the RRE to identify the recurrence of the topmost bridge identifier M2 and determines the loop as M2->M3->M1->M2.

Although the ethernet network <NUM> shown in <FIG> enables loop detection in response to fast re-routing by one of the ethernet bridges <NUM>-<NUM>, some embodiments of the ethernet network <NUM> enable loop detection in the network by default. For example, if the operator of the network intends to protect against loops created by misbehavior of one of the ethernet bridges <NUM>-<NUM>, inconsistency in MAC forwarding tables in ethernet bridges <NUM>-<NUM> during convergence of the SPB network or the EVPN network then the ingress bridge always pushes an RRE onto each packet. As a result, each subsequent ethernet bridge <NUM>-<NUM> along the path of the packet scans the RRE to check for loop, and if no loop is found then pushes its own bridge identifier onto the RRE before forwarding the packet. Apart from loop detection, the RRE can be used by a receiving bridge of a packet to also determine the path traversed by the packet for various purposes.

Including the RRE in ethernet packets does not incur a large overhead cost. For example, if the maximum number of bridges traversed by any ethernet packet is ten, the maximum overhead of RRE on an ethernet packet that uses MAC address as bridge identifier would be around 10x6B = 60B when the packet reaches the last bridge (as RRE grows linearly along each hop in the path). If the Br-VID is used as bridge identifier, then maximum overhead of RRE would be 10x2B = 20B which is <NUM>%reduction from the size when bridge identifier is encoded as MAC address. If the overhead is tolerable, an operator may choose to enable loop detection in the network by default so that ingress bridges always append an RRE after the ethernet header of packets. Otherwise, the operator may choose to selectively enable loop detection, such as during FRR or other network convergence scenarios. If loop detection is not enabled by default, then it is also possible that the operator of the ethernet network <NUM> can administratively inject a test packet at the ingress ethernet bridge <NUM> or in any intermediate bridge, such that the packet includes the RRE. Then if a loop is detected on the test packet by one of the ethernet bridges <NUM>-<NUM>, it may generate a loop detection notification with the details on the looping path. Such test packets could be OAM packets such as CFM packets to verify connectivity along a path.

<FIG> is a block diagram of a communication system <NUM> that includes a set of ethernet bridges that form a nested ethernet network according to some embodiments. One example of a nested ethernet network is a provider backbone bridge (PBB). Ethernet packets that traverse a PBB network included to ethernet headers that are referred to as MAC-in-MAC headers. The outer ethernet header (the backbone header) belongs to the provider of the backbone bridging domain. The inner ethernet header (customer header) belongs to a customer bridging domain. The levels corresponding to the backbone bridging domain and the customer bridging domain enable and perform loop detection independently. Ethernet bridges in the backbone and customer domains push or process RREs appended to the ethernet header at the corresponding level. For example, an ethernet bridge in the backbone bridging domain pushes or processes RREs appended to the outer ethernet header and an ethernet bridge in the customer bridging domain pushes or processes RREs appended to the inner ethernet header.

In the illustrated embodiment, the communication system <NUM> includes ethernet bridges <NUM>, <NUM>, <NUM>, <NUM>, <NUM> that are collectively referred to herein as "the ethernet bridges <NUM>-<NUM>. " The ethernet bridges <NUM>-<NUM> form two levels of a hierarchy of nested ethernet networks. The first, higher level is a customer bridging domain that supports a path including a portion <NUM> between the ethernet bridge <NUM> and the ethernet bridge <NUM> and a portion <NUM> between the ethernet bridge <NUM> and the ethernet bridge <NUM>. The second, lower, level includes a first backbone bridging domain that supports a path between the ethernet bridges <NUM>-<NUM> and a second backbone bridging domain that supports a path between the ethernet bridges <NUM>-<NUM>.

In the customer bridging domain, the ethernet bridge <NUM> sends a packet to the ethernet bridge <NUM> with a customer header. The ethernet bridge <NUM> looks up the destination MAC address of the customer header in the customers MAC forwarding table and, based on the lookup, forward the packet to the ethernet bridge <NUM>. Bridges in the customer domain are not directly connected so the customer packet is overlaid on a provider domain to reach a next bridge. In the illustrated embodiment, the customer bridging domain between the ethernet bridges <NUM>, <NUM> is overlaid on the first backbone bridging domain including the ethernet bridges <NUM>-<NUM>. The customer bridging domain between the ethernet bridges <NUM>, <NUM> is overlaid on the second backbone bridging domain including the ethernet bridges <NUM>-<NUM>. The ethernet bridge <NUM> therefore pushes a backbone header onto the packet with the destination MAC address of the ethernet bridge <NUM>. The headers in the packet therefore include {backbone header, customer header}. The packet is then processed along the path including the ethernet bridges <NUM>-<NUM> based on the backbone header and the backbone or provider MAC forwarding table. The ethernet bridge <NUM> pops the backbone header based on the destination MAC address in the backbone header. The ethernet bridge <NUM> that makes the forwarding decision for the packet based on the customer header and the customers MAC forwarding table. In the illustrated embodiment, the ethernet bridge <NUM> forwards the packet to the ethernet bridge <NUM>. Again, since the ethernet bridge <NUM> is not directly connected to the ethernet bridge <NUM> in the customer bridging domain, the ethernet bridge <NUM> pushes a backbone header onto the packet with a destination MAC address of the ethernet bridge <NUM>. The packet is then forwarded in the second backbone bridging domain as discussed herein.

To implement loop detection in the customer bridging domain and the backbone bridging domains, the ethernet bridges <NUM>-<NUM> are assigned unique network identifiers M1-M5, as discussed herein. The ethernet bridge <NUM> appends an RRE-<NUM> = {M1} after the customer header. Then the ethernet bridge <NUM> pushes the backbone header (with destination MAC of the ethernet bridge <NUM>) and appends RRE-<NUM> = {M1} after the backbone header. The headers in the resultant packet would be: {backbone header, RRE-<NUM>, customer header, RRE-<NUM>}, which is sent to the ethernet bridge <NUM>, which checks for a loop in RRE-<NUM>, pushes its bridge identifier M2 into RRE-<NUM>, and transmits the resultant packet with headers {backbone header, RRE-<NUM>= {M2, M1}, customer header, RRE-<NUM>={M1}} to the ethernet bridge <NUM>. The ethernet bridge <NUM> checks for loop in RRE-<NUM> and pops backbone header and RRE-<NUM> since the ethernet bridge <NUM> is the termination point of the first backbone bridging domain. The ethernet bridge <NUM> then finds the RRE-<NUM>, checks for loop, and inserts its bridge identifier M3 into RRE-<NUM>. The resultant packet {customer header, RRE-<NUM>= {M3, M1}} is sent over the second backbone bridging domain. The ethernet bridge <NUM> pushes the backbone header to the ethernet bridge <NUM> and then appends RRE-<NUM> = {M3} after the backbone header. The resultant packet with headers {backbone header, RRE-<NUM>= {M3}, customer header, RRE-<NUM>= {M3, M1}} is sent to the ethernet bridge <NUM>. The packet is then forwarded to the ethernet bridge <NUM> following the above procedure.

<FIG> is a block diagram of a communication system <NUM> that assigns unique identifiers to routers from a Br-VID space according to some embodiments. The communication system <NUM> includes ethernet bridges <NUM>, <NUM>, <NUM>, <NUM>, which are collectively referred to herein as "the ethernet bridges <NUM>-<NUM>. " In the illustrated embodiment, the ethernet bridge <NUM> is an ingress ethernet bridge that is connected to a source and the ethernet bridge <NUM> is an egress ethernet bridge that is connected to a destination. The metrics or costs of the links are indicated in the circled numerals. For example, the cost of the link between the ethernet bridge <NUM> and the ethernet bridge <NUM> and to is one and the cost of the link between the ethernet bridge <NUM> and the ethernet bridge <NUM> is three.

The communication system <NUM> includes a centralized software defined networking (SDN) controller <NUM> that oversees the communication system <NUM>. The SDN controller <NUM> includes (or has access to) a Br-VID space <NUM> that is implemented using memory internal to SDN controller <NUM> or external to the SDN controller <NUM>. In some embodiments, the Br-VID space <NUM> is hosted by a centralized network management server (NMS), a path computation element (PCE) server, and the like. The SDN controller <NUM> assigns or allocates network-wide unique identifiers (Br-VID) to the ethernet bridges <NUM>-<NUM>. The assignments or allocations are stored in the Br-VID space <NUM>. A first column in the Br-VID space <NUM> indicates values of the Br-VIDs and a second column in the Br-VID space <NUM> indicates the user that has been assigned or allocated the label. For example, VID1 is assigned to the ethernet bridge <NUM>, the VID2 is assigned to the ethernet bridge <NUM>, VID3 is assigned to the ethernet bridge <NUM>, and VID4 is assigned to the ethernet bridge <NUM>. Assigning or allocating the Br-VID to the ethernet bridges <NUM>-<NUM> includes providing the Br-VIDs from the SDN controller <NUM> to the corresponding ethernet bridges <NUM>-<NUM>.

In the illustrated embodiment, the Br-VID space <NUM> used for the bridge identifier does not collide with VIDs used for VLAN based partitioning of network segments, as the former is not encoded into the packet as VLAN tag, rather encoded within RRE. Using the VID as bridge identifier provides more compact encoding of RRE since size of a VID is <NUM> bits. In the RRE, each Br-VID padded with <NUM>-bits so that Br-VID always maintains byte wise alignment. Size of Br-VID plus padding is 2B. For example, if a maximum number of hops a packet would traverse in an ethernet network is <NUM> hops, then a maximum size of RRE would be 10x 2B = 20B which is <NUM>% reduction from the size when bridge identifier is encoded as MAC address (size of MAC address is 6B). However, Br-VID based encoding imposes maximum number of bridges in the network to <NUM>, which is much higher than practical sizes of networks.

<FIG> is a flow diagram of a method <NUM> of configuring Br-VIDs that are allocated from a Br-VID space according to some embodiments. The method <NUM> is implemented in some embodiments of the communication system <NUM> shown in <FIG>, the communication system <NUM> shown in <FIG>, and the communication system <NUM> shown in <FIG>. Some embodiments of the method <NUM> are implemented in a controller such as the SDN controller <NUM> shown in <FIG>.

The method <NUM> begins at the block <NUM>. At the block <NUM>, the controller retrieves the identity of the first ethernet bridge. At decision block <NUM>, the controller determines whether the Br-VID space includes one or more free Br-VIDs, e.g., Br-VIDs that are unallocated or unassigned in any context. If the Br-VID space includes at least one free Br-VID, the method <NUM> flows to block <NUM>. If the Br-VID space does not include any free Br-VIDs because the Br-VIDs have all been assigned to other routers, the method <NUM> flows to block <NUM>.

At block <NUM>, the controller allocates (or assigns) a Br-VID from the Br-VID space to the current ethernet bridge. At block <NUM>, the controller transmits one or more messages to the current ethernet bridge including information that the current ethernet bridge uses to configure the Br-VID as its Br-VID. In response to receiving the message, the current ethernet bridge configures itself to use the received Br-VID, e.g., by storing the Br-VID in a local memory or database. The method <NUM> then flows to decision block <NUM>.

At block <NUM>, the controller excludes the ethernet bridge from the network due to the exhaustion of Br-VID in the Br-VID space because assigning a previously assigned Br-VID to the current ethernet bridge would result in a non-unique Br-VID for the ethernet bridges that share the Br-VID. The method <NUM> then flows to decision block <NUM>.

At decision block <NUM>, the controller determines whether there are more ethernet bridges that need to be allocated or assigned Br-VID. If so, the method <NUM> flows to block <NUM> and the controller retrieves the identity of another ethernet bridge, which becomes the current ethernet bridge for the controller. The method <NUM> then flows to decision block <NUM>. If there are no more ethernet bridges that require allocation or assignment of Br-VID in the network, the method <NUM> flows to block <NUM> and the method <NUM> ends.

<FIG> is a flow diagram of a method <NUM> of configuring an ethernet bridge with a Br-VID provided by a controller according to some embodiments. The method <NUM> is implemented in some embodiments of the communication system <NUM> shown in <FIG>, the communication system <NUM> shown in <FIG>, and the communication system <NUM> shown in <FIG>.

The method <NUM> begins at block <NUM>. At the input block <NUM>, the ethernet bridge receives the Br-VID provided by the controller. At block <NUM>, the ethernet bridge records the input Br-VID as the network-wide unique identifier assigned to the ethernet bridge. In some embodiments, the ethernet bridge stores the Br-VID in a memory or database implemented in the ethernet bridge. At block <NUM>, the ethernet bridge programs the Br-VID into the forwarding plane so that the forwarding plane refers to the Br-VID when originating an RRE (e.g., when the ethernet bridge is an ingress ethernet bridge for an ethernet packet) or processing received packets that include an RRE. The method <NUM> ends at block <NUM>.

<FIG> illustrates a format of an RRE <NUM> according to some embodiments. The fields in the RRE <NUM> are as follows:.

<FIG> illustrates a MAC address used as a bridge identifier <NUM> according to some embodiments. In the illustrated embodiment, the list of bridge identifiers is used when the TPID is 0xB000. Each bridge identifier is a <NUM>-octet MAC address.

<FIG> illustrates a list <NUM> of bridge identifiers when TPID is 0xB001 according to some embodiments. Each bridge identifier is a <NUM>-octets unit with the following fields:.

<FIG> is a block diagram illustrating a process <NUM> of addition of an RRE to an ethernet header according to some embodiments. Adding the RRE to the ethernet header is performed by some embodiments of the communication system <NUM> shown in <FIG>, the communication system <NUM> shown in <FIG>, and the communication system <NUM> shown in <FIG>. In the illustrated embodiment, the packet including the ethernet header is in untagged packet.

Initially, an ethernet header <NUM> includes a preamble <NUM>, a destination MAC address <NUM>, a source MAC address <NUM>, an Ethertype or size indicator <NUM>, a payload <NUM>, a cyclic redundancy check (CRC) <NUM>, and an interframe gap <NUM>. An RRE <NUM> is then added to the ethernet header <NUM> to form the ethernet header <NUM>. In the illustrated embodiment, the RRE <NUM> is inserted between the source MAC address <NUM> and the Ethertype/size indicator <NUM>, although other locations for the RRE <NUM> are used in other embodiments.

<FIG> is a block diagram illustrating a process <NUM> of addition of an RRE to an ethernet header in a tagged packet according to some embodiments. Adding the RRE to the ethernet header is performed by some embodiments of the communication system <NUM> shown in <FIG>, the communication system <NUM> shown in <FIG>, and the communication system <NUM> shown in <FIG>.

Initially, an ethernet header <NUM> includes a destination MAC address <NUM>, a source MAC address <NUM>, VLAN tags <NUM>-<NUM>, a length or Ethertype indicator <NUM>, a payload <NUM>, and an FCS field <NUM>. The number of VLAN tags included in the ethernet header <NUM> varies in different embodiments. An RRE <NUM> is then added to the ethernet header <NUM> to form the ethernet header <NUM>. In the illustrated embodiment, the RRE <NUM> is inserted between the source MAC address <NUM> and the VLAN tag <NUM>, although other locations for the RRE <NUM> are used in other embodiments.

If any other ethernet layer specific headers were present after the ethernet header then those headers are appended to the RRE <NUM>. For example, the VLAN stack <NUM>-<NUM> is positioned after the RRE <NUM>. Since the TPID in the RRE <NUM> takes the position of EtherType then, based on the TPID in RRE <NUM>, an ethernet bridge that is processing the packet figures out that the next header is RRE <NUM>. The ethernet bridge looks for the EtherType field at the end of RRE <NUM>. Since VLAN Type in VLAN header takes the position of Ethertype then, based on the VLAN type, the ethernet bridge figures out that a VLAN header is present. So, if RRE <NUM> is present, then the ethernet bridge that is processing the ethernet packet <NUM> looks at Ethertype field after the RRE <NUM> to determine if other ethernet specific headers are present.

<FIG> is a flow diagram of a first portion of a method <NUM> of processing an ethernet packet at an ethernet bridge according to some embodiments. The method <NUM> is implemented by the ethernet bridges in some embodiments of the communication system <NUM> shown in <FIG>, the communication system <NUM> shown in <FIG>, and the communication system <NUM> shown in <FIG>.

The method <NUM> begins at block <NUM>. At the input block <NUM>, the ethernet bridge receives an ethernet packet.

At decision block <NUM>, the router determines whether an RRE is present in the ethernet packet. If not, the method <NUM> flows to block <NUM>. If the ethernet bridge detects an RRE in the packet, the method <NUM> flows to block <NUM>.

At block <NUM>, the ethernet bridge processes the ethernet packet. In some embodiments, the ethernet bridge performs processing operations including learning the source MAC address (if required), evaluating other ethernet related headers (e.g., VLAN tags, etc.), and looking up the destination MAC address in the appropriate MAC forwarding table at the ethernet bridge. The method <NUM> then flows to the node <NUM>.

At block <NUM>, the router performs loop detection on the RRE, as discussed herein. At decision block <NUM>, the ethernet bridge determines whether a loop is detected. If so, the method <NUM> flows to the block <NUM> and the ethernet bridge (optionally) transmits a loop detection notification, as discussed herein. If the ethernet bridge is to transmit a loop detection notification, the ethernet bridge generates the loop detection notification. The method <NUM> then flows to the node <NUM>. If no loop is detected, the method <NUM> flows to the block <NUM>.

<FIG> is a flow diagram of a second portion of the method <NUM> of processing the ethernet packet at the ethernet bridge according to some embodiments. The node <NUM> connects the block <NUM> shown in <FIG> to the block <NUM> in <FIG>. The node <NUM> connects the block <NUM> shown in <FIG> to the decision block <NUM> in <FIG>.

At block <NUM>, the ethernet bridge drops the packet. The method <NUM> then flows to block <NUM> and the method <NUM> ends.

At decision block <NUM>, the ethernet bridge determines whether the forwarding state indicates that the ethernet bridge is the egress bridge for the ethernet packet. If the ethernet bridge is not the egress bridge, the method <NUM> flows to the block <NUM>. If the ethernet bridge is the egress bridge, the method <NUM> flows to the block <NUM>.

At block <NUM>, the ethernet bridge forwards the packet to the next top link on the path to the destination. The method <NUM> then flows to the block <NUM> and the method <NUM> ends.

At block <NUM>, the ethernet bridge pops the RRE (if present) and the incoming ethernet header. At block <NUM>, the ethernet bridge processes the packet based on the underlying headers. In some embodiments, the ethernet bridge processes the ethernet packet based on underlying headers determined by an Etype at the end of the ethernet related headers. The method <NUM> then flows to the block <NUM> and the method <NUM> ends.

<FIG> is a flow diagram of a first portion of a method <NUM> of performing loop detection at an ethernet bridge according to some embodiments. The method <NUM> is implemented by the ethernet bridges in some embodiments of the communication system <NUM> shown in <FIG>, the communication system <NUM> shown in <FIG>, and the communication system <NUM> shown in <FIG>. Some embodiments of the method <NUM> are used to implement the block <NUM> shown in <FIG>.

The method <NUM> begins at block <NUM>. At the input block <NUM>, the ethernet bridge accesses an RRE that was present in an ethernet packet received at the ethernet bridge.

At block <NUM>, the ethernet bridge computes the total number of bridge identifiers in the RRE and stores in a local variable Num_Bridge_IDs. For example, if the TPID in RRE is 0xB000, the bridge identifier is encoded as a <NUM>-octet MAC address and the number of bridge identifiers is (Value of Length field in RRE/<NUM>). If the TPID in RRE is 0xB001, the bridge identifier is encoded as <NUM>-bit Br-VID, and the number of bridge identifiers is (Value of Length field in RRE x <NUM>)/<NUM>.

At block <NUM>, the ethernet bridge reads the first bridge identifier from the RRE. At block <NUM>, the ethernet bridge decrements the value of the number bridge identifiers. In the illustrated embodiment, the ethernet bridge decrements Num_Bridge_IDs by one in response to one entry being read at the block <NUM>. Thus, the value of Num_Bridge_IDs indicates how many bridge identifiers are left in the RRE that have not yet been compared to the locally configured bridge identifier that uniquely identifies the ethernet bridge. At block <NUM>, the next bridge identifier in the RRE is read, e.g., in response to determining that the number of bridge identifiers (Num_Bridge_IDs) left to examine is greater than zero at block <NUM> in <FIG>. The method <NUM> then flows to the node <NUM>.

<FIG> is a flow diagram of a second portion of the method <NUM> of performing loop detection at the ethernet bridge according to some embodiments. The node <NUM> connects the block <NUM> shown in <FIG> to the decision block <NUM> in <FIG>.

At decision block <NUM>, the ethernet bridge compares if the bridge identifier is equivalent to the bridge identifier configured locally on the ethernet bridge to identify the ethernet bridge. If the bridge identifier is equivalent to the locally configured bridge identifier, the method is <NUM> flows to the block <NUM> and the ethernet bridge declares that a loop has been detected. The method <NUM> then flows to the block <NUM> and the method <NUM> ends. If the bridge identifier is not equivalent to the locally configured bridge identifier, the method <NUM> flows to the decision block <NUM> and the ethernet bridge determines whether there are additional bridge identifiers to examine, e.g., the number of bridge identifiers (Num_Bridge_IDs) is greater than zero. If so, the method <NUM> flows to the block <NUM> in <FIG> via the node <NUM>. If there are no additional bridge identifiers to compare to the locally configured bridge identifier, the method <NUM> flows to the block <NUM> and the method <NUM> ends.

<FIG> is a flow diagram of a method <NUM> of forwarding an ethernet packet to the next hop link according to some embodiments. The method <NUM> is implemented by the ethernet bridges in some embodiments of the communication system <NUM> shown in <FIG>, the communication system <NUM> shown in <FIG>, and the communication system <NUM> shown in <FIG>. Some embodiments of the method <NUM> are used to implement the block <NUM> shown in <FIG>.

The method <NUM> begins at block <NUM>. At the input block <NUM>, the ethernet bridge accesses an ethernet packet received at the ethernet bridge and information indicating a next hop link for the packet.

At decision block <NUM>, the ethernet bridge determines whether loop detection is enabled on the next hop link. If so, the method <NUM> flows to the decision block <NUM>. If loop detection is not enabled on the next hop link, the method <NUM> flows to decision block <NUM>.

At decision block <NUM>, the ethernet bridge determines whether an RRE is present in the ethernet packet. If not, the method <NUM> flows to the block <NUM> and the ethernet bridge inserts an empty RRE into the ethernet packet because loop detection is enabled on the next hop link and an RRE was absent from the ethernet packet. The method <NUM> then flows to the block <NUM>. If an RRE is present in the ethernet packet, the method <NUM> flows to the block <NUM>.

At block <NUM>, the ethernet bridge pushes the local bridge identifier onto the RRE in the ethernet packet. At block <NUM>, the ethernet bridge increments the value of the length field in the RRE by the size of the bridge identifier that was pushed onto the RRE. The method <NUM> then flows to the block <NUM>.

At decision block <NUM>, the ethernet bridge determines whether an RRE is present in the ethernet packet. If so, the method <NUM> flows to the block <NUM> and the ethernet bridge removes the RRE from the packet because loop detection is not enabled on the next hop link. The method <NUM> then flows to the block <NUM>. If there is no RRE present in the ethernet packet, the method <NUM> flows to the block <NUM>.

At block <NUM>, the ethernet bridge transmits the ethernet packet on the next hop link. The method <NUM> then flows to the block <NUM> and the method <NUM> ends.

<FIG> is a flow diagram of a method <NUM> of generating and transmitting a loop detection notification according to some embodiments. The method <NUM> is implemented by the ethernet bridges in some embodiments of the communication system <NUM> shown in <FIG>, the communication system <NUM> shown in <FIG>, and the communication system <NUM> shown in <FIG>. Some embodiments of the method <NUM> are used to implement the block <NUM> shown in <FIG>.

The method <NUM> begins at block <NUM>. At the input block <NUM>, the ethernet bridge accesses an ethernet packet that included the RRE used to detect a loop.

At block <NUM>, the ethernet bridge retrieves a first condition for notification of the loop. At decision block <NUM>, the ethernet bridge determines whether the condition is met (e.g., the condition is true) by the input packet. If so, the method <NUM> flows to the block <NUM>. If not, the method <NUM> flows to the decision block <NUM>.

At block <NUM>, the ethernet bridge generates a copy of the ethernet packet and encodes the loop information into the packet. Some embodiments of the loop information include a copy of the RRE from the ethernet packet. At block <NUM>, the ethernet bridge notifies the copy of the ethernet packet to a reporting entity associated with the condition. The method <NUM> then flows to the decision block <NUM>.

At decision block <NUM>, the ethernet bridge determines whether there are more conditions to check for notification of the loop. If so, the method <NUM> flows to the block <NUM> and the ethernet bridge retrieves the next condition for notification of the loop. The method <NUM> then flows to decision block <NUM>. If the ethernet bridge determines that there are no more conditions to check for notification of the loop, the method <NUM> flows to the block <NUM> and the method <NUM> ends.

<FIG> is a flow diagram of a method <NUM> of generating a copy of an ethernet packet for loop notification according to some embodiments. The method <NUM> is implemented by the ethernet bridges in some embodiments of the communication system <NUM> shown in <FIG>, the communication system <NUM> shown in <FIG>, and the communication system <NUM> shown in <FIG>. Some embodiments of the method <NUM> are used to implement the block <NUM> shown in <FIG>.

At block <NUM>, the ethernet bridge makes a copy of the ethernet packet. At the block <NUM>, the ethernet bridge pushes the local bridge identifier onto the RRE in the copy of the packet. At the block <NUM>, the ethernet bridge increments the length field in the RRE of the ethernet packet by the size of the local bridge identifier. The method <NUM> then flows to the block <NUM> and the method <NUM> ends.

<FIG> is a flow diagram of a method <NUM> of loop notification to a notification server and a sender of an operations, administration, and maintenance (OAM) packet according to some embodiments. The method <NUM> is implemented by the ethernet bridges in some embodiments of the communication system <NUM> shown in <FIG>, the communication system <NUM> shown in <FIG>, and the communication system <NUM> shown in <FIG>. Some embodiments of the method <NUM> are used to implement the method <NUM> shown in <FIG>.

The method <NUM> implements two conditions for notification of the loop:.

At decision block <NUM>, the ethernet bridge determines whether the ethernet bridge is configured to notify loops to a reporting server. If the server is available, the method <NUM> flows to the block <NUM>. If the server is not available, the method <NUM> flows to the decision block <NUM>.

At block <NUM>, the ethernet bridge makes a copy of the ethernet packet and encodes loop information to the packet, as discussed herein. At block <NUM>, the ethernet bridge transmits the copy of the packet to the reporting server with a notification indicating "loop detected" on the packet. In some embodiments, the ethernet bridge implements a custom protocol between the bridge and the server to perform the notification. The method <NUM> then flows to the decision block <NUM>.

At decision block <NUM>, the ethernet bridge determines whether the input ethernet packet is a test packet or an OAM packet. For example, an OAM packet could be a connectivity fault management (CFM) packet. If so, the method <NUM> flows to the block <NUM>. If not, the method <NUM> flows to the block <NUM> and the method <NUM> ends.

At block <NUM>, the ethernet bridge makes a copy of the packet and encodes the loop information in the packet. At block <NUM>, the ethernet bridge transmits a reply to the sender of the test or OAM packet. In some embodiments, the reply includes headers from the copy of the packet. The reply is transmitted with a notification indicating "loop detected. " In some embodiments, the CFM protocol is modified to support loop notifications generated by the ethernet bridge.

Such storage media can include, but is not limited to, optical media (e.g., compact disc (CD), digital versatile disc (DVD), Blu-Ray disc), magnetic media (e.g., floppy disc , magnetic tape, or magnetic hard drive), volatile memory (e.g., random access memory (RAM) or cache), non-volatile memory (e.g., read-only memory (ROM) or Flash memory), or microelectromechanical systems (MEMS)-based storage media.

Claim 1:
An apparatus comprising:
at least one processor (<NUM>); and
at least one memory (<NUM>) including computer program code;
the apparatus, by means of the at least one processor (<NUM>) and the at least one memory (<NUM>) including computer program code, being configured at least to:
store a first identifier that uniquely identifies the apparatus within a network (<NUM>);
receive a first data link layer packet, wherein the first data link layer packet is an ethernet data packet transmitted in the forwarding plane and including an ethernet header and a payload;
forward the first data link layer packet, if a first recorded route for ethernet, RRE, included in the ethernet header in the first data link layer packet does not include the first identifier; and
drop the first data link layer packet in response to the first identifier being in the first data link layer packet.