A Discrete-Event Network Simulator
API
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Groups Pages
aodv-rtable.cc
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 NS_LOG_COMPONENT_DEFINE ("AodvRoutingTable");
36 
37 namespace ns3
38 {
39 namespace aodv
40 {
41 
42 /*
43  The Routing Table
44  */
45 
46 RoutingTableEntry::RoutingTableEntry (Ptr<NetDevice> dev, Ipv4Address dst, bool vSeqNo, uint32_t seqNo,
47  Ipv4InterfaceAddress iface, uint16_t hops, Ipv4Address nextHop,
48  Time lifetime, uint16_t channelNo) :
49  m_ackTimer (Timer::CANCEL_ON_DESTROY),
50  m_validSeqNo (vSeqNo), m_seqNo (seqNo), m_hops (hops),
51  m_lifeTime (lifetime + Simulator::Now ()), m_iface (iface), m_flag (VALID),
52  m_reqCount (0), m_blackListState (false), m_blackListTimeout (Simulator::Now ()),
53  m_channel (channelNo)
54 {
55  m_ipv4Route = Create<Ipv4Route> ();
57  m_ipv4Route->SetGateway (nextHop);
58  m_ipv4Route->SetSource (m_iface.GetLocal ());
60 }
61 
62 RoutingTableEntry::~RoutingTableEntry ()
63 {
64 }
65 
66 bool
68 {
69  NS_LOG_FUNCTION (this << id);
70  if (!LookupPrecursor (id))
71  {
72  m_precursorList.push_back (id);
73  return true;
74  }
75  else
76  return false;
77 }
78 
79 bool
81 {
82  NS_LOG_FUNCTION (this << id);
83  for (std::vector<Ipv4Address>::const_iterator i = m_precursorList.begin (); i
84  != m_precursorList.end (); ++i)
85  {
86  if (*i == id)
87  {
88  NS_LOG_LOGIC ("Precursor " << id << " found");
89  return true;
90  }
91  }
92  NS_LOG_LOGIC ("Precursor " << id << " not found");
93  return false;
94 }
95 
96 bool
98 {
99  NS_LOG_FUNCTION (this << id);
100  std::vector<Ipv4Address>::iterator i = std::remove (m_precursorList.begin (),
101  m_precursorList.end (), id);
102  if (i == m_precursorList.end ())
103  {
104  NS_LOG_LOGIC ("Precursor " << id << " not found");
105  return false;
106  }
107  else
108  {
109  NS_LOG_LOGIC ("Precursor " << id << " found");
110  m_precursorList.erase (i, m_precursorList.end ());
111  }
112  return true;
113 }
114 
115 void
117 {
118  NS_LOG_FUNCTION (this);
119  m_precursorList.clear ();
120 }
121 
122 bool
124 {
125  return m_precursorList.empty ();
126 }
127 
128 void
129 RoutingTableEntry::GetPrecursors (std::vector<Ipv4Address> & prec) const
130 {
131  NS_LOG_FUNCTION (this);
132  if (IsPrecursorListEmpty ())
133  return;
134  for (std::vector<Ipv4Address>::const_iterator i = m_precursorList.begin (); i
135  != m_precursorList.end (); ++i)
136  {
137  bool result = true;
138  for (std::vector<Ipv4Address>::const_iterator j = prec.begin (); j
139  != prec.end (); ++j)
140  {
141  if (*j == *i)
142  result = false;
143  }
144  if (result)
145  prec.push_back (*i);
146  }
147 }
148 
149 void
151 {
152  NS_LOG_FUNCTION (this << badLinkLifetime.GetSeconds ());
153  if (m_flag == INVALID)
154  return;
155  m_flag = INVALID;
156  m_reqCount = 0;
157  m_lifeTime = badLinkLifetime + Simulator::Now ();
158 }
159 
160 void
161 RoutingTableEntry::Print (Ptr<OutputStreamWrapper> stream) const
162 {
163  std::ostream* os = stream->GetStream ();
164  *os << m_ipv4Route->GetDestination () << "\t" << m_ipv4Route->GetGateway ()
165  << "\t" << m_iface.GetLocal () << "\t";
166  switch (m_flag)
167  {
168  case VALID:
169  {
170  *os << "UP";
171  break;
172  }
173  case INVALID:
174  {
175  *os << "DOWN";
176  break;
177  }
178  case IN_SEARCH:
179  {
180  *os << "IN_SEARCH";
181  break;
182  }
183  }
184  *os << "\t";
185  *os << std::setiosflags (std::ios::fixed) <<
186  std::setiosflags (std::ios::left) << std::setprecision (2) <<
187  std::setw (14) << (m_lifeTime - Simulator::Now ()).GetSeconds ();
188  *os << "\t" << m_hops << "\n";
189 }
190 
191 /*
192  The Routing Table
193  */
194 
196  m_badLinkLifetime (t)
197 {
198 }
199 
200 bool
202 {
203  NS_LOG_FUNCTION (this << id);
204  Purge ();
205  if (m_ipv4AddressEntry.empty ())
206  {
207  NS_LOG_LOGIC ("Route to " << id << " not found; m_ipv4AddressEntry is empty");
208  return false;
209  }
210  std::map<Ipv4Address, RoutingTableEntry>::const_iterator i =
211  m_ipv4AddressEntry.find (id);
212  if (i == m_ipv4AddressEntry.end ())
213  {
214  NS_LOG_LOGIC ("Route to " << id << " not found");
215  return false;
216  }
217  rt = i->second;
218  NS_LOG_LOGIC ("Route to " << id << " found");
219  return true;
220 }
221 
222 bool
224 {
225  NS_LOG_FUNCTION (this << id);
226  if (!LookupRoute (id, rt))
227  {
228  NS_LOG_LOGIC ("Route to " << id << " not found");
229  return false;
230  }
231  NS_LOG_LOGIC ("Route to " << id << " flag is " << ((rt.GetFlag () == VALID) ? "valid" : "not valid"));
232  return (rt.GetFlag () == VALID);
233 }
234 
235 bool
237 {
238  NS_LOG_FUNCTION (this << dst);
239  Purge ();
240  if (m_ipv4AddressEntry.erase (dst) != 0)
241  {
242  NS_LOG_LOGIC ("Route deletion to " << dst << " successful");
243  return true;
244  }
245  NS_LOG_LOGIC ("Route deletion to " << dst << " not successful");
246  return false;
247 }
248 
249 bool
251 {
252  NS_LOG_FUNCTION (this);
253  Purge ();
254  if (rt.GetFlag () != IN_SEARCH)
255  rt.SetRreqCnt (0);
256  std::pair<std::map<Ipv4Address, RoutingTableEntry>::iterator, bool> result =
257  m_ipv4AddressEntry.insert (std::make_pair (rt.GetDestination (), rt));
258  return result.second;
259 }
260 
261 bool
263 {
264  NS_LOG_FUNCTION (this);
265  std::map<Ipv4Address, RoutingTableEntry>::iterator i =
266  m_ipv4AddressEntry.find (rt.GetDestination ());
267  if (i == m_ipv4AddressEntry.end ())
268  {
269  NS_LOG_LOGIC ("Route update to " << rt.GetDestination () << " fails; not found");
270  return false;
271  }
272  i->second = rt;
273  if (i->second.GetFlag () != IN_SEARCH)
274  {
275  NS_LOG_LOGIC ("Route update to " << rt.GetDestination () << " set RreqCnt to 0");
276  i->second.SetRreqCnt (0);
277  }
278  return true;
279 }
280 
281 bool
283 {
284  NS_LOG_FUNCTION (this);
285  std::map<Ipv4Address, RoutingTableEntry>::iterator i =
286  m_ipv4AddressEntry.find (id);
287  if (i == m_ipv4AddressEntry.end ())
288  {
289  NS_LOG_LOGIC ("Route set entry state to " << id << " fails; not found");
290  return false;
291  }
292  i->second.SetFlag (state);
293  i->second.SetRreqCnt (0);
294  NS_LOG_LOGIC ("Route set entry state to " << id << ": new state is " << state);
295  return true;
296 }
297 
298 void
299 RoutingTable::GetListOfDestinationWithNextHop (Ipv4Address nextHop, std::map<Ipv4Address, uint32_t> & unreachable )
300 {
301  NS_LOG_FUNCTION (this);
302  Purge ();
303  unreachable.clear ();
304  for (std::map<Ipv4Address, RoutingTableEntry>::const_iterator i =
305  m_ipv4AddressEntry.begin (); i != m_ipv4AddressEntry.end (); ++i)
306  {
307  if (i->second.GetNextHop () == nextHop)
308  {
309  NS_LOG_LOGIC ("Unreachable insert " << i->first << " " << i->second.GetSeqNo ());
310  unreachable.insert (std::make_pair (i->first, i->second.GetSeqNo ()));
311  }
312  }
313 }
314 
315 void
316 RoutingTable::InvalidateRoutesWithDst (const std::map<Ipv4Address, uint32_t> & unreachable)
317 {
318  NS_LOG_FUNCTION (this);
319  Purge ();
320  for (std::map<Ipv4Address, RoutingTableEntry>::iterator i =
321  m_ipv4AddressEntry.begin (); i != m_ipv4AddressEntry.end (); ++i)
322  {
323  for (std::map<Ipv4Address, uint32_t>::const_iterator j =
324  unreachable.begin (); j != unreachable.end (); ++j)
325  {
326  if ((i->first == j->first) && (i->second.GetFlag () == VALID))
327  {
328  NS_LOG_LOGIC ("Invalidate route with destination address " << i->first);
329  i->second.Invalidate (m_badLinkLifetime);
330  }
331  }
332  }
333 }
334 
335 void
337 {
338  NS_LOG_FUNCTION (this);
339  if (m_ipv4AddressEntry.empty ())
340  return;
341  for (std::map<Ipv4Address, RoutingTableEntry>::iterator i =
342  m_ipv4AddressEntry.begin (); i != m_ipv4AddressEntry.end ();)
343  {
344  if (i->second.GetInterface () == iface)
345  {
346  std::map<Ipv4Address, RoutingTableEntry>::iterator tmp = i;
347  ++i;
348  m_ipv4AddressEntry.erase (tmp);
349  }
350  else
351  ++i;
352  }
353 }
354 
355 void
357 {
358  NS_LOG_FUNCTION (this);
359  if (m_ipv4AddressEntry.empty ())
360  return;
361  for (std::map<Ipv4Address, RoutingTableEntry>::iterator i =
362  m_ipv4AddressEntry.begin (); i != m_ipv4AddressEntry.end ();)
363  {
364  if (i->second.GetLifeTime () < Seconds (0))
365  {
366  if (i->second.GetFlag () == INVALID)
367  {
368  std::map<Ipv4Address, RoutingTableEntry>::iterator tmp = i;
369  ++i;
370  m_ipv4AddressEntry.erase (tmp);
371  }
372  else if (i->second.GetFlag () == VALID)
373  {
374  NS_LOG_LOGIC ("Invalidate route with destination address " << i->first);
375  i->second.Invalidate (m_badLinkLifetime);
376  ++i;
377  }
378  else
379  ++i;
380  }
381  else
382  {
383  ++i;
384  }
385  }
386 }
387 
388 void
389 RoutingTable::Purge (std::map<Ipv4Address, RoutingTableEntry> &table) const
390 {
391  NS_LOG_FUNCTION (this);
392  if (table.empty ())
393  return;
394  for (std::map<Ipv4Address, RoutingTableEntry>::iterator i =
395  table.begin (); i != table.end ();)
396  {
397  if (i->second.GetLifeTime () < Seconds (0))
398  {
399  if (i->second.GetFlag () == INVALID)
400  {
401  std::map<Ipv4Address, RoutingTableEntry>::iterator tmp = i;
402  ++i;
403  table.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  ++i;
413  }
414  else
415  {
416  ++i;
417  }
418  }
419 }
420 
421 bool
423 {
424  NS_LOG_FUNCTION (this << neighbor << blacklistTimeout.GetSeconds ());
425  std::map<Ipv4Address, RoutingTableEntry>::iterator i =
426  m_ipv4AddressEntry.find (neighbor);
427  if (i == m_ipv4AddressEntry.end ())
428  {
429  NS_LOG_LOGIC ("Mark link unidirectional to " << neighbor << " fails; not found");
430  return false;
431  }
432  i->second.SetUnidirectional (true);
433  i->second.SetBalcklistTimeout (blacklistTimeout);
434  i->second.SetRreqCnt (0);
435  NS_LOG_LOGIC ("Set link to " << neighbor << " to unidirectional");
436  return true;
437 }
438 
439 void
441 {
442  std::map<Ipv4Address, RoutingTableEntry> table = m_ipv4AddressEntry;
443  Purge (table);
444  *stream->GetStream () << "\nAODV Routing table\n"
445  << "Destination\tGateway\t\tInterface\tFlag\tExpire\t\tHops\n";
446  for (std::map<Ipv4Address, RoutingTableEntry>::const_iterator i =
447  table.begin (); i != table.end (); ++i)
448  {
449  i->second.Print (stream);
450  }
451  *stream->GetStream () << "\n";
452 }
453 
454 }
455 }
void InvalidateRoutesWithDst(std::map< Ipv4Address, uint32_t > const &unreachable)
Definition: aodv-rtable.cc:316
keep track of time unit.
Definition: nstime.h:149
bool MarkLinkAsUnidirectional(Ipv4Address neighbor, Time blacklistTimeout)
Definition: aodv-rtable.cc:422
smart pointer class similar to boost::intrusive_ptr
Definition: ptr.h:59
#define NS_LOG_FUNCTION(parameters)
Definition: log.h:311
Control the scheduling of simulation events.
Definition: simulator.h:58
bool LookupRoute(Ipv4Address dst, RoutingTableEntry &rt)
Definition: aodv-rtable.cc:201
a simple Timer class
Definition: timer.h:45
Routing table entry.
Definition: aodv-rtable.h:59
bool Update(RoutingTableEntry &rt)
Update routing table.
Definition: aodv-rtable.cc:262
#define NS_LOG_COMPONENT_DEFINE(name)
Definition: log.h:122
void GetPrecursors(std::vector< Ipv4Address > &prec) const
Definition: aodv-rtable.cc:129
void SetSource(Ipv4Address src)
Definition: ipv4-route.cc:49
bool InsertPrecursor(Ipv4Address id)
Definition: aodv-rtable.cc:67
double GetSeconds(void) const
Definition: nstime.h:262
void Print(Ptr< OutputStreamWrapper > stream) const
Print routing table.
Definition: aodv-rtable.cc:440
bool IsPrecursorListEmpty() const
Definition: aodv-rtable.cc:123
RouteFlags m_flag
Routing flags: valid, invalid or in search.
Definition: aodv-rtable.h:173
void DeleteAllRoutesFromInterface(Ipv4InterfaceAddress iface)
Delete all route from interface with address iface.
Definition: aodv-rtable.cc:336
bool SetEntryState(Ipv4Address dst, RouteFlags state)
Set routing table entry flags.
Definition: aodv-rtable.cc:282
bool LookupPrecursor(Ipv4Address id)
Definition: aodv-rtable.cc:80
void SetGateway(Ipv4Address gw)
Definition: ipv4-route.cc:63
uint8_t m_reqCount
Number of route requests.
Definition: aodv-rtable.h:180
Time m_badLinkLifetime
Deletion time for invalid routes.
Definition: aodv-rtable.h:256
bool DeletePrecursor(Ipv4Address id)
Delete precursor.
Definition: aodv-rtable.cc:97
Ptr< Ipv4Route > m_ipv4Route
Definition: aodv-rtable.h:169
std::vector< Ipv4Address > m_precursorList
List of precursors.
Definition: aodv-rtable.h:176
#define NS_LOG_LOGIC(msg)
Definition: log.h:334
void DeleteAllPrecursors()
Delete all precursors.
Definition: aodv-rtable.cc:116
Ipv4Address GetGateway(void) const
Definition: ipv4-route.cc:70
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:299
RoutingTableEntry(Ptr< NetDevice > dev=0, Ipv4Address dst=Ipv4Address(), bool vSeqNo=false, uint32_t m_seqNo=0, Ipv4InterfaceAddress iface=Ipv4InterfaceAddress(), uint16_t hops=0, Ipv4Address nextHop=Ipv4Address(), Time lifetime=Simulator::Now(), uint16_t channelNo=1)
c-to
Definition: aodv-rtable.cc:46
void Invalidate(Time badLinkLifetime)
Mark entry as "down" (i.e. disable it)
Definition: aodv-rtable.cc:150
static Time Now(void)
Definition: simulator.cc:179
void SetOutputDevice(Ptr< NetDevice > outputDevice)
Definition: ipv4-route.cc:77
Ipv4InterfaceAddress m_iface
Output interface address.
Definition: aodv-rtable.h:171
RoutingTable(Time t)
c-tor
Definition: aodv-rtable.cc:195
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:162
Ipv4Address GetDestination(void) const
Definition: ipv4-route.cc:42
Ipv4 addresses are stored in host order in this class.
Definition: ipv4-address.h:38
Time Seconds(double seconds)
create ns3::Time instances in units of seconds.
Definition: nstime.h:586
a class to store IPv4 address information on an interface
Time Now(void)
create an ns3::Time instance which contains the current simulation time.
Definition: simulator.cc:286
bool AddRoute(RoutingTableEntry &r)
Definition: aodv-rtable.cc:250
uint16_t m_hops
Hop Count (number of hops needed to reach destination)
Definition: aodv-rtable.h:155
bool LookupValidRoute(Ipv4Address dst, RoutingTableEntry &rt)
Lookup route in VALID state.
Definition: aodv-rtable.cc:223
bool DeleteRoute(Ipv4Address dst)
Definition: aodv-rtable.cc:236
void Purge()
Delete all outdated entries and invalidate valid entry if Lifetime is expired.
Definition: aodv-rtable.cc:356
std::ostream * GetStream(void)
void SetDestination(Ipv4Address dest)
Definition: ipv4-route.cc:35
RouteFlags
Route record states.
Definition: aodv-rtable.h:48