Transport Protocols Built for Sensor Networks: PSFQ, ESRT, CODA and RMST

Pump. "A user node broadcasts a packet to its neighbors every Tmin until all the data fragments has been sent out." A neighbour checks its cache, drops duplicates, decrements the TTL and then, only "if the TTL value is not zero and there is no gap in the sequence number", schedules the fragment to be forwarded after "a random period between Tmin and Tmax". The random delay matters on a broadcast medium, "to avoid collisions because RTS/CTS dialogues are inappropriate in broadcasting operations when the timing of rebroadcasts among interfering nodes can be highly correlated."

In-sequence forwarding is the second mechanism. A node with a gap forwards nothing past it. PSFQ thereby localises the damage: "By localizing loss events and not relaying any higher sequence number messages until recovery has taken place, this mechanism operates in a similar fashion to a store-and-forward" scheme. The gap is repaired where it happened, not carried onward.

Fetch. "A node goes into fetch mode once a sequence number gap in a file fragments is detected. A fetch operation is the proactive act of requesting a retransmission from neighboring nodes once loss is detected at a receiving node." It is aggressive, on a timer much shorter than the pump's, which is the protocol's name: pump slowly, fetch quickly. To save messages, "PSFQ uses the concept of 'loss aggregation' whenever loss is detected; that is, it attempts to batch up all message losses in a single fetch operation whenever possible."

Report. A NACK protocol leaves the sender blind, so PSFQ adds feedback on demand: the user sets a report bit, and "The report message is designed to travel from the furthest target node back to the user on a hop-by-hop basis. Each node en route toward the user is capable of piggybacking their report message in an aggregated manner." One message gathers the status of a whole path instead of one message per node.

Timers. Tmin paces the pump, Tmax bounds the forwarding delay, and together they give the loose delay bound the protocol promises: D(n) = Tmax × n × (number of hops), for a file of n fragments.

ESRT: reliability of the event, not of the packet

ESRT carries reports up, and begins by refusing the usual goal. Its notion, from [Transport Protocol Design Issues in WSNs], is event reliability: the observed reliability ri is the number of data packets received in a decision interval, the desired reliability R is what the application needs, and the problem is "to configure the reporting rate, f, of source nodes so as to achieve the required event detection reliability, R, at the sink with minimum resource utilization."

Write eta for ri divided by R. As f rises, eta rises, until the network cannot carry the load and congestion pulls it down. That curve divides into five regions, which the paper defines with a tolerance eps and the frequency fmax at which congestion begins:

• (NC, LR): no congestion, low reliability, f below fmax and eta below 1 - eps.
• (NC, HR): no congestion, high reliability, f at most fmax and eta above 1 + eps.
• (C, HR): congestion, high reliability, f above fmax and eta above 1.
• (C, LR): congestion, low reliability, f above fmax and eta at most 1.
• OOR, the optimal operating region: f below fmax and eta within eps of 1.

Figure 71.1 ESRT's five regions, after its Fig. 4, with the program's two trajectories

The sink runs one rule at the end of each decision interval and broadcasts the new f. In the paper's own pseudo-code (its Figure 6), with k a counter of consecutive congested intervals:

• (C, LR): decrease aggressively, f becomes f raised to the power eta / k, and k increases. Reliability is low and the network is congested, so the rate must come down hard.
• (C, HR): relieve the congestion without giving up reliability, f becomes f / eta, and k returns to 1.
• (NC, LR): increase aggressively, f becomes f / eta.
• (NC, HR): decrease cautiously, f becomes (f / 2)(1 + 1 / eta), which is half way between f and f / eta: more reliability than needed is energy wasted, but the cut is gentle.
• OOR: hold, f unchanged.

Two things are worth noticing. The sink does the deciding, so the nodes stay simple: they listen for the broadcast and set their rate. And congestion is reported by the nodes cheaply: each watches its own buffer and, if the level would overflow in the next interval, sets a congestion notification bit in the header of the packets it forwards.

CODA: detect congestion, push back, then regulate

CODA does not deliver data; it keeps the network from drowning in it. Its setting is the event impulse: "Sensor networks typically operate under light load and then suddenly become active in response to a detected or monitored event", and it is exactly then that "the information it delivers is of greatest importance."

Its three mechanisms:

