blob: 1cd1d1630b2245a3d9e57358a095a14f66931bf0 [file] [log] [blame]
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/**
* Copyright (c) 2014, Regents of the University of California,
* Arizona Board of Regents,
* Colorado State University,
* University Pierre & Marie Curie, Sorbonne University,
* Washington University in St. Louis,
* Beijing Institute of Technology,
* The University of Memphis
*
* This file is part of NFD (Named Data Networking Forwarding Daemon).
* See AUTHORS.md for complete list of NFD authors and contributors.
*
* NFD is free software: you can redistribute it and/or modify it under the terms
* of the GNU General Public License as published by the Free Software Foundation,
* either version 3 of the License, or (at your option) any later version.
*
* NFD 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
* NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
*/
#include "forwarder.hpp"
#include "core/logger.hpp"
#include "core/random.hpp"
#include "available-strategies.hpp"
#include <boost/random/uniform_int_distribution.hpp>
namespace nfd {
NFD_LOG_INIT("Forwarder");
using fw::Strategy;
const Name Forwarder::LOCALHOST_NAME("ndn:/localhost");
Forwarder::Forwarder()
: m_faceTable(*this)
, m_fib(m_nameTree)
, m_pit(m_nameTree)
, m_measurements(m_nameTree)
, m_strategyChoice(m_nameTree, fw::makeDefaultStrategy(*this))
{
fw::installStrategies(*this);
}
Forwarder::~Forwarder()
{
}
void
Forwarder::onIncomingInterest(Face& inFace, const Interest& interest)
{
// receive Interest
NFD_LOG_DEBUG("onIncomingInterest face=" << inFace.getId() <<
" interest=" << interest.getName());
const_cast<Interest&>(interest).setIncomingFaceId(inFace.getId());
++m_counters.getNInInterests();
// /localhost scope control
bool isViolatingLocalhost = !inFace.isLocal() &&
LOCALHOST_NAME.isPrefixOf(interest.getName());
if (isViolatingLocalhost) {
NFD_LOG_DEBUG("onIncomingInterest face=" << inFace.getId() <<
" interest=" << interest.getName() << " violates /localhost");
// (drop)
return;
}
// PIT insert
shared_ptr<pit::Entry> pitEntry = m_pit.insert(interest).first;
// detect duplicate Nonce
int dnw = pitEntry->findNonce(interest.getNonce(), inFace);
bool hasDuplicateNonce = (dnw != pit::DUPLICATE_NONCE_NONE) ||
m_deadNonceList.has(interest.getName(), interest.getNonce());
if (hasDuplicateNonce) {
// goto Interest loop pipeline
this->onInterestLoop(inFace, interest, pitEntry);
return;
}
// cancel unsatisfy & straggler timer
this->cancelUnsatisfyAndStragglerTimer(pitEntry);
// is pending?
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) {
const_cast<Data*>(csMatch)->setIncomingFaceId(FACEID_CONTENT_STORE);
// XXX should we lookup PIT for other Interests that also match csMatch?
// set PIT straggler timer
this->setStragglerTimer(pitEntry, true, csMatch->getFreshnessPeriod());
// goto outgoing Data pipeline
this->onOutgoingData(*csMatch, inFace);
return;
}
}
// insert InRecord
pitEntry->insertOrUpdateInRecord(inFace.shared_from_this(), interest);
// set PIT unsatisfy timer
this->setUnsatisfyTimer(pitEntry);
// FIB lookup
shared_ptr<fib::Entry> fibEntry = m_fib.findLongestPrefixMatch(*pitEntry);
// dispatch to strategy
this->dispatchToStrategy(pitEntry, bind(&Strategy::afterReceiveInterest, _1,
cref(inFace), cref(interest), fibEntry, pitEntry));
}
void
Forwarder::onInterestLoop(Face& inFace, const Interest& interest,
shared_ptr<pit::Entry> pitEntry)
{
NFD_LOG_DEBUG("onInterestLoop face=" << inFace.getId() <<
" interest=" << interest.getName());
// (drop)
}
/** \brief compare two InRecords for picking outgoing Interest
* \return true if b is preferred over a
*
* This function should be passed to std::max_element over InRecordCollection.
* The outgoing Interest picked is the last incoming Interest
* that does not come from outFace.
* If all InRecords come from outFace, it's fine to pick that. This happens when
* there's only one InRecord that comes from outFace. The legit use is for
* vehicular network; otherwise, strategy shouldn't send to the sole inFace.
*/
static inline bool
compare_pickInterest(const pit::InRecord& a, const pit::InRecord& b, const Face* outFace)
{
bool isOutFaceA = a.getFace().get() == outFace;
bool isOutFaceB = b.getFace().get() == outFace;
if (!isOutFaceA && isOutFaceB) {
return false;
}
if (isOutFaceA && !isOutFaceB) {
return true;
}
return a.getLastRenewed() > b.getLastRenewed();
}
void
Forwarder::onOutgoingInterest(shared_ptr<pit::Entry> pitEntry, Face& outFace,
bool wantNewNonce)
{
if (outFace.getId() == INVALID_FACEID) {
NFD_LOG_WARN("onOutgoingInterest face=invalid interest=" << pitEntry->getName());
return;
}
NFD_LOG_DEBUG("onOutgoingInterest face=" << outFace.getId() <<
" interest=" << pitEntry->getName());
// scope control
if (pitEntry->violatesScope(outFace)) {
NFD_LOG_DEBUG("onOutgoingInterest face=" << outFace.getId() <<
" interest=" << pitEntry->getName() << " violates scope");
return;
}
// pick Interest
const pit::InRecordCollection& inRecords = pitEntry->getInRecords();
pit::InRecordCollection::const_iterator pickedInRecord = std::max_element(
inRecords.begin(), inRecords.end(), bind(&compare_pickInterest, _1, _2, &outFace));
BOOST_ASSERT(pickedInRecord != inRecords.end());
shared_ptr<Interest> interest = const_pointer_cast<Interest>(
pickedInRecord->getInterest().shared_from_this());
if (wantNewNonce) {
interest = make_shared<Interest>(*interest);
static boost::random::uniform_int_distribution<uint32_t> dist;
interest->setNonce(dist(getGlobalRng()));
}
// insert OutRecord
pitEntry->insertOrUpdateOutRecord(outFace.shared_from_this(), *interest);
// send Interest
outFace.sendInterest(*interest);
++m_counters.getNOutInterests();
}
void
Forwarder::onInterestReject(shared_ptr<pit::Entry> pitEntry)
{
if (pitEntry->hasUnexpiredOutRecords()) {
NFD_LOG_ERROR("onInterestReject interest=" << pitEntry->getName() <<
" cannot reject forwarded Interest");
return;
}
NFD_LOG_DEBUG("onInterestReject interest=" << pitEntry->getName());
// cancel unsatisfy & straggler timer
this->cancelUnsatisfyAndStragglerTimer(pitEntry);
// set PIT straggler timer
this->setStragglerTimer(pitEntry, false);
}
void
Forwarder::onInterestUnsatisfied(shared_ptr<pit::Entry> pitEntry)
{
NFD_LOG_DEBUG("onInterestUnsatisfied interest=" << pitEntry->getName());
// invoke PIT unsatisfied callback
this->dispatchToStrategy(pitEntry, bind(&Strategy::beforeExpirePendingInterest, _1,
pitEntry));
// goto Interest Finalize pipeline
this->onInterestFinalize(pitEntry, false);
}
void
Forwarder::onInterestFinalize(shared_ptr<pit::Entry> pitEntry, bool isSatisfied,
const time::milliseconds& dataFreshnessPeriod)
{
NFD_LOG_DEBUG("onInterestFinalize interest=" << pitEntry->getName() <<
(isSatisfied ? " satisfied" : " unsatisfied"));
// Dead Nonce List insert if necessary
this->insertDeadNonceList(*pitEntry, isSatisfied, dataFreshnessPeriod, 0);
// PIT delete
this->cancelUnsatisfyAndStragglerTimer(pitEntry);
m_pit.erase(pitEntry);
}
void
Forwarder::onIncomingData(Face& inFace, const Data& data)
{
// receive Data
NFD_LOG_DEBUG("onIncomingData face=" << inFace.getId() << " data=" << data.getName());
const_cast<Data&>(data).setIncomingFaceId(inFace.getId());
++m_counters.getNInDatas();
// /localhost scope control
bool isViolatingLocalhost = !inFace.isLocal() &&
LOCALHOST_NAME.isPrefixOf(data.getName());
if (isViolatingLocalhost) {
NFD_LOG_DEBUG("onIncomingData face=" << inFace.getId() <<
" data=" << data.getName() << " violates /localhost");
// (drop)
return;
}
// PIT match
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 (const shared_ptr<pit::Entry>& pitEntry : pitMatches) {
NFD_LOG_DEBUG("onIncomingData matching=" << pitEntry->getName());
// 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::steady_clock::now()) {
pendingDownstreams.insert(it->getFace());
}
}
// invoke PIT satisfy callback
this->dispatchToStrategy(pitEntry, bind(&Strategy::beforeSatisfyInterest, _1,
pitEntry, cref(inFace), cref(data)));
// Dead Nonce List insert if necessary (for OutRecord of inFace)
this->insertDeadNonceList(*pitEntry, true, data.getFreshnessPeriod(), &inFace);
// mark PIT satisfied
pitEntry->deleteInRecords();
pitEntry->deleteOutRecord(inFace);
// set PIT straggler timer
this->setStragglerTimer(pitEntry, true, data.getFreshnessPeriod());
}
// foreach pending downstream
for (std::set<shared_ptr<Face> >::iterator it = pendingDownstreams.begin();
it != pendingDownstreams.end(); ++it) {
shared_ptr<Face> pendingDownstream = *it;
if (pendingDownstream.get() == &inFace) {
continue;
}
// goto outgoing Data pipeline
this->onOutgoingData(data, *pendingDownstream);
}
}
void
Forwarder::onDataUnsolicited(Face& inFace, const Data& data)
{
// accept to cache?
bool acceptToCache = inFace.isLocal();
if (acceptToCache) {
// CS insert
m_cs.insert(data, true);
}
NFD_LOG_DEBUG("onDataUnsolicited face=" << inFace.getId() <<
" data=" << data.getName() <<
(acceptToCache ? " cached" : " not cached"));
}
void
Forwarder::onOutgoingData(const Data& data, Face& outFace)
{
if (outFace.getId() == INVALID_FACEID) {
NFD_LOG_WARN("onOutgoingData face=invalid data=" << data.getName());
return;
}
NFD_LOG_DEBUG("onOutgoingData face=" << outFace.getId() << " data=" << data.getName());
// /localhost scope control
bool isViolatingLocalhost = !outFace.isLocal() &&
LOCALHOST_NAME.isPrefixOf(data.getName());
if (isViolatingLocalhost) {
NFD_LOG_DEBUG("onOutgoingData face=" << outFace.getId() <<
" data=" << data.getName() << " violates /localhost");
// (drop)
return;
}
// TODO traffic manager
// send Data
outFace.sendData(data);
++m_counters.getNOutDatas();
}
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::steady_clock::TimePoint lastExpiry = lastExpiring->getExpiry();
time::nanoseconds lastExpiryFromNow = lastExpiry - time::steady_clock::now();
if (lastExpiryFromNow <= time::seconds(0)) {
// TODO all InRecords are already expired; will this happen?
}
scheduler::cancel(pitEntry->m_unsatisfyTimer);
pitEntry->m_unsatisfyTimer = scheduler::schedule(lastExpiryFromNow,
bind(&Forwarder::onInterestUnsatisfied, this, pitEntry));
}
void
Forwarder::setStragglerTimer(shared_ptr<pit::Entry> pitEntry, bool isSatisfied,
const time::milliseconds& dataFreshnessPeriod)
{
time::nanoseconds stragglerTime = time::milliseconds(100);
scheduler::cancel(pitEntry->m_stragglerTimer);
pitEntry->m_stragglerTimer = scheduler::schedule(stragglerTime,
bind(&Forwarder::onInterestFinalize, this, pitEntry, isSatisfied, dataFreshnessPeriod));
}
void
Forwarder::cancelUnsatisfyAndStragglerTimer(shared_ptr<pit::Entry> pitEntry)
{
scheduler::cancel(pitEntry->m_unsatisfyTimer);
scheduler::cancel(pitEntry->m_stragglerTimer);
}
static inline void
insertNonceToDnl(DeadNonceList& dnl, const pit::Entry& pitEntry,
const pit::OutRecord& outRecord)
{
dnl.add(pitEntry.getName(), outRecord.getLastNonce());
}
void
Forwarder::insertDeadNonceList(pit::Entry& pitEntry, bool isSatisfied,
const time::milliseconds& dataFreshnessPeriod,
Face* upstream)
{
// need Dead Nonce List insert?
bool needDnl = false;
if (isSatisfied) {
bool hasFreshnessPeriod = dataFreshnessPeriod >= time::milliseconds::zero();
// Data never becomes stale if it doesn't have FreshnessPeriod field
needDnl = static_cast<bool>(pitEntry.getInterest().getMustBeFresh()) &&
(hasFreshnessPeriod && dataFreshnessPeriod < m_deadNonceList.getLifetime());
}
else {
needDnl = true;
}
if (!needDnl) {
return;
}
// Dead Nonce List insert
if (upstream == 0) {
// insert all outgoing Nonces
const pit::OutRecordCollection& outRecords = pitEntry.getOutRecords();
std::for_each(outRecords.begin(), outRecords.end(),
bind(&insertNonceToDnl, ref(m_deadNonceList), cref(pitEntry), _1));
}
else {
// insert outgoing Nonce of a specific face
pit::OutRecordCollection::const_iterator outRecord = pitEntry.getOutRecord(*upstream);
if (outRecord != pitEntry.getOutRecords().end()) {
m_deadNonceList.add(pitEntry.getName(), outRecord->getLastNonce());
}
}
}
} // namespace nfd