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

Areas: Routing protocols for bridging networks need further progress to improve their performance, efficiency, and practicality. The embodiments described elsewhere herein enable improvement.

Related Techniques: The techniques and concepts described herein are known or prior art, including those for contextual provision, definition, or comparison, unless expressly stated to be publicly known or well known. It should not be interpreted as part of the technology. When citations are made herein, all of those references, including patents, patent applications, and publications, are hereby incorporated by reference in their entirety, whether or not they are specifically included for all purposes. It shall be incorporated into the book. The description herein is also construed as prior art in which any of the references is relevant, and that any of the references is a factual approval of the content or date on which these references were actually published (published). Should not be.

<p> The present invention can be implemented (implemented) in a number of ways, including methods, products, devices, systems, composition of substances, and other computer-readable media such as computer-readable storage media, and programs via optical or electronic communication links. It can be implemented as a computer network to which instructions are transmitted. As used herein, these embodiments, or any other form that the invention may take, can be referred to as technology. In general, the order of each step (step) of the methods disclosed herein can be changed within the scope of the present invention. One or more embodiments of the present invention are disclosed in the section of detailed description. This detailed description section includes the "Introduction (Introduction)" section to facilitate understanding of the rest of this section. This "Introduction (Introduction)" describes an exemplary combination that briefly summarizes exemplary systems and methods according to the concepts disclosed herein. As described in detail below in the "Conclusion" section, the present invention includes all possible modified (modified) and modified forms within the scope of the claims attached to the end of the registered patent.</p>

The present invention can be implemented (implemented) in a number of ways, including processes, manufactured goods, equipment, systems, composition of substances, and other computer-readable media such as computer-readable storage media, and programs via optical or electronic communication links. It can be implemented as a computer network to which instructions are transmitted. As used herein, these embodiments, or any other form that the invention may take, can be referred to as technology. In general, the order of each step (step) of the methods disclosed herein can be changed within the scope of the present invention.

Hereinafter, one or more embodiments of the present invention will be described in detail with accompanying drawings exemplifying the principles of the present invention. The present invention will be described in connection with such embodiments, but is not limited to any embodiment. The scope of the present invention is limited only by claim, and the present invention includes many alternative forms, modified (modified) forms, and equivalents (equivalents). In the following description, a number of specific details will be provided so that the present invention may be fully understood. These details are provided for exemplification purposes, and the present invention can be carried out in accordance with the appended claims, even without some or all of these specific details. For clarity, technical matters known in the art of the invention are not detailed so as not to unnecessarily obscure the invention.

Introduction (Introduction) This section is included so that the following detailed explanation can be easily understood in a shorter time. The description in this section is inevitably a summary of the entire subject matter of the invention and is not intended to be a complete and limited description of the invention, and thus the invention is limited to the concepts described in this section. It's not something. For example, the following provides an overview only for certain embodiments due to space and configuration limitations of this specification. In fact, there are many other embodiments, including those that are ultimately consistent with the claims described throughout the rest of the specification. As described in detail below in the "Conclusion" section, the present invention includes all possible modified (modified) and modified forms within the scope of the claims attached to the end of the registered patent.

Various embodiments relate to low overhead, low complexity techniques that provide scalability and interoperability by allowing arbitrarily interconnected mesh networks to communicate information efficiently. The network formed as a result of interconnecting a set of mesh networks is called a multi-mesh. Each mesh network of the multi-mesh can have its own (possibly unique) internal settings and modes of operation. This technique allows all unicast packets to follow their respective best paths across the interconnected mesh, avoiding forwarding loops for unicast and broadcast packets. With this technique, if the entire multi-mesh is regarded as one unit, it is possible to transfer packets along the best route over the entire multi-mesh. Since the routing information and its processing are constrained to each mesh of the multi-mesh and are unique to each mesh, the routing processing and memory requirements are reduced as compared with the scenario where all the nodes are in a single mesh.

the term In other parts of the specification, various terms are used to select and describe some of the elements and aspects of various embodiments and embodiments. The following are typical terms.

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

Packets: An example of a packet is when the information that nodes communicate with each other is subdivided into packets.

Link: An example of a link is the conceptual representation of the ability of two (or more) nodes to communicate with each other. Links can be wired (nodes are connected to carry information via physical media such as electrical or optical interconnects) or wireless (nodes are connected by wireless technology, etc. without using physical media). It may be there.

Routes: Examples of routes include a series of links, one or more.

Path Metrics: Examples of path metrics include metrics (numerical indicators) that reflect the desirability of the route. For example, one possible metric is the number of links, such as the number of hops on the route. It is advantageous for the route to have a small number of hops. Its advantages include using less resources (less forwarding) and less risk of packet loss (less chance of packets being lost before reaching each destination).

Best Routes: An example of the best routes is an ordered node list that makes it efficient to move from source to destination when packets pass (orderly) according to certain criteria. Because parameters and operating conditions change over time, any best route is a "known" best route, eg, a route evaluated at a particular time point based on certain criteria, with different best routes being used at different time points. There is a possibility that it can be done. Also, the best route can be considered "nearly optimal" based on one or more metrics measured against the routing protocol that determines it.

