blob: dffe4a34c355f6d3b283f8e22a611eb5a2510083 [file] [log] [blame]
akmhoque3d06e792014-05-27 16:23:20 -05001/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2/**
3 * Copyright (c) 2014 University of Memphis,
4 * Regents of the University of California
5 *
6 * This file is part of NLSR (Named-data Link State Routing).
7 * See AUTHORS.md for complete list of NLSR authors and contributors.
8 *
9 * NLSR is free software: you can redistribute it and/or modify it under the terms
10 * of the GNU General Public License as published by the Free Software Foundation,
11 * either version 3 of the License, or (at your option) any later version.
12 *
13 * NLSR is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
14 * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
15 * PURPOSE. See the GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License along with
18 * NLSR, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
19 *
20 * \author A K M Mahmudul Hoque <ahoque1@memphis.edu>
21 *
22 **/
akmhoque53353462014-04-22 08:43:45 -050023#include <iostream>
24#include <cmath>
25#include "lsdb.hpp"
26#include "routing-table-calculator.hpp"
27#include "map.hpp"
28#include "lsa.hpp"
29#include "nexthop.hpp"
30#include "nlsr.hpp"
akmhoque2f423352014-06-03 11:49:35 -050031#include "logger.hpp"
akmhoque53353462014-04-22 08:43:45 -050032
Vince Lehman9a709032014-09-13 16:28:07 -050033#include <boost/math/constants/constants.hpp>
34
akmhoque53353462014-04-22 08:43:45 -050035namespace nlsr {
36
akmhoque2f423352014-06-03 11:49:35 -050037INIT_LOGGER("RoutingTableCalculator");
akmhoque53353462014-04-22 08:43:45 -050038using namespace std;
39
40void
41RoutingTableCalculator::allocateAdjMatrix()
42{
Vince Lehman9a709032014-09-13 16:28:07 -050043 adjMatrix = new double*[m_nRouters];
44
45 for (size_t i = 0; i < m_nRouters; ++i) {
46 adjMatrix[i] = new double[m_nRouters];
akmhoque53353462014-04-22 08:43:45 -050047 }
48}
49
50void
51RoutingTableCalculator::initMatrix()
52{
Vince Lehman9a709032014-09-13 16:28:07 -050053 for (size_t i = 0; i < m_nRouters; i++) {
54 for (size_t j = 0; j < m_nRouters; j++) {
akmhoque53353462014-04-22 08:43:45 -050055 adjMatrix[i][j] = 0;
akmhoque157b0a42014-05-13 00:26:37 -050056 }
akmhoque53353462014-04-22 08:43:45 -050057 }
58}
59
60void
61RoutingTableCalculator::makeAdjMatrix(Nlsr& pnlsr, Map pMap)
62{
63 std::list<AdjLsa> adjLsdb = pnlsr.getLsdb().getAdjLsdb();
Vince Lehman9a709032014-09-13 16:28:07 -050064 for (std::list<AdjLsa>::iterator it = adjLsdb.begin(); it != adjLsdb.end() ; it++) {
65
66 int32_t row = pMap.getMappingNoByRouterName((*it).getOrigRouter());
67
akmhoque53353462014-04-22 08:43:45 -050068 std::list<Adjacent> adl = (*it).getAdl().getAdjList();
Vince Lehman9a709032014-09-13 16:28:07 -050069 for (std::list<Adjacent>::iterator itAdl = adl.begin(); itAdl != adl.end() ; itAdl++) {
70
71 int32_t col = pMap.getMappingNoByRouterName((*itAdl).getName());
akmhoque53353462014-04-22 08:43:45 -050072 double cost = (*itAdl).getLinkCost();
Vince Lehman9a709032014-09-13 16:28:07 -050073
74 if ((row >= 0 && row < static_cast<int32_t>(m_nRouters)) &&
75 (col >= 0 && col < static_cast<int32_t>(m_nRouters)))
76 {
akmhoque53353462014-04-22 08:43:45 -050077 adjMatrix[row][col] = cost;
78 }
79 }
80 }
81}
82
83void
akmhoque2f423352014-06-03 11:49:35 -050084RoutingTableCalculator::writeAdjMatrixLog()
akmhoque53353462014-04-22 08:43:45 -050085{
Vince Lehman9a709032014-09-13 16:28:07 -050086 for (size_t i = 0; i < m_nRouters; i++) {
akmhoque2f423352014-06-03 11:49:35 -050087 string line="";
Vince Lehman9a709032014-09-13 16:28:07 -050088 for (size_t j = 0; j < m_nRouters; j++) {
akmhoque2f423352014-06-03 11:49:35 -050089 line += boost::lexical_cast<std::string>(adjMatrix[i][j]);
90 line += " ";
akmhoque157b0a42014-05-13 00:26:37 -050091 }
akmhoque2f423352014-06-03 11:49:35 -050092 _LOG_DEBUG(line);
akmhoque53353462014-04-22 08:43:45 -050093 }
94}
95
96void
97RoutingTableCalculator::adjustAdMatrix(int source, int link, double linkCost)
98{
Vince Lehman9a709032014-09-13 16:28:07 -050099 for (int i = 0; i < static_cast<int>(m_nRouters); i++) {
akmhoque157b0a42014-05-13 00:26:37 -0500100 if (i == link) {
akmhoque53353462014-04-22 08:43:45 -0500101 adjMatrix[source][i] = linkCost;
102 }
akmhoque157b0a42014-05-13 00:26:37 -0500103 else {
akmhoque53353462014-04-22 08:43:45 -0500104 adjMatrix[source][i] = 0;
105 }
106 }
107}
108
109int
110RoutingTableCalculator::getNumOfLinkfromAdjMatrix(int sRouter)
111{
112 int noLink = 0;
Vince Lehman9a709032014-09-13 16:28:07 -0500113
114 for (size_t i = 0; i < m_nRouters; i++) {
akmhoque157b0a42014-05-13 00:26:37 -0500115 if (adjMatrix[sRouter][i] > 0) {
akmhoque53353462014-04-22 08:43:45 -0500116 noLink++;
117 }
118 }
119 return noLink;
120}
121
122void
123RoutingTableCalculator::getLinksFromAdjMatrix(int* links,
124 double* linkCosts, int source)
125{
126 int j = 0;
Vince Lehman9a709032014-09-13 16:28:07 -0500127
128 for (size_t i = 0; i < m_nRouters; i++) {
akmhoque157b0a42014-05-13 00:26:37 -0500129 if (adjMatrix[source][i] > 0) {
akmhoque53353462014-04-22 08:43:45 -0500130 links[j] = i;
131 linkCosts[j] = adjMatrix[source][i];
132 j++;
133 }
134 }
135}
136
137void
138RoutingTableCalculator::freeAdjMatrix()
139{
Vince Lehman9a709032014-09-13 16:28:07 -0500140 for (size_t i = 0; i < m_nRouters; ++i) {
akmhoque53353462014-04-22 08:43:45 -0500141 delete [] adjMatrix[i];
142 }
143 delete [] adjMatrix;
144}
145
146
147void
148RoutingTableCalculator::allocateLinks()
149{
150 links = new int[vNoLink];
151}
152
153void
154RoutingTableCalculator::allocateLinkCosts()
155{
156 linkCosts = new double[vNoLink];
157}
158
159
160void
161RoutingTableCalculator::freeLinks()
162{
163 delete [] links;
164}
165void
166RoutingTableCalculator::freeLinksCosts()
167{
168 delete [] linkCosts;
169}
170
171void
172LinkStateRoutingTableCalculator::calculatePath(Map& pMap,
173 RoutingTable& rt, Nlsr& pnlsr)
174{
akmhoque2f423352014-06-03 11:49:35 -0500175 _LOG_DEBUG("LinkStateRoutingTableCalculator::calculatePath Called");
akmhoque53353462014-04-22 08:43:45 -0500176 allocateAdjMatrix();
177 initMatrix();
178 makeAdjMatrix(pnlsr, pMap);
akmhoque2f423352014-06-03 11:49:35 -0500179 writeAdjMatrixLog();
akmhoque31d1d4b2014-05-05 22:08:14 -0500180 int sourceRouter = pMap.getMappingNoByRouterName(pnlsr.getConfParameter().getRouterPrefix());
akmhoque53353462014-04-22 08:43:45 -0500181 allocateParent();
182 allocateDistance();
akmhoque157b0a42014-05-13 00:26:37 -0500183 if (pnlsr.getConfParameter().getMaxFacesPerPrefix() == 1) {
akmhoque53353462014-04-22 08:43:45 -0500184 // Single Path
185 doDijkstraPathCalculation(sourceRouter);
akmhoque53353462014-04-22 08:43:45 -0500186 // update routing table
187 addAllLsNextHopsToRoutingTable(pnlsr, rt, pMap, sourceRouter);
188 }
akmhoque157b0a42014-05-13 00:26:37 -0500189 else {
akmhoque53353462014-04-22 08:43:45 -0500190 // Multi Path
191 setNoLink(getNumOfLinkfromAdjMatrix(sourceRouter));
192 allocateLinks();
193 allocateLinkCosts();
194 getLinksFromAdjMatrix(links, linkCosts, sourceRouter);
akmhoque157b0a42014-05-13 00:26:37 -0500195 for (int i = 0 ; i < vNoLink; i++) {
akmhoque53353462014-04-22 08:43:45 -0500196 adjustAdMatrix(sourceRouter, links[i], linkCosts[i]);
akmhoque2f423352014-06-03 11:49:35 -0500197 writeAdjMatrixLog();
akmhoque53353462014-04-22 08:43:45 -0500198 doDijkstraPathCalculation(sourceRouter);
akmhoque53353462014-04-22 08:43:45 -0500199 //update routing table
200 addAllLsNextHopsToRoutingTable(pnlsr, rt, pMap, sourceRouter);
201 }
202 freeLinks();
203 freeLinksCosts();
204 }
205 freeParent();
206 freeDistance();
207 freeAdjMatrix();
208}
209
210void
211LinkStateRoutingTableCalculator::doDijkstraPathCalculation(int sourceRouter)
212{
213 int i;
214 int v, u;
Vince Lehman9a709032014-09-13 16:28:07 -0500215 int* Q = new int[m_nRouters];
akmhoque53353462014-04-22 08:43:45 -0500216 int head = 0;
217 /* Initiate the Parent */
Vince Lehman9a709032014-09-13 16:28:07 -0500218 for (i = 0 ; i < static_cast<int>(m_nRouters); i++) {
akmhoque53353462014-04-22 08:43:45 -0500219 m_parent[i] = EMPTY_PARENT;
220 m_distance[i] = INF_DISTANCE;
221 Q[i] = i;
222 }
akmhoque157b0a42014-05-13 00:26:37 -0500223 if (sourceRouter != NO_MAPPING_NUM) {
akmhoque53353462014-04-22 08:43:45 -0500224 m_distance[sourceRouter] = 0;
Vince Lehman9a709032014-09-13 16:28:07 -0500225 sortQueueByDistance(Q, m_distance, head, m_nRouters);
226 while (head < static_cast<int>(m_nRouters)) {
akmhoque53353462014-04-22 08:43:45 -0500227 u = Q[head];
akmhoque157b0a42014-05-13 00:26:37 -0500228 if (m_distance[u] == INF_DISTANCE) {
akmhoque53353462014-04-22 08:43:45 -0500229 break;
230 }
Vince Lehman9a709032014-09-13 16:28:07 -0500231 for (v = 0 ; v < static_cast<int>(m_nRouters); v++) {
akmhoque157b0a42014-05-13 00:26:37 -0500232 if (adjMatrix[u][v] > 0) {
Vince Lehman9a709032014-09-13 16:28:07 -0500233 if (isNotExplored(Q, v, head + 1, m_nRouters)) {
akmhoque157b0a42014-05-13 00:26:37 -0500234 if (m_distance[u] + adjMatrix[u][v] < m_distance[v]) {
akmhoque53353462014-04-22 08:43:45 -0500235 m_distance[v] = m_distance[u] + adjMatrix[u][v] ;
236 m_parent[v] = u;
237 }
238 }
239 }
240 }
241 head++;
Vince Lehman9a709032014-09-13 16:28:07 -0500242 sortQueueByDistance(Q, m_distance, head, m_nRouters);
akmhoque53353462014-04-22 08:43:45 -0500243 }
244 }
245 delete [] Q;
246}
247
248void
Vince Lehman9a709032014-09-13 16:28:07 -0500249LinkStateRoutingTableCalculator::addAllLsNextHopsToRoutingTable(Nlsr& pnlsr, RoutingTable& rt,
250 Map& pMap, uint32_t sourceRouter)
akmhoque53353462014-04-22 08:43:45 -0500251{
akmhoque2f423352014-06-03 11:49:35 -0500252 _LOG_DEBUG("LinkStateRoutingTableCalculator::addAllNextHopsToRoutingTable Called");
Vince Lehman9a709032014-09-13 16:28:07 -0500253
akmhoque53353462014-04-22 08:43:45 -0500254 int nextHopRouter = 0;
Vince Lehman9a709032014-09-13 16:28:07 -0500255
256 for (size_t i = 0; i < m_nRouters ; i++) {
akmhoque157b0a42014-05-13 00:26:37 -0500257 if (i != sourceRouter) {
Vince Lehman9a709032014-09-13 16:28:07 -0500258
akmhoque53353462014-04-22 08:43:45 -0500259 nextHopRouter = getLsNextHop(i, sourceRouter);
Vince Lehman9a709032014-09-13 16:28:07 -0500260
akmhoque157b0a42014-05-13 00:26:37 -0500261 if (nextHopRouter != NO_NEXT_HOP) {
Vince Lehman9a709032014-09-13 16:28:07 -0500262
akmhoque53353462014-04-22 08:43:45 -0500263 double routeCost = m_distance[i];
akmhoque31d1d4b2014-05-05 22:08:14 -0500264 ndn::Name nextHopRouterName = pMap.getRouterNameByMappingNo(nextHopRouter);
akmhoque157b0a42014-05-13 00:26:37 -0500265 std::string nextHopFace =
266 pnlsr.getAdjacencyList().getAdjacent(nextHopRouterName).getConnectingFaceUri();
akmhoque53353462014-04-22 08:43:45 -0500267 // Add next hop to routing table
akmhoque157b0a42014-05-13 00:26:37 -0500268 NextHop nh(nextHopFace, routeCost);
akmhoque53353462014-04-22 08:43:45 -0500269 rt.addNextHop(pMap.getRouterNameByMappingNo(i), nh);
270 }
271 }
272 }
273}
274
275int
276LinkStateRoutingTableCalculator::getLsNextHop(int dest, int source)
277{
278 int nextHop = NO_NEXT_HOP;
akmhoque157b0a42014-05-13 00:26:37 -0500279 while (m_parent[dest] != EMPTY_PARENT) {
akmhoque53353462014-04-22 08:43:45 -0500280 nextHop = dest;
281 dest = m_parent[dest];
282 }
akmhoque157b0a42014-05-13 00:26:37 -0500283 if (dest != source) {
akmhoque53353462014-04-22 08:43:45 -0500284 nextHop = NO_NEXT_HOP;
285 }
286 return nextHop;
287}
288
289void
akmhoque53353462014-04-22 08:43:45 -0500290LinkStateRoutingTableCalculator::sortQueueByDistance(int* Q,
akmhoque2f423352014-06-03 11:49:35 -0500291 double* dist,
292 int start, int element)
akmhoque53353462014-04-22 08:43:45 -0500293{
akmhoque157b0a42014-05-13 00:26:37 -0500294 for (int i = start ; i < element ; i++) {
295 for (int j = i + 1; j < element; j++) {
296 if (dist[Q[j]] < dist[Q[i]]) {
akmhoque53353462014-04-22 08:43:45 -0500297 int tempU = Q[j];
298 Q[j] = Q[i];
299 Q[i] = tempU;
300 }
301 }
302 }
303}
304
305int
306LinkStateRoutingTableCalculator::isNotExplored(int* Q,
307 int u, int start, int element)
308{
309 int ret = 0;
akmhoque157b0a42014-05-13 00:26:37 -0500310 for (int i = start; i < element; i++) {
311 if (Q[i] == u) {
akmhoque53353462014-04-22 08:43:45 -0500312 ret = 1;
313 break;
314 }
315 }
316 return ret;
317}
318
319void
320LinkStateRoutingTableCalculator::allocateParent()
321{
Vince Lehman9a709032014-09-13 16:28:07 -0500322 m_parent = new int[m_nRouters];
akmhoque53353462014-04-22 08:43:45 -0500323}
324
325void
326LinkStateRoutingTableCalculator::allocateDistance()
327{
Vince Lehman9a709032014-09-13 16:28:07 -0500328 m_distance = new double[m_nRouters];
akmhoque53353462014-04-22 08:43:45 -0500329}
330
331void
332LinkStateRoutingTableCalculator::freeParent()
333{
334 delete [] m_parent;
335}
336
337void LinkStateRoutingTableCalculator::freeDistance()
338{
339 delete [] m_distance;
340}
341
Vince Lehman9a709032014-09-13 16:28:07 -0500342const double HyperbolicRoutingCalculator::MATH_PI = boost::math::constants::pi<double>();
akmhoque53353462014-04-22 08:43:45 -0500343
Vince Lehman9a709032014-09-13 16:28:07 -0500344const double HyperbolicRoutingCalculator::UNKNOWN_DISTANCE = -1.0;
345const double HyperbolicRoutingCalculator::UNKNOWN_RADIUS = -1.0;
346
347const int32_t HyperbolicRoutingCalculator::ROUTER_NOT_FOUND = -1.0;
akmhoque53353462014-04-22 08:43:45 -0500348
349void
Vince Lehman9a709032014-09-13 16:28:07 -0500350HyperbolicRoutingCalculator::calculatePaths(Map& map, RoutingTable& rt,
351 Lsdb& lsdb, AdjacencyList& adjacencies)
akmhoque53353462014-04-22 08:43:45 -0500352{
Vince Lehman9a709032014-09-13 16:28:07 -0500353 _LOG_TRACE("Calculating hyperbolic paths");
354
355 int thisRouter = map.getMappingNoByRouterName(m_thisRouterName);
356
357 // Iterate over directly connected neighbors
358 std::list<Adjacent> neighbors = adjacencies.getAdjList();
359 for (std::list<Adjacent>::iterator adj = neighbors.begin(); adj != neighbors.end(); ++adj) {
360
361 // Don't calculate nexthops using an inactive router
362 if (adj->getStatus() == Adjacent::STATUS_INACTIVE) {
363 _LOG_TRACE(adj->getName() << " is inactive; not using it as a nexthop");
364 continue;
365 }
366
367 ndn::Name srcRouterName = adj->getName();
368
369 // Don't calculate nexthops for this router to other routers
370 if (srcRouterName == m_thisRouterName) {
371 continue;
372 }
373
374 std::string srcFaceUri = adj->getConnectingFaceUri();
375
376 // Install nexthops for this router to the neighbor; direct neighbors have a 0 cost link
377 addNextHop(srcRouterName, srcFaceUri, 0, rt);
378
379 int src = map.getMappingNoByRouterName(srcRouterName);
380
381 if (src == ROUTER_NOT_FOUND) {
382 _LOG_WARN(adj->getName() << " does not exist in the router map!");
383 continue;
384 }
385
386 // Get hyperbolic distance from direct neighbor to every other router
387 for (int dest = 0; dest < static_cast<int>(m_nRouters); ++dest) {
388 // Don't calculate nexthops to this router or from a router to itself
389 if (dest != thisRouter && dest != src) {
390
391 ndn::Name destRouterName = map.getRouterNameByMappingNo(dest);
392
393 double distance = getHyperbolicDistance(map, lsdb, srcRouterName, destRouterName);
394
395 // Could not compute distance
396 if (distance == UNKNOWN_DISTANCE) {
397 _LOG_WARN("Could not calculate hyperbolic distance from " << srcRouterName << " to " <<
398 destRouterName);
399 continue;
akmhoque53353462014-04-22 08:43:45 -0500400 }
akmhoque53353462014-04-22 08:43:45 -0500401
Vince Lehman9a709032014-09-13 16:28:07 -0500402 addNextHop(destRouterName, srcFaceUri, distance, rt);
403 }
akmhoquedcee9362014-08-05 22:58:01 -0500404 }
akmhoque53353462014-04-22 08:43:45 -0500405 }
406}
407
408double
Vince Lehman9a709032014-09-13 16:28:07 -0500409HyperbolicRoutingCalculator::getHyperbolicDistance(Map& map, Lsdb& lsdb,
410 ndn::Name src, ndn::Name dest)
akmhoque53353462014-04-22 08:43:45 -0500411{
Vince Lehman9a709032014-09-13 16:28:07 -0500412 _LOG_TRACE("Calculating hyperbolic distance from " << src << " to " << dest);
akmhoquedcee9362014-08-05 22:58:01 -0500413
Vince Lehman9a709032014-09-13 16:28:07 -0500414 double distance = UNKNOWN_DISTANCE;
415
416 ndn::Name srcLsaKey = src;
417 srcLsaKey.append("coordinate");
418
419 CoordinateLsa* srcLsa = lsdb.findCoordinateLsa(srcLsaKey);
420
421 ndn::Name destLsaKey = dest;
422 destLsaKey.append("coordinate");
423
424 CoordinateLsa* destLsa = lsdb.findCoordinateLsa(destLsaKey);
425
426 // Coordinate LSAs do not exist for these routers
427 if (srcLsa == NULL || destLsa == NULL) {
428 return UNKNOWN_DISTANCE;
akmhoquedcee9362014-08-05 22:58:01 -0500429 }
430
akmhoquedcee9362014-08-05 22:58:01 -0500431 double srcTheta = srcLsa->getCorTheta();
akmhoquedcee9362014-08-05 22:58:01 -0500432 double destTheta = destLsa->getCorTheta();
433
akmhoque53353462014-04-22 08:43:45 -0500434 double diffTheta = fabs(srcTheta - destTheta);
Vince Lehman9a709032014-09-13 16:28:07 -0500435
akmhoque157b0a42014-05-13 00:26:37 -0500436 if (diffTheta > MATH_PI) {
akmhoque53353462014-04-22 08:43:45 -0500437 diffTheta = 2 * MATH_PI - diffTheta;
438 }
Vince Lehman9a709032014-09-13 16:28:07 -0500439
440 double srcRadius = srcLsa->getCorRadius();
441 double destRadius = destLsa->getCorRadius();
442
443 if (srcRadius == UNKNOWN_RADIUS && destRadius == UNKNOWN_RADIUS) {
444 return UNKNOWN_DISTANCE;
445 }
446
447 if (diffTheta == 0) {
448 distance = fabs(srcRadius - destRadius);
akmhoque53353462014-04-22 08:43:45 -0500449 }
akmhoque157b0a42014-05-13 00:26:37 -0500450 else {
Vince Lehman9a709032014-09-13 16:28:07 -0500451 distance = acosh((cosh(srcRadius) * cosh(destRadius)) -
452 (sinh(srcRadius) * sinh(destRadius) * cos(diffTheta)));
akmhoque53353462014-04-22 08:43:45 -0500453 }
Vince Lehman9a709032014-09-13 16:28:07 -0500454
455 _LOG_TRACE("Distance from " << src << " to " << dest << " is " << distance);
456
akmhoque53353462014-04-22 08:43:45 -0500457 return distance;
458}
459
Vince Lehman9a709032014-09-13 16:28:07 -0500460void HyperbolicRoutingCalculator::addNextHop(ndn::Name dest, std::string faceUri,
461 double cost, RoutingTable& rt)
akmhoque53353462014-04-22 08:43:45 -0500462{
Vince Lehman9a709032014-09-13 16:28:07 -0500463 NextHop hop(faceUri, cost);
akmhoque53353462014-04-22 08:43:45 -0500464
Vince Lehman9a709032014-09-13 16:28:07 -0500465 _LOG_TRACE("Calculated " << hop << " for destination: " << dest);
akmhoque53353462014-04-22 08:43:45 -0500466
Vince Lehman9a709032014-09-13 16:28:07 -0500467 if (m_isDryRun) {
468 rt.addNextHopToDryTable(dest, hop);
469 }
470 else {
471 rt.addNextHop(dest, hop);
472 }
akmhoque53353462014-04-22 08:43:45 -0500473}
474
475}//namespace nlsr