• Receiver-based congestion detection. "CODA uses a combination of the present and past channel loading conditions, and the current buffer occupancy, to infer accurate detection of congestion at each receiver with low cost." Listening costs energy, so "CODA uses a sampling scheme that activates local channel monitoring at the appropriate time to minimize cost while forming an accurate estimate."
• Open-loop hop-by-hop backpressure. "Once congestion is detected, the receiver will broadcast a suppression message to its neighbors and at the same time make local adjustments to prevent propagating the congestion downstream." Upstream nodes "could throttle their sending rates or drop packets based on some local congestion policy (e.g., packet drop, AIMD, etc.)", and each decides whether to pass the signal further. CODA names the distance the signal travels the depth of congestion: "the number of hops that the backpressure message has traversed before a non-congested node is encountered."
• Closed-loop multi-source regulation. For congestion that will not go away, the sink takes charge. A source whose rate passes a fraction of the channel's theoretical maximum sets a regulate bit; the sink then sends acknowledgements at a set rate (the paper's example is one per hundred events), and "The reception of ACKs at sources would serve as a self-clocking mechanism allowing the sources to maintain the current event rate". A source that stops hearing them must slow down.

CODA is judged by two measures of its own: the energy tax it charges and the fidelity penalty it imposes on the application.

RMST: NACKs along a diffusion path

RMST is a reliability layer for directed diffusion ([Directed Diffusion and Rumour Routing]), implemented "as a filter that could be attached to any diffusion node on an as needed basis". It exists for the data that cannot lose a fragment: "A single missing fragment from a large binary object (such as executable code) may render the data entity useless; therefore, transport layer facilities are required."

• Fragments and entities. A data entity is split into fragments, each with a fragment number, and the total is known, so a receiver can see exactly what is missing. "Reliability in RMST refers to the eventual delivery to all subscribing sinks of any and all fragments related to a unique RMST entity."
• Loss detection. A watchdog timer. "In non-caching mode, only sinks set timers to detect loss. In caching mode, each caching node on the reinforced path from source to sink detects loss."
• Repair. A single control message, the NACK, travels back along the reverse reinforced path; a node with the fragment cached answers, otherwise the NACK travels on toward the source.
• Two modes. "In caching mode, the caching of fragments along reinforced paths is used to limit power loss due to end-to-end retransmission. In non-caching mode, the underlying MAC layer is exploited to limit the transport layer overhead."
• Node failure is diffusion's business: a new reinforced path appears, and the RMST filter follows it.

RMST's wider finding is where reliability belongs: "We conclude that reliability is important at the MAC layer and the transport layer. MAC-level reliability is important not just to provide hop-by-hop error recovery for the transport layer, but also because it is needed for route discovery and maintenance."

The protocols, run

The program delivers a 40-fragment file along a chain of ten relays, each hop losing 15 per cent, with PSFQ's pump, cache and in-sequence forwarding, once with fetch and once without; then it runs ESRT's Figure 6 rule on a model network whose reports peak at f = 40 and collapse beyond it, with 20 reports required, starting below, just above and far above the peak.

# Two of the four protocols, run. PSFQ's pump with in-sequence forwarding and
# its fetch, against the same pump without fetch; then ESRT's own algorithm
# (its Figure 6) driven to the optimal operating region.
import math
import random

# ---- PSFQ.
# A user node injects a 40-fragment file along a chain of 10 relays.
# The pump sends each fragment once; a node caches what arrives and forwards
# only in sequence, so a gap stops it. With fetch, a node that sees a gap asks
# the node upstream, which resends from its cache, and the request is repeated
# until the hole is filled (loss aggregation is not modelled: one fetch per
# gap). Without fetch, a lost fragment is lost and the node stalls there.
def psfq(hops=10, frags=40, q=0.15, fetch=True, seed=71):
    rnd = random.Random(seed)
    have = [set(range(1, frags + 1))] + [set() for _ in range(hops)]
    sends, fetches = 0, 0
    for n in range(hops):
        for frag in range(1, frags + 1):
            if frag not in have[n]:
                break                                   # nothing upstream to pump
            if len(have[n + 1]) + 1 != frag:
                break                                   # a gap: in-sequence forwarding stops
            sends += 1
            if rnd.random() > q:
                have[n + 1].add(frag)
                continue
            if not fetch:
                break                                   # lost, and nobody will ask
            while True:                                 # fetch until the hole is filled
                fetches, sends = fetches + 1, sends + 1
                if rnd.random() > q:
                    have[n + 1].add(frag)
                    break
    return [len(h) for h in have], sends, fetches

for fetch in (True, False):
    got, sends, fetches = psfq(fetch=fetch)
    print("PSFQ %-7s fetch: fragments at each node %s" % ("with" if fetch else "without", got))
    print("                     %d transmissions, %d of them fetch requests and their answers"
          % (sends, 2 * fetches))

