Left: | ||
Right: |
LEFT | RIGHT |
---|---|
1 .. include:: replace.txt | 1 .. include:: replace.txt |
2 .. highlight:: cpp | 2 .. highlight:: cpp |
3 | 3 |
4 Epidemic Routing | 4 Epidemic Routing |
5 ---------------- | 5 ---------------- |
6 | 6 |
7 Epidemic Routing protocol is a controlled flooding routing protocol | 7 Epidemic Routing protocol is a controlled flooding routing protocol |
8 designed specifically for use in multi-hop wireless ad hoc networks | 8 designed specifically for use in multi-hop wireless ad hoc networks |
9 of mobile nodes. This routing protocol is designed for intermittent· | 9 of mobile nodes. This routing protocol is designed for intermittent· |
10 or sparse networks. Basically, incoming packets are stored in· | 10 or sparse networks. Packets are held in the source nodes' buffer until |
11 the sender's buffer. When two nodes come into contact, disjoint· | 11 the source node comes into communication range with another node.·· |
Peter Barnes
2014/09/23 22:54:25
receiver's buffer.
mjf.alenazi
2014/11/25 19:51:51
Packets are actually stored in the sender's buffer
| |
12 packets are exchanged. Packets are dropped if they expire or buffers· | 12 The packets are transmitted to the new node, which becomes a transit· |
13 reaches a certain limit. It is not useful for dense networks since· | 13 node for those packets. Transit nodes hold all packets received until· |
14 the number of duplicate packets will be very large. | 14 they come into range with other nodes, at which point they each send· |
15 the other any packets the other doesn't already have. The name "epidemic"· | |
16 is drawn from the way packets spread virally by communication | |
17 contact between nodes. At the source and all transit nodes, packets are | |
18 eventually dropped when the expire or the epidemic routing buffer· | |
19 becomes full, in which case the oldest packets are dropped. It is· | |
20 not useful for dense networks since the number of duplicate packets· | |
21 will be very large. | |
15 | 22 |
16 This model was developed by· | 23 This model was developed by· |
17 the `ResiliNets research group <http://www.ittc.ku.edu/resilinets>`_ | 24 the `ResiliNets research group <http://www.ittc.ku.edu/resilinets>`_ |
18 at the University of Kansas.·· | 25 at the University of Kansas.·· |
19 | 26 |
20 | 27 |
21 Epidemic Routing Routing Overview | 28 Epidemic Routing Routing Overview |
22 ********************************* | 29 ********************************* |
23 | 30 |
24 This implementation is based on the paper titled 'Epidemic Routing | 31 This implementation is based on the paper titled 'Epidemic Routing |
25 for Partially-Connected Ad Hoc Networks.'[#Vahdat]_ | 32 for Partially-Connected Ad Hoc Networks.'[#Vahdat]_ |
26 | 33 |
27 In the original paper, the implementation was on top of top of | 34 In the original paper, the implementation was on top of top of |
28 the Internet MANET Encapsulation Protocol (IMEP) layer, | 35 the Internet MANET Encapsulation Protocol (IMEP) layer, |
29 which is responsible for notifying the epidemic agent | 36 which is responsible for notifying the epidemic agent |
30 when a new node comes into radio range. However, since IMEP | 37 when a new node comes into radio range. However, since IMEP |
31 is not implemented in |ns-3|, a beacon mechanism is added to the implementation. | 38 is not implemented in |ns3|, a beacon mechanism is added to the implementation. |
32 | 39 |
33 | 40 |
34 ·· | |
35 Useful parameters | 41 Useful parameters |
36 ================= | 42 ================= |
37 | 43 |
38 Epidemic routing supports these options: | 44 Epidemic routing supports these options: |
39 | |
40 | 45 |
41 +-----------------------+-----------------------------------+---------------+ | 46 +-----------------------+-----------------------------------+---------------+ |
42 | Parameter | Description | Default | | 47 | Parameter | Description | Default | |
43 +=======================+===================================+===============+ | 48 +=======================+===================================+===============+ |
44 | HopCount | Maximum number of hops a packet | 64 | | 49 | HopCount | Maximum number of hops a packet | 64 | |
45 | | can be forwarded through. | |· | 50 | | can be forwarded through. | |· |
46 | | This value does not interact with | |· | 51 | | HopCount serves a similar | | |
47 | | IP TTL. However, the IP TTL is | | | 52 | | function to TTL, but the 8-bit | | |
48 | | incremented at each hop so the | | · | 53 | | range of TTL is too small, so we | | |
49 | | packet does not get dropped. | | · | 54 | | use a 32-bit field as in | | |
Peter Barnes
2014/09/23 22:54:25
Not done.
Explanations in the code review comment
mjf.alenazi
2014/11/25 19:51:51
Done.
| |
55 | | the paper. | | | |
50 +-----------------------+-----------------------------------+---------------+ | 56 +-----------------------+-----------------------------------+---------------+ |
51 | QueueLength | Maximum number of packets that | 64 | | 57 | QueueLength | Maximum number of packets that | 64 | |
52 | | can be stored in Epidemic buffer | | | 58 | | can be stored in Epidemic buffer | | |
53 +-----------------------+-----------------------------------+---------------+ | 59 +-----------------------+-----------------------------------+---------------+ |
54 | QueueEntryExpireTime | Maximum time a packet can live | | | 60 | QueueEntryExpireTime | Maximum time a packet can live | | |
55 | | since generated at the source. | Seconds(100) | | 61 | | since generated at the source. | Seconds(100) | |
56 | | Network-wide synchronization | | | 62 | | Network-wide synchronization | | |
57 | | is assumed | | | 63 | | is assumed. | | |
64 +-----------------------+-----------------------------------+---------------+ | |
65 | HostRecentPeriod | Time in seconds for host recent | | | |
66 | | period, in which hosts can not | Seconds(10) | | |
67 | | re-exchange summary vectors. | | | |
58 +-----------------------+-----------------------------------+---------------+ | 68 +-----------------------+-----------------------------------+---------------+ |
59 | BeaconInterval | Mean time interval between sending| Seconds(1) | | 69 | BeaconInterval | Mean time interval between sending| Seconds(1) | |
60 | | beacon packets. | | | 70 | | beacon packets. | | |
61 +-----------------------+-----------------------------------+---------------+ | 71 +-----------------------+-----------------------------------+---------------+ |
62 | BeaconRandomness | Random number of milliseconds | 100 | | 72 | BeaconRandomness | Random number of milliseconds | 100 | |
63 | | added at the beginning | | | 73 | | added at the beginning | | |
64 | | of the BeaconInterval to avoid | | | 74 | | of the BeaconInterval to avoid | | |
65 | | collisions | | | 75 | | collisions. | | |
66 +-----------------------+-----------------------------------+---------------+ | 76 +-----------------------+-----------------------------------+---------------+ |
67 | 77 |
68 | 78 |
69 Dropping Packets | 79 Dropping Packets |
70 ================ | 80 ================ |
71 Packets, stored in buffers, are dropped if they exceed HopCount, they are older than QueueEntryExpireTime, | 81 Packets, stored in buffers, are dropped if they exceed HopCount, they are |
72 or the holding buffer exceed QueueLength.·· | 82 older than QueueEntryExpireTime, or the holding buffer exceed QueueLength.·· |
73 | 83 |
74 | 84 |
75 Helper | 85 Helper |
76 ****** | 86 ****** |
77 | 87 |
78 To have a node run Epidemic Routing Protocol, the easiest way would be to use th e EpidemicHelper | 88 To have a node run Epidemic Routing Protocol, the easiest way would be to use |
79 in your simulation script. For instance (assuming ``mainNodes`` is a ``NodeConta iner``):: | 89 the EpidemicHelper |
90 in your simulation script. For instance (assuming ``mainNodes`` | |
91 is a ``NodeContainer``):: | |
80 | 92 |
81 EpidemicHelper epidemic; | 93 EpidemicHelper epidemic; |
82 mainNodes.Install (epidemic, adhocNodes); | 94 mainNodes.Install (epidemic, adhocNodes); |
83 | 95 |
84 This will run the epidemic routing using the default values. To use different pa rameter values:: | 96 This will run the epidemic routing using the default values. To use |
97 different parameter values:: | |
85 | 98 |
86 EpidemicHelper epidemic; | 99 EpidemicHelper epidemic; |
87 epidemic.Set ("HopCount", UintegerValue (20)); | 100 epidemic.Set ("HopCount", UintegerValue (20)); |
88 epidemic.Set ("QueueLength", UintegerValue (100)); | 101 epidemic.Set ("QueueLength", UintegerValue (100)); |
89 epidemic.Set ("QueueEntryExpireTime", TimeValue (Seconds (60))); | 102 epidemic.Set ("QueueEntryExpireTime", TimeValue (Seconds (60))); |
90 epidemic.Set ("BeaconInterval", UintegerValue (5)); | 103 epidemic.Set ("BeaconInterval", UintegerValue (5)); |
91 mainNodes.Install (epidemic, adhocNodes); | 104 mainNodes.Install (epidemic, adhocNodes); |
92 | 105 |
93 | 106 |
94 Examples | 107 Examples |
95 ******** | 108 ******** |
96 This example creates an N-node wireless network, which is set by default to 10 n odes. | 109 First example creates an N-node wireless network, which is set by |
97 The mobility model can be either static Grid or Randomwaypoint, which by default is selected to be Grid. | 110 default to 10 nodes. The mobility model can be either static Grid |
98 The data traffic is generated using OnOff application and received by PacketSink . There is one source and | 111 or Randomwaypoint, which by default is selected to be Grid. |
99 one sink in this configuration. | 112 The data traffic is generated using OnOff application and received |
100 One example can be found in ``src/epidemic/examples/epidemic-example.cc`` This | 113 by PacketSink. There is one source and one sink in this configuration. |
101 example creates the scenarios presented in the paper. [#Vahdat]_ We have 50 node s in an area of 1500 m x 300 m.· | 114 One example can be found in ``src/epidemic/examples/epidemic-example.cc`` |
102 45 nodes are selected to send a message of size 1KB to the other 44 nodes.· | 115 |
103 The total messages are 45 * 44 = 1980 messages. The buffer size is 2000 which is infinite | 116 This example creates the scenarios presented in the paper. |
104 in these scenarios. The ranges for the transmission are from 10 m to 250 m while | 117 [#Vahdat]_ We have 50 nodes in an area of 1500 m x 300 m.· |
105 the default is set to 50 m.· | 118 45 nodes are selected to send a packet of size 1KB to the other 44 nodes.· |
119 The total packets are 45 * 44 = 1980 packets. The buffer size is 2000 | |
120 which can hold all packets in each simulation. The ranges for the transmission | |
121 are from 10 m to 250 m while the default is set to 50 m.· | |
106 The example can be found in ``src/epidemic/examples/epidemic-benchmark.cc`` | 122 The example can be found in ``src/epidemic/examples/epidemic-benchmark.cc`` |
107 | 123 |
108 | 124 |
109 Validation | 125 Validation |
110 ********** | 126 ********** |
111 | 127 |
112 This model has been tested as follows: | 128 This model has been tested as follows: |
113 | 129 |
114 * Unit tests have been written to verify the internals of Epidemic. This can be found in ``src/epidemic/test/epidemic-test-suite.cc``. These tests verify whethe r the methods inside Epidemic module which deal with packet buffer, headers work correctly. | 130 * Unit tests have been written to verify the internals of Epidemic. This can· |
131 be found in ``src/epidemic/test/epidemic-test-suite.cc``. These tests verify | |
132 whether the methods inside Epidemic module which deal with packet buffer, | |
133 headers work correctly. | |
115 | 134 |
116 LIMITATIONS· | 135 LIMITATIONS· |
117 *********** | 136 *********** |
118 Epidemic does not work with more then one address per each interface. Additiona l addresses are ignored. | 137 Epidemic does not work with more than one address per each interface. Additiona l· |
138 addresses are ignored.· | |
139 | |
140 Epidemic routing protocol assume many beacons are exchanged in the time nodes· | |
141 are in range. If not, packets will not be delivered. | |
119 | 142 |
120 | 143 |
121 References | 144 References |
122 ********** | 145 ********** |
123 | 146 |
124 [#Vahdat] Amin Vahdat and David Becker, "Epidemic Routing for Partially-Connecte d | 147 .. rubric:: Footnotes |
125 Ad Hoc Networks," Duke University, Technical Report CS-200006, | 148 |
126 http://issg.cs.duke.edu/epidemic/epidemic.pdf | 149 .. [#Vahdat] Amin Vahdat and David Becker, "Epidemic Routing for |
150 Partially-Connected Ad Hoc Networks," Duke University, Technical | |
151 Report CS-200006, http://issg.cs.duke.edu/epidemic/epidemic.pdf | |
LEFT | RIGHT |