North American Network Operators Group

Date Prev | Date Next | Date Index | Thread Index | Author Index | Historical

Re: multi-homing fixes

  • From: Iljitsch van Beijnum
  • Date: Thu Aug 30 05:23:36 2001

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

> 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


> 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.