packet classification using tuple space search_sigcomm99.ps

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

(general)i(tuple)g(space)f(searc)o(h)g(prob-)0 2141 y(lem,)12
b(and)f(describ)q(e)i(an)e(optimal)i(algorithm,)g(called)g
Fm(R)n(e)n(ctangle)0 2183 y(Se)n(ar)n(ch)p Fn(,)e(for)i(t)o(w)o
(o-dimensional)i(\014lters.)p 0 2213 377 2 v 42 2234
a Fk(\003)60 2247 y Fj(Researc)o(h)10 b(supp)q(orted)i(in)g(part)f(b)o
(y)h(NSF)f(Gran)o(t)g(NCR-9628145.)44 2271 y Fk(y)60
2284 y Fj(Researc)o(h)f(supp)q(orted)i(in)g(part)f(b)o(y)h(NSF)f(Gran)o
(t)g(9813723)44 2308 y Fk(z)60 2320 y Fj(Researc)o(h)f(supp)q(orted)i
(in)g(part)f(b)o(y)h(NSF)f(Gran)o(t)g(NCR)g(9813723.)1040
776 y Fo(1)40 b(Intro)q(duction)1040 854 y Fn(As)13 b(the)h(In)o
(ternet)g(b)q(egins)i(to)d(b)q(e)h(used)h(for)e(commercial)j(appli-)
1040 896 y(cations,)i(service)f(pro)o(viders)h(w)o(ould)g(lik)o(e)f
(routers)g(to)f(pro)o(vide)1040 937 y(\\service)d(di\013eren)o(tiation)
q(".)19 b(T)m(raditional)c(routers)d(do)g(not)h(pro-)1040
979 y(vide)j(service)f(di\013eren)o(tiati)q(on)j(b)q(ecause)d(they)g
(treat)g(all)h(tra\016c)1040 1020 y(going)k(to)e(the)g(same)h(In)o
(ternet)g(destination)i(address)e(iden)o(ti-)1040 1062
y(cally)m(.)e(Routers)12 b(with)f(a)f(pac)o(k)o(et)h(classi\014cati)q
(on)i([8,)d(13)q(])g(capabil-)1040 1103 y(it)o(y)m(,)h(ho)o(w)o(ev)o
(er,)g(can)g(distinguis)q(h)i(tra\016c)e(based)h(on)f(destination,)1040
1145 y(source,)16 b(and)g(application)j(t)o(yp)q(e.)24
b(Suc)o(h)16 b(classi\014cation)i(allo)o(ws)1040 1186
y(v)n(arious)f(forms)f(of)g(service)h(di\013eren)o(tiation)q(:)25
b(blo)q(c)o(king)19 b(tra\016c)1040 1228 y(sen)o(t)d(b)o(y)f(insecure)j
(sites)e(\(\014rew)o(alls\),)h(preferen)o(tial)h(treatmen)o(t)1040
1269 y(for)f(premium)h(tra\016c)f(\(resource)h(reserv)n(ation\),)i(and)
d(routing)1040 1311 y(based)d(on)f(tra\016c)g(t)o(yp)q(e)g(and)h
(source)g(\(QoS)f(routing\).)1096 1352 y(While)18 b(more)e(general)h
(applicatio)q(ns)i(lik)o(e)e(resource)g(reser-)1040 1394
y(v)n(ation)f([2]\))f(and)h(QoS)g(routing)g(are)g(lik)o(ely)i(to)d(b)q
(e)g(part)h(of)f(fu-)1040 1435 y(ture)d(routers,)h(man)o(y)g(routers)g
(to)q(da)o(y)g(implemen)o(t)h Fl(\014rew)o(alls)h Fn([3])1040
1477 y(at)i(trust)g(b)q(oundaries,)k(suc)o(h)d(as)f(the)h(en)o(try)f
(and)h(exit)g(p)q(oin)o(ts)1040 1518 y(of)i(a)h(corp)q(orate)g(net)o(w)
o(ork.)40 b(A)20 b(\014rew)o(all)i(database)f(consists)1040
1560 y(of)e(a)h(series)h(of)f(pac)o(k)o(et)g(\014lters)h(\(or)f(rules)g
(based)h(on)f(pac)o(k)o(et)1040 1601 y(header)15 b(\014elds\))h(that)e
(implemen)o(t)j(securit)o(y)e(p)q(olicies.)24 b(Despite)1040
1643 y(the)17 b(progress)h(made)g(in)f(the)h(last)f(y)o(ear)h(on)f
(solutions)j(to)d(the)1040 1684 y(pac)o(k)o(et)9 b(classi\014cation)j
(problem)e([8,)e(13)q(],)h(existing)h(\014rew)o(all)h(soft-)1040
1726 y(w)o(are)i(is)g(still)i(slo)o(w.)1096 1767 y(While)21
b(the)e(general)h(solution)h(in)f([8)o(])f(can)g(handle)h(thou-)1040
1809 y(sands)14 b(of)g(\014lters)h(at)e(v)o(ery)h(high)h(sp)q(eeds,)g
(it)f(is)g(geared)h(to)o(w)o(ards)1040 1850 y(hardw)o(are)f(and)f(uses)
h(hardw)o(are)g(parallelis)q(m)i(and)d(high)i(sp)q(eed)1040
1892 y(memories.)23 b(The)15 b(solutions)i(in)f([13])e(ha)o(v)o(e)h(a)g
(high)h(w)o(orst)f(case)1040 1933 y(\014gure)g(for)g(the)f(general)j
(pac)o(k)o(et)e(\014lter)g(problem.)24 b(Th)o(us)15 b(there)1040
1975 y(is)d(ro)q(om)f(for)g(further)g(researc)o(h)h(esp)q(ecially)i(in)
e(the)f(area)h(of)e Fm(soft-)1040 2016 y(war)n(e)h(p)n(acket)f
(classi\014c)n(ati)o(on)o(.)j Fn(Existing)g(solutions)g(are)e(also)h
(op-)1040 2058 y(timized)j(for)e(the)g(case)h(when)g(up)q(dates)g(are)g
(infrequen)o(t.)20 b(Ho)o(w-)1040 2099 y(ev)o(er,)14
b(man)o(y)g(\014rew)o(all)h(v)o(endors)g(no)o(w)f(o\013er)g(stateful)h
(\014lters)g([4].)1040 2141 y(F)m(or)e(example,)i(the)e(sending)j(of)d
(a)h(UDP)f(request)h(ma)o(y)g(trigger)1040 2183 y(the)f(addition)i(of)d
(a)h(\014lter)h(addition)h(that)e(allo)o(ws)h(the)f(resp)q(onse)1040
2224 y(to)d(\015o)o(w)g(past)h(the)g(\014rew)o(all.)17
b(This)11 b(ma)o(y)g(require)g(\014lter)h(insertion)1040
2266 y(in)18 b(the)g(order)g(of)g(microseconds.)33 b(Other)17
b(applicatio)q(ns)k(that)1040 2307 y(ma)o(y)14 b(require)h(fast)f
(\014lter)h(up)q(dates)g(include)h(resource)f(reserv)n(a-)1040
2349 y(tion)f(proto)q(cols)g(lik)o(e)h(RSVP)e([2].)1096
2390 y(Th)o(us)19 b(faster)g(soft)o(w)o(are)g(pac)o(k)o(et)h
(classi\014cation)i(with)e(fast)1040 2432 y(up)q(date)h(times)f(can)g
(b)q(ene\014t)h(screening)h(routers)e(and)g(man)o(y)1040
2473 y(commercial)g(\014rew)o(all)h(soft)o(w)o(are)d(pac)o(k)n(ages.)35
b(It)19 b(can)g(also)h(b)q(e)1040 2515 y(useful)c(for)e(other)i
(applications)i(of)d(pac)o(k)o(et)g(classi\014catio)q(n)j(im-)1040
2556 y(plemen)o(ted)i(in)g(sa)o(y)f(endno)q(des,)i(whic)o(h)f(are)f
(unlik)o(ely)j(to)c(use)1040 2598 y(FPGA)13 b(or)g(ASIC)f(based)i
(solutions.)p eop
%%Page: 2 2
2 1 bop 56 53 a Fn(A)16 b(general)h(\014lter)f(consists)i(of)d
(arbitrary)j(pre\014x)e(or)g(range)0 95 y(sp)q(eci\014cations)i(on)e
(the)g(destination,)i(source,)e(proto)q(col,)i(p)q(ort)0
136 y(n)o(um)o(b)q(er)12 b(and)h(p)q(ossibly)h(other)e(\014elds.)18
b(There)11 b(is)h(evidence)i(that)0 178 y(the)h(general)g(\014lter)g
(problem)h(is)f(a)g(hard)g(problem)g([8,)f(13])g(and)0
224 y(requires)j(either)f(memory)g(of)f Fi(N)490 208
y Fh(K)535 224 y Fn(or)g(time)h(of)f Fi(O)q Fn(\()p Fi(N)t
Fn(\),)h(where)0 266 y Fi(N)e Fn(is)d(the)g(n)o(um)o(b)q(er)h(of)e
(\014lters)h(and)h Fi(K)g Fn(is)f(the)g(n)o(um)o(b)q(er)h(of)e(dimen-)0
307 y(sions.)21 b(W)m(e)14 b(con\014rm)h(this)g(gro)o(wing)g(b)q(o)q
(dy)g(of)f(evidence)i(in)f(our)0 349 y(pap)q(er)f(with)h(some)f(new)f
(lo)o(w)o(er)h(b)q(ounds)h(in)g(a)f(hashing)h(mo)q(del,)0
390 y(whic)o(h)h(complemen)o(t)g(the)e(earlier)j(lo)o(w)o(er)e(b)q
(ounds)h(on)f(m)o(ultidi-)0 432 y(mensional)g(range)f(matc)o(hing)g
(quoted)g(in)g([8,)f(13].)56 473 y(The)g(lo)o(w)o(er)h(b)q(ounds)h
(indicate)g(that)f(to)f(do)g(b)q(etter)h(one)g(has)0
515 y(to)h Fm(exploit)e(the)i(semantics)e(of)i(actual)f(datab)n(ases.)
20 b Fn(Since)c(\014re-)0 556 y(w)o(all)d(databases)h(are)e(commonly)i
(used,)f(w)o(e)f(decided)i(to)e(exam-)0 598 y(ine)18
b(actual)h(\014rew)o(all)g(databases)g(to)e(see)g(if)h(there)g(w)o(ere)
f(some)0 639 y(regularities)g(w)o(e)c(could)i(exploit.)21
b(On)14 b(examination)i(w)o(e)d(found)0 681 y(that)h(there)f(w)o(ere)g
(only)i(a)f(few)e(com)o(binations)17 b(of)c(\014eld)i(lengths)0
722 y(used)i(in)g(\014rew)o(all)g(\014lters.)27 b(In)o(tuitiv)o(ely)m
(,)19 b(this)e(follo)o(ws)g(b)q(ecause)0 764 y(most)c(address)h
(pre\014xes)g(are)g(based)g(on)f(Class)h(C)e(\(24)i(bit\))f(and)0
805 y(Class)i(B)f(\(16)g(bits\))g(pre\014xes.)21 b(Similarly)c(p)q(ort)
e(\014elds)g(are)f(t)o(yp-)0 847 y(ically)i(either)e(fully)h(sp)q
(eci\014ed)g(p)q(ort)f(n)o(um)o(b)q(ers)h(\(e.g.,)d(p)q(ort)i(23\),)0
888 y(the)j(wildcard)h(range)f(\(*\),)g(or)f(the)h(single)h(range)f(\()
p Fi(>)f Fn(1024)h(or)0 930 y Fg(\024)11 b Fn(1023\).)143
914 y Ff(1)56 971 y Fn(This)21 b(motiv)n(ated)g(us)f(to)f(examine)j
(what)d(w)o(e)h(call)h Fm(T)m(uple)0 1013 y(Se)n(ar)n(ch)p
Fn(.)16 b(In)d(its)h(simplest)h(form,)d(T)m(uple)i(Searc)o(h)g
(examines)h(the)0 1055 y(space)i(of)g(tuples)h(in)f(a)g(\014lter)h
(database,)g(where)f(a)g(tuple)h(is)f(a)0 1096 y(com)o(bination)f(of)d
(\014eld)h(lengths.)19 b(Eac)o(h)14 b(c)o(hec)o(k)f(for)g(a)g(tuple)i
(can)0 1138 y(b)q(e)h(e\016cien)o(tly)i(done)f(b)o(y)f(hashing.)28
b(Next,)17 b(w)o(e)e(dev)o(elop)j(some)0 1179 y(additional)g
(heuristics)f(for)e(sp)q(eeding)i(up)e(T)m(uple)h(Searc)o(h,)f(and)0
1221 y(use)g(them)f(to)h(construct)g(e\016cien)o(t)h(and)f(practical)h
(implemen-)0 1262 y(tations,)f(some)g(of)e(whic)o(h)i(ha)o(v)o(e)g
(fast)f(up)q(date)h(times.)21 b(W)m(e)14 b(also)0 1304
y(dev)o(elop)i(the)e(theory)h(b)q(ehind)h(T)m(uple)e(Searc)o(h.)21
b(W)m(e)15 b(sho)o(w)f(that)0 1345 y(the)e(general)i(\014lter)e(case)h
(is)f(indeed)i(hard)f(in)f(the)g(T)m(uple)h(Searc)o(h)0
1387 y(paradigm)g(as)f(w)o(ell,)h(con\014rming)h(the)e(in)o(tuition)i
(in)f([8,)e(13].)16 b(F)m(or)0 1428 y(the)h(sp)q(ecial)i(case)f(of)f(t)
o(w)o(o-dimensional)j(\014lters,)f(w)o(e)d(describ)q(e)0
1470 y(an)10 b(optimal)i(T)m(uple)e(Searc)o(h)h(sc)o(heme)f(called)h
(Rectangle)h(Searc)o(h,)0 1511 y(whose)e(p)q(erformance)g(is)g
(comparable)i(to)d(the)h(t)o(w)o(o-dimensional)0 1553
y(algorithms)15 b(presen)o(ted)f(in)g([8,)e(13)q(].)56
1594 y(This)h(pap)q(er)h(is)f(organized)h(as)f(follo)o(ws.)18
b(W)m(e)12 b(pro)o(vide)j(bac)o(k-)0 1636 y(ground)i(on)f(\014rew)o
(alls)i(in)f(Section)g(2,)f(and)h(formally)g(describ)q(e)0
1677 y(the)e(pac)o(k)o(et)h(classi\014catio)q(n)i(problem)f(in)f
(Section)h(3.)23 b(W)m(e)16 b(sur-)0 1719 y(v)o(ey)g(related)h(w)o(ork)
e(in)i(Section)g(4.)25 b(W)m(e)15 b(start)h(our)g(discussion)0
1760 y(of)e(tuple)i(space)f(searc)o(h)g(in)h(Section)g(5)e(with)h(the)g
(simplest)h(tu-)0 1802 y(ple)i(searc)o(h.)32 b(In)17
b(Section)i(6,)g(w)o(e)e(describ)q(e)i(a)f(simple)h(heuris-)0
1843 y(tic)d(v)n(arian)o(t)g(of)f(the)h(basic)g(tuple)h(searc)o(h)e
(called)j Fl(T)m(uple)e(Prun-)0 1885 y(ing)s Fn(,)h(that)f(has)g(fast)f
(searc)o(h)h(and)g(up)q(date)h(times.)25 b(While)18 b(T)m(u-)0
1926 y(ple)d(Pruning)g(app)q(ears)g(to)f(b)q(e)g(our)g(most)g
(practical)i(algorithm)0 1968 y(\(based)e(on)f(our)h(exp)q(erience)h
(with)f(real)f(databases\),)i(its)e(w)o(orst)0 2009 y(case)f(case)f
(searc)o(h)h(time)g(for)f Fm(arbitr)n(ary)f Fn(databases)i(can)g(b)q(e)
g(bad.)0 2051 y(In)18 b(Section)i(7,)f(w)o(e)e(sho)o(w)h(ho)o(w)g(to)g
(impro)o(v)o(e)i(the)e(w)o(orst)g(case)0 2092 y(searc)o(h)e(time)h(of)e
(tuple)i(searc)o(h)g(using)g(mark)o(ers)f(and)h(precom-)0
2134 y(putation.)h(In)11 b(Section)k(8,)c(w)o(e)g(also)h(describ)q(e)h
(an)e(optimal)i(algo-)0 2175 y(rithm)i(for)f(2-dimensional)k
(\014lters.)k(Next,)14 b(w)o(e)g(describ)q(e)i(lo)o(w)o(er)0
2217 y(b)q(ounds)c(on)g(the)f(general)h(tuple)g(searc)o(h)g(problem)g
(in)g(Section)g(9.)0 2258 y(In)20 b(Section)15 b(10)20
b(w)o(e)g(describ)q(e)i(another)g(balancing)h(heuristic)0
2300 y(for)16 b(computing)h(a)f(go)q(o)q(d)h(prob)q(e)f(sequence)h(for)
f(general)h(tuple)0 2341 y(spaces)10 b(while)g(exploiting)i(mark)o(ers)
d(and)h(precomputation.)18 b(W)m(e)0 2383 y(conclude)d(in)f(Section)g
(11.)p 0 2406 377 2 v 43 2430 a Fe(1)60 2442 y Fj(Because)8
b(BSD)h(UNIX)f(reserv)o(es)h(p)q(orts)f(0)h(to)f(1023)f(for)i(lo)q(cal)
f(use)h(only)0 2476 y(b)o(y)k(ro)q(ot,)f(these)g(p)q(orts)g(are)g(only)
h(used)f(b)o(y)h(serv)o(ers,)h(not)e(clien)o(ts.)19 b(Other)0
2509 y(op)q(erating)9 b(systems)i(ha)o(v)o(e)f(follo)o(w)o(ed)g(this)h
(custom.)k(This)10 b(allo)o(ws)g(pac)o(k)o(ets)0 2542
y(sen)o(t)j(b)o(y)h(serv)o(ers)f(to)f(b)q(e)h(distinguished)i(from)d
(pac)o(k)o(ets)h(sen)o(t)g(b)o(y)h(clien)o(ts.)0 2575
y(Filters)i(for)f(X)g(serv)o(ers)h(are)e(another)h(non-trivial)i
(example)f(of)f(a)f(p)q(ort)0 2608 y(range)c(\(e.g.,)i(60000-6100)o
(0\))c(but)k(these)f(are)f(less)i(common.)1040 53 y Fo(2)40
b(A)15 b(Brief)e(Intro)q(duction)g(to)g(Firew)o(alls)1040
132 y Fn(While)i(the)e(tec)o(hniques)i(in)f(our)g(pap)q(er)g(are)f
(applicable)j(to)d(an)o(y)1040 173 y(application)22 b(that)c(requires)i
(pac)o(k)o(et)f(classi\014cation)q(,)j(w)o(e)c(pro-)1040
215 y(vide)e(some)f(bac)o(kground)j(on)d(\014rew)o(alls.)25
b(Firew)o(alls)17 b(pro)o(vide)g(a)1040 256 y(concrete)h(applicatio)q
(n)j(of)c(pac)o(k)o(et)i(classi\014cation)i(where)d(fast)1040
298 y(soft)o(w)o(are)13 b(implemen)o(tations)j(are)d(curren)o(tly)h
(desired.)1096 339 y(Firew)o(alls)d(are)d(implemen)o(ted)j(using)g(v)n
(arious)f(com)o(binations)1040 381 y(of)k(t)o(w)o(o)f(basic)i(tec)o
(hniques)h([4]:)j Fm(p)n(acket)12 b(\014ltering)g Fn(and)j
Fm(applic)n(a-)1040 422 y(tion)h(level)g(gateways)f Fn(\(also)j(kno)o
(wn)g(as)f(pro)o(xy)h(services\).)31 b(In)1040 464 y(pac)o(k)o(et)13
b(\014ltering,)h(a)f(so-called)h Fm(scr)n(e)n(ening)d(r)n(outer)g
Fn(\(also)i(kno)o(wn)1040 505 y(as)j(a)h Fm(choke)d(r)n(outer)p
Fn(\))h(sits)i(b)q(et)o(w)o(een)g(the)g(external)g(and)g(in)o(ter-)1040
547 y(nal)12 b(w)o(orlds,)g(and)g(allo)o(ws)h(or)e(blo)q(c)o(ks)i
(certain)g(t)o(yp)q(es)e(of)g(pac)o(k)o(ets.)1040 588
y(Unlik)o(e)g(con)o(v)o(en)o(tional)h(routers,)f(screening)g(routers)f
(mak)o(e)g(their)1040 630 y(decision)k(based)e(on)g(La)o(y)o(er)g(3)g
(headers)g(as)g(w)o(ell)h(as)f(La)o(y)o(er)f(