File: rfc1479.txt

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






Network Working Group                                     M. Steenstrup
Request for Comments: 1479                 BBN Systems and Technologies
                                                              July 1993


     Inter-Domain Policy Routing Protocol Specification: Version 1

Status of this Memo

   This RFC specifies an IAB standards track protocol 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.

Abstract

   We present the set of protocols and procedures that constitute
   Inter-Domain Policy Routing (IDPR).  IDPR includes the virtual
   gateway protocol, the flooding protocol, the route server query
   protocol, the route generation procedure, the path control protocol,
   and the data message forwarding procedure.

Contributors

   The following people have contributed to the protocols and procedures
   described in this document: Helen Bowns, Lee Breslau, Ken Carlberg,
   Isidro Castineyra, Deborah Estrin, Tony Li, Mike Little, Katia
   Obraczka, Sam Resheff, Martha Steenstrup, Gene Tsudik, and Robert
   Woodburn.

Table of Contents

   1. Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . 3
   1.1. Domain Elements . . . . . . . . . . . . . . . . . . . . . . . 3
   1.2. Policy. . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
   1.3. IDPR Functions. . . . . . . . . . . . . . . . . . . . . . . . 5
   1.3.1. IDPR Entities . . . . . . . . . . . . . . . . . . . . . . . 6
   1.4. Policy Semantics. . . . . . . . . . . . . . . . . . . . . . . 7
   1.4.1. Source Policies . . . . . . . . . . . . . . . . . . . . . . 7
   1.4.2. Transit Policies. . . . . . . . . . . . . . . . . . . . . . 8
   1.5. IDPR Message Encapsulation. . . . . . . . . . . . . . . . . . 9
   1.5.1. IDPR Data Message Format. . . . . . . . . . . . . . . . . .11
   1.6. Security. . . . . . . . . . . . . . . . . . . . . . . . . . .12
   1.7. Timestamps and Clock Synchronization. . . . . . . . . . . . .13
   1.8. Network Management. . . . . . . . . . . . . . . . . . . . . .14
   1.8.1. Policy Gateway Configuration. . . . . . . . . . . . . . . .17
   1.8.2. Route Server Configuration. . . . . . . . . . . . . . . . .18



Steenstrup                                                      [Page 1]

RFC 1479                     IDPR Protocol                     July 1993


   2. Control Message Transport Protocol. . . . . . . . . . . . . . .18
   2.1. Message Transmission. . . . . . . . . . . . . . . . . . . . .20
   2.2. Message Reception . . . . . . . . . . . . . . . . . . . . . .22
   2.3. Message Validation. . . . . . . . . . . . . . . . . . . . . .23
   2.4. CMTP Message Formats. . . . . . . . . . . . . . . . . . . . .24
   3. Virtual Gateway Protocol. . . . . . . . . . . . . . . . . . . .27
   3.1. Message Scope . . . . . . . . . . . . . . . . . . . . . . . .28
   3.1.1. Pair-PG Messages. . . . . . . . . . . . . . . . . . . . . .28
   3.1.2. Intra-VG Messages . . . . . . . . . . . . . . . . . . . . .29
   3.1.3. Inter-VG Messages . . . . . . . . . . . . . . . . . . . . .29
   3.1.4. VG Representatives. . . . . . . . . . . . . . . . . . . . .31
   3.2. Up/Down Protocol. . . . . . . . . . . . . . . . . . . . . . .31
   3.3. Implementation. . . . . . . . . . . . . . . . . . . . . . . .33
   3.4. Policy Gateway Connectivity . . . . . . . . . . . . . . . . .35
   3.4.1. Within a Virtual Gateway. . . . . . . . . . . . . . . . . .35
   3.4.2. Between Virtual Gateways. . . . . . . . . . . . . . . . . .37
   3.4.3. Communication Complexity. . . . . . . . . . . . . . . . . .40
   3.5. VGP Message Formats . . . . . . . . . . . . . . . . . . . . .41
   3.5.1. UP/DOWN . . . . . . . . . . . . . . . . . . . . . . . . . .41
   3.5.2. PG CONNECT. . . . . . . . . . . . . . . . . . . . . . . . .42
   3.5.3. PG POLICY . . . . . . . . . . . . . . . . . . . . . . . . .43
   3.5.4. VG CONNECT. . . . . . . . . . . . . . . . . . . . . . . . .44
   3.5.5. VG POLICY . . . . . . . . . . . . . . . . . . . . . . . . .45
   3.5.6. Negative Acknowledgements . . . . . . . . . . . . . . . . .46
   4. Routing Information Distribution. . . . . . . . . . . . . . . .47
   4.1. AD Representatives. . . . . . . . . . . . . . . . . . . . . .48
   4.2. Flooding Protocol . . . . . . . . . . . . . . . . . . . . . .48
   4.2.1. Message Generation. . . . . . . . . . . . . . . . . . . . .50
   4.2.2. Sequence Numbers. . . . . . . . . . . . . . . . . . . . . .52
   4.2.3. Message Acceptance. . . . . . . . . . . . . . . . . . . . .52
   4.2.4. Message Incorporation . . . . . . . . . . . . . . . . . . .54
   4.2.5. Routing Information Database. . . . . . . . . . . . . . . .56
   4.3. Routing Information Message Formats . . . . . . . . . . . . .57
   4.3.1. CONFIGURATION . . . . . . . . . . . . . . . . . . . . . . .57
   4.3.2. DYNAMIC . . . . . . . . . . . . . . . . . . . . . . . . . .62
   4.3.3. Negative Acknowledgements . . . . . . . . . . . . . . . . .63
   5. Route Server Query Protocol . . . . . . . . . . . . . . . . . .64
   5.1. Message Exchange. . . . . . . . . . . . . . . . . . . . . . .64
   5.2. Remote Route Server Communication . . . . . . . . . . . . . .65
   5.3. Routing Information . . . . . . . . . . . . . . . . . . . . .66
   5.4. Routes. . . . . . . . . . . . . . . . . . . . . . . . . . . .67
   5.5. Route Server Message Formats. . . . . . . . . . . . . . . . .67
   5.5.1. ROUTING INFORMATION REQUEST . . . . . . . . . . . . . . . .67
   5.5.2. ROUTE REQUEST . . . . . . . . . . . . . . . . . . . . . . .68
   5.5.3. ROUTE RESPONSE. . . . . . . . . . . . . . . . . . . . . . .71
   5.5.4. Negative Acknowledgements . . . . . . . . . . . . . . . . .72
   6. Route Generation. . . . . . . . . . . . . . . . . . . . . . . .73
   6.1. Searching . . . . . . . . . . . . . . . . . . . . . . . . . .74



Steenstrup                                                      [Page 2]

RFC 1479                     IDPR Protocol                     July 1993


   6.1.1. Implementation. . . . . . . . . . . . . . . . . . . . . . .75
   6.2. Route Directionality. . . . . . . . . . . . . . . . . . . . .78
   6.3. Route Database. . . . . . . . . . . . . . . . . . . . . . . .79
   6.3.1. Cache Maintenance . . . . . . . . . . . . . . . . . . . . .80
   7. Path Control Protocol and Data Message Forwarding Procedure . .80
   7.1. An Example of Path Setup. . . . . . . . . . . . . . . . . . .81
   7.2. Path Identifiers. . . . . . . . . . . . . . . . . . . . . . .84
   7.3. Path Control Messages . . . . . . . . . . . . . . . . . . . .85
   7.4. Setting Up and Tearing Down a Path. . . . . . . . . . . . . .87
   7.4.1. Validating Path Identifiers . . . . . . . . . . . . . . . .89
   7.4.2. Path Consistency with Configured Transit Policies . . . . .89
   7.4.3. Path Consistency with Virtual Gateway Reachability. . . . .91
   7.4.4. Obtaining Resources . . . . . . . . . . . . . . . . . . . .92
   7.4.5. Target Response . . . . . . . . . . . . . . . . . . . . . .93
   7.4.6. Originator Response . . . . . . . . . . . . . . . . . . . .93
   7.4.7. Path Life . . . . . . . . . . . . . . . . . . . . . . . .  94
   7.5. Path Failure and Recovery . . . . . . . . . . . . . . . . .  95
   7.5.1. Handling Implicit Path Failures . . . . . . . . . . . . .  96
   7.5.2. Local Path Repair . . . . . . . . . . . . . . . . . . . .  97
   7.5.3. Repairing a Path. . . . . . . . . . . . . . . . . . . . .  98
   7.6. Path Control Message Formats. . . . . . . . . . . . . . . . 100
   7.6.1. SETUP . . . . . . . . . . . . . . . . . . . . . . . . . . 101
   7.6.2. ACCEPT. . . . . . . . . . . . . . . . . . . . . . . . . . 103
   7.6.3. REFUSE. . . . . . . . . . . . . . . . . . . . . . . . . . 103
   7.6.4. TEARDOWN. . . . . . . . . . . . . . . . . . . . . . . . . 104
   7.6.5. ERROR . . . . . . . . . . . . . . . . . . . . . . . . . . 105
   7.6.6. REPAIR. . . . . . . . . . . . . . . . . . . . . . . . . . 106
   7.6.7. Negative Acknowledgements . . . . . . . . . . . . . . . . 106
   8. Security Considerations . . . . . . . . . . . . . . . . . . . 106
   9. Authors's Address . . . . . . . . . . . . . . . . . . . . . . 107
   References . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

1.  Introduction

   In this document, we specify the protocols and procedures that
   compose Inter-Domain Policy Routing (IDPR).  The objective of IDPR is
   to construct and maintain routes between source and destination
   administrative domains, that provide user traffic with the services
   requested within the constraints stipulated for the domains
   transited.  IDPR supports link state routing information distribution
   and route generation in conjunction with source specified message
   forwarding.  Refer to [5] for a detailed justification of our
   approach to inter-domain policy routing.

1.1.  Domain Elements

   The IDPR architecture has been designed to accommodate an
   internetwork with tens of thousands of administrative domains



Steenstrup                                                      [Page 3]

RFC 1479                     IDPR Protocol                     July 1993


   collectively containing hundreds of thousands of local networks.
   Inter-domain policy routes are constructed using information about
   the services offered by, and the connectivity between, administrative
   domains.  The intra-domain details - gateways, networks, and links
   traversed - of an inter-domain policy route are the responsibility of
   intra-domain routing and are thus outside the scope of IDPR.

   An "administrative domain" (AD) is a collection of contiguous hosts,
   gateways, networks, and links managed by a single administrative
   authority.  The domain administrator defines service restrictions for
   transit traffic and service requirements for locally-generated
   traffic, and selects the addressing schemes and routing procedures
   that apply within the domain.  Within the Internet, each domain has a
   unique numeric identifier assigned by the Internet Assigned Numbers
   Authority (IANA).

   "Virtual gateways" (VGs) are the only IDPR-recognized connecting
   points between adjacent domains.  Each virtual gateway is a
   collection of directly-connected "policy gateways" (see below) in two
   adjoining domains, whose existence has been sanctioned by the
   administrators of both domains.  The domain administrators may agree
   to establish more than one virtual gateway between the two domains.
   For each such virtual gateway, the two administrators together assign
   a local numeric identifier, unique within the set of virtual gateways
   connecting the two domains.  To produce a virtual gateway identifier
   unique within its domain, a domain administrator concatenates the
   mutually assigned local virtual gateway identifier together with the
   adjacent domain's identifier.

   Policy gateways (PGs) are the physical gateways within a virtual
   gateway.  Each policy gateway enforces service restrictions on IDPR
   transit traffic, as stipulated by the domain administrator, and
   forwards the traffic accordingly.  Within a domain, two policy
   gateways are "neighbors" if they are in different virtual gateways.
   A single policy gateway may belong to multiple virtual gateways.
   Within a virtual gateway, two policy gateways are "peers" if they are
   in the same domain and are "adjacent" if they are in different
   domains.  Adjacent policy gateways are "directly connected" if the
   only Internet-addressable entities attached to the connecting medium
   are policy gateways in the virtual gateways.  Note that this
   definition implies that not only point-to-point links but also
   networks may serve as direct connections between adjacent policy
   gateways.  The domain administrator assigns to each of its policy
   gateways a numeric identifier, unique within that domain.

   A "domain component" is a subset of a domain's entities such that all
   entities within the subset are mutually reachable via intra-domain
   routes, but no entities outside the subset are reachable via intra-



Steenstrup                                                      [Page 4]

RFC 1479                     IDPR Protocol                     July 1993


   domain routes from entities within the subset.  Normally, a domain
   consists of a single component, namely itself; however, when
   partitioned, a domain consists of multiple components.  Each domain
   component has an identifier, unique within the Internet, composed of
   the domain identifier together with the identifier of the lowest-
   numbered operational policy gateway within the component.  All
   operational policy gateways within a domain component can discover
   mutual reachability through intra-domain routing information.  Hence,
   all such policy gateways can consistently determine, without explicit
   negotiation, which of them has the lowest number.

1.2.  Policy

   With IDPR, each domain administrator sets "transit policies" that
   dictate how and by whom the resources in its domain should be used.
   Transit policies are usually public, and they specify offered
   services comprising:

   -   Access restrictions: e.g., applied to traffic to or from certain
       domains or classes of users.

   -   Quality: e.g., delay, throughput, or error characteristics.

   -   Monetary cost: e.g., charge per byte, message, or unit time.

   Each domain administrator also sets "source policies" for traffic
   originating in its domain.  Source policies are usually private, and
   they specify requested services comprising:

   -   Access restrictions: e.g., domains to favor or avoid in routes.

   -   Quality: e.g., acceptable delay, throughput, and reliability.

   -   Monetary cost: e.g., acceptable session cost.

1.3.  IDPR Functions

   IDPR comprises the following functions:

   -   Collecting and distributing routing information including domain
       transit policies and inter-domain connectivity.

   -   Generating and selecting policy routes based on the routing
       information distributed and on the source policies configured or
       requested.

   -   Setting up paths across the Internet using the policy routes
       generated.



Steenstrup                                                      [Page 5]

RFC 1479                     IDPR Protocol                     July 1993


   -   Forwarding messages across and between domains along the
       established paths.

   -   Maintaining databases of routing information, inter-domain policy
       routes, forwarding information, and configuration information.

1.3.1.  IDPR Entities

   Several different entities are responsible for performing the IDPR
   functions.

   Policy gateways, the only IDPR-recognized connecting points between
   adjacent domains, collect and distribute routing information,
   participate in path setup, forward data messages along established
   paths, and maintain forwarding information databases.

   "Path agents", resident within policy gateways and within "route
   servers" (see below), act on behalf of hosts to select policy routes,
   to set up and manage paths, and to maintain forwarding information
   databases.  Any Internet host can reap the benefits of IDPR, as long
   as there exists a path agent configured to act on its behalf and a
   means by which the host's messages can reach the path agent.
   Specifically, a path agent in one domain may be configured to act on
   behalf of hosts in another domain.  In this case, the path agent's
   domain is an IDPR "proxy" for the hosts' domain.

   Route servers maintain both the routing information database and the
   route database, and they generate policy routes using the routing
   information collected and the source policies requested by the path
   agents.  A route server may reside within a policy gateway, or it may
   exist as an autonomous entity.  Separating the route server functions
   from the policy gateways frees the policy gateways from both the
   memory intensive task of database (routing information and route)
   maintenance and the computationally intensive task of route
   generation.  Route servers, like policy gateways, each have a unique
   numeric identifier within their domain, assigned by the domain
   administrator.

   Given the size of the current Internet, each policy gateway can
   perform the route server functions, in addition to its message
   forwarding functions, with little or no degradation in message
   forwarding performance.  Aggregating the routing functions into
   policy gateways simplifies implementation; one need only install IDPR
   protocols in policy gateways.  Moreover, it simplifies communication
   between routing functions, as all functions reside within each policy
   gateway.  As the Internet grows, the memory and processing required
   to perform the route server functions may become a burden for the
   policy gateways.  When this happens, each domain administrator should



Steenstrup                                                      [Page 6]

RFC 1479                     IDPR Protocol                     July 1993


   separate the route server functions from the policy gateways in its
   domain.

   "Mapping servers" maintain the database of mappings that resolve
   Internet names and addresses to domain identifiers.  Each host is
   contained within a domain and is associated with a proxy domain which
   may be identical with the host's domain.  The mapping server function
   will be integrated into the existing DNS name service (see [6]) and
   will provide mappings between a host and its local and proxy domains.

   "Configuration servers" maintain the databases of configured
   information that apply to IDPR entities within their domains.
   Configuration information for a given domain includes transit
   policies (i.e., service offerings and restrictions), source policies
   (i.e., service requirements), and mappings between local IDPR
   entities and their names and addresses.  The configuration server
   function will be integrated into a domain's existing network
   management system (see [7]-[8]).

1.4.  Policy Semantics

   The source and transit policies supported by IDPR are intended to
   accommodate a wide range of services available throughout the
   Internet.  We describe the semantics of these policies, concentrating
   on the access restriction aspects.  To express these policies in this
   document, we have chosen to use a syntactic variant of Clark's policy
   term notation [1].  However, we provide a more succinct syntax (see
   [7]) for actually configuring source and transit policies.

1.4.1.  Source Policies

   Each source policy takes the form of a collection of sets as follows:

   Applicable Sources and Destinations:
      {((H(1,1),s(1,1)),...,(H(1,f1),s(1,f1))),...,((H(n,1),s(n,1)),...,
      (H(n,fn),s(n,fn)))}: The set of groups of source/destination
      traffic flows to which the source policy applies.  Each traffic
      flow group ((H(i,1),s(i,1)),...,(H(i,fi),s(i,fi))) contains a set
      of source hosts and corresponding destination hosts.  Here, H(i,j)
      represents a host, and s(i,j), an element of {SOURCE,
      DESTINATION}, represents an indicator of whether H(i,j) is to be
      considered as a source or as a destination.

   Domain Preferences: {(AD(1),x(1)),...,(AD(m),x(m))}: The set of
      transit domains that the traffic flows should favor, avoid, or
      exclude.  Here, AD(i) represents a domain, and x(i), an element of
      {FAVOR, AVOID, EXCLUDE}, represents an indicator of whether routes
      including AD(i) are to be favored, avoided if possible, or



Steenstrup                                                      [Page 7]

RFC 1479                     IDPR Protocol                     July 1993


      unconditionally excluded.

   UCI: The source user class for the traffic flows listed.

   RequestedServices: The set of requested services not related to
      access restrictions, i.e., service quality and monetary cost.

   When selecting a route for a traffic flow from a source host H(i,j)
   to a destination host H(i,k), where 1 < or = i < or = n and 1 < or =
   j, k < or = fi, the path agent (see section 1.3.1) must honor the
   source policy such that:

   - For each domain, AD(p), contained in the route, AD(p) is not equal
     to any AD(k), such that 1 < or = k < or = m and x(k) = EXCLUDE.

   - The route provides the services listed in the set Requested
     Services.

1.4.2.  Transit Policies

   Each transit policy takes the form of a collection of sets as
   follows:

   Source/Destination Access Restrictions:
      {((H(1,1),AD(1,1),s(1,1)),...,(H(1,f1),AD(1,f1),s(1,f1))),...,
      ((H(n,1),AD(n,1),s(n,1)),...,(H(n,fn),AD(n,fn),s(n,fn)))}: The set
      of groups of source and destination hosts and domains to which the
      transit policy applies.  Each domain group
      ((H(i,1),AD(i,1),s(i,1)),...,(H(i,fi),AD(i,fi),s(i,fi))) contains
      a set of source and destination hosts and domains such that this
      transit domain will carry traffic from each source listed to each
      destination listed.  Here, H(i,j) represents a set of hosts,
      AD(i,j) represents a domain containing H(i,j), and s(i,j), a
      subset of {SOURCE, DESTINATION}, represents an indicator of
      whether (H(i,j),AD(i,j)) is to be considered as a set of sources,
      destinations, or both.

   Temporal Access Restrictions: The set of time intervals during which
      the transit policy applies.

   User Class Access Restrictions: The set of user classes to which the
      transit policy applies.

   Offered Services: The set of offered services not related to access
      restrictions, i.e., service quality and monetary cost.






Steenstrup                                                      [Page 8]

