Advanced OpenFlow Network Classification and Ranges Analysis
Explore the innovative concepts of OpenFlow-based range classification in network architectures, as showcased in the research presented at the 11th ACM/IEEE Symposium on Architectures for Networking and Communications Systems. Discover the contributions made to range classification efficiency and update consistency in OpenFlow networks, along with insights into single-field and multi-field classifications. Dive into the nuances of packet header handling and the dynamic nature of ranges for enhanced network performance and security.
Uploaded on | 0 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
ORange: Multi Field OpenFlow based Range Classifier Liron Schiff Tel Aviv University Yehuda Afek Tel Aviv University Anat Bremler-Barr Inter Disciplinary Center Presenter: Netanel Cohen Inter Disciplinary Center The 11th ACM/IEEE Symposium on Architectures for Networking and Communications Systems (ANCS '15) Supported by the European Research Council (ERC) Starting Grant no. 259085 and by the Israel Science Foundation Grant no. 1386/11.
Range-based packet classification replicas Internet Source IP Address Destination IP Address Start 0.0.0.0 End 61.26.188.55 Action Server r3 192.168.1.1 Start End 192.168.15.7 Action Server r3 Server r1 61.26.188. 56 61.37.255.0 Server r1 192.168.1.1 192.168.99.1 Firewalls Forwarding Load Balancers DDoS mitigation 61.37.255.1 93.2.100.50 Server r2 10.0.0.1 10.5.0.127 Server r2 93.2.100.51 127.0.64.40 Drop 10.12.0.100 10.40.5.77 Drop .. .. .
Packet header : Field 1 Field 2 Field k Match Actions Flow Table: Flow Entry Flow Entry But OpenFlow matches can not be ranges! Only masked values No consistent multi switch update
Contributions Ranges classification in OpenFlow: ORange1 Costs 2 entries per range (instead of linear with field size , usually 16 or 32) Multi Field ranges classification: ORange-k Update consistency (with ranges) Per packet, per flow and cross-entrance
Single Field Ranges classification in OpenFlow ORange1
Ranges by Naive Prefix Expansion Pattern 125.26.188. [00111***] 125.26.188. [01******] 125.26.188. [1*******] 125. [00011011].*.* 125. [000111**].*.* 125. [001000**].*.* 125.[00100100].*.* 125.37.[0*******].* 125.37.[10******].* 125.37.[110*****].* 125.37.[1110****].* 125.37.[11110***].* 125.37.[111110**].* 125.37.[1111110*].* 125.37.[11111110].* 125.37. 255.0 125.37. 255.1 125.37. 255.[0000001*] 125.37. 255.[000001**] 125.37. 255.[00001***] 125.37. 255.[0001****] 125.37. 255.[001*****] 125.37. 255.[01******] 125.37. 255.[1*******] 125.[0010011*].*.* 125.[00101***].*.* 125.[0011****].*.* 125.[01******].*.* 125.[1*******].*.* 126. [0000000*].*.* 126. 2. [00******].* 126. 2. [010*****].* 126. 2. [011000**].* 126. 2. 100.[0010****] 126. 2. 100.[00110001] 126. 2. 100.[00110010] Action Server A Server A Server A Server A Server A Server A Server A Server A Server A Server A Server A Server A Server A Server A Server A Server A Server B Server B Server B Server B Server B Server B Server B Server B Server B Server B Server B Server B Server B Server B Server B Server B Server B Server B Server B Server B 2w 2 entries per range 62 entries per IPv4 range 254 entries per IPv6 range Start End Action 125.26.188. 56 125.37.255.0 Server A 125.37.255.1 126.2.100.50 Server B
Ternary CAMs (TCAMs) Associative Memory chips: 0 1 2 0*10**1* 00100111 11***011 entry index entry data out 0 00100111 in m 01010110 Properties: Ternary values ( 0 , 1 and * ) High throughput (300M ops per sec for 1Mb TCAM) Used in routers (IP lookup, classification) Expensive, high power consumption -> limited size Sometimes used to implement Flow Tables
A non OpenFlow Approach - PIDR [Panigrahy&Sharma2003] ? = 34,55 = [00100010?,00110111?] Longest common prefix (LCP): 001 0-ELCPs 0010**** 1-ELCPs 0011**** TCAMs:
A non OpenFlow Approach - PIDR [Panigrahy&Sharma2003] ?? > ?? ? Compare Read Range Bound (TCAM) Query ?? < ?? ? Compare Read Range Bound (TCAM) Query
Adapting PIDR to OpenFlow PIDR ORange1 Special hardware design Parallel TCAMs Query and read range bounds Comparing with bounds New OpenFlow design OpenFlow pipeline Match+Action sets field Compare by flow table and metadata field Static configuration No online updates Dynamic configuration Consistent updates
A non OpenFlow Approach - PIDR [Panigrahy&Sharma2003] Compare Read Range Bound (TCAM) Query Compare Read Range Bound (TCAM) Query
Adapting PIDR to OpenFlow Read Range Bound Compare Compare Read Range Query Query Even Comparisons are Flow-Table based! Bound Flow Table match + action Flow Table based comparisons
Adapting PIDR to OpenFlow 51 0 55 51 Packet: max/ min rid max q rid max q q <tmp> rid min q rid q no match no match Drop / controller ELCP0s (size n TCAM) ELCP1s (size n TCAM) Compare max q (size 2w TCAM) Compare min q (size 2w TCAM) False False Range 0 Action True True RIDs (size n CAM) Range Action
Reducing Pipeline Length Packet: max/ min rid max q rid max q q <tmp> rid min q rid q no match no match Drop / controller ELCP0s (size n TCAM) ELCP1s (size n TCAM) Can be Compare max q (size 2w TCAM) Compare min q (size 2w TCAM) False False implemented by the groups table No need if ranges span the entire space True True RIDs (size n CAM) Range Action
ORange1 Implementation Space Complexity (entries per range) Naive Approach: 2w-2 2 per range + 65 for comparison table Our work: 2 e.g. for 100 IPv4 ranges: 6,200 vs 265 entries Limitation only disjoint ranges
k field Ranges Classification ORange-k
Multi Dimensional Ranges Naive expansion: #entries exponentially grows with the dimension k: y x range 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 3 3 2 2 2 2 2 2 2 2 2 2 2 2 0001 001* 010* 0110 0001 001* 010* 0110 0001 001* 010* 0110 0001 001* 010* 0110 0111 10** 110* 01** 100* 1010 01** 100* 1010 01** 100* 1010 01** 100* 1010 0001 0001 0001 0001 001* 001* 001* 001* 010* 010* 010* 010* 0110 0110 0110 0110 10** 10** 10** 0011 0011 0011 01** 01** 01** 10** 10** 10** 1100 1100 1100 (2? 2)? entries per range Bigger problem!
Field Reduction Given k-dimensional ranges: ?1= 1,6 ?[1,6] ?2= 4,10 ?[3,12] ?3= 7,13 ?[8,11]
Field Reduction We project them on each axis
Field Reduction We compose each axis to disjoint intervals [11,13] [7,10] [4,6] [1,3]
Field Reduction We re-encode the ranges according to intervals ids ? 1= 0,1 ?[0,1] ? 2= 1,2 ?[1,4] ? 3= 2,3 ?{3}
Field Reduction For each packet we re-encode its field values ?,? = (8,4) ? ,? = (2,1) ? 1= 0,1 ?[0,1] ? 2= 1,2 ?[1,4] ? 3= 2,3 ?{3}
Field Reduction Smaller fields make much smaller k-dimensional encoding range x y 1 0001 0001 1 0001 001* 1 0001 010* 1 0001 0110 1 001* 0001 1 001* 001* 1 001* 010* 1 001* 0110 1 010* 0001 1 010* 001* 1 010* 010* 1 010* 0110 1 0110 0001 1 0110 001* 1 0110 010* 1 0110 0110 3 10** 0111 3 10** 10** 3 10** 110* 2 0011 01** 2 0011 100* 2 0011 1010 2 01** 01** 2 01** 100* 2 01** 1010 2 10** 01** 2 10** 100* 2 10** 1010 2 1100 01** 2 1100 100* 2 1100 1010 y' 00* 001 010 01* 001 010 001 010 x' 00* 001 001 011 01* 01* 100 100 range 1 1 1 3 2 2 2 2 ? 1= 0,1 ?[0,1] ?1= 1,6 ?[1,6] ? 2= 1,2 ?[1,4] ?2= 4,10 ?[3,12] ? 3= 2,3 ?{3} ?3= 7,13 ?[8,11]
ORange-k Implementation Re-encode each field in the metadata field Then classify by new (smaller) k field ranges Packet header Metadata field1 8 field2 4 field k f1 2 1 f2 fk k dims.Classifier ORange1 Classifier #1 ORange1 Classifier #2 ORange1 Classifier #k
ORange-k Implementation Space Complexity (entries per range) Naive expansion: (2? 2)? Our approach: 4k + 2log?? e.g. for 100 2-dimensional IPv4 ranges: 20k vs 380k entries in the worst case Pipeline length 3k + 1 Atomic updates (next slides) Works well with overlapping ranges
ORange-k Space Improvement w=16 60% Improvment (%) 50% 40% 30% 20% 10% 0% 1 2 # dimensions 3 4 1000 Random ranges 16bit fields
ORange-k Space Improvement 109 108 107 106 105 104 103 1.00E+09 1.00E+08 Na ve expansion Space (bits) 1.00E+07 1.00E+06 ORange 1.00E+05 1.00E+04 1.00E+03 8 16 24 32 40 48 56 64 width (bits) Total space for 100 Random 4-dimensional ranges.
Consistency As time permits
Update Consistency Consistency of adding, changing and deleting ranges Three levels of consistency: Per-Packet Per-Flow Cross-Entrance
Per-Packet consistency Change affects several entries Pattern 125.26.188. [00111***] 125.26.188. [01******] 125.26.188. [1*******] 125. [00011011].*.* 125. [000111**].*.* 125. [001000**].*.* 125.[00100100].*.* 125.37.[0*******].* 125.37.[10******].* 125.37.[110*****].* 125.37.[1110****].* 125.37.[11110***].* 125.37.[111110**].* 125.37.[1111110*].* 125.37.[11111110].* 125.37. 255.0 125.37. 255.1 125.37. 255.[0000001*] 125.37. 255.[000001**] 125.37. 255.[00001***] 125.37. 255.[0001****] 125.37. 255.[001*****] 125.37. 255.[01******] 125.37. 255.[1*******] 125.[0010011*].*.* 125.[00101***].*.* 125.[0011****].*.* 125.[01******].*.* 125.[1*******].*.* 126. [0000000*].*.* 126. 2. [00******].* 126. 2. [010*****].* 126. 2. [011000**].* 126. 2. 100.[0010****] 126. 2. 100.[00110001] 126. 2. 100.[00110010] Action Server A Server A Server A Server A Server A Server A Server A Server A Server A Server A Server A Server A Server A Server A Server A Server A Server B Server B Server B Server B Server B Server B Server B Server B Server B Server B Server B Server B Server B Server B Server B Server B Server B Server B Server B Server B <empty> 125.36.[0*******].* 125.36.[10******].* 125.36.[110*****].* 125.36.[1110****].* 125.36.[11110***].* 125.36.[111110**].* 125.36.[1111110*].* 125.36.[11111110].* 125.36. 255.0 125.36. 255.1 125.36. 255.[0000001*] 125.36. 255.[000001**] 125.36. 255.[00001***] 125.36. 255.[0001****] 125.36. 255.[001*****] 125.36. 255.[01******] 125.36. 255.[1*******] 125.[00100101].*.* Server A Server A Server A Server A Server A Server A Server A Server A Server A Server B Server B Server B Server B Server B Server B Server B Server B Server B Start End Action 36 125.26.188. 56 125.37.255.0 Server A 125.37.255.1 36 126.2.100.50 Server B Flow table:
Per-Packet consistency Change affects several entries Need atomicity (while traffic passes thru) Existing solutions implemented using Packet buffering, or duplicating and switching tables Packet match Flow Table Accesses modify entry modify entry modify entry time Single range update
Per-Flow Consistency [Reitblatt, Foster, Rexford, Schlesinger, Walker 2012] Start End Action replicas 125.26.188. 56 125.37.255.0 Server 2 125.37.255.1 126.2.100.50 Server 3 Internet client s IPs
Per-Flow Consistency [Wang, Butnariu, Rexford, 2011] Change in weights Change in ranges Start End Action replicas 36 125.26.188. 56 125.37.255.0 Server 2 125.37.255.1 36 126.2.100.50 Server 3 Internet But existing flow shouldn t change client s IPs
Per-Flow Consistency [Wang, Butnariu, Rexford, 2011] Start End Action replicas 36 125.26.188. 56 125.37.255.0 Server 2 125.37.255.1 36 126.2.100.50 Server 3 New flow client s IPs
Cross-Entrance Consistency replicas SDN Network X Internet client s IPs
summary Efficient Ranges implementation in OpenFlow One dimensional ORange1 Multi-dimensional ORange-k Update Consistency Per packet Per flow Cross-entrance
