Island topologies and routing in hybrid mesh networks

Island topology and routing in a hybrid mesh network

[0001] CROSS-REFERENCE TO RELATED APPLICATIONS

[0002] This application claims the benefits of U.S. Provisional Application No. 62/450,350 filed on January 25, 2017, which is incorporated herein by reference as if it were fully described.

Background technique

[0003] Hybrid mesh networks are being used to expand coverage areas, provide better coverage areas with fewer dead spots, improve throughput and reliability, and so on. Hybrid mesh networks also provide diverse networks by combining different wired and wireless interfaces between access points (APs), gateways, routers, nodes, client devices, etc. Dedicated protocols for discovery, formation, routing, and learning algorithms are required for the rapid and automatic construction and maintenance of reliable hybrid mesh networks.

Summary of the invention

[0004] An island or cluster can be formed in a hybrid mesh network, where nodes utilize different wired or wireless interfaces. Protocols can be used to divide the hybrid mesh network into mesh islands or clusters to reduce interruptions, interference, etc. Once the island or cluster topology is formed, the best route or path from the source node in the hybrid mesh network to any destination node can be utilized that minimizes or meets the target metric or path cost.

Description of the drawings

[0005] A more detailed understanding can be obtained from the following description given by way of example in conjunction with the accompanying drawings, in which similar reference numerals in the accompanying drawings indicate similar elements, and among them:

[0006] FIG. 1 is a diagram showing an example of an access point (AP), router, gateway, or node;

[0007] FIG. 2 is a diagram showing an exemplary topology of a mesh network;

[0008] FIG. 3 is a diagram showing an exemplary topology of a mesh network with islands;

[0009] FIG. 4 is a schematic diagram showing an exemplary mesh island network with an island head;

[0010] FIG. 5 is a schematic diagram showing an exemplary topology with an Ethernet loop;

[0011] FIG. 6 is a diagram showing an exemplary topology with an access point (AP) and/or router island head using Ethernet;

[0012] FIG. 7 is a diagram showing an example of routing in a mesh network;

[0013] FIG. 8 is a diagram showing an exemplary routing process in a mesh network;

[0014] FIG. 9 is a diagram showing an exemplary process of hell o message processing;

[0015] FIG. 10 is a diagram showing an exemplary process for an announce message processing;

[0016] FIG. 11 is a diagram showing an exemplary process of peer learning;

[0017] FIG. 12 is a schematic diagram showing another exemplary process for peer learning;

[0018] FIG. 13 is a diagram showing an exemplary process of interface blocking related to post-routing;

[0019] FIG. 14 is a diagram showing an exemplary process of interface blocking related to a local-in operation; [0020] FIG. 15 is a diagram showing an interface related to a local-out operation A diagram of an exemplary process of blocking; [0021] FIG. 16 is a diagram showing an exemplary process for routing; and

[0022] FIG. 17 is a diagram showing an example of a procedure of protocol message processing through recalculation of a routing path and update of a routing table.

Detailed ways

[0023] In the examples given herein, it is possible to communicate, signal, transmit, or provide information in an island or cluster of a hybrid mesh network. Although reference is made to a hybrid mesh network, examples of island formation, routing, interference management, topology, etc. can be utilized, configured, or adapted to any mesh network that employs two or more communication interfaces. And, in the examples given in this article, packet, flow, part of flow, or frame can be used interchangeably.

[0024] Although any protocol or communication layer, sub-layer, partial layer, part of a layer, part of a layer, etc. can be utilized, this article gives an example of using layer 2 to form a topology or network. In addition, the layer 2 may include a sub-layer, a partial layer, a part of a layer, and the like. The routing algorithms for hybrid mesh networks can include 802.11xx (for example, 802.11ac, 802.11ax, etc.), Wi-Fi, Ethernet, power-line communication (PLC), and multimedia over coax (multimedia over coax). Alliance, MoCA), personal area network (PAN), small cell, metropolitan area network (MAN), and wide area network (WAN) network interface or link in any combination of nodes.

[0025] The nodes in a mesh network can be divided into mesh islands, which are connected or coupled to each other through 802.11xx, Wi-Fi, Ethernet, PLC, and/or MoCA links of commercial devices in the network. Commercial equipment may be home network equipment, wireless routers, routers, wireless gateways, gateways, range extenders, wireless bridges, network bridges, wireless switches, switches, Ethernet switches, etc. In addition to preventing or reducing possible mutual interference between the mesh routing algorithm and the "learning" process of commercial equipment, examples of reducing overall wireless interference are also given. For example, this interference can be reduced by configuring or operating mesh islands on non-interfering wireless channels or resources.

