0% found this document useful (0 votes)
28 views7 pages

NFV in Openstack

This paper explores using OpenStack Tacker to implement service function chaining (SFC) on a cloud platform. The authors identify two important issues in deploying reliably and efficiently SFC with Tacker: service placement and policy scaling. They propose two algorithms for finding service location and scaling policy rules. Experiments show the efficiency of their approach compared to default deployment methods provided in Tacker.

Uploaded by

TomCat
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
0% found this document useful (0 votes)
28 views7 pages

NFV in Openstack

This paper explores using OpenStack Tacker to implement service function chaining (SFC) on a cloud platform. The authors identify two important issues in deploying reliably and efficiently SFC with Tacker: service placement and policy scaling. They propose two algorithms for finding service location and scaling policy rules. Experiments show the efficiency of their approach compared to default deployment methods provided in Tacker.

Uploaded by

TomCat
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

AKTH2K2MiBM; L6o avbi2K rBi?

PT2Mai+F
CBMHBM *?2M- uB`2M *?2M- a?B@*?mM hbB- uB@"BM; GBM

LiBQMH *?BQ hmM; lMBp2`bBiv- >bBM+?m- hBrM


&DBMHBMyd8- vB`2M- b+ibB- HBMv'!+bXM+imX2/mXir

#bi`+iěL2irQ`F 6mM+iBQM oB`imHBxiBQM UL6oV Bb i?2B` ~Qr i#H2b KM;2/ #v i?2 a.L +QMi`QHH2`X AM  i`@
 T`QKBbBM; TT`Q+? 7Q` b2`pB+2 T`QpB/2`b iQ `2/m+2 /BiBQMH M2irQ`F 2MpB`QMK2Mi- i?2 M2irQ`F /KBMBbi`iQ`
*S1s M/ PS1s M/ ?b /`rM  HQi Q7 ii2MiBQM ?b iQ KM;2 2+? M2irQ`F /2pB+2 M/ ``M;2 `QmiBM;
7`QK p2M/Q`bX a2`pB+2 6mM+iBQM *?BMBM; Ua6*V T`Q@
pB/2b i?2 #BHBiv iQ /2}M2  b2[m2M+2 Q7 M2irQ`F b2`@ `mH2b QM2 #v QM2X PM i?2 Qi?2` ?M/- a.L /2pB+2b +M #2
pB+2bX h?Bb TT2` B/2MiB}2b irQ BKTQ`iMi Bbbm2b UTH+2@ KM;2/ miQKiB+HHv #v /2p2HQTBM; TTHB+iBQMb 7Q` i?2
K2Mi M/ b+HBM;V QM /2THQvBM; `2HB#Hv M/ 2{+B2MiHv a.L +QMi`QHH2`X
a6* rBi?  +HQm/ THi7Q`KX "b2/ QM i?2 PT2Mai+F h?2`2 `2 b2p2`H QT2M bQm`+2 T`QD2+ib 7Q` L6o /2p2H@
h+F2` `+?Bi2+im`2- r2 2tTHQ`2 TQbbB#H2 bQHmiBQMb M/ QTK2Mi- BM+Hm/BM; PSL6o (9)- PS1L aPl_*1 JLP
BKTH2K2Mi i?2 KBbbBM; 72im`2b BM h+F2` 7Q` a6*X q2
T`QTQb2 irQ H;Q`Bi?Kb 7Q` }M/BM; b2`pB+2 HQ+iBQM M/ (8)- 2i+X >Qr2p2`- i?2b2 /2p2HQTK2Mib `2 biBHH BM i?2 2`Hv
TQHB+v Q7 b+HBM;X h?2 2tT2`BK2Mib b?Qr i?2 2{+B2M+v bi;2bX q2 /QTi PT2Mai+F h+F2` (e)- r?B+? Bb M Q{@
Q7 Qm` TT`Q+? +QKT`2/ rBi? i?2 /27mHi /2THQvK2Mi +BH PT2Mai+F T`QD2+i #mBH/BM;  :2M2`B+ oL6 JM;2`
K2i?Q/b T`QpB/2/ BM PT2Mai+FX q2 HbQ /Bb+mbb M/ UoL6JV M/  L6o P`+?2bi`iQ` UL6oPV iQ KM;2
?B;?HB;?i 7mim`2 rQ`F iQ BKT`Qp2 miBHBxiBQM Q7 +HQm/ L2irQ`F a2`pB+2b M/ oL6b QM M L6o BM7`bi`m+im`2
THi7Q`K 7Q` /2THQvBM; b2`pB+2 7mM+iBQM +?BMBM;X
THi7Q`KX Aib 2p2MimH ;QH Bb iQ BKTH2K2Mi L6o M/ a6*
E2vrQ`/b, a2`pB+2 6mM+iBQM *?BMBM;c aQ7ir`2 .2}M2/
#v /QTiBM; 1ahA JLP `+?Bi2+im`H 7`K2rQ`Fb(d)X
L2irQ`FBM;c PT2Mai+Fc *HQm/ *QKTmiBM;
aBM+2 Bib MMQmM+2K2Mi BM kyR8- h+F2` ?b b?QrM ;`2i
AX AMi`Q/m+iBQM T`QKBb2 BM `2HBxBM; i?2 JLP 7`K2rQ`FX
Hi?Qm;? THi#H2- b2p2`H ?m`/H2b `2KBM M/ M22/ iQ
L2irQ`F 6mM+iBQM oB`imHBxiBQM UL6oV Bb QM2 Q7 i?2
#2 +H2`2/X 6B`bi- i?2 +m``2Mi h+F2` `+?Bi2+im`2 Bb biBHH
?Qii2bi i2+?MQHQ;B2b BM `2+2Mi v2`bX L2irQ`F pB`imH@
BM  T`BKBiBp2 biimbX JMv 7mM+iBQMb K2MiBQM2/ BM i?2
BxiBQM Bb mb2/ iQ b2T`i2 M2irQ`F 7mM+iBQMb 7`QK i?2
T`QTQbH `2 mMpBH#H2 r?2M r2 /2p2HQT2/ Qm` bvbi2KbX
/2bB;Mi2/ ?`/r`2X "2bB/2b QT2`iBM; QM  p`B2iv Q7
a2+QM/- Bi Bb mM+H2` ?Qr i?2 `2bQm`+2b `2 HHQ+i2/ M/
biM/`/ THi7Q`Kb- Bi +M #2 /2THQv2/ /vMKB+HHv QM
Q`+?2bi`i2/X aBM+2 i?2 PT2Mai+F T`QD2+i rb T`QTQb2/
/2KM/ (R)X >2M+2 ?`/r`2 miBHBxiBQM Bb BM+`2b2/ iQ
#27Q`2 JLP `+?Bi2+im`2- i?2 bi`i2;v Q7 bbB;MBM; oJb
`2/m+2 +TBiH 2tT2M/Bim`2b U*S1sVX >`/r`2 /2pB+2b
Bb MQi /2bB;M2/ bT2+B}+HHv 7Q` /2THQvBM; b2`pB+2 +?BMbX hQ
Kv #2 bT`2/ i?`Qm;? b2`pB+2 Qp2` /Bz2`2Mi HQ+iBQMbX
/2p2HQT M 2{+B2Mi a6* #b2/ QM QT2M bQm`+2b- r2 M22/ iQ
6Q` i?2 b2`pB+2 T`QpB/2`b- Bi Bb M BKTQ`iMi Bbbm2 ?Qr iQ
mM/2`biM/ i?2 /2iBHb Q7 `2Hi2/ K2+?MBbKbX AM +2`iBM
/2THQv i?2 pB`imH M2irQ`F 7mM+iBQMb iQ T`QpB/2 2{+B2Mi
Q++bBQMb- Bi M22/b iQ KQ/B7v i?2 Q`B;BMH /2bB;Mb Q7 i?2
b2`pB+2 7mM+iBQM +?BMBM; Ua6*V (k)X
QT2M THi7Q`KbX
qBi? `2+2Mi /pM+2K2Mi BM pB`imHBxiBQM i2+?MQHQ;v-
AM i?Bb TT2`- r2 2tTHQ`2  bQHmiBQM #v mbBM; PT2Mai+F
Bi ?b /`rM  HQi Q7 BMi2`2bib BM BKTH2K2MiBM; L6o rBi?
h+F2` b Qm` THi7Q`K iQ BKTH2K2Mi b2`pB+2 7mM+iBQM
+HQm/ THi7Q`K Ubm+? b PT2Mai+FV M/ aQ7ir`2 .2}M2/
+?BMBM;X h?2 ;QH Q7 i?Bb rQ`F Bb iQ B/2MiB7v BKTQ`@
L2irQ`F [Link] a.L b2T`i2b i?2 +QMi`QH THM2 M/ i?2
iMi Bbbm2b r?BH2 /2p2HQTBM; L6o M/ a6* rBi? +HQm/
/i THM2X lbmHHv- i?2`2 Bb QM2 a.L +QMi`QHH2` BM i?2
THi7Q`KX "2bB/2b BKTH2K2MiBM; b2`pB+2 7mM+iBQM +?BMBM;
+QMi`QH THM2- M/ i?2 /i THM2 +QMbBbib Q7 KMv M2irQ`F
K2+?MBbK- r2 // 2ti` 72im`2b M/ bHB;?iHv KQ/B7v
/2pB+2bX S`Q;`KK2`b +M BKTH2K2Mi M2irQ`F 7mM+iBQMb
i?2 Q`B;BMH `+?Bi2+im`2 Q7 PT2Mai+F h+F2`X h?mb r2
#v /2p2HQTBM; i?2B` TTHB+iBQMb M/ 2K#2/ i?2K BMiQ i?2
+M /2bB;M- BKTH2K2Mi M/ 2tT2`BK2Mi Qm` bvbi2K M/
a.L +QMi`QHH2` iQ +QMi`QH i?2 T+F2i 7Q`r`/BM; BM i?2
H;Q`Bi?Kb 7Q` b2`pB+2 TH+2K2Mi M/ b+HBM;X h?2 `2bi
/i THM2X L2irQ`F /2pB+2b mb2 bT2+B}+ T`QiQ+QHb bm+? b
Q7 i?2 TT2` Bb Q`;MBx2/ b 7QHHQrbX AM a2+iBQM AA- r2
PT2M6HQr (j) iQ +QKKmMB+i2 rBi? i?2 +QMi`QHH2` pB i?2
b?Qr i?2 KQiBpiBQM M/ i?2 `2Hi2/ rQ`FbX AM a2+iBQM
+QMi`QH THM2X L2irQ`F /2pB+2b QM i?2 /i THM2 bBKTHv
AAA - r2 /2b+`B#2 Qm` 2tT2`BK2Mi 2MpB`QMK2Mi M/ Qp2`HH
7Q`r`/ T+F2ib ++Q`/BM; iQ i?2 ~Qr 2Mi`B2b /2}M2/ BM
`+?Bi2+im`2X AM a2+iBQM Ao- r2 b?Qr i?2 K2+?MBbK Q7 Qm`
h?Bb rQ`F rb bmTTQ`i2/ BM T`ib #v i?2 JBMBbi`v Q7 a+B2M+2 M/ b2`pB+2 7mM+iBQM +?BMX h?2 /2iBHb Q7 i?2 H;Q`Bi?Kb rBHH
h2+?MQHQ;v Q7 hBrM mM/2` +QMi`+i JPah Ry9@kekk@3@yyN@yyR M/ #2 /Bb+mbb2/ BM a2+iBQM oX h?2 2tT2`BK2MiH `2bmHib `2
JPah Ry9@kkkR@1@yyN @y9eX b?QrM BM a2+iBQM oAX 6BMHHv- r2 +QM+Hm/2 rBi? a2+iBQM
Nd3@R@8yNy@88eN@kfRdf0jRXyy Ü kyRd A111 oAAX

