# US 7,609,641 B2 · System and method for providing a congestion-aware routing metric for selecting a route between nodes in a multihopping communication network > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 7,609,641 B2 - Document ID: US7609641B2 - Status: Granted - Kind: B2 - Application number: 11/268,102 - Filed: 2005-11-07 - Published: 2006-05-25 - Granted: 2009-10-27 - Earliest claimed: 2004-11-05 - Assignees: MeshNetworks, Inc. - Inventors: Guenael T. Strutt; Surong Zeng; Sebnem Z. Ozer; Avinash Joshi - Web page: https://patentgrep.com/patent/US7609641B2 ## CPC - H04W 40/02: Communication route or path selection, e.g. power-based or shortest path routing - H04L 45/122: by minimising distances, e.g. by selecting a route with minimum of number of hops - H04L 45/124: {using a combination of metrics} - H04L 45/125: based on throughput or bandwidth - H04W 40/22: using selective relaying for reaching a BTS [Base Transceiver Station] or an access point - H04L 1/18: Automatic repetition systems, e.g. Van Duuren systems - H04W: WIRELESS COMMUNICATION NETWORKS (broadcast communication H04H; communication systems using wireless links for non-selective communication, e.g. wireless extensions H04M1/72) - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## 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 ### Claim 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. ### Claim 2 (depends on 1) 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. ### Claim 3 (depends on 2) 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. ### Claim 4 (depends on 1) 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. ### Claim 5 (depends on 1) 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. ### Claim 6 (depends on 1) A method as claimed in claim 1, further comprising: operating the node to provide information pertaining to the routing metric. ### Claim 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. ### Claim 8 (depends on 7) 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. ### Claim 9 (depends on 8) 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. ### Claim 10 (depends on 7) 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. ### Claim 11 (depends on 7) 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. ### Claim 12 (depends on 7) A node as claimed in claim 7, wherein: the controller further controls the node to provide information pertaining to the routing metric. ### Claim 13 (depends on 7) 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. ### Claim 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. ### Claim 15 (depends on 14) 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. ### Claim 16 (depends on 15) 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. ### Claim 17 (depends on 14) 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. ### Claim 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. ### Claim 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.