Re: [RRG] Consensus check: mapping granularity

[Robin Whittle <rw@firstpr.com.au>]

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

    The identifier to locator mapping function should support
    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/


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