File: rfc2676.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 (2803 lines) | stat: -rw-r--r-- 124,563 bytes parent folder | download | duplicates (5)
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






Network Working Group                                  G. Apostolopoulos
Request for Comments: 2676                                   D. Williams
Category: Experimental                                               IBM
                                                                S. Kamat
                                                                  Lucent
                                                               R. Guerin
                                                                   UPenn
                                                                 A. Orda
                                                                Technion
                                                           T. Przygienda
                                                           Siara Systems
                                                             August 1999


               QoS Routing Mechanisms and OSPF Extensions

Status of this Memo

   This memo defines an Experimental Protocol for the Internet
   community.  It does not specify an Internet standard of any kind.
   Discussion and suggestions for improvement are requested.
   Distribution of this memo is unlimited.

Copyright Notice

   Copyright (C) The Internet Society (1999).  All Rights Reserved.

Abstract

   This memo describes extensions to the OSPF [Moy98] protocol to
   support QoS routes.  The focus of this document is on the algorithms
   used to compute QoS routes and on the necessary modifications to OSPF
   to support this function, e.g., the information needed, its format,
   how it is distributed, and how it is used by the QoS path selection
   process.  Aspects related to how QoS routes are established and
   managed are also briefly discussed.  The goal of this document is to
   identify a framework and possible approaches to allow deployment of
   QoS routing capabilities with the minimum possible impact to the
   existing routing infrastructure.

   In addition, experience from an implementation of the proposed
   extensions in the GateD environment [Con], along with performance
   measurements is presented.








Apostolopoulos, et al.        Experimental                      [Page 1]

RFC 2676       QoS Routing Mechanisms and OSPF Extensions    August 1999


Table of Contents

   1. Introduction                                                    3
       1.1. Overall Framework . . . . . . . . . . . . . . . . . . . . 3
       1.2. Simplifying Assumptions . . . . . . . . . . . . . . . . . 5
   2. Path Selection Information and Algorithms                       7
       2.1. Metrics . . . . . . . . . . . . . . . . . . . . . . . . . 7
       2.2. Advertisement of Link State Information . . . . . . . . . 8
       2.3. Path Selection  . . . . . . . . . . . . . . . . . . . . .10
             2.3.1. Path Computation Algorithm  . . . . . . . . . . .11
   3. OSPF Protocol Extensions                                       16
       3.1. QoS -- Optional Capabilities  . . . . . . . . . . . . . .17
       3.2. Encoding Resources as Extended TOS  . . . . . . . . . . .17
             3.2.1. Encoding bandwidth resource . . . . . . . . . . .19
             3.2.2. Encoding Delay  . . . . . . . . . . . . . . . . .21
       3.3. Packet Formats  . . . . . . . . . . . . . . . . . . . . .21
       3.4. Calculating the Inter-area Routes . . . . . . . . . . . .22
       3.5. Open Issues . . . . . . . . . . . . . . . . . . . . . . .22
   4. A Reference Implementation based on GateD                      22
       4.1. The Gate Daemon (GateD) Program . . . . . . . . . . . . .22
       4.2. Implementing the QoS Extensions of OSPF . . . . . . . . .23
             4.2.1. Design Objectives and Scope . . . . . . . . . . .23
             4.2.2. Architecture  . . . . . . . . . . . . . . . . . .24
       4.3. Major Implementation Issues . . . . . . . . . . . . . . .25
       4.4. Bandwidth and Processing Overhead of QoS Routing  . . . .29
   5. Security Considerations                                        32
   A. Pseudocode for the BF Based Pre-Computation Algorithm          33
   B. On-Demand Dijkstra Algorithm for QoS Path Computation          36
   C. Precomputation Using Dijkstra Algorithm                        39
   D. Explicit Routing Support                                       43
   Endnotes                                                          45
   References                                                        46
   Authors' Addresses                                                48
   Full Copyright Statement                                          50

















Apostolopoulos, et al.        Experimental                      [Page 2]

RFC 2676       QoS Routing Mechanisms and OSPF Extensions    August 1999


1. Introduction

   In this document, we describe a set of proposed additions to the OSPF
   routing protocol (these additions have been implemented on top of the
   GateD [Con] implementation of OSPF V2 [Moy98]) to support Quality-
   of-Service (QoS) routing in IP networks.  Support for QoS routing can
   be viewed as consisting of three major components:

   1. Obtain the information needed to compute QoS paths and select a
      path capable of meeting the QoS requirements of a given request,

   2. Establish the path selected to accommodate a new request,

   3. Maintain the path assigned for use by a given request.

   Although we touch upon aspects related to the last two components,
   the focus of this document is on the first one.  In particular, we
   discuss the metrics required to support QoS, the extension to the
   OSPF link state advertisement mechanism to propagate updates of QoS
   metrics, and the modifications to the path selection to accommodate
   QoS requests.  The goal of the extensions described in this document
   is to improve performance for QoS flows (likelihood to be routed on a
   path capable of providing the requested QoS), with minimal impact on
   the existing OSPF protocol and its current implementation.  Given the
   inherent complexity of QoS routing, achieving this goal obviously
   implies trading-off "optimality" for "simplicity", but we believe
   this to be required in order to facilitate deployment of QoS routing
   capabilities.

   In addition to describing the proposed extensions to the OSPF
   protocol, this document also reports experimental data based on
   performance measurements of an implementation done on the GateD
   platform (see Section 4).

1.1. Overall Framework

   We consider a network (1) that supports both best-effort packets and
   packets with QoS guarantees.  The way in which the network resources
   are split between the two classes is irrelevant, except for the
   assumption that each QoS capable router in the network is able to
   dedicate some of its resources to satisfy the requirements of QoS
   packets.  QoS capable routers are also assumed capable of identifying
   and advertising resources that remain available to new QoS flows.  In
   addition, we limit ourselves to the case where all the routers
   involved support the QoS extensions described in this document, i.e.,
   we do not consider the problem of establishing a route in a
   heterogeneous environment where some routers are QoS-capable and
   others are not.  Furthermore, in this document, we focus on the case



Apostolopoulos, et al.        Experimental                      [Page 3]

RFC 2676       QoS Routing Mechanisms and OSPF Extensions    August 1999


   of unicast flows, although many of the additions we define are
   applicable to multicast flows as well.

   We assume that a flow with QoS requirements specifies them in some
   fashion that is accessible to the routing protocol.  For example,
   this could correspond to the arrival of an RSVP [RZB+97] PATH
   message, whose TSpec is passed to routing together with the
   destination address.  After processing such a request, the routing
   protocol returns the path that it deems the most suitable given the
   flow's requirements.  Depending on the scope of the path selection
   process, this returned path could range from simply identifying the
   best next hop, i.e., a hop-by-hop path selection model, to specifying
   all intermediate nodes to the destination, i.e., an explicit route
   model.  The nature of the path being returned impacts the operation
   of the path selection algorithm as it translates into different
   requirements for constructing and returning the appropriate path
   information.  However, it does not affect the basic operation of the
   path selection algorithm (2).

   For simplicity and also because it is the model currently supported
   in the implementation (see Section 4 for details), in the rest of
   this document we focus on the hop-by-hop path selection model.  The
   additional modifications required to support an explicit routing
   model are discussed in appendix D, but are peripheral to the main
   focus of this document which concentrates on the specific extensions
   to the OPSF protocol to support computation of QoS routes.

   In addition to the problem of selecting a QoS path and possibly
   reserving the corresponding resources, one should note that the
   successful delivery of QoS guarantees requires that the packets of
   the associated "QoS flow" be forwarded on the selected path.  This
   typically requires the installation of corresponding forwarding state
   in the router.  For example, with RSVP [RZB+97] flows a classifier
   entry is created based on the filter specs contained in the RESV
   message.  In the case of a Differentiated Service [KNB98] setting,
   the classifier entry may be based on the destination address (or
   prefix) and the corresponding value of the DS byte.  The mechanisms
   described in this document are at the control path level and are,
   therefore, independent of data path mechanisms such as the packet
   classification method used.  Nevertheless, it is important to notice
   that consistent delivery of QoS guarantees implies stability of the
   data path.  In particular, while it is possible that after a path is
   first selected, network conditions change and result in the
   appearance of "better" paths, such changes should be prevented from
   unnecessarily affecting existing paths.  In particular, switching
   over to a new (and better) path should be limited to specific
   conditions, e.g., when the initial selection turns out to be
   inadequate or extremely "expensive".  This aspect is beyond the scope



Apostolopoulos, et al.        Experimental                      [Page 4]

RFC 2676       QoS Routing Mechanisms and OSPF Extensions    August 1999


   of QoS routing and belongs to the realm of path management, which is
   outside the main focus of this document.  However, because of its
   potentially significant impact on the usefulness of QoS routing, we
   briefly outline a possible approach to path management.

   Avoiding unnecessary changes to QoS paths requires that state
   information be maintained for each QoS path after it has been
   selected.  This state information is used to track the validity of
   the path, i.e., is the current path adequate or should QoS routing be
   queried again to generate a new and potentially better path.  We say
   that a path is "pinned" when its state specifies that QoS routing
   need not be queried anew, while a path is considered "un-pinned"
   otherwise.  The main issue is then to define how, when, and where
   path pinning and un-pinning is to take place, and this will typically
   depend on the mechanism used to request QoS routes.  For example,
   when the RSVP protocol is the mechanism being used, it is desirable
   that path management be kept as synergetic as possible with the
   existing RSVP state management.  In other words, pinning and un-
   pinning of paths should be coordinated with RSVP soft states, and
   structured so as to require minimal changes to RSVP processing rules.
   A broad RSVP-routing interface that enables this is described in
   [GKR97].  Use of such an interface in the context of reserving
   resources along an explicit path with RSVP is discussed in [GLG+97].
   Details of path management and a means for avoiding loops in case of
   hop-by-hop path setup can be found in [GKH97], and are not addressed
   further in this document.

1.2. Simplifying Assumptions

   In order to achieve our goal of minimizing impact to the existing
   protocol and implementation, we impose certain restrictions on the
   range of extensions we initially consider to support QoS. The first
   restriction is on the type of additional (QoS) metrics that will be
   added to Link State Advertisements (LSAs) for the purpose of
   distributing metrics updates.  Specifically, the extensions to LSAs
   that we initially consider, include only available bandwidth and
   delay.  In addition, path selection is itself limited to considering
   only bandwidth requirements.  In particular, the path selection
   algorithm selects paths capable of satisfying the bandwidth
   requirement of flows, while at the same time trying to minimize the
   amount of network resources that need to be allocated, i.e., minimize
   the number of hops used.

   This focus on bandwidth is adequate in most instances, and meant to
   keep initial complexity at an acceptable level.  However, it does not
   fully capture the complete range of potential QoS requirements.  For
   example, a delay-sensitive flow of an interactive application could
   be put on a path using a satellite link, if that link provided a



Apostolopoulos, et al.        Experimental                      [Page 5]

RFC 2676       QoS Routing Mechanisms and OSPF Extensions    August 1999


   direct path and had plenty of unused bandwidth.  This would clearly
   be an undesirable choice.  Our approach to preventing such poor
   choices, is to assign delay-sensitive flows to a "policy" that would
   eliminate from the network all links with high propagation delay,
   e.g., satellite links, before invoking the path selection algorithm.
   In general, multiple policies could be used to capture different
   requirements, each presenting to the path selection algorithm a
   correspondingly pruned network topology, on which the same algorithm
   would be used to generate an appropriate path.  Alternatively,
   different algorithms could be used depending on the QoS requirements
   expressed by an incoming request.  Such extensions are beyond the
   scope of this document, which limits itself to describing the case of
   a single metric, bandwidth.  However, it is worth pointing out that a
   simple extension to the path selection algorithm proposed in this
   document allows us to directly account for delay, under certain
   conditions, when rate-based schedulers are employed, as in the
   Guaranteed Service proposal [SPG97]; details can be found in [GOW97].

   Another important aspect to ensure that introducing support for QoS
   routing has the minimal possible impact, is to develop a solution
   that has the smallest possible computing overhead.  Additional
   computations are unavoidable, but it is desirable to keep the
   computational cost of QoS routing at a level comparable to that of
   traditional routing algorithms.  One possible approach to achieve
   this goal, is to allow pre-computation of QoS routes.  This is the
   method that was chosen for the implementation of the QoS extensions
   to OSPF and is, therefore, the one described in detail in this
   document.  Alternative approaches are briefly reviewed in appendices.
   However, it should be noted that although several alternative path
   selection algorithms are possible, the same algorithm should be used
   consistently within a given routing domain.  This requirement may be
   relaxed when explicit routing is used, as the responsibility for
   selecting a QoS path lies with a single entity, the origin of the
   request, which then ensures consistency even if each router uses a
   different path selection algorithm.  Nevertheless, the use of a
   common path selection algorithm within an AS is recommended, if not
   necessary, for proper operation.

   A last aspect of concern regarding the introduction of QoS routing,
   is to control the overhead associated with the additional link state
   updates caused by more frequent changes to link metrics.  The goal is
   to minimize the amount of additional update traffic without adversely
   affecting the performance of path selection.  In Section 2.2, we
   present a brief discussion of various alternatives that trade
   accuracy of link state information for protocol overhead.  Potential
   enhancements to the path selection algorithm, which seek to
   (directly) account for the inaccuracies in link metrics, are
   described in [GOW97], while a comprehensive treatment of the subject



