Internet DRAFT - draft-hares-trill-multicast
draft-hares-trill-multicast
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, <ftp://ftp.isi.edu/in-notes/rfc2119>.
[2] ""Rbridges: Transparent Routing"", May 2005, <http://
www.ietf.org/internet-drafts/draft-perlman-rbridge-03.txt>.
[3] ""Multicast Extensions to OSPF"", March 1994,
<http://www.ietf.org/rfc/rfc1584.txt>.
[4] ""MANET Extension of OSPF using CDS Flooding"", July 2005, <http
://www.ietf.org/internet-drafts/
draft-ogier-manet-ospf-extension-04.txt>.
[5] ""Extensions to OSPF to Support Mobile Ad Hoc Networking"",
April 2005, <http://www.ietf.org/internet-drafts/
draft-chandra-ospf-manet-ext-03.txt>.
[6] ""802.11 TGS MAC Enhancment Proposal - Wi-Mesh Alliance"",
<http://www.ieee.org/802.11/IEEE 802.11.05/5899r4>.
[7] ""Optimized Link State Routing Protocol (OLSR)"", October 2003,
<http://www.ietf.org/rfc/rfc3626.txt>.
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]