[0026] In the example given herein, for the identified island head or cluster gateway, mesh nodes can be assigned to the island so that the path overhead to the island head can be reduced, minimized or optimized. Once the island topology is formed, the best or optimal route from any source node to any destination node in the mesh network can be determined, thereby reducing, minimizing or optimizing the path cost.

[0027] Using multiple 802.11xx access points (APs) and/or routers with meshing can improve or expand the wireless coverage area, connection speed or throughput in the network. APs and/or routers can form a mesh network topology , And collaborate to distribute data from or to wireless clients or other nodes.

[0028] FIG. 1 is a diagram showing an example of an AP, router, gateway, or node 100. MP, router, gateway, or node 100 may include one or more processors/controllers 102 that utilize ( A plurality of) memories 104 are used to process the hells communicating with one or more wireless/wired interfaces 106. Message^announce message, routing information, etc., as given in the example in this article. The AP, router, gateway, or node 100 may include one or more power supplies 108.

[0029] The one or more processors/controllers 102 may be general-purpose processors, special-purpose processors, conventional processors, digital signal processors (DSP), multiple microprocessors, one or more and Microprocessors, controllers, microcontrollers, ASICs (Application Specific Integrated Circuits, ASICs), Field Programmable Gate Arrays (FPGAs) associated with DSP cores, and any other types of integrated circuits ( integrated circuit, IC), state machine, etc. The memory(s) 104 may include read only memory (ROM), random access memory (random access memory, RAM), registers, cache memory, semiconductor memory devices, flash memory, such as internal hard disks and removable disks Magnetic media, magneto-optical media

One or more of optical media, etc. The one or more wireless/wired interfaces 106 may include one or more transceivers, transmitters, receivers, amplifiers, signal converters, antennas, etc., to facilitate networking.

[0030] The examples given herein are automatic settings, and management and reduction of maintenance of network equipment (such as commercial equipment) to enhance or simplify usability. For example, when the system requirements are reduced to a basic set and a mesh network is formed in the presence of an Internet gateway (which also specifies a mesh network configuration), complexity can be avoided. Moreover, when the device drivers and low-level software libraries provided by the chip supplier may need to be modified or cannot be updated, the examples given in this article may simplify software maintenance, version upgrades may be smoother, and may be faster Add mesh support to commercial gateways.

[0031] A method for automatic configuration and maintenance of a gateway-centric Wi-Fi mesh network is described in US provisional patent application 62/448,718 filed on January 25, 2017. The provisional application passed The citation is incorporated here as if it were fully stated. APs or routers forming a mesh network can be paired with gateway devices by simply pressing a button. The initial network or system configuration information and/or any subsequent changes required by the gateway device can be automatically propagated to the entire mesh network with little or no user intervention. The replacement of the gateway device of the mesh network or the pairing of the AP and/or router with another gateway device can also be handled automatically by a simple button press. In addition, when any node in the mesh network detects a radar signal, the operation channel(s) of the mesh network can be changed automatically.

[0032] This article gives an example of the configuration and/or process of forming mesh islands and routing of traffic (such as layer 2 traffic) between mesh nodes based on path cost. This can be performed and desired after a mesh node is paired with another mesh node and basic network configuration information is shared by the mesh node, such as a network service set identifier (SSID), operating channel, and pass phrase. The routing algorithm and island formation algorithm of the hybrid mesh network can be as described in the U.S. Patent Application Serial No. 14/166,040 issued on August 30, 2016, such as U.S. Patent No. 9,432,990, and the U.S. filed on December 23, 2015. It is implemented as given in the patent application serial number 14/757,422, which are incorporated herein by reference, as if fully explained.

[0033] In the example given herein, once the encrypted link between the mesh nodes is established, the layer 2 routing protocol can be executed. Finding the best, good, or optimal route between mesh nodes may require mesh network topology information. Topology discovery can be accomplished by exchanging messages (such as hello or announce messages) °hello messages can enable nodes to discover neighbors or nearby nodes, and therefore establish and maintain neighbor relationships. Announce messages can spread network topology information throughout the mesh network .

[0034] In an example, certain messaging (messaging) may be processed by a customized or optimized layer 2 transmission module using a customized EtherType field. The layer 2 transport protocol can provide reliable, orderly, segmented, and/or error-checking delivery services of packets, traffic, part of traffic, or frames between nodes of a mesh network. For some configurations, the message type and sequence number can be used to confirm the message. If the expected acknowledgment is not received, the message can be resent within the maximum retry count. Although any maximum retry count can be configured, a retry count 4 using delay schemes such as 1, 2, 3, and 5 seconds can be utilized or configured. The fragmentation size can be configured based on the maximum transmission unit (MTU) size of the medium.

