Poptrie:)A)Compressed)Trie)with)
Popula5on)Count)for)Fast)and)Scalable)
So<ware)IP)Rou5ng)Table)Lookup
Hirochika)Asai)(The...
Brief)Summary)of)Poptrie
•  Mul5way)trie)for)IP)rou5ng)table)lookup)in)
so<ware)
– Small)memory)footprint)with)popula5on)c...
IP)Rou5ng)Table)Lookup
•  Principle)
– Longest)prefix)match)
•  Challenges)
1.  Large)and)growing)rou5ng)table)
•  IPv4:)50...
Radix)Tree)(Revisited)
Aug.)18,)2015
Poptrie:)A)Compressed)Trie)with)Popula5on)Count)
for)Fast)and)Scalable)So<ware)IP)Rou...
Related)Work:)Fast)IP)Rou5ng)Table)
Lookup)Algorithms
Approach Feature
Tree)BitMap)[1] Trie)(partly)
mul5way)
Succinct)dat...
Key)Ideas)for)High)Lookup)Rate
1.  Reduce)instruc5ons)including)memory)access)
– Reduce)the)lookup)depth)of)the)trie)
2.  ...
At)a)Glance:)Radix)Tree
0.0.0.0
255.255.255.255 128.0.0.0
Root
mul5cast/reserved)
/24 /16
Aug.)18,)2015
(*))IPv4)Rou5ng)ta...
At)a)Glance:)Poptrie
0.0.0.0
255.255.255.255 128.0.0.0
mul5cast/reserved)
/24
Aug.)18,)2015
(*))IPv4)Rou5ng)table)from)
an...
Poptrie
•  Basic)algorithm)
– Mul5way)trie)
– Pointer)compression)with)popula5on)count)
•  Extensions)
– Compression)with)...
Poptrie
•  Basic&algorithm&
– Mul5way)trie)
– Pointer)compression)with)popula5on)count)
•  Extensions)
– Compression)with)...
Poptrie)(basic):)2kVary)Mul5way)Trie
Aug.)18,)2015
Poptrie:)A)Compressed)Trie)with)Popula5on)Count)
for)Fast)and)Scalable)...
b
Poptrie)(basic):)Pointer)Compression)
with)Popula5on)Count)(1/2)
Aug.)18,)2015
Poptrie:)A)Compressed)Trie)with)Popula5on...
b
Poptrie)(basic):)Pointer)Compression)
with)Popula5on)Count)(2/2)
Aug.)18,)2015
Poptrie:)A)Compressed)Trie)with)Popula5on...
Poptrie
•  Basic)algorithm)
– Mul5way)trie)
– Pointer)compression)with)popula5on)count)
•  Extensions&
– Compression)with)...
Poptrie:)Compression)with)LeafVVector
Aug.)18,)2015
Poptrie:)A)Compressed)Trie)with)Popula5on)Count)
for)Fast)and)Scalable...
Poptrie:)Compression)with)LeafVVector
Aug.)18,)2015
Poptrie:)A)Compressed)Trie)with)Popula5on)Count)
for)Fast)and)Scalable...
Poptrie:)Route)Aggrega5on
Aug.)18,)2015
Poptrie:)A)Compressed)Trie)with)Popula5on)Count)
for)Fast)and)Scalable)So<ware)IP)...
Poptrie:)Direct)Poin5ng
Aug.)18,)2015
Poptrie:)A)Compressed)Trie)with)Popula5on)Count)
for)Fast)and)Scalable)So<ware)IP)Ro...
Implementa5on
•  Data)size)
– Internal)node)(with)leafvec):)24)bytes)
•  vector,)leafvec:)8)bytes)(k=6))
•  base0,)base1:)...
Evalua5ons
•  Effect)of)Extensions)in)Poptrie)
•  Mul5core)Scalability)
•  Comparison)with)Other)Algorithms)
–  Average)loo...
Effect)of)Extensions)in)Poptrie
Algorithm&/&
Extensions
s #&of&internal&
nodes
#&of&leaves Memory&
[MiB]&
Rate&[Mlps]
Radix...
Comparison)with)Other)Algorithms)
(for)random)traffic)pasern)
Algorithm Memory&[MiB] Rate&[Mlps]
Radix 30.48 8.82
Tree)BitMa...
PerVLookup)Performance)Analysis
Aug.)18,)2015
Poptrie:)A)Compressed)Trie)with)Popula5on)Count)
for)Fast)and)Scalable)So<wa...
PerVLookup)Performance)Analysis:)
Cumula5ve)Distribu5on)of)CPU)Cycles
Aug.)18,)2015
Poptrie:)A)Compressed)Trie)with)Popula...
PerVLookup)Performance)Analysis:)
Binary)Radix)Depth
Aug.)18,)2015
Poptrie:)A)Compressed)Trie)with)Popula5on)Count)for)Fas...
PerVLookup)Performance)
at)Different)Binary)Radix)Depth
Aug.)18,)2015
Poptrie:)A)Compressed)Trie)with)Popula5on)Count)
for)...
PerVLookup)Performance)
at)Different)Binary)Radix)Depth
Aug.)18,)2015
Poptrie:)A)Compressed)Trie)with)Popula5on)Count)
for)...
Rou5ng)table:)Backbone)core)router)of)5erV1)ISP)(Jan.)9,)2015)
PerVLookup)Performance)
at)Different)Binary)Radix)Depth
Aug....
Average)Lookup)Rate:)
Random)vs.)Real)Traffic
Aug.)18,)2015
Poptrie:)A)Compressed)Trie)with)Popula5on)Count)
for)Fast)and)Sc...
Performance)on)Large)Rou5ng)Tables
Algorithm SYN1&(with&764,847&routes) SYN2&(with&885,645&routes)
SAIL 102.86)Mlps N/A)(O...
Conclusion
•  Poptrie:)Mul5way)trie)for)IP)rou5ng)table)
lookup)in)so<ware)
– Small)memory)footprint)with)popula5on)count)...
BACKUP&SLIDES
Aug.)18,)2015
Poptrie:)A)Compressed)Trie)with)Popula5on)Count)
for)Fast)and)Scalable)So<ware)IP)Rou5ng)Table...
Tree)BitMap:)Succinct)Data)Structure
Aug.)18,)2015
Poptrie:)A)Compressed)Trie)with)Popula5on)Count)for)Fast)and)
Scalable)...
SAIL:)3Vlevel)Mul5way)Trie
Aug.)18,)2015
Poptrie:)A)Compressed)Trie)with)Popula5on)Count)for)Fast)and)
Scalable)So<ware)IP...
DXR:)Binary)Search)in)Range)Table
Aug.)18,)2015
Poptrie:)A)Compressed)Trie)with)Popula5on)Count)for)Fast)and)
Scalable)So<...
LockVfree)Update)Procedure
Internal node
1 1 0 0
vector base0
N[2048] N[2049] N[2050]
31290 0 0 1
leafvec base1
2048
N
L
1...
Mul5core)Scalability)Evalua5on)for)
Random)Traffic
Aug.)18,)2015
Poptrie:)A)Compressed)Trie)with)Popula5on)Count)for)Fast)an...
Performance)on)IPv6)Rou5ng)Table
Aug.)18,)2015
Poptrie:)A)Compressed)Trie)with)Popula5on)Count)
for)Fast)and)Scalable)So<w...
of 38

