Hybrid distance vector protocol for wireless mesh networks

• US 20070025274A1
• Filed: 02/27/2006
• Published: 02/01/2007
• 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: Rahman, Shahriar, O'Hara, Robert, Kruys, Johannes
• Granted Patent: US 7,787,361 B2
• Time in Patent Office: Days
• US Class Current: 370/254
• 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 of mesh point discovery in a mesh network, said method comprising:

formatting a route request message at a first mesh point, said route request message comprising a hop limit parameter;

broadcasting said route request message from said first mesh point, wherein said hop limit parameter limits a number of times said route request message will be forwarded through receiving mesh points;

receiving a unicast route reply message from a neighboring mesh point, wherein said neighboring mesh point is in receipt of said route request message; and

establishing a route to said neighboring mesh point.

2. The method of claim 1 wherein said route request message further comprises a unique sequence number, wherein any route reply messages sent in response to said route request message contain said unique sequence number.

3. The method of claim 2 wherein said establishing a route to said neighboring mesh point comprises:

comparing sequence numbers in a received route reply message and said route request message; and

if said sequence numbers match, storing route information pertaining to said neighboring mesh point.

4. The method of claim 2 further comprising:

receiving a plurality of unicast route reply messages from a plurality of neighboring mesh points;

comparing sequence numbers in said route request message and said plurality of route reply messages; and

storing route information pertaining to each of said plurality of neighboring mesh points sending a route reply message with a matching sequence number.

5. The method of claim 1 wherein said route request message comprises a request to locate a specific mesh point.

6. The method of claim 1 wherein said route request message comprises a request to link to a specific address outside the mesh network.

7. The method of claim 1 wherein said hop limit parameter is set to one, said hop limit parameter of one for instructing any mesh point receiving said route request message not to forward said route request message.

8. The method of claim 1 wherein said hop limit parameter is set to two, said hop limit parameter of two for instructing any mesh point receiving said route request message and seeing a hop limit parameter of two, to decrement said hop limit parameter and forward said route request message with said decremented hop limit parameter.

9. A method of route maintenance in a mesh network, said method comprising:

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

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

10. The method of claim 9, further comprising:

if said unicast route reply is not received, performing a route discovery and update process, said route discovery and update process comprising;

broadcasting a route request message from said mesh point;

discovering a new neighboring mesh point;

propagating a route error message from said mesh point via said new neighboring mesh point;

said route error message propagated throughout said tree based routing topology; and

updating route information in response to said route error message.

11. The method of claim 9 wherein said established route is an established route in a tree based routing topology.

12. The method of claim 9 wherein said established route is an on-demand ad hoc distance vector route.

13. A method of route maintenance in a mesh network, said method comprising:

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

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

14. The method of claim 13 further comprising;

forwarding a received periodic message to a designated destination address, if a hop limit parameter in said periodic message is greater than one.

15. The method of claim 14 wherein said forwarding comprises searching for said destination address in a hybrid distance vector protocol route table prior to forwarding said route request message.

16. The method of claim 15 wherein said searching further comprises searching for said destination address in a hybrid distance vector protocol bridge table if said destination address is not found in said hybrid distance vector protocol route table.

17. The method of claim 14 wherein said forwarding comprises shipping said received periodic message to a root bridge of said tree based routing topology for forwarding to said destination address.

18. The method of claim 13 further comprising:

if said anticipated unicast periodic message is not received, propagating a route error message from said mesh point throughout a tree based routing topology; and

updating route information based on said route error message.

19. An apparatus for maintaining a route in a mesh network, said apparatus comprising:

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

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

20. An apparatus for maintaining a route in a mesh network, said apparatus comprising:

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

a 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.

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

a transmitter, for transmitting messages;

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

a receiver coupled to said memory, for receiving message, wherein said transmitter transmits a unicast periodic message from said mesh point, said periodic message for checking the validity of an established route between said mesh point and another mesh point in said mesh network, and said receiver, in response to said unicast periodic message, receives a unicast route reply message, said route reply message for confirming the validity of said established route.

22. The mesh point of claim 21, wherein if said unicast route reply is not received, said transmitter initiates a route discovery and update process, said route discovery and update process comprising:

said transmitter broadcasting a route request message from said mesh point;

said receiver receiving a route response message from a neighboring mesh point;

said transmitter propagating, via said neighboring mesh point, a route error message throughout a tree base routing topology of said mesh network; and

said memory updating stored route information, in response to said route error message.

23. The mesh point of claim 21 wherein said established route is an established route in tree based routing topology.

24. The mesh point of claim 21 wherein said established route is an on-demand ad hoc distance vector route.

25. A mesh point in a mesh network comprising:

a memory, for storing route information;

a receiver, coupled to said memory, for receiving messages; and

a transmitter, coupled to said memory, for transmitting messages, wherein said receiver is configured to receive an anticipated unicast periodic message, said periodic message for validating an established route between two mesh points in said mesh network, and said transmitter is configured to transmit, in response to receiving said anticipated unicast periodic message, a unicast route reply message, said unicast route reply message for confirming the validity of said established route.

26. The method of claim 25, wherein said receiver is further configured to receive a periodic message addressed to a destination mesh point, and, if a hop limit parameter in said periodic message is greater than one, said transmitter is configured to forward said periodic message along a route between said mesh point and said destination mesh point, said route stored in said memory.

27. The mesh point of claim 25, 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 a tree based routing topology, and said memory is configured to update stored route information to reflect said route error message.

28. A method for utilizing a wireless mesh network with multiple portals, said method comprising:

receiving, into a root node, a packet from a source within said wireless mesh network and directed towards a destination in a connected local area network LAN;

forwarding said packet via a plurality of uplinks, each of said plurality of uplinks connected with one of a plurality of portals in said wireless mesh network;

receiving, into one of said plurality of portals, a reply from said destination; and

establishing a route between said destination and said source, said route utilizing said one of said plurality of portals.