Routing Tables and What Happens When the Topology Changes

ETX: why transmissions, not hops

"CTP uses expected transmissions (ETX) as its routing gradient. A root has an ETX of 0. The ETX of a node is the ETX of its parent plus the ETX of its link to its parent." The metric makes sense because nodes retransmit lost packets at the link layer, so the real cost of a hop is how many times it must be sent.

Woo, Tong and Culler explain why hop count misleads on lossy links: "If link quality is not considered in route selection, the real cost of packet delivery can be much larger than the hop count." Shortest-path routing picks long hops, and long hops are the lossy ones ([TOSSIM: Simulating Motes, Radio Gain and Packet Loss] showed the transitional region where they live). "With links of varying quality, a longer path with fewer retransmissions may be better than a shorter path with many retransmissions." They call the transmission count the Minimum Transmission (MT) metric and note that "it is important to determine link quality for both directions since losing an acknowledgment would also trigger a useless retransmission": a link's cost is 1 over the product of its forward and backward qualities.

Worked example. A 10 m link that delivers 95 per cent of packets one way and 90 per cent of acknowledgements the other has ETX 1 / (0.95 × 0.90) = 1 / 0.855, about 1.17. A 20 m link that delivers 40 and 50 per cent has ETX 1 / (0.40 × 0.50) = 1 / 0.2 = 5. Two short hops cost about 2.34 transmissions; one long hop costs 5.

Beacons and link estimates

A node learns its table from routing beacons, in which each neighbour advertises its current path ETX and parent. "When a node hears a routing frame, it MUST update its routing table to reflect the address' new metric." The TinyOS implementation sends beacons "on an exponentially increasing randomized timer", like the Trickle algorithm, so that a stable network beacons rarely, and resets the timer to a short interval when the routing table is empty, when "The node's routing ETX increases by >= 1 transmission", or when it hears a packet asking for routing information.

Link ETX is estimated in two ways and combined: from beacons, which seed the table, and from data traffic, "a direct measure of ETX": the estimator produces a new ETX "every 5 such transmissions, where 0 successes has an ETX of 6." Because data estimates arrive as fast as data is sent, the node "can quickly detect a broken link and switch to another candidate neighbor."

A tree, a table, and a death, computed

The program places 40 nodes at random over 60 m by 60 m, with the root at a corner. Link quality is illustrative: 1 up to 8 m, falling to 0 at 22 m, and a little different in each direction. A link's ETX is 1 / (forward × backward quality); links with ETX above 10 are ignored, and path ETX is capped at 30, as CTP caps routes with "an ETX higher than a reasonable constant". In each beacon round every node advertises its path ETX and then re-chooses its parent from its table, keeping its current parent unless another neighbour is better by a margin of 0.5 ETX, Woo, Tong and Culler's "noise margin". The program builds the tree, prints the deepest node's table, compares the tree's routes with hop-count routes over the same links, and then kills the relay on the most nodes' routes and lets the tree repair itself, watching for loops.

# A collection tree built the way TinyOS's CTP builds one. 40 nodes at random
# over 60 m by 60 m, the root at a corner. A link's quality falls from 1 at
# 8 m to 0 at 22 m, a little differently each way (illustrative). A link's
# ETX is 1 / (forward quality x backward quality), links with ETX over 10 are
# ignored, and a node's path ETX is its parent's plus the link's. Every round
# each node beacons its path ETX, and each node picks the neighbour with the
# lowest total, switching parent only if the new one is better by MARGIN.
import math
import random

rnd = random.Random(62)
N, SIDE, MARGIN, CAP = 40, 60.0, 0.5, 30.0
pts = [(0.0, 0.0)] + [(rnd.uniform(0, SIDE), rnd.uniform(0, SIDE)) for _ in range(N - 1)]

def quality(d):
    return 1.0 if d <= 8 else max(0.0, 1 - (d - 8) / 14)

etx = {}
for i in range(N):
    for j in range(i + 1, N):
        d = math.dist(pts[i], pts[j])
        qf = min(1.0, quality(d) * rnd.uniform(0.85, 1.0))
        qb = min(1.0, quality(d) * rnd.uniform(0.85, 1.0))
        if qf * qb > 0.1:                              # ETX below 10
            etx[i, j] = etx[j, i] = 1 / (qf * qb)
nbrs = {i: [j for j in range(N) if (i, j) in etx] for i in range(N)}

def converge(alive, path, parent):
    """Beacon rounds until nothing changes. Returns the rounds taken and the
    number of rounds in which some nodes' parents formed a loop."""
    rounds = looped = 0
    while True:
        rounds += 1
        adv = dict(path)                               # this round's beacons
        changed = False
        for u in alive:
            if u == 0:
                continue
            options = [(etx[u, v] + adv[v], v) for v in nbrs[u] if v in alive and adv[v] < CAP]
            if not options:
                new, p = CAP, None
            else:
                new, p = min(options)
                cur = parent.get(u)
                if cur in alive and cur is not None and adv[cur] < CAP:
                    keep = etx[u, cur] + adv[cur]
                    if keep <= new + MARGIN:           # not better by the margin: stay
                        new, p = keep, cur
            if p != parent.get(u) or abs(new - path[u]) > 1e-9:
                changed = True
            path[u], parent[u] = new, p
        if any(in_loop(u, parent) for u in alive):
            looped += 1
        if not changed or rounds > 200:
            return rounds, looped

