Method and system for enabling the efficient operation of arbitrarily interconnected mesh networks

Method and system for effectively operating arbitrary interconnected mesh networks

[0001] This application is a divisional application. The application number of the original application is 200680032343.X, the filing date is July 19, 2006, and the title of the invention is "A method for effectively operating an arbitrary interconnected mesh network with D." .

Technical field

[0002] There is a need to improve routing protocols for bridging networks to provide improvements in performance, efficiency, and utility. The embodiments described elsewhere herein can achieve these improvements.

Background technique

[0003] Unless it is clearly considered to be public or known, the technology and content mentioned in this article should not be construed as an acknowledgement, including those used for context (context, also called context), definition, or comparison purposes. These technologies and contents are previously known or part of existing technologies. All references cited herein, including patents, patent applications, and published publications (if any), regardless of whether they are specifically incorporated or not, are all incorporated herein for all purposes. Nothing in this article shall be construed as an admission that any reference is related to prior art, nor shall it be construed as an admission that it constitutes the content or date of the actual public publication on these documents.

Summary of the invention

[0004] The present invention can be implemented in a variety of ways, including processing, processing articles, equipment, systems, combinations of substances, and computer-readable media (for example, computer-readable storage media or computer networks), wherein, via optical communication Link or electronic communication link to send program instructions. In this context, these embodiments or any other form that the present invention can take may be referred to as technologies. In general, the order of the disclosed processing steps can be changed within the scope of the present invention. The detailed description provides an illustration of one or more embodiments of the invention. The detailed description includes an introduction to help you understand the rest of the detailed description more quickly. The introduction includes exemplary combinations that succinctly summarize exemplary systems and methods based on what is taught herein. As discussed in more detail in the conclusion, the present invention includes all possible improvements and changes within the scope of the submitted claims, which are attached to the end of the submitted patent.

Description of the drawings

[0005] Various embodiments of the present invention are disclosed in the following detailed description and drawings.

[0006] FIG. 1 shows a number of techniques for reducing (or eliminating) loops and for optimizing multi-mesh single-wave packet flow and broadcast packet flow Selected detailed description of the embodiment.

[0007] Figure 2 shows a selected detailed description of the hardware aspects of an embodiment of a node.

[0008] Figure 3 shows a selected detailed description of the software aspects of an embodiment of a node.

Detailed ways

[0009] The present invention can be implemented in a variety of ways, including processing, processing articles, equipment, systems, combinations of substances, and computer-readable media (for example, computer-readable storage media or computer networks), wherein, via an optical communication link Way or electronic communication link to send program instructions. Here, these embodiments or any other that the present invention can adopt

CN 103220748 Β

His form is called technology. Generally speaking, the order of the disclosed processing steps can be changed within the scope of the present invention.

[0010] The following provides a detailed description of one or more embodiments of the present invention and accompanying drawings that illustrate the principles of the present invention. The present invention can be described in conjunction with these embodiments, but the present invention is not limited to any embodiment. The scope of the present invention is limited only by the claims, and the present invention includes many changes, improvements, and equivalents. In the following description, many specific details are clarified in order to provide a thorough understanding of the present invention. These details are provided for the purpose of example, and the present invention can be implemented according to the claims without some or all of these specific details. For the sake of clarity, technical material that is known in the technical fields related to the present invention has not been described in detail so as not to unnecessarily obscure the present invention.

[0011] Introduction

[0012] The introduction is only used to help understand the detailed description more quickly. Any paragraph in the introduction needs to be a concise summary of all the topics, and does not mean an exhaustive description or a restrictive description, so the present invention is not limited to the content proposed in the introduction. For example, the following introduction only provides general information limited by space and organization to specific embodiments. In fact, there are many other embodiments, including those finally extracted by the claims, and they are discussed throughout this balance. As discussed in more detail in the conclusion, the present invention includes all possible improvements and changes within the scope of the submitted claims, which are attached to the end of the submitted patent.

[0013] Various embodiments relate to techniques for enabling arbitrary interconnected mesh networks to efficiently transmit information and for enabling scalability and interoperability with low overhead and low complexity. The network formed as a result of interconnecting a group of mesh networks is called a multi-mesh. Each of the mesh networks of the multi-mesh network may have its own (and possibly unique) internal configuration and operation mode. This technology provides all the unicast data packets to propagate through the corresponding optimal path on the interconnected mesh network, as well as to avoid the forwarding loop of unicast and broadcast data packets. When considering the technology as a whole, the technology also provides for forwarding data packets along the best path through multiple mesh networks. The routing information and its processing are limited to and specifically used for each mesh of the multi-mesh network, thereby reducing routing processing and memory requirements compared to the case where there are all nodes in a single mesh network.

[0014] Terminology

[0015] Terminology elsewhere herein is used to describe selected elements and aspects of various embodiments and implementations. The following are examples of selected terms.

[0016] Node: An example of a node is an electronic device.

[0017] Data packet: An example of a data packet is that nodes transmit information subdivided into multiple data packets with each other.

[0018] Link: An example of a link is a conceptual representation of the ability of two (or more) nodes to communicate with each other. The link can be wired (nodes connected by a physical medium for carrying information, for example, electrical or optical interconnection) or wireless (nodes connected without a physical medium, for example, via radio technology).

