tradeoffs for packet classification.ps

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

Fu(W)m(e)e(present)f(a)h(no)o(v)o(el)g(algorithmic)e(frame)o(work)975
2762 y(for)e(solving)g(the)g(packet)h(classi\002cation)g(problem.)k(It)
7 b(relies)h(on)f(insights)975 2811 y(from)j(computational)f(geometry)m
(,)i(and)f(has)h(the)f(follo)o(wing)d(interesting)p eop
%%Page: 2 2
2 1 bop 2017 -139 a FB(2)-130 -23 y Fu(features.)30 b(\(1\))15
b(It)g(allo)o(ws)g(v)o(arious)g(access)j(time)d(vs.)h(memory)g(space)
-130 26 y(tradeof)o(fs,)f(and)f(can)h(be)g(engineered)f(for)f(dif)o
(ferent)h(applications.)23 b(In)-130 76 y(particular)n(,)10
b(it)g(gi)o(v)o(es)g(the)h(currently)e(best)h(kno)o(wn)g(access)i
(times)f(for)f(the)-130 125 y(packet)16 b(classi\002cation)f(problem)g
(with)f(moderate)i(amount)g(of)f(mem-)-130 174 y(ory)e(use.)24
b(\(2\))13 b(It)g(reduces)i(the)f(packet)f(classi\002cation)h(problem)f
(\(with)-130 224 y(arbitrary)g(ranges)i(and)g Fo(d)p
Fu(-dimensions,)f Fo(d)19 b Fr(\025)g Fp(1)p Fu(\))14
b(to)g(a)g(small)h(number)-130 273 y(of)f(in)n(v)o(ocations)g(of)g(a)h
(speci\002c)h(one-dimensional)d(packet)i(classi\002ca-)-130
323 y(tion)9 b(problem,)h(namely)m(,)i(the)e Ft(IP)g(Lookup)g
Fu(problem)g(in)g(which)g(all)g(rules)-130 372 y(are)j(pre\002x)f
(ranges.)20 b(Man)o(y)12 b(optimized)f(software)h([5],)h([12],)f([17])g
(and)-130 421 y(hardware)k(solutions)d(\(e.g.,)34 b([10]\))15
b(are)h(kno)o(wn)f(for)g(the)g(IP)g(Lookup)-130 471 y(problem.)f(Using)
c(our)h(frame)o(work,)g(these)g(are)h(no)o(w)e(applicable)h(to)f(the)
-130 520 y(general)h(packet)g(classi\002cation)f(problem.)k(\(3\))c(It)
g(allo)o(ws)g(ef)o(\002cient)h(up-)-130 570 y(dates)h(to)g(the)f
(ruleset)h(without)e(recomputing)h(the)g(full)g(data)h(structure.)-130
619 y(Moderate)i(amount)e(of)h(updates)h(\(additions)d(as)j(well)f(as)h
(deletions)e(of)-130 668 y(rules\))d(do)h(not)e(ef)o(fect)j(the)e
(access)j(times)e(signi\002cantly;)d(this)i(is)h(the)f(\002rst)-130
718 y(such)i(solution)d(for)h(the)i(packet)f(classi\002cation)g
(problem.)-88 769 y(W)m(e)j(test)g(our)f(two-dimensional)f(algorithm)g
(on)i(rulesets)g(\(source/-)-130 818 y(destination)d(ranges\))j(deri)o
(v)o(ed)f(from)g(\003o)o(w)g(traces)h(collected)f(at)g(multi-)-130
867 y(ple)i(backbone)g(routers)g(of)f(an)i(ISP)-5 b(,)15
b(A)-5 b(T&T)15 b(W)m(orldNet.)23 b(The)15 b(results)-130
917 y(sho)o(w)g(that)h(our)f(algorithm)f(can)i(perform)g(packet)g
(classi\002cation)f(for)-130 966 y(rulesets)f(of)g(size)h(be)o(yond)f
Fp(10)317 951 y Fn(6)350 966 y Fu(with)f(at)h(most)g
Fp(18)g Fu(memory)h(accesses)-130 1016 y(\(assuming)9
b(that)f(each)j(memory)e(access)i(retrie)o(v)o(es)f(a)g(full)d
Fp(32)i Fu(bit)f(cache-)-130 1065 y(line)h([15]\))g(in)g(the)g(worst)g
(case.)14 b(The)d(space)g(to)e(store)g(the)g(data)h(structure)-130
1114 y(is)15 b(at)g(most)g(a)h(factor)e(of)h Fp(5)g Fu(bigger)f(than)h
(the)f(space)j(needed)e(to)g(store)-130 1164 y(the)f(rules)f(themselv)o
(es.)25 b(No)14 b(pre)o(vious)f(e)o(xperimental)h(result)f(consid-)-130
1213 y(ered)h(real)f(datasets)g(of)g(this)f(magnitude.)42
b(The)14 b(number)f(of)f(memory)-130 1263 y(accesses)17
b(can)e(be)g(further)e(reduced)i(by)f(using)f(bigger)h(cachelines)h(or)
-130 1312 y(lar)o(ger)c(memory)m(.)-88 1363 y(At)k(the)i(technical)f
(core,)i(our)e(algorithmic)f(frame)o(work)h(relies)g(on)-130
1412 y(data)c(structural)f(solutions)e([7])j(in)f(which)g(the)g(access)
j(time)e(is)f(aggres-)-130 1462 y(si)o(v)o(ely)e(minimized)f(\(to)h
(roughly)e Fo(O)q Fp(\(log)f(log)h Fo(U)e Fp(\))k Fu(where)h
Fo(U)k Fu(is)9 b(the)f(range)-130 1511 y(of)j(IP)h(addresses\).)19
b(W)m(e)12 b(modify)e(their)h(algorithm)g(to)g(eliminate)g(man)o(y)-130
1560 y(of)j(the)f(steps)i(with)d(inherently)h(lar)o(ge)h(constants.)24
b(Consequently)12 b(we)-130 1610 y(ha)o(v)o(e)h(obtained)f(a)h(simple)f
(solution)e(which)i(we)h(further)e(e)o(xtend)i(to)f(al-)-130
1659 y(lo)o(w)c(dynamic)h(updates.)k(The)c(theoretical)f(solution)f
(could)h(use)i(moder)o(-)-130 1709 y(ately)f(lar)o(ge)h(memory)g(space)
h(\(e.g.,)g Fo(O)q Fp(\()p Fo(n)470 1694 y Fn(1+)p Fm(\017)528
1709 y Fp(\))f Fu(for)f Fp(1)i Fo(>)h(\017)f(>)h Fp(0)e
Fu(where)g Fo(n)-130 1758 y Fu(is)f(the)g(number)g(of)g(rules\).)j(Ho)o
(we)o(v)o(er)n(,)f(our)e(e)o(xperiments)g(sho)o(w)g(that)g(the)-130
1807 y(memory)k(usage)g(of)f(our)f(algorithm)g(is)h(quite)f(reasonable)
i(on)f(realistic)-130 1857 y(datasets.)-130 1908 y Fs(Organization:)19
b Fu(W)m(e)c(de\002ne)g(the)f(packet)g(classi\002cation)g(problem)f(in)
-130 1957 y(Section)d(II)f(and)h(ne)o(xt)g(present)g(our)f(algorithmic)
g(frame)o(work)h(for)f(static)-130 2007 y(\(Sections)k(III)f(\226)h
(V\),)h(as)g(well)f(as)h(dynamic)f(cases)h(\(Section)f(VI\).)21
b(W)m(e)-130 2056 y(discuss)15 b(engineering)e(tradeof)o(fs)h(in)g
(Section)h(VII.)25 b(In)15 b(Section)f(VIII,)-130 2105
y(we)c(focus)f(on)g(the)g(two-dimensional)e(problem)i(and)g(present)g
(e)o(xtensi)o(v)o(e)-130 2155 y(e)o(xperimental)17 b(results.)31
b(W)m(e)17 b(re)o(vie)o(w)f(related)h(work)e(in)h(Section)g(IX.)-130
2204 y(Concluding)8 b(remarks)j(and)g(future)e(work)g(are)i(in)f
(Section)g(X.)141 2296 y(I)r(I)r(.)23 b(P)r Fv(R)q(O)r(B)r(L)r(E)r(M)13
b(S)r(P)r(E)r(C)r(I)r(FI)r(C)r(A)n(T)r(I)r(O)r(N)-88
2367 y Fu(Informally)m(,)19 b(the)g(packet)f(classi\002cation)g
(problem)g(identi\002es)g(the)-130 2416 y(\003o)o(w)e(a)h(packet)f
(belongs)f(to,)j(based)f(on)e(one)i(or)e(more)i(\002elds)f(in)g(the)
-130 2465 y(packet)9 b(header)n(.)k(F)o(ormally)m(,)c(the)f
Fo(d)p Ft(-dimensional)e(pac)o(ket)i(classi\002cation)-130
2515 y(pr)n(oblem)j Fu(\(denoted)f(as)i Fl(PC)f Fu(problem\))g(is)g(as)
g(follo)o(ws.)k(W)m(e)c(are)h(gi)o(v)o(en)f(a)-130 2564
y(set)g Fr(R)j Fp(=)f Fr(f)p Fo(r)61 2570 y Fn(1)79 2564
y Fo(;)7 b(:)g(:)g(:)e(;)i(r)191 2570 y Fm(n)213 2564
y Fr(g)k Fu(of)g(rules)g(o)o(v)o(er)h Fo(d)f Fu(\002elds)g
(\(dimensions\).)k(Each)-130 2614 y(rule)c(consist)g(of)h(a)g(set)g(of)
f(ranges)h Fo(r)393 2620 y Fm(i)421 2614 y Fp(=)i([)p
Fo(F)512 2599 y Fm(i)506 2624 y Fn(1)525 2614 y Fo(;)7
b(:)g(:)g(:)e(;)i(F)651 2599 y Fm(i)645 2625 y(d)664
2614 y Fp(])p Fu(,)12 b(where)g Fo(F)844 2599 y Fm(i)838
2624 y(j)869 2614 y Fu(is)f(a)-130 2663 y(range)f(\(interv)o(al\))d(of)
i(v)o(alues)h(the)f(\002eld)g Fo(j)j Fu(may)e(take;)f(each)h(rule)f
(also)g(has)-130 2712 y(a)k Ft(cost)p Fu(.)19 b(The)13
b(set)g(of)f(rules)g(may)h(be)g(preprocessed.)20 b(Queries)13
b(are)g(pre-)-130 2762 y(sented)f(on)g(line.)18 b(Each)13
b(query)f(is)g(a)g(packet)g Fo(p)j Fp(=)g([)p Fo(f)640
2768 y Fn(1)659 2762 y Fo(;)7 b(:)g(:)g(:)e(;)i(f)772
2768 y Fm(d)791 2762 y Fp(])p Fu(,)12 b(where)-130 2811
y(each)17 b Fo(f)-18 2817 y Fm(i)12 2811 y Fu(is)f(a)h(singleton)d(v)o
(alue.)30 b(A)16 b(rule)f Fo(r)533 2817 y Fm(i)563 2811
y Ft(applies)g Fu(to)g(a)i(packet)f Fo(p)p 1066 -63 874
2 v 1065 -14 2 50 v 1091 -29 a Fu(Reference)p 1284 -14
V 54 w(Space)11 b(used)p 1524 -14 V 53 w(#)f(of)g(memory)h(accesses)p
1939 -14 V 1066 -12 874 2 v 1066 -4 V 1065 46 2 50 v
1151 31 a([5])p 1284 46 V 160 w Fo(O)q Fp(\()p Fo(n)p
Fp(\))p 1524 46 V 194 w Fo(O)q Fp(\(log)1746 41 y Fn(2)1772
31 y Fo(U)5 b Fp(\))p 1939 46 V 1065 95 V 1141 80 a Fu([17])p
1284 95 V 102 w Fo(O)q Fp(\()p Fo(n)i Fp(log)g Fo(n)p
Fp(\))p 1524 95 V 108 w Fo(O)q Fp(\(log)1707 90 y Fn(2)1732
80 y Fp(log)1786 90 y Fn(2)1812 80 y Fo(U)e Fp(\))p 1939
95 V 1065 144 V 1141 130 a Fu([12])p 1284 144 V 98 w
Fk(RL)1353 136 y Fm(s)1371 130 y Fp(\(2)p Fo(n;)i(U)e
Fp(\))p 1524 144 V 138 w Fk(RL)1682 136 y Fm(t)1697 130
y Fp(\(2)p Fo(n;)i(U)e Fp(\))p 1939 144 V 1066 146 874
2 v 1442 197 a Fv(T)m(ABLE)k(I)1161 247 y(P)r Fj(E)r(R)r(F)r(O)r(R)r(M)
r(A)q(N)r(C)r(E)e(B)r(O)r(U)r(N)r(D)r(S)h(F)r(O)r(R)h(T)r(H)r(E)g
Fi(IPL)g Fj(P)r(R)q(O)r(B)r(L)r(E)r(M)975 417 y Fu(if)16
b(for)f(all)h(dimensions)f Fo(k)q Fu(,)j(the)e(\002eld)g(v)o(alue)g
Fo(f)1677 423 y Fm(k)1714 417 y Fu(of)f(packet)h Fo(p)g
Fu(lies)g(in)975 466 y(the)e(range)h Fo(F)1180 451 y
Fm(i)1174 478 y(k)1194 466 y Fu(.)25 b(The)15 b(problem)f(is)g(to)g
(determine)g(the)g(least)h(cost)f(rule)975 516 y(that)f(applies)g(to)g
(the)g(packet.)1410 501 y FB(2)1449 516 y Fu(F)o(or)h(e)o(xample,)i(in)
d(layer)o(-four)f(switch-)975 565 y(ing,)i(the)f(dimensions)g(could)g
(consist)g(of)g(the)h(source)g(address,)h(desti-)975
615 y(nation)9 b(address,)j(source)e(port,)g(and)h(destination)d(port.)
13 b(A)d(rule)g(such)h(as)975 664 y Fp([135)p Fo(:)p
Fp(207)p Fo(:)p Fr(\003)p Fo(;)6 b Fp(12)p Fo(:)o Fr(\003)p
Fo(;)h Fp(1)o(024)q Fr(\000)q Fp(6553)o(5)p Fo(;)g Fp(2)o(0)q
Fr(\000)q Fp(23])e Fu(may)k(be)f(used)h(to)e(allo)o(w)h(IP)975
713 y(addresses)14 b(within)c(A)-5 b(T&T)14 b(Labs-Research)h(to)c
(contact)i(IP)f(addresses)975 763 y(within)c(W)m(orldNet)h(either)g
(via)g(ftp,)h(ssh,)g(or)g(telnet.)i(Hosts)e(from)f(A)-5
b(T&T)975 812 y(Labs-Research)12 b(are)e(restricted)g(to)f(use)h(an)o
(y)h(of)e(the)h(non-pri)o(v)o(ate)e(ports.)975 862 y(Depending)14
b(on)h(ho)o(w)g(costs)g(are)h(assigned)f(to)f(rules)h(one)g(can)h
(model)975 911 y(dif)o(ferent)9 b(\003a)o(v)o(ors)i(of)f(the)g
Fl(PC)g Fu(problem)g(\(see)h([9]\).)1017 962 y(The)g(rules)g(ha)o(v)o
(e)g(a)h(natural)e(geometric)h(interpretation)d(in)i
Fo(d)h Fu(dimen-)975 1012 y(sions.)j(Each)d(rule)g Fo(r)1273
1018 y Fm(i)1297 1012 y Fu(can)g(be)g(thought)e(of)h(as)i(a)f
(\223hyperrectangle\224)g(in)f Fo(d)975 1061 y Fu(dimensions)e
(\(called)h(rectangles)h(henceforth\),)f(obtained)f(by)g(the)h(cross)
975 1110 y(product)f(of)g(the)h(interv)o(als)e Fo(F)1397
1095 y Fm(i)1391 1121 y(j)1419 1110 y Fu(along)i(each)g(of)g(the)f
(dimensions)g Fo(j)r Fu(.)13 b(Thus)975 1160 y(the)d(set)g(of)f(rules)h
Fr(R)g Fu(no)o(w)f(corresponds)h(to)f(a)h(set)g(of)g(rectangles)g(in)f
Fo(d)g Fu(di-)975 1209 y(mensions.)j(Each)e(packet)e
Fo(p)g Fu(corresponds)g(to)g(a)h(point)d(in)i Fo(d)g
Fu(dimensions,)975 1259 y(and)i(the)f Fl(PC)h Fu(problem)f(is)h
(identical)f(to)g(the)g Ft(r)n(ectangle)h(enclosur)n(e)h(pr)n(ob-)975
1308 y(lem)p Fu(,)g(that)e(is,)h(gi)o(v)o(en)g(a)h(set)f(of)g
(rectangles)g Fr(R)p Fu(,)h(determine)f(the)g(least)h(cost)975
1357 y(rectangle)g(that)e(encloses)i(an)o(y)g(query)f(point)e
Fo(p)p Fu(.)1017 1409 y(In)g(solving)g(the)h Fl(PC)g
Fu(problem,)g(the)g(parameters)i(of)e(interest)f(are)i(stor)o(-)975
1458 y(age)15 b(space)h(and)e(the)g(number)g(of)g(memory)h(accesses)i
(performed)d(per)975 1508 y(query)c(\(which)g(is)g(the)g(dominating)e
(lookup)h(cost\).)1138 1600 y(I)r(I)r(I)r(.)23 b(O)r
Fv(N)r(E)r Fu(-)r Fv(D)r(I)r(M)r(E)r(N)r(S)r(I)r(O)r(N)q(A)r(L)14
b(C)r(L)r(A)r(S)r(S)r(I)r(FI)r(C)r(A)n(T)r(I)r(O)r(N)1017
1672 y Fu(The)e(one-dimensional)e Fl(PC)h Fu(problem)g(is:)j(gi)o(v)o
(en)d(a)h(set)g(of)f Fo(n)h Fu(rules)f(\226)975 1722
y(possibly)e(o)o(v)o(erlapping)g(interv)o(als)g(from)h
Fp([1)d Fr(\001)g(\001)g(\001)e Fo(U)g Fp(])10 b Fu(\226)g(each)h(with)
e(a)i(cost,)975 1771 y(answer)g(lookup)e(queries)i(for)f(point)f
Fo(q)k Fr(2)e Fp([1)c Fr(\001)g(\001)g(\001)e Fo(U)g
Fp(])10 b Fu(by)g(identifying)e(the)975 1820 y(smallest)i(cost)h(rule)f
(that)f(contains)h Fo(q)q Fu(.)975 1872 y Fs(Special)h(case)h(one:)j
Fu(The)d Ft(IP)g(Lookup)f Fu(\()p Fl(IPL)p Fu(\))f(problem)h(is)g(a)h
(subprob-)975 1921 y(lem)h(of)f(the)h(general)g Fl(PC)g
Fu(problem)f(in)g(which)g(each)i(range)f(is)f(a)i(pre\002x)975
1970 y(of)g(an)h(IP)f(address)h(\(IP)f(addresses)i(are)f(in)f
Fp([1)7 b Fr(\001)g(\001)g(\001)t Fo(U)e Fp(])p Fu(,)16
b(with)d Fo(U)24 b Fp(=)c(2)1997 1955 y Fn(32)975 2020
y Fu(for)12 b(IPv4\).)20 b(Each)14 b(query)e Fo(q)i Fu(is)f(an)g(IP)g
(address.)21 b(The)13 b(task)g(is)f(to)h(deter)o(-)975
2069 y(mine)d(the)f(least)h(cost)g(rule)f(that)g(is)h(a)g(pre\002x)f
(of)h Fo(q)q Fu(.)j(The)d Fl(IPL)g Fu(problem)f(is)975
2119 y(the)i(classical)h Fl(PC)f Fu(problem)g(based)h(on)e(the)h
(destination)f(IP)h(addresses.)975 2168 y(The)17 b(worst)f(case)i
(number)f(of)f(memory)i(accesses)h(needed)e(to)f(solv)o(e)975
2217 y(this)e(problem)g(is)h(denoted)f(by)g Fk(IPL)1514
2223 y Fm(t)1528 2217 y Fp(\()p Fo(n;)7 b(U)e Fp(\))15
b Fu(and)f(the)h(space)h(used)f(by)975 2267 y Fk(IPL)1040
2273 y Fm(s)1058 2267 y Fp(\()p Fo(n;)7 b(U)e Fp(\))p
Fu(.)20 b(The)13 b(best)f(kno)o(wn)g(performance)h(bounds)e(for)h(the)h
Fl(IPL)975 2316 y Fu(problem)d(are)h(in)e(T)m(able)i(I.)i(\()p
Fl(RL)d Fu(will)f(be)i(de\002ned)f(shortly)m(.\))975
2368 y Fs(Special)g(case)g(two:)i Fu(The)f Ft(Range)e(Location)g
Fu(\()p Fl(RL)p Fu(\))g(problem)g(is)h(another)975 2417
y(subproblem)h(of)h(the)g(general)g Fl(PC)g Fu(problem)f(in)h(which)f
(the)h(ranges)h(are)975 2466 y(non-o)o(v)o(erlapping)7
b(and)i(completely)g(co)o(v)o(er)h(the)f(uni)o(v)o(erse)g
Fp(1)e Fr(\001)g(\001)g(\001)e Fo(U)g Fu(.)13 b(The)975
2516 y(collection)h(of)h(interv)o(als)f(of)h Fl(RL)g
Fu(can)h(be)g(speci\002ed)g(as)f(series)h(of)f(left)975
2565 y(end)e(points)e(of)i(the)f(interv)o(als)g(in)g(the)h(sorted)f
(order)n(.)21 b(Each)13 b(query)g Fo(q)h Fu(is)975 2614
y(an)c(inte)o(ger)n(,)g(and)g(the)g(goal)f(is)h(to)f(determine)h(the)f
(interv)o(al)g(that)g(contains)1002 2690 y Fq(2)1019
2702 y Fv(For)h(deb)o(ugging)e(purposes,)i(it)h(may)e(be)h(useful)g(to)
h(enumerate)d(all)j(rules)f(that)h(apply)975 2738 y(to)f(a)f(gi)o(ven)f
(packet)g(and)h(not)g(merely)g(return)g(the)g(one)f(with)i(the)f
(smallest)h(cost.)k(All)c(our)975 2775 y(solutions)f(can)h(be)g
(extended)e(to)i(determine)g(such)f(a)h(output,)h(and)e(we)h(do)g(not)g
(consider)975 2811 y(this)e(version)f(of)h(the)g(problem)f(any)f
(further)n(.)p eop
%%Page: 3 3
3 2 bop 2017 -139 a FB(3)-127 -65 y
 16577003 7128110 0 0 21773762 9472573 startTexFig
 -127 -65 a
%%BeginDocument: elementary.eps
/$F2psDict 200 dict def
$F2psDict begin
$F2psDict /mtrx matrix put
/col-1 {0 setgray} bind def
/col0 {0.000 0.000 0.000 srgb} bind def
/col1 {0.000 0.000 1.000 srgb} bind def
/col2 {0.000 1.000 0.000 srgb} bind def
/col3 {0.000 1.000 1.000 srgb} bind def
/col4 {1.000 0.000 0.000 srgb} bind def
/col5 {1.000 0.000 1.000 srgb} bind def
/col6 {1.000 1.000 0.000 srgb} bind def
/col7 {1.000 1.000 1.000 srgb} bind def
/col8 {0.000 0.000 0.560 srgb} bind def
/col9 {0.000 0.000 0.690 srgb} bind def
/col10 {0.000 0.000 0.820 srgb} bind def
/col11 {0.530 0.810 1.000 srgb} bind def
/col12 {0.000 0.560 0.000 srgb} bind def
/col13 {0.000 0.690 0.000 srgb} bind def
/col14 {0.000 0.820 0.000 srgb} bind def