We have studied this problem (i.e., map-proliferation due to holes in
EID prefixes) in some detail in the proposal that I have submitted on
"Enhanced Efficiency of Mapping Distribution Protocols (EEMDP) ...."
Please see a detailed document at:
(I posted a substantially updated document earlier today.)

Fig. 3 in the document provides a real-world example of it,
and Fig. 4 provides statistics on occurrence of holes in
prefixes based on RouteViews trace data.
Our main purpose in the document is to develop a methodology
for enhancing the mapping distribution protocol so that
the existence of prefix-holes (or exceptions) can be
managed efficiently without excessive proliferation of
mapping entries and mapping messages.
In Section 3.A and in Table I (pp. 7-9), there is a new detailed
description of the previously proposed mapping response algorithms.


From: rrg-boun...@irtf.org [mailto:rrg-boun...@irtf.org] On Behalf Of Flinck, 
Hannu (NSN - FI/Espoo)
Sent: Monday, March 08, 2010 6:39 AM
Subject: Re: [rrg] LISP does not implement Locator / Identity Separation

Hello Damien,

Robin had in his mail a following example that relates the issue:

Robin wrote:
  It might be messy, for instance, to make a single IPv4
EID have a separate EID prefix if it was in the middle of an existing
EID prefix.   If it was the 09 address in a 16 IPv4 address /28
prefix, then there would need to be a bunch of separate EID prefixes to make up 
the full 16 addresses:

   0 -  7    /29 EID prefix mapped to ETR N.
   8         /32 EID prefix mapped to ETR N.
   9         /32 EID prefix mapped to ETR Z.
  10 - 11    /31 EID prefix mapped to ETR N.
  12 - 15    /30 EID prefix mapped to ETR N.

As the above example shows how hole bunching of an EID block will case multiple 
entries. In Robin's example there are only  two ETRs (N and Z), but the same 
hole bunching is likely to happening with many sites with their allocated EIDs.

- Hannu

Damien Saucez wrote:

> If  end devices do not renumber, then the mapping system needs to
> reconstruct its structure, or then the blocks will deaggregate.
I do not follow you? The cache, yes, it needs to do some kind of compression if 
too many entries have to be installed, but again, in practice, you will have to 
scale to your traffic, not the Internet, you can thus provision your routers 

> Migration of a single subsidiary from an enterprise to an other is not
> a big issue, I can see that, but over the time migration of small
> sites seems to be quite common. They keep on coming and going. This
> will lead to the extreme case that there would be long prefixes at the
> very top of the mapping system if we stick to the original allocation.
> And then all of the map-requests will go through the top of the
> mapping system. At least with the DNS of today that is not the most ideal 
> case.

I am not sure to understand the problem. A well design mapping system should 
not take care of the number of mappings. Having a lot of prefixes for the same 
entity will generate a lot of different mappings, but, the overall mapping 
system does not take care about this. I see the mapping system as a set of 
pointer, each node point you to a more specialized node until you arrive a node 
able to provide you the mapping. So that, a node only need to know what is 
under the responsibility of its neighbors. This is true that in a mapping 
system like NERD we will have scalability troubles in the case of a lot of 
small mappings, but ALT will not suffer it is correctly deployed.
rrg mailing list

Reply via email to