A Discrete-Event Network Simulator
API
Loading...
Searching...
No Matches
dsr-rreq-table.cc
Go to the documentation of this file.
1/*
2 * Copyright (c) 2011 Yufei Cheng
3 *
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License version 2 as
6 * published by the Free Software Foundation;
7 *
8 * This program is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 * GNU General Public License for more details.
12 *
13 * You should have received a copy of the GNU General Public License
14 * along with this program; if not, write to the Free Software
15 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
16 *
17 * Author: Yufei Cheng <yfcheng@ittc.ku.edu>
18 *
19 * James P.G. Sterbenz <jpgs@ittc.ku.edu>, director
20 * ResiliNets Research Group https://resilinets.org/
21 * Information and Telecommunication Technology Center (ITTC)
22 * and Department of Electrical Engineering and Computer Science
23 * The University of Kansas Lawrence, KS USA.
24 *
25 * Work supported in part by NSF FIND (Future Internet Design) Program
26 * under grant CNS-0626918 (Postmodern Internet Architecture),
27 * NSF grant CNS-1050226 (Multilayer Network Resilience Analysis and Experimentation on GENI),
28 * US Department of Defense (DoD), and ITTC at The University of Kansas.
29 */
30
31#include "dsr-rreq-table.h"
32
33#include "ns3/log.h"
34
35#include <algorithm>
36#include <iostream>
37
38namespace ns3
39{
40
41NS_LOG_COMPONENT_DEFINE("DsrRreqTable");
42
43namespace dsr
44{
45
46NS_OBJECT_ENSURE_REGISTERED(DsrRreqTable);
47
48TypeId
50{
51 static TypeId tid = TypeId("ns3::dsr::DsrRreqTable")
53 .SetGroupName("Dsr")
54 .AddConstructor<DsrRreqTable>();
55 return tid;
56}
57
59 : m_linkStates(PROBABLE)
60{
61}
62
64{
66}
67
68void
70{
71 NS_LOG_FUNCTION(this);
72 Ipv4Address firstExpire;
73 Time max = Seconds(0.0);
74 for (std::map<Ipv4Address, RreqTableEntry>::const_iterator i = m_rreqDstMap.begin();
75 i != m_rreqDstMap.end();
76 ++i)
77 {
78 Ipv4Address dst = i->first;
79 RreqTableEntry rreqTableEntry = i->second;
80 if (rreqTableEntry.m_expire > max)
81 {
82 max = rreqTableEntry.m_expire;
83 firstExpire = dst;
84 }
85 }
86 m_rreqDstMap.erase(firstExpire);
87}
88
89void
91{
92 NS_LOG_FUNCTION(this << dst);
93 std::map<Ipv4Address, RreqTableEntry>::const_iterator i = m_rreqDstMap.find(dst);
94 if (i == m_rreqDstMap.end())
95 {
96 NS_LOG_LOGIC("The request table entry for " << dst << " not found");
97 /*
98 * Drop the most aged packet when buffer reaches to max
99 */
100 if (m_rreqDstMap.size() >= m_requestTableSize)
101 {
103 NS_LOG_INFO("The request table size after erase " << (uint32_t)m_rreqDstMap.size());
104 }
105 RreqTableEntry rreqTableEntry;
106 rreqTableEntry.m_reqNo = 1;
107 rreqTableEntry.m_expire = Simulator::Now();
108 m_rreqDstMap[dst] = rreqTableEntry;
109 }
110 else
111 {
112 NS_LOG_LOGIC("Find the request table entry for " << dst
113 << ", increment the request count");
114 Ipv4Address dst = i->first;
115 RreqTableEntry rreqTableEntry = i->second;
116 rreqTableEntry.m_reqNo = rreqTableEntry.m_reqNo + 1;
117 rreqTableEntry.m_expire = Simulator::Now();
118 m_rreqDstMap[dst] = rreqTableEntry;
119 }
120}
121
122void
124{
125 NS_LOG_FUNCTION(this << dst);
126 std::map<Ipv4Address, RreqTableEntry>::const_iterator i = m_rreqDstMap.find(dst);
127 if (i == m_rreqDstMap.end())
128 {
129 NS_LOG_LOGIC("The request table entry not found");
130 }
131 else
132 {
133 // erase the request entry
134 m_rreqDstMap.erase(dst);
135 }
136}
137
140{
141 NS_LOG_FUNCTION(this << dst);
142 std::map<Ipv4Address, RreqTableEntry>::const_iterator i = m_rreqDstMap.find(dst);
143 if (i == m_rreqDstMap.end())
144 {
145 NS_LOG_LOGIC("Request table entry not found");
146 return 0;
147 }
148
149 RreqTableEntry rreqTableEntry = i->second;
150 return rreqTableEntry.m_reqNo;
151}
152
153// ----------------------------------------------------------------------------------------------------------
154/*
155 * This part takes care of the route request ID initialized from a specific source to one
156 * destination Essentially a counter
157 */
160{
161 NS_LOG_LOGIC("The size of id cache " << m_rreqIdCache.size());
162 std::map<Ipv4Address, uint32_t>::const_iterator i = m_rreqIdCache.find(dst);
163 if (i == m_rreqIdCache.end())
164 {
165 NS_LOG_LOGIC("No Request id for " << dst << " found, initialize it to 0");
166 m_rreqIdCache[dst] = 0;
167 return 0;
168 }
169
170 NS_LOG_LOGIC("Request id for " << dst << " found in the cache");
171 uint32_t rreqId = m_rreqIdCache[dst];
172 if (rreqId >= m_maxRreqId)
173 {
174 NS_LOG_DEBUG("The request id increase past the max value, " << m_maxRreqId
175 << " so reset it to 0");
176 rreqId = 0;
177 m_rreqIdCache[dst] = rreqId;
178 }
179 else
180 {
181 rreqId++;
182 m_rreqIdCache[dst] = rreqId;
183 }
184 NS_LOG_INFO("The Request id for " << dst << " is " << rreqId);
185 return rreqId;
186}
187
190{
191 return m_rreqIdCache.size();
192}
193
194// ----------------------------------------------------------------------------------------------------------
195/*
196 * This part takes care of black list which can save unidirectional link information
197 */
198
199void
201{
203 {
204 return;
205 }
207}
208
211{
212 PurgeNeighbor(); // purge the neighbor cache
213 for (std::vector<BlackList>::iterator i = m_blackList.begin(); i != m_blackList.end(); ++i)
214 {
215 if (i->m_neighborAddress == neighbor)
216 {
217 return &(*i);
218 }
219 }
220 return nullptr;
221}
222
223bool
225{
226 NS_LOG_LOGIC("Add neighbor address in blacklist " << m_blackList.size());
227 for (std::vector<BlackList>::iterator i = m_blackList.begin(); i != m_blackList.end(); i++)
228 {
229 if (i->m_neighborAddress == neighbor)
230 {
231 NS_LOG_DEBUG("Update the blacklist list timeout if found the blacklist entry");
232 i->m_expireTime = std::max(blacklistTimeout + Simulator::Now(), i->m_expireTime);
233 }
234 BlackList blackList(neighbor, blacklistTimeout + Simulator::Now());
235 m_blackList.push_back(blackList);
237 return true;
238 }
239 return false;
240}
241
242void
244{
245 /*
246 * Purge the expired blacklist entries
247 */
248 m_blackList.erase(remove_if(m_blackList.begin(), m_blackList.end(), IsExpired()),
249 m_blackList.end());
250}
251
252bool
254{
255 NS_LOG_FUNCTION(this << src << dst << id);
256 DsrReceivedRreqEntry rreqEntry;
257 rreqEntry.SetDestination(dst);
258 rreqEntry.SetIdentification(id);
259 std::list<DsrReceivedRreqEntry> receivedRreqEntryList;
260 /*
261 * this function will return false if the entry is not found, true if duplicate entry find
262 */
263 std::map<Ipv4Address, std::list<DsrReceivedRreqEntry>>::const_iterator i =
264 m_sourceRreqMap.find(src);
265 if (i == m_sourceRreqMap.end())
266 {
267 NS_LOG_LOGIC("The source request table entry for " << src << " not found");
268
269 receivedRreqEntryList.clear();
270 receivedRreqEntryList.push_back(rreqEntry);
271
272 m_sourceRreqMap[src] = receivedRreqEntryList;
273 return false;
274 }
275
276 NS_LOG_LOGIC("Find the request table entry for " << src << ", check if it is exact duplicate");
277 /*
278 * Drop the most aged packet when buffer reaches to max
279 */
280 receivedRreqEntryList = i->second;
281 if (receivedRreqEntryList.size() >= m_requestIdSize)
282 {
283 receivedRreqEntryList.pop_front();
284 }
285
286 // We loop the receive rreq entry to find duplicate
287 for (std::list<DsrReceivedRreqEntry>::const_iterator j = receivedRreqEntryList.begin();
288 j != receivedRreqEntryList.end();
289 ++j)
290 {
291 if (*j == rreqEntry)
292 {
293 return true;
294 }
295 }
298 receivedRreqEntryList.push_back(rreqEntry);
299 m_sourceRreqMap[src] = receivedRreqEntryList;
300 return false;
301}
302
303} // namespace dsr
304} // namespace ns3
#define max(a, b)
Definition: 80211b.c:42
Ipv4 addresses are stored in host order in this class.
Definition: ipv4-address.h:42
A base class which provides memory management and object aggregation.
Definition: object.h:89
static Time Now()
Return the current simulation virtual time.
Definition: simulator.cc:199
Simulation virtual time values and global simulation resolution.
Definition: nstime.h:105
a unique identifier for an interface.
Definition: type-id.h:59
TypeId SetParent(TypeId tid)
Set the parent TypeId.
Definition: type-id.cc:936
The request entry for intermediate nodes to check if they have received this request or not This is u...
void SetIdentification(uint16_t i)
Set identification.
void SetDestination(Ipv4Address d)
Set IPv4 address of the destination.
maintain list of DsrRreqTable entry
void FindAndUpdate(Ipv4Address dst)
Find the entry in the route request queue to see if already exists.
void RemoveLeastExpire()
Remove the least used entry.
std::map< Ipv4Address, std::list< DsrReceivedRreqEntry > > m_sourceRreqMap
The cache to ensure all the route request from unique source.
uint32_t CheckUniqueRreqId(Ipv4Address dst)
The following code generates new request id for each destination.
std::map< Ipv4Address, uint32_t > m_rreqIdCache
The id cache to ensure all the ids are unique, it is used when sending out route request.
LinkStates m_linkStates
The state of the unidirectional link.
void Invalidate()
set the unidirectional entry as QUESTIONABLE state
std::map< Ipv4Address, RreqTableEntry > m_rreqDstMap
The cache to save route request table entries indexed with destination address.
void RemoveRreqEntry(Ipv4Address dst)
Remove route request entry for dst.
std::vector< BlackList > m_blackList
The Black list.
uint32_t m_maxRreqId
The unique request id for any destination.
bool MarkLinkAsUnidirectional(Ipv4Address neighbor, Time blacklistTimeout)
Mark entry as unidirectional (e.g.
uint32_t m_requestTableSize
The request table size.
uint32_t GetRreqCnt(Ipv4Address dst)
Get the request count number for one destination address.
static TypeId GetTypeId()
Get the type ID.
uint32_t m_requestIdSize
The request source id size.
void PurgeNeighbor()
Remove all expired black list entries.
bool FindSourceEntry(Ipv4Address src, Ipv4Address dst, uint16_t id)
Find the source request entry in the route request queue, return false if not found.
BlackList * FindUnidirectional(Ipv4Address neighbor)
Verify if entry is unidirectional or not(e.g.
uint32_t GetRreqSize()
Get the request id size.
#define NS_LOG_COMPONENT_DEFINE(name)
Define a Log component with a specific name.
Definition: log.h:202
#define NS_LOG_DEBUG(msg)
Use NS_LOG to output a message of level LOG_DEBUG.
Definition: log.h:268
#define NS_LOG_LOGIC(msg)
Use NS_LOG to output a message of level LOG_LOGIC.
Definition: log.h:282
#define NS_LOG_FUNCTION_NOARGS()
Output the name of the function.
#define NS_LOG_FUNCTION(parameters)
If log level LOG_FUNCTION is enabled, this macro will output all input parameters separated by ",...
#define NS_LOG_INFO(msg)
Use NS_LOG to output a message of level LOG_INFO.
Definition: log.h:275
#define NS_OBJECT_ENSURE_REGISTERED(type)
Register an Object subclass with the TypeId system.
Definition: object-base.h:46
Time Seconds(double value)
Construct a Time in the indicated unit.
Definition: nstime.h:1336
@ PROBABLE
PROBABLE.
@ QUESTIONABLE
QUESTIONABLE.
Every class exported by the ns3 library is enclosed in the ns3 namespace.
BlackList description.
Check if the entry is expired or not.
The route request table entries.
Time m_expire
Expire time.
uint32_t m_reqNo
Route request number.