[Babel-users] Heads-up: AHCP redesign

Thu Dec 11 20:29:12 UTC 2008

Dear all,

I'm currently in the process of redesigning AHCP[1], so I thought I'd share
a number of ideas with you.

AHCP is an address configuration protocol.  Because it is designed for mesh
networks, it needs to solve a number of issues that are not handled by DHCP:

  - it needs to work across multiple hops;
  - a part of the network needs to be able to survive for at least a few
    hours when it becomes isolated from the rest of the network;
  - stale configuration data needs to be reliably flushed from the network
    even when connectivity is lost;
  - it needs to work when time synchronisation is lost, both on clients and
    on servers.

The last point deserves some elaboration.  Some of my mesh nodes are cheap
access points that don't have a hardware clock.  These nodes boot with the
system clock set at some arbitrary time in the past, and only get a proper
time after NTP synchronises; since NTP is only operational after IP
addresses have been configured, AHCP needs to be able to configure even
when the system clock is mis-set.

For the same reason, there is no certainty that the AHCP server will be
able to set its clock before it configures the rest of the network.
I recently f*cked up a demo, in which my mesh nodes failed to properly
configure because the AHCP server had failed to contact its configured NTP
server (there was an issue with the firewall).

There are currently two versions of the AHCP protocol, 0 and 0.1, and
version 1 is under development.

AHCP version 0
**************

AHCP version 0, as implemented by ahcpd up to and including version 0.4, is
a purely stateless peer-to-peer protocol.  AHCP version 0 has all of the
features above, and aditionally is a maginificently efficient protocol --
in a stable network, configuration has a cost that it sub-linear in the
number of nodes to configure (if a single node reboots, the cost of
configuration is 2 packets, but if 10 nodes reboot simulteaneously, the
cost can be as low as 2 packets under some circumstances).

Unfortunately, AHCP 0, being a stateless protocol, does not allow
configuration of IPv4 addresses.  When Babel was rewritten to handle IPv4
in additiona to IPv6, I needed an integrated autoconfiguration solution for
IPv6 and IPv4.

AHCP version 0.1
****************

AHCP 0.1, as implemented by ahcpd 0.5, is an upwards-compatible extension
to AHCP 0 (hence the weird version number).  AHCP 0.1 proceeds by first
performing stateless configuration of an IPv6 address, using the AHCP 0
procedures, and then performs a stateful client-server lease acquisition
over IPv6 unicast.  I am deeply unhappy with AHCP 0.1, for the following
reasons:

  - due to the two-phase protocol, the AHCP 0.1 is very complicated (the
    state space is the cartesian product of the stateless and the
    stateful state spaces); I believe this is indicative of improper
    protocol layering (IPv4 autoconf relies on IPv6 routing, which in turn
    relies on IPv6 autoconf);
  - because the stateful phase of the protocol is carried over IPv6
    unicast, AHCP can only work with hybrid IPv6/IPv4 routing protocols
    (this excludes unik-olsrd, the most widely deployed mesh routing
    implementation);
  - because the stateful part of the protocol deals with absolute leases,
    it does not serve addresses when servers' clocks are broken.

Note, however, that AHCP 0.1 is safe under all circumstances -- there are
mechanisms in the protocol to ensure that stale leases will be flushed even
when the nodes' clocks are stepped.

AHCP version 1
**************

AHCP version 1 is the version of the protocol under development.  Since
IPv4 doesn't seem to want to go away, AHCP 1 is a pure stateful protocol,
roughly modeled on DHCP.

AHCP version 1 has all of the desirable properties outlined above, notably
the ability to safely give out leases even when both the client's and the
server's clocks are off.  This is done by carefully monitoring one's clock
and the clocks of one's peers, and being extremely conservative about lease
timeouts when clocks are suspicious.

Basic AHCP 1 operation
----------------------

In short, AHCP 1 functions as follows.  All AHCP nodes are able to forward
AHCP packets, whether they are configured or not; in other words, the AHCP
network implements a very simple multicast routing protocol.  When it first
boots, an AHCP client performs an increasing diameter search for an AHCP
server; when a server is found, a lease is requested, DHCP-style.

