Project

General

Profile

Feature #3566

Adaptive Forwarding Strategy for hyperbolic routing

Added by Junxiao Shi over 4 years ago. Updated about 4 years ago.

Status:
Closed
Priority:
Normal
Assignee:
Category:
Forwarding
Target version:
Start date:
Due date:
% Done:

100%

Estimated time:
18.00 h

Description

Current forwarding strategies in NFD focus on being able to retrieve content, but may not always find the lowest delay path. To facilitate optimal forwarding in HR and address drawbacks (embedding issues, network dynamics, etc.), a strategy which bases its forwarding decisions on RTT measurements and also periodically probes alternative next hops is crucial to HR’s deployment.

The design of the adaptive forwarding strategy is composed of two components:

SRTT-based Forwarding

When a Data packet is received, the RTT is recorded (time between Interest forwarded and Data received). This RTT is used to compute an SRTT; an SRTT measurement is calculated and associated with the FIB entry which the Interest matched.

When an interest arrives, all available next hops from the FibEntry are divided into three distinct groups.

  • Group 1: Next hops with SRTT values
  • Group 2: Next hops that do not have measurements
  • Group 3: Next hops that timed-out on the previous Interest

The strategy will then try to pick a next hop in the following way:

  1. If Group 1 is not empty, pick the next hop with the lowest SRTT
  2. Otherwise, if Group 2 is not empty, pick the next hop with the lowest cost
  3. Otherwise, pick the lowest cost next hop from Group 3

SRTT-based Probing

The first probe for a namespace is scheduled after the first Interest which matches the FIB entry arrives. The first probe is scheduled at a random interval from [0, 5] seconds. After the initial probe, probing is scheduled to occur periodically every 60 seconds.

If probing is due but no Interests arrive under that namespace, probing will not occur until a matching Interest arrives. Probes use the same name as the triggering Interest but use a different nonce. A different nonce is used to ensure that if the probed path is able to reach the Data, the Data will be returned on the probed path as well as the primary path.

The steps for probing are defined as follows:

  1. Pick the next hop with the lowest routing cost from Group 2
  2. Otherwise, sort the next hops in Group 1 by SRTT and Group 3 by cost; priority Group 1 > Group 3
  3. Assign a probing probability to each next hop and probabilistically select a next hop for probing

The probing probability of the next hop with rank i = 1, 2, …, N in the sorted list is assigned P(i) = (2 * (N + 1 - i))/(N * (N + 1))

e.g.)
With sorted NextHops (rank: 1, FaceId=128, rank: 2, FaceId=256, rank:3, FaceId=512)

  • NextHop with FaceId=128 will be assigned the probability P(1) = (2 * (3 + 1 - 1))/(3 * (3 + 1)) = 6/12 = 50%
  • NextHop with FaceId=256 will be assigned the probability P(2) = (2 * (3 + 1 - 2))/(3 * (3 + 1)) = 4/12 = 33.3%
  • NextHop with FaceId=256 will be assigned the probability P(3) = (2 * (3 + 1 - 3))/(3 * (3 + 1)) = 2/12 = 16.6%

Handling Incoming NACKs

All received NACKs are handled by setting the timeout flag in the corresponding face's measurements

Outgoing NACKs

On an incoming Interest if the strategy cannot forward to any next hops, send a NO_ROUTE NACK.

Retransmissions

  • Consumer retransmissions
    • Follow the same suppressions logic as implemented in best route strategy v4 (#1913)
    • Follow similar forwarding logic for retransmitted Interest as in best route strategy v4 (#1871); On retransmission, pick best next hop from sorted groups
  • Router retransmissions - this strategy does not perform router retransmissions

Implementation

An experimental implementation of the above described strategy can be found at https://github.com/vslehman/NFD/tree/asf/daemon/fw/asf.


Files

hr-adaptive-forwarding-strategy.pdf (569 KB) hr-adaptive-forwarding-strategy.pdf Vince Lehman, 04/08/2016 08:30 AM
asf-specification.pdf (199 KB) asf-specification.pdf Vince Lehman, 07/01/2016 01:39 PM

Related issues

Has duplicate NFD - Feature #3813: Forwarding strategy for using multiple interfaces in generic deploymentsDuplicate10/16/2016

Actions
Has duplicate NFD - Task #1901: Strategy for backbone routerDuplicateJunxiao Shi

Actions

Also available in: Atom PDF