[0019] Path/Route: An example of a path/route is a series of one or more links.

[0020] Path metric: An example of a path metric is the number that reflects the desirabity of the path. For example, the number of links (e.g., the hop count of the path) is a possible metric. A path with a low number of hops has an advantage over a path with a high number of hops. These advantages include less resource usage (due to reduced forwarding) and less chance of packet loss (due to fewer chances of loss before data packets reach their respective destinations).

[0021] Optimal path: An example of an optimal path is a sequential list of multiple nodes that result in an effective traversal from source to destination according to predetermined criteria as a data packet passes (in order). Since the parameters and operating conditions change over time, any optimal path is also a "known" optimal path; for example, it is based on a criterion estimated at a specific point in time, and different points in time can use different The best path. The best path can also be considered as the basis used to determine the best path

CN 103220748 Β

When the routing protocol is measured, it is based on the "almost ideal" of one or more metrics.

[0022] Network: An example of a network is a group of nodes that enable communication with each other via any combination of wired and wireless links.

[0023] Mesh network: An example of a mesh network is a group of nodes that self-organize as a multi-hop network. In some use cases, mesh networks have limited resources (for example, available bandwidth, available computing power, and available energy).

[0024] Multi-mesh network: An example of a multi-mesh network is a group of interconnected mesh networks, which, from the perspective of users of the resources provided by the multi-mesh network, appear to operate as one network.

[0025] Shared access network: An example of a shared access network is a network in which data packets transmitted by any node can be overheard by all other nodes in the network. An example implementation of such a network is 802.3LAN.

[0026] Ingress mesh network: An example of an ingress mesh network is a mesh network where data packets enter multiple mesh networks.

[0027] Egress mesh network: An example of an egress mesh network is a mesh network where data packets exit (or leave) multiple mesh networks.

[0028] Ingress mesh node: An example of an ingress mesh node is a node where a data packet enters a mesh network; for example, a node that forwards a data packet from a non-mesh network link to a mesh network link/network .

[0029] Egress mesh node: An example of an egress mesh node is a node where a data packet exits the mesh network; for example, a node that forwards a data packet from a mesh link to a non-mesh link/network .

[0030] Mesh bridge (node), an example of a mesh bridge is a node that participates in more than one mesh network at a time; for example, the node is connected to at least two mesh networks at a time . The bridge node connects multiple nodes to the first mesh network (or as part of the first mesh network) to communicate with multiple nodes connected to the second mesh network (or as part of the second mesh network) To communicate.

[0031] (Mesh) Bridge Link: An example of a mesh bridge link is two bridge nodes used to forward traffic between two mesh networks (each bridge node is connected To their respective mesh networks).

[0032] Ingress bridge node: An example of an ingress bridge node is a mesh bridge where a data packet exits (or leaves) an ingress mesh network.

[0033] Egress bridge node: An example of an egress bridge node is a mesh bridge where data packets enter the egress mesh network.

[0034] Mesh portal (portal): An example of a mesh portal is a node that is part of a mesh network and is also connected to other (shared access) networks. The mesh portal allows multiple nodes to connect to the mesh network (or as part of the mesh network) to communicate with nodes that are part of the shared access network (or reach through the shared access network). In some embodiments, the mesh network appears to act as a transparent layer-2 transport outside the network, that is, packets injected into the mesh network at one portal exit the mesh network at other unchanged portals.

[0035] Ingress mesh portal: An example of an ingress mesh portal is a portal for data packets to enter a mesh network, for example, forwarding data packets from a non-mesh link/network to a mesh link/network Portal.

[0036] Egress mesh portal: An example of an egress mesh portal is a portal where data packets exit the mesh network, for example, forwarding data packets from a mesh link/network to a non-mesh link/network Portal.

[0037] Mesh client interface: An example of a mesh client interface is an interface for connecting to a client device (as part of a node of the mesh network).

CN 103220748 Β

[0038] Mesh Gateway Interface (Mesh Network NGI): An example of a mesh network NGI is as part of a mesh network (for example, has an interface configured as part of a mesh network) and is also connected to another A network (for example, a node that has an interface configured to be on another network). The mesh network NGI enables nodes connected to the mesh network (or as part of the mesh network) to communicate with nodes that are part of the shared access network (or reach through the shared access network). In some embodiments, the mesh network appears to act as a transparent layer 2 transmitter outside the network: packets injected into the mesh network at one NGI exit the mesh network at another NGI or unchanged client interface.

[0039] Ingress mesh interface: An example of an ingress mesh interface is an interface through which a data packet enters a mesh network, for example, an interface that forwards a data packet from a non-mesh network link to a mesh network link/network .

[0040] Egress mesh interface: An example of an egress mesh interface is an interface for data packets exiting a mesh network, for example, an interface for forwarding data packets from a mesh link to a non-mesh link/network .

[0041] Unicast: An example of unicast is communication between two nodes.

[0042] Broadcast: An example of broadcast is communication that wants to reach multiple nodes from one node. In some use cases, the broadcast may not reach all desired nodes (for example, due to packet loss).

