Project

General

Profile

Task #4978

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

Added by Saurab Dulal 24 days ago. Updated 23 days ago.

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

10%

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

History

#1 Updated by Saurab Dulal 24 days 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

#2 Updated by Saurab Dulal 24 days 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

#3 Updated by Saurab Dulal 24 days 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.

#4 Updated by Saurab Dulal 23 days 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.

Also available in: Atom PDF