CN102227151B - Mixing grid routing protocol - Google Patents

Abstract

The invention describes a method for selecting a route by a node between a source node and a destination node in a wireless mesh network by using a media access control address to establish a route between the source node and the destination node. Also described is a method for a node to use a media access control address to select a route to join a multicast group in a wireless mesh network.

Description

Hybrid Mesh Routing Protocol

This application is a divisional application of the Chinese patent application No. 200580048992.4 filed on March 10, 2005, whose invention title is "Hybrid Mesh Routing Protocol".

technical field

The present invention relates to a routing mechanism for automatic topology learning and path selection. In particular, the invention relates to routing in a wireless local area mesh network based on media access control addresses.

Background technique

A wireless local area mesh network, also known as a wireless LAN-based ad hoc network, consists of two or more nodes interconnected by radio links and communicating with each other directly or indirectly. This network can be connected to the Internet or other networks through portals. In WLANs, IP layer routing protocols have been used to discover routes from source nodes to destination nodes. The IP layer ad hoc routing protocol is based on IP addresses. However, some devices, such as WLAN access points, forward data packets based on IEEE 802.11 Media Access Control (MAC) addresses and operate only at the link layer (layer 2). Furthermore, because data packets do not need to go through the IP layer (layer 3), forwarding data at layer 2 is generally faster than at the IP layer.

The Ad Hoc On-demand Distance Vector (AODV) protocol is an ad hoc routing protocol operating on the IP layer. The protocol can support unicast and multicast route discovery. Routing is based on discovery on demand. When a source wants to send a packet to a destination node, if the source does not have a route to the destination node and needs it, the source discovers the route to the destination by broadcasting a route request message on the network. The message includes the IP addresses of the source node and the destination node and other necessary information. The destination node, or a node with a valid route to the destination node, responds to this request by sending a route reply to the source node. The Route Request and Route Reply messages build routing tables in each of the intermediate nodes for the forward and reverse paths/routes. An established route expires if the route is not used within the given route lifetime. On-demand routing reduces the impact of failed routes due to network topology changes (eg, node movement and failures) and the need to keep unused routes. However, a route discovery delay is introduced because the source node needs to establish a route before being able to send data. The source node also needs to buffer data during route discovery.

Destination Sequence Distance Vector (DSDV) is a proactive routing protocol for WLAN mesh networks. Nodes in the network exchange routing control messages so that the routing table at each node includes information to all destination nodes in the wireless local area mesh network. The data packets are forwarded along the path by the intermediate nodes from the source node to the destination node based on the routing table. To maintain valid paths, and avoid routing loops due to link/node failures and network topology changes, each node not only transmits routing updates periodically, but broadcasts them as soon as important new information becomes available. While DSDV allows packets to be forwarded using either a layer 2 MAC address or a layer 3 IP address with no route discovery delay, this results in relatively high routing overhead because of the broadcast of routing messages throughout the network. Especially when the nodes in the network move relatively quickly and the network topology changes frequently, it is current to devote a large part of the network capacity to maintaining routing information. Furthermore, due to processing and battery constraints or other reasons, some nodes may not be able to forward data packets originating from other nodes. However, the above protocol assumes that each node agrees to rebroadcast data packets to other nodes upon request, and does not consider non-forwarding nodes.

In a WLAN, two or more nodes are interconnected via IEEE 802.11 links. Each node has a unique IEEE 802.11 Media Access Control (MAC) address. When a source node sends a data packet to a destination node, the source node needs to know the path/route from the source node to the destination node.

What is needed is a routing mechanism to discover and establish paths based on the destination MAC address. The problem solved by the present invention is how to discover and establish the path to the destination node based on the IEEE 802.11 MAC address of the destination node in the wireless local area mesh network by the source node.

Contents of the invention

A wireless LAN (WLAN) mesh network consists of two or more nodes interconnected by IEEE 802.11 links. Each node will participate in a routing protocol for automatic topology learning and path selection. The present invention provides a mechanism for discovering routes based on IEEE 802.11 Media Access Control (MAC) addresses. This mechanism supports both on-demand route discovery and proactive route establishment. This mechanism can discover and establish routes to meet the quality of service (QoS) requirements of real-time multimedia applications, and maintain such routes. Additionally, the mechanism supports non-forwarding nodes.

A method is described in which a node between a source node and a destination node selects a route by using a media access control address to establish a route between the source node and the destination node in a wireless mesh network. Also described is a method by which a node selects a route to join a multicast group in a wireless mesh network by establishing a route between the node and the multicast group using a media access control address. In both cases, the established routes can be established by using on-demand routing or proactive routing. Although the present invention described herein is described in terms of a wireless local area mesh network, the network in which routing is established is not limited to a wireless local area mesh network, but may be any form of wireless mesh network. Access points with proxy servers can join the wireless mesh. A station is associated with an access point, but the station is not a member of the wireless mesh, so communication with the station occurs through the access point and is transparent to the associated station.

Description of drawings

The present invention is best understood from the following detailed description when read in conjunction with the accompanying drawings. The accompanying drawings include the following illustrations briefly described below:

Figure 1 depicts a wireless local area mesh network showing flooding of the mesh network with route request (RREQ) messages and reverse path establishment.

Figure 2 depicts a wireless local area mesh network showing unicast of Route Reply (RREP) messages and forward path establishment.

3A depicts a wireless local area mesh network showing flooding of route announcement (RANN) messages for proactive establishment of routes to the originator of the RANN message.

3B depicts a wireless local area mesh network showing a source node sending a gratuitous RREP message to establish a reverse route to the source node.

Fig. 4 is a diagram illustrating a method for nodes to establish routes on demand and proactively, and to process routing control messages in accordance with the principles of the present invention.

Figure 5 depicts a WLAN mesh access point with multiple associated stations.

FIG. 6 is a schematic diagram showing a WLAN access point according to the present invention.

Figure 7A shows the flooding of a mesh network by a new node with a route request (RREQ) message requesting it to join a multicast group.

Figure 7B depicts a Route Reply (RREP) message sent back to the originator of a Route Request (RREQ) message through different multicast tree members.

FIG. 7C shows the originator of a Route Request (RREQ) message transmitting a Route Activate message.

Figure 7D shows a new node that has been added to the multicast group.

Figure 8A shows how a multicast leaf node exits/leaves a multicast group.

Figure 8B shows the multicast tree after pruning.

Figure 9A shows a multicast tree with broken links.

Figure 9B depicts a downstream node attempting to bypass a broken link.

Figure 9C shows downstream nodes receiving Route Reply (RREP) messages from eligible multicast tree members.

Figure 9D shows a downstream node activating a new link.

Figure 9E depicts a new multicast tree that bypasses broken links.

Detailed ways

The present invention performs layer 2 routing functions, so packets can be transmitted and forwarded from source nodes to destination nodes based on IEEE 802.11 MAC addresses. The invention supports on-demand routing and proactive routing at the same time. Also, some nodes can only send or receive data, but cannot forward data originating from other nodes due to processing and battery constraints or other reasons. The present invention can handle these non-forwarding nodes. The routing mechanism of the present invention can be used for client-server application configurations/topologies, peer-to-peer application configurations/topologies, and hybrid application configurations/topologies.

Hybrid grid on-demand routing is similar to IP layer routing protocol AODV, both based on routing request and routing response messages. For layer 2 hybrid network on-demand routing, when a source node wants to send a packet to some destination nodes, the source node checks its routing table for routing. If a valid route exists, the source node forwards the packet to the next hop for this destination node specified in the routing table. If there is no valid route, the source node initiates route discovery by broadcasting a route request (RREQ) message. Unlike AODV, the RREQ message includes the originator IEEE 802.11 MAC address (not an IP address) with a sequence number and optional layer 3 information, and the last known destination sequence number and optional layer 3 information for this destination node Destination node MAC address (not IP address). The RREQ message also includes a message ID, route metric, time to live (TTL) and route lifetime. Before initiating a routing request, the RREQ message will increment its own sequence number.

The IEEE 802.11 broadcast MAC address can be used as the destination address of the transmitted mesh routing control messages by broadcasting RREQ messages or other mesh routing control messages such as the RANN message to be described below. An alternative is to assign a dedicated IEEE 802.11 multicast MAC address for flooding Mesh Routing Control messages (Network Routing Control Group Address). This address specifies all grid nodes. Mesh nodes receive messages directed to this mesh routing control group address. Non-mesh nodes may not receive messages directed to this mesh routing control group address.

Referring to Figure 1 which depicts a wireless local area mesh network, node 105 is the source node and node 110 is the destination node. All other nodes 115 are potential/possible intermediate nodes, which are nodes through which messages/packets/data can be passed between source node 105 and destination node 110 . Based on the selected route/path, a set of intermediate nodes 115 for transferring a particular unit of content from the source node to the destination node is determined. The source node 105 and destination node 110 are textured or shaded to distinguish them from potential/possible intermediate nodes 115 . It should be noted that in another example, the nodes that are now (FIG. 1) the source and destination nodes may be intermediate nodes in this example, while other nodes become source and destination nodes. In FIG. 1, the source node 105 floods the wireless local area mesh network with a route request (RREQ) message. A reverse path is established based on the route request message.

Once a node receives a RREQ message, it checks the originator address and message ED to see if it has seen this RREQ message before. If this is the first RREQ message, the node updates the metric field by increasing the link cost between the node it received the RREQ message from and the node itself, and then establishes in its routing table the reverse routing. If the node is a destination node, or if the node has an unexpired valid route to the destination, and the sequence number of the destination node is at least as large as indicated in the RREQ message, the node sends a route reply (RREP) The message is unicast back to the originator to respond. Otherwise, the node propagates a RREQ message with the new metric. If this is not the first RREQ message, the node updates the metric field to the originator by increasing the link cost between the node from which the RREQ message was received and this node. If the new metric is less than the metric recorded in the node's routing table, the node updates the reverse route. Otherwise, the RREQ message is discarded. If the node meets the above requirements, it replies to the initiator with an RREP message. Otherwise the node propagates the RREQ message with the new reverse routing metric. The reverse path/routing is used to send the RREP message back to the originator of the RREQ message to establish the forward path, and also for the two-way communication between the source node and the destination node.

