Subject: [RRG] Consensus check: mapping granularity

From: "Tony Li" <[email-masked]>
Date: Wed, 19 Mar 2008 21:19:26 -0700

Hi all,

So after opening the discussion on this subject, the silence has been
deafening.  Therefore, I assume that we're all in agreement.  ;-)

Specifically, do we agree that:

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

Any dissent?

Tony

--
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: Thu, 20 Mar 2008 16:16:10 +1100

Hi Tony,

> for both host identifiers and their aggregates.

I understand this means individual IP addresses for IPv4 or IPv6, or
power of two spans of them.

Ivip uses any starting point with an integer length, so each
micronet can be of any size at all.  In practice, I would probably
have some length limit, but I haven't figured that out yet.  Also, I
would want a compact binary representation for IPv6 in the likely
event that everyone in fact specified their micronets as an integer
number of complete /64s.

I am not expecting a great deal of support for this, since I think
most folks are happy with 1, 2, 4, 256, 512 etc. IP addresses.

I would prefer something different, such as:

   The identifier to locator mapping function should support
   mapping entries covering a contiguous set of IP addresses
   of some arbitrary length 1 to some TBD maximum value.

But would be surprised if enough folks agreed to lead to rough
consensus for this, instead of your suggestion.

Examples of your suggestion would include, I think:

   2.2.2.0/32
   2.2.2.0/31
   2.2.2.0/24

What about this?

   2.2.2.1/24  = 2.2.2.1 to 2.2.3.0 inclusive?

Perhaps the next step - now or in the future, perhaps beyond the RRG
- is to define data formats, so we know how many bits are involved
in exactly specifying the starting and ending addresses of the
micronet, EID prefix or whatever.  This would help in estimating the
number of bytes required for each mapping update, which is
particularly important in a push or hybrid push-pull system.

 - Robin

---

From: Olivier Bonaventure <[email-masked]>
Date: Thu, 20 Mar 2008 08:54:34 +0100

Tony,
> for both host identifiers and their aggregates.

For scalability reasons, I would propose to define this requirement as 
follows :

The identifier to locator mapping function MUST support mapping entries 
for aggregates of identifiers. It MAY also support mapping entries for 
host identifiers.

My reasoning is that to be scalable, a mapping system must deal with 
aggregates. However, some devices, perhaps for some destinations may 
request or agree to receive map entries for host identifiers. Mapping 
individual host identifiers is clearly not scalable and should only be 
an option while the default should be to map aggregates.

Olivier

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

---

From: Xu Xiaohu <[email-masked]>
Date: Thu, 20 Mar 2008 10:55:38 +0100

> for aggregates of identifiers. It MAY also support mapping entries for

Hi Tony and Olivier,

Does this requirement imply that the identifier must be a hierarchical label
(not flat label) so as to be aggregatable?

Best wishes,
Xiaohu XU

---

From: Olivier Bonaventure <[email-masked]>
Date: Thu, 20 Mar 2008 11:16:46 +0100

Xu,
> (not flat label) so as to be aggregatable?

I don't think that a hierarchy is necessary. What is required is a 
mapping system that deals with blocks of identifiers and not with 
individual identifiers.

Olivier

---

From: Xu Xiaohu <[email-masked]>
Date: Thu, 20 Mar 2008 11:37:19 +0100

> -----邮件原件-----
> 发件人: Olivier Bonaventure [mailto:[email-masked]]
> 发送时间: 2008年3月20日 11:17
> 收件人: Xu Xiaohu
> 抄送: [email-masked]; 'Routing Research Group'
> 主题: Re: [RRG] Consensus check: mapping granularity
> 
> Xu,

Hi Olivier,

Let's take an example, can the host identifier (flat label) in HIP or i3
meet the above requirement of the mapping system?

Best wishes,
Xiaohu XU

---

From: "PAPADIMITRIOU Dimitri" <[email-masked]>
Date: Thu, 20 Mar 2008 12:05:31 +0100

olivier, xu,
> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On Behalf 
> Of Olivier Bonaventure
> Sent: Thursday, March 20, 2008 11:17 AM
> To: Xu Xiaohu
> Cc: [email-masked]; 'Routing Research Group'
> Subject: Re: [RRG] Consensus check: mapping granularity
> 
> Xu,

