LOAD MANAGEMENT IN WIRELESS MESH COMMUNICATIONS NETWORKS

• US 20090003214A1
• Filed: 06/27/2008
• Published: 01/01/2009
• Est. Priority Date: 06/15/2007
• Status: Active Grant

• Current Assignee: Itron Networked Solutions, Inc. (Itron, Inc.)
• Original Assignee: Silver Spring Networks, Inc. (Itron, Inc.)
• Inventors: van Greunen, Jana, Hughes, Sterling, San Filippo, William E. III, Vaswani, Raj, Flammer, George III
• Granted Patent: US 8,233,905 B2
• Time in Patent Office: Days
• US Class Current: 370/236
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/122 by minimising distances, e.g. by selecting a route with minimum of number of hops
• CPC Class Codes: H04L 45/124 using a combination of metrics
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/122 by diverting traffic away from congested entities
• CPC Class Codes: H04W 28/0289 Congestion control load shedding arrangements in network planning H04W16/08; performing reselection for handling the traffic H04W36/22; wireless traffic scheduling H04W72/12
• CPC Class Codes: H04W 28/10 Flow control between communication endpoints
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 40/08 based on transmission power
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 8/04 Registration at HLR or HSS [Home Subscriber Server]
• CPC Class Codes: H04W 80/045 involving different protocol versions, e.g. MIPv4 and MIPv6

Abstract

Methods and systems for providing a network and routing protocol for utility services are disclosed. A method includes discovering a utility network. Neighboring nodes are discovered and the node listens for advertised routes for networks from the neighbors. The node is then registered with one or more utility networks, receiving a unique address for each network registration. Each upstream node can independently make forwarding decisions on both upstream and downstream packets, i.e., choose the next hop according to the best information available to it. The node can sense transient link problems, outage problems and traffic characteristics. Information is used to find the best route out of and within each network. Each network node maintains multi-egress, multi-ingress network routing options both for itself and the node(s) associated with it. The node is capable of several route maintenance functions utilizing the basic routing protocol and algorithms.

Claims

1. A method of load management in a network, comprising:

sending, by a first node, a request packet to a second node;

receiving, by the second node, the request packet;

determining whether the second node has reached a limit of nodes, and in the event the determination is that the second node has reached the limit of nodes, increasing a value corresponding to a path cost;

sending the increased value corresponding to the path cost to other first nodes that the second node has determined as candidates to be dropped; and

sending an actual path cost to other first nodes.

2. The method of claim 1, wherein a request packet is sent at approximately the same rate as a routing advertisement period.

3. The method of claim 2, wherein the routing advertisement period is approximately twenty minutes.

4. The method of claim 1, wherein path cost updates from a node are included in the node'"'"'s regular routing update messages.

5. The method of claim 1, wherein the candidates that are selected to receive path cost increases are nodes that may have other second nodes for routing.

6. The method of claim 3, wherein the request packet is kept by the second node for approximately ten minutes.

7. The method of claim 1, wherein the value corresponding to the path cost is increased by 10% to 20% above actual path cost.

8. The method of claim 1, wherein sending the increased path cost to first nodes comprises sending to first nodes selected randomly over all nodes to which the second node sends a routing advertisement.

9. The method of claim 4, wherein a first node receiving the actual path cost by the sending node via routing updates may be instructed by the sending node not to distribute the cost information to its neighbors until the sending node clears it for distribution.

24. The method of claim 1, wherein the gateway and the node are part of a frequency-hopping spread spectrum wireless utility network.

10. A method of load management in a network, comprising:

determining whether a number of nodes registered with a gateway exceeds a predetermined number, and in the event the determination is that the gateway has exceeded the predetermined number, reducing a route advertisement range by one hop.

11. A method of load management in a network, comprising:

determining whether a number of nodes registered with a gateway does not exceed a predetermined number, and in the event the determination is that the gateway has not exceeded the predetermined number, increasing a route advertisement range by one hop.

12. A method of load management in a network, comprising:

informing a gateway, by a node registering with the gateway, if the gateway is the node'"'"'s primary, secondary or tertiary route; and

determining whether the number of nodes that the gateway has registered is above a predetermined limit, and in the event the determination is that the number of nodes that the gateway has registered is above a the predetermined limit, sending, by the gateway, a negative acknowledgement to any node attempting to register as a secondary or tertiary route.

13. The method of claim 12, wherein the predetermined limit is higher for a node attempting to register as a secondary route than for a node attempting to register as a tertiary route.

14. The method of claim 12, comprising receiving a negative acknowledgement, by a node attempting to register as a secondary or tertiary route, and storing the negative acknowledgement in a list.

15. The method of claim 14, wherein the negative acknowledgement is stored in the list for a predetermined time.

16. The method of claim 15, wherein the predetermined time is approximately three hours after receiving the negative acknowledgement.

17. The method of claim 15, wherein once the predetermined time has expired, removing the negative acknowledgement from the list and informing the gateway, by the node re-registering with the gateway, if the gateway is the node'"'"'s primary, secondary or tertiary route.

18. The method of claim 12, wherein the predetermined limit for the number of nodes that the gateway may register as the node'"'"'s primary or secondary route is established by synchronizing a plurality of gateways with each other.

19. The method of claim 12, wherein the gateway sends a positive acknowledgement to a registration request from a node for a primary route.

20. The method of claim 19, wherein the gateway drops a node registered with it as a secondary or tertiary route before sending a positive acknowledgement to a registration request from a node for a primary route.

21. The method of claim 20, wherein the gateway sends a positive acknowledgement to a registration request from a node for a primary route and the gateway is above the predetermined node limit.

22. The method of claim 19, wherein the gateway increases by one or more its predetermined node limit until it is able to drop one or more nodes.

23. The method of claim 19, wherein the gateway dynamically adjusts its predetermined node limit based on network traffic conditions.