Route optimization for on-demand routing protocols for mesh networks

Areas: Mesh networks need further progress to improve their performance, efficiency, and practicality. The embodiments described elsewhere herein allow for that 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, products, 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.

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 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 the registered patent.

In some embodiments, the on-demand routing protocol for the mesh network discovers the route only if the node with which it needs to communicate does not have a valid route to the destination. Therefore, if a node moves or a new node joins the network and the network topology changes, and that change provides a better route to available destinations, the node is currently in use. Unless the route is disconnected, the routing protocol will not find and use a better route. In various embodiments, a set of low overhead mechanisms is implemented (implemented), even if the route currently used by the protocol is not disconnected, if a better route becomes available. Enable the on-demand routing protocol to perform route accumulation during the discovery flood (discovery flood). In other words, this mechanism (ie, "route optimization") can improve the route even if the functioning route is available. This route optimization mechanism enables nodes in the network that passively learn routing information to notify nodes that need to be aware of significant changes in routing information. In some embodiments, the learning of routing information about the latest route and the determination of the nodes that will benefit from that information are performed without exchanging explicit control packets. One of the route optimization mechanisms is communication of information describing the improved route from a node which is a branch point between an improved route and an unsuitable route.

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, for example, being 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 a mesh or nodes that are part of a mesh to communicate with nodes that are part of a shared access network or that are reachable via a 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.

In the first embodiment, a step of determining a first route and a second route from a source node to a destination node, a step of comparing the first route and the second route, and a step of comparing the first route and the second route. A first embodiment comprising a method having a step of notifying an improved route if the second route is better than the first route. In the aforementioned embodiments, the comparison is based on the number of hops between nodes. In any of the aforementioned embodiments, the communication step is conditional on the number of retries being less than a predetermined threshold. In any of the aforementioned embodiments, the communication process is initiated by a node at a position where the first path and the second path diverge. In the above-described embodiment, the node that starts the communication is at a position where the first route and the second route first branch. In the first embodiment, the first node that determines the first route and the second node that determines the second route are different nodes or the same node. In the first embodiment, the first node that determines the first route and the source node are different nodes or the same node. In the first embodiment, the second node that determines the second route and the destination node are different nodes or the same node. In the first embodiment, at least one of the first route and the second route is limited to a single link. In the first embodiment, at least one of the first route and the second route has a plurality of links. In the first embodiment, at least one of the first route and the second route passes through a single node. In the first embodiment, at least one of the first route and the second route passes through a plurality of nodes.

In the first embodiment, the step of notifying the improved route is non-selective. In the first embodiment, the step of notifying the improved route is selective. In the aforementioned embodiments, the selective communication is transmitted to at least one of a node that is actively communicating and a node that is selectively identified. In the aforementioned embodiment, the embodiment further comprises a step of identifying at least one of the actively communicating node and the selectively identified node. In the aforementioned embodiments, the selectively identified nodes provide services. In the aforementioned embodiments, the service has at least one of an internet interconnection service and a web proxy service.

In a second embodiment having all the elements of the first embodiment, the second embodiment further comprises a step of collecting route information used to determine the second route. In the second embodiment, the step of collecting the route information is active or passive. In the above-described embodiment, the step of actively collecting the route information includes a step of acquiring the route information in response to the transmission of the control packet associated with the collection of the route information, and the passive route. The process of collecting information does not involve the transmission of control packets. In any of the second embodiment and subsequent embodiments described above, the route information has information about the topology of the mesh network. In any of the second embodiment and subsequent embodiments described above, the route information has accumulated route information.

In a third embodiment having all the elements of the second embodiment, the collected route information has a first network address of a first node that determines the first route. In the aforementioned embodiment, the collected route information further has a second network address of the second node that determines the second route. In the aforementioned embodiment, the collected route information has a third network address of a third node that transfers traffic from the first node to the second node along the third route.

