47  Address Collisions

In 60 Seconds

Address collisions in IoT networks follow the Birthday Problem: with just 300 devices in a 16-bit address space (65,536 values), there is already a 50% chance two devices share the same address. Use the formula Safe Count = sqrt(Address Space) x 0.85 to right-size your address space and prevent silent communication failures from duplicate addresses.

47.1 Learning Objectives

By the end of this module, you will be able to:

• Apply the Birthday Problem formula to calculate collision probability
• Explain why address collisions occur more often than intuition suggests
• Evaluate address space requirements for different deployment sizes
• Design IoT networks with appropriate address space sizing
• Calculate bandwidth requirements for IoT deployments

Minimum Viable Understanding

• Address collisions follow quadratic probability: with just 300 devices in a 16-bit address space, there is already a ~50% chance of a collision – far higher than most engineers expect.
• The Birthday Problem formula (P(collision) ~ 1 - e^(-n2 / 2d)) lets you calculate how many devices can safely share an address space before collisions become likely.
• Right-size your address space: use the rule of thumb Safe Count = sqrt(Address Space) x 0.85 and always validate bandwidth needs before upgrading to a more expensive protocol.

Sensor Squad: The Birthday Surprise Party

Sammy the Sensor is throwing a party and giving each guest a random number from 1 to 100 as a name tag. “With 100 numbers, we won’t run out until we have 100 guests!” Sammy says proudly.

But Lila the Light Sensor notices something strange at the door: “Sammy, guest number 42 just arrived, but we already HAVE a guest number 42! They got the same random number!”

“That’s impossible!” Sammy gasps. “We only have 12 guests!”

Max the Motion Detector explains: “It’s called the Birthday Problem. You don’t need anywhere close to 100 guests before two of them share a number. With just 12 guests picking from 100 numbers, there’s already about a 50-50 chance of a match!”

Think of it like this: Imagine your class has 23 students. What are the chances two students share the same birthday? Most people guess about 6%, but the real answer is 50%! That is because every new person is compared against ALL the others, and those comparisons add up fast.

In IoT networks, devices get random addresses the same way party guests get name tags. If two devices accidentally get the same address, their messages get mixed up – just like two guests both responding to “Number 42!”

47.2 Module Overview

Time: ~30 min total | Difficulty: Intermediate | Unit: P07.C15.U04

When designing IoT networks, engineers often assume that address collisions are extremely unlikely given the large address spaces available. However, the Birthday Problem reveals a surprising truth: collisions occur far more frequently than intuition suggests. This module explores the mathematics behind address collisions and provides practical guidance for network design.

For Beginners: What Is an Address Collision?

Every device on a network needs a unique address so messages reach the right destination – just like every house on a street needs a unique house number.

An address collision happens when two devices accidentally end up with the same address. This causes confusion: messages intended for one device may be delivered to the other, or both devices may try to respond at the same time.

You might think: “If we have millions of possible addresses, surely no two devices will pick the same one.” But the Birthday Problem from mathematics shows this is a dangerous assumption. Collisions become likely much sooner than you would expect, because each new device must differ from all existing devices, not just one.

Key takeaway: Always do the math before assuming your address space is “big enough.”

This module is divided into three focused chapters:

47.2.1 Chapter Navigation

Chapter	Topics	Time
The Birthday Problem in IoT Networks	Classic birthday paradox, formula derivation, MAC address collisions, 16-bit short addresses, collision probability calculator	~10 min
Collision Design Strategies	Zigbee network limits, IPv6 addressing, UUID design, collision detection and resolution, case study	~10 min
Bandwidth Requirements and Calculations	Common bandwidth misconceptions, IoT bandwidth calculator, protocol selection, cost optimization	~10 min

47.3 Key Concepts Preview

47.3.1 The Birthday Problem

The Birthday Problem demonstrates why collisions occur more frequently than expected:

• With just 23 people, there’s a 50% chance of shared birthdays
• The probability depends on n squared (quadratic), not n (linear)
• For IoT: 300 devices in a 16-bit address space = ~50% collision probability