def in_loop(u, parent):
    seen = set()
    while u is not None and u != 0:
        if u in seen:
            return True
        seen.add(u)
        u = parent.get(u)
    return False

alive = set(range(N))
path = {u: (0.0 if u == 0 else CAP) for u in range(N)}
parent = {}
rounds, _ = converge(alive, path, parent)
print("tree built in %d beacon rounds; %d links usable" % (rounds, len(etx) // 2))

def on_route(w, u):
    """Is u on w's route to the root?"""
    while w not in (None, 0):
        if w == u:
            return True
        w = parent.get(w)
    return False

def hops_to_root(u):
    h = 0
    while u != 0:
        u, h = parent[u], h + 1
    return h

reached = [u for u in alive if u and path[u] < CAP]
show = max(reached, key=hops_to_root)
print("%d of %d nodes have a route; the deepest, node %d, has path ETX %.2f in %d hops"
      % (len(reached), N - 1, show, path[show], hops_to_root(show)))
print("its routing table:")
print("  neighbour  link ETX  advertised  total")
for v in sorted(nbrs[show], key=lambda v: etx[show, v] + path[v]):
    print("  %9d %9.2f %11.2f %6.2f%s" % (v, etx[show, v], path[v], etx[show, v] + path[v],
                                          "   <- parent" if v == parent[show] else ""))

# the same links routed by hop count instead: breadth-first from the root
from collections import deque
hop, via, q = {0: 0}, {}, deque([0])
while q:
    a = q.popleft()
    for b in sorted(nbrs[a]):
        if b not in hop:
            hop[b], via[b] = hop[a] + 1, a
            q.append(b)
def hop_route_etx(u):
    total = 0.0
    while u != 0:
        total, u = total + etx[u, via[u]], via[u]
    return total
print("over the %d routed nodes: hop-count routes average %.2f hops and %.2f ETX;"
      % (len(reached), sum(hop[u] for u in reached) / len(reached),
         sum(hop_route_etx(u) for u in reached) / len(reached)))
print("the ETX tree's routes average %.2f hops and %.2f ETX"
      % (sum(hops_to_root(u) for u in reached) / len(reached),
         sum(path[u] for u in reached) / len(reached)))

relay = max(reached, key=lambda u: sum(on_route(w, u) for w in reached if w != u))
affected = [w for w in reached if w != relay and on_route(w, relay)]
before = {w: path[w] for w in affected}
alive.discard(relay)
rounds, looped = converge(alive, path, parent)
print("node %d dies: it was on the route of %d nodes" % (relay, len(affected)))
print("re-converged in %d beacon rounds; a routing loop existed in %d of them" % (rounds, looped))
cut = [w for w in affected if path[w] >= CAP]
worse = [path[w] - before[w] for w in affected if path[w] < CAP]
print("afterwards %d are cut off; the others' path ETX rose by %.2f on average, %.2f at most"
      % (len(cut), sum(worse) / len(worse), max(worse)))

Figure 62.1 The program's collection tree before and after its busiest relay dies

Reading it: building the tree. Starting with only the root's ETX known, the tree forms in 9 beacon rounds, each round's beacons carrying the gradient one hop further. 36 of the 39 nodes have a route; the other 3 have no usable link within the ETX limits.

Reading it: one table. The deepest node, 6, reaches the root in 8 hops at a path ETX of 16.71. Its table lists five neighbours. Neighbour 15 now offers the lowest total, 16.53, but node 6 keeps its parent 13, at 16.71: the difference, 0.18, is smaller than the 0.5 margin. Without the margin, small fluctuations in link estimates would make nodes change parent constantly, and each change would ripple through the tree below them. Neighbour 23 shows why ETX matters: it advertises the best path of all (14.30) but its link to node 6 costs 4.21 transmissions.

Reading it: ETX against hop count. Over the same usable links, hop-count routes average 3.56 hops but 18.06 expected transmissions; the ETX tree's routes average 5.08 hops and 11.46 transmissions, about 37 per cent fewer. Hop count chooses long, lossy hops; ETX chooses more, shorter, reliable ones.

Reading it: a death. The busiest relay, node 29, next to the root, was on the route of 34 nodes. After it dies, the tree re-forms in 11 beacon rounds, no node is cut off, and path ETX rises by 0.90 on average and 2.88 at most. No loop formed in this run; the next section is about the runs where one does.

Loops, and CTP's two defences

"Routing loops generally occur when a node choose a new route that has a significantly higher ETX than its old one, perhaps in response to losing connectivity with a candidate parent. If the new route includes a node which was a descendant, then a loop occurs." A child whose parent has died may see its own child still advertising the old, cheap path through the dead node, choose it, and so point at a node that points back at it. Each then advertises a slightly higher ETX than the other, and the numbers climb, the count to infinity of distance-vector routing, which the paired practical demonstrates.

CTP has two defences:

1. Every data frame carries the sender's ETX. A node that receives data from a node whose ETX is lower than its own knows the tree is inconsistent (data should always flow downhill in ETX), and "CTP tries to resolve the inconsistency by broadcasting a beacon frame, with the hope that the node which sent the data frame will hear it and adjust its routes accordingly." The data traffic itself detects loops, quickly, wherever there is traffic.
2. A cap on ETX. "If a collection of nodes is separated from the rest of the network, then they will form a loop whose ETX increases forever. CTP's second mechanism is to not consider routes with an ETX higher than a reasonable constant." The program's cap of 30 plays this part.

Loops also complicate duplicate suppression: a looping packet revisits nodes, so CTP's data frames carry a time-has-lived count that distinguishes a looping packet from a duplicate sent twice.

Distinctions

What it does not mean

A routing table is not a list of destinations here. A collection node has one destination; its table is a list of neighbours and their costs to it.

The lowest total is not always chosen. A parent is kept unless another neighbour is better by the margin; stability is worth a little cost.

More hops is not worse. On lossy links, ETX's longer routes need fewer transmissions, and so less energy and delay.

A dead node is not reported by anyone. Its children notice missing acknowledgements or beacons and choose again from their tables; the change spreads through ordinary beacons.

Quick revision

• Collection tree (CTP): data flows to a root through a parent; address-free: choosing a next hop chooses the root.
• ETX gradient: root 0; node ETX = parent's ETX + link ETX; link ETX = 1 / (forward × backward quality) (the MT metric of Woo, Tong and Culler).
• Routing table: neighbour, link ETX, advertised path ETX, total; parent = lowest total, changed only if better by a margin.
• Beacons advertise path ETX on a Trickle-like timer, reset when the table is empty, ETX rises by 1 or more, or a neighbour asks. Link estimates from beacons and from data (every 5 transmissions; none acknowledged counts as ETX 6).
• Loops: a node choosing a former descendant; CTP detects data from a lower-ETX sender and beacons; caps ETX.
• Program: tree in 9 rounds; hop-count routes 3.56 hops, 18.06 ETX against ETX routes 5.08 hops, 11.46 ETX; the busiest relay (on 34 routes) dies: re-formed in 11 rounds, none cut off, ETX up 0.90 on average.

Test yourself

1. What does a node's routing table contain in a collection tree protocol such as CTP? For each neighbour: the ETX of the link to it, the path ETX it last advertised to the root, and their sum, the cost of routing through it. The node chooses as its parent the neighbour with the lowest sum, and its own path ETX, which it advertises in its beacons, is that sum.

2. What is ETX, and why is it a better routing metric than hop count in a sensor network? ETX is the expected number of transmissions, including retransmissions, needed to deliver a packet and receive its acknowledgement over a link, estimated as 1 over the product of the forward and backward delivery ratios; a path's ETX is the sum of its links' ETX. Hop count ignores link quality and so prefers long, lossy links that need many retransmissions. In the program, hop-count routes averaged 3.56 hops but 18.06 transmissions, ETX routes 5.08 hops but 11.46 transmissions.

3. Compute the ETX of a link with 80 per cent forward and 75 per cent backward delivery, and compare it with a route of two links of ETX 1.2 each. 1 / (0.80 × 0.75) = 1 / 0.6, about 1.67. The two-link route costs 1.2 + 1.2 = 2.4, so the single link is cheaper despite being less reliable than either of the two.

4. Why does CTP use a margin when choosing a parent? Link estimates fluctuate, and if a node switched to whichever neighbour looked slightly cheaper each time, parents would change constantly and every change would disturb the tree below. Keeping the current parent unless another is better by a margin makes the tree stable at a small cost in optimality; in the program, a node kept a parent costing 0.18 more than the best, within the 0.5 margin.

5. What happens in a collection tree when a relay node dies? Its children stop receiving acknowledgements or beacons from it, remove it from their tables, and choose the neighbour with the next lowest total as their new parent. Their path ETX changes, their beacons carry the new value, and the change spreads down their subtrees until the tree is consistent again. In the program, a relay on 34 nodes' routes died and the tree re-formed in 11 beacon rounds with every node still connected.

6. How do routing loops form, and how does CTP deal with them? When a node loses its parent it may choose a neighbour that was its own descendant and still advertises an old, cheap route through the lost parent; the two then point at each other and their advertised ETX climbs. CTP detects loops on the data path: every data frame carries the sender's ETX, and a node that receives data from a node with a lower ETX than its own broadcasts a beacon to correct it. It also ignores routes whose ETX exceeds a set limit, which stops a partitioned loop counting upwards for ever.