Klaus Schneider | 3878430 | 2019-08-31 18:26:36 -0700 | [diff] [blame^] | 1 | /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */ |
| 2 | /** |
| 3 | * Copyright (c) 2019 Klaus Schneider, The University of Arizona |
| 4 | * |
| 5 | * This program is free software; you can redistribute it and/or modify |
| 6 | * it under the terms of the GNU General Public License version 2 as |
| 7 | * published by the Free Software Foundation; |
| 8 | * |
| 9 | * This program is distributed in the hope that it will be useful, |
| 10 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
| 11 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| 12 | * GNU General Public License for more details. |
| 13 | * |
| 14 | * You should have received a copy of the GNU General Public License |
| 15 | * along with this program; if not, write to the Free Software |
| 16 | * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA |
| 17 | * |
| 18 | * Author: Klaus Schneider <klaus@cs.arizona.edu> |
| 19 | */ |
| 20 | |
| 21 | #include "abstract-fib.hpp" |
| 22 | |
| 23 | #include <algorithm> |
| 24 | |
| 25 | #include "ns3/names.h" |
| 26 | #include "ns3/ndnSIM/NFD/daemon/fw/forwarder.hpp" |
| 27 | #include "ns3/ndnSIM/model/ndn-global-router.hpp" |
| 28 | #include "ns3/ndnSIM/model/ndn-l3-protocol.hpp" |
| 29 | #include "ns3/node.h" |
| 30 | |
| 31 | namespace ns3 { |
| 32 | namespace ndn { |
| 33 | |
| 34 | using std::set; |
| 35 | |
| 36 | AbstractFib::AbstractFib(const Ptr<GlobalRouter> own, int numNodes) |
| 37 | : nodeId{static_cast<int>(own->GetObject<ns3::Node>()->GetId())} |
| 38 | , nodeName{ns3::Names::FindName(own->GetObject<ns3::Node>())} |
| 39 | , numberOfNodes{numNodes} |
| 40 | , nodeDegree{static_cast<int>(own->GetIncidencies().size())} |
| 41 | , ownRouter{own} |
| 42 | , upwardCounter{0} |
| 43 | , totalNhCounter{0} |
| 44 | { |
| 45 | checkInputs(); |
| 46 | |
| 47 | createEmptyFib(); |
| 48 | } |
| 49 | |
| 50 | void |
| 51 | AbstractFib::checkInputs() |
| 52 | { |
| 53 | if (nodeDegree <= 0) { |
| 54 | std::cerr << nodeName << " has a degree of " << nodeDegree << "!\n\n"; |
| 55 | } |
| 56 | |
| 57 | const auto MAX_SIZE{1e5}; |
| 58 | NS_ABORT_UNLESS(nodeId >= 0 && nodeId <= MAX_SIZE); |
| 59 | NS_ABORT_UNLESS(nodeName.size() > 0 && nodeName.size() <= MAX_SIZE); |
| 60 | NS_ABORT_UNLESS(nodeDegree >= 0 && nodeDegree <= MAX_SIZE); |
| 61 | NS_ABORT_UNLESS(numberOfNodes > 1 && numberOfNodes <= MAX_SIZE); |
| 62 | } |
| 63 | |
| 64 | void |
| 65 | AbstractFib::createEmptyFib() |
| 66 | { |
| 67 | // Create empty FIB: |
| 68 | for (int dstId = 0; dstId < numberOfNodes; dstId++) { |
| 69 | if (dstId == nodeId) { |
| 70 | continue; |
| 71 | } |
| 72 | perDstFib.insert({dstId, {}}); |
| 73 | upwardPerDstFib.insert({dstId, {}}); |
| 74 | } |
| 75 | } |
| 76 | |
| 77 | Ptr<GlobalRouter> |
| 78 | AbstractFib::getGR() const |
| 79 | { |
| 80 | return ownRouter; |
| 81 | } |
| 82 | |
| 83 | // Setters: |
| 84 | void |
| 85 | AbstractFib::insert(int dstId, const FibNextHop& nh) |
| 86 | { |
| 87 | NS_ABORT_UNLESS(nh.getType() == NextHopType::DOWNWARD || nh.getType() == NextHopType::UPWARD); |
| 88 | NS_ABORT_UNLESS(nh.getNexthopId() != nodeId); |
| 89 | |
| 90 | bool inserted1 = perDstFib.at(dstId).insert(nh).second; |
| 91 | BOOST_VERIFY(inserted1); // Check if it didn't exist yet. |
| 92 | totalNhCounter++; |
| 93 | |
| 94 | if (nh.getType() == NextHopType::UPWARD) { |
| 95 | bool inserted2 = upwardPerDstFib.at(dstId).insert(nh).second; |
| 96 | BOOST_VERIFY(inserted2); |
| 97 | upwardCounter++; |
| 98 | } |
| 99 | } |
| 100 | |
| 101 | size_t |
| 102 | AbstractFib::erase(int dstId, int nhId) |
| 103 | { |
| 104 | auto& fib{perDstFib.at(dstId)}; |
| 105 | |
| 106 | auto fibNh = std::find_if(fib.begin(), fib.end(), |
| 107 | [&](const FibNextHop& item) { return item.getNexthopId() == nhId; }); |
| 108 | |
| 109 | // Element doesn't exist: |
| 110 | if (fibNh == fib.end()) { |
| 111 | |
| 112 | // TODO: Figure out why this happens. |
| 113 | return 0; |
| 114 | } |
| 115 | |
| 116 | NS_ABORT_UNLESS(fibNh != perDstFib.at(dstId).end()); |
| 117 | NS_ABORT_UNLESS(fibNh->getType() == NextHopType::UPWARD); |
| 118 | totalNhCounter--; |
| 119 | |
| 120 | fib.erase(fibNh); |
| 121 | auto numErased2 = upwardPerDstFib.at(dstId).erase(*fibNh); |
| 122 | NS_ABORT_UNLESS(numErased2 == 1); |
| 123 | upwardCounter--; |
| 124 | |
| 125 | return numErased2; |
| 126 | } |
| 127 | |
| 128 | // O(1) |
| 129 | const set<FibNextHop>& |
| 130 | AbstractFib::getNexthops(int dstId) const |
| 131 | { |
| 132 | NS_ABORT_MSG_IF(dstId == nodeId, "Requested destination id is the same as current nodeId!"); |
| 133 | NS_ABORT_MSG_IF(perDstFib.count(dstId) == 0, |
| 134 | "Node " << nodeId << " No nexthops for dst: " << dstId << "!"); |
| 135 | NS_ABORT_UNLESS(perDstFib.count(dstId) != 0); |
| 136 | return perDstFib.at(dstId); |
| 137 | } |
| 138 | |
| 139 | const set<FibNextHop>& |
| 140 | AbstractFib::getUpwardNexthops(int dstId) const |
| 141 | { |
| 142 | NS_ABORT_MSG_IF(dstId == nodeId, "Requested destination id is the same as current nodeId!"); |
| 143 | NS_ABORT_MSG_IF(perDstFib.count(dstId) == 0, |
| 144 | "Node " << nodeId << " No nexthops for dst: " << dstId << "!"); |
| 145 | return upwardPerDstFib.at(dstId); |
| 146 | } |
| 147 | |
| 148 | void |
| 149 | AbstractFib::checkFib() const |
| 150 | { |
| 151 | BOOST_VERIFY(perDstFib.size() > 0); |
| 152 | |
| 153 | for (const auto& fibSet : perDstFib) { |
| 154 | const size_t numNhs = fibSet.second.size(); |
| 155 | |
| 156 | bool hasDownward{false}; |
| 157 | std::unordered_set<int> nextHopSet{}; |
| 158 | |
| 159 | for (const FibNextHop& nextHop : fibSet.second) { |
| 160 | BOOST_VERIFY(nextHop.getCost() > 0 && nextHop.getCost() < FibNextHop::MAX_COST); |
| 161 | if (nextHop.getType() == NextHopType::DOWNWARD) { |
| 162 | hasDownward = true; |
| 163 | } |
| 164 | |
| 165 | // Only one FIB entry per nexthop allowed! |
| 166 | BOOST_VERIFY(nextHopSet.count(nextHop.getNexthopId()) == 0); |
| 167 | nextHopSet.emplace(nextHop.getNexthopId()); |
| 168 | } |
| 169 | BOOST_VERIFY(hasDownward || numNhs == 0); |
| 170 | BOOST_VERIFY(nextHopSet.size() == fibSet.second.size()); |
| 171 | } |
| 172 | } |
| 173 | |
| 174 | std::ostream& |
| 175 | operator<<(std::ostream& os, const AbstractFib& fib) |
| 176 | { |
| 177 | for (const auto& entry : fib.perDstFib) { |
| 178 | os << "\nFIB node: " << fib.nodeName << fib.nodeId << "\n"; |
| 179 | os << "Dst: " << entry.first << "\n"; |
| 180 | for (const auto& nh : entry.second) { |
| 181 | os << nh << "\n"; |
| 182 | } |
| 183 | } |
| 184 | return os; |
| 185 | } |
| 186 | |
| 187 | } // namespace ndn |
| 188 | } // namespace ns-3 |