Fast Packet Classification on OpenFlow Switches Using ...

Fast Packet Classification on OpenFlow Switches Using ...

Guarantee-IP-Lookup-Performancewith-FIB-Explosion Author: Tong Yang, Gaogang Xie, YanBiao Li, Qiaobin Fu, Alex X. Liu, Qi Li, Laurent Mathy Publisher/Conf.: SIGCOMM '14 Proceedings of the 2014 ACM conference on SIGCOMM Pages 39-50 Presenter: Date: 2019/2/20 Department of Computer Science and Information Engineering National Cheng Kung University, Taiwan R.O.C. Motivation On-chip vs. Off-chip memory. 10 times faster, but limited in size. With FIBs increasing, for almost all packets Constant yet small footprint for FIB: On-chip Memory + Constant yet fast lookup speed: Low Time Complexity Ideal IP Lookup Algorithm 2 SAIL Framework Observation: almost all packets hit 0~24 prefixes Two Splitting for a given IP address Splitting lookup process finding its longest matching prefix length finding the next hop Splitting prefix length length 24

length 25 Prefix length 0~24 Prefix length 25~32 Finding prefix length Finding next hop On-chip Off-chip Off-chip Off-chip 4 Splitting Original trie Bitmap arrays 1 6 1 0 1 1 8 0 3 1 0 0 1 1 0 1 0 0 9 2 0 3 10 1 1 1 0 1 1

Bit Maps 0-24 On-Chip Next hop arrays 1 1 3 0 4 5 1 1 24 1 0 7 1 Level 0~24 Short prefixes 11 2 1 Level 25~32 Long prefixes 2 =4 =0 How to avoid searching both short and long prefixes? 5 Pivot Pushing & Lookup Pivot push: FIB prefix */0

level 0 nexthop 6 level 1 1*/1 4 01*/2 3 001*/3 3 111*/3 7 0011*/4 1 1110*/4 8 11100*/5 2 001011*/6 9 (a) Trie level 2 level 3

1 B4 [001010 >> 2] = 1 B1 4 0 B2 3 O 3 7 B 1 A F 3 B0 6 C 8 E 2 D 3 G 9 (b) B3 B4

H N4 8 N3 Lookup 001010 Pivot level: 4 Bit maps 0 1 1 0 1 0 0 0 0 0 0 N4 [2] = 0 0 1 0 0 1 1 0 0 1 0 0 0 0 1 0 0 0 0

0 3 0 0 0 0 (c) 0 7 long prefix 6 7 Level 25 ~32 Let the number of internal nodes on level 24 be n. We can push all solid nodes on levels 2531 to level 32. Afterwards, the number of nodes on l31 to level 32. Afterwards, the number of nodes on l evel 32 is 256 n because each internal node on level 24 has a complete n because each internal node on level 24 has a complete subtree with 256 leaf nodes, each of which is called a chunk. For each leaf node, its corresponding entry in bit map is 1 and its corresp onding entry in next hop array is the next hop of this node. For each internal node, its corresponding entry in bit map is 1 and its cor responding entry in next hop array is the chunk ID in , multiplying whic h by 256 plus the last 8 bits of the given IP address locates the next hop i n. 8 To distinguish these two cases, we let the next hop be a positive number and th e chunk ID to be a negative number whose absolute value is the real chunk ID value.

With our pivot pushing technique, looking up an IP address a is simple: if [a >> 8] = 0, then we know the longest matching prefix length is within [0, 23] and f urther test whether [a >> 9] = 1; if [a >> 8] = 1 [a >> 8] > 0, then we know t [a >> 8] > 0, then we know t hat the longest matching prefix length is 24 and the next hop is [a >> 8]; if [a > > 8] = 1 [a >> 8] > 0, then we know t [a >> 8] < 0, then we know that the longest matching prefix length i s longer than 24 and the next hop is [(| [a >> 8]| 1) n because each internal node on level 24 has a complete 256 + (a&255)]. 9 Update of SAIL_B Insert 10* FIB prefix */0 level 0 nexthop 6 level 1 1*/1 4 01*/2 3 001*/3 3 111*/3 7 0011*/4 1 1110*/4

8 11100*/5 2 001011*/6 9 (a) Trie level 2 level 3 F 3 B0 6 0 B2 3 O 3 7 B 1 C 8 E 2 D 3

G 9 (b) B3 B4 H N4 8 N3 B2[10]=1 1 B1 4 A Bit maps delete111* 1 B3[111]=0 0 1 10 0 0 1 0 0 0 01 0 0 0 0 1 1 0 0

1 0 0 0 0 1 0 0 0 0 0 3 0 0 0 0 (c) 0 7 changing 001*, or inserting 0010* only need to update off-chip tables 10 SAIL_U Level 6 Level 12 Pushing to levels 6, 12, 18, and 24. One update at most affects 2^6= 64 bits in the bitmap array. Level 18 Still at most one on-chip memory access is enough for each update.

Level 24 11 SAIL_L(1/2) If B16==1 Y N N16 Level 16 If B24==1 Y N Level 24 N32 N24 Level32 12 SAIL_L(2/2) 13 SAIL_M Trie 1 A: 00* C: 10* G: 110* Trie 2 A:00* C:10* E:100* Overlay Trie A: 00*

B: 01* E: 100* F: 101* G: 110* H: 111* + A D C G A C A B C D E E F G H (a) (b) (c) 14 Optimization SAIL_B

