Techniques for enabling the efficient operation of arbitrarily interconnected mesh networks

• US 10,505,845 B2
• Filed: 01/31/2015
• Issued: 12/10/2019
• Est. Priority Date: 07/21/2005
• Status: Active Grant

• Current Assignee: FireTide Incorporated (UNICOM Global, Inc.)
• Original Assignee: FireTide Incorporated (UNICOM Global, Inc.)
• Inventors: Jetcheva, Jorjeta Gueorguieva, Kailas, Sivakumar, Natarajan, Mohan
• Primary Examiner(s): Tran, Phuc H
• Application Number:
  US14/611,212
• Publication Number:
  US 20150381489A1
• Time in Patent Office: 1,774 Days
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/122 by minimising distances, e.g. by selecting a route with minimum of number of hops
• CPC Class Codes: H04L 45/124 using a combination of metrics
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04L 45/32 Flooding denial of service attacks H04L63/1458
• CPC Class Codes: H04L 45/74 Address processing for routing
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

Wireless mesh networks (or “meshes”) are enabled for arbitrary interconnection to each other and may provide varying levels of coverage and redundancy as desired. Interoperability between meshes having differing configurations, internal operations, or both, may be freely intermixed and inter-operated in unrestricted combination. Enhanced explicit inter-bridge control protocols operate using pre-existing control packets. Pre-existing broadcast packet floods are used to learn the best paths across interconnected meshes (termed a “multi-mesh”). Enhanced routing protocols operating within each mesh may optionally examine information limited to the respective mesh when forwarding traffic, thus enabling robust multi-mesh scaling with respect to memory and processing time required by the routing protocols. Using assigned identifiers, forwarding loops are prevented, and optionally redundant broadcast flooding is prevented.

Claims

1. A method comprising:

passing packets between first and second wireless mesh networks, at least in part via first and second mesh bridge nodes respectively associated with and respectively coupled to the first and the second wireless mesh networks, to form a multi-mesh network;

preventing forwarding loops between the wireless mesh networks, the preventing forwarding loops being performed at least in part via one or more of the mesh bridge nodes; and

wherein the preventing forwarding loops is via duplicate detection based in part on identifiers assigned to respective ones of at least some of the packets, each respective identifier comprising a respective first portion and a respective second portion, the respective first portion uniquely identifying a respective entry point of the respective packet into the multi-mesh network, and the respective second portion uniquely identifying each respective packet in a context of the respective entry point.

2. The method of claim 1, wherein the identifiers are comprised in pre-existing control packets.

3. The method of claim 1, wherein the identifiers are comprised in pre-existing data packets.

4. The method of claim 1, further comprising

accumulating route cost information at least in part during the passing packets, the accumulating route cost information being performed at least in part via the mesh bridge nodes, the accumulated route cost information corresponding to a cost of forwarding a respective packet through each wireless mesh network the respective packet has traversed up to an update of the accumulated route cost information, the accumulating route cost information comprising stripping route cost information specific to a just-traversed wireless mesh network from the respective packet and appending to the respective packet respective route cost information for the just-traversed wireless mesh network;

and

forwarding at least some of the packets, at least in part via the mesh bridge nodes, according to efficient routes based at least in part on the accumulated route cost information.

5. The method of claim 4, wherein the accumulating route cost information is performed at least in part during bridge link traversal.

6. The method of claim 4, wherein the accumulating route cost information is performed at least in part during traversal of at least one of the wireless mesh networks.

7. The method of claim 1, further comprising eliminating redundant broadcast packet flooding within each respective wireless mesh network, the eliminating redundant broadcast packet flooding being performed at least in part via one or more of the mesh bridge nodes.

8. The method of claim 7, wherein the eliminating redundant broadcast packet flooding is based in part on the identifiers.

9. The method of claim 8, wherein the identifiers are comprised in pre-existing control packets.

10. The method of claim 8, wherein the identifiers are comprised in pre-existing data packets.

11. A system comprising:

a processing element coupled to a memory;

a wireless interface enabling wireless communication with a plurality of nodes of a first wireless mesh network and at least partially enabling operation of the system as a first bridge node with respect to the first wireless mesh network;

a communication interface enabling communication via a bridge link to a second bridge node coupled to a second wireless mesh network;

wherein the first and the second bridge nodes are respectively enabled to couple to the first and the second wireless mesh networks;

wherein the processing element is enabled to execute instructions fetched from the memory and enabling functions comprising

passing packets between the first and the second wireless mesh networks, at least in part via the bridge link, to form a multi-mesh network, and

preventing forwarding loops between the wireless mesh networks; and

wherein the preventing of forwarding loops is via duplicate detection based in part on identifiers assigned to respective ones of at least some of the packets, each respective identifier comprising a respective first portion and a respective second portion, the respective first portion uniquely identifying a respective entry point of the respective packet into one of the wireless mesh networks, and the respective second portion uniquely identifying each respective packet in a context of the respective entry point.

12. The system of claim 11, wherein the identifiers are comprised in pre-existing control packets.

13. The system of claim 11, wherein the identifiers are comprised in pre-existing data packets.

14. The system of claim 11, wherein the functions further comprise

accumulating route cost information at least in part during the passing packets, the accumulated route cost information corresponding to a cost of forwarding a respective packet through each wireless mesh network the respective packet has traversed up to an update of the accumulated route cost information, the accumulating route cost information comprising stripping route cost information specific to a just-traversed wireless mesh network from the respective packet and appending to the respective packet respective route cost information for the just-traversed wireless mesh network;

and

forwarding at least a portion of the packets according to efficient routes based at least in part on the accumulated route cost information.

15. The system of claim 11, wherein the functions further comprise eliminating redundant broadcast packet flooding within each respective wireless mesh network.

16. The system of claim 15, wherein the eliminating redundant broadcast packet flooding is based in part on the identifiers.

17. A system comprising:

means for passing packets between first and second wireless mesh networks, operable at least in part via first and second mesh bridge nodes respectively associated with and respectively coupled to the first and the second wireless mesh networks, to form a multi-mesh network, the first and the second mesh bridge nodes being connected to each other via a bridge link;

means for preventing forwarding loops between the wireless mesh networks, operable at least in part via one or more of the mesh bridge nodes; and

wherein the means for preventing forwarding loops operates via duplicate detection based in part on identifiers assigned to respective ones of at least some of the packets, each respective identifier comprising a respective first portion and a respective second portion, the respective first portion uniquely identifying a respective entry point of the respective packet into the multi-mesh network, and the respective second portion uniquely identifying each respective packet in a context of the respective entry point.

18. The system of claim 17, further comprising

means for accumulating route cost information at least in part during the passing packets, the means for accumulating route cost information operable at least in part via the mesh bridge nodes, the accumulated route cost information corresponding to a cost of forwarding a respective packet through each wireless mesh network the respective packet has traversed up to an update of the accumulated route cost information, the means for accumulating route cost information comprising means for stripping route cost information specific to a just-traversed wireless mesh network from the respective packet and means for appending to the respective packet respective route cost information for the just-traversed wireless mesh network;

and

means for forwarding at least some of the packets, at least in part via the mesh bridge nodes, according to efficient routes based at least in part on the accumulated route cost information.

19. The system of claim 17, further comprising means for eliminating redundant broadcast packet flooding within each respective wireless mesh network, the means for eliminating redundant broadcast packet flooding operable at least in part via one or more of the mesh bridge nodes.

20. The system of claim 19, wherein the means for eliminating redundant broadcast packet flooding operates based in part on the identifiers.