文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 人文社科 > 文学研究 > compressing forwarding tables for datacenter scalability
侵权投诉

compressing forwarding tables for datacenter scalability

ROTTENSTREICHetal.:COMPRESSINGFORWARDINGTABLESFORDATACENTERSCALABILITY145

ByDe nition4oftheFIBencodingwidth,wecanseethattheencodingwidthofanencodingschemeCA=(¯σ1,σ2)canbepresentedas

(C A)=imax

∈[1,h]

(¯σ1(ai1))

+

(σ2(ai2))

=ymax

∈Sφ

(13)

2

σ¯1(y)+ (σ2(y)).

Weobservethatinordertocalculatetheoptimalencoding

σ2giventhatσ1:=¯σy∈S1,itisenoughtoknowφ (¯σσ¯1(y)forany

2whiletheexactvaluesof1(s1,1)),..., (¯σ1(srequired.Thisisbecause

1,n))arenotnecessarilyOPT(A|σ1:=σ¯1)=Cmin

(CA)

A=( σ1:=¯σ1,σ2)

=Cmin

A=(σ1:=¯σ1,σ2)

imax∈[1,h]

(¯

σ1(ai1))+ (σ2(ai))

2=

Cmin

max φ(y)+ (σ σ¯A=(σ1:=¯σ1,σ2)y∈S2

12(y)).

(14)Beforepresentingthealgorithm,wesuggestthefollowing

lemma.

Lemma5.Thereexistsa(pre x)encodingσ¯(σσ2ofS2suchthatthe1,σFIB2)=(¯encoding1,σ¯2)achievestheminimalencodingwidthofall

schemes{(σ1,σ2)|σ1:=¯σ

1}andsatis es( y∈S2),φσ¯1(y)+ (¯σ2(y))=OPT(A|σ1:=σ¯1).(15)Proof.LetC A=(σ1schemethatsatis es (C

:=σ¯1,σ 2)beaFIBencoding

A)=OPT(A|σ( y∈S1:=σ¯1).If2),φσ¯1(y)+ ( σ

2(y))=OPT(A|σσ¯ 1:=σ¯1)thende nition2=σ

2canbetherequestedencoding.Otherwise,bytheof (C A),( y∈Sσ¯2),φσ¯1(y)+ ( σ

2(y))≤ (C OPT(A|σA)=1:=1).ThisisbecausebyEquationCσ (13),for A=(¯1,σ 2)wehave (C A)=maxy∈S2φσ¯1(y)+

(σ

2(y)).Fory∈S2weusethenotationq(y)=

OPT(A|σ¯encodingσ¯1:=σ1) (φσ¯1(y)+ ( σ

2(y))).Wede nean2ofS2basedon σ

2asσ¯2(y)=σ 2(y)·0q(y)wherethe·signisusedtorepresenttheconcatenationoperation.In

particular,iffory∈S σ¯2,φσ¯1(y)+ (σ

2(y))=OPT(A|σ1)thenσ¯y∈S2(y)=σ 2(y)·0q(y)

=σ 1:=2(y).Wecanseethat( 2),φσ¯1(y)+ (¯σOPT(A|σ2(y))=φσ¯1(y)+ ( σ

2(y))+q(y)=1:=¯σ

1).Thusσ¯2satis estherequiredequality.Tocompletetheproofwehavetoshowalsothatσ¯apre xencoding.Wecan rstverifythatthen2isindeeddifferent.Ifforanyx,y∈S2=|Scodewordsofσ2|σ¯2(x)=σ

(x)2are·0q(x)=σ 0q(y)=σ¯2(s.t.x=y),

σ 22(y)·2(y)thennecessarily2(x)isapre xofσ (x)2(y)(ifq(x)≥q(y))orσ ofσ ≤q(y)),acontradictionsince2(y)isapre x2(x)(ifqσ pre xencoding.σ¯2isa)=σ 2alsopreserversthepre xpropertysinceifσ¯2(x2(x)·0q(x)isapre xofσ¯2(y)=σ 2(y)·0q(y)thenagaineitherσ 2(x)isapre xofσ 2(y)orσ 2(y)isapre xofσ2(x).

BasedonthelastlemmawecandeducefromKraft’s

inequality,theexactvalueofOPT(A|σ1:=¯σ

1).Theorem6.TheoptimalconditionalFIBencodingwidthof

Asatis es

OPT(A|σ1:=¯σ)= 1 ¯(y)

1 log2

2φσ (16)y∈S 2 .Proof.Weσ¯ rst

1)≥log wouldliketo showthatOPT(A|σ1:=2y∈Sφσ¯(y221

).ConsideraFIBencod-ing(σ1,σ2)=(¯σσ¯1,σ¯2)thathasanencodingwidthofOPT(A|σ (¯σ1:=1)and( y∈S2)satis esφσ¯1(y)+

2(y))=OPT(A|σ¯1).Thelastequalitycanbepresentedalsoas (¯σ1:=σ

2(y))=OPT(A|σ1:=σ¯1) φσ¯1(y).SuchanencodingexistsbyLemma5.ByKraft’sinequalityσ¯2satis es

1≥

2 (¯σ2(y))

= 2 OPT(A|σ1:=¯σ1) φσ¯1(y)y∈S2

y∈S2

2

OPT(A|σ1:=¯σ1)

≥

2φ¯σ

1(y)y

∈S2

OPT(A|σ1:=σ¯1)≥

φσ¯1(y)

log2

2

(17)

y∈S 2

,

wherethelastinequalityisobtainedsinceOPT(A|σσ¯)isofcourseaninteger.Tocompletetheproof1:=1wewould

log also liketoshowthatOPT(A|σ1:=σ¯1)≤2φ(y) σ¯1by ndingaFIB(σy∈S22

encodingscheme1,σ2)=(¯σ1,σ¯2)whoseencodingwidthsatis esthisupper Todolog bound. 2

so,wedenotebyvσ¯1theterm

2y∈Sφσ¯21(y).Then,2 (vσ¯1 φσ¯1(y))= 2φσ¯1(y) vσ¯1= 2φ¯σ1(y)·2 v¯σ

1y∈S2

y∈S2

≤

2

φσ¯1(y)

·

y∈S2

2

φσ¯ 1

1(y)

=1.y∈S2y∈S2

(18)

Thusthereexistsapre xencodingσ¯y))=(v(y))fory∈2withcodewordlengths (¯σ2(σ¯1 φσ¯1SC2.TheFIBencodingschemeA=(¯σ1,σ¯2)satis es

(C=max y∈Sφ

A)2

σ¯1(y)+ (¯σ2(y))(19)=max y∈Sφy)+(v(y)))

2

σ¯1(σ¯1 φσ¯1=max y∈Sv

2

σ¯1=vσ¯1.

Then,OPT(A|σ1:=σ¯1)≤v

σ¯1=log

2

y∈Sφσ¯2

2

1(y)

.

Now,whenthecodewordlengthsoftheelementsofSfromLemma5andTheorem6,itiseasyto nd2are

knownsuchanencodingasexplainedearlierinSectionIII.

Basedonthesuggestedoptimalconditionalencodingfromabove,wenowsuggesttwodirectionsto ndanef cientencodingschemeforagiventwo-columnFIBtable.Ofcourse,thesedirectionsarealternativesfortheencodingofgeneralFIBtablespresentedinSectionIII-Bthatcanbeappliedalsofortwo-columntables.The rstdirectionmaybeconsidered

上一页第8页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email