File: rfc3063.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 (2467 lines) | stat: -rw-r--r-- 93,523 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






Network Working Group                                            Y. Ohba
Request for Comments: 3063                                    Y. Katsube
Category: Experimental                                           Toshiba
                                                                E. Rosen
                                                           Cisco Systems
                                                               P. Doolan
                                                       Ennovate Networks
                                                           February 2001


                     MPLS Loop Prevention Mechanism

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 (2001).  All Rights Reserved.

Abstract

   This paper presents a simple mechanism, based on "threads", which can
   be used to prevent Multiprotocol Label Switching (MPLS) from setting
   up label switched path (LSPs) which have loops.  The mechanism is
   compatible with, but does not require, VC merge.  The mechanism can
   be used with either the ordered downstream-on-demand allocation or
   ordered downstream allocation.  The amount of information that must
   be passed in a protocol message is tightly bounded (i.e., no path-
   vector is used).  When a node needs to change its next hop, a
   distributed procedure is executed, but only nodes which are
   downstream of the change are involved.
















Ohba, et al.                  Experimental                      [Page 1]

RFC 3063             MPLS Loop Prevention Mechanism        February 2001


Table of Contents

   1      Introduction ..........................................  2
   2      Basic definitions .....................................  3
   3      Thread basics .........................................  5
   3.1    Thread attributes .....................................  5
   3.2    Thread loop ...........................................  7
   3.3    Primitive thread actions ..............................  7
   3.4    Examples of primitive thread actions  ................. 10
   4      Thread algorithm ...................................... 14
   5      Applicability of the algorithm ........................ 14
   5.1    LSP Loop prevention/detection ......................... 15
   5.2    Using old path while looping on new path .............. 15
   5.3    How to deal with ordered downstream allocation ........ 15
   5.4    How to realize load splitting ......................... 15
   6      Why this works ........................................ 16
   6.1    Why a thread with unknown hop count is extended ....... 16
   6.2    Why a rewound thread cannot contain a loop ............ 17
   6.2.1  Case1: LSP with known link hop counts ................. 17
   6.2.1  Case2: LSP with unknown link hop counts ............... 17
   6.3    Why L3 loop is detected ............................... 17
   6.4    Why L3 loop is not mis-detected ....................... 17
   6.5    How a stalled thread automatically recovers from loop . 18
   6.6    Why different colored threads do not chase each other . 18
   7      Loop prevention examples .............................. 19
   7.1    First example ......................................... 19
   7.2    Second example ........................................ 23
   8      Thread control block .................................. 24
   8.1    Finite state machine .................................. 25
   9      Comparison with path-vector/diffusion method .......... 28
   10     Security Considerations ............................... 29
   11     Intellectual Property Considerations .................. 29
   12     Acknowledgments ....................................... 29
   13     Authors' Addresses .................................... 30
   14     References ............................................ 30
   Appendix A   Further discussion of the algorithm ............. 31
   Full Copyright Statement ..................................... 44

1.  Introduction

   This paper presents a simple mechanism, based on "threads", which can
   be used to prevent MPLS from setting up label switched paths (LSPs)
   which have loops.

   When an LSR finds that it has a new next hop for a particular FEC
   (Forwarding Equivalence Class) [1], it creates a thread and extends
   it downstream.  Each such thread is assigned a unique "color", such
   that no two threads in the network can have the same color.



Ohba, et al.                  Experimental                      [Page 2]

RFC 3063             MPLS Loop Prevention Mechanism        February 2001


   For a given LSP, once a thread is extended to a particular next hop,
   no other thread is extended to that next hop unless there is a change
   in the hop count from the furthest upstream node.  The only state
   information that needs to be associated with a particular next hop
   for a particular LSP is the thread color and hop count.

   If there is a loop, then some thread will arrive back at an LSR
   through which it has already passed.  This is easily detected, since
   each thread has a unique color.

   Section 3 and 4 provide procedures for determining that there is no
   loop.  When this is determined, the threads are "rewound" back to the
   point of creation.  As they are rewound, labels get assigned.  Thus
   labels are NOT assigned until loop freedom is guaranteed.

   While a thread is extended, the LSRs through which it passes must
   remember its color and hop count, but when the thread has been
   rewound, they need only remember its hop count.

   The thread mechanism works if some, all, or none of the LSRs in the
   LSP support VC-merge.  It can also be used with either the ordered
   downstream on-demand label allocation or ordered downstream
   unsolicited label allocation [2,3].  The mechanism can also be
   applicable to loop detection, old path retention, and load-splitting.

   The state information which must be carried in protocol messages, and
   which must be maintained internally in state tables, is of fixed
   size, independent of the network size.  Thus the thread mechanism is
   more scalable than alternatives which require that path-vectors be
   carried.

   To set up a new LSP after a routing change, the thread mechanism
   requires communication only between nodes which are downstream of the
   point of change.  There is no need to communicate with nodes that are
   upstream of the point of change.  Thus the thread mechanism is more
   robust than alternatives which require that a diffusion computation
   be performed (see section 9).

2. Basic definitions

   LSP

      We will use the term LSP to refer to a multipoint-to-point tree
      whose root is the egress node.  See section 3.5 of [3].







Ohba, et al.                  Experimental                      [Page 3]

RFC 3063             MPLS Loop Prevention Mechanism        February 2001


      In the following, we speak as if there were only a single LSP
      being set up in the network.  This allows us to talk of incoming
      and outgoing links without constantly saying something like "for
      the same LSP.

   Incoming Link, Upstream Link
   Outgoing Link, Downstream Link

      At a given node, a given LSP will have one or more incoming, or
      upstream links, and one outgoing or downstream link.  A "link" is
      really an abstract relationship with an "adjacent" LSR; it is an
      "edge" in the "tree", and not necessarily a particular concrete
      entity like an "interface".

   Leaf Node, Ingress Node

      A node which has no upstream links.

   Eligible Leaf Node

      A node which is capable of being a leaf node.  For example, a node
      is not an eligible leaf node if it is not allowed to directly
      inject L3 packets created or received at the node into its
      outgoing link.

   Link Hop Count

      Every link is labeled with a "link hop count".  This is the number
      of hops between the given link and the leaf node which is furthest
      upstream of the given link.  At any node, the link hop count for
      the downstream link is one more than the largest of the hop counts
      associated with the upstream links.

      We define the quantity "Hmax" at a given node to be the maximum of
      all the incoming link hop counts.  Note that, the link hop count
      of the downstream link is equal to Hmax+1.  At a leaf node, Hmax
      is set to be zero.

      An an example of link hop counts is shown in Fig.1.












Ohba, et al.                  Experimental                      [Page 4]

RFC 3063             MPLS Loop Prevention Mechanism        February 2001


                    1   2
                   A---B---C       K
                           |       |
                           |3      |1
                           |       |
                           | 4   5 | 6   7
                           D---G---H---I---J
                           |
                           |2
                         1 |
                       E---F

                 Fig.1  Example of link hop counts

   Next Hop Acquisition

      Node N thought that FEC F was unreachable, but now has a next hop
      for it.

   Next Hop Loss

      Node N thought that node A was the next hop for FEC F, but now no
      longer has the next hop for FEC F.  A node loses a next hop
      whenever the next hop goes down.

   Next Hop Change

      At node N, the next hop for FEC F changes from node A to node B,
      where A is different than B.  A next hop change event can be seen
      as a combination of a next hop loss event on the old next hop and
      a next hop acquisition event on the new next hop.

3. Thread basics

   A thread is a sequence of messages used to set up an LSP, in the
   "ordered downstream-on-demand" (ingress-initiated ordered control)
   style.

3.1.  Thread attributes

   There are three attributes related to threads.  They may be encoded
   into a single thread object as:









Ohba, et al.                  Experimental                      [Page 5]

