13 DTN Epidemic Routing

13.1 Begin With One Copy

This section: Begin With One Copy — A protocol means an agreed set of rules for passing data.

A protocol means an agreed set of rules for passing data. Picture two field teams that meet only now and then. One phone holds a safety note. When the teams meet, the note can be copied. Later, either team may meet the base camp. More copies can raise the chance that the note arrives.

Make the first choice small. Name the message. Name its useful life. Set a copy limit. Set aside space for it. Decide which meetings count. Then run a simple contact test. Start with one carrier. Add two meetings. Count the live copies, the bytes sent, and the energy used. Also check what happens when the note is old or the store is full.

The gain has a cost. Fast spread can crowd out newer work. A long useful life can waste power. A tight limit can miss the only path to the goal. This first story does not predict real movement or prove the best limit. Use the Practitioner layer to set bounds and field checks. Use the Under the Hood layer to model copy growth, contact rates, and resource use. Those deeper routes show when broad copying helps and when it becomes the failure.

13.2 Start Simple

This section: Start Simple

13.3 Start With a Message That Spreads by Contact

This section: Start With a Message That Spreads by Contact — Epidemic routing uses contact opportunities aggressively.

Epidemic routing uses contact opportunities aggressively. When two nodes meet, they compare what messages they carry and exchange missing copies so delivery odds rise through replication.

That simple rule can rescue data in disconnected IoT environments, but it can also consume buffers, energy, and airtime quickly. Start with one message copy, then watch how every contact multiplies both opportunity and cost.

13.4 Flooding as DTN Trade-off

This section: Flooding as DTN Trade-off — Epidemic routing is a delay-tolerant networking strategy for places where an end-to-end path may not exist when a message is created.

Epidemic routing is a delay-tolerant networking strategy for places where an end-to-end path may not exist when a message is created. Nodes store a message, carry it while disconnected, and forward a copy when they meet another node that does not already have it. The design goal is high delivery opportunity, not low overhead.

The important question is not whether epidemic routing can spread a message. It can. The important question is whether the deployment can afford the copies, contact time, buffer space, energy, and stale-message cleanup that flooding creates.

A clean overview starts by naming what the extra copies are buying. In a wildlife collar network, a replicated sighting may be acceptable because the next gateway contact is uncertain and the payload is small. In a battery-powered alarm system, the same replication pattern may be reckless if urgent alarms must share a short contact with routine sensor logs. Epidemic routing is therefore a policy choice about delivery probability, delay tolerance, and resource burn.

The common mistake is to treat epidemic routing as ordinary wireless broadcast. It is not a one-hop flood that disappears when the transmission ends. Each accepted copy becomes stored state with an owner, an expiration rule, and a chance to create more copies at the next encounter. The reader should be able to answer three questions before any diagram looks convincing: who may carry the payload, when does a copy stop spreading, and what lower-value work is displaced when the contact window is full?

Epidemic routing improves the chance of eventual delivery by giving a payload more potential carriers, but every new carrier consumes storage and may spend airtime and energy later, so inspect Figure 13.1 to see why stopping rules are needed before the first contact.

+

The trace in Figure 13.1 opens at T=0 — Create P1, where node A holds the only copy. At T=1 — Exchange IDs, A and B first compare a summary vector and only then copy; that ordering prevents a transmission when the peer already has P1. By T=2 — Copy Spread, the drawing shows 4 copies, making the exponential sequence 1, 2, 4, 8, … concrete. The protocol does not contain an automatic notion of “enough,” so T=3+ — Stop Rule must supply one: delivery, TTL expiry, buffer policy, or a replication limit. That progression connects store-carry-forward reliability to the chapter’s resource argument. A routing design is incomplete if it celebrates extra delivery paths without also specifying which rule halts copying and which queued payload loses capacity while P1 remains live.

The short timeline establishes that copies can grow quickly; the next question is what must happen at each encounter before that growth is justified. Use Figure 13.2 to test the forwarding rule against one complete trace, paying particular attention to the checks that prevent “epidemic” from meaning indiscriminate transmission.

+

In Figure 13.2, t0 — Source S creates and stores message M42 starts the TTL and copy limits while S owns M42 — copy 1. At t1 — Opportunistic encounter: S meets relay A, the numbered notes require the peers to exchange summary IDs, confirm that A lacks M42, and check eligibility before S sends anything; S retaining its buffered copy is replication rather than custody transfer. The later t4 encounter shows why that inventory check matters: B and C both list M42, so no payload crosses the link. Finally, t5 — C encounters destination D records delivery only for this trace and leaves other carriers waiting for a cleanup notice or TTL expiry. The trace turns the broad reliability argument into an implementable policy: every additional path exists because an inventory, lifetime, buffer, contact, and energy gate admitted one more live copy.

Inspect the two node classes in Figure 13.3 to see how one allowed copy changes both the chance of delivery and the number of devices with cleanup work.

+

Read Figure 13.3 by comparing the purple M nodes with the grey ? nodes. An M node holds the message; a ? node does not. The red edge marks one active transfer. After it ends, one more carrier may meet the target. That carrier also uses storage, radio time, and energy, and it may make more copies. Several M marks therefore show both route choice and added cost, not several proofs of delivery. A time limit, copy limit, or delivery receipt must stop later sends and clear copies that no longer help.