i suggest to refine the requirement: one is the nature / structure of
the identifier itself, the other is in terms of scalability
("aggregation" of identifiers), and the last one in terms of ID-to-Loc
mapping function.

> I don't think that a hierarchy is necessary. 
>
> What is required is a mapping system that deals with blocks 
> of identifiers and not with individual identifiers.

agreed. aggregates of identifiers shall be defined though to complete
the initial requirement. what's relationship between block & aggregate
of identifiers ?

-d.

---

From: Robin Whittle <[email-masked]>
Date: Thu, 20 Mar 2008 22:23:46 +1100

Hi Olivier,

> an option while the default should be to map aggregates.

I don't understand what the problem is with having one, many, or
most EID prefixes (LISP) or micronets (Ivip) being a single IPv4
address.

I think that with IPv4, more and more end-users will have smaller
and smaller chunks of space - many of them will be happy with a
single IP address.  Likewise, the only scenario where billions of
end-users each want their own address space is mobile phones /
computers.  Virtually all those users would be happy with a single
IPv4 address or a /64 in IPv6.

Nor do I see a problem with many EID prefixes / micronets being /48s
or /64s in IPv6.  I think it would be a bit nutty having ITRs having
to trawl through 128 bits, but I think the protocol by which the
mapping is sent (push or pull) should be able to accommodate
individual IPv6 addresses.

That is what we are discussing, isn't it?  The characteristics of
the protocol by which the mapping system communicates EID prefix /
micronet details to whatever requests them, along with the mapping
for that EID prefix / micronet.

What happens inside the mapping database - centralised or
distributed - is a private matter for whoever implements it.  The
innards of the mapping database storage system does not need to be
standardised.

I don't see any scaling problem with how the EIDs or micronets are
defined.  All I see is some efficiency and flexibility issues.  The
following examples assume IPv4.

One way is to have 32 bits for the base address and 5 bits for the
prefix length.  That is nice and compact - 5 bytes.

Ivip would use 32 bits for the base address and probably 24 bits for
the length.  That is 7 bytes rather than 5, but enables arbitrary
lengths of micronets.  Since IPv4 space is so precious, I think
these 2 extra bytes would be a good price to pay for the benefit of
more flexible slicing and dicing.

Your specification doesn't enable me to construct examples of what
you want in terms of bits and bytes to represent a micronet.  Could
you give some examples?

For instance, 3.4.5.0/31 is an aggregate, but takes no less bits to
specify than 3.4.5.0/32.

If your proposal is not motivated by compactness of representation
of the EID prefix's starting and ending point, then what is your goal?

Your statement:

> My reasoning is that to be scalable, a mapping system must deal
> with aggregates.

doesn't convey to me why you believe that being able to specify
individual IP addresses presents a scaling problem.

Surely you don't mean that you assume a mapping system can only have
a certain number of entries, and that to cover the address space
with this limited number of entries, most of them must cover a large
number of IP addresses?

One of the major benefits of ALT (actually, the only one, I think)
is that it can have endless divisions of the address space, without
burdening the ITRs, since they only cache whatever mapping they need
at the time.  So there's no scaling problem due to the number of
EIDs in terms of the ITRs or the conceptual nature of the ALT system
- you just add more ETRs and/or more storage capacity in these ETRs.

 - Robin

---

From: Olivier Bonaventure <[email-masked]>
Date: Thu, 20 Mar 2008 12:53:42 +0100

Dimitri,

> ("aggregation" of identifiers), and the last one in terms of ID-to-Loc

I agree, we should describe what the identifiers are and how they can be 
aggregated. Then another requirement can specify how the mapping will work.

> the initial requirement. what's relationship between block & aggregate

 From my viewpoint block=aggregate

Olviier

---

From: Olivier Bonaventure <[email-masked]>
Date: Thu, 20 Mar 2008 12:57:27 +0100

Robin,
> most EID prefixes (LISP) or micronets (Ivip) being a single IPv4

The problem is that if the mapping system is required to map each host 
identifier onto a (set of) locators, then I don't see how one can build 
a stable and scalable mapping system.

