Method and apparatus for measuring flow capacity of and determining the optimal window size of a communications network

[0002] The invention relates to networking in general and specifically for dynamically estimating the idle bandwidth capacity of a packet switched communications channel in a communications network for purposes such as bandwidth reservation and allocation. Once the idle capacity of a channel is determined, it is possible to estimate the optimal window size at which the channel should operate and to further improve the operation of the channel, while at the same time reducing the possibility that the bandwidth measurements will push the channel into congestion and packet loss. The idle capacity is used to make bandwidth guarantees to applications; the optimal window size is used to help achieve maximum throughput of the channel.

[0003] There is a need to determine dynamically the idle capacity of a packet communication channel in which the actual network nodes and links which form the channel cannot be predicted or controlled apriori. The Internet is such a network. The set of Internet nodes and links that form an Internet channel between a source node and a destination node anywhere in the world is unpredictable and depends on a number of variables such as the time the channel is formed and the state of spanning trees located in the various nodes that are selected as the channel is formed. Knowledge of the idle channel bandwidth at any given time is needed, for example, to allocate or reserve the bandwidth for different applications or for various purposes. It is also desirable to determine this idle bandwidth and the optimal window size on a channel that is in use, without significantly increasing the probability of channel overload and packet loss.

[0004] The effective bandwidth of a channel depends on the window size that is in use on the channel. Window size is defined as the maximum number of packets that can be in transit on a channel at any given time. One can think of the operation of a channel as a source node initially transmitting N packets, where N equals the window size, and thereafter transmitting one packet for each packet acknowledgment that is received from the destination node. In this way, one window's worth of packets are maintained in transit on the channel.

[0005] There is an optimal window size for every channel and this optimal size varies depending on channel load, among other things. When a channel is operating at below its optimal window size, queuing is not occurring at the nodes that form the channel and there is idle bandwidth available. A channel operating at above its optimal window size is experiencing queuing at the channel nodes. If the channel load is pushed too far, the queue of the worst performing node (the bottleneck node) in the channel will overflow and packet loss will be experienced.

[0006] To my knowledge, there is no known feasible way at the present time of dynamically determining the idle capacity of a channel. However, there are known methods of estimating idle capacity over a relatively large period of time by sending a large number of packets much greater that a typical window size. This characteristic of transmitting many windows worth of packets is what makes the known methods undesirable for dynamic use. Early methods of measuring idle channel capacity rely on sending packets from a source node at a constant rate and estimating performance from the arrival rate of acknowledgments and the number of packets lost. However, these methods are unreliable. At packet rates less than the processing rate of the bottleneck node in the channel, no queue is formed and performance is measured at less than the optimal performance of the channel. At packet rates even slightly greater than the processing rate of the bottleneck node, the queue quickly overloads and there is not a sustained queue in the channel from which reliable data can be obtained by use of these algorithms. Further, as mentioned, large numbers of packets are required, which detracts from their use dynamically.

[0007] Mathew Mathis addressed the problem of overload in the measuring process as described in his 1994 paper “Windowed Ping: An IP Layer Performance Diagnostic”. Mathis uses a sliding window size control to plot the performance of a channel in terms of packets in transit (window size) versus packets delivered and lost. However, Mathis's method also requires the transmission of large numbers of packets at different window sizes to plot the static performance of the channel.

[0008] Both of these methods of estimating idle capacity require the transmission of many windows worth of packets. This consumes resources and may further the tendency of a channel to congest. Thus, the known methods are not suitable for dynamically determining or estimating channel bandwidth. Further, if the optimal window size is not being used, then there is idle channel time introduced at the bottleneck node of the channel as illustrated in FIG. 3 and this tends to worsen the accuracy of bandwidth estimates.

