Subject: Re: [rrg] rrg Digest, Vol 15, Issue 44

From: wei zhang <[email-masked]>
Date: Sat, 26 Dec 2009 00:52:49 +0800

> On Dec 17, 2009, at 1:02 AM, Flinck, Hannu (NSN - FI/Espoo) wrote:
>
>> Most of the scalability discussions we have had are dealing exactly
>> with
>> the mapping system, not how to tunnel or rewrite the addresses. The
>> mapping system is the architecture that uses the tunnels or address
>> manipulation based on some address structure.  A tunneling
>> scheme/address rewrite together with an address structure is not
>> sufficient for scalabilty.
>>
>> - Hannu

> Hi Hannu,
>
> I agree that the mapping itself is a critical part of the
> architecture. However I believe a mapping proposal needs to go
> together with an overall architecture, because one needs to know where
> mapping happens, mapping what to what.
> Take a simple example: ILNP has kind of mapping (implemented in DNS)
> and LISP has another kind of mapping, 2 different proposals have
> rather different mappings.
>
> Lixia
>
>> -----Original Message-----
>>> From: [email-masked] [mailto:[email-masked]] On
>>> Behalf Of ext Tony Li
>>> Sent: Tuesday, December 15, 2009 11:52
>>> To: Brian E Carpenter
>>> Cc: [email-masked]; Lixia Zhang
>>> Subject: Re: [rrg] belated msg: further description of the
>>> recommendation process
>>>
>>> Brian E Carpenter wrote:
>>>
>>>>> Mapping systems are obviously a component of a solution but are not
>>>>> by themselves a solution.  To be considered seriously, they
>>> should be
>>>>> used in conjunction with some network layer solution.
>>>>
>>>> Hmm. Don't you think that to some extent these should be orthogonal?
>>>> A mapping mechanism needs to meet the specific requirements of a
>>>> network layer mechanism, but that doesn't require the two to be
>>>> irrevocably bound to each other.
>>>>
>>>> I have a feeling that the mapping system should be very general in
>>>> nature, in case the first cut at either the locator or identifier
>>>> space proves to fall short. Also I feel it should support hierarchy,
>>>> even if we don't need a hierarchy from the start.
>>>
>>> Brian,
>>>
>>> Our recommendation is focused on providing an alternative
>>> routing architecture.  A mapping system is a fine component,
>>> but would not seem to provide a credible architecture by itself.
>>>
>>> Tony
>>>
>>> _______________________________________________
>>> rrg mailing list
>>> [email-masked]
>>> http://www.irtf.org/mailman/listinfo/rrg
>>>
>

Hi, all

It seems to me the logic is inside the routing architecture. A
scalable routing architecture intrinsicly requires properly designed
routing hierarchy with topology sensitive aggregateable address
(RLoc/PA addr. or sth like that). On the other hand, the upper layer
over IP requires a fixed interface with layer 3 which is not topology
sensitive and globally unique(EID/Host ID). This contradictory
requirements partly incurred ID/Loc seperation and inevitably a
mapping between them. If we introduce this kind of Locator and ID into
the routing scheme, the routing with the aggregateable hierarchy can
be scalable for sure, but the mapping scalability may not be
guaranteed or even worse, inefficient for another lookup besides
routing. As a consequence, we shift the routing scalability problem to
the mapping scalability problem.

Therefore many proposals focus their artifice on mapping mechanisms to
find a final solution for the scalability problem.To make the mapping
system scalable becomes the ultimate resort to settle this issue down.
However many efforts dispersed our attention on overheads,
security(e.g. LISP NERD) or performance (e.g. data probe in LISP ALT )
etc. We should attack the core directly and make the mapping system
scalable before we deduce a perfect mapping mechanism.

A good answer is that the EID should also be aggregateable, but the
aggregation is independent of routing topology. EID aggregation can be
implemented in many ways (even virtually or conceptually). Anyway we
need a corse EID granularity in the mapping scheme.

If we put these pieces together, a hierarchically organized RLoc and a
corse EID aggregation are prerequisites of a scalable mapping and
routing. Under such circumstances, the number of entries in the
mapping system will admirably scale with Internet size.

I agree the mapping scheme must be imbedding in a certain routing
architecture, just like addressing scheme in a routing mechanism.
However the EID aggregation design can be relatively independent and
be treated as a general design. Later on, how to deploy and implement
mapping system will be either illustrated on the core/edge split
(with tunnel or rewrite) abstraction or with other new designs.

