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 "remove-loops.hpp" |
| 22 | |
| 23 | #include <boost/graph/adjacency_list.hpp> |
| 24 | #include <boost/graph/dijkstra_shortest_paths.hpp> |
| 25 | #include <boost/graph/properties.hpp> |
| 26 | #include <boost/property_map/property_map.hpp> |
| 27 | #include <queue> |
| 28 | |
| 29 | #include "ns3/abort.h" |
| 30 | #include "ns3/ndnSIM/helper/lfid/abstract-fib.hpp" |
| 31 | |
| 32 | namespace ns3 { |
| 33 | namespace ndn { |
| 34 | |
| 35 | using std::set; |
| 36 | using AllNodeFib = AbstractFib::AllNodeFib; |
| 37 | |
| 38 | /** |
| 39 | * Fill directed graph only with edges existing in the FIB. |
| 40 | */ |
| 41 | void |
| 42 | getDigraphFromFib(DiGraph& dg, const AllNodeFib& allNodeFIB, const int dstId) |
| 43 | { |
| 44 | |
| 45 | // 1. Erase All Arcs: |
| 46 | dg.clear(); |
| 47 | |
| 48 | // 2. Add Arcs from FIB |
| 49 | for (const auto& node : allNodeFIB) { |
| 50 | int nodeId = node.first; |
| 51 | if (dstId == nodeId) { |
| 52 | continue; |
| 53 | } |
| 54 | |
| 55 | for (const auto& fibNh : node.second.getNexthops(dstId)) { |
| 56 | NS_ABORT_UNLESS(fibNh.getType() <= NextHopType::UPWARD); |
| 57 | boost::add_edge(static_cast<uint64_t>(nodeId), static_cast<uint64_t>(fibNh.getNexthopId()), 1, dg); |
| 58 | } |
| 59 | } |
| 60 | } |
| 61 | |
| 62 | class NodePrio { |
| 63 | public: |
| 64 | NodePrio(int nodeId, int remainingNh, set<FibNextHop> nhSet) |
| 65 | : m_nodeId{nodeId} |
| 66 | , m_remainingNh{remainingNh} |
| 67 | , m_uwSet{nhSet} |
| 68 | { |
| 69 | NS_ABORT_UNLESS(remainingNh > 0 && m_uwSet.size() > 0); |
| 70 | NS_ABORT_UNLESS(static_cast<int>(m_uwSet.size()) < remainingNh); |
| 71 | } |
| 72 | |
| 73 | int |
| 74 | getId() const |
| 75 | { |
| 76 | return m_nodeId; |
| 77 | } |
| 78 | |
| 79 | int |
| 80 | getRemainingUw() const |
| 81 | { |
| 82 | return static_cast<int>(m_uwSet.size()); |
| 83 | } |
| 84 | |
| 85 | /** |
| 86 | * Order by Remamining UW NHs, Highest DeltaCost, and then id. |
| 87 | */ |
| 88 | bool |
| 89 | operator<(const NodePrio& other) const |
| 90 | { |
| 91 | return std::make_tuple(m_remainingNh, getHighestCostUw(), m_nodeId) |
| 92 | < std::make_tuple(other.m_remainingNh, other.getHighestCostUw(), other.m_nodeId); |
| 93 | } |
| 94 | |
| 95 | // Setters: |
| 96 | FibNextHop |
| 97 | popHighestCostUw() |
| 98 | { |
| 99 | const FibNextHop& tmp = getHighestCostUw(); |
| 100 | eraseUw(tmp); |
| 101 | return tmp; |
| 102 | } |
| 103 | |
| 104 | void |
| 105 | reduceRemainingNh() |
| 106 | { |
| 107 | m_remainingNh--; |
| 108 | // Check that remaining nexthops >= remaining uw nexthops. |
| 109 | NS_ABORT_UNLESS(m_remainingNh > 0 && m_remainingNh > getRemainingUw()); |
| 110 | } |
| 111 | |
| 112 | private: |
| 113 | void |
| 114 | eraseUw(FibNextHop nh) |
| 115 | { |
| 116 | NS_ABORT_UNLESS(m_uwSet.size() > 0); |
| 117 | auto success = m_uwSet.erase(nh); |
| 118 | NS_ABORT_UNLESS(success == 1); |
| 119 | } |
| 120 | |
| 121 | FibNextHop |
| 122 | getHighestCostUw() const |
| 123 | { |
| 124 | NS_ABORT_UNLESS(m_uwSet.size() > 0); |
| 125 | NS_ABORT_UNLESS(std::prev(m_uwSet.end()) != m_uwSet.end()); |
| 126 | return *(std::prev(m_uwSet.end())); |
| 127 | } |
| 128 | |
| 129 | private: |
| 130 | int m_nodeId; |
| 131 | int m_remainingNh; |
| 132 | set<FibNextHop> m_uwSet; |
| 133 | |
| 134 | friend std::ostream& |
| 135 | operator<<(std::ostream&, const NodePrio& node); |
| 136 | }; |
| 137 | |
| 138 | std::ostream& |
| 139 | operator<<(std::ostream& os, const NodePrio& node) |
| 140 | { |
| 141 | return os << "Id: " << node.m_nodeId << ", remaining NH: " << node.m_remainingNh |
| 142 | << ", remaining UW: " << node.getRemainingUw() << " "; |
| 143 | } |
| 144 | |
| 145 | int |
| 146 | removeLoops(AllNodeFib& allNodeFIB, bool printOutput) |
| 147 | { |
| 148 | int removedLoopCounter = 0; |
| 149 | int upwardCounter = 0; |
| 150 | |
| 151 | const int NUM_NODES{static_cast<int>(allNodeFIB.size())}; |
| 152 | |
| 153 | // Build graph with boost graph library: |
| 154 | DiGraph dg{}; |
| 155 | |
| 156 | // Add all Arcs that fit into FIB. // O(n) |
| 157 | for (int dstId = 0; dstId < NUM_NODES; dstId++) { |
| 158 | // 1. Get DiGraph from Fib // |
| 159 | getDigraphFromFib(dg, allNodeFIB, dstId); |
| 160 | |
| 161 | // NodeId -> set<UwNexthops> |
| 162 | std::priority_queue<NodePrio> q; |
| 163 | |
| 164 | // 2. Put nodes in the queue, ordered by # remaining nexthops, then CostDelta // O(n^2) |
| 165 | for (const auto& node : allNodeFIB) { |
| 166 | int nodeId{node.first}; |
| 167 | const AbstractFib& fib{node.second}; |
| 168 | if (nodeId == dstId) { |
| 169 | continue; |
| 170 | } |
| 171 | |
| 172 | const auto& uwNhSet = fib.getUpwardNexthops(dstId); |
| 173 | if (!uwNhSet.empty()) { |
| 174 | upwardCounter += uwNhSet.size(); |
| 175 | |
| 176 | int fibSize{fib.numEnabledNhPerDst(dstId)}; |
| 177 | // NodePrio tmpNode {nodeId, fibSize, uwNhSet}; |
| 178 | q.emplace(nodeId, fibSize, uwNhSet); |
| 179 | } |
| 180 | } |
| 181 | |
| 182 | // 3. Iterate PriorityQueue // |
| 183 | while (!q.empty()) { |
| 184 | NodePrio node = q.top(); |
| 185 | q.pop(); |
| 186 | |
| 187 | int nodeId = node.getId(); |
| 188 | int nhId = node.popHighestCostUw().getNexthopId(); |
| 189 | |
| 190 | // Remove opposite of Uphill link |
| 191 | // int arcId1 {getArcId(arcMap, nhId, nodeId)}; |
| 192 | auto res = boost::edge(static_cast<uint64_t>(nhId), static_cast<uint64_t>(nodeId), dg); |
| 193 | |
| 194 | auto arc = res.first; |
| 195 | bool arcExists = res.second; |
| 196 | |
| 197 | if (arcExists) { |
| 198 | boost::remove_edge(arc, dg); |
| 199 | } |
| 200 | |
| 201 | // 2. Loop Check: Is the current node still reachable for the uphill nexthop? |
| 202 | // Uses BFS: |
| 203 | // bool willLoop = bfs(dg).run(dg.nodeFromId(nhId), dg.nodeFromId(nodeId)); // O(m^2n) |
| 204 | |
| 205 | std::vector<int> dists(num_vertices(dg)); |
| 206 | |
| 207 | auto weightmap = get(boost::edge_weight, dg); |
| 208 | |
| 209 | const auto& x = boost::edges(dg); |
| 210 | for (auto e = x.first; e != x.second; e++) { |
| 211 | int weight = get(weightmap, *e); |
| 212 | NS_ABORT_UNLESS(weight == 1); // Only use uniform weights. |
| 213 | } |
| 214 | |
| 215 | // TODO: Could be replaced by BFS/DFS to improve speed. |
| 216 | dijkstra_shortest_paths(dg, static_cast<uint64_t>(nhId), |
| 217 | distance_map( |
| 218 | boost::make_iterator_property_map(dists.begin(), get(boost::vertex_index, dg)))); |
| 219 | |
| 220 | bool willLoop = (dists.at(static_cast<size_t>(nodeId)) < (std::numeric_limits<int>::max() - 1)); |
| 221 | |
| 222 | // Uphill nexthop loops back to original node |
| 223 | if (willLoop) { |
| 224 | node.reduceRemainingNh(); |
| 225 | removedLoopCounter++; |
| 226 | |
| 227 | // Erase FIB entry |
| 228 | allNodeFIB.at(node.getId()).erase(dstId, nhId); |
| 229 | |
| 230 | auto res2 = boost::edge(static_cast<uint64_t>(node.getId()), static_cast<uint64_t>(nhId), dg); |
| 231 | auto arc2 = res2.first; |
| 232 | NS_ABORT_UNLESS(res.second); |
| 233 | |
| 234 | boost::remove_edge(arc2, dg); |
| 235 | } |
| 236 | |
| 237 | // Add opposite of UW link back: |
| 238 | if (arcExists) { |
| 239 | boost::add_edge(static_cast<uint64_t>(nhId), static_cast<uint64_t>(nodeId), 1, dg); |
| 240 | } |
| 241 | |
| 242 | // If not has further UW nexthops: Requeue. |
| 243 | if (node.getRemainingUw() > 0) { |
| 244 | q.push(node); |
| 245 | } |
| 246 | } |
| 247 | } |
| 248 | |
| 249 | if (printOutput) { |
| 250 | std::cout << "Found " << upwardCounter << " UW nexthops, Removed " << removedLoopCounter |
| 251 | << " Looping UwNhs, Remaining: " << upwardCounter - removedLoopCounter << " NHs\n"; |
| 252 | } |
| 253 | NS_ABORT_UNLESS((upwardCounter - removedLoopCounter) >= 0); |
| 254 | |
| 255 | return removedLoopCounter; |
| 256 | } |
| 257 | |
| 258 | int |
| 259 | removeDeadEnds(AllNodeFib& allNodeFIB, bool printOutput) |
| 260 | { |
| 261 | int NUM_NODES{static_cast<int>(allNodeFIB.size())}; |
| 262 | int checkedUwCounter{0}; |
| 263 | int uwCounter{0}; |
| 264 | int totalCounter{0}; |
| 265 | int removedDeadendCounter{0}; |
| 266 | |
| 267 | for (int dstId = 0; dstId < NUM_NODES; dstId++) { |
| 268 | // NodeId -> FibNexthops (Order important) |
| 269 | set<std::pair<int, FibNextHop>> nhSet; |
| 270 | |
| 271 | // 1. Put all uwNexthops in set<NodeId, FibNexhtop>: |
| 272 | for (const auto& node : allNodeFIB) { |
| 273 | int nodeId{node.first}; |
| 274 | if (nodeId == dstId) { |
| 275 | continue; |
| 276 | } |
| 277 | |
| 278 | totalCounter += node.second.getNexthops(dstId).size(); |
| 279 | |
| 280 | const auto& uwNhSet = node.second.getUpwardNexthops(dstId); |
| 281 | uwCounter += uwNhSet.size(); |
| 282 | for (const FibNextHop& fibNh : uwNhSet) { |
| 283 | nhSet.emplace(nodeId, fibNh); |
| 284 | } |
| 285 | } |
| 286 | |
| 287 | // FibNexthops ordered by (costDelta, cost, nhId). |
| 288 | // Start with nexthop with highest cost: |
| 289 | while (!nhSet.empty()) { |
| 290 | checkedUwCounter++; |
| 291 | |
| 292 | // Pop from queue: |
| 293 | const auto& nhPair = nhSet.begin(); |
| 294 | NS_ABORT_UNLESS(nhPair != nhSet.end()); |
| 295 | nhSet.erase(nhPair); |
| 296 | |
| 297 | int nodeId = nhPair->first; |
| 298 | const FibNextHop& nh = nhPair->second; |
| 299 | AbstractFib& fib = allNodeFIB.at(nodeId); |
| 300 | |
| 301 | if (nh.getNexthopId() == dstId) { |
| 302 | continue; |
| 303 | } |
| 304 | |
| 305 | int reverseEntries{allNodeFIB.at(nh.getNexthopId()).numEnabledNhPerDst(dstId)}; |
| 306 | |
| 307 | // Must have at least one FIB entry. |
| 308 | NS_ABORT_UNLESS(reverseEntries > 0); |
| 309 | |
| 310 | // If it has exactly 1 entry -> Is downward back through the upward nexthop! |
| 311 | // Higher O-Complexity below: |
| 312 | if (reverseEntries <= 1) { |
| 313 | removedDeadendCounter++; |
| 314 | |
| 315 | // Erase NhEntry from FIB: |
| 316 | fib.erase(dstId, nh.getNexthopId()); |
| 317 | |
| 318 | // Push into Queue: All NhEntries that lead to m_nodeId! |
| 319 | const auto& nexthops = fib.getNexthops(dstId); |
| 320 | |
| 321 | for (const auto& ownNhs : nexthops) { |
| 322 | if (ownNhs.getType() == NextHopType::DOWNWARD && ownNhs.getNexthopId() != dstId) { |
| 323 | const auto& reverseNh = allNodeFIB.at(ownNhs.getNexthopId()).getNexthops(dstId); |
| 324 | |
| 325 | for (const auto& y : reverseNh) { |
| 326 | if (y.getNexthopId() == nodeId) { |
| 327 | NS_ABORT_UNLESS(y.getType() == NextHopType::UPWARD); |
| 328 | nhSet.emplace(ownNhs.getNexthopId(), y); |
| 329 | break; |
| 330 | } |
| 331 | } |
| 332 | } |
| 333 | } |
| 334 | } |
| 335 | } |
| 336 | } |
| 337 | |
| 338 | if (printOutput) { |
| 339 | std::cout << "Checked " << checkedUwCounter << " Upward NHs, Removed " << removedDeadendCounter |
| 340 | << " Deadend UwNhs, Remaining: " << uwCounter - removedDeadendCounter << " UW NHs, " |
| 341 | << totalCounter - removedDeadendCounter << " total nexthops\n"; |
| 342 | } |
| 343 | |
| 344 | return removedDeadendCounter; |
| 345 | } |
| 346 | |
| 347 | } // namespace ndn |
| 348 | } // namespace ns3 |