Practical 14: Performance Evaluation of MANET Routing Protocols

Everything except the three arguments is fixed: twenty nodes in 1000 m by 500 m; five flows, 0 to 10, 2 to 12, 4 to 14, 6 to 16 and 8 to 18, from 5 s to 95 s; 100 s in all.

The movement is random waypoint, generated inside the script. Each node repeatedly picks a random point and a random speed between 1 m/s and the top speed, travels there, pauses 2 s, and picks again. Practical 11's setdest does the same, but seeds itself from the clock and so writes a different file every time. Here the random numbers come from ns-2's own generator, RNG, with a fixed seed: the same seed gives the same network on every run, for every protocol. Two generators are used, one for the starting positions and one for the moves, so that a network's starting positions are the same at every speed.

Every run writes run.tr and run.nam, overwriting the last run's, so that 36 runs never need 36 traces on the disk.

Step 2: measuring one run

one.awk reduces a run to one line: protocol, speed, network, delivery ratio in per cent, throughput in kbit/s, average delay in ms, and routing load.

# one.awk: one run's measures on one line: protocol speed seed delivered% throughput delay routing-load
$1 == "s" && $4 == "AGT" && $7 == "cbr" { sent++; start[$6] = $2; size[$6] = $8 }
$1 == "r" && $4 == "AGT" && $7 == "cbr" { got++; bits += size[$6] * 8; delay += $2 - start[$6] }
$4 == "RTR" && ($1 == "s" || $1 == "f") && $7 != "cbr" { routing++ }
END { printf "%s %s %s %.1f %.1f %.1f %.2f\n", proto, speed, seed, got * 100 / sent, bits / 90 / 1000, delay / got * 1000, routing / got }

Throughput divides the delivered bits by 90 s, the time the flows run. Each delivered packet counts at the size its source sent, 512 bytes, because the size a trace line shows on arrival differs between protocols (Practical 13).

$ ns eval.tcl AODV 10 1 > /dev/null 2>&1
$ awk -v proto=AODV -v speed=10 -v seed=1 -f one.awk run.tr
AODV 10 1 92.8 76.0 140.5 0.84

Step 3: thirty-six runs

A short shell script runs every protocol, at every speed, on every network, and prints one line per run:

# sweep.sh: every protocol, at every top speed, on every network, one line of measures per run
for v in 2 5 10 20; do
    for p in AODV DSR DSDV; do
        for s in 1 2 3; do
            ns eval.tcl $p $v $s > /dev/null 2>&1
            awk -v proto=$p -v speed=$v -v seed=$s -f one.awk run.tr
        done
    done
done

On the machine this book was checked on, all 36 runs took under half a minute. Keep the output: it is the experiment's data.

$ bash sweep.sh > results.txt
$ wc -l results.txt
36 results.txt

summary.awk averages the three networks at each point, and gives the lowest and highest delivery ratio among them:

# summary.awk: per protocol and speed, the average of every measure and the range of the delivery ratio
{ k = $1 " " $2; n[k]++; order[k] = NR
  pdr[k] += $4; tput[k] += $5; dly[k] += $6; rl[k] += $7
  if (!(k in lo) || $4 < lo[k]) lo[k] = $4
  if (!(k in hi) || $4 > hi[k]) hi[k] = $4 }
END {
    printf "%-5s %5s  %13s  %18s  %13s  %12s\n", "", "speed", "throughput", "delivered", "delay", "routing load"
    for (k in n) line[order[k]] = k
    for (i = 1; i <= NR; i++) if (i in line) {
        k = line[i]; split(k, f, " ")
        printf "%-5s %3s m/s  %7.1f kbit/s  %5.1f %% (%5.1f-%5.1f)  %8.1f ms  %12.2f\n",
            f[1], f[2], tput[k] / n[k], pdr[k] / n[k], lo[k], hi[k], dly[k] / n[k], rl[k] / n[k]
    }
}

$ awk -f summary.awk results.txt
      speed     throughput           delivered          delay  routing load
