Provider link state bridging

Provider Link State Bridging (PLSB) is a proposal brought by Nortel to the IEEE 802.1aq Shortest Path Bridging Working Group. It combines IEEE 802.1ah MACinMAC, the IS-IS routing protocol, and the techniques of filtering database (FDB) population specified by IEEE 802.1Qay Provider Backbone Bridge Traffic Engineering to produce a link state based spanning tree replacement for 802.1ah based upon shortest path trees and reverse path forwarding for multicast. It is complementary to 802.1Qay in that PLSB forwarding delivers virtualized broadcast LAN segments, while 802.1Qay provides complete route freedom for point-to-point connections, and both may co-exist on a single platform.

Principles of Operation

PLSB uses Ethernet forwarding to construct the MEF 6.1 service set (ELINE, ELAN and ETREE) . PLSB carries forward the PBB paradigm of mapping I-Component (per service) flooding and learning to B-component (backbone) multicast MAC forwarding. This greatly enhances the scalability beyond the IEEE 802.1ad (QinQ) limit of 4094 services to a theoretical limit of 2²⁴ services. A difference between PBB and PLSB is that the 802.1ah multicast MAC address is a (*, G) address common to the entire I-SID (due to the split horizon forwarding nature of a spanning tree), while the 802.1aq multicast MAC address must also encode the root of the shortest path tree. So a 4 site ELAN service will require 4 unique multicast B-MAC (S, G) addresses.

PLSB is dependent exclusively on IS-IS information exchange and computation to set up both unicast and per-service multicast meshing of backbone edge bridges. IS-IS is augmented to distribute I-SID (802.1ah I-component service ID) registrations and nodal nicknames. These two tokens of information are used to algorithmically construct root and service specific multicast MAC addresses.

The extensions to normal IS-IS procedures which lie at the heart of PLSB are best appreciated by describing what happens when a node receives an IS-IS link state packet:

1. If the packet advertises a topology change, the node first computes the shortest path tree from itself to the other nodes in the network and installs the unicast B-component MAC addresses accordingly
2. When the distance to another node in the network is determined to have changed, multicast state for the (S, G) trees rooted on that node is removed from the FDB.
3. Upon completion of steps 1 and 2 the node advertises a digest of the link state database to its immediate peers, to inform them that invalid multicast state has been removed (in step 2), and to allow them to determine whether their link state database is synchronized.
4. It performs additional shortest path computations to determine for which node pairs in the network it is on the shortest transit path between each pair,
5. It compares I-SID registrations on the shortest transit node pairs in the IS-IS database, and determines the multicast MAC addresses that should be populated in the FDB.
6. When it has completed determining the updated FDB it then awaits receipt of a digest from its neighbors indicating IS-IS database synchronization and removal of their invalid multicast state before installing the multicast updates.

This may appear complex, but it reflects construction of complete unicast and per-service multicast connectivity with loop avoidance using only the exchange of the IS-IS LSPs, and the link state database digests, which needs many orders of magnitude less transactions than for traditional multicast protocols using inter-nodal messaging. This is predicated on the notion that raw computation power available in the current generation of technology has far outstripped message processing capability, at least partially due to the overhead of repeated context swaps associated with message handling.

It is also important to observe the degree of parallelism which has been achieved in that the initial two steps leading to the advertising of a digest can be accomplished significantly faster than the subsequent computation of multicast trees, so a node should rarely need to actually wait at step 6.

A required component of the above algorithms is a distributed tie breaking algorithm The proposed algorithm uses the ranking of a lexographically ordered list of nodal system IDs. This approach has a number of desirable properties:

1. Any portion of the shortest path is also itself a shortest path, which means tie breaking can be resolved at intermediate steps, and the amount of state carried forward by the algorithm is minimized.
2. The bookends of the ranking tend to maximize path diversity, and so are useful for load spreading purposes. Each can be instantiated as a B-VID, and edge based load assignment employed.

Backwards Compatibility

The connectivity instantiated by PLSB is backward compatible with Ethernet in a number of ways:

1. It delivers symmetric congruence of unicast and multicast, such that both the unicast and the multicast forwarding between any two points in the network follows the same path in both directions. This has a number of benefits:
   • it allows a per-packet reverse path forwarding check to be applied on ingress to every node, which, in conjunction with the link state database synchronization (above), guarantees loop-free paths even under transients induced by topology changes
   • minimal possibility of re-ordering of flows due to race conditions between multicast flooding and subsequent unicast forwarding as a consequence of learning
   • proper fate sharing of I-component, B-component and client IEEE 802.1ag OAM with the actual connectivity
2. Sharing of all other attributes such that it can be run side by side with STP based PBB and/or PBB-TE. Similar to PBB-TE, it will simply have a reserved MSTI ID with an associated set of VLANs specified as using PLSB forwarding behaviour.

PLSB is not necessarily backwards compatible when a peer interworking function is required; in order to peer interwork between PBB and PLSB, these steps are needed :

1. Construction of the I-SID specific multicast addresses. The OUI field and "local" bit would require modification by any IWF.
2. Multiple Registration Protocol registration PDUs from PBB would need to be terminated at any IWF and advertised in IS-IS, because MMRP runs over a spanning tree, not shortest path trees.

Scalability

A design objective of the 802.1aq effort for shortest path backbone bridging is 1000 nodes. This appears to be achievable with acceptable resilience performance based upon numbers presented to the IEEE.

The actual identifier limits in the current protocol definitions are as follows:

I-component IDs (services): 2²⁴

B-VIDs (unique SPF topologies): 2¹² although it is envisioned that no more than a very Small number (2 – 4) will ever be needed

Nodal Nicknames (802.1aq limit): 2²⁰ (only one per PLSB node is required !)

MEP IDs (802.1ag limitation): 2¹³

History

PLSB was first proposed to the 802.1aq WG in early 2007. It has progressed since and is expected to enter sponsor ballot in 2010.

See Also

• Connection-oriented Ethernet
• Provider Backbone Bridges
• IEEE 802.1

External Links

• IEEE 802.1aq project page
• "New Innovations in Ethernet: Provider Link State Bridging", Nortel Technical Journal, Issue 6, January 2008
• "Provider Link State Bridging", IEEE Communications Magazine, volume 46, number 9. September 2008