Wireless home network routing protocol

• US 10,263,885 B2
• Filed: 09/18/2017
• Issued: 04/16/2019
• Est. Priority Date: 01/23/2009
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Empire Technology Development LLC (Allied Inventors Management, LLC)
• Inventors: Chiang, Mung
• Primary Examiner(s): Elliott, IV, Benjamin H
• Application Number:
  US15/707,572
• Publication Number:
  US 20180006933A1
• Time in Patent Office: 575 Days
• CPC Class Codes: H04L 12/189 in combination with wireless systems selective distribution or broadcast in wireless communication networks H04W4/06
• CPC Class Codes: H04L 12/2834 Switching of information between an external network and a home network access arrangements H04L12/2856
• CPC Class Codes: H04L 12/2838 Distribution of signals within a home automation network, e.g. involving splitting/multiplexing signals to/from different paths adaptations of television systems for transmission by electric cable for domestic distribution H04N7/106; hybrid transport H04L12/6418; home network arrangements specially adapted for distribution of digital video signals H04N7/24
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/64 using an overlay routing layer
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames
• CPC Class Codes: H04W 24/04 Arrangements for maintaining operational condition
• CPC Class Codes: H04W 40/00 Communication routing or communication path finding

Abstract

A hierarchical wireless network is provided with a mesh backbone network portion and a switching tree network portion. The mesh backbone network portion includes first tier nodes each having at least one wireless link to another first tier node. The first tier nodes execute a link-state protocol for routing packets. The switching tree network portion includes second tier nodes each having a single wireless link to one first tier node and at least one wireless link to one third tier node, and third tier nodes each having a single wireless link to one second tier node. The second tier and the third tier nodes execute switching rules for switching packets.

Claims

1. A hierarchical wireless network, comprising:

a mesh backbone network portion that comprises a plurality of first nodes, wherein at least one of the plurality of first nodes is configured to exchange packets with at least another of the plurality of first nodes; and

a tree switching network portion, comprising;

one or more second nodes; and

one or more third nodes, wherein;

at least one of the one or more second nodes is configured to exchange packets with one of the plurality of first nodes,

at least one of the one or more second nodes is configured to exchange packets with at least one of the one or more third nodes,

at least one of the one or more third nodes is configured to exchange packets with one of the one or more second nodes, and

at least one of the one or more second nodes and at least one of the one or more third nodes are configured to;

determine whether a receive buffer is full; and

in response to a determination that the receive buffer is full, discard packets stored in the receive buffer based on respective ages and respective importance levels of the stored packets.

2. The hierarchical wireless network of claim 1, wherein the plurality of first nodes include stationary devices.

3. The hierarchical wireless network of claim 1, wherein the one or more second nodes include one or more stationary devices.

4. The hierarchical wireless network of claim 1, wherein the one or more third nodes include one or more mobile devices.

5. The hierarchical wireless network of claim 1, wherein the plurality of first nodes are configured to receive power from an alternating current (AC) source.

6. The hierarchical wireless network of claim 1, wherein the one or more second nodes and the one or more third nodes are configured to receive power from respective batteries.

7. The hierarchical wireless network of claim 1, wherein each of the plurality of first nodes is configured to execute a link-state protocol to route packets.

8. The hierarchical wireless network of claim 7, wherein the link-state protocol includes one of:

penalizing exponential flow splitting (PEFT) protocol, distributed exponentially weighted flow splitting (DEFT) protocol, and open shortest path first (OSPF) protocol.

9. The hierarchical wireless network of claim 1, wherein each of the one or more second nodes and each of the one or more third nodes are configured to execute switching rules to switch packets.

10. The hierarchical wireless network of claim 1, wherein one of the plurality of first nodes includes a wireless gateway device.

11. The hierarchical wireless network of claim 10, wherein the wireless gateway device includes one of:

a wireless router, a wireless cable modem, and a wireless digital subscriber line (DSL) modem.

12. The hierarchical wireless network of claim 1, wherein two or more of the plurality of first nodes are configured to exchange packets with each other.

13. The hierarchical wireless network of claim 1, wherein each of the one or more second nodes is configured to:

exchange packets with the one of the plurality of first nodes; and

exchange packets with the at least one of the one or more third nodes.

