Feature #3566
Updated by Vince Lehman over 8 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 received a CONGESTION NACK on the previous Interest * `Group 4`: 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, if `Group 3` is not empty, pick the next hop with the lowest cost 4. Otherwise, pick the lowest cost next hop from `Group 3` 4` ## 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 SRTT, and `Group 3` and `Group 4` by cost; priority `Group 1` > `Group 3` > `Group 4` 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 * `CONGESTION` * Set flag in measurements to indicate that last Interest returned a CONGESTION NACK * This flag lowers both forwarding priority and probing probability * `DUPLICATE` * Design in progress * `NO_ROUTE` * Set 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.