File: rfc1584.txt

package info (click to toggle)
doc-rfc 20181229-2
  • links: PTS, VCS
  • area: non-free
  • in suites: buster
  • size: 570,944 kB
  • sloc: xml: 285,646; sh: 107; python: 90; perl: 42; makefile: 14
file content (5713 lines) | stat: -rw-r--r-- 262,463 bytes parent folder | download | duplicates (8)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706
1707
1708
1709
1710
1711
1712
1713
1714
1715
1716
1717
1718
1719
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
1737
1738
1739
1740
1741
1742
1743
1744
1745
1746
1747
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
1761
1762
1763
1764
1765
1766
1767
1768
1769
1770
1771
1772
1773
1774
1775
1776
1777
1778
1779
1780
1781
1782
1783
1784
1785
1786
1787
1788
1789
1790
1791
1792
1793
1794
1795
1796
1797
1798
1799
1800
1801
1802
1803
1804
1805
1806
1807
1808
1809
1810
1811
1812
1813
1814
1815
1816
1817
1818
1819
1820
1821
1822
1823
1824
1825
1826
1827
1828
1829
1830
1831
1832
1833
1834
1835
1836
1837
1838
1839
1840
1841
1842
1843
1844
1845
1846
1847
1848
1849
1850
1851
1852
1853
1854
1855
1856
1857
1858
1859
1860
1861
1862
1863
1864
1865
1866
1867
1868
1869
1870
1871
1872
1873
1874
1875
1876
1877
1878
1879
1880
1881
1882
1883
1884
1885
1886
1887
1888
1889
1890
1891
1892
1893
1894
1895
1896
1897
1898
1899
1900
1901
1902
1903
1904
1905
1906
1907
1908
1909
1910
1911
1912
1913
1914
1915
1916
1917
1918
1919
1920
1921
1922
1923
1924
1925
1926
1927
1928
1929
1930
1931
1932
1933
1934
1935
1936
1937
1938
1939
1940
1941
1942
1943
1944
1945
1946
1947
1948
1949
1950
1951
1952
1953
1954
1955
1956
1957
1958
1959
1960
1961
1962
1963
1964
1965
1966
1967
1968
1969
1970
1971
1972
1973
1974
1975
1976
1977
1978
1979
1980
1981
1982
1983
1984
1985
1986
1987
1988
1989
1990
1991
1992
1993
1994
1995
1996
1997
1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
2010
2011
2012
2013
2014
2015
2016
2017
2018
2019
2020
2021
2022
2023
2024
2025
2026
2027
2028
2029
2030
2031
2032
2033
2034
2035
2036
2037
2038
2039
2040
2041
2042
2043
2044
2045
2046
2047
2048
2049
2050
2051
2052
2053
2054
2055
2056
2057
2058
2059
2060
2061
2062
2063
2064
2065
2066
2067
2068
2069
2070
2071
2072
2073
2074
2075
2076
2077
2078
2079
2080
2081
2082
2083
2084
2085
2086
2087
2088
2089
2090
2091
2092
2093
2094
2095
2096
2097
2098
2099
2100
2101
2102
2103
2104
2105
2106
2107
2108
2109
2110
2111
2112
2113
2114
2115
2116
2117
2118
2119
2120
2121
2122
2123
2124
2125
2126
2127
2128
2129
2130
2131
2132
2133
2134
2135
2136
2137
2138
2139
2140
2141
2142
2143
2144
2145
2146
2147
2148
2149
2150
2151
2152
2153
2154
2155
2156
2157
2158
2159
2160
2161
2162
2163
2164
2165
2166
2167
2168
2169
2170
2171
2172
2173
2174
2175
2176
2177
2178
2179
2180
2181
2182
2183
2184
2185
2186
2187
2188
2189
2190
2191
2192
2193
2194
2195
2196
2197
2198
2199
2200
2201
2202
2203
2204
2205
2206
2207
2208
2209
2210
2211
2212
2213
2214
2215
2216
2217
2218
2219
2220
2221
2222
2223
2224
2225
2226
2227
2228
2229
2230
2231
2232
2233
2234
2235
2236
2237
2238
2239
2240
2241
2242
2243
2244
2245
2246
2247
2248
2249
2250
2251
2252
2253
2254
2255
2256
2257
2258
2259
2260
2261
2262
2263
2264
2265
2266
2267
2268
2269
2270
2271
2272
2273
2274
2275
2276
2277
2278
2279
2280
2281
2282
2283
2284
2285
2286
2287
2288
2289
2290
2291
2292
2293
2294
2295
2296
2297
2298
2299
2300
2301
2302
2303
2304
2305
2306
2307
2308
2309
2310
2311
2312
2313
2314
2315
2316
2317
2318
2319
2320
2321
2322
2323
2324
2325
2326
2327
2328
2329
2330
2331
2332
2333
2334
2335
2336
2337
2338
2339
2340
2341
2342
2343
2344
2345
2346
2347
2348
2349
2350
2351
2352
2353
2354
2355
2356
2357
2358
2359
2360
2361
2362
2363
2364
2365
2366
2367
2368
2369
2370
2371
2372
2373
2374
2375
2376
2377
2378
2379
2380
2381
2382
2383
2384
2385
2386
2387
2388
2389
2390
2391
2392
2393
2394
2395
2396
2397
2398
2399
2400
2401
2402
2403
2404
2405
2406
2407
2408
2409
2410
2411
2412
2413
2414
2415
2416
2417
2418
2419
2420
2421
2422
2423
2424
2425
2426
2427
2428
2429
2430
2431
2432
2433
2434
2435
2436
2437
2438
2439
2440
2441
2442
2443
2444
2445
2446
2447
2448
2449
2450
2451
2452
2453
2454
2455
2456
2457
2458
2459
2460
2461
2462
2463
2464
2465
2466
2467
2468
2469
2470
2471
2472
2473
2474
2475
2476
2477
2478
2479
2480
2481
2482
2483
2484
2485
2486
2487
2488
2489
2490
2491
2492
2493
2494
2495
2496
2497
2498
2499
2500
2501
2502
2503
2504
2505
2506
2507
2508
2509
2510
2511
2512
2513
2514
2515
2516
2517
2518
2519
2520
2521
2522
2523
2524
2525
2526
2527
2528
2529
2530
2531
2532
2533
2534
2535
2536
2537
2538
2539
2540
2541
2542
2543
2544
2545
2546
2547
2548
2549
2550
2551
2552
2553
2554
2555
2556
2557
2558
2559
2560
2561
2562
2563
2564
2565
2566
2567
2568
2569
2570
2571
2572
2573
2574
2575
2576
2577
2578
2579
2580
2581
2582
2583
2584
2585
2586
2587
2588
2589
2590
2591
2592
2593
2594
2595
2596
2597
2598
2599
2600
2601
2602
2603
2604
2605
2606
2607
2608
2609
2610
2611
2612
2613
2614
2615
2616
2617
2618
2619
2620
2621
2622
2623
2624
2625
2626
2627
2628
2629
2630
2631
2632
2633
2634
2635
2636
2637
2638
2639
2640
2641
2642
2643
2644
2645
2646
2647
2648
2649
2650
2651
2652
2653
2654
2655
2656
2657
2658
2659
2660
2661
2662
2663
2664
2665
2666
2667
2668
2669
2670
2671
2672
2673
2674
2675
2676
2677
2678
2679
2680
2681
2682
2683
2684
2685
2686
2687
2688
2689
2690
2691
2692
2693
2694
2695
2696
2697
2698
2699
2700
2701
2702
2703
2704
2705
2706
2707
2708
2709
2710
2711
2712
2713
2714
2715
2716
2717
2718
2719
2720
2721
2722
2723
2724
2725
2726
2727
2728
2729
2730
2731
2732
2733
2734
2735
2736
2737
2738
2739
2740
2741
2742
2743
2744
2745
2746
2747
2748
2749
2750
2751
2752
2753
2754
2755
2756
2757
2758
2759
2760
2761
2762
2763
2764
2765
2766
2767
2768
2769
2770
2771
2772
2773
2774
2775
2776
2777
2778
2779
2780
2781
2782
2783
2784
2785
2786
2787
2788
2789
2790
2791
2792
2793
2794
2795
2796
2797
2798
2799
2800
2801
2802
2803
2804
2805
2806
2807
2808
2809
2810
2811
2812
2813
2814
2815
2816
2817
2818
2819
2820
2821
2822
2823
2824
2825
2826
2827
2828
2829
2830
2831
2832
2833
2834
2835
2836
2837
2838
2839
2840
2841
2842
2843
2844
2845
2846
2847
2848
2849
2850
2851
2852
2853
2854
2855
2856
2857
2858
2859
2860
2861
2862
2863
2864
2865
2866
2867
2868
2869
2870
2871
2872
2873
2874
2875
2876
2877
2878
2879
2880
2881
2882
2883
2884
2885
2886
2887
2888
2889
2890
2891
2892
2893
2894
2895
2896
2897
2898
2899
2900
2901
2902
2903
2904
2905
2906
2907
2908
2909
2910
2911
2912
2913
2914
2915
2916
2917
2918
2919
2920
2921
2922
2923
2924
2925
2926
2927
2928
2929
2930
2931
2932
2933
2934
2935
2936
2937
2938
2939
2940
2941
2942
2943
2944
2945
2946
2947
2948
2949
2950
2951
2952
2953
2954
2955
2956
2957
2958
2959
2960
2961
2962
2963
2964
2965
2966
2967
2968
2969
2970
2971
2972
2973
2974
2975
2976
2977
2978
2979
2980
2981
2982
2983
2984
2985
2986
2987
2988
2989
2990
2991
2992
2993
2994
2995
2996
2997
2998
2999
3000
3001
3002
3003
3004
3005
3006
3007
3008
3009
3010
3011
3012
3013
3014
3015
3016
3017
3018
3019
3020
3021
3022
3023
3024
3025
3026
3027
3028
3029
3030
3031
3032
3033
3034
3035
3036
3037
3038
3039
3040
3041
3042
3043
3044
3045
3046
3047
3048
3049
3050
3051
3052
3053
3054
3055
3056
3057
3058
3059
3060
3061
3062
3063
3064
3065
3066
3067
3068
3069
3070
3071
3072
3073
3074
3075
3076
3077
3078
3079
3080
3081
3082
3083
3084
3085
3086
3087
3088
3089
3090
3091
3092
3093
3094
3095
3096
3097
3098
3099
3100
3101
3102
3103
3104
3105
3106
3107
3108
3109
3110
3111
3112
3113
3114
3115
3116
3117
3118
3119
3120
3121
3122
3123
3124
3125
3126
3127
3128
3129
3130
3131
3132
3133
3134
3135
3136
3137
3138
3139
3140
3141
3142
3143
3144
3145
3146
3147
3148
3149
3150
3151
3152
3153
3154
3155
3156
3157
3158
3159
3160
3161
3162
3163
3164
3165
3166
3167
3168
3169
3170
3171
3172
3173
3174
3175
3176
3177
3178
3179
3180
3181
3182
3183
3184
3185
3186
3187
3188
3189
3190
3191
3192
3193
3194
3195
3196
3197
3198
3199
3200
3201
3202
3203
3204
3205
3206
3207
3208
3209
3210
3211
3212
3213
3214
3215
3216
3217
3218
3219
3220
3221
3222
3223
3224
3225
3226
3227
3228
3229
3230
3231
3232
3233
3234
3235
3236
3237
3238
3239
3240
3241
3242
3243
3244
3245
3246
3247
3248
3249
3250
3251
3252
3253
3254
3255
3256
3257
3258
3259
3260
3261
3262
3263
3264
3265
3266
3267
3268
3269
3270
3271
3272
3273
3274
3275
3276
3277
3278
3279
3280
3281
3282
3283
3284
3285
3286
3287
3288
3289
3290
3291
3292
3293
3294
3295
3296
3297
3298
3299
3300
3301
3302
3303
3304
3305
3306
3307
3308
3309
3310
3311
3312
3313
3314
3315
3316
3317
3318
3319
3320
3321
3322
3323
3324
3325
3326
3327
3328
3329
3330
3331
3332
3333
3334
3335
3336
3337
3338
3339
3340
3341
3342
3343
3344
3345
3346
3347
3348
3349
3350
3351
3352
3353
3354
3355
3356
3357
3358
3359
3360
3361
3362
3363
3364
3365
3366
3367
3368
3369
3370
3371
3372
3373
3374
3375
3376
3377
3378
3379
3380
3381
3382
3383
3384
3385
3386
3387
3388
3389
3390
3391
3392
3393
3394
3395
3396
3397
3398
3399
3400
3401
3402
3403
3404
3405
3406
3407
3408
3409
3410
3411
3412
3413
3414
3415
3416
3417
3418
3419
3420
3421
3422
3423
3424
3425
3426
3427
3428
3429
3430
3431
3432
3433
3434
3435
3436
3437
3438
3439
3440
3441
3442
3443
3444
3445
3446
3447
3448
3449
3450
3451
3452
3453
3454
3455
3456
3457
3458
3459
3460
3461
3462
3463
3464
3465
3466
3467
3468
3469
3470
3471
3472
3473
3474
3475
3476
3477
3478
3479
3480
3481
3482
3483
3484
3485
3486
3487
3488
3489
3490
3491
3492
3493
3494
3495
3496
3497
3498
3499
3500
3501
3502
3503
3504
3505
3506
3507
3508
3509
3510
3511
3512
3513
3514
3515
3516
3517
3518
3519
3520
3521
3522
3523
3524
3525
3526
3527
3528
3529
3530
3531
3532
3533
3534
3535
3536
3537
3538
3539
3540
3541
3542
3543
3544
3545
3546
3547
3548
3549
3550
3551
3552
3553
3554
3555
3556
3557
3558
3559
3560
3561
3562
3563
3564
3565
3566
3567
3568
3569
3570
3571
3572
3573
3574
3575
3576
3577
3578
3579
3580
3581
3582
3583
3584
3585
3586
3587
3588
3589
3590
3591
3592
3593
3594
3595
3596
3597
3598
3599
3600
3601
3602
3603
3604
3605
3606
3607
3608
3609
3610
3611
3612
3613
3614
3615
3616
3617
3618
3619
3620
3621
3622
3623
3624
3625
3626
3627
3628
3629
3630
3631
3632
3633
3634
3635
3636
3637
3638
3639
3640
3641
3642
3643
3644
3645
3646
3647
3648
3649
3650
3651
3652
3653
3654
3655
3656
3657
3658
3659
3660
3661
3662
3663
3664
3665
3666
3667
3668
3669
3670
3671
3672
3673
3674
3675
3676
3677
3678
3679
3680
3681
3682
3683
3684
3685
3686
3687
3688
3689
3690
3691
3692
3693
3694
3695
3696
3697
3698
3699
3700
3701
3702
3703
3704
3705
3706
3707
3708
3709
3710
3711
3712
3713
3714
3715
3716
3717
3718
3719
3720
3721
3722
3723
3724
3725
3726
3727
3728
3729
3730
3731
3732
3733
3734
3735
3736
3737
3738
3739
3740
3741
3742
3743
3744
3745
3746
3747
3748
3749
3750
3751
3752
3753
3754
3755
3756
3757
3758
3759
3760
3761
3762
3763
3764
3765
3766
3767
3768
3769
3770
3771
3772
3773
3774
3775
3776
3777
3778
3779
3780
3781
3782
3783
3784
3785
3786
3787
3788
3789
3790
3791
3792
3793
3794
3795
3796
3797
3798
3799
3800
3801
3802
3803
3804
3805
3806
3807
3808
3809
3810
3811
3812
3813
3814
3815
3816
3817
3818
3819
3820
3821
3822
3823
3824
3825
3826
3827
3828
3829
3830
3831
3832
3833
3834
3835
3836
3837
3838
3839
3840
3841
3842
3843
3844
3845
3846
3847
3848
3849
3850
3851
3852
3853
3854
3855
3856
3857
3858
3859
3860
3861
3862
3863
3864
3865
3866
3867
3868
3869
3870
3871
3872
3873
3874
3875
3876
3877
3878
3879
3880
3881
3882
3883
3884
3885
3886
3887
3888
3889
3890
3891
3892
3893
3894
3895
3896
3897
3898
3899
3900
3901
3902
3903
3904
3905
3906
3907
3908
3909
3910
3911
3912
3913
3914
3915
3916
3917
3918
3919
3920
3921
3922
3923
3924
3925
3926
3927
3928
3929
3930
3931
3932
3933
3934
3935
3936
3937
3938
3939
3940
3941
3942
3943
3944
3945
3946
3947
3948
3949
3950
3951
3952
3953
3954
3955
3956
3957
3958
3959
3960
3961
3962
3963
3964
3965
3966
3967
3968
3969
3970
3971
3972
3973
3974
3975
3976
3977
3978
3979
3980
3981
3982
3983
3984
3985
3986
3987
3988
3989
3990
3991
3992
3993
3994
3995
3996
3997
3998
3999
4000
4001
4002
4003
4004
4005
4006
4007
4008
4009
4010
4011
4012
4013
4014
4015
4016
4017
4018
4019
4020
4021
4022
4023
4024
4025
4026
4027
4028
4029
4030
4031
4032
4033
4034
4035
4036
4037
4038
4039
4040
4041
4042
4043
4044
4045
4046
4047
4048
4049
4050
4051
4052
4053
4054
4055
4056
4057
4058
4059
4060
4061
4062
4063
4064
4065
4066
4067
4068
4069
4070
4071
4072
4073
4074
4075
4076
4077
4078
4079
4080
4081
4082
4083
4084
4085
4086
4087
4088
4089
4090
4091
4092
4093
4094
4095
4096
4097
4098
4099
4100
4101
4102
4103
4104
4105
4106
4107
4108
4109
4110
4111
4112
4113
4114
4115
4116
4117
4118
4119
4120
4121
4122
4123
4124
4125
4126
4127
4128
4129
4130
4131
4132
4133
4134
4135
4136
4137
4138
4139
4140
4141
4142
4143
4144
4145
4146
4147
4148
4149
4150
4151
4152
4153
4154
4155
4156
4157
4158
4159
4160
4161
4162
4163
4164
4165
4166
4167
4168
4169
4170
4171
4172
4173
4174
4175
4176
4177
4178
4179
4180
4181
4182
4183
4184
4185
4186
4187
4188
4189
4190
4191
4192
4193
4194
4195
4196
4197
4198
4199
4200
4201
4202
4203
4204
4205
4206
4207
4208
4209
4210
4211
4212
4213
4214
4215
4216
4217
4218
4219
4220
4221
4222
4223
4224
4225
4226
4227
4228
4229
4230
4231
4232
4233
4234
4235
4236
4237
4238
4239
4240
4241
4242
4243
4244
4245
4246
4247
4248
4249
4250
4251
4252
4253
4254
4255
4256
4257
4258
4259
4260
4261
4262
4263
4264
4265
4266
4267
4268
4269
4270
4271
4272
4273
4274
4275
4276
4277
4278
4279
4280
4281
4282
4283
4284
4285
4286
4287
4288
4289
4290
4291
4292
4293
4294
4295
4296
4297
4298
4299
4300
4301
4302
4303
4304
4305
4306
4307
4308
4309
4310
4311
4312
4313
4314
4315
4316
4317
4318
4319
4320
4321
4322
4323
4324
4325
4326
4327
4328
4329
4330
4331
4332
4333
4334
4335
4336
4337
4338
4339
4340
4341
4342
4343
4344
4345
4346
4347
4348
4349
4350
4351
4352
4353
4354
4355
4356
4357
4358
4359
4360
4361
4362
4363
4364
4365
4366
4367
4368
4369
4370
4371
4372
4373
4374
4375
4376
4377
4378
4379
4380
4381
4382
4383
4384
4385
4386
4387
4388
4389
4390
4391
4392
4393
4394
4395
4396
4397
4398
4399
4400
4401
4402
4403
4404
4405
4406
4407
4408
4409
4410
4411
4412
4413
4414
4415
4416
4417
4418
4419
4420
4421
4422
4423
4424
4425
4426
4427
4428
4429
4430
4431
4432
4433
4434
4435
4436
4437
4438
4439
4440
4441
4442
4443
4444
4445
4446
4447
4448
4449
4450
4451
4452
4453
4454
4455
4456
4457
4458
4459
4460
4461
4462
4463
4464
4465
4466
4467
4468
4469
4470
4471
4472
4473
4474
4475
4476
4477
4478
4479
4480
4481
4482
4483
4484
4485
4486
4487
4488
4489
4490
4491
4492
4493
4494
4495
4496
4497
4498
4499
4500
4501
4502
4503
4504
4505
4506
4507
4508
4509
4510
4511
4512
4513
4514
4515
4516
4517
4518
4519
4520
4521
4522
4523
4524
4525
4526
4527
4528
4529
4530
4531
4532
4533
4534
4535
4536
4537
4538
4539
4540
4541
4542
4543
4544
4545
4546
4547
4548
4549
4550
4551
4552
4553
4554
4555
4556
4557
4558
4559
4560
4561
4562
4563
4564
4565
4566
4567
4568
4569
4570
4571
4572
4573
4574
4575
4576
4577
4578
4579
4580
4581
4582
4583
4584
4585
4586
4587
4588
4589
4590
4591
4592
4593
4594
4595
4596
4597
4598
4599
4600
4601
4602
4603
4604
4605
4606
4607
4608
4609
4610
4611
4612
4613
4614
4615
4616
4617
4618
4619
4620
4621
4622
4623
4624
4625
4626
4627
4628
4629
4630
4631
4632
4633
4634
4635
4636
4637
4638
4639
4640
4641
4642
4643
4644
4645
4646
4647
4648
4649
4650
4651
4652
4653
4654
4655
4656
4657
4658
4659
4660
4661
4662
4663
4664
4665
4666
4667
4668
4669
4670
4671
4672
4673
4674
4675
4676
4677
4678
4679
4680
4681
4682
4683
4684
4685
4686
4687
4688
4689
4690
4691
4692
4693
4694
4695
4696
4697
4698
4699
4700
4701
4702
4703
4704
4705
4706
4707
4708
4709
4710
4711
4712
4713
4714
4715
4716
4717
4718
4719
4720
4721
4722
4723
4724
4725
4726
4727
4728
4729
4730
4731
4732
4733
4734
4735
4736
4737
4738
4739
4740
4741
4742
4743
4744
4745
4746
4747
4748
4749
4750
4751
4752
4753
4754
4755
4756
4757
4758
4759
4760
4761
4762
4763
4764
4765
4766
4767
4768
4769
4770
4771
4772
4773
4774
4775
4776
4777
4778
4779
4780
4781
4782
4783
4784
4785
4786
4787
4788
4789
4790
4791
4792
4793
4794
4795
4796
4797
4798
4799
4800
4801
4802
4803
4804
4805
4806
4807
4808
4809
4810
4811
4812
4813
4814
4815
4816
4817
4818
4819
4820
4821
4822
4823
4824
4825
4826
4827
4828
4829
4830
4831
4832
4833
4834
4835
4836
4837
4838
4839
4840
4841
4842
4843
4844
4845
4846
4847
4848
4849
4850
4851
4852
4853
4854
4855
4856
4857
4858
4859
4860
4861
4862
4863
4864
4865
4866
4867
4868
4869
4870
4871
4872
4873
4874
4875
4876
4877
4878
4879
4880
4881
4882
4883
4884
4885
4886
4887
4888
4889
4890
4891
4892
4893
4894
4895
4896
4897
4898
4899
4900
4901
4902
4903
4904
4905
4906
4907
4908
4909
4910
4911
4912
4913
4914
4915
4916
4917
4918
4919
4920
4921
4922
4923
4924
4925
4926
4927
4928
4929
4930
4931
4932
4933
4934
4935
4936
4937
4938
4939
4940
4941
4942
4943
4944
4945
4946
4947
4948
4949
4950
4951
4952
4953
4954
4955
4956
4957
4958
4959
4960
4961
4962
4963
4964
4965
4966
4967
4968
4969
4970
4971
4972
4973
4974
4975
4976
4977
4978
4979
4980
4981
4982
4983
4984
4985
4986
4987
4988
4989
4990
4991
4992
4993
4994
4995
4996
4997
4998
4999
5000
5001
5002
5003
5004
5005
5006
5007
5008
5009
5010
5011
5012
5013
5014
5015
5016
5017
5018
5019
5020
5021
5022
5023
5024
5025
5026
5027
5028
5029
5030
5031
5032
5033
5034
5035
5036
5037
5038
5039
5040
5041
5042
5043
5044
5045
5046
5047
5048
5049
5050
5051
5052
5053
5054
5055
5056
5057
5058
5059
5060
5061
5062
5063
5064
5065
5066
5067
5068
5069
5070
5071
5072
5073
5074
5075
5076
5077
5078
5079
5080
5081
5082
5083
5084
5085
5086
5087
5088
5089
5090
5091
5092
5093
5094
5095
5096
5097
5098
5099
5100
5101
5102
5103
5104
5105
5106
5107
5108
5109
5110
5111
5112
5113
5114
5115
5116
5117
5118
5119
5120
5121
5122
5123
5124
5125
5126
5127
5128
5129
5130
5131
5132
5133
5134
5135
5136
5137
5138
5139
5140
5141
5142
5143
5144
5145
5146
5147
5148
5149
5150
5151
5152
5153
5154
5155
5156
5157
5158
5159
5160
5161
5162
5163
5164
5165
5166
5167
5168
5169
5170
5171
5172
5173
5174
5175
5176
5177
5178
5179
5180
5181
5182
5183
5184
5185
5186
5187
5188
5189
5190
5191
5192
5193
5194
5195
5196
5197
5198
5199
5200
5201
5202
5203
5204
5205
5206
5207
5208
5209
5210
5211
5212
5213
5214
5215
5216
5217
5218
5219
5220
5221
5222
5223
5224
5225
5226
5227
5228
5229
5230
5231
5232
5233
5234
5235
5236
5237
5238
5239
5240
5241
5242
5243
5244
5245
5246
5247
5248
5249
5250
5251
5252
5253
5254
5255
5256
5257
5258
5259
5260
5261
5262
5263
5264
5265
5266
5267
5268
5269
5270
5271
5272
5273
5274
5275
5276
5277
5278
5279
5280
5281
5282
5283
5284
5285
5286
5287
5288
5289
5290
5291
5292
5293
5294
5295
5296
5297
5298
5299
5300
5301
5302
5303
5304
5305
5306
5307
5308
5309
5310
5311
5312
5313
5314
5315
5316
5317
5318
5319
5320
5321
5322
5323
5324
5325
5326
5327
5328
5329
5330
5331
5332
5333
5334
5335
5336
5337
5338
5339
5340
5341
5342
5343
5344
5345
5346
5347
5348
5349
5350
5351
5352
5353
5354
5355
5356
5357
5358
5359
5360
5361
5362
5363
5364
5365
5366
5367
5368
5369
5370
5371
5372
5373
5374
5375
5376
5377
5378
5379
5380
5381
5382
5383
5384
5385
5386
5387
5388
5389
5390
5391
5392
5393
5394
5395
5396
5397
5398
5399
5400
5401
5402
5403
5404
5405
5406
5407
5408
5409
5410
5411
5412
5413
5414
5415
5416
5417
5418
5419
5420
5421
5422
5423
5424
5425
5426
5427
5428
5429
5430
5431
5432
5433
5434
5435
5436
5437
5438
5439
5440
5441
5442
5443
5444
5445
5446
5447
5448
5449
5450
5451
5452
5453
5454
5455
5456
5457
5458
5459
5460
5461
5462
5463
5464
5465
5466
5467
5468
5469
5470
5471
5472
5473
5474
5475
5476
5477
5478
5479
5480
5481
5482
5483
5484
5485
5486
5487
5488
5489
5490
5491
5492
5493
5494
5495
5496
5497
5498
5499
5500
5501
5502
5503
5504
5505
5506
5507
5508
5509
5510
5511
5512
5513
5514
5515
5516
5517
5518
5519
5520
5521
5522
5523
5524
5525
5526
5527
5528
5529
5530
5531
5532
5533
5534
5535
5536
5537
5538
5539
5540
5541
5542
5543
5544
5545
5546
5547
5548
5549
5550
5551
5552
5553
5554
5555
5556
5557
5558
5559
5560
5561
5562
5563
5564
5565
5566
5567
5568
5569
5570
5571
5572
5573
5574
5575
5576
5577
5578
5579
5580
5581
5582
5583
5584
5585
5586
5587
5588
5589
5590
5591
5592
5593
5594
5595
5596
5597
5598
5599
5600
5601
5602
5603
5604
5605
5606
5607
5608
5609
5610
5611
5612
5613
5614
5615
5616
5617
5618
5619
5620
5621
5622
5623
5624
5625
5626
5627
5628
5629
5630
5631
5632
5633
5634
5635
5636
5637
5638
5639
5640
5641
5642
5643
5644
5645
5646
5647
5648
5649
5650
5651
5652
5653
5654
5655
5656
5657
5658
5659
5660
5661
5662
5663
5664
5665
5666
5667
5668
5669
5670
5671
5672
5673
5674
5675
5676
5677
5678
5679
5680
5681
5682
5683
5684
5685
5686
5687
5688
5689
5690
5691
5692
5693
5694
5695
5696
5697
5698
5699
5700
5701
5702
5703
5704
5705
5706
5707
5708
5709
5710
5711
5712
5713