Network: An example of a network is a set of nodes that can communicate with each other over any combination of wired and wireless links.

Mesh network: An example of a mesh network is a set of nodes that self-organize into a multi-hop network. In some usage scenarios, mesh network resources are limited (available bandwidth, available computing power, available energy, etc.).

Multi-mesh network: An example of a multi-mesh network is a set of interconnected meshes that appear to be operating as a single network to the users of the resources provided by that multi-mesh network.

Shared access network: An example of a shared access network is a network in which all other nodes in the network overhear (listen to) packets sent by any node. An example embodiment of such a network is an 802.3 LAN.

Ingress mesh: An example of an ingress mesh is a mesh that is the entry point for packets into a multi-mesh.

Egress (exit) mesh: An example of an egress mesh is a mesh that is the exit for packets from a multi-mesh.

Ingress mesh node: An example of an ingress mesh node is a node that is the entry point for packets, such as a node that forwards packets from a non-mesh link to a mesh link / network.

Egress mesh node: An example of an egress mesh node is a node that exits a packet, for example, a node that forwards a packet from a mesh link to a non-mesh link / network.

Mesh Bridge (Node): An example of a mesh bridge is a node that participates in two or more mesh networks at the same time, which is, for example, joined to at least two mesh networks at the same time. A node connected to (or part of) the first mesh by a bridge node is a node connected to (or part of) the second mesh. Can communicate with.

(Mesh) Bridge Link: An example of a mesh bridge link is a link between two bridge nodes used to forward traffic between the two meshes (each bridge node is attached to its own mesh). ).

Ingress Bridge Node: An example of an Ingress Bridge node is the mesh bridge, which is the exit for packets from the Ingress mesh.

Egress Bridge Node: An example of an Egress Bridge node is the mesh bridge, which is the entry point for packets from the Egress mesh.

Mesh Portal: An example of a mesh portal is a node that is part of a mesh network, which is also connected to another (shared access) network. The mesh portal allows nodes connected to the mesh or nodes that are part of the mesh to communicate with nodes that are part of the shared access network or reachable via the shared access network. In some embodiments, the mesh network appears to be out of the network as a transparent Layer 2 transport, i.e. packets populated into the mesh from one portal exit the mesh from another portal unmodified.

Ingress Mesh Portal: An example of an Ingress Mesh Portal is a portal that is the entry point for packets into the mesh, for example a portal that forwards packets from a non-mesh link / network to a mesh link / network.

Egress Mesh Portal: An example of an Egress Mesh Portal is a portal that exits packets from the mesh, for example a portal that forwards packets from a mesh link / network to a non-mesh link / network.

Mesh client interface: An example of a mesh client interface is an interface (which is part of a node in a mesh network) for binding to a client device.

Mesh Network Gateway Interface (Mesh NGI): An example of a mesh NGI is a node that is part of a mesh network (for example, has an interface configured as part of a mesh network), which can also be on another network. Being connected (eg, having an interface configured on another network). Mesh NGI allows nodes connected to or part of a mesh network to communicate with nodes that are part of a shared access network or reachable via a shared access network. In some embodiments, the mesh network appears to be off-network as a transparent Layer 2 transport. That is, packets put into a mesh by one NGI exit the mesh from another NGI or client interface without modification.

Ingress mesh interface: An example of an ingress mesh interface is an interface that is the entry point for packets into the mesh, for example an interface that forwards packets from a non-mesh link / network to a mesh link / network.

Egress mesh interface: An example of an egress mesh interface is an interface that exits packets from the mesh, for example, an interface that forwards packets from a mesh link / network to a non-mesh link / network.

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

Broadcast: An example of a broadcast is communication aimed at reaching multiple nodes from one node. In some usage scenarios, these multiple nodes include all nodes on the network. Also, in some scenarios, the broadcast may not reach all intended nodes (eg due to packet loss).

Flood: An example of a flood is a broadcast sent by a node, which is rebroadcast by all other nodes that receive this broadcast, potentially reaching all nodes in the network.

Routing Protocol: An example of a routing protocol is a set of mechanisms implemented on each node in a mesh network, which serves to find information about that network, with each node in that network being the same network. Allows communication with one node (even if other nodes are a few hops away from the node).

Route accumulation: An example of route accumulation is when each node forwarding a packet adds its own address to the packet.

Illustrative combination The following is a brief summary of exemplary systems and methods for the concepts disclosed herein. Each paragraph describes a combination of features that is representative in an informal format similar to the claims. These introductions are not mutually exclusive with the present invention, do not fully describe the present invention, nor limit the present invention, and the present invention is limited to a representative combination thereof. It's not a thing. As detailed below in the "Conclusion" section, the present invention includes all possible modified (modified) and modified forms within the scope of the claims attached to the end of this patent.

