Project

General

Profile

Actions

Task #2715

closed

NextHopList sorting order depends on insertion order

Added by Vince Lehman over 9 years ago. Updated over 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

Also available in: Atom PDF