A RREP message is sent back to the originator of the RREQ message via unicast to establish the forward path. The RREP message includes the initiator MAC address, the destination MAC address and optional destination layer 3 information, the serial number of the destination node, the metric, the lifetime and the route lifetime. If the destination node responds, it uses the maximum value of its current sequence number and the destination sequence number in the RREQ message. The initial value of the metric is zero. The destination node also sets the lifetime of the route. If the intermediate node responds, its records of the destination sequence number and metric are used, along with the route lifetime calculated based on the routing table entries.

Referring to Figure 2 which depicts a wireless local area mesh network, node 205 is the source node and node 210 is the destination node. A set of intermediate nodes 220 for a particular source node 205 and destination node 210 is determined. For the route/path between source node 205 and destination node 210, intermediate node 215 is no longer an intermediate node. The forward path is established by unicast RREP messages from destination node 210 to source node 205 .

RREP messages are unicast through the reverse route established during route request broadcast. When an intermediate node receives a RREP message, the intermediate node updates the metric by increasing the link cost between the node from which the RREP message was received and the intermediate node itself. The intermediate node establishes a forward path in its routing table and forwards the RREP message to the originator of the RREQ message. If the node receives more than one RREP message, it forwards the first RREP message. The node updates the routing table and forwards the new RREP message only if the new RREP message includes a larger destination sequence number or the same destination number with a better metric. Otherwise, the new RREP message is discarded. Figure 1 and Figure 2 show that RREQ messages are flooded into the mesh network, and a forward path is established through unicast RREP messages. The initiator can start data/packet transmission immediately upon receiving the first RREP message, and can update its routing information later if a better route is found.

Nodes can have multiple IEEE 802.11 radio interfaces. A node has a unique node identifier, which is the node's IEEE 802.11 MAC address, and each interface also has its own IEEE 802.11 MAC address. The node's MAC address is used for RREQ and RREP messages and other routing control messages as described below. When a multi-interface node broadcasts an EQ message, the node may broadcast the RREQ message through all interfaces. When a multi-interface node responds to a RREQ message through a unicast RREP message, the node sends the RREP message to the interface through which the corresponding RREQ message was received.

The routing table includes entries for destination nodes. Each entry includes the destination MAC address and its optional layer 3 information (supported layer 3 protocols and addresses, such as the IP address of the destination node), the destination sequence number, the next hop MAC address, and the interface to the next hop , a list of upstream nodes and interfaces using this route, status and routing flags (eg, valid, invalid), metric to destination, and route lifetime. Each time a route is used, the lifetime of the route is updated. If the route is not used during the lifetime of the route, the route becomes invalid. When the deletion timer of an invalid route expires, the invalid route will be deleted. The initiator can start data transmission immediately upon receiving the first RREP message, and can update the routing information later if a better route is found. When an intermediate node receives a data packet, the intermediate node checks the routing table based on the destination MAC address. If there is a valid entry for this destination, the intermediate node forwards the packet to the next hop specified in this routing entry. This process will continue until the destination node is reached.

In on-demand routing, only the currently used routes are maintained. This reduces routing overhead. However, this introduces additional delay because the source node must establish a route before data can be sent. The source node also needs to buffer data during route discovery. To reduce route discovery latency, proactive routing can be used. Furthermore, where many nodes communicate with a particular node, significant traffic control is required if each of these nodes individually discovers a route to this particular node. For example, many nodes in a mesh network access the Internet or other network through one or more entry nodes that connect the mesh network to the Internet or other network. Desirably, an ingress node proactively announces routes to it in the mesh network. The invention combines on-demand route discovery and proactive route announcement. Nodes can be explicitly configured by the network administrator, or implicitly determined to perform proactive routing in the mesh network according to specific policies. For example, one policy is that all mesh entry nodes should implement proactive route announcements. Referring to FIG. 3A , a node 310 announces itself by periodically broadcasting an Unsolicited Route Announcement (RANN) message, so that other nodes 315 in the mesh network can learn the route to the originator 310 of the RANN message. In other words, a node originating a RANN message floods the wireless local area mesh network with unsolicited RANN messages in order to proactively establish a route to itself. When a multi-interface node broadcasts a RANN message, the multi-interface node may broadcast the RANN message through all its interfaces. The RANN message includes the IEEE 802.11 MAC address (not the IP address) of the initiator node with the destination sequence number and optional layer 3 information. The RANN message also includes a route metric, a lifetime, and a route lifetime. Note that different from the RREQ message, the destination address in the RANN message is the MAC address of the originator of the RANN message, because the RANN message is used to proactively establish a route to the originator of the RANN message in the mesh network.

