Determining throughput between hosts

[0001] The invention relates generally to communications. More particularly, the invention relates to a method and apparatus of determining throughput between hosts.

[0002] Packet networking is a form of data communication in which data packets are routed from a source device to a destination device. Packets can be transmitted directly between a source device and a destination device, or the packets can be relayed through a number of intermediate devices.

[0003] A wireless network can include a wireless device (client) being connected to a network through a base station (or gateway) that is wired to the network. The wireless device can transmit data packets that are received by the gateway and then routed through the network. The wireless network can include many gateways that are each wired to the network.

[0004] FIG. 1 shows a prior art mesh network. As shown, clients 150, 160 are able to access an internet network 100 through a wired network 105, and a mesh network that includes gateways 110, 120 and access nodes 130, 140. The mesh network infrastructure including the gateways 110, 120 and the access nodes 130, 140 can be placed, for example, on top of streetlights.

[0005] Wireless mesh networks can be more complex than typical networks because wireless networks typically are subject to environmental conditions. For example, wireless links can be subjected to interference, fading and multi-path. As a result, wireless mesh networks typically desire monitoring of the interconnections of the wireless mesh network. A fundamental operating quality metric that is typically desired by a network operator is the data throughput between access nodes or hosts of the network. More specifically, the throughput between access nodes and clients is a very useful quality parameter.

[0006] The throughput between hosts of a network can be used to gauge the quality and health of the network. Additionally, throughput between hosts of a network can be used as a measure for comparing different networks.

[0007] Wireless mesh network can include access nodes within the mesh network performing routing through the mesh network based upon one or more network operating parameters. Data throughput between gateways and access nodes of the network can be useful in selecting or maintaining selections of routing paths through the mesh network.

[0008] Prior art systems measure throughput to a remote host by setting up a server at the remote host. This is difficult because setting up the server requires access to the remote host. Additionally, the server is required to have special throughput measurement software to be configured and run.

[0009] It is desirable to have a wireless mesh network that includes access nodes that can determine data throughput between separate hosts of the mesh network. It is desirable that the throughput determinations not require a separate server having throughput measurement software.

[0010] The invention includes an apparatus and method for estimating throughput between hosts of networks. The estimation can be adapted for determining throughput between devices within 802.11 wireless mesh networks.

[0011] An embodiment includes a method of determining throughput between a first host and a second host of at least one network. The method includes the first host intentionally corrupting ICMP packets by manipulating a checksum of the ICMP packets. The first host sends the corrupted ICMP packets to the second host through the at least one network. The first host additionally sends non-corrupted ICMP packets to the second host. Based on responses from the second host to the ICMP packets, the first host estimates a throughput between the first host and the second host.

[0012] Another embodiment includes a method of determining throughput of an 802.11 link between an access node and a another access node, or a client of a wireless mesh network. The method includes the access node intentionally corrupting ping packets by manipulating a layer four checksum of the ping packets while maintaining a proper layer two CRC of the ping packets. The access node sends the corrupted ping packets to the client. Based on layer two responses from the client, the access node estimates a downlink throughput from the access node to the client. The downlink throughput is estimated by the access node estimating a number of packets received by the client by counting how many layer two responses the access node receives back from the client, and estimating the downlink throughput by multiplying the number of packets received by a size of the packets, and dividing a result by a downlink transmit time.

[0013] Other aspects and advantages of the present invention will become apparent from the following detailed description, taken in conjunction with the accompanying drawings, illustrating by way of example the principles of the invention.

[0014] FIG. 1 shows a prior art mesh network.

[0015] FIG. 2 is a flow chart that shows the steps of a method of determining data throughput between a first host and a second host.

[0016] FIG. 3A is a flow chart that shows the steps of a method of determining data throughput of a first direction between a first host and a second host of an 802.11 mesh network.

[0017] FIG. 3B is a flow chart that shows the steps of a method of determining data throughput of a round trip between a first host and a second host of an 802.11 mesh network.

[0018] FIG. 3C is a flow chart that shows the steps of a method of determining data throughput of a second direction between a first host and a second host of an 802.11 mesh network.

[0019] FIG. 4 shows a data packet that includes a layer four checksum that is intentionally corrupted, and a layer two CRC that is correctly set.

[0020] FIG. 5A is a flow chart that shows the steps of a method of determining data throughput of a round trip between a first host and a second host of one or more networks.

[0021] FIG. 5B is a flow chart that shows the steps of a method of determining data throughput of a first direction between a first host and a second host of one or more networks.

[0022] FIG. 5C is a flow chart that shows the steps of a method of determining data throughput of a second direction between a first host and a second host of one or more networks.

