Summary

  • In Keshav's 1991 model, two back-to-back packets were spaced most strongly by the bottleneck rate-allocating server; acknowledgement spacing gave the source a noisy estimate of its allocated service rate.
  • The estimate fed a rate controller whose stability was proved for a declared linear model. Fuzzy averaging, a queue setpoint and a deliberate one-RTT reset addressed noise, delay and drift.
  • Packet-pair did not reveal generic Internet capacity. The method excluded FCFS networks, depended on scheduler semantics and did not by itself guarantee packet delivery, available bandwidth or application performance.

The empty queue defeated passive observation

Keshav later recalled the moment as a researcher's story rather than a theorem. In December 1989, sitting in a Berkeley coffee shop before a Bell Labs talk, he was trying to infer the service rate offered to one flow by an intermediate router. If that flow already had a queue, acknowledgements could reflect the pace at which its packets received service. If the queue was empty, there was no train of work from which to read a pace.

His move was to manufacture the smallest possible queue. Send two packets back to back. Even an otherwise empty per-flow queue now has a first packet and a second packet waiting behind it. As the pair crosses several routers, the slowest per-conversation service point separates them the most. The returning acknowledgements can carry that spacing to the sender without a router placing an explicit rate field in the packet.

The retrospective also prevents a heroic simplification. Keshav says that Samar Singh and Ashok Agrawala independently reached the same idea at about the same time; they combined work for a joint 1991 paper. The SIGCOMM control-theory paper is Keshav's, but packet-pair should not be presented as a solitary invention. His 2019 account is an editorial note, explicitly not peer reviewed. It is good evidence for how he remembers the work, not an independent performance test.

The scheduler made the hidden state legible

The two packets were not a magic probe. They worked inside a network model whose output queues used what the paper called Rate Allocating Servers. Fair Queueing and Virtual Clock supplied the family resemblance: active conversations received approximately round-robin service, so each one could perceive a relatively stable interval between its own packet services.

That scheduler semantics mattered more than the number two. The service time at each server included the turns granted to other active conversations. The largest such interval on the path was the bottleneck service time. A back-to-back pair arrived with no intentional gap; the bottleneck imposed its own interval, and faster downstream servers did not close it under the model.

This is why the paper expressly excluded ordinary first-come-first-served networks. In FCFS, another flow's burst can abruptly change the apparent service offered to this flow. There is no equally simple state observation on which to build the same controller. The probe did not discover a universal property of packets. It exploited a property supplied by the queue discipline.

A returned spacing was an estimate, not a view

Even within the model, the sender did not see the bottleneck directly. Different queueing delays for the two acknowledgements on the reverse path could widen or narrow their separation. A server after the bottleneck could add disturbance before the packets reached the receiver. Measuring at the receiver and reporting the result would reduce some return-path noise, but could not remove all downstream effects.

The paper therefore treated the measured service rate as an observation with noise. It also modelled the true allocated rate as changing when conversations became active or idle. The controller had to predict a value for the next decision interval from an ageing and imperfect receipt.

A Kalman estimator offered a formal route, but it required system-noise and observation-noise variances that an operator would have to supply through measurement or simulation. Keshav considered that impractical. His alternative adjusted an exponential average with fuzzy rules: when the system looked steady, history received more weight; when it looked changeable, the latest observation mattered more. “Fuzzy” did not mean evidence-free. It was a disclosed policy for choosing how quickly the estimate forgot.

From observation to a bounded control decision

The controller did not simply set the sending rate equal to the last observed rate. It tracked packets outstanding, measured round-trip time, estimated bottleneck service and an inferred number of packets in the bottleneck queue. Its chosen setpoint represented a trade-off.

A queue near empty risks wasting an offered service turn because the flow has nothing ready. A queue near full raises delay and packet-loss risk. For exposition, the paper used half the per-conversation buffer allocation, B/2, under a symmetric-noise argument. It also said another setpoint could be chosen. Half-full was a model choice, not an enduring network default.

Keshav first derived a controller whose poles lay on the unit circle: it was not asymptotically stable. Introducing a placement parameter moved the poles inside the circle under the stated model. A later continuous-time form could act more frequently than once per round trip. These were meaningful results, but the proof belonged to the equations that produced it—linear dynamics, a fluid approximation, observable RAS service and defined noise assumptions. It did not certify every implementation carrying the name packet-pair.

The pause that restored the measurement's provenance

Estimates built from earlier estimates can drift. If the inferred queue occupancy moved away from the real queue, later rate decisions could remain internally consistent and externally wrong.

The proposed repair was deliberately costly. The source sent a special pair, then stopped transmitting until the pair was acknowledged. With no later packets entering, the bottleneck queue for that conversation could drain. The sender could reset the estimated queue to zero and resume. The price was roughly one round trip of unused bandwidth.

That pause is the paper's most revealing operational act. The controller did not hide uncertainty behind more smoothing. It created a condition in which a state claim could be re-grounded. Silence became a calibration procedure.

Rate control still did not guarantee zero loss. The paper proposed window control as a separate conservative ceiling on outstanding packets, supported by per-conversation buffer assumptions. The rate loop chose an operating point; the window constrained the failure edge. One mechanism could not inherit the other's promise.

What two packets could not say

The 1991 paper summarised simulations but left detailed results to Keshav's thesis and identified measurement on a real network as future work. Its linear form did not adequately model every interaction with window control. Gaussian and white-noise assumptions were acknowledged restrictions. Other users were folded into noise for a single modelled conversation.

Later packet-dispersion methods have often been discussed as tools for estimating link capacity or available bandwidth. This article does not grant those later meanings backwards. Keshav's pair estimated the service rate allocated to one conversation under RAS assumptions. It did not, by itself, prove physical link speed, unused capacity, end-to-end throughput, loss protection or application delivery.

Cambridge's biography now describes Keshav's career across Berkeley, Bell Labs, Cornell, Waterloo and sustainability research at Cambridge. His personal site notes that Keshav is his given name although syntactically last. The historical paper matters because it joined an observation to its control surface and kept the limits visible. In the language of Running-Code Primacy, the returning interval was useful only when its scheduler, path, time and uncertainty travelled with it.

Sources