A Discrete-Event Network Simulator
API
Loading...
Searching...
No Matches
aodv-rtable.cc
Go to the documentation of this file.
1/*
2 * Copyright (c) 2009 IITP RAS
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 * Based on
18 * NS-2 AODV model developed by the CMU/MONARCH group and optimized and
19 * tuned by Samir Das and Mahesh Marina, University of Cincinnati;
20 *
21 * AODV-UU implementation by Erik Nordström of Uppsala University
22 * https://web.archive.org/web/20100527072022/http://core.it.uu.se/core/index.php/AODV-UU
23 *
24 * Authors: Elena Buchatskaia <borovkovaes@iitp.ru>
25 * Pavel Boyko <boyko@iitp.ru>
26 */
27
28#include "aodv-rtable.h"
29
30#include "ns3/log.h"
31#include "ns3/simulator.h"
32
33#include <algorithm>
34#include <iomanip>
35
36namespace ns3
37{
38
39NS_LOG_COMPONENT_DEFINE("AodvRoutingTable");
40
41namespace aodv
42{
43
44/*
45 The Routing Table
46 */
47
49 Ipv4Address dst,
50 bool vSeqNo,
51 uint32_t seqNo,
53 uint16_t hops,
54 Ipv4Address nextHop,
55 Time lifetime)
56 : m_ackTimer(Timer::CANCEL_ON_DESTROY),
57 m_validSeqNo(vSeqNo),
58 m_seqNo(seqNo),
59 m_hops(hops),
60 m_lifeTime(lifetime + Simulator::Now()),
61 m_iface(iface),
62 m_flag(VALID),
63 m_reqCount(0),
64 m_blackListState(false),
65 m_blackListTimeout(Simulator::Now())
66{
67 m_ipv4Route = Create<Ipv4Route>();
68 m_ipv4Route->SetDestination(dst);
69 m_ipv4Route->SetGateway(nextHop);
70 m_ipv4Route->SetSource(m_iface.GetLocal());
71 m_ipv4Route->SetOutputDevice(dev);
72}
73
75{
76}
77
78bool
80{
81 NS_LOG_FUNCTION(this << id);
82 if (!LookupPrecursor(id))
83 {
84 m_precursorList.push_back(id);
85 return true;
86 }
87 else
88 {
89 return false;
90 }
91}
92
93bool
95{
96 NS_LOG_FUNCTION(this << id);
97 for (auto i = m_precursorList.begin(); i != m_precursorList.end(); ++i)
98 {
99 if (*i == id)
100 {
101 NS_LOG_LOGIC("Precursor " << id << " found");
102 return true;
103 }
104 }
105 NS_LOG_LOGIC("Precursor " << id << " not found");
106 return false;
107}
108
109bool
111{
112 NS_LOG_FUNCTION(this << id);
113 auto i = std::remove(m_precursorList.begin(), m_precursorList.end(), id);
114 if (i == m_precursorList.end())
115 {
116 NS_LOG_LOGIC("Precursor " << id << " not found");
117 return false;
118 }
119 else
120 {
121 NS_LOG_LOGIC("Precursor " << id << " found");
122 m_precursorList.erase(i, m_precursorList.end());
123 }
124 return true;
125}
126
127void
129{
130 NS_LOG_FUNCTION(this);
131 m_precursorList.clear();
132}
133
134bool
136{
137 return m_precursorList.empty();
138}
139
140void
141RoutingTableEntry::GetPrecursors(std::vector<Ipv4Address>& prec) const
142{
143 NS_LOG_FUNCTION(this);
145 {
146 return;
147 }
148 for (auto i = m_precursorList.begin(); i != m_precursorList.end(); ++i)
149 {
150 bool result = true;
151 for (auto j = prec.begin(); j != prec.end(); ++j)
152 {
153 if (*j == *i)
154 {
155 result = false;
156 break;
157 }
158 }
159 if (result)
160 {
161 prec.push_back(*i);
162 }
163 }
164}
165
166void
168{
169 NS_LOG_FUNCTION(this << badLinkLifetime.As(Time::S));
170 if (m_flag == INVALID)
171 {
172 return;
173 }
174 m_flag = INVALID;
175 m_reqCount = 0;
176 m_lifeTime = badLinkLifetime + Simulator::Now();
177}
178
179void
181{
182 std::ostream* os = stream->GetStream();
183 // Copy the current ostream state
184 std::ios oldState(nullptr);
185 oldState.copyfmt(*os);
186
187 *os << std::resetiosflags(std::ios::adjustfield) << std::setiosflags(std::ios::left);
188
189 std::ostringstream dest;
190 std::ostringstream gw;
191 std::ostringstream iface;
192 std::ostringstream expire;
193 dest << m_ipv4Route->GetDestination();
194 gw << m_ipv4Route->GetGateway();
195 iface << m_iface.GetLocal();
196 expire << std::setprecision(2) << (m_lifeTime - Simulator::Now()).As(unit);
197 *os << std::setw(16) << dest.str();
198 *os << std::setw(16) << gw.str();
199 *os << std::setw(16) << iface.str();
200 *os << std::setw(16);
201 switch (m_flag)
202 {
203 case VALID: {
204 *os << "UP";
205 break;
206 }
207 case INVALID: {
208 *os << "DOWN";
209 break;
210 }
211 case IN_SEARCH: {
212 *os << "IN_SEARCH";
213 break;
214 }
215 }
216
217 *os << std::setw(16) << expire.str();
218 *os << m_hops << std::endl;
219 // Restore the previous ostream state
220 (*os).copyfmt(oldState);
221}
222
223/*
224 The Routing Table
225 */
226
228 : m_badLinkLifetime(t)
229{
230}
231
232bool
234{
235 NS_LOG_FUNCTION(this << id);
236 Purge();
237 if (m_ipv4AddressEntry.empty())
238 {
239 NS_LOG_LOGIC("Route to " << id << " not found; m_ipv4AddressEntry is empty");
240 return false;
241 }
242 auto i = m_ipv4AddressEntry.find(id);
243 if (i == m_ipv4AddressEntry.end())
244 {
245 NS_LOG_LOGIC("Route to " << id << " not found");
246 return false;
247 }
248 rt = i->second;
249 NS_LOG_LOGIC("Route to " << id << " found");
250 return true;
251}
252
253bool
255{
256 NS_LOG_FUNCTION(this << id);
257 if (!LookupRoute(id, rt))
258 {
259 NS_LOG_LOGIC("Route to " << id << " not found");
260 return false;
261 }
262 NS_LOG_LOGIC("Route to " << id << " flag is "
263 << ((rt.GetFlag() == VALID) ? "valid" : "not valid"));
264 return (rt.GetFlag() == VALID);
265}
266
267bool
269{
270 NS_LOG_FUNCTION(this << dst);
271 Purge();
272 if (m_ipv4AddressEntry.erase(dst) != 0)
273 {
274 NS_LOG_LOGIC("Route deletion to " << dst << " successful");
275 return true;
276 }
277 NS_LOG_LOGIC("Route deletion to " << dst << " not successful");
278 return false;
279}
280
281bool
283{
284 NS_LOG_FUNCTION(this);
285 Purge();
286 if (rt.GetFlag() != IN_SEARCH)
287 {
288 rt.SetRreqCnt(0);
289 }
290 auto result = m_ipv4AddressEntry.insert(std::make_pair(rt.GetDestination(), rt));
291 return result.second;
292}
293
294bool
296{
297 NS_LOG_FUNCTION(this);
298 auto i = m_ipv4AddressEntry.find(rt.GetDestination());
299 if (i == m_ipv4AddressEntry.end())
300 {
301 NS_LOG_LOGIC("Route update to " << rt.GetDestination() << " fails; not found");
302 return false;
303 }
304 i->second = rt;
305 if (i->second.GetFlag() != IN_SEARCH)
306 {
307 NS_LOG_LOGIC("Route update to " << rt.GetDestination() << " set RreqCnt to 0");
308 i->second.SetRreqCnt(0);
309 }
310 return true;
311}
312
313bool
315{
316 NS_LOG_FUNCTION(this);
317 auto i = m_ipv4AddressEntry.find(id);
318 if (i == m_ipv4AddressEntry.end())
319 {
320 NS_LOG_LOGIC("Route set entry state to " << id << " fails; not found");
321 return false;
322 }
323 i->second.SetFlag(state);
324 i->second.SetRreqCnt(0);
325 NS_LOG_LOGIC("Route set entry state to " << id << ": new state is " << state);
326 return true;
327}
328
329void
331 std::map<Ipv4Address, uint32_t>& unreachable)
332{
333 NS_LOG_FUNCTION(this);
334 Purge();
335 unreachable.clear();
336 for (auto i = m_ipv4AddressEntry.begin(); i != m_ipv4AddressEntry.end(); ++i)
337 {
338 if (i->second.GetNextHop() == nextHop)
339 {
340 NS_LOG_LOGIC("Unreachable insert " << i->first << " " << i->second.GetSeqNo());
341 unreachable.insert(std::make_pair(i->first, i->second.GetSeqNo()));
342 }
343 }
344}
345
346void
347RoutingTable::InvalidateRoutesWithDst(const std::map<Ipv4Address, uint32_t>& unreachable)
348{
349 NS_LOG_FUNCTION(this);
350 Purge();
351 for (auto i = m_ipv4AddressEntry.begin(); i != m_ipv4AddressEntry.end(); ++i)
352 {
353 for (auto j = unreachable.begin(); j != unreachable.end(); ++j)
354 {
355 if ((i->first == j->first) && (i->second.GetFlag() == VALID))
356 {
357 NS_LOG_LOGIC("Invalidate route with destination address " << i->first);
358 i->second.Invalidate(m_badLinkLifetime);
359 }
360 }
361 }
362}
363
364void
366{
367 NS_LOG_FUNCTION(this);
368 if (m_ipv4AddressEntry.empty())
369 {
370 return;
371 }
372 for (auto i = m_ipv4AddressEntry.begin(); i != m_ipv4AddressEntry.end();)
373 {
374 if (i->second.GetInterface() == iface)
375 {
376 auto tmp = i;
377 ++i;
378 m_ipv4AddressEntry.erase(tmp);
379 }
380 else
381 {
382 ++i;
383 }
384 }
385}
386
387void
389{
390 NS_LOG_FUNCTION(this);
391 if (m_ipv4AddressEntry.empty())
392 {
393 return;
394 }
395 for (auto i = m_ipv4AddressEntry.begin(); i != m_ipv4AddressEntry.end();)
396 {
397 if (i->second.GetLifeTime() < Seconds(0))
398 {
399 if (i->second.GetFlag() == INVALID)
400 {
401 auto tmp = i;
402 ++i;
403 m_ipv4AddressEntry.erase(tmp);
404 }
405 else if (i->second.GetFlag() == VALID)
406 {
407 NS_LOG_LOGIC("Invalidate route with destination address " << i->first);
408 i->second.Invalidate(m_badLinkLifetime);
409 ++i;
410 }
411 else
412 {
413 ++i;
414 }
415 }
416 else
417 {
418 ++i;
419 }
420 }
421}
422
423void
424RoutingTable::Purge(std::map<Ipv4Address, RoutingTableEntry>& table) const
425{
426 NS_LOG_FUNCTION(this);
427 if (table.empty())
428 {
429 return;
430 }
431 for (auto i = table.begin(); i != table.end();)
432 {
433 if (i->second.GetLifeTime() < Seconds(0))
434 {
435 if (i->second.GetFlag() == INVALID)
436 {
437 auto tmp = i;
438 ++i;
439 table.erase(tmp);
440 }
441 else if (i->second.GetFlag() == VALID)
442 {
443 NS_LOG_LOGIC("Invalidate route with destination address " << i->first);
444 i->second.Invalidate(m_badLinkLifetime);
445 ++i;
446 }
447 else
448 {
449 ++i;
450 }
451 }
452 else
453 {
454 ++i;
455 }
456 }
457}
458
459bool
461{
462 NS_LOG_FUNCTION(this << neighbor << blacklistTimeout.As(Time::S));
463 auto i = m_ipv4AddressEntry.find(neighbor);
464 if (i == m_ipv4AddressEntry.end())
465 {
466 NS_LOG_LOGIC("Mark link unidirectional to " << neighbor << " fails; not found");
467 return false;
468 }
469 i->second.SetUnidirectional(true);
470 i->second.SetBlacklistTimeout(blacklistTimeout);
471 i->second.SetRreqCnt(0);
472 NS_LOG_LOGIC("Set link to " << neighbor << " to unidirectional");
473 return true;
474}
475
476void
477RoutingTable::Print(Ptr<OutputStreamWrapper> stream, Time::Unit unit /* = Time::S */) const
478{
479 std::map<Ipv4Address, RoutingTableEntry> table = m_ipv4AddressEntry;
480 Purge(table);
481 std::ostream* os = stream->GetStream();
482 // Copy the current ostream state
483 std::ios oldState(nullptr);
484 oldState.copyfmt(*os);
485
486 *os << std::resetiosflags(std::ios::adjustfield) << std::setiosflags(std::ios::left);
487 *os << "\nAODV Routing table\n";
488 *os << std::setw(16) << "Destination";
489 *os << std::setw(16) << "Gateway";
490 *os << std::setw(16) << "Interface";
491 *os << std::setw(16) << "Flag";
492 *os << std::setw(16) << "Expire";
493 *os << "Hops" << std::endl;
494 for (auto i = table.begin(); i != table.end(); ++i)
495 {
496 i->second.Print(stream, unit);
497 }
498 *stream->GetStream() << "\n";
499}
500
501} // namespace aodv
502} // namespace ns3
Ipv4 addresses are stored in host order in this class.
Definition: ipv4-address.h:42
a class to store IPv4 address information on an interface
Ipv4Address GetLocal() const
Get the local address.
Smart pointer class similar to boost::intrusive_ptr.
Definition: ptr.h:77
Control the scheduling of simulation events.
Definition: simulator.h:68
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
TimeWithUnit As(const Unit unit=Time::AUTO) const
Attach a unit to a Time, to facilitate output in a specific unit.
Definition: time.cc:415
Unit
The unit to use to interpret a number representing time.
Definition: nstime.h:111
@ S
second
Definition: nstime.h:116
A simple virtual Timer class.
Definition: timer.h:74
Routing table entry.
Definition: aodv-rtable.h:62
void DeleteAllPrecursors()
Delete all precursors.
Definition: aodv-rtable.cc:128
Ipv4InterfaceAddress m_iface
Output interface address.
Definition: aodv-rtable.h:403
std::vector< Ipv4Address > m_precursorList
List of precursors.
Definition: aodv-rtable.h:408
bool IsPrecursorListEmpty() const
Check that precursor list is empty.
Definition: aodv-rtable.cc:135
bool InsertPrecursor(Ipv4Address id)
Insert precursor in precursor list if it doesn't yet exist in the list.
Definition: aodv-rtable.cc:79
void Print(Ptr< OutputStreamWrapper > stream, Time::Unit unit=Time::S) const
Print packet to trace file.
Definition: aodv-rtable.cc:180
void GetPrecursors(std::vector< Ipv4Address > &prec) const
Inserts precursors in output parameter prec if they do not yet exist in vector.
Definition: aodv-rtable.cc:141
RouteFlags GetFlag() const
Get the route flags.
Definition: aodv-rtable.h:294
uint16_t m_hops
Hop Count (number of hops needed to reach destination)
Definition: aodv-rtable.h:387
Ptr< Ipv4Route > m_ipv4Route
Ip route, include.
Definition: aodv-rtable.h:401
bool DeletePrecursor(Ipv4Address id)
Delete precursor.
Definition: aodv-rtable.cc:110
void SetRreqCnt(uint8_t n)
Set the RREQ count.
Definition: aodv-rtable.h:303
void Invalidate(Time badLinkLifetime)
Mark entry as "down" (i.e.
Definition: aodv-rtable.cc:167
bool LookupPrecursor(Ipv4Address id)
Lookup precursor by address.
Definition: aodv-rtable.cc:94
Ipv4Address GetDestination() const
Get destination address function.
Definition: aodv-rtable.h:132
~RoutingTableEntry()
Definition: aodv-rtable.cc:74
RoutingTableEntry(Ptr< NetDevice > dev=nullptr, Ipv4Address dst=Ipv4Address(), bool vSeqNo=false, uint32_t seqNo=0, Ipv4InterfaceAddress iface=Ipv4InterfaceAddress(), uint16_t hops=0, Ipv4Address nextHop=Ipv4Address(), Time lifetime=Simulator::Now())
constructor
Definition: aodv-rtable.cc:48
Time m_lifeTime
Expiration or deletion time of the route Lifetime field in the routing table plays dual role: for an ...
Definition: aodv-rtable.h:394
RouteFlags m_flag
Routing flags: valid, invalid or in search.
Definition: aodv-rtable.h:405
uint8_t m_reqCount
Number of route requests.
Definition: aodv-rtable.h:412
void GetListOfDestinationWithNextHop(Ipv4Address nextHop, std::map< Ipv4Address, uint32_t > &unreachable)
Lookup routing entries with next hop Address dst and not empty list of precursors.
Definition: aodv-rtable.cc:330
bool LookupValidRoute(Ipv4Address dst, RoutingTableEntry &rt)
Lookup route in VALID state.
Definition: aodv-rtable.cc:254
void Purge()
Delete all outdated entries and invalidate valid entry if Lifetime is expired.
Definition: aodv-rtable.cc:388
bool Update(RoutingTableEntry &rt)
Update routing table.
Definition: aodv-rtable.cc:295
Time m_badLinkLifetime
Deletion time for invalid routes.
Definition: aodv-rtable.h:543
bool AddRoute(RoutingTableEntry &r)
Add routing table entry if it doesn't yet exist in routing table.
Definition: aodv-rtable.cc:282
void Print(Ptr< OutputStreamWrapper > stream, Time::Unit unit=Time::S) const
Print routing table.
Definition: aodv-rtable.cc:477
RoutingTable(Time t)
constructor
Definition: aodv-rtable.cc:227
bool LookupRoute(Ipv4Address dst, RoutingTableEntry &rt)
Lookup routing table entry with destination address dst.
Definition: aodv-rtable.cc:233
bool SetEntryState(Ipv4Address dst, RouteFlags state)
Set routing table entry flags.
Definition: aodv-rtable.cc:314
void DeleteAllRoutesFromInterface(Ipv4InterfaceAddress iface)
Delete all route from interface with address iface.
Definition: aodv-rtable.cc:365
void InvalidateRoutesWithDst(const std::map< Ipv4Address, uint32_t > &unreachable)
Update routing entries with this destination as follows:
Definition: aodv-rtable.cc:347
std::map< Ipv4Address, RoutingTableEntry > m_ipv4AddressEntry
The routing table.
Definition: aodv-rtable.h:541
bool MarkLinkAsUnidirectional(Ipv4Address neighbor, Time blacklistTimeout)
Mark entry as unidirectional (e.g.
Definition: aodv-rtable.cc:460
bool DeleteRoute(Ipv4Address dst)
Delete routing table entry with destination address dst, if it exists.
Definition: aodv-rtable.cc:268
RouteFlags
Route record states.
Definition: aodv-rtable.h:51
@ INVALID
INVALID.
Definition: aodv-rtable.h:53
@ IN_SEARCH
IN_SEARCH.
Definition: aodv-rtable.h:54
@ VALID
VALID.
Definition: aodv-rtable.h:52
#define NS_LOG_COMPONENT_DEFINE(name)
Define a Log component with a specific name.
Definition: log.h:202
#define NS_LOG_LOGIC(msg)
Use NS_LOG to output a message of level LOG_LOGIC.
Definition: log.h:282
#define NS_LOG_FUNCTION(parameters)
If log level LOG_FUNCTION is enabled, this macro will output all input parameters separated by ",...
Time Now()
create an ns3::Time instance which contains the current simulation time.
Definition: simulator.cc:305
Time Seconds(double value)
Construct a Time in the indicated unit.
Definition: nstime.h:1326
Every class exported by the ns3 library is enclosed in the ns3 namespace.