Network Working Group                                             J. Moy
Request for Comments: 1584                                 Proteon, Inc.
Category: Standards Track                                     March 1994


                      Multicast Extensions to OSPF



Status of this Memo

    This document specifies an Internet standards track protocol for the
    Internet community, and requests discussion and suggestions for
    improvements.  Please refer to the current edition of the "Internet
    Official Protocol Standards" (STD 1) for the standardization state
    and status of this protocol.  Distribution of this memo is
    unlimited.

Abstract

    This memo documents enhancements to the OSPF protocol enabling the
    routing of IP multicast datagrams. In this proposal, an IP multicast
    packet is routed based both on the packet's source and its multicast
    destination (commonly referred to as source/destination routing). As
    it is routed, the multicast packet follows a shortest path to each
    multicast destination. During packet forwarding, any commonality of
    paths is exploited; when multiple hosts belong to a single multicast
    group, a multicast packet will be replicated only when the paths to
    the separate hosts diverge.

    OSPF, a link-state routing protocol, provides a database describing
    the Autonomous System's topology. A new OSPF link state
    advertisement is added describing the location of multicast
    destinations. A multicast packet's path is then calculated by
    building a pruned shortest-path tree rooted at the packet's IP
    source. These trees are built on demand, and the results of the
    calculation are cached for use by subsequent packets.

    The multicast extensions are built on top of OSPF Version 2. The
    extensions have been implemented so that a multicast routing
    capability can be introduced piecemeal into an OSPF Version 2
    routing domain. Some of the OSPF Version 2 routers may run the
    multicast extensions, while others may continue to be restricted to
    the forwarding of regular IP traffic (unicasts).

    Please send comments to mospf@gated.cornell.edu.





Moy                                                             [Page 1]

RFC 1584              Multicast Extensions to OSPF            March 1994


Table of Contents

    1       Introduction ........................................... 4
    1.1     Terminology ............................................ 5
    1.2     Acknowledgments ........................................ 6
    2       Multicast routing in MOSPF ............................. 6
    2.1     Routing characteristics ................................ 6
    2.2     Sample path of a multicast datagram .................... 8
    2.3     MOSPF forwarding mechanism ............................ 10
    2.3.1   IGMP interface: the local group database .............. 10
    2.3.2   A datagram's shortest-path tree ....................... 14
    2.3.3   Support for Non-broadcast networks .................... 16
    2.3.4   Details concerning forwarding cache entries ........... 16
    3       Inter-area multicasting ............................... 18
    3.1     Extent of group-membership-LSAs ....................... 19
    3.2     Building inter-area datagram shortest-path trees ...... 22
    4       Inter-AS multicasting ................................. 27
    4.1     Building inter-AS datagram shortest-path trees ........ 28
    4.2     Stub area behavior .................................... 30
    4.3     Inter-AS multicasting in a core Autonomous System ..... 31
    5       Modelling internal group membership ................... 31
    6       Additional capabilities ............................... 33
    6.1     Mixing with non-multicast routers ..................... 34
    6.2     TOS-based multicast ................................... 35
    6.3     Assigning multiple IP networks to a physical network .. 36
    6.4     Networks on Autonomous System boundaries .............. 37
    6.5     Recommended system configuration ...................... 38
    7       Basic implementation requirements ..................... 40
    8       Protocol data structures .............................. 40
    8.1     Additions to the OSPF area structure .................. 41
    8.2     Additions to the OSPF interface structure ............. 42
    8.3     Additions to the OSPF neighbor structure .............. 43
    8.4     The local group database .............................. 43
    8.5     The forwarding cache .................................. 44
    9       Interaction with the IGMP protocol .................... 45
    9.1     Sending IGMP Host Membership Queries .................. 46
    9.2     Receiving IGMP Host Membership Reports ................ 46
    9.3     Aging local group database entries .................... 47
    9.4     Receiving IGMP Host Membership Queries ................ 47
    10      Group-membership-LSAs ................................. 48
    10.1    Constructing group-membership-LSAs .................... 49
    10.2    Flooding group-membership-LSAs ........................ 52
    11      Detailed description of multicast datagram forwarding . 52
    11.1    Associating a MOSPF interface with a received datagram  55
    11.2    Locating the source network ........................... 55
    11.3    Forwarding locally originated multicasts .............. 57
    12      Construction of forwarding cache entries .............. 58
    12.1    The Vertex data structure ............................. 59



Moy                                                             [Page 2]

RFC 1584              Multicast Extensions to OSPF            March 1994


    12.2    The SPF calculation ................................... 60
    12.2.1  Candidate list Initialization: Case SourceIntraArea ... 65
    12.2.2  Candidate list Initialization: Case SourceInterArea1 .. 66
    12.2.3  Candidate list Initialization: Case SourceInterArea2 .. 66
    12.2.4  Candidate list Initialization: Case SourceExternal .... 67
    12.2.5  Candidate list Initialization: Case SourceStubExternal  70
    12.2.6  Processing labelled vertices .......................... 70
    12.2.7  Merging datagram shortest-path trees .................. 71
    12.2.8  TOS considerations .................................... 72
    12.2.9  Comparison to the unicast SPF calculation ............. 74
    12.3    Adding local database entries to the forwarding cache   75
    13      Maintaining the forwarding cache ...................... 76
    14      Other additions to the OSPF specification ............. 77
    14.1    The Designated Router ................................. 77
    14.2    Sending Hello packets ................................. 78
    14.3    The Neighbor state machine ............................ 78
    14.4    Receiving Database Description packets ................ 78
    14.5    Sending Database Description packets .................. 79
    14.6    Originating Router-LSAs ............................... 79
    14.7    Originating Network-LSAs .............................. 79
    14.8    Originating Summary-link-LSAs ......................... 80
    14.9    Originating AS external-link-LSAs ..................... 80
    14.10   Next step in the flooding procedure ................... 81
    14.11   Virtual links ......................................... 81
    15      References ............................................ 83
            Footnotes ............................................. 84
    A       Data Formats .......................................... 88
    A.1     The Options field ..................................... 89
    A.2     Router-LSA ............................................ 91
    A.3     Group-membership-LSA .................................. 93
    B       Configurable Constants ................................ 95
    B.1     Global parameters ..................................... 95
    B.2     Router interface parameters ........................... 95
    C       Sample datagram shortest-path trees ................... 97
    C.1     An intra-area tree .................................... 98
    C.2     The effect of areas .................................. 100
    C.3     The effect of virtual links .......................... 101
            Security Considerations .............................. 102
            Author's Address ..................................... 102












Moy                                                             [Page 3]

RFC 1584              Multicast Extensions to OSPF            March 1994


1.  Introduction

    This memo documents enhancements to OSPF Version 2 to support IP
    multicast routing. The enhancements have been added in a backward-
    compatible fashion; routers running the multicast additions will
    interoperate with non-multicast OSPF routers when forwarding regular
    (unicast) IP data traffic. The protocol resulting from the addition
    of the multicast enhancements to OSPF is herein referred to as the
    MOSPF protocol.

    IP multicasting is an extension of LAN multicasting to a TCP/IP
    internet. Multicasting support for TCP/IP hosts has been specified
    in [RFC 1112]. In that document, multicast groups are represented by
    IP class D addresses. Individual TCP/IP hosts join (and leave)
    multicast groups through the Internet Group Management Protocol
    (IGMP, also specified in [RFC 1112]). A host need not be a member of
    a multicast group in order to send datagrams to the group. Multicast
    datagrams are to be delivered to each member of the multicast group
    with the same "best-effort" delivery accorded regular (unicast) IP
    data traffic.

    MOSPF provides the ability to forward multicast datagrams from one
    IP network to another (i.e., through internet routers). MOSPF
    forwards a multicast datagram on the basis of both the datagram's
    source and destination (this is sometimes called source/destination
    routing). The OSPF link state database provides a complete
    description of the Autonomous System's topology. By adding a new
    type of link state advertisement, the group-membership-LSA, the
    location of all multicast group members is pinpointed in the
    database. The path of a multicast datagram can then be calculated by
    building a shortest-path tree rooted at the datagram's source. All
    branches not containing multicast members are pruned from the tree.
    These pruned shortest-path trees are initially built when the first
    datagram is received (i.e., on demand).  The results of the shortest
    path calculation are then cached for use by subsequent datagrams
    having the same source and destination.

    OSPF allows an Autonomous System to be split into areas. However,
    when this is done complete knowledge of the Autonomous System's
    topology is lost. When forwarding multicasts between areas, only
    incomplete shortest-path trees can be built. This may lead to some
    inefficiency in routing. An analogous situation exists when the
    source of the multicast datagram lies in another Autonomous System.
    In both cases (i.e., the source of the datagram belongs to a
    different OSPF area, or to a different Autonomous system) the
    neighborhood immediately surrounding the source is unknown. In these
    cases the source's neighborhood is approximated by OSPF summary link
    advertisements or by OSPF AS external link advertisements



Moy                                                             [Page 4]

RFC 1584              Multicast Extensions to OSPF            March 1994


    respectively.

    Routers running MOSPF can be intermixed with non-multicast OSPF
    routers. Both types of routers can interoperate when forwarding
    regular (unicast) IP data traffic. Obviously, the forwarding extent
    of IP multicasts is limited by the number of MOSPF routers present
    in the Autonomous System (and their interconnection, if any). An
    ability to "tunnel" multicast datagrams through non-multicast
    routers is not provided. In MOSPF, just as in the base OSPF
    protocol, datagrams (multicast or unicast) are routed "as is" --
    they are not further encapsulated or decapsulated as they transit
    the Autonomous System.

    1.1.  Terminology

        This memo uses the terminology listed in section 1.2 of [OSPF].
        For this reason, terms such as "Network", "Autonomous System"
        and "link state advertisement" are assumed to be understood. In
        addition, the abbreviation LSA is used for "link state
        advertisement". For example, router links advertisements are
        referred to as router-LSAs and the new link state advertisement
        describing the location of members of a multicast group is
        referred to as a group-membership-LSA.

        [RFC 1112] discusses the data-link encapsulation of IP multicast
        datagrams. In contrast to the normal forwarding of IP unicast
        datagrams, on a broadcast network the mapping of an IP multicast
        destination to a data-link destination address is not done with
        the ARP protocol. Instead, static mappings have been defined
        from IP multicast destinations to data-link addresses. These
        mappings are dependent on network type; for some networks IP
        multicasts are algorithmically mapped to data-link multicast
        addresses, for other networks all IP multicast destinations are
        mapped onto the data-link broadcast address. This document
        loosely describes both of these possible mappings as data-link
        multicast.

        The following terms are also used throughout this document:

        o   Non-multicast router. A router running OSPF Version 2, but
            not the multicast extensions. These routers do not forward
            multicast datagrams, but can interoperate with MOSPF routers
            in the forwarding of unicast packets. Routers running the
            MOSPF protocol are referred to herein as either multicast-
            capable routers or MOSPF routers.

        o   Non-broadcast networks. A network supporting the attachment
            of more than two stations, but not supporting the delivery



Moy                                                             [Page 5]

RFC 1584              Multicast Extensions to OSPF            March 1994


            of a single physical datagram to multiple destinations
            (i.e., not supporting data-link multicast). [OSPF] describes
            these networks as non-broadcast, multi-access networks. An
            example of a non-broadcast network is an X.25 PDN.

        o   Transit network. A network having two or more OSPF routers
            attached.  These networks can forward data traffic that is
            neither locally-originated nor locally-destined. In OSPF,
            with the exception of point-to-point networks and virtual
            links, the neighborhood of each transit network is described
            by a network links advertisement (network-LSA).

        o   Stub network. A network having only a single OSPF router
            attached. A network belonging to an OSPF system is either a
            transit or a stub network, but never both.

    1.2.  Acknowledgments

        The multicast extensions to OSPF are based on Link-State
        Multicast Routing algorithm presented in [Deering]. In addition,
        the [Deering] paper contains a section on Hierarchical Multicast
        Routing (providing the ideas for MOSPF's inter-area multicasting
        scheme) and several Distance Vector (also called Bellman-Ford)
        multicast algorithms. One of these Distance Vector multicast
        algorithms, Truncated Reverse Path Broadcasting, has been
        implemented in the Internet (see [RFC 1075]).

        The MOSPF protocol has been developed by the MOSPF Working Group
        of the Internet Engineering Task Force. Portions of this work
        have been supported by DARPA under NASA contract NAG 2-650.

2.  Multicast routing in MOSPF

    This section describes MOSPF's basic multicast routing algorithm.
    The basic algorithm, run inside a single OSPF area, covers the case
    where the source of the multicast datagram is inside the area
    itself. Within the area, the path of the datagram forms a tree
    rooted at the datagram source.

    2.1.  Routing characteristics

        As a multicast datagram is forwarded along its shortest-path
        tree, the datagram is delivered to each member of the
        destination multicast group. In MOSPF, the forwarding of the
        multicast datagram has the following properties:

        o   The path taken by a multicast datagram depends both on the
            datagram's source and its multicast destination. Called



Moy                                                             [Page 6]

RFC 1584              Multicast Extensions to OSPF            March 1994


            source/destination routing, this is in contrast to most
            unicast datagram forwarding algorithms (like OSPF) that
            route based solely on destination.

        o   The path taken between the datagram's source and any
            particular destination group member is the least cost path
            available. Cost is expressed in terms of the OSPF link-state
            metric. For example, if the OSPF metric represents delay, a
            minimum delay path is chosen. OSPF metrics are configurable.
            A metric is assigned to each outbound router interface,
            representing the cost of sending a packet on that interface.
            The cost of a path is the sum of its constituent (outbound)
            router interfaces[1].

        o   MOSPF takes advantage of any commonality of least cost paths
            to destination group members. However, when members of the
            multicast group are spread out over multiple networks, the
            multicast datagram must at times be replicated. This
            replication is performed as few times as possible (at the
            tree branches), taking maximum advantage of common path
            segments.

        o   For a given multicast datagram, all routers calculate an
            identical shortest-path tree. There is a single path between
            the datagram's source and any particular destination group
            member. This means that, unlike OSPF's treatment of regular
            (unicast) IP data traffic, there is no provision for equal-
            cost multipath.

        o   On each packet hop, MOSPF normally forwards IP multicast
            datagrams as data-link multicasts. There are two exceptions.
            First, on non-broadcast networks, since there are no data-
            link multicast/broadcast services the datagram must be
            forwarded to specific MOSPF neighbors (see Section 2.3.3).
            Second, a MOSPF router can be configured to forward IP
            multicasts on specific networks as data-link unicasts, in
            order to avoid datagram replication in certain anomalous
            situations (see Section 6.4).

        While MOSPF optimizes the path to any given group member, it
        does not necessarily optimize the use of the internetwork as a
        whole. To do so, instead of calculating source-based shortest-
        path trees, something similar to a minimal spanning tree
        (containing only the group members) would need to be calculated.
        This type of minimal spanning tree is called a Steiner tree in
        the literature. For a comparison of shortest-path tree routing
        to routing using Steiner trees, see [Deering2] and [Bharath-
        Kumar].



Moy                                                             [Page 7]

RFC 1584              Multicast Extensions to OSPF            March 1994


    2.2.  Sample path of a multicast datagram

        As an example of multicast datagram routing in MOSPF, consider
        the sample Autonomous System pictured in Figure 1. This figure
        has been taken from the OSPF specification (see [OSPF]). The
        larger rectangles represent routers, the smaller rectangles
        hosts. Oblongs and circles represent multi-access networks[2].
        Lines joining routers are point-to-point serial connections. A
        cost has been assigned to each outbound router interface.

        All routers in Figure 1 are assumed to be running MOSPF. A
        number of hosts have been added to the figure. The hosts
        labelled Ma have joined a particular multicast group (call it
        Group A) via the IGMP protocol.  These hosts are located on
        networks N2, N6 and N11. Similarly, using IGMP the hosts
        labelled Mb have joined a separate multicast group B; these
        hosts are located on networks N1, N2 and N3. Note that hosts can
        join multiple multicast groups; it is only for clarity of
        presentation that each host has joined at most one multicast
        group in this example.  Also, hosts H2 through H5 have been
        added to the figure to serve as sources for multicast datagrams.
        Again, the datagrams' sources have been made separate from the
        group members only for clarity of presentation.

        To illustrate the forwarding of a multicast datagram, suppose
        that Host H2 (attached to Network N4) sends a multicast datagram
        to multicast group B. This datagram originates as a data-link
        layer multicast on Network N4. Router RT3, being a multicast
        router, has "opened up" its interface data-link multicast
        filters. It therefore receives the multicast datagram, and
        attempts to forward it to the members of multicast group B
        (located on networks N1, N2 and N3). This is accomplished by
        sending a single copy of the datagram onto Network N3, again as
        a data-link multicast[3].  Upon receiving the multicast datagram
        from RT3, routers RT1 and RT2 will then multicast the datagram
        on their connected stub networks (N1 and N2 respectively).  Note
        that, since the datagram is sent onto Network N3 as a data-link
        multicast, Router RT4 will also receive a copy. However, it will
        not forward the datagram, since it does not lie on a shortest
        path between the source (Host H2) and any members of multicast
        group B.

        Note that the path of the multicast datagram depends on the
        datagram's source network. If the above multicast datagram was
        instead originated by Host H3, the path taken would be
        identical, since hosts H2 and H3 lie on the same network
        (Network N4). However, if the datagram was originated by Host
        H4, its path would be different. In this case, when Router RT3



Moy                                                             [Page 8]

RFC 1584              Multicast Extensions to OSPF            March 1994





                 +
                 | 3+---+    +--+  +--+       N12      N14
               N1|--|RT1|\1  |Mb|  |H4|         \ N13 /
                _|  +---+ \  +--+ /+--+         8\ |8/8
               | +         \ _|__/                \|/
             +--+   +--+    /    \   1+---+8    8+---+6
             |Mb|   |Mb|   *  N3  *---|RT4|------|RT5|--------+
             +--+  /+--+    \____/    +---+      +---+        |
                  +         /   |                  |7         |
                  | 3+---+ /    |                  |          |
                N2|--|RT2|/1    |1                 |6         |
                __|  +---+    +---+8            6+---+        |
               |  +           |RT3|--------------|RT6|        |
             +--+    +--+     +---+     +--+     +---+        |
             |Ma|    |H3|_      |2     _|H2|     Ia|7         |
             +--+    +--+ \     |     / +--+       |          |
                           +---------+             |          |
                               N4                  |          |
                                                   |          |
                                                   |          |
                       N11                         |          |
                   +---------+                     |          |
                        |     \                    |          |    N12
                        |3     +--+                |          |6 2/
                      +---+    |Ma|                |        +---+/
                      |RT9|    +--+                |        |RT7|---N15
                      +---+                        |        +---+ 9
                        |1                   +     |          |1
                       _|__                  |   Ib|5       __|_   +--+
                      /    \      1+----+2   |  3+----+1   /    \--|Ma|
                     *  N9  *------|RT11|----|---|RT10|---*  N6  * +--+
                      \____/       +----+    |   +----+    \____/
                        |                    |                |
                        |1                   +                |1
             +--+   10+----+                N8              +---+
             |H1|-----|RT12|                                |RT8|
             +--+SLIP +----+                                +---+  +--+
                        |2                                    |4  _|H5|
                        |                                     |  / +--+
                   +---------+                            +--------+
                       N10                                    N7

                    Figure 1: A sample MOSPF configuration





Moy                                                             [Page 9]

RFC 1584              Multicast Extensions to OSPF            March 1994


        receives the datagram, RT3 will drop the datagram instead of
        forwarding it (since RT3 is no longer on the shortest path to
        any member of Group B).

        Note that the path of the multicast datagram also depends on the
        destination multicast group. If Host H2 sends a multicast to
        Group A, the path taken is as follows. The datagram again starts
        as a multicast on Network N4. Router RT3 receives it, and
        creates two copies. One is sent onto Network N3 which is then
        forwarded onto Network N2 by RT2. The other copy is sent to
        Router RT10 (via RT6), where the datagram is again split,
        eventually to be delivered onto networks N6 and N11. Note that,
        although multiple copies of the datagram are produced, the
        datagram itself is not modified (except for its IP TTL) as it is
        forwarded. No encapsulation of the datagram is performed; the
        destination of the datagram is always listed as the multicast
        group A.

    2.3.  MOSPF forwarding mechanism

        Each MOSPF router in the path of a multicast datagram bases its
        forwarding decision on the contents of a data cache. This cache
        is called the forwarding cache. There is a separate forwarding
        cache entry for each source/destination combination[4].  Each
        cache entry indicates, for multicast datagrams having matching
        source and destination, which neighboring node (i.e., router or
        network) the datagram must be received from (called the upstream
        node) and which interfaces the datagram should then be forwarded
        out of (called the downstream interfaces).

        A forwarding cache entry is actually built from two component
        pieces.  The first of these components is called the local group
        database. This database, built by the IGMP protocol, indicates
        the group membership of the router's directly attached networks.
        The local group database enables the local delivery of multicast
        datagrams. The second component is the datagram's shortest path
        tree. This tree, built on demand, is rooted at a multicast
        datagram's source. The datagram's shortest path tree enables the
        delivery of multicast datagrams to distant (i.e., not directly
        attached) group members.

        2.3.1.  IGMP interface: the local group database

            The local group database keeps track of the group membership
            of the router's directly attached networks. Each entry in
            the local group database is a [group, attached network]
            pair, which indicates that the attached network has one or
            more IP hosts belonging to the IP multicast destination



Moy                                                            [Page 10]

RFC 1584              Multicast Extensions to OSPF            March 1994


            group. This information is then used by the router when
            deciding which directly attached networks to forward a
            received IP multicast datagram onto, in order to complete
            delivery of the datagram to (local) group members.

            The local group database is built through the operation of
            the Internet Group Management Protocol (IGMP; see [RFC
            1112]). When a MOSPF router becomes Designated Router on an
            attached network (call the network N1), it starts sending
            periodic IGMP Host Membership Queries on the network. Hosts
            then respond with IGMP Host Membership Reports, one for each
            multicast group to which they belong. Upon receiving a Host
            Membership Report for a multicast group A, the router
            updates its local group database by adding/refreshing the
            entry [Group A, N1]. If at a later time Reports for Group A
            cease to be heard on the network, the entry is then deleted
            from the local group database.

            It is important to note that on any particular network, the
            sending of IGMP Host Membership Queries and the listening to
            IGMP Host Membership Reports is performed solely by the
            Designated Router. A MOSPF router ignores Host Membership
            Reports received on those networks where the router has not
            been elected Designated Router[5].  This means that at most
            one router performs these IGMP functions on any particular
            network, and ensures that the network appears in the local
            group database of at most one router. This prevents
            multicast datagrams from being replicated as they are
            delivered to local group members. As a result, each router
            in the Autonomous System has a different local group
            database. This is in contrast to the MOSPF link state
            database, and the datagram shortest-path trees (see Section
            2.3.2), all of which are identical in each router belonging
            to the Autonomous System.

            The existence of local group members must be communicated to
            the rest of the routers in the Autonomous System. This
            ensures that a remotely-originated multicast datagram will
            be forwarded to the router for distribution to its local
            group members. This communication is accomplished through
            the creation of a group-membership-LSA. Like other link
            state advertisements, the group-membership-LSA is flooded
            throughout the Autonomous System. The router originates a
            separate group-membership-LSA for each multicast group
            having one or more entries in the router's local group
            database. The router's group-membership-LSA (say for Group
            A) lists those local transit vertices (i.e., the router
            itself and/or any directly connected transit networks) that



Moy                                                            [Page 11]

RFC 1584              Multicast Extensions to OSPF            March 1994


            should not be pruned from Group A's datagram shortest-path
            trees. The router lists itself in its group-membership-LSA
            for Group A if either 1) one or more of the router's
            attached stub networks contain Group A members or 2) the
            router itself is a member of Group A. The router lists a
            directly connected transit network in the group-membership-
            LSA for Group A if both 1) the router is Designated Router
            on the network and 2) the network contains one or more Group
            A members.

            Consider again the example pictured in Figure 1. If Router
            RT3 has been elected Designated Router for Network N3, then
            Table 1: lists the local group database for the routers
            RT1-RT4.

            In this case, each of the routers RT1, RT2 and RT3 will
            originate a group-membership-LSA for Group B. In addition,
            RT2 will also be originating a group-membership-LSA for
            Group A. RT1 and RT2's group-membership-LSAs will list
            solely the routers themselves (N1 and N2 are stub networks).
            RT3's group-membership-LSA will list the transit Network N3.

            Figure 2 displays the Autonomous System's link state
            database. A router/transit network is labelled with a
            multicast group if (and only if) it has been mentioned in a
            group-membership-LSA for the group When building the
            shortest-path tree for a particular multicast datagram, this
            labelling enables those branches without group members to be
            pruned from the tree. The process of building a multicast
            datagram's shortest path tree is discussed in Section 2.3.2.

            Note that none of the hosts in Figure 1 belonging to
            multicast groups A and B show up explicitly in the link
            state database (see Figure 2).  In fact, looking at the link
            state database you cannot even determine which stub networks


                 Router   local group database
                 _____________________________________
                 RT1      [Group B, N1]
                 RT2      [Group A, N2], [Group B, N2]
                 RT3      [Group B, N3]
                 RT4      None


                 Table 1: Sample local group databases





Moy                                                            [Page 12]