AODV    2 m/s     75.0 kbit/s   91.5 % ( 79.8- 99.3)     122.3 ms          0.20
DSR     2 m/s     76.1 kbit/s   92.9 % ( 79.9- 99.7)     174.5 ms          0.13
DSDV    2 m/s     46.6 kbit/s   56.9 % ( 37.4- 82.8)      14.3 ms          0.36
AODV    5 m/s     79.4 kbit/s   97.0 % ( 92.9- 99.8)      91.2 ms          0.22
DSR     5 m/s     81.4 kbit/s   99.4 % ( 98.3-100.0)     126.5 ms          0.12
DSDV    5 m/s     45.9 kbit/s   56.1 % ( 42.6- 65.4)      11.7 ms          0.35
AODV   10 m/s     79.4 kbit/s   96.9 % ( 92.8- 99.3)      65.2 ms          0.52
DSR    10 m/s     81.3 kbit/s   99.2 % ( 98.0-100.0)     151.5 ms          0.27
DSDV   10 m/s     38.6 kbit/s   47.1 % ( 20.3- 69.3)      12.7 ms          0.54
AODV   20 m/s     79.3 kbit/s   96.9 % ( 95.9- 97.6)     195.4 ms          0.86
DSR    20 m/s     80.5 kbit/s   98.3 % ( 96.3- 99.7)     124.7 ms          0.46
DSDV   20 m/s     31.2 kbit/s   38.1 % ( 35.6- 42.4)      10.4 ms          0.47

Figure 17.1 Delivery ratio and delay against top speed, each point the average of three networks

Step 4: how connected were the networks?

Before comparing protocols, ask what the network allowed. If a flow's two ends are not joined by any chain of links, no routing protocol can deliver its packets at that moment. reach.py reads the node positions from the NAM file, as Practical 11's frames.py does, and checks every half second whether each flow's ends are joined:

# reach.py: for how much of the traffic's time each flow's two ends were joined by a chain
# of links within 250 m. A packet sent while they are apart can still arrive, later, if the
# routing protocol keeps it until they are joined.
import math
import sys

RANGE, START, STOP, STEP = 250.0, 5.0, 95.0, 0.5
FLOWS = [(0, 10), (2, 12), (4, 14), (6, 16), (8, 18)]

start, moves = {}, {}
for line in open(sys.argv[1]):
    if not line.startswith('n -t '):
        continue
    f = line.split()
    o = dict(zip(f[1::2], f[2::2]))
    n = int(o['-s'])
    if o['-t'] == '*':
        start[n] = (float(o['-x']), float(o['-y']))
    else:
        moves.setdefault(n, []).append(tuple(float(o[k]) for k in ('-t', '-x', '-y', '-U', '-V', '-T')))


def position(n, t):
    x, y = start[n]
    for t0, x0, y0, u, v, dur in moves.get(n, []):
        if t0 > t:
            break
        x, y = x0 + u * min(t - t0, dur), y0 + v * min(t - t0, dur)
    return x, y


def reachable(pos, a):
    seen, todo = {a}, [a]
    while todo:
        m = todo.pop()
        for k in pos:
            if k not in seen and math.dist(pos[m], pos[k]) <= RANGE:
                seen.add(k)
                todo.append(k)
    return seen


if len(start) < 2:
    sys.exit('no starting positions in %s: does the script call initial_node_pos?' % sys.argv[1])
steps = int((STOP - START) / STEP)
joined = {fl: 0 for fl in FLOWS}
for i in range(steps):
    t = START + i * STEP
    pos = {n: position(n, t) for n in start}
    for a, b in FLOWS:
        if b in reachable(pos, a):
            joined[(a, b)] += 1
for (a, b), k in joined.items():
    print('flow %d to %2d: ends joined %5.1f %% of the time' % (a, b, 100.0 * k / steps))
print('time connected, all five flows: %.1f %%' % (100.0 * sum(joined.values()) / (steps * len(FLOWS))))

