Provider link state bridging

• US 7,688,756 B2
• Filed: 10/02/2006
• Issued: 03/30/2010
• Est. Priority Date: 10/05/2005
• Status: Expired due to Fees

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Bragg, Nigel, Allan, David
• Primary Examiner(s): Patel, Jayanti K
• Assistant Examiner(s): CAMPBELL, MATTHEW T
• Application Number:
  US11/537,775
• Publication Number:
  US 20070086361A1
• Time in Patent Office: 1,275 Days
• Field of Search: 370/238, 370/254, 370/389, 370/398, 370/401
• US Class Current: 370/254
• CPC Class Codes: H04L 12/18 for broadcast or conference , e.g. multicast
• CPC Class Codes: H04L 12/462 LAN interconnection over a bridge based backbone
• CPC Class Codes: H04L 12/4625 Single bridge functionality, e.g. connection of two networks over a single bridge
• CPC Class Codes: H04L 12/4641 Virtual LANs, VLANs, e.g. virtual private networks [VPN] LAN interconnection over a bridge based backbone H04L12/462; encapsulation techniques H04L12/4633; routing of packets H04L45/00; packet switches H04L49/00; virtual private networks for security H04L63/0272
• CPC Class Codes: H04L 12/4675 Dynamic sharing of VLAN information amongst network nodes configuration of the network or of network elements H04L41/08
• CPC Class Codes: H04L 41/0816 the condition being an adaptation, e.g. in response to network events
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/03 by updating link state protocols
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/18 Loop-free operations
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/484 using multiple routing trees
• CPC Class Codes: H04L 45/66 Layer 2 routing, e.g. in Ethernet based MAN's
• CPC Class Codes: H04L 49/3009 Header conversion, routing tables or routing tags
• CPC Class Codes: H04L 49/354 for supporting virtual local area networks [VLAN]

Abstract

Provider Link State Bridging (PLSB) expands static configuration of Ethernet MAC forwarding tables by the control plane and utilizes direct manipulation of Ethernet forwarding by a link state routing system. At least one media-access-control (MAC) address for unicast forwarding to the bridge and at least one MAC address for multicast forwarding from the bridge are assigned. Bridges exchange state information by a link state bridging protocol so that a synchronized configured view of the network is shared between nodes. Each node can calculate shortest path connective between peer bridging nodes and populated the appropriate forwarding tables. A reverse path forwarding check is performed on incoming packets to provide loop suppression. During times of network instability the loop suppression can be disabled for unicast packets as identified by the destination MAC address to buffer packets and minimize the impact on traffic flow.

Claims

1. A provider link state bridging Ethernet node, the node comprising:

at least one associated unicast media-access-control (MAC) address;

at least one associated multicast MAC address;

a routing module for exchanging link state routing information between nodes based upon the respective unicast MAC address and a plurality of multicast MAC addresses of peer nodes and for determining shortest path connectivity between peer nodes and wherein when multiple equal cost paths are available, the selected shortest path is arranged to be consistent for all bridges participating in the routing information exchange;

a forwarding information base (FIB) populated with forwarding information received from the routing module for identifying connectivity from the node to peer bridge nodes, wherein the unicast MAC addresses point to peer nodes and the multicast address point from peer nodes;

a reverse path forwarding check (RPFC) module for inspecting incoming packets and determining whether the packets arrived on the same ingress port as would be used as an egress port, as determined by the FIB, to forward a packet with a destination MAC address equal to the ingress source MAC address; and

a forwarding module for determining, from the FIB, if an egress port of the node is associated with the destination MAC address of a peer bridge and forwarding the packet.

2. The Ethernet node of claim 1 wherein the RPFC module discards the packet if it is determined that the packet did not arrive on the correct ingress port.

3. The Ethernet node of claim 1 wherein the RPFC module is disabled for unicast traffic when the network topology and the routing module is not converged.

4. The Ethernet node of claim 3 wherein the RPFC module is periodically enabled for unicast packets to check if a persistent loop condition exists by detecting the discard of packets.

5. The Ethernet node of claim 1 wherein the forwarding module discards the packet if an egress port is not identified in the FIB for the packet destination MAC address.

6. The Ethernet node of claim 1 wherein the at least one unicast MAC addresses are assigned to one of a line card, a virtual switch instance (VSI) or IJNI port or other arbitrary naming of terminations at a bridge, or are representative of MAC terminations behind the bridge.

7. The Ethernet node of claim 1 wherein the routing module determines the shortest path by Floyd'"'"'s algorithm or Dikjstra'"'"'s algorithm.

8. The Ethernet node of claim 1 where the FIB module is populated based upon information related only to nodes in the shortest path.

9. The Ethernet node of claim 1 wherein the link state information includes community of interest information within the routing advertisements such that each bridge can determine, when it is on the shortest path between two nodes, if the two nodes have intersecting communities of interests, the bridge modifies what is populated in the forwarding tables accordingly.

10. The Ethernet node of claim 1 wherein the link state information further comprises including a plurality of virtual LAN (VLAN) identifiers wherein each identifier is used to define one instance of the mesh at the control plane.

11. The Ethernet node of claim 10 wherein the plurality of VLAN identifiers may be used to partition the network to facilitate the spreading of traffic in the mesh such that multiple equal cost paths can be utilized.

12. The Ethernet node of claim 11 wherein the routing module determines the shortest paths for each VLAN while having assigned a distinct ranking algorithm to each VLAN for tie breaking between multiple equal cost paths to load spread across a range of VLANs.

