--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/dsr/model/dsr-rreq-table.cc Fri Jan 27 15:15:48 2012 -0800
@@ -0,0 +1,383 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) 2011 Yufei Cheng
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Author: Yufei Cheng <yfcheng@ittc.ku.edu>
+ *
+ * James P.G. Sterbenz <jpgs@ittc.ku.edu>, director
+ * ResiliNets Research Group http://wiki.ittc.ku.edu/resilinets
+ * Information and Telecommunication Technology Center (ITTC)
+ * and Department of Electrical Engineering and Computer Science
+ * The University of Kansas Lawrence, KS USA.
+ *
+ * Work supported in part by NSF FIND (Future Internet Design) Program
+ * under grant CNS-0626918 (Postmodern Internet Architecture),
+ * NSF grant CNS-1050226 (Multilayer Network Resilience Analysis and Experimentation on GENI),
+ * US Department of Defense (DoD), and ITTC at The University of Kansas.
+ */
+
+#include "dsr-rreq-table.h"
+#include "ns3/log.h"
+#include <algorithm>
+#include <iostream>
+
+NS_LOG_COMPONENT_DEFINE ("RreqTable");
+
+namespace ns3 {
+namespace dsr {
+
+NS_OBJECT_ENSURE_REGISTERED (RreqTable);
+
+TypeId RreqTable::GetTypeId ()
+{
+ static TypeId tid = TypeId ("ns3::dsr::RreqTable")
+ .SetParent<Object> ()
+ .AddConstructor<RreqTable> ()
+ ;
+ return tid;
+}
+
+RreqTable::RreqTable ()
+ : m_linkStates (PROBABLE)
+{
+}
+
+RreqTable::~RreqTable ()
+{
+ NS_LOG_FUNCTION_NOARGS ();
+}
+
+void
+RreqTable::RemoveLeastExpire (std::map<Ipv4Address, RreqTableEntry > & rreqDstMap)
+{
+ NS_LOG_FUNCTION (this);
+ Ipv4Address firstExpire;
+ Time max = Seconds (0.0);
+ for (std::map<Ipv4Address, RreqTableEntry >::const_iterator i =
+ rreqDstMap.begin (); i != rreqDstMap.end (); ++i)
+ {
+ Ipv4Address dst = i->first;
+ RreqTableEntry rreqTableEntry = i->second;
+ if (rreqTableEntry.m_expire > max)
+ {
+ max = rreqTableEntry.m_expire;
+ firstExpire = dst;
+ }
+ }
+ rreqDstMap.erase (firstExpire);
+}
+
+void
+RreqTable::FindAndUpdate (Ipv4Address dst)
+{
+ NS_LOG_LOGIC ("Find and update the route request entry for " << dst);
+ std::map<Ipv4Address, RreqTableEntry >::const_iterator i =
+ m_rreqDstMap.find (dst);
+ if (i == m_rreqDstMap.end ())
+ {
+ NS_LOG_DEBUG ("The request table entry not found");
+ /*
+ * Drop the most aged packet when buffer reaches to max
+ */
+ if (m_rreqDstMap.size () >= m_requestTableSize)
+ {
+ RemoveLeastExpire (m_rreqDstMap);
+ NS_LOG_DEBUG ("The request table size after erase ");
+ }
+ RreqTableEntry rreqTableEntry;
+ rreqTableEntry.m_reqNo = 0;
+ rreqTableEntry.m_expire = Simulator::Now ();
+ m_rreqDstMap [dst] = rreqTableEntry;
+ }
+ else
+ {
+ NS_LOG_DEBUG ("Find the request table entry, increment the request count");
+ Ipv4Address dst = i->first;
+ RreqTableEntry rreqTableEntry = i->second;
+ NS_LOG_DEBUG ("The request count before incrementing " << rreqTableEntry.m_reqNo);
+ rreqTableEntry.m_reqNo = (rreqTableEntry.m_reqNo + 1);
+ rreqTableEntry.m_expire = Simulator::Now ();
+ m_rreqDstMap [dst] = rreqTableEntry;
+ }
+}
+
+void
+RreqTable::RemoveRreqEntry (Ipv4Address dst)
+{
+ NS_LOG_DEBUG ("Remove rreq entry with index dst");
+ std::map<Ipv4Address, RreqTableEntry >::const_iterator i =
+ m_rreqDstMap.find (dst);
+ if (i == m_rreqDstMap.end ())
+ {
+ NS_LOG_DEBUG ("The request table entry not found");
+ }
+ else
+ {
+ // erase the request entry
+ m_rreqDstMap.erase (dst);
+ }
+}
+
+uint16_t
+RreqTable::GetRreqCnt (Ipv4Address dst)
+{
+ NS_LOG_DEBUG ("Get the request count for a certain dst");
+ std::map<Ipv4Address, RreqTableEntry >::const_iterator i =
+ m_rreqDstMap.find (dst);
+ if (i == m_rreqDstMap.end ())
+ {
+ NS_LOG_DEBUG ("The request table entry not found");
+ FindAndUpdate (dst);
+ return 0;
+ }
+ else
+ {
+ RreqTableEntry rreqTableEntry = i->second;
+ NS_LOG_DEBUG ("Find the request count for " << dst << " " << rreqTableEntry.m_reqNo);
+ return rreqTableEntry.m_reqNo;
+ }
+}
+
+// ----------------------------------------------------------------------------------------------------------
+/**
+ * This part takes care of the route request from a specific source
+ * need to ignore future route requests from same source for same destination with same identification
+ */
+bool
+RreqTable::FindSrc (Ipv4Address source, Ipv4Address target, uint16_t id)
+{
+ Purge ();
+ std::map<Ipv4Address, std::list<SourceRreqEntry> >::const_iterator i =
+ m_rreqMap.find (source);
+ if (i == m_rreqMap.end ())
+ {
+ NS_LOG_LOGIC ("No Request entry for " << source << " found");
+ SourceRreqEntry sourceRreqEntry;
+ sourceRreqEntry.m_dst = target;
+ sourceRreqEntry.m_identification = id;
+ sourceRreqEntry.m_expire = m_rreqEntryExpire + Simulator::Now ();
+ NS_LOG_DEBUG ("The src rreq expire time " << sourceRreqEntry.m_expire);
+ std::list<SourceRreqEntry> rqVector;
+ rqVector.push_back (sourceRreqEntry);
+ m_rreqMap[source] = rqVector;
+ return false;
+ }
+ else
+ {
+ NS_LOG_LOGIC ("Request entry for " << source << " found in the cache");
+ std::list<SourceRreqEntry> rqVector = i->second;
+ for (std::list<SourceRreqEntry>::iterator j = rqVector.begin (); j != rqVector.end (); ++j)
+ {
+ SourceRreqEntry rreqEntry = *j;
+ if ((rreqEntry.m_dst == target) && (rreqEntry.m_identification == id))
+ {
+ NS_LOG_DEBUG ("Found the request entry for source node with address " << source);
+// j = rqVector.erase (j);
+// rqVector.push_back(*j);
+// m_rreqMap[source] = rqVector;
+ return true;
+ }
+ }
+
+ SourceRreqEntry rreqEntry;
+ rreqEntry.m_dst = target;
+ rreqEntry.m_identification = id;
+ rreqEntry.m_expire = m_rreqEntryExpire + Simulator::Now ();
+ if (rqVector.size () >= m_requestIdSize)
+ {
+ // erase the first element when the size is larger than the request id size (default: 16)
+ rqVector.pop_front ();
+ }
+ // May need to check the size of the entry
+ rqVector.push_back (rreqEntry);
+ m_rreqMap[source] = rqVector;
+ return false;
+ }
+ return false;
+}
+
+void
+RreqTable::Purge ()
+{
+ //Trying to purge the rreq table
+ if (m_rreqMap.empty ())
+ {
+ NS_LOG_DEBUG ("The rreq table is empty");
+ return;
+ }
+
+ for (std::map<Ipv4Address, std::list<SourceRreqEntry> >::iterator i =
+ m_rreqMap.begin (); i != m_rreqMap.end (); )
+ {
+ // Loop of rreq table entry with the source entries
+ std::map<Ipv4Address, std::list<SourceRreqEntry> >::iterator itmp = i;
+ /*
+ * The rreq table entries
+ */
+ Ipv4Address dst = i->first;
+ std::list<SourceRreqEntry> rqVector = i->second;
+ NS_LOG_DEBUG ("The rqVector size for " << dst << " is " << rqVector.size ());
+ if (rqVector.size ())
+ {
+ for (std::list<SourceRreqEntry>::iterator j = rqVector.begin (); j != rqVector.end (); )
+ {
+ NS_LOG_DEBUG ("The expire time of every entry with expire time " << j->m_expire - Simulator::Now ());
+ /*
+ * First verify if the rreq table entry has expired or not
+ */
+ if (j->m_expire - Simulator::Now () <= Seconds (0))
+ {
+ /*
+ * When the expire time has passed, erase the certain rreq table entry
+ */
+ NS_LOG_DEBUG ("Erase the expired rreq table entry for " << dst << " with expire time " << j->m_expire - Simulator::Now ());
+ j = rqVector.erase (j);
+ }
+ else
+ {
+ ++j;
+ }
+ }
+ NS_LOG_DEBUG ("The rreq table entry for " << dst << " " << rqVector.size ());
+ if (rqVector.size ())
+ {
+ ++i;
+ m_rreqMap.erase (itmp); // erase the entry first
+ /*
+ * Save the new rreq table entry along with the destination address in map
+ */
+ std::pair<std::map<Ipv4Address, std::list<SourceRreqEntry> >::iterator, bool> result =
+ m_rreqMap.insert (std::make_pair (dst, rqVector));
+ }
+ else
+ {
+ ++i;
+ m_rreqMap.erase (itmp);
+ }
+ }
+ else
+ {
+ ++i;
+ m_rreqMap.erase (itmp);
+ }
+ }
+ return;
+}
+
+// ----------------------------------------------------------------------------------------------------------
+/**
+ * This part takes care of the route request ID initialized from a specific source to one destination
+ * Essentially a counter
+ */
+uint16_t
+RreqTable::CheckUniqueRreqId (Ipv4Address dst)
+{
+ NS_LOG_DEBUG ("The size of id cache " << m_rreqIdCache.size ());
+ std::map<Ipv4Address, uint16_t>::const_iterator i =
+ m_rreqIdCache.find (dst);
+ if (i == m_rreqIdCache.end ())
+ {
+ NS_LOG_LOGIC ("No Request id for " << dst << " found");
+ m_rreqIdCache[dst] = 0;
+ return 0;
+ }
+ else
+ {
+ NS_LOG_LOGIC ("Request id for " << dst << " found in the cache");
+ uint16_t rreqId = m_rreqIdCache[dst];
+ if (rreqId >= m_maxRreqId)
+ {
+ NS_LOG_DEBUG ("The request id increase past the max value, so reset it to 0");
+ rreqId = 0;
+ m_rreqIdCache[dst] = rreqId;
+ }
+ else
+ {
+ rreqId++;
+ m_rreqIdCache[dst] = rreqId;
+ }
+ NS_LOG_DEBUG ("The Request id for " << dst << " is " << rreqId);
+ return rreqId;
+ }
+}
+
+uint16_t
+RreqTable::GetRreqSize ()
+{
+ return m_rreqIdCache.size ();
+}
+
+// ----------------------------------------------------------------------------------------------------------
+/**
+ * This part takes care of black list which can save unidirectional link information
+ */
+
+void
+RreqTable::Invalidate ()
+{
+ if (m_linkStates == QUESTIONABLE)
+ {
+ return;
+ }
+ m_linkStates = QUESTIONABLE;
+}
+
+BlackList*
+RreqTable::FindUnidirectional (Ipv4Address neighbor)
+{
+ PurgeNeighbor (); // purge the neighbor cache
+ for (std::vector<BlackList>::iterator i = m_blackList.begin ();
+ i != m_blackList.end (); ++i)
+ {
+ if (i->m_neighborAddress == neighbor)
+ {
+ return &(*i);
+ }
+ }
+ return NULL;
+}
+
+bool
+RreqTable::MarkLinkAsUnidirectional (Ipv4Address neighbor, Time blacklistTimeout)
+{
+ NS_LOG_LOGIC ("Add neighbor address in blacklist " << m_blackList.size ());
+ for (std::vector<BlackList>::iterator i = m_blackList.begin (); i != m_blackList.end (); ++i)
+ {
+ if (i->m_neighborAddress == neighbor)
+ {
+ NS_LOG_DEBUG ("Update the blacklist list timeout if found the blacklist entry");
+ i->m_expireTime = std::max (blacklistTimeout + Simulator::Now (), i->m_expireTime);
+ }
+ BlackList blackList (neighbor, blacklistTimeout + Simulator::Now ());
+ m_blackList.push_back (blackList);
+ PurgeNeighbor ();
+ return true;
+ }
+ return false;
+}
+
+void
+RreqTable::PurgeNeighbor ()
+{
+ /*
+ * Purge the expired blacklist entries
+ */
+ m_blackList.erase (remove_if (m_blackList.begin (), m_blackList.end (),
+ IsExpired ()), m_blackList.end ());
+}
+
+} // namespace dsr
+} // namespace ns3