The network whose delivery ratios were lowest at 2 m/s, network 2:

$ ns eval.tcl DSDV 2 2 > /dev/null 2>&1
$ python3 reach.py run.nam
flow 0 to 10: ends joined   0.0 % of the time
flow 2 to 12: ends joined 100.0 % of the time
flow 4 to 14: ends joined 100.0 % of the time
flow 6 to 16: ends joined 100.0 % of the time
flow 8 to 18: ends joined 100.0 % of the time
time connected, all five flows: 80.0 %

And all twelve networks, one line each. The protocol does not matter here, because the movement is the same whichever protocol runs:

# connected.sh: how connected each of the twelve networks was
for v in 2 5 10 20; do
    for s in 1 2 3; do
        ns eval.tcl DSDV $v $s > /dev/null 2>&1
        echo "$v m/s, network $s: $(python3 reach.py run.nam | tail -1)"
    done
done

$ bash connected.sh
2 m/s, network 1: time connected, all five flows: 100.0 %
2 m/s, network 2: time connected, all five flows: 80.0 %
2 m/s, network 3: time connected, all five flows: 96.0 %
5 m/s, network 1: time connected, all five flows: 100.0 %
5 m/s, network 2: time connected, all five flows: 95.9 %
5 m/s, network 3: time connected, all five flows: 100.0 %
10 m/s, network 1: time connected, all five flows: 95.9 %
10 m/s, network 2: time connected, all five flows: 100.0 %
10 m/s, network 3: time connected, all five flows: 100.0 %
20 m/s, network 1: time connected, all five flows: 98.6 %
20 m/s, network 2: time connected, all five flows: 100.0 %
20 m/s, network 3: time connected, all five flows: 96.6 %

What the connectivity explains. At 2 m/s, network 2 kept nodes 0 and 10 apart for the whole run: no chain of links ever joined them, so no protocol could deliver a single packet of that flow, and 80 per cent was the most anyone could deliver on that network. AODV delivered 79.8 per cent there and DSR 79.9. Averaged, the three networks at 2 m/s were connected for (100 + 80.0 + 96.0) / 3 = 92.0 per cent of the time, against about 98.5 per cent at every other speed. Slow nodes stay near where they started, and a pair that starts apart stays apart; faster nodes mix. That, not the routing, is why AODV and DSR delivered less at 2 m/s than at 5.

The time connected is not a strict limit. On network 3 at 2 m/s the flows were joined 96.0 per cent of the time, and DSR delivered 99.1 per cent: it keeps a packet for up to 30 s (Practical 13), and a packet sent while its ends were apart arrived after they met.

Step 5: why each protocol lost what it lost

The trace gives every lost packet a reason. The three most common, for each protocol on network 1 at 10 m/s:

# losses.sh: the three commonest reasons each protocol lost packets, on network 1 at 10 m/s
for p in AODV DSR DSDV; do
    ns eval.tcl $p 10 1 > /dev/null 2>&1
    echo "$p: $(awk '$1 == "D" && $7 == "cbr" {print $4 "/" $5}' run.tr | sort | uniq -c | sort -rn | head -3 | xargs)"
done

$ bash losses.sh
AODV: 68 RTR/CBK 59 RTR/NRTE 3 IFQ/ARP
DSR: 17 RTR/TOUT 17 IFQ/ARP 3 RTR/NRTE
DSDV: 770 RTR/CBK 402 RTR/IFQ 257 IFQ/ARP

AODV lost packets in flight when links broke (CBK) and packets it had held when a search gave up (NRTE): the two mechanisms of Practical 12.

DSR lost few, and two kinds: packets that waited longer than its send buffer's 30 s (TOUT, "packet expired"), and packets for a next hop that had moved away before its address could be resolved (ARP).

DSDV lost many more, and its own code says why:

1. It is not told when a link breaks. ns-2 sets Agent/DSDV set use_mac_ 0. When the MAC reports that a packet could not reach the next hop, DSDV drops the packet (CBK) and leaves the route in its table (dsdv.cc, line 348), so the next packets for that destination go the same dead way until a routing update replaces it. That is the 770.
2. With no valid route, it keeps only five packets. DSDV holds up to MAX_QUEUE_LENGTH, 5, packets per destination while it has no route, and throws away the oldest beyond that (dsdv.h, line 64; dsdv.cc, line 936): the 402 IFQ drops. A flow of four packets a second fills five places in just over a second.
3. Its routes change slowly. A node sends its whole table every 11.25 to 15 s (perup_, 15 s, jittered), and holds back an improved route for twice its settling time, 12 s at first, before advertising it (dsdv.cc, line 703), so that a route that is about to change again is not advertised. In a network whose links change every few seconds, much of the table is out of date much of the time.

The delay figures follow from the same code. DSDV never waits for a route: a packet either goes at once or is dropped, so the packets that arrive are fast, 10 to 14 ms. AODV and DSR hold packets while they search, so their averages include packets that waited seconds; a few long waits move the average a lot, which is why it jumps between speeds.

Procedure

1. Write eval.tcl: twenty nodes, random waypoint from seeded generators, five CBR flows, and the protocol, top speed and network taken from the command line.
2. Reduce one run to one line of measures with one.awk, and check it on one run.
3. Run all three protocols at four top speeds on three networks each, 36 runs, into results.txt.
4. Average the three networks at each point with summary.awk, with the range of the delivery ratio.
5. Measure how long each flow's two ends were connected in every network with reach.py.
6. Explain the differences: the drop reasons of each protocol, from the trace and the protocols' code.

Observations

Result

AODV, DSR and DSDV were each run on the same twelve random networks, three at each of four top speeds, with five CBR flows offering 81.9 kbit/s. The two on-demand protocols delivered 91.5 to 99.4 per cent of the data on average, DSR a little more than AODV at every speed and at a lower routing load; DSDV delivered 38.1 to 56.9 per cent, less as the nodes moved faster. Throughput followed the delivery ratio, as it must when the offered load is fixed. DSDV had the lowest average delay, 10 to 14 ms, because it drops packets it cannot route at once, while AODV and DSR averaged 65 to 195 ms including packets that waited for a route. The lower delivery of every protocol at 2 m/s was the networks': one of them kept a flow's two ends apart for the whole run. DSDV's losses were traced to three things in ns-2's implementation: it ignores link failures reported by the MAC (use_mac_ 0), holds only five packets for a destination without a route, and advertises changed routes slowly.

Where marks are lost

Comparing protocols on different networks. Each protocol must see the same positions, movements and traffic. Three runs of setdest give three different networks; a seeded generator, or one saved setdest file, gives the same one.

One run per point. At 10 m/s DSDV delivered 20.3 per cent on one network and 69.3 on another. A single run can be the unusual one; report the average and the spread.

Reporting delay without delivery. DSDV's delay is the best because it delivers the fewest packets and drops the rest at once. Delay is averaged over delivered packets only; always give the delivery ratio beside it.

Treating throughput and delivery ratio as two findings. With a fixed offered load, throughput is the delivery ratio times that load. They are one finding.

Blaming a protocol for a partition. When no chain of links joins a flow's ends, no protocol can deliver. Measure the connectivity before comparing.

Counting a delivered packet at the size its trace line shows. Protocols differ in what the size includes on arrival. Count the size the source sent.

Running ns-2.35 on an ARM computer. On some of these networks the packaged ns stops with Floating point exception inside AODV; on Intel and AMD computers it does not. This book's results come from a copy with that one fault corrected, and match an Intel computer's exactly.

For the journal

Write: aim; the three protocols, reactive and proactive, in three lines each; the table of measures with their definitions; eval.tcl and how its seeded random waypoint works; one.awk and summary.awk; the 36-run loop and the summary; the figure, drawn by hand from the summary if you have no plotting program; the connectivity of each network from reach.py, and what it explains; the drop reasons of each protocol, with DSDV's three causes; observations; result.

Quick revision