[0009] In accordance with the invention, it has been determined that the idle capacity of a channel can be reliably estimated by transmitting only a single window of packets at whatever window size is presently in use on the channel and by measuring the time intervals between acknowledgments of adjacent packets. Preferably, an average value for the inter-acknowledgment time interval is calculated from all of the acknowledgment intervals associated with the window of packets. The idle capacity of the channel is then calculated from the formula C=1/I_Avg, where C is the idle capacity in packets per second and I_Avgis the average acknowledgment time between packets. This method of determining idle capacity is effective, even though the channel is presently operating at less than or greater than its optimal window size. This is important, since in real situations, the window size actually in use on a channel and for which a window of test packets is transmitted is usually arbitrarily selected and is usually less than the optimal bandwidth of the channel.

[0010] Preferably, all of the window of test packets is transmitted in immediate succession and results are calculated after acknowledgments are received for each of the test packets. However, even though this transmits far less than the number of packets onto the channel than prior known methods, it still introduces traffic into a channel already in use and may lead in some cases to undesirable congestion and packet loss. An alternative method may be used in some cases to meter the window of test packets over short intervals to further reduce the tendency to congest and interfere with real traffic. For example, if a window size happened to be ten packets, it would be satisfactory in most circumstances to meter the ten packets in groups of 2 or more over a number of relatively short intervals.

[0011] The same parameters that are collected to calculate the idle capacity are also used to calculate the optimal window size on a dynamic basis and each value of optimal window size is used by the protocol components of the system that controls the actual window in use to improve the performance of a channel. Since the idle channel capacity and optimal window size changes over time, preferably the estimates are periodically updated and refined.

[0012] In the drawing,

[0013] FIG. 1 shows an illustrative network useful for practicing the invention, comprising a source node and a destination node and a channel including an intermediate node linking the source and destination nodes;

[0014] FIG. 2 shows an illustrative example of a throughput graph of a channel in terms of window size;

[0015] FIGS. 3 and 4 show packet transmission and acknowledgment timing diagrams for use in explaining the operation of packet channels;

[0016] FIG. 5 shows an illustrative flowchart of test packet transmissions at a source node concerned with estimating the idle capacity of a channel;

[0017] FIG. 6 shows an illustrative flowchart of the steps taken on receipt of test packet acknowledgments at the source node in calculating the idle channel capacity and optimal window size;

[0018] FIG. 7 shows an illustrative flowchart of the steps taken at the source node when a packet acknowledgment timeout occurs, and

[0019] FIG. 8 shows an illustrative table format used for storing data relating to the times of transmission of test packets and the times of receipt of the corresponding acknowledgments, which data is used to calculate the idle bandwidth and optimal window size.

[0020] FIG. 1 shows a network channel between applications 101 in a source node 100 and a destination node 108. The channel consists of links 102 and 106 and an intermediate node 104. This channel is illustrative and should not be taken as limiting in any way. The problem is to measure, or estimate, the idle capacity of this channel at any given time and preferably dynamically. Such measurements are needed in bandwidth reservation schemes for high-speed networking to guarantee quality of service (QoS) for certain applications and for other purposes. It is assumed for the purposes of discussion that each node is running a TCP/IP protocol stack for channel communications. TCP/IP is well known. In fact, it is the protocol of the Internet and no particular details of its protocol operation are deemed necessary for an understanding of the invention. Additionally, the invention applies to other protocols that are used for packet transmission.

[0021] The TCP/IP protocol stack is shown in each of the nodes 100 and 108 as a TCP layer 110 that serves general applications 101, a resource reservation component (RSVP) 112 that, among other functions, controls the window size used on the channel and allocates or guarantees bandwidth chosen by the applications, and an IP protocol layer 114 for controlling packet transmission at the link level. In accordance with the invention, the IP layer also communicates with a software measuring tool 116 that performs the dynamic determination of idle capacity and optimal window size. Tool 116 is shaded to emphasize that it represents the novel aspects of FIG. 1. Each node of the network contains one or more computers (not 10 explicitly shown in FIG. 1 for simplicity) of a general or special nature to execute the software associated with the applications, the protocol stack and the tool for estimating the idle channel bandwidth.