Putting Numbers to It

Birthday Problem Collision Probability

The probability of address collision grows quadratically, far faster than intuition suggests. The formula:

\[P(\text{collision}) \approx 1 - e^{-\frac{n^2}{2d}}\]

where \(n\) = number of devices, \(d\) = address space size.

Solving for “safe” device count (50% collision threshold): \[1 - e^{-\frac{n^2}{2d}} = 0.5 \quad \Rightarrow \quad n \approx \sqrt{2d \ln 2} \approx 1.177 \sqrt{d}\]

Practical examples:

• 16-bit Zigbee (\(d = 2^{16} = 65{,}536\)): \(n_{50\%} \approx 1.177 \times 256 = 301\) devices
• 32-bit LoRaWAN (\(d = 2^{32}\)): \(n_{50\%} \approx 1.177 \times 65{,}536 = 77{,}162\) devices
• 64-bit BLE (\(d = 2^{64}\)): \(n_{50\%} \approx 5.1 \times 10^9\) devices (no practical limit)

For 1% collision risk, use \(n \approx 0.142\sqrt{d}\) (derived from \(\sqrt{-2d\ln(0.99)}\)). A 16-bit address space safely supports only ~36 devices at 1% risk. This explains why Zigbee networks require either hierarchical addressing (parent routers pre-assign collision-free addresses) or Duplicate Address Detection (DAD) to prevent silent failures in real deployments.

47.3.2 Address Space Sizing

Design Guideline: Safe device count = sqrt(Address Space) x 0.85

Address Size	Safe Device Count	Protocol Examples
16-bit	~220 devices	Zigbee short addresses
32-bit	~55,000 devices	LoRaWAN DevAddr
64-bit	~3.6 billion devices	EUI-64, BLE MAC
128-bit	Unlimited for IoT	IPv6, UUIDs

Try It: Collision Probability Calculator

viewof numDevices = Inputs.range([1, 5000], {
  value: 300,
  step: 10,
  label: "Number of devices (n)"
})

viewof addrBits = Inputs.select([8, 16, 24, 32, 48, 64], {
  value: 16,
  label: "Address space (bits)"
})

