Practical 12: The AODV Routing Protocol

Step 1: the network

The network of Practical 11, with two more moves at the end so that one link breaks next to the destination. aodv.tcl:

# aodv.tcl: Practical 11's MANET, run on for a break next to the destination
set val(chan)   Channel/WirelessChannel
set val(prop)   Propagation/TwoRayGround
set val(netif)  Phy/WirelessPhy
set val(mac)    Mac/802_11
set val(ifq)    Queue/DropTail/PriQueue
set val(ll)     LL
set val(ant)    Antenna/OmniAntenna
set val(ifqlen) 50
set val(nn)     6
set val(rp)     AODV
set val(x)      800
set val(y)      600
set val(stop)   60.0

set ns [new Simulator]
set tf [open aodv.tr w]
$ns trace-all $tf
set nf [open aodv.nam w]
$ns namtrace-all-wireless $nf $val(x) $val(y)

set topo [new Topography]
$topo load_flatgrid $val(x) $val(y)
create-god $val(nn)

$ns node-config -adhocRouting $val(rp) -llType $val(ll) -macType $val(mac) \
    -ifqType $val(ifq) -ifqLen $val(ifqlen) -antType $val(ant) \
    -propType $val(prop) -phyType $val(netif) -channel [new $val(chan)] \
    -topoInstance $topo -agentTrace ON -routerTrace ON -macTrace OFF \
    -movementTrace ON

# where each node starts: x y
set start {
    {50 300}
    {250 300}
    {450 300}
    {250 560}
    {450 560}
    {650 300}
}
for {set i 0} {$i < $val(nn)} {incr i} {
    set node($i) [$ns node]
    $node($i) random-motion 0
    $node($i) set X_ [lindex $start $i 0]
    $node($i) set Y_ [lindex $start $i 1]
    $node($i) set Z_ 0
    $ns initial_node_pos $node($i) 30
}

# how the topology changes: at time t, node n heads for (x, y) at speed m/s
$ns at 10.0 "$node(2) setdest 450 40 20"
$ns at 20.0 "$node(4) setdest 450 300 20"
$ns at 30.0 "$node(1) setdest 250 40 20"
$ns at 30.0 "$node(3) setdest 250 300 20"
$ns at 40.0 "$node(2) setdest 550 150 20"
$ns at 44.0 "$node(4) setdest 380 300 10"

set udp [new Agent/UDP]
$ns attach-agent $node(0) $udp
set sink [new Agent/Null]
$ns attach-agent $node(5) $sink
$ns connect $udp $sink
set cbr [new Application/Traffic/CBR]
$cbr set packetSize_ 512
$cbr set interval_ 0.25
$cbr attach-agent $udp
$ns at 1.0 "$cbr start"
$ns at 59.0 "$cbr stop"

for {set i 0} {$i < $val(nn)} {incr i} {
    $ns at $val(stop) "$node($i) reset"
}
$ns at $val(stop) "finish"
proc finish {} {
    global ns tf nf
    $ns flush-trace
    close $tf
    close $nf
    exit 0
}
$ns run

So one run shows AODV finding a route, losing it to a break in the middle, finding none, finding one again, losing it to a break at the source, and repairing a break next to the destination.

Step 2: run it, and list every control packet

$ ns aodv.tcl
num_nodes is set 6
INITIALIZE THE LIST xListHead
channel.cc:sendUp - Calc highestAntennaZ_ and distCST_
highestAntennaZ_ = 1.5,  distCST_ = 550.0
SORTING LISTS ...DONE!

Everything AODV did is in its control packets. control.awk prints each one that a node sent or forwarded, with its fields named:

# control.awk: every AODV control packet sent or forwarded, with its fields named
function node(f) { return substr(f, 2, length(f) - 2) }
function inner(f) { gsub(/[][]/, "", f); return f }
$4 == "RTR" && $7 == "AODV" && ($1 == "s" || $1 == "f") {
    if ($NF == "(REQUEST)")
        printf "%10.6f  node %s  REQUEST  TTL %-2s  hops %s  id %s  for %s (seq %s)  from %s (seq %s)\n",
            $2, node($3), $16, $19, $20, inner($21), inner($22), inner($23), inner($24)
    else if ($NF == "(REPLY)")
        printf "%10.6f  node %s  REPLY    to %s  hops %s  route to %s (seq %s)\n",
            $2, node($3), inner($17), $19, inner($20), inner($21)
    else if ($NF == "(ERROR)")
        printf "%10.6f  node %s  ERROR    to all neighbours: %s unreachable\n", $2, node($3), inner($20)
}

The field numbers come from Chapter 13's decoding of the wireless trace. In a request, [0x2 1 1 [5 0] [0 4]] is the type (2, a request), the hop count so far, the request's id, then the destination with the newest sequence number the sender knows for it, then the source with its own sequence number. In a reply, [0x4 1 [5 4] 10.000000] is the type (4), the hop count, the destination with its sequence number, and the route's lifetime in seconds.

$ awk -f control.awk aodv.tr
  1.000000  node 0  REQUEST  TTL 30  hops 1  id 1  for 5 (seq 0)  from 0 (seq 4)
  1.001551  node 1  REQUEST  TTL 29  hops 2  id 1  for 5 (seq 0)  from 0 (seq 4)
  1.010791  node 2  REQUEST  TTL 28  hops 3  id 1  for 5 (seq 0)  from 0 (seq 4)
  1.011900  node 5  REPLY    to 2  hops 1  route to 5 (seq 4)
  1.016547  node 2  REPLY    to 1  hops 2  route to 5 (seq 4)
  1.021579  node 1  REPLY    to 0  hops 3  route to 5 (seq 4)
 17.546547  node 1  ERROR    to all neighbours: 5 unreachable
 17.750000  node 0  REQUEST  TTL 5   hops 1  id 2  for 5 (seq 5)  from 0 (seq 6)
 17.752923  node 1  REQUEST  TTL 4   hops 2  id 2  for 5 (seq 5)  from 0 (seq 6)
 18.000000  node 0  REQUEST  TTL 7   hops 1  id 3  for 5 (seq 5)  from 0 (seq 8)
 18.005354  node 1  REQUEST  TTL 6   hops 2  id 3  for 5 (seq 5)  from 0 (seq 8)
 18.250000  node 0  REQUEST  TTL 30  hops 1  id 4  for 5 (seq 5)  from 0 (seq 10)
 18.260515  node 1  REQUEST  TTL 29  hops 2  id 4  for 5 (seq 5)  from 0 (seq 10)
 19.000000  node 0  REQUEST  TTL 30  hops 1  id 5  for 5 (seq 5)  from 0 (seq 12)
 19.006283  node 1  REQUEST  TTL 29  hops 2  id 5  for 5 (seq 5)  from 0 (seq 12)
 20.250000  node 0  REQUEST  TTL 30  hops 1  id 6  for 5 (seq 5)  from 0 (seq 14)
 20.259229  node 1  REQUEST  TTL 29  hops 2  id 6  for 5 (seq 5)  from 0 (seq 14)
 22.000000  node 0  REQUEST  TTL 30  hops 1  id 7  for 5 (seq 5)  from 0 (seq 16)
 22.002802  node 1  REQUEST  TTL 29  hops 2  id 7  for 5 (seq 5)  from 0 (seq 16)
 34.250000  node 0  REQUEST  TTL 30  hops 1  id 8  for 5 (seq 5)  from 0 (seq 18)
 34.255385  node 1  REQUEST  TTL 29  hops 2  id 8  for 5 (seq 5)  from 0 (seq 18)
 34.258353  node 4  REQUEST  TTL 28  hops 3  id 8  for 5 (seq 5)  from 0 (seq 18)
 34.259781  node 5  REPLY    to 4  hops 1  route to 5 (seq 6)
 34.265449  node 4  REPLY    to 1  hops 2  route to 5 (seq 6)
 34.270701  node 1  REPLY    to 0  hops 3  route to 5 (seq 6)
 37.538287  node 0  ERROR    to all neighbours: 5 unreachable
 37.750000  node 0  REQUEST  TTL 5   hops 1  id 9  for 5 (seq 7)  from 0 (seq 22)
 37.756271  node 3  REQUEST  TTL 4   hops 2  id 9  for 5 (seq 7)  from 0 (seq 22)
 37.759735  node 4  REQUEST  TTL 3   hops 3  id 9  for 5 (seq 7)  from 0 (seq 22)
 37.761103  node 5  REPLY    to 4  hops 1  route to 5 (seq 8)
 37.762837  node 4  REPLY    to 3  hops 2  route to 5 (seq 8)
 37.767870  node 3  REPLY    to 0  hops 3  route to 5 (seq 8)
 49.047548  node 4  REQUEST  TTL 30  hops 1  id 1  for 5 (seq 8)  from 4 (seq 4)
 49.048817  node 3  REPLY    to 4  hops 3  route to 5 (seq 8)
 49.057633  node 2  REQUEST  TTL 29  hops 2  id 1  for 5 (seq 8)  from 4 (seq 4)
 49.058662  node 5  REPLY    to 2  hops 1  route to 5 (seq 10)
 49.060575  node 2  REPLY    to 4  hops 2  route to 5 (seq 10)

