Routing Packets on a Network Using Directed Graphs

• US 20090046732A1
• Filed: 04/10/2008
• Published: 02/19/2009
• Est. Priority Date: 04/13/2007
• Status: Active Grant

• Current Assignee: FieldComm Group, Inc.
• Original Assignee: Hart Communication Foundation (FieldComm Group, Inc.)
• Inventors: Blevins, Terrence L., Nixon, Mark J., Zats, Yuri, Rotvold, Eric D., Pratt, Wallace A. JR., Pramanik, Robin S., Lennvall, Tomas P.
• Granted Patent: US 8,230,108 B2
• Time in Patent Office: Days
• US Class Current: 370/406
• 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;

associating a first node, a second node, and zero or more intermediate nodes of the multi-node communication network with the first graph; and

associating a first communication path including the first node, the second node, and the zero or more intermediate nodes with the first graph;

associating a first graph identifier with the first graph;

sending a first data packet from the first node, wherein the first node is a source of the first data packet and the second node is a destination of the first data packet;

sending the first graph identifier with the first data packet; and

routing the first data packet to the destination of the first data packet based on the first graph identifier.

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

3. The method of claim 2, wherein sending a 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 a first graph includes associating the first communication path of the first graph with a plurality of direct wireless connections between pairs of nodes of the multi-node communication network;

and further includes associating the first graph with at least a third node of the multi-node communication network distinct from the first node and from the second node.

5. The method of claim 4, wherein defining a 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 defining a first graph includes associating the first node with a source of the directed graph and associating the second node with a destination of the directed graph.

7. The method of claim 4, wherein defining a first graph includes providing a first partial definition of the first graph to the third node, wherein the first partial definition includes information related to a neighbor network node associated with the first graph and connected to the third node via a first one of the plurality of direct wireless connections associated with the first graph.

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

and wherein routing the first data packet to the destination based on the first graph identifier includes selecting one of the neighbor network node and the redundant neighbor network node at the third node.

9. The method of claim 8, wherein selecting one of the neighbor network node and the redundant neighbor network node at the third node includes selecting one of the neighbor network node and 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 or the redundant network node.

10. The method of claim 1, further comprising:

defining a second graph, including;

associating the first node, the second node, and zero or more intermediate nodes of the multi-node communication network with the second graph; and

associating a second communication path including the first node, the second node, and one or more intermediate nodes with the first graph;

wherein the first graph and the second graph are directed graphs;

wherein the first communication path specifies a flow of data from the first node to the second node and wherein the second communication path specifies a flow of data from the second node to the first node; and

wherein at least one of the first graph and the second graph includes a network node not included by the other one of the first graph and the second graph.

11. The method of claim 1, further comprising:

sending a second data packet from the first node, wherein the first node is the source of the second data packet and the second node is the destination of the second data packet;

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

routing the second data packet to the second node 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 a first data packet includes sending data associated with at least one of a first latency requirement or a first reliability requirement;

and wherein sending a 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 12, 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, further comprising

defining a second graph, including:

associating the second node, a third node, and zero or more intermediate nodes with the second graph; and

associating a second communication path including the second node, the third node, and zero or more intermediate nodes with the second graph;

associating a second graph identifier with the second graph;

wherein

the first node and the third node are field devices operating in the process control environment, and wherein the second node 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 to the third node, including;

sending the first graph identifier with the second data packet;

routing the second data packet to the second node based on the first graph identifier;

sending the second graph identifier with the second data packet; and

routing the second data packet to the third node based on the second graph identifier.

16. The method of claim 1, wherein each of sending a first data packet, sending a 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 source of the first data packet to the 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 to the destination of 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.

23. The device of claim 18, wherein the first graph is a unidirectional graph defining 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 18, 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.

19. A device 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 first routing entry comprising;

a network address associated with a first peer device; and

a first graph identifier associated with a first graph including the device and the first peer device;

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 peer device exchange data without a use of an intermediate network device.

21. The device of claim 19, wherein the graph routing further includes a second routing entry comprising:

a network address associated with a second peer device; and

the first graph identifier associated with the first graph, the graph further including the second peer device.

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

a path information associated with a data path from the device to a destination network device, wherein the path information specifies each intermediate peer device between the device and the destination network device.

26. A multi-node mesh network operating in a process control environment and including a plurality of network nodes, the network comprising:

a first network node including a first memory unit to store a first graph routing table;

a second network node including a second memory unit to store a second graph routing table, wherein the first graph routing table and the second graph routing tables store different information;

a plurality of direct connections between pairs of network nodes in the plurality of network nodes; and