The first embodiment includes a step of forwarding a unicast packet according to the best route. In the aforementioned embodiment, the best route is determined according to a route learned from the accumulated path cost information. In the aforementioned embodiments, the determination of the best route is made in response to packet forwarding, at least in part. In the above-described embodiment, the accumulated path cost information is accumulated in at least one of the existing control packet and the existing data packet. In the aforementioned embodiment, the accumulated path cost information is the cost of packet transfer over the entire mesh through which the packet has passed.

In a second embodiment, a step of operating a first wireless mesh network and a second wireless mesh network via a bridge link connecting these wireless mesh networks and a packet between the wireless mesh networks are transmitted. A second embodiment comprising a step of forming a multi-mesh network by transfer and a step of eliminating redundant broadcast flooding within each wireless mesh network. In the above-described embodiment, the step of eliminating the redundant broadcast flooding includes a step of assigning an identifier to the packet. In the aforementioned embodiments, each identifier has a packet source address field corresponding to that identifier. In the aforementioned embodiments, each identifier has an identification field that uniquely identifies each packet in the context of its associated entry point to the multi-mesh network (related entry point). In the aforementioned embodiment, the identifier is included in an existing control packet.

A third embodiment, in which a first wireless mesh network and a second wireless mesh network are operated via a bridge link connecting these wireless mesh networks, and a packet is transmitted between the wireless mesh networks. A third embodiment comprising a step of forming a multi-mesh network by forwarding and a step of forwarding packets at least partially according to an efficient route based on route cost information. In the above embodiment, the route cost information is accumulated in the packet when passing through the bridge link. In the above-described embodiment, the route cost information is included in the existing control packet.

In any of the first embodiment, the second embodiment, and the third embodiment, the bridge link is a wireless link. In any of the first embodiment, the second embodiment, and the third embodiment, the bridge link is a plurality of wireless links. In any of the first embodiment, the second embodiment, and the third embodiment, the bridge link is a wired link. In any of the first embodiment, the second embodiment, and the third embodiment, the bridge link is a plurality of wired links. In any of the first embodiment, the second embodiment, and the third embodiment, the bridge link has at least one wireless link and at least one wired link.

In any of the first embodiment, the second embodiment, and the third embodiment, the first wireless mesh network and the second wireless mesh network operate according to frequency diversity. In the above embodiments, the frequency diversity comprises manipulating the first wireless mesh network and the second wireless mesh network according to different (distinguishable) frequency spectra. In any of the first embodiment, the second embodiment, and the third embodiment, the first wireless mesh network and the second wireless mesh network are each assigned a first frequency and Operates according to the second frequency allocation. In any of the first embodiment, the second embodiment, and the third embodiment, the first wireless mesh network and the second wireless mesh network are each assigned a first frequency and It operates according to the second frequency allocation and at least one of the frequency allocations corresponding to 802.11 compatible channels. In any of the first embodiment, the second embodiment, and the third embodiment, the first wireless mesh network and the second wireless mesh network are each assigned a first frequency and Second frequency allocation and 802.11a compatible channels, 802.11b compatible channels, and 802.11. Operates according to at least one of the frequency assignments for 11g compatible channels. In any of the first embodiment, the second embodiment, and the third embodiment, the first wireless mesh network and the second wireless mesh network partially overlap or interfere with each other. Operates according to frequency allocation. In any of the first embodiment, the second embodiment, and the third embodiment, the first wireless mesh network and the second wireless mesh network operate according to the same frequency allocation. .. In any of the first embodiment, the second embodiment, and the third embodiment, the first wireless mesh network and the second wireless mesh network do not overlap or interfere with frequency allocation. It works according to.

In any of the first embodiment, the second embodiment, and the third embodiment, the first wireless mesh network and the second wireless mesh network are each a first internal routing protocol. And operates according to a second internal routing protocol. In any of the first embodiment, the second embodiment, and the third embodiment, the first wireless mesh network and the second wireless mesh network operate according to the same internal routing protocol. To do. In any of the first embodiment, the second embodiment, and the third embodiment, the first wireless mesh network and the second wireless mesh network operate according to different internal routing protocols. To do. In any of the first embodiment, the second embodiment, and the third embodiment, the first wireless mesh network and the second wireless mesh network operate according to different routing options. .. In any of the first embodiment, the second embodiment, and the third embodiment, the first wireless mesh network and the second wireless mesh network operate according to different routing parameters. .. In any of the first embodiment, the second embodiment, and the third embodiment, the first wireless mesh network and the second wireless mesh network operate according to the same internal routing protocol. However, each internal routing protocol can operate according to different routing options. In any of the first embodiment, the second embodiment, and the third embodiment, the first wireless mesh network and the second wireless mesh network operate according to the same internal routing protocol. However, each internal routing protocol can operate according to different routine parameters. is there. In any of the first embodiment, the second embodiment, and the third embodiment, the first wireless mesh network and the second wireless mesh network follow the same media access control layer. Operate. In any of the first embodiment, the second embodiment, and the third embodiment, the first wireless mesh network and the second wireless mesh network operate according to different media access control layers. To do. In any of the first embodiment, the second embodiment, and the third embodiment, the first wireless mesh network and the second wireless mesh network operate according to the same physical layer. .. In any of the first embodiment, the second embodiment, and the third embodiment, the first wireless mesh network and the second wireless mesh network operate according to different physical layers.

