STATIC ADDRESSING OF DEVICES IN A DYNAMICALLY ROUTED NETWORK

• US 20100150059A1
• Filed: 12/15/2008
• Published: 06/17/2010
• Est. Priority Date: 12/15/2008
• Status: Active Grant

• Current Assignee: Itron Networked Solutions, Inc. (Itron, Inc.)
• Original Assignee: Silver Spring Networks, Inc. (Itron, Inc.)
• Inventors: Van Greunen, Jana, Rathi, Prashant, Hughes, Sterling
• Granted Patent: US 8,213,357 B2
• Time in Patent Office: Days
• US Class Current: 370/328
• CPC Class Codes: H04W 40/242 aging of topology database entries
• CPC Class Codes: H04W 40/248 Connectivity information update
• CPC Class Codes: H04W 40/28 for reactive routing

Abstract

A method of routing in a network includes dividing a time corresponding to a predetermined maximum registration age of a first node registered with a second node into a number of first time intervals and second time intervals. The first time intervals each have a predetermined duration and the second time intervals each have a duration greater than the predetermined duration of the first time intervals. Each of the first and second time intervals are assigned a metric designating a cost associated with a path between the first node and the second node. The metric increases in value for each of the first and second time intervals as registration age increases. The second node sends a message including the metric associated with the time interval during which it is transmitted.

Claims

1. A method of routing in a network, comprising:

dividing a period of time, corresponding to registration of a first node with a second node, into a sequence of time intervals, wherein a time interval at the beginning said period of time has a duration that is shorter than a time interval that is later in said period of time;

assigning to each of said time intervals a metric designating a cost associated with a communications path between the first node and the second node, wherein the designated cost increases in value for successive intervals of time in said sequence; and

broadcasting, by the second node, at least one message during each of said time intervals, said message containing the metric associated with time interval during which the message is broadcast.

2. The method of claim 1, wherein said period of time is divided into a number n of first time increments at the beginning of said sequence and a number x of second time intervals at the end of said sequence, where n+x is equal to the total number, z, of intervals in said sequence, and wherein the first time intervals each have a predetermined duration and the second time increments each have a duration greater than the predetermined time interval of the first time increments n.

3. The method of claim 2, wherein each of the first time intervals has the same duration.

4. The method of claim 3, wherein each of the second time intervals has the same duration.

5. The method of claim 4, wherein the second time intervals each have a duration determined by ((said period of time)−

(n*predetermined time))/(z−

n).

6. The method of claim 1, wherein the durations of the time intervals increase successively over the sequence of time intervals.

7. The method of claim 6, wherein the durations of the time intervals increase in a non-linear manner.

8. The method of claim 1, wherein the first node is an Ethernet bridge to a utility device.

9. The method of claim 1, wherein the first node is a node in an ad-hoc utility wireless network

10. The method of claim 1, wherein the second node is an Access Point of an ad-hoc utility wireless network.

11. The method of claim 1, wherein the second node is a node in an ad-hoc utility wireless network

12. The method of claim 1, wherein the message containing the metric is a routing advertisement.

13. The method of claim 12, wherein the routing advertisement conforms to a distance-vector routing protocol.

14. The method of claim 13, wherein the distance-vector routing protocol is a Routing Information Protocol.

15. The method of claim 1, wherein the metric is a hop count.

16. The method of claim 1, wherein the network is a frequency-hopping spread spectrum network.

17. The method of claim 1, wherein said first node is associated with a device having a static IP address.

18. The method of claim 17, wherein said network employs dynamic address assignment to registered nodes.

19. A node in a communications network with which other nodes register to provide a communications path to a destination, said node including a transmitting unit that broadcasts advertisements via said network that it can provide a path to an other node that is registered with it, said advertisements comprising messages that are transmitted during a sequence of time intervals over a period of time while the other node is registered, wherein a time interval earlier in said sequence has a duration that is shorter than a time interval that is later in said sequence, each said message containing a metric designating a cost associated with the path to the other node, and wherein the designated cost increases in value for successive intervals of time in said sequence.

20. The node of claim 19, wherein the durations of said time intervals conform to a step function, wherein each time interval in a first group of time intervals has a first duration, and time intervals in a second group of time intervals, which are later in said sequence, have a duration that is longer than said first duration.

21. The node of claim 19, wherein the durations of the time intervals increase successively over the sequence of time intervals.

22. The node of claim 21, wherein the durations of the time intervals increase in a non-linear manner.

23. The node of claim 19, wherein said node is an Access Point in an ad-hoc wireless utility network.

24. The node of claim 19, wherein said node is a node in an ad-hoc wireless utility network.

25. The node of claim 19, wherein the metric is a hop count.

26. The node of claim 19, wherein the network is a frequency-hopping spread spectrum network.

27. The node of claim 19, wherein said other node is associated with a device having a static IP address.

28. The node of claim 27, wherein said network employs dynamic address assignment to registered nodes.

29. The node of claim 19, wherein the durations of the time intervals increase monotonically between the beginning and end of said sequence of time intervals.

30. In a network in which a first node can register with two or more other nodes that provide access to and from said first node, a method comprising the following steps:

at each other node with which the first node is registered, broadcasting advertisements that said other node can provide a path to the first node, said advertisements comprising messages that are transmitted during a sequence of time intervals over a period of time while the first node is registered, wherein a time interval earlier in said sequence has a duration that is shorter than a time interval that is later in said sequence, each said message containing a metric designating a cost associated with the path to the other node, and wherein the designated cost increases in value for successive intervals of time in said sequence;

upon receiving an advertisement at one of said other nodes that another node can provide a path to said first node, determining whether the metric contained in the received advertisement designates a lower cost than the metric being broadcast by said one node for its path to the first node; and

terminating the broadcast of the advertisements from said one node if the metric contained in the received advertisement designates a lower cost than the metric being broadcast by said one node.

31. The method of claim 30, wherein said first node comprises an endpoint in the network, and said other nodes comprise access points in the network.

32. The method of claim 30, wherein said first node has a static address, and said network employs dynamic addressing to access nodes in the network.

33. In a network in which a first node can register with two or more other nodes that provide access to and from said first node, a method comprising the following steps:

at each other node with which the first node is registered, broadcasting advertisements that said other node can provide a path to the first node, said advertisements comprising messages that are transmitted during a sequence of time intervals over a period of time while the first node is registered, wherein a time interval earlier in said sequence has a duration that is shorter than a time interval that is later in said sequence, each said message containing a metric designating a cost associated with the path to the other node, and wherein the designated cost increases in value for successive intervals of time in said sequence;

receiving said advertisements from two or more other nodes at a transmitting node, and selecting one of said other nodes based upon the respective metrics contained in the received advertisements; and

transmitting a message to the first node from the transmitting node, via the selected one of said other nodes.

34. The method of claim 33, wherein said first node comprises an endpoint in the network, and said other nodes comprise access points in the network.

35. The method of claim 33, wherein said first node has a static address, and said network employs dynamic addressing to access nodes in the network.