Olivier

---

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

Hi Olivier,

> a stable and scalable mapping system.

with which I disagree entirely.

Just because the mapping system is capable of specifying mapping for
a single IP address doesn't mean it is required to be able to do it
for every IP address in the system.

So there is no scaling problem with having the mapping system work
with the location of boundaries between one EID prefixes / micronet
and the next definable in units of single IP addresses.

Maybe the final IPv4 mapping system will be able to handle 4 billion
micronets, or maybe it can only handle a billion.  A consumer
terabyte hard drive could store 250 bytes of mapping for every
single IPv4 address - so I don't see that storage is a problem.

Whatever the maximum practical number of EID prefixes / micronets
(which will grow over time as technology improves), it makes no
sense to restrict the resolution with which an EID prefix / micronet
could be defined (to ensure no such EID prefix / micronet could be
smaller than some number of IP addresses) in order to somehow
protect against the system ever being required to handle more than
some maximum number of EID prefixes / micronets.

 - Robin

---

From: Olivier Bonaventure <[email-masked]>
Date: Thu, 20 Mar 2008 14:57:18 +0100

Robin,
> for every IP address in the system.

In the wordings that I used, I do not prohibit the mapping system from 
being able to specify a mapping for each host identifier.

"The identifier to locator mapping function MUST support mapping entries 
for aggregates of identifiers. It MAY also support mapping entries for 
host identifiers."

The first sentence means that the mapping function must be designed with 
aggregates in mind and must deal with aggregates (the larger the better 
from a scalability viewpoint). Then, the second sentence means that some 
parts of the mapping may choose to provide more specific mappings, but 
an entity that requested a mapping shall not be obliged to accept a 
mapping reply which is more specific than its request. It may accept 
such a more specific reply if it wishes to do so.

> single IPv4 address - so I don't see that storage is a problem.

I don't believe that the mapping system will be placed on a consummer 
terabyte hard drive... The main concern with using host identifiers from 
a scalability viewpoint is the potential churn, not the amount of storage.

Olivier

---

From: Scott Brim <[email-masked]>
Date: Thu, 20 Mar 2008 10:55:19 -0400

> for both host identifiers and their aggregates.

"should" ... are you trying to say that it should *support* this but not 
necessarily do well at it, or that it should support it at the same 
level of scalability as coarser aggregates, or ?

I wouldn't mind just "allow".  Beyond that has serious implications that 
have to be thought through.

---

From: Scott Brim <[email-masked]>
Date: Thu, 20 Mar 2008 11:14:01 -0400

> - you just add more ETRs and/or more storage capacity in these ETRs.

The problem is in fact on the sender side, the ITR side.  The receiver 
side, and LAT aren't problems, but smaller mapping granularity can cause 
problems for the encapsulator's cache strategy.  You need to think about 
how many individual endpoints a typical medium organization connects to, 
and figure out how much memory it would need.  What about Google, which 
needs to communicate with most endpoints in the world, and often?  Cache 
generally doesn't work in a situation like that.  They would have to 
aggregate into prefixes themselves, and carefully manage which ITR send 
to which prefix.

---

From: "Tony Li" <[email-masked]>
Date: Thu, 20 Mar 2008 09:58:13 -0700

|> The identifier to locator mapping function should support 
|mapping entries
|> for both host identifiers and their aggregates.
|
|"should" ... are you trying to say that it should *support* 
|this but not 
|necessarily do well at it, or that it should support it at the same 
|level of scalability as coarser aggregates, or ?
|
|I wouldn't mind just "allow".  Beyond that has serious 
|implications that 
|have to be thought through.

I would think that we would want to support it as the same level of
scalability as coarser aggregates.  However, we have not yet discussed what
level of scalability is a necessity.  Yet another item on the discussion
list...

Tony

---

From: [email-masked]
Date: Thu, 20 Mar 2008 13:50:41 EDT

In einer eMail vom 20.03.2008 17:59:34 Westeuropäische Normalzeit schreibt  
[email-masked]:

Tony

quote from draft-carpenter-idloc-map-cons-01.txt:
4.6.  Scale
 
   We want no arbitrary scaling limits.  However, proposed  scaling