{
  const d = Math.pow(2, addrBits);
  const n = numDevices;
  const exponent = -(n * n) / (2 * d);
  const prob = (1 - Math.exp(exponent)) * 100;
  const safeCount = Math.round(Math.sqrt(d) * 0.85);
  const n50 = Math.round(1.177 * Math.sqrt(d));

  const riskColor = prob < 1 ? "#16A085" : prob < 10 ? "#E67E22" : "#E74C3C";
  const riskLabel = prob < 1 ? "Low Risk" : prob < 10 ? "Moderate Risk" : prob < 50 ? "High Risk" : "Very High Risk";

  return html`
    <div style="font-family:Arial,sans-serif; padding:16px; background:#f8f9fa; border-radius:6px; border-left:4px solid ${riskColor}; margin-top:8px;">
      <div style="display:grid; grid-template-columns:1fr 1fr 1fr; gap:12px; margin-bottom:12px;">
        <div style="text-align:center; padding:10px; background:white; border-radius:4px; border:1px solid #dee2e6;">
          <div style="font-size:1.6em; font-weight:bold; color:${riskColor};">${prob < 0.01 ? "<0.01" : prob.toFixed(1)}%</div>
          <div style="font-size:0.8em; color:#7F8C8D;">Collision Probability</div>
          <div style="font-size:0.75em; font-weight:bold; color:${riskColor};">${riskLabel}</div>
        </div>
        <div style="text-align:center; padding:10px; background:white; border-radius:4px; border:1px solid #dee2e6;">
          <div style="font-size:1.6em; font-weight:bold; color:#2C3E50;">${safeCount.toLocaleString()}</div>
          <div style="font-size:0.8em; color:#7F8C8D;">Safe Device Count</div>
          <div style="font-size:0.75em; color:#7F8C8D;">sqrt(2^${addrBits}) × 0.85</div>
        </div>
        <div style="text-align:center; padding:10px; background:white; border-radius:4px; border:1px solid #dee2e6;">
          <div style="font-size:1.6em; font-weight:bold; color:#3498DB;">${n50.toLocaleString()}</div>
          <div style="font-size:0.8em; color:#7F8C8D;">50% Threshold</div>
          <div style="font-size:0.75em; color:#7F8C8D;">1.177 × sqrt(2^${addrBits})</div>
        </div>
      </div>
      <div style="font-size:0.85em; color:#2C3E50; padding:8px; background:white; border-radius:4px; border:1px solid #dee2e6;">
        <strong>Formula:</strong> P = 1 − e<sup>−n²/2d</sup> = 1 − e<sup>−${n}²/(2×${d.toLocaleString()})</sup>
        &nbsp;&nbsp;|&nbsp;&nbsp;
        <strong>Address space:</strong> 2<sup>${addrBits}</sup> = ${d.toLocaleString()} values
      </div>
      ${n > safeCount ? html`<div style="margin-top:8px; padding:6px 10px; background:#fdf3f2; border-radius:4px; color:#E74C3C; font-size:0.85em;">⚠ ${n.toLocaleString()} devices exceeds the safe count of ${safeCount.toLocaleString()} for a ${addrBits}-bit space. Consider a larger address space.</div>` : html`<div style="margin-top:8px; padding:6px 10px; background:#f0faf8; border-radius:4px; color:#16A085; font-size:0.85em;">✓ ${n.toLocaleString()} devices is within the safe count of ${safeCount.toLocaleString()} for a ${addrBits}-bit space.</div>`}
    </div>
  `;
}

47.3.3 Collision Mitigation Strategies

When address collisions are unavoidable, networks need strategies to detect and resolve them:

47.3.4 Bandwidth Reality Check

Most IoT sensor applications need Kbps, not Mbps:

• 500 soil sensors sending 50 bytes every 15 seconds = 13 Kbps total
• Upgrading from LoRaWAN (5 Kbps) to LTE-M (1 Mbps) often wastes money
• Bandwidth and latency are independent – more bandwidth doesn’t reduce response time

Common Pitfalls

1. Assuming collisions are impossible with “large” address spaces. A 32-bit address space sounds enormous (4.3 billion), but collisions reach 50% probability at just 77,000 devices. For city-scale IoT, that threshold arrives sooner than you think.

2. Confusing address space size with safe device count. Safe device count scales with the square root of the address space, not linearly. Doubling the address bits does not double the safe count – it squares it.

3. Over-provisioning bandwidth “just in case.” Many teams choose LTE-M or Wi-Fi for applications that generate only a few Kbps of traffic. This wastes money on data plans and power-hungry radios without improving latency.

4. Ignoring collision detection in constrained protocols. Zigbee and Thread use 16-bit short addresses. Without Duplicate Address Detection (DAD), two devices silently sharing an address cause intermittent, hard-to-debug failures.

5. Assuming more bandwidth = lower latency. Bandwidth and latency are independent. Upgrading from LoRaWAN to LTE-M increases throughput but does not reduce the propagation delay or server processing time.

47.4 Worked Example: Smart Parking Deployment

Scenario: A city plans to deploy parking occupancy sensors across its downtown core. Each parking space gets one sensor. The network uses Zigbee with 16-bit short addresses assigned randomly at join time.

Given:

• Downtown has 2,500 parking spaces (one sensor each)
• Zigbee short address space: 16-bit (65,536 possible addresses)
• Each sensor sends a 20-byte occupancy update every 5 minutes
• The city wants collision probability below 1%

Step 1: Calculate collision probability with 2,500 devices

Using the Birthday Problem approximation:

P(collision) = 1 - e^(-n2 / 2d)

Where n = 2,500 devices, d = 65,536 addresses:

P = 1 - e^(-(2500)2 / (2 x 65536)) P = 1 - e^(-6,250,000 / 131,072) P = 1 - e^(-47.68) P is approximately 1.0 (100%)

Result: With 2,500 devices in a 16-bit space, collision is virtually certain. The 16-bit address space is far too small.

Step 2: Determine required address space

For a 1% collision threshold, we need: n < sqrt(2d x 0.01)

Rearranging to find d: d > n^2 / (2 x 0.01) = 6,250,000 / 0.02 = 312,500,000

This requires at least a 29-bit address space. In practice, use 32-bit (LoRaWAN DevAddr) or 64-bit (EUI-64).

Step 3: Calculate bandwidth

Total bandwidth = (2,500 devices x 20 bytes x 8 bits/byte) / (5 min x 60 sec) = 400,000 bits / 300 seconds = 1,333 bps (about 1.3 Kbps)

Conclusion: The city needs to upgrade from Zigbee 16-bit addresses to at least a 32-bit address scheme, but the bandwidth requirement is only 1.3 Kbps – well within LoRaWAN’s capacity. Deploying LTE-M (1 Mbps) would be 750x more capacity than needed.

Try It: IoT Bandwidth Calculator

viewof bwDevices = Inputs.range([1, 10000], {
  value: 2500,
  step: 10,
  label: "Number of devices"
})

viewof bwPayload = Inputs.range([1, 1000], {
  value: 20,
  step: 1,
  label: "Payload size (bytes)"
})

viewof bwInterval = Inputs.range([0.1, 60], {
  value: 5,
  step: 0.1,
  label: "Reporting interval (minutes)"
})

{
  const bitsTotal = bwDevices * bwPayload * 8;
  const intervalSec = bwInterval * 60;
  const bwBps = bitsTotal / intervalSec;
  const bwKbps = bwBps / 1000;

  const protocols = [
    { name: "LoRaWAN", kbps: 5, color: "#16A085" },
    { name: "NB-IoT", kbps: 62.5, color: "#3498DB" },
    { name: "LTE-M", kbps: 1000, color: "#E67E22" },
    { name: "Wi-Fi", kbps: 54000, color: "#9B59B6" }
  ];

  const suitable = protocols.filter(p => p.kbps >= bwKbps);
  const cheapest = suitable.length > 0 ? suitable[0] : null;

  return html`
    <div style="font-family:Arial,sans-serif; padding:16px; background:#f8f9fa; border-radius:6px; border-left:4px solid #3498DB; margin-top:8px;">
      <div style="display:grid; grid-template-columns:1fr 1fr; gap:12px; margin-bottom:12px;">
        <div style="text-align:center; padding:10px; background:white; border-radius:4px; border:1px solid #dee2e6;">
          <div style="font-size:1.6em; font-weight:bold; color:#2C3E50;">${bwBps < 1000 ? bwBps.toFixed(0) + " bps" : bwKbps < 1000 ? bwKbps.toFixed(2) + " Kbps" : (bwKbps/1000).toFixed(2) + " Mbps"}</div>
          <div style="font-size:0.8em; color:#7F8C8D;">Aggregate Bandwidth</div>
        </div>
        <div style="text-align:center; padding:10px; background:white; border-radius:4px; border:1px solid #dee2e6;">
          <div style="font-size:1.6em; font-weight:bold; color:${cheapest ? cheapest.color : '#E74C3C'};">${cheapest ? cheapest.name : "None found"}</div>
          <div style="font-size:0.8em; color:#7F8C8D;">Most Cost-Effective Protocol</div>
          ${cheapest ? html`<div style="font-size:0.75em; color:#7F8C8D;">${cheapest.kbps >= 1000 ? (cheapest.kbps/1000).toFixed(0)+"Mbps" : cheapest.kbps+"Kbps"} capacity</div>` : ""}
        </div>
      </div>
      <div style="font-size:0.85em; color:#2C3E50; padding:8px; background:white; border-radius:4px; border:1px solid #dee2e6;">
        <strong>Calculation:</strong> (${bwDevices} devices × ${bwPayload} bytes × 8 bits) ÷ (${bwInterval} min × 60 s) = <strong>${bwBps.toFixed(0)} bps</strong>
      </div>
      <div style="margin-top:10px; display:flex; gap:8px; flex-wrap:wrap;">
        ${protocols.map(p => {
          const fits = p.kbps >= bwKbps;
          return html`<span style="padding:4px 10px; border-radius:12px; font-size:0.8em; font-weight:bold;
            background:${fits ? p.color : "#dee2e6"}; color:${fits ? "white" : "#7F8C8D"};">
            ${p.name} (${p.kbps >= 1000 ? (p.kbps/1000)+"Mbps" : p.kbps+"Kbps"}) ${fits ? "✓" : "✗"}
          </span>`;
        })}
      </div>
    </div>
  `;
}