In the fourth embodiment, the fifth embodiment, and the sixth embodiment, which have all the elements of the first embodiment, the second embodiment, and the third embodiment, respectively, the bridge link. Is a first bridge link, wherein the fourth embodiment, the fifth embodiment, and the sixth embodiment further include the first wireless mesh network and the first wireless mesh network via the second bridge link. It comprises a step of combining the second wireless mesh network and a step of extending the multi-mesh network by transferring packets between the first mesh network and the second mesh network. The coupling of the two bridge links is interface-coupled to the first wireless mesh network and the second wireless mesh network via the third mesh bridge node and the fourth mesh bridge node, respectively. In any of the fourth embodiment, the fifth embodiment, and the sixth embodiment, the coupling of the first bridge link and the second bridge link is performed according to a load balancing technique. It is operational. In any of the fourth embodiment, the fifth embodiment, and the sixth embodiment, the coupling of the first bridge link and the second bridge link operates according to the redundancy / failover technique. It is possible.

In the seventh embodiment, the eighth embodiment, and the ninth embodiment having all the elements of the first embodiment, the second embodiment, and the third embodiment, respectively, the bridge link. Can work with the bridge link protocol. In any of the seventh embodiment, the eighth embodiment, and the ninth embodiment, there is no packet dedicated to the bridge link protocol.

A tenth embodiment, in which a step of operating a first wireless mesh network and a second wireless mesh network and a first bridge link and a second bridge link connecting these wireless mesh networks are used. A method having a step of forming a multi-mesh network by transferring packets between the wireless mesh networks and a step of operating the first bridge link and the second bridge link according to a load distribution technique. A tenth embodiment having. In the aforementioned embodiment, this embodiment further includes a step of preventing a transfer loop between the wireless mesh networks. In the above-described embodiment, the step of preventing the transfer loop includes a step of assigning an identifier to the packet. In the aforementioned embodiment, the packet includes a broadcast packet. In the aforementioned embodiments, each identifier has a source address field based on the source address corresponding to the node that generates the identifier. In the aforementioned embodiments, each identifier further has an identification field that uniquely identifies each packet in the context of its associated entry point to the multi-mesh network (related entry point). In the aforementioned embodiment, the relevant entry point is an ingress mesh node. In the aforementioned embodiment, the identifier is included in an existing control packet.

In the tenth embodiment, the tenth embodiment further includes a step of eliminating redundant broadcast flooding in each wireless mesh network. In the above-described embodiment, the step of eliminating the redundant broadcast flooding includes a step of assigning an identifier to the packet. In the aforementioned embodiments, each identifier has a packet source address field corresponding to that identifier. In the aforementioned embodiments, each identifier has an identification field that uniquely identifies each packet in the context of its associated entry point to the multi-mesh network (related entry point). In the aforementioned embodiment, the identifier is included in an existing control packet.

In the tenth embodiment, the tenth embodiment further includes a step of forwarding packets according to an efficient route based on route cost information, at least in part. In the above embodiment, the route cost information is accumulated in the packet when passing through the bridge link. In the above-described embodiment, the route cost information is included in the existing control packet.

In the eleventh embodiment, the step of operating the first wireless mesh network and the second wireless mesh network, and via the first bridge link and the second bridge link connecting the wireless mesh networks. , A step of forming a multi-mesh network by forwarding packets between the wireless mesh networks, and a step of manipulating the first bridge link and the second bridge link according to redundancy / failover technology. The eleventh embodiment having the method. In the aforementioned embodiment, this embodiment further includes a step of preventing a transfer loop between the wireless mesh networks. In the above-described embodiment, the step of preventing the transfer loop includes a step of assigning an identifier to the packet. In the aforementioned embodiment, the packet includes a broadcast packet. In the aforementioned embodiments, each identifier has a source address field based on the source address corresponding to the node that generates the identifier. In the aforementioned embodiments, each identifier further has an identification field that uniquely identifies each packet in the context of its associated entry point to the multi-mesh network (related entry point). In the aforementioned embodiment, the relevant entry point is an ingress mesh node. In the aforementioned embodiment, the identifier is included in an existing control packet.

In the eleventh embodiment, the eleventh embodiment further includes a step of eliminating redundant broadcast flooding in each wireless mesh network. In the above-described embodiment, the step of eliminating the redundant broadcast flooding includes a step of assigning an identifier to the packet. In the aforementioned embodiments, each identifier has a packet source address field corresponding to that identifier. In the aforementioned embodiments, each identifier has an identification field that uniquely identifies each packet in the context of its associated entry point to the multi-mesh network (related entry point). In the aforementioned embodiment, the identifier is included in an existing control packet.

In the eleventh embodiment, the eleventh embodiment further includes a step of forwarding packets according to an efficient route based on route cost information, at least in part. In the above embodiment, the route cost information is accumulated in the packet when passing through the bridge link. In the above-described embodiment, the route cost information is included in the existing control packet.