[0022] FIG. 2 shows a graph of the normal throughput (capacity) of a channel in terms of window size in use. If the channel is empty, FIG. 2 represents the total channel capacity. If the channel is carrying traffic, Fig, 2 represents the idle capacity remaining on the channel. The part of the curve labeled 200 represents the capacity of the channel for window sizes that are too small to initiate queuing at any of the channel nodes. This represents idle capacity of the channel and, accordingly, channel throughput increases over this part of the curve as window size is increased. The knee of the curve occurring at 202 of FIG. 2 represents the optimal window size. This is the point at which packet queuing begins to occur in one or more nodes of the channel. Along the part of the curve labeled 204, the queues in one or more channel nodes are increasing in size. Because of the queuing, the throughput on the channel tends to remain constant along this part of the curve. At point 206 of the curve, queue overflow starts to occur and, as a result, packet loss and reduced throughput begins to occur. This is illustrated by that portion of the curve labeled as 208. It should also be noted that the optimal window size N_opttends to change on a channel according to a number of parameters such as the number of nodes in a channel and the length of the channel. The problem then is, at any given time, to find the idle throughput value represented by the stable portion of the curve at 204, and additionally, to determine N_optat any given time, all according to the level of traffic the channel is already carrying at a that time.

[0023] The theoretical basis for the invention is first presented.

[0024] It is assumed that the average data rates of the links between channel nodes are larger than the average processing data rates of the channel nodes. In equilibrium, this implies that the average rate of acknowledgment arrivals at a source node is equal to this maximum average throughput. These two rates also equal the average rate of packet departures from the source node. This is because when the system is in equilibrium, a new packet is injected in the network only when an acknowledgment arrives from the destination node; it also means that there is a full window of packets in transit on the channel. We first start with some notation.

[0025] d_n=Departure time from the source node of the nth packet.

[0026] a_n=Arrival time of the nth acknowledgment packet from the destination.

[0027] I_n=Inter-acknowledgment time interval between packets n+1 and n.

[0028] RTT_n=Round trip time of packet n.

[0029] Then we have the following two expressions:

[0030] I_n=a_n+1−a_n  [1]

[0031] RTT_n=a_n−d_n  [2]

[0032] The sustainable idle capacity of a channel is defined as $\begin{array}{cc}C=\underset{n\to \infty }{\lim }\frac{n}{a_n-d_1}.& \left[3\right]\end{array}$

[0033] The expression inside the limit on the right hand side of the above equality is the average throughput achieved along the channel when sending a file of size n packets. If I denotes the inter-acknowledgment time between packets, then $\begin{array}{cc}I=\underset{n\to \infty }{\lim }\frac{\prod _{k=1}^n{I}_k}{n}.& \left[4\right]\end{array}$

[0034] After some straightforward arithmetic, we have:

[0035] C=1/I  [5]

[0036] It can be shown that I_k=S_maxfor all integers k, where S_Maxis the average packet processing time at the bottleneck node.

[0037] From equation 4 then:

[0038] I=S_Max,  [6]

[0039] and combining with equation 5 we have

[0040] C=1/S_max.  [7]

[0041] This shows that it is sufficient to determine a representative value of the inter-acknowledgment time interval between successive packets to determine an estimate of the idle capacity of a channel.

[0042] FIGS. 3 and 4 give further insight into the operation of a channel consisting of three nodes, a source node N1, a channel node N2 and a destination node N3. This example channel has been arranged for illustrative purposes to have an optimal window size of two packets. In FIG. 3, the channel is operating at a sub-optimal window size of one packet. To maintain a window's worth, or less, of packets on the channel, the protocol rules state that after an initial window's worth of packets are transmitted, the source node N1 cannot transmit another packet until it receives an acknowledgment from a previously transmitted packet. Thus, node N1 begins by transmitting packet 1 (a windows worth in this example) at time t1. Node N2 receives packet 1 at t2 and immediately begins to process it. Node N3 receives packet 1 at t3 and immediately begins to process it. Node N3 finishes processing packet 1 at t4 and immediately returns an acknowledgment to node N1. Therefore, node N1 transmits packet 2 essentially at t4. Node N2 cannot begin to process packet 2 until it receives it at t5. The time difference between t5 and t4 represents wasted channel time at node N2 and, in this example, node N2 is the bottleneck node. The wasted time at N2 is caused by running the channel at other than the optimal window size.

