Scalable High Speed IP Routing Lookups Authors: M. Waldvogel, G. Varghese, J. Turner, B. Plattner Presenter: Zhqi Qiuv Outlinev Introductionv More about BMPSlide 5v Basic Schemev Marker Managementv False Markersv Basic AlgorithmSlide 10v Algorithm Refinementsv Asymmetric Binary Searchv Mutating Binary SearchSlide 14v Potential Disadvantagesv Rope: Encoded TreesSlide 17v Rope Searchv Building Rope SearchSlide 20v Existing Approachesv Complexity Comparisonv Performance Comparisonv ConclusionScalable High Speed IP Scalable High Speed IP Routing LookupsRouting LookupsAuthors: M. Waldvogel, G. Varghese, J. Turner, B. PlattnerPresenter: Zhqi Qiu Outline•Routing and the BMP (Best Matching Prefix) problem•Basic scheme: binary search of hash tables•Refinements: asymmetric trees, mutated binary search and ropes•Implementation: building the tree•Performance and comparison studyIntroduction•Increases in Internet traffic demands: link speed, router data throughput, packet forward rate •Packet forwarding rate becomes bottleneck•Address lookup: main step in packet forwarding•Need efficient Best Prefix Match algorithmMore about BMP•Classless Inter-Domain Routing (CIDR) - cope with routing table growth•Aggregation results in address prefix list in routing tables•Packets forwarded according to Best Matching Prefix•Goal: use hashing to find BMP Outline•Routing and the BMP (Best Matching Prefix) problem•Basic scheme: binary search of hash tables•Refinements: asymmetric trees and ropes•Implementation: building the tree•Performance and comparison studyBasic Scheme•Hash table organized by prefix length•Markers neededMarker Management•Reducing marker storage: markers only needed in levels visited by binary search when looking for P •E. g. : In table of 8 levels:a prefix with length of 7 [111] needs markers in level 4 and 6a prefix with length of 3 [11] needs markers in level 2False Markers•What if table entries are: P1=1, P2=00, P3=110 in the previous example? •Solution:to avoid backtracking, record current best matching prefix of marker M in M.bmpBasic AlgorithmInitialize range R = array LInitialize BMP to be null stringWhile R not empty I = middle level in range R D’ = D(L[i].length) M = Search(D’, L[i].hash) If M is nil Then set R = upper R Elseif M is a prefix & not a marker Then BMP = M.bmp; break Else { BMP = M.bmp; R = lower R} Endif Endwhile Outline•Routing and the BMP (Best Matching Prefix) problem•Basic scheme: binary search of hash tables•Refinements: asymmetric trees and ropes•Implementation: building the tree•Performance and comparison studyAlgorithm Refinements•To optimize, need to exploit deeper structure in routing table•Simplest improvement:Search only non-empty triesAsymmetric Binary Search•Try to search the most promising trie first•Example: Maximize table entries while keeping tree balanceMutating Binary Search•The number of distinct prefix lengths rarely exceeds 12•Every match with some marker X means that we need only search among the set of prefixes for which X is a prefixPotential Disadvantages•Pre-computing optimal trees increases insertion time•Storage of binary trees for each prefix enormous•Storage problem solved with “rope” data structure•Rope maximum length: log2W pointersRope: Encoded Trees•Only need to store the sequence of levels which binary search on a given subtrie will follow on repeated failures to find a match •e.g.: Rope 1 contains 16, 8, 4, 2, 1•Rope algorithm: a prefix not a marker: end of ropea prefix and a marker: X.bmp = XRope SearchInitialize Rope R = default search sequenceInitialize BMP = null stringWhile R not emptyi = first pointer of R D’ = D(L[i].length) M = Search(D’, L[i].hash)If M is success Then BMP = M.bmp; R = M.ropeEndif EndwhileBuilding Rope Search•Pass 1: builds a conventional trie•Pass 2: all prefixes inserted into hash tables, starting with shortest prefix •Batch insertions and deletions into the table as these operations are expensive. Outline•Routing and the BMP (Best Matching Prefix) problem•Basic scheme: binary search of hash tables•Refinements: asymmetric trees and ropes•Implementation: building the tree•Performance and comparison studyExisting Approaches•Modification of exact matching:log22N•Trie based: BDS radix trie O(W2)•Hardware: parallelism, CAM expensive•Protocol based: IP/tag switching, still need some IP lookups•Caching: CAM (Content Addressable Memory)Complexity ComparisonPerformance ComparisonConclusion•Intellectual contribution: markers and pre-computation ensure log time in worst-case•Solution scalable and can be implemented in software efficiently•Future work: choice of balancing function and faster insertion
View Full Document