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.<br><br>Jacques<br><br><div class="gmail_quote">
On Thu, Dec 11, 2008 at 10:29 PM, Juliusz Chroboczek <span dir="ltr"><<a href="mailto:Juliusz.Chroboczek@pps.jussieu.fr">Juliusz.Chroboczek@pps.jussieu.fr</a>></span> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Dear all,<br>
<br>
I'm currently in the process of redesigning AHCP[1], so I thought I'd share<br>
a number of ideas with you.<br>
<br>
AHCP is an address configuration protocol. Because it is designed for mesh<br>
networks, it needs to solve a number of issues that are not handled by DHCP:<br>
<br>
- it needs to work across multiple hops;<br>
- a part of the network needs to be able to survive for at least a few<br>
hours when it becomes isolated from the rest of the network;<br>
- stale configuration data needs to be reliably flushed from the network<br>
even when connectivity is lost;<br>
- it needs to work when time synchronisation is lost, both on clients and<br>
on servers.<br>
<br>
The last point deserves some elaboration. Some of my mesh nodes are cheap<br>
access points that don't have a hardware clock. These nodes boot with the<br>
system clock set at some arbitrary time in the past, and only get a proper<br>
time after NTP synchronises; since NTP is only operational after IP<br>
addresses have been configured, AHCP needs to be able to configure even<br>
when the system clock is mis-set.<br>
<br>
For the same reason, there is no certainty that the AHCP server will be<br>
able to set its clock before it configures the rest of the network.<br>
I recently f*cked up a demo, in which my mesh nodes failed to properly<br>
configure because the AHCP server had failed to contact its configured NTP<br>
server (there was an issue with the firewall).<br>
<br>
There are currently two versions of the AHCP protocol, 0 and 0.1, and<br>
version 1 is under development.<br>
<br>
AHCP version 0<br>
**************<br>
<br>
AHCP version 0, as implemented by ahcpd up to and including version 0.4, is<br>
a purely stateless peer-to-peer protocol. AHCP version 0 has all of the<br>
features above, and aditionally is a maginificently efficient protocol --<br>
in a stable network, configuration has a cost that it sub-linear in the<br>
number of nodes to configure (if a single node reboots, the cost of<br>
configuration is 2 packets, but if 10 nodes reboot simulteaneously, the<br>
cost can be as low as 2 packets under some circumstances).<br>
<br>
Unfortunately, AHCP 0, being a stateless protocol, does not allow<br>
configuration of IPv4 addresses. When Babel was rewritten to handle IPv4<br>
in additiona to IPv6, I needed an integrated autoconfiguration solution for<br>
IPv6 and IPv4.<br>
<br>
AHCP version 0.1<br>
****************<br>
<br>
AHCP 0.1, as implemented by ahcpd 0.5, is an upwards-compatible extension<br>
to AHCP 0 (hence the weird version number). AHCP 0.1 proceeds by first<br>
performing stateless configuration of an IPv6 address, using the AHCP 0<br>
procedures, and then performs a stateful client-server lease acquisition<br>
over IPv6 unicast. I am deeply unhappy with AHCP 0.1, for the following<br>
reasons:<br>
<br>
- due to the two-phase protocol, the AHCP 0.1 is very complicated (the<br>
state space is the cartesian product of the stateless and the<br>
stateful state spaces); I believe this is indicative of improper<br>
protocol layering (IPv4 autoconf relies on IPv6 routing, which in turn<br>
relies on IPv6 autoconf);<br>
- because the stateful phase of the protocol is carried over IPv6<br>
unicast, AHCP can only work with hybrid IPv6/IPv4 routing protocols<br>
(this excludes unik-olsrd, the most widely deployed mesh routing<br>
implementation);<br>
- because the stateful part of the protocol deals with absolute leases,<br>
it does not serve addresses when servers' clocks are broken.<br>
<br>
Note, however, that AHCP 0.1 is safe under all circumstances -- there are<br>
mechanisms in the protocol to ensure that stale leases will be flushed even<br>
when the nodes' clocks are stepped.<br>
<br>
AHCP version 1<br>
**************<br>
<br>
AHCP version 1 is the version of the protocol under development. Since<br>
IPv4 doesn't seem to want to go away, AHCP 1 is a pure stateful protocol,<br>
roughly modeled on DHCP.<br>
<br>
AHCP version 1 has all of the desirable properties outlined above, notably<br>
the ability to safely give out leases even when both the client's and the<br>
server's clocks are off. This is done by carefully monitoring one's clock<br>
and the clocks of one's peers, and being extremely conservative about lease<br>
timeouts when clocks are suspicious.<br>
<br>
Basic AHCP 1 operation<br>
----------------------<br>
<br>
In short, AHCP 1 functions as follows. All AHCP nodes are able to forward<br>
AHCP packets, whether they are configured or not; in other words, the AHCP<br>
network implements a very simple multicast routing protocol. When it first<br>
boots, an AHCP client performs an increasing diameter search for an AHCP<br>
server; when a server is found, a lease is requested, DHCP-style.<br>
<br>
The server gives out two kinds of leases. A server that does not have<br>
a trusted real-time clock gives out a relative lease, one that is valid for<br>
a given time interval d. A server that does have a trusted real-time clock<br>
sends out an absolute lease, one that has both a relative expiry time d and<br>
an absolute expiry time e.<br>
<br>
AHCP 1 and time<br>
---------------<br>
<br>
AHCP 1 assumes that nodes have two kinds of clocks: a monotonic clock, that<br>
is stable for extended periods of time, and whose instabilites can be<br>
reliably detected, and a real-time clock, that can suffer from frequent<br>
instability.<br>
<br>
The real-time clock has three states:<br>
<br>
* unknown, meaning that the time it gives is probably off<br>
* untrusted, meaning that it is most probably either correct or<br>
moderately fast, but we shouldn't rely on it for safety, and<br>
* trusted, meaning that it is definitely known to be within a few<br>
minutes of UTC time.<br>
<br>
The monotonic clock can be implemented using the POSIX TIME_MONOTONIC<br>
clock; such a clock only suffers from instabilites at reboot time. For<br>
platforms that don't implement TIME_MONOTONIC, it can be implemented using<br>
the real-time clock and carefully monitoring it for instabilities.<br>
<br>
The real-time clock is implemented using the system's real-time clock; it<br>
is initiallly in the broken state. It switches to the untrusted state<br>
whenever we receive a server message with a time that makes sense to us<br>
(server clocks are therefore never in the untrusted state -- they're either<br>
broken or trusted), and to the trusted state whenever NTP sync is<br>
established. It switches back to the untrusted state a few hours after NTP<br>
sync is lost, and to the broken state whenever we receive a server message<br>
that carries a timestamp that is in the future or very far in the past.<br>
<br>
A client expires a lease (1) after a delay d, or, (2) when its clock is not<br>
in the broken state and time e has been reached. Additionally, if the<br>
client doesn't have a trusted monotonic clock, it expires its lease<br>
whenever it detects that its clock has been stepped.<br>
<br>
The server, on the other hand, can expire a lease (a) when its monotonic<br>
clock has been stable for time d + g (where g is the lease's ``grace<br>
time''), (b) when the lease is absolute, the real-time clock is trusted,<br>
and time e + g has been reached. Additionally, a server conservatively<br>
converts relative leases to absolute leases whenever its clock switches to<br>
the trusted state.<br>
<br>
Optimisations<br>
-------------<br>
<br>
In order to avoid the increasing diameter search, an AHCP 1 client can<br>
perform a lease renewal using global unicast. Indeed, renewal requests are<br>
only destined to a single server, and at the time we renew a lease, the<br>
client is configured, the routing protocol is running, and hence it should<br>
be possible to reach the server using unicast.<br>
<br>
If we are currently configured, we may also forward packets using unicast<br>
to our currently selected server. This means that in a stable network, the<br>
increasing diameter search will converge after just 2 hops.<br>
<br>
Properties<br>
----------<br>
<br>
AHCP 1 has all of the desirable properties that I listed above. Additionally,<br>
its correctness is provable (I'm currently writing down the proof).<br>
<br>
The two main limitations of AHCP 1 are unavoidable in a stateful protocol.<br>
Unlike AHCP 0, AHCP 1 requires that servers have read-write persistent<br>
storage; a small flash should be enough, but you'll not be able to run AHCP<br>
1 servers on disk-less, flash-less netbooted nodes. (This does not apply<br>
to clients.)<br>
<br>
For the same reason, a node will not be able to autoconfigure unless it can<br>
reach a server. This is unlike AHCP 0, in which a node was able to<br>
autoconfigure by grabbing configuration information from a previously-<br>
configured peer.<br>
<br>
Finally, AHCP 1 is somewhat less efficient than AHCP 0. In a network with<br>
n nodes and g neighbours for each node, configuring a newly-booted node<br>
takes between 4 and 4 * n packets, 4 * (g + 1) in a stable network, as<br>
compared to 2 to 2 * n packets, 2 typical, in AHCP 0. I believe that this<br>
is still tolerable.<br>
<br>
Open issues<br>
-----------<br>
<br>
The main open issue is whether we need conflict detection. To be safe, I'm<br>
implementing defense but not detection -- this means that detection will be<br>
easy to add in a backwards-compatible manner at a later date if I become<br>
convinced that it is necessary.<br>
<br>
Implementation status<br>
---------------------<br>
<br>
I currently have a slightly incomplete implementation of AHCP 1, and<br>
a slightly incomplete proof of its correctness. I am hoping to finish both<br>
before the end of the Christmas holidays, at which point the code will<br>
become available. Let me know if you want a copy before then.<br>
<br>
Juliusz<br>
<br>
[1] <a href="http://www.pps.jussieu.fr/%7Ejch/software/ahcp/" target="_blank">http://www.pps.jussieu.fr/~jch/software/ahcp/</a><br>
<font color="#888888"><br>
--<br>
Olsr-users mailing list<br>
<a href="mailto:Olsr-users@lists.olsr.org">Olsr-users@lists.olsr.org</a><br>
<a href="http://lists.olsr.org/mailman/listinfo/olsr-users" target="_blank">http://lists.olsr.org/mailman/listinfo/olsr-users</a><br>
</font></blockquote></div><br>