RFC 3063             MPLS Loop Prevention Mechanism        February 2001


    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                                                               |
   +                             Color                             +
   |                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |   Hop Count   |      TTL      |           Reserved            |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   Thread Color

      Every time a path control message is initiated by a node, the node
      assigns a unique "color" to it.  This color is to be unique in
      both time and space: its encoding consists of an IP address of the
      node concatenated with a unique event identifier from a numbering
      space maintained by the node.  The path setup messages that the
      node sends downstream will contain this color.  Also, when the
      node sends such a message downstream, it will remember the color,
      and this color becomes the color of the downstream link.

      When a colored message is received, its color becomes the color of
      the incoming link.  The thread which consists of messages of a
      certain color will be known as a thread of that color.

      special color value "transparent"(=all 0's) is reserved.

      One possible method for unique color assignment is, starting the
      event identifier from its initial value, and incrementing it by
      one (modulo its maximum value) each time a color is assigned.  In
      this method, the initial event identifier is either selected at
      random or assigned to be larger than the largest event identifier
      used on the previous system incarnation.

   Thread Hop Count

      In order to maintain link hop counts, we need to carry hop counts
      in the path control messages.  For instance, a leaf node would
      assign a hop count of 1 to its downstream link, and would store
      that value into a path setup message it sends downstream.  When a
      path setup message is sent downstream, a node would assign a hop
      count which is one more than the largest of the incoming link hop
      counts, to its downstream link, and  would store that value into a
      path setup message it sends downstream.  Once the value is stored
      in a path control message, we may refer to it has a "thread hop
      count".






Ohba, et al.                  Experimental                      [Page 6]

RFC 3063             MPLS Loop Prevention Mechanism        February 2001


      A special hop count value "unknown"(=0xff), which is larger than
      any other known value, is used when a loop is found.  Once the
      thread hop count is "unknown", it is not increased any more as the
      thread is extended.

   Thread TTL

      To avoid infinite looping of control messages in some cases, a
      thread TTL is used.  When a node creates a path control message
      and sends it downstream, it sets a TTL to the message, and the TTL
      is decremented at each hop.  When the TTL reaches 0, the message
      is not forwarded any more.  Unlike the thread hop counts and the
      thread colors, the thread TTLs do not needs to be stored in
      incoming links.

3.2.  Thread loop

   When the same colored thread is received on multiple incoming links,
   or the received thread color was assigned by the receiving node, it
   is said that the thread forms a loop.  A thread creator can tell
   whether it assigned the received thread color by checking the IP
   address part of the received thread color.

3.3.  Primitive thread actions

   Five primitive actions are defined in order to prevent LSP loops by
   using threads: "extending", "rewinding", "withdrawing", "merging",
   and "stalling".  This section describes only each primitive action
   and does not describe how these primitive actions are combined and
   how the algorithm totally works.  The main body of the algorithm is
   described in section 4.

   Thread Extending

      When a node starts to send a path setup message to its next hop
      with a set of thread attributes, it is said that "the node creates
      a thread and extends it downstream".  When a node receives a path
      setup message from an upstream node with a set of thread
      attributes and forwards it downstream, it is said that "the node
      receives a thread and extends it downstream".  The color and hop
      count of the thread become the color and hop count of the outgoing
      link.  Whenever a thread is received on a particular link, the
      color and hop count of that thread become the color and hop count
      of that incoming link, replacing any color and hop count that the
      link may have had previously.






Ohba, et al.                  Experimental                      [Page 7]

RFC 3063             MPLS Loop Prevention Mechanism        February 2001


      For example, when an ingress node initiates a path setup, it
      creates a thread and extends it downstream by sending a path setup
      message.  The thread hop count is set to be 1, and the thread
      color is set to be the ingress node's address with an appropriate
      event identifier, and the thread TTL is set to be its maximum
      value.

      When a node receives a thread and extends it downstream, the node
      either (i) extends the thread without changing color, or (ii)
      extend the thread with changing color.  The received thread is
      extended with changing color if it is received on a new incoming
      link and extended on an already existing outgoing link, otherwise,
      it is extended without changing color.  When a thread is extended
      with changing color, a new colored thread is created and extended.

      Thread creation does not occur only at leaf nodes.  If an
      intermediate node has an incoming link, it will create and extend
      a new thread whenever it acquires a new next hop.

      When a node notifies a next hop node of a decrease of the link hop
      count, if it is not extending a colored thread, a transparent
      thread is extended.

   Thread Merging

      When a node which has a colored outgoing link receives a new
      thread, it does not necessarily extend the new thread.  It may
      instead 'merge' the new threads into the existing outgoing thread.
      In this case, no messages are sent downstream.  Also, if a new
      incoming thread is extended downstream, but there are already
      other incoming threads, these other incoming threads are
      considered to be merged into the new outgoing thread.

      Specifically, a received thread is merged if all the following
      conditions hold:

      o  A colored thread is received by node N, AND
      o  The thread does not form a loop, AND
      o  N is not an egress node, AND
      o  N's outgoing link is colored, AND
      o  N's outgoing link hop count is at least one greater than the
         hop count of the newly received thread.

      When an outgoing thread rewinds (see below), any incoming threads
      which have been merged with it will rewind as well.






Ohba, et al.                  Experimental                      [Page 8]

RFC 3063             MPLS Loop Prevention Mechanism        February 2001


   Thread Stalling

      When a colored thread is received, if the thread forms a loop, the
      received thread color and hop count are stored on the receiving
      link without being extended.  This is the special case of thread
      merging applied only for threads forming a loop and referred to as
      the "thread stalling", and the incoming link storing the stalled
      thread is called "stalled incoming link".  A distinction is made
      between stalled incoming links and unstalled incoming links.

   Thread Rewinding

      When a thread reaches a node which satisfies a particular loop-
      free condition, the node returns an acknowledgment message back to
      the message initiator in the reverse path on which the thread was
      extended.  The transmission of the acknowledgment messages is the
      "rewinding" of the thread.

      The loop-free condition is:

      o  A colored thread is received by the egress node, OR
      o  All of the following conditions hold:
         (a) A colored thread is received by node N, AND
         (b) N's outgoing link is transparent, AND
         (c) N's outgoing link hop count is at least one greater than
             the hop count of the newly received thread.

      When a node rewinds a thread which was received on a particular
      link, it changes the color of that link to transparent.

      If there is a link from node M to node N, and M has extended a
      colored thread to N over that link, and M determines (by receiving
      a message from N) that N has rewound that thread, then M sets the
      color of its outgoing link to transparent.  M then continues
      rewinding the thread, and in addition, rewinds any other incoming
      thread which had been merged with the thread being rewound,
      including stalled threads.

      Each node can start label switching after the thread colors in all
      incoming and outgoing links becomes transparent.

      Note that transparent threads are threads which have already been
      rewound; hence there is no such thing as rewinding a  transparent
      thread.







Ohba, et al.                  Experimental                      [Page 9]

RFC 3063             MPLS Loop Prevention Mechanism        February 2001


   Thread Withdrawing

      It is possible for a node to tear down a path.  A node tears down
      the portion of the path downstream of itself by sending teardown
      messages to its next hop.  This process is known as the "thread
      withdrawing".

      For example, suppose a node is trying to set up a path, and then
      experiences a next hop change or a next hop loss.  It will
      withdraw the thread that it had extended down its old next hop.

      If node M has extended a thread to node N, and node M then
      withdraws that thread, N now has one less incoming link than it
      had before.  If N now has no other unstalled incoming links and N
      is not an eligible leaf node, it must withdraw its outgoing
      thread.  If N still has an unstalled incoming link or N is an
      eligible leaf node, it may (or may not) need to change the hop
      count of the outgoing link.

      N needs to change the outgoing hop count if:

      o  The incoming link hop count that was just removed had a larger
         hop count than any of the remaining incoming links, AND
      o  One of the following conditions holds:
         (a) The outgoing link is transparent, OR
         (b) The outgoing link has a known hop count.

      If the outgoing link is transparent, it remains transparent, but
      the new hop count needs to be sent downstream.  If the outgoing
      link is colored, a new thread (with a new color) needs to be
      created and extended downstream.

3.4.  Examples of primitive thread actions

   The following notations are used to illustrate examples of primitive
   actions defined for threads.

   A pair of thread attributes stored in each link is represented by
   "(C,H)", where C and H represent the thread color and thread hop
   count, respectively.

   A thread marked "+" indicates that it is created or received now.  A
   thread marked "-" indicates that it is withdrawn now.

   A link labeled with squared brackets (e.g., "[a]") indicates that it
   is an unstalled link.  A link labeled with braces (e.g., "{a}")
   indicates that it is a stalled link.




Ohba, et al.                  Experimental                     [Page 10]

RFC 3063             MPLS Loop Prevention Mechanism        February 2001


   Fig. 2 shows an example in which a leaf node A creates a blue thread
   and extends it downstream.

                                    (bl,1)
                                 A---[o1]--->

                 Fig.2    Thread extending at leaf node

   Fig.3 shows an example of thread extending without changing color at
   intermediate node.  Assume that a node B has no incoming and outgoing
   link before receiving a blue thread.  When node B receives the blue
   thread of hop count 1 on a new incoming link i1, it extends the
   thread downstream without changing color (Fig.3(a)).  After the blue
   thread is extended, node B receives a red thread of hop count unknown
   on incoming link i1 again (Fig.3(b)).  The red thread is also
   extended without changing its color, since both i1 and o1 already
   exists.

         (bl,1)+     (bl,2)            (re,U)+      (re,U)
      ----[i1]--->B---[o1]---->     ----[i1]--->B----[o1]--->

              Fig.3(a)                      Fig.3(b)

          Fig.3    Thread extending without changing color

   Fig.4 shows an example of thread extending with changing color.
   There are single incoming link i1 and single outgoing link o1 in
   Fig.4(a).  Then a red thread of hop count 3 is received on a new
   incoming link i2.  In this case, the received thread is extended with
   changing color, i.e., a new green thread is created and extended
   (Fig.4(b)), since o1 already exists.

       (bl,1)       (bl,2)          (bl,1)       (gr,4)
    ----[i1]--->B----[o1]--->    ----[i1]--->B----[o1]--->
                                             ^
                                             |
                                 ----[i2]----+
                                    (re,3)+

             Fig.4(a)                     Fig.4(b)

        Fig.4    Thread extending with changing color

   Fig.5 shows an example of thread merging.  When a node B receives a
   red thread of hop count 3, the received thread is not extended since
   the outgoing link hop count is at least one greater than the received
   thread hop count.  Both the red and blue threads will be rewound when
   the blue thread on outgoing link o1 is rewound.



Ohba, et al.                  Experimental                     [Page 11]

RFC 3063             MPLS Loop Prevention Mechanism        February 2001


                      (bl,3)       (bl,4)
                   ----[i1]--->B----[o1]--->
                               ^
                               |
                   ----[i2]----+
                      (re,3)+

                   Fig.5    Thread merging

   Figs 6 and 7 show examples of thread stalling.  When a node B
   receives a blue thread of hop count 10 on incoming link i2 in Fig.6,
   it "stalls" the received thread since the blue thread forms a loop.
   In Fig.7, a leaf node A finds the loop of its own thread.

                       (bl,3)       (bl,4)
                    ----[i1]--->B----[o1]--->
                                ^
                                |
                    ----{i2}----+
                       (bl,10)+

                   Fig.6    Thread stalling (1)


                      (bl,10)+      (bl,1)
                    ----{i1}--->A----[o1]--->

                   Fig.7    Thread stalling (2)

   Fig.8 shows an example of thread rewinding.  When the yellow thread
   which is currently being extended is rewound (Fig.8(a)), the node
   changes all the incoming and outgoing thread color to transparent,
   and propagates thread rewinding to upstream nodes (Fig.8(b)).

        (bl,1)       (ye,2)                  (tr,1)       (tr,2)
     ----[i2]--->B----[o1]--->            ----[i2]--->B----[o1]--->
                 ^                                    ^
                 |                                    |
     ----[i3]----+                        ----[i3]----+
        (ye,1)                               (tr,1)

            Fig.8(a)                              Fig.8(b)

                     Fig.8    Thread rewinding







Ohba, et al.                  Experimental                     [Page 12]

RFC 3063             MPLS Loop Prevention Mechanism        February 2001


   Fig.9 shows an example of thread withdrawing.  In Fig.9(a), the red
   thread on incoming link i2 is withdrawn.  Then Hmax decreases from 3
   to  1, and node B  creates a new  green thread and extends it
   downstream, as shown in Fig.9(b).

          (bl,1)      (re,4)           (bl,1)       (gr,2)+
       ----[i1]--->B---[o1]--->     ----[i1]--->B----[o1]--->
                   ^
                   |
       ----[i2]----+
          (re,3)-

                Fig.9(a)                     Fig.9(b)

               Fig.9  Thread withdrawing (1)

   Fig.10 shows another example of thread withdrawing.  In Fig.10(a),
   the red thread on incoming link i3 is withdrawn.  In this case, Hmax
   decreases from unknown to 1, however, no thread is extended as shown
   in Fig.10(b), since the outgoing link has a colored thread and the
   hop count is unknown.

           (bl,1)      (re,U)          (bl,1)       (re,U)
       ----[i2]--->B----[o1]--->    ----[i2]--->B----[o1]--->
                   ^
                   |
       ----[i3]----+
           (re,U)-

               Fig.10(a)                     Fig.10(b)

               Fig.10    Thread withdrawing (2)

   Fig.11 shows another example of thread withdrawing.  In Fig.11(a),
   the transparent thread on incoming link i3 is withdrawn.  In this
   case, a transparent thread is extended (Fig.11(b)), since Hmax
   decreases and the outgoing link is transparent.

           (tr,1)      (tr,U)          (tr,1)       (tr,2)+
       ----[i2]--->B----[o1]--->    ----[i2]--->B----[o1]--->
                   ^
                   |
       ----[i3]----+
           (tr,U)-

               Fig.11(a)                     Fig.11(b)

               Fig.11    Thread withdrawing (3)



Ohba, et al.                  Experimental                     [Page 13]

RFC 3063             MPLS Loop Prevention Mechanism        February 2001


4. Thread algorithm

   The ordered downstream-on-demand allocation is assumed here, however,
   the algorithm can be adapted to the ordered downstream allocation, as
   shown in section 5.

   In the algorithm, a next hop change event will be separated into two
   events: a next hop loss event on the old next hop and a next hop
   acquisition event on the new next hop, in this order.

   The following notations are defined:

         Hmax: the largest incoming link hop count
         Ni:   the number of unstalled incoming links

   The thread algorithm is described as follows.

   When a node acquires a new next hop, it creates a colored thread and
   extends it downstream.

   When a node loses a next hop to which it has extended a thread, it
   may withdraw that thread.  As described in section 3, this may or may
   not cause the next hop to take some action.  Among the actions the
   next hop may take are withdrawing the thread from its own next hop,
   or extending a new thread to its own next hop.

   A received colored thread is either stalled, merged, rewound, or
   extended.  A thread with TTL zero is never extended.

   When a received thread is stalled at a node, if Ni=0 and the node is
   not an eligible leaf node, initiate a thread withdrawing.  Otherwise,
   if Ni>0 and the received thread hop count is not unknown, a colored
   thread of hop count unknown is created and extended.  If the received
   thread hop count is unknown, no thread is extended and no further
   action is taken.

   When a thread being extended is rewound, if the thread hop count is
   greater than one more than Hmax, a transparent thread of hop count
   (Hmax+1) is extended downstream.

   When a node that has an transparent outgoing link receives a
   transparent thread, if Hmax decreases the node extends it downstream
   without changing color.

5. Applicability of the algorithm

   The thread algorithm described in section 4 can be applied to various
   LSP management policies.



Ohba, et al.                  Experimental                     [Page 14]

RFC 3063             MPLS Loop Prevention Mechanism        February 2001


5.1.  LSP Loop prevention/detection

   The same thread algorithm is applicable to both LSP loop prevention
   and detection.

   In loop prevention mode, a node transmits a label mapping (including
   a thread object) for a particular LSP only when it rewinds the thread
   for that LSP.  No mapping message is sent until the thread rewinds.

   On the other hand, if a node operates in loop detection mode, it
   returns a label mapping message without a thread object immediately
   after receiving a colored thread.  A node which receives a label
   mapping message that does not have a thread object will not rewind
   the thread.

5.2.  Using old path while looping on new path

   When a route changes, one might want to continue to use the old path
   if the new route is looping.  This is achieved simply by holding the
   label assigned to the downstream link on the old path until the
   thread being extended on the new route gets rewound.  This is an
   implementation choice.

5.3.  How to deal with ordered downstream allocation

   The thread mechanism can be also adapted to ordered downstream
   allocation mode (or the egress-initiated ordered control) by
   regarding the event of newly receiving of a label mapping message [4]
   from the next hop as a next hop acquisition event.

   Note that a node which doesn't yet have an incoming link behaves as a
   leaf.  In the case where the tree is being initially built up (e.g.,
   the egress node has just come up), each node in turn will behave as a
   leaf for a short period of time.

5.4.  How to realize load splitting

   A leaf node can easily perform load splitting by setting up two
   different LSPs for the same FEC.  The downstream links for the two
   LSPs are simply assigned different colors.  The thread algorithm now
   prevents a loop in either path, but also allows the two paths to have
   a common downstream node.

   If some intermediate node wants to do load splitting, the following
   modification is made.  Assume that there are multiple next hops for
   the same FEC.  If there are n next hops for a particular FEC, the set
   of incoming links for that FEC's LSP can be partitioned into n
   subsets, where each subset can be mapped to a distinct outgoing link.



Ohba, et al.                  Experimental                     [Page 15]

RFC 3063             MPLS Loop Prevention Mechanism        February 2001


   This provides n LSPs for the FEC.  Each such LSP uses a distinct
   color for its outgoing link.  The thread algorithm now prevents a
   loop in any of the paths, but also allows two or more of the paths to
   have a common downstream node.

   In this case, an interesting situation may happen.  Let's say that in
   Fig.12, node B has two incoming links, i1 and i2, and two outgoing
   links, o1 and o2, such that i1 is mapped to o1, while i2 is mapped to
   o2.

   If a blue thread received on i1 and extended on o1 is again received
   at node B on i2, the blue thread is not regarded as forming a loop,
   since i1 and i2 are regarded as belonging to different subsets.
   Instead, the blue thread received on i2 is extended on o2.  If the
   thread extended on o2 is rewound, a single loop-free LSP which
   traverses node B twice is established.

           +------------------...--------------------+
           .        (bl,3)          (bl,4)           |
           .     ----[i1]---+     +--[o1]---> .... --+
           .                 \   /
           .                  v /
           |                   B
           |
           +-----------[i2]--->B----[o2]--->
                     (bl,10)+      (bl,11)


            Fig.12  Load splitting at intermediate node

   There is another type of load splitting, in which packets arrived at
   single incoming link can be label switched to any one of multiple
   outgoing links.  This case does not seem to be a good load-splitting
   scheme, since the packet order in the same FEC is not preserved.
   Thus, this document does not focus on this case.

   Whether that's a good type of load splitting or not, the fact remains
   that ATM-LSRs cannot load split like this because ATM switches just
   don't have the capability to make forwarding decisions on a per-
   packet basis.

6.  Why this works

6.1.  Why a thread with unknown hop count is extended

   In the algorithm, a thread of unknown hop count is extended when a
   thread loop is detected.  This reduces the number of loop prevention




Ohba, et al.                  Experimental                     [Page 16]

RFC 3063             MPLS Loop Prevention Mechanism        February 2001


   messages by merging threads (of known hop count) that are flowing
   inside or outside the loop.  See Appendix A.12.

6.2.  Why a rewound thread cannot contain a loop

6.2.1.  Case1: LSP with known link hop counts

   How can we be sure that an established path does not contain a loop
   when the outgoing link hop count is NOT "unknown"?

   Consider a sequence of LSRs <R1, ..., Rn>, such that there is a loop
   traversing the LSRs in the sequence.  (I.e., packets from R1 go to
   R2, then to R3, etc., then to Rn, and then from Rn to R1.)

   Suppose that the thread hop count of the link between R1 and R2 is k.
   Then by the above procedures, the hop counts between Rn and R1 must
   be k+n-1.  But the algorithm also ensures that if a node has an
   incoming hop count of j, its outgoing link hop count must be at least
   of j+1.  Hence, if we assume that the LSP established as a result of
   thread rewinding contains a loop, the hop counts between R1 and R2
   must be at least k+n.  From this we may derive the absurd conclusion
   that n=0, and we may therefore conclude that there is no such
   sequence of LSRs.

6.2.1.  Case2: LSP with unknown link hop counts

   An established path does not contain a loop as well, when the
   outgoing link hop count is "unknown".  This is because a colored
   thread of unknown hop count is never rewound unless it reaches
   egress.

6.3.  Why L3 loop is detected

   Regardless of whether the thread hop count is known or unknown, if
   there is a loop, then some node in the loop will be the last node to
   receive a thread over a new incoming link.  This thread will always
   arrive back at that node, without its color having changed.  Hence
   the loop will always be detected by at least one of the nodes in the
   loop.

6.4.  Why L3 loop is not mis-detected

   Since no node ever extends the same colored thread downstream twice,
   a thread loop is not detected unless there actually is an L3 routing
   loop.






Ohba, et al.                  Experimental                     [Page 17]

RFC 3063             MPLS Loop Prevention Mechanism        February 2001


6.5.  How a stalled thread automatically recovers from loop

   Once a thread is stalled in a loop, the thread (or the path setup
   request) effectively remains in the loop, so that a path
   reconfiguration (i.e., thread withdrawing on the old path and thread
   extending on the new path) can be issued from any node that may
   receive a route change event so as to break the loop.

6.6.  Why different colored threads do not chase each other

   In the algorithm, multiple thread color and/or hop count updates may
   happen if several leaf nodes start extending threads at the same
   time.  How can we prevent multiple threads from looping unlimitedly?

   First, when a node finds that a thread forms a loop, it creates a new
   thread of hop count "unknown".  All the looping threads of a known
   hop count which later arrive at the node would be merged into this
   thread.  Such a thread behaves like a thread absorber.

   Second, the "thread extending with changing color" prevents two
   threads from chasing each other.

   Suppose that a received thread were always extended without changing
   color.  Then we would encounter the following situation.

                                G        Y
                                |        |
                                v        v
                                R1------>R2
                                ^        |
                                |        v
                                R4<------R3

                   Fig.13   Example of thread chasing

   In Fig.13, (1) node G acquires R1 as a next hop, and starts to extend
   a green thread of hop count 1, (2) node Y acquires R2 as a next hop,
   and starts to extend a yellow thread of hop count 1, and (3) both
   node G and node Y withdraws their threads before these threads go
   round.

   In this case, the yellow and green threads would go round and get
   back to R2 and R1, respectively.  When the threads get back to R2 and
   R1, however, the incoming links that store the yellow and green
   colors no longer exist.  As a result, the yellow and green threads
   would chase each other forever in the loop.





Ohba, et al.                  Experimental                     [Page 18]

RFC 3063             MPLS Loop Prevention Mechanism        February 2001


   However, since we have the "extending with changing color" mechanism,
   this does not actually happen.  When a green thread is received at
   R2, R2 extends the thread with changing color, i.e., creates a new
   red thread and extends it.  Similarly, when a yellow thread is
   received at R1, R1 creates a new purple thread and extends it.  Thus,
   the thread loop is detected even after node G and node Y withdraw
   threads.  This ensures that a thread is extended around the loop
   which has a color assigned by some node that is in the loop.

   There is at least one case even the "extending with changing color"
   mechanism cannot treat, that is, the "self-chasing" in which thread
   extending and thread withdrawing with regard to the same thread chase
   each other in a loop.  This case would happen when a node withdraw a
   thread immediately after extending it into an L3 loop.

   A heuristics for self-chasing is to delay the execution of thread
   withdrawing at an initiating node of the thread withdrawing.  Anyway,
   the thread TTL mechanism can eliminate any kind of thread looping.

7.  Loop prevention examples

   In this section, we show two examples to show how the algorithm can
   prevent LSP loops in given networks.

   We assume that the ordered downstream-on-demand allocation is
   employed, that all the LSPs are with regard to the same FEC, and that
   all nodes are VC-merge capable.

7.1.  First example

   Consider an MPLS network shown in Fig.14 in which an L3 loop exists.
   Each directed link represents the current next hop of the FEC at each
   node.  Now leaf nodes R1 and R6 initiate creation of an LSP.

               R11 ------- R10 <-------------------- R9
                |           |                         ^
                |           |                         |
                |           |                         |
                v           v                         |
                R1 -------> R2 --------> R3 --------> R4 --------- R5
              [leaf]                     ^
                                         |
                                         |
                                         |
                R6 -------> R7 --------> R8
              [leaf]

                      Fig. 14   Example MPLS network (1)



Ohba, et al.                  Experimental                     [Page 19]

RFC 3063             MPLS Loop Prevention Mechanism        February 2001


   Assume that R1 and R6 send a label request message at the same time,
   and that the initial thread TTL is 255.  First we show an example of
   how to prevent LSP loops.

   A set of thread attributes is represented by (color, hop count, TTL).

   The request from R1 and R6 contains (re,1,255) and (bl,1,255),
   respectively.

   Assume that R3 receives the request originated from R1 before
   receiving the request originated from R6.  When R3 receives the first
   request with red thread, R3 forwards it with (re,3,253) without
   changing thread color, since both the receiving incoming link and the
   outgoing link are newly created.  Then R3 receives the second request
   with blue thread.  In this time, the outgoing link is already exists.
   Thus, R3 performs thread extending with changing color, i.e., creates
   a new brown thread and forwards the request with (br,4,255).

   When R2 receives the request from R10 with (re,6,250), it finds that
   the red thread forms a loop, and stalls the red thread.  Then, R2
   creates a purple thread of hop count unknown and extends it
   downstream by sending a request with (pu,U,255) to R3, where "U"
   represents "unknown".

   After that, R2 receives another request from R10 with (br,7,252).
   The brown thread is merged into purple thread.  R2 sends no request
   to R3.

   On the other hand, the purple thread goes round without changing
   color through existing links, and R2 finds the thread loop and stalls
   the purple thread.  Since the received thread hop count is unknown,
   no thread is created any more.  In this case no thread rewinding
   occurs.  The current state of the network is shown in Fig.15.


















Ohba, et al.                  Experimental                     [Page 20]

RFC 3063             MPLS Loop Prevention Mechanism        February 2001


           *: location of thread stalling

                                      (pu,U)
               R11 ------- R10 <-------------------- R9
                |           |                         ^
                |           |(pu,U)*                  |
                |           |                         |(pu,U)
                v           v                         |
                R1 -------> R2 --------> R3 --------> R4 --------- R5
              [leaf] (re,1)      (pu,U)  ^  (pu,U)
                                         |
                                         | (bl,3)
                                         |
                R6 -------> R7 --------> R8
              [leaf] (bl,1)      (bl,2)


                            Fig.15  The network state

   Then R10 changes its next hop from R2 to R11.

   Since R10 has a purple thread on the old downstream link, it first
   sends a path teardown message to the old next hop R2 for withdrawing
   the purple thread.  Next, it creates a green thread of hop count
   unknown and sends a request with (gr,U,255) to R11.

   When R2 receives the teardown message from R10, R2 removes the
   stalled incoming link between R10 and R2.

   On the other hand, the green thread reaches R1 and Hmax is updated
   from zero to unknown.  In this case, R1 performs thread extending
   with changing color since the thread is received on a new incoming
   link but extended on the already existing outgoing link.  As a
   result, R1 creates an orange thread of hop count unknown and extend
   it to R2.

   The orange thread goes round through existing links without changing
   color, and finally it is stalled at R1.

   The state of the network is now shown in Fig.16.











Ohba, et al.                  Experimental                     [Page 21]

RFC 3063             MPLS Loop Prevention Mechanism        February 2001


           *: location of thread stalling

                    (or,U)             (or,U)
               R11 <------ R10 <-------------------- R9
                |           |                         ^
                |(or,U)*    |                         |
                |           |                         |(or,U)
                v           |                         |
                R1 -------> R2 --------> R3 --------> R4 --------- R5
              [leaf] (or,U)      (or,U)  ^  (or,U)
                                         |
                                         | (bl,3)
                                         |
                R6 -------> R7 --------> R8
              [leaf] (bl,1)      (bl,2)


                            Fig.16  The network state

   Then R4 changes its next hop from R9 to R5.

   Since R4 is extending an orange thread, it first sends a teardown
   message to the old next hop R9 to withdraw the orange thread on the
   old route.  Next, it creates a yellow thread of hop count unknown,
   and sends a request message with (ye,U,255) to R5.

   Since R5 is the egress node, the yellow thread rewinding starts.  R5
   returns a label mapping message.  The thread rewinding procedure is
   performed at each node, as the label mapping message is returned
   upstream hop-by-hop.

   If R1 receives a label mapping message before receiving the orange
   thread's withdrawal from R11, R1 returns a label mapping message to
   R11.  On receiving the orange thread's withdrawal, R1 will create a
   transparent thread and extend it by sending an update message with
   (tr,1,255) in order to notify downstream of the known hop count.

   Otherwise, if R1 receives the orange thread's withdrawal before
   receiving a label mapping message, R1 removes the stalled incoming
   orange link and waits for rewinding of the outgoing orange thread.
   Finally, when R1 receives a label mapping message from R2, it creates
   a transparent thread (tr,1,255) and extend it downstream.

   In both cases, a merged LSP ((R1->R2),(R6->R7->R8))->R3->R4->R5) is
   established and every node obtains the correct link hop count.  The
   final network state is shown in Fig.17.





