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