Granted Patent B2

US 7,567,547 · App. 11/517,203 · Granted Jul 28, 2009

Abstract

Claims (88)

1. A method for facilitating loop-free ad-hoc routing in a wireless network, the method comprising:

advertising a local integer sequence number associated with a local node for a destination node;

receiving a first route request at the local node, wherein the route request specifies a source node, the destination node, and a first integer sequence number;

selectively maintaining a record at the local node, wherein the record indicates the source node, the destination node, the first sequence number, and a node from which the route request is received; and

selectively forwarding a second route request based on the received route request, wherein the second route request specifies the source node, the destination node, and a second integer sequence number which is less than the first sequence number and less than or equal to the advertised local sequence number.

2. The method of claim 1 , wherein selectively maintaining the record at the local node involves:

determining whether the local node has previously received the first route request; and

if not, producing the record.

3. The method of claim 1 , wherein the first route request includes a first time-to-live (TTL) value; and wherein the method further comprises:

producing a second TTL value by reducing the first TTL value;

determining whether the second TTL value is below a threshold; and

if not, including the second TTL value in the second route request.

4. The method of claim 1 , wherein selectively forwarding the second route request involves:

setting the second sequence number to be the lesser value of:

the advertised local sequence number, and

the first sequence number reduced by a spacing interval.

5. The method of claim 1 , further comprising:

determining a sequence number which is greater than any sequence number advertised by a successor node for the destination node with respect to the local node and which less than the first sequence number specified by the first route request; and

selectively sending a route reply to the node that sends the first route request, wherein the route reply specifies the determined sequence number.

6. The method of claim 1 , further comprising:

initiating a route request for the destination node at the local node, comprising:

including the advertised local sequence number in the initiated route request;

including a TTL value in the initiated route request; and

broadcasting the initiated route request to one or more neighbor nodes.

7. The method of claim 1 , further comprising:

receiving a first route reply for the destination node, wherein the received route reply specifies a third integer sequence number associated with a node which sends the route reply; and

selectively forwarding a second route reply, based on the first route reply, to a node which sends the first route request, wherein the second route reply contains a sequence number that is greater than the third sequence number.

8. The method of claim 7 , wherein the first route reply is allowed to include characteristic information about a path for the destination node, thereby facilitating selection of a preferred path to the destination node; and

wherein the method further comprises cryptically authenticating, encrypting, or decrypting a routing control message, which can be a routing request or a routing reply.

9. The method of claim 1 , wherein the local node is identified by an Internet Protocol (IP) address, a locally assigned number, a locally assigned name, a Domain Naming System (DNS) name, an IP subnet address, or a link-layer Medium-Access Control (MAC) address.

10. A system for facilitating loop-free ad-hoc routing in a wireless network, the system comprising:

an advertising mechanism configured to advertise a local integer sequence number associated with a local node for a destination node;

a route-request receiving mechanism configured to receive a first route request at the local node, wherein the route request specifies a source node, the destination node, and a first integer sequence number;

a storage mechanism configured to selectively maintain a record at the local node, wherein the record indicates the source node, the destination node, the first sequence number, and a node from which the route request is received; and

a forwarding mechanism configured to selectively forward a second route request based on the received route request, wherein the second route request specifies the source node, the destination node, and a second integer sequence number which is less than the first sequence number and less than or equal to the advertised local sequence number.

11. The system of claim 10 , wherein while selectively maintaining the record at the local node, the storage mechanism is configured to:

determine whether the local node has previously received the first route request; and

if not, to produce the record.

12. The system of claim 10 , wherein the first route request includes a first time-to-live (TTL) value; and wherein the system further comprises:

a TTL computation mechanism configured to:

produce a second TTL value by reducing the first TTL value;

determine whether the second TTL value is below a threshold; and

to include the second TTL value in the second route request based on the determination.

13. The system of claim 10 , wherein while selectively forwarding the second route request, the forwarding mechanism is configured to:

set the second sequence number to be the lesser value of:

the advertised local sequence number, and

the first sequence number reduced by a spacing interval.

14. The system of claim 10 , further comprising a route-reply mechanism configured to:

determine a sequence number which is greater than any sequence number advertised by a successor node for the destination node with respect to the local node and which is less than the first sequence number specified by the first route request; and

to selectively send a route reply to the node that sends the first route request, wherein the route reply specifies the determined sequence number.

15. The system of claim 10 , further comprising a route-request initiation mechanism configured to:

initiate a route request for the destination node at the local node;

include the advertised local sequence number in the initiated route request;

include a TTL value in the initiated route request; and

to broadcast the initiated route request to one or more neighbor nodes.

16. The system of claim 10 , further comprising:

a route-reply receiving mechanism configured to receive a first route reply for the destination node, wherein the received route reply specifies a third integer sequence number associated with a node which sends the route reply; and

a route-reply forwarding mechanism configured to selectively forward a second route reply, based on the first route reply, to a node which sends the first route request, wherein the second route reply contains a sequence number that is greater than the third sequence number.

17. The system of claim 16 , wherein the first route reply is allowed to include characteristic information about a path for the destination node, thereby facilitating selection of a preferred path to the destination node; and

wherein the system further comprises a security mechanism configured to cryptically authenticate, encrypt, or decrypt a routing control message, which can be a routing request or a routing reply.

18. The system of claim 10 , wherein the local node is identified by an IP address, a locally assigned number, a locally assigned name, a DNS name, an IP subnet address, or a link-layer MAC address.

19. A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for facilitating loop-free ad-hoc routing in a wireless network, the method comprising:

advertising a local integer sequence number associated with a local node for a destination node;

receiving a first route request at the local node, wherein the route request specifies a source node, the destination node, and a first integer sequence number;

selectively maintaining a record at the local node, wherein the record indicates the source node, the destination node, the first sequence number, and a node from which the route request is received; and

selectively forwarding a second route request based on the received route request, wherein the second route request specifies the source node, the destination node, and a second integer sequence number which is less than the first sequence number and less than or equal to the advertised local sequence number.

20. The computer-readable storage medium of claim 19 , wherein selectively maintaining the record at the local node involves:

determining whether the local node has previously received the first route request; and

if so, producing the record.

21. The computer-readable storage medium of claim 19 , wherein the first route request includes a first time-to-live (TTL) value; and wherein the method further comprises:

producing a second TTL value by reducing the first TTL value;

determining whether the second TTL value is below a threshold; and

if not, including the second TTL value in the second route request.

22. The computer-readable storage medium of claim 19 , wherein selectively forwarding the second route request involves:

setting the second sequence number to be the lesser value of:

the advertised local sequence number, and

the first sequence number reduced by a spacing interval.

23. The computer-readable storage medium of claim 19 , the method further comprising:

determining a sequence number which is greater than any sequence number advertised by a successor node for the destination node with respect to the local node and which less than the first sequence number specified by the first route request; and

selectively sending a route reply to the node that sends the first route request, wherein the route reply specifies the determined sequence number.

24. The computer-readable storage medium of claim 19 , the method further comprising:

initiating a route request for the destination node at the local node, comprising:

including the advertised local sequence number in the initiated route request;

including a TTL value in the initiated route request; and

broadcasting the initiated route request to one or more neighbor nodes.

25. The computer-readable storage medium of claim 19 , the method further comprising:

receiving a first route reply for the destination node, wherein the received route reply specifies a third integer sequence number associated with a node which sends the route reply; and

selectively forwarding a second route reply, based on the first route reply, to a node which sends the first route request, wherein the second route reply contains a sequence number that is greater than the third sequence number.

Assignments (10)