A twelfth embodiment has a computer-readable medium that stores an instruction set, and when the instruction set is executed by a processing element, a function having any one of the first to eleventh embodiments is executed. Will be done.

A thirteenth embodiment comprises a system having a processor and a memory that is configured to store instructions executed by the processor, the instructions comprising any of the first to eleventh embodiments. Implement (execute).

Mesh scaling and interoperability As the size of the radio mesh increases, the transmissions of the radio devices begin to interfere with each other, limiting the use of a single radio frequency throughout the mesh. As a result, the bandwidth available to the nodes in the mesh is reduced. In some embodiments, the relatively large mesh is subdivided into smaller meshes to reduce interference at the same frequency. Each of the smaller meshes is configured to reduce interference from nodes operating on physically close meshes by operating at their own unique (non-interfering) radio frequencies.

Also, as the size of the wireless mesh increases, so does the memory and processing requirements associated with the operation of the mesh routing protocol. Such routing protocol operations include storing information that describes how the wireless mesh reaches the selected node, and determining the next node address as the packet forwarding destination. In some embodiments, the routing protocol resource requirements for large meshes are reduced by subdividing the relatively large meshes into smaller meshes. The smaller meshes operate with routing protocols based on the constraints associated with each of them. Dividing a relatively large mesh into smaller meshes in this way improves the scalability of the mesh performance and the cost of operating resources.

In some usage scenarios, advances in mesh technology may also make relatively new mesh network equipment inoperable with relatively older equipment. Similarly, even if the old and new equipment is built with the same or substantially similar technology, different user requirements will require the old and new equipment to have their own settings, capabilities, or both. sell. Some embodiments allow interconnection between dissimilar meshes (by allowing communication between meshes with different internal settings or behavior).

As an example of a usage scenario, consider a mesh network deployed in a large city. Possibly, the mesh network has more than 1000 mesh nodes and is divided into smaller meshes of about 50 nodes each. Each small mesh (or collection thereof) can be deployed independently of each other by different vendors, but the overall network remains operational as a multi-mesh. Various parts of this deployment can be configured for home access and other parts can be configured for business access.

Mesh interconnection and bridging In some embodiments, the wireless mesh can be split into smaller (sub) meshes interconnected via mesh bridge nodes that are partially operated according to the bridging protocol. The first mesh bridge in the first mesh network is coupled to the second mesh bridge in the second mesh network via a point-to-point (wired or wireless) link. The point-to-point link that connects the mesh bridges is called a bridge link. In some embodiments, the bridge link comprises a plurality of point-to-point links, and in some embodiments, the plurality of bridge links allow communication between a pair of meshes. The plurality of links and bridge links improve overall throughput between meshes and optionally load balance within the mesh. In some embodiments, the nodes within each (sub) mesh have a corresponding unique frequency (interfering) so that the nodes of the physically closer (or adjacent) meshes operate less interfered with. It can be configured to operate at frequencies that do not match. In some embodiments, the nodes in the selected (sub) mesh can be configured to operate in the same frequency band or overlapping / interfering frequency bands if interference is not an issue. For example, a bridge link that couples between (sub) meshes and operates in the same or overlapping frequency bands physically sufficiently separates the combined (sub) meshes to substantially prevent interference. be able to.

Multiple mesh behavior Techniques for efficiently manipulating multiple interconnected meshes include techniques for reducing (or eliminating) loops, as well as techniques for optimizing the forwarding of unicast and broadcast packets. As a first example, when meshes are interconnected via looped bridge links, in some usage scenarios, packets passed from one mesh to another are augmented with control information and controlled. The information is used to prevent the packet from being forwarded multiple times in the same loop, and in some usage scenarios, the packet can be forwarded indefinitely (and thus potentially network congestion). Used to prevent (packets) and bankruptcies. In some usage scenarios, one or more loop interconnects can be used to provide redundancy, or multiple customers own different meshes within a multi-mesh and each other between these customers. It may be the result of incorrect installation, such as when there is no adjustment (cooperation).

As a second example, if there are multiple connections between two meshes of a multi-mesh, then allowing the unicast packet to follow the best path throughout the multi-mesh will result in overall multi-mesh efficiency. improves. In other words, bandwidth, latency, and resource utilization are improved by determining the most efficient routes for the entire multi-mesh network rather than individual meshes.

As a third example, in a usage scenario where individual meshes of a multi-mesh deliver broadcast packets by flooding, when the broadcast packet enters the mesh (before transmission to any bridge link), it controls the packet. Contains information. This control information usually occurs because if an equivalent copy of a broadcast packet enters one of the individual meshes via different bridge links, each copy is treated as a different broadcast packet to be flooded. Flooding of redundant broadcast packets can be reduced or eliminated. With this control information, it is possible to suppress unnecessary multiple floods.

As a fourth example, in some usage scenarios where looping between individual meshes of a multi-mesh is possible (eg by a bridge link), control information is included in the packet before transmission across the bridge link. With this control information, it is possible to reduce or eliminate loop operations that would normally occur infinitely between individual meshes and cause failure due to congestion.