RFC 1584              Multicast Extensions to OSPF            March 1994





                                **FROM**

                 |RT|RT|RT|RT|RT|RT|RT|RT|RT|RT|RT|RT|
                 |1 |2 |3 |4 |5 |6 |7 |8 |9 |10|11|12|N3|N6|N8|N9|
              ----- ---------------------------------------------
              RT1|  |  |  |  |  |  |  |  |  |  |  |  |0 |  |  |  |
              RT2|  |  |  |  |  |  |  |  |  |  |  |  |0 |  |  |  |
              RT3|  |  |  |  |  |6 |  |  |  |  |  |  |0 |  |  |  |
              RT4|  |  |  |  |8 |  |  |  |  |  |  |  |0 |  |  |  |
              RT5|  |  |  |8 |  |6 |6 |  |  |  |  |  |  |  |  |  |
              RT6|  |  |8 |  |7 |  |  |  |  |5 |  |  |  |  |  |  |
              RT7|  |  |  |  |6 |  |  |  |  |  |  |  |  |0 |  |  |
          *   RT8|  |  |  |  |  |  |  |  |  |  |  |  |  |0 |  |  |
          *   RT9|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |0 |
          T  RT10|  |  |  |  |  |7 |  |  |  |  |  |  |  |0 |0 |  |
          O  RT11|  |  |  |  |  |  |  |  |  |  |  |  |  |  |0 |0 |
          *  RT12|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |0 |
          *    N1|3 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
               N2|  |3 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
               N3|1 |1 |1 |1 |  |  |  |  |  |  |  |  |  |  |  |  |
               N4|  |  |2 |  |  |  |  |  |  |  |  |  |  |  |  |  |
               N6|  |  |  |  |  |  |1 |1 |  |1 |  |  |  |  |  |  |
               N7|  |  |  |  |  |  |  |4 |  |  |  |  |  |  |  |  |
               N8|  |  |  |  |  |  |  |  |  |3 |2 |  |  |  |  |  |
               N9|  |  |  |  |  |  |  |  |1 |  |1 |1 |  |  |  |  |
              N10|  |  |  |  |  |  |  |  |  |  |  |2 |  |  |  |  |
              N11|  |  |  |  |  |  |  |  |3 |  |  |  |  |  |  |  |
              N12|  |  |  |  |8 |  |2 |  |  |  |  |  |  |  |  |  |
              N13|  |  |  |  |8 |  |  |  |  |  |  |  |  |  |  |  |
              N14|  |  |  |  |8 |  |  |  |  |  |  |  |  |  |  |  |
              N15|  |  |  |  |  |  |9 |  |  |  |  |  |  |  |  |  |
               H1|  |  |  |  |  |  |  |  |  |  |  |10|  |  |  |  |


                     Figure 2: The MOSPF database.

                 Networks and routers are represented by vertices.
                 An edge of cost X connects Vertex A to Vertex B iff
                 the intersection of Column A and Row B is marked
                 with an X. In addition, RT1, RT2 and N3 are labelled
                 with multicast group A and RT1, N6 and RT9 are
                 labelled with multicast group B.






Moy                                                            [Page 13]

RFC 1584              Multicast Extensions to OSPF            March 1994


            contain multicast group members. The link state database
            simply indicates those routers/transit networks having
            attached group members. This is all that is necessary for
            successful forwarding of multicast datagrams.

        2.3.2.  A datagram's shortest-path tree

            While the local group database facilitates the local
            delivery of multicast datagrams, the datagram's shortest-
            path tree describes the intermediate hops taken by a
            multicast datagram as it travels from its source to the
            individual multicast group members. As mentioned above, the
            datagram's shortest-path tree is a pruned shortest-path tree
            rooted at the datagram's source. Two datagrams having
            differing [source net, multicast destination] pairs may
            have, and in fact probably will have, different pruned
            shortest-path trees.

            A datagram's shortest path tree is built "on demand"[6],
            i.e., when the first multicast datagram is received having a
            particular [source net, multicast destination] combination.
            To build the datagram's shortest-path tree, the following
            calculations are performed. First, the datagram's source IP
            network is located in the link state database. Then using
            the router-LSAs and network-LSAs in the link state database,
            a shortest-path tree is built having the source network as
            root. To complete the process, the branches that do not
            contain routers/transit networks that have been labelled
            with the particular multicast destination (via a group-
            membership-LSA) are pruned from the tree.

            As an example of the building of a datagram's shortest path
            tree, again consider the Autonomous System in Figure 1. The
            Autonomous System's link state database is pictured in
            Figure 2. When a router initially receives a multicast
            datagram sent by Host H2 to the multicast group A, the
            following steps are taken: Host H2 is first determined to be
            on Network N4. Then the shortest path tree rooted at net N4
            is calculated[7], pruning those branches that do not contain
            routers/transit networks that have been labelled with the
            multicast group A. This results in the pruned shortest-path
            tree pictured in Figure 3. Note that at this point all the
            leaves of the tree are routers/transit networks labelled
            with multicast group A (routers RT2 and RT9 and transit
            Network N6).

            In order to forward the multicast datagram, each router must
            find its own position in the datagram's shortest path tree.



Moy                                                            [Page 14]

RFC 1584              Multicast Extensions to OSPF            March 1994



                                       o RT3 (N4, origin)
                                      / \
                                    1/   \8
                                    /     \
                           N3 (Mb) o       o RT6
                                  /         \
                                0/           \7
                                /             \
                   RT2 (Ma,Mb) o               o RT10
                                              / \
                                            3/   \1
                                            /     \
                                        N8 o       o N6 (Ma)
                                          /
                                        0/
                                        /
                                  RT11 o
                                      /
                                    1/
                                    /
                                N9 o
                                  /
                                0/
                                /
                      RT9 (Ma) o



                 Figure 3: Sample datagram's shortest-path tree,
                          source N4, destination Group A

            The router's (call it Router RTX) position in the datagram's
            pruned shortest-path tree consists of 1) RTX's parent in the
            tree (this will be the forwarding cache entry's upstream
            node) and 2) the list of RTX's interfaces that lead to
            downstream routers/transit networks that have been labelled
            with the datagram's destination (these will be added to the
            forwarding cache entry as downstream interfaces). Note that
            after calculating the datagram's shortest path tree, a
            router may find that it is itself not on the tree. This
            would be indicated by a forwarding cache entry having no
            upstream node or an empty list of downstream interfaces.

            As an example of a router describing its position on the
            datagram's shortest-path tree, consider Router RT10 in
            Figure 3. Router RT10's upstream node for the datagram is
            Router RT6, and there are two downstream interfaces: one



Moy                                                            [Page 15]

RFC 1584              Multicast Extensions to OSPF            March 1994


            connecting to Network N6 and the other connecting to Network
            N8.

        2.3.3.  Support for Non-broadcast networks

            When forwarding multicast datagrams over non-broadcast
            networks, the datagram cannot be sent as a link-level
            multicast (since neither link-level multicast nor broadcast
            are supported on these networks), but must instead be
            forwarded separately to specific neighbors. To facilitate
            this, forwarding cache entries can also contain downstream
            neighbors as well as downstream interfaces.

            The IGMP protocol is not defined over non-broadcast
            networks. For this reason, there cannot be group members
            directly attached to non-broadcast networks, nor do non-
            broadcast networks ever appear in local group database
            entries.

            As an example, suppose that Network N3 in Figure 1 is an
            X.25 PDN.  Consider Router RT3's forwarding cache entry for
            datagrams having source Network N4 and multicast destination
            Group B. In place of having the interface to Network N3
            appear as the downstream interface in the matching
            forwarding cache entry, the neighboring routers RT1 and RT2
            would instead appear as separate downstream neighbors. In
            addition, in this case there could not be a Group B member
            directly attached to Network N3.

        2.3.4.  Details concerning forwarding cache entries

            Each of the downstream interface/neighbors in the cache
            entry is labelled with a TTL value. This value indicates the
            number of hops a datagram forwarded out of the interface (or
            forwarded to the neighbor) would have to travel before
            encountering a router/transit network requesting the
            multicast destination. The reason that a hop count is
            associated with each downstream interface/neighbor is so
            that IP multicast's expanding ring search procedure can be
            more efficiently implemented. By expanding ring search is
            meant the following. Hosts can restrict the frowarding
            extent of the IP multicast datagrams that they send by
            appropriate setting of the TTL value in the datagram's IP
            header.  Then, for example, to search for the nearest server
            the host can send multicasts first with TTL set to 1, then
            2, etc. By attaching a hop count to each downstream
            interface/neighbor in the forwarding cache, datagrams will
            not be forwarded unless they will ultimately reach a



Moy                                                            [Page 16]

RFC 1584              Multicast Extensions to OSPF            March 1994


            multicast destination before their TTL expires[8].  This
            avoids wasting network bandwidth during an expanding ring
            search.

            As an example consider Router RT10's forwarding cache in
            Figure 3.  Router RT10's cache entry has two downstream
            interfaces. The first, connecting to Network N6, is labelled
            as having a group member one hop away (Network N6). The
            second, which connects to Network N8, is labelled as having
            a group member two hops away (Router RT9).

            Both the datagram shortest path tree and the local group
            database may contribute downstream interfaces to the
            forwarding cache entries. As an example, if a router has a
            local group database entry of [Group G, NX], then a
            forwarding cache entry for Group G, regardless of
            destination, will list the router interface to Network NX as
            a downstream interface. Such a downstream interface will
            always be labelled with a TTL of 1.

            As an example of forwarding cache entries, again consider
            the Autonomous System pictured in Figure 1. Suppose Host H2
            sends a multicast datagram to multicast group A. In that
            case, some routers will not even attempt to build a
            forwarding cache entry (e.g, router RT5) because they will
            never receive the multicast datagram in the first place.
            Other routers will receive the multicast datagram (since
            they are forwarded as link-level multicasts), but after
            building the pruned shortest path tree will notice that they
            themselves are not a part of the tree (routers RT1, RT4,
            RT7, RT8 and RT12). These latter routers will install an
            empty cache entry, indicating that they do not participate
            in the forwarding of the multicast datagram. A sample of the
            forwarding cache entries built by the other routers in the
            Autonomous System is pictured in Table 2.

            A MOSPF router must clear its entire forwarding cache when
            the Autonomous System's topology changes, because all the
            datagram shortest-path trees must be rebuilt. Likewise, when
            the location of a multicast group's membership changes
            (reflected by a change in group-membership-LSAs), all cache
            entries associated with the particular multicast destination
            group must be cleared. Other than these two cases,
            forwarding cache entries need not ever be deleted or
            otherwise modified; in particular, the forwarding cache
            entries do not have to be aged. However, forwarding cache
            entries can be freely deleted after some period of
            inactivity (i.e., garbage collected), if router memory



Moy                                                            [Page 17]

RFC 1584              Multicast Extensions to OSPF            March 1994




              Router   Upstream     Downstream interfaces
                       node         (interface:hops)
              ___________________________________________
              RT10     Router RT6   (N6:1), (N8:2)
              RT11     Net N8       (N9:1)
              RT3      Net N4       (N3:1), (RT6:3)
              RT6      Router RT3   (RT10:2)
              RT2      Net N3       (N2:1)


               Table 2: Sample forwarding cache entries,
                 for source N4 and destination Group A.

            resources are in short supply.

3.  Inter-area multicasting

    Up to this point this memo has discussed multicast forwarding when
    the entire Autonomous System is a single OSPF area. The logic for
    when the multicast datagram's source and its destination group
    members belong to the same OSPF area is the same. This section
    explains the behavior of the MOSPF protocol when the datagram's
    source and (at least some of) its destination group members belong
    to different OSPF areas. This situation is called inter-area
    multicast.

    Inter-area multicast brings up the following issues, which are
    resolved in succeeding sections:

    o   Are the group-membership-LSAs specific to a single area? And if
        they are, how is group membership information conveyed from one
        area to the next?

    o   How are the datagram shortest-path trees built in the inter-area
        case, since complete information concerning the topology of the
        datagram source's neighborhood is not available to routers in
        other areas?

    o   In an area border router, multiple datagram shortest-path trees
        are built, one for each attached area. How are these separate
        datagram shortest-path trees combined into a single forwarding
        cache entry?

    It should be noted in the following that the basic protocol
    mechanisms in the inter-area case are the same as for the intra-area
    case.  Forwarding of multicasts is still defined by the contents of



Moy                                                            [Page 18]

RFC 1584              Multicast Extensions to OSPF            March 1994


    the forwarding cache. The forwarding cache is still built from the
    same two components: the local group database and the datagram
    shortest-path trees. And while the calculation of the datagram
    shortest-path trees is different in the inter-area case (see Section
    3.2), the local group database is built exactly the same as in the
    intra-area case (i.e., MOSPF's interface with IGMP remains unchanged
    in the presence of areas). Finally, the forwarding algorithm
    described in Section 11 is the same for both the intra-area and
    inter-area cases.

    The following discussion uses the area configuration pictured in
    Figure 4 as an example. This figure, taken from the OSPF
    specification, shows an Autonomous System split into three areas
    (Area 1, Area 2 and Area 3). A single backbone area has been
    configured (everything outside of the shading). Since the backbone
    area must be contiguous, a single virtual link has been configured
    between the area border routers RT10 and RT11. Additionally, an area
    address range has been configured in Router RT11 so that Networks
    N9-N11 and Host H1 will be reported as a single route outside of
    Area 3 (via summary-link-LSAs).

    3.1.  Extent of group-membership-LSAs

        Group-membership-LSAs are specific to a single OSPF area. This
        means that, just as with OSPF router-LSAs, network-LSAs and
        summary-link-LSAs, a group-membership-LSA is flooded throughout
        a single area only[9].  A router attached to multiple areas
        (i.e., an area border router) may end up originating several
        group-membership-LSAs concerning a single multicast destination,
        one for each attached area.  However, as we will see below, the
        contents of these group-membership-LSAs will vary depending on
        their associated areas.

        Just as in OSPF, each MOSPF area has its own link state
        database. The MOSPF database is simply the OSPF link state
        database enhanced by the group-membership-LSAs. Consider again
        the area configuration pictured in Figure 4. The result of
        adding the group-membership-LSAs to the area databases yields
        the databases pictured in Figures 6 and 7.  Figure 6 shows Area
        1's MOSPF database. Figure 7 shows the backbone's MOSPF
        database. Superscripts indicate which transit vertices have been
        advertised as requesting particular multicast destinations. A
        superscript of "w" indicates that the router is advertising
        itself as a wild-card multicast receiver (see below). The dashed
        lines are OSPF summary-link-LSAs or AS external-link-LSAs. Note
        in Figure 7 that Router RT11 has condensed its routes to
        Networks N9-N11 and Host H1 into a single summary-link-LSA.




Moy                                                            [Page 19]

RFC 1584              Multicast Extensions to OSPF            March 1994



           ..................................
           .     +                          .
           .     | 3+---+    +--+  +--+     . N12      N14
           .   N1|--|RT1|\1  |Mb|  |H4|     .   \ N13 /
           .    _|  +---+ \  +--+ /+--+     .   8\ |8/8
           .   | +         \ _|__/          .     \|/
           . +--+   +--+    /    \   1+---+8.   8+---+6
           . |Mb|   |Mb|   *  N3  *---|RT4|------|RT5|--------+
           . +--+  /+--+    \____/    +---+ .    +---+        |
           .      +         /   |           .      |7         |
           .      | 3+---+ /    |           .      |          |
           .    N2|--|RT2|/1    |1          .      |6         |
           .    __|  +---+    +---+8        .   6+---+        |
           .   |  +           |RT3|--------------|RT6|        |
           . +--+    +--+     +---+     +--+.    +---+        |
           . |Ma|    |H3|_      |2     _|H2|.    Ia|7         |
           . +--+    +--+ \     |     / +--+.      |          |
           .               +---------+      .      |          |
           .Area 1             N4           .      |          |
           ..................................      |          |
           ................................        |          |
           .           N11                .        |          |
           .       +---------+            .        |          |
           .            |     \           .        |          |    N12
           .            |3     +--+       .        |          |6 2/
           .          +---+    |Ma|       .        |        +---+/
           .          |RT9|    +--+       .        |        |RT7|---N15
           .          +---+               .......  |        +---+ 9
           .            |1                .. +  ...|..........|1........
           .           _|__               .. |   Ib|5       __|_   +--+.
           .          /    \      1+----+2.. |  3+----+1   /    \--|Ma|.
           .         *  N9  *------|RT11|----|---|RT10|---*  N6  * +--+.
           .          \____/       +----+ .. |   +----+    \____/      .
           .            |            !*******|*****!          |        .
           .            |1           Virtual + Link           |1       .
           . +--+   10+----+              ..N8              +---+      .
           . |H1|-----|RT12|              ..                |RT8|      .
           . +--+SLIP +----+              ..                +---+  +--+.
           .            |2                ..                  |4  _|H5|.
           .            |                 ..                  |  / +--+.
           .       +---------+            ..              +--------+   .
           .           N10          Area 3..Area 2            N7       .
           .............................................................

                    Figure 4: A sample MOSPF area configuration





Moy                                                            [Page 20]

RFC 1584              Multicast Extensions to OSPF            March 1994


        Suppose an OSPF router has a local group database entry for
        [Group Y, Network X]. The router then originates a group-
        membership-LSA for Group Y into the area containing Network X.
        For example, in the area configuration pictured in Figure 4,
        Router RT1 originates a group-membership-LSA for Group B. This
        group-membership-LSA is flooded throughout Area 1, and no
        further. Likewise, assuming that Router RT3 has been elected
        Designated Router for Network N3, RT3 originates a group-
        membership-LSA into Area 1 listing the transit Network N3 as
        having group members. Note that in the link state database for
        Area 1 (Figure 6) both Router RT1 and Network N3 have
        accordingly been labelled with Group B.

        In OSPF, the area border routers forward routing information and
        data traffic between areas. In MOSPF. a subset of the area
        border routers, called the inter-area multicast forwarders,
        forward group membership information and multicast datagrams
        between areas. Whether a given OSPF area border router is also a
        MOSPF inter-area multicast forwarder is configuration dependent
        (see Section B.1). In Figure 4 we assume that all area border
        routers are also inter-area multicast forwarders.

        In order to convey group membership information between areas,
        inter-area multicast forwarders "summarize" their attached
        areas' group membership to the backbone. This is very similar
        functionality to the summary-link-LSAs that are generated in the
        base OSPF protocol.  An inter-area multicast forwarder
        calculates which groups have members in its attached non-
        backbone areas. Then, for each of these groups, the inter-area
        multicast forwarder injects a group-membership-LSA into the
        backbone area. For example, in Figure 4 there are two groups
        having members in Area 1: Group A and Group B. For that reason,
        both of Area 1's inter-area multicast forwarders (Routers RT3
        and RT4) inject group-membership-LSAs for these two groups into
        the backbone.  As a result both of these routers are labelled

                membership    +------------------+   datagrams
                    + > > > >>|     Backbone     |< < < < +
                    ^         +------------------+        ^
                    ^        /         |          \       ^
                    ^       /          |           \      ^
               +----^-----+/      +----------+      \+----^-----+
               |  Area 1  |       |  Area 2  |       |  Area 3  |
               +----------+       +----------+       +----------+

                    Figure 5: Inter-area routing architecture





Moy                                                            [Page 21]

RFC 1584              Multicast Extensions to OSPF            March 1994


        with Groups A and B in the backbone link state database (see
        Figure 7).

        However, unlike the summarization of unicast destinations in the
        base OSPF protocol, the summarization of group membership in
        MOSPF is asymmetric. While a non-backbone area's group
        membership is summarized to the backbone, this information is
        not then readvertised into other non-backbone areas. Nor is the
        backbone's group membership summarized for the non-backbone
        areas. Going back to the example in Figure 4, while the presence
        of Area 3's group (Group A) is advertised to the backbone, this
        information is not then redistributed to Area 1. In other words,
        routers internal to Area 1 have no idea of Area 3's group
        membership.

        At this point, if no extra functionality was added to MOSPF,
        multicast traffic originating in Area 1 destined for Multicast
        Group A would never be forwarded to those Group A members in
        Area 3. To accomplish this, the notion of wild-card multicast
        receivers is introduced. A wild-card multicast receiver is a
        router to which all multicast traffic, regardless of multicast
        destination, should be forwarded. A router's wild-card multicast
        reception status is per-area. In non-backbone areas, all inter-
        area multicast forwarders[10] are wild-card multicast receivers.
        This ensures that all multicast traffic originating in a non-
        backbone area will be forwarded to its inter-area multicast
        forwarders, and hence to the backbone area. Since the backbone
        has complete knowledge of all areas' group membership, the
        datagram can then be forwarded to all group members. Note that
        in the backbone itself there is no need for wild-card multicast
        receivers[11].  As an example, note that Routers RT3 and RT4 are
        wild-card multicast receivers in Area 1 (see Figure 6), while
        there are none in the backbone (see Figure 7).

        This yields the inter-area routing architecture pictured in
        Figure 5.  All group membership is advertised by the non-
        backbone areas into the backbone. Likewise, all IP multicast
        traffic arising in the non-backbone areas is forwarded to the
        backbone. Since at this point group membership information meets
        the multicast datagram traffic, delivery of the multicast
        datagrams becomes possible.

    3.2.  Building inter-area datagram shortest-path trees

        When building datagram shortest-path trees in the presence of
        areas, it is often the case that the source of the datagram and
        (at least some of) the destination group members are in separate
        areas. Since detailed topological information concerning one



Moy                                                            [Page 22]

RFC 1584              Multicast Extensions to OSPF            March 1994



                                  **FROM**

                             |RT|RT|RT|RT|RT|RT|
                             |1 |2 |3 |4 |5 |7 |N3|
                          ----- -------------------
                          RT1|  |  |  |  |  |  |0 |
                          RT2|  |  |  |  |  |  |0 |
                          RT3|  |  |  |  |  |  |0 |
                      *   RT4|  |  |  |  |  |  |0 |
                      *   RT5|  |  |14|8 |  |  |  |
                      T   RT7|  |  |20|14|  |  |  |
                      O    N1|3 |  |  |  |  |  |  |
                      *    N2|  |3 |  |  |  |  |  |
                      *    N3|1 |1 |1 |1 |  |  |  |
                           N4|  |  |2 |  |  |  |  |
                        Ia,Ib|  |  |15|22|  |  |  |
                           N6|  |  |16|15|  |  |  |
                           N7|  |  |20|19|  |  |  |
                           N8|  |  |18|18|  |  |  |
                    N9-N11,H1|  |  |19|16|  |  |  |
                          N12|  |  |  |  |8 |2 |  |
                          N13|  |  |  |  |8 |  |  |
                          N14|  |  |  |  |8 |  |  |
                          N15|  |  |  |  |  |9 |  |


                     Figure 6: Area 1's MOSPF database.

             Networks and routers are represented by vertices.
             An edge of cost X connects Vertex A to Vertex B iff
             the intersection of Column A and Row B is marked
             with an X. In addition, RT1, RT2 and N3 are labelled
             with multicast group A, RT1 is labelled with multicast
             group B, and both RT3 and RT4 are labelled as
             wild-card multicast receivers.















Moy                                                            [Page 23]

RFC 1584              Multicast Extensions to OSPF            March 1994


                                 **FROM**

                           |RT|RT|RT|RT|RT|RT|RT
                           |3 |4 |5 |6 |7 |10|11|
                        ------------------------
                        RT3|  |  |  |6 |  |  |  |
                        RT4|  |  |8 |  |  |  |  |
                        RT5|  |8 |  |6 |6 |  |  |
                        RT6|8 |  |7 |  |  |5 |  |
                        RT7|  |  |6 |  |  |  |  |
                    *  RT10|  |  |  |7 |  |  |2 |
                    *  RT11|  |  |  |  |  |3 |  |
                    T    N1|4 |4 |  |  |  |  |  |
                    O    N2|4 |4 |  |  |  |  |  |
                    *    N3|1 |1 |  |  |  |  |  |
                    *    N4|2 |3 |  |  |  |  |  |
                         Ia|  |  |  |  |  |5 |  |
                         Ib|  |  |  |7 |  |  |  |
                         N6|  |  |  |  |1 |1 |3 |
                         N7|  |  |  |  |5 |5 |7 |
                         N8|  |  |  |  |4 |3 |2 |
                  N9-N11,H1|  |  |  |  |  |  |1 |
                        N12|  |  |8 |  |2 |  |  |
                        N13|  |  |8 |  |  |  |  |
                        N14|  |  |8 |  |  |  |  |
                        N15|  |  |  |  |9 |  |  |


                 Figure 7: The backbone's MOSPF database.

             Networks and routers are represented by vertices.
             An edge of cost X connects Vertex A to Vertex B iff
             the intersection of Column A and Row B is marked
             with an X. In addition, RT3 and RT4 are labelled
             with both multicast groups A and B, and RT7, RT10,
             and RT11 are labelled with multicast group A.

        OSPF area is not distributed to other OSPF areas (the flooding
        of router-LSAs, network-LSAs and group-membership-LSAs is
        restricted to a single OSPF area only), the building of complete
        datagram shortest-path trees is often impossible in the inter-
        area case. To compensate, approximations are made through the
        use of wild-card multicast receivers and OSPF summary-link-LSAs.

        When it first receives a datagram for a particular [source net,
        destination group] pair, a router calculates a separate datagram
        shortest-path tree for each of the router's attached areas. Each
        datagram shortest-path tree is built solely from LSAs belonging



Moy                                                            [Page 24]

RFC 1584              Multicast Extensions to OSPF            March 1994


        to the particular area's link state database. Suppose that a
        router is calculating a datagram shortest-path tree for Area A.
        It is useful then to separate out two cases.

        The first case, Case 1: The source of the datagram belongs to
        Area A has already been described in Section 2.3.2. However, in
        the presence of OSPF areas, during tree pruning care must be
        taken so that the branches leading to other areas remain, since
        it is unknown whether there are group members in these (remote)
        areas. For this reason, only those branches having no group
        members nor wild-card multicast receivers are pruned when
        producing the datagram shortest-path tree.

        As an example, suppose in Figure 4 that Host H2 sends a
        multicast datagram to destination Group A. Then the datagram's
        shortest-path tree for Area 1, built identically by all routers
        in Area 1 that receive the datagram, is shown in Figure 8. Note
        that both inter-area multicast forwarders (RT3 and RT4) are on
        the datagram's shortest-path tree, ensuring the delivery of the
        datagram to the backbone and from there to Areas 2 and 3.

        o   Case 2: The source of the datagram belongs to an area other
            than Area A. In this case, when building the datagram
            shortest-path tree for Area A, the immediate neighborhood of
            the datagram's source is unknown. However, there are
            summary-link-LSAs in the Area A link state database
            indicating the cost of the paths between each of Area A's
            inter-area multicast forwarders and the datagram source.
            These summary links are used to approximate the neighborhood
            of the datagram's source; the tree begins with links
            directly connecting the source to each of the inter-area
            multicast forwarders. These links point in the reverse

                                      o RT3 (W, origin=N4)
                                      |
                                     1|
                                      |
                              N3 (Mb) o
                                     / \
                                   0/   \0
                                   /     \
                      RT2 (Ma,Mb) o       o RT4 (W)


                    Figure 8: Datagram's shortest-path tree,
                      Area 1, source N4, destination Group A





Moy                                                            [Page 25]

RFC 1584              Multicast Extensions to OSPF            March 1994


            direction (towards instead of away from the datagram source)
            from the links considered in Case 1 above. All additional
            links added to the tree also point in the reverse direction.
            The final datagram shortest-path tree is then produced by,
            as before, pruning all branches having no group-members nor
            wild-card multicast receivers.

            As an example, suppose again that Host H2 in Figure 4 sends
            a multicast datagram to destination Group A. The datagram's
            shortest-path tree for the backbone is shown in Figure 9.
            The neighborhood around the source (Network N4) has been
            approximated by the summary links advertised by routers RT3
            and RT4. Note that all links in Figure 9's datagram
            shortest-path tree have arrows pointing in the reverse
            direction, towards Network N4 instead of away from it.

        The reverse costs used for the entire tree in Case 2 are forced
        because summary-link-LSAs only specify the cost towards the
        datagram source. In the presence of asymmetric link costs, this
        may lead to less efficient routes when forwarding multicasts

                                     o N4
                                    / \
                                  2/   \3
                                  /     \
                     RT3 (Ma,Mb) o       o RT4 (Ma,Mb)
                                /         \
                              6/           \8
                              /             \
                         RT6 o               o RT5
                             |               |
                            5|               |6
                             |               |
                   RT10 (Ma) o               o RT7 (Ma)
                             |
                            2|
                             |
                   RT11 (Ma) o



               Figure 9: Datagram shortest-path tree: Backbone,
                  source N4, destination Group A. Note that
                  reverse costs (i.e., toward origin) are
                             used throughout.






Moy                                                            [Page 26]