Apostolopoulos, et al.        Experimental                      [Page 6]

RFC 2676       QoS Routing Mechanisms and OSPF Extensions    August 1999


   can be found in [LO98, GO99].  In Section 4, we also describe the
   design choices made in a reference implementation, to allow future
   extensions and experimentation with different link state update
   mechanisms.

   The rest of this document is structured as follows.  In Section 2, we
   describe the general design choices and mechanisms we rely on to
   support QoS request.  This includes details on the path selection
   metrics, link state update extensions, and the path selection
   algorithm itself.  Section 3 focuses on the specific extensions that
   the OSPF protocol requires, while Section 4 describes their
   implementation in the GateD platform and also presents some
   experimental results.  Section 5 briefly addresses security issues
   that the proposed schemes may raise.  Finally, several appendices
   provide additional material of interest, e.g., alternative path
   selection algorithms and support for explicit routes, but somewhat
   outside the main focus of this document.

2. Path Selection Information and Algorithms

   This section reviews the basic building blocks of QoS path selection,
   namely the metrics on the which the routing algorithm operates, the
   mechanisms used to propagate updates for these metrics, and finally
   the path selection algorithm itself.

2.1. Metrics

   The process of selecting a path that can satisfy the QoS requirements
   of a new flow relies on both the knowledge of the flow's requirements
   and characteristics, and information about the availability of
   resources in the network.  In addition, for purposes of efficiency,
   it is also important for the algorithm to account for the amount of
   resources the network has to allocate to support a new flow.  In
   general, the network prefers to select the "cheapest" path among all
   paths suitable for a new flow, and it may even decide not to accept a
   new flow for which a feasible path exists, if the cost of the path is
   deemed too high.  Accounting for these aspects involves several
   metrics on which the path selection process is based.  They include:

   -  Link available bandwidth:  As mentioned earlier, we currently
      assume that most QoS requirements are derivable from a rate-
      related quantity, termed "bandwidth."  We further assume that
      associated with each link is a maximal bandwidth value, e.g., the
      link physical bandwidth or some fraction thereof that has been set
      aside for QoS flows.  Since for a link to be capable of accepting
      a new flow with given bandwidth requirements, at least that much
      bandwidth must be still available on the link, the relevant link
      metric is, therefore, the (current) amount of available (i.e.,



Apostolopoulos, et al.        Experimental                      [Page 7]

RFC 2676       QoS Routing Mechanisms and OSPF Extensions    August 1999


      unallocated) bandwidth.  Changes in this metric need to be
      advertised as part of extended LSAs, so that accurate information
      is available to the path selection algorithm.

   -  Link propagation delay:  This quantity is meant to identify high
      latency links, e.g., satellite links, which may be unsuitable for
      real-time requests.  This quantity also needs to be advertised as
      part of extended LSAs, although timely dissemination of this
      information is not critical as this parameter is unlikely to
      change (significantly) over time.  As mentioned earlier, link
      propagation delay can be used to decide on the pruning of specific
      links, when selecting a path for a delay sensitive request; also,
      it can be used to support a related extension, as described in
      [GOW97].

   -  Hop-count:  This quantity is used as a measure of the path cost to
      the network.  A path with a smaller number of hops (that can
      support a requested connection) is typically preferable, since it
      consumes fewer network resources.  As a result, the path selection
      algorithm will attempt to find the minimum hop path capable of
      satisfying the requirements of a given request.  Note that
      contrary to bandwidth and propagation delay, hop count is a metric
      that does not affect LSAs, and it is only used implicitly as part
      of the path selection algorithm.

2.2. Advertisement of Link State Information

   The new link metrics identified in the previous section need to be
   advertised across the network, so that each router can compute
   accurate and consistent QoS routes.  It is assumed that each router
   maintains an updated database of the network topology, including the
   current state (available bandwidth and propagation delay) of each
   link.  As mentioned before, the distribution of link state (metrics)
   information is based on extending OSPF mechanisms.  The detailed
   format of those extensions is described in Section 3, but in addition
   to how link state information is distributed, another important
   aspect is when such distribution is to take place.

   One option is to mandate periodic updates, where the period of
   updates is determined based on a tolerable corresponding load on the
   network and the routers.  The main disadvantage of such an approach
   is that major changes in the bandwidth available on a link could
   remain unknown for a full period and, therefore, result in many
   incorrect routing decisions.  Ideally, routers should have the most
   current view of the bandwidth available on all links in the network,
   so that they can make the most accurate decision of which path to
   select.  Unfortunately, this then calls for very frequent updates,
   e.g., each time the available bandwidth of a link changes, which is



Apostolopoulos, et al.        Experimental                      [Page 8]

RFC 2676       QoS Routing Mechanisms and OSPF Extensions    August 1999


   neither scalable nor practical.  In general, there is a trade-off
   between the protocol overhead of frequent updates and the accuracy of
   the network state information that the path selection algorithm
   depends on.  We outline next a few possible link state update
   policies, which strike a practical compromise.

   The basic idea is to trigger link state advertisements only when
   there is a significant change in the value of metrics since the last
   advertisement.  The notion of significance of a change can be based
   on an "absolute" scale or a "relative" one.  An absolute scale means
   partitioning the range of values that a metric can take into
   equivalence classes and triggering an update whenever the metric
   changes sufficiently to cross a class boundary (3).  A relative
   scale, on the other hand, triggers updates when the percentage change
   in the metric value exceeds a predefined threshold.  Independent of
   whether a relative or an absolute change trigger mechanism is used, a
   periodic trigger constraint can also be added.  This constraint can
   be in the form of a hold-down timer, which is used to force a minimum
   spacing between consecutive updates.  Alternatively, a transmit timer
   can also be used to ensure the transmission of an update after a
   certain time has expired.  Such a feature can be useful if link state
   updates advertising bandwidth changes are sent unreliably.  The
   current protocol extensions described in Section 3 as well as the
   implementation of Section 4 do not consider such an option as metric
   updates are sent using the standard, and reliable, OSPF flooding
   mechanism.  However, this is clearly an extension worth considering
   as it can help lower substantially the protocol overhead associated
   with metrics updates.

   In both the relative and absolute change approaches, the metric value
   advertised in an LSA can be either the actual or a quantized value.
   Advertising the actual metric value is more accurate and, therefore,
   preferable when metrics are frequently updated.  On the other hand,
   when updates are less frequent, e.g., because of a low sensitivity
   trigger or the use of hold-down timers, advertising quantized values
   can be of benefit.  This is because it can help increase the number
   of equal cost paths and, therefore, improve robustness to metrics
   inaccuracies.  In general, there is a broad space of possible trade-
   offs between accuracy and overhead and selecting an appropriate
   design point is difficult and depends on many parameters (see
   [AGKT98] for a more detailed discussion of these issues).  As a
   result, in order to help acquire a better understanding of these
   issues, the implementation described in Section 4 supports a range of
   options that allow exploration of the available design space.  In
   addition, Section 4 also reports experimental data on the traffic
   load and processing overhead generated by links state updates for
   different configurations.




Apostolopoulos, et al.        Experimental                      [Page 9]

RFC 2676       QoS Routing Mechanisms and OSPF Extensions    August 1999


2.3. Path Selection

   There are two major aspects to computing paths for QoS requests.  The
   first is the actual path selection algorithm itself, i.e., which
   metrics and criteria it relies on.  The second is when the algorithm
   is actually invoked.

   The topology on which the algorithm is run is, as with the standard
   OSPF path selection, a directed graph where vertices (4) consist of
   routers and networks (transit vertices) as well as stub networks
   (non-transit vertices).  When computing a path, stub networks are
   added as a post-processing step, which is essentially similar to what
   is done with the current OSPF routing protocol.  The optimization
   criteria used by the path selection are reflected in the costs
   associated with each interface in the topology and how those costs
   are accounted for in the algorithm itself.  As mentioned before, the
   cost of a path is a function of both its hop count and the amount of
   available bandwidth.  As a result, each interface has associated with
   it a metric, which corresponds to the amount of bandwidth that
   remains available on this interface.  This metric is combined with
   hop count information to provide a cost value, whose goal is to pick
   a path with the minimum possible number of hops among those that can
   support the requested bandwidth.  When several such paths are
   available, the preference is for the path whose available bandwidth
   (i.e., the smallest value on any of the links in the path) is
   maximal.  The rationale for the above rule is the following:  we
   focus on feasible paths (as accounted by the available bandwidth
   metric) that consume a minimal amount of network resources (as
   accounted by the hop-count metric); and the rule for selecting among
   these paths is meant to balance load as well as maximize the
   likelihood that the required bandwidth is indeed available.

   It should be noted that standard routing algorithms are typically
   single objective optimizations, i.e., they may minimize the hop-
   count, or maximize the path bandwidth, but not both.  Double
   objective path optimization is a more complex task, and, in general,
   it is an intractable problem [GJ79].  Nevertheless, because of the
   specific nature of the two objectives being optimized (bandwidth and
   hop count), the complexity of the above algorithm is competitive with
   even that of standard single-objective algorithms.  For readers
   interested in a thorough treatment of the topic, with insights into
   the connection between the different algorithms, linear algebra and
   modification of metrics, [Car79] is recommended.

   Before proceeding with a more detailed description of the path
   selection algorithm itself, we briefly review the available options
   when it comes to deciding when to invoke the algorithm.  The two main
   options are:  1) to perform on-demand computations, that is, trigger



Apostolopoulos, et al.        Experimental                     [Page 10]

RFC 2676       QoS Routing Mechanisms and OSPF Extensions    August 1999


   a computation for each new request, and 2) to use some form of pre-
   computation.  The on-demand case involves no additional issues in
   terms of when computations should be triggered, but running the path
   selection algorithm for each new request can be computationally
   expensive (see [AT98] for a discussion on this issue).  On the other
   hand, pre-computing paths amortizes the computational cost over
   multiple requests, but each computation instance is usually more
   expensive than in the on-demand case (paths are computed to all
   destinations and for all possible bandwidth requests rather than for
   a single destination and a given bandwidth request).  Furthermore,
   depending on how often paths are recomputed, the accuracy of the
   selected paths may be lower.  In this document, we primarily focus on
   the case of pre-computed paths, which is also the only method
   currently supported in the reference implementation described in
   Section 4.  In this case, clearly, an important issue is when such
   pre-computation should take place.  The two main options we consider
   are periodic pre-computations and pre-computations after a given (N)
   number of updates have been received.  The former has the benefit of
   ensuring a strict bound on the computational load associated with
   pre-computations, while the latter can provide for a more responsive
   solution (5).  Section 4 provides some experimental results comparing
   the performance and cost of periodic pre-computations for different
   period values.