FIG. 1 exemplifies some details of various embodiments of a technique that partially follows a bridging protocol in a multi-mesh to reduce (or eliminate) loop occurrence and optimize unicast and broadcast packet flow. It is a diagram. In some usage scenarios, the technique operates with relatively minimal control byte overhead and low protocol complexity without the addition of control packet overhead. The illustrated multi-mesh includes individual meshes, namely mesh 1 121, mesh 2 122, mesh 3 123, and mesh 4. 124 is included. These meshes are bridged via a plurality of bridges exemplified as bridges 1-12 (101-112 respectively). Bridges 1 and 3, like bridges 2 and 4, bridge meshes 1 and 2, respectively. Bridges 9 and 7, like bridges 10 and 8, bridge meshes 4 and 3, respectively. Bridges 12 and 11 bridge meshes 1 and 4, respectively. Bridges 5 and 6 bridge meshes 2 and 3, respectively, via wireless link 130. Ingress mesh node 1 The 141 provides a portal for packets to enter this multimesh, for example from the Internet, local area networks (LANs), wide area networks (WANs), or any other suitable network. Egress mesh nodes 1 and 2 (151 and 152, respectively) provide a portal for packets to exit this multi-mesh, for example to the Internet, LAN, WAN, or any other suitable network. In some embodiments, the node can act as an ingress mesh node and an ingress mesh node simultaneously to provide a portal for packets entering and exiting the multimesh.

As an example of operation, when a mesh bridge receives a broadcast packet from one mesh (such as mesh 1), it forwards the packet to another mesh (such as mesh 2) via a bridge link. Prior to forwarding the packet, the mesh bridge removes from the packet all routing information specific to the mesh (such as mesh 1) that the packet just passed through. The information to be deleted includes path cost information associated with the mesh passage of the mesh (mesh 1, etc.) that the packet passed immediately before. This path cost information is added to the packet in preparation for transfer. The broadcast packet is then forwarded to another mesh.

In this way, information about the path cost is accumulated as the broadcast packet passes through the multi-mesh. The accumulated path cost information corresponds to the packet transfer cost of each mesh that the packet has passed through before the point where this information was calculated (or updated). In some embodiments, an increment is added to the mesh hop count metric for each mesh passed. In some embodiments, a mesh cost metric is calculated and stored for each mesh passed. In some embodiments, a mesh metric type that describes the cost metric associated with the mesh is stored for each mesh passed. In some embodiments, the minimum link metric across all links is used as the path metric. The routes are compared based on the metric. In some embodiments, the comparison is partly based on the metric value, and in some embodiments, the comparison is partly based on the mesh metric type. In some embodiments, the mesh metric type acts as a (implicit) metric value (for example, in the context of "high bandwidth" and "low bandwidth" mesh metric types).

In some embodiments, a bridge table with one entry for each bridge node is used. Each entry contains the address and status of the destination bridge and the next hop bridge address list. Each element of the next hop bridge address list includes the cost to the destination bridge through the bridge identified by each next hop bridge address and the status of the bridge links attached to each of those next hop bridges. Is done.

When an Egress Mesh node receives a (redundant) copy of a broadcast packet (for example, because it has multiple routes to that Egress Mesh node), it compares the path cost of each copy and the overall cost is the best. Determine a route as the route to be used thereafter. In embodiments where the mesh metrics are accumulated separately and one or more metric types are unknown, some routes taken from a given mesh are compared.

Mesh bridges and egres mesh nodes that send and receive broadcast packets learn about the best route through each mesh (in the mesh sequence that the packet has passed through) by examining and processing the control information contained in the packet. .. The learned best route includes the ingress mesh node of the broadcast packet and the best route between each of the mesh bridges and the egress node that forwards the broadcast packet. The control information includes path cost information added when the packet is transferred through the bridge link, the next bridge which is the packet transfer destination on the route, and optionally along the route. Includes mesh bridge nodes that have passed through. In some embodiments, learning about the best route through said mesh sequence that has passed remains unclear how packets are routed within each mesh (ie, only information about the bridge links that have passed). It is enough). In some embodiments, learning about the best route through the passed mesh sequence is performed using a metric associated with the passed mesh and a metric associated with the next bridge to which the packet is forwarded. It is said. In some embodiments, the metric is a hop count metric and the best route is the route with the minimum number of hops. Because the techniques described elsewhere herein do not rely on the details of best route determination, other metrics may be used in determining the best route based on embodiments-based criteria. ..

The unicast packet is forwarded by the Ingress mesh node to the next mesh bridge along the best path learned during the previous reverse broadcast packet forwarding (from the destination of the unicast packet). When a unicast packet is transferred from a mesh including the mesh bridge, the mesh bridge transfers the unicast packet to an adjacent mesh over the bridge link. If the packet has been forwarded from an adjacent mesh (eg, across a bridge link), the mesh bridge forwards the packet to the mesh bridge on the best route to the destination, or said. When the mesh including the mesh bridge also includes the packet destination (for example, when the packet enters the final mesh to be passed), the packet is transferred to the Egress mesh node. Unicast packets destined for unknown destinations are forwarded as broadcast floods (similar to layer 2 switch flooding), allowing learning of bridge forwarding information for use in forwarding subsequent packets.