[0043] Flood: An example of flood is a broadcast sent by a node, which is rebroadcasted by each other node receiving the broadcast in turn, so that it may reach all nodes in the network.

[0044] Routing protocol: An example of a routing protocol is a set of mechanisms implemented on each node in a mesh network, where the mechanism is used to discover information about the network and connect each node on the network with Other nodes of the network communicate (even when other nodes are multiple hops away from each node) ο

[0045] Path accumulation: An example of path accumulation is to add its respective address to the data packet when each node forwards the data packet.

[0046] Exemplary combinations

[0047] The following is a collection of paragraphs concisely summarizing exemplary systems and methods based on the concepts taught in this article. Each paragraph uses an informal pseudo-claim format to highlight multiple combinations of features. These concise descriptions are not meant to be mutually exclusive, detailed, or restrictive, and the present invention is not limited to these prominent combinations. As discussed in more detail in the concluding section, the present invention includes all possible improvements and changes within the scope of the submitted claims, which are attached to the end of the submitted patent.

[0048] The first embodiment includes a method including: operating the first and second wireless mesh networks; and forwarding data packets between the wireless mesh networks via a bridge link connecting the wireless mesh networks Form multiple mesh networks; and prevent forwarding loops between wireless mesh networks. In the above embodiment, preventing the forwarding loop includes: assigning an identifier to the data packet. In the foregoing embodiment, the data packet includes a broadcast data packet. In the above embodiment, each identifier includes a source address field, and the source address field is based on the source address corresponding to the node that generated the identifier. In the foregoing embodiment, each identifier further includes an identification field, and the identification field uniquely identifies each data packet to the multi-mesh network in the environment of the relevant entry point. In the above embodiment, the relevant entry point is the entry mesh network node. In the above embodiment, the identifier is included in the previously existing control data packet. In the first embodiment, preventing the forwarding loop includes: assigning identifiers to broadcast data packets and unicast data packets.

[0049] The first embodiment includes: forwarding unicast data packets according to the best path. In the foregoing embodiment, the optimal path is determined based on the path learned from the accumulated path cost information. In the above embodiment, determining the best path is at least partially in response to forwarding the data packet. In the above embodiment, the accumulated path cost information is accumulated in at least one of the previously existing control data packet and the previously existing data data packet. In the above-mentioned embodiment, the cumulative path cost information is passed through each packet

CN 103220748 Β

The cost of forwarding packets on the mesh network.

[0050] The second embodiment includes a method including: operating the first and second wireless mesh networks, via a bridge link connecting the wireless mesh networks, by forwarding between the wireless mesh networks Data packets form a multi-mesh network; and eliminate redundant broadcast floods in each wireless mesh network. In the foregoing embodiment, eliminating redundant broadcast torrents includes: assigning identifiers to data packets. In the above embodiment, each identifier includes a source address field, and the source address field is based on the source address of the data packet corresponding to the identifier. In the foregoing embodiment, each identifier includes an identification field, and the identification field uniquely identifies each data packet to the multi-mesh network in the environment of the relevant entry point. In the above embodiment, the identifier is included in the previously existing control data packet.

[0051] The third embodiment includes a method including: operating the first and second wireless mesh networks via a bridge link connecting the wireless mesh networks by forwarding between the wireless mesh networks The data packets form a multi-mesh network; and the data packets are forwarded according to an effective route based at least in part on the routing cost information. In the above embodiment, the routing cost information is accumulated in the data packet during the traversal of the bridge link. In the above embodiment, the routing cost information is included in the previously existing control data packet.

[0052] In any one of the first, second, and third embodiments, the bridge link is a wireless link. In any of the first, second, and third embodiments, the bridge link is a plurality of wireless links. In any of the first, second, and third embodiments, the bridge link is a wired link. In any of the first, second, and third embodiments, the bridge link is a plurality of wired links. In any one of the first, second, and third embodiments, the bridge link includes at least one wired link and at least one wireless link.

[0053] In any of the first, second, and third embodiments, the first and second wireless mesh networks operate according to frequency diversity. In the above embodiment, frequency diversity includes operating the first and second wireless mesh networks according to distinct frequency spectrums. In any of the first, second, and third embodiments, the first and second wireless mesh networks operate according to respective first and second frequency allocations. In any of the first, second, and third embodiments, the first and second wireless mesh networks operate according to respective first and second frequency allocations, and at least one of the frequency allocations corresponds to an 802.11 compatible channel . In any of the first, second, and third embodiments, the first and second wireless mesh networks operate according to respective first and second frequency allocations, and at least one of the frequency allocations corresponds to 802.11a , 802.lib, and at least one of 802.11g compatible channels. In any of the first, second, and third embodiments, the first and second wireless mesh networks operate according to partial overlap or interference frequency allocation. In any of the first, second, and third embodiments, the first and second wireless mesh networks operate according to the same frequency allocation. In any of the first, second, and third embodiments, the first and second wireless mesh networks operate according to non-overlapping or non-interfering frequency allocation.