2.3.1. Path Computation Algorithm

   This section describes a path selection algorithm, which for a given
   network topology and link metrics (available bandwidth), pre-computes
   all possible QoS paths, while maintaining a reasonably low
   computational complexity.  Specifically, the algorithm pre-computes
   for any destination a minimum hop count path with maximum bandwidth,
   and has a computational complexity comparable to that of a standard
   Bellman-Ford shortest path algorithm.  The Bellman-Ford (BF) shortest
   path algorithm is adapted to compute paths of maximum available
   bandwidth for all hop counts.  It is a property of the BF algorithm
   that, at its h-th iteration, it identifies the optimal (in our
   context:  maximal bandwidth) path between the source and each
   destination, among paths of at most h hops.  In other words, the cost
   of a path is a function of its available bandwidth, i.e., the
   smallest available bandwidth on all links of the path, and finding a
   minimum cost path amounts to finding a maximum bandwidth path.
   However, because the BF algorithm progresses by increasing hop count,
   it essentially provides for free the hop count of a path as a second
   optimization criteria.

   Specifically, at the kth (hop count) iteration of the algorithm, the
   maximum bandwidth available to all destinations on a path of no more
   than k hops is recorded (together with the corresponding routing



Apostolopoulos, et al.        Experimental                     [Page 11]

RFC 2676       QoS Routing Mechanisms and OSPF Extensions    August 1999


   information).  After the algorithm terminates, this information
   provides for all destinations and bandwidth requirements, the path
   with the smallest possible number of hops and sufficient bandwidth to
   accommodate the new request.  Furthermore, this path is also the one
   with the maximal available bandwidth among all the feasible paths
   with at most these many hops.  This is because for any hop count, the
   algorithm always selects the one with maximum available bandwidth.

   We now proceed with a more detailed description of the algorithm and
   the data structure used to record routing information, i.e., the QoS
   routing table that gets built as the algorithm progresses (the
   pseudo-code for the algorithm can be found in Appendix A).  As
   mentioned before, the algorithm operates on a directed graph
   consisting only of transit vertices (routers and networks), with
   stub-networks subsequently added to the path(s) generated by the
   algorithm.  The metric associated with each edge in the graph is the
   bandwidth available on the corresponding interface.  Let us denote by
   b(n;m) the available bandwidth on the link from node n to m.  The
   vertex corresponding to the router where the algorithm is being run,
   i.e., the computing router, is denoted as the "source node" for the
   purpose of path selection.  The algorithm proceeds to pre-compute
   paths from this source node to all possible destination networks and
   for all possible bandwidth values.  At each (hop count) iteration,
   intermediate results are recorded in a QoS routing table, which has
   the following structure:

The QoS routing table:

   -  a KxH matrix, where K is the number of destinations (vertices in
      the graph) and H is the maximal allowed (or possible) number of
      hops for a path.

   -  The (n;h) entry is built during the hth iteration (hop count
      value) of the algorithm, and consists of two fields:

         *  bw:  the maximum available bandwidth, on a path of at most h
            hops between the source node (router) and destination node
            n;

         *  neighbor:  this is the routing information associated with
            the h (or less) hops path to destination node n, whose
            available bandwidth is bw.  In the context of hop-by-hop
            path selection (6), the neighbor information is simply the
            identity of the node adjacent to the source node on that
            path.  As a rule, the "neighbor" node must be a router and
            not a network, the only exception being the case where the
            network is the destination node (and the selected path is
            the single edge interconnecting the source to it).



Apostolopoulos, et al.        Experimental                     [Page 12]

RFC 2676       QoS Routing Mechanisms and OSPF Extensions    August 1999


   Next, we provide additional details on the operation of the algorithm
   and how the entries in the routing table are updated as the algorithm
   proceeds.  For simplicity, we first describe the simpler case where
   all edges count as "hops," and later explain how zero-hop edges are
   handled.  Zero-hop edges arise in the case of transit networks
   vertices, where only one of the two incoming and outgoing edges
   should be counted in the hop count computation, as they both
   correspond to the same physical hop.  Accounting for this aspect
   requires distinguishing between network and router nodes, and the
   steps involved are detailed later in this section as well as in the
   pseudo-code of Appendix A.

   When the algorithm is invoked, the routing table is first initialized
   with all bw fields set to 0 and neighbor fields cleared.  Next, the
   entries in the first column (which corresponds to one-hop paths) of
   the neighbors of the computing router are modified in the following
   way:  the bw field is set to the value of the available bandwidth on
   the direct edge from the source.  The neighbor field is set to the
   identity of the neighbor of the computing router, i.e., the next
   router on the selected path.

   Afterwards, the algorithm iterates for at most H iterations
   (considering the above initial iteration as the first).  The value of
   H could be implicit, i.e., the diameter of the network or, in order
   to better control the worst case complexity, it can be set explicitly
   thereby limiting path lengths to at most H hops.  In the latter case,
   H must be assigned a value larger than the length of the minimum
   hop-count path to any node in the graph.

   At iteration h, we first copy column h-1  into column h.  In
   addition, the algorithm keeps a list of nodes that changed their bw
   value in the previous iteration, i.e., during the (h-1)-th iteration.
   The algorithm then looks at each link (n;m) where n is a node whose
   bw value changed in the previous iteration, and checks the maximal
   available bandwidth on an (at most) h-hop path to node m whose final
   hop is that link.  This amounts to taking the minimum between the bw
   field in entry (n;h-1) and the link metric value b(n;m) kept in the
   topology database.  If this value is higher than the present value of
   the bw field in entry (m;h), then a better (larger bw value) path has
   been found for destination m and with at most h hops.  The bw field
   of entry (m;h) is then updated to reflect this new value.  In the
   case of hop-by-hop routing, the neighbor field of entry (m;h) is set
   to the same value as in entry (n;h-1).  This records the identity of
   the first hop (next hop from the source) on the best path identified
   thus far for destination m and with h (or less) hops.






Apostolopoulos, et al.        Experimental                     [Page 13]

RFC 2676       QoS Routing Mechanisms and OSPF Extensions    August 1999


   As mentioned earlier, extending the above algorithm to handle zero-
   hop edges is needed due to the possible use of multi-access networks,
   e.g., T/R, E/N, etc., to interconnect routers.  Such entities are
   also represented by means of a vertex in the OSPF topology, but a
   network connecting two routers should clearly be considered as a
   single hop path rather than a two hop path.  For example, consider
   three routers A, B, and C connected over an Ethernet network N, which
   the OSPF topology represents as in Figure 1.

                           A----N----B
                                |
                                |
                                C



                        Figure 1: Zero-Hop Edges


   In the example of Figure 1, although there are directed edges in both
   directions, an edge from the network to any of the three routers must
   have zero "cost", so that it is not counted twice.  It should be
   noted that when considering such environments in the context of QoS
   routing, it is assumed that some entity is responsible for
   determining the "available bandwidth" on the network, e.g., a subnet
   bandwidth manager.  The specification and operation of such an entity
   is beyond the scope of this document.

   Accommodating zero-hop edges in the context of the path selection
   algorithm described above is done as follows:  At each iteration h
   (starting with the first), whenever an entry (m;h) is modified, it is
   checked whether there are zero-cost edges (m;k) emerging from node m.
   This is the case when m is a transit network.  In that case, we
   attempt to further improve the entry of node k within the current
   iteration, i.e., entry (k;h) (rather than entry (k;h+1)), since the
   edge (m;k) should not count as an additional hop.  As with the
   regular operation of the algorithm, this amounts to taking the
   minimum between the bw field in entry (m;h) and the link metric value
   b(m;k) kept in the topology database (7).  If this value is higher
   than the present value of the bw field in entry (k;h), then the bw
   field of entry (k;h) is updated to this new value.  In the case of
   hop-by-hop routing, the neighbor field of entry (k;h) is set, as
   usual, to the same value as in entry (m;h) (which is also the value
   in entry (n;h-1)).







Apostolopoulos, et al.        Experimental                     [Page 14]

RFC 2676       QoS Routing Mechanisms and OSPF Extensions    August 1999


   Note that while for simplicity of the exposition, the issue of equal
   cost, i.e., same hop count and available bandwidth, is not detailed
   in the above description, it can be easily supported.  It only
   requires that the neighbor field be expanded to record the list of
   next (previous) hops, when multiple equal cost paths are present.

Addition of Stub Networks

   As was mentioned earlier, the path selection algorithm is run on a
   graph whose vertices consist only of routers and transit networks and
   not stub networks.  This is intended to keep the computational
   complexity as low as possible as stub networks can be added
   relatively easily through a post-processing step.  This second
   processing step is similar to the one used in the current OSPF
   routing table calculation [Moy98], with some differences to account
   for the QoS nature of routes.

   Specifically, after the QoS routing table has been constructed, all
   the router vertices are again considered.  For each router, stub
   networks whose links appear in the router's link advertisements will
   be processed to determine QoS routes available to them.  The QoS
   routing information for a stub network is similar to that of routers
   and transit networks and consists of an extension to the QoS routing
   table in the form of an additional row.  The columns in that new row
   again correspond to paths of different hop counts, and contain both
   bandwidth and next hop information.  We also assume that an available
   bandwidth value has been advertised for the stub network.  As before,
   how this value is determined is beyond the scope of this document.
   The QoS routes for a stub network S are constructed as follows:

   Each entry in the row corresponding to stub network S has its bw(s)
   field initialized to zero and its neighbor set to null.  When a stub
   network S is found in the link advertisement of router V, the value
   bw(S,h) in the hth column of the row corresponding to stub network S
   is updated as follows:

      bw(S,h) = max ( bw(S,h) ; min ( bw(V,h) , b(V,S) ) ),

   where bw(V,h) is the bandwidth value of the corresponding column for
   the QoS routing table row associated with router V, i.e., the
   bandwidth available on an h hop path to V, and b(V,S) is the
   advertised available bandwidth on the link from V to S.  The above
   expression essentially states that the bandwidth of a h hop path to
   stub network S is updated using a path through router V, only if the
   minimum of the bandwidth of the h hop path to V and the bandwidth on
   the link between V and S is larger than the current value.





Apostolopoulos, et al.        Experimental                     [Page 15]

RFC 2676       QoS Routing Mechanisms and OSPF Extensions    August 1999


   Update of the neighbor field proceeds similarly whenever the
   bandwidth of a path through V is found to be larger than or equal to
   the current value.  If it is larger, then the neighbor field of V in
   the corresponding column replaces the current neighbor field of S.
   If it is equal, then the neighbor field of V in the corresponding
   column is concatenated with the existing field for S, i.e., the
   current set of neighbors for V is added to the current set of
   neighbors for S.

Extracting Forwarding Information from Routing Table

   When the QoS paths are precomputed, the forwarding information for a
   flow with given destination and bandwidth requirement needs to be
   extracted from the routing table.  The case of hop-by-hop routing is
   simpler than that of explicit routing.  This is because, only the
   next hop needs to be returned instead of an explicit route.

   Specifically, assume a new request to destination, say, d, and with
   bandwidth requirements B.  The index of the destination vertex
   identifies the row in the QoS routing table that needs to be checked
   to generate a path.  Assuming that the QoS routing table was
   constructed using the Bellman-Ford algorithm presented later in this
   section, the search then proceeds by increasing index (hop) count
   until an entry is found, say at hop count or column index of h, with
   a value of the bw field which is equal to or larger than B.  This
   entry points to the initial information identifying the selected
   path.

   If the path computation algorithm stores multiple equal cost paths,
   then some degree of load balancing can be achieved at the time of
   path selection.  A next hop from the list of equivalent next hops can
   be chosen in a round robin manner, or randomly with a probability
   that is weighted by the actual available bandwidth on the local
   interface.  The latter is the method used in the implementation
   described in Section 4.

   The case of explicit routing is discussed in Appendix D.

3. OSPF Protocol Extensions

   As stated earlier, one of our goals is to limit the additions to the
   existing OSPF V2 protocol, while still providing the required level
   of support for QoS based routing.  To this end, all of the existing
   OSPF mechanisms, data structures, advertisements, and data formats
   remain in place.  The purpose of this section of the document is to
   describe the extensions to the OSPF protocol needed to support QoS as
   outlined in the previous sections.




Apostolopoulos, et al.        Experimental                     [Page 16]

RFC 2676       QoS Routing Mechanisms and OSPF Extensions    August 1999