When a node 315 receives a RANN message, the node updates the metric field to the originator of the RANN message by increasing the link cost between the node from which the RANN message was received and the node itself. If the node does not have a valid route to the destination node (ie, RANN message originator 310) in its routing table, the node creates a route to the destination node in its routing table. The node broadcasts a RANN message to neighboring nodes through one or more of its interfaces with the new metric. When the node has a valid route to this destination, the node updates its routing table with the new metric only if the RANN message includes a larger destination sequence number or the same destination sequence number with a better metric. Broadcast RANN messages to neighboring nodes. Otherwise, the RANN message is discarded. In this way, a route to the originator of the RANN message is established in the mesh network.

Referring to FIG. 3B , when the source node 305 intends to send a data packet to the destination node 310 , the node may have obtained the forward path to the destination node 310 from the destination node's route announcement. In this instance, the node can transmit the packet immediately. However, it is also possible that there is no reverse route from destination node 310 to source node 305 . If two-way communication is required, source node 305 may unicast send a gratuitous RREP message to node 310 through intermediate node 320 along the forward path established by destination node 310's RANN message. This RREP message establishes a reverse route to source node 305 .

Some nodes want to join the WLAN mesh network only as source or destination nodes, ie not forward traffic originating from other nodes. Nodes can be configured as non-forwarding nodes by an administrator, or determined to be non-forwarding nodes based on certain policies. For example, one such policy is that if a node's battery energy falls below a threshold, the node will become a non-forwarding node. A non-forwarding mesh node sends a RREQ message when it wants to transmit a packet. Only when the non-forwarding node is the destination node in the received RREQ message, it responds to the routing request message. If the non-forwarding node is not the destination node in the received RREQ message, it does not respond to the routing request message. The non-forwarding node receives the RANN message to learn the route to the originator of the RANN message. A non-forwarding node sends a RANN message so that a route to the non-forwarding node can be established proactively. However, non-forwarding mesh nodes do not forward any routing control messages, including RREQ, RREP, and RANN messages, to neighboring nodes. By doing this, there are no routes with non-forwarding nodes as intermediate nodes.

If the link goes down, a Routing Error (RERR) message is sent to the affected source node of the active path. The upstream node that disconnects the link, that is, the node close to the source, initiates a RERR message. Before sending the RERR message, the node also marks the damaged route as invalid, sets the metric of the damaged route to infinity, and increments the destination sequence number of the unreachable destination due to the failure of this link in the routing table. The RERR message includes a list of all unreachable destinations due to this link failure, along with their incremented sequence numbers. The node broadcasts the RERR message to one or more of its upstream neighbors. For multi-interface nodes, the RERR message is sent through the interface that has a route using the failed link. When a neighboring node receives a RERR message from its downstream node, the neighboring node checks whether there is a route to the listed destination using the downstream neighboring node. If there are, mark those routes as invalid and set their metric to infinity. The RERR message is then propagated to upstream nodes. When the source node receives the RERR message, the source node re-initiates route discovery. If a node receives a data packet with a destination MAC address (which does not have an active/valid route), the node creates a RERR message for the destination node and sends this RERR message to the upstream neighbor node.

Local connectivity management is implemented by nodes periodically sending beacons (HELLO messages) to neighboring nodes. A node that receives a beacon from a neighboring node updates the route lifetime associated with that neighboring node in its routing table. If a node cannot receive a beacon for a given Hello_life from a neighboring node, the link to that neighboring node is broken, and the routing information for this neighboring node is updated in the routing table.

Figure 4 is a diagram illustrating a method for nodes to establish routes on demand and proactively, and to process routing control messages according to the principles of the present invention. In step 402, the node determines whether proactive route discovery is required. This information can be explicitly configured by the network administrator, or obtained implicitly through policies as described above. If proactive routing discovery is required, then in step 404 RANN messages are sent periodically. If proactive routing is not required, the node returns to an idle state. In step 410, when a node receives a new data packet from an upper layer application, the node checks whether there is a forward path/route to the destination node (step 412). If not, the node initiates on-demand route discovery by sending a RREQ message (step 414). The node waits for the corresponding RREP message. Once the RREP message is received (step 416), a forward route is established (step 422), and data transmission begins (step 428). If the RREQ message is lost, the source node may be allowed to retransmit the RREQ message for a set number of times (step 418). If the RREP message is still not received after the maximum number of retransmissions of the RREQ message, the application is notified by an error message that the destination node is unreachable (step 420). If the source node has a forward route, the source node checks if it has a reverse route for bi-directional communication (step 424). If the forward route is established through the RANN advertisement of the destination node, there may be no reverse route. In the case of one-way communication or two-way communication where reverse routing is available, the source node transmits the data immediately in step 428 . In the case of two-way communication without a reverse route, the source node sends a gratuitous RREP message (step 426) to establish the reverse route. Once the gratuitous RREP message has been sent, the source node may then transmit the data (step 428).

