classful routes redux
Todd Vierling
tv at duh.org
Thu Nov 3 20:29:35 UTC 2005
On Thu, 3 Nov 2005, Stephen J. Wilcox wrote:
> well, /56 /48 /32 seem to have resonance but are not special in any way
Well, they are somewhat special. All of them are on eight-bit boundaries.
The importance of this comes in when deciding how to lay out a routing table
in a gate array or memory-based table.
A routing table capable of handling a flat 2^128 addressing space goes
beyond the realm of known physics -- and flat 2^64 comes close, at least for
a while (consider semiconductor atomic weights, and the fact that 1 mole is
approximately 2^79 atoms). That's quite a stretch, but should give a hint
as to why flat addressing does not work for every model.
Routing tables become much simpler when you have N-level (tree-like) tables,
a concept also used in MMUs. A tree done one bit at a time, while the most
compact form in many cases, is not very efficient at lookups. If you divide
the bitspace into sized chunks, the lookup time can be a better tradeoff
between speed and tree size.
Specifically, 8-bit dividing lines make this even easier. Much logic
programming (FPGA or similar) depends on power-of-two data sizes with a
minimum of 4 or 8 bits. This has led to well established 4-bit and 8-bit
data movement patterns that have been better optimized over time. If using
a store-and-forward mechanism with a more generic data processor (such as a
CPU), 8-bit dividing lines are all the more important for speed.
Or in summary of all of the above, "8-bit building blocks in routing tables
make writing the physical routing code much easier, and in many cases makes
the forwarding operation much faster."
--
-- Todd Vierling <tv at duh.org> <tv at pobox.com> <todd at vierling.name>
More information about the NANOG
mailing list