RFC 1584              Multicast Extensions to OSPF            March 1994


        between areas.

        Those routers attached to multiple areas must calculate multiple
        trees and then merge them into a single forwarding cache entry.
        As shown in Section 2.3.2, when connected to a single area the
        router's position on the datagram shortest-path tree determines
        (in large part) its forwarding cache entry. When attached to
        multiple areas, and hence calculating multiple datagram
        shortest-path trees, each tree contributes to the forwarding
        cache entry's list of downstream interfaces/neighbors. However,
        only one of the areas' datagram shortest-path trees will
        determine the forwarding cache entry's upstream node. When one
        of the attached areas contains the datagram source, that area
        will determine the upstream node. Otherwise, the tiebreaking
        rules of Section 12.2.7 are invoked.

        Consider again the example of Host H2 in Figure 4 sending a
        multicast datagram to destination Group A. Router RT3 will
        calculate two datagram shortest-path trees, one for Area 1 and
        one for the backbone.  Since the source of the datagram (Host
        H2) belongs to Area 1, the Area 1 datagram shortest-path tree
        determines RT3's upstream node: Network N4. Router RT3
        calculates two downstream interfaces for the datagram: the
        interface to Network N3 (which comes from Area 1's datagram
        shortest-path tree) and the serial line to Router RT6 (which
        comes from the backbone's datagram shortest-path tree). As for
        Router RT10, it calculates two trees, determining its upstream
        node from the backbone tree and its two downstream interfaces
        from the Area 2 tree.  Finally, Router RT11 calculates three
        trees, determining its upstream node from the Area 2 tree and
        its downstream interface from the Area 3 tree.

4.  Inter-AS multicasting

    This section explains how MOSPF deals with the forwarding of
    multicast datagrams between Autonomous Systems. Certain AS boundary
    routers in a MOSPF system will be configured as inter-AS multicast
    forwarders. It is assumed that these routers will also be running an
    inter-AS multicast routing protocol. This specification does not
    dictate the operation of such an inter-AS multicast routing
    protocol. However, the following interactions between MOSPF and the
    inter-AS routing protocol are assumed:

    (1) MOSPF guarantees that the inter-AS multicast forwarders will
        receive all multicast datagrams; but it is up to each router so
        designated to determine whether the datagram should be forwarded
        to other Autonomous Systems. This determination will probably be
        made via the inter-AS routing protocol.



Moy                                                            [Page 27]

RFC 1584              Multicast Extensions to OSPF            March 1994


    (2) MOSPF assumes that the inter-AS routing protocol is forwarding
        multicast datagrams in an RPF (reverse path forwarding; see
        [Deering] for an explanation of this terminology) fashion. In
        other words, it is assumed that a multicast datagram whose
        source (call it X) lies outside the MOSPF domain will enter the
        MOSPF domain at those points that are advertising (into OSPF)
        the best routes back to X. MOSPF calculates the path of the
        datagram through the MOSPF domain based on this assumption.

    MOSPF designates an inter-AS multicast forwarder as a wild-card
    multicast receiver in all of its attached areas. As in the inter-
    area case, this ensures that the routers remain on all pruned
    shortest-path trees and thereby receive all multicast datagrams,
    regardless of destination.

    As an example, suppose that in Figure 1 both RT5 and RT7 were
    configured as inter-AS multicast forwarders. Then the link state
    database would look like the one pictured in Figure 2, with the
    addition of a) wild-card status for RT5 and RT7 (they would appear
    with superscripts of "w") and b) the external links originated by
    RT5 and RT7 being labelled as multicast-capable[12].

    As another example, consider the area configuration in Figure 4.
    Again suppose RT5 and RT7 are configured as inter-AS multicast
    forwarders. Then in Area 1's link state database (Figure 6), the
    external links originated by RT5 and RT7 would again be labelled as
    multicast-capable. However, note that in Area 1's database RT5 and
    RT7 are not labelled as wild-card multicast receivers. This is
    unnecessary; since Area 1's inter-area multicast forwarders (RT3 and
    RT4) are wild-cards, all multicast datagrams will be forwarded to
    the backbone. And in the backbone's link state database (Figure 7),
    RT5 and RT7 will be labelled as wild-cards.

    4.1.  Building inter-AS datagram shortest-path trees.

        When multicast datagrams are to be forwarded between Autonomous
        Systems, the datagram shortest-path tree is built as follows.
        Remember that the router builds a separate tree for each area to
        which it is attached; these trees are then merged into a single
        forwarding cache entry. Suppose that the router is building the
        tree for Area A. We break up the tree building into three cases.
        This first two cases have already been described earlier in this
        memo: Case 1 (the source of the datagram belongs to Area A)
        having been described in Section 2.3.2 and Case 2 (the source of
        the datagram belongs to another OSPF area) having been described
        in Section 3.2. The only modification to these cases is that
        inter-AS multicast forwarders, as well as group members and
        inter-area multicast forwarders, must remain on the pruned



Moy                                                            [Page 28]

RFC 1584              Multicast Extensions to OSPF            March 1994


        trees.  The new case is as follows:

        o   Case 3: The source of the datagram belongs to another
            Autonomous System. The immediate neighborhood of the source
            is then unknown. In this case the multicast-capable AS
            external links are used to approximate the neighborhood of
            the source; the tree begins with links directly attaching
            the source to one or more inter-AS multicast forwarders. The
            approximating AS external links point in the reverse
            direction (i.e., towards the source), just as with the
            approximating summary links in Case 2. Also, as in Case 2,
            all links included in the tree must point in the reverse
            direction. The final datagram shortest-path tree is then
            produced (as always) by pruning those branches having no
            group members nor wild-card multicast receivers.

            As an example, suppose that a host on Network N12 (see
            Figure 4) originates a multicast datagram for Destination
            Group B. Assume that all external costs pictured are OSPF
            external type 1 metrics. Then any routers in Area 1
            receiving the datagram would build the datagram shortest-
            path tree pictured in Figure 10. Note that all links in the
            tree point in the reverse direction, towards the source. The
            tree indicates that the routers expect the datagram to enter
            the Autonomous System at Router RT7, and then to enter the
            area at Router RT4.

            Note that in those cases where the "best" inter-AS multicast
            forwarder is not directly attached to the area, the
            neighborhood of the source is actually approximated by the
            concatenation of a summary link and a multicast-capable AS
            external link. This is in fact the case in Figure 10.

        In Case 3 (datagram source in another AS) the requirement that
        all tree links point in the reverse direction (towards the
        source) accommodates the fact that summary links and AS external
        links already point in the reverse direction. This also leads to
        the requirement that the inter-AS multicast routing protocol
        operate in a reverse path forwarding fashion (see condition 2 of
        Section 4). Note that Reverse path forwarding can lead to sub-
        optimal routing when costs are configured asymmetrically. And it
        can even lead to non-delivery of multicast datagrams in the case
        of asymmetric reachability.

        Inter-AS multicast forwarders may end up calculating a
        forwarding cache entry's upstream node as being external to the
        AS. As an example, Router RT7 in Figure 10 will end up
        calculating an external router (via its external link to Network



Moy                                                            [Page 29]

RFC 1584              Multicast Extensions to OSPF            March 1994



                                     o N12
                                     |
                                    2|
                                     |
                                     o RT7
                                     |
                                   14|
                                     |
                                     o RT4 (W)
                                     |
                                    0|
                                     |
                                     o N3 (Mb)
                                    /|\
                                   / | \
                                 1/  | 1\
                                 /  1|   \
                                /    |    \
                      RT1 (Mb) o     |     o RT3 (W)
                                     o
                                RT2 (Ma,Mb)


               Figure 10: Datagram shortest-path tree: Area 1,
                 source N12, destination Group B. Note that
                  reverse costs (i.e., toward origin) are
                             used throughout.

        N12) as the upstream node for the datagram. This means that RT7
        must receive the datagram from a router in another AS before
        injecting the datagram into the MOSPF system.

    4.2.  Stub area behavior

        AS external links are not imported into stub areas. Suppose that
        the source of a particular datagram lies outside of the
        Autonomous System, and that the datagram is forwarded into a
        stub area. In the stub area's datagram shortest-path tree the
        neighborhood of the datagram's source cannot be approximated by
        AS external links. Instead the neighborhood of the source is
        approximated by the default summary links (see Section 3.6 of
        [OSPF]) that are originated by the stub area's intra-area
        multicast forwarders.

        Except for this small change to the construction of a stub
        area's datagram shortest-path trees, all other MOSPF algorithms
        (e.g., merging with other areas' datagram shortest-path trees to



Moy                                                            [Page 30]

RFC 1584              Multicast Extensions to OSPF            March 1994


        form the forwarding cache) function the same for stub areas as
        they do for non-stub areas.

    4.3.  Inter-AS multicasting in a core Autonomous System

        It may be the case that the MOSPF routing domain connects
        together many different Autonomous Systems, thereby serving as a
        "core Autonomous System" (e.g, the old NSFNet backbone). In this
        case, it could very well be that the majority of the MOSPF
        routers are also inter-AS multicast forwarders. Having each
        inter-AS multicast forwarder then declare itself a wild-card
        multicast receiver could very well waste considerable network
        bandwidth. However, as an alternative to declaring themselves
        wild-card multicast receivers, the inter-AS multicast routers
        could instead explicitly advertise all groups that they were
        interested in forwarding (to other "client" Autonomous Systems)
        in group-membership-LSAs. These advertised groups would have to
        be learned through an inter-AS multicast routing protocol (or
        possibly even statically configured).

        This in essence allows the clients of the core Autonomous System
        to advertise their group membership into the core. However,
        since any client MOSPF domains will still have their inter-AS
        multicast forwarders configured as wild-card multicast
        receivers, this advertisement will be asymmetric: the core will
        not advertise its or others' group membership to the clients.
        The achieves the same inter-AS multicast routing architecture
        that MOSPF uses for inter-area multicast routing (see Figure 5).

5.  Modelling internal group membership

    A MOSPF router may itself contain multicast applications. A typical
    example of this is a UNIX workstation that doubles as a multicast
    router. This section concerns two alternative ways of representing
    the group membership of the MOSPF router's internal applications.
    Both representations have advantages. For maximum flexibility, the
    MOSPF forwarding algorithm (see Section 11) has been specified so
    that either representation can be used in a MOSPF router (and in
    fact, both representations can be used at once, depending on the
    application).

    The first representation is based on the paradigm presented in RFC
    1112. In this case, an application joins a multicast group on one or
    more specific physical interfaces. The application then receives a
    multicast datagram if and only if it is received on one of the
    specified interfaces. If a datagram is received on multiple
    specified interfaces, the application receives multiple copies.
    Figure 11 shows this algorithm as it is implemented in (modified)



Moy                                                            [Page 31]

RFC 1584              Multicast Extensions to OSPF            March 1994


    BSD UNIX kernels.  The figure shows the processing of a multicast
    datagram, starting with its reception on a particular interface.
    First copies of the datagram are given to those applications that
    have joined on the receiving interface. Then the forwarding decision
    (pictured as a box containing a question mark) is made, and the
    packet is (possibly) forwarded out certain interfaces. If these
    interfaces are not capable of receiving their own multicasts, a copy
    of the datagram must be internally looped back to appropriately
    joined applications.

    The advantages to the RFC 1112 representation are as follows:

    o   It is the standard for the way an IP host joins multicast
        groups. It is simplest to use the same membership model for
        hosts and routers; most would consider an IP router to be a
        special case of an IP host anyway.

    o   It is the way group membership has been implemented in BSD UNIX.
        Existing multicast applications are written to join multicast
        groups on specific interfaces.

    o   The possibility of receiving multiple datagram copies may
        improve fault tolerance. If the datagram is dropped due to an

                            +-------+
                            |receive|
                            +-------+
                                |
                                |---> To application
                                |
                      +-------------------+
                      |forwarding decision|
                      +-------------------+
                                |
                               / \
                              /---\----> To application
                             /     \------> To application
                            /       \
                           /         \
                     +--------+  +--------+
                     |transmit|  |transmit|
                     +--------+  +--------+


              Figure 11: RFC 1112 representation of internal
                          group membership





Moy                                                            [Page 32]

RFC 1584              Multicast Extensions to OSPF            March 1994


        error on the path to some interface, another interface may still
        receive a copy.

    o   The ability to specify a particular receiving interface may
        improve the accuracy of IP multicast's expanding ring search
        mechanism (see Section 2.3.4).

    o   Membership in the non-routable multicast groups (224.0.0.1 -
        224.0.0.255) must be on a per-interface basis. An OSPF router
        always belongs to 224.0.0.5 (AllSPFRouters) on its OSPF
        interfaces, and may belong to 224.0.0.6 (AllDRouters) on one or
        more of its OSPF interfaces.

    The second representation is MOSPF-specific. In this case, an
    application joins a multicast group on an interface-independent
    basis.  In other words, group membership is associated with the
    router as a whole, not separately on each interface. The application
    then receives a copy of a multicast datagram if and only if the
    datagram would actually be forwarded by the MOSPF router. Figure 12
    shows how this algorithm would be implemented. The datagram is
    received on a particular interface. If the datagram is validated for
    forwarding (i.e., the receiving interface connects to the matching
    forwarding cache entry's upstream node), a copy of the datagram is
    also given to appropriately joined applications. Note that this
    model of group membership is not as general as the RFC 1112 model,
    in that it can only be implemented in MOSPF routers and not in
    arbitrary IP hosts.  However, it has the following advantages:

    o   The application does not need to have knowledge of the router
        interfaces. It does not need to know what kind or how many
        interfaces there are; this will be taken care of by the MOSPF
        protocol itself.

    o   As long as any interface is operational, the application will
        continue to receive multicast datagrams. This happens
        automatically, without the application modifying its group
        membership.

    o   The application receives only one copy of the datagram. Using
        the RFC1112 representation, whenever an application joins on
        more than one interface (which must be done if the application
        does not want to rely on a single interface), multiple datagram
        copies will be received during normal operation.

6.  Additional capabilities

    This section describes the MOSPF configuration options that allow
    routers of differing capabilities to be mixed together in the same



Moy                                                            [Page 33]

RFC 1584              Multicast Extensions to OSPF            March 1994



                            +-------+
                            |receive|
                            +-------+
                                |
                                |
                                |
                      +-------------------+
                      |forwarding decision|---> to application
                      +-------------------+
                                |
                               / \
                              /   \
                             /     \
                            /       \
                           /         \
                     +--------+  +--------+
                     |transmit|  |transmit|
                     +--------+  +--------+


              Figure 12: MOSPF-specific representation of internal
                             group membership

    routing domain. Note that these options handle special circumstances
    that may not be encountered in normal operation. Default values for
    the configuration settings are specified in Appendix B.

    6.1.  Mixing with non-multicast routers

        MOSPF routers can be mixed freely with routers that are running
        only the base OSPF algorithm (called non-multicast routers in
        the following). This allows MOSPF to be deployed in a piecemeal
        fashion, thereby speeding deployment and allowing
        experimentation with multicast routing on a limited scale.

        When a MOSPF router builds a datagram shortest-path tree, it
        omits all non-multicast routers. For example, in Figure 1, if
        Router RT6 was not a multicast router, the datagram shortest-
        path tree in Figure 3 would be built with a more circuitous
        branch through Router RT5, instead of through Router RT6. In
        addition, non-multicast routers do not participate in the
        flooding of the new group-membership-LSAs. This adheres to the
        general principle that a router should not have to handle those
        link state advertisements whose format (or contents) the router
        does not understand.





Moy                                                            [Page 34]

RFC 1584              Multicast Extensions to OSPF            March 1994


        Mixing MOSPF routers with non-multicast routers creates a number
        of potential problems. Certain mixings of MOSPF and non-
        multicast routers can cause multicast datagrams to take
        suboptimal paths, or in other cases can lead to the non-delivery
        of multicast datagrams. In addition, mixing MOSPF routers and
        non-multicast routers can cause the paths of multicast datagrams
        to diverge radically from the path of unicast datagrams. Such
        divergences can make routing problems harder to debug.

        In particular, the following specific difficulties may arise
        when mixing MOSPF routers with non-multicast routers:

        o   Even though there is unicast connectivity to a destination,
            there may not be multicast connectivity. For example, if
            Router RT10 in Figure 1 becomes a non-multicast router, the
            group member connected to Network N11 will no longer be able
            to receive multicasts sourced by Host H2.  But the two hosts
            will be able to exchange unicasts (e.g., ICMP pings).

        o   When the Designated Router for a multi-access network is a
            non-multicast router, the network will not be used for
            forwarding multicast datagrams. For example, if in Figure 1
            Router RT4 is Designated Router for Network N3, and RT4 is
            non-multicast, Network N3 will not be used to forward IP
            multicasts. This would mean that multicast datagrams
            originated by Hosts H2 and H3 would not be forwarded beyond
            their local network (N4), even though it seems that the
            needed multicast connectivity exists.

        o   When forwarding multicast datagrams between areas, mixing of
            MOSPF routers and non-multicast routers in the source area
            may cause unexpected loss of multicast connectivity. This is
            because in the inter-area routing of multicast datagrams the
            neighborhood of the datagram's source is approximated by
            OSPF summary links, and OSPF summary-link-LSAs do not carry
            indications/guarantees of the summarized path's multicast
            routing capability.

    6.2.  TOS-based multicast

        MOSPF allows a separate datagram shortest-path tree to be built
        for each IP Type of Service. This means that the path of a
        multicast datagram can vary depending on the datagram's TOS
        classification, as well as its source and destination.

        For each router interface, OSPF allows a separate metric to be
        configured for each IP TOS. When building the shortest path tree
        for TOS X, the cost of a path is the sum of the component



Moy                                                            [Page 35]

RFC 1584              Multicast Extensions to OSPF            March 1994


        interfaces' TOS X metrics. Note that OSPF requires that a TOS 0
        metric be specified for each interface. However, as a form of
        data compression, metrics need only be specified for non-zero
        TOS if they are different than the TOS 0 metric.

        Additionally, OSPF routers can be configured to ignore TOS when
        forwarding packets. Such routers, called TOS-incapable, build
        only the TOS 0 portion of the routing table. TOS-incapable
        routers can be mixed freely with TOS-capable routers when
        forwarding unicast packets. The way this is handled for unicast
        packets is that the unicast is forwarded along the TOS 0 route
        whenever the TOS X route does not exist. However, MOSPF must
        treat this situation somewhat differently, since each router
        must build the exact same tree rooted at the datagram's source.

        Like OSPF, MOSPF allows TOS-based routing to be optional. TOS-
        capable and TOS-incapable multicast routers can be mixed freely
        in the routing domain. TOS-incapable routers will only ever
        build TOS 0 datagram shortest-path trees. TOS-capable routers
        will first build TOS 0 datagram shortest-path trees. If these
        trees contain only TOS-capable routers, datagram shortest-path
        trees are then built separately for non-zero TOS values.
        Otherwise, the TOS 0 datagram shortest-path tree is used to
        forward all traffic, regardless of its TOS designation.  Using
        this logic, all routers in essence continue to utilize identical
        datagram shortest-path trees. See Section 12.2.8 for more
        details.

    6.3.  Assigning multiple IP networks to a physical network

        Assigning multiple IP networks/subnets to a single physical
        network causes some confusion in MOSPF. This is because the
        underlying OSPF protocol treats these IP networks/subnets as
        entirely separate entities, originating separate network-LSAs
        for each and forming separate adjacencies for each, while IGMP
        recognizes only the single underlying physical network. Adding
        to the problem is the fact that when a multicast datagram is
        received from such a multiply-addressed physical wire, there is
        no good way to choose the datagram's upstream node (which must
        be done in order to make the forwarding decision; see Section 11
        for details). As a result, unless this situation is dealt with
        through configuration, unwanted replication of multicast
        datagrams may occur when they are forwarded over multiply-
        addressed wires.

        As a remedy, MOSPF allows multicast forwarding to be disabled on
        certain IP networks/subnets. When multicast forwarding is
        disabled on the wire's "extra" subnets (i.e., all but one), the



Moy                                                            [Page 36]

RFC 1584              Multicast Extensions to OSPF            March 1994


        extra subnets will not appear in datagram shortest-path trees,
        nor will they appear in local group database or forwarding cache
        entries. As a result, the possibility of unwanted datagram
        replication is eliminated. The actual disabling of multicast
        forwarding on a subnet is done through setting the
        IPMulticastForwarding parameter to disabled on all router
        interfaces connecting to the subnet (see Section B.2).

    6.4.  Networks on Autonomous System boundaries

        Another complication can arise on IP networks/subnets that lie
        on the boundary of a MOSPF Autonomous System. Similar to the
        unicast situation where these networks may be running multiple
        IGPs (Interior Gateway Protocols), these networks may also be
        running multiple multicast routing protocols. It may then become
        impossible for a MOSPF router to determine whether a multicast
        datagram is being forwarded along the datagram shortest-path
        tree, or whether it has been inadvertently received from the
        other Autonomous System. Guessing wrong can lead to either
        unwanted replication or non-delivery of the multicast datagram.
        In addition, in order to prevent receiving duplicate multicast
        datagrams, group members on these boundary networks will
        probably want to declare their membership to one Autonomous
        System and not another.

        For example, consider the two Autonomous Systems pictured in
        Figure 13. Network X is on the boundary of both ASes. One
        possible multicast datagram path is shown; the datagram
        originates in a third Autonomous System, and is then delivered
        to both AS #1 and AS #2 separately. The paths through the two
        Autonomous Systems may end up having certain boundary networks
        as common segments. In Figure 13, Network X is common to both
        paths. In this case, if both Autonomous Systems were running
        (separate copies of) MOSPF, the same datagram would appear twice
        on Network X as a data-link multicast. This would cause
        duplicate datagrams to be received by any group members on
        Network X or downstream from Network X.

        MOSPF has two mechanisms to eliminate this replication of
        multicast datagrams. First, a system administrator can configure
        certain networks to forward multicast datagrams as data-link
        unicasts instead of data-link multicasts. This is done by
        setting the IPMulticastForwarding parameter to data-link unicast
        on those router interfaces attaching to the network (see Section
        B.2). As an example, in Figure 13 the routers in AS #2 could be
        configured so that Router C would send the multicast datagram
        out onto Network X as a data-link unicast addressed directly to
        Router D. Router D would accept this data-link unicast, but



Moy                                                            [Page 37]

RFC 1584              Multicast Extensions to OSPF            March 1994



                              <-Datagram path->*
                             *                 *
                             *                 *
                             *            .....*.........
                    .........*.....   |   .    *    AS #2
                    AS #1    *    .   |*****+---+
                            +---+*****|*----|RTC|
                            |RTA|----*|*  . +---+
                            +---+ .  *|*  .
                                  .  *|*  .
                                  .  *|*  . +---+
                            +---+ .  *|*----|RTD|
                            |RTB|----*|*****+---+
                            +---+*****|   .....*..........
                    .........*....    |        *
                             *        |        *
                             *    Network X    *
                             *

                     Figure 13: Networks on AS boundaries

        would reject any data-link multicast forwarded by Router A. This
        would eliminate replication of multicast datagrams downstream
        from Network X. In addition, if the IPMulticastForwarding
        parameter is set to data-link unicast on Network X, group
        membership will not be monitored on the network. This will
        prevent group members attached directly to Network X from
        receiving multiple datagram copies, since group membership on
        the boundary network will be monitored from only one AS (AS #1
        in our example).

        It should be noted that forwarding IP multicasts as data-link
        unicasts has some disadvantages when three or more MOSPF routers
        are attached to the network. First of all, it is more work for a
        router to send multiple unicasts than a single multicast.
        Second, the multiple unicasts consume more network bandwidth
        than a single multicast. And last, it increases the delay for
        some group members since multiple unicasts also take longer to
        send than a single multicast.

    6.5.   Recommended system configuration

        In order to make MOSPF's selection of routes more predictable,
        it is recommended that all routers in any particular OSPF area
        have the same multicast and TOS capabilities.Keeping areas
        homogeneous ensures that IP multicast packets will follow
        relatively the same path as IP unicasts. In contrast, while



Moy                                                            [Page 38]

RFC 1584              Multicast Extensions to OSPF            March 1994


        heterogeneous areas will function, and will probably be
        necessary at least during the initial introduction of multicast
        routing, such areas may produce seemingly sub-optimal and
        unexpected routes. For example, see Section 6.1 above for a
        detailed description of the possible pitfalls when mixing
        multicast and non-multicast routers.

        As for the other options presented above, to achieve the most
        predictable results it is recommended that a router interface's
        IPMulticastForwarding parameter be set to a value other than
        data-link multicast only when either a) multiple IP networks
        have been assigned to a single physical wire or b) multiple
        multicast routing protocols are running on the attached network.






































Moy                                                            [Page 39]

RFC 1584              Multicast Extensions to OSPF            March 1994


7.  Basic implementation requirements

    An implementation of MOSPF requires the following pieces of system
    support. Note that this support is in addition to that required for
    the base OSPF implementation as outlined in Section 4.4 of [OSPF].

    o   Promiscuous multicast reception. In a multicast router, it is
        necessary to receive all IP multicasts at the data-link level.
        On those interfaces where IP multicast datagrams are
        encapsulated by a wide range of data-link multicast destination
        addresses (e.g, ethernet and FDDI), this is most easily
        accomplished by disabling any hardware filtering of multicast
        destinations (i.e., by "opening up" the interface's multicast
        filter).

    o   Data-link multicast/broadcast detection. To avoid unwanted
        replication of multicast datagrams in certain exceptional
        conditions, it is necessary for the multicast router to
        determine whether a datagram was received as a data-link
        multicast/broadcast or as a data-link unicast, for later use by
        the MOSPF forwarding mechanism.  See Section 6.4 for more
        details.

    o   An implementation of IGMP. MOSPF uses the Internet Group
        Management Protocol (IGMP, documented in [RFC 1112]) to monitor
        multicast group membership. See Section 9 for details.

8.  Protocol data structures

    The MOSPF protocol is described herein in terms of its operation on
    various protocol data structures. These data structures are included
    for explanatory uses only, and are not intended to constrain a MOSPF
    implementation. Besides the data structures listed below, this
    specification will also reference the various data structures (e.g.,
    OSPF interfaces and neighbors) defined in [OSPF].

    In a MOSPF router, the following items are added to the list of
    global OSPF data structures described in Section 5 of [OSPF]:

    o   Local group database. This database describes the group
        membership on all attached networks for which the router is
        either Designated Router or Backup Designated Router. This in
        turn determines the group-membership-LSAs that the router will
        originate, and the local delivery of multicast datagrams (see
        Sections 2.3.1 and 10).

    o   Forwarding cache. Each entry in the forwarding cache describes
        the path of a multicast datagram having a particular [source



Moy                                                            [Page 40]

RFC 1584              Multicast Extensions to OSPF            March 1994


        net, multicast destination, TOS] combination. These cache
        entries are calculated when building the datagram shortest-path
        trees. See Sections 2.3.4 and 11 for more details.

    o   Multicast routing capability. Indicates whether the router is
        running the multicast extensions defined in this memo. A router
        running the multicast extensions must still run the base OSPF
        algorithm as set forth in [OSPF]. Such a router will continue to
        interoperate with non-multicast-capable OSPF routers when
        forwarding IP unicast traffic.

    o   Inter-area multicast forwarder. Indicates whether the router
        will forward IP multicasts from one OSPF area to another. Such a
        router declares itself a wild-card multicast receiver in its
        non-backbone area router-LSAs (see Section 14.6), and also
        summarizes its attached areas' group membership to the backbone
        in group-membership-LSAs. When building inter-area datagram
        shortest-path trees, it is these routers that appear immediately
        adjacent to the datagram source at the root of the tree (see
        Section 3.2). Not all multicast-capable area border routers need
        be configured as inter-area multicast forwarders. However,
        whenever both ends of a virtual link are multicast-capable, they
        must both be configured as inter-area multicast forwarders (see
        Section 14.11).

    o   Inter-AS multicast forwarder. Indicates whether the router will
        forward IP multicasts between Autonomous Systems. Such a router
        declares itself a wild-card multicast receiver in its router-
        LSAs (see Section 14.6). These routers are also assumed to be
        running some kind of inter-AS multicast protocol. They mark all
        external routes that they import into the OSPF domain as to
        whether they provide multicast connectivity (see Section 14.9).
        When building inter-AS multicast datagram trees, it is these
        routers that appear immediately adjacent to the datagram source
        at the root of the tree.

    8.1.  Additions to the OSPF area structure

        The OSPF area data structure is described in Section 6 of
        [OSPF]. In a MOSPF router, the following item is added to the
        OSPF area structure:

        o   List of group-membership-LSAs. These link state
            advertisements describe the location of the area's multicast
            group members.  Group-membership-LSAs are flooded throughout
            a single area only. Area border routers also summarize their
            attached areas' membership by originating group-membership-
            LSAs into the backbone area. For more information, see