An Ingress mesh node, which is the entry point for broadcast packets to enter the multi-mesh, assigns a unique ID to each broadcast packet, which is maintained while the packet is forwarded across the bridge link. This ID can be used for duplicate detection at each mesh node and each mesh bridge, which can prevent loops within each mesh and between multiple meshes. This ID contains two elements. The first element is the address associated with the node that generates the ID, which is a unique value throughout the multi-mesh. The second element is a sequence number (or similar field) that is unique to the broadcast packet as identified by the node that generates this ID and is therefore unique to the broadcast packet. It is not unique to the second element of the ID generated by other nodes. Therefore, this second element (and thus the entire ID) can be independently generated by the nodes. That is, no communication between nodes is required to generate this ID, which is unique in the context of the entire multimesh.

In some operational scenarios, identifiers are assigned to broadcast packets, and in other operational scenarios, identifiers are assigned to unicast and broadcast. A unicast packet receives an identifier, for example, when the packet is originally transmitted as a unicast packet, but the unicast packet has no state of forwarding the unicast packet when it reaches the mesh bridge. In some cases (for example, when the transfer state has expired). Then, the unicast packet is treated as a packet addressed to an unknown destination, and is flooded inside the mesh (similar to the broadcast packet) which is the transfer destination of the unicast packet from the mesh bridge. The unicast packet is then treated as a broadcast packet and is assigned an identifier to prevent loops as part of it.

The individual meshes of a multi-mesh operate according to a variety of characteristics, including routing protocols, routing options, media access control (MAC) layer, and physical access (PHY) layer. The characteristics of each mesh included in the multi-mesh may be different without depending on the characteristics of other meshes of the same multi-mesh. For example, it is possible that the first mesh operates on the first routing protocol and all other meshes operate on different routing protocols. As another example, it is possible for each mesh to operate with a different routing protocol. In yet another example, each mesh may operate with the same routing protocol. Similar variants are possible for other characteristics (routing options, MAC layer, and PHY layer).

The links that enable communication between bridges 5 and 6 are shown as wireless links (such as wireless links such as 802.11 links), but in some embodiments this link may be a wired link (Ethernet®). Links etc.). The links illustrated in some embodiments are representative single links, while the links illustrated in other embodiments are representative of two or more links (wireless, wired, or both). Combined use). In embodiments with two or more links connecting the same two meshes, those two or more links are operated in a load balancing mode, a failover / redundancy mode, or both.

Node hardware and software FIG. 2 exemplifies a part of the details of the hardware aspect of one embodiment of the node. This node, shown in the figure, includes a processor 205 connected to various types of storage devices, including volatile read / write memory "memory bank" elements 2011-2, through DRAM memory interface 202, and non-volatile read / write flash memory. Includes 203 and EEPROM 204 elements. The processor further provides an Ethernet® interface 206 that provides multiple Ethernet® ports 207 to establish a wired link and a wireless interface that provides wireless (radio) packet communication to establish a wireless link. It is connected to 209. In some embodiments, the wireless interface is an IEEE. Compliant with 802.11 wireless standards (802.11a, 802.11b, 802.11g, etc.). In some embodiments, the radio interface operates (in conjunction with any combination of hardware and software elements) and collects statistics on nearby mesh nodes. The statistic can include any combination of signal strength and link quality. In some embodiments, the radio interface can be configured to drop all packets below the configurable Received Signal Strength Indicator (RSSI) threshold. The illustrated partition is merely an example, and other equivalent node embodiments are possible.

The illustrated node functions as any one of the nodes in Figure 1, including the Ingress mesh node, the Egress mesh node, and the bridge. The wireless interface of FIG. 2 allows communication with the nodes inside the mesh (not explicitly shown in FIG. 1, but is assumed to be an element of each of mesh 1, 2, 3, and 4). .. The wireless interface can also provide a wireless bridge link when the node according to FIG. 2 is used as a bridge node, eg, one of bridges 1-12 in FIG. The Ethernet® interface of FIG. 2 is for wired bridge links (including load balancing bridge links or redundancy / failover bridge links) in the embodiment according to FIG. 1 having one or more wired links. Ethernet® ports can be provided. Using one or more of the Ethernet® ports provided by the Ethernet® interface, if the node according to Figure 2 acts as an Ingress (Egress) mesh node, packets entering and exiting the mesh Routes can also be provided. Based on various usage scenarios, any combination of storage elements (DRAM, flash, and EEPROM) can store one or more bridge tables.

During operation, the processor reads and executes instructions from any combination of the storage elements (DRAM, flash, and EEPROM). Some of these instructions correspond to the software associated with the operation of the bridge link in conjunction with the bridge link protocol. Part of the bridge link protocol controls the operation of any combination of the wireless interface and the Ethernet® interface. The accumulated path cost information can be stored in any combination of the storage elements according to the instructions executed in the processing related to the bridge link protocol.

