A Discrete-Event Network Simulator
API
Loading...
Searching...
No Matches
dsr-rcache.cc
Go to the documentation of this file.
1/*
2 * Copyright (c) 2011 Yufei Cheng
3 *
4 * SPDX-License-Identifier: GPL-2.0-only
5 *
6 * Author: Yufei Cheng <yfcheng@ittc.ku.edu>
7 * Song Luan <lsuper@mail.ustc.edu.cn> (Implemented Link Cache using Dijsktra
8 * algorithm)
9 *
10 * James P.G. Sterbenz <jpgs@ittc.ku.edu>, director
11 * ResiliNets Research Group https://resilinets.org/
12 * Information and Telecommunication Technology Center (ITTC)
13 * and Department of Electrical Engineering and Computer Science
14 * The University of Kansas Lawrence, KS USA.
15 *
16 * Work supported in part by NSF FIND (Future Internet Design) Program
17 * under grant CNS-0626918 (Postmodern Internet Architecture),
18 * NSF grant CNS-1050226 (Multilayer Network Resilience Analysis and Experimentation on GENI),
19 * US Department of Defense (DoD), and ITTC at The University of Kansas.
20 */
21
22#include "dsr-rcache.h"
23
24#include "ns3/address-utils.h"
25#include "ns3/ipv4-route.h"
26#include "ns3/log.h"
27#include "ns3/packet.h"
28#include "ns3/simulator.h"
29#include "ns3/socket.h"
30#include "ns3/wifi-mac-header.h"
31
32#include <algorithm>
33#include <cmath>
34#include <functional>
35#include <iomanip>
36#include <iostream>
37#include <list>
38#include <map>
39#include <vector>
40
41namespace ns3
42{
43
44NS_LOG_COMPONENT_DEFINE("DsrRouteCache");
45
46namespace dsr
47{
48
49bool
51{
52 // compare based on both with hop count considered priority
53 return (a.GetVector().size() < b.GetVector().size()) ||
54 ((a.GetVector().size() == b.GetVector().size()) &&
55 (a.GetExpireTime() > b.GetExpireTime()));
56}
57
58bool
60{
61 // compare based on hops
62 return a.GetVector().size() < b.GetVector().size();
63}
64
65bool
67{
68 // compare based on expire time
69 return a.GetExpireTime() > b.GetExpireTime();
70}
71
72void
74{
75 NS_LOG_DEBUG(m_low << "----" << m_high);
76}
77
79 : m_nodeStability(nodeStab + Simulator::Now())
80{
81}
82
86
88 : m_linkStability(linkStab + Simulator::Now())
89{
90}
91
95
96void
98{
99 NS_LOG_LOGIC("LifeTime: " << GetLinkStability().As(Time::S));
100}
101
102typedef std::list<DsrRouteCacheEntry>::value_type route_pair;
103
105 : m_ackTimer(Timer::CANCEL_ON_DESTROY),
106 m_dst(dst),
107 m_path(ip),
108 m_expire(exp + Simulator::Now()),
109 m_reqCount(0),
110 m_blackListState(false),
111 m_blackListTimeout(Simulator::Now())
112{
113}
114
118
119void
121{
122 m_reqCount = 0;
123 m_expire = badLinkLifetime + Simulator::Now();
124}
125
126void
127DsrRouteCacheEntry::Print(std::ostream& os) const
128{
129 os << m_dst << "\t" << (m_expire - Simulator::Now()).As(Time::S) << "\t";
130}
131
133
134TypeId
136{
137 static TypeId tid = TypeId("ns3::dsr::DsrRouteCache")
138 .SetParent<Object>()
139 .SetGroupName("Dsr")
140 .AddConstructor<DsrRouteCache>();
141 return tid;
142}
143
145 : m_vector(0),
146 m_maxEntriesEachDst(3),
147 m_isLinkCache(false),
148 m_ntimer(Timer::CANCEL_ON_DESTROY),
149 m_delay(MilliSeconds(100))
150{
151 /*
152 * The timer to set layer 2 notification, not fully supported by ns3 yet
153 */
156}
157
159{
161 // clear the route cache when done
162 m_sortedRoutes.clear();
163}
164
165void
166DsrRouteCache::RemoveLastEntry(std::list<DsrRouteCacheEntry>& rtVector)
167{
168 NS_LOG_FUNCTION(this);
169 // Release the last entry of route list
170 rtVector.pop_back();
171}
172
173bool
175{
176 NS_LOG_FUNCTION(this << dst);
177 auto i = m_sortedRoutes.find(dst);
178 if (i == m_sortedRoutes.end())
179 {
180 NS_LOG_LOGIC("Failed to find the route entry for the destination " << dst);
181 return false;
182 }
183 else
184 {
185 std::list<DsrRouteCacheEntry> rtVector = i->second;
186 DsrRouteCacheEntry successEntry = rtVector.front();
187 successEntry.SetExpireTime(RouteCacheTimeout);
188 rtVector.pop_front();
189 rtVector.push_back(successEntry);
190 rtVector.sort(CompareRoutesExpire); // sort the route vector first
191 m_sortedRoutes.erase(dst); // erase the entry first
192 /*
193 * Save the new route cache along with the destination address in map
194 */
195 auto result = m_sortedRoutes.insert(std::make_pair(dst, rtVector));
196 return result.second;
197 }
198 return false;
199}
200
201bool
203{
204 NS_LOG_FUNCTION(this << id);
205 if (IsLinkCache())
206 {
207 return LookupRoute_Link(id, rt);
208 }
209
210 Purge(); // Purge first to remove expired entries
211 if (m_sortedRoutes.empty())
212 {
213 NS_LOG_LOGIC("Route to " << id << " not found; m_sortedRoutes is empty");
214 return false;
215 }
216 auto i = m_sortedRoutes.find(id);
217 if (i == m_sortedRoutes.end())
218 {
219 NS_LOG_LOGIC("No Direct Route to " << id << " found");
220 for (auto j = m_sortedRoutes.begin(); j != m_sortedRoutes.end(); ++j)
221 {
222 std::list<DsrRouteCacheEntry> rtVector =
223 j->second; // The route cache vector linked with destination address
224 /*
225 * Loop through the possibly multiple routes within the route vector
226 */
227 for (auto k = rtVector.begin(); k != rtVector.end(); ++k)
228 {
229 // return the first route in the route vector
232
233 for (auto l = routeVector.begin(); l != routeVector.end(); ++l)
234 {
235 changeVector.push_back(*l);
236
237 if (*l == id)
238 {
239 break;
240 }
241 }
242 /*
243 * When the changed vector is smaller in size and larger than 1, which means we
244 * have found a route with the destination address we are looking for
245 */
246 if ((changeVector.size() < routeVector.size()) && (changeVector.size() > 1))
247 {
248 DsrRouteCacheEntry changeEntry; // Create the route entry
249 changeEntry.SetVector(changeVector);
250 changeEntry.SetDestination(id);
251 // Use the expire time from original route entry
252 changeEntry.SetExpireTime(k->GetExpireTime());
253 // We need to add new route entry here
254 std::list<DsrRouteCacheEntry> newVector;
255 newVector.push_back(changeEntry);
256 newVector.sort(CompareRoutesExpire); // sort the route vector first
257 m_sortedRoutes[id] =
258 newVector; // Only get the first sub route and add it in route cache
259 NS_LOG_INFO("We have a sub-route to " << id << " add it in route cache");
260 }
261 }
262 }
263 }
264 NS_LOG_INFO("Here we check the route cache again after updated the sub routes");
265 auto m = m_sortedRoutes.find(id);
266 if (m == m_sortedRoutes.end())
267 {
268 NS_LOG_LOGIC("No updated route till last time");
269 return false;
270 }
271 /*
272 * We have a direct route to the destination address
273 */
274 std::list<DsrRouteCacheEntry> rtVector = m->second;
275 rt = rtVector.front(); // use the first entry in the route vector
276 NS_LOG_LOGIC("Route to " << id << " with route size " << rtVector.size());
277 return true;
278}
279
280void
282{
283 NS_LOG_FUNCTION(this << type);
284 if (type == "LinkCache")
285 {
286 m_isLinkCache = true;
287 }
288 else if (type == "PathCache")
289 {
290 m_isLinkCache = false;
291 }
292 else
293 {
294 m_isLinkCache = true; // use link cache as default
295 NS_LOG_INFO("Error Cache Type");
296 }
297}
298
299bool
305
306void
308{
309 NS_LOG_FUNCTION(this << source);
310 /**
311 * \brief The following are initialize-single-source
312 */
313 // @d shortest-path estimate
314 std::map<Ipv4Address, uint32_t> d;
315 // @pre preceding node
316 std::map<Ipv4Address, Ipv4Address> pre;
317 for (auto i = m_netGraph.begin(); i != m_netGraph.end(); ++i)
318 {
319 if (i->second.find(source) != i->second.end())
320 {
321 d[i->first] = i->second[source];
322 pre[i->first] = source;
323 }
324 else
325 {
326 d[i->first] = MAXWEIGHT;
327 pre[i->first] = Ipv4Address("255.255.255.255");
328 }
329 }
330 d[source] = 0;
331 /**
332 * \brief The following is the core of Dijkstra algorithm
333 */
334 // the node set which shortest distance has been calculated, if true calculated
335 std::map<Ipv4Address, bool> s;
336 double temp = MAXWEIGHT;
337 Ipv4Address tempip("255.255.255.255");
338 for (uint32_t i = 0; i < m_netGraph.size(); i++)
339 {
340 temp = MAXWEIGHT;
341 for (auto j = d.begin(); j != d.end(); ++j)
342 {
343 Ipv4Address ip = j->first;
344 if (s.find(ip) == s.end())
345 {
346 /*
347 * \brief The following are for comparison
348 */
349 if (j->second <= temp)
350 {
351 temp = j->second;
352 tempip = ip;
353 }
354 }
355 }
356 if (!tempip.IsBroadcast())
357 {
358 s[tempip] = true;
359 for (auto k = m_netGraph[tempip].begin(); k != m_netGraph[tempip].end(); ++k)
360 {
361 if (s.find(k->first) == s.end() && d[k->first] > d[tempip] + k->second)
362 {
363 d[k->first] = d[tempip] + k->second;
364 pre[k->first] = tempip;
365 }
366 /*
367 * Selects the shortest-length route that has the longest expected lifetime
368 * (highest minimum timeout of any link in the route)
369 * For the computation overhead and complexity
370 * Here I just implement kind of greedy strategy to select link with the longest
371 * expected lifetime when there is two options
372 */
373 else if (d[k->first] == d[tempip] + k->second)
374 {
375 auto oldlink = m_linkCache.find(Link(k->first, pre[k->first]));
376 auto newlink = m_linkCache.find(Link(k->first, tempip));
377 if (oldlink != m_linkCache.end() && newlink != m_linkCache.end())
378 {
379 if (oldlink->second.GetLinkStability() < newlink->second.GetLinkStability())
380 {
381 NS_LOG_INFO("Select the link with longest expected lifetime");
382 d[k->first] = d[tempip] + k->second;
383 pre[k->first] = tempip;
384 }
385 }
386 else
387 {
388 NS_LOG_INFO("Link Stability Info Corrupt");
389 }
390 }
391 }
392 }
393 }
394 // clean the best route table
396 for (auto i = pre.begin(); i != pre.end(); ++i)
397 {
398 // loop for all vertices
400 Ipv4Address iptemp = i->first;
401
402 if (!i->second.IsBroadcast() && iptemp != source)
403 {
404 while (iptemp != source)
405 {
406 route.push_back(iptemp);
407 iptemp = pre[iptemp];
408 }
409 route.push_back(source);
410 // Reverse the route
411 DsrRouteCacheEntry::IP_VECTOR reverseroute(route.rbegin(), route.rend());
412 NS_LOG_LOGIC("Add newly calculated best routes");
413 PrintVector(reverseroute);
414 m_bestRoutesTable_link[i->first] = reverseroute;
415 }
416 }
417}
418
419bool
421{
422 NS_LOG_FUNCTION(this << id);
423 /// We need to purge the link node cache
425 auto i = m_bestRoutesTable_link.find(id);
426 if (i == m_bestRoutesTable_link.end())
427 {
428 NS_LOG_INFO("No route find to " << id);
429 return false;
430 }
431
432 if (i->second.size() < 2)
433 {
434 NS_LOG_LOGIC("Route to " << id << " error");
435 return false;
436 }
437
438 DsrRouteCacheEntry newEntry; // Create the route entry
439 newEntry.SetVector(i->second);
440 newEntry.SetDestination(id);
442 NS_LOG_INFO("Route to " << id << " found with the length " << i->second.size());
443 rt = newEntry;
444 std::vector<Ipv4Address> path = rt.GetVector();
445 PrintVector(path);
446 return true;
447}
448
449void
451{
452 NS_LOG_FUNCTION(this);
453 for (auto i = m_linkCache.begin(); i != m_linkCache.end();)
454 {
455 NS_LOG_DEBUG("The link stability " << i->second.GetLinkStability().As(Time::S));
456 auto itmp = i;
457 if (i->second.GetLinkStability() <= Seconds(0))
458 {
459 ++i;
460 m_linkCache.erase(itmp);
461 }
462 else
463 {
464 ++i;
465 }
466 }
467 /// may need to remove them after verify
468 for (auto i = m_nodeCache.begin(); i != m_nodeCache.end();)
469 {
470 NS_LOG_DEBUG("The node stability " << i->second.GetNodeStability().As(Time::S));
471 auto itmp = i;
472 if (i->second.GetNodeStability() <= Seconds(0))
473 {
474 ++i;
475 m_nodeCache.erase(itmp);
476 }
477 else
478 {
479 ++i;
480 }
481 }
482}
483
484void
486{
487 NS_LOG_FUNCTION(this);
488 m_netGraph.clear();
489 for (auto i = m_linkCache.begin(); i != m_linkCache.end(); ++i)
490 {
491 // Here the weight is set as 1
492 /// \todo May need to set different weight for different link here later
493 uint32_t weight = 1;
494 m_netGraph[i->first.m_low][i->first.m_high] = weight;
495 m_netGraph[i->first.m_high][i->first.m_low] = weight;
496 }
497}
498
499bool
501{
502 NS_LOG_FUNCTION(this << node);
503 auto i = m_nodeCache.find(node);
504 if (i == m_nodeCache.end())
505 {
506 NS_LOG_INFO("The initial stability " << m_initStability.As(Time::S));
508 m_nodeCache[node] = ns;
509 return false;
510 }
511 else
512 {
513 /// \todo get rid of the debug here
514 NS_LOG_INFO("The node stability " << i->second.GetNodeStability().As(Time::S));
515 NS_LOG_INFO("The stability here "
516 << Time(i->second.GetNodeStability() * m_stabilityIncrFactor).As(Time::S));
517 DsrNodeStab ns(Time(i->second.GetNodeStability() * m_stabilityIncrFactor));
518 m_nodeCache[node] = ns;
519 return true;
520 }
521 return false;
522}
523
524bool
526{
527 NS_LOG_FUNCTION(this << node);
528 auto i = m_nodeCache.find(node);
529 if (i == m_nodeCache.end())
530 {
532 m_nodeCache[node] = ns;
533 return false;
534 }
535 else
536 {
537 /// \todo remove it here
538 NS_LOG_INFO("The stability here " << i->second.GetNodeStability().As(Time::S));
539 NS_LOG_INFO("The stability here "
540 << Time(i->second.GetNodeStability() / m_stabilityDecrFactor).As(Time::S));
541 DsrNodeStab ns(Time(i->second.GetNodeStability() / m_stabilityDecrFactor));
542 m_nodeCache[node] = ns;
543 return true;
544 }
545 return false;
546}
547
548bool
550{
551 NS_LOG_FUNCTION(this << source);
552 NS_LOG_LOGIC("Use Link Cache");
553 /// Purge the link node cache first
555 for (uint32_t i = 0; i < nodelist.size() - 1; i++)
556 {
557 DsrNodeStab ns; /// This is the node stability
559
560 if (m_nodeCache.find(nodelist[i]) == m_nodeCache.end())
561 {
562 m_nodeCache[nodelist[i]] = ns;
563 }
564 if (m_nodeCache.find(nodelist[i + 1]) == m_nodeCache.end())
565 {
566 m_nodeCache[nodelist[i + 1]] = ns;
567 }
568 Link link(nodelist[i], nodelist[i + 1]); /// Link represent the one link for the route
569 DsrLinkStab stab; /// Link stability
571 /// Set the link stability as the smallest node stability
572 if (m_nodeCache[nodelist[i]].GetNodeStability() <
573 m_nodeCache[nodelist[i + 1]].GetNodeStability())
574 {
575 stab.SetLinkStability(m_nodeCache[nodelist[i]].GetNodeStability());
576 }
577 else
578 {
579 stab.SetLinkStability(m_nodeCache[nodelist[i + 1]].GetNodeStability());
580 }
581 if (stab.GetLinkStability() < m_minLifeTime)
582 {
583 NS_LOG_LOGIC("Stability: " << stab.GetLinkStability().As(Time::S));
584 /// Set the link stability as the m)minLifeTime, default is 1 second
586 }
587 m_linkCache[link] = stab;
588 NS_LOG_DEBUG("Add a new link");
589 link.Print();
590 NS_LOG_DEBUG("Link Info");
591 stab.Print();
592 }
594 RebuildBestRouteTable(source);
595 return true;
596}
597
598void
600{
601 NS_LOG_FUNCTION(this);
602 /// Purge the link node cache first
604 if (rt.size() < 2)
605 {
606 NS_LOG_INFO("The route is too short");
607 return;
608 }
609 for (auto i = rt.begin(); i != rt.end() - 1; ++i)
610 {
611 Link link(*i, *(i + 1));
612 if (m_linkCache.find(link) != m_linkCache.end())
613 {
614 if (m_linkCache[link].GetLinkStability() < m_useExtends)
615 {
616 m_linkCache[link].SetLinkStability(m_useExtends);
617 /// \todo remove after debug
618 NS_LOG_INFO("The time of the link "
619 << m_linkCache[link].GetLinkStability().As(Time::S));
620 }
621 }
622 else
623 {
624 NS_LOG_INFO("We cannot find a link in cache");
625 }
626 }
627 /// Increase the stability of the node cache
628 for (auto i = rt.begin(); i != rt.end(); ++i)
629 {
630 if (m_nodeCache.find(*i) != m_nodeCache.end())
631 {
632 NS_LOG_LOGIC("Increase the stability");
633 if (m_nodeCache[*i].GetNodeStability() <= m_initStability)
634 {
635 IncStability(*i);
636 }
637 else
638 {
639 NS_LOG_INFO("The node stability has already been increased");
640 }
641 }
642 }
643}
644
645bool
647{
648 NS_LOG_FUNCTION(this);
649 Purge();
650 std::list<DsrRouteCacheEntry> rtVector; // Declare the route cache entry vector
651 Ipv4Address dst = rt.GetDestination();
652 std::vector<Ipv4Address> route = rt.GetVector();
653
654 NS_LOG_DEBUG("The route destination we have " << dst);
655 auto i = m_sortedRoutes.find(dst);
656
657 if (i == m_sortedRoutes.end())
658 {
659 rtVector.push_back(rt);
660 m_sortedRoutes.erase(dst); // Erase the route entries for dst first
661 /**
662 * Save the new route cache along with the destination address in map
663 */
664 auto result = m_sortedRoutes.insert(std::make_pair(dst, rtVector));
665 return result.second;
666 }
667
668 rtVector = i->second;
669 NS_LOG_DEBUG("The existing route size " << rtVector.size() << " for destination address "
670 << dst);
671 /**
672 * \brief Drop the most aged packet when buffer reaches to max
673 */
674 if (rtVector.size() >= m_maxEntriesEachDst)
675 {
676 RemoveLastEntry(rtVector); // Drop the last entry for the sorted route cache, the route
677 // has already been sorted
678 }
679
680 if (FindSameRoute(rt, rtVector))
681 {
683 "Find same vector, the FindSameRoute function will update the route expire time");
684 return true;
685 }
686 else
687 {
688 // Check if the expire time for the new route has expired or not
689 if (rt.GetExpireTime() > Time(0))
690 {
691 rtVector.push_back(rt);
692 // This sort function will sort the route cache entries based on the size of route
693 // in each of the route entries
694 rtVector.sort(CompareRoutesExpire);
695 NS_LOG_DEBUG("The first time" << rtVector.front().GetExpireTime().As(Time::S)
696 << " The second time "
697 << rtVector.back().GetExpireTime().As(Time::S));
698 NS_LOG_DEBUG("The first hop" << rtVector.front().GetVector().size()
699 << " The second hop "
700 << rtVector.back().GetVector().size());
701 m_sortedRoutes.erase(dst); // erase the route entries for dst first
702 /**
703 * Save the new route cache along with the destination address in map
704 */
705 auto result = m_sortedRoutes.insert(std::make_pair(dst, rtVector));
706 return result.second;
707 }
708 else
709 {
710 NS_LOG_INFO("The newly found route is already expired");
711 }
712 }
713
714 return false;
715}
716
717bool
718DsrRouteCache::FindSameRoute(DsrRouteCacheEntry& rt, std::list<DsrRouteCacheEntry>& rtVector)
719{
720 NS_LOG_FUNCTION(this);
721 for (auto i = rtVector.begin(); i != rtVector.end(); ++i)
722 {
723 // return the first route in the route vector
726
727 if (routeVector == newVector)
728 {
729 NS_LOG_DEBUG("Found same routes in the route cache with the vector size "
730 << rt.GetDestination() << " " << rtVector.size());
731 NS_LOG_DEBUG("The new route expire time " << rt.GetExpireTime().As(Time::S)
732 << " the original expire time "
733 << i->GetExpireTime().As(Time::S));
734 if (rt.GetExpireTime() > i->GetExpireTime())
735 {
736 i->SetExpireTime(rt.GetExpireTime());
737 }
738 m_sortedRoutes.erase(rt.GetDestination()); // erase the entry first
739 rtVector.sort(CompareRoutesExpire); // sort the route vector first
740 /*
741 * Save the new route cache along with the destination address in map
742 */
743 auto result = m_sortedRoutes.insert(std::make_pair(rt.GetDestination(), rtVector));
744 return result.second;
745 }
746 }
747 return false;
748}
749
750bool
752{
753 NS_LOG_FUNCTION(this << dst);
754 Purge(); // purge the route cache first to remove timeout entries
755 if (m_sortedRoutes.erase(dst) != 0)
756 {
757 NS_LOG_LOGIC("Route deletion to " << dst << " successful");
758 return true;
759 }
760 NS_LOG_LOGIC("Route deletion to " << dst << " not successful");
761 return false;
762}
763
764void
766 Ipv4Address unreachNode,
767 Ipv4Address node)
768{
769 NS_LOG_FUNCTION(this << errorSrc << unreachNode << node);
770 if (IsLinkCache())
771 {
772 // Purge the link node cache first
774 /*
775 * The following are for cleaning the broken link in link cache
776 * We basically remove the link between errorSrc and unreachNode
777 */
778 Link link1(errorSrc, unreachNode);
779 Link link2(unreachNode, errorSrc);
780 // erase the two kind of links to make sure the link is removed from the link cache
781 NS_LOG_DEBUG("Erase the route");
782 m_linkCache.erase(link1);
783 /// \todo get rid of this one
784 NS_LOG_DEBUG("The link cache size " << m_linkCache.size());
785 m_linkCache.erase(link2);
786 NS_LOG_DEBUG("The link cache size " << m_linkCache.size());
787
788 auto i = m_nodeCache.find(errorSrc);
789 if (i == m_nodeCache.end())
790 {
791 NS_LOG_LOGIC("Update the node stability unsuccessfully");
792 }
793 else
794 {
795 DecStability(i->first);
796 }
797 i = m_nodeCache.find(unreachNode);
798 if (i == m_nodeCache.end())
799 {
800 NS_LOG_LOGIC("Update the node stability unsuccessfully");
801 }
802 else
803 {
804 DecStability(i->first);
805 }
808 }
809 else
810 {
811 /*
812 * the following are for cleaning the broken link in pathcache
813 *
814 */
815 Purge();
816 if (m_sortedRoutes.empty())
817 {
818 return;
819 }
820 /*
821 * Loop all the routes saved in the route cache
822 */
823 for (auto j = m_sortedRoutes.begin(); j != m_sortedRoutes.end();)
824 {
825 auto jtmp = j;
826 Ipv4Address address = j->first;
827 std::list<DsrRouteCacheEntry> rtVector = j->second;
828 /*
829 * Loop all the routes for a single destination
830 */
831 for (auto k = rtVector.begin(); k != rtVector.end();)
832 {
833 // return the first route in the route vector
836 /*
837 * Loop the ip addresses within a single route entry
838 */
839 for (auto i = routeVector.begin(); i != routeVector.end(); ++i)
840 {
841 if (*i != errorSrc)
842 {
843 changeVector.push_back(*i);
844 }
845 else
846 {
847 changeVector.push_back(*i);
848
849 if (*(i + 1) == unreachNode)
850 {
851 break;
852 }
853 }
854 }
855 /*
856 * Verify if need to remove some affected links
857 */
858 if (changeVector.size() == routeVector.size())
859 {
860 NS_LOG_DEBUG("The route does not contain the broken link");
861 ++k;
862 }
863 else if ((changeVector.size() < routeVector.size()) && (changeVector.size() > 1))
864 {
865 NS_LOG_DEBUG("sub route " << m_subRoute);
866 if (m_subRoute)
867 {
868 Time expire = k->GetExpireTime();
869 /*
870 * Remove the route first
871 */
872 k = rtVector.erase(k);
873 DsrRouteCacheEntry changeEntry;
874 changeEntry.SetVector(changeVector);
875 Ipv4Address destination = changeVector.back();
876 NS_LOG_DEBUG("The destination of the newly formed route "
877 << destination << " and the size of the route "
878 << changeVector.size());
879 changeEntry.SetDestination(destination);
880 changeEntry.SetExpireTime(
881 expire); // Initialize the timeout value to the one it has
882 rtVector.push_back(changeEntry); // Add the route entry to the route list
883 NS_LOG_DEBUG("We have a sub-route to " << destination);
884 }
885 else
886 {
887 /*
888 * Remove the route
889 */
890 k = rtVector.erase(k);
891 }
892 }
893 else
894 {
895 NS_LOG_LOGIC("Cut route unsuccessful and erase the route");
896 /*
897 * Remove the route
898 */
899 k = rtVector.erase(k);
900 }
901 }
902 ++j;
903 if (!IsLinkCache())
904 {
905 m_sortedRoutes.erase(jtmp);
906 }
907 if (!rtVector.empty())
908 {
909 /*
910 * Save the new route cache along with the destination address in map
911 */
912 rtVector.sort(CompareRoutesExpire);
913 m_sortedRoutes[address] = rtVector;
914 }
915 else
916 {
917 NS_LOG_DEBUG("There is no route left for that destination " << address);
918 }
919 }
920 }
921}
922
923void
924DsrRouteCache::PrintVector(std::vector<Ipv4Address>& vec)
925{
926 NS_LOG_FUNCTION(this);
927 /*
928 * Check elements in a route vector, used when one wants to check the IP addresses saved in
929 */
930 if (vec.empty())
931 {
932 NS_LOG_DEBUG("The vector is empty");
933 }
934 else
935 {
936 NS_LOG_DEBUG("Print all the elements in a vector");
937 for (auto i = vec.begin(); i != vec.end(); ++i)
938 {
939 NS_LOG_DEBUG("The ip address " << *i);
940 }
941 }
942}
943
944void
945DsrRouteCache::PrintRouteVector(std::list<DsrRouteCacheEntry> route)
946{
947 NS_LOG_FUNCTION(this);
948 for (auto i = route.begin(); i != route.end(); i++)
949 {
950 std::vector<Ipv4Address> path = i->GetVector();
951 NS_LOG_INFO("Route NO. ");
952 PrintVector(path);
953 }
954}
955
956void
958{
959 NS_LOG_FUNCTION(this);
960 // Trying to purge the route cache
961 if (m_sortedRoutes.empty())
962 {
963 NS_LOG_DEBUG("The route cache is empty");
964 return;
965 }
966 for (auto i = m_sortedRoutes.begin(); i != m_sortedRoutes.end();)
967 {
968 // Loop of route cache entry with the route size
969 auto itmp = i;
970 /*
971 * The route cache entry vector
972 */
973 Ipv4Address dst = i->first;
974 std::list<DsrRouteCacheEntry> rtVector = i->second;
975 NS_LOG_DEBUG("The route vector size of 1 " << dst << " " << rtVector.size());
976 if (!rtVector.empty())
977 {
978 for (auto j = rtVector.begin(); j != rtVector.end();)
979 {
980 NS_LOG_DEBUG("The expire time of every entry with expire time "
981 << j->GetExpireTime());
982 /*
983 * First verify if the route has expired or not
984 */
985 if (j->GetExpireTime() <= Seconds(0))
986 {
987 /*
988 * When the expire time has passed, erase the certain route
989 */
990 NS_LOG_DEBUG("Erase the expired route for " << dst << " with expire time "
991 << j->GetExpireTime());
992 j = rtVector.erase(j);
993 }
994 else
995 {
996 ++j;
997 }
998 }
999 NS_LOG_DEBUG("The route vector size of 2 " << dst << " " << rtVector.size());
1000 if (!rtVector.empty())
1001 {
1002 ++i;
1003 m_sortedRoutes.erase(itmp); // erase the entry first
1004 /*
1005 * Save the new route cache along with the destination address in map
1006 */
1007 m_sortedRoutes.insert(std::make_pair(dst, rtVector));
1008 }
1009 else
1010 {
1011 ++i;
1012 m_sortedRoutes.erase(itmp);
1013 }
1014 }
1015 else
1016 {
1017 ++i;
1018 m_sortedRoutes.erase(itmp);
1019 }
1020 }
1021}
1022
1023void
1024DsrRouteCache::Print(std::ostream& os)
1025{
1026 NS_LOG_FUNCTION(this);
1027 Purge();
1028 os << "\nDSR Route Cache\n"
1029 << "Destination\tGateway\t\tInterface\tFlag\tExpire\tHops\n";
1030 for (auto i = m_routeEntryVector.begin(); i != m_routeEntryVector.end(); ++i)
1031 {
1032 i->Print(os);
1033 }
1034 os << "\n";
1035}
1036
1037// ----------------------------------------------------------------------------------------------------------
1038/**
1039 * This part of code maintains an Acknowledgment id cache for next hop and remove duplicate ids
1040 */
1041uint16_t
1043{
1044 NS_LOG_FUNCTION(this);
1045 auto i = m_ackIdCache.find(nextHop);
1046 if (i == m_ackIdCache.end())
1047 {
1048 NS_LOG_LOGIC("No Ack id for " << nextHop
1049 << " found and use id 1 for the first network ack id");
1050 m_ackIdCache[nextHop] = 1;
1051 return 1;
1052 }
1053
1054 uint16_t ackId = m_ackIdCache[nextHop];
1055 NS_LOG_LOGIC("Ack id for " << nextHop << " found in the cache has value " << ackId);
1056 ackId++;
1057 m_ackIdCache[nextHop] = ackId;
1058 return ackId;
1059}
1060
1061uint16_t
1063{
1064 return m_ackIdCache.size();
1065}
1066
1067// ----------------------------------------------------------------------------------------------------------
1068/**
1069 * This part maintains a neighbor list to handle unidirectional links and link-layer acks
1070 */
1071bool
1073{
1074 NS_LOG_FUNCTION(this);
1075 PurgeMac(); // purge the mac cache
1076 for (auto i = m_nb.begin(); i != m_nb.end(); ++i)
1077 {
1078 if (i->m_neighborAddress == addr)
1079 {
1080 return true;
1081 }
1082 }
1083 return false;
1084}
1085
1086Time
1088{
1089 NS_LOG_FUNCTION(this);
1090 PurgeMac();
1091 for (auto i = m_nb.begin(); i != m_nb.end(); ++i)
1092 {
1093 if (i->m_neighborAddress == addr)
1094 {
1095 return (i->m_expireTime - Simulator::Now());
1096 }
1097 }
1098 return Seconds(0);
1099}
1100
1101void
1102DsrRouteCache::UpdateNeighbor(std::vector<Ipv4Address> nodeList, Time expire)
1103{
1104 NS_LOG_FUNCTION(this);
1105 for (auto i = m_nb.begin(); i != m_nb.end(); ++i)
1106 {
1107 for (auto j = nodeList.begin(); j != nodeList.end(); ++j)
1108 {
1109 if (i->m_neighborAddress == (*j))
1110 {
1111 i->m_expireTime = std::max(expire + Simulator::Now(), i->m_expireTime);
1112 if (i->m_hardwareAddress == Mac48Address())
1113 {
1114 i->m_hardwareAddress = LookupMacAddress(i->m_neighborAddress);
1115 }
1116 return;
1117 }
1118 }
1119 }
1120
1121 Ipv4Address addr;
1122 NS_LOG_LOGIC("Open link to " << addr);
1123 Neighbor neighbor(addr, LookupMacAddress(addr), expire + Simulator::Now());
1124 m_nb.push_back(neighbor);
1125 PurgeMac();
1126}
1127
1128void
1129DsrRouteCache::AddNeighbor(std::vector<Ipv4Address> nodeList, Ipv4Address ownAddress, Time expire)
1130{
1131 NS_LOG_LOGIC("Add neighbor number " << nodeList.size());
1132 for (auto j = nodeList.begin(); j != nodeList.end();)
1133 {
1134 Ipv4Address addr = *j;
1135 if (addr == ownAddress)
1136 {
1137 j = nodeList.erase(j);
1138 NS_LOG_DEBUG("The node list size " << nodeList.size());
1139 }
1140 else
1141 {
1142 ++j;
1143 }
1144 Neighbor neighbor(addr, LookupMacAddress(addr), expire + Simulator::Now());
1145 m_nb.push_back(neighbor);
1146 PurgeMac();
1147 }
1148}
1149
1150/// CloseNeighbor structure
1152{
1153 /**
1154 * Check if the entry is expired
1155 *
1156 * \param nb DsrRouteCache::Neighbor entry
1157 * \return true if expired or closed, false otherwise
1158 */
1160 {
1161 return ((nb.m_expireTime < Simulator::Now()) || nb.close);
1162 }
1163};
1164
1165void
1167{
1168 if (m_nb.empty())
1169 {
1170 return;
1171 }
1172
1173 CloseNeighbor pred;
1174 if (!m_handleLinkFailure.IsNull())
1175 {
1176 for (auto j = m_nb.begin(); j != m_nb.end(); ++j)
1177 {
1178 if (pred(*j))
1179 {
1180 NS_LOG_LOGIC("Close link to " << j->m_neighborAddress);
1181 /// \todo disable temporarily
1182 // m_handleLinkFailure (j->m_neighborAddress);
1183 }
1184 }
1185 }
1186 m_nb.erase(std::remove_if(m_nb.begin(), m_nb.end(), pred), m_nb.end());
1187 m_ntimer.Cancel();
1189}
1190
1191void
1197
1198void
1200{
1201 m_arp.push_back(a);
1202}
1203
1204void
1206{
1207 m_arp.erase(std::remove(m_arp.begin(), m_arp.end(), a), m_arp.end());
1208}
1209
1212{
1213 Mac48Address hwaddr;
1214 for (auto i = m_arp.begin(); i != m_arp.end(); ++i)
1215 {
1216 ArpCache::Entry* entry = (*i)->Lookup(addr);
1217 if (entry != nullptr && (entry->IsAlive() || entry->IsPermanent()) && !entry->IsExpired())
1218 {
1219 hwaddr = Mac48Address::ConvertFrom(entry->GetMacAddress());
1220 break;
1221 }
1222 }
1223 return hwaddr;
1224}
1225
1226void
1228{
1229 Mac48Address addr = hdr.GetAddr1();
1230
1231 for (auto i = m_nb.begin(); i != m_nb.end(); ++i)
1232 {
1233 if (i->m_hardwareAddress == addr)
1234 {
1235 i->close = true;
1236 }
1237 }
1238 PurgeMac();
1239}
1240} // namespace dsr
1241} // namespace ns3
A record that that holds information about an ArpCache entry.
Definition arp-cache.h:173
bool IsAlive()
Definition arp-cache.cc:386
Address GetMacAddress() const
Definition arp-cache.cc:488
bool IsExpired() const
Definition arp-cache.cc:535
bool IsPermanent()
Definition arp-cache.cc:400
Ipv4 addresses are stored in host order in this class.
bool IsBroadcast() const
an EUI-48 address
static Mac48Address ConvertFrom(const Address &address)
A base class which provides memory management and object aggregation.
Definition object.h:78
Smart pointer class similar to boost::intrusive_ptr.
Control the scheduling of simulation events.
Definition simulator.h:57
static Time Now()
Return the current simulation virtual time.
Definition simulator.cc:197
Simulation virtual time values and global simulation resolution.
Definition nstime.h:94
TimeWithUnit As(const Unit unit=Time::AUTO) const
Attach a unit to a Time, to facilitate output in a specific unit.
Definition time.cc:404
@ S
second
Definition nstime.h:105
A simple virtual Timer class.
Definition timer.h:67
void SetDelay(const Time &delay)
Definition timer.cc:65
void SetFunction(FN fn)
Definition timer.h:268
void Cancel()
Cancel the currently-running event if there is one.
Definition timer.cc:97
void Schedule()
Schedule a new event using the currently-configured delay, function, and arguments.
Definition timer.cc:151
a unique identifier for an interface.
Definition type-id.h:48
TypeId SetParent(TypeId tid)
Set the parent TypeId.
Definition type-id.cc:1001
Implements the IEEE 802.11 MAC header.
Mac48Address GetAddr1() const
Return the address in the Address 1 field.
DsrNodeStab class (DSR node stability)
Definition dsr-rcache.h:181
void SetNodeStability(Time nodeStab)
Set node stability.
Definition dsr-rcache.h:195
DsrNodeStab(Time nodeStab=Simulator::Now())
Constructor.
Definition dsr-rcache.cc:78
DsrRouteCacheEntry class for entries in the route cache.
Definition dsr-rcache.h:218
IP_VECTOR GetVector() const
Get the IP vector.
Definition dsr-rcache.h:298
void SetDestination(Ipv4Address d)
Set destination address.
Definition dsr-rcache.h:289
Time m_expire
Expire time for queue entry.
Definition dsr-rcache.h:350
DsrRouteCacheEntry(IP_VECTOR const &ip=IP_VECTOR(), Ipv4Address dst=Ipv4Address(), Time exp=Simulator::Now())
Constructor.
Ipv4Address m_dst
The destination Ip address.
Definition dsr-rcache.h:348
uint8_t m_reqCount
Number of route requests.
Definition dsr-rcache.h:352
Ipv4Address GetDestination() const
Get destination address.
Definition dsr-rcache.h:280
virtual ~DsrRouteCacheEntry()
void Invalidate(Time badLinkLifetime)
Mark entry as "down" (i.e.
void Print(std::ostream &os) const
Print necessary fields.
std::vector< Ipv4Address > IP_VECTOR
Define the vector to hold Ip address.
Definition dsr-rcache.h:220
Time GetExpireTime() const
Get expire time.
Definition dsr-rcache.h:325
void SetExpireTime(Time exp)
Set expire time.
Definition dsr-rcache.h:316
void SetVector(IP_VECTOR v)
Sets the IP vector.
Definition dsr-rcache.h:307
DSR route request queue Since DSR is an on demand routing we queue requests while looking for route.
Definition dsr-rcache.h:365
std::map< Ipv4Address, std::map< Ipv4Address, uint32_t > > m_netGraph
Current network graph state for this node, double is weight, which is calculated by the node informat...
Definition dsr-rcache.h:793
uint32_t m_stabilityDecrFactor
stability decrease factor
Definition dsr-rcache.h:761
std::list< DsrRouteCacheEntry::IP_VECTOR > routeVector
Define the vector of route entries.
Definition dsr-rcache.h:387
static TypeId GetTypeId()
Get the type ID.
void PurgeLinkNode()
Purge from the cache if the stability time expired.
Callback< void, Ipv4Address, uint8_t > m_handleLinkFailure
The following code handles link-layer acks.
Definition dsr-rcache.h:866
std::map< Link, DsrLinkStab > m_linkCache
The data structure to store link info.
Definition dsr-rcache.h:797
void ScheduleTimer()
Schedule m_ntimer.
void RebuildBestRouteTable(Ipv4Address source)
Rebuild the best route table.
void SetCacheType(std::string type)
Dijsktra algorithm to get the best route from m_netGraph and update the m_bestRoutesTable_link when c...
routeEntryVector m_routeEntryVector
Define the route vector.
Definition dsr-rcache.h:774
void AddArpCache(Ptr< ArpCache > a)
Add ARP cache to be used to allow layer 2 notifications processing.
std::map< Ipv4Address, DsrNodeStab > m_nodeCache
The data structure to store node info.
Definition dsr-rcache.h:798
void Purge()
Delete all outdated entries and invalidate valid entry if Lifetime is expired.
Time m_initStability
initial stability
Definition dsr-rcache.h:763
uint16_t CheckUniqueAckId(Ipv4Address nextHop)
Check for duplicate ids and save new entries if the id is not present in the table.
bool IsLinkCache()
is link cached
uint32_t m_stabilityIncrFactor
stability increase factor
Definition dsr-rcache.h:762
bool LookupRoute(Ipv4Address id, DsrRouteCacheEntry &rt)
Lookup route cache entry with destination address dst.
uint16_t GetAckSize()
Get the ack table size.
std::map< Ipv4Address, uint16_t > m_ackIdCache
The id cache to ensure all the ids are unique.
Definition dsr-rcache.h:778
void ProcessTxError(const WifiMacHeader &hdr)
Process layer 2 TX error notification.
Time RouteCacheTimeout
The maximum period of time that dsr is allowed to for an unused route.
Definition dsr-rcache.h:755
bool AddRoute_Link(DsrRouteCacheEntry::IP_VECTOR nodelist, Ipv4Address node)
dd route link to cache
std::vector< Ptr< ArpCache > > m_arp
list of ARP cached to be used for layer 2 notifications processing
Definition dsr-rcache.h:873
Mac48Address LookupMacAddress(Ipv4Address addr)
Find MAC address by IP using list of ARP caches.
void UseExtends(DsrRouteCacheEntry::IP_VECTOR rt)
When a link from the Route Cache is used in routing a packet originated or salvaged by that node,...
void PurgeMac()
Remove all expired mac entries.
bool FindSameRoute(DsrRouteCacheEntry &rt, std::list< DsrRouteCacheEntry > &rtVector)
Find the same route in the route cache.
std::map< Ipv4Address, routeEntryVector > m_sortedRoutes
Map the ipv4Address to route entry vector.
Definition dsr-rcache.h:772
void PrintVector(std::vector< Ipv4Address > &vec)
Print the route vector elements.
bool m_isLinkCache
Check if the route is using path cache or link cache.
Definition dsr-rcache.h:780
Time m_delay
This timeout deals with the passive ack.
Definition dsr-rcache.h:875
bool DeleteRoute(Ipv4Address dst)
Delete the route with certain destination address.
bool IncStability(Ipv4Address node)
increase the stability of the node
void PrintRouteVector(std::list< DsrRouteCacheEntry > route)
Print all the route vector elements from the route list.
uint32_t m_maxEntriesEachDst
number of entries for each destination
Definition dsr-rcache.h:776
Time GetExpireTime(Ipv4Address addr)
Return expire time for neighbor node with address addr, if exists, else return 0.
Time m_useExtends
use extend
Definition dsr-rcache.h:765
std::vector< Neighbor > m_nb
vector of entries
Definition dsr-rcache.h:870
Time m_minLifeTime
minimum lifetime
Definition dsr-rcache.h:764
void DelArpCache(Ptr< ArpCache >)
Don't use the provided ARP cache any more (interface is down)
void Print(std::ostream &os)
Print route cache.
bool LookupRoute_Link(Ipv4Address id, DsrRouteCacheEntry &rt)
used by LookupRoute when LinkCache
bool UpdateRouteEntry(Ipv4Address dst)
Update route cache entry if it has been recently used and successfully delivered the data packet.
void UpdateNeighbor(std::vector< Ipv4Address > nodeList, Time expire)
Update expire time for entry with address addr, if it exists, else add new entry.
void RemoveLastEntry(std::list< DsrRouteCacheEntry > &rtVector)
Remove the aged route cache entries when the route cache is full.
Timer m_ntimer
Timer for neighbor's list. Schedule Purge().
Definition dsr-rcache.h:868
bool m_subRoute
Check if save the sub route entries or not.
Definition dsr-rcache.h:782
void DeleteAllRoutesIncludeLink(Ipv4Address errorSrc, Ipv4Address unreachNode, Ipv4Address node)
Delete all the routes which includes the link from next hop address that has just been notified as un...
bool IsNeighbor(Ipv4Address addr)
Check that node with address addr is neighbor.
std::map< Ipv4Address, DsrRouteCacheEntry::IP_VECTOR > m_bestRoutesTable_link
for link route cache
Definition dsr-rcache.h:796
bool DecStability(Ipv4Address node)
decrease the stability of the node
void UpdateNetGraph()
Update the Net Graph for the link and node cache has changed.
bool AddRoute(DsrRouteCacheEntry &rt)
Add route cache entry if it doesn't yet exist in route cache.
void AddNeighbor(std::vector< Ipv4Address > nodeList, Ipv4Address ownAddress, Time expire)
Add to the neighbor list.
#define MAXWEIGHT
The link cache to update all the link status, bi-link is two link for link is a struct when the weigh...
Definition dsr-rcache.h:787
#define NS_LOG_COMPONENT_DEFINE(name)
Define a Log component with a specific name.
Definition log.h:191
#define NS_LOG_DEBUG(msg)
Use NS_LOG to output a message of level LOG_DEBUG.
Definition log.h:257
#define NS_LOG_LOGIC(msg)
Use NS_LOG to output a message of level LOG_LOGIC.
Definition log.h:271
#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:264
#define NS_OBJECT_ENSURE_REGISTERED(type)
Register an Object subclass with the TypeId system.
Definition object-base.h:35
Time Now()
create an ns3::Time instance which contains the current simulation time.
Definition simulator.cc:294
Time Seconds(double value)
Construct a Time in the indicated unit.
Definition nstime.h:1308
Time MilliSeconds(uint64_t value)
Construct a Time in the indicated unit.
Definition nstime.h:1320
bool CompareRoutesBoth(const DsrRouteCacheEntry &a, const DsrRouteCacheEntry &b)
Definition dsr-rcache.cc:50
bool CompareRoutesExpire(const DsrRouteCacheEntry &a, const DsrRouteCacheEntry &b)
Definition dsr-rcache.cc:66
bool CompareRoutesHops(const DsrRouteCacheEntry &a, const DsrRouteCacheEntry &b)
Definition dsr-rcache.cc:59
std::list< DsrRouteCacheEntry >::value_type route_pair
Every class exported by the ns3 library is enclosed in the ns3 namespace.
CloseNeighbor structure.
bool operator()(const DsrRouteCache::Neighbor &nb) const
Check if the entry is expired.
Structure to manage neighbor state.
Definition dsr-rcache.h:653
Time m_expireTime
route expire time
Definition dsr-rcache.h:656