Moy                                                            [Page 41]

RFC 1584              Multicast Extensions to OSPF            March 1994


            Sections 3.1 and 10.

    8.2.  Additions to the OSPF interface structure

        The OSPF interface structure is described in Section 9 of
        [OSPF]. In a MOSPF router, the following items are added to the
        OSPF interface structure. Note that the IPMulticastForwarding
        parameter is really a description of the attached network. As
        such, it should be configured identically on all routers
        attached to a common network; otherwise incorrect routing of
        multicast datagrams may result[13].

        o   IPMulticastForwarding. This configurable parameter indicates
            whether IP multicasts should be forwarded over the attached
            network, and if so, how the forwarding should be done. The
            parameter can assume one of three possible values: disabled,
            data-link multicast and data-link unicast. When set to
            disabled, IP multicast datagrams will not be forwarded out
            the interface. When set to data-link multicast, IP multicast
            datagrams will be forwarded as data-link multicasts. When
            set to data-link unicast, IP multicast datagrams will be
            forwarded as data-link unicasts. The default value for this
            parameter is data-link multicast. The other two settings are
            for use in the special circumstances described in Sections
            6.3 and 6.4. When set to disabled or to data-link unicast,
            IGMP group membership is not monitored on the attached
            network.

        o   IGMPPollingInterval. When the router is actively monitoring
            group membership on the attached network, it periodically
            sends IGMP Host Membership Queries. IGMPPollingInterval is a
            configurable parameter indicating the number of seconds
            between IGMP Host Membership Queries.  The router actively
            monitors group membership on the attached network when both
            a) the interface's IPMulticastForwarding parameter is set to
            data-link multicast and b) the router has been elected
            Designated Router on the attached network. See Section 9 for
            details.

        o   IGMPTimeout. This configurable parameter indicates the
            length of time (in seconds) that a local group database
            entry associated with this interface will persist without
            another matching IGMP Host Membership Report being received.
            See Section 9 for details.

        o   IGMP polling timer. The firing of this interval timer causes
            an IGMP Host Membership Query to be sent out the interface.
            The length of this timer is the configurable parameter



Moy                                                            [Page 42]

RFC 1584              Multicast Extensions to OSPF            March 1994


            IGMPPollingInterval. See Section 9 for details.

    8.3.  Additions to the OSPF neighbor structure

        The OSPF neighbor structure is defined in Section 10 of [OSPF].
        In a MOSPF router, the following items are added to the OSPF
        neighbor structure:

        o   Neighbor Options. This field was already defined in the OSPF
            specification. However, in MOSPF there is a new option which
            indicates the neighbor's multicast capability. This new
            option is learned in the Database Exchange process through
            reception of the neighbor's Database Description packets,
            and determines whether group-membership-LSAs are flooded to
            the neighbor. See the items concerning flooding in Section
            14 for a more detailed explanation.

    8.4.  The local group database

        The local group database has already been introduced in Section
        2.3.1.  The current section attempts a more precise definition.
        The local group database tracks the group membership of the
        router's directly attached networks. Database entries are
        created and maintained by the IGMP protocol. Database entries
        can cause group-membership-LSAs to be originated, which in turn
        enable the pruning of datagram shortest-path trees. The local
        group database also dictates the router's responsibility for the
        delivery of multicast datagrams to directly attached group
        members.

        Each entry in the local group database has three components: the
        multicast group, the attached network and the entry's age. A
        database entry is indexed by the first two components: multicast
        group and attached network. A database lookup function is
        assumed to exist, so that given a [multicast group, attached
        network] pair, the matching database entry (if any) can be
        discovered. A database entry for [Group A, Network N1] exists if
        and only if there are Group A members currently located on
        Network N1.

        The three components of a local group database entry are defined
        as follows:

        o   MulticastGroup. The multicast group whose members are being
            tracked by this entry. Each multicast group is represented
            as a class D IP address. For the semantics of multicast
            group membership, see [RFC 1112].




Moy                                                            [Page 43]

RFC 1584              Multicast Extensions to OSPF            March 1994


        o   AttachedNetwork. Each database entry is concerned with the
            group members belonging to a single attached network. To get
            a complete picture of the local group membership (when for
            example building a group-membership-LSA), it may be
            necessary to consult multiple database entries, one for each
            attached network. Note that a router is only required to
            maintain entries for those attached networks on which the
            router has been elected Designated Router or Backup
            Designated Router (see Section 9).

        o   Age. Indicates the number of seconds since an IGMP Host
            Membership Report for multicast Group A has been seen on
            Network N1. If the age field hits Network N1's configured
            IGMPTimeout value, the local group database entry is removed
            (i.e., the entry has "aged out"). See Sections 9.2 and 9.3
            for more information.

    8.5.  The forwarding cache

        The forwarding cache has already been defined in Section 2.3.
        The current section attempts a more precise definition. Each
        entry in the forwarding cache indicates how a multicast datagram
        having a particular [source network, destination multicast
        group, IP TOS] will be forwarded. A forwarding cache entry is
        built on demand from the local group database and the datagram's
        shortest-path tree. For more details, consult Sections 2.3.4 and
        12.

        Each entry in the forwarding cache has six components: the
        multicast datagram's source network, the destination multicast
        group, the IP TOS, the upstream node, the list of downstream
        interfaces and (possibly) a list of downstream neighbors. A
        forwarding cache entry is indexed by source network, destination
        multicast group and IP TOS. A lookup function is assumed to
        exist, so that given a multicast datagram with a particular [IP
        source, destination multicast group, IP TOS], a matching cache
        entry (if any) can be found.

        The six components of a forwarding cache entry are defined as
        follows:

        o   Source network. The datagram's source network is described
            by a network/subnet/supernet number and its corresponding
            mask. The source network for a datagram is discovered via a
            routing table/database lookup of the datagram's IP source
            address, as described in Section 11.2.





Moy                                                            [Page 44]

RFC 1584              Multicast Extensions to OSPF            March 1994


        o   Destination multicast group. The destination group to which
            matching datagrams are being forwarded. For the semantics of
            multicast group membership, see [RFC 1112].

        o   IP TOS. The IP Type of Service specified by matching
            datagrams. Note that this means that the path of the
            multicast datagram depends on its TOS classification.

        o   Upstream node. The attached network/neighboring router from
            which the datagram must be received. If received from a
            different attached network/neighboring router, the matching
            datagram is dropped instead of forwarded. This prevents
            unwanted replication of multicast datagrams. It is possible
            that the upstream node is unspecified (i.e., set to NULL).
            In this case, matching datagrams will always be dropped, no
            matter where they are received from. It is also possible
            that the upstream node is specified as the placeholder
            EXTERNAL. This means that the datagram must be received on a
            non-MOSPF interface in order to be forwarded.

        o   List of downstream interfaces. These are the router
            interfaces that the matching datagram should be forwarded
            out of (assuming that the datagram was received from
            upstream node). Each interface is also listed with a TTL
            value. The TTL value is the minimum number of hops necessary
            to reach the closest (in terms of router hops) group member.
            This allows the router to drop datagrams that have no chance
            of reaching a destination group member.

        o   List of downstream neighbors. When the datagram is to be
            forwarded out a non-broadcast multi-access network, or if
            the interface's IPMulticastForwarding parameter is set to
            data-link unicast, the datagram must be forwarded separately
            to each downstream neighbor (see Sections 2.3.3 and 6.4). As
            done for downstream interfaces, each downstream neighbor is
            specified together with the smallest TTL that will actually
            reach a group member.

9.  Interaction with the IGMP protocol

    MOSPF uses the IGMP protocol (see [RFC 1112]) to monitor multicast
    group membership. In short, the Designated Router on a network
    periodically sends IGMP Host Membership Queries (see Section 9.1),
    which in turn elicit IGMP Host Membership Reports from the network's
    multicast group members. These Host Membership Reports are then
    recorded in the Designated Router's and Backup Designated Router's
    local group databases (see Section 9.2).




Moy                                                            [Page 45]

RFC 1584              Multicast Extensions to OSPF            March 1994


    9.1.  Sending IGMP Host Membership Queries

        Only the network's Designated Router sends Host Membership
        Queries.  This minimizes the amount of group membership
        information on the network, both in terms of queries and
        responses.

        When a MOSPF router becomes Designated Router on a network, it
        checks to see that the network's IPMulticastForwarding parameter
        is set to data-link multicast (see Section B.2). If so, it
        starts the interface's IGMP polling timer. Then, whenever the
        timer fires (every IGMPPollingInterval seconds), the MOSPF
        router sends a Host Membership Query out the interface. The
        destination of the query is the IP address 224.0.0.1. For the
        format of the query, see [RFC 1112].  If/when the MOSPF router
        ceases to be the network's Designated Router, the IGMP polling
        timer is disabled and no more Hosts Membership Queries are sent.

        Unusual behavior can result when multiple IP networks are
        assigned to a single physical network. MOSPF treats each such IP
        network separately, electing (possibly) a different Designated
        Router for each network.  However, IGMP operates on a physical
        network basis only: when a Host Membership Query is sent, all
        group members on the physical network respond, regardless of
        their IP addresses. So unless the IPMulticastForwarding
        parameter is set to a value other than data-link multicast on
        all but one of the physical network's IP networks, excess
        multicast membership reporting will result.

    9.2.  Receiving IGMP Host Membership Reports

        Received Host Membership Reports are processed by both the
        network's Designated Router and Backup Designated Router. It is
        the Designated Router's responsibility to distribute the
        network's group membership information throughout the routing
        domain, by originating group-membership-LSAs (see Section 10).
        The Backup Designated Router processes Reports so that it too
        has a complete picture of the network's group membership,
        enabling a quick cutover upon Designated Router failure.

        An IGMP Host Membership Report concerns membership in a single
        IP multicast group (call it Group A). The Report is sent to the
        Group A address so that other group members may see the Report
        and avoid sending duplicates (see [RFC 1112] for details). When
        an IGMP Host Membership Report, sent on Network N[14], is
        received by a MOSPF router, the following steps are executed:





Moy                                                            [Page 46]

RFC 1584              Multicast Extensions to OSPF            March 1994


        (1) If the router is neither the Designated Router nor the
            Backup Designated Router on the network, the Report is
            discarded and processing stops.

        (2) If the Report concerns a multicast group in the range
            224.0.0.1 - 224.0.0.255, the Report is discarded and
            processing stops. This range of multicast groups are for
            local use (single hop) only, and datagrams sent to these
            destinations are never forwarded by multicast routers.

        (3) Locate the entry for [Group A, Network N] in the local group
            database.  If no such entry exists, create one. In any case,
            set the age of the entry to 0. Note that even if multiple
            hosts attached to Network N report membership in the same
            group, only a single local group database entry will be
            formed. See Section 8.4 for more details concerning the
            local group database.

        (4) If the router is the network's Designated Router, and a
            local group database entry was created in the previous step,
            it may be necessary to originate a new group-membership-LSA.
            See Section 10 for details.

    9.3.  Aging local group database entries

        Every local database entry has an age field. Suppose that there
        is a database entry for [Group A, Network N1]. The age field
        then indicates the length of time (in seconds) since the last
        Host Membership Report for Group A was received on Network N1.
        If the age of the entry reaches Network N1's configured
        IGMPTimeout value (see Section B.2), the entry is considered
        invalid and is removed from the database.

        Note that when a router, after having been either Network N1's
        Designated Router or Backup Designated Router, but now being
        neither, will (after IGMPTimeout seconds) automatically age out
        all of its local group database entries associated with Network
        N1. For this reason, it is not necessary to purge local group
        database entries on OSPF interface state changes.

    9.4.  Receiving IGMP Host Membership Queries

        If a MOSPF router has internal multicast applications, and if
        the applications have bound themselves to certain interfaces
        (using the RFC 1112 representation described in Section 5), then
        the MOSPF router responds to received Host Membership Queries by
        issuing Host Membership Reports. Identical to the operation of
        any IP host supporting multicast applications, the exact



Moy                                                            [Page 47]

RFC 1584              Multicast Extensions to OSPF            March 1994


        procedure for issuing these Host Membership Reports is specified
        in [RFC 1112]. Note that in this case, if the router has been
        elected Designated Router on a network, it must receive its own
        Host Membership Reports and Host Membership Queries.

        If instead all of its applications have joined groups in an
        interface-independent fashion (using the MOSPF-specific
        representation described in Section 5), the MOSPF router does
        not respond to Host Membership Queries. Instead, the MOSPF
        router communicates this membership information by originating
        appropriate group-membership-LSAs (see Section 10.1).

10.  Group-membership-LSAs

    Group-membership-LSAs provide the means of distributing membership
    information throughout the MOSPF routing domain. Group-membership-
    LSAs are specific to a single OSPF area (see Section 3.1). Each
    group-membership-LSA concerns a single multicast group. Essentially,
    the group-membership-LSA lists those networks which are directly
    connected to the LSA's originator and which contain one or more
    group members. For more details on how the group-membership-LSA
    augments the OSPF link state database, see Section 2.3.1.

    The creation of group-membership-LSAs is discussed in Section 10.1.
    The format of the group-membership-LSA is described in Section A.3.
    A router will originate a group membership-LSA for multicast group A
    when one or more of the following conditions hold:

    (1) The router is Designated Router on a network (call it Network
        X), the interface to Network X has its IPMulticastForwarding
        parameter set to data-link multicast (see Section B.2), and
        Network X contains one or more members of Group A.

    (2) The router is an inter-area multicast forwarder (see Section
        B.1), and one or more of the router's attached non-backbone
        areas contain Group A members. In this case, the router will
        originate a group-membership-LSA for Group A into the backbone.
        This is the way group membership is conveyed between areas (see
        Section 3.1).

    (3) The router itself has applications that are requesting
        membership in Group A, in an interface-independent fashion (see
        Section 5).

    As for all other types of OSPF link state advertisements (e.g,
    router-LSAs, network-LSAs, etc.), group-membership-LSAs are aged as
    they are held in a router's link state database. To prevent valid
    advertisements from "aging out", a router must refresh its self-



Moy                                                            [Page 48]

RFC 1584              Multicast Extensions to OSPF            March 1994


    originated group-membership-LSAs every LSRefreshTime interval, by
    incrementing their LS sequence numbers and reissuing them. In
    addition, when an event occurs that would alter one of the router's
    self-originated group-membership-LSAs, a new instance of the LSA is
    issued with an updated (i.e., incremented by 1) LS sequence number.
    Note however that a router is not allowed to originate two new
    instances of the same advertisement within MinLSInterval seconds.
    For that reason, occasionally advertisement originations will need
    to be deferred. Also, an event may occur that makes it inappropriate
    for the router to continue to originate a particular LSA. In that
    case, the router flushes the advertisement from the routing domain
    by "premature aging". For more information concerning the
    maintenance of LSAs, see Sections 12, 12.4, 14 and 14.1 of [OSPF].

    When one of the following events occurs, it may be necessary for a
    router to (re)issue one or more group-membership-LSAs:

    (1) One of the router's interfaces changes state. For example, the
        router may have become Designated Router on a particular
        network, causing the router to start advertising the network's
        group membership to the rest of the MOSPF system in group-
        membership-LSAs.

    (2) The router receives an IGMP Host Membership Report, causing a
        new local group database entry to be formed (see Section 9.2).

    (3) One of the router's local group database entries "ages out",
        because it is no longer being refreshed by received IGMP Host
        Membership Reports (see Section 9.3).

    (4) The router is an inter-area multicast forwarder, and the group
        membership of one of the router's attached non-backbone areas
        changes.  This is detected by the reception of a new, or the
        flushing of an old, group-membership-LSA into/from the non-
        backbone area's link state database.

    (5) The group membership of one of the router's internal
        applications changes.

    10.1.  Constructing group-membership-LSAs

        This section details how to build a group-membership-LSA. The
        format of a group-membership-LSA is described in Section A.3.
        Each group-membership-LSA concerns a single multicast group. The
        body of the advertisement is a list of the local transit nodes
        (the router itself and directly attached transit networks) that
        contain group members. Section 10 listed the conditions
        requiring the (re)origination of a group-membership-LSA. Note



Moy                                                            [Page 49]

RFC 1584              Multicast Extensions to OSPF            March 1994


        that if the router is an area border router, it may be necessary
        to originate a separate group-membership-LSA for each attached
        area.

        The following defines the contents of a group-membership-LSA, as
        originated by Router X into Area A. It is assumed that the
        group-membership-LSA is to report membership in multicast group
        G:

        o   The advertisement fields that are not type-specific (LS age,
            LS sequence number, LS checksum and length) are set
            according to Section 12.1 of [OSPF].

        o   The Options field of a group-membership-LSA is not processed
            on receipt. However, for consistency, the Option field in
            these advertisements should have its MC-bit set, T-bit
            clear, and the E-bit should match the configuration of Area
            A (i.e., set if and only if Area A is not a stub area). The
            rest of the Options field is set to 0.

        o   The Link State ID is set to the group whose membership is
            being reported (Group G).

        o   The Advertising Router is set to the OSPF Router ID of the
            router originating the advertisement (Router X).

        o   The body of the advertisement is a list of local transit
            vertices that should be labelled with Group G membership
            (see Section 2.3.1). This list may include the advertising
            router itself, and any of the transit networks that are
            directly attached to said router. The following steps
            determine which of these transit vertices are actually
            included in the group-membership-LSA. Note that any
            particular vertex should be listed at most once, even though
            the following may indicate multiple reasons for a particular
            vertex to be listed. Also note that if no transit vertices
            are listed by the advertisement, the advertisement should
            not be (re)originated; if an instance of the advertisement
            already exists, it should then be flushed from the link
            state database using the premature aging procedure specified
            in Section 14.1 of [OSPF].

            a.  Consider those entries in the local group database that
                describe Group G membership (see Section 8.4). Consider
                each such entry in turn. Each entry references one of
                Router X's attached networks (call it Network N). If
                either Network N does not belong to Area A, or if Router
                X is not Network N's Designated Router[15], Network N



Moy                                                            [Page 50]

RFC 1584              Multicast Extensions to OSPF            March 1994


                should not be added to the group-membership-LSA, and the
                next local group database entry should be examined.
                Otherwise, if N is a stub network (e.g., Router X is the
                only OSPF router attached to N), Router X adds itself to
                the advertisement by adding a vertex with Vertex type
                set to 1 (router) and Vertex ID set to Router X's OSPF
                Router ID. Otherwise, N is a transit network. In this
                case, Network N should be added to the advertisement by
                adding a vertex with Vertex type set to 2 (network) and
                Vertex ID set to the IP address of Network N's
                Designated Router (i.e., Router X's IP interface address
                on Network N).

            b.  If Router X itself has applications requesting Group G
                membership on an interface-independent basis (see
                Section 5), it should add itself to the advertisement by
                adding a vertex with Vertex type set to 1 (router) and
                Vertex ID set to Router X's OSPF Router ID.

            c.  If Router X is an inter-area multicast forwarder (see
                Section 3.1), Area A is the backbone area (Area ID
                0.0.0.0), and at least one of Router X's attached non-
                backbone areas has Group G members (indicated by the
                presence of one or more advertisements in the areas'
                link state databases having Link State ID set to Group G
                and LS age set to a value other than MaxAge[16]), then
                Router X should add itself to the advertisement by
                adding a vertex with Vertex type set to 1 (router) and
                Vertex ID set to Router X's OSPF Router ID.

        Consider as an example the network configuration in Figure 4.
        Suppose that Router RT2 has been elected Designated Router for
        Network N3.  Router RT2 would then originate (into Area 1) the
        following group-membership-LSA for Group B:

          ; RT2's group-membership-LSA for Group B

          LS age = 0                     ;always true on origination
          Options = (E-bit|MC-bit)
          LS type = 6                    ;group-membership-LSA
          Link State ID = Group B
          Advertising Router = RT2's Router ID
                 Vertex type = 1         ;RT2 itself (for stub N2)
                 Vertex ID = RT2's Router ID
                 Vertex type = 2         ;Network N3 (since RT2 is DR)
                 Vertex ID = RT2's IP interface address on N3





Moy                                                            [Page 51]

RFC 1584              Multicast Extensions to OSPF            March 1994


    10.2.  Flooding group-membership-LSAs

        When MOSPF routers and non-multicast OSPF routers are mixed
        together in a routing domain, the group-membership-LSAs are not
        flooded to the non-multicast routers[17].  As a general design
        principle, optional OSPF advertisements are only flooded to
        those routers that understand them.

        A MOSPF router learns of its neighbor's multicast-capability at
        the beginning of the "Database Exchange Process" (see Section
        10.6 of [OSPF], receiving Database Description packets from a
        neighbor in state Exstart). A neighbor is multicast-capable if
        and only if it sets the MC-bit in the Options field of its
        Database Description packets.  Then, in the next step of the
        Database Exchange process, group-membership-LSAs are included in
        the Database summary list sent to the neighbor (see Sections 7.2
        and 10.3 of [OSPF]) if and only if the neighbor is multicast-
        capable.

        When flooding group-membership-LSAs to adjacent neighbors, a
        MOSPF router looks at the neighbor's multicast-capability.
        Group-membership-LSAs are only flooded to multicast-capable
        neighbors. To be more precise, in Section 13.3 of [OSPF],
        group-membership-LSAs are only placed on the Link state
        retransmission lists of multicast-capable neighbors[18].  Note
        however that when sending Link State Update packets as
        multicasts, a non-multicast neighbor may (inadvertently) receive
        group-membership-LSAs. The non-multicast router will then simply
        discard the LSA (see Section 13 of [OSPF], receiving LSAs having
        unknown LS types).

11.  Detailed description of multicast datagram forwarding

    This section describes in detail the way MOSPF forwards a multicast
    datagram. The forwarding process has already been informally
    presented in Section 2.2. However, there are several obscure
    configuration options (e.g., the IPMulticastForwarding interface
    parameter) that have been presented elsewhere in this document,
    which may influence the forwarding process. This section gathers
    together all the influencing factors into a single algorithm.

    It is assumed in the following that the datagram under consideration
    has actually be received on one of the router's interfaces. Locally
    generated datagrams (i.e., originated by one of the router's
    internal applications) are handled instead by the algorithm in
    Section 11.3.





Moy                                                            [Page 52]

RFC 1584              Multicast Extensions to OSPF            March 1994


    Assume that the datagram's IP destination is Group G. The forwarding
    process then consists of the following steps:

    (1) Upon reception of the datagram, the MOSPF router notes the
        following parameters. These parameters are examined in later
        steps, to determine whether the datagram should be forwarded.

        a.  The receiving MOSPF interface associated with the datagram.
            Based on the receiving physical interface, the receiving
            MOSPF interface is selected by the algorithm in Section
            11.1.

        b.  Whether the datagram was received as a link-level
            multicast/broadcast or as a link-level unicast. This
            information is used later in Step 7 to help determine
            whether the datagram should be forwarded.

    (2) A copy of the datagram should be passed to each internal
        application that has joined Group G on the receiving MOSPF
        interface (see Section 5).

    (3) If the datagram's IP source address matches the receiving MOSPF
        interface's IP address, the datagram should not be forwarded
        further, and should instead be discarded, completing the
        forwarding process.  This keeps the router's own locally
        originated datagrams from being mistakenly replicated, in those
        cases where the receiving MOSPF interface receives its own
        multicast transmissions.

    (4) If Group G falls into the range 224.0.0.1 through 224.0.0.255
        inclusive, the datagram should not be forwarded further. This
        range of addresses has been dedicated for use on a local network
        segment only.

    (5) Associate a source network (SourceNet) with the multicast
        datagram, as described in Section 11.2. If SourceNet cannot be
        determined (i.e., there is no available unicast route back to
        the datagram source), the datagram should not be forwarded
        further.

    (6) Look up the forwarding cache entry (see Section 8.5) matching
        the datagram's [SourceNet, Group G, TOS] combination. If the
        cache entry does not yet exist, one is built by the calculation
        in Section 12. In order for the datagram to be forwarded, the
        contents of the forwarding cache entry must be further verified
        against the received datagram's characteristics as follows:





Moy                                                            [Page 53]

RFC 1584              Multicast Extensions to OSPF            March 1994


        a.  If the forwarding cache entry's upstream node is unspecified
            (i.e., NULL), then the datagram should not be forwarded
            further.

        b.  Otherwise, suppose that the forwarding cache entry's
            upstream node is set to EXTERNAL. In this case, the datagram
            is forwarded further if and only if the receiving MOSPF
            interface is set to NULL (i.e., if and only if the datagram
            was received on a non-MOSPF interface).

        c.  Otherwise, if the datagram's receiving MOSPF interface does
            not attach to the forwarding cache entry's upstream node,
            the datagram should not be forwarded further.

    (7) If the receiving MOSPF interface's IPMulticastForwarding
        parameter is set to data-link unicast, the datagram should be
        forwarded further only if it was received as a data-link
        unicast.

    (8) At this point the datagram is eligible for further forwarding.
        Before forwarding, the router checks to see whether it has any
        internal applications that have joined Group G on an interface-
        independent basis. If so, a copy of the datagram should be
        passed to each such requesting application process.

    (9) Examine each of the downstream interfaces listed in the
        forwarding cache entry. If the TTL in the datagram is greater
        than or equal to the TTL specified for the downstream interface,
        a copy of the datagram should be forwarded out the downstream
        interface. Before forwarding the datagram copy, the copy's TTL
        should be decremented by 1. On most interfaces, the datagram is
        forwarded as a data-link multicast/broadcast. The exact data-
        link encapsulation is dependent on the attached network's type:

        o   On ethernet and IEEE 802.3 networks, the datagram is
            forwarded as a data-link multicast. The destination data-
            link multicast address is selected as an algorithmic
            translation of the IP multicast destination. See [RFC 1112]
            for details.

        o   On FDDI networks, the datagram is forwarded as a data-link
            multicast.  The destination data-link multicast address is
            selected as an algorithmic translation of the IP multicast
            destination. See [RFC 1390] for details.

        o   On SMDS networks, the datagram is forwarded using the same
            SMDS address that is used by IP broadcast datagrams. See
            [RFC 1209] for details.



Moy                                                            [Page 54]

