A Discrete-Event Network Simulator
API
Loading...
Searching...
No Matches
dsr-rcache.h
Go to the documentation of this file.
1/*
2 * Copyright (c) 2011 Yufei Cheng
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 * Author: Yufei Cheng <yfcheng@ittc.ku.edu>
18 * Song Luan <lsuper@mail.ustc.edu.cn> (Implemented Link Cache using dijsktra algorithm
19 * to get the best route)
20 *
21 * James P.G. Sterbenz <jpgs@ittc.ku.edu>, director
22 * ResiliNets Research Group https://resilinets.org/
23 * Information and Telecommunication Technology Center (ITTC)
24 * and Department of Electrical Engineering and Computer Science
25 * The University of Kansas Lawrence, KS USA.
26 *
27 * Work supported in part by NSF FIND (Future Internet Design) Program
28 * under grant CNS-0626918 (Postmodern Internet Architecture),
29 * NSF grant CNS-1050226 (Multilayer Network Resilience Analysis and Experimentation on GENI),
30 * US Department of Defense (DoD), and ITTC at The University of Kansas.
31 */
32
33#ifndef DSR_RCACHE_H
34#define DSR_RCACHE_H
35
36#include "dsr-option-header.h"
37
38#include "ns3/arp-cache.h"
39#include "ns3/callback.h"
40#include "ns3/enum.h"
41#include "ns3/header.h"
42#include "ns3/ipv4-address.h"
43#include "ns3/ipv4-l3-protocol.h"
44#include "ns3/ipv4-route.h"
45#include "ns3/ipv4.h"
46#include "ns3/net-device.h"
47#include "ns3/nstime.h"
48#include "ns3/simple-ref-count.h"
49#include "ns3/simulator.h"
50#include "ns3/timer.h"
51
52#include <cassert>
53#include <iostream>
54#include <map>
55#include <stdint.h>
56#include <sys/types.h>
57#include <vector>
58
59namespace ns3
60{
61
62class Time;
63class WifiMacHeader;
64
65namespace dsr
66{
67
91struct Link
92{
95
103 {
104 if (ip1 < ip2)
105 {
106 m_low = ip1;
107 m_high = ip2;
108 }
109 else
110 {
111 m_low = ip2;
112 m_high = ip1;
113 }
114 }
115
121 bool operator<(const Link& L) const
122 {
123 if (m_low < L.m_low)
124 {
125 return true;
126 }
127 else if (m_low == L.m_low)
128 {
129 return (m_high < L.m_high);
130 }
131 else
132 {
133 return false;
134 }
135 }
136
138 void Print() const;
139};
140
146{
147 public:
152 DsrLinkStab(Time linkStab = Simulator::Now());
156 virtual ~DsrLinkStab();
157
162 void SetLinkStability(Time linkStab)
163 {
164 m_linkStability = linkStab + Simulator::Now();
165 }
166
172 {
174 }
175
177 void Print() const;
178
179 private:
185};
186
192{
193 public:
199 DsrNodeStab(Time nodeStab = Simulator::Now());
200 virtual ~DsrNodeStab();
201
206 void SetNodeStability(Time nodeStab)
207 {
208 m_nodeStability = nodeStab + Simulator::Now();
209 }
210
216 {
218 }
219
220 private:
222};
223
229{
230 public:
231 typedef std::vector<Ipv4Address> IP_VECTOR;
232 typedef std::vector<Ipv4Address>::iterator Iterator;
233
242 Ipv4Address dst = Ipv4Address(),
243 Time exp = Simulator::Now());
244 virtual ~DsrRouteCacheEntry();
245
248 void Invalidate(Time badLinkLifetime);
249
250 // Fields
255 void SetUnidirectional(bool u)
256 {
258 }
259
264 bool IsUnidirectional() const
265 {
266 return m_blackListState;
267 }
268
274 {
276 }
277
283 {
284 return m_blackListTimeout;
285 }
286
292 {
293 return m_dst;
294 }
295
301 {
302 m_dst = d;
303 }
304
310 {
311 return m_path;
312 }
313
319 {
320 m_path = v;
321 }
322
328 {
329 m_expire = exp + Simulator::Now();
330 }
331
337 {
338 return m_expire - Simulator::Now();
339 }
340
345 void Print(std::ostream& os) const;
346
352 bool operator==(const DsrRouteCacheEntry& o) const
353 {
354 return m_path == o.m_path;
355 }
356
357 private:
363 uint8_t m_reqCount;
368};
369
375class DsrRouteCache : public Object
376{
377 public:
382 static TypeId GetTypeId();
383
385 ~DsrRouteCache() override;
386
387 // Delete assignment operator to avoid misuse
389
394 void RemoveLastEntry(std::list<DsrRouteCacheEntry>& rtVector);
398 typedef std::list<DsrRouteCacheEntry::IP_VECTOR> routeVector;
399
400 // Fields
405 bool GetSubRoute() const
406 {
407 return m_subRoute;
408 }
409
414 void SetSubRoute(bool subRoute)
415 {
416 m_subRoute = subRoute;
417 }
418
424 {
425 return m_maxCacheLen;
426 }
427
433 {
434 m_maxCacheLen = len;
435 }
436
442 {
443 return RouteCacheTimeout;
444 }
445
451 {
453 }
454
460 {
461 return m_maxEntriesEachDst;
462 }
463
469 {
470 m_maxEntriesEachDst = entries;
471 }
472
478 {
479 return m_badLinkLifetime;
480 }
481
487 {
489 }
490
495 uint64_t GetStabilityDecrFactor() const
496 {
498 }
499
504 void SetStabilityDecrFactor(uint64_t decrFactor)
505 {
506 m_stabilityDecrFactor = decrFactor;
507 }
508
513 uint64_t GetStabilityIncrFactor() const
514 {
516 }
517
522 void SetStabilityIncrFactor(uint64_t incrFactor)
523 {
524 m_stabilityIncrFactor = incrFactor;
525 }
526
532 {
533 return m_initStability;
534 }
535
540 void SetInitStability(Time initStability)
541 {
542 m_initStability = initStability;
543 }
544
550 {
551 return m_minLifeTime;
552 }
553
558 void SetMinLifeTime(Time minLifeTime)
559 {
560 m_minLifeTime = minLifeTime;
561 }
562
568 {
569 return m_useExtends;
570 }
571
576 void SetUseExtends(Time useExtends)
577 {
578 m_useExtends = useExtends;
579 }
580
605 void PrintVector(std::vector<Ipv4Address>& vec);
610 void PrintRouteVector(std::list<DsrRouteCacheEntry> route);
617 bool FindSameRoute(DsrRouteCacheEntry& rt, std::list<DsrRouteCacheEntry>& rtVector);
623 bool DeleteRoute(Ipv4Address dst);
633 Ipv4Address unreachNode,
634 Ipv4Address node);
635
637 void Clear()
638 {
640 }
641
643 void Purge();
646 void Print(std::ostream& os);
647
648 //------------------------------------------------------------------------------------------
654 uint16_t CheckUniqueAckId(Ipv4Address nextHop);
659 uint16_t GetAckSize();
660
661 // --------------------------------------------------------------------------------------------
663 struct Neighbor
664 {
668 bool close;
669
678 : m_neighborAddress(ip),
680 m_expireTime(t),
681 close(false)
682 {
683 }
684
686 {
687 } // For Python bindings
688 };
689
701 bool IsNeighbor(Ipv4Address addr);
707 void UpdateNeighbor(std::vector<Ipv4Address> nodeList, Time expire);
714 void AddNeighbor(std::vector<Ipv4Address> nodeList, Ipv4Address ownAddress, Time expire);
718 void PurgeMac();
722 void ScheduleTimer();
723
727 void ClearMac()
728 {
729 m_nb.clear();
730 }
731
742
748 {
750 }
751
757 {
758 return m_handleLinkFailure;
759 }
760
761 private:
769 /*
770 * Define the parameters for link cache type
771 */
780 typedef std::list<DsrRouteCacheEntry> routeEntryVector;
781
782 std::map<Ipv4Address, routeEntryVector>
784
786
788
789 std::map<Ipv4Address, uint16_t> m_ackIdCache;
790
792
798#define MAXWEIGHT 0xFFFF;
804 std::map<Ipv4Address, std::map<Ipv4Address, uint32_t>> m_netGraph;
805
806 std::map<Ipv4Address, DsrRouteCacheEntry::IP_VECTOR>
808 std::map<Link, DsrLinkStab> m_linkCache;
809 std::map<Ipv4Address, DsrNodeStab> m_nodeCache;
822 bool IncStability(Ipv4Address node);
828 bool DecStability(Ipv4Address node);
829
830 public:
836 void SetCacheType(std::string type);
841 bool IsLinkCache();
859 void PurgeLinkNode();
872 void UpdateNetGraph();
873 //---------------------------------------------------------------------------------------
878
880
881 std::vector<Neighbor> m_nb;
882
883 std::vector<Ptr<ArpCache>>
885
887
892
895 void ProcessTxError(const WifiMacHeader& hdr);
896};
897} // namespace dsr
898} // namespace ns3
899#endif /* DSR_RCACHE_H */
Callback template class.
Definition: callback.h:438
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
an EUI-48 address
Definition: mac48-address.h:46
A base class which provides memory management and object aggregation.
Definition: object.h:89
Smart pointer class similar to boost::intrusive_ptr.
Definition: ptr.h:77
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
A simple virtual Timer class.
Definition: timer.h:74
a unique identifier for an interface.
Definition: type-id.h:59
Implements the IEEE 802.11 MAC header.
DsrNodeStab class (DSR node stability)
Definition: dsr-rcache.h:192
Time GetNodeStability() const
Get node stability.
Definition: dsr-rcache.h:215
Time m_nodeStability
the node stability
Definition: dsr-rcache.h:221
void SetNodeStability(Time nodeStab)
Set node stability.
Definition: dsr-rcache.h:206
virtual ~DsrNodeStab()
Definition: dsr-rcache.cc:94
DsrRouteCacheEntry class for entries in the route cache.
Definition: dsr-rcache.h:229
IP_VECTOR GetVector() const
Get the IP vector.
Definition: dsr-rcache.h:309
void SetDestination(Ipv4Address d)
Set destination address.
Definition: dsr-rcache.h:300
Time m_expire
Expire time for queue entry.
Definition: dsr-rcache.h:361
IP_VECTOR m_path
brief The IP address constructed route
Definition: dsr-rcache.h:360
Ipv4Address m_dst
The destination Ip address.
Definition: dsr-rcache.h:359
Ptr< Ipv4Route > m_ipv4Route
The Ipv4 route.
Definition: dsr-rcache.h:366
Time GetBlacklistTimeout() const
Get blacklist timeout.
Definition: dsr-rcache.h:282
std::vector< Ipv4Address >::iterator Iterator
Define the iterator.
Definition: dsr-rcache.h:232
uint8_t m_reqCount
Number of route requests.
Definition: dsr-rcache.h:363
Timer m_ackTimer
RREP_ACK timer.
Definition: dsr-rcache.h:358
Ptr< Ipv4 > m_ipv4
The Ipv4 layer 3.
Definition: dsr-rcache.h:367
Ipv4Address GetDestination() const
Get destination address.
Definition: dsr-rcache.h:291
void SetBlacklistTimeout(Time t)
Set blacklist timeout.
Definition: dsr-rcache.h:273
Ipv4InterfaceAddress m_iface
Output interface address.
Definition: dsr-rcache.h:362
virtual ~DsrRouteCacheEntry()
Definition: dsr-rcache.cc:126
Time m_blackListTimeout
Time for which the node is put into the blacklist.
Definition: dsr-rcache.h:365
bool IsUnidirectional() const
Get unidirectional flag.
Definition: dsr-rcache.h:264
void Invalidate(Time badLinkLifetime)
Mark entry as "down" (i.e.
Definition: dsr-rcache.cc:131
void Print(std::ostream &os) const
Print necessary fields.
Definition: dsr-rcache.cc:138
void SetUnidirectional(bool u)
Set unidirectional flag.
Definition: dsr-rcache.h:255
std::vector< Ipv4Address > IP_VECTOR
Define the vector to hold Ip address.
Definition: dsr-rcache.h:231
bool m_blackListState
Indicate if this entry is in "blacklist".
Definition: dsr-rcache.h:364
Time GetExpireTime() const
Get expire time.
Definition: dsr-rcache.h:336
void SetExpireTime(Time exp)
Set expire time.
Definition: dsr-rcache.h:327
void SetVector(IP_VECTOR v)
Sets the IP vector.
Definition: dsr-rcache.h:318
bool operator==(const DsrRouteCacheEntry &o) const
Compare the route cache entry.
Definition: dsr-rcache.h:352
DSR route request queue Since DSR is an on demand routing we queue requests while looking for route.
Definition: dsr-rcache.h:376
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:804
uint32_t m_stabilityDecrFactor
stability decrease factor
Definition: dsr-rcache.h:772
std::list< DsrRouteCacheEntry::IP_VECTOR > routeVector
Define the vector of route entries.
Definition: dsr-rcache.h:398
static TypeId GetTypeId()
Get the type ID.
Definition: dsr-rcache.cc:146
void SetBadLinkLifetime(Time t)
Set bad link lifetime function.
Definition: dsr-rcache.h:486
void PurgeLinkNode()
Purge from the cache if the stability time expired.
Definition: dsr-rcache.cc:461
Callback< void, Ipv4Address, uint8_t > m_handleLinkFailure
The following code handles link-layer acks.
Definition: dsr-rcache.h:877
std::map< Link, DsrLinkStab > m_linkCache
The data structure to store link info.
Definition: dsr-rcache.h:808
void ScheduleTimer()
Schedule m_ntimer.
Definition: dsr-rcache.cc:1203
void SetInitStability(Time initStability)
Set initial stability.
Definition: dsr-rcache.h:540
void RebuildBestRouteTable(Ipv4Address source)
Rebuild the best route table.
Definition: dsr-rcache.cc:318
void SetCacheType(std::string type)
Dijsktra algorithm to get the best route from m_netGraph and update the m_bestRoutesTable_link when c...
Definition: dsr-rcache.cc:292
std::list< DsrRouteCacheEntry > routeEntryVector
Define the route cache data structure.
Definition: dsr-rcache.h:780
void SetStabilityDecrFactor(uint64_t decrFactor)
Set stability decrease factor.
Definition: dsr-rcache.h:504
uint64_t GetStabilityDecrFactor() const
Get stability decrease factor.
Definition: dsr-rcache.h:495
routeEntryVector m_routeEntryVector
Define the route vector.
Definition: dsr-rcache.h:785
void AddArpCache(Ptr< ArpCache > a)
Add ARP cache to be used to allow layer 2 notifications processing.
Definition: dsr-rcache.cc:1210
std::map< Ipv4Address, DsrNodeStab > m_nodeCache
The data structure to store node info.
Definition: dsr-rcache.h:809
void Purge()
Delete all outdated entries and invalidate valid entry if Lifetime is expired.
Definition: dsr-rcache.cc:968
Time m_initStability
initial stability
Definition: dsr-rcache.h:774
uint16_t CheckUniqueAckId(Ipv4Address nextHop)
Check for duplicate ids and save new entries if the id is not present in the table.
Definition: dsr-rcache.cc:1053
bool IsLinkCache()
is link cached
Definition: dsr-rcache.cc:311
Time GetBadLinkLifetime() const
Get bad link lifetime function.
Definition: dsr-rcache.h:477
void SetMinLifeTime(Time minLifeTime)
Set minimum lifetime.
Definition: dsr-rcache.h:558
uint32_t GetMaxEntriesEachDst() const
Get max entries for each destination.
Definition: dsr-rcache.h:459
uint32_t m_stabilityIncrFactor
stability increase factor
Definition: dsr-rcache.h:773
Time GetInitStability() const
Get initial stability.
Definition: dsr-rcache.h:531
Time GetCacheTimeout() const
Get cache timeout value.
Definition: dsr-rcache.h:441
uint64_t GetStabilityIncrFactor() const
Get stability increase factor.
Definition: dsr-rcache.h:513
void SetMaxCacheLen(uint32_t len)
Set the max queue length.
Definition: dsr-rcache.h:432
bool LookupRoute(Ipv4Address id, DsrRouteCacheEntry &rt)
Lookup route cache entry with destination address dst.
Definition: dsr-rcache.cc:213
bool GetSubRoute() const
Get subroute indicator.
Definition: dsr-rcache.h:405
uint16_t GetAckSize()
Get the ack table size.
Definition: dsr-rcache.cc:1073
std::map< Ipv4Address, uint16_t > m_ackIdCache
The id cache to ensure all the ids are unique.
Definition: dsr-rcache.h:789
void ProcessTxError(const WifiMacHeader &hdr)
Process layer 2 TX error notification.
Definition: dsr-rcache.cc:1238
Time RouteCacheTimeout
The maximum period of time that dsr is allowed to for an unused route.
Definition: dsr-rcache.h:766
void SetMaxEntriesEachDst(uint32_t entries)
Set max entries for each destination.
Definition: dsr-rcache.h:468
bool AddRoute_Link(DsrRouteCacheEntry::IP_VECTOR nodelist, Ipv4Address node)
dd route link to cache
Definition: dsr-rcache.cc:560
Time m_badLinkLifetime
The time for which the neighboring node is put into the blacklist.
Definition: dsr-rcache.h:768
uint32_t m_maxCacheLen
The maximum number of packets that we allow a routing protocol to buffer.
Definition: dsr-rcache.h:764
std::vector< Ptr< ArpCache > > m_arp
list of ARP cached to be used for layer 2 notifications processing
Definition: dsr-rcache.h:884
Mac48Address LookupMacAddress(Ipv4Address addr)
Find MAC address by IP using list of ARP caches.
Definition: dsr-rcache.cc:1222
Callback< void, Ipv4Address, uint8_t > GetCallback() const
Handle link failure callback.
Definition: dsr-rcache.h:756
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,...
Definition: dsr-rcache.cc:610
void PurgeMac()
Remove all expired mac entries.
Definition: dsr-rcache.cc:1177
bool FindSameRoute(DsrRouteCacheEntry &rt, std::list< DsrRouteCacheEntry > &rtVector)
Find the same route in the route cache.
Definition: dsr-rcache.cc:729
void Clear()
Delete all entries from routing table.
Definition: dsr-rcache.h:637
std::map< Ipv4Address, routeEntryVector > m_sortedRoutes
Map the ipv4Address to route entry vector.
Definition: dsr-rcache.h:783
Time GetMinLifeTime() const
Get minimum lifetime.
Definition: dsr-rcache.h:549
DsrRouteCacheEntry::IP_VECTOR m_vector
The route vector to save the ip addresses for intermediate nodes.
Definition: dsr-rcache.h:763
void ClearMac()
Remove all entries.
Definition: dsr-rcache.h:727
void SetUseExtends(Time useExtends)
Set use extends.
Definition: dsr-rcache.h:576
Time GetUseExtends() const
Get use extends.
Definition: dsr-rcache.h:567
void PrintVector(std::vector< Ipv4Address > &vec)
Print the route vector elements.
Definition: dsr-rcache.cc:935
bool m_isLinkCache
Check if the route is using path cache or link cache.
Definition: dsr-rcache.h:791
Time m_delay
This timeout deals with the passive ack.
Definition: dsr-rcache.h:886
bool DeleteRoute(Ipv4Address dst)
Delete the route with certain destination address.
Definition: dsr-rcache.cc:762
bool IncStability(Ipv4Address node)
increase the stability of the node
Definition: dsr-rcache.cc:511
void PrintRouteVector(std::list< DsrRouteCacheEntry > route)
Print all the route vector elements from the route list.
Definition: dsr-rcache.cc:956
uint32_t m_maxEntriesEachDst
number of entries for each destination
Definition: dsr-rcache.h:787
Time GetExpireTime(Ipv4Address addr)
Return expire time for neighbor node with address addr, if exists, else return 0.
Definition: dsr-rcache.cc:1098
Time m_useExtends
use extend
Definition: dsr-rcache.h:776
std::vector< Neighbor > m_nb
vector of entries
Definition: dsr-rcache.h:881
uint32_t GetMaxCacheLen() const
Get the max queue length.
Definition: dsr-rcache.h:423
Time m_minLifeTime
minimum lifetime
Definition: dsr-rcache.h:775
void DelArpCache(Ptr< ArpCache >)
Don't use the provided ARP cache any more (interface is down)
Definition: dsr-rcache.cc:1216
void SetSubRoute(bool subRoute)
Set subroute indicator.
Definition: dsr-rcache.h:414
void Print(std::ostream &os)
Print route cache.
Definition: dsr-rcache.cc:1035
void SetCacheTimeout(Time t)
Set cache timeout value.
Definition: dsr-rcache.h:450
bool LookupRoute_Link(Ipv4Address id, DsrRouteCacheEntry &rt)
used by LookupRoute when LinkCache
Definition: dsr-rcache.cc:431
void SetStabilityIncrFactor(uint64_t incrFactor)
Set stability increase factor.
Definition: dsr-rcache.h:522
bool UpdateRouteEntry(Ipv4Address dst)
Update route cache entry if it has been recently used and successfully delivered the data packet.
Definition: dsr-rcache.cc:185
void UpdateNeighbor(std::vector< Ipv4Address > nodeList, Time expire)
Update expire time for entry with address addr, if it exists, else add new entry.
Definition: dsr-rcache.cc:1113
void RemoveLastEntry(std::list< DsrRouteCacheEntry > &rtVector)
Remove the aged route cache entries when the route cache is full.
Definition: dsr-rcache.cc:177
void SetCallback(Callback< void, Ipv4Address, uint8_t > cb)
Handle link failure callback.
Definition: dsr-rcache.h:747
Timer m_ntimer
Timer for neighbor's list. Schedule Purge().
Definition: dsr-rcache.h:879
DsrRouteCache & operator=(const DsrRouteCache &)=delete
bool m_subRoute
Check if save the sub route entries or not.
Definition: dsr-rcache.h:793
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...
Definition: dsr-rcache.cc:776
bool IsNeighbor(Ipv4Address addr)
Check that node with address addr is neighbor.
Definition: dsr-rcache.cc:1083
std::map< Ipv4Address, DsrRouteCacheEntry::IP_VECTOR > m_bestRoutesTable_link
for link route cache
Definition: dsr-rcache.h:807
bool DecStability(Ipv4Address node)
decrease the stability of the node
Definition: dsr-rcache.cc:536
void UpdateNetGraph()
Update the Net Graph for the link and node cache has changed.
Definition: dsr-rcache.cc:496
bool AddRoute(DsrRouteCacheEntry &rt)
Add route cache entry if it doesn't yet exist in route cache.
Definition: dsr-rcache.cc:657
void AddNeighbor(std::vector< Ipv4Address > nodeList, Ipv4Address ownAddress, Time expire)
Add to the neighbor list.
Definition: dsr-rcache.cc:1140
void(* Time)(Time oldValue, Time newValue)
TracedValue callback signature for Time.
Definition: nstime.h:839
Every class exported by the ns3 library is enclosed in the ns3 namespace.
Structure to manage neighbor state.
Definition: dsr-rcache.h:664
Mac48Address m_hardwareAddress
neighbor MAC address
Definition: dsr-rcache.h:666
Neighbor(Ipv4Address ip, Mac48Address mac, Time t)
Constructor.
Definition: dsr-rcache.h:677
Ipv4Address m_neighborAddress
neighbor address
Definition: dsr-rcache.h:665
Time m_expireTime
route expire time
Definition: dsr-rcache.h:667