The fourth embodiment has a computer-readable medium that stores and has an instruction set, and when the instruction set is executed, a function is executed, and the function is performed from a source node to a destination node. It was improved when the step of determining the first route and the second route, the step of comparing the first route and the second route, and the second route being better than the first route. A fourth embodiment having a step of notifying a route. In the aforementioned embodiments, the comparison is based on the number of hops between nodes. In any of the fourth embodiment and subsequent embodiments described above, the communication step is conditional on the number of retries being less than a predetermined threshold. In any of the fourth embodiment and subsequent embodiments described above, the communication process is initiated by a node at a position where the first path and the second path diverge. In the above-described embodiment, the node that starts the communication is at a position where the first route and the second route first branch.

In the above-described embodiment, the node that initiates the communication is at a position where the first route and the second route first branch. In the fourth embodiment, the first node that determines the first route and the second node that determines the second route are different nodes or the same node. In the fourth embodiment, the first node that determines the first route and the source node are different nodes or the same node. In the fourth embodiment, the second node that determines the second route and the destination node are different nodes or the same node. In the fourth embodiment, at least one of the first route and the second route is limited to a single link. In the fourth embodiment, at least one of the first route and the second route has a plurality of links. In the fourth embodiment, at least one of the first route and the second route passes through a single node. In the fourth embodiment, at least one of the first route and the second route passes through a plurality of nodes.

In the fourth embodiment, the step of notifying the improved route is non-selective. In the fourth embodiment, the step of notifying the improved route is selective. In the aforementioned embodiments, the selective communication is transmitted to at least one of a node that is actively communicating and a node that is selectively identified. In the aforementioned embodiment, the embodiment further comprises a step of identifying at least one of the actively communicating node and the selectively identified node. In the aforementioned embodiments, the selectively identified nodes provide services. In the aforementioned embodiments, the service has at least one of an internet interconnection service and a web proxy service.

In a fifth embodiment having all the elements of the fourth embodiment, the fifth embodiment further comprises a step of collecting route information used to determine the second route. In the fifth embodiment, the step of collecting the route information is active or passive. In the above-described embodiment, the step of actively collecting the route information includes a step of acquiring the route information in response to the transmission of the control packet associated with the collection of the route information, and the passive route. The process of collecting information does not involve the transmission of control packets. In any of the fifth embodiment and subsequent embodiments described above, the route information has information about the topology of the mesh network. In any of the fifth embodiment and subsequent embodiments described above, the route information has accumulated route information.

In a sixth embodiment having all the elements of the fifth embodiment, the collected route information has a first network address of a first node that determines the first route. In the aforementioned embodiment, the collected route information further has a second network address of the second node that determines the second route. In the aforementioned embodiment, the collected route information has a third network address of a third node that transfers traffic from the first node to the second node along the third route.

In a seventh embodiment having a system with a wireless mesh network having at least two nodes, each said node has a radio interface that allows communication with at least two other nodes, and each said node. Each has a processing element that executes the function of the wireless mesh network, and the function is determined by a routing function that determines a route between two nodes of the wireless mesh network and two that are determined by the routing function. It has a route comparison function for comparing routes and a route distribution function for controlling the distribution of route information to the nodes of the wireless mesh network, and the route distribution function indicates that a better route can be used. If the comparison function indicates, deliver the new route. In the above-described embodiment, the route comparison function compares the number of hops between nodes. In any of the seventh embodiment and subsequent embodiments described above, the distribution is conditional on the number of retries being less than a predetermined threshold. In any of the seventh embodiment and subsequent embodiments described above, the distribution is initiated by a node at a position where the new route branches off from the previous route.

In the above-described embodiment, the node that initiates the communication is at a position where the first route and the second route first branch. In the seventh embodiment, the first node that determines the first route and the second node that determines the second route are different nodes or the same node. In the seventh embodiment, the first node that determines the first route and the source node are different nodes or the same node. In the seventh embodiment, the second node that determines the second route and the destination node are different nodes or the same node. In the seventh embodiment, at least one of the first route and the second route is limited to a single link. In the seventh embodiment, at least one of the first route and the second route has a plurality of links. In the seventh embodiment, at least one of the first route and the second route passes through a single node. In the seventh embodiment, at least one of the first route and the second route passes through a plurality of nodes.