[0043] FIG. 4 shows the same example as FIG. 3, except that the channel is now assumed to be operating at its optimal window size of two packets. Thus, node N1 initially starts at t1 by transmitting two packets, packet 1 and packet 2 (a windows worth). Node N2 receives packet 1 and begins to process it at t2. At t3, N2 transmits packet 1 to node N3 and begins to process packet 2. Node N3 completes the processing of packet 1 at t4 and returns an acknowledgment to node N1, at which time node N1 transmits packet 3 to node N2. In this example, notice that there is no longer any idle time at node 2, as in FIG. 1.

[0044] We now describe the operation of the measuring tool 116 of FIG. 1 to determine the idle capacity of a channel and its optimal window size as discussed above. In the implementation described below, use is made of the Windowed Ping program described in the Mathis paper mentioned earlier. Windowed Ping is used as a convenience, because it implements a packet sequence number algorithm in which transmitted packets are assigned sequence numbers and returning acknowledgments identify the packet sequence number with which they are associated. This ability is used, as will be seen, to account and compensate for lost test packets. However, this preferred embodiment does not make use of the sliding window described in the Mathis paper.

[0045] When the tool 116 is first initiated, an entry is made to program label Start 500 in FIG. 5. Step 502 initially selects an arbitrary window size, which is two in this illustrative example. The initial window size of two is selected because this should minimize the probability of the test packets pushing the channel into an overflow condition. Step 504 prepares two (N) test packets for transmission from source node 100 to destination node 108 of FIG. 1. This step includes adding a sequence number to each test packet. Step 505 clears the table in FIG. 8 so that it does not contain old data. Steps 506, 508, 510 and 512 constitute a loop in which the N test packets are transmitted in immediate succession to the destination node. For each test packet, step 508 records in the “SENT” field 800 of FIG. 8 the time of packet transmission for later calculations. The entry is made into the record of the table corresponding to the sequence number of the test packet. For example, the transmission time of test packet 1 is recorded in record 1, that for test packet is recorded in record 2, and so on. This is important in this illustrative embodiment, because records ordered by sequence number are used in conjunction with a RETRANSMIT counter field 804 of the table subsequently to properly account in the calculations for test packets which were lost at least once and had to be retransmitted. This is described in more detail below with respect to FIG. 7. In this example, only two records are shown in FIG. 8. When the N test packets have been transmitted, step 512 initiates a Retransmission Timer to a value that is much greater than the expected time to receive an acknowledgment for the last of the test packets. If the timer expires before all acknowledgments are received, then an entry is made to the program of FIG. 700 to detect which packet or packets were lost and to retransmit them. This portion of the measuring tool 116 now terminates for the time being at label End 514 of FIG. 1. The tool now waits for the return of an acknowledgment packet or an acknowledgment timeout. At the receiving node 108, the corresponding tool 116 receives the test packets, retrieves the sequence number from each test packet as it is received and returns an acknowledgment which includes the sequence number.