3.1. QoS -- Optional Capabilities

   The OSPF Options field is present in OSPF Hello packets, Database
   Description packets and all LSAs.  The Options field enables OSPF
   routers to support (or not support) optional capabilities, and to
   communicate their capability level to other OSPF routers.  Through
   this mechanism, routers of differing capabilities can be mixed within
   an OSPF routing domain.  Currently, the OSPF standard [Moy98]
   specifies the following 5 bits in the options octet:

           +-----------------------------------------------+
           |  *  |  *  | DC  |  EA | N/P |  MC |  E  |  *  |
           +-----------------------------------------------+

   Note that the least significant bit (`T' bit) that was used to
   indicate TOS routing capability in the older OSPF specification
   [Moy94] has been removed.  However, for backward compatibility with
   previous versions of the OSPF specification, TOS-specific information
   can be included in router-LSAs, summary-LSAs and AS-external-LSAs.

   We propose to reclaim the `T' bit as an indicator of router's QoS
   routing capability and refer to it as the `Q' bit.  In fact, QoS
   capability can be viewed as an extension of the TOS-capabilities and
   QoS routing as a form of TOS-based routing.  A router sets this bit
   in its hello packets to indicate that it is capable of supporting
   such routing.  When this bit is set in a router or summary links link
   state advertisement, it means that there are QoS fields to process in
   the packet.  When this bit is set in a network link state
   advertisement it means that the network described in the
   advertisement is QoS capable.

   We need to be careful in this approach so as to avoid confusing any
   old style (i.e., RFC 1583 based) TOS routing implementations.  The
   TOS metric encoding rules of QoS fields introduced further in this
   section will show how this is achieved.  Additionally, unlike the RFC
   1583 specification that unadvertised TOS metrics be treated to have
   same cost as TOS 0, for the purpose of computing QOS routes,
   unadvertised TOS metrics (on a hop) indicate lack of connectivity for
   the specific TOS metrics (for that hop).

3.2. Encoding Resources as Extended TOS

   Introduction of QoS should ideally not influence the compatibility
   with existing OSPFv2 routers.  To achieve this goal, necessary
   extensions in packet formats must be defined in a way that either is
   understood by OSPFv2 routers, ignored, or in the worst case
   "gracefully" misinterpreted.  Encoding of QoS metrics in the TOS
   field which fortunately enough is longer in OSPF packets than



Apostolopoulos, et al.        Experimental                     [Page 17]

RFC 2676       QoS Routing Mechanisms and OSPF Extensions    August 1999


   officially defined in [Alm92], allows us to mimic the new facility as
   extended TOS capability.  OSPFv2 routers will either disregard these
   definitions or consider those unspecified.  Specific precautions are
   taken to prevent careless OSPF implementations from influencing
   traditional TOS routers (if any) when misinterpreting the QoS
   extensions.

   For QoS resources, 32 combinations are available through the use of
   the fifth bit in TOS fields contained in different LSAs.  Since
   [Alm92] defines TOS as being four bits long, this definition never
   conflicts with existing values.  Additionally, to prevent naive
   implementations that do not take all bits of the TOS field in OSPF
   packets into considerations, the definitions of the `QoS encodings'
   is aligned in their semantics with the TOS encoding.  Only bandwidth
   and delay are specified as of today and their values map onto
   `maximize throughput' and `minimize delay' if the most significant
   bit is not taken into account.  Accordingly, link reliability and
   jitter could be defined later if necessary.

        OSPF encoding   RFC 1349 TOS values
        ___________________________________________
        0               0000 normal service
        2               0001 minimize monetary cost
        4               0010 maximize reliability
        6               0011
        8               0100 maximize throughput
        10              0101
        12              0110
        14              0111
        16              1000 minimize delay
        18              1001
        20              1010
        22              1011
        24              1100
        26              1101
        28              1110
        30              1111














Apostolopoulos, et al.        Experimental                     [Page 18]

RFC 2676       QoS Routing Mechanisms and OSPF Extensions    August 1999


        OSPF encoding   `QoS encoding values'

        -------------------------------------------
        32             10000
        34             10001
        36             10010
        38             10011
        40             10100 bandwidth
        42             10101
        44             10110
        46             10111
        48             11000 delay
        50             11001
        52             11010
        54             11011
        56             11100
        58             11101
        60             11110
        62             11111

        Representing TOS and QoS in OSPF.

3.2.1. Encoding bandwidth resource

   Given the fact that the actual metric field in OSPF packets only
   provides 16 bits to encode the value used and that links supporting
   bandwidth ranging into Gbits/s are becoming reality, linear
   representation of the available resource metric is not feasible.  The
   solution is exponential encoding using appropriately chosen implicit
   base value and number bits for encoding mantissa and the exponent.
   Detailed considerations leading to the solution described are not
   presented here but can be found in [Prz95].

   Given a base of 8, the 3 most significant bits should be reserved for
   the exponent part and the remaining 13 for the mantissa.  This allows
   a simple comparison for two numbers encoded in this form, which is
   often useful during implementation.

   The following table shows bandwidth ranges covered when using
   different exponents and the granularity of possible reservations.











Apostolopoulos, et al.        Experimental                     [Page 19]

RFC 2676       QoS Routing Mechanisms and OSPF Extensions    August 1999


        exponent
        value x         range (2^13-1)*8^x      step 8^x
        -------------------------------------------------
        0               8,191                   1
        1               65,528                  8
        2               524,224                 64
        3               4,193,792               512
        4               33,550,336              4,096
        5               268,402,688             32,768
        6               2,147,221,504           262,144
        7               17,177,772,032          2,097,152

          Ranges of Exponent Values for 13 bits,
               base 8 Encoding, in Bytes/s

   The bandwidth encoding rule may be summarized as: "represent
   available bandwidth in 16 bit field as a 3 bit exponent (with assumed
   base of 8) followed by a 13 bit mantissa as shown below and advertise
   2's complement of the above representation."

        0       8       16
        |       |       |
        -----------------
       |EXP| MANT        |
        -----------------

   Thus, the above encoding advertises a numeric value that is

      2^16 -1 -(exponential encoding of the available bandwidth):

   This has the property of advertising a higher numeric value for lower
   available bandwidth, a notion that is consistent with that of cost.

   Although it may seem slightly pedantic to insist on the property that
   less bandwidth is expressed higher values, it has, besides
   consistency, a robustness aspect in it.  A router with a poor OSPF
   implementation could misuse or misunderstand bandwidth metric as
   normal administrative cost provided to it and compute spanning trees
   with a "normal" Dijkstra.  The effect of a heavily congested link
   advertising numerically very low cost could be disastrous in such a
   scenario.  It would raise the link's attractiveness for future
   traffic instead of lowering it.  Evidence that such considerations
   are not speculative, but similar scenarios have been encountered, can
   be found in [Tan89].







Apostolopoulos, et al.        Experimental                     [Page 20]

RFC 2676       QoS Routing Mechanisms and OSPF Extensions    August 1999


   Concluding with an example, assume a link with bandwidth of 8 Gbits/s
   = 1024^3 Bytes/s, its encoding would consist of an exponent value of
   6 since 1024^3= 4,096*8^6, which would then have a granularity of 8^6
   or approx. 260 kBytes/s.  The associated binary representation would
   then be %(110) 0 1000 0000 0000% or 53,248 (8).  The bandwidth cost
   (advertised value) of this link when it is idle, is then the 2's
   complement of the above binary representation, i.e., %(001) 1 0111
   1111 1111% which corresponds to a decimal value of (2^16 - 1) -
   53,248 = 12,287.  Assuming now a current reservation level of 6;400
   Mbits/s = 200 * 1024^2, there remains 1;600 Mbits/s of available
   bandwidth on the link.  The encoding of this available bandwidth of
   1'600 Mbits/s is 6,400 * 8^5, which corresponds to a granularity of
   8^5 or approx. 30 kBytes/s, and has a binary representation of %(101)
   1 1001 0000 0000% or decimal value of 47,360.  The advertised cost of
   the link with this load level, is then %(010) 0 0110 1111 1111%, or
   (2^16-1) -47,360 = 18,175.

   Note that the cost function behaves as it should, i.e., the less
   bandwidth is available on a link, the higher the cost and the less
   attractive the link becomes.  Furthermore, the targeted property of
   better granularity for links with less bandwidth available is also
   achieved.  It should, however, be pointed out that the numbers given
   in the above examples match exactly the resolution of the proposed
   encoding, which is of course not always the case in practice.  This
   leaves open the question of how to encode available bandwidth values
   when they do not exactly match the encoding.  The standard practice
   is to round it to the closest number.  Because we are ultimately
   interested in the cost value for which it may be better to be
   pessimistic than optimistic, we choose to round costs up and,
   therefore, bandwidth down.

3.2.2. Encoding Delay

   Delay is encoded in microseconds using the same exponential method as
   described for bandwidth except that the base is defined to be 4
   instead of 8.  Therefore, the maximum delay that can be expressed is
   (2^13-1) *4^7 i.e., approx. 134 seconds.

3.3. Packet Formats

   Given the extended TOS notation to account for QoS metrics, no
   changes in packet formats are necessary except for the
   (re)introduction of T-bit as the Q-bit in the options field.  Routers
   not understanding the Q-bit should either not consider the QoS
   metrics distributed or consider those as `unknown' TOS.






Apostolopoulos, et al.        Experimental                     [Page 21]

RFC 2676       QoS Routing Mechanisms and OSPF Extensions    August 1999


   To support QoS, there are additions to two Link State Advertisements,
   the Router Links Advertisement and the Summary Links Advertisement.
   As stated above, a router identifies itself as supporting QoS by
   setting the Q-bit in the options field of the Link State Header.
   When a router that supports QoS receives either the Router Links or
   Summary Links Advertisement, it should parse the QoS metrics encoded
   in the received Advertisement.

3.4. Calculating the Inter-area Routes

   This document proposes a very limited use of OSPF areas, that is, it
   is assumed that summary links advertisements exist for all networks
   in the area.  This document does not discuss the problem of providing
   support for area address ranges and QoS metric aggregation.  This is
   left for further studies.

3.5. Open Issues

   Support for AS External Links, Virtual Links, and incremental updates
   for summary link advertisements are not addressed in this document
   and are left for further study.  For Virtual Links that do exist, it
   is assumed for path selection that these links are non-QoS capable
   even if the router advertises QoS capability.  Also, as stated
   earlier, this document does not address the issue of non-QoS routers
   within a QoS domain.

4. A Reference Implementation based on GateD

   In this section we report on the experience gained from implementing
   the pre-computation based approach of Section 2.3.1 in the GateD
   [Con] environment.  First, we briefly introduce the GateD
   environment, and then present some details on how the QoS extensions
   were implemented in this environment.  Finally, we discuss issues
   that arose during the implementation effort and present some
   measurement based results on the overhead that the QoS extensions
   impose on a QoS capable router and a network of QoS routers.  For
   further details on the implementation study, the reader is referred
   to [AGK99].  Additional performance evaluation based on simulations
   can be found in [AGKT98].

4.1. The Gate Daemon (GateD) Program

   GateD [Con] is a popular, public domain (9) program that provides a
   platform for implementing routing protocols on hosts running the Unix
   operating system.  The distribution of the GateD software also
   includes implementations of many popular routing protocols, including
   the OSPF protocol.  The GateD environment offers a variety of
   services useful for implementing a routing protocol.  These services



Apostolopoulos, et al.        Experimental                     [Page 22]

RFC 2676       QoS Routing Mechanisms and OSPF Extensions    August 1999


   include a) support for creation and management of timers, b) memory
   management, c) a simple scheduling mechanism, d) interfaces for
   manipulating the host's routing table and accessing the network, and
   e) route management (e.g., route prioritization and route exchange
   between protocols).

   All GateD processing is done within a single Unix process, and
   routing protocols are implemented as one or several tasks.  A GateD
   task is a collection of code associated with a Unix socket.  The
   socket is used for the input and output requirements of the task.
   The main loop of GateD contains, among other operations, a select()
   call over all task sockets to determine if any read/write or error
   conditions occurred in any of them.  GateD implements the OSPF link
   state database using a radix tree for fast access to individual link
   state records.  In addition, link state records for neighboring
   network elements (such as adjacent routers) are linked together at
   the database level with pointers.  GateD maintains a single routing
   table that contains routes discovered by all the active routing
   protocols.  Multiple routes to the same destination are prioritized
   according to a set of rules and administrative preferences and only a
   single route is active per destination.  These routes are
   periodically downloaded in the host's kernel forwarding table.

4.2. Implementing the QoS Extensions of OSPF

4.2.1. Design Objectives and Scope

   One of our major design objectives was to gain substantial experience
   with a functionally complete QoS routing implementation while
   containing the overall implementation complexity.  Thus, our
   architecture was modular and aimed at reusing the existing OSPF code
   with only minimal changes.  QoS extensions were localized to specific
   modules and their interaction with existing OSPF code was kept to a
   minimum.  Besides reducing the development and testing effort, this
   approach also facilitated experimentation with different alternatives
   for implementing the QoS specific features such as triggering
   policies for link state updates and QoS route table computation.
   Several of the design choices were also influenced by our assumptions
   regarding the core functionalities that an early prototype
   implementation of QoS routing must demonstrate.  Some of the
   important assumptions/requirements are:

   -  Support for only hop-by-hop routing.  This affected the path
      structure in the QoS routing table as it only needs to store next
      hop information.  As mentioned earlier, the structure can be
      easily extended to allow construction of explicit routes.





Apostolopoulos, et al.        Experimental                     [Page 23]

