[e2e] a means to an end

[Pekka Nikander]

On 9 Sun, 9 Nov 2008 09:25:38 +0200, Pekka Nikander wrote:
>> Path-specific locators

On 10 Nov 2008, at 19:09, Noel Chiappa wrote:
> Let me make sure I understand what you mean by this term. To me, it  
> implies 'a source route composed of names of only local scope' -  
> whether the 'names' refer to outbound-interface/next-hop pairs, or  
> local flow names, or whatever, I don't have any specific concept.

That is one particular way of implementing path-specific locators.

More generally, I may have been better referring to "location-specific  
locators", or "sender-specific locators", but both might have been  
even more confusing, IMHO.

The general idea is to construct locators that are only useful along a  
specific path, at a specific location or region, or for a specific  
sender or sender group.

Of course, the most obvious way is to use crypto and some kind of  
access control, as has been done in the myriad of path authorisation  
papers, such as [1,2,3,4], to name but a few.  But that is boring by  
now; the most interesting problems seem to related to deployment  
incentives and the markets effects resulting from deploying such  
technologies.  (If someone is interested in co-operation, I have a  
student working in that area.)

More interesting is to consider the fundamentals of what you can do in  
a forwarding box.  You get a packet.  There is some information in the  
packet, some in your forwarding table, and then you know the incoming  
link.  The goal is to decide which output links to use, but only if  
the packet is "meant" to be sent along those links.  (You may want to  
relax some of the requirements and allow some false positives,  
provided that they are either random enough or controlled enough.)

One specific interesting approach is to name the links uni- 
directionally (more or less as you suggest), and then to compress the  
names into a Bloom filter or other compact fixed-sized representation,  
tagging the packets with the compact representation.  The  
representation effectively works as a path-specific locator.  (There  
are a number of interesting details, such as loop prevention, fast  
failure recovery, some security issues, etc, but I would digress.)

But you can go much further.  Of course, you can check that the packet  
came from a right incoming link, but that is again boring (and has a  
number of obvious complications that make it a little bit brittle as  
such).  More interestingly, you can accumulate the path so far to the  
packet (e.g., as a Bloom filter), and use that information as a part  
of the forwarding decision.

In general, there is a wealth of potential information that you could  
use, pretty efficiently, for the forwarding decisions.  Using  
destination addresses or source routing are by no means the only ways  
of constructing forwarding fabrics.  I believe that the middle ground  
where you combine some source-routing-like techniques, some hop-by-hop- 
like forwarding, and are also ready to carefully add some dynamic  
forwarding state to the network, maybe hide undiscovered troves.  But  
there are also dragons there.

> Even if it's not flows, but rather e.g. a translation which turns  
> that scope-local name into a global locator, the path-specific  
> locator is really just a security layer which obscures what global  
> locator that scope-local locator translates to. It can't be much  
> shorter/simpler than a global locator because that single scope- 
> local locator has to be able to specify the full range of  
> destinations that can be specified in a global locator.

You may well be right that path-specific locators cannot be shorter or  
simpler that global locators.  However, I don't think that they are  
just a security layer.

My fundamental question is whether it is possible to construct a  
forwarding fabric that has now global locators and where no single  
entity needs to have the full graph, or even a too large fraction of  
the whole graph.  (Why such a design would lead to a favourable market  
structure is another interesting issue where I have only gut feelings  
to guide...)  I believe the answer is yes, you can do that, and that  
you can do that in a way that is roughly as efficient as IP  
forwarding.  Indeed, our current straw-man design has much smaller  
forwarding tables than IP or even MPLS has, the mechanics of  
forwarding decisions are trivial, and we seem to have solved most of  
the thorny issues related to traditional source routing.  But I'm  
afraid that there may be a dragon or two lurking in the dark corners,  
ready to burn our straws completely.

> Or am I missing something?

Well, in this context (e2e-interest), I guess most of the people  
suffer from IP myopism.  As I tried to indicate above, IMHO it is by  
no means a necessity to have IP-address like global locators.  Indeed,  
I believe that a forwarding fabric without such locators would have  
potentially a much larger social utility that the current one we  
have.  Unfortunately, the utility of such a fabric alone, without the  
proper rendezvous and topology management systems, would be zero...   
Of course, the original IP had forwarding, topology, and rendezvous  
all nicely packed together, avoiding many of the potential deployment  
hurdles related to a multi-component system.

--Pekka


[1] Anderson et al. Preventing Internet Denial-of-Service with
    Capabilities.  (2008)

[2] Handley et al. Steps Towards a DoS-resistant Internet Architecture.
    Future directions in network architecture (2004) pp. 49–56

[3] Keromytis et al. SOS: secure overlay services.
    CCR (2002) vol. 32 (4) pp. 61-72

[4] Parno et al. Portcullis: Protecting Connection Setup from
    Denial-of-Capability Attacks.   SIGCOMM (2007)