Subject: [RRG] Generic requirements on mapping mechanisms

From: Olivier Bonaventure <[email-masked]>
Date: Tue, 11 Mar 2008 15:15:43 +0100

Hello,

Today, there is a generic discussion on mapping during the RRG meeting. 
Unfortunately, I'm not in Philapdelphia, but I would like to list a few 
requirements that I consider important. These requirements are 
independant of the particular mapping mechanism used.

Comments are welcome

Olivier

---------------------------------------------------------

The mapping mechanism will be used to map a (set of) identifier(s) on a 
set of locators, formally

{EIDs} -> {Loc1, Loc2, Loc3}

 From a generic/abstract viewpoint, I think that the following 
requirements are important :

1. Locators and EIDs

Locators and EIDs will be allocated by a central authority, such as IANA 
or deleguates like RIPE, ARIN, APNIC, ...  This central authority is 
important to ensure uniqueness of the locators and of the EIDs.

I assume that locators will be IPv4 or IPv6 addresses. EIDs could be 
something else.

2. For scalability reasons, the mapping mechanism must allow to map a 
(preferably large) set of identifiers on a set of locators.

This implies that EIDs will need to be allocated in contiguous blocks 
and not individually.  The size of the EID set will affect the 
scalability of the system. Using large EID sets will make the mechanism 
more scalable. Thus, the central authorities should allocate large EID 
blocks.

To avoid the scalability problems that we have today with interdomain 
routing, the owner of the EIDs should support the cost of using small 
EID sets. A possible way to ensure this would be to force the an owner 
of an EID block to always reply with a mapping that is valid for the 
entire block and optionnally add mappings for subsets of the EID block, 
e.g. for traffic engineering purposes.

3. There should be a way to secure the mapping replies

It should be possible for an entity that requests a mapping to verify 
the validity of the reply. Some entities may assume that any received 
reply is by definition valid, but such a behaviour raises serious 
security issues. The mapping mechanism should allow an entity to verify 
that a reply is correct and valid. This could be a cryptographic 
verification based on signatures or an online verification where a 
server responsible for the EID block is contacted to validate a mapping.

4. A mapping will have a limited lifetime.

No mapping can be permament and the mapping reply should contain the 
lifetime of this mapping. This is similar to the TTL in the DNS. A long 
lifetime will favor scalability while a shorter lifetime will ease 
traffic engineering by allowing a site to update regularly its map 
replies. As for requirement 2, the cost of using short lifetimes should 
be supported by the site that is using those short lifetimes, not by the 
entire mapping system.

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

---

From: Scott Brim <[email-masked]>
Date: Tue, 11 Mar 2008 15:51:51 -0400

> important to ensure uniqueness of the locators and of the EIDs.

s/authority/authorities/.  The authorities for Locators and EIDs could 
be independent, and different EID address families could also use 
different authorities.

> e.g. for traffic engineering purposes.

You imply that if long prefixes are "advertised", nodes other than the 
owner will suffer.  Not necessarily -- depending on the mapping system 
design.  Would your real requirement be that nodes not be required to 
maintain the entire EID prefix set?

> be supported by the site that is using those short lifetimes, not by the 

I don't know how to do that.  Can you give an example?

Scott

---

From: "William Herrin" <[email-masked]>
Date: Tue, 11 Mar 2008 16:27:33 -0400

>  be supported by the site that is using those short lifetimes, not by the

Olivier,

There may be other useful ways to guarantee that knowledge of any
state change in the mapping system propagates to all interested
parties in a "reasonable" amount of time. I'm trying to put together a
list and any assistance would be appreciated. Refer to
http://bill.herrin.us/network/statechange.html

Regards,
Bill Herrin

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

---

From: Olivier Bonaventure <[email-masked]>
Date: Tue, 11 Mar 2008 21:42:13 +0100

Scott,
>> Locators and EIDs will be allocated by a central authority, such as 
>> IANA or deleguates like RIPE, ARIN, APNIC, ...  This central authority 
>> is important to ensure uniqueness of the locators and of the EIDs.
> 
> be independent, 

Agreed

> and different EID address families could also use 
> different authorities.

Agreed, but I hope that there won't be too many EID address families.

>> entire block and optionnally add mappings for subsets of the EID 
>> block, e.g. for traffic engineering purposes.
> 
> owner will suffer.  

If long prefixes are advertised, and the worst case are host-specific 
prefixes, then other nodes may suffer depending on the mapping system.

> Not necessarily -- depending on the mapping system 
> design. 

If the design of the mapping system ensures that other nodes do not 
suffer, that's fine.

> Would your real requirement be that nodes not be required to 

