Routing packets on a network using directed graphs

• US 8,892,769 B2
• Filed: 05/12/2011
• Issued: 11/18/2014
• Est. Priority Date: 04/13/2007
• Status: Active Grant

• Current Assignee: FieldComm Group, Inc.
• Original Assignee: 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 Lynn
• Primary Examiner(s): Maung, Zarni
• Application Number:
  US13/106,464
• Publication Number:
  US 20110216656A1
• Time in Patent Office: 1,286 Days
• Field of Search: 709/203, 709223-229, 709238-242, 709/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 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.

2. The method of claim 1, 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.

3. The method of claim 1, 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.

4. The method of claim 1, 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.

5. The method of claim 4, 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 b the graph identifier.

6. The method of claim 1, 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.