RFC 2676       QoS Routing Mechanisms and OSPF Extensions    August 1999


   -  Support for path pre-computation.  This required the creation of a
      separate QoS routing table and its associated path structure, and
      was motivated by the need to minimize processing overhead.

   -  Full integration of the QoS extensions into the GateD framework,
      including configuration support, error logging, etc.  This was
      required to ensure a fully functional implementation that could be
      used by others.

   -  Ability to allow experimentation with different approaches, e.g.,
      use of different update and pre-computation triggering policies
      with support for selection and parameterization of these policies
      from the GateD configuration file.

   -  Decoupling from local traffic and resource management components,
      i.e., packet classifiers and schedulers and local call admission.
      This is supported by providing an API between QoS routing and the
      local traffic management module, which hides all internal details
      or mechanisms.  Future implementations will be able to specify
      their own mechanisms for this module.

   -  Interface to RSVP. The implementation assumes that RSVP [RZB+97]
      is the mechanism used to request routes with specific QoS
      requirements.  Such requests are communicated through an interface
      based on [GKR97], and used the RSVP code developed at ISI, version
      4.2a2 [RZB+97].

   In addition, our implementation also relies on several of the
   simplifying assumptions made earlier in this document, namely:

   -  The scope of QoS route computation is currently limited to a
      single area.

   -  All routers within the area are assumed to run a QoS enabled
      version of OSPF, i.e., inter-operability with non-QoS aware
      versions of the OSPF protocol is not considered.

   -  All interfaces on a router are assumed to be QoS capable.

4.2.2. Architecture

   The above design decisions and assumptions resulted in the
   architecture shown in Figure 2.  It consists of three major
   components:  the signaling component (RSVP in our case); the QoS
   routing component; and the traffic manager.  In the rest of this
   section we concentrate on the structure and operation of the QoS
   routing component.  As can be seen in Figure 2, the QoS routing
   extensions are further divided into the following modules:



Apostolopoulos, et al.        Experimental                     [Page 24]

RFC 2676       QoS Routing Mechanisms and OSPF Extensions    August 1999


   -  Update trigger module determines when to advertise local link
      state updates.  This module implements a variety of triggering
      policies:  periodic, threshold based triggering, and class based
      triggering.  This module also implements a hold-down timer that
      enforces minimum spacing between two consecutive update
      triggerings from the same node.

   -  Pre-computation trigger module determines when to perform QoS path
      pre-computation.  So far, this module implements only periodic
      pre-computation triggering.

   -  Path pre-computation module computes the QoS routing table based
      on the QoS specific link state information as described in Section
      2.3.1.

   -  Path selection and management module selects a path for a request
      with particular QoS requirements, and manages it once selected,
      i.e., reacts to link or reservation failures.  Path selection is
      performed as described in Section 2.3.1.  Path management
      functionality is not currently supported.

   -  QoS routing table module implements the QoS specific routing
      table, which is maintained independently of the other GateD
      routing tables.

   -  Tspec mapping module maps request requirements expressed in the
      form of RSVP Tspecs and Rspecs into the bandwidth requirements
      that QoS routing uses.

4.3. Major Implementation Issues

   Mapping the above design to the framework of the GateD implementation
   of OSPF led to a number of issues and design decisions.  These issues
   mainly fell under two categories:  a) interoperation of the QoS
   extensions with pre-existing similar OSPF mechanisms, and b)
   structure, placement, and organization of the QoS routing table.
   Next, we briefly discuss these issues and justify the resulting
   design decisions.













Apostolopoulos, et al.        Experimental                     [Page 25]

RFC 2676       QoS Routing Mechanisms and OSPF Extensions    August 1999


                    +--------------------------------------------------+
                    |              +-----------------------------+     |
                    |              | QoS Route Table Computation |     |
                    |              +-----------------------------+     |
                    |                 |                    |           |
                    |                 V                    |           |
                    |  +-----------------+                 |           |
       +-------------->| QoS Route Table |                 |           |
       |            |  +-----------------+                 |           |
       |            |                                      |           |
       |            |  +----------------------+     +---------------+  |
       |            |  | Core OSPF Functions  |     | Precomputation|  |
       |            |  |        +             |     | Trigger       |  |
       |            |  | (Enhanced) Topology  |     +---------------+  |
       |            |  | Data Base            |             |          |
       |            |  +----------------------+             |          |
       |            |         |           |                 |          |
       |            |         |       +----------------------------+   |
       |            |         |       | Receive and update QoS-LSA |   |
       |            |         |       +----------------------------+   |
       |            |         |                             |          |
       |            |         |                    +----------------+  |
       |            |         |                    | Local Interface|  |
       |            |         |                    | Status Monitor |  |
       |            |         |                    +----------------+  |
+----------------+  |         |                            |           |
| Path Selection |  |    +--------------+          +----------------+  |
| & Management   |  |    | Build and    |          | Link State     |  |
+----------------+  |    | Send QoS-LSA |----------| Update Trigger |  |
       |            |    +--------------+          +----------------+  |
+----------------+  |                                           |      |
| QoS Parameter  |  |                                           |      |
| Mapping        |  |        OSPF with QoS Routing Extensions   |      |
|----------------+  +-------------------------------------------|------+
       |                                                        |
+----------------+                                          +----------+
| QoS Route      |                                          | Local    |
| Request Client |<---------------------------------------->| Resource |
| (e.g. RSVP)    |                                          | Manager  |
+----------------+                                          +----------+



                  Figure 2: The software architecture







Apostolopoulos, et al.        Experimental                     [Page 26]

RFC 2676       QoS Routing Mechanisms and OSPF Extensions    August 1999


   The ability to trigger link state updates in response to changes in
   bandwidth availability on interfaces is an essential component of the
   QoS extensions.  Mechanisms for triggering these updates and
   controlling their rate have been mentioned in Section 2.2.  In
   addition, OSPF implements its own mechanism for triggering link state
   updates as well as its own hold down timer, which may be incompatible
   with what is used for the QoS link state updates.  We handle such
   potential conflicts as follows.  First, since OSPF triggers updates
   on a periodic basis with low frequency, we expect these updates to be
   only a small part of the total volume of updates generated.  As a
   result, we chose to maintain the periodic update triggering of OSPF.
   Resolving conflicts in the settings of the different hold down timer
   settings requires more care.  In particular, it is important to
   ensure that the existing OSPF hold down timer does not interfere with
   QoS updates.  One option is to disable the existing OSPF timer, but
   protection against transient overloads calls for some hold down
   timer, albeit with a small value.  As a result, the existing OSPF
   hold down timer was kept, but reduced its value to 1 second.  This
   value is low enough (actually is the lowest possible, since GateD
   timers have a maximum resolution of 1 second) so that it does not
   interfere with the generation of the QoS link state updates, which
   will actually often have hold down timers of their own with higher
   values.  An additional complexity is that the triggering of QoS link
   state updates needs to be made aware of updates performed by OSPF
   itself.  This is necessary, as regular OSPF updates also carry
   bandwidth information, and this needs to be considered by QoS updates
   to properly determine when to trigger a new link state update.

   Another existing OSPF mechanism that has the potential to interfere
   with the extensions needed for QoS routing, is the support for
   delayed acknowledgments that allows aggregation of acknowledgments
   for multiple LSAs.  Since link state updates are maintained in
   retransmission queues until acknowledged, excessive delay in the
   generation of the acknowledgement combined with the increased rates
   of QoS updates may result in overflows of the retransmission queues.
   To avoid these potential overflows, this mechanism was bypassed
   altogether and LSAs received from neighboring routers were
   immediately acknowledged.  Another approach which was considered but
   not implemented, was to make QoS LSAs unreliable, i.e., eliminate
   their acknowledgments, so as to avoid any potential interference.
   Making QoS LSAs unreliable would be a reasonable design choice
   because of their higher frequency compared to the regular LSAs and
   the reduced impact that the loss of a QoS LSA has on the protocol
   operation.  Note that the loss of a QoS LSA does not interfere with
   the base operation of OSPF, and only transiently reduces the quality
   of paths discovered by QoS routing.





Apostolopoulos, et al.        Experimental                     [Page 27]

RFC 2676       QoS Routing Mechanisms and OSPF Extensions    August 1999


   The structure and placement of the QoS routing table also raises some
   interesting implementation issues.  Pre-computed paths are placed
   into a QoS routing table.  This table is implemented as a set of path
   structures, one for each destination, which contain all the available
   paths to this destination.  In order to be able to efficiently locate
   individual path structures, an access structure is needed.  In order
   to minimize the develpement effort, the radix tree structure used for
   the regular GateD routing tables was reused.  In addition, the QoS
   routing table was kept independent of the GateD routing tables to
   conform to the design goal of localizing changes and minimizing the
   impact on the existing OSPF code.  An additional reason for
   maintaining the QoS routing separate and self-contained is that it is
   re-computed under conditions that are different from those used for
   the regular routing tables.

   Furthermore, since the QoS routing table is re-built frequently, it
   must be organized so that its computation is efficient.  A common
   operation during the computation of the QoS routing table is mapping
   a link state database entry to the corresponding path structure.  In
   order to make this operation efficient, the link state database
   entries were extended to contain a pointer to the corresponding path
   structure.  In addition, when a new QoS routing table is to be
   computed, the previous one must be de-allocated.  This is
   accomplished by traversing the radix tree in-order, and de-allocating
   each node in the tree.  This full de-allocation of the QoS routing
   table is potentially wasteful, especially since memory allocation and
   de-allocation is an expensive operation.  Furthermore, because path
   pre-computations are typically not triggered by changes in topology,
   the set of destinations will usually remain the same and correspond
   to an unchanged radix tree.  A natural optimization would then be to
   de-allocate only the path structures and maintain the radix tree.  A
   further enhancement would be to maintain the path structures as well,
   and attempt to incrementally update them only when required.
   However, despite the potential gains, these optimizations have not
   been included in the initial implementation.  The main reason is that
   they involve subtle and numerous checks to ensure the integrity of
   the overall data structure at all times, e.g., correctly remove
   failed destinations from the radix tree and update the tree
   accordingly.












Apostolopoulos, et al.        Experimental                     [Page 28]

RFC 2676       QoS Routing Mechanisms and OSPF Extensions    August 1999


4.4. Bandwidth and Processing Overhead of QoS Routing

   After completing the implementation outlined in the previous
   sections, it was possible to perform an experimental study of the
   cost and nature of the overhead of the QoS routing extensions
   proposed in this document.  In particular, using a simple setup
   consisting of two interconnected routers, it is possible to measure
   the cost of individual QoS routing related operations.  These
   operations are:  a) computation of the QoS routing table, b)
   selection of a path from the QoS routing table, c) generation of a
   link state update, and d) reception of a link state update.  Note
   that the last two operations are not really specific to QoS routing
   since regular OSPF also performs them.  Nevertheless, we expect the
   more sensitive update triggering mechanisms required for effective
   QoS routing to result in increased number of updates, making the cost
   of processing updates an important component of the QoS routing
   overhead.  An additional cost dimension is the memory required for
   storing the QoS routing table.  Scaling of the above costs with
   increasing sizes of the topology database was investigated by
   artificially populating the topology databases of the routers under
   measurement.

   Table 1 shows how the measured costs depend on the size of the
   topology.  The topology used in the measurements was built by
   replicating a basic building block consisting of four routers
   connected with transit networks in a rectangular arrangement.  The
   details of the topology and the measurements can be found in [AGK99].
   The system running the GateD software was an IBM IntelliStation Z Pro
   with a Pentium Pro processor at 200 MHz, 64 MBytes or real memory,
   running FreeBSD 2.2.5-RELEASE and GateD 4.  From the results of Table
   1, one can observe that the cost of path pre-computation is not much
   higher than that of the regular SPF computation.  However, path pre-
   computation may need to be performed much more often than the SPF
   computation, and this can potentially lead to higher processing
   costs.  This issue was investigated in a set of subsequent
   experiments, that are described later in this section.  The other
   cost components reported in Table 1 include memory, and it can be
   seen that the QoS routing table requires roughly 80% more memory than
   the regular routing table.  Finally, the cost of selecting a path is
   found to be very small compared to the path pre-computation times.
   As expected, all the measured quantities increase as the size of the
   topology increases.  In particular, the storage requirements and the
   processing costs for both SPF computation and QoS path pre-
   computation scale almost linearly with the network size.







Apostolopoulos, et al.        Experimental                     [Page 29]

RFC 2676       QoS Routing Mechanisms and OSPF Extensions    August 1999


