Routing Packets on a Network Using Directed Graphs

• US 20110216656A1
• Filed: 05/12/2011
• Published: 09/08/2011
• Est. Priority Date: 04/13/2007
• Status: Active Grant

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

a first network node defining a single source of the graph, wherein the source only transmits data when using the graph;

a second network node defining a destination node of the graph, wherein the destination node only receives data when using the graph; and

a predetermined primary communication path along which a communication packet is to be primarily routed from the source node to the destination node via one or more intermediate nodes.

2. The multi-node mesh network of claim 1, 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.

3. The multi-node mesh network of claim 2, 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.

4. The multi-node mesh network of claim 2, 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.

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

6. The multi-node mesh network of claim 1, 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.

8. The multi-node mesh network of claim 1, 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.

7. (canceled)

9. 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;

assigning a unique graph identifier to 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.

10. The method of claim 9, 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.

11. The method of claim 10, 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.

12. The method of claim 9, wherein establishing a plurality of direct connections includes establishing a plurality of wireless connections.

13. The method of claim 9, wherein establishing a plurality of direct connections includes establishing unidirectional connections.

14. The method of claim 13, 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.

15. The method of claim 14, 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.

16. The method of claim 14, 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.

17. The method of claim 14, 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 anode associated with the first routing entry; and

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

18. The method of claim 13, 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.

19. The method of claim 13, 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.

20. The method of claim 19, 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.

21. The method of claim 9, 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 acknowledgment 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.

22. The method of claim 9, 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.

23. The method of claim 22, 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.

24. The method of claim 9, 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.

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

26. The method of claim 9, 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.

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

28. 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 devices 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;

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; and

routing data packets of a second type at intermediate network devices based on information other than graph identifiers.

29. The method of claim 28, 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.

30. The method of claim 28, 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.

32. The method of claim 28, 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.

33. The method of claim 32, 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.

34. The method of claim 28, 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.

31. (canceled)