blob: 6c4163f803bd4d04fbab0ef3069518c22f7e7121 [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 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);
// 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) {
// XXX should we lookup PIT for other Interests that also match csMatch?
// goto outgoing Data pipeline
this->onOutgoingData(*csMatch, inFace);
return;
}
}
// insert InRecord
pitEntry->insertOrUpdateInRecord(inFace.shared_from_this(), interest);
// 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);
// set PIT unsatisfy timer
this->setUnsatisfyTimer(pitEntry);
// 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());
// set PIT straggler timer
this->setStragglerTimer(pitEntry);
}
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));
// 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
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;
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::beforeSatisfyPendingInterest, _1,
pitEntry, cref(inFace), cref(data)));
// mark PIT satisfied
pitEntry->deleteInRecords();
pitEntry->deleteOutRecord(inFace.shared_from_this());
// set PIT straggler timer
this->setStragglerTimer(pitEntry);
}
// 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)
{
time::nanoseconds stragglerTime = time::milliseconds(100);
scheduler::cancel(pitEntry->m_stragglerTimer);
pitEntry->m_stragglerTimer = scheduler::schedule(stragglerTime,
bind(&Pit::erase, &m_pit, pitEntry));
}
void
Forwarder::cancelUnsatisfyAndStragglerTimer(shared_ptr<pit::Entry> pitEntry)
{
scheduler::cancel(pitEntry->m_unsatisfyTimer);
scheduler::cancel(pitEntry->m_stragglerTimer);
}
} // namespace nfd