RFC 1479                     IDPR Protocol                     July 1993


   Virtual Gateway Access Restrictions:
      {((VG(1,1),e(1,1)),...,(VG(1,g1),e(1,g1))),...,((VG(m,1),e(m,1)),
      gateways to which the transit policy applies.  Each virtual
      gateway group ((VG(i,1),e(i,1)),...,(VG(i,gi),e(i,gi))) contains a
      set of domain entry and exit points such that each entry virtual
      gateway can reach (barring an intra-domain routing failure) each
      exit virtual gateway via an intra-domain route supporting the
      transit policy.  Here, VG(i,j) represents a virtual gateway, and
      e(i,j), a subset of {ENTRY, EXIT}, represents an indicator of
      whether VG(i,j) is to be considered as a domain entry point, exit
      point, or both.

   The domain advertising such a transit policy will carry traffic from
   any host in the set H(i,j) in AD(i,j) to any host in the set H(i,k)
   in AD(i,k), where 1 < or = i < or = n and 1 < or = j, k < or = fi,
   provided that:

   - SOURCE is an element of s(i,j).

   - DESTINATION is an element of s(i,k).

   - Traffic from H(i,j) enters the domain during one of the intervals
     in the set Temporal Access Restrictions.

   - Traffic from H(i,j) carries one of the user class identifiers in
     the set User Class Access Restrictions.

   - Traffic from H(i,j) enters via any VG(u,v) such that ENTRY is an
     element of e(u,v), where 1 < or = u < or = m and 1 < or = v < or =
     gu.

   - Traffic to H(i,k) leaves via any VG(u,w) such that EXIT is an
     element of e(u,w), where 1 < or = w < or = gu.

1.5.  IDPR Message Encapsulation

   There are two kinds of IDPR messages:

   - "Data messages" containing user data generated by hosts.

   - "Control messages" containing IDPR protocol-related control
     information generated by policy gateways and route servers.

   Within an internetwork, only policy gateways and route servers are
   able to generate, recognize, and process IDPR messages.  The
   existence of IDPR is invisible to all other gateways and hosts,
   including mapping servers and configuration servers.  Mapping servers
   and configuration servers perform necessary but ancillary functions



Steenstrup                                                      [Page 9]

RFC 1479                     IDPR Protocol                     July 1993


   for IDPR, and thus they are not required to handle IDPR messages.

   An IDPR entity places IDPR-specific information in each IDPR control
   message it originates; this information is significant only to
   recipient IDPR entities.  Using "encapsulation" across each domain,
   an IDPR message tunnels from source to destination across an
   internetwork through domains that may employ disparate intra-domain
   addressing schemes and routing procedures.

   As an alternative to encapsulation, we had considered embedding IDPR
   in IP, as a set of IP options.  However, this approach has the
   following disadvantages:

   - Only domains that support IP would be able to participate in IDPR;
     domains that do not support IP would be excluded.

   - Each gateway, policy or other, in a participating domain would at
     least have to recognize the IDPR option, even if it did not execute
     the IDPR protocols.  However, most commercial routers are not
     optimized for IP options processing, and so IDPR message handling
     might require significant processing at each gateway.

   - For some IDPR protocols, in particular path control, the size
     restrictions on IP options would preclude inclusion of all of the
     necessary protocol-related information.

   For these reasons, we decided against the IP option approach and in
   favor of encapsulation.

   An IDPR message travels from source to destination between
   consecutive policy gateways.  Each policy gateway encapsulates the
   IDPR message with information, for example an IP header, that will
   enable the message to reach the next policy gateway.  Note that the
   encapsulating header and the IDPR-specific information may increase
   the message size beyond the MTU of the given domain.  However,
   message fragmentation and reassembly is the responsibility of the
   protocol, for example IP, that encapsulates IDPR messages for
   transport between successive policy gateways; it is not currently the
   responsibility of IDPR itself.

   A policy gateway, when forwarding an IDPR message to a peer or a
   neighbor policy gateway, encapsulates the message in accordance with
   the addressing scheme and routing procedure of the given domain and
   indicates in the protocol field of the encapsulating header that the
   message is indeed an IDPR message.  Intermediate gateways between the
   two policy gateways forward the IDPR message as they would any other
   message, using the information in the encapsulating header.  Only the
   recipient policy gateway interprets the protocol field, strips off



Steenstrup                                                     [Page 10]

RFC 1479                     IDPR Protocol                     July 1993


   the encapsulating header, and processes the IDPR message.

   A policy gateway, when forwarding an IDPR message to a directly-
   connected adjacent policy gateway, encapsulates the message in
   accordance with the addressing scheme of the entities within the
   virtual gateway and indicates in the protocol field of the
   encapsulating header that the message is indeed an IDPR message.  The
   recipient policy gateway strips off the encapsulating header and
   processes the IDPR message.  We recommend that the recipient policy
   gateway perform the following validation check of the encapsulating
   header, prior to stripping it off.  Specifically, the recipient
   policy gateway should verify that the source address and the
   destination address in the encapsulating header match the adjacent
   policy gateway's address and its own address, respectively.
   Moreover, the recipient policy gateway should verify that the message
   arrived on the interface designated for the direct connection to the
   adjacent policy gateway.  These checks help to ensure that IDPR
   traffic that crosses domain boundaries does so only over direct
   connections between adjacent policy gateways.

   Policy gateways forward IDPR data messages according to a forwarding
   information database which maps "path identifiers", carried in the
   data messages, into next policy gateways.  Policy gateways forward
   IDPR control messages according to next policy gateways selected by
   the particular IDPR control protocols associated with the messages.
   Distinguishing IDPR data messages and IDPR control messages at the
   encapsulating protocol level, instead of at the IDPR protocol level,
   eliminates an extra level of dispatching and hence makes IDPR message
   forwarding more efficient.  When encapsulated within IP messages,
   IDPR data messages and IDPR control messages carry the IP protocol
   numbers 35 and 38, respectively.

1.5.1.  IDPR Data Message Format

   The path agents at a source domain determine which data messages
   generated by local hosts are to be handled by IDPR.  To each data
   message selected for IDPR handling, a source path agent prepends the
   following header:













Steenstrup                                                     [Page 11]

RFC 1479                     IDPR Protocol                     July 1993


    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |    VERSION    |     PROTO     |            LENGTH             |
   +---------------+---------------+-------------------------------+
   |                            PATH ID                            |
   |                                                               |
   +---------------------------------------------------------------+
   |                           TIMESTAMP                           |
   +---------------------------------------------------------------+
   |                            INT/AUTH                           |
   |                                                               |
   +---------------------------------------------------------------+

   VERSION (8 bits) Version number for IDPR data messages, currently
   equal to 1.

   PROTO (8 bits) Numeric identifier for the protocol with which to
   process the contents of the IDPR data message.  Only the path agent
   at the destination interprets and acts upon the contents of the PROTO
   field.

   LENGTH (16 bits) Length of the entire IDPR data message in bytes.

   PATH ID (64 bits) Path identifier assigned by the source's path agent
   and consisting of the numeric identifier for the path agent's domain
   (16 bits), the numeric identifier for the path agent's policy gateway
   (16 bits), and the path agent's local path identifier (32 bits) (see
   section 7.2).

   TIMESTAMP (32 bits) Number of seconds elapsed since 1 January 1970
   0:00 GMT.

   INT/AUTH (variable) Computed integrity/authentication value,
   dependent on the type of integrity/authentication requested during
   path setup.

   We describe the IDPR control message header in section 2.4.

1.6.  Security

   IDPR contains mechanisms for verifying message integrity and source
   authenticity and for protecting against certain types of denial of
   service attacks.  It is particularly important to keep IDPR control
   messages intact, because they carry control information critical to
   the construction and use of viable policy routes between domains.

   All IDPR messages carry a single piece of information, referred to as



Steenstrup                                                     [Page 12]

RFC 1479                     IDPR Protocol                     July 1993


   the "integrity/authentication value", which may be used not only to
   detect message corruption but also to verify the authenticity of the
   message source.  In the Internet, the IANA will sanction the set of
   valid algorithms which may be used to compute the
   integrity/authentication values.  This set may include algorithms
   that perform only message integrity checks such as n-bit cyclic
   redundancy checksums (CRCs), as well as algorithms that perform both
   message integrity and source authentication checks such as signed
   hash functions of message contents.

   Each domain administrator is free to select any
   integrity/authentication algorithm, from the set specified by the
   IANA, for computing the integrity/authentication values contained in
   its domain's messages.  However, we recommend that IDPR entities in
   each domain be capable of executing all of the valid algorithms so
   that an IDPR control message originating at an entity in one domain
   can be properly checked by an entity in another domain.

   Each IDPR control message must carry a non-null
   integrity/authentication value.  We recommend that control message
   integrity/authentication be based on a digital signature algorithm
   applied to a one-way hash function, such as RSA applied to MD5 [17],
   which simultaneously verifies message integrity and source
   authenticity.  The digital signature may be based on either public-
   key or private-key cryptography.  Our approach to digital signature
   use in IDPR is based on the privacy-enhanced Internet electronic mail
   service [13]-[15], already available in the Internet.

   We do not require that IDPR data messages carry a non-null
   integrity/authentication value.  In fact, we recommend that a higher
   layer (end-to-end) procedure, and not IDPR, assume responsibility for
   checking the integrity and authenticity of data messages, because of
   the amount of computation involved.

1.7.  Timestamps and Clock Synchronization

   Each IDPR message carries a timestamp (expressed in seconds elapsed
   since 1 January 1970 0:00 GMT, following the UNIX precedent) supplied
   by the source IDPR entity, which serves to indicate the age of the
   message.  IDPR entities use the absolute value of the timestamp to
   confirm that a message is current and use the relative difference
   between timestamps to determine which message contains the more
   recent information.

   All IDPR entities must possess internal clocks that are synchronized
   to some degree, in order for the absolute value of a message
   timestamp to be meaningful.  The synchronization granularity required
   by IDPR is on the order of minutes and can be achieved manually.



Steenstrup                                                     [Page 13]

RFC 1479                     IDPR Protocol                     July 1993


   Thus, a clock synchronization protocol operating among all IDPR
   entities in all domains, while useful, is not necessary.

   An IDPR entity can determine whether to accept or reject a message
   based on the discrepancy between the message's timestamp and the
   entity's own internal clock time.  Any IDPR message whose timestamp
   lies outside of the acceptable range may contain stale or corrupted
   information or may have been issued by a source whose internal clock
   has lost synchronization with the message recipient's internal clock.
   Timestamp checks are required for control messages because of the
   consequences of propagating and acting upon incorrect control
   information.  However, timestamp checks are discretionary for data
   messages but may be invoked during problem diagnosis, for example,
   when checking for suspected message replays.

   We note that none of the IDPR protocols contain explicit provisions
   for dealing with an exhausted timestamp space.  As timestamp space
   exhaustion will not occur until well into the next century, we expect
   timestamp space viability to outlast the IDPR protocols.

1.8.  Network Management

   In this document, we do not describe how to configure and manage
   IDPR.  However, in this section, we do provide a list of the types of
   IDPR configuration information required.  Also, in later sections
   describing the IDPR protocols, we briefly note the types of
   exceptional events that must be logged for network management.
   Complete descriptions of IDPR entity configuration and IDPR managed
   objects appear in [7] and [8] respectively.

   To participate in inter-domain policy routing, policy gateways and
   route servers within a domain each require configuration information.
   Some of the configuration information is specifically defined within
   the given domain, while some of the configuration information is
   universally defined throughout an internetwork.  A domain
   administrator determines domain-specific information, and in the
   Internet, the IANA determines globally significant information.

   To produce valid domain configurations, the domain administrators
   must receive the following global information from the IANA:

   - For each integrity/authentication type, the numeric
     identifier, syntax, and semantics.  Available integrity and
     authentication types include but are not limited to:

       o    public-key based signatures;

       o    private-key based signatures;



Steenstrup                                                     [Page 14]

RFC 1479                     IDPR Protocol                     July 1993



       o    cyclic redundancy checksums;

       o    no integrity/authentication.

   - For each user class, the numeric identifier, syntax, and
     semantics.  Available user classes include but are not limited to:

       o    federal (and if necessary, agency-specific such as NSF, DOD,
            DOE, etc.);

       o    research;

       o    commercial;

       o    support.

   - For each offered service that may be advertised in transit
     policies, the numeric identifier, syntax, and semantics.  Available
     offered services include but are not limited to:

       o    average message delay;

       o    message delay variation;

       o    average bandwidth available;

       o    available bandwidth variation;

       o    maximum transfer unit (MTU);

       o    charge per byte;

       o    charge per message;

       o    charge per unit time.

   - For each access restriction that may be advertised in transit
     policies, the numeric identifier, syntax, and semantics.  Available
     access restrictions include but are not limited to:

       o    Source and destination domains and host sets.

       o    User classes.

       o    Entry and exit virtual gateways.

       o    Time of day.



Steenstrup                                                     [Page 15]

RFC 1479                     IDPR Protocol                     July 1993


   - For each requested service that may appear within a path setup
     message, the numeric identifier, syntax, and semantics.  Available
     requested services include but are not limited to:

       o    maximum path life in minutes, messages, or bytes;

       o    integrity/authentication algorithms to be used on data
            messages sent over the path;

       o    upper bound on path delay;

       o    minimum delay path;

       o    upper bound on path delay variation;

       o    minimum delay variation path;

       o    lower bound on path bandwidth;

       o    maximum bandwidth path;

       o    upper bound on monetary cost;

       o    minimum monetary cost path.

   In an internetwork-wide implementation of IDPR, the set of global
   configuration parameters and their syntax and semantics must be
   consistent across all participating domains.  The IANA, responsible
   for establishing the full set of global configuration parameters in
   the Internet, relies on the cooperation of the administrators of all
   participating domains to ensure that the global parameters are
   consistent with the desired transit policies and user service
   requirements of each domain.  Moreover, as the syntax and semantics
   of the global parameters affects the syntax and semantics of the
   corresponding IDPR software, the IANA must carefully define each
   global parameter so that it is unlikely to require future
   modification.

   The IANA provides configured global information to configuration
   servers in all domains participating in IDPR.  Each domain
   administrator uses the configured global information maintained by
   its configuration servers to develop configurations for each IDPR
   entity within its domain.  Each configuration server retains a copy
   of the configuration for each local IDPR entity and also distributes
   the configuration to that entity using, for example, SNMP.






Steenstrup                                                     [Page 16]

RFC 1479                     IDPR Protocol                     July 1993


1.8.1.  Policy Gateway Configuration

   Each policy gateway must contain sufficient configuration information
   to perform its IDPR functions, which subsume those of the path agent.
   These include: validating IDPR control messages; generating and
   distributing virtual gateway connectivity and routing information
   messages to peer, neighbor, and adjacent policy gateways;
   distributing routing information messages to route servers in its
   domain; resolving destination addresses; requesting policy routes
   from route servers; selecting policy routes and initiating path
   setup; ensuring consistency of a path with its domain's transit
   policies; establishing path forwarding information; and forwarding
   IDPR data messages along existing paths.  The necessary configuration
   information includes the following:

   - For each integrity/authentication type, the numeric identifier,
     syntax, and semantics.

   - For each policy gateway and route server in the given domain, the
     numeric identifier and set of addresses or names.

   - For each virtual gateway connected to the given domain, the numeric
     identifier, the numeric identifiers for the constituent peer policy
     gateways, and the numeric identifier for the adjacent domain.

   - For each virtual gateway of which the given policy gateway is a
     member, the numeric identifiers and set of addresses for the
     constituent adjacent policy gateways.

   - For each policy gateway directly-connected and adjacent to the
     given policy gateway, the local connecting interface.

   - For each local route server to which the given policy gateway
     distributes routing information, the numeric identifier.

   - For each source policy applicable to hosts within the given domain,
     the syntax and semantics.

   - For each transit policy applicable to the domain, the numeric
     identifier, syntax, and semantics.

   - For each requested service that may appear within a path setup
     message, the numeric identifier, syntax, and semantics.

   - For each source user class, the numeric identifier, syntax, and
     semantics.





Steenstrup                                                     [Page 17]

RFC 1479                     IDPR Protocol                     July 1993


1.8.2.  Route Server Configuration

   Each route server must contain sufficient configuration information
   to perform its IDPR functions, which subsume those of the path agent.
   These include: validating IDPR control messages; deciphering and
   storing the contents of routing information messages; exchanging
   routing information with other route servers and policy gateways;
   generating policy routes that respect transit policy restrictions and
   source service requirements; distributing policy routes to path
   agents in policy gateways; resolving destination addresses; selecting
   policy routes and initiating path setup; establishing path forwarding
   information; and forwarding IDPR data messages along existing paths.
   The necessary configuration information includes the following:

   - For each integrity/authentication type, the numeric identifier,
     syntax, and semantics.

   - For each policy gateway and route server in the given domain, the
     numeric identifier and set of addresses or names.

   - For each source policy applicable to hosts within the given domain,
     the syntax and semantics.

   - For access restriction that may be advertised in transit
     policies, the numeric identifier, syntax, and semantics.

   - For each offered service that may be advertised in transit policies,
     the numeric identifier, syntax, and semantics.

   - For each requested service that may appear within a path setup
     message, the numeric identifier, syntax, and semantics.

   - For each source user class, the numeric identifier, syntax, and
     semantics.

2.  Control Message Transport Protocol

   IDPR control messages convey routing-related information that
   directly affects the policy routes generated and the paths set up
   across the Internet.  Errors in IDPR control messages can have
   widespread, deleterious effects on inter-domain policy routing, and
   so the IDPR protocols have been designed to minimize loss and
   corruption of control messages.  For every control message it
   transmits, each IDPR protocol expects to receive notification as to
   whether the control message successfully reached the intended IDPR
   recipient.  Moreover, the IDPR recipient of a control message first
   verifies that the message appears to be well-formed, before acting on
   its contents.



Steenstrup                                                     [Page 18]

RFC 1479                     IDPR Protocol                     July 1993


   All IDPR protocols use the Control Message Transport Protocol (CMTP),
   a connectionless, transaction-based transport layer protocol, for
   communication with intended recipients of control messages.  CMTP
   retransmits unacknowledged control messages and applies integrity and
   authenticity checks to received control messages.

   There are three types of CMTP messages:

   DATAGRAM:
        Contains IDPR control messages.

   ACK: Positive acknowledgement in response to a DATAGRAM message.

   NAK: Negative acknowledgement in response to a DATAGRAM message.

   Each CMTP message contains several pieces of information supplied by
   the sender that allow the recipient to test the integrity and
   authenticity of the message.  The set of integrity and authenticity
   checks performed after CMTP message reception are collectively
   referred to as "validation checks" and are described in section 2.3.

   When we first designed the IDPR protocols, CMTP as a distinct
   protocol did not exist.  Instead, CMTP-equivalent functionality was
   embedded in each IDPR protocol.  To provide a cleaner implementation,
   we later decided to provide a single transport protocol that could be
   used by all IDPR protocols.  We originally considered using an
   existing transport protocol, but rejected this approach for the
   following reasons:

   - The existing reliable transport protocols do not provide all of the
     validation checks, in particular the timestamp and authenticity
     checks, required by the IDPR protocols.  Hence, if we were to use
     one of these protocols, we would still have to provide a separate
     protocol on top of the transport protocol to force retransmission of
     IDPR messages that failed to pass the required validation checks.

   - Many of the existing reliable transport protocols are window-based
     and hence can result in increased message delay and resource use
     when, as is the case with IDPR, multiple independent messages use
     the same transport connection.  A single message experiencing
     transmission problems and requiring retransmission can prevent the
     window from advancing, forcing all subsequent messages to queue
     behind it.  Moreover, many of the window-based protocols do not
     support selective retransmission of failed messages but instead
     require retransmission of not only the failed message but also all
     preceding messages within the window.

   For these reasons, we decided against using an existing transport



Steenstrup                                                     [Page 19]

RFC 1479                     IDPR Protocol                     July 1993


   protocol and in favor of developing CMTP.

2.1.  Message Transmission

   At the transmitting entity, when an IDPR protocol is ready to issue a
   control message, it passes a copy of the message to CMTP; it also
   passes a set of parameters to CMTP for inclusion in the CMTP header
   and for proper CMTP message handling.  In turn, CMTP converts the
   control message and associated parameters into a DATAGRAM by
   prepending the appropriate header to the control message.  The CMTP
   header contains several pieces of information to aid the message
   recipient in detecting errors (see section 2.4).  Each IDPR protocol
   can specify all of the following CMTP parameters applicable to its
   control message:

   -   IDPR protocol and message type.

   -   Destination.

   -   Integrity/authentication scheme.

   -   Timestamp.

   -   Maximum number of transmissions allotted.

   -   Retransmission interval in microseconds.

   One of these parameters, the timestamp, can be specified directly by
   CMTP as the internal clock time at which the message is transmitted.
   However, two of the IDPR protocols, namely flooding and path control,
   themselves require message generation timestamps for proper protocol
   operation.  Thus, instead of requiring CMTP to pass back a timestamp
   to an IDPR protocol, we simplify the service interface between CMTP
   and the IDPR protocols by allowing an IDPR protocol to specify the
   timestamp in the first place.

   Using the control message and accompanying parameters supplied by the
   IDPR protocol, CMTP constructs a DATAGRAM, adding to the header
   CMTP-specific parameters.  In particular, CMTP assigns a "transaction
   identifier" to each DATAGRAM generated, which it uses to associate
   acknowledgements with DATAGRAM messages.  Each DATAGRAM recipient
   includes the received transaction identifier in its returned ACK or
   NAK, and each DATAGRAM sender uses the transaction identifier to
   match the received ACK or NAK with the original DATAGRAM.

   A single DATAGRAM, for example a routing information message or a
   path control message, may be handled by CMTP at many different policy
   gateways.  Within a pair of consecutive IDPR entities, the DATAGRAM



Steenstrup                                                     [Page 20]

RFC 1479                     IDPR Protocol                     July 1993


   sender expects to receive an acknowledgement from the DATAGRAM
   recipient.  However, only the IDPR entity that actually generated the
   original CMTP DATAGRAM has control over the transaction identifier,
   because that entity may supply a digital signature that covers the
   entire DATAGRAM.  The intermediate policy gateways that transmit the
   DATAGRAM do not change the transaction identifier.  Nevertheless, at
   each DATAGRAM recipient, the transaction identifier must uniquely
   distinguish the DATAGRAM so that only one acknowledgement from the
   next DATAGRAM recipient matches the original DATAGRAM.  Therefore,
   the transaction identifier must be globally unique.

   The transaction identifier consists of the numeric identifiers for
   the domain and IDPR entity (policy gateway or route server) issuing
   the original DATAGRAM, together with a 32-bit local identifier
   assigned by CMTP operating within that IDPR entity.  We recommend
   implementing the 32-bit local identifier either as a simple counter
   incremented for each DATAGRAM generated or as a fine granularity
   clock.  The former always guarantees uniqueness of transaction
   identifiers; the latter guarantees uniqueness of transaction
   identifiers, provided the clock granularity is finer than the minimum
   possible interval between DATAGRAM generations and the clock wrapping
   period is longer than the maximum round-trip delay to and from any
   internetwork destination.

   Before transmitting a DATAGRAM, CMTP computes the length of the
   entire message, taking into account the prescribed
   integrity/authentication scheme, and then computes the
   integrity/authentication value over the whole message.  CMTP includes
   both of these quantities, which are crucial for checking message
   integrity and authenticity at the recipient, in the DATAGRAM header.
   After sending a DATAGRAM, CMTP saves a copy and sets an associated
   retransmission timer, as directed by the IDPR protocol parameters.
   If the retransmission timer fires and CMTP has received neither an
   ACK nor a NAK for the DATAGRAM, CMTP then retransmits the DATAGRAM,
   provided this retransmission does not exceed the transmission
   allotment.  Whenever a DATAGRAM exhausts its transmission allotment,
   CMTP discards the DATAGRAM, informs the IDPR protocol that the
   control message transmission was not successful, and logs the event
   for network management.  In this case, the IDPR protocol may either
   resubmit its control message to CMTP, specifying an alternate
   destination, or discard the control message altogether.










Steenstrup                                                     [Page 21]

RFC 1479                     IDPR Protocol                     July 1993


2.2.  Message Reception

   At the receiving entity, when CMTP obtains a DATAGRAM, it takes one
   of the following actions, depending upon the outcome of the message
   validation checks:

   - The DATAGRAM passes the CMTP validation checks.  CMTP then delivers
     the DATAGRAM with enclosed IDPR control message, to the appropriate
     IDPR protocol, which in turn applies its own integrity checks to
     the control message before acting on the contents.  The recipient
     IDPR protocol, except in one case, directs CMTP to generate an ACK
     and return the ACK to the sender.  That exception is the up/down
     protocol (see section 3.2) which determines reachability of
     adjacent policy gateways and does not use CMTP ACK messages to
     notify the sender of message reception.  Instead, the up/down
     protocol messages themselves carry implicit information about
     message reception at the adjacent policy gateway.  In the cases
     where the recipient IDPR protocol directs CMTP to generate an ACK,
     it may pass control information to CMTP for inclusion in the ACK,
     depending on the contents of the original IDPR control message.
     For example, a route server unable to fill a request for routing
     information may inform the requesting IDPR entity, through an ACK
     for the initial request, to place its request elsewhere.

   - The DATAGRAM fails at least one of the CMTP validation checks.
     CMTP then generates a NAK, returns the NAK to the sender, and
     discards the DATAGRAM, regardless of the type of IDPR control
     message contained in the DATAGRAM.  The NAK indicates the nature of
     the validation failure and serves to help the sender establish
     communication with the recipient.  In particular, the CMTP NAK
     provides a mechanism for negotiation of IDPR version and
     integrity/authentication scheme, two parameters crucial for
     establishing communication between IDPR entities.

   Upon receiving an ACK or a NAK, CMTP immediately discards the message
   if at least one of the validation checks fails or if it is unable to
   locate the associated DATAGRAM.  CMTP logs the latter event for
   network management.  Otherwise, if all of the validation checks pass
   and if it is able to locate the associated DATAGRAM, CMTP clears the
   associated retransmission timer and then takes one of the following
   actions, depending upon the message type:

   - The message is an ACK.  CMTP discards the associated DATAGRAM and
     delivers the ACK, which may contain IDPR control information, to
     the appropriate IDPR protocol.

   - The message is a NAK.  If the associated DATAGRAM has exhausted its
     transmission allotment, CMTP discards the DATAGRAM, informs the



Steenstrup                                                     [Page 22]

RFC 1479                     IDPR Protocol                     July 1993


     appropriate IDPR protocol that the control message transmission was
     not successful, and logs the event for network management.
     Otherwise, if the associated DATAGRAM has not yet exhausted its
     transmission allotment, CMTP first checks its copy of the DATAGRAM
     against the failure indication contained in the NAK.  If its
     DATAGRAM copy appears to be intact, CMTP retransmits the DATAGRAM
     and sets the associated retransmission timer.  However, if its
     DATAGRAM copy appears to be corrupted, CMTP discards the DATAGRAM,
     informs the IDPR protocol that the control message transmission was
     not successful, and logs the event for network management.

2.3.  Message Validation

   On every CMTP message received, CMTP performs a set of validation
   checks to test message integrity and authenticity.  The order in
   which these tests are executed is important.  CMTP must first
   determine if it can parse enough of the message to compute the
   integrity/authentication value.  (Refer to section 2.4 for a
   description of CMTP message formats.)  Then, CMTP must immediately
   compute the integrity/authentication value before checking other
   header information.  An incorrect integrity/authentication value
   means that the message is corrupted, and so it is likely that CMTP
   header information is incorrect.  Checking specific header fields
   before computing the integrity/authentication value not only may
   waste time and resources, but also may lead to incorrect diagnoses of
   a validation failure.

   The CMTP validation checks are as follows:

   - CMTP verifies that it can recognize both the control message
     version type contained in the header.  Failure to recognize either
     one of these values means that CMTP cannot continue to parse the
     message.

   - CMTP verifies that it can recognize and accept the
     integrity/authentication type contained in the header; no
     integrity/authentication is not an acceptable type for CMTP.

   - CMTP computes the integrity/authentication value and verifies that
     it equals the integrity/authentication value contained in the
     header.  For key-based integrity/authentication schemes, CMTP may
     use the source domain identifier contained in the CMTP header to
     index the correct key.  Failure to index a key means that CMTP
     cannot compute the integrity/authentication value.

   - CMTP computes the message length in bytes and verifies that it
     equals the length value contained in the header.




Steenstrup                                                     [Page 23]

RFC 1479                     IDPR Protocol                     July 1993


   - CMTP verifies that the message timestamp is in the acceptable
     range.  The message should be no more recent than cmtp_new (300)
     seconds ahead of the entity's current internal clock time.  In this
     document, when we present an IDPR system configuration parameter,
     such as cmtp_new, we usually follow it with a recommended value in
     parentheses.  The cmtp_new value allows some clock drift between
     IDPR entities.  Moreover, each IDPR protocol has its own limit on
     the maximum age of its control messages.  The message should be no
     less recent than a prescribed number of seconds behind the
     recipient entity's current internal clock time.  Hence, each IDPR
     protocol performs its own message timestamp check in addition to
     that performed by CMTP.

   - CMTP verifies that it can recognize the IDPR protocol designated
     for the enclosed control message.

   Whenever CMTP encounters a failure while performing any of these
   validation checks, it logs the event for network management.  If the
   failure occurs on a DATAGRAM, CMTP immediately generates a NAK
   containing the reason for the failure, returns the NAK to the sender,
   and discards the DATAGRAM message.  If the failure occurs on an ACK
   or a NAK, CMTP discards the ACK or NAK message.

2.4.  CMTP Message Formats

   In designing the format of IDPR control messages, we have attempted
   to strike a balance between efficiency of link bandwidth usage and
   efficiency of message processing.  In general, we have chosen compact
   representations for IDPR information in order to minimize the link
   bandwidth consumed by IDPR-specific information.  However, we have
   also organized IDPR information in order to speed message processing,
   which does not always result in minimum link bandwidth usage.

   To limit link bandwidth usage, we currently use fixed-length
   identifier fields in IDPR messages; domains, virtual gateways, policy
   gateways, and route servers are all represented by fixed-length
   identifiers.  To simplify message processing, we currently align
   fields containing an even number of bytes on even-byte boundaries
   within a message.  In the future, if the Internet adopts the use of
   super domains, we will offer hierarchical, variable-length identifier
   fields in an updated version of IDPR.

   The header of each CMTP message contains the following information:








Steenstrup                                                     [Page 24]

RFC 1479                     IDPR Protocol                     July 1993


    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |    VERSION    |  PRT  |  MSG  |  DPR  |  DMS  |    I/A TYP    |
   +---------------+-------+-------+-------+-------+---------------+
   |           SOURCE AD           |           SOURCE ENT          |
   +-------------------------------+-------------------------------+
   |                           TRANS ID                            |
   +---------------------------------------------------------------+
   |                           TIMESTAMP                           |
   +-------------------------------+-------------------------------+
   |            LENGTH             |       message specific        |
   +-------------------------------+-------------------------------+
   |         DATAGRAM AD           |         DATAGRAM ENT          |
   +-------------------------------+-------------------------------+
   |                             INFORM                            |
   +---------------------------------------------------------------+
   |                            INT/AUTH                           |
   |                                                               |
   +---------------------------------------------------------------+

   VERSION
        (8 bits) Version number for IDPR control messages, currently
        equal to 1.

   PRT (4 bits) Numeric identifier for the control message transport
        protocol, equal to 0 for CMTP.

   MSG (4 bits) Numeric identifier for the CMTP message type,equal to 0
        for a DATAGRAM, 1 for an ACK, and 2 for a NAK.

   DPR (4 bits) Numeric identifier for the original DATAGRAM's IDPR
        protocol type.

   DMS (4 bits) Numeric identifier for the original DATAGRAM's IDPR
        message type.

   I/A TYP (8 bits) Numeric identifier for the integrity/authentication
        scheme used.  CMTP requires the use of an
        integrity/authentication scheme; this value must not be set
        equal to 0, indicating no integrity/authentication in use.

   SOURCE AD (16 bits) Numeric identifier for the domain containing the
        IDPR entity that generated the message.

   SOURCE ENT (16 bits) Numeric identifier for the IDPR entity that
        generated the message.




Steenstrup                                                     [Page 25]

RFC 1479                     IDPR Protocol                     July 1993


   TRANSACTION ID (32 bits) Local transaction identifier assigned by the
        IDPR entity that generated the original DATAGRAM.

   TIMESTAMP (32 bits) Number of seconds elapsed since 1 January 1970
        0:00 GMT.

   LENGTH (16 bits) Length of the entire IDPR control message, including
        the CMTP header, in bytes.

   message specific (16 bits) Dependent upon CMTP message type.

        For DATAGRAM and ACK messages:

             RESERVED
                  (16 bits) Reserved for future use and currently set
                  equal to 0.

        For NAK messages:

             ERR TYP (8 bits) Numeric identifier for the type of CMTP
                  validation failure encountered.  Validation failures
                  include the following types:

                  1.   Unrecognized IDPR control message version number.

                  2.   Unrecognized CMTP message type.

                  3.   Unrecognized integrity/authentication scheme.

                  4.   Unacceptable integrity/authentication scheme.

                  5.   Unable to locate key using source domain.

                  6.   Incorrect integrity/authentication value.

                  7.   Incorrect message length.

                  8.   Message timestamp out of range.

                  9.   Unrecognized IDPR protocol designated for the
                  enclosed control message.










Steenstrup                                                     [Page 26]

RFC 1479                     IDPR Protocol                     July 1993


             ERR INFO (8 bits) CMTP supplies the following additional
                  information for the designated types of validation
                  failures:

                  Type 1:
                      Acceptable IDPR control message version number.

                  Types 3 and 4: Acceptable integrity/authentication
                      type.

   DATAGRAM AD
        (16 bits) Numeric identifier for the domain containing the IDPR
        entity that generated the original DATAGRAM.  Present only in
        ACK and NAK messages.

   DATAGRAM ENT (16 bits) Numeric identifier for the IDPR entity that
        generated the original DATAGRAM.  Present only in ACK and NAK
        messages.

   INFORM (optional,variable) Information to be interpreted by the IDPR
        protocol that issued the original DATAGRAM.  Present only in ACK
        messages and dependent on the original DATAGRAM's IDPR protocol
        type.

   INT/AUTH (variable) Computed integrity/authentication value,
        dependent on the type of integrity/authentication scheme used.

3.  Virtual Gateway Protocol

   Every policy gateway within a domain participates in gathering
   information about connectivity within and between virtual gateways of
   which it is a member and in distributing this information to other
   virtual gateways in its domain.  We refer to these functions
   collectively as the Virtual Gateway Protocol (VGP).

   The information collected through VGP has both local and global
   significance for IDPR.  Virtual gateway connectivity information,
   distributed to policy gateways within a single domain, aids those
   policy gateways in selecting routes across and between virtual
   gateways connecting their domain to adjacent domains.  Inter-domain
   connectivity information, distributed throughout an internetwork in
   routing information messages, aids route servers in constructing
   feasible policy routes.

   Provided that a domain contains simple virtual gateway and transit
   policy configurations, one need only implement a small subset of the
   VGP functions.  The connectivity among policy gateways within a
   virtual gateway and the heterogeneity of transit policies within a



Steenstrup                                                     [Page 27]

RFC 1479                     IDPR Protocol                     July 1993


   domain determine which VGP functions must be implemented, as we
   explain toward the end of this section.

3.1.  Message Scope

   Policy gateways generate VGP messages containing information about
   perceived changes in virtual gateway connectivity and distribute
   these messages to other policy gateways within the same domain and
   within the same virtual gateway.  We classify VGP messages into three
   distinct categories: "pair-PG", "intra-VG", and "inter-VG", depending
   upon the scope of message distribution.

   Policy gateways use CMTP for reliable transport of VGP messages.  The
   issuing policy gateway must communicate to CMTP the maximum number of
   transmissions per VGP message, vgp_ret, and the interval between VGP
   message retransmissions, vgp_int microseconds.  The recipient policy
   gateway must determine VGP message acceptability; conditions of
   acceptability depend on the type of VGP message, as we describe
   below.

   Policy gateways store, act upon, and in the case of inter-VG
   messages, forward the information contained in acceptable VGP
   messages.  VGP messages that pass the CMTP validation checks but fail
   a specific VGP message acceptability check are considered to be
   unacceptable and are hence discarded by recipient policy gateways.  A
   policy gateway that receives an unacceptable VGP message also logs
   the event for network management.

3.1.1.  Pair-PG Messages

   Pair-PG message communication occurs between the two members of a
   pair of adjacent, peer, or neighbor policy gateways.  With IDPR, the
   only pair-PG messages are those periodically generated by the up/down
   protocol and used to monitor mutual reachability between policy
   gateways.

   A pair-PG message is "acceptable" if:

   - It passes the CMTP validation checks.

   - Its timestamp is less than vgp_old (300) seconds behind the
     recipient's internal clock time.

   - Its destination policy gateway identifier coincides with the
     identifier of the recipient policy gateway.

   - Its source policy gateway identifier coincides with the identifier
     of a policy gateway configured for the recipient's domain or



Steenstrup                                                     [Page 28]

RFC 1479                     IDPR Protocol                     July 1993


     associated virtual gateway.

3.1.2.  Intra-VG Messages

   Intra-VG message communication occurs between one policy gateway and
   all of its peers.  Whenever a policy gateway discovers that its
   connectivity to an adjacent or neighbor policy gateway has changed,
   it issues an intra-VG message indicating the connectivity change to
   all of its reachable peers.  Whenever a policy gateway detects that a
   previously unreachable peer is now reachable, it issues, to that
   peer, intra-VG messages indicating connectivity to adjacent and
   neighbor policy gateways.  If the issuing policy gateway fails to
   receive an analogous intra-VG message from the newly reachable peer
   within twice the configured VGP retransmission interval, vgp_int
   microseconds, it actively requests the intra-VG message from that
   peer.  These message exchanges ensure that peers maintain a
   consistent view of each others' connectivity to adjacent and neighbor
   policy gateways.

   An intra-VG message is "acceptable" if:

   - It passes the CMTP validation checks.

   - Its timestamp is less than vgp_old (300) seconds behind the
     recipient's internal clock time.

   - Its virtual gateway identifier coincides with that of a virtual
     gateway configured for the recipient's domain.

3.1.3.  Inter-VG Messages

   Inter-VG message communication occurs between one policy gateway and
   all of its neighbors.  Whenever the lowest-numbered operational
   policy gateway in a set of mutually reachable peers discovers that
   its virtual gateway's connectivity to the adjacent domain or to
   another virtual gateway has changed, it issues an inter-VG message
   indicating the connectivity change to all of its neighbors.
   Specifically, the policy gateway distributes an inter-VG message to a
   "VG representative" policy gateway (see section 3.1.4 below) in each
   virtual gateway in the domain.  Each VG representative in turn
   propagates the inter-VG message to each of its peers.

   Whenever the lowest-numbered operational policy gateway in a set of
   mutually peers detects that one or more previously unreachable peers
   are now reachable, it issues, to the lowest-numbered operational
   policy gateway in all other virtual gateways, requests for inter-VG
   information indicating connectivity to adjacent domains and to other
   virtual gateways.  The recipient policy gateways return the requested



Steenstrup                                                     [Page 29]

RFC 1479                     IDPR Protocol                     July 1993


   inter-VG messages to the issuing policy gateway, which in turn
   distributes the messages to the newly reachable peers.  These message
   exchanges ensure that virtual gateways maintain a consistent view of
   each others' connectivity, while consuming minimal domain resources
   in distributing connectivity information.

   An inter-VG message contains information about the entire virtual
   gateway, not just about the issuing policy gateway.  Thus, when
   virtual gateway connectivity changes happen in rapid succession,
   recipients of the resultant inter-VG messages should be able to
   determine the most recent message and that message must contain the
   current virtual gateway connectivity information.  To ensure that the
   connectivity information distributed is consistent and unambiguous,
   we designate a single policy gateway, namely the lowest-numbered
   operational peer, for generating and distributing inter-VG messages.
   It is a simple procedure for a set of mutually reachable peers to
   determine the lowest-numbered member, as we describe in section 3.2
   below.

   To understand why a single member of a virtual gateway must issue
   inter-VG messages, consider the following example.  Suppose that two
   peers in a virtual gateway each detect a different connectivity
   change and generate separate inter-VG messages.  Recipients of these
   messages may not be able to determine which message is more recent if
   policy gateway internal clocks are not perfectly synchronized.
   Moreover, even if the clocks were perfectly synchronized, and hence
   message recency could be consistently determined, it is possible for
   each peer to issue its inter-VG message before receiving current
   information from the other.  As a result, neither inter-VG message
   contains the correct connectivity from the perspective of the virtual
   gateway.  However, these problems are eliminated if all inter-VG
   messages are generated by a single peer within a virtual gateway, in
   particular the lowest-numbered operational policy gateway.

   An inter-VG message is "acceptable" if:

   - It passes the CMTP validation checks.

   - Its timestamp is less than vgp_old (300) seconds behind the
     recipient's internal clock time.

   - Its virtual gateway identifier coincides with that of a virtual
     gateway configured for the recipient's domain.

   - Its source policy gateway identifier represents the lowest numbered
     operational member of the issuing virtual gateway, reachable from
     the recipient.




Steenstrup                                                     [Page 30]

RFC 1479                     IDPR Protocol                     July 1993


   Distribution of intra-VG messages among peers often triggers
   generation and distribution of inter-VG messages among virtual
   gateways.  Usually, the lowest-numbered operational policy gateway in
   a virtual gateway generates and distributes an inter-VG message
   immediately after detecting a change in virtual gateway connectivity,
   through receipt or generation of an intra-VG message.  However, if
   this policy gateway is also waiting for an intra-VG message from a
   newly reachable peer, it does not immediately generate and distribute
   the inter-VG message.

   Waiting for intra-VG messages enables the lowest-numbered operational
   policy gateway in a virtual gateway to gather the most recent
   connectivity information for inclusion in the inter-VG message.
   However, under unusual circumstances, the policy gateway may fail to
   receive an intra-VG message from a newly reachable peer, even after
   actively requesting such a message.  To accommodate this case, VGP
   uses an upper bound of four times the configured retransmission
   interval, vgp_int microseconds, on the amount of time to wait before
   generating and distributing an inter-VG message, when receipt of an
   intra-VG message is pending.

3.1.4.  VG Representatives

   When distributing an inter-VG message, the issuing policy gateway
   selects as recipients one neighbor, the VG Representative, from each
   virtual gateway in the domain.  To be selected as a VG
   representative, a policy gateway must be reachable from the issuing
   policy gateway via intra-domain routing.  The issuing policy gateway
   gives preference to neighbors that are members of more than one
   virtual gateway.  Such a neighbor acts as a VG representative for all
   virtual gateways of which it is a member and restricts inter-VG
   message distribution as follows: any policy gateway that is a peer in
   more than one of the represented virtual gateways receives at most
   one copy of the inter-VG message.  This message distribution strategy
   minimizes the number of message copies required for disseminating
   inter-VG information.

3.2.  Up/Down Protocol

   Directly-connected adjacent policy gateways execute the Up/Down
   Protocol to determine mutual reachability.  Pairs of peer or neighbor
   policy gateways can determine mutual reachability through information
   provided by the intra-domain routing procedure or through execution
   of the up/down protocol.  In general, we do not recommend
   implementing the up/down protocol between each pair of policy
   gateways in a domain, as it results in O(n**2) (where n is the number
   of policy gateways within the domain) communications complexity.
   However, if the intra-domain routing procedure is slow to detect



Steenstrup                                                     [Page 31]

RFC 1479                     IDPR Protocol                     July 1993


   connectivity changes or is unable to report reachability at the IDPR
   entity level, the reachability information obtained through the
   up/down protocol may well be worth the extra communications cost.  In
   the remainder of this section, we decribe the up/down protocol from
   the perspective of adjacent policy gateways, but we note that the
   identical protocol can be applied to peer and neighbor policy
   gateways as well.

   The up/down protocol determines whether the direct connection between
   adjacent policy gateways is acceptable for data traffic transport.  A
   direct connection is presumed to be "down" (unacceptable for data
   traffic transport) until the up/down protocol declares it to be "up"
   (acceptable for data traffic transport).  We say that a virtual
   gateway is "up" if there exists at least one pair of adjacent policy
   gateways whose direct connection is acceptable for data traffic
   transport, and that a virtual gateway is "down" if there exists no
   such pair of adjacent policy gateways.

   When executing the up/down protocol, policy gateways exchange UP/DOWN
   messages every ud_per (1) second.  All policy gateways use the same
   default period of ud_per initially and then negotiate a preferred
   period through exchange of UP/DOWN messages.  A policy gateway
   reports its desired value for ud_per within its UP/DOWN messages.  It
   then chooses the larger of its desired value and that of the adjacent
   policy gateway as the period for exchanging subsequent UP/DOWN
   messages.  Policy gateways also exchange, in UP/DOWN messages,
   information about the identity of their respective domain components.
   This information assists the policy gateways in selecting routes
   across virtual gateways to partitioned domains.

   Each UP/DOWN message is transported using CMTP and hence is covered
   by the CMTP validation checks.  However, unlike other IDPR control
   messages, UP/DOWN messages do not require reliable transport.
   Specifically, the up/down protocol requires only a single
   transmission per UP/DOWN message and never directs CMTP to return an
   ACK.  As pair-PG messages, UP/DOWN messages are acceptable under the
   conditions described in section 3.1.1.

   Each policy gateway assesses the state of its direct connection, to
   the adjacent policy gateway, by counting the number of acceptable
   UP/DOWN messages received within a set of consecutive periods.  A
   policy gateway communicates its perception of the state of the direct
   connection through its UP/DOWN messages.  Initially, a policy gateway
   indicates the down state in each of its UP/DOWN messages.  Only when
   the direct connection appears to be up from its perspective does a
   policy gateway indicate the up state in its UP/DOWN messages.

   A policy gateway can begin to transport data traffic over a direct



Steenstrup                                                     [Page 32]

RFC 1479                     IDPR Protocol                     July 1993


   connection only if both of the following conditions are true:

   - The policy gateway receives from the adjacent policy gateway at
     least j acceptable UP/DOWN messages within the last m consecutive
     periods.  From the recipient policy gateway's perspective, this
     event up.  Hence, the recipient policy gateway indicates the up
     state in its subsequent UP/DOWN messages.

   - The UP/DOWN message most recently received from the adjacent policy
     gateway indicates the up state, signifying that the adjacent policy
     gateway considers the direct connection to be up.

   A policy gateway must cease to transport data traffic over a direct
   connection whenever either of the following conditions is true:

   - The policy gateway receives from the adjacent policy gateway at
     most acceptable UP/DOWN messages within the last n consecutive
     periods.

   - The UP/DOWN message most recently received from the adjacent policy
     gateway indicates the down state, signifying that the adjacent
     policy gateway considers the direct connection to be down.

   From the recipient policy gateway's perspective, either of these
   events constitutes a state transition of the direct connection from
   up to down.  Hence, the policy gateway indicates the down state in
   its subsequent UP/DOWN messages.

3.3.  Implementation

   We recommend implementing the up/down protocol using a sliding
   window.  Each window slot indicates the UP/DOWN message activity
   during a given period, containing either a "hit" for receipt of an
   acceptable UP/DOWN message or a "miss" for failure to receive an
   acceptable UP/DOWN message.  In addition to the sliding window, the
   implementation should include a tally of hits recorded during the
   current period and a tally of misses recorded over the current
   window.

   When the direct connection moves to the down state, the initial
   values of the up/down protocol parameters must be set as follows:

   -   The sliding window size is equal to m.

   -   Each window slot contains a miss.

   -   The current period hit tally is equal to 0.




Steenstrup                                                     [Page 33]

RFC 1479                     IDPR Protocol                     July 1993


   -   The current window miss tally is equal to m.

   When the direct connection moves to the up state, the initial values
   of the up/down protocol parameters must be set as follows:

   -   The sliding window size is equal to n.

   -   Each window slot contains a hit.

   -   The current period hit tally is equal to 0.

   -   The current window miss tally is equal to 0.

   At the conclusion of each period, a policy gateway computes the miss
   tally and determines whether there has been a state transition of the
   direct connection to the adjacent policy gateway.  In the down state,
   a miss tally of no more than m - j signals a transition to the up
   state.  In the up state, a miss tally of no less than n - k signals a
   transition to the down state.

   Computing the correct miss tally involves several steps.  First, the
   policy gateway prepares to slide the window by one slot so that the
   oldest slot disappears, making room for the newest slot.  However,
   before sliding the window, the policy gateway checks the contents of
   the oldest window slot.  If this slot contains a miss, the policy
   gateway decrements the miss tally by 1, as this slot is no longer
   part of the current window.

   After sliding the window, the policy gateway determines the proper
   contents.  If the hit tally for the current period equals 0, the
   policy gateway records a miss for the newest slot and increments the
   miss tally by 1.  Otherwise, if the hit tally for the current period
   is greater than 0, the policy gateway records a hit for the newest
   slot and decrements the hit tally by 1.  Moreover, the policy gateway
   applies any remaining hits to slots containing misses, beginning with
   the newest and progressing to the oldest such slot.  For each such
   slot containing a miss, the policy gateway records a hit in that slot
   and decrements both the hit and miss tallies by 1, as the hit cancels
   out a miss.  The policy gateway continues to apply each remaining hit
   tallied to any slot containing a miss, until either all such hits are
   exhausted or all such slots are accounted for.  Before beginning the
   next up/down period, the policy gateway resets the hit tally to 0.

   Although we expect the hit tally, within any given period, to be no
   greater than 1, we do anticipate the occasional period in which a
   policy gateway receives more than one UP/DOWN message from an
   adjacent policy gateway.  The most common reasons for this occurrence
   are message delay and clock drift.  When an UP/DOWN message is



Steenstrup                                                     [Page 34]

RFC 1479                     IDPR Protocol                     July 1993


   delayed, the receiving policy gateway observes a miss in one period
   followed by two hits in the next period, one of which cancels the
   previous miss.  However, excess hits remaining in the tally after
   miss cancellation indicate a problem, such as clock drift.  Thus,
   whenever a policy gateway accumulates excess hits, it logs the event
   for network management.

   When clock drift occurs between two adjacent policy gateways, it
   causes the period of one policy gateway to grow with respect to the
   period of the other policy gateway.  Let p(X) be the period for PG X,
   let p(Y) be the period for PG Y, and let g and h be the smallest
   positive integers such that g * p(X) = h * p(Y).  Suppose that p(Y) >
   p(X) because of clock drift.  In this case, PG X observes g - h
   misses in g consecutive periods, while PG Y observes g - h surplus
   hits in h consecutive periods.  As long as (g - h)/g < (n - k)/n and
   (g - h)/g < or = (m - j)/m, the clock drift itself will not cause the
   direct connection to enter or remain in the down state.

3.4.  Policy Gateway Connectivity

   Policy gateways collect connectivity information through the intra-
   domain routing procedure and through VGP, and they distribute
   connectivity changes through VGP in both intra-VG messages to peers
   and inter-VG messages to neighbors.  Locally, this connectivity
   information assists policy gateways in selecting routes, not only
   across a virtual gateway to an adjacent domain but also across a
   domain between two virtual gateways.  Moreover, changes in
   connectivity between domains are distributed, in routing information
   messages, to route servers throughout an internetwork.

3.4.1.  Within a Virtual Gateway

   Each policy gateway within a virtual gateway constantly monitors its
   connectivity to all adjacent and to all peer policy gateways.  To
   determine the state of its direct connection to an adjacent policy
   gateway, a policy gateway uses reachability information supplied by
   the up/down protocol.  To determine the state of its intra-domain
   routes to a peer policy gateway, a policy gateway uses reachability
   information supplied by either the intra-domain routing procedure or
   the up/down protocol.

   A policy gateway generates a PG CONNECT message whenever either of
   the following conditions is true:

   -   The policy gateway detects a change, in state or in adjacent
       domain component, associated with its direct connection to an
       adjacent policy gateway.  In this case, the policy gateway
       distributes a copy of the message to each peer reachable via



Steenstrup                                                     [Page 35]

RFC 1479                     IDPR Protocol                     July 1993


       intra-domain routing.

   -   The policy gateway detects that a previously unreachable peer is
       now reachable.  In this case, the policy gateway distributes a
       copy of the message to the newly reachable peer.

   A PG CONNECT message is an intra-VG message that includes information
   about each adjacent policy gateway directly connected to the issuing
   policy gateway.  Specifically, the PG CONNECT message contains the
   adjacent policy gateway's identifier, status (reachable or
   unreachable), and domain component identifier.  If a PG CONNECT
   message contains a "request", each peer that receives the message
   responds to the sender with its own PG CONNECT message.

   All mutually reachable peers monitor policy gateway connectivity
   within their virtual gateway, through the up/down protocol, the
   intra-domain routing procedure, and the exchange of PG CONNECT
   messages.  Within a given virtual gateway, each constituent policy
   gateway maintains the following information about each configured
   adjacent policy gateway:

   - The identifier for the adjacent policy gateway.

   - The status of the adjacent policy gateway: reachable/unreachable,
     directly connected/not directly connected.

   - The local exit interfaces used to reach the adjacent policy
     gateway, provided it is reachable.

   - The identifier for the adjacent policy gateway's domain component.

   - The set of peers to which the adjacent policy gateway is
     directly-connected.

   Hence, all mutually reachable peers can detect changes in
   connectivity across the virtual gateway to adjacent domain
   components.

   When the lowest-numbered operational peer policy gateway within a
   virtual gateway detects a change in the set of adjacent domain
   components reachable through direct connections across the given
   virtual gateway, it generates a VGCONNECT message and distributes a
   copy to a VG representative in all other virtual gateways connected
   to its domain.  A VG CONNECT message is an inter-VG message that
   includes information about each peer's connectivity across the given
   virtual gateway.  Specifically, the VG CONNECT message contains, for
   each peer, its identifier and the identifiers of the domain
   components reachable through its direct connections to adjacent