Lookup: 2 on-chip memory accesses in worst case Update: unbounded, low average update complexity Update Oriented Optimization (SAIL_U) Update: 1 on-chip memory access Lookup Oriented Optimization (SAIL_L) Lookup: 25 on-chip memory accesses in worst case Lookup: 4 on-chip memory accesses in worst case Update: 1 on-chip memory access Extension: SAIL for Multiple FIBs (SAIL_M) 15 SAILs in worst case On-Chip Memory Lookup (on-chip) Update (on-chip) SAIL_B = 4MB 25 1

SAIL_L 2.13MB 2 Unbounded SAIL_U 2.03MB 4 1 SAIL_M 2.13MB 2 Unbounded Worst case: 2 off-chip memory accesses for lookup 16 Implementations FPGA: Xilinx ISE 13.2 IDE; Xilinx Virtex 7 device; On-chip memory is 8.26MB Intel CPU: Core(TM) i7-3520M 2.9 GHz; 64KB L1, 512KB L2, 4MB L3; DRAM 8GB SAIL_L and SAIL_M GPU: NVIDIA GPU (Tesla C2075, 1147 MHz, 5376 MB device memory, 448 CUDA co

res), Intel CPU (Xeon E5-2630, 2.30 GHz, 6 Cores). SAIL_B, SAIL_U, and SAIL_L SAIL_L Many-core: TLR4-03680, 36 cores, each 256K L2 cache. SAIL_L 17 Evaluation FIBs Traces Real FIB from a tier-1 router in China 18 real FIBs from www.ripe.net Real packet traces from the same tier-1 router Generating random packet traces Generating packer traces according to FIBs Comparing with

PBF [sigcomm 03] LC-trie [applied in Linux Kernel] Tree Bitmap Lulea [sigcomm 97 best paper] 18 FPGA Simulation On-chip memory usage SAIL_L PBF 1.2MB 1.0MB 800.0kB 600.0kB 400.0kB 200.0kB 0.0B rrc00rrc01rrc03rrc04rrc05rrc06rrc07rrc10rrc11rrc12rrc13rrc14rrc15 FIB SAIL Algorithms Lookup Speed Throughput SAIL_B 351Mpps 112Gbps SAIL_U 405Mpps 130Gbps

SAIL_L 479Mpps 153Gbps 19 Intel CPU: real FIB and traces LC-trie 800 TreeBitmap Lulea SAIL_L Lookup speed (Mpps) 700 600 500 400 300 200 100 0 1 2 3 4 5 6 7

8 9 10 11 12 FIB 20 14 12 10 8 9 19 29 39 49 59 69 79 89 99 109 119 129 139 149 159 169 179 189 199 209 219 229

239 249 259 269 279 289 299 309 319 # of memory accesses per update Intel CPU: Update rrc00 average of rrc00 rrc01 average of rrc01 rrc03 average of rrc03 6 4 2 0 # of updates (*500) 21

Recently Viewed Presentations

  • Introduction to Procurement for Public Housing Authorities

    Introduction to Procurement for Public Housing Authorities

    Unit 2 Introduction to Procurement for Public Housing Authorities Procurement Planning: Choosing a Contracting Method * * * * * * * * Learning Objectives Identify the four main methods of procurement: small purchase procedures, sealed bidding, competitive proposals and...
  • The Sociology of the Family

    The Sociology of the Family

    Multi-cultural nature of society (Afro-Caribbean families often Matrifocal - female dominated; Asian families may be extended) Diversity withinFamilies. Not only have the types of families changed, but the roles people do in them have changed to.
  • ENUM Implementation in the US

    ENUM Implementation in the US

    R E S E T Roadmap for European research on Smartcard Technologies FROM SMART CARD TO TRUSTED PERSONAL DEVICE Working Group Outcomes RESET Seminar - 3 April 2003
  • Mesleki̇ İngi̇li̇zce Ii

    Mesleki̇ İngi̇li̇zce Ii

    In contrast, the term may also refer to the construction of state corporatism, where state-owned corporations are created and delegated public joint-stock, publicly listed companies, in order to introduce corporate and business management techniques to social tasks resembling corporate nationalism...
  • Capital Goods Skills Council PMMAI Workshop: Ahmedabad 25th

    Capital Goods Skills Council PMMAI Workshop: Ahmedabad 25th

    Capital Goods Sector Skill Council (CGSC) Registered as a Society. Promoted by FICCI and Co-promoted by DHI, with funding support from NSDC and industry. Key Segments. Initial focus is on the following segments of Capital Goods Sector: Machine Tools.
  • Key Stage Two Maths Tests

    Key Stage Two Maths Tests

    Think of an adjective beginning with ....Y Write some sentences to punctuate correctly. How to help with spellings... Investigate the rules... -cious, -tious -cian -tion -sion -ible -able -cial - tial Silent letters: knife, subtle Homophones: there, their, they're Reading...
  • strong academic program - Duval County Public Schools

    strong academic program - Duval County Public Schools

    What is important in college admissions? Your final grades in challenging courses are the most important items of your college application.. You have taken an exceptionally strong academic program (+2) Your 7th and/or 8th grade Algebra I, Geometry, and/or World...
  • Group 4 Project - Waterloo Region District School Board

    Group 4 Project - Waterloo Region District School Board

    Group 4 Project "a student will not be awarded a grade without participation in the project" Stuart Bond, Principal Moderator IB. Rationale. students analyze a topic or problem or question. emphasis is on interdisciplinary . cooperation. and the .