Fast-tracking approach for building routing topologies in fast-moving networks

• US 8,718,055 B2
• Filed: 01/25/2012
• Issued: 05/06/2014
• Est. Priority Date: 01/25/2012
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Vasseur, Jean-Philippe, Addepalli, Sateesh K., Sudhaakar, Raghuram S., Lee, Kevin C.
• Primary Examiner(s): Wu, Jianye
• Application Number:
  US13/358,361
• Publication Number:
  US 20130188513A1
• Time in Patent Office: 832 Days
• Field of Search: None
• US Class Current: 370/389
• CPC Class Codes: H04L 45/028 Dynamic adaptation of the update intervals, e.g. event-triggered updates
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 45/70 Routing based on monitoring results
• CPC Class Codes: H04W 40/20 based on geographic position or location
• CPC Class Codes: H04W 40/248 Connectivity information update

Abstract

In one embodiment, a local node in a communication network determines a set of its neighbor nodes, and determines a respective occurrence frequency at which each particular neighbor node is to be probed based on a rate of change in distance between the local node and the particular neighbor node. The local node may then probe each particular neighbor node according to the respective occurrence frequency to determine the rate of change in distance between the local node and each particular neighbor node, and one or more routing metrics for reaching each particular neighbor node. As such, the local node may select, based on the probing, a suitable preferred next-hop node of the set of neighbor nodes for a corresponding routing topology.

Claims

1. A method, comprising:

determining a set of neighbor nodes of a local node in a communication network;

determining a respective occurrence frequency at which each particular neighbor node is to be probed based on a rate of change in distance between the local node and the particular neighbor node;

probing each particular neighbor node according to the respective occurrence frequency to determine the rate of change in distance between the local node and each particular neighbor node, and one or more routing metrics for reaching each particular neighbor node; and

selecting, based on the probing, a suitable preferred next-hop node of the set of neighbor nodes for a corresponding routing topology.

2. The method as in claim 1, wherein the distance is based on at least one of either a signal strength or a physical distance between the local node and each particular neighbor node.

3. The method as in claim 2, further comprising:

determining that the selected preferred next-hop node is suitable based on the preferred next-hop node being within a threshold distance from the local node.

4. The method as in claim 1, further comprising:

determining that the selected preferred next-hop node is no longer suitable based on the preferred next-hop node no longer being within a threshold distance from the local node as detected by the probing; and

selecting, based on the probing, a suitable updated preferred next-hop node of the set of neighbor nodes for the corresponding routing topology.

5. The method as in claim 1, further comprising:

selecting, based on the probing, a suitable alternate next-hop node of the set of neighbor nodes for the corresponding routing topology;

determining that the selected alternate next-hop node is no longer suitable based on the alternate next-hop node no longer being within a threshold distance from the local node as detected by the probing; and

selecting, based on the probing, a suitable updated alternate next-hop node of the set of neighbor nodes for the corresponding routing topology.

6. The method as in claim 1, wherein the occurrence frequency increases when the rate of change in distance increases, and decreases when the rate of change in distance decreases.

7. The method as in claim 1, wherein probing determines one or more of:

a signal strength, a speed vector, an acceleration, a current location, and one or more routing metrics, each associated with each particular neighbor node.

8. The method as in claim 1, wherein probing utilizes layer-2 beacon messages.

9. The method as in claim 1, wherein the nodes in the communication network are selected from a group consisting of vehicles and mobile user devices.

10. The method as in claim 1, wherein routing metrics comprise a path cost.

11. The method as in claim 1, further comprising:

limiting the probing to neighbor nodes capable of being probed.

12. The method as in claim 1, wherein the selected preferred next-hop node is selected based on having the best set of routing metrics according to a directive of a routing protocol used to compute the corresponding routing topology.

13. The method as in claim 1, wherein probing further determines n-hop neighbor information, and wherein the selected preferred next-hop node is selected based on associated n-hop neighbor information via the preferred next-hop node.

14. The method as in claim 1, wherein determining the respective occurrence frequency at which each particular neighbor node is to be probed is based on:

c/((a*signal strength)+(b*relative position)),

where c is a constant, a and b are weight values, and relative position is a current location having motion physics applied thereto given a speed vector and acceleration of a corresponding particular node.

15. An apparatus, comprising:

one or more network interfaces to communicate in a communication network;

a processor coupled to the network interfaces and adapted to execute one or more processes; and

a memory configured to store a process executable by the processor, the process when executed operable to;

determine a set of neighbor nodes of the apparatus;

determine a respective occurrence frequency at which each particular neighbor node is to be probed based on a rate of change in distance between the apparatus and the particular neighbor node;

probe each particular neighbor node according to the respective occurrence frequency to determine the rate of change in distance between the apparatus and each particular neighbor node, and one or more routing metrics for reaching each particular neighbor node; and

select, based on the probing, a suitable preferred next-hop node of the set of neighbor nodes for a corresponding routing topology.

16. The apparatus as in claim 15, wherein the distance is based on at least one of either a signal strength or a physical distance between the local node and each particular neighbor node.

17. The apparatus as in claim 16, wherein the process when executed is further operable to:

determine that the selected preferred next-hop node is suitable based on the preferred next-hop node being within a threshold distance from the apparatus.

18. The apparatus as in claim 15, wherein the process when executed is further operable to:

determine that the selected preferred next-hop node is no longer suitable based on the preferred next-hop node no longer being within a threshold distance from the apparatus as detected by the probing; and

select, based on the probing, a suitable updated preferred next-hop node of the set of neighbor nodes for the corresponding routing topology.

19. The apparatus as in claim 15, wherein the process when executed is further operable to:

select, based on the probing, a suitable alternate next-hop node of the set of neighbor nodes for the corresponding routing topology;

determine that the selected alternate next-hop node is no longer suitable based on the alternate next-hop node no longer being within a threshold distance from the apparatus as detected by the probing; and

select, based on the probing, a suitable updated alternate next-hop node of the set of neighbor nodes for the corresponding routing topology.

20. The apparatus as in claim 15, wherein the occurrence frequency increases when the rate of change in distance increases, and decreases when the rate of change in distance decreases.

21. The apparatus as in claim 15, wherein probing determines one or more of:

a signal strength, a speed vector, an acceleration, a current location, and one or more routing metrics, each associated with each particular neighbor node.

22. The apparatus as in claim 15, wherein the process when executed to probe is further operable to:

utilize layer-2 beacon messages.

23. The apparatus as in claim 15, wherein the nodes in the communication network are selected from a group consisting of vehicles and mobile user devices.

24. A tangible, non-transitory, computer-readable media having software encoded thereon, the software when executed by a processor operable to:

determine a set of neighbor nodes of a local node in a communication network;

determine a respective occurrence frequency at which each particular neighbor node is to be probed based on a rate of change in distance between the local node and the particular neighbor node;

probe each particular neighbor node according to the respective occurrence frequency to determine the rate of change in distance between the local node and each particular neighbor node, and one or more routing metrics for reaching each particular neighbor node; and

select, based on the probing, a suitable preferred next-hop node of the set of neighbor nodes for a corresponding routing topology.