Another way to express the requirement could be that nodes are not 
forced to use the more specific mappings that they receive. These more 
specific mappings may improve the performance but they decrease 
scalability and using these more specific mappings should only be an 
optionnal optimisation, not the default.

>> lifetime of this mapping. This is similar to the TTL in the DNS. A 
>> long lifetime will favor scalability while a shorter lifetime will 
>> ease traffic engineering by allowing a site to update regularly its 
>> map replies. As for requirement 2, the cost of using short lifetimes 
>> should be supported by the site that is using those short lifetimes, 
>> not by the entire mapping system.
> 

In the case of the DNS, some of the cost of using short TTLs is 
supported by the owner of the domain names with a short TTL. The 
resolvers of nodes that resolve those domain names also suffer some 
cost, but the nodes that do not contact these domain names do not suffer 
  the additional cost. In this case, there is some cost (replying to 
more DNS requests) for the domain that chooses to use short lifetime. 
This is not perfect since the resolvers that contact this domain also 
support some cost.

Olivier

---

From: Scott Brim <[email-masked]>
Date: Tue, 11 Mar 2008 17:14:31 -0400

On 3/11/08 4:42 PM, Olivier Bonaventure allegedly wrote:
>> and different EID address families could also use different authorities.
> 

I'm sure there will only be a few :-)

> forced to use the more specific mappings that they receive. 

I like it.

>  the additional cost. In this case, there is some cost (replying to more 
> DNS requests) for the domain that chooses to use short lifetime. This is 
> not perfect since the resolvers that contact this domain also support 
> some cost.

OK.  I thought perhaps you had a way of removing even that cost.

Scott

---

From: "Tony Li" <[email-masked]>
Date: Tue, 11 Mar 2008 17:34:21 -0400

|> In the case of the DNS, some of the cost of using short TTLs is 
|> supported by the owner of the domain names with a short TTL. The 
|> resolvers of nodes that resolve those domain names also suffer some 
|> cost, but the nodes that do not contact these domain names 
|do not suffer 
|>  the additional cost. In this case, there is some cost 
|(replying to more 
|> DNS requests) for the domain that chooses to use short 
|lifetime. This is 
|> not perfect since the resolvers that contact this domain 
|also support 
|> some cost.
|
|OK.  I thought perhaps you had a way of removing even that cost.

One way of shifting that cost further is for the advertising site to
proactively issue updates based on historical requests.

Tony

---

From: Scott Brim <[email-masked]>
Date: Wed, 12 Mar 2008 16:14:03 -0400

Excerpts from Tony Li on Tue, Mar 11, 2008 05:34:21PM -0400:
> > resolvers of nodes that resolve those domain names also suffer
> > some cost, but the nodes that do not contact these domain names do
> > not suffer the additional cost. In this case, there is some cost
> > (replying to more DNS requests) for the domain that chooses to use
> > short lifetime. This is not perfect since the resolvers that
> > contact this domain also support some cost.
> 

Are you suggesting that if the advertising site does this, the caching
site could toss out cache entries more casually, because they are
likely to be refreshed?  I wonder if proactive updates will increase
both the cost of caching and the cost of processing updates even more,
because updates will be sent and processed even when they are not
needed.

---

From: "Tony Li" <[email-masked]>
Date: Thu, 13 Mar 2008 16:07:08 -0400

|> One way of shifting that cost further is for the advertising site to
|> proactively issue updates based on historical requests.
|
|Are you suggesting that if the advertising site does this, the caching
|site could toss out cache entries more casually, because they are
|likely to be refreshed?  I wonder if proactive updates will increase
|both the cost of caching and the cost of processing updates even more,
|because updates will be sent and processed even when they are not
|needed.

No, I'm saying that having the advertising site issue proactive updates
might be cheaper (on the caching side) than having the caching site send
refresh requests.  The caching site might want to have the ability to
terminate the proactive updates.

Over the lifetime of a non-trivially lived cache entry, this could shift
more of the burden to the advertiser.

Tony

---

From: Lars Westberg <[email-masked]>
Date: Fri, 14 Mar 2008 08:53:49 +0100

What are the implementation requirements on the routing system?

In my mind, all of the routers (at that time) will probably be based on 
ASIC-design and main limitation in the forwarding. If we are looking in 
the future,  the routers has to be to forward multi-100G capacity and 
the throughput demands simplicity. If we develop a new routing systems 
that imposing a requirement on a certain flexibillity and complexity, 
this will cause hardware implementation problems.

Therefore, I missing the implementation design aspects into the 
discussion. I would rather prefer that we differentiate the solution 
space depending of the problem to solve.

so let's try::
    -differentiate solutions for different problems
    - Keep simplicity and avoid complexity in forwarding.

-Lasse