Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Ad-hoc network routing: DSDV, DSR, AODV and ZRP

Concise study notes comparing four ad-hoc routing approaches (DSDV, DSR, AODV, ZRP) with definitions, derivations, algorithm traces, formulas, common mistakes and exam guidance.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Ad-hoc routing protocols are used when mobile nodes form a network without fixed infrastructure (for example, disaster recovery, vehicle-to-vehicle or device-to-device communication). Engineers use these protocols to design and tune routing behavior (latency, overhead, robustness) for mobile computing systems and for parts of courses such as Mobile IP, VANETs and 5G D2D.

Key ideas

Start with basic definitions and assumptions used across protocols:

  • Ad-hoc network: a network of wireless nodes that can communicate without fixed infrastructure; nodes may move and links may change.
  • Route: an ordered list of nodes (or next hops) used to deliver a packet from source to destination.
  • Hop: one wireless transmission between two nodes.

Distance-vector basis (used by DSDV)

  • Distance-vector routing: each node maintains a table (vector) of the currently known best distance (cost) to every destination. The core equation (Bellman-Ford) is:
    • D_x(y) = min_{v in N(x)} { c(x,v) + D_v(y) } where node x uses neighbor v's distance to y and the cost c(x,v) to pick the best.
  • Assumptions: periodic exchange of vectors between neighbors; cost additivity across hops.
  • Problems: slow convergence, count-to-infinity under link failure; countermeasures include split horizon and poisoned reverse; in DSDV specifically, destination sequence numbers are used to avoid loops and ensure freshness.

DSDV (Destination-Sequenced Distance-Vector)

  • DSDV: a proactive (table-driven) ad-hoc routing protocol derived from distance-vector with sequence numbers to avoid routing loops and to determine freshness.
  • Each route carries a sequence number issued by the destination; higher number = fresher. When a link break is detected to a destination, the detecting node advertises that destination with hop count = Infinity and a sequence number one greater than the last known (odd), to invalidate stale routes.
  • Every node periodically broadcasts its routing table to neighbors (full or incremental updates). On receiving table entries, a node applies Bellman-Ford with sequence-number comparison: prefer route with higher sequence number; if equal, prefer smaller metric (hop count).
  • Draw to show: a node table row: Destination | Next hop | Metric (hop count) | Sequence number | Install time.

DSR (Dynamic Source Routing)

  • DSR: an on-demand protocol using source routing and route caches.
  • Route Discovery: source floods a Route Request (RREQ) that accumulates the path; destination replies with Route Reply (RREP) containing the full path. The packet header carries the full route (list of nodes) — that is source routing.
  • Route Maintenance: intermediate nodes detect link breaks (e.g., via ACK or link-layer feedback) and send Route Error (RERR) back to source; source then uses cache or re-initiates discovery.
  • Draw to show: RREQ flooded from S to D collecting path S-A-B-D; RREP returns D-B-A-S; data packets contain header [S, A, B, D].

AODV (Ad-hoc On-demand Distance Vector)

  • AODV: an on-demand protocol that mixes distance-vector ideas with sequence numbers; maintains routing tables with next-hop and hop count but does not carry full path in data packets.
  • Route Discovery: source broadcasts RREQ with its own sequence number and the last known destination sequence number; nodes record reverse routes. Destination or intermediate node with fresh route sends RREP back along reverse path (unicast). Sequence numbers ensure loop freedom and freshness.
  • Route Maintenance: link break triggers RERR messages to affected upstream nodes who invalidate routes; precursor lists help identify affected neighbors, and an intermediate node may optionally attempt local repair.
  • AODV uses periodic Hello messages optionally for neighbor detection. RREQs carry a per-source broadcast ID; nodes drop duplicate RREQs identified by (SourceAddr, BroadcastID). Expanding ring search may be used by setting a small TTL initially and increasing it on retries to limit flooding.
  • Important invariant (used in proofs): a route with higher destination sequence number is strictly fresher; AODV chooses RREP with greatest seqnum or, if equal, smallest hop count.

ZRP (Zone Routing Protocol)

  • ZRP: a hybrid protocol combining proactive and reactive approaches. Each node defines a routing zone of radius k hops (k is an integer >= 0).
  • Inside the zone, an Intra-zone Routing Protocol (IARP) maintains routes proactively. Between zones, an Inter-zone Routing Protocol (IERP) performs reactive discovery, assisted by Bordercast Resolution Protocol (BRP) to efficiently target border nodes.
  • Behavior: for destinations within k hops, use IARP; for beyond k, source queries border nodes which in turn query their zones until the destination or route is found.
  • Draw: node X with circle radius k showing interior nodes and border nodes; arrows illustrating bordercast to other zones.

Diagrams to draw in exam answers (describe exactly):

  1. Small 4-node graph: nodes A,B,C,D in a square with diagonals optional. Label link costs as 1 and show DSDV routing tables at each node (columns as above).
  2. Line topology S-A-B-D: show RREQ accumulation for DSR with path labels on packet.
  3. Small tree for AODV: source S, intermediate A,B, destination D; show RREQ reverse route creation and RREP unicast along reverse path with seqnums.
  4. ZRP node with circle: center node, nodes within k=1 or k=2 highlighted; mark border nodes and bordercast arrows.

