System and method for providing a congestion-aware routing metric for selecting a route between nodes in a multihopping communication network

• US 7,609,641 B2
• Filed: 11/07/2005
• Issued: 10/27/2009
• Est. Priority Date: 11/05/2004
• Status: Active Grant

• Current Assignee: ARRIS Enterprises LLC (CommScope Holding Company, Inc.)
• Original Assignee: MeshNetworks, Inc. (Motorola Solutions, Inc.)
• Inventors: Joshi, Avinash, Ozer, Sebnem Z., Zeng, Surong, Strutt, Guenael T.
• Primary Examiner(s): Yao, Kwang B
• Assistant Examiner(s): Elpenord, Candal
• Application Number:
  US11/268,102
• Publication Number:
  US 20060109787A1
• Time in Patent Office: 1,450 Days
• Field of Search: 370/235, 370237-238, 370/338, 370/401
• US Class Current: 370/238
• CPC Class Codes: H04L 1/18 Automatic repetition systems, e.g. Van Duuren systems
• CPC Class Codes: H04L 45/122 by minimising distances, e.g. by selecting a route with minimum of number of hops
• CPC Class Codes: H04L 45/124 using a combination of metrics
• CPC Class Codes: H04L 45/125 based on throughput or bandwidth
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 40/22 using selective relaying for reaching a BTS [Base Transceiver Station] or an access point

Abstract

A system and method for calculating a routing metric that can select the route providing the best throughput in a multihopping network (100), based on one or more parameters including completion rates, data rates, MAC overhead and congestion. The system and method are capable of selecting a route in a multihopping network (100) having a high throughput, comprising calculating a routing metric at one or more nodes (102, 106, 107), wherein the routing metric enables the one or more nodes (102, 106, 107) to select the route in the network (100). The routing metric can include network information such as the raw data rate, the completion rate, and the media access control overhead and congestion.

Claims

1. A method of operation of a node for routing data in a wireless network, the method comprising:

for one or more routes from the node to another node;

determining information pertaining to transmission of a packet, the information comprising a packet length, a data rate, a packet completion rate, a transmission time of the packet, an additional time for retransmission of a failed packet, and a time elapsed between arrival of a received packet at the node and a first attempt at transmission of a packet by the node in response to the received packet, and

calculating a routing metric based on the determined information; and

selecting a route having a best routing metric for communication of at least one subsequent packet from the node to the another node.

2. A method as claimed in claim 1, further comprising:

operating the node to allocate an amount of bandwidth for transmission of the subsequent packet based on the routing metric of the selected route.

3. A method as claimed in claim 2, further comprising:

operating the node to transmit a plurality of said subsequent packets to achieve a level of throughput based on the amount of bandwidth allocated for transmission.

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

operating the node to determine the another node to which to transmit the subsequent packet based on the routing metric.

5. A method as claimed in claim 1, further comprising:

performing the determining step for a plurality of nodes in the network; and

calculating the routing metric based on the respective information determined at each of the plurality of nodes.

6. A method as claimed in claim 1, further comprising:

operating the node to provide information pertaining to the routing metric.

7. A node, operating within a wireless communication network, the node comprising:

a transceiver, operating to transmit and receive packets; and

a controller, operating to;

determine information pertaining to transmission of a packet each of one or more routes from the node to another node, the information comprising a packet length, a data rate, a packet completion rate, a transmission time of the packet, an additional time for retransmission of a failed packet by the transceiver, and a time elapsed between arrival of a received packet at the transceiver and a first attempt at transmission of a packet by the transceiver in response to the received packet,

calculate a routing metric based on the determined information for each of the one or more routes, and

select a route having a best routing metric for communication of at least one subsequent packet.

8. A node as claimed in claim 7, wherein:

the controller further allocates an amount of bandwidth for transmission of the subsequent packet based on the routing metric of the selected route.

9. A node as claimed in claim 8, wherein:

the controller further controls the transceiver to transmit a plurality of said subsequent packets to achieve a level of throughput based on the amount of bandwidth allocated for transmission.

10. A node as claimed in claim 7, wherein:

the controller further determines the another node to which to control the transceiver to transmit the subsequent packet based on the routing metric of the selected route.

11. A node as claimed in claim 7, wherein:

the controller further calculates the routing metric based on the determined information and information pertaining to the routing metric received from a plurality of other nodes in the network.

12. A node as claimed in claim 7, wherein:

the controller further controls the node to provide information pertaining to the routing metric.

13. A node as claimed in claim 7, wherein:

the controller further controls the transceiver to transmit information pertaining to the routing metric for receipt by at least one other node in the network.

14. A method for communicating in a wireless communication network, the method comprising:

operating a plurality of nodes, communicating in the wireless network, to each determine respective information comprising a packet length, a data rate, a packet completion rate, a transmission time of a packet, an additional time for retransmission of a failed packet, and a time elapsed between arrival of a received packet and a first attempt at transmission of a packet by the node in response to the received packet;

operating the plurality of nodes to transmit their respective information for receipt by other nodes; and

operating each of the plurality of nodes to calculate a respective routing metric based on their respective information and the information received from the other nodes.

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

operating each of the nodes to allocate a respective amount of bandwidth for transmission of the subsequent packet based on their respective calculated routing metric.

16. A method claimed in claim 15, further comprising:

operating each of the nodes to transmit a respective plurality of subsequent packets to achieve a respective level of throughput based on their respective amount of bandwidth allocated for transmission.

17. A method as claimed in claim 14, further comprising:

operating each of the nodes to determine to which other node to transmit their respective subsequent packet based on their respective routing metric.

18. A method for providing a congestion-aware routing metric for selecting a route between nodes in a multihopping communication network, the method comprising:

calculating an associated routing metric for each of a plurality of routes between a source node and a destination node based on one or more parameters including a completion rate, a data rates, a media access control (MAC) overhead and a congestion, wherein one or more of the plurality of routes comprise a multihop route, and further wherein the associated routing metric of the multihop route comprises a cumulative routing metric calculated using an individual routing metric of each of a plurality of hops within the multihopping route;

selecting a route for communication between the source node and the destination node with the best associated routing metric;

determining whether communication in one hop of the multihop route and communication in another hop of the multihop route can occur concurrently;

allotting more bandwidth along the multihop route when the communications can occur concurrently; and

decreasing the throughput along the multihop route when the communications cannot occur concurrently.

19. A method for providing a congestion-aware routing metric for selecting a route between nodes in a multihopping communication network, the method comprising:

calculating an associated routing metric for each of a plurality of routes between a source node and a destination node based on one or more parameters including a completion rate, a data rates, a media access control (MAC) overhead and a congestion, wherein the calculating the associated routing metric for each of a plurality of routes between a source node and a destination node further is based on a transmission time of a packet, an extra time required for retransmission of a failed packet, a time elapsed between the packet arrival to the node'"'"'s queue and this packet'"'"'s first transmission attempt; and

selecting a route for communication between the source node and the destination node with the best associated routing metric.