The server gives out two kinds of leases.  A server that does not have
a trusted real-time clock gives out a relative lease, one that is valid for
a given time interval d.  A server that does have a trusted real-time clock
sends out an absolute lease, one that has both a relative expiry time d and
an absolute expiry time e.

AHCP 1 and time
---------------

AHCP 1 assumes that nodes have two kinds of clocks: a monotonic clock, that
is stable for extended periods of time, and whose instabilites can be
reliably detected, and a real-time clock, that can suffer from frequent
instability.

The real-time clock has three states:

  * unknown, meaning that the time it gives is probably off
  * untrusted, meaning that it is most probably either correct or
    moderately fast, but we shouldn't rely on it for safety, and
  * trusted, meaning that it is definitely known to be within a few
    minutes of UTC time.

The monotonic clock can be implemented using the POSIX TIME_MONOTONIC
clock; such a clock only suffers from instabilites at reboot time.  For
platforms that don't implement TIME_MONOTONIC, it can be implemented using
the real-time clock and carefully monitoring it for instabilities.

The real-time clock is implemented using the system's real-time clock; it
is initiallly in the broken state.  It switches to the untrusted state
whenever we receive a server message with a time that makes sense to us
(server clocks are therefore never in the untrusted state -- they're either
broken or trusted), and to the trusted state whenever NTP sync is
established.  It switches back to the untrusted state a few hours after NTP
sync is lost, and to the broken state whenever we receive a server message
that carries a timestamp that is in the future or very far in the past.

A client expires a lease (1) after a delay d, or, (2) when its clock is not
in the broken state and time e has been reached.  Additionally, if the
client doesn't have a trusted monotonic clock, it expires its lease
whenever it detects that its clock has been stepped.

The server, on the other hand, can expire a lease (a) when its monotonic
clock has been stable for time d + g (where g is the lease's ``grace
time''), (b) when the lease is absolute, the real-time clock is trusted,
and time e + g has been reached.  Additionally, a server conservatively
converts relative leases to absolute leases whenever its clock switches to
the trusted state.

Optimisations
-------------

In order to avoid the increasing diameter search, an AHCP 1 client can
perform a lease renewal using global unicast.  Indeed, renewal requests are
only destined to a single server, and at the time we renew a lease, the
client is configured, the routing protocol is running, and hence it should
be possible to reach the server using unicast.

If we are currently configured, we may also forward packets using unicast
to our currently selected server.  This means that in a stable network, the
increasing diameter search will converge after just 2 hops.

Properties
----------

AHCP 1 has all of the desirable properties that I listed above.  Additionally,
its correctness is provable (I'm currently writing down the proof).

The two main limitations of AHCP 1 are unavoidable in a stateful protocol.
Unlike AHCP 0, AHCP 1 requires that servers have read-write persistent
storage; a small flash should be enough, but you'll not be able to run AHCP
1 servers on disk-less, flash-less netbooted nodes.  (This does not apply
to clients.)

For the same reason, a node will not be able to autoconfigure unless it can
reach a server.  This is unlike AHCP 0, in which a node was able to
autoconfigure by grabbing configuration information from a previously-
configured peer.

Finally, AHCP 1 is somewhat less efficient than AHCP 0. In a network with
n nodes and g neighbours for each node, configuring a newly-booted node
takes between 4 and 4 * n packets, 4 * (g + 1) in a stable network, as
compared to 2 to 2 * n packets, 2 typical, in AHCP 0.  I believe that this
is still tolerable.

Open issues
-----------

The main open issue is whether we need conflict detection.  To be safe, I'm
implementing defense but not detection -- this means that detection will be
easy to add in a backwards-compatible manner at a later date if I become
convinced that it is necessary.

Implementation status
---------------------

I currently have a slightly incomplete implementation of AHCP 1, and
a slightly incomplete proof of its correctness.  I am hoping to finish both
before the end of the Christmas holidays, at which point the code will
become available.  Let me know if you want a copy before then.

                                        Juliusz

[1] http://www.pps.jussieu.fr/~jch/software/ahcp/