This exercise provides a look at the Broadcast Storm problem, as well as Phase Transition phenomena that hold the key to one possible solution.
Wireless networks of reasonable density possess a high degree of redundancy in that, if a message is broadcast to the entire network using naive flooding, the message is received multiple times by most nodes (from different neighbors). This can be inefficient from the viewpoint of energy consumption, and can also lead to phases of severe congestion when such broadcasts are ongoing. Several techniques have been proposed and studied to alleviate this problem. The simplest of these is the notion of "probabilistic flooding". This implies that when a node received a broadcast message, it re-broadcasts it with a probability "p". If the value "p" is carefully chosen, the message overhead can be substantially reduced, while still ensuring that most nodes receive the message. Underlying this are certain "phase transition" phenomena, that we shall briefly explore in this exercise. We shall use a simple Broadcast Agent coded in OTcl. You are provided a file p_bcast.tcl that comprises the relevant code.
Part 1: A Regular Grid Network 1. A script "pbcast_sim.tcl" is provided. Get the tcl script from here. This script takes one command-line argument: the re-broadcast probability. Script usage is : ns pbcast_sim.tcl -prob (probability) 2. We shall consider a topology of 400 nodes arranged in a 20x20 grid with a grid-spacing of 125m. At time 0, Node 210 (somewhere close to the center of the grid) originates a broadcast packet. This packet is flooded in the network with a certain probability that is specified at the beginning of the simulation. 3. Run the simulation for probability values: 0.1, 0.2, 0.3, 0.4, 0.45, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0. Remember that probability=1.0 is equivalent to complete flooding. Obtain the following statistics and plot them vs the probability value: Avg. no. of message copies received per node, Fraction of nodes that receive the message at least once. - Briefly describe the trends visible in the obtained graphs. In particular, what do you observe in the graph of fraction of nodes that receive the message at least once? - Does it seem that there might be some choice of probability < 1.0 that would allow most nodes to receive the broadcast? If such a value exists, how much message overhead is saved with this value compared to flooding, and what fraction of nodes receive the value when the probability is slightly less (-0.1/-0.2) than this value?
Part 2: Random Networks 1. A script "pbcast_randsim.tcl" is provided. Get the tcl script from here. This script takes two command-line arguments: the name of the scenario-file, and the re-broadcast probability. Script usage is : ns pbcast_randsim.tcl -scenfile (scenario-file) -prob (probability) 2. We shall now consider random networks of 400 nodes. Use the "scengen" utility available with ns2 to generate 5 random topologies of 400 nodes over a 2500m x 2500m area, each with a min speed of 1.0 m/s and a maximum speed of 2.0 m/s. (Go to /ns-allinone-2.2*/ns-2.2*/indep-utils/cmu-scen-gen and use setdest as follows - ./setdest -v {1/2} -n {no of nodes} -p {pause time} -M {max speed} -t {simulation time} -x {terrain x dimension} -y {terrain y dimension} > scenario-file) 3. For each topology, run the simulation with the same probability values as in part 1. Obtain the same two statistics, as in part 1, for each topology and plot them vs the re-broadcast probability. There should be only 2 graphs, one for each statistic. - Once again, describe the trends visible in the obtained graphs? Are they similar or different to those seen in part 1? NOTE : You might find it useful to use awk to obtain the statistics required for this exercise. Get it from here.
1. What is broadcast storm problem? 2. Overview of IEEE 802.11 3. Know ns2