# ---- ESRT, exactly the algorithm of its Figure 6. eta is the normalised
# reliability, reports received over reports required. The sink runs this at
# the end of every decision interval and broadcasts the new frequency f.
def esrt_step(f, eta, congestion, k, eps=0.05):
    if congestion:
        if eta < 1:
            return f ** (eta / k), k + 1                # (C, LR): decrease aggressively
        if eta > 1:
            return f / eta, 1                           # (C, HR): relieve the congestion
        return f, k
    if eta < 1 - eps:
        return f / eta, 1                               # (NC, LR): increase aggressively
    if eta > 1 + eps:
        return f / 2 * (1 + 1 / eta), 1                 # (NC, HR): decrease cautiously
    return f, 1                                         # OOR: hold

# A model network, after the shape of the paper's Fig. 4: reports rise with f
# but contention eats into them, they peak at fmax, and beyond it congestion
# collapses them. R reports are required in a decision interval.
fmax, R, eps = 40.0, 20.0, 0.05
def eta_of(f):
    got = f * (1 - f / (2 * fmax)) if f <= fmax else fmax / 2 * math.exp(-(f - fmax) / 15)
    return got / R

def state(f, eta):
    if f > fmax:
        return "(C, LR)" if eta < 1 else "(C, HR)"
    if eta < 1 - eps:
        return "(NC, LR)"
    if eta > 1 + eps:
        return "(NC, HR)"
    return "OOR"

print("\nESRT (Figure 6): reports peak at f = %.0f, %.0f are required, eps = %.2f" % (fmax, R, eps))
for start in (4.0, 55.0, 90.0):
    f, k, row = start, 1, []
    for _ in range(9):
        eta = eta_of(f)
        row.append("%6.2f %5.3f %-8s" % (f, eta, state(f, eta)))
        f, k = esrt_step(f, eta, f > fmax, k, eps)
    print("  from f = %5.1f" % start)
    for line in row:
        print("     f =%s" % line)

Fetch is the protocol. With fetch, every one of the ten relays ends with all 40 fragments, at 468 transmissions, of which 136 belong to fetch requests and their answers: 29 per cent overhead for complete delivery over a chain losing 15 per cent per hop. Without fetch, the first relay receives two fragments before one is lost, and in-sequence forwarding stops it there; the file never reaches the rest, and only 11 transmissions are made. In-sequence forwarding without fetch is a dam; with fetch it is what makes each hop repair its own loss.

ESRT finds its region. From f = 4, eta is 0.19, so (NC, LR) increases the rate aggressively to 21.05, then 27.14, 30.27, 32.17, where eta is 0.962, within eps of 1: OOR, and the rate holds. From f = 55 the network is congested and eta only 0.368, so the (C, LR) rule, f raised to the power eta, cuts the rate to 4.37 in one interval, and the climb begins again. From f = 90, eta is 0.036 and the rate collapses to 1.17. The aggressive cut is deliberate: while the network is congested and unreliable, every packet sent is wasted, so ESRT would rather start again from almost nothing than creep down. Notice also where it stops: eta = 0.96, not 1. The optimal region is a band, and holding inside it is the goal, because chasing eta = 1 exactly would cost more energy than the accuracy is worth.

Distinctions

What it does not mean

PSFQ is not a routing protocol. "Recall that PSFQ is not a routing solution but a transport scheme"; it can run over diffusion, DSDV or plain broadcast.

ESRT does not make packets reliable. It never retransmits: it changes how often sources report, so enough arrive.

A high eta is not good news. Above 1 + eps the network is spending energy on reports the application does not need, which is why ESRT cuts the rate there too.

CODA does not deliver anything. It is congestion control alone, to be run beside a delivery scheme such as diffusion.

RMST's caches are not always worth it. Its own conclusion is that once the MAC's retries bring losses below about 1 per cent, caching and hop-by-hop repair stop paying.

None of the four is a TCP replacement. Each answers part of the problem, for one direction and one kind of reliability.

Quick revision

