Method and system for loop-free ad-hoc routing

• US 20080062916A1
• Filed: 09/07/2006
• Published: 03/13/2008
• Est. Priority Date: 09/07/2006
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Garcia-Luna-Aceves, Jose J., Mosko, Marc E.
• Granted Patent: US 7,567,547 B2
• Time in Patent Office: Days
• US Class Current: 370/328
• 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/32 Flooding denial of service attacks H04L63/1458
• CPC Class Codes: H04W 40/28 for reactive routing

Abstract

One embodiment of the present invention provides a system that facilitates loop-free ad-hoc routing in a wireless network. During operation, the system advertises a local sequence number associated with a local node for a destination node, and receives a first route request at the local node, wherein the route request specifies a source node, the destination node, and a first sequence number. The system further selectively maintains a record, which indicates the source node, the destination node, the first sequence number, and a node from which the route request is received. The system also selectively forwards 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 sequence number which is less than the first sequence number and less than or equal to the advertised local sequence number.

Claims

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.