Adaptive Forwarding Strategy for hyperbolic routing
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:
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:
Group 1is not empty, pick the next hop with the lowest SRTT
- Otherwise, if
Group 2is not empty, pick the next hop with the lowest cost
- Otherwise, pick the lowest cost next hop from
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:
- Pick the next hop with the lowest routing cost from
- Otherwise, sort the next hops in
Group 1by SRTT and
Group 3by cost; priority
- 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(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
On an incoming Interest if the strategy cannot forward to any next hops, send a NO_ROUTE NACK.
- Consumer retransmissions
- Router retransmissions - this strategy does not perform router retransmissions
An experimental implementation of the above described strategy can be found at https://github.com/vslehman/NFD/tree/asf/daemon/fw/asf.