Hybrid distance vector protocol for wireless mesh networks

• US 7,787,361 B2
• Filed: 02/27/2006
• Issued: 08/31/2010
• Est. Priority Date: 07/29/2005
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Kruys, Johannes Petrus, O'Hara, Robert Bernard Jr., Rahman, Shahriar
• Primary Examiner(s): Ahmed; Salman
• Assistant Examiner(s): CHAU, PETER P
• Application Number:
  US11/364,020
• Publication Number:
  US 20070025274A1
• Time in Patent Office: 1,646 Days
• Field of Search: 370/242, 370/248, 370/250, 370/254, 370/244, 370/217, 370/360
• US Class Current: 370/217
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04W 40/26 for hybrid routing by combining proactive and reactive routing

Abstract

A method of hybrid route discovery in a mesh network is described. The method comprises the optional designation of a root node of the mesh network and formatting a route request message at an originating mesh point, where the route request messages include a hop limit parameter. If a root node has been configured, the route request is responded to with a message that describes the route to the root. If a direct route between two nodes is required, the route request message is broadcast from the originating mesh point, and the hop limit parameter limits the number of times the route request message will be forwarded. The originating mesh point receives a unicast route reply message from a neighboring mesh point, after the neighboring mesh point received the route request message. Finally, a route connecting the originating mesh point and the destination mesh point is established.

Claims

1. A method comprising:

receiving a unicast periodic message, said unicast periodic message for checking a validity of an established route between a mesh point and a destination point in a mesh network, wherein said mesh network comprises a spanning tree based routing topology connecting said mesh point to said destination point via a pre-defined tree based route of said spanning tree based routing topology comprising more hops than said established route, and wherein said spanning tree based routing topology is defined by a root node that connects each node in said mesh network with an Internet connection;

forwarding said unicast periodic message to a designated destination address associated with said destination point via said established route;

identifying a route error when a reply to said unicast periodic message is not received;

broadcasting a route request message to a plurality of mesh points in said mesh network comprising said mesh point and said destination point to determine a new optimal route between said mesh point and said destination point, wherein said route request message is broadcast using a hybrid ad-hoc on-demand distance vectoring (AODV) protocol that includes a maximum hop count comprising fewer hops than said pre-defined tree based route, and wherein said new optimal route replaces said established route; and

transmitting a unicast data packet from said mesh point through said pre-defined tree based route to said destination point until said new optimal route is established.

2. The method of claim 1, further comprising:

establishing said new optimal route based on a reply to said route request message, wherein said route request message is wirelessly broadcast;

transmitting a unicast route error message to said root node of said spanning tree based routing topology for updating route information between said mesh point and said destination point, wherein said unicast route error message is propagated to each node using said spanning tree based routing topology, and wherein each node receives a single instance of said unicast route error message; and

updating said route information maintained at said root node based on said unicast route error message.

3. The method of claim 1 wherein a common ancestor node of said mesh point and said destination point flags said unicast data packet as being transmitted intramesh within said mesh network, wherein said route request message is broadcast in response to receiving said flagged unicast data packet, and wherein said common ancestor node is communicatively located between said root node and said mesh point in said spanning tree based routing topology.

4. The method of claim 3 wherein said common ancestor node is configured to transmit said unicast data packet to said destination point without said unicast data packet having been received by said root node of said spanning tree based routing topology.

5. The method of claim 1 further comprising:

identifying an origin of said unicast data packet; and

flagging said unicast data packet if said origin is located inside outside of said mesh network.

6. The method of claim 1 further comprising:

propagating a route error message throughout said spanning tree based routing topology to avoid flooding a network with duplicate route error messages, wherein said route error message is propagated to each mesh point in said spanning tree based routing topology; and

updating route information maintained at said root node based on said route error message.

7. The method of claim 1 wherein said spanning tree based routing topology identifies a predetermined spanning tree routing path connecting said mesh point to said destination point, and wherein said predetermined spanning tree routing path comprises more hops than said established route.

8. An apparatus for maintaining a route in a mesh network comprising a plurality of mesh points, said apparatus comprising:

means for transmitting a unicast periodic message from a source point, said unicast periodic message for checking a validity of an established route between said source point and a destination point in said mesh network;

means for receiving a unicast route reply message, said unicast route reply message for confirming the validity of said established route;

means for temporarily transmitting a unicast data packet through a spanning tree based routing topology of said mesh network if said established route is not valid, until a new route between said source point and said destination point is established, wherein said spanning tree based routing topology provides a pre-defined route between said source point and said destination point, wherein said spanning tree based routing topology is defined by a root node that connects said mesh network with a network gateway, and wherein said pre-defined route comprises more hops than said established route;

means for flagging said unicast data packet as being transmitted intramesh;

means for wirelessly broadcasting, responsive to receiving said flagged unicast data packet, a routing request to one or more of said plurality of mesh points to establish said new route, using a hybrid ad-hoc on-demand distance vectoring (AODV) protocol, wherein said one or more mesh points forward said routing request through said spanning tree based routing topology according to a hop limit parameter contained within said routing request; and

means for identifying said new route based on responses to said routing request that indicate a shortest path between said source point and said destination point.

9. The apparatus of claim 8 wherein said hop limit parameter allows fewer hops than said pre-defined route.

10. The apparatus of claim 8, wherein each of the plurality of mesh points are connected through the spanning tree based routing topology, and wherein the spanning tree based routing topology only includes one root node.

11. An apparatus, comprising:

means for receiving an anticipated unicast periodic message into a mesh point, said anticipated unicast periodic message for validating an established route between a source point and a destination point in a mesh network;

means for transmitting a unicast route reply message in response to receiving said anticipated unicast periodic message, said unicast route reply message for confirming the validity of said established route;

