Digraph based mesh communication network

• US 8,194,655 B2
• Filed: 08/05/2004
• Issued: 06/05/2012
• 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.
• Primary Examiner(s): Chriss, Andrew
• Assistant Examiner(s): LOUIS, VINNCELAS
• Application Number:
  US10/914,056
• Publication Number:
  US 20060029060A1
• Time in Patent Office: 2,861 Days
• Field of Search: 370/389, 370/395.41, 370/395.42, 370/253, 370/338, 370/238, 370/330, 370/328, 370/473, 370/311, 370/315, 370/401, 370/351, 370/237, 370/241, 455/450, 455/466, 358/402, 358/407, 358/425, 358/426.02, 358/426.14, 709/222, 709/224, 709/230, 709/236, 340/531
• 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:

creating at least a portion of one or more digraphs at a current node of a first type, wherein the one or more digraphs are defined in the multi-hop packet-switched communication network, wherein each digraph of the one or more digraphs defines a plurality of nodes and a plurality of directional links connecting the plurality of nodes, wherein the plurality of directional links comprise zero or more incoming and one or more outgoing directional links associated with each node of the plurality of nodes, and wherein each directional link defined by a particular digraph is associated with a label of a same value;

and

transmitting, using a transmitter, a packet from the current node directly to a next node of a set of next nodes of a second type or indirectly through a node of a third type, wherein content of the packet indicates a digraph for the packet to flow along, wherein the packet is transmitted to the next node along one or more outgoing directional links of the indicated digraph, wherein the one or more outgoing directional links of the indicated digraph are each associated with a label of a same specific value associated with the indicated digraph, and wherein the indicated digraph comprises one of the one or more digraphs for which at least a portion was created at the current node.

2. The method according to claim 1, further comprising:

transmitting the packet from the current node along an alternate outgoing directional link of the one or more outgoing directional links of an alternate packet-associated digraph.

3. The method according to claim 1, wherein a flow rate of packets is based at least in part on which of the one or more digraphs the packet is associated with.

4. The method according to claim 1, wherein a priority of the packet is based at least in part on which of the one or more digraphs the packet is associated with.

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

creating at least a portion of one or more digraphs at a current node of a first type, wherein the one or more digraphs are defined in the multi-hop packet-switched communication network, wherein each digraph of the one or more digraphs defines a plurality of nodes and a plurality of directional links connecting the plurality of nodes, wherein the plurality of directional links comprise one or more incoming and zero or more outgoing directional links associated with each node of the plurality of nodes, and wherein each directional link defined by a particular digraph is associated with a label of a same value;

receiving, using a receiver, a packet at the current node from an incoming directional link; and

determining a packet-associated digraph that is associated with the packet based at least in part on the at least the portion of the one or more digraphs created at the current node, wherein the packet-associated digraph defines a specific set of incoming directional links of the one or more incoming directional links, wherein the specific set of incoming directional links are each associated with a label of a same specific value associated with the packet-associated digraph, wherein the incoming directional link is one link within the specific set of incoming directional links associated with the packet-associated digraph, wherein the packet-associated digraph comprises one of the one or more digraphs for which at least a portion was created at the current node, and wherein the current node of the first type receives the packet directly from a prior node of a second type or indirectly through a node of a third type.

6. The method according to claim 5, further comprising determining whether the packet is intended for the current node.

7. The method according to claim 6, wherein determining whether the packet is intended for the current node comprises determining if the current node has no outgoing links in the packet-associated digraph.

8. The method according to claim 6, wherein determining whether the packet is intended for the current node uses a comparison of information at the current node with the packet.

9. The method according to claim 8, wherein the comparison of information at the current node with the packet comprises:

detecting whether a “

time to live”

field has expired.

10. The method according to claim 8, wherein the comparison of information at the current node with the packet comprises:

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

, if the current node is capable of the requested action,

taking the requested action.

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

extracting a payload of the packet; and

sending the payload to a destination via the Internet.

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

extracting a payload of the packet; and

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

13. The method according to claim 6, wherein determining whether the packet is intended for the current node comprises satisfying a condition represented in the packet.

14. The method according to claim 13, wherein the condition represented in the packet comprises the existence of a WAN connection at said node.

15. The method according to claim 13, wherein the condition represented in the packet comprises the condition that a measured sensor value at the current node is within a preselected range.

16. The method according to claim 5, further comprising:

combining a payload of the packet with a second payload to make a combined payload that is part of a combined-payload packet; and

transmitting the combined-payload packet from the current node along an outgoing directional link of the zero or more outgoing directional links of the packet-associated digraph.

