Re: [rrg] Locator: routing scalability

[Toni Stoev <[e-mail]>]

Paul, have my regards for going deep into the matter.
See my comments inline.

On Saturday 16 May 2009 00:34:56 Paul Jakma sent:
> On Thu, 14 May 2009, Toni Stoev wrote:
> 
> > Does locator have to facilitate routing with its structure?
> > My answer is: yes, it must.
> 
> I have a question, a stupid one probably... Is the following thinking 
> of mine correct?:
> 
> If we encode routing information into the locator somehow, then this 
> implies the 2 are tied together, and that (at least) the initial 
> top-level hierarchy of internet routing is fixed for the life-time of 
> the locator.

This shall be backwards when using locator for intra-domain routing (and AS paths for inter-domain routing).
Then locator's tying is with its routing domain (AS). And the intra-domain location-naming/routing hierarchy needs just the AS number as its top-level.

> So this implies either one or more of: 
> 
> - that the lifetime of locators be short, and that they are
>    re-calculated/re-assigned frequently enough to have a sufficient
>    level of reachability between hosts on the internet.

My vision is that node reachability has to be shown by locator. Then lifetime of locators has to be relevant to that reachability.

>    (e.g. imagine a scheme that assigned locators empirically, by
>     examining the structure of the internet and calculating a
>     spanning-tree that approximated a power-law distribution
>     as good as possible and then assigning locators in an according
>     fashion, thus maximising the aggregation of routing information.
> 
>     I think there may be papers describing such things, but I'm not
>     sure there are RRG proposals ???).
> 
> - fairly long-lived, indeed static locator assignments. This implies
>    a quite broad and flat, top-level routing table. This is basically
>    what we have today, if ASes advertised just one prefix.
> 
>    Proposals under this model generally split routing into a 2-tier
>    system: the flat, top-level routing table + a secondary table of
>    networks behind the top-level locators (either aggregated locators,
>    or remapped/tunneled somehow)
> 
> Is this right so far?
> 
> If so, and if the prevailing proposals so far are of the static 
> top-level kind, then do know if a flat top-level is sufficiently 
> scalable? Is there any data/work on how fast this top-level might 
> grow? To what extent is the AS growth reflective of how that 
> top-level might grow? To what extent is the transit-AS growth 
> reflective of it?
> 
> I ask because AS growth might not be linear:
> 
>  	http://www.potaroo.net/tools/asn32/
> 
> though transit-AS growth is unclear (it doesn't grow much in fact, so 
> its perhaps impossible to get a trend from it):
> 
>  	http://www.potaroo.net/ispcol/2009-03/bgp2008.html

Paul, please keep helping with AS growth revision.

> Basically, what I wonder is whether a static top-level 
> locator->routing mapping is sufficient to meet the scaleability 
> requirement?
> 
> If it is not, then facilitating routing with the locator is just a 
> delaying tactic - a more dynamic system would eventually be 
> necessary.
> 
> If it is sufficient, great, of course - any dynamic system would by 
> definition be more complex.
> 
> (There may be ways of statically assigning locators according to some 
> kind of power-law distribution - but this means impressing some kind 
> of order onto ISPs, which probably isn't socio-politically 
> tractable).
> 
> regards,

Reconsider,
Toni