FIG. 3 exemplifies a part of the details of the software aspect of the embodiment of the node. The software illustrated includes Network Interface Manager 302 and Fault, Configuration, Accounting, Performance, Fault, Configuration, Accounting, Performance, and Security: FCAPS) Network Management that works with Manager 303 System: NMS) Manager 301 is included. In some embodiments, the NMS is an interface between management software running outside the node and software running inside the node (various applications, FCAPS, etc.). The network interface manager manages the physical network interface (such as a node's Ethernet interface or wireless interface). This network interface manager assists the NMS in passing dynamic configuration changes (requested by the user) to FCAPS via the management software. In some embodiments, FCAPS includes a function for storing and reading setting information, and the FCAPS function works with all applications that continuously require setting information. FCAPS also assists in collecting failure information, statistics, and performance data from various operating modules of the node. FCAPS passes the collected information, statistics, and any part of the data to the NMS.

Kernel interface 310 acts as an interface between the manager of layer 311 for routing and transport protocols and the manager of flash file system module 313. The routing protocol includes the bridge link protocol and a portion of software related to the management and reference of bridge tables. The transport protocol includes TCP and UDP. The flash file system module serves as an interface with the flash driver 316, which is conceptually illustrated in the state of being connected to the flash hardware element 323, and the flash hardware element 323 is the flash element and EEPROM element of FIG. It represents a flash file system that is stored in any combination. Layer 2 abstraction layer 312 serves as an interface between the routing protocol and the transport protocol and the Ethernet (registered trademark) driver 314 and the wireless driver 315, respectively. The Ethernet driver is conceptually illustrated connected to the Ethernet interface 326, which represents the Ethernet interface of FIG. The wireless driver is conceptually illustrated in a state of being connected to the wireless interface 329 representing the wireless interface of FIG. In some embodiments, the software may also include serial drivers. The software is stored on a computer-readable medium (eg, any combination of the DRAM, flash, and EEPROM elements described above) and executed by the processor. The shown partition is just an example, and many other equivalent layer configurations are possible.

Conclusion Although some of the above embodiments have been described in detail for the purpose of clarifying understanding, the present invention is not limited to the details provided above, and many alternative embodiments are possible. The disclosed embodiments are exemplary and not limiting. It will be appreciated that its structure, construction, and use are consistent with the present disclosure and that many variations within the scope of the claims attached to the registered patent are possible. For example, the bit widths of interconnects and functional units, clock speeds, and the type of technology used are generally different for each component block. The order and composition of the steps and functional elements of the flow chart generally varies from case to case. In addition, unless otherwise specified, the specified value range, maximum and minimum values used, or other specific specifications (such as integration / integration technology and design flow technology) are merely examples. It should not be construed as limiting the present invention as it is of a specific embodiment and the techniques of the embodiments can be expected to be improved and modified.

When implementing (implementing) various components, subsystems, functions, actions, routines, and subroutines, functionally equivalent techniques known to those of skill in the art may be used instead of the techniques exemplified. The names given to interconnects, logic, functions, and routines are merely exemplary and should not be construed as limiting the disclosed concepts. Needless to say, many functional aspects of a design are hardware (generally dedicated circuits) or software (depending on some aspect of a programmed controller or processor), with design constraints depending on the embodiment, and more. Fast processing technology trends (promoting the migration of features previously contained in hardware to software) and higher integration densities (promoting migration of features previously contained in software to hardware) Can be implemented as a function of). Specific variants include (but are not limited to) different networking technologies (eg, wired / wireless, protocol, bandwidth), while other variants include proprietary engineering techniques and It is expected to occur when implementing (implementing) the concepts disclosed herein in accordance with the business constraints of a particular application.

The embodiments exemplify a number of aspects of the disclosed concept with far more details and environmental context than the minimum required embodiments. Those skilled in the art will appreciate that in variants of the invention, omitting the components disclosed herein can leave the basic mode of cooperation between the remaining elements unchanged. .. Therefore, it goes without saying that it is not necessary to implement (implement) various aspects of the disclosed concept for most of the disclosed details. As long as the remaining elements are distinguishable from the prior art, the omitted components do not limit the concepts disclosed herein.

No such modification in the design is a substantial change to the content disclosed in the illustrated embodiments. Needless to say, the concepts disclosed herein have wide applicability to other networking and communication applications and are not limited to the particular application or industry of the illustrated embodiments. As such, the invention should be construed as including all possible modified (modified) and modified forms within the scope of the claims attached to the registered patent.

Various embodiments of the present invention are disclosed in the following detailed description and accompanying drawings.<figref num="1">FIG. 1 is a partial selection of details of various embodiments of a technique for reducing (or eliminating) loop occurrence in a multi-mesh and optimizing unicast and broadcast packet flow.</figref><figref num="2">FIG. 2 exemplifies a part of the details of the hardware aspect of one embodiment of the node.</figref><figref num="3">FIG. 3 exemplifies a part of the details of the software aspect of the embodiment of the node.</figref>