targets are 10 to 100 billion Stacks (which scales the  Identifier
Namespace), and 10 million sites.  Although the  latter does not
directly scale the Internet's Locator Namespace,  it indicates the
worst-case granularity of the routing table for  that Locator
Namespace.  If we don't do better than random  allocation of address
blocks to sites, we will end up with 10  million routing table
entries.
 
Heiner

---

From: Brian E Carpenter <[email-masked]>
Date: Fri, 21 Mar 2008 13:54:30 +1300

> blocks to sites, we will end up with 10  million routing table

These weren't consensus numbers. Since then, Tony has convinced me
that we need to allow mapping down to individual hosts as well
as aggregates (so my answer to his question is Yes), but we probably
need to increase the likely size of the map from 10 million
to 100 million. I think these changes are compatible, but note my
belief that aggregates as small as a SOHO network would be
very rare in the map. Others disagree, and that changes the
numbers substantially.

    Brian

---

From: Sheng Jiang <[email-masked]>
Date: Fri, 21 Mar 2008 11:21:41 +0800

*> >>> The identifier to locator mapping function should support mapping
*> > entries
*> >>> for both host identifiers and their aggregates.
*> >> For scalability reasons, I would propose to define this
*> requirement as
*> >> follows :
*> >>
*> >> The identifier to locator mapping function MUST support
*> mapping entries
*> >> for aggregates of identifiers. It MAY also support mapping
*> entries for
*> >> host identifiers.
*
*i suggest to refine the requirement: one is the nature / 
*structure of the identifier itself, the other is in terms of 
*scalability ("aggregation" of identifiers), and the last one 
*in terms of ID-to-Loc mapping function.
*
*> > Hi Tony and Olivier,
*> > 
*> > Does this requirement imply that the identifier must be a
*> hierarchical label
*> > (not flat label) so as to be aggregatable?
*> 
*> I don't think that a hierarchy is necessary. 
*>
*> What is required is a mapping system that deals with blocks of 
*> identifiers and not with individual identifiers.
*
*agreed. aggregates of identifiers shall be defined though to 
*complete the initial requirement. what's relationship between 
*block & aggregate of identifiers ?

I have two points to make here:

a, we can have aggregatable identifiers and also keep part of identifiers flat at
the same time. For instance, normal identifiers are aggregatable, any identifiers
starting with 000 are flat. This design can meet special requirements too, such as
id privacy.

b, for me, aggregatable id has almost  the same meaning with hierarchical id. If an
id block is not hierarchical, it means there is no guarantee these ids are
topological together. If ids are distributed, one has to deal them individually,
then, they are not aggregatable. In another word, IDs has to be hierarchical in
order to be aggregatable. One may argue virtual aggregation mechanisms, similar to
CRIO, may be used to aggregate distributed IDs. It is true. But it is a much worse
choice only when we can not make topological aggregation. By design a new
architecture, there is no point for us to choose a worse and more complicated
solution. As a summary, hierarchy may not be necessary, but it is a better and
natural choice.

BR,

Sheng

*-d.
*> Olivier
*> 
*> --
*> http://inl.info.ucl.ac.be , Universite catholique de Louvain, Belgium
*> 
*> --
*> 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
*> 
*
*--
*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: [email-masked]
Date: Fri, 21 Mar 2008 14:27:27 EDT

Brian

10 millions, 100 millions and even billions - these figures wouldn't  
frighten me  because the only right solution is the one that scales  logarithmically. 
My solution would not only shrink the table size  and update churn, but 
consequently also the work load per router.  Hence it could take advantage of the 
idle time, e.g. by pursueing  similar goals like  the rtgwg wrt. to multipath 
and detours.
 
Quote------------
 
> Doesn't the issue persist independent of the characteristics based  on
> which a path gets selected?  Independent of *how* a path gets  selected,
> you need to decide *who* selects it (or who selects which part  of it).

Well, that's true of course. But nothing  can change the fact
that the originating host chooses  the source address and destination
address that the  packet starts out with, and all subsequent  choices
depend on  that.

Brian
End of  quote -----------------
 
