IDR Working Group S. Hares Internet-Draft NextHop Technologies Expires: April 20, 2006 October 17, 2005 Multicast Link State For Rbidges draft-hares-trill-multicast-00.txt Status of this Memo By submitting this Internet-Draft, each author represents that any applicable patent or other IPR claims of which he or she is aware have been or will be disclosed, and any of which he or she becomes aware will be disclosed, in accordance with Section 6 of BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet- Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt. The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. This Internet-Draft will expire on April 20, 2006. Copyright Notice Copyright (C) The Internet Society (2005). Abstract Rbridges are transparent Layer 2 bridges that provide the ability to have an entire campus, with multiple physical links look like a single subnet. The Rbridge technology utilizes Rbridges to link together Layer 2 areas using spanning trees to calculate paths. The Rbridges run a link state protocol to determine the least cost paths Rbridges and exchange information about the location of MAC addresses. The Rbridges will run a level 1 or a single area routing protocol. To forward multicast packets, the Rbirdges may treat these as broadcast (sending the packets to all Rbridges) or use methods to Hares Expires April 20, 2006 [Page 1] Internet-Draft TRILL-Multicast-LS October 2005 snoop the Multicast MAC addresses (GARP, MAC learning) or IP/MAC address packets (IGMP/PIM snooping). Multicast Link State Rbridge connections suggest a Hybrid Multicast Link state extensions to ISIS and OSPF for Rbridges. Table of Contents 1. Definitions . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1. Conventions used in this document . . . . . . . . . . . . 3 2. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 3. Multicast Algorithms . . . . . . . . . . . . . . . . . . . . . 7 3.1. Forwarding Database for Rbridges . . . . . . . . . . . . . 7 3.1.1. Output: Forwarding Database for Rbridges . . . . . . . 9 3.2. S,G Multicast Tree Calculation rooted at S MAC . . . . . . 10 3.3. S,G Multicast Tree Calculation to all G-Group MACs . . . . 12 3.4. Reduced Flooding Trees for all Rbridges supporting multicast . . . . . . . . . . . . . . . . . . . . . . . . 13 4. Multicast Rbridge Cross Algorithm Aids . . . . . . . . . . . . 15 5. Multicast Rbridge TLV formats . . . . . . . . . . . . . . . . 16 6. Security Considerations . . . . . . . . . . . . . . . . . . . 17 7. References . . . . . . . . . . . . . . . . . . . . . . . . . . 17 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 18 Intellectual Property and Copyright Statements . . . . . . . . . . 19 Hares Expires April 20, 2006 [Page 2] Internet-Draft TRILL-Multicast-LS October 2005 1. Definitions 1.1. Conventions used in this document The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 [1]. Hares Expires April 20, 2006 [Page 3] Internet-Draft TRILL-Multicast-LS October 2005 2. Introduction Rbridges are transparent Layer 2 bridges that provide the ability to have an entire campus, with multiple physical links look like a single subnet. The Rbridge technology utilizes Rbridges to link together Layer 2 areas using spanning trees to calculate paths. The Rbridges run a link state protocol to determine the least cost paths Rbridges and exchange information about the location of MAC addresses. Rbridges calculate one spanning tree and distables the use of equal cost links by utilizing the ID of the parent as the tie breaker. Rbridges are described in RBRIDGE [2]. Tie breaking is described in section 2.2 (Spanning Tree). The Rbridges will run a level 1 or a single area routing protocol. The Rbridge specification RBRIDGE [2] suggests that the protocol be IS-IS due ease of adding TLVS and the NET ID (6 bytes) that identifies the node. While ISIS may be easier, it is still possible to OSPF to pass information given more modifications to OSPF. To forward multicast packets, the Rbridges may treat these as broadcast (sending the packets to all Rbridges) or use methods to snoop the Multicast MAC addresses (GARP GMRP or MAC learning) or IP/ MAC address packets (IGMP/PIM snooping), or ARP/ND replies. The Rbridge must support multiple VLANs and traffic engineering to support Layer 2 forwarding based on traffic engineered paths (802.11e, 802.1 P bit and Q bits). These constraints placed on the routing calculations for the Rbridge are exactly the constraints placed on two previous protocols: MOSPF and 802.11s Wireless mesh. This document suggests a Hybrid Link State Rbridge Protocol based on the work for 802.11s Wireless Mesh that is in turned based on the earlier work in MOSPF. MOSPF RFC 1584 [3].created source based trees rooted at the datagram source. The MOSPF routers collected information about requests for nodes to receive multicast group traffice. The MOSPF protocol calculated the shortest path from the source to the destinations. MOSPF did not support Equal-Cost Multi-path. It select a single link for multiast traffic, just as the Rbridge work suggests. The Hybrid Link State Protocol Wi-Mesh 802.11s Proposal: Hybrid Link State Protocol [6], part of Wi-Mesh Alliance submission for 802.11s, suggests allowing three options for the multicast trees: Hares Expires April 20, 2006 [Page 4] Internet-Draft TRILL-Multicast-LS October 2005 Tree rooted at MAC source addreses per Destination MAC address Flooding Trees based on detection of a MAC Group Address detected an an Rbrdige Reduced flooding trees to Rbridges that support Multicast Todays layer 2 bridges are often highly meshed within a campus area. Bridges may be support WLANs (802.11) or Wired LANs (802.3 or Ethernet). The reducing of flooding trees may allow needless flooding of multicast packets between Rbridges. The Reduced flooding tree methods from OSLR or OSPF MANET can be used in general multicast flooding algorithsm to reduce the cost of forwarding data. This document suggest allowing Rbridges to be able to negotiate Flooding reduction algorithms as well as Traffic Engineering paths. A reduced flooding algorithm may be useful for two reason The Layer 2 LANs supported by TRILL will include both wired and wireless physical media. In the wireless media, the bridges broadcast may reach several This document will cover the three multicast algorithms: 1. Forwarding Pathways results that Multicast Link State for Rbridges must creat 2. Tree Calculations Rooted at Rbridge report (Source MAC, Group MAC) state 3. Tree Calculations Rooted at Rbridge that detect sets of Sources addresses sending to Group MAC Address or receiving traffic for Group MAC Addresses 4. Reduced Fooding Trees to Rbridge that simply request to support Multicast for a VLAN or for a TE/VLAN pairing In each of these section will provide basic algorithms, TLV suggestions and a sample topology. This document will also cover mechanism in a different section that span across multiple multicast algorithms. 1. Alternative Tie-Breakers for spanning tree passed as part of Rbridge to Rbridge Link attribute 2. Used of Logical Link Bundling to support multiple links Hares Expires April 20, 2006 [Page 5] Internet-Draft TRILL-Multicast-LS October 2005 3. Negotiating of reduced flooding algorithms between Rbridges. 4. Database issues Hares Expires April 20, 2006 [Page 6] Internet-Draft TRILL-Multicast-LS October 2005 3. Multicast Algorithms Rbridges must learn about Multicast pathways request by learning about frames destined to a Group MAC address from a Source MAC address. The Rbridges must create a forwarding database structure to support forwarding behavior required by the Rbridge. Section 4.1 contains information about the Forwarding path for Rbridges. The next three section contain information about the multicast tree calculations 4.2- Tree rooted at MAC source addreses per Destination MAC address 4.3 - Flooding Trees based on detection of a MAC Group Address detected an an Rbrdige 4.4 - Reduced flooding trees to Rbridges that support Multicast 3.1. Forwarding Database for Rbridges The Rbridge RBRIDGE [2] contains information on Forwarding Behavior and Forwarding headers The first step to defining how a Multicast algorithsm can work to support Multicast pathways through Rbridges is by defining the inputs and outputs. The inputs are: 1. Rbridge topology - Bridges, Links and Designate Rbridges 2. Source-Group (S,G) MAC address pairs associated per Rbridge 3. (*,G) MAC pairs associated per Rbridge 4. IP Multicast (S,G) to (S,G) mappings 5. Single Path Selection weights The outputs are: 1. Destination Multicast MAC to Rbridge(s) mapping 2. Source Code MAC to Rbridge mapping 3. Encapsulation Table for traffic Destined for Rbridge 4. Forwarding Table for Encapsulated traffic to Rbridge(s) Hares Expires April 20, 2006 [Page 7] Internet-Draft TRILL-Multicast-LS October 2005 Rbridge Topolology The Rbridge topology borrows from the ISIS router topology for Bridges but must be extended to support: 1. Hello information to indicated Flags for support Router has. In a similar manner, the ISIS hello must be extended to indicate support for: Multicast Forwarding, Multicast Reduced Flooding algorithms Multicast Path Weights 2. Link information must include: Rbridge link Metric Traffic Engineering link metrics - both radio and wired Multicast support - broadcast, multicast by unicast replication, or other 3. Number of topology (default, VLAN Based) 4. Designated RBridge per link (S,G) MAC state: the Rbridge needs to indicate keep a table of Source MAC, Group MAC pairs associated with each Rbridge. The Destinated Ingress Rbridge will learn these pairs from the endnodes associated with the Rbridge. The Designated Rbridge will send this state in TLVs passed to other Rbridges. The ISIS flooding algorithm will be used to distribute the (S,G) MAC information. (*,G) MAC state: the Rbridge should also be able to passing Support for flooding to all Rbridges Multicast traffic from any source. The (*,G) MAC state can be used for a reduced flooding to a limited set of Rbridges. IP (S,G) Mappings to MAC (S,G): the Rbridge should keep a set of mappings from IP (S,G) to MAC (S,G) in order to aid the ARP processing. Hares Expires April 20, 2006 [Page 8] Internet-Draft TRILL-Multicast-LS October 2005 Singe Path Weights: The Tie breaker mechanisms may be tuned by allowing common single path weights per VLAN so that alternative single path calculations may be optionally used. The default tie- breaker would be required to be supported. Note: Since the Rbridge topology cannot make use of equal-cost-multi- path links, it would be good to combine the links into bundled links and utilize traffic engineer capabilities within that link. 3.1.1. Output: Forwarding Database for Rbridges Figure 1 shows sample Databases for the forwarding tables Destination Multicast MAC to Rbridge(s) mapping Source Code MAC to Rbridge mapping Encapsulation Table for traffic Destined for Rbridge Forwarding Table for Encapsulated traffic to Rbridge(s) The Multicast Algorithms need to take the input and create the forwarding state per VLAN, per Traffic-Engineering layer 2 overlayin. Hares Expires April 20, 2006 [Page 9] Internet-Draft TRILL-Multicast-LS October 2005 Destination MAC Table ========================================================== Destination MAC RBridge List ------------------ ------------------------------- Group MAC-1 Rbridge-x, Rbridge-y, Rbridge-z Group MAC-2 Rbridge-w, Rbridge-z ... Group MAC-n Rbridge-z, Rbridge-y Source MAC Table ============================================================ Source MAC Rbridge ---------------- ------------- MAC-1 Rbridge-x MAC-10 Rbridge-z Encapsulation Table ================================================================== Source MAC Destination MAC Egress Encapsulation Rbridges Group MAC Unicast MAC ---------- --------------- --------- ----------- ----------- MAC-1 Group-MAC 1 Rbridge-x, Group-MAC-3 [none] Rbridge-y, Rbridge-z MAC-10 Group-MAC-n Rbridge-z, MAC-5 Rbridge-y [none] Forwarding of Encapsulations Unicast Encap MAC Next Rbridge ----------------- --------------- MAC-5 Rbridge-a Multicast Encap MAC Next Rbridges --------------------- -------------------------- Group-MAC-3 Rbridge-a, Rbridge-C Figure 1: Destinatino MAC to Rbridge mapping 3.2. S,G Multicast Tree Calculation rooted at S MAC The mechanism has three parts: Hares Expires April 20, 2006 [Page 10] Internet-Draft TRILL-Multicast-LS October 2005 1. Flooding Information via Link State 2. Sorting (S,G,Rbridge) into S-[G-sets,Rbridges-set] 3. Calculating a multicast forwarding tree based in the source for S-[G-Sets,Rbridge 1. The Flooding of information via the link state should include the following information about MAC Addresses: TLV sent from originating Rbridge ===================================== TLV1: Source MAC address ------------------------------------- Source MAC Address IDentifier Count of Unicast Source MAC Addresses Source MAC 1 [Flag Add/Delete, Encrypted/None] Source MAC 2 Source MAC n [count of Group MACs associated with Source set] [MAC Group Identifier - number] TLV2: Group MAC set --------------------------- Count of Multicast MAC addresses Group MAC Address-1 [6 bytes][ Flag byte -Add/Delete, Encrypt/None] Group MAC Address-2 ... Group MAC Address -n [count of Groups of Source MAC adddresses Associted with Group] [Source MAC Identifiers] Figure 2: TLVs for MAC flooding 2. Sorting (S,G,Rbridge) into [S, G-Sets] [G-sets,Rbridges-set] This part of the calculation tries to reduce the (S,G,Rbridge) source tree to all destination MAC Address and Rbridge calculations. Each Rbridge has received them mappings between (S,G,Rbridge) pairs from the above TLVs. After storing the original link state information in the ISIS LSDB, the Rbridge needs to sort information around this calculation framework: Sources going to the same Groups, a "Group-Set". For these sources, the calculation to the Groups can be summarized into a "Source- set". Hares Expires April 20, 2006 [Page 11] Internet-Draft TRILL-Multicast-LS October 2005 For each group set, the groups will be listed on a a set of Rbridges. If the multiple groups share the same group sets, the Group set can be summarized into a "Rbridge-Group-set". Map the Source Address to a Rbridge and see if any further reduction by combining Source Addresses to Rbridge can be made of the Source-Rbridge-set each with a G-Destination-Rbridge- Group-Set. The results (Source-Rbridge-set, G-Destination-Rbridge-Group- set) is passed to the next stage. 3. For each Source-Rbridge-Set calculate the spanning tree for each G-Destination-Rbridge-Group Set. Store the Resulting Entries in the forwarding state as {S-MAC, G-MAC] state. Use the Path tie entries to set the forwarding tree state to a single path. 3.3. S,G Multicast Tree Calculation to all G-Group MACs The Group MAC address calculation can be used for a smaller number of Rbridges with only some of the Rbridges supporting the Destination MAC Addresses. In this calcualtion, the source tree is calculated form each Ingress Rbridge to the Group MAC Destination learned at each Rbridge. The benefit of this calculation is that only Group MAC addresses need to be passed around and no (S,G) calculation is completed. The mechanism has three parts: 1. Flooding Information via Link State 2. Sorting the (Group-MAC-set,Rbridge> into Rbridge-(*,G)sets that share the same Group-MAC-Sets 3. Calculating a multicast forwarding tree from each Rbridge to the Rbridge-(*,G)sets 4. Updating the forwarding table with the results 1. The Flooding of information via the link state should include the following information about MAC Addresses: Hares Expires April 20, 2006 [Page 12] Internet-Draft TRILL-Multicast-LS October 2005 TLV sent from originating Rbridge ===================================== TLV2: Group MAC set --------------------------- Count of Multicast MAC addresses Group MAC Address-1 [6 bytes][ Flag byte -Add/Delete, Encrypt/None] Group MAC Address-2 ... Group MAC Address -n [count of Groups of Source MAC adddresses Associted with Group] [Source MAC Identifiers] Figure 3: Defitions for TLV for MAC flooding 2. Sort the (Group-Set,originating RBridge) into (*,G) Group sets that share the same set of Rbridges. (For example, four (*,g) group sets could be found only on Rbridges 1,2,3, and 4. The calculation for these two group sets sets can be done at the same time.) 3. For each Source-Rbridge calculate the spanning tree for each Rbridges for the (*,G) group sets. Use the path tie-break entries to set the forwarding state to 1 path. 4. Store the Resulting Entries in the forwarding state as {S-MAC, G-MAC] state. 3.4. Reduced Flooding Trees for all Rbridges supporting multicast The third algorithm for calculating multicast state is to simply calculate a more efficient broadcast flood. The MANET and OSPF MANET work has started to look at ways to reduced the Link state announcements that are sent over and over. The first step in this method is to determine what Rbridges will support Multicast forwarding. If nodes do not support multicast flooding, the nodes are cut out of the calculation tree. Reduction of flooding of multicast frames may utilize the similar methods that calculate the minimum routers that need to flood Link State Advertisements. All routers send ACKs for the information received - but the repeat ACK require less bandwidth than the data. The OLSR RFC 3626 [7] MPR sets that announced to the other routers. Hares Expires April 20, 2006 [Page 13] Internet-Draft TRILL-Multicast-LS October 2005 The OSPF manet work has two drafts: OSPF with Minimum Connected Dominating Sets (MCDS) calculated and optionally sent. draft-chandra-ospf-manet-ext [5] OSPF with MPR sets calculated and always sent draft-ogier-manet-ospf-extension-04> [4] Hares Expires April 20, 2006 [Page 14] Internet-Draft TRILL-Multicast-LS October 2005 4. Multicast Rbridge Cross Algorithm Aids This section covers algorithms that will span across multiple multicast algorithms. Alternative Tie-Break: The addition tie breaking algorithms can be: Negotiated on the ISIS Hello Passed as TLVs indicating weights to select a group leader Rbridge that will form the root of the spanning tree Logical Links: Logical links provide a natural bundling of existing links into larger calculations. The link bundling is supported by many ISIS implementations. Use of a "logical link" identifier or a L2 Logical Link ID (6 bytes) to identify the logical link bundle. Negotiating of Reduced flooding a mechanism to negotiate the flood algorithms between bridge is needed for the a non-configured selection of flooding algorithms. Hares Expires April 20, 2006 [Page 15] Internet-Draft TRILL-Multicast-LS October 2005 5. Multicast Rbridge TLV formats +--------------------------------------------------+ |Source MAC Group ID (4 octet) | +--------------------------------------------------+ | count of Unicast MAC addr (2 octet) | +--------------------------------------------------+ | Source MAC Address 1 (6 octet) | +--------------------------------------------------+ | MAC 1 Flag (Add/Delete, Encrypt/none (1 octet) | +--------------------------------------------------+ | Source MAC Address 2 (6 octets | +--------------------------------------------------+ | MAC 2 Flag (Add/Delte, Encrypt/none) (1 octet) | +--------------------------------------------------+ |............................... | +--------------------------------------------------+ | count sets of Group MACs (2 octets) | +--------------------------------------------------+ + Group set 1 Identifier (6 octest) + ---------------------------------------------------- + ................................. + ---------------------------------------------------- ---------------------------------------------------+ |Group MAC Group ID (4 octet) | +--------------------------------------------------+ | count of Group MAC addr (2 octet) | +--------------------------------------------------+ | Group MAC Address 1 (6 octet) | +--------------------------------------------------+ | MAC 1 Flag (Add/Delete, Encrypt/none (1 octet) | +--------------------------------------------------+ | Group MAC Address 2 (6 octets | +--------------------------------------------------+ | MAC 2 Flag (Add/Delte, Encrypt/none) (1 octet) | +--------------------------------------------------+ |............................... | +--------------------------------------------------+ | count sets of Source MACs (2 octets) | +--------------------------------------------------+ + Group of Source MAC set 1 Id (6 octets) + ---------------------------------------------------- + ................................. + ---------------------------------------------------- + Group of Source MAC set N ID (6 octets> + ---------------------------------------------------- Hares Expires April 20, 2006 [Page 16] Internet-Draft TRILL-Multicast-LS October 2005 6. Security Considerations The security of the Rbridge exchange depends on the factors: IS-IS protocol security Encryption of MAC traffic on a hop-by-hop basis. Wireless LANs will utilized encrypted traffic. Some wired traffic may be encrupted. This proposal does not change the security implications pre-existing in these protocols. 7. References [1] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", March 1997, . [2] ""Rbridges: Transparent Routing"", May 2005, . [3] ""Multicast Extensions to OSPF"", March 1994, . [4] ""MANET Extension of OSPF using CDS Flooding"", July 2005, . [5] ""Extensions to OSPF to Support Mobile Ad Hoc Networking"", April 2005, . [6] ""802.11 TGS MAC Enhancment Proposal - Wi-Mesh Alliance"", . [7] ""Optimized Link State Routing Protocol (OLSR)"", October 2003, . Hares Expires April 20, 2006 [Page 17] Internet-Draft TRILL-Multicast-LS October 2005 Author's Address Susan Hares NextHop Technologies 825 Victors Way Ann Arbor, MI 48105 Phone: +1-734-222-1610 Email: shares@nexthop.com Hares Expires April 20, 2006 [Page 18] Internet-Draft TRILL-Multicast-LS October 2005 Intellectual Property Statement The IETF takes no position regarding the validity or scope of any Intellectual Property Rights or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; nor does it represent that it has made any independent effort to identify any such rights. Information on the procedures with respect to rights in RFC documents can be found in BCP 78 and BCP 79. Copies of IPR disclosures made to the IETF Secretariat and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementers or users of this specification can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr. The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement this standard. Please address the information to the IETF at ietf-ipr@ietf.org. Disclaimer of Validity This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Copyright Statement Copyright (C) The Internet Society (2005). This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights. Acknowledgment Funding for the RFC Editor function is currently provided by the Internet Society. Hares Expires April 20, 2006 [Page 19]