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