idnits 2.17.1 draft-ietf-mospf-mospf-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Cannot find the required boilerplate sections (Copyright, IPR, etc.) in this document. Expected boilerplate is as follows today (2024-04-25) according to https://trustee.ietf.org/license-info : IETF Trust Legal Provisions of 28-dec-2009, Section 6.a: This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 2: Copyright (c) 2024 IETF Trust and the persons identified as the document authors. All rights reserved. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 3: This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** Missing expiration date. The document expiration date should appear on the first and last page. ** The document seems to lack a 1id_guidelines paragraph about Internet-Drafts being working documents. ** The document seems to lack a 1id_guidelines paragraph about 6 months document validity. ** The document seems to lack a 1id_guidelines paragraph about the list of current Internet-Drafts. ** The document seems to lack a 1id_guidelines paragraph about the list of Shadow Directories. == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** There are 6 instances of too long lines in the document, the longest one being 2 characters in excess of 72. ** There are 3414 instances of lines with control characters in the document. == There are 1 instance of lines with non-RFC6890-compliant IPv4 addresses in the document. If these are example addresses, they should be changed. == There are 5 instances of lines with multicast IPv4 addresses in the document. If these are generic example addresses, they should be changed to use the 233.252.0.x range defined in RFC 5771 == There are 6 instances of lines with private range IPv4 addresses in the document. If these are generic example addresses, they should be changed to use any of the ranges defined in RFC 6890 (or successor): 192.0.2.x, 198.51.100.x or 203.0.113.x. Miscellaneous warnings: ---------------------------------------------------------------------------- == Line 511 has weird spacing: '... Router loca...' -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (August 1998) is 9385 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Looks like a reference, but probably isn't: '1' on line 334 -- Looks like a reference, but probably isn't: '2' on line 362 == Missing Reference: 'Group A' is mentioned on line 1877, but not defined == Missing Reference: 'N1' is mentioned on line 513, but not defined == Missing Reference: 'Group B' is mentioned on line 516, but not defined == Missing Reference: 'N3' is mentioned on line 516, but not defined == Missing Reference: 'N2' is mentioned on line 514, but not defined -- Looks like a reference, but probably isn't: '4' on line 625 -- Looks like a reference, but probably isn't: '5' on line 728 == Missing Reference: 'Group G' is mentioned on line 2300, but not defined == Missing Reference: 'NX' is mentioned on line 742, but not defined -- Looks like a reference, but probably isn't: '6' on line 847 == Missing Reference: 'Group Y' is mentioned on line 872, but not defined == Missing Reference: 'Network X' is mentioned on line 872, but not defined -- Looks like a reference, but probably isn't: '7' on line 984 -- Looks like a reference, but probably isn't: '8' on line 991 -- Looks like a reference, but probably isn't: '9' on line 1247 -- Looks like a reference, but probably isn't: '10' on line 1827 == Missing Reference: 'Network N1' is mentioned on line 1877, but not defined -- Looks like a reference, but probably isn't: '11' on line 2164 -- Looks like a reference, but probably isn't: '12' on line 2190 -- Looks like a reference, but probably isn't: '13' on line 2216 -- Looks like a reference, but probably isn't: '14' on line 2236 == Missing Reference: 'SourceNet' is mentioned on line 2300, but not defined -- Looks like a reference, but probably isn't: '15' on line 2397 -- Looks like a reference, but probably isn't: '16' on line 2431 -- Looks like a reference, but probably isn't: '17' on line 2591 -- Looks like a reference, but probably isn't: '18' on line 2744 -- Looks like a reference, but probably isn't: '19' on line 2908 -- Looks like a reference, but probably isn't: '20' on line 2955 -- Looks like a reference, but probably isn't: '21' on line 3004 -- Looks like a reference, but probably isn't: '22' on line 3017 -- Looks like a reference, but probably isn't: '23' on line 3031 -- Looks like a reference, but probably isn't: '24' on line 3129 -- Looks like a reference, but probably isn't: '25' on line 3237 -- Looks like a reference, but probably isn't: '26' on line 3337 -- Looks like a reference, but probably isn't: '3' on line 3546 == Unused Reference: 'RFC 1584' is defined on line 3541, but no explicit reference was found in the text == Unused Reference: 'Bharath-Kumar' is defined on line 3544, but no explicit reference was found in the text == Unused Reference: 'RFC 1700' is defined on line 3572, but no explicit reference was found in the text == Unused Reference: 'NSSA' is defined on line 3785, but no explicit reference was found in the text ** Downref: Normative reference to an Historic RFC: RFC 1584 -- Possible downref: Non-RFC (?) normative reference: ref. 'Bharath-Kumar' -- Possible downref: Non-RFC (?) normative reference: ref. 'Deering' -- Possible downref: Non-RFC (?) normative reference: ref. 'Deering2' ** Downref: Normative reference to an Experimental RFC: RFC 1075 ** Obsolete normative reference: RFC 1700 (Obsoleted by RFC 3232) -- Possible downref: Non-RFC (?) normative reference: ref. 'IGMPv2' -- Possible downref: Non-RFC (?) normative reference: ref. 'NSSA' -- Possible downref: Non-RFC (?) normative reference: ref. 'EXATTR' Summary: 13 errors (**), 0 flaws (~~), 20 warnings (==), 35 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group J. Moy 3 Internet Draft Ascend Communications, Inc. 4 Expiration Date: February 1999 August 1998 5 File name: draft-ietf-mospf-mospf-00.txt 7 Multicast Extensions to OSPF 9 Status of this Memo 11 This document is an Internet-Draft. Internet-Drafts are working 12 documents of the Internet Engineering Task Force (IETF), its areas, 13 and its working groups. Note that other groups may also distribute 14 working documents as Internet-Drafts. 16 Internet-Drafts are draft documents valid for a maximum of six 17 months and may be updated, replaced, or obsoleted by other documents 18 at any time. It is inappropriate to use Internet- Drafts as 19 reference material or to cite them other than as "work in progress." 21 To view the entire list of current Internet-Drafts, please check the 22 "1id-abstracts.txt" listing contained in the Internet-Drafts Shadow 23 Directories on ftp.is.co.za (Africa), ftp.nordu.net (Northern 24 Europe), ftp.nis.garr.it (Southern Europe), munnari.oz.au 26 (Pacific Rim), ftp.ietf.org (US East Coast), or ftp.isi.edu (US West 27 Coast). 29 Abstract 31 This memo documents the MOSPF protocol. MOSPF, which stands for the 32 Multicast extensions to OSPF, is an enhancement to the OSPF protocol 33 enabling the routing of IP multicast datagrams. The extensions have 34 been implemented so that a multicast routing capability can be 35 introduced piecemeal into an OSPF Version 2 routing domain. Some of 36 the OSPF Version 2 routers may run the multicast extensions, while 37 others may continue to be restricted to the forwarding of regular IP 38 traffic (unicasts). 40 An implementation of this memo will interoperate with 41 implementations of the previous MOSPF specification, RFC 1584. 42 Differences between this memo and RFC 1584 include bug fixes, 43 modifications which track changes to the base OSPF specification, 44 and an assumption that IGMPv2 (instead of IGMPv1) will now be used 45 to communicate group membership from IP hosts to MOSPF routers. See 46 Appendix D for details. 48 Please send comments to mospf@gated.cornell.edu. 50 Table of Contents 52 1 Introduction ........................................... 5 53 1.1 Terminology ............................................ 6 54 1.2 Acknowledgments ........................................ 7 55 2 Multicast routing in MOSPF ............................. 7 56 2.1 Routing characteristics ................................ 7 57 2.2 Sample path of a multicast datagram .................... 8 58 2.3 MOSPF forwarding mechanism ............................ 11 59 2.3.1 IGMP interface: the local group database .............. 11 60 2.3.2 A datagram's shortest-path tree ....................... 13 61 2.3.3 Support for Non-broadcast networks .................... 16 62 2.3.4 Details concerning forwarding cache entries ........... 17 63 3 Inter-area multicasting ............................... 19 64 3.1 Extent of group-membership-LSAs ....................... 20 65 3.2 Building inter-area datagram shortest-path trees ...... 23 66 4 Inter-AS multicasting ................................. 28 67 4.1 Building inter-AS datagram shortest-path trees ........ 29 68 4.2 Stub area behavior .................................... 31 69 4.3 Inter-AS multicasting in a core Autonomous System ..... 31 70 5 Modelling internal group membership ................... 32 71 6 Additional capabilities ............................... 35 72 6.1 Mixing with non-multicast routers ..................... 35 73 6.2 Assigning multiple IP networks to a physical network .. 36 74 6.3 Networks on Autonomous System boundaries .............. 37 75 6.4 Recommended system configuration ...................... 38 76 7 Basic implementation requirements ..................... 40 77 8 Protocol data structures .............................. 40 78 8.1 Additions to the OSPF area structure .................. 41 79 8.2 Additions to the OSPF interface structure ............. 42 80 8.3 Additions to the OSPF neighbor structure .............. 42 81 8.4 The local group database .............................. 42 82 8.5 The forwarding cache .................................. 43 83 9 Interaction with the IGMP protocol .................... 45 84 9.1 Receiving IGMP Membership Reports ..................... 45 85 9.2 Receiving IGMP Membership Queries ..................... 46 86 10 Group-membership-LSAs ................................. 46 87 10.1 Constructing group-membership-LSAs .................... 48 88 10.2 Flooding group-membership-LSAs ........................ 50 89 11 Detailed description of multicast datagram forwarding . 50 90 11.1 Associating a MOSPF interface with a received datagram 53 91 11.2 Locating the source network ........................... 54 92 11.3 Forwarding locally originated multicasts .............. 55 93 12 Construction of forwarding cache entries .............. 56 94 12.1 The Vertex data structure ............................. 57 95 12.2 The SPF calculation ................................... 58 96 12.2.1 Candidate list Initialization: Case SourceIntraArea ... 63 97 12.2.2 Candidate list Initialization: Case SourceInterArea1 .. 64 98 12.2.3 Candidate list Initialization: Cases SourceInterArea2 99 and SourceStubExternal ............................ 64 100 12.2.4 Candidate list Initialization: Case SourceExternal .... 65 101 12.2.5 Processing labelled vertices .......................... 68 102 12.2.6 Merging datagram shortest-path trees .................. 69 103 12.2.7 Comparison to the unicast SPF calculation ............. 70 104 12.3 Adding local database entries to the forwarding cache 71 105 13 Maintaining the forwarding cache ...................... 72 106 14 Other additions to the OSPF specification ............. 73 107 14.1 The Designated Router ................................. 73 108 14.2 Sending Hello packets ................................. 74 109 14.3 The Neighbor state machine ............................ 74 110 14.4 Receiving Database Description packets ................ 74 111 14.5 Sending Database Description packets .................. 74 112 14.6 Originating Router-LSAs ............................... 75 113 14.7 Originating Network-LSAs .............................. 75 114 14.8 Originating Summary-LSAs .............................. 76 115 14.9 Originating AS-external-LSAs .......................... 76 116 14.10 Next step in the flooding procedure ................... 77 117 14.11 Virtual links ......................................... 77 118 15 References ............................................ 78 119 Footnotes ............................................. 80 120 A Data Formats .......................................... 83 121 A.1 The Options field ..................................... 84 122 A.2 Router-LSA ............................................ 86 123 A.3 Group-membership-LSA .................................. 88 124 B Configurable Constants ................................ 90 125 B.1 Global parameters ..................................... 90 126 B.2 Router interface parameters ........................... 90 127 C Sample datagram shortest-path trees ................... 92 128 C.1 An intra-area tree .................................... 93 129 C.2 The effect of areas ................................... 95 130 C.3 The effect of virtual links ........................... 96 131 D Differences from RFC 1584 ............................. 97 132 D.1 Bug Fixes ............................................. 97 133 D.1.1 Merging datagram shortest-path trees .................. 97 134 D.1.2 Candidate list initialization for stub areas .......... 97 135 D.1.3 Sources on multiply addressed segments ................ 97 136 D.1.4 Local group database modifications .................... 98 137 D.2 Changes required by RFC 2328 .......................... 98 138 D.2.1 Deleting the TOS routing option ....................... 98 139 D.2.2 Giving more-specific sources precedence ............... 98 140 D.3 Changes required by IGMPv2 ............................ 98 141 D.4 Clarifications ........................................ 99 142 Security Considerations .............................. 100 143 Author's Address ..................................... 100 144 1. Introduction 146 This memo documents enhancements to OSPF Version 2 to support IP 147 multicast routing. The enhancements have been added in a backward- 148 compatible fashion; routers running the multicast additions will 149 interoperate with non-multicast OSPF routers when forwarding regular 150 (unicast) IP data traffic. The protocol resulting from the addition 151 of the multicast enhancements to OSPF is herein referred to as the 152 MOSPF protocol. 154 IP multicasting is an extension of LAN multicasting to a TCP/IP 155 internet. Multicasting support for TCP/IP hosts has been specified 156 in [RFC 1112]. In that document, multicast groups are represented by 157 IP class D addresses. Individual TCP/IP hosts join (and leave) 158 multicast groups through the Internet Group Management Protocol 159 (IGMP, specified in [RFC 1112] and [IGMPv2]). A host need not be a 160 member of a multicast group in order to send datagrams to the group. 161 Multicast datagrams are to be delivered to each member of the 162 multicast group with the same "best-effort" delivery accorded 163 regular (unicast) IP data traffic. 165 MOSPF provides the ability to forward multicast datagrams from one 166 IP network to another (i.e., through internet routers). MOSPF 167 forwards a multicast datagram on the basis of both the datagram's 168 source and destination (this is sometimes called source/destination 169 routing). The OSPF link state database provides a complete 170 description of the Autonomous System's topology. By adding a new 171 type of link state advertisement, the group-membership-LSA, the 172 location of all multicast group members is pinpointed in the 173 database. The path of a multicast datagram can then be calculated by 174 building a shortest-path tree rooted at the datagram's source. All 175 branches not containing multicast members are pruned from the tree. 176 These pruned shortest-path trees are initially built when the first 177 datagram is received (i.e., on demand). The results of the shortest 178 path calculation are then cached for use by subsequent datagrams 179 having the same source and destination. 181 OSPF allows an Autonomous System to be split into areas. However, 182 when this is done complete knowledge of the Autonomous System's 183 topology is lost. When forwarding multicasts between areas, only 184 incomplete shortest-path trees can be built. This may lead to some 185 inefficiency in routing. An analogous situation exists when the 186 source of the multicast datagram lies in another Autonomous System. 187 In both cases (i.e., the source of the datagram belongs to a 188 different OSPF area, or to a different Autonomous system) the 189 neighborhood immediately surrounding the source is unknown. In these 190 cases the source's neighborhood is approximated by OSPF summary link 191 advertisements or by OSPF AS external link advertisements 192 respectively. 194 Routers running MOSPF can be intermixed with non-multicast OSPF 195 routers. Both types of routers can interoperate when forwarding 196 regular (unicast) IP data traffic. Obviously, the forwarding extent 197 of IP multicasts is limited by the number of MOSPF routers present 198 in the Autonomous System (and their interconnection, if any). An 199 ability to "tunnel" multicast datagrams through non-multicast 200 routers is not provided. In MOSPF, just as in the base OSPF 201 protocol, datagrams (multicast or unicast) are routed "as is" -- 202 they are not further encapsulated or decapsulated as they transit 203 the Autonomous System. 205 1.1. Terminology 207 This memo uses the terminology listed in section 1.2 of [OSPF]. 208 For this reason, terms such as "Network", "Autonomous System" 209 and "link state advertisement" are assumed to be understood. 211 [RFC 1112] discusses the data-link encapsulation of IP multicast 212 datagrams. In contrast to the normal forwarding of IP unicast 213 datagrams, on a broadcast network the mapping of an IP multicast 214 destination to a data-link destination address is not done with 215 the ARP protocol. Instead, static mappings have been defined 216 from IP multicast destinations to data-link addresses. These 217 mappings are dependent on network type; for some networks IP 218 multicasts are algorithmically mapped to data-link multicast 219 addresses, for other networks all IP multicast destinations are 220 mapped onto the data-link broadcast address. This document 221 loosely describes both of these possible mappings as data-link 222 multicast. 224 The following terms are also used throughout this document: 226 o Non-multicast router. A router running OSPF Version 2, but 227 not the multicast extensions. These routers do not forward 228 multicast datagrams, but can interoperate with MOSPF routers 229 in the forwarding of unicast packets. Routers running the 230 MOSPF protocol are referred to herein as either multicast- 231 capable routers or MOSPF routers. 233 o Non-broadcast networks. A network supporting the attachment 234 of more than two stations, but not supporting the delivery 235 of a single physical datagram to multiple destinations 236 (i.e., not supporting data-link multicast). An example of a 237 non-broadcast network is an X.25 PDN. 239 o Transit network. A network having two or more OSPF routers 240 attached. These networks can forward data traffic that is 241 neither locally-originated nor locally-destined. 243 o Stub network. A network having only a single OSPF router 244 attached. A network belonging to an OSPF system is either a 245 transit or a stub network, but never both. 247 1.2. Acknowledgments 249 The multicast extensions to OSPF are based on Link-State 250 Multicast Routing algorithm presented in [Deering]. In addition, 251 the [Deering] paper contains a section on Hierarchical Multicast 252 Routing (providing the ideas for MOSPF's inter-area multicasting 253 scheme) and several Distance Vector (also called Bellman-Ford) 254 multicast algorithms. One of these Distance Vector multicast 255 algorithms, Truncated Reverse Path Broadcasting, has been 256 implemented in the Internet (see [RFC 1075]). 258 The MOSPF protocol has been developed by the MOSPF Working Group 259 of the Internet Engineering Task Force. Portions of this work 260 have been supported by DARPA under NASA contract NAG 2-650. 262 2. Multicast routing in MOSPF 264 This section describes MOSPF's basic multicast routing algorithm. 265 The basic algorithm, run inside a single OSPF area, covers the case 266 where the source of the multicast datagram is inside the area 267 itself. Within the area, the path of the datagram forms a tree 268 rooted at the datagram source. 270 2.1. Routing characteristics 272 As a multicast datagram is forwarded along its shortest-path 273 tree, the datagram is delivered to each member of the 274 destination multicast group. In MOSPF, the forwarding of the 275 multicast datagram has the following properties: 277 o The path taken by a multicast datagram depends both on the 278 datagram's source and its multicast destination. Called 279 source/destination routing, this is in contrast to most 280 unicast datagram forwarding algorithms (like OSPF) that 281 route based solely on destination. 283 o The path taken between the datagram's source and any 284 particular destination group member is the least cost path 285 available. Cost is expressed in terms of the OSPF link-state 286 metric. For example, if the OSPF metric represents delay, a 287 minimum delay path is chosen. OSPF metrics are configurable. 288 A metric is assigned to each outbound router interface, 289 representing the cost of sending a packet on that interface. 290 The cost of a path is the sum of its constituent (outbound) 291 router interfaces. 293 o MOSPF takes advantage of any commonality of least cost paths 294 to destination group members. However, when members of the 295 multicast group are spread out over multiple networks, the 296 multicast datagram must at times be replicated. This 297 replication is performed as few times as possible (at the 298 tree branches), taking maximum advantage of common path 299 segments. 301 o For a given multicast datagram, all routers calculate an 302 identical shortest-path tree. There is a single path between 303 the datagram's source and any particular destination group 304 member. This means that, unlike OSPF's treatment of regular 305 (unicast) IP data traffic, there is no provision for equal- 306 cost multipath. 308 o On each packet hop, MOSPF normally forwards IP multicast 309 datagrams as data-link multicasts. There are two exceptions. 310 First, on non-broadcast networks, since there are no data- 311 link multicast/broadcast services the datagram must be 312 forwarded to specific MOSPF neighbors (see Section 2.3.3). 313 Second, a MOSPF router can be configured to forward IP 314 multicasts on specific networks as data-link unicasts, in 315 order to avoid datagram replication in certain anomalous 316 situations (see Section 6.3). 318 While MOSPF optimizes the path to any given group member, it 319 does not necessarily optimize the use of the internetwork as a 320 whole. To do so, instead of calculating source-based shortest- 321 path trees, something similar to a minimal spanning tree 322 (containing only the group members) would need to be calculated. 323 This type of minimal spanning tree is called a Steiner tree in 324 the literature. For a comparison of shortest-path tree routing 325 to routing using Steiner trees, see [Deering2] and [Bharath- 326 Kumar]. 328 2.2. Sample path of a multicast datagram 330 As an example of multicast datagram routing in MOSPF, consider 331 the sample Autonomous System pictured in Figure 1. This figure 332 has been taken from the OSPF specification (see [OSPF]). The 333 larger rectangles represent routers, the smaller rectangles 334 hosts. Oblongs and circles represent multi-access networks[1]. 336 Lines joining routers are point-to-point serial connections. A 337 cost has been assigned to each outbound router interface. 339 All routers in Figure 1 are assumed to be running MOSPF. A 340 number of hosts have been added to the figure. The hosts 341 labelled Ma have joined a particular multicast group (call it 342 Group A) via the IGMP protocol. These hosts are located on 343 networks N2, N6 and N11. Similarly, using IGMP the hosts 344 labelled Mb have joined a separate multicast group B; these 345 hosts are located on networks N1, N2 and N3. Note that hosts can 346 join multiple multicast groups; it is only for clarity of 347 presentation that each host has joined at most one multicast 348 group in this example. Also, hosts H2 through H5 have been 349 added to the figure to serve as sources for multicast datagrams. 350 Again, the datagrams' sources have been made separate from the 351 group members only for clarity of presentation. 353 To illustrate the forwarding of a multicast datagram, suppose 354 that Host H2 (attached to Network N4) sends a multicast datagram 355 to multicast group B. This datagram originates as a data-link 356 layer multicast on Network N4. Router RT3, being a multicast 357 router, has "opened up" its interface data-link multicast 358 filters. It therefore receives the multicast datagram, and 359 attempts to forward it to the members of multicast group B 360 (located on networks N1, N2 and N3). This is accomplished by 361 sending a single copy of the datagram onto Network N3, again as 362 a data-link multicast[2]. Upon receiving the multicast datagram 363 from RT3, routers RT1 and RT2 will then multicast the datagram 364 on their connected stub networks (N1 and N2 respectively). Note 365 that, since the datagram is sent onto Network N3 as a data-link 366 multicast, Router RT4 will also receive a copy. However, it will 367 not forward the datagram, since it does not lie on a shortest 368 path between the source (Host H2) and any members of multicast 369 group B. 371 Note that the path of the multicast datagram depends on the 372 datagram's source network. If the above multicast datagram was 373 instead originated by Host H3, the path taken would be 374 identical, since hosts H2 and H3 lie on the same network 375 (Network N4). However, if the datagram was originated by Host 376 H4, its path would be different. In this case, when Router RT3 377 receives the datagram, RT3 will drop the datagram instead of 378 forwarding it (since RT3 is no longer on the shortest path to 379 any member of Group B). 381 Note that the path of the multicast datagram also depends on the 382 destination multicast group. If Host H2 sends a multicast to 383 Group A, the path taken is as follows. The datagram again starts 384 + 385 | 3+---+ +--+ +--+ N12 N14 386 N1|--|RT1|\1 |Mb| |H4| \ N13 / 387 _| +---+ \ +--+ /+--+ 8\ |8/8 388 | + \ _|__/ \|/ 389 +--+ +--+ / \ 1+---+8 8+---+6 390 |Mb| |Mb| * N3 *---|RT4|------|RT5|--------+ 391 +--+ /+--+ \____/ +---+ +---+ | 392 + / | |7 | 393 | 3+---+ / | | | 394 N2|--|RT2|/1 |1 |6 | 395 __| +---+ +---+8 6+---+ | 396 | + |RT3|--------------|RT6| | 397 +--+ +--+ +---+ +--+ +---+ | 398 |Ma| |H3|_ |2 _|H2| Ia|7 | 399 +--+ +--+ \ | / +--+ | | 400 +---------+ | | 401 N4 | | 402 | | 403 | | 404 N11 | | 405 +---------+ | | 406 | \ | | N12 407 |3 +--+ | |6 2/ 408 +---+ |Ma| | +---+/ 409 |RT9| +--+ | |RT7|---N15 410 +---+ | +---+ 9 411 |1 + | |1 412 _|__ | Ib|5 __|_ +--+ 413 / \ 1+----+2 | 3+----+1 / \--|Ma| 414 * N9 *------|RT11|----|---|RT10|---* N6 * +--+ 415 \____/ +----+ | +----+ \____/ 416 | | | 417 |1 + |1 418 +--+ 10+----+ N8 +---+ 419 |H1|-----|RT12| |RT8| 420 +--+SLIP +----+ +---+ +--+ 421 |2 |4 _|H5| 422 | | / +--+ 423 +---------+ +--------+ 424 N10 N7 426 Figure 1: A sample MOSPF configuration 427 as a multicast on Network N4. Router RT3 receives it, and 428 creates two copies. One is sent onto Network N3 which is then 429 forwarded onto Network N2 by RT2. The other copy is sent to 430 Router RT10 (via RT6), where the datagram is again split, 431 eventually to be delivered onto networks N6 and N11. Note that, 432 although multiple copies of the datagram are produced, the 433 datagram itself is not modified (except for its IP TTL) as it is 434 forwarded. No encapsulation of the datagram is performed; the 435 destination of the datagram is always listed as the multicast 436 group A. 438 2.3. MOSPF forwarding mechanism 440 Each MOSPF router in the path of a multicast datagram bases its 441 forwarding decision on the contents of a data cache. This cache 442 is called the forwarding cache. There is a separate forwarding 443 cache entry for each source/destination combination. Each cache 444 entry indicates, for multicast datagrams having matching source 445 and destination, which neighboring node (i.e., router or 446 network) the datagram must be received from (called the upstream 447 node) and which interfaces the datagram should then be forwarded 448 out of (called the downstream interfaces). 450 A forwarding cache entry is actually built from two component 451 pieces. The first of these components is called the local group 452 database. This database, built by the IGMP protocol, indicates 453 the group membership of the router's directly attached networks. 454 The local group database enables the local delivery of multicast 455 datagrams. The second component is the datagram's shortest path 456 tree. This tree, built on demand, is rooted at a multicast 457 datagram's source. The datagram's shortest path tree enables the 458 delivery of multicast datagrams to distant (i.e., not directly 459 attached) group members. 461 2.3.1. IGMP interface: the local group database 463 The local group database keeps track of the group membership 464 of the router's directly attached networks. Each entry in 465 the local group database is a [group, attached network] 466 pair, which indicates that the attached network has one or 467 more IP hosts belonging to the IP multicast destination 468 group. This information is then used by the router when 469 deciding which directly attached networks to forward a 470 received IP multicast datagram onto, in order to complete 471 delivery of the datagram to (local) group members. 473 The local group database is built through the operation of 474 the Internet Group Management Protocol (IGMP; see [RFC 1112] 475 and [IGMPv2]). This document assumes that version 2 of the 476 IGMP protocol, IGMPv2, is being run on all local network 477 segments. All references to IGMP herein should be understood 478 as IGMPv2. 480 On each network segment, IGMP elects a special router called 481 a Querier. The IGMP Querier on an attached network (call 482 the network N1), sends periodic IGMP Membership Queries on 483 the network. Hosts then respond with IGMP Membership 484 Reports, one for each multicast group to which they belong. 485 Upon receiving a Host Membership Report for a multicast 486 group A, a MOSPF router updates its local group database by 487 adding/refreshing the entry [Group A, N1]. If at a later 488 time Reports for Group A cease to be heard on the network, 489 the entry is then deleted from the local group database. 491 Consider again the example pictured in Figure 1. Table 1 492 lists the local group database for the routers RT1-RT4. 494 The existence of local group members must be communicated to 495 the rest of the routers in the Autonomous System. This 496 ensures that a remotely-originated multicast datagram will 497 be forwarded to the router for distribution to its local 498 group members. This communication is accomplished through 499 the creation of a group-membership-LSA. Like other link 500 state advertisements, the group-membership-LSA is flooded 501 throughout the Autonomous System. A MOSPF router's group- 502 membership-LSA for Group A lists those local transit 503 vertices (i.e., the router itself and/or any directly 504 connected transit networks) that should not be pruned from 505 Group A's datagram shortest-path trees. The router lists 506 itself in its group-membership-LSA for Group A if either 1) 507 one or more of the router's attached stub networks contain 508 Group A members or 2) the router itself is a member of Group 509 A. The router lists a directly connected transit network in 511 Router local group database 512 ____________________________________________________ 513 RT1 [Group B, N1], [Group B, N3] 514 RT2 [Group A, N2], [Group B, N2], [Group B, N3] 515 RT3 [Group B, N3] 516 RT4 [Group B, N3] 518 Table 1: Sample local group databases 519 the group-membership-LSA for Group A if both 1) the router 520 is Designated Router on the network and 2) the network 521 contains one or more Group A members. 523 In Figure 1, if Router RT3 has been elected Designated 524 Router for Network N3, then each of the routers RT1, RT2 and 525 RT3 will originate a group-membership-LSA for Group B. In 526 addition, RT2 will also be originating a group-membership- 527 LSA for Group A. RT1 and RT2's group-membership-LSAs will 528 list solely the routers themselves (N1 and N2 are stub 529 networks). RT3's group-membership-LSA will list the transit 530 Network N3. 532 Figure 2 displays the Autonomous System's link state 533 database. A router/transit network is labelled with a 534 multicast group if (and only if) it has been mentioned in a 535 group-membership-LSA for the group. When building the 536 shortest-path tree for a particular multicast datagram, this 537 labelling enables those branches without group members to be 538 pruned from the tree. The process of building a multicast 539 datagram's shortest path tree is discussed in Section 2.3.2. 541 Note that none of the hosts in Figure 1 belonging to 542 multicast groups A and B show up explicitly in the link 543 state database (see Figure 2). In fact, looking at the link 544 state database you cannot even determine which stub networks 545 contain multicast group members. The link state database 546 simply indicates those routers/transit networks having 547 attached group members. This is all that is necessary for 548 successful forwarding of multicast datagrams. 550 2.3.2. A datagram's shortest-path tree 552 While the local group database facilitates the local 553 delivery of multicast datagrams, the datagram's shortest- 554 path tree describes the intermediate hops taken by a 555 multicast datagram as it travels from its source to the 556 individual multicast group members. As mentioned above, the 557 datagram's shortest-path tree is a pruned shortest-path tree 558 rooted at the datagram's source. Two datagrams having 559 differing [source net, multicast destination] pairs may 560 have, and in fact probably will have, different pruned 561 shortest-path trees. 563 A datagram's shortest path tree is built "on demand"[3], 564 i.e., when the first multicast datagram is received having a 565 particular [source net, multicast destination] combination. 566 To build the datagram's shortest-path tree, the following 567 **FROM** 569 |RT|RT|RT|RT|RT|RT|RT|RT|RT|RT|RT|RT| 570 |1 |2 |3 |4 |5 |6 |7 |8 |9 |10|11|12|N3|N6|N8|N9| 571 ----- --------------------------------------------- 572 RT1| | | | | | | | | | | | |0 | | | | 573 RT2| | | | | | | | | | | | |0 | | | | 574 RT3| | | | | |6 | | | | | | |0 | | | | 575 RT4| | | | |8 | | | | | | | |0 | | | | 576 RT5| | | |8 | |6 |6 | | | | | | | | | | 577 RT6| | |8 | |7 | | | | |5 | | | | | | | 578 RT7| | | | |6 | | | | | | | | |0 | | | 579 * RT8| | | | | | | | | | | | | |0 | | | 580 * RT9| | | | | | | | | | | | | | | |0 | 581 T RT10| | | | | |7 | | | | | | | |0 |0 | | 582 O RT11| | | | | | | | | | | | | | |0 |0 | 583 * RT12| | | | | | | | | | | | | | | |0 | 584 * N1|3 | | | | | | | | | | | | | | | | 585 N2| |3 | | | | | | | | | | | | | | | 586 N3|1 |1 |1 |1 | | | | | | | | | | | | | 587 N4| | |2 | | | | | | | | | | | | | | 588 N6| | | | | | |1 |1 | |1 | | | | | | | 589 N7| | | | | | | |4 | | | | | | | | | 590 N8| | | | | | | | | |3 |2 | | | | | | 591 N9| | | | | | | | |1 | |1 |1 | | | | | 592 N10| | | | | | | | | | | |2 | | | | | 593 N11| | | | | | | | |3 | | | | | | | | 594 N12| | | | |8 | |2 | | | | | | | | | | 595 N13| | | | |8 | | | | | | | | | | | | 596 N14| | | | |8 | | | | | | | | | | | | 597 N15| | | | | | |9 | | | | | | | | | | 598 H1| | | | | | | | | | | |10| | | | | 600 Figure 2: The MOSPF database. 602 Networks and routers are represented by vertices. 603 An edge of cost X connects Vertex A to Vertex B iff 604 the intersection of Column A and Row B is marked 605 with an X. In addition, RT1, RT2 and N3 are labelled 606 with multicast group A and RT1, N6 and RT9 are 607 labelled with multicast group B. 609 calculations are performed. First, the datagram's source IP 610 network is located in the link state database. Then using 611 the router-LSAs and network-LSAs in the link state database, 612 a shortest-path tree is built having the source network as 613 root. To complete the process, the branches that do not 614 contain routers/transit networks that have been labelled 615 with the particular multicast destination (via a group- 616 membership-LSA) are pruned from the tree. 618 As an example of the building of a datagram's shortest path 619 tree, again consider the Autonomous System in Figure 1. The 620 Autonomous System's link state database is pictured in 621 Figure 2. When a router initially receives a multicast 622 datagram sent by Host H2 to the multicast group A, the 623 following steps are taken: Host H2 is first determined to be 624 on Network N4. Then the shortest path tree rooted at net N4 625 is calculated[4], pruning those branches that do not contain 626 routers/transit networks that have been labelled with the 627 multicast group A. This results in the pruned shortest-path 628 tree pictured in Figure 3. Note that at this point all the 629 leaves of the tree are routers/transit networks labelled 630 with multicast group A (routers RT2 and RT9 and transit 631 Network N6). 633 In order to forward the multicast datagram, each router must 634 find its own position in the datagram's shortest path tree. 635 The router's (call it Router RTX) position in the datagram's 636 pruned shortest-path tree consists of 1) RTX's parent in the 637 tree (this will be the forwarding cache entry's upstream 638 node) and 2) the list of RTX's interfaces that lead to 639 downstream routers/transit networks that have been labelled 640 with the datagram's destination (these will be added to the 641 forwarding cache entry as downstream interfaces). Note that 642 after calculating the datagram's shortest path tree, a 643 router may find that it is itself not on the tree. This 644 would be indicated by a forwarding cache entry having no 645 upstream node or an empty list of downstream interfaces. 647 As an example of a router describing its position on the 648 datagram's shortest-path tree, consider Router RT10 in 649 Figure 3. Router RT10's upstream node for the datagram is 650 Router RT6, and there are two downstream interfaces: one 651 connecting to Network N6 and the other connecting to Network 652 N8. 654 o RT3 (N4, origin) 655 / \ 656 1/ \8 657 / \ 658 N3 (Mb) o o RT6 659 / \ 660 0/ \7 661 / \ 662 RT2 (Ma,Mb) o o RT10 663 / \ 664 3/ \1 665 / \ 666 N8 o o N6 (Ma) 667 / 668 0/ 669 / 670 RT11 o 671 / 672 1/ 673 / 674 N9 o 675 / 676 0/ 677 / 678 RT9 (Ma) o 680 Figure 3: Sample datagram's shortest-path tree, 681 source N4, destination Group A 683 2.3.3. Support for Non-broadcast networks 685 When forwarding multicast datagrams over non-broadcast 686 networks, the datagram cannot be sent as a link-level 687 multicast (since neither link-level multicast nor broadcast 688 are supported on these networks), but must instead be 689 forwarded separately to specific neighbors. To facilitate 690 this, forwarding cache entries can also contain downstream 691 neighbors as well as downstream interfaces. 693 The IGMP protocol is not defined over non-broadcast 694 networks. For this reason, there cannot be group members 695 directly attached to non-broadcast networks, nor do non- 696 broadcast networks ever appear in local group database 697 entries. 699 As an example, suppose that Network N3 in Figure 1 is an 700 X.25 PDN. Consider Router RT3's forwarding cache entry for 701 datagrams having source Network N4 and multicast destination 702 Group B. In place of having the interface to Network N3 703 appear as the downstream interface in the matching 704 forwarding cache entry, the neighboring routers RT1 and RT2 705 would instead appear as separate downstream neighbors. In 706 addition, in this case there could not be a Group B member 707 directly attached to Network N3. 709 2.3.4. Details concerning forwarding cache entries 711 Each of the downstream interface/neighbors in the cache 712 entry is labelled with a TTL value. This value indicates the 713 number of hops a datagram forwarded out of the interface (or 714 forwarded to the neighbor) would have to travel before 715 encountering a router/transit network requesting the 716 multicast destination. The reason that a hop count is 717 associated with each downstream interface/neighbor is so 718 that IP multicast's expanding ring search procedure can be 719 more efficiently implemented. By expanding ring search is 720 meant the following. Hosts can restrict the frowarding 721 extent of the IP multicast datagrams that they send by 722 appropriate setting of the TTL value in the datagram's IP 723 header. Then, for example, to search for the nearest server 724 the host can send multicasts first with TTL set to 1, then 725 2, etc. By attaching a hop count to each downstream 726 interface/neighbor in the forwarding cache, datagrams will 727 not be forwarded unless they will ultimately reach a 728 multicast destination before their TTL expires[5]. This 729 avoids wasting network bandwidth during an expanding ring 730 search. 732 As an example consider Router RT10's forwarding cache in 733 Figure 3. Router RT10's cache entry has two downstream 734 interfaces. The first, connecting to Network N6, is labelled 735 as having a group member one hop away (Network N6). The 736 second, which connects to Network N8, is labelled as having 737 a group member two hops away (Router RT9). 739 Both the datagram shortest path tree and the local group 740 database may contribute downstream interfaces to the 741 forwarding cache entries. As an example, if a router has a 742 local group database entry of [Group G, NX] for a stub 743 network NX, then a forwarding cache entry for Group G, 744 regardless of source, will list the router interface to 745 Network NX as a downstream interface. Such a downstream 746 interface will always be labelled with a TTL of 1. 748 As an example of forwarding cache entries, again consider 749 the Autonomous System pictured in Figure 1. Suppose Host H2 750 sends a multicast datagram to multicast group A. In that 751 case, some routers will not even attempt to build a 752 forwarding cache entry (e.g, router RT5) because they will 753 never receive the multicast datagram in the first place. 754 Other routers will receive the multicast datagram (since 755 they are forwarded as link-level multicasts), but after 756 building the pruned shortest path tree will notice that they 757 themselves are not a part of the tree (routers RT1, RT4, 758 RT7, RT8 and RT12). These latter routers will install an 759 empty cache entry, indicating that they do not participate 760 in the forwarding of the multicast datagram. A sample of the 761 forwarding cache entries built by the other routers in the 762 Autonomous System is pictured in Table 2. 764 A MOSPF router must clear its entire forwarding cache when 765 the Autonomous System's topology changes, because all the 766 datagram shortest-path trees must be rebuilt. Likewise, when 767 the location of a multicast group's membership changes 768 (reflected by a change in group-membership-LSAs), all cache 769 entries associated with the particular multicast destination 770 group must be cleared. Other than these two cases, 771 forwarding cache entries need not ever be deleted or 772 otherwise modified; in particular, the forwarding cache 773 entries do not have to be aged. However, forwarding cache 774 entries can be freely deleted after some period of 775 inactivity (i.e., garbage collected), if router memory 776 resources are in short supply. 778 Router Upstream Downstream interfaces 779 node (interface:hops) 780 ___________________________________________ 781 RT10 Router RT6 (N6:1), (N8:2) 782 RT11 Net N8 (N9:1) 783 RT3 Net N4 (N3:1), (RT6:3) 784 RT6 Router RT3 (RT10:2) 785 RT2 Net N3 (N2:1) 787 Table 2: Sample forwarding cache entries, 788 for source N4 and destination Group A. 790 3. Inter-area multicasting 792 Up to this point this memo has discussed multicast forwarding when 793 the entire Autonomous System is a single OSPF area. The logic for 794 when the multicast datagram's source and its destination group 795 members belong to the same OSPF area is the same. This section 796 explains the behavior of the MOSPF protocol when the datagram's 797 source and (at least some of) its destination group members belong 798 to different OSPF areas. This situation is called inter-area 799 multicast. 801 Inter-area multicast brings up the following issues, which are 802 resolved in succeeding sections: 804 o Are the group-membership-LSAs specific to a single area? And if 805 they are, how is group membership information conveyed from one 806 area to the next? 808 o How are the datagram shortest-path trees built in the inter-area 809 case, since complete information concerning the topology of the 810 datagram source's neighborhood is not available to routers in 811 other areas? 813 o In an area border router, multiple datagram shortest-path trees 814 are built, one for each attached area. How are these separate 815 datagram shortest-path trees combined into a single forwarding 816 cache entry? 818 It should be noted in the following that the basic protocol 819 mechanisms in the inter-area case are the same as for the intra-area 820 case. Forwarding of multicasts is still defined by the contents of 821 the forwarding cache. The forwarding cache is still built from the 822 same two components: the local group database and the datagram 823 shortest-path trees. And while the calculation of the datagram 824 shortest-path trees is different in the inter-area case (see Section 825 3.2), the local group database is built exactly the same as in the 826 intra-area case (i.e., MOSPF's interface with IGMP remains unchanged 827 in the presence of areas). Finally, the forwarding algorithm 828 described in Section 11 is the same for both the intra-area and 829 inter-area cases. 831 The following discussion uses the area configuration pictured in 832 Figure 4 as an example. This figure, taken from the OSPF 833 specification, shows an Autonomous System split into three areas 834 (Area 1, Area 2 and Area 3). A single backbone area has been 835 configured (everything outside of the shading). Since the backbone 836 area must be contiguous, a single virtual link has been configured 837 between the area border routers RT10 and RT11. Additionally, an area 838 address range has been configured in Router RT11 so that Networks 839 N9-N11 and Host H1 will be reported as a single route outside of 840 Area 3 (via summary-LSAs). 842 3.1. Extent of group-membership-LSAs 844 Group-membership-LSAs are specific to a single OSPF area. This 845 means that, just as with OSPF router-LSAs, network-LSAs and 846 summary-LSAs, a group-membership-LSA is flooded throughout a 847 single area only[6]. A router attached to multiple areas (i.e., 848 an area border router) may end up originating several group- 849 membership-LSAs concerning a single multicast destination, one 850 for each attached area. However, as we will see below, the 851 contents of these group-membership-LSAs will vary depending on 852 their associated areas. 854 Just as in OSPF, each MOSPF area has its own link state 855 database. The MOSPF database is simply the OSPF link state 856 database enhanced by the group-membership-LSAs. Consider again 857 the area configuration pictured in Figure 4. The result of 858 adding the group-membership-LSAs to the area databases yields 859 the databases pictured in Figures 6 and 7. Figure 6 shows Area 860 1's MOSPF database. RT1, RT2 and N3 are labelled with multicast 861 group A, RT1 is labelled with multicast group B, and both RT3 862 and RT4 are labelled as wild-card multicast receivers. Summary- 863 LSAs and ASE-external-LSAs are also included, as links 864 originating from routers RT3 and RT4, and from routers RT5 and 865 RT7, respectively. 867 Similarly, Figure 7 shows the backbone's MOSPF database. Note 868 that Router RT11 has condensed its routes to Networks N9-N11 and 869 Host H1 into a single summary-LSA. 871 Suppose an OSPF router has a local group database entry for 872 [Group Y, Network X], and that the router has been elected 873 Designated Router on Network X. The router then originates a 874 group-membership-LSA for Group Y into the area containing 875 Network X. For example, in the area configuration pictured in 876 Figure 4, Router RT1 originates a group-membership-LSA for Group 877 B. This group-membership-LSA is flooded throughout Area 1, and 878 no further. Likewise, assuming that Router RT3 has been elected 879 Designated Router for Network N3, RT3 originates a group- 880 membership-LSA into Area 1 listing the transit Network N3 as 881 having group members. Note that in the link state database for 882 Area 1 (Figure 6) both Router RT1 and Network N3 have 883 accordingly been labelled with Group B. 885 .................................. 886 . + . 887 . | 3+---+ +--+ +--+ . N12 N14 888 . N1|--|RT1|\1 |Mb| |H4| . \ N13 / 889 . _| +---+ \ +--+ /+--+ . 8\ |8/8 890 . | + \ _|__/ . \|/ 891 . +--+ +--+ / \ 1+---+8. 8+---+6 892 . |Mb| |Mb| * N3 *---|RT4|------|RT5|--------+ 893 . +--+ /+--+ \____/ +---+ . +---+ | 894 . + / | . |7 | 895 . | 3+---+ / | . | | 896 . N2|--|RT2|/1 |1 . |6 | 897 . __| +---+ +---+8 . 6+---+ | 898 . | + |RT3|--------------|RT6| | 899 . +--+ +--+ +---+ +--+. +---+ | 900 . |Ma| |H3|_ |2 _|H2|. Ia|7 | 901 . +--+ +--+ \ | / +--+. | | 902 . +---------+ . | | 903 .Area 1 N4 . | | 904 .................................. | | 905 ................................ | | 906 . N11 . | | 907 . +---------+ . | | 908 . | \ . | | N12 909 . |3 +--+ . | |6 2/ 910 . +---+ |Ma| . | +---+/ 911 . |RT9| +--+ . | |RT7|---N15 912 . +---+ ....... | +---+ 9 913 . |1 .. + ...|..........|1........ 914 . _|__ .. | Ib|5 __|_ +--+. 915 . / \ 1+----+2.. | 3+----+1 / \--|Ma|. 916 . * N9 *------|RT11|----|---|RT10|---* N6 * +--+. 917 . \____/ +----+ .. | +----+ \____/ . 918 . | !*******|*****! | . 919 . |1 Virtual + Link |1 . 920 . +--+ 10+----+ ..N8 +---+ . 921 . |H1|-----|RT12| .. |RT8| . 922 . +--+SLIP +----+ .. +---+ +--+. 923 . |2 .. |4 _|H5|. 924 . | .. | / +--+. 925 . +---------+ .. +--------+ . 926 . N10 Area 3..Area 2 N7 . 927 ............................................................. 929 Figure 4: A sample MOSPF area configuration 930 In OSPF, the area border routers forward routing information and 931 data traffic between areas. In MOSPF. a subset of the area 932 border routers, called the inter-area multicast forwarders, 933 forward group membership information and multicast datagrams 934 between areas. Whether a given OSPF area border router is also a 935 MOSPF inter-area multicast forwarder is configuration dependent 936 (see Section B.1). In Figure 4 we assume that all area border 937 routers are also inter-area multicast forwarders. 939 In order to convey group membership information between areas, 940 inter-area multicast forwarders "summarize" their attached 941 areas' group membership to the backbone. This is very similar 942 functionality to the summary-LSAs that are generated in the base 943 OSPF protocol. An inter-area multicast forwarder calculates 944 which groups have members in its attached non-backbone areas. 945 Then, for each of these groups, the inter-area multicast 946 forwarder injects a group-membership-LSA into the backbone area. 947 For example, in Figure 4 there are two groups having members in 948 Area 1: Group A and Group B. For that reason, both of Area 1's 949 inter-area multicast forwarders (Routers RT3 and RT4) inject 950 group-membership-LSAs for these two groups into the backbone. 951 As a result both of these routers are labelled with Groups A and 952 B in the backbone link state database (see Figure 7). 954 However, unlike the summarization of unicast destinations in the 955 base OSPF protocol, the summarization of group membership in 956 MOSPF is asymmetric. While a non-backbone area's group 957 membership is summarized to the backbone, this information is 958 not then readvertised into other non-backbone areas. Nor is the 959 backbone's group membership summarized for the non-backbone 960 areas. Going back to the example in Figure 4, while the presence 961 of Area 3's group (Group A) is advertised to the backbone, this 962 information is not then redistributed to Area 1. In other words, 963 routers internal to Area 1 have no idea of Area 3's group 964 membership. 966 membership +------------------+ datagrams 967 + > > > >>| Backbone |< < < < + 968 ^ +------------------+ ^ 969 ^ / | \ ^ 970 ^ / | \ ^ 971 +----^-----+/ +----------+ \+----^-----+ 972 | Area 1 | | Area 2 | | Area 3 | 973 +----------+ +----------+ +----------+ 975 Figure 5: Inter-area routing architecture 976 At this point, if no extra functionality was added to MOSPF, 977 multicast traffic originating in Area 1 destined for Multicast 978 Group A would never be forwarded to those Group A members in 979 Area 3. To accomplish this, the notion of wild-card multicast 980 receivers is introduced. A wild-card multicast receiver is a 981 router to which all multicast traffic, regardless of multicast 982 destination, should be forwarded. A router's wild-card multicast 983 reception status is per-area. In non-backbone areas, all inter- 984 area multicast forwarders[7] are wild-card multicast receivers. 985 This ensures that all multicast traffic originating in a non- 986 backbone area will be forwarded to its inter-area multicast 987 forwarders, and hence to the backbone area. Since the backbone 988 has complete knowledge of all areas' group membership, the 989 datagram can then be forwarded to all group members. Note that 990 in the backbone itself there is no need for wild-card multicast 991 receivers[8]. As an example, note that Routers RT3 and RT4 are 992 wild-card multicast receivers in Area 1 (see Figure 6), while 993 there are none in the backbone (see Figure 7). 995 This yields the inter-area routing architecture pictured in 996 Figure 5. All group membership is advertised by the non- 997 backbone areas into the backbone. Likewise, all IP multicast 998 traffic arising in the non-backbone areas is forwarded to the 999 backbone. Since at this point group membership information meets 1000 the multicast datagram traffic, delivery of the multicast 1001 datagrams becomes possible. 1003 3.2. Building inter-area datagram shortest-path trees 1005 When building datagram shortest-path trees in the presence of 1006 areas, it is often the case that the source of the datagram and 1007 (at least some of) the destination group members are in separate 1008 areas. Since detailed topological information concerning one 1009 OSPF area is not distributed to other OSPF areas (the flooding 1010 of router-LSAs, network-LSAs and group-membership-LSAs is 1011 restricted to a single OSPF area only), the building of complete 1012 datagram shortest-path trees is often impossible in the inter- 1013 area case. To compensate, approximations are made through the 1014 use of wild-card multicast receivers and OSPF summary-LSAs. 1016 When it first receives a datagram for a particular [source net, 1017 destination group] pair, a router calculates a separate datagram 1018 shortest-path tree for each of the router's attached areas. Each 1019 datagram shortest-path tree is built solely from LSAs belonging 1020 to the particular area's link state database. Suppose that a 1021 router is calculating a datagram shortest-path tree for Area A. 1022 It is useful then to separate out two cases. 1024 **FROM** 1026 |RT|RT|RT|RT|RT|RT| 1027 |1 |2 |3 |4 |5 |7 |N3| 1028 ----- ------------------- 1029 RT1| | | | | | |0 | 1030 RT2| | | | | | |0 | 1031 RT3| | | | | | |0 | 1032 * RT4| | | | | | |0 | 1033 * RT5| | |14|8 | | | | 1034 T RT7| | |20|14| | | | 1035 O N1|3 | | | | | | | 1036 * N2| |3 | | | | | | 1037 * N3|1 |1 |1 |1 | | | | 1038 N4| | |2 | | | | | 1039 Ia,Ib| | |15|22| | | | 1040 N6| | |16|15| | | | 1041 N7| | |20|19| | | | 1042 N8| | |18|18| | | | 1043 N9-N11,H1| | |19|16| | | | 1044 N12| | | | |8 |2 | | 1045 N13| | | | |8 | | | 1046 N14| | | | |8 | | | 1047 N15| | | | | |9 | | 1049 Figure 6: Area 1's MOSPF database. 1051 Networks and routers are represented by vertices. 1052 An edge of cost X connects Vertex A to Vertex B iff 1053 the intersection of Column A and Row B is marked 1054 with an X. In addition, RT1, RT2 and N3 are labelled 1055 with multicast group A, RT1 is labelled with multicast 1056 group B, and both RT3 and RT4 are labelled as 1057 wild-card multicast receivers. 1059 **FROM** 1061 |RT|RT|RT|RT|RT|RT|RT 1062 |3 |4 |5 |6 |7 |10|11| 1063 ------------------------ 1064 RT3| | | |6 | | | | 1065 RT4| | |8 | | | | | 1066 RT5| |8 | |6 |6 | | | 1067 RT6|8 | |7 | | |5 | | 1068 RT7| | |6 | | | | | 1069 * RT10| | | |7 | | |2 | 1070 * RT11| | | | | |3 | | 1071 T N1|4 |4 | | | | | | 1072 O N2|4 |4 | | | | | | 1073 * N3|1 |1 | | | | | | 1074 * N4|2 |3 | | | | | | 1075 Ia| | | | | |5 | | 1076 Ib| | | |7 | | | | 1077 N6| | | | |1 |1 |3 | 1078 N7| | | | |5 |5 |7 | 1079 N8| | | | |4 |3 |2 | 1080 N9-N11,H1| | | | | | |1 | 1081 N12| | |8 | |2 | | | 1082 N13| | |8 | | | | | 1083 N14| | |8 | | | | | 1084 N15| | | | |9 | | | 1086 Figure 7: The backbone's MOSPF database. 1088 Networks and routers are represented by vertices. 1089 An edge of cost X connects Vertex A to Vertex B iff 1090 the intersection of Column A and Row B is marked 1091 with an X. In addition, RT3 and RT4 are labelled 1092 with both multicast groups A and B, and RT7, RT10, 1093 and RT11 are labelled with multicast group A. 1095 The first case, Case 1: The source of the datagram belongs to 1096 Area A has already been described in Section 2.3.2. However, in 1097 the presence of OSPF areas, during tree pruning care must be 1098 taken so that the branches leading to other areas remain, since 1099 it is unknown whether there are group members in these (remote) 1100 areas. For this reason, only those branches having no group 1101 members nor wild-card multicast receivers are pruned when 1102 producing the datagram shortest-path tree. 1104 As an example, suppose in Figure 4 that Host H2 sends a 1105 multicast datagram to destination Group A. Then the datagram's 1106 shortest-path tree for Area 1, built identically by all routers 1107 in Area 1 that receive the datagram, is shown in Figure 8. Note 1108 that both inter-area multicast forwarders (RT3 and RT4) are on 1109 the datagram's shortest-path tree, ensuring the delivery of the 1110 datagram to the backbone and from there to Areas 2 and 3. 1112 o Case 2: The source of the datagram belongs to an area other 1113 than Area A. In this case, when building the datagram 1114 shortest-path tree for Area A, the immediate neighborhood of 1115 the datagram's source is unknown. However, there are 1116 summary-LSAs in the Area A link state database indicating 1117 the cost of the paths between each of Area A's inter-area 1118 multicast forwarders and the datagram source. These summary 1119 links are used to approximate the neighborhood of the 1120 datagram's source; the tree begins with links directly 1121 connecting the source to each of the inter-area multicast 1122 forwarders. These links point in the reverse direction 1123 (towards instead of away from the datagram source) from the 1124 links considered in Case 1 above. All additional links added 1125 to the tree also point in the reverse direction. The final 1126 datagram shortest-path tree is then produced by, as before, 1127 pruning all branches having no group-members nor wild-card 1128 multicast receivers. 1130 As an example, suppose again that Host H2 in Figure 4 sends 1131 a multicast datagram to destination Group A. The datagram's 1132 shortest-path tree for the backbone is shown in Figure 9. 1133 The neighborhood around the source (Network N4) has been 1134 approximated by the summary links advertised by routers RT3 1135 and RT4. Note that all links in Figure 9's datagram 1136 shortest-path tree have arrows pointing in the reverse 1137 direction, towards Network N4 instead of away from it. 1139 o RT3 (W, origin=N4) 1140 | 1141 1| 1142 | 1143 N3 (Mb) o 1144 / \ 1145 0/ \0 1146 / \ 1147 RT2 (Ma,Mb) o o RT4 (W) 1149 Figure 8: Datagram's shortest-path tree, 1150 Area 1, source N4, destination Group A 1151 o N4 1152 / \ 1153 2/ \3 1154 / \ 1155 RT3 (Ma,Mb) o o RT4 (Ma,Mb) 1156 / \ 1157 6/ \8 1158 / \ 1159 RT6 o o RT5 1160 | | 1161 5| |6 1162 | | 1163 RT10 (Ma) o o RT7 (Ma) 1164 | 1165 2| 1166 | 1167 RT11 (Ma) o 1169 Figure 9: Datagram shortest-path tree: Backbone, 1170 source N4, destination Group A. Note that 1171 reverse costs (i.e., toward origin) are 1172 used throughout. 1174 The reverse costs used for the entire tree in Case 2 are forced 1175 because summary-LSAs only specify the cost towards the datagram 1176 source. In the presence of asymmetric link costs, this may lead 1177 to less efficient routes when forwarding multicasts between 1178 areas. 1180 Those routers attached to multiple areas must calculate multiple 1181 trees and then merge them into a single forwarding cache entry. 1182 As shown in Section 2.3.2, when connected to a single area the 1183 router's position on the datagram shortest-path tree determines 1184 (in large part) its forwarding cache entry. When attached to 1185 multiple areas, and hence calculating multiple datagram 1186 shortest-path trees, each tree contributes to the forwarding 1187 cache entry's list of downstream interfaces/neighbors. However, 1188 only one of the areas' datagram shortest-path trees will 1189 determine the forwarding cache entry's upstream node. When one 1190 of the attached areas contains the datagram source, that area 1191 will determine the upstream node. Otherwise, the tiebreaking 1192 rules of Section 12.2.6 are invoked. 1194 Consider again the example of Host H2 in Figure 4 sending a 1195 multicast datagram to destination Group A. Router RT3 will 1196 calculate two datagram shortest-path trees, one for Area 1 and 1197 one for the backbone. Since the source of the datagram (Host 1198 H2) belongs to Area 1, the Area 1 datagram shortest-path tree 1199 determines RT3's upstream node: Network N4. Router RT3 1200 calculates two downstream interfaces for the datagram: the 1201 interface to Network N3 (which comes from Area 1's datagram 1202 shortest-path tree) and the serial line to Router RT6 (which 1203 comes from the backbone's datagram shortest-path tree). As for 1204 Router RT10, it calculates two trees, determining its upstream 1205 node from the backbone tree and its two downstream interfaces 1206 from the Area 2 tree. Finally, Router RT11 calculates three 1207 trees, determining its upstream node from the Area 2 tree and 1208 its downstream interface from the Area 3 tree. 1210 4. Inter-AS multicasting 1212 This section explains how MOSPF deals with the forwarding of 1213 multicast datagrams between Autonomous Systems. Certain AS boundary 1214 routers in a MOSPF system will be configured as inter-AS multicast 1215 forwarders. It is assumed that these routers will also be running an 1216 inter-AS multicast routing protocol. This specification does not 1217 dictate the operation of such an inter-AS multicast routing 1218 protocol. However, the following interactions between MOSPF and the 1219 inter-AS routing protocol are assumed: 1221 (1) MOSPF guarantees that the inter-AS multicast forwarders will 1222 receive all multicast datagrams; but it is up to each router so 1223 designated to determine whether the datagram should be forwarded 1224 to other Autonomous Systems. This determination will probably be 1225 made via the inter-AS routing protocol. 1227 (2) MOSPF assumes that the inter-AS routing protocol is forwarding 1228 multicast datagrams in an RPF (reverse path forwarding; see 1229 [Deering] for an explanation of this terminology) fashion. In 1230 other words, it is assumed that a multicast datagram whose 1231 source (call it X) lies outside the MOSPF domain will enter the 1232 MOSPF domain at those points that are advertising (into OSPF) 1233 the best routes back to X. MOSPF calculates the path of the 1234 datagram through the MOSPF domain based on this assumption. 1236 MOSPF designates an inter-AS multicast forwarder as a wild-card 1237 multicast receiver in all of its attached areas. As in the inter- 1238 area case, this ensures that the routers remain on all pruned 1239 shortest-path trees and thereby receive all multicast datagrams, 1240 regardless of destination. 1242 As an example, suppose that in Figure 1 both RT5 and RT7 were 1243 configured as inter-AS multicast forwarders. Then the link state 1244 database would look like the one pictured in Figure 2, with the 1245 addition of a) wild-card status for RT5 and RT7 and b) the external 1246 links originated by RT5 and RT7 being labelled as multicast- 1247 capable[9]. 1249 As another example, consider the area configuration in Figure 4. 1250 Again suppose RT5 and RT7 are configured as inter-AS multicast 1251 forwarders. Then in Area 1's link state database (Figure 6), the 1252 external links originated by RT5 and RT7 would again be labelled as 1253 multicast-capable. However, note that in Area 1's database RT5 and 1254 RT7 are not labelled as wild-card multicast receivers. This is 1255 unnecessary; since Area 1's inter-area multicast forwarders (RT3 and 1256 RT4) are wild-cards, all multicast datagrams will be forwarded to 1257 the backbone. And in the backbone's link state database (Figure 7), 1258 RT5 and RT7 will be labelled as wild-cards. 1260 4.1. Building inter-AS datagram shortest-path trees. 1262 When multicast datagrams are to be forwarded between Autonomous 1263 Systems, the datagram shortest-path tree is built as follows. 1264 Remember that the router builds a separate tree for each area to 1265 which it is attached; these trees are then merged into a single 1266 forwarding cache entry. Suppose that the router is building the 1267 tree for Area A. We break up the tree building into three cases. 1268 This first two cases have already been described earlier in this 1269 memo: Case 1 (the source of the datagram belongs to Area A) 1270 having been described in Section 2.3.2 and Case 2 (the source of 1271 the datagram belongs to another OSPF area) having been described 1272 in Section 3.2. The only modification to these cases is that 1273 inter-AS multicast forwarders, as well as group members and 1274 inter-area multicast forwarders, must remain on the pruned 1275 trees. The new case is as follows: 1277 o Case 3: The source of the datagram belongs to another 1278 Autonomous System. The immediate neighborhood of the source 1279 is then unknown. In this case the multicast-capable AS 1280 external links are used to approximate the neighborhood of 1281 the source; the tree begins with links directly attaching 1282 the source to one or more inter-AS multicast forwarders. The 1283 approximating AS external links point in the reverse 1284 direction (i.e., towards the source), just as with the 1285 approximating summary links in Case 2. Also, as in Case 2, 1286 all links included in the tree must point in the reverse 1287 direction. The final datagram shortest-path tree is then 1288 produced (as always) by pruning those branches having no 1289 group members nor wild-card multicast receivers. 1291 As an example, suppose that a host on Network N12 (see 1292 Figure 4) originates a multicast datagram for Destination 1293 Group B. Assume that all external costs pictured are OSPF 1294 external type 1 metrics. Then any routers in Area 1 1295 receiving the datagram would build the datagram shortest- 1296 path tree pictured in Figure 10. Note that all links in the 1297 tree point in the reverse direction, towards the source. The 1298 tree indicates that the routers expect the datagram to enter 1299 the Autonomous System at Router RT7, and then to enter the 1300 area at Router RT4. 1302 Note that in those cases where the "best" inter-AS multicast 1303 forwarder is not directly attached to the area, the 1304 neighborhood of the source is actually approximated by the 1305 concatenation of a summary link and a multicast-capable AS 1306 external link. This is in fact the case in Figure 10. 1308 o N12 1309 | 1310 2| 1311 | 1312 o RT7 1313 | 1314 14| 1315 | 1316 o RT4 (W) 1317 | 1318 0| 1319 | 1320 o N3 (Mb) 1321 /|\ 1322 / | \ 1323 1/ | 1\ 1324 / 1| \ 1325 / | \ 1326 RT1 (Mb) o | o RT3 (W) 1327 o 1328 RT2 (Ma,Mb) 1330 Figure 10: Datagram shortest-path tree: Area 1, 1331 source N12, destination Group B. Note that 1332 reverse costs (i.e., toward origin) are 1333 used throughout. 1335 In Case 3 (datagram source in another AS) the requirement that 1336 all tree links point in the reverse direction (towards the 1337 source) accommodates the fact that summary links and AS external 1338 links already point in the reverse direction. This also leads to 1339 the requirement that the inter-AS multicast routing protocol 1340 operate in a reverse path forwarding fashion (see condition 2 of 1341 Section 4). Note that Reverse path forwarding can lead to sub- 1342 optimal routing when costs are configured asymmetrically. And it 1343 can even lead to non-delivery of multicast datagrams in the case 1344 of asymmetric reachability. 1346 Inter-AS multicast forwarders may end up calculating a 1347 forwarding cache entry's upstream node as being external to the 1348 AS. As an example, Router RT7 in Figure 10 will end up 1349 calculating an external router (via its external link to Network 1350 N12) as the upstream node for the datagram. This means that RT7 1351 must receive the datagram from a router in another AS before 1352 injecting the datagram into the MOSPF system. 1354 4.2. Stub area behavior 1356 AS external links are not imported into stub areas. Suppose that 1357 the source of a particular datagram lies outside of the 1358 Autonomous System, and that the datagram is forwarded into a 1359 stub area. In the stub area's datagram shortest-path tree the 1360 neighborhood of the datagram's source cannot be approximated by 1361 AS external links. Instead the neighborhood of the source is 1362 approximated by the default summary links (see Section 3.6 of 1363 [OSPF]) that are originated by the stub area's intra-area 1364 multicast forwarders. 1366 Except for this small change to the construction of a stub 1367 area's datagram shortest-path trees, all other MOSPF algorithms 1368 (e.g., merging with other areas' datagram shortest-path trees to 1369 form the forwarding cache) function the same for stub areas as 1370 they do for non-stub areas. 1372 4.3. Inter-AS multicasting in a core Autonomous System 1374 It may be the case that the MOSPF routing domain connects 1375 together many different Autonomous Systems, thereby serving as a 1376 "core Autonomous System" (e.g, the old NSFNet backbone). In this 1377 case, it could very well be that the majority of the MOSPF 1378 routers are also inter-AS multicast forwarders. Having each 1379 inter-AS multicast forwarder then declare itself a wild-card 1380 multicast receiver could very well waste considerable network 1381 bandwidth. However, as an alternative to declaring themselves 1382 wild-card multicast receivers, the inter-AS multicast routers 1383 could instead explicitly advertise all groups that they were 1384 interested in forwarding (to other "client" Autonomous Systems) 1385 in group-membership-LSAs. These advertised groups would have to 1386 be learned through an inter-AS multicast routing protocol (or 1387 possibly even statically configured). 1389 This in essence allows the clients of the core Autonomous System 1390 to advertise their group membership into the core. However, 1391 since any client MOSPF domains will still have their inter-AS 1392 multicast forwarders configured as wild-card multicast 1393 receivers, this advertisement will be asymmetric: the core will 1394 not advertise its or others' group membership to the clients. 1395 The achieves the same inter-AS multicast routing architecture 1396 that MOSPF uses for inter-area multicast routing (see Figure 5). 1398 5. Modelling internal group membership 1400 A MOSPF router may itself contain multicast applications. A typical 1401 example of this is a UNIX workstation that doubles as a multicast 1402 router. This section concerns two alternative ways of representing 1403 the group membership of the MOSPF router's internal applications. 1404 Both representations have advantages. For maximum flexibility, the 1405 MOSPF forwarding algorithm (see Section 11) has been specified so 1406 that either representation can be used in a MOSPF router (and in 1407 fact, both representations can be used at once, depending on the 1408 application). 1410 The first representation is based on the paradigm presented in RFC 1411 1112. In this case, an application joins a multicast group on one or 1412 more specific physical interfaces. The application then receives a 1413 multicast datagram if and only if it is received on one of the 1414 specified interfaces. If a datagram is received on multiple 1415 specified interfaces, the application receives multiple copies. 1416 Figure 11 shows this algorithm as it is implemented in (modified) 1417 BSD UNIX kernels. The figure shows the processing of a multicast 1418 datagram, starting with its reception on a particular interface. 1419 First copies of the datagram are given to those applications that 1420 have joined on the receiving interface. Then the forwarding decision 1421 (pictured as a box containing a question mark) is made, and the 1422 packet is (possibly) forwarded out certain interfaces. If these 1423 interfaces are not capable of receiving their own multicasts, a copy 1424 of the datagram must be internally looped back to appropriately 1425 joined applications. 1427 The advantages to the RFC 1112 representation are as follows: 1429 o It is the standard for the way an IP host joins multicast 1430 groups. It is simplest to use the same membership model for 1431 +-------+ 1432 |receive| 1433 +-------+ 1434 | 1435 |---> To application 1436 | 1437 +-------------------+ 1438 |forwarding decision| 1439 +-------------------+ 1440 | 1441 / \ 1442 /---\----> To application 1443 / \------> To application 1444 / \ 1445 / \ 1446 +--------+ +--------+ 1447 |transmit| |transmit| 1448 +--------+ +--------+ 1450 Figure 11: RFC 1112 representation of internal 1451 group membership 1453 hosts and routers; most would consider an IP router to be a 1454 special case of an IP host anyway. 1456 o It is the way group membership has been implemented in BSD UNIX. 1457 Existing multicast applications are written to join multicast 1458 groups on specific interfaces. 1460 o The possibility of receiving multiple datagram copies may 1461 improve fault tolerance. If the datagram is dropped due to an 1462 error on the path to some interface, another interface may still 1463 receive a copy. 1465 o The ability to specify a particular receiving interface may 1466 improve the accuracy of IP multicast's expanding ring search 1467 mechanism (see Section 2.3.4). 1469 o Membership in the non-routable multicast groups (224.0.0.1 - 1470 224.0.0.255) must be on a per-interface basis. An OSPF router 1471 always belongs to 224.0.0.5 (AllSPFRouters) on its OSPF 1472 interfaces, and may belong to 224.0.0.6 (AllDRouters) on one or 1473 more of its OSPF interfaces. 1475 The second representation is MOSPF-specific. In this case, an 1476 application joins a multicast group on an interface-independent 1477 basis. In other words, group membership is associated with the 1478 router as a whole, not separately on each interface. The application 1479 then receives a copy of a multicast datagram if and only if the 1480 datagram would actually be forwarded by the MOSPF router. Figure 12 1481 shows how this algorithm would be implemented. The datagram is 1482 received on a particular interface. If the datagram is validated for 1483 forwarding (i.e., the receiving interface connects to the matching 1484 forwarding cache entry's upstream node), a copy of the datagram is 1485 also given to appropriately joined applications. Note that this 1486 model of group membership is not as general as the RFC 1112 model, 1487 in that it can only be implemented in MOSPF routers and not in 1488 arbitrary IP hosts. However, it has the following advantages: 1490 o The application does not need to have knowledge of the router 1491 interfaces. It does not need to know what kind or how many 1492 interfaces there are; this will be taken care of by the MOSPF 1493 protocol itself. 1495 o As long as any interface is operational, the application will 1496 continue to receive multicast datagrams. This happens 1497 automatically, without the application modifying its group 1498 membership. 1500 +-------+ 1501 |receive| 1502 +-------+ 1503 | 1504 | 1505 | 1506 +-------------------+ 1507 |forwarding decision|---> to application 1508 +-------------------+ 1509 | 1510 / \ 1511 / \ 1512 / \ 1513 / \ 1514 / \ 1515 +--------+ +--------+ 1516 |transmit| |transmit| 1517 +--------+ +--------+ 1519 Figure 12: MOSPF-specific representation of internal 1520 group membership 1521 o The application receives only one copy of the datagram. Using 1522 the RFC1112 representation, whenever an application joins on 1523 more than one interface (which must be done if the application 1524 does not want to rely on a single interface), multiple datagram 1525 copies will be received during normal operation. 1527 6. Additional capabilities 1529 This section describes the MOSPF configuration options that allow 1530 routers of differing capabilities to be mixed together in the same 1531 routing domain. Note that these options handle special circumstances 1532 that may not be encountered in normal operation. Default values for 1533 the configuration settings are specified in Appendix B. 1535 6.1. Mixing with non-multicast routers 1537 MOSPF routers can be mixed freely with routers that are running 1538 only the base OSPF algorithm (called non-multicast routers in 1539 the following). This allows MOSPF to be deployed in a piecemeal 1540 fashion, thereby speeding deployment and allowing 1541 experimentation with multicast routing on a limited scale. 1543 When a MOSPF router builds a datagram shortest-path tree, it 1544 omits all non-multicast routers. For example, in Figure 1, if 1545 Router RT6 was not a multicast router, the datagram shortest- 1546 path tree in Figure 3 would be built with a more circuitous 1547 branch through Router RT5, instead of through Router RT6. In 1548 addition, non-multicast routers do not participate in the 1549 flooding of the new group-membership-LSAs. This adheres to the 1550 general principle that a router should not have to handle those 1551 link state advertisements whose format (or contents) the router 1552 does not understand. 1554 Mixing MOSPF routers with non-multicast routers creates a number 1555 of potential problems. Certain mixings of MOSPF and non- 1556 multicast routers can cause multicast datagrams to take 1557 suboptimal paths, or in other cases can lead to the non-delivery 1558 of multicast datagrams. In addition, mixing MOSPF routers and 1559 non-multicast routers can cause the paths of multicast datagrams 1560 to diverge radically from the path of unicast datagrams. Such 1561 divergences can make routing problems harder to debug. 1563 In particular, the following specific difficulties may arise 1564 when mixing MOSPF routers with non-multicast routers: 1566 o Even though there is unicast connectivity to a destination, 1567 there may not be multicast connectivity. For example, if 1568 Router RT10 in Figure 1 becomes a non-multicast router, the 1569 group member connected to Network N11 will no longer be able 1570 to receive multicasts sourced by Host H2. But the two hosts 1571 will be able to exchange unicasts (e.g., ICMP pings). 1573 o When the Designated Router for a multi-access network is a 1574 non-multicast router, the network will not be used for 1575 forwarding multicast datagrams. For example, if in Figure 1 1576 Router RT4 is Designated Router for Network N3, and RT4 is 1577 non-multicast, Network N3 will not be used to forward IP 1578 multicasts. This would mean that multicast datagrams 1579 originated by Hosts H2 and H3 would not be forwarded beyond 1580 their local network (N4), even though it seems that the 1581 needed multicast connectivity exists. 1583 o When forwarding multicast datagrams between areas, mixing of 1584 MOSPF routers and non-multicast routers in the source area 1585 may cause unexpected loss of multicast connectivity. This is 1586 because in the inter-area routing of multicast datagrams the 1587 neighborhood of the datagram's source is approximated by 1588 OSPF summary links, and OSPF summary-LSAs do not carry 1589 indications/guarantees of the summarized path's multicast 1590 routing capability. 1592 6.2. Assigning multiple IP networks to a physical network 1594 Assigning multiple IP networks/subnets to a single physical 1595 network causes some confusion in MOSPF. This is because the 1596 underlying OSPF protocol treats these IP networks/subnets as 1597 entirely separate entities, originating separate network-LSAs 1598 for each and forming separate adjacencies for each, while IGMP 1599 recognizes only the single underlying physical network. Adding 1600 to the problem is the fact that when a multicast datagram is 1601 received from such a multiply-addressed physical wire, there is 1602 no good way to choose the datagram's upstream node (which must 1603 be done in order to make the forwarding decision; see Section 11 1604 for details). As a result, unless this situation is dealt with 1605 through configuration, unwanted replication of multicast 1606 datagrams may occur when they are forwarded over multiply- 1607 addressed wires. 1609 As a remedy, MOSPF allows multicast forwarding to be disabled on 1610 certain IP networks/subnets. When multicast forwarding is 1611 disabled on the wire's "extra" subnets (i.e., all but one), the 1612 extra subnets will not appear in datagram shortest-path trees, 1613 nor will they appear in group-membership-LSAs or forwarding 1614 cache entries. As a result, the possibility of unwanted datagram 1615 replication is eliminated. The actual disabling of multicast 1616 forwarding on a subnet is done through setting the 1617 IPMulticastForwarding parameter to disabled on all router 1618 interfaces connecting to the subnet (see Section B.2). 1620 6.3. Networks on Autonomous System boundaries 1622 Another complication can arise on IP networks/subnets that lie 1623 on the boundary of a MOSPF Autonomous System. Similar to the 1624 unicast situation where these networks may be running multiple 1625 IGPs (Interior Gateway Protocols), these networks may also be 1626 running multiple multicast routing protocols. It may then become 1627 impossible for a MOSPF router to determine whether a multicast 1628 datagram is being forwarded along the datagram shortest-path 1629 tree, or whether it has been inadvertently received from the 1630 other Autonomous System. Guessing wrong can lead to either 1631 unwanted replication or non-delivery of the multicast datagram. 1632 In addition, in order to prevent receiving duplicate multicast 1633 datagrams, group members on these boundary networks will 1634 probably want to declare their membership to one Autonomous 1635 System and not another. 1637 For example, consider the two Autonomous Systems pictured in 1638 Figure 13. Network X is on the boundary of both ASes. One 1639 possible multicast datagram path is shown; the datagram 1640 originates in a third Autonomous System, and is then delivered 1641 to both AS #1 and AS #2 separately. The paths through the two 1642 Autonomous Systems may end up having certain boundary networks 1643 as common segments. In Figure 13, Network X is common to both 1644 paths. In this case, if both Autonomous Systems were running 1645 (separate copies of) MOSPF, the same datagram would appear twice 1646 on Network X as a data-link multicast. This would cause 1647 duplicate datagrams to be received by any group members on 1648 Network X or downstream from Network X. 1650 MOSPF has two mechanisms to eliminate this replication of 1651 multicast datagrams. First, a system administrator can configure 1652 certain networks to forward multicast datagrams as data-link 1653 unicasts instead of data-link multicasts. This is done by 1654 setting the IPMulticastForwarding parameter to data-link unicast 1655 on those router interfaces attaching to the network (see Section 1656 B.2). As an example, in Figure 13 the routers in AS #2 could be 1657 configured so that Router C would send the multicast datagram 1658 out onto Network X as a data-link unicast addressed directly to 1659 Router D. Router D would accept this data-link unicast, but 1660 would reject any data-link multicast forwarded by Router A. This 1661 would eliminate replication of multicast datagrams downstream 1662 from Network X. In addition, if the IPMulticastForwarding 1663 parameter is set to data-link unicast on Network X, group 1664 membership will not be monitored on the network. This will 1665 <-Datagram path->* 1666 * * 1667 * * 1668 * .....*......... 1669 .........*..... | . * AS #2 1670 AS #1 * . |*****+---+ 1671 +---+*****|*----|RTC| 1672 |RTA|----*|* . +---+ 1673 +---+ . *|* . 1674 . *|* . 1675 . *|* . +---+ 1676 +---+ . *|*----|RTD| 1677 |RTB|----*|*****+---+ 1678 +---+*****| .....*.......... 1679 .........*.... | * 1680 * | * 1681 * Network X * 1682 * 1684 Figure 13: Networks on AS boundaries 1686 prevent group members attached directly to Network X from 1687 receiving multiple datagram copies, since group membership on 1688 the boundary network will be monitored from only one AS (AS #1 1689 in our example). 1691 It should be noted that forwarding IP multicasts as data-link 1692 unicasts has some disadvantages when three or more MOSPF routers 1693 are attached to the network. First of all, it is more work for a 1694 router to send multiple unicasts than a single multicast. 1695 Second, the multiple unicasts consume more network bandwidth 1696 than a single multicast. And last, it increases the delay for 1697 some group members since multiple unicasts also take longer to 1698 send than a single multicast. 1700 6.4. Recommended system configuration 1702 In order to make MOSPF's selection of routes more predictable, 1703 it is recommended that all routers in any particular OSPF area 1704 have the same multicast capabilities. Keeping areas homogeneous 1705 ensures that IP multicast packets will follow relatively the 1706 same path as IP unicasts. In contrast, while heterogeneous areas 1707 will function, and will probably be necessary at least during 1708 the initial introduction of multicast routing, such areas may 1709 produce seemingly sub-optimal and unexpected routes. For 1710 example, see Section 6.1 above for a detailed description of the 1711 possible pitfalls when mixing multicast and non-multicast 1712 routers. 1714 As for the other options presented above, to achieve the most 1715 predictable results it is recommended that a router interface's 1716 IPMulticastForwarding parameter be set to a value other than 1717 data-link multicast only when either a) multiple IP networks 1718 have been assigned to a single physical wire or b) multiple 1719 multicast routing protocols are running on the attached network. 1721 7. Basic implementation requirements 1723 An implementation of MOSPF requires the following pieces of system 1724 support. Note that this support is in addition to that required for 1725 the base OSPF implementation as outlined in Section 4.4 of [OSPF]. 1727 o Promiscuous multicast reception. In a multicast router, it is 1728 necessary to receive all IP multicasts at the data-link level. 1729 On those interfaces where IP multicast datagrams are 1730 encapsulated by a wide range of data-link multicast destination 1731 addresses (e.g, ethernet and FDDI), this is most easily 1732 accomplished by disabling any hardware filtering of multicast 1733 destinations (i.e., by "opening up" the interface's multicast 1734 filter). 1736 o Data-link multicast/broadcast detection. To avoid unwanted 1737 replication of multicast datagrams in certain exceptional 1738 conditions, it is necessary for the multicast router to 1739 determine whether a datagram was received as a data-link 1740 multicast/broadcast or as a data-link unicast, for later use by 1741 the MOSPF forwarding mechanism. See Section 6.3 for more 1742 details. 1744 o An implementation of IGMPv2. MOSPF uses the Internet Group 1745 Management Protocol (IGMP, documented in [RFC 1112] and 1746 [IGMPv2]) to monitor multicast group membership. See Section 9 1747 for details. 1749 8. Protocol data structures 1751 The MOSPF protocol is described herein in terms of its operation on 1752 various protocol data structures. These data structures are included 1753 for explanatory uses only, and are not intended to constrain a MOSPF 1754 implementation. Besides the data structures listed below, this 1755 specification will also reference the various data structures (e.g., 1756 OSPF interfaces and neighbors) defined in [OSPF]. 1758 In a MOSPF router, the following items are added to the list of 1759 global OSPF data structures described in Section 5 of [OSPF]: 1761 o Local group database. This database describes the group 1762 membership on all attached networks. This in turn determines 1763 the group-membership-LSAs that the router will originate, and 1764 the local delivery of multicast datagrams (see Sections 2.3.1 1765 and 10). 1767 o Forwarding cache. Each entry in the forwarding cache describes 1768 the path of a multicast datagram having a particular [source 1769 net, multicast destination] combination. These cache entries are 1770 calculated when building the datagram shortest-path trees. See 1771 Sections 2.3.4 and 11 for more details. 1773 o Multicast routing capability. Indicates whether the router is 1774 running the multicast extensions defined in this memo. A router 1775 running the multicast extensions must still run the base OSPF 1776 algorithm as set forth in [OSPF]. Such a router will continue to 1777 interoperate with non-multicast-capable OSPF routers when 1778 forwarding IP unicast traffic. 1780 o Inter-area multicast forwarder. Indicates whether the router 1781 will forward IP multicasts from one OSPF area to another. Such a 1782 router declares itself a wild-card multicast receiver in its 1783 non-backbone area router-LSAs (see Section 14.6), and also 1784 summarizes its attached areas' group membership to the backbone 1785 in group-membership-LSAs. When building inter-area datagram 1786 shortest-path trees, it is these routers that appear immediately 1787 adjacent to the datagram source at the root of the tree (see 1788 Section 3.2). Not all multicast-capable area border routers need 1789 be configured as inter-area multicast forwarders. However, 1790 whenever both ends of a virtual link are multicast-capable, they 1791 must both be configured as inter-area multicast forwarders (see 1792 Section 14.11). 1794 o Inter-AS multicast forwarder. Indicates whether the router will 1795 forward IP multicasts between Autonomous Systems. Such a router 1796 declares itself a wild-card multicast receiver in its router- 1797 LSAs (see Section 14.6). These routers are also assumed to be 1798 running some kind of inter-AS multicast protocol. They mark all 1799 external routes that they import into the OSPF domain as to 1800 whether they provide multicast connectivity (see Section 14.9). 1801 When building inter-AS multicast datagram trees, it is these 1802 routers that appear immediately adjacent to the datagram source 1803 at the root of the tree. 1805 8.1. Additions to the OSPF area structure 1807 The OSPF area data structure is described in Section 6 of 1808 [OSPF]. In a MOSPF router, the following item is added to the 1809 OSPF area structure: 1811 o List of group-membership-LSAs. These link state 1812 advertisements describe the location of the area's multicast 1813 group members. Group-membership-LSAs are flooded throughout 1814 a single area only. Area border routers also summarize their 1815 attached areas' membership by originating group-membership- 1816 LSAs into the backbone area. For more information, see 1817 Sections 3.1 and 10. 1819 8.2. Additions to the OSPF interface structure 1821 The OSPF interface structure is described in Section 9 of 1822 [OSPF]. In a MOSPF router, the following items are added to the 1823 OSPF interface structure. Note that the IPMulticastForwarding 1824 parameter is really a description of the attached network. As 1825 such, it should be configured identically on all routers 1826 attached to a common network; otherwise incorrect routing of 1827 multicast datagrams may result[10]. 1829 o IPMulticastForwarding. This configurable parameter indicates 1830 whether IP multicasts should be forwarded over the attached 1831 network, and if so, how the forwarding should be done. The 1832 parameter can assume one of three possible values: disabled, 1833 data-link multicast and data-link unicast. When set to 1834 disabled, IP multicast datagrams will not be forwarded out 1835 the interface. When set to data-link multicast, IP multicast 1836 datagrams will be forwarded as data-link multicasts. When 1837 set to data-link unicast, IP multicast datagrams will be 1838 forwarded as data-link unicasts. The default value for this 1839 parameter is data-link multicast. The other two settings are 1840 for use in the special circumstances described in Sections 1841 6.2 and 6.3. When set to disabled or to data-link unicast, 1842 IGMP group membership is not advertised for the attached 1843 network. 1845 8.3. Additions to the OSPF neighbor structure 1847 The OSPF neighbor structure is defined in Section 10 of [OSPF]. 1848 In a MOSPF router, the following items are added to the OSPF 1849 neighbor structure: 1851 o Neighbor Options. This field was already defined in the OSPF 1852 specification. However, in MOSPF there is a new option which 1853 indicates the neighbor's multicast capability. This new 1854 option is learned in the Database Exchange process through 1855 reception of the neighbor's Database Description packets, 1856 and determines whether group-membership-LSAs are flooded to 1857 the neighbor. See the items concerning flooding in Section 1858 14 for a more detailed explanation. 1860 8.4. The local group database 1862 The local group database has already been introduced in Section 1863 2.3.1. The current section attempts a more precise definition. 1864 The local group database tracks the group membership of the 1865 router's directly attached networks. Database entries are 1866 created and maintained by the IGMP protocol. Database entries 1867 can cause group-membership-LSAs to be originated, which in turn 1868 enable the pruning of datagram shortest-path trees. The local 1869 group database also dictates the router's responsibility for the 1870 delivery of multicast datagrams to directly attached group 1871 members. 1873 Each entry in the local group database has two components: the 1874 multicast group, the attached network. A database lookup 1875 function is assumed to exist, so that given a [multicast group, 1876 attached network] pair, the matching database entry (if any) can 1877 be discovered. A database entry for [Group A, Network N1] exists 1878 if and only if there are Group A members currently located on 1879 Network N1. 1881 The two components of a local group database entry are defined 1882 as follows: 1884 o MulticastGroup. The multicast group whose members are being 1885 tracked by this entry. Each multicast group is represented 1886 as a class D IP address. For the semantics of multicast 1887 group membership, see [RFC 1112]. 1889 o AttachedNetwork. Each database entry is concerned with the 1890 group members belonging to a single attached network. To get 1891 a complete picture of the local group membership (when for 1892 example building a group-membership-LSA), it may be 1893 necessary to consult multiple database entries, one for each 1894 attached network. 1896 8.5. The forwarding cache 1898 The forwarding cache has already been defined in Section 2.3. 1899 The current section attempts a more precise definition. Each 1900 entry in the forwarding cache indicates how a multicast datagram 1901 having a particular [source network, destination multicast 1902 group] will be forwarded. A forwarding cache entry is built on 1903 demand from the local group database and the datagram's 1904 shortest-path tree. For more details, consult Sections 2.3.4 and 1905 12. 1907 Each entry in the forwarding cache has five components: the 1908 multicast datagram's source network, the destination multicast 1909 group, the upstream node, the list of downstream interfaces and 1910 (possibly) a list of downstream neighbors. A forwarding cache 1911 entry is indexed by source network and destination multicast 1912 group. A lookup function is assumed to exist, so that given a 1913 multicast datagram with a particular [IP source, destination 1914 multicast group], a matching cache entry (if any) can be found. 1916 The five components of a forwarding cache entry are defined as 1917 follows: 1919 o Source network. The datagram's source network is described 1920 by a network/subnet/supernet number and its corresponding 1921 mask. The source network for a datagram is discovered via a 1922 routing table/database lookup of the datagram's IP source 1923 address, as described in Section 11.2. 1925 o Destination multicast group. The destination group to which 1926 matching datagrams are being forwarded. For the semantics of 1927 multicast group membership, see [RFC 1112]. 1929 o Upstream node. The attached network/neighboring router from 1930 which the datagram must be received. If received from a 1931 different attached network/neighboring router, the matching 1932 datagram is dropped instead of forwarded. This prevents 1933 unwanted replication of multicast datagrams. It is possible 1934 that the upstream node is unspecified (i.e., set to NULL). 1935 In this case, matching datagrams will always be dropped, no 1936 matter where they are received from. It is also possible 1937 that the upstream node is specified as the placeholder 1938 EXTERNAL. This means that the datagram must be received on a 1939 non-MOSPF interface in order to be forwarded. 1941 o List of downstream interfaces. These are the router 1942 interfaces that the matching datagram should be forwarded 1943 out of (assuming that the datagram was received from 1944 upstream node). Each interface is also listed with a TTL 1945 value. The TTL value is the minimum number of hops necessary 1946 to reach the closest (in terms of router hops) group member. 1947 This allows the router to drop datagrams that have no chance 1948 of reaching a destination group member. 1950 o List of downstream neighbors. When the datagram is to be 1951 forwarded out a non-broadcast multi-access network, or if 1952 the interface's IPMulticastForwarding parameter is set to 1953 data-link unicast, the datagram must be forwarded separately 1954 to each downstream neighbor (see Sections 2.3.3 and 6.3). As 1955 done for downstream interfaces, each downstream neighbor is 1956 specified together with the smallest TTL that will actually 1957 reach a group member. 1959 9. Interaction with the IGMP protocol 1961 MOSPF uses the IGMP protocol (see [RFC 1112] and [IGMPv2]) to 1962 monitor multicast group membership. This document assumes that 1963 Version 2 of the IGMP protocol is being used [IGMPv2]. IGMPv2 elects 1964 a Querier on each network segment. The Querier periodically sends 1965 IGMP Membership Queries which in turn elicit IGMP Membership Reports 1966 from the network's multicast group members. These Membership Reports 1967 are then recorded in the MOSPF routers' local group databases (see 1968 Section 9.1). 1970 9.1. Receiving IGMP Membership Reports 1972 Received Membership Reports are processed by all MOSPF routers 1973 on a given network segment. However, it is the sole 1974 responsibility of the network's Designated Router to distribute 1975 the network's group membership information throughout the 1976 routing domain, by originating group-membership-LSAs (see 1977 Section 10). 1979 An IGMP Membership Report concerns membership in a single IP 1980 multicast group (call it Group A). The Report is sent to the 1981 Group A address so that other group members may see the Report 1982 and avoid sending duplicates (see [RFC 1112] for details). When 1983 an IGMP Membership Report is received by a MOSPF router from a 1984 physical network segment, the following steps are executed: 1986 (1) When multiple IP networks have been assigned to the same 1987 physical network, the first thing that needs to be done is 1988 to associate an IP network with the received Membership 1989 Report. Of all the IP network/subnets associated with the 1990 physical network segment and having IPMulticastForwarding 1991 set to data-link multicast, choose the subnet whose MOSPF 1992 interface has the highest IP interface address. Call this 1993 subnet "Network N". 1995 (2) If the Report concerns a multicast group in the range 1996 224.0.0.1 - 224.0.0.255, the Report is discarded and 1997 processing stops. This range of multicast groups are for 1998 local use (single hop) only, and datagrams sent to these 1999 destinations are never forwarded by multicast routers. 2001 (3) Locate the entry for [Group A, Network N] in the local group 2002 database. If no such entry exists, create one. 2004 (4) If the router is the network's Designated Router, and a 2005 local group database entry was created in the previous step, 2006 it may be necessary to originate a new group-membership-LSA. 2008 See Section 10 for details. 2010 If the router stops hearing Membership Reports for a given 2011 group, the local group database entry will be deleted, as 2012 specified in [IGMPv2]. If the router is Designated Router for 2013 the associated network, the group-membership-LSA for the group 2014 must then be reoriginated, or if its contents are now empty, the 2015 group-membership-LSA should be flushed. 2017 9.2. Receiving IGMP Membership Queries 2019 If a MOSPF router has internal multicast applications, and if 2020 the applications have bound themselves to certain interfaces 2021 (using the RFC 1112 representation described in Section 5), then 2022 the MOSPF router responds to received Membership Queries by 2023 issuing Membership Reports. Identical to the operation of any IP 2024 host supporting multicast applications, the exact procedure for 2025 issuing these Membership Reports is specified in [RFC 1112] and 2026 [IGMPv2]. 2028 If instead all of its applications have joined groups in an 2029 interface-independent fashion (using the MOSPF-specific 2030 representation described in Section 5), the MOSPF router does 2031 not respond to Membership Queries. Instead, the MOSPF router 2032 communicates this membership information by originating 2033 appropriate group-membership-LSAs (see Section 10.1). 2035 10. Group-membership-LSAs 2037 Group-membership-LSAs provide the means of distributing membership 2038 information throughout the MOSPF routing domain. Group-membership- 2039 LSAs are specific to a single OSPF area (see Section 3.1). Each 2040 group-membership-LSA concerns a single multicast group. Essentially, 2041 the group-membership-LSA lists those networks which are directly 2042 connected to the LSA's originator and which contain one or more 2043 group members. For more details on how the group-membership-LSA 2044 augments the OSPF link state database, see Section 2.3.1. 2046 The creation of group-membership-LSAs is discussed in Section 10.1. 2047 The format of the group-membership-LSA is described in Section A.3. 2048 A router will originate a group membership-LSA for multicast group A 2049 when one or more of the following conditions hold: 2051 (1) The router is Designated Router on a network (call it Network 2052 X), the interface to Network X has its IPMulticastForwarding 2053 parameter set to data-link multicast (see Section B.2), and 2054 Network X contains one or more members of Group A. 2056 (2) The router is an inter-area multicast forwarder (see Section 2057 B.1), and one or more of the router's attached non-backbone 2058 areas contain Group A members. In this case, the router will 2059 originate a group-membership-LSA for Group A into the backbone. 2060 This is the way group membership is conveyed between areas (see 2061 Section 3.1). 2063 (3) The router itself has applications that are requesting 2064 membership in Group A, in an interface-independent fashion (see 2065 Section 5). 2067 As for all other types of OSPF link state advertisements (e.g, 2068 router-LSAs, network-LSAs, etc.), group-membership-LSAs are aged as 2069 they are held in a router's link state database. To prevent valid 2070 advertisements from "aging out", a router must refresh its self- 2071 originated group-membership-LSAs every LSRefreshTime interval, by 2072 incrementing their LS sequence numbers and reissuing them. In 2073 addition, when an event occurs that would alter one of the router's 2074 self-originated group-membership-LSAs, a new instance of the LSA is 2075 issued with an updated (i.e., incremented by 1) LS sequence number. 2076 Note however that a router is not allowed to originate two new 2077 instances of the same advertisement within MinLSInterval seconds. 2078 For that reason, occasionally advertisement originations will need 2079 to be deferred. Also, an event may occur that makes it inappropriate 2080 for the router to continue to originate a particular LSA. In that 2081 case, the router flushes the advertisement from the routing domain 2082 by "premature aging". For more information concerning the 2083 maintenance of LSAs, see Sections 12, 12.4, 14 and 14.1 of [OSPF]. 2085 When one of the following events occurs, it may be necessary for a 2086 router to (re)issue one or more group-membership-LSAs: 2088 (1) One of the router's interfaces changes state. For example, the 2089 router may have become Designated Router on a particular 2090 network, causing the router to start advertising the network's 2091 group membership to the rest of the MOSPF system in group- 2092 membership-LSAs. 2094 (2) The router receives an IGMP Membership Report, causing a new 2095 local group database entry to be formed (see Section 9.1). 2097 (3) One of the router's local group database entries "ages out", 2098 because it is no longer being refreshed by received IGMP 2099 Membership Reports (see Section 9). 2101 (4) The router is an inter-area multicast forwarder, and the group 2102 membership of one of the router's attached non-backbone areas 2103 changes. This is detected by the reception of a new, or the 2104 flushing of an old, group-membership-LSA into/from the non- 2105 backbone area's link state database. 2107 (5) The group membership of one of the router's internal 2108 applications changes. 2110 10.1. Constructing group-membership-LSAs 2112 This section details how to build a group-membership-LSA. The 2113 format of a group-membership-LSA is described in Section A.3. 2114 Each group-membership-LSA concerns a single multicast group. The 2115 body of the advertisement is a list of the local transit nodes 2116 (the router itself and directly attached transit networks) that 2117 contain group members. Section 10 listed the conditions 2118 requiring the (re)origination of a group-membership-LSA. Note 2119 that if the router is an area border router, it may be necessary 2120 to originate a separate group-membership-LSA for each attached 2121 area. 2123 The following defines the contents of a group-membership-LSA, as 2124 originated by Router X into Area A. It is assumed that the 2125 group-membership-LSA is to report membership in multicast group 2126 G: 2128 o The advertisement fields that are not type-specific (LS age, 2129 LS sequence number, LS checksum and length) are set 2130 according to Section 12.1 of [OSPF]. 2132 o The Options field of a group-membership-LSA is not processed 2133 on receipt. However, for consistency, the Option field in 2134 these advertisements should have its MC-bit set. The rest of 2135 the Options field is set according to [OSPF]. 2137 o The Link State ID is set to the group whose membership is 2138 being reported (Group G). 2140 o The Advertising Router is set to the OSPF Router ID of the 2141 router originating the advertisement (Router X). 2143 o The body of the advertisement is a list of local transit 2144 vertices that should be labelled with Group G membership 2145 (see Section 2.3.1). This list may include the advertising 2146 router itself, and any of the transit networks that are 2147 directly attached to said router. The following steps 2148 determine which of these transit vertices are actually 2149 included in the group-membership-LSA. Note that any 2150 particular vertex should be listed at most once, even though 2151 the following may indicate multiple reasons for a particular 2152 vertex to be listed. Also note that if no transit vertices 2153 are listed by the advertisement, the advertisement should 2154 not be (re)originated; if an instance of the advertisement 2155 already exists, it should then be flushed from the link 2156 state database using the premature aging procedure specified 2157 in Section 14.1 of [OSPF]. 2159 a. Consider those entries in the local group database that 2160 describe Group G membership (see Section 8.4). Consider 2161 each such entry in turn. Each entry references one of 2162 Router X's attached networks (call it Network N). If 2163 either Network N does not belong to Area A, or if Router 2164 X is not Network N's Designated Router[11], Network N 2165 should not be added to the group-membership-LSA, and the 2166 next local group database entry should be examined. 2167 Otherwise, if N is a stub network (e.g., Router X is the 2168 only OSPF router attached to N), Router X adds itself to 2169 the advertisement by adding a vertex with Vertex type 2170 set to 1 (router) and Vertex ID set to Router X's OSPF 2171 Router ID. Otherwise, N is a transit network. In this 2172 case, Network N should be added to the advertisement by 2173 adding a vertex with Vertex type set to 2 (network) and 2174 Vertex ID set to the IP address of Network N's 2175 Designated Router (i.e., Router X's IP interface address 2176 on Network N). 2178 b. If Router X itself has applications requesting Group G 2179 membership on an interface-independent basis (see 2180 Section 5), it should add itself to the advertisement by 2181 adding a vertex with Vertex type set to 1 (router) and 2182 Vertex ID set to Router X's OSPF Router ID. 2184 c. If Router X is an inter-area multicast forwarder (see 2185 Section 3.1), Area A is the backbone area (Area ID 2186 0.0.0.0), and at least one of Router X's attached non- 2187 backbone areas has Group G members (indicated by the 2188 presence of one or more advertisements in the areas' 2189 link state databases having Link State ID set to Group G 2190 and LS age set to a value other than MaxAge[12]), then 2191 Router X should add itself to the advertisement by 2192 adding a vertex with Vertex type set to 1 (router) and 2193 Vertex ID set to Router X's OSPF Router ID. 2195 Consider as an example the network configuration in Figure 4. 2196 Suppose that Router RT2 has been elected Designated Router for 2197 Network N3. Router RT2 would then originate (into Area 1) the 2198 following group-membership-LSA for Group B: 2200 ; RT2's group-membership-LSA for Group B 2202 LS age = 0 ;always true on origination 2203 Options = (E-bit|MC-bit) 2204 LS type = 6 ;group-membership-LSA 2205 Link State ID = Group B 2206 Advertising Router = RT2's Router ID 2207 Vertex type = 1 ;RT2 itself (for stub N2) 2208 Vertex ID = RT2's Router ID 2209 Vertex type = 2 ;Network N3 (since RT2 is DR) 2210 Vertex ID = RT2's IP interface address on N3 2212 10.2. Flooding group-membership-LSAs 2214 When MOSPF routers and non-multicast OSPF routers are mixed 2215 together in a routing domain, the group-membership-LSAs are not 2216 flooded to the non-multicast routers[13]. As a general design 2217 principle, optional OSPF advertisements are only flooded to 2218 those routers that understand them. 2220 A MOSPF router learns of its neighbor's multicast-capability at 2221 the beginning of the "Database Exchange Process" (see Section 2222 10.6 of [OSPF], receiving Database Description packets from a 2223 neighbor in state Exstart). A neighbor is multicast-capable if 2224 and only if it sets the MC-bit in the Options field of its 2225 Database Description packets. Then, in the next step of the 2226 Database Exchange process, group-membership-LSAs are included in 2227 the Database summary list sent to the neighbor (see Sections 7.2 2228 and 10.3 of [OSPF]) if and only if the neighbor is multicast- 2229 capable. 2231 When flooding group-membership-LSAs to adjacent neighbors, a 2232 MOSPF router looks at the neighbor's multicast-capability. 2233 Group-membership-LSAs are only flooded to multicast-capable 2234 neighbors. To be more precise, in Section 13.3 of [OSPF], 2235 group-membership-LSAs are only placed on the Link state 2236 retransmission lists of multicast-capable neighbors[14]. Note 2237 however that when sending Link State Update packets as 2238 multicasts, a non-multicast neighbor may (inadvertently) receive 2239 group-membership-LSAs. The non-multicast router will then simply 2240 discard the LSA (see Section 13 of [OSPF], receiving LSAs having 2241 unknown LS types). 2243 11. Detailed description of multicast datagram forwarding 2245 This section describes in detail the way MOSPF forwards a multicast 2246 datagram. The forwarding process has already been informally 2247 presented in Section 2.2. However, there are several obscure 2248 configuration options (e.g., the IPMulticastForwarding interface 2249 parameter) that have been presented elsewhere in this document, 2250 which may influence the forwarding process. This section gathers 2251 together all the influencing factors into a single algorithm. 2253 It is assumed in the following that the datagram under consideration 2254 has actually be received on one of the router's interfaces. Locally 2255 generated datagrams (i.e., originated by one of the router's 2256 internal applications) are handled instead by the algorithm in 2257 Section 11.3. 2259 Assume that the datagram's IP destination is Group G. The forwarding 2260 process then consists of the following steps: 2262 (1) Upon reception of the datagram, the MOSPF router notes the 2263 following parameters. These parameters are examined in later 2264 steps, to determine whether the datagram should be forwarded. 2266 a. The receiving MOSPF interface associated with the datagram. 2267 Based on the receiving physical interface, the receiving 2268 MOSPF interface is selected by the algorithm in Section 2269 11.1. 2271 b. Whether the datagram was received as a link-level 2272 multicast/broadcast or as a link-level unicast. This 2273 information is used later in Step 7 to help determine 2274 whether the datagram should be forwarded. 2276 (2) A copy of the datagram should be passed to each internal 2277 application that has joined Group G on the receiving MOSPF 2278 interface (see Section 5). 2280 (3) If the datagram's IP source address matches the receiving MOSPF 2281 interface's IP address, the datagram should not be forwarded 2282 further, and should instead be discarded, completing the 2283 forwarding process. This keeps the router's own locally 2284 originated datagrams from being mistakenly replicated, in those 2285 cases where the receiving MOSPF interface receives its own 2286 multicast transmissions. 2288 (4) If Group G falls into the range 224.0.0.1 through 224.0.0.255 2289 inclusive, the datagram should not be forwarded further. This 2290 range of addresses has been dedicated for use on a local network 2291 segment only. 2293 (5) Associate a source network (SourceNet) with the multicast 2294 datagram, as described in Section 11.2. If SourceNet cannot be 2295 determined (i.e., there is no available unicast route back to 2296 the datagram source), the datagram should not be forwarded 2297 further. 2299 (6) Look up the forwarding cache entry (see Section 8.5) matching 2300 the datagram's [SourceNet, Group G] combination. If the cache 2301 entry does not yet exist, one is built by the calculation in 2302 Section 12. In order for the datagram to be forwarded, the 2303 contents of the forwarding cache entry must be further verified 2304 against the received datagram's characteristics as follows: 2306 a. If the forwarding cache entry's upstream node is unspecified 2307 (i.e., NULL), then the datagram should not be forwarded 2308 further. 2310 b. Otherwise, suppose that the forwarding cache entry's 2311 upstream node is set to EXTERNAL. In this case, the datagram 2312 is forwarded further if and only if the receiving MOSPF 2313 interface is set to NULL (i.e., if and only if the datagram 2314 was received on a non-MOSPF interface). 2316 c. Otherwise, if the datagram's receiving MOSPF interface does 2317 not attach to the forwarding cache entry's upstream node, 2318 the datagram should not be forwarded further. 2320 (7) If the receiving MOSPF interface's IPMulticastForwarding 2321 parameter is set to data-link unicast, the datagram should be 2322 forwarded further only if it was received as a data-link 2323 unicast. 2325 (8) At this point the datagram is eligible for further forwarding. 2326 Before forwarding, the router checks to see whether it has any 2327 internal applications that have joined Group G on an interface- 2328 independent basis. If so, a copy of the datagram should be 2329 passed to each such requesting application process. 2331 (9) Examine each of the downstream interfaces listed in the 2332 forwarding cache entry. If the TTL in the datagram is greater 2333 than or equal to the TTL specified for the downstream interface, 2334 a copy of the datagram should be forwarded out the downstream 2335 interface. Before forwarding the datagram copy, the copy's TTL 2336 should be decremented by 1. On most interfaces, the datagram is 2337 forwarded as a data-link multicast/broadcast. The exact data- 2338 link encapsulation is dependent on the attached network's type: 2340 o On ethernet and IEEE 802.3 networks, the datagram is 2341 forwarded as a data-link multicast. The destination data- 2342 link multicast address is selected as an algorithmic 2343 translation of the IP multicast destination. See [RFC 1112] 2344 for details. 2346 o On FDDI networks, the datagram is forwarded as a data-link 2347 multicast. The destination data-link multicast address is 2348 selected as an algorithmic translation of the IP multicast 2349 destination. See [RFC 1390] for details. 2351 o On SMDS networks, the datagram is forwarded using the same 2352 SMDS address that is used by IP broadcast datagrams. See 2353 [RFC 1209] for details. 2355 o On networks that support broadcast, but not multicast (e.g., 2356 the Experimental Ethernet), the datagram is forwarded as a 2357 data-link broadcast. See [RFC 1112] for details. 2359 o On point-to-point networks, the datagram is forwarded in the 2360 same way that unicast datagrams are forwarded. See [RFC 2361 1112] for details. 2363 (10) 2364 Examine each of the downstream neighbors listed in the 2365 forwarding cache entry. If the TTL in the datagram is greater 2366 than or equal to the TTL specified for the downstream neighbor, 2367 a copy of the datagram should be forwarded to the downstream 2368 neighbor (as a data-link unicast). Before forwarding the 2369 datagram copy, the copy's TTL should be decremented by 1. 2371 ICMP error messages are never generated in response to received IP 2372 multicasts. In particular, ICMP destination unreachables and ICMP 2373 TTL expired messages are not generated by the above procedure if the 2374 router refuses to forward a multicast datagram. 2376 11.1. Associating a MOSPF interface with a received datagram 2378 A MOSPF interface must be associated with a received multicast 2379 datagram before it is forwarded (see Step 1a of Section 11). 2381 When there is only a single IP network assigned to the physical 2382 interface that received the datagram, the choice of receiving 2383 MOSPF interface is clear. When there are multiple logical IP 2384 networks attached to the receiving physical interface, the 2385 receiving MOSPF interface is selected as follows. Examine all of 2386 the MOSPF interfaces associated with the receiving physical 2387 interface. 2389 (1) If the IP source address of the datagram falls into one of 2390 the attached physical segment's IP subnets, choose the MOSPF 2391 interface connecting to that subnet. 2393 (2) Otherwise, discard those interfaces whose 2394 IPMulticastForwarding parameter has been set to disabled. 2395 The receiving MOSPF interface is then the remaining 2396 interface having the highest IP interface address (or NULL 2397 if there are no remaining interfaces)[15]. 2399 11.2. Locating the source network 2401 MOSPF forwarding cache entries are indexed by the datagram's 2402 source IP network/subnet/supernet. For this reason, whenever an 2403 IP multicast datagram is received, the IP network belonging to 2404 the datagram's IP source address must be found. This is 2405 accomplished by the following algorithm: 2407 Look up the OSPF routing table entry corresponding to the 2408 datagram's IP source address, as described in Section 11.1 of 2409 [OSPF]. If this routing table entry describes an OSPF intra- 2410 area or inter-area route, the source network is set to be the 2411 network defined by the routing table entry's Destination ID and 2412 Address Mask (see Section 11 of [OSPF]). Otherwise (i.e., the 2413 routing table entry specifies an external route, or there is no 2414 matching routing table entry), the list of matching AS- 2415 external-LSAs is examined. A matching AS-external-LSA is one 2416 that describes a network which contains the datagram's IP source 2417 address. The list of matching AS-external-LSAs is pruned in the 2418 following steps to determine the source network: 2420 (1) Those AS-external-LSAs with MC-bit clear (see Section A.1), 2421 or with LS age set to MaxAge, or which have been originated 2422 by unreachable AS boundary routers are discarded. 2424 (2) If there are still multiple AS-external-LSAs remaining, 2425 those specifying the best matching (i.e., most specific) 2426 network are selected. The source network is then set to the 2427 network/subnet/supernet (possibly even the default route) 2428 described by the best matching AS-external-LSAs. Note that 2429 AS-external-LSAs specifying a cost of LSInfinity are 2430 eligible for this best match, as long as their MC-bit is 2431 set.[16] 2433 It is possible that two different MOSPF routers may calculate 2434 the same multicast datagram's source network differently. For 2435 example, consider the network configuration shown in Figure 4. 2436 When calculating the source network for a datagram whose source 2437 is Network N10 and destination is Group Ma, Router RT11 would 2438 calculate the source network as Network N10 itself, while Router 2439 RT10 would calculate the source network as the aggregate of 2440 Networks N9-N11 and Host H1 (advertised in a single summary-LSA 2441 by Router RT11). However, despite the possibility of routers 2442 selecting different source networks, all routers will still 2443 agree on the datagram's shortest-path tree. 2445 External sources are treated differently in the above 2446 calculation since it is likely that the Internet will have 2447 separate multicast and unicast topologies for some time to come. 2448 When the multicast and unicast topologies do merge, the MC-bit 2449 will be set on all AS-external-LSAs and the above use of the 2450 LSInfinity metric (to indicate a route that is to be used for 2451 multicast traffic, but not unicast traffic), will no longer be 2452 necessary. At that time, the determination of source network for 2453 external sources will revert to the same simple routing table 2454 lookup that is used for internal sources. 2456 As an example of the logic for external sources, suppose a 2457 multicast datagram is received having the IP source address 2458 10.1.1.1. Suppose also that the three AS-external-LSAs shown in 2459 Table 3 are in the router's OSPF database. The OSPF routing 2460 table lookup would yield the network 10.1.1.0 with a mask of 2461 255.255.255.0, however the above calculation would choose a 2462 source network of 10.1.0.0 with a mask of 255.255.0.0, despite 2463 the fact that its matching LSA has a cost of LSInfinity. 2465 11.3. Forwarding locally originated multicasts 2467 This section describes how a MOSPF router forwards a multicast 2468 datagram that has been originated by one of the router's own 2469 internal applications. The process begins with one of the 2470 router's internal applications formatting and addressing the 2471 datagram. Forwarding the locally originated multicast then 2472 consists of the following steps: 2474 (1) Find the router interface whose IP address matches the 2475 datagram's source address. Multicast the datagram out that 2476 interface, according to the Host extensions for IP 2478 Network Mask Cost MC-bit 2479 ______________________________________________________ 2480 10.1.1.0 255.255.255.0 Type 1: 10 clear 2481 10.1.0.0 255.255.0.0 Type 2: LSInfinity set 2482 10.0.0.0 255.0.0.0 Type 2: 1 set 2484 Table 3: Sample AS-external-LSAs 2485 multicasting specified in [RFC 1112]. 2487 (2) Set the receiving MOSPF interface to that interface. 2489 (3) Execute the MOSPF forwarding process described in Section 2490 11, beginning with its Step 4. 2492 The above algorithm amounts to the router always multicasting 2493 the datagram out the source interface, and the executing the 2494 basic forwarding algorithm (in Section 11) as if the datagram 2495 had actually been received on the source interface. In those 2496 cases where the router receives its own multicast transmissions, 2497 unwanted replication is prevented by Step 3 of Section 11. In 2498 fact, this specification has purposely presented the forwarding 2499 algorithm (both for received and for locally originated 2500 datagrams) so that the correct forwarding actions are taken 2501 independent of whether the router receives its own multicast 2502 transmissions. 2504 12. Construction of forwarding cache entries 2506 This section details the building of a MOSPF forwarding cache entry. 2507 A high level discussion of this construction has already been 2508 presented in Sections 2.3, 2.3.1, 2.3.2, 3.2, and 4.1. Forwarding 2509 cache entries are built on demand, when a multicast datagram is 2510 received and no matching forwarding cache entry is found (see Step 6 2511 of Section 11). The parameters passed to the forwarding cache entry 2512 build process are: the datagram's source network (see Section 11.2) 2513 and its destination group address. These two parameters are called 2514 SourceNet and Group G in the following algorithm. The main steps in 2515 the build process are the following: 2517 (1) Allocate the forwarding cache entry. Initialize its Source 2518 network to SourceNet and its Destination multicast group to 2519 Group G. Initialize its upstream node and list of downstream 2520 interfaces to NULL. 2522 (2) For each Area A to which the calculating router is attached: 2524 a. Calculate Area A's datagram shortest-path tree. This 2525 calculation is described in Section 12.2 below. In many ways 2526 it is similar to the calculation of OSPF's intra-area 2527 routes, described in Section 16.1 of [OSPF]. The main 2528 differences between the multicast datagram shortest-path 2529 tree calculation and OSPF's intra-area unicast calculation 2530 are listed in Section 12.2.7 below. As a product of each 2531 area's datagram shortest-path tree, the forwarding cache 2532 entry's list of outgoing interfaces is (possibly) updated. 2534 b. Possibly set the forwarding cache entry's upstream node. 2535 Only one of the calculating router's attached areas will 2536 determine the forwarding cache entry's upstream node. This 2537 area is called the datagram's RootArea. The RootArea is 2538 initially set to NULL. After completing Area A's datagram 2539 shortest-path tree, the calculation in Section 12.2.6 will 2540 determine whether Area A is the datagram's RootArea. 2542 (3) Update the forwarding cache entry's list of outgoing interfaces, 2543 according to the contents of the local group database. This 2544 ensures multicast delivery to group members residing on the 2545 calculating router's directly attached networks. This process is 2546 described in Section 12.3. 2548 These main steps are described in more detail below. The detailed 2549 description begins with an explanation of the major data structure 2550 used by the datagram shortest-path tree calculation: The Vertex data 2551 structure. 2553 12.1. The Vertex data structure 2555 A datagram shortest-path tree is built by the Dijkstra or SPF 2556 algorithm. The algorithm is stated herein using graph-oriented 2557 language: vertices and links. Vertices are the area's routers 2558 and transit networks, and links are the router interfaces and 2559 point-to-point lines that connect them. Each vertex has the 2560 following state information attached to it. Basically, this 2561 information indicates the current best path from the SourceNet 2562 to the vertex, and the position of the vertex relative to the 2563 calculating router. Note that a separate datagram shortest-path 2564 tree is built for each area, and that the vertices described 2565 below are also specific to a single area (called Area A). 2567 o Vertex type. Set to 1 for routers, 2 for transit networks. 2568 Note that this coding matches the coding for vertices listed 2569 in the group-membership-LSA (see Section A.3). 2571 o Vertex ID. A 32-bit identifier for the vertex. For routers, 2572 set to the router's OSPF Router ID. For transit networks, 2573 set the IP address of the network's Designated Router. Note 2574 that this coding matches the coding for vertices listed in 2575 the group-membership-LSA (see Section A.3). 2577 o LSA. The link state advertisement describing the vertex' 2578 immediate neighborhood. Can be discovered by performing a 2579 database lookup in Area A's link state database (see Section 2580 12.2 of [OSPF]), with LS type set to Vertex type and Link 2581 State ID set to Vertex ID. 2583 o Parent. In the current best path from SourceNet to the 2584 vertex, the router/transit network immediately preceding the 2585 vertex. Note that the parent can change as better and better 2586 paths are found, up until the vertex is installed on the 2587 shortest-path tree. 2589 o IncomingLinkType. This parameter is set to the type of link 2590 that led to Vertex's inclusion on the shortest-path tree. 2591 Listed in order of decreasing preference[17], the possible 2592 types are: ILVirtual (virtual links), ILDirect (vertex is 2593 directly attached to SourceNet), ILNormal (either router- 2594 to-router or router-to-network links), ILSummary (OSPF 2595 summary links), ILExternal (OSPF AS external links), or 2596 ILNone (the vertex is not on the shortest-path tree). 2598 o AssociatedInterface/Neighbor. If the current best path from 2599 SourceNet to the vertex goes through the calculating router, 2600 this parameter indicates the calculating router's interface 2601 (or neighbor) which leads to the vertex. 2603 o Cost. The cost, in terms of the OSPF link state metric, of 2604 the current best path from SourceNet to the vertex. Note 2605 that if the cost of the path is a combination of both 2606 external type 2 and internal OSPF metrics, that the vertex' 2607 cost parameter reflects both cost components. Remember that 2608 the type 2 cost component is always more significant than 2609 the type 1 component. 2611 o TTL. If the current best path from SourceNet to vertex goes 2612 through the calculating router, TTL is set to the number of 2613 routers between the calculating router and the vertex. This 2614 includes the calculating router, but does not include the 2615 vertex itself. 2617 12.2. The SPF calculation 2619 This section details the construction of datagram shortest-path 2620 trees. Such a tree describes the path of a multicast datagram 2621 as it traverses an OSPF area. For a given datagram, each router 2622 in an OSPF area builds an identical tree. A router connected to 2623 multiple areas builds a separate datagram shortest-path tree for 2624 each area. 2626 The datagram shortest-path tree is built by the Dijkstra or SPF 2627 algorithm, which is the same algorithm used to discover OSPF's 2628 intra-area unicast routes (see Section 16.1 of [OSPF]). The 2629 algorithm is stated herein and in [OSPF] using graph-oriented 2630 language: vertices and links. Vertices are the area's routers 2631 and transit networks, and links are the router interfaces and 2632 point-to-point lines that connect them. Basically, the algorithm 2633 manipulates two lists of vertices: the candidate list and the 2634 forming shortest-path tree. The candidate list consists of those 2635 vertices to which paths have been discovered, but for which the 2636 optimality of the discovered paths is yet unknown. At each cycle 2637 of the algorithm, the vertex closest to the tree's root, yet 2638 still remaining on the candidate list, is moved from the 2639 candidate list to the shortest-path tree. Then the neighbors of 2640 the just processed vertex are examined for possible addition 2641 to/modification of the candidate list. The algorithm terminates 2642 when the candidate list is empty. 2644 The datagram shortest-path tree for Area A is constructed in the 2645 following steps. The datagram's SourceNet and its destination 2646 group G are inputs to the calculation (see Step 6 of Section 2647 11). Call the router performing the calculation Router RTX. At 2648 each step (and in the subordinate Sections 12.2.1 through 2649 12.2.6) LSAs from Area A's link state database are examined. In 2650 all cases, any LSA having LS age equal to MaxAge is ignored. The 2651 main body of the calculation is in Steps 4 and 5, which are 2652 repeated until the candidate list becomes empty: 2654 (1) Initialize the algorithm's data structures. Clear the 2655 shortest-path tree. Initialize the state of each vertex in 2656 Area A (i.e., the area's routers and transit networks) to: 2657 Parent set to NULL, IncomingLinkType set to ILNone and 2658 AssociatedInterface/Neighbor set to NULL. 2660 (2) Initialize the candidate list. One or more vertices are 2661 initially placed on the candidate list, depending on the 2662 location of SourceNet with respect to Area A and Router RTX. 2663 This breaks down into the following cases (which are named 2664 for later reference): 2666 o Case SourceIntraArea: SourceNet belongs to Area A. In 2667 this case, the candidate list is initialized as in 2668 Section 12.2.1. 2670 o Case SourceStubExternal: Area A is an OSPF stub area, 2671 and SourceNet is outside of Area A (either in another 2672 OSPF area or external to the OSPF routing domain). In 2673 this case, the candidate list is initialized as in 2674 Section 12.2.3. 2676 o Case SourceInterArea1: SourceNet belongs to an OSPF area 2677 that is not directly attached to Router RTX. In this 2678 case, the candidate list is initialized as in Section 2679 12.2.2. 2681 o Case SourceInterArea2: SourceNet does not belong to Area 2682 A, but it still belongs to an OSPF area that is directly 2683 attached to Router RTX. In this case, the candidate 2684 list is initialized as in Section 12.2.3. 2686 o Case SourceExternal: SourceNet is external to the OSPF 2687 routing domain. In this case, the candidate list is 2688 initialized as in Section 12.2.4. 2690 Two different routers in Area A may select different 2691 initialization cases above. For example, consider the 2692 network configuration shown in Figure 4. When calculating 2693 the Area 3 datagram shortest-path tree for a datagram whose 2694 source is Network N7 (e.g., from Host H5) and destination is 2695 Group Ma, Router RT11 would initialize the candidate list 2696 using Case SourceInterArea2 while Router RT9 would use Case 2697 SourceInterArea1. However, despite the possibility of 2698 routers selecting different cases, all routers in an area 2699 will still initialize the candidate list (and in fact, run 2700 the rest of the SPF calculation) identically. 2702 (3) If the candidate list is empty, the algorithm terminates. 2704 (4) Move the closest candidate vertex to the shortest-path tree. 2705 Select the vertex on the candidate list that is closest to 2706 SourceNet (i.e., has the smallest Cost value). If there are 2707 multiple possibilities, select transit networks over 2708 routers. If there are still multiple possibilities 2709 remaining, select the vertex having the highest Vertex ID. 2710 Call the chosen vertex Vertex V. Remove Vertex V from the 2711 candidate list, and install it on the shortest-path tree. 2713 Next, determine whether Vertex V has been labelled with the 2714 Destination multicast Group G. If so, it may cause the 2715 forwarding cache entry's list of outgoing 2716 interfaces/neighbors to be updated. See Section 12.2.6 for 2717 details. 2719 (5) Examine Vertex V's neighbors for possible inclusion in the 2720 candidate list. Consider Vertex V's LSA. Each link in the 2721 LSA describes a connection to a neighboring router/network. 2722 If the link connects to a stub network, examine the next 2723 link in the LSA. Otherwise, the link (Link L) connects to a 2724 neighboring transit node. Call this node Vertex W. Perform 2725 the following steps on Vertex W: 2727 a. If W is already on the shortest-path tree, or if W's LSA 2728 does not contain a link back to vertex V, or if W's LSA 2729 has LS age of MaxAge, or if W is not multicast-capable 2730 (indicated by the MC-bit in the LSA's Options field), 2731 examine the next link in V's LSA. 2733 b. Otherwise determine the cost to associate with the link 2734 from V to W. If SourceNet belongs to Area A (Case 2735 SourceIntraArea in Step 2), use the cost listed for Link 2736 L in V's LSA. Otherwise, use the link's reverse cost: 2737 Examine W's LSA, and find the cost listed for the link 2738 connecting back to V. Actually, when V and W are both 2739 routers, there may be multiple links between them. In 2740 this case, use the smallest cost listed in W's LSA for 2741 any of the links connecting back to V and having the 2742 same Type (as specified in the Router-LSA; must be 2743 either: point-to-point connection or virtual link) as 2744 Link L[18]. 2746 c. Calculate the cost from SourceNet to W, when using Link 2747 L. It is the sum of the cost of SourceNet to V (i.e., 2748 V's Cost parameter) plus the link cost calculated in 2749 Step 5b. Let this sum be Cost C. If W is not yet on the 2750 candidate list, install W on the candidate list, 2751 modifying its parameters as specified below (Step 5d). 2752 Otherwise, W is on the candidate list already. In this 2753 case, if: 2755 o C is less than W's current Cost, update W's 2756 parameters on the candidate list as specified below 2757 (Step 5d). 2759 o C is equal to W's current Cost, then the following 2760 tiebreakers are invoked. The type of Link L is 2761 compared to W's current IncomingLinkType, and 2762 whichever link has the preferred type is chosen (the 2763 preference order of link types is listed in Section 2764 12.1's definition of IncomingLinkType). If the link 2765 types are the same, then a link whose Parent is a 2766 transit network is preferred over one whose Parent 2767 is a router. If the links are still equivalent, the 2768 link whose Parent has the higher Vertex ID is 2769 chosen. Whenever Link L is chosen, W's parameters 2770 are modified as below (Step 5d). Whenever the 2771 previously discovered link is chosen, the next link 2772 in V's LSA is examined instead. 2774 o C is greater than W's current Cost, examine the next 2775 link in V's LSA. 2777 d. At this point, a better candidate path has been found to 2778 Vertex W, using Link L. Modify Vertex W's parameters 2779 accordingly. W's Parent is set to Vertex V. W's 2780 IncomingLinkType is set to ILVirtual if Link L is a 2781 virtual link, otherwise IncomingLinkType is set to 2782 ILNormal. W's Cost parameter is set to C. W's TTL and 2783 AssociatedInterface/Neighbor parameters are set 2784 according to one of the following cases: 2786 o Vertex V is the calculating router itself. In this 2787 case, W's TTL parameter is set to 1. If Link L is a 2788 virtual link, W's AssociatedInterface/Neighbor is 2789 set to NULL. Otherwise, W's 2790 AssociatedInterface/Neighbor is set to the non- 2791 virtual interface connecting the calculating router 2792 to W which has the smallest cost value. Note that, 2793 in the reverse cost (inter-area and inter-AS 2794 multicast) cases, this may not be the interface 2795 corresponding to Link L. However, since W is only 2796 concerned with the node it is receiving the datagram 2797 from (the upstream node; see Section 11), and not 2798 with the particular interface the datagram is 2799 received on, the calculating router is free to pick 2800 the sending interface when there are multiple 2801 connecting links. 2803 o Vertex V is upstream of the calculating router 2804 (i.e., V's AssociatedInterface/Neighbor is equal to 2805 NULL). In this case, Vertex W's TTL parameter is set 2806 to 0, and its AssociatedInterface/Neighbor is set to 2807 NULL. 2809 o V is a transit network, and is directly downstream 2810 from the calculating router (i.e., V's 2811 AssociatedInterface/Neighbor is non-NULL and V's TTL 2812 is set to 1). W is then one of the calculating 2813 router's neighbors. In this case, W's TTL parameter 2814 is also set to 1. If network V has been configured 2815 for data-link unicasting (see Section B.2) or if V 2816 is a non-broadcast network, W's 2817 AssociatedInterface/Neighbor is set to W itself (a 2818 neighbor of the calculating router). Otherwise, W's 2819 AssociatedInterface/Neighbor is set to the 2820 calculating router's interface to Network V. 2822 o Vertex V is downstream from the calculating router 2823 (i.e., V's AssociatedInterface/Neighbor is non- 2824 NULL), and either a) V is a router or b) V's TTL 2825 parameter is greater than 1. In these cases, W's 2826 AssociatedInterface/Neighbor parameter is copied 2827 directly from V. If V is a router, W's TTL 2828 parameter is set to V's TTL parameter incremented by 2829 one. If V is a transit network, W's TTL parameter is 2830 set directly to V's TTL parameter. 2832 (6) If the candidate list is non-empty, go to Step 4. Otherwise, 2833 the algorithm terminates. 2835 After the datagram shortest-path tree for Area A is complete, 2836 the calculating router (RTX) must decide whether Area A, out of 2837 all of RTX's attached areas, determines the forwarding cache 2838 entry's upstream node. This determination is described in 2839 Section 12.2.7. 2841 Examples of the above SPF calculation, with particular emphasis 2842 on the tiebreaking rules, are given in Appendix C. 2844 12.2.1. Candidate list Initialization: Case SourceIntraArea 2846 In this case, SourceNet belongs to Area A. The candidate 2847 list is then initialized as follows. Start with the LSA 2848 listed as Link State Origin in the matching OSPF routing 2849 table entry. If this is a non-multicast-capable router-LSA 2850 (i.e, its Options field has the MC-bit clear) the candidate 2851 list should be set to NULL (network-LSAs are accepted here 2852 regardless of their MC-bit setting). Otherwise, the vertex 2853 identified by the LSA is installed on the candidate list, 2854 setting its vertex parameters as follows: IncomingLinkType 2855 set to ILDirect, Cost set to 0, Parent to NULL and 2856 AssociatedInterface/Neighbor to NULL. 2858 As a consequence of this initialization, note that if 2859 SourceNet is a stub network, then the datagram shortest-path 2860 tree will not actually be rooted at the datagram source, but 2861 will instead be rooted at the MOSPF router that attaches the 2862 stub network to the rest of the MOSPF system. For example, 2863 consider the network configuration shown in Figure 4. When 2864 calculating the Area 2 datagram shortest-path tree for a 2865 datagram whose source is Network N7 (e.g., from Host H5) and 2866 destination is Group Ma, Router RT11 (and all other routers 2867 attached to Area 2) will begin with the candidate list set 2868 to Router RT8. As another example, the datagram shortest- 2869 path tree pictured in Figure 3 is really rooted at Router 2870 RT3 instead of Network N4. 2872 12.2.2. Candidate list Initialization: Case SourceInterArea1 2874 In this case, SourceNet belongs to an OSPF area that is not 2875 directly attached to the calculating router (RTX). The 2876 candidate list is then initialized as follows. Examine the 2877 Area A summary-LSAs advertising SourceNet. For each such 2878 summary-LSA: if both a) the MC-bit is set in the LSA's 2879 Options field and b) the advertised cost is not equal to 2880 LSInfinity, then the vertex representing the LSA's 2881 advertising area border router is added to the candidate 2882 list. An added vertex' state is initialized as: 2883 IncomingLinkType set to ILSummary, Cost to whatever is 2884 advertised in the LSA, Parent to NULL and 2885 AssociatedInterface/Neighbor to NULL. 2887 For example, consider the network configuration shown in 2888 Figure 4. When calculating the Area 1 datagram shortest- 2889 path tree for a datagram whose source is Network N7 (e.g., 2890 from Host H5) and destination is Group Ma, Router RT2 would 2891 initialize the candidate list to contain the two area border 2892 routers RT3 (with a cost of 20) and RT4 (with a cost of 19). 2893 See Figure 6 for more details. 2895 12.2.3. Candidate list Initialization: Cases SourceInterArea2 2896 and SourceStubExternal 2898 In case SourceInterArea2, SourceNet belongs to an OSPF area 2899 other than Area A, but one that is still directly attached 2900 to the calculating router (RTX). In case 2901 SourceStubExternal, Area A is a stub area and SourceNet is 2902 outside of Area A (either in another OSPF area or external 2903 to the OSPF routing domain). In either case the candidate 2904 list is then initialized in the following two steps: 2906 (1) Find the Area A summary-LSA that best matches SourceNet, 2907 excluding those summary-LSAs specifying cost LSInfinity 2908 or having unreachable Advertising Routers[19]. A 2909 matching summary-LSA is one that advertises a range of 2910 addresses containing SourceNet; the best matching is as 2911 usual the most specific match. Let SourceRange be the 2912 network described by the best matching summary-LSA. 2914 (2) Similar to the logic in the SourceInterArea1 case, 2915 examine all the Area A summary-LSAs which advertise 2916 SourceRange. For each such summary-LSA: if both a) the 2917 MC-bit is set in the LSA's Options field, b) the 2918 advertised cost is not equal to LSInfinity and c) the 2919 Advertising Router is reachable, then the vertex 2920 representing the LSA's Advertising Router is added to 2921 the candidate list. An added vertex' state is 2922 initialized as: IncomingLinkType set to ILSummary, Cost 2923 to whatever is advertised in the LSA, Parent to NULL and 2924 AssociatedInterface/Neighbor to NULL. 2926 The reason why SourceRange is used, instead of simply using 2927 SourceNet (as was done in case SourceInterArea1), is that 2928 routing information may have been collapsed at area 2929 boundaries. In order for Area A's area border routers and 2930 its internal routers to construct the same Area A datagram 2931 shortest-path tree, they must both start at SourceRange - 2932 Area A's internal routers know nothing about SourceNet. Note 2933 that SourceRange is not discovered simply by looking at the 2934 calculating router's configured set of area address ranges, 2935 in order to avoid dependence on the configured area address 2936 ranges being synchronized across all area border routers. 2938 For example, consider the network configuration shown in 2939 Figure 4. When calculating the Area 2 datagram shortest- 2940 path tree for a datagram whose source is Network N11 and 2941 destination is Group Ma, Router RT11 would calculate 2942 SourceRange to be the collection: Networks N9-N11 and Host 2943 H1. It would then initialize the candidate list to contain 2944 itself (RT11) only, with an associated Cost of 1 (since RT11 2945 is advertising Networks N9-N11 and Host H1 in a summary-LSA 2946 with a cost of 1). 2948 12.2.4. Candidate list Initialization: Case SourceExternal 2950 In this case, SourceNet is external to the OSPF routing 2951 domain. The candidate list is then initialized as follows. 2952 Note that an attempt may be made to add a Vertex W to the 2953 candidate list when W already belongs to the candidate list. 2954 When this happens, W's vertex parameters are updated if the 2955 Cost parameter it would be added with is better[20] (closer 2956 to SourceNet) than its previous value. When the costs are 2957 the same, W's parameters are still modified if the 2958 IncomingLinkType it would be added with is better (see 2959 IncomingLinkType's definition in Section 12.1) than its 2960 previous value. 2962 For each AS-external-LSA advertising SourceNet, the 2963 following steps are performed: 2965 o If the AS-external-LSA's MC-bit is clear or if its 2966 advertising router is not reachable, then the AS- 2967 external-LSA is not used. AS-external-LSAs having their 2968 MC-bit set and advertising a cost of LSInfinity can be 2969 used; these LSAs describe paths that can be used for 2970 multicast, but not unicast, data traffic (see Section 2971 11.2). 2973 o If the AS-external-LSA's Forwarding address field is 2974 0.0.0.0, the following vertices are added to the 2975 candidate list. If the Advertising AS boundary router 2976 (call it ASBR) belongs to Area A, the vertex 2977 representing the AS boundary router is added to the 2978 candidate list using parameters: IncomingLinkType set to 2979 ILExternal, Cost to whatever is advertised in the LSA, 2980 Parent to NULL and AssociatedInterface/Neighbor to NULL. 2981 Then, regardless of whether ASBR belongs to Area A, all 2982 Area A area border routers that are advertising 2983 reachable multicast-capable (MC-bit set) type 4 2984 summary-LSAs for ASBR are added to the candidate list. 2985 Each such area border router is added with the 2986 parameters: IncomingLinkType set to ILSummary, Cost to 2987 the sum of whatever is advertised in the type 4 2988 summary-LSA plus the value in the original AS-external- 2989 LSA, Parent to NULL and AssociatedInterface/Neighbor to 2990 NULL. 2992 o If the AS-external-LSA's Forwarding address field is 2993 non-zero, the Forwarding address is looked up in the 2994 OSPF routing table. Then processing breaks into one of 2995 the following cases: 2997 o The Forwarding address is not usable. In this case, 2998 nothing is added to the candidate list. The 2999 Forwarding address is not usable if either it has no 3000 matching routing table entry, or if the matching 3001 routing table entry is neither of type intra-area 3002 nor of type inter-area. 3004 o The Forwarding address belongs to Area A[21]: the 3005 Forwarding address' matching routing table entry has 3006 Path-type of intra-area and its Associated area is 3007 Area A. In this case, the vertex represented by the 3008 matching routing table entry's Link State Origin 3009 field is added to the candidate list (assuming that 3010 the vertex is multicast-capable). The vertex is 3011 added with the parameters: IncomingLinkType set to 3012 ILExternal, Cost to whatever was advertised in the 3013 original AS-external-LSA, Parent to NULL and 3014 AssociatedInterface/Neighbor to NULL. 3016 o The Forwarding address belongs to an area that is 3017 not attached to Router RTX[22]: the Forwarding 3018 address' matching routing table entry has Path-type 3019 of inter-area. Call the network represented by the 3020 matching routing table entry ForwardNet. For each 3021 reachable multicast-capable summary-LSA (in Area A) 3022 advertising ForwardNet, add the LSA's advertising 3023 area border router to the candidate list using 3024 parameters: IncomingLinkType set to ILSummary, Cost 3025 to the sum of whatever is advertised in the 3026 summary-LSA plus the value in the original AS- 3027 external-LSA, Parent to NULL and 3028 AssociatedInterface/Neighbor to NULL. 3030 o The Forwarding address belongs to another one of 3031 Router RTX's attached areas[23]: the Forwarding 3032 address' matching routing table entry has Path-type 3033 of intra-area and its associated Area is other than 3034 Area A. Call the network represented by the 3035 matching routing table entry ForwardNet. First find 3036 the Area A summary-LSA that best matches ForwardNet, 3037 excluding those summary-LSAs specifying cost 3038 LSInfinity or having unreachable Advertising 3039 Routers. Let ForwardRange be the network described 3040 by the best matching summary-LSA. Then, for each 3041 reachable multicast-capable summary-LSA (in Area A) 3042 advertising ForwardRange, add the LSA's advertising 3043 area border router to the candidate list using 3044 parameters: IncomingLinkType set to ILSummary, Cost 3045 to the sum of whatever is advertised in the 3046 summary-LSA plus the value in the original AS- 3047 external-LSA, Parent to NULL and 3048 AssociatedInterface/Neighbor to NULL. 3050 The above calculation can be restated as follows. Each of 3051 Area A's inter-area multicast forwarders and inter-AS 3052 multicast forwarders are examined. Those that have 3053 multicast-capable paths to SourceNet (represented as either 3054 a multicast-capable AS external link or the concatenation of 3055 a Type 4 summary link and a multicast-capable AS external 3056 link) are added to the candidate list as router vertices. 3057 (It is possible that, when considering a router that is both 3058 an inter-area multicast forwarder and an inter-AS multicast 3059 forwarder, two equal cost paths exist to SourceNet, one an 3060 AS external link and the other a concatenation of a Type 4 3061 summary link and an AS external link. In this case, the 3062 concatenation of the Type 4 summary link and the AS external 3063 link is preferred). The added vertex' state is set as 3064 follows: IncomingLinkType set to ILSummary if the path is 3065 represented as a concatenation of a Type 4 summary link and 3066 an AS external link, IncomingLinkType set to ILExternal 3067 otherwise, Cost set to the cost of the shortest path from 3068 vertex to SourceNet, Parent set to NULL and 3069 AssociatedInterface/Neighbor set to NULL. 3071 For example, consider the network configuration shown in 3072 Figure 4. When calculating the Area 2 datagram shortest- 3073 path tree for a datagram whose source is Network N14 and 3074 destination is Group Ma, the candidate list would be 3075 initialized to the two routers RT7 at a cost of 14 and RT10 3076 at a cost of 19. This assumes that the external costs 3077 pictured in Figure 4 are external type 1s. 3079 12.2.5. Processing labelled vertices 3081 When encountered during the SPF calculation, vertices 3082 labelled with the destination multicast group (Group G) may 3083 cause the forwarding cache entry's list of downstream 3084 interfaces/neighbors to be modified. A Vertex V in Area A 3085 is labelled with Group G if and only if at least one of the 3086 following holds: 3088 (1) V is a router, and its router-LSA indicates that it is a 3089 wild-card multicast receiver (i.e., bit W in its 3090 router-LSA is set). This may be true when V is an 3091 inter-area or inter-AS multicast forwarder. 3093 (2) V is listed in the body of a group membership-LSA. In 3094 particular, find the originator of Vertex V's LSA; call 3095 it Router Y. Then find the group-membership-LSA in Area 3096 A's link state database which has Link State ID = Group 3097 G and Advertising Router = Router Y (see Section A.3). 3098 If this group-membership-LSA exists, and if Vertex V is 3099 listed in the body of the LSA (see Sections 10 and A.3), 3100 then Vertex V is labelled with Group G. 3102 When Vertex V is added to the shortest-path tree in Step 4 3103 of Section 12.2, and if Vertex V is both downstream from the 3104 calculating router (i.e., Vertex V's 3105 AssociatedInterface/Neighbor is non-NULL) and labelled with 3106 Group G, then Vertex V's AssociatedInterface/Neighbor is 3107 added to the forwarding cache entry's list of downstream 3108 interfaces/neighbors. In addition, Vertex V's TTL value is 3109 attached to the added downstream interface/neighbor. If the 3110 particular interface/neighbor had already been added to the 3111 list of downstream interfaces/neighbors, the list is simply 3112 modified by setting the downstream interface/neighbor's TTL 3113 value to the minimum of its existing TTL value and Vertex 3114 V's TTL value. 3116 12.2.6. Merging datagram shortest-path trees 3118 After the datagram shortest-path tree for Area A is 3119 complete, the calculating router (RTX) must decide whether 3120 Area A, out of all of its attached areas, determines the 3121 forwarding cache entry's upstream node. This is done by 3122 examining RTX's position on the Area A datagram shortest- 3123 path tree, which is in turn described by RTX's Area A Vertex 3124 data structure. If RTX's Vertex parameter IncomingLinkType 3125 is either ILNone (RTX is not on the tree), ILVirtual or 3126 ILSummary, then some area other than Area A will determine 3127 the upstream node. Otherwise, Area A might possibly 3128 determine the upstream node (i.e., may be selected the 3129 RootArea), depending on the following tiebreakers[24]: 3131 o If RootArea has not been set, then set RootArea to Area 3132 A. Otherwise, compare the present RootArea to Area A in 3133 the following: 3135 o Choose the area that is "nearest to the source". Nearest 3136 to the source depends on each area's candidate list 3137 initialization case, as it occurs in Step 2 of Section 3138 12.2. The initialization cases, listed in order of 3139 decreasing preference (or nearest to farthest) are: 3140 SourceIntraArea, SourceInterArea2, SourceInterArea1, 3141 SourceExternal and SourceStubExternal. As an example, 3142 consider the network configuration shown in Figure 4. 3143 When calculating the datagram shortest-path tree for a 3144 datagram whose source is Network N7 (e.g., from Host H5) 3145 and destination is Group Ma, Router RT11 would set its 3146 RootArea to Area 2 (Case SourceIntraArea) instead of 3147 Area 3 (Case SourceInterArea2) or the backbone Area 0 3148 (Case SourceInterArea). 3150 o If there are still two equally good areas, and one of 3151 them is the backbone, set RootArea to the backbone (Area 3152 0). 3154 o If there are still two equally good areas, set RootArea 3155 to the area whose datagram shortest-path tree provides 3156 the shortest path from SourceNet to RTX. This is a 3157 comparison of RTX's Vertex parameter Cost in the two 3158 areas. 3160 o If there are still two equally good areas, set RootArea 3161 to one with the highest OSPF Area ID. 3163 If the above has set the RootArea to be Area A, the 3164 forwarding cache entry's upstream node must be set 3165 accordingly. This setting depends on the IncomingLinkType in 3166 RTX's Area A Vertex structure. If IncomingLinkType is equal 3167 to ILDirect, the upstream node is set to the appropriate 3168 directly-connected stub network. If equal to ILNormal, the 3169 upstream node is set to the Parent field in RTX's Area A 3170 Vertex structure. If equal to ILExternal, the upstream node 3171 is set to the placeholder EXTERNAL. 3173 12.2.7. Comparison to the unicast SPF calculation 3175 There are many similarities between the construction of a 3176 multicast datagram's shortest-path trees in Section 12.2 and 3177 OSPF's intra-area route calculation for unicast traffic 3178 (Section 16.1 of [OSPF]). Both have been described in terms 3179 of Dijkstra's algorithm. However, there are some 3180 differences. The major differences are listed below: 3182 o In the multicast case, the datagram SPF calculation is 3183 rooted at the datagram's source. In the unicast case, 3184 each router is the root of its own unicast intra-area 3185 SPF calculation. 3187 o In the multicast case, the datagram shortest-path tree 3188 is a true tree; i.e., between any two nodes on the tree 3189 there is one path. However, due to the provision for 3190 equal-cost multipath in [OSPF], the unicast SPF 3191 calculation may add additional links to the shortest- 3192 path tree. 3194 o In order to avoid unwanted replication of multicast 3195 datagrams, MOSPF ensures that, for any given datagram, 3196 each router builds the exact same datagram shortest-path 3197 tree. This forces two differences from the unicast SPF 3198 calculation. First, it eliminates the possibility of 3199 equal-cost multipath. Secondly, when the MOSPF system 3200 contains multiple alternate paths, the algorithm must 3201 ensure that each MOSPF router deterministically chooses 3202 the same alternative. For this reason, tie-breaking 3203 mechanisms have been specified in Steps 2, 4 and 5b of 3204 Section 12.2. 3206 o The calculation of datagram shortest path trees takes 3207 into account only those links that connect transit nodes 3208 (i.e, router to router or router to transit network 3209 links). The unicast SPF calculation in Section 16.1 of 3210 [OSPF] must additionally examine links to stub networks, 3211 although this is done after all the transit links are 3212 examined. 3214 o While both the multicast and unicast trees select 3215 shortest paths on the basis of the OSPF metric, the 3216 datagram shortest-path trees also keep track of the TTL 3217 values between the root (datagram source) and all 3218 destinations (group members). This enables more 3219 efficient implementation of IP multicast's "expanding 3220 ring search" (see Section 2.3.4). 3222 o In the multicast case, the algorithm is sometimes forced 3223 to use the link state cost for the reverse direction 3224 (i.e, the cost towards, instead of away from, the 3225 source). This is because the costs of OSPF summary-LSAs 3226 and AS-external-LSAs, which sometime form the base of 3227 the multicast datagram shortest-path trees, are 3228 specified in the reverse direction (from the multicast 3229 perspective). 3231 o There are potentially many more datagram shortest-path 3232 trees that need to be calculated (one for each source 3233 net and destination group combination), than the single 3234 unicast SPF tree. This is the main reason that the 3235 datagram shortest-path trees are calculated on demand; 3236 it is hoped that this will spread the cost of the SPF 3237 calculations over time[25]. 3239 12.3. Adding local database entries to the forwarding cache 3241 After the datagram shortest-path trees have been built for each 3242 attached area, the forwarding cache has an upstream node and a 3243 list of downstream interfaces. In order to ensure the delivery 3244 of the multicast datagram to group members on directly attached 3245 networks, the local group database (Section 8.4) must then be 3246 scanned for possible addition to the list of downstream 3247 interfaces. All local group database entries having Group G as 3248 MulticastGroup are examined. Suppose [Group G, Network N] is 3249 one such entry. If Network N is a stub network, then RTX's 3250 Network N interface is added to the list of outgoing interfaces, 3251 with a TTL of 1. (If the Network N interface was already present 3252 in the list of outgoing interfaces, its TTL is simply set to 1). 3254 For example, consider the network configuration shown in Figure 3255 4 when calculating the forwarding cache entry for a datagram 3256 whose source is Network N4 (e.g., from Host H2) and destination 3257 is Group Mb. After calculating the datagram shortest-path tree 3258 for Area 1, Router RT2 would have set it upstream node to 3259 Network N3 and its list of downstream interfaces to NULL. But 3260 then looking at its local group database, it would add its 3261 Network N2 interface with a TTL of 1 to its list of downstream 3262 interfaces. 3264 13. Maintaining the forwarding cache 3266 A MOSPF router may, for resource reasons, limit the size of its 3267 forwarding cache. At any time cache entries can be purged to make 3268 room for newer entries, since the purged entries can always be 3269 rebuilt when necessary. This memo does not specify an algorithm to 3270 select which entries to purge. However, care should be taken to 3271 ensure that any particular entry is not continually rebuilt and then 3272 purged again (i.e., thrashing should be avoided). 3274 The building of the forwarding cache has been previously described 3275 in Section 12. There are events that force one or more forwarding 3276 cache entries to be deleted; these events are described below. Note 3277 that deleted cache entries will be rebuilt on an as-needed basis. 3279 o When the internal topology of the MOSPF system changes, all 3280 forwarding cache entries must be deleted. This is because 3281 internal topology changes may invalidate the previously 3282 calculated datagram shortest-path trees. Since the multicast 3283 routing calculation depends on the result of the unicast routing 3284 calculations, the forwarding cache should be cleared after the 3285 unicast routing table is rebuilt. Internal topology changes are 3286 indicated when both a) a new instance of either a router-LSA or 3287 a network-LSA is received and b) the contents of the new 3288 advertisement (other than the LS age, LS sequence number and LS 3289 checksum fields) are different from the previous instance. This 3290 covers routers and links going up or down, routers that change 3291 from being multicast-incapable to being multicast-capable, etc. 3293 o When a Type 3 summary-LSA (network summary) changes, those 3294 forwarding cache entries specifying datagram sources belonging 3295 to the range of addresses described by the updated summary-LSA 3296 must be deleted. See Sections 12.2.3 and 12.2.5. The change to 3297 the summary-LSA may also modify the cost to one or more AS- 3298 external-LSAs' forwarding addresses (see below). 3300 o Suppose that the content of an AS-external-LSA changes. If the 3301 AS-external-LSA describes an external network N, then all 3302 forwarding cache entries specifying the external source network 3303 N must be deleted. 3305 o When membership in a multicast group changes, all forwarding 3306 cache entries for the particular group must be deleted. Group 3307 membership changes are indicated when either a) the content of a 3308 group-membership-LSA changes or b) an entry in the local group 3309 database (see Section 8.4) changes. 3311 o When the cost to an AS boundary router or to a forwarding 3312 address specified by one or more AS external-LSAs changes, all 3313 forwarding cache entries specifying an external network as 3314 datagram source must be deleted. In this case, potentially all 3315 inter-AS datagram shortest-path trees have been invalidated. The 3316 forwarding cache entries should be deleted after the new best 3317 cost to the AS boundary router/forwarding address has been 3318 calculated. 3320 14. Other additions to the OSPF specification 3322 MOSPF requires some modifications to the base OSPF protocol. All 3323 these modifications are backward-compatible. A router running MOSPF 3324 will still interoperate with an OSPF router when forwarding unicast 3325 traffic. Most of the modifications have been described earlier in 3326 this document. This section collects together those changes which 3327 have yet to be mentioned, organizing them by the affected Section of 3328 [OSPF]. 3330 14.1. The Designated Router 3332 This functionality is described in Section 7.3 of [OSPF]. In 3333 OSPF, a network's Designated Router has two specialized roles. 3334 First, it originates the network's network-LSA. Second, it 3335 controls the flooding on the network, in that all of the routers 3336 on the network synchronize with the Designated Router (and the 3337 Backup Designated Router) only. For these reasons[26], when one 3338 or more of the network's routers are running MOSPF, the 3339 Designated Router should be running MOSPF also. This can be 3340 ensured by assigning all non-multicast routers the Router 3341 Priority of 0. 3343 In MOSPF, the Designated Router also has the additional 3344 responsibility of advertising the network's multicast group 3345 membership in group-membership-LSAs. This is yet another reason 3346 why the Designated Router must be multicast-capable. 3348 14.2. Sending Hello packets 3350 This functionality is described in Section 9.5 of [OSPF]. A 3351 MOSPF router sets the MC-bit in the Options field of its Hello 3352 packets. This indicates that the router is multicast-capable; it 3353 does not necessarily indicate the state of the sending 3354 interface's IPMulticastForwarding parameter (see Section B.2). 3355 Setting the MC-bit in Hellos is done strictly for informational 3356 purposes. Neighbors receiving the router's Hello packets do not 3357 act on the state of the MC-bit. A neighbor's multicast- 3358 capability is learned instead during the Database Exchange 3359 Process (see Section 14.4). 3361 14.3. The Neighbor state machine 3363 This functionality is described in Section 10.3 of [OSPF]. When 3364 a neighbor enters state Exchange, the neighbor Database summary 3365 list is initialized (see the OSPF neighbor FSM entry for State: 3366 ExStart and Event: NegotiationDone). This list describes of the 3367 portion of the router's link state database that needs to be 3368 synchronized with the neighbor. Group-membership-LSAs are 3369 included in the neighbor Database summary list if and only if 3370 the neighbor is multicast-capable. The neighbor's multicast 3371 capability is learned by examining the neighbor's Database 3372 Description packets (see Section 14.4). 3374 14.4. Receiving Database Description packets 3376 This functionality is described in Section 10.6 of [OSPF]. A 3377 neighbor's multicast-capability is learned through received 3378 Database Description packets. When the Database Description 3379 packet is received that transitions the neighbor from ExStart to 3380 Exchange, the state of the MC-bit in the packet's Options field 3381 is examined. The neighbor is multicast-capable if and only if 3382 the MC-bit is set. 3384 The neighbor's multicast capability controls whether group- 3385 membership-LSAs are summarized to the neighbor during the 3386 Database Exchange process (see Section 14.3), and whether 3387 group-membership-LSAs are flooded to the neighbor during the 3388 flooding process (see Section 10.2). 3390 14.5. Sending Database Description packets 3392 This functionality is described in Section 10.8 of [OSPF]. A 3393 MOSPF router sets the MC-bit in the Options field of its 3394 Database Description packets. This indicates to its adjacent 3395 neighbors that the router is multicast-capable; it does not 3396 necessarily indicate the state of the sending interface's 3397 IPMulticastForwarding parameter (see Section B.2). 3399 When a router goes from being multicast-capable to multicast- 3400 incapable, or vice-versa, it must indicate this fact to its 3401 adjacent neighbors by restarting the Database Description 3402 process (i.e., rolling back the state of all adjacent neighbors 3403 to Exstart). 3405 14.6. Originating Router-LSAs 3407 This functionality is described in Section 12.4.1 of [OSPF]. A 3408 MOSPF router sets the MC-bit in the Options field of its 3409 router-LSA. This allows the router to be included in datagram 3410 shortest-path trees (see Step 5a of Section 12.2). 3412 In addition, MOSPF has introduced a new flag in the router-LSA's 3413 rtype field: the W-bit. When the W-bit is set, the router is 3414 included on all datagram shortest-path trees, regardless of 3415 multicast group (see Section 12.2.6). Such a router is called a 3416 wild-card multicast receiver. The router sets the W-bit when it 3417 wishes to receive all multicast datagrams, regardless of 3418 destination. This will sometimes be true of inter-area multicast 3419 forwarders (see Section 3.1), and inter-AS multicast forwarders 3420 (see Section 4). 3422 A router must originate a new instance of its router-LSA 3423 whenever an event occurs that would invalidate the LSA's current 3424 contents. In particular, if the router's multicast capability or 3425 its ability to function as either an inter-area or inter-AS 3426 multicast forwarder changes, its router-LSA must be 3427 reoriginated. 3429 14.7. Originating Network-LSAs 3431 This functionality is described in Section 12.4.2 of [OSPF]. In 3432 OSPF, a transit network's network-LSA is originated by the 3433 network's Designated Router. The Designated Router sets the MC- 3434 bit in the Options field of the network-LSA if and only if both 3435 a) the Designated Router is multicast-capable (i.e., running 3436 MOSPF) and b) the Designated Router's interface's 3437 IPMulticastForwarding parameter has been set to a value other 3438 than disabled (see Section B.2). When the network-LSA has the 3439 MC-bit set, the network can be included in datagram shortest- 3440 path trees (see Section 12.2.6). 3442 It is intended that all routers attached to a common network 3443 agree on the network's IPMulticastForwarding capability. 3445 However, this agreement is not enforced. When there are 3446 disagreements, incorrect routing of multicast datagrams can 3447 result. 3449 14.8. Originating Summary-LSAs 3451 This functionality is described in Section 12.4.3 of [OSPF]. 3452 Inter-area multicast forwarders always set the MC-bit in the 3453 Options field of their summary-link-LSAs, regardless of whether 3454 the path described by the summary-LSA is actually multicast- 3455 capable. Indeed, it is possible that there is no multicast- 3456 capable path to the described destination. All other area border 3457 routers (ones that are not inter-area multicast forwarders) 3458 clear the MC-bit in the Options field of their summary-LSAs. 3460 If its MC-bit is clear, the summary-LSA will not be used when 3461 initializing the candidate list in Sections 12.2.2, 12.2.3 and 3462 12.2.5. 3464 14.9. Originating AS-external-LSAs 3466 This functionality is described in Section 12.4.4 of [OSPF]. 3467 Unlike in summary-LSAs, an inter-AS multicast forwarder should 3468 clear the MC-bit in the Options field of one of its AS- 3469 external-LSAs if it is known that there is no multicast-capable 3470 path from the described destination to the router itself. This 3471 knowledge may possibly be obtained, for example, from an inter- 3472 AS multicast routing algorithm (see Section 4). If the inter-AS 3473 multicast forwarder is unsure of whether a multicast-capable 3474 path exists between the described destination and the router 3475 itself, the MC-bit should be set in the AS-external-LSA. All 3476 other AS boundary routers (ones that are not inter-AS multicast 3477 forwarders) clear the MC-bit in the Options field of their AS- 3478 external-LSAs. 3480 If its MC-bit is clear, the AS-external-LSA will not be used 3481 when initializing the candidate list in Section 12.2.4. 3483 When multicast connectivity to an external destination exists, 3484 but no unicast connectivity, an AS-external-LSA can be 3485 originated having its MC-bit set and specifying a cost of 3486 LSInfinity. Such an AS-external-LSA will still be used by the 3487 multicast routing calculation (see Section 12.2.4). As a result, 3488 when a MOSPF router wishes to stop advertising an AS external 3489 destination, it must use the premature aging procedure specified 3490 in Section 14.1 of [OSPF], rather than simply setting the AS- 3491 external-LSA's cost to LSInfinity. 3493 14.10. Next step in the flooding procedure 3495 This functionality is described in Section 13.3 of [OSPF]. 3496 Group-membership-LSAs are specific to a OSPF single area, and 3497 are flooded to multicast-capable routers only. When flooding a 3498 group-membership-LSA, Section 13.3 of the OSPF specification is 3499 modified as follows: 1) The list of interfaces examined during 3500 flooding (called the eligible interfaces in Section 13.3 of 3501 [OSPF]) is the set of all interfaces attaching to Area A (the 3502 area that the group-membership-LSA is received from), just as 3503 for router-LSAs, network-LSAs and summary-LSAs. 2) When 3504 examining each interface, a group-membership-LSA is added to a 3505 neighbor's link state retransmission list if and only if both a) 3506 Step 1d of [OSPF]'s Section 13.3 is reached for the neighbor and 3507 b) the neighbor is multicast-capable. The neighbor's multicast 3508 capability is discovered during the Database Exchange process 3509 (see Section 14.4). 3511 Note that, since on broadcast networks Link State Update packets 3512 are sent initially as multicasts, non-multicast routers may 3513 receive group-membership-LSAs. However, non-multicast routers 3514 will simply drop the group-membership-LSAs, for reasons of 3515 unrecognized LS type (see Step 2 of [OSPF]'s Section 13). Link 3516 State acknowledgments for group-membership-LSAs are not expected 3517 from non-multicast routers, and group-membership-LSAs will never 3518 be retransmitted to non-multicast routers, since the LSAs are 3519 not added to these routers' link state retransmission lists (see 3520 above paragraph). 3522 For more information on flooding group-membership-LSAs, see 3523 Section 10.2. 3525 14.11. Virtual links 3527 This functionality is described in Section 15 of [OSPF]. When a 3528 MOSPF router (i.e., multicast-capable router) is both an area 3529 border router and an endpoint of a virtual link whose other 3530 endpoint is also multicast capable, the router must then also be 3531 an inter-area multicast forwarder. This is necessary to ensure 3532 that multicast datagrams will flow through the virtual link's 3533 transit area, from one endpoint to the other. When the 3534 backbone's datagram shortest-path tree is constructed in Section 3535 12.1, it is assumed that virtual links are capable of forwarding 3536 multicast datagrams whenever both endpoints are multicast- 3537 capable. 3539 15. References 3541 [RFC 1584] Moy, J., "Multicast Extensions to OSPF", RFC 1584, 3542 Proteon, Inc., March 1994. 3544 [Bharath-Kumar] Bharath-Kumar, K. and J. Jaffe, "Routing to Multiple 3545 Destinations in Computer Networks", IEEE 3546 Transactions on Communications, COM-31[3], March 3547 1983. 3549 [Deering] Deering, S., "Multicast Routing in Internetworks and 3550 Extended LANs", SIGCOMM Summer 1988 Proceedings, 3551 August 1988. 3553 [Deering2] Deering, S., "Multicast Routing in a Datagram 3554 Internetwork", Stanford Technical Report, STAN-CS- 3555 92-1415, Department of Computer Science, Stanford 3556 University, December 1991. 3558 [OSPF] Moy, J., "OSPF Version 2", STD 54, RFC 2328, Ascend 3559 Communications, Inc., April 1998. 3561 [RFC 1075] Waitzman, D., Partridge, C., and S. Deering, 3562 "Distance Vector Multicast Routing Protocol", RFC 3563 1075, BBN STC, Stanford University, November 1988. 3565 [RFC 1112] Deering, S., "Host Extensions for IP Multicasting", 3566 STD 5, RFC 1112, Stanford University, May 1988. 3568 [RFC 1209] Piscitello, D., and J. Lawrence, "Transmission of IP 3569 Datagrams over the SMDS Service", RFC 1209, Bell 3570 Communications Research, March 1991. 3572 [RFC 1700] Reynolds, J. and J. Postel, "Assigned Numbers", STD 3573 2, RFC 1700, USC/Information Sciences Institute, 3574 October 1994. 3576 [RFC 1390] Katz, D., "Transmission of IP and ARP over FDDI 3577 Networks", STD 36, RFC 1390, cisco Systems, Inc., 3578 January 1993. 3580 [IGMPv2] Fenner, W., "Internet Group Mamnegement Protocol, 3581 Version 2", RFC 2236, Xerox PARC, November 1997. 3583 [NSSA] Coltun, R. and V. Fuller, "The OSPF NSSA Option", 3584 RFC 1587, RainbowBridge Communications, Stanford 3585 University, March 1994. 3587 [EXATTR] Ferguson, D., "The OSPF External Attributes LSA", 3588 work in progress. 3590 [DEMAND] Moy, J., "Extending OSPF to Support Demand 3591 Circuits", RFC 1793, Cascade, April 1995. 3593 Footnotes 3595 [1]We also assume in this section that the pictured multi-access 3596 networks provide data-link multicast/broadcast services. 3598 [2]Note that if N3 were a non-broadcast network, Router RT3 would 3599 send separate copies of the datagram to routers RT1 and RT2. Since 3600 the IGMP protocol is not defined on non-broadcast networks, there 3601 could in this case be no Group B member attached to Network N3. 3602 However the multicast datagram would still be delivered to the Group 3603 B members attached to networks N1 and N2. 3605 [3]One might imagine building all possible datagram shortest-path 3606 trees up front. However, this might be expensive, both in router CPU 3607 time and in router memory. It is hoped that building the datagram 3608 shortest-path trees on demand and caching the results will ease 3609 demands on router resources by spreading out the calculations over a 3610 longer period of time. 3612 [4]It is possible that, due to the existence of alternate paths, 3613 several different shortest-path trees are available. MOSPF depends 3614 on all routers constructing the exact same shortest path tree. For 3615 that reason, tie-breaking schemes have been implemented during tree 3616 construction to ensure that identical trees result. See Section 12 3617 for more details. 3619 [5]Note that the expanding ring search yields the nearest server in 3620 terms of hop count, but not necessarily in terms of the OSPF metric. 3622 [6]This means that in MOSPF, just as in OSPF, the only kind of link 3623 state advertisement that can be flooded between areas is the AS- 3624 external-LSA. 3626 [7]A router indicates that it is a wild-card multicast receiver by 3627 setting the appropriate flag in its router-LSA. See Section 14.6 for 3628 details. 3630 [8]This is not quite true. As we shall see, any inter-AS multicast 3631 forwarders belonging to the backbone are designated as wild-card 3632 multicast receivers. See Section 4. 3634 [9]It is possible that through the operation of an inter-AS 3635 multicast routing protocol, Router RT7 knows that it does not have 3636 multicast connectivity to Network N15 (even though it has unicast 3637 connectivity). In this case, RT7 would not advertise the external 3638 link to N15 as being multicast capable. 3640 [10]Synchronization of the IPMulticastForwarding interface parameter 3641 is not enforced by the MOSPF protocol, since it is not included in 3642 the contents of a MOSPF router's Hello packets. 3644 [11]For this reason when a transit network has both MOSPF routers 3645 and non-multicast OSPF routers attached, care should be taken to 3646 ensure that a MOSPF router is elected Designated Router. This can be 3647 accomplished through proper setting of the routers' configured 3648 Router Priority. 3650 [12]Note that just because these advertisements exist in the link 3651 state database, it does not mean that the Group G members are 3652 reachable. Reachability does not enter into the building of the 3653 transit vertex list, in order to simplify the calculation. This is a 3654 trade-off. As a result, some multicast datagrams may be forwarded 3655 further than necessary, when the described Group G members actually 3656 are unreachable. 3658 [13]Since the Designated Router controls flooding on the network, 3659 this is another reason to ensure that a MOSPF router is elected as 3660 Designated Router. 3662 [14]In other words, group-membership-LSAs will never be 3663 retransmitted to non-multicast routers. 3665 [15]This last step will not be necessary if the configuration 3666 guidelines presented in Section 6.5 are followed. 3668 [16]It is assumed that a MOSPF router that wants to stop advertising 3669 a route to an external destination will use the premature aging 3670 procedure specified in Section 14.1 of [OSPF], rather than setting 3671 the AS-external-LSA's cost to LSInfinity. 3673 [17]This preference ordering is used in Step 5c of Section 12.2. 3675 [18]No attempt is made to match the links' two halves. See Step 5d. 3677 [19]However, a summary-LSA is eligible for matching even if the MC- 3678 bit in its Options field is clear. 3680 [20]Costs may have both a Type 2 and a Type 1 component; the Type 2 3681 component is always most significant. 3683 [21]This case mirrors the SourceIntraArea candidate list 3684 initialization in Section 12.2.1. 3686 [22]This case mirrors the SourceInterArea1 candidate list 3687 initialization in Section 12.2.2. 3689 [23]This case mirrors the SourceInterArea2 candidate list 3690 initialization in Section 12.2.3. 3692 [24]Note that selecting the upstream node in this manner enforces 3693 the inter-area routing architecture outlined in Section 3.1. Namely, 3694 the multicast datagram is forwarded from the source area, over the 3695 backbone and then into the non-backbone areas. This is similar to 3696 the "hub and spoke" architecture for unicast forwarding described in 3697 Section 3.2 of [OSPF]. 3699 [25]Indeed, there will also be those cases where the router, not 3700 being on a particular datagram shortest-path tree, will never have 3701 to calculate the particular tree, since the router will not receive 3702 the datagram in the first place. 3704 [26]Group-membership-LSAs are not processed by non-multicast routers 3705 (see Section 10.2). Also, if the Designated Router was not running 3706 the multicast extensions, multicast datagrams would not be forwarded 3707 over the network because its network-LSA would have its MC-bit clear 3708 (see Step 5a in Section 12.2). 3710 A. Data Formats 3712 This section documents the format of MOSPF protocol packets and link 3713 state advertisements (LSAs). All changes and additions made to the 3714 OSPF Version 2 data formats have been made in a backward-compatible 3715 manner. In other words, multicast routers running MOSPF can 3716 interoperate with (non-multicast) OSPF Version 2 routers when 3717 forwarding regular (unicast) IP data traffic. 3719 The MOSPF packet formats are the same as for OSPF Version 2 3720 (described in Appendix A of [OSPF]). One additional option has been 3721 added to the Options field that appears in OSPF Hello packets, 3722 Database Description packets and all link state advertisements. This 3723 new option indicates a router's/network's multicast capability, and 3724 is documented in Section A.1. The presence of this new option is 3725 ignored by all non-multicast routers. 3727 To support MOSPF, one of OSPF's link state advertisements has been 3728 modified, and a new link state advertisement has been added. The 3729 format of the router-LSA has been modified (see Section A.2) to 3730 include a new flag indicating whether the router is a wild-card 3731 multicast receiver. A new link state advertisement, called the 3732 group-membership-LSA, has been added to pinpoint multicast group 3733 members in the link state database. This new advertisement is 3734 neither flooded nor processed by non-multicast routers. The group- 3735 membership-LSA is documented in Section A.3. 3737 A.1 The Options field 3739 The OSPF Options field is present in OSPF Hello packets, Database 3740 Description packets and all LSAs. The Options field enables OSPF 3741 routers to support (or not support) optional capabilities, and to 3742 communicate their capability level to other OSPF routers. Through 3743 this mechanism routers of differing capabilities can be mixed within 3744 an OSPF routing domain. 3746 When used in Hello packets, the Options field allows a router to 3747 reject a neighbor because of a capability mismatch. Alternatively, 3748 when capabilities are exchanged in Database Description packets a 3749 router can choose not to forward certain LSAs to a neighbor because 3750 of its reduced functionality. Lastly, listing capabilities in LSAs 3751 allows routers to forward traffic around reduced functionality 3752 routers, by excluding them from parts of the routing table 3753 calculation. 3755 Five bits of the OSPF Options field have been assigned, although 3756 only one (the MC-bit) is described completely by this memo. Each bit 3757 is described briefly below. Routers should reset (i.e. clear) 3758 unrecognized bits in the Options field when sending Hello packets or 3759 Database Description packets and when originating LSAs. Conversely, 3760 routers encountering unrecognized Option bits in received Hello 3761 Packets, Database Description packets or LSAs should ignore the 3762 capability and process the packet/LSA normally. 3764 +------------------------------------+ 3765 | * | * | DC | EA | N/P | MC | E | * | 3766 +------------------------------------+ 3768 The Options field 3770 E-bit 3771 This bit describes the way AS-external-LSAs are flooded, as 3772 described in [OSPF]. 3774 MC-bit 3775 This bit describes the multicast capability of the various 3776 pieces of the OSPF routing domain. When calculating the path of 3777 multicast datagrams, only those link state advertisements having 3778 their MC-bit set are used. In addition, a router uses the MC-bit 3779 in its Database Description packets to tell adjacent neighbors 3780 whether the router will participate in the flooding of the new 3781 group-membership-LSAs. 3783 N/P-bit 3784 This bit describes the handling of Type-7 LSAs, as specified in 3785 [NSSA]. 3787 EA-bit 3788 This bit describes the router's willingness to receive and 3789 forward External-Attributes-LSAs, as specified in [EXATTR]. 3791 DC-bit 3792 This bit describes the router's handling of demand circuits, as 3793 specified in [DEMAND]. 3795 A.2 Router-LSA 3797 An OSPF router originates a router-LSA into each of its attached 3798 areas. The router-LSA describes the state and cost of the router's 3799 interfaces to the area. The contents of the router-LSA are described 3800 in detail in Section A.4.2 of [OSPF]. There are flags in the 3801 router-LSA that indicate whether the router is either a) an area 3802 border router or b) an AS boundary router or c) the endpoint of a 3803 virtual link. One more flag has been added to the router-LSA for 3804 MOSPF; it is called bit W below. This flag indicates whether the 3805 router wishes to receive all multicast datagrams regardless of 3806 destination (i.e., is a wild-card multicast receiver). 3808 0 1 2 3 3809 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 3810 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3811 | LS age | Options | 1 | 3812 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3813 | Link State ID | 3814 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3815 | Advertising Router | 3816 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3817 | LS sequence number | 3818 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3819 | LS checksum | length | 3820 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3821 | rtype | 0 | # links | 3822 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + 3823 | Link ID | P 3824 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ E 3825 | Link Data | R 3826 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3827 | Type | # TOS | TOS 0 metric | # 3828 + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ L 3829 # | TOS | 0 | metric | I 3830 T +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ N 3831 O | ... | K 3832 S +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ S 3833 | | TOS | 0 | metric | | 3834 + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + 3835 | ... | 3837 The router LSA 3838 +---+---+---+---+---+---+---+---+ 3839 | * | * | * | * | W | V | E | B | 3840 +---+---+---+---+---+---+---+-+-+ 3842 The rtype field 3844 The following defines the flags found in the rtype field. Each flag 3845 classifies the router by function: 3847 o bit B. When set, the router is an area border router (B is for 3848 border). These routers forward unicast data traffic between OSPF 3849 areas. 3851 o bit E. When set, the router is an AS boundary router (E is for 3852 external). These routers forward unicast data traffic between 3853 Autonomous Systems. 3855 o bit V. When set, the router is an endpoint of an active virtual 3856 link (V is for virtual) which uses the described area as its 3857 Transit area. 3859 o bit W. When set, the router is a wild-card multicast receiver. 3860 These routers receive all multicast datagrams, regardless of 3861 destination. Inter-area multicast forwarders and inter-AS 3862 multicast forwarders are sometimes wild-card multicast receivers 3863 (see Sections 3 and 4). 3865 A.3 Group-membership-LSA 3867 Group-membership-LSAs are the Type 6 link state advertisements. 3868 Group-membership-LSAs are specific to a particular OSPF area. They 3869 are never flooded beyond their area of origination. A router's 3870 group-membership-LSA for Area A indicates its directly attached 3871 networks which belong to Area A and contain members of a particular 3872 multicast group. A router originates a group-membership-LSA for 3873 multicast group D when the following conditions are met for at least 3874 one directly attached network: 1) the router has been elected 3875 Designated Router for the network and 2) at least one host on the 3876 network has joined Group D via the IGMP protocol. 3878 A router may also originate a group-membership-LSA for Group D if 3879 the router itself has internal applications belonging to Group D. In 3880 addition, area border routers originate group-membership-LSAs into 3881 the backbone area when there are group members in the router's 3882 attached non-backbone areas. See Section 10 for more information 3883 concerning the origination of group-membership-LSAs. 3885 0 1 2 3 3886 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 3887 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3888 | LS age | Options | 6 | 3889 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3890 | Link State ID = Destination Group | 3891 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3892 | Advertising Router | 3893 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3894 | LS sequence number | 3895 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3896 | LS checksum | length | 3897 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3898 | Vertex type | 3899 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3900 | Vertex ID | 3901 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3902 | ... | 3904 The group-membership-LSA 3906 The group-membership-LSA consists of the standard 20-byte link state 3907 header (see Section A.4.1 of [OSPF]) followed by a list of transit 3908 vertices to label with the multicast destination. The 3909 advertisement's Link State ID is set to the destination multicast 3910 group address. There is no metric associated with the advertisement. 3911 Each transit vertex is specified by its Vertex type and Vertex ID 3912 (see Section 12.1 for an explanation of this terminology): 3914 o Vertex type. Set equal to 1 for a router, and 2 for a transit 3915 network. Note that the only router that may be included in the 3916 list is the Advertising Router itself. 3918 o Vertex ID. For router vertices, this field indicates the 3919 router's OSPF Router ID. For transit network vertices, this 3920 field indicates the IP address of the network's Designated 3921 Router. Note that the link state advertisement associated with 3922 the transit vertex is the LSA whose LS type = Vertex type, Link 3923 State ID = Vertex ID and Advertising Router = the group- 3924 membership-LSA's Advertising Router. 3926 B. Configurable Constants 3928 This section documents the configurable parameters used by OSPF's 3929 multicast routing extensions. These parameters are in addition to 3930 the configurable constants used by the base OSPF protocol 3931 (documented in Appendix C of [OSPF]). An implementation of MOSPF 3932 must provide the ability to set these parameters, either through 3933 network management or some other means. 3935 B.1 Global parameters 3937 The following parameters apply to the router as a whole. 3939 o Multicast capability. An indication of whether the router is 3940 running MOSPF. If the router is running MOSPF, it will 3941 perform the algorithms as set forth in this specification. 3942 Otherwise, the router is still able to run the basic OSPF 3943 algorithm (as set forth in [OSPF]), and will be able to 3944 interoperate with multicast capable routers (see Section 3945 6.1) when forwarding regular (unicast) IP data traffic. 3947 o Inter-area multicast forwarder. This parameter indicates 3948 whether the router will forward multicast datagrams between 3949 OSPF areas. Such a router summarizes group membership 3950 information to the backbone, and acts as a wild-card 3951 multicast receiver in all its attached non-backbone areas 3952 (see Section 3.1). Not all multicast-capable area border 3953 routers need be configured as inter-area multicast 3954 forwarders. However, whenever both ends of a virtual link 3955 are multicast-capable, they must both be configured as 3956 inter-area multicast forwarders (see Section 14.11). By 3957 default, all multicast-capable area border routers are 3958 configured as inter-area multicast forwarders. 3960 o Inter-AS multicast forwarder. This parameter indicates 3961 whether the router forwards multicast datagrams between 3962 Autonomous Systems. Such a router acts as a wild-card 3963 multicast receiver in all attached areas (see Section 4). It 3964 is also assumed that an inter-AS multicast forwarder runs 3965 some kind of inter-AS multicast routing algorithm. 3967 B.2 Router interface parameters 3969 The following parameter can be configured separately for each of 3970 the router's OSPF interfaces. 3972 o IPMulticastForwarding. This configurable parameter indicates 3973 whether IP multicasts should be forwarded over the attached 3974 network, and if so, how the forwarding should be done. The 3975 parameter can assume one of three possible values: disabled, 3976 data-link multicast and data-link unicast. When set to 3977 disabled, IP multicast datagrams will not be forwarded out 3978 the interface. When set to data-link multicast, IP multicast 3979 datagrams will be forwarded as data-link multicasts. When 3980 set to data-link unicast, IP multicast datagrams will be 3981 forwarded as data-link unicasts. The default value for this 3982 parameter is data-link multicast. The other two settings are 3983 for use in the special circumstances described in Sections 3984 6.2 and 6.3. When set to disabled or to data-link unicast, 3985 IGMP group membership is not advertised for the attached 3986 network. 3988 The IPMulticastForwarding parameter is really a description 3989 of the attached network. As such, it should be configured 3990 identically on all routers attached to a common network; 3991 otherwise incorrect routing of multicast datagrams may 3992 result. 3994 C. Sample datagram shortest-path trees 3996 In MOSPF, all routers must calculate exactly the same datagram 3997 shortest-path trees. In order to ensure this in internetworks having 3998 redundant links, a number of tie-breakers were defined in the MOSPF 3999 routing table calculation (see Steps 4 and 5c of Section 12.2, and 4000 Sections 12.2.4 and 12.2.7). This section illustrates the use of 4001 these tie-breakers on a sample topology. 4003 Three different examples are given. All examples use the same 4004 physical topology and the same set of OSPF interface costs (see the 4005 left side of Figure 14). The source of the datagram is always Host 4006 H1 on the network at the top of the figure (192.9.1.0), and the 4007 destination group members are the two hosts labelled with Group Ma 4008 at the bottom of the figure. The first case shows an example of 4009 intra-area multicast, while the remaining two cases show the 4010 influence of OSPF areas on the path of a multicast datagram. 4012 C.1 An intra-area tree 4014 The datagram shortest-path tree resulting from the intra-area case 4015 is shown on the right of Figure 14. The root of the tree is the 4016 source network (192.9.1.0), and the leaves are the two routers (RT4 4017 and RT3) directly attached to the stub networks containing Group Ma 4018 members. 4020 There are equal-cost paths available to both group members. For the 4021 group member on the left, the path could go either through network 4022 10.1.0.0 or through network 10.2.0.0. By the tie-breaking rules, the 4023 path through 10.2.0.0 is chosen since it has the larger IP network 4024 number (see Step 5c of Section 12.2). 4026 For the group member on the right, the path could go either over 4027 Network 10.2.0.0 or over the serial line connecting routers RT2 and 4028 RT3. The path over Network 10.2.0.0 is chosen after executing two 4029 tie-breaking rules. First, Network 10.2.0.0 is placed on the 4030 shortest-path tree before Router RT3 since networks are always 4031 chosen over routers (see Step 4 of Section 12.2). Then, given a 4033 +--+ 4034 |H1| 4035 +--+ 4036 Net 192.9.1.0 | 4037 +------------------+ 4038 | | 4039 +----------+ |1 |1 4040 | Network | 8+---+ +---+ o 192.9.1.0 4041 | 10.1.0.0 |------|RT1| |RT2| | 4042 +----------+ +---+ +---+ 0| 4043 | |8 8| | 4044 8| +----------+ |8 o RT1 4045 +---+10 | Network | 10+---+ | 4046 |RT4|-------| 10.2.0.0 |----|RT3| 8| 4047 +---+ +----------+ +---+ | 4048 |3 |3 o 10.2.0.0 4049 | | / \ 4050 +---------+ +-------+ 0/ \0 4051 | | / \ 4052 +--+ +--+ o o 4053 |Ma| |Ma| RT4 RT3 4054 +--+ +--+ 4056 Figure 14: An intra-area tree 4057 choice of either Network 10.2.0.0 or Router RT2 for RT3's parent on 4058 the tree, Net 10.2.0.0 is again preferred since it is a network (see 4059 Step 5c of Section 12.2) 4061 C.2 The effect of areas 4063 In Figure 15 below, the previous diagram has been modified by the 4064 inclusion of OSPF areas. The datagram source is now part of the OSPF 4065 backbone (Area 0), while the rest of the topology is in Area 1. In 4066 this case, since the datagram source and the group members belong to 4067 different areas, reverse costs are used when building the tree (see 4068 Step 5b of Section 12.2). This actually eliminates the equal cost 4069 paths from the diagram, and leads to the Area 1 datagram shortest- 4070 path tree on the right of Figure 15. 4072 +--+ 4073 |H1| 4074 +--+ 4075 Net 192.9.1.0 | 4076 +------------------+ 4077 ..................... | | 4078 . +----------+ . |1 |1 192.9.1.0 4079 . | Network | 8+---+ +---+ o 4080 . | 10.1.0.0 |------|RT1|........|RT2|... / \ 4081 . +----------+ +---+ +---+ . 1/ \1 4082 . | |8 8| . / \ 4083 . 8| +----------+ |8 . o RT1 o RT2 4084 . +---+10 | Network | 10+---+ . | \ 4085 . |RT4|-------| 10.2.0.0 |----|RT3| . 0| \8 4086 . +---+ +----------+ +---+ . | \ 4087 . |3 |3 . o 10.1.0.0 o 4088 . | | . | RT3 4089 . +---------+ +-------+. 8| 4090 . | | . | 4091 . +--+ +--+ . o 4092 . |Ma| |Ma| . RT4 4093 . +--+ Area 1 +--+ . 4094 ......................................... 4096 Figure 15: The effect of areas 4097 C.3 The effect of virtual links 4099 In Figure 16 below, Network 10.1.0.0 has been configured as a 4100 separate area (Area 1), while everything else belongs to the OSPF 4101 backbone (Area 0). In addition, a virtual link has been configured 4102 through Area 1, enhancing the backbone connectivity. In this case, 4103 both the source and the group members belong to the same area, so 4104 forward costs are used. However, since virtual links are preferred 4105 over regular links (see Step 5c of Section 12.2), the backbone 4106 datagram shortest-path tree uses Network 10.1.0.0 instead of 4107 10.2.0.0 on the path to the left group member. This leads to the 4108 tree on the right of Figure 16. 4110 +--+ 4111 |H1| 4112 +--+ 4113 Net 192.9.1.0 | 4114 ................ +------------------+ 4115 . +----------+ . /1 | 4116 . | Network |8. / |1 4117 . | 10.1.0.0 |-+---+ +---+ o 192.9.1.0 4118 . +----------+*|RT1| |RT2| | 4119 . 8|*******+---+ +---+ 0| 4120 .Area1 |*VL . \8 8| | 4121 .....+---+...... +----------+ |8 o RT1 4122 |RT4|10 | Network | 10+---+ / \ 4123 +---+-------| 10.2.0.0 |----|RT3| /8 \8 4124 | +----------+ +---+ / \ 4125 |3 |3 o 10.1 o 10.2.0.0 4126 | | | | 4127 +---------+ +-------+ |0 |0 4128 | | | | 4129 +--+ +--+ o o 4130 |Ma| |Ma| RT4 RT3 4131 +--+ +--+ 4133 Figure 16: The effect of virtual links 4134 D. Differences from RFC 1584 4136 This section briefly describes the differences between this document 4137 and the MOSPF specification previously published in RFC 1584. The 4138 differences can be divided into three categories: a) bug fixes, b) 4139 changes necessary to keep in step with the latest base OSPF 4140 specification [OSPF], and c) changes required for interoperation 4141 with the new version of IGMP, IGMPv2 [IGMPv2]. 4143 D.1 Bug Fixes 4145 The following problems in RFC 1584 have been corrected. 4147 D.1.1 Merging datagram shortest-path trees 4149 In order to calculate multicast paths through areas with 4150 configured virtual links, those areas whose candidate list 4151 initialization falls into case SourceInterArea2 are now 4152 eligible for consideration as RootArea. This change affects 4153 Section 12.2.7. 4155 This change also enables the correct operation of the 4156 example in Section C.3. Router RT4 will now be able to 4157 correctly calculate the upstream node for the datagram with 4158 source H1 and multicast destination group Ma. 4160 D.1.2 Candidate list initialization for stub areas 4162 When Area A is a stub area and SourceNet is outside of Area 4163 A (either in another OSPF area or external to the OSPF 4164 routing domain), the candidate list initialization for Area 4165 A (case SourceStubExternal) has been changed. The processing 4166 in this case is now identical to the case SourceInterArea2. 4167 See Sections 12.2 and 12.2.3 for details. 4169 D.1.3 Sources on multiply addressed segments 4171 Multicast sources on multiply-addressed segments should be 4172 allowed to send multicast datagrams, and have them forwarded 4173 by MOSPF routers, regardless of which subnet on the 4174 multiply-addressed segment the source host belongs to. This 4175 change affects the association of an interface with an 4176 incoming datagram (Section 11.1), candidate list 4177 initialization in the SourceIntraArea case (Section 12.2.1), 4178 interaction with IGMP (Section 9), and the forwarding of 4179 locally-originated multicasts (Section 11.3). 4181 D.1.4 Local group database modifications 4183 There are two changes to the local group database 4184 processing. First, all MOSPF routers (and not just the 4185 Designated Router and Backup Designated Router) maintain 4186 local group database entries for their attached segments by 4187 listening to IGMP membership Reports. Second, only those 4188 local group database entries associated with stub networks 4189 cause outgoing interfaces to be added to multicast 4190 forwarding cache entries. 4192 See Sections 2.3.1, 2.3.4, 9, 9.1, and 12.3 for details. 4194 D.2 Changes required by RFC 2328 4196 The following changes were made to stay in step with the latest 4197 OSPFv2 base specification [OSPF]. 4199 D.2.1 Deleting the TOS routing option 4201 As was done for the base OSPFv2 specification, TOS routing 4202 has now been removed from the MOSPF specification, due to 4203 lack of deployment experience. 4205 D.2.2 Giving more-specific sources precedence 4207 RFC 2328 now gives precedence to longest-matching prefixes, 4208 over path type (intra-area, inter-area, external type-1 and 4209 external type-2). The MOSPF specification has been changed 4210 accordingly. See Sections 11.2 and 13 for details. 4212 D.3 Changes required by IGMPv2 4214 The MOSPF specification now assumes that local group membership 4215 is monitored through IGMPv2, instead of the original IGMPv1 4216 assumption made by RFC 1584. In particular, IGMPv2 is assumed to 4217 elect the IGMP querier, instead of having the OSPF Designated 4218 Router serve that function. Detailed discussion of IGMP 4219 functions such as the sending of IGMP Membership Queries and the 4220 reception of IGMP Membership Reports has been removed from the 4221 MOSPF specification in deference to the IGMPv2 specification 4222 [IGMPv2]. 4224 IGMP polling parameters have been removed from the MOSPF 4225 specification. These parameters were listed in RFC 1584 as 4226 IGMPPollingInterval and IGMPTimeout. Mention of the interface's 4227 IGMP polling timer has also been removed. 4229 All MOSPF routers now listen to IGMP Membership Reports, instead 4230 of just the Designated Routers and Backup Designated Routers as 4231 specified by RFC 1584. 4233 See Sections 2.3.1, 9, and 9.1 for details. 4235 D.4 Clarifications 4237 The following are clarifications based on questions received on 4238 the previous MOSPF specification, RFC 1584: 4240 o If using an AS-external-LSA to indicate multicast-only 4241 connectivity, you can use either type-1 or type-2 external 4242 metrics, setting the cost to LSInfinity. A type-1 external 4243 metric of LSInfinity is considered to be the same cost as a 4244 type-2 external metric of LSInfinity. 4246 o A MOSPF router floods group-membership-LSAs out an interface 4247 regardless of the interface's IPMulticastForwarding 4248 parameter setting. MOSPF routers always set the MC-bit in 4249 their Database Description packets, again regardless of the 4250 attached interface's IPMulticastForwarding parameter 4251 setting. 4253 o A MOSPF router which is an inter-AS multicast forwarder, but 4254 not an inter-area multicast forwarder, would set the W-bit 4255 (wild-card) in all of its router-LSAs (one per attached OSPF 4256 area), but would clear the MC-bit in every summary-LSA that 4257 the router originates. 4259 o If MOSPF is run on some, but not all, of an OSPF routing 4260 domain's segments, then incomplete multicast connectivity 4261 will result, even if another routing protocol (such as 4262 DVMRP) is run on the remaining segments. This is because 4263 AS-external-LSAs, which are used to import multicast sources 4264 from other multicast routing protocols, are ignored for 4265 intra-domain sources. 4267 Security Considerations 4269 MOSPF uses the authentication mechanisms supplied by the base OSPF 4270 protocol. All OSPF protocol exchanges are authenticated. OSPF 4271 supports multiple types of authentication; the type of 4272 authentication in use can be configured on a per network segment 4273 basis. One of OSPF's authentication types, namely the Cryptographic 4274 authentication option, is believed to be secure against passive 4275 attacks and provide significant protection against active attacks. 4276 For more information, see [OSPF]. 4278 Author's Address 4280 John Moy 4281 Ascend Communications, Inc. 4282 1 Robbins Road 4283 Westford, MA 01886 4284 Phone: 978-952-1367 4285 Fax: 978-392-2075 4286 Email: jmoy@casc.com 4288 This document expires in February 1999.