CS 636 InternetworkingCS 636 InternetworkingRamana KompellaROUTER ALGORITHMICSLecture 20: Packet classification1Good 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 2Beyond 2-d 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 3Any two dimensional search algorithm for all matches for (S, D)R1R2R5R7R2R6Extended 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 computationCS 636 Internetworking 4Divide-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 5Bit Vector linear searchCS 636 Internetworking 6Dest IP Src IP Dest Port Src Port Proto ActionM * 25 * * R1M * 53 * UDP R2M S 53 * * R3M * 23 * * R4TI TO 123 123 UDP R5* Net * * * R6Net * * * TCP R7* * * * * R8Dest IPM 11110111TI 00001111Net 00000111* 00000101Source IPS 11110011TO 11011011Net 11010111* 11010011ProtoUDP 11111101TCP 10110111* 10110101Dest Port25 1000011153 0110011123 00010111123 00001111* 00000111Src Port123 11111111* 1111011100000101+11010011+00000111+11110111+1011011100000001R8ComplexityRun time – O(kn)Memory – O (n2)Cross-productingCS 636 Internetworking 7Dest IP Src IP Dest Port Src Port Proto ActionM * 25 * * R1M * 53 * UDP R2M S 53 * * R3M * 23 * * R4TI TO 123 123 UDP R5* Net * * * R6Net * * * TCP R7* * * * * R8Dest IPMTINet*Src IPSTONet*ProtoUDPTCP*Dest Port255323123*Src Port123*3*120+3*30+4*6+1*3+1=478•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.Cross Product Action0 M,S,25,123,UDP R11 M,S,25,123TCP R12 M,S,25,123,* R13 M,S,25,*,UDP R14 M,S,25,*,TCP R15 M,S,25,*,* R1478 *,*,*,*,TCP R8479 *,*,*,*,* R8Equivalenced cross-producting 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 largeCS 636 Internetworking 8Dest IP - Src IPRule bitmapClass0 M,S 11110011 C11 M,TO 11010011 C22 M,Net 11010111 C33 M,* 11010011 C24 TI,S 00000011 C45 TI,T0 00001011 C56 TI,Net 00000111 C67 TI,* 00000011 C48 Net,S 00000011 C49 Net,TO 00000011 C410 Net,Net 00000111 C611 Net,* 00000011 C412 *,S 00000001 C713 *,TO 00000001 C714 *,Net 00000100 C815 *,* 00000001 C716 entries, 8 distinct classesSrc IPDest IPSrc PortDest PortProtoFinal resultDecision 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 todayCS 636 Internetworking 9HiCuts, HyperCutsCS 636 Internetworking 10Dest port < 50Source = S ?DestPort = 53 ? Dest Port = 53 ? R1R3R5R6R10R2R7R2R7R9R5R4Summary 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