Thirty-seven packets in sixty seconds, in five groups. The rest of the practical reads them one group at a time.

Step 3: route discovery

At 1.0 s node 0 has a packet for node 5 and no route. The first six lines are the discovery.

The request floods outwards. Node 0 broadcasts a request with hop count 1 and id 1. Node 1 hears it, and rebroadcasts it with hop count 2 and a TTL one lower; node 2 does the same with hop count 3. Nodes 3 and 4 are out of range and never hear it. Node 0 hears node 1's rebroadcast of its own request, and node 1 hears node 2's; each discards it without a trace line (AODV::recvRequest frees its own requests and any it has seen before). A node passes on each request, identified by its source and id, once.

Why TTL 30, when TTL_START is 5? AODV::sendRequest chooses the TTL from the largest of the last TTL it used and the route's last known hop count. For a destination it has never had a route to, the hop count is still its starting value, 255, "unknown" (aodv_rtable.cc, line 47), which is above TTL_THRESHOLD, so the very first request of all goes to the whole network. The expanding ring is used only when a hop count is known, after a route breaks (step 5).

The destination answers, and raises its sequence number. Node 5 replies with sequence number 4. The request carried 0 for node 5, meaning "I know nothing"; the rule in recvRequest sets the reply's number to one more than the larger of the two, rounded up to an even number: node 5's own 2 and the request's 0 give 3, and 3 rounds up to 4. The reply goes back along the path the request came by, node 2, then node 1, then node 0, its hop count rising from 1 to 3.

Each node learns a route from each message it accepts. A request teaches the route back to its source; a reply teaches the route forward to the destination. table.awk rebuilds what each node learnt, by AODV's own acceptance rule, from the trace:

# table.awk: the routes each node accepts from the requests and replies it hears, by AODV's
# own rule: a newer destination sequence number, or the same one with fewer hops.
# Every line of the trace is read; only those from time `from` to `to` are printed.
#   awk -v from=T1 -v to=T2 -f table.awk trace
function node(f) { return substr(f, 2, length(f) - 2) }
function inner(f) { gsub(/[][]/, "", f); return f }
function offer(me, dst, via, h, s, how,    k, note) {
    k = me SUBSEP dst; h += 0; s += 0
    if (!(k in seq) || seq[k] < s || (seq[k] == s && hops[k] > h)) {
        seq[k] = s; hops[k] = h; verb = "accepts"; note = how
    } else {
        verb = "ignores"; note = sprintf("%s; it has seq %d, %d hops", how, seq[k], hops[k])
    }
    if ($2 >= from && $2 < to)
        printf "%10.6f  node %s  %s  route to %s via %s, %d hops, seq %d   (%s)\n", $2, me, verb, dst, via, h, s, note
}
$1 == "r" && $4 == "RTR" && $7 == "AODV" {
    me = node($3); prev = $11
    if ($NF == "(REQUEST)") {
        src = inner($23); id = $20
        if (src == me || (me, src, id) in heard) next    # its own request, or a copy already heard
        heard[me, src, id] = 1
        offer(me, src, prev, $19, inner($24), "reverse, from a request")
    } else if ($NF == "(REPLY)")
        offer(me, inner($20), prev, $19, inner($21), "forward, from a reply")
}

