Method and system for providing a network and routing protocols for utility services

The invention relates generally to networks and computer systems based on networks and, more specifically, relates to a method and a system for providing a network and routing protocols for utilities and household services.

Methods and systems are known for configuring the packet routing mode from a source to a destination in a wireless network comprising a plurality of nodes (US 2006/0125582, WO 2007/034313).

The technical problem that the invention solves is increasing the flexibility of routing data packets over a wireless network.

This problem is solved by the fact that any node can select one of several routing paths, which are stored in a table so that, if a link on the preferred route is unreliable, one of the alternative routes is chosen.

The invention provides a routing scheme and protocols from an RF network (a wired or wireless LAN network) operating in FHSS mode, to enable two-way communication between utility and home devices (such as electric meters, power meters). water, gas meters, Automatic Distribution Devices (DA) and basement devices), which are IP hosts in the RF LAN network, by interconnecting with the Host Utility System (also known as the Administration Server or Back Office System - BOS) which is an IP host from a wireless or WAN (Broadband Network) infrastructure. The IP version of the illustrative example is IPv6. IPv6 packets are encapsulated in IPv4 for WAN cloud transmission, usually based on IPv4. The method of routing IPv6 packets within the wireless LAN includes providing an Access Point (PA) that can perform encapsulation (for example, IPv6 in IPv4 packets) in its ability to gateway between LAN and WAN, and providing a multitude. of IPv6 endpoints or devices that appear as being directly connected to the PA access point at IPv6 level.

From the physical point of view, the endpoints or devices are capable of establishing radio transmission routes directly to the PA access point (single jump to the PA access point) or to other IPv6 devices (multiple jumps to the PA access point). , and the algorithm and methods according to the present invention describe how the network topology is created between the PA access points and the packets using the data link layer (Layer 2 of the OSI model). Devices or nodes become available, discover available networks, select networks to be coupled, choose an ordered set of viable ascending candidates, as the next jump on their targeting scheme, register with ascending nodes having the best route and cost of the link and , finally, it is registered with PA access points, associated with one or more available networks. The process of discovering the network, performed by the nodes, ensures that there are routes for forwarding the packets upstream to the PA access point, for the exit to the Utility Host System, at the same time with the explicit registration with the upstream nodes, and the access points The PA provides the PA with the most up-to-date information about the network and ensures that the traffic can be carried downstream of the node. This is a routing scheme with multiple outputs and multiple inputs, in which a network node can be part of more than one network through one or more PA access points (access gates).

The above features, as well as others, including different implementation details and combinations of elements, are described in detail below, with reference to the attached drawings, in which:

FIG. 1A illustrates the entire network architecture, according to a possible embodiment;

FIG. 1B is an alternative representation of the entire network architecture, according to a possible embodiment;

RO 125809 Β1

FIG. IC is a generalized block diagram of a wireless utility network, according to 1 possible embodiment;

FIG. 2 is a representation of a bit-by-bit structure, of a starting block on the connection layer 3, for a packet that is directed;

FIG. 3 presents the format of the Network Warning message, sent by a node about the 5 best route to a particular network, known by it;

FIG. 4 is a simplified representation of the targeting table, built at level 7 of a node, after it receives the warnings from the neighbors network;

FIG. 5 is an example of a list of routes with different types of routes that may be present 9 at the node level;

FIG. 6 presents the format for an upstream message, sent by 11 a node to another upstream node;

FIG. 7 is an example of a format for an upstream registration acceptance message, sent by the upstream node to the node that wants to register;

FIG. 8 is an example of a format for a PA recording message, sent by 15 a node to a PA with which it wishes to register;

FIG. 9 further illustrates the contents for the description of the neighboring AREG, 17 contained within the PA registration message;

FIG. 10 shows a network in which the end node is connected by several relays to more than one PA access point, which ensures the output in a WAN network;

FIG. 11 is a representation of the order list of the upstream jumps, generated by the node 21 at the end M1041, for the network exit, during the network entry process, illustrated in fig. 10; 23

FIG. 12 illustrates the network of FIG. 11, where a modification of one of the costs of the connection took place; 25

FIG. 13 is a representation of the rearranged list of the jumps upstream, generated by the end node M for the output in a Network, during the process of updating the route in the network 27 illustrated in fig. 13;

FIG. 14 is a network sample in which several access points PA, relays and 29 end point devices appear one at a time;

FIG. 15 shows a map of the costs of the connections between all the nodes that can establish 31 RF communication links with each other, in a possible embodiment;

FIG. 16 provides descriptions of the notations used in fig. 17; 33

FIG. 17 is a summary of the process of determining and propagating the route that occurs when a node is started in the network of fig. 14 to get the link; 35

FIG. 18 describes a network configuration with multiple outputs / inputs for adaptive targeting.37 In the detailed description, for the purpose of explaining, a specific language is provided, to provide a complete understanding of the various inventive concepts disclosed herein. . 39 However, it will be obvious, for a person in the art, that these specific details are not necessary in order to put into practice the different inventive concepts, disclosed in the 41 front.

the lines portions of the following detailed description are presented in terms of the 43 algorithms and the symbolic representations of the operations on data bits inside a computer memory. These descriptions and algorithmic representations are the means used by the specialized persons in the fields of data processing, in order to transfer the essence of their work to other specialized persons in the field most efficiently. An algorithm 47

RO 125809 Β1 is designed in this case and in general to be a standalone sequence of stages in series and in the parallel, leading to the desired result. The stages are those that require manipulation of the physical quantities.

It should be kept in mind, however, that all of these, as well as similar terms, must be associated with appropriate physical sizes and are only appropriate labels, applied to these sizes. Unless specifically stated otherwise, as is evident from the following description, it is appreciated that, during the description, presentations using terms such as processing or computing or calculating or determining or displaying or the like, refer to actions and processes. a computer system or a similar electronic computing device, which manipulates and transfers the data represented as physical quantities (electronic) within the registers and memories of the computer system in other data, similarly represented, as physical quantities, within the memories and registers of the computer system or other such storage, transmission or display devices .

