Deepak Bansal and Hari Balakrishnan

MIT Technical Report, MIT-LCS-TR-806.

This paper introduces and analyzes a class of nonlinear congestion
control algorithms called **binomial algorithms,** motivated in
part by the needs of streaming audio and video applications for which
a drastic reduction in transmission rate upon congestion is
problematic. Binomial algorithms generalize TCP-style
additive-increase by increasing inversely proportional to a power
*k* of the current window (for TCP, *k=0*); they generalize
TCP-style multiplicative-decrease by decreasing proportional to a
power l of the current window (for TCP, *l=1*). We show that
there are an infinite number of deployable TCP-friendly binomial
algorithms, all of which satisfy *k+l=1*, and that all binomial
algorithms converge to fairness under a synchronized-feedback
assumption provided *k+l > 0; k, l >= 0*. Our simulation results
show that binomial algorithms interact well with TCP across a RED
bottleneck gateway. We focus on two particular algorithms, IIAD
(inverse-increase/additive-decrease, *k=1, l=0*) and SQRT
(*k=l=0.5*), showing that they are well-suited to applications
that do not react well to large TCP-style window reductions. We
also find that TCP-friendliness in terms of the relationship between
throughput and loss rate of an algorithm does not necessarily imply
fairness relative to TCP performance, especially for drop-tail
bottleneck gateways.

[Gzipped PostScript (163KB)] [PostScript (1.1MB)] [PDF (531KB)]