• Reactive (on-demand): AODV, DSR. Proactive (table-driven): DSDV.
• Throughput = data bits delivered per second; packet delivery ratio = delivered ÷ sent; average end-to-end delay = mean (received - sent) over delivered packets.
• Offered load here: 5 × 512 × 8 × 4 = 81920 bit/s; throughput follows the delivery ratio.
• Same networks for every protocol; several networks per point; report average and spread.
• ns-2's RNG with a fixed seed repeats exactly; setdest does not.
• Check connectivity: a partition defeats every protocol.
• AODV and DSR: 91.5 to 99.4 per cent delivered; DSDV: 38.1 to 56.9, falling with speed.
• DSDV in ns-2: use_mac_ 0 (link failures ignored), 5 packets held per destination, updates every 11.25 to 15 s, changed routes held back.
• Delay: DSDV lowest (no waiting); AODV and DSR higher (packets wait for route discovery).
• Routing load rises with speed for AODV and DSR: more breaks, more searches.

Questions you must be able to answer

1. Define throughput, packet delivery ratio and average end-to-end delay. Throughput is the number of data bits delivered to the destinations per second. The packet delivery ratio is the number of data packets delivered divided by the number sent. The average end-to-end delay is the mean, over the delivered packets, of the time each took from being sent by the source's application to being received by the destination's.

2. Why can a protocol with the lowest delay be the worst protocol? Because delay is averaged only over the packets that arrive. DSDV sends a packet at once or drops it, so the few that arrive are fast, while it loses half of them. The delivery ratio must always be read beside the delay.

3. Why must every protocol be run on the same networks? Because the network itself, where the nodes are and how they move, changes the results as much as the protocol does. Only if everything else is the same can a difference be put down to the protocol.

4. Why three networks at each speed, not one? Because one random network can be unusual. At 2 m/s one network kept a flow's two ends apart for the whole run, and on its own it would have made every protocol look poor at low speed.

5. What does eval.tcl do that the setdest generator does not? It generates the random waypoint movement from ns-2's random number generator with a fixed seed, so the same seed gives exactly the same network on every run and for every protocol. setdest seeds itself from the clock and writes a different file every time.

6. Why did AODV and DSR deliver less at 2 m/s than at 5 m/s? Because the 2 m/s networks were less connected, 92.0 per cent of the time on average against about 98.5 per cent at the other speeds. In one of them nodes 0 and 10 were never joined, and slow nodes do not move far enough to meet.

7. Give three reasons, from its code, why ns-2's DSDV delivered so little. It ignores link failures reported by the MAC (use_mac_ 0), so it keeps sending into broken links; with no valid route it keeps only five packets per destination and drops the rest; and it sends full updates only every 11.25 to 15 s and holds back changed routes for twice their settling time, so its table is often out of date.

8. Why does the routing load of AODV and DSR rise with speed? Faster nodes break more links, and every break costs route errors and new route requests and replies. More routing packets are spent for each data packet delivered.

9. Five flows each send a 512-byte packet four times a second. What is the offered load, and what throughput does 97 per cent delivery give? 5 × 512 × 8 × 4 = 81920 bits a second, 81.9 kbit/s. Delivering 97 per cent of it is about 79.5 kbit/s.

10. On this evidence, is a reactive or a proactive protocol better for a MANET whose nodes keep moving? For these networks, the reactive protocols: they delivered 91.5 to 99.4 per cent against DSDV's 38.1 to 56.9, and DSDV fell further as speed rose. The evidence is ns-2's implementations with their default settings, on twenty nodes and five flows.

11. What does reach.py measure, and why is it not a strict upper limit on delivery? For how much of the time each flow's two ends were joined by some chain of links within 250 m. It is not a strict limit because a protocol that keeps packets, like DSR, can deliver a packet sent while the ends were apart once they are joined again.

12. What would make this evaluation stronger? More networks at each point, with the spread reported as a confidence interval; more nodes, flows and speeds; longer runs; and other kinds of traffic, such as TCP.