Steenstrup                                                     [Page 36]

RFC 1479                     IDPR Protocol                     July 1993


   policy gateways.  Moreover, the VG CONNECT message gives each
   recipient enough information to determine the state, up or down, of
   the issuing virtual gateway.

   The issuing policy gateway, namely the lowest-numbered operational
   peer, may have to wait up to four times vgp_int microseconds after
   detecting the connectivity change, before generating and distributing
   the VGCONNECT message, as described in section 3.1.3.  Each recipient
   VG representative in turn distributes a copy of the VG CONNECT
   message to each of its peers reachable via intra-domain routing.  If
   a VG CONNECT message contains a "request", then in each recipient
   virtual gateway, the lowest-numbered operational peer that receives
   the message responds to the original sender with its own VGCONNECT
   message.

3.4.2.  Between Virtual Gateways

   At present, we expect transit policies to be uniform over all intra-
   domain routes between any pair of policy gateways within a domain.
   However, when tariffed qualities of service become prevalent
   offerings for intra-domain routing, we can no longer expect
   uniformity of transit policies throughout a domain.  To monitor the
   transit policies supported on intra-domain routes between virtual
   gateways requires both a policy-sensitive intra-domain routing
   procedure and a VGP exchange of policy information between neighbor
   policy gateways.

   Each policy gateway within a domain constantly monitors its
   connectivity to all peer and neighbor policy gateways, including the
   transit policies supported on intra-domain routes to these policy
   gateways.  To determine the state of its intra-domain connection to a
   peer or neighbor policy gateway, a policy gateway uses reachability
   information supplied by either the intra-domain routing procedure or
   the up/down protocol.  To determine the transit policies supported on
   intra-domain routes to a peer or neighbor policy gateway, a policy
   gateway uses policy-sensitive reachability information supplied by
   the intra-domain routing procedure.  We note that when transit
   policies are uniform over a domain, reachability and policy-sensitive
   reachability are equivalent.

   Within a virtual gateway, each constituent policy gateway maintains
   the following information about each configured peer and neighbor
   policy gateway:

   - The identifier for the peer or neighbor policy gateway.

   - The identifiers corresponding to the transit policies configured to
     be supported by intra-domain routes to the peer or neighbor policy



Steenstrup                                                     [Page 37]

RFC 1479                     IDPR Protocol                     July 1993


     gateway.

   - According to each transit policy, the status of the peer or
     neighbor policy gateway: reachable/unreachable.

   - For each transit policy, the local exit interfaces used to reach
     the peer or neighbor policy gateway, provided it is reachable.

   - The identifiers for the adjacent domain components reachable
     through direct connections from the peer or neighbor policy
     gateway, obtained through VG CONNECT messages.

   Using this information, a policy gateway can detect changes in its
   connectivity to an adjoining domain component, with respect to a
   given transit policy and through a given neighbor.  Moreover,
   combining the information obtained for all neighbors within a given
   virtual gateway, the policy gateway can detect changes in its
   connectivity, with respect to a given transit policy, to that virtual
   gateway and to adjoining domain components reachable through that
   virtual gateway.

   All policy gateways mutually reachable via intra-domain routes
   supporting a configured transit policy need not exchange information
   about perceived changes in connectivity, with respect to the given
   transit policy.  In this case, each policy gateway can infer
   another's policy-sensitive reachability to a third, through mutual
   intra-domain reachability information provided by the intra-domain
   routing procedure.  However, whenever two or more policy gateways are
   no longer mutually reachable with respect to a given transit policy,
   these policy gateways can no longer infer each other's reachability
   to other policy gateways, with respect to that transit policy.  In
   this case, these policy gateways must exchange explicit information
   about changes in connectivity to other policy gateways, with respect
   to that transit policy.

   A policy gateway generates a PG POLICY message whenever either of the
   following conditions is true:

   - The policy gateway detects a change in its connectivity to another
     virtual gateway, with respect to a configured transit policy, or to
     an adjoining domain component reachable through that virtual
     gateway.  In this case, the policy gateway distributes a copy of
     the message to each peer reachable via intra-domain routing but not
     currently reachable via any intra-domain routes of the given
     transit policy.

   - The policy gateway detects that a previously unreachable peer is
     reachable.  In this case, the policy gateway distributes a copy of



Steenstrup                                                     [Page 38]

