Lightweight Mobile Routing

LMR

The Lightweight Mobile Routing algorithm (LMR) belongs to the class of link reversal algorithms. It addresses the issue of nonconvergence for partitioned networks found in the Gafni-Bertsekas algorithms. In addition it is an on demand routing protocol, so it maintains only routes that are actually needed. It has a route deletion mechanism that causes edges from the acyclic graph to become undirected.

The algorithm consists of two main parts:
* Route establishment
* Route maintenance

Query- and Reply-packets are used to establish routes whereas Falure-Query packets are issued when a downstream link gets lost.

Route establishment

When no route is actually needed for a given destination, the underlying graphs directions are undirected. If a route is needed for a destination, a node issues a Query- Packet for route discovery.

A Query-Packet (QRY) contains
* a sequence number,
* the id of the node for which a route is sought after,
* the id of the node which issued the request for the first time
* and a transmitting node id to distinguish the broadcasted messages among the neighbours.

QRY-packets only travel over undirected links of the underlying graph. The answer to the QRY is the RPY reply packet which only contains the destination id and the transmitting node id. RPY packets have as effect that the links over which they travel become directed in the opposite direction of propagation.

Suppose source S wants to send to D. Part of the graph is still undirected, but nodes 6 and 7 know of a route to D:

Node S issues a QRY which propagates over the undirected links...

until they hit a node which knows of a route to the destination. This node replies with a RPY which propagates in the opposite direction

The result should be a directed acyclic graph routed at the destination:

Note that each node that has received a query retransmits it only once. It distinguishes queries by their sequence numbers. Only the initiator, the source, may retransmit a query after a certain time during which it has not received a reply.

Route maintenance

LMR is an on-demand routing protocol. Route maintenance is only triggered when a route to a particular destination is still needed. This can be determined by monitoring the traffic at the router nodes. After a certain time-out period of no traffic a route is no more considered to be active.

A node which has lost its last link to a still active destination issues a Failure Query Packet (FQ) which has as affect that other nodes that previously routed through this link will not do so anymore. In our DAG, the edges to the uptstream nodes of the node which has lost the route will become undirected. Failure queries propagate until they hit a node which still has a route to the destination. This node which still has a route will send RPY packets which will travel in the opposite direction of the FQ and will redirect the edges as seen above with the replies to normal QRY packets.

For the route maintenance to work correctly nodes shall restransmit FQ packets regardless if they need themselves a route to the destination. A node which has no upstream links for a destination will not retransmit a FQ but will instead issue a normal QRY as in route estblishment.

Here, node 3 has lost its last downstream link to the destination:

The node issues a FQ, so its upstream links become undirected. A FQ packet contains the destination id and the originator id.

Nodes that know a route send RPY packets. A RPY packet contains the destination id and the id of the the node the RPY is addressed to

Notice that node 2 doesn't need a link to the destination (8) by itself and it will not be involved in the traffic, because it only has downstream links to the destination. If it looses those links in the future it will not issue a failure query, because for the node the route will not be needed.

Unlike the GB algorithm which always maintains a totally ordered set of nodes in the DAG using the "height" values, the maintenance procedure described so far does not guarantee that no loops could be formed, due to the asynchronous transmission of messages in a dynamically changing network topology. So countermeasures must be taken to prevent loop creation.

A node that receives a reply over an unassigned link checks if it has upstream neighbours for the destination. If not, it can consider the link as a downstream to the destination. Otherwise the link is marked "downstream blocked". This is done because the RPY could have as origin a node which is at the moment connected indirectly through an upstream neighbour. A link marked as blocked can not be considered for routing through. A blocked link can be converted to a normal downstream link if all upstream links have become unassigned. This happens when the upstream neighbours have received the propagated failure query. To be sure that all upstream links have become unassigned, there must be a handshake mechanism between the nodes that send or receive failure queries. This is achieved by marking the links "un-assigned waiting" or "awaiting broadcast" temporarily. "Unassigned waiting" prevents a node from transmitting until a reply or failure query has been received over the link. "Awaiting broadcast" tells a node that it has to send a RPY or FQ over the link.

Reliability of the link erasure mechanism

The undirected (unassigned) state of a link is synonym to the erasure of invalid routes, which was one main goal in the design of the LMR protocol. Unlike with the GB algorithms a portion of a graph that gets disconnected from the destination will not exchange link reversal messages forever. The failure query mechanism erases invalid directed edges and it has been proved that the algorithm converges if the network gets partitioned.

However, if the network (the Graph for a particular destination) gets partitioned at a given moment there may be still some directed links around in portions of the network which are further away from the (now unreachable) destination. So there will also be replies to failure queries which must be incorrect. This means that the network may become ustable for hopefully short periods of time, due to the asynchronous nature of the protocol. It will take a certain time until the failure queries have caught up with the propagation of false replies. However after an incertain time the FQs have erased all directed links and the network has settled to a stable condition.

Conclusion

The LMR agorithm is a link reversal algorithm which addresses the issue of partitioned networks found with the Gafni-Bertsekas algorithms, by providing a link erasure mechanism. However in a rapidly changing network there may be many false RPY packets producing message overhead. The benefits are that routes will be found rather quickly and broken links will have only local affect. One can expect good results if the network connectivity is rather high (dense network). Routes may be redundant. A higher level protocol could use redundant routes in a round-robin fashion to economically use local bandwidth.

References