[RRG] Re: Fast and sparse mapping?

[Brian E Carpenter <brian.e.carpenter@gmail.com>]

On 2008-09-16 15:24, Robin Whittle wrote:
> Hi Brian,
> 
> I don't understand any part of what you wrote clearly enough to
> respond.  Could you be more expansive?
> 
> It seems there is a new Olympic sport of trying to discuss scalable
> routing in as few words as possible.  Perhaps there could be similar
> contests restricting communication to haiku, sign-language or charades.
> 
> I would prefer a more detailed initial exposition so I don't have to
> write back to the list and report I wasn't able to guess the full
> meaning the writer had in mind.
> 
>   - Robin
> 
> 
> Subject: Re: [RRG] Consequences of no renumbering...
> 
>> On 2008-09-11 17:02, Tony Li wrote:
>>> Hi Robin,
>>>
>>> |There is no scalable routing system - or transition scheme to a
>>> |scalable routing system - which can meet our goals of being
>>> |attractive to end-users and generating real scalability benefits
>>> |if it is not allowed to require most small end-user networks
>>> |(all PI and probably most small PA) to renumber once when
>>> |adopting the new system.
>>>
>>> One word: translation.
>> Two words: fast mapping.
> 
> Other than Ivip's essentially real-time control of ITRs by
> end-users, I am not sure what "fast mapping" means.  Please explain
> what you mean, with some examples.

An EID to RLOC map that can be consulted in much less than one packet time
in an edge router.

> 
>> I missed the bit where it was proved that fast mapping
>> mathematically requires aggregatable EIDs.
> 
> Who suggested this?

I've seen numerous references to EIDs needing to aggregate.
I'd like to know why.

> 
>> As I said a couple of weeks ago:
>>
>> However, would a lower estimate, say 2^23 (8 million) prefixes be
>> an issue?
> 
> An "issue" (meaning problem) for what?  I assume this figure is for
> the number of EID prefixes (LISP and APT terminology) or micronets
> (Ivip) which the mapping system supports.  Or is this a figure of
> how many routes are advertised in BGP?

I'm thinking specifically of the number of EIDs to be mapped to
a significantly smaller number of RLOCs. And I'm assuming that
lookup in a table of 2^23 entries is a fast operation.

> 
>> If not, why can't we start on the assumption that we know how to
>> support a map with 8 or 10 million entries, and have many years to
>> figure out a sparse  mapping system with several orders of
>> magnitude more entries?
> 
> I don't understand what "sparse mapping" means.

One where we assume that no aggregation is possible in the ID space,
i.e. the ID space is sparsely populated.

(Given the history of IP addressing, and the recent discussions
on this list, I don't know any other assumption we can make
except that IDs will look like meaningless randomly distributed
numbers.)

    Brian

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