The previous hop, "via", is the MAC transmitter address, field 11 of the trace line (Chapter 13, step 6).

$ awk -v from=1 -v to=2 -f table.awk aodv.tr
  1.001409  node 1  accepts  route to 0 via 0, 1 hops, seq 4   (reverse, from a request)
  1.002799  node 2  accepts  route to 0 via 1, 2 hops, seq 4   (reverse, from a request)
  1.011900  node 5  accepts  route to 0 via 2, 3 hops, seq 4   (reverse, from a request)
  1.016547  node 2  accepts  route to 5 via 5, 1 hops, seq 4   (forward, from a reply)
  1.021579  node 1  accepts  route to 5 via 2, 2 hops, seq 4   (forward, from a reply)
  1.026631  node 0  accepts  route to 5 via 1, 3 hops, seq 4   (forward, from a reply)

When node 0 accepts its route to 5, 3 hops via node 1, the discovery is over, and the packet that waited for it goes. From request to route took 26.6 ms, a little under 9 ms a hop; AODV remembers that figure and uses it in step 5.

Step 4: a link breaks in the middle

At 17.5 s node 2 moves out of range of nodes 1 and 5. Nothing announces it: ns-2's AODV sends no HELLOs. The break is found when node 1 tries to pass on the next data packet. The 802.11 MAC tries to send it, hears no answer from node 2, retries, gives up about 41 ms later, and tells AODV through a callback that the link has failed: the packet is dropped with the reason CBK.

AODV::rt_ll_failed then decides between two responses. If the packet has already travelled further than the remaining distance to its destination, it tries to repair the route on the spot; otherwise it gives the route up. At node 1 the packet had come one hop and had two to go, so it gave up: it raised its sequence number for node 5 from 4 to 5, marked the route down, and broadcast a route ERROR to its neighbours, TTL 1. Node 0, hearing it, marks its own route to 5 down too.

The ERROR line needs care. ns-2 prints an error through the layout of a reply, so in [0x8 1 [5 0] 0.000000] only the first three numbers mean anything: type 8, one unreachable destination, and that destination, node 5. The 0 and 0.000000 are the reply layout reading parts of the error packet that hold nothing.

Step 5: searching again, and giving up

Node 0's next data packet, at 17.75 s, has no route, so AODV asks again, and the next nine request lines are that search. It is not repeated blindly; each request follows from the one before by rules in AODV::sendRequest:

1. The expanding ring. The route's last hop count is now known, 3, so the first request goes only 3 + 2 = 5 hops. If nothing answers, the next goes 5 + 2 = 7. At TTL_THRESHOLD, 7, the next goes to the whole network, TTL 30.
2. Each request waits for 2 × TTL × the time a hop takes, measured in the last discovery, and each network-wide request waits that times the number of network-wide requests so far.
3. Requests are triggered by data. AODV asks when it has a packet to route and its wait is over, so requests fall on the data packets' quarter seconds.
4. When it has sent more network-wide requests than RREQ_RETRIES, 3, without an answer, it gives up: it drops every packet it was holding for the destination, reason NRTE, no route, and asks nothing more for MAX_RREQ_TIMEOUT, 10 s.

schedule.py applies these rules, and only these, to predict the search:

# schedule.py: when AODV at node 0 asks again for a route after a break, by its own rules
# (aodv/aodv.cc, AODV::sendRequest; the constants are aodv/aodv.h's)
import sys