RFC 1479                     IDPR Protocol                     July 1993


     the message to the newly reachable peer.

   A PG POLICY message is an intra-VG message that includes information
   about each configured transit policy and each virtual gateway
   configured to be reachable from the issuing policy gateway via
   intra-domain routes of the given transit policy.  Specifically, the
   PGPOLICY message contains, for each configured transit policy:

   - The identifier for the transit policy.

   - The identifiers for the virtual gateways associated with the given
     transit policy and currently reachable, with respect to that
     transit policy, from the issuing policy gateway.

   - The identifiers for the domain components reachable from and
     adjacent to the members of the given virtual gateways.

   If a PG POLICY message contains a "request", each peer that receives
   the message responds to the original sender with its own PG POLICY
   message.

   In addition to connectivity between itself and its neighbors, each
   policy gateway also monitors the connectivity, between domain
   components adjacent to its virtual gateway and domain components
   adjacent to other virtual gateways, through its domain and with
   respect to the configured transit policies.  For each member of each
   of its virtual gateways, a policy gateway monitors:

   -  The set of  adjacent domain components  currently reachable
     through direct connections across the given virtual gateway.  The
     policy gateway obtains this information through PG CONNECT messages
     from reachable peers and through UP/DOWN messages from adjacent
     policy gateways.

   - For each configured transit policy, the set of virtual gateways
     currently reachable from the given virtual gateway with respect to
     that transit policy and the set of adjoining domain components
     currently reachable through direct connections across those virtual
     gateways.  The policy gateway obtains this information through PG
     POLICY messages from peers, VG CONNECT messages from neighbors, and
     the intra-domain routing procedure.  Using this information, a
     policy gateway can detect connectivity changes, through its domain
     and with respect to a given transit policy, between adjoining
     domain components.

   When the lowest-numbered operational policy gateway within a virtual
   gateway detects a change in the connectivity between a domain
   component adjacent to its virtual gateway and a domain component



Steenstrup                                                     [Page 39]

RFC 1479                     IDPR Protocol                     July 1993


   adjacent to another virtual gateway in its domain, with respect to a
   configured transit policy, it generates a VG POLICY message and
   distributes a copy to a VG representative in selected virtual
   gateways connected to its domain.  In particular, the lowest-numbered
   operational policy gateway distributes a VG POLICY message to a VG
   representative in every other virtual gateway containing a member
   reachable via intra-domain routing but not currently reachable via
   any routes of the given transit policy.  A VG POLICY message is an
   inter-VG message that includes information about the connectivity
   between domain components adjacent to the issuing virtual gateway and
   domain components adjacent to the other virtual gateways in the
   domain, with respect to configured transit policies.  Specifically,
   the VG POLICY message contains, for each transit policy:

   - The identifier for the transit policy.

   - The identifiers for the virtual gateways associated with the given
     transit policy and currently reachable, with respect to that
     transit policy, from the issuing virtual gateway.

   - The identifiers for the domain components reachable from and
     adjacent to the members of the given virtual gateways.

   The issuing policy gateway, namely the lowest-numbered operational
   peer, may have to wait up to four times vgp_int microseconds after
   detecting the connectivity change, before generating and distributing
   the VG POLICY message, as described in section 3.1.3.  Each recipient
   VG representative in turn distributes a copy of the VG POLICY message
   to each of its peers reachable via intra-domain routing.  If a VG
   POLICY message contains a "request", then in each recipient virtual
   gateway, the lowest-numbered operational peer that receives the
   message responds to the original sender with its own VG POLICY
   message.

3.4.3.  Communication Complexity

   We offer an example, to provide an estimate of the number of VGP
   messages exchanged within a domain, AD X, after a detected change in
   policy gateway connectivity.  Suppose that an adjacent domain, AD Y,
   partitions such that the partition is detectable through the exchange
   of UP/DOWN messages across a virtual gateway connecting AD X and AD
   Y.  Let V be the number of virtual gateways in AD X.  Suppose each
   virtual gateway contains P peer policy gateways, and no policy
   gateway is a member of multiple virtual gateways.  Then, within AD X,
   the detected partition will result in the following VGP message
   exchanges:

   - P policy gateways each receive at most P-1 PG CONNECT messages.



Steenstrup                                                     [Page 40]

RFC 1479                     IDPR Protocol                     July 1993


     Each policy gateway detecting the adjacent domain partition
     generates a PG CONNECT message and distributes it to each reachable
     peer in the virtual gateway.

   - P * (V-1) policy gateways each receive at most one VG CONNECT
     message.  The lowest-numbered operational policy gateway in the
     virtual gateway detecting the partition of the adjacent domain
     generates a VG CONNECT message and distributes it to a VG
     representative in all other virtual gateways connected to the
     domain.  In turn, each VG representative distributes the VG CONNECT
     message to each reachable peer within its virtual gateway.

   - P * (V-1) policy gateways each receive at most P-1 PG POLICY
     messages, and only if the domain has more than a single uniform
     transit policy.  Each policy gateway in each virtual gateway
     generates a PG POLICY message and distributes it to all reachable
     peers not currently reachable with respect to the given transit
     policy.

   - P * V policy gateways each receive at most V-1 VG POLICY messages,
     only if the domain has more than a single uniform transit policy.
     The lowest-numbered operational policy gateway in each virtual
     gateway generates a VG POLICY message and distributes it to a VG
     representative in all other virtual gateways containing at least
     one reachable member not currently reachable with respect to the
     given transit policy.  In turn, each VG representative distributes
     a VG POLICY message to each peer within its virtual gateway.

3.5.  VGP Message Formats

   The virtual gateway protocol number is equal to 0.  We describe the
   contents of each type of VGP message below.

3.5.1.  UP/DOWN

   The UP/DOWN message type is equal to 0.

    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |            SRC CMP            |            DST AD             |
   +-------------------------------+---------------+---------------+
   |            DST PG             |    PERIOD     |     STATE     |
   +-------------------------------+---------------+---------------+

   SRC CMP
        (16 bits) Numeric identifier for the domain component containing
        the issuing policy gateway.



Steenstrup                                                     [Page 41]

RFC 1479                     IDPR Protocol                     July 1993


   DST AD (16 bits) Numeric identifier for the destination domain.

   DST PG (16 bits) Numeric identifier for the destination policy
        gateway.

   PERIOD (8 bits) Length of the UP/DOWN message generation period, in
        seconds.

   STATE (8 bits) Perceived state (1 up, 0 down) of the direct
        connection from the perspective of the issuing policy gateway,
        contained in the right-most bit.

3.5.2.  PG CONNECT

   The PG CONNECT message type is equal to 1.  PG CONNECT messages are
   not required for any virtual gateway containing exactly two policy
   gateways.

    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |            ADJ AD             |      VG       |     RQST      |
   +-------------------------------+---------------+---------------+
   |            NUM RCH            |           NUM UNRCH           |
   +-------------------------------+-------------------------------+
   For each reachable adjacent policy gateway:
   +-------------------------------+-------------------------------+
   |            ADJ PG             |            ADJ CMP            |
   +-------------------------------+-------------------------------+
   For each unreachable adjacent policy gateway:
   +-------------------------------+
   |            ADJ PG             |
   +-------------------------------+

   ADJ AD
        (16 bits) Numeric identifier for the adjacent domain.

   VG (8 bits) Numeric identifier for the virtual gateway.

   RQST (8 bits) Request for a PG CONNECT message (1 request, 0 no
        request) from each recipient peer, contained in the right-most
        bit.

   NUM RCH (16 bits) Number of adjacent policy gateways within the
        virtual gateway, which are directly-connected to and currently
        reachable from the issuing policy gateway.

   NUM UNRCH (16 bits) Number of adjacent policy gateways within the



Steenstrup                                                     [Page 42]

RFC 1479                     IDPR Protocol                     July 1993


        virtual gateway, which are directly-connected to but not
        currently reachable from the issuing policy gateway.

   ADJ PG (16 bits) Numeric identifier for a directly-connected adjacent
        policy gateway.

   ADJ CMP (16 bits) Numeric identifier for the domain component
        containing the reachable, directly-connected adjacent policy
        gateway.

3.5.3.  PG POLICY

   The PG POLICY message type is equal to 2.  PG POLICY messages are not
   required for any virtual gateway containing exactly two policy
   gateways or for any domain with a single uniform transit policy.

    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |            ADJ AD             |      VG       |     RQST      |
   +-------------------------------+---------------+---------------+
   |            NUM TP             |
   +-------------------------------+
   For each transit policy associated with the virtual gateway:
   +-------------------------------+-------------------------------+
   |              TP               |            NUM VG             |
   +-------------------------------+-------------------------------+
   For each virtual gateway reachable via the transit policy:
   +-------------------------------+---------------+---------------+
   |            ADJ AD             |      VG       |    UNUSED     |
   +-------------------------------+---------------+---------------+
   |            NUM CMP            |            ADJ CMP            |
   +-------------------------------+-------------------------------+

   ADJ AD
        (16 bits) Numeric identifier for the adjacent domain.

   VG (8 bits) Numeric identifier for the virtual gateway.

   RQST (8 bits) Request for a PG POLICY message (1 request, 0 no
        request) from each recipient peer, contained in the right-most
        bit.

   NUM TP (8 bits) Number of transit policies configured to include the
        virtual gateway.

   TP (16 bits) Numeric identifier for a transit policy associated with
        the virtual gateway.



Steenstrup                                                     [Page 43]

RFC 1479                     IDPR Protocol                     July 1993


   NUM VG (16 bits) Number of virtual gateways reachable from the
        issuing policy gateway, via intra-domain routes supporting the
        transit policy.

   UNUSED (8 bits) Not currently used; must be set equal to 0.

   NUM CMP (16 bits) Number of adjacent domain components reachable via
        direct connections through the virtual gateway.

   ADJ CMP (16 bits) Numeric identifier for a reachable adjacent domain
        component.

3.5.4.  VG CONNECT

   The VG CONNECT message type is equal to 3.

    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |            ADJ AD             |      VG       |     RQST      |
   +-------------------------------+---------------+---------------+
   |            NUM PG             |
   +-------------------------------+
   For each reach policy gateway in the virtual gateway:
   +-------------------------------+-------------------------------+
   |              PG               |            NUM CMP            |
   +-------------------------------+-------------------------------+
   |            ADJ CMP            |
   +-------------------------------+

   ADJ AD
        (16 bits) Numeric identifier for the adjacent domain.

   VG (8 bits) Numeric identifier for the virtual gateway.

   RQST (8 bits) Request for a VG CONNECT message (1 request, 0 no
        request) from a recipient in each virtual gateway, contained in
        the right-most bit.

   NUM PG (16 bits) Number of mutually-reachable peer policy gateways in
        the virtual gateway.

   PG (16 bits) Numeric identifier for a peer policy gateway.

   NUM CMP (16 bits) Number of components of the adjacent domain
        reachable via direct connections from the policy gateway.





Steenstrup                                                     [Page 44]

RFC 1479                     IDPR Protocol                     July 1993


   ADJ CMP (16 bits) Numeric identifier for a reachable adjacent domain
        component.

3.5.5.  VG POLICY

   The VG POLICY message type is equal to 4.  VG POLICY messages are not
   required for any domain with a single uniform transit policy.

    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |            ADJ AD             |      VG       |     RQST      |
   +-------------------------------+---------------+---------------+
   |            NUM TP             |
   +-------------------------------+
   For each transit policy associated with the virtual gateway:
   +-------------------------------+-------------------------------+
   |              TP               |            NUM GRP            |
   +-------------------------------+-------------------------------+
   For each virtual gateway group reachable via the transit policy:
   +-------------------------------+-------------------------------+
   |            NUM VG             |            ADJ AD             |
   +---------------+---------------+-------------------------------+
   |     VG        |    UNUSED     |            NUM CMP            |
   +---------------+---------------+-------------------------------+
   |            ADJ CMP            |
   +-------------------------------+

   ADJ AD
        (16 bits) Numeric identifier for the adjacent domain.

   VG (8 bits) Numeric identifier for the virtual gateway.

   RQST (8 bits) Request for a VG POLICY message (1 request, 0 no
        request) from a recipient in each virtual gateway, contained in
        the right-most bit.

   NUM TP (16 bits) Number of transit policies configured to include the
        virtual gateway.

   TP (16 bits) Numeric identifier for a transit policy associated with
        the virtual gateway.

   NUM GRP (16 bits) Number of groups of virtual gateways, such that all
        members in a group are reachable from the issuing virtual
        gateway via intra-domain routes supporting the given transit
        policy.




Steenstrup                                                     [Page 45]

RFC 1479                     IDPR Protocol                     July 1993


   NUM VG (16 bits) Number of virtual gateways in a virtual gateway
        group.

   UNUSED (8 bits) Not currently used; must be set equal to 0.

   NUM CMP (16 bits) Number of adjacent domain components reachable via
        direct connections through the virtual gateway.

   ADJ CMP (16 bits) Numeric identifier for a reachable adjacent domain
        component.

   Normally, each VG POLICY message will contain a single virtual
   gateway group.  However, if the issuing virtual gateway becomes
   partitioned such that peers are mutually reachable with respect to
   some transit policies but not others, virtual gateway groups may be
   necessary.  For example, let PG X and PG Y be two peers in VG A which
   configured to support transit policies 1 and 2.  Suppose that PG X
   and PG Y are reachable with respect to transit policy 1 but not with
   respect to transit policy 2.  Furthermore, suppose that PG X can
   reach members of VG B via intra-domain routes of transit policy 2 and
   that PG Y can reach members of VG C via intra-domain routes of
   transit policy 2.  Then the entry in the VG POLICY message issued by
   VG A will include, for transit policy 2, two groups of virtual
   gateways, one containing VG B and one containing VG C.

3.5.6.  Negative Acknowledgements

   When a policy gateway receives an unacceptable VGP message that
   passes the CMTP validation checks, it includes, in its CMTP ACK, an
   appropriate VGP negative acknowledgement.  This information is placed
   in the INFORM field of the CMTP ACK (described previously in section
   2.4); the numeric identifier for each type of VGP negative
   acknowledgement is contained in the left-most 8 bits of the INFORM
   field.  Negative acknowledgements associated with VGP include the
   following types:

   1.  Unrecognized VGP message type.  Numeric identifier for the
       unrecognized message type (8 bits).

   2.  Out-of-date VGP message.

   3.  Unrecognized virtual gateway source.  Numeric identifier for the
       unrecognized virtual gateway including the adjacent domain
       identifier (16 bits) and the local identifier (8 bits).







Steenstrup                                                     [Page 46]

RFC 1479                     IDPR Protocol                     July 1993


4.  Routing Information Distribution

   Each domain participating in IDPR generates and distributes its
   routing information messages to route servers throughout an
   internetwork.  IDPR routing information messages contain information
   about the transit policies in effect across the given domain and the
   virtual gateway connectivity to adjacent domains.  Route servers in
   turn use IDPR routing information to generate policy routes between
   source and destination domains.

   There are three different procedures for distributing IDPR routing
   information:

   - The flooding protocol.  In this case, a representative policy
     gateway in each domain floods its routing information messages to
     route servers in all other domains.

   - Remote route server communication.  In this case, a route server
     distributes its domain's routing information messages to route
     servers in specific destination domains, by encapsulating these
     messages within IDPR data messages.  Thus, a domain administrator
     may control the distribution of the domain's routing information by
     restricting routing information exchange with remote route servers.
     Currently, routing information distribution restrictions are not
     included in IDPR configuration information.

   - The route server query protocol.  In this case, a policy gateway or
     route server requests routing information from another route
     server, which in turn responds with routing information from its
     database.  The route server query protocol may be used for quickly
     updating the routing information maintained by a policy gateway
     or route server that has just been connected or reconnected to an
     internetwork.  It may also be used to retrieve routing information
     from domains that restrict distribution of their routing
     information.

   In this section, we describe the flooding protocol only.  In section
   5, we describe the route server query protocol, and in section 5.2,
   we describe communication between route servers in separate domains.

   Policy gateways and route servers use CMTP for reliable transport of
   IDPR routing information messages flooded between peer, neighbor, and
   adjacent policy gateways and between those policy gateways and route
   servers.  The issuing policy gateway must communicate to CMTP the
   maximum number of transmissions per routing information message,
   flood_ret, and the interval between routing information message
   retransmissions, flood_int microseconds.  The recipient policy
   gateway or route server must determine routing information message



Steenstrup                                                     [Page 47]

RFC 1479                     IDPR Protocol                     July 1993


   acceptability, as we describe in section 4.2.3 below.

4.1.  AD Representatives

   We designate a single policy gateway, the "AD representative", for
   generating and distributing IDPR routing information about its
   domain, to ensure that the routing information distributed is
   consistent and unambiguous and to minimize the communication required
   for routing information distribution.  There is usually only a single
   AD representative per domain, namely the lowest-numbered operational
   policy gateway in the domain.  Within a domain, policy gateways need
   no explicit election procedure to determine the AD representative.
   Instead, all members of a set of policy gateways mutually reachable
   via intra-domain routes can agree on set membership and therefore on
   which member has the lowest number.

   A partitioned domain has as many AD representatives as it does domain
   components.  In fact, the numeric identifier for an AD representative
   is identical to the numeric identifier for a domain component.  One
   cannot normally predict when and where a domain partition will occur,
   and thus any policy gateway within a domain may become an AD
   representative at any time.  To prepare for the role of AD
   representative in the event of a domain partition, every policy
   gateway must continually monitor its domain's IDPR routing
   information, through VGP and through the intra-domain routing
   procedure.

4.2.  Flooding Protocol

   An AD representative policy gateway uses unrestricted flooding among
   all domains to distribute its domain's IDPR routing information
   messages to route servers in an internetwork.  There are two kinds of
   IDPR routing information messages issued by each AD representative:
   CONFIGURATION and DYNAMIC messages.  Each CONFIGURATION message
   contains the transit policy information configured by the domain
   administrator, including for each transit policy, its identifier, its
   specification, and the sets of virtual gateways configured as
   mutually reachable via intra-domain routes supporting the given
   transit policy.  Each DYNAMIC message contains information about
   current virtual gateway connectivity to adjacent domains and about
   the sets of virtual gateways currently mutually reachable via intra-
   domain routes supporting the configured transit policies.

   The IDPR Flooding Protocol is similar to the flooding procedures
   described in [9]-[11].  Through flooding, the AD representative
   distributes its routing information messages to route servers in its
   own domain and in adjacent domains.  After generating a routing
   information message, the AD representative distributes a copy to each



Steenstrup                                                     [Page 48]

RFC 1479                     IDPR Protocol                     July 1993


   of its peers and to a selected VG representative (see section 3.1.4)
   in all other virtual gateways connected to the domain.  Each VG
   representative in turn distributes a copy of the routing information
   message to each of its peers.  We note that distribution of routing
   information messages among virtual gateways and among peers within a
   virtual gateway is identical to distribution of inter-VG messages in
   VGP, as described in section 3.1.3.

   Within a virtual gateway, each policy gateway distributes a copy of
   the routing information message:

   - To each route server in its configured set of route servers.  A
     domain administrator should ensure that each route server not
     contained within a policy gateway appears in the set of configured
     route servers for at least two distinct policy gateways.  Hence,
     such a route server will continue to receive routing information
     messages, even when one of the policy gateways becomes unreachable.
     However, the route server will normally receive duplicate copies of
     a routing information message.

   - To certain directly-connected adjacent policy gateways.  A policy
     gateway distributes a routing information message to a
     directly-connected adjacent policy gateway in an adjacent domain
     component, only when it is the lowest-numbered operational peer
     with a direct connection to the given domain component.  We note
     that each policy gateway knows, through information provided by
     VGP, which peers have direct connections to which components of
     the adjacent domain.  If the policy gateway has direct connections
     to more than one adjacent policy gateway in that domain component,
     it selects the routing information message recipient according to
     the order in which the adjacent policy gateways appear in its
     database, choosing the first one encountered.  This selection
     procedure ensures that a copy of the routing information message
     reaches each component of the adjacent domain, while limiting the
     number of copies distributed.

   Once a routing information message reaches an adjacent policy
   gateway, that policy gateway distributes copies of the message
   throughout its domain.  The adjacent policy gateway, acting as the
   first recipient of the routing information message in its domain,
   follows the same message distribution procedure as the AD
   representative in the source domain, as described above.  The
   flooding procedure terminates when all reachable route servers in an
   internetwork receive a copy of the routing information message.

   Neighbor policy gateways may receive copies of the same routing
   information message from different adjoining domains.  If two
   neighbor policy gateways receive the message copies simultaneously,



Steenstrup                                                     [Page 49]

RFC 1479                     IDPR Protocol                     July 1993


   they will distribute them to VG representatives in other virtual
   gateways within their domain, resulting in duplicate message
   distribution.  However, each policy gateway stops the spread of
   duplicate routing information messages as soon as it detects them, as
   described in section 4.2.3 below.  In the Internet, we expect
   simultaneous message receptions to be the exception rather than the
   rule, given the hierarchical structure of the current topology.

4.2.1.  Message Generation

   An AD representative generates and distributes a CONFIGURATION
   message whenever there is a configuration change in a transit policy
   or virtual gateway associated with its domain.  This ensures that
   route servers maintain an up-to-date view of a domain's configured
   transit policies and adjacencies.  An AD representative may also
   distribute a CONFIGURATION message at a configurable period of
   conf_per (500) hours.  A CONFIGURATION message contains, for each
   configured transit policy, the identifier assigned by the domain
   administrator, the specification, and the set of associated "virtual
   gateway groups".  Each virtual gateway group comprises virtual
   gateways configured to be mutually reachable via intra-domain routes
   of the given transit policy.  Accompanying each virtual gateway
   listed is an indication of whether the virtual gateway is configured
   to be a domain entry point, a domain exit point, or both according to
   the given transit policy.  The CONFIGURATION message also contains
   the set of local route servers that the domain administrator has
   configured to be available to IDPR clients in other domains.

   An AD representative generates and distributes a DYNAMIC message
   whenever there is a change in currently supported transit policies or
   in current virtual gateway connectivity associated with its domain.
   This ensures that route servers maintain an up-to-date view of a
   domain's supported transit policies and existing adjacencies and how
   they differ from those configured for the domain.  Specifically, an
   AD representative generates a DYNAMIC message whenever there is a
   change in the connectivity, through the given domain and with respect
   to a configured transit policy, between two components of adjoining
   domains.  An AD representative may also distribute a DYNAMIC message
   at a configurable period of dyn_per (24) hours.  A DYNAMIC message
   contains, for each configured transit policy, its identifier,
   associated virtual gateway groups, and domain components reachable
   through virtual gateways in each group.  Each DYNAMIC message also
   contains the set of currently "unavailable", either down or
   unreachable, virtual gateways in the domain.

   We note that each virtual gateway group expressed in a DYNAMIC
   message may be a proper subset of one of the corresponding virtual
   gateway groups expressed in a CONFIGURATION message.  For example,



Steenstrup                                                     [Page 50]

RFC 1479                     IDPR Protocol                     July 1993


   suppose that, for a given domain, the virtual gateway group (VG
   A,...,VG E) were configured for a transit policy such that each
   virtual gateway was both a domain entry and exit point.  Thus, all
   virtual gateways in this group are configured to be mutually
   reachable via intra-domain routes of the given transit policy.  Now
   suppose that VG E becomes unreachable because of a power failure and
   furthermore that the remaining virtual gateways form two distinct
   groups, (VG A,VG B) and (VG C,VG D), such that although virtual
   gateways in both groups are still mutually reachable via some intra-
   domain routes they are no longer mutually reachable via any intra-
   domain routes of the given transit policy.  In this case, the virtual
   gateway groups for the given transit policy now become (VG A,VG B)
   and (VG C,VG D); VG E is listed as an unavailable virtual gateway.

   A route server uses information about the set of unavailable virtual
   gateways to determine which of its routes are no longer viable, and
   it subsequently removes such routes from its route database.
   Although route servers could determine the set of unavailable virtual
   gateways using information about configured virtual gateways and
   currently reachable virtual gateways, the associated processing cost
   is high.  In particular, a route server would have to examine all
   virtual gateway groups listed in a DYNAMIC message to determine
   whether there are any unavailable virtual gateways in the given
   domain.  To reduce the message processing at each route server, we
   have chosen to include the set of unavailable virtual gateways in
   each DYNAMIC message.

   In order to construct a DYNAMIC message, an AD representative
   assembles information gathered from intra-domain routing and from
   VGP.  Specifically, the AD representative uses the following
   information:

   - VG CONNECT and UP/DOWN messages to determine the state, up or down,
     of each of its domain's virtual gateways and the adjacent domain
     components reachable through a given virtual gateway.

   - Intra-domain routing information to determine, for each of its
     domain's transit policies, whether a given virtual gateway in the
     domain is reachable with respect to that transit policy.

   - VG POLICY messages to determine the connectivity of adjoining
     domain components, across the given domain and with respect to a
     configured transit policy, such that these components are adjacent
     to virtual gateways not currently reachable from the AD
     representative's virtual gateway according to the given transit
     policy.





Steenstrup                                                     [Page 51]

RFC 1479                     IDPR Protocol                     July 1993


4.2.2.  Sequence Numbers

   Each IDPR routing information message carries a sequence number
   which, when used in conjunction with the timestamp carried in the
   CMTP message header, determines the recency of the message.  An AD
   representative assigns a sequence number to each routing information
   message it generates, depending upon its internal clock time:

   - The AD representative sets the sequence number to 0, if its
     internal clock time is greater than the timestamp in its previously
     generated routing information message.

   - The AD representative sets the sequence number to 1 greater than
     the sequence number in its previously generated routing information
     message, if its internal clock time equals the timestamp for its
     previously generated routing information message and if the
     previous sequence number is less than the maximum value
     (currently 2**16 - 1).  If the previous sequence number equals the
     maximum value, the AD representative waits until its internal clock
     time exceeds the timestamp in its previously generated routing
     information message and then sets the sequence number to 0.

   In general, we do not expect generation of multiple distinct IDPR
   routing information messages carrying identical timestamps, and so
   the sequence number may seem superfluous.  However, the sequence
   number may become necessary during synchronization of an AD
   representative's internal clock.  In particular, the AD
   representative may need to freeze the clock value during
   synchronization, and thus distinct sequence numbers serve to
   distinguish routing information messages generated during the clock
   synchronization interval.

