fw: basic forwarding procedure & strategy skeleton

refs #1131 #1136

Change-Id: I3e97cb17bf85082b6499a310120409379f8eaa65
diff --git a/daemon/fw/best-route-strategy.cpp b/daemon/fw/best-route-strategy.cpp
new file mode 100644
index 0000000..12db744
--- /dev/null
+++ b/daemon/fw/best-route-strategy.cpp
@@ -0,0 +1,37 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (C) 2014 Named Data Networking Project
+ * See COPYING for copyright and distribution information.
+ */
+
+#include "best-route-strategy.hpp"
+
+namespace nfd {
+
+BestRouteStrategy::BestRouteStrategy(Forwarder& fw)
+  : Strategy(fw)
+{
+}
+
+BestRouteStrategy::~BestRouteStrategy()
+{
+}
+
+void
+BestRouteStrategy::afterReceiveInterest(const Face& inFace,
+                   const Interest& interest,
+                   shared_ptr<fib::Entry> fibEntry,
+                   shared_ptr<pit::Entry> pitEntry,
+                   pit::InRecordCollection::iterator pitInRecord)
+{
+  const fib::NextHopList& nexthops = fibEntry->getNextHops();
+  if (nexthops.size() == 0) {
+    this->rebuffPendingInterest(pitEntry);
+    return;
+  }
+  
+  shared_ptr<Face> outFace = nexthops.begin()->getFace();
+  this->sendInterest(pitEntry, outFace);
+}
+
+} // namespace nfd
diff --git a/daemon/fw/best-route-strategy.hpp b/daemon/fw/best-route-strategy.hpp
new file mode 100644
index 0000000..8e9f127
--- /dev/null
+++ b/daemon/fw/best-route-strategy.hpp
@@ -0,0 +1,38 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (C) 2014 Named Data Networking Project
+ * See COPYING for copyright and distribution information.
+ */
+
+#ifndef NFD_FW_BEST_ROUTE_STRATEGY_HPP
+#define NFD_FW_BEST_ROUTE_STRATEGY_HPP
+
+#include "strategy.hpp"
+
+namespace nfd {
+
+/** \class BestRouteStrategy
+ *  \brief a forwarding strategy that forwards Interest
+ *         to the first nexthop
+ */
+class BestRouteStrategy : public Strategy
+{
+public:
+  explicit
+  BestRouteStrategy(Forwarder& fw);
+  
+  virtual
+  ~BestRouteStrategy();
+  
+  virtual void
+  afterReceiveInterest(const Face& inFace,
+                       const Interest& interest,
+                       shared_ptr<fib::Entry> fibEntry,
+                       shared_ptr<pit::Entry> pitEntry,
+                       pit::InRecordCollection::iterator pitInRecord
+                       );
+};
+
+} // namespace nfd
+
+#endif // NFD_FW_BEST_ROUTE_STRATEGY_HPP
diff --git a/daemon/fw/forwarder.cpp b/daemon/fw/forwarder.cpp
index 15881e3..1ba6808 100644
--- a/daemon/fw/forwarder.cpp
+++ b/daemon/fw/forwarder.cpp
@@ -9,6 +9,7 @@
 namespace nfd {
 
 Forwarder::Forwarder(boost::asio::io_service& ioService)
+  : m_scheduler(ioService)
 {
 }
 
@@ -26,11 +27,227 @@
 void
 Forwarder::onInterest(const Face& face, const Interest& interest)
 {
+  this->onIncomingInterest(const_cast<Face&>(face), interest);
 }
 
 void
 Forwarder::onData(const Face& face, const Data& data)
 {
+  this->onIncomingData(const_cast<Face&>(face), data);
 }
 
+void
+Forwarder::onIncomingInterest(Face& inFace, const Interest& interest)
+{
+  // receive Interest
+  
+  // PIT insert
+  std::pair<shared_ptr<pit::Entry>, bool>
+    pitInsertResult = m_pit.insert(interest);
+  shared_ptr<pit::Entry> pitEntry = pitInsertResult.first;
+  
+  // detect loop and record Nonce
+  bool isLoop = ! pitEntry->addNonce(interest.getNonce());
+  if (isLoop) {
+    // goto Interest loop pipeline
+    this->onInterestLoop(inFace, interest, pitEntry);
+    return;
+  }
+  
+  // cancel unsatisfy & straggler timer
+  this->cancelUnsatisfyAndStragglerTimer(pitEntry);
+  
+  const pit::InRecordCollection& inRecords = pitEntry->getInRecords();
+  bool isPending = inRecords.begin() == inRecords.end();
+  
+  if (!isPending) {
+    // CS lookup
+    const Data* csMatch = m_cs.find(interest);
+    if (csMatch != 0) {
+      // XXX should we lookup PIT for other Interests that also match csMatch?
+
+      // goto outgoing Data pipeline
+      this->onOutgoingData(*csMatch, inFace);
+      return;
+    }
+  }
+  
+  // insert InRecord
+  pit::InRecordCollection::iterator inRecordIt =
+    pitEntry->insertOrUpdateInRecord(inFace.shared_from_this(), interest);
+  
+  // app chosen nexthops
+  bool isAppChosenNexthops = false; // TODO get from local control header
+  if (isAppChosenNexthops) {
+    // TODO foreach chosen nexthop: goto outgoing Interest pipeline
+    return;
+  }
+  
+  // FIB lookup
+  shared_ptr<fib::Entry> fibEntry
+    = m_fib.findLongestPrefixMatch(interest.getName());
+  // TODO use Fib::findParent(pitEntry)
+  
+  // dispatch to strategy
+  // TODO
+}
+
+void
+Forwarder::onInterestLoop(Face& inFace, const Interest& interest,
+                          shared_ptr<pit::Entry> pitEntry)
+{
+  // do nothing, which means Interest is dropped
+}
+
+void
+Forwarder::onOutgoingInterest(shared_ptr<pit::Entry> pitEntry, Face& outFace)
+{
+  // pick Interest
+  const Interest& interest = pitEntry->getInterest();
+  // TODO pick the last incoming Interest
+  
+  // insert OutRecord
+  pit::OutRecordCollection::iterator outRecordIt =
+    pitEntry->insertOrUpdateOutRecord(outFace.shared_from_this(), interest);
+  
+  // set PIT unsatisfy timer
+  this->setUnsatisfyTimer(pitEntry);
+  
+  // send Interest
+  outFace.sendInterest(interest);
+}
+
+void
+Forwarder::onInterestRebuff(shared_ptr<pit::Entry> pitEntry)
+{
+  // set PIT straggler timer
+  this->setStragglerTimer(pitEntry);
+}
+
+void
+Forwarder::onInterestUnsatisfied(shared_ptr<pit::Entry> pitEntry)
+{
+  // invoke PIT unsatisfied callback
+  // TODO
+  
+  // PIT delete
+  m_pit.remove(pitEntry);
+}
+
+void
+Forwarder::onIncomingData(Face& inFace, const Data& data)
+{
+  // receive Data
+  
+  // PIT match
+  shared_ptr<pit::DataMatchResult> pitMatches = m_pit.findAllDataMatches(data);
+  if (pitMatches->begin() == pitMatches->end()) {
+    // goto Data unsolicited pipeline
+    this->onDataUnsolicited(inFace, data);
+    return;
+  }
+  
+  // CS insert
+  m_cs.insert(data);
+  
+  std::set<shared_ptr<Face> > pendingDownstreams;
+  // foreach PitEntry
+  for (pit::DataMatchResult::iterator it = pitMatches->begin();
+       it != pitMatches->end(); ++it) {
+    shared_ptr<pit::Entry> pitEntry = *it;
+    
+    // cancel unsatisfy & straggler timer
+    this->cancelUnsatisfyAndStragglerTimer(pitEntry);
+    
+    // remember pending downstreams
+    const pit::InRecordCollection& inRecords = pitEntry->getInRecords();
+    for (pit::InRecordCollection::const_iterator it = inRecords.begin();
+                                                 it != inRecords.end(); ++it) {
+      if (it->getExpiry() > time::now()) {
+        pendingDownstreams.insert(it->getFace());
+      }
+    }
+    
+    // mark PIT satisfied
+    pitEntry->deleteInRecords();
+    pitEntry->deleteOutRecord(inFace.shared_from_this());
+    
+    // set PIT straggler timer
+    this->setStragglerTimer(pitEntry);
+    
+    // invoke PIT satisfy callback
+    // TODO
+  }
+  
+  // foreach pending downstream
+  for (std::set<shared_ptr<Face> >::iterator it = pendingDownstreams.begin();
+      it != pendingDownstreams.end(); ++it) {
+    // goto outgoing Data pipeline
+    this->onOutgoingData(data, **it);
+  }
+}
+
+void
+Forwarder::onDataUnsolicited(Face& inFace, const Data& data)
+{
+  // accept to cache?
+  bool acceptToCache = false;// TODO decision
+  if (acceptToCache) {
+    // CS insert
+    m_cs.insert(data);
+  }
+}
+
+void
+Forwarder::onOutgoingData(const Data& data, Face& outFace)
+{
+  // traffic manager
+  // pass through
+  
+  // send Data
+  outFace.sendData(data);
+}
+
+static inline bool
+compare_InRecord_expiry(const pit::InRecord& a, const pit::InRecord& b)
+{
+  return a.getExpiry() < b.getExpiry();
+}
+
+void
+Forwarder::setUnsatisfyTimer(shared_ptr<pit::Entry> pitEntry)
+{
+  const pit::InRecordCollection& inRecords = pitEntry->getInRecords();
+  pit::InRecordCollection::const_iterator lastExpiring =
+    std::max_element(inRecords.begin(), inRecords.end(),
+    &compare_InRecord_expiry);
+
+  time::Point lastExpiry = lastExpiring->getExpiry();
+  time::Duration lastExpiryFromNow = lastExpiry  - time::now();
+  if (lastExpiryFromNow <= time::seconds(0)) {
+    // TODO all InRecords are already expired; will this happen?
+  }
+  
+  pitEntry->m_unsatisfyTimer = m_scheduler.scheduleEvent(lastExpiryFromNow,
+    bind(&Forwarder::onInterestUnsatisfied, this, pitEntry));
+}
+
+void
+Forwarder::setStragglerTimer(shared_ptr<pit::Entry> pitEntry)
+{
+  time::Duration stragglerTime = time::milliseconds(100);
+  
+  pitEntry->m_stragglerTimer = m_scheduler.scheduleEvent(stragglerTime,
+    bind(&Pit::remove, &m_pit, pitEntry));
+}
+
+void
+Forwarder::cancelUnsatisfyAndStragglerTimer(shared_ptr<pit::Entry> pitEntry)
+{
+  m_scheduler.cancelEvent(pitEntry->m_unsatisfyTimer);
+  m_scheduler.cancelEvent(pitEntry->m_stragglerTimer);
+}
+
+
+
 } // namespace nfd
