Routing method and system for a wireless network

• US 20080267116A1
• Filed: 09/21/2007
• Published: 10/30/2008
• Est. Priority Date: 04/27/2007
• Status: Active Grant

• Current Assignee: Extreme Networks, Inc.
• Original Assignee: Aerohive Networks Incorporated (Extreme Networks, Inc.)
• Inventors: Liu, Changming, Kang, Yong
• Granted Patent: US 8,948,046 B2
• Time in Patent Office: Days
• US Class Current: 370/328
• CPC Class Codes: H04L 41/0893 Assignment of logical groups to network elements
• CPC Class Codes: H04L 41/0894 Policy-based network configuration management
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/03 by updating link state protocols
• CPC Class Codes: H04L 45/18 Loop-free operations
• CPC Class Codes: H04L 45/20 Hop count for routing purposes, e.g. TTL
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/245 Link aggregation, e.g. trunking
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers
• CPC Class Codes: H04W 4/06 Selective distribution of broadcast services, e.g. multimedia broadcast multicast service [MBMS]; Services to user groups; One-way selective calling services
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 40/24 Connectivity information management, e.g. connectivity discovery or connectivity update
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 40/30 for proactive routing
• CPC Class Codes: H04W 40/36 due to handover
• CPC Class Codes: H04W 84/005 Moving wireless networks

Abstract

A method and system for selecting a route in a wireless network for the transmission of a data packet between wireless nodes in said network using a modified link-state routing algorithm wherein only a limited number of broadcast messages are generated to synchronize the link-state database throughout the wireless network. A subset of nodes called portal nodes within the network are elected to do the broadcasting for the entire network. Each portal node broadcasts an announcement of its identity to all of the wireless nodes. Each wireless node responds to these broadcasts to select one of the portal nodes as its root portal node. It then identifies a unicast route back to its root portal node, and sends a link-state register message to this portal node. These link-state register messages received by each portal node are aggregated by them and are broadcast to each of the wireless nodes for storage. When a data packet is thereafter received by a wireless node from a neighboring node, it detects if the data packet satisfies one of a plurality of predetermined conditions and rebroadcasts the data packet to neighboring wireless nodes if none of the conditions is satisfied.

Claims

1. A method for selecting a route in a wireless network for the transmission of a data packet between a first wireless node functioning as a source node and a second wireless node, comprising:

causing each portal node to broadcast an announcement of its identity as a portal node to all of said wireless nodes, each said wireless node acting in response to said broadcasting to elect one of said portal nodes as its root portal node and to identify a unicast path back to said elected portal node; and

causing each wireless node to send a link-state register message to its said root portal node, each said portal node acting in response to the receipt of a link-state register message to aggregate said messages into one link-state-update packet and to broadcast said link-state-update packet to each of said wireless nodes, each said wireless node storing said received link-state-update packets in a link-state database at said node.

2. The method of claim 1, wherein said announcement is a packet that includes the Ethernet address of the portal node broadcasting the announcement, a sequence number that is an increasing integer per node, and a metric value that represents the number of links that announcement has traversed from said portal node to the node receiving the announcement, each said non-portal wireless node electing as its root portal node the portal node whose announcement metric value is the lowest.

3. The method of claim 2, wherein each said wireless node responds to a received announcement packet by:

identifying the packet node that originated the announcement packet;

comparing the wireless node'"'"'s sequence number to the sequence number carried in the announcement packet to decide if the announcement packet should be taken;

updating the stored sequence number once the announcement packet is taken;

storing a unicast route to the portal node that generated said packet; and

relaying the announcement packet after updating the metric value.

4. The method of claim 1, further comprising the step of causing each wireless node to detect if a data packet being broadcast from a neighboring node satisfies one of a plurality of conditions indicating that the data packet should not be rebroadcast and re-broadcasting the data packet to neighboring wireless nodes if none of the plurality of conditions is satisfied.

5. The method of claim 4, wherein the broadcasting of a data packet by each wireless node to a neighboring node comprises an outgoing wireless interface, wherein the broadcasting of a data packet by each portal node to a wireless node is also a wireless interface.

6. The method of claim 5, wherein the step of detecting in a given wireless node if a data packet should not be broadcast comprises:

detecting that there is no route with a destination that matches the original sending node address;

detecting, if there is a route match, that the outgoing interface is a wireless interface and that the next-hop address of the route is different from the relaying wireless'"'"' node'"'"'s transmitting address; and

detecting, if there is a route match, that the outgoing interface is not a wireless interface and it is different from the incoming interface.

7. The method of claim 1, wherein the link-state register message broadcast by a given wireless node includes the wireless node'"'"'s node ID, the backhaul links associated with said wireless node and any client links to said wireless node.

8. The method of claim 7, further comprising enabling each said wireless node to detect when a new client link is established between a client station and said wireless node and to cause said wireless node to update its client link-state and to send a message indicating this change to its root portal, and thereby to all other said wireless nodes.

9. The method of claim 8 further comprising enabling the wireless node having the new client link to detect that the client station has roamed to it from a specific prior wireless node and for causing said detecting wireless node to send a message to said prior wireless node to inform said prior wireless node of the change in client link-state, said message being caused to propagate to all said wireless nodes as a link-state-update packet by the detecting wireless node'"'"'s root portal node.

10. The method of claim 8 wherein the step of causing said wireless node to update its client link-state and send a message indicating this change to all other said wireless nodes when there is a change in a client'"'"'s link-state includes performing said step on demand when the client has linked up to a wireless node or disassociated from a wireless node.

11. The method of claim 8 wherein the step of causing said wireless node to update its client link-state and send a message indicating this change to all other said wireless nodes when there is a change in a client'"'"'s link-state is performed periodically at predetermined times.

12. The method of claim 1 wherein each portal node operates independently of every other portal node, such that more than one portal is enabled to be active at any given time.

13. The method of claim 1 wherein the step of each wireless node identifying a unicast path back to said elected portal node comprises identifying a shortest path to said elected portal node.

14. The method of claim 1, wherein each of the data packets includes four addresses:

a transmitting node address, a receiving address within one wireless node hop, the original sending node address, and the ultimate destination address.

15. A wireless network routing system having a plurality of wireless nodes operative to select a route for the transmission of a data packet between a wireless source node and a predetermined destination node in said network, comprising:

a subset of portal nodes, wherein each portal node is elected to do the broadcasting for the entire network, wherein each portal node periodically broadcasts an announcement of its identity to all of the wireless nodes;

means for causing each wireless node to respond to said broadcast announcements to select one of the portal nodes as its root portal node, to identify a unicast route back to its root portal node, and to send a link-state register message to this portal node;

and wherein each said portal node acts in response to the receipt of said link-state register messages to aggregate them and broadcast this aggregation to each of the wireless nodes for storage therein.

16. The system of claim 15, further comprising means in each wireless node for receiving data packets from a neighboring wireless node and for detecting if each such data packet satisfies one of a plurality of predetermined conditions and means for rebroadcasting the data packet to neighboring wireless nodes if none of the conditions is satisfied.