22 Route maintenance

org.arl.unet.Services.ROUTE_MAINTENANCE

22.1 Overview

Setting up routes by hand (Chapter 21) is practical only for small, well-understood networks. The ROUTE_MAINTENANCE service automatically discovers routes and keeps them up to date as the network changes, populating the routing tables used by the ROUTING service.

When asked to find a route to a destination (using a RouteDiscoveryReq, or the rreq command), the agent floods route discovery probes into the network. Nodes that receive a probe relay it and record the path it took, so that when a probe reaches the destination, the path back to the originator is known. The resulting routes are installed in the routing tables of the participating nodes, and reported as RouteDiscoveryNtf notifications. Because the probes propagate over a lossy, time-varying medium, route discovery is inherently probabilistic — repeating a discovery may find additional or better routes.

The service also supports diagnostics: a RouteTraceReq (the trace command) reports the actual sequence of hops currently used to reach a destination and return, which is useful for verifying that routing is working as intended (Section 22.6). The default route discovery agent is accessed as rdp.

22.2 Messages

Agents providing this service honor the following requests:

RouteDiscoveryReq – initiate route discovery to a node

Field	Type	Default	Remarks
`count`	`int`	`3`	number of route discovery probes to send
`interval`	`float`	`20.0`	interval between probes in seconds
`maxHops`	`int`	`3`	maximum number of hops to search for
`to`	`int`	`-1`	destination node address

RouteTraceReq – trace the current route to a node

Field Type Default Remarks

to int -1 destination node address

Field	Type	Default	Remarks
`to`	`int`	`-1`	destination node address

Both requests are answered with an AGREE once accepted (a REFUSE if invalid, a FAILURE if something goes wrong); the results then arrive asynchronously as the probes propagate:

RouteDiscoveryNtf – discovered route to a node

Field Type Default Remarks

hops int 0

link string

nextHop int -1

reliability boolean true

route int[]

to int 0

Field	Type	Default
`hops`	`int`	`0`
`link`	`string`
`nextHop`	`int`	`-1`
`reliability`	`boolean`	`true`
`route`	`int[]`
`to`	`int`	`0`

RouteTraceNtf – result of a route trace

Field Type Default Remarks

to int -1

trace int[]

Field	Type	Default	Remarks
`to`	`int`	`-1`
`trace`	`int[]`

RouteDiscoveryNtf notifications are published on the agent’s topic — one for each route (or partial route) learned, including routes learned passively from probes relayed on behalf of other nodes — which is how the routing agent hears about and installs discovered routes. A RouteTraceNtf, carrying the list of node addresses traversed out and back, is sent to the agent that requested the trace.

22.3 Parameters

This service defines no parameters.

22.4 Commands

rreq – initiate route discovery

With a single parameter, rreq finds up to 3-hop routes using 3 probes spaced 20 seconds apart.

Examples:
```
rreq 27             // start route discovery to node 27
rreq 27, 3, 2, 10   // find <3-hop route to node 27 with 2 RREQs 10s apart
```

trace – trace route

Example:

trace 27            // trace current route to node 27
trace 27, 10000     // trace current route to node 27 with 10s timeout

22.5 Examples

To discover a route to node 31, issue an rreq from the shell and then inspect the routing table populated by the discovery (see Chapter 6 for the routing table and routes command). Since discovery is probabilistic, the routes found — and their hop counts and metrics — may differ from run to run:

> rreq 31
OK

Once the flooded discovery has completed, node 21’s routing table shows the route(s) found:

> routes
    uuid      to nextHop         link reliability hops dataRate metric enabled  auto  poll
------------------------------------------------------------------------------------------
  vixjss      28      28       uwlink        true    1      965    3.0    true  true   0.0
  2bmfi6      22      22       uwlink        true    1      965    3.0    true  true   0.0
  vw7s68      29      29       uwlink        true    1      965    3.0    true  true   0.0
  2fm7bd      27      27       uwlink        true    1      965    3.0    true  true   0.0
  hvuzar      34      34       uwlink        true    1      965    3.0    true  true   0.0
  3d82qo      31      28       uwlink        true    2      965   -7.0    true  true   0.0

22.6 How trace works

Route discovery finds routes; the trace facility answers a different, diagnostic question — which nodes does a datagram actually pass through on the way to a destination and back? It is exposed through the trace command, and is built on two messages that live at different layers:

RouteTraceReq is the user-facing request, handled by rdp. You send it to the rdp agent (or run trace), naming the destination in to. It is a plain control message; you never handle the trace as it is carried out, only its final result — a RouteTraceNtf.
DatagramTraceReq is the routing-layer probe that does the carrying. It is a DatagramReq subclass owned by the ROUTING service: the router forwards it while each node appends its own address, so the datagram accumulates the path it takes (Chapter 21).

rdp is a client of that routing mechanism. When it receives a RouteTraceReq, it sends a DatagramTraceReq over the route currently installed in the routing tables — so trace reports the route already in use; it does not discover new ones (that is what rreq is for), and if no route to the destination exists, the trace simply fails. The router forwards the probe to the destination, accumulating the outbound hops. At the destination, rdp turns the probe around and sends it back the same way, so the return hops are appended too. Back at the source, rdp has the complete out-and-back hop sequence and delivers it to the original requester as a RouteTraceNtf, whose trace field is the list of node addresses traversed.

A worked example of the trace command and its output appears in Chapter 5.

22.7 Implementation

22.7.1 RouteDiscoveryProtocol (`rdp`)

Class	Services	Capabilities	Availability
`RouteDiscoveryProtocol`	`ROUTE_MAINTENANCE`	—	default stack

The default implementation is the rdp agent, loaded as part of the default stack (Chapter 13).

22.7.1.1 How it works

When asked to find a route (via a RouteDiscoveryReq, or the rreq command), the agent floods a route-request probe (RREQ) into the network. Each node that receives a probe rebroadcasts it — but only up to a maximum hop count, and only the first time it sees a given probe, suppressing duplicates it has cached (for a few minutes) so that the controlled flood terminates rather than circulating forever. Every relayer records the path the probe took, so that when a probe reaches the destination, the destination can return a route response (RRSP) back along the reverse path; as the response travels back, each node along the way learns a route to the originator and vice versa. The discovered routes are announced as RouteDiscoveryNtf notifications, from which the routing agent populates its table. Because the acoustic channel is lossy and time-varying, discovery is inherently probabilistic — repeating it (or sending several probes via the count field) may turn up additional or better routes. The route-trace diagnostic that this agent also provides is described separately in Section 22.6.

22.7.1.2 Usage notes

Run rreq a few times (or raise the probe count) on lossy networks to improve the chance of discovering good routes.
Use trace to verify that multi-hop routing is behaving as intended.
Limit maxHops to bound the extent of the flood on large networks.