[0054] In any of the first, second, and third embodiments, the first and second wireless mesh networks operate according to respective first and second internal routing protocols. In any of the first, second, and third embodiments, the first and second wireless mesh networks operate according to the same internal routing protocol. In any of the first, second, and third embodiments, the first and second wireless mesh networks operate according to their own different internal routing protocols. In any of the first, second, and third embodiments, the first and second wireless mesh networks operate according to their different routing options. In any of the first, second, and third embodiments, the first and second wireless mesh networks operate according to their different routing parameters. In any of the first, second, and third embodiments, the first and second wireless mesh networks operate according to the same internal routing protocol, and each internal routing protocol can be based on its own different Route selection options to operate. Any one of the first, second, and third embodiments

CN 103220748 Β

, The first and second wireless mesh networks operate according to the same internal routing protocol, and each internal routing protocol can operate according to its own different routing parameters. In any of the first, second, and third embodiments, the first and second wireless mesh networks operate according to the same medium access control layer. In any of the first, second, and third embodiments, the first and second wireless mesh networks operate according to different media access control layers. In any of the first, second, and third embodiments, the first and second wireless mesh networks operate according to the same physical layer. In any of the first, second, and third embodiments, the first and second wireless mesh networks operate according to different physical layers.

[0055] The fourth, fifth, and sixth embodiments respectively include all the elements in the first, second, and third embodiments, wherein the bridge link is the first bridge link; and further includes: Connect the first and second wireless mesh networks via the second bridge link; expand the multiple mesh networks by forwarding data packets between the first and second mesh networks; and wherein, the second bridge link The connection is joined to the first and second wireless mesh networks via respective third and fourth mesh bridge nodes. In any of the fourth, fifth, and sixth embodiments, the first and second bridge link connections can be operated according to load balancing technology. In any of the fourth, fifth, and sixth embodiments, the first and second bridge link connections can be operated according to redundancy/failover technology.

[0056] The seventh, eighth, and ninth embodiments include all the elements of the first, second, and third embodiments, respectively, wherein the bridge link can operate in conjunction with the bridge link protocol. In any of the seventh, eighth, and ninth embodiments, there is no data packet dedicated to the use of the bridge link protocol.

[0057] The tenth embodiment includes a method that includes: operating the first and second wireless mesh networks; connecting the wireless mesh network via the first and second bridge links, by connecting to the wireless mesh network Data packets are forwarded between networks to form a multiple mesh network; and the bridge link is operated according to load balancing technology. The above embodiment further includes: preventing loops from being forwarded between wireless mesh networks. In the above embodiment, preventing the forwarding loop includes: assigning an identifier to the data packet. In the foregoing embodiment, the data packet includes a broadcast data packet. In the above embodiment, each identifier includes a source address field, and the source address field is based on the source address corresponding to the node generating the identifier. In the foregoing embodiment, each identifier further includes an identification field, which uniquely identifies each data packet to the multi-mesh network in the environment of the relevant entry point. In the above embodiment, the relevant entry point is the entry mesh network node. In the above embodiment, the identifier is included in the previously existing control data packet.

[0058] The tenth embodiment further includes: eliminating redundant broadcast floods in each wireless mesh network. In the foregoing embodiment, eliminating redundant broadcast torrents includes: assigning identifiers to data packets. In the above embodiment, each identifier includes a source address field, and the source address field is based on the source address of the data packet corresponding to the identifier. In the foregoing embodiment, each identifier includes an identification field, and the identification field uniquely identifies each data packet to the multi-mesh network in the environment of the relevant entry point. In the above embodiment, the identifier is included in the previously existing control data packet.

[0059] The tenth embodiment further includes: forwarding the data packet according to an effective route based at least in part on the routing cost information. In the above embodiment, during the traversal of the bridge link, the routing cost information is accumulated in the data packet. In the above embodiment, the routing cost information is included in the previously existing control data packet.

[0060] The eleventh embodiment includes a method that includes: operating the first and second wireless mesh networks; connecting the wireless mesh network via the first and second bridge links, by connecting to the wireless mesh network Data packets are forwarded between the network to form a multiple mesh network; and the bridge link is operated according to the redundancy/failure technology. The above embodiment further includes: preventing loops from being forwarded between wireless mesh networks. In the above embodiment, preventing the forwarding loop includes: assigning an identifier to the data packet. In the foregoing embodiment, the data packet includes a broadcast data packet. In the above embodiment, each identifier includes the source address

CN 103220748 Β

Field, the source address field is based on the source address corresponding to the node that generated the identifier. In the foregoing embodiment, each identifier further includes an identification field, and the identification field uniquely identifies each data packet to the multi-mesh network in the environment of the relevant entry point. In the above embodiment, the relevant entry point is the entry mesh network node. In the above embodiment, the identifier is included in the previously existing control data packet.

[0061] The eleventh embodiment further includes: eliminating redundant broadcast floods in each wireless mesh network. In the above embodiment, eliminating redundant broadcast torrents includes: assigning identifiers to data packets. In the above embodiment, each identifier includes a source address field, and the source address field is based on the source address of the data packet corresponding to the identifier. In the foregoing embodiment, each identifier includes an identification field, and the identification field uniquely identifies each data packet to the multi-mesh network in the environment of the relevant entry point. In the above embodiment, the identifier is included in the previously existing control data packet.