[0035] The optimized transmission module can also provide general communication services between software modules running on mesh nodes. Higher-level applications can use the service through a public payload application programming interface (Application Programming Interface, API). Applications can bind to payload IDs ranging from 0 to 255, for example, and send and receive encrypted and authenticated payloads facilitated by cryptographic encryption and authentication algorithms. These algorithms can be included in the user space library. In addition, each payload can be encrypted by a user-supplied key and/or a globally unique random number. A random number length such as 128 bits or any other length can be used.

[0036] The message type of the hello or announce message may be indicated by a field in a message header. The sequence number in the message header can be delivered in an orderly manner, and the hash-based message authentication code (HMAC) field can provide data integrity and authentication. Messages larger than the configured MTU size may be fragmented. Fragmentation can be performed using the fragment number field in the message header and reassembled by the receiver.

[0037] In the example given herein, the message content can be encoded as a type-length-value (typelength-value, TLV) element within the message body. The element value field can be any size, such as 256 bytes. However, larger elements can be sent in blocks (such as 256 bytes) and then reassembled by the receiver. Examples of TLV elements that may be included in the hello and announce messages are listed in Table 1 and Table 2, respectively.

[0038]

[0039] Node ID Node Media Access Control (Medium Access Control, MAC) address Node Capability Interface ID Interface MAC Address Interface Type Table 1: hello message

<td>Message sign</td>

<td>Node ID</td>

<td>Node Media Access Control (MAC) address</td>

<td>Node capacity</td>

<td>Node lifetime</td>

<td>Node sequence</td>

<td>Interface ID</td>

<td>Interface MAC address</td>

<td>Interface Type</td>

<td>Interface metrics</td>

<td>Peer ID</td>

<td>Peer MAC address</td>

<td>Peer flag</td>

[0041] Table 2: Announce message

[0042] In the example given herein, a mesh node may have multiple network interfaces, such as 802.11xx, Wi-Fi, Ethernet, PLC, and/or MoCA (for clients and mesh peers). A separate hello message can be broadcast by the node on each configured network interface. The interface type element in the ohello message can indicate the type of a specific interface. The ohello message can enable nodes to discover their neighbors and the interface being used. The ohello message can be, for example, every 1T0 seconds. Broadcast on 802.11xx, Wi-Fi> Ethernet, PLC and/or MoCA and wireless distribution system (WDS) links.

[0043] In some exemplary configurations, a node that receives a hello message through a WDS link can initialize a sending peer in a blocked state, and advertise this information to the network. The hello message count can be used for network management WDS links . On Ethernet, PLC, and/or MoCA links, the sending node can be initialized as an unblocked peer. The peer status information can be carried in the peer flag element of the announce message. When the peer is in a blocking state, protocol messages, data packets, traffic, part of traffic, or frames other than hello may not be processed.

[0044] The receiving node may also refresh the learned peer information of a given receiving interface. This refresh may be desirable for dividing the network into mesh islands. After receiving, for example, 10 hello messages from the peer, the operation of transitioning to the non-blocking state can be performed and notified to the network. The time required to unblock the peer may depend on the configuration

The hello cycle is set.

[0045] The mesh node can propagate network topology information by sending periodic announce messages to non-blocked hello peers. This announcement message can be used in particular for Ethernet, PLC, MoCA or WDS links. You can send an announce message when the topology changes to quickly respond to the topology changes.

[0046] In the example given herein, the notification period can be configured to any value from 0 to infinite seconds (for example, every 30 seconds). Configure the interval to zero to disable periodic notifications. For this configuration, notifications can be sent or triggered when the topology, nodes, links, etc. change, instead of being sent periodically. In addition, the announce message can be unicast. For unicast, the message can be confirmed by the receiver and forwarded. The forwarded message can be terminated with the help of the message sequence number.

[0047] The node receiving the announce message can update the mesh network node and routing table when any changes are made. In some configurations, the receiving node may only forward the announce message when the network information changes. The general communication service provided by the transmission module can be carried on the announce message for applications that can tolerate a delay equal to at most the announcement period.

[0048] The node may periodically check the node list to ensure that old, outdated, outdated, etc. information is removed. For example, if a node is idle for more than 120 seconds, it may fail. The learning peer can be deleted if it is idle for more than 300 seconds, for example. The idle expiration time can be configured according to the value of the announcement period, and preferably should be in the order of several times the announcement period. In either configuration, routing can be updated and event-based notifications can be sent. Since the announcement message receiving time can be random, the obsolescence check period can be adjusted according to the trade-off between the computational load and responsiveness of the algorithm.

