route: Fix hyperbolic cost adjustment
refs: #1974
Change-Id: Ic96c94d978487bbef2804235b75aa227c350d941
diff --git a/src/route/nexthop.hpp b/src/route/nexthop.hpp
index b31d09a..0e409d2 100644
--- a/src/route/nexthop.hpp
+++ b/src/route/nexthop.hpp
@@ -23,6 +23,8 @@
#ifndef NLSR_NEXTHOP_HPP
#define NLSR_NEXTHOP_HPP
+#include "test-access-control.hpp"
+
#include <iostream>
#include <cmath>
#include <boost/cstdint.hpp>
@@ -34,10 +36,12 @@
NextHop()
: m_connectingFaceUri()
, m_routeCost(0)
+ , m_isHyperbolic(false)
{
}
NextHop(const std::string& cfu, double rc)
+ : m_isHyperbolic(false)
{
m_connectingFaceUri = cfu;
m_routeCost = rc;
@@ -58,7 +62,15 @@
uint64_t
getRouteCostAsAdjustedInteger() const
{
- return static_cast<uint64_t>(round(m_routeCost*HYPERBOLIC_COST_ADJUSTMENT_FACTOR));
+ if (m_isHyperbolic) {
+ // Round the cost to better preserve decimal cost differences
+ // e.g. Without rounding: 12.3456 > 12.3454 -> 12345 = 12345
+ // With rounding: 12.3456 > 12.3454 -> 12346 > 12345
+ return static_cast<uint64_t>(round(m_routeCost*HYPERBOLIC_COST_ADJUSTMENT_FACTOR));
+ }
+ else {
+ return static_cast<uint64_t>(m_routeCost);
+ }
}
double
@@ -73,10 +85,35 @@
m_routeCost = rc;
}
+ void
+ setHyperbolic(bool b)
+ {
+ m_isHyperbolic = b;
+ }
+
+ bool
+ isHyperbolic() const
+ {
+ return m_isHyperbolic;
+ }
+
private:
std::string m_connectingFaceUri;
double m_routeCost;
- static const uint64_t HYPERBOLIC_COST_ADJUSTMENT_FACTOR = 100;
+ bool m_isHyperbolic;
+
+PUBLIC_WITH_TESTS_ELSE_PRIVATE:
+ /** \brief Used to adjust floating point route costs to integers
+ * Since NFD uses integer route costs in the FIB, hyperbolic paths with similar route costs
+ * will be rounded to integers and installed with identical nexthop costs.
+ *
+ * e.g. costs 12.34 and 12.35 will be equal in NFD's FIB
+ *
+ * This multiplier is used to differentiate similar route costs in the FIB.
+ *
+ * e.g costs 12.34 and 12.35 will be installed into NFD's FIB as 12340 and 12350
+ */
+ static const uint64_t HYPERBOLIC_COST_ADJUSTMENT_FACTOR = 1000;
};
std::ostream&
diff --git a/src/route/routing-table-calculator.cpp b/src/route/routing-table-calculator.cpp
index dffe4a3..24707b0 100644
--- a/src/route/routing-table-calculator.cpp
+++ b/src/route/routing-table-calculator.cpp
@@ -461,6 +461,7 @@
double cost, RoutingTable& rt)
{
NextHop hop(faceUri, cost);
+ hop.setHyperbolic(true);
_LOG_TRACE("Calculated " << hop << " for destination: " << dest);
diff --git a/tests/test-hyperbolic-calculator.cpp b/tests/test-hyperbolic-calculator.cpp
index eaf1f1a..65b0ad2 100644
--- a/tests/test-hyperbolic-calculator.cpp
+++ b/tests/test-hyperbolic-calculator.cpp
@@ -131,6 +131,15 @@
const std::string HyperbolicCalculatorFixture::ROUTER_B_FACE = "face-b";
const std::string HyperbolicCalculatorFixture::ROUTER_C_FACE = "face-c";
+uint64_t
+applyHyperbolicFactorAndRound(double d)
+{
+ // Hyperbolic costs in the tests were calculated with 1*10^-9 precision.
+ // A factor larger than 1*10^9 will cause the tests to fail.
+ BOOST_REQUIRE(NextHop::HYPERBOLIC_COST_ADJUSTMENT_FACTOR <= 1000000000);
+ return round(NextHop::HYPERBOLIC_COST_ADJUSTMENT_FACTOR*d);
+}
+
BOOST_FIXTURE_TEST_SUITE(TestHyperbolicRoutingCalculator, HyperbolicCalculatorFixture)
BOOST_AUTO_TEST_CASE(Basic)
@@ -140,8 +149,7 @@
RoutingTableEntry* entryB = routingTable.findRoutingTableEntry(ROUTER_B_NAME);
- // Router A should be able to get to B through B with cost 0 and to B through
- // C with cost 2010
+ // Router A should be able to get to B through B with cost 0 and to B through C
NexthopList& bHopList = entryB->getNexthopList();
BOOST_REQUIRE_EQUAL(bHopList.getNextHops().size(), 2);
@@ -150,13 +158,12 @@
uint64_t cost = it->getRouteCostAsAdjustedInteger();
BOOST_CHECK((faceUri == ROUTER_B_FACE && cost == 0) ||
- (faceUri == ROUTER_C_FACE && cost == 2010));
+ (faceUri == ROUTER_C_FACE && cost == applyHyperbolicFactorAndRound(20.103356956)));
}
RoutingTableEntry* entryC = routingTable.findRoutingTableEntry(ROUTER_C_NAME);
- // Router A should be able to get to C through C with cost 0 and to C through
- // B with cost 2010
+ // Router A should be able to get to C through C with cost 0 and to C through B
NexthopList& cHopList = entryC->getNexthopList();
BOOST_REQUIRE_EQUAL(cHopList.getNextHops().size(), 2);
@@ -164,7 +171,7 @@
std::string faceUri = it->getConnectingFaceUri();
uint64_t cost = it->getRouteCostAsAdjustedInteger();
- BOOST_CHECK((faceUri == ROUTER_B_FACE && cost == 2010) ||
+ BOOST_CHECK((faceUri == ROUTER_B_FACE && cost == applyHyperbolicFactorAndRound(20.103356956)) ||
(faceUri == ROUTER_C_FACE && cost == 0));
}
}
diff --git a/tests/test-nexthop-list.cpp b/tests/test-nexthop-list.cpp
index eeea461..e4e8bc7 100644
--- a/tests/test-nexthop-list.cpp
+++ b/tests/test-nexthop-list.cpp
@@ -43,7 +43,7 @@
BOOST_CHECK_EQUAL(nhl1.getSize(), (uint32_t)0);
}
-BOOST_AUTO_TEST_CASE(RemoveNextHop)
+BOOST_AUTO_TEST_CASE(LinkStateRemoveNextHop)
{
NextHop hop1;
hop1.setRouteCost(12.34);
@@ -52,6 +52,28 @@
hopList.addNextHop(hop1);
NextHop hop2;
+ hop2.setRouteCost(13.01);
+
+ BOOST_REQUIRE_EQUAL(hopList.getSize(), 1);
+
+ hopList.removeNextHop(hop2);
+ BOOST_CHECK_EQUAL(hopList.getSize(), 1);
+
+ hopList.removeNextHop(hop1);
+ BOOST_CHECK_EQUAL(hopList.getSize(), 0);
+}
+
+BOOST_AUTO_TEST_CASE(HyperbolicRemoveNextHop)
+{
+ NextHop hop1;
+ hop1.setHyperbolic(true);
+ hop1.setRouteCost(12.34);
+
+ NexthopList hopList;
+ hopList.addNextHop(hop1);
+
+ NextHop hop2;
+ hop2.setHyperbolic(true);
hop2.setRouteCost(12.35);
BOOST_REQUIRE_EQUAL(hopList.getSize(), 1);
diff --git a/tests/test-nexthop.cpp b/tests/test-nexthop.cpp
index da3a19f..9720ece 100644
--- a/tests/test-nexthop.cpp
+++ b/tests/test-nexthop.cpp
@@ -29,7 +29,19 @@
BOOST_AUTO_TEST_SUITE(TestNexthop)
-BOOST_AUTO_TEST_CASE(NexthopSetAndGet)
+double
+getHyperbolicAdjustedDecimal(unsigned int i)
+{
+ return static_cast<double>(i)/(10*NextHop::HYPERBOLIC_COST_ADJUSTMENT_FACTOR);
+}
+
+uint64_t
+applyHyperbolicFactorAndRound(double d)
+{
+ return round(NextHop::HYPERBOLIC_COST_ADJUSTMENT_FACTOR*d);
+}
+
+BOOST_AUTO_TEST_CASE(LinkStateSetAndGet)
{
NextHop hop1;
hop1.setConnectingFaceUri("udp://test/uri");
@@ -37,17 +49,60 @@
BOOST_CHECK_EQUAL(hop1.getConnectingFaceUri(), "udp://test/uri");
BOOST_CHECK_EQUAL(hop1.getRouteCost(), 12.34);
- BOOST_CHECK_EQUAL(hop1.getRouteCostAsAdjustedInteger(), 1234);
+ BOOST_CHECK_EQUAL(hop1.getRouteCostAsAdjustedInteger(), 12);
NextHop hop2;
hop2.setRouteCost(12.34);
BOOST_CHECK_EQUAL(hop1.getRouteCostAsAdjustedInteger(), hop2.getRouteCostAsAdjustedInteger());
+}
+
+BOOST_AUTO_TEST_CASE(HyperbolicSetAndGet)
+{
+ NextHop hop1;
+ hop1.setHyperbolic(true);
+ hop1.setConnectingFaceUri("udp://test/uri");
+ hop1.setRouteCost(12.34);
+
+ BOOST_CHECK_EQUAL(hop1.getConnectingFaceUri(), "udp://test/uri");
+ BOOST_CHECK_EQUAL(hop1.getRouteCost(), 12.34);
+ BOOST_CHECK_EQUAL(hop1.getRouteCostAsAdjustedInteger(), applyHyperbolicFactorAndRound(12.34));
+
+ NextHop hop2;
+ hop2.setHyperbolic(true);
+
+ hop2.setRouteCost(12.34);
+ BOOST_CHECK_EQUAL(hop1.getRouteCostAsAdjustedInteger(), hop2.getRouteCostAsAdjustedInteger());
hop2.setRouteCost(12.35);
BOOST_CHECK(hop1.getRouteCostAsAdjustedInteger() < hop2.getRouteCostAsAdjustedInteger());
}
+BOOST_AUTO_TEST_CASE(HyperbolicRound)
+{
+ NextHop hop1;
+ hop1.setHyperbolic(true);
+ hop1.setConnectingFaceUri("udp://test/uri");
+ hop1.setRouteCost(1 + getHyperbolicAdjustedDecimal(6));
+
+ BOOST_CHECK_EQUAL(hop1.getConnectingFaceUri(), "udp://test/uri");
+ BOOST_CHECK_EQUAL(hop1.getRouteCost(), 1 + getHyperbolicAdjustedDecimal(6));
+ BOOST_CHECK_EQUAL(hop1.getRouteCostAsAdjustedInteger(),
+ applyHyperbolicFactorAndRound((1 + getHyperbolicAdjustedDecimal(6))));
+
+ NextHop hop2;
+ hop2.setHyperbolic(true);
+
+ hop2.setRouteCost(1 + getHyperbolicAdjustedDecimal(6));
+ BOOST_CHECK_EQUAL(hop1.getRouteCostAsAdjustedInteger(), hop2.getRouteCostAsAdjustedInteger());
+
+ hop2.setRouteCost(1 + getHyperbolicAdjustedDecimal(5));
+ BOOST_CHECK_EQUAL(hop1.getRouteCostAsAdjustedInteger(), hop2.getRouteCostAsAdjustedInteger());
+
+ hop2.setRouteCost(1 + getHyperbolicAdjustedDecimal(4));
+ BOOST_CHECK(hop1.getRouteCostAsAdjustedInteger() > hop2.getRouteCostAsAdjustedInteger());
+}
+
BOOST_AUTO_TEST_SUITE_END()
} //namespace test