RFC 1584              Multicast Extensions to OSPF            March 1994


        o   On networks that support broadcast, but not multicast (e.g.,
            the Experimental Ethernet), the datagram is forwarded as a
            data-link broadcast. See [RFC 1112] for details.

        o   On point-to-point networks, the datagram is forwarded in the
            same way that unicast datagrams are forwarded. See [RFC
            1112] for details.

    (10)
        Examine each of the downstream neighbors listed in the
        forwarding cache entry. If the TTL in the datagram is greater
        than or equal to the TTL specified for the downstream neighbor,
        a copy of the datagram should be forwarded to the downstream
        neighbor (as a data-link unicast). Before forwarding the
        datagram copy, the copy's TTL should be decremented by 1.

    ICMP error messages are never generated in response to received IP
    multicasts. In particular, ICMP destination unreachables and ICMP
    TTL expired messages are not generated by the above procedure if the
    router refuses to forward a multicast datagram.

    11.1.  Associating a MOSPF interface with a received datagram

        A MOSPF interface must be associated with a received multicast
        datagram before it is forwarded (see Step 1a of Section 11), and
        with received IGMP Host Membership Reports before they are
        processed (see Section 9.2).

        When there is only a single IP network assigned to the physical
        interface that received the datagram, the choice of receiving
        MOSPF interface is clear. When there are multiple logical IP
        networks attached to the receiving physical interface, the
        receiving MOSPF interface is selected as follows. Examine all of
        the MOSPF interfaces associated with the receiving physical
        interface. Discard those interfaces whose IPMulticastForwarding
        parameter has been set to disabled. The receiving MOSPF
        interface is then the remaining interface having the highest IP
        interface address (or NULL if there are no remaining
        interfaces)[19].

    11.2.  Locating the source network

        MOSPF forwarding cache entries are indexed by the datagram's
        source IP network/subnet/supernet. For this reason, whenever an
        IP multicast datagram is received, the IP network belonging to
        the datagram's IP source address must be found. This is
        accomplished by the following algorithm:




Moy                                                            [Page 55]

RFC 1584              Multicast Extensions to OSPF            March 1994


        Look up the OSPF TOS 0 routing table entry[20] corresponding to
        the datagram's IP source address, as described in Section 11.1
        of [OSPF].  If this routing table entry describes an OSPF
        intra-area or inter-area route, the source network is set to be
        the network defined by the routing table entry's Destination ID
        and Address Mask (see Section 11 of [OSPF]). Otherwise (i.e.,
        the routing table entry specifies an external route, or there is
        no matching routing table entry), the list of matching AS
        external-link-LSAs is examined. A matching AS external-link-LSA
        is one that describes a network which contains the datagram's IP
        source address. The list of matching AS external-link-LSAs is
        pruned in the following steps to determine the source network:

        (1) Those AS external-link-LSAs with MC-bit clear (see Section
            A.1), or with LS age set to MaxAge, or which have been
            originated by unreachable AS boundary routers are discarded.

        (2) AS external-link-LSAs specifying Type 1 external metrics are
            always preferred over those specifying Type 2 external
            metrics.

        (3) If there are still multiple AS external-link-LSAs remaining,
            those specifying the best matching (i.e., most specific)
            network are selected. The source network is then set to the
            network/subnet/supernet (possibly even the default route)
            described by the best matching AS external-link-LSAs. Note
            that AS external-link-LSAs specifying a cost of LSInfinity
            are eligible for this best match, as long as their MC-bit is
            set.[21]

        It is possible that two different MOSPF routers may calculate
        the same multicast datagram's source network differently. For
        example, consider the network configuration shown in Figure 4.
        When calculating the source network for a datagram whose source
        is Network N10 and destination is Group Ma, Router RT11 would
        calculate the source network as Network N10 itself, while Router
        RT10 would calculate the source network as the aggregate of
        Networks N9-N11 and Host H1 (advertised in a single summary-
        link-LSA by Router RT11). However, despite the possibility of
        routers selecting different source networks, all routers will
        still agree on the datagram's shortest-path tree.

        External sources are treated differently in the above
        calculation since it is likely that the Internet will have
        separate multicast and unicast topologies for some time to come.
        When the multicast and unicast topologies do merge, the MC-bit
        will be set on all AS external-link-LSAs and the above use of
        the LSInfinity metric (to indicate a route that is to be used



Moy                                                            [Page 56]

RFC 1584              Multicast Extensions to OSPF            March 1994


        for multicast traffic, but not unicast traffic), will no longer
        be necessary. At that time, the determination of source network
        for external sources will revert to the same simple routing
        table lookup that is used for internal sources.

        As an example of the logic for external sources, suppose a
        multicast datagram is received having the IP source address
        10.1.1.1. Suppose also that the three AS external-link-LSAs
        shown in Table 3 are in the router's OSPF database. The OSPF
        routing table lookup would yield the network 10.1.1.0 with a
        mask of 255.255.255.0, however the above calculation would
        choose a source network of 10.1.0.0 with a mask of 255.255.0.0,
        despite the fact that its matching LSA has a cost of LSInfinity.

    11.3.  Forwarding locally originated multicasts

        This section describes how a MOSPF router forwards a multicast
        datagram that has been originated by one of the router's own
        internal applications. The process begins with one of the
        router's internal applications formatting and addressing the
        datagram. Forwarding the locally originated multicast then
        consists of the following steps:

        (1) Find the router interface whose IP address matches the
            datagram's source address. Multicast the datagram out that
            interface, according to the Host extensions for IP
            multicasting specified in [RFC 1112].

        (2) If the router interface found in the previous step has been
            configured for MOSPF, and if its IPMulticastForwarding
            parameter is not equal to disabled, then set the receiving
            MOSPF interface to that interface.  Otherwise, set the
            receiving MOSPF interface to NULL.

        (3) Execute the MOSPF forwarding process described in Section
            11, beginning with its Step 4.


         Network    Mask            Cost                 MC-bit
         ______________________________________________________
         10.1.1.0   255.255.255.0   Type 1: 10           clear
         10.1.0.0   255.255.0.0     Type 2: LSInfinity   set
         10.0.0.0   255.0.0.0       Type 2: 1            set


                 Table 3: Sample AS external-link-LSAs





Moy                                                            [Page 57]

RFC 1584              Multicast Extensions to OSPF            March 1994


        The above algorithm amounts to the router always multicasting
        the datagram out the source interface, and the executing the
        basic forwarding algorithm (in Section 11) as if the datagram
        had actually been received on the source interface. In those
        cases where the router receives its own multicast transmissions,
        unwanted replication is prevented by Step 3 of Section 11. In
        fact, this specification has purposely presented the forwarding
        algorithm (both for received and for locally originated
        datagrams) so that the correct forwarding actions are taken
        independent of whether the router receives its own multicast
        transmissions.

12.  Construction of forwarding cache entries

    This section details the building of a MOSPF forwarding cache entry.
    A high level discussion of this construction has already been
    presented in Sections 2.3, 2.3.1, 2.3.2, 3.2, and 4.1. Forwarding
    cache entries are built on demand, when a multicast datagram is
    received and no matching forwarding cache entry is found (see Step 6
    of Section 11).  The parameters passed to the forwarding cache entry
    build process are: the datagram's source network (see Section 11.2)
    and its destination group address. These two parameters are called
    SourceNet and Group G in the following algorithm. The main steps in
    the build process are the following:

    (1) Allocate the forwarding cache entry. Initialize its Source
        network to SourceNet, its Destination multicast group to Group G
        and its IP TOS field to match the multicast datagram's TOS.
        Initialize its upstream node and list of downstream interfaces
        to NULL.

    (2) For each Area A to which the calculating router is attached:

        a.  Calculate Area A's datagram shortest-path tree. This
            calculation is described in Section 12.2 below. In many ways
            it is similar to the calculation of OSPF's intra-area
            routes, described in Section 16.1 of [OSPF]. The main
            differences between the multicast datagram shortest-path
            tree calculation and OSPF's intra-area unicast calculation
            are listed in Section 12.2.9 below. As a product of each
            area's datagram shortest-path tree, the forwarding cache
            entry's list of outgoing interfaces is (possibly) updated.

            Area A's datagram shortest-path tree is dependent on the
            datagram's IP TOS. Section 12.2 describes the TOS 0 datagram
            shortest-path tree. The modifications necessary for non-zero
            TOS values are detailed in Section 12.2.8.




Moy                                                            [Page 58]

RFC 1584              Multicast Extensions to OSPF            March 1994


        b.  Possibly set the forwarding cache entry's upstream node.
            Only one of the calculating router's attached areas will
            determine the forwarding cache entry's upstream node. This
            area is called the datagram's RootArea. The RootArea is
            initially set to NULL. After completing Area A's datagram
            shortest-path tree, the calculation in Section 12.2.7 will
            determine whether Area A is the datagram's RootArea.

    (3) Update the forwarding cache entry's list of outgoing interfaces,
        according to the contents of the local group database. This
        ensures multicast delivery to group members residing on the
        calculating router's directly attached networks. This process is
        described in Section 12.3.

    These main steps are described in more detail below. The detailed
    description begins with an explanation of the major data structure
    used by the datagram shortest-path tree calculation: The Vertex data
    structure.

    12.1.  The Vertex data structure

        A datagram shortest-path tree is built by the Dijkstra or SPF
        algorithm. The algorithm is stated herein using graph-oriented
        language: vertices and links. Vertices are the area's routers
        and transit networks, and links are the router interfaces and
        point-to-point lines that connect them. Each vertex has the
        following state information attached to it. Basically, this
        information indicates the current best path from the SourceNet
        to the vertex, and the position of the vertex relative to the
        calculating router. Note that a separate datagram shortest-path
        tree is built for each area, and that the vertices described
        below are also specific to a single area (called Area A).

        o   Vertex type. Set to 1 for routers, 2 for transit networks.
            Note that this coding matches the coding for vertices listed
            in the group-membership-LSA (see Section A.3).

        o   Vertex ID. A 32-bit identifier for the vertex. For routers,
            set to the router's OSPF Router ID. For transit networks,
            set the IP address of the network's Designated Router. Note
            that this coding matches the coding for vertices listed in
            the group-membership-LSA (see Section A.3).

        o   LSA. The link state advertisement describing the vertex'
            immediate neighborhood. Can be discovered by performing a
            database lookup in Area A's link state database (see Section
            12.2 of [OSPF]), with LS type set to Vertex type and Link
            State ID set to Vertex ID.



Moy                                                            [Page 59]

RFC 1584              Multicast Extensions to OSPF            March 1994


        o   Parent. In the current best path from SourceNet to the
            vertex, the router/transit network immediately preceding the
            vertex. Note that the parent can change as better and better
            paths are found, up until the vertex is installed on the
            shortest-path tree.

        o   IncomingLinkType. This parameter is set to the type of link
            that led to Vertex's inclusion on the shortest-path tree.
            Listed in order of decreasing preference[22], the possible
            types are: ILVirtual (virtual links), ILDirect (vertex is
            directly attached to SourceNet), ILNormal (either router-
            to-router or router-to-network links), ILSummary (OSPF
            summary links), ILExternal (OSPF AS external links), or
            ILNone (the vertex is not on the shortest-path tree).

        o   AssociatedInterface/Neighbor. If the current best path from
            SourceNet to the vertex goes through the calculating router,
            this parameter indicates the calculating router's interface
            (or neighbor) which leads to the vertex.

        o   Cost. The cost, in terms of the OSPF link state metric, of
            the current best path from SourceNet to the vertex. Note
            that if the cost of the path is a combination of both
            external type 2 and internal OSPF metrics, that the vertex'
            cost parameter reflects both cost components. Remember that
            the type 2 cost component is always more significant than
            the type 1 component.

        o   TTL. If the current best path from SourceNet to vertex goes
            through the calculating router, TTL is set to the number of
            routers between the calculating router and the vertex. This
            includes the calculating router, but does not include the
            vertex itself.

    12.2.  The SPF calculation

        This section details the construction of datagram shortest-path
        trees.  Such a tree describes the path of a multicast datagram
        as it traverses an OSPF area. For a given datagram, each router
        in an OSPF area builds an identical tree. A router connected to
        multiple areas builds a separate datagram shortest-path tree for
        each area.

        The datagram shortest-path tree is built by the Dijkstra or SPF
        algorithm, which is the same algorithm used to discover OSPF's
        intra-area unicast routes (see Section 16.1 of [OSPF]). The
        algorithm is stated herein and in [OSPF] using graph-oriented
        language: vertices and links. Vertices are the area's routers



Moy                                                            [Page 60]

RFC 1584              Multicast Extensions to OSPF            March 1994


        and transit networks, and links are the router interfaces and
        point-to-point lines that connect them. Basically, the algorithm
        manipulates two lists of vertices: the candidate list and the
        forming shortest-path tree. The candidate list consists of those
        vertices to which paths have been discovered, but for which the
        optimality of the discovered paths is yet unknown. At each cycle
        of the algorithm, the vertex closest to the tree's root, yet
        still remaining on the candidate list, is moved from the
        candidate list to the shortest-path tree. Then the neighbors of
        the just processed vertex are examined for possible addition
        to/modification of the candidate list. The algorithm terminates
        when the candidate list is empty.

        The datagram shortest-path tree for Area A is constructed in the
        following steps. The datagram's SourceNet and its destination
        group G are inputs to the calculation (see Step 6 of Section
        11). The datagram shortest-path tree also depends on the IP Type
        of service specified in the datagrams' IP Header. However, a
        discussion of TOS is deferred until Section 12.2.8; all
        calculations and costs in the current section concern TOS 0
        only. Call the router performing the calculation Router RTX. At
        each step (and in the subordinate Sections 12.2.1 through
        12.2.8) LSAs from Area A's link state database are examined. In
        all cases, any LSA having LS age equal to MaxAge is ignored. The
        main body of the calculation is in Steps 4 and 5, which are
        repeated until the candidate list becomes empty:

        (1) Initialize the algorithm's data structures. Clear the
            shortest-path tree.  Initialize the state of each vertex in
            Area A (i.e., the area's routers and transit networks) to:
            Parent set to NULL, IncomingLinkType set to ILNone and
            AssociatedInterface/Neighbor set to NULL.

        (2) Initialize the candidate list. One or more vertices are
            initially placed on the candidate list, depending on the
            location of SourceNet with respect to Area A and Router RTX.
            This breaks down into the following cases (which are named
            for later reference):

            o   Case SourceIntraArea: SourceNet belongs to Area A. In
                this case, the candidate list is initialized as in
                Section 12.2.1.

            o   Case SourceInterArea1: SourceNet belongs to an OSPF area
                that is not directly attached to Router RTX. In this
                case, the candidate list is initialized as in Section
                12.2.2.




Moy                                                            [Page 61]

RFC 1584              Multicast Extensions to OSPF            March 1994


            o   Case SourceInterArea2: SourceNet does not belong to Area
                A, but it still belongs to an OSPF area that is directly
                attached to Router RTX.  In this case, the candidate
                list is initialized as in Section 12.2.3.

            o   Case SourceExternal: SourceNet is external to the OSPF
                routing domain, and Area A is not an OSPF stub area. In
                this case, the candidate list is initialized as in
                Section 12.2.4.

            o   Case SourceStubExternal: SourceNet is external to the
                OSPF routing domain, and Area A is an OSPF stub area. In
                this case, the candidate list is initialized as in
                Section 12.2.5.

            Two different routers in Area A may select different
            initialization cases above. For example, consider the
            network configuration shown in Figure 4. When calculating
            the Area 3 datagram shortest-path tree for a datagram whose
            source is Network N7 (e.g., from Host H5) and destination is
            Group Ma, Router RT11 would initialize the candidate list
            using Case SourceInterArea2 while Router RT9 would use Case
            SourceInterArea1. Likewise, if Area 3 were configured as an
            OSPF stub area and the datagram source was the external
            Network N12, Router RT11 would use Case SourceStubExternal
            while Router RT9 would use Case SourceInterArea1! However,
            despite the possibility of routers selecting different
            cases, all routers in an area will still initialize the
            candidate list (and in fact, run the rest of the SPF
            calculation) identically.

        (3) If the candidate list is empty, the algorithm terminates.

        (4) Move the closest candidate vertex to the shortest-path tree.
            Select the vertex on the candidate list that is closest to
            SourceNet (i.e., has the smallest Cost value). If there are
            multiple possibilities, select transit networks over
            routers. If there are still multiple possibilities
            remaining, select the vertex having the highest Vertex ID.
            Call the chosen vertex Vertex V. Remove Vertex V from the
            candidate list, and install it on the shortest-path tree.

            Next, determine whether Vertex V has been labelled with the
            Destination multicast Group G. If so, it may cause the
            forwarding cache entry's list of outgoing
            interfaces/neighbors to be updated. See Section 12.2.6 for
            details.




Moy                                                            [Page 62]

RFC 1584              Multicast Extensions to OSPF            March 1994


        (5) Examine Vertex V's neighbors for possible inclusion in the
            candidate list. Consider Vertex V's LSA. Each link in the
            LSA describes a connection to a neighboring router/network.
            If the link connects to a stub network, examine the next
            link in the LSA. Otherwise, the link (Link L) connects to a
            neighboring transit node. Call this node Vertex W. Perform
            the following steps on Vertex W:

            a.  If W is already on the shortest-path tree, or if W's LSA
                does not contain a link back to vertex V, or if W's LSA
                has LS age of MaxAge, or if W is not multicast-capable
                (indicated by the MC-bit in the LSA's Options field),
                examine the next link in V's LSA.

            b.  Otherwise determine the cost to associate with the link
                from V to W.  If SourceNet belongs to Area A (Case
                SourceIntraArea in Step 2), use the cost listed for Link
                L in V's LSA. Otherwise, use the link's reverse cost:
                Examine W's LSA, and find the cost listed for the link
                connecting back to V. Actually, when V and W are both
                routers, there may be multiple links between them. In
                this case, use the smallest cost listed in W's LSA for
                any of the links connecting back to V and having the
                same Type (as specified in the Router-LSA; must be
                either: point-to-point connection or virtual link) as
                Link L[23].

            c.  Calculate the cost from SourceNet to W, when using Link
                L. It is the sum of the cost of SourceNet to V (i.e.,
                V's Cost parameter) plus the link cost calculated in
                Step 5b. Let this sum be Cost C. If W is not yet on the
                candidate list, install W on the candidate list,
                modifying its parameters as specified below (Step 5d).
                Otherwise, W is on the candidate list already. In this
                case, if:

                o   C is less than W's current Cost, update W's
                    parameters on the candidate list as specified below
                    (Step 5d).

                o   C is equal to W's current Cost, then the following
                    tiebreakers are invoked. The type of Link L is
                    compared to W's current IncomingLinkType, and
                    whichever link has the preferred type is chosen (the
                    preference order of link types is listed in Section
                    12.1's definition of IncomingLinkType). If the link
                    types are the same, then a link whose Parent is a
                    transit network is preferred over one whose Parent



Moy                                                            [Page 63]

RFC 1584              Multicast Extensions to OSPF            March 1994


                    is a router. If the links are still equivalent, the
                    link whose Parent has the higher Vertex ID is
                    chosen. Whenever Link L is chosen, W's parameters
                    are modified as below (Step 5d). Whenever the
                    previously discovered link is chosen, the next link
                    in V's LSA is examined instead.

                o   C is greater than W's current Cost, examine the next
                    link in V's LSA.

            d.  At this point, a better candidate path has been found to
                Vertex W, using Link L. Modify Vertex W's parameters
                accordingly. W's Parent is set to Vertex V. W's
                IncomingLinkType is set to ILVirtual if Link L is a
                virtual link, otherwise IncomingLinkType is set to
                ILNormal. W's Cost parameter is set to C. W's TTL and
                AssociatedInterface/Neighbor parameters are set
                according to one of the following cases:

                o   Vertex V is the calculating router itself. In this
                    case, W's TTL parameter is set to 1. If Link L is a
                    virtual link, W's AssociatedInterface/Neighbor is
                    set to NULL. Otherwise, W's
                    AssociatedInterface/Neighbor is set to the non-
                    virtual interface connecting the calculating router
                    to W which has the smallest cost value. Note that,
                    in the reverse cost (inter-area and inter-AS
                    multicast) cases, this may not be the interface
                    corresponding to Link L. However, since W is only
                    concerned with the node it is receiving the datagram
                    from (the upstream node; see Section 11), and not
                    with the particular interface the datagram is
                    received on, the calculating router is free to pick
                    the sending interface when there are multiple
                    connecting links.

                o   Vertex V is upstream of the calculating router
                    (i.e., V's AssociatedInterface/Neighbor is equal to
                    NULL). In this case, Vertex W's TTL parameter is set
                    to 0, and its AssociatedInterface/Neighbor is set to
                    NULL.

                o   V is a transit network, and is directly downstream
                    from the calculating router (i.e., V's
                    AssociatedInterface/Neighbor is non-NULL and V's TTL
                    is set to 1). W is then one of the calculating
                    router's neighbors. In this case, W's TTL parameter
                    is also set to 1. If network V has been configured



Moy                                                            [Page 64]

RFC 1584              Multicast Extensions to OSPF            March 1994


                    for data-link unicasting (see Section B.2) or if V
                    is a non-broadcast network, W's
                    AssociatedInterface/Neighbor is set to W itself (a
                    neighbor of the calculating router). Otherwise, W's
                    AssociatedInterface/Neighbor is set to the
                    calculating router's interface to Network V.

                o   Vertex V is downstream from the calculating router
                    (i.e., V's AssociatedInterface/Neighbor is non-
                    NULL), and either a) V is a router or b) V's TTL
                    parameter is greater than 1. In these cases, W's
                    AssociatedInterface/Neighbor parameter is copied
                    directly from V.  If V is a router, W's TTL
                    parameter is set to V's TTL parameter incremented by
                    one. If V is a transit network, W's TTL parameter is
                    set directly to V's TTL parameter.

        (6) If the candidate list is non-empty, go to Step 4. Otherwise,
            the algorithm terminates.

        After the datagram shortest-path tree for Area A is complete,
        the calculating router (RTX) must decide whether Area A, out of
        all of RTX's attached areas, determines the forwarding cache
        entry's upstream node. This determination is described in
        Section 12.2.7.

        Examples of the above SPF calculation, with particular emphasis
        on the tiebreaking rules, are given in Appendix C.

        12.2.1.  Candidate list Initialization: Case SourceIntraArea

            In this case, SourceNet belongs to Area A.  The candidate
            list is then initialized as follows. Start with the LSA
            listed as Link State Origin in the matching OSPF routing
            table entry.  If this LSA is not multicast-capable (i.e, its
            Options field has the MC-bit clear) the candidate list
            should be set to NULL. Otherwise, the vertex identified by
            the LSA is installed on the candidate list, setting its
            vertex parameters as follows: IncomingLinkType set to
            ILDirect, Cost set to 0, Parent to NULL and
            AssociatedInterface/Neighbor to NULL.

            As a consequence of this initialization, note that if
            SourceNet is a stub network, then the datagram shortest-path
            tree will not actually be rooted at the datagram source, but
            will instead be rooted at the MOSPF router that attaches the
            stub network to the rest of the MOSPF system. For example,
            consider the network configuration shown in Figure 4. When



Moy                                                            [Page 65]

RFC 1584              Multicast Extensions to OSPF            March 1994


            calculating the Area 2 datagram shortest-path tree for a
            datagram whose source is Network N7 (e.g., from Host H5) and
            destination is Group Ma, Router RT11 (and all other routers
            attached to Area 2) will begin with the candidate list set
            to Router RT8. As another example, the datagram shortest-
            path tree pictured in Figure 3 is really rooted at Router
            RT3 instead of Network N4.

        12.2.2.  Candidate list Initialization: Case SourceInterArea1

            In this case, SourceNet belongs to an OSPF area that is not
            directly attached to the calculating router (RTX).  The
            candidate list is then initialized as follows. Examine the
            Area A summary-link-LSAs advertising SourceNet. For each
            such summary-link-LSA: if both a) the MC-bit is set in the
            LSA's Options field and b) the advertised cost is not equal
            to LSInfinity, then the vertex representing the LSA's
            advertising area border router is added to the candidate
            list. An added vertex' state is initialized as:
            IncomingLinkType set to ILSummary, Cost to whatever is
            advertised in the LSA, Parent to NULL and
            AssociatedInterface/Neighbor to NULL.

            For example, consider the network configuration shown in
            Figure 4.  When calculating the Area 1 datagram shortest-
            path tree for a datagram whose source is Network N7 (e.g.,
            from Host H5) and destination is Group Ma, Router RT2 would
            initialize the candidate list to contain the two area border
            routers RT3 (with a cost of 20) and RT4 (with a cost of 19).
            See Figure 6 for more details.

        12.2.3.  Candidate list Initialization: Case SourceInterArea2

            In this case, SourceNet belongs to an OSPF area other than
            Area A, but one that is still directly attached to the
            calculating router (RTX).  The candidate list is then
            initialized in the following two steps:

            (1) Find the Area A summary-link-LSA that best matches
                SourceNet, excluding those summary-link-LSAs specifying
                cost LSInfinity or having unreachable Advertising
                Routers[24].  A matching summary-link-LSA is one that
                advertises a range of addresses containing SourceNet;
                the best matching is as usual the most specific match.
                Let SourceRange be the network described by the best
                matching summary-link-LSA.





Moy                                                            [Page 66]

RFC 1584              Multicast Extensions to OSPF            March 1994


            (2) Similar to the logic in the SourceInterArea1 case,
                examine all the Area A summary-link-LSAs which advertise
                SourceRange. For each such summary-link-LSA: if both a)
                the MC-bit is set in the LSA's Options field, b) the
                advertised cost is not equal to LSInfinity and c) the
                Advertising Router is reachable, then the vertex
                representing the LSA's Advertising Router is added to
                the candidate list. An added vertex' state is
                initialized as: IncomingLinkType set to ILSummary, Cost
                to whatever is advertised in the LSA, Parent to NULL and
                AssociatedInterface/Neighbor to NULL.

            The reason why SourceRange is used, instead of simply using
            SourceNet (as was done in case SourceInterArea1), is that
            routing information may have been collapsed at area
            boundaries. In order for Area A's area border routers and
            its internal routers to construct the same Area A datagram
            shortest-path tree, they must both start at SourceRange -
            Area A's internal routers know nothing about SourceNet. Note
            that SourceRange is not discovered simply by looking at the
            calculating router's configured set of area address ranges,
            in order to avoid dependence on the configured area address
            ranges being synchronized across all area border routers.

            For example, consider the network configuration shown in
            Figure 4.  When calculating the Area 2 datagram shortest-
            path tree for a datagram whose source is Network N11 and
            destination is Group Ma, Router RT11 would calculate
            SourceRange to be the collection: Networks N9-N11 and Host
            H1. It would then initialize the candidate list to contain
            itself (RT11) only, with an associated Cost of 1 (since RT11
            is advertising Networks N9-N11 and Host H1 in a summary-
            link-LSA with a cost of 1).

        12.2.4.  Candidate list Initialization: Case SourceExternal

            In this case, SourceNet is external to the OSPF routing
            domain, and Area A is not an OSPF stub area.  The candidate
            list is then initialized as follows. Note that an attempt
            may be made to add a Vertex W to the candidate list when W
            already belongs to the candidate list. When this happens,
            W's vertex parameters are updated if the Cost parameter it
            would be added with is better[25] (closer to SourceNet) than
            its previous value. When the costs are the same, W's
            parameters are still modified if the IncomingLinkType it
            would be added with is better (see IncomingLinkType's
            definition in Section 12.1) than its previous value.




Moy                                                            [Page 67]