4.2.3.  Message Acceptance

   Prior to a policy gateway forwarding a routing information message or
   a route server incorporating routing information into its routing
   information database, the policy gateway or route server assesses
   routing information message acceptability.  An IDPR routing
   information message is "acceptable" if:

   - It passes the CMTP validation checks.

   - Its timestamp is less than conf_old (530) hours behind the
     recipient's internal clock time for CONFIGURATION messages and less
     than dyn_old (25) hours behind the recipient's internal clock time
     for DYNAMIC messages.

   - Its timestamp and sequence number indicate that it is more recent



Steenstrup                                                     [Page 52]

RFC 1479                     IDPR Protocol                     July 1993


     than the currently-stored routing information from the given
     domain.  If there is no routing information currently stored from
     the given domain, then the routing information message contains, by
     default, the more recent information.

   Policy gateways acknowledge and forward acceptable IDPR routing
   information messages, according to the flooding protocol described in
   section 4.2 above.  Moreover, each policy gateway retains the
   timestamp and sequence number for the most recently accepted routing
   information message from each domain and uses these values to
   determine acceptability of routing information messages received in
   the future.  Route servers acknowledge the receipt of acceptable
   routing information messages and incorporate the contents of these
   messages into their routing information databases, contingent upon
   criteria discussed in section 4.2.4 below; however, they do not
   participate in the flooding protocol.  We note that when a policy
   gateway or route server first returns to service, it immediately
   updates its routing information database with routing information
   obtained from another route server, using the route server query
   protocol described in section 5.

   An AD representative takes special action upon receiving an
   acceptable routing information message, supposedly generated by
   itself but originally obtained from a policy gateway or route server
   other than itself.  There are at least three possible reasons for the
   occurrence of this event:

   - The routing information message has been corrupted in a way that is
     not detectable by the integrity/authentication value.

   - The AD representative has experienced a memory error.

   - Some other entity is generating routing information messages on
     behalf of the AD representative.

   In any case, the AD representative logs the event for network
   management.  Moreover, the AD representative must reestablish its own
   routing information messages as the most recent for its domain.  To
   do so, the AD representative waits until its internal clock time
   exceeds the value of the timestamp in the received routing
   information message and then generates a new routing information
   message using the currently-stored domain routing information
   supplied by VGP and by the intra-domain routing procedure.  Note that
   the length of time the AD representative must wait to generate the
   new message is at most cmtp_new (300) seconds, the maximum CMTP-
   tolerated difference between the received message's timestamp and the
   AD representative's internal clock time.




Steenstrup                                                     [Page 53]

RFC 1479                     IDPR Protocol                     July 1993


   IDPR routing information messages that pass the CMTP validity checks
   but appear less recent than stored routing information are
   unacceptable.  Policy gateways do not forward unacceptable routing
   information messages, and route servers do not incorporate the
   contents of unacceptable routing information messages into their
   routing information databases.  Instead, the recipient of an
   unacceptable routing information message acknowledges the message in
   one of two ways:

   - If the routing information message timestamp and sequence number
     equal to the timestamp and sequence number associated with the
     stored routing information for the given domain, the recipient
     assumes that the routing information message is a duplicate and
     acknowledges the message.

   - If the routing information message timestamp and sequence number
     indicate that the message is less recent than the stored routing
     information for the domain, the recipient acknowledges the message
     with an indication that the routing information it contains is
     out-of-date.  Such a negative acknowledgement is a signal to the
     sender of the routing information message to request more up-to-
     date routing information from a route server, using the route
     server query protocol.  Furthermore, if the recipient of the out-
     of-date routing information message is a route server, it
     regenerates a routing information message from its own routing
     information database and forwards the message to the sender.  The
     sender may in turn propagate this more recent routing information
     message to other policy gateways and route servers.

4.2.4.  Message Incorporation

   A route server usually stores the entire contents of an acceptable
   IDPR routing information message in its routing information database,
   so that it has access to all advertised transit policies when
   generating a route and so that it can regenerate routing information
   messages at a later point in time if requested to do so by another
   route server or policy gateway.  However, a route server may elect
   not to store all routing information message contents.  In
   particular, the route server need not store any transit policy that
   excludes the route server's domain as a source or any routing
   information from a domain that the route server's domain's source
   policies exclude for transit.  Selective storing of routing
   information message contents simplifies the route generation
   procedure since it reduces the search space of possible routes, and
   it limits the amount of route server memory devoted to routing
   information.  However, selective storing of routing information also
   means that the route server cannot always regenerate the original
   routing information message, if requested to do so by another route



Steenstrup                                                     [Page 54]

RFC 1479                     IDPR Protocol                     July 1993


   server or policy gateway.

   An acceptable IDPR routing information message may contain transit
   policy information that is not well-defined according to the route
   server's perception.  A CONFIGURATION message may contain an
   unrecognized domain, virtual gateway, or transit policy attribute,
   such as user class access restrictions or offered service.  In this
   case, "unrecognized" means that the value in the routing information
   message is not listed in the route server's configuration database,
   as described previously in section 1.8.2.  A DYNAMIC message may
   contain an unrecognized transit policy or virtual gateway.  In this
   case, "unrecognized" means that the transit policy or virtual gateway
   was not listed in the most recent CONFIGURATION message for the given
   domain.

   Each route server can always parse an acceptable routing information
   messsage, even if some of the information is not well-defined, and
   thus can always use the information that it does recognize.
   Therefore, a route server can store the contents of acceptable
   routing information messages from domains in which it is interested,
   regardless of whether all contents appear to be well-defined at
   present.  If a routing message contains unrecognized information, the
   route server may attempt to obtain the additional information it
   needs to decipher the unrecognized information.  For a CONFIGURATION
   message, the route server logs the event for network management; for
   a DYNAMIC message, the route server requests, from another route
   server, the most recent CONFIGURATION message for the domain in
   question.

   When a domain is partitioned, each domain component has its own AD
   representative, which generates routing information messages on
   behalf of that component.  Discovery of a domain partition prompts
   the AD representative for each domain component to generate and
   distribute a DYNAMIC message.  In this case, a route server receives
   and stores more than one routing information message at a time for
   the given domain, namely one for each domain component.

   When the partition heals, the AD representative for the entire domain
   generates and distributes a DYNAMIC message.  In each route server's
   routing information database, the new DYNAMIC message does not
   automatically replace all of the currently-stored DYNAMIC messages
   for the given domain.  Instead, the new message only replaces that
   message whose AD representative matches the AD representative for the
   new message.  The other DYNAMIC messages, generated during the period
   over which the partition occurred, remain in the routing information
   database until they attain their maximum lifetime, as described in
   section 4.2.5 below.  Such stale information may lead to the
   generation of routes that result in path setup failures and hence the



Steenstrup                                                     [Page 55]

RFC 1479                     IDPR Protocol                     July 1993


   selection of alternative routes.  To reduce the chances of path setup
   failures, we will investigate, for a future version of IDPR,
   mechanisms for removing partition-related DYNAMIC messages
   immediately after a partition disappears.

4.2.5.  Routing Information Database

   We expect that most of the IDPR routing information stored in a
   routing information database will remain viable for long periods of
   time, perhaps until a domain reconfiguration occurs.  By "viable", we
   mean that the information reflects the current state of the domain
   and hence may be used successfully for generating policy routes.  To
   reduce the probability of retaining stale routing information, a
   route server imposes a maximum lifetime on each database entry,
   initialized when it incorporates an accepted entry into its routing
   information database.  The maximum lifetime should be longer than the
   corresponding message generation period, so that the database entry
   is likely to be refreshed before it attains its maximum lifetime.

   Each CONFIGURATION message stored in the routing information database
   has a maximum lifetime of conf_old (530) hours; each DYNAMIC message
   stored in the routing information database has a maximum lifetime of
   dyn_old (25) hours.  Periodic generation of routing information
   messages makes it unlikely that any routing information message will
   remain in a routing information database for its full lifetime.
   However, a routing information message may attain its maximum
   lifetime in a route server that is separated from a internetwork for
   a long period of time.

   When an IDPR routing information message attains its maximum lifetime
   in a routing information database, the route server removes the
   message contents from its database, so that it will not generate new
   routes with the outdated routing information nor distribute old
   routing information in response to requests from other route servers
   or policy gateways.  Nevertheless, the route server continues to
   dispense routes previously generated with the old routing
   information, as long as path setup (see section 7) for these routes
   succeeds.

   The route server treats routing information message lifetime
   expiration differently, depending on the type of routing information
   message.  When a CONFIGURATION message expires, the route server
   requests, from another route server, the most recent CONFIGURATION
   message issued for the given domain.  When a DYNAMIC message expires,
   the route server does not initially attempt to obtain more recent
   routing information.  Instead, if route generation is necessary, the
   route server uses the routing information contained in the
   corresponding CONFIGURATION message for the given domain.  Only if



Steenstrup                                                     [Page 56]

RFC 1479                     IDPR Protocol                     July 1993


   there is a path setup failure (see section 7.4) involving the given
   domain does the route server request, from another route server, the
   most recent DYNAMIC message issued for the given domain.

4.3.  Routing Information Message Formats

   The flooding protocol number is equal to 1.  We describe the contents
   of each type of routing information message below.

4.3.1.  CONFIGURATION

   The CONFIGURATION message type is equal to 0.

    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |            AD CMP             |              SEQ              |
   +-------------------------------+-------------------------------+
   |            NUM TP             |            NUM RS             |
   +-------------------------------+-------------------------------+
   |              RS               |
   +-------------------------------+
   For each transit policy configured for the domain:
   +-------------------------------+-------------------------------+
   |              TP               |            NUM ATR            |
   +-------------------------------+-------------------------------+
   For each attribute of the transit policy:
   +-------------------------------+-------------------------------+
   |            ATR TYP            |            ATR LEN            |
   +-------------------------------+-------------------------------+
   For the source/destination access restrictions attribute:
   +-------------------------------+
   |          NUM AD GRP           |
   +-------------------------------+
   For each domain group in the source/destination access restrictions:
   +-------------------------------+-------------------------------+
   |            NUM AD             |              AD               |
   +---------------+---------------+-------------------------------+
   |    AD FLGS    |    NUM HST    |            HST SET            |
   +---------------+---------------+-------------------------------+
   For the temporal access restrictions attribute:
   +-------------------------------+
   |            NUM TIM            |
   +-------------------------------+







Steenstrup                                                     [Page 57]

RFC 1479                     IDPR Protocol                     July 1993


   For each set of times in the temporal access restrictions:
   +---------------+-----------------------------------------------+
   |   TIM FLGS    |                   DURATION                    |
   +---------------+-----------------------------------------------+
   |                             START                             |
   +-------------------------------+-------------------------------+
   |            PERIOD             |            ACTIVE             |
   +-------------------------------+-------------------------------+
   For the user class access restrictions attribute:
   +-------------------------------+
   |            NUM UCI            |
   +-------------------------------+
   For each UCI in the user class access restrictions:
   +---------------+
   |      UCI      |
   +---------------+
   For each offered service attribute:
   +---------------------------------------------------------------+
   |                            OFR SRV                            |
   +---------------------------------------------------------------+
   For the virtual gateway access restrictions attribute:
   +-------------------------------+
   |           NUM VG GRP          |
   +-------------------------------+
   For each virtual gateway group in the virtual gateway access
   restrictions:
   +-------------------------------+-------------------------------+
   |            NUM VG             |            ADJ AD             |
   +---------------+---------------+-------------------------------+
   |      VG       |    VG FLGS    |
   +---------------+---------------+

   AD CMP
        (16 bits) Numeric identifier for the domain component containing
        the AD representative policy gateway.

   SEQ (16 bits) Routing information message sequence number.

   NUM TP (16 bits) Number of transit policy specifications contained in
        the routing information message.

   NUM RS (16 bits) Number of route servers advertised to serve clients
        outside of the domain.

   RS (16 bits) Numeric identifier for a route server.

   TP (16 bits) Numeric identifier for a transit policy specification.




Steenstrup                                                     [Page 58]

RFC 1479                     IDPR Protocol                     July 1993


   NUM ATR (16 bits) Number of attributes associated with the transit
        policy.

   ATR TYP (16 bits) Numeric identifier for a type of attribute.  Valid
        attributes include the following types:

   - Set of  virtual  gateway access restrictions   (see  section 1.4.2)
     associated with the transit policy (variable).  This attribute must
     be included.

   - Set of source/destination access restrictions (see section 1.4.2)
     associated with the transit policy (variable).  This attribute may
     be omitted.  Absence of this attribute implies that traffic from
     any source to any destination is acceptable.

   - Set of temporal access restrictions (see section 1.4.2) associated
     with the transit policy (variable).  This attribute may be omitted.
     Absence of this attribute implies that the transit policy applies
     at all times.

   - Set of user class access restrictions (see section 1.4.2)
     associated with the transit policy (variable).  This attribute may
     be omitted.  Absence of this attribute implies that traffic from
     any user class is acceptable.

   - Average delay in milliseconds (16 bits).  This attribute may be
     omitted.

   - Delay variation in milliseconds (16 bits).  This attribute may be
     omitted.

   - Average available bandwidth in bits per second (48 bits).  This
     attribute may be omitted.

   - Available bandwidth variation in bits per second (48 bits).  This
     attribute may be omitted.

   - MTU in bytes (16 bits).  This attribute may be omitted.

   - Charge per byte in thousandths of a cent (16 bits). This attribute
     may be omitted.

   - Charge per message in thousandths of a cent (16 bits).  This
     attribute may be omitted.

   - Charge for session time in thousandths of a cent per second (16
     bits).  This attribute may be omitted.  Absence of any charge
     attribute implies that the domain provides free transit service.



Steenstrup                                                     [Page 59]

RFC 1479                     IDPR Protocol                     July 1993


   ATR LEN (16 bits) Length of an attribute in bytes, beginning with the
   subsequent field.

   NUM AD GRP (16 bits) Number of source/destination domain groups (see
   section 1.4.2) associated with the source/destination access
   restrictions.

   NUM AD (16 bits) Number of domains or sets of domains in a domain
   group.

   AD (16 bits) Numeric identifier for a domain or domain set.

   AD FLGS (8 bits) Set of five flags indicating how to interpret the AD
   field, contained in the right-most bits.  Proceeding left to right,
   the first flag indicates whether the transit policy applies to all
   domains or to specific domains (1 all, 0 specific), and when set to
   1, causes the second and third flags to be ignored.  The second flag
   indicates whether the domain identifier signifies a single domain or
   a domain set (1 single, 0 set).  The third flag indicates whether the
   transit policy applies to the given domain or domain set (1 applies,
   0 does not apply) and is used for representing complements of sets of
   domains.  The fourth flag indicates whether the domain is a source (1
   source, 0 not source).  The fifth flag indicates whether the domain
   is a destination (1 destination, 0 not destination).  At least one of
   the fourth and fifth flags must be set to 1.

   NUM HST (8 bits) Number of "host sets" (see section 1.4.2) associated
   with a particular domain or domain set.  The value 0 indicates that
   all hosts in the given domain or domain set are acceptable sources or
   destinations, as specified by the fourth and fifth AD flags.

   HST SET (16 bits) Numeric identifier for a host set.

   NUM TIM (16 bits) Number of time specifications associated with the
   temporal access restrictions.  Each time specification is split into
   a set of continguous identical periods, as we describe below.

   TIM FLGS (8 bits) Set of two flags indicating how to combine the time
   specifications, contained in the right-most bits.  Proceeding left to
   right, the first flag indicates whether the transit policy applies
   during the periods specified in the time specification (1 applies, 0
   does not apply) and is used for representing complements of policy
   applicability intervals.  The second flag indicates whether the time
   specification takes precedence over the previous time specifications
   listed (1 precedence, 0 no precedence).  Precedence is equivalent to
   the boolean OR and AND operators, in the following sense.  At any
   given instant, a transit policy either applies or does not apply,
   according to a given time specification, and we can assign a boolean



Steenstrup                                                     [Page 60]

RFC 1479                     IDPR Protocol                     July 1993


   value to the state of policy applicability according to a given time
   specification.  If the second flag assumes the value 1 for a given
   time specification, that indicates the boolean operator OR should be
   applied to the values of policy applicability, according to the given
   time specification and to all previously listed time specifications.
   If the second flag assumes the value 0 for a given time
   specification, that indicates the boolean operator AND should be
   applied to the values of policy applicability, according to the given
   time specification and to all previously listed time specifications.

   DURATION (24 bits) Length of the time specification duration, in
   minutes.  A value of 0 indicates an infinite duration.

   START (32 bits) Time at which the time specification first takes
   effect, in seconds elapsed since 1 January 1970 0:00 GMT.

   PERIOD (16 bits) Length of each time period within the time
   specification, in minutes.

   ACTIVE (16 bits) Length of the policy applicable interval during each
   time period, in minutes from the beginning of the time period.

   NUM UCI (16 bits) Number of user classes associated with the user
   class access restrictions.

   UCI (8 bits) Numeric identifier for a user class.

   NUM VG GRP (16 bits) Number of virtual gateway groups (see section
   1.4.2) associated with the virtual gateway access restrictions.

   NUM VG (16 bits) Number of virtual gateways in a virtual gateway
   group.

   ADJ AD (16 bits) Numeric identifier for the adjacent domain to which
   a virtual gateway connects.

   VG (8 bits) Numeric identifier for a virtual gateway.

   VG FLGS (8 bits) Set of two flags indicating how to interpret the VG
   field, contained in the right-most bits.  Proceeding left to right,
   the first flag indicates whether the virtual gateway is a domain
   entry point (1 entry, 0 not entry).  The second flag indicates
   whether the virtual gateway is a domain exit point (1 exit, 0 not
   exit).  At least one of the first and second flags must be set to 1.







Steenstrup                                                     [Page 61]

RFC 1479                     IDPR Protocol                     July 1993


4.3.2.  DYNAMIC

   The DYNAMIC message type is equal to 1.

    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |            AD CMP             |              SEQ              |
   +-------------------------------+-------------------------------+
   |           UNAVL VG            |            NUM PS             |
   +-------------------------------+-------------------------------+
   For each unavailable virtual gateway in the domain:
   +-------------------------------+---------------+---------------+
   |            ADJ AD             |      VG       |    UNUSED     |
   +-------------------------------+---------------+---------------+
   For each set of transit policies for the domain:
   +-------------------------------+-------------------------------+
   |            NUM TP             |          NUM VG GRP           |
   +-------------------------------+-------------------------------+
   |              TP               |
   +-------------------------------+
   For each virtual gateway group associated with the transit policy
   set:
   +-------------------------------+-------------------------------+
   |            NUM VG             |            ADJ AD             |
   +---------------+---------------+-------------------------------+
   |      VG       |    VG FLGS    |            NUM CMP            |
   +---------------+---------------+-------------------------------+
   |            ADJ CMP            |
   +-------------------------------+

   AD CMP
        (16 bits) Numeric identifier for the domain component containing
        the AD representative policy gateway.

   SEQ (16 bits) Routing information message sequence number.

   UNAVL VG (16 bits) Number of virtual gateways in the domain component
        that are currently unavailable via any intra-domain routes.

   NUM PS (16 bits) Number of sets of transit policies listed.  Transit
        policy sets provide a mechanism for reducing the size of DYNAMIC
        messages.  A single set of virtual gateway groups applies to all
        transit policies in a given set.

   ADJ AD (16 bits) Numeric identifier for the adjacent domain to which
        a virtual gateway connects.




Steenstrup                                                     [Page 62]

RFC 1479                     IDPR Protocol                     July 1993


   VG (8 bits) Numeric identifier for a virtual gateway.

   UNUSED (8 bits) Not currently used; must be set equal to 0.

   NUM TP (16 bits) Number of transit policies in a set.

   NUM VGGRP (16 bits) Number of virtual gateway groups currently
        associated with the transit policy set.

   TP (16 bits) Numeric identifier for a transit policy.

   NUM VG (16 bits) Number of virtual gateways in a virtual gateway
        group.

   VG FLGS (8 bits) Set of two flags indicating how to interpret the VG
        field, contained in the right-most bits.  Proceeding left to
        right, the first flag indicates whether the virtual gateway is a
        domain entry point (1 entry, 0 not entry).  The second flag
        indicates whether the virtual gateway is a domain exit point (1
        exit, 0 not exit).  At least one of the first and second flags
        must be set to 1.

   NUM CMP (16 bits) Number of adjacent domain components reachable via
        direct connections through the virtual gateway.

   ADJ CMP (16 bits) Numeric identifier for a reachable adjacent domain
        component.

4.3.3.  Negative Acknowledgements

   When a policy gateway or route server receives an unacceptable IDPR
   routing information message that passes the CMTP validation checks,
   it includes, in its CMTP ACK, an appropriate negative
   acknowledgement.  This information is placed in the INFORM field of
   the CMTP ACK (described previously in section 2.4); the numeric
   identifier for each type of routing information message negative
   acknowledgement is contained in the left-most 8 bits of the INFORM
   field.  Negative acknowledgements associated with routing information
   messages include the following types:

   1.  Unrecognized IDPR routing information message type.  Numeric
       identifier for the unrecognized message type (8 bits).

   2.  Out-of-date IDPR routing information message.  This is a signal
       to the sender that it may not have the most recent routing
       information for the given domain.





Steenstrup                                                     [Page 63]

RFC 1479                     IDPR Protocol                     July 1993


5.  Route Server Query Protocol

   Each route server is responsible for maintaining both the routing
   information database and the route database and for responding to
   database information requests from policy gateways and other route
   servers.  These requests and their responses are the messages
   exchanged via the Route Server Query Protocol (RSQP).

   Policy gateways and route servers normally invoke RSQP to replace
   absent, outdated, or corrupted information in their own routing
   information or route databases.  In section 4, we discussed some of
   the situations in which RSQP may be invoked; in this section and in
   section 7, we discuss other such situations.

5.1.  Message Exchange

   Policy gateways and route servers use CMTP for reliable transport of
   route server requests and responses.  RSQP must communicate to CMTP
   the maximum number of transmissions per request/response message,
   rsqp_ret, and the interval between request/response message
   retransmissions, rsqp_int microseconds.  A route server
   request/response message is "acceptable" if:

   - It passes the CMTP validation checks.

   - Its timestamp is less than rsqp_old (300) seconds behind the
     recipient's internal clock time.

   With RSQP, a requesting entity expects to receive an acknowledgement
   from the queried route server indicating whether the route server can
   accommodate the request.  The route server may fail to fill a given
   request for either of the following reasons:

   - Its corresponding database contains no entry or only a partial
     entry for the requested information.

   - It is governed by special message distribution rules, imposed by
     the domain administrator, that preclude it from releasing the
     requested information.  Currently, such distribution rules are not
     included in IDPR configuration information.

   For all requests that it cannot fill, the route server responds with
   a negative acknowledgement message carried in a CMTP acknowledgement,
   indicating the set of unfulfilled requests (see section 5.5.4).

   If the requesting entity either receives a negative acknowledgement
   or does not receive any acknowledgement after rsqp_ret attempts
   directed at the same route server, it queries a different route



Steenstrup                                                     [Page 64]

RFC 1479                     IDPR Protocol                     July 1993


   server, as long as the number of attempted requests to different
   route servers does not exceed rsqp_try (3).  Specifically, the
   requesting entity proceeds in round-robin order through its list of
   addressable route servers.  However, if the requesting entity is
   unsuccessful after rsqp_try attempts, it abandons the request
   altogether and logs the event for network management.

   A policy gateway or a route server can request information from any
   route server that it can address.  Addresses for local route servers
   within a domain are part of the configuration for each IDPR entity
   within a domain; addresses for remote route servers in other domains
   are obtained through flooded CONFIGURATION messages, as described
   previously in section 4.2.1.  However, requesting entities always
   query local route servers before remote route servers, in order to
   contain the costs associated with the query and response.  If the
   requesting entity and the queried route server are in the same
   domain, they can communicate over intra-domain routes, whereas if the
   requesting entity and the queried route server are in different
   domains, they must obtain a policy route and establish a path before
   they can communicate, as we describe below.

5.2.  Remote Route Server Communication

   RSQP communication involving a remote route server requires a policy
   route and accompanying path setup (see section 7) between the
   requesting and queried entities, as these entities reside in
   different domains.  After generating a request message, the
   requesting entity hands to CMTP its request message along with the
   remote route server's entity and domain identifiers.  CMTP encloses
   the request in a DATAGRAM and hands the DATAGRAM and remote route
   server information to the path agent.  Using the remote route server
   information, the path agent obtains, and if necessary sets up, a path
   to the remote route server.  Once the path to the remote route server
   has been successfully established, the path agent encapsulates the
   DATAGRAM within an IDPR data message and forwards the data message
   along the designated path.

   When the path agent in the remote route server receives the IDPR data
   message, it extracts the DATAGRAM and hands it to CMTP.  In addition,
   the path agent, using the requesting entity and domain identifiers
   contained in the path identifier, obtains, and if necessary sets up,
   a path back to the requesting entity.

   If the DATAGRAM fails any of the CMTP validation checks, CMTP returns
   a NAK to the requesting entity.  If the DATAGRAM passes all of the
   CMTP validation checks, the remote route server assesses the
   acceptability of the request message.  Provided the request message
   is acceptable, the remote route server determines whether it can



Steenstrup                                                     [Page 65]

RFC 1479                     IDPR Protocol                     July 1993


   fulfill the request and directs CMTP to return an ACK to the
   requesting entity.  The ACK may contain a negative acknowledgement if
   the entire request cannot be fulfilled.

   The remote route server generates responses for all requests that it
   can fulfill and returns the responses to the requesting entity.
   Specifically, the remote route server hands to CMTP its response and
   the requesting entity information.  CMTP in turn encloses the
   response in a DATAGRAM.

   When returning an ACK, a NAK, or a response to the requesting entity,
   the remote route server hands the corresponding CMTP message and
   requesting entity information to the path agent.  Using the
   requesting entity information, the path agent retrieves the path to
   the requesting entity, encapsulates the CMTP message within an IDPR
   data message, and forwards the data message along the designated
   path.

   When the path agent in the requesting entity receives the IDPR data
   message, it extracts the ACK, NAK, or response to its request and
   performs the CMTP validation checks for that message.  In the case of
   a response messsage, the requesting entity also assesses message
   acceptability before incorporating the contents into the appropriate
   database.