14. A method to establish a hierarchical wireless network, the method comprising:

establishing a mesh backbone network portion of the hierarchical wireless network, wherein establishing the mesh backbone network portion comprises providing a plurality of first nodes, and wherein at least one of the plurality of first nodes is configured to exchange packets with at least another of the plurality of first nodes; and

establishing a tree switching network portion of the hierarchical wireless network, wherein establishing the tree switching network portion of the hierarchical wireless network comprises;

providing one or more second nodes; and

providing one or more third nodes, wherein;

at least one of the one or more second nodes is configured to exchange packets with one of the plurality of first nodes,

at least one of the one or more second nodes is configured to exchange packets with at least one of the one or more third nodes,

at least one of the one or more third nodes is configured to exchange packets with one of the one or more second nodes,

at least one of the one or more second nodes and at least one of the one or more third nodes are configured to;

determine whether a receive buffer is full; and

in response to a determination that the receive buffer is full, discard packets stored in the receive buffer based on respective ages and respective importance levels of the stored packets.

15. The method of claim 14, wherein the plurality of first nodes have a different mobility than the one or more second nodes and the one or more third nodes.

16. The method of claim 14, wherein providing the one or more third nodes comprises providing the one or more third nodes that are operable from a same type of power supply as the one or more second nodes.

17. The method of claim 14, wherein providing the plurality of first nodes comprises providing a node, among the plurality of first nodes, which is configured to operate as a network management node of the hierarchical wireless network.

18. The method of claim 17, wherein to operate as the network management node of the hierarchical wireless network, the node of the plurality of first nodes is configured to:

discover neighbor nodes;

determine a topology of the mesh backbone network portion based on the neighbor nodes;

organize the one or more second nodes and the one or more third nodes into a tree structure;

determine a topology of the hierarchical wireless network based on the topology of the mesh backbone network portion, and the tree structure;

compute a routing table based on the topology of the hierarchical wireless network; and

use the routing table to process incoming packets.

19. The method of claim 18, wherein to operate as the network management node of the hierarchical wireless network, the node of the plurality of first nodes is further configured to:

determine that one of the nodes in the hierarchical wireless network has failed; and

reconstruct the routing table based on the determination.

20. The method claim 14, wherein at least one of the one or more second nodes, and at least one of the one or more third nodes are configured to:

receive a tree structure of the one or more second nodes and the one or more third nodes from a network management node;

construct switching rules based on the tree structure, wherein the switching rules define an ingress link from a parent node, and one or more egress links to one or more child nodes; and

process incoming packets based on the switching rules.

21. A method to establish a hierarchical wireless network, the method comprising:

establishing a mesh backbone network portion of the hierarchical wireless network, wherein establishing the mesh backbone network portion comprises providing a plurality of first tier nodes, wherein at least one of the plurality of first tier nodes is configured to establish at least one wireless link to at least another of the plurality of first tier nodes, and wherein the plurality of first tier nodes include stationary nodes that are operable by an alternating current (AC) power; and

establishing a tree switching network portion of the hierarchical wireless network, wherein establishing the tree switching network portion of the hierarchical wireless network comprises;

providing one or more second tier nodes; and

providing one or more third tier nodes, wherein;

at least one of the one or more second tier nodes is configured to establish a single wireless link to one of the plurality of first tier nodes,

at least one of the one or more second tier nodes is configured to establish at least one wireless link to at least one of the one or more third tier nodes,

at least one of the one or more third tier nodes is configured to establish a single wireless link to one of the one or more second tier nodes, and

the one or more second tier nodes and the one or more third tier nodes include a mobile device that is operable by battery power.

22. The method of claim 21, wherein establishing the tree switching network portion comprises organizing the one or more second tier nodes and the one or more third tier nodes into a tree structure.

23. The method of claim 21, wherein the at least one of the plurality of first tier nodes is configured to execute a link-state protocol to route packets, and wherein at least one of the one or more second tier nodes and at least one of the one or more third tier nodes are configured to execute switching rules to switch packets.

24. The method of claim 21, wherein at least one of the one or more second tier nodes and at least one of the one or more third tier nodes are configured to:

determine whether a receive buffer is full; and

in response to a determination that the receive buffer is full, discard packets stored in the receive buffer based on respective ages and respective importance levels of the stored packets.