a network manager to define a set of graphs, each graph within the set of graphs specifying a communication path between a pair of network nodes in the plurality of network nodes for transmitting data between the pair of network nodes.

27. The multi-node mesh network of claim 26, wherein the first network node includes a network interface adapted to send a first data packet to the second network node, the first data packet including:

a data payload; and

a routing information specifying a graph identifier corresponding to one of the set of graphs with which the second node is associated.

28. The multi-node mesh network of claim 27, wherein the data payload of the first data packet includes at least one of a process control information, a network management information, a device status information, or a device management information.

29. The multi-node mesh network of claim 27, wherein the first network node includes a network interface adapted to send a second data packet to the second network node, the second data packet including:

a data payload; and

a routing information specifying each network node associated with a communication path from the first network node to the second network node.

30. The multi-node mesh network of claim 26, wherein the network manager includes a third memory unit to store a topology of the multi-node mesh network.

31. The multi-node mesh network of claim 26, further comprising:

a gateway host including;

a first interface providing a direct connection with at least one of the plurality of network nodes;

a second interface to transmit data between the multi-node mesh network and an external network.

32. The multi-node mesh network of claim 26, wherein each graph within the set of graphs is a unidirectional graph.

33. The multi-node mesh network of claim 26, wherein the first network node is a field device performing at least one of a control or a measurement function in the process control environment.

34. A method of routing a data packet between a first node and a second node on a communication network, the method comprising:

establishing a plurality of direct connections, wherein each of the plurality of direct connections connects a pair of nodes of the communication network;

defining a first graph, including associating a plurality of nodes with the first graph, wherein each of the plurality of nodes belongs to the communication network;

associating a first graph identifier with the first graph;

providing partial definitions of the first graph and the first graph identifier to at least some of the plurality of nodes associated with the first graph;

determining a type of data associated with a payload of the data packet;

sending the data packet from the first node;

if the data associated with the payload of the data packet is determined to be of a first type;

sending the graph identifier with the data packet;

directing the data packet to the second node via an intermediate node, including forwarding the data packet to a neighbor node of the intermediate node, wherein the intermediate node and the neighbor nodes are nodes associated with the first graph and wherein the intermediate node and the neighbor node are connected by at least one of the plurality of direct connections; and

if the data associated with the payload of the data packet is determined to be of a second type;

not sending the graph identifier with the data packet.

35. The method of claim 34, wherein the first graph is a directed graph, wherein each of the plurality of nodes associated with the first graph shares at least one direct connection with at least one other node associated with the first graph, and wherein defining the first graph further includes:

defining a path from the first node to the second node, wherein the path includes a plurality of direct connections between pairs on nodes.

36. The method of claim 35, wherein defining the first graph further includes associating the first node with a source of the first graph and associating the second node with a destination of the first graph.

37. The method of claim 34, wherein establishing a plurality of direct connections includes establishing a plurality of wireless connections.

38. The method of claim 34, wherein establishing a plurality of direct connections includes establishing unidirectional connections.

39. The method of claim 38, wherein providing partial definitions of the first graph to at least some of the plurality of nodes associated with the first graph includes, for each of the at least some of the plurality of nodes:

defining a first routing entry, wherein the first routing entry stores the first graph identifier and an address of a first subsequent node associated with the first graph and being one hop closer to the second node.

40. The method of claim 39, wherein providing partial definitions of the first graph to at least some of the plurality of nodes associated with the first graph further includes:

defining a second routing entry, wherein the second routing entry stores the first graph identifier and an address of a second subsequent node associated with the first graph and being one hop closer to the second node, wherein the second subsequent node is distinct from the first subsequent node.

41. The method of claim 39, wherein forwarding the packet to a neighbor of the intermediate node includes:

selecting between the first routing entry and the second routing entry in view of a first statistical indication associated with the first subsequent node and a second statistical indication associated with the second subsequent node; and

sending the data packet to a node associated with the selected routing entry.

42. The method of claim 39, wherein forwarding the packet to a neighbor of the intermediate node includes:

selecting the second routing entry in response to failing to deliver the data packet via a node associated with the first routing entry; and

sending the data packet to a node associated with the second selected routing entry.

43. The method of claim 38, wherein providing partial definitions of the first graph to at least some of the plurality of nodes associated with the first graph includes, for each of at least some of the plurality nodes:

defining a first routing entry, wherein the first routing entry stores the first graph identifier and an identifier of a direct connection, wherein the direct connection connects the node to a next node associated with the first graph, wherein the next node is one hop closer to the second node.