47.5 Knowledge Checks

## Start Learning {#net-fund-collision-start}

Begin with The Birthday Problem in IoT Networks to understand why address collisions occur far more often than intuition suggests, then continue through the module.

Quick Reference

50% Collision Thresholds:

• 16-bit: ~300 devices
• 32-bit: ~77,000 devices
• 48-bit: ~20 million devices
• 64-bit: ~5 billion devices

Bandwidth Formula: Average (bps) = (Devices x Payload_bytes x 8) / (Interval_minutes x 60)

Decision Framework: Choosing Address Space Size for IoT Networks

Use this framework to select the appropriate address space for your deployment before implementation:

Deployment Scale	Device Count	Address Space	Protocol Examples	Collision Risk (no mitigation)
Tiny Network	1-50	8-bit (256)	Custom protocols, I²C addresses	Acceptable
Small Home/Building	50-200	16-bit (65K)	Zigbee short addresses, BACnet MS/TP	50% at 300 devices
Campus/District	200-50,000	32-bit (4.3B)	LoRaWAN DevAddr, IPv4 private	50% at 77K devices
City/Enterprise	50K-1M	64-bit (1.8×10^19)	BLE MAC, EUI-64	50% at 5 billion devices
Global IoT	1M+	128-bit (3.4×10^38)	IPv6, UUID	Collision impossible

Step-by-Step Selection Process:

1. Estimate Maximum Device Count (with 5-year growth)

Current devices: _____
Growth rate: _____ % per year
5-year projection: Current × (1 + rate)^5
Safety factor: 2× projection
Maximum devices: _____

2. Apply Birthday Problem Safe Count Formula

Safe Count = sqrt(Address Space) × 0.85

For your max devices, find minimum address space where:
Max Devices < Safe Count

3. Check Protocol Compatibility

Your Protocol	Native Address Size	Can Extend?
Zigbee	16-bit short	Yes (use 64-bit EUI-64)
LoRaWAN	32-bit DevAddr	Limited (regional allocation)
Thread	16-bit short	Yes (IPv6 underneath)
BLE	48-bit MAC	No (hardware-assigned)

4. Consider Collision Mitigation Strategy

Strategy	Implementation	Best For	Trade-offs
Prevention	Coordinator assigns addresses	Zigbee, star topologies	Requires central coordination; single point of failure
Detection	Duplicate Address Detection (DAD)	IPv6 SLAAC, Thread	Adds join latency (1-2 sec); network overhead
Larger Space	Use 128-bit instead of 16-bit	Any protocol with flexibility	Storage overhead (16 bytes vs 2 bytes)
Hierarchical	Divide address space by location	Large deployments	Requires careful planning; hard to reorganize

5. Calculate Storage and Transmission Overhead

Address size impacts: - Memory: N devices × address_bytes × 2 (storage + routing tables) - Bandwidth: address_bytes per packet × packets_per_day

Example with 1,000 devices:

16-bit addresses: 2 bytes × 1,000 = 2 KB routing table
128-bit addresses: 16 bytes × 1,000 = 16 KB routing table