In step 440, when a node in the mesh network receives the RANN message, it sets/establishes/restores a route to the originator of the RANN message (step 424). If the node is a non-forwarding node (step 444), the RANN message is not forwarded (step 448). If the node is a forwarding node, the RAISIN message is forwarded (step 446). When the node receives the RREQ message in step 450, the reverse route is set/established/restored (step 452). The node determines whether it is a non-forwarding node (step 454). Only if the node is the destination node specified in the RREQ message (step 460), the non-forwarding node replies to the RREQ message by unicasting an RREP message back to the originator of the RREQ message (step 462). If the node is not the destination node, the non-forwarding node does not forward the RREQ message (step 464), but discards the RREQ message. For a forwarding node, if the node is a destination node or if the node has a valid route to the destination node (step 456), the node responds by unicasting a route reply (RREP) message back to the originator of the RREQ message (step 456). 462). Otherwise the RREQ message is propagated (step 458). When the node receives the RREP message in step 470, it sets/creates/restores the route (step 472). If the node is a non-forwarding node or the node is the destination node for the RREP message (step 474), then the node does not forward the RREP message (step 478). Otherwise, the RREP message is forwarded (step 476). When a node detects a link failure or when a node receives a RERR message (step 480), the node deactivates the broken route (step 482). If the node is the source node (step 484), the node discovers/learns the new route (step 490). Otherwise, if the node is not a non-forwarding node (step 486), the RERR message is forwarded (step 488). If the node is a non-forwarding node, the node does not forward the RERR message (step 492).

Multiple stations can be associated with an access point (AP) in a WLAN. Referring to FIG. 5, a node 505 is an AP joining a mesh network. However, station 510 is not part of wireless local area mesh network 525 . Stations 510 form an infrastructure-based network/subnetwork with access points 505 . Mesh AP 505 acts as a proxy server for these sites 510, and routing is transparent to non-mesh sites 510. When a mesh AP 505 forwards a data packet originating from an associated site 510, a route to the destination node is discovered. Mesh AP 505 also responds to the RREQ message of the associated station by unicasting the RREQ message to the originator of the RREQ message. Mesh APs 505 announce routes to associated sites 510 by broadcasting RANN messages. A single RANN message can be used to announce multiple destination addresses with separate sequence numbers, optional layer 3 information, time to live (TTL), metrics and route lifetimes. Each destination address corresponds to a site.

FIG. 6 is a block diagram showing details of a mesh access point (node/AP 505 in FIG. 5 ) with a proxy server 600 . A mesh AP with proxy server 600 has two logical interfaces. One is a station transmit/receive (TX/RX) interface module 645 that communicates with associated stations, and the other is a mesh network transmit/receive (TX/RX) interface module 655 that communicates with the mesh network. These two logical interfaces can be implemented using two physical IEEE 802.11 radio interfaces operating on different channels (each physical interface corresponds to a logical interface) or using a single IEEE 802.11 radio interface. The site association control module 650 performs site association control. The mesh routing module 605 is responsible for routing data in the mesh network. The mesh routing module 605 includes a mesh routing discovery unit 610, configured to send a routing request to discover a route to a destination node in the wireless local area mesh network (perform on-demand routing). The mesh routing module 605 also includes a network route announcement unit 615, configured to send RANN messages in the mesh network (performing proactive routing). The routing message processing unit 620 processes the received routing control message, and responds/forwards the routing control message. If a link disconnection is detected, the route maintaining unit 625 maintains the route and generates a route error message. The mesh routing module 605 also maintains a routing table 630 in its cache. The data processing unit 635 transmits/receives/forwards data packets based on the routing table. The mesh routing module 605 interfaces with the mesh network through the mesh network TX/RX interface module 655 . The site proxy server 640 bridges the associated sites and the mesh network. Site proxy server 640 passes associated site information from association control module 650 to routing module 605 . The site proxy server 640 interacts with the routing module 605 to perform routing and data forwarding functions for the associated site (for example, when the site proxy server 640 forwards data packets originating from the associated site, it discovers a route to the destination node, responding to the RREQ of the associated site messages, and announce routes to associated sites by initiating RANN messages in the mesh network).

The invention supports multicast and unicast routing. A separate multicast routing table is maintained by the nodes. Similar to the above-mentioned unicast on-demand route discovery, multicast on-demand discovery is based on route request and route reply messages, which is also similar to the IP layer routing protocol AODV. Nodes can dynamically join or leave the multicast group at any time. Each multicast group has a multicast group leader. The group leader maintains the multicast group sequence number. In case a multicast group leader failure is detected, a new group leader is created so that there is no central point of failure.

When a node wants to join a multicast group, the node broadcasts a RREQ message to all mesh nodes. The RREQ message includes the initiator's MAC address, the current sequence number, optional layer 3 information (supporting layer 3 protocols and addresses, such as IP addresses), the destination MAC address (that is, the address of the multicast group to be joined), the latest Learned sequence numbers, message IDs, metrics, age parameters, and join tokens. Any member of the multicast tree can respond to RREQ messages, but only members of the multicast tree can respond. Non-member nodes (non-members of the multicast tree) do not respond to RREQ messages, but create a route/path to the originator. The non-member node then forwards the RREQ message to neighboring nodes. This will be described in detail below. The length of time the initiator waits for the discovery period in order to receive an acknowledgment or reply. If there is no reply, the initiator retransmits/rebroadcasts the RREQ message with the message ID incremented by 1. The initiator continues in this manner until a reply is received or the retry limit has been exceeded. If no acknowledgment is received after the maximum number of retries, the initiator may become the multicast group leader of the new multicast group.