means for transmitting a unicast error message through a pre-defined route of a spanning tree based routing topology of said mesh network if said established route is not valid, wherein each node in said mesh network receives a single instance of said unicast error message, and wherein said spanning tree based routing topology is defined by a root node that connects said mesh network with a network gateway;

means for receiving a wireless routing request comprising a hop limit parameter, wherein said wireless routing request is broadcast from said source point using a hybrid ad-hoc on-demand distance vectoring (AODV) protocol;

means for transmitting a unicast data packet from said source point to said destination point along said pre-defined route until a new route between said source point and said destination point is identified, wherein said pre-defined route contains more hops between said source point and said destination point than said established route; and

means for identifying said new route between said source point and said destination point based on responses to the wireless routing request, wherein said new route contains fewer hops than said pre-defined route.

12. The apparatus of claim 11, wherein said unicast data packet is flagged by a common ancestor node of both said source point and said destination point, and wherein said wireless routing request is broadcast in response to receiving said flagged unicast data packet.

13. A mesh point in a mesh network, said mesh point comprising:

a transmitter configured to transmit a unicast periodic message, said unicast periodic message for checking a validity of an established ad hoc distance vector route between said mesh point and a destination point, wherein said mesh network is organized as a spanning tree routing topology connecting each mesh point in the mesh network, and wherein said spanning tree routing topology is defined by a root node that connects said mesh network with a network gateway;

a memory, for storing information, coupled to said transmitter; and

a receiver coupled to said memory, wherein said receiver, in response to said unicast periodic message, is configured to receive a unicast route reply message, said unicast route reply message for confirming the validity of said established ad hoc distance vector route, wherein upon a failure to receive said unicast route reply message, said mesh point is configured to;

transmit a unicast data packet through a pre-configured path of said spanning tree routing topology connecting said mesh point to said destination point until a new route can be established that contains fewer hops than said pre-configured path; and

receive a broadcast route request message, wherein said broadcast route request message is transmitted responsive to said unicast data packet being flagged as originating within said mesh network, wherein said broadcast route request message is transmitted using a hybrid ad hoc on-demand distance vector (AODV) protocol that includes a maximum hop count comprising fewer hops than said pre-configured path, and wherein said new route is determined based on route response messages to said broadcast route request message that indicate a shortest path between said mesh point and said destination point.

14. The mesh point of claim 13, wherein said broadcast route request message is forwarded throughout said spanning tree routing topology according to said maximum hop count.

15. The mesh point of claim 13 wherein said established ad hoc distance vector route contains fewer hops than said pre-configured path.

16. A mesh point in a mesh network comprising:

a memory, for storing route information;

a wireless receiver, coupled to said memory, for receiving messages, wherein said receiver is configured to receive an anticipated unicast periodic message, said anticipated unicast periodic message for validating an established ad hoc distance vector route between a source point and a destination point of said mesh network, wherein said mesh network is organized as a spanning tree routing topology connecting each mesh point in the mesh network, and wherein said spanning tree routing topology is defined by a root node that connects said mesh network with a network gateway; and

a transmitter, coupled to said memory, for transmitting messages, wherein said transmitter is configured to transmit a unicast route reply message for confirming the validity of said established ad hoc distance vector route, wherein upon a failure to receive said anticipated unicast periodic message, said transmitter is configured to;

transmit a unicast data packet through a pre-configured route of said spanning tree routing topology connecting said source point to said destination point until a new ad hoc distance vector route can be established between said source point and said destination point, and wherein said new ad hoc distance vector route contains fewer hops than said pre-configured route;

flag said unicast data packet as being transmitted intramesh; and

receive a broadcast route request message, responsive to said flagged unicast data packet, wherein said broadcast route request message is broadcast using a hybrid ad hoc on-demand distance vector (AODV) protocol that includes a hop limit parameter comprising fewer hops than said pre-configured path, and wherein said new route is determined based on route response messages to said broadcast route request message that indicate a shortest path between said source point and said destination point.

17. The mesh point of claim 16, wherein, if said hop limit parameter in said anticipated unicast periodic message is greater than one, said transmitter is configured to forward said anticipated unicast periodic message along said established ad hoc distance vector route, and wherein said established ad hoc distance vector route contains fewer hops than said pre-configured route.

18. The mesh point of claim 16, wherein, if said anticipated unicast periodic message is not received, said transmitter is configured to propagate a route error message from said mesh point throughout said spanning tree routing topology to avoid flooding said mesh network with duplicate route error messages, and wherein said memory is configured to update stored route information to reflect said route error message.

19. A method comprising:

receiving, into a root node of a wireless mesh network, a packet from a mesh node within said wireless mesh network and directed towards a destination in a connected local area network (LAN), wherein said LAN is a separate network from said wireless mesh network;

transmitting said packet to said LAN via a root portal, wherein said root portal connects said root node of said wireless mesh network to said LAN;

forwarding said packet to one or more non-root nodes of said wireless mesh network, each of said one or more non-root nodes associated with a non-root portal, wherein said non-root portal connects said wireless mesh network to said LAN;

receiving at said root node a gratuitous route reply from said one or more non-root nodes via a spanning tree based routing topology of said wireless mesh network defined by said root node, wherein said gratuitous route reply indicates that said destination was reached via said one or more non-root portals; and

establishing a hybrid ad hoc on-demand distance vector (AODV) route between said destination and said mesh node, wherein said AODV route comprises a path including said one or more non-root nodes that sent said gratuitous route reply.

20. The method of claim 19 wherein said one or more non-root nodes communicate an existence of said non-root portal with said root node via said spanning tree based routing topology of said wireless mesh network.