[0062] The eleventh embodiment further includes: forwarding the data packet according to an effective route based at least in part on the routing cost information. In the above embodiment, during the traversal of the bridge link, the routing cost information is accumulated in the data packet. In the above embodiment, the routing cost information is included in the previously existing control data packet.

[0063] In the twelfth embodiment, which is a computer-readable medium, the computer-readable medium has a set of instructions stored therein, and when the set of instructions is executed by the processing element, the processing element executes the instructions including the first to the eleventh The function of any one of the embodiments.

[0064] In the thirteenth embodiment of the system, the system includes a processor and a memory, the memory is used to store instructions executed by the processor, and the instructions are used to implement any one of the first to eleventh embodiments.

[0065] Mesh Scaling and Interoperability

[0066] As the size of the wireless mesh network increases, because wireless device transmissions interfere with each other, the use of a single radio frequency in the entire mesh network becomes a limitation. Therefore, the bandwidth available to nodes in the mesh network is reduced. Some embodiments reduce the effect of co-frequency interference by splitting a relatively large mesh network into smaller mesh networks. Then, each smaller mesh network is configured to operate at its own unique (eg, non-interfering) radio frequency, thereby reducing the interference of nodes operating in physically adjacent mesh networks.

[0067] In addition, due to the increase in the size of the wireless mesh network, the memory and processing requirements associated with the operation of the mesh network routing protocol have both increased. The operation of this routing protocol includes: storing the information describing how to reach the node of the selected wireless mesh network, and determining the address of the next node to send the data packet to continue forwarding the data packet. Some embodiments reduce the resource requirements of routing protocols for larger mesh networks by splitting relatively large mesh networks into smaller mesh networks. Each smaller mesh network then operates the routing protocol according to the restrictions associated with each smaller mesh network. Therefore, splitting a relatively large mesh network into smaller mesh networks improves the scalability of mesh network performance and operating resource costs.

[0068] In some use cases, with the development of mesh network technology, relatively new mesh network devices may not be able to be combined with relatively old devices. Similarly, even when both the new device and the old device are constructed with the same or essentially similar technology, different user requirements may still result in the new device and the old device having their own unique configurations, capabilities, or both Both. Some embodiments can interconnect different mesh networks (ie, provide communication between mesh networks for different internal configurations or operations).

[0069] As an example use case, consider a mesh network deployed in a large city. The mesh network can have more than 1000 mesh nodes, and can be split into smaller mesh networks with approximately 50 nodes each. Each small mesh network (or collection thereof) can be independently deployed by different vendors, but the overall network can remain operating as a multi-mesh network. Multiple parts of the deployment can be configured for home access, while other parts of the deployment can be configured for commercial use.

CN 103220748 Β

Use access.

[0070] Mesh interconnection and bridging

[0071] In some embodiments, the wireless mesh network may be divided into smaller (sub)mesh networks, and the smaller mesh networks are interconnected by mesh bridge nodes that operate in part in accordance with a bridging protocol. The first mesh bridge in the first mesh network is connected to the second mesh bridge in the second mesh network via a point-to-point (wired or wireless) link. The point-to-point links connecting the mesh bridges are called bridge links. In some embodiments, the bridge link includes multiple point-to-point links, and in some embodiments, multiple bridge links can enable communication between a pair of mesh networks. Multiple links and bridge links provide higher overall throughput between the mesh network, and also selectively load balance within the mesh network. In some embodiments, the nodes in each (sub)mesh network can be configured to operate at a corresponding unique/non-interfering frequency, so that the nodes in the physically adjacent (or adjacent) mesh network Operation has reduced interference. In some embodiments, if interference is not an issue, the nodes in the selected (sub)mesh network can be configured to operate in the same or overlapping/interfering frequency bands. For example, bridge links connecting (sub)mesh networks operating in the same or overlapping frequency bands can provide a sufficiently large physical separation of the connected (sub)mesh networks to prevent basic interference.

[0072] Multiple mesh operations

[0073] The effective operation of interconnected multiple mesh networks includes techniques for reducing (or eliminating) loops and optimizing unicast and broadcast packet forwarding. For the first example, if the mesh networks are interconnected by bridge links forming loops, in some use cases, control information is added to the data packets transmitted from one mesh network to another mesh network to control Information is used to prevent data packets from circling the loop multiple times or in some uncertain situations (thus potentially causing network congestion to collapse). In some use cases, one or more loop interconnections may be used to provide redundancy, or it may be an installation error (for example, in a multi-mesh network, multiple customers have multiple meshes and customers lack each other When coordinating).

[0074] As a second example, if there are multiple connections between two mesh networks in a multi-mesh network, increase the number of connections by making unicast packets follow the entire optimal path through the multi-mesh network. The efficiency of the entire multiple mesh network. In other words, by determining the most efficient path based on the entire multiple mesh network (rather than based on each individual mesh network), bandwidth, delay, and resource utilization are improved.

[0075] As a third example, in a use case where a separate mesh network in a multiple mesh network distributes broadcast data packets via a torrent, when the data packet enters the mesh network (for example, when it is sent via any bridge link) Before), the control information was included in the broadcast packet. The control information reduces and eliminates the flood of redundant broadcast packets, otherwise a flood occurs when a comparable copy of the broadcast packet enters one of the separate mesh networks via multiple different bridge links, and each copy is considered to be a stream Different broadcast packets that have been passed. Control information can suppress other excessive multiple torrents.