In the seventh embodiment, the step of notifying the improved route is non-selective. In the seventh embodiment, the step of notifying the improved route is selective. In the aforementioned embodiments, the selective communication is transmitted to at least one of a node that is actively communicating and a node that is selectively identified. In the aforementioned embodiment, the embodiment further comprises a step of identifying at least one of the actively communicating node and the selectively identified node. In the aforementioned embodiments, the selectively identified nodes provide services. In the aforementioned embodiments, the service has at least one of an internet interconnection service and a web proxy service.

In an eighth embodiment having all the elements of the seventh embodiment, the eighth embodiment further comprises a step of collecting route information used to determine the second route. In the eighth embodiment, the step of collecting the route information is active or passive. In the above-described embodiment, the step of actively collecting the route information includes a step of acquiring the route information in response to the transmission of the control packet associated with the collection of the route information, and the passive route. The process of collecting information does not involve the transmission of control packets. In any of the eighth embodiment and subsequent embodiments described above, the route information has information about the topology of the mesh network. In any of the eighth embodiment and subsequent embodiments described above, the route information has accumulated route information.

In a ninth embodiment having all the elements of the tenth embodiment, the collected route information has a first network address of a first node that determines the first route. In the aforementioned embodiment, the collected route information further has a second network address of the second node that determines the second route. In the aforementioned embodiment, the collected route information has a third network address of a third node that transfers traffic from the first node to the second node along the third route.

Routing information and discoveries Nodes retain and partially use routing information when implementing various networking protocols. Routing information is discovered during the operation of the network and transmitted between nodes. The network topology changes over time (due to node movements, node comings and goings, changes in environmental conditions affecting communication between nodes, etc.), new routing information is learned, and in some cases active according to embodiments. Delivered via any combination of technology (including control packet transmission) and passive (not including control packet transmission) technology.

Routing information Each node in the mesh network implements a data structure such as a "route cache" that describes the links in the network that have been learned by that node. Nodes use various techniques to combine their link information to create routes. Next, the source node uses the route information to transmit packets to various destination nodes, including a node separated from the source node by a plurality of hops.

FIG. 1 exemplifies some details of embodiments of a mesh network and related route calculations, routes passing through the network, and various entries included in the route cache. More specifically, this mesh network has nodes "S" 100S, "A" 100A, "B" 100B, "C" 100C, "D" 100D, "E" 100E, "F" 100F, "G". Includes 100G, "H" 100H, and "J" 100J. The route is illustrated by starting with "S" and reaching "D" via "B", "E", "F", and "J". The route caches implemented by "S" are ("S", "A"), ("S", "B"), ("B", "E"), ("E", "F"). Describe various links within the network, including, ("F", "J"), ("J", "D"), and ("G", "H"). There is a route from "S" to "D", [("S", "B"), ("B", "E"), ("E", "F"), ("F", It can be expressed as "J"), ("J", "D")].

Discovery of routing information A node that participates in a mesh network and implements an on-demand routing protocol (a node that participates in the mesh network is also known as a "mesh node"), while performing processing associated with sending packets to the destination. Examine the route cache provided within that node. If the route cache lacks information that describes the route to the destination, the node acting as the source will "Route Discovery" to find the route. In this route discovery, a "route request" (Route) is broadcast by the source and then rebroadcast by all nodes that receive this route discovery. Request) Flood is implemented first. The rebroadcast operation continues until all nodes in the network are flooded with the route discovery. In an embodiment in which a routing protocol for accumulating routes during route discovery is implemented (implemented), as the route request is transferred by each node, each node associates the address of the node with the route request. Add to the address list in the packet header. As a result, each node that receives the route request is provided with information that describes the node that transferred the copy of the route request so that each node can "learn" about all the links that the route request has passed. Become.

