Subject: [RRG] Text proposal: mapping granularity

From: "Tony Li" <[email-masked]>
Date: Thu, 20 Mar 2008 18:35:18 -0700

Hi all,

I'm trying to record the items that we reach consensus on, as well as some
of the background behind the discussion.  Here's my first draft at this
particular issue.  

If you have comments, more specific comments (i.e., replacement text) is
favored over less specifics. 

Thanks,
Tony

3.1.1.  Granularity

   The granularity of the mapping function controls the specificity of
   the entries that make up the map.  Mapping large blocks of
   identifiers to a common set of locators is highly efficient because
   it reduces the amount of information needed in the mapping function,
   but it sacrifices the ability for the mapping function to support
   more specific information, at the expense of scalability.  Shifting
   the scalability problem from today's routing protocols and forwarding
   plane to tomorrow's mapping function simply moves the problem.  Thus,
   any mapping solution that is going to have detailed granularity must
   also have commensurate scaling properties.

3.1.1.1.  Recommendation

   The identifier to locator mapping function should support mapping
   entries for both host identifiers and their aggregates.

--
to unsubscribe send a message to [email-masked] 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

---

From: Robin Whittle <[email-masked]>
Date: Fri, 21 Mar 2008 14:28:23 +1100

Hi Tony,

>    also have commensurate scaling properties.

A more thorough version of the last sentence might be:

     Thus, any mapping solution which can support more detailed
     granularity is in principle capable of supporting a separate
     mapping for every host identifier in the address space.  Since
     different mapping solutions have different practical upper
     limits on the number of mappings they can support, the ability
     of a mapping system to support individual host identifier
     granularity does not imply that a practical implementation
     could necessarily cope with such a large number of mappings.

This is a general discussion section, but the recommendation is that
the finally chosen mapping system will support individual IPv4/6
addresses (host identifiers).  Therefore, the astute reader will
note that the proposed mapping system is not required to support as
many mappings as there are IP addresses.

>    entries for both host identifiers and their aggregates.

I suggest that "should" be replaced by "must".

I think there needs to be some clearer definition of "aggregate".

I figure most people accept that:

   12.34.56.0/32 is not an aggregate.

   12.34.56.0/31 is an aggregate.

   12.34.56.0/24 is an aggregate.

but would everyone agree that:

   12.34.56.1/24

is an aggregate?

Does "aggregate" imply the starting point have all zeroes to the
right of the prefix length number of bits to the left?

If aggregate means an arbitrary length of contiguous address space,
from any starting point, then I will be perfectly happy - but I
think most people see it as some starting point with a prefix length.

Do we need to say anything about how the system is designed to
optimise performance, for instance in terms of data compactness in
the mapping messages (both push and pull)?

Maybe not, but here are some thoughts on data compactness anyway:

Using 4 bytes for an IPv4 address plus 1 byte for the prefix length
is the obvious way of specifying any "aggregate" or single IP
address.  For Ivip I would use 4 bytes for the starting point and 3
bytes for the length, because I want very flexible micronet sizes,
so there is the greatest possible flexibility for slicing and dicing
the IPv4 space.

For IPv6, space is plentiful and I would probably stick with the
traditional prefix method of determining the length, and enforce the
starting point to have zeroes to the right of the prefix length
number of bits on the left.

With IPv6, there are two obvious ways of tackling this:

    8 + 1 bytes for IPv6 with /64 resolution and a prefix length

   16 + 1 bytes for IPv6 with /64 resolution and a prefix length

I intend Ivip to be optimised for the 8 + 1 bytes arrangement, with
the protocol being capable of supporting 16 + 1, but with this
option not used in general.  It could be implemented in the future
if it ever becomes worth the trouble, which I suspect it won't.

  - Robin

---

From: "Tony Li" <[email-masked]>
Date: Thu, 20 Mar 2008 20:48:41 -0700

Hi Robin,

