OLD | NEW |
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */ | 1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */ |
2 /* | 2 /* |
3 * Copyright (c) 2011 Yufei Cheng | 3 * Copyright (c) 2011 Yufei Cheng |
4 * | 4 * |
5 * This program is free software; you can redistribute it and/or modify | 5 * This program is free software; you can redistribute it and/or modify |
6 * it under the terms of the GNU General Public License version 2 as | 6 * it under the terms of the GNU General Public License version 2 as |
7 * published by the Free Software Foundation; | 7 * published by the Free Software Foundation; |
8 * | 8 * |
9 * This program is distributed in the hope that it will be useful, | 9 * This program is distributed in the hope that it will be useful, |
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of | 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of |
(...skipping 14 matching lines...) Expand all Loading... |
25 * | 25 * |
26 * Work supported in part by NSF FIND (Future Internet Design) Program | 26 * Work supported in part by NSF FIND (Future Internet Design) Program |
27 * under grant CNS-0626918 (Postmodern Internet Architecture), | 27 * under grant CNS-0626918 (Postmodern Internet Architecture), |
28 * NSF grant CNS-1050226 (Multilayer Network Resilience Analysis and Experimenta
tion on GENI), | 28 * NSF grant CNS-1050226 (Multilayer Network Resilience Analysis and Experimenta
tion on GENI), |
29 * US Department of Defense (DoD), and ITTC at The University of Kansas. | 29 * US Department of Defense (DoD), and ITTC at The University of Kansas. |
30 */ | 30 */ |
31 | 31 |
32 #include "dsr-rreq-table.h" | 32 #include "dsr-rreq-table.h" |
33 #include "ns3/log.h" | 33 #include "ns3/log.h" |
34 #include <algorithm> | 34 #include <algorithm> |
| 35 #include <iostream> |
35 | 36 |
36 NS_LOG_COMPONENT_DEFINE ("RreqTable"); | 37 NS_LOG_COMPONENT_DEFINE ("RreqTable"); |
37 | 38 |
38 namespace ns3 { | 39 namespace ns3 { |
39 namespace dsr { | 40 namespace dsr { |
40 | 41 |
41 NS_OBJECT_ENSURE_REGISTERED (RreqTable); | 42 NS_OBJECT_ENSURE_REGISTERED (RreqTable); |
42 | 43 |
43 TypeId RreqTable::GetTypeId () | 44 TypeId RreqTable::GetTypeId () |
44 { | 45 { |
45 static TypeId tid = TypeId ("ns3::dsr::RreqTable") | 46 static TypeId tid = TypeId ("ns3::dsr::RreqTable") |
46 .SetParent<Object> () | 47 .SetParent<Object> () |
47 .AddConstructor<RreqTable> () | 48 .AddConstructor<RreqTable> () |
48 ; | 49 ; |
49 return tid; | 50 return tid; |
50 } | 51 } |
51 | 52 |
52 RreqTable::RreqTable () | 53 RreqTable::RreqTable () |
53 : m_linkStates (PROBABLE) | 54 : m_linkStates (PROBABLE) |
54 { | 55 { |
55 } | 56 } |
56 | 57 |
57 RreqTable::~RreqTable () | 58 RreqTable::~RreqTable () |
58 { | 59 { |
59 NS_LOG_FUNCTION_NOARGS (); | 60 NS_LOG_FUNCTION_NOARGS (); |
60 } | 61 } |
61 | 62 |
62 bool | 63 void |
63 RreqTable::UpdateEntryTTL (Ipv4Address dst) | 64 RreqTable::RemoveLeastExpire (std::map<Ipv4Address, RreqTableEntry > & rreqDstMa
p) |
64 { | 65 { |
65 for (std::vector<RreqTableEntry>::iterator i = m_rreqTable.begin (); i != m_rr
eqTable.end (); ++i) | 66 NS_LOG_FUNCTION (this); |
| 67 Ipv4Address firstExpire; |
| 68 Time max = Seconds (0.0); |
| 69 for (std::map<Ipv4Address, RreqTableEntry >::const_iterator i = |
| 70 rreqDstMap.begin (); i != rreqDstMap.end (); ++i) |
66 { | 71 { |
67 if (i->m_dst == dst) | 72 Ipv4Address dst = i->first; |
| 73 RreqTableEntry rreqTableEntry = i->second; |
| 74 if (rreqTableEntry.m_expire > max) |
68 { | 75 { |
69 uint8_t ttl = i->m_ttl; | 76 max = rreqTableEntry.m_expire; |
70 if (ttl - 1) | 77 firstExpire = dst; |
71 { | |
72 i->m_ttl = (ttl - 1); | |
73 return true; | |
74 } | |
75 return false; | |
76 } | |
77 else | |
78 { | |
79 NS_LOG_DEBUG ("The request table entry not found"); | |
80 return false; | |
81 } | 78 } |
82 } | 79 } |
83 return false; | 80 rreqDstMap.erase (firstExpire); |
84 } | |
85 | |
86 bool | |
87 RreqTable::Find (Ipv4Address dst) | |
88 { | |
89 for (std::vector<RreqTableEntry>::iterator i = m_rreqTable.begin (); i != m_rr
eqTable.end (); ++i) | |
90 { | |
91 if (i->m_dst == dst) | |
92 { | |
93 return true; | |
94 } | |
95 } | |
96 return false; | |
97 } | 81 } |
98 | 82 |
99 void | 83 void |
100 RreqTable::Update (RreqTableEntry & entry) | 84 RreqTable::FindAndUpdate (Ipv4Address dst) |
101 { | 85 { |
102 NS_LOG_LOGIC ("Open link to " << entry.m_dst); | 86 NS_LOG_LOGIC ("Find and update the route request entry for " << dst); |
103 for (std::vector<RreqTableEntry>::iterator i = m_rreqTable.begin (); i != m_rr
eqTable.end (); ++i) | 87 std::map<Ipv4Address, RreqTableEntry >::const_iterator i = |
| 88 m_rreqDstMap.find (dst); |
| 89 if (i == m_rreqDstMap.end ()) |
104 { | 90 { |
105 if (i->m_dst == entry.m_dst) | 91 NS_LOG_DEBUG ("The request table entry not found"); |
| 92 /* |
| 93 * Drop the most aged packet when buffer reaches to max |
| 94 */ |
| 95 if (m_rreqDstMap.size () >= m_requestTableSize) |
106 { | 96 { |
107 uint16_t reqNo = i->m_reqNo; | 97 RemoveLeastExpire (m_rreqDstMap); |
108 i->m_reqNo = (reqNo + 1); | 98 NS_LOG_DEBUG ("The request table size after erase "); |
109 return; | |
110 } | 99 } |
| 100 RreqTableEntry rreqTableEntry; |
| 101 rreqTableEntry.m_reqNo = 0; |
| 102 rreqTableEntry.m_expire = Simulator::Now(); |
| 103 m_rreqDstMap [dst] = rreqTableEntry; |
111 } | 104 } |
112 /* | 105 else |
113 * Drop the most aged packet when buffer reaches to max | |
114 */ | |
115 if (m_rreqTable.size () >= m_requestTableSize) | |
116 { | 106 { |
117 m_rreqTable.erase (m_rreqTable.begin ()); | 107 NS_LOG_DEBUG ("Find the request table entry, increment the request count")
; |
| 108 Ipv4Address dst = i->first; |
| 109 RreqTableEntry rreqTableEntry = i->second; |
| 110 NS_LOG_DEBUG ("The request count before incrementing " << rreqTableEntry.m
_reqNo); |
| 111 rreqTableEntry.m_reqNo = (rreqTableEntry.m_reqNo + 1); |
| 112 rreqTableEntry.m_expire = Simulator::Now(); |
| 113 m_rreqDstMap [dst] = rreqTableEntry; |
118 } | 114 } |
119 NS_LOG_DEBUG ("The request table entry not found"); | |
120 RreqTableEntry rreqTableEntry; | |
121 rreqTableEntry.m_dst = entry.m_dst; | |
122 rreqTableEntry.m_ttl = entry.m_ttl; | |
123 rreqTableEntry.m_reqNo = entry.m_reqNo; | |
124 m_rreqTable.push_back (rreqTableEntry); | |
125 } | 115 } |
126 | 116 |
127 bool | 117 void |
128 RreqTable::RemoveRreqEntry (Ipv4Address dst) | 118 RreqTable::RemoveRreqEntry (Ipv4Address dst) |
129 { | 119 { |
130 NS_LOG_DEBUG ("Remove rreq entry"); | 120 NS_LOG_DEBUG ("Remove rreq entry with index dst"); |
131 for (std::vector<RreqTableEntry>::iterator i = m_rreqTable.begin (); i != m_rr
eqTable.end (); ++i) | 121 std::map<Ipv4Address, RreqTableEntry >::const_iterator i = |
| 122 m_rreqDstMap.find (dst); |
| 123 if (i == m_rreqDstMap.end ()) |
132 { | 124 { |
133 if (i->m_dst == dst) | 125 NS_LOG_DEBUG ("The request table entry not found"); |
134 { | |
135 NS_LOG_DEBUG ("The rreq entry been removed"); | |
136 m_rreqTable.erase (i); | |
137 return true; | |
138 } | |
139 } | 126 } |
140 return false; | 127 else |
| 128 { |
| 129 // erase the request entry |
| 130 m_rreqDstMap.erase (dst); |
| 131 } |
141 } | 132 } |
142 | 133 |
143 uint16_t | 134 uint16_t |
144 RreqTable::GetRreqCnt (Ipv4Address dst) | 135 RreqTable::GetRreqCnt (Ipv4Address dst) |
145 { | 136 { |
146 for (std::vector<RreqTableEntry>::iterator i = m_rreqTable.begin (); i != m_rr
eqTable.end (); ++i) | 137 NS_LOG_DEBUG ("Get the request count for a certain dst"); |
| 138 std::map<Ipv4Address, RreqTableEntry >::const_iterator i = |
| 139 m_rreqDstMap.find (dst); |
| 140 if (i == m_rreqDstMap.end ()) |
147 { | 141 { |
148 if (i->m_dst == dst) | 142 NS_LOG_DEBUG ("The request table entry not found"); |
149 { | 143 FindAndUpdate (dst); |
150 return (i->m_reqNo); | 144 return 0; |
151 } | |
152 } | 145 } |
153 return 0; | 146 else |
154 } | |
155 | |
156 bool | |
157 RreqTable::IncrementRreqCnt (Ipv4Address dst) | |
158 { | |
159 for (std::vector<RreqTableEntry>::iterator i = m_rreqTable.begin (); i != m_rr
eqTable.end (); ++i) | |
160 { | 147 { |
161 if (i->m_dst == dst) | 148 RreqTableEntry rreqTableEntry = i->second; |
162 { | 149 NS_LOG_DEBUG ("Find the request count for " << dst << " " << rreqTableEntr
y.m_reqNo); |
163 i->m_reqNo = (i->m_reqNo + 1); | 150 return rreqTableEntry.m_reqNo; |
164 return true; | |
165 } | |
166 } | 151 } |
167 NS_LOG_DEBUG ("This dst has not been seen, create a new entry"); | |
168 RreqTableEntry rreqTableEntry; | |
169 rreqTableEntry.m_dst = dst; | |
170 rreqTableEntry.m_ttl = m_initHopLimit; | |
171 rreqTableEntry.m_reqNo = 0; | |
172 m_rreqTable.push_back (rreqTableEntry); | |
173 NS_LOG_DEBUG ("The request table size " << m_rreqTable.size ()); | |
174 return false; | |
175 } | 152 } |
176 | 153 |
177 // -----------------------------------------------------------------------------
----------------------------- | 154 // -----------------------------------------------------------------------------
----------------------------- |
178 /** | 155 /** |
179 * This part takes care of the route request from a specific source | 156 * This part takes care of the route request from a specific source |
180 * need to ignore future route requests from same source for same destination wi
th same identification | 157 * need to ignore future route requests from same source for same destination wi
th same identification |
181 */ | 158 */ |
182 | |
183 bool | 159 bool |
184 RreqTable::FindSrc (Ipv4Address source, Ipv4Address target, uint16_t id) | 160 RreqTable::FindSrc (Ipv4Address source, Ipv4Address target, uint16_t id) |
185 { | 161 { |
186 std::map<Ipv4Address, std::vector<SourceRreqEntry> >::const_iterator i = | 162 std::map<Ipv4Address, std::list<SourceRreqEntry> >::const_iterator i = |
187 m_rreqMap.find (source); | 163 m_rreqMap.find (source); |
188 if (i == m_rreqMap.end ()) | 164 if (i == m_rreqMap.end ()) |
189 { | 165 { |
190 NS_LOG_LOGIC ("No Request entry for " << source << " found"); | 166 NS_LOG_LOGIC ("No Request entry for " << source << " found"); |
191 SourceRreqEntry sourceRreqEntry; | 167 SourceRreqEntry sourceRreqEntry; |
192 sourceRreqEntry.m_dst = target; | 168 sourceRreqEntry.m_dst = target; |
193 sourceRreqEntry.m_identification = id; | 169 sourceRreqEntry.m_identification = id; |
194 std::vector<SourceRreqEntry> rqVector; | 170 sourceRreqEntry.m_expire = Simulator::Now(); |
| 171 std::list<SourceRreqEntry> rqVector; |
195 rqVector.push_back (sourceRreqEntry); | 172 rqVector.push_back (sourceRreqEntry); |
196 std::pair<std::map<Ipv4Address, std::vector<SourceRreqEntry> >::iterator,
bool> result = | 173 m_rreqMap[source] = rqVector; |
197 m_rreqMap.insert (std::make_pair (source, rqVector)); | |
198 return false; | 174 return false; |
199 } | 175 } |
200 else | 176 else |
201 { | 177 { |
202 NS_LOG_LOGIC ("Request entry for " << source << " found in the cache"); | 178 NS_LOG_LOGIC ("Request entry for " << source << " found in the cache"); |
203 for (std::map<Ipv4Address, std::vector<SourceRreqEntry> >::const_iterator
j = | 179 std::list<SourceRreqEntry> rqVector = i->second; |
204 m_rreqMap.begin (); j != m_rreqMap.end (); ++j) | 180 for (std::list<SourceRreqEntry>::iterator j = rqVector.begin (); j != rqVe
ctor.end (); ++j) |
205 { | 181 { |
206 Ipv4Address address = j->first; // Route Request Source IP address | 182 SourceRreqEntry rreqEntry = *j; |
207 std::vector<SourceRreqEntry> rqVector = j->second; // The route reques
t vector linked with destination address | 183 if ((rreqEntry.m_dst == target) && (rreqEntry.m_identification == id)) |
208 for (std::vector<SourceRreqEntry>::iterator k = rqVector.begin (); k !
= rqVector.end (); ++k) | |
209 { | 184 { |
210 SourceRreqEntry rreqEntry = *k; | 185 NS_LOG_DEBUG ("Found the request entry for source node with addres
s " << source); |
211 if ((rreqEntry.m_dst == target) && (rreqEntry.m_identification ==
id)) | 186 // j = rqVector.erase (j); |
212 { | 187 // rqVector.push_back(*j); |
213 NS_LOG_DEBUG ("Found the request entry and we should disgard t
he packet with request option"); | 188 // m_rreqMap[source] = rqVector; |
214 return true; | 189 return true; |
215 } | |
216 else | |
217 { | |
218 SourceRreqEntry rreqEntry; | |
219 rreqEntry.m_dst = target; | |
220 rreqEntry.m_identification = id; | |
221 // May need to check the size of the entry | |
222 rqVector.push_back (rreqEntry); | |
223 std::pair<std::map<Ipv4Address, std::vector<SourceRreqEntry> >
::iterator, bool> result = | |
224 m_rreqMap.insert (std::make_pair (source, rqVector)); | |
225 return false; | |
226 } | |
227 } | 190 } |
228 } | 191 } |
| 192 |
| 193 SourceRreqEntry rreqEntry; |
| 194 rreqEntry.m_dst = target; |
| 195 rreqEntry.m_identification = id; |
| 196 if (rqVector.size() >= m_requestIdSize) |
| 197 { |
| 198 // erase the first element when the size is larger than the request id
size (default: 16) |
| 199 rqVector.pop_front (); |
| 200 } |
| 201 // May need to check the size of the entry |
| 202 rqVector.push_back (rreqEntry); |
| 203 m_rreqMap[source] = rqVector; |
229 } | 204 } |
230 return false; | 205 return false; |
231 } | 206 } |
232 | 207 |
233 // -----------------------------------------------------------------------------
----------------------------- | 208 // -----------------------------------------------------------------------------
----------------------------- |
234 /** | 209 /** |
235 * This part takes care of the route request ID initialized from a specific sour
ce to one destination | 210 * This part takes care of the route request ID initialized from a specific sour
ce to one destination |
236 * Essentially a counter | 211 * Essentially a counter |
237 */ | 212 */ |
238 uint16_t | 213 uint16_t |
239 RreqTable::CheckUniqueRreqId (Ipv4Address dst) | 214 RreqTable::CheckUniqueRreqId (Ipv4Address dst) |
240 { | 215 { |
241 NS_LOG_DEBUG ("The size of id cache " << m_rreqIdCache.size ()); | 216 NS_LOG_DEBUG ("The size of id cache " << m_rreqIdCache.size ()); |
242 std::map<Ipv4Address, uint16_t>::const_iterator i = | 217 std::map<Ipv4Address, uint16_t>::const_iterator i = |
243 m_rreqIdCache.find (dst); | 218 m_rreqIdCache.find (dst); |
244 if (i == m_rreqIdCache.end ()) | 219 if (i == m_rreqIdCache.end ()) |
245 { | 220 { |
246 NS_LOG_LOGIC ("No Request id for " << dst << " found"); | 221 NS_LOG_LOGIC ("No Request id for " << dst << " found"); |
247 // /* | |
248 // * Drop the most aged id entry when the cache to max | |
249 // */ | |
250 // if (m_rreqIdCache.size () >= m_requestIdSize) | |
251 // { | |
252 // m_rreqIdCache.erase (m_rreqIdCache.begin ()); | |
253 // } | |
254 m_rreqIdCache[dst] = 0; | 222 m_rreqIdCache[dst] = 0; |
255 return 0; | 223 return 0; |
256 } | 224 } |
257 else | 225 else |
258 { | 226 { |
259 NS_LOG_LOGIC ("Request id for " << dst << " found in the cache"); | 227 NS_LOG_LOGIC ("Request id for " << dst << " found in the cache"); |
260 uint16_t rreqId = m_rreqIdCache[dst]; | 228 uint16_t rreqId = m_rreqIdCache[dst]; |
261 rreqId++; | 229 if (rreqId >= m_maxRreqId) |
262 m_rreqIdCache[dst] = rreqId; | 230 { |
| 231 NS_LOG_DEBUG ("The request id increase past the max value, so reset it
to 0"); |
| 232 rreqId = 0; |
| 233 m_rreqIdCache[dst] = rreqId; |
| 234 } |
| 235 else |
| 236 { |
| 237 rreqId++; |
| 238 m_rreqIdCache[dst] = rreqId; |
| 239 } |
| 240 NS_LOG_DEBUG ("The Request id for " << dst << " is " << rreqId); |
263 return rreqId; | 241 return rreqId; |
264 } | 242 } |
265 } | 243 } |
266 | 244 |
267 uint16_t | 245 uint16_t |
268 RreqTable::GetRreqSize () | 246 RreqTable::GetRreqSize () |
269 { | 247 { |
270 return m_rreqIdCache.size (); | 248 return m_rreqIdCache.size (); |
271 } | 249 } |
272 | 250 |
273 // -----------------------------------------------------------------------------
----------------------------- | 251 // -----------------------------------------------------------------------------
----------------------------- |
274 /** | 252 /** |
275 * This part takes care of black list which can save unidirectional link informa
tion | 253 * This part takes care of black list which can save unidirectional link informa
tion |
276 */ | 254 */ |
| 255 |
277 void | 256 void |
278 RreqTable::Invalidate () | 257 RreqTable::Invalidate () |
279 { | 258 { |
280 if (m_linkStates == QUESTIONABLE) | 259 if (m_linkStates == QUESTIONABLE) |
281 { | 260 { |
282 return; | 261 return; |
283 } | 262 } |
284 m_linkStates = QUESTIONABLE; | 263 m_linkStates = QUESTIONABLE; |
285 } | 264 } |
286 | 265 |
(...skipping 36 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
323 { | 302 { |
324 /* | 303 /* |
325 * Purge the expired blacklist entries | 304 * Purge the expired blacklist entries |
326 */ | 305 */ |
327 m_blackList.erase (remove_if (m_blackList.begin (), m_blackList.end (), | 306 m_blackList.erase (remove_if (m_blackList.begin (), m_blackList.end (), |
328 IsExpired ()), m_blackList.end ()); | 307 IsExpired ()), m_blackList.end ()); |
329 } | 308 } |
330 | 309 |
331 } // namespace dsr | 310 } // namespace dsr |
332 } // namespace ns3 | 311 } // namespace ns3 |
OLD | NEW |