The present invention also relates to an apparatus for performing the operations within the present frame. This device may be built specifically for the purposes proposed or it may comprise an ordinary computer, selectively activated or reconfigured by a computer program, stored in the computer. Such a computer program can be stored on a readable environment, through the computer, such as, but not limited to, any type of disk, including floppy disks, optical disks, CD-ROMs and magneto-optical disks, memory only with readability (ROM), random access memory (RAM), EPROM, EEPROM, magnetic or optical cards, or any type of environment suitable for storing electronic instructions, and each coupled to a computer system channel.

The algorithms, processes and methods presented herein are not associated or restricted inherently to a particular computer or device. Various general-purpose systems, with programs according to the disclosures in the present framework, may be used, or it may prove advantageous to construct a more specialized apparatus for carrying out the steps of the required method. The structure required for a variety of such systems will result from the description below. In addition, the present invention is not described with reference to any particular programming language. It will be appreciated that a variety of programming languages ​​can be used to implement the disclosures of the invention, as described herein.

WIRELESS NETWORK

Referring to FIG. 1A, a communication network includes a plurality of devices 140 and 130 (nodes), connected to each other (at least one or more) and to one or more Access Points 120, within the wireless LAN 160. If not stated otherwise, PA access points may alternatively be referred to as Gateways. In contrast, PA access points may be linked to one or more management systems (BOS) 150, through one or more networks 110, typically Wide Area Networks (WANs). An administration system may be implemented on one or more computing devices, for example, a central server, such as the central server 150, as shown in FIG. 1B, and can be implemented along one or more networks.

Referring to FIG. 1B, the nodes, such as battery powered devices (BPD) 130 and / or constant power devices (CPD) 140, can discover available networks 110, by listening to all the neighbors with whom they can make connections, select one, to which to connect , and can choose a set of upstream variable candidates as their next jump. It is to be noted that, in this preferred embodiment, CPDs may act as intermediary elements for BPD. However, alternative embodiments may allow BPD to directly participate as nodes in the wireless network without an intermediary element.

RO 125809 Β1

Example. The node M-1 is a constant supply device 40, in FIG. 1A, hears about 1 two WAN-1 and WAN-2 networks, of the type of WAN 110 network (with unique IP addresses) from its neighbors, and is registered with both PA-1 and PA-2, of the type of Point Access 120, which provides 3 output to WAN networks. It accomplishes this through the upstream nodes M-5, M-6,

M-18, M-2 and M-12, of the type Constanced Power Device140, for communication with BOS- 5

1, of the Central Server type 150.

Each of these nodes can construct a routing table, with a list of order 7 of the following jumps and the costs associated with the connection (the costs adjacent to the local node and the next jump), and the costs of the route (the cost required for the exit by the next jump). Each 9 node is still registered with the upstream neighbor and access gate 120. Access gate 120 can track the network topology and capabilities of all devices in its control device 11 and also other devices. The nodes can maintain the local state and the status of their close neighbors, and can update their records periodically. 13

WIRELESS UTILITIES NETWORK

The following illustrative embodiment provides a system based on a network and the method 15 for monitoring or controlling a utility meter in a utility network.

Fig. IC is a generalized block diagram, for a utility network 170, which can be used to implement the embodiments of the present invention. Utility network 170 may include one or more electronic devices 171 or nodes. In a preferred embodiment 19, the electronic devices 171 can be connected on a local area wireless network (LAN) 172. Within the example utility network, the LAN can be a 21 neighboring area (NAN) network, corresponding to a neighboring area or utility services.

As illustrated in the illustrative embodiment, multiple LAN networks may be used, 23 which may or may not overlap, so that a given electronic device may be connected to (or may be part of) only a single wireless LAN or on multiple wireless LANs. 25 Nodes can be any type of electronic device. Examples of electronic devices or nodes include utility nodes, which may include a utility counter or can be connected to a 27 utility counter. A utility meter is a device that is capable of measuring a metered size, typically a product such as electricity, water, natural gas, etc. 29 Utility nodes that connect a utility meter may include a network interface card (NIC) for communication over a network, may include one or more RF transmitting / receiving devices 31 for communication on one or more wireless networks. LAN, and may include one or more devices with the utility meter interface (a given utility node 33 may interface with multiple meters, which may or may not count different products, how to draw electricity, gas, water, etc.). Utility nodes can also include an interface 35 for basement devices, to connect the basement devices through a basement network (which may or may not be a wireless network). The interface with the basement device 37 is connected to the basement devices, to ensure the communication link between the utility node and the basement devices. In addition, the utility node can provide a 39 communication link between the basement devices and the wireless communication network connected to the utility node. Other examples of electronic devices include communications devices, 41 such as height-locked boxes (such as those used in cable television or satellite television delivery services), home appliances (eg refrigerators, 43 radiators, light (ni), kitchen appliances), computers or computing devices (for example, game consoles, storage devices, PCs, servers, etc.), network deployment devices, such as relays, access gates, access points, routers or other network deployment devices, telephones or cell phones, battery storage devices, 47

EN 125809 Β1 transport devices, transport vehicles (for example, an electric or hybrid car or other vehicle, which may or may not be able to connect to a utility network to receive a metered / monitored product such as electricity) , entertainment devices (eg TVs, DVDs, height-mounted cassettes, game consoles, etc.) or other device that can be found in a home, office on the freeway or in a parking lot or other location. The relays can manipulate the communication between the electronic devices 171 and the wireless network 172. For example, a relay can ensure the communication between the electronic device and the infrastructure of the wireless network. Unless otherwise stated, other devices within the network, such as meters, electronic devices, access gates, etc., may act as relays, and the relays may perform the functions of other devices or computer programs in the network.

The wireless LAN 172 network can be any type of wireless network and can use any frequency, communication channel or communication protocol, within a preferred embodiment, that one or more wireless LAN 172 networks are the FHSS (Cu) networks. Spectrum scattered with Frequency Jump).

LAN networks 172 are typically connected to one or more access points (PAs) 173. A given LAN may be connected to a single PA access point or may be connected to two or more access points. Access points 173 may be connected to one or more wide area networks (WAN) 174. WAN networks 174 may be connected to one or more management systems (BOS) 175. The management system can handle a variety of business or management tasks, including participating in the collection of metering information, managing the metering devices, network security or other functions, as may be desired in an AMI network. Examples of management systems include billing and accounting systems, intermediary servers, interruption detection systems (such as those used in a utility network), data storage systems, etc.