188
AAX JQiBpiBQM M/ _2Hi2/ qQ`Fb QM 2KTB`B+H bim/v 7Q` #mBH/BM; i?2 7`K2 rQ`F 7Q` a6*
rBi? PT2Mai+F M/ [Link]
L2irQ`F 7mM+iBQMb `2 i?2 +QKTQM2Mib Q` /2pB+2b i?i
`2bB/2 BM i?2 M2irQ`F M/ T`QpB/2 2bb2MiBH 7mM+iBQMHBiv AAAX `+?Bi2+im`2
7Q` i?2 M2irQ`F- bm+? b HQ/ #HM+2- }`2rHHb- .SA- 2i+X
h`/BiBQMHHv- M2irQ`F 7mM+iBQMb `2 T?vbB+H M/ KMm@
HHv +QM};m`2/- bQ Bi Bb MQi 2bv iQ /Dmbi i?2 MmK#2` Q7
b2`pB+2b r?2M i2KTQ``v /2KM/ `Bb2bX L2irQ`F 6mM+@
iBQM oB`imHBxiBQM UL6oV Bb i?2 i2+?MQHQ;v i?i T+Fb
M2irQ`F 7mM+iBQMb BMiQ pB`imH K+?BM2bX Ai Bb 2bB2` iQ
KM;2 oB`imHBx2/ M2irQ`F 7mM+iBQMb i?M T?vbB+H QM2b
M/ i?2`2 Bb KQ`2 ~2tB#BHBivX h?2 Ǵh+F2`Ǵ T`QD2+i }`bi
TT2`2/ BM PT2Mai+F EBHQ (e)X Ai Bb M L6o P`+?2bi`iQ`
b2`pB+2 #b2/ QM 1haA JLP `+?Bi2+im`H 7`K2rQ`F (3)X
>Qr2p2`- i?2 7mHH 7mM+iBQMHBiv r2`2 MQi BKTH2K2Mi2/ i
i?i iBK2X 7i2` r2 i`+2/ i?2 bQm`+2 +Q/2 Q7 h+F2`- r2
7QmM/ i?i Bi QMHv /2}M2/ i?2 SA Q7 i?2 7`K2rQ`FX PM2
Q7 i?2 `2bQMb Kv #2 +mb2/ #v i?2 +QKTH2t `2[mB`2K2Mib
Q7 1haA JLP `+?Bi2+im`H 7`K2rQ`FX hQ AMi2;`i2
L6o BMiQ PT2Mai+F M/ T`QpB/2 a6* r2 /QTi a.L
TT`Q+? 7Q` b+HBM; i?2 b2`pB+2X q?BH2 PT2Mai+F 7Q+mb2b
QM oJ KM;2K2Mi- i?Bb KQiBpi2b mb iQ rQ`F Qmi i?2
KBbbBM; TB2+2bX
h?2 TH+2K2Mi T`Q#H2K 7Q` oL6 ?b #22M bim/B2/ #v
bQK2 T`2pBQmb rQ`Fb (N)- (Ry)- (RR)- (Rk)- (Rj)- (R9)X JQbi
Q7 i?2 rQ`Fb T`QTQb2/ bQHmiBQMb #b2/ QM i?2 KQ/2Hb
rBi? BMi2;2` HBM2` UQ` MQM@HBM2`V T`Q;`Kb Q` ?2m`BbiB+ 6B;X RX  KQ/B}2/ h+F2` `+?Bi2+im`2
H;Q`Bi?Kb iQ QTiBKBx2 i?2 QT2`iBQMH +Qbi Q` KtBKBx2
i?2 MmK#2` Q7 ++2Ti2/ /2KM/bX EmQ 2i HX (N) TQBMi2/ 6B;m`2 R b?Qrb  KQ/B}2/ h+F2` bvbi2K `+?Bi2+im`2-
Qmi i?i i?2 `2HiBQM #2ir22M i?2 HBMF M/ b2`p2` mb@ r?B+? +QMbBbib Q7 9 KQ/mH2b, oL6J UoL6 JM;2`V-
;2 THvb  +`m+BH `QH2 BM oL6 TH+2K2Mi M/ Ti? oL6. UoL6 .2b+`BTiQ`V- .2THQvK2Mi M/ a6* Ua2`pB+2
b2H2+iBQMX GmFQpbxFB M/ a+?KB/ (Ry) T`QTQb2/ M QM@HBM2 6mM+iBQM *?BMBM;VX h?2 L6o bvbi2K Bb BKTH2K2Mi2/
H;Q`Bi?K iQ KtBKBx2 i?2 MmK#2` Q7 b2`pB+2 +?BMb BM #v mbBM; b2`pB+2b 7`QK PT2Mai+F LQp- L2mi`QM M/
 M2irQ`FX J2?`;?/K 2i HX (RR) KQ/2H2/ i?2 +?BMBM; >Q`BxQM- M/ PT2M.vHB;?i *QMi`QHH2` (R8)X h?2`2 `2 9
Q7 M2irQ`F 7mM+iBQMb mbBM;  +QMi2ti@7`22 HM;m;2 M/ bi2Tb 7Q` /2THQvBM; oL6b, URV lT/i2 oL6.- UkV .2THQv
 JBt2/ AMi2;2` Zm/`iB+HHv *QMbi`BM2/ S`Q;`K 7Q` oL6- UjV lT/i2 oL6 *QM}; M/ U9V miQ a+HBM;X
}M/BM; i?2 TH+2K2Mi M/ +?BMBM; i?2 oL6b iQ;2i?2` q2 }`bi /2bB;M  r2#T;2 rBi? PT2Mai+F >Q`BxQM
rBi? i?2 HBKBi2/ M2irQ`F `2bQm`+2b M/ `2[mB`2K2Mib Q7 7Q` mTHQ/BM; oL6. iQ h+F2`Ƕb /i#b2X h+F2` /QTib
i?2 7mM+iBQMbX "`B 2i HX (Rk) bim/B2/ i?2 T`Q#H2K Q7 hPa* (3)-  /2b+`BTiBp2 HM;m;2- iQ /2}M2 i?2 ii`B#mi2b
/2i2`KBMBM; i?2 `2[mB`2/ MmK#2` M/ TH+2K2Mi Q7 oL6b Q7 pB`imHBx2/ M2irQ`F 7mM+iBQMbX  }H2 rBi? hPa*
i?i QTiBKBx2b M2irQ`F QT2`iBQMH +Qbib M/ miBHBxiBQM 7Q`Ki Bb +HH2/  pB`imH M2irQ`F 7mM+iBQM /2b+`BTiQ`
rBi? BMi2;2` HBM2` T`Q;`KKBM;X JQ2Mb M/ hm`+F (Rj) [Link] am+? }H2b `2 T`Q+2bb2/ #v oL6J- M/ `2
T`QTQb2/  7Q`KH KQ/2H 7Q` `2bQm`+2 HHQ+iBQM Q7 oL6b biQ`2/ BM i?2 /i#b2X "2bB/2b i?2 biM/`/ ii`B#mi2b Q7
rBi?BM L6o 2MpB`QMK2Mib-  T`Q#H2K +HH2/ b oB`imH oL6 UBX2X- M2irQ`F- BK;2 M/ b2`pB+2 ivT2V- r2 2ti2M/
L2irQ`F 6mM+iBQM SH+2K2Mi UoL6@SV- M/ 2pHmi2/ i?2 i?2 /2}MBiBQM Q7 oL6. #v BM+Hm/BM; i?2 /2THQvK2Mi
T2`7Q`KM+2 rBi?  bKHH b+H2 b2`pB+2 T`QpB/2`X *Q?2M 2i BM7Q`KiBQM Q7 a6*- bm+? i?i r2 +M /2b+`B#2 i?2 +?BMBM;
HX (R9) T`QpB/2/ M2` QTiBKH TT`QtBKiBQM H;Q`Bi?Kb Q`/2` Q7 oL6b BM  bBM;H2 oL6. }H2X
;m`Mi22BM;  TH+2K2Mi rBi? i?2Q`2iB+HHv T`Qp2M T2`@ h?`Qm;? i?2 >Q`BxQM r2#T;2- r2 +M b2H2+i  oL6.-
7Q`KM+2 rBi? `2bT2+i iQ irQ K2bm`2b, i?2 /BbiM+2 +Qbi rBi? r?B+? h+F2` rBHH /2THQv i?2 oL6 ++Q`/BM;Hv #v
#2ir22M i?2 +HB2Mib M/ i?2 pB`imH 7mM+iBQMb M/ i?2 b2imT Qm` .2THQvK2Mi KQ/mH2X h?2 Q`B;BMH /2bB;M Q7 h+F2`
+Qbib Q7 i?2 oL6bX /2THQvb oL6 rBi? PT2Mai+F >2i (Re)X AMbi2/- r2 TTHv
Pp2`HH- i?2B` 2pHmiBQMb r2`2 KQbiHv /QM2 rBi? bBK@ /B`2+iHv i?2 SAb Q7 PT2Mai+F LQp iQ Q#iBM KQ`2
mHiBQMb M/ i?2`2 rb 72r /Bb+mbbBQM #Qmi i?2 b+HBM; ~2tB#BHBiv 7Q` TH+BM; M/ b+HBM; oL6bX h?2`27Q`2- r2
Bbbm2 7Q` oL6bX AM i?Bb TT2`- r2 //`2bb M/ BKTH2K2Mi KQ/B7v bQK2 Q7 i?2 Q`B;BMH +Q/2b BM h+F2`- bm+? i?i
#Qi? TH+2K2Mi M/ b+HBM; Bbbm2b rBi? PT2Mai+F M/ h+F2` +M KM;2 oL6b rBi? Qm` H;Q`Bi?Kb i?`Qm;?
a.L i2+?MQHQ;B2bX AM Qi?2` rQ`/b- Qm` rQ`Fb 7Q+mb KQ`2 LQp SAX LQp Bb BM +?`;2 Q7 KBMiBMBM; i?2 pB`imH

189
K+?BM2b Q7 PT2Mai+FX qBi? /pM+2/ J2bb;2 Zm2mBM; }`bi `2KQp2 i?2 +Q``2bTQM/BM; ~Qr `mH2b M/ rBi mMiBH
S`QiQ+QH UJZSV- LQp +QMi`QHb >vT2`pBbQ` iQ +`2i2 i?2 oL6 ?b }MBb?2/ 2`HB2` `2[m2bibX PM+2 i?2 `2[m2bib
Q` /2H2i2 pB`imH K+?BM2bX PM+2 2+? oJ 7Q` oL6 Bb iQ i?2 oL6 ?p2 #22M +QKTH2i2/- i?2 h+F2` ;2Mi rBHH
/2THQv2/- i?2 KQ/mH2 7Q` a6* rBHH HBMF i?2 oJb BM i?2 MQiB7v h+F2` iQ `2KQp2 i?2 +Q``2bTQM/BM; oL6X
Q`/2` /2b+`B#2/ BM oL6.X h?2 a6* KQ/mH2 +QMM2+ib
i?2 oL6b BM  T`2/2}M2/ Q`/2` pB PT2Mai+F L2mi`QM oX H;Q`Bi?Kb
M/ PT2M.vHB;?i *QMi`QHH2`X q2 //`2bb i?2 /2iBHb BM q2 /2B;M irQ H;Q`Bi?Kb 7Q` TH+2K2Mi M/ b+HBM;- BM
a2+iBQM AoX Q`/2` iQ T`QpB/2 M 2{+B2Mi M/ bi#H2 b2`pB+2X "2bB/2b
7i2` i?2 a6* KQ/mH2 Bb 2t2+mi2/- r2 M22/ iQ BMbiHH `2/m+BM; i?2 TQi2MiBH M2irQ`F #QiiH2M2+F M/ Qp2`HH
i?2 b2`pB+2 Q7 2+? oL6 QM i?2 oJ- bm+? b b2iiBM; i?2 /2Hv- r2 +M `TB/Hv /2THQv 2ti` oL6b r?2M i?2 `2[m2bi
TQHB+v Q7 }`2 rHHX q2 /2bB;M  h+F2` ;2Mi 7Q` 2+? bm`;2bX
oL6X h?2 ;2Mi +QKKmMB+i2b rBi? h+F2` pB JZSX
h?2 BMbiHHiBQM /2T2M/b QM i?2 ivT2 Q7 b2`pB+2X aBM+2 Qm` X SH+2K2Mi
bvbi2K T`QpB/2b miQ b+HBM;- i?2 MmK#2` Q7 oL6b 7Q` h?2 TH+2K2Mi T`Q#H2K +M #2 //`2bb2/ b  HQ/@
 b2`pB+2 Kv +?M;2 7`QK iBK2 iQ iBK2X A7 i?2 }H2 Q7  #HM+BM; T`Q#H2K (Rd), i?2`2 `2 N Bi2Kb U2+? Q7  ;Bp2M