|A more thorough version of the last sentence might be:
|
|     Thus, any mapping solution which can support more detailed
|     granularity is in principle capable of supporting a separate
|     mapping for every host identifier in the address space.  Since
|     different mapping solutions have different practical upper
|     limits on the number of mappings they can support, the ability
|     of a mapping system to support individual host identifier
|     granularity does not imply that a practical implementation
|     could necessarily cope with such a large number of mappings.

Seems reasonable.  Any objections?

|>    The identifier to locator mapping function should support mapping
|>    entries for both host identifiers and their aggregates.
|
|I suggest that "should" be replaced by "must".

I hesitate to go there, as then some folks will infer that we're trying to
use RFC 2119 standards terminology.  As we're writing an informational
recommendation that is, by prior agreement, not standards track, that would
be out of bounds.  Of course, "should" is also defined by 2119, but would
hopefully not set folks off.

|I think there needs to be some clearer definition of "aggregate".
|
|If aggregate means an arbitrary length of contiguous address space,
|from any starting point, then I will be perfectly happy - but I
|think most people see it as some starting point with a prefix length.

How about we just rephrase it to be "contiguous blocks of identifiers"?

|Do we need to say anything about how the system is designed to
|optimise performance, for instance in terms of data compactness in
|the mapping messages (both push and pull)?

Not in this section.  ;-)

It sounds very much like what you're talking about is an engineering
optimization, which shouldn't be part of our recommendation anyway.

Tony

---

From: Robin Whittle <[email-masked]>
Date: Fri, 21 Mar 2008 15:02:23 +1100

Hi Tony,

> Seems reasonable.  Any objections?

Great!

> hopefully not set folks off.

OK - I understand the context and "should" does the trick.

> How about we just rephrase it to be "contiguous blocks of identifiers"?

This would be great.  It would be brief, unambiguous and would mean
that the mapping system wasn't constrained to provide micronets (EID
prefixes) with lengths only in powers of two.

> optimization, which shouldn't be part of our recommendation anyway.

That's fine - but maybe someone found it interesting to see how I
was thinking about the size of the micronet description on the wire.

  - Robin

---

From: Olivier Bonaventure <[email-masked]>
Date: Fri, 21 Mar 2008 09:11:25 +0100

Tony,
>    entries for both host identifiers and their aggregates.

The way the sentence is written can be understood as meaning that the 
mapping function will be designed to support host identifiers and in 
addition aggregates (or better contiguous blocks of identifiers). I 
would strongly prefer to write it in the opposite way :

The identifier to locator mapping function should support mapping 
entries for contiguous blocks of locators and host identifiers.

Olivier

-- 
http://inl.info.ucl.ac.be , Universite catholique de Louvain, Belgium

---

From: Randall Atkinson <[email-masked]>
Date: Fri, 21 Mar 2008 03:32:19 -0700

% 3.1.1.  Granularity
%
%   The granularity of the mapping function controls the specificity of
%   the entries that make up the map.  Mapping large blocks of
%   identifiers to a common set of locators is highly efficient because
%   it reduces the amount of information needed in the mapping function,
%   but it sacrifices the ability for the mapping function to support
%   more specific information, at the expense of scalability.  Shifting
%   the scalability problem from today's routing protocols and forwarding
%   plane to tomorrow's mapping function simply moves the problem.  Thus,
%   any mapping solution that is going to have detailed granularity must
%   also have commensurate scaling properties.
%
% 3.1.1.1.  Recommendation
%
%   The identifier to locator mapping function should support mapping
%   entries for both host identifiers and their aggregates.

The above seems to have already made some architectural assumptions.
It isn't  at all clear to me that the underlying assumptions are RG consensus
right now.

For example, in ILNP the primary mappings are forward FQDN->I and FQDN->L.;
of course there are also reverse lookups (equivalent to PTR lookups now).

However, no direct mapping I->L exists in ILNP -- because one is not needed.

The above text assumes in each case that (A) direct I->L mappings are
needed and (B) that direct I->L mappings exist and (C) the mapping
function in (B) has certain properties.

At least in the case of ILNP, all 3 of those assumptions (A, B, C) are not valid.

