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 
38 namespace ns3
39 {
40 
41 NS_LOG_COMPONENT_DEFINE("DsrRreqTable");
42 
43 namespace dsr
44 {
45 
46 NS_OBJECT_ENSURE_REGISTERED(DsrRreqTable);
47 
48 TypeId
50 {
51  static TypeId tid = TypeId("ns3::dsr::DsrRreqTable")
52  .SetParent<Object>()
53  .SetGroupName("Dsr")
54  .AddConstructor<DsrRreqTable>();
55  return tid;
56 }
57 
59  : m_linkStates(PROBABLE)
60 {
61 }
62 
64 {
66 }
67 
68 void
70 {
71  NS_LOG_FUNCTION(this);
72  Ipv4Address firstExpire;
73  Time max = Seconds(0.0);
74  for (auto i = m_rreqDstMap.begin(); i != m_rreqDstMap.end(); ++i)
75  {
76  Ipv4Address dst = i->first;
77  RreqTableEntry rreqTableEntry = i->second;
78  if (rreqTableEntry.m_expire > max)
79  {
80  max = rreqTableEntry.m_expire;
81  firstExpire = dst;
82  }
83  }
84  m_rreqDstMap.erase(firstExpire);
85 }
86 
87 void
89 {
90  NS_LOG_FUNCTION(this << dst);
91  auto i = m_rreqDstMap.find(dst);
92  if (i == m_rreqDstMap.end())
93  {
94  NS_LOG_LOGIC("The request table entry for " << dst << " not found");
95  /*
96  * Drop the most aged packet when buffer reaches to max
97  */
98  if (m_rreqDstMap.size() >= m_requestTableSize)
99  {
101  NS_LOG_INFO("The request table size after erase " << (uint32_t)m_rreqDstMap.size());
102  }
103  RreqTableEntry rreqTableEntry;
104  rreqTableEntry.m_reqNo = 1;
105  rreqTableEntry.m_expire = Simulator::Now();
106  m_rreqDstMap[dst] = rreqTableEntry;
107  }
108  else
109  {
110  NS_LOG_LOGIC("Find the request table entry for " << dst
111  << ", increment the request count");
112  Ipv4Address dst = i->first;
113  RreqTableEntry rreqTableEntry = i->second;
114  rreqTableEntry.m_reqNo = rreqTableEntry.m_reqNo + 1;
115  rreqTableEntry.m_expire = Simulator::Now();
116  m_rreqDstMap[dst] = rreqTableEntry;
117  }
118 }
119 
120 void
122 {
123  NS_LOG_FUNCTION(this << dst);
124  auto i = m_rreqDstMap.find(dst);
125  if (i == m_rreqDstMap.end())
126  {
127  NS_LOG_LOGIC("The request table entry not found");
128  }
129  else
130  {
131  // erase the request entry
132  m_rreqDstMap.erase(dst);
133  }
134 }
135 
136 uint32_t
138 {
139  NS_LOG_FUNCTION(this << dst);
140  auto i = m_rreqDstMap.find(dst);
141  if (i == m_rreqDstMap.end())
142  {
143  NS_LOG_LOGIC("Request table entry not found");
144  return 0;
145  }
146 
147  RreqTableEntry rreqTableEntry = i->second;
148  return rreqTableEntry.m_reqNo;
149 }
150 
151 // ----------------------------------------------------------------------------------------------------------
152 /*
153  * This part takes care of the route request ID initialized from a specific source to one
154  * destination Essentially a counter
155  */
156 uint32_t
158 {
159  NS_LOG_LOGIC("The size of id cache " << m_rreqIdCache.size());
160  auto i = m_rreqIdCache.find(dst);
161  if (i == m_rreqIdCache.end())
162  {
163  NS_LOG_LOGIC("No Request id for " << dst << " found, initialize it to 0");
164  m_rreqIdCache[dst] = 0;
165  return 0;
166  }
167 
168  NS_LOG_LOGIC("Request id for " << dst << " found in the cache");
169  uint32_t rreqId = m_rreqIdCache[dst];
170  if (rreqId >= m_maxRreqId)
171  {
172  NS_LOG_DEBUG("The request id increase past the max value, " << m_maxRreqId
173  << " so reset it to 0");
174  rreqId = 0;
175  m_rreqIdCache[dst] = rreqId;
176  }
177  else
178  {
179  rreqId++;
180  m_rreqIdCache[dst] = rreqId;
181  }
182  NS_LOG_INFO("The Request id for " << dst << " is " << rreqId);
183  return rreqId;
184 }
185 
186 uint32_t
188 {
189  return m_rreqIdCache.size();
190 }
191 
192 // ----------------------------------------------------------------------------------------------------------
193 /*
194  * This part takes care of black list which can save unidirectional link information
195  */
196 
197 void
199 {
200  if (m_linkStates == QUESTIONABLE)
201  {
202  return;
203  }
205 }
206 
207 BlackList*
209 {
210  PurgeNeighbor(); // purge the neighbor cache
211  for (auto i = m_blackList.begin(); i != m_blackList.end(); ++i)
212  {
213  if (i->m_neighborAddress == neighbor)
214  {
215  return &(*i);
216  }
217  }
218  return nullptr;
219 }
220 
221 bool
223 {
224  NS_LOG_LOGIC("Add neighbor address in blacklist " << m_blackList.size());
225  for (auto i = m_blackList.begin(); i != m_blackList.end(); i++)
226  {
227  if (i->m_neighborAddress == neighbor)
228  {
229  NS_LOG_DEBUG("Update the blacklist list timeout if found the blacklist entry");
230  i->m_expireTime = std::max(blacklistTimeout + Simulator::Now(), i->m_expireTime);
231  }
232  BlackList blackList(neighbor, blacklistTimeout + Simulator::Now());
233  m_blackList.push_back(blackList);
234  PurgeNeighbor();
235  return true;
236  }
237  return false;
238 }
239 
240 void
242 {
243  /*
244  * Purge the expired blacklist entries
245  */
246  m_blackList.erase(remove_if(m_blackList.begin(), m_blackList.end(), IsExpired()),
247  m_blackList.end());
248 }
249 
250 bool
252 {
253  NS_LOG_FUNCTION(this << src << dst << id);
254  DsrReceivedRreqEntry rreqEntry;
255  rreqEntry.SetDestination(dst);
256  rreqEntry.SetIdentification(id);
257  std::list<DsrReceivedRreqEntry> receivedRreqEntryList;
258  /*
259  * this function will return false if the entry is not found, true if duplicate entry find
260  */
261  auto i = m_sourceRreqMap.find(src);
262  if (i == m_sourceRreqMap.end())
263  {
264  NS_LOG_LOGIC("The source request table entry for " << src << " not found");
265 
266  receivedRreqEntryList.clear();
267  receivedRreqEntryList.push_back(rreqEntry);
268 
269  m_sourceRreqMap[src] = receivedRreqEntryList;
270  return false;
271  }
272 
273  NS_LOG_LOGIC("Find the request table entry for " << src << ", check if it is exact duplicate");
274  /*
275  * Drop the most aged packet when buffer reaches to max
276  */
277  receivedRreqEntryList = i->second;
278  if (receivedRreqEntryList.size() >= m_requestIdSize)
279  {
280  receivedRreqEntryList.pop_front();
281  }
282 
283  // We loop the receive rreq entry to find duplicate
284  for (auto j = receivedRreqEntryList.begin(); j != receivedRreqEntryList.end(); ++j)
285  {
286  if (*j == rreqEntry)
287  {
288  return true;
289  }
290  }
293  receivedRreqEntryList.push_back(rreqEntry);
294  m_sourceRreqMap[src] = receivedRreqEntryList;
295  return false;
296 }
297 
298 } // namespace dsr
299 } // 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:208
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:931
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:1326
@ 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.