33 #include "dsr-rcache.h"
43 #include "ns3/simulator.h"
44 #include "ns3/ipv4-route.h"
45 #include "ns3/socket.h"
47 #include "ns3/address-utils.h"
48 #include "ns3/packet.h"
55 bool CompareRoutesBoth (
const RouteCacheEntry &a,
const RouteCacheEntry &b)
58 return (a.GetVector ().size () < b.GetVector ().size ())
59 || ((a.GetVector ().size () == b.GetVector ().size ()) && (a.GetExpireTime () > b.GetExpireTime ()))
63 bool CompareRoutesHops (
const RouteCacheEntry &a,
const RouteCacheEntry &b)
66 return a.GetVector ().size () < b.GetVector ().size ();
69 bool CompareRoutesExpire (
const RouteCacheEntry &a,
const RouteCacheEntry &b)
72 return a.GetExpireTime () > b.GetExpireTime ();
75 void Link::Print ()
const
98 void LinkStab::Print ( )
const
100 NS_LOG_LOGIC (
"LifeTime: " << GetLinkStability ().GetSeconds ());
103 typedef std::list<RouteCacheEntry>::value_type route_pair;
106 : m_ackTimer (
Timer::CANCEL_ON_DESTROY),
111 m_blackListState (false),
121 RouteCacheEntry::Invalidate (
Time badLinkLifetime)
140 .AddConstructor<RouteCache> ()
147 m_maxEntriesEachDst (3),
148 m_isLinkCache (false),
149 m_ntimer (
Timer::CANCEL_ON_DESTROY),
172 rtVector.pop_back ();
179 std::map<Ipv4Address, std::list<RouteCacheEntry> >::const_iterator i =
183 NS_LOG_LOGIC (
"Failed to find the route entry for the destination " << dst);
188 std::list<RouteCacheEntry> rtVector = i->second;
191 rtVector.pop_front ();
192 rtVector.push_back (successEntry);
193 rtVector.sort (CompareRoutesExpire);
198 std::pair<std::map<Ipv4Address, std::list<RouteCacheEntry> >::iterator,
bool> result =
200 return result.second;
218 NS_LOG_LOGIC (
"Route to " <<
id <<
" not found; m_sortedRoutes is empty");
221 std::map<Ipv4Address, std::list<RouteCacheEntry> >::const_iterator i =
m_sortedRoutes.find (
id);
225 for (std::map<
Ipv4Address, std::list<RouteCacheEntry> >::const_iterator j =
228 std::list<RouteCacheEntry> rtVector = j->second;
232 for (std::list<RouteCacheEntry>::const_iterator k = rtVector.begin (); k != rtVector.end (); ++k)
238 for (RouteCacheEntry::IP_VECTOR::iterator l = routeVector.begin (); l != routeVector.end (); ++l)
242 changeVector.push_back (*l);
246 changeVector.push_back (*l);
254 if ((changeVector.size () < routeVector.size ()) && (changeVector.size () > 1))
257 changeEntry.SetVector (changeVector);
258 changeEntry.SetDestination (
id);
260 changeEntry.SetExpireTime (k->GetExpireTime ());
262 std::list<RouteCacheEntry> newVector;
263 newVector.push_back (changeEntry);
264 newVector.sort (CompareRoutesExpire);
266 NS_LOG_INFO (
"We have a sub-route to " <<
id <<
" add it in route cache");
271 NS_LOG_INFO (
"Here we check the route cache again after updated the sub routes");
272 std::map<Ipv4Address, std::list<RouteCacheEntry> >::const_iterator m =
m_sortedRoutes.find (
id);
281 std::list<RouteCacheEntry> rtVector = m->second;
282 rt = rtVector.front ();
283 NS_LOG_LOGIC (
"Route to " <<
id <<
" with route size " << rtVector.size ());
292 if (type == std::string (
"LinkCache"))
296 else if (type == std::string (
"PathCache"))
308 RouteCache::IsLinkCache ()
322 std::map<Ipv4Address, uint32_t> d;
324 std::map<Ipv4Address, Ipv4Address> pre;
327 if (i->second.find (source) != i->second.end ())
329 d[i->first] = i->second[source];
330 pre[i->first] = source;
334 d[i->first] = MAXWEIGHT;
343 std::map<Ipv4Address, bool> s;
344 double temp = MAXWEIGHT;
346 for (uint32_t i = 0; i <
m_netGraph.size (); i++)
349 for (std::map<Ipv4Address,uint32_t>::const_iterator j = d.begin (); j != d.end (); ++j)
352 if (s.find (ip) == s.end ())
357 if (j->second <= temp)
367 for (std::map<Ipv4Address, uint32_t>::const_iterator k =
m_netGraph[tempip].begin (); k !=
m_netGraph[tempip].end (); ++k)
369 if (s.find (k->first) == s.end () && d[k->first] > d[tempip] + k->second)
371 d[k->first] = d[tempip] + k->second;
372 pre[k->first] = tempip;
380 else if (d[k->first] == d[tempip] + k->second)
382 std::map<Link, LinkStab>::iterator oldlink =
m_linkCache.find (
Link (k->first, pre[k->first]));
383 std::map<Link, LinkStab>::iterator newlink =
m_linkCache.find (
Link (k->first, tempip));
386 if (oldlink->second.GetLinkStability () < newlink->second.GetLinkStability ())
388 NS_LOG_INFO (
"Select the link with longest expected lifetime");
389 d[k->first] = d[tempip] + k->second;
390 pre[k->first] = tempip;
403 for (std::map<Ipv4Address, Ipv4Address>::iterator i = pre.begin (); i != pre.end (); ++i)
409 if (!i->second.IsBroadcast () && iptemp != source)
411 while (iptemp != source)
413 route.push_back (iptemp);
414 iptemp = pre[iptemp];
416 route.push_back (source);
419 for (RouteCacheEntry::IP_VECTOR::reverse_iterator j = route.rbegin (); j != route.rend (); ++j)
421 reverseroute.push_back (*j);
444 if (i->second.size () < 2)
451 newEntry.SetVector (i->second);
452 newEntry.SetDestination (
id);
454 NS_LOG_INFO (
"Route to " <<
id <<
" found with the length " << i->second.size ());
456 std::vector<Ipv4Address> path = rt.GetVector ();
468 NS_LOG_DEBUG (
"The link stability " << i->second.GetLinkStability ().GetSeconds ());
469 std::map<Link, LinkStab>::iterator itmp = i;
470 if (i->second.GetLinkStability () <=
Seconds (0))
483 NS_LOG_DEBUG (
"The node stability " << i->second.GetNodeStability ().GetSeconds ());
484 std::map<Ipv4Address, NodeStab>::iterator itmp = i;
485 if (i->second.GetNodeStability () <=
Seconds (0))
507 m_netGraph[i->first.m_low][i->first.m_high] = weight;
508 m_netGraph[i->first.m_high][i->first.m_low] = weight;
516 std::map<Ipv4Address, NodeStab>::const_iterator i =
m_nodeCache.find (node);
527 NS_LOG_INFO (
"The node stability " << i->second.GetNodeStability ().GetSeconds ());
528 NS_LOG_INFO (
"The stability here " <<
Time (i->second.GetNodeStability () * m_stabilityIncrFactor).GetSeconds ());
529 NodeStab ns (
Time (i->second.GetNodeStability () * m_stabilityIncrFactor));
540 std::map<Ipv4Address, NodeStab>::const_iterator i =
m_nodeCache.find (node);
550 NS_LOG_INFO (
"The stability here " << i->second.GetNodeStability ().GetSeconds ());
566 for (uint32_t i = 0; i < nodelist.size () - 1; i++)
569 ns.SetNodeStability (m_initStability);
579 Link link (nodelist[i], nodelist[i + 1]);
591 if (stab.GetLinkStability () < m_minLifeTime)
619 for (RouteCacheEntry::IP_VECTOR::iterator i = rt.begin (); i != rt.end () - 1; ++i)
621 Link link (*i, *(i + 1));
624 if (
m_linkCache[link].GetLinkStability () < m_useExtends)
637 for (RouteCacheEntry::IP_VECTOR::iterator i = rt.begin (); i != rt.end (); ++i)
642 if (
m_nodeCache[*i].GetNodeStability () <= m_initStability)
648 NS_LOG_INFO (
"The node stability has already been increased");
659 std::list<RouteCacheEntry> rtVector;
661 std::vector<Ipv4Address> route = rt.GetVector ();
664 std::map<Ipv4Address, std::list<RouteCacheEntry> >::const_iterator i =
669 rtVector.push_back (rt);
674 std::pair<std::map<Ipv4Address, std::list<RouteCacheEntry> >::iterator,
bool> result =
676 return result.second;
680 rtVector = i->second;
681 NS_LOG_DEBUG (
"The existing route size " << rtVector.size () <<
" for destination address " << dst);
692 NS_LOG_DEBUG (
"Find same vector, the FindSameRoute function will update the route expire time");
698 if (rt.GetExpireTime () > 0)
700 rtVector.push_back (rt);
703 rtVector.sort (CompareRoutesExpire);
704 NS_LOG_DEBUG (
"The first time" << rtVector.front ().GetExpireTime ().GetSeconds () <<
" The second time "
705 << rtVector.back ().GetExpireTime ().GetSeconds ());
706 NS_LOG_DEBUG (
"The first hop" << rtVector.front ().GetVector ().size () <<
" The second hop "
707 << rtVector.back ().GetVector ().size ());
712 std::pair<std::map<Ipv4Address, std::list<RouteCacheEntry> >::iterator,
bool> result =
714 return result.second;
718 NS_LOG_INFO (
"The newly found route is already expired");
728 for (std::list<RouteCacheEntry>::iterator i = rtVector.begin (); i != rtVector.end (); ++i)
734 if (routeVector == newVector)
736 NS_LOG_DEBUG (
"Found same routes in the route cache with the vector size "
737 << rt.GetDestination () <<
" " << rtVector.size ());
739 <<
" the original expire time " << i->GetExpireTime ().GetSeconds ());
740 if (rt.GetExpireTime () > i->GetExpireTime ())
742 i->SetExpireTime (rt.GetExpireTime ());
745 rtVector.sort (CompareRoutesExpire);
749 std::pair<std::map<Ipv4Address, std::list<RouteCacheEntry> >::iterator,
bool> result =
750 m_sortedRoutes.insert (std::make_pair (rt.GetDestination (), rtVector));
751 return result.second;
764 NS_LOG_LOGIC (
"Route deletion to " << dst <<
" successful");
767 NS_LOG_LOGIC (
"Route deletion to " << dst <<
" not successful");
783 Link link1 (errorSrc, unreachNode);
784 Link link2 (unreachNode, errorSrc);
793 std::map<Ipv4Address, NodeStab>::iterator i =
m_nodeCache.find (errorSrc);
796 NS_LOG_LOGIC (
"Update the node stability unsuccessfully");
805 NS_LOG_LOGIC (
"Update the node stability unsuccessfully");
828 for (std::map<
Ipv4Address, std::list<RouteCacheEntry> >::iterator j =
831 std::map<Ipv4Address, std::list<RouteCacheEntry> >::iterator jtmp = j;
833 std::list<RouteCacheEntry> rtVector = j->second;
837 for (std::list<RouteCacheEntry>::iterator k = rtVector.begin (); k != rtVector.end (); )
845 for (RouteCacheEntry::IP_VECTOR::iterator i = routeVector.begin (); i != routeVector.end (); ++i)
849 changeVector.push_back (*i);
853 if (*(i + 1) == unreachNode)
855 changeVector.push_back (*i);
860 changeVector.push_back (*i);
867 if (changeVector.size () == routeVector.size ())
869 NS_LOG_DEBUG (
"The route does not contain the broken link");
872 else if ((changeVector.size () < routeVector.size ()) && (changeVector.size () > 1))
877 Time expire = k->GetExpireTime ();
881 k = rtVector.erase (k);
883 changeEntry.SetVector (changeVector);
885 NS_LOG_DEBUG (
"The destination of the newly formed route " << destination <<
" and the size of the route " << changeVector.size ());
886 changeEntry.SetDestination (destination);
887 changeEntry.SetExpireTime (expire);
888 rtVector.push_back (changeEntry);
889 NS_LOG_DEBUG (
"We have a sub-route to " << destination);
896 k = rtVector.erase (k);
901 NS_LOG_LOGIC (
"Cut route unsuccessful and erase the route");
905 k = rtVector.erase (k);
913 if (rtVector.size ())
918 rtVector.sort (CompareRoutesExpire);
923 NS_LOG_DEBUG (
"There is no route left for that destination " << address);
943 for (std::vector<Ipv4Address>::const_iterator i = vec.begin (); i != vec.end (); ++i)
954 for (std::list<RouteCacheEntry>::iterator i = route.begin (); i != route.end (); i++)
956 std::vector<Ipv4Address> path = i->GetVector ();
972 for (std::map<
Ipv4Address, std::list<RouteCacheEntry> >::iterator i =
976 std::map<Ipv4Address, std::list<RouteCacheEntry> >::iterator itmp = i;
981 std::list<RouteCacheEntry> rtVector = i->second;
982 NS_LOG_DEBUG (
"The route vector size of 1 " << dst <<
" " << rtVector.size ());
983 if (rtVector.size ())
985 for (std::list<RouteCacheEntry>::iterator j = rtVector.begin (); j != rtVector.end (); )
987 NS_LOG_DEBUG (
"The expire time of every entry with expire time " << j->GetExpireTime ());
991 if (j->GetExpireTime () <=
Seconds (0))
996 NS_LOG_DEBUG (
"Erase the expired route for " << dst <<
" with expire time " << j->GetExpireTime ());
997 j = rtVector.erase (j);
1004 NS_LOG_DEBUG (
"The route vector size of 2 " << dst <<
" " << rtVector.size ());
1005 if (rtVector.size ())
1030 RouteCache::Print (std::ostream &os)
1034 os <<
"\nDSR Route Cache\n"
1035 <<
"Destination\tGateway\t\tInterface\tFlag\tExpire\tHops\n";
1036 for (std::list<RouteCacheEntry>::const_iterator i =
1052 std::map<Ipv4Address, uint16_t>::const_iterator i =
1056 NS_LOG_LOGIC (
"No Ack id for " << nextHop <<
" found and use id 1 for the first network ack id");
1063 NS_LOG_LOGIC (
"Ack id for " << nextHop <<
" found in the cache has value " << ackId);
1085 for (std::vector<Neighbor>::const_iterator i =
m_nb.begin ();
1086 i !=
m_nb.end (); ++i)
1088 if (i->m_neighborAddress == addr)
1101 for (std::vector<Neighbor>::const_iterator i =
m_nb.begin (); i
1102 !=
m_nb.end (); ++i)
1104 if (i->m_neighborAddress == addr)
1116 for (std::vector<Neighbor>::iterator i =
m_nb.begin (); i !=
m_nb.end (); ++i)
1118 for (std::vector<Ipv4Address>::iterator j = nodeList.begin (); j != nodeList.end (); ++j)
1120 if (i->m_neighborAddress == (*j))
1136 m_nb.push_back (neighbor);
1143 NS_LOG_LOGIC (
"Add neighbor number " << nodeList.size ());
1144 for (std::vector<Ipv4Address>::iterator j = nodeList.begin (); j != nodeList.end (); ++j)
1147 if (addr == ownAddress)
1150 NS_LOG_DEBUG (
"The node list size " << nodeList.size ());
1153 m_nb.push_back (neighbor);
1177 for (std::vector<Neighbor>::iterator j =
m_nb.begin (); j !=
m_nb.end (); ++j)
1181 NS_LOG_LOGIC (
"Close link to " << j->m_neighborAddress);
1187 m_nb.erase (std::remove_if (
m_nb.begin (),
m_nb.end (), pred),
m_nb.end ());
1202 m_arp.push_back (a);
1216 i !=
m_arp.end (); ++i)
1233 for (std::vector<Neighbor>::iterator i =
m_nb.begin (); i !=
m_nb.end (); ++i)
1235 if (i->m_hardwareAddress == addr)
bool DeleteRoute(Ipv4Address dst)
Delete the route with certain destination address.
static TypeId GetTypeId()
The Route Cache used by DSR.
LinkStab(Time linkStab=Simulator::Now())
Constructor.
#define NS_LOG_FUNCTION(parameters)
void PurgeMac()
Remove all expired mac entries.
Control the scheduling of simulation events.
bool IncStability(Ipv4Address node)
increase the stability of the node
Ipv4Address m_dst
The destination Ip address.
void SetLinkStability(Time linkStab)
set/get the link stability
virtual ~LinkStab()
Destructor.
#define NS_LOG_COMPONENT_DEFINE(name)
Time RouteCacheTimeout
The maximum period of time that dsr is allowed to for an unused route.
bool AddRoute(RouteCacheEntry &rt)
Add route cache entry if it doesn't yet exist in route cache.
void RebuildBestRouteTable(Ipv4Address source)
USE MAXWEIGHT TO REPRESENT MAX; USE BROADCAST ADDRESS TO REPRESENT NULL PRECEEDING ADDRESS...
NodeStab(Time nodeStab=Simulator::Now())
Constructor.
#define NS_LOG_FUNCTION_NOARGS()
bool LookupRoute_Link(Ipv4Address id, RouteCacheEntry &rt)
used by LookupRoute when LinkCache
std::map< Ipv4Address, std::map< Ipv4Address, uint32_t > > m_netGraph
uint32_t m_stabilityDecrFactor
std::map< Ipv4Address, uint16_t > m_ackIdCache
The id cache to ensure all the ids are unique.
void SetCacheType(std::string type)
dijsktra algorithm to get the best route from m_netGraph and update the m_bestRoutesTable_link curre...
double GetSeconds(void) const
void UseExtends(RouteCacheEntry::IP_VECTOR rt)
uint16_t CheckUniqueAckId(Ipv4Address nextHop)
Check for duplicate ids and save new entries if the id is not present in the table.
std::list< RouteCacheEntry::IP_VECTOR > routeVector
Define the vector of route entries.
void AddNeighbor(std::vector< Ipv4Address > nodeList, Ipv4Address ownAddress, Time expire)
Add to the neighbor list.
void UpdateNeighbor(std::vector< Ipv4Address > nodeList, Time expire)
Update expire time for entry with address addr, if it exists, else add new entry. ...
void ScheduleTimer()
Schedule m_ntimer.
std::vector< Ipv4Address > IP_VECTOR
Define the vector to hold Ip address.
bool m_subRoute
Check if save the sub route entries or not.
bool IsBroadcast(void) const
bool UpdateRouteEntry(Ipv4Address dst)
Update route cache entry if it has been recently used and successfully delivered the data packet...
Callback< R > MakeCallback(R(T::*memPtr)(void), OBJ objPtr)
void DelArpCache(Ptr< ArpCache >)
Don't use given ARP cache any more (interface is down)
bool IsExpired(void) const
RouteCacheEntry(IP_VECTOR const &ip=IP_VECTOR(), Ipv4Address dst=Ipv4Address(), Time exp=Simulator::Now())
Constructor.
void PrintRouteVector(std::list< RouteCacheEntry > route)
Print all the route vector elements from the route list.
std::map< Link, LinkStab > m_linkCache
The data structure to store link info.
void SetDelay(const Time &delay)
#define NS_LOG_LOGIC(msg)
Address GetMacAddress(void) const
virtual ~RouteCacheEntry()
Destructor.
Callback< void, WifiMacHeader const & > m_txErrorCallback
TX error callback.
void ProcessTxError(WifiMacHeader const &)
Process layer 2 TX error notification.
Mac48Address LookupMacAddress(Ipv4Address)
Find MAC address by IP using list of ARP caches.
uint8_t m_reqCount
Number of route requests.
bool AddRoute_Link(RouteCacheEntry::IP_VECTOR nodelist, Ipv4Address node)
static Mac48Address ConvertFrom(const Address &address)
void RemoveLastEntry(std::list< RouteCacheEntry > &rtVector)
Remove the aged route cache entries when the route cache is full.
void PrintVector(std::vector< Ipv4Address > &vec)
Print the route vector elements.
void Print(std::ostream &os) const
Print necessary fields.
DSR route request queue Since DSR is an on demand routing we queue requests while looking for route...
A record that that holds information about an ArpCache entry.
uint16_t GetAckSize()
Get the ack table size.
std::vector< Ptr< ArpCache > > m_arp
list of ARP cached to be used for layer 2 notifications processing
bool LookupRoute(Ipv4Address id, RouteCacheEntry &rt)
Lookup route cache entry with destination address dst.
Ipv4 addresses are stored in host order in this class.
uint32_t m_maxEntriesEachDst
number of entries for each destination
Timer m_ntimer
Timer for neighbor's list. Schedule Purge().
virtual ~NodeStab()
Destructor.
Time Seconds(double seconds)
create ns3::Time instances in units of seconds.
std::map< Ipv4Address, RouteCacheEntry::IP_VECTOR > m_bestRoutesTable_link
for link route cache
Time Now(void)
create an ns3::Time instance which contains the current simulation time.
#define NS_LOG_DEBUG(msg)
std::map< Ipv4Address, routeEntryVector > m_sortedRoutes
Map the ipv4Address to route entry vector.
Time m_expire
Expire time for queue entry.
Time MilliSeconds(uint64_t ms)
create ns3::Time instances in units of milliseconds.
void UpdateNetGraph()
Update the Net Graph for the link and node cache has changed.
Callback< void, Ipv4Address, uint8_t > m_handleLinkFailure
link failure callback
bool FindSameRoute(RouteCacheEntry &rt, std::list< RouteCacheEntry > &rtVector)
Find the same route in the route cache.
a base class which provides memory management and object aggregation
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 DecStability(Ipv4Address node)
decrease the stability of the node
std::vector< Neighbor > m_nb
vector of entries
routeEntryVector m_routeEntryVector
Define the route vector.
bool m_isLinkCache
Check if the route is using path cache or link cache.
a unique identifier for an interface.
bool IsNeighbor(Ipv4Address addr)
Check that node with address addr is neighbor.
Time GetExpireTime(Ipv4Address addr)
Return expire time for neighbor node with address addr, if exists, else return 0. ...
TypeId SetParent(TypeId tid)
Time m_delay
This timeout deals with the passive ack.
void AddArpCache(Ptr< ArpCache >)
Add ARP cache to be used to allow layer 2 notifications processing.
std::map< Ipv4Address, NodeStab > m_nodeCache
The data structure to store node info.
virtual ~RouteCache()
Destructor.