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"
106 : m_ackTimer (
Timer::CANCEL_ON_DESTROY),
111 m_blackListState (false),
140 .AddConstructor<RouteCache> ()
147 m_maxEntriesEachDst (3),
148 m_isLinkCache (false),
149 m_ntimer (
Timer::CANCEL_ON_DESTROY),
150 m_delay (MilliSeconds (100))
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);
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))
262 std::list<RouteCacheEntry> newVector;
263 newVector.push_back (changeEntry);
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"))
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;
343 std::map<Ipv4Address, bool>
s;
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)
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 ());
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++)
579 Link link (nodelist[i], nodelist[i + 1]);
619 for (RouteCacheEntry::IP_VECTOR::iterator i = rt.begin (); i != rt.end () - 1; ++i)
621 Link link (*i, *(i + 1));
637 for (RouteCacheEntry::IP_VECTOR::iterator i = rt.begin (); i != rt.end (); ++i)
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");
700 rtVector.push_back (rt);
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 "
739 <<
" the original expire time " << i->GetExpireTime ().GetSeconds ());
749 std::pair<std::map<Ipv4Address, std::list<RouteCacheEntry> >::iterator,
bool> result =
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);
885 NS_LOG_DEBUG (
"The destination of the newly formed route " << destination <<
" and the size of the route " << changeVector.size ());
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 ())
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 ())
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 ();)
1147 if (addr == ownAddress)
1149 j = nodeList.erase (j);
1150 NS_LOG_DEBUG (
"The node list size " << nodeList.size ());
1157 m_nb.push_back (neighbor);
1181 for (std::vector<Neighbor>::iterator j =
m_nb.begin (); j !=
m_nb.end (); ++j)
1185 NS_LOG_LOGIC (
"Close link to " << j->m_neighborAddress);
1191 m_nb.erase (std::remove_if (
m_nb.begin (),
m_nb.end (), pred),
m_nb.end ());
1206 m_arp.push_back (a);
1220 i !=
m_arp.end (); ++i)
1237 for (std::vector<Neighbor>::iterator i =
m_nb.begin (); i !=
m_nb.end (); ++i)
1239 if (i->m_hardwareAddress == addr)
bool CompareRoutesBoth(const RouteCacheEntry &a, const RouteCacheEntry &b)
bool DeleteRoute(Ipv4Address dst)
Delete the route with certain destination address.
static TypeId GetTypeId()
The Route Cache used by DSR.
keep track of time values and allow control of global simulation resolution
LinkStab(Time linkStab=Simulator::Now())
Constructor.
#define NS_LOG_FUNCTION(parameters)
void PurgeMac()
Remove all expired mac entries.
NS_OBJECT_ENSURE_REGISTERED(DsrFsHeader)
Control the scheduling of simulation events.
void SetVector(IP_VECTOR v)
bool CompareRoutesHops(const RouteCacheEntry &a, const RouteCacheEntry &b)
bool IncStability(Ipv4Address node)
increase the stability of the node
Ipv4Address m_dst
The destination Ip address.
Ipv4Address GetDestination() const
void SetLinkStability(Time linkStab)
set/get the link stability
virtual ~LinkStab()
Destructor.
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.
void Print(std::ostream &os)
#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
bool CompareRoutesExpire(const RouteCacheEntry &a, const RouteCacheEntry &b)
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...
bool operator()(const RouteCache::Neighbor &nb) const
Callback< R > MakeCallback(R(T::*memPtr)(void), OBJ objPtr)
void Invalidate(Time badLinkLifetime)
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.
uint32_t m_stabilityIncrFactor
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.
Time GetLinkStability() const
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.
Time GetExpireTime() const
IP_VECTOR GetVector() const
std::vector< Ptr< ArpCache > > m_arp
list of ARP cached to be used for layer 2 notifications processing
std::list< RouteCacheEntry >::value_type route_pair
void SetExpireTime(Time exp)
bool LookupRoute(Ipv4Address id, RouteCacheEntry &rt)
Lookup route cache entry with destination address dst.
void SetNodeStability(Time nodeStab)
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.
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.
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)
NS_LOG_COMPONENT_DEFINE("RouteCache")
void SetDestination(Ipv4Address d)
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.