[0076] As a fourth example, in some use cases where a single mesh network in a multiple mesh network may loop (eg, via a bridge link), the control information is included in the data packet before being sent over the bridge link in. The control information reduces or eliminates other possible wireless loop behaviors among multiple separate mesh networks, otherwise it may cause congestion collapse.

[0077] FIG. 1 shows selected examples of techniques for reducing (or eliminating) loops and optimizing single-wave and broadcast packet streams for multiple mesh networks, in part, based on bridging protocols. Details. In some use cases, this technology has no additional control data packet overhead, relatively minimized control byte overhead, and reduced protocol complexity. The multi-mesh network shown includes individual multiple individual meshes 1121, mesh 2122, mesh 3123, and mesh 4124. As shown by bridges 1-12 (101-112 respectively), these meshes are bridged via several bridges. Bridges 1 and 3 bridge meshes 1 and 2, respectively, and bridges 2 and 4 are the same. The bridges 9 and 7 are connected to the mesh 4 and

CN 103220748 Β

3 for bridging, the same for bridges 10 and 8. The bridges 12 and 11 bridge the mesh networks 1 and 4, respectively. The bridges 5 and 6 bridge the mesh networks 2 and 3 via the wireless link 130, respectively. The ingress mesh node 1141 provides a portal for data packets, such as from the Internet, a local area network (LAN), a wide area network (WAN), or any other suitable network to enter the multi-mesh. Egress mesh nodes 1 and 2 (151 and 152 respectively) provide a portal for data packets to exit the multiple mesh network (for example, to the Internet, LAN, WAN, or any other suitable network). In some embodiments, the node can operate as an ingress mesh node and an egress mesh node at the same time, providing a portal for data packets to enter and exit multiple mesh networks.

[0078] As an example of operation, when the mesh bridge receives a broadcast data packet from a mesh network (for example, mesh 1), the mesh bridge forwards the data packet to Another mesh network (for example, mesh network 2). Before forwarding the data packet, the mesh bridge removes any data packets specifically used for routing information of the mesh network (for example, mesh network 1) that has just passed through. The removed information includes path cost information associated with the traversal of the data packet through the mesh network (eg, mesh network 1) that has just passed. The path cost information is attached to the data packet to be forwarded. The broadcast packet is then forwarded to other mesh networks.

[0079] In this way, when a broadcast data packet passes through multiple mesh networks, information related to path costs is accumulated. The accumulated path cost information corresponds to the cost of forwarding a data packet through each mesh network, and the data packet is forwarded to the point where the accumulated path cost information is calculated (or updated). In some embodiments, for each mesh that passes through, the mesh hop metric is added_oIn some embodiments, for each mesh traversed, a mesh cost metric is calculated and stored. In some embodiments, for each traversed mesh network, a mesh network metric type describing the type of cost metric associated with the mesh network is stored. In some embodiments, the smallest connection metric on all links is used as the path metric. Compare paths based on metrics. In some embodiments, this comparison is based in part on the metric value, and in some embodiments, this comparison is based in part on the mesh metric type. In some embodiments, the mesh metric type is used as the (intrinsic) metric value (eg, "high bandwidth" and "low bandwidth" mesh metric type environments).

[0080] In some embodiments, there is a bridge table with one entry for each bridge node. Each entry includes the address and status for the destination bridge, and a list of next-hop bridge addresses. Each element of the next-hop bridge address list includes the cost of reaching the destination bridge via the bridge determined by the respective next-hop bridge address, and the status of the bridge link connected to the respective next-hop bridge .

[0081] The egress mesh node that receives the (redundant) copy of the broadcast data packet (for example, due to multiple paths to the egress mesh node) compares the cost of each path in the copy and determines that it has the relatively best The total cost of the path is for future use. In an embodiment where the mesh network metrics are accumulated separately and one or more metric types are unknown, multiple parts of the adopted path through the mesh network can be compared.

[0082] The mesh bridge and the egress mesh node that receive and forward the broadcast data packet learn the best path through each mesh network by checking and processing the control information included in the data packet (with the data packet passing through The order of the mesh network). The learned best path includes the best path between the ingress mesh node that broadcasts the data packet and each mesh bridge and the egress mesh node that forwards the broadcast data packet. The control information includes path cost information added when the data packet is forwarded through the bridge link, the next bridge that forwards the data packet along the path, and the mesh bridge node that has been selectively passed along the path so far. In some embodiments, the implementation learns the best path through a series of mesh networks traversed, without knowing how to route data packets within each mesh network (ie, the information about the bridge links passed is Full). In some embodiments, learning the best path through a series of mesh networks passed is performed using the metric associated with the traversed mesh network and the metric associated with the next bridge through which the packet is forwarded. In some embodiments, the metric is a hop-count metric, and the best path is the route with the smallest number of hops. In this article

CN 103220748 Β

The techniques discussed elsewhere in "do not depend on the details of the best path determination, and other metrics for the best path determination can be used based on implementation-dependent criteria.

