Skip to main content

Zeroconf Address Allocation

IPv4 Zeroconf lets devices choose local network addresses without manual configuration or a DHCP server [RFC 3927]. A device sends probes to check whether another device already uses its chosen address.

Lost probes or replies can leave a conflict unnoticed, while additional probes cost traffic and delay [PRISM Zeroconf]. For one address choice and a fixed probe limit, we verify an upper bound on the probability that the address is free or the collision is detected. Both outcomes count as success.

The Program​

The functions probCollision() and probMessageLost() give the collision probability cc and the probability qq that a probe fails to detect it. This can happen if the probe or its reply is lost. The function maxTries() gives the probe limit MM. The helper exp(q, k) denotes qkq^k.

The procedure zeroconf first samples whether the address is occupied. For an occupied address, it calls arp(maxTries()) to try to detect the collision.

One Zeroconf address choice with three probesAn incoming arrow marks the address choice. With probability 1βˆ’c the address is free, and with probability c probing starts with three probes remaining. Each probe detects the collision with probability 1βˆ’q; otherwise, one fewer probe remains. Free and detected return true, while three unsuccessful attempts leave the collision undetected and return false.3211 βˆ’ ccqqq1 βˆ’ q1 βˆ’ q1 βˆ’ qchoosefreedetectedmissedprobes leftM = 3
Choosing an address and checking for a collision
Expected: Verified
@wp
coproc zeroconf() -> (success: Bool)
pre probCollision() * (1 - exp(probMessageLost(), maxTries())) + (1 - probCollision())
post [success]
{
var collision: Bool = flip(probCollision())
if collision {
// Try at most maxTries() probes to detect this collision.
success = arp(maxTries())
} else {
success = true
}
}

Choosing another address after detecting a collision is outside this model.

Verification​

Both coprocedures use the @wp annotation to verify upper bounds on the probability that success is true.

Upper Bound for the Address Choice​

Caesar verifies the upper bound

Pr⁑(success)≀(1βˆ’c)+cβ‹…(1βˆ’qM).\Pr(\mathtt{success})\le (1-c)+c\cdot\left(1-q^M\right).

The term 1βˆ’c1-c accounts for a free address, which immediately succeeds. The term cβ‹…(1βˆ’qM)c\cdot(1-q^M) accounts for an occupied address, using the bound in arp's specification for MM probes.

Bounding Collision Detection Recursively​

The helper arp(triesRemaining) probes an occupied address, stopping when a collision is detected or no probes remain.

Detecting a collision with the remaining probes
Expected: Verified
@wp
coproc arp(triesRemaining: UInt) -> (success: Bool)
pre 1 - exp(probMessageLost(), triesRemaining)
post [success]
{
if triesRemaining == 0 {
// With no probes remaining, the collision cannot be detected.
success = false
} else {
// A delivered probe detects the collision; a lost probe leaves one fewer attempt.
var messageLost: Bool = flip(probMessageLost())
if messageLost {
success = arp(triesRemaining - 1)
} else {
success = true
}
}
}

With kk independent probes left, the collision remains undetected if all fail, an event of probability qkq^k. With no probes remaining, arp returns false, matching the bound zero. For k>0k>0, a probe detects the collision with probability 1βˆ’q1-q; otherwise, we use the recursive specification with one fewer probe:

(1βˆ’q)+qβ‹…(1βˆ’qkβˆ’1)=1βˆ’qk.(1-q)+q\cdot\left(1-q^{k-1}\right)=1-q^k.

Each recursive call decreases triesRemaining, so the procedure terminates after at most that many probes. Caesar uses the recursive definition of exp for qkq^k and the axiom exp_bounded for qk≀1q^k\le1.

See Also​

References​