When a node receives a request to join a multicast group from another node (not in the group), the node updates the metrics field and adds the originator's inactive entry to its multicast routing table. Each entry in the multicast routing table has a flag indicating whether the link is active or inactive. For multicast groups, no data/packets will be forwarded/transmitted over passive links. The node also creates a reverse route/path entry to the originator in the unicast routing table according to the unicast routing establishment rules.

The multicast tree includes nodes that are members of the multicast group, and forwarding nodes for the multicast group. A forwarding node is a node that is a member of a multicast tree, but not a member of a multicast group. The forwarding node acts as a "channel" or "pipe" for the received data/packet/content. A forwarding node does not use and is not interested in the data/packets/content it receives. If the sequence number recorded by the multicast tree is at least as large as that carried in the RREQ message, any member of the multicast tree can respond to the RREQ message to join the multicast group. A multicast group leader always responds to a RREQ message to join the multicast group. The node that responds to the RREQ message of joining the multicast group establishes a unicast reverse route to the initiator in its routing table according to the unicast route establishment rules. The responding node also establishes a route for the initiator in the multicast routing table. Mark the route as inactive. The responding node then unicasts the RREP message back to the originator of the RREQ message. When a node along the reverse path receives an RREP message, the node updates the metrics and builds the forward path/route in its multicast routing table. Marks established paths/routes in the multicast routing table as inactive. The node then forwards the RREP message to the next hop.

Each node in the multicast tree has a multicast routing table. The multicast routing table has an entry for each multicast group. Entries in the multicast routing table include multicast group MAC address, next-hop MAC address, interface to next-hop, multicast group sequence number, metric to the multicast group leader, flags (active/inactive, and routing tag) and route lifetime parameters. Every time a route/path is used/passed, update the route lifetime parameter. If the route/path is not used within the specified route lifetime, the route/path becomes invalid.

The originator of a RREQ message to join a multicast group may receive multiple RREP messages from different members of the multicast tree. Each reply represents a potential route/path to that multicast group. The initiator keeps track of the replies received and waits for the expiry of the route discovery period/interval. The initiator then chooses the route with the largest multicast group sequence number and the best metric to that multicast group. By unicasting a Multicast Activation (MACT) message with Join Flag set to Join Next Hop, the initiator activates the route/path selected upon expiry of the route discovery period/interval. The initiator sets the active/inactive flag to active for the selected route/path in the multicast routing table. As each hop along the path receives the MACT message, the node activates the route in its multicast routing table and, if the node is not the originator of the RREP message, forwards the MACT message to the next hop. This process continues until the originator of the RREP message receives the MACT message. It should be noted that a node can be a member of two multicast groups/trees at the same time.

7A-7D illustrate how a new node "N" joins a multicast group. Dark shaded nodes are members of multicast groups and members of multicast trees. White nodes are nodes that are not members of a multicast tree or multicast group. Node "N" is a new node that wants to join the multicast group. Nodes marked with "F" are forward nodes. Now, referring to FIG. 7A, node "N" is a new node that wants to join the multicast group. Node "N" floods the mesh with RREQ messages when attempting to join the multicast group. The RREQ message is transmitted by nodes that are not members of the multicast tree before the RREQ message reaches the nodes that are members of the multicast tree. Figure 7B depicts the RREP message returned to a new node wishing to join a multicast group. The RREP message is sent back to the originator of the RREQ message along the reverse path by a different multicast tree member. FIG. 7C shows the originator of the RREQ message that transmits the Routing Activation Message (MACT). The originator of the RREQ message unicasts the MACT message with the join flag set to activate the route/path to the multicast group. Figure 7D shows a new node that has been added to the multicast group. A node that is not a member of a multicast group or a multicast tree has been added as a forwarding node, thus becoming a member of the multicast tree.

If a node that is a member of a multicast group wants to exit/leave the group, the node unicasts a MACT message to the next hop with the pruning flag set to pruning and deletes the entry to the multicast group in its multicast routing table. entry. Once the next node along the path receives a MACT message with the pruning flag set to pruning, that node deletes the routing information for the node to which the MACT message was transmitted. If a node receiving a MACT message with a pruning flag set to pruning is not a member of a multicast group, and the node becomes a leaf node upon removal of a node wishing to relinquish its membership in the multicast group, then the It itself is pruned from the multicast tree. A leaf node prunes itself from the multicast tree by unicasting to its next hop a MACT message with the pruning flag set to pruning. If a node that receives a MACT message with a pruning flag set to pruning is a member of a multicast group or is not a leaf node, the node cannot prune itself.

8A-8B illustrate how node "A" relinquishes its membership in a multicast tree and group. Dark shaded nodes are members of multicast groups as well as members of multicast trees. White nodes are nodes that are not members of a multicast tree or multicast group. Nodes marked with "F" are forwarding nodes. Figure 8A shows how a multicast leaf node exits/leaves a multicast group. Node "A" unicasts a MACT message with the prune flag set to prune in order to relinquish its membership in the multicast group and tree. Figure 8B shows the pruned multicast tree. After node "A" relinquishes its membership from the multicast group and tree, leaving node "B" as a forwarding node as a leaf node, the node prunes itself from the multicast tree.

