a modular approach to packet classification.ps

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

1964 2186 y(issues)j(concerning)d(the)i(practical)g(implementation)e
(of)i(our)f(approach.)1964 2285 y(\(3\))i(W)-7 b(e)23
b(identify)d(characteristics)h(of)h(realistic)g(\002lter)g(tables)g
(for)f(dif)n(fer)n(-)1964 2384 y(ent)h(classes)i(of)e(router)f(de)n
(vices)h(and)g(de)n(v)o(elop)f(a)i(frame)n(w)o(ork)d(for)i(mod-)1964
2482 y(eling)k(them.)43 b(\(4\))25 b(W)-7 b(e)28 b(pro)o(vide)c
(benchmark)g(results)j(on)f(the)g(practical)1964 2581
y(performance)16 b(of)i(our)h(proposed)d(algorithms)i(based)h(on)f(the)
h(\002lter)h(table)1964 2680 y(models)f(of)h(dif)n(ferent)f(router)g
(de)n(vices.)2047 2783 y(The)d(balance)f(of)h(the)h(paper)e(is)i(or)o
(ganized)d(as)j(follo)n(ws.)23 b(In)16 b(Section)g(II,)1964
2882 y(we)29 b(precisely)g(de\002ne)g(the)g(pack)o(et)g
(classi\002cation)g(problem.)51 b(In)29 b(Sec-)1964 2980
y(tion)21 b(III,)h(we)g(present)g(the)f(details)i(of)e(our)h
(algorithms.)29 b(In)21 b(Section)h(IV,)1964 3079 y(we)17
b(e)o(xamine)e(implementation)f(issues.)25 b(In)16 b(Section)h(V,)g(we)
g(present)f(our)1964 3178 y(e)o(xperimental)24 b(results.)43
b(In)26 b(Section)g(VI,)h(we)g(compare)d(our)i(approach)1964
3277 y(to)20 b(related)g(w)o(ork.)k(Finally)-5 b(,)19
b(we)i(conclude)d(in)j(Section)e(VII.)2243 3464 y(I)t(I)t(.)45
b(T)t Fy(H)t(E)25 b Fx(P)m Fy(A)q(C)t(K)t(E)t(T)g Fx(C)t
Fy(L)t(A)t(S)t(S)t(I)t(FI)t(C)t(A)m(T)t(I)t(O)t(N)g Fx(P)t
Fy(R)q(O)t(B)t(L)t(E)t(M)2047 3607 y Fx(From)f(an)i(algorithmic)d
(perspecti)n(v)o(e,)i(the)g(IP)h(pack)o(et)f(classi\002cation)1964
3706 y(problem)30 b(is)i(simply)g(a)g(concrete)f(instance)g(of)h(the)f
(abstract)h(classi\002-)1964 3805 y(cation)26 b(problem.)43
b(In)26 b(the)h(follo)n(wing,)g(we)g(de\002ne)f(the)h(latter)g(\002rst)
g(and)1964 3904 y(specialize)20 b(it)h(to)f(IP)h(in)f(the)g(ne)o(xt)g
(subsection.)1964 4091 y Fw(A.)41 b(Abstr)o(act)19 b(Classi\002cation)h
(Pr)l(oblem)2047 4234 y Fx(A)25 b Fw(basic)f(\002lter)j
Fv(f)34 b Fx(is)25 b(an)g(ordered)d(pair)j Fu(\()p Fv(b;)14
b(m)p Fu(\))25 b Fx(of)f(binary)f(strings)i(of)1964 4333
y(equal)17 b(length.)24 b(W)-7 b(e)19 b(call)g Fv(b)f
Fx(the)g Fw(pattern)p Fx(,)g(and)g Fv(m)h Fx(the)f Fw(mask)p
Fx(.)24 b Fv(m)19 b Fx(indicates)1964 4432 y(the)k Fw(signi\002cant)g
Fx(bits)h(in)g Fv(b)f Fx(for)g(matching)f(purpose.)33
b(F)o(or)23 b(e)o(xample,)g(the)1964 4531 y(basic)f(\002lter)h(\(1001,)
d(1010\))h(means)h(that)g(the)h(\002rst)g(and)e(third)h(\(counting)1964
4630 y(from)15 b(left)i(to)f(right\))g(bits)h(of)f(\2231001\224)e(are)j
(signi\002cant)f(for)g(matching)f(pur)n(-)1964 4728 y(pose.)30
b(Equi)n(v)n(alently)-5 b(,)20 b(a)i(basic)h(\002lter)f(can)g(be)g
(represented)f(as)h(a)h(ternary)1964 4827 y(string)h(in)h(the)g
(alphabet)e Ft(f)p Fx(0,1,*)p Ft(g)p Fx(.)37 b(Speci\002cally)-5
b(,)24 b(all)i(the)f(insigni\002cant)1964 4926 y(bits)k(in)g
Fv(b)g Fx(are)g(replaced)f(by)h(\223*,)-6 b(\224)31 b(the)e(don')o(t)e
(care)i(bit.)51 b(The)29 b(e)o(xample)1964 5025 y(abo)o(v)o(e)18
b(can)i(be)g(denoted)f(as)i(\2231*0*.)-6 b(\224)2047
5128 y(Three)28 b(special)i(cases)h(of)e(basic)h(\002lters)g(can)g(be)f
(de\002ned.)52 b(A)31 b(basic)1964 5227 y(\002lter)m(,)d(or)f(equi)n(v)
n(alently)d(called)j(a)g Fw(mask-based)h Fx(\002lter)m(,)g
Fv(f)44 b Fu(=)35 b(\()p Fv(b;)14 b(m)p Fu(\))28 b Fx(is)1964
5325 y(called)21 b(\(1\))f Fw(e)n(xact)j Fx(if)f Fv(m)g
Fx(consists)f(of)g(all)h(\2231\224s;)g(\(2\))f Fw(wildcar)m(d)i
Fx(if)f Fv(m)g Fx(con-)1964 5424 y(sists)g(of)f(all)h(\2230\224s;)g
(and)f(\(3\))g Fw(pr)m(e\002x)g Fx(if)g Fv(m)h Fx(is)g(made)f(up)g(of)g
(\2231\224s)g(follo)n(wed)1964 5523 y(by)c(\2230\224s.)24
b(Clearly)-5 b(,)18 b(both)f(e)o(xact)h(and)f(wildcard)g(basic)h
(\002lters)h(are)f(special)1964 5622 y(cases)31 b(of)f(pre\002x)g
(basic)h(\002lters;)36 b(and)30 b(an)o(y)g(basic)h(\002lter)g(can)f(be)
h(repre-)1964 5720 y(sented)d(as)i(a)g(collection)e(of)h(pre\002x)f
(basic)h(\002lters.)52 b(F)o(or)29 b(e)o(xample,)h(the)p
eop
%%Page: 2 2
2 1 bop -260 -46 a Fx(basic)23 b(\002lter)h(\223*0**\224)d(is)j(equi)n
(v)n(alent)d(to)i(the)g(collection)f(of)h(pre\002x)f(basic)-260
52 y(\002lters)f Ft(f)p Fx(\22300**\224,)d(\22310**\224)p
Ft(g)p Fx(.)-177 151 y(A)25 b(binary)e(string)g Fv(t)i
Fw(matc)o(hes)f Fx(a)g(basic)g(\002lter)h Fv(f)39 b Fu(=)30
b(\()p Fv(b;)14 b(m)p Fu(\))24 b Fx(if)h Fv(t)g Fx(and)e
Fv(b)-260 250 y Fx(are)16 b(of)f(equal)h(length)f(and)g(are)h
(identical)f(in)h(all)g(signi\002cant)g(bit)g(positions)-260
349 y(as)22 b(indicated)e(by)g Fv(m)p Fx(.)27 b(F)o(or)21
b(e)o(xample,)e(\2231100\224)g(matches)i(the)g(basic)g(\002lter)-260
448 y(\2231*0*.)-6 b(\224)-177 547 y(A)29 b Fv(k)s Fx(-)p
Fw(dimensional)c(\002lter)30 b Fv(F)41 b Fx(is)28 b(a)h
Fv(k)s Fx(-tuple)e(of)g(basic)h(\002lters.)1623 516 y
Fs(1)1705 547 y Fx(A)g Fv(k)s Fx(-)-260 645 y Fw(dimensional)d
(\002lter)i(table)f(of)g(size)i Fv(N)35 b Fx(is)28 b(an)e(ordered)f
(sequence)g(of)h Fv(N)-260 744 y(k)s Fx(-dimensional)e(\002lters.)44
b(W)-7 b(e)28 b(typically)d(denote)g(such)h(a)h(table)f
Fv(F)12 b(T)38 b Fx(by)-260 843 y(the)29 b(sequence)f
Fv(F)258 855 y Fr(1)296 843 y Fv(;)14 b(F)386 855 y Fr(2)423
843 y Fv(;)g(:)g(:)g(:)g(;)g(F)661 855 y Fq(N)724 843
y Fx(.)52 b(The)29 b(size)g(of)g(a)g(\002lter)h(table)f
Fv(F)12 b(T)40 b Fx(is)-260 942 y(denoted)19 b(by)h Ft(j)p
Fv(F)12 b(T)g Ft(j)p Fx(,)19 b(i.e.,)h Ft(j)p Fv(F)559
954 y Fr(1)597 942 y Fv(;)14 b(F)687 954 y Fr(2)724 942
y Fv(;)g(:)g(:)g(:)g(;)g(F)962 954 y Fq(N)1025 942 y
Ft(j)23 b Fu(=)g Fv(N)9 b Fx(.)-177 1041 y(Let)28 b Fv(t)h
Fx(be)e(a)i Fv(k)s Fx(-tuple)d Fu(\()p Fv(t)522 1053
y Fr(1)560 1041 y Fv(;)14 b(:)g(:)g(:)g(;)g(t)775 1053
y Fq(k)815 1041 y Fu(\))29 b Fx(of)f(binary)e(strings,)j(and)f
Fv(F)40 b Fx(a)28 b Fv(k)s Fx(-)-260 1140 y(dimensional)20
b(\002lter)i(denoted)d(by)i Fu(\()p Fv(f)809 1152 y Fr(1)846
1140 y Fv(;)14 b(:)g(:)g(:)g(;)g(f)1072 1152 y Fq(k)1112
1140 y Fu(\))p Fx(.)29 b(W)-7 b(e)23 b(say)e Fv(t)h Fw(matc)o(hes)f
Fv(F)-260 1238 y Fx(if)k(for)g(all)h Fu(1)31 b Ft(\024)h
Fv(j)37 b Ft(\024)31 b Fv(k)s Fx(,)c Fv(t)509 1250 y
Fq(j)569 1238 y Fx(matches)e Fv(f)908 1250 y Fq(j)943
1238 y Fx(.)40 b(In)24 b(this)i(case,)g Fv(F)38 b Fx(is)26
b(called)f(a)-260 1337 y Fw(matc)o(hing)19 b Fx(\002lter)h(for)g
Fv(t)p Fx(.)-177 1436 y(Gi)n(v)o(en)25 b(a)i Fv(k)s Fx(-dimensional)c
(\002lter)k(table)f Fv(F)12 b(T)37 b Fx(of)26 b(size)g
Fv(N)35 b Fx(denoted)25 b(by)-260 1535 y Fv(F)-207 1547
y Fr(1)-169 1535 y Fv(;)14 b(:)g(:)g(:)f(;)h(F)68 1547
y Fq(N)132 1535 y Fx(,)25 b(a)g(procedure)d(for)i Fw(abstr)o(act)g
(classi\002cation)f Fx(tak)o(es)i(an)f(ar)n(-)-260 1634
y(bitrary)17 b(input)h Fv(k)s Fx(-tuple)f Fv(t)h Fx(and)g(returns)f
(the)h(\002rst)h Fv(F)1185 1646 y Fq(i)1232 1634 y Fx(such)f(that)g
Fv(t)h Fx(matches)-260 1732 y Fv(F)-207 1744 y Fq(i)-150
1732 y Fx(or)28 b Fp(NIL)i Fx(if)e(there)g(is)i(no)e(match.)49
b(W)-7 b(e)29 b(call)g Fv(F)1209 1744 y Fq(i)1266 1732
y Fx(the)f Fw(best)h(matc)o(hing)-260 1831 y(\002lter)23
b Fx(for)c Fv(t)p Fx(.)-177 1930 y(An)i(equi)n(v)n(alent)d(formulation)
g(of)j(the)f(problem)f(is)i(to)g(associate)g(each)-260
2029 y(\002lter)i(with)g(a)g(distinct)g Fw(cost)h Fx(or)f
Fw(priority)p Fx(.)33 b(In)22 b(which)g(case,)i(the)e(classi\002-)-260
2128 y(cation)g(procedure)d(should)i(return)g(the)h(matching)f
(\002lter)h(with)g(the)h(least)-260 2227 y(cost)e(or)f(highest)f
(priority)-5 b(.)-177 2326 y(A)31 b(simple)f(e)o(xtension)f(to)i(the)f
(classi\002cation)h(problem)d(is)k(to)e(asso-)-260 2424
y(ciate)22 b(each)f(\002lter)h Fv(F)325 2436 y Fq(i)375
2424 y Fx(with)f(a)h(weight)f Fv(W)929 2436 y Fq(i)957
2424 y Fx(.)30 b(The)21 b(weight)g(represents)f(the)-260
2523 y(relati)n(v)o(e)30 b(match)g(frequenc)o(y)e(of)i(a)h(particular)f
(\002lter)m(,)j(and)d(is)h(typically)-260 2622 y(deri)n(v)o(ed)24
b(from)g(the)h(distrib)n(ution)f(of)h(the)h(input)e(tuple)h
Fv(t)h Fx(or)f(\002lter)h(usage)-260 2721 y(statistics.)37
b(More)23 b(precisely)-5 b(,)23 b(let)i Fv(t)f Fx(be)f(dra)o(wn)g(from)
g(some)g(\002x)o(ed)g(input)-260 2820 y(distrib)n(ution)c(from)g(which)
h(the)g Fv(W)748 2832 y Fq(i)776 2820 y Fx(')-5 b(s)21
b(are)f(deri)n(v)o(ed.)k(Then)16 2986 y Fv(pr)r(ob)p
Fu(\()p Fv(F)258 2998 y Fq(i)307 2986 y Fx(is)d(the)g(best)f(matching)f
(\002lter)h(for)g Fv(t)p Fu(\))p 12 3023 1339 4 v 12
3099 a Fv(pr)r(ob)p Fu(\()p Fv(F)254 3111 y Fq(j)311
3099 y Fx(is)h(the)f(best)h(matching)d(\002lter)j(for)f
Fv(t)p Fu(\))1384 3042 y Ft(\031)1485 2986 y Fv(W)1563
2998 y Fq(i)p 1481 3023 114 4 v 1481 3099 a Fv(W)1559
3111 y Fq(j)-177 3271 y Fx(Kno)n(wledge)h(of)i(the)g(weights)f(may)h
(help)f(in)h(constructing)e(more)h(ef-)-260 3370 y(\002cient)34
b(classi\002cation)g(procedures.)64 b(W)-7 b(e)35 b(call)g(this)f(e)o
(xtended)e(prob-)-260 3469 y(lem)23 b(the)f Fw(weighted)g(abstr)o(act)g
(classi\002cation)g(pr)l(oblem)p Fx(.)31 b(In)22 b(the)h(sequel,)-260
3568 y(to)g(a)n(v)n(oid)f(repeated)g(de\002nitions,)g(the)g
(classi\002cation)h(problem)e(without)-260 3666 y(weights)j(is)i
(treated)d(as)i(the)g(weighted)e(classi\002cation)h(problem)f(where)
-260 3765 y(all)e Fv(W)-78 3777 y Fq(i)-50 3765 y Fx(')-5
b(s)21 b(are)f(1.)-260 3939 y Fw(F)l(ilter)h(Co)o(vering)-177
4076 y Fx(Gi)n(v)o(en)40 b(a)h(\002lter)g(table)f Fv(F)12
b(T)g Fx(,)45 b(not)40 b(all)i(\002lters)f(can)f(potentially)f(be)-260
4175 y(matched.)51 b(F)o(or)29 b(e)o(xample,)h(consider)e(the)h
(1-dimensional)e(\002lter)i(table)-260 4273 y(1*,)36
b(00,)h(11,)f(01,)g(0*,)g(both)d(the)g(\002lters)i(\22311\224)e(and)g
(\2230*\224)f(will)j(ne)n(v)o(er)-260 4372 y(be)24 b(returned)e(as)j(a)
f(match)f(as)i(an)o(y)e(input)g(matching)f(them)i(w)o(ould)f(ha)n(v)o
(e)-260 4471 y(matched)e(earlier)g(\002lters,)h(\2231*\224)f(for)g(the)
g(former)f(and)h(\22300\224)g(or)g(\22301\224)g(for)-260
4570 y(the)f(latter)-5 b(.)-177 4669 y(W)e(e)23 b(can)f(formalize)e
(this)j(with)f(a)g(notion)f(called)g Fw(co)o(vering)p
Fx(.)30 b(A)22 b(set)h(of)-260 4767 y(\002lters)h Fv(S)35
b Fu(=)29 b Ft(f)p Fv(F)228 4779 y Fq(i)255 4767 y Ft(g)24
b Fx(is)g(said)g(to)g Fw(co)o(ver)i Fx(a)e(\002lter)g
Fv(F)36 b Fx(if)24 b(for)f(all)h(input)f Fv(t)p Fx(,)i(if)f
Fv(t)-260 4866 y Fx(matches)17 b Fv(F)12 b Fx(,)19 b(then)e
Fv(t)h Fx(also)g(matches)f(some)g(\002lter)h Fv(F)1207
4878 y Fq(i)1253 4866 y Fx(in)g Fv(S)5 b Fx(.)24 b(Gi)n(v)o(en)17
b(a)h(\002lter)-260 4965 y(table)23 b Fv(F)12 b(T)g Fx(,)22
b(a)i(subsequence)c(of)j(\002lters)g Fv(F)955 4977 y
Fq(i)978 4985 y Fo(1)1016 4965 y Fv(;)14 b(:)g(:)g(:)f(;)h(F)1253
4977 y Fq(i)1276 4985 y Fn(m)1360 4965 y Fx(is)23 b(said)g(to)g
Fw(co)o(ver)-260 5064 y Fv(F)-207 5076 y Fq(`)-154 5064
y Fx(if)e Ft(f)p Fv(F)13 5076 y Fq(i)36 5084 y Fo(1)73
5064 y Fv(;)14 b(:)g(:)g(:)f(;)h(F)310 5076 y Fq(i)333
5084 y Fn(m)393 5064 y Ft(g)21 b Fx(co)o(v)o(ers)e Fv(F)744
5076 y Fq(`)797 5064 y Fx(and)g Fv(i)966 5076 y Fq(m)1052
5064 y Ft(\024)k Fv(`)p Fx(.)-177 5163 y(Using)28 b(the)f(co)o(v)o
(ering)f(relation,)i(we)g(can)f(di)n(vide)g(a)h(\002lter)g(table)g
Fv(F)12 b(T)-260 5262 y Fx(into)29 b(tw)o(o)g(sub-tables)f
Fv(T)41 b Fx(and)28 b Fv(T)718 5231 y Fm(0)770 5262 y
Fx(such)h(that)g(\(1\))f(\002lters)h(in)g Fv(T)41 b Fx(and)28
b Fv(T)1844 5231 y Fm(0)-260 5360 y Fx(are)c(subsequences)f(of)h
Fv(F)12 b(T)g Fx(;)27 b(\(2\))c Fv(T)36 b Fx(and)24 b
Fv(T)1025 5330 y Fm(0)1072 5360 y Fx(form)g(a)h(partition)e(of)h
Fv(F)12 b(T)g Fx(,)-260 5459 y(i.e.,)30 b(all)f(\002lters)h(in)e
Fv(F)12 b(T)40 b Fx(are)28 b(in)h(e)o(xactly)f(one)f(of)i
Fv(T)40 b Fx(or)28 b Fv(T)1458 5429 y Fm(0)1480 5459
y Fx(;)33 b(\(3\))28 b Ft(8)p Fv(F)49 b Ft(2)-260 5558
y Fv(T)-199 5528 y Fm(0)-177 5558 y Fv(;)14 b Ft(9)p
Fv(F)-41 5570 y Fq(i)-18 5578 y Fo(1)20 5558 y Fv(;)g(:)g(:)g(:)g(;)g
(F)258 5570 y Fq(i)281 5578 y Fn(m)364 5558 y Ft(2)23
b Fv(T)30 b Fx(such)17 b(that)h Fv(F)887 5570 y Fq(i)910
5578 y Fo(1)948 5558 y Fv(;)c(:)g(:)g(:)f(;)h(F)1185
5570 y Fq(i)1208 5578 y Fn(m)1287 5558 y Fx(co)o(v)o(er)i
Fv(F)c Fx(;)19 b(\(4\))f Fv(T)1771 5528 y Fm(0)1811 5558
y Fx(is)-207 5697 y Fl(1)-172 5720 y Fy(In)f(other)h(w)o(ords,)f(a)g
(basic)h(\002lter)g(is)f(equi)n(v)n(alent)k(to)c(a)g(1-dimensional)j
(\002lter)l(.)1964 -46 y Fx(a)k(maximal)f(subsequence)g(satisfying)g
(\(1\)\226\(3\).)34 b(W)-7 b(e)26 b(can)e(easily)g(sho)n(w)1964
52 y(that)i(such)h(a)g(di)n(vision)e(produces)g(a)i(unique)e(pair)h
Fv(T)39 b Fx(and)26 b Fv(T)3747 22 y Fm(0)3769 52 y Fx(.)45
b(W)-7 b(e)27 b(call)1964 151 y(the)20 b(process)h(of)f(obtaining)f
Fv(T)32 b Fx(and)20 b Fv(T)3065 121 y Fm(0)3109 151 y
Fw(r)m(eduction)p Fx(,)f(and)h(denote)g Fu(\()p Fv(T)7
b(;)14 b(T)4036 121 y Fm(0)4058 151 y Fu(\))1964 250
y Fx(as)20 b(the)h Fw(r)m(e