[0049] Referring again to Table 2, the interface metric field may indicate the transmission overhead from the node to the peer through a given interface. The quality of the link can be assessed by using different cost metrics. There are many examples of calculating the cost metric of a link. Examples can be found in British Patent Application No. GB1700997.8, which is incorporated herein by reference, as if fully explained. Equation (1) gives possible link overhead metrics.

„ 50000

[0050] C 1 + LR/20] Equation (1)

[0051] The overhead metric C may be inversely proportional to the current physical layer transmission rate R (in Kbps) to the peer node. Therefore, faster links may have lower overhead and be preferentially treated. The overhead can also be proportional to the transmission airtime. The link cost metric can be calculated by another software process running on the node and passed to the routing process via the software bus. The best route from any source node to a destination node in a mesh network can be calculated using link cost to minimize the total transmission cost.

[0052] In order to prevent replay attacks, each node may generate a new random number every 30 seconds, for example, to be included in the sent hello message. Each interface that receives the random number of the peer node may include the random number of the peer node and the random number of its own node in its own hello message. If the received hello message does not include the current random number of the receiving node, it may be discarded. The current random number with message integrity provided by HMAC can provide sufficient security for the routing algorithm.

[0053] When traffic flows through a port of a commercial switch (for example, an Ethernet switch), the sent frame can be inspected by the attached node and the source media access control (MAC) address is recorded. The switch can therefore build a table of MAC addresses and (versus) port numbers, and "learn" the location or existence of the MAC destination. In some configurations or examples given in this article, the switch can directly forward the received frame to the correct port without flooding or broadcasting on all ports.

[0054] FIG. 2 is a diagram illustrating an exemplary topology 200 of a mesh network. Wireless links 214.212 and 216 can connect or couple STA1, STA2 and STA3 to AP1, respectively. AP2 and AP3° STA can be mobile devices, sensors, and the Internet of Things

(Internet of thing, IoT) devices, laptops, laptops, tablets, smart phones, televisions, monitors, wireless audio devices, wireless speakers, etc.AP2 and AP3 can be connected to the switch using wired links 202 or 206 ( For example, Ethernet switch) oAP1 can be connected to both AP2 and AP3 via WDS link 208 or 210, respectively. STA4 can be connected or coupled to the switch via wired link 204.

[0055] In some configurations, the WDS link 208 between AP1 and AP2 may have a smaller or desired overhead compared to the overhead of the WDS link 210 between AP1 and AP3. Due to the physical proximity, the link overhead may be lower, allowing higher data rates or throughput due to higher signal strength or signal to noise ratio (SNR). If STA1 has data to send to STA4, the mesh routing algorithm can use the path STALAPL AP2 to STA4 due to the low overhead. In topology 200, data packets or frames originating from STA1 can enter the switch on its port x. Correspondingly, the switch can "learn" that STA 1 is reachable through port x from the source MAC address of these packets or frames. Therefore, when STA4 attempts to send data to STA1, the switch can forward these data packets or frames to ports y and x.

[0056] The overhead of the wireless link may change over time, and the overhead may be asymmetric. For example, AP1 may move closer to AP3, or a strong interference source may appear near AP2. In addition, the overhead of the link AP1-AP2 may be lower than the overhead of APLAP3, and the overhead of AP3-AP1 may be lower than the overhead of AP2-AP1. In this case, using AP3-AP1 link instead of AP2-AP1 link may be more advantageous. MP3-AP1 link may also be preferred for better quality of service (QoS) or improved load balancing .

[0057] If the link 208 between AP2 and AP1 is temporarily interrupted or unavailable, the switch can still try to use the link 202 to send packets or frames destined for STA4 to port x. Even if the link 210 between AP3 and AP1 can be used to carry information to the destination, these packets or frames may be lost. In the example given in this article, when the learning process of the switch operates independently of the mesh routing algorithm run by the AP, conflicts can be avoided.

[0058] In addition, for load balancing or QoS purposes, multiple paths can be utilized at the same time. For example, AP 1 can send a packet or frame through AP2, and send the next one through AP3. However, frequent path changes may complicate or confuse the learning process of the switch. For example, STA 1 seems to move quickly between port x and port z. When multiple paths are utilized, the internal routing table updates of the switch may not be able to keep up, resulting in dropped packets or frames or unpredictable forwarding decisions.

[0059] Commercial switches can run Spanning Tree Protocol (STP) to prevent the formation of network loops. However, switch ports blocked by STP may interfere with mesh routing protocols and block routing protocol messages from reaching their destinations. To avoid this scenario, when two or more mesh nodes are connected via switches, the mesh network can be divided into mesh islands or clusters. Nodes connected via switches can become island heads, cluster gateways, or gateways between mesh islands.

