On Wed, 29 Aug 2001, Sean M. Doran wrote:
| 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: whether it is reachable or | not. If we assign a bit of memory to every possible route
Is this a novel way of doing RIP and solving the split-horizon problem by eliminating the "D" in "DV"?
I'm all in favor of a radical solution, but that would be a bit too radical.
Sorry for being obtuse, but what does this bit-vector really represent? That neighbour A (a MAC address on a LAN, or a p2p interface or a VP/VC/DLCI/blah on an NMBA interface) is an OK next-hop towards prefix X?
The bit indicates whether some information (such as a route) is valid or not for some part of the address space.
Or is it associated with a next-hop address with a recursive lookup into another database (e.g. your IGP), such that each known next-hop has one of these bit vectors associated with it?
There are many possibilities. One would be to apply the bitmap encoding to the routing table (FIB) by taking the first 24 bits (for instance) of the IPv4 address range into a 2 MB bitmap. Then a "0" bit means next-hop address A, and a "1" bit means next-hop address B. But a few more next-hop addresses would be desirable, using a byte instead of a bit would make more sense.
| 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.
So, a per-prefix "holes" attribute
Yes.
in the form of a flattened Patricia Tree?
I'm not familiar with those.
Where is the savings here? Indeed, how do you avoid unflattening the bit-vector when eventually building your Adj_RIB/Loc_RIB/FIB?
You can keep the information in the BGP table in the "native" bitmapped format and create a regular routing table from this, or use a bit (or byte) mapped routing table as well.
I'm pretty sure I need further explanation to "get it"./
Suppose that multihoming becomes real popular, and 1% of the population starts to do it. Then you would need about 100k routes for a place like New York City. Suppose each of those multihomers announces a /24, that would be a /9. (Ok, this will work better with IPv6.) If every ISP that has multihomed customers in the NYC area announces that /9 with a 131072 bit bitmap that is less than 17 kilobytes of information per ISP rather than 17 MB or so for individual routes from each of those multihomers. Someone who peers with a number of those ISPs can easily create their own bitmap by applying some logical operations: mybitmap = peer1sbitmap OR peer2sbitmap OR peer3sbitmap Turning this information into a FIB is harder, though. Especially if we want to be able to do traffic engineering. A router would basically need to scan all the bitmaps from all peers, putting a route for the bit into the routing table using the best announcement where the respective bit is "1". We would probably want to use an extra bit per route to make traffic engineering possible.