blob: a05080fe8d371bcec0bab0eb953ea7ea1673a3db [file] [log] [blame]
Junxiao Shid3c792f2014-01-30 00:46:13 -07001/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
Junxiao Shifc2e13d2017-07-25 02:08:48 +00002/*
Teng Liang63086442018-02-25 20:39:42 -07003 * Copyright (c) 2014-2018, Regents of the University of California,
Junxiao Shi35353962015-01-08 09:13:47 -07004 * Arizona Board of Regents,
5 * Colorado State University,
6 * University Pierre & Marie Curie, Sorbonne University,
7 * Washington University in St. Louis,
8 * Beijing Institute of Technology,
9 * The University of Memphis.
Alexander Afanasyev9bcbc7c2014-04-06 19:37:37 -070010 *
11 * This file is part of NFD (Named Data Networking Forwarding Daemon).
12 * See AUTHORS.md for complete list of NFD authors and contributors.
13 *
14 * NFD is free software: you can redistribute it and/or modify it under the terms
15 * of the GNU General Public License as published by the Free Software Foundation,
16 * either version 3 of the License, or (at your option) any later version.
17 *
18 * NFD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
19 * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
20 * PURPOSE. See the GNU General Public License for more details.
21 *
22 * You should have received a copy of the GNU General Public License along with
23 * NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
Junxiao Shi82e7f582014-09-07 15:15:40 -070024 */
Junxiao Shid3c792f2014-01-30 00:46:13 -070025
26#include "strategy.hpp"
Junxiao Shi8c8d2182014-01-30 22:33:00 -070027#include "forwarder.hpp"
Steve DiBenedettobf6a93d2014-03-21 14:03:02 -060028#include "core/logger.hpp"
Junxiao Shic5f651f2016-11-17 22:58:12 +000029#include "core/random.hpp"
Junxiao Shic34d1672016-12-09 15:57:59 +000030#include <boost/range/adaptor/map.hpp>
31#include <boost/range/algorithm/copy.hpp>
Junxiao Shid3c792f2014-01-30 00:46:13 -070032
33namespace nfd {
Junxiao Shi8c8d2182014-01-30 22:33:00 -070034namespace fw {
Junxiao Shid3c792f2014-01-30 00:46:13 -070035
Junxiao Shi679e9272014-02-15 20:10:21 -070036NFD_LOG_INIT("Strategy");
37
Junxiao Shic34d1672016-12-09 15:57:59 +000038Strategy::Registry&
39Strategy::getRegistry()
40{
41 static Registry registry;
42 return registry;
43}
44
45Strategy::Registry::const_iterator
Junxiao Shi18739c42016-12-22 08:03:00 +000046Strategy::find(const Name& instanceName)
Junxiao Shic34d1672016-12-09 15:57:59 +000047{
48 const Registry& registry = getRegistry();
Junxiao Shi18739c42016-12-22 08:03:00 +000049 ParsedInstanceName parsed = parseInstanceName(instanceName);
50
Junxiao Shi18739c42016-12-22 08:03:00 +000051 if (parsed.version) {
Junxiao Shi91f6ee02016-12-29 21:44:44 +000052 // specified version: find exact or next higher version
53
54 auto found = registry.lower_bound(parsed.strategyName);
55 if (found != registry.end()) {
56 if (parsed.strategyName.getPrefix(-1).isPrefixOf(found->first)) {
57 NFD_LOG_TRACE("find " << instanceName << " versioned found=" << found->first);
58 return found;
59 }
60 }
61
62 NFD_LOG_TRACE("find " << instanceName << " versioned not-found");
63 return registry.end();
Junxiao Shi18739c42016-12-22 08:03:00 +000064 }
65
Junxiao Shi91f6ee02016-12-29 21:44:44 +000066 // no version specified: find highest version
67
68 if (!parsed.strategyName.empty()) { // Name().getSuccessor() would be invalid
69 auto found = registry.lower_bound(parsed.strategyName.getSuccessor());
70 if (found != registry.begin()) {
71 --found;
72 if (parsed.strategyName.isPrefixOf(found->first)) {
73 NFD_LOG_TRACE("find " << instanceName << " unversioned found=" << found->first);
74 return found;
75 }
Junxiao Shic34d1672016-12-09 15:57:59 +000076 }
77 }
Junxiao Shi91f6ee02016-12-29 21:44:44 +000078
79 NFD_LOG_TRACE("find " << instanceName << " unversioned not-found");
80 return registry.end();
Junxiao Shic34d1672016-12-09 15:57:59 +000081}
82
83bool
Junxiao Shi18739c42016-12-22 08:03:00 +000084Strategy::canCreate(const Name& instanceName)
Junxiao Shic34d1672016-12-09 15:57:59 +000085{
Junxiao Shi18739c42016-12-22 08:03:00 +000086 return Strategy::find(instanceName) != getRegistry().end();
Junxiao Shic34d1672016-12-09 15:57:59 +000087}
88
89unique_ptr<Strategy>
Junxiao Shi18739c42016-12-22 08:03:00 +000090Strategy::create(const Name& instanceName, Forwarder& forwarder)
Junxiao Shic34d1672016-12-09 15:57:59 +000091{
Junxiao Shi18739c42016-12-22 08:03:00 +000092 auto found = Strategy::find(instanceName);
Junxiao Shic34d1672016-12-09 15:57:59 +000093 if (found == getRegistry().end()) {
Junxiao Shi18739c42016-12-22 08:03:00 +000094 NFD_LOG_DEBUG("create " << instanceName << " not-found");
Junxiao Shic34d1672016-12-09 15:57:59 +000095 return nullptr;
96 }
97
Junxiao Shi18739c42016-12-22 08:03:00 +000098 unique_ptr<Strategy> instance = found->second(forwarder, instanceName);
99 NFD_LOG_DEBUG("create " << instanceName << " found=" << found->first <<
100 " created=" << instance->getInstanceName());
101 BOOST_ASSERT(!instance->getInstanceName().empty());
102 return instance;
Junxiao Shic34d1672016-12-09 15:57:59 +0000103}
104
Junxiao Shi55e21b92017-01-23 03:27:47 +0000105bool
106Strategy::areSameType(const Name& instanceNameA, const Name& instanceNameB)
107{
108 return Strategy::find(instanceNameA) == Strategy::find(instanceNameB);
109}
110
Junxiao Shic34d1672016-12-09 15:57:59 +0000111std::set<Name>
112Strategy::listRegistered()
113{
114 std::set<Name> strategyNames;
115 boost::copy(getRegistry() | boost::adaptors::map_keys,
116 std::inserter(strategyNames, strategyNames.end()));
117 return strategyNames;
118}
119
Junxiao Shi18739c42016-12-22 08:03:00 +0000120Strategy::ParsedInstanceName
121Strategy::parseInstanceName(const Name& input)
122{
123 for (ssize_t i = input.size() - 1; i > 0; --i) {
124 if (input[i].isVersion()) {
125 return {input.getPrefix(i + 1), input[i].toVersion(), input.getSubName(i + 1)};
126 }
127 }
128 return {input, ndn::nullopt, PartialName()};
129}
130
131Name
132Strategy::makeInstanceName(const Name& input, const Name& strategyName)
133{
134 BOOST_ASSERT(strategyName.at(-1).isVersion());
135
136 bool hasVersion = std::any_of(input.rbegin(), input.rend(),
137 [] (const name::Component& comp) { return comp.isVersion(); });
138 return hasVersion ? input : Name(input).append(strategyName.at(-1));
139}
140
141Strategy::Strategy(Forwarder& forwarder)
Junxiao Shicde37ad2015-12-24 01:02:05 -0700142 : afterAddFace(forwarder.getFaceTable().afterAdd)
143 , beforeRemoveFace(forwarder.getFaceTable().beforeRemove)
Junxiao Shibb5105f2014-03-03 12:06:45 -0700144 , m_forwarder(forwarder)
Junxiao Shi15e98b02016-08-12 11:21:44 +0000145 , m_measurements(m_forwarder.getMeasurements(), m_forwarder.getStrategyChoice(), *this)
Junxiao Shid3c792f2014-01-30 00:46:13 -0700146{
147}
148
Junxiao Shi15e98b02016-08-12 11:21:44 +0000149Strategy::~Strategy() = default;
Junxiao Shid3c792f2014-01-30 00:46:13 -0700150
Junxiao Shi679e9272014-02-15 20:10:21 -0700151void
Junxiao Shi15e98b02016-08-12 11:21:44 +0000152Strategy::beforeSatisfyInterest(const shared_ptr<pit::Entry>& pitEntry,
Junxiao Shi82e7f582014-09-07 15:15:40 -0700153 const Face& inFace, const Data& data)
Junxiao Shi22be22c2014-02-16 22:53:48 -0700154{
Junxiao Shi82e7f582014-09-07 15:15:40 -0700155 NFD_LOG_DEBUG("beforeSatisfyInterest pitEntry=" << pitEntry->getName() <<
Junxiao Shi15e98b02016-08-12 11:21:44 +0000156 " inFace=" << inFace.getId() << " data=" << data.getName());
Junxiao Shi22be22c2014-02-16 22:53:48 -0700157}
158
159void
Teng Liang85a36632018-03-21 05:59:34 -0700160Strategy::afterContentStoreHit(const shared_ptr<pit::Entry>& pitEntry,
161 const Face& inFace, const Data& data)
162{
163 NFD_LOG_DEBUG("afterContentStoreHit pitEntry=" << pitEntry->getName() <<
164 " inFace=" << inFace.getId() << " data=" << data.getName());
165
166 this->sendData(pitEntry, data, inFace);
167}
168
169void
Junxiao Shi5e5e4452015-09-24 16:56:52 -0700170Strategy::afterReceiveNack(const Face& inFace, const lp::Nack& nack,
Junxiao Shi15e98b02016-08-12 11:21:44 +0000171 const shared_ptr<pit::Entry>& pitEntry)
Junxiao Shi5e5e4452015-09-24 16:56:52 -0700172{
173 NFD_LOG_DEBUG("afterReceiveNack inFace=" << inFace.getId() <<
174 " pitEntry=" << pitEntry->getName());
175}
176
177void
Eric Newberry41aba102017-11-01 16:42:13 -0700178Strategy::onDroppedInterest(const Face& outFace, const Interest& interest)
179{
180 NFD_LOG_DEBUG("onDroppedInterest outFace=" << outFace.getId() << " name=" << interest.getName());
181}
182
183void
Junxiao Shib9420cf2016-08-13 04:38:52 +0000184Strategy::sendNacks(const shared_ptr<pit::Entry>& pitEntry, const lp::NackHeader& header,
Junxiao Shi5e5e4452015-09-24 16:56:52 -0700185 std::initializer_list<const Face*> exceptFaces)
186{
187 // populate downstreams with all downstreams faces
188 std::unordered_set<const Face*> downstreams;
Junxiao Shi4846f372016-04-05 13:39:30 -0700189 std::transform(pitEntry->in_begin(), pitEntry->in_end(), std::inserter(downstreams, downstreams.end()),
Junxiao Shi9cff7792016-08-01 21:45:11 +0000190 [] (const pit::InRecord& inR) { return &inR.getFace(); });
Junxiao Shi5e5e4452015-09-24 16:56:52 -0700191
192 // delete excluded faces
Junxiao Shi9cff7792016-08-01 21:45:11 +0000193 // .erase in a loop is more efficient than std::set_difference because that requires sorted range
Junxiao Shi5e5e4452015-09-24 16:56:52 -0700194 for (const Face* exceptFace : exceptFaces) {
195 downstreams.erase(exceptFace);
196 }
197
198 // send Nacks
199 for (const Face* downstream : downstreams) {
200 this->sendNack(pitEntry, *downstream, header);
201 }
Junxiao Shi4846f372016-04-05 13:39:30 -0700202 // warning: don't loop on pitEntry->getInRecords(), because in-record is deleted when sending Nack
Junxiao Shi5e5e4452015-09-24 16:56:52 -0700203}
Junxiao Shid3c792f2014-01-30 00:46:13 -0700204
Junxiao Shicf0f3ce2016-09-02 13:01:59 +0000205const fib::Entry&
206Strategy::lookupFib(const pit::Entry& pitEntry) const
207{
208 const Fib& fib = m_forwarder.getFib();
Junxiao Shicf0f3ce2016-09-02 13:01:59 +0000209
210 const Interest& interest = pitEntry.getInterest();
Junxiao Shifc2e13d2017-07-25 02:08:48 +0000211 // has forwarding hint?
212 if (interest.getForwardingHint().empty()) {
Junxiao Shicf0f3ce2016-09-02 13:01:59 +0000213 // FIB lookup with Interest name
214 const fib::Entry& fibEntry = fib.findLongestPrefixMatch(pitEntry);
Junxiao Shifc2e13d2017-07-25 02:08:48 +0000215 NFD_LOG_TRACE("lookupFib noForwardingHint found=" << fibEntry.getPrefix());
Junxiao Shicf0f3ce2016-09-02 13:01:59 +0000216 return fibEntry;
217 }
218
Junxiao Shifc2e13d2017-07-25 02:08:48 +0000219 const DelegationList& fh = interest.getForwardingHint();
220 // Forwarding hint should have been stripped by incoming Interest pipeline when reaching producer region
221 BOOST_ASSERT(!m_forwarder.getNetworkRegionTable().isInProducerRegion(fh));
Junxiao Shicf0f3ce2016-09-02 13:01:59 +0000222
Junxiao Shifc2e13d2017-07-25 02:08:48 +0000223 const fib::Entry* fibEntry = nullptr;
224 for (const Delegation& del : fh) {
225 fibEntry = &fib.findLongestPrefixMatch(del.name);
226 if (fibEntry->hasNextHops()) {
227 if (fibEntry->getPrefix().size() == 0) {
228 // in consumer region, return the default route
229 NFD_LOG_TRACE("lookupFib inConsumerRegion found=" << fibEntry->getPrefix());
230 }
231 else {
232 // in default-free zone, use the first delegation that finds a FIB entry
233 NFD_LOG_TRACE("lookupFib delegation=" << del.name << " found=" << fibEntry->getPrefix());
234 }
235 return *fibEntry;
Junxiao Shicf0f3ce2016-09-02 13:01:59 +0000236 }
Junxiao Shifc2e13d2017-07-25 02:08:48 +0000237 BOOST_ASSERT(fibEntry->getPrefix().size() == 0); // only ndn:/ FIB entry can have zero nexthop
Junxiao Shicf0f3ce2016-09-02 13:01:59 +0000238 }
Junxiao Shifc2e13d2017-07-25 02:08:48 +0000239 BOOST_ASSERT(fibEntry != nullptr && fibEntry->getPrefix().size() == 0);
240 return *fibEntry; // only occurs if no delegation finds a FIB nexthop
Junxiao Shicf0f3ce2016-09-02 13:01:59 +0000241}
242
Junxiao Shi8c8d2182014-01-30 22:33:00 -0700243} // namespace fw
Junxiao Shid3c792f2014-01-30 00:46:13 -0700244} // namespace nfd