Advanced Ad Hoc Networks 2008

Homework 2 Solution



1. Textbook, Chapter 7, problem 4
Solution:
   No. In a highly mobile environment a table-driven routing protocol would cause very frequent updates resulting in decrease in the efficiency of the protocol.


2. Textbook, Chapter 7, problem 9
Solution:
    The algorithm need not give a deterministic result. This feature is because of the inherent non-determinism in the distributed algorithm which decides which node transmits the beacon first. Fig.1 shows two cases where different results are obtained for the same topology.

1


3. Textbook, Chapter 7, problem 11
Solution:
   The fisheye routing tables for node 7 and node 5 are given in Table 1 and 2, respectively.

Table 1: Routing table for node 7


Destination

Neighbors

Hops

7

2,6

0

2

1,3,7

1

6

5,7

1

1

2,5

2

3

2,4

2

5

1,4,6

2

4

3,5

3

Table 2: Routing table for node 5


Destination

Neighbors

Hops

5

1,4,6

0

1

2,5

1

4

3,5

1

6

5,7

1

2

1,3,7

2

3

2,4

2

7

2,6

2


4. Textbook, Chapter 7, problem 12
Solution:

Before link failure:
2
After link failure:
3


5. Textbook, Chapter 8, problem 10
Solution:
Total number of JoinRequest packets originated by source S1 and propagated in the network: 50*200/2=5000
Total number of JoinRequest packets originated by source S2 and propagated in the network: 50 (Source S2 sends JoinRequest at least once)
Total number of JoinReply packets sent by receivers: 7*200/2=700
Total number of PassReq packets sent by source S2: 2*200/2=200
Total number of Confirm packets sent by source S1: 2*200/2=200
Total number of control packets transmitted: 5000+700+200+200=6100