Bandwidth efficient source tracing (BEST) routing protocol for wireless networks

• US 7,002,949 B2
• Filed: 06/15/2001
• Issued: 02/21/2006
• Est. Priority Date: 06/16/2000
• Status: Active Grant

• Current Assignee: Regents of the University of California (University of California)
• Original Assignee: Regents of the University of California (University of California)
• Inventors: Garcia-Luna-Aceves, Jose Joaquin, Raju, Jyoti
• Primary Examiner(s): Kizou, Hassan
• Assistant Examiner(s): PIZARRO, RICARDO M
• Application Number:
  US09/883,082
• Publication Number:
  US 20020036987A1
• Time in Patent Office: 1,712 Days
• Field of Search: 370/338, 370/351, 370/352, 370/238, 370/400, 370/255, 370/600, 370/407, 370/389, 370/392, 370/229, 370/254
• US Class Current: 370/351
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/028 Dynamic adaptation of the update intervals, e.g. event-triggered updates
• CPC Class Codes: H04L 45/18 Loop-free operations
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 40/248 Connectivity information update
• CPC Class Codes: H04W 40/28 for reactive routing
• CPC Class Codes: H04W 52/0219 where the power saving management affects multiple terminals
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

A bandwidth efficient routing protocol for wireless ad-hoc networks. This protocol can be used in ad-hoc networks because it considerably reduces control overhead, thus increasing available bandwidth and conserving power at mobile stations. It also gives very good results in terms of the throughput seen by the user. The protocol is a table-driven distance-vector routing protocol that uses the same constraints used in on-demand routing protocols, i.e., paths are used as long as they are valid and updates are only sent when a path becomes invalid. The paths used by neighbors are maintained and this allows the design of a distance-vector protocol with non-optimum routing and event-driven updates, resulting in reduced control overhead.

Claims

1. A method for routing data packets in a wireless network at a node i, comprising:

selecting a neighbor p as a next hop in a route from node i to destination j if

(i) the path from neighbor p to destination j does not include node i and does not repeat any node, and

(ii) D_ypⁱ<

D_yxⁱ for any other neighbor x and for all nodes y that are in the path from destination j to neighbor p,

where D_ypⁱ is the distance value of the route from node i to node y through neighbor p and D_ypⁱ is the distance value of the route from node i to node y through neighbor x.

2. A method as recited in claim 1,

wherein a first node considers a second as its neighbor if it hears update messages from said second node;

and

wherein said first node no longer considers said second node as its neighbor if said first node cannot send data packets to said second node.

3. A method as recited in claim 1, further comprising:

sending updates to a routing table if

a node discovers a new destination with a finite and valid path to the destination, or

a node loses the last path to a destination, or

a node suffers a distance increase to a destination.

4. A method as recited in claim 1, further comprising:

sending a unicast routing table update from a node to a neighbor that sends it a data packet, if the neighbor is upstream from it towards the destination; and

sending a unicast routing table update from a node to a neighbor that sends it a data packet when the path implied by the neighbor'"'"'s distance table entry is different from the path implied by the node'"'"'s routing table.

5. A method for routing data packets in a wireless network at a node i, comprising:

(a) selecting a neighbor p as a next hop in a route from node i to destination j if

(i) the path from neighbor p to destination j does not include node i and does not repeat any node, and

(ii) D_ypⁱ<

D_yxⁱ for any other neighbor x and for all nodes y that are in the path from destination j to neighbor p,

where D_ypⁱ is the distance value of the route from node i to node y through neighbor p and D_yxⁱ is the distance value of the route from node i to node y through neighbor x;

(b) wherein a first node considers a second as its neighbor if it hears update messages from said second node; and

(c) wherein said first node no longer considers said second node as its neighbor if said first node cannot send data packets to said second node.

6. A method as recited in claim 5, further comprising sending updates to a routing table if

a node discovers a new destination with a finite and valid path to the destination, or