When the route request packet reaches the destination, the route request packet includes a list (route) of nodes / links from the source node to the destination node. The destination node then "routes" the route. Reply) Placed in a packet, this route response packet is transmitted to the source of the route discovery, and the source is notified of the link and the route discovered as part of the route discovery. Since the route response is transmitted to the source, the communication destination of the updated routing information is inevitably limited to the source (and the node on the route from the destination to the source). The node. In some embodiments, the route response information is optionally transmitted to a selected additional node other than the source. In some embodiments, the additional node selected to receive route response information is identified by the user. In some embodiments, the additional node is selected based on the provider's identity of the service, including any combination of internet interconnections and web proxies. In some embodiments, the additional node is identified as a node that is likely to require or benefit from new route information in the near future.

FIG. 2 exemplifies a part of the details of one embodiment of the mesh network route discovery process including the route request and the route response. More specifically, this mesh network includes "S" 100S, "A" 100A, "B" 100B, "C" 100C, "D" 100D, "E" 100E, "F" 100F, " Includes "G" 100G, "H" 100H, and "J" 100J. The route discovery operation is started by the node "S" and transmitted to the destination node "D". Here, as illustrated in Route Requests 210SA, 210SB, 210AC, 210CG, 210GH, 210GJ, 210GF, 210HD, 210JD, 210FJ, 210EF, and 210BE, only one copy of the Route Request flood is forwarded by each node. Consider the scenario. If the first copy of the route request that has reached "J" is from node "F" and the first copy of the route request that has reached "F" is from node "E". Except for ("G", "J") and ("G", "F"), all illustrated links are learned by "D". The route response is generated by node "D" and as illustrated in the route responses 220DJ, 220JF, 220FE, 220EB, and 220BS ["S", "B", "E", "F", "J", "J", " Returns the route described as "D"].

In some usage scenarios, different copies of the route request follow different routes within the network. As a result, the node may receive more than one route request belonging to the same route discovery. To enable duplicate detection, the source of the route request includes a sequence number unique to the source in the route request. Next, the forwarding node uses the sequence number to identify route request packets belonging to the same route discovery. In some embodiments, the node implements a routing request table that includes an entry with source address and corresponding sequence number information. This route request table is updated when a route request is received and is searched to identify duplicate route requests. In some embodiments, each node in the mesh transfers a route request by a certain number of copies when processing a given route discovery. This constant number may be 1, 2, 3, or any other number similar thereto, according to various embodiments. In some usage scenarios, one or more copies of the route request follow different routes. In that case, during a single route discovery, the destination of the route discovery can learn a plurality of routes to the source (a plurality of routes to the initiator of the route discovery). In some embodiments, multiple copies of the route request are forwarded, so that there may be only one route, or potential additional routes are temporarily unrecognizable due to intermittent packet loss. Even in such cases, the possibility of finding multiple routes increases.

The information received in response to a route request represents the state of the network over the time it takes for the route request to be transmitted and reach the target. As the network topology changes over time, different route requests sent before and after the period collect different information. Changes in network topology are environmental conditions that move nodes from one physical location to another, adding or removing nodes from the network, or improving (or worsening) communication between some nodes. Can be the result of a change. In general, changes in network topology are discovered and learned as route requests travel through the network. A more efficient route (eg, in the context of a route cache) replaces a more inefficient route, and a feasible route replaces an inoperable route.

For example, the first node that enables the first route between the source and the target can operate during the first time when the first route request is active in the network. In this example, the second node that enables the second route between the source and the target is operational during the second time when the second route request is active in the network ( And it is inoperable during the first time). If the second time is after the first time and the second path is more efficient than the first path, the node learns the second path and is more inefficient. The information about the second route will be used to replace the information about the first route.

Route optimization During the route discovery flood, a node in a network learns about the links currently available in the network and the characteristics associated with that node, the link, or both. These characteristics or information may be useful not only to the destination of the route discovery, but also to other nodes in the network that are transmitting the traffic. The information is provided because new and better routes may be available within the network as a result of node movement, changes in link characteristics, or other similar changes made to the mesh network. It is useful. Below, some of the mechanisms of "route optimization" that improve network performance using the above information are selected and summarized.

When an arbitrary route discovery flood is received, the node that is the destination of the active flow from the route discovery source examines the route request packet associated with the route discovery flood and determines if there is a new link ( Or learn). The destination node then asks if any of the new links (optionally combined with routing information already known by the destination) is an improved route for the source of the route request. Please check. If so, the destination node returns a route response with a better route to the source of the flood.