[0083] The ingress mesh node forwards the unicast packet to the next mesh in the opposite direction (for example, from the destination of the unicast packet) along the best path learned during the previous forwarding of the broadcast packet Network bridge. If the data packet comes from a mesh network including a mesh bridge, the mesh bridge forwards the unicast data packet to the adjacent mesh network via the bridge link. If the packet comes from an adjacent mesh network (for example, via a bridge link), the mesh bridge forwards the packet to the mesh bridge along the best path to the destination, or if it includes a network The mesh network of the network bridge also includes a destination (for example, the data packet enters the final mesh network through which it passes), and it is forwarded to the egress mesh network node. Unicast packets to unknown destinations are forwarded as broadcast torrents (similar to layer-2 switching torrents), so that the de-bridge forwarding information used in the process of forwarding subsequent packets can be learned.

[0084] Each broadcast data packet is assigned a unique ID by the ingress mesh network node, and the broadcast data packet enters the multi-mesh network, and the ID is maintained when the data packet is forwarded through the bridge link. The ID can be used for replication detection at each mesh network node and each mesh bridge, thereby preventing loops within each mesh network and between multiple mesh networks. The ID includes two elements. The first element is the address associated with the node that generated the ID, so the first element is unique across the entire multi-mesh network. The second element is relative to other broadcast data packets identified by the node that generated the ID. The sequence number (or similar field) unique to this broadcast data packet, so the second element can be relative to the ID generated by other nodes The second element is not unique. Therefore, the second element (thus generating the entire ID) can be independently generated by multiple nodes. In other words, the communication between nodes does not need to generate a unique ID in the entire multi-mesh network environment.

[0085] In some operating situations, an identifier is assigned to broadcast data packets, while in other operating situations, an identifier is assigned to unicast and broadcast data packets. For example, when a data packet is originally sent as a unicast data packet, but the unicast data packet arrives at a mesh bridge that does not have the state to forward unicast data packets (for example, the forwarding state may have expired), the unicast data The packet can receive an identifier. Then, the unicast data packet is treated as a data packet to an unknown destination, and is transmitted within the mesh network (the mesh bridge forwards the unicast data packet to the mesh network) (similar to broadcast data) package). Subsequently, the unicast data packet is treated as a broadcast data packet (including receiving identifier assignment) to prevent loops.

[0086] A single mesh network among multiple mesh networks may operate according to various characteristics including routing protocols, routing options, media access control (MAC) layer, and physical access (PHY) layer. The characteristics of each mesh in the multi-mesh network may not depend on the characteristics of other mesh networks in the multi-mesh network. For example, a first mesh network can operate with a first routing protocol, while all other mesh networks can operate with a different routing protocol. For another example, each mesh network can operate with its own distinct routing protocol. For another example, each mesh network can use the same routing protocol to operate. Similar changes can be made for other features (routing options, MAC layer, and PHY layer).

[0087] Although the link enabling communication between the bridge 5 and the bridge 6 is shown as a wireless link (for example, a radio frequency link such as an 802.11 link), in some embodiments, the link may be a wired link. Link (for example, Ethernet link). In some embodiments, the illustrated link represents a single link, while in other embodiments, the illustrated link represents two or more links (wireless, wired, or both). In an embodiment with two or more links connecting the same two mesh networks, the two or more links may be operated in a load balancing manner, a failure/redundancy manner, or both.

[0088] Node hardware and software

[0089] Figure 2 shows selected details of the hardware aspects of an embodiment of a node. The node shown includes a processor 205 connected to multiple types of memories, including volatile read/write via DRAM memory interface 202.

CN 103220748 Β

Write memory bank components 201.1-2 and non-volatile read/write memory flash 203 and EEPROM 204 devices. The processor is also connected to an Ethernet interface 206 that provides a plurality of Ethernet ports 207 for establishing a wired link, and to a wireless interface 209 that provides radio frequency communication of data packets for establishing a wireless link. In some embodiments, the wireless interface is compatible with IEEE 802.11 wireless communication standards (for example, any one of 802.1 la, 802.1 lb, and 802.1 lg). In some embodiments, the wireless interface (along with any combination of hardware and software devices) operates to collect statistics based on neighboring nodes of the mesh network. Statistics can include any combination of signal strength and link quality. In some embodiments, the wireless interface is configured to cancel all data packets below a settable received signal strength indicator (RSSI) threshold. The block shown is only an example, and other equivalent embodiments of nodes are also possible.

[0090] The illustrated node may function as any one of the multiple nodes including an ingress mesh network node, an egress mesh network node, and a bridge shown in FIG. 1. The wireless interface of FIG. 2 can communicate with nodes inside the mesh network (not explicitly shown in FIG. 1, but can be understood as elements of each of the mesh networks 1, 2, 3, and 4). When the node according to FIG. 2 is used as a bridge node (for example, any one of the bridges 1 to 12 of FIG. 1), the wireless interface may also provide a wireless bridge link. In the embodiment according to FIG. 1 with one or more wired links, the Ethernet interface of FIG. 2 may provide Ethernet for wired bridge links (including load balancing or redundant/faulty bridge links) port. When the node according to Figure 2 operates as an ingress (egress) mesh node, one or more Ethernet ports provided by the Ethernet interface can also be used to provide a path for data packets to enter (exit) the mesh network . According to various usage conditions, any combination of storage elements (DRAM, FLASH, and EEPROM) can store one or more bridge tables.