[0023] As shown in the drawings for purposes of illustration, the invention is embodied in an apparatus and method for estimating throughput between hosts of networks. The estimation can be adapted for determining throughput between devices within 802.11 wireless mesh networks. The estimations do not require a throughput measurement server to be set up at a remote host.

[0024] FIG. 2 is a flow chart that shows the steps of a method of determining data throughput between a first host and a second host. A first step 210 includes the first host intentionally corrupting ICMP packets by manipulating a checksum of the ICMP packets. A second step 220 includes the first host sending the corrupted ICMP packets to the second host through the at least one network. A third step 230 includes the first host sending also non-corrupted ICMP packets to the second host. A fourth step 240 includes the first host estimating a throughput between the first host and the second host based on responses from second host to the ICMP packets (as will be described, this includes both corrupted ICMP packets, and non-corrupted ICMP packets). The throughput includes a first direction throughput from the first host to the second host, a second direction throughput from the second host to the first host, and a round trip throughput between the first host and the second host.

[0025] Hosts

[0026] A host can generally be defined as a device connected to a network. For example, a non-exhaustive list of exemplary hosts includes a router, a server, a computer, a laptop, or an access point.

[0027] ICMP Packets

[0028] To allow routers in an internet to report errors or provide information about unexpected circumstances, TCP/IP protocols include a special-purpose message mechanism. The mechanism, known as the Internet Control Message Protocol (ICMP), is a required part of internet protocol (IP) and must be included in every IP implementation.

[0029] Like all other traffic, ICMP messages travel across the internet in the data portion of IP datagrams. The ultimate destination of an ICMP message is not an application program or user on the destination machine, but rather, the IP software on that machine. If the ICMP determines that a particular higher-level protocol or application program has caused a problem, it will inform the appropriate module. Generally, ICMP allows routers to send error or control messages to other routers or hosts. ICMP provides communication between the IP software on one machine (host) and the IP software on another machine (host).

[0030] Generally, an arbitrary host can send an ICMP message to any other host. Therefore, a host can use ICMP to correspond with a router or another host. An advantage of allowing hosts to use ICMP is that it provides a single mechanism for all control and information messages.

[0031] ICMP is an error reporting mechanism. It provides a way for routers that encounter an error to report the error to the original source. Although the protocol specification outlines intended uses of ICMP and suggests possible actions to take in response to error reports, ICMP does not fully specify the action to be taken for each possible error.

[0032] A properly transmitted ICMP packet (having a proper checksum) causes a receiving host to respond (also referred to as an echo) to the ICMP packet. That is, when a first host sends a proper ICMP packet to a second host, the second host generates a response. The responses, however, echo the payload of the ICMP request packet, and therefore, occupy transmission bandwidth.

[0033] FIG. 3A is a flow chart that shows the steps of a method of determining data throughput of a first direction between a first host and a second host of an 802.11 mesh network. More specifically, FIG. 3A provides the steps of a method of determining throughput of an 802.11 link between an access node (first host), and another access node or client (second host) of a wireless mesh network through the use of ping packets. A first step 310 includes the access node intentionally corrupting ping packets by manipulating a checksum of the ping packets while maintaining a proper CRC of the ping packets. A second step 320 includes the access node sending the corrupted ping packets to the client. A third step 330 includes the access node estimating a number of packets received by the client by counting how many layer two responses the access node receives back from the client. A fourth step 340 estimating the downlink throughput by multiplying the number of packets received by a size of the packets, and dividing a result by a downlink transmit time.

[0034] Ping Packets

[0035] TCP/IP protocols can facilitate in identification of network problems. One of the most frequently used debugging tools invokes ICMP echo request and echo reply messages. On many systems, the command invoked to send ICMP echo requests is named “ping”. Sophisticated versions of ping send a series of ICMP echo requests, capture responses, and provide statistics about datagram loss. The ping allows specification of the length of the data being sent and the interval between requests. Less sophisticated versions merely send one ICMP echo request and await a reply.

[0036] The ping packets (as will be shown later) include a cyclic redundancy check (CRC) and a checksum. The ping packets that have a corrupted checksum will not generate a response at the second host. However, the layer two CRC associated with 802.11 packets, do generate a response. The CRC response only includes a very small number of bits, and therefore, does not interfere with downlink throughput. The corrupted ping packets do not generate a response. This is desirable because response packets generate interference with first direction (downlink) packets, and therefore, make estimates of the first direction (downlink) throughput more difficult.

[0037] An exemplary embodiment includes the downlink transmit time being approximated by the time duration of the transmission at the first host.