For sensor sending 100 packets/day:
16-bit: 200 bytes/day addressing overhead
128-bit: 1,600 bytes/day addressing overhead

6. Final Decision Matrix

Score each option (1-5, higher = better):

Criterion	16-bit	32-bit	64-bit	128-bit
Collision risk	1 (high)	3 (medium)	5 (very low)	5 (impossible)
Memory efficiency	5	4	2	1
Bandwidth efficiency	5	4	2	1
Future scalability	1	3	5	5
Implementation cost	5	4	3	2

Choose the option with highest total score meeting your minimum collision risk requirement.

Real-World Example Decision:

Scenario: Smart warehouse, 500 current sensors, 20% annual growth, 5-year horizon.

Calculation:

Max devices = 500 × (1.2)^5 × 2 = 2,488 devices
16-bit safe count = sqrt(65,536) × 0.85 = 218 ✗ (too small)
32-bit safe count = sqrt(4.3B) × 0.85 = 55,700 ✓ (sufficient)

Decision: Use 32-bit addresses (LoRaWAN DevAddr or IPv4 private range).

Validation:

• Collision probability at 2,488 devices in 32-bit space: ~0.07% (acceptable)
• Routing table overhead: 2,488 × 4 bytes = 9.7 KB (manageable)
• Protocol: LoRaWAN supports 32-bit DevAddr natively ✓

This systematic approach prevents the “deploy and discover collision problems later” scenario that plagues many IoT projects.

🏷️ Label the Diagram

Code Challenge

47.6 Summary

This module covered three interconnected topics critical for IoT network design:

• The Birthday Problem reveals that address collisions follow quadratic probability growth – they occur far sooner than linear intuition predicts. Just 300 devices in a 16-bit space create a 50% collision risk.
• Address space sizing must be calculated using the square root rule (Safe Count = sqrt(Address Space) x 0.85), not by comparing device count to total addresses. A 16-bit space supports only ~220 devices safely, while 32-bit supports ~55,000.
• Collision mitigation strategies fall into three categories: prevention (coordinator-assigned addresses), detection (Duplicate Address Detection), and resolution (random backoff and re-addressing).
• Bandwidth requirements for IoT are typically in the Kbps range, not Mbps. Always calculate actual needs before selecting a protocol to avoid over-provisioning that wastes cost and power.
• Right-sizing networks across both address space and bandwidth dimensions produces deployments that are reliable, cost-effective, and appropriately scaled.

47.6.1 Key Formulas

Formula	Purpose
P(collision) = 1 - e(-n2 / 2d)	Collision probability for n devices in d-size address space
Safe count = sqrt(d) x 0.85	Maximum devices for low collision risk
BW (bps) = (N x P x 8) / (T x 60)	Aggregate bandwidth (N devices, P payload bytes, T-minute interval)

47.7 What’s Next

Topic	Chapter	Description
Birthday Problem Deep Dive	The Birthday Problem in IoT Networks	Derive the collision probability formula, work through MAC address and Zigbee short address examples, and use an interactive calculator to predict collision risk for any deployment size
Collision Design Strategies	Collision Design Strategies	Apply hierarchical addressing, Duplicate Address Detection (DAD), UUID design, and case-study analysis to build collision-free IoT networks
Bandwidth Calculations	Bandwidth Requirements and Calculations	Calculate real-world IoT bandwidth needs, compare protocol capacities, and avoid costly over-provisioning with the interactive bandwidth calculator
Radio Propagation	Radio Propagation Fundamentals	Understand how wireless signals travel, attenuate, and reflect – essential context for planning network coverage and link budgets
Network Topologies	IoT Network Topologies	Compare star, mesh, tree, and hybrid topologies and select the right structure for your address space and collision mitigation strategy
MAC Layer Protocols	MAC Layer and Medium Access	Explore how CSMA/CD, CSMA/CA, and TDMA prevent transmission collisions at the MAC layer – complementing address-level collision prevention