________________________________________________________________________
|Link_state_database_size_______|_25_|__49_|__81__|__121_|__169_|__225_|
|Regular_SPF_time_(microsec)____|215_|_440_|_747__|_1158_|_1621_|_2187_|
|Pre-computation_time_(microsec)|736_|_1622|_2883_|_4602_|_6617_|_9265_|
|SPF_routing_table_size_(bytes)_|2608|_4984|_8152_|_12112|_16864|_22408|
|QoS_routing_table_size_(bytes)_|3924|_7952|_13148|_19736|_27676|_36796|
|Path_Selection_time_(microsec)_|_.7_|_1.6_|__2.8_|__4.6_|__6.6_|__9.2_|

                 Table 1: Stand alone QoS routing costs

   In addition to the stand alone costs reported in Table 1, it is
   important to assess the actual operational load induced by QoS
   routing in the context of a large network.  Since it is not practical
   to reproduce a large scale network in a lab setting, the approach
   used was to combine simulation and measurements.  Specifically, a
   simulation was used to obtain a time stamped trace of QoS routing
   related events that occur in a given router in a large scale network.
   The trace was then used to artificially induce similar load
   conditions on a real router and its adjacent links.  In particular,
   it was used to measure the processing load at the router and
   bandwidth usage that could be attributed to QoS updates.  A more
   complete discussion of the measurement method and related
   considerations can be found in [AGK99].

   The use of a simulation further allows the use of different
   configurations, where network topology is varied together with other
   QoS parameters such as a) period of pre-computation, and b) threshold
   for triggering link state updates.  The results reported here were
   derived using two types of topologies.  One based on a regular but
   artificial 8x8 mesh network, and another (isp) which has been used in
   several previous studies [AGKT98, AT98] and that approximates the
   network of a nation-wide ISP. As far as pre-computation periods are
   concerned, three values of 1, 5 and 50 seconds were chosen, and for
   the triggering of link state update thresholds of 10% and 80% were
   used.  These values were selected as they cover a wide range in terms
   of precision of pre-computed paths and accuracy of the link state
   information available at the routers.  Also note that 1 second is the
   smallest pre-computation period allowed by GateD.

   Table 2 provides results on the processing load at the router driven
   by the simulation trace, for the two topologies and different
   combinations of QoS parameters, i.e., pre-computation period and
   threshold for triggering link state updates.  Table 3 gives the
   bandwidth consumption of QoS updates on the links adjacent to the
   router.






Apostolopoulos, et al.        Experimental                     [Page 30]

RFC 2676       QoS Routing Mechanisms and OSPF Extensions    August 1999


    ________________________________________________________________
    |_____________________|_________Pre-computation_Period_________|
    |Link_state_threshold_|___1_sec____|____5_sec____|____50_sec___|
    |_________10%_________|.45%_(1.6%)_|__.29%_(2%)__|__.17%_(3%)__|
    |_________80%_________|.16%_(2.4%)_|__.04%_(3%)__|_.02%_(3.8%)_|

                                  isp

    ________________________________________________________________
    |_________10%_________|3.37%_(2.1%)|_2.23%_(3.3%)|_1.78%_(7.7%)|
    |_________80%_________|1.54%_(5.4%)|_.42%_(6.6%)_|_.14%_(10.4%)|

                               8x8 mesh

       Table 2: Router processing load and (bandwidth blocking).

   In Table 2, processing load is expressed as the percentage of the
   total CPU resources that are consumed by GateD processing.  The same
   table also shows the routing performance that is achieved for each
   combination of QoS parameters, so that comparison of the different
   processing cost/routing performance trade-offs can be made.  Routing
   performance is measured using the bandwidth blocking ratio, defined
   as the sum of requested bandwidth of the requests that were rejected
   over the total offered bandwidth.  As can be seen from Table 2,
   processing load is low even when the QoS routing table is recomputed
   every second, and LSAs are generated every time the available
   bandwidth on a link changes by more than 10% of the last advertised
   value.  This seems to indicate that given today's processor
   technology, QoS routing should not be viewed as a costly enhancement,
   at least not in terms of its processing requirements.  Another
   general observation is that while network size has obviously an
   impact, it does not seem to drastically affect the relative influence
   of the different parameters.  In particular, despite the differences
   that exist between the isp and mesh topologies, changing the pre-
   computation period or the update threshold translates into
   essentially similar relative changes.

   Similar conclusions can be drawn for the update traffic shown in
   Table 3.  In all cases, this traffic is only a small fraction of the
   link's capacity.  Clearly, both the router load and the link
   bandwidth consumption depend on the router and link that was the
   target of the measurements and will vary for different choices.  The
   results shown here are meant to be indicative, and a more complete
   discussion can be found in [AGK99].







Apostolopoulos, et al.        Experimental                     [Page 31]

RFC 2676       QoS Routing Mechanisms and OSPF Extensions    August 1999


                _______________________________________
                |_Link_state_threshold_|_______________|
                |_________10%__________|3112_bytes/sec_|
                |_________80%__________|177_bytes/sec__|

                                  isp
                ________________________________________
                |_________10%__________|15438_bytes/sec_|
                |_________80%__________|1053_bytes/sec__|

                               8x8 mesh

                   Table 3: Link state update traffic

   Summarizing, by carrying out the implementation of the proposed QoS
   routing extensions to OSPF we demonstrated that such extensions are
   fairly straightforward to implement.  Furthermore, by measuring the
   performance of the real system we were able to demonstrate that the
   overheads associated with QoS routing are not excessive, and are
   definitely within the capabilities of modern processor and
   workstation technology.

5. Security Considerations

   The QoS extensions proposed in this document do not raise any
   security considerations that are in addition to the ones associated
   with regular OSPF. The security considerations of OSPF are presented
   in [Moy98].  However, it should be noted that this document assumes
   the availability of some entity responsible for assessing the
   legitimacy of QoS requests.  For example, when the protocol used for
   initiating QoS requests is the RSVP protocol, this capability can be
   provided through the use of RSVP Policy Decision Points and Policy
   Enforcement Points as described in [YPG97].  Similarly, a policy
   server enforcing the acceptability of QoS requests by implementing
   decisions based on the rules and languages of [RMK+98], would also be
   capable of providing the desired functionality.















Apostolopoulos, et al.        Experimental                     [Page 32]

RFC 2676       QoS Routing Mechanisms and OSPF Extensions    August 1999


APPENDICES

A. Pseudocode for the BF Based Pre-Computation Algorithm

   Note:  The pseudocode below assumes a hop-by-hop forwarding approach
   in updating the neighbor field.  The modifications needed to support
   explicit route construction are straightforward.  The pseudocode also
   does not handle equal cost multi-paths for simplicity, but the
   modification needed to add this support are straightforward.

Input:
  V = set of vertices, labeled by integers 1 to N.
  L = set of edges, labeled by ordered pairs (n,m) of vertex labels.
  s = source vertex (at which the algorithm is executed).
  For all edges (n,m) in L:
    * b(n,m) = available bandwidth (according to last received update)
    on interface associated with the edge between vertices n and m.
    * If(n,m) outgoing interface corresponding to edge (n,m) when n is
      a router.
  H = maximum hop-count (at most the graph diameter).

Type:
  tab_entry: record
                 bw = integer,
                 neighbor = integer 1..N.

Variables:
  TT[1..N, 1..H]: topology table, whose (n,h) entry is a tab_entry
                  record, such that:
                    TT[n,h].bw is the maximum available bandwidth (as
                      known thus far) on a path of at most h hops
                      between vertices s and n,
                    TT[n,h].neighbor is the first hop on that path (a
                      neighbor of s). It is either a router or the
                      destination n.

  S_prev: list of vertices that changed a bw value in the TT table
          in the previous iteration.
  S_new: list of vertices that changed a bw value (in the TT table
          etc.) in the current iteration.

The Algorithm:

begin;

  for n:=1 to N do  /* initialization */
  begin;
    TT[n,0].bw := 0;



Apostolopoulos, et al.        Experimental                     [Page 33]

RFC 2676       QoS Routing Mechanisms and OSPF Extensions    August 1999


    TT[n,0].neighbor := null
    TT[n,1].bw := 0;
    TT[n,1].neighbor := null
  end;
  TT[s,0].bw := infinity;

  reset S_prev;
  for all neighbors n of s do
  begin;
    TT[n,1].bw := max( TT[n,1].bw, b[s,n]);
    if (TT[n,1].bw = b[s,n]) then TT[n,1].neighbor := If(s,n);
             /* need to make sure we are picking the maximum */
             /* bandwidth path for routers that can be reached */
             /* through both networks and point-to-point links */
       if (n is a router) then
           S_prev :=  S_prev union {n}
             /* only a router is added to S_prev, */
             /* if it is not already included in S_prev */
       else     /* n is a network: */
             /* proceed with network--router edges, without */
             /* counting another hop */
          for all (n,k) in L, k <> s, do
             /* i.e., for all other neighboring routers of n */
          begin;
          TT[k,1].bw := max( min( TT[n,1].bw, b[n,k]), TT[k,1].bw );
             /* In case k could be reached through another path */
             /* (a point-to-point link or another network) with */
             /* more bandwidth, we do not want to update TT[k,1].bw */
          if (min( TT[n,1].bw, b[n,k]) = TT[k,1].bw )
             /* If we have updated TT[k,1].bw by going through */
             /* network n  */
          then TT[k,1].neighbor := If(s,n);
             /* neighbor is interface to network n */
          if ( {k} not in S_prev) then S_prev :=  S_prev union {k}
             /* only routers are added to S_prev, but we again need */
             /* to check they are not already included in S_prev */
          end
  end;


  for h:=2 to H do   /* consider all possible number of hops */
  begin;
    reset S_new;
    for all vertices m in V do
    begin;
      TT[m,h].bw := TT[m,h-1].bw;
      TT[m,h].neighbor := TT[m,h-1].neighbor
    end;



Apostolopoulos, et al.        Experimental                     [Page 34]

RFC 2676       QoS Routing Mechanisms and OSPF Extensions    August 1999


    for all vertices n in S_prev do
             /* as shall become evident, S_prev contains only routers */
    begin;
      for all edges (n,m) in L do
      if min( TT[n,h-1].bw, b[n,m]) > TT[m,h].bw then
      begin;
        TT[m,h].bw := min( TT[n,h-1].bw, b[n,m]);
        TT[m,h].neighbor := TT[n,h-1].neighbor;
        if m is a router then S_new :=  S_new union {m}
             /* only routers are added to S_new */
        else /* m is a network: */
             /* proceed with network--router edges, without counting */
             /* them as another hop */
        for all (m,k) in L, k <> n,
             /* i.e., for all other neighboring routers of m */
        if min( TT[m,h].bw, b[m,k]) > TT[k,h].bw then
        begin;
             /* Note: still counting it as the h-th hop, as (m,k) is */
             /* a network--router edge */
          TT[k,h].bw := min( TT[m,h].bw, b[m,k]);
          TT[k,h].neighbor := TT[m,h].neighbor;
          S_new :=  S_new union {k}
             /* only routers are added to S_new */
        end
      end
    end;
    S_prev := S_new;
            /* the two lists can be handled by a toggle bit */
    if S_prev=null then h=H+1   /* if no changes then exit */
  end;

end.



















Apostolopoulos, et al.        Experimental                     [Page 35]

RFC 2676       QoS Routing Mechanisms and OSPF Extensions    August 1999


B. On-Demand Dijkstra Algorithm for QoS Path Computation

   In the main text, we described an algorithm that allows pre-
   computation of QoS routes.  However, it may be feasible in some
   instances, e.g., limited number of requests for QoS routes, to
   instead perform such computations on-demand, i.e., upon receipt of a
   request for a QoS route.  The benefit of such an approach is that
   depending on how often recomputation of pre-computed routes is
   triggered, on-demand route computation can yield better routes by
   using the most recent link metrics available.  Another benefit of
   on-demand path computation is the associated storage saving, i.e.,
   there is no need for a QoS routing table.  This is essentially the
   standard trade-off between memory and processing cycles.

   In this section, we briefly describe how a standard Dijkstra
   algorithm can, for a given destination and bandwidth requirement,
   generate a minimum hop path that can accommodate the required
   bandwidth and also has maximum bandwidth.  Because the Dijkstra
   algorithm is already used in the current OSPF route computation, only
   differences from the standard algorithm are described.  Also, while
   for simplicity we do not consider here zero-hop edges, the
   modification required for supporting them is straightforward.

   The algorithm essentially performs a minimum hop path computation, on
   a graph from which all edges, whose available bandwidth is less than
   that requested by the flow triggering the computation, have been
   removed.  This can be performed either through a pre-processing step,
   or while running the algorithm by checking the available bandwidth
   value for any edge that is being considered (see the pseudocode that
   follows).  Another modification to a standard Dijkstra based minimum
   hop count path computation, is that the list of equal cost next
   (previous) hops which is maintained as the algorithm proceeds, needs
   to be sorted according to available bandwidth.  This is to allow
   selection of the minimum hop path with maximum available bandwidth.
   Alternatively, the algorithm could also be modified to, at each step,
   only keep among equal hop count paths the one with maximum available
   bandwidth.  This would essentially amount to considering a cost that
   is function of both hop count and available bandwidth.

   Note:  The pseudocode below assumes a hop-by-hop forwarding approach
   in updating the neighbor field.  Addition of routes to stub networks
   is done in a second phase as usual.  The modifications needed to
   support explicit route construction are straightforward.  The
   pseudocode also does not handle equal cost multi-paths for
   simplicity, but the modifications needed to add this support are also
   easily done.