[0038] FIG. 3B is a flow chart that shows the steps of a method of determining data throughput of a round trip between a first host and a second host of an 802.11 mesh network. A first step 312 includes the access node transmitting non-corrupted ping packets to the client. A second step 322 includes the access node counting responses by the client to the ping packets per unit of time. The third step 332 includes the access node determining a round trip transmission time. A fourth step 342 includes the access node estimating the round trip throughput by multiplying the number of response received by the access node by the size of the packets, and dividing a result by the round trip transmission time.

[0039] The responses to the ping packets are counted by counting the ping responses received by the first host.

[0040] The round trip transmission time can be determined by comparing the time of reception of a response to a time stamp included in the ping packets. That is, the time stamp provides the start time of transmission from the first host, and the time of reception of a response provides the end time of the round trip time. Alternatively, the transmission start time can be stored by the first host, and compared with the reception of a response.

[0041] FIG. 3C is a flow chart that shows the steps of a method of determining data throughput of a second direction (uplink) between a first host and a second host of an 802.11 mesh network. A first step 314 includes the access node estimating an uplink transmit time from the round trip transmission time and the downlink transmit time. A second step 324 includes the access node estimating the uplink throughput by multiplying the number of response received by the access node by the size of the packets, and dividing a result by the uplink transmit time.

[0042] Generally, the uplink transmit time can be estimated from the downlink transmit time and the round trip transmission time. More specifically, the uplink transmit time can be determined by subtracting the downlink transmit time from the round trip transmission time.

[0043] As stated before, the number of response received by the access node is estimated by counting the number of response received by the access node (first host).

[0044] FIG. 4 shows a data packet that includes a checksum that is intentionally corrupted, and a CRC that is correctly set. As shown, the packet includes a layer two CRC 410, a layer three IP header 420, a layer four ICMP header 430 that includes a checksum and a payload 440. As described, the embodiments of FIGS. 3A, 3B, 3C include ping packets that include a proper CRC, and an intentionally corrupted checksum. The proper CRCs will generate low data bit CRC responses, but the corrupted checksums do not generate high data bit checksum responses. The non-corrupted CRC is used for packet integrity verification. The corrupt ICMP checksum prevents the second host from responding to the ICMP packet.

[0045] FIG. 5A is a flow chart that shows the steps of a method of estimating data throughput of a round trip between a first host and a second host of one or more networks. A first step 510 includes the first host sending non-corrupted ICMP packets. A second step 520 includes the first host counting responses by the second host to the non-corrupted ICMP packets per unit of time. A third step 530 includes the first host determining a round trip transmission time. A fourth step 540 includes the first host estimating the round trip throughput by multiplying the number of response from the second host by the size of the packets, and dividing a result by the round trip transmission time.

[0046] As previously described, the responses can be counted by the first host by counting the responses to the non-corrupted ICMP packets.

[0047] As previously described, the round trip transmission time can be determined by comparing the time of reception of a response to a time stamp included in the ping packets. That is, the time stamp provides the start time of transmission from the first host, and the time of reception of a response provides the end time of the round trip time.

[0048] FIG. 5B is a flow chart that shows the steps of a method of determining data throughput of a first direction between a first host and a second host of one or more networks. A first step 512 includes transmitting G groups of packets, wherein each group comprises N packets in which M of the N packets are intentionally corrupted. A second step 522 includes receiving R responses to G*(N-M) non-corrupted packets. A third step 532 includes estimating a packet success rate by dividing the R responses by G*(N-M). A fourth step 542 includes estimating a first direction number of packets received by the second host by multiplying the packet success rate by G*N. A fifth step 552 includes estimating a first direction transmit time by summing a time of transmission with the round trip transmission time divided by two. A sixth step 562 includes estimating the first direction throughput by dividing the first direction number of packets received by the second host by the first direction transmit time.

[0049] FIG. 5C is a flow chart that shows the steps of a method of determining data throughput of a second direction between a first host and a second host of one or more networks. A first step 514 includes the first host sending non-corrupted ICMP packets. A second step 524 includes the first host counting responses by the second host to the non-corrupted ICMP packets per unit of time. A third step 534 includes estimating a second direction transmit time from the first direction transmit time. A fourth step 544 includes the first host estimating the second direction throughput by multiplying the number of response from the second host to the non-corrupted packets by the size of the packets, and dividing a result by the second direction transmit time.

[0050] Estimating the second direction transmit time from the first direction transmit time may provide a second direction transmit time that is a high-end estimate. Other methods could be used for determining the second direction transmit time as suggested earlier. As a result, the second direction throughput may be a low-end estimate.

[0051] Although specific embodiments of the invention have been described and illustrated, the invention is not to be limited to the specific forms or arrangements of parts so described and illustrated. The invention is limited only by the appended claims.