a dynamic lookup scheme for bursty access patterns_infocom2001.ps

本函数的作用就是把读取内存的物理地址,之后找到物理页面的首地址返回过来...它专门找物理地址的 具体东西很多都用汇编编写.好像C很难完成吧 毕竟要用一些调用的 ...哈哈 后面的程序会调用啦 因为每一

D<0F3C30E62040606060606060204030C02F00600060003FE03FF06018C00CC00CC00C60
1830300FC00F147F8C11>103 D<F0303030303030303030303030303030303030FC0614
7F9309>108 D<0FC0186020106018C00CC00CC00CC00CC00C6018601838700FC00E0D7F
8C11>111 D E /Fl 133[16 18 18 28 18 21 12 16 16 1[21
21 21 30 12 18 12 12 21 21 12 18 21 18 21 21 12[23 21
25 1[25 30 1[35 23 2[14 2[25 25 1[28 25 25 6[14 1[21
21 21 21 21 21 21 21 2[10 14 3[14 14 40[{}51 41.666668
/Times-Italic rf /Fm 2 122 df<0C000C008C40EDC07F800C007F80EDC08C400C000C
000A0B7D8B10>3 D<1818181818FFFF18181818181818181818181818181808167D900E>
121 D E /Fn 8 107 df<FFFFFF80FFFFFF8019027D8A20>0 D<01800180018001804182
F18F399C0FF003C003C00FF0399CF18F4182018001800180018010127E9215>3
D<000001800000078000001E00000078000001E00000078000001E00000078000001E000
00078000001E00000078000000E0000000780000001E0000000780000001E00000007800
00001E0000000780000001E0000000780000001E00000007800000018000000000000000
0000000000000000000000000000000000000000007FFFFF00FFFFFF8019227D9920>20
D<7FC0FFC0C000C000C000C000C000C000C000C000C000C000C000C000C000C000C000C0
00C000C000C000C000C000C000C000C000C000C000C000C000C000C000C000C000C000C0
00C000C000C000C000C00040000A2A799E12>100 D<FFC0FFC000C000C000C000C000C0
00C000C000C000C000C000C000C000C000C000C000C000C000C000C000C000C000C000C0
00C000C000C000C000C000C000C000C000C000C000C000C000C000C000C000C000400A2A
809E12>I<003C00E001C001800380038003800380038003800380038003800380038003
800380030007001C00F0001C000700030003800380038003800380038003800380038003
80038003800380018001C000E0003C0E297D9E15>I<F0001C0007000300038003800380
0380038003800380038003800380038003800380018001C000E0003C00E001C001800380
038003800380038003800380038003800380038003800380030007001C00F0000E297D9E
15>I<C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0
C0C0C0C0C0C0C0C002297B9E0C>106 D E /Fo 19 112 df<004000800100020006000C
000C0018001800300030007000600060006000E000E000E000E000E000E000E000E000E0
00E000E000E000600060006000700030003000180018000C000C00060002000100008000
400A2A7D9E10>40 D<800040002000100018000C000C0006000600030003000380018001
80018001C001C001C001C001C001C001C001C001C001C001C001C0018001800180038003
000300060006000C000C00180010002000400080000A2A7E9E10>I<0006000000060000
000600000006000000060000000600000006000000060000000600000006000000060000
0006000000060000FFFFFFE0FFFFFFE00006000000060000000600000006000000060000
00060000000600000006000000060000000600000006000000060000000600001B1C7E97
20>43 D<03C00C301818300C300C700E60066006E007E007E007E007E007E007E007E007
E007E007E007E007E00760066006700E300C300C18180C3007E0101D7E9B15>48
D<030007003F00C700070007000700070007000700070007000700070007000700070007
00070007000700070007000700070007000F80FFF80D1C7C9B15>I<07C01830201C400C
400EF00FF80FF807F8077007000F000E000E001C001C00380070006000C0018003000601
0C01180110023FFE7FFEFFFE101C7E9B15>I<07E01830201C201C781E780E781E381E00
1C001C00180030006007E00030001C001C000E000F000F700FF80FF80FF80FF00E401C20
1C183007E0101D7E9B15>I<000C00000C00001C00003C00003C00005C0000DC00009C00
011C00031C00021C00041C000C1C00081C00101C00301C00201C00401C00C01C00FFFFC0
001C00001C00001C00001C00001C00001C00001C0001FFC0121C7F9B15>I<300C3FF83F
F03FC020002000200020002000200023E024302818301C200E000E000F000F000F600FF0
0FF00FF00F800E401E401C2038187007C0101D7E9B15>I<00F0030C06040C0E181E301E
300C700070006000E3E0E430E818F00CF00EE006E007E007E007E007E007600760077006
300E300C18180C3003E0101D7E9B15>I<03E00C301008200C2006600660066006700678
0C3E083FB01FE007F007F818FC307E601E600FC007C003C003C003C00360026004300C1C
1007E0101D7E9B15>56 D<03C00C301818300C700C600EE006E006E007E007E007E007E0
076007700F300F18170C2707C700060006000E300C780C78187010203030C00F80101D7E
9B15>I<60F0F0600000000000000000000060F0F06004127C910C>I<7FFFFFC0FFFFFFE0
0000000000000000000000000000000000000000000000000000000000000000FFFFFFE0
7FFFFFC01B0C7E8F20>61 D<FEFEC0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0
C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0FEFE07297C9E0C>91 D<FEFE060606060606060606
06060606060606060606060606060606060606060606060606060606FEFE0729809E0C>
93 D<00038003C4C00C38C01C3880181800381C00381C00381C00381C001818001C3800
0C300013C0001000003000001800001FF8001FFF001FFF803003806001C0C000C0C000C0
C000C06001803003001C0E0007F800121C7F9215>103 D<FC001C001C001C001C001C00
1C001C001C001C001C001C001C001C001C001C001C001C001C001C001C001C001C001C00
1C001C001C001C00FF80091D7F9C0C>108 D<03F0000E1C001806003003007003806001
80E001C0E001C0E001C0E001C0E001C0E001C06001807003803003001806000E1C0003F0
0012127F9115>111 D E /Fp 69[18 8[21 1[23 23 3[18 47[18
21 21 30 21 21 12 16 14 21 21 21 21 32 12 21 12 12 21
21 14 18 21 18 21 18 3[14 1[14 1[30 1[39 30 30 25 23
28 1[23 30 30 37 25 2[14 30 30 23 25 30 28 28 30 5[12
12 21 21 21 21 21 21 21 21 21 21 12 10 14 10 23 21 14
14 14 39[{}75 41.666668 /Times-Roman rf /Fq 69[15 8[17
1[18 18 3[15 47[15 17 17 24 17 17 9 13 11 17 17 17 17
26 9 17 9 9 17 17 11 15 17 15 17 15 3[11 1[11 1[24 24
31 24 24 20 18 22 1[18 24 24 30 20 24 1[11 24 24 18 20
24 22 22 24 31 4[9 9 17 17 17 17 17 17 17 17 17 17 9
8 11 8 2[11 11 40[{}75 33.333332 /Times-Roman rf /Fr
134[15 4[9 13 2[17 1[18 26 9 17 1[9 3[15 17 15 1[17 13[18
6[20 9[22 19[8 46[{}17 33.333332 /Times-BoldItalic rf
/Fs 47[33 30[17 1[18 18 52[17 17 24 17 18 11 13 15 18
18 17 18 28 9 18 1[9 18 17 11 15 18 15 18 17 3[11 1[11
3[33 2[22 18 24 2[26 1[31 22 2[13 26 26 4[22 6[11 7[17
17 17 2[8 11 8 2[11 11 40[{}50 33.333332 /Times-Bold
rf /Ft 138[17 9 13 13 1[17 17 17 24 9 2[9 17 17 9 15
17 15 17 17 13[17 2[20 24 22 28 2[15 11 1[24 20 20 1[22
20 20 18[8 11 45[{}33 33.333332 /Times-Italic rf /Fu
7 122 df<FFFFF0FFFFF014027D881B>0 D<020002000200C218F2783AE00F800F803AE0
F278C2180200020002000D0E7E8E12>3 D<0F00043F80047FC00470F00CC0780CC03C38
800FF88007F08003C016097E8C1B>24 D<007800C0018003000300030003000300030003
00030003000300030006000C00F0000C0006000300030003000300030003000300030003
0003000300018000C000780D217E9812>102 D<F0000C00060003000300030003000300
030003000300030003000300018000C0007800C001800300030003000300030003000300
030003000300030006000C00F0000D217E9812>I<C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0
C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C002217C980A>106 D<060006000600060006
00060006000600FFF0FFF006000600060006000600060006000600060006000600060006
000600060006000600060006000C1D7E9611>121 D E /Fv 52[17
2[17 78[25 2[25 25 14 19 17 1[25 25 25 39 14 25 1[14
25 25 1[22 25 2[22 13[28 33 4[44 1[36 19 3[28 30 1[33
20[12 46[{}29 50.000000 /Times-Roman rf /Fw 134[52 3[52
29 40 34 1[52 52 52 80 1[52 1[29 52 1[34 46 1[46 1[46
13[57 2[57 3[63 7[75 1[69 75 65[{}22 103.666679 /Times-Roman
rf /Fx 198[15 15 15 15 15 15 15 15 15 15 48[{}10 29.166668
/Times-Roman rf end
%%EndProlog
%%BeginSetup
%%Feature: *Resolution 300dpi
TeXDict begin

%%EndSetup
%%Page: 1 1
1 0 bop 1935 -100 a Fx(1)3 78 y Fw(A)25 b(Dynamic)f(Lookup)h(Scheme)g
(for)i(Bursty)e(Access)809 194 y(P)n(atterns)37 294 y
Fv(Funda)12 b(Er)o(gun)295 276 y Fu(\003)354 294 y Fv(Suv)o(o)g(Mittra)
593 276 y Fu(y)650 294 y Fv(S)t(\310)-21 b(ule)o(yman)12
b(Cenk)g(S)-22 b(\313)5 b(ahinalp)1153 276 y Fu(\003)1212
294 y Fv(Jonathan)12 b(Sharp)1518 276 y Fu(\003)1562
294 y Fv(Rakesh)h(K.)g(Sinha)1896 276 y Fu(y)42 429 y
Ft(Abstract)q Fs(\320)s(The)8 b(pr)o(oblem)h(of)g(fast)g(addr)o(ess)g
(lookup)h(is)f(crucial)g(to)f(r)o(out-)0 467 y(ing)h(and)h(thus)g(has)f
(r)o(eceived)f(considerable)h(attention.)14 b(Most)9
b(of)g(the)g(work)0 505 y(in)k(this)g(\256eld)h(has)e(f)o(ocused)h(on)f
(impr)o(oving)h(the)f(speed)h(of)f(individual)i(ac-)0
544 y(cesses)8 b(\261)h(independent)j(fr)o(om)c(the)i(underlying)g
(access)e(pattern.)13 b(Recently)n(,)0 582 y(Gupta)f
Fr(et)f(al.)h Fs([1])f(pr)o(oposed)g(an)h(ef\256cient)g(data)f
(structur)o(e)g(to)g(exploit)h(the)0 620 y(bias)g(in)g(access)f
(pattern.)20 b(This)13 b(technique)g(achieves)d(faster)h(lookups)h(f)o
(or)0 658 y(mor)o(e)6 b(fr)o(equently)h(accessed)e(keys)h(while)h
(bounding)h(the)f(worst)f(case)f(lookup)0 696 y(time;)i(in)h(fact)f(it)
g(is)g(\(near\))g(optimal)g(under)h(constraints)f(on)g(worst)f(case)g
(per)o(-)0 735 y(f)o(ormance.)12 b(However)m(,)6 b(it)k(needs)f(to)g
(be)g(r)o(eb)o(uilt)i(periodically)e(to)g(r)o(e\257ect)g(the)0
773 y(changes)f(in)i(access)d(patterns,)i(which)h(can)e(be)h
(inef\256cient)h(f)o(or)f(b)o(ursty)g(en)o(vi-)0 811
y(r)o(onments.)42 849 y(In)h(this)i(paper)e(we)g(intr)o(oduce)i(a)e
(new)g Fr(dynamic)g Fs(data)g(structur)o(e)h(to)f(ex-)0
887 y(ploit)e(biases)g(in)g(the)g(access)e(pattern,)h(which)i(tend)f
(to)f(change)g(dynamically)n(.)0 926 y(Recent)g(work)h(shows)f(that)h
(ther)o(e)g(ar)o(e)f(many)g(cir)o(cumstances)g(under)i(which)0
964 y(access)g(patterns)h(change)g(quickly)i([2],)f([3].)17
b(Our)11 b(data)f(structur)o(e,)i(which)0 1002 y(we)i(call)f(the)h
Fr(Biased)f(Skip)h(List)h Fs(\(BSL\),)f(has)g(a)g(self-update)g
(mechanism)0 1040 y(which)c(r)o(e\257ects)f(the)h(changes)e(in)i(the)g
(access)e(patterns)h(ef\256ciently)g(and)h(im-)0 1078
y(mediately)n(,)e(without)h(any)f(need)h(f)o(or)e(r)o(eb)o(uilding.)13
b(It)8 b(impr)o(oves)f(thr)o(oughput)0 1116 y(while)14
b(keeping)f(the)h(worst)e(case)g(access)g(time)h(bounded)i(by)e(that)h
(of)f(the)0 1155 y(fastest)7 b(\(unbiased\))j(schemes.)g(W)n(e)d
(demonstrate)h(the)g(practicality)f(of)h(BSL)0 1193 y(by)g(experiments)
g(on)g(data)g(with)h(varying)e(degr)o(ees)h(of)g(b)o(urstiness.)313
1311 y Fp(I)r(.)23 b(I)r Fq(N)r(T)r(R)q(O)r(D)r(U)r(C)r(T)r(I)r(O)r(N)
42 1386 y Fp(A)15 b(fundamental)h(requirement)f(for)g(a)h(router)f(is)h
(to)f(decide,)0 1436 y(upon)9 b(the)g(arri)o(v)o(al)g(of)g(each)i
(packet,)f(on)f(which)g(outgoing)f(line)g(to)0 1485 y(forward)j(the)i
(packet,)g(i.e.,)h(to)e(compute)g(the)h(ne)o(xt)f(hop.)19
b(Gi)o(v)o(en)0 1534 y(the)8 b(e)o(xponential)g(gro)o(wth)f(of)h(the)g
(Internet,)g(Internet)g(traf)o(\256c,)h(and)0 1584 y(the)h(increase)h
(in)f(link)f(speeds,)i(it)f(has)g(become)i(crucial)e(that)g(this)0
1633 y(decision)g(be)h(made)g(at)g(e)o(xtremely)g(high)e(speeds.)15
b(In)10 b(traditional)0 1683 y(IP)h(this)f(decision)g(is)h(based)g(on)f
(the)h(destination)e(address)j(of)e(the)0 1732 y(packet)e(recei)o(v)o
(ed.)14 b(The)9 b(router)e(maintains)h(a)g(set)h(of)f(pre\256x)o(es)h
(and)0 1781 y(the)14 b(task)h(of)f(the)h(router)f(is)g(to)g(quickly)f
(\256nd)i(the)f(longest)g(pre-)0 1831 y(\256x)h(that)f(matches)i(the)f
(destination)e(address)j(of)f(an)g(incoming)0 1880 y(packet)9
b(and)g(forward)f(the)h(packet)g(to)g(the)g(outgoing)e(link)h(associ-)0
1930 y(ated)h(with)e(that)h(pre\256x.)k(The)d(destination)e(addresses)j
(are)f Fo(32)f Fp(bits)0 1979 y(long)g(in)g(the)g(current)h(IPv4)f
(standard)g(and)h(will)f(include)g Fo(128)g Fp(bits)0
2028 y(in)13 b(the)g(ne)o(xt)g(generation)g(IPv6.)21
b(Figure)13 b(I)g(sho)o(ws)g(an)h(e)o(xample)0 2078 y(set)8
b(of)g(pre\256x)o(es)h(and)f(the)f(corresponding)g(ne)o(xt)h(hops.)k
(In)7 b(this)g(e)o(x-)0 2127 y(ample,)i(the)f(destination)e(address)j
Fo(0010)e Fp(matches)i(the)e(\256rst)h(three)0 2177 y(pre\256x)o(es,)j
(b)o(ut)f(the)g(longest)f(matching)g(pre\256x)h(is)g(\252)p
Fo(001)p Fn(\003)p Fp(\272.)j(Ho)o(w-)0 2226 y(e)o(v)o(er)n(,)18
b(the)c(address)i Fo(1010)p Fp(,)g(only)d(matches)k(pre\256x)d(\252)p
Fn(\003)p Fp(\272.)28 b(Other)0 2275 y(types)9 b(of)h(lookup,)e(which)i
(use)g(e)o(xact)g(matches)h(rather)f(than)f(pre-)0 2325
y(\256x)i(matches,)i(are)f(also)f(necessary)i(in)e(IP)g(applications.)k
(In)c(this)0 2374 y(paper)g(we)f(focus)h(mainly)e(on)h(this)g(IP)g
(lookup)f(problem.)42 2427 y(The)20 b(most)g(commonly)f(used)h(data)h
(structure)e(for)g(the)h(IP)29 2509 y Fm(\003)47 2521
y Fq(Dept.)9 b(of)e(EECS,)h(Case)e(W)m(estern)g(Reserve)g(Uni)o
(versity;)g(email:)j Fu(f)p Fq(afe,)e(cenk,)0 2558 y(jps17)p
Fu(g)p Fq(@eecs.cwru.edu)29 2586 y Fm(y)67 2598 y Fq(Bell)22
b(Labs,)j(Murray)20 b(Hill;)29 b(email:)p Fu(f)p Fq(mittra,)d(rks1)p
Fu(g)p Fq(@research.be)o(ll-)0 2634 y(labs.com)29 2674
y(The)8 b(authors)f(are)h(listed)g(alphabetically)n(.)p
1299 389 352 2 v 1298 439 2 50 v 1324 424 a Fp(Pre\256x)p
1447 439 V 50 w(Ne)o(xt)i(hop)p 1650 439 V 1299 440 352
2 v 1298 490 2 50 v 1363 475 a(*)p 1447 490 V 156 w(a)p
1650 490 V 1298 539 V 1353 524 a(0*)p 1447 539 V 144
w(b)p 1650 539 V 1298 588 V 1332 574 a(001*)p 1447 588
V 124 w(c)p 1650 588 V 1298 638 V 1332 623 a(100*)p 1447
638 V 123 w(d)p 1650 638 V 1299 640 352 2 v 1262 712
a Fq(Fig.)f(1.)18 b(Sample)8 b(table)g(of)g(pre\256xes)999
845 y Fp(lookup)k(problem)h(is)g(the)g(binary)g(trie,)h(which)f(is)g(a)
h(tree)g(where)999 894 y(e)o(v)o(ery)9 b(edge)g(has)f(a)h(bit)e(label)h
(and)g(each)h(pre\256x)f(is)g(represented)g(by)999 944
y(a)k(path)e(from)g(the)h(root)f(to)g(a)h(leaf.)k(The)d(internal)d
(nodes)i(in)f(a)i(trie)999 993 y(can)d(ha)o(v)o(e)h(a)e(single)g(child)
f(or)h(two)g(children.)j(The)e(search)h(time)e(in)999
1043 y(a)13 b(trie)e(is)h(proportional)d(to)i(the)h(number)g(of)f(bits)
g(in)h(the)g(address)999 1092 y(space)17 b(and)f(a)g(trie)f(does)h(not)
f(distinguish)e(between)j(high)e(fre-)999 1141 y(quenc)o(y)e
(\(commonly)f(occurring\))g(and)g(lo)o(w)g(frequenc)o(y)h(\(rarely)999
1191 y(occurring\))g(pre\256x)o(es;)j(this)d(may)i(result)e(in)h(poor)f
(performance)999 1240 y(especially)f(for)e(128)h(bit)f(IPv6)h
(addresses.)1041 1290 y(Man)o(y)j(data)h(structures)f(ha)o(v)o(e)h
(been)g(proposed)e(for)h(impro)o(v-)999 1340 y(ing)g(the)g(performance)
h(of)f(tries)g(\([4],)g([5],)h([6],)g([7],)g([8]\).)21
b(The)999 1389 y(majority)14 b(of)h(this)g(work)f(focuses)i(on)f
(intelligent)e(schemes)k(to)999 1439 y(minimize)e(e)o(xpected)g(or)f
(worst)g(case)i(lookup)d(times)i(for)f(indi-)999 1488
y(vidual)e(accesses,)k(independent)11 b(from)h(the)h(underlying)d
(access)999 1537 y(pattern.)17 b(It)11 b(is)g(concei)o(v)o(able,)i(ho)o
(we)o(v)o(er)n(,)g(that)e(one)h(can)g(impro)o(v)o(e)999
1587 y(the)h(throughput)d(of)i(a)i(data)f(structure)f(by)g(tuning)f(it)
h(according)999 1636 y(to)e(lookup)f(biases.)1041 1686
y(A)15 b(recent)h(work)e(by)g(Cheung)h(and)g(McCanne)h([9])e(e)o
(xploits)999 1736 y(the)d(bias)g(in)f(access)k(with)c(a)h(trie-based)g
(approach)g(under)g(space)999 1785 y(limitations.)25
b(Subsequently)m(,)15 b(Gupta)g Fl(et)g(al.)f Fp([1])h(proposed)f(an)
999 1834 y(ef)o(\256cient)19 b(data)g(structure)f(to)g(e)o(xploit)g
(the)g(bias)h(under)f(worst)999 1884 y(case)25 b(performance)e
(constraints.)50 b(The)24 b(main)f(features)g(of)999
1933 y(this)15 b(method)h(are,)i(\(i\))d(the)h(pre\256x)o(es)g(are)h
(treated)f(as)g(interv)o(als)999 1983 y(\(ranges\))h(in)e(the)i
(address)g(space)g Fo([0)22 b(:)h(2)1628 1968 y Fk(32)1662
1983 y Fo(])p Fp(;)c(the)d(number)g(of)999 2032 y(ranges)c(obtained)e
(is)i(sho)o(wn)e(to)h(be)h(at)f(most)h(twice)f(the)g(number)999
2081 y(of)j(pre\256x)o(es,)j(\(ii\))d(access)i(counts)e(are)i
(maintained)e(for)g(ranges)999 2131 y(o)o(v)o(er)e(long)d(periods,)i
(\(iii\))e(a)i(binary)f(search)i(tree)f(is)g(constructed)999
2180 y(on)j(the)g(range)g(set.)24 b(T)m(o)14 b(guarantee)g(worst)f
(case)j(performance,)999 2230 y(the)9 b(depth)f(of)g(the)g(tree)h(is)f
(bounded)g(by)g(a)h(user)g(speci\256ed)g(param-)999 2279
y(eter)n(.)k(The)8 b(tree)h(is)f(then)g(optimized)f(according)h(to)f
(access)k(counts)999 2328 y(under)16 b(this)g(maximum)h(depth)f
(constraint.)30 b(While)16 b(this)g(data)999 2378 y(structure)11
b(achie)o(v)o(es)i(\(near\))e(optimal)g(lookup)e(time)j(for)f(a)g(gi)o
(v)o(en)999 2427 y(set)e(of)g(data,)g(it)f(assumes)i(relati)o(v)o(ely)e
(stable)h(access)i(patterns)d(and)999 2477 y(pre\256x)o(es;)i(i.e.)k
(the)9 b(addresses)i(and)e(access)j(probabilities)7 b(do)i(not)999
2526 y(change)14 b(much)g(o)o(v)o(er)g(time.)22 b(In)13
b(the)h(e)o(v)o(ent)f(of)h(a)f(change)h(in)f(the)999
2575 y(form)j(of)f(an)h(addition/remo)o(v)o(al)e(of)h(an)h(address,)i
(or)e(e)o(v)o(en)g(the)999 2625 y(change)c(of)e(an)h(access)i
(probability)m(,)c(the)i(data)g(structure)f(cannot)999
2674 y(be)f(easily)g(modi\256ed)g(\(this)f(is)g(the)h(case)h(in)f([9])f
(as)i(well\).)i(Instead,)p eop
%%Page: 2 2
2 1 bop 1935 -100 a Fx(2)0 16 y Fp(it)12 b(must)g(be)g(reb)o(uilt)f
(from)i(scratch)g(in)e Fj(O)q Fo(\()p Fj(n)c Fo(log)g