b2`pB+2 Bb H`;2- Bi Kv +mb2 T`Q#H2Kb, 7Q` 2tKTH2- i?2 r2B;?i pi V- r?B+? `2 iQ #2 bbB;M2/ iQ M K+?BM2bc i?2
}H2b #2+QK2 BM+QMbBbi2Mi BM /Bz2`2Mi oL6b M/ Bi Kv ;QH Bb iQ bbB;M 2+? Bi2K iQ QM2 K+?BM2 bQ iQ KBMBKBx2
rbi2 /BbF bT+2X hQ `2bQHp2 i?2b2 T`Q#H2Kb- r2 /2bB;M i?2 iQiH i`{+ KQM; i?2 K+?BM2bX AM Qm` +b2 2+?
 bvM+?`QMBxBM; K2+?MBbK rBi? L2irQ`F 6BH2 avbi2K Bi2K Bb  +?BM- r?B+? +QMbBbib Q7 b2p2`H oL6bX h?2`27Q`2-
UL6aV 7Q` KM;BM; H`;2 oL6 }H2bX AM i?Bb +b2 h+F2` Qm` Bi2K Kv #2 bbB;M2/ iQ KQ`2 i?M QM2 K+?BM2- B7
;2Mi rBHH KQmMi QM i?2 L6a a2`p2` 7Q` bvM+?`QMBxiBQM M2+2bb`vX
M/ /BbF bT+2 bpBM;X
q?BH2 i?2 b2`pB+2b `2 7mM+iBQMBM;- h+F2` ;2Mi rBHH H;Q`Bi?K R, SH+2K2Mi H;Q`Bi?K
`2;mH`Hv `2TQ`i i?2 oL6 biimb BM+Hm/BM; i?2 mb;2 Q7
AMTmi , *QKTH2i2 :`T? G(V, E)- n,
*Sl M/ K2KQ`vX oL6J rBHH /2i2`KBM2 r?2M iQ b+H2
V Bb i?2 b2i Q7 +QKTmi2 MQ/2b M/ i?2 M2irQ`F MQ/2c
BM Q` Qmi oL6bX Pm` 2tT2`BK2Mib mb2 oL6b 7Q` 6B`2rHH-
n Bb i?2 MmK#2` Q7 oL6b BM  +?BM
GQ/#HM+2 M/ q2# b2`p2` iQ p2`B7v M/ K2bm`2 i?2
PmiTmi, lT/i2/ :`T? G(V, E)
2{+B2M+v Q7 Qm` H;Q`Bi?KbX
R `QQi ← :X`QQi

AoX a2`pB+2 6mM+iBQM *?BMBM; k r?BH2 M = y /Q