5.3  Routing Information

   Policy gateways and route servers request routing information from
   route servers, in order to update their routing information
   databases.  To obtain routing information from a route server, the
   requesting entity issues a ROUTING INFORMATION REQUEST message
   containing the type of routing information requested - CONFIGURATION
   messages, DYNAMIC messages, or both - and the set of domains from
   which the routing information is requested.

   Upon receiving a ROUTING INFORMATION REQUEST message, a route server
   first assesses message acceptability before proceeding to act on the
   contents.  If the ROUTING INFORMATION REQUEST message is deemed
   acceptable, the route server determines how much of the request it
   can fulfill and then instructs CMTP to generate an acknowledgement,
   indicating its ability to fulfill the request.  The route server
   proceeds to fulfill as much of the request as possible by
   reconstructing individual routing information messages, one per
   requested message type and domain, from its routing information
   database.  We note that only a regenerated routing information
   message whose entire contents match that of the original routing
   information message may pass the CMTP integrity/authentication
   checks.



Steenstrup                                                     [Page 66]

RFC 1479                     IDPR Protocol                     July 1993


5.4.  Routes

   Path agents request routes from route servers when they require
   policy routes for path setup.  To obtain routes from a route server,
   the requesting path agent issues a ROUTE REQUEST message containing
   the destination domain and applicable service requirements, the
   maximum number of routes requested, a directive indicating whether to
   generate the routes or retrieve them from the route database, and a
   directive indicating whether to refresh the routing information
   database with the most recent CONFIGURATION or DYNAMIC message from a
   given domain, before generating the routes.  To refresh its routing
   information database, a route server must obtain routing information
   from another route server.  The path agent usually issues routing
   information database refresh directives in response to a failed path
   setup.  We discuss the application of these directives in more detail
   in section 7.4.

   Upon receiving a ROUTE REQUEST message, a route server first assesses
   message acceptability before proceeding to act on the contents.  If
   the ROUTE REQUEST message is deemed acceptable, the route server
   determines whether it can fulfill the request and then instructs CMTP
   to generate an acknowledgement, indicating its ability to fulfill the
   request.  The route server proceeds to fulfill the request with
   policy routes, either retrieved from its route database or generated
   from its routing information database if necessary, and returns these
   routes in a ROUTE RESPONSE message.

5.5.  Route Server Message Formats

   The route server query protocol number is equal to 2.  We describe
   the contents of each type of RSQP message below.

5.5.1.  ROUTING INFORMATION REQUEST

   The ROUTING INFORMATION REQUEST message type is equal to 0.

    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |            QRY AD             |            QRY RS             |
   +-------------------------------+-------------------------------+
   |            NUM AD             |              AD               |
   +---------------+---------------+-------------------------------+
   |   RIM FLGS    |    UNUSED     |
   +---------------+---------------+

   QRY AD
        (16 bits) Numeric identifier for the domain containing the



Steenstrup                                                     [Page 67]

RFC 1479                     IDPR Protocol                     July 1993


        queried route server.

   QRY RS (16 bits) Numeric identifier for the queried route server.

   NUM AD (16 bits) Number of domains about which routing information is
        requested.  The value 0 indicates a request for routing
        information from all domains.

   AD (16 bits) Numeric identifier for a domain.  This field is absent
        when NUM AD equals 0.

   RIM FLGS (8 bits) Set of two flags indicating the type of routing
        information messages requested, contained in the right-most
        bits.  Proceeding left to right, the first flag indicates
        whether the request is for a CONFIGURATION message (1
        CONFIGURATION, 0 no CONFIGURATION).  The second flag indicates
        whether the request is for a DYNAMIC message (1 DYNAMIC, 0 no
        DYNAMIC).  At least one of the first and second flags must be
        set to 1.

   UNUSED (8 bits) Not currently used; must be set equal to 0.

5.5.2.  ROUTE REQUEST

        The ROUTE REQUEST message type is equal to 1.

    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |            QRY AD             |            QRY RS             |
   +-------------------------------+-------------------------------+
   |            SRC AD             |            HST SET            |
   +---------------+---------------+-------------------------------+
   |      UCI      |    UNUSED     |            NUM RQS            |
   +---------------+---------------+-------------------------------+
   |            DST AD             |            PRX AD             |
   +---------------+---------------+-------------------------------+
   |    NUM RTS    |   GEN FLGS    |            RFS AD             |
   +---------------+---------------+-------------------------------+
   |            NUM AD             |
   +-------------------------------+
   For each domain to be favored, avoided, or excluded:
   +-------------------------------+---------------+---------------+
   |              AD               |    AD FLGS    |    UNUSED     |
   +-------------------------------+---------------+---------------+






Steenstrup                                                     [Page 68]

RFC 1479                     IDPR Protocol                     July 1993


   For each requested service:
   +-------------------------------+-------------------------------+
   |            RQS TYP            |            RQS LEN            |
   +-------------------------------+-------------------------------+
   |                            RQS SRV                            |
   +---------------------------------------------------------------+

   QRY AD
        (16 bits) Numeric identifier for the domain containing the
        queried route server.

   QRY RS (16 bits) Numeric identifier for the queried route server.

   SRC AD (16 bits) Numeric identifier for the route's source domain.

   HST SET (16 bits) Numeric identifier for the source's host set.

   UCI (8 bits) Numeric identifier for the source user class. The value
        0 indicates that there is no particular source user class.

   UNUSED (8 bits) Not currently used; must be set equal to 0.

   NUM RQS (16 bits) Number of requested services.  The value 0
        indicates that the source requests no special services.

   DST AD (16 bits) Numeric identifier for the route's destination
        domain.

   PRX AD (16 bits) Numeric identifier for the destination domain's
        proxy (see section 1.3.1).  If the destination domain provides
        the path agent function for its hosts, then the destination and
        proxy domains are identical.  A route server constructs routes
        between the source domain's proxy and the destination domain's
        proxy.  We note that the source domain's proxy is identical to
        the domain issuing the CMTP message containing the ROUTE REQUEST
        message, and hence available in the CMTP header.

   NUM RTS (8 bits) Number of policy routes requested.

   GEN FLGS (8 bits) Set of three flags indicating how to obtain the
        requested routes, contained in the right-most bits.  Proceeding
        left to right, the first flag indicates whether the route server
        should retrieve existing routes from its route database or
        generate new routes (1 retrieve, 0 generate).  The second flag
        indicates whether the route server should refresh its routing
        information database before generating the requested routes (1
        refresh, 0 no refresh) and when set to 1, causes the third flag
        and the RFS AD field to become significant.  The third flag



Steenstrup                                                     [Page 69]

RFC 1479                     IDPR Protocol                     July 1993


        indicates whether the routing information database refresh
        should include CONFIGURATION messages or DYNAMIC messages (1
        configuration, 0 dynamic).

   RFS AD (16 bits) Numeric identifier for the domain for which routing
        information should be refreshed.  This field is meaningful only
        if the second flag in the GEN FLGS field is set to 1.

   NUM AD (16 bits) Number of transit domains that are to be favored,
        avoided, or excluded during route selection (see section 1.4.1).

   AD (16 bits) Numeric identifier for a transit domain to be favored,
        avoided, or excluded.

   AD FLGS (8 bits) Three flags indicating how to interpret the AD
        field, contained in the right-most bits.  Proceeding left to
        right, the first flag indicates whether the domain should be
        favored (1 favored, 0 not favored).  The second flag indicates
        whether the domain should be avoided (1 avoided, 0 not avoided).
        The third flag indicates whether the domain should be excluded
        (1 excluded, 0 not excluded).  No more than one of the first,
        second, and third flags must set to 1.

   RQS TYP (16 bits) Numeric identifier for a type of requested service.
        Valid requested services include the following types:

   1.  Upper bound on delay, in milliseconds (16 bits).  This attribute
       may be omitted.

   2.  Minimum delay route.  This attribute may be omitted.

   3.  Upper bound on delay variation, in milliseconds (16 bits).  This
       attribute may be omitted.

   4.  Minimum delay variation route.  This attribute may be omitted.

   5.  Lower bound on bandwidth, in bits per second (48 bits).  This
       attribute may be omitted.

   6.  Maximum bandwidth route.  This attribute may be omitted.

   7.  Upper bound on monetary cost, in cents (32 bits).  This attribute
       may be omitted.

   8.  Minimum monetary cost route.  This attribute may be omitted.

   9.  Path lifetime in minutes (16 bits). This attribute may be omitted
       but must be present if types 7 or 8 are present. Route servers



Steenstrup                                                     [Page 70]

RFC 1479                     IDPR Protocol                     July 1993


       use path lifetime information together with domain charging
       method to compute expected session monetary cost over a given
       domain.

   10. Path lifetime in messages (16 bits).  This attribute may be
       omitted but must be present if types 7 or 8 are present.

   11. Path lifetime in bytes (48 bits).  This attribute may be omitted
       but must be present if types 7 or 8 are present.

   RQS LEN
        (16 bits) Length of the requested service, in bytes, beginning
        with the next field.

   RQS SRV
        (variable) Description of the requested service.

5.5.3.  ROUTE RESPONSE

   The ROUTE RESPONSE message type is equal to 2.

    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |    NUM RTS    |
   +---------------+
   For each route provided:
   +---------------+---------------+
   |    NUM AD     |   RTE FLGS    |
   +---------------+---------------+
   For each domain in the route:
   +---------------+---------------+-------------------------------+
   |    AD LEN     |      VG       |            ADJ AD             |
   +---------------+---------------+-------------------------------+
   |            ADJ CMP            |            NUM TP             |
   +-------------------------------+-------------------------------+
   |              TP               |
   +-------------------------------+

   NUM RTS
        (16 bits) Number of policy routes provided.

   RTE FLGS (8 bits) Set of two flags indicating the directions in which
        a route can be used, contained in the right-most bits.  Refer to
        sections 6.2, 7, and 7.2 for detailed discussions of path
        directionality.  Proceeding left to right, the first flag
        indicates whether the route can be used from source to
        destination (1 from source, 0 not from source).  The second flag



Steenstrup                                                     [Page 71]

RFC 1479                     IDPR Protocol                     July 1993


        indicates whether the route can be used from destination to
        source (1 from destination, 0 not from destination).  At least
        one of the first and second flags must be set to 1, if NUM RTS
        is greater than 0.

   NUM AD (8 bits) Number of domains in the policy route, not including
        the first domain on the route.

   AD LEN (8 bits) Length of the information associated with a
        particular domain, in bytes, beginning with the next field.


   VG (8 bits) Numeric identifier for an exit virtual gateway.

   ADJ AD (16 bits) Numeric identifier for the adjacent domain connected
        to the virtual gateway.

   ADJ CMP (16 bits) Numeric identifier for the adjacent domain
        component.  Used by policy gateways to select a route across a
        virtual gateway connecting to a partitioned domain.

   NUM TP (16 bits) Number of transit policies that apply to the section
        of the route traversing the domain component.

   TP (16 bits) Numeric identifier for a transit policy.

5.5.4.  Negative Acknowledgements

   When a policy gateway receives an unacceptable RSQP message that
   passes the CMTP validation checks, it includes, in its CMTP ACK, an
   appropriate negative acknowledgement.  This information is placed in
   the INFORM field of the CMTP ACK (described previously in section
   2.4); the numeric identifier for each type of RSQP negative
   acknowledgement is contained in the left-most 8 bits of the INFORM
   field.  Negative acknowledgements associated with RSQP include the
   following types:

   1.  Unrecognized RSQP message type.  Numeric identifier for the
       unrecognized message type (8 bits).

   2.  Out-of-date RSQP message.

   3.  Unable to fill requests for routing information from the
       following domains.  Number of domains for which requests cannot
       be filled (16 bits); a value of 0 indicates that the route
       server cannot fill any of the requests.  Numeric identifier for
       each domain for which a request cannot be filled (16 bits).




Steenstrup                                                     [Page 72]

RFC 1479                     IDPR Protocol                     July 1993


   4.  Unable to fill requests for routes to the following destination
       domain.  Numeric identifier for the destination domain (16 bits).

6.  Route Generation

   Route generation is the most computationally complex part of IDPR,
   because of the number of domains and the number and heterogeneity of
   policies that it must accommodate.  Route servers must generate
   policy routes that satisfy the requested services of the source
   domains and respect the offered services of the transit domains.

   We distinguish requested qualities of service and route generation
   with respect to them as follows:

  - Requested service limits include upper bounds on route delay, route
    delay variation, and session monetary cost and lower bounds on
    available route bandwidth.  Generating a route that must satisfy
    more than one quality of service constraint, for example route delay
    of no more than X seconds and available route bandwidth of no less
    than Y bits per second, is an NP-complete problem.

  - Optimal requested  services  include  minimum  route delay, minimum
    route delay variation, minimum session monetary cost, and maximum
    available route bandwidth.  In the worst case, the computational
    complexity of generating a route that is optimal with respect to a
    given requested service is O((N + L) log N) for Dijkstra's shortest
    path first (SPF) search and O(N + (L * L)) for breadth-first (BF)
    search, where N is the number of nodes and L is the number of links
    in the search graph.  Multi-criteria optimization, for example
    finding a route with minimal delay variation and minimal session
    monetary cost, may be defined in several ways.  One approach to
    multi-criteria optimization is to assign each link a single value
    equal to a weighted sum of the values of the individual offered
    qualities of service and generate a route that is optimal with
    respect to this new criterion.  However, selecting the weights that
    yield the desired route generation behavior is itself an
    optimization procedure and hence not trivial.

To help contain the combinatorial explosion of processing and memory
costs associated with route generation, we supply the following
guidelines for generation of suitable policy routes:

  - Each route server should only generate policy routes from the
    perspective of its own domain as source; it need not generate policy
    routes for arbitrary source/destination domain pairs.  Thus, we can
    distribute the computational burden over all route servers.

  - Route servers should precompute routes for which they anticipate



Steenstrup                                                     [Page 73]

RFC 1479                     IDPR Protocol                     July 1993


    requests and should generate routes on demand only in order to
    satisfy unanticipated route requests.  Hence, a single route server
    can distribute its computational burden over time.

  - Route servers should cache the results of route generation, in order
    to minimize the computation associated with responding to future
    route requests.

  - To handle requested service limits, a route server should always
    select the first route generated that satisfies all of the requested
    service limits.

  - To handle multi-criteria optimization in route selection, a route
    server should generate routes that are optimal with respect to the
    first optimal requested service listed in the ROUTE REQUEST message.
    The route server should resolve ties between otherwise equivalent
    routes by evaluating these routes according to the other optimal
    requested services contained in the ROUTE REQUEST message, in the
    order in which they are listed.  With respect to the route server's
    routing information database, the selected route is optimal
    according to the first optimal requested service listed in the ROUTE
    REQUEST message but is not necessarily optimal according to any
    other optimal requested service listed in the ROUTE REQUEST message.

    ti 2 - To handle a mixture of requested service limits and optimal
    requested services, a route server should generate routes that
    satisfy all of the requested service limits.  The route server
    should resolve ties between otherwise equivalent routes by
    evaluating these routes as described in the multi-criteria
    optimization case above.

    ti 2 - All else being equal, a route server should always prefer
    minimum-hop routes, because they minimize the amount of network
    resources consumed by the routes.

    ti 2 - A route server should generate at least one route to each
    component of a partitioned destination domain, because it may not
    know in which domain component the destination host resides.  Hence,
    a route server can maximize the chances of providing a feasible
    route to a destination within a partitioned domain.

6.1  Searching

    All domains need not execute the identical route generation
    procedure.  Each domain administrator is free to specify the IDPR
    route generation procedure for route servers in its own domain,
    making the procedure as simple or as complex as desired.




Steenstrup                                                     [Page 74]

RFC 1479                     IDPR Protocol                     July 1993


    We offer an IDPR route generation procedure as a model.  With slight
    modification, this procedure can be made to search in either BF or
    SPF order.  The procedure can be used either to generate a single
    policy route from the source to a specified destination domain or to
    generate a set of policy routes from the source domain to all
    destination domains.  If the source or destination domain has a
    proxy, then the source or destination endpoint of the policy route
    is a proxy domain and not the actual source or destination domain.

    For high-bandwidth traffic flows, BF search is the recommended
    search technique, because it produces minimum-hop routes.  For low-
    bandwidth traffic flows, the route server may use either BF search
    or SPF search.  The computational complexity of BF search is O(N +
    L) and hence it is the search procedure of choice, except when
    generating routes with optimal requested services.  We recommend
    using SPF search only for optimal requested services and never in
    response to a request for a maximum bandwidth route.

6.1.1.  Implementation

   Data Structures:

   The routing information database contains the graph of an
   internetwork, in which virtual gateways are the nodes and intra-
   domain routes between virtual gateways are the links.  During route
   generation, each route is represented as a sequence of virtual
   gateways, domains, and relevant transit policies, together with a
   list of route characteristics, stored in a temporary array and
   indexed by destination domain.

   - Execute the Policy Consistency routine, first with the source
     domain the given domain and second with the destination domain as
     the given domain.  If any policy inconsistency precludes the
     requested traffic flow, go to Exit.

   - For each domain, initialize a null route, set the route bandwidth
     to and set the following route characteristics to infinity: route
     delay, route delay variation, session monetary cost, and route
     length in hops.

   - With each operational virtual gateway in the source or source proxy
     domain, associate the initial route characteristics.

   - Initialize a next-node data structure which will contain, for each
     route in progress, the virtual gateway at the current endpoint of
     the route together with the associated route characteristics.  The
     next-node data structure determines the order in which routes get
     expanded.



Steenstrup                                                     [Page 75]

RFC 1479                     IDPR Protocol                     July 1993


        BF:  A fifo queue.

        SPF: A heap, ordered according to the first optimal requested
             service listed in the ROUTE REQUEST message.

   Remove Next Node: These steps are performed for each virtual gateway
        in the next-node data structure.

      - If there are no more virtual gateways in the next-node data
        structure, go to Exit.

      - Extract a virtual gateway and its associated route
        characteristics from the next-node data structure, obtain the
        adjacent domain, and:

             SPF: Remake the heap.

      - If there is a specific destination domain and if for the primary
        optimal service:

             BF:  Route length in hops.

             SPF: First optimal requested service listed in the ROUTE
             REQUEST message.

        the extracted virtual gateway's associated route characteristic
        is no better than that of the destination domain, go to Remove
        Next Node.

      - Execute the Policy Consistency routine with the adjacent domain
        as given domain.  If any policy inconsistency precludes the
        requested traffic flow, go to Remove Next Node.

      - Check that the source domain's transit policies do not preclude
        traffic generated by members of the source host set with the
        specified user class and requested services, from flowing to the
        adjacent domain as destination.  This check is necessary because
        the route server caches what it considers to be all feasible
        routes, to intermediate destination domains, generated during
        the computation of the requested route.  If there are no policy
        inconsistencies, associate the route and its characteristics
        with the adjacent domain as destination.

      - If there is a specific destination domain and if the adjacent
        domain is the destination or destination proxy domain, go to
        Remove Next Node.

      - Record the set of all exit virtual gateways in the adjacent



Steenstrup                                                     [Page 76]

RFC 1479                     IDPR Protocol                     July 1993


        domain which the adjacent domain's transit policies permit the
        requested traffic flow and which are currently reachable from
        the entry virtual gateway.

   Next Node:

        These steps are performed for all exit virtual gateways in the
        above set.

      - If there are no exit virtual gateways in the set, go to Remove
        Next Node.

      - Compute the characteristics for the route to the exit virtual
        gateway, and check that all of the route characteristics are
        within the requested service limits.  If any of the route
        characteristics are outside of these limits, go to Next Node.

      - Compare these route characteristics with those already
        associated with the exit virtual gateway (there may be none, if
        this is the first time the exit virtual gateway has been visited
        in the search), according to the primary optimal service.

      - Select the route with the optimal value of the primary optimal
        service, resolve ties by considering optimality according to any
        other optimal requested services in the order in which they are
        listed in the ROUTE REQUEST message, and associate the selected
        route and its characteristics with the exit virtual gateway.

      - Add the virtual gateway to the next-node structure:

             BF:  Add to the end of the fifo queue.

             SPF: Add to the heap.

             and go to Next Node.

   Exit:
        Return a response to the route request, consisting of either a
        set of candidate policy routes or an indication that the route
        request cannot be fulfilled.

   Policy Consistency: Check policy consistency for the given domain.

      - Check that the given domain is not specified as an excluded
        domain in the route request.

      - Check that the given domain's transit policies do not preclude
        traffic generated by members of the source host set with the



Steenstrup                                                     [Page 77]

RFC 1479                     IDPR Protocol                     July 1993


        specified user class and requested services, from flowing to the
        destination domain.

   During the computation of the requested routes, a route server also
   caches what it considers to be all feasible routes to intermediate
   destination domains, thus increasing the chances of being able to
   respond to a future route request without having to generate a new
   route.  The route server does perform some policy consistency checks
   on the routes, as they are generated, to intermediate destinations.
   However, these routes may not in fact be feasible; the transit
   domains contained on the routes may not permit traffic between the
   source and the given intermediate destinations.  Hence, before
   dispensing such a route in response to a route request, a route
   server must check that the transit policies of the constituent
   domains are consistent with the source and destination of the traffic
   flow.

6.2.  Route Directionality

   A path agent may wish to set up a bidirectional path using a route
   supplied by a route server.  (Refer to sections 7.2 and 7.4 for
   detailed discussions of path directionality.)  However, a route
   server can only guarantee that the routes it supplies are feasible if
   used in the direction from source to destination.  The reason is that
   the route server, which resides in the source or source proxy domain,
   does not have access to, and thus cannot account for, the source
   policies of the destination domain.  Nevertheless, the route server
   can provide the path agent with an indication of its assessment of
   route feasibility in the direction from destination to source.

   A necessary but insufficient condition for a route to be feasible in
   the direction from destination to source is as follows.  The route
   must be consistent, in the direction from destination to source, with
   the transit policies of the domains that compose the route.  The
   transit policy consistency checks performed by the route server
   during route generation account for the direction from source to
   destination but not for the direction from destination to source.
   Only after a route server generates a feasible route from source to
   destination does it perform the transit policy consistency checks for
   the route in the direction from destination to source.  Following
   these checks, the route server includes in its ROUTE RESPONSE message
   to the path agent an indication of its assessment of route
   feasibility in each direction.








Steenstrup                                                     [Page 78]

RFC 1479                     IDPR Protocol                     July 1993


6.3.  Route Database

   A policy route, as originally specified by a route server, is an
   ordered list of virtual gateways, domains, and transit policies: VG 1
   - AD 1 - TP 1 - ... - VG n - AD n - TP n. where VG i is the virtual
   gateway that serves as exit from AD i-1 and entry to AD i, and TP i
   is the set of transit policies associated with AD i and relevant to
   the particular route.  Each route is indexed by source and
   destination domain.  Route servers and paths agents store policy
   routes in route databases maintained as caches whose entries must be
   periodically flushed to avoid retention of stale policy routes.  A
   route server's route database is the set of all routes it has
   generated on behalf of its domain as source or source proxy;
   associated with each route in the database are its route
   characteristics.  A path agent's route database is the set of all
   routes it has requested and received from route servers on behalf of
   hosts for which it is configured to act.

   When attempting to locate a feasible route for a traffic flow, a path
   agent first consults its own route database before querying a route
   server.  If the path agent's route database contains one or more
   routes between the given source and destination domains and
   accommodating the given host set and UCI, then the path agent checks
   each such route against the set of excluded domains listed in the
   source policy.  The path agent either selects the first route
   encountered that does not include the excluded domains, or, if no
   such route exists in its route database, requests a route from a
   route server.

   A path agent must query a route server for routes when it is unable
   to fulfill a route request from its own route database.  Moreover, we
   recommend that a path agent automatically forward to a route server,
   all route requests with non-null requested services.  The reason is
   that the path agent retains no route characteristics in its route
   database.  Hence, the path agent cannot determine whether an entry in
   its route database satisfies the requested services.

   When responding to a path agent's request for a policy route, a route
   server first consults its route database, unless the ROUTE REQUEST
   message contains an explicit directive to generate a new route.  If
   its route database contains one or more routes between the given
   source and destination domains and accommodating the given host set
   and UCI, the route server checks each such route against the set of
   excluded domains listed in the ROUTE REQUEST message.  The route
   server either selects all routes encountered that do not include the
   excluded domains, or, if no such route exists in its route database,
   attempts to generate such a route.  Once the route server selects a
   set of routes, it then checks each such route against the services



Steenstrup                                                     [Page 79]

RFC 1479                     IDPR Protocol                     July 1993


   requested by the path agent and the services offered by the domains
   composing the route.  To obtain the offered services information, the
   route server consults its routing information database.  The route
   server either selects the first route encountered that is consistent
   with both the requested and offered services, or, if no such route
   exists in its route database, attempts to generate such a route.

6.3.1.  Cache Maintenance

   Each route stored in a route database has a maximum cache lifetime
   equal to rdb_rs minutes for a route server and rdb_ps minutes for a
   path agent.  Route servers and path agents reclaim cache space by
   flushing entries that have attained their maximum lifetimes.
   Moreover, paths agents reclaim cache space for routes whose paths
   have failed to be set up successfully or have been torn down (see
   section 7.4).

   Nevertheless, cache space may become scarce, even with reclamation of
   entries.  If a cache fills, the route server or path agent logs the
   event for network management.  To obtain space in the cache when the
   cache is full, the route server or path agent deletes from the cache
   the oldest entry.

7.  Path Control Protocol and Data Message Forwarding Procedure

   Two entities in different domains may exchange IDPR data messages,
   only if there exists an IDPR path set up between the two domains.
   Path setup requires cooperation among path agents and intermediate
   policy gateways.  Path agents locate policy routes, initiate the Path
   Control Protocol (PCP), and manage existing paths between
   administrative domains.  Intermediate policy gateways verify that a
   given policy route is consistent with their domains' transit
   policies, establish the forwarding information, and forward messages
   along existing paths.

   Each policy gateway and each route server contains a path agent.  The
   path agent that initiates path setup in the source or source proxy
   domain is the "originator", and the path agent that handles the
   originator's path setup message in the destination or destination
   proxy domain is the "target".  Every path has two possible directions
   of traffic flow: from originator to target and from target to
   originator.  Path control messages are free to travel in either
   direction, but data messages may be restricted to only one direction.

   Once a path for a policy route is set up, its physical realization is
   a set of consecutive policy gateways, with policy gateways or route
   servers forming the endpoints.  Two successive entities in this set
   belong to either the same domain or the same virtual gateway.  A