The nodes in a communication network, which can be a LAN or WAN network or a combination of the two, can communicate, using one or more protocols. Nodes may include an electronic device, a relay, an access point, a router or a BOS. Node lines may be able to communicate using IPv6, some may be able to communicate using IPv4, while some may be able to communicate on both IPv4, IPv6. Some nodes may be able to encapsulate IPv6 packets into an IPv4 packet. In addition, some nodes may be able to establish an IPv4 tunnel over an IPv6 network. The communication between the nodes and the routing, used within the wireless communication network that connects the nodes, is described in more detail below.

In a preferred embodiment, a routing protocol used is a jump-to-hop algorithm with multiple outputs / multiple inputs, to determine an optimal route to / from the destination, which may use a route backbone and / or a history. of stable targeting upstream or downstream, as a metric, for determining the next hop, for targeting a packet. In the present preferred embodiment, no jump accounts are used to evaluate the cost of the route, but are used to prevent the directional loops, as described below. In such an embodiment, a node may select the route with the lowest cost value, as the preferred route for packet forwarding.

In a preferred embodiment, a routing protocol is used in the scanning process, to discover the initial network by the new node, through all slots or channels, to find out (preferably) all the neighbors, and to obtain responses of acceptance and an initial value of the estimative values, regarding the quality of the connection for those

RO 125809 Β1 neighbors discovered. This initial estimate value of link quality can be used to select a number of the best neighbors upstream to discuss (the selected number can be configurable). 3 registering a node with its upstream nodes, in the present preferred embodiment, means that the node intends to use these upstream nodes for outgoing to another network. In response to the registration with the upstream node, the upstream node will add the downstream node that was recorded at the inputs in the table of downstream targeting 7, maintained by the downstream node. The upstream nodes can also proceed with the up-to-date keeping of the timing information regarding node 9 that was registered in response to the downstream node registration. Node routing, one via the other, is preferably set to periodically change 11 timing information, in order to stay in sync and exchange packets on the RF LAN, using FHSS methods. In this embodiment, the time updates 13 are carried on any data transfer messages, but an explicit exchange of time information can be triggered, if there was no data exchange for a preconfigured interval (e.g., on the order of 30 min).

The registration of a node with one or more PA access points can then take place. 17 This registration process will preferably require the PA to add the node that it wants to register in its targeting table and ensure that the node's status is updated. the registration of the node with the PA may occur periodically, but less frequently, than the registration with a node upstream. In the present preferred embodiment, the frequency is of the order, every 12 hours.

ALLOCATION OF AN ADDRESS; AWARDING AN IPv6 ADDRESS 23

Each node 130 and 140, within the wireless communication network, can be identified for end-to-end targeting of any particular network through a unique I Pv6 address. The 25 I Pv6 addresses are usually composed of two logical portions: a 64-bit network prefix and a 64-bit host portion. After successfully registering a node with a PA access point 27, the PA access point can transmit to the node a set of TLVs (Length Type Value) containing the node configuration, including the IPv6 global addressable prefix, associated 29 with the subnet to which joined the knot. Then the node can send a Dynamic DNS Update Request (RFC 2136) to the Network Utility System DNS (BOS) server. 31 When an application server wants to send traffic to the wireless LAN, it can change the DNS name of the node to a Pv6 I layer 3 (IP) address by routing it 33 through the WAN network to the correct PA access point. If the WAN network is based on lPv4, the I Pv6 packets can be encapsulated in I Pv4 with the appropriate prefixes for channeling through an IPv4 cloud. At the BOS level, the received Pv6 packet will be soldered.

A node can register with multiple networks either on the same PA access point, or 37 on multiple PA access points, in which case it can establish the order of priorities for the networks it belongs to, based on its estimates or calculations. at the cost of the lowest route 39. In this preferred embodiment, the node will have an IP address for each network it is registered with. The DNS server can associate these 41 IP addresses not the host name of the node, in a preferred order, in accordance with the policies defined on the DNS server. When the BOS server in the WAN network wants to send traffic to the 43 wireless LAN, the DNS server scans IPv6 addresses to resolve the node host name. As described above, the | Pv4 cloud in the WAN network can be routed 45 by encapsulating the IPv6 packet at the BOS server level in an IPv4 packet, with the appropriate prefix, to allow channeling. 47

RO 125809 Β1

ALLOCATION OF THE ADDRESS OF THE LINKING LAYER

Each node 130 and 140 can be identified by routing in the wireless LAN, through a unique address, for the connection layer assigned to its radio interface. In this embodiment, each node has only one interface. Other embodiments may have multiple discrete addresses for the connection layer. The addresses of the connection layer are usually 8 bits long and represent the MAC address of the device. The radio transmission address of the connection layer can be hex ff: ff: ff: ff: ff: ff (all of them). The packets transmitted with this local radio communication address are preferably processed by each of the recipients.

Further transmission of a packet on the RF link layer

Fig. 2 illustrates the bit composition for the connection layer header, which can carry the information as explained in the table below.

The marking labels, carried by the header of the connection layer, shown in fig. 2, are presented in table 1

Table 1

<td>Bit (i)</td><td>Name</td><td>Description</td>

<td> 0-3</td><td>Version</td><td>Protocol version number. If a larger version is received, the frame is removed.</td>

<td> 4-7</td><td>Protocol ID</td><td>Protocol id on a top layer: - 0x03: SSN targeting protocol; - 0x04: IPv4 network transmission protocol; - 0x06: IPv6 network transmission protocol; - 0x07: follow data link.</td>

<td> 8-12</td><td>Address Counter</td><td>Indicates the total number of addresses contained in the data link header, including source, destination, and any intermediate address, for source-directed packets</td>

<td> 13-17</td><td>TTL</td><td>It is set when the package is generated. The initial value is set to TTL automatically and is configurable. TTL is reduced with each jump that the packet traverses.</td>

<td> 18-22</td><td>Current gap</td><td>Set to 0. for packets that do not use source routes. It is set to 0. when the packet is first sent to the network. It is raised with each jump that the package goes through.</td>

