Routing packets on a network using directed graphs

• US 8,230,108 B2
• Filed: 04/10/2008
• Issued: 07/24/2012
• Est. Priority Date: 04/13/2007
• Status: Active Grant

• Current Assignee: FieldComm Group, Inc.
• Original Assignee: Dust Networks Incorporated (Analog Devices, Inc.), Hart Communication Foundation (FieldComm Group, Inc.)
• Inventors: Pratt, Wallace A. Jr., Nixon, Mark J., Rotvold, Eric D., Pramanik, Robin S., Lennvall, Tomas P., Zats, Yuri, Blevins, Terrence L.
• Primary Examiner(s): Maung, Zarni
• Application Number:
  US12/101,071
• Publication Number:
  US 20090046732A1
• Time in Patent Office: 1,566 Days
• Field of Search: 709238-250
• US Class Current: 709/238
• CPC Class Codes: H04L 12/66 Arrangements for connecting between networks having differing types of switching systems, e.g. gateways
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/34 Source routing
• CPC Class Codes: H04L 45/42 Centralised routing
• CPC Class Codes: H04L 45/44 Distributed routing
• CPC Class Codes: H04W 40/22 using selective relaying for reaching a BTS [Base Transceiver Station] or an access point
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

A method of routing a data packet between a first node and a second node on a communication network includes defining a first graph through the first node and the second node and zero or more intermediate nodes, associating several nodes which belong to the communication network with the first graph, associating a first unique graph identifier with the first graph and providing at least partial definitions of the first graph and the first unique identifier to at least some of the nodes associated with the first graph. The method then sends data packet with the graph identifier from the first node, and directs the data packet to the second node via the zero or more intermediate nodes using the graph identifier. This method may include forwarding the packet to a neighbor node of an intermediate node if the intermediate node and the neighbor node are nodes associated with the first graph and if the intermediate node and the neighbor node are connected by at least one direct communication connection.

Claims

1. A method of routing data in a multi-node communication network operating in a process control environment, the method comprising:

defining a first graph, including;

assigning a first node to be exactly one source of the first graph;

assigning a second node to be destination of the first graph;

associating one or more intermediate nodes of the multi-node communication

network with the first graph; and

associating a first graph identifier with the first graph;

defining a second graph, including;

assigning the first node to be exactly one source of the second graph;

associating a third node with a destination of the second graph; and

associating a second graph identifier with the second graph; and

sending a first data packet from the first node;

sending one of the first graph identifier or the second graph identifier with the first data packet; and

routing the first data packet along the first graph or the second graph based on the first graph identifier or the second graph identifier.

2. The method of claim 1, wherein sending the first data packet from the first node includes sending one of measurement data associated with sensing or measurement functions or control data associated with actuating or positioning functions, and wherein at least one of the first node, the second node, or the third node is a field device operating in the process control environment.

3. The method of claim 2, wherein sending the first data packet from the first node further includes sending one of the measurement data or the control data to or from a gateway device connecting the multi-node communication network with an external network.

4. The method of claim 1, wherein defining the first graph includes associating a primary communication path of the first graph with a plurality of direct wireless connections between pairs of nodes of the multi-node communication network.

5. The method of claim 4, wherein defining the first graph includes defining a directed graph, such that data travels in only one direction along each direct wireless connection associated with the first graph.

6. The method of claim 5, wherein the first graph has exactly one destination node.

7. The method of claim 4, wherein defining the first graph includes providing a first partial definition of the first graph to one of the one or more intermediate nodes associated with the first graph, wherein the first partial definition includes information related to a neighbor network node associated with the first graph and connected to the one of the one or more intermediate nodes via a first one of the plurality of direct wireless connections associated with the first graph and includes an identification of a portion of the primary communication path.

8. The method of claim 7, wherein providing the first partial definition of the first graph to the one of the one or more intermediate nodes further includes providing at least one redundant neighbor network node distinct from the neighbor network node, wherein the at least one redundant neighbor network node is associated with the first graph and is connected to the one of the one or more intermediate nodes via a second one of the plurality of the direct wireless connections on a secondary communication path associated with the first graph;

and wherein routing the first data packet based on the first graph identifier includes selecting the at least one redundant neighbor network node at the one of the one or more intermediate nodes after considering the ability to route via the neighbor network node.

9. The method of claim 8, wherein selecting the redundant neighbor network node at the one of the one or more intermediate nodes includes selecting the redundant neighbor network node based on statistical data indicative of a probability of successfully delivering the first data packet via the neighbor network node.

10. The method of claim 1, wherein defining the second graph includes:

associating a further set of one or more intermediate nodes of the multi-node communication network with the second graph, the second graph specifying a further primary communication path along which a communication packet is to be routed between the third node associated with the destination of the second graph and the first node associated with the exactly one source of the second graph via at least some of the further set of intermediate nodes.

11. The method of claim 1, further comprising:

sending a second data packet from the first node associated with the exactly one source of the first graph;

sending a complete list of intermediate nodes with the second data packet;

routing the second data packet to the second node associated with the destination of the first graph based on the complete list of intermediate nodes.

12. The method of claim 11, further comprising providing the first node with at least a partial topology of the multi-node communication network, so that the first node is aware of at least one complete communication path from the first node to the second node.

13. The method of claim 11, wherein sending the first data packet includes sending data associated with at least one of a first latency requirement or a first reliability requirement;

and wherein sending the second data packet includes sending data associated with at least one of a second latency requirement or a second reliability requirement.

14. The method of claim 11, wherein sending the first data packet includes sending process control information and wherein sending the second data packet includes sending network management information.

15. The method of claim 1, wherein defining the second graph includes:

assigning one or more further intermediate nodes to the second graph, the second graph specifying a predetermined path along which a communication packet is to be routed from the first node associated with the exactly one source node of the second graph to the third node associated with the destination of the second graph via the one or more further intermediate nodes; and

wherein the first node and the node are field devices operating in the process control environment, and wherein the second node associated with the destination of the first graph is a gateway device connecting the multi-node communication network with an external network;

the method further comprising;

sending a second data packet from the first node associated with the exactly one source of the first graph to the third node associated with the destination of the second graph, including;

sending the first graph identifier with the second data packet at the first node associated with the exactly one source of the first graph;

routing the second data packet to the second node associated with the destination of the first graph based on the first graph identifier;

sending the second graph identifier with the second data packet at the second node associated with the destination of the first graph; and

routing the second data packet to the third node associated with the destination of the second graph based on the second graph identifier.

16. The method of claim 1, wherein each of sending the first data packet, sending the ine of the first graph indentifier or the second graph identifier, and routing the first data packet is supported by a communication protocol of the multi-node communication network, wherein the communication protocol further supports commands of the Highway Addressable Remote Transmitter (HART) protocol.

17. The method of claim 1, further comprising:

sending a list of intermediate nodes with the first data packet, wherein the list of intermediate nodes specifies a complete path from the first node associated with the exactly one source of the first data packet to a destination of the data packet in an order encountered in a direction of the destination of the data packet; and

wherein routing the first data packet based on the first graph identifier includes;

forwarding the data packet to an intermediate node included in the list of intermediate nodes according to the list of intermediate nodes;

detecting an error in forwarding the data packet from the intermediate node toward the destination of the data packet according to the list of intermediate nodes; and

routing the data packet to the destination of the data packet using the first graph identifier in response to detecting the error.

18. The method of claim 17, wherein detecting an error includes detecting an unavailability, at the intermediate node, of a next node following the intermediate node in the list of intermediate nodes.

19. A device for operating in a multi-node mesh network comprising:

a network interface to establish a connection with at least one peer device;

a computer-readable memory unit storing;

a substantially unique device network address, wherein the device network address is associated with the device;

a graph routing table including;

a network address of a first peer device;

a first graph identifier associated with a first graph including the device and the first peer device, wherein the first graph connects a source of the first graph to a destination node via a first one or more intermediate devices;

a network address of a second peer device; and

a second graph identifier associated with a second graph including the device and the second peer device, wherein the second graph includes a communication path along which a communication packet can be routed from a source of the second graph to the destination node via a second one or more intermediate devices;

a set of computer instructions to route a data packet based on a graph identifier associated with the data packet; and

a processor unit adapted to control the network interface and execute the computer instructions stored in the memory unit.

20. The device of claim 19, wherein the connection with the at least one peer device is a direct wireless connection, such that the device and the at least one peer device exchange data without a use of an intermediate network device.

21. The device of claim 19, wherein the first graph further includes the second peer device.

22. The device of claim 19, wherein the computer-readable memory unit further stores:

a path information associated with a primary communication path from the device to the destination node, wherein the path information specifies each intermediate peer device between the device and the destination node.

23. The device of claim 19, wherein the first graph defines a flow of data from a second peer device to a third peer device via the device and the first peer device.

24. The device of claim 19, wherein the multi-node mesh network operates in a process control environment;

and wherein the device further comprises a process control module adapted to perform a process control function in the process control environment.

25. The device of claim 24, wherein the first graph is a unidirectional graph defining a flow of data from a peer field device to a gateway device via the device and the first peer device;

wherein the gateway device operatively connects the multi-node mesh network to a plant automation network.