From: "Ronnie Sahlberg" <ronnie_sahlberg@ozemail•com.au>
To: <netdev@oss•sgi.com>
Subject: Re: IPv4 and IPv6 stack multi-FIB, scalable in the million of entries.
Date: Fri, 9 Apr 2004 23:16:10 +1000 [thread overview]
Message-ID: <014801c41e34$d3759e50$6501010a@C5043436> (raw)
For fast routing lookups for IPv4, has anyone considered :
Treat all addresses as class c networks, dont route on anything else than
class c networks.
Limit the number of next-hop routers to 256. With next-hop-router index 0
meaning no route to that network.
Use a 16Mbyte large lookup table of bytes, where each byte represents the
next hop router.
Let the route to A.B.C.x re represented by the next-hop router described in
table[A*65536+B*256+C]
Then a route lookup would be O(1), a simple table lookup.
Route insertions/deletions would take longer but anyway, the lookup would be
fast, essentially a shift by 8 bits
and one memory read from the table. At the cost of 16Mbyte wasted of kernel
memory.
Wasteful, yes, only really useful if you have enormous routing tables, can
not do policy routing but fast.
next reply other threads:[~2004-04-09 13:16 UTC|newest]
Thread overview: 8+ messages / expand[flat|nested] mbox.gz Atom feed top
2004-04-09 13:16 Ronnie Sahlberg [this message]
-- strict thread matches above, loose matches on Subject: below --
2004-04-08 21:16 IPv4 and IPv6 stack multi-FIB, scalable in the million of entries Krishna Kumar
2004-04-08 19:53 Mathieu Giguere
2004-04-09 1:05 ` jamal
[not found] <1IJuR-8qH-39@gated-at.bofh.it>
2004-04-08 17:18 ` Andi Kleen
2004-04-08 18:10 ` Mathieu Giguere
2004-04-08 18:33 ` David S. Miller
2004-04-08 18:34 ` alex
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='014801c41e34$d3759e50$6501010a@C5043436' \
--to=ronnie_sahlberg@ozemail$(echo .)com.au \
--cc=netdev@oss$(echo .)sgi.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox