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
|
Network Working Working Group R. Callon
Request for Comments: 1195 Digital Equipment Corporation
December 1990
Use of OSI IS-IS for Routing in TCP/IP and Dual Environments
Status of this Memo
This RFC specifies a protocol on the IAB Standards Track for the
Internet community, and requests discussion and suggestions for
improvements. Please refer to the current edition of the "IAB
Official Protocol Standards" for the standardization state and status
of this protocol. Distribution of this memo is unlimited.
This RFC is available in both postscript and text versions. Where
possible, use of the postscript version is recommended. For example,
this text version may have figures which are less informative or
missing.
Abstract
This RFC specifies an integrated routing protocol, based on the OSI
Intra-Domain IS-IS Routing Protocol, which may be used as an interior
gateway protocol (IGP) to support TCP/IP as well as OSI. This allows
a single routing protocol to be used to support pure IP environments,
pure OSI environments, and dual environments. This specification was
developed by the IS-IS working group of the Internet Engineering Task
Force.
The OSI IS-IS protocol has reached a mature state, and is ready for
implementation and operational use. The most recent version of the
OSI IS-IS protocol is contained in ISO DP 10589 [1]. The proposed
standard for using IS-IS for support of TCP/IP will therefore make
use of this version (with a minor bug correction, as discussed in
Annex B). We expect that future versions of this proposed standard
will upgrade to the final International Standard version of IS-IS
when available.
Comments should be sent to "isis@merit.edu".
Contents
1 Introduction: Overview of the Protocol
1.1 What the Integrated IS-IS offers
1.2 Overview of the ISO IS-IS Protocol
1.3 Overview of the Integrated IS-IS
1.4 Support of Mixed Routing Domains
Callon [Page 1]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
1.5 Advantages of Using Integrated IS-IS
2 Symbols and Abbreviations
3 Subnetwork Independent Functions
3.1 Exchange of Routing Information
3.2 Hierarchical Abbreviation of IP Reachability Information
3.3 Addressing Routers in IS-IS Packets
3.4 External Links
3.5 Type of Service Routing
3.6 Multiple LSPs and SNPs
3.7 IP-Only Operation
3.8 Encapsulation
3.9 Authentication
3.10 Order of Preference of Routes / Dijkstra Computation
4 Subnetwork Dependent Functions
4.1 Link Demultiplexing
4.2 Multiple IP Addresses per Interface
4.3 LANs, Designated Routers, and Pseudonodes
4.4 Maintaining Router Adjacencies
4.5 Forwarding to Incompatible Routers
5 Structure and Encoding of PDUs
5.1 Overview of IS-IS PDUs
5.2 Overview of IP-Specific Information for IS-IS
5.3 Encoding of IP-Specific Fields in IS-IS PDUs
6 Security Considerations
7 Author's Address
8 References
A Inter-Domain Routing Protocol Information
A.1 Inter-Domain Information Type
A.2 Encoding
B Encoding of Sequence Number Packets
B.1 Level 1 Complete Sequence Numbers PDU
B.2 Level 2 Complete Sequence Numbers PDU
B.3 Level 1 Partial Sequence Numbers PDU
B.4 Level 2 Partial Sequence Numbers PDU
C Dijkstra Calculation and Forwarding
C.1 SPF Algorithm for IP and Dual Use
C.2 Forwarding of IP packets
Callon [Page 2]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
D Use of the Authentication Field
D.1 Authentication Field in IS-IS packets
D.2 Authentication Type 1 - Simple Password
E Interaction of the Integrated IS-IS with Brouters
E.1 The Problem
E.2 Possible Solutions
Figures
1 ISO Hierarchical Address Structure
2 An Example
3 Encoding of Variable Length Fields
1 Introduction: Overview of the Protocol
The TCP/IP protocol suite has been growing in importance as a multi-
vendor communications architecture. With the anticipated emergence of
OSI, we expect coexistence of TCP/IP and OSI to continue for an
extended period of time. There is a critical need for routers to
support both IP traffic and OSI traffic in parallel.
There are two main methods that are available for routing protocols
to support dual OSI and IP routers. One method, known as "Ships in
the Night", makes use of completely independent routing protocols for
each of the two protocol suites. This specification presents an
alternate approach, which makes use of a single integrated protocol
for interior routing (i.e., for calculating routes within a routing
domain) for both protocol suites.
This integrated protocol design is based on the OSI Intra-domain IS-
IS routing protocol [1], with IP-specific functions added. This RFC
is considered a companion to the OSI IS-IS Routing spec, and will
only describe the required additional features.
By supporting both IP and OSI traffic, this integrated protocol
design supports traffic to IP hosts, OSI end systems, and dual end
systems. This approach is "integrated" in the sense that the IS-IS
protocol can be used to support pure-IP environments, pure-OSI
environments, and dual environments. In addition, this approach
allows interconnection of dual (IP and OSI) routing domains with
other dual domains, with IP-only domains, and with OSI-only domains.
The protocol specified here is based on the work of the IETF IS-IS
working group.
1.1 What the Integrated IS-IS offers
The integrated IS-IS provides a single routing protocol which will
Callon [Page 3]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
simultaneously provide an efficient routing protocol for TCP/IP, and
for OSI. This design makes use of the OSI IS-IS routing protocol,
augmented with IP-specific information. This design provides explicit
support for IP subnetting, variable subnet masks, TOS-based routing,
and external routing. There is provision for authentication
information, including the use of passwords or other mechanisms. The
precise form of authentication mechanisms (other than passwords) is
outside of the scope of this document.
Both OSI and IP packets are forwarded "as is" -- i.e., they are
transmitted directly over the underlying link layer services without
the need for mutual encapsulation. The integrated IS-IS is a dynamic
routing protocol, based on the SPF (Dijkstra) routing algorithm.
The protocol described in this specification allows for mixing of
IP-only, OSI-only, and dual (IP and OSI) routers, as defined below.
An IP-only IS-IS router (or "IP-only" router) is defined to be a
router which: (i) Uses IS-IS as the routing protocol for IP, as
specified in this report; and (ii) Does not otherwise support OSI
protocols. For example, such routers would not be able to forward OSI
CLNP packets.
An OSI-only router is defined to be a router which uses IS-IS as the
routing protocol for OSI, as specified in [1]. Generally, OSI-only
routers may be expected to conform to OSI standards, and may be
implemented independent of this specification.
A dual IS-IS router (or "dual" router) is defined to be a router
which uses IS-IS as a single integrated routing protocol for both IP
and OSI, as specified in this report.
This approach does not change the way that IP packets are handled.
IP-only and dual routers are required to conform to the requirements
of Internet Gateways [4]. The integrated IS-IS protocol described in
this report outlines an Interior Gateway Protocol (IGP) which will
provide routing within a TCP/IP routing domain (i.e., autonomous
system). Other aspects of router functionality (e.g., operation of
ICMP, ARP, EGP, etc.) are not affected by this proposal.
Similarly, this approach does not change the way that OSI packets are
handled. There will be no change at all to the contents nor to the
handling of ISO 8473 Data packets and Error Reports, nor to ISO 9542
Redirects and ES Hellos. ISO 9542 IS Hellos transmitted on LANs are
similarly unchanged. ISO 9542 IS Hellos transmitted on point-to-point
links are unchanged except for the addition of IP-related
information. Similarly, other OSI packets (specifically those
involved in the IS-IS intra-domain routing protocol) remain unchanged
Callon [Page 4]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
except for the addition of IP-related information.
This approach makes use of the existing IS-IS packets, with IP-
specific fields added. Specifically: (i) authentication information
may be added to all IS-IS packets; (ii) the protocols supported by
each router, as well as each router's IP addresses, are specified in
ISO 9542 IS Hello, IS-IS Hello and Link State Packets; (iii)
internally reachable IP addresses are specified in all Link State
Packets; and (iv) externally reachable IP addresses, and external
routing protocol information, may be specified in level 2 Link State
Packets. The detailed encoding and interpretation of this in
formation is specified in sections 3, 4, and 5 of this RFC.
The protocol described in this report may be used to provide routing
in an IP-only routing domain, in which all routers are IP-only.
Similarly, this protocol may be used to provide routing in a pure
dual domain, in which all routers are dual. Finally, this protocol
may be used to provide routing in a mixed domain, in which some
routers are IP-only, some routers are OSI-only, and some routers are
dual. The specific topological restrictions which apply in this
latter case are described in detail in section 1.4 ("Support of Mixed
Routing Domains"). The use of IS-IS for support of pure OSI domains
is specified in [1].
This protocol specification does not constrain which network
management protocol(s) may be used to manage IS-IS-based routers.
Management information bases (MIBs) for managing IP-only, OSI-only,
and dual routers, compatible with CMIP, CMOT, and/or SNMP, are the
subject of a separate, companion document [8].
1.2 Overview of the ISO IS-IS Protocol
The IS-IS Routing Protocol has been developed in ISO to provide
routing for pure OSI environments. In particular, IS-IS is designed
to work in conjunction with ISO 8473 (The ISO Connectionless Network
Layer Protocol [2]), and ISO 9542 (The ISO End System to Intermediate
System Protocol [3]). This section briefly describes the manner in
which IS-IS is used to support pure OSI environments. Enhancements
for support of IP and dual environments are specified elsewhere in
this report.
In IS-IS, the network is partitioned into "routing domains". The
boundaries of routing domains are defined by network management, by
setting some links to be "exterior links". If a link is marked as
"exterior", no IS-IS routing messages are sent on that link.
Currently, ISO does not have a standard for inter-domain routing
(i.e., for routing between separate autonomous routing domains).
Callon [Page 5]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
Instead, manual configuration is used. The link is statically
configured with the set of address prefixes reachable via that link,
and with the method by which they can be reached (such as the DTE
address to be dialed to reach that address, or the fact that the DTE
address should be extracted from the IDP portion of the ISO address).
OSI IS-IS routing makes use of two-level hierarchical routing. A
routing domain is partitioned into areas. Level 1 routers know the
topology in their area, including all routers and end systems in
their area. However, level 1 routers do not know the identity of
routers or destinations outside of their area. Level 1 routers
forward all traffic for destinations outside of their area to a level
2 router in their area. Similarly, level 2 routers know the level 2
topology, and know which addresses are reachable via each level 2
router. However, level 2 routers do not need to know the topology
within any level 1 area, except to the extent that a level 2 router
may also be a level 1 router within a single area. Only level 2
routers can exchange data packets or routing information directly
with external routers located outside of the routing domains.
+----------------------+-------------------------------+
| IDP | DSP |
+----------------------+-------------------------------+
. . .
. . .
. . .
+-----+----------------+----------+--------------+-----+
| AFI | IDI | HO-DSP | ID | SEL |
+-----+----------------+----------+--------------+-----+
Figure 1 - ISO Hierarchical Address Structure
As illustrated in figure 1, ISO addresses are subdivided into the
Initial Domain Part (IDP), and the Domain Specific Part (DSP). The
IDP is the part which is standardized by ISO, and specifies the
format and authority responsible for assigning the rest of the
address. The DSP is assigned by whatever addressing authority is
specified by the IDP. The DSP is further subdivided into a "High
Order Part of DSP" (HO-DSP), a system identifier (ID), and an NSAP
selector (SEL). The HO-DSP may use any format desired by the
authority which is identified by the IDP. Together, the combination
of [IDP, HO-DSP] identify both the routing domain and the area within
the routing domain. The combination of [IDP,HO-DSP] may therefore be
referred to as the "Area Address".
Usually, all nodes in an area have the same area address. However,
sometimes an area might have multiple addresses. Motivations for
Callon [Page 6]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
allowing this are:
- It might be desirable to change the address of an area. The most
graceful way of changing an area from having address A to having
address B is to first allow it to have both addresses A and B, and
then after all nodes in the area have been modified to recognize
both addresses, then one by one the nodes can be modified to
"forget" address A.
- It might be desirable to merge areas A and B into one area. The
method for accomplishing this is to, one by one, add knowledge of
address B into the A partition, and similarly add knowledge of
address A into the B partition.
- It might be desirable to partition an area C into two areas, A
and B (where "A" might equal "C", in which case this example
becomes one of removing a portion of an area). This would be
accomplished by first introducing knowledge of address A into
the appropriate nodes (those destined to become area A), and
knowledge of address B into the appropriate nodes, and then one
by one removing knowledge of address C.
Since OSI addressing explicitly identifies the area, it is very easy
for level 1 routers to identify packets going to destinations outside
of their area, which need to be forwarded to level 2 routers.
In IS-IS, there are two types of routers:
- Level 1 intermediate systems -- these nodes route based on the ID
portion of the ISO address. They route within an area. They
recognize, based on the destination address in a packet, whether
the destination is within the area. If so, they route towards
the destination. If not, they route to the nearest level 2 router.
- Level 2 intermediate systems -- these nodes route based on the area
address (i.e., on the combination of [IDP, HO-DSP]). They route
towards areas, without regard to the internal structure of an area.
A level 2 IS may also be a level 1 IS in one area.
A level 1 router will have the area portion of its address manually
configured. It will refuse to become a neighbor with a node whose
area addresses do not overlap its area addresses. However, if level 1
router has area addresses A, B, and C, and a neighbor has area
addresses B and D, then the level 1 router will accept the other node
as a neighbor.
A level 2 router will accept another level 2 router as a neighbor,
regardless of area address. However, if the area addresses do not
Callon [Page 7]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
overlap, the link would be considered by both routers to be "level 2
only", and only level 2 LSPs would flow on the link. External links
(to other routing domains) must be from level 2 routers.
IS-IS provides an optional partition repair function. In the unlikely
case that a level 1 area become partitioned, this function, if
implemented, allows the partition to be repaired via use of level 2
routes.
IS-IS requires that the set of level 2 routers be connected. Should
the level 2 backbone become partitioned, there is no provision for
use of level 1 links to repair a level 2 partition.
In unusual cases, a single level 2 router may lose connectivity to
the level 2 backbone. In this case the level 2 router will indicate
in its level 1 LSPs that it is not "attached", thereby allowing level
1 routers in the area to route traffic for outside of the domain to a
different level 2 router. Level 1 routers therefore route traffic to
destinations outside of their area only to level 2 routers which
indicate in their level 1 LSPs that they are "attached".
An end system may autoconfigure the area portion of its address by
extracting the area portion of a neighboring router's address. If
this is the case, then an endnode will always accept a router as a
neighbor. Since the standard does not specify that the end system
MUST autoconfigure its area address, an end system may be configured
with an area address. In this case the end system would ignore router
neighbors with non-matching area addresses.
Special treatment is necessary for broadcast subnetworks, such as
LANs. This solves two sets of issues: (i) In the absence of special
treatment, each router on the subnetwork would announce a link to
every other router on the subnetwork, resulting in n-squared links
reported; (ii) Again, in the absence of special treatment, each
router on the LAN would report the same identical list of end systems
on the LAN, resulting in substantial duplication.
These problems are avoided by use of a "pseudonode", which represents
the LAN. Each router on the LAN reports that it has a link to the
pseudonode (rather than reporting a link to every other router on the
LAN). One of the routers on the LAN is elected "designated router".
The designated router then sends out an LSP on behalf of the
pseudonode, reporting links to all of the routers on the LAN. This
reduces the potential n-squared links to n links. In addition, only
the pseudonode LSP includes the list of end systems on the LAN,
thereby eliminating the potential duplication (for further
information on designated routers and pseudonodes, see [1]).
Callon [Page 8]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
The IS-IS provides for optional Quality of Service (QOS) routing,
based on throughput (the default metric), delay, expense, or residual
error probability. This is described in greater detail in section
3.5, and in [1].
1.3 Overview of the Integrated IS-IS
The integrated IS-IS allows a single routing protocol to be used to
route both IP and OSI packets. This implies that the same two-level
hierarchy will be used for both IP and OSI routing. Each area will be
specified to be either IP-only (only IP traffic can be routed in that
particular area), OSI-only (only OSI traffic can be routed in that
area), or dual (both IP and OSI traffic can be routed in the area).
This proposal does not allow for partial overlap of OSI and IP areas.
For example, if one area is OSI-only, and an other area is IP-only,
then it is not permissible to have some routers be in both areas.
Similarly, a single backbone is used for the routing domain. There is
no provision for independent OSI and IP backbones.
Similarly, within an IP-only or dual area, the amount of knowledge
maintained by routers about specific IP destinations will be as
similar as possible as for OSI. For example, IP-capable level 1
routers will maintain the topology within the area, and will be able
to route directly to IP destinations within the area. However, IP-
capable level 1 routers will not maintain information about
destinations outside of the area. Just as in normal OSI routing,
traffic to destinations outside of the area will be forwarded to the
nearest level 2 router. Since IP routes to subnets, rather than to
specific end systems, IP routers will not need to keep nor distribute
lists of IP host identifiers (note that routes to hosts can be
announced by using a subnet mask of all ones).
The IP address structure allows networks to be partitioned into
subnets, and allows subnets to be recursively subdivided into smaller
subnets. However, it is undesireable to require any specific
relationship between IP subnet addresses and IS-IS areas. For
example, in many cases, the dual routers may be installed into
existing environments, which already have assigned IP and/or OSI
addresses. In addition, even if IP addresses are not already pre-
assigned, the address limitations of IP constrain what addresses may
be assigned. We therefore will not require any specific relationship
between IP addresses and the area structure. The IP addresses can be
assigned completely independently of the OSI addresses and IS-IS area
structure. As will be described in section 3.2 ("Hierarchical
Abbreviation of IP Reachability Information"), greater efficiency and
scaling of the routing algorithm can be achieved if there is some
correspondence between the IP address assignment structure and the
Callon [Page 9]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
area structure.
Within an area, level 1 routers exchange link state packets which
identify the IP addresses reachable by each router. Specifically,
zero or more [IP address, subnet mask, metric] combinations may be
included in each Link State Packet. Each level 1 router is manually
configured with the [IP address, subnet mask, metric] combinations
which are reachable on each interface. A level 1 router routes as
follows:
- If a specified destination address matches an [IP address, subnet
mask, metric] reachable within the area, the packet is routed via
level 1 routing.
- If a specified destination address does not match any [IP address,
subnet mask, metric] combination listed as reachable within the
area, the packet is routed towards the nearest level 2 router.
Flexible use of the limited IP address space is important in order to
cope with the anticipated growth of IP environments. Thus an area
(and by implication a routing domain) may simultaneously make use of
a variety of different address masks for different subnets in the
area (or domain). Generally, if a specified destination address
matches more than one [IP address, subnet mask] pair, the more
specific address is the one routed towards (the one with more "1"
bits in the mask -- this is known as "best match" routing).
Level 2 routers include in their level 2 LSPs a complete list of [IP
address, subnet mask, metric] specifying all IP addresses reachable
in their area. As described in section 3, this information may be
obtained from a combination of the level 1 LSPs (obtained from level
1 routers in the same area), and/or by manual configuration. In
addition, Level 2 routers may report external reachability
information, corresponding to addresses which can be reached via
routers in other routing domains (autonomous systems)
Default routes may be announced by use of a subnet mask containing
all zeroes. Default routes should be used with great care, since they
can result in "black holes". Default routes are permitted only at
level 2 as external routes (i.e., included in the "IP External
Reachability Information" field, as explained in sections 3 and 5).
Default routes are not permitted at level 1.
The integrated IS-IS provides optional Type of Service (TOS) routing,
through use of the QOS feature from IS-IS.
Callon [Page 10]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
1.4 Support of Mixed Routing Domains
The integrated IS-IS proposal specifically allows for three types of
routing domains:
- Pure IP
- Pure OSI
- Dual
In a pure IP routing domain, all routers must be IP-capable. IP-only
routers may be freely mixed with dual routers. Some fields
specifically related to OSI operation may be included by dual
routers, and will be ignored by IP-only routers. Only IP traffic will
be routed in an pure IP domain. Any OSI traffic may be discarded
(except for the IS-IS packets necessary for operation of the routing
protocol).
In a pure OSI routing domain, all routers must be OSI-capable. OSI-
only routers may be freely mixed with dual routers. Some fields
specifically related to IP operation may be included by dual routers,
and will be ignored by OSI-only routers. Only OSI traffic will be
routed in a pure OSI domain. Any IP traffic may be discarded.
In a dual routing domain, IP-only, OSI-only, and dual routers may be
mixed on a per-area basis. Specifically, each area may itself be
defined to be pure IP, pure OSI, or dual.
In a pure IP area within a dual domain, IP-only and dual routers may
be freely mixed. Only IP traffic can be routed by level 1 routing
within a pure-IP area.
In a pure-OSI area within a dual domain, OSI-only and dual routers
may be freely mixed. Only OSI traffic can be routed by level 1
routing within a pure OSI area.
In a dual area within a dual routing domain only dual routers may be
used. Both IP and OSI traffic can be routed within a dual area.
Within a dual domain, if both IP and OSI traffic are to be routed
between areas then all level 2 routers must be dual.
1.5 Advantages of Using Integrated IS-IS
Use of the integrated IS-IS protocol, as a single protocol for
routing both IP and OSI packets in a dual environment, has
significant advantages over using separate protocols for
Callon [Page 11]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
independently routing IP and OSI traffic.
An alternative approach is known as "Ships In the Night" (S.I.N.).
With the S.I.N. approach, completely separate routing protocols are
used for IP and for OSI. For example, OSPF [5] may be used for
routing IP traffic, and IS-IS [1] may be used for routing OSI
traffic. With S.I.N., the two routing protocols operate more or less
independently. However, dual routers will need to implement both
routing protocols, and therefore there will be some degree of
competition for resources.
Note that S.I.N. and the integrated IS-IS approach are not really
completely separate options. In particular, if the integrated IS-IS
is used within a routing domain for routing of IP and OSI traffic, it
is still possible to use other independent routing protocols for
routing other protocol suites.
In the future, optional extensions to IS-IS may be defined for
routing other common protocol suites. However, such future options
are outside of the scope of this document. This section will compare
integrated IS-IS and S.I.N. for routing of IP and OSI only.
A primary advantage of the integrated IS-IS relates to the network
management effort required. Since the integrated IS-IS provides a
single routing protocol, within a single coordinated routing domain
using a single backbone, this implies that there is less information
to configure. This combined with a single coordinated MIB simplifies
network management.
Note that the operation of two routing protocols with the S.I.N.
approach are not really independent, since they must share common
resources. However, with the integrated IS-IS, the interactions are
explicit, whereas with S.I.N., the interactions are implicit. Since
the interactions are explicit, again it may be easier to manage and
debug dual routers.
Another advantage of the integrated IS-IS is that, since it requires
only one routing protocol, it uses fewer resources. In particular,
less implementation resources are needed (since only one protocol
needs to be implemented), less CPU and memory resources are used in
the router (since only one protocol needs to be run), and less
network resources are used (since only one set of routing packets
need to be transmitted). Primarily this translates into a financial
savings, since each of these three types of resources cost money.
This implies that dual routers based on the integrated IS-IS should
be less expensive to purchase and operate than dual routers based on
S.I.N.
Callon [Page 12]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
Note that the operation of two routing protocols with the S.I.N.
approach are not really independent, since they must share common
resources. For example, if one routing protocol becomes unstable and
starts to use excessive resources, the other protocol is likely to
suffer. A bug in one protocol could crash the other. However, with
the integrated IS-IS, the interactions are explicit and are defined
into the protocol and software interactions. With S.I.N., the
interactions are implicit.
The use of a single integrated routing protocol similarly reduces the
likely frequency of software upgrades. Specifically, if you have two
different routing protocols in your router, then you have to upgrade
the software any time EITHER of the protocols change. If you make use
of a single integrated routing protocol, then software changes are
still likely to be needed, but less frequently.
Finally, routing protocols have significant real time requirements.
In IS-IS, these real time requirements have been explicitly
specified. In other routing protocols, these requirements are
implicit. However, in all routing protocols, there are real time
guarantees which must be met in order to ensure correct operation. In
general, it is difficult enough to ensure compliance with real time
requirements in the implementation of a single real time system. With
S.I.N., implementation of two semi-independent real-time protocols in
a single device makes this more difficult.
Note that both integrated IS-IS and S.I.N. allow for independence of
external routes (for traffic from/to outside of the routing domain),
and allow for independent assignment of OSI and TCP/IP addresses.
2 Symbols and Abbreviations
AA Administrative Authority
(a three octet field in the GOSIP version 2.0 NSAP
address format)
AFI Authority and Format Identifier
(the first octet of all OSI NSAP addresses -- identifies
format of the rest of the address)
CLNP Connection-Less Network Protocol
(ISO 8473, the OSI connectionless network layer protocol
-- very similar to IP)
DFI DSP Format Identifier
(a one octet field in the GOSIP version 2.0 NSAP address
format)
Callon [Page 13]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
ES End System
(The OSI term for a host)
ES-IS End System to Intermediate System Routeing Exchange
Protocol (ISO 9542 -- OSI protocol between routers
and end systems)
ICD International Code Designator
(ISO standard for identifying organizations)
IP Internetwork Protocol
(an Internet Standard Network Layer Protocol)
IS Intermediate System
(The OSI term for a router)
IS-IS Intermediate System to Intermediate System Routeing
Exchange Protocol
(the ISO protocol for routing within a single
routing domain)
IS-IS Hello An Hello packet defined by the IS-IS protocol
(a type of packet used by the IS-IS protocol)
ISH An Hello packet defined by ISO 9542 (ES-IS protocol).
(not the same as IS-IS Hello)
ISO International Organization for Standardization
(an international body which is authorized to write
standards of many kinds)
LSP Link State Packet
(a type of packet used by the IS-IS protocol)
NLPID Network Layer Protocol ID
(A one-octet field identifying a network layer protocol)
NSAP Network Service Access Point
(a conceptual interface point at which the network
service is made available)
SEL NSAP Selector
(the last octet of NSAP addresses, also called NSEL)
OSI Open Systems Interconnection
(an international standard protocol architecture)
Callon [Page 14]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
RD Routing Domain
(the set of routers and end systems using a single
instance of a routing protocol such as IS-IS)
SNPA Subnetwork Point of Attachment
(a conceptual interface at which a subnetwork service
is provided)
TCP Transmission Control Protocol
(an Internet Standard Transport Layer Protocol)
TCP/IP The protocol suite based on TCP, IP, and related
protocols (the Internet standard protocol
architecture)
3 Subnetwork Independent Functions
3.1 Exchange of Routing Information
The exchange of routing information between routers makes use of the
normal routing packet exchange as defined in the OSI IS-IS routing
spec, with additional IP-specific information added to the IS-IS
routing packets.
The IS-IS protocol provides for the inclusion of variable length
fields in all IS-IS packets. These fields are encoded using a "Code,
Length, Value" triplet, where the code and length are encoded in one
octet each, and the value has the length specified (from 0 to 254
octets). IS-IS requires that: "Any codes in a received PDU that are
not recognised are ignored and passed through unchanged". This
requirement applies to all routers implementing IS-IS, including
OSI-only, IP-only, and dual routers. This allows IP-specific
information to be encoded in a manner which OSI-only routers will
ignore, and also allows OSI-specific information to be encoded in a
manner which IP-only routers will ignore.
IP-capable (i.e., all IP-only and dual) routers need to know what
network layer protocols are supported by other routers in their area.
This information is made available by inclusion of a "protocols
supported" field in all IS-IS Hello and Link State Packets. This
field makes use of the NLPID (Network Layer Protocol Identifier),
which is a one-octet value assigned by ISO to identify network level
protocols. NLPID values have been assigned to ISO 8473 and to IP.
IP-capable routers need to know the IP address of the adjacent
interface of neighboring routers. This is required for sending ICMP
redirects (when an IP-capable router sends an ICMP redirect to a
host, it must include the IP address of the appropriate interface of
Callon [Page 15]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
the correct next-hop router). This information is made available by
inclusion of the IP interface address in the IS-IS Hello packets.
Specifically, each IS-IS Hello packet contains the IP address(es) of
the interface over which the Hello is transmitted. The IS-IS allows
multiple IP addresses to be assigned to each physical interface.
In some cases, it will be useful for IP-capable routers to be able to
determine an IP address(es) of all other routers at their level
(i.e., for level 1 routers: all other routers in their area; for
level 2 routers: all other level 2 routers in the routing domain).
This is useful whenever an IP packet is to be sent to a router, such
as for encapsulation or for transmission of network management
packets. This information is made available by inclusion of IP
address in LSPs. Specifically, each IS-IS LSP includes one or more IP
addresses of the router which transmits the LSP. An IP-capable router
is required to include at least one of its IP addresses in its LSPs,
and may optionally include several or all of its IP addresses. Where
a single router operates as both a level 1 and a level 2 router, it
is required to include the same IP address(es) in its level 1 and
level 2 LSPs.
IP-capable routers need to know, for any given IP destination
address, the correct route to that destination. Specifically, level 1
routers need to know what IP addresses are reachable from each level
1 router in their area. In addition, level 1 routers need to find
level 2 routers (for traffic to IP addresses outside of their area).
Level 2 routers need to know what IP addresses are reachable
internally (either directly, or via level 1 routing) from other level
2 routers, and what addresses are reachable externally from other
level 2 routers. All of this information is made available by
inclusion of IP reachable address information in the Link State
Packets.
Internal (within the routing domain) and external (outside the
domain) reachability information is announced separately in level 2
LSPs. Reachable IP addresses include a default metric, and may
include multiple TOS-specific metrics. In general, for external
routes, metrics may be of type "internal" (i.e., directly comparable
with internal metrics) or of type "external" (i.e., not comparable
with the internal metric). A route using internal metrics (i.e.,
either announced as "IP internal reachability information", or
announced as "IP external reachability information" with an internal
metric) is always preferred to a route using external metrics (i.e.,
announced as "IP external reachability information", with an external
metric).
The detailed encoding of the IP-specific information included in
routing packets is provided in section 5 (Structure and Encoding of
Callon [Page 16]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
PDUs).
3.2 Hierarchical Abbreviation of IP Reachability Information
Level 2 routers include in their level 2 LSPs a list of all [IP
address, subnet mask, metric] combinations reachable in their area.
In general, this information may be determined from the level 1 LSPs
from all routers in the area. If we ignore resource constraints, then
it would be permissible for a level 2 router to simply duplicate all
[IP address, subnet mask, metric] entries from all level 1 routers in
its area (with appropriate metric adjustment), for inclusion in its
level 2 LSP. However, in order for hierarchical routing to scale to
large routing domain sizes, it is highly desired to abbreviate the
reachable address information.
This is accomplished by manual configuration of summary addresses.
Each level 2 router may be configured with one or more [IP address,
subnet mask, metric] entries for announcement in their level 2 LSPs.
The set of reachable addresses obtained from level 1 LSPs is compared
with the configured reachable addresses. Redundant information
obtained from level 1 LSPs is not included in level 2 LSPs. Generally
it is expected that the level 2 configured information will specify
more inclusive addresses (corresponding to a subnet mask with fewer
bits set to 1). This will therefore allow one configured
address/submask pair (or a small number of such pairs) to
hierarchically supercede the information corresponding to multiple
entries in level 1 LSPs.
The manually configured addresses are included in level 2 LSPs only
if they correspond to at least one address which is reachable in the
area. For manually configured level 2 addresses, the associated
metric values to announce in level 2 LSPs are also manually
configured. The configured addresses will supercede reachable address
entries from level 1 LSPs based only on the IP address and subnet
mask -- metric values are not considered when determining if a given
configured address supercedes an address obtained from a level 1 LSP.
Any address obtained from a level 1 LSP which is not superceded by
the manually configured information is included in the level 2 LSPs.
In this case, the metric value announced in the level 2 LSPs is
calculated from the sum of the metric value announced in the
corresponding level 1 LSP, plus the distance from the level 2 router
to the appropriate level 1 router. Note: If this sum results in a
metric value greater than 63 (the maximum value that can be reported
in level 2 LSPs), then the value 63 must be used. Delay, expense, and
error metrics (i.e., those TOS metrics other than the default metric)
will be included only if (i) the level 2 router supports the specific
Callon [Page 17]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
TOS; (ii) the path from the level 2 router to the appropropriate
level 1 router is made up of links which support the specific TOS;
and (iii) the level 1 router which can reach the address directly
also supports the specific TOS for this route, as indicated in its
level 1 LSP.
In general, the same [IP address, subnet mask] pair may be announced
in level 1 LSPs sent by multiple level 1 routers in the same area. In
this case (assuming the entry is not superceded by a manually
configured entry), then only one such entry shall be included in the
level 2 LSP. The metric value(s) announced in level 2 LSPs correspond
to the minimum of the metric value(s) that would be calculated for
each of the level 1 LSP entries.
A level 2 router will have IP addresses which are directly reachable
via its own interfaces. For purposes of inclusion of IP reachable
address information in level 2 LSPs, these "directly reachable"
addresses are treated exactly the same as addresses received in level
1 LSPs.
Manually configured addresses may hierarchically supercede multiple
level 1 reachable address entries. However, there may be some IP
addresses which match the manually configured addresses, but which
are not reachable via level 1 routing. If a level 2 router receives
an IP packet whose IP address matches a manually configured address
which it is including in its level 2 LSP, but which is not reachable
via level 1 routing in the area, then the packet must be discarded.
In this case, an error report may be returned (as specified in RFC
1009), with the reason for discard specifying destination
unreachable.
Figure 2 - An Example Routing Domain (not shown)
An example is illustrated in figure 2. Suppose that the network
number for the entire routing domain is 17 (a class A network).
Suppose each area is assigned a subnet number consisting of the next
8 bits. The area may be further subdivided by assigning the next
eight bits to each LAN in the area, giving each a 24 bit subnet mask
(counting the network and subnet fields). Finally 8 bits are left for
the host field. Suppose that for a particular area (given subnet
number 17.133) there are a number of IP capable level 1 routers
announcing (in the special IP entry in their level 1 LSPs) subnets
17.133.5, 17.133.43, and 17.133.57.
Callon [Page 18]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
Suppose that in this example, in order to save space in level 2 LSPs,
the level 2 routers in this area are configured to announce subnet
17.133. Only this one address needs to be announced in level 2 LSPs.
Thus if an IP packet comes along for an address in subnet 17.133.5,
17.133.43 or 17.133.57, then other level 2 routers, in other areas,
will know to pass the traffic to this area.
The inclusion of 17.133 in level 2 LSPs means that the three subnet
addresses starting with 17.133 do not all have to be listed
separately in level 2 LSPs.
If any traffic comes along that is for an unreachable address such as
17.133.124.7, then level 2 routers in other areas in this particular
domain will think that this area can handle this traffic, will
forward traffic to level 2 routers in this area, which will have to
discard this traffic.
Suppose that subnet number 17.133.125 was actually reachable via some
other area, such as the lower right hand area. In this case, the
level 2 router in the left area would be announcing (in its level 2
LSPs according to manually configured information) reachability to
subnet 17.133. However, the level 2 router in the lower right area
would be announcing (in its level 2 LSPs according to information
taken from its received level 1 LSPs), reachability to subnet
17.133.125. Due to the use of best match routing, this works
correctly. All traffic from other areas destined to subnet 17.133.125
would be sent to the level 2 router in the lower right area, and all
other traffic to subnet 17.133 (i.e., traffic to any IP address
starting with 17.133, but not starting with 17.133.125) would be sent
to the level 2 router in the leftmost area.
3.3 Addressing Routers in IS-IS Packets
The IS-IS packet formats explicitly require that OSI-style addresses
of routers appear in the IS-IS packets. For example, these addresses
are used to determine area membership of routers. It is therefore
necessary for all routers making use of the IS-IS protocol to have
OSI style addresses assigned. For IP-only routers, these addresses
will be used only in the operation of the IS-IS protocol, and are not
used for any other purpose (such as the operation of EGP, ICMP, or
other TCP/IP protocols).
For OSI-only and dual routers, assignment of NSAP addresses is
straight forward, but is outside of the scope of this specification.
Address assignment mechanisms are being set up by standards bodies
which allow globally unique OSI NSAP addresses to be assigned. All
OSI-only and dual routers may therefore make use of normal OSI
addresses in the operation of the IS-IS protocol.
Callon [Page 19]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
For IP-only routers, there are two ways in which NSAP addresses may
be obtained for use with the IS-IS protocol.
1) For those environments in which OSI is being used, or in which it
is anticipated that OSI will be used in the future, it is
permissible to obtain NSAP address assignments in the normal
manner, assign normal NSAP addresses to IP-only routers, and use
these addresses in the operation of IS-IS. This approach is
recommended even for pure IP routing domains, as it will simplify
future migration from IP-only to dual operation.
2) In some cases, routers may have only TCP/IP addresses, and it may
be undesireable to have to go through the normal mechanisms for
assignment of NSAP addresses. Instead, an alternate mechanim is
provided below for algorithmically generating a valid OSI style
address from existing IP address and autonomous system number
assignments.
Where desired, for IP-only routers, for use in IS-IS packet formats
only, OSI-style addresses (compatible with the USA GOSIP version 2.0
NSAP address format [9]) may be derived as follows:
AFI 1 octet value "47" (specifies ICD format)
ICD 2 octet value "00 05" (specifies Internet/Gosip)
DFI 1 octet value "xx"
AA 3 octets value "xx xx xx" (specifies special
IP-only use of NSAPs)
Reserved 2 octets must be "00 00"
RD 2 octets contains autonomous system number
Area 2 octets must be assigned as described below
ID 6 octets must be assigned as described below
SEL 1 octet used as described below
The AFI value of "47" and the ICD value of "00 05" specifies the
Gosip Version 2.0 addressing format. The DFI number of "xx" and the
AA of "xx xx xx" specify that this special NSAP address format is
being used, solely for IS-IS packet formats in an IP-only
environment. The reserved field must contain "00 00", as specified in
GOSIP version 2.0.
Callon [Page 20]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
The routing domain field contains the Autonomous System number.
Strictly speaking, this is not necessary, since the IS-IS packets are
exchanged within a single AS only. However, inclusion of the AS
number in this address format will ensure correct operation in the
event that routers from separate routing domains/ASs are incorrectly
placed on the same link. The AS number in this context is used only
for definition of unique NSAP addresses, and does not imply any
coupling with exterior routing protocols.
The Area field must be assigned by the authority responsible for the
routing domain, such that each area in the routing domain must have a
unique Area value.
The ID must be assigned by the authority responsible for the routing
domain. The ID must be assigned such that every router in the routing
domain has a unique value. It is recommended that one of the
following methods is used:
1)use a unique IEEE 802 48 bit station ID
2)use the value hex "02 00" prepended to an IP address of the router.
IEEE 802 addresses, if used, must appear in IEEE canonical format.
Since the IEEE 802 station IDs are assigned to be globally unique,
use of these values clearly assures uniqueness in the area. Also, all
assigned IEEE 802 station IDs have the global/local bit set to zero.
Prepending the indicated pattern to the front of the IP address
therefore assures that format (2) illustrated above cannot produce
addresses which collide with format (1). Finally, to the extent that
IP addresses are also globally unique, format (2) will produce unique
IDs for routers.
The indicated hex value is specified in IEEE 802 canonical form [10].
In IEEE 802 addresses, the multicast bit is the least significant bit
of the first byte. The global/local bit is the next least significant
bit of the first byte. The indicated prefix therefore sets the
global/local bit to 1, and all other bits in the first two octets to
0.
Note that within an area, whether ISO addresses are configured into
the routers through ISO address assignment, or whether the ISO-style
address is generated directly from the AS number and IP address, all
routers within an area must have the same high order part of address
(AFI, ICD, DFI, AA, RD, and Area). This ISO-style address is used in
IS-IS Hello messages and is the basis by which routers recognize
whether neighbor nodes are in or out of their area.
Callon [Page 21]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
3.4 External Links
External connectivity (i.e., communications with routers outside of
the routing domain) is done only by level 2 routers. The ISO version
of IS-IS allows external OSI routes to be reported as "reachable
address prefixes" in level 2 LSPs. The integrated IS-IS also allows
external IP reachable addresses (i.e., IP addresses reachable via
inter-domain routing) to be reported in level 2 LSPs in the "IP
external reachability information" field. External OSI and external
IP routes are handled independently.
The routes announced in IP external reachability information entries
include all routes to outside of the routing domain. This includes
routes learned from OSPF, EGP, RIP, or any other external protocol.
External routes may make use of "internal" or "external" metrics.
Internal metrics are comparable with the metrics used for internal
routes. Thus in choosing between an internal route, and an external
route using internal metrics, the metric values may be directly
compared. In contrast, external metrics cannot be directly compared
with internal metrics. Any route defined solely using internal
metrics is always preferred to any route defined using external
metrics. When an external route using external metrics must be used,
the lowest value of the external metric is preferred regardless of
the internal cost to reach the appropriate exit point.
It is useful, in the operation of external routing protocols, to
provide a mechanism for border routers (i.e., routers in the same
routing domain, which have the ability to route externally to other
domains) to determine each other's existence, and to exchange
external information (in a form understood only by the border routers
themselves). This is made possible by inclusion of "inter-domain
routing protocol information" fields in level 2 LSPs. The inter-
domain routing protocol information field is not included in
pseudonode LSPs.
In general there may be multiple types of external inter-domain
routing protocol information exchanged between border routers. The
IS-IS therefore specifies that each occurance of the inter-domain
routing protocol information field include a "type" field, which
indicates the type of inter-domain routing protocol information
enclosed. Values to be used in the type field will be specified in
future versions of the "Assigned Numbers" RFC. Initial values for
this field are specified in Annex A of this specification.
Information contained in the inter-domain routing protocol
information field will be carried in level 2 LSPs, and will therefore
need to be stored by all level 2 routers in the domain. However, only
Callon [Page 22]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
those level 2 routers which are directly involved in external routing
will use this information. In designing the use of this field, it is
important to carefully consider the implications that this may have
on storage requirements in level 2 routers (including those level 2
routers which are not directly involved in external routing).
The protocols used to exchange routing information directly between
border routers, and external routers (in other routing domains /
autonomous systems) are outside of the scope of this specification.
3.5 Type of Service Routing
The integrated IS-IS protocol provides IP Type of Service (TOS)
routing, through use of the Quality of Service (QOS) feature of IS-
IS. This allows for routing on the basis of throughput (the default
metric), delay, expense, or residual error probability. Note than any
particular packet may be routed on the basis of any one of these four
metrics. Routing on the basis of general combinations of metrics is
not supported.
The support for TOS/QOS is optional. If a particular packet calls for
a specific TOS, and the correct path from the source to destination
is made up of routers all of which support that particular TOS, then
the packet will be routed on the optimal path. However, if there is
no path from the source to destination made up of routers which
support that particular type of service, then the packet will be
forwarded using the default metric instead. This allows for TOS
service in those environments where it is needed, while still
providing acceptable service in the case where an unsupported TOS is
requested.
NOTE - IP does not have a cost TOS. There is therefore no mapping of
IP TOS metrics which corresponds to the minimum cost metric.
The IP TOS field is mapped onto the four available metrics as
follows:
Bits 0-2 (Precedence): This field does not affect the route, but
rather may affect other aspects of packet
forwarding.
Bits 3 (Delay), 4 (Throughput) and 5 (Reliability):
000 (all normal) Use default metric
100 (low delay) Use delay metric
010 (high throughput) Use default metric
Callon [Page 23]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
001 (high reliabiity) Use reliability metric
other Use default metric
3.6 Multiple LSPs and SNPs
In some cases, IS-IS packets (specifically Link State Packets and
Complete Sequence Number Packets) may be too large to fit into one
packet. The OSI IS-IS [1] allows for LSPs and CSNPs to be split into
multiple packets. This is independent of ISO 8473 segmentation, and
is also independent of IP fragmentation. Use of independent multiple
packets has the advantages (with respect to segmentation or
fragmentation) that: (i) when information in the IS-IS changes, only
those packets effected need to be re-issued; (ii) when a single
packet is received, it can be processed without the need to receive
all other packets of the same type from the same router before
beginning processing.
The Integrated IS-IS makes use of the same multiple packet function,
as defined in [1]. IP-specific fields in IS-IS packets may be split
across multiple packets. As specified in section 5 ("Structure and
Encoding of PDUs"), some of the IP-specific fields (those which may
be fairly long) may be split into several occurences of the same
field, thereby allowing splitting of the fields across different
packets.
Multiple LSPs from the same router are distinguished by LSP number.
Generally, most variable length fields may occur in an LSP with any
LSP number. Some specific variable length fields may be required to
occur in LSP number 0. Except where explicitly stated otherwise, when
an IS-IS router issues multiple LSPs, the IP-specific fields may
occur in an LSP with any LSP number.
Complete Sequence Number Packets may be split into multiple packets,
with the range to which each packet applies explicitly reported in
the packet. Partial Sequence Number Packets are inherently partial,
and so can easily be split into multiple packets if this is
necessary. Again, where applicable, IP-specific fields may occur in
any SNP.
3.7 IP-Only Operation
For IP-only routers, the format for IS-IS packets remains unchanged.
However, there are some variable length fields from the IS-IS packets
that can be omitted. Specifically:
Callon [Page 24]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
IS-IS Hello Packets:
- no change
IS-IS Link State Packets:
- the "End Systems Neighbours" entries are omitted
- the "Prefix Neighbours" entries are omitted
IS-IS Sequence Number Packets:
- no change
3.8 Encapsulation
Future versions of the Integated IS-IS may specify optional
encapsulation mechanisms for partition repair, and for forwarding
packets through incompatible routers (i.e., for forwarding OSI
packets through IP-only routers, and forwarding IP packets through
OSI-only routers). The details of encapsulation and decapsulation are
for further study. Routers complying with the Integrated IS-IS are
not required to implement encapsulation nor decapsulation.
3.9 Authentication
The authentication field allows each IS-IS packet to contain
information used to authenticate the originator and/or contents of
the packet. The authentication information contained in each packet
is used to authenticate the entire packet, including OSI and IP
parts. If a packet is received which contains invalid authentication
information, then the entire packet is discarded. If an LSP or SNP is
split into multiple packets (as described in section 3.6), then each
is authenticated independently.
Use of the authentication field is optional. Routers are not required
to be able to interpret authentication information. As with other
fields in the integrated IS-IS, if a router does not implement
authentication then it will ignore any authentication field that may
be present in an IS-IS packet.
Annex D specifies a proposed use of the authentication field.
3.10 Order of Preference of Routes / Dijkstra Computation
We define the term "IP reachability entry" to mean the combination of
the [IP address, subnet mask]. The Dijkstra calculation must
calculate routes to each distinct IP reachability entry. For the
Callon [Page 25]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
Dijkstra calculation, each IP reachability entry can be treated in
much the same manner as an OSI end system. Naturally, each IP
reachability entry is treated as distinct from any OSI end systems
which may also be reachable in the same area or routing domain.
For any particular IP reachability entry, this is the same as another
entry if and only if: (i) the subnet masks are identical; and (ii)
for each bit in the subnet mask which has the value "1", the IP
address is identical. This can easily be tested by zeroing those bits
in the IP address which correspond to a zero bit in the mask, and
then treating the entry as a 64 bit quantity, and testing for
equality between different 64 bit quantities. The actual calculation
of routes to IP reachability entries is therefore no more complex
than calculation of routes to OSI end systems (except for the
replacement of a 48-bit test with a 64-bit test).
The Dijkstra computation does not take into consideration whether a
router is IP-only, OSI-only, or dual. The topological restrictions
specified in section 1.4 ensure that IP packets will only be sent via
IP-capable routers, and OSI packets will only be sent via OSI-capable
routers.
The Integrated IS-IS prefers routes within the area (via level 1
routing) whenever possible. If level 2 routes must be used, then
routes within the routing domain (specifically, those routes using
internal metrics) are prefered to routes outside of the routing
domain (using external metrics).
The Integrated IS-IS protocol makes use of "best match" routing of IP
packets. This implies that a particular destination address may match
more than one entry in the forwarding database. If a particular IP
packet has a destination address which matches two different IP
reachability entries, then the entry who's mask contains the most "1"
bits is preferred.
IP packets whose destination is a router are routed the same way as
any other IP packet, by forwarding first to the appropriate subnet,
and then forwarding on that subnet to the destination host (which
just happens to be a router in this case). In particular, the IP
forwarding database does not contain explicit routes to the
individual "IP interface addresses" listed by each router in its LSP.
However, host routes (routes with a subnet mask of all ones) may of
course be included in the IP reachability entries, and will be
handled in the same manner as other IP reachability entries.
In order to ensure correct interoperation of different router
implementations, it is necessary to specify the order of preference
Callon [Page 26]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
of possible routes. For OSI destinations, this is outside of the
scope of this report. For IP destinations, this is specified in
section 3.10.1 and 3.10.2 below. Annex C specifies a detailed
Dijkstra calculation and forwarding algorithm which is compatible
with the order of preference of routes specified here.
With IS-IS, if a route to a given destination is advertised, or a
link between routers is advertised, then metric values associated
with some or all of the specified TOS metric types may be associated
with that destination or link. However, the default metric must
always be available. Normally this ensures that if a route using any
TOS metric is available, then a route using the default metric will
also be available. The only exception to this is where the
corresponding route using the default metric has a total cost (within
the area, or within the level 2 backbone) greater than MaxPathMetric.
In determining the route to a particular destination for a specified
TOS, only routes using either the requested TOS metric, or the
default TOS metric, are considered.
3.10.1 Order of Preference of Routes In Level 1 Routing
If a given destination is reachable within an area via a route using
either the requested TOS or the default TOS, then the IS-IS will
always make use of a path within the area (via level 1 routing),
regardless of whether an alternate path exists outside of the area
(via level 2 routing). In this case, routes within the area are
selected as follows:
1) Amongst routes in the area, if the specified destination
address matches more than one [IP address, subnet mask] pair,
then the more specific address match (the one with more "1"
bits in the mask) is prefered.
2) Amongst routes in the area to equally specific address
matches, routes on which the requested TOS (if any) is
supported are always prefered to routes on which the
requested TOS is not supported.
3) Amongst routes in the area of the same TOS to equally
specific address matches, the shortest routes are prefered.
For determination of the shortest path, if a route on which
the specified TOS is supported is available, then the
specified TOS metric is used, otherwise the default metric
is used. Amongst routes of equal cost, load splitting may
be performed as specified in [1].
For a level 1 only router (i.e., a router which does not take part in
Callon [Page 27]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
level 2 routing, or a level 2 router which is not "attached"), if a
given destination is not reachable within an area, level 1 routing
will always route to a level 2 router as follows:
1) Amongst routes in the area to attached level 2 routers,
routes on which the requested TOS (if any) is supported
are always prefered to routes on which the requested TOS
is not supported.
2) Amongst routes in the area of the same TOS to attached
level 2 routers, the shortest routes are prefered. For
determination of the shortest path, if a route on which
the specified TOS is supported is available, then the
specified TOS metric is used, otherwise the default
metric is used. Amongst routes of equal cost,
loadsplitting may be performed as specified in [1].
3.10.2 Order of Preference of Routes in Level 2 Routing
For those level 2 routers which also take part in level 1 routing,
routes learned via level 1 routing, using either the requested TOS or
the default TOS, are always prefered to routes learned through level
2 routing. For destinations which are not reachable via level 1
routing, or for level 2 only routers (routers which do not take part
in level 1 routing), then level 2 routes are selected as follows:
1) Routes using internal metrics only are always preferred
to routes using external metrics.
2) If a route using internal metrics only is available:
a) If the specified destination address matches more
than one [IP address, subnet mask] pair, then the more
specific address match (i.e., the largest number of
"1"s present in the subnet mask) is prefered.
b) Amongst routes with equally specific address matches
(i.e., an equal number of "1"s present in the subnet
mask), routes on which the requested TOS (if any) is
supported are always preferred to routes on which the
requested TOS is not supported.
c) Amongst routes of the same TOS with an equally specific
address matches, the shortest path is prefered. For
determination of the shortest path, if a route on which
the specified TOS is supported is available, then the
specified TOS metric is used, otherwise the default
metric is used. Amongst routes of equal cost,
Callon [Page 28]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
loadsplitting may be performed as specified in [1].
NOTE: Internal routes (routes to destinations announced
in the "IP Internal Reachability Information" field),
and external routes using internal metrics (routes to
destinations announced in the "IP External Reachability
Information" field, with a metric of type "internal")
are treated identically for the purpose of the order of
preference of routes, and the Dijkstra calculation.
3) If a route using internal metrics only is not available,
but a route using external metrics is available:
a) If the specified destination address matches more than
one [IP address, subnet mask] pair, then the more
specific address match is prefered.
NOTE: For external routes, the subnet mask will normally
correspond precisely to the network number. This implies
that this test will always discover equal length matching
strings. However, this test is included to allow future
migration to more general handling of external addresses.
b) Amongst routes with equally specific matches, routes on
which the requested TOS (if any) is supported are always
preferred to routes on which the requested TOS is not
supported. NOTE: for external routes, the route is
considered to support the requested TOS only if the
internal route to the appropriate border router
supports the requested TOS, and the external route
reported by the border router also supports the
requested TOS.
c) Amongst routes of the same TOS with an equal length
matching address string, the shortest path is prefered.
For determination of the shortest path:
(i) Routes with a smaller announced external metric
are always prefered.
(ii) Amongst routes with an equal external metric,
routes with a shorter internal metric are prefered.
Amongst routes of equal cost, loadsplitting may be
performed as specified in [1].
For level 2 routers which are announcing manually configured summary
addresses in their level 2 LSPs, in some cases there will exist IP
addresses which match the manually configured addresses, but which do
Callon [Page 29]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
not match any addresses which are actually reachable via level 1
routing in the area. Generally, packets to such addresses are handled
according to the following rules:
1) If the specified destination is reachable via level 1 routing,
then according to the order of preference of routes specified
above, the packet will be delivered via level 1 routing.
2) If the specified destination is not reachable via level 1 routing,
but is reachable via 2 routing, and there are other level 2
routers which offer more desireable routes according to the
rules specified above (for example a route with a more specific
match, or a route with an equally specific match which supports
the correct TOS), then level 2 routing will forward the packet
according to the more desireable route.
3) If the specified destination is not reachable via level 1 routing,
and the manually configured summary address advertised by this
router (the router which has received the packet and is trying
to forward it) represents the most desireable route, then the
destination is unreachable and the packet must be discarded.
4 Subnetwork Dependent Functions
4.1 Link Demultiplexing
Dual routers may receive a combination of OSI packets, and IP
packets. It is necessary for the dual routers to be able to clearly
and unambiguously distinguish the two protocol suites.
This problem is not unique to the integrated IS-IS routing protocol.
In fact, this problem will occur in any multi-protocol environment.
This problem is currently being worked on independently, and is
outside of the scope of this specification.
In general, the link type is a configuration parameter. For example,
whether to use PPP, HDLC, or some other point-to-point protocol over
a point-to-point link would be configured. For any particular link
type, a method must be defined for encapsulation of both OSI and IP
packets. Definition of such methods for common link types is outside
of the scope of this specification.
IP packets are encapsulated directly over the underlying link layer
service, using the normal method for transmssion of IP packets over
each type of link. Similarly OSI packets are encapsulated directly
over the underlying link layer service, using the normal method for
transmission of OSI packets over each type of link. Finally, note
that IS-IS packets are encapsulated using the normal method for
Callon [Page 30]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
transmission of OSI packets over any particular link type. This
implies that all IS-IS routers, including IP-only routers, must be
able to receive IS-IS packets using the normal encapsulation for OSI
packets.
4.2 Multiple IP Addresses per Interface
The integrated IS-IS allows each router to have multiple IP addresses
for each physical interface, up to the maximum number which may be
contained in a single "IP Interface Address" field (i.e., up to a
maximum of 63 addresses per interface). For example, where there are
two logical subnets on the same LAN, the interface may have two IP
addresses, one corresponding to each logical subnet. Each IS-IS Hello
packet contains a list of IP addresses associated with the physical
interface over which the Hello is transmitted.
It is permissible to implement routers which conform to the
Integrated IS-IS specification which restrict the number of IP
addresses per interface. However, IP-capable routers must be able to
interact correctly with other routers which assign multiple IP
addresses per physical interface (up to the maximum of 63 addresses
per interface).
Where appropriate (for example, in some cases on point-to-point
links), some interfaces may have no IP addresses assigned. In this
case, the IS-IS Hello transmitted on that interface may omit the IP
Interface Address field, or may include the IP Interface Address
field with zero entries.
4.3 LANs, Designated Routers, and Pseudonodes
The maintenance of designated routers and pseudonodes is specified in
[1], and is not changed by this proposal. In the case that IP-only
and dual routers (or OSI-only and dual routers) are mixed on the same
LAN in a pure IP area (or a pure OSI area, respectively), any router
on the LAN may be elected designated router.
However, there is a fundamental difference in the way that OSI and
TCP/IP deal with LANs, and other broadcast subnetworks.
With OSI, the use of the ES-IS protocol (ISO 9542) allows the end
systems and routers to automatically determine their connectivity,
thereby allowing all end systems on the LAN to potentially route via
any of the routers on the LAN.
In contract, TCP/IP explictly assigns subnet identifiers to each
local area network. In some cases, a single physical LAN could have
multiple subnet identifiers assigned to it. In this case, end systems
Callon [Page 31]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
(hosts) which have an address on one logical subnet are explicitly
precluded from sending IP packets directly to a router whose address
places it on a different logical subnet. Each router is manually
configured to know which subnets it can reach on each interface. In
the case that there are multiple logical subnets on the same LAN,
each router can only exchange IP packets with those end systems which
are on the same logical subnet. This implies that it is not
sufficient for the pseudonode LSP to announce all subnets on the LAN
(i.e., all [IP address, subnet mask] pairs reachable on the LAN).
It is therefore necessary for each router to announce in its LSPs
those subnets which it can reach on each interface, including
interfaces to broadcast subnetworks such as LANs. The pseudonode LSP
does not specify the IP addresses which are reachable on the LAN
(i.e., does not contain the the IP reachability field).
As specified elsewhere (see the forthcoming update to the
"Requirements of IP Gateways" [4]), routers may send ICMP redirects
only if: (i) the IP packet is being forwarded over the same physical
interface over which it arrived; and (ii) the source address of the
forwarded IP packet, the IP address of this router's interface (as
indicated by the source address of the ICMP redirect), and the IP
address of the router to which the packet is being redirected (again,
as indicated in the ICMP redirect) are all on the same IP subnet.
4.4 Maintaining Router Adjacencies
The IS-IS determines whether an adjacency is to be established
between two routers using means which are independent of the IP
interface addresses of the routers. Where multiple logical subnets
occur on the same physical LAN, this potentially allows adjacencies
to be brought up between two routers which share physical
connectivity to each other, but which don't have a logical subnet in
common. IP-capable IS-IS routers therefore must be able to forward IP
packets over existing adjacencies to routers with which they share
physical connectivity, even when the IP address of the adjacent
interface of the neighboring router is on a different logical IP
subnet.
For point-to-point links, IS-IS requires exchange of ISO 9542 ISHs,
as the first step in establishing the link between routers. All IS-IS
routers are therefore required to transmit and receive ISO 9542 ISH
packets on point-to-point links.
The "protocols supported" field (defined in section 5 below) must be
present in all IS-IS Hello packets sent by dual and IP-only routers.
If this field is missing, then it is assumed that the packet was
transmitted by an OSI-only router. Similarly, those 9542 ISHs sent
Callon [Page 32]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
over point-to-point links, where there is (or may be) another IS-IS
router at the other end of the point-to-point link, must also
contains the "protocols supported" field. Note that if this field is
mistakenly sent in a 9542 ISH where there is an ordinary OSI-only End
System at the other end of the link, then (in accordance to ISO 9542)
the End System is required to ignore the field and interpret the ISH
correctly. It is therefore safe to always include this field in ISHs
sent over point-to-point links.
Dual routers must operate in a dual fashion on every link in the
routing domain over which they are running IS-IS. Thus, the value of
the "protocols supported" field must be identical on every link
(i.e., for any one router running IS-IS, all of the Hellos and LSPs
transmitted by it must contain the same "protocols supported"
values).
4.5 Forwarding to Incompatible Routers
There may be times when a dual router has to forward an IP packet to
an OSI-only router, or forward an OSI packet to an IP-only router. In
this case the packet must be discarded. An error report may be
transmitted, in accordance with the IP or ISO 8473 specification
(respectively). The reason for discard specified in the error report
should specify "destination host unreachable" (for IP), or
"destination unreachable" (for OSI).
Similarly, due to errors, in some cases an IP-only router may have to
forward an IP packet to an OSI-only router. Again, the packet must be
discarded, as specified above. This may only occur if IP-only and
OSI-only routers occur in the same area, which is a configuration
error.
5 Structure and Encoding of PDUs
This clause describes the additional packet fields for use of the ISO
IS-IS Intra-Domain Routing protocol in pure IP and dual environments.
Specifically, the same packet types are used as in IS-IS [1], and all
fixed fields remain the same. Additional variable length fields are
defined in this section.
5.1 Overview of IS-IS PDUs
The packets used in IS-IS routing protocol fall into three main
classes: (i) Hello Packets; (ii) Link State Packets (LSPs); and (iii)
Sequence Number Packets (SNPs).
Hello packets are used to initialize and maintain adjacencies between
neighboring routers. There are three types of IS-IS Hello packets:
Callon [Page 33]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
(i) "Level 1 LAN IS to IS Hello PDUs" are used by level 1 routers on
broadcast LANs. (ii) "Level 2 LAN IS to IS Hello PDUs" are used by
level 2 routers on broadcast LANs. (iii) "Point-to-Point IS to IS
Hello PDUs" are used on non-broadcast media, such as point-to-point
links, or general topology subnetworks.
On point-to-point links, the exchange of ISO 9542 ISHs (intermediate
system Hellos) is used to initialize the link, and to allow each
router to know if there is a router on the other end of the link,
before IS-IS Hellos are exchanged. All routers implementing IS-IS
(whether IP-only, OSI-only, or dual), if they have any interfaces on
point-to-point links, must therefore be able to transmit ISO 9542
ISHs on their point-to-point links.
Link State Packets (LSPs) are used to exchange link state
information. There are two types of LSPs: (i) "Level 1 Link State
PDUs" are transmitted by level 1 routers. (ii) "Level 2 Link State
PDUs" are transmitted by level 2 routers. Note that level 2 routers
will, in most cases, also be level 1 routers, and will therefore
transmit both sorts of LSPs.
Sequence number PDUs are used to ensure that neighboring routers have
the same notion of what is the most recent LSP from each other
router. The sequence number PDUs therefore serve a similar function
to acknowledgement packets, but allow more efficient operation. There
are four types of sequence number packets: (i) "Level 1 Complete
Sequence Numbers PDU"; (ii) "Level 2 Complete Sequence Numbers PDU";
(iii) "Level 1 Partial Sequence Numbers PDU"; and (iv) "Level 2
Partial Sequence Numbers PDU". A partial sequence number packet lists
the most recent sequence number of one or more LSPs, and operates
much like an acknowlegement. A partial sequence number packet differs
from an conventional acknowledgement in the sense that it may
acknowlege multiple LSPs at once, and in the sense that it may act as
a request for information. A complete sequence number packet contains
the most recent sequence number of all LSPs in the database. A
complete sequence number packet may therefore be used to ensure
synchronization of the database between adjacent routers either
periodically, or when a link first comes up.
5.2 Overview of IP-Specific Information for IS-IS
There are six new fields defined for the Integrated IS-IS: (i)
"Protocols Supported"; (ii) "IP Interface Address"; (iii)
"Authentication Information"; (iv) "IP Internal Reachability
Information"; (v) "IP External Reachability Information"; and (vi)
"Inter-Domain Routing Protocol Information".
The "Protocols Supported" field identifies the protocols which are
Callon [Page 34]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
supported by each router. This field must be included in all IS-IS
Hello packets and all LSPs with LSP number 0 transmitted by IP-
capable routers. If this field is not included in an IS-IS Hello
packet or an LSP with LSP number 0, it may be assumed that the packet
was transmitted by an OSI-only router. The "Protocols Supported"
field must also be included in ISO 9542 ISHs send by IP-capable
routers over point-to-point links to other IS-IS routers.
The "IP Interface Address" is included in all IS-IS Hello packets and
LSPs transmitted by IP-only and dual routers. In the Hello packets,
this field occurs once only, and contains the IP address(es) of the
interface on which the Hello packet is transmitted (up to a maximum
of 63 IP addresses on each interface). If an IS-IS Hello is
transmitted over an interface which does not have an IP address
assigned, then this field may be omitted, or may be included with
zero entries. In Link State Packets, this field contains a list of
one or more IP addresses corresponding to one or more interfaces of
the router which originates the LSP. Each IP-capable router must
include this field in its LSPs. This field may occur multiple times
in an LSP, and may occur in an LSP with any LSP number.
The "Authentication Information" field is optional in all IS-IS PDUs.
If used, it contains information used to authenticate the packet. All
IS-IS packets (including 9542 IS Hellos) may be authenticated by use
of this field.
The "IP Internal Reachability Information" field may be present in
all LSPs transmitted by IP-capable routers. If present, it identifies
a list of zero or more [IP address, subnet mask, metrics] reachable
by the router which originates the LSP. Each entry must contain a
default metric, and may contain delay, expense, and error metrics. If
an IP-capable router does not directly reach any IP addresses, then
it may omit this field, or may include the field with zero [IP
address, subnet mask, metrics] entries. If included in level 1 LSPs,
this field includes only entries directly reachable by the router
which originates the LSP, via one of its interfaces. If included in
level 2 LSPs, this field includes only entries reachable by the
router which originates the LSP, either via one of its interfaces, or
indirectly via level 1 routing. This field may occur multiple times
in an LSP, and may occur in an LSP with any LSP number.
The "IP External Reachability Information" field may be present in
level 2 LSPs transmitted by level 2 IP-capable routers. If present,
it identifies a list of zero or more [IP address, subnet mask,
metrics] entries reachable by the router which originates the level 2
LSP. Each entry must contain a default metric, and may contain delay,
expense, and error metrics. Each entry may contain metrics of type
"internal", or of type "external". If a level 2 router does not have
Callon [Page 35]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
any external routes (via neighboring routers in other routing
domains), when it may omit this field, or may include the field with
zero entries. This field includes only entries reachable by the
router which originates the LSP, via a direct link to an external
router. This field may occur multiple times in a level 2 LSP, and may
occur in an LSP with any LSP number.
The "Inter-Domain Routing Protocol Information" field may be present
in level 2 LSPs transmitted by level 2 IP-capable routers. This field
is transmitted for the convenience of the external routing protocol,
and is not used by the IS-IS. For example, this may be used to allow
border routers to find each other. This field may occur multiple
times in a level 2 LSP, and may occur in an LSP with any LSP number.
The DP 10589 version of the OSI IS-IS does not currently allow
addition of TLV-encoded variable length fields to Sequence Number
Packets. However, this is being corrected in future versions of
10589. In addition, this is expected to be the only correction to
future versions of 10589 that is not backward-compatible with the DP
version. The Integrated IS-IS therefore makes use of a corrected
version of DP 10589, such that the encoding of SNPs has been fixed.
The correct encoding of sequence number packets (as is expected to
appear in future versions of ISO 10589) is given in Annex B of this
specification.
All IP-specific information is encoded in IS-IS packets as variable
length fields. All variable length fields in IS-IS are encoded as
follows:
No. of Octets
+---------------------------+
| CODE | 1
+---------------------------+
| LENGTH | 1
+---------------------------+
| VALUE | LENGTH
+---------------------------+
Figure 3 - Encoding of Variable Length Fields
Any codes in a received PDU that are not recognised shall be ignored
and, for those packets which are forwarded (specifically Link State
Packets), passed on unchanged.
In general, an IS-IS PDU may contain multiple variable length fields,
some of which contain OSI-specific information (specified in [1]) and
some of which contain IP-specific information (specified below).
Except where explicitly stated otherwise, these variable length
Callon [Page 36]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
fields may occur in any order.
5.3 Encoding of IP-Specific Fields in IS-IS PDUs
This section specifies the detailed encoding of all IP-specific
fields in IS-IS PDUs. Where a particular field may be present in more
than one type of PDU, the field is repeated for each type of PDU to
which it applies.
Bit and octet numbering is the same as in [1]. In particular, octets
in a PDU are numbered starting from 1, in increasing order. Bits in
an octet are numbered from 1 to 8, where bit 1 is the least
significant bit and is pictured on the right. When consecutive octets
are used to represent a number, the lower octet number has the most
significant value.
5.3.1 Level 1 LAN IS to IS Hello PDU
- Additional codes for IP support are:
7 Protocols Supported -- the set Network Layer Protocol Identifiers
for Network Layer protocols that this Intermediate System is
capable of relaying
x CODE - 129
x LENGTH - total length of the value field (one octet per
protocol supported).
x VALUE - one octet NLPID (as assigned by ISO/TR 9577) for
each supported data protocol.
No. of Octets
+---------------------------+
| NLPID | 1
+---------------------------+
: :
: :
|---------------------------|
| NLPID | 1
+---------------------------+
NLPID - ISO/TR 9577 registered Network Layer Protocol Identifier.
7 IP Interface Address -- the IP address(es) of the interface
corresponding to the SNPA over which this PDU is to be transmitted.
x CODE - 132
x LENGTH - total length of the value field (four octets per address).
Callon [Page 37]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
x VALUE -
No. of Octets
+----------------------------+
| IP ADDRESS | 4
+----------------------------+
: :
: :
+----------------------------+
| IP ADDRESS | 4
+----------------------------+
IP ADDRESS - 4 octet IP Address of the Interface.
7 Authentication Information -- Information used to authenticate the
PDU
x CODE - 133
x LENGTH - total length of the value field.
x VALUE - TBD.
5.3.2 Level 2 LAN IS to IS Hello PDU
- Additional codes for IP support are:
7 Protocols Supported -- the set Network Layer Protocol Identifiers
for Network Layer protocols that this Intermediate System is
capable of relaying
x CODE - 129
x LENGTH - total length of the value field (one octet per protocol
supported).
x VALUE - one octet NLPID (as assigned by ISO/TR 9577) for each
supported data protocol.
No. of Octets
+----------------------------+
| NLPID | 1
+----------------------------+
: :
: :
+----------------------------+
| NLPID | 1
+----------------------------+
NLPID - ISO/TR 9577 registered Network Layer Protocol Identifier.
7 IP Interface Address -- The IP address(es) of the interface
Callon [Page 38]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
corresponding to the SNPA over which this PDU is to be transmitted.
x CODE - 132
x LENGTH - total length of the value field (four octets per address).
x VALUE -
No. of Octets
+----------------------------+
| IP ADDRESS | 4
+----------------------------+
: :
: :
+----------------------------+
| IP ADDRESS | 4
+----------------------------+
IP ADDRESS - 4 octet IP Address of the Interface.
7 Authentication Information -- Information used to authenticate
the PDU
x CODE - 133
x LENGTH - total length of the value field
x VALUE - TBD
5.3.3 Point-to-Point IS to IS Hello PDU
- Additional codes for IP support are:
7 Protocols Supported -- the set Network Layer Protocol Identifiers
for Network Layer protocols that this Intermediate System is
capable of relaying
x CODE - 129
x LENGTH - total length of the value field (one octet per protocol
supported).
x VALUE - one octet NLPID (as assigned by ISO/TR 9577) for each
supported data protocol.
Callon [Page 39]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
No. of Octets
+----------------------------+
| NLPID | 1
+----------------------------+
: :
: :
+----------------------------+
| NLPID | 1
+----------------------------+
NLPID - ISO/TR 9577 registered Network Layer Protocol Identifier.
7 IP Interface Address -- The IP address(es) of the interface
corresponding to the SNPA over which this PDU is to be transmitted.
x CODE - 132
x LENGTH - total length of the value field (four octets per address).
x VALUE -
No. of Octets
+----------------------------+
| IP ADDRESS | 4
+----------------------------+
: :
: :
+----------------------------+
| IP ADDRESS | 4
+----------------------------+
IP ADDRESS - 4 octet IP Address of the Interface.
7 Authentication Information -- Information used to authenticate
the PDU
x CODE - 133
x LENGTH - total length of the value field
x VALUE - TBD
5.3.4 Level 1 Link State PDU
- Additional codes for IP support are:
7 Protocols Supported -- the set Network Layer Protocol Identifiers
for Network Layer protocols that this Intermediate System is
capable of relaying.
This must appear once in LSP number 0.
Callon [Page 40]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
x CODE - 129
x LENGTH - total length of the value field (one octet per protocol
supported).
x VALUE - one octet NLPID (as assigned by ISO/TR 9577) for each
supported data protocol.
No. of Octets
+----------------------------+
| NLPID | 1
+----------------------------+
: :
: :
+----------------------------+
| NLPID | 1
+----------------------------+
NLPID - ISO/TR 9577 registered Network Layer Protocol Identifier.
7 IP Interface Addresses -- The IP addresss of one or more interfaces
corresponding to the SNPAs enabled on this Intermediate system
(i.e., one or more IP addresses of this router).
This is permitted to appear multiple times, and in an LSP with
any LSP number.
x CODE - 132
x LENGTH - total length of the value field (four octets per address).
x VALUE -
No. of Octets
+----------------------------+
| IP ADDRESS | 4
+----------------------------+
: :
: :
+----------------------------+
| IP ADDRESS | 4
+----------------------------+
IP ADDRESS - 4 octet IP Address
7 Authentication Information -- Information used to authenticate
the PDU
x CODE - 133
x LENGTH - total length of the value field
Callon [Page 41]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
x VALUE - TBD
7 IP Internal Reachability Information -- IP addresses within the
routing domain reachable directly via one or more interfaces on
this Intermediate system.
This is permitted to appear multiple times, and in an LSP with any
LSP number. However, this field must not appear in pseudonode LSPs.
x CODE - 128.
x LENGTH - a multiple of 12.
x VALUE -
No. of Octets
+----------------------------+
| 0 |I/E| DEFAULT METRIC | 1
+----------------------------+
| S | R | DELAY METRIC | 1
+----------------------------+
| S | R | EXPENSE METRIC | 1
+----------------------------+
| S | R | ERROR METRIC | 1
+----------------------------+
| IP ADDRESS | 4
+----------------------------+
| SUBNET MASK | 4
+----------------------------+
: :
: :
+----------------------------+
| 0 |I/E| DEFAULT METRIC | 1
+----------------------------+
| S | R | DELAY METRIC | 1
+----------------------------+
| S | R | EXPENSE METRIC | 1
+----------------------------+
| S | R | ERROR METRIC | 1
+----------------------------+
| IP ADDRESS | 4
+----------------------------+
| SUBNET MASK | 4
+----------------------------+
DEFAULT METRIC is the value of the default metric for the link
to the listed neighbor. Bit 8 of this field is reserved, and
must be set to zero on tranmission and ignored on reception.
Bit 7 of this field (marked I/E) indicates the metric type
Callon [Page 42]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
(internal or external) for all four TOS metrics, and must be
set to zero indicating internal metrics.
DELAY METRIC is the value of the delay metric for the link to the
listed neighbor. If this IS does not support this metric it shall
set the bit "S" to 1 to indicate that the metric is unsupported.
Bit 7 of this field is reserved, and must be set to zero on
transmission and ignored on reception.
EXPENSE METRIC is the value of the expense metric for the link to
the listed neighbor. If this IS does not support this metric it
shall set the bit "S" to 1 to indicate that the metric is
unsupported. Bit 7 of this field is reserved, and must be set to
zero on transmission and ignored on reception.
ERROR METRIC is the value of the error metric for the link to
the listed neighbor. If this IS does not support this metric it
shall set the bit "S" to 1 to indicate that the metric is
unsupported. Bit 7 of this field is reserved, and must be set
to zero on transmission and ignored on reception.
IP ADDRESS is a 4-octet Internet address
SUBNET MASK is a 4 octet IP subnet mask.
5.3.5 Level 2 Link State PDU
- Additional codes for IP support are:
7 Protocols Supported -- the set Network Layer Protocol Identifiers
for Network Layer protocols that this Intermediate System is
capable of relaying.
This must appear once in LSP number 0.
x CODE - 129
x LENGTH - total length of the value field (one octet per
protocol supported).
Callon [Page 43]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
x VALUE - one octet NLPID (as assigned by ISO/TR 9577) for
each supported data protocol.
No. of Octets
+----------------------------+
| NLPID | 1
+----------------------------+
: :
: :
+----------------------------+
| NLPID | 1
+----------------------------+
NLPID - ISO/TR 9577 registered Network Layer Protocol Identifier.
7 IP Interface Addresses -- The IP addresss of one or more interfaces
corresponding to the SNPAs enabled on this Intermediate system
(i.e., one or more IP addresses of this router).
This is permitted to appear multiple times, and in an LSP with
any LSP number. Where a router is both a level 1 and level 2 router,
it must include the same IP addresses in its level 1 and level 2 LSPs.
x CODE - 132
x LENGTH - total length of the value field (four octets per address).
x VALUE-
No. of Octets
+----------------------------+
| IP ADDRESS | 4
+----------------------------+
: :
: :
+----------------------------+
| IP ADDRESS | 4
+----------------------------+
IP ADDRESS - 4 octet IP Address
7 Authentication Information -- Information used to authenticate
the PDU
x CODE - 133
x LENGTH - total length of the value field
x VALUE - TBD
7 IP Internal Reachability Information -- IP addresses within the
routing domain reachable directly via one or more interfaces on
Callon [Page 44]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
this Intermediate system.
This is permitted to appear multiple times, and in an LSP with
any LSP number. However, this field must not appear in pseudonode
LSPs.
x CODE - 128.
x LENGTH - a multiple of 12.
x VALUE -
No. of Octets
+----------------------------+
| 0 |I/E| DEFAULT METRIC | 1
+----------------------------+
| S | R | DELAY METRIC | 1
+----------------------------+
| S | R | EXPENSE METRIC | 1
+----------------------------+
| S | R | ERROR METRIC | 1
+----------------------------+
| IP ADDRESS | 4
+----------------------------+
| SUBNET MASK | 4
+----------------------------+
: :
: :
+----------------------------+
| 0 |I/E| DEFAULT METRIC | 1
+----------------------------+
| S | R | DELAY METRIC | 1
+----------------------------+
| S | R | EXPENSE METRIC | 1
+----------------------------+
| S | R | ERROR METRIC | 1
+----------------------------+
| IP ADDRESS | 4
+----------------------------+
| SUBNET MASK | 4
+----------------------------+
DEFAULT METRIC is the value of the default metric for the link
to the listed neighbor. Bit 8 of this field is reserved, and must
be set to zero on transmission and ignored on reception. Bit 7
of this field indicates the metric type (internal or external)
for all four TOS metrics, and must be set to zero indicating
internal metrics.
Callon [Page 45]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
DELAY METRIC is the value of the delay metric for the link to
the listed neighbor. If this IS does not support this metric it
shall set the bit "S" to 1 to indicate that the metric is
unsupported. Bit 7 of this field is reserved, and must be set
to zero on transmission and ignored on reception.
EXPENSE METRIC is the value of the expense metric for the link to
the listed neighbor. If this IS does not support this metric it
shall set the bit "S" to 1 to indicate that the metric is
unsupported. Bit 7 of this field is reserved, and must be set
to zero on transmission and ignored on reception.
ERROR METRIC is the value of the error metric for the link to the
listed neighbor. If this IS does not support this metric it shall
set the bit "S" to 1 to indicate that the metric is unsupported.
Bit 7 of this field is reserved, and must be set to zero on
transmission and ignored on reception.
IP ADDRESS is a 4-octet Internet address
SUBNET MASK is a 4 octet IP subnet mask.
7 IP External Reachability Information -- IP addresses outside the
routing domain reachable via interfaces on this Intermediate
system.
This is permitted to appear multiple times, and in an LSP with
any LSP number. However, this field must not appear in pseudonode LSPs.
x CODE - 130.
x LENGTH - a multiple of 12.
x VALUE -
Callon [Page 46]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
No. of Octets
+----------------------------+
| 0 |I/E| DEFAULT METRIC | 1
+----------------------------+
| S | R | DELAY METRIC | 1
+----------------------------+
| S | R | EXPENSE METRIC | 1
+----------------------------+
| S | R | ERROR METRIC | 1
+----------------------------+
| IP ADDRESS | 4
+----------------------------+
| SUBNET MASK | 4
+----------------------------+
: :
: :
+----------------------------+
| 0 |I/E| DEFAULT METRIC | 1
+----------------------------+
| S | R | DELAY METRIC | 1
+----------------------------+
| S | R | EXPENSE METRIC | 1
+----------------------------+
| S | R | ERROR METRIC | 1
+----------------------------+
| IP ADDRESS | 4
+----------------------------+
| SUBNET MASK | 4
+----------------------------+
DEFAULT METRIC is the value of the default metric for the
path to the listed IP addresses. Bit 8 of this field is
reserved, and must be set to zero on transmission and ignored
on reception. Bit 7 of this field indicates the metric type
(internal or external) for all four TOS metrics, and may be
set to zero indicating internal metrics, or may be set to 1
indicating external metrics.
DELAY METRIC is the value of the delay metric for the path
to the listed IP addresses. If this IS does not support this
metric it shall set the bit "S" to 1 to indicate that the metric
is unsupported. Bit 7 of this field is reserved, and must be
set to zero on transmission and ignored on reception.
EXPENSE METRIC is the value of the expense metric for the link
to the listed IP addresses. If this IS does not support this
metric it shall set the bit "S" to 1 to indicate that the metric
is unsupported. Bit 7 of this field is reserved, and must be
Callon [Page 47]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
set to zero on transmission and ignored on reception.
ERROR METRIC is the value of the error metric for the link to
the listed IP addresses. If this IS does not support this metric
it shall set the bit "S" to 1 to indicate that the metric is
unsupported. Bit 7 of this field is reserved, and must be set to
zero on transmission and ignored on reception.
IP ADDRESS is a 4-octet Internet address
SUBNET MASK is a 4 octet IP subnet mask
7 Inter-Domain Routing Protocol Information -- Inter-domain routing
protocol information carried transparently through level 2 for
the convenience of any Inter-Domain protocol that may be running
in the boundary ISs.
This is permitted to appear multiple times, and in an LSP with
any LSP number.
x CODE - 131.
x LENGTH - total length of the value field
x VALUE -
No. of Octets
+-------------------------------+
| Inter-Domain Information Type | 1
+-------------------------------+
| External Information | VARIABLE
+-------------------------------+
INTER-DOMAIN INFORMATION TYPE indicates the type of the
external information which is encoded in the field.
EXTERNAL INFORMATION contains inter-domain routing protocol
information, and is passed transparently by the IS-IS protocol.
5.3.6 Level 1 Complete Sequence Numbers PDU
- Additional codes for IP support are:
7 Authentication Information -- Information used to authenticate
the PDU
x CODE - 133
x LENGTH - total length of the value field
Callon [Page 48]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
x VALUE - TBD
5.3.7 Level 2 Complete Sequence Numbers PDU
- Additional codes for IP support are:
7 Authentication Information -- Information used to authenticate
the PDU
x CODE - 133
x LENGTH - total length of the value field
x VALUE - TBD
5.3.8 Level 1 Partial Sequence Numbers PDU
- Additional codes for IP support are:
7 Authentication Information -- Information used to authenticate
the PDU
x CODE - 133
x LENGTH - total length of the value field
x VALUE - TBD
5.3.9 Level 2 Partial Sequence Numbers PDU
- Additional codes for IP support are:
7 Authentication Information -- Information used to authenticate
the PDU
x CODE - 133
x LENGTH - total length of the value field
x VALUE - TBD
5.3.10 ISO 9542 ISH PDU
- Additional codes for IP support are:
7 Protocols Supported -- the set Network Layer Protocol Identifiers
for Network Layer protocols that this Intermediate System is
capable of relaying.
Callon [Page 49]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
This appears in ISO 9542 ISH PDUs transmitted on point-to-point
links.
x CODE - 129
x LENGTH - total length of the value field (one octet per
protocol supported).
x VALUE - one octet NLPID (as assigned by ISO/TR 9577) for
each supported data protocol.
No. of Octets
+----------------------------+
| NLPID | 1
+----------------------------+
: :
: :
+----------------------------+
| NLPID | 1
+----------------------------+
NLPID - ISO/TR 9577 registered Network Layer Protocol Identifier.
7 Authentication Information -- Information used to authenticate
the PDU
x CODE - 133
x LENGTH - total length of the value field
x VALUE - TBD
6 Security Considerations
The integrated IS-IS has a provision for carrying authentication
information in all IS-IS packets. This is extensible to multiple
authentication mechanisms. However, currently the only defined
mechanism is a simple password, transmitted in the clear without
encryption (see Annex D). The use of a simple password does not
provide useful protection against intentional misbehavior. Rather,
this should be thought of as a weak protection against accidental
errors such as accidental mis-configuration. Definition of other
authentication mechanisms is beyond the scope of this document.
Other aspects of security are not discussed in this document.
Callon [Page 50]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
7 Author's Address
Ross Callon
Digital Equipment Corporation
550 King Street, LKG 1-2/A19
Littleton, MA 01460-1289
508-486-5009
8 References
[1] "Intermediate System to Intermediate System Intra-Domain
Routeing Exchange Protocol for use in Conjunction with the
Protocol for Providing the Connectionless-mode Network Service
(ISO 8473)", ISO DP 10589, February 1990.
[2] "Protocol for Providing the Connectionless-Mode Network
Service", ISO 8473, March 1987.
[3] "End System to Intermediate System Routeing Exchange Protocol
for Use in Conjunction with the Protocol for Providing the
Connectionless-Mode Network Service (ISO 8473)", ISO 9542,
March 1988.
[4] Braden,R., and Postel,J., "Requirements for Internet Gateways",
RFC 1009, June 1987.
[5] Moy,J., "The OSPF Specification", RFC 1131, October 1989.
[6] Postel,J., "Internetwork Protocol", RFC 791, September 1981.
[7] Postel,J., "Internet Control Message Protocol", RFC 792,
September 1981.
[8] "MIB for Use with the Extended OSI IS-IS in TCP/IP and Dual
Environments", forthcoming.
[9] GOSIP Advanced Requirements Group, "Government Open Systems
Interconnection Profile (GOSIP) Version 2.0 [Final Text]",
Federal Information Processing Standard, U.S. Department of
Commerce, National Institute of Standards and Technology,
Gaithersburg, MD, October 1990.
[10] "Standard for Local Area Networks and Metropolitan Area
Networks: Overview and Architecture of Network Standards",
IEEE Standard 802.1a-1990.
Callon [Page 51]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
Annex A
Inter-Domain Routing Protocol Information
This annex specifies the contents and encoding of the Inter-Domain
Routing Protocol Information (IDRPI) field. This annex is an integral
part of the Integrated IS-IS specification. However, it is expected
that this annex may be augmented or superceded by future efforts
outside of the scope of the IS-IS specification.
A.1 Inter-Domain Information Type
As specified in sections 3.4 and 5.3, the IDRPI field consists of a
one-octet inter-domain information type field, plus a variable
external information field. This section specifies initial values for
the inter-domain information type field. Other values for inter-
domain information type will be assigned and maintained in future
versions of the "Assigned Numbers" RFC.
The following types have been assigned:
Type = 0 reserved
Type = 1 local (uses routing-domain specific format)
Type = 2 AS Number Tag
Type = 1 indicates that the inter-domain routing protocol information
uses a format which is local to the routing domain.
Type = 2 indicates that the inter-domain routing protocol information
includes autonomous system information used to tag IP external
reachability information. In this case the inter-domain routing
protocol information entry must include a single AS number, which is
used to tag all subsequent External IP Reachability entries until the
end of the LSP, or until the next occurence of the Inter-Domain
Routing Protocol Information field.
A.2 Encoding
As specified in section 5.3.5, the IDPRI entry is encoded as a
variable length field, as follows:
x CODE - 131
x LENGTH - total length of the value field
x VALUE -
Callon [Page 52]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
No. of Octets
+-------------------------------+
| Inter-Domain Information Type | 1
+-------------------------------+
| External Information | VARIABLE
+-------------------------------+
INTER-DOMAIN INFORMATION TYPE indicates the type of the
external information which is encoded in the field.
EXTERNAL INFORMATION contains inter-domain routing protocol
information, and is passed transparently by the IS-IS protocol.
The Inter-domain information type field indicates the type of
information which is contained in the external information field, as
follow:
Type = 0 is reserved (must not be sent, and must be ignored on receipt).
Type = 1 indicates that the external information field contains
information which follows a locally specified format.
Type = 2 indicates that the external information field contains an
autonomous system number tag, to be applied to subsequent IP external
reachability information entries. In this case, this "inter-domain
routing protocol information" entry must contain precisely one 2
octet AS number. The AS tag is associated with subsequent IP External
Reachability entries, until the end of the LSP, or until the next
occurence of the Inter-Domain Routing Protocol Information field.
In this case, the VALUE contains the following:
x VALUE -
No. of Octets
+---------------------------------+
| Inter-Domain Information Type=2 | 1
+---------------------------------+
| Autonomous System Number | 2
+---------------------------------+
Callon [Page 53]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
Annex B
Encoding of Sequence Number Packets
The Integrated IS-IS protocol defined in this specification makes use
of the ISO Draft Proposed standard for Intra-domain routing (ISO DP
10589 [1]) as the base routing protocol, upon which IP support may be
added.
However, DP 10589 contains a bug regarding encoding of the variable
length fields in Sequence Number Packets. In particular, DP 10589
encodes the variable length fields in SNPs in a manner which is not
flexible (additional variable length fields cannot be defined for
sequence number packets), and which is inconsistent with the encoding
of the variable length fields in all other IS-IS and ES-IS packets.
The encoding of the variable length fields in SNPs is expected to be
fixed in future versions of 10589. Also, this bug represents the only
expected change to 10589 which cannot be made backward compatible
with existing DP 10589 implementations. For these reasons, the
current version of the Integrated IS-IS will use the anticipated
future encoding of the variable length part of the SNPs. This should
allow future versions of this specification to be compatible with
implementations based on this specification.
This annex specifies the encoding of SNPs, as amended to fix the
encoding of variable length fields. This annex is an integral part of
the Integrated IS-IS specification.
The encoding of SNPs for OSI-only use is shown in this section. For
IP-only or Integrated use, the additional variable length fields
specified in sections 5.3.6 through 5.3.9 are also applicable to
SNPs.
Callon [Page 54]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
B.1 Level 1 Complete Sequence Numbers PDU
No. of Octets
+--------------------------------+
| INTRA-DOMAIN ROUTEING | 1
| PROTOCOL DISCRIMINATOR |
+--------------------------------+
| LENGTH INDICATOR | 1
+--------------------------------+
| VERSION/PROTOCOL ID EXT | 1
+--------------------------------+
| RESERVED | 1
+--------------------------------+
| R | R | R | TYPE | 1
+--------------------------------+
| VERSION | 1
+--------------------------------+
| ECO | 1
+--------------------------------+
| USER ECO | 1
+--------------------------------+
| PDU LENGTH | 2
+--------------------------------+
| SOURCE ID | 7
+--------------------------------+
| START LSP ID | 8
+--------------------------------+
| END LSP ID | 8
+================================+====================
| VARIABLE LENGTH FIELDS | VARIABLE
+--------------------------------+
- INTRADOMAIN ROUTEING PROTOCOL DISCRIMINATOR - architectural constant
- LENGTH INDICATOR - Header Length in octets (33.)
- VERSION/PROTOCOL ID EXTENSION - 1
- RESERVED - transmitted as 0, ignored on receipt
- TYPE (bits 1 through 5) - 24. Note bits 6, 7 and 8 are Reserved,
which means they are transmitted as 0 and ignored on receipt.
- VERSION - 1
- ECO - transmitted as zero, ignored on receipt
Callon [Page 55]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
- USER ECO - transmitted as zero, ignored on receipt
- PDU LENGTH - Entire Length of this PDU, in octets, including header
- SOURCE ID - 7 octet ID of Intermediate System (with zero Circuit ID)
generating this Sequence Numbers PDU.
- START LSP ID - 8 octet ID of first LSP in the range covered by this
Complete Sequence Numbers PDU.
- END LSP ID - 8 octet ID of last LSP in the range covered by this
Complete Sequence Numbers PDU.
- VARIABLE LENGTH FIELDS - fields of the form:
No. of Octets
+--------------------------------+
| CODE | 1
+--------------------------------+
| LENGTH | 1
+--------------------------------+
| VALUE | LENGTH
+--------------------------------+
Any codes in a received CSNP that are not recognised are ignored.
Currently defined codes are:
7 LSP Entries -- This may appear multiple times. The option fields,
if they appear more than once, shall appear sorted into ascending
LSPID order.
x CODE - 9
x LENGTH - total length of the value field.
x VALUE - a list of LSP entries of the form:
Callon [Page 56]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
No. of Octets
+--------------------------------+
| REMAINING LIFETIME | 2
+--------------------------------+
| LSP ID | 8
+--------------------------------+
| LSP SEQ NUMBER | 4
+--------------------------------+
| CHECKSUM | 2
+--------------------------------+
: :
: :
+--------------------------------+
| REMAINING LIFETIME | 2
+--------------------------------+
| LSP ID | 8
+--------------------------------+
| LSP SEQ NUMBER | 4
+--------------------------------+
| CHECKSUM | 2
+--------------------------------+
7 REMAINING LIFETIME - Remaining Lifetime of LSP.
7 LSP ID - 8 octet ID of the LSP to which this entry refers.
7 LSP SEQ NUMBER - Sequence number of LSP.
7 CHECKSUM - Checksum reported in LSP.
The entries shall be sorted into ascending LSPID order (the LSP
number octet of the LSPID is the least significant octet).
Callon [Page 57]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
B.2 Level 2 Complete Sequence Numbers PDU
No. of Octets
+--------------------------------+
| INTRA-DOMAIN ROUTEING | 1
| PROTOCOL DISCRIMINATOR |
+--------------------------------+
| LENGTH INDICATOR | 1
+--------------------------------+
| VERSION/PROTOCOL ID EXT | 1
+--------------------------------+
| RESERVED | 1
+--------------------------------+
| R | R | R | TYPE | 1
+--------------------------------+
| VERSION | 1
+--------------------------------+
| ECO | 1
+--------------------------------+
| USER ECO | 1
+--------------------------------+
| PDU LENGTH | 2
+--------------------------------+
| SOURCE ID | 7
+--------------------------------+
| START LSP ID | 8
+--------------------------------+
| END LSP ID | 8
+================================+====================
| VARIABLE LENGTH FIELDS | VARIABLE
+--------------------------------+
- INTRADOMAIN ROUTEING PROTOCOL DISCRIMINATOR - architectural constant
- LENGTH INDICATOR - Header Length in octets (33.)
- VERSION/PROTOCOL ID EXTENSION - 1
- RESERVED - transmitted as 0, ignored on receipt
- TYPE (bits 1 through 5) - 25. Note bits 6, 7 and 8 are Reserved,
which means they are transmitted as 0 and ignored on receipt.
- VERSION - 1
- ECO - transmitted as zero, ignored on receipt
Callon [Page 58]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
- USER ECO - transmitted as zero, ignored on receipt
- PDU LENGTH - Entire Length of this PDU, in octets, including header
- SOURCE ID - 7 octet ID of Intermediate System (with zero Circuit ID)
generating this Sequence Numbers PDU.
- START LSP ID - 8 octet ID of first LSP in the range covered by this
Complete Sequence Numbers PDU.
- END LSP ID - 8 octet ID of last LSP in the range covered by this
Complete Sequence Numbers PDU.
- VARIABLE LENGTH FIELDS - fields of the form:
No. of Octets
+--------------------------------+
| CODE | 1
+--------------------------------+
| LENGTH | 1
+--------------------------------+
| VALUE | LENGTH
+--------------------------------+
Any codes in a received CSNP that are not recognised are ignored.
Currently defined codes are:
7 LSP Entries -- this may appear multiple times. The option fields,
if they appear more than once, shall appear sorted into ascending
LSPID order.
x CODE - 9
x LENGTH - total length of the value field.
x VALUE - a list of LSP entries of the form:
Callon [Page 59]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
No. of Octets
+--------------------------------+
| REMAINING LIFETIME | 2
+--------------------------------+
| LSP ID | 8
+--------------------------------+
| LSP SEQ NUMBER | 4
+--------------------------------+
| CHECKSUM | 2
+--------------------------------+
: :
: :
+--------------------------------+
| REMAINING LIFETIME | 2
+--------------------------------+
| LSP ID | 8
+--------------------------------+
| LSP SEQ NUMBER | 4
+--------------------------------+
| CHECKSUM | 2
+--------------------------------+
7 REMAINING LIFETIME - Remaining Lifetime of LSP.
7 LSP ID - 8 octet ID of the LSP to which this entry refers.
7 LSP SEQ NUMBER - Sequence number of LSP.
7 CHECKSUM - Checksum reported in LSP.
The entries shall be sorted into ascending LSPID order (the LSP
number octet of the LSPID is the least significant octet).
Callon [Page 60]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
B.3 Level 1 Partial Sequence Numbers PDU
No. of Octets
+--------------------------------+
| INTRA-DOMAIN ROUTEING | 1
| PROTOCOL DISCRIMINATOR |
+--------------------------------+
| LENGTH INDICATOR | 1
+--------------------------------+
| VERSION/PROTOCOL ID EXT | 1
+--------------------------------+
| RESERVED | 1
+--------------------------------+
| R | R | R | TYPE | 1
+--------------------------------+
| VERSION | 1
+--------------------------------+
| ECO | 1
+--------------------------------+
| USER ECO | 1
+--------------------------------+
| PDU LENGTH | 2
+--------------------------------+
| SOURCE ID | 7
+================================+====================
| VARIABLE LENGTH FIELDS | VARIABLE
+--------------------------------+
- INTRADOMAIN ROUTEING PROTOCOL DISCRIMINATOR - architectural constant
- LENGTH INDICATOR - Header Length in octets (17.)
- VERSION/PROTOCOL ID EXTENSION - 1
- RESERVED - transmitted as 0, ignored on receipt
- TYPE (bits 1 through 5) 26. Note bits 6, 7 and 8 are Reserved,
which means they are transmitted as 0 and ignored on receipt.
- VERSION - 1
- ECO - transmitted as zero, ignored on receipt
- USER ECO - transmitted as zero, ignored on receipt
- PDU LENGTH - Entire Length of this PDU, in octets, including header
- SOURCE ID - 7 octet ID of Intermediate system (with zero Circuit ID)
Callon [Page 61]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
generating this Sequence Numbers PDU.
- VARIABLE LENGTH FIELDS - fields of the form:
No. of Octets
+--------------------------------+
| CODE | 1
+--------------------------------+
| LENGTH | 1
+--------------------------------+
| VALUE | LENGTH
+--------------------------------+
Any codes in a received PSNP that are not recognised are ignored.
Currently defined codes are:
7 LSP Entries - this may appear multiple times. The option fields,
if they appear more than once, shall appear sorted into ascending
LSPID order.
x CODE - 9
x LENGTH - total length of the value field.
Callon [Page 62]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
x VALUE - a list of LSP entries of the form:
No. of Octets
+--------------------------------+
| REMAINING LIFETIME | 2
+--------------------------------+
| LSP ID | 8
+--------------------------------+
| LSP SEQ NUMBER | 4
+--------------------------------+
| CHECKSUM | 2
+--------------------------------+
: :
: :
+--------------------------------+
| REMAINING LIFETIME | 2
+--------------------------------+
| LSP ID | 8
+--------------------------------+
| LSP SEQ NUMBER | 4
+--------------------------------+
| CHECKSUM | 2
+--------------------------------+
7 REMAINING LIFETIME - Remaining Lifetime of LSP.
7 LSP ID - 8 octet ID of the LSP to which this entry refers.
7 LSP SEQ NUMBER - Sequence number of LSP.
7 CHECKSUM - Checksum reported in LSP.
The entries shall be sorted into ascending LSPID order (the LSP number
octet of the LSPID is the least significant octet).
Callon [Page 63]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
B.4 Level 2 Partial Sequence Numbers PDU
No. of Octets
+--------------------------------+
| INTRA-DOMAIN ROUTEING | 1
| PROTOCOL DISCRIMINATOR |
+--------------------------------+
| LENGTH INDICATOR | 1
+--------------------------------+
| VERSION/PROTOCOL ID EXT | 1
+--------------------------------+
| RESERVED | 1
+--------------------------------+
| R | R | R | TYPE | 1
+--------------------------------+
| VERSION | 1
+--------------------------------+
| ECO | 1
+--------------------------------+
| USER ECO | 1
+--------------------------------+
| PDU LENGTH | 2
+--------------------------------+
| SOURCE ID | 7
+================================+====================
| VARIABLE LENGTH FIELDS | VARIABLE
+--------------------------------+
- INTRADOMAIN ROUTEING PROTOCOL DISCRIMINATOR - architectural constant
- LENGTH INDICATOR - Header Length in octets (17.)
- VERSION/PROTOCOL ID EXTENSION - 1
- RESERVED - transmitted as 0, ignored on receipt
- TYPE (bits 1 through 5) - 27. Note bits 6, 7 and 8 are Reserved,
which means they are transmitted as 0 and ignored on receipt.
- VERSION - 1
- ECO - transmitted as zero, ignored on receipt
- USER ECO - transmitted as zero, ignored on receipt
- PDU LENGTH - Entire Length of this PDU, in octets, including header
- SOURCE ID - 7 octet ID of Intermediate system (with zero Circuit ID)
Callon [Page 64]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
generating this Sequence Numbers PDU.
- VARIABLE LENGTH FIELDS - fields of the form:
No. of Octets
+--------------------------------+
| CODE | 1
+--------------------------------+
| LENGTH | 1
+--------------------------------+
| VALUE | LENGTH
+--------------------------------+
Any codes in a received PSNP that are not recognised are ignored.
Currently defined codes are:
7 LSP Entries -- this may appear multiple times. The option fields,
if they appear more than once, shall appear sorted into ascending
LSPID order.
x CODE - 9
x LENGTH - total length of the value field.
x VALUE - a list of LSP entries of the form:
Callon [Page 65]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
No. of Octets
+--------------------------------+
| REMAINING LIFETIME | 2
+--------------------------------+
| LSP ID | 8
+--------------------------------+
| LSP SEQ NUMBER | 4
+--------------------------------+
| CHECKSUM | 2
+--------------------------------+
: :
: :
+--------------------------------+
| REMAINING LIFETIME | 2
+--------------------------------+
| LSP ID | 8
+--------------------------------+
| LSP SEQ NUMBER | 4
+--------------------------------+
| CHECKSUM | 2
+--------------------------------+
7 REMAINING LIFETIME - Remaining Lifetime of LSP.
7 LSP ID - 8 octet ID of the LSP to which this entry refers.
7 LSP SEQ NUMBER -Sequence number of LSP.
7 CHECKSUM - Checksum reported in LSP.
The entries shall be sorted into ascending LSPID order (the LSP
number octet of the LSPID is the least significant octet).
Callon [Page 66]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
Annex C
Dijkstra Calculation and Forwarding
Annex C.2 of ISO DP 10589 [1] specifies the SPF (Dikskstra) algorithm
for calculating routes with the IS-IS routing protocol. This annex
specifies modifications to the SPF algorithm for supporting IP and
dual routing, and specifies a compatible method for forwarding IP
packets. This will result in an order of preference of routes which
is compatible with that specified in section 3.10.
This annex is included for informational purposes.
C.1 SPF Algorithm for IP and Dual Use
This section specifies an SPF Algorithm for calculating routes with
the IS-IS routing protocol, for support of both TCP/IP and OSI. This
is based on an extention to the algorithm specified in annex C.2 of
ISO DP 10589 [1].
An algorithm invented by Dijkstra known as shortest path first (SPF)
is used as the basis for the route calculation. It has a
computational complexity of the square of the number of nodes, which
can be decreased to the number of links in the domain times the log
of the number of nodes for sparse networks (networks which are not
highly connected).
A number of additional optimizations are possible:
1) If the routing metric is defined over a small finite field (as in
this standard), the factor of log n may be removed by using data
structures which maintain a separate list of systems for each value
of the metric rather than sorting the systems by logical distance.
2) Updates can be performed incrementally without requiring a complete
recalculation. However, a full update must be done periodically to
ensure recovery from data corruption, and studies suggest that with
a very small number of link changes (perhaps 2) the expected
computation complexity of the incremental update exceeds the
complete recalculation. Thus, this annex specifies the algorithm
only for the full update.
3) If only End System LSP information has changed, it is not necessary
to re-compute the entire Dijkstra tree. If the proper data
structures are used, End Systems (including IP reachability
entries) may be attached and detached as leaves of the tree and
their forwarding information base entries altered as appropriate.
The original SPF algorithm does not support load splitting over
Callon [Page 67]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
multiple paths. The algorithm in this annex does permit load
splitting by identifying a set of equal cost paths to each
destination rather than a single least cost path.
C.1.1 Databases
PATHS -- This represents an acyclic directed graph of shortest paths
from the system S performing the calculation. It is stored as a set
of triples of the form <N,d(N),{Adj(N)}>, where:
N is a system identifier. In the level 1 algorithm, N is a
6 octet ID for OSI end systems, a 7 octet ID for routers, or
an 8 octet IP Internal Reachability Information entry. For a
router which is not a pseudonode, it is the 6 octet system ID,
with a 0 appended octet. For a pseudonode it is a true 7 octet
quantity, comprised of the 6 octet Designated Intermediate
System ID and the extra octet assigned by the Destinated Router.
The IP Internal Reachability Information entries consist of a
4 octet IP address plus a 4 octet subnet mask, and will always
be a leaf, i.e., "End System" in PATHS.
In the level 2 algorithm, N is either a 7 octet router or
pseudonode ID (as in the level 1 algorithm); a variable
length OSI address prefix; an 8 octet IP Internal Reachability
Information Entry, or an 8 octet IP External Reachability
Information entry. The variable length OSI address prefixes,
and 8 octet IP Reachability Information entries will always
be a leaf, i.e., "End System" in PATHS. As above, the IP
Reachability Information entries consist of an [IP address,
subnet mask] combination.
d(N) is N's distance from S (i.e., the total metric value
from N to S).
{Adj(N)} is a set of valid adjacencies that S may use for
forwarding to N.
When a system is placed on PATHS, the path(s) designated by its
position in the graph is guaranteed to be a shortest path.
TENT -- This is a list of triples of the form <N,d(N),{Adj(N)}>,
where N, d(N), and {Adj(N)} are as defined above for PATHS.
TENT can intuitively be thought of as a tentative placement
of a system in PATHS. In other words, the triple <N,x,{A}>
in TENT means that if N were placed in PATHS, d(N) would be x,
but N cannot be placed on PATHS until is is guaranteed that
no path shorter than x exists.
Callon [Page 68]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
Similarly, the triple <N,x,{A,B}> in TENT means that if N
were placed in PATHS, then d(N) would be x via either
adjacency A or B.
Note: It is suggested that the implementation maintain the database
TENT as a set of list of triples of the form <*,Dist,*>, sorted by
distance Dist. In addition, it is necessary to be able to process
those systems which are pseudonodes before any non-pseudonodes at the
same distance Dist.
The 8 octet system identifiers which specify IP reachability entries
must always be distinguishable from other system identifiers. As
specified in section 3.10, two IP reachability entries which differ
only in the subnet mask are still considered to be separate, and will
therefore have distinct system identifiers N. The SPF algorithm will
therefore calculate routes to each such entry, and the correct entry
will be selected in the forwarding process.
C.1.2 Use of Metrics in the SPF Algorithm
Internal metrics are not comparable to external metrics. For external
routes (routes to destinations outside of the routing domain), the
cost d(N) of the path from N to S may include both internal and
external metrics. d(N) may therefore be maintained as a two-
dimensioned vector quantity (specifying internal and external metric
values).
d(N) is initialized to [internal metric = 0, external metric = 0].
In incrementing d(N) by 1, if the internal metric value is less than
the maximum value MaxPathMetric, then the internal metric value is
incremented by one and the external metric value left unchanged; if
the internal metric value is equal to the maximum value
MaxPathMetric, then the internal metric value is set to 0 and the
external metric value is incremented by 1. Note that this can be
implemented in a straightforward manner by maintaining the external
metric as the high order bits of the distance.
In the code of the algorithm below, the current path length is held
in the variable "tentlength". This variable is a two-dimensional
quantity tentlength=[internal metric, external metric], and is used
for comparing the current path length with d(N) as described above.
Tentlength is incremented in the same manner as d(N).
C.1.3 Overview of the Algorithm
The basic algorithm, which builds PATHS from scratch, starts out by
putting the system doing the computation on PATHS (no shorter path to
Callon [Page 69]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
SELF can possibly exist). TENT is then pre-loaded from the local
adjacency database.
Note that a system is not placed on PATHS unless no shorter path to
that system exists. When a system N is placed on PATHS, the path to
each neighbor M of N, through N, is examined, as the path to N plus
the link from N to M. If <M,*,*> is in PATHS, this new path will be
longer, and thus ignored.
If <M,*,*> is in TENT, and the new path is shorter, the old entry is
removed from TENT and the new path is placed in TENT. If the new path
is the same length as the one in TENT, then the set of potential
adjacencies {Adj(M)} is set to the union of the old set (in TENT) and
the new set {Adj(N)}. If M is not in TENT, then the path is added to
TENT.
Next the algorithm finds the triple <N,x,{Adj(N)}> in TENT, with
minimal x. Note: This is done efficiently because of the optimization
described above. When the list of triples for distance Dist is
exhausted, the algorithm then increments Dist until it finds a list
with a triple of the form <*,Dist,*>.
N is placed in PATHS. We know that no path to N can be shorter than x
at this point because all paths through systems already in PATHS have
already been considered, and paths through systems in TENT still have
to be greater than x because x is minimal in TENT.
When TENT is empty, PATHS is complete.
Note that external metrics can only occur in "IP External
Reachability Information" entries, which correspond to a leaf (i.e.,
End System in PATHS). Any route utilizing an entry with an external
metric will always be considered to be less desireable than any entry
which uses an internal metric. This implies that in the addition of
systems to PATHS, all systems reachable via internal routes are
always added before any system reachable via external routes.
C.1.4 The Algorithm
The Decision Process Algorithm must be run once for each supported
routing metric (i.e., for each supported Type of Service). A level 1
router runs the algorithm using the level 1 LSP database to compute
level 1 paths (for those level 1 routers which are not level 2
routers, this includes the path to the nearest attached level 2
router). Level 2 routers also separately run the algorithm using the
level 2 LSP database to compute level 2 paths. IP-capable level 2
routers must keep level 2 internal IP routes separate from level 2
external IP routes.
Callon [Page 70]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
Note that this implies that routers which are both level 1 and level
2 routers, and which support all four routing metrics, must run the
SPF algorithm 8 times (assuming partition repair is not implemented).
If this system is a Level 2 Router which supports the partition
repair optional function the Decision Process algorithm for computing
Level 1 paths must be run twice for the default metric. This first
execution is done to determine which of the area's
manualAreaAddresses are reachable in this partition, and to elect a
Partition Designated Level 2 Router for the partition. The partition
Designated Level 2 Router will determine if the area is partitioned
and will create virtual Level 1 links to the other Partition
Designated Level 2 Routers in the area in order to repair the Level 1
partition. This is further described in section 7.2.10 of [1].
The SPF algorithm specified here will calculate routes for both OSI
and IP. In particular, routes are calculated to all system
identifiers N, where N may specify an OSI End System, the OSI address
of a router, or an IP reachability entry. In computing the forwarding
database, it is an implementation specific issue whether the IP
forwarding database is kept separately from the OSI forwarding
database. Where appropriate, this annex will refer separately to
entries in these two forwarding data bases. This is not meant to
preclude any specific implementation method.
OSI and IP use separate mechanisms to determine whether a packet is
in the area (in particular, OSI makes use of area addresses, and IP
determines that a destination is not in an area by looking in the
level 1 forwarding database and determining that no entry exists for
that destination within the area). The route to the nearest level 2
router will result in separate entries in the forwarding database for
OSI and IP. For IP, the route to the nearest attached level 2 router
may be entered in the forwarding database as a default route (i.e., a
route with a subnet mask of all 0).
One approach would be to put the results of each Dijkstra algorithm
in a separate forwarding database. For a router which supports both
level 1 and level 2 routing (including level 2 internal and level 2
external routes), and which supports all four types of service, this
would result in twelve separate forwarding databases for IP.
Implementations may choose to minimize the number of forwarding
databases by combining the information from the multiple Dijkstra
calculations into a single database per supported TOS. This is
discussed in section C.2 below.
The SPF algorithm specified in section C.2.3 of [1] is amended to
appear as follows:
Callon [Page 71]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
Step 0: Initialize TENT and PATHS to empty. Initialize tentlength to
[internalmetric=0, externalmetric=0].
(tentlength is the pathlength of elements in TENT that we are
examining.)
1) Add <SELF,0,W> to PATHS, where W is a special value indicating
traffic to SELF is passed up to internal processes (rather than
forwarded).
2) Now pre-load TENT with the local adjacency database (Each
entry made to TENT must be marked as being either an End System
or a router to enable the check at the end of Step 2 to be made
correctly - Note that each local IP reachability entry is
included as an adjacency, and is marked as being an End System).
For each adjacency Adj(N) (including level 1 OSI Manual
Adjacencies, or level 2 OSI enabled reachable addresses, and
IP reachability entries) on enabled circuits, to system N of
SELF in state "Up" compute:
d(N) = cost of the parent circuit of the adjacency (N),
obtained from metric.k , where k = one of {default metric,
delay metric, monetary metric, error metric}
Adj(N) = the adjacency number of the adjacency to N
3) If a triple <N,x,{Adj(M)}> is in TENT, then:
If x = d(N), then {Adj(M)} <--- {Adj(M)} U {Adj(N)}.
4) If N is a router or an OSI End System entry, and there are now
more adjacencies in {Adj(M)} than maximumPathSplits, then remove
excess adjacencies as described in Clause 7.2.7 of [1]. If N
is an IP Reachability Entry, then excess adjacencies may be
removed as desired. This will not effect the correctness of
routing, but may eliminate the determinism for IP routes (i.e.,
IP packets still follow optimal routes within an area, but
where multiple equally good routes exist, will not necessarily
follow precisely the route that any one particular router
would have anticipated).
5) If x < d(N), do nothing.
6) If x > d(N), remove <N,x,{Adj(M)}> from TENT and add the triple
<N,d(N),{Adj(N)}>.
7) If no triple <N,x,{Adj(M)}> is in TENT, then add <N,d(N),{Adj(N)}>
to TENT.
Callon [Page 72]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
8) Now add systems to which the local router does not have adjacencies,
but which are mentioned in neighboring pseudonode LSPs. The
adjacency for such systems is set to that of the designated router.
Note that this does not include IP reachability entries from
neighboring pseudonode LSPs. In particular, the pseudonode LSPs
do not include IP reachability entries.
9) For all broadcast circuits in state "On", find the pseudonode
LSP for that circuit (specifically, the LSP with number zero and
with the first 7 octets of LSPID equal to LnCircuitID for that
circuit, where n is 1 (for level 1 routing) or 2 (level 2
routing)). If it is present, for all the neighbors N reported in
all the LSPs of this pseudonode which do not exist in TENT add
an entry <N,d(N),{Adj(N)}> to TENT, where:
d(N) = metric.k of the circuit.
Adj(N) = the adjacency number of the adjacency to the DR.
10) Go to Step 2.
Step 1: Examine the zeroeth link state PDU of P, the system just
placed on PATHS (i.e., the LSP with the same first 7 octets of LSPID
as P, and LSP number zero).
1) If this LSP is present, and the "Infinite Hippity Cost" bit is
clear, then for each LSP of P (i.e., all LSPs with the same
first 7 octets of LSPID and P, irrespective of the value of
LSP number) compute:
dist(P,N) = d(P) + metric.k(P,N)
for each neighbor N (both End System and router) of the system P. If
the "Infinite Hippity Cost" bit is set, only consider the End System
neighbors of the system P. Note that the End Systems neighbors of the
system P includes IP reachable address entries included in the LSPs
from system P. Here, d(P) is the second element of the triple
<P,d(P),{Adj(P)}>
and metric.k(P,N) is the cost of the link from P to N as reported in
P's link state PDU.
2) If dist(P,N) > MaxPathMetric, then do nothing.
3) If <N,d(N),{Adj(N)}> is in PATHS, then do nothing.
Note: d(N) must be less than dist(P,N), or else N would not
have been put into PATHS. An additional sanity check may be
Callon [Page 73]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
done here to ensure that d(N) is in fact less than dist(P,N)
4) If a triple <N,x,{Adj(N)}> is in TENT, then:
a) If x = dist(P,N), then {Adj(N)} <-- {Adj(N)} U {Adj(P)}.
b) If N is a router or an OSI end system, and there are now more
adjacencies in {Adj(N)} than maximumPath Splits, then remove
excess adjacencies, as described in clause 7.2.7 of [1]. For
IP Reachability Entries, excess adjacencies may be removed as
desired. This will not effect the correctness of routing, but
may eliminate the determinism for IP routes (i.e., IP packets
will still follow optimal routes within an area, but where
multiple equally good routes exist, will not necessarily follow
precisely the route that any one particular router would have
anticipated).
c) if x < dist(P,N), do nothing.
d) if x > dist(P,N), remove <N,x,{Adj(N)}> from TENT, and add
<N,dist(P,N),{Adj(P)}>
5) if no triple <N,x,{Adj(N)}> is in TENT, then add
<N,dist(P,N),{Adj(P)}> to TENT.
Step 2: If TENT is empty, stop. Else:
1) Find the element <P,x,{Adj(P)}>, with minimal x as follows:
a) If an element <*,tentlength,*> remains in TENT in the list for
tentlength, choose that element. If there are more than one
elements in the list for tentlength, choose one of the elements
(if any) for a system which is a pseudonode in preference to one
for a non-pseudonode. If there are no more elements in the list
for tentlength, increment tentlength and repeat Step 2.
b) Remove <P,tentlength,{Adj(P)}> from TENT.
c) Add <P,d(P),{Adj(P)}> to PATHS.
d) If this is the Level 2 Decision Process running, and the system
just added to PATHS listed itself as Partition Designated Level 2
Intermediate system, then additionally add <AREA.P,d(P),{Adj(P)}>
to PATHS, where AREA.P is the Network Entity Title of the other
end of the Virtual Link, obtained by taking the first AREA
listed in P's LSP and appending P's ID.
e) If the system just added to PATHS was an end system, go to
Callon [Page 74]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
step 2. Else go to Step 1.
NOTE - In the level 2 context, the "End Systems" are the set of
Reachable Address Prefixes (for OSI), the set of Area Addresses with
zero cost (again, for OSI), plus the set of IP reachability entries
(including both internal and external).
C.2 Forwarding of IP packets
The SPF algorithm specified in section C.1 may be used to calculate
(logically) separate IP forwarding tables for each type of service,
and for level 1, level 2 internal, and level 2 external routes.
Section C.2.1 describes how to forward IP packets, based on these
multiple forwarding databases. Section C.2.2 describes how the
multiple forwarding databases can be combined into a single
forwarding database per supported TOS.
C.2.1 Basic Method for Forwarding IP packets
For level 1-only routers:
- Determine if the IP destination address matches any entry in the
level 1 forwarding table for the specified TOS.
- Determine if the IP destination address matches any entry in the
level 1 forwarding table for the default TOS.
- If default TOS resulted in more specific entry, forward according
to default TOS.
- If equally specific entries found, or specified TOS resulted in
more specific entry, forward according to specified TOS
- If no entry was found (which includes no default route entry), then
destination is unreachable.
Note: For level 1 only routers, the route to the nearest attached
level 2 router will be entered into the forwarding database as a
default route (i.e., a route with a subnet mask which is all 0). Thus
this last event (no entry found) can occur only if there is no
attached level 2 router reachable in the area.
For routers which are both level 1 and level 2 routers:
- Determine if the IP destination address matches any entry in the
level 1 forwarding table for the specified TOS.
- Determine if the IP destination address matches any entry in the
Callon [Page 75]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
level 1 forwarding table for the default TOS.
- If default TOS resulted in more specific entry (i.e., more bits in
the subnet mask take the value 1), forward according to default TOS.
- If equally specific entries found, or specified TOS resulted in
more specific entry, forward according to specified TOS
- If no entry found:
- Determine if the IP destination address matches any entry in the
level 2 internal forwarding table for the specified TOS.
- Determine if the IP destination address matches any entry in the
level 2 internal forwarding table for the default TOS.
- If default TOS resulted in more specific entry, forward according
to default TOS.
- If equally specific entries found, or specified TOS resulted in
more specific entry, forward according to specified TOS
- If no entry found:
- Determine if the IP destination address matches any entry in the
level 2 external forwarding table for the specified TOS.
- Determine if the IP destination address matches any entry in the
level 2 external forwarding table for the default TOS.
- If default TOS resulted in more specific entry, forward according
to default TOS.
- If equally specific entries found, or specified TOS resulted in
more specific entry, forward according to specified TOS
- If no entry is found, then destination is unreachable
For level 2-only routers, the above algorithm can be used, except
since there is no level 1 forwarding database, the corresponding
steps can be skipped.
As discussed in section 3.10.2, for level 2 routers which are
announcing manually configured summary addresses in their level 2
LSPs, in some cases there will exist IP addresses which match the
manually configured addresses, but which do not match any addresses
which are reachable via level 1 routing in the area. Packets to such
addresses are handled according to the rules specified in section
Callon [Page 76]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
3.10.2. This may be accomplished by adding the manually configured
[IP address, subnet mask] entry to the level 2 forwarding database
(for the appropriate TOS), with a special "next hop" address which
specifies that packets for which this entry is selected are to be
discarded. This will work correctly because more desireable entries
(such as delivering the packet via level 1 routing to the correct
destination, or a more specific level 2 route) will automatically
take precedence according to the forwarding rules specified above.
Less desireable routes (such as using a level 2 external route to the
"default route" entry) are not possible because other level 2 routers
will believe the summary addresses advertised by this router.
C.2.2 Reduction of IP Forwarding Databases
The multiple forwarding databases used in the basic forwarding method
in section C.2.1 can be reduced, by combining the multiple databases
into one database for each supported TOS.
For reduction of IP forwarding databases, it is assumed that for any
two overlapping address entries, either the entries are identical, or
one range contains the other. In other words, for any two [IP
address, subnet mask] entries A and B, if there is at least one IP
address which matches both entries, then either: (i) the two entries
are identical; or (ii) entry A contains entry B (i.e., any IP address
which matches entry B also matches entry A); or (iii) entry B
contains entry A (any IP address which matches entry A also matches
entry B).
Non-contiguous subnet masks can be configured to violate this
assumption. For example, consider the two entries:
- A=[address="01010101 00000101 00000000 00000000",
mask="11111111 00001111 00000000 00000000"]
- B=[address="01010101 01010000 00000000 00000000",
mask="11111111 11110000 00000000 00000000"]
In this case neither entry contains the other. Specifically;
- there are IP addresses which match both A and B (e.g.,
"01010101 01010101 xxxxxxxx xxxxxxxx"),
- there are IP addresses which match A but not B (e.g.,
"01010101 11110101 xxxxxxxx xxxxxxxx")
- there are IP addresses which match B but not A (e.g.,
"01010101 01011111 xxxxxxxx xxxxxxxx").
Callon [Page 77]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
The reduction of the multiple forwarding databases for each TOS to a
single database for each TOS is based on the use of "best match"
routing, combined with reduction of the entries placed in the
forwarding database in order to eliminate entries which are not to be
selected (based on the order of preference of routes specified in
section 3.10). The specific algorithm for creation of the IP
forwarding database can be described as follows:
1) Make use of the the Dijkstra algorithm described in section C.1 to
create separate forwarding databases for each supported TOS for
level 1 routes, level 2 internal routes, and level 2 external
routes. (Note that each entry in the forwarding database will
specify an [IP address, subnet mask] combination, as well as the
next hop router for IP packets which match that entry).
2) For each level 1 route entry which has been placed in the level 1
IP forwarding database for a specific TOS, copy that entry into
the overall IP forwarding database for that TOS.
3) For each route entry X which has been placed in the level 2 internal
IP forwarding database for a specific TOS, search for overlapping
entries in the level 1 IP forwarding database for the specific TOS,
and also for the default TOS:
a) If there is any overlapping entry Y in the level 1 forwarding
database (for the specfic TOS, or for the default TOS) such
that either (i) Y contains X; or (ii) Y is identically specific
to X; then ignore entry X.
b) Otherwise, copy entry X into the overall IP forwarding database
for the specific TOS.
4) For each route entry X which has been placed in the level 2
external IP forwarding database for a specific TOS, search for
overlapping entries in the level 1 IP forwarding database for
the specific TOS, and for the default TOS, and the level 2
internal IP forwarding database for the specific TOS, and for
the default TOS.
a) If there is an overlapping entry Y such that either (i) Y
contains X; or (ii) Y is identically specific to X; then
ignore entry X.
b) Otherwise, copy entry X into the overall IP forwarding database
for the specific TOS.
This method will result in one forwarding database for each supported
TOS. The forwarding of packets can then be simplified to be as follows:
Callon [Page 78]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
1) For IP packets which map to the default TOS metric (or to an
unsupported TOS metric), search the default TOS forwarding
database and select the entry which has the most specific match.
Forward the packet accordingly.
2) For packets which map to a specific (non-default) TOS metric,
search the specific TOS forwarding database and select the entry
j which has the most specific match. Also search the default TOS
forwarding database and select the entry k which has the most
specific match. Forward the packet as follows:
a) If k is more specific than j, forward according to entry k
b) If j and k are equally specific, forward according to entry j
c) If j is more specific than k, forward according to entry j
Callon [Page 79]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
Annex D
Use of the Authentication Field
The use of the Authentication field is outside of the scope of this
specification. However, there is a urgent need for simple error
detection/authentication mechanisms (such as a simple password) to
protect against certain types of errors. This annex therefore
proposes a possible use of this field.
This annex is included for informational purposes.
D.1 Authentication Field in IS-IS packets
All IS-IS packets may optionally include the authentication field, as
described in sections 3.9 and 5 of this specification. As described
in section 5, the authentication field is encoded as a (Code, Length,
Value) triplet. This annex proposes that the contents of the Value
field consist of a one octet "Authentication Type" field, plus a
variable length "Authentication Information" field. A specific value
of the "Authentication Type" is assigned to passwords, transmitted in
the clear without encryption. The authentication field is encoded as
follows:
7 Authentication Information -- Information used to authenticate
the PDU
x CODE - 133
x LENGTH - total length of the value field
x VALUE -
No. of Octets
+--------------------------------+
| Authentication Type | 1
+--------------------------------+
| Authentication Information | VARIABLE
+--------------------------------+
The Authentication Type is assigned as follows:
Type = 0 reserved
Type = 1 simple password
Type > 1 reserved
Callon [Page 80]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
D.2 Authentication Type 1 - Simple Password
Using this authentication type, a variable length password is passed
in the clear (i.e., not encrypted) in the Authentication Information
field.
WARNING: The use of a simple password does not provide useful
protection against intentional misbehavior. In particular, since the
password is transmitted in the clear without encryption, it is easy
for a hostile system to intercept the passwords, and to transmit
authenticated packets. The use of simple passwords should be
considered only as a weak protection against accidental errors such
as accidental misconfiguration.
The password shall be configured on a per-link, per-area, and per-
domain basis. Specifically, when this form of authentication is used:
- IS-IS Hello and 9542 IS Hello packets shall contain the
per-link password
- Level 1 Link State Packets shall contain the per-area password
- Level 2 Link State Packets shall contain the per-domain password
- Level 1 Sequence Number Packets shall contain the per-area password
- Level 2 Sequence Number Packets shall contain the per-domain
password
Also, each of these three passwords shall be configured with: (i)
"Transmit Password", whose value is a single password, and (ii)
"Receive Passwords", whose value is a set of passwords. The transmit
password value is always transmitted. However, any password contained
in the receive password set will be accepted on receipt. This method
allows the graceful changing of passwords without temporary loss of
connectivity.
For example, consider the case that an area has the configured area
password "OLDAREAPASSWORD". In this case, the per-area transmit
password value is set to OLDAREAPASSWORD, and the per-area receive
password value is set to {OLDAREAPASSWORD}. Suppose that it is
desired to change the per-area password to "NEWERPASSWORD". The
first step would be to manually configure all of the routers in the
area to set the per-area receive password value to {OLDAREAPASSWORD,
NEWERPASSWORD}. When this step is complete, then all routers in the
area will still be using the old password OLDAREAPASSWORD in their
level 1 LSPs and SNPs. However, they will also accept the alternate
password NEWERPASSWORD. The second step would be to configure the
Callon [Page 81]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
routers in the area to set the per-area transmit password to
NEWERPASSWORD. When the second step is complete, then all routers
will be using the new value of the per-area password, but will accept
the old value as well. Finally, the third step is to change all
routers in the area to have the per-area receive password set to
{NEWERPASSWORD}.
By configuring transmit and receive values for the passwords in this
manner, it is possible to maintain continuous correct operation. For
example, in the middle of the second step in the above example, some
of the routers in the area will be transmitting level 1 LSPs and SNPs
using the old password OLDAREAPASSWORD, and some will be transmitting
level 1 LSPs and SNPs using the new password NEWERPASSWORD. However,
during the second step of the transition all routers in the area will
accept level 1 LSPs and SNPs using either password.
Callon [Page 82]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
Annex E
Interaction of the Integrated IS-IS with Brouters
A "brouter" is a device which operates an both a bridge and a router.
One possible type of brouter acts as a router for IP traffic, and
acts as a bridge for all other types of traffic.
Depending upon the manner in which a brouter is implemented, and
depending upon the network topology, there is an obscure bug which
can result from the interaction of the Integrated IS-IS protocol, and
brouters. This appendix gives an example of the bug, and proposes a
simple correction to the operation of brouters to correct the
problem.
This annex is included for informational purposes.
E.1 The Problem
Suppose that we have a brouter which treats IP packets as if it were
a normal IP router, and which treats all other packets as if it is a
bridge.
Suppose that two routers "X" and "Y" (which implement the integrated
IS-IS protocol), two Ethernets, and a brouter B are all connected as
follows:
| |
+----+---+ +----+---+
| Router | | Router |
| X | | Y |
+----+---+ +----+---+
| |
-----+------------+- -+------------+----
| |
+-+-----+-+
| Brouter |
| B |
+---------+
Here suppose that X and Y are running the Integrated IS-IS protocol,
and are both level 1 routers in the same area. Thus X and Y send IS-
IS Hello packets on the LAN. These Hello packets are received and
forwarded by the brouter (using normal bridge functions). Similarly,
X and Y receive each other's IS-IS LSP packets. In this way, it
appears to the Brouter that X and Y are exchanging OSI packets, and
so they are forwarded using normal bridge functions. It appears to X
Callon [Page 83]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
and Y as if they are on the same LAN, and so they learn each others
48-bit Ethernet addresses and exchange routing information.
Now, suppose that X receives an IP packet, which it needs to forward
via Y. Since X thinks that it and Y are on the same Ethernet, it just
forwards the IP packet directly, using normal Ethernet encapsulation
and using the 48-bit Ethernet address of Y as the destination address
in the Ethernet header. Brouter B, when thinking as a bridge says:
"this is an IP packet, I don't forward this as a bridge". Brouter B,
when thinking like an IP router says: "this is an IP packet, I know
how to forward IP packets. However, this is sent to an Ethernet
address which is not me, thus I will ignore it". The result is that
the IP packet does not get forwarded.
This problem relates directly to the fact that X and Y are exchanging
OSI packets to determine the connectivity of the path between them,
but then are trying to send IP packets over the path. Also, there is
a device between X and Y on the path which treats OSI and IP packets
differently.
Also note that this problem can also occur in more complex
topologies, whenever a brouter is treating OSI and IP packets in a
fundamentally different manner.
E.2 Possible Solutions
E.2.1 More Sophisticated Brouter
One solution is that brouter B needs to be a little more
sophisticated. In particular, it needs to use the following rules:
- For packets which are not IP packets, act as a bridge (this is the
same as before).
- For IP packets sent to an Ethernet broadcast or multicast address,
act as an IP router (this is also the same as before).
- For IP packets sent to my own Ethernet 48-bit address(es), act as
an IP router (this is also the same as before).
- For IP packets sent to a single station 48-bit address which is not
one of my addresses, act at a bridge (THIS IS NEW).
With this change, the IP packet transmitted from X to Y is forwarded
by the brouter, acting as a bridge. This allows the Brouter and the
multiprotocol routers to interoperate properly.
Callon [Page 84]
RFC 1195 OSI ISIS for IP and Dual Environments December 1990
E.2.2 Dual Router / Brouter
An alternate solution would be for the Brouter to route both OSI and
IP equally. If the Brouter used the integrated IS-IS for this
purpose, then it could be part of the same routing domain and
interoperate like any other dual router (except for the ability to
bridge other protocol suites). If it used other protocols for
routing OSI and IP, then it would need to be part of another routing
domain, and could interoperate with integrated IS-IS routers like any
other external router.
Callon [Page 85]
|