[0060] In some configurations, commercial PLC devices in the mesh network can keep their own MAC address tables and run their own MAC layer routing and repetition algorithms, which may interfere with the mesh network routing. Therefore, when two or more mesh nodes are connected via commercial PLC equipment, the mesh network can also be divided into islands. The PLC network interface of the mesh node can be controlled by the routing algorithm given in this article, and therefore it may not be necessary to consider the partition separator.

[0061] It may also be desirable to divide the mesh network into islands so that each island operates on a different channel or resource, thereby reducing interference with other islands within the transmission and/or interference range. This can reduce the broadcast collision domain and increase the available talk time of active mesh nodes. In addition, dividing the mesh network into smaller mesh islands can alleviate the multi-hop unfairness observed in other or larger wireless mesh network configurations.

[0062] FIG. 3 is a diagram showing an exemplary topology of a mesh network with islands. The topology or graph 300 may be a mesh network in which AP1 and AP2 are connected or coupled using a wired link 302 (eg, Ethernet). WDS link 304.306 or 308 can

Used for meshing APi, AP2 and AP3. Since there is a wired link 302 between AP1 and AP2, AP1 can be identified or designated as the island head.

[0063] By using the wired link 314 and the WDS link 316, two mesh islands 310 and 312 can be formed around the island heads AP1 and AP2, as shown in the topology or graph 301. The third node AP3 can be assigned to one of the islands, and the wireless links with nodes in other islands are blocked, forbidden, not allowed, forbidden, etc. In the topology or graph 301, the third node AP3 can be allocated to the island of the node AP1 because the WDS link 316 to AP1 can have a lower overhead, and the wireless link to the node AP2 is removed. In addition, the AP or router may have multiple interfaces (for example, Ethernet), which are part of the embedded switch. Therefore, in the topology or graph 301, the interfaces of two wireless APs or routers can be connected via a switch or directly via wires or cables.

[0064] FIG. 4 is a diagram showing an exemplary mesh island network 400 with island heads. When the announce message propagates the topology map information throughout the mesh network, the nodes may have the necessary information to separate the mesh nodes into islands (402). A node that can be the head of the island can be found or identified (404). If a node has a hello peer on any Ethernet, PLC, and/or MoCA interface, it may be marked as an island head. Therefore, the number of mesh nodes as island heads can be equal to the number of mesh nodes with Ethernet, plc, and/or MoCA peers.

[0065] In order to form a mesh island network with island heads, wireless data connections between nodes in different islands may be blocked, forbidden, not allowed, forbidden, etc., and a large number or all of the island division possibilities can be calculated , And you can choose a partition scheme that minimizes metrics (such as link overhead). The possible metric can be the maximum cost from a node to the nearest island head, or the sum of the costs from all nodes in a given island to its head.

[0066] Considering that as the number of mesh nodes increases, a large number or all of the possibilities may quickly become computationally intensive, especially when the network topology changes and the routing algorithm is expected to respond quickly. Iterative algorithms can be used to approximate the optimal solution. After the mesh island head is determined, the wireless data link between the island heads may be blocked, disabled, not allowed, or forbidden. [0067] The node that is the hello peer of at least one island head can be determined, and the minimum path cost of each of the island heads can be calculated. In addition, other possible metrics can be the sum of the cost of all nodes from the island to the head of the island, or the maximum cost of the island to the head of the island. The minimum or shortest path between nodes in a mesh network can be determined by using any deterministic algorithm (such as the Dijkstra algorithm or the Bellman-Ford algorithm).

[0068] Once the node with the least path cost in the group is identified, it can be assigned to the corresponding island head. This process can continue to form an initial node group, which is the hello peer of the island head. Then, the wireless link that may exist between the node and any of the other island heads can be blocked, disabled, not allowed, prohibited, etc. The remaining nodes in the initial group can then be considered, and their minimum path costs to each of the island heads can be recalculated. Any wireless data links that may exist between the node and any other islands may also be blocked. This can be repeated until all remaining nodes in the initial group are assigned to islands.

[0069] The second group may include orphan nodes (406), which are hello peers of at least one node in the first group. Orphan nodes can be unassigned nodes in any group. The nodes in the second group can be allocated (408) to the islands using the algorithm presented herein. Recalculate the minimum path cost to the island head, and in each step, the node with the least minimum path cost is assigned to the corresponding island, and its wireless links to other islands are blocked, disabled, not allowed, prohibited, etc. Until all nodes in the second group are assigned to islands. This can be repeated until all nodes in the network are assigned to islands.

[0070] FIG. 5 is a diagram showing an exemplary topology 500 having an Ethernet loop due to configuration errors, glitches, etc. The loop created by wired links 502.504 and 506 between the switch, AP1 and AP2 may cause broadcast storms. although

