tradeoffs for packet classification.ps

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

D<EA03F0EA0E1CEA1806487E00701380EA600100E013C0A600601380EA700300301300EA
1806EA0E1CEA03F012127F9115>I<EAFC7CEA1D87381E0180001C13C0EB00E0A21470A6
14E0A2EB01C0001E1380381D0700EA1CFC90C7FCA7B47E141A7F9117>I<EAFCE0EA1D38
EA1E78A2EA1C301300ACEAFFC00D127F9110>114 D<EA1F90EA2070EA4030EAC010A212
E0EAF800EA7F80EA3FE0EA0FF0EA00F8EA8038131812C0A2EAE010EAD060EA8FC00D127F
9110>I<1204A4120CA2121C123CEAFFE0EA1C00A91310A5120CEA0E20EA03C00C1A7F99
10>I E /Fq 8 56 df<13C0A9B51280A23800C000A911147E8F17>43
D<1218127812981218AC12FF08107D8F0F>49 D<121FEA6180EA40C0EA806012C01200A2
13C0EA0180EA030012065AEA10201220EA7FC012FF0B107F8F0F>I<121FEA2180EA60C0
A212001380EA0100121FEA00801340136012C0A2EA8040EA6080EA1F000B107F8F0F>I<
EA0180A212031205120D121912111221124112C1EAFFE0EA0180A4EA0FE00B107F8F0F>
I<EA20C0EA3F80EA2E001220A3122FEA3080EA2040EA0060A312C0EA80C0EA6180EA1F00
0B107F8F0F>I<EA0780EA1840EA30C0126013005A12CFEAF080EAE040EAC060A31240EA
60C0EA3080EA1F000B107F8F0F>I<1240EA7FF013E0EA8040A2EA0080EA01001202A212
061204A2120CA50C117F900F>I E /Fr 17 107 df<B61280A219027D8A20>0
D<126012F0A2126004047C8B0C>I<1203A4EAC30CEAE31CEA7338EA1FE0EA0780A2EA1F
E0EA7338EAE31CEAC30CEA0300A40E127D9215>3 D<EA03C0EA0FF0EA1FF8EA3FFCEA7F
FEA2B5FCA4EA7FFEA2EA3FFCEA1FF8EA0FF0EA03C010107E9115>15
D<EC01801407EC1E001478EB01E0EB0780011EC7FC1378EA01E0EA0780001EC8FC127812
E01278121EEA0780EA01E0EA0078131EEB0780EB01E0EB0078141EEC0780140191C7FCA7
007FB5FCB6128019227D9920>20 D<12C012F0123C120FEA03C0EA00F0133C130FEB03C0
EB00F0143C140FEC0380EC0F00143C14F0EB03C0010FC7FC133C13F0EA03C0000FC8FC12
3C127012C0C9FCA7007FB5FCB6128019227D9920>I<90387FFF800003B5FCD80780C7FC
000CC8FC5A5AA25AA25AA81260A27EA27E120E6C7E0001B512806C7E191A7D9620>26
D<EB7FF8EA01FF38078000000EC7FC12185AA25AA25AA3B512F8A200C0C7FCA31260A27E
A27E120E6C7E3801FFF8EA007F151A7D961C>50 D<1460A214C0A2EB0180A3EB0300A213
06A25BA25BA35BA25BA25BA2485AA248C7FCA31206A25AA25AA25AA35AA25A124013287A
9D00>54 D<EB3FFF48B512E039071E0FF039081C01F800381300D8703C1378126012C000
00147013385D01785B4A5A0202C7FCEB700CEB71F013F313E1EBE0F81201EBC07CA20003
133C9039803E0180ED07000007EB1F06010013880006EB0FF048EB07C0211D809B23>82
D<EB01FCEB07FF9038083F80EB300FEB700713E0EC06000001130491C7FC7F7F6C7E137E
6D7EEB1FE0EB07F0EB01F86D7E0008137C0038133C5AA200F01338A26C5B1460007C1380
D87F03C7FCEA3FFCEA0FF0191E7F9C19>I<150348B512FE000714F8390C00E00048485A
1230EA700312F000C05B12001307A291C7FCA25BA2130EA2131EA2131CA2133C1338A213
781370A213F05B5B485A20207F9C17>I<EA7F8012FFEAC000B3B3A31240092A7A9E12>
100 D<EAFF80A21201B3B3A31200092A7E9E12>I<133C13E0EA01C013801203AD13005A
121C12F0121C12077E1380AD120113C0EA00E0133C0E297D9E15>I<12F0121C12077E13
80AD120113C0EA00E0133C13E0EA01C013801203AD13005A121C12F00E297D9E15>I<12
C0B3B3A502297B9E0C>106 D E /Fs 133[18 21 21 30 21 23
14 16 18 23 23 21 23 35 12 23 1[12 23 21 14 18 23 18
23 21 12[28 23 30 32 25 32 30 39 28 2[16 2[25 28 30 30
28 30 6[14 11[10 43[23 2[{ TeXBase1Encoding ReEncodeFont }44
41.666668 /Times-Bold rf /Ft 134[18 18 28 18 21 12 16
16 21 21 21 21 30 12 18 12 12 21 21 12 18 21 18 21 21
9[35 25 30 23 21 25 1[25 30 28 1[23 2[14 2[25 25 30 28
25 25 5[14 14 6[21 21 21 2[10 14 10 2[14 14 36[21 21
2[{ TeXBase1Encoding ReEncodeFont }54 41.666668 /Times-Italic
rf /Fu 104[42 21 1[18 18 24[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 30 39 30 30 25 23 28 30 23 30 30 37 25 30 16
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 2[14 14 14 32 2[21 31[23 23 2[{
 TeXBase1Encoding ReEncodeFont }80 41.666668 /Times-Roman
rf /Fv 105[17 27[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 20 24 24
31 24 24 20 18 22 24 18 24 24 30 20 24 13 11 24 24 18
20 24 22 22 24 6[9 17 17 17 17 17 17 17 17 17 17 9 8
11 8 2[11 11 11 26 28 1[17 31[18 18 2[{ TeXBase1Encoding ReEncodeFont }
78 33.333332 /Times-Roman rf /Fw 104[33 29[17 17 24 17
18 11 13 15 1[18 17 18 28 9 18 1[9 18 17 11 15 18 15
18 17 9[33 2[22 18 2[20 1[24 4[13 2[20 4[24 18[8 11 8
5[28 35[18 2[{ TeXBase1Encoding ReEncodeFont }37 33.333332
/Times-Bold rf /Fx 134[15 15 22 15 17 9 13 13 1[17 17
17 24 9 15 1[9 17 17 9 15 17 15 17 17 9[28 2[18 17 20
1[20 24 22 28 18 1[15 11 24 24 20 20 1[22 1[20 6[11 11[8
11 45[{ TeXBase1Encoding ReEncodeFont }43 33.333332 /Times-Italic
rf /Fy 2 104 df<EB03C0EB1E0013385B5BB1485A485A000FC7FC12F8120FEA03806C7E
6C7EB113707F131EEB03C012317DA419>102 D<12F8120FEA03806C7E6C7EB113707F13
1EEB03C0EB1E0013385B5BB1485A485A000FC7FC12F812317DA419>I
E /Fz 105[25 32[25 14 19 17 2[25 25 39 14 25 14 14 25
2[22 25 22 25 22 12[30 28 33 1[28 1[36 44 30 1[19 3[28
4[36 46 17[12 1[12 5[39 38[{ TeXBase1Encoding ReEncodeFont }32
50.000000 /Times-Roman rf /FA 139[34 40 46 2[52 57 1[29
57 1[29 2[34 46 57 46 1[52 12[69 3[63 12[75 64[57 2[{
 TeXBase1Encoding ReEncodeFont }17 103.666679 /Times-Bold
rf /FB 198[15 15 15 15 15 15 15 15 15 15 48[{
 TeXBase1Encoding ReEncodeFont }10 29.166668 /Times-Roman
rf end
%%EndProlog
%%BeginSetup
%%Feature: *Resolution 300dpi
TeXDict begin

%%EndSetup
%%Page: 1 1
1 0 bop 2017 -139 a FB(1)192 40 y FA(T)-8 b(radeoffs)27
b(f)m(or)f(P)o(ack)o(et)g(Classi\002cation)428 139 y
Fz(Anja)13 b(Feldmann)378 b(S.)13 b(Muthukrishnan)727
220 y(A)-6 b(T&T)14 b(Labs\226Research)775 278 y(Florham)d(P)o(ark,)h
(NJ)628 336 y Fy(f)p Fz(anja,muthu)p Fy(g)p Fz(@research.att.com)-88
473 y Fx(Abstract)q Fw(\227)t(W)n(e)c(pr)o(esent)i(an)g(algorithmic)f
(framework)f(f)o(or)h(solving)h(the)g(packet)-130 511
y(classi\002cation)d(pr)o(oblem)h(that)f(allows)g(various)f(access)g
(time)h(vs.)g(memory)e(tradeoffs.)-130 549 y(It)k(r)o(educes)h(the)g
(multi-dimensional)g(packet)f(classi\002cation)g(pr)o(oblem)h(to)f
(solving)g(a)-130 588 y(few)h(instances)h(of)f(the)g(one-dimensional)h
(IP)g(lookup)g(pr)o(oblem.)17 b(It)10 b(gives)f(the)h(best)-130
626 y(known)e(lookup)g(perf)o(ormance)e(with)i(moderately)e(large)f
(memory)h(space.)j(Further)o(-)-130 664 y(mor)o(e,)e(it)h
(ef\002ciently)f(supports)h(a)f(r)o(easonable)g(number)h(of)f
(additions)h(and)g(deletions)-130 702 y(to)13 b(the)g(rulesets)g
(without)g(degrading)g(the)h(lookup)f(perf)o(ormance.)24
b(W)n(e)12 b(perf)o(orm)-130 740 y(a)i(thor)o(ough)g(experimental)g
(study)g(of)g(the)g(tradeoffs)g(f)o(or)f(the)i(two-dimensional)-130
779 y(packet)e(classi\002cation)g(pr)o(oblem)g(on)h(rulesets)e(derived)
h(fr)o(om)g(datasets)f(collected)-130 817 y(fr)o(om)c(A)m(T&T)g(W)n
(orldNet,)g(an)g(Internet)g(Service)g(Pr)o(ovider)m(.)236
933 y Fu(I)r(.)23 b(I)r Fv(N)r(T)r(R)q(O)r(D)r(U)r(C)r(T)r(I)r(O)r(N)
-88 1007 y Fu(While)16 b(the)h(current)g(Internet)f(of)o(fers)h
(best-ef)o(fort)f(service,)j(future)-130 1057 y(IP)14
b(networks)f(will)g(pro)o(vide)g(enhanced)i(services)f(to)g(its)f
(users.)25 b(Such)-130 1106 y(services)c(may)f(include)f(dif)o
(ferentiated)g(services)h(underwritten)e(by)-130 1155
y(service)d(le)o(v)o(el)g(agreements)g(\(SLA)-5 b(')n(s\),)16
b(\002ne)f(grain)e(quality)g(of)h(service)-130 1205 y(\(QoS\),)e(V)n
(irtual)e(Pri)o(v)o(ate)i(Network)f(\(VPN\))g(service,)j(distrib)o
(uted)9 b(\002re-)-130 1254 y(walls,)k(IP)g(security)g(gate)o(ways,)h
(traf)o(\002c)f(based)h(billing,)d(etc.)22 b(All)12 b(such)-130
1304 y(enhancements)18 b(need)g Ft(pac)o(ket)f(classi\002cation)p
Fu(,)g(that)f(is,)j(determining)-130 1353 y(which)13
b(\003o)o(w)f(a)i(packet)f(belongs)f(to)g(based)i(on)e(one)h(or)g(more)
g(\002elds)g(in)-130 1402 y(the)j(packet)f(header)n(.)30
b(P)o(acket)17 b(header)f(\002elds)g(that)f(may)h(be)g(used)g(for)-130
1452 y(classi\002cation)g(include)e(the)i(destination)e(and)h(source)i
(IP)e(addresses,)-130 1501 y(the)c(protocol)f(type,)i(and)f(the)h
(source)g(and)f(destination)f(port)g(numbers.)-130 1551
y(Rules)h(for)g(classi\002cation)h(are)g(speci\002ed)h(by)e(specifying)
g(v)o(alid)f(ranges)-130 1600 y(for)j(an)o(y)h(of)g(the)f(header)i
(\002elds.)23 b(Determining)13 b(the)g(most)h(\002tting)e(rule)-130
1649 y(for)e(each)h(packet)g(is)f(the)g(packet)g(classi\002cation)g
(problem.)-130 1702 y Fs(Examples)17 b(of)h(packet)h(classi\002cation:)
27 b Fu(In)18 b(today')n(s)f(IP)h(networks,)-130 1751
y(packet)12 b(classi\002cation)h(for)e(routing)g(is)h(based)h(purely)e
(on)h(the)g(destina-)-130 1801 y(tion)g(IP)i(address,)i(and)d(the)h
(rules)f(are)i(e)o(xpressed)f(as)h(IP)e(address)i(pre-)-130
1850 y(\002x)o(es.)30 b(P)o(acket)16 b(classi\002cation)g(rules)f(for)g
(access)j(lists)c(and)i(\002re)o(walls)-130 1899 y(use)8
b(two)f(IP)h(pre\002x)o(es)h(\226)e(source)i(and)f(destination)e(IP)i
(address)g(pre\002x)o(es)h(\226)-130 1949 y(and)g(sometimes)g
(conditions)e(on)h(the)g(port)g(numbers)h(and)f(protocols.)k(IP)-130
1998 y(networks)e(that)h(use)g(impro)o(v)o(ed)h(traf)o(\002c)f
(engineering)f(and)i(support)e(dif-)-130 2048 y(ferentiated)e(services)
g(may)h(use)f(one)g(set)g(of)g(packet)g(classi\002cation)g(rules)-130
2097 y(to)g(determine)h(which)g(router)f(to)g(forward)g(a)h(packet)g
(\(using)e(MPLS)j(tun-)-130 2146 y(nels\))j(and)g(another)f(set)h(of)g
(rules)g(to)f(determine)h(which)g(queue)g(to)f(use)-130
2196 y(\(for)j(dif)o(ferentiated)g(service\))h(and)g(yet)f(another)g
(set)h(of)g(rules)f(to)h(de-)-130 2245 y(cided)f(whether)g(to)g
(forward)f(a)i(packet)f(\(for)g(VPNs)h(and)f(IP)g(security)-130
2295 y(gate)o(ways\).)34 b(Such)17 b(rules)g(are)h(likely)d(to)i(be)h
(based)f(on)g(at)g(least)h(the)-130 2344 y(source)d(and)f(destination)f
(IP)h(addresses)i(b)o(ut)e(may)h(also)f(include)g(port)-130
2393 y(numbers)13 2378 y FB(1)30 2393 y Fu(.)-130 2446
y Fs(Requir)o(ements)d(f)o(or)f(packet)g(classi\002cation:)h
Fu(The)o(y)g(can)f(v)o(ary)g(widely)-130 2495 y(depending)h(on)g(the)g
(application)f(and)i(where)g(packet)f(classi\002cation)h(is)-130
2545 y(performed)e(in)g(the)g(network.)-130 2597 y Fr(\017)e
Ft(Resour)n(ce)i(limitations:)e Fu(P)o(acket)h(classi\002cation)f
(solutions)e(can)j(trade-)-130 2646 y(of)o(f)17 b(time)g(to)f(perform)h
(the)g(classi\002cation)g(per)h(packet)f(vs.)g(memory)-103
2726 y Fq(1)-86 2738 y Fv(Any)9 b(communication)f(that)i(uses)f(IP-Sec)
i(encryption)d(will)j(not)f(expose)e(port)h(num-)-130
2775 y(bers.)k(Therefore)8 b(relying)h(on)f(the)h(a)o(v)o(ailability)h
(of)f(port)g(numbers)e(in)i(backbone)e(IP)j(net-)-130
2811 y(works)d(may)h(be)f(problematic.)975 473 y Fu(used.)29
b(At)14 b(lar)o(ge)i(corporate)f(campuses,)k(access)e(speeds)f(may)g
(range)975 522 y(from)10 b(medium)h(speed)g(of)f(T)p
Fp(3)h Fu(and)f(OC)p Fp(3)p Fu(,)g(to)g(top)g(speeds)h(of)f(OC)p
Fp(12)g Fu(and)975 572 y(abo)o(v)o(e.)k(At)9 b(inter)f(ISP)i
(boundaries,)f(the)g(access)i(speeds)f(will)e(be)i(OC)p
Fp(12)p Fu(,)975 621 y(OC)p Fp(48)p Fu(,)h(and)g(abo)o(v)o(e.)17
b(Residential)11 b(customers)g(ha)o(v)o(e)i(access)g(speeds)f(of)975
671 y(T)p Fp(1)h Fu(\(DSL\))g(or)f(less.)20 b(Solutions)11
b(should)g(achie)o(v)o(e)j(the)f(required)f(tar)o(get)975
720 y(access)g(speed,)g(while)d(minimizing)g(the)h(amount)g(of)g
(memory)h(used.)975 774 y Fr(\017)h Ft(Number)f(of)h(rules)g(to)f(be)h
(supported:)j Fu(P)o(acket)e(classi\002cation)f(appli-)975
823 y(cations)i(dif)o(fer)f(in)g(the)h(number)f(of)h(rules)f(that)h
(are)g(speci\002ed.)25 b(T)m(oday)975 873 y(typical)11
b(\002re)o(walls)h(may)g(specify)g(a)h(fe)o(w)f(hundred)f(rules,)i
(while)e(an)i(ac-)975 922 y(cess/backbone)f(router)f(may)g(ha)o(v)o(e)i
(a)f(fe)o(w)f(hundreds)g(of)g(thousands)f(of)975 972
y(rules;)f(these)g(numbers)g(are)g(e)o(xpected)h(to)e(scale)i(up)f
(with)e(enhanced)j(ser)o(-)975 1021 y(vices)h(and)f(router)g
(throughput)d(and)j(may)h(reach)h(millions)c(of)i(rules.)975
1075 y Fr(\017)f Ft(Number)f(of)g(\002elds)h(used:)j
Fu(P)o(acket)d(classi\002cation)g(applications)e(dif)o(fer)975
1124 y(on)h(the)g(number)g(of)g(\002elds)g(\()p Ft(dimensions)p
Fu(\))f(of)h(the)g(IP)g(header)h(that)e(is)h(used)975
1174 y(for)13 b(classi\002cation.)22 b(Current)13 b(routers)f(use)i
(one)g(\002eld)f(\(destination)f(IP)975 1223 y(address\),)i(b)o(ut)e
(it)g(is)h(e)o(xpected)g(that)f(emer)o(ging)h(routers)f(will)g(use)h
(two-)975 1272 y(dimensional)g(rules.)23 b(Fire)o(walls)13
b(and)h(other)f(access)j(list)d(applications)975 1322
y(may)e(use)g(a)f(fe)o(w)h(more)g(\002elds)f([9].)975
1376 y Fr(\017)i Ft(Natur)n(e)g(of)f(rules:)17 b Fu(Current)11
b(routers)g(use)h(rules)g(with)f(a)i(pre\002x)f(mask)975
1425 y(on)d(destination)f(IP)i(addresses.)k(Ho)o(we)o(v)o(er)n(,)d
(more)f(general)g(masks)g(such)975 1475 y(as)i(arbitrary)f(ranges)h
(are)h(e)o(xpected)g(to)e(become)i(permissible.)k(P)o(acket)975
1524 y(classi\002cation)9 b(solutions)e(need)i(to)f(accommodate)j(such)
e(general)g(spec-)975 1573 y(i\002cation.)975 1627 y
Fr(\017)h Ft(Updating)f(the)h(set)h(of)f(rules:)j Fu(The)e(number)f(of)
g(changes)i(to)e(the)g(rules)975 1677 y(either)g(due)g(to)f(a)i(route)e
(or)h(polic)o(y)f(change)h(is)g(moderate)h(to)e(small)h(com-)975
1726 y(pared)g(to)e(the)h(number)g(of)g(packets)h(that)e(an)i
(application,)e(e.g.,)j(a)f(router)n(,)975 1776 y(needs)18
b(to)e(classify)h(in)f(the)h(same)h(time)f(period.)32
b(P)o(acket)17 b(classi\002ca-)975 1825 y(tion)8 b(solutions)f(must)i
(adapt)g(gracefully)g(and)g(quickly)f(to)g(such)i(updates)975
1874 y(without)j(sacri\002cing)h(the)h(access)h(performance.)27
b(Reb)o(uilding)13 b(major)975 1924 y(parts)d(of)g(the)g(data)h
(structure)e(for)h(e)o(v)o(ery)h(update)f(is)g(prohibiti)o(v)o(e.)975
1978 y Fr(\017)g Ft(W)l(orst)g(case)h(vs.)h(A)n(ver)o(age)f(case:)j
Fu(There)e(is)e(a)h(widely)f(held)g(vie)o(w)g(that)975
2027 y(for)j(access)i(time)f(performance)g(of)f(packet)g
(classi\002cation,)h(one)g(must)975 2077 y(focus)c(on)g(worst)f(case,)k
(rather)d(than)g(a)o(v)o(erage)i(case)f([11].)1017 2164
y(Man)o(y)i(of)f(these)h(requirements)g(ha)o(v)o(e)h(been)f
(articulated)f(in)g(the)h(e)o(x-)975 2214 y(tensi)o(v)o(e)d(collection)
g(of)g(papers)g(that)g(ha)o(v)o(e)h(addressed)h(the)e(packet)g(clas-)
975 2263 y(si\002cation)15 b(problem)h([1],)i([9],)f([8],)g([11],)h
([12],)f([14],)g([15])f(and)g(the)975 2313 y(references)e(therein.)20
b(Se)o(v)o(eral)13 b(solutions)e(ha)o(v)o(e)j(been)f(proposed;)g(the)o
(y)975 2362 y(are)e(ef)o(fecti)o(v)o(e)f(in)g(meeting)g(some)h(of)e
(the)h(criteria,)g(b)o(ut)g(not)f(all)g(of)h(them.)975
2411 y(Some)j(of)f(them)g(do)f(not)h(allo)o(w)f(range)h
(speci\002cation)g(in)g(the)g(rules)g([8],)975 2461 y(others)h(do)g
(not)f(preserv)o(e)i(the)f(access)i(time)f(performance)g(with)e(guar)o
(-)975 2510 y(anteed)g(small)f(update)g(times)g([9],)g([11],)g([15],)g
(and)g(yet)g(others)g(are)g(not)975 2560 y(designed)i(for)h(lar)o(ge)g
(rulesets)f([12],)h([14].)23 b(It)13 b(is)h(desirable)f(to)g(ha)o(v)o
(e)i(a)975 2609 y(suite)c(of)h(solutions)e(with)h(a)h(range)h(of)e
(tradeof)o(fs)h(that)f(can)i(be)f(tuned)f(to)975 2658
y(particular)e(applications.)975 2712 y Fs(Our)i(contrib)o(utions:)i