As a summary, towards the scalable Internet routing architecture, the
route map can be like this: design a routing hierarchy with
aggregateable Locator, design ideal EID aggregation to facilitate
scalable mapping, design efficent mapping scheme with specific
forwarding mechanism, at last polish all designs with various
operational requirements.

Merry Christmas!

Wei Zhang

---

From: Brian E Carpenter <[email-masked]>
Date: Sat, 26 Dec 2009 08:32:21 +1300

On 2009-12-26 05:52, wei zhang wrote:
...
> A good answer is that the EID should also be aggregateable,

I may be missing what you mean, because it seems to me that
any set of bit strings (even of variable length) is aggregatable
to an arbitrary extent. Just build a binary tree and chop it
off at whatever level you want (/N if you want 2^N aggregates).

(The equivalent has to be true for namespaces using n-ary instead of
binary symbols.)

    Brian

---

From: Xu Xiaohu <[email-masked]>
Date: Sat, 26 Dec 2009 09:20:35 +0800

> -----邮件原件-----
> 发件人: [email-masked] [mailto:[email-masked]] 代表 Brian E
> Carpenter
> 发送时间: 2009年12月26日 3:32
> 收件人: wei zhang
> 抄送: [email-masked]
> 主题: [rrg] Aggregatable EIDs
> 

Agree. Even the EID is a flat label, the corresponding ID->Locator mapping
system could scale well by using some methods, e.g., DHT.

IMO, a major reason that the EID should be hierarchical is as follows: 

The resolution infrastructure for flat names has no "pay-for-your-own”
model, as the flat names are stored at essentially random nodes. In
contrast, the resolution infrastructure for the hierarchical host
identifiers has reasonable business models and clear trust boundaries. Since
the hierarchical host identifiers have clear organization affiliation, the
identifier resources and the corresponding mappings can be managed by
different bodies with clear administrative boundaries.

Xiaohu

---

From: wei zhang <[email-masked]>
Date: Sat, 26 Dec 2009 12:42:11 +0800

Hi, Brian and Xiaohu

My response to your comments inline.

>> off at whatever level you want (/N if you want 2^N aggregates).
Here the EID aggregation is based on the same mapping information,
e.g. if 2 neighboring /16 EIDs map to different RLocs, there needs at
least 2 entries in the mapping system for this discrimination.
Therefore they are not "aggregateable"  if concerned by scalable
mapping.

> system could scale well by using some methods, e.g., DHT.
DHT also builds fine hierarchies within its scheme, or to say a flat
label can be organized in a logic hierarchical structure. Indeed
hierarchical structure helps to alleviate scalability problems, but it
might be prudent to say it scales "better" (than flat label) instead
of "well" if we are facing an already massive mess. IMHO, to make EID
organized/assigned in an "aggregateable" way beforehand can be easier
than to find any aftermath remedies.

> different bodies with clear administrative boundaries.
I agree. Hierarchically organized EID with some constraints on its
assignment(clear organization affiliation) guarantees scalable
mapping, since theoretically the information entropy reduced.
However, before anyone enforces these constraints in the Internet, we
need to define the hierarchy with corresponding range of effects which
is my intention of designing "aggregateable" EID on behalf of ID/Loc
mapping scalability.

Wei Zhang

---

From: Brian E Carpenter <[email-masked]>
Date: Sun, 27 Dec 2009 08:34:34 +1300

Hi,

> Therefore they are not "aggregateable"  if concerned by scalable

That seems to describe EIDs that have topological significance, and I don't
understand how that works.

> mapping, since theoretically the information entropy reduced.

I don't understand. There's no reason in physics or economics why
customers that happen to be adjacent in an ISP's address allocation
scheme should be adjacent in any scheme of organisational affiliation.
This argument fails for exactly the same reason that geographically
based BGP aggregation fails.

I'm not saying there is zero correlation. Obviously, two customers
in the same city are more likely to use the same ISP than two customers
in different countries. But can you point to studies that show that
the observed correlation is enough to significantly affect aggregation?
Significantly means: this would scale a lot better than BGP aggregation
scales today, otherwise we have gained nothing from the loc/ID split.
I'm puzzled how this could be, since if there is such a correlation,
it would also help BGP aggregation.

My understanding of the value of the loc/ID split is not that it
benefits from aggregation in the ID space, but rather that the
cost of non-aggregation is acceptable in the ID-to-loc map
because it is not subject to the performance constraints of
a routing protocol.

    Brian

---

From: "Joel M. Halpern" <[email-masked]>
Date: Sat, 26 Dec 2009 14:40:06 -0500