STP can prevent this kind of loop, but in the example given in this article, it can be avoided in a mesh network. For example, the root node can track the hello peer of the node to prevent such loops.

[0071] In the example given in this article, any node can be selected, and only relevant hello peers are considered. Each of these peers and its hello peer can be viewed in the remaining nodes. In a given iteration, if the starting node is reached, the loop in the topology can be identified. This kind of loop can be broken by blocking, prohibiting, disallowing, prohibiting, etc., one of the links in the chain. For example, you can determine the link to be blocked by selecting the link with the slowest connection speed. Another way is to block the link so that the resulting topology minimizes the maximum number of hops to the gateway of the mesh network. The path cost can be considered or calculated, such as using equation (1), and the maximum cost among the loop nodes to the mesh gateway is minimized. If the gateway is unknown, you can try to minimize the maximum number of hops or the maximum path cost between any two nodes in the loop.

[0072] FIG. 6 is a diagram showing an exemplary topology 600 with AP and/or router island heads using Ethernet. For this topology, AP1, AP2, AP3, and AP4 can be configured as island heads because they can have Ethernet hello peers that span links 602, 604, and 610. For some configurations, the island separation or division algorithm can block, disable, disallow, or prohibit wireless connections between different islands. However, this may cause a disconnection between islands 612 and 614. Without the wireless link 606 or 608, AP1 will only connect to AP2, and AP3 will only connect to AP4. Therefore, there is no connection between islands 612 and 614. To prevent possible disconnection between islands, the wireless link can be restored to obtain a fully connected topology. However, the two island heads connected to the wireless link may have to operate on the same wireless channel or resource, resulting in potential interference.

[0073] The root node of the mesh network can be selected based on the node ID and the node MAC address to prevent undesired network configuration or architecture. For example, the node with the smallest node ID and MAC address combination can be selected. The root node can check the disconnected cluster after identifying the island head and determine which wireless links should be restored to form a fully connected graph. A suitable metric may be, for example, the maximum path cost between all nodes to a mesh gateway, or the maximum path cost between any two mesh nodes if the gateway is not known.

[0074] FIG. 7 is a diagram showing an example of a route 700 in a mesh network. The incoming and outgoing packets, traffic, part of the traffic or frames on each interface can be filtered for mesh routing, peer learning, protocol message processing, etc. Traffic 702 from the network interface can be input for pre-routing. Pre-routing may be triggered by incoming traffic from any network interface after entering the network stack. Once triggered, any routing decision may be aborted.

[0075] Traffic from the pre-routing output 704 may be communicated for further routing. Traffic from the routing output 706 can be communicated to the local input component for output 708 to local processing. Traffic from the local processing input 712 may be communicated to the local output component for processing. Traffic from the local output 710 can be communicated for further routing. Traffic from routing output 714 can be communicated for post-routing. Traffic from the post-routing output 716 can be communicated to the network interface.

[0076] Pre-routing, local input, local output, and post-routing may be operations related to the operating system or the protocol of the operating system kernel or packet filtering in the network stack. Packets or frames entering the network system can trigger these hooks as they progress through the stack, thereby allowing programs or applications registered with these hooks to interact at different points in the process. Soon after entering the network stack, any incoming traffic may trigger the pre-routing hook. This hook can be processed before making a routing decision about where to send the packet or frame. If the destination of the packet or frame is the local system, the local input hook may be triggered after the incoming packet or frame is routed. Soon after reaching the network stack, any locally created outbound traffic may trigger the local output hook. Post-routing hooks can be triggered by any outgoing traffic after routing occurs and just before communication or signaling on the network interface.

[0077] For example, Linux network filter (Netfilter) operations for pre-routing, local input, local output, and post-routing can be used to determine whether a packet or frame will be accepted, discarded, or passed to the routing process. Protocol message processing can include forwarding announce messages, updating routing tables, invalidating nodes, deleting known peers, and so on.

[0078] FIG. 8 is a diagram illustrating an exemplary routing process 800 in a mesh network. Once the pre-routing (802) is initialized at the node(s), a determination or check is made whether the received packet is a hello message (804). As an example, a custom Ethernet type with a hell o message type in the packet or frame header can be used to identify the hell o message. If a hello message is recognized, the hello message is processed (804) and then discarded (806).

[0079] If the received packet is not a hell o message, a determination or check is made whether the received packet is an announce message (810). As an example, a custom Ethernet type with an announce message type in the packet or frame header can be used to identify the announce message. If an announce message is recognized, the announce message is processed (812) and then discarded (806). If the received packet is not an announce message, peer learning (814) and subsequent routing (816) are performed.

