Project

General

Profile

Actions

Task #4978

closed

Link-state routing table calculation via a neighbor fails when the cost to that neighbor is zero

Added by Saurab Dulal over 4 years ago. Updated over 4 years ago.

Status:
Closed
Priority:
Normal
Assignee:
Target version:
-
Start date:
07/31/2019
Due date:
% Done:

100%

Estimated time:

Description

Currently, if the neighbor's cost is equal to zero the routing table calculation fails and no routes are registered to fib. Even though cost zero is not a practical scenario, the link-state routing-table calculation should not fail.

Example:

Triangular topology with the cost from each node to another is equal to zero.

A ----> B, cost 0
A ----> C, cost 0
B ----> C, cost 0

Actions #1

Updated by Saurab Dulal over 4 years ago

  • Subject changed from Link-state routing table calculation fails when neighbor cost is zero to Link-state routing table calculation fails via a neighbor when the llink-cost to that neighbor is zero
Actions #2

Updated by Saurab Dulal over 4 years ago

  • Subject changed from Link-state routing table calculation fails via a neighbor when the llink-cost to that neighbor is zero to Link-state routing table calculation via a neighbor fails when the cost to that neighbor is zero
Actions #3

Updated by Saurab Dulal over 4 years ago

In routing-table-calculator, a variable vNoLink (https://github.com/named-data/NLSR/blob/master/src/route/routing-table-calculator.hpp#L122) stores a number of links from a node-neighbor/s that have cost greater than 0.

for (size_t i = 0; i < m_nRouters; i++) { //https://github.com/named-data/NLSR/blob/master/src/route/routing-table-calculator.cpp#L161
    if (adjMatrix[sRouter][i] > 0) { //checking if cost is > 0 from a node to its neighbor
      noLink++; //this is used to set vNoLink.
    }
  }

The same > 0 assumption is made when getting sparse links from AdjMatrix.

  for (size_t i = 0; i < m_nRouters; i++) { //https://github.com/named-data/NLSR/blob/master/src/route/routing-table-calculator.cpp#L174
    if (adjMatrix[source][i] > 0) { // checking if cost is > 0 from a node to its neighbor
      links[j] = i;
      linkCosts[j] = adjMatrix[source][i];
      j++;
    }

The "vNoLink" is used in other sections of the code as well, therefore the same assumption is propagated elsewhere.

In LS:doDijkstraPathCalculation, (https://github.com/named-data/NLSR/blob/master/src/route/routing-table-calculator.hpp#L239), a node is considered accessible if the cost to that node is greater than zero and for the rest of the nodes the cost is set to zero in the adjacent matrix. Now, this fundamentally violates a use-case when the actual cost from a node to its neighbor is supplied zero by the user/operator. In such case, code won't be able to figure out the diff between real cost and the one set considering inaccessible.

For more clarity,

let's Assume a link-cost between A---->C = 0, and say, B is not reachable from A. The following "if condition" will result false and both (B and C) won't be considered as a neighbor.

if (adjMatrix[u][v] > 0) //will fail to incorporate our use-case, (routing-table-calculator.hpp#L293)

changing ">" sign in the above "if" to >= won't work, as the code will falsely consider both of them as a neighbor.

Actions #4

Updated by Saurab Dulal over 4 years ago

Additionally,

The current NLSR code cannot handle negative value properly.

https://github.com/named-data/NLSR/blob/master/src/adjacent.hpp#L83

  uint64_t
  getLinkCost() const
  {
    uint64_t linkCost = static_cast<uint64_t>(ceil(m_linkCost));
    return linkCost;
  }

this function will return garbage for negative link cost as uint64_t is an unsigned integer.

Actions #5

Updated by Junxiao Shi over 4 years ago

Instead of intensive code changes, why not automatically interpret configured "0" as "1"? It's "not practical" so a minimal change should be sufficient.

Actions #6

Updated by Saurab Dulal over 4 years ago

Junxiao Shi wrote:

Instead of intensive code changes, why not automatically interpret configured "0" as "1"? It's "not practical" so a minimal change should be sufficient.

I don't have a better explanation besides what's presented above and on the gerrit. Interpreting "0" as "1" might affect other links which genuinely have link cost 1.

I am wondering why NFD accepts 0 cost links?

Actions #7

Updated by Saurab Dulal over 4 years ago

  • Status changed from In Progress to Closed
  • % Done changed from 10 to 100
Actions

Also available in: Atom PDF