Re: Autonomous System Sanity Protocol

Noel Chiappa <> Mon, 28 April 1997 15:48 UTC

Received: from cnri by id aa05757; 28 Apr 97 11:48 EDT
Received: from by CNRI.Reston.VA.US id aa12579; 28 Apr 97 11:48 EDT
Received: from mailing-list by (8.6.9/1.0) id BAA13025; Tue, 29 Apr 1997 01:40:47 +1000
Received: from munnari.OZ.AU by (8.6.9/1.0) with SMTP id BAA12910; Tue, 29 Apr 1997 01:22:32 +1000
Received: from by munnari.OZ.AU with SMTP (5.83--+1.3.1+0.56) id PA04450; Tue, 29 Apr 1997 01:22:30 +1000 (from
Received: by id AA29486; Mon, 28 Apr 97 11:20:40 -0400
Date: Mon, 28 Apr 97 11:20:40 -0400
From: Noel Chiappa <>
Message-Id: <>
Subject: Re: Autonomous System Sanity Protocol
Precedence: bulk

    From: RADIA PERLMAN <>

    > do you know if Perlman's thesis is available on the net?

    I no longer have softcopy.

That's what scanners are for! :-)

    I won't have to ask whether there's a problem with copyright.

I doubt very much MIT would be *any* problem with this.

    Having an authoritative database of all the potential links, and the
    routing algorithm only tells yo u which of those things are currently
    unreachable, might be nice.

I dunno. See my comments about "fate-sharing" between router R1, and
information about what R1 is connected to. I don't think we can have a
centralized database for connectivity, and if we are going to have a
distributed one, we might as well make the routers the holders of the
authoritative data - which co-locates the data with the routers.

    unfortunately parts of the topology w ant to remain secret from other

That's OK, most advanced systems have provision for hiding the internal
topology of an abstraction from people whom they don't want to have it..

    Maybe rather than passing around the authoritative database, there can be
    a tool that queries all the configured information at boundaries, or a
    hierarchy of such tools that explore their own portion of the topology

I'm not sure quite what the point would be? Can you elucidate? (Also, are you
assuming a classic hop-by-hop system for determing paths? Perhaps this
comment is intended for such a system?)

    A Byzantine failure of a true router can't be solved with having routers
    sign messages, because the compromised router will be able to generate a
    legitimate signature to prove he's one of the good guys.

Sure. The only way to detect such a router (which might simply trash 82% of
all packets going through it) is to monitor the actual performance you get
from the network, relative to any performace guarantee the network has made
you, and if you aren't getting it, to try and fault-isolate.

Expensive, complex and painful, but I don't see any alternative, *iff*
automated protection against this kind of thing is an important goal. My take
is that it might be, *for some people*, and the routing architecture should
*allow* and *support* it for those who need it, and are willing to pay the
price in overhead of so doing, but hopefully with zero cost to those who

    BGP is actually somewhat like a link state protocol, in that the entire
    path is given.

Yakov and I have this argument all the time! I claim they are fundamentally
different - and up until now the only argument I had was that PV is a "back
door kludge" way of distributing topology info, and i) is almost certainly
not going to give you a complete map, and ii) just feels like a kludgy way
of doing it (and we all know that sooner or later, kludges bite you in the

Now (see recent message on PKS overhead) I have another argument, which is
that the way in which connectivity changes get propogated is fundamentally
different too.

    If each route r signs its path to D, then when router R chooses among the
    aroutes given by each of its neighbors, it chooses one, and can preserve
    that neighbor's signature, and then add its own. ... I don't think that
    solves too much, though, since the problem is a legitimate router being
    misconfigured rather than having malicious people inject messages.

I'm not sure quite what you're getting at here - are you saying that the
problem is some router is misconfigured to think it is attached to D, when it
in fact is not?

If so, sigh, this is what I get for trying to *not* generate a massive tome
in my original message - I leave out some of what I assumed (wrongly :-) were
fairly obvious steps! I did expand in a later message:

    > Only "auhorized" agents of topological entity X (i.e. those allowed to
    > distribute maps or abstractions of X, outside X) have the key to sign
    > map data about X.

but perhaps you missed it. Not only does router R9 have to have a private key
(to veryify that updates which claim to be from it actually came from it),
but topological abstraction X has to have a private key, so that all routers
which can claim to be attached to it can do so authoritatively (i.e. they
have to have that private key).

This should fix most instances of bad configuration (i.e. excluding ones
like R9 is authorized to originate abstractions of X, and originates a
bad abstraction, or claims to have a working link to X, when in fact its
link is broken). It does, I think, limit the scope of entities which can
originate erroneous information about X to those entities to which X has
entrusted a private key - and thus are probably under X's control.