Poptrie: A Compressed Trie with Population Count for Fast and Scalable Software IP Routing Table Lookup

Presented in SIGCOMM 2015.
Published on: Mar 4, 2016
Published in: Presentations & Public Speaking      
Source: www.slideshare.net


Transcripts - Poptrie: A Compressed Trie with Population Count for Fast and Scalable Software IP Routing Table Lookup

  • 1. Poptrie:)A)Compressed)Trie)with) Popula5on)Count)for)Fast)and)Scalable) So<ware)IP)Rou5ng)Table)Lookup Hirochika)Asai)(The)University)of)Tokyo)) Yasuhiro)Ohara)(NTT)Communica5ons)Corpora5on)) ) ACM)SIGCOMM)2015,)Aug.)18,)2015
  • 2. Brief)Summary)of)Poptrie •  Mul5way)trie)for)IP)rou5ng)table)lookup)in) so<ware) – Small)memory)footprint)with)popula5on)count) •  e.g.,)2.4)MiB)for)a)global)5erV1)ISP’s)full)route) – Good)performance)through)comprehensive) evalua5on) •  4–578%)faster)than)other)stateVofVtheVart)technologies) –  Private)and)public)IPv4/IPv6)rou5ng)tables) –  FutureVenvisioned)800K+)IPv4)routes) •  Advantageous)for)longer)prefixes) –  demonstrated)through)perVlookup)performance)analysis) Aug.)18,)2015 Poptrie:)A)Compressed)Trie)with)Popula5on)Count) for)Fast)and)Scalable)So<ware)IP)Rou5ng)Table)Lookup
  • 3. IP)Rou5ng)Table)Lookup •  Principle) – Longest)prefix)match) •  Challenges) 1.  Large)and)growing)rou5ng)table) •  IPv4:)500K+)entries) •  IPv6:)20K+)entries) 2.  High)lookup)rate)requirement) •  e.g.,)148.8)Mpps)!)6.7)ns)per)lookup) (at)the)wireVrate)on)100)GbE)of)minimumVsize)frames))) Aug.)18,)2015 Poptrie:)A)Compressed)Trie)with)Popula5on)Count) for)Fast)and)Scalable)So<ware)IP)Rou5ng)Table)Lookup
  • 4. Radix)Tree)(Revisited) Aug.)18,)2015 Poptrie:)A)Compressed)Trie)with)Popula5on)Count) for)Fast)and)Scalable)So<ware)IP)Rou5ng)Table)Lookup d c b 0 1 e 0 1 a 0 0.0.0.0/0 128.0.0.0/1 0.0.0.0/2 64.0.0.0/2 64.0.0.0/3 Radix&Tree&Example Problems)with)the)radix)tree) •  Depth)up)to)32)(for)IPv4)) •  requires)a)number)of) memory)access) •  Large)memory)footprint) due)to)many)pointers) •  causes)CPU)cache)misses) ")Bad&performance) Prefix)length) =)Priority Prefix Fundamental)data)structure)and)algorithm)for)longest)prefix)match
  • 5. Related)Work:)Fast)IP)Rou5ng)Table) Lookup)Algorithms Approach Feature Tree)BitMap)[1] Trie)(partly) mul5way) Succinct)data)structure)within) CPU)cache)size SAIL)[2] Trie)(mul5way) Op5mized)mul5Vlevel)trie)(3V level)for)IPv4) DXR)[3] Range Small)memory)footprint)and) high)L1)cache)efficiency Aug.)18,)2015 Poptrie:)A)Compressed)Trie)with)Popula5on)Count) for)Fast)and)Scalable)So<ware)IP)Rou5ng)Table)Lookup [1])W.)Eatherton)et)al.,)“Tree)Bitmap:)Hardware/So<ware)IP)Lookups)with)Incremental)Updates,”)ACM)SIGCOMM)CCR,)2004) [2])T.)Yang)et)al.,)“Guarantee)IP)Lookup)Performance)with)FIB)Explosion,”)ACM)SIGCOMM)2014) [3])M.)Zec)et)al.,)“DXR:)Towards)a)Billion)Rou5ng)Lookups)Per)Second)in)So<ware,”)ACM)SIGCOMM)CCR,)2012)
  • 6. Key)Ideas)for)High)Lookup)Rate 1.  Reduce)instruc5ons)including)memory)access) – Reduce)the)lookup)depth)of)the)trie) 2.  Increase)CPU)cache)efficiency) – Compress)the)data)structure)for)small)memory) footprint)within)CPU)cache)size) Aug.)18,)2015 Poptrie:)A)Compressed)Trie)with)Popula5on)Count) for)Fast)and)Scalable)So<ware)IP)Rou5ng)Table)Lookup Poptrie& V  Extended)from)the)mul5way)trie)) V  Compressed)with)popula5on)count)(CPU)instruc5on))
  • 7. At)a)Glance:)Radix)Tree 0.0.0.0 255.255.255.255 128.0.0.0 Root mul5cast/reserved) /24 /16 Aug.)18,)2015 (*))IPv4)Rou5ng)table)from) an)AS)border)router)of) WIDE)Project)(Jan.)3,)2015)
  • 8. At)a)Glance:)Poptrie 0.0.0.0 255.255.255.255 128.0.0.0 mul5cast/reserved) /24 Aug.)18,)2015 (*))IPv4)Rou5ng)table)from) an)AS)border)router)of) WIDE)Project)(Jan.)3,)2015) Root
  • 9. Poptrie •  Basic)algorithm) – Mul5way)trie) – Pointer)compression)with)popula5on)count) •  Extensions) – Compression)with)leaf)bitVvector) – Route)aggrega5on) – Direct)poin5ng Aug.)18,)2015 Poptrie:)A)Compressed)Trie)with)Popula5on)Count) for)Fast)and)Scalable)So<ware)IP)Rou5ng)Table)Lookup
  • 10. Poptrie •  Basic&algorithm& – Mul5way)trie) – Pointer)compression)with)popula5on)count) •  Extensions) – Compression)with)leaf)bitVvector) – Route)aggrega5on) – Direct)poin5ng Aug.)18,)2015 Poptrie:)A)Compressed)Trie)with)Popula5on)Count) for)Fast)and)Scalable)So<ware)IP)Rou5ng)Table)Lookup
  • 11. Poptrie)(basic):)2kVary)Mul5way)Trie Aug.)18,)2015 Poptrie:)A)Compressed)Trie)with)Popula5on)Count) for)Fast)and)Scalable)So<ware)IP)Rou5ng)Table)Lookup d c b 0 1 e 0 1 a 0 0.0.0.0/0 128.0.0.0/1 64.0.0.0/2 64.0.0.0/3 Radix&Tree b c c a a e e Internal)node Leaf)node 00 01 10 11 00 01 10 11 2k=ary&Mul@way&Trie&(k=2) Push)the)next)hop)informa5on)in)the)internal)nodes) to)leaf)nodes 0.0.0.0/2 X)X)X)X)X)X Key)IP)address MSB 00 01 10 11 chunk
  • 12. b Poptrie)(basic):)Pointer)Compression) with)Popula5on)Count)(1/2) Aug.)18,)2015 Poptrie:)A)Compressed)Trie)with)Popula5on)Count) for)Fast)and)Scalable)So<ware)IP)Rou5ng)Table)Lookup 0 1 0 0 vector)† b Internal)node pointer pointer base0 base1 c c b 0 0 0 0 vector pointer pointer base0 base1 Internal)node Array)of)descendant) internal)nodes Array)of)descendant) leaf)nodes 00 01 10 11 b c c a a e e Internal)node Leaf)node 00 01 10 11 00 01 10 11 2k=ary&Mul@way&Trie&(k=2) Pointer&compression&with&bit=vector&and&array †)in)lisle)endian 00 01 10 11
  • 13. b Poptrie)(basic):)Pointer)Compression) with)Popula5on)Count)(2/2) Aug.)18,)2015 Poptrie:)A)Compressed)Trie)with)Popula5on)Count) for)Fast)and)Scalable)So<ware)IP)Rou5ng)Table)Lookup 0 1 0 0 vector)† b Internal)node pointer pointer base0 base1 c c Internal Leaf 00 01 10 11 Pointer&compression&with&bit=vector&and&array b 0 1 0 0 vector)† b Internal)node pointer pointer base0 base1 c c Internal Leaf Array&compression&with&popula@on&count †)in)lisle)endian Index:)#)of)1’s)bits)in)the)least) significant)N+1)bits)of)vector)(V1) Index:)#)of)0’s)bits)in)the)least) significant)N+1)bits)of)vector)(V1) Coun5ng)#)of)1s:)Use)x86’s)popcnt)instruc5on N:)Value)of)the)chunk N= 00 01 10 11 00 01 10 11N=
  • 14. Poptrie •  Basic)algorithm) – Mul5way)trie) – Pointer)compression)with)popula5on)count) •  Extensions& – Compression)with)leaf)bitVvector) – Route)aggrega5on) – Direct)poin5ng Aug.)18,)2015 Poptrie:)A)Compressed)Trie)with)Popula5on)Count) for)Fast)and)Scalable)So<ware)IP)Rou5ng)Table)Lookup
  • 15. Poptrie:)Compression)with)LeafVVector Aug.)18,)2015 Poptrie:)A)Compressed)Trie)with)Popula5on)Count) for)Fast)and)Scalable)So<ware)IP)Rou5ng)Table)Lookup d c b 0 1 e 0 1 a 0 0.0.0.0/0 128.0.0.0/1 64.0.0.0/2 64.0.0.0/3 Radix&Tree b c c a a e e Internal)node Leaf)node 00 01 10 11 00 01 10 11 2k=ary&Mul@way&Trie&(k=2) A)problem)with)the)basic)data)structure:)Redundant)leaf)nodes) V  for)prefixes)that)do)not)match)kVbit)boundary) V  e.g.,)/1)(/7,)etc.)as)well))may)create)32)redundant)leaf)nodes)when)k=6) V  for)holeVpunched)prefixes) 0.0.0.0/2
  • 16. Poptrie:)Compression)with)LeafVVector Aug.)18,)2015 Poptrie:)A)Compressed)Trie)with)Popula5on)Count) for)Fast)and)Scalable)So<ware)IP)Rou5ng)Table)Lookup b 0 1 0 0 vector)† b Internal)node pointer pointer base0 base1 c c Internal Leaf Poptrie&(basic) †)in)lisle)endian b 0 1 0 0 vector)† b Internal)node pointer pointer base0 base1 c c Internal Leaf Poptrie&with&leaf=vector&(leafvec) 1 0 1 0 leafvec)† Index:)#)of)1’s)bits)in)the)least) significant)N+1)bits)of)leafvec'(V1)
  • 17. Poptrie:)Route)Aggrega5on Aug.)18,)2015 Poptrie:)A)Compressed)Trie)with)Popula5on)Count) for)Fast)and)Scalable)So<ware)IP)Rou5ng)Table)Lookup b 0 1 0 0 vector)† b Internal)node pointer pointer base0 base1 c Internal Leaf Poptrie&with&leaf=vector&(leafvec) 1 0 1 0 leafvec)† b 0 1 0 0 vector)† x’ Internal)node pointer pointer base0 base1 Internal Leaf 1 0 0 0 leafvec)† Poptrie&with&route&aggrega@on When)the)next)hop)info.)of)b)and)c)is)iden5cal;) e.g.,) )b:)prefix)0.0.0.0/2,)next)hop)X) )c:)prefix)128.0.0.0/1,)next)hop)X Aggregate)b)and)c)to)x’) (x’:)prefix)aggregated)[0.0.0.0/0],)next)hop)X) †)in)lisle)endian
  • 18. Poptrie:)Direct)Poin5ng Aug.)18,)2015 Poptrie:)A)Compressed)Trie)with)Popula5on)Count) for)Fast)and)Scalable)So<ware)IP)Rou5ng)Table)Lookup Extract)and)lookup)s)bits)at)the)first)stage)(like)other)algorithms)such)as)DXR) 0.0.0.0/18 0.0.64.0/18 192.0.0.0/18 N.B.,)illustrated)the)case)of)s)=)18 0.0.128.0/18 1 1 0 flag:)leaf)(0))or)internal)node)(1) leaf0 pointer pointer leaf TopVlevel)array:)Array)of)length)2s Internal)node Internal)node Poptriex):)Poptrie)with)s'=)x
  • 19. Implementa5on •  Data)size) – Internal)node)(with)leafvec):)24)bytes) •  vector,)leafvec:)8)bytes)(k=6)) •  base0,)base1:)4)bytes) –  Index)in)the)con5guous)array†)instead)of)memory)address) – Leaf)node:)2)bytes) – Direct)poin5ng)entry:)4)bytes) •  Code)in)C:)hsps://github.com/pixos/poptrie) Aug.)18,)2015 Poptrie:)A)Compressed)Trie)with)Popula5on)Count) for)Fast)and)Scalable)So<ware)IP)Rou5ng)Table)Lookup †)The)con5guous)arrays)of)the)internal)and)leaf)nodes)are)managed)by)the)buddy) memory)allocator)to)allocate)an)array)of)descendant)nodes.)
  • 20. Evalua5ons •  Effect)of)Extensions)in)Poptrie) •  Mul5core)Scalability) •  Comparison)with)Other)Algorithms) –  Average)lookup)rate) •  Traffic)pasern:)Sequen5al,)repeated,)random,)real)trace) •  Rou5ng)tables:)3)private,)32)public,)4)synthe5c) –  CPU)cycles)per)lookup) •  Update) •  Performance)in)IPv6 Aug.)18,)2015 Poptrie:)A)Compressed)Trie)with)Popula5on)Count) for)Fast)and)Scalable)So<ware)IP)Rou5ng)Table)Lookup Equipment)for)the)evalua5ons:) Intel(R))Core)i7)4770K)(3.9)GHz,)8)MiB)cache)) with)four)8)GB)DDR3V1866)RAM) (using)a)single)core))
  • 21. Effect)of)Extensions)in)Poptrie Algorithm&/& Extensions s #&of&internal& nodes #&of&leaves Memory& [MiB]& Rate&[Mlps] Radix – – – 30.48 8.82 Poptrie)(basic)) without)route) aggrega5on 0 64,009 4,032,568 8.67 87.71 16 172,110 10,862,901 23.60 130.72 18 61,282 3,911,422 9.40 170.69 Poptrie)(leafvec)) without)route) aggrega5on 0 64,009 280,673 2.00 89.15 16 172,110 347,449 4.85 154.33 18 61,282 269,320 2.91 191.95 Poptrie 0 43,191 263,381 1.49 96.27 16 86,171 274,145 2.75 198.28 18 40,760 245,034 2.40 240.52 1.)leafvec)significantly)contributes)the)memory)footprint)reduc5on. Rou5ng)table:)Backbone)core)router)of)5erV1)ISP)(Jan.)9,)2015),)Traffic)pasern:)Random 2.)Route)aggrega5on)contributes)to)reduce)the)internal)nodes)(i.e.,)average)depth). Mlps) =)Million)lookups) )))per)second
  • 22. Comparison)with)Other)Algorithms) (for)random)traffic)pasern) Algorithm Memory&[MiB] Rate&[Mlps] Radix 30.48 8.82 Tree)BitMap 2.62 56.24 Tree)BitMap)(64Vary) 3.10 61.61 SAIL 44.24 158.22 D16R 1.16 116.63 D18R 1.91 179.92 Poptrie16 2.75 198.28 Poptrie18 2.40 240.52 Aug.)18,)2015 Poptrie:)A)Compressed)Trie)with)Popula5on)Count) for)Fast)and)Scalable)So<ware)IP)Rou5ng)Table)Lookup Rou5ng)table:)Backbone)core)router)of)5erV1)ISP)(Jan.)9,)2015),)Traffic)pasern:)Random Poptrie18)runs)1.34–27.3x)faster)than)the)other)algorithms
  • 23. PerVLookup)Performance)Analysis Aug.)18,)2015 Poptrie:)A)Compressed)Trie)with)Popula5on)Count) for)Fast)and)Scalable)So<ware)IP)Rou5ng)Table)Lookup Performance)evalua5on)machine) with)my)singleVtask)opera5ng)system c0)=)rdpmc() c1)=)rdpmc() r)=)lookup(key) key)=)recv() send(r,)c1)V)c0) Rx Tx NIC UDP) header key UDP) header r,)c1)V)c0 Linux)machine rdpmc):)read)performance)monitoring)counter) (i.e.,)CPU)cycles)) UDP)packet UDP)packet Measured)CPU)cycles)(c1)V)c0)) for)224)random)keys) (with)the)same)random)seed) for)different)algorithms))
  • 24. PerVLookup)Performance)Analysis:) Cumula5ve)Distribu5on)of)CPU)Cycles Aug.)18,)2015 Poptrie:)A)Compressed)Trie)with)Popula5on)Count)for)Fast)and) Scalable)So<ware)IP)Rou5ng)Table)Lookup 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 50 100 150 200 250 300 350 CDF CPU cycles per lookup Poptrie18 D18R Poptrie16 D16R SAIL It)is)worth)to)analyze)perVlookup)performance)than)the)average!
  • 25. PerVLookup)Performance)Analysis:) Binary)Radix)Depth Aug.)18,)2015 Poptrie:)A)Compressed)Trie)with)Popula5on)Count)for)Fast)and) Scalable)So<ware)IP)Rou5ng)Table)Lookup d c b 0 10 1 a 0 0.0.0.0/0 128.0.0.0/1 64.0.0.0/3 Radix&Tree 0.0.0.0/2 Binary)radix)depth)=)Search)depth)in)the)radix)tree) •  0.0.0.0/2):)2 •  64.0.0.0/3):)3) •  96.0.0.0/3&:&2&&(matching)0.0.0.0/0)& •  128.0.0.0/1):)1 0 4 8 12 16 20 24 28 32 Prefix length 4 8 12 16 20 24 28 32 Binaryradixdepth 100 101 102 103 104 105 106 10 7 10 8 109 Rou5ng)table:)Backbone)core)router)of)5erV1)ISP)(Jan.)9,)2015)
  • 26. PerVLookup)Performance) at)Different)Binary)Radix)Depth Aug.)18,)2015 Poptrie:)A)Compressed)Trie)with)Popula5on)Count) for)Fast)and)Scalable)So<ware)IP)Rou5ng)Table)Lookup 0 50 100 150 200 250 300 350 2 4 6 8 10 12 14 16 18 20 22 24 26 CPUcyclesperlookup Binary radix depth D16R 0 50 100 150 200 250 300 350 2 4 6 8 10 12 14 16 18 20 22 24 26 CPUcyclesperlookup Binary radix depth D18R 0 50 100 150 200 250 300 350 2 4 6 8 10 12 14 16 18 20 22 24 26 CPUcyclesperlookup Binary radix depth Poptrie16 0 50 100 150 200 250 300 350 2 4 6 8 10 12 14 16 18 20 22 24 26 CPUcyclesperlookup Binary radix depth Poptrie18 0 50 100 150 200 250 300 350 2 4 6 8 10 12 14 16 18 20 22 24 26 CPUcyclesperlookup Binary radix depth SAIL Wicks:)5th/95th)percen5les) Bodies:)25th/75th)percen5les) Internal)bar:)Median (3Vlevel)trie) (RangeVbase) (RangeVbase) Rou5ng)table:)Backbone)core)router)of)5erV1)ISP)(Jan.)9,)2015)
  • 27. PerVLookup)Performance) at)Different)Binary)Radix)Depth Aug.)18,)2015 Poptrie:)A)Compressed)Trie)with)Popula5on)Count) for)Fast)and)Scalable)So<ware)IP)Rou5ng)Table)Lookup 0 50 100 150 200 250 300 350 2 4 6 8 10 12 14 16 18 20 22 24 26 CPUcyclesperlookup Binary radix depth D16R 0 50 100 150 200 250 300 350 2 4 6 8 10 12 14 16 18 20 22 24 26 CPUcyclesperlookup Binary radix depth D18R 0 50 100 150 200 250 300 350 2 4 6 8 10 12 14 16 18 20 22 24 26 CPUcyclesperlookup Binary radix depth Poptrie16 0 50 100 150 200 250 300 350 2 4 6 8 10 12 14 16 18 20 22 24 26 CPUcyclesperlookup Binary radix depth Poptrie18 0 50 100 150 200 250 300 350 2 4 6 8 10 12 14 16 18 20 22 24 26 CPUcyclesperlookup Binary radix depth SAIL Wicks:)5th/95th)percen5les) Bodies:)25th/75th)percen5les) Internal)bar:)Median (3Vlevel)trie) (RangeVbase) (RangeVbase) Rou5ng)table:)Backbone)core)router)of)5erV1)ISP)(Jan.)9,)2015) O(1) O(1) O(1) O(1) O(1) binary)search binary) search 2nd)level
  • 28. Rou5ng)table:)Backbone)core)router)of)5erV1)ISP)(Jan.)9,)2015) PerVLookup)Performance) at)Different)Binary)Radix)Depth Aug.)18,)2015 Poptrie:)A)Compressed)Trie)with)Popula5on)Count) for)Fast)and)Scalable)So<ware)IP)Rou5ng)Table)Lookup 0 50 100 150 200 250 300 350 2 4 6 8 10 12 14 16 18 20 22 24 26 CPUcyclesperlookup Binary radix depth D16R 0 50 100 150 200 250 300 350 2 4 6 8 10 12 14 16 18 20 22 24 26 CPUcyclesperlookup Binary radix depth D18R 0 50 100 150 200 250 300 350 2 4 6 8 10 12 14 16 18 20 22 24 26 CPUcyclesperlookup Binary radix depth Poptrie16 0 50 100 150 200 250 300 350 2 4 6 8 10 12 14 16 18 20 22 24 26 CPUcyclesperlookup Binary radix depth Poptrie18 0 50 100 150 200 250 300 350 2 4 6 8 10 12 14 16 18 20 22 24 26 CPUcyclesperlookup Binary radix depth SAIL Wicks:)5th/95th)percen5les) Bodies:)25th/75th)percen5les) Internal)bar:)Median ≤)172)cycles >)234)cycles
  • 29. Average)Lookup)Rate:) Random)vs.)Real)Traffic Aug.)18,)2015 Poptrie:)A)Compressed)Trie)with)Popula5on)Count) for)Fast)and)Scalable)So<ware)IP)Rou5ng)Table)Lookup 0 50 100 150 200 250 300 350 Tree BitMap SAIL D16R Poptrie16 D18R Poptrie18 Lookuprate[Mlps] Data Structure and Algorithm 0 50 100 150 200 250 300 350 Tree BitMap SAIL D16R Poptrie16 D18R Poptrie18 Lookuprate[Mlps] Data Structure and Algorithm For)random)traffic For)real)traffic (*))Rou5ng)table)is)dumped)at)an)AS)border)router)of)WIDE)project,) and)traffic)trace)is)captured)at)the)transit)link)of)the)router. Good)for) repeated)paserns Not)good)for)longer) prefixes)(IGP)routes) Bad)for)random Binary&radix&depth Random Real >18 22.1% 32.5% >24 1.7% 21.8% Many)packets) go)to)IGP)routes.
  • 30. Performance)on)Large)Rou5ng)Tables Algorithm SYN1&(with&764,847&routes) SYN2&(with&885,645&routes) SAIL 102.86)Mlps N/A)(Overflowed) D18R)(modified) 115.45)Mlps 102.59)Mlps Poptrie18 188.02)Mlps 174.42)Mlps Aug.)18,)2015 Poptrie:)A)Compressed)Trie)with)Popula5on)Count) for)Fast)and)Scalable)So<ware)IP)Rou5ng)Table)Lookup SYN1:) •  /0V15):)split)into)four)prefixes) •  /16V23):)split)into)two)prefixes) SYN2:) •  /0V15):)split)into)eight)prefixes) •  /16V19):)split)into)four)prefixes) •  /20V23):)split)into)two)prefixes) Two)synthe5c)datasets)from)the)rou5ng)table)of)a)backbone) core)router)of)5erV1)ISP Poptrie18)is)1.63–1.70x)faster)than)D18R.) Traffic)pasern:)Random
  • 31. Conclusion •  Poptrie:)Mul5way)trie)for)IP)rou5ng)table) lookup)in)so<ware) – Small)memory)footprint)with)popula5on)count) •  e.g.,)2.4)MiB)for)a)global)5erV1)ISP’s)full)route) – Good)performance)through)comprehensive) evalua5on) •  4–578%)faster)than)other)stateVofVtheVart)technologies) –  Private)and)public)IPv4/IPv6)rou5ng)tables) –  FutureVenvisioned)800K+)IPv4)routes) •  Advantageous)for)longer)prefixes) –  demonstrated)through)perVlookup)performance)analysis) Aug.)18,)2015 Poptrie:)A)Compressed)Trie)with)Popula5on)Count) for)Fast)and)Scalable)So<ware)IP)Rou5ng)Table)Lookup
  • 32. BACKUP&SLIDES Aug.)18,)2015 Poptrie:)A)Compressed)Trie)with)Popula5on)Count) for)Fast)and)Scalable)So<ware)IP)Rou5ng)Table)Lookup
  • 33. Tree)BitMap:)Succinct)Data)Structure Aug.)18,)2015 Poptrie:)A)Compressed)Trie)with)Popula5on)Count)for)Fast)and) Scalable)So<ware)IP)Rou5ng)Table)Lookup 1 0 1 1 1 1 d c b 0 1 e 0 1 a 0 0.0.0.0/0 128.0.0.0/1 0.0.0.0/2 64.0.0.0/2 64.0.0.0/3 Radix&Tree d c b e 0 0 Result)pointer Child)pointer )Mul5way)trie Node)array Mul5Vbit)node Tree&BitMap
  • 34. SAIL:)3Vlevel)Mul5way)Trie Aug.)18,)2015 Poptrie:)A)Compressed)Trie)with)Popula5on)Count)for)Fast)and) Scalable)So<ware)IP)Rou5ng)Table)Lookup 2nd)level:)28Vary) /0V16 /17V24 /25V32 3rd)level:)28Vary 1st)level:)216Vary #)in)L1/L2)cache #)in)L3)cache/DRAM #)in)DRAM ")Slow&when&cache&miss&occurs)
  • 35. DXR:)Binary)Search)in)Range)Table Aug.)18,)2015 Poptrie:)A)Compressed)Trie)with)Popula5on)Count)for)Fast)and) Scalable)So<ware)IP)Rou5ng)Table)Lookup 0.0.0.0/18 0.0.64.0/18 192.0.0.0/18 192.0.0.0 a 192.0.2.0 b 192.0.3.0 a Next)hopStar5ng)at Directly&indexed&table =)192.0.0.0V192.0.1.255 =)192.0.2.0V192.0.2.255 =)192.0.3.0V192.0.63.255 1))O(1))lookup 2))Binary)search) for)matching)range) (within)L1)cache)line(s))) Range&table N.B.,)illustrated)the)case)of)X)=)18 " Slow&for&large&range&tables& (e.g.,)a)cluster)of)IGP)routes))
  • 36. LockVfree)Update)Procedure Internal node 1 1 0 0 vector base0 N[2048] N[2049] N[2050] 31290 0 0 1 leafvec base1 2048 N L 1 L[3129] base1 1024 Node array (X) Top of the marked internal nodes Parent to be replaced Figure 6: The lock-free update procedure to th internal node. Updated prefix Updated leaves Replace these internal nodes Top of the marked triangles
  • 37. Mul5core)Scalability)Evalua5on)for) Random)Traffic Aug.)18,)2015 Poptrie:)A)Compressed)Trie)with)Popula5on)Count)for)Fast)and) Scalable)So<ware)IP)Rou5ng)Table)Lookup 0 100 200 300 400 500 600 700 800 900 1000 1 2 3 4 Lookuprate[Mlps] # of threads REAL-Tier1-A REAL-Tier1-B REALVTier1VA:)Global)TierV1’s)BGP)Router) REALVTier1VB:)Domes5c)ISP’s)BGP)Router
  • 38. Performance)on)IPv6)Rou5ng)Table Aug.)18,)2015 Poptrie:)A)Compressed)Trie)with)Popula5on)Count) for)Fast)and)Scalable)So<ware)IP)Rou5ng)Table)Lookup Algorithm Average&Lookup& rate&[Mlps] SAIL N/A)(no)support)for)more) specific)routes)than)/64) D16R 163.07 D18R 169.91 Poptrie16 209.84 Poptrie18 211.32 •  On)a)rou5ng)table)dumped)at)a)5erV1)ISP)(with)20,440)prefixes)) •  For)2^32)random)addresses)within)2000::/8) Poptrie18)is)1.24x)faster)than)D18R.)

Related Documents