<td> 23-25</td><td>Priority</td><td>The DLC layer supports 8 priority levels, this field falling directly on those priorities.</td>

<td> 26</td><td>Source Route Bit</td><td>Indicates whether the packet contains the entire hop-to-hop route to be used between source and destination.</td>

RO 125809 Β1

Table 1 (continued) 1

<td>Bit (i)</td><td>Name</td><td>Description</td>

<td> 27</td><td>Source Route Conservation</td><td>Established when forwarding code L2 will retain the elements in the source route when forwarding the packet downstream. If this is not established, the forwarding code L2 may decrease the intermediate jump address, once a forwarding decision has been made.</td>

<td> 28-31</td><td>Reserved</td><td>Reserve for future use.</td>

As illustrated in FIG. 2, the labels are followed by the address of the source of the node that 13 generated the packet. In this preferred embodiment, the label source address can never be set as the radio communication address. 15

As illustrated in FIG. 2, the source address is followed by the address of the next hop, on which the packet is to be transmitted. In the present preferred embodiment, 17 if the Source Route bit is set, then the entire list of hop addresses, ending with the destination address, is included, otherwise only one next jump is specified. in each case, the final address is the destination to which the packet must be addressed.

If the source path bit is set, the packet's title file contains the complete route 21 that the packet will follow. It is noteworthy that a packet can be routed from the source between two nodes without intermediate jumps (ie, Add Cnt is 2, and the destination address 23 is either a node or the radio communication address). This is a mechanism that can be used to query individual nodes 130 and 140 from a terminal, such as a mobile devirus station 25.

If the source path bit is not set, the forwarding code L2 from a 27 node can make a decision based on the value of the Address Counter field. For example, if the Address Meter is equal to 1, on a packet to be sent from RF LAN to WAN (117) 29 or Central Server (150), it means that the packet can be forwarded to any output node or point. access PA from the system. If the respective Address Meter is greater than 1, it means that all the additional addresses in the forwarding table further from the node level have the L2 output destinations allowed. The addresses in the forwarding table 33 for a network are sorted, preferably, from the least preferred, to the most desired. 35

If the respective Address Meter is greater than 1, the packet may be redirected to a different destination L2, in the event of congestion or an error. Then 37 when a different L2 destination is selected, the previous network must be removed (either by reducing the Current Gap or assigning the zero value to the previous field). Removing the previous network 39 is intended to help reduce the appearance of targeting loops, where a packet can be re-injected much farther from the destination compared to the original source. 41

Preferably, TTL gets a lower value when a packet passes through L2 of a node. Packets that pass through L2 are lost when 43 TTL becomes zero; zero TTL messages for the local host are delivered from the stack. Nodes 130 and 140, which send messages to the access point PA (access gate) 120, without fully utilizing the preferred source route, must set their TTL so that it is at least

RO 125809 Β1 number of jumps on the longest route leading to PA 120 access point. The maximum TTL can be configured by the administrator. In the present preferred embodiment, the packets sent with the destination address set to be the value of the radio communication

L2, they are not transmitted further.

The preferential delivery of packages is accepted, preferably, by the DLC (Data Link Control) layer. The broadcast packets can be implemented in the form of the packets transmitted preferentially in the FHSS scheme and are also accepted, preferably. Unsupported packets cannot be transmitted preferentially. When a node 130 and 140 sends packets to a neighbor, the MAC layer can report the number of withdrawals and the possible success of the transmission. The network layer can keep records of this information on a per-neighbor basis.

The targeting subsystem within the present preferred embodiment, the targeting subsystem can be divided into four functional components:

- scanning and discovering neighbors;

- preserving the neighbors;

- registering the node with the upstream neighbors;

- registering the node with the PA access point.

The present preferred embodiment of the targeting subsystem uses the entity of the DLF code (Transmission element further on the data link) for Layer 2 and the entity of the MLME (Management Entity of the Substrate of Access Control Media) code for acquiring neighboring nodes and maintaining the information. timing between neighbors. The DLC code is interfaced with MLME through a set of APIs.

SCANNING TO DISCOVER NEIGHBORS

Nodes, such as CPD 140, can initiate network discovery when, for example:

- does not have viable output nodes (it is not associated with any of the PA access points);

- communications with the upstream nodes were interrupted either administratively, due to partial problems or loss of propagation;

- a periodic registration message, at one of its PA access points, failed at least three times;

- a new network is announced.

Nodes, such as BPD 130, may initiate network discovery, for example, if the connection to the nominated master (CPD node 140) has been interrupted.

In illustrative embodiments, a node discovers neighboring nodes, using two basic processes: discovering radio communication and searching for neighbors. When a node appears, MLME can find all adjacent nodes (or directly connected to RF links) through a radio communication discovery process. It can do this randomly, to determine when transmission of radio communication discovery frames should begin, and then choose the channel to transmit the radio communication discovery frame (the channel section can be made random). It can then move through each slot, transmitting each successive frame of radio communication discovery from the next slot, wrapping the last slot. In the preferred embodiment, this process guarantees that a frame of radio communication discovery is transmitted on each channel, in a sequence in jumps, on the FHSS-based network.

In the illustrative examples, there are two ways of discovering radio communication: aggressive and passive. When powered, a device may aggressively enter the discovery mode in which it sends discovery frames at intervals

RO 125809 Β1 randomized, which can be of the order of milliseconds. It can enter the passive discovery mode, when the duration of aggressive discovery has expired. In passive discovery mode, a node can wait a longer period of time, between sending the 3 radio communication discovery frames, usually in the order of minutes.

Once the discovery process has found a neighbor (an adjacent one) or a set of neighbors, 5 MLMEs can then search for the discovered neighbors, to determine the direct neighbors (preferably all direct neighbors will be provided in response). This can be done, in order to discover 7 the proximity of the network faster (in contrast to the radio communication of a large number of frames in jumps, for contacting any particular device). The search mechanism of 9 neighbors is preferably a simple question-and-answer procedure: a node that receives the neighbor search question applies the criterion, preferably, to all the nodes in its list 11 and, preferably, all the nodes that fit the criterion. are placed in the neighbor's response. If no criteria is given, all nodes in the list can be placed in the neighbor's answer 13.

