[Olsr-users] Heads-up: AHCP redesign

[Jacques _]

No intend to troll, but doesn't ipv6 solve the need for ahcp by just having
prefix-mac(even cooler would be olsrd on link local) ? Therefore ipv6 is
auto-configuring by itself.

Jacques

On Thu, Dec 11, 2008 at 10:29 PM, Juliusz Chroboczek <
(spam-protected)> wrote:

> 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/<http://www.pps.jussieu.fr/%7Ejch/software/ahcp/>
>
> --
> Olsr-users mailing list
> (spam-protected)
> http://lists.olsr.org/mailman/listinfo/olsr-users
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.olsr.org/pipermail/olsr-users/attachments/20081211/b709d03a/attachment.html>