13.5 Bound Flooding Before Fielding

This section: Bound Flooding Before Fielding — A practical epidemic design needs a control record.

A practical epidemic design needs a control record. Without it, each message can continue occupying buffers and airtime long after it has stopped being useful. The record should say which messages may replicate, how many copies are allowed, when stale copies expire, and which messages are dropped first when storage is tight.

Start the record at the contact exchange. Each node needs an inventory method, often called a summary vector or message manifest, that says which bundle or payload identifiers it already carries. The receiving node then requests only missing, still-eligible items. That step matters because a ten-second contact can be wasted by duplicate transfers if the nodes do not compare inventories before sending payload bytes.

Next, write the transfer order as an operator-visible rule rather than a hidden implementation guess. Emergency observations may go before routine logs; soon-expiring payloads may go before long-lived ones; large payloads may be deferred unless enough contact time remains. The rule should also define what happens when two limits conflict, such as a high-priority message that is already widely replicated or an old message that is the only copy left.

Inspect Figure 13.4 and look for where another replica stops buying a comparable delivery improvement.

+

Read Figure 13.4 from left to right. The first copies raise delivery because they reach new contact paths. The curve then flattens as later carriers repeat paths already covered. Each extra copy still uses storage, contact time, radio energy, and cleanup work. Pick a copy ceiling and time limit from the required delivery target. Measure both gain and cost near that point. Stop adding copies when the cost keeps rising but the chance of useful delivery barely changes. The bend in the curve, not the highest copy count, marks the useful test region.

Figure 13.5 shows replication overhead keeps rising after delivery gains begin to flatten.

+

13.6 Copy Growth as Resource Model

This section: Copy Growth as Resource Model — Epidemic routing behaves like a resource amplifier.

Epidemic routing behaves like a resource amplifier. One message can become many stored copies. The upper bound is shaped by node count, contact pattern, TTL, copy budget, duplicate suppression, buffer policy, and delivery acknowledgements. This is why the routing decision must be evaluated as a storage, energy, and airtime decision.

At contact time the protocol is an anti-entropy exchange: two nodes compare message identifiers, calculate the set difference, then schedule transfers from the missing eligible set. The exact encoding can vary by implementation, but the state machine should be explicit: discover peer, exchange inventory, choose candidates, transfer payloads, update local metadata, and record partial-transfer failures. If any step is invisible in logs, field debugging quickly becomes guesswork.

Duplicate suppression is as important as replication. A node that receives a payload must record enough identity information to avoid accepting the same copy again under a different contact. A delivered-message acknowledgement or deletion signal can also spread through later contacts so carriers purge copies that no longer need to exist. If the system cannot propagate that cleanup state, the TTL and buffer-drop policy become the only brakes on copy growth.

The resource model should be calculated with worst plausible contact patterns, not only average behavior. High-contact carriers can become buffer hot spots because they meet many peers and receive many copies. Low-contact nodes can hold stale payloads until the TTL expires. A simulator acceptance run should therefore report per-node maximum buffer occupancy, copy count distribution, expired bytes, delivered bytes, contact utilization, and energy-sensitive transmissions, then compare pure epidemic routing with a bounded alternative such as Spray and Wait or PRoPHET-style probabilistic forwarding when overhead is too high.

+

Read Figure 13.6 from "Overhead: about 1000%" to "resources are secondary". Taken together, the figure’s replication-overhead and resource-budget labels show that epidemic routing is the high-replication end of a wider DTN strategy set. For the Copy Growth as Resource Model, the figure’s overhead and resource-budget labels connect replication choices to the next routing decision.

13.7 Stop Epidemic Copies After Delivery

This section: Stop Epidemic Copies After Delivery — A wildlife collar creates message M42 where no base station is reachable.

A wildlife collar creates message M42 where no base station is reachable. Figure 13.1 follows M42 from its first stored copy through opportunistic contacts, and Figure 13.3 distinguishes delivered, carrying, and unaware nodes. The replica charts show the benefit and cost together: more carriers improve contact chances but consume storage, airtime, and energy.

Starting from one carrier, ideal pairwise spreading can grow as 1, 2, 4, and 8 copies across contact rounds. After three doublings, eight stored copies exist for one payload. A delivery receipt, time-to-live, or copy limit must stop later exchanges; otherwise nodes keep spending DTN resources on M42 after the destination already has it.

13.8 Summary

This section: Summary — Epidemic routing improves delivery opportunity in delay-tolerant networks by copying messages during opportunistic contacts.

Epidemic routing improves delivery opportunity in delay-tolerant networks by copying messages during opportunistic contacts. It is useful when connectivity is intermittent and delivery matters more than minimal overhead. It is dangerous when treated as free flooding. A defensible design records summary-vector behavior, TTL, copy budgets, buffer drop rules, contact-window priority, and delivery-versus-overhead evidence before field deployment.

13.9 Key Takeaway

This section: Key Takeaway

13.10 See Also

This section: See Also