Example: Be that the destination is "just behind the globe". So you may  have 
a West-route, a North-, East- and  South-route. The ingress may  take a 
choice and yes, all subsequent choices may not only depend on that but  should also 
COMPLY with that !!!! Sure, some respective assignment may have  to be 
conveyed, but first of all be enabled ! Multihoming ist just the last  hop of the 
West-,..,South-route issue.
 
------
There are  more issues which have never been discussed  here:
Support of (better models of) multicast, mp2mp ! 
The irrational behind using orthogonal models for intra/inter-domain  routing.
The fundamental deficiencies of distance vector.
 
------
Incremental deployability:
Like "ships in the night", as has been mentioned, several mechanisms may  
coexist:
Seafarers used to watch the stars. Using the compass and watching the  
magnetic needle came in parallel.
Car navigation did not start out with CDs that covered the entire continent  
either.
All of these methods are independend from each other, can evolve, and also,  
may fallback if necessary.
My solution was argued down to be not incrementally deployable. Just the  
opposite is the case and can be compared with the  progress in automobile 
navigation where at first the navigation  quality was also minor (e.g. was lost 
itself), so that more often  the driver had to fallback using other methods (maps, 
direction  signs).  
Here,  at the beginning when a rather small number of routers  takes part in 
the new protocol, switching back to the current method will be  necessary 
although the packet hasn't yet approached the destination very well.  But that 
will be improved the more routers are going to participate. In a  half-half 
scenario, falling back to current BGP however means, to benefit just  from the 
REGIONAL update churn! The global update churn is only required  for today's 
routing.
 
Yes, a new additional mechanism gets its deployment incentives from  
providing better service (the compass needle can be watched also in cloudy  nights, 
the car navigation makes driving comfortable,..)
I mentioned quite a few such additional aspects above. There are even  more 
(e.g. there is really no IPv4 depletion problem) and I learn more and  more the 
longer I follow this mailinglist discussion.
 
Heiner

 

 
 
extremely, it would hereb small. There is no prefix aggregation  problem if 
you aggregate the area instead (remember:Rhekther's law offers 2  alternative 
choices).

I have heard that a Dijkstra can be already be run within a second   dealing 
with 10 000 nodes.

---

From: Scott Brim <[email-masked]>
Date: Fri, 21 Mar 2008 15:25:36 -0400

Excerpts from Tony Li on Thu, Mar 20, 2008 09:58:13AM -0700:
> |> The identifier to locator mapping function should support mapping
> |> entries for both host identifiers and their aggregates.
> |
> |"should" ... are you trying to say that it should *support* this
> |but not necessarily do well at it, or that it should support it at
> |the same level of scalability as coarser aggregates, or ?
> |
> |I wouldn't mind just "allow".  Beyond that has serious implications
> |that have to be thought through.
> 
> 
> scalability as coarser aggregates.  However, we have not yet
> discussed what level of scalability is a necessity.  Yet another
> item on the discussion list...

"at the same level of scalability" ... I have decided I can't figure
out what you mean.  Are you saying that if we can support 10^10
prefixes we should be able to support 10^10 individual entries as
well?

Scott

---

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

|> I would think that we would want to support it as the same level of
|> scalability as coarser aggregates.  However, we have not yet
|> discussed what level of scalability is a necessity.  Yet another
|> item on the discussion list...
|
|"at the same level of scalability" ... I have decided I can't figure
|out what you mean.  Are you saying that if we can support 10^10
|prefixes we should be able to support 10^10 individual entries as
|well?

No, I was suggesting that we should support N entries, regardless of the
scope of each entry.

Tony

---

From: Scott Brim <[email-masked]>
Date: Fri, 21 Mar 2008 17:53:23 -0400

Excerpts from Tony Li on Fri, Mar 21, 2008 02:32:25PM -0700:
> No, I was suggesting that we should support N entries, regardless of
> the scope of each entry.

So, the cost of an individual entry should be the same regardless of
the scope of the entry??

---

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

|> No, I was suggesting that we should support N entries, regardless of
|> the scope of each entry.
|
|So, the cost of an individual entry should be the same regardless of
|the scope of the entry??

Sure, why not?

Tony

---

From: Robin Whittle <[email-masked]>
Date: Sat, 22 Mar 2008 12:54:16 +1100