TTL_START, TTL_INCREMENT, TTL_THRESHOLD, NETWORK_DIAMETER = 5, 2, 7, 30
RREQ_RETRIES, MAX_RREQ_TIMEOUT = 3, 10.0
INTERVAL = 0.25                     # a new data packet every quarter second


def first_discovery(trace):
    """Node 0's first request and the reply that answered it."""
    sent = None
    for line in open(trace):
        f = line.split()
        if len(f) < 8 or f[6] != 'AODV' or f[2] != '_0_':
            continue
        if sent is None and f[0] == 's' and f[-1] == '(REQUEST)':
            sent = float(f[1])
        elif sent is not None and f[0] == 'r' and f[-1] == '(REPLY)':
            return sent, float(f[1]), int(f[18])


sent, got, hops = first_discovery(sys.argv[1])
per_hop = (got - sent) / hops
print('first discovery: asked at %.6f s, answered at %.6f s, %d hops: %.6f s a hop'
      % (sent, got, hops, per_hop))

last_ttl = last_hops = hops         # what the route remembers once it breaks
count, not_before = 0, 0.0
t, stop = float(sys.argv[2]), float(sys.argv[3])
while t <= stop:
    if t >= not_before:
        if count > RREQ_RETRIES:
            count, not_before = 0, t + MAX_RREQ_TIMEOUT
            print('%6.2f s  gives up: every waiting packet dropped, no request before %.2f s'
                  % (t, not_before))
        else:
            m = max(last_ttl, last_hops)
            if m == 0:
                ttl = TTL_START
            elif m < TTL_THRESHOLD:
                ttl = m + TTL_INCREMENT
            else:
                ttl = NETWORK_DIAMETER
                count += 1
            last_ttl = ttl
            wait = min(2 * ttl * per_hop * max(count, 1), MAX_RREQ_TIMEOUT)
            not_before = t + wait
            print('%6.2f s  request, TTL %2d; no other before %.3f s' % (t, ttl, not_before))
    t = round(t + INTERVAL, 2)

$ python3 schedule.py aodv.tr 17.75 34.25
first discovery: asked at 1.000000 s, answered at 1.026631 s, 3 hops: 0.008877 s a hop
 17.75 s  request, TTL  5; no other before 17.839 s
 18.00 s  request, TTL  7; no other before 18.124 s
 18.25 s  request, TTL 30; no other before 18.783 s
 19.00 s  request, TTL 30; no other before 20.065 s
 20.25 s  request, TTL 30; no other before 21.848 s
 22.00 s  request, TTL 30; no other before 24.130 s
 24.25 s  gives up: every waiting packet dropped, no request before 34.25 s
 34.25 s  request, TTL 30; no other before 34.783 s

Set it against node 0's requests in the trace:

$ awk -f control.awk aodv.tr | awk '$3 == 0 && $4 == "REQUEST"'
  1.000000  node 0  REQUEST  TTL 30  hops 1  id 1  for 5 (seq 0)  from 0 (seq 4)
 17.750000  node 0  REQUEST  TTL 5   hops 1  id 2  for 5 (seq 5)  from 0 (seq 6)
 18.000000  node 0  REQUEST  TTL 7   hops 1  id 3  for 5 (seq 5)  from 0 (seq 8)
 18.250000  node 0  REQUEST  TTL 30  hops 1  id 4  for 5 (seq 5)  from 0 (seq 10)
 19.000000  node 0  REQUEST  TTL 30  hops 1  id 5  for 5 (seq 5)  from 0 (seq 12)
 20.250000  node 0  REQUEST  TTL 30  hops 1  id 6  for 5 (seq 5)  from 0 (seq 14)
 22.000000  node 0  REQUEST  TTL 30  hops 1  id 7  for 5 (seq 5)  from 0 (seq 16)
 34.250000  node 0  REQUEST  TTL 30  hops 1  id 8  for 5 (seq 5)  from 0 (seq 18)
 37.750000  node 0  REQUEST  TTL 5   hops 1  id 9  for 5 (seq 7)  from 0 (seq 22)

Every request after the break is where the rules put it, with the TTL they give: 5, 7, then 30 four times at widening intervals, then nothing for ten seconds. The network was partitioned from 17.5 to 25.5 s, so every one of the search's requests went unanswered, and at 24.25 s the source dropped the 27 packets it had been holding. The route through node 4 existed from 25.5 s, but AODV was in its ten-second hold-down; its next request, at 34.25 s, found the route at once, and the packets that had waited since 24.5 s were delivered. The request at 34.25 s is network-wide because the last TTL used was 30.

Step 6: a link breaks at the source

At 37.5 s the link from node 0 to node 1 breaks. This time node 0 itself finds out, when its own packet fails (CBK). It is the source, so the packet has travelled no distance at all: no repair. Node 0 broadcasts an ERROR, and at its next data packet, 37.75 s, searches again. The last discovery ended with a 3-hop route, so the ring starts at 3 + 2 = 5, and it is enough: nodes 3 and 4 pass the request on, node 5 replies with sequence number 8, and 23 ms after the request node 0 has the route 0-3-4-5. One packet was lost to this break, the one in flight.

Step 7: local repair next to the destination

At 49 s node 4, backing away, loses node 5. The packet that finds the break has come two hops, 0 to 3 to 4, and has one to go, so this time rt_ll_failed repairs: node 4 keeps the packet, sends no ERROR, and asks for a route to 5 itself. Its request goes network-wide, TTL 30: node 4 never had its route to 5 break before, so its last hop count is still "unknown", 255.

Two answers come back, and they show what sequence numbers are for.

$ awk -v from=49 -v to=50 -f table.awk aodv.tr
 49.048817  node 3  accepts  route to 4 via 4, 1 hops, seq 4   (reverse, from a request)
 49.048817  node 2  accepts  route to 4 via 4, 1 hops, seq 4   (reverse, from a request)
 49.054237  node 4  ignores  route to 5 via 3, 3 hops, seq 8   (forward, from a reply; it has seq 8, 1 hops)
 49.058662  node 5  accepts  route to 4 via 2, 2 hops, seq 4   (reverse, from a request)
 49.060575  node 2  accepts  route to 5 via 5, 1 hops, seq 10   (forward, from a reply)
 49.065787  node 4  accepts  route to 5 via 2, 2 hops, seq 10   (forward, from a reply)

Node 3 answers first, with a stale route. Node 3's route to node 5 runs through node 4, the node that is asking; accepting it would send packets in a circle. Node 3 is allowed to answer, because its route is as fresh as the request asks, sequence number 8. But node 4 already has number 8 for node 5, with 1 hop, and a route with the same number and 3 hops is not better. Node 4 ignores it.

Node 5 answers through node 2, with a new number. Node 5 raises its sequence number to 10 in the reply, newer than anything anyone had, and every node on the way accepts it. Node 4's new route is 2 hops, via node 2, and the held packet goes that way. Nothing was lost: the route is now 0-3-4-2-5.

Step 8: what it cost, and what it delivered

route.awk, from Practical 11, groups the data packets by the route each took:

# route.awk: the route every data packet took, grouped into runs of packets that went the same way
$7 == "cbr" && $1 == "s" && $4 == "AGT" { t[$6] = $2; path[$6] = "0"; ids[++n] = $6 }
$7 == "cbr" && $1 == "f" && $4 == "RTR" { path[$6] = path[$6] "-" substr($3, 2, length($3) - 2) }
$7 == "cbr" && $1 == "r" && $4 == "AGT" { got[$6] = 1; path[$6] = path[$6] "-5" }
$7 == "cbr" && $1 == "D" { why[$6] = $5 }
END {
    for (i = 1; i <= n; i++) {
        id = ids[i]
        how = (id in got) ? "delivered via " path[id] : "LOST (" why[id] ") at node " substr(path[id], length(path[id]))
        if (how != last) {
            if (i > 1) printf "%6.2f to %6.2f s  %3d packets  %s\n", first, t[ids[i - 1]], count, last
            first = t[id]; count = 0; last = how
        }
        count++
    }
    printf "%6.2f to %6.2f s  %3d packets  %s\n", first, t[ids[n]], count, last
}

$ awk -f route.awk aodv.tr
  1.00 to  17.25 s   66 packets  delivered via 0-1-2-5
 17.50 to  17.50 s    1 packets  LOST (CBK) at node 1
 17.75 to  24.25 s   27 packets  LOST (NRTE) at node 0
 24.50 to  37.25 s   52 packets  delivered via 0-1-4-5
 37.50 to  37.50 s    1 packets  LOST (CBK) at node 0
 37.75 to  48.75 s   45 packets  delivered via 0-3-4-5
 49.00 to  49.00 s    1 packets  delivered via 0-3-4-4-2-5
 49.25 to  58.75 s   39 packets  delivered via 0-3-4-2-5

The packet sent at 49.00 s is the one node 4 held during the repair: it appears as forwarded by node 4 twice, once into the broken link and once, after the repair, to node 2.

The control traffic, counted by type:

$ awk -f control.awk aodv.tr | awk '{print $4}' | sort | uniq -c
      2 ERROR
     12 REPLY
     23 REQUEST

Procedure

1. Write aodv.tcl: Practical 11's six nodes, AODV, one CBR flow, and six scripted moves.
2. Run it and list every AODV control packet with control.awk.
3. Read the first discovery: the request's flood, the destination's reply, and the routes each node learnt (table.awk).
4. Find the first link break: the CBK drop, the route ERROR, and why no repair was tried.
5. Predict the search that follows with schedule.py, and compare it with the trace.
6. Read the break at the source and the search that followed it.
7. Read the local repair: the request, the stale reply ignored, and the fresh one accepted.
8. Group the data packets by route with route.awk, and count the control packets by type.

Observations

Result

AODV was simulated in NS-2 on a six-node MANET whose links broke and formed on a known schedule, and every one of its 37 control packets was read. Route discovery flooded a request, network-wide the first time, and brought back a reply from the destination with a raised sequence number; every node on the path learnt a reverse route from the request and a forward route from the reply. Route maintenance showed three responses to a broken link: a route ERROR when the break was nearer the source (17.5 s and 37.5 s), and a local repair, with no error, when it was next to the destination (49 s). After the first break the source's search followed AODV's rules exactly, as predicted by a program applying them: an expanding ring of TTL 5 and 7, four network-wide requests at growing intervals, then a give-up that dropped 27 packets and a ten-second hold-down. In the local repair, a stale reply that would have led back through the repairing node was ignored because its sequence number was no newer, and the destination's fresh reply was accepted. 203 of 232 data packets were delivered, 87.5 per cent.

Where marks are lost

Saying that ns-2's AODV sends HELLO messages. It does not. It learns of a broken link from its MAC, when a packet cannot be delivered: the CBK drop.

Reading the ERROR line like a reply. Only the type, the count and the unreachable destination mean anything. The 0 and 0.000000 after them are the reply layout reading an error packet.

Expecting the first request to use TTL_START. In ns-2 a destination never reached before has hop count 255, "unknown", so the first request goes to the whole network. The expanding ring starts only after a route breaks.

Counting every REQUEST line as a new search. A request passed on by other nodes keeps its source and id. Node 0's search after the break is six requests, not twelve lines.

Saying AODV moves to a better route. It does not look for one while its route works. It replaces a route only when the route breaks.

Confusing when a packet was dropped with when it was sent. The 27 NRTE drops all happen at 24.25 s, for packets sent from 17.75 s on. Group losses by the time the packet was sent.

Quoting RFC 3561's constants for an ns-2 run. ns-2.35 uses its own: TTL_START 5 against 1, a network diameter of 30 against 35, three retries against two.

For the journal

Write: aim; what AODV is, in five lines; the table of its four messages; the table of constants, RFC against ns-2; aodv.tcl and its moves; the list of control packets; the first discovery read line by line, with the routes from table.awk; the first break and its ERROR; schedule.py's prediction set against the trace, with the rules; the break at the source; the local repair and the ignored reply; the route groups and the control counts; observations; result.

Quick revision

• AODV: on demand (a route only when needed), distance vector (next hop and hop count only).
• Request: type 2, hop count, id, destination with the newest known sequence number, source with its own.
• Reply: type 4, hop count, destination with its sequence number, lifetime.
• A request teaches the route back to its source; a reply teaches the route to the destination.
• Accept a route only if its sequence number is newer, or the same with fewer hops.
• A node passes on a request (source, id) once; its own and repeated ones are discarded.
• ns-2's AODV has no HELLOs: a broken link is reported by the MAC (CBK).
• Break nearer the source: ERROR to the neighbours. Break nearer the destination: local repair, no ERROR.
• Search after a break: TTL last hops + 2, then + 2 again, then 30; waits of 2 × TTL × time per hop, times the number of network-wide tries.
• More than RREQ_RETRIES (3) network-wide tries: drop the waiting packets (NRTE), then 10 s of silence.
• First request to a new destination: network-wide, because the hop count is unknown.

Questions you must be able to answer

1. Why is AODV called on-demand? Because a node looks for a route only when it has a packet for a destination it has no route to. Until then it sends nothing about routes to that destination.

2. What does a route request carry? Its type; the number of hops it has travelled; an id that, with the source's address, identifies it; the destination, with the newest sequence number the source knows for it; and the source, with its own sequence number.

3. How does a node avoid passing on the same request twice? It remembers the source and id of every request it has passed on, and discards any copy it hears again, and any request it sent itself.

4. What does a node learn from a request, and what from a reply? From a request, a route back to the request's source, through the node it heard it from. From a reply, a route to the destination, through the node it heard it from.

5. What is a destination sequence number for? Use the reply node 3 sent at 49 s. It says how fresh a route is, so that no node replaces a route with an older one, which might lead in a circle. Node 3's route to node 5 went through node 4 itself and carried number 8; node 4 already had 8 with 1 hop, so it ignored node 3's route and accepted node 5's reply, which carried 10.

6. How does ns-2's AODV learn that a link has broken? From its MAC: when a packet cannot be delivered to the next hop after the MAC's retries, the MAC reports the failure and the packet is dropped with the reason CBK.

7. When does AODV repair a route locally, and when does it send an ERROR? Give both cases from the run. It repairs when the packet has already come further than the distance left to its destination, and sends an ERROR otherwise. At 17.5 s node 1 had a packet that had come 1 hop with 2 to go: ERROR. At 49 s node 4 had one that had come 2 hops with 1 to go: local repair.

8. Why was node 0's first request sent with TTL 30, but its first request after the break with TTL 5? The first time, its hop count to node 5 was unknown, stored as 255, so the request went to the whole network. After the break it knew the route had been 3 hops, and the expanding ring starts at 3 + 2 = 5.

9. Why did node 0 send no request from 24.25 s to 34.25 s, when a route existed from 25.5 s? Because at 24.25 s it had sent more network-wide requests than RREQ_RETRIES allows without an answer, so it gave up and, in ns-2, waits MAX_RREQ_TIMEOUT, 10 s, before asking again.

10. What happened to the packets node 0 held at 24.25 s, and to those it was given afterwards? The 27 it held were dropped with the reason NRTE, no route. Those sent from 24.50 s on were held again and delivered after the request at 34.25 s found the route through node 4.

11. Which constants decided the timing of the search after the break? TTL_INCREMENT and TTL_THRESHOLD (the ring of 5 and 7), NETWORK_DIAMETER (30), RREQ_RETRIES (3) and MAX_RREQ_TIMEOUT (10 s), with the time per hop measured in the first discovery.

12. Why is the local repair's request at 49 s network-wide? Because ns-2's local repair sends an ordinary request, and node 4's route to node 5 had never broken before, so its last hop count was still unknown, 255.