Ad hoc On-Demand Distributed Minimal Hop based Cycle eliminated Routing Algorithm

1 u = v

1.1 Nbu[v] = local

2 if u!=v then, Nbu[v] w, where w is the first neighbour of u on a shortest path from u to v
(Multithreaded operation at u)

2.1 Sends Rreq to Neigh[u]

(operation at w)
2.1.1 For each Neigh(u) having d(v) in cache

2.1.1.1 Reply to Rreq to u by exponential time proportional to hops to v.

(Route Maintainance Operation)
2.1.1.2 Make a Async message (mydist, v, d) to all its neighbours

(operations at Neigh(w) say z)
2.1.1.2.1 Receive message (mydist,v,d)
2.1.1.2.2 Decide on d(z,v)<= d(w,z)(1)+d(w,v)
2.1.1.2.3 Reply to w if false (notifying that path from w is minimal)
2.1.1.2.4 Update Cache, Nbu[v] vector = w
2.1.1.2.5 Notify Neigh(z) about change

2.1.1.3 Make a reverse route entry by Lsd

2.1.2 If d(v) = ndef (Recursive Route Discovery operation)
2.1.2.1 Sends Rreq to Neigh(w)
2.1.2.2 Append route list Lsd with w

2.2 Receive and process Rres

2.2.1 For Rreq TTL accept Rres
2.2.2 Process minimal hop and 2.2.3 Extract Lsd and make route entry for Destination and Intemediate nodes too.

3 If no route to v

3.1 Neigh(v) = udef
3.2 Propagate Rerr to intermediate nodes so that stale entries (containing route for v from u) in other Uks can be removed.


Satifiability conditions for Nbu[v]
a if u=v, then, Nbu[v] = local
b1 if u!=v then, Nbu[v] w, where w is the first neighbour of u on a shortest path from u to v
b2 if u!=v then, and for all w Dw[v] >= N-1, then Du[v] = N {u and v are in different connected components}
c if no path from u to v exists then Nbu[v] = udef