[0080] FIG. 9 is a diagram illustrating an exemplary process 900 for hello message processing. After initializing or processing the hello message (902) at the node(s), the existence of the peer is determined (904). If the peer exists, a determination is made whether the peer is blocked (906). If the peer is blocked, determine the reception of traffic on the WDS (908) and check whether the hello count is higher than the limit (910). If hell. If the count is higher than the limit, the peer is unblocked (912), the announce message is sent (914) to the unblocked hello peer, and the process is stopped (916).

[0081] If the peer does not exist, create a blocked peer (918), refresh the learned peer (920), send an announce message to the non-blocked hello peer (914), and the process is changed Stop (916). If the peer is not blocked, the idle time of the peer can be updated (922), and the process is stopped (916). Furthermore, if no WDS traffic is received, the peer is unblocked (912), and the process 900 proceeds as presented herein. And, if the hello count is lower than the limit, the process is stopped (916).

[0082] FIG. 10 is a diagram illustrating an exemplary process 1000 for announce message processing. After initializing or processing the announce message (1002) at the node(s), a determination of the topology change is made (1004). If the topology changes, the routing update is processed (1006), and the announce message is forwarded (1008) to the node peers to propagate the topology information. If the topology is the same or unchanged, the process is stopped (1010).

[0083] FIG. 11 is a schematic diagram illustrating an exemplary process 1100 for peer learning. Peer learning can be the process or operation of discovering devices that are not mesh nodes. In peer learning, the mesh topology can be propagated via the announce message, so that each node discovers information about each other node and its connections or interfaces. However, in some peer learning configurations, commercial devices that are not configured to be meshed will not send announce messages. And an example of this kind of device "learning" the network topology is given.

[0084] Process 1100 may be performed as part of a pre-routing operation. After initializing the peer learning operation (1102) at the node(s), a determination is made that the interface is capable of peer learning (1104). If capable, a determination is made that the peer has been learned (1106). If the peer has been learned, the process stops (1108). Otherwise, a determination is made that the peer (1110) needs to be learned.

[0085] If learning is not required, the process stops (1108). If learning is needed, the peer is learned (1112), an announce message can be sent (1114) to the unblocked hello peer, and the operation stops (1108).

[0086] FIG. 12 is a schematic diagram illustrating another exemplary process 1200 for peer learning. In some configurations, process 1200 may be performed as part of a pre-routing operation. The mesh node can learn the source MAC address of the interface in the network,

Similar to the learning process of commercial switches (for example, Ethernet switches). An interface (for example, an Ethernet interface) that does not belong to a mesh node and is not a peer of another mesh node may be a candidate for learning. And, if the interface and two mesh nodes are connected to the same switch, both mesh nodes can learn the interface. In some configurations, in order to learn the same interface, the two mesh nodes may need to be hello peers.

[0087] After a determination is made at the node(s) that peer learning is required (1202), a determination is made that the source is a mesh node (1204). If the source is a mesh node, then peer learning may not be needed or performed (1216). If the source is not a mesh node, a determination is made that the interface has a hello peer (1206). If the interface does not have a hello peer, then peer learning can be performed (1214).

[0088] If the interface has a hello peer, a determination is made that the source has a peer of another node (1208). If the source is not a peer of another node, peer learning can be performed (1214). If the source is a peer of another node, a determination is made that the source is on another island (1210). If the source is on another island, peer learning may not be needed or performed (1216).

[0089] If the source is not on another island, a determination is made whether the node and the peer's node are the island head (1212), and if so, peer learning can be performed (1214). If the node and the peer's node are not island heads, then peer learning is not required or performed (1216).

[0090] FIG. 13 is a diagram illustrating an exemplary process 1300 of interface blocking related to post-routing. Post-routing operations can be triggered by outgoing or forwarded traffic after routing has occurred and before any network interface sends out packets or frames. By dropping frames, post-routing can be used for interface blocking, etc. After the routing decision is made and the packet or frame is destined for the non-local device, a post-routing process (1302) can be performed. A determination is made that the interface is blocked (1304). This can be specified as specific to the outgoing interface selected by the routing block for the destination of the packet or frame. If the interface is blocked (1306), the packet, flow, part of the flow, or frame may be dropped (1306). Otherwise, if the interface is not blocked, send packets, traffic, or frames (1308).

[0091] FIG. 14 is a diagram illustrating an exemplary process 1400 of interface blocking related to local input operations. After an incoming packet or frame destined for the local system has been or previously routed, it may trigger the blocking of the interface operated by the local input. If the network interface is blocked, incoming frames may be dropped. In process 1400, after initialization of local input operations (1402) at the node(s), a determination is made that the interface is blocked (1404). If the interface is blocked, the packet, flow, part of the flow, or frame is dropped (1406). Otherwise, the packet, flow, part of the flow, or frame is accepted (1408) for further processing or routing.

