Feature #3566

Updated by Vince Lehman over 4 years ago

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` and `Group 3` by SRTT and cost, respectively; next hops in `Group 3` have lower priority than next hops in `Group 1`. 
 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)) 

 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(2) = (2 * (3 + 1 - 3))/(3 * (3 + 1)) = 4/12 = 16.6% 

 ## Implementation 
 An experimental implementation of the above described strategy can be found at