Formulas

D_x(y) = min_{v in N(x)} { c(x,v) + D_v(y) } — D_x(y) is cost from x to y; N(x) is neighbors of x; c(x,v) is cost of link (x,v); unit: cost (often hop count, unitless), applies to distance-vector protocols.

RouteOverhead = ControlPackets / DataPackets — ControlPackets and DataPackets are counts in the same time interval; unitless ratio; useful to compare protocol efficiency.

Cost(path) = Σ_{i=1..n-1} c(node_i, node_{i+1}) — cost of a path as sum of link costs; unit: same as link cost (often unitless if hop count). Applies to path selection.

Freshness: seq_A > seq_B ⇒ route A is fresher than route B — sequence numbers are integers; higher means newer information. Applies in DSDV and AODV.

Note: no single standard SI unit for hop count (it's a count). Verify if you need link transmission times or bandwidth — those are separate metrics.

Worked examples

Example 1 — DSDV table update (4 nodes) Network: A—B—C—D in a line. All link costs = 1. Initial step (time 0): each node advertises itself: A: (A,0,sn=2), B: (B,0,sn=2), etc. Assume sequence numbers even for reachable routes and increment by destination when it sends update. After first exchange, compute A's table: A knows B direct (next=B, metric=1, seq=2), B knows C etc. Using Bellman-Ford: A's cost to C = min{ via B: c(A,B)+D_B(C) } = 1 + 1 = 2. Table row: Destination C | Next hop B | Metric 2 | Seq number from C (2). Now link B—C breaks. B detects the break to destination C and advertises C as unreachable with hop count = Infinity and an odd sequence number (last known from C plus 1, e.g., 3). A receives and updates C's entry because seq=3 (fresher), sets metric=Infinity. Nodes on the A—B side mark C unreachable until a new route forms; C still has a self-route with metric 0. Bold final answer: A's route to C = unreachable (metric=∞), seq=3.

Example 2 — DSR route discovery trace Topology: S—A—B—D (linear). S wants to send to D and has no route. Step 1: S broadcasts RREQ: [src=S, dest=D, path=[S]] Step 2: A receives, appends itself, re-broadcasts: path=[S,A]. B receives and repeats: path=[S,A,B]. D receives the RREQ with path=[S,A,B]; as destination, it does not rebroadcast but forms the RREP using the accumulated path plus itself. Step 3: D sends RREP back to S using accumulated path reversed: RREP path = [D,B,A,S]. Data packets then carry source route header [S,A,B,D] and are forwarded accordingly. If B—D fails later, B sends RERR to S; S removes route from its cache and re-initiates discovery. Show final: S's data packet header = [S,A,B,D]; packet forwarded to A then B then D. Bold: delivered along source route.

Example 3 — AODV route discovery and sequence numbers Topology: S—A—B—D. S has seqnum 10. D has seqnum 20. S broadcasts RREQ with destSeq=20. A receives and records reverse route to S. B records reverse to S. D receives the RREQ and replies with an RREP containing destSeq=20 and hop count initialized to 0; as the RREP is forwarded back along B then A to S, each hop increments the hop count. Intermediate nodes install forward routes to D: at B, hop count=1; at A, hop count=2; at S, hop count=3. Bold: S installs route to D via A with hop count=3. If later an intermediate node has a fresher route (higher seqnum) it replies: route selection rule: prefer higher seqnum, then smaller hop count.

Example 4 — ZRP with k=1 Nodes: center X, neighbors A,B,C within 1 hop; outer node D at 2 hops via B. For destination D: X queries its border nodes (A,B,C). B is border and queries its zone; B discovers D inside its zone and replies to X with path X-B-D. ZRP avoided flooding entire network. Bold: bordercast reduced query scope compared to flood.

Common mistakes

  • For DSR, forgetting that data packets carry the full source route; for AODV, assuming full path is carried in data packets — AODV only stores next-hop entries.
  • In Bellman-Ford step, forgetting to apply sequence-number freshness (in DSDV) before metric comparison.
  • Drawing RREQ accumulation incorrectly for DSR (must show path recorded in RREQ, not in RREP).

For your exam

Typical question types: short definitions (define DSDV/DSR/AODV/ZRP), compare-and-contrast (table of proactive vs reactive vs hybrid, loop avoidance methods), algorithm trace (trace route discovery or table exchanges on a small topology), derivation (write Bellman-Ford update and explain count-to-infinity), and diagram-based answers (draw zone for ZRP or show RREQ/RREP flows). What full-marks answers include:

  • For definitions: clear bold definition, protocol class (proactive/reactive/hybrid), core mechanisms (sequence numbers, source routing, routing tables), and pros/cons.
  • For traces: labeled topology, numbered steps for messages (RREQ, RREP, updates), table states after each step, and final outcome.
  • For comparisons: a small table listing overhead, latency to discover route, scalability, loop prevention, and typical use-case.

Quick check

  1. Which protocol uses source routing and carries the full route in packet headers?
  2. In DSDV and AODV, what does a larger sequence number mean?
  3. In ZRP, what is a border node (briefly)?

Answers: 1) DSR. 2) It means the routing information is fresher (prefer larger seqnum). 3) A border node is any node at exactly k hops from the zone center that forwards inter-zone queries (for radius k).

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?