The granularity specification has some unavoidable implementation
implications which I think sufficiently impact the scaling of the
whole map-encap system that we should make the choices I suggest here.

I have changed my preference for IPv6 mapping granularity from an
integer number of IP addresses to a power of two number of /64 prefixes.

For IPv4 I support what I suggested and Tony provisionally accepted:

  http://psg.com/lists/rrg/2008/msg00935.html

which results in:

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

Which I would refine to meaning:

   Arbitrary starting point (32 bits) and arbitrary length
   up to the length of a /8 (24 bits).

However, for IPv6 I now support a granularity scheme which requires
less information be stored and conveyed, with a coarser granularity.

   Prefixes of /64 prefixes, specified by a 64 bit base
   address and a 6 bit prefix length - where the base
   address bits to the right of the prefix length should
   be zero, and will be regarded as zero if not so.

I think most people will be happy with my IPv6 proposal - although
unfortunately this means I now disagree with Brian Carpenter.

The IPv4 approach is non-conventional.  Instead of the traditional
prefix approach (32 + 5 bits = 5 bytes) this will require 32 + 24
bits = 7 bytes.)  This is a 40% increase in storage and on-the-wire
requirements, for this part of the mapping information.  However,
the whole body of mapping information for each micronet (each EID
prefix) is longer than this, so it is less than a 40% increase in
the whole thing - in the database in RAM or in a mapping update or
reply message.

The benefit is that each micronet can then be of any length, and
have any starting address.

Suppose an end-user has 8 IP addresses in their User Address Block.
 Initially they have it split 4-4 into two micronets.

Now they want to change things a little, to be 5-3.

With my proposal, the result is still 2 micronets.

  x.y.z.0  Micronet a }
  x.y.z.1  Micronet a }
  x.y.z.2  Micronet a }    Mapping A
  x.y.z.3  Micronet a }
  x.y.z.4  Micronet a }
  x.y.z.5  Micronet b   }
  x.y.z.6  Micronet b   }  Mapping B
  x.y.z.7  Micronet b   }

However, with the 32 bits plus a prefix (conventional) approach,
they would be forced to create 2 additional micronets:

  x.y.z.0  Micronet w  }
  x.y.z.1  Micronet w  }  Mapping A
  x.y.z.2  Micronet w  }
  x.y.z.3  Micronet w  }
  x.y.z.4  Micronet x     Mapping A
  x.y.z.5  Micronet y     Mapping B
  x.y.z.6  Micronet z       }
  x.y.z.7  Micronet z       } Mapping B

So with the conventional approach, end-users who want (more likely
really need) to maximise the use of their address space would often
be forced to create additional micronets.

This would bloat the database size, and require more updates (push)
or more mapping requests and responses (pull).  (Ivip uses global
push and local pull.  LISP-ALT and TRRP are full pull on a global
basis.)

For instance, for pull, an ITR requests the mapping for x.y.z.6.  In
my system, it gets back the mapping information for micronet b.

In the conventional (power of 2 lengths) system, it gets back the
mapping information for micronet z.

When the ITR subsequently has to handle a packet addressed to
x.y.z.5, in my integer length system, it already has the mapping -
so there is no need for delay, a request or a reply.  With the
conventional approach, it needs to request mapping again, and later
gets the mapping for micronet y.

The ITR in my system caches a single micronet while an ITR in the
power of 2 system winds up caching two micronets.

Here are the major arguments for integer lengths for IPv4:

  1 - The address space is scarce and precious.  Collectively, we
      want and need end-users to use their address space fully, so
      they don't have to ask for as much of it as if they could only
      slice and dice it in a clunky power of 2 manner.  Likewise,
      since each end-user won't be able to obtain much space, we
      need to  provide them with a map-encap scheme which enables
      them to get the most use out of whatever they obtained.

  2 - Having a full arbitrary integer length specifier for IPv4 only
      costs 24 bits, since no practical micronet will encompass more
      than a /8.  This is only 19 bits more than the conventional
      prefix-based power of 2 approach.