Apostolopoulos, et al.        Experimental                     [Page 36]

RFC 2676       QoS Routing Mechanisms and OSPF Extensions    August 1999


Input:
  V = set of vertices, labeled by integers 1 to N.
  L = set of edges, labeled by ordered pairs (n,m) of vertex labels.
  s = source vertex (at which the algorithm is executed).
  For all edges (n,m) in L:
    * b(n,m) = available bandwidth (according to last received update)
    on interface associated with the edge between vertices n and m.
    * If(n,m) = outgoing interface corresponding to edge (n,m) when n is
      a router.
  d = destination vertex.
  B = requested bandwidth for the flow served.

Type:
  tab_entry: record
                 hops = integer,
                 neighbor = integer 1..N,
                 ontree = boolean.

Variables:
  TT[1..N]: topology table, whose (n) entry is a tab_entry
                  record, such that:
                    TT[n].bw is the available bandwidth (as known
                        thus far) on a shortest-path between
                        vertices s and n,
                    TT[n].neighbor is the first hop on that path (a
                        neighbor of s). It is either a router or the
                        destination n.
  S: list of candidate vertices;
  v: vertex under consideration;

The Algorithm:

begin;
  for n:=1 to N do  /* initialization */
  begin;
    TT[n].hops := infinity;
    TT[n].neighbor := null;
    TT[n].ontree := FALSE;
  end;
  TT[s].hops := 0;

  reset S;
  v:= s;
  while v <> d do
  begin;
    TT[v].ontree := TRUE;
    for all edges (v,m) in L and b(v,m) >= B do
    begin;



Apostolopoulos, et al.        Experimental                     [Page 37]

RFC 2676       QoS Routing Mechanisms and OSPF Extensions    August 1999


      if m is a router
      begin;
        if not TT[m].ontree then
        begin;
          /* bandwidth must be fulfilled since all links >= B */
          if TT[m].hops > TT[v].hops + 1 then
          begin
            S := S union { m };
            TT[m].hops := TT[v].hops + 1;
            TT[m].neighbor := v;
          end;
        end;
      end;
      else /* must be a network, iterate over all attached routers */
      begin; /* each network -- router edge treated as zero hop edge */
        for all (m,k) in L, k <> v,
             /* i.e., for all other neighboring routers of m */
        if not TT[k].ontree and b(m,k) >= B then
        begin;
          if TT[k].hops > TT[v].hops  then
          begin;
            S := S union { k };
            TT[k].hops := TT[v].hops;
            TT[k].neighbor := v;
          end;
        end;
      end;
    end; /* of all edges from the vertex under consideration */

    if S is empty then
    begin;
      v=d; /* which will end the algorithm */
    end;
    else
    begin;
      v := first element of S;
      S := S - {v}; /* remove and store the candidate to consider */
    end;
  end; /* from processing of the candidate list */
end.











Apostolopoulos, et al.        Experimental                     [Page 38]

RFC 2676       QoS Routing Mechanisms and OSPF Extensions    August 1999


C. Precomputation Using Dijkstra Algorithm

   This appendix outlines a Dijkstra-based algorithm that allows pre-
   computation of QoS routes for all destinations and bandwidth values.
   The benefit of using a Dijkstra-based algorithm is a greater synergy
   with existing OSPF implementations.  The solution to compute all
   "best" paths is to consecutively compute shortest path spanning trees
   starting from a complete graph and removing links with less bandwidth
   than the threshold used in the previous computation.  This yields
   paths with possibly better bandwidth but of course more hops.
   Despite the large number of Dijkstra computations involved, several
   optimizations such as incremental spanning tree computation can be
   used and allow for efficient implementations in terms of complexity
   as well as storage since the structure of computed paths leans itself
   towards path compression [ST83].  Details including measurements and
   applicability studies can be found in [Prz95] and [BP95].

   A variation of this theme is to trade the "accuracy" of the pre-
   computed paths, (i.e., the paths being generated may be of a larger
   hop count than needed) for the benefit of using a modified version of
   Dijkstra shortest path algorithm and also saving on some
   computations.  This loss in accuracy comes from the need to rely on
   quantized bandwidth values, which are used when computing a minimum
   hop count path.  In other words, the range of possible bandwidth
   values that can be requested by a new flow is mapped into a fixed
   number of quantized values, and minimum hop count paths are generated
   for each quantized value.  For example, one could assume that
   bandwidth values are quantized as low, medium, and high, and minimum
   hop count paths are computed for each of these three values.  A new
   flow is then assigned to the minimum hop path that can carry the
   smallest quantized value, i.e., low, medium, or high, larger than or
   equal to what it requested.  We restrict our discussion here to this
   "quantized" version of the algorithm.

   Here too, we discuss the elementary case where all edges count as
   "hops", and note that the modification required for supporting zero-
   hop edges is straightforward.

   As with the BF algorithm, the algorithm relies on a routing table
   that gets built as the algorithm progresses.  The structure of the
   routing table is as follows:

The QoS routing table:

   -  a K x Q matrix, where K is the number of vertices and Q is the
      number of quantized bandwidth values.





Apostolopoulos, et al.        Experimental                     [Page 39]

RFC 2676       QoS Routing Mechanisms and OSPF Extensions    August 1999


   -  The (n;q) entry contains information that identifies the minimum
      hop count path to destination n, which is capable of accommodating
      a bandwidth request of at least bw[q] (the qth quantized bandwidth
      value).  It consists of two fields:

      *  hops:  the minimal number of hops on a path between the source
         node and destination n, which can accommodate a request of at
         least bw[q] units of bandwidth.

      *  neighbor:  this is the routing information associated with the
         minimum hop count path to destination node n, whose available
         bandwidth is at least bw[q].  With a hop-by-hop routing
         approach, the neighbor information is simply the identity of
         the node adjacent to the source node on that path.

   The algorithm operates again on a directed graph where vertices
   correspond to routers and transit networks.  The metric associated
   with each edge in the graph is as before the bandwidth available on
   the corresponding interface, where b(n;m) is the available bandwidth
   on the edge between vertices n and m.  The vertex corresponding to
   the router where the algorithm is being run is selected as the source
   node for the purpose of path selection, and the algorithm proceeds to
   compute paths to all other nodes (destinations).

   Starting with the highest quantization index, Q, the algorithm
   considers the indices consecutively, in decreasing order.  For each
   index q, the algorithm deletes from the original network topology all
   links (n;m) for which b(n;m) < bw[q], and then runs on the remaining
   topology a Dijkstra-based minimum hop count algorithm  (10) between
   the source node and all other nodes (vertices) in the graph.  Note
   that as with the Dijkstra used for on-demand path computation, the
   elimination of links such that b(n;m) < bw[q] could also be performed
   while running the algorithm.

   After the algorithm terminates, the q-th column in the routing table
   is updated.  This amounts to recording in the hops field the hop
   count value of the path that was generated by the algorithm, and by
   updating the neighbor field.  As before, the update of the neighbor
   field depends on the scope of the path computation.  In the case of a
   hop-by-hop routing decision, the neighbor field is set to the
   identity of the node adjacent to the source node (next hop) on the
   path returned by the algorithm.  However, note that in order to
   ensure that the path with the maximal available bandwidth is always
   chosen among all minimum hop paths that can accommodate a given
   quantized bandwidth, a slightly different update mechanism of the
   neighbor field needs to be used in some instances.  Specifically,
   when for a given row, i.e., destination node n, the value of the hops
   field in column q is found equal to the value in column q+1 (here we



Apostolopoulos, et al.        Experimental                     [Page 40]

RFC 2676       QoS Routing Mechanisms and OSPF Extensions    August 1999


   assume q<Q), i.e., paths that can accommodate bw[q] and bw[q+ 1] have
   the same hop count, then the algorithm copies the value of the
   neighbor field from entry (n;q+1) into that of entry (n;q).

   Note:  The pseudocode below assumes a hop-by-hop forwarding approach
   in updating the neighbor field.  The modifications needed to support
   explicit route construction are straightforward.  The pseudocode also
   does not handle equal cost multi-paths for simplicity, but the
   modification needed to add this support have been described above.
   Details of the post-processing step of adding stub networks are
   omitted.

Input:
  V = set of vertices, labeled by integers 1 to N.
  L = set of edges, labeled by ordered pairs (n,m) of vertex labels.
  s = source vertex (at which the algorithm is executed).
  bw[1..Q] = array of bandwidth values to "quantize" flow requests to.
  For all edges (n,m) in L:
    * b(n,m) = available bandwidth (according to last received update)
    on interface associated with the edge between vertices n and m.
    * If(n,m) = outgoing interface corresponding to edge (n,m) when n is
      a router.

Type:
  tab_entry: record
                 hops = integer,
                 neighbor = integer 1..N,
                 ontree = boolean.

Variables:
  TT[1..N, 1..Q]: topology table, whose (n,q) entry is a tab_entry
                  record, such that:
                    TT[n,q].bw is the available bandwidth (as known
                        thus far) on a shortest-path between
                        vertices s and n accommodating bandwidth b(q),
                    TT[n,q].neighbor is the first hop on that path (a
                        neighbor of s). It is either a router or the
                        destination n.
  S: list of candidate vertices;
  v: vertex under consideration;
  q: "quantize" step

The Algorithm:

begin;
  for r:=1 to Q do
  begin;
    for n:=1 to N do  /* initialization */



Apostolopoulos, et al.        Experimental                     [Page 41]

RFC 2676       QoS Routing Mechanisms and OSPF Extensions    August 1999


    begin;
      TT[n,r].hops     := infinity;
      TT[n,r].neighbor := null;
      TT[n,r].ontree   := FALSE;
    end;
    TT[s,r].hops := 0;
  end;
  for r:=1 to Q do
  begin;
    S = {s};
    while S not empty do
    begin;
      v := first element of S;
      S := S - {v}; /* remove and store the candidate to consider */
      TT[v,r].ontree := TRUE;
      for all edges (v,m) in L and b(v,m) >= bw[r] do
      begin;
        if m is a router
        begin;
          if not TT[m,r].ontree then
          begin;
            /* bandwidth must be fulfilled since all links >= bw[r] */
            if TT[m,r].hops > TT[v,r].hops + 1 then
            begin
              S := S union { m };
              TT[m,r].hops := TT[v,r].hops + 1;
              TT[m,r].neighbor := v;
            end;
          end;
        end;
        else /* must be a network, iterate over all attached
                routers */
        begin;
          for all (m,k) in L, k <> v,
               /* i.e., for all other neighboring routers of m */
          if not TT[k,r].ontree and b(m,k) >= bw[r] then
          begin;
            if TT[k,r].hops > TT[v,r].hops + 2 then
            begin;
              S := S union { k };
              TT[k,r].hops := TT[v,r].hops + 2;
              TT[k,r].neighbor := v;
            end;
          end;
        end;
      end; /* of all edges from the vertex under consideration */
    end; /* from processing of the candidate list */
  end; /* of "quantize" steps */



Apostolopoulos, et al.        Experimental                     [Page 42]

RFC 2676       QoS Routing Mechanisms and OSPF Extensions    August 1999


end.