RFC 1584              Multicast Extensions to OSPF            March 1994


            For each AS external-link-LSA advertising SourceNet, the
            following steps are performed:

            o   If the AS external-link-LSA's MC-bit is clear or if its
                advertising router is not reachable, then the AS
                external-link-LSA is not used. AS external-link-LSAs
                having their MC-bit set and advertising a cost of
                LSInfinity can be used; these LSAs describe paths that
                can be used for multicast, but not unicast, data traffic
                (see Section 11.2).

            o   If the AS external-link-LSA's Forwarding address field
                is 0.0.0.0, the following vertices are added to the
                candidate list. If the Advertising AS boundary router
                (call it ASBR) belongs to Area A, the vertex
                representing the AS boundary router is added to the
                candidate list using parameters: IncomingLinkType set to
                ILExternal, Cost to whatever is advertised in the LSA,
                Parent to NULL and AssociatedInterface/Neighbor to NULL.
                Then, regardless of whether ASBR belongs to Area A, all
                Area A area border routers that are advertising
                reachable multicast-capable (MC-bit set) type 4
                summary-link-LSAs for ASBR are added to the candidate
                list. Each such area border router is added with the
                parameters: IncomingLinkType set to ILSummary, Cost to
                the sum of whatever is advertised in the type 4
                summary-link-LSA plus the value in the original AS
                external-link-LSA, Parent to NULL and
                AssociatedInterface/Neighbor to NULL.

            o   If the AS external-link-LSA's Forwarding address field
                is non-zero, the Forwarding address is looked up in the
                OSPF routing table. Then processing breaks into one of
                the following cases:

                o   The Forwarding address is not usable. In this case,
                    nothing is added to the candidate list. The
                    Forwarding address is not usable if either it has no
                    matching routing table entry, or if the matching
                    routing table entry is neither of type intra-area
                    nor of type inter-area.

                o   The Forwarding address belongs to Area A[26]: the
                    Forwarding address' matching routing table entry has
                    Path-type of intra-area and its Associated area is
                    Area A. In this case, the vertex represented by the
                    matching routing table entry's Link State Origin
                    field is added to the candidate list (assuming that



Moy                                                            [Page 68]

RFC 1584              Multicast Extensions to OSPF            March 1994


                    the vertex is multicast-capable). The vertex is
                    added with the parameters: IncomingLinkType set to
                    ILExternal, Cost to whatever was advertised in the
                    original AS external-link-LSA, Parent to NULL and
                    AssociatedInterface/Neighbor to NULL.

                o   The Forwarding address belongs to an area that is
                    not attached to Router RTX[27]: the Forwarding
                    address' matching routing table entry has Path-type
                    of inter-area. Call the network represented by the
                    matching routing table entry ForwardNet. For each
                    reachable multicast-capable summary-link-LSA (in
                    Area A) advertising ForwardNet, add the LSA's
                    advertising area border router to the candidate list
                    using parameters: IncomingLinkType set to ILSummary,
                    Cost to the sum of whatever is advertised in the
                    summary-link-LSA plus the value in the original AS
                    external-link-LSA, Parent to NULL and
                    AssociatedInterface/Neighbor to NULL.

                o   The Forwarding address belongs to another one of
                    Router RTX's attached areas[28]: the Forwarding
                    address' matching routing table entry has Path-type
                    of intra-area and its associated Area is other than
                    Area A.  Call the network represented by the
                    matching routing table entry ForwardNet. First find
                    the Area A summary-link-LSA that best matches
                    ForwardNet, excluding those summary-link-LSAs
                    specifying cost LSInfinity or having unreachable
                    Advertising Routers. Let ForwardRange be the network
                    described by the best matching summary-link-LSA.
                    Then, for each reachable multicast-capable summary-
                    link-LSA (in Area A) advertising ForwardRange, add
                    the LSA's advertising area border router to the
                    candidate list using parameters: IncomingLinkType
                    set to ILSummary, Cost to the sum of whatever is
                    advertised in the summary-link-LSA plus the value in
                    the original AS external-link-LSA, Parent to NULL
                    and AssociatedInterface/Neighbor to NULL.

            The above calculation can be restated as follows. Each of
            Area A's inter-area multicast forwarders and inter-AS
            multicast forwarders are examined. Those that have
            multicast-capable paths to SourceNet (represented as either
            a multicast-capable AS external link or the concatenation of
            a Type 4 summary link and a multicast-capable AS external
            link) are added to the candidate list as router vertices.
            (It is possible that, when considering a router that is both



Moy                                                            [Page 69]

RFC 1584              Multicast Extensions to OSPF            March 1994


            an inter-area multicast forwarder and an inter-AS multicast
            forwarder, two equal cost paths exist to SourceNet, one an
            AS external link and the other a concatenation of a Type 4
            summary link and an AS external link. In this case, the
            concatenation of the Type 4 summary link and the AS external
            link is preferred). The added vertex' state is set as
            follows: IncomingLinkType set to ILSummary if the path is
            represented as a concatenation of a Type 4 summary link and
            an AS external link, IncomingLinkType set to ILExternal
            otherwise, Cost set to the cost of the shortest path from
            vertex to SourceNet, Parent set to NULL and
            AssociatedInterface/Neighbor set to NULL.

            For example, consider the network configuration shown in
            Figure 4.  When calculating the Area 2 datagram shortest-
            path tree for a datagram whose source is Network N14 and
            destination is Group Ma, the candidate list would be
            initialized to the two routers RT7 at a cost of 14 and RT10
            at a cost of 19. This assumes that the external costs
            pictured in Figure 4 are external type 1s.

        12.2.5.  Candidate list Initialization: Case
            SourceStubExternal

            In this case, SourceNet is external to the OSPF routing
            domain, and Area A is an OSPF stub area.  The candidate list
            is then initialized similarly to case SourceInterArea1. The
            Area A summary-link-LSAs advertising DefaultDestination are
            examined. For each such summary-link-LSA having both its
            MC-bit set and its advertised cost not equal to LSInfinity,
            the vertex representing the LSA's advertising area border
            router is added to the candidate list. An added vertex'
            state is initialized as: IncomingLinkType set to ILSummary,
            Cost to whatever is advertised in the LSA, Parent to NULL
            and AssociatedInterface/Neighbor to NULL.

            The most likely outcome of the above is that all of stub
            Area A's inter-area multicast forwarders will be installed
            on the candidate list, with appropriate costs.

        12.2.6.  Processing labelled vertices

            When encountered during the SPF calculation, vertices
            labelled with the destination multicast group (Group G) may
            cause the forwarding cache entry's list of downstream
            interfaces/neighbors to be modified.  A Vertex V in Area A
            is labelled with Group G if and only if at least one of the
            following holds:



Moy                                                            [Page 70]

RFC 1584              Multicast Extensions to OSPF            March 1994


            (1) V is a router, and its router-LSA indicates that it is a
                wild-card multicast receiver (i.e., bit W in its
                router-LSA is set). This may be true when V is an
                inter-area or inter-AS multicast forwarder.

            (2) V is listed in the body of a group membership-LSA. In
                particular, find the originator of Vertex V's LSA; call
                it Router Y. Then find the group-membership-LSA in Area
                A's link state database which has Link State ID = Group
                G and Advertising Router = Router Y (see Section A.3).
                If this group-membership-LSA exists, and if Vertex V is
                listed in the body of the LSA (see Sections 10 and A.3),
                then Vertex V is labelled with Group G.

            When Vertex V is added to the shortest-path tree in Step 4
            of Section 12.2, and if Vertex V is both downstream from the
            calculating router (i.e., Vertex V's
            AssociatedInterface/Neighbor is non-NULL) and labelled with
            Group G, then Vertex V's AssociatedInterface/Neighbor is
            added to the forwarding cache entry's list of downstream
            interfaces/neighbors. In addition, Vertex V's TTL value is
            attached to the added downstream interface/neighbor. If the
            particular interface/neighbor had already been added to the
            list of downstream interfaces/neighbors, the list is simply
            modified by setting the downstream interface/neighbor's TTL
            value to the minimum of its existing TTL value and Vertex
            V's TTL value.

        12.2.7.  Merging datagram shortest-path trees

            After the datagram shortest-path tree for Area A is
            complete, the calculating router (RTX) must decide whether
            Area A, out of all of its attached areas, determines the
            forwarding cache entry's upstream node.  This is done by
            examining RTX's position on the Area A datagram shortest-
            path tree, which is in turn described by RTX's Area A Vertex
            data structure. If RTX's Vertex parameter IncomingLinkType
            is either ILNone (RTX is not on the tree), ILVirtual or
            ILSummary, then some area other than Area A will determine
            the upstream node. Otherwise, Area A might possibly
            determine the upstream node (i.e., may be selected the
            RootArea), depending on the following tiebreakers[29]:

            o   If RootArea has not been set, then set RootArea to Area
                A. Otherwise, compare the present RootArea to Area A in
                the following:





Moy                                                            [Page 71]

RFC 1584              Multicast Extensions to OSPF            March 1994


            o   Choose the area that is "nearest to the source". Nearest
                to the source depends on each area's candidate list
                initialization case, as it occurs in Step 2 of Section
                12.2. The initialization cases, listed in order of
                decreasing preference (or nearest to farthest) are:
                SourceIntraArea, SourceInterArea1, SourceExternal and
                SourceStubExternal. Areas whose candidate list
                initialization falls into case SourceInterArea2 are
                never used as the RootArea. As an example, consider the
                network configuration shown in Figure 4. When
                calculating the datagram shortest-path tree for a
                datagram whose source is Network N7 (e.g., from Host H5)
                and destination is Group Ma, Router RT11 would set its
                RootArea to Area 2 (Case SourceIntraArea) instead of
                Area 3 (Case SourceInterArea2) or the backbone Area 0
                (Case SourceInterArea).

            o   If there are still two equally good areas, and one of
                them is the backbone, set RootArea to the backbone (Area
                0).

            o   If there are still two equally good areas, set RootArea
                to the area whose datagram shortest-path tree provides
                the shortest path from SourceNet to RTX. This is a
                comparison of RTX's Vertex parameter Cost in the two
                areas.

            o   If there are still two equally good areas, set RootArea
                to one with the highest OSPF Area ID.

            If the above has set the RootArea to be Area A, the
            forwarding cache entry's upstream node must be set
            accordingly. This setting depends on the IncomingLinkType in
            RTX's Area A Vertex structure. If IncomingLinkType is equal
            to ILDirect, the upstream node is set to the appropriate
            directly-connected stub network. If equal to ILNormal, the
            upstream node is set to the Parent field in RTX's Area A
            Vertex structure. If equal to ILExternal, the upstream node
            is set to the placeholder EXTERNAL.

        12.2.8.  TOS considerations

            The previous sections 12.2 through 12.2.7 described the
            construction of a TOS 0 (default TOS) datagram shortest-path
            tree. However, in a TOS-capable router, a separate tree may
            be built for each TOS. If a TOS-capable router receives a
            multicast datagram that specifies a non-zero TOS X, it first
            builds the TOS 0 datagram shortest-path tree.  Then, if all



Moy                                                            [Page 72]

RFC 1584              Multicast Extensions to OSPF            March 1994


            the routers on the pruned tree are TOS-capable, a separate
            TOS X datagram shortest-path tree is calculated[30].
            Otherwise, the TOS 0 tree is used for all datagrams,
            regardless of their specified TOS.

            To determine whether there are any TOS-incapable routers on
            the pruned TOS 0 tree, the following additions are made to
            Section 12.2's tree calculation:

            o   A new piece of state information is added to each
                vertex: TOS-capable path. This indicates whether the
                present path from SourceNet to vertex, as represented on
                the datagram shortest-path tree, contains only TOS-
                capable routers.

            o   The TOS-capable path parameter is calculated when the
                vertex is first added to the candidate list and
                recalculated when/if the vertex' position on the
                candidate list is modified (see Section 12.2's Step 2
                and Step 5d). The parameter is set to TRUE if both the
                vertex itself is TOS-capable and the vertex' parent has
                its TOS-capable path parameter set to TRUE; otherwise,
                TOS-capable path is set to FALSE.

            o   All routers on the TOS 0 datagram shortest-path tree are
                TOS-capable if and only if, whenever a vertex labelled
                with Group G is added to the shortest-path tree (Section
                12.2.6), the value of the vertex' TOS-capable path
                parameter is TRUE.

            The source of the multicast datagram is always located using
            a TOS 0 routing table lookup, regardless of the datagram's
            TOS classification (see Section 11.2). If the calculating
            router is not capable of TOS-based routing, it calculates
            only TOS 0 datagram shortest-path trees, and uses them to
            route datagrams independent of TOS value.  Otherwise, when
            calculating the TOS X datagram shortest-path tree, the
            algorithm in Section 12.2 is used, with the modifications
            listed below.

            o   When calculating RangeNet and ForwardRange in Sections
                12.2.3 and 12.2.4 respectively, only summary-link-LSAs
                having TOS 0 cost of LSInfinity are excluded (no change
                from the TOS 0 case). However, when adding vertices to
                the candidate list in Sections 12.2.2 through 12.2.5,
                the TOS X cost of the summary links and/or AS external
                links (and not the TOS 0 cost) are reflected in the
                added vertices' Cost parameter.



Moy                                                            [Page 73]

RFC 1584              Multicast Extensions to OSPF            March 1994


            o   In Step 5 of Section 12.2, the TOS X cost of Link L (in
                the appropriate direction) is used, not the TOS 0 cost.

            o   Non-TOS-routers are not added to the candidate list, and
                are thus excluded from the trees.

        12.2.9.  Comparison to the unicast SPF calculation

            There are many similarities between the construction of a
            multicast datagram's shortest-path trees in Section 12.2 and
            OSPF's intra-area route calculation for unicast traffic
            (Section 16.1 of [OSPF]). Both have been described in terms
            of Dijkstra's algorithm. However, there are some
            differences. The major differences are listed below:

            o   In the multicast case, the datagram SPF calculation is
                rooted at the datagram's source. In the unicast case,
                each router is the root of its own unicast intra-area
                SPF calculation.

            o   In the multicast case, the datagram shortest-path tree
                is a true tree; i.e., between any two nodes on the tree
                there is one path. However, due to the provision for
                equal-cost multipath in [OSPF], the unicast SPF
                calculation may add additional links to the shortest-
                path tree.

            o   In order to avoid unwanted replication of multicast
                datagrams, MOSPF ensures that, for any given datagram,
                each router builds the exact same datagram shortest-path
                tree. This forces two differences from the unicast SPF
                calculation. First, it eliminates the possibility of
                equal-cost multipath. Secondly, when the MOSPF system
                contains multiple alternate paths, the algorithm must
                ensure that each MOSPF router deterministically chooses
                the same alternative. For this reason, tie-breaking
                mechanisms have been specified in Steps 2, 4 and 5b of
                Section 12.2.

            o   The calculation of datagram shortest path trees takes
                into account only those links that connect transit nodes
                (i.e, router to router or router to transit network
                links). The unicast SPF calculation in Section 16.1 of
                [OSPF] must additionally examine links to stub networks,
                although this is done after all the transit links are
                examined.





Moy                                                            [Page 74]

RFC 1584              Multicast Extensions to OSPF            March 1994


            o   While both the multicast and unicast trees select
                shortest paths on the basis of the OSPF metric, the
                datagram shortest-path trees also keep track of the TTL
                values between the root (datagram source) and all
                destinations (group members). This enables more
                efficient implementation of IP multicast's "expanding
                ring search" (see Section 2.3.4).

            o   In the multicast case, the algorithm is sometimes forced
                to use the link state cost for the reverse direction
                (i.e, the cost towards, instead of away from, the
                source). This is because the costs of OSPF summary-
                link-LSAs and AS external-link-LSAs, which sometime form
                the base of the multicast datagram shortest-path trees,
                are specified in the reverse direction (from the
                multicast perspective).

            o   There are potentially many more datagram shortest-path
                trees that need to be calculated (one for each source
                net, destination group and TOS combination), than the
                limited number of unicast SPF trees (one per each TOS).
                This is the main reason that the datagram shortest-path
                trees are calculated on demand; it is hoped that this
                will spread the cost of the SPF calculations over
                time[31].

            o   The way that the two algorithms handle TOS is different.
                In the multicast case, if a TOS-incapable node is
                encountered during the calculation of the TOS 0 datagram
                shortest-path tree, the TOS 0 datagram shortest-path
                tree is used instead of trying to build the TOS X tree
                (see Section 12.2.8). In the unicast case, the TOS X
                tree is always used, only falling back on the TOS 0
                paths when a TOS X path does not exist.

    12.3.  Adding local database entries to the forwarding cache

        After the datagram shortest-path trees have been built for each
        attached area, the forwarding cache has an upstream node and a
        list of downstream interfaces. In order to ensure the delivery
        of the multicast datagram to group members on directly attached
        networks, the local group database (Section 8.4) must then be
        scanned for possible addition to the list of downstream
        interfaces. All local group database entries having Group G as
        MulticastGroup are examined.  Suppose [Group G, Network N] is
        one such entry. If the calculating router (RTX) is Network N's
        Designated Router, then RTX's Network N interface is added to
        the list of outgoing interfaces, with a TTL of 1. If the Network



Moy                                                            [Page 75]

RFC 1584              Multicast Extensions to OSPF            March 1994


        N interface was already present in the list of outgoing
        interfaces, its TTL is simply set to 1.

        For example, consider the network configuration shown in Figure
        4 when calculating the forwarding cache entry for a datagram
        whose source is Network N4 (e.g., from Host H2) and destination
        is Group Mb. After calculating the datagram shortest-path tree
        for Area 1, Router RT2 would have set it upstream node to
        Network N3 and its list of downstream interfaces to NULL. But
        then looking at its local group database, it would add its
        Network N2 interface with a TTL of 1 to its list of downstream
        interfaces.

13.  Maintaining the forwarding cache

    A MOSPF router may, for resource reasons, limit the size of its
    forwarding cache. At any time cache entries can be purged to make
    room for newer entries, since the purged entries can always be
    rebuilt when necessary. This memo does not specify an algorithm to
    select which entries to purge. However, care should be taken to
    ensure that any particular entry is not continually rebuilt and then
    purged again (i.e., thrashing should be avoided).

    The building of the forwarding cache has been previously described
    in Section 12. There are events that force one or more forwarding
    cache entries to be deleted; these events are described below. Note
    that deleted cache entries will be rebuilt on an as-needed basis.

    o   When the internal topology of the MOSPF system changes, all
        forwarding cache entries must be deleted. This is because
        internal topology changes may invalidate the previously
        calculated datagram shortest-path trees. Since the multicast
        routing calculation depends on the result of the unicast routing
        calculations, the forwarding cache should be cleared after the
        unicast routing table is rebuilt.  Internal topology changes are
        indicated when both a) a new instance of either a router-LSA or
        a network-LSA is received and b) the contents of the new
        advertisement (other than the LS age, LS sequence number and LS
        checksum fields) are different from the previous instance. This
        covers routers and links going up or down, routers that change
        from being multicast-incapable to being multicast-capable, etc.

    o   When a Type 3 summary-link-LSA (network summary) changes, those
        forwarding cache entries specifying datagram sources belonging
        to the range of addresses described by the updated summary-
        link-LSA must be deleted. See Sections 12.2.3 and 12.2.5.





Moy                                                            [Page 76]

RFC 1584              Multicast Extensions to OSPF            March 1994


    o   Suppose that the content of an AS external-link-LSA changes. If
        the AS external-link-LSA describes an external network N, then
        all forwarding cache entries specifying an external source
        network that is contained in N or that contains N (i.e.,
        external sources that are a subset or a superset of N) must be
        deleted.

    o   When membership in a multicast group changes, all forwarding
        cache entries for the particular group must be deleted. Group
        membership changes are indicated when either a) the content of a
        group-membership-LSA changes or b) an entry in the local group
        database (see Section 8.4) changes.

    o   When the cost to an AS boundary router or to a forwarding
        address specified by one or more AS external-link-LSAs changes,
        all forwarding cache entries specifying an external network as
        datagram source must be deleted. In this case, potentially all
        inter-AS datagram shortest-path trees have been invalidated. The
        forwarding cache entries should be deleted after the new best
        cost to the AS boundary router/forwarding address has been
        calculated.

14.  Other additions to the OSPF specification

    MOSPF requires some modifications to the base OSPF protocol. All
    these modifications are backward-compatible. A router running MOSPF
    will still interoperate with an OSPF router when forwarding unicast
    traffic. Most of the modifications have been described earlier in
    this document. This section collects together those changes which
    have yet to be mentioned, organizing them by the affected Section of
    [OSPF].

    14.1.  The Designated Router

        This functionality is described in Section 7.3 of [OSPF]. In
        OSPF, a network's Designated Router has two specialized roles.
        First, it originates the network's network-LSA. Second, it
        controls the flooding on the network, in that all of the routers
        on the network synchronize with the Designated Router (and the
        Backup Designated Router) only.  For these reasons[32], when one
        or more of the network's routers are running MOSPF, the
        Designated Router should be running MOSPF also.  This can be
        ensured by assigning all non-multicast routers the Router
        Priority of 0.

        In MOSPF, the Designated Router also has the additional
        responsibility of monitoring the network's multicast group
        membership. This is done by periodically sending Host Membership



Moy                                                            [Page 77]

RFC 1584              Multicast Extensions to OSPF            March 1994


        Queries, and receiving Host Membership Reports in response (see
        Section 9). This is yet another reason why the Designated Router
        must be multicast-capable.

    14.2.  Sending Hello packets

        This functionality is described in Section 9.5 of [OSPF]. A
        MOSPF router sets the MC-bit in the Options field of its Hello
        packets. This indicates that the router is multicast-capable; it
        does not necessarily indicate the state of the sending
        interface's IPMulticastForwarding parameter (see Section B.2).
        Setting the MC-bit in Hellos is done strictly for informational
        purposes. Neighbors receiving the router's Hello packets do not
        act on the state of the MC-bit. A neighbor's multicast-
        capability is learned instead during the Database Exchange
        Process (see Section 14.4).

    14.3.  The Neighbor state machine

        This functionality is described in Section 10.3 of [OSPF]. When
        a neighbor enters state Exchange, the neighbor Database summary
        list is initialized (see the OSPF neighbor FSM entry for State:
        ExStart and Event: NegotiationDone). This list describes of the
        portion of the router's link state database that needs to be
        synchronized with the neighbor.  Group-membership-LSAs are
        included in the neighbor Database summary list if and only if
        the neighbor is multicast-capable. The neighbor's multicast
        capability is learned by examining the neighbor's Database
        Description packets (see Section 14.4).

    14.4.  Receiving Database Description packets

        This functionality is described in Section 10.6 of [OSPF]. A
        neighbor's multicast-capability is learned through received
        Database Description packets. When the Database Description
        packet is received that transitions the neighbor from ExStart to
        Exchange, the state of the MC-bit in the packet's Options field
        is examined. The neighbor is multicast-capable if and only if
        the MC-bit is set.

        The neighbor's multicast capability controls whether group-
        membership-LSAs are summarized to the neighbor during the
        Database Exchange process (see Section 14.3), and whether
        group-membership-LSAs are flooded to the neighbor during the
        flooding process (see Section 10.2).






Moy                                                            [Page 78]

RFC 1584              Multicast Extensions to OSPF            March 1994


    14.5.  Sending Database Description packets

        This functionality is described in Section 10.8 of [OSPF]. A
        MOSPF router sets the MC-bit in the Options field of its
        Database Description packets. This indicates to its adjacent
        neighbors that the router is multicast-capable; it does not
        necessarily indicate the state of the sending interface's
        IPMulticastForwarding parameter (see Section B.2).

        When a router goes from being multicast-capable to multicast-
        incapable, or vice-versa, it must indicate this fact to its
        adjacent neighbors by restarting the Database Description
        process (i.e., rolling back the state of all adjacent neighbors
        to Exstart).

    14.6.  Originating Router-LSAs

        This functionality is described in Section 12.4.1 of [OSPF]. A
        MOSPF router sets the MC-bit in the Options field of its
        router-LSA. This allows the router to be included in datagram
        shortest-path trees (see Step 5a of Section 12.2).

        In addition, MOSPF has introduced a new flag in the router-LSA's
        rtype field: the W-bit. When the W-bit is set, the router is
        included on all datagram shortest-path trees, regardless of
        multicast group (see Section 12.2.6). Such a router is called a
        wild-card multicast receiver. The router sets the W-bit when it
        wishes to receive all multicast datagrams, regardless of
        destination. This will sometimes be true of inter-area multicast
        forwarders (see Section 3.1), and inter-AS multicast forwarders
        (see Section 4).

        A router must originate a new instance of its router-LSA
        whenever an event occurs that would invalidate the LSA's current
        contents. In particular, if the router's multicast capability or
        its ability to function as either an inter-area or inter-AS
        multicast forwarder changes, its router-LSA must be
        reoriginated.

    14.7.  Originating Network-LSAs

        This functionality is described in Section 12.4.2 of [OSPF]. In
        OSPF, a transit network's network-LSA is originated by the
        network's Designated Router. The Designated Router sets the MC-
        bit in the Options field of the network-LSA if and only if both
        a) the Designated Router is multicast-capable (i.e., running
        MOSPF) and b) the Designated Router's interface's
        IPMulticastForwarding parameter has been set to a value other



Moy                                                            [Page 79]

RFC 1584              Multicast Extensions to OSPF            March 1994


        than disabled (see Section B.2). When the network-LSA has the
        MC-bit set, the network can be included in datagram shortest-
        path trees (see Section 12.2.6).

        It is intended that all routers attached to a common network
        agree on the network's IPMulticastForwarding capability.
        However, this agreement is not enforced. When there are
        disagreements, incorrect routing of multicast datagrams can
        result.

    14.8.  Originating Summary-link-LSAs

        This functionality is described in Section 12.4.3 of [OSPF].
        Inter-area multicast forwarders always set the MC-bit in the
        Options field of their summary-link-LSAs, regardless of whether
        the path described by the summary-link-LSA is actually
        multicast-capable. Indeed, it is possible that there is no
        multicast-capable path to the described destination. All other
        area border routers (ones that are not inter-area multicast
        forwarders) clear the MC-bit in the Options field of their
        summary-link-LSAs.

        If its MC-bit is clear, the summary-link-LSA will not be used
        when initializing the candidate list in Sections 12.2.2, 12.2.3
        and 12.2.5.

    14.9.  Originating AS external-link-LSAs

        This functionality is described in Section 12.4.4 of [OSPF].
        Unlike in summary-link-LSAs, an inter-AS multicast forwarder
        should clear the MC-bit in the Options field of one of its AS
        external-link-LSAs if it is known that there is no multicast-
        capable path from the described destination to the router
        itself. This knowledge may possibly be obtained, for example,
        from an inter-AS multicast routing algorithm (see Section 4).
        If the inter-AS multicast forwarder is unsure of whether a
        multicast-capable path exists between the described destination
        and the router itself, the MC-bit should be set in the AS
        external-link-LSA.  All other AS boundary routers (ones that are
        not inter-AS multicast forwarders) clear the MC-bit in the
        Options field of their AS external-link-LSAs.

        If its MC-bit is clear, the AS external-link-LSA will not be
        used when initializing the candidate list in Section 12.2.4.

        When multicast connectivity to an external destination exists,
        but no unicast connectivity, an AS external-link-LSA can be
        originated having its MC-bit set and specifying a cost of



Moy                                                            [Page 80]

RFC 1584              Multicast Extensions to OSPF            March 1994


        LSInfinity. Such an AS external-link-LSA will still be used by
        the multicast routing calculation (see Section 12.2.4). As a
        result, when a MOSPF router wishes to stop advertising an AS
        external destination, it must use the premature aging procedure
        specified in Section 14.1 of [OSPF], rather than simply setting
        the AS external-link-LSA's cost to LSInfinity.

    14.10.  Next step in the flooding procedure

        This functionality is described in Section 13.3 of [OSPF].
        Group-membership-LSAs are specific to a OSPF single area, and
        are flooded to multicast-capable routers only. When flooding a
        group-membership-LSA, Section 13.3 of the OSPF specification is
        modified as follows: 1) The list of interfaces examined during
        flooding (called the eligible interfaces in Section 13.3 of
        [OSPF]) is the set of all interfaces attaching to Area A (the
        area that the group-membership-LSA is received from), just as
        for router-LSAs, network-LSAs and summary-link-LSAs. 2) When
        examining each interface, a group-membership-LSA is added to a
        neighbor's link state retransmission list if and only if both a)
        Step 1d of [OSPF]'s Section 13.3 is reached for the neighbor and
        b) the neighbor is multicast-capable. The neighbor's multicast
        capability is discovered during the Database Exchange process
        (see Section 14.4).

        Note that, since on broadcast networks Link State Update packets
        are sent initially as multicasts, non-multicast routers may
        receive group-membership-LSAs. However, non-multicast routers
        will simply drop the group-membership-LSAs, for reasons of
        unrecognized LS type (see Step 2 of [OSPF]'s Section 13). Link
        State acknowledgments for group-membership-LSAs are not expected
        from non-multicast routers, and group-membership-LSAs will never
        be retransmitted to non-multicast routers, since the LSAs are
        not added to these routers' link state retransmission lists (see
        above paragraph).

        For more information on flooding group-membership-LSAs, see
        Section 10.2.

    14.11.  Virtual links

        This functionality is described in Section 15 of [OSPF]. When a
        MOSPF router (i.e., multicast-capable router) is both an area
        border router and an endpoint of a virtual link whose other
        endpoint is also multicast capable, the router must then also be
        an inter-area multicast forwarder. This is necessary to ensure
        that multicast datagrams will flow through the virtual link's
        transit area, from one endpoint to the other. When the