The same principles apply if the end-user has 8,096 or 8,388,608
IPv4 addresses.  There will be tens of millions of end-users with 8
IP address and hundreds of thousands with 8k.  The same arguments
apply: the only way of optimising address space usage and meeting
the changing needs of end-users whilst minimising the number of
micronets and updates to micronets is to use an integer for the length.

I initially extended this idea to IPv6, not just to the /64
granularity which I think should actually be used, but in accordance
with Brian Carpenter's suggestion that the architecture shouldn't
constrain granularity to anything coarser than single IP addresses.

That results in 128 bits of starting address and in 128 bits (or
maybe a few less) of length.

I think the resulting 32 byte data format would be really verbose
and wasteful, so I proposed that Ivip would be capable of doing that
if it was needed at some stage in the future, but would be initially
(probably forever) deployed in a form which assumed /64 granularity,
with arbitrary start point and arbitrary length.  This would be 64 +
64 bits = 16 bytes.

However, I am not convinced we need to use exactly the same
principles for defining mapping granularity in IPv4 as in IPv6.

Following Brian's suggestion of going right down to individual IPv6
addresses, using prefixes for power of 2 length specifications,
results in:

  128 bit of base address + 7 bits for prefix length = 17 bytes

I think it would be better to define the mapping system's IPv6
granularity as 64 bits for the starting point (/64 granularity) with
6 bits for the prefix length.

This results in:

  64 bit of base address + 6 bits for prefix length = 9 bytes

This saves 8 bytes of storage and transmission bandwidth, compared
with the full 128 bit system, and is only 2 bytes more than the
integer length IPv4 system.

This saving of space just for storing the total mapping record

   Start and length information of address area covered by this
   mapping

   Mapping information itself

in a query server (ETR in LISP-ALT, Default Mapper in APT) or ITR,
or for sending the mapping information from the query server to the
ITR.  It also reduces the number of bits which need to be sent in an
ITR to query server mapping query, from 128 to 64.

This means that all IPv6 micronets would be on binary boundaries,
power of two lengths etc. of /64  I think this will be flexible
enough for most end-users - and the efficiency of address usage
arguments of IPv4 do not apply.

Even with the concept of one host per /64, IVv6 has such a large
address space that I think it there is little or no significant
detriment in forcing end-users to slice and dice their space in
powers of 2.  The IPv4 example above - trying to squeeze
changing-size micronets into a small space - wouldn't apply, since
there are vast swathes of address space up for grabs, and it would
be easy to have MABs (Mapped Address Blocks, advertised in BGP and
split into thousands of User Address Blocks with multiple micronets)
so large that you could have thousands of UABs, each with thousands
or millions of /64s.

Let's say we invent 64k MABs, each a /32.  This is one 1/65,536 of
total IPv6 space.  Each MAB has 64k /48s - and we make each /48 into
 a UAB, providing a UAB for each of 4 billion end-users.

Each such end-user now has 64k /64 prefixes (each with potentially a
bazillion hosts) to define into one or more micronets, so I don't
think it is going to be a bother to make each micronet a power of 2
number of /64s in length.

Another advantage of sticking to /64s is we already have CPUs which
handle the 64 bits in play in single instructions.  Enforcing all
storage, software, communications etc. to cope with 128 bits would
be burdensome - and as far as I can see, would never really be needed.

I propose a new recommendation:

  3.1.1.1.  Recommendation

    mapping entries for:

     IPv4: One or more contiguous host identifiers, with arbitrary
           starting point and a length between 1 and 16,777,215.

     IPv6: Prefixes of /64 prefixes, specified by a 64 bit base
           address and a 6 bit prefix length - where the base
           address bits to the right of the prefix length should
           be zero, and will be regarded as zero if not so.

