-
Notifications
You must be signed in to change notification settings - Fork 1
/
draft-eckert-pim-rts-forwarding-00.txt
1848 lines (1241 loc) · 73.6 KB
/
draft-eckert-pim-rts-forwarding-00.txt
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
PIM T. Eckert, Ed.
Internet-Draft Futurewei Technologies USA
Intended status: Informational M. Menth
Expires: 25 April 2024 S. Lindner
University of Tuebingen
23 October 2023
Stateless Multicast Replication with Segment Routed Recursive Tree
Structures (RTS)
draft-eckert-pim-rts-forwarding-00
Abstract
BIER provides stateless multicast in BIER domains using bitstrings to
indicate receivers. BIER-TE extends BIER with tree engineering
capabilities. Both suffer from scalability problems in large
networks as bitsrings are of limited size so the BIER domains need to
be subdivided using set identifiers so that possibly many packets
need to be sent to reach all receivers of a multicast group within a
subdomain.
This problem can be mitigated by encoding explicit multicast trees in
packet headers with bitstrings that have only node-local
significance. A drawback of this method is that any hop on the path
needs to be encoded so that long paths consume lots of header space.
This document presents the idea of Segment Routed Recursive Tree
Structures (RTS), a unifying approach to use either bitstrings with
local node-local significance or SIDs with local or domain-wide
significance to encode multicast trees in packet headers.
RTS, like RBS is intended to expand the applicability of deployment
for stateless multicast replication beyond what BIER and BIER-TE
support and expect: larger networks, less operational complexity, and
utilization of more modern forwarding planes as those expected to be
possible when BIER was designed (ca. 2010).
This document only specifies the forwarding plane but discusses
possible architectural options, which are primarily determined
through the future definition/mapping to encapsulation headers and
controller-plane functions.
Status of This Memo
This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79.
Eckert, et al. Expires 25 April 2024 [Page 1]
Internet-Draft pim-rts October 2023
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
This Internet-Draft will expire on 25 April 2024.
Copyright Notice
Copyright (c) 2023 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents (https://trustee.ietf.org/
license-info) in effect on the date of publication of this document.
Please review these documents carefully, as they describe your rights
and restrictions with respect to this document. Code Components
extracted from this document must include Revised BSD License text as
described in Section 4.e of the Trust Legal Provisions and are
provided without warranty as described in the Revised BSD License.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Overview . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.1. From BIER to RTS . . . . . . . . . . . . . . . . . . . . 4
2.1.1. Example topology and tree . . . . . . . . . . . . . . 4
2.1.2. IP Multicast . . . . . . . . . . . . . . . . . . . . 4
2.1.3. BIER . . . . . . . . . . . . . . . . . . . . . . . . 4
2.1.4. BIER-TE . . . . . . . . . . . . . . . . . . . . . . . 5
2.1.5. RTS . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.1.6. Summary and Benefits of RTS . . . . . . . . . . . . . 8
3. Architecture . . . . . . . . . . . . . . . . . . . . . . . . 9
4. Specification . . . . . . . . . . . . . . . . . . . . . . . . 10
4.1. RTS Encapsulation . . . . . . . . . . . . . . . . . . . . 10
4.2. RTS Addressing . . . . . . . . . . . . . . . . . . . . . 11
4.3. RTS Header . . . . . . . . . . . . . . . . . . . . . . . 13
4.4. Creating and Receiving copies . . . . . . . . . . . . . . 15
4.5. Creating copies because of RTS Header D=1 . . . . . . . . 15
4.6. Creating copies because of RTS Header B=1 . . . . . . . . 15
4.7. Creating copies because of the presence of an RU0 . . . . 15
4.7.1. Replication with SID-lists . . . . . . . . . . . . . 16
4.7.2. Replication with local bitstrings (RBS) . . . . . . . 20
Eckert, et al. Expires 25 April 2024 [Page 2]
Internet-Draft pim-rts October 2023
5. Discussion . . . . . . . . . . . . . . . . . . . . . . . . . 21
5.1. Encoding and allocation of SIDs for delivering and
broadcasting . . . . . . . . . . . . . . . . . . . . . . 21
5.2. Encapsulation considerations . . . . . . . . . . . . . . 22
5.2.1. Comparison with BIER header and forwarding . . . . . 22
5.2.2. Comparison with IPv6 extension headers . . . . . . . 23
5.3. Encoding choices and complexity . . . . . . . . . . . . . 23
5.4. Discovering malformed RTS Headers . . . . . . . . . . . . 25
5.5. Differences over prior Recursive BitString (RBS) encodings
proposal . . . . . . . . . . . . . . . . . . . . . . . . 25
6. Security considerations . . . . . . . . . . . . . . . . . . . 26
7. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 26
8. Changelog . . . . . . . . . . . . . . . . . . . . . . . . . . 26
9. References . . . . . . . . . . . . . . . . . . . . . . . . . 26
9.1. Normative References . . . . . . . . . . . . . . . . . . 26
9.2. Informative References . . . . . . . . . . . . . . . . . 27
Appendix A. Evolution to RTS . . . . . . . . . . . . . . . . . . 29
A.1. Research work on BIER . . . . . . . . . . . . . . . . . . 30
A.2. Initial RBS from CGM2 . . . . . . . . . . . . . . . . . . 30
A.3. RBS scalability compared to BIER . . . . . . . . . . . . 31
A.4. Discarding versus offset pointers . . . . . . . . . . . . 31
A.5. Encapsulations for IPv6-only networks . . . . . . . . . . 32
Contributors . . . . . . . . . . . . . . . . . . . . . . . . . . 32
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 33
1. Introduction
This draft expands on prior experimental work called "Recursive
BitString Structure" (RBS) for stateless multicast replication with
source routed data structures in the header of multicast data
packets. Its changes and enhancements over RBS are a result from
further scalability analysis and further matching against different
use cases. Its proposed design also includes Proof of Concept work
on Tofino programmable forwarding plane via P4.
Compared to RBS, RTS includes encoding options using either a per-hop
bitstring or a per-hop list of segment identifiers (SID) to address
next hops in the multicast tree.
RTS, like RBS is intended to expand the applicability of deployment
for stateless multicast replication beyond what BIER and BIER-TE
support and expect: larger networks, less operational setup
complexity, and utilization of more flexible programmable forwarding
planes as those expected to be possible when BIER was designed (ca.
2010). Unlike RBS, RTS does not limit itself to a design that is
only based on the use of bitstrings but instead offers both bitstring
and SID based addressing inside the recursive tree structure to
support to allow more scalability for a wider range of use cases.
Eckert, et al. Expires 25 April 2024 [Page 3]
Internet-Draft pim-rts October 2023
2. Overview
2.1. From BIER to RTS
2.1.1. Example topology and tree
Src Src
| ||
R1 R1
/ \ // \\
R2 R3 R2 R3
/ \ / \ // \ / \\
R5 R6 R7 R5 R6 R7
/ \ | \ / \ // \\ | \ // \\
R8 R9 R10 R11 R8 R9 R10 R11
| | | | || || || ||
Rcv1 Rcv2 Rcv3 Rcv4 Rcv1 Rcv2 Rcv3 Rcv4
Example Network Example BIER-TE / RTS Tree,
Topology // and || indicate tree segments
Figure 1: Example topology and tree
The following explanations use above example topology in Figure 1 on
the left, and example tree on the right.
2.1.2. IP Multicast
Assume a multicast packet is originated by Src and needs to be
replicated and forwarded to be received by Rcv1...Rcv4. In IP
Multicast with PIM multicast routing, router R1...R11 will have so-
called PIM multicast tree state, especially the intermediate routers
R2...R7. Whenever an IP Multicast router has multiple upstream
routers to choose from, then the path election is based on routing
RPF, so the routing protocol on R9 would need to route Src via R5,
and R10 would need to route Src via R7 to arrive at the tree shown in
the example.
2.1.3. BIER
In stateless multicast forwarding with Bit Index Explicit Replication
(BIER), [RFC8279], a packet has a header with a bitstring, and each
bit in the bitstring indicates one receiver side BIER router (BFER).
[R8:5 R9:9 R10:11 R11:17] =
00001000001000001000000000000000000000000
Eckert, et al. Expires 25 April 2024 [Page 4]
Internet-Draft pim-rts October 2023
Figure 2: Example BIER bitstring
In Figure 2, the term [Ri:bi...] (i=5,9,10,11; bi=5,9,11,17)
indicates the routers "Ri" that have their associated bit in the
bitstring number "bi" set. In this example, the bitstring is assumed
to be 42 bit long. The actual length of bitstring supported depends
on the header, such as [RFC8296] and implementation. The assignment
of routers to bits in this example is random.
With BIER, there is no tree state in R2...R7, but the packet is
forwarded from R2 across these routers based on those "destination"
bits bi and information of the hop-by-hop IP routing protocol, e.g.:
IS-IS or OSPF. The intervening routers traversed therefore also
solely depend on that routing protocols routing table, and as in IP
multicast, there is no guarantee that the shown intermediate hops in
the example picture are chosen if, as shown there are multiple equal
cost paths (e.g.: src via R10->R6->R3 and R10->R7->R3).
The header and hence bitstring size is a limiting factor for BIER and
any source-routing. When the network becomes larger, not all
receiver side routers or all links in the topology can be expressed
by this number of bits. A network with 10,000 receivers for example
would require at least 40 different bitstrings of 256 bits to
represent all receiver routers with separate bits. In addition, the
packet header needs to indicate which of those 40 bitstrings is
contained in the packet header.
When then receiver routers in close proximity in the topology are
assigned to different bitstrings, then the path to these receivers
will need to carry multiple copies of the same packet payload,
because each copy is required to carry a different bitstring. In the
worst case, even as few as 40 receivers may require still 40 separate
copies, as if unicast was used - because each of the 40 bits is
represented in a different bitstring.
2.1.4. BIER-TE
In BIER with Tree Engineering (BIER-TE), [RFC9262], the bits in the
bitstring do not only indicate the receiver side routers, but also
the intermediate links in the topology, hence allowing to explicitly
"engineer" the tree, for purposes such as load-splitting or bandwidth
guarantees on the tree.
[R1R2:4 R2R5:10 R5R8:15 R5R9:16 R1R3:25 R3R7:32 R7R10:39 R7R11:42]
000100000100001100000000100000010000001001
Figure 3: Example BIER-TE bitstring
Eckert, et al. Expires 25 April 2024 [Page 5]
Internet-Draft pim-rts October 2023
In Figure 3, the list of [RxRy:bi...] indicates the set of bits
needed to describe the tree in Figure 1, using the same notation as
in Figure 2.
Each RxRy indicates one bit in the bitstring for the link Rx->Ry.
The need to express every link in a topology as a separate bit makes
scaling even more challenging and requiring more bitstrings to
represent a network than BIER does, but in result of this
representation, BIER-TE allows to explicitly steer copies along the
engineered path, something requiredfor services that provide traffic
engineering, or when non-equal-cost load splitting is required
(without strict guarantees).
2.1.5. RTS
With Recursive Tree Structure (RTS) encoding, the concept of steered
forwarding from BIER-TE is modified to actually encode the tree
structure in the header as opposed to just one single "flat"
bitstring out of a large number of such bitstrings (in a large
network). For the same tree as above, the structure in the header
will logically look as follows.
Eckert, et al. Expires 25 April 2024 [Page 6]
Internet-Draft pim-rts October 2023
Syntax:
RU = SID { :[ NHi+ ] }
NHi = SID
SID = Ri
Example tree with SID list on R1:
R1 :[ R2 :[ R5 :[ R8 ,R9 ]], R3 :[R7 :[R10, R11]]]
Semantic:
R1 replicates to neighbors R2, R3.
R2 replicates to R5
R3 replicates to R7
...
Encoding structure:
1 byte SID always followed by
1 byte length of recursive structure legth (":[" in example)
If no recursive structure follows, length is 0.
Example SID list serialization (decimal):
R1 :[ R2 :[ R5 :[ R8 ,R9 ]], R3 :[ R7 :[R10, R11 ]]]
| | | | | | | | | | | | | | | | | |
v v v v v v v v v v v v v v v v v v
..........SIDs according to above example..........
| | | | | | | | |
01 16 02 06 05 04 08 00 09 00 03 06 07 04 10 00 11 00
| | | | | | | | |
......................Length fields................
Tree with SID list on R2:
R2 :[ R5 :[ R8 ,R9 ]]
Figure 4: Example RTS structure with SIDs
In the example the simplified RTS tree representation in Figure 4,
Rx:[NH1,... NHn] indicates that Rx needs to replicate the packet to
NH1, NH2 up to NHn. This [NH1,... NHn] list is called the SID-list.
Each NH can again be a "recursive" structure Rx:[NH1',...NHn'], such
as R5, or a leaf, such as R8, R9, Ro10, R11.
A simplified RTS serialization of this structure for the packet
header is also shown: Each router Ri is represented by am 8-bit SID
i. The length of the following SID list, :[NHi,...NHn], is also
encoded in one byte. If no SID list follows, it is 00.
Eckert, et al. Expires 25 April 2024 [Page 7]
Internet-Draft pim-rts October 2023
When a packet copy is made for a next-hop, only the relevant part of
the structure is kept in the header as shown for R2.
Example tree with bitstrings on R1:
BS1 :[ BS2 :[ BS5 :[ BS8, BS9 ]], BS3 :[BS7 :[BS10, BS11]]]
Example bitstring serialization (decimal):
....List of next-hops indicated by the BitStrings.........
| | | | | | | | |
R2,R3 R5 R8,R9 Rcv Rcv R7 R10,R11 Rcv Rcv
| | | | | | | | |
06 16 02 06 05 04 01 00 01 00 02 06 06 04 01 00 11 00
| | | | | | | | |
......................Length fields.......................
Example tree with bitstrings on R2:
BS2 :[ BS5 :[ BS8, BS9 ]]
Figure 5: Example RTS structure with bitstrings
Instead of enumerating for each router the list of next-hop neigbors
by their number (SID), RTS can also use a bitstring on each router,
resulting in a potentially more compact encoding. Scalability
comparison of the two encoding options is discussed later in the
document. Unlike BIER/BIER-TE bitstrings, each of these bitstring
will be small, as it only needs to indicate the direct neighbors of
the router for which the bitstring is intended.
In Figure 5, the example tree is shown with this bitstring encoding,
also simplified over the actual RTS encoding. BSi indicates the
bitstring for Ri as an 8-bit bitstring. On R8, R9, R10, R11 this
bitstring has bit 1 set, which is indicating that these routers
should receive ("Rcv") and decapsulate the packet.
2.1.6. Summary and Benefits of RTS
In BIER for large networks, even small number of receivers may not
fit into a single packet header, such as aforementioned when having
10,000 receiver routers with a bitstring size of 256. BIER always
requires to process the whole bitstring, bit-by-bit, so longer
bitstrings may cause issues in the ability of routers to process
them, even if the actual length of the bitstring would fit into
processable packet header memory in the router.
In BIER-TE, these problems are even more pronounced because the
bitstrings now need to also carry bits for the intermediate node
hops, which are necessary whenever the path for a packet need to be
Eckert, et al. Expires 25 April 2024 [Page 8]
Internet-Draft pim-rts October 2023
explicitly predetermined such as in traffic engineering and global
network capacity optimization through non-equal cost load-balancing,
which in unicast is also a prime reason for deployment of Segment
Routing.
These scalability problems in BIER and BIER-TE can be reduced by
intelligent allocation of bits to bitstrings, but this requires
global coordination, and for best results good predictions of the
most important required future multicast trees.
In RTS, no such network wide intelligent assignment of addresses is
required, and any combination of receiver routers can be put into a
single packet header as long as the maximum size of the header is not
exceeded (including of course the intermediate nodes along the path).
Unlike Bier/BIER-TE, the RTS header can likely on many platforms be
larger than a BIER/BIER-TE bitstring, because the router never needs
to examine every bit in the header, but only the (local) bitstring or
list of SIDs for this router itself and then for each copy to a
neighbor, it only needs to copy the recursive structure for that
neighbor. The only significant limit for RTS in processing is hence
the maximum amount of bytes in a header that can be addressed.
3. Architecture
This version of the document does not specify an architecture for
RTS.
The forwarding described in this document can allow different
architectures, also depending on the encapsulation chosen. The
following high-level architectural considerations and possible goals/
benefits apply:
(A) If embedding RTS in an IP or IPv6 source-routing extension
header, RTS can provide source-routing to eliminate stateful (IP)
Multicast hop-by-hop tree building protocols such as PIM. This can
be specifically attractive in use cases that previously used end-to-
end IP Multicast without a more complex P/PE architecture, such as
enterprises, industrial and other non-SP networks.
(B) The encoding of the RTS multicast tree in the packet header makes
it natural to think about RTS providing a multicast "Segment Routing"
architecture style service with stateless replication segments: Each
recursive structure is an RTS segment.
This too can be a very attractive type of architecture to support,
especially for networks that already use MPLS or IPv6 Segment Routing
for unicast. Nevertheless, RTS can also be beneficial in SP networks
Eckert, et al. Expires 25 April 2024 [Page 9]
Internet-Draft pim-rts October 2023
not using unicast Segment Routing, and there are no dependencies for
networks running RTS to also support unicast SR, other than sharing
architecture concepts.
(C) RTS naturally aligns with many goals and benefits of BIER and
even more so BIER-TE, which it could most easily supersede for better
scalability and ease of operations.
In one possible option, the RTS header specified in this document
could even replace the bitstring of the BIER [RFC8296] header,
keeping all other aspects of BIER/BIER-TE reusable. In such an
option, the architectural aspects of RTS would be derived and
simplified from [RFC9262], similar to details described in
[I-D.eckert-bier-cgm2-rbs-01].
4. Specification
4.1. RTS Encapsulation
+----------+--------+------------+
| Encap | RTS | Next Proto |
| Header(s)| Header | Payload |
+----------+--------+------------+
Figure 6: RTS encapsulation
This document specifies the formatting and functionality of the
"Recursive Tree Structure" (RTS) Header, which is assumed to be
located in a packet between some Encap Header and some Next Proto /
Payload.
The RTS header contains only elements to support replication to next-
hops, not any element for forwarding to next-hop. This is left as a
task for the Encap Header so that RTS can most easily be combined
with potentially multiple alternative Encapsulation Header(s) for
different type of network protocols or deployment use cases. Common
Encap Headers will also require an Encap Header specific description
of the total length of the RTS Header.
In a minimum (theoretical) example, RTS could be used on top of
Ethernet with an ethertype of RTS+Payload, which indicates not only
that an RTS Header follows, but also the type of the Next Proto
Payload.
See the encap discussions in Section 5.2 for considerations regarding
BIER or IPv6 extension headers as Encap Headers.
Eckert, et al. Expires 25 April 2024 [Page 10]
Internet-Draft pim-rts October 2023
4.2. RTS Addressing
Addresses of next-hops to which RTS can replicata are called RTS
Segment IDentifiers (SIDs). This is re-using the terminology
established by [RFC8402] to be agnostic of the addressing of the
routing underlay used for forwarding to next-hops and obtaining
routing information for those routing underlay addresses. Specifying
an encapsulation for RTS requires specifying how to map RTS SIDs to
addresses of the addresses used by that (unicast) forwarding
mechanism.
RTS SIDs are more accurately called RTS replication SIDs. They are
assigned to RTS nodes. When a packet is directed to a particular RTS
SID of an RTS node it means that that node needs then to process the
RTS Header and perform replication according to it.
Using the SR terminology does not mean that RTS is constrained to be
used with forwarding planes for which (unicast) SR mappings exist:
IPv6 and MPLS, but it means that for other forwarding planes,
mappings need to be defined. For example, when using RTS with
[RFC8296] encapsulation, and hence BIER addressing, which is relying
on 16-bit BFR-id addressing (especially the BFIR-id in the [RFC8296]
header), then RTS SIDs need to map to these BFR-ids.
If instead RTS is to be deployed with (only) an IPv6 extension header
as the Encap Header, then RTS SIDs need to be mapped to IPv6 SIDs.
This document uses three types of RTS SIDs to support three type of
encoding of next-hops in an RTS Header: Global, Local and Local
bitstring RTS SIDs.
All SIDs map to a unicast address or unicast SID of the node which
the RTS SID addresses. This unicast address or SID is used in an
Encap Header when sending an RTS packet to that node.
The type of an RTS SID determines the encoding and scope of the SID.
Global and Local SIDs are used in the SID-list encoding option of the
RTS header, Local bitstring SIDs are used in the local-bitstring
encoding option of the RTS header.
Eckert, et al. Expires 25 April 2024 [Page 11]
Internet-Draft pim-rts October 2023
Local and local bitstring RTS SID are valid only on an individual RTS
node because they are both so compact in their encoding that only a
limited number of RTS nodes can be addressed by them. Global RTS
SIDs are valid on every RTS node: Using Global RTS SIDs allow the
creator of an RTS Header to steer a packet copy from any RTS to any
other RTS node. Local and local bitstring SIDs allow to only steer
traffic across adjacencies predetermined by network and/or operator
policy that allocates these SIDs, typically L2 adjcencies between RTS
nodes.
* Global RTS SIDs are 15 or 23 bit values depending on the size of
the deployment.
* Local RTS SIDs (or abbreviated local SIDs) are 7-bit values
1...127.
* Local bitstring RTS SIDs (or abbreviated local bitstring SIDs) are
values from 1.. (8*N). N is the size of the local bitstring for
the node on which the local bitstring SID is allocated. The value
of the local bitstring SID indicates the bit in that bitstring
that needs to be set to indicate that a copy to the node addressed
by the SID is needed.
Each RTS SID has flags associated with it that define encoding and
processing of RTS packet when the SID is processed in the RTS header
by an RTS node that is sending a packet to that SID.
* The D)eliver Flag indicates that the node addressed by the SID
needs to receive a copy of the packet by appropriate disposing of
the RTS Header and processing of the Next Proto Payload.
* The B)roadcast Flag indicates that the node addressed by the SID
need to broadcast a copy of the packet to a preconfigured list of
"all-leaf-neighbors".
* The RU Flag indicates that the RTS header contains a recursive
unit for the SID. When the node addressed by the SID receives the
packet, it will act as a transit node and create copies to the
nodes in that RU.
Eckert, et al. Expires 25 April 2024 [Page 12]
Internet-Draft pim-rts October 2023
All Flags for a SID are processed by the node that is sending a copy
to the addressed SID, but not the node which is addressed by the SID
itself. That node is only the receiver of a copy of the packet. The
sending node moifies the RTS Header accordingly for the Flags so that
the addressed node when it receives the copy will have the Flags in
the RTS Header. This is done so that network or operator policy can
allocate from the limited local and local bitstring SID space only
those (combination of) Flags for a node that are deemed necessary, as
opposed to costing space in the RTS header if the Flags where all
static part of the RTS Header encoding.
The network is expected to make SID information available to the
creators of RTS headers so they can create one or more RTS headers to
achieve the desired replication tree(s) for a payload. This
includes:
* Global SID for each node and the unicast address it maps to.
* For each node its Local SIDs and local bitstring SIDs, its flags
and the unicast address/SID it maps to.
* For each node its "all-leaf-neighbors" list of global SIDs (see
{#all-leaf-neighbors})
4.3. RTS Header
+--------+---------------------------------------------+
| | RU0 (optional) |
| RTS |+----------++--------++-------+ +-------+|
| Params ||RU0 Params|| RU-NH1 ||RU-NH2 | ....|RU-NHn ||
| |+----------++--------++-------+ +-------+|
+--------+---------------------------------------------+
Figure 7: RTS Header
The RTS Header consists of the "RTS Params" field followed by an
optional element called "Recursive Unit 0" (RU0).
When the RTS header is processed by a router, RU0 (if present) is
composed of RU0 Params as well as 0 or more RU's, one for each next-
hop. Each of these RUs is composed like RU0 itself from a RU Params
field and potentially following RU-NHi fields.
RU Params differ depending on whether bitstring or SID encoding is
chosen for the packet. These differences are explained later.
Eckert, et al. Expires 25 April 2024 [Page 13]
Internet-Draft pim-rts October 2023
RTS Params:
0 1 2 3 4 5 6 7
+-+-+-+-+-+-+-+-+
|R|D|B|S| Rsvd |
+-+-+-+-+-+-+-+-+
Figure 8: RTS Params
The (R)U0 bit indicates whether a RU0 follows.
R=0: No RU0 follows. In this case, D MUST be 1, or else the packet
is misformed.
R=1: An RU0 follows.
The (D)eliver bit indicates whether a copy of the packet should be
delivered on this node by disposing the RTS Param and processing the
next-header.
D=0: Do not deliver a copy of the packet.
D=1: Deliver a copy of the packet by disposing of the RTS Header and
processing of the next-header.
The (B)roadcast bit determines if copies of the packet should be send
to all "all leaf neighbors".
B=0: Do not send copies to all "all leaf neighbors"
B=1: Send copies to all "all leaf neighbors"
Creating copies because of the presence D, B and RU is orthogonal
from each other and can happen in any combination. At least one copy
needs to be indicated or else the packet is invalid.
The (S) bit indicates whether next-hops are encoded as a bitstring or
SID-list. This flag is irrelevant if R=0 (because there is no
bitstring nor SID-list).
S=0: next-hops are encoded as a bitstring
S=1: next-hops are encoded as a SID-list.
Eckert, et al. Expires 25 April 2024 [Page 14]
Internet-Draft pim-rts October 2023
4.4. Creating and Receiving copies
RTS relies on unicast forwarding procedures using the Encap Header(s)
to receive packets and send copies of packets. Every copy of a
packet created, except for those that are for local reception by a
node, is sent towards a unicast address/SID according to the RTS SID
it addresses.
In summary, RTS Params is responsible for distinguishing the encoding
of the following (optional) RU0 but also provides the bits used for
processing by so-called "leaves" of an RTS tree, where packets need
to be delivered and/or broadcast to all "leaf" neighbors (where they
are then delivered).
4.5. Creating copies because of RTS Header D=1
When D=1 is encountered in the RTS Params, an (internal) copy of the
packet is created in which the headers up to the RTS Header are
disposed of according to the procedures specified for Encap Header(s)
so that the Next Proto Payload after the RTS Header is processed.
4.6. Creating copies because of RTS Header B=1
When B=1 is set in the RTS Params, a list of uncast addresses/SIDs
called the "all leaf neighbors" is used to create a separate copy of
the packet for each element in that list. Each RTS node MAY have
such a list.
For each packet copy made because of B=1, RU0 is removed, D is set to
1 and B to 0. Typically, the "all-leaf-neighbors" list is
(auto-)configured with the list of RTS L2 neighbors that are known to
be leaves of the RTS domain.
4.7. Creating copies because of the presence of an RU0
The common processing of RU0 to create copies, independent of whether
SID-list or local bitstring list encoding of next-hops is used is as
follows.
If R=1, then the RTS router examines the RU0 header and the following
RU-NHi to determine the copies it needs to create.
Eckert, et al. Expires 25 April 2024 [Page 15]
Internet-Draft pim-rts October 2023
When packet gets replicated to a NHi (1...n) with an RU-NHi, RU0 gets
replaced by RU-NHi, all RU0 data before and after RU-NHi is skipped
when rewriting the packet header for the copy to NHi. If a packet
copy gets replicated to a next-hop not including an RU-NHi, the copy
to that next-hop will not include any RU0. In this case, the Flags
for the SID of that next-hop will include the D and/or B flag, and
these flags will be accordingly set in the copy sent to the node so
that it delivers and/or broadcasts the packet.
The following example shows how a copy made to NH2 will cause RU-NH2
to become RU0 on the copy of the packet made for NH2:
Original RTS Header at this hop:
+--------+---------------------------------------------+
| | RU0 |
| RTS |+--....----++--------++-------+ +-------+|
| Params ||RU0 Params|| RU-NH1 ||RU-NH2 | ....|RU-NHn ||
| |+--....----++--------++-------+ +-------+|
| | |<........... RU List..........>||
+--------+---------------------------------------------+
<--- discard -------->||<-copy>||<--discard-->|
(&strip)
Copy sent to NH2:
+--------+-------------------------------------------+
| | RU0 (was RU-NH2 on prior hop) |
| RTS |+--....----+--------+-------+ +-------+|
| Params ||RU0 Params| RU-NH1'|RU-NH2'| ....|RU-NHn'||
| |+--....----+--------+-------+ +-------+|
+--------+-------------------------------------------+
Figure 9: Example copy to NH2
4.7.1. Replication with SID-lists
+--------+--------------------------------------------+
| | RU0 (present if RTS Params RU=1) |
| RTS |+...........+--------+-------+ +-------+|
| Params |. RU0 Params| RU-NH1 |RU-NH2 | ....|RU-NHn ||
| (S=1) |+...........+--------+-------+ +-------+|
+--------+--------------------------------------------+
Figure 10: RTS Header with SID-list format (S=1)
This section describes replication with SID-list. The SID-list
format is indicated by S=1 in the RTS Param field of the header.
Eckert, et al. Expires 25 April 2024 [Page 16]
Internet-Draft pim-rts October 2023
|<--- RU-NHi RU Params ------>|<-- RU-NHi RU List --------->|
+-+-+-+ ... +-+-+-+-+-+-+-+-+-+-+....-+-+....-+ +-+....-+
|G| RU-NHi | RUlength |RU-NH1'|RU-NH2'| ... |RU-NHn'|
| | SID | (optional) | | | | |
+-+-+-+ ... +-+-+-+-+-+-+-+-+-+-+....-+-+....-+ +-+....-+
|<-7/15/23->| |<....... optional ..........>|
Figure 11: RU-NHi in SID-list format
When forwarding with the SID-list RTS format, RU Params in RU-NHi
contains the SID of the router to which the RU is destined. If the
SID indicates the RU flag, then the SID is followed by a RUlength
field and a list of zero or more RU-NHi' as shown in Figure 11.
If the G)lobal bit of RU Params is 0, SID is a 7-bit long local RTS
SID assigned by the router processing the RU0. If G is 1, SID is a
global SID with a deployment chosen length of 23 or 17 bit, which
needs to be common across all RTS nodes in the RTS domain.
Note that instead of being configurable, this length could also
become a specification defined size in later versions of this
document.
RU0 Params in the SID-list format is empty. It is stripped from RU-
NHi when the packet copy is made so that that RU-NHi becomes RU0 of
the packet copy.
The reason for stripping it is because it serves no purpose anymore.
The Encap Header is responsible to deliver the packet to the correct
RTS neighbor. Once that RTS neighbor receives the packet, it may not
be able to interpret the SID, because that SID could be a local SID
from the context of the sending node, and some forwarding planes like
MPLS make it impossible to know who sent a packet.
Likewise, the RUlength field is redundant: It was only necessary when
creating the packet copy, copying RU-NHi into the new packet copy
towards NHi, based on RU-NHi's RUlength field. Once the new packet
copy is created, it's Encap Header will need to have it's length
field updates according to the new RU0 length, so this information
does not need to be duplicated in the RU0 itself.
Eckert, et al. Expires 25 April 2024 [Page 17]
Internet-Draft pim-rts October 2023
4.7.1.1. Encoding and Allocation of SIDs
D), B) and RU) flags are properties of SIDs so that they do not
unnecessarily require a fixed amount of bits in the encoding, when it
is clear for specific nodes that they do not ever need all of the
encodings. This is especially true, when local SIDs are used, or
global SIDs with 15 bit in networks close that that amount of
required SIDs.
When global SIDs use 23 bits instead, there should be enough SID
space to allocate all 7 possible Flag combination for each node,
maybe even by allocating the last 3 bit of the numeric SID
representation, wasting one SID number for every node, just to have a
simple addressing scheme.
+----------+--------------+-------+---------------------+
| Type | SID | Flags | Encap data |
+----------+--------------+-------+---------------------+
| Global | <Node1 SID1> |D | <Unicast Address 1> |
| Global | <Node1 SID2> | B | <Unicast Address 1> |
| Global | <Node1 SID3> |D B | <Unicast Address 1> |
| Global | <Node1 SID4> | RU | <Unicast Address 1> |
| Global | <Node1 SID5> |D RU | <Unicast Address 1> |
| Global | <Node1 SID6> | B RU | <Unicast Address 1> |
| Global | <Node1 SID7> |D B RU | <Unicast Address 1> |
| <unused> | <unused> | ... | ... |
| Global | <Node2 SID1> |D | <Unicast Address 2> |
| Global | <Node2 SID2> | B | <Unicast Address 2> |
| ... | ... | ... | ... |
+----------+--------------+-------+---------------------+
Figure 12: Global SID allocation example
For optimized allocation of SIDs, the following considerations may be
used as a starting point to limit the numbrer of local SIDs requird
for nodes.
A large number of nodes may be leaves in the network topology. For
example, when PE routers are not in a ring, but only attached to two
P routers, they are not assumed to carry transit traffic, and even
the unicast routing protocol may accordingly be configured. In this
case this PE never needs to have the RU flag, it would also not need
a B flag, but all RTS packets arriving at it would solely be for
delivering RTS packets. Hence such nodes only need a single SID with