diff --git a/daemon/fw/forwarder.hpp b/daemon/fw/forwarder.hpp
index 6395f29..591254e 100644
--- a/daemon/fw/forwarder.hpp
+++ b/daemon/fw/forwarder.hpp
@@ -8,7 +8,11 @@
 #define NFD_FW_FORWARDER_HPP
 
 #include "common.hpp"
+#include "core/scheduler.hpp"
 #include "face/face.hpp"
+#include "table/fib.hpp"
+#include "table/pit.hpp"
+#include "table/cs.hpp"
 
 namespace nfd {
 
@@ -34,10 +38,69 @@
   void
   onData(const Face& face, const Data& data);
   
+private: // pipelines
+  /** \brief incoming Interest pipeline
+   */
+  void
+  onIncomingInterest(Face& inFace, const Interest& interest);
+
+  /** \brief Interest loop pipeline
+   */
+  void
+  onInterestLoop(Face& inFace, const Interest& interest,
+                 shared_ptr<pit::Entry> pitEntry);
+  
+  /** \brief outgoing Interest pipeline
+   */
+  void
+  onOutgoingInterest(shared_ptr<pit::Entry> pitEntry, Face& outFace);
+  
+  /** \brief Interest rebuff pipeline
+   */
+  void
+  onInterestRebuff(shared_ptr<pit::Entry> pitEntry);
+  
+  /** \brief Interest unsatisfied pipeline
+   */
+  void
+  onInterestUnsatisfied(shared_ptr<pit::Entry> pitEntry);
+  
+  /** \brief incoming Data pipeline
+   */
+  void
+  onIncomingData(Face& inFace, const Data& data);
+  
+  /** \brief Data unsolicited pipeline
+   */
+  void
+  onDataUnsolicited(Face& inFace, const Data& data);
+  
+  /** \brief outgoing Data pipeline
+   */
+  void
+  onOutgoingData(const Data& data, Face& outFace);
+
 private:
+  void
+  setUnsatisfyTimer(shared_ptr<pit::Entry> pitEntry);
+  
+  void
+  setStragglerTimer(shared_ptr<pit::Entry> pitEntry);
+  
+  void
+  cancelUnsatisfyAndStragglerTimer(shared_ptr<pit::Entry> pitEntry);
+
+private:
+  Scheduler m_scheduler;
+  Fib m_fib;
+  Pit m_pit;
+  Cs  m_cs;
   // container< shared_ptr<Face> > m_faces;
+  
+  // allow Strategy (base class) to enter pipelines
+  friend class Strategy;
 };
 
