Address Matching

Packet forwarding requires

Address matching
- Followed by table lookup of output port
Moving the packet through the router (from input port to output port)
- This involves scheduling, queueing, design of switch fabric etc, conventional aspects of switch design

Address matching

Longest prefix match – “best matching”
- Find the smallest network that contains the destination

Longest Prefix Match

Longest Prefix Match: Search for the routing table entry that has the longest match with the prefix of the destination IP address

Search for a match on all 32 bits, then 31 bits, then 30, 29 ,28 … until 0 bits

Host route, loopback entry are => 32-bit prefix match

Default route is represented as 0.0.0.0/0 => 0-bit prefix match

Example:

If we cannot find a match, use default route as answer.

How to do Longest Prefix Match in faster way?

Not as easy as exact match
- because length will be changing, the value we are comparing are changing
- unlike conventional binary search

Approaches:

Create a data structure for doing LPM
Convert the problem into a form so that we can do binary search
Reduce the problem to a sequence of exact match problems which we can apply hashing
Optimization based on distribution of prefix lengths
Combine software and hardware techniques

The Fast Longest Prefix Match Alogirthms

Fast LPM ( Longest Prefix Match ) Alogirthms includes:

Trie: bit-by-bit match
Binary search based on prefix length
Binary search among all prefixes in forwarding table

Notation and Terminology

Instead of address+mask, we use prefix* as short-hand.

Example: *, 00*, 001*, 11*

We store the set of prefixes found in a forwarding table into a Dictionary.

LPM with Trie

Trie pronounced as “Try”, derived from reTRIEval

Actual data structure also known as Patricia Trie – “Practical Algorithm To Retrieve Information Coded as Alphanumeric”

A tree for storing strings in which there is one node for every common prefix
Given an address, match by walking down the tree matching bit by bit
Implementation distributed in BSD Unix

Longest Prefix Matching with Trie

Given a Dictionary and the Match:

First we construct a binary tree for all *

To find the match, we follow bit by bit

Since it cant find the 5th one, we just match the furthest one with * which is the 3rd one (101*)

So the answer is 101*

101 will then be the longest prefix for this address

Maintaining a Trie

Adding/Removing new entries are easy

Collaspsing Non-branching Paths

In order to have a simpler representation, we do a collapsing on the non-branching paths.

Combine non-branching paths into a single path

Before:

After:

Performance of Trie

Lookup time
- $O(w)$ , where $w$ is the average size of addresses in the dictionary
- or $O(\log N)$ where $N$ is number of prefixes in dictionary
It gets much worse for IPv6 (128 bit addresses)

Binary search based on prefix length

Group all prefixes of the same length together and put them into a hash table
So we have up to $w$ hash tables ( $w=32$ for IPv4)
If we try each hash table one by one, then in worst case it takes $O(w)$ tries → not good
In Binary search, we pick the root node as $\frac{w}{2}$ bits ( $\frac{w}{2}=16$ for IPv4)

Each entry has 3 things: [Prefix, Flag, LSF]

Flag : Off = True address (need not to find LSF), On = Imaginary address (need to find LSF)

LSF : longest-so-far (Real entry)

Example: Binary search based on prefix length (8-bit)

Given dictionary:

First form a tree

Fill in all the dictionary prefixes into hash tables
Then from smallest node but larger bit, add the entries into upper node and mark the flag on
for entries with flag on, find LSF which is the equal or smaller length of prefix in dictionary

Table 3

Prefix	Flag	LSF
001*	Off
101*	Off
111*	Off

Table 2

Prefix	Flag	LSF
00*	On	00
11*	On	11
10*	On	*

Table 1

Prefix	Flag	LSF
0*	Off

Table 5

Prefix	Flag	LSF
10100*	Off
10011*	Off

Table 8

Prefix	Flag	LSF
10101010*	Off
11001100*	Off

Table 7

Prefix	Flag	LSF
1101110*	Off
0101101*	Off
1010101*	On	101*
1100110*	On	11*

Table 6

Prefix	Flag	LSF
100001*	Off
100100*	Off
010110*	On	0101* => 010110*
110111*	On	11*
101010*	On	101*
110011*	On	11*

Table 4

Prefix	Flag	LSF
0001*	Off
0101*	On	0101
1000	On	*
1001	On	*
1101	On	11*
1010	On	101*
1100	On	11*

The Steps:

First form a tree
First Fill in all the dictionary prefixes into hash tables
Then from smallest node but larger bit, add the entries into upper node and mark the flag on
for entries with flag on, find LSF which is the equal or smaller length of prefix in dictionary

A More detailed example on hash table 1,2,3

First fill in all the dictionary prefixes into hash tables

Table 3

Prefix	Flag	LSF
001*	Off
101*	Off
111*	Off

Table 2

Prefix	Flag	LSF
00*	Off
11*	Off

Table 1

Prefix	Flag	LSF
0*	Off

Then from smallest node but larger bit, add the entries into upper node and mark the flag on

Table 3

Prefix	Flag	LSF
001*	Off
101*	Off
111*	Off

Table 2

Prefix	Flag	LSF
00*	On
11*	On
10*	On

Table 1

Prefix	Flag	LSF
0*	Off

for entries with flag on, find LSF which is the equal or smaller length of prefix in dictionary
- If cant found, then fill in *

Table 3

Prefix	Flag	LSF
001*	Off
101*	Off
111*	Off

Table 2

Prefix	Flag	LSF
00*	On	00
11*	On	11
10*	On	*

Table 1

Prefix	Flag	LSF
0*	Off

Then do the same to other nodes recursively and we can eventually get all the tables done.

Binary search among all prefixes in forwarding table

Think of each prefix as a range:
- E.g. for 16 bits, 01* = in range of [0100000000000000, 0111111111111111]
Represent each prefix by two padded prefixes
Sort all the padded prefixes
For a given IP address to lookup, do a binary search on the sorted, padded prefixes
This gives you the smallest range the IP address falls into and the corresponding longest match prefix

Example Binary search among all prefixes in forwarding table

After Sorting:

So when finding best matched prefix:

If Left bracket at Left:

If Right bracket at Left:
- count back,
- adding 1 for )
- -1 for (
- till you reach -1

Try 11000

But this “counting back” can take a long time, therefore we need to do pre-computation

Create a lookup table based on the range

> column contains the LPM result for the input address having a binary value greater than the current entry but smaller than the next one.

> means IP address greater than current value and smaller than the next row value
= means IP address equal to current value

Now you get a lookup table.

Then remove duplicates (need to update the > or = item, depends on which duplicate you delete)

Not delete in pairs, this example is just a coincidence.

Finally the table looks like:

Lets say we want to find for 10001.

10001 is higher and 10000 but smaller than 10011

Therefore 100 is the answer.

Another Example

Prefix	Ranges of padded version
*	000000 - 111111
1*	100000 - 111111
01*	010000 - 011111
10*	100000 - 101111
001*	001000 - 001111
110*	110000 - 110111
1101*	110100 - 110111
0111*	011110 - 011111

After sorting:

Now you get a lookup table.

	>	=
000000	*	*
001000	001	001
001111	*	001
010000	01	01
011110	0111	0111
011111	01	0111
011111	*	01
100000	1	1
100000	10	10
101111	1	10
110000	110	110
110100	1101	1101
110111	110	1101
110111	1	110
111111	*	1
111111	-	*

After remove dupilcates and update