[0046] Assuming that an acknowledgment is received in short order, that acknowledgment causes a program entry to AckRcvd 600 in FIG. 6. Step 602 obtains from the acknowledgment packet the sequence number of the associated test packet and uses this sequence number to locate the storage record in FIG. 8 associated with the test packet. Step 602 then records in the record the time of receipt of the acknowledgment. Step 604 determines if a total of N acknowledgments have been received, thus indicating that calculations may now proceed. However, there is the possibility that one or more test packets may get lost which will prevent N acknowledgments form ever being received at step 604 if this situation is not detected. If a test packet should get lost, then step 604 will not be satisfied even when the acknowledgment for packet N is received. Eventually the retransmission timer set at step 512 will expire, causing an entry at program label AckTimeout 700 in FIG. 7. In this event, step 702 determines the sequence number or numbers of lost packets by searching the FIG. 8 records for times of received acknowledgments. Records with no recorded time of receipt of an acknowledgement have been lost. Step 704 retransmits a test packet with the same sequence number as each lost packet. Step 706 then replaces the time of transmittal of each test packet in the appropriate packet record from step 602 with the present time and increments the RETRANSMIT counter for each such packet. Step 708 restarts the retransmission timer. When the acknowledgment from these retransmitted packets arrive, step 604 is satisfied and processing of results begins at step 606 to calculate the idle capacity and optimal window size of the channel at the present time. If a retransmitted packet also gets lost, the retransmission timer will eventually expire again, and the above steps will be repeated until eventually N acknowledgments are received for each of the N test packets.

[0047] Step 606 sets up a loop counter to loop through each of the N records. Step 608 uses the recorded times of transmission and acknowledgment receipt to calculate the round-trip-time (RTT) for the present ith packet of the loop. Next, the inter-acknowledgment time between packets i and i−1 is calculated. This requires special processing in case the present loop packet number is 1 or in case a packet was retransmitted. For packet number 1, there is no inter-acknowledgment time to be calculated. Therefore, step 610 returns to step 608 to process the next packet if the present packet number being processed is packet 1. If the present packet being processed is not packet 1, step 610 passes to step 612, which determines if either of the present packet i or the former packet i−1 was retransmitted and, if so, how many times. If adjacent packets are retransmitted a different number of times, then a calculation of the inter-acknowledgment time using the values in FIG. 8 for either of these records would yield invalid results. Therefore, if either packet was retransmitted and the adjacent packet was not retransmitted or retransmitted a different number of times as indicated by the value in the RETRANSMIT counter field of FIG. 8, step 612 skips the inter-acknowledgment time calculation by moving directly to step 616. If the present and immediately preceding packets were not retransmitted, or retransmitted the same number of times, step 614 calculates the inter-acknowledgment time I=A_i−A_i-1, where A_iis the acknowledgment time of the ith packet from FIG. 8. Step 616 next determines if the loop is finished. If not, step 616 returns to step 608 to process the next packet. If all test packets have been processed, the remaining steps calculate the overall results of the set of test packets. Step 618 uses the individual values for RTT to calculate an average RTT_Avg,.Step 618 uses the inter-acknowledgment times for each packet for which an inter-acknowledgment time was calculated at step 614 to calculate an average inter-acknowledgment time I_avg. Step 618 then calculates the idle capacity of the channel from the formula C=1/I_avgpackets per second. Finally, step 618 estimates the optimal window size at the present time from the formula N_opt=RTT_Avg*C. This value of N_optis stored for the next iteration of test packets at step 620. Step 622 cancels the retransmission timer and schedules a re-entry to the Repeat function at 516 to run the test packets again at a later time. Finally, step 624 stores the newly calculated values of N_optand C for use by the packet layer component RSVP 112 of FIG. 1 in allocating bandwidth and for honing the performance of the channel.

[0048] At a later time as scheduled by step 622, the function Repeat 516, when entered, reads the calculated value of N_optfrom the previous iteration and uses that value to determine (step 518) the number of test packets for the next iteration. In this manner, the accuracy of the calculations should, in general, converge toward more accurate values.

[0049] In accordance with conventional practice in the software industry, It is possible to store and distribute the software associated with the tool 116 by means of magnetic media such as floppy disks, CD-ROMs, magnetic tape, and the like.

[0050] It is to be understood that the above described arrangements are merely illustrative of the application of principles of the invention and that other arrangements may be devised by workers skilled in the art without departing from the spirit and scope of the invention.