In usage scenarios where computational power is relatively unconstrained (freely available), a node optionally recalculates a route to one or more nodes (or all nodes) that are active partners of that node. To do. The recalculated route is compared to the currently known route. If a better route is found, a route response is sent to all nodes accessible via each. In some embodiments, the route comparison includes a step of comparing the number of hops of the route to be compared. As a result, a route response is provided to each node for which an improved route is available. In some embodiments, the initiation of the routing response is optionally rate limited so as to limit the routing response packets sent to one or more nodes.

In some embodiments, in each node, for all active communication flows (or any part thereof) of which the node is the source, destination, or forwarding node, periodically all routes (or any part thereof). ) Is recalculated. Each node then optionally compares the recalculated route to a previously known route to determine if a better route is available. If the node is the source of traffic and a better route is found on that node, the node will immediately begin using the better (or new) route. When the node is a destination, the node can send a route response to the source of the flow. If the node is the node that forwards the traffic flow, the node can compare the new (better) route with the route currently used by the flow. If the next hop to the source of the flow via the new route is different from the next hop to the source via the current route, a route response is transmitted. Therefore, only the node at the position immediately before the new route and the current route start to differ may send a route response, and the improved route may be detected in a plurality of nodes, but it is better than the newly detected node. Only one route response is sent per route (or shortened). If the source of the flow continues to use the old route, the corresponding route response is transmitted. In some embodiments, there are several usage scenarios where the source is using a less optimal (or appearing to be) route for some reason that is not known to the forwarding node. After the trial, the transmission of the route response is stopped.