MLME can notify DLF, when the discovery procedure is completed, ie 15 (preferably) all nodes have been queried on their neighbors and an attempt has been made to obtain these neighbors. 17

Using the list of neighbors, built by M LM E, DLF will try to find the announced exit routes. This can be accomplished by listening to Network Announcement 19 (NADV) messages from the devices in the MLME neighbors table.

The NADV message may announce a set of exit routes, which may include the cost of route 21 and the value of the jump of the exit routes. The route cost is the lowest cost associated with that output (PA), of all the candidate routes. The value of the jump is the largest number of 23 jumps that must be made to reach the exit. The value of jumps is used to prevent targeting loops and is not used in conjunction with the cost of the route. The format 25 of the NADV message is shown in fig. 3. The destination MAC address is the MAC address of the device from which the last warning in the network originates. In most cases, this is the 27 point of exit (or PA), because the networks are identified by their output nodes.

From the announcements received in the form of NADV messages, each node can build a routing table 29 that lists all available networks, the output node (PA) that identifies each network, and the routes available for that output node. Preferably, each of the 31 available routes is described by the following jump, the labels that describe the type of route and the costs associated with the connection and the route. The labels indicate the type of route, if it is a permanent entry 33 in the table, if it can be announced by the node etc., within the preferred embodiment, the node will decide to register with that node upstream, for which the total cost 35 (the costs) network and route) of the network is the smallest. Other embodiments may use other criteria, including validation of the reliability of the link in ensuring long-term output 37 to the network. An example of information that can be found in the targeting table is shown in fig. 4. 39

From the information in the routing table, the nodes can build a forward table for the next hop or with a list of destination MAC addresses, a type associated with each address 41, and the cost of the route for it. In the present preferred embodiment, the type reflects the preference of the selection, associated with the destination and may be one of the 43 five: source-directed, jump-by-jump, direct-adjacent, route history, or local. Fig. 5 provides an example of the types of routes that can be listed. In the present 45 preferred embodiment of the hop-to-hop destination, it is listed, along with the next hop from the source node. In the case of a directional type destination from the source, a series of jumps with the destination from the forwarding table is explicitly mentioned. May

EN 125809 multe1 many entries for the same destination can be listed in order of preference, which can be determined by both the type of label and the cost of the route. In the present preferred embodiment, when trying to reach Destination 4, from the example below, the node will first use one of the hopcu jump entries, which are kept in an annexed list, in order to increase the cost of the route. In other embodiments, the routing algorithm allows the routing information to be maintained in the source node, to create an input for the source route to Destination 4, by structuring a next set of routes to the destination address. In addition, in other embodiments, the node will use the preceding route, which was picked up by traversing traffic through certain points in time.

MAINTENANCE OF NEIGHBORS In the present invention, the preferred neighbors, upstream and downstream, are kept constantly, by means of MLME warning signals or periodically targeted maintenance messages, used for synchronizing the hours and ensuring that the nodes can still change. packages, one with the other. This constant contact and retroactive information can be used by the L2 targeting layer for many purposes, which may include:

- updates about the neighbors are communicated to the downstream devices, within the time updating signals;

- The nodes use MLME, to detect if their routes, downstream and upstream, still exist.

The characteristics of the upstream link of a node can be changed, for example, when:

- an upstream node disappears;

- a new preferred upstream link is detected;

- the quality of the connection changes (smooth over time).

In the present preferred embodiment, these rules are applied to all the nodes upstream of a path. When an adjustment occurs, the node recalculates the costs for each of its output nodes. When the cost of a node on the upstream link significantly changes the cost to one of the networks to which it directs, it distributes this information, in the next set of MLME warning signals, to its downstream nodes.

In the present preferred example, a change in network information is propagated with a Neighbor List message, with the protocol type field set to 0x2, indicating that a partial list of changes is distributed. In one embodiment, this may reflect the addition of new networks or changes in the cost of existing networks. When an upstream link disappears, causing a particular network to no longer be accessed, a Neighbor List message, with protocol set 0x3, is sent to indicate that the network has been removed from the upstream node list by network.

In the present preferred example, PA access points are notified of changes in the network topology, through periodic network registration messages, which are transmitted exclusively to them. These messages can be transmitted by each node in the network of access points and may contain a complete list of their nodes upstream and / or the costs of the links to each of them.

In the present preferred example, MLME retains two environments, which can be used by DLF to determine the costs of links for targeting purposes: one value

RSSI balanced and a percentage with balanced success information. The term balanced refers to the type of mediation, achieved on the data. In the present preferred example, the calculation of media uses the formula:

balanced mean = A * mean + B * sample; B = (1 - A),

RO 125809 Β1

This type of mediation does not require a large amount of memory for storage (in 1 way as opposed to storing the last N samples) and also has a controllable amount of history. The term history refers to how much the new balanced value, 3 current, affects. This can be controlled by the values ​​A and B: high A values ​​mean that the average has a higher history than in the case of lower A values. Other embodiments may use 5 other methods of calculating the average, which are appropriate under the conditions that characterize the network.

RSSI is an indicator of the received signal strength. This value can be measured on all frames received from a node. In some embodiments, it is of limited use only for connection quality calculations, as it may not provide a clear indication of the error bit rate per link. Preferably, when any frame in a node is received, the RSSI of that frame is mediated in a balanced RSSI, 11 using the average calculation formula.

In the present preferred example, the percentage of success info criterion is used 13 as the best size of the link quality and, for this reason, for the decisions to make the targeting. Successful info percentage is a form of the success rate of the package. The term 15 info is used to designate cadres, other than those who started communications. The first frame transmitted to a node directed on its jump sequence may fail, due to 17 interference or due to the occupancy of the receiver. The percentage of successful info, by including only those frames that the desired node listens to and not the frames from the beginning of 19 communications, provides a measure of the quality of the connection, which does not vary strongly once the receiver is loaded. The percentage of success info is considered to be the best indicator of the quality of the link.

REGISTERING THE NODE WITH NEIGHBOR NEIGHBORS 23

