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 * SPDX-License-Identifier: GPL-2.0-only
5 *
6 * Author: Yufei Cheng <yfcheng@ittc.ku.edu>
7 *
8 * James P.G. Sterbenz <jpgs@ittc.ku.edu>, director
9 * ResiliNets Research Group https://resilinets.org/
10 * Information and Telecommunication Technology Center (ITTC)
11 * and Department of Electrical Engineering and Computer Science
12 * The University of Kansas Lawrence, KS USA.
13 *
14 * Work supported in part by NSF FIND (Future Internet Design) Program
15 * under grant CNS-0626918 (Postmodern Internet Architecture),
16 * NSF grant CNS-1050226 (Multilayer Network Resilience Analysis and Experimentation on GENI),
17 * US Department of Defense (DoD), and ITTC at The University of Kansas.
18 */
19
20#include "dsr-rreq-table.h"
21
22#include "ns3/log.h"
23
24#include <algorithm>
25#include <iostream>
26
27namespace ns3
28{
29
30NS_LOG_COMPONENT_DEFINE("DsrRreqTable");
31
32namespace dsr
33{
34
35NS_OBJECT_ENSURE_REGISTERED(DsrRreqTable);
36
37TypeId
39{
40 static TypeId tid = TypeId("ns3::dsr::DsrRreqTable")
42 .SetGroupName("Dsr")
43 .AddConstructor<DsrRreqTable>();
44 return tid;
45}
46
48 : m_linkStates(PROBABLE)
49{
50}
51
56
57void
59{
60 NS_LOG_FUNCTION(this);
61 Ipv4Address firstExpire;
62 Time max = Seconds(0.0);
63 for (auto i = m_rreqDstMap.begin(); i != m_rreqDstMap.end(); ++i)
64 {
65 Ipv4Address dst = i->first;
66 RreqTableEntry rreqTableEntry = i->second;
67 if (rreqTableEntry.m_expire > max)
68 {
69 max = rreqTableEntry.m_expire;
70 firstExpire = dst;
71 }
72 }
73 m_rreqDstMap.erase(firstExpire);
74}
75
76void
78{
79 NS_LOG_FUNCTION(this << dst);
80 auto i = m_rreqDstMap.find(dst);
81 if (i == m_rreqDstMap.end())
82 {
83 NS_LOG_LOGIC("The request table entry for " << dst << " not found");
84 /*
85 * Drop the most aged packet when buffer reaches to max
86 */
87 if (m_rreqDstMap.size() >= m_requestTableSize)
88 {
90 NS_LOG_INFO("The request table size after erase " << (uint32_t)m_rreqDstMap.size());
91 }
92 RreqTableEntry rreqTableEntry;
93 rreqTableEntry.m_reqNo = 1;
94 rreqTableEntry.m_expire = Simulator::Now();
95 m_rreqDstMap[dst] = rreqTableEntry;
96 }
97 else
98 {
99 NS_LOG_LOGIC("Find the request table entry for " << dst
100 << ", increment the request count");
101 Ipv4Address dst = i->first;
102 RreqTableEntry rreqTableEntry = i->second;
103 rreqTableEntry.m_reqNo = rreqTableEntry.m_reqNo + 1;
104 rreqTableEntry.m_expire = Simulator::Now();
105 m_rreqDstMap[dst] = rreqTableEntry;
106 }
107}
108
109void
111{
112 NS_LOG_FUNCTION(this << dst);
113 auto i = m_rreqDstMap.find(dst);
114 if (i == m_rreqDstMap.end())
115 {
116 NS_LOG_LOGIC("The request table entry not found");
117 }
118 else
119 {
120 // erase the request entry
121 m_rreqDstMap.erase(dst);
122 }
123}
124
127{
128 NS_LOG_FUNCTION(this << dst);
129 auto i = m_rreqDstMap.find(dst);
130 if (i == m_rreqDstMap.end())
131 {
132 NS_LOG_LOGIC("Request table entry not found");
133 return 0;
134 }
135
136 RreqTableEntry rreqTableEntry = i->second;
137 return rreqTableEntry.m_reqNo;
138}
139
140// ----------------------------------------------------------------------------------------------------------
141/*
142 * This part takes care of the route request ID initialized from a specific source to one
143 * destination Essentially a counter
144 */
147{
148 NS_LOG_LOGIC("The size of id cache " << m_rreqIdCache.size());
149 auto i = m_rreqIdCache.find(dst);
150 if (i == m_rreqIdCache.end())
151 {
152 NS_LOG_LOGIC("No Request id for " << dst << " found, initialize it to 0");
153 m_rreqIdCache[dst] = 0;
154 return 0;
155 }
156
157 NS_LOG_LOGIC("Request id for " << dst << " found in the cache");
158 uint32_t rreqId = m_rreqIdCache[dst];
159 if (rreqId >= m_maxRreqId)
160 {
161 NS_LOG_DEBUG("The request id increase past the max value, " << m_maxRreqId
162 << " so reset it to 0");
163 rreqId = 0;
164 m_rreqIdCache[dst] = rreqId;
165 }
166 else
167 {
168 rreqId++;
169 m_rreqIdCache[dst] = rreqId;
170 }
171 NS_LOG_INFO("The Request id for " << dst << " is " << rreqId);
172 return rreqId;
173}
174
177{
178 return m_rreqIdCache.size();
179}
180
181// ----------------------------------------------------------------------------------------------------------
182/*
183 * This part takes care of black list which can save unidirectional link information
184 */
185
186void
188{
190 {
191 return;
192 }
194}
195
198{
199 PurgeNeighbor(); // purge the neighbor cache
200 for (auto i = m_blackList.begin(); i != m_blackList.end(); ++i)
201 {
202 if (i->m_neighborAddress == neighbor)
203 {
204 return &(*i);
205 }
206 }
207 return nullptr;
208}
209
210bool
212{
213 NS_LOG_LOGIC("Add neighbor address in blacklist " << m_blackList.size());
214 for (auto i = m_blackList.begin(); i != m_blackList.end(); i++)
215 {
216 if (i->m_neighborAddress == neighbor)
217 {
218 NS_LOG_DEBUG("Update the blacklist list timeout if found the blacklist entry");
219 i->m_expireTime = std::max(blacklistTimeout + Simulator::Now(), i->m_expireTime);
220 }
221 BlackList blackList(neighbor, blacklistTimeout + Simulator::Now());
222 m_blackList.push_back(blackList);
224 return true;
225 }
226 return false;
227}
228
229void
231{
232 /*
233 * Purge the expired blacklist entries
234 */
235 m_blackList.erase(remove_if(m_blackList.begin(), m_blackList.end(), IsExpired()),
236 m_blackList.end());
237}
238
239bool
241{
242 NS_LOG_FUNCTION(this << src << dst << id);
243 DsrReceivedRreqEntry rreqEntry;
244 rreqEntry.SetDestination(dst);
245 rreqEntry.SetIdentification(id);
246 std::list<DsrReceivedRreqEntry> receivedRreqEntryList;
247 /*
248 * this function will return false if the entry is not found, true if duplicate entry find
249 */
250 auto i = m_sourceRreqMap.find(src);
251 if (i == m_sourceRreqMap.end())
252 {
253 NS_LOG_LOGIC("The source request table entry for " << src << " not found");
254
255 receivedRreqEntryList.clear(); /// Clear the received source request entry
256 receivedRreqEntryList.push_back(rreqEntry);
257
258 m_sourceRreqMap[src] = receivedRreqEntryList;
259 return false;
260 }
261
262 NS_LOG_LOGIC("Find the request table entry for " << src << ", check if it is exact duplicate");
263 /*
264 * Drop the most aged packet when buffer reaches to max
265 */
266 receivedRreqEntryList = i->second;
267 if (receivedRreqEntryList.size() >= m_requestIdSize)
268 {
269 receivedRreqEntryList.pop_front();
270 }
271
272 // We loop the receive rreq entry to find duplicate
273 for (auto j = receivedRreqEntryList.begin(); j != receivedRreqEntryList.end(); ++j)
274 {
275 if (*j == rreqEntry) /// Check if we have found one duplication entry or not
276 {
277 return true;
278 }
279 }
280 /// if this entry is not found, we need to save the entry in the cache, and then return
281 /// false for the check
282 receivedRreqEntryList.push_back(rreqEntry);
283 m_sourceRreqMap[src] = receivedRreqEntryList;
284 return false;
285}
286
287} // namespace dsr
288} // namespace ns3
Ipv4 addresses are stored in host order in this class.
A base class which provides memory management and object aggregation.
Definition object.h:78
static Time Now()
Return the current simulation virtual time.
Definition simulator.cc:197
Simulation virtual time values and global simulation resolution.
Definition nstime.h:94
a unique identifier for an interface.
Definition type-id.h:48
TypeId SetParent(TypeId tid)
Set the parent TypeId.
Definition type-id.cc:1001
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:191
#define NS_LOG_DEBUG(msg)
Use NS_LOG to output a message of level LOG_DEBUG.
Definition log.h:257
#define NS_LOG_LOGIC(msg)
Use NS_LOG to output a message of level LOG_LOGIC.
Definition log.h:271
#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:264
#define NS_OBJECT_ENSURE_REGISTERED(type)
Register an Object subclass with the TypeId system.
Definition object-base.h:35
Time Seconds(double value)
Construct a Time in the indicated unit.
Definition nstime.h:1308
@ 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.