AIP: Revisiting Internet Addressing
		     Hari Balakrishnan (MIT)

Joint work with David Andersen (CMU), Nick Feamster (Georgia Tech) and
Scott Shenker (UC Berkeley).

Knowing what we know now after three decades of the Internet and its
evolution, how would we re-design the Internet's network layer to
provide much higher end-to-end availability while retaining its
scalability?

This statement addresses this question, proposing a new addressing
proposal called AIP (Atomic Internet Protocol).  AIP is an attempt at a
principled re-examination of Internet addressing, unencumbered by the
current architecture.  Addressing plays a fundamental role in network
architecture---the choice of addressing scheme has deep ramifications
for routing, security, naming, and other aspects of the Internet
architecture.

Why focus on availability?  The answer is two-fold: first, providing
end-to-end connectivity in the face of faults (whether due to accident,
misconfiguration, or, as is increasingly the case, malice) is the
primary goal of any routing protocol.  Second, many measurements have
shown that the end-to-end availability of the Internet infrastructure is
between 1 and 2 "nines", which is orders of magnitude worse than other
mission critical services such as the traditional wireline phone system,
the emergency (911) phone system, the electric grid, and the national
airspace system.  In any case, it is a useful intellectual exercise,
with practical ramifications, to understand what the fundamental limits
to Internet routing availability are, while retaining its impressive
scalability.  Another way of asking the question is: are there
fundamental trade-offs between a routing protocol's ability to scale and
its ability to overcome faults?

The AIP project is a first step in this exercise, addressing this
question in the context of a specific proposal.  The underlying
intuition is that the Internet is organized into groups of hosts that
generally appear to {\em all be reachable} or are {\em all unreachable}
at any given time from any host outside the group.  We use the term
"Failure Atomic Unit" (FAU) to refer to such a group.  Today's network
architecture does does not preserve the "atomicity" (in terms of fate
sharing in the routing protocol) of such groups; the use of IP prefixes
as routing objects, we claim, is the wrong granularity for IP routing
because it does not reflect the notion of failure atomicity.  A single
prefix may include hosts that are in different locations, often in
different cities, served by different (fault-prone) links.  As a result,
the Internet's routing protocols may advertise routes that do not map to
currently usable paths, and some usable paths may not have routes
visible to routers.

We claim that each wide-area routing object should correspond one-to-one
with a FAU.  In this model, each AIP address has two parts: a global
identifier called an "AD" (for atomic domain), which specifies the FAU,
and an "endpoint identifier", which uniquely names the host's network
attachment point (a host could have many such identifiers).  Only ADs
are disseminated in the wide-area routing protocol (e.g., BGP).  ADs are
"flat" and without structure, and we give these identifiers
cryptographic meaning to help solve various problems with routing
security and address spoofing.

Those who know Internet history will observe that the proposed address
structure bears some resemblance to the original "TCP addressing"
proposal from the early days of the Internet [Cerf and Kahn, 1974].
This "back-to-the-past" structure, augmented with the idea of
"self-certification" in which each flat identifier is derived from the
public key of the owning entity (e.g., hash(public_key, other_salt)),
has four important benefits:

1. By identifying failure-atomicity as an organizing principle and
   explicitly using FAUs as routing objects, AIP can avoid falsely
   disseminating routing information for unusable paths.

2. ADs are cryptographically self-certifying, making it much easier to
   perform origin authentication and to secure routing protocols.

3. By including a simple mechanism to automatically check if packets
   arriving on an interface are valid, AIP makes spoofing harder.  That,
   in turn, makes it difficult for attackers to launch certain types of
   denial-of-service attacks on the network infrastructure.

4. By including a simple mechanism by which an end host (which knows
   when a path is not working because it can directly observe end-to-end
   reachability and performance) can signal in-band to the network to
   attempt a different path, AIP decouples path construction from path
   selection.  This separation allows hosts to quickly avoid failures
   when the network has no idea that a given end-to-end path has failed.
   This approach addresses the inability of current wide-area routing
   protocols to conduct end-to-end path probes scalably.

We conclude by mentioning a few key research questions that we need to
answer to show that AIP is practical and useful (these questions don't
include the many related to AIP's design, but only the ones concerning
its feasibility and utility):

1. Is the Internet in fact decomposable into FAUs?  Empirical evidence
   at small scale done in various overlay network experiments suggests
   that this is true, but a large-scale measurement study is essential.

2. How many FAUs are there likely to be in the Internet?  We expect the
   answer to be on the order of 1 million or so, although some of us
   think it might be fewer.

3. As the number of routing objects increases, what is the scaling limit
   in wide-area routing?  This question is obviously interesting even in the
   context of prefix-based routing.