Ohba, et al.                  Experimental                     [Page 22]

RFC 3063             MPLS Loop Prevention Mechanism        February 2001


               R11 <------ R10 <-------------------- R9
                |           |                         |
                |           |                         |
                |           |                         |
                v           |                         |
                R1 -------> R2 --------> R3 --------> R4 --------> R5
              [leaf] (tr,1)      (tr,2)  ^  (tr,4)        (tr,5)
                                         |
                                         | (tr,3)
                                         |
                R6 -------> R7 --------> R8
              [leaf] (tr,1)      (tr,2)


                       Fig.17  The final network state

7.2.  Second example

                          +----- R6----> R7-----+
                          |                     |
                          |                     v
                   R1---->R2                    R4----->R5
                          |                     ^
                          |                     |
                          +--------->R3---------+


                   Fig.18   Example MPLS network (2)

   Assume that in Fig.18, there is an established LSP R1->R2->R3->R4-
   >R5, and the next hop changes at R2 from R3 to R6.  R2 sends a
   request to R6 with a red thread (re,2,255).  When the request with
   (re,4,253) reaches R4, it extends the thread to R5 with changing
   color.  Thus, a new green thread is created at R4 and extended to R5
   by sending an update message with (gr,5,255).

   When R5 receives the update, it updates the incoming link hop count
   to 5 and returns an ack (or a notification message with a success
   code) for the update.  When R4 receives the ack for the update, it
   returns a label mapping message to R7.

   When R2 receives the label mapping message on the new route, it sends
   a teardown message to R3.  When R4 receives the teardown message, it
   does not sends an update to R5 since Hmax does not change.  Now an
   established LSP R1->R2->R6->R7->R4->R5 is obtained.

   Then, the next hop changes again at R2 from R6 to R3.




