41 #include "ns3/simulator.h"
42 #include "ns3/ipv4-route.h"
43 #include "ns3/socket.h"
45 #include "ns3/address-utils.h"
46 #include "ns3/packet.h"
47 #include "ns3/wifi-mac-header.h"
104 typedef std::list<DsrRouteCacheEntry>::value_type
route_pair;
107 : m_ackTimer (
Timer::CANCEL_ON_DESTROY),
112 m_blackListState (false),
141 .SetGroupName (
"Dsr")
149 m_maxEntriesEachDst (3),
150 m_isLinkCache (false),
151 m_ntimer (
Timer::CANCEL_ON_DESTROY),
174 rtVector.pop_back ();
181 std::map<Ipv4Address, std::list<DsrRouteCacheEntry> >::const_iterator i =
185 NS_LOG_LOGIC (
"Failed to find the route entry for the destination " << dst);
190 std::list<DsrRouteCacheEntry> rtVector = i->second;
193 rtVector.pop_front ();
194 rtVector.push_back (successEntry);
200 std::pair<std::map<Ipv4Address, std::list<DsrRouteCacheEntry> >::iterator,
bool>
result =
220 NS_LOG_LOGIC (
"Route to " <<
id <<
" not found; m_sortedRoutes is empty");
223 std::map<Ipv4Address, std::list<DsrRouteCacheEntry> >::const_iterator i =
m_sortedRoutes.find (
id);
227 for (std::map<
Ipv4Address, std::list<DsrRouteCacheEntry> >::const_iterator j =
230 std::list<DsrRouteCacheEntry> rtVector = j->second;
234 for (std::list<DsrRouteCacheEntry>::const_iterator
k = rtVector.begin ();
k != rtVector.end (); ++
k)
244 changeVector.push_back (*l);
248 changeVector.push_back (*l);
256 if ((changeVector.size () <
routeVector.size ()) && (changeVector.size () > 1))
264 std::list<DsrRouteCacheEntry> newVector;
265 newVector.push_back (changeEntry);
268 NS_LOG_INFO (
"We have a sub-route to " <<
id <<
" add it in route cache");
273 NS_LOG_INFO (
"Here we check the route cache again after updated the sub routes");
274 std::map<Ipv4Address, std::list<DsrRouteCacheEntry> >::const_iterator m =
m_sortedRoutes.find (
id);
283 std::list<DsrRouteCacheEntry> rtVector = m->second;
284 rt = rtVector.front ();
285 NS_LOG_LOGIC (
"Route to " <<
id <<
" with route size " << rtVector.size ());
294 if (type == std::string (
"LinkCache"))
298 else if (type == std::string (
"PathCache"))
324 std::map<Ipv4Address, uint32_t> d;
326 std::map<Ipv4Address, Ipv4Address> pre;
329 if (i->second.find (source) != i->second.end ())
331 d[i->first] = i->second[source];
332 pre[i->first] = source;
345 std::map<Ipv4Address, bool> s;
348 for (uint32_t i = 0; i <
m_netGraph.size (); i++)
351 for (std::map<Ipv4Address,uint32_t>::const_iterator j = d.begin (); j != d.end (); ++j)
354 if (s.find (ip) == s.end ())
359 if (j->second <= temp)
369 for (std::map<Ipv4Address, uint32_t>::const_iterator
k =
m_netGraph[tempip].begin ();
k !=
m_netGraph[tempip].end (); ++
k)
371 if (s.find (
k->first) == s.end () && d[
k->first] > d[tempip] +
k->second)
373 d[
k->first] = d[tempip] +
k->second;
374 pre[
k->first] = tempip;
382 else if (d[
k->first] == d[tempip] +
k->second)
384 std::map<Link, DsrLinkStab>::iterator oldlink =
m_linkCache.find (
Link (
k->first, pre[
k->first]));
385 std::map<Link, DsrLinkStab>::iterator newlink =
m_linkCache.find (
Link (
k->first, tempip));
388 if (oldlink->second.GetLinkStability () < newlink->second.GetLinkStability ())
390 NS_LOG_INFO (
"Select the link with longest expected lifetime");
391 d[
k->first] = d[tempip] +
k->second;
392 pre[
k->first] = tempip;
405 for (std::map<Ipv4Address, Ipv4Address>::iterator i = pre.begin (); i != pre.end (); ++i)
411 if (!i->second.IsBroadcast () && iptemp != source)
413 while (iptemp != source)
415 route.push_back (iptemp);
416 iptemp = pre[iptemp];
418 route.push_back (source);
421 for (DsrRouteCacheEntry::IP_VECTOR::reverse_iterator j = route.rbegin (); j != route.rend (); ++j)
423 reverseroute.push_back (*j);
438 std::map<Ipv4Address, DsrRouteCacheEntry::IP_VECTOR>::const_iterator i =
m_bestRoutesTable_link.find (
id);
446 if (i->second.size () < 2)
456 NS_LOG_INFO (
"Route to " <<
id <<
" found with the length " << i->second.size ());
458 std::vector<Ipv4Address> path = rt.
GetVector ();
471 std::map<Link, DsrLinkStab>::iterator itmp = i;
472 if (i->second.GetLinkStability () <=
Seconds (0))
486 std::map<Ipv4Address, DsrNodeStab>::iterator itmp = i;
487 if (i->second.GetNodeStability () <=
Seconds (0))
509 m_netGraph[i->first.m_low][i->first.m_high] = weight;
510 m_netGraph[i->first.m_high][i->first.m_low] = weight;
518 std::map<Ipv4Address, DsrNodeStab>::const_iterator i =
m_nodeCache.find (node);
542 std::map<Ipv4Address, DsrNodeStab>::const_iterator i =
m_nodeCache.find (node);
568 for (uint32_t i = 0; i < nodelist.size () - 1; i++)
581 Link link (nodelist[i], nodelist[i + 1]);
621 for (DsrRouteCacheEntry::IP_VECTOR::iterator i = rt.begin (); i != rt.end () - 1; ++i)
623 Link link (*i, *(i + 1));
639 for (DsrRouteCacheEntry::IP_VECTOR::iterator i = rt.begin (); i != rt.end (); ++i)
650 NS_LOG_INFO (
"The node stability has already been increased");
661 std::list<DsrRouteCacheEntry> rtVector;
663 std::vector<Ipv4Address> route = rt.
GetVector ();
666 std::map<Ipv4Address, std::list<DsrRouteCacheEntry> >::const_iterator i =
671 rtVector.push_back (rt);
676 std::pair<std::map<Ipv4Address, std::list<DsrRouteCacheEntry> >::iterator,
bool>
result =
682 rtVector = i->second;
683 NS_LOG_DEBUG (
"The existing route size " << rtVector.size () <<
" for destination address " << dst);
694 NS_LOG_DEBUG (
"Find same vector, the FindSameRoute function will update the route expire time");
702 rtVector.push_back (rt);
706 NS_LOG_DEBUG (
"The first time" << rtVector.front ().GetExpireTime ().As (
Time::S) <<
" The second time "
707 << rtVector.back ().GetExpireTime ().As (
Time::S));
708 NS_LOG_DEBUG (
"The first hop" << rtVector.front ().GetVector ().size () <<
" The second hop "
709 << rtVector.back ().GetVector ().size ());
714 std::pair<std::map<Ipv4Address, std::list<DsrRouteCacheEntry> >::iterator,
bool>
result =
720 NS_LOG_INFO (
"The newly found route is already expired");
730 for (std::list<DsrRouteCacheEntry>::iterator i = rtVector.begin (); i != rtVector.end (); ++i)
738 NS_LOG_DEBUG (
"Found same routes in the route cache with the vector size "
741 <<
" the original expire time " << i->GetExpireTime ().As (
Time::S));
751 std::pair<std::map<Ipv4Address, std::list<DsrRouteCacheEntry> >::iterator,
bool>
result =
766 NS_LOG_LOGIC (
"Route deletion to " << dst <<
" successful");
769 NS_LOG_LOGIC (
"Route deletion to " << dst <<
" not successful");
785 Link link1 (errorSrc, unreachNode);
786 Link link2 (unreachNode, errorSrc);
795 std::map<Ipv4Address, DsrNodeStab>::iterator i =
m_nodeCache.find (errorSrc);
798 NS_LOG_LOGIC (
"Update the node stability unsuccessfully");
807 NS_LOG_LOGIC (
"Update the node stability unsuccessfully");
830 for (std::map<
Ipv4Address, std::list<DsrRouteCacheEntry> >::iterator j =
833 std::map<Ipv4Address, std::list<DsrRouteCacheEntry> >::iterator jtmp = j;
835 std::list<DsrRouteCacheEntry> rtVector = j->second;
839 for (std::list<DsrRouteCacheEntry>::iterator
k = rtVector.begin ();
k != rtVector.end (); )
851 changeVector.push_back (*i);
855 if (*(i + 1) == unreachNode)
857 changeVector.push_back (*i);
862 changeVector.push_back (*i);
871 NS_LOG_DEBUG (
"The route does not contain the broken link");
874 else if ((changeVector.size () <
routeVector.size ()) && (changeVector.size () > 1))
879 Time expire =
k->GetExpireTime ();
883 k = rtVector.erase (
k);
887 NS_LOG_DEBUG (
"The destination of the newly formed route " << destination <<
" and the size of the route " << changeVector.size ());
890 rtVector.push_back (changeEntry);
891 NS_LOG_DEBUG (
"We have a sub-route to " << destination);
898 k = rtVector.erase (
k);
903 NS_LOG_LOGIC (
"Cut route unsuccessful and erase the route");
907 k = rtVector.erase (
k);
915 if (rtVector.size ())
945 for (std::vector<Ipv4Address>::const_iterator i = vec.begin (); i != vec.end (); ++i)
956 for (std::list<DsrRouteCacheEntry>::iterator i = route.begin (); i != route.end (); i++)
958 std::vector<Ipv4Address> path = i->GetVector ();
974 for (std::map<
Ipv4Address, std::list<DsrRouteCacheEntry> >::iterator i =
978 std::map<Ipv4Address, std::list<DsrRouteCacheEntry> >::iterator itmp = i;
983 std::list<DsrRouteCacheEntry> rtVector = i->second;
984 NS_LOG_DEBUG (
"The route vector size of 1 " << dst <<
" " << rtVector.size ());
985 if (rtVector.size ())
987 for (std::list<DsrRouteCacheEntry>::iterator j = rtVector.begin (); j != rtVector.end (); )
989 NS_LOG_DEBUG (
"The expire time of every entry with expire time " << j->GetExpireTime ());
993 if (j->GetExpireTime () <=
Seconds (0))
998 NS_LOG_DEBUG (
"Erase the expired route for " << dst <<
" with expire time " << j->GetExpireTime ());
999 j = rtVector.erase (j);
1006 NS_LOG_DEBUG (
"The route vector size of 2 " << dst <<
" " << rtVector.size ());
1007 if (rtVector.size ())
1036 os <<
"\nDSR Route Cache\n"
1037 <<
"Destination\tGateway\t\tInterface\tFlag\tExpire\tHops\n";
1038 for (std::list<DsrRouteCacheEntry>::const_iterator i =
1054 std::map<Ipv4Address, uint16_t>::const_iterator i =
1058 NS_LOG_LOGIC (
"No Ack id for " << nextHop <<
" found and use id 1 for the first network ack id");
1065 NS_LOG_LOGIC (
"Ack id for " << nextHop <<
" found in the cache has value " << ackId);
1087 for (std::vector<Neighbor>::const_iterator i =
m_nb.begin ();
1088 i !=
m_nb.end (); ++i)
1090 if (i->m_neighborAddress == addr)
1103 for (std::vector<Neighbor>::const_iterator i =
m_nb.begin (); i
1104 !=
m_nb.end (); ++i)
1106 if (i->m_neighborAddress == addr)
1118 for (std::vector<Neighbor>::iterator i =
m_nb.begin (); i !=
m_nb.end (); ++i)
1120 for (std::vector<Ipv4Address>::iterator j = nodeList.begin (); j != nodeList.end (); ++j)
1122 if (i->m_neighborAddress == (*j))
1138 m_nb.push_back (neighbor);
1145 NS_LOG_LOGIC (
"Add neighbor number " << nodeList.size ());
1146 for (std::vector<Ipv4Address>::iterator j = nodeList.begin (); j != nodeList.end (); )
1149 if (addr == ownAddress)
1151 j = nodeList.erase (j);
1152 NS_LOG_DEBUG (
"The node list size " << nodeList.size ());
1159 m_nb.push_back (neighbor);
1190 for (std::vector<Neighbor>::iterator j =
m_nb.begin (); j !=
m_nb.end (); ++j)
1194 NS_LOG_LOGIC (
"Close link to " << j->m_neighborAddress);
1200 m_nb.erase (std::remove_if (
m_nb.begin (),
m_nb.end (), pred),
m_nb.end ());
1215 m_arp.push_back (a);
1229 i !=
m_arp.end (); ++i)
1246 for (std::vector<Neighbor>::iterator i =
m_nb.begin (); i !=
m_nb.end (); ++i)
1248 if (i->m_hardwareAddress == addr)
A record that that holds information about an ArpCache entry.
Address GetMacAddress(void) const
bool IsExpired(void) const
Ipv4 addresses are stored in host order in this class.
bool IsBroadcast(void) const
static Mac48Address ConvertFrom(const Address &address)
A base class which provides memory management and object aggregation.
Control the scheduling of simulation events.
static Time Now(void)
Return the current simulation virtual time.
Simulation virtual time values and global simulation resolution.
TimeWithUnit As(const enum Unit unit=Time::AUTO) const
Attach a unit to a Time, to facilitate output in a specific unit.
A simple virtual Timer class.
void SetDelay(const Time &delay)
void Schedule(void)
Schedule a new event using the currently-configured delay, function, and arguments.
void Cancel(void)
Cancel the currently-running event if there is one.
a unique identifier for an interface.
TypeId SetParent(TypeId tid)
Set the parent TypeId.
DsrLinkStab class (DSR link stability)
Time GetLinkStability() const
get the link stability
DsrLinkStab(Time linkStab=Simulator::Now())
Constructor.
void Print() const
Print function.
void SetLinkStability(Time linkStab)
set the link stability
virtual ~DsrLinkStab()
Destructor.
DsrNodeStab class (DSR node stability)
void SetNodeStability(Time nodeStab)
Set node stability.
DsrNodeStab(Time nodeStab=Simulator::Now())
Constructor.
DsrRouteCacheEntry class for entries in the route cache.
IP_VECTOR GetVector() const
Get the IP vector.
void SetDestination(Ipv4Address d)
Set destination address.
Time m_expire
Expire time for queue entry.
DsrRouteCacheEntry(IP_VECTOR const &ip=IP_VECTOR(), Ipv4Address dst=Ipv4Address(), Time exp=Simulator::Now())
Constructor.
Ipv4Address m_dst
The destination Ip address.
uint8_t m_reqCount
Number of route requests.
Ipv4Address GetDestination() const
Get destination address.
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.
Time GetExpireTime() const
Get expire time.
void SetExpireTime(Time exp)
Set expire time.
void SetVector(IP_VECTOR v)
Sets the IP vector.
DSR route request queue Since DSR is an on demand routing we queue requests while looking for route.
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...
uint32_t m_stabilityDecrFactor
stability decrease factor
void ProcessTxError(WifiMacHeader const &hdr)
Process layer 2 TX error notification.
std::list< DsrRouteCacheEntry::IP_VECTOR > routeVector
Define the vector of route entries.
static TypeId GetTypeId()
Get the type ID.
void PurgeLinkNode()
Purge from the cache if the stability time expired.
std::map< Link, DsrLinkStab > m_linkCache
The data structure to store link info.
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.
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.
void Purge()
Delete all outdated entries and invalidate valid entry if Lifetime is expired.
Time m_initStability
initial stability
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
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.
Time RouteCacheTimeout
The maximum period of time that dsr is allowed to for an unused route.
bool AddRoute_Link(DsrRouteCacheEntry::IP_VECTOR nodelist, Ipv4Address node)
dd route link to cache
Callback< void, WifiMacHeader const & > m_txErrorCallback
TX error callback.
std::vector< Ptr< ArpCache > > m_arp
list of ARP cached to be used for layer 2 notifications processing
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.
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.
Time m_delay
This timeout deals with the passive ack.
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
Time GetExpireTime(Ipv4Address addr)
Return expire time for neighbor node with address addr, if exists, else return 0.
Time m_useExtends
use extend
std::vector< Neighbor > m_nb
vector of entries
Time m_minLifeTime
minimum lifetime
void DelArpCache(Ptr< ArpCache >)
Don't use the provided ARP cache any more (interface is down)
void Print(std::ostream &os)
Print route cache.
Callback< void, Ipv4Address, uint8_t > m_handleLinkFailure
The following code handles link-layer acks.
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().
bool m_subRoute
Check if save the sub route entries or not.
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
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...
#define NS_LOG_COMPONENT_DEFINE(name)
Define a Log component with a specific name.
#define NS_LOG_DEBUG(msg)
Use NS_LOG to output a message of level LOG_DEBUG.
#define NS_LOG_LOGIC(msg)
Use NS_LOG to output a message of level LOG_LOGIC.
#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.
#define NS_OBJECT_ENSURE_REGISTERED(type)
Register an Object subclass with the TypeId system.
Time Now(void)
create an ns3::Time instance which contains the current simulation time.
Time Seconds(double value)
Construct a Time in the indicated unit.
Time MilliSeconds(uint64_t value)
Construct a Time in the indicated unit.
bool CompareRoutesBoth(const DsrRouteCacheEntry &a, const DsrRouteCacheEntry &b)
bool CompareRoutesExpire(const DsrRouteCacheEntry &a, const DsrRouteCacheEntry &b)
bool CompareRoutesHops(const DsrRouteCacheEntry &a, const DsrRouteCacheEntry &b)
std::list< DsrRouteCacheEntry >::value_type route_pair
Every class exported by the ns3 library is enclosed in the ns3 namespace.
Callback< R, Ts... > MakeCallback(R(T::*memPtr)(Ts...), OBJ objPtr)
Build Callbacks for class method members which take varying numbers of arguments and potentially retu...
bool operator()(const DsrRouteCache::Neighbor &nb) const
Check if the entry is expired.
Structure to manage neighbor state.
Time m_expireTime
route expire time
bool close
is route active
The route cache structure.
void Print() const
Print function.
Ipv4Address m_low
low IP address
Ipv4Address m_high
high IP address