17. The method according to claim 5, wherein, further comprising:

compressing a payload of the packet to make a compressed payload that is part of a compressed-payload packet; and

transmitting the compressed-payload packet from the current node along an outgoing directional link of the zero or more outgoing directional links of the packet-associated digraph.

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

a current node of a first type, wherein at least a portion of one or more digraphs are created at the current node, wherein the one or more digraphs are defined in the multi-hop packet-switched communication network, wherein each digraph of the one or more digraphs defines a plurality of nodes and a plurality of directional links connecting the plurality of nodes, wherein the plurality of directional links comprise zero or more incoming and one or more outgoing directional links associated with each node of the plurality of nodes, and wherein each directional link defined by a particular digraph is associated with a label of a same value; and

a next node of a set of next nodes of a second type, wherein a packet is transmitted from the current node directly to the next node or indirectly through a node of a third type, wherein content of the packet indicates a digraph for the packet to flow along, wherein the packet is transmitted to the next node along one or more outgoing directional links of the indicated digraph, wherein the one or more outgoing directional links defined by the indicated digraph are each associated with a label of a same specific value associated with the indicated digraph, and wherein the indicated digraph comprises one of the one or more digraphs for which at least a portion was created at the current node.

19. The system according to claim 18, wherein the packet is transmitted from the current node along an alternate outgoing directional link of the one or more outgoing directional links of an alternate packet-associated digraph.

20. The system according to claim 18, wherein a flow rate of packets is based at least in part on which of the one or more digraphs the packet is associated with.

21. The system according to claim 18, wherein a priority of the packet is based at least in part on which of the one or more digraphs the packet is associated with.

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

a current node of a first type, wherein at least a portion of one or more digraphs are created at the current node, wherein the one or more digraphs are defined in the multi-hop packet-switched communication network, wherein each digraph of the one or more digraphs defines a plurality of nodes and a plurality of directional links connecting the plurality of nodes, wherein the plurality of directional links comprise one or more incoming and zero or more outgoing directional links associated with each node of the plurality of nodes, and wherein each directional link defined by a particular digraph is associated with a label of a same value, and wherein a packet is received at the current node from an incoming directional link, and wherein a packet-associated digraph that is associated with the packet is determined based at least in part on the at least the portion of the one or more digraphs created at the current node, wherein the packet-associated digraph defines a specific set of incoming directional links of the one or more incoming directional links, wherein the specific set of incoming directional links are each associated with a label of a same specific value associated with the packet-associated digraph, wherein the incoming directional link is one link within the specific set of incoming directional links associated with the packet-associated digraph, wherein the packet-associated digraph comprises one of the one or more digraphs for which at least a portion was created at the current node; and

a prior node of a second type, wherein the current node of the first type receives the packet directly from the prior node of the second type or indirectly through a node of a third type.

23. The system according to claim 22, wherein it is determined whether the packet is intended for the current node.

24. The system according to claim 23, wherein determining whether the packet is intended for the current node comprises determining if the current node has no outgoing links in the packet-associated digraph.

25. The system according to claim 23, wherein determining whether the packet is intended for the current node uses a comparison of information at the current node with the packet.

26. The system according to claim 25, wherein the comparison of information at the current node with the packet comprises:

detecting whether a “

time to live”

field has expired.

27. The system according to claim 26, wherein the requested action comprises:

extracting a payload of the packet; and

sending the payload to a destination via the Internet.

28. The system according to claim 26, wherein the requested action comprises:

extracting a payload of the packet; and

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

29. The system according to claim 25, wherein the comparison of information at the current node with the packet comprises:

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

, if the current node is capable of the requested action,

taking the requested action.

30. The system according to claim 23, wherein determining whether the packet is intended for the current node comprises satisfying a condition represented in the packet.

31. The system according to claim 30, wherein the condition represented in the packet comprises the existence of a WAN connection at said node.

32. The system according to claim 30, wherein the condition represented in the packet comprises the condition that a measured sensor value at the current node is within a preselected range.

33. The system according to claim 22,

wherein a payload of the packet is combined with a second payload to make a combined payload that is part of a combined-payload packet;

and

wherein the combined-payload packet is transmitted from the current node along an outgoing directional link of the zero or more outgoing directional links of the packet-associated digraph.

34. The system according to claim 22,

wherein a payloads of the packet is compressed to make a compressed payload that is part of a compressed-payload packet;

and

wherein the compressed-payload packet is transmitted from the current node along an outgoing directional link of the zero or more outgoing directional links of the packet-associated digraph.