Rate-limiting samples for ETX computation in computer networks

Patent metadata

Field	Value
Publication number	US-9577915-B2
Application number	US-201414567370-A
Country	US
Kind code	B2
Filing date	Dec 11, 2014
Priority date	Nov 7, 2014
Publication date	Feb 21, 2017
Grant date	Feb 21, 2017

Abstract

In one embodiment, a device in a network obtains information regarding a transmission between the device and a neighbor of the device in the network. The device determines whether to use the information regarding the transmission to update an expected transmission count associated with the neighbor based on a rate of samples used to compute expected transmission counts. The device updates the expected transmission count, in response to determining that the information regarding the transmission should be used to update the expected transmission count. The device selects a routing path in the network based in part on the updated expected transmission count associated with the neighbor.

First claim

What is claimed is:

1. A method comprising:
obtaining, by a device in a network, information regarding a transmission between the device and a neighbor of the device in the network;
determining, by the device, whether to use the information regarding the transmission to update an expected transmission count associated with the neighbor based on a rate of samples used to compute expected transmission counts;
adjusting, by the device, the rate of samples used to compute expected transmission counts based on a quantity of samples associated with the neighbor that were previously used to compute expected transmission counts;
updating, by the device, the expected transmission count, in response to determining that the information regarding the transmission should be used to update the expected transmission count; and
selecting, by the device, a routing path in the network based in part on the updated expected transmission count associated with the neighbor.

2. The method as in claim 1 , wherein determining whether to use the information regarding the transmission to update the expected transmission count comprises:
determining, by the device, that the rate of samples used to compute expected transmission counts exceeds threshold value; and
determining, by the device, not to use the information regarding the transmission to update the expected transmission count, in response to determining that the rate of samples used to compute expected transmission counts exceeds the threshold value.

3. The method as in claim 1 , further comprising:
determining, by the device, that the information regarding the transmission should not be used to update the expected transmission count based on the transmission occurring within a threshold amount of time after a transmission that was used to compute the expected transmission count.

4. The method as in claim 1 , further comprising:
using, by the device, a token bucket to control the rate of samples used to compute expected transmission counts.

5. The method as in claim 1 , further comprising:
switching, by the device, to a different channel used by the device to communicate with the neighbor; and
resetting, by the device, the rate of samples used to compute expected transmission counts, in response to switching to the different channel.

6. The method as in claim 1 , further comprising:
detecting, by the device, a change in activity on a channel used by the device to communicate with the neighbor, wherein the device determines whether to use the information regarding the transmission to update the expected transmission count based in part on the detected change in the activity on the channel.

7. The method as in claim 6 , wherein detecting the change in activity on the channel comprises:
determining, by the device, a degree of correlation between the activity that occurred on the channel and a transmission failure between the device and the neighbor, wherein the device determines not to use the transmission failure to update the expected transmission count when the activity that occurred on the channel and the transmission failure are correlated.

8. The method as in claim 1 , further comprising:
providing, by the device, the rate of samples used to compute the expected transmission count to a second device in the network;
receiving, at the device, an instruction from the second device to adjust the rate of samples; and
adjusting, by the device, the rate of samples used to compute the expected transmission count, in response to receiving the instruction from the second device.

9. The method as in claim 1 , wherein the information regarding the transmission comprises at least one of: an indication as to whether or not the transmission was acknowledged by the neighbor, an indication that the transmission is a retransmission, or an indication of the number of retransmission attempts made to send the transmission.

10. A method comprising:
receiving, at a first device in a network, data indicative of an estimated transmission count (ETX) strategy used by a second device in the network to compute ETX metrics;
determining, by the first device, whether the ETX strategy used by the second device should be adjusted; and
causing, by the first device, the second device to adjust the ETX strategy, in response to a determination that the ETX strategy used by the second device should be adjusted, wherein adjusting includes adjusting the rate of samples used to compute the ETX metrics based on a quantity of samples associated with the second device that were previously used to compute the ETX metrics.

11. The method as in claim 10 , wherein determining whether the ETX strategy used by the second device should be adjusted comprises:
monitoring, by the first device, routing topology changes in the network associated with the second device; and
determining, by the first device, whether the routing topology changes within a specific time period exceed a threshold amount.

12. The method as in claim 10 , wherein causing the second device to adjust the ETX strategy comprises:
providing, by the first device, a new ETX strategy to the second device.

13. An apparatus, comprising:
one or more network interfaces to communicate with a network;
a processor coupled to the one or more network interfaces and configured to execute a process; and
a memory configured to store the process executable by the processor, the process when executed operable to:
obtain information regarding a transmission between the apparatus and a neighbor of the apparatus in the network;
determine whether to use the information regarding the transmission to update an expected transmission count associated with the neighbor based on a rate of samples used to compute expected transmission counts;
adjust the rate of samples used to compute expected transmission counts based on a quantity of samples associated with the neighbor that were previously used to compute expected transmission counts;
update the expected transmission count, in response to determining that the information regarding the transmission should be used to update the expected transmission count; and
select a routing path in the network based in part on the updated expected transmission count associated with the neighbor.

14. The apparatus as in claim 13 , wherein whether to use the information regarding the transmission to update the expected transmission count is determined by:
determining that the rate of samples used to compute expected transmission counts exceeds threshold value; and
determining not to use the information regarding the transmission to update the expected transmission count, in response to determining that the rate of samples used to compute expected transmission counts exceeds the threshold value.

15. The apparatus as in claim 13 , wherein the process when executed is further operable to:
determine that the information regarding the transmission should not be used to update the expected transmission count based on the transmission occurring within a threshold amount of time after a transmission that was used to compute the expected transmission count.

16. The apparatus as in claim 13 , wherein the process when executed is further operable to:
use a token bucket to control the rate of samples used to compute expected transmission counts.

17. The apparatus as in claim 13 , wherein the process when executed is further operable to:
switch to a different channel used by the apparatus to communicate with the neighbor; and
reset the rate of samples used to compute expected tr

Assignees

• Cisco Tech Inc

Inventors

• Hui Jonathan W
• Vasseur Jean-Philippe
• Hong Wei

Classifications

• H04L45/12 Primary

  Shortest path evaluation · CPC title

• H04W40/125

  using a measured number of retransmissions as a link metric · CPC title