DOC PREVIEW
UW-Madison CS 740 - Scalable High Speed IP Routing Lookups

This preview shows page 1-2-23-24 out of 24 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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 studyIntroduction•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 algorithmMore 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 studyBasic Scheme•Hash table organized by prefix length•Markers neededMarker 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 2False 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.bmpBasic 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 studyAlgorithm Refinements•To optimize, need to exploit deeper structure in routing table•Simplest improvement:Search only non-empty triesAsymmetric Binary Search•Try to search the most promising trie first•Example: Maximize table entries while keeping tree balanceMutating 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 prefixPotential 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 pointersRope: 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 = XRope 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 EndwhileBuilding 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 studyExisting 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 ComparisonPerformance ComparisonConclusion•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

UW-Madison CS 740 - Scalable High Speed IP Routing Lookups

Documents in this Course
Load more
Download Scalable High Speed IP Routing Lookups
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Scalable High Speed IP Routing Lookups 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 Scalable High Speed IP Routing Lookups 2 2 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?