Ohba, et al.                  Experimental                     [Page 23]

RFC 3063             MPLS Loop Prevention Mechanism        February 2001


   R2 sends a request with a blue thread (bl,2,255) to R3.  R3 forwards
   the request with (bl,3,254) to R4.

   When R4 receives the request, it immediately returns a label mapping
   message to R3 since Hmax does not change.

   When R2 receives the label mapping message on the new route, it sends
   a teardown message to R6.  The teardown message reaches R4,
   triggering an update message with a transparent thread (tr,4,255) to
   R5, since Hmax decreases from 4 to 3.  R5 updates the incoming link
   hop count to 4 without returning an ack.

8. Thread control block

   A thread control block (TCB) is maintained per LSP at each node and
   may contain the following information:

         - FEC
         - State
         - Incoming links
             Each incoming link has the following attributes:
               o  neighbor: upstream neighbor node address
                 o  color: received thread color
                 o  hop count: received thread hop count
               o  label
               o  S-flag: indicates a stalled link
         - Outgoing links
             Each outgoing link has the following attributes:
               o  neighbor: downstream neighbor node address
                 o  color: received thread color
                 o  hop count: received thread hop count
               o  label
               o  C-flag: indicates the link to the current next hop

   If a transparent thread is received on an incoming link for which no
   label is assigned yet or a non-transparent color is stored, discard
   the thread without entering the FSM.  An error message may be
   returned to the sender.

   Whenever a thread is received on an incoming link, the following
   actions are taken before entering the FSM: (1) Store the received
   thread color and hop count on the link, replacing the old thread
   color and hop count, and (2) set the following flags that are used
   for an event switch within "Recv thread" event (see section 8.1).







