The DARPA Packet Radio Network Protocols

One-line summary: This paper is a more recent version of the Advances in Packet Radio Technology paper, describing the DARPA PRnet system.

Overview/Main Points

• Autonomy of Packet Radios (PRs): The PRs are completely standalone units that communicate with a digital counterpart; the digital counterpart implements transport and above layers (TCP, etc) while the PR units implement the network and below layers (IP, etc). The PR OS/firmware can be loaded over an RS-232 link or over the radio link; debugging can be done similarly.
• Network size: In this paper, it is stated up front that the PRnet was designed with at most 138 "entities" in mind - entities include PRs, repeaters, etc. Larger networks can be created by piecing PRnets together with gateways.
• Route calculation: Each PR maintains 3 tables:
  1. neighbor table - the neighbor table contains one entry per neighbor PR (a neighbor is exactly 1 hop away). It is built via the exchange of "PROP" messages - each PR sends a PROP message out every 7.5s. Each entry also contains link quality values (quality changes have hysteresis to avoid yo-yoing).
  2. tier table - each neighbor is said to be at tier 1 from a PR. All PR's that are exactly 2 hops from a PR (and thus not in tier 1) are at tier 2 from the PR. The tier table contains a list of all known destination PRs in the network, along with each destination PR's tier and the next PR along the best route to that destination PR. Again, PROP messages are used to build the tier table; PROP packets thus contain subsets of the PROP originator's tier table. Changes in link connectivity are reflected in tier tables; care must be taken to not introduce loops.
  3. device table - this table provides a mapping from digital device names to PR addresses.
• Packet Headers: An end-to-end (ETE) header contains source and destination IDs, and a type of service flag. The routing header (encapsulating the ETE header) contaings source and destination IDs, sequence numbers, and state modified by intermediate PRs for routing purposes. This state includes the previous PR router ID and transmit count, the transmitting PRs ID and transmit count, and the next PR ID along the route. Also included in this state are flags used when the best route fails - an "alternate routing request flag" indicates that the intended next PR is not acknowledging receipt, and that any PR of the same or lower tier than the intended next PR can forward the packet instead. The "lateral alternate routing flag" indicates that this has taken place, and that the next PR to forward the packet must have a strictly lower tier number to prevent packets perpetually circulating at a constant tier.
• Pacing: A packet send from PR L to PR M experiences a triple delay; the time to go from L to M, the time to go from M to the next PR N (which includes an implicit acknowledgment), and the time for the implicit acknowledgement from N back to M. This third delay is necessary because M can only receive from one radio at a time. Successive packets from a given PR are thus paced with this triple forwarding delay imposed on them. Also, a second packet to the same next-hop PR is not sent until the first packet is acknowledged; this is done for congestion and flow control, and is called single-threading.
• Fairness queues: The normal FIFO packet ordering from a PR is altered to expedite packets from a PR with poor radio connectivity to maintain fairness.
• CSMA: CSMA is used, with random delays imposed once a channel becomes free and (exponential?) backoffs in case of collisions.

Relevance

Flaws

• Maintaining complete routing tables for the entire network at each node seems wasteful; this must be why they claim a maximum of 138 network entities.