[0092] FIG. 15 is a diagram illustrating an exemplary process 1500 of interface blocking related to a local output operation. Any locally created outbound traffic entering the network stack can trigger or perform local output operations. Local output operations can be used to deliver locally generated outgoing packets or frames for routing. In the process 1500, after the initialization of the local output operation (1502), a determination is made (1504) that the interface is blocked. This determination may include the local network interface accepting packets from the local system. If the interface is blocked, the packet, flow, part of the flow, or frame is dropped (1506). Otherwise, the packet, flow, part of the flow, or frame is communicated for further routing (1508).

[0093] When a packet, flow, part of the flow or frame is delivered to the routing process, it can be transmitted to the target or intermediate node on the best or optimal path to the target via the routing table lookup. When needed, the routing table can be updated according to topology changes. For example, when a protocol message indicating the identification of changed or outdated information after the expiration of a periodic timer is received, an update operation may be performed. If there is no entry for the destination address in the routing table, the routing process can queue packets or frames until the routing table is corrected or repaired. As an example, the maximum queue size can be 16 packets, and can

Configure at runtime. The routing process can use the accelerated backend for network transmission.

[0094] As an example, for certain configurations or scenarios, acceleration can refer to 802.11xx or WiFi System on Chip (SoC), which forwards packets or traffic entering the physical interface to the correct destination physical interface without First, the packet or traffic is passed up to the operating system's network stack for further processing. This shortcut or hardware acceleration can provide higher throughput by avoiding the processing time of packets or traffic in the network stack.

[0095] FIG. 16 is a diagram illustrating an exemplary process 1600 for routing. After the initialization of the routing operation (1602) at the node(s), a determination is made that there is an entry in the table (1604). If there is an entry, a determination is made that the traffic is going to the local destination (1606). If the traffic is for a local destination, a local input operation can be performed (1608). If the traffic is not for a local destination, then a determination is made that an interface exists (1616). If there is an interface, acceleration (1618) can be set, and post-routing (1622) can be performed.

[0096] If the table entry does not exist, an entry is created (1610), and a determination is made that the queue is full (1612). Similarly, if the interface does not exist, a determination is made that the queue is full (1612). If the queue is full, the traffic can be dropped (1614). Otherwise, the acceleration (1620) can be cleared and the queuing operation (1624) can be performed.

[0097] FIG. 17 is a diagram showing an example of a procedure 1700 of protocol message processing through recalculation of a routing path and update of a routing table. After the initialization of the routing update (1702) at the node(s), the learned peers can be verified (1704). In this process, invalid learned peers or peers that should not be learned may be deleted. The exchanged peer can be handled by deleting any peer node that has been disconnected and then connected to some other node (1706). The island graph can be constructed based on the peer-to-peer connection topology (1708). In the island map, blocked peer-to-peer connections between islands can be marked.

[0098] A routing graph (1710) may be constructed by nodes, interfaces, and/or peers based on the connection topology and island settings. It is possible to construct a reverse routing graph (1712) for nodes only. The reverse graph can be used for node verification and can enable the network to dynamically or quickly respond to topology changes. The disappearance of nodes may cause topology changes. The reverse graph can be checked to verify the node connectivity of the node (1714), and the disappeared node can be marked as invalid. The verification of the hello peer can be performed by marking the peer in the blocking hello state as invalid (1716).

[0099] In addition, in process 1700, invalid routes for nodes, interfaces, or peers may be deleted (1718) from the routing table. Blocked routes for nodes, interfaces, or peers can be deleted from the routing table (1720). It can calculate (1722) and populate the routing table for valid nodes, interfaces, and peers. Invalid nodes, interfaces, and peers can be deleted from the topology graph and marked as invalid (1724). Any unnecessary flags of nodes, interfaces, or peers can be cleared (1726).

[0100] Although the features and elements are described above in specific combinations, those of ordinary skill in the art will understand that each feature or element can be used alone or in any combination with other features and elements. In addition, the method described herein can be implemented in a computer program, software, or firmware, which is incorporated into a computer-readable medium to be executed by a computer or a processor. Examples of computer-readable media include electronic signals (transmitted through wired or wireless connections) and computer-readable storage media. Examples of computer-readable storage media include, but are not limited to, read only memory (ROM), random access memory (RAM), registers, cache memory, semiconductor memory devices, magnetic media such as internal hard disks and removable disks, magneto-optical media And optical media such as CDROM (Compact Disc Read-Only Memory) and digital versatile disks (DVD).