Project

General

Profile

Actions

Task #2715

closed

NextHopList sorting order depends on insertion order

Added by Vince Lehman almost 9 years ago. Updated almost 9 years ago.

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

100%

Estimated time:

Description

Currently, NextHopLists are sorted using the simple comparator:

return nh1.getRouteCost() < nh2.getRouteCost();

In cases where two next hops have the same cost, the order after sorting would depend on the next hop's insertion order.

Therefore, it is possible that different runs of NLSR will have different routes installed in the FIB.

For example, with max-faces-per-prefix set to 2:

Run 1:
------
FaceId 129 is added to the NextHopList first. After sorting, it will remain in front of FaceId 130.

Routing Table
/name nexthops={faceid=128 (cost=10), faceid=129 (cost=25), faceid=130 (cost=25)}

FIB
/name nexthops={faceid=128 (cost=10), faceid=129 (cost=25)}


Run 2:
------
FaceId 130 is added to the NextHopList first. After sorting, it will remain in front of FaceId 129.

Routing Table
/name nexthops={faceid=128 (cost=10), faceid=130 (cost=25), faceid=129 (cost=25)}

FIB
/name nexthops={faceid=128 (cost=10), faceid=130 (cost=25)}

Instead, in cases of two next hops with the same cost, the sorting comparator should break the tie.

Since next hops also have a connecting FaceUri string, a lexicographical comparison can be performed on the strings to break the tie:

if (nh1.getRouteCostAsAdjustedInteger() < nh2.getRouteCostAsAdjustedInteger()) {
  return true;
}
else if (nh1.getRouteCostAsAdjustedInteger() == nh2.getRouteCostAsAdjustedInteger()) {
  return nh1.getConnectingFaceUri() < nh2.getConnectingFaceUri();
}
else {
  return false;
}
Actions #1

Updated by Vince Lehman almost 9 years ago

  • Status changed from In Progress to Code review
  • % Done changed from 0 to 90
Actions #2

Updated by Vince Lehman almost 9 years ago

  • Status changed from Code review to Closed
  • % Done changed from 90 to 100
Actions

Also available in: Atom PDF