[0091] In operation, the processor reads instructions from any combination of storage elements (DRAM, FLASH, and EEPROM) and executes the instructions. Some of the instructions correspond to software associated with operating the bridge link in conjunction with the bridge link protocol. The various parts of the bridge link protocol control the operation of any combination of wireless and Ethernet interfaces. According to instructions executed during processing associated with the bridge link protocol, the accumulated path cost information can be stored in any combination of a plurality of storage elements.

[0092] FIG. 3 shows selected details of the software aspects of an embodiment of a node. The software shown includes a network management system (NMS) manager 301, which is connected to a network interface manager 302 and a fault, configuration, accounting, performance, and security (FCAPS) manager 303. In some embodiments, the NMS interfaces between the management software operating outside the node and the software operating inside the node (for example, multiple applications and FCAPS). The network interface manager manages the physical network interfaces (for example, the node's Ethernet interface and wireless interface). The network interface manager assists the NMS to transmit dynamic configuration changes (as requested by the user) to FCAPS through the management software. In some embodiments, FCAPS includes the function of storing and retrieving configuration information. The FCAPS function serves all applications that require constant configuration information. FCAPS can also assist in collecting fault information and statistical information from multiple operating modules of the node. And performance data oFCAPS can transmit any part of the collected information, statistical information, and data to the NMS.

[0093] The kernel interface 310 interfaces multiple managers with the routing and transmission protocol layer 311 and the flash file system module 313. The routing protocol includes several parts of the bridge link protocol and the software involved in maintaining the bridge table and referencing the bridge table. Transmission protocols include TCP and UDP. The flash file system module interface is connected to the flash drive 316, which is conceptually connected to the flash hardware element 323, and the flash hardware element is represented as a flash file system stored in any combination of flash and EEPROM elements in FIG. 2. The Layer-2 abstraction layer 312 interfaces the routing and transmission protocols to the Ethernet driver 314 and the radio frequency driver 315, respectively. The Ethernet driver is shown as conceptually connected to the Ethernet interface 326, which is represented as the Ethernet interface of FIG. 2. The RF driver is shown conceptually connected to the wireless

CN 103220748 Β

The interface 329, the wireless interface is shown as the wireless interface in FIG. 2. In some embodiments, the software may also include a serial port driver. The software is stored on a computer-readable medium (for example, any combination of DRAM, FLASH, and EEPROM components) and executed by the processor. The blocks shown are only examples, and many other equivalent configurations of layers are also possible.

[0094] Summary

[0095] Although some of the above-mentioned embodiments are described in some detail for a clearer understanding, the present invention is not limited to the details provided. There are many alternative ways of implementing the invention. The disclosed embodiments are illustrative and not restrictive. It should be understood that many changes in the structure, configuration, and use may be consistent with the content taught and fall within the scope of the claims appended to the submitted patent. For example, the interconnection and functional unit bit width, clock speed, and technology type used usually vary among the various component blocks. The processing sequence and configuration of flowcharts and flowchart diagrams, as well as functional elements, are usually subject to change. In addition, unless stated to the contrary, the range of values listed, the maximum and minimum values used, or other specific descriptions (for example, comprehensive technology and design flow technology) are merely exemplary embodiments, and it is conceivable to implement technology Improvements and changes are not being interpreted as limitations.

[0096] Various components, subsystems, functions, operations, procedures, and subroutines can be implemented using functionally equivalent technologies known to those skilled in the art instead of the illustrated embodiments. The names assigned to interconnections, logics, functions, and programs are only exemplary and should not be construed as being limited to what is taught. It should also be understood that many design functional aspects can be implemented by hardware (ie, generally dedicated hardware) or software (ie, some way via a programmed controller or processor), as a way to achieve independent design constraints and faster The technological trend of processing (which facilitates the movement of functions previously in hardware to software) and higher integration density (which facilitates the movement of functions previously in software to hardware). Specific changes can include, but are not limited to: differences in networking technology (for example, wired/wireless, protocol, and bandwidth); and what is expected in accordance with the unique features and business constraints of specific applications when implementing the content taught in this article Other changes.

[0097] A number of embodiments have been shown, and the surrounding environment is beyond that required for minimizing many aspects of the taught content. Those of ordinary skill in the art will recognize that changes can omit the disclosed elements without changing the basic cooperation in the remaining elements. Therefore, it should be understood that in order to achieve multiple aspects of the content taught, a large amount of public details is not necessary. As far as the remaining components are distinguishable from the prior art, the omitted components are not limited to the content taught in this article.

[0098] All such changes in the design include insubstantial changes based on the teachings conveyed by the exemplary embodiments. It should also be understood that the content taught in this article has wide applicability in other networking and communication applications, and is not limited to the specific application or industry of the illustrated embodiment. Therefore, the present invention should be understood to include all possible improvements and changes included in the scope of the claims appended to the filed patent.

CN 103220748 Β