Abstract.
A congestion control algorithm has to cope with two types of uncertainty.
-
It receives noisy feedback from the network, e.g. in the form
of random packet drops or latency measurements, and from this noisy
signal it has to infer the level of congestion. This may be termed
probabilistic uncertainty .
-
Congestion varies, as other flows come and go. Any
measurement of congestion is always out of date—and if the
congestion controller uses any sort of smoothing to cope with
probabilistic uncertainty, then its estimates are even more out of
date.
This may be termed predictive uncertainty.
Fluid models of congestion control, used to great effect since they
were proposed by
Kelly, Maulloo
and Tan (1998), do not capture these two types of
uncertainty, and (at least in the context of multipath congestion
control) we observe behaviour that the fluid models do not predict.
I will argue that
dynamic programming rather than fluid modeling is the natural way to incorporate
these two types of uncertainty into a model for congestion control.
I will present a numerically-derived optimal congestion control
algorithm.
An optimal congestion controller (for a specific congestion model).
The top plot shows the window size and the bottom plot shows the
sender's estimate of congestion, both as a function of time. This
controller tracks congestion using two parameters: the estimated level
of congestion and the uncertainty in that estimate. It chooses its
window size to trade off optimally between sending at a
low rate when the link appears bad, and sending enough to keep its
congestion estimate reasonably accurate.