Ohba, et al.                  Experimental                     [Page 24]

RFC 3063             MPLS Loop Prevention Mechanism        February 2001


      o  Color flag (CL-flag):
            Set if the received thread is colored.
      o  Loop flag (LP-flag):
            Set if the received thread forms a loop.
      o  Arrived on new link flag (NL-flag):
            Set if the received thread arrives on a new incoming link.

   If LP-flag is set, there must be an incoming link L, other than the
   receiving link, which stores the same thread color as the received
   one.  The TCB to which link L belongs is referred to as the
   "detecting TCB".  If the receiving LSR is VC-merge capable, the
   detecting TCB and the receiving TCB is the same, otherwise, the two
   TCBs are different.

   Before performing a thread extending, the thread TTL is decremented
   by one.  If the resulting TTL becomes zero, the thread is not
   extended but silently discarded.  Otherwise, the thread is extended
   and the extended thread hop count and color are stored into the
   outgoing link.

   When a node receives a thread rewinding event, if the received thread
   color and the extending thread color are different, it discards the
   event without entering the FSM.

8.1. Finite state machine

   An event which is "scheduled" by an action in an FSM must be passed
   immediately after the completion of the action.

   The following variables are used in the FSM:

      o  Ni: number of unstalled incoming links
      o  Hmax: largest incoming hop count
      o  Hout: hop count of the outgoing link for the current next hop
      o  Hrec: hop count of the received thread

   In the FSM, if Hmax=unknown, the value for (Hmax+1) becomes the value
   reserved for unknown hop count plus 1.  For example, if
   Hmax=unknown=255, the value (Hmax+1) becomes 256.

   A TCB has three states; Null, Colored, and Transparent.  When a TCB
   is in state Null, there is no outgoing link and Ni=0.  The state
   Colored means that the node is extending a colored thread on the
   outgoing link for the current next hop.  The state Transparent means
   that the node is the egress node or the outgoing link is transparent.

   The flag value "1" represents the flag is set, "0" represents the
   flag is not set, and "*" means the flag value is either 1 or 0.



Ohba, et al.                  Experimental                     [Page 25]

RFC 3063             MPLS Loop Prevention Mechanism        February 2001


   The FSM allows to have one transparent outgoing link on the old next
   hop and one colored outgoing link on the current next hop.  However,
   it is not allowed to have a colored outgoing link on the old next
   hop.

   State Null:

 Event         Action                                          New state
 Recv thread
   Flags
  CL LP NL
  0  *  *      Do nothing.                                     No change
  1  0  *      If the node is egress, start thread rewinding Transparent
               and change the color of the receiving link to
               transparent.
               Otherwise, extend the received thread without   Colored
               changing color.
  1  1  *      Stall the received thread; if Hrec<unknown,     No change
               schedule "Reset to unknown" event for the
               detecting TCB.

 Next hop      If eligible-leaf, create a colored thread and   Colored
 acquisition   extend it.

 Others        Silently ignore the event.                      No change

State Colored:

 Event         Action                                          New state
 Recv thread
     Flags
   CL LP NL
   0  *  *     If Hmax+1<Hout<unknown, create a colored        No change
               thread and extend it.  Otherwise, do nothing.
   1  0  *     If Hmax<Hout, merge the received thread.        No change
               Otherwise, extend the thread with (if NL=1)
               or without (if NL=0) changing color.
   1  1  *     Stall the received thread.
               If Ni=0 and the node is not an eligible leaf,   Null
               initiate thread withdrawing.
               If Ni>0 and Hrec<unknown, schedule "Reset to    No change
               unknown" event for the detecting TCB.
               Otherwise, do nothing.                          No change








Ohba, et al.                  Experimental                     [Page 26]

RFC 3063             MPLS Loop Prevention Mechanism        February 2001


 Rewound       Propagate thread rewinding to previous hops   Transparent
               that are extending a colored thread; change
               the colors stored in all incoming and outgoing
               links to transparent; if Hmax+1<Hout, extend
               transparent thread.  Withdraw the thread on
               the outgoing link for which C-flag=0.

 Withdrawn     Remove the corresponding incoming link.
               If Ni=0 and the node is not an eligible leaf,   Null
               propagate thread withdrawing to all next hops.
               Otherwise, if Hmax+1<Hout<unknown, create       No change
               a colored thread and extend it.
               Otherwise, do nothing.                          No change

 Next hop      If there is already an outgoing link for the  Transparent
 acquisition   next hop, do nothing.  (This case happens only
               when the node retains the old path.)
               Otherwise, create a colored thread and extend   No change
               it.

 Next hop      If the outgoing link is transparent and the     No change
 loss          node is allowed to retain the link and the
               next hop is alive, do nothing.
               Otherwise, take the following actions.
               Initiate thread withdrawing for the next hop;
               if the node becomes a new egress, schedule
               "Rewound" event for this TCB.
               If Ni=0, move to Null.                          Null
               Otherwise, do nothing.                          No change

 Reset to      Create a colored thread of hop count unknown    No change
 unknown       and extend it.

 Others        Silently ignore the event.                      No change

