Routing and Forwarding

• All possible routes to a destination network

• Routing table

• -> contains best routes to a destination (chooses one best route from the routing inforamtion base…)

• NO!

• -> rounting used to create routing information base

• and based on this, create forwarding information base…

• => also responsible for updates of RIB / FIB

Forwarding:

• actually look at packets and relay to next hop based on FIB

• Routing

• -> not that time critical

• Forwarding

• -> Highly time critical!

• Find an IP address with identical network parts (prefix matching)

• Find the IP address with longest matching network parts (longest prefix matching)

Strict Longest Prefix Matching (LPM) Algorithm

1. Sort FIB: longest prefixes first

2. Scan for matching prefix (top to bottom)

3. First prefix that matches is the correct one

• very easy to implement

• very slow (linear probing…)

• Tree based lookup

• Trie structures

• -> trie := Tree with more invariants

• content of parent node is prefix of the nodes content

• -> useful for a variety of index structures, can be used for LPM

• => idea: model entire IP space inside a trie

• Omit the parent nodes and when creating a prefix, concatenate until leaf is reached…

• Start with shortest prefix in FIB (default gateway…)

• -> for each entry, look at next hop…

• => assign each next hop unique Next Hop ID

• => going from shortest to longest prefix, extend Trie (based on binary representation of prefix, e.g. 0; 01, 10; 01-> 010, 011; …) if prefix is in FIB with ND-ID of corresponding next hop… and with X if no entry… (null entry)

1. Set curNode to the root

2. Set level to 0

3. Set lastNH-ID to invalid

4. If curNode.NH-ID exists: Set lastNH-ID to curNode.NH-ID

5. Check level-th bit of destination address

   • If 0: Set curNode to curNode.left

   • If 1: Set curNode to curNode.right

6. If curNode is NULL: Return lastNH-ID

7. level++

8. Goto step 4

Problem:

• Basic Tries are very wasteful

• Most nodes would not be occupied by a route

• Most routes have long prefixes (16 or 24)

Solution:

• Aggregate chains of “empty” nodes into one (or zero) nodes

• This compresses the path the algorithm has to traverse

• Fewer nodes to save -> less memory consumption

• Fewer nodes to visit -> less CPU consumption

Problem

• Basic Tries are very wasteful

• Each node has only two children

• Very large (binary) trees are built

Solution

• Nodes have 2n children

• Pull children’s children into the parent

• Fewer (but bigger) nodes to save

• Fewer nodes to visit less CPU consumption (branch misses)

• Idea

  • Path compression and level compression are orthogonal

  • Both can be combined

  • Result: LPC-Trie

• more advanced lookup structure for routing tables

• Construct two large tables

• First 24 bit of the prefix are handled in the “TBL24”

• Last 8 bit in “TBLlong”

• Works because most prefixes are shorter than 24 bit (for IPv4)

• Dir 24-8 was designed for hardware implementation

  • +  simple control flow

  • +  only one memory lookup for ≤ /24 prefixes (2 accesses for > /24 prefixes)

  • - requires lots of memory (> 32 MiB)

• requires two lookups

• first, lookup the /24 bit part that fits the specific IP

• this part then points to the /8 table containing the enumeration of all IPaddresses with the corresponding next hop ID

• only one lookup

• -> next hop id directly stored in first table…

• Similar to Dir 24-8, but with more flexible address separation (e.g. 16/16)

• => idea: create smaller routing tables to perform faster lookups