• PSFQ: downstream, hop-by-hop, NACK. Pump every Tmin, relay after a random Tmin to Tmax, cache, forward only in sequence, TTL. Fetch aggressively on a gap, with loss aggregation. Report on demand, aggregated hop by hop. Delay bound D(n) = Tmax × n × hops.
• ESRT: upstream, event reliability; eta = observed / desired; five regions (NC/C, LR/HR, OOR); rules f / eta (NC, LR), (f / 2)(1 + 1 / eta) (NC, HR), f / eta (C, HR), f^(eta / k) (C, LR), hold in OOR; nodes set a congestion notification bit from their buffer level.
• CODA: congestion detection (channel loading + buffer, sampled), open-loop hop-by-hop backpressure (depth of congestion), closed-loop sink regulation (regulate bit, ACKs as self-clocking). Metrics: energy tax, fidelity penalty.
• RMST: over directed diffusion, a filter; entities in fragments; watchdog timers, NACK back along the reinforced path; caching or non-caching mode; reliability belongs in the MAC and the transport layer.
• Program: PSFQ with fetch, all 40 fragments at all 10 relays, 468 transmissions (136 fetch); without fetch the file stops at the first relay. ESRT reaches OOR (eta 0.962) from f = 4, and cuts 55 to 4.37 and 90 to 1.17 when congested.

Test yourself

1. Explain PSFQ's three operations. The pump operation injects fragments: the user node broadcasts one every Tmin, and each relay caches what it receives, discards duplicates, decrements the TTL and forwards the fragment after a random delay between Tmin and Tmax, but only if there is no gap in the sequence numbers. The fetch operation is error recovery: a node that detects a gap goes into fetch mode and aggressively requests the missing fragments from its neighbours, batching several losses into one request by loss aggregation. The report operation returns delivery status to the user on demand: the furthest node starts a report message that travels back hop by hop, and each node on the way appends its own status, so one message carries the status of a whole path.

2. Why does PSFQ pump slowly and fetch quickly? Pumping slowly keeps the injected traffic light, so congestion, which is not the main cause of loss in sensor networks, does not arise, and neighbouring relays do not collide with one another. Fetching quickly repairs a gap in far less time than the interval between pumped fragments, so the loss is made good before the next fragment is due and the node can keep forwarding in sequence; the loss is contained at the hop where it happened rather than propagating downstream.

3. Define ESRT's reliability measure and its five regions. The observed event reliability is the number of data packets received at the sink in a decision interval, the desired reliability is the number the application needs, and eta is their ratio. With fmax the reporting frequency at which congestion begins and eps a tolerance, the regions are: (NC, LR), no congestion and eta below 1 - eps; (NC, HR), no congestion and eta above 1 + eps; (C, HR), congestion with eta above 1; (C, LR), congestion with eta at most 1; and the optimal operating region, no congestion and eta within eps of 1.

4. Give ESRT's rule for updating the reporting frequency in each region. In (NC, LR) the frequency is increased aggressively to f / eta. In (NC, HR) it is decreased cautiously to (f / 2)(1 + 1 / eta). In (C, HR) it is decreased to f / eta, relieving the congestion without giving up reliability. In (C, LR) it is decreased aggressively to f raised to the power eta / k, where k counts consecutive congested intervals. In the optimal operating region it is left unchanged.

5. Describe CODA's three mechanisms. Congestion detection at the receiver, which combines the present and past channel loading, measured by sampling the channel to save energy, with the current buffer occupancy. Open-loop hop-by-hop backpressure: a congested node broadcasts backpressure messages upstream, and each node that receives one throttles its sending rate or drops packets by its local policy and decides whether to propagate the signal further; the number of hops the signal travels is the depth of congestion. Closed-loop multi-source regulation: when a source's rate exceeds a fraction of the channel's theoretical maximum it sets a regulate bit, and the sink then sends acknowledgements at a set rate which the sources need in order to keep sending, so the sink controls all the sources of an event.

6. What is RMST, and what are its two modes? RMST, reliable multi-segment transport, is a transport layer for sensor networks implemented as a filter over directed diffusion. It splits a data entity into numbered fragments, guarantees the eventual delivery of every fragment to all subscribing sinks, detects loss with watchdog timers and repairs it with NACKs sent back along the reverse reinforced path. In caching mode every node on the path caches fragments and can answer a NACK, so repairs are hop by hop; in non-caching mode only the source and the sinks cache and only sinks set timers, and the protocol relies on the MAC's own retries, trading memory against transmissions.

7. Which of the four protocols would you choose to send a new program image to every node, and why? PSFQ, because the traffic goes downstream from the user node to many receivers, every fragment must arrive since a single missing fragment makes an executable useless, and the load is light enough to pump slowly. Its in-sequence forwarding with hop-by-hop fetch repairs each loss at the hop where it happens, which is what a long lossy path needs, and its report operation tells the user which nodes have the complete image before the new task is started.