Steenstrup                                                     [Page 80]

RFC 1479                     IDPR Protocol                     July 1993


   policy gateway or route server may, at any time, recover the
   resources dedicated to a path that goes through it by tearing down
   that path.  For example, a policy gateway may decide to tear down a
   path that has not been used for some period of time.

   PCP may build multiple paths between source and destination domains,
   but it is not responsible for managing such paths as a group or for
   eliminating redundant paths.

7.1.  An Example of Path Setup

   We illustrate how path setup works by stepping through an example.
   Suppose host Hx in domain AD X wants to communicate with host Hy in
   domain AD Y and that both AD X and AD Y support IDPR.  Hx need not
   know the identity of its own domain or of Hy's domain in order to
   send messages to Hy.  Instead, Hx simply forwards a message bound for
   Hy to one of the gateways on its local network, according to its
   local forwarding information only.  If the recipient gateway is a
   policy gateway, the resident path agent determines how to forward the
   message outside of the domain.  Otherwise, the recipient gateway
   forwards the message to another gateway in AD X, according to its
   local forwading information.  Eventually, the message will arrive at
   a policy gateway in AD X, as policy gateways are the only egress
   points to other domains, in domains that support IDPR.

   The path agent resident in the recipient policy gateway uses the
   message header, including source and destination addresses and any
   requested service information (for example, type of service), in
   order to determine whether it is an intra-domain or inter-domain
   message, and if inter-domain, whether it requires an IDPR policy
   route.  Specifically, the path agent attempts to locate a forwarding
   information database entry for the given traffic flow, from the
   information contained in the message header.  In the future, for IP
   messages, the relevant header information may also include special
   service-specific IP options or even information from higher layer
   protocols.

   Forwarding database entries exist for all of the following:

   - All intra-domain traffic flows.  Intra-domain forwarding
     information is integrated into the forwarding information database
     as soon as it is received.

   - Inter-domain traffic flows that do not require IDPR policy routes.
     Non-IDPR forwarding information is integrated into the forwarding
     database as soon as it is received.

   - IDPR inter-domain traffic flows for which a path has already been



Steenstrup                                                     [Page 81]

RFC 1479                     IDPR Protocol                     July 1993


     set up.  IDPR forwarding information is integrated into the
     forwarding database only during path setup.

   The path agent uses the message header contents to guide the search
   for a forwarding information database entry for a given traffic flow.
   We recommend a radix search to locate such an entry.  When the search
   terminates, it produces either an entry, or, in the case of a new
   IDPR traffic flow, a directive to generate an entry.  If the search
   terminates in an existing forwarding information database entry, the
   path agent forwards the message according to that entry.

   Suppose that the search terminates indicating that the traffic flow
   from Hx to Hy requires an IDPR policy route and that no entry in the
   forwarding information database yet exists for that traffic flow.  In
   this case, the path agent first determines the source and destination
   domains associated with the message's source and destination
   addresses, before attempting to obtain a policy route.  The path
   agent relies on the mapping servers to supply the domain information,
   but it caches all mapping server responses locally to limit the
   number of future queries.  When attempting to resolve an address to a
   domain, the path agent always checks its local cache before
   contacting a mapping server.

   After obtaining the domain information, the path agent attempts to
   obtain a policy route to carry the traffic from Hx to Hy.  The path
   agent relies on route servers to supply policy routes, but it caches
   all route server responses locally to limit the number of future
   queries.  When attempting to locate a suitable policy route, the path
   agent usually consults its local cache before contacting a route
   server, as described previously in section 6.3.

   If no suitable cache entry exists, the path agent queries the route
   server, providing it with the source and destination domains together
   with source policy information carried in the host message or
   specified through configuration.  Upon receiving a policy route
   query, a route server consults its route database.  If it cannot
   locate a suitable route in its route database, the route server
   attempts to generate at least one route to AD Y, consistent with the
   requested services for Hx.

   The route server always returns a response to the path agent,
   regardless of whether it is successful in locating a suitable policy
   route.  The response to a successful route query consists of a set of
   candidate routes, from which the path agent makes its selection.  We
   expect that a path agent will normally choose a single route from a
   candidate set.  Nevertheless, IDPR does not preclude a path agent
   from selecting multiple routes from the candidate set.  A path agent
   may desire multiple routes to support features such as fault



Steenstrup                                                     [Page 82]

RFC 1479                     IDPR Protocol                     July 1993


   tolerance or load balancing; however, IDPR does not currently specify
   how the path agent should use multiple routes.

   If the policy route is a new route provided by the route server,
   there will be no existing path for the route, and thus the path agent
   must set up such a path.  However, if the policy route is an existing
   route extracted from the path agent's cache, there may well be an
   existing path for the route, set up to accommodate a host traffic
   flow.  IDPR permits multiple traffic flows to use the same path,
   provided that all traffic flows sharing the path travel between the
   same endpoint domains and have the same service requirements.
   Nevertheless, IDPR does not preclude a path agent from setting up
   distinct paths along the same policy route to preserve the
   distinction between host traffic flows.

   The path agent associates an identifier with the path, which is
   included in each message that travels down the path and is used by
   the policy gateways along the path in order to determine how to
   forward the message.  If the path already exists, the path agent uses
   the preexisting identifier.  However, for new paths, the path agent
   chooses a path identifier that is different from those of all other
   paths that it manages.  The path agent also updates its forwarding
   information database to reference the path identifier and modifies
   its search procedure to yield the correct entry in the forwarding
   information database given the data message header.

   For new paths, the path agent initiates path setup, communicating the
   policy route, in terms of requested services, constituent domains,
   relevant transit policies, and the connecting virtual gateways, to
   policy gateways in intermediate domains.  Using this information, an
   intermediate policy gateway determines whether to accept or refuse
   the path and to which next policy gateway to forward the path setup
   information.  The path setup procedure allows policy gateways to set
   up a path in both directions simultaneously.  Each intermediate
   policy gateway, after path acceptance, updates its forwarding
   information database to include an entry that associates the path
   identifier with the appropriate previous and next hop policy
   gateways.

   When a policy gateway in AD Y accepts a path, it notifies the source
   path agent in AD X.  We expect that the source path agent will
   normally wait until a path has been successfully established before
   using it to transport data traffic.  However, PCP does not preclude a
   path agent from forwarding messages along a path prior to
   confirmation of successful path establishment.  Paths remain in place
   until they are torn down because of failure, expiration, or when
   resources are scarce, preemption in favor of other paths.




Steenstrup                                                     [Page 83]

RFC 1479                     IDPR Protocol                     July 1993


   We note that data communication between Hx and Hy may occur over two
   separate IDPR paths: one from AD X to AD Y and one from AD Y to AD X.
   The reasons are that within a domain, hosts know nothing about path
   agents nor IDPR paths, and path agents know nothing about other path
   agents' existing IDPR paths.  Thus, in AD Y, the path agent that
   terminates the path from AD X may not be the same as the path agent
   that receives traffic from Hy destined for Hx.  In this case, receipt
   of traffic from Hy forces the second path agent to set up an
   independent path from AD Y to AD X.

7.2.  Path Identifiers

   Each path has an associated path identifier, unique throughout an
   internetwork.  Every IDPR data message travelling along that path
   includes the path identifier, used for message forwarding.  The path
   identifier is the concatenation of three items: the identifier of the
   originator's domain, the identifier of the originator's policy
   gateway or route server, and a 32-bit local path identifier specified
   by the originator.  The path identifier and the CMTP transaction
   identifier have analogous syntax and play analogous roles in their
   respective protocols.

   When issuing a new path identifier, the originator always assigns a
   local path identifier that is different from that of any other active
   or recently torn-down path originally set up by that path agent.
   This helps to distinguish new paths from replays.  Hence, the
   originator must keep a record of each extinct path for long enough
   that all policy gateways on the path will have eliminated any
   reference to it from their memories.  The right-most 30 bits of the
   local identifier are the same for each path direction, as they are
   assigned by the originator.  The left-most 2 bits of the local
   identifier indicate the path direction.

   At path setup time, the originator specifies which of the path
   directions to enable contingent upon the information received from
   the route server in the ROUTE RESPONSE message.  By "enable", we mean
   that each path agent and each intermediate policy gateway establishes
   an association between the path identifier and the previous and next
   policy gateways on the path, which it uses for forwarding data
   messages along that path.  IDPR data messages may travel in the
   enabled path directions only, but path control messages are always
   free to travel in either path direction.  The originator may enable
   neither path direction, if the entire data transaction can be carried
   in the path setup message itself.  In this case, the path agents and
   the intermediate policy gateways do not establish forwarding
   associations for the path, but they do verify consistency of the
   policy information contained in the path setup message, with their
   own transit policies, before forwarding the setup message on to the



Steenstrup                                                     [Page 84]

RFC 1479                     IDPR Protocol                     July 1993


   next policy gateway.

   The path direction portion of the local path identifier has different
   interpretations, depending upon message type.  In an IDPR path setup
   message, the path direction indicates the directions in which the
   path should be enabled: the value 01 denotes originator to target,
   the value 10 denotes target to originator, the value 11 denotes both
   directions, and the value 00 denotes neither direction.  Each policy
   gateway along the path interprets the path direction in the setup
   message and sets up the forwarding information as directed.  In an
   IDPR data message, the path direction indicates the current direction
   of traffic flow: either 01 for originator to target or 10 for target
   to originator.  Thus, if for example, an originator sets up a path
   enabling only the direction from target to originator, the target
   sends data messages containing the path identifier selected by the
   originator together with the path direction set equal to 10.

   Instead of using path identifiers that are unique throughout an
   internetwork, we could have used path identifiers that are unique
   only between a pair of consecutive policy gateways and that change
   from one policy gateway pair to the next.  The advantage of locally
   unique path identifiers is that they may be much shorter than
   globally unique identifiers and hence consume less transmission
   bandwidth.  However, the disadvantage is that the path identifier
   carried in each IDPR data message must be modified at each policy
   gateway, and hence if the integrity/authentication information covers
   the path identifier, it must be recomputed at each policy gateway.
   For security reasons, we have chosen to include the path identifier
   in the set of information covered by the integrity/authentication
   value, and moreover, we advocate public-key based signatures for
   authentication.  Thus, it is not possible for intermediate policy
   gateways to modify the path identifier and then recompute the correct
   integrity/authentication value.  Therefore, we have decided in favor
   of path identifiers that do not change from hop to hop and hence must
   be globally unique.  To speed forwarding of IDPR data messages with
   long path identifiers, policy gateways should hash the path
   identifiers in order to index IDPR forwarding information.

7.3.  Path Control Messages

   Messages exchanged by the path control protocol are classified into
   "requests": SETUP, TEARDOWN, REPAIR; and "responses": ACCEPT, REFUSE,
   ERROR.  These messages have significance for intermediate policy
   gateways as well as for path agents.

   SETUP:
        Establishes a path by linking together pairs of policy gateways.
        The SETUP message is generated by the originator and propagates



Steenstrup                                                     [Page 85]

RFC 1479                     IDPR Protocol                     July 1993


        to the target.  In response to a SETUP message, the originator
        expects to receive an ACCEPT, REFUSE, or ERROR message.  The
        SETUP message carries all information necessary to set up the
        path including path identifier, requested services, transit
        policy information relating to each domain traversed, and
        optionally, expedited data.

   ACCEPT: Signals successful path establishment.  The ACCEPT message is
        generated by the target, in response to a SETUP message, and
        propagates back to the originator.  Reception of an ACCEPT
        message by the originator indicates that the originator can now
        safely proceed to send data along the path.  The ACCEPT message
        contains the path identifier and an optional reason for
        conditional acceptance.

   REFUSE: Signals that the path could not be successfully established,
        either because resources were not available or because there was
        an inconsistency between the services requested by the source
        and the services offered by a transit domain along the path.
        The REFUSE message is generated by the target or by any
        intermediate policy gateway, in response to a SETUP message, and
        propagates back to the originator.  All recipients of a REFUSE
        message recover the resources dedicated to the given path.  The
        REFUSE message contains the path identifier and the reason for
        path refusal.

   TEARDOWN: Tears down a path, typically when a non-recoverable failure
        is detected.  The TEARDOWN message may be generated by any path
        agent or policy gateway in the path and usually propagates in
        both path directions.  All recipients of a TEARDOWN message
        recover the resources dedicated to the given path.  The TEARDOWN
        message contains the path identifier and the reason for path
        teardown.

   REPAIR: Establishes a repaired path by linking together pairs of
        policy gateways.  The REPAIR message is generated by a policy
        gateway after detecting that the next policy gateway on one of
        its existing paths is unreachable.  A policy gateway that
        generates a REPAIR message propagates the message forward at
        most one virtual gateway.  In response to a REPAIR message, the
        policy gateway expects to receive an ACCEPT, REFUSE, TEARDOWN,
        or ERROR message.  The REPAIR message carries the original SETUP
        message.

   ERROR: Transports information about a path error back to the
        originator, when a PCP message contains unrecognized
        information.  The ERROR message may be generated by the target
        or by any intermediate policy gateway and propagates back to the



Steenstrup                                                     [Page 86]

RFC 1479                     IDPR Protocol                     July 1993


        originator.  Most, but not all, ERROR messages are generated in
        response to errors encountered during path setup.  The ERROR
        message includes the path identifier and an explanation of the
        error detected.

   Policy gateways use CMTP for reliable transport of PCP messages,
   between path agents and policy gateways and between consecutive
   policy gateways on a path.  PCP must communicate to CMTP the maximum
   number of transmissions per path control message, pcp_ret, and the
   interval between path contol message retransmissions, pcp_int
   microseconds.  All path control messages, except ERROR messages, may
   be transmitted up to pcp_ret times; ERROR messages are never
   retransmitted.  A path control message is "acceptable" if:

   - It passes the CMTP validation checks.

   - Its timestamp is less than pcp_old (300) seconds behind the
     recipient's internal clock time.

   - It carries a recognized path identifier, provided it is not a SETUP
     message.

   An intermediate policy gateway on a path forwards acceptable PCP
   messages.  As we describe in section 7.4 below, SETUP messages must
   undergo additional tests at each intermediate policy gateway prior to
   forwarding.  Moreover, receipt of an acceptable ACCEPT, REFUSE,
   TEARDOWN, or ERROR message at either path agent or at any
   intermediate policy gateway indirectly cancels any active local CMTP
   retransmissions of the original SETUP message.  When a path agent or
   intermediate policy gateway receives an unacceptable path control
   message, it discards the message and logs the event for network
   management.  The path control message age limit reduces the
   likelihood of denial of service attacks based on message replay.

7.4.  Setting Up and Tearing Down a Path

   Path setup begins when the originator generates a SETUP message
   containing:

   - The path identifier, including path directions to enable.

   - An indication of whether the message includes expedited data.

   -   The source user class identifier.

   - The requested services (see section 5.5.2) and source-specific
     information (see section 7.6.1) for the path.




Steenstrup                                                     [Page 87]

RFC 1479                     IDPR Protocol                     July 1993


   - For each domain on the path, the domain component, applicable
     transit policies, and entry and exit virtual gateways.

   The only mandatory requested service is the maximum path lifetime,
   pth_lif, and the only mandatory source-specific information is the
   data message integrity/authentication type.  If these are not
   specified in the path setup message, each recipient policy gateway
   assigns them default values, (60) minutes for pth_lif and no
   authentication for integrity/authentication type.  Each path agent
   and intermediate policy gateway tears down a path when the path
   lifetime is exceeded.  Hence, no single source can indefinitely
   monopolize policy gateway resources or still functioning parts of
   partially broken paths.

   After generating the SETUP message and establishing the proper local
   forwarding information, the originator selects the next policy
   gateway on the path and forwards the SETUP message to the selected
   policy gateway.  The next policy gateway selection procedure,
   described below, applies when either the originator or an
   intermediate policy gateway is making the selection.  We have elected
   to describe the procedure from the perspective of a selecting
   intermediate policy gateway.

   The policy gateway selects the next policy gateway on a path, in
   round-robin order from its list of policy gateways contained in the
   present or next virtual gateway, as explained below.  In selecting
   the next policy gateway, the policy gateway uses information
   contained in the SETUP message and information provided by VGP and by
   the intra-domain routing procedure.

   If the selecting policy gateway is a domain entry point, the next
   policy gateway must be:

   - A member of the next virtual gateway listed in the SETUP message.

   - Reachable according to intra-domain routes supporting the transit
     policies listed in the SETUP message.

   - Able to reach, according to VGP, the next domain component listed
     in the SETUP message.

   In addition, the selecting policy gateway may use quality of service
   information supplied by intra-domain routing to resolve ties between
   otherwise equivalent next policy gateways in the same domain.  In
   particular, the selecting policy gateway may select the next policy
   gateway whose connecting intra-domain route is optimal according to
   the requested services listed in the SETUP message.




Steenstrup                                                     [Page 88]

