What is the big-O picture? (was: [RRG] Happiness; lack thereof)

["Victor Grishchenko" <victor.grishchenko@gmail.com>]

As it comes to summarizing/comparing proposals, could we focus on what
is the expected big-O gain?

If we'll assume unhindered network growth to be exponential and
equipment performance growth to be also exponential, the outcome is
mostly defined by the correspondence between the exponents. (Actually,
we don't want the routing table growth to consume all the performance
gains, so the former exponent better be much smaller than the latter.)
From that standpoint, a one-time gain is not truly significant. At
best, it delays the problem for several years.

Historically, once a flat routing space becomes unmanageable, it is
usually split in two layers (e.g. EGP vs IGP or OSPF areas or even
MAC-in-MAC). In a perfect world, that replaces one O(N) routing table
for two O(sqrt(N)) tables.
So, if a new split is introduced every k years, it solves all the
routing problems. Except for the fact each split adds a bit more of
stretch, complexity and opaqueness.
(I personally think that the prefix-bunch approach might bring new
rules, although that is still "a research".)

So, half-jokingly, let me propose a proposal evaluation scale.
Other things being equal, every O(N) -> O( sqrt(N) + sqrt(N) )
proposal might be considered as "normal", everything better is "a
breakthrough" and everything worse is "a regression".

On 07/03/2008, Luigi Iannone <luigi.iannone@uclouvain.be> wrote:
> Finally, I cannot find why EID-to-RLOC cache is significantly smaller
> (preferably, in terms of big-O) than the EID-to-RLOC database. Is
> there any study of that issue?
> You can get a look to:
> http://inl.info.ucl.ac.be/publications/cost-caching-locatorid-mappings
> There you can find the size of a cache.
> The size of the database, assuming granularity of prefixes annonced by BGP,
> is just the size of a BGP table.

-- 
Victor

--
to unsubscribe send a message to rrg-request@psg.com with the
word 'unsubscribe' in a single line as the message text body.
archive: <http://psg.com/lists/rrg/> & ftp://psg.com/pub/lists/rrg