Two points of clarification:
1) EIDs need to be aggregatable only if they are used as look up keys. 
If they are never the key for a lookup (and some proposals have that 
property) then aggregatability is a non-issue.
2) The corollary to 1 is that EIDs only need to be aggregatable in the 
structure in which they are looked up.  If they are looked up in the 
routing system, then they need to be topological.  If they are looked up 
in something else, then they need to right structure for that something 
else.  If the EID is a DNS name, then the DNS structure defines its 
aggregatability.  If it is looked up in a binary delegation tree, then 
that defines the structure.  If they are looked up in a DHT, and we are 
prepared to mandate a DHT, then again they don't need aggregation 
properties.
2') It is very likely that EIDs will have at least delegation oriented 
aggregation, unless we resort to random EID creation.

Yours,
Joel M. Halpern

---

From: wei zhang <[email-masked]>
Date: Sun, 27 Dec 2009 16:30:34 +0800

Hi, Brian:

Thank you for your enlightening arguments. A pleasure to have in depth
discussion with you.

> understand how that works.

Of course, individual EID has no topological significance, but we are
trying to make them in "groups" in the mapping system, otherwise we
might need to map each IPv4 EID in /32 to their Rlocs.   Practically,
we use LAN prefixes to group them, you may regard this constraint as
"topological significance". And we hope to make this granularity even
more coarse by certain feasible aggregation, then we might need more
constraints on different levels(e.g. AS level, country, RIR).

> because it is not subject to the performance constraints of
IP address allocation has few constraints on prefixes usage, since
there seems no "physics and economics reason" to do so. At the
beginning, BGP scaled well. Later on BGP encountered great
difficulties when it tried to aggregate fragmented IP prefixes. If we
retrospectively reconsider the lessons learned from IPv4, we might
need to admit that some constraints are helpful if it is not too much
troublesome, which definitely have the aggregation significance on
scalability.

Then how to design the constraints (e.g. the one you have mentioned
previously) which may  significantly facilitate aggregation or
scalability? The answer can be complicated where we may need physics
and economics reasoning. BGP is hard to be adapted to enforce new
constraints, since it is too overwhelming and on duty all the time.

Now ID/Loc split offers us an opportunity to put things back on the
right track, although it has many other appreciating values. If we
take it for granted that the cost of non aggregatable EID mapping will
not influence the performance of a routing protocol, we might repeat
the story of IPv4 allocation and BGP.

Wei Zhang

---

From: Xu Xiaohu <[email-masked]>
Date: Tue, 29 Dec 2009 10:21:44 +0800

> -----邮件原件-----
> 发件人: [email-masked] [mailto:[email-masked]] 代表 Joel M.
> Halpern
> 发送时间: 2009年12月27日 3:40
> 收件人: Brian E Carpenter
> 抄送: [email-masked]; wei zhang
> 主题: Re: [rrg] Aggregatable EIDs
> 

I fully agree to the above clarification! 

Then the question is: among the delegation oriented aggregation and the
random creation, which one is the better choice for EIDs? Or do we need a
third option, a compromise between these two options, e.g., one part of the
EID is delegation-oriented aggregatable, while the other part is randomly
created?

Xiaohu

---

From: wei zhang <[email-masked]>
Date: Tue, 29 Dec 2009 12:11:53 +0800

> EID is delegation-oriented aggregatable, while the other part is randomly
 I agree to differentiate EIDs into different groups (maybe in
different mapping systems), not only it is possible with delegation
oriented and  random, but we can have 'stable" and "mobile" as well (
just like the mobile phone number and wired phone number). There won't
be harmful to deploy more than one mapping system in the Internet and
most likely scalable for a long run.

 Here we are touching the EID fundamental features. I quote RRG's
terminology for ID:
 An identifier is the name of an object at a given layer; identifiers
have no topological sensitivity, and do not have to change, even if
the object changes its point(s) of attachment within the network
topology. Identifiers may have other properties, such as the scope of
their uniqueness (local or global (default)), the probability of their
uniqueness (statistical or absolute (default)), and their lifetime
(ephemeral or permanent (default)).

Since there might be contradictory properties why not we put them into
different boxes. ID can hardly be changed once it is put in use, why
not arrange them properly beforehand. If we hold this to be ture, we
may get hierarchical aggregatable delegation EID mapping system(s),
mobile/ephemeral random EID with DHT mapping system(s), which of
course will not interfere connections between any pair of EIDs. What
we need is to draw the demarkation between them and let ITR knows how
to map different EIDs.

RFC

Wei Zhang