Every Hello_mterval, a node on the multicast tree must receive a transmission from every neighboring node. Transmissions include multicast data packets, RREQ messages, Hello messages, Beacon messages, or Group Hello (GRPH) messages. GRPH messages are sent periodically along the multicast tree by the group leader. If a node fails to receive any transmissions from a neighboring node on the multicast tree within HelloJlife, the link to this neighboring node is broken. When a link breaks, the broken node downstream (ie, a node that is farther away from the multicast group manager) attempts to repair the link. In effect, this is an attempt to bypass broken links and generate alternative paths back into the multicast tree. Downstream nodes responsible for attempting to repair a broken link or to bypass a broken link by discovering alternative routes send a RREQ message to join the multicast group, which includes a metric indicating the sending node and the group leader extension field. A node responding to a RREQ message must be a member of a multicast tree with a sufficiently fresh sequence number (where the sequence number is at least as large as the multicast group sequence number carried in the RREQ message), and the metric to the multicast group manager Must be better than the metric indicated in the RREQ message. Upon expiry of the route discovery period/interval, a node that initiates a RREQ message attempting to set a bypass for a broken link selects a route/path and unicasts a MACT message with the join flag set as the join next hop in order to activate The latest discovered route. If the multicast tree cannot be repaired by rejoining the tree through any branch, the downstream node responsible for bypassing the broken link becomes the new multicast group leader of the new multicast tree.

9A-9E illustrate bypassing a broken multicast tree link. Figure 9A shows a multicast tree with broken links. In this example, the link between node "A" and node "B" is down. Figure 9B depicts a downstream node (node "A") attempting to bypass a broken link by sending a RREQ message requesting to join a multicast group. Figure 9C shows a downstream node (node "A") receiving an RREP message from a qualified multicast tree member. Figure 9D shows a downstream node (node "A") activating a new link using a MACT message with the join flag set to join. Figure 9E depicts a repaired multicast tree with bypasses for broken links. It is important to note that broken links are not actually repaired, but bypassed by using available route discovery mechanisms.

Similar to unicast, in order to reduce route discovery delay, the present invention supports proactive route selection. The invention combines on-demand route discovery and proactive route announcement. For multicast, if the node is a multicast group leader, the node can be explicitly configured by the network administrator, or determined implicitly according to a specific policy, in order to perform proactive routing in the mesh network. The configured group leader advertises the multicast group by periodically broadcasting unsolicited route announcement (RANN) messages, so that other nodes in the mesh network can learn the route of the multicast group. The RANN message includes the IEEE 802.11 MAC address (not the IP address) of the multicast group with the group sequence number and optional layer 3 information. RANN also includes routing metrics, lifetimes, and routing lifetimes.

For example, for multimedia and video applications, it is necessary to support Quality of Service (QoS) in WLAN mesh networks. In order to support QoS, the optional field of the extended RREQ message may carry QoS requirements such as the maximum delay of data and the minimum bandwidth requirement. In order to respond to or forward RREQ messages with QoS extensions, nodes must satisfy the QoS constraints. Otherwise, the QoS RREQ message is discarded. After establishing a QoS route, if any node along the path detects that it no longer satisfies the requested QoS parameters, that node sends a RERR message to the initiator. The RERR message may also carry currently measured QoS parameters such as the link's available bandwidth and delay parameters. The initiator can decide to continue using the route with lower QoS, or discover another route. For example, the RERR message indicates that the current bandwidth available on the link is equal to a lower value than previously requested by the initiator. The initiator can reduce its source rate to satisfy the currently available bandwidth or to discover new routes with the originally required bandwidth.

It will be appreciated that the present invention can be implemented as hardware, software, firmware, special purpose processors, or a combination of these, for example within a mobile terminal, an access point, or a cellular network. Preferably, the invention is implemented as a combination of hardware and software. Furthermore, the software is preferably implemented as an application program tangibly embodied on a program storage device. An application program may be uploaded to, or executed by, a machine comprising any suitable architecture. Preferably, the machine is implemented on a computer platform having hardware such as one or more central processing units (CPUs), random access memory (RAM), and input/output (I/O) interfaces. The computer platform also includes an operating system and microinstruction code. The various processes and functions described herein may be part of the microinstruction code or part of the application program (or a combination of both) executed by the operating system. In addition, various other peripheral devices, such as additional data storage devices and printing devices, can be connected to the computer platform.

It is also to be understood that since some of the components and method steps that make up the system described in the drawings are preferably implemented as software, the actual connections between computer components (or processing steps) may be based on the manner in which the invention is programmed And there is a difference. Given the teachings herein, one of ordinary skill in the relevant art will be able to contemplate these and similar implementations or constructions of the invention.

Claims (14)

1. node of in wireless mesh network, selecting the route between source node and the destination node, described node comprises: be used for using media access control address to set up the device of the described route between described source node and the described destination node, described route between described source node and the described destination node based on hybrid grid as required with answer formula grid Route Selection earlier, wherein said node also comprises:

Be used for receiving the device of route request information;

First determines device, is used for determining that whether described route request information is first route request information from described source node;

First updating device, be used for determining that in response to described first definite device described route request information is first route request information from described source node, receive the node of described route request information and the link cost between the described node from it and upgrade tolerance the described route request information by increasing, and in the routing table of described node, be established to the reverse route of described source node; And determine that in response to described first device determines that described route request information is not first route request information from described source node, receive the node of described route request information and the metric field that the link cost between the described node is updated to the promoter by increasing from it;

Second determines device, one of below being used for determining by described node: a) whether described node is described destination node, and b) in described routing table, it is represented equally big in the route request information at least as described whether described node has to the sequence number of the effective not yet due route of described destination node and described destination node;

Final controlling element: be used for determining that in response to described second device determines that described node is that destination node or described node have to the sequence number of the effective not yet due route of described destination node and described destination node represented equally big of route request information at least as described, with the route replies message unicast to described source node; Otherwise propagate the described route request information with tolerance of upgrading;

Comparison means, be used for determining that in response to described first definite device described route request information is not first route request information from described source node at described first updating device, receive under the situation of the node of described route request information and the metric field that the link cost between the described node is updated to the promoter from it by increasing, the described tolerance in the described routing table and the tolerance of upgrading are compared;

Second updating device is used for upgrading reverse route in response to the tolerance that the operation by described comparison means obtains upgrading less than described tolerance;

The tolerance that is used for obtaining upgrading in response to the operation by described comparison means is not less than the device that described tolerance abandons described route request information.

2. node as claimed in claim 1 also comprises the device for the route that keeps the current use of described wireless mesh network.

3. node as claimed in claim 1 or 2, also comprise for the routing iinformation that uses advertisement keep with described source node and described destination node between the device of the relevant information of all routes.

4. node as claimed in claim 1 or 2, the described device that wherein is used for setting up described route also comprises:

The device that is used for determining at least one route between source node described in the described wireless mesh network and the described destination node based on Route Selection as required; And

Based on being used at the device of selecting a route between described source node and the described destination node under the situation of having identified a plurality of routes between described source node and the described destination node of Route Selection as required, wherein said selection is based on sequence number and tolerance.

5. node as claimed in claim 1 or 2, wherein said node is the node that is configured in the described wireless mesh network, and the described device that is used for setting up described route is also based on answering the formula Route Selection earlier, advertisement arrives the route of described node.

6. node as claimed in claim 1 or 2 also comprises at described wireless mesh network beacon message regularly being sent to adjacent node to keep local internuncial device.

7. node as claimed in claim 1, wherein said node is associated with access point, and the described node that is associated with described access point is not the member of described wireless mesh network, described access point serves as the agency of the described node that is associated with described access point, and the Route Selection between any other member of described node and described wireless mesh network is transparent for described node.

8. node as claimed in claim 1, wherein said destination node is the member of the multicast group in the described wireless mesh network, the described multicast group of described wireless mesh network is dynamic, and any node can at any time dynamically add or withdraw from the described multicast group of described wireless mesh network.

9. node as claimed in claim 8 also comprises: be used for keeping the device of the route of the current use of described wireless mesh network, and be used for using the routing iinformation of advertisement to keep the device of the information relevant with all routes of described multicast group.

10. node as claimed in claim 8, the described device that wherein is used for setting up described route also comprises:

The device that is used for determining at least one route between node described in the described wireless mesh network and the described multicast group based on Route Selection as required;

Based on being used at the device of selecting a route between described node and the described multicast group under the situation of having identified a plurality of routes between described node and the described multicast group of Route Selection as required, wherein said selection is based on sequence number and tolerance; And

The device that is used for activating selected route based on Route Selection as required.

11. node as claimed in claim 8 or 9, wherein said node is the group guide who is configured of multicast group described in the described wireless mesh network, and the described device that is used for setting up described route is also based on answering the formula Route Selection earlier, and advertisement arrives the route of described node.

12. node as claimed in claim 9 also comprises for beacon message regularly being sent to adjacent node to keep local internuncial device.

13. node comprises that also the multicast tree link that is used to disconnection arranges the device of bypass as claimed in claim 8 or 9.

14. a method that is used for the operation access point, described method comprises:

At least one website that control is associated with described access point;

Receive route request information;

Check originator address and message identifier, before whether seen described route request information to determine described access point;

If described route request information is first route request information, then upgrade the metric field of described access point by the node of the described route request information of increase initiation and the link cost between the described access point self, and in the routing table of described access point, be established to the promoter's of described route request information reverse route;

If described access point is destination node, if perhaps described access point has to the sequence number of the effective not yet due route of described destination node and described destination node represented equally greatly in the route request information at least as described, then the route replies message unicast is returned the promoter of described route request information; Otherwise propagate described route request information with new tolerance;

If described route request information is not first route request information, the promoter by increasing described route request information and the link cost between the described access point self metric field that is updated to the promoter of described route request information then;

If the tolerance of upgrading less than the tolerance in the described routing table, is then upgraded reverse route; Otherwise, then abandon described route request information.

Images