a node loses the last path to a destination, or

a node suffers a distance increase to a destination.

7. A method as recited in claim 5, further comprising:

sending a unicast muting table update from a node to a neighbor that sends it a data packet, if the neighbor is upstream from it towards the destination; and

sending a unicast routing table update from a node to a neighbor that sends it a data packet when the path implied by the neighboes distance table entry is different from the path implied by the node'"'"'s routing table.

8. A method for routing data packets in a wireless network at a node i, comprising:

(a) selecting a neighbor p as a next hop in a route from node i to destination j if

(i) the path from neighbor p to destination j does not include node i and does not repeat any node, and

(ii) D_ypⁱ<

D_yxⁱ for any other neighbor x and for all nodes y that are in the path from destination j to neighbor p,

where D_yp, is the distance value of the route from node i to node y through neighbor p and D_yxⁱ is the distance value of the route from node i to node y through neighbor x; and

(b) sending updates to a routing table if

(i) a node discovers a new destination with a finite and valid path to the destination, or

(ii) a node loses the last path to a destination, or

(iii) a node suffers a distance increase to a destination.

9. A method as recited in claim 8,

wherein a first node considers a second as its neighbor if it hears update messages from said second node;

and

wherein said first node no longer considers said second node as its neighbor if said first node cannot send data packets to said second node.

10. A method as recited in claim 8, further comprising:

sending a unicast routing table update from a node to a neighbor that sends it a data packet, if the neighbor is upstream from it towards the destination; and

sending a unicast routing table update from a node to a neighbor that sends it a data packet when the path implied by the neighbors distance table entry is different from the path implied by the node'"'"'s routing table.

11. A method for routing data packets in a wireless network at a node i, comprising:

(a) selecting a neighbor p as a next hop in a route from node i to destination j if

(i) the path from neighbor p to destination j does not include node i and does not repeat any node, and

(ii) D_ypⁱ<

D_yxⁱ for any other neighbor x end for all nodes y that are in the path from destination j to neighbor p.

where D_ypⁱ is the distance value of the route from node i to node y through neighbor p and D_yxⁱ is the distance value of the route from node i to node y through neighbor x;

(b) sending a unicast routing table update from a node to a neighbor that sends it a data packet, if the neighbor is upstream from it towards the destination, and

(c) sending a unicast routing table update from a node to a neighbor that sends it a data packet when the path implied by the neighbors distance table entry is different from the path implied by the node'"'"'s routing table.

12. A method as recited in claim 11,

wherein a first node considers a second as its neighbor if it hears update messages from said second node;

and

wherein said first node no longer considers said second node as its neighbor if said first node cannot send data packets to said second node.

13. A method as recited in claim 11, further comprising sending updates to a routing table if

a node discovers a new destination with a finite and valid path to the destination, or

a node loses the last path to a destination, or

a node suffers a distance increase to a destination.

14. A method for muting data packets in a wireless network at a node i, comprising:

(a) selecting a neighbor p as a next hop in a route from node i to destination j if

(i) the path from neighbor p to destination j does not include node i and does not repeat any node, and

(ii) D_ypⁱ<

D_yxⁱ for any other neighbor x and for all nodes y that are in the path from destination j to neighbor p,

where D_ypⁱ is the distance value of the route from node i to node y through neighbor p and D_yxⁱ is the distance value of the route from node i to node y through neighbor x; and

(b) sending updates to a routing table if

(i) a node discovers a new destination with a finite and valid path to the destination, or

(ii) a node loses the last path to a destination, or

(iii) a node suffers a distance increase to a destination;

(c) wherein a first node considers a second as its neighbor if it hears update messages from said second node; and

(d) wherein said first node no longer considers said second node as its neighbor if said first node cannot send data packets to said second node.

15. A method as recited in claim 14, further comprising:

sending a unicast routing table update from a node to a neighbor that sends it a data packet, if the neighbor is upstream from it towards the destination; and

sending a unicast routing table update from a node to a neighbor that sends it a data packet when the path implied by the neighbor'"'"'s distance table entry is different from the path implied by the node'"'"'s routing table.

16. A method for routing data packets in a wireless network at a node i, comprising:

(a) selecting a neighbor p as a next hop in a route from node i to destination j if

(i) the path from neighbor p to destination i does not include node i and does not repeat any node, and

(ii) D_ypⁱ<

D_yxⁱ for any other neighbor x and for all nodes y that are in the path from destination i to neighbor p.

where D_ypⁱ is the distance value of the route from node i to node y through neighbor p and D_yxⁱ is the distance value of the route from node i to node y through neighbor x;

(b) sending a unicast routing table update from a node to a neighbor that sends it a data packet, if the neighbor is upstream from it towards the destination; and

(c) sending a unicast routing table update from a node to a neighbor that sends it a data packet when the path implied by the neighbor'"'"'s distance table entry is different from the path implied by the node'"'"'s muting table;

(d) wherein a first node considers a second as its neighbor if it hears update messages from said second node; and

(e) wherein said first node no longer considers said second node as its neighbor if said first node cannot send data packets to said second node.

17. A method as recited in claim 16, further comprising sending updates to a routing table if

a node discovers a new destination with a finite and valid path to the destination, or

a node loses the last path to a destination, or

a node suffers a distance increase to a destination.

18. A method for routing data packets in a wireless network at a node i, comprising:

(a) selecting a neighbor p as a next hop in a route from node i to destination j if

(i) the path from neighbor p to destinationj does not include node i and does not repeat any node, and

(ii) D_ypⁱ<

D_yxⁱ for any other neighbor x and for all nodes y that are in the path from destination j to neighbor p,

where D_ypⁱ is the distance value of the route from node i to node y through neighbor p and D_yxⁱ is the distance value of the route from node i to node y through neighbor x;

(b) sending updates to a routing table if

(i) a node discovers a new destination with a finite and valid path to the destination, or

(ii) a node loses the last path to a destination, or

(iii) a node suffers a distance increase to a destination;

(c) sending a unicast routing table update from a node to a neighbor that sends it a data packet, if the neighbor is upstream from it towards the destination; and

(d) sending a unicast routing table update from a node to a neighbor that sends it a data packet when the path implied by the neighbors distance table entry is different from the path implied by the node'"'"'s routing table.

19. A method as recited in claim 18,

wherein a first node considers a second as its neighbor if it hears update messages from said second node;

and

wherein said first node no longer considers said second node as its neighbor if said first node cannot send data packets to said second node.

20. A method for routing data packets in a wireless network at a node i, comprising:

(a) selecting a neighbor p as a next hop in a route from node i to destination j if

(i) the path from neighbor p to destination j does not include node i and does not repeat any node, and

(ii) D_yp<sup>i<

D</sup>_yxⁱ for any other neighbor x and for all nodes y that are in the path from destination i to neighbor p,

where D_ypⁱ is the distance value of the route from node i to node y through neighbor p and D_yxⁱ is the distance value of the route from node i to node y through neighbor x;

(b) sending updates to a routing table if

(i) a node discovers a new destination with a finite and valid path to the destination, or

(ii) a node loses the last path to a destination, or

(iii) a node suffers a distance increase to a destination.

(c) sending a unicast routing table update from a node to a neighbor that sends it a data packet, if the neighbor is upstream from it towards the destination; and

(d) sending a unicast muting table update from a node to a neighbor that sends it a data packet when the path implied by the neighbor'"'"'s distance table entry is different from the path implied by the node'"'"'s routing table;

(e) wherein a first node considers a second as its neighbor if it hears update messages from said second node; and

(f) wherein said first node no longer considers said second node as its neighbor if said first node cannot send data packets to said second node.