a modular approach to packet classification.ps

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

1AE0D90003018090380FFC004BC713E00201ED07804EC7FC6E6C140E606F5C705B606F6C
485A4D5A031F91C8FCEEE0065F6F6C5A5F03075B705A16F96FB45A94C9FC6F5AA36F7EA3
4B7FED037F9238063FC0150E4B6C7E1538ED700F03E07F15C04A486C7EEC030002061303
4A805C4A6D7E14704A1300494880495A49C86C7E130E011E153F017E4B7ED803FF4B7E00
7F01E0011FEBFFC0B5FC6144397EB845>I<1578EC01FEEC07C6EC0F861507EC1E03143E
147C1507ECF806A2EB01F00103130EECE00C1307A2ECC01C010F1318153890381F803015
70156090383F00E015C01401017F1380EB7E03EC07001406EBFE0E495A5C143000011370
495AEBF9C0EBFB8001FFC7FC5B5B485AA25BA4485A120F121DEA39F0127100E1140C0080
143C0000147015E090387801C0EC078090383C1E00EB1FF8EB07E0203C7FBA23>96
D<133FEA1FFFA3C67E137EA313FE5BA312015BA312035BA31207EBE0FCEBE3FF9038E707
C0390FFE03E09038F801F001F013F8EBE000485A15FC5BA2123F90C7FCA214015A127EA2
140312FE4814F8A2140715F05AEC0FE0A215C0EC1F80143F00781400007C137E5C383C01
F86C485A380F07C06CB4C7FCEA01FC1E3B7CB924>98 D<16F8ED03FEED0F8792381F0F80
ED3E3F167F157CA215FC1700161C4A48C7FCA414035DA414075DA20107B512F0A3902600
0FE0C7FC5DA4141F5DA4143F92C8FCA45C147EA514FE5CA413015CA4495AA45C1307A25C
121E123F387F8F80A200FF90C9FC131E12FEEA7C3CEA7878EA1FF0EA07C0294C7CBA29>
102 D<EB03F0EA01FFA3EA00075CA3130F5CA3131F5CA3133F91C9FCA35B90387E03F8EC
0FFF91383C0F809039FEF007C0D9FDC07FEBFF80EC0003485A5BA249130712035BA2150F
00075D5BA2151F000F5D5B153F93C7FC121F4990387F0180157EEDFE03003F02FC130090
C7FC5EEDF80648150E007E150C161C5E00FEEC787048EC3FE00038EC0F80293B7CB930>
104 D<14E0EB03F8A21307A314F0EB01C090C7FCAB13F8EA03FEEA070F000E1380121C12
1812381230EA701F1260133F00E0130012C05BEA007EA213FE5B1201A25B12035BA20007
131813E01438000F133013C01470EB806014E014C01381EB838038078700EA03FEEA00F8
15397EB71D>I<150FED3F80A2157FA31600151C92C7FCABEC0F80EC3FE0ECF0F0903801
C0F849487E14005B130E130C131CEB1801133801305BA2EB0003A25DA21407A25DA2140F
A25DA2141FA25DA2143FA292C7FCA25CA2147EA214FEA25CA21301001E5B123F387F83F0
A238FF87E0495A00FE5BD87C1FC8FCEA707EEA3FF8EA0FC0214981B722>I<EB03F0EA01
FFA3EA00075CA3130F5CA3131F5CA3133F91C8FCA35B017EEB07C0ED1FF0ED783801FEEB
E0F89039FC01C1FCEC0383EC07070001130ED9F81C13F891383803F091387001E0000349
C7FCEBF1C0EBF38001F7C8FCEA07FEA2EBFFE0EBE7F8380FE0FEEBC07F6E7E141F001F80
D9800F1330A21670003F011F136001001380A216E04815C0007E1481020F1380158300FE
903807870048EB03FE0038EB00F8263B7CB92B>I<D803E0017F14FE3D07F801FFE003FF
C03D0E3C0781F00F03E03D1C3E1E00F83C01F026383F38D9FC707F00304914E04A90387D
C000007049EB7F8000604991C7FCA200E090C700FE1301485A017E5CA200000201140301
FE5F495CA203031407000160495C180F03075D1203494A011F13601980030F023F13E000
07F000C0495C1901031F023E1380000F1803494A150061033F150E001FEF1E1C4991C7EA
0FF80007C7000EEC03E043267EA449>109 D<D803E0137F3A07F801FFE03A0E3C0781F0
3A1C3E1E00F826383F387F00305B4A137C00705B00605BA200E090C712FC485A137EA200
00140101FE5C5BA2150300015D5B15075E120349010F133016C0031F13700007ED80605B
17E0EE00C0000F15014915801603EE0700001FEC0F0E49EB07FC0007C7EA01F02C267EA4
32>I<EC1FC0ECFFF8903807E07E90380F801F90393F000F80017E14C0491307484814E0
485A4848EB03F0120F5B121F48481307A2127F90C7FCA2150F5A4815E0A2151F16C0A248
EC3F8016005D157E007E5C4A5A003E495A003F495A6C495A6C6C48C7FC3807E07E3801FF
F038003F8024267DA428>I<90390F8003F090391FE00FFC903939F03C1F903A70F8700F
80903AE0FDE007C09038C0FF80030013E00001491303018015F05CEA038113015CA2D800
031407A25CA20107140FA24A14E0A2010F141F17C05CEE3F80131FEE7F004A137E16FE01
3F5C6E485A4B5A6E485A90397F700F80DA383FC7FC90387E1FFCEC07E001FEC9FCA25BA2
1201A25BA21203A25B1207B512C0A32C3583A42A>I<3903E001F83907F807FE390E3C1E
07391C3E381F3A183F703F800038EBE07F0030EBC0FF00705B00601500EC007E153CD8E0
7F90C7FCEAC07EA2120013FE5BA312015BA312035BA312075BA3120F5BA3121F5B0007C9
FC21267EA425>114 D<14FF010313C090380F80F090383E00380178131C153C4913FC00
01130113E0A33903F000F06D13007F3801FFE014FC14FF6C14806D13C0011F13E0130390
38003FF014071403001E1301127FA24814E0A348EB03C012F800E0EB07800070EB0F006C
133E001E13F83807FFE0000190C7FC1E267CA427>I<EB01C0497E1307A4130F5CA3131F
5CA3133F91C7FC007FB51280A2B6FCD8007EC7FCA313FE5BA312015BA312035BA312075B
A3120FEBC006A2140E001F130CEB801C141814385C146014E0380F81C038078780D803FE
C7FCEA00F819357EB31E>I<903907E001F090391FF807FC9039783E0E0F9039E01F1C1F
D801C09038383F803A03800FF07F0100EBE0FF5A000E4A1300000C157E021F133C001C4A
C7FC1218A2C7123FA292C8FCA25CA2147EA214FEA24A130CA20101141C001E1518003F5B
D87F81143801835C00FF1560010714E03AFE0E7C01C0D87C1C495A2778383E0FC7FC391F
F00FFC3907C003F029267EA42F>120 D<13F8D803FE1470D8070F14F8000EEB8001121C
121800381403003015F0EA701F1260013F130700E0010013E012C05BD8007E130F16C013
FE5B151F000115805BA2153F000315005BA25D157EA315FE5D1401000113033800F80790
387C1FF8EB3FF9EB0FE1EB00035DA2000E1307D83F805B007F495AA24A5A92C7FCEB003E
007C5B00705B6C485A381E07C06CB4C8FCEA01FC25367EA429>I
E /Fw 133[32 37 37 55 37 42 23 32 32 42 42 42 42 60 23
37 1[23 42 42 23 37 42 37 42 42 12[46 42 51 1[51 1[55
4[28 1[60 51 1[60 55 51 51 18[21 28 2[42 39[42 2[{
 TeXBase1Encoding ReEncodeFont }41 83.333336 /Times-Italic
rf /Fx 104[83 42 1[37 37 24[37 42 42 60 42 42 23 32 28
42 42 42 42 65 23 42 23 23 42 42 28 37 42 37 42 37 3[28
1[28 3[78 60 60 51 46 55 1[46 60 60 74 51 60 1[28 60
60 46 51 60 55 55 60 5[23 23 42 42 42 42 42 42 42 42
42 42 23 21 28 21 1[42 28 28 28 1[69 33[46 46 2[{
 TeXBase1Encoding ReEncodeFont }76 83.333336 /Times-Roman
rf /Fy 105[33 1[29 29 24[29 33 33 48 33 33 18 26 22 33
33 33 33 52 18 33 18 18 33 33 22 29 33 29 33 29 3[22
1[22 41 48 48 63 48 48 41 37 44 1[37 48 48 59 41 48 26
22 48 48 37 41 48 44 44 48 3[37 1[18 18 33 33 33 33 33
33 33 33 33 33 1[17 22 17 1[33 22 22 22 36[37 2[{
 TeXBase1Encoding ReEncodeFont }77 66.666664 /Times-Roman
rf /Fz 104[66 29[33 33 48 33 37 22 26 29 37 37 33 37
55 18 37 1[18 37 33 22 29 37 29 37 33 10[48 1[44 37 1[52
41 4[52 1[26 6[44 9[33 6[33 2[17 22 17 2[22 22 37[37
2[{ TeXBase1Encoding ReEncodeFont }41 66.666664 /Times-Bold
rf /FA 134[29 29 44 1[33 18 26 26 1[33 33 33 48 18 29
1[18 33 33 18 29 33 29 33 33 9[55 2[37 33 2[41 1[44 55
3[22 48 48 41 41 1[44 1[41 6[22 12[22 2[33 42[{
 TeXBase1Encoding ReEncodeFont }38 66.666664 /Times-Italic
rf /FB 136[72 1[50 28 39 33 2[50 50 78 28 2[28 50 50
1[44 1[44 50 44 7[72 1[94 2[61 7[61 8[66 66 1[92 17[25
33 25 44[{ TeXBase1Encoding ReEncodeFont }26 100.000000
/Times-Roman rf /FC 138[103 57 80 69 1[103 103 103 161
57 103 1[57 103 103 1[92 103 92 1[92 14[138 1[115 2[184
9[138 1[149 6[57 55[115 2[{ TeXBase1Encoding ReEncodeFont }24
207.333359 /Times-Roman rf end
%%EndProlog
%%BeginSetup
%%Feature: *Resolution 600dpi
TeXDict begin
%%PaperSize: Letter

%%EndSetup
%%Page: 1 1
1 0 bop 4 78 a FC(A)52 b(Modular)g(Approach)g(to)h(P)m(ack)n(et)e
(Classi\002cation:)940 310 y(Algorithms)i(and)f(Results)1549
509 y FB(Thomas)24 b(Y)-13 b(.C.)25 b(W)-8 b(oo)1127
626 y(Bell)25 b(Laboratories,)g(Lucent)f(T)-7 b(echnologies)1336
742 y(w)o([e-mail])-177 992 y FA(Abstr)o(act)q
Fz(\227)10 b(The)25 b(ability)e(to)g(classify)g(pack)o(ets)h(according)
g(to)e(pr)o(e-de\002ned)i(rules)-260 1069 y(is)18 b(critical)j(to)d(pr)
o(o)o(viding)h(many)f(sophisticated)i(v)o(alue-added)g(ser)o(vices,)g
(such)e(as)f(se-)-260 1145 y(curity)l(,)23 b(QoS,)c(load)i(balancing,)i
(traf\002c)e(accounting,)i(etc.)32 b(V)-6 b(arious)21
b(appr)o(oaches)g(to)-260 1221 y(pack)o(et)e(classi\002cation)i(ha)n(v)
o(e)e(been)g(studied)f(in)h(the)f(literatur)o(e)j(with)d(accompanying)
-260 1298 y(theor)o(etical)j(bounds.)j(Practical)d(studies)e(with)f(r)o
(esults)h(applying)g(to)f(lar)o(ge)j(number)-260 1374
y(of)c(\002lters)h(\(fr)o(om)g(8K)e(to)h(1)g(million\))i(ar)o(e)f(rar)o
(e.)-177 1458 y(In)d(this)g(paper)-6 b(,)16 b(we)g(tak)o(e)g(a)f
(practical)j(appr)o(oach)e(to)g(the)f(pr)o(oblem)i(of)e(pack)o(et)i
(clas-)-260 1535 y(si\002cation.)45 b(Speci\002cally)l(,)29
b(we)c(pr)o(opose)g(and)f(study)h(a)f(no)o(v)o(el)i(appr)o(oach)g(to)e
(pack)o(et)-260 1611 y(classi\002cation)32 b(which)e(combines)h
(heuristic)g(tr)o(ee)g(sear)o(ch)f(with)g(the)f(use)h(of)f(\002lter)
-260 1687 y(b)o(uck)o(ets.)50 b(Besides)28 b(high)f(perf)n(ormance)j
(and)c(r)o(easonable)i(storage)g(r)o(equir)o(ement,)-260
1764 y(our)23 b(algorithm)i(is)e(unique)g(in)g(the)g(sense)g(that)g(it)
g(can)h(adapt)e(to)h(the)g(input)g(pack)o(et)-260 1840
y(distrib)o(ution)18 b(by)f(taking)h(into)f(account)h(the)f(r)o(elati)o
(v)o(e)j(\002lter)e(usage.)-177 1924 y(T)-6 b(o)21 b(e)o(v)o(aluate)h
(our)f(algorithms,)i(we)e(ha)n(v)o(e)h(de)o(v)o(eloped)g(r)o(ealistic)i
(models)d(of)g(lar)o(ge)-260 2001 y(scale)j(\002lter)g(tables,)g(and)f
(used)f(them)h(to)g(dri)o(v)o(e)i(extensi)o(v)o(e)g(experimentation.)41
b(The)-260 2077 y(r)o(esults)22 b(demonstrate)h(practicality)h(of)d
(our)g(algorithms)i(f)n(or)f(e)o(v)o(en)g(up)f(to)g(1)f(million)-260
2154 y(\002lters.)479 2392 y Fx(I)t(.)46 b(I)t Fy(N)t(T)t(R)q(O)t(D)t
(U)t(C)t(T)t(I)t(O)t(N)-177 2543 y Fx(Multi-dimensional)26
b(pack)o(et)i(classi\002cation)g(with)h(a)g(lar)o(ge)e(number)-260
2642 y(of)f(\002lter)h(rules)g(is)h(a)f(pro)o(v)n(ably)d(hard)h
(problem)g([4],)j([7],)f([8].)43 b(Speci\002-)-260 2741
y(cally)-5 b(,)27 b(pre)n(vious)e(w)o(ork)h(has)g(cast)h(it)g(in)g
(terms)f(of)g(the)g(range)g(matching)-260 2840 y(problem)19
b(in)h(computational)e(geometry)g([3],)i(where)f(there)h(are)g(v)n
(arious)-260 2939 y(kno)n(wn)f(algorithms)g(and)g(theoretical)h
(results.)-177 3045 y(Most)29 b(of)f(these)h(studies,)i(ho)n(we)n(v)o
(er)m(,)d(focus)g(on)h(w)o(orst-case)f(perfor)n(-)-260
3144 y(mance,)c(and)f(does)g(not)h(tak)o(e)g(into)f(account)f(actual)i
(\002lter)g(usage)f(statis-)-260 3243 y(tics,)g(nor)f(the)g(types)g(of)
f(commonly)f(occurring)g(\002lter)i(patterns.)30 b(More-)-260
3342 y(o)o(v)o(er)m(,)c(the)o(y)g(pro)o(vide)f(sparse)i(e)o
(xperimental)d(results.)45 b(In)26 b(practice,)h(the)-260
3440 y(asymptotic)32 b(comple)o(xity)g(does)h(not)g(accurately)f(tell)i
(ho)n(w)f(the)g(algo-)-260 3539 y(rithms)20 b(scale)h(to)f(lar)o(ge)f
(number)g(\(e.g.,)g(from)g(8K)h(to)h(1M\))e(of)h(\002lters.)-177
3646 y(In)30 b(this)g(paper)m(,)h(we)g(tak)o(e)f(a)g(more)f(pragmatic)g
(approach.)52 b(Our)29 b(in-)-260 3745 y(terest)g(is)g(not)f(as)h(much)
e(in)i(analytical)e(results,)k(b)n(ut)d(in)g(e)o(xploring)e(the)-260
3843 y(practical)j(limits)h(of)g(pack)o(et)f(classi\002cation)g(and)g
(understanding)e(per)n(-)-260 3942 y(formance)k(through)g(empirical)h
(e)o(xperimentations.)60 b(Our)33 b(algorithm)-260 4041
y(is)e(moti)n(v)n(ated)e(by)g(intuiti)n(v)o(e)h(observ)n(ation)d(on)j
(the)g(classi\002cation)g(pro-)-260 4140 y(cess,)c(and)e(is)h(based)e
(on)h(an)g(ef)n(\002cient)g(di)n(vide-and-conquer)19
b(approach.)-260 4239 y(Speci\002cally)-5 b(,)30 b(we)f(break)e(up)h
(the)h(classi\002cation)g(procedure)d(into)i(tw)o(o)-260
4337 y(main)i(steps.)56 b(In)30 b(the)h(\002rst)g(step,)i(our)c
(algorithm)g(tries)i(to)f(eliminates)-260 4436 y(as)e(man)o(y)e
(\002lters)i(as)g(possible)f(by)f(e)o(xamining)f(speci\002c)j(bit)f
(positions.)-260 4535 y(Ho)n(we)n(v)o(er)m(,)g(instead)g(of)g
(eliminating)f(all)i(b)n(ut)f(one)g(\002lter)m(,)i(the)e(\002rst)h
(step)-260 4634 y(terminates)i(when)h(the)g(set)g(of)g(remaining)e
(\002lters)i(is)h(less)g(than)e(some)-260 4733 y(pre-speci\002ed)19
b(maximum.)24 b(W)-7 b(e)21 b(call)g(this)g(set)g(of)f(\002lters)h(a)g
Fw(\002lter)f(b)n(uc)n(k)o(et)p Fx(.)-260 4831 y(This)25
b(early)f(termination)e(a)n(v)n(oids)j(the)f(e)o(xplosion)f(that)h(is)i
(often)d(the)i(re-)-260 4930 y(sult)k(of)f(trying)f(to)h(completely)f
(dif)n(ferentiate)f(between)h(a)i(fe)n(w)f(\223simi-)-260
5029 y(lar\224)e(\002lters.)44 b(In)26 b(the)g(second)f(step,)j(the)e
(\002lter)g(b)n(uck)o(et)g(is)h(processed)e(to)-260 5128
y(\002nd)k(a)h(match.)52 b(Because)30 b(of)f(the)h(limited)f(size)h(of)
f(a)h(\002lter)g(b)n(uck)o(et,)h(a)-260 5227 y(completely)21
b(dif)n(ferent)f(procedure)f(\(e.g.,)j(\(hardw)o(are-based\))c(linear)k
(or)-260 5325 y(associati)n(v)o(e)k(search\))g(can)g(be)h(used.)43
b(In)27 b(essence,)h(our)d(algorithm)g(is)j(a)-260 5424
y(modular)21 b(composition)f(of)i(tw)o(o)h(procedures:)k(the)c(\002rst)
g(to)f(decompose)-260 5523 y(lar)o(ge)31 b(\002lter)g(table)h(into)f
(small)h(\002lter)f(b)n(uck)o(ets)g(of)g(a)h(\002x)o(ed)f(maximum)-260
5622 y(size)24 b(\(from)e(8)h(to)h(128\),)e(and)h(the)g(second)g(to)g
(process)g(\002lter)h(b)n(uck)o(ets)f(of)-260 5720 y(limited)d(size)h
(to)f(\002nd)g(a)h(match.)2047 992 y(Our)h(algorithm)f(is)i(also)g
(unique)f(in)g(the)h(sense)g(that)g(it)g(can)f(tak)o(e)h(into)1964
1091 y(account)18 b(the)h(relati)n(v)o(e)f(usage)h(of)g(the)h(indi)n
(vidual)d(\002lters)j(in)f(a)h(\002lter)g(table)1964
1190 y(to)i(b)n(uild)f(a)i(more)e(optimal)h(search)f(data)h(structure.)
30 b(This)22 b(is)h(especially)1964 1289 y(important)18
b(as)k(usage)e(of)g(indi)n(vidual)e(\002lters)k(tends)e(to)g(be)h
(highly)e(unbal-)1964 1387 y(anced.)2047 1490 y(Our)36
b(algorithm)f(is)j(amenable)e(to)h(implementation)d(in)j(softw)o(are,)
1964 1589 y(hardw)o(are,)30 b(or)f(a)h(combination)e(of)h(the)h(tw)o
(o.)53 b(W)-7 b(e)31 b(e)o(xamine)e(some)g(of)1964 1688
y(the)20 b(implementation)e(issues)j(in)f(this)h(paper)-5
b(.)2047 1791 y(In)20 b(a)g(nutshell,)g(our)g(contrib)n(utions)e(are:)
26 b(\(1\))19 b(W)-7 b(e)22 b(propose)c(and)i(study)1964
1890 y(a)k(no)o(v)o(el)e(heuristic)h(approach)f(to)i(pack)o(et)f
(classi\002cation)h(that)f(pro)o(vides)1964 1988 y(good)13
b(a)n(v)o(erage)h(case)i(performance,)d(uses)j(reasonable)e(storage,)h
(and)g(can)1964 2087 y(adapt)k(to)h(the)g(usage)f(of)g(indi)n(vidual)f
(\002lters.)26 b(\(2\))19 b(W)-7 b(e)21 b(e)o(xamine)d(dif)n(ferent)