RFC 1479                     IDPR Protocol                     July 1993


   If the selecting policy gateway is a domain exit point, the next
   policy gateway must be:

   - A member of the current virtual gateway listed in the SETUP message
     (which is also the selecting policy gateway's virtual gateway).

   - Reachable according to VGP.

   - A member of the next domain component listed in the SETUP message.

   Once the originator or intermediate policy gateway selects a next
   policy gateway, it forwards the SETUP message to the selected policy
   gateway.  Each recipient (policy gateway or target) of an acceptable
   SETUP message performs several checks on the contents of the message,
   in order to determine whether to establish or reject the path.  We
   describe these checks in detail below from the perspective of a
   policy gateway as SETUP message recipient.

7.4.1.  Validating Path Identifiers

   The recipient of a SETUP message first checks the path identifier, to
   make sure that it does not correspond to that of an already existing
   or recently extinct path.  To detect replays, malicious or otherwise,
   path agents and policy gateways maintain a record of each path that
   they establish, for max{pth_lif, pcp_old} seconds.  If the path
   identifier and timestamp carried in the SETUP message match a stored
   path identifier and timestamp, the policy gateway considers the
   message to be a retransmission and does not forward the message.  If
   the path identifier carried in the SETUP message matches a stored
   path identifier but the two timestamps do not agree, the policy
   gateway abandons path setup, logs the event for network management,
   and returns an ERROR message to the originator via the previous
   policy gateway.

7.4.2.  Path Consistency with Configured Transit Policies

   Provided the path identifier in the SETUP message appears to be new,
   the policy gateway proceeds to determine whether the information
   contained within the SETUP message is consistent with the transit
   policies configured for its domain.  The policy gateway must locate
   the source and destination domains, the source host set and user
   class identifier, and the domain-specific information for its own
   domain, within the SETUP message, in order to evaluate path
   consistency.  If the policy gateway fails to recognize the source
   user class (or one or more of the requested services), it logs the
   event for network management but continues with path setup.  If the
   policy gateway fails to locate its domain within the SETUP message,
   it abandons path setup, logs the event for network management, and



Steenstrup                                                     [Page 89]

RFC 1479                     IDPR Protocol                     July 1993


   returns an ERROR message to the originator via the previous policy
   gateway.  The originator responds by tearing down the path and
   subsequently removing the route from its cache.

   Once the policy gateway locates its domain-specific portion of the
   SETUP message, it may encounter the following problems with the
   contents:

   - The domain-specific portion lists a transit policy not configured
     for the domain.

   - The domain-specific portion lists a virtual gateway not configured
     for the domain.

   In each case, the policy gateway abandons path setup, logs the event
   for network management, and returns an ERROR message to the
   originator via the previous policy gateway.  These types of ERROR
   messages indicate to the originator that the route may have been
   generated using information from an out-of-date CONFIGURATION
   message.

   The originator reacts to the receipt of such an ERROR message as
   follows.  First, it tears down the path and removes the route from
   its cache.  Then, it issues to a route server a ROUTE REQUEST message
   containing a directive to refresh the routing information database,
   with the most recent CONFIGURATION message from the domain that
   issued the ERROR message, before generating a new route.

   Once it verifies that its domain-specific information in the SETUP
   message is recognizable, the policy gateway then checks that the
   information contained within the SETUP message is consistent with the
   transit policies configured for its domain.  A policy gateway at the
   entry to a domain checks path consistency in the direction from
   originator to target, if the enabled path directions include
   originator to target.  A policy gateway at the exit to a domain
   checks path consistency in the direction from target to originator,
   if the enabled path directions include target to originator.

   When evaluating the consistency of the path with the transit policies
   configured for the domain, the policy gateway may encounter any of
   the following problems with SETUP message contents:

   - A transit policy does not apply in the given direction between the
     virtual gateways listed in the SETUP message.

   - A transit policy denies access to traffic from the given host set
     between the source and destination domains listed in the SETUP
     message.



Steenstrup                                                     [Page 90]

RFC 1479                     IDPR Protocol                     July 1993


   - A transit policy denies access to traffic from the source user
     class listed in the SETUP message.

   - A transit policy denies access to traffic at the current time.

   In each case, the policy gateway abandons path setup, logs the event
   for network management, and returns a REFUSE message to the
   originator via the previous policy gateway.  These types of REFUSE
   messages indicate to the originator that the route may have been
   generated using information from an out-of-date CONFIGURATION
   message.  The REFUSE message also serves to teardown the path.

   The originator reacts to the receipt of such a REFUSE message as
   follows. First, it removes the route from its cache.  Then, it issues
   to a route server a ROUTE REQUEST message containing a directive to
   refresh the routing information database, with the most recent
   CONFIGURATION message from the domain that issued the REFUSE message,
   before generating a new route.

7.4.3.  Path Consistency with Virtual Gateway Reachability

   Provided the information contained in the SETUP message is consistent
   with the transit policies configured for its domain, the policy
   gateway proceeds to determine whether the path is consistent with the
   reachability of the virtual gateway containing the potential next
   hop.  To determine virtual gateway reachability, the policy gateway
   uses information provided by VGP and by the intra-domain routing
   procedure.

   When evaluating the consistency of the path with virtual gateway
   reachability, the policy gateway may encounter any of the following
   problems:

   - The virtual gateway containing the potential next hop is down.

   - The virtual gateway containing the potential next hop is not
     reachable via any intra-domain routes supporting the transit
     policies listed in the SETUP message.

   - The next domain component listed in the SETUP message is not
     reachable.

   Each of these determinations is made from the perspective of a single
   policy gateway and may not reflect actual reachability.  In each
   case, the policy gateway encountering such a problem returns a REFUSE
   message to the previous policy gateway which then selects a different
   next policy gateway, in round-robin order, as described in
   previously.  If the policy gateway receives the same response from



Steenstrup                                                     [Page 91]

RFC 1479                     IDPR Protocol                     July 1993


   all next policy gateways selected, it abandons path setup, logs the
   event for network management, and returns the REFUSE message to the
   originator via the previous policy gateway.  These types of REFUSE
   messages indicate to the originator that the route may have been
   generated using information from an out-of-date DYNAMIC message.  The
   REFUSE message also serves to teardown the path.

   The originator reacts to the receipt of such a REFUSE message as
   follows.  First, it removes the route from its cache.  Then, it
   issues to a route server a ROUTE REQUEST message containing a
   directive to refresh the routing information database, with the most
   recent DYNAMIC message from the domain that issued the REFUSE
   message, before generating a new route.

7.4.4.  Obtaining Resources

   Once the policy gateway determines that the SETUP message contents
   are consistent with the transit policies and virtual gateway
   reachability of its domain, it attempts to gain resources for the new
   path.  For this version of IDPR, path resources consist of memory in
   the local forwarding information database.  However, in the future,
   path resources may also include reserved link bandwidth.

   If the policy gateway does not have sufficient resources to establish
   the new path, it uses the following algorithm to determine whether to
   generate a REFUSE message for the new path or a TEARDOWN message for
   an existing path in favor of the new path.  There are two cases:


   - No paths have been idle for more than pcp_idle (300) seconds.  In
     this case, the policy gateway returns a REFUSE message to the
     previous policy gateway.  This policy gateway then tries to select
     a different next policy gateway, as described previously, provided
     the policy gateway that issued the REFUSE message was not the
     target. If the REFUSE message was issued by the target or if there
     is no available next policy gateway, the policy gateway returns
     the REFUSE message to the originator via the previous policy
     gateway and logs the event for network management.  The REFUSE
     message serves to tear down the path.

   - At least one path has been idle for more than pcp_idle seconds.  In
     this case, the policy gateway tears down an older path in order to
     accommodate the newer path and logs the event for network
     management.  Specifically, the policy gateway tears down the least
     recently used path among those that have been idle for longer than
     pcp_idle seconds, resolving ties by choosing the oldest such path.

   If the policy gateway has sufficient resources to establish the path,



Steenstrup                                                     [Page 92]

RFC 1479                     IDPR Protocol                     July 1993


   it attempts to update its local forwarding information database with
   information about the path identifier, previous and next policy
   gateways on the path, and directions in which the path should be
   enabled for data traffic transport.

7.4.5  Target Response

   When an acceptable SETUP message successfully reaches an entry policy
   gateway in the destination or destination proxy domain, this policy
   gateway performs all of the SETUP message checks described in the
   above sections.  The policy gateway's path agent then becomes the
   target, provided no checks fail, unless there is an explicit target
   specified in the SETUP message.  For example, remote route servers
   act as originator and target during RSQP message exchanges (see
   section 5.2).  If the recipient policy gateway is not the target, it
   attempts to forward the SETUP message to the target along an intra-
   domain route.  However, if the target is not reachable via intra-
   domain routing, the policy gateway abandons path setup, logs the
   event for network management, and returns a REFUSE message to the
   originator via the previous policy gateway.  The REFUSE message
   serves to tear down the path.

   Once the SETUP message reaches the target, the target determines
   whether it has sufficient path resources.  The target generates an
   ACCEPT message, provided it has sufficient resources to establish the
   path.  Otherwise, it generates a REFUSE message.

   The target may choose to use the reverse path to transport data
   traffic to the source domain, if the enabled path directions include
   10 or 11.  However, the target must first verify the consistency of
   the reverse path with its own domain's configured transit policies,
   before sending data traffic over that path.

7.4.6.  Originator Response

   The originator expects to receive an ACCEPT, REFUSE, or ERROR message
   in response to a SETUP message and reacts as follows:

   - The originator receives an ACCEPT message, confirming successful
     path establishment.  To expedite data delivery, the originator may
     forward data messages along the path prior to receiving an ACCEPT
     message, with the understanding that there is no guarantee that the
     path actually exists.

   - The originator receives a REFUSE message or an ERROR message,
     implying that the path could not be successfully established.  In
     response, the originator attempts to set up a different path to the
     same destination, as long as the number of selected different paths



Steenstrup                                                     [Page 93]

RFC 1479                     IDPR Protocol                     July 1993


     does not exceed setup_try (3).  If the originator is unsuccessful
     after setup_try attempts, it abandons path setup and logs the event
     for network management.

   - The originator fails to receive any response to the SETUP message
     within setup_int microseconds after transmission.  In this case,
     the originator attempts path setup using the same policy route and
     a new path identifier, as long as the number of path setup attempts
     using the same route does not exceed setup_ret (2).  If the
     originator fails to receive a response to a SETUP message after
     setup_ret attempts, it logs the event for network management and
     then proceeds as though it received a negative response, namely a
     REFUSE or an ERROR, to the SETUP message.  Specifically, it
     attempts to set up a different path to the same destination, or it
     abandons path setup altogether, depending on the value of
     setup_try.

7.4.7.  Path Life

   Once set up, a path does not live forever.  A path agent or policy
   gateway may tear down an existing path, provided any of the following
   conditions are true:

   - The maximum path lifetime (in minutes, bytes, or messages) has been
     exceeded at the originator, the target, or an intermediate policy
     gateway.  In each case, the IDPR entity detecting path expiration
     logs the event for network management and generates a TEARDOWN
     message as follows:

      o The originator path agent generates a TEARDOWN message for
        propagation toward the target.

      o The target path agent generates a TEARDOWN message for
        propagation toward the originator.

      o An intermediate policy gateway generates two TEARDOWN messages,
        one for propagation toward the originator and one for
        propagation toward the target.

   - The previous or next policy gateway becomes unreachable, across a
     virtual gateway or across a domain according to a given transit
     policy, and the path is not reparable.  In either case, the policy
     gateway detecting the reachability problem logs the event for
     network management and generates a TEARDOWN message as follows:

      o If the previous policy gateway is unreachable, an intermediate
        policy gateway generates a TEARDOWN message for propagation to
        the target.



Steenstrup                                                     [Page 94]

RFC 1479                     IDPR Protocol                     July 1993


      o If the next policy gateway is unreachable, an intermediate
        policy gateway generates a TEARDOWN message for propagation to
        the originator.

   - All of the policy gateway's path resources are in use at the
     originator, the target, or an intermediate policy gateway, a new
     path requires resources, and the given existing path is expendable,
     according to the least recently used criterion discussed in section
     7.4.4 above.  In each case, the IDPR entity initiating path
     preemption logs the event for network management and generates a
     TEARDOWN message as follows:

      o The originator path agent generates a TEARDOWN message for
        propagation toward the originator.

      o The target path agent generates a TEARDOWN message for
        propagation toward the originator.

      o An intermediate policy gateway generates two TEARDOWN messages,
        one for propagation toward the originator and one for
        propagation toward the target.

   Path teardown at a path agent or policy gateway, whether initiated by
   one of the above events, by receipt of a TEARDOWN message, or by
   receipt of a REFUSE message during path setup (as discussed in the
   previous sections), results in the path agent or policy gateway
   releasing all resources devoted to both directions of the path.

7.5.  Path Failure and Recovery

   When a policy gateway fails, it may not be able to save information
   pertaining to its established paths.  Thus, when the policy gateway
   returns to service, it may have no recollection of the paths set up
   through it and hence may no longer be able to forward data messages
   along these paths.  We expect that when a policy gateway fails, it
   will usually be out of service for long enough that the up/down
   protocol and the intra-domain routing procedure can detect that the
   particular policy gateway is no longer reachable.  In this case,
   adjacent or neighbor policy gateways that have set up paths through
   the failed policy gateway and that have detected the failure, attempt
   local path repair (see section 7.5.2 below), and if unsuccessful,
   issue TEARDOWN messages for all affected paths.









Steenstrup                                                     [Page 95]

RFC 1479                     IDPR Protocol                     July 1993


7.5.1.  Handling Implicit Path Failures

   Nevertheless, policy gateways along a path must be able to handle the
   case in which a policy gateway fails and subsequently returns to
   service without either the up/down protocol or the intra-domain
   routing procedure detecting the failure; we do not expect this event
   to occur often.  If the policy gateway, prior to failure, contained
   forwarding information for several established paths, it may now
   receive many IDPR data messages containing unrecognized path
   identifiers.  The policy gateway should alert the data sources that
   their paths through it are no longer viable.

   Policy gateways that receive IDPR data messages with unrecognized
   path identifiers take one of the following two actions, depending
   upon their past failure record:

   - The policy gateway has not failed in the past pg_up (24) hour
     period.  In this case, there are at least four possible reasons for
     the unrecognized path identifier in the data message:

      o The data message path identifier has been corrupted in a way
        that is not detectable by the integrity/authentication value, if
        one is present.

      o The policy gateway has experienced a memory error.

      o The policy gateway failed sometime during the life of the path
        and source sent no data on the path for a period of pg_up hours
        following the failure.  Although paths may persist for more than
        pg_up hours, we expect that they will also be used more
        frequently than once every pg_up hours.

      o The path was not successfully established, and the originator
        sent data messages down the path prior to receiving a response
        to its SETUP message.

      In all cases, the policy gateway discards the data message and
      logs the event for network management.

   - The policy gateway has failed at least once in the past pg_up hour
     period.  Thus, the policy gateway assumes that the unrecognized
     path identifier in the data message may be attributed to its
     failure.  In response to the data message, the policy gateway
     generates an ERROR message containing the unrecognized path
     identifier.  The policy gateway then sends the ERROR message back
     to the entity from which it received the data message, which should
     be equivalent to the previous policy gateway on the path.




Steenstrup                                                     [Page 96]

RFC 1479                     IDPR Protocol                     July 1993


   When the previous policy gateway receives such an ERROR message, it
   decides whether the message is acceptable.  If the policy gateway
   does not recognize the path identifier contained in the ERROR
   message, it does not find the ERROR message acceptable and
   subsequently discards the message.  However, if the policy gateway
   does find the ERROR message acceptable, it then determines whether it
   has already received an ACCEPT message for the given path.  If the
   policy gateway has not received an ACCEPT message for that path, it
   discards the ERROR message and takes no further action.

   If the policy gateway has received an ACCEPT message for that path,
   it then attempts path repair, as described in section 7.5.2 below.
   Only if path repair is unsuccessful does the previous policy gateway
   generate a TEARDOWN message for the path and return it to the
   originator.  The TEARDOWN message includes the domain and virtual
   gateway containing the policy gateway that failed, which aids the
   originator in selecting a new path that does not include the domain
   containing the failed policy gateway.  This mechanism ensures that
   path agents quickly discover and recover from disrupted paths, while
   guarding against unwarranted path teardown.

7.5.2.  Local Path Repair

   Failure of one of more entities on a given path may render the path
   unusable.  If the failure is within a domain, IDPR relies on the
   intra-domain routing procedure to find an alternate route across the
   domain, which leaves the path unaffected.  If the failure is in a
   virtual gateway, policy gateways must bear the responsibility of
   repairing the path.  Policy gateways nearest to the failure are the
   first to recognize its existence and hence can react most quickly to
   repair the path.

   Relinquishing control over path repair to policy gateways in other
   domains may be unacceptable to some domain administrators.  The
   reason is that these policy gateways cannot guarantee construction of
   a path that satisfies the source policies of the source domain, as
   they have no knowledge of other domains' source policies.

   Nevertheless, limited local path repair is feasible, without
   distributing either source policy information throughout an
   internetwork or detailed path information among policy gateways in
   the same domain or in the same virtual gateway.  We say that a path
   is "locally reparable" if there exists an alternate route between two
   policy gateways, separated by at most one virtual gateway, on the
   path.  This definition covers path repair in the presence of failed
   routes between consecutive policy gateways as well as failed policy
   gateways themselves.




Steenstrup                                                     [Page 97]

RFC 1479                     IDPR Protocol                     July 1993


   An IDPR entity attempts local repair of an established path, in the
   direction from originator to target, immediately after detecting that
   the next policy gateway on the path is no longer reachable.  To
   prevent multiple path repairs in response to the same failure, we
   have stipulated that path repair can only be initiated in the
   direction from originator to target.  The IDPR entity initiating
   local path repair attempts to find an alternate path to the policy
   gateway immediately following the unreachable policy gateway on the
   path.

   Local path repair minimizes the disruption of data traffic flow
   caused by certain types of failures along an established path.
   Specifically, local path repair can accommodate an individual failed
   policy gateway or failed direct connection between two adjacent
   policy gateways.  However, it can only be attempted through virtual
   gateways containing multiple peer policy gateways.  Local path repair
   is not designed to repair paths traversing failed virtual gateways or
   domain partitions.  Whenever local path repair is impossible, the
   failing path must be torn down.

7.5.3.  Repairing a Path

   When an IDPR entity detects through an ERROR message that the next
   policy gateway has no knowledge of a given path, it generates a
   REPAIR message and forwards it to the next policy gateway.  This
   REPAIR message will reestablish the path through the next policy
   gateway.

   When an entity detects that the next policy gateway on a path is no
   longer reachable, it takes one of the following actions, depending
   upon whether the entity is a member of the next policy gateway's
   virtual gateway.

   - If the entity is not a member of the next policy gateway's virtual
     gateway, then one of the following two conditions must be true:

      o The next policy gateway has a peer that is reachable via an
        intra-domain route consistent with the requested services.  In
        this case, the entity generates a REPAIR message containing the
        original SETUP message and forwards it to the next policy
        gateway's peer.

      o The next policy gateway has no peers that are reachable via
        intra-domain routes consistent with the requested services.  In
        this case, the entity tears down the path back to the
        originator.

   - If the entity is a member of the next policy gateway's virtual



Steenstrup                                                     [Page 98]

RFC 1479                     IDPR Protocol                     July 1993


   gateway, then one of the following four conditions must be true:

      o The next policy gateway has a peer that belongs to the same
        domain component and is directly-connected to and reachable from
        the entity.  In this case, the entity generates a REPAIR message
        and forwards it to the next policy gateway's peer.

      o The next policy gateway has a peer that belongs to the same
        domain component, is not directly-connected to the entity, but
        is directly-connected to and reachable from one of the entity's
        peers, which in turn is reachable from the entity via an intra-
        domain route consistent with the requested services.  In this
        case, the entity generates a REPAIR message and forwards it to
        its peer.

      o The next policy gateway has no operational peers within its
        domain component, but is directly-connected to and reachable
        from one of the entity's peers, which in turn is reachable from
        the entity via an intra-domain route consistent with the
        requested services.  In this case, the entity generates a REPAIR
        message and forwards it to its peer.

      o The next policy gateway has no operational peers within its
        domain component, and the entity has no operational peers which
        are both reachable via intra-domain routes consistent with the
        requested services and directly-connected to and reachable from
        the next policy gateway.  In this case, the entity tears down
        the path back to the originator.

   A recipient of a REPAIR message takes the following steps, depending
   upon its relationship to the entity that issued the REPAIR message.

   - The recipient and the issuing entity are in the same domain or in
     same virtual gateway.  In this case, the recipient extracts the
     SETUP message contained within the REPAIR message and treats the
     message as it would any other SETUP message.  Specifically, the
     recipient checks consistency of the path with its domain's transit
     policies and virtual gateway reachability.  If there are
     unrecognized portions of the SETUP message, the recipient generates
     an ERROR message, and if there are path inconsistencies, the
     recipient generates a REFUSE message.  In either case, the
     recipient returns the corresponding message to the policy gateway
     from which it received the REPAIR message.  Otherwise, if the
     recipient accepts the REPAIR message, it updates its local
     forwarding information database accordingly and forwards the REPAIR
     message to a potential next policy gateway, according to the
     information contained in the enclosed SETUP message.




Steenstrup                                                     [Page 99]

RFC 1479                     IDPR Protocol                     July 1993


   - The recipient and the issuing entity are in different domains and
     different virtual gateways.  In this case, the recipient extracts
     the SETUP message from the REPAIR message and determines whether
     the associated path matches any of its established paths.  If the
     path does not match an established path, the recipient generates a
     REFUSE message and returns it to the policy gateway from which it
     received the REPAIR message.  In response to the receipt of a
     REFUSE message, the policy gateway tries a different next policy
     gateway.

   The path is reparable, if a path match is discovered.  In this case,
   the recipient updates the path entry in the local forwarding
   information database and issues an ACCEPT message to the policy
   gateway from which it received the REPAIR message, which in turn
   returns the message to the entity that issued the REPAIR message.
   The path is irreparable if all potential next policy gateways have
   been exhausted and a path match has yet to be discovered.  In this
   case, the policy gateway that fails to locate a next policy gateway
   issues a TEARDOWN message to return to the originator.

   An IDPR entity expects to receive an ACCEPT, TEARDOWN, REFUSE, or
   ERROR message in response to a REPAIR message and reacts to these
   responses differently as follows:

   - The entity always returns a TEARDOWN message to the originator via
     previous policy gateway.

   - The entity does not return an ACCEPT message to the originator, but
     receipt of such a message indicates that the path has been
     successfully repaired.

   - The entity infers that the path is irreparable and subsequently
     tears down the path and logs the event for network management, upon
     receipt of a REFUSE or ERROR message or when no response to the
     REPAIR message arrives within setup_int microseconds.

   When an entity detects that the previous policy gateway on a path
   becomes unreachable, it expects to receive a REPAIR message within
   setup_wait microseconds.  If the entity does not receive a REPAIR
   message for the path within that time, it infers that the path is
   irreparable and subsequently tears down the path and logs the event
   for network management.

7.6.  Path Control Message Formats

   The path control protocol number is equal to 3.  We describe the
   contents of each type of PCP message below.




Steenstrup                                                    [Page 100]

RFC 1479                     IDPR Protocol                     July 1993


7.6.1.  SETUP

   The SETUP message type is equal to 0.

    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                            PATH ID                            |
   |                                                               |
   +-------------------------------+-------------------------------+
   |            SRC AD             |            HST SET            |
   +---------------+---------------+-------------------------------+
   |      UCI      |    UNUSED     |            NUM RQS            |
   +---------------+---------------+-------------------------------+
   |            DST AD             |            TGT ENT            |
   +-------------------------------+-------------------------------+
   |            AD PTR             |
   +-------------------------------+
   For each requested service for the path:
   +-------------------------------+-------------------------------+
   |            RQS TYP            |            RQS LEN            |
   +-------------------------------+-------------------------------+
   |                            RQS SRV                            |
   +---------------------------------------------------------------+
   For each domain contained in the path:
   +---------------+---------------+-------------------------------+
   |    AD LEN     |      VG       |            ADJ AD             |
   +---------------+---------------+-------------------------------+
   |            ADJ CMP            |            NUM TP             |
   +-------------------------------+-------------------------------+
   |              TP               |
   +-------------------------------+

   PATH ID
        (64 bits) Path identifier consisting of the numeric identifier
        for the originator's domain (16 bits), the numeric identifier
        for the originator policy gateway or route server (16 bits), the
        path direction (2 bits), and the local path identifier (30
        bits).

   SRC AD (16 bits) Numeric identifier for the source domain, which may
        be different from the originator domain if the originator domain
        is a proxy for the source.

   HST SET (16 bits) Numeric identifier for the source's host set.

   UCI (8 bits) Numeric identifier for the source user class.  The value
        0 indicates that there is no particular source user class.



Steenstrup                                                    [Page 101]

RFC 1479                     IDPR Protocol                     July 1993


   UNUSED (8 bits) Not currently used; must be set equal to 0.

   NUM RQS (16 bits) Number of requested services.

   DST AD (16 bits) Numeric identifier for the destination domain, which
        may be different from the target domain if the target domain is
        a proxy for the destination.

   TGT ENT (16 bits) Numeric identifier for the target entity.  A value
        of 0 indicates that there is no specific target entity.

   AD PTR (16 bits) Byte offset from the beginning of the message
        indicating the location of the beginning of the domain-specific
        information, contained in the right-most 15 bits.  The left-most
        bit indicates whether the message includes expedited data (1
        expedited data, 0 no expedited data).

   RQS TYP (16 bits) Numeric identifier for a type of requested service
        or source-specific information.  Valid requested services are
        described in section 5.5.2.  Valid source source-specific
        information includes the following types:

        12.  MD4/RSA data message authentication (see [16]).

        13.  MD5/RSA data message authentication (see [17]).

        14.  Billing address (variable).

        15.  Charge number (variable).

   RQS LEN (16 bits) Length of the requested service or source-specific
        information, in bytes, beginning with the next field.

   RQS SRV (variable) Description of the requested service or source-
        specific information.

   AD LEN (8 bits) Length of the information associated with a
        particular domain on the route, in bytes, beginning with the
        next field.

   VG (8 bits) Numeric identifier for an exit virtual gateway.

   ADJ AD (16 bits) Numeric identifier for an adjacent domain.

   ADJ CMP (16 bits) Numeric identifier for a component of the adjacent
        domain.  Used to aid a policy gateway in routing across a
        virtual gateway connected to a partitioned domain.




Steenstrup                                                    [Page 102]

RFC 1479                     IDPR Protocol                     July 1993


   NUM TP (16 bits) Number of transit policies that apply to the section
        of the path traversing the given domain component.

   TP (16 bits) Numeric identifier for a transit policy.

7.6.2.  ACCEPT

   The ACCEPT message type is equal to 1.

    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                            PATH ID                            |
   |                                                               |
   +---------------+-----------------------------------------------+
   |    RSN TYP    |                    REASON                     |
   +---------------+-----------------------------------------------+

   PATH ID
        (64 bits) Path identifier contained in the original SETUP
        message.

   RSN TYP (optional, 8 bits) Numeric identifier for the reason for
        conditional path acceptance.

   REASON (optional, variable) Description of the reason for conditional
        path acceptance.  Currently, no reasons have been defined.

7.6.3  REFUSE

   The REFUSE message type is equal to 2.

    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                            PATH ID                            |
   |                                                               |
   +---------------+-----------------------------------------------+
   |    RSN TYP    |                    REASON                     |
   +---------------+-----------------------------------------------+

   PATH ID
        (64 bits) Path identifier contained in the original SETUP
        message.

   RSN TYP (8 bits) Numeric identifier for the reason for path refusal.

   REASON (variable) Description of the reason for path refusal.  Valid



Steenstrup                                                    [Page 103]

RFC 1479                     IDPR Protocol                     July 1993


        reasons include the following types:


        1.  Transit policy does not apply between the virtual gateways in a
            given direction.  Numeric identifier for the transit policy (16
            bits).

        2.  Transit policy denies access to traffic from the host set between
            the source and destination domains.  Numeric identifier for the
            transit policy (16 bits).

        3.  Transit policy denies access to traffic from the source user
            class.  Numeric identifier for the transit policy (16 bits).

        4.  Transit policy denies access to traffic at the current time.
            Numeric identifier for the transit policy (16 bits).

        5.  Virtual gateway is down.  Numeric identifier for the virtual
            gateway (8 bits) and associated adjacent domain (16 bits).

        6.  Virtual gateway is not reachable according to the given transit
            policy.  Numeric identifier for the virtual gateway (8 bits),
            associated adjacent domain (16 bits), and transit policy (16
            bits).

        7.  Domain component is not reachable.  Numeric identifier for the
            domain (16 bits) and the component (16 bits).

        8.  Insufficient resources to establish the path.

        9.  Target is not reachable via intra-domain routing.

        10. No existing path with the given path identifier, in response to
            a REPAIR message only.

7.6.4.  TEARDOWN

   The TEARDOWN message type is equal to 3.

    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                            PATH ID                            |
   |                                                               |
   +---------------+-----------------------------------------------+
   |    RSN TYP    |                    REASON                     |
   +---------------+-----------------------------------------------+




Steenstrup                                                    [Page 104]

RFC 1479                     IDPR Protocol                     July 1993


   PATH ID
        (64 bits) Path identifier contained in the original SETUP
        message.

   RSN TYP (8 bits) Numeric identifier for the reason for path teardown.

   REASON (variable) Description of the reason for path teardown. Valid
        reasons include the following types:

   1.  Virtual gateway is down.  Numeric identifier for the virtual
       gateway (8 bits) and associated adjacent domain (16 bits).

   2.  Virtual gateway is not reachable according to the given transit
       policy.  Numeric identifier for the virtual gateway (8 bits),
       associated adjacent domain (16 bits), and transit policy (16
       bits).

   3.  Domain component is not reachable.  Numeric identifier for the
       domain (16 bits) and the component (16 bits).

   4.  Maximum path lifetime exceeded.

   5.  Preempted path.

   6.  Unable to repair path.

7.6.5.  ERROR

   The ERROR message type is equal to 4.

    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                            PATH ID                            |
   |                                                               |
   +---------------+---------------+-------------------------------+
   |      MSG      |    RSN TYP    |            REASON             |
   +---------------+---------------+-------------------------------+

   PATH ID
        (64 bits) Path identifier contained in the path control or data
        message in error.

   MSG (8 bits) Numeric identifier for the type of path control message
        in error.  This field is ignored for error type 5.

   RSN TYP (8 bits) Numeric identifier for the reason for the PCP
        message error.



Steenstrup                                                    [Page 105]

RFC 1479                     IDPR Protocol                     July 1993


   REASON (variable) Description of the reason for the PCP message
        error.  Valid reasons include the following types:

   1.   Path identifier is already currently active.

   2.   Domain does not appear in the SETUP message.

   3.   Transit policy is not configured for the domain.  Numeric
   identifer for
        the transit policy (16 bits).

   4.   Virtual gateway not configured for the domain.  Numeric
   identifier
        for the virtual gateway (8 bits) and associated adjacent domain
   (16
        bits).

   5.   Unrecognized path identifier in an IDPR data message.

7.6.6.  REPAIR

   The REPAIR message type is equal to 5.  A REPAIR message contains the
   original SETUP message only.

7.6.7.  Negative Acknowledgements

   When a policy gateway receives an unacceptable PCP message that
   passes the CMTP validation checks, it includes, in its CMTP ACK, an
   appropriate negative acknowledgement.  This information is placed in
   the INFORM field of the CMTP ACK (described previously in section
   2.4); the numeric identifier for each type of PCP negative
   acknowledgement is contained in the left-most 8 bits of the INFORM
   field.  Negative acknowledgements associated with PCP include the
   following types:

   1.  Unrecognized PCP message type.  Numeric identifier for the
       unrecognized message type (8 bits).

   2.  Out-of-date PCP message.

   3.  Unrecognized path identifier (for all PCP messages except SETUP).
       Numeric identifier for the unrecognized path (64 bits).

8.  Security Considerations

   Refer to sections 1.6, 1.7, and 2.3 for details on security in IDPR.





Steenstrup                                                    [Page 106]

RFC 1479                     IDPR Protocol                     July 1993


9.  Author's Address

   Martha Steenstrup
   BBN Systems and Technologies
   10 Moulton Street
   Cambridge, MA 02138

   Phone: (617) 873-3192
   Email: msteenst@bbn.com

References

   [1]  Clark, D., "Policy Routing in Internet Protocols", RFC 1102, May
        1989.

   [2]  Estrin, D., "Requirements for Policy Based Routing in the
        Research Internet", RFC 1125, November 1989.

   [3]  Little, M., "Goals and Functional Requirements for Inter-
        Autonomous System Routing", RFC 1126, July 1989.

   [4]  Breslau, L. and Estrin, D., "Design of Inter-Administrative
        Domain Routing Protocols", Proceedings of the ACM SIGCOMM '90
        Symposium, September 1990.

   [5]  Steenstrup, M., "An Architecture for Inter-Domain Policy Rout-
        ing", RFC 1478, July 1993.

   [6]  Austein, R., "DNS Support for IDPR", Work in Progress, March
        1993.

   [7]  Bowns, H. and Steenstrup, M., "Inter-Domain Policy Routing Con-
        figuration and Usage", Work in Progress, July 1991.

   [8]  Woodburn, R., "Definitions of Managed Objects for Inter-Domain
        Policy Routing (Version 1)", Work in Progress, March 1993.

   [9]  McQuillan, J., Richer, I., Rosen, E., and Bertsekas, D.,
        "ARPANET Routing Algorithm Improvements: Second Semiannual
        Technical Report", BBN Report No. 3940, October 1978.

   [10] Moy, J., "The OSPF Specification", RFC 1131, October 1989.

   [11] Oran, D. (editor), "Intermediate System to Intermediate System
        Routeing Exchange Protocol for Use in Conjunction with the Pro-
        tocol for Providing the Connectionless-mode Network Service (ISO
        8473)", ISO/IEC JTC1/SC6/WG2, October 1989.




Steenstrup                                                    [Page 107]

RFC 1479                     IDPR Protocol                     July 1993


   [12] Estrin, D., and Tsudik, G., "Secure Control of Transit Internet-
        work Traffic, TR-89-15, Computer Science Department, University
        of Southern California.

   [13] Linn, J., "Privacy Enhancement for Internet Electronic Mail:
        Part I - Message Encipherment and Authentication Procedures",
        RFC 1113, August 1989.

   [14] Kent, S., and Linn, J., "Privacy Enhancement for Internet Elec-
        tronic Mail: Part II - Certificate-based Key Management", RFC
        1114, August 1989.

   [15] Linn, J., "Privacy Enhancement for Internet Electronic Mail:
        Part III - Algorithms, Modes, and Identifiers", RFC 1115, August
        1989.

   [16] Rivest, R., "The MD4 Message-Digest Algorithm", RFC 1320, April
        1992.

   [17] Rivest, R., "The MD5 Message-Digest Algorithm", RFC 1321, April
        1992.






























Steenstrup                                                    [Page 108]