44. The method of claim 38, wherein the first node is a field device and wherein the second node is a gateway device connecting the communication network to a second network, wherein the communication network is a process control network and wherein establishing a plurality of direct connections includes exchanging messages formatted in accordance with the HART®

communication protocol over a wireless link, and wherein defining the first graph is defining an upstream graph.

45. The method of claim 44, further including:

defining a second graph, including defining a path from the second node to the first node, wherein the second graph is a downstream graph and wherein the first graph and the second graph are not symmetrical.

46. The method of claim 34, wherein forwarding the data packet to a neighbor of the intermediate node includes:

sending the data packet to the neighbor node;

keeping a copy of the data packet at the intermediate node until an acknowledgement is received from the neighbor node;

deleting the data packet if the acknowledgement is received; and

sending the packet to a second neighbor node of the intermediate node if the acknowledgement is not received, wherein the second neighbor node is a node associated with the first graph.

47. The method of claim 34, further comprising:

providing a complete definition of the first graph to the first node;

if the data associated with a payload of the data packet is determined to be of a second type further including;

sending a definition of a complete route with the data packet, wherein the definition of the complete route contains a list of addresses for each node associated with the first graph.

48. The method of claim 47, wherein sending a complete route with the data packet in response to detecting a second data type includes, at each intermediate node:

deleting an address of the intermediate node from the list to produce a reduced list; and

sending the data packet and the reduced list to a node listed immediately after the intermediate node in the list.

49. The method of claim 34, wherein establishing a plurality of direct connections includes establishing a plurality of wireless connections and wherein defining a first graph includes:

analyzing a topology of the communication network; and

collecting statistical data from at least one of the nodes of the communication network, wherein the statistical data is indicative of at least one of a propagation delay or a delivery success rate.

50. The method of claim 34, wherein defining a first graph includes testing the first graph for a presence of loops defining circular paths between pairs of nodes.

51. The method of claim 34, wherein directing the data packet to the second node via an intermediate node includes not sending any routing information other than the graph identifier with the data packet.

52. The method of claim 34, wherein the first type of data is associated with a higher reliability requirement than the second type of data.

53. A method of routing data in a multi-node wireless network operating in a process control environment and having a plurality of direct wireless connections between a plurality of network devices, wherein each of the plurality of network device is a node of the multi-node wireless network, the method comprising:

attaching graph identifiers to data packets of a first type at originating network devices to send the data packets of the first type between pairs of the plurality of network devices; and

routing the data packets of the first type at intermediate network devices using the graph identifiers, wherein each of the graph identifiers corresponds to one of a plurality of graphs, each of the plurality of graphs associated with two or more of the plurality of nodes and one or more of the plurality of direct wireless connections;

wherein at least two of the plurality of graphs differ in at least one node associated with the respective graph.

54. The method of claim 53, wherein defining a plurality of graphs includes defining a plurality of directed graphs, each directed graph associated with a source node, a destination node, and zero or more intermediate nodes.

55. The method of claim 53, further comprising:

attaching complete path definitions to data packets of a second type at originating network devices to send the data packets of the second type between pairs of the plurality of network devices;

routing the data packets of the second type at intermediate network devices using the complete path definitions, wherein each complete path definition corresponds to a communication path including two or more nodes and one or direct wireless connections; and

wherein a communication path specifies a source node, a destination node, and each intermediate node associated with the communication path.

56. The method of claim 55, further comprising:

analyzing the data packets at the originating network devices to determine which of the data packets are associated with the first type and which of the data packets are associated with the second type, including analyzing at least one of a latency requirement or a reliability requirement.

57. The method of claim 53, wherein routing the data packets of the first type at intermediate network devices using the graph identifiers includes locating corresponding routing entries at the intermediate network devices based on the graph identifiers, wherein each of the routing entries corresponding to a graph identifier specifies a next node associated with a graph identified by the graph identifier.

58. The method of claim 57, wherein locating corresponding routing entries at the intermediate network devices at the intermediate network devices based on the graph identifiers includes locating partial graph definitions at the intermediate network devices, wherein each partial graph definition specifies one or more immediately neighboring nodes associated with a graph identified by the graph identifier.

59. The method of claim 53, further comprising:

attaching a complete list of intermediate nodes to a data packet of the first type at an originating network device, the complete list specifying a complete path to a destination network device;

wherein the originating network device and the destination network device correspond to a pair of network devices associated with a graph identifier attached to the data packet;

routing the data packet from the originating network device toward the destination network device in accordance with the complete list of intermediate nodes; and

routing the data packet at an intermediate network device using the graph identifier in response to failing to route the data packet in accordance with the complete list of intermediate nodes.