-}
+} // namespace nfd
 
 #endif // NFD_FW_FORWARDER_HPP
diff --git a/daemon/fw/strategy.cpp b/daemon/fw/strategy.cpp
new file mode 100644
index 0000000..ed1233f
--- /dev/null
+++ b/daemon/fw/strategy.cpp
@@ -0,0 +1,34 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (C) 2014 Named Data Networking Project
+ * See COPYING for copyright and distribution information.
+ */
+
+#include "strategy.hpp"
+
+namespace nfd {
+
+Strategy::Strategy(Forwarder& fw)
+  : m_fw(fw)
+{
+}
+
+Strategy::~Strategy()
+{
+}
+
+
+void
+Strategy::sendInterest(shared_ptr<pit::Entry> pitEntry,
+                       shared_ptr<Face> outFace)
+{
+  m_fw.onOutgoingInterest(pitEntry, *outFace);
+}
+
+void
+Strategy::rebuffPendingInterest(shared_ptr<pit::Entry> pitEntry)
+{
+  m_fw.onInterestRebuff(pitEntry);
+}
+
+} // namespace nfd
diff --git a/daemon/fw/strategy.hpp b/daemon/fw/strategy.hpp
new file mode 100644
index 0000000..1a6e47f
--- /dev/null
+++ b/daemon/fw/strategy.hpp
@@ -0,0 +1,65 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (C) 2014 Named Data Networking Project
+ * See COPYING for copyright and distribution information.
+ */
+
+#ifndef NFD_FW_STRATEGY_HPP
+#define NFD_FW_STRATEGY_HPP
+
+#include "forwarder.hpp"
+
+namespace nfd {
+
+/** \class Strategy
+ *  \brief represents a forwarding strategy
+ */
+class Strategy
+{
+public:
+  explicit
+  Strategy(Forwarder& fw);
+  
+  virtual
+  ~Strategy();
+  
+  virtual void
+  afterReceiveInterest(const Face& inFace,
+                       const Interest& interest,
+                       shared_ptr<fib::Entry> fibEntry,
+                       shared_ptr<pit::Entry> pitEntry,
+                       pit::InRecordCollection::iterator pitInRecord
+                       ) =0;
+  
+  //virtual void
+  //beforeExpirePendingInterest() =0;
+  
+  //virtual void
+  //afterAddFibEntry() =0;
+  
+  //virtual void
+  //afterUpdateFibEntry() =0;
+  
+  //virtual void
+  //beforeRemoveFibEntry() =0;
+  
+protected: // actions
+  /// send Interest to outFace
+  void
+  sendInterest(shared_ptr<pit::Entry> pitEntry,
+                    shared_ptr<Face> outFace);
+  
+  /** \brief decide that a pending Interest cannot be forwarded
+   *  This shall not be called if the pending Interest has been
+   *  forwarded earlier, and does not need to be resent now.
+   */
+  void
+  rebuffPendingInterest(shared_ptr<pit::Entry> pitEntry);
+  
+private:
+  Forwarder& m_fw;
+};
+
+} // namespace nfd
+
+#endif // NFD_FW_STRATEGY_HPP