The simplest fix for the above text would be to insert some scoping text for
those paragraphs, perhaps starting with something like:

 "For an architecture where a direct I->L mapping is a functional
  requirement, ...

and ending with something like:

  "This section is not applicable for an architecture where a direct I->L
    mapping is not a functional requirement."

Yours,

Ran
[email-masked]

---

From: Scott Brim <[email-masked]>
Date: Fri, 21 Mar 2008 16:43:00 -0400

Excerpts from Tony Li on Thu, Mar 20, 2008 06:35:18PM -0700:
>    more specific information, at the expense of scalability.  

There's some subtlety missing.  "Information in the mapping function"
refers to state in mapping originators, the distribution system,
intermediaries ("holders"), and mapping points.  

Two-phase mapping functions (like ALT) can provide a high degree of
specificity at the mapping points while requiring very little state in
the distribution system or at holders, while at mapping points only
the information that is used is stored.

I think the best solution is just to delete the text above.  You don't
need it anyway, since what follows ...

>    Shifting

... captures the requirement anyway.

---

From: Scott Brim <[email-masked]>
Date: Fri, 21 Mar 2008 16:46:52 -0400

> Seems reasonable.  Any objections?

I don't think it adds.  "In theory it could support a huge number of
entries, but in reality it won't be able to."  That's beside the
point.  The real point is that if you're going to support fine
granularity, you need to do a good job at it -- as was in the text
that I recommended you save in my last message:

>    Shifting the scalability problem from today's routing protocols
>    and forwarding plane to tomorrow's mapping function simply moves
>    the problem.  Thus, any mapping solution that is going to have
>    detailed granularity must also have commensurate scaling
>    properties.

---

From: Scott Brim <[email-masked]>
Date: Fri, 21 Mar 2008 16:48:30 -0400

> prefixes) with lengths only in powers of two.

In reality ranges are always implemented as powers of two.  What's the
point?

---

From: "Tony Li" <[email-masked]>
Date: Fri, 21 Mar 2008 14:04:04 -0700

Strictly speaking, this is not always true.  See AppleTalk, which uses a
notion of cable ranges.  This of course begs the question: how do you deal
with overlapping aggregates?  Longest match is no longer meaningful.

If the IETF wants to deal with this issue, they're more than welcome to do
so.  ;-)

Tony

|-----Original Message-----
|From: [email-masked] [mailto:[email-masked]] On Behalf 
|Of Scott Brim
|Sent: Friday, March 21, 2008 1:49 PM
|To: 'Routing Research Group'
|Subject: Re: [RRG] Text proposal: mapping granularity
|
|Excerpts from Robin Whittle on Fri, Mar 21, 2008 03:02:23PM +1100:
|> > How about we just rephrase it to be "contiguous blocks of
|> > identifiers"?
|> 
|> This would be great.  It would be brief, unambiguous and would mean
|> that the mapping system wasn't constrained to provide micronets (EID
|> prefixes) with lengths only in powers of two.
|
|In reality ranges are always implemented as powers of two.  What's the
|point?
|
|--
|to unsubscribe send a message to [email-masked] 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
|

---

From: "Tony Li" <[email-masked]>
Date: Fri, 21 Mar 2008 15:09:05 -0700

Hi Ran,

|The above seems to have already made some architectural assumptions.
|It isn't  at all clear to me that the underlying assumptions 
|are RG consensus
|right now.

Yes and yes.  Since we were having some small amount of difficulty trying to
reach consensus about top level issues, we're instead trying to have a more
bottoms up discussion.  While we are exploring the leaves of one portion of
the tree, this does NOT imply that we have consensus that we will be taking
this branch.  Rather, it is simply an exploration of this portion of the
solution space.

Yes, this entire mapping discussion is in the context of solutions that will
need a mapping function and an identifier to locator map.  This context
should be obviously clear in the overall document.

Regards,
Tony

---

From: "ext Tony Li" <[email-masked]>
Date: Fri, 21 Mar 2008 14:04:04 -0700

Tony