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 https://resilinets.org/
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
37namespace ns3 {
38
39NS_LOG_COMPONENT_DEFINE ("DsrRreqTable");
40
41namespace dsr {
42
43NS_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
65void
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
85void
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
118void
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
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 */
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
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
201void
203{
205 {
206 return;
207 }
209}
210
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
226bool
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
245void
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
255bool
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
#define max(a, b)
Definition: 80211b.c:43
Ipv4 addresses are stored in host order in this class.
Definition: ipv4-address.h:41
A base class which provides memory management and object aggregation.
Definition: object.h:88
static Time Now(void)
Return the current simulation virtual time.
Definition: simulator.cc:195
Simulation virtual time values and global simulation resolution.
Definition: nstime.h:104
a unique identifier for an interface.
Definition: type-id.h:59
TypeId SetParent(TypeId tid)
Set the parent TypeId.
Definition: type-id.cc:922
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
void RemoveRreqEntry(Ipv4Address dst)
Remove route request entry for dst.
std::map< Ipv4Address, RreqTableEntry > m_rreqDstMap
The cache to save route request table entries indexed with destination address.
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:206
#define NS_LOG_DEBUG(msg)
Use NS_LOG to output a message of level LOG_DEBUG.
Definition: log.h:274
#define NS_LOG_LOGIC(msg)
Use NS_LOG to output a message of level LOG_LOGIC.
Definition: log.h:290
#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:282
#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:1245
@ 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.