Purdue CS 63600 - Packet classification (11 pages)

Previewing pages 1, 2, 3, 4 of 11 page document View the full content.
View Full Document

Packet classification



Previewing pages 1, 2, 3, 4 of actual document.

View the full content.
View Full Document
View Full Document

Packet classification

75 views


Pages:
11
School:
Purdue University
Course:
Cs 63600 - Internetworking
Unformatted text preview:

CS 636 Internetworking Ramana Kompella ROUTER ALGORITHMICS Lecture 20 Packet classification CS 636 Internetworking 1 Good news real life much simpler Prefix containment is rare max 7 Few distinct port ranges Number of disjoint classification regions small linear in N For any given pair of source and destination IP addresses few rules match it 20 based on survey of real ISP rules CS 636 Internetworking 2 Beyond 2 d Any two dimensional search algorithm for all matches for S D R1 R2 R5 R7 R2 R6 Simplest scheme extend any 2d scheme to multiple dimensions Given at most 20 rules match use linear search Advantage no replication port ranges stay as ranges CS 636 Internetworking 3 Extended grid of tries Grid of tries for normal 2 d matches We fixed backtracking with replication EGT PC BSV03 uses pre computation of rule costs and path computation CS 636 Internetworking 4 Divide and conquer Three schemes Bit vector linear search On demand cross producting Equivalenced cross producting Common idea Search along individual dimensions and combine results CS 636 Internetworking 5 Bit Vector linear search Dest IP M M M M TI Net Complexity Run time O kn Memory O n2 Src IP Dest Port Src Port Proto 25 53 UDP S 53 23 TO 123 123 UDP Net TCP Dest IP M 11110111 TI 00001111 Net 00000111 00000101 Source IP S 11110011 TO 11011011 Net 11010111 11010011 Src Port 123 11111111 11110111 Proto UDP 11111101 TCP 10110111 10110101 Action R1 R2 R3 R4 R5 R6 R7 R8 Dest Port 25 10000111 53 01100111 23 00010111 123 00001111 00000111 00000101 11010011 00000111 11110111 10110111 00000001 R8 CS 636 Internetworking 6 Cross producting Dest IP M M M M TI Net Dest IP M TI Net Src IP Dest Port Src Port Proto 25 53 UDP S 53 23 TO 123 123 UDP Net TCP Action R1 R2 R3 R4 R5 R6 R7 R8 Dest Port 25 53 23 123 Proto UDP TCP Src IP S TO Net 3 120 3 30 4 6 1 3 1 478 0 1 2 3 4 5 Cross Product M S 25 123 UDP M S 25 123TCP M S 25 123 M S 25 UDP M S 25 TCP M S 25 478 TCP 479 Action R1 R1 R1 R1 R1 R1 R8 R8 Src Port 123 Longest prefix matching separately for all fields Combines the results in a single step by looking up the matching rule in a pre computed table Size of this table is the product of the numbers of recognized prefixes ranges for the individual fields Due to its memory requirements this method is not feasible CS 636 Internetworking 7 Equivalenced cross producting Dest IP Rule Class Src IP bitmap 0 M S 11110011 C1 1 M TO 11010011 C2 2 M Net 11010111 C3 3 M 11010011 C2 4 TI S 00000011 C4 5 TI T0 00001011 C5 6 TI Net 00000111 C6 7 TI 00000011 C4 8 Net S 00000011 C4 9 Net TO 00000011 C4 10 Net Net 00000111 C6 11 Net 00000011 C4 12 S 00000001 C7 13 TO 00000001 C7 14 Net 00000100 C8 15 00000001 C7 16 entries 8 distinct classes Dest Src Dest Src Proto IP IP Port Port Equivalenced cross producting a k a recursive flow classification or RFC Combines the results of the per field longest matching prefix operations two by two Pairs of values grouped in equivalence classes Leads to significant memory savings as compared to simple cross producting Provides fast packet classification but compared to other algorithms the memory requirements relatively large Final result CS 636 Internetworking 8 Decision tree approaches At each node of the tree test a bit in a field or perform a range test Large fan out leads to shallow trees and fast classification Leaves contain a few rules traversed linearly Interior nodes may contain rules that match also Tests may look at bits from multiple fields A rule may appear in multiple nodes of the decision tree this can lead to increased memory usage Tree built using heuristics that pick fields to compare on that divide remaining rules relatively evenly among descendants Fast and compact on rule sets used today CS 636 Internetworking 9 HiCuts HyperCuts Dest port 50 Source S DestPort 53 R1 R3 R5 R6 R10 R2 R7 Dest Port 53 R2 R7 R9 R5 R4 CS 636 Internetworking 10 Summary Hardware solutions usually more attractive Efficient 2d such as grid of tries works well General problem harder Equivalenced cross producting is fast but still requires 16 30 Mbytes for 100 1000 filters BV scheme works well for upto 8K filters CS 636 Internetworking 11


View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Packet classification and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Packet classification and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?