Address Lookup in IP Routers Routing Table Lookup

Address Lookup in IP Routers Routing Table Lookup

Address Lookup in IP Routers Routing Table Lookup Routing Table Output Scheduling Switch Fabric Routing Decision Routing Table Forwarding Decision Routing Table Forwarding

Decision 2 IPv4 Routing Table Size Source: Geoff Huston, APNIC 3 IPv4 Routing Table Size Source: bgp.potaroo.net, 2013 4 Routing table lookup: Longest Prefix Match With CIDR, there can be multiple matches for a destination address in the routing table Longest Prefix Match: Search for the routing table entry that has the longest match with the prefix of the destination IP address (=Most Specific Router):

1. 2. Search for a match on all 32 bits Search for a match for 31 bits .. 32. Search for a mach on 0 bits Needed: Data structures that support a fast longest prefix match lookup! 128.143.71.21 Destination address Next hop 10.0.0.0/8 128.143.0.0/16 128.143.64.0/20 128.143.192.0/20

128.143.71.0/24 128.143.71.55/32 default R1 R2 R3 R3 R4 R3 R5 The longest prefix match for 128.143.71.21 is for 24 bits with entry 128.143.71.0/24 Datagram will be sent to R4 5 IP Address Lookup Algorithms The following algorithms are suitable for Longest Prefix Match

routing table lookups Tries Path-Compressed Tries Disjoint-prefix binary Tries Multibit Tries Binary Search on Prefix Prefix Range Search 6 IP Address Lookup Algorithms The following algorithms are suitable for Longest Prefix Match routing table lookups

Tries Path-Compressed Tries Disjoint-prefix binary Tries Multibit Tries Binary Search on Prefix Prefix Range Search 7 What is a Trie? A trie is a tree-based data structure for storing strings: There is one node for every

common prefix The strings are stored in extra leaf nodes t t e Tries can be used to store network prefixes Note: Prefixes are not only stored at leaf nodes but also at internal nodes p o te n

ten p o to a tea po o top t pot 8 Binary Trie

Each leaf contains a possible address Prefixes in the table are marked (dark) Search: Traverse the tree according to destination address Most recent marked node is the current longest prefix Search ends when a leaf node is reached 9 Binary Trie 1 k 1010*

0 k Update: Search for the new entry Search ends when a leaf node is reached If there is no branch to take, insert new node(s) 10 Compressed Binary Trie d

Goal: Eliminate long sequences of 1-child nodes Path compression collapses 1-child branches Path Compression: Requires to store additional information with nodes Bit number field is added to node Bit string of prefixes must be explicitly stored at nodes Need to make comparison when searching the tree 11 Compressed Binary Trie d Search: 010110 Root node: Inspect 1st bit and move left

a node: Check with prefix of a (0*) and find a match Inspect 3rd bit and move left b node: Check with prefix of b (01000*) and determine that there is no match Search stops. Longest prefix match is with a 12 Disjoint-Prefix Binary Trie Multiple matches in longest prefix rule require backtracking of search Goal: Transform tree as to avoid multiple matches

Disjoint prefix: Nodes are split so that there is only one match for each prefix (Leaf pushing) Consequence: Internal nodes do not match with prefixes Results: a (0*) is split into: a1 (00*), a3 (010*), a2 (01001*) d (1*) is represented as d1 (101*) 13 Variable-Stride Multibit Trie Goal: Accelerate lookup by inspecting more than one bit at a time Stride: number of bits inspected at one time

With k-bit stride, node has up to 2k child nodes 2-bit stride: 1-bit prefix for a (0*) is split into 00* and 01* 1-bit prefix for d (1*) is split into 10* and 11* 3-bit prefix for c has been expanded to two nodes Why are the prefixes for b and e not expanded? 14 Complexity of the Lookup Complexity is expressed with O(.) (big O) notation: describes an asymptotic upper bound for the magnitude of a function in terms of another, usually simpler, function. W: length of the address (32 bits) N: number of prefix in the routing table O(N) : growth is linear with N O(N2): growth is quadratic with N O(log N): logarithmic growth in N

15 Complexity of the Lookup Bounds are expressed for Look-up time: What is the longest lookup time? Update time: How long does it take to change an entry? Memory: How much memory is required to store the data structure? Scheme Lookup Update Memory Binary trie O(W)

O(W) O(NW) Path-compressed trie O(W) O(W) O(NW) k-stride multibit trie O(W/k) O(W/k+2k) O(2kNW/k) 16

Recently Viewed Presentations

  • An idealized semi-empirical framework for modeling the MJO

    An idealized semi-empirical framework for modeling the MJO

    Adam Sobel and Eric Maloney NE Tropical Workshop, May 17 2011 ... Implicitly there is a Hadley cell. All linear modes are unstable due to WISHE, but westward- propagating Most unstable wavelength is ~decay length scale for stationary response to...
  • Child growth charts in Australia Murdoch Childrens Research

    Child growth charts in Australia Murdoch Childrens Research

    mostly formula fed infants . ... no health, environmental or economic constraints on growth. single-birth, term baby. no significant morbidity. ... Poor growth = decline in rate of weight gain first, followed by length / height gain.
  • Instruction Flow Techniques ECE/CS 752 Fall 2017 Prof.

    Instruction Flow Techniques ECE/CS 752 Fall 2017 Prof.

    1979: Smith Predictor. Disruption of Sequential Control Flow. Mikko Lipasti-University of Wisconsin. REVIEW - SKIP. Penalty (increased lost opportunity cost): 1) target addr. Generation, 2) condition resolution. Sketch Tyranny of Amdahl's Law pipeline diagram.
  • Jelly Beans - appeal to the FIVE Senses -- IMAGERY

    Jelly Beans - appeal to the FIVE Senses -- IMAGERY

    Appeal to the FIVE Senses -- IMAGERY. Without touching, describe the shape and colour. Compare it to something else (use similes, metaphors, hyperboles). First. Its colour is like a tropical ocean, with little light flecks like bubbles. It is shaped...
  • 2018-2019 ABOUT NEW JERSEY FCCLA DESCRIPTION: Family, Career

    2018-2019 ABOUT NEW JERSEY FCCLA DESCRIPTION: Family, Career

    Challenge Events Culinary Chicken Fabrication Culinary Food Art Culinary Knife Skills Fashion Sketch FCCLA Creed Speaking & Interpretation CLUSTER MEETING EVENTS NEW JERSEY SPRING EVENTS: Art of Garde Manger Bread Basics Cake Decorating Fashion Runway FCCLA Speaks Hospitality 101 Lessons...
  • TEXAS RIVERS RIO GRANDE  Separates Texas and Mexico

    TEXAS RIVERS RIO GRANDE Separates Texas and Mexico

    They beat the Indians to the river, but were afraid to cross, because it was swollen by the spring rains. The man decided it was still better to plunge into the waters, than to face the Comanche and so they...
  • Chapter 2: Chemistry, Matter, and Life

    Chapter 2: Chemistry, Matter, and Life

    The nephron is associated with two capillary beds. Which capillary bed receives blood first? Nephron's Blood Supply . Fig. 19-5B. A nephron and its blood supply. Formation of Urine. Glomerular filtration. Glomerular filtrate. Tubular reabsorption. Diffusion.
  • DAU Hot Topics Forum "Using commercial items to increase ...

    DAU Hot Topics Forum "Using commercial items to increase ...

    DAU Hot Topics Forum"Using commercial items to increase innovation, increase competition and lower costs". Date: July 19th, 2017. Presented by: Phil Jasper, EVP & COO, Government Systems. Thank you for the opportunity to express industry's viewpoint ref this critical "contracting...