j m ← MmHH f m Bb i?2 +m``2Mi #2bi +M/B/i2 f
q2 BKTH2K2Mi a2`pB+2 6mM+iBQM *?BMBM; rBi? PT2M@
9 W eight(root, u) ← ∞
.vHB;?i *QMi`QHH2`X 7i2` PT2Mai+F h+F2` /2THQvb i?2
8 7Q` 7Q` 2+? M2B;?#Q` p Q7 `QQi /Q
oL6b- i?2 a6* KQ/mH2 Bb BM +?`;2 Q7 HBMFBM; i?2 oL6b
e B7 p M/ m ?p2 i?2 bK2 +T+Biv i?2M
BM  bT2+B}+ Q`/2` b /2}M2/ BM oL6.X a6* KQ/mH2
d B7 q2B;?iU`QQi- pV I q2B;?iU`QQi- mV i?2M
+[mB`2b BM7Q`KiBQM Q7 M2irQ`F iQTQHQ;v M/ biimb 7`QK
3 u←v
PT2Mai+F L2mi`QM M/ /2+B/2b i?2 ~Qr `mH2b iQ #2
N 2M/
BMbiHH2/X qBi? _1ah7mH SA- a6* KQ/mH2 TQbib ~Qr `mH2b
Ry 2M/
QM PT2M.vHB;?iX ++Q`/BM;Hv- PT2M.vHB;?i rBHH b2i mT
RR 2Hb2 B7 p ?b  H`;2` +T+Biv i?M m i?2M
i?2 ~Qr `mH2b QM i?2 PT2MparBi+?2b mM/2` Bib +QMi`QH iQ
Rk u←v
`Qmi2 i?2 T+F2ib Q7 2+? oL6 T`QT2`Hv M/ +QKTH2i2 i?2
Rj 2M/
7mM+iBQMHBiv Q7  b2`pB+2 +?BMX aQK2 oL6b- bm+? b HQ/
R9 B7 m ?b 2KTiv +T+Biv i?2M
#HM+2`- `2 +T#H2 Q7 /B`2+iBM; i?2 T+F2i ~Qr M/ i?2v
R8 `2im`M MmHH
/Q MQi M22/ ~Qr `mH2bX 6Q` i?Bb ivT2 Q7 oL6b- r2 M22/ iQ
Re 2M/
b2i mT T`QT2` ii`B#mi2b iQ /B`2+i i?2 T+F2ib iQ i?2 M2ti
Rd AM+`2b2 W eight(root, u) #v R
oL6bX q?BH2 /2THQvBM;  b2`pB+2 +?BM- r2 +M BMbiHH i?2
R3 n ← n− Ui?2 MmK#2` Q7 oL6b ?Qbi2/ i uV
~Qr `mH2b i i?2 bK2 iBK2- bBM+2 i?2 oL6b M22/ bQK2
RN root ← u
BMBiBHBxiBQM #27Q`2 7mM+iBQMBM;X
ky 2M/
PM+2 i?2 +?BM ?b bi`i2/ iQ b2`p2- `2/B`2+iBM; Kv
kR `2im`M G(V, E)
+mb2 bQK2 T`Q#H2Kb- bm+? b r?2M b+HBM; BM M/ QmiX
JQ`2 bT2+B}+HHv- r?2M b+HBM; Qmi- r2 M22/ iQ KF2
bm`2 B7 i?2 oL6b ?p2 #22M BMBiBHBx2/ T`QT2`Hv #27Q`2  b2`p2` i?i ?Qbib i?2 oL6b BM PT2Mai+F Bb +HH2/ 
r2 +M /B`2+i T+F2ib iQ i?2 M2rHv //2/ oL6bX AM Qm` *QKTmi2 LQ/2- r?B+? Bb 2[mBTT2/ rBi? M PT2MparBi+?
BKTH2K2MiiBQM- i?2 h+F2` ;2Mi rBHH MQiB7v h+F2` r?2M M/ +QKKmMB+i2b rBi? Qi?2` MQ/2b pB imMM2Hb U2X;X :_1-
oL6b ?p2 #22M BMBiBHBx2/- M/ i?2M h+F2` rBHH BMbiHH otHM- 2i+VX h?2 L2irQ`F LQ/2 Q7 PT2Mai+F Bb BM +?`;2
+Q``2bTQM/BM; ~Qr `mH2bX aBKBH`Hv- 7Q` b+HBM; BM- r2 Q7 pB`imH M2irQ`F b2`pB+2- r?B+? Bb 2[mBTT2/ rBi? M
+MMQi `2KQp2 i`;2i2/ oL6b `B;?i i?2 rvX q2 M22/ iQ PT2MparBi+? M/ +QKKmMB+i2b rBi? Qi?2` MQ/2b pB

190
imMM2HbX h?2 M2irQ`F 7mM+iBQMb Q7 oJb `2 ?M/H2/ #v H;Q`Bi?K k, a+HBM; H;Q`Bi?K
i?2 L2irQ`F LQ/2X Pm` TH+2K2Mi H;Q`Bi?K }M/b bmBi#H2 AMTmi , hrQ MQM@M2;iBp2 BMi2;2`b K M/ M,
*QKTmi2b LQ/2b 7Q` oL6b BM Q`/2` iQ `2/m+2 i?2 /2Hv M Bb i?2 MmK#2` Q7 oL6 7Q`  bBM;H2 b2`pB+2 BM i?2
#2ir22M irQ *QKTmi2 LQ/2bX "2`;2` (R3) ?b Q#b2`p2/ +?BMc
i?i imMM2HBM; #2ir22M MQ/2b M22/b MQM@i`BpBH +QKTmiBM; K Bb i?2 MmK#2` Q7 #mbv oL6
7`QK *SlX h?mb TH+BM;  b2`pB+2 +?BM BM  bBM;H2 MQ/2 PmiTmi, M BMi2;2` t, t Bb i?2 MmK#2` Q7 oL6
r?2M2p2` TQbbB#H2 rBHH bp2 i?2 *Sl +Qbi M/ i?mb i?2 /2THQv2/ Q` i2`KBMi2/
Hi2M+vX m
R HQ/ 7+iQ` ← n
H;Q`Bi?K R b?Qrb i?2 /2iBHb Q7 i?2 ;`22/v TH+2K2Mi k B7 HQ/ 7+iQ` 4 R i?2M
TT`Q+?X h?2 BMTmib BM+Hm/2 irQ T`ib,  ;`T? G(V, E) j B7 i?2`2 `2 2MQm;? `2bQm`+2 iQ ?Qbi MQi?2` M
BM/B+iBM; i?2 HQ;B+H iQTQHQ;v Q7 i?2 L2irQ`F LQ/2 M/ oL6b i?2M
*QKTmi2 LQ/2bc M/ M BMi2;2` n BM/B+iBM; i?2 MmK#2` Q7 9 `2im`M M
oL6b iQ #2 /2THQv2/X h?2 `QQi Q7 i?2 ;`T? Bb i?2 L2irQ`F 8 2M/
LQ/2- bBM+2 r?2M ++2bbBM; i?2 oL6b Bi }`bi M22/b i?2 e 2Hb2 B7 i?2 `2bQm`+2 Q7 i?2 bvbi2K Bb bm{+B2Mi i?2M
L2irQ`F LQ/2 iQ i`MbHi2 i?2 //`2bbX G(V, E) Bb +imHHv d B7 M = 9 i?2M
i`2i2/ b M mM@/B`2+i2/ +QKTH2i2 ;`T?- r?2`2 2+? TB` 3 B7 HQ/ 7+iQ` I Rf9 i?2M
Q7 LQ/2b +QMM2+i iQ 2+? Qi?2`X 1+? 2/;2 ?b  r2B;?i N `2im`M @Mfk
BM/B+iBM; i?2 MmK#2` Q7 +?BMb TbbBM; #vX AMBiBHHv- i?2 Ry 2M/
r2B;?i Bb yX 1+? 2/;2 r2B;?i Bb BM+`2b2/ #v R- r?2M2p2` RR 2M/
i?2`2 Bb  M2r +?BM mbBM; i?Bb 2/;2X h?2 H`;2` i?2 i?2 Rk 2Hb2 B7 i?2 `2bQm`+2 Q7 i?2 bvbi2K Bb MQi bm{+B2Mi
2/;2 r2B;?i- i?2 KQ`2 b2`pB+2 +?BMb Tbb i?`Qm;?X q?BH2 i?2M
/2THQvBM; i?2 oL6b- r2 +?QQb2 i?2 2/;2b rBi? i?2 bKHH2` Rj B7 M = k i?2M
r2B;?ibX h?2 QmiTmi Q7 i?2 H;Q`Bi?K Bb i?2 ;`T? rBi? R9 B7 HQ/ 7+iQ` I Rfk i?2M
mT/i2/ 2/;2 r2B;?ibX R8 `2im`M @R
h?2 H;Q`Bi?K +QM/m+ib  ;`22/v b2`+? bi`iBM; i i?2 Re 2M/
L2irQ`F LQ/2 UrootV M/ HQQFBM; 7Q`  *QKTmi2 LQ/2 Rd 2M/
UuV rBi? i?2 bKHH2bi 2/;2 r2B;?i #2ir22M i?2K M/ i?2 R3 `2im`M y
H`;2bi `2KBMBM; +T+Biv iQ ++QKKQ/i2 i?2 oL6bX h?2
+T+Biv Q7  *QKTmi2` LQ/2 BM/B+i2b i?2 MmK#2` Q7 oL6
i?i +M #2 ?Qbi2/ QM BiX
A7  bBM;H2 *QKTmi2 LQ/2 Bb bm{+B2Mi iQ ?Qbi i?2 oL6b- i?2 MmK#2` Q7 o6Lb iQ #2 /Dmbi2/X h?2M Qm` bvbi2K mb2
i?2M r2 `2 /QM2c 2Hb2 i?2 H;Q`Bi?K +QMiBMm2b i?2 b2`+? LQp SA iQ KF2 i?2 /DmbiK2MiX
mMiBH Bi }M/b 2MQm;? LQ/2b 7Q` HH i?2 oL6bX qBi? i?2 2/;2 JQ`2 bT2+B}+HHv- i?2 H;Q`Bi?K ?b irQ bi;2b, Bi }`bi
r2B;?ib- r2 +M #HM+2 i?2 HQ/ Qp2` i?2 *QKTmi2 LQ/2bX /2i2`KBM2b B7 i?2 b2`pB+2 Bb Qp2`HQ/2/ Q` MQiX Pp2`HQ/BM;
++Q`/BM; iQ Qm` 2tT2`BK2Mib- Bi b?Qrb i?Bb TT`Q+? +M K2Mb i?i 2+? oL6 Q7  7mM+iBQM BM  +?BM Bb #mbvX
BKT`Qp2 i?2 2{+B2M+v mT iQ 8yW +QKT`2/ iQ i?2 /27mHi A7 Qp2`HQ/BM; M/ i?2 b2`p2` ?b bm{+B2Mi +T+Biv- i?2M
K2i?Q/ T`QpB/2/ #v PT2Mai+F >2iX 6BMHHv- r?2M  r2 /Qm#H2 i?2 MmK#2` Q7 oL6bX Ai iF2b bQK2 iBK2 iQ
+?BM 2M/b Bib b2`pB+2- r2 M22/ iQ `2KQp2 M/ `2+v+H2 i?2 /2THQv i?2 oL6bX A7 +m``2Mi `2[m2bi Bb MQi biBb}2/- M2r
oL6b M/ mT/i2 i?2 2/;2 r2B;?ib Q7 G(V, E)X `2[m2bi rBHH `2+m`X HbQ r2 Q#b2`p2 i?i r?2M i?2 *Sl
?b bm{+B2Mi +Q`2b- Bi iF2b #Qmi i?2 bK2 iBK2 iQ HmM+?
"X a+HBM; KmHiBTH2 oJb b 7Q`  bBM;H2 oJX 1p2M i?Qm;? Qm` bi`i2;v
h?2 b+HBM; H;Q`Bi?K /Dmbib i?2 /2THQvK2Mi Q7 oL6bX Kv Qp2`bmTTHv oJb- Bi iF2b QMHv HBiiH2 iBK2 iQ `2H2b2
q?2M i?2 `2[m2bi BM+`2b2b- i?2 H;Q`Bi?K //b M2r oL6b i?2 2t+2bb oL6bX
iQ i?2 +?BM iQ KBiB;i2 i?2 HQ/X PM i?2 Qi?2` ?M/- A7 i?2 b2`pB+2 Bb MQi Qp2`HQ/2/- i?2M i?2 H;Q`Bi?K
i?2 H;Q`Bi?K rBHH `2/m+2 i?2 oL6b r?2M HQ/ Bb mM/2` /2i2`KBM2b B7 i?2 oL6b `2 Qp2`bmTTHB2/X q2 BKTH2K2Mi
 i?`2b?QH/X  7mM+iBQM Bbam{+B2MiUV iQ +?2+F B7 i?2 T?vbB+H K+?BM2b
H;Q`Bi?K k b?Qrb i?2 /2iBHb Q7 i?2 b+HBM; H;Q`Bi?K- ?p2 2MQm;? `2bQm`+2 Q` MQiX A7 i?2 `2bQm`+2 Bb bm{+B2Mi
r?B+? iF2b irQ BMi2;2` T`K2i2`b, m M/ n- r?2`2 m M/ i?2 HQ/ 7+iQ` Bb bKHH2` i?M Rf9 rBi? n > 4- i?2M
BM/B+i2b i?2 MmK#2` Q7 #mbv oL6b M/ n Bb i?2 MmK#2` i?2 H;Q`Bi?K rBHH `2/m+2 i?2 bBx2 #v ?H7 M/ i?Bb rBHH
Q7 iQiH oL6b Q7  bBM;H2 7mM+iBQM M/ m/n /2}M2b i?2 KBMiBM i?2 HQ/ 7+iQ` `QmM/ RfkX h?2 `2[mB`2K2Mi Q7
HQ/ 7+iQ` Q7 i?2 7mM+iBQMX q?2M i?2 Hi2M+v Q7  b2`pB+2 n > 4 Bb iQ pQB/ 7`2[m2MiHv BM+`2bBM; M/ /2+`2bBM; i?2
BM+`2b2b- r2 bv i?2 oJ ?QbiBM; oL6 #2+QK2b #mbv- MmK#2` Q7 oL6bX q?2M i?2 `2bQm`+2 Bb BMbm{+B2Mi- i?2
?Qr2p2` Bi rBHH /2T2M/ QM i?2 T`QT2`iv Q7 i?2 oL6X 6Q`  H;Q`Bi?K rBHH i`v iQ `2H2b2  `2/mM/Mi oL6 7Q` i?2 Qi?2`
q2# a2`p2`- B7 Bib *Sl `i2 `2+?2b NyW- i?2M Bi H2/b iQ +?BMb BM M22/X AM i?Bb +b2- B7 i?2 HQ/ 7+iQ` Bb bKHH2`
HQM;2` Hi2M+v M/ Bi Bb #mbv 7Q` bm`2X "b2/ QM i?2 HQ/ i?M Rfk M/ n > 2- i?2M i?2 H;Q`Bi?K rBHH `2/m+2 i?2
7+iQ` i?2 b+HBM; H;Q`Bi?K /2+B/2b i?2 b+HBM; TQHB+v M/ MmK#2` Q7 oL6b #v RX aBKBH`Hv- i?2 `2[mB`2K2Mi Q7 n > 2

191
Bb iQ pQB/ mMM2+2bb`v 2t+2bbBp2 BM+`2bBM; M/ /2+`2bBM;
Q7 oL6bX h?2 T2`7Q`KM+2 Q7 i?2 b+HBM; H;Q`Bi?K +M #2
DmbiB}2/ rBi? KQ`iBx2/ MHvbBb b 7QHHQrbX
h?2Q`2K RX h?2 KQ`iBx2/ +Qbi 7Q` 2+? QT2`iBQM 7Q` 
b2[m2M+2 Q7 N b+HBM; Qmi QT2`iBQMb Bb O(1)X
S`QQ7X a+HBM; Qmi  b2`pB+2 BM  +?BM /2T2M/b QM i?2
HQ/ 7+iQ` m/nX G2i S #2 i?2 oL6 b2i Q7  bT2+B}+
b2`pB+2 M/ S.n M/ S.m BM/B+i2b i?2 MmK#2` Q7 oL6b
BM S M/ i?2 MmK#2` Q7 #mbv oL6b- `2bT2+iBp2HvX .2}M2
 TQi2MiBH 7mM+iBQM Φ(S) = 2S.m − [Link] AKK2/Bi2Hv
7i2` /Qm#HBM; i?2 bBx2 Q7 S- r2 ?p2 S.m = S.n/2 M/
Φ(S) = 0X AKK2/Bi2Hv #27Q`2 /Qm#HBM;- S.m = S.n- M/
i?mb Φ(S) = [Link] 6Q` b+HBM; Qmi QMHv- r2 Hrvb ?p2
S.m ≥ S.n/2X 6Q` i?2 +Qbi Q7 i?2 i@i? b+HBM; Qmi- H2i mi
#2 i?2 MmK#2` Q7 #mbv oL6b M/ ni #2 i?2 MmK#2` Q7
oL6b BM S- `2bT2+iBp2Hv- M/ Φi #2 i?2 TQi2MiBH 7i2` i?2
i@i? b+HBM; QmiX G2i ĉi M/ ci #2 i?2 KQ`iBx2/ +Qbi M/ 6B;X kX 1tT2`BK2Mi `+?Bi2+im`2
+imH +Qbi- `2bT2+iBp2Hv 7i2` i?2 i@i? b+HBM; QmiX AMBiBHHv-
m0 = n0 = Φ0 = 0X
"v i?2 TQi2MiBH K2i?Q/- r2 ?p2 ĉi = ci + Φi − Φi−1 X A7 h?2 pB`imH LA* Q7 oJ Bb +QMM2+i2/ iQ i?2 PT2M@
i?2 i@i? b+HBM; /Q2b MQi /Qm#H2 S- i?2M ni = ni−1 M/ mi parBi+? Q7 *QKTmi2 LQ/2- r?B+? ?b i?2 ~Qr `mH2b
BM+`2b2b i KQbi RX h?mb ĉi ≤ 3 Bb #QmM/2/ #v  +QMbiMiX iQ /B`2+i i?2 T+F2ib iQ i?2 BMi2M/2/ /2biBMiBQMX q2
A7 i?2 /Qm#HBM; Bb 2t2+mi2/- i?2M ni = 2ni−1 M/ ni−1 = ?p2 j *QKTmi2 LQ/2b BM Qm` 2tT2`BK2MibX
mi−1 = mi − 1X aQ ĉi = ci + Φi − Φi−1 = mi + (2mi − ni ) − 9V h?2 L2irQ`Fb `2 #mBHi rBi? pB`imH #`B/;2b- BM@
(2mi−1 − ni−1 ) = 3X h?Bb +QKTH2i2b i?2 T`QQ7X biHH2/ rBi? oJr`2 qQ`FbiiBQM- r?B+? +QMbBbib Q7
j T`ib 7Q` 2ti2`MH M2irQ`F- KM;2K2Mi M2irQ`F
h?2 7QHHQrBM; Bb bBKBH` iQ i?2 `;mK2Mi 7Q` /vMKB+
M/ BMi2`MH M2irQ`FX h?2 2ti2`MH M2irQ`F +QM@
i#H2 (RN)X
M2+ib iQ Tm#HB+ M2irQ`FX h?2 KM;2K2Mi M2irQ`F
h?2Q`2K kX h?2 KQ`iBx2/ +Qbi 7Q` 2+? QT2`iBQM 7Q`  ?M/H2b i?2 2t+?M;2 Q7 KM;2K2Mi BM7Q`KiBQM
b2[m2M+2 Q7 N b+HBM; Qmi M/ b+HBM; BM QT2`iBQMb Bb O(1)X Q7 PT2Mai+F (kR)X h?2 BMi2`MH M2irQ`F Bb mb2/
#v oJb 7Q` +QKKmMB+iBQMX q2 HbQ BMbiHH :_1
S`QQ7X aBKBH`Hv- H2i S #2 i?2 oL6b Q7  bT2+B}+ b2`pB+2X
imMM2Hb KQM; PT2MparBi+?2b Q7 *QKTmi2 LQ/2b
>2`2 r2 /2}M2 i?2 TQi2MiBH 7mM+iBQM b 7QHHQrb,
 M/ L2irQ`F LQ/2X
2mi − ni , B7 HQ/ 7+iQ` ≥ 1/2- 6Q` *QMi`QHH2` LQ/2 M/ L2irQ`F LQ/2- r2 2+? HHQ@
Φi (S) =
ni /2 − mi , B7 HQ/ 7+iQ` < 1/2X +i2 R *Sl +Q`2 M/ 9:" _JX 6Q` 2+? *QKTmi2 LQ/2-
qBi?  bBKBH` `;mK2Mi b #Qp2- r2 +M b?Qr i?i i?2 r2 HHQ+i2 9 *Sl +Q`2b M/ 3:J _JX q2 +`2i2 oL6b
KQ`iBx2/ +Qbi Bb #QmM/2/ #v  +QMbiMiX 7Q` }`2rHH- HQ/ #HM+2 M/ r2# b2`p2`X 1+? oL6 ?b
8RkJ" _J M/ R pB`imH *SlX aBM+2 i?2 2M/TQBMi Q7 Qm`
oAX 1tT2`BK2Mib b2`pB+2 +?BM Bb r2# b2`p2`- r2 mb2 T+?2"2M+? U#V (kk)
b b?QrM BM 6B;m`2 k- r2 mb2 oJq`2 rQ`FbiiBQM(ky) iQ 2pHmi2 Qm` 2tT2`BK2MibX T+?2"2M+? Bb bT2+B}+HHv
iQ b2i mT Qm` 2tT2`BK2Mi 2MpB`QMK2Mi- r?B+? +QMbBbib Q7 j mb2/ iQ i2bi i?2 T2`7Q`KM+2 Q7 p`BQmb q2# a2`p2`b- M/
*QKTmi2 LQ/2b M/ j M2irQ`FbX h?2 7mM+iBQMHBiv Q7 2+? Bi T`QpB/2b b2p2`H T`K2i2`b iQ imM2 i?2 bvbi2K 7Q`
+QKTQM2Mi Bb BHHmbi`i2/ b 7QHHQrb, 2tT2`BK2MibX aBM+2 T+?2"2M+? HbQ T`QpB/2b i?2 b2`pB+2
Q7 q2# a2`p2` M/ i?mb Bi +M K2bm`2 i?2 T2`7Q`KM+2
RV h?2 *QMi`QHH2` LQ/2 Bb mb2/ 7Q` i?2 +QMi`QH THM2 Q7
Q7  +?BM i?i BM+Hm/2b q2# a2`p2`X h?2`27Q`2- Bi Bb 
PT2Mai+F- r?B+? +QMbBbib Q7 b2`pB+2b 7Q` B/2MiBiv-
p2`v ?M/v iQQH 7Q` 2pHmiBM; Qm` TH+2K2Mi M/ b+HBM;
/b?#Q`/- M2irQ`F b2`p2`X h+F2` M/ a.L +QM@
H;Q`Bi?KbX
i`QHH2` `2 HbQ /2THQv2/ QM i?Bb MQ/2X
kV L2irQ`F LQ/2 iF2b +`2 Q7 i?2 M2irQ`F Q7 PT2M@
X SH+2K2Mi 2tT2`BK2Mi
ai+FX qBi? L2mi`QM SA- mb2`b +M b2i mT p`BQmb
Q7 pB`imH M2irQ`F 2MpB`QMK2MibX h?`Qm;? PT2M@ q2 +QKT`2 i?2 2{+B2M+v Q7 Qm` TH+2K2Mi TQHB+v
parBi+?- oJb BM *QKTmi2 LQ/2b +M +QMM2+i iQ rBi? i?2 /27mHi /2THQvBM; K2i?Q/ Q7 >2iX q2 i2bi irQ
Tm#HB+ M2irQ`F pB i?2 1ti2`MH L2irQ`FX b+2M`BQb rBi? 2+? b2`pB+2 +?BM +QMbBbiBM; Q7 }`2rHH- HQ/
jV h?2 ?vT2`pBbQ` Bb `mM QM i?2 *QKTmi2 LQ/2 iQ #HM+2` M/ r2# b2`p2`X q2 mb2 T+?2"2M+? iQ K2bm`2
`2+2Bp2 `2[m2bi 7`QK *QMi`QHH2` LQ/2 iQ HmM+? oJbX i?2 T2`7Q`KM+2 Q7 i?2 r2# b2`p2`X HQM; i?2 b2`pB+2

192
+?BM- r2 HbQ K2bm`2 i?2 Hi2M+v Q7 2+? b2`pB+2X AM i?Bb imMM2H 2M+TbmHiBQMf/2+TbmHiBQM M/ i?mb BKT`Qp2b i?2
2tT2`BK2Mi- r2 /B/ MQi +iBpi2 i?2 b+HBM; H;Q`Bi?KX T2`7Q`KM+2X

"X a+HBM; 2tT2`BK2Mi


h?2`2 `2 irQ T`ib 7Q` i?Bb 2tT2`BK2Mi, QM2 7Q` b+HBM;
Qmi M/ i?2 Qi?2` 7Q` b+HBM; BMX 6Q` +QKT`BbQM- r2
/2bB;M  MBp2 b+HBM; K2i?Q/- r?B+? b+H2b Qmi oL6b
QM2 #v QM2 mMiBH i?2 b2`pB+2 +?BM Bb MQi Qp2`HQ/2/X AM
i?Bb 2tT2`BK2Mi- r2 /2THQv  b2`pB+2 +?BM- r?B+? +QMbBbib
Q7 QM2 HQ/ #HM+2` M/ QM2 r2# b2`p2`X .m`BM; i?2
2tT2`BK2Mi- i?2 bvbi2K rBHH /2i2+i B7 Bi M22/b iQ b+H2
i?2 r2# b2`p2`X AMBiBHHv- T+?2"2M+? `2T2i2/Hv b2M/b
`2[m2bib 7Q` QM2 b2+QM/ M/ K2bm`2b i?2 p2`;2 Hi2M+vX
h?2M Bi BM+`2b2b  H`;2 MmK#2` Q7 `2[m2bib iQ i?2 r2#
b2`p2` i i?2 Ryi? b2+QM/ M/ 8yi? b2+QM/- `2bT2+iBp2HvX

6B;X jX Gi2M+v rBi? TH+2K2Mi M/ rBi?Qmi TH+2K2Mi H;Q`Bi?K UR


`2[m2bi 2+? iBK2V

6B;m`2 j BHHmbi`i2b i?2 +mKmHiBp2 T`Q##BHBiv Q7 i?2


}`bi b+2M`BQ- r?2`2 r2 2bi#HBb?  b2`pB+2 +?BM M/
`2T2i2/Hv b2M/  `2[m2bi iQ Bi 7Q`  KBHHBQM iBK2bX q2
+H+mHi2 i?2 p2`;2 Hi2M+v- r?B+? Bb jXyjNKb 7Q` i?2 /2@
7mHi K2i?Q/ M/ kXkj9 Kb rBi? Qm` TH+2K2Mi H;Q`Bi?KX
Ai BKT`Qp2b #Qmi keX8WX

6B;X 8X Gi2M+v rBi? b+HBM; H;Q`Bi?K M/ MQ`KH b+HBM; K2i?Q/

b b?QrM BM 6B;m`2 8- #Qi? K2i?Q/b +M // M2r oL6


BM jy b2+QM/b M/ `2/m+2 i?2 Hi2M+vX h?2 }`bi iBK2 r?2M
i?2 `2[m2bi BM+`2b2b- #Qi? K2i?Q/b BM+`2b2 QM2 oL6 M/
i?2`2 Bb MQ bB;MB}+Mi /Bz2`2M+2X AM i?2 b2+QM/ BM+`2b2 Q7
i?2 `2[m2bib- Qm` b+HBM; H;Q`Bi?K /Qm#H2b i?2 MmK#2` Q7
oL6b- M/ i?2 Hi2M+v /`QTb BM  Km+? b?Q`i2` iBK2X q?BH2
i?2 MBp2 b+HBM; K2i?Q/ iF2b #Qmi irB+2 b Km+? iBK2
iQ `2/m+2 i?2 Hi2M+v iQ i?2 bK2 H2p2HX 6`QK i?2 };m`2-
r2 b22 i?i i i?2 3yi? b2+QM/- #Qi? TT`Q+?2b `2/m+2 i?2
Hi2M+v rBi? i?2 bK2 2{+B2M+vX h?2 MBp2 K2i?Q/ iF2b
#Qmi jy b2+QM/ iQ HmM+? MQi?2` oL6 M/ i?2 Hi2M+v
6B;X 9X Gi2M+v rBi? TH+2K2Mi M/ rBi?Qmi TH+2K2Mi H;Q`Bi?KU8y
`2[m2bib 2+? iBK2V rBHH #2 `2/m+2/ iQ i?2 H2p2H b rBi? Qm` b+HBM; H;Q`Bi?K
i i?2 RRyi? b2+QM/X
q?2M i?2 MmK#2` Q7 `2[m2bib BM+`2b2b- M2irQ`F Kv 6Q` b+HBM; BM- r2 i2bi #v `2H2bBM; `2bQm`+2 7`QK  MQM@
+QM;2bi 2bBHvX Pm` T2`7Q`KM+2 BKT`Qp2K2Mi #2+QK2b #mbv b2`pB+2 +?BM M/ +`2iBM; oL6b 7Q` M Qp2`HQ/2/
KQ`2 bB;MB}+MiX 6B;m`2 9 BHHmbi`i2b i?2 `2bmHi Q7 i?2 +?BMX b b?QrM BM 6B;m`2 e- r2 ?p2 k b2`pB+2 +?BMb M/
b2+QM/ b+2M`BQ- r?2`2 r2 b2i mT 9 b2`pB+2 +?BMb M/ #Qi? T`QpB/2 HQ/ #HM+2` M/ r2# b2`p2`bX h?2 }`bi +?BM
`2T2i2/Hv b2M/ 8y `2[m2bib iQ 2+? +?BM 7Q`  KBHHBQM ?b 8 r2# b2`p2`b M/ Bb bi#H2- q?BH2 +?BM k ?b QMHv
iBK2bX h?2 /27mHi K2i?Q/ ?b p2`;2 Hi2M+v j8Xjd9KbX QM2 r2# b2`p2` M/ Bb Qp2`HQ/2/X 6Q` i?2 KQK2Mi i?2`2
q?BH2 i?2 p2`;2 Hi2M+v rBi? Qm` TH+2K2Mi H;Q`Bi?K Bb MQ 2ti` `2bQm`+2 iQ +`2i2 M2r oL6 M/ i?2 b2+QM/
Bb RNXe98KbX Ai Bb M BKT`Qp2K2Mi Q7 99X8WX 6Q` i?2 rQ`bi +?BM Bb Qp2`HQ/2/X i i?2 Ryi? b2+QM/- r2 +H2M mT i?2
+b2- Bi /`QTb 7`QK NeXdeKb iQ 9eXyRkKbX Ai b?Qrb i?i Qm` `2[m2bib Q7 +?BM R M/ b+H2 BM #v `2H2bBM;  oL6- bm+?
TH+2K2Mi H;Q`Bi?K bp2b  HQi Q7 +QKTmiiBQM 7Q` :_1 i?i +?BM k +M `2mb2 BiX i i?2 9kM/ b2+QM/- +?BM k

193
(k) JX *X GmBx2HHB- GX _X "vb- GX aX "m`BQH- JX SX "`+2HHQb- M/
GX SX :bT`v- dzSB2+BM; iQ;2i?2` i?2 M7p T`QpBbBQMBM; TmxxH2,
1{+B2Mi TH+2K2Mi M/ +?BMBM; Q7 pB`imH M2irQ`F 7mM+iBQMbX-Ǵ
BM AJ U_X "/QMM2H- CX sBQ- aX i- 6X .X hm`+F- oX :`Qx- M/
*X _X SX /Qb aMiQb- 2/bXV- TTX N3ĜRye- A111- kyR8X
(j) LX J+E2QrM- hX M/2`bQM- >X "HF`Bb?MM- :X S`mHF`-
GX S2i2`bQM- CX _2t7Q`/- aX a?2MF2`- M/ CX hm`M2`- dzPT2M6HQr,
1M#HBM; AMMQpiBQM BM *KTmb L2irQ`Fb-Ǵ aA:*PJJ *QK@
TmiX *QKKmMX _2pX- pQHX j3- TTX eNĜd9- J`X kyy3X
(9) dzPTM7p, PT2M THi7Q`K 7Q` M7pXǴ ?iiTb,ffrrrXQTM7pXQ`;fX
(8) dzPT2M bQm`+2 KMQXǴ ?iiTb,ffrrrXQbKX2ibBXQ`;fX
(e) dzPT2Mbi+F i+F2`XǴ ?iiTb,ffrBFBXQT2Mbi+FXQ`;frBFBfh+F2`X
(d) 1X :X JLyyR- dzJM;2K2Mi M/ Q`+?2bi`iBQM UKMQV-Ǵ kyR9X
(3) dzhQb+ i2KTHi2 7Q` M7pXǴ ?iiT,ff/Q+bXQbBb@QT2MXQ`;fiQb+f
iQb+@M7pfpRXyfiQb+@M7p@pRXyX?iKHX
(N) hX@qX EmQ- "X@>X GBQm- *X@CX GBM- M/ JX@CX hbB- dz.2THQvBM;
+?BMb Q7 pB`imH M2irQ`F 7mM+iBQMb, PM i?2 `2HiBQM #2ir22M HBMF
M/ b2`p2` mb;2-Ǵ BM A111 AL6P*PJ- kyReX
(Ry) hX GmFQpbxFB M/ aX a+?KB/- dzPMHBM2 /KBbbBQM +QMi`QH M/
2K#2//BM; Q7 b2`pB+2 +?BMb-Ǵ BM aA_P**P- kyR8X
6B;X eX Gi2M+v rBi? irQ +?BMb Q7 oL6b (RR) aX J2?`;?/K- JX E2HH2`- M/ >X E`H- dzaT2+B7vBM; M/ TH+BM;
+?BMb Q7 pB`imH M2irQ`F 7mM+iBQMb-Ǵ BM A111 *HQm/L2i- kyR9X
(Rk) JX 6X "`B- aX _X *?Qr/?m`v- _X ?K2/- M/ _X "Qmi#- dzPM
Q`+?2bi`iBM; pB`imH M2irQ`F 7mM+iBQMb BM M7p-Ǵ `sBp 2@T`BMib-
HmM+?2b MQi?2` r2# b2`p2` iQ KBiB;i2 i?2 HQ/X Ai iF2b kyR8X
#Qmi jk b2+QM/b- r?B+? Bb #Qmi 9@8 b2+QM/b KQ`2 i?M (Rj) >X JQ2Mb M/ 6X .X hm`+F- dzoM7@T,  KQ/2H 7Q` 2{+B2Mi TH+2@
b+HBM; QmiX h?2 2ti` iBK2 Bb +mb2/ #v i?2 b+HBM; BM Q7 K2Mi Q7 pB`imHBx2/ M2irQ`F 7mM+iBQMb-Ǵ BM A111 *LaJ- kyR9X
(R9) _X *Q?2M- GX G2rBM@1viM- CX LQ`- M/ .X _x- dzL2` QTiBKH
+?BM RX i i?2 dyi? b2+QM/- Bi iF2b #Qmi k3 b2+QM/b iQ TH+2K2Mi Q7 pB`imH M2irQ`F 7mM+iBQMb-Ǵ BM A111 AL6P*PJ-
HmM+? i?2 b2+QM/ r2# b2`p2` 7Q` +?BM kX h?Bb Bb 7bi2` kyR8X
#2+mb2 Q7 i?2 7+i i?i +?BM R ?b H`2/v `2H2b2/ i?2 (R8) dzPT2M.vHB;?iXǴ ?iiTb,ffrrrXQT2M/vHB;?iXQ`;fX
(Re) dzPT2Mbi+F ?2iXǴ ?iiTb,ffrBFBXQT2Mbi+FXQ`;frBFBf>2iX
`2[mB`2/ `2bQm`+2 7Q` +?BM kX (Rd) .X SX qBHHBKbQM M/ .X "X a?KQvb- h?2 .2bB;M Q7 TT`QtBK@
6`QK i?2 #Qp2 2tT2`BK2Mib- r2 Q#b2`p2 i?i Bi iF2b iBQM H;Q`Bi?KbX *K#`B/;2 lMBp2`bBiv S`2bb- kyRRX
(R3) hX "2`;2`- dzMHvbBb Q7 *m``2Mi oSL h2+?MQHQ;B2bX-Ǵ BM _1a-
#Qmi k8b iQ //  M2r oL6- r?BH2 Bi iF2b QMHv 8b iQ TTX Ry3ĜRR8- A111 *QKTmi2` aQ+B2iv- kyyeX
`2KQp2  oL6X Ai K2Mb `2KQpBM; oL6 Bb Km+? 7bi2` (RN) hX >X *Q`K2M- *X 1X G2Bb2`bQM- _X GX _Bp2bi- M/ *X ai2BM-
i?M +`2iBM; QM2X "v iFBM; /pMi;2 Q7 i?Bb Q#b2`piBQM- AMi`Q/m+iBQM iQ H;Q`Bi?KbX h?2 JAh S`2bb- j`/ 2/X- kyyNX
(ky) dzoKr`2XǴ ?iiT,ffrrrXpKr`2X+QKX
r2 +M Hrvb b+H2 Qmi KQ`2 oL6b M/ `2KQp2 i?2 2t+2bb (kR) dzPT2Mbi+FXǴ ?iiTb,ffrBFBXQT2Mbi+FXQ`;frBFBfJBMnS;2X
QM2 B7 M2+2bb`vX h?Bb rBHH ?2HT bT22/ mT i?2 b+HBM; QmiX (kk) dzT+?2 T+?2#2M+?XǴ ?iiTb,ff?iiT/XT+?2XQ`;f/Q+bfkX9f
T`Q;`Kbf#X?iKHX
oAAX *QM+HmbBQM

AM i?Bb TT2`- r2 b?Qr ?Qr iQ BKTH2K2Mi i?2 K2+?@


MBbK 7Q` b2`pB+2 7mM+iBQM +?BMBM; rBi? PT2Mai+F h+F2`
M/ PT2M.vHB;?iX hQ +QKTH2i2 i?2 7mM+iBQMHBiv- r2
BKTH2K2Mi i?2 KBbbBM; 72im`2b b +HBK2/ BM h+F2`X q2
HbQ /2bB;M H;Q`Bi?Kb 7Q` b2`pB+2 TH+2K2Mi M/ b+HBM;
BMfQmiX *QKT`2/ rBi? i?2 bi`B;?i7Q`r`/ K2i?Q/b- Qm`
H;Q`Bi?Kb `2/m+2 i?2 Hi2M+v bB;MB}+MiHvX 6Q` b+HBM;
Qmi- Qm` H;Q`Bi?K KBiB;i2b i?2 HQ/ KQ`2 2z2+iBp2HvX h?2
2tT2`BK2MiH `2bmHib b?Qr i?i Qm` TT`Q+? +M BKT`Qp2
i?2 2{+B2M+v bB;MB}+MiHv 7Q` b2`pB+2 7mM+iBQM +?BMBM;X
Pm` `2bmHib T`QpB/2 pHm#H2 2tT2`B2M+2b 7Q` /2HBp2`BM;
oL6 bQHmiBQM rBi? +HQm/ THi7Q`Kb- 2bT2+BHHv PT2Mai+FX
hQ ?p2  +QKTH2i2 oL6 bvbi2K- K2+?MBbK 7Q` 2{+B2Mi
M/ miQ HBp2 KB;`iBQM rBHH #2 M2+2bb`vX Ai rBHH /2T2M/
QM i?2 KB;`iBQM K2+?MBbK Q7 +HQm/ THi7Q`KX q2 H2p2
Bi b  7mim`2 rQ`FX

_272`2M+2b

(R) dzL2irQ`F 7mM+iBQMb BM/mbi`v bT2+B}+iBQM ;`QmTX ǴM2irQ`F 7mM+@


iBQM pB`imHBxiBQM UM7pV, M BMi`Q/m+iBQM- #2M2}ib- 2M#H2`b-
+?HH2M;2b M/ +HH 7Q` +iBQMǴ-Ǵ TX R–Re- BM a.L M/ PT2M6HQr
qQ`H/ *QM;`2bb- kyRkX

194

You might also like