Japanese Wikipedia article page for link-local address mentions that the creation of link-local address is almost always indeterministic (非決定論的 in Japanese). The corresponding English page does not contain an equivalent statement.

My questions are how APIPA is implemented and how the candidate address is selected (or calculated). Is it really an undeterministic algorithm?

2 Answers 2


RFC 3927 is the specification for how it should be implemented. It has a section 2.1. Link-Local Address Selection which specifies the usage of a PRNG and recommends that the PRNG should be seeded using the same initial value (e.g. a MAC address) every time.

PRNGs are deterministic – their only source of randomness comes from external seeds; reinitializing the same PRNG with the same seed will always give the same sequence of outputs (hence pseudo-random). So any APIPA implementation that uses a MAC address as its PRNG seed should also generate the IPv4 addresses deterministically.

   The pseudo-random number generation algorithm MUST be chosen so that
   different hosts do not generate the same sequence of numbers.  If the
   host has access to persistent information that is different for each
   host, such as its IEEE 802 MAC address, then the pseudo-random number
   generator SHOULD be seeded using a value derived from this
   information.  This means that even without using any other persistent
   storage, a host will usually select the same IPv4 Link-Local address
   each time it is booted, which can be convenient for debugging and
   other operational reasons.  Seeding the pseudo-random number

It is not possible to know whether all APIPA implementations follow this recommendation except by testing them experimentally (many of them, such as the one in Windows, are closed-source). If I remember correctly, Avahi on Linux is compliant.

As one differing example, I seem to remember that the implementation used by Ubiquiti's airOS firmware is specifically called out in the device docs as directly using the device's last two MAC octets as the initial APIPA address (being somewhat noncompliant but nevertheless deterministic).

  • I have a circumspection towards calling a pseudo-random number generator undeterministic.
    – Taro
    Apr 19 at 8:04
  • 3
    PRNGs are exactly as deterministic as their seed is. With a given input seed, any PRNG will always return the same series of outputs every time. Apr 19 at 8:05
  • 2
    For example, even many CSPRNGs are just hash algorithms or symmetric ciphers that are deterministic by their nature – they're only made "random" by collecting a sufficiently random input seed from somewhere else first (i.e. the "entropy collection" or "seeding" process). But it is not uncommon to use PRNGs with a predictable seed for cetain purposes, as in this case – as long as it's seeded with the same MAC address it'll generate the same numbers. Apr 19 at 8:11
  • 2
    Another example; many procedurally generated games like Minecraft or Factorio. The "seed" for a world is the PRNG seed.
    – mtak
    Apr 19 at 11:06
  • 1
    On what @Taro is mentioning, I too was educated to believe that PRNG did not specifically indicate determinism, but that the subset of them that are DPRNGs (D for Deterministic) are. that said Wikipedia disagrees with my uni, so .... en.wikipedia.org/wiki/Pseudorandom_generator Apr 20 at 5:45

From RFC 3927:

This means that even without using any other persistent storage, a host will usually select the same IPv4 Link-Local address each time it is booted, which can be convenient for debugging and other operational reasons.

Note the usually there. The PRNG is used to generate a sequence of IP addresses, and the device chooses the first address from that sequence that isn't claimed by another device. This means that the result is path-dependent. Even if all devices seed their PRNGs deterministically, in case of a clash the results depend on the order that different devices come online and claim addresses. If you turn everything off and then bring it up again in a different order than the last time, the results may be different. Even just changing the relative order of two devices may create a chain reaction that causes any number of devices to receive different addresses (although this is statistically quite unlikely unless you have thousands of devices on the same network segment).

So is this deterministic or nondeterministic? That totally depends on the view you take of the system. The narrower view is that algorithm is deterministic — it will make the same choice every time given the same inputs (i.e. the same seed and the same set of currently-online network peers).

But if we take the view that the network consists of a collection of devices with various seeds (some of which may be unknown to us), which join and leave the network at unpredictable times, then we come to the conclusion that we can't predict with certainty what address any device will have at any future time. We can only figure it out at the moment of assignment by taking census of the network. In this sense, automatic IP assignment is nondeterministic, because it depends on nondeterministic outside factors (like people walking in and out of the building with their phones and laptops).

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .