4

I am learning about the AODV (ad-hoc on-demand distance vector) protocol. I saw a "sequence number" with a value like "A 46"; however, I don't understand why incrementing this sequence number can prevent loops. Why does this help?

  • 3
    Have you tried reading RFC 3561? If not, that is a very good place to start. – Mike Pennington Sep 14 '13 at 13:06
  • yes, i was reading that documentation, however i dont have time to read them all for now, really appreciate some quick guide... – jolin Sep 14 '13 at 13:23
6

Mike's suggestion to read RFC 3561 - Ad hoc On-Demand Distance Vector (AODV) Routing should do the trick; in the meantime, I will go ahead and summarize it for you.

Wireless (routing) protocols, such as AODV protocols, use sequence numbers in a different way than wireline protocols do. AODV maintains a table of destination IP addresses, along with the last sequence number. This way, if it receives the same routing sequence number in an update, it detects the duplicate and drops the update; thus, avoiding a potential loop. Additionally, AODV does not forward/process update packets that it has seen before. The sending node (based on whatever message they send Route request, Route Reply), maintains their own sequence numbers and increments it before sending a new packet out.

AODV is hardly alone in depending upon sequence numbers to avoid loops; RFC 4728 - Dynamic Source Routing (DSR) also depends on sequence numbers. Yet another wireless (multicast) routing protocol that uses sequence number to avoid looping is IETF Draft - The Adaptive Demand-Driven Multicast Routing Protocol for Mobile Ad Hoc Networks (ADMR).

We should note that layer-2 in wireless networks (typically) do not use Spanning Tree Protocol (STP) for loop prevention.

  • Thanks for your detailed answer! Another question pops up say there is a hopA with a sequence number of A-111, a hobB sends a RREQ with a destination sequence number A-111, if everything goes well, a packet from hobB will be sent to hobA, and as a result the hobA's sequence number will increase right? Meanwhile, if there is a hobC, which also sends a RREQ with a destination sequence number A-111, what happens now? is there any mechanism informing hobC that the sequence number of hobA has changed? – jolin Sep 14 '13 at 17:10
  • The sequence numbers are tied to the originator. So, if hopC sends a RREQ (or RREP) with A-111, it would no way interfere were A-111 seq number form hopB. It is the (hopX, seqnumber) tuple that is unique. When you go through the RFC, these things should get clearer. I would also recommend reading some of the AODV (and DSR) papers as well. – Manoj Pandey Sep 14 '13 at 17:21
  • oh yeah, that makes a lot more sense to me now. thanks a lot! – jolin Sep 14 '13 at 17:22
  • Welcome to NE Manoj, thank you for such a good answer. I hope you don't mind if I took the liberty of using active voice English ... could you proofread my edits? – Mike Pennington Sep 14 '13 at 17:32
  • @MikePennington, thank you! I am looking forward to learning from NE and also contributing my 2 cents, whenever I can! Yes, using active is better -- it has been long time since I was in college :-) – Manoj Pandey Sep 14 '13 at 19:22
0

Perkins, in his original paper on AODV, actually gives a mathematical proof of how sequence numbers can prevent loops. For details, see A. Proof of the Loop-free Property in Ad-hoc On-Demand Distance Vector Routing.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.