State Transparent:

 Event          Action                                         New state
 Recv thread
    Flags
   CL LP NL
   0  *  *     If Hmax+1<Hout, extend a transparent thread.    No change
   1  0  *     If the node is egress or if Hmax<Hout, change   No change
               the color of the receiving link to transparent
               and start thread rewinding.
               Otherwise, extend the thread with (if NL=1)     Colored
               or without (if NL=0) changing color.




Ohba, et al.                  Experimental                     [Page 27]

RFC 3063             MPLS Loop Prevention Mechanism        February 2001


 Withdrawn     Remove the corresponding incoming link.
               If Ni=0 and the node is not an eligible leaf,   Null
               propagate thread withdrawing to next hops.
               Otherwise, if Hmax+1<Hout, create               No change
               a transparent thread and extend it.
               Otherwise, do nothing.                          No change

 Next hop      Create a colored thread and extend it.          Colored
 acquisition

 Next hop      If the node is allowed to retain the outgoing   No change
 loss          link and the next hop is alive, do nothing.
               Otherwise, take the following actions.
               Initiate thread withdrawing.
               If Ni=0, move to Null.                          Null
               Otherwise, do nothing.                          No change

 Others        Silently ignore the event.                      No change

9.  Comparison with path-vector/diffusion method

   o  Whereas the size of the path-vector increases with the length of
      the LSP, the sizes of the threads are constant.  Thus the size
      of messages used by the thread algorithm are unaffected by the
      network size or topology.  In addition, the thread merging
      capability reduces the number of outstanding messages.  These
      lead to improved scalability.

   o  In the thread algorithm, a node which is changing its next hop
      for a particular LSP must interact only with nodes that are
      between it and the LSP egress on the new path.  In the
      path-vector algorithm, however, it is necessary for the node to
      initiate a diffusion computation that involves nodes which do
      not lie between it and the LSP egress.

      This characteristic makes the thread algorithm more robust.  If
      a diffusion computation is used, misbehaving nodes which aren't
      even in the path can delay the path setup.  In the thread
      algorithm, the only nodes which can delay the path setup are
      those nodes which are actually in the path.

   o  The thread algorithm is well suited for use with both the
      ordered downstream-on-demand allocation and ordered downstream
      allocation.  The path-vector/diffusion algorithm, however, is
      tightly coupled with the ordered downstream allocation.






Ohba, et al.                  Experimental                     [Page 28]

RFC 3063             MPLS Loop Prevention Mechanism        February 2001


   o  The thread algorithm is retry-free, achieving quick path
      (re)configuration.  The diffusion algorithm tends to delay the
      path reconfiguration time, since a node at the route change
      point must to consult all its upstream nodes.

   o  In the thread algorithm, the node can continue to use the old
      path if there is an L3 loop on the new path, as in the
      path-vector algorithm.

10.  Security Considerations

   The use of the procedures specified in this document does not have
   any security impact other than that which may generally be present
   in the use of any MPLS procedures.

11.  Intellectual Property Considerations

   Toshiba and/or Cisco may seek patent or other intellectual property
   protection for some of the technologies disclosed in this document.
   If any standards arising from this document are or become protected
   by one or more patents assigned to Toshiba and/or Cisco, Toshiba
   and/or Cisco intend to disclose those patents and license them on
   reasonable and non-discriminatory terms.

12.  Acknowledgments

   We would like to thank Hiroshi Esaki, Bob Thomas, Eric Gray, and
   Joel Halpern for their comments.























Ohba, et al.                  Experimental                     [Page 29]

RFC 3063             MPLS Loop Prevention Mechanism        February 2001


13.  Authors' Addresses

   Yoshihiro Ohba
   Toshiba Corporation
   1, Komukai-Toshiba-cho, Saiwai-ku
   Kawasaki 210-8582, Japan

   EMail: yoshihiro.ohba@toshiba.co.jp


   Yasuhiro Katsube
   Toshiba Corporation
   1, Toshiba-cho, Fuchu-shi,
   Tokyo, 183-8511, Japan

   EMail: yasuhiro.katsube@toshiba.co.jp


   Eric Rosen
   Cisco Systems, Inc.
   250 Apollo Drive
   Chelmsford, MA, 01824

   EMail: erosen@cisco.com


   Paul Doolan
   Ennovate Networks
   330 Codman Hill Rd
   Marlborough MA 01719

   EMail: pdoolan@ennovatenetworks.com

14.  References

   [1] Callon, R., et al., "A Framework for Multiprotocol Label
       Switching", Work in Progress.

   [2] Davie, B., Lawrence, J., McCloghrie, K., Rosen, E., Swallow, G.,
       Rekhter, Y. and P. Doolan, "MPLS using LDP and ATM VC Switching",
       RFC 3035, January 2001.

   [3] Rosen, E., et al., "A Proposed Architecture for MPLS", Work in
       Progress.

   [4] Andersson, L., Doolan, P., Feldman, N., Fredette, A. and B.
       Thomas, "LDP Specification", RFC 3036, January 2001.




Ohba, et al.                  Experimental                     [Page 30]

RFC 3063             MPLS Loop Prevention Mechanism        February 2001


Appendix A - Further discussion of the algorithm

   The purpose of this appendix is to give a more informal and tutorial
   presentation of the algorithm, and to provide some of the motivation
   for it.  For the precise specification of the algorithm, the FSM
   should be taken as authoritative.

   As in the body of the document, we speak as if there is only one LSP;
   otherwise we would always be saying "... of the same LSP".  We also
   consider only the case where the algorithm is used for loop
   prevention, rather than loop detection.

A.1. Loop Prevention the Brute Force Way

   As a starting point, let's consider an algorithm which we might call
   "loop prevention by brute force".  In this algorithm, every path
   setup attempt must go all the way to the egress and back in order for
   the path to be setup.  This algorithm is obviously loop-free, by
   virtue of the fact that the setup messages actually made it to the
   egress and back.

   Consider, for example, an existing LSP B-C-D-E to egress node E.  Now
   node A attempts to join the LSP.  In this algorithm, A must send a
   message to B, B to C, C to D, D to E.  Then messages are sent from E
   back to A.  The final message, from B to A, contains a label binding,
   and A can now join the LSP, knowing that the path is loop-free.

   Using our terminology, we say that A created a thread and extended it
   downstream.  The thread reached the egress, and then rewound.

   We needn't assume, in the above example, that A is an ingress node.
   It can be any node which acquires or changes its next hop for the LSP
   in question, and there may be nodes upstream of it which are also
   trying to join the LSP.

   It is clear that if there is a loop, the thread never reaches the
   egress, so it does not rewind.  What does happen?  The path setup
   messages just keep traveling around the loop.  If one keeps a hop
   count in them, one can ensure that they stop traveling around the
   loop when the hop count reaches a certain maximum value.  That is,
   when one receives a path setup message with that the maximum hop
   count value, one doesn't send a path setup message downstream.

   How does one recover from this situation of a looping thread?  In
   order for L3 routing to break the loop, some node in the loop MUST
   experience a next hop change.  This node will withdraw the thread





Ohba, et al.                  Experimental                     [Page 31]

RFC 3063             MPLS Loop Prevention Mechanism        February 2001


   from its old next hop, and extend a thread down its new next hop.  If
   there is no longer a loop, this thread now reaches the egress, and
   gets rewound.

A.2. What's Wrong with the Brute Force Method?

   Consider this example:

                A
                |
                B--D--E
                |
                C

   If A and C both attempt to join the established B-D-E path, then B
   and D must keep state for both path setup attempts, the one from A
   and the one from C.  That is, D must keep track of two threads, the
   A-thread and the C-thread.  In general, there may be many more nodes
   upstream of B who are attempting to join the established path, and D
   would need to keep track of them all.

   If VC merge is not being used, this isn't actually so bad.  Without
   VC merge, D really must support one LSP for each upstream node
   anyway.  If VC merge is being used, however, supporting an LSP
   requires only that one keep state for each upstream link.  It would
   be advantageous if the loop prevention technique also required that
   the amount of state kept by a node be proportional to the number of
   upstream links which thenode has, rather than to the number of nodes
   which are upstream in the LSP.

   Another problem is that if there is a loop, the setup messages keep
   looping.  Even though a thread has traversed some node twice, the
   node has no way to tell that a setup message it is currently
   receiving is part of the same thread as some setup message it
   received in the past.

   Can we modify this brute force scheme to eliminate these two
   problems?  We can.  To show how to do this, we introduce two notions:
   thread hop count, and thread color.

A.3. Thread Hop Count

   Suppose every link in an LSP tree is labeled with the number of hops
   you would traverse if you were to travel backwards (upstream) from
   that link to the leaf node which is furthest upstream of the link.

   For example, the following tree would  have its links labeled as
   follows:



