The bitmaps are generated inside the source AS (presumably, iBGP will still carry regular routes) and the bitmaps are transmitted from one network to another, so there is no requirement for full interconnetion at the routing level.
The trouble with using 1 bit to represent 1 prefix is that there is a need to move more than 1 bit of information per route between AS's (think AS paths for loop detection, communities etc.). In iBGP the situation is worse as you have more information you want to carry (next hop, localpref), but you seem to envisage this only to replace eBGP. So all you are doing is compressing the data stream (after making some simplifying assumptions some of which I don't believe hold up). As you have to translate your bitmap back to/from iBGP in order to propagate announcements across the AS, you might as well consider the simpler alternative of just compressing the eBGP. However, you're increasing processor power here, rather than decreasing it. It would probably be possible to compress information on stub nodes, or nearly stub nodes much further (but you can do that effectively with outbound route filters), and, to a limitted extent reduce their visibility in the middle of the network (think proxy-aggregation) but we have existing tools to do this. The 'real' solution is to hierachicalize (sp?) or indirect the routing tree such that reachability information for common multihomed configurations does not in general reach the core's of most people's networks [*]. I suspect technologies similar to mobile IP may have application here. [*] or reduce the routes held in most of the routers in most people's networks, which, without wishing to start another flame war, is a claim occasionally made for MPLS networks in that non-edge LSR routers need not carry any BGP table, 'merely' an LIB. However, you still need to carry the prefixes in edge LSRs so, stepping neatly around the flame-fest, this seems to me an incomplete solution. -- Alex Bligh Personal Capacity