Digraph based mesh communication network

• US 20060029060A1
• Filed: 08/05/2004
• Published: 02/09/2006
• Est. Priority Date: 08/05/2004
• Status: Active Grant

• Current Assignee: Analog Devices International Unlimited Company (Analog Devices, Inc.)
• Original Assignee: Dust Networks Incorporated (Analog Devices, Inc.)
• Inventors: Pister, Kristofer S.J.
• Granted Patent: US 8,194,655 B2
• Time in Patent Office: Days
• US Class Current: 370/389
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04W 40/00 Communication routing or communication path finding

Abstract

In a packet communication network, a method of packet switched transport is provided using digraphs defining paths among nodes in which a graph identifier, instead of a literal destination address, is used to determine paths through the network. The nodes themselves implement a real-time mesh of connectivity. Packets flow along paths that are available to them, flowing around obstructions such as dead nodes and lost links without need for additional computation, route request messages, or dynamic routing tree construction.

Claims

1. In a multi-hop packet-switched communication network, a method for routing packets comprising:

providing at least one digraph defining routing information for packets via a plurality of directional links among a plurality of nodes, at least one of said nodes having a plurality of directional output links;

generating a plurality of packets, each of said packets having a header associating each packet with one or more digraphs; and

using said header on each said packet at each said node to direct each said packet to flow between said nodes via at least one of said directional links at said nodes according merely to said digraph.

2. In a multi-hop packet-switched communication network, a method for routing packets comprising:

providing at least a first node and a second node, said first node and said second node serving as nodes in said packet communication network and each said first node and said second node having independent intelligence for storing and redirecting units of communication traffic;

providing at least one digraph, each said digraph being expressed as routing information for directional links at each node in the network, including at least a first node having a plurality of outgoing directional links from said first node to at least a second node;

generating a plurality of packets, each of said packets having a header; and

directing, via said routing information at each said node, said packets to flow between selected ones of said nodes according to one of said digraphs.

3. The method according to claim 2 wherein, at each said individual node that is operative to receive a packet, determining:

a) whether the packet is intended for said individual node; and

b) whether the packet is of interest to said individual node.

4. The method according to claim 3 wherein selected ones of said individual nodes determine that the packet is intended for itself if said individual node has no outgoing links in the digraph.

5. The method according to claim 3 wherein selected ones of said individual nodes determine that the packet is intended for itself from comparison of information at said individual node with the packet.

6. The method according to claim 3 wherein each said node is operative to determine that a received packet is of interest to itself if a specific destination pattern described in the received packet matches with said node.

7. The method according to claim 6 wherein a specific destination pattern includes a WAN connection at said node.

8. The method according to claim 6 wherein a specific destination pattern includes a measured sensor value at said node is within a preselected range.

9. The method according to claim 5 wherein said determining step comprises:

detecting whether a “

time to live”

field has expired.

10. The method according to claim 5 wherein said determining step comprises:

detecting whether the received packet has requested an action of which said node is capable; and

, if said node is capable of the requested action,

taking the requested action.

11. The method according to claim 10 wherein said requested action comprises:

extracting a payload of the packet out of the network; and

sending the payload to a destination via the Internet.

12. The method according to claim 10 wherein said requested action comprises:

extracting a payload of the packet out of the mesh network; and

causing a specific task that is local to said node to be performed.

18. The method according to claim 2 wherein, at a node that is operative to receive packets and wherein payloads of at least two packets are stored on a single node, further comprising the steps of:

combining said payloads of said at least two packets; and

replacing said at least two packets if said at least two said packets are on the same digraph.

19. The method according to claim 2 wherein, at a node that is operative to receive packets, further comprising the step of:

compressing a payloads of said packets prior to transmission.

13. In a multi-hop packet-switched communication netwmethod for routing packets via a plurality of digraphs, a digraph being a pattern of directional links between nodes, the method comprising:

providing to each node sufficient information to establish said plurality of digraphs defining packet routing information at said nodes and directional links between said nodes;

generating a plurality of packets, each of said packets having a header carrying a plurality of graph IDs for at least a selection of said plurality of digraphs; and

directing each said packet to flow between said nodes according to said plurality of said predefined digraphs.

14. The method according to claim 13 wherein said directing step comprises:

a) using a first graph ID for the packet to direct the packet along at least a first link of a first graph;

then at a selecting first receiving node

b) deleting the first graph ID and using a second graph ID to forward the packet onward via at least a first link of the second graph to a selected second receiving node; and

c) repeating steps a) and b) for subsequent receiving nodes.

15. The method according to claim 14 wherein flow rate of packets depends upon the graph in which said packets flow.

16. The method according to claim 14 wherein priority among packets depends upon the graph in which said packets flow.

17. The method according to claim 14 comprising:

d) repeating steps a), b) and c) for subsequent graphs.