Ohba, et al.                  Experimental                     [Page 32]

RFC 3063             MPLS Loop Prevention Mechanism        February 2001


         1   2
       A---B---C       K
               |       |
               |3      |1
               |       |
               | 4   5 | 6   7
               D---G---H---I---J
               |
               |2
             1 |
           E---F

   Call these the "link hop counts".

   Links AB, EF, KH are labeled one, because you can go only one hop
   upstream from these links.  Links BC, and FD are labeled 2, because
   you can go 2 hops upstream from these links.  Link DG is labeled 4,
   because it is possible to travel 4 hops upstream from this link, etc.

   Note that at any node, the hop count associated with the downstream
   link is one more than the largest of the hop counts associated with
   the upstream links.

   Let's look at a way to maintain these hop counts.

   In order to maintain the link hop counts, we need to carry hop counts
   in the path setup messages.  For instance, a node which has no
   upstream links would assign a hop count of 1 to its downstream link,
   and would store that value into the path setup messages it sends
   downstream.  Once the value is stored in a path setup message, we may
   refer to it has a "thread hop count".

   When a path setup message is received, the thread hop count is stored
   as the link hop count of the upstream link over which the message was
   received.

   When a path setup message is sent downstream, the downstream link's
   hop count (and the thread hop count) is set to be one more than the
   largest of the incoming link hop counts.

   Suppose a node N has some incoming links and an outgoing link, with
   hop counts all set properly, and N now acquires a new incoming link.
   If, and only if, the link hop count of the new incoming link is
   greater than that of all of the existing incoming links, the
   downstream link hop count must be changed.  In this case, control
   messages must be sent downstream carrying the new, larger thread hop
   count.




Ohba, et al.                  Experimental                     [Page 33]

RFC 3063             MPLS Loop Prevention Mechanism        February 2001


   If, on the other hand, N acquires a new incoming link with a link hop
   count that is less than or equal to the link hop count of all
   existing incoming links, the downstream link hop count remains
   unchanged, and no messages need be sent downstream.

   Suppose N loses the incoming link whose hop count was the largest of
   any of the incoming links.  In this case, the downstream link hop
   count must be made smaller, and messages need to be sent downstream
   to indicate this.

   Suppose we were not concerned with loop prevention, but only with the
   maintenance of the hop counts.  Then we would adopt the following
   rules to be used by merge points:

A.3.1   When a new incoming thread is received, extend it downstream if
   and only if its hop count is the largest of all incoming threads.

A.3.2   Otherwise, rewind the thread.

A.3.3   An egress node would, of course, always rewind the thread.

A.4. Thread Color

   Nodes create new threads as a result of next hop changes or next hop
   acquisitions.  Let's suppose that every time a thread is created by a
   node, the node assigns a unique "color" to it.  This color is to be
   unique in both time and space: its encoding consists of an IP address
   of the node concatenated with a unique event identifier from a
   numbering space maintained by the node.  The path setup messages that
   the node sends downstream will contain this color.  Also, when the
   node sends such a message downstream, it will remember the color, and
   this color becomes the color of the downstream link.

   When a colored message is received, its color becomes the color of
   the incoming link.  The thread which consists of messages of a
   certain color will be known as a thread of that color.

   When a thread is rewound (and a path set up), the color is removed.
   The links become transparent, and we will sometimes speak of an
   established LSP as being a "transparent thread".

   Note that packets cannot be forwarded on a colored link, but only on
   a transparent link.

   Note that if a thread loops, some node will see a message, over a
   particular incoming link, with a color that the node has already seen
   before.  Either the node will have originated the thread of that
   color, or it will have a different incoming link which already has



Ohba, et al.                  Experimental                     [Page 34]

RFC 3063             MPLS Loop Prevention Mechanism        February 2001


   that color.  This fact can be used to prevent control messages from
   looping.  However, the node would be required to remember the colors
   of all the threads passing through it which have not been rewound or
   withdrawn.  (I.e., it would have to remember a color for each path
   setup in progress.)

A.5. The Relation between Color and Hop Count

   By combining the color mechanism and the hop count mechanism, we can
   prevent loops without requiring any node to remember more than one
   color and one hop count per link for each LSP.

   We have already stated that in order to maintain the hop counts, a
   node needs to extend only the thread which has the largest hop count
   of any incoming thread.  Now we add the following rule:

A.5.1   When extending an incoming thread downstream, that thread's
   color is also passed downstream (I.e., the downstream link's color
   will be the same as the color of the upstream link with largest hop
   count.)

   Note that at a given node, the downstream link is either transparent
   or it has one and only one color.

A.5.2   If a link changes color, there is no need to remember the old
   color.

   We now define the concept of "thread merging":

A.5.2   Suppose a colored thread arrives at a node over an incoming
   link, the node already has an incoming thread with the same or larger
   hop count, and the node has an outgoing colored thread.  In this
   case, we may say that the new incoming thread is "merged" into the
   outgoing thread.

   Note that when an incoming thread is merged into an outgoing thread,
   no messages are sent downstream.

A.6. Detecting Thread Loops

   It can now be shown that if there is a loop, there will always either
   be some node which gets two incoming threads of the same color, or
   the colored thread will return to its initiator.  In this section, we
   give several examples that may provide an intuitive understanding of
   how the thread loops are detected.






Ohba, et al.                  Experimental                     [Page 35]

RFC 3063             MPLS Loop Prevention Mechanism        February 2001


         1   2
       A---B---C       K
               |       |
               |3      |1
               |       |
               | 4   5 | 6   7
               D---G---H---I---J
               |
               |2
             1 |
           E---F

   Returning to our previous example, let's set what would happen if H
   changed its next hop from I to E.  H now creates a new thread, and
   assigns it a new color, say, red.  Since H has two incoming link,
   with hop counts 1 and 5 respectively, it assigns hop count 6 to its
   new downstream link, and attempts a path setup through E.

   E now has an incoming red thread with hop count 6.  Since E's
   downstream link hop count is now only 1, it must extend the red
   thread to F, with hop count 7.  F then extends the red thread to D
   with hop count 8, D to G with hop count 9, and G to H with hop count
   10.

   The red thread has now returned to its initiator, and the loop is
   detected.

   Suppose though that before the red thread makes it back to H, G
   changes its next hop from H to E.  Then G will extend the red thread
   to E.  But E already has an incoming red link (from H), so the loop
   is detected.

   Let's now define the notion of a "stalled thread".  A stalled thread
   is a thread which is merged into the outgoing thread, even though the
   outgoing thread has a smaller link hop count.

   When a thread loop is detected, the thread becomes stalled.

A.6.1   When a loop is detected due to a thread of a particular color
   traversing some node twice, we will say that the thread is "stalled"
   at the node.  More precisely, it is the second appearance of the
   thread which is stalled.  Note that we say that a thread is
   traversing a node twice if the thread is received by that node on an
   incoming link, but either there is another incoming link with the
   same color, or the color is one that was assigned by the node itself.






Ohba, et al.                  Experimental                     [Page 36]

RFC 3063             MPLS Loop Prevention Mechanism        February 2001


A.7. Preventing the Setup of Looping LSPS

   The mechanism to be used for preventing the setup of looping LSPs
   should now be obvious.  If node M is node N's next hop, and N wishes
   to set up an LSP (or to merge into an LSP which already exists at M),
   then N extends a thread to M.

   M first checks to see if the thread forms a loop (see Appendix A.6),
   and if so, the thread is stalled.  If not, the following procedure is
   followed.

A.7.1   If M receives this thread, and M has a next hop, and either:

   -  M has no outgoing thread

   -  the incoming thread hop count is larger than the hop count of all
      other incoming threads,

   then M must extend the thread downstream.

A.7.2   On the other hand, if M receives this thread, and M has a next
   hop and there is another incoming thread with a larger hop count,
   then:

A.7.2.1 if the outgoing thread is transparent, M rewinds the new
   incoming thread.

A.7.2.2 if the outgoing thread is colored, M merges the new incoming
   thread into the outgoing thread, but does not send any messages
   downstream.

A.7.3   If M has not already assigned a label to N, it will assign one
   when, and only when, M rewinds the thread which N has extended to it.

A.7.4   If M merges the new thread into an existing colored outgoing
   thread, then the new incoming thread will rewind when, and only when,
   the outgoing thread rewinds.

A.8. Withdrawing Threads

A.8.1   If a particular node has a colored outgoing thread, and loses or
   changes its next hop, it withdraws the outgoing thread.

   Suppose that node N is immediately upstream of node M, and that N has
   extended a thread to M.  Suppose further that N then withdraws the
   thread.





Ohba, et al.                  Experimental                     [Page 37]

RFC 3063             MPLS Loop Prevention Mechanism        February 2001


A.8.2   If M has another incoming thread with a larger hop count, then M
   does not send any messages downstream.

A.8.3   However, if the withdrawn thread had the largest hop count of
   any incoming thread, then M's outgoing thread will no longer have the
   proper hop count and color.  Therefore:

A.8.3.1 M must now extend downstream the incoming thread with the
   largest hop count.  (This will cause it to forget the old downstream
   link hop count and color.)