Here is a proposed explanation to precede it, based on Tony's text,
my mssg 933, this message and an attempt to convey something which
encompasses the purpose of Scott's text (mssg 950).

  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 more scalable because
  it reduces the amount of information needed in the mapping
  function to cover any given range of addresses.  A smaller "grain
  size" increases the finesse with which an area can be defined, at
  the cost of increasing the information to be stored in and
  transferred between elements of the mapping system and other
  elements which need to use the mapping information.

  Fine grain control of the area to which a single mapping applies,
  particularly with an integer number of that grain size to define
  the length of the area, enables end-users to make the most
  efficient use of limited address space.  For instance, if it was
  desired to have 3 contiguous grain sizes of space have the same
  mapping, this could be achieved with a single map entry, rather
  than multiple entries each of which is restricted to a power of
  two number of grain sizes.

  Shifting the scalability problem from today's routing protocols
  and forwarding plane to tomorrow's mapping function simply moves
  the problem.  While the new architectural solution is intended
  to be far more efficient and scalable than the current system,
  ever mapping solution has its own relationship between number
  of mappings and both cost and practicality.

  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 fine-grain mapping does not imply
  that a practical implementation could necessarily cope with the
  number of minimal sized mapping areas which fit into the total
  available address space.

    - Robin                  http://www.firstpr.com.au/ip/ivip/

---

From: "ext Scott Brim" <[email-masked]>
Date: Fri, 21 Mar 2008 15:25:36 -0400

Scott

---

From: "ext Robin Whittle" <[email-masked]>
Date: Sat, 22 Mar 2008 12:54:16 +1100

which results in:

  x.y.z.0  Micronet a }
  x.y.z.1  Micronet a }

  x.y.z.0  Micronet w  }

This results in:

  3.1.1.1.  Recommendation

  3.1.1.  Granularity

---

From: "Stephen Sprunk" <[email-masked]>
Date: Sat, 22 Mar 2008 23:55:39 -0500

Thus spake "Olivier Bonaventure" <[email-masked]>
>> for both host identifiers and their aggregates.

"should"?  I'd make that a MUST.

> for aggregates of identifiers. It MAY also support mapping entries for 

I cannot imagine how a mapping system could be capable of mapping aggregates 
of identifiers without also being capable of mapping individual ones.

Presumably we've all learned our lessons from the VLSM and CIDR days, and 
the aggregate would have some sort of size tagged to it (either a prefix 
length as in LISP or a run length as in Ivip).  One extreme end of that size 
will be the entire identifier space, and the other end will be a single 
host.  It's more work to make those things disallowed than it is to leave 
them in.

That said, there's plenty of reason to expect that mappings for individual 
hosts might be filtered out or prohibited for policy reasons, due to 
resource constraints.  However, that's no reason to leave the capability out 
of the protocol level.

S

Stephen Sprunk         "God does not play dice."  --Albert Einstein
CCIE #3723         "God is an inveterate gambler, and He throws the
K5SSS        dice at every possible opportunity." --Stephen Hawking

---

From: Xu Xiaohu <[email-masked]>
Date: Tue, 25 Mar 2008 16:20:43 +0100

> a scalability viewpoint is the potential churn, not the amount of storage.

The storage pressure of the mapping server can be alleviated by using
distribute system, however, the storage pressure on ITR's cache can not be
neglected.

Best wishes,
Xiaohu XU

---

From: "William Herrin" <[email-masked]>
Date: Tue, 25 Mar 2008 13:16:50 -0400

>  of identifiers without also being capable of mapping individual ones.

Stephen,

In a monolithic push system you'll want to aggregate maps as they
become distant from their origin. When asking whether the mapping
function must support individual host identifiers, we're really asking
whether that aggregation is permitted to be mandatory or whether it's
only allowed to be opportunistic.

I say the latter: the mapping function MUST support mapping entries
for individual host identifiers anywhere such is necessary to achieve
the origin's desired functionality. Otherwise we're back to wasting an
entire /24 (or whatever the distance aggregate is) in order to support
a single anycasted server.

Regards,
Bill Herrin

-- 
William D. Herrin [email-masked] [email-masked]
3005 Crane Dr. Web: <http://bill.herrin.us/>
Falls Church, VA 22042-3004

---

From: Brian E Carpenter <[email-masked]>
Date: Wed, 26 Mar 2008 10:32:30 +1300

> a single anycasted server.

Well, that's a side-effect of BGP filtering practice, isn't it?
As far as I can see, filtering simply won't be possible or
meaningful in map distribution, so an anycast address will
normally be mapped 1:n to a set of RLOCs (i.e. will have n
1:1 mappings). It's highly unlikely that any of those
mappings could aggregate with any other prefix mapping to
the same RLOC.

    Brian