-2.75 E(carry multicast-speci\214c topology information.)105 578.2 Q
(In PIM-SM this is used to mak)5.5 E 2.75(ed)-.11 G(ecisions)-2.75 E(re)
105 591.2 Q -.055(ga)-.165 G(rding where to forw).055 E
(ard Join/Prune messages.)-.11 E(RPF Neighbor)72 607.8 Q
(RPF stands for "Re)105 620.8 Q -.165(ve)-.275 G(rse P).165 E(ath F)
-.165 E(orw)-.165 E 2.75(arding". The)-.11 F
(RPF Neighbor of a router with respect to)2.75 E(an address is the neig\
hbor that the MRIB indicates should be used to forw)105 633.8 Q
(ard pack)-.11 E(ets to)-.11 E(that address.)105 646.8 Q(In the case of\
 a PIM-SM multicast group, the RPF neighbor is the router that)5.5 E
2.75(aJ)105 659.8 S(oin message for that group w)-2.75 E
(ould be directed to, in the absence of modifying Assert)-.11 E(state.)
105 672.8 Q 12.529(TIB T)72 689.4 R(ree Information Base.)-.385 E
(This is the collection of state at a PIM router that has been created)
5.5 E(by recei)105 702.4 Q(ving PIM Join/Prune messages, PIM Assert mes\
sages, and IGMP information)-.275 E(from local hosts.)105 715.4 Q
(It essentially stores the state of all multicast distrib)5.5 E
(ution trees at that)-.22 E(Fenner/Handle)72 769 Q(y/Holbrook/K)-.165 E
(ouv)-.385 E 174.721(elas Section)-.165 F 2.75(2.1. [P)2.75 F(age 4])
-.165 E EP
%%Page: 5 5
%%BeginPageSetup
BP
%%EndPageSetup
/F0 11/Times-Roman@0 SF(INTERNET)72 49 Q 71.587(-DRAFT Expires:)-1.012 F
(January 2002)2.75 E(July 2001)123.726 E(router)105 85 Q(.)-.605 E 3.355
(MFIB Multicast)72 101.6 R -.165(Fo)2.75 G(rw).165 E
(arding Information Base.)-.11 E
(The TIB holds all the state that is necessary to)5.5 E(forw)105 114.6 Q
(ard multicast pack)-.11 E(ets at a router)-.11 E 5.5(.H)-.605 G -.275
(ow)-5.5 G -2.365 -.275(ev e).275 H .88 -.44(r, a).275 H
(lthough this speci\214cation de\214nes).44 E(forw)105 127.6 Q
(arding in terms of the TIB, to actually forw)-.11 E(ard pack)-.11 E
(ets using the TIB is v)-.11 E(ery)-.165 E(inef)105 140.6 Q 2.75
(\214cient. Instead)-.275 F 2.75(ar)2.75 G
(eal router implementation will normally b)-2.75 E(uild an ef)-.22 E
(\214cient MFIB)-.275 E(from the TIB state to perform forw)105 153.6 Q
2.75(arding. Ho)-.11 F 2.75(wt)-.275 G
(his is done is implementation-speci\214c,)-2.75 E
(and is not discussed in this document.)105 166.6 Q(Upstream)72 183.2 Q
-1.265 -.88(To w)105 196.2 T(ards the root of the tree.).77 E
(The root of tree may either be the source or the RP)5.5 E
(depending on the conte)105 209.2 Q(xt.)-.165 E(Do)72 225.8 Q(wnstream)
-.275 E -.836 -1.012(Aw a)105 238.8 T 2.75(yf)1.012 G
(rom the root of the tree.)-2.75 E/F1 11/Times-Bold@0 SF(2.2.)72 264.8 Q
/F2 13/Times-Bold@0 SF(Pseudocode Notation)5.5 E F0 1.76 -.88(We u)72
281.4 T(se set notation in se).88 E -.165(ve)-.275 G
(ral places in this speci\214cation.).165 E/F3 11/Courier@0 SF 6.6(A\()
72 298 S(+\) B)-6.6 E F0(is the union of tw)94 311 Q 2.75(os)-.11 G
(ets A and B.)-2.75 E F3 6.6(A\()72 327.6 S(-\) B)-6.6 E F0
(is the elements of set A that are not in set B.)94 340.6 Q F3(NULL)72
357.2 Q F0(is the empty set or list.)94 370.2 Q
(In addition we use C-lik)72 386.8 Q 2.75(es)-.11 G(yntax:)-2.75 E
15.796(=d)72 403.4 S(enotes assignment of a v)-15.796 E(ariable.)-.275 E
6.842(== denotes)72 420 R 2.75(ac)2.75 G(omparison for equality)-2.75 E
(.)-.715 E 9.383(!= denotes)72 436.6 R 2.75(ac)2.75 G
(omparison for inequality)-2.75 E(.)-.715 E
(Braces { and } are used for grouping.)72 453.2 Q F1(3.)72 482.8 Q/F4 14
/Times-Bold@0 SF(PIM-SM Pr)5.5 E(otocol Ov)-.252 E(er)-.14 E(view)-.14 E
F0(This section pro)72 499.4 Q(vides an o)-.165 E -.165(ve)-.165 G(rvie)
.165 E 2.75(wo)-.275 G 2.75(fP)-2.75 G(IM-SM beha)-2.75 E(vior)-.22 E
5.5(.I)-.605 G 2.75(ti)-5.5 G 2.75(si)-2.75 G
(ntended as an introduction to ho)-2.75 E(w)-.275 E(PIM-SM w)72 512.4 Q
(orks, and is)-.11 E F1(NO)2.75 E(T)-.44 E F0(de\214niti)2.75 E -.165
(ve)-.275 G 5.5(.F).165 G(or the de\214niti)-5.665 E .33 -.165(ve s)
-.275 H(peci\214cation, see Section 4.).165 E
(PIM relies on an underlying topology-g)72 529 Q
(athering protocol to populate a routing table with routes.)-.055 E(Thi\
s routing table is called the MRIB or Multicast Routing Information Bas\
e.)72 542 Q(The routes in this)5.5 E(table may be tak)72 555 Q
(en directly from the unicast routing table, or it may be dif)-.11 E
(ferent and pro)-.275 E(vided by)-.165 E 2.75(as)72 568 S
(eparate routing protocol such as MBGP [1]. In an)-2.75 E 2.75(ye)-.165
G -.165(ve)-3.025 G(nt, the routes in the MRIB must).165 E
(represent a multicast-capable path to each subnet.)72 581 Q
(The MRIB is used to determine the path that)5.5 E
(PIM control messages such as Join messages tak)72 594 Q 2.75(et)-.11 G
2.75(og)-2.75 G(et to the source subnet, and data \215o)-2.75 E(ws)-.275
E(along the re)72 607 Q -.165(ve)-.275 G(rse path of the Join messages.)
.165 E(Thus, in contrast to the unicast RIB where the routes)5.5 E(gi)72
620 Q .33 -.165(ve a p)-.275 H(ath that data pack).165 E(ets tak)-.11 E
2.75(et)-.11 G 2.75(og)-2.75 G(et)-2.75 E/F5 11/Times-Italic@0 SF(to)
2.75 E F0(each subnet, the MRIB gi)2.75 E -.165(ve)-.275 G 2.75(sr).165
G -2.365 -.275(ev e)-2.75 H(rse-path information,).275 E
(and indicates the path that data pack)72 633 Q(ets w)-.11 E(ould tak)
-.11 E(e)-.11 E F5(fr)2.75 E(om)-.495 E F0
(each subnet to the router that has the)2.75 E(MRIB.)72 646 Q(Lik)72
662.6 Q 2.75(ea)-.11 G(ll multicast routing protocols that implement th\
e service model from RFC 1112 [2], PIM-)-2.75 E
(SM must be able to route data pack)72 675.6 Q
(ets from sources to recei)-.11 E -.165(ve)-.275 G
(rs without either the sources or).165 E(recei)72 688.6 Q -.165(ve)-.275
G(rs kno).165 E(wing a-priori of the e)-.275 E(xistence of the others.)
-.165 E(This is essentially done in three phases,)5.5 E
(although as senders and recei)72 701.6 Q -.165(ve)-.275 G
(rs may come and go at an).165 E 2.75(yt)-.165 G
(ime, all three phases may be occur)-2.75 E(simultaneously)72 714.6 Q(.)
-.715 E(Fenner/Handle)72 769 Q(y/Holbrook/K)-.165 E(ouv)-.385 E 182.971
(elas Section)-.165 F 2.75(3. [P)2.75 F(age 5])-.165 E EP
%%Page: 6 6
%%BeginPageSetup
BP
%%EndPageSetup
/F0 11/Times-Roman@0 SF(INTERNET)72 49 Q 71.587(-DRAFT Expires:)-1.012 F
(January 2002)2.75 E(July 2001)123.726 E/F1 11/Times-Bold@0 SF
(Phase One: RP T)72 85 Q -.198(re)-.814 G(e).198 E F0
(In phase one, a multicast recei)72 101.6 Q -.165(ve)-.275 G 2.75(re)
.165 G(xpresses its interest in recei)-2.915 E(ving traf)-.275 E
(\214c destined for a multicast)-.275 E 2.75(group. T)72 114.6 R
(ypically it does this using IGMP [3], b)-.88 E
(ut other mechanisms might also serv)-.22 E 2.75(et)-.165 G(his)-2.75 E
2.75(purpose. One)72 127.6 R(of the recei)2.75 E -.165(ve)-.275 G(r')
.165 E 2.75(sl)-.605 G
(ocal routers is elected as the Designated Router \(DR\) for that)-2.75
E 2.75(subnet. On)72 140.6 R(recei)2.75 E(ving the recei)-.275 E -.165
(ve)-.275 G(r').165 E 2.75(se)-.605 G
(xpression of interest, the DR then sends a PIM Join message)-2.915 E
(to)72 153.6 Q -.11(wa)-.275 G(rds the RP for that multicast group.).11
E(This Join message is kno)5.5 E(wn as a \(*,G\) Join because it)-.275 E
(joins group G for all sources to that group.)72 166.6 Q
(The \(*,G\) Join tra)5.5 E -.165(ve)-.22 G(ls hop-by-hop to).165 E -.11
(wa)-.275 G(rds the RP for).11 E(the group, and in each router it passe\
s through, multicast tree state for group G is instantiated.)72 179.6 Q
(Ev)72 192.6 Q(entually the \(*,G\) Join either reaches the RP)-.165 E
2.75(,o)-1.221 G 2.75(rr)-2.75 G
(eaches a router that already has \(*,G\) Join)-2.75 E
(state for that group.)72 205.6 Q(When man)5.5 E 2.75(yr)-.165 G(ecei)
-2.75 E -.165(ve)-.275 G(rs join the group, their Join messages con).165
E -.165(ve)-.44 G -.198(rg).165 G 2.75(eo).198 G 2.75(nt)-2.75 G(he)
-2.75 E(RP)72 218.6 Q 2.75(,a)-1.221 G(nd form a distrib)-2.75 E
(ution tree for group G that is rooted at the RP)-.22 E 5.5(.T)-1.221 G
(his is kno)-5.5 E(wn as the RP T)-.275 E(ree)-.385 E
(\(RPT\), and is also kno)72 231.6 Q(wn as the shared tree because it i\
s shared by all sources sending to that)-.275 E 2.75(group. Join)72
244.6 R(messages are resent periodically so long as the recei)2.75 E
-.165(ve)-.275 G 2.75(rr).165 G(emains in the group.)-2.75 E(When)5.5 E
(all recei)72 257.6 Q -.165(ve)-.275 G(rs on a leaf-netw).165 E(ork lea)
-.11 E .33 -.165(ve t)-.22 H
(he group, the DR will send a PIM \(*,G\) Prune message).165 E(to)72
270.6 Q -.11(wa)-.275 G(rds the RP for that multicast group. Ho).11 E
(we)-.275 E -.165(ve)-.275 G 2.75(ri).165 G 2.75(ft)-2.75 G
(he prune message is not sent for an)-2.75 E 2.75(yr)-.165 G(eason,)
-2.75 E(the state will e)72 283.6 Q -.165(ve)-.275 G(ntually time out.)
.165 E 2.75(Am)72 300.2 S(ulticast data sender just starts sending data\
 destined for a multicast group.)-2.75 E(The sender')5.5 E 2.75(sl)-.605
G(ocal)-2.75 E(router \(DR\) tak)72 313.2 Q(es those data pack)-.11 E
(ets, unicast-encapsulates them, and sends them directly to the)-.11 E
(RP)72 326.2 Q 5.5(.T)-1.221 G(he RP recei)-5.5 E -.165(ve)-.275 G 2.75
(st).165 G(hese encapsulated data pack)-2.75 E
(ets, decapsulates them, and forw)-.11 E(ards them onto)-.11 E
(the shared tree.)72 339.2 Q(The pack)5.5 E(ets then follo)-.11 E 2.75
(wt)-.275 G(he \(*,G\) multicast tree state in the routers on the RP)
-2.75 E -.385(Tr)72 352.2 S(ee, being replicated where).385 E -.165(ve)
-.275 G 2.75(rt).165 G(he RP T)-2.75 E(ree branches, and e)-.385 E -.165
(ve)-.275 G(ntually reaching all the recei).165 E -.165(ve)-.275 G(rs)
.165 E(for that multicast group.)72 365.2 Q
(The process of encapsulating data pack)5.5 E
(ets to the RP is called re)-.11 E(gistering,)-.165 E
(and the encapsulation pack)72 378.2 Q(ets are kno)-.11 E(wn as PIM Re)
-.275 E(gister pack)-.165 E(ets.)-.11 E
(At the end of phase one, multicast traf)72 394.8 Q(\214c is \215o)-.275
E(wing encapsulated to the RP)-.275 E 2.75(,a)-1.221 G(nd then nati)
-2.75 E -.165(ve)-.275 G(ly o).165 E -.165(ve)-.165 G(r).165 E
(the RP tree to the multicast recei)72 407.8 Q -.165(ve)-.275 G(rs.).165
E F1(Phase T)72 446.8 Q -.11(wo)-.814 G 2.75(:R).11 G(egister Stop)-2.75
E F0(Re)72 463.4 Q(gister)-.165 E(-encapsulation of data pack)-.22 E
(ets is inef)-.11 E(\214cient for tw)-.275 E 2.75(or)-.11 G(easons:)
-2.75 E 7.15<8345>72 480 S(ncapsulation and decapsulation may be relati)
-7.15 E -.165(ve)-.275 G(ly e).165 E(xpensi)-.165 E .33 -.165(ve o)-.275
H(perations for a router to).165 E
(perform, depending on whether or not the router has appropriate hardw)
83 493 Q(are for these tasks.)-.11 E 7.15<8354>72 509.6 S(ra)-7.535 E
-.165(ve)-.22 G(ling all the w).165 E(ay to the RP)-.11 E 2.75(,a)-1.221
G(nd then back do)-2.75 E(wn the shared tree may entail the pack)-.275 E
(ets)-.11 E(tra)83 522.6 Q -.165(ve)-.22 G(ling a relati).165 E -.165
(ve)-.275 G(ly long distance to reach recei).165 E -.165(ve)-.275 G
(rs that are close to the sender).165 E 5.5(.F)-.605 G(or some)-5.665 E
(applications, this increased latenc)83 535.6 Q 2.75(yi)-.165 G 2.75(su)
-2.75 G(ndesirable.)-2.75 E(Although Re)72 552.2 Q(gister)-.165 E
(-encapsulation may continue inde\214nitely)-.22 E 2.75(,f)-.715 G
(or these reasons, the RP will)-2.75 E
(normally choose to switch to nati)72 565.2 Q .33 -.165(ve f)-.275 H
(orw).165 E 2.75(arding. T)-.11 F 2.75(od)-.88 G 2.75(ot)-2.75 G
(his, when the RP recei)-2.75 E -.165(ve)-.275 G 2.75(sar).165 G -.165
(eg)-2.75 G(ister).165 E(-)-.22 E(encapsulated data pack)72 578.2 Q(et \
from source S on group G, it will normally initiate an \(S,G\) source-)
-.11 E(speci\214c Join to)72 591.2 Q -.11(wa)-.275 G(rds S.).11 E
(This join message tra)5.5 E -.165(ve)-.22 G(ls hop-by-hop to).165 E
-.11(wa)-.275 G(rds S, instantiating \(S,G\)).11 E
(multicast tree state in the routers along the path.)72 604.2 Q
(\(S,G\) multicast tree state is used only to forw)5.5 E(ard)-.11 E
(pack)72 617.2 Q(ets for group G if those pack)-.11 E
(ets come from source S.)-.11 E(Ev)5.5 E
(entually the Join message reaches)-.165 E(S')72 630.2 Q 2.75(ss)-.605 G
(ubnet or a router that already has \(S,G\) multicast tree state, and t\
hen pack)-2.75 E(ets from S start to)-.11 E<8d6f>72 643.2 Q 2.75(wf)
-.275 G(ollo)-2.75 E(wing the \(S,G\) tree state to)-.275 E -.11(wa)
-.275 G(rds the RP).11 E 5.5(.T)-1.221 G(hese data pack)-5.5 E
(ets may also reach routers)-.11 E(with \(*,G\) state along the path to)
72 656.2 Q -.11(wa)-.275 G(rds the RP - if so, the).11 E 2.75(yc)-.165 G
(an short-cut onto the RP tree at this)-2.75 E(point.)72 669.2 Q(While \
the RP is in the process of joining the source-speci\214c tree for S, t\
he data pack)72 685.8 Q(ets will)-.11 E
(continue being encapsulated to the RP)72 698.8 Q 5.5(.W)-1.221 G
(hen pack)-5.5 E(ets from S also start to arri)-.11 E .33 -.165(ve n)
-.275 H(ati).165 E -.165(ve)-.275 G(ly at the).165 E(the RP)72 711.8 Q
2.75(,t)-1.221 G(he RP will be recei)-2.75 E(ving tw)-.275 E 2.75(oc)
-.11 G(opies of each of these pack)-2.75 E 2.75(ets. At)-.11 F
(this point, the RP starts)2.75 E(to discard the encapsulated cop)72
724.8 Q 2.75(yo)-.11 G 2.75(ft)-2.75 G(hese pack)-2.75 E
(ets, and it sends a Re)-.11 E(gister)-.165 E(-Stop message back to)-.22
E(Fenner/Handle)72 769 Q(y/Holbrook/K)-.165 E(ouv)-.385 E 182.971
(elas Section)-.165 F 2.75(3. [P)2.75 F(age 6])-.165 E EP
%%Page: 7 7
%%BeginPageSetup
BP
%%EndPageSetup
/F0 11/Times-Roman@0 SF(INTERNET)72 49 Q 71.587(-DRAFT Expires:)-1.012 F
(January 2002)2.75 E(July 2001)123.726 E(S')72 85 Q 2.75(sD)-.605 G 2.75
(Rt)-2.75 G 2.75(op)-2.75 G(re)-2.75 E -.165(ve)-.275 G
(nt the DR unnecessarily encapsulating the pack).165 E(ets.)-.11 E
(At the end of phase 2, traf)72 101.6 Q(\214c will be \215o)-.275 E
(wing nati)-.275 E -.165(ve)-.275 G
(ly from S along a source-speci\214c tree to the).165 E(RP)72 114.6 Q
2.75(,a)-1.221 G(nd from there along the shared tree to the recei)-2.75
E -.165(ve)-.275 G 2.75(rs. Where).165 F(the tw)2.75 E 2.75(ot)-.11 G
(rees intersect, traf)-2.75 E<8c63>-.275 E
(may transfer from the source-speci\214c tree to the RP tree, and so a)
72 127.6 Q -.22(vo)-.22 G(id taking a long detour via the).22 E(RP)72
140.6 Q(.)-1.221 E(It should be noted that a sender may start sending b\
efore or after a recei)72 157.2 Q -.165(ve)-.275 G 2.75(rj).165 G
(oins the group, and)-2.75 E(thus phase tw)72 170.2 Q 2.75(om)-.11 G
(ay happen before the shared tree to the recei)-2.75 E -.165(ve)-.275 G
2.75(ri).165 G 2.75(sb)-2.75 G(uilt.)-2.97 E/F1 11/Times-Bold@0 SF
(Phase 3: Shortest-P)72 209.2 Q(ath T)-.11 E -.198(re)-.814 G(e).198 E