Each node can explicitly register with the upstream nodes it intends to use on a network. This record means that the node upstream 25 will now try to keep the time information related to the node that wants to record updated, and keep the entry in the downstream routing table. This 27 ensures that the traffic can be carried out not only to the exit, but also back to the node.

The node is registered with its upstream node, by sending to it a message 29 upstream. The registration message in Amonte contains the device type and a metric related to the health of the neighborhood. Neighborhood health metric 31 is used to appease downstream nodes when an upstream link becomes overloaded. Devices with a low neighborhood health metric (and for this reason, 33 possibly with a low route diversity) are selected, preferably, with high metric devices related to neighborhood health. 35

The format for the recording message in Amonte is specified in fig. 6, The message type indicates that it is an upstream record. Neighborhood cost means the neighborhood health metric, based on a combination of upstream, potential and active node numbers.

Potential upstream nodes accept either positive or negative, upstream registration message 39, using the Upstream Accept registration message. The health metric of the vicinity of a device is updated based on the value of this accept. The potential upstream nodes 41 give a lower weight than the upstream nodes accepted.

The format for the Accept registration in Upstream message is shown in fig. 7. 43

The type indicates that it is an Accept registration message upstream. Seq Num represents the number of the sequence transmitted by the applicant in the registration message upstream. The response 45 status code can be one of the following:

- 0x0, - node successfully added; 47

- 0x1, - error adding node;

RO 125809 Β1

- 0x2, - node rejected due to large load;

- 0x3, - the node is already maintained

NOD REGISTRATION WITH PA ACCESS POINT

A node registers itself with a PA access point, by sending an individual PA registration message (AREG). The AREG message contains the list of addresses of the nodes in the PA network, which the node uses as upstream nodes, and the cost of the connection associated with each of these upstream nodes. It may also contain a list of other candidate networks (represented by the output nodes of these networks) and their costs.

The format of the AREG message is shown in fig. 8. The type is set to indicate that it is an AREG message. Bit M is set, if more data is to be transmitted. Seq Number is the sequence number of the recording message. The message number is used when the recording message is transmitted in several parts. Each AREG Neighbor describes a node upstream on the paths used by the node that wants to register.

The format for describing the AREG Neighbor, from the AREG message, is shown in fig. 9, the MAC address corresponds to the upstream node or to a network exit point, about which the node that wants to register informs the PA access point. The cost is recorded either at the upstream node or at the network exit point, which has been described. Bit E is the Node Output bit of the Network. It is established if the description of the neighbors represents a node out of the network and not a neighbor upstream.

When a node is successfully registered at the PA access point, the PA will place the node in its targeting table and ensure that it keeps the node status updated. The node sends regular recording messages to the PA (of the order every 12 hours). The PA access point will update its targeting table when it sees the next registration message to the PA. If the PA loses three consecutive recording messages, the node will be withdrawn from the PA routing table and will have to re-register itself.

In response to a first successful recording, the PA will preferably send a set of TLVs, containing any network configuration information. This list may include, but is not limited to, the globally addressable IPv6 prefix of the PA, the MAC address of the PA, the DNS server address, network hours, and any other L2 / L3 routing variables.

If an access point becomes overloaded with too many nodes, it may start to withdraw nodes that have other candidate networks. It can be evaluated on the different networks reported in the AREG messages and can remove the less reliable candidates from the network.

The preferred process here, regarding the output of a node, can be summarized, as follows, using FIG. 10 and 11. Fig. 10 shows a network deployment with PA 1021 and PA 1022, ensuring the output to Network 1 1010. Relays R1 1031, R2 1032 and R3 1033 and Access Points PA1 and PA2 are considered to have already been established. M1 1041 is the first endpoint whose network output process is described below. Tables 2a and 2b show the costs of the links for all the links that are detected and established.

Table 2a

<td></td><td>network 1 (1010)</td><td>PA (1021)</td><td>BYE (1022)</td><td>R (1031)</td><td>R (1032)</td><td>R (1033)</td><td>M (1041)</td>

<td>network 1 (1010)</td><td></td><td> 5</td><td> 10</td><td></td><td></td><td></td><td></td>

<td>PA (1021)</td><td> 5</td><td></td><td></td><td> 20</td><td> 40</td><td></td><td></td>

RO 125809 Β1

Table 2a (continued)

<td></td><td>network 1 (1010)</td><td>PA (1021)</td><td>PA (1022)</td><td>R (1031)</td><td>R (1032)</td><td>R (1033)</td><td>M (1041)</td>

<td>PA (1022)</td><td> 10</td><td></td><td></td><td></td><td></td><td> 30</td><td></td>

<td>R (1031)</td><td></td><td> 20</td><td></td><td></td><td> 10</td><td></td><td></td>

<td>R (1032)</td><td></td><td> 40</td><td></td><td> 10</td><td></td><td> 10</td><td></td>

<td>R (1O33)</td><td></td><td></td><td> 30</td><td></td><td> 10</td><td></td><td> 15</td>

<td>M (1041)</td><td></td><td></td><td></td><td></td><td> 30</td><td> 15</td><td></td>

Table 2b

<td>Link</td><td>Cost connection</td>

<td>PA (1021) &lt;-&gt; Network (1010)</td><td> 5</td>

<td>PA (1022) &lt;-&gt; Network (1010)</td><td> 10</td>

<td>R (1031) &lt;-&gt; PA (1021)</td><td> 20</td>

<td>R (1031) &lt;-&gt; R (1032)</td><td> 10</td>

<td>PA (1021) &lt;-&gt; R (1032)</td><td> 40</td>

<td>R (1032) &lt;-&gt; R (1033)</td><td> 10</td>

<td>PA (1022) &lt;-&gt; R (1033)</td><td> 30</td>

