CS 268: Route Lookup and Packet ClassificationOverviewLookup ProblemExamplePatricia TriesLulea’s Routing Lookup Algorithm (Sigcomm’97)First Level: Bit-VectorFirst Level: PointersSlide 9Code Word and Base Indexes ArrayFirst Level: Finding Pointer GroupFirst Level: Encoding Bit-masksFirst Level: Finding Pointer IndexFirst Level: Memory RequirementsFirst Level: OptimizationsLevels 2 and 3LimitationsNotesSlide 19Classification ProblemExample of Classification RulesCharacteristics of Real Classifiers (Gupta & McKeown, Sigcomm’99)Slide 23Hard ProblemSimplifying AssumptionsRecursive Flow Classification (RFC) AlgorithmRFC AlgorithmThe RFC AlgorithmExample of Packet Flow in RFCSlide 30Complete ExampleSlide 32RFC Lookup PerformanceRFC ScallingSummaryCheck-Point Presentation (cont’d)Slide 37RFC Algorithm: ExampleCS 268: Route Lookup and Packet ClassificationIon StoicaMarch 3, [email protected] 2OverviewPacket LookupPacket [email protected] 3Lookup ProblemIdentify the output interface to forward an incoming packet based on packet’s destination addressForwarding tables summarize information by maintaining a mapping between IP address prefixes and output interfacesRoute lookup find the longest prefix in the table that matches the packet destination [email protected] 4ExamplePacket with destination address 12.82.100.101 is sent to interface 2, as 12.82.100.xxx is the longest prefix matching packet’s destination address…… 312.82.xxx.xxx 1128.16.120.xxx12128.16.120.11112.82.100.10112.82.100.xxx [email protected] 5Patricia TriesUse binary tree paths to encode prefixesAdvantage: simple to implementDisadvantage: one lookup may take O(m), where m is number of bits (32 in the case of IPv4)001xx 2 0100x 310xxx 101100 [email protected] 6Lulea’s Routing Lookup Algorithm (Sigcomm’97)Minimize number of memory accessesMinimize size of data structure (why?)Solution: use a three-level data [email protected] 7First Level: Bit-Vector Cover all prefixes down to depth 16Use one bit to encode each prefix-Memory requirements: 216 = 64 Kb = 8 KBgenuine headsroot [email protected] 8First Level: PointersMaintain 16-bit pointers to (1) next-hop (routing) table or (2) to two level chuncks-2 bits encode pointer type-14 bits represent an index into routing table or into an array containing level two chuncksPointers are stored at consecutive memory addressesProblem: find the [email protected] 9Example…pointerarrayRoutingtableLevel two chunks0006abcdbit vector…000acdef1 0 0 0 1 0 1 1 1 0 0 0 1 1 1 1Problem:[email protected] 10Code Word and Base Indexes ArraySplit the bit-vector in bit-masks (16 bits each)Find corresponding bit-maskHow? -Maintain a16-bit code word for each bit-mask (10-bit value; 6-bit offset) -Maintain a base index array (one 16-bit entry for each 4 code words)number of previous ones in the bit-vector Code word arrayBase index [email protected] 11First Level: Finding Pointer GroupUse first 12 bits to index into code word arrayUse first 10 bits to index into base index array address: 004C first 12 bits41first 10 bits13 + 0 = 13Code word arrayBase index [email protected] 12First Level: Encoding Bit-masksObservation: not all 16-bit values are possible-Example: bit-mask 1001… is not possible (why not?)Let a(n) be number of non-zero bit-masks of length 2nCompute a(n) using recurrence:-a(0) = 1-a(n) = 1 + a(n-1)2For length 16, 678 possible values for bit-masks This can be encoded in 10 bits-Values ri in code wordsStore all possible bit-masks in a table, called [email protected] 13First Level: Finding Pointer IndexEach entry in maptable is an offset of 4 bits:-Offset of pointer in the group Number of memory accesses: 3 (7 bytes accessed)[email protected] 14First Level: Memory Requirements Code word array: one code word per bit-mask-64 KbBased index array: one base index per four bit-mask-16 KbMaptable: 677x16 entries, 4 bits each-~ 43.3 KbTotal: 123.3 Kb = 15.4 [email protected] 15First Level: OptimizationsReduce number of entries in Maptable by two:-Don’t store bit-masks 0 and 1; instead encode pointers directly into code word -If r value in code word larger than 676 direct encoding-For direct encoding use r value + 6-bit [email protected] 16Levels 2 and 3Levels 2 and 3 consists of chunksA chunck covers a sub-tree of height 8 at most 256 headsThree types of chunks-Sparse: 1-8 heads•8-bit indices, eight pointers (24 B)-Dense: 9-64 heads•Like level 1, but only one base index (< 162 B) -Very dense: 65-256 heads•Like level 1 (< 552 B)Only 7 bytes are accessed to search each of levels 2 and [email protected] 17LimitationsOnly 214 chuncks of each kind-Can accommodate a growth factor of 16Only 16-bit base indices-Can accommodate a growth factor of 3-5Number of next hops <= [email protected] 18NotesThis data structure trades the table construction time for lookup time (build time < 100 ms)-Good trade-off because routes are not supposed to change oftenLookup performance:-Worst-case: 101 cycles•A 200 MHz Pentium Pro can do at least 2 millions lookups per second -On average: ~ 50 cyclesOpen question: how effective is this data structure in the case of IPv6 [email protected] 19OverviewPacket LookupPacket [email protected] 20Classification ProblemClassify an IP packet based on a number of fields in the packet header, e.g.,-source/destination IP address (32 bits)-source/destination port number (16 bits)-TOS byte (8 bits)-Type of protocol (8 bits)In general fields are specified by [email protected] 21Example of Classification RulesAccess-control in firewalls-Deny all e-mail traffic from ISP-X to YPolicy-based routing-Route IP telephony traffic from X to Y via ATMDifferentiate quality of service -Ensure that no more than 50 Mbps are injected from [email protected] 22Characteristics of Real Classifiers (Gupta & McKeown, Sigcomm’99)Results are collected over 793 packet classifiers from 101 ISPs, with a total of 41,505 rules-Classifiers do not contain many rules: mean = 50 rules, max = 1734 rules, only 0.7% contain over 1000 rules-Many fields are specified
View Full Document
Unlocking...