First approximation of PIT
diff --git a/model/ccnx-fib.cc b/model/ccnx-fib.cc
index 14c6138..fa972a0 100644
--- a/model/ccnx-fib.cc
+++ b/model/ccnx-fib.cc
@@ -89,8 +89,20 @@
NS_ASSERT_MSG (record != m_faces.get<i_face> ().end (), "Update status can be performed only on existing faces of CcxnFibEntry");
m_faces.modify (record, ChangeStatus (status));
+
+ // reordering random access index same way as by metric index
+ m_faces.get<i_nth> ().rearrange (m_faces.get<i_metric> ().begin ());
}
+
+Ptr<CcnxFace>
+CcnxFibEntry::FindBestCandidate (int skip/* = 0*/)
+{
+ skip = skip % m_faces.size();
+ return m_faces.get<i_nth> () [skip].GetFace ();
+}
+
+
CcnxFib::CcnxFib (Ptr<Ccnx> node)
: m_node (node)
{
diff --git a/model/ccnx-fib.h b/model/ccnx-fib.h
index 90d5ec8..bc559c6 100644
--- a/model/ccnx-fib.h
+++ b/model/ccnx-fib.h
@@ -24,12 +24,14 @@
#include "hash-helper.h"
#include "ccnx-face.h"
#include "ns3/nstime.h"
+#include "ns3/simple-ref-count.h"
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/tag.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/composite_key.hpp>
#include <boost/multi_index/hashed_index.hpp>
+#include <boost/multi_index/random_access_index.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/mem_fun.hpp>
@@ -45,6 +47,7 @@
class i_face {};
class i_metric {};
+class i_nth {};
class i_prefix {};
}
@@ -78,6 +81,9 @@
bool
operator< (const CcnxFibFaceMetric &m) const { return *m_face < *(m.m_face); } // return identity of the face
+ Ptr<CcnxFace>
+ GetFace () const { return m_face; }
+
private:
friend std::ostream& operator<< (std::ostream& os, const CcnxFibFaceMetric &metric);
public:
@@ -101,6 +107,8 @@
* Currently, there are 2 indexes:
* - by face (used to find record and update metric)
* - by metric (face ranking)
+ * - random access index (for fast lookup on nth face). Order is
+ * maintained manually to be equal to the 'by metric' order
*/
struct CcnxFibFaceMetricContainer
{
@@ -121,6 +129,11 @@
boost::multi_index::member<CcnxFibFaceMetric,uint8_t,&CcnxFibFaceMetric::m_status>,
boost::multi_index::member<CcnxFibFaceMetric,uint32_t,&CcnxFibFaceMetric::m_routingCost>
>
+ >,
+
+ // To optimize nth candidate selection (sacrifice a little bit space to gain speed)
+ boost::multi_index::random_access<
+ boost::multi_index::tag<__ccnx_private_fib::i_nth>
>
>
> type;
@@ -131,7 +144,7 @@
* \brief Structure for FIB table entry, holding indexed list of
* available faces and their respective metrics
*/
-class CcnxFibEntry
+class CcnxFibEntry : public SimpleRefCount<CcnxFibEntry>
{
public:
/**
@@ -153,8 +166,14 @@
* \brief Get prefix for the FIB entry
*/
const CcnxNameComponents&
- GetName () const { return *m_prefix; }
+ GetPrefix () const { return *m_prefix; }
+ /**
+ * \brief Find "best route" candidate, skipping `skip' first candidates (modulo # of faces)
+ */
+ Ptr<CcnxFace>
+ FindBestCandidate (int skip = 0);
+
private:
friend std::ostream& operator<< (std::ostream& os, const CcnxFibEntry &entry);
@@ -185,7 +204,7 @@
boost::multi_index::tag<__ccnx_private_fib::i_prefix>,
boost::multi_index::const_mem_fun<CcnxFibEntry,
const CcnxNameComponents&,
- &CcnxFibEntry::GetName>,
+ &CcnxFibEntry::GetPrefix>,
CcnxPrefixHash>
// other indexes?
diff --git a/model/ccnx-pit-entry-incoming-face.cc b/model/ccnx-pit-entry-incoming-face.cc
new file mode 100644
index 0000000..0c65549
--- /dev/null
+++ b/model/ccnx-pit-entry-incoming-face.cc
@@ -0,0 +1,34 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2011 University of California, Los Angeles
+ *
+ * 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: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#include "ccnx-pit-entry-incoming-face.h"
+
+#include "ns3/simulator.h"
+
+namespace ns3 {
+
+CcnxPitEntryIncomingFace::CcnxPitEntryIncomingFace (Ptr<CcnxFace> face)
+ : m_face (face)
+ , m_arrivalTime (Simulator::Now ())
+ // , m_nonce (nonce)
+{
+}
+
+} // namespace ns3
diff --git a/model/ccnx-pit-entry-incoming-face.h b/model/ccnx-pit-entry-incoming-face.h
new file mode 100644
index 0000000..80f7e09
--- /dev/null
+++ b/model/ccnx-pit-entry-incoming-face.h
@@ -0,0 +1,62 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2011 University of California, Los Angeles
+ *
+ * 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: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef _CCNX_PIT_ENTRY_INCOMING_FACE_H_
+#define _CCNX_PIT_ENTRY_INCOMING_FACE_H_
+
+#include "ns3/nstime.h"
+#include "ns3/ptr.h"
+
+#include "ccnx-face.h"
+// #include <iostream>
+
+namespace ns3 {
+
+/**
+ * \ingroup ccnx
+ * \brief PIT state component for each incoming interest (not including duplicates)
+ */
+struct CcnxPitEntryIncomingFace
+{
+ Ptr<CcnxFace> m_face; ///< \brief face of the incoming Interest
+ Time m_arrivalTime; ///< \brief arrival time of the incoming Interest
+
+public:
+ /**
+ * \brief Constructor
+ * \param face face of the incoming interest
+ * \param lifetime lifetime of the incoming interest
+ */
+ CcnxPitEntryIncomingFace (Ptr<CcnxFace> face);
+
+ bool operator== (const CcnxPitEntryIncomingFace &dst) { return *m_face==*(dst.m_face); }
+ bool operator== (Ptr<CcnxFace> face) { return *m_face==*face; }
+
+ /**
+ * \brief Comparison operator used by boost::multi_index::identity<>
+ */
+ bool
+ operator< (const CcnxPitEntryIncomingFace &m) const { return *m_face < *(m.m_face); } // return identity of the face
+};
+
+
+} // namespace ns3
+
+#endif /* CCNX_PIT_ENTRY_INCOMING_FACE_H */
diff --git a/model/ccnx-pit-entry-outgoing-face.cc b/model/ccnx-pit-entry-outgoing-face.cc
new file mode 100644
index 0000000..c15df71
--- /dev/null
+++ b/model/ccnx-pit-entry-outgoing-face.cc
@@ -0,0 +1,37 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2011 University of California, Los Angeles
+ *
+ * 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: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#include "ccnx-pit-entry-outgoing-face.h"
+
+#include "ns3/simulator.h"
+
+namespace ns3 {
+
+CcnxPitEntryOutgoingFace::CcnxPitEntryOutgoingFace (Ptr<CcnxFace> face)
+ : m_face (face)
+ , m_sendTime (Simulator::Now ())
+ // , m_retxNum (0)
+ // , m_nonce (nonce)
+ // , m_outstanding (true)
+ // , m_waitingInVain (false)
+{
+}
+
+} // namespace ns3
diff --git a/model/ccnx-pit-entry-outgoing-face.h b/model/ccnx-pit-entry-outgoing-face.h
new file mode 100644
index 0000000..d5fc4da
--- /dev/null
+++ b/model/ccnx-pit-entry-outgoing-face.h
@@ -0,0 +1,62 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2011 University of California, Los Angeles
+ *
+ * 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: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef _CCNX_PIT_ENTRY_OUTGOING_FACE_H_
+#define _CCNX_PIT_ENTRY_OUTGOING_FACE_H_
+
+#include "ns3/nstime.h"
+#include "ns3/ptr.h"
+
+#include "ccnx-face.h"
+
+namespace ns3 {
+
+/**
+ * \ingroup ccnx
+ * \brief PIT state component for each outgoing interest
+ */
+struct CcnxPitEntryOutgoingFace
+{
+ Ptr<CcnxFace> m_face; ///< \brief face of the outgoing Interest
+ Time m_sendTime; ///< \brief time when the first outgoing interest is sent (for RTT measurements)
+ ///< \todo handle problem of retransmitted interests... Probably, we should include something similar
+ ///< to TimeStamp TCP option for retransmitted (i.e., only lost interests will suffer)
+ // int m_retxNum; ///< \brief number of retransmission
+ // int m_nonce; ///< \brief nonce of the outgoing Interest
+ // bool m_outstanding; ///< \brief flag to indicate that this interest is currently pending
+ // bool m_waitingInVain; ///< \brief when flag is set, we do not expect data for this interest, only a small hope that it will happen
+
+public:
+ CcnxPitEntryOutgoingFace (Ptr<CcnxFace> face);
+
+ bool operator== (const CcnxPitEntryOutgoingFace &dst) { return *m_face==*dst.m_face; }
+ bool operator== (Ptr<CcnxFace> face) { return *m_face==*face; }
+
+ /**
+ * \brief Comparison operator used by boost::multi_index::identity<>
+ */
+ bool
+ operator< (const CcnxPitEntryOutgoingFace &m) const { return *m_face < *(m.m_face); } // return identity of the face
+};
+
+
+} // namespace ns3
+
+#endif /* CCNX_PIT_ENTRY_OUTGOING_FACE_H */
diff --git a/model/ccnx-pit-entry.cc b/model/ccnx-pit-entry.cc
new file mode 100644
index 0000000..a6629d0
--- /dev/null
+++ b/model/ccnx-pit-entry.cc
@@ -0,0 +1,119 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2011 University of California, Los Angeles
+ *
+ * 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: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#include "ccnx-pit-entry.h"
+#include "ccnx-name-components.h"
+#include "ccnx-fib.h"
+
+namespace ns3
+{
+
+// struct SearchByFace
+// {
+// /**
+// * \brief To perform effective searches by CcnxFace
+// */
+// bool
+// operator() (const CcnxPitIncomingInterest &m, const Ptr<CcnxFace> &face) const
+// {
+// return *(m.m_face) < *face;
+// }
+
+// /**
+// * \brief To perform effective searches by CcnxFace
+// */
+// bool
+// operator() (const Ptr<CcnxFace> &face, const CcnxPitIncomingInterest &m) const
+// {
+// return *face < *(m.m_face);
+// }
+
+// /**
+// * \brief To perform effective searches by CcnxFace
+// */
+// bool
+// operator() (const CcnxPitOutgoingInterest &m, const Ptr<CcnxFace> &face) const
+// {
+// return *(m.m_face) < *face;
+// }
+
+// /**
+// * \brief To perform effective searches by CcnxFace
+// */
+// bool
+// operator() (const Ptr<CcnxFace> &face, const CcnxPitOutgoingInterest &m) const
+// {
+// return *face < *(m.m_face);
+// }
+// };
+
+
+CcnxPitEntry::CcnxPitEntry (Ptr<CcnxNameComponents> prefix)
+ : m_prefix (prefix)
+ , m_fib (0)
+ // , m_expireTime (?)
+ , m_timerExpired (false)
+ , m_counterExpirations (0)
+{
+}
+
+const CcnxNameComponents &
+CcnxPitEntry::GetPrefix () const
+{
+ return *m_prefix;
+}
+
+CcnxPitEntry::SetFibEntry::SetFibEntry (Ptr<CcnxFibEntry> fib)
+ : m_fib (fib)
+{
+}
+
+void
+CcnxPitEntry::SetFibEntry::operator() (CcnxPitEntry &entry)
+{
+ entry.m_fib = m_fib;
+}
+
+void
+CcnxPitEntry::AddIncoming::operator() (CcnxPitEntry &entry)
+{
+ entry.m_incoming.insert (CcnxPitEntryIncomingFace (m_face));
+}
+
+void
+CcnxPitEntry::AddOutgoing::operator() (CcnxPitEntry &entry)
+{
+ entry.m_outgoing.insert (CcnxPitEntryOutgoingFace (m_face));
+}
+
+void
+CcnxPitEntry::DeleteIncoming::operator() (CcnxPitEntry &entry)
+{
+ entry.m_incoming.erase (m_face);
+}
+
+void
+CcnxPitEntry::ClearIncoming::operator() (CcnxPitEntry &entry)
+{
+ entry.m_incoming.clear ();
+}
+
+
+}
diff --git a/model/ccnx-pit-entry.h b/model/ccnx-pit-entry.h
new file mode 100644
index 0000000..5da3c4c
--- /dev/null
+++ b/model/ccnx-pit-entry.h
@@ -0,0 +1,199 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2011 University of California, Los Angeles
+ *
+ * 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: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef _CCNX_PIT_ENTRY_H_
+#define _CCNX_PIT_ENTRY_H_
+
+#include "ns3/ptr.h"
+
+#include "ccnx-pit-entry-incoming-face.h"
+#include "ccnx-pit-entry-outgoing-face.h"
+#include "ccnx-fib.h"
+
+#include <boost/multi_index_container.hpp>
+#include <boost/multi_index/tag.hpp>
+#include <boost/multi_index/ordered_index.hpp>
+#include <boost/multi_index/composite_key.hpp>
+#include <boost/multi_index/hashed_index.hpp>
+#include <boost/multi_index/member.hpp>
+#include <boost/multi_index/mem_fun.hpp>
+
+#include <iostream>
+
+namespace ns3 {
+
+class CcnxFace;
+class CcnxNameComponents;
+
+namespace __ccnx_private
+{
+class i_face {};
+}
+
+/**
+ * \ingroup ccnx
+ * \brief Typedef for indexed face container of CcnxPitEntryIncomingFace
+ *
+ * Indexes:
+ * - by face (may be it will be possible to replace with just the std::map)
+ */
+struct CcnxPitEntryIncomingFaceContainer
+{
+ typedef boost::multi_index::multi_index_container<
+ CcnxPitEntryIncomingFace,
+ boost::multi_index::indexed_by<
+ // For fast access to elements using CcnxFace
+ boost::multi_index::ordered_unique<
+ boost::multi_index::tag<__ccnx_private::i_face>,
+ boost::multi_index::identity<CcnxPitEntryIncomingFace>
+ >
+ >
+ > type;
+};
+
+/**
+ * \ingroup ccnx
+ * \brief Typedef for indexed face container of CcnxPitEntryOutgoingFace
+ *
+ * Indexes:
+ * - by face (may be it will be possible to replace with just the std::map)
+ */
+struct CcnxPitEntryOutgoingFaceContainer
+{
+ typedef boost::multi_index::multi_index_container<
+ CcnxPitEntryOutgoingFace,
+ boost::multi_index::indexed_by<
+ // For fast access to elements using CcnxFace
+ boost::multi_index::ordered_unique<
+ boost::multi_index::tag<__ccnx_private::i_face>,
+ boost::multi_index::identity<CcnxPitEntryOutgoingFace>
+ >
+ >
+ > type;
+};
+
+
+/**
+ * \ingroup ccnx
+ * \brief structure for PIT entry
+ */
+struct CcnxPitEntry
+{
+public:
+ /**
+ * \brief PIT entry constructor
+ * \param prefix Prefix of the PIT entry
+ * \param fib A FIB entry associated with the PIT entry
+ */
+ CcnxPitEntry (Ptr<CcnxNameComponents> prefix);
+
+ // // Get number of outgoing interests that we're expecting data from
+ // inline size_t numberOfPromisingInterests( ) const;
+
+ /**
+ * \brief Unary function to set or update FIB entry with this PIT entry
+ * \param fib smart pointer to FIB entry
+ */
+ struct SetFibEntry
+ {
+ SetFibEntry (Ptr<CcnxFibEntry> fib);
+ void operator() (CcnxPitEntry &entry);
+ private:
+ Ptr<CcnxFibEntry> m_fib;
+ };
+
+ /**
+ * \brief Unary Function to add incoming interest to the PIT entry
+ *
+ * \param incomingFace smart pointer to the face of the incoming interest
+ * \returns const iterator to a newly added or updated
+ * CcnxPitIncomingInterest entry
+ */
+ struct AddIncoming
+ {
+ AddIncoming (Ptr<CcnxFace> incomingFace) : m_face (incomingFace) {}
+ void operator() (CcnxPitEntry &entry);
+
+ private:
+ Ptr<CcnxFace> m_face;
+ Time m_lifeTime;
+ };
+
+ /**
+ * \brief Unary function to add outgoing interest to PIT entry
+ *
+ * \param outgoingFace smart pointer to the face of the outgoing interest
+ * \returns const iterator to a newly added or updated
+ * CcnxPitOutgoingInterest entry
+ */
+ struct AddOutgoing
+ {
+ AddOutgoing (Ptr<CcnxFace> outgoingFace) : m_face (outgoingFace) {}
+ void operator() (CcnxPitEntry &entry);
+ private:
+ Ptr<CcnxFace> m_face;
+ };
+
+ /**
+ * \brief Unary function to delete incoming interest for the interface
+ * \param face face that should be removed from the list of incoming interests
+ */
+ struct DeleteIncoming
+ {
+ DeleteIncoming (Ptr<CcnxFace> face) : m_face (face) {}
+ void operator() (CcnxPitEntry &entry);
+ private:
+ Ptr<CcnxFace> m_face;
+ };
+
+ /**
+ * \brief Unary function to remove all incoming interests
+ */
+ struct ClearIncoming
+ {
+ ClearIncoming ();
+ void operator() (CcnxPitEntry &entry);
+ };
+
+ const CcnxNameComponents &
+ GetPrefix () const;
+
+ const Time &
+ GetExpireTime () const { return m_expireTime; }
+
+private:
+ friend std::ostream& operator<< (std::ostream& os, const CcnxPitEntry &entry);
+
+private:
+ Ptr<CcnxNameComponents> m_prefix; ///< \brief Prefix of the PIT entry
+ Ptr<CcnxFibEntry> m_fib; ///< \brief FIB entry related to this prefix
+
+ CcnxPitEntryIncomingFaceContainer::type m_incoming; ///< \brief container for incoming interests
+ CcnxPitEntryOutgoingFaceContainer::type m_outgoing; ///< \brief container for outgoing interests
+
+ Time m_expireTime; ///< \brief Time when PIT entry will be removed
+ bool m_timerExpired; ///< \brief flag indicating that PIT timer has expired
+ int m_counterExpirations; ///< \brief whether timer is expired (+ number of times timer expired)
+};
+
+
+} // namespace ns3
+
+#endif // _CCNX_PIT_ENTRY_H_
diff --git a/model/ccnx-pit.cc b/model/ccnx-pit.cc
new file mode 100644
index 0000000..7ee9d83
--- /dev/null
+++ b/model/ccnx-pit.cc
@@ -0,0 +1,137 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2011 University of California, Los Angeles
+ *
+ * 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: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#include "ccnx-pit.h"
+#include "ns3/log.h"
+#include "ns3/simulator.h"
+#include "ccnx-interest-header.h"
+#include "ccnx-content-object-header.h"
+
+NS_LOG_COMPONENT_DEFINE ("CcnxPit");
+
+namespace ns3 {
+
+NS_OBJECT_ENSURE_REGISTERED (CcnxPit);
+
+using namespace __ccnx_private;
+
+// size_t
+// PitEntry::numberOfPromisingInterests(e_pi ) const
+// {
+// size_t count = 0;
+
+// BOOST_FOREACH (const CcnxPitOutgoingInterest &interest, m_outgoingInterests)
+// {
+// }
+// for( PitOutgoingConstIterator i = outgoingInterests.begin();
+// i!=outgoingInterests.end();
+// i++ )
+// {
+// if( !i->waitingInVain ) count++;
+// }
+
+// return count;
+// }
+
+TypeId
+CcnxPit::GetTypeId ()
+{
+ static TypeId tid = TypeId ("ns3::CcnxPit")
+ .SetGroupName ("Ccnx")
+ .SetParent<Object> ()
+ .AddConstructor<CcnxPit> ()
+ .AddAttribute ("CleanupTimeout",
+ "Timeout defining how frequent RIT should be cleaned up",
+ TimeValue (Seconds (1)),
+ MakeTimeAccessor (&CcnxPit::GetCleanupTimeout, &CcnxPit::SetCleanupTimeout),
+ MakeTimeChecker ())
+ ;
+
+ return tid;
+}
+
+CcnxPit::CcnxPit ()
+{
+}
+
+void
+CcnxPit::SetCleanupTimeout (const Time &timeout)
+{
+ m_cleanupTimeout = timeout;
+ if (m_cleanupEvent.IsRunning ())
+ m_cleanupEvent.Cancel (); // cancel any scheduled cleanup events
+
+ // schedule even with new timeout
+ m_cleanupEvent = Simulator::Schedule (Simulator::Now () + m_cleanupTimeout,
+ &CcnxPit::CleanExpired, this);
+}
+
+Time
+CcnxPit::GetCleanupTimeout () const
+{
+ return m_cleanupTimeout;
+}
+
+void CcnxPit::CleanExpired ()
+{
+ NS_LOG_LOGIC ("Cleaning PIT");
+ Time now = Simulator::Now ();
+
+ while( !m_pit.empty() )
+ {
+ if( m_pit.get<i_timestamp> ().front ().GetExpireTime () <= now ) // is the record stale?
+ {
+ m_pit.get<i_timestamp> ().pop_front( );
+ }
+ else
+ break; // nothing else to do. All later records will not be stale
+ }
+
+ // schedule next even
+ m_cleanupEvent = Simulator::Schedule (Simulator::Now () + m_cleanupTimeout,
+ &CcnxPit::CleanExpired, this);
+}
+
+const CcnxPitEntry&
+CcnxPit::Lookup (const CcnxContentObjectHeader &header) const
+{
+ CcnxPitEntryContainer::type::iterator entry =
+ m_pit.get<i_prefix> ().find (header.GetName ());
+
+ if (entry != m_pit.end ())
+ throw CcnxPitEntryNotFound();
+
+ return *entry;
+}
+
+const CcnxPitEntry&
+CcnxPit::Lookup (const CcnxInterestHeader &header) const
+{
+ CcnxPitEntryContainer::type::iterator entry =
+ m_pit.get<i_prefix> ().find (header.GetName ());
+
+ // if (entry != m_pit.end ())
+ // entry = m_pit.insert (m_pit.end (), CcnxPitEntry (Create<CcnxNameComponents> (header.GetName ())));
+
+ return *entry;
+}
+
+
+} // namespace ns3
diff --git a/model/ccnx-pit.cpp b/model/ccnx-pit.cpp
new file mode 100644
index 0000000..5d10b90
--- /dev/null
+++ b/model/ccnx-pit.cpp
@@ -0,0 +1,243 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+//
+// Copyright (c) 2010,2011 UCLA
+//
+// 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:
+//
+
+#include "ccnx-pit.h"
+#include <algorithm>
+
+CcnxPit::CcnxPit( Ccnx &node )
+: _node(node)
+{
+};
+
+CcnxPit::~CcnxPit( ) { }
+
+//Find corresponding CS entry for the given content name
+PitIterator CcnxPit::lookup( const string &prefix )
+{
+ QNThreadLock lock( &_pitMutex );
+
+ PitIterator entry=_pit.find( prefix );
+ return entry;
+}
+
+// add new PIT entry
+bool CcnxPit::add( const string &name, const PitIncomingInterest &interest )
+{
+ QNThreadLock lock( &_pitMutex );
+
+ PitEntry *entry=NULL;
+
+ PitIterator existent_entry = _pit.find( name );
+ if( isValid(existent_entry) )
+ {
+ if( VALUE(existent_entry).timerExpired )
+ {
+ _node.fillAvailableInterfacesInPitEntry( VALUE(existent_entry) );
+ }
+
+ add( VALUE(existent_entry), interest );
+ }
+ else
+ {
+ PitEntry &entry = _pit[ name ];
+ entry.contentName = name;
+
+ _node.fillAvailableInterfacesInPitEntry( entry );
+
+ add( entry, interest );
+ }
+}
+
+// Remove expired records from PIT
+void CcnxPit::cleanExpired( clocktype time )
+{
+ QNThreadLock lock( &_pitMutex );
+
+ while( !_pitExpirationList.empty() )
+ {
+ PitExpirationIterator entry = _pitExpirationList.begin( );
+
+ if( VALUE(entry)->expireTime <= time )
+ {
+ deleteIncomingInterest( *(KEY(entry)), VALUE(entry)->interfaceIndex );
+
+ // delete entry if all incoming interests expired
+ if( KEY(entry)->incomingInterests.size()==0 )
+ {
+ _pit.erase( KEY(entry)->contentName );
+ }
+ }
+ else
+ break;
+ }
+}
+
+//delete PIT entry
+void CcnxPit::erase( const string &name )
+{
+ // should not call `lookup' method !!!
+
+ QNThreadLock lock( &_pitMutex );
+
+ PitIterator pe = _pit.find( name );
+
+ if( !isValid(pe) ) return;
+
+ if( VALUE(pe).timerMsg ) MESSAGE_CancelSelfMsg( _node.getNode(), VALUE(pe).timerMsg );
+
+ PitIncomingIterator it = VALUE(pe).incomingInterests.begin();
+ while( it!=VALUE(pe).incomingInterests.end() )
+ {
+ deleteIncomingInterest( VALUE(pe), it );
+
+ it = VALUE(pe).incomingInterests.begin();
+ }
+
+ resetPendingState( VALUE(pe) );
+
+ _pit.erase( name );
+}
+
+//delete incoming interest from PIT entry
+//return 0 if interest does not exist, 1 otherwise
+bool CcnxPit::deleteIncomingInterest( PitEntry &pe, int interfaceIndex )
+{
+ // should not lock thread !!! Otherwise there will be a deadlock
+ if( pe.incomingInterests.size()==0 ) return false; //nothing to delete. Can happen when duplicate data arrives to the node
+
+ PitIncomingIterator it = findIncoming( pe, interfaceIndex );
+
+ if( !isValid(pe, it) ) return false;
+
+ deleteIncomingInterest( pe, it );
+
+ return true;
+}
+
+void CcnxPit::deleteAllIncomingInterests( PitEntry &pe )
+{
+ PitIncomingIterator it = pe.incomingInterests.begin();
+ while( it!=pe.incomingInterests.end() )
+ {
+ deleteIncomingInterest( pe, it );
+
+ it = pe.incomingInterests.begin();
+ }
+}
+
+void CcnxPit::deleteIncomingInterest( PitEntry &pe, PitIncomingIterator it )
+{
+ assert( KEY(it->expirationPosition)==&pe );
+ assert( VALUE(it->expirationPosition)->interfaceIndex==it->interfaceIndex );
+
+ _pitExpirationList.erase( it->expirationPosition );
+ pe.incomingInterests.erase( it );
+}
+
+//add new incoming interest to PIT entry
+//returns false if interface already exists, true otherwise
+bool CcnxPit::add( PitEntry &pe, const PitIncomingInterest &interest )
+{
+ pe.availableInterfaces.remove( interest.interfaceIndex );
+
+ PitIncomingIterator it=findIncoming( pe, interest.interfaceIndex );
+
+ if( isValid(pe, it) )
+ {
+ //update expiration time
+ it->expireTime = interest.expireTime;
+ it->nonce = interest.nonce;
+
+ //move Interest to the end of the node's Interest list
+ _pitExpirationList.erase( it->expirationPosition );
+ _pitExpirationList.push_back( PitExpirationEntry(&pe,&(*it)) );
+
+ it->expirationPosition = --_pitExpirationList.end();
+ return false;
+ }
+
+ pe.incomingInterests.push_back( interest );
+ PitIncomingInterest *incoming = &pe.incomingInterests.back();
+
+ //Add to the end of the node's Interest list
+ _pitExpirationList.push_back( PitExpirationEntry(&pe,incoming) );
+ incoming->expirationPosition = -- _pitExpirationList.end();
+
+ return true;
+}
+
+//add new outgoing interest to PIT entry
+//returns false interface limit reached or interest exists and is still marked as outstanding (nonce will not be changed)
+// true otherwise
+int CcnxPit::add( PitEntry &pe, const PitOutgoingInterest &interest )
+{
+ if( _node.isRateLimit && _bucketsPerInterface[interest.interfaceIndex]+1.0 >= maxBucketsPerInterface[interest.interfaceIndex] )
+ {
+// printf( "DEBUG: bucket overflow. Should not forward anything to interface %d\n", interest.interfaceIndex );
+ return false;
+ }
+
+ _bucketsPerInterface[interest.interfaceIndex] = _bucketsPerInterface[interest.interfaceIndex] + 1.0;
+ pe.availableInterfaces.remove( interest.interfaceIndex );
+
+ PitOutgoingIterator it = findOutgoing(pe, interest.interfaceIndex);
+ if( isValid(pe, it) )
+ {
+ if( it->outstanding ) return false;
+
+ it->retxNum ++;
+ it->nonce = interest.nonce;
+ it->outstanding = true;
+ it->waitingInVain = false;
+ }
+ else
+ {
+ //add to the head of the list
+ pe.outgoingInterests.push_front( interest );
+ }
+
+ return true;
+}
+
+void CcnxPit::resetPendingState( PitEntry &pe )
+{
+ for( PitOutgoingIterator it = pe.outgoingInterests.begin();
+ it != pe.outgoingInterests.end();
+ it++ )
+ {
+ it->outstanding = false;
+ }
+}
+
+void CcnxPit::leakBuckets( )
+{
+ for( PitBucketIterator it=_bucketsPerInterface.begin();
+ it != _bucketsPerInterface.end();
+ it++ )
+ {
+ it->second = max( 0.0, it->second - leakSize[it->first] );
+ }
+}
+
+void CcnxPit::leakBucket( int interface, int amount )
+{
+ _bucketsPerInterface[interface] =
+ max( 0.0, _bucketsPerInterface[interface] - amount );
+}
diff --git a/model/ccnx-pit.h b/model/ccnx-pit.h
new file mode 100644
index 0000000..3ffadad
--- /dev/null
+++ b/model/ccnx-pit.h
@@ -0,0 +1,197 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2011 University of California, Los Angeles
+ *
+ * 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: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef _CCNX_PIT_H_
+#define _CCNX_PIT_H_
+
+#include "ns3/nstime.h"
+#include "ns3/event-id.h"
+
+#include "hash-helper.h"
+#include "ccnx-pit-entry.h"
+
+#include <boost/multi_index_container.hpp>
+#include <boost/multi_index/tag.hpp>
+#include <boost/multi_index/ordered_index.hpp>
+#include <boost/multi_index/composite_key.hpp>
+#include <boost/multi_index/hashed_index.hpp>
+#include <boost/multi_index/member.hpp>
+#include <boost/multi_index/mem_fun.hpp>
+#include <boost/multi_index/sequenced_index.hpp>
+
+#include <iostream>
+
+namespace ns3 {
+
+class Ccnx;
+class CcnxFace;
+class CcnxContentObjectHeader;
+class CcnxInterestHeader;
+
+/**
+ * \ingroup ccnx
+ * \private
+ * \brief Private namespace for CCNx PIT implementation
+ */
+namespace __ccnx_private
+{
+class i_prefix{}; ///< tag for prefix hash
+class i_timestamp {}; ///< tag for timestamp-ordered records (for cleanup optimization)
+};
+
+/**
+ * \ingroup ccnx
+ * \brief Typedef for RIT container implemented as a Boost.MultiIndex container
+ *
+ * - First index (tag<i_prefix>) is a unique hash index based on
+ * prefixes
+ * - Second index (tag<i_timestamp>) is a sequenced index based on
+ * arrival order (for clean-up optimizations)
+ *
+ * \see http://www.boost.org/doc/libs/1_46_1/libs/multi_index/doc/ for more information on Boost.MultiIndex library
+ */
+struct CcnxPitEntryContainer
+{
+ typedef
+ boost::multi_index::multi_index_container<
+ CcnxPitEntry,
+ boost::multi_index::indexed_by<
+ // indexed by hash
+ boost::multi_index::hashed_unique<
+ boost::multi_index::tag<__ccnx_private::i_prefix>,
+ boost::multi_index::const_mem_fun<CcnxPitEntry, const CcnxNameComponents&, &CcnxPitEntry::GetPrefix>,
+ CcnxPrefixHash
+ >,
+ // sequenced to implement MRU
+ boost::multi_index::sequenced<
+ boost::multi_index::tag<__ccnx_private::i_timestamp> >
+ >
+ > type;
+};
+
+// typedef std::map<int,int> PitCounter;
+// typedef std::map<int,int>::iterator PitCounterIterator;
+
+// typedef std::map<int,double> PitBucket;
+// typedef std::map<int,double>::iterator PitBucketIterator;
+
+
+////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////
+
+/**
+ * \ingroup ccnx
+ * \brief Class implementing Pending Interests Table
+ */
+class CcnxPit : public Object
+{
+public:
+ /**
+ * \brief Interface ID
+ *
+ * \return interface ID
+ */
+ static TypeId GetTypeId ();
+
+ /**
+ * \brief PIT constructor
+ */
+ CcnxPit ();
+
+ /**
+ * \brief Find corresponding PIT entry for the given content name
+ * \param prefix Prefix for which to lookup the entry
+ * \returns const reference to Pit entry. If record not found,
+ * CcnxPitEntryNotFound exception will be thrown
+ */
+ const CcnxPitEntry&
+ Lookup (const CcnxContentObjectHeader &header) const;
+
+ /**
+ * \brief Find corresponding PIT entry for the given content name
+ * \param prefix Prefix for which to lookup the entry
+ * \returns const reference to Pit entry. If record does not exist, it will be created
+ */
+ const CcnxPitEntry&
+ Lookup (const CcnxInterestHeader &header) const;
+
+ // remove a PIT entry
+ //void erase (const string &contentName);
+
+ // Reset pending state in outgoing interests
+ // void resetPendingState( PitEntry &pe );
+
+ // // Check if there are any interfaces that we haven't sent data to yet
+ // bool areFreeInterfaces( PitEntry &pe, int interface );
+
+ // // Periodically generate pre-calculated number of tokens (leak buckets)
+ // void LeakBuckets( );
+
+ // // Selectively leak a bucket
+ // void LeakBucket (Ptr<CcnxFace> face, int amount);
+
+ /**
+ * \brief Set cleanup timeout
+ *
+ * Side effect: current clean up even (if any) will be cancelled and a new event started
+ *
+ * \param timeout cleanup timeout
+ */
+ void SetCleanupTimeout (const Time &timeout);
+
+ /**
+ * \brief Get cleanup timeout
+ *
+ * \returns cleanup timeout
+ */
+ Time GetCleanupTimeout () const;
+
+public:
+ // PitBucket maxBucketsPerInterface; // maximum number of buckets. Automatically computed based on link capacity
+ // // averaging over 1 second (bandwidth * 1second)
+ // PitBucket leakSize; // size of a periodic bucket leak
+
+private:
+ /** \brief Remove expired records from PIT */
+ void CleanExpired ();
+
+ friend std::ostream& operator<< (std::ostream& os, const CcnxPit &fib);
+
+private:
+ CcnxPitEntryContainer::type m_pit; ///< \brief Container for PIT entries
+
+ Time m_cleanupTimeout; ///< \brief Configurable timeout of how often cleanup events are working
+ EventId m_cleanupEvent; ///< \brief Cleanup event
+
+ // PitBucket m_bucketsPerInterface; ///< \brief pending interface counter per interface
+};
+
+///////////////////////////////////////////////////////////////////////////////
+///////////////////////////////////////////////////////////////////////////////
+
+std::ostream& operator<< (std::ostream& os, const CcnxPit &fib);
+std::ostream& operator<< (std::ostream& os, const CcnxPitEntry &entry);
+// std::ostream& operator<< (std::ostream& os, const CcnxFibFaceMetric &metric);
+
+class CcnxPitEntryNotFound {};
+
+} // namespace ns3
+
+#endif /* CCNX_PIT_H */
diff --git a/model/ccnx-rit.h b/model/ccnx-rit.h
index 99b2fac..0c8922d 100644
--- a/model/ccnx-rit.h
+++ b/model/ccnx-rit.h
@@ -204,4 +204,3 @@
} // namespace ns3
#endif // _CCNX_RIT_H_
-