Re: The state of IPv6 multihoming development

[Masataka Ohta <mohta@necom830.hpcl.titech.ac.jp>]

Iljitsch;

> > Is this really about the limits of top end scaling?
> > I always considered it to be about making routing more O(1)ish with
> > respect to multihomed networks you don't have a bussiness relationship
> > then O(n*mumble)..
> 
> O(1)?  :-)
> 
> Well, maybe there is such a beast. When I studied software engineering I
> was told there were no sorting algorithms that could do better than
> O(n*log(n)). However, some digging produced radix sort, which was used
> in the good old days of the Hollerith machines and scales O(n). So just
> because people think it can't be done doesn't mean it can't be done.

Radix sort uses address arithmetic complexity of which is silently
assumed to be O(1).

However, speed of real memory is O(log(size of the memory)). 

That's one of the reason why reduction of DFZ is important for
the high speed Internet with quick routing table look up.

							Masataka Ohta