D. Explicit Routing Support

   As mentioned before, the scope of the path selection process can
   range from simply returning the next hop on the QoS path selected for
   the flow, to specifying the complete path that was computed, i.e., an
   explicit route.  Obviously, the information being returned by the
   path selection algorithm differs in these two cases, and constructing
   it imposes different requirements on the path computation algorithm
   and the data structures it relies on.  While the presentation of the
   path computation algorithms focused on the hop-by-hop routing
   approach, the same algorithms can be applied to generate explicit
   routes with minor modifications.  These modifications and how they
   facilitate constructing explicit routes are discussed next.

   The general approach to facilitate construction of explicit routes is
   to update the neighbor field differently from the way it is done for
   hop-by-hop routing as described in Section 2.3.  Recall that in the
   path computation algorithms the neighbor field is updated to reflect
   the identity of the router adjacent to the source node on the partial
   path computed.  This facilitates returning the next hop at the source
   for the specific path.  In the context of explicit routing, the
   neighbor information is updated to reflect the identity of the
   previous router on the path.

   In general, there can be multiple equivalent paths for a given hop
   count.  Thus, the neighbor information is stored as a list rather
   than single value.  Associated with each neighbor, additional
   information is stored to facilitate load balancing among these
   multiple paths at the time of path selection.  Specifically, we store
   the advertised available bandwidth on the link from the neighbor to
   the destination in the entry.

   With this change, the basic approach used to extract the complete
   list of vertices on a path from the neighbor information in the QoS
   routing table is to proceed `recursively' from the destination to the
   origin vertex.  The path is extracted by stepping through the
   precomputed QoS routing table from vertex to vertex, and identifying
   at each step the corresponding neighbor (precursor) information.  The
   process is described as recursive since the neighbor node identified
   in one step becomes the destination node for table look up in the
   next step.  Once the source router is reached, the concatenation of
   all the neighbor fields that have been extracted forms the desired
   explicit route.  This applies to algorithms of Section 2.3.1 and
   Appendix C.  If at a particular stage there are multiple neighbor
   choices (due to equal cost multi-paths), one of them can be chosen at
   random with a probability that is weighted, for example, by the



Apostolopoulos, et al.        Experimental                     [Page 43]

RFC 2676       QoS Routing Mechanisms and OSPF Extensions    August 1999


   associated bandwidth on the link from the neighbor to the (current)
   destination.

   Specifically, assume a new request to destination, say, d, and with
   bandwidth requirements B.  The index of the destination vertex
   identifies the row in the QoS routing table that needs to be checked
   to generate a path.  The row is then searched to identify a suitable
   path.  If the Bellman-Ford algorithm of Section 2.3.1 was used, the
   search proceeds by increasing index (hop) count until an entry is
   found, say at hop count or column index of h, with a value of the bw
   field that is equal to or greater than B.  This entry points to the
   initial information identifying the selected path.  If the Dijkstra
   algorithm of Appendix C is used, the first quantized value qB such
   that qB  >=   B is first identified, and the associated column then
   determines the first entry in the QoS routing table that identifies
   the selected path.

   Once this first entry has been identified, reconstruction of the
   complete list of vertices on the path proceeds similarly, whether the
   table was built using the algorithm of Section 2.3.1 or Appendix C.
   Specifically, in both cases, the neighbor field in each entry points
   to the previous node on the path from the source node and with the
   same bandwidth capabilities as those associated with the current
   entry.  The complete path is, therefore, reconstructed by following
   the pointers provided by the neighbor field of successive entries.

   In the case of the Bellman-Ford algorithm of Section 2.3.1, this
   means moving backwards in the table from column to column, using at
   each step the row index pointed to by the neighbor field of the entry
   in the previous column.  Each time, the corresponding vertex index
   specified in the neighbor field is pre-pended to the list of vertices
   constructed so far.  Since we start at column h, the process ends
   when the first column is reached, i.e., after h steps, at which point
   the list of vertices making up the path has been reconstructed.

   In the case of the Dijkstra algorithm of Appendix C, the backtracking
   process is similar although slightly different because of the
   different relation between paths and columns in the routing table,
   i.e., a column now corresponds to a quantized bandwidth value instead
   of a hop count.  The backtracking now proceeds along the column
   corresponding to the quantized bandwidth value needed to satisfy the
   bandwidth requirements of the flow.  At each step, the vertex index
   specified in the neighbor field is pre-pended to the list of vertices
   constructed so far, and is used to identify the next row index to
   move to.  The process ends when an entry is reached whose neighbor
   field specifies the origin vertex of the flow.  Note that since there
   are as many rows in the table as there are vertices in the graph,
   i.e., N, it could take up to N steps before the process terminates.



Apostolopoulos, et al.        Experimental                     [Page 44]

RFC 2676       QoS Routing Mechanisms and OSPF Extensions    August 1999


   Note that the identification of the first entry in the routing table
   is identical to what was described for the hop-by-hop routing case.
   However, as described in this section, the update of the neighbor
   fields while constructing the QoS routing tables, is being performed
   differently in the explicit and hop-by-hop routing cases.  Clearly,
   two different neighbor fields can be kept in each entry and updates
   to both could certainly be performed jointly, if support for both
   xplicit routing and hop-by-hop routing is needed.

Endnotes

   1. In this document we commit the abuse of notation of calling a
      "network" the interconnection of routers and networks through
      which we attempt to compute a QoS path.

   2. This is true for uni-cast flows, but in the case of multi-cast
      flows, hop-by-hop and an explicit routing clearly have different
      implications.

   3. Some hysteresis mechanism should be added to suppress updates when
      the metric value oscillates around a class boundary.

   4. In this document, we use the terms node and vertex
      interchangeably.

   5. Various hybrid methods can also be envisioned, e.g., periodic
      computations except if more than a given number of updates are
      received within a shorter interval, or periodic updates except if
      the change in metrics corresponding to a given update exceeds a
      certain threshold.  Such variations are, however, not considered
      in this document.

   6. Modifications to support explicit routing are discussed in
      Appendix D.

   7. Note, that this does not say anything on whether to differentiate
      between outgoing and incoming bandwidth on a shared media network.
      As a matter of fact, a reasonable option is to set the incoming
      bandwidth (from network to router) to infinity, and only use the
      outgoing bandwidth value to characterize bandwidth availability on
      the shared network.

   8. exponent in parenthesis

   9. Access to some of the more recent versions of the GateD software
      is restricted to the GateD consortium members.





Apostolopoulos, et al.        Experimental                     [Page 45]

RFC 2676       QoS Routing Mechanisms and OSPF Extensions    August 1999


   10. Note that a Breadth-First-Search (BFS) algorithm [CLR90] could
      also be used.  It has a lower complexity, but would not allow
      reuse of existing code in an OSPF implementation.

References

   [AGK99]  G. Apostolopoulos, R. Guerin, and S. Kamat. Implementation
            and performance meassurements of QoS routing extensions to
            OSPF.  In Proceedings of INFOCOM'99, pages 680--688, New
            York, NY, March 1999.

   [AGKT98] G. Apostolopoulos, R. Guerin, S. Kamat, and S. K. Tripathi.
            QoS routing:  A performance perspective.  In Proceedings of
            ACM SIGCOMM'98, pages 17--28, Vancouver, Canada, October

   [Alm92]  Almquist, P., "Type of Service in the Internet Protocol
            Suite", RFC 1349, July 1992.

   [AT98]   G. Apostolopoulos and S. K. Tripathi.  On reducing the
            processing cost of on-demand QoS path computation.  In
            Proceedings of ICNP'98, pages 80--89, Austin, TX, October
            1998.

   [BP95]   J.-Y. Le Boudec and T. Przygienda.  A Route Pre-Computation
            Algorithm for Integrated Services Networks.  Journal of
            Network and Systems Management, 3(4), 1995.

   [Car79]  B. Carre.  Graphs and Networks.  Oxford University Press,
            ISBN 0-19-859622-7, Oxford, UK, 1979.

   [CLR90]  T. H. Cormen, C. E. Leiserson, and R. L. Rivest.
            Introduction to Algorithms.  MIT Press, Cambridge, MA, 1990.

   [Con]    Merit GateD Consortium.  The Gate Daemon (GateD) project.

   [GJ79]   M.R. Garey and D.S. Johnson.  Computers and Intractability.
            Freeman, San Francisco, 1979.

   [GKH97]  R. Guerin, S. Kamat, and S. Herzog.  QoS Path Management
            with RSVP.  In Proceedings of the 2nd IEEE Global Internet
            Mini-Conference, pages 1914-1918, Phoenix, AZ, November

   [GKR97]  Guerin, R., Kamat, S. and E. Rosen, "An Extended RSVP
            Routing Interface, Work in Progress.

   [GLG+97] Der-Hwa G., Li, T., Guerin, R., Rosen, E. and S. Kamat,
            "Setting Up Reservations on Explicit Paths using RSVP", Work
            in Progress.



Apostolopoulos, et al.        Experimental                     [Page 46]

RFC 2676       QoS Routing Mechanisms and OSPF Extensions    August 1999


   [GO99]   R. Guerin and A. Orda.  QoS-Based Routing in Networks with
            Inaccurate Information: Theory and Algorithms.  IEEE/ACM
            Transactions on Networking, 7(3):350--364, June 1999.


   [GOW97]  R. Guerin, A. Orda, and D. Williams.  QoS Routing Mechanisms
            and OSPF Extensions.  In Proceedings of the 2nd IEEE Global
            Internet Mini-Conference, pages 1903-1908, Phoenix, AZ,
            November 1997.

   [KNB98]  Nichols, K., Blake, S., Baker F. and D. Black, "Definition
            of the Differentiated Services Field (DS Field) in the IPv4
            and IPv6 Headers", RFC 2474, December 1998.

   [LO98]   D. H. Lorenz and A. Orda.  QoS Routing in Networks with
            Uncertain Parameters.  IEEE/ACM Transactions on Networking,
            6(6):768--778, December 1998.

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

   [Moy98]  Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998.

   [Prz95]  A. Przygienda.  Link State Routing with QoS in ATM LANs.
            Ph.D. Thesis Nr. 11051, Swiss Federal Institute of
            Technology, April 1995.

   [RMK+98] R. Rajan, J. C. Martin, S. Kamat, M. See, R. Chaudhury, D.
            Verma, G. Powers, and R. Yavatkar.  Schema for
            differentiated services and integrated services in networks.
            INTERNET-DRAFT, October 1998.  work in progress.

   [RZB+97] Braden, R., Editor, Zhang, L., Berson, S., Herzog, S. and S.
            Jamin, "Resource reSerVation Protocol (RSVP) Version 1,
            Functional Specification", RFC 2205, September 1997.

   [SPG97]  Shenker, S., Partridge, C. and R. Guerin, "Specification of
            Guaranteed Quality of Service", RFC 2212, November 1997.

   [ST83]   D.D. Sleator and R.E. Tarjan.  A Data Structure for Dynamic
            Trees.  Journal of Computer Systems, 26, 1983.

   [Tan89]  A. Tannenbaum.  Computer Networks.  Addisson Wesley, 1989.

   [YPG97]  Yavatkar, R., Pendarakis, D. and R. Guerin, "A Framework for
            Policy-based Admission Control", INTERNET-DRAFT, April 1999.
            Work in Progress.





Apostolopoulos, et al.        Experimental                     [Page 47]

RFC 2676       QoS Routing Mechanisms and OSPF Extensions    August 1999


Authors' Addresses

   George Apostolopoulos
   IBM T.J. Watson Research Center
   P.O. Box 704
   Yorktown Heights, NY 10598

   Phone: +1 914 784-6204
   Fax:   +1 914 784-6205
   EMail: georgeap@watson.ibm.com


   Roch Guerin
   University Of Pennsylvania
   Department of Electrical Engineering, Rm 367 GRW
   200 South 33rd Street
   Philadelphia, PA 19104--6390

   Phone: +1 215-898-9351
   EMail: guerin@ee.upenn.edu


   Sanjay Kamat
   Bell Laboratories
   Lucent Technologies
   Room 4C-510
   101 Crawfords Corner Road
   Holmdel, NJ 07733

   Phone: (732) 949-5936
   email: sanjayk@dnrc.bell-labs.com


   Ariel Orda
   Dept. Electrical Engineering
   Technion - I.I.T
   Haifa, 32000 - ISRAEL

   Phone: +011 972-4-8294646
   Fax:   +011 972-4-8323041
   EMail: ariel@ee.technion.ac.il










Apostolopoulos, et al.        Experimental                     [Page 48]

RFC 2676       QoS Routing Mechanisms and OSPF Extensions    August 1999


   Tony Przygienda
   Siara Systems
   300 Ferguson Drive
   Moutain View
   California 94043

   Phone: +1 732 949-5936
   Email: prz@siara.com


   Doug Williams
   IBM T.J. Watson Research Center
   P.O. Box 704
   Yorktown Heights, NY 10598

   Phone: +1 914 784-5047
   Fax:   +1 914 784-6318
   EMail: dougw@watson.ibm.com

































Apostolopoulos, et al.        Experimental                     [Page 49]

RFC 2676       QoS Routing Mechanisms and OSPF Extensions    August 1999


Full Copyright Statement

   Copyright (C) The Internet Society (1999).  All Rights Reserved.

   This document and translations of it may be copied and furnished to
   others, and derivative works that comment on or otherwise explain it
   or assist in its implementation may be prepared, copied, published
   and distributed, in whole or in part, without restriction of any
   kind, provided that the above copyright notice and this paragraph are
   included on all such copies and derivative works.  However, this
   document itself may not be modified in any way, such as by removing
   the copyright notice or references to the Internet Society or other
   Internet organizations, except as needed for the purpose of
   developing Internet standards in which case the procedures for
   copyrights defined in the Internet Standards process must be
   followed, or as required to translate it into languages other than
   English.

   The limited permissions granted above are perpetual and will not be
   revoked by the Internet Society or its successors or assigns.

   This document and the information contained herein is provided on an
   "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
   TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING
   BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION
   HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF
   MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.

Acknowledgement

   Funding for the RFC Editor function is currently provided by the
   Internet Society.



















Apostolopoulos, et al.        Experimental                     [Page 50]