13. The Ethernet node of claim 1 wherein the link state information includes an extended service ID (I-SID) incorporated in the link state routing advertisements to identify a unique multicast group, wherein a bridge that that is on the shortest path between two bridges installs the unicast MAC address associated with each bridge, and the multicast MAC addresses for all I-SIDs common to the two bridges.

14. A method of configuring and operating a provider link state bridging Ethernet node in a mesh networks the method comprising:

exchanging link state information with peer nodes wherein each node has at least one associated unicast media-access-control (MAC) address and at least one multicast MAC address;

determining shortest paths to peer nodes by a shortest path algorithm based upon the exchanged link state information and wherein when multiple equal cost paths are available, the selected shortest path is arranged to be consistent for all bridges participating in the routing information exchange;

populating a forwarding information base (FIB) with the determined shortest paths utilizing associated unicast MAC addresses pointing to peer nodes and multicast MAC addresses pointing from peer nodes;

performing a reverse path forwarding check (RPFC), by inspecting the source MAC address of an incoming packet to determine whether the packet arrived on the same ingress port of the node as would be used as an egress port of the node to forward a packet with a destination MAC address equal to the ingress source MAC address, wherein the packet is discarded if the RPFC fails; and

forwarding the packet to a peer bridge, if the RPFC is successful, via an egress port of the node associated with the destination MAC of the packet as identified in the FIB.

15. The method of claim 14 wherein the step of performing the RPFC is selectively bypassed for unicast traffic when the network topology and therefore routing module is not converged.

16. The method of claim 14 wherein the step of determining shortest paths utilizes a Floyd'"'"'s algorithm or Dikjstra'"'"'s algorithm.

17. The method of claim 16 wherein the shortest path algorithm further includes a measure of cost selected from a group comprising capacity, speed, usage and availability net of other applications using the network.

18. The method of claim 14 wherein the routing module utilizes common metrics for unicast and multicast connectivity such that there is congruency of forwarding between packets of either type.

19. The method of claim 14 wherein the step of populating the FIB is only based upon information related only to nodes in the shortest path.

20. The method of claim 14 wherein the packet is the MAC-in-MAC encapsulation is as per 802.1ah.

21. The method of claim 14 wherein the step of exchanging link state information further comprises including community of interest information within the routing advertisements such that each bridge can determine, when it is on the shortest path between two nodes, if the two nodes have intersecting communities of interests, the bridge modifies what is populated in the forwarding tables accordingly.

22. The method of claim 14 wherein the step of exchanging link state information further comprises including a plurality of virtual LAN (VLAN) identifiers, wherein each identifier is used to define one instance of the mesh at the control plane.

23. The method of claim 22 wherein the plurality of VLAN identifiers may be used to partition the network to facilitate the spreading of traffic in the mesh such that multiple equal cost paths can be utilized.

24. The method of claim 23 wherein the step of determining the shortest paths is repeated for each VLAN while having assigned a distinct ranking algorithm to each VLAN for tie breaking between multiple equal cost paths to load spread across a range of VLANs.

25. The method of claim 14 wherein the step of exchanging link state information further comprises including an extended service ID (I-SID) incorporated in the link state routing advertisements to identify a unique multicast group, wherein a bridge that that is on the shortest path between two bridges installs the unicast MAC address associated with each bridge, and the multicast MAC addresses for all 1-SIDs common to the two bridges.

26. The method of claim 14 wherein the step of exchanging link state information further comprises providing asymmetrical VPN connectivity by adding attributes to the link state advertisement indicating desire of the bridge to be a source, a sink or both a source and sink for a given multicast group, the bridge establishing that it is on the shortest path between two other bridges using the source/sink attributes to determine which multicast group addresses should be installed.

27. An Ethernet bridging network comprising:

a plurality of bridges each having a forwarding information base (FIB) containing forwarding information for peer bridges in the network, each bridge capable of performing a reverse path forwarding check (RPFC) to determine if an incoming packet arrived on the same ingress port of the bridge as would be used as an egress port of the bridge to forward a packet with a destination MAC address equal to the incoming packet'"'"'s source MAC address,

a plurality of paths interconnecting the bridges and forming the network; and

wherein the FIB is populated based upon link state information exchanged between the plurality of bridges and is used to determine the shortest path between peer bridges, wherein the determination of the chosen paths when multiple equal cost paths are available is arranged to be consistent for peer bridges; and

wherein one or more bridges has at least one associated unicast media-access-control (MAC) address and at least one associated multicast MAC address, which are utilized in populating the FIB of each peer bridge.

28. The bridging network of claim 27 wherein the RPFC is selectively disabled for unicast packets as identified by the destination address of the packet and enabled for multicast packets when the network topology is not converged between bridges.

29. The bridging network of claim 27 wherein subset of bridges form individual provider link state bridging (PLSB) domains which can be interconnected via a MAC identifying peer PLSB domains.

30. The bridging network of claim 27 wherein Provider Backbone Transport (PBT) networks can be interconnected with edge bridges of the bridging network via a PBT MAC identifiers.

31. The bridging network of claim 27 where provider 802.1ah Provider Backbone Bridging is overlaid on the bridging network.

32. The bridging network of claim 27 wherein a connectivity policy mechanism is constructed by utilizing one of the plurality of bridges as a leaf on a multipoint-to-point (mp2p) unicast tree to each peer bridge, and a root of an (S, G) point-to-multipoint (p2mp) multicast tree to a respective set of peer nodes for each community of interest.