Moy                                                            [Page 81]

RFC 1584              Multicast Extensions to OSPF            March 1994


        backbone's datagram shortest-path tree is constructed in Section
        12.1, it is assumed that virtual links are capable of forwarding
        multicast datagrams whenever both endpoints are multicast-
        capable.















































Moy                                                            [Page 82]

RFC 1584              Multicast Extensions to OSPF            March 1994


15.  References

    [Bharath-Kumar] Bharath-Kumar, K. and J. Jaffe, "Routing to Multiple
                    Destinations in Computer Networks", IEEE
                    Transactions on Communications, COM-31[3], March
                    1983.

    [Deering]       Deering, S., "Multicast Routing in Internetworks and
                    Extended LANs", SIGCOMM Summer 1988 Proceedings,
                    August 1988.

    [Deering2]      Deering, S., "Multicast Routing in a Datagram
                    Internetwork", Stanford Technical Report, STAN-CS-
                    92-1415, Department of Computer Science, Stanford
                    University, December 1991.

    [OSPF]          Moy, J., "OSPF Version 2", RFC 1583, Proteon, Inc.,
                    March 1994.

    [RFC 1075]      Waitzman, D., Partridge, C., and S. Deering,
                    "Distance Vector Multicast Routing Protocol", RFC
                    1075, BBN STC, Stanford University, November 1988.

    [RFC 1112]      Deering, S., "Host Extensions for IP Multicasting",
                    STD 5, RFC 1112, Stanford University, May 1988.

    [RFC 1209]      Piscitello, D., and J. Lawrence, "Transmission of IP
                    Datagrams over the SMDS Service", RFC 1209, Bell
                    Communications Research, March 1991.

    [RFC 1340]      Reynolds, J. and J. Postel, "Assigned Numbers", STD
                    2, RFC 1340, USC/Information Sciences Institute,
                    July 1992.

    [RFC 1390]      Katz, D., "Transmission of IP and ARP over FDDI
                    Networks", STD 36, RFC 1390, cisco Systems, Inc.,
                    January 1993.














Moy                                                            [Page 83]

RFC 1584              Multicast Extensions to OSPF            March 1994


Footnotes

    [1]Actually, OSPF allows a separate link cost to be configured for
    each TOS. MOSPF then potentially calculates separate paths for each
    TOS. For details, see Section 6.2.

    [2]We also assume in this section that the pictured multi-access
    networks provide data-link multicast/broadcast services.

    [3]Note that if N3 were a non-broadcast network, Router RT3 would
    send separate copies of the datagram to routers RT1 and RT2. Since
    the IGMP protocol is not defined on non-broadcast networks, there
    could in this case be no Group B member attached to Network N3.
    However the multicast datagram would still be delivered to the Group
    B members attached to networks N1 and N2.

    [4]Actually, in MOSPF there is a separate forwarding cache entry for
    each combination of source, destination and TOS. For a discussion of
    TOS-based multicast routing, see Section 6.2.

    [5]The discussion in this section omits mention of the Backup
    Designated Router's role in the IGMP protocol. While the Backup
    Designated Router does not send IGMP Host Membership Queries, it
    does listen to IGMP Host Membership Reports, building "shadow" local
    group database entries in the process. These entries do not lead to
    group-membership-LSAs, nor do they influence delivery of multicast
    datagrams, but are merely maintained to ease the transition from
    Backup Designated Router to Designated Router, should the Designated
    Router fail. See Sections 2.3.4, 9 and 10 for details.

    [6]One might imagine building all possible datagram shortest-path
    trees up front. However, this might be expensive, both in router CPU
    time and in router memory. It is hoped that building the datagram
    shortest-path trees on demand and caching the results will ease
    demands on router resources by spreading out the calculations over a
    longer period of time.

    [7]It is possible that, due to the existence of alternate paths,
    several different shortest-path trees are available. MOSPF depends
    on all routers constructing the exact same shortest path tree. For
    that reason, tie-breaking schemes have been implemented during tree
    construction to ensure that identical trees result. See Section 12
    for more details.

    [8]Note that the expanding ring search yields the nearest server in
    terms of hop count, but not necessarily in terms of the OSPF metric.

    [9]This means that in MOSPF, just as in OSPF, the only kind of link



Moy                                                            [Page 84]

RFC 1584              Multicast Extensions to OSPF            March 1994


    state advertisement that can be flooded between areas is the AS
    external-link-LSA.

    [10]A router indicates that it is a wild-card multicast receiver by
    setting the appropriate flag in its router-LSA. See Section 14.6 for
    details.

    [11]This is not quite true. As we shall see, any inter-AS multicast
    forwarders belonging to the backbone are designated as wild-card
    multicast receivers. See Section 4.

    [12]It is possible that through the operation of an inter-AS
    multicast routing protocol, Router RT7 knows that it does not have
    multicast connectivity to Network N15 (even though it has unicast
    connectivity). In this case, RT7 would not advertise the external
    link to N15 as being multicast capable.

    [13]Synchronization of the IPMulticastForwarding interface parameter
    is not enforced by the MOSPF protocol, since it is not included in
    the contents of a MOSPF router's Hello packets.

    [14]Actually, when multiple IP networks have been assigned to the
    same physical network, the first thing that needs to be done is to
    associate an IP network with the received Host Membership Report.
    This is done in the same way that a receiving interface is
    associated with a received multicast datagram; see Section 11.1.

    [15]For this reason when a transit network has both MOSPF routers
    and non-multicast OSPF routers attached, care should be taken to
    ensure that a MOSPF router is elected Designated Router. This can be
    accomplished through proper setting of the routers' configured
    Router Priority.

    [16]Note that just because these advertisements exist in the link
    state database, it does not mean that the Group G members are
    reachable.  Reachability does not enter into the building of the
    transit vertex list, in order to simplify the calculation. This is a
    trade-off. As a result, some multicast datagrams may be forwarded
    further than necessary, when the described Group G members actually
    are unreachable.

    [17]Since the Designated Router controls flooding on the network,
    this is another reason to ensure that a MOSPF router is elected as
    Designated Router.

    [18]In other words, group-membership-LSAs will never be
    retransmitted to non-multicast routers.




Moy                                                            [Page 85]

RFC 1584              Multicast Extensions to OSPF            March 1994


    [19]This last step will not be necessary if the configuration
    guidelines presented in Section 6.5 are followed.

    [20]The TOS 0 routing table entry is examined regardless of the TOS
    specified by the multicast datagram.

    [21]It is assumed that a MOSPF router that wants to stop advertising
    a route to an external destination will use the premature aging
    procedure specified in Section 14.1 of [OSPF], rather than setting
    the AS external-link-LSA's cost to LSInfinity.

    [22]This preference ordering is used in Step 5c of Section 12.2.

    [23]No attempt is made to match the links' two halves. See Step 5d.

    [24]However, a summary-link-LSA is eligible for matching even if the
    MC-bit in its Options field is clear.

    [25]Costs may have both a Type 2 and a Type 1 component; the Type 2
    component is always most significant.

    [26]This case mirrors the SourceIntraArea candidate list
    initialization in Section 12.2.1.

    [27]This case mirrors the SourceInterArea1 candidate list
    initialization in Section 12.2.2.

    [28]This case mirrors the SourceInterArea2 candidate list
    initialization in Section 12.2.3.

    [29]Note that selecting the upstream node in this manner enforces
    the inter-area routing architecture outlined in Section 3.1. Namely,
    the multicast datagram is forwarded from the source area, over the
    backbone and then into the non-backbone areas. This is similar to
    the "hub and spoke" architecture for unicast forwarding described in
    Section 3.2 of [OSPF].

    [30]This procedure seems backwards. One would expect that the TOS X
    datagram tree would be built first. However, the SPF calculation
    must ensure that all routers participating in the forwarding of that
    datagram, both TOS-capable and non-TOS-capable, build the same tree.
    Since it is known that the non-TOS-capable routers will use the TOS
    0 tree, the only safe way to use the TOS X tree is when you are
    guaranteed that the non-TOS-capable routers will decline to forward
    the datagram. This guarantee is clearly met when there are only
    TOS-capable routers on the TOS 0 datagram tree.

    [31]Indeed, there will also be those cases where the router, not



Moy                                                            [Page 86]

RFC 1584              Multicast Extensions to OSPF            March 1994


    being on a particular datagram shortest-path tree, will never have
    to calculate the particular tree, since the router will not receive
    the datagram in the first place.

    [32]Group-membership-LSAs are not processed by non-multicast routers
    (see Section 10.2). Also, if the Designated Router was not running
    the multicast extensions, multicast datagrams would not be forwarded
    over the network because its network-LSA would have its MC-bit clear
    (see Step 5a in Section 12.2).










































Moy                                                            [Page 87]

RFC 1584              Multicast Extensions to OSPF            March 1994


A. Data Formats

    This section documents the format of MOSPF protocol packets and link
    state advertisements (LSAs). All changes and additions made to the
    OSPF Version 2 data formats have been made in a backward-compatible
    manner. In other words, multicast routers running MOSPF can
    interoperate with (non-multicast) OSPF Version 2 routers when
    forwarding regular (unicast) IP data traffic.

    The MOSPF packet formats are the same as for OSPF Version 2
    (described in Appendix A of [OSPF]). One additional option has been
    added to the Options field that appears in OSPF Hello packets,
    Database Description packets and all link state advertisements. This
    new option indicates a router's/network's multicast capability, and
    is documented in Section A.1.  The presence of this new option is
    ignored by all non-multicast routers.

    To support MOSPF, one of OSPF's link state advertisements has been
    modified, and a new link state advertisement has been added. The
    format of the router-LSA has been modified (see Section A.2) to
    include a new flag indicating whether the router is a wild-card
    multicast receiver. A new link state advertisement, called the
    group-membership-LSA, has been added to pinpoint multicast group
    members in the link state database. This new advertisement is
    neither flooded nor processed by non-multicast routers. The group-
    membership-LSA is documented in Section A.3.

























Moy                                                            [Page 88]

RFC 1584              Multicast Extensions to OSPF            March 1994


A.1 The Options field

    The OSPF Options field is present in OSPF Hello packets, Database
    Description packets and all link state advertisements. The Options
    field enables OSPF routers to support (or not support) optional
    capabilities, and to communicate their capability level to other
    OSPF routers. Through this mechanism routers of differing
    capabilities can be mixed within an OSPF routing domain.

    When used in Hello packets, the Options field allows a router to
    reject a neighbor because of a capability mismatch. Alternatively,
    when capabilities are exchanged in Database Description packets a
    router can choose not to forward certain LSA types to a neighbor
    because of its reduced functionality. Lastly, listing capabilities
    in LSAs allows routers to route traffic around reduced functionality
    routers, by excluding them from parts of the routing table
    calculation.

    Three capabilities are currently defined. For each capability, the
    effect of the capability's appearance (or lack of appearance) in
    Hello packets, Database Description packets and link state
    advertisements is specified below. For example, the
    ExternalRoutingCapability (below called the E-bit) has meaning only
    in OSPF Hello packets.

                     +---+---+---+---+---+---+---+---+
                     | * | * | * | * | * |MC | E | T |
                     +---+---+---+---+---+---+---+-+-+

                          The OSPF Options field


    o   T-bit. This describes the router's TOS capability. If the T-bit
        is reset, then the router supports only a single TOS (TOS 0).
        Such a router is also said to be incapable of TOS-routing. The
        absence of the T-bit in a router links advertisement causes the
        router to be skipped when building a non-zero TOS shortest-path
        tree. In other words, routers incapable of TOS routing will be
        avoided as much as possible when forwarding data traffic
        requesting a non-zero TOS. The absence of the T-bit in a summary
        link advertisement or an AS external link advertisement
        indicates that the advertisement is describing a TOS 0 route
        only (and not routes for non-zero TOS).

    o   E-bit. AS external link advertisements are not flooded
        into/through OSPF stub areas. The E-bit ensures that all members
        of a stub area agree on that area's configuration. The E-bit is
        meaningful only in OSPF Hello packets. When the E-bit is reset



Moy                                                            [Page 89]

RFC 1584              Multicast Extensions to OSPF            March 1994


        in the Hello packet sent out a particular interface, it means
        that the router will neither send nor receive AS external link
        state advertisements on that interface (in other words, the
        interface connects to a stub area). Two routers will not become
        neighbors unless they agree on the state of the E-bit.

    o   MC-bit. The MC-bit describes the multicast capability of the
        various pieces of the OSPF routing domain. When calculating the
        path of multicast datagrams, only those link state
        advertisements having their MC-bit set are used. In addition, a
        router uses the MC-bit in its Database Description packets to
        tell adjacent neighbors whether the router will participate in
        the flooding of the new group-membership-LSAs.






































Moy                                                            [Page 90]

RFC 1584              Multicast Extensions to OSPF            March 1994


A.2 Router-LSA

    An OSPF router originates a router-LSA into each of its attached
    areas. The router-LSA describes the state and cost of the router's
    interfaces to the area. The contents of the router-LSA are described
    in detail in Section A.4.2 of [OSPF]. There are flags in the
    router-LSA that indicate whether the router is either a) an area
    border router or b) an AS boundary router or c) the endpoint of a
    virtual link. One more flag has been added to the router-LSA for
    MOSPF; it is called bit W below. This flag indicates whether the
    router wishes to receive all multicast datagrams regardless of
    destination (i.e., is a wild-card multicast receiver).

        0                   1                   2                   3
        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
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |            LS age             |     Options   |       1       |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                        Link State ID                          |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                     Advertising Router                        |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                     LS sequence number                        |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |         LS checksum           |             length            |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |    rtype      |        0      |            # links            |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +
       |                          Link ID                              | P
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ E
       |                         Link Data                             | R
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |     Type      |     # TOS     |        TOS 0 metric           | #
     + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ L
     # |      TOS      |        0      |            metric             | I
     T +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ N
     O |                              ...                              | K
     S +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ S
     | |      TOS      |        0      |            metric             | |
     + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +
       |                              ...                              |

                                The router LSA








Moy                                                            [Page 91]

RFC 1584              Multicast Extensions to OSPF            March 1994


                     +---+---+---+---+---+---+---+---+
                     | * | * | * | * | W | V | E | B |
                     +---+---+---+---+---+---+---+-+-+

                                The rtype field

    The following defines the flags found in the rtype field. Each flag
    classifies the router by function:

    o   bit B. When set, the router is an area border router (B is for
        border). These routers forward unicast data traffic between OSPF
        areas.

    o   bit E. When set, the router is an AS boundary router (E is for
        external). These routers forward unicast data traffic between
        Autonomous Systems.

    o   bit V. When set, the router is an endpoint of an active virtual
        link (V is for virtual) which uses the described area as its
        Transit area.

    o   bit W. When set, the router is a wild-card multicast receiver.
        These routers receive all multicast datagrams, regardless of
        destination.  Inter-area multicast forwarders and inter-AS
        multicast forwarders are sometimes wild-card multicast receivers
        (see Sections 3 and 4).

























Moy                                                            [Page 92]

RFC 1584              Multicast Extensions to OSPF            March 1994


A.3 Group-membership-LSA

    Group-membership-LSAs are the Type 6 link state advertisements.
    Group-membership-LSAs are specific to a particular OSPF area. They
    are never flooded beyond their area of origination. A router's
    group-membership-LSA for Area A indicates its directly attached
    networks which belong to Area A and contain members of a particular
    multicast group. A router originates a group-membership-LSA for
    multicast group D when the following conditions are met for at least
    one directly attached network: 1) the router has been elected
    Designated Router for the network and 2) at least one host on the
    network has joined Group D via the IGMP protocol.

    A router may also originate a group-membership-LSA for Group D if
    the router itself has internal applications belonging to Group D. In
    addition, area border routers originate group-membership-LSAs into
    the backbone area when there are group members in the router's
    attached non-backbone areas. See Section 10 for more information
    concerning the origination of group-membership-LSAs.

        0                   1                   2                   3
        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
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |            LS age             |     Options   |       6       |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |              Link State ID = Destination Group                |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                     Advertising Router                        |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                     LS sequence number                        |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |         LS checksum           |             length            |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                        Vertex type                            |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                         Vertex ID                             |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                              ...                              |

                           The group-membership-LSA


    The group-membership-LSA consists of the standard 20-byte link state
    header (see Section A.4.1 of [OSPF]) followed by a list of transit
    vertices to label with the multicast destination. The
    advertisement's Link State ID is set to the destination multicast
    group address. There is no metric associated with the advertisement.
    Each transit vertex is specified by its Vertex type and Vertex ID



Moy                                                            [Page 93]

RFC 1584              Multicast Extensions to OSPF            March 1994


    (see Section 12.1 for an explanation of this terminology):

    o   Vertex type. Set equal to 1 for a router, and 2 for a transit
        network.  Note that the only router that may be included in the
        list is the Advertising Router itself.

    o   Vertex ID. For router vertices, this field indicates the
        router's OSPF Router ID. For transit network vertices, this
        field indicates the IP address of the network's Designated
        Router. Note that the link state advertisement associated with
        the transit vertex is the LSA whose LS type = Vertex type, Link
        State ID = Vertex ID and Advertising Router = the group-
        membership-LSA's Advertising Router.






































Moy                                                            [Page 94]

RFC 1584              Multicast Extensions to OSPF            March 1994


B. Configurable Constants

    This section documents the configurable parameters used by OSPF's
    multicast routing extensions. These parameters are in addition to
    the configurable constants used by the base OSPF protocol
    (documented in Appendix C of [OSPF]). An implementation of MOSPF
    must provide the ability to set these parameters, either through
    network management or some other means.

    B.1 Global parameters

        The following parameters apply to the router as a whole.

        o   Multicast capability. An indication of whether the router is
            running MOSPF. If the router is running MOSPF, it will
            perform the algorithms as set forth in this specification.
            Otherwise, the router is still able to run the basic OSPF
            algorithm (as set forth in [OSPF]), and will be able to
            interoperate with multicast capable routers (see Section
            6.1) when forwarding regular (unicast) IP data traffic.

        o   Inter-area multicast forwarder. This parameter indicates
            whether the router will forward multicast datagrams between
            OSPF areas. Such a router summarizes group membership
            information to the backbone, and acts as a wild-card
            multicast receiver in all its attached non-backbone areas
            (see Section 3.1). Not all multicast-capable area border
            routers need be configured as inter-area multicast
            forwarders.  However, whenever both ends of a virtual link
            are multicast-capable, they must both be configured as
            inter-area multicast forwarders (see Section 14.11). By
            default, all multicast-capable area border routers are
            configured as inter-area multicast forwarders.

        o   Inter-AS multicast forwarder. This parameter indicates
            whether the router forwards multicast datagrams between
            Autonomous Systems. Such a router acts as a wild-card
            multicast receiver in all attached areas (see Section 4). It
            is also assumed that an inter-AS multicast forwarder runs
            some kind of inter-AS multicast routing algorithm.

    B.2 Router interface parameters

        The following parameters can be configured separately for each
        of the router's OSPF interfaces. Remember that an OSPF interface
        is the connection between the router and one of its attached IP
        networks.  Note that the IPMulticastForwarding parameter is
        really a description of the attached network. As such, it should



Moy                                                            [Page 95]

RFC 1584              Multicast Extensions to OSPF            March 1994


        be configured identically on all routers attached to a common
        network; otherwise incorrect routing of multicast datagrams may
        result.

        o   IPMulticastForwarding. This configurable parameter indicates
            whether IP multicasts should be forwarded over the attached
            network, and if so, how the forwarding should be done. The
            parameter can assume one of three possible values: disabled,
            data-link multicast and data-link unicast. When set to
            disabled, IP multicast datagrams will not be forwarded out
            the interface. When set to data-link multicast, IP multicast
            datagrams will be forwarded as data-link multicasts. When
            set to data-link unicast, IP multicast datagrams will be
            forwarded as data-link unicasts. The default value for this
            parameter is data-link multicast. The other two settings are
            for use in the special circumstances described in Sections
            6.3 and 6.4. When set to disabled or to data-link unicast,
            IGMP group membership is not monitored on the attached
            network.

        o   IGMPPollingInterval. The number of seconds between IGMP Host
            Membership Queries sent out this interface. A multicast-
            capable router sends IGMP Host Membership Queries only when
            it has been elected Designated Router for the attached
            network. See [RFC 1112] for a discussion of this parameter's
            value.

        o   IGMP timeout. If no IGMP Host Membership Reports have been
            heard on an attached network for a particular multicast
            group A after this period of time, the entry [Group A,
            attached network] is deleted from the router's local group
            database. See Section 9 for more information.



















Moy                                                            [Page 96]

RFC 1584              Multicast Extensions to OSPF            March 1994


C. Sample datagram shortest-path trees

    In MOSPF, all routers must calculate exactly the same datagram
    shortest-path trees. In order to ensure this in internetworks having
    redundant links, a number of tie-breakers were defined in the MOSPF
    routing table calculation (see Steps 4 and 5c of Section 12.2, and
    Sections 12.2.4 and 12.2.7). This section illustrates the use of
    these tie-breakers on a sample topology.

    Three different examples are given. All examples use the same
    physical topology and the same set of OSPF interface costs (see the
    left side of Figure 14). The source of the datagram is always Host
    H1 on the network at the top of the figure (192.9.1.0), and the
    destination group members are the two hosts labelled with Group Ma
    at the bottom of the figure. The first case shows an example of
    intra-area multicast, while the remaining two cases show the
    influence of OSPF areas on the path of a multicast datagram.


































Moy                                                            [Page 97]

RFC 1584              Multicast Extensions to OSPF            March 1994


C.1 An intra-area tree

    The datagram shortest-path tree resulting from the intra-area case
    is shown on the right of Figure 14. The root of the tree is the
    source network (192.9.1.0), and the leaves are the two routers (RT4
    and RT3) directly attached to the stub networks containing Group Ma
    members.

    There are equal-cost paths available to both group members. For the
    group member on the left, the path could go either through network
    10.1.0.0 or through network 10.2.0.0. By the tie-breaking rules, the
    path through 10.2.0.0 is chosen since it has the larger IP network
    number (see Step 5c of Section 12.2).

    For the group member on the right, the path could go either over
    Network 10.2.0.0 or over the serial line connecting routers RT2 and
    RT3. The path over Network 10.2.0.0 is chosen after executing two
    tie-breaking rules. First, Network 10.2.0.0 is placed on the
    shortest-path tree before Router RT3 since networks are always
    chosen over routers (see Step 4 of Section 12.2). Then, given a

                                 +--+
                                 |H1|
                                 +--+
                    Net 192.9.1.0  |
                         +------------------+
                            |            |
        +----------+        |1           |1
        |  Network |     8+---+        +---+            o 192.9.1.0
        | 10.1.0.0 |------|RT1|        |RT2|            |
        +----------+      +---+        +---+           0|
             |              |8          8|              |
            8|         +----------+      |8             o RT1
           +---+10     | Network  |  10+---+            |
           |RT4|-------| 10.2.0.0 |----|RT3|           8|
           +---+       +----------+    +---+            |
             |3                          |3             o 10.2.0.0
             |                           |             / \
        +---------+                  +-------+       0/   \0
             |                           |           /     \
           +--+                        +--+         o       o
           |Ma|                        |Ma|        RT4      RT3
           +--+                        +--+


                        Figure 14: An intra-area tree





Moy                                                            [Page 98]

RFC 1584              Multicast Extensions to OSPF            March 1994


    choice of either Network 10.2.0.0 or Router RT2 for RT3's parent on
    the tree, Net 10.2.0.0 is again preferred since it is a network (see
    Step 5c of Section 12.2)
















































Moy                                                            [Page 99]

RFC 1584              Multicast Extensions to OSPF            March 1994


C.2 The effect of areas

    In Figure 15 below, the previous diagram has been modified by the
    inclusion of OSPF areas. The datagram source is now part of the OSPF
    backbone (Area 0), while the rest of the topology is in Area 1. In
    this case, since the datagram source and the group members belong to
    different areas, reverse costs are used when building the tree (see
    Step 5b of Section 12.2). This actually eliminates the equal cost
    paths from the diagram, and leads to the Area 1 datagram shortest-
    path tree on the right of Figure 15.











                                 +--+
                                 |H1|
                                 +--+
                    Net 192.9.1.0  |
                         +------------------+
      ..................... |            |
      . +----------+      . |1           |1            192.9.1.0
      . |  Network |     8+---+        +---+                o
      . | 10.1.0.0 |------|RT1|........|RT2|...            / \
      . +----------+      +---+        +---+  .          1/   \1
      .      |              |8          8|    .          /     \
      .     8|         +----------+      |8   .         o RT1   o RT2
      .    +---+10     | Network  |  10+---+  .         |        \
      .    |RT4|-------| 10.2.0.0 |----|RT3|  .        0|         \8
      .    +---+       +----------+    +---+  .         |          \
      .      |3                          |3   .         o 10.1.0.0  o
      .      |                           |    .         |          RT3
      . +---------+                  +-------+.        8|
      .      |                           |    .         |
      .    +--+                        +--+   .         o
      .    |Ma|                        |Ma|   .        RT4
      .    +--+     Area 1             +--+   .
      .........................................

                        Figure 15: The effect of areas





Moy                                                           [Page 100]

RFC 1584              Multicast Extensions to OSPF            March 1994


C.3 The effect of virtual links

    In Figure 16 below, Network 10.1.0.0 has been configured as a
    separate area (Area 1), while everything else belongs to the OSPF
    backbone (Area 0). In addition, a virtual link has been configured
    through Area 1, enhancing the backbone connectivity. In this case,
    both the source and the group members belong to the same area, so
    forward costs are used. However, since virtual links are preferred
    over regular links (see Step 5c of Section 12.2), the backbone
    datagram shortest-path tree uses Network 10.1.0.0 instead of
    10.2.0.0 on the path to the left group member. This leads to the
    tree on the right of Figure 16.









                                 +--+
                                 |H1|
                                 +--+
                    Net 192.9.1.0  |
      ................   +------------------+
      . +----------+ .     /1            |
      . |  Network |8.    /              |1
      . | 10.1.0.0 |-+---+             +---+            o 192.9.1.0
      . +----------+*|RT1|             |RT2|            |
      .     8|*******+---+             +---+           0|
      .Area1 |*VL    .    \8            8|              |
      .....+---+...... +----------+      |8             o RT1
           |RT4|10     | Network  |  10+---+           / \
           +---+-------| 10.2.0.0 |----|RT3|          /8  \8
             |         +----------+    +---+         /     \
             |3                          |3         o 10.1  o 10.2.0.0
             |                           |          |       |
        +---------+                  +-------+      |0      |0
             |                           |          |       |
           +--+                        +--+         o       o
           |Ma|                        |Ma|        RT4      RT3
           +--+                        +--+


                   Figure 16: The effect of virtual links





Moy                                                           [Page 101]

RFC 1584              Multicast Extensions to OSPF            March 1994


Security Considerations

    Security issues are not discussed in this memo.

Author's Address

    John Moy
    Proteon, Inc.
    9 Technology Drive
    Westborough, MA 01581
    Phone: (508) 898-2800
    Email: jmoy@proteon.com







































Moy                                                           [Page 102]