A.8.3.2 The other incoming threads are considered to be merged into the
   thread which is extended.

A.8.4   When the last unstalled incoming thread is withdrawn, the
   outgoing thread must be withdrawn.

A.9. Modifying Hop Counts and Colors of Existing Threads

   We have seen the way in which the withdrawal of a thread may cause
   hop count and color changes downstream.  Note that if the hop count
   and/or color of an outgoing thread changes, then the hop count and
   color of the corresponding incoming thread at the next hop will also
   change.  This may result in a color and/or next hop change of the
   outgoing thread at that next hop.

A.9.1   Whenever there is a hop count change for any incoming thread, a
   node must determine whether the "largest hop count of any incoming
   thread" has changed as a result.  If so, the outgoing thread's hop
   count, and possibly color, will change as well, causing messages to
   be sent downstream.

A.10. When There is No Next Hop

A.10.1  If a particular node has a colored incoming thread, but has no
   next hop (or loses its next hop), the incoming thread is stalled.

A.11. Next Hop Changes and Pre-existing Colored Incoming Threads

   It is possible that a node will experience a next hop change or a
   next hop acquisition at a time when it has colored incoming threads.
   This happens when routing changes before path setup is complete.

A.11.1  If a node has a next hop change or a next hop acquisition at a
   time when it has colored incoming threads, it will create a thread
   with a new color, but whose hop count is one more than the largest of
   the incoming link hop counts.  It will then extend this thread
   downstream.



Ohba, et al.                  Experimental                     [Page 38]

RFC 3063             MPLS Loop Prevention Mechanism        February 2001


A.11.2  When this new thread is created and extended downstream, all
   incoming threads are merged into it.  Any incoming threads that were
   previously stalled are now considered to be "merged" rather than
   "stalled".

   That is, even though the outgoing thread has a different color than
   any of the incoming threads, the pre-existing incoming threads are
   all considered to have been merged into the new outgoing thread.
   This means that when the outgoing thread rewinds, the incoming
   threads will too.

   Note: it is still required to distinguish stalled incoming links from
   unstalled incoming links when thread withdrawing is performed.

A.12. How Many Threads Run Around a Loop?

   We have seen that when a loop is detected, the looping thread stalls.
   However, considering the following topology:

                   X--->A----->B<---Y
                        ^      |
                        |      v
                   W--->D<-----C<---Z

   In this example, there is a loop A-B-C-D-A.  However, there are also
   threads entering the loop from X, Y, Z, and W.  Once the loop is
   detected, there really is no reason why any other thread should have
   to wrap around the loop.  It would be better to simply mark presence
   of the loop in each node.

   To do this, we introduce the notion of the "unknown" hop count, U.
   This hop count value is regarded as being larger than any other hop
   count value.  A thread with hop count U will be known as a "U-
   thread".

A.12.1  When an incoming thread with a known hop count stalls, and there
   is an outgoing thread, we assign the hop count U to the outgoing
   thread, and we assign a new color to the outgoing thread as well.

   As a result, the next hop will then have an incoming U-thread, with
   the newly assigned color.  This causes its outgoing thread in turn to
   be assigned hop count U and the new color.  The rules we have already
   given will then cause each link in the loop to be assigned the new
   color and the hop count U.  When this thread either reaches its
   originator, or any other node which already has an incoming thread of
   the same color, it stalls.





Ohba, et al.                  Experimental                     [Page 39]

RFC 3063             MPLS Loop Prevention Mechanism        February 2001


   In our example above, this will cause the links AB, BC, CD, and DA to
   be given hop count U.

   Now let's add one more rule:

A.12.2  When a thread with a known hop count reaches a node that has a
   colored outgoing U-thread, the incoming thread merges into the
   outgoing thread.  (Actually, this is just a consequence of a rule
   which has already been given, since U is greater than any known hop
   count.)

   Then if W, X, Y, or Z attempt to extend a thread to D, A, B, or C
   respectively, those threads will immediately stall.  Once all the
   links are marked as being within a loop, no other threads are
   extended around the loop, i.e., no other setup messages will traverse
   the loop.

   Here is our example topology with the link hop counts that would
   exist during a loop:

                     1     U      1
                   X--->A----->B<---Y
                        ^      |
                      U |      |U
                        |      v
                   W--->D<-----C<---Z
                     1      U     1

A.13. Some Special Rules for Hop Count U

   When a U-thread encounters a thread with known hop count, the usual
   rules apply, remembering that U is larger than any known hop count
   value.

   However, we need to add a couple of special rules for the case when a
   U-thread encounters a U-thread.  Since we can't tell which of the two
   U-threads is really the longer, we need to make sure that each of the
   U-threads is extended.

A.13.1  If an incoming colored U-thread arrives at a node which already
   has an incoming U-thread of that color, or arrives at the node which
   created that U-thread, then the thread stalls.

   (Once a loop is detected, there is no need to further extend the
   thread.)






Ohba, et al.                  Experimental                     [Page 40]

RFC 3063             MPLS Loop Prevention Mechanism        February 2001


A.13.2  If an incoming colored U-thread arrives at a node which has a
   transparent outgoing U-thread to its next hop, the incoming thread is
   extended.

A.13.3  If an incoming colored U-thread arrives at a node which has a
   colored outgoing U-thread, and if the incoming link over which the
   thread was received was already an incoming link of the LSP, the
   thread is extended.

A.13.4  If an incoming colored U-thread arrives at a node which has a
   colored outgoing U-thread, and if the incoming link over which the
   thread was received was NOT already an incoming link of the LSP, a
   new U-thread is created and extended.  All the incoming threads are
   merged into it.  This is known in the main body of this document as
   "extending the thread with changing color".

   These rules ensure that an incoming U-thread is always extended (or
   merged into a new U-thread which then gets extended), unless it is
   already known to form a loop.

   What is the purpose of rule A.13.4?  There are certain cases where a
   loop can form, but where the node which created the looping thread is
   not part of the loop.  Rule A.13.4 ensures that when there is a loop,
   there will be a looping thread which was created by some node which
   is actually in the loop.  This in turn ensures that the loop will be
   detected well before the thread TTL expires.

   The rule of "extending the thread with changing color" is also
   applied when extending a thread with a known hop count.

A.13.5  When a received colored thread with a known hop count is
   extended, if the node has an outgoing thread, and if the incoming
   link over which the thread was received was NOT already an incoming
   link of the LSP, a new thread is created and extended.  All the
   incoming threads are merged into it.  This is an exceptional case of
   A.5.1.

A.14. Recovering From a Loop

   Here is our example topology again, in the presence of a loop.

                     1     U      1
                   X--->A----->B<---Y
                        ^      |
                      U |      |U
                        |      v
                   W--->D<-----C<---Z
                     1      U     1



Ohba, et al.                  Experimental                     [Page 41]

RFC 3063             MPLS Loop Prevention Mechanism        February 2001



   Suppose now that C's next hop changes from D to some other node E,
   thereby breaking the loop.  For simplicity, we will assume that E is
   the egress node.

   C will withdraw its outgoing U-thread from D (9.1).  It will also
   create a new thread (12.1), assign it a new color, assign it hop
   count U (the largest hop count of C's incoming threads), merge its
   two other incoming threads into the new thread (12.2), and extend the
   new thread to E, resulting the following configuration:

                     1     U      1
                   X--->A----->B<---Y
                        ^      |
                      U |      |U
                        |      v
                   W--->D      C<---Z
                     1         |  1
                              U|
                               v
                               E

   When the thread from C to E rewinds, the merged threads also rewind
   (8.4).  This process of rewinding can now proceed all the way back to
   the leafs.  While this is happening, of course, D will note that its
   outgoing thread hop count should be 2, not U, and will make this
   change (9.3).  As a result, A will note that its outgoing hop count
   should be 3, not U, and will make this change.  So at some time in
   the future, we might see the following:

                     1     3      1
                   X--->A----->B<---Y
                        ^      |
                      2 |      |U
                        |      v
                   W--->D      C<---Z
                     1         |  1
                              U|
                               v
                               E











Ohba, et al.                  Experimental                     [Page 42]

RFC 3063             MPLS Loop Prevention Mechanism        February 2001


   After a short period, we see the following:

                     1     3      1
                   X--->A----->B<---Y
                        ^      |
                      2 |      |4
                        |      v
                   W--->D      C<---Z
                     1         |  1
                              5|
                               v
                               E

   with all threads transparent, and we have a fully set up non-looping
   path.

A.15. Continuing to Use an Old Path

   Nothing in the above requires that any node withdraw a transparent
   thread.  Existing transparent threads (established paths) can
   continue to be used, even while new paths are being set up.

   If this is done, then some node may have both a transparent outgoing
   thread (previous path) and a colored outgoing thread (new path being
   set up).  This would happen only if the downstream links for the two
   threads are different.  When the colored outgoing thread rewinds (and
   becomes transparent), the previous path should be withdrawn.
























Ohba, et al.                  Experimental                     [Page 43]

RFC 3063             MPLS Loop Prevention Mechanism        February 2001


Full Copyright Statement

   Copyright (C) The Internet Society (2001).  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.



















Ohba, et al.                  Experimental                     [Page 44]