Encoding routing information in bitmaps

In early 2001, the global routing table reached 100,000 routes. Many
people feel that if the number of distinct routes in the default-free zone
(DFZ, the part of the Internet where routers don't have a default route,
typically the largest or tier-1 ISPs) keeps growing too fast, at some
point the DFZ routers will fail and the Internet will "break" because they
can no longer hold the large number of routes in their memory or they
don't have the CPU power to process them within a reasonable time.

There are many potential ways to improve the situation, but none of them
magically fixes everything. My standpoint is that we need a paradigm
shift.The current paradigm is that every route is very important, so we
should store as much information about it as possible. For instance, a
Cisco router uses something between 60 and 240 bytes per route per peer
(it's hard to get exact figures). So a full routing table from ten peers
takes something like 60 to 240 megabytes of memory.

This will have to change. If we remove all non-essential information from
a route, we finally arrive at the single thing that must always be encoded
for each route individually: the fact whether it is reachable or not. If
we assign a bit of memory to every possible route, we can store the
reachability state of the entire Internet as /24s in just two megabytes.
Or as individual /32s in 512 MB. Using bitmaps also makes processing a lot
faster, since a single CPU operation can work on 32 or more bits at the
same time.

Obviously, a lot of work has to be done to apply this to the real world.
An idea would be to assign /16s to geographic areas. Each ISP that has
customers in that area would announce the /16, just like they would do
now, but with an attached bitmap that indicates for which /24s this
announcement is valid and for which it isn't. So 10 ISPs in one area would
all announce the /16 with a 256 bit bitmap, so just 10 routes end up in
the default-free zone instead of 500.

I think it is possible to add support for bitmaps to the BGP protocol, and
probably in a backward compatible way, too. I might write up an Internet
Draft about this. However, not only the BGP protocol has to change, but
also the way the router stores the information internally and even the
route lookup part of the forwarding algorithm.

Iljitsch van Beijnum, aug 2001.

Ideas can't be copyrighted, but please give proper credit.
See my website http://www.muada.com/ for contact information.