A Discrete-Event Network Simulator
API
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 else
149 {
150 RreqTableEntry rreqTableEntry = i->second;
151 return rreqTableEntry.m_reqNo;
152 }
153}
154
155// ----------------------------------------------------------------------------------------------------------
156/*
157 * This part takes care of the route request ID initialized from a specific source to one
158 * destination Essentially a counter
159 */
162{
163 NS_LOG_LOGIC("The size of id cache " << m_rreqIdCache.size());
164 std::map<Ipv4Address, uint32_t>::const_iterator i = m_rreqIdCache.find(dst);
165 if (i == m_rreqIdCache.end())
166 {
167 NS_LOG_LOGIC("No Request id for " << dst << " found, initialize it to 0");
168 m_rreqIdCache[dst] = 0;
169 return 0;
170 }
171 else
172 {
173 NS_LOG_LOGIC("Request id for " << dst << " found in the cache");
174 uint32_t rreqId = m_rreqIdCache[dst];
175 if (rreqId >= m_maxRreqId)
176 {
177 NS_LOG_DEBUG("The request id increase past the max value, " << m_maxRreqId
178 << " so reset it to 0");
179 rreqId = 0;
180 m_rreqIdCache[dst] = rreqId;
181 }
182 else
183 {
184 rreqId++;
185 m_rreqIdCache[dst] = rreqId;
186 }
187 NS_LOG_INFO("The Request id for " << dst << " is " << rreqId);
188 return rreqId;
189 }
190}
191
194{
195 return m_rreqIdCache.size();
196}
197
198// ----------------------------------------------------------------------------------------------------------
199/*
200 * This part takes care of black list which can save unidirectional link information
201 */
202
203void
205{
207 {
208 return;
209 }
211}
212
215{
216 PurgeNeighbor(); // purge the neighbor cache
217 for (std::vector<BlackList>::iterator i = m_blackList.begin(); i != m_blackList.end(); ++i)
218 {
219 if (i->m_neighborAddress == neighbor)
220 {
221 return &(*i);
222 }
223 }
224 return nullptr;
225}
226
227bool
229{
230 NS_LOG_LOGIC("Add neighbor address in blacklist " << m_blackList.size());
231 for (std::vector<BlackList>::iterator i = m_blackList.begin(); i != m_blackList.end(); i++)
232 {
233 if (i->m_neighborAddress == neighbor)
234 {
235 NS_LOG_DEBUG("Update the blacklist list timeout if found the blacklist entry");
236 i->m_expireTime = std::max(blacklistTimeout + Simulator::Now(), i->m_expireTime);
237 }
238 BlackList blackList(neighbor, blacklistTimeout + Simulator::Now());
239 m_blackList.push_back(blackList);
241 return true;
242 }
243 return false;
244}
245
246void
248{
249 /*
250 * Purge the expired blacklist entries
251 */
252 m_blackList.erase(remove_if(m_blackList.begin(), m_blackList.end(), IsExpired()),
253 m_blackList.end());
254}
255
256bool
258{
259 NS_LOG_FUNCTION(this << src << dst << id);
260 DsrReceivedRreqEntry rreqEntry;
261 rreqEntry.SetDestination(dst);
262 rreqEntry.SetIdentification(id);
263 std::list<DsrReceivedRreqEntry> receivedRreqEntryList;
264 /*
265 * this function will return false if the entry is not found, true if duplicate entry find
266 */
267 std::map<Ipv4Address, std::list<DsrReceivedRreqEntry>>::const_iterator i =
268 m_sourceRreqMap.find(src);
269 if (i == m_sourceRreqMap.end())
270 {
271 NS_LOG_LOGIC("The source request table entry for " << src << " not found");
272
273 receivedRreqEntryList.clear();
274 receivedRreqEntryList.push_back(rreqEntry);
275
276 m_sourceRreqMap[src] = receivedRreqEntryList;
277 return false;
278 }
279 else
280 {
281 NS_LOG_LOGIC("Find the request table entry for " << src
282 << ", check if it is exact duplicate");
283 /*
284 * Drop the most aged packet when buffer reaches to max
285 */
286 receivedRreqEntryList = i->second;
287 if (receivedRreqEntryList.size() >= m_requestIdSize)
288 {
289 receivedRreqEntryList.pop_front();
290 }
291 Ipv4Address src = i->first;
292 // We loop the receive rreq entry to find duplicate
293 for (std::list<DsrReceivedRreqEntry>::const_iterator j = receivedRreqEntryList.begin();
294 j != receivedRreqEntryList.end();
295 ++j)
296 {
297 if (*j == rreqEntry)
298 {
299 return true;
300 }
301 }
304 receivedRreqEntryList.push_back(rreqEntry);
305 m_sourceRreqMap[src] = receivedRreqEntryList;
306 return false;
307 }
308}
309
310} // namespace dsr
311} // namespace ns3
#define max(a, b)
Definition: 80211b.c:43
Ipv4 addresses are stored in host order in this class.
Definition: ipv4-address.h:43
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:60
TypeId SetParent(TypeId tid)
Set the parent TypeId.
Definition: type-id.cc:935
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:45
Time Seconds(double value)
Construct a Time in the indicated unit.
Definition: nstime.h:1338
@ 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.