FIGS. 3A and 3B exemplify a time-series operation diagram of a part of one embodiment of mesh routing optimization selected. More specifically, FIG. 3A shows the nodes "S" 300S, "A" 300A, "B" 300B, "C" 300C, "D" 300D, "E" 300E, "F" 300F, and "J". This is an example of a mesh network including 300J. When node "S" performs route discovery to node "D" (as illustrated in Route Requests 310SA, 310SB, 310AC, 310AB, 310BE, 310EF, 310FJ, and 310JD, each node is a copy of each route request. (In a usage scenario that transfers two or more), the nodes "B", "E", and "F" learn about the ("S", "A") links. Here, when the best route between the node "S" and the node "D" is determined as ["S", "B", "E", "F", "J", "D"]. Considering that, node "S" routes packets to node "D" using the route ["S", "B", "E", "F", "J", "D"]. ..

FIG. 3B illustrates the mesh network of FIG. 3A at a time point after FIG. 3A, where node "A" can move and communicate with node "F" (links can be established and maintained). And still has links with nodes "S" and "C". When node "C" initiates route discovery (to any node), nodes "F", "J", and "D" learn about a better route that can reach "S" via "A". To do. Examples of route discovery initiated by node "C" are illustrated with route requests 330CA, 330AS, 330AF, 330FJ, 330JD, 330FE, 330EB, and 330BS. During periodic route recalculation, nodes "F", "J", and "D" each detect shorter routes. However, since the node just before the route starts to be improved (shortened) is the node "F", only the node "F" is the new route ["S", "A", "F", "J". , "D"] is sent to "S" (shown in Route Responses 320FA and 320AS). By sending a route response from the selected node where the old and new routes start to differ, a better route may be detected on more than one node, but for the newly detected better route. , Make sure only one route response is sent.

In the above description, the best route is the route with the shortest hop count metric. However, since the techniques described above do not depend on the details of the best route determination, other metrics may be used in determining the best route based on the criteria according to the embodiment.

In some embodiments, the processing related to the route response transmission from the selected node includes background processing of the link information learned by all the floods (or any part thereof) transmitted from the arbitrary node within a certain period of time. It may also include, and optionally, the processing of information about new links in the vicinity. Computational overhead only occurs when new or better routes are not available (processing is "wasted" in that there is no improvement). If an improved route is discovered and notified, there will be a small amount of control packet overhead (route response packet traffic). In some embodiments, a node that is actively transmitting traffic periodically emits a routing discovery flood that does not have a specific target destination, so that a routing discovery flood would not normally occur. Provides an opportunity for routing information to be refreshed (or improved).

In some embodiments or usage scenarios, route discovery is about a single target, i.e., aimed at finding a route to one destination. In some embodiments or usage scenarios, route discovery is about multiple targets, i.e., aimed at finding routes to multiple destinations. When the route discovery is related to a single target, the route to be discovered is known at that time, and the address of the target (or destination) is not included in the accumulated route information. The accompanying route request is not transmitted by the target. When the route discovery is related to two or more targets, the route request associated with the route discovery is arbitrary because each target does not recognize whether or not all the targets have received the route request associated with the route discovery. Transferred by a number of targets.

The techniques exemplified by the above embodiments are applicable not only to mesh networks (wired and wireless) and ad hoc networks (wired and wireless), but also to other similar self-organized networks and networks with aging topologies. Is.

Node hardware and software FIG. 4 exemplifies a part of the details of the hardware aspect of the embodiment of the node. This node, shown in the figure, includes a processor 405 connected to various types of storage devices, including volatile read / write memory "memory bank" elements 401.1-2, through DRAM memory interface 402, and non-volatile read / write flash memory. 403 and EEPROM 404 element are included. The processor further provides an Ethernet® interface 406 that provides multiple Ethernet® ports 407 to establish a wired link and a wireless interface that provides wireless (radio) packet communication to establish a wireless link. It is linked to 409. 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.

These illustrated nodes function as one of the nodes illustrated in Figures 1, 2, 3A, and 3B. The wireless interface of Figure 4 enables communication between nodes and provides low-level transport for route request and route response packets.

During operation, the processor reads and executes instructions from any combination of the storage elements (DRAM, flash, and EEPROM). Some of the instructions correspond to software associated with route request, route response, and route optimization operations. The route cache information can be stored in any combination of the storage elements according to the instruction executed in the processing related to the route response processing.

FIG. 5 exemplifies a part of the details of the software aspect of the embodiment of the node. The software illustrated includes Network Interface Manager 502 and Fault, Configuration, Accounting, Performance, Fault, Configuration, Accounting, Performance, and Security: FCAPS) Network Management that works with Manager 503 Software: NMS) Includes Manager 501. Kernel interface 510 acts as an interface between the manager of layer 511 for routing and transport protocols and the manager of flash file system module 513. The routing protocol includes a part of processing related to route request generation, route response interpretation, and route cache management. The transport protocol includes TCP and UDP. The flash file system module serves as an interface with the flash driver 516 conceptually illustrated in the state of being connected to the flash hardware element 523, and the flash hardware element 523 is the flash element and EEPROM element of FIG. It represents a flash file system in which storage is performed in any combination. The layer 2 abstraction layer 512 serves as an interface between the routing protocol and the transport protocol and the Ethernet (registered trademark) driver 514 and the wireless driver 515, respectively. The Ethernet driver is conceptually illustrated connected to the Ethernet interface 526, which represents the Ethernet interface of FIG. The wireless driver is conceptually illustrated in a state of being connected to the wireless interface 529 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 allow a number of variants within the claims attached to the registered patent. For example, the bit width of the interconnect and functional units, the clock speed, 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 exemplifies some details of embodiments of a mesh network and related route calculations, routes passing through the network, and various entries included in the route cache.</figref><figref num="2">FIG. 2 exemplifies a part of the details of one embodiment of the mesh network route discovery process including the route request and the route response.</figref><figref num="3A">FIGS. 3A and 3B exemplify a time-series operation diagram of a part of one embodiment of mesh routing optimization selected.</figref><figref num="3B">FIGS. 3A and 3B exemplify a time-series operation diagram of a part of one embodiment of mesh routing optimization selected.</figref><figref num="4">FIG. 4 exemplifies a part of the details of the hardware aspect of the embodiment of the node.</figref><figref num="5">FIG. 5 exemplifies a part of the details of the software aspect of the embodiment of the node.</figref>