1
$\begingroup$

I wish to use a multi-bit trie structure for storing IPv4 forwarding information with a fixed stride width of 8 bits, I think this is also called a "radix of 8" (so for any IP prefix 4 levels will exist between root and leaf nodes inclusive: 8-8-8-8). This is just a basic multibit binary trie that doesn't use any form of compression as it is for demonstration purposes only.

How can I calculate the memory storage requirements for a few basic scenarios (this is just to store the IP data, excluding any other data such as pointers to the next branch/leaf node in memory for example);

  1. The worst possible case is to hold all IPv4 addresses as individual /32 subnet entries (so 4.29 billion routes, the tree is "full")?
  2. To store 1.048 million routes (2^20) in the "best" case scenario described below?
  3. To store 1.048 million routes (2^20) in the "worst" case scenario described below?

For 2. above I imagine the best cast scenario in terms of memory requirements to be 1 million routes that all fall under 1.0.0.0/8 for example, they would fit into the IP ranges of 1.[0-16].[0-255].[0-255].

For 3. above I image the worst case scenario in terms of memory requirements is 1 million routes evenly spread out across all possibilities such that many 8 bit nodes are created in the tree with empty space in them. For example, the routes would fall in the ranges of [0-255].[0-255].[0-15].0 (this is ignoring the fact that many devices wouldn't route a packet with 0 in the first or last octect, this is about the memory requirements only).

When trying to calculate the answer to point 1, above I came up with the following sum where k is the stride:

k + (2^k * 8) + (2^k * 2^k * 8) + (2^k * 2^k * 2^k * 8) == 8 + (256 * 8) + (256 * 256 * 8) + (256 * 256 * 256 * 8) == 134744072 bits / 8 == 16.34MBs

For points 2. and 3. above I have found and equation on this website: O((2^k ∗ N ∗ W)/k) , N is the number of prefixes and W is the prefix size in bits. However, this seems wrong to me because there will be shared nodes even with 1 million prefix entries: ((2^8) * 1048575 * 32)/8 == 1073740800.

What are the correct formula for these three calculations?

$\endgroup$
  • $\begingroup$ After more research I might need a geometric expression to calculate 256^n where n is each level number in a trie. $\endgroup$ – jwbensley Oct 16 '17 at 16:08
  • $\begingroup$ Yes the answer to my first question is: 256*(1-256^n)/(1-256) I believe. $\endgroup$ – jwbensley Oct 16 '17 at 16:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.