When M1 (1041) appears, the MLME neighbor scans for the discovery of adjacent R2 (1032) and R3 (1033) in the first stage. During the adjacent establishment, R2 (1032) and R3 (1033) send the Network Announcement messages. Specifically, in the second step, R2 (1032) sends the Network Announcement message, announcing an exit route to Network 1 (1010) through PA1 (1021). The message contains the MAC Address of the PAI (1021), the class or mask of the subnet of the network address (IPv6 or IPv4 address), the cost of the adjacent Ml (1041), as seen by R1 (1031), the maximum number of jumps it makes reach the output node (2), and the lowest cost of network output (35). Using a short notation, we can specify [R2 (1032) sends NADV (30, MAC_ADDRESS (PA1 (1021)), 2, 35)]. It should be mentioned that R2 (1032) does not announce the direct route it has to PA1 (1021), because the cost of the route is 45, which is higher than 35. Then, in the third stage, R3 (1033) send the NADV message, in response to the announcement of an exit route through PA2 (1022). In the short notation, we can write [R3 (1033) send NADV (15, MAC_ADRESS (PA2 (1022)), 1.40)]. This is followed, in the fourth stage, by the calculation by M 1 (1041) of the total cost of the networks, by adding the cost of the route and the cost of the connection, and creating an order list with the following jumps upstream to be used. The upstream node R3 (1033) has a total cost of 55, while the upstream node R2 (1032) has a total cost of 65. R3 (1033) is therefore preferred and placed above R2 (1032) in the list, so as indicated in tables 2a and 2b above. In the fifth step, M1 (1041) attempts to register with R3 (1033), by sending a message upstream to R3 (1033), reporting no other possible node for this output. The sixth stage occurs when R3 (1033) sends an Upstream Registration Acceptance message to M1 (1041), accepting M1 (1041).

RO 125809 Β1

