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

53 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



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?