Bandwidth efficient source tracing (BEST) routing protocol for wireless networks
First Claim
1. A method for routing data packets in a wireless network at a node i, comprising:
- selecting a neighbor p as the 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) Diyp<
Diyx for any other neighbor x and for all nodes y that are in the path from destination j to neighbor p, where Diyp is the distance value of the route from node i to node y through neighbor p and Diyx is the distance value of the route from node i to node y through neighbor x.
2 Assignments
0 Petitions
Accused Products
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.
-
Citations
20 Claims
-
1. A method for routing data packets in a wireless network at a node i, comprising:
-
selecting a neighbor p as the 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) Diyp<
Diyx for any other neighbor x and for all nodes y that are in the path from destination j to neighbor p,where Diyp is the distance value of the route from node i to node y through neighbor p and Diyx is the distance value of the route from node i to node y through neighbor x. - View Dependent Claims (2, 3, 4)
-
-
5. A method for routing data packets in a wireless network at a node i, comprising:
-
(a) selecting a neighbor p as the next hop in a route from node i to destination if (i) the path from neighbor p to destination j does not include node i and does not repeat any node, and (ii) Diyp<
Diyx for any other neighbor x and for all nodes y that are in the path from destination j to neighbor p,where Diyp is the distance value of the route from node i to node y through neighbor p and Diyx 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. - View Dependent Claims (6, 7)
-
-
8. A method for routing data packets in a wireless network at a node i, comprising:
-
(a) selecting a neighbor p as the 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) Diyp<
Diyx for any other neighbor x and for all nodes y that are in the path from destination j to neighbor p,where Diyp is the distance value of the route from node i to node y through neighbor p and Diyx 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. - View Dependent Claims (9, 10)
-
-
11. A method for routing data packets in a wireless network at a node i, comprising:
-
(a) selecting a neighbor p as the 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) Diyp<
Diyx for any other neighbor x and for all nodes y that are in the path from destination j to neighbor p,where Diyp is the distance value of the route from node i to node y through neighbor p and Diyx 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 routing table. - View Dependent Claims (12, 13, 15, 17, 19)
-
-
14. A method for routing data packets in a wireless network at a node i, comprising:
-
(a) selecting a neighbor p as the 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) Diyp<
Diyx for any other neighbor x and for all nodes y that are in the path from destination j to neighbor p,where Diyp is the distance value of the route from node i to node y through neighbor p and Diyx 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.
-
-
16. A method for routing data packets in a wireless network at a node i, comprising:
-
(a) selecting a neighbor p as the 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) Diyp<
Diyx for any other neighbor x and for all nodes y that are in the path from destination j to neighbor p,where Diyp is the distance value of the route from node i to node y through neighbor p and Diyx 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 routing 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.
-
-
18. A method for routing data packets in a wireless network at a node i, comprising:
-
(a) selecting a neighbor p as the 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) Diyp<
Diyx for any other neighbor x and for all nodes y that are in the path from destination j to neighbor p,where Diyp is the distance value of the route from node i to node y through neighbor p and Diyx 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 neighbor'"'"'s distance table entry is different from the path implied by the node'"'"'s routing table.
-
-
20. A method for routing data packets in a wireless network at a node i, comprising:
-
(a) selecting a neighbor p as the 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) Diyp<
Diyx for any other neighbor x and for all nodes y that are in the path from destination j to neighbor p,where Diyp is the distance value of the route from node i to node y through neighbor p and Diyx 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 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.
-
Specification