diff --git a/src/hello-protocol.cpp b/src/hello-protocol.cpp
index cc3ed63..9585255 100644
--- a/src/hello-protocol.cpp
+++ b/src/hello-protocol.cpp
@@ -24,6 +24,8 @@
 #include "utility/name-helper.hpp"
 #include "logger.hpp"
 
+#include <ndn-cxx/encoding/nfd-constants.hpp>
+
 namespace nlsr {
 
 INIT_LOGGER(HelloProtocol);
@@ -43,6 +45,24 @@
   , m_lsdb(lsdb)
   , m_adjacencyList(m_confParam.getAdjacencyList())
 {
+  ndn::Name name(m_confParam.getRouterPrefix());
+  name.append(NLSR_COMPONENT);
+  name.append(INFO_COMPONENT);
+
+  NLSR_LOG_DEBUG("Setting interest filter for Hello interest: " << name);
+
+  m_face.setInterestFilter(ndn::InterestFilter(name).allowLoopback(false),
+    [this] (const auto& name, const auto& interest) {
+      processInterest(name, interest);
+    },
+    [] (const auto& name) {
+      NLSR_LOG_DEBUG("Successfully registered prefix: " << name);
+    },
+    [] (const auto& name, const auto& resp) {
+      NLSR_LOG_ERROR("Failed to register prefix " << name);
+      NDN_THROW(std::runtime_error("Failed to register hello prefix: " + resp));
+    },
+    m_signingInfo, ndn::nfd::ROUTE_FLAG_CAPTURE);
 }
 
 void
@@ -161,7 +181,7 @@
   uint32_t infoIntTimedOutCount = m_adjacencyList.getTimedOutInterestCount(neighbor);
   NLSR_LOG_DEBUG("Status: " << status);
   NLSR_LOG_DEBUG("Info Interest Timed out: " << infoIntTimedOutCount);
-  if (infoIntTimedOutCount <= m_confParam.getInterestRetryNumber()) {
+  if (infoIntTimedOutCount < m_confParam.getInterestRetryNumber()) {
     // interest name: /<neighbor>/NLSR/INFO/<router>
     ndn::Name interestName(neighbor);
     interestName.append(NLSR_COMPONENT);
@@ -170,13 +190,17 @@
     NLSR_LOG_DEBUG("Resending interest: " << interestName);
     expressInterest(interestName, m_confParam.getInterestResendTime());
   }
-  else if ((status == Adjacent::STATUS_ACTIVE) &&
-           (infoIntTimedOutCount == m_confParam.getInterestRetryNumber())) {
+  else if (status == Adjacent::STATUS_ACTIVE) {
     m_adjacencyList.setStatusOfNeighbor(neighbor, Adjacent::STATUS_INACTIVE);
 
     NLSR_LOG_DEBUG("Neighbor: " << neighbor << " status changed to INACTIVE");
 
-    m_lsdb.scheduleAdjLsaBuild();
+    if (m_confParam.getHyperbolicState() == HYPERBOLIC_STATE_ON) {
+      m_routingTable.scheduleRoutingTableCalculation();
+    }
+    else {
+      m_lsdb.scheduleAdjLsaBuild();
+    }
   }
 }
 
diff --git a/src/hello-protocol.hpp b/src/hello-protocol.hpp
index efce624..9ff5924 100644
--- a/src/hello-protocol.hpp
+++ b/src/hello-protocol.hpp
@@ -125,33 +125,6 @@
   onContentValidationFailed(const ndn::Data& data,
                             const ndn::security::ValidationError& ve);
 
-  /*! \brief Treat a failed Face registration as an INACTIVE neighbor.
-   *
-   * If NLSR fails to register a Face when contacting a neighbor, it
-   * will instantly toggle that neighbor to INACTIVE. This is
-   * necessary because NLSR will put off building its own adjacency
-   * LSA until the status of each neighbor is definitively
-   * known. Without this, NLSR might have to wait many scheduled Hello
-   * intervals to finish building an adjacency LSA.
-   */
-  void
-  onRegistrationFailure(const ndn::nfd::ControlResponse& response,
-                        const ndn::Name& name);
-
-  /*! \brief Set up a Face for NLSR use.
-   *
-   * When NLSR receives a Hello Interest from a neighbor that it has
-   * not seen before, it may need to create a Face for that
-   * neighbor. After doing so, it will be necessary to inform NFD
-   * about the standard prefixes that NLSR needs a node to have in
-   * order to conduct normal operations. This function accomplishes
-   * that, and then sends its own Hello Interest to confirm the
-   * contact.
-   */
-  void
-  onRegistrationSuccess(const ndn::nfd::ControlParameters& commandSuccessResult,
-                        const ndn::Name& neighbor, const ndn::time::milliseconds& timeout);
-
 public:
   ndn::util::Signal<HelloProtocol, const ndn::Name&> onHelloDataValidated;
 
diff --git a/src/nlsr.cpp b/src/nlsr.cpp
index fac8ae7..590c8a4 100644
--- a/src/nlsr.cpp
+++ b/src/nlsr.cpp
@@ -31,7 +31,6 @@
 #include <vector>
 
 #include <ndn-cxx/net/face-uri.hpp>
-#include <ndn-cxx/signature.hpp>
 
 namespace nlsr {
 
@@ -94,9 +93,7 @@
 
   NLSR_LOG_DEBUG("Default NLSR identity: " << m_confParam.getSigningInfo().getSignerName());
 
-  // Can be moved to HelloProtocol and Lsdb ctor if initializeKey is set
-  // earlier in the Nlsr constructor so as to set m_signingInfo
-  setInfoInterestFilter();
+  // Can be moved to Lsdb ctor
   setLsaInterestFilter();
 
   // Add top-level prefixes: router and localhost prefix
@@ -154,7 +151,7 @@
 Nlsr::registrationFailed(const ndn::Name& name)
 {
   NLSR_LOG_ERROR("ERROR: Failed to register prefix " << name << " in local hub's daemon");
-  BOOST_THROW_EXCEPTION(Error("Error: Prefix registration failed"));
+  NDN_THROW(Error("Error: Prefix registration failed"));
 }
 
 void
@@ -164,22 +161,6 @@
 }
 
 void
-Nlsr::setInfoInterestFilter()
-{
-  ndn::Name name(m_confParam.getRouterPrefix());
-  name.append("nlsr");
-  name.append("INFO");
-
-  NLSR_LOG_DEBUG("Setting interest filter for Hello interest: " << name);
-
-  m_face.setInterestFilter(ndn::InterestFilter(name).allowLoopback(false),
-                           std::bind(&HelloProtocol::processInterest, &m_helloProtocol, _1, _2),
-                           std::bind(&Nlsr::onRegistrationSuccess, this, _1),
-                           std::bind(&Nlsr::registrationFailed, this, _1),
-                           m_confParam.getSigningInfo(), ndn::nfd::ROUTE_FLAG_CAPTURE);
-}
-
-void
 Nlsr::setLsaInterestFilter()
 {
   ndn::Name name = m_confParam.getLsaPrefix();
@@ -253,7 +234,7 @@
 void
 Nlsr::onFaceEventNotification(const ndn::nfd::FaceEventNotification& faceEventNotification)
 {
-  NLSR_LOG_TRACE("Nlsr::onFaceEventNotification called");
+  NLSR_LOG_TRACE("onFaceEventNotification called");
 
   switch (faceEventNotification.getKind()) {
     case ndn::nfd::FACE_EVENT_DESTROYED: {
@@ -288,10 +269,12 @@
           // has met the HELLO retry threshold
           adjacent->setInterestTimedOutNo(m_confParam.getInterestRetryNumber());
 
-          if (m_confParam.getHyperbolicState() != HYPERBOLIC_STATE_OFF) {
+          if (m_confParam.getHyperbolicState() == HYPERBOLIC_STATE_ON) {
             m_routingTable.scheduleRoutingTableCalculation();
           }
           else {
+            // Will call scheduleRoutingTableCalculation internally
+            // if needed in case of LS or DRY_RUN
             m_lsdb.scheduleAdjLsaBuild();
           }
         }
@@ -322,12 +305,10 @@
 
         registerAdjacencyPrefixes(*adjacent, ndn::time::milliseconds::max());
 
-        if (m_confParam.getHyperbolicState() != HYPERBOLIC_STATE_OFF) {
-          m_routingTable.scheduleRoutingTableCalculation();
-        }
-        else {
-         m_lsdb.scheduleAdjLsaBuild();
-        }
+        // We should not do scheduleRoutingTableCalculation or scheduleAdjLsaBuild here
+        // because once the prefixes are registered, we send a HelloInterest
+        // to the prefix (see NLSR ctor). HelloProtocol will call these functions
+        // once HelloData is received and validated.
       }
       break;
     }
diff --git a/src/nlsr.hpp b/src/nlsr.hpp
index cc8ee3c..841a15a 100644
--- a/src/nlsr.hpp
+++ b/src/nlsr.hpp
@@ -88,9 +88,6 @@
   onRegistrationSuccess(const ndn::Name& name);
 
   void
-  setInfoInterestFilter();
-
-  void
   setLsaInterestFilter();
 
   /*! \brief Add top level prefixes for Dispatcher
diff --git a/src/route/routing-table.hpp b/src/route/routing-table.hpp
index 8f9309b..4a0ebd2 100644
--- a/src/route/routing-table.hpp
+++ b/src/route/routing-table.hpp
@@ -26,8 +26,8 @@
 #include "signals.hpp"
 #include "lsdb.hpp"
 #include "route/fib.hpp"
+#include "test-access-control.hpp"
 
-#include <boost/cstdint.hpp>
 #include <ndn-cxx/util/scheduler.hpp>
 
 namespace nlsr {
@@ -166,6 +166,7 @@
 
   ndn::time::seconds m_routingCalcInterval;
 
+PUBLIC_WITH_TESTS_ELSE_PRIVATE:
   bool m_isRoutingTableCalculating;
   bool m_isRouteCalculationScheduled;
 
diff --git a/tests/test-common.hpp b/tests/test-common.hpp
index 49238ad..ea48ecc 100644
--- a/tests/test-common.hpp
+++ b/tests/test-common.hpp
@@ -33,7 +33,6 @@
 
 #include <ndn-cxx/face.hpp>
 #include <ndn-cxx/security/key-chain.hpp>
-#include <ndn-cxx/security/signature-sha256-with-rsa.hpp>
 #include <ndn-cxx/util/dummy-client-face.hpp>
 #include <ndn-cxx/util/scheduler.hpp>
 #include <ndn-cxx/util/time-unit-test-clock.hpp>
diff --git a/tests/test-hello-protocol.cpp b/tests/test-hello-protocol.cpp
new file mode 100644
index 0000000..67bf272
--- /dev/null
+++ b/tests/test-hello-protocol.cpp
@@ -0,0 +1,121 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) 2014-2020,  The University of Memphis,
+ *                           Regents of the University of California,
+ *                           Arizona Board of Regents.
+ *
+ * This file is part of NLSR (Named-data Link State Routing).
+ * See AUTHORS.md for complete list of NLSR authors and contributors.
+ *
+ * NLSR is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * NLSR is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
+ * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+ * PURPOSE.  See the GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * NLSR, e.g., in COPYING.md file.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include "hello-protocol.hpp"
+#include "nlsr.hpp"
+#include "test-common.hpp"
+
+namespace nlsr {
+namespace test {
+
+class HelloProtocolFixture : public UnitTestTimeFixture
+{
+public:
+  HelloProtocolFixture()
+    : face(m_ioService, m_keyChain, {true, true})
+    , conf(face, m_keyChain)
+    , confProcessor(conf)
+    , adjList(conf.getAdjacencyList())
+    , nlsr(face, m_keyChain, conf)
+    , helloProtocol(nlsr.m_helloProtocol)
+  {
+    ndn::FaceUri faceUri("udp4://10.0.0.1:6363");
+    Adjacent adj1(ACTIVE_NEIGHBOR, faceUri, 10, Adjacent::STATUS_ACTIVE, 0, 300);
+    adjList.insert(adj1);
+  }
+
+  int
+  checkHelloInterests(ndn::Name name)
+  {
+    int sent = 0;
+    for (const auto& i : face.sentInterests) {
+      if (name == i.getName().getPrefix(4)) {
+        sent++;
+      }
+    }
+    return sent;
+  }
+
+  void
+  checkHelloInterestTimeout()
+  {
+    helloProtocol.sendHelloInterest(ndn::Name(ACTIVE_NEIGHBOR));
+    this->advanceClocks(10_ms);
+    BOOST_CHECK_EQUAL(checkHelloInterests(ACTIVE_NEIGHBOR), 1);
+    this->advanceClocks(4_s);
+    BOOST_CHECK_EQUAL(checkHelloInterests(ACTIVE_NEIGHBOR), 2);
+    this->advanceClocks(4_s);
+    BOOST_CHECK_EQUAL(checkHelloInterests(ACTIVE_NEIGHBOR), 3);
+    if (conf.getHyperbolicState() == HYPERBOLIC_STATE_ON) {
+      BOOST_CHECK_EQUAL(nlsr.m_routingTable.m_isRouteCalculationScheduled, false);
+    }
+    else {
+      BOOST_CHECK_EQUAL(nlsr.m_lsdb.m_isBuildAdjLsaSheduled, false);
+    }
+    BOOST_CHECK_EQUAL(adjList.findAdjacent(ndn::Name(ACTIVE_NEIGHBOR))->getStatus(),
+                      Adjacent::STATUS_ACTIVE);
+
+    this->advanceClocks(4_s);
+    BOOST_CHECK_EQUAL(checkHelloInterests(ACTIVE_NEIGHBOR), 3);
+    if (conf.getHyperbolicState() == HYPERBOLIC_STATE_ON) {
+      BOOST_CHECK_EQUAL(nlsr.m_routingTable.m_isRouteCalculationScheduled, true);
+    }
+    else {
+      BOOST_CHECK_EQUAL(nlsr.m_lsdb.m_isBuildAdjLsaSheduled, true);
+    }
+    BOOST_CHECK_EQUAL(adjList.findAdjacent(ndn::Name(ACTIVE_NEIGHBOR))->getStatus(),
+                      Adjacent::STATUS_INACTIVE);
+  }
+
+public:
+  ndn::util::DummyClientFace face;
+  ConfParameter conf;
+  DummyConfFileProcessor confProcessor;
+  AdjacencyList& adjList;
+  Nlsr nlsr;
+  HelloProtocol& helloProtocol;
+  const std::string ACTIVE_NEIGHBOR = "/ndn/site/%C1.Router/router-active";
+};
+
+BOOST_FIXTURE_TEST_SUITE(HelloProtocol, HelloProtocolFixture)
+
+BOOST_AUTO_TEST_CASE(Basic)
+{
+  this->advanceClocks(10_s);
+  checkPrefixRegistered(face, "/ndn/site/%C1.Router/this-router/nlsr/INFO");
+  face.sentInterests.clear();
+}
+
+BOOST_AUTO_TEST_CASE(HelloInterestTimeoutLS) // #5139
+{
+  checkHelloInterestTimeout();
+}
+
+BOOST_AUTO_TEST_CASE(HelloInterestTimeoutHR) // #5139
+{
+  conf.setHyperbolicState(HYPERBOLIC_STATE_ON);
+  checkHelloInterestTimeout();
+}
+
+BOOST_AUTO_TEST_SUITE_END()
+
+} // namespace test
+} // namespace nlsr
\ No newline at end of file