Μ1 (1041) is accepted because it has no other possible node for this output. This is followed by the seventh stage, in which Ml (1041) attempts to register with R2 (1032), by sending a recording message upstream to R2 (1032), reporting no other possible node for this output. Next, the eighth step follows, in which R2 (1032) sends an Upstream Registration Acceptance message to M1 (1041), accepting M1 (1041). M1 (1041) is accepted because it has no other possible node for this output. In the ninth step, M1 (1041) attempts to register with PA2 (1022), by sending a PA Registration Message. It reports R3 (1033), as an upstream node that it wants to use. Next is the tenth stage, in which PA2 (1022) accepts M1 (1041) by sending an Acceptance Message of PA registration and passes M1 (1041), in the network configuration (mainly IPv6 address, DNS address, PA2 network prefix ( 1022), PA2 (1022) can now direct M1 (1041) .The next step or eleventh is the one in which M1 (1041) attempts to register with PA1 (1021) by sending a PA Registration Message. It reports R2 (1032) as an upstream node that it wants to use. In the twelfth step, PA1 (1021) accepts M1 (1041), by sending the PA Acceptance Message, and passes M1 (1041) into the network configuration (mainly, IPv6 address, DNS address, PA1 network prefix (1021). PA1 (1021) can now direct M1 (1041). Next, in the thirteenth step, M1 (1041) sends the DNS Dynamic Update message (RFC 2136) to the DNS Network 1 server, with the IPv6 address via PA2 (1022). The last step occurs when M1 (1041) sends the DNS Dynamic Update message (RFC 2136) to the DNS Network 1 server, with its second IPv6 address via PA1 (1021).

The method of updating routes, when a change in network occurs, is illustrated, using an example of changing the cost of the network connection to 1000. The modified network is illustrated in fig. 12, the only difference being the black line indicating that the respective cost of the route from R1 (1031) to PA1 (1021) has changed from 20 to 5.

First, R1 (1031) updates R2 (1032), through MLME, because R2 (1032) uses R1 (1031) and an upstream flow to PA2 (1021). R2 (1032) recalculates its cost to PA2 (1021). The cost is now 15. R2 (1032) updates M 1 (1041) through MLME regarding the new cost of the route which is 20. M1 (1041) then recalculates the total cost of the networks, by adding the cost of the route and the cost of the connection, and creates a list of orders, for the next jumps to be used. The upstream node R3 (1033) has a total cost of 55, while the upstream node R2 (1032) has a total cost of 50. R2 (1032) is therefore now preferred and placed above R3 (1033) in the list. The reordered list of the targeting information is shown in fig. 13. Finally, R1 (1031), R2 (1032) and M 1 (1041) send the updated information to both PA1 (1021) and PA2 (1022) through their next regular PA registration message.

A small-scale RF network is illustrated in FIG. 14 and will continue to be used, to illustrate the preferred embodiment, regarding how the route determination and propagation operations work, in an ordinary scenario, in which Access Points (1520 series) and relays (series) 1530) are brought first and then the end points (1540 series) are stopped. As illustrated in FIG. 15, the costs of the connections are mapped between the nodes that establish the communications with each other on the RF layer. Fig. 16 is used together with Fig. 17, to illustrate the preferred embodiment, in which a complete sequence of changes takes place between the nodes, to establish the routes or routes for packet delivery upstream in the announced network or downstream of the WAN network, announced in the RF network.

RO 125809 Β1

It should be noted that in Step 4 of FIG. 17, R2 (1532) never announces the 1-hop route, for Net1, through R1 (1531), back to R1 (1531). This method of not announcing the routing information back along an already traversed route is called method 3 "separate horizon and prevents routing loops.

In a preferred embodiment, the targeting mechanism is adapted to be compatible with, and utilizes, the advantage of the Frequency Jump Spread Spectrum Access Scheme (FHSS), used in the wireless network, according to the preferred embodiment, and 7 increases some of the inherent operational characteristics of the FHSS. Regular time updates are required as part of the frequency hopping method to correlate the different 9-hour time lags of the different nodes that must remain correlated with the synchronously changed packets. The routing protocol keeps packets overcrowding to a minimum, 11 by using time updates on frequency hops, in the form of "in-service" messages, for transmitting information about the link status. Alternatively, 13 time updates can also be carried on any of the data packets that are transmitted later. Unless otherwise stated, operation maintenance messages 15 are messages sent to update the information and may be transmitted on a regular basis. The "function" message, which can also be used to update the routing information, is usually sent to, for example, announce when the node is initially powered or when it is introduced to a network. 19 In such an embodiment, there may be a radio communication, in the conventional sense, in the routing protocol on a network, using the FHSS scheme. The nodes are 21 directed one by one directly, for the exchange of packages. The targeting protocol, according to this invention, discloses the use of an abstract relationship of radio communication, in which the frame broadcast on the link layer uses an 8-bit MAC address, all (ff: ff: ff: ff: ff: ff in hex). being transmitted on each slot or channel, starting from a randomly selected slot 25 and with a predetermined waiting time between each transmission.

In the preferred embodiment, according to the invention, the 27 targeting protocol described herein utilizes the wireless signaling capabilities on the FHSS basis, where a warning signal is a periodic transmission, 29 on a certain known sequence. frequency hopping, which all neighbors can recognize. The communicated warning signal, which can be received by several neighbors, is 31 much more efficient than sending a targeting update to each neighbor. A warning signal is also a shorter transmission, with a smaller overcrowding than a targeting update, as there are no acceptance messages and, for this reason, fewer packets retransmitted during an error. 35 In this preferred embodiment, the routing protocol, described below, is intended to exploit the collective computing resources of network devices 37 (nodes), instead of relying on a single gateway to access the wireless network base, to calculate and distribute routes to all nodes. The endpoints select a preferred set 39, with the orderly multiplication of upstream nodes, intended to be used as the next jumps, for output to a WAN network, through multiple Access Points 41 (also called access gates), based on the announcements. of exit routes, with the associated costs of the route, for each route and for each jump. During an error of the main route 43 upstream or to the Access Point, the return on the secondary routes and / or Access Points from the endpoint database is immediate, without waiting for a 45 targeting algorithm, to reconvert, because the routes are already too appropriate.

In a preferred embodiment, the routing protocol allows the nodes to migrate from one WAN network to another WAN network. When an upstream node announces its known routes to a downstream node, it sends a set of outbound routes to all 49

RO 125809 Β1 WAN networks available. The routing table for each node lists the following jumps through multiple Access Points, for all available WAN networks, making it possible to migrate quickly, in case the main or established network becomes unavailable.

In a preferred embodiment, each node records itself with all the upstream nodes it intends to use. The upstream node can now retain an entry in the downstream routing table for that node. The traffic destined for an endpoint can now be routed first and foremost, where only the next jump from the source or any subsequent node is added to the packet's message title, of course, the destination address is typically included. Targeting from the source where the entire order list of the nodes through which the packet must pass is explicitly mentioned by the access gate, in the message title, is also for the purpose of this algorithm. The targeting protocol, disclosed in this invention, allows each node to have several subsequent jumps in its knowledge base and gives it the ability to choose between them forward by jump. By doing so, the packets can bypass the problem links without transmission errors and retransmissions, and it is much more advantageous in a wireless network where RF links tend to be transient in nature. In addition, the present invention avoids open-loop route discovery loops, in which source-directed targeting methods are forced in the event of faulty connections.

The example of the routing protocol, described herein, provides "historic" routes, which represent alternate routes, gathered by a node in the traffic passing through it. History paths are removed from the node routing table, when the allocated memory is full and when they are out of date, after a specified period of time. These routes, which are in addition to the announced routes, serve to expand the list of redundant links available for a node to ensure the successful transmission of a packet.

The example of the routing protocol, described in this case, allows the sorting and preferential sorting of the following available jumps for a node, to direct packets to a destination on a Pv6 network. The logical sorting program may vary in different implementations. In the present embodiment, the logical sorting program uses both the origin of the targeting information and the cost of the route to the destination and the cost of the link to the desired jump. For example, a next jump is picked up from the "historical route, which was gathered from past traffic, which uses an inconsistent route, receives a lower level of preference than the next jump marked as being frequently used in" jump-by-jump traffic. Several subsequent jumps, from the "historical or jump" category, will be sorted in a list of orders, according to the cost of the route. There are other options available for route selection, and these options are described in detail within the scope of this invention.

The example of the targeting protocol, described herein, allows an extension of the sorting software program, to prefer the most recently used link or the link that most traffic has passed or a configurable window (and for this reason, called "Powerful), thus allowing greater control of the flow of traffic. To bypass overloaded links, a current traffic load size, on each available link to a possible next hop, is also considered when a node selects the use of the next best jump.

With the node allowed to register on multiple networks (resulting in the node obtaining more than one IP address) and the DNS server capable of sorting these IP addresses according to the configuration policies for resolving the host name of the node, a method is now provided for control of traffic entry in the l_AN RF network.

RO 125809 Β1

THE LOAD BALANCE MECHANISM OF THE LOAD ROLLER IN 1

PURPOSE OF DIRECTION

Fig. 18 presents a scenario of deployment of a particular network that amplifies 3 the routing algorithm described in the application, to ensure the mechanisms of load balancing and robust running. 5

The targeting algorithm described herein is particularly adaptable to deployments such as the one illustrated in FIG. 18. The concept of multi-point recording 7 output and the notion of configurable link costs can be amplified, to allow (almost) instantaneous removal of errors from multiple layers. For example, if 9 PA-1, an Access Point type device (1810) fails, then the next available PA-2 point can be selected, essentially immediately. In addition, if PA-2 fails, packets can be supported on routes via PA-3, and so on.

Consolidation of all PA access points, in a more central location, encourages 13 the network to announce routes through all PA access points to the endpoint nodes, resulting in a registration of these endpoints with all PAs, instead of one 15 or two PA access points, as in the scenario where PA access points are scattered. These lead different PAs from the central location to look very similar in terms of cost of connection 17; thus ensuring that all of these are part of the routing table (in the preferred embodiment) of the nodes and thus provide a robust error avoidance mechanism 19. Relays (1830) can be used to extend the reach to these ads for the best ratio between the PA and the endpoint node. Moreover, the policies of 21 traffic management at the PA access points can be used to adjust the connection or the costs of the routes to the Access Points, to obtain a load balancing or 23 to allow the conservation of resources, for certain types of traffic. traffic.

The invention has been described with reference to specific embodiments. However, it will be obvious to those skilled in the art that it is possible to implement the invention in specific forms, other than those of preferred embodiments 27, described above. This can be done without departing from the spirit of the invention.

Thus, the preferred embodiment is merely illustrative and should not be considered in any way restrictive. The scope of the invention is presented by the dependent claims and not by the foregoing description, and all equivalent variants and means, which are within the scope of the claims, are intended to be incorporated by them.