Method and system for routing information in a network

• US 9,641,426 B2
• Filed: 12/04/2013
• Issued: 05/02/2017
• Est. Priority Date: 02/23/2011
• Status: Active Grant

• Current Assignee: Hp Ventures A/S
• Original Assignee: Hp Ventures A/S
• Inventors: Jaeger, Morten Gravild Bjerregaard
• Primary Examiner(s): CATTUNGAL, AJAY P
• Application Number:
  US14/096,937
• Publication Number:
  US 20140092911A1
• Time in Patent Office: 1,245 Days
• CPC Class Codes: H04L 45/026 Details of "hello" or keep-alive messages
• CPC Class Codes: H04L 45/124 using a combination of metrics
• CPC Class Codes: H04W 40/248 Connectivity information update

Abstract

A method and system for determining an optimal route from a node to a given sink node in a network is described. Sink node periodically transmits routing information containing an indicator of recency. This indicator of recency is periodically updated. Routing information is received by a plurality of nodes in the network. Each node receiving routing information compares the indicator of recency contained in the routing information with an indicator of recency stored at the node to determine whether the received routing information is more recent than the stored routing information. An optimal route to the sink node is determined based on this comparison. Each node also periodically transmits routing information based on stored routing information to other nodes.

Claims

1. A method of determining a route in a network, the method comprising:

sending routing information from a sink node at a periodic interval, the routing information comprising an indicator of recency and allowing identification of the sink node;

sending routing information from each of a plurality of nodes at a periodic interval, the routing information being based on stored routing information at each of the plurality of nodes;

repeatedly receiving routing information at any node able to receive routing information;

determining at each node receiving routing information whether the received routing information is more recent than stored routing information at the node; and

if the received routing information at a node is more recent than the stored routing information, storing the received routing information at the node;

wherein the indicator of recency belongs to a set of indicators of recency of a limited size; and

wherein the limited size is determined based on the length of the longest chordless cycle of the topology of the network.

2. The method of claim 1, wherein the routing information sent from the plurality of nodes is free of a hop count.

3. The method of claim 1, wherein the stored routing information is free of a hop count.

4. The method of claim 3, wherein determining whether the received routing information is more recent than stored routing information at the node comprises comparing an indicator of recency of the received routing information with an indicator of recency of the stored routing information.

5. The method of claim 1, wherein the periodic interval for sending routing information from a sink node and the periodic interval for sending routing information from each of the plurality of nodes are of approximately equal duration.

6. The method of claim 1, wherein sending routing information from each of the plurality of nodes comprises sending at a first periodic interval routing information comprising a first group identifying field and one or more indicators of recency corresponding to a first group of one or more sink nodes and sending at a second periodic interval routing information comprising a second group identifying field and one or more indicators of recency corresponding to a second group of one or more sink nodes, wherein each of the one or more sink nodes of the first group are identified based on the first group identifying field and the position of each of the one or more indicators of recency within the routing information sent at the first periodic interval and each of the one or more sink nodes of the second group are identified based on the second group identifying field and the position of each of the one or more indicators of recency within the routing information sent at the second periodic interval.

7. The method of claim 1, wherein sending routing information from the sink node comprises sending at a first periodic interval routing information comprising a first group identifying field and one or more indicators of recency corresponding to a first group of one or more sink nodes and sending at a second periodic interval routing information comprising a second group identifying field and one or more indicators of recency corresponding to a second group of one or more sink nodes, wherein each of the one or more sink nodes of the first group are identified based on the first group identifying field and the position of each of the one or more indicators of recency within the routing information sent at the first periodic interval and each of the one or more sink nodes of the second group are identified based on the second group identifying field and the position of each of the one or more indicators of recency within the routing information sent at the second periodic interval.

8. The method of claim 1, wherein the limited size is further determined based on a probability that a travel time over a path of the network being greater than an average travel time over the path.

9. The method of claim 8, wherein the probability that a travel time over a path of the network being greater than an average travel time over the path is based on the longest travel time over the path of the network.

10. The method of claim 1, wherein the indicator of recency is a race number, wherein the race number sent at a subsequent periodic interval is updated, and wherein updating of the race number is cyclical.

11. The method of claim 10, wherein determining whether the received routing information is more recent than stored routing information at the node comprises comparing the race number (A) of the received routing information with the race number (B) of the stored routing information, the comparing comprising:

X=A−

B;

if (A<

B), then X =X+N;

if (X>

L), then race number B is more recent, else race number A is more recent or race number A and race number B are equally recent;

wherein N is the number of race numbers in one cycle and L is the length of the longest chordless cycle on the topology of the network given by L=(N−

l)/2.

12. A non-transitory computer-readable medium upon which a plurality of instructions are stored, the instructions for performing the steps of the method as claimed in claim 1.

13. The method of claim 1, wherein the receiving routing information at any node further comprises identifying a neighbor node from which the routing information was sent.

14. A system for establishing a route in a network, the system comprising:

a plurality of nodes, each node comprising;

a node memory; and

a node processor, the node processor configured to;

send routing information at a periodic interval, the routing information being based on routing information stored in the node memory;

receive routing information;

determine whether the received routing information is more recent than the stored routing information at the node; and

if the received routing information is more recent than stored routing information, to store the received routing information in the node memory;

wherein at least one of the nodes is a sink node, the processor of the sink node further configured to;

send routing information at a periodic interval, the routing information comprising an indicator of recency and allowing identification of the sink node;

wherein the indicator of recency belongs to a set of indicators of recency of a limited size; and

wherein the limited size is determined based on the length of the longest chordless cycle of the topology of the network.

15. The system of claim 14, wherein the routing information sent from the plurality of nodes is free of a hop count.

16. The system of claim 14, wherein the stored routing information is free of a hop count.

17. The system of claim 16, wherein determining whether the received routing information is more recent than stored routing information at the node comprises comparing an indicator of recency of the received routing information with an indicator of recency of the stored routing information.

18. The system of claim 14, wherein the periodic interval for sending routing information from the sink node processor and the periodic interval for sending routing information from the node processor are of approximately equal duration.

19. The system of claim 14, wherein sending routing information from the node processor comprises sending at a first periodic interval routing information comprising a first group identifying field and one or more indicators of recency corresponding to a first group of one or more sink nodes and sending at a second periodic interval routing information comprising a second group identifying field and one or more indicators of recency corresponding to a second group of one or more sink nodes, wherein each of the one or more sink nodes of the first group are identified based on the first group identifying field and the position of each of the one or more indicators of recency within the routing information sent at the first periodic interval and each of the one or more sink nodes of the second group are identified based on the second group identifying field and the position of each of the one or more indicators of recency within the routing information sent at the second periodic interval.

20. The system of claim 14, wherein sending routing information from the sink processor comprises sending at a first periodic interval routing information comprising a first group identifying field and one or more indicators of recency corresponding to a first group of one or more sink nodes and sending at a second periodic interval routing information comprising a second group identifying field and one or more indicators of recency corresponding to a second group of one or more sink nodes, wherein each of the one or more sink nodes of the first group are identified based on the first group identifying field and the position of each of the one or more indicators of recency within the routing information sent at the first periodic interval and each of the one or more sink nodes of the second group are identified based on the second group identifying field and the position of each of the one or more indicators of recency within the routing information sent at the second periodic interval.

21. The system of claim 14, wherein the limited size is further determined based on a probability that a travel time over a path of the network being greater than an average travel time over the path.

22. The system of claim 21, wherein the probability that a travel time over a path of the network being greater than an average travel time over the path is based on the longest travel time over the path of the network.

23. The system of claim 14, wherein the indicator of recency is a race number, wherein the race number sent at a subsequent periodic interval is updated, and wherein updating of the race number is cyclical.

24. The system of claim 23, wherein determining whether the received routing information is more recent than stored routing information at the node comprises comparing the race number (A) of the received routing information with the race number (B) of the stored routing information, the comparing comprising:

X=A−

B;

if (A<

B), then X=X+N;

if (X>

L), then race number B is more recent, else race number A is more recent or race number A and race number B are equally recent;

wherein N is the number of race numbers in one cycle and L is the length of the longest chordless cycle on the topology of the network given by L=(N−

l)/2.

25. The system of claim 14, wherein the node processor of each node of the plurality of nodes is further configured to identify a neighbor node from which the received routing information was sent.

26. A method of determining a route in a network, the method comprising:

sending routing information from a sink node at a periodic interval, the routing information comprising an indicator of recency and allowing identification of the sink node;

sending routing information from each of a plurality of nodes at a periodic interval, the routing information being based on stored routing information at each of the plurality of nodes, the stored routing information comprising an indicator of recency;

repeatedly receiving routing information at any node able to receive routing information;

determining at each node receiving routing information whether the received routing information is more recent than stored routing information at the node by comparing the indicator of recency of the received routing information with the indicator of recency of the stored routing information; and

only if the received routing information at a node is more recent than the stored routing information, storing the received routing information at the node.

27. A system for establishing a route in a network, the system comprising:

a plurality of nodes, each node comprising;

a node memory; and

a node processor, the node processor configured to;

send routing information at a periodic interval, the routing information being based on routing information stored in the node memory, each of the routing information sent and the routing information stored comprising an indicator of recency;

receive routing information;

determine whether the received routing information is more recent than the stored routing information at the node by comparing the indicator of recency of the received routing information with the indicator of recency of the stored routing information; and

only if the received routing information is more recent than stored routing information, to store the received routing information in the node memory